Retrieval-augmented question answering has a known paradox. Retrieving more passages raises the chance that the answer is somewhere in the prompt, but each irrelevant passage also distracts the language model that reads them, so accuracy often falls. The best training-free fix in the literature is to score every retrieved passage with the reader model itself. For example, one can ask how likely the reader thinks the question is given the passage, and then keep only the passages it rates highly. Improving Zero-shot Reader by Reducing Distractions (DAS) did this and reports an average 64% Exact Match gain over naive readers, with 100 retrieved documents. The cost is that every candidate needs an expensive scoring pass through the reader. Cheap learned pruners avoid that cost, but nothing tells you when they have thrown away a passage the reader would have wanted.
Exact nearest-neighbor search faced the same tension between a cheap approximate method and an expensive exact one, and solved it with bounds. App2Exa first runs a fast approximate search to get a provisional k-th best distance. It then uses that distance as a cutoff that lets an exact tree search skip whole branches without losing exactness. We propose the same move for passage selection. A cheap first pass sets a query-specific bar. A calibrated upper bound, computed from cheap retrieval features, then predicts the most any remaining passage could score under the reader. The scan stops as soon as that bound falls below the bar. The result should match the passage set that exhaustive reader scoring would choose, with a stated error probability, while scoring only a fraction of the candidates.
Core Claim
The central claim is that reader-aware passage selection can be run as a branch-and-bound search with a statistical guarantee rather than a heuristic cutoff. Let $s(p)$ be the expensive reader-specific score of passage $p$, such as the reader's log-probability of the query given $p$. Let $c(p)$ be cheap features: bi-encoder cosine, rank, lexical overlap, and length. We fit an upper bound $U_\alpha(c(p))$ by quantile regression and then calibrate it on held-out queries with split conformal prediction, a method that adjusts the bound so that it holds a guaranteed fraction of the time. The calibrated bound satisfies
$$ \Pr\big[s(p) > U_\alpha(c(p))\big] \le \alpha , $$
where $\alpha$ is a user-chosen miss rate. The guarantee holds when calibration and test queries are exchangeable, meaning they come from the same distribution.
The procedure has three steps. First, exactly score a small seed set of $m$ top-ranked passages and set $\tau_k$ to the k-th best exact score. Second, visit the remaining passages in decreasing order of $U_\alpha$, exactly scoring each one and raising $\tau_k$ whenever a better passage appears. Third, stop at the first passage whose bound falls below the bar:
$$ U_\alpha(c(p)) < \tau_k . $$
Because the visiting order is sorted by the bound, every unvisited passage is pruned at once. By a union bound, the chance that any true top-k passage is lost is at most $k\alpha$ in expectation.
Two things are new here. The cutoff $\tau_k$ is dynamic and set per query, as in App2Exa, rather than a global threshold. The guarantee is stated relative to the reader's own judgment, so it directly controls how far the selected set can drift from what the distraction-aware reader would have chosen. The guarantee does not certify answer correctness, and we say so throughout.
Research Program
The work has three parts.
The first is the bound itself. We will study how tightly cheap features predict reader scores across readers and datasets. We expect an analogue of the "dimensionality ceiling" that metric trees hit in high dimensions. When cosine similarity and reader preference come apart, for example on multi-hop second-hop passages whose relevance depends on a bridge entity, the bound becomes loose and pruning power collapses. We will measure pruning rate as a function of the rank correlation between $c$ and $s$. This should identify where the method helps and where it cannot.
The second is the search. We will implement the seeded scan and its stopping rule for single-hop retrieval. We will then extend it to two-hop retrieval, where second-hop candidates are conditioned on a chosen first-hop passage. There, a failed first-hop branch can leave a barrier, in the spirit of BC-DFS in Hop-constrained s-t Simple Path Enumeration, which records how far a failed vertex is from the target so later searches reaching it with less budget are cut immediately. In our setting the barrier would raise the bar for passages that are close in embedding space to an already-failed bridge. This extension is secondary, and we will report it separately.
The third is shift. Conformal guarantees break when test queries differ from calibration queries. We will measure the realized miss rate when the bound is calibrated on one dataset and applied to another. We will also test whether a small amount of target-domain calibration data restores coverage.
Baselines
The naive reference point is a zero-shot reader given the top-k passages by bi-encoder cosine, with k swept. We tune k on the same development split used for every other method.
The strongest existing method on the question we ask is exhaustive DAS: the reader scores all 100 retrieved passages by query likelihood and keeps the top k. It defines the target set our method tries to reproduce, and it is the accuracy ceiling for reader-aware selection. Its reported result is an average 64% Exact Match increase over naive zero-shot readers across four open-domain benchmarks, and 231% with DPR on SQuAD at 100 documents (DAS). We will rerun it with our readers and retriever. Beating it means matching its Exact Match within noise, and recovering at least $1-k\alpha$ of its selected set, while using substantially fewer reader scoring passes. We target under 30% of passages scored on single-hop data.
The strongest cheap competitors are learned pre-generation pruners. One is Provence, a DeBERTa-v3 labeler that reranks and drops tokens, reporting 50–80% token reduction and a 2x generation speedup. The other is LDAR, a text-free policy over cosine scores that picks a band of passage ranks, reporting 25–63% of full-context tokens and nearly 4x faster than full context. We use released checkpoints where available and give them the same retriever output and the same reader. We compare them at matched wall-clock budgets including the pruner's own cost. Beating them means a better accuracy-per-second frontier or equal accuracy with a verified miss rate; they offer no miss-rate statement at all.
For attention-based selection, AttentionRAG reports 0.89 Exact Match on TriviaQA with a 70B reader against 0.87 uncompressed. We include it on TriviaQA at 8B scale and match its compression ratio.
Two ablations isolate the key ingredient. The first replaces the dynamic bar $\tau_k$ with a single global threshold on $U_\alpha$ calibrated for the same miss rate. The second removes conformal calibration and uses the raw quantile regressor. If the dynamic bar does not prune noticeably more than the global threshold at the same miss rate, the App2Exa transfer contributes nothing and the claim fails.
Why not just…?
Why not just rerank a fixed top-N with the reader and tune N? This is the most serious alternative, because our method reduces to it whenever the stopping point happens to be constant. LDAR's analysis shows fixed cutoffs suffer "retrieval missing" when gold passages sit slightly lower in the ranking (LDAR), which suggests per-query stopping should matter. We will settle it directly. We plot reader-score set recall against average passages scored for fixed-N reranking and for our scan. If the two curves coincide, we will report that the bound adds only a guarantee, not efficiency.
Why not just use Provence or LDAR, which are cheaper still? They may well match our end accuracy on single-hop data. Provence even improves accuracy on PopQA by filtering distractors. What they lack is any statement of how often they discard what the reader needs. They are also trained for a fixed reader distribution rather than calibrated to the reader in use. The experiment that decides this is reader swapping: we change the reader without retraining and compare how much each method's fidelity degrades. Recalibrating our bound costs only a few hundred scored queries.
Why not just pass everything to the reader and let it extract, as Ext2Gen argues? Aligning Extraction and Generation reports 0.557 against 0.473 for a default reader by training the generator to extract from noisy context jointly. That result contradicts the premise that pre-generation pruning is safe. Our framing addresses it in part, since pruning is judged by the reader's own scores rather than an external compressor. Still, the reader may need context that it rates low in isolation. We therefore include full-context reading and an Ext2Gen-style model where checkpoints allow. If exhaustive DAS selection itself loses to joint extraction, our method inherits that loss, and we will say so.
Proposed Experiments
The single-hop experiments use NaturalQuestions, TriviaQA, and SQuAD with 100 DPR-retrieved passages per question, following the DAS setting. The readers are Llama-3.1-8B-Instruct and one other open 7–8B model. The multi-hop experiments use HotpotQA and MuSiQue. MuSiQue's connected reasoning chains make it the hardest test of whether cheap features can bound second-hop relevance. For context, PropRAG reports 53.9 F1 on MuSiQue, and its fixed-width beam is a natural target for the barrier extension.
We report four metrics:
- Exact Match and F1;
- set recall against exhaustive reader scoring;
- realized miss rate against the nominal $k\alpha$;
- fraction of passages scored and end-to-end latency, including bound computation.
The decisive checks are three. First, the realized miss rate must stay at or below nominal on in-distribution data across $\alpha \in \{0.01, 0.05, 0.1\}$. Second, the dynamic bar must prune more than the global-threshold ablation at the same miss rate. Third, on MuSiQue, we expect the pruning rate to drop sharply. If it does not drop and Exact Match holds, the cheap features carry more multi-hop signal than we assume. If it drops to near-exhaustive scoring, the method is a single-hop tool, and the barrier extension is the only path to multi-hop gains.
References
- Improving Zero-shot Reader by Reducing Distractions from Irrelevant Documents in Open-Domain Question Answering
- App2Exa: Accelerating Exact kNN Search via Dynamic Cache-Guided Approximation
- Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice
- Provence: efficient and robust context pruning for retrieval-augmented generation
- Beyond RAG vs. Long-Context: Learning Distraction-Aware Retrieval for Efficient Knowledge Grounding
- AttentionRAG: Attention-Guided Context Pruning in Retrieval-Augmented Generation
- Aligning Extraction and Generation for Robust Retrieval-Augmented Generation
- PropRAG: Guiding Retrieval with Beam Search over Proposition Paths