PaperlayerView exact revision on arXiv

Source-linked AI summary

BM25 Wins at Scale: A Scaling Study of Retrieval-Augmented Generation Paradigms

Pengyu Wang, Benfeng Xu, Shaohan Wang, Mingxuan Du, Xin Zeng, Huarui Wu, Lei Zhang, Licheng Zhang

arXiv:2607.26497v3cs.CL

TL;DR

Existing RAG paradigms are commonly compared at different benchmarks and corpus sizes, leaving their accuracy-cost scaling unclear. This paper conducts a controlled 28-tier corpus-scaling study with fixed questions, evidence, distractors, reader, and judging protocol, finding that File-System Agent leads early but BM25 overtakes it around 10 million corpus tokens and leads thereafter.

  • Problem

    Existing comparisons vary benchmarks, corpus sizes, readers, judges, and question sets, leaving RAG paradigms’ accuracy-cost scaling unclear.

  • Method

    The study evaluates RAG paradigms across 28 strictly nested corpus tiers while fixing questions, relevant evidence, adversarial distractors, reader model, judging protocol, and cost measurement.

  • Results

    Around 10 million corpus tokens, BM25 overtakes File-System Agent and leads at every larger shared tier, reaching 50.5 accuracy at full scale versus 30.7.

  • Takeaways & Limitations

    Corpus growth favors global lexical ranking, making BM25 the stronger scalable default while agentic reasoning is best applied after ranked candidate discovery.

  • Takeaways & Limitations

    Graph-based methods do not reach full deployment scale, so their large-scale comparisons are limited by construction feasibility rather than extrapolated accuracy.

Abstract

from arXiv · show

Retrieval-augmented generation (RAG) spans lexical and dense retrieval, graph-based indexing, and agentic search, but these paradigms are usually evaluated on different benchmarks at one corpus size, leaving their accuracy-cost scaling unclear. To bridge this gap, we present a controlled study that varies corpus size along 28 strictly nested tiers spanning roughly 450-fold, while holding questions and a fixed bedrock of relevant and adversarial documents unchanged. Under one reader model and one judging protocol, we measure official accuracy, construction and query tokens, and latency. The results reveal a scale-dependent crossover rather than an unconditional winner. File-System Agent leads at the smallest shared tiers, but its sequential exploration costs 39 times more query tokens at the bedrock and becomes less effective as the search space grows. Around 10 million corpus tokens, BM25 overtakes it and leads at every larger shared tier, with a margin approaching 20 points at full scale. BM25 also anchors the low-cost end of the Pareto frontier without LLM-based construction. Dense retrieval remains efficient but less accurate, whereas graph-based RAG encounters construction walls before deployment scale and its scalable variants remain below BM25 at shared tiers. Overall, corpus growth increasingly favors global candidate ranking: lexical retrieval is the strongest scalable default, while agentic reasoning works best after ranked discovery rather than in place of it.

1 Introduction

This controlled study evaluates seven RAG pipelines across four paradigms on a 28-tier, 450-fold corpus ladder with fixed questions, relevant evidence, and distractors. It finds a scale-dependent crossover: File-System Agent leads early, while BM25 overtakes it around 10M corpus tokens.

  • Retrieval paradigms: File-System Agent incurs query-time cost through iterative, sequential file-system tool calls conditioned on earlier results.Its cost is concentrated at query time rather than corpus construction.
  • Evaluation: The study addresses prior comparison confounds by holding the reader model, judge, question set, and corpus difficulty controlled across corpus sizes.Existing comparisons typically evaluate at a single corpus size while varying these factors freely.
  • Study design: 28 strictly nested tiers grow from 1,144 to 511,959 documents while questions, relevant evidence, and adversarial distractors remain fixed.The ladder spans roughly 450-fold, from 1.7M to 601M corpus tokens.
  • Evaluation: Seven pipelines across four RAG paradigms are evaluated with token-level cost metering and matched controls.The evaluation measures answer accuracy, construction tokens, query tokens, and latency.
  • Scaling result: File-System Agent leads at early corpus scales, but BM25 overtakes it around 10M corpus tokens.The observed crossover occurs at roughly 10M corpus tokens, after which BM25 leads at every larger shared tier.

2 Related Work

