When a retrieval-augmented language model answers a question, meaning a model that first fetches passages from a document collection and then writes an answer from them, the answer depends heavily on which passages ended up in its prompt. On multi-hop questions, where the answer requires chaining facts from two to four passages, this dependence is severe. GPT-4 reaches 0.89 accuracy on MultiHop-RAG when given the gold evidence but only 0.56 when given retrieved chunks. The usual responses either pick one "best" set of passages more cleverly or sample the answer several times from a single fixed prompt. We propose a third view. The right answer is a weighted vote over many possible evidence sets, with each set weighted by how plausible the retriever finds it. Computing that vote exactly would mean summing over exponentially many passage subsets, each scored by a language-model call. Exact inference here is intractable for the same structural reason it is in graphical models.
The obstacle that matters in practice is not the size of the sum. It is that almost every randomly drawn subset is useless: it lacks the bridge passage, so the reader can only say "not enough information." Classical inference calls this the rejection problem. Under hard constraints, most samples have zero weight and are discarded. SampleSearch addresses it by replacing rejection with a backtracking search that repairs a failed sample into a nearby valid one and corrects its weight. We bring that repair-and-reweight idea to retrieval. When a sampled evidence set is judged insufficient, the system searches for the missing passage instead of throwing the sample away. A Bayesian stopping rule, in the style of Optimal Bayesian Stopping, then decides when enough evidence sets have been read. The result is an answer distribution with an explicit "evidence was insufficient" mass, which gives a principled abstention signal for unanswerable questions.
Core Claim
Define the answer distribution for a question $q$ as a mixture over evidence subsets $S$ drawn from a candidate pool:
$$p(a \mid q) = \frac{\sum_{S} \pi(S \mid q)\, r(a \mid q, S)}{\sum_{S} \pi(S \mid q)\,\big(1 - r(\bot \mid q, S)\big)}, \qquad a \neq \bot .$$
The terms are as follows. $\pi(S \mid q)$ is a prior over subsets built from retriever and reranker scores. $r(a \mid q, S)$ is the reader model's probability of answer $a$ given only the passages in $S$. $\bot$ is the reader's "insufficient evidence" output. The denominator is the total prior mass of subsets the reader considers sufficient; when it is small, the system should abstain.
We make three claims. First, this mixture is better calibrated and more accurate than answering from any single context, because errors caused by distractor passages become less correlated when the context varies. Second, a repair proposal that fixes insufficient subsets by targeted search estimates the mixture with far fewer reader calls than plain subset sampling. Third, a stopping rule on the estimated answer posterior cuts reader calls further without lowering accuracy.
Each claim is falsifiable against a ground truth we can actually compute. On small candidate pools, the sum above can be enumerated exactly.
Relation to Prior Work
Two RAG systems motivate the problem by showing that evidence must be chosen jointly, but both commit to a single evidence chain. Evidence Tree Search trains a 7B policy and value model with Monte Carlo tree search, then runs beam search to select one sentence chain. HopRAG builds a passage graph from simulated questions, where each passage gets questions it answers and questions it raises, and an LLM walks the graph to return one pruned context. Neither assigns probabilities to alternative evidence sets, and neither can say how much of the plausible evidence space supports its answer. We reuse HopRAG's "outgoing question" device as the repair operator. We differ in averaging over many chains rather than optimizing one.
Optimal Bayesian Stopping supplies the stopping method. It tracks the leader, the runner-up and a pooled tail ($L=3$) to make an otherwise $O(K!)$ posterior computation take about 14 ms. However, it assumes unweighted, independent answer draws from one fixed prompt. Our samples are importance-weighted, so extending the rule to weighted counts is part of the work, not a free transfer.
SampleSearch supplies the repair idea. It was developed for discrete networks with known constraint tables. Our "constraint" is the reader's sufficiency judgment, which is noisy and costs a model call to evaluate. That is a regime the original never faced.
The graphical-model literature also constrains the design. Thin Junction Trees and the treewidth analyses in Compiling Bayesian Networks Using Variable Elimination suggest a tempting alternative: compile the passage graph into a bounded-treewidth model and run exact inference. We deliberately do not do this. The reader's factor over a subset is not decomposable into small cliques, because the model reads the whole subset at once. Multi-hop questions also involve only 2–4 hops (MuSiQue), so treewidth is not the binding constraint. The binding constraint is the cost of each factor evaluation and the near-zero density of sufficient subsets.
Research Program
The system has four components.
The first is the subset prior. A retriever and cross-encoder produce a candidate pool of $N$ passages. $\pi(S \mid q)$ samples subsets of size one to four, with inclusion probabilities taken from temperature-scaled reranker scores, and the temperature is fit on a development split.
The second is the reader. It is prompted, and lightly fine-tuned if needed, to output either an answer or $\bot$, together with a short outgoing question naming what is missing.
The third is the repair proposal. When a sample returns $\bot$, the outgoing question is used to retrieve within the pool. The best-matching passage is added, or swapped in, with probability proportional to its match score. The probability of every random choice along the repair path is recorded, so the proposal probability $g(S)$ of the final subset is known along that path. The importance weight is $\pi(S \mid q)/g(S)$, and estimates are self-normalized. The proposal probability is path-dependent: several repair paths can reach the same subset. We therefore measure the resulting bias directly against exact enumeration rather than asserting unbiasedness.
The fourth is stopping. We adapt the $L=3$ posterior of Huang et al. by replacing raw counts with effective counts, meaning weighted counts scaled by the effective sample size. We check empirically whether the stopping rule's error rate matches its nominal threshold.
The analysis has two parts. On HotpotQA's distractor setting, each question comes with exactly ten paragraphs (HotpotQA). All subsets of size at most three number 175, so the exact mixture costs 175 reader calls per question. This is affordable for a few hundred questions with an 8B reader and gives a true posterior to compare against. We report total variation distance between estimated and exact answer distributions as a function of reader calls, for each proposal. The second part characterizes when the mixture helps. We split questions by how much the exact posterior differs from the single-context answer, and test whether those are the questions with distractor-sensitive reasoning.
Baselines
The naive reference point is single-call RAG. The same reader receives the top-$k$ reranked passages in one prompt, with $k$ tuned on the development split. This is what most deployed systems do, and the method must beat it at a matched or explicitly reported cost. MultiHop-RAG reports 0.56 accuracy for GPT-4 in this setting (MultiHop-RAG). We rerun it with our reader for a like-for-like number.
The most direct competitor is fixed-context self-consistency with Bayesian stopping. The top-$k$ prompt is fixed, answers are sampled at temperature, and sampling stops with the $L=3$ rule of Huang et al.. This isolates our key ingredient: it varies the decoding but not the evidence. It receives the same per-question reader-call budget and the same threshold tuning. Beating it requires higher accuracy, or better selective accuracy at equal coverage, at equal mean calls per question. The file has no reported result for it on multi-hop RAG benchmarks; on CommonsenseQA it saves over 80% of sampling cost relative to standard adaptive self-consistency.
The strongest existing evidence-selection methods are HopRAG and Evidence Tree Search. HopRAG reports 42.20 exact match on MuSiQue against 40.50 for SiReRAG (HopRAG). For Evidence Tree Search, the file gives only a 22% relative gain over CFIC on LongBench and no absolute figure (Evidence Tree Search). We will reimplement HopRAG's graph construction over the same candidate pools with our reader, so that differences reflect the selection rule rather than the model. We will also report its published MuSiQue number separately. Beating HopRAG means exceeding its exact match at a comparable number of reader calls, or matching it while also providing calibrated abstention, which HopRAG does not offer.
Three ablations isolate the inference ingredients. The first is plain subset sampling without repair, the rejection-style estimator. The second is repair without reweighting, which treats repaired subsets as if drawn from the prior. The third is repair with reweighting but a fixed budget instead of the stopping rule. If plain sampling matches repair at equal calls, the rejection analogy is wrong for this problem.
Why not just…?
Why not just sample answers repeatedly from one good prompt? This is the real threat. If most multi-hop errors come from the reader's decoding rather than from which passages it sees, fixed-context self-consistency will match our method more cheaply. The MultiHop-RAG gap between gold evidence (0.89) and retrieved chunks (0.56) suggests context is the dominant error source. However, that gap could be closed by better retrieval alone, without averaging. The matched-budget comparison above settles this question directly. We will also report how correlated errors are across samples under each scheme, since lower correlation is the mechanism we claim.
Why not just put every candidate passage into one long prompt? It is one call, and long-context readers exist. Evidence Tree Search reports that uncurated long contexts on LongBench suffer from evidence being lost in the middle. MultiHop-RAG shows that more retrieved text does not rescue open models: Llama2-70B scored 0.32 and Mixtral-8x7B scored 0.36 even with gold evidence. We include all-passages-in-one-prompt as an additional baseline. If it wins on HotpotQA's small pools but loses on MultiHop-RAG's larger corpus, that defines where subset averaging is worth its cost.
Why not just pick the single best evidence chain, as Evidence Tree Search and HopRAG do? A single chain can be very good. If the posterior is usually sharply peaked, averaging adds calls without benefit. The exact-enumeration study measures how often the posterior is multimodal. If multimodality is rare, the honest conclusion is that our value lies in abstention and calibration rather than accuracy, and we will report it that way.
Why not just vote over random subsets without importance weights? Unweighted voting is simpler and may be nearly as good when repair rarely changes subsets much. The "repair without reweighting" ablation tests exactly this, measured by distance to the exact posterior and by downstream accuracy.
Proposed Experiments
The decisive check is on HotpotQA distractor. We compare total variation distance to the exactly enumerated posterior, together with answer F1, against mean reader calls for plain sampling, repaired sampling, and fixed-context self-consistency. The prediction is that repair reaches within 0.1 total variation of the exact posterior in a small fraction of the 175-call enumeration, because insufficient subsets dominate the prior mass and repair stops paying for them.
The second check is on MuSiQue-Ans and MuSiQue-Full, plus MultiHop-RAG across its inference, comparison, temporal and null query types. We report exact match or accuracy, mean calls, and selective accuracy versus coverage when abstaining on low sufficient mass. On null queries and MuSiQue-Full's unanswerable contrast questions, the prediction is that low sufficient mass flags unanswerability better than the reader's own verbal refusal.
The third check tests the stopping rule. We ask whether its realized error rate tracks its threshold once samples are weighted, and how much it saves relative to the fixed-budget ablation.
All methods share one reader model, one candidate pool per question, and one tuning split. The negative outcome is also informative. If fixed-context self-consistency matches us at equal calls on MuSiQue and MultiHop-RAG, the proposal reduces to a calibration method, and the paper will say so.
References
- MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queries
- Approximate Inference in Probabilistic Graphical Models with Determinism
- Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answers
- Enhancing Retrieval-Augmented Generation via Evidence Tree Search
- HopRAG: Multi-Hop Reasoning for Logic-Aware Retrieval-Augmented Generation
- Thin Junction Trees
- Compiling Bayesian Networks Using Variable Elimination
- ♫ MuSiQue: Multihop Questions via Single-hop Question Composition
- HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering