STORM makes BM25 rival dense retrieval with LLM query rewriting

Lexical retrievers like BM25 are efficient and transparent but suffer from vocabulary mismatch. LLM query rewriting can help, but prompted rewriters often produce ineffective or harmful terms, and training against retrieval reward gives only sequence-level supervision. Enter STORM (Stepwise Token Optimization with Reward-guided beaM search), a self-supervised framework that trains a rewriter through generation guided by retrieval metrics. At each step, candidate expansions are scored against the BM25 index and low-reward continuations pruned, transforming retrieval reward into a token-level signal that focuses exploration on retrieval-effective vocabulary.

Across TREC DL and BEIR benchmarks, STORM allows 0.6B–8B backbone LLMs to match or surpass competitive LLM rewriters while retrieving as fast as plain BM25; at 8B parameters, it rivals far larger proprietary rewriters. Crucially, STORM transfers zero-shot to 18 languages in the MIRACL benchmark, beating dedicated multilingual dense retrievers on average. This makes STORM a compelling, infrastructure-light alternative to dense neural retrieval—no need to rebuild specialized indexes when models change, just standard inverted indexes.