Prior RAG work spans learned or frozen readers, lexical and neural retrieval, explicit graph structures, and agentic search. Existing benchmarks usually fix corpus size and under-measure offline cost, motivating this study’s nested scaling, unified accounting, cross-paradigm comparison, and dual judging protocols.

  • Reader and retrieval paradigms: RAG grounds generation in retrieved text through learned or frozen readers, with adaptive variants deciding when to retrieve or critique evidence.Retrieval spans lexical BM25, learned sparse, dense, and late-interaction models.
  • Graph-based retrieval: Graph-based RAG methods construct explicit structures before answering, including hierarchical entity communities, entity-relation indexes, query-linked facts, and lightweight entity co-occurrence graphs.LinearRAG uses lightweight NER and embeddings without generative build calls.
  • Agentic search: Agentic RAG interleaves reasoning with tool calls, supporting open-web search, adaptive multi-step retrieval, failure reflection, and learned search policies.These systems vary both their controller and retrieval substrate.
  • Benchmarking gap: Existing RAG benchmarks usually evaluate answer quality at a fixed corpus size and rarely meter offline cost.This study extends EnterpriseRAG-Bench with nested scaling, unified cost accounting, cross-paradigm comparison, and dual protocols with measured cross-judge agreement.

3 Method

The method evaluates four retrieval paradigms on a shared, strictly nested corpus ladder while retaining a fixed 1,144-document bedrock. A unified reader and metering harness measures official accuracy, build/query tokens, and latency across 28 tiers.

  • Corpus: 511,959 documents at the full evaluation tier total 600.8M tokens and span nine enterprise sources, including wiki pages, chats, tickets, e-mail, transcripts, CRM records, and code reviews.Two organizational overview pages serve as scaffolds alongside the 511,957-document corpus.
  • Scaling ladder: 28 tiers grow by 1.25 per rung while preserving a fixed 1,144-document bedrock and exact nesting verified through manifest checksums.Each tier adds a prefix from one seeded, source-and-noise-stratified ordering of the non-bedrock corpus.
  • Unified evaluation: Four paradigms access the same nested corpus ladder and use the same reader, enabling controlled comparison of official accuracy, build/query tokens, and latency.The ladder is denoted T0 ⊂ · · · ⊂ T27 in the evaluation methodology.
  • Evaluation questions: 500 questions comprise 470 source-grounded, 10 scaffold-supported high-level, and 20 not-found questions.The released gold set pools candidate evidence from BM25, dense retrieval, and file-agent search, so label construction is not tied to BM25 alone.

4 Experiment

Across a 28-tier, roughly 450-fold corpus ladder evaluated with a shared reader and judging protocol, BM25 overtakes File-System Agent around 10M corpus tokens and leads at larger scales. Agentic exploration is more costly, while graph-based systems face construction limits that prevent deployment-scale comparison.

  • Accuracy scaling: Around 10M corpus tokens, BM25 overtakes File-System Agent and leads at every larger shared tier, reaching 50.5 at full scale versus 30.7 and 29.9 for File-System Agent and DenseRAG.At the bedrock, File-System Agent and BM25 score 77.4 and 74.7, respectively, with overlapping 95% intervals.
  • Construction scaling: 2.9B generative tokens: HippoRAG 2’s fitted full-scale construction cost reaches this estimate, while its 724M-token build at 155M corpus tokens scores 41.0, about fifteen points below BM25.Graph-family construction, rather than extrapolated accuracy, limits large-scale evaluation.
  • Construction scaling: 102B tokens: LightRAG’s fitted full-scale construction estimate reaches this level, or four instance-years; even an optimistic b = 1.2 leaves the estimate near 42B tokens.LightRAG does not complete at 2,826 documents within the resource envelope.
  • Construction scaling: 659.4M embedding tokens: DenseRAG completes the full corpus, while LinearRAG reports zero generative construction tokens but still incurs local NER and embedding work.BM25 and File-System Agent require no index construction.
  • Query cost: 39 times more query tokens: File-System Agent grows from 226K at the bedrock to 343K at N = 21,614, while BM25 uses 5.8K tokens per question.Its median LLM calls rise from 5 to 8 by N = 42,587, and budget exhaustion reaches 15% at N = 131,876.
  • Robustness: 96.2%: An independent official judge agrees on pooled alignment verdicts, while binary re-scoring preserves every family ranking across nine shared scales.Official correctness is 2.60 points lower on average under binary re-scoring, with combined-score changes from −3.56 to +1.18.

