Modern 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.

High-dimensional dense embeddings have become central to modern Information Retrieval, but many dimensions are noisy or redundant. Recently proposed DIME (Dimension IMportance Estimation), provides query-dependent scores to identify informative components of embeddings. DIME relies on a costly grid search to select a priori a dimensionality for all the query corpus’s embeddings. Our work provides a statistically grounded criterion that directly identifies the optimal set of dimensions for each query at inference time. Experiments confirm that this approach improves retrieval effectiveness and reduces embedding size by an average 50% of across different models and datasets at inference time.