TL;DR
STORM is a new self-supervised framework for lexical query expansion that uses a novel reward-guided beam search to turn delayed, sequence-level retrieval rewards into token-level guidance. By pruning ineffective expansion terms during generation, STORM enables small, open-source language models (0.6B to 8B parameters) to match or outperform massive proprietary models and dense retrievers while maintaining the blazing-fast speed of traditional BM25 search.
What Problem Does This Paper Address?
In Information Retrieval (IR), traditional lexical search methods like BM25 are highly efficient and easy to maintain because they rely on simple inverted indices. However, they suffer from vocabulary mismatch—if a user searches for "diabetes diet," BM25 might miss a highly relevant document that uses the phrase "medical care for blood sugar management" instead.
To fix this, modern search engines often use dense neural retrievers (like DPR or ColBERT). While effective, dense retrievers require encoding the entire document corpus into massive vector indices. Whenever the model changes, the entire index must be rebuilt from scratch, creating a massive infrastructure burden.
An alternative is LLM query rewriting, where a language model expands the user's query with relevant keywords before sending it to BM25. The challenge here is optimization. Standard reinforcement learning (RL) approaches only provide a reward after the full sequence is generated. This creates an exploration bottleneck: the model doesn't know which specific word helped or hurt retrieval, often causing it to generate generic terms or drift away from the user's original intent.
Methods
The authors introduce STORM (Stepwise Token Optimization with Reward-guided beaM search) to solve this credit-assignment problem.
Instead of waiting until the end of a sentence to score a rewrite, STORM integrates the retriever directly into the LLM's generation loop during training. At each token generation step, candidate keyword expansions are evaluated against the actual BM25 index. Branches that yield low retrieval rewards are immediately pruned. This effectively converts a delayed, sequence-level reward into an immediate, token-level signal.
STORM adapts the Generative Cooperative Networks (GCN) framework, replacing a learned discriminator with a fixed, multi-faceted reward function:
- Retrieval Quality (nDCG): Evaluated using dense cross-encoder pseudo-labels from MS-MARCO.
- Document Frequency (DF) Penalty: Explicitly penalizes overly common words to prevent the model from generating generic terms that slow down index lookups.
- Log-Likelihood Regularizer: Acts as a length constraint and provides a useful prior for token selection.
Datasets
STORM was trained and evaluated on several standard information retrieval benchmarks:
- Training: A sample of approximately 80,000 queries from the MS-MARCO passage-retrieval training set.
- In-Domain Evaluation: TREC DL '19, TREC DL '20, and the MS-MARCO dev set.
- Out-of-Domain Evaluation (BEIR): 12 diverse text retrieval collections (including NFCorpus, SciFact, TREC-COVID, FiQA, and Robust04) totaling over 14,000 queries.
- Multilingual Evaluation: MIRACL, a benchmark covering 18 different languages.
Key Insights and Ideas
- Beam Search as a Training Tool: Beam search is traditionally used only at inference time to find high-probability text. STORM uniquely repurposes it as a training-time exploration mechanism to guide the policy toward retrieval-effective vocabulary.
- Efficiency by Design: By penalizing high document-frequency terms in the reward function, the model naturally learns to generate short, highly discriminative keywords. This prevents the query from bloating and keeps search times low.
- Zero-Shot Language Transfer: Despite being trained exclusively on English MS-MARCO data, STORM successfully transfers to 18 non-English languages. It doesn't just memorize English word associations; it learns a language-independent strategy for selecting high-impact, content-bearing terms.
Key Results
State-of-the-Art Accuracy at Scale
Across the BEIR out-of-domain benchmarks, STORM-8B achieved the highest mean nDCG@10 score compared to other LLM-based rewriters. Remarkably, STORM-8B achieved an average score of 54.8, outperforming much larger proprietary models like GPT-4-based query rewriters (such as MuGI-GPT4 at 54.5).
Blazing Fast Latency
Competing LLM rewriters often generate long pseudo-documents, which dramatically increases downstream BM25 retrieval times. STORM breaks this pattern. Its retrieval latency matches plain BM25 (0.01 seconds) because it generates concise keyword strings and avoids costly index lookups.
Surpassing Dense Multilingual Retrievers
In zero-shot evaluations on the 18-language MIRACL dataset, STORM-8B achieved an average nDCG@10 of 48.4. This represents a +9.9 point gain over plain BM25 and actually outperforms dedicated multilingual dense retrievers like mColBERT (44.1) and mContriever (43.1), which were explicitly trained with multilingual data.
Limitations and Future Work
Despite its strong out-of-domain performance, STORM still exhibits an in-domain effectiveness gap behind learned sparse retrievers like SPLADE-v2 on MS-MARCO. This suggests that while STORM is excellent at finding discriminative keywords, it still struggles to capture the richer contextual and semantic relationships that native neural sparse retrievers encode through internal term-weighting.
Additionally, STORM's performance is sensitive to its maximum generation length budget. While 64 tokens provide the best latency-effectiveness trade-off for English queries, multilingual benchmarks like MIRACL require up to 128 tokens for optimal results. The authors point to adaptive, query-dependent length control as an important direction for future work.
Summary updated