Source-linked AI summary
RankEvolve: Automating the Discovery of Retrieval Algorithms via LLM-Driven Evolution
Jinming Nian, Fangchen Li, Dae Hoon Park, Yi Fang
TL;DR
Lexical ranker improvements have largely depended on parameter tuning and human intuition, motivating automated discovery of better retrieval algorithms. RankEvolve uses evaluator-guided LLM evolution over executable programs seeded by BM25 and QL-Dir, producing novel algorithms that outperform seeds and transfer to held-out benchmarks, albeit with substantial latency costs.
Problem
Improved lexical retrieval has largely relied on parameter tuning and human intuition despite BM25 and query likelihood remaining strong first-stage rankers.
Method
RankEvolve evolves executable ranking programs from BM25 and QL-Dir seeds using LLM-guided mutation, recombination, and evaluator-based selection.
Results
Evolved programs consistently outperform their seeds and established variants on held-out benchmark datasets, with novel scoring motifs transferring to unseen datasets.
Takeaways & Limitations
Evaluator-guided LLM program evolution is a promising approach for automatically discovering novel lexical retrieval algorithms.
Takeaways & Limitations
The best-performing BM25★ program is roughly 11× slower than BM25 because latency is not part of the optimization target.
Abstract
from arXiv · showhide
Retrieval algorithms like BM25 and query likelihood with Dirichlet smoothing remain strong and efficient first-stage rankers, yet improvements have mostly relied on parameter tuning and human intuition. We investigate whether a large language model, guided by an evaluator and evolutionary search, can automatically discover improved lexical retrieval algorithms. We introduce RankEvolve, a program evolution setup based on AlphaEvolve, in which candidate ranking algorithms are represented as executable code and iteratively mutated, recombined, and selected based on retrieval performance across 12 IR datasets from BEIR and BRIGHT. RankEvolve starts from two seed programs: BM25 and query likelihood with Dirichlet smoothing. The evolved algorithms are novel, effective, and show promising transfer to the full BEIR and BRIGHT benchmarks as well as TREC DL 19 and 20. Our results suggest that evaluator-guided LLM program evolution is a practical path towards automatic discovery of novel ranking algorithms.
1 Introduction
BM25 and query-likelihood rankers remain strong and efficient, but improved lexical retrieval has mainly come from parameter tuning and human intuition. RankEvolve addresses this gap by evolving executable ranking programs with LLM-guided, evaluator-driven search.
- BM25 and query-likelihood rankers remain strong and efficient first-stage lexical retrieval algorithms.
- Prior lexical retrieval improvements largely relied on tuning parameters and manually designing scoring components.
- RankEvolve represents candidate ranking algorithms as executable Python programs that LLMs iteratively mutate and recombine using performance-driven selection.
- The system starts from BM25 and query likelihood with Dirichlet smoothing, evolving each seed for several hundred steps.
- The evolved algorithms introduce scoring mechanisms absent from either seed family and show promising transfer to held-out BEIR, BRIGHT, and TREC DL datasets.
- RankEvolve suggests evaluator-guided LLM program evolution can automate discovery of novel lexical retrieval algorithms.
2 Related Work
Prior work has used genetic programming to discover ranking functions from arithmetic combinations of information-retrieval features, while grid search tunes fixed functions. RankEvolve differs by using LLM-guided evolution to search executable retrieval programs.
- Genetic programming has evolved ranking functions by combining tf, idf, and document length features with arithmetic operators.
- Earlier genetic-programming systems evolved local and global term-weighting schemes that competed with BM25.
- Grid search provides a simpler alternative but remains limited to tuning hyperparameters within a fixed retrieval function.
- RankEvolve differs fundamentally by evolving executable retrieval algorithms through LLM-guided program search.
3 Method
RankEvolve defines retrieval discovery as LLM-guided evolutionary program synthesis: seed programs specify the search space, populations preserve diverse candidates, and an evaluator supplies retrieval fitness.
- 3 Method: RankEvolve frames improved retrieval discovery as program synthesis driven by iterative LLM mutation and performance-based selection.
- 3.1 Search Space: The seed program and system prompt jointly define which retrieval-program components are evolvable and how candidates are generated.
- 3.1 Search Space: BM25 seeds expose document representation, query representation, and scoring function as three evolvable components.
- 3.1 Search Space: QL-Dir adds the collection language model as a fourth evolvable component, with its initial probability defined from corpus term frequency and corpus size.
- 3.2 Population: The population combines island-based evolution with MAP-Elites to preserve independent lineages and organize candidates by complexity and diversity.
- 3.2 Population: At each iteration, parent selection mixes exploration, elite exploitation, and performance-proportional sampling while supplying additional reference programs to the LLM.
- 3.4 Evaluator: The evaluator executes tokenization, indexing, and retrieval, returning nDCG@10, Recall@100, and latency; fitness is 0.8 × Avg Recall@100 + 0.2 × Avg nDCG@10.
4 Experiments
RankEvolve evolves lexical ranking programs from BM25 and QL-Dir seeds, producing structurally novel algorithms with strong held-out performance and convergent retrieval strategies. Its optimization favors Recall@100, while allowing occasional nDCG@10 regressions, and greater structural freedom improves scores but can trade benchmark-specific strengths and latency.
- 4 Experiments: BM25 and QL-Dir remain strong, efficient baselines, but prior improvements largely rely on parameter tuning and human intuition.
- 4.3 Results: BM25★ outperforms BM25 baselines on BRIGHT and BEIR Recall@100, while QL-Dir★ consistently outperforms QL-Dir and QL-JM across all three benchmarks.Gains are statistically significant over the respective seeds on most evaluation groups and extend to unseen datasets.
- 4.3 Results: Recall@100 improves nearly monotonically, whereas nDCG@10 sometimes regresses because the optimization target weights Recall 0.8× and nDCG 0.2×.The combined score is monotonically increasing throughout optimization, so mutations may trade small nDCG losses for larger Recall gains.
- 4.4 The Evolved BM25 Algorithm: The best evolved BM25 algorithm departs from BM25 through multi-channel tokenization and a product of bounded scoring multipliers over lexical features.Its channels include prefixes, bigrams, and gated character 3-grams; its multipliers encode coverage, specificity, coordination, anchoring, and length effects.
- 4.5 The Evolved Query Likelihood Algorithm: The evolved QL algorithm retains an additive language-model architecture while adding missing-term penalties, soft-AND coverage, adaptive TF exponents, and an enriched collection model.Its collection model flattens raw probabilities, mixes document-frequency estimates, and adds a uniform safety component.
- 4.6 Convergent Principles Across Seeds: Both evolved seeds independently converge on term-frequency saturation, soft stopword filtering, coordination mechanisms, and gentle length normalization despite using different architectures.The evolved BM25 uses multiplicative modulation and multi-channel tokenization, while evolved QL uses additive penalties and per-term adaptive exponents.
5 Ablation Study
Seed structure strongly shapes RankEvolve’s search: greater structural freedom improves optimization targets on seen and held-out datasets, while different structures produce complementary benchmark strengths.
- Effect of seed structure: Greater structural freedom yields monotonically higher optimization target scores on both the 12 evaluator datasets and 16 held-out datasets.Constrained evolution converges earliest with the smallest gains; freeform evolution converges last but achieves the best scores on seen and unseen data.
- Complementary strengths across structures: The freeform variant achieves the highest BRIGHT Recall@100, BEIR Recall@100, and TREC DL nDCG@10, but composable and constrained variants lead on selected metrics.Freeform TREC DL Recall@100 is 47.10 versus 48.62 for composable, while freeform BEIR nDCG@10 is 47.90 and below the constrained variant’s value.
- Influence on the discovery process: Different seed structures impose distinct inductive biases that shape search trajectories and expose trade-offs across nDCG, Recall, TREC DL, and BRIGHT.Constrained seeds preserve BM25-like behavior, whereas composable seeds can rewrite scoring primitives while retaining the pipeline skeleton.
- Influence on the discovery process: Multiple seed structures can support deployment-specific selection or ensembling rather than single-objective optimization.The diverse high-performing program family offers variants emphasizing different benchmark and metric trade-offs.
- Overall comparison: The freeform seed remains strongest on average, achieving the highest optimization target on both 12 seen and 16 unseen datasets.The passage presents maximal structural freedom as the best risk–award trade-off when one general-purpose retrieval function is needed.
6 Latency
RankEvolve’s effectiveness gains carry increasing computational cost: indexing overhead remains negligible, but more complex evolved programs substantially increase query latency.
- Latency trade-offs: Indexing overhead is negligible, while the best-performing BM25★ at step 293 is roughly 11× slower per query than seed BM25.Latency is averaged across all 28 datasets and was visible during evolution but excluded from the optimization target.
- Latency trade-offs: The constrained variant adds virtually no overhead, with latency of 58.50 versus 56.72 ms/query, while still improving the optimization target.Its gains therefore stem almost entirely from parameter tuning rather than major algorithmic changes.
- Late-stage evolution: From freeform step 177 to step 293, continued recall and nDCG improvements accompany a 3.8× further increase in query latency.Step 177 had already achieved strong effectiveness with latency within a modest 3× of baseline.
7 Conclusion and Future Work
RankEvolve uses LLM-guided program evolution to discover lexical retrieval algorithms that outperform their seeds and established variants on held-out benchmarks. The authors identify structural freedom and efficiency objectives as important directions for future work.
- Conclusion: RankEvolve applies LLM-guided program evolution to discover lexical retrieval algorithms from BM25 and QL-Dir seeds.The framework represents ranking functions as evolving programs and evaluates the resulting algorithms on retrieval benchmarks.
- Conclusion: The evolved functions consistently outperform their seeds and established variants on held-out benchmark datasets while rediscovering and reformulating established IR concepts.The conclusion reports both effectiveness and novelty in the evolved algorithms.
- Future work: The ablation indicates that seed-program structural freedom determines the ceiling of what RankEvolve can discover.The conclusion also notes that evolved algorithms are much more complex than their seeds.
- Future work: Future extensions include explicit efficiency constraints and application beyond lexical retrieval to dense retrieval, learned sparse representations, and LLM reranking.These extensions follow from optimizing whatever objective the evaluator defines.
A Full Evolved BM25 Scoring Function
The evolved BM25 scoring function combines evidence from multiple token spaces with bounded coordination, specificity, coverage, anchor, term-weight, and length mechanisms.
- Scoring architecture: The top-level scoring function applies a shared core function across four parallel token spaces, and the core combines base evidence with bounded multipliers.The appendix presents complete component definitions for this evolved BM25 algorithm.
- Term weighting: Term weights use diminishing repeated-query-term credit and IDF-based factors that suppress stopword-like terms while preserving rare-term contributions.A term with IDF ≈1 receives very small weight, whereas a term with IDF ≈8 passes through nearly unaffected.
- Coverage: The coverage multiplier rewards breadth of match, giving a document matching all query terms a 1.25× boost.The multiplier uses the fraction of total query importance satisfied by the document.
- Specificity: The specificity multiplier uses pointwise mutual information to reward terms over-represented in a document relative to their corpus-wide rate.A cap of 3.0 and document-length floor of 25 prevent extreme values.
- Coordination and rare terms: The coordination bonus adapts to query difficulty and avoids double-counting coverage, while the anchor multiplier safeguards recall for rare terms.Only the single rarest matched term contributes to the bounded anchor boost, and coordination calibration varies with query difficulty.
- Length normalization: The length dampener replaces BM25’s per-term linear normalization with a global logarithmic penalty that grows slowly for extremely long documents.A document twice average length is penalized by roughly 10%, compared with up to 40% under BM25 with b=0.4.
B Full Evolved Query Likelihood Scoring Function
The evolved query-likelihood ranker replaces standard collection smoothing with an enriched language model and combines adaptive term weighting, gated likelihood scoring, coverage bonuses, penalties, and length priors.
- Enriched collection language model: The enriched collection model tempers raw collection probabilities with τ=0.85, renormalizes them, interpolates document-presence probabilities, and adds a uniform component.Document-frequency smoothing reduces sensitivity to bursty within-document repetition, while the uniform component prevents zero background probabilities.
- Adaptive term-frequency saturation: Adaptive saturation sets β(t) from normalized IDF, aggressively saturating common-term frequencies while preserving the full signal for rare terms.β(t) is approximately 0.70 for common terms and approximately 1.0 for rare terms.
- Gated Dirichlet log-likelihood: The gated Dirichlet log-likelihood uses μ=1750 and an Entity Dispersion Ratio gate to adjust term contributions according to document spread.The lower μ is attributed to the more uniform tempered background model, while the EDR gate upweights broadly dispersed informative terms and downweights concentrated frequent terms.
- Query term weight: Composite query-term weights boost broadly distributed terms and apply sub-linear 0.6 damping to repeated query terms.The residual weight ranges from 1.0 to 1.9, limiting over-counting from verbose or repetitive queries.
- Penalties: A leaky rectifier retains negative per-term evidence at 12%, while a separate scaled Dirichlet penalty handles completely missing query terms.Together, these mechanisms penalize weak matches and absent terms at distinct granularities.
- Coverage and length prior: The soft-AND bonus rewards breadth of query-term matching, and a Gaussian log-length prior mildly penalizes documents deviating from average corpus length.Coverage is normalized to [0, 1], while a document 10× the average length receives an approximately −0.32 penalty.