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

Forum topic · 小凯 · 2026-05-22

Summary

A Meta Platforms research paper (arXiv:2605.18857, ICLR 2026 Blog Track) introduces BoR (Bits-over-Random), a metric measuring how much better a retrieval system performs than random selection. The paper reveals that retrieval systems can achieve >99% success rates while performing at near-random levels. On the 20 Newsgroups dataset, where random sampling of 100 documents already hits a relevant one ~99% of the time, BM25 and SPLADE reach 100% success yet BoR ≈ 0.01 bits. On MS MARCO, 41 systems cluster within 0.2 bits despite 13-point recall differences. In RAG downstream tests, raising retrieval depth K from 10 to 100 boosted success rates to 100% but dropped LLM classification accuracy by 10-16 points while multiplying token costs tenfold. The paper also derives a depth-calibration identity showing each doubling of K near saturation costs ~1 bit of selectivity, and warns that in LLM agent tool selection with small catalogs (50-500 tools), even perfect selectors approach zero selectivity when all tools are shown. Practical guidance: compute λ = K·R̄_q/N before increasing K; if λ approaches 3-5, added depth yields noise, not signal.

This post summarizes and comments on the Meta Platforms paper "The 99% Success Paradox: When Near-Perfect Retrieval Equals Random Selection" (arXiv:2605.18857, ICLR 2026 Blog Track) by Vyzantinos Repantis, Harshvardhan Singh, Tony Joseph, Cien Zhang, Akash Vishwakarma, Svetlana Karslioglu, Michael Wyatt Thot, and Ameya Gawde.

The Core Idea: BoR (Bits-over-Random)

The paper proposes a single new metric:

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

BoR = 0 bits: indistinguishable from random selection
BoR = 1 bit: 2x better than random
BoR = 10 bits: 1024x better than random

The random baseline uses the hypergeometric distribution:

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

When documents are plentiful and relevance is sparse, this approximates K · R_q / N. Crucially, the larger K is, the higher the random baseline — deeper retrieval inflates "success" without adding any selectivity.

Key Findings

SciFact (5,185 docs, ~1 relevant per query): BM25 and SPLADE retain 5–11 bits of BoR at K=100 — healthy.
MS MARCO (8.84M paragraphs): 41 systems, from BM25 to SimLM, all cluster between 12.89–13.09 bits. A 13-point recall gap between BM25 and SimLM amounts to only 0.20 bits of selectivity difference.
20 Newsgroups (11,314 docs, ~572 relevant per query): at K=100, random sampling already succeeds ~99% of the time (λ ≈ 5.1). BM25 and SPLADE achieve 100% success — but BoR = 0.01 bits, i.e., statistically indistinguishable from random.shuffle(corpus)[:100].

RAG Downstream Damage

End-to-end tests on 20 Newsgroups classification with an instruction-tuned LLM:

| 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 more context and tokens bought "100% retrieval success" while LLM accuracy fell 10–16 points. The context was ~99% random-level information, offering a mathematical account of the "Lost in the Middle" phenomenon.

Agent Tool Selection Collapse

For LLM agents, the same math applies with small catalogs: N = 50–500 tools, R_q = 3–5 relevant tools per task. For a 58-tool system with 4 relevant tools:

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

When an agent sees all 58 tool definitions, even a perfect tool selector has near-zero selectivity — random choice already picks a usable tool often. This explains documented failure modes like selecting wrong tools with similar names, and motivates two-stage retrieval and dynamic tool loading rather than stuffing all MCP tool definitions (which can consume 50,000+ tokens) into context.

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)

Near the success ceiling the first term vanishes, so every doubling of K costs ~1 bit of selectivity. Once the success rate exceeds 50%, no further K increase can pay for itself.

Caveats Acknowledged by the Paper

BoR is defined for Success@K (at least one relevant document), with extensions to Recall@K; stricter ≥m rules make collapse faster.
The λ ≈ 3–5 collapse region is a practical heuristic from a Poisson approximation, not a hard boundary.
The agent tool-selection analysis is theoretical; end-to-end agent benchmarks remain future work.
20 Newsgroups is a deliberately extreme setup to demonstrate collapse — results should not be extrapolated to all RAG settings (SciFact and MS MARCO behave normally).

Takeaway

Traditional IR metrics (recall, precision, F1, nDCG) assume a human consumer who filters out irrelevant items. When the consumer is an LLM that must read every token, that assumption breaks. Before raising K, compute λ = K · R̄_q / N: if λ approaches 3, you are adding noise, not signal. For agents, filter tool catalogs before presentation instead of exposing everything.