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 ZhangarXiv 2026 · arXiv

TL;DR

As retrieval-augmented generation (RAG) systems scale up to handle massive enterprise data, more complex isn't always better. This paper demonstrates a scale-dependent "crossover" effect: while LLM-driven file agents perform best on tiny datasets, classic keyword-based BM25 retrieval overtakes them at around 10 million tokens and wins by up to 20 points at full scale (600 million tokens). Meanwhile, advanced GraphRAG methods hit severe "construction walls," making them computationally impractical for large production environments.

What Problem Does This Paper Address?

Retrieval-Augmented Generation (RAG) has evolved into several distinct paradigms: lexical retrieval (like BM25), dense retrieval (embedding-based), graph-based indexing (GraphRAG), and agentic search (LLMs iteratively exploring file trees).

However, these methods are typically evaluated on different benchmarks at a single, static corpus size. This leaves a massive blind spot for engineers and researchers: how do accuracy and computational costs scale as the underlying corpus grows? An architecture that shines on a small academic dataset might completely collapse or become prohibitively expensive when deployed over an enterprise knowledge base containing hundreds of thousands of documents.

Methods

To uncover the true scaling laws of RAG, the authors designed a controlled corpus-scaling study using 28 strictly nested tiers of data, growing exponentially (1.25x per tier) from 1,144 documents (1.7M tokens) up to 511,959 documents (600.8M tokens).

Evaluation Methodology

Crucially, they established a fixed "bedrock" tier containing all 500 evaluation questions, their corresponding gold-standard answer documents, and adversarial "traps" (factually incorrect or outdated documents on the same topics). As the tiers grew, only background noise documents were added. This isolated the impact of corpus size and noise on retrieval performance.

They evaluated seven native pipelines across four major paradigms using a single underlying reader model (Qwen3.6-27B) and a unified token-level cost-metering harness.

Datasets

The study utilized EnterpriseRAG-Bench, a public synthetic enterprise benchmark modeling a fictional company. The corpus spans nine realistic enterprise sources, including wiki pages, chat threads, support tickets, emails, meeting transcripts, and code reviews, totaling 600.8 million tokens.

Key Insights and Ideas

  • The Scale-Dependent Crossover: There is no unconditional winner across all data scales. At the smallest scale, a File-System Agent (which uses an LLM to browse directories sequentially) achieves the highest accuracy. However, as the search space expands, its performance plummets while its query costs skyrocket.
  • BM25 is the Scalable Default: Around the 10-million-token mark, BM25 overtakes the File-System Agent and maintains a dominant lead across all larger tiers.
Scaling Crossover Curves
  • The GraphRAG "Construction Wall": Graph-based RAG methods (like MS-GraphRAG and LightRAG) require running an LLM over every text chunk to extract entities and relationships during indexing. The authors found that LightRAG exhibits super-linear indexing growth ($b = 1.36$), projecting to an impossible 102 billion tokens or 4 instance-years of compute to index the full corpus.
  • Global Ranking First, Agency Second: The failure of the file agent at scale is a candidate-discovery failure, not an evidence-synthesis failure. When the authors tested a hybrid approach—Agent+BM25 (forcing the agent to use a global BM25 search tool rather than browsing raw files)—the accuracy collapse was completely reversed.

Key Results

  • Full-Scale Accuracy: At the maximum corpus size (601M tokens), BM25 achieved an official combined score of 50.5%, vastly outperforming the File-System Agent (30.7%) and DenseRAG (29.9%).
  • The Hybrid Winner: The Agent+BM25 hybrid achieved the highest overall full-scale performance at 69.4%, beating native BM25 by nearly 15 points while consuming only one-ninth of the query tokens required by the raw file agent.
  • Query Latency & Cost: For one-shot pipelines (BM25, DenseRAG), query costs and latencies remained nearly scale-invariant. In contrast, the File-System Agent's query cost grew from 226K tokens at bedrock to 343K tokens at larger tiers due to deeper sequential exploration.

Limitations and Future Work

The authors note that enterprise corpora heavily feature precise lexical anchors (product IDs, specific names, dates) and semantic "traps" (outdated versions of documents), which inherently favors BM25's exact-matching capabilities over dense embeddings.

Additionally, because graph-based RAG methods hit computational walls early on, their true accuracy at maximum scale could not be directly measured, only projected. Future work is needed to explore lightweight graph-construction techniques (like LinearRAG) that bypass expensive generative LLM indexing passes while preserving relational retrieval benefits.

Summary updated

Abstract

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.
BibTeX
@misc{wang2026bm,
  author = {Pengyu Wang and Benfeng Xu and Shaohan Wang and Mingxuan Du and Xin Zeng and Huarui Wu and Lei Zhang and Licheng Zhang},
  title = {{BM25 Wins at Scale: A Scaling Study of Retrieval-Augmented Generation Paradigms}},
  year = {2026},
  eprint = {2607.26497},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.26497},
}
Figure