# STORM: Stepwise Token Optimization with Reward-Guided Beam Search

arXiv: https://arxiv.org/abs/2606.10621 · HTML: https://mlsanity.com/paper/2606.10621/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 39 references that are in the map.
- First posted on arXiv 9 Jun 2026.

## Builds on (most cited first, 24 of 24)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [Unsupervised Dense Information Retrieval with Contrastive Learning](https://mlsanity.com/paper/2112.09118/) (2021)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [Passage Re-ranking with BERT](https://mlsanity.com/paper/1901.04085/) (2019)
- [Precise Zero-Shot Dense Retrieval without Relevance Labels](https://mlsanity.com/paper/2212.10496/) (2022)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [Overview of the TREC 2019 deep learning track](https://mlsanity.com/paper/2003.07820/) (2020)
- [Overview of the TREC 2020 deep learning track](https://mlsanity.com/paper/2102.07662/) (2021)
- [RQ-RAG: Learning to Refine Queries for Retrieval Augmented Generation](https://mlsanity.com/paper/2404.00610/) (2024)
- [SPLADE v2: Sparse Lexical and Expansion Model for Information Retrieval](https://mlsanity.com/paper/2109.10086/) (2021)
- [Mr. TyDi: A Multi-lingual Benchmark for Dense Retrieval](https://mlsanity.com/paper/2108.08787/) (2021)
- [mMARCO: A Multilingual Version of the MS MARCO Passage Ranking Dataset](https://mlsanity.com/paper/2108.13897/) (2021)
- [Pyserini: An Easy-to-Use Python Toolkit to Support Replicable IR Research with Sparse and Dense Representations](https://mlsanity.com/paper/2102.10073/) (2021)
- [RaFe: Ranking Feedback Improves Query Rewriting for RAG](https://mlsanity.com/paper/2405.14431/) (2024)
- [Query expansion techniques for information retrieval: A survey](https://mlsanity.com/paper/1708.00247/) (2017)
- [MS MARCO: Benchmarking Ranking Models in the Large-Data Regime](https://mlsanity.com/paper/2105.04021/) (2021)
- [Generative Query Reformulation for Effective Adhoc Search](https://mlsanity.com/paper/2308.00415/) (2023)
- [Can Generative LLMs Create Query Variants for Test Collections? An Exploratory Study](https://mlsanity.com/paper/2501.17981/) (2025)
- [Towards Competitive Search Relevance For Inference-Free Learned Sparse Retrievers](https://mlsanity.com/paper/2411.04403/) (2024)
- [A Reproducibility Study of LLM-Based Query Reformulation](https://mlsanity.com/paper/2604.27421/) (2026)
- [QueStER: Query Specification for Generative keyword-based Retrieval](https://mlsanity.com/paper/2511.05301/) (2025)

## Abstract (arXiv)

Modern retrieval increasingly relies on dense and learned-sparse neural models that are effective but require encoding the entire corpus into a specialized index, rebuilt whenever the model changes. Lexical retrievers like BM25 stay efficient and transparent on a standard inverted index that need not change as models evolve, but suffer from vocabulary mismatch. LLM query rewriting can help, yet prompted rewriters emit well-formed but retrieval-ineffective or harmful-terms, and training against a retrieval reward gives only delayed, sequence-level supervision that obscures which terms helped. We introduce STORM (Stepwise Token Optimization with Reward-guided beaM search), a self-supervised framework for lexical query expansion. STORM trains the rewriter through generation guided by retrieval metrics: at each step, candidate expansions are scored against the BM25 index and low-reward continuations pruned, turning the retrieval reward into a token-level signal that concentrates exploration on retrieval-effective vocabulary. Across TREC DL and BEIR, STORM lets 0.6B-8B backbones match or surpass competitive LLM rewriters while retrieving as fast as plain BM25; at 8B it rivals far larger proprietary rewriters. It further transfers zero-shot to 18 languages (MIRACL), beating dedicated multilingual dense retrievers on average, making STORM a competitive, infrastructure-light alternative to dense neural retrieval.