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

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.

Introduction. Retrieval-augmented generation grounds the outputs of large language models in external corpora, mitigating hallucination (Lewis et al., 2021). Its methods have diverged into paradigms whose costs arise at different stages and in different forms. Lexical retrieval (Robertson and Zaragoza, 2009) and dense retrieval (Karpukhin et al., 2020) require little preparation: indexing takes at most an embedding pass over the corpus. Graph-based RAG, including MS-GraphRAG (Edge et al., 2025), LightRAG (Guo et al., 2025), and HippoRAG 2 (Gutiérrez et al., 2025a,b), invests heavily at indexing time: it runs an LLM over every chunk to extract entities and relations, so that the resulting structure can be exploited at query time; LinearRAG (Zhuang et al., 2025) builds the same kind of graph with a lightweight named-entity recognizer and embeddings instead. File-System Agent spends its cost at query time, using an LLM to search the corpus through iterative file-system tool calls (Yao et al., 2023). Each call is conditioned on earlier results, making the tool loop a sequential retrieval policy.

Discussion / Conclusion. The decisive factor is corpus-wide candidate discovery. BM25 and DenseRAG amortize global ranking in an index; lexical matching also rejects this corpus’ factually wrong semantic traps more effectively. File-System Agent instead explores a local tree sequentially, making relevant branches harder to reach as the corpus grows. Graph methods require corpus-wide extraction, where cost, noise, and information loss become bottlenecks. At full scale, Agent+BM25 isolates this mechanism: changing retrieval cuts calls from 36.12 to 5.79 and tokens from 895K to 101K per question, while document recall rises from 36.8 to 72.4 and score from 36.9 to 69.4. Iteration helps most after global ranking, not in place of it.