5 Separating Agency from Structure

The full-scale BM25–File-System gap reflects candidate discovery rather than weak evidence synthesis. Across matched controls, agency helps when layered on globally ranked retrieval, while native agentic exploration is not a substitute for ranking.

  • Retrieval primitive control: 17.97 points: BM25 leads the File-System Agent at full corpus, reversing its 5.73-point bedrock deficit.The bedrock comparison is statistically tied, with a paired bootstrap 95% CI of [−11.57, 0.15], whereas the full-scale lead has CI [9.68, 26.14].
  • Retrieval primitive control: The File-System Agent scores 85.9 versus BM25’s 73.8 on queries finding at least one gold document, but its any-gold hit rate is 39.0% versus BM25’s 71.6%.This selection-conditioned contrast identifies candidate discovery as the mechanism behind the full-scale gap.
  • Retrieval primitive control: 32.52 points: Agent+BM25 beats the raw-file agent at full scale, while its any-gold hit rate reaches 78.0%.Agent+BM25 scores 69.4 and uses 101K tokens/question, roughly one ninth of raw-file exploration.
  • Harness control: Harness choice matters, and the study’s harness achieves the highest score among the three file agents in the matched resweep.This supports using Agent+BM25 against the strongest observed raw-file implementation when isolating the retrieval swap.
  • Agency versus substrate: 22.2–29.9 points: agentic access changes native LightRAG scores, compared with −0.6–14.5 for HippoRAG2 and −6.7–0.4 for MS-GraphRAG.The matched comparison shows that the same index can produce different outcomes under an agent and its native one-shot ranker.

6 Discussion

BM25’s advantage persists under altered wording and matched retrieval depth because global lexical candidate discovery better rejects factually wrong semantic traps as corpora grow. The discussion therefore recommends BM25 as the enterprise default, with Agent+BM25 for aggregation-heavy questions and careful reporting of scale, cost, and index coverage.

  • Robustness controls: BM25 remains above dense and graph retrieval under altered wording and comparable retrieval depth, while direct DenseRAG top-10 retrieval recovers only 57 of 431 confirmed items.The audit also found 1.2 overlapping documents on average, plus 115 traps and 100 not-found lures.
  • Graph limitations: Graph retrieval falls short because construction introduces malformed extraction noise, prohibitive scale cost, semantically wrong neighborhoods, and lost relation semantics.LinearRAG’s performance near MS-GraphRAG and LightRAG at the bedrock suggests LLM extraction contributes to the shortfall.
  • Mechanism: Global candidate discovery drives the crossover: indexed BM25 and DenseRAG amortize ranking, whereas sequential tree exploration makes relevant branches harder to reach as corpora grow.Lexical matching also rejects factually wrong semantic traps more effectively than semantic neighborhoods.
  • Evaluation implications: Cross-paradigm evaluations should report nested-scale accuracy, construction and query cost, and index coverage because quality is conditional on index completion.Coverage-adjusted summaries distinguish unavailable tiers from observed answer failures.
  • Practical recommendation: BM25 is the appropriate enterprise default, while aggregation-heavy questions favor Agent+BM25 for lexical discovery followed by agentic calls on narrowed candidates.LLM-built graph indexes are difficult to justify at 10^5–10^6 documents unless construction is near-linear and relational questions dominate.

7 Conclusion · A Scope · B Corpus Ladder

