Does lexical search outperform agentic navigation as corpus size grows?

The paper argues that RAG paradigms have no unconditional winner; they cross over as the corpus grows. It varies corpus size across 28 strictly nested tiers spanning roughly 450-fold, holding the questions and a fixed bedrock of relevant and adversarial documents constant, under one reader model and one judging protocol. The 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 stays ahead 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 any LLM-based construction. Dense retrieval "remains efficient but less accurate," and graph-based RAG "encounters construction walls before deployment scale," with its scalable variants still below BM25 at shared tiers.

The mechanism the authors give is that "the decisive factor is corpus-wide candidate discovery." BM25 and dense retrieval amortize global ranking in an index, so every query sees the whole corpus at once. The File-System Agent instead explores a local tree one call at a time, each call conditioned on the last, which makes relevant branches harder to reach as the tree grows. Graph methods need corpus-wide LLM extraction, where cost, noise and information loss become the bottleneck. Their one direct test of the mechanism is Agent+BM25 at full scale: swapping in BM25 as the retrieval step cuts calls per question from 36.12 to 5.79 and tokens from 895K to 101K, while document recall rises from 36.8 to 72.4 and score from 36.9 to 69.4. Their summary is that "iteration helps most after global ranking, not in place of it." They also report that lexical matching rejects this corpus' factually wrong semantic traps more effectively.

This qualifies the case made in Can direct corpus search beat embedding-based retrieval?, where an agent working directly over raw text with shell commands wins on lexical precision. Both results credit lexical matching, but this paper locates the advantage in the index that lets lexical matching span the whole corpus, not in the agent's ability to author exact-match commands. It also puts a scale condition on When do graph databases outperform vector embeddings for retrieval?: that note already flags graph construction as expensive, and here the expense becomes a wall before deployment size. The lexical-trap result is consistent with Do vector embeddings actually measure task relevance?, though the excerpt does not break out the dense-retriever failures. It also bears on Can retrieval be extended into multi-step chains like reasoning?: extra retrieval steps pay off when each step draws on a strong first-stage ranking.

The excerpt is silent on several things that limit how far the claim travels. It does not name the corpus, the question types, the reader model, or the absolute accuracy of BM25, dense retrieval or the graph systems, and it does not define "official accuracy." The trap finding is tied to this corpus' adversarial documents, and the mechanism is isolated by a single Agent+BM25 contrast, not by varying the agent's design. Whether the roughly 10 million token crossover moves with a different reader model or a stronger agent is not stated. What the evidence does support is narrower and useful: when choosing a RAG paradigm, the corpus size should be part of the decision, and a lexical index is the baseline any agentic or graph pipeline has to beat at scale.