STORM: Stepwise Token Optimization with Reward-Guided Beam Search
Abstract
AbstractModern retrieval increasingly relies on dense and learned-sparse neural models that are effective but require encoding the entire corpus into a specialized index, which must be rebuilt whenever the model changes. Lexical retrievers like BM25 stay efficient, transparent, and run 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 with retrieval feedback for lexical query expansion. STORM trains the rewriter through generation guided by retrieval metrics: at each step, a beam of candidate expansions is scored against the BM25 index and low-reward continuations are 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 and far larger proprietary models while retrieving as fast as plain BM25, and transfers zero-shot to 18 languages (MIRACL), beating dedicated multilingual dense retrievers. STORM is thus a competitive, infrastructure-light alternative to dense neural retrieval.