Across a controlled 28-tier scaling study with fixed questions, evidence, and adversarial documents, raw-file agency leads at the smallest shared tiers before BM25 overtakes it around 10M corpus tokens. BM25’s lead widens to nearly 20 points at 601M tokens while remaining Pareto-optimal without LLM-based construction.

  • 7 Conclusion: 28 tiers evaluate four RAG paradigms on an enterprise corpus ladder while holding questions, relevant evidence, and adversarial distractors fixed.The study also unifies the reader model, judge, and cost metering, with matched controls separating substrate from agentic policy.
  • 7 Conclusion: Raw-file agency leads at the smallest measured shared tiers, but BM25 catches it around 10M corpus tokens.
  • 7 Conclusion: Nearly 20 points is BM25’s lead at 601M tokens, where it remains Pareto-optimal without LLM-based construction.
  • A Scope: The supplement adds experimental detail, result tables, and reproducibility notes while keeping the main paper self-contained.It anonymizes identifiers and omits local machine paths.
  • B Corpus Ladder: EnterpriseRAG-Bench is a public synthetic enterprise benchmark with slightly more than 500K documents and 500 questions.
  • B Corpus Ladder: The bedrock tier contains all question-relevant documents, hard negatives, and not-found lures before larger tiers append seeded, source- and noise-stratified corpus prefixes.
  • B Corpus Ladder: The 28 corpus tiers are strictly nested, and corpus tokens use a shared tokenizer.Systems using shared chunks use a 1,200-token chunker with 100-token overlap.

C Method Configuration … C.4 Official Judge Prompts

The study standardizes native pipelines under shared reader, embedding, chunk, and judging configurations, while explicitly controlling agentic retrieval variants. Official evaluation combines LLM-judged answer quality with document recall computed from retrieved and gold identifiers.

  • C Method Configuration: Native pipelines share the Qwen3.6-27B reader, Qwen3-Embedding-0.6B embeddings, and shared chunks where applicable, while graph pipelines retain native chunking.BM25, DenseRAG, and HippoRAG 2 use shared chunks; MS-GraphRAG and LightRAG map native evidence back to shared identifiers when recall is available.
  • C.1 Reader Prompt: Non-agentic pipelines use one reader prompt that restricts answers to the supplied context, requires explicit uncertainty, and matches the question’s language.The prompt also instructs the reader to avoid outside knowledge or invented facts and to answer concisely.
  • C.2 File-System Agent Prompt and Tools: The File-System Agent uses Qwen3.6-27B as its policy model and receives read-only corpus-tree access through list_dir, grep, and read_doc.Its instructions require document-grounded, concise, factual answers with cited relative file paths.
  • C.3 Agent+BM25 Prompt and Control Guarantee: Agent+BM25 preserves the agent harness and budget but replaces raw tree search with ranked BM25 retrieval, requiring the original question for its first search.That forced call returns exactly the native BM25 top-5; subsequent reformulations or document reads constitute the agentic intervention.
  • C.4 Official Judge Prompts: The official combined score includes two LLM-judged components and one non-LLM document-recall component.The holistic alignment judge receives the query, gold answer, and candidate answer, accepting stylistic differences while rejecting contradictions, wrong quantities, or missing core content.
  • C.4 Official Judge Prompts: Reported cell scores are mean combined scores, while document recall uses exact set overlap between retrieved and gold document identifiers for answerable questions.This separates answer-quality judgment from retrieval-level document coverage.

D Figure and Table Metrics … G Matched Controls

The paper distinguishes measured native-pipeline results from missing or projected values, documents token-accounting procedures, and uses matched controls to isolate retrieval substrate and agentic-policy effects. Expanded native-ladder tables and controlled evaluations clarify how scores, costs, and retrieval mechanisms are compared.

  • D Figure and Table Metrics: Native-ladder tables report scores only for tiers actually built and evaluated, with dashes marking missing native results rather than extrapolated failures.Accuracy curves therefore contain measured cells only; projected build-token scaling is not used as hidden accuracy estimation.
  • D Figure and Table Metrics: Figure 1’s roughly 10M-token marker denotes the rounded interval where measured BM25 and File-System Agent point-estimate orderings change, not a fitted threshold or significance boundary.Figure 3 provides the measured curves and confidence bands.
  • D Figure and Table Metrics: Figure 5 summarizes six fixed tiers on one 150-question sample using coverage-adjusted scores and mean construction-plus-normalized-workload cost, with embedding tokens weighted by 0.6/27.Unsupported graph tiers receive zero only in this summary.
  • E Token Metering: The metering layer records prompt, completion, and total tokens per LLM call, assigns construction versus query phases, and reports embedding-token accounting separately from generative calls.Usage fields, cache metadata, indexing logs, or tokenizer inputs supply family-specific measurements.
  • F Full Native-Ladder Scores: Tables 11 and 12 expand the main result matrix across smaller and larger native-ladder tiers, with dashes indicating tiers not built or not evaluated for that native pipeline.These tables provide the full native-ladder score coverage beyond the subset shown in the main paper.
  • G Matched Controls: The retrieval-primitive control replaces file-tree exploration with BM25 while fixing the agent model, prompt, tools, and 80-call budget to isolate global candidate discovery from the policy loop.The first search uses the original question, and matched-pair audits verify the returned top-5 order equals native BM25.
  • G Matched Controls: Graph-substrate controls expose typed, read-only tools for entity, fact, relation, neighborhood, Personalized PageRank, and chunk retrieval while preventing agents from reading raw files.Any gains over native one-shot graph rankers therefore arise from policy access to the stored index rather than extra corpus text.

