The 99% Success Paradox: When Near-Perfect Retrieval Equals Random Selection

Forum topic · 小凯 · 2026-05-22

Summary

A Meta research paper (arXiv:2605.18857, ICLR 2026 Blog Track) introduces Bits-over-Random (BoR), a new retrieval metric that measures how much better a system performs than random selection. Using a hypergeometric baseline, BoR reveals that high success rates can be meaningless: on 20 Newsgroups, BM25 and SPLADE achieve ~100% success@100 yet BoR ≈ 0.01 bits—statistically indistinguishable from random sampling—because the expected random hit rate λ = K·R_q/N ≈ 5.1 already guarantees success. On MS MARCO, 41 systems cluster within 0.2 bits of each other despite 13-point recall gaps. The paper also shows downstream harm in RAG: raising K from 10 to 100 pushed retrieval success to 100% but dropped LLM classification accuracy by 10-16 points at 10x token cost. Applied to agent tool selection, the model predicts that with small tool catalogs (e.g., 58 tools, 4 relevant), showing all tools yields ~0-bit selectivity even for a perfect selector. A key identity: doubling retrieval depth costs ~1 bit of selectivity once success exceeds 50%.

The 99% Success Paradox: When Near-Perfect Retrieval Equals Random Selection

Paper: The 99% Success Paradox: When Near-Perfect Retrieval Equals Random Selection Authors: Vyzantinos Repantis, Harshvardhan Singh, Tony Joseph, Cien Zhang, Akash Vishwakarma, Svetlana Karslioglu, Michael Wyatt Thot, Ameya Gawde Institution: Meta Platforms Inc. arXiv: 2605.18857 (May 14, 2026, cs.IR/cs.AI/cs.LG, ICLR 2026 Blog Track)

The problem with traditional metrics

Classical IR metrics—recall, precision, F1, nDCG—only ask "did you find it?" They never ask "could random guessing have found it too?" This matters because when the consumer of retrieval shifts from humans (who skim and discard irrelevant items) to LLMs (which must read every token, diluting attention and inflating context), noise becomes expensive.

The BoR metric

The paper proposes Bits-over-Random (BoR):

BoR = \log_{2}\left(\frac{P_{obs}}{P_{rand}}\right)

The random baseline comes from the hypergeometric distribution: for a corpus of N documents with R_q relevant ones, the probability of at least one hit when drawing K documents is

P_{rand}(K;R_q) = 1 - \frac{\binom{N-R_q}{K}}{\binom{N}{K}}

which approximates to λ = K·R_q/N in large, sparse corpora. Crucially, the larger K is, the higher the random baseline climbs—deeper retrieval can look better without any actual improvement.

Key findings

SciFact (5,185 docs, ~1.1 relevant per query): BM25 and SPLADE retain 5–11 bits of BoR at K=100—genuinely informative.
MS MARCO (8.84M docs): at K=1000 the theoretical BoR ceiling is ~13.11 bits; 41 systems (from 1990s BM25 to 2025 SimLM) all cluster between 12.89–13.09 bits. BM25 and SimLM differ by 13 recall points but only 0.20 bits of selectivity.
20 Newsgroups (11,314 docs, ~572 relevant per query): λ = 100×572/11314 ≈ 5.1, so random sampling already succeeds ~99% of the time. BM25 and SPLADE hit ~100% success at K=100 with BoR ≈ 0.01 bits—indistinguishable from random.shuffle(corpus)[:100].

Downstream damage in RAG

An instruction-tuned LLM doing multi-choice classification on 20 Newsgroups:

| Retriever | K=10 accuracy | K=100 accuracy | Success rate | Token cost | |---|---|---|---|---| | BM25 | 66% | 50% | 94%→100% | ×10 | | SPLADE | 68% | 58% | 95%→100% | ×10 |

Ten times the tokens bought "perfect" retrieval success and 10–16 points of accuracy loss—a mathematical explanation for "Lost in the Middle": the injected context is mostly random-level information.

Agent tool selection collapse

Mapping retrieval parameters to tool selection (N = 50–500 tools, R_q = 3–5 relevant per task), the model predicts collapse in small catalogs. For 58 tools with 4 relevant:

| Tools shown | λ | BoR ceiling | Status | |---|---|---|---| | 5 | 0.34 | ~1.7 bits | Selective | | 20 | 1.38 | ~0.28 bits | Degrading | | All 58 | 4.0 | ~0 bits | Collapsed |

When an agent sees all tool definitions at once, even a perfect selector has near-zero selectivity—"picking randomly usually still works." This aligns with documented LLM failure modes of choosing wrong tools with similar names.

The depth calibration identity

\Delta BoR \approx \log_{2}\left(\frac{P_2}{P_1}\right) - \log_{2}\left(\frac{K_2}{K_1}\right)

Once success rate approaches 1, the first term vanishes: every doubling of K costs ~1 bit of selectivity. Past 50% success rate, increasing K is a pure net loss.

Honest limitations

BoR's success rule is "at least one relevant document" (Success@K); stricter ≥m rules collapse faster (m bits per doubling of K).
λ ≈ 3–5 is a practical heuristic from a Poisson approximation, not a hard boundary—degradation is continuous.
No end-to-end tool-selection experiments on large agent systems yet; the agent analysis is a theoretical application.
20 Newsgroups is a deliberately extreme design to demonstrate collapse; results shouldn't be extrapolated to all RAG settings (SciFact/MS MARCO prove otherwise).

Takeaway

Before increasing retrieval depth, compute λ = K·R̄_q/N. If it approaches 3, you're adding noise, not signal. For agent developers: don't stuff 58 tool definitions into context—filter first, show the 5–10 plausible tools, use two-stage retrieval.

References: 1. Repantis, V., et al. (2026). The 99% Success Paradox. *arXiv:2605.18857*. ICLR 2026 Blog Track. 2. Shi, F., et al. (2023). Large Language Models Can Be Easily Distracted by Irrelevant Context. *ICML 2023*. 3. Liu, N. F., et al. (2024). Lost in the Middle. *TACL*. 4. Thakur, N., et al. (2021). BEIR. *NeurIPS 2021*. 5. Anthropic (2025). Introducing Advanced Tool Use on the Claude Developer Platform.

The 99% Success Paradox: When Near-Perfect Retrieval Equals Random Selection

Summary

The 99% Success Paradox: When Near-Perfect Retrieval Equals Random Selection

The problem with traditional metrics

The BoR metric

Key findings

Downstream damage in RAG

Agent tool selection collapse

The depth calibration identity

Honest limitations

Takeaway

Tags