H Robustness Checks · I Failure and Stopping Criteria

Robustness audits preserve the study’s broad method rankings across judging protocols, retrieval controls, and proposal-sensitivity checks. Failure criteria treat unusable graph tiers as unavailable and show that File-System Agent’s full-scale losses persist beyond budget exhaustion.

  • H Robustness Checks: 96.2% pooled judge-decision agreement supports stable broad rankings, despite close pairs moving by a few points.Per-cell agreement ranges from 94.4% to 98.0%.
  • H Robustness Checks: A binary correctness protocol preserves all broad family rankings across the nine shared native-pipeline scales.The official score uses correctness-gated completeness.
  • H Robustness Checks: BM25 remains above dense and graph retrieval under paraphrased questions and comparable top-10 retrieval budgets at the two smallest eligible tiers.The controls target lexical-overlap sensitivity.
  • H Robustness Checks: 90-question full-corpus DenseRAG top-10 retrieval confirms trap proposals are not exclusively reachable through the BM25-prefiltered dense pool.This is the proposal-sensitivity audit’s direct retrieval check.
  • I Failure and Stopping Criteria: A graph tier is completed only when its construction artifact is usable for all scheduled questions and its token ledger is available.Build failures, resource-envelope overruns, extraction or merge failures, and incomplete indexes make a tier unavailable rather than assigning inferred accuracy.
  • I Failure and Stopping Criteria: File-System Agent failures are counted at question level, with failed or retried attempts included in full-scale call and token totals.Budget exhaustion is recorded separately from answer correctness.
  • I Failure and Stopping Criteria: Full-scale File-System Agent accuracy also falls among within-budget questions, showing the loss is not only a truncation artifact.This separates answer-quality degradation from budget-exhaustion effects.

J Data Schemas … M Artifact Contents

The supplement specifies native prediction and judgment schemas, phase-separated token ledgers, bootstrap procedures, and a map from empirical claims to reproducibility artifacts. It also organizes scripts, aggregate results, figures, and README guidance for reproduction.

  • J Data Schemas: Native prediction files store one JSON object per question with identifiers, question and answer fields, retrieved evidence IDs, latency, and metadata.The listed fields are id, question, predicted_answer, retrieved_chunk_ids, retrieved_doc_ids, latency_sec, and metadata.
  • J Data Schemas: Official judgment files bind judgments to answers and retrieved evidence with a SHA256 hash, recording alignment, reasons, completeness, fact counts and results, document recall, and prediction_sha256.The judgment fields are id, aligned, reason, completeness_pct, n_facts, fact_results, doc_recall, and prediction_sha256.
  • J Data Schemas: Token ledgers are phase-separated and include baseline, dataset, source, build and QA token counts and calls, plus build_qa_total_tokens.The schema names build{prompt,completion,total,calls} and qa{prompt,completion,total,calls}.
  • K Bootstrap Intervals: Confidence intervals resample questions within each method–tier cell using 10,000 bootstrap resamples, while matched controls use paired resampling over shared question IDs.Intervals report the 2.5th and 97.5th percentiles; matched-control intervals cover paired score differences.
  • L Artifact-to-Claim Map: Lexical controls and the cross-scale summary are stored in results/judge_paraphrase_*, results/judge_topk10_*, and figures/teaser_crossscale_points.csv.These artifacts cover lexical controls and the cross-scale summary.
  • M Artifact Contents: The supplement organizes sanitized construction, pipeline, metering, judging, and figure scripts; aggregate results ledgers; figure inputs and PDFs; and README.md reproduction guidance.The directories are scripts/, results/, and figures/, with README.md documenting environment variables and reproduction order.
Loading 2607.26497v3…