Counting Shared Evidence Once in Multi-Hop Question Answering

Multi-hop question answering systems break a hard question ("Which university did the director of film X attend?") into a tree of simpler sub-questions, answer the leaves first, and pass those answers upward. An early mistake then corrupts every later step. The current fix keeps several candidate answers at each step and scores every combination, then aggregates the scores. This creates a quiet accounting error. Many of the combined reasoning chains rest on the same retrieved Wikipedia paragraph or the same intermediate answer, so adding up their scores counts one piece of evidence many times. Chains that pass through rival candidates for the same sub-question are mutually exclusive, so treating them as independent supporters is also wrong. We propose to treat the final answer's probability as what it actually is: the probability that at least one supporting chain holds, where chains share underlying random events. We compute that probability exactly with the knowledge-compilation tools that probabilistic logic programming built for this problem.

Probabilistic logic programming calls this the disjoint-sum problem. Its standard solution is to compile all proofs of a query into a binary decision diagram. That is a graph in which every root-to-true path is a mutually exclusive case, so probabilities can be summed safely in one linear pass. The opportunity is that multi-hop beams are small, structured, and full of overlap, which is exactly the regime where compilation is cheap and the double-counting error is largest. The same compiled graph also yields exact derivatives of the answer probability with respect to each leaf event. These derivatives show which upstream step the answer most depends on. We use them to decide where to spend extra retrieval, which turns error propagation from something we tolerate into something we can locate.

Core Claim

Answer aggregation in beam-based multi-hop QA should be exact inference over a small discrete model with three ingredients. The first is one categorical variable per sub-question node, whose values are that node's beam candidates. This makes the candidates mutually exclusive. The second is one binary reliability variable per retrieved passage, shared by every chain that cites it. The third is deterministic logic tying a final answer to the conjunction of the node choices and passage reliabilities that produce it. Compiling this model into a decision diagram gives the exact answer distribution. We claim this improves exact match and especially calibration over score-sum or score-product aggregation. We also predict where the gain comes from: it should grow with the measured passage overlap among a question's chains and vanish on questions whose chains share nothing. That stratified prediction is what makes the claim falsifiable rather than a generic accuracy bump.

The second claim follows from the first. The compiled diagram supports exact sensitivity of the answer probability to each leaf event, computed by swapping in a gradient semiring as in An Algebraic Prolog for Reasoning about Possible Worlds. Sensitivity-guided re-retrieval, which re-queries the leaf whose uncertainty most moves the final answer, should beat uniform or lowest-confidence re-retrieval at a matched retrieval budget.

Position Relative to Prior Work

The work that motivates this proposal is BeamAggR. It decomposes questions into trees, keeps top-$k$ answers per node, forms the Cartesian product of child candidates at composite nodes, and scores the resulting trajectories by probabilistic aggregation. It reports an average 8.5% improvement over ProbTree across HotpotQA, 2WikiMQA, MuSiQue and Bamboogle. According to the research file, its aggregation does not track which trajectories share retrieved documents. We keep its decomposition and beams unchanged and replace only the aggregation step. Flow-of-Options has a related motivation. It turns rigid reasoning trees into a DAG over options and propagates successes with a max-update rule. Max is idempotent, so it never double-counts, but it also discards the accumulated support from several partially reliable chains. We want that support.

The method comes from probabilistic logic programming. ProbLog and Kimmig et al. (2010) compile overlapping proofs of a query, such as overlapping paths in a biological network, into a decision diagram to get an exact union probability. Retrieval chains sharing passages are the same structure. Dice supplies the practical engine. It is a discrete probabilistic language with first-class categorical choices and observations, compiled to decision diagrams with reuse of shared sub-functions, and it reports Munin inference in 3500 ms against $2.2\times10^7$ ms for Ace. We write each question tree as a short Dice program. aProbLog supplies the semiring view that lets one compiled graph give both probabilities and gradients.

Two lines of work constrain the design. First, hierarchical classification shows that coherence can be had cheaply. Coherent Hierarchical Multi-Label Classification Networks enforces it with an idempotent max layer, and Hierarchical Image Classification using Entailment Cone Embeddings sums child probabilities into parents. We considered applying compilation to taxonomies instead. We rejected that because, under the usual independent per-label outputs, the probability that any descendant holds already has a closed form, and a decision diagram would add nothing. The disjoint-sum problem only bites when supporting chains share random variables, which is the multi-hop case. Second, the known limits of compilation are exponential worst-case diagram size and variable-ordering sensitivity. These argue against applying it to whole knowledge bases, and in favor of the per-question, beam-bounded models used here.

Research Program

The pipeline runs in four stages.

  1. Fixed upstream system. We run a BeamAggR-style decomposition, retrieval and reading pipeline with one retriever and one language model. We cache, for every question, the tree, the per-node candidate beams with reader confidences, and the passages each candidate was extracted from.
  2. Model construction. A translator turns each cached tree into a Dice program. Each node's choice is drawn from a categorical variable over its candidates, with weights given by tempered reader confidences. Each distinct passage receives one Bernoulli reliability flag. A composite node's candidate is supported only if its producing child choices and cited passages hold. We use Dice's bit-level encoding of categorical variables, as in Scaling integer arithmetic in probabilistic programs, to keep wide beams compact.
  3. Learning the event probabilities. The temperatures and the passage-reliability prior are learned on each dataset's training split by maximizing the exact log-probability of the gold answer. Gradients come from the compiled diagram. This step matters because raw model confidences are not probabilities. Without it, any calibration gain could be an artifact of mis-scaled inputs.
  4. Re-retrieval loop. With the aggregation fixed, we add a budgeted loop. At each round we compute the derivative of the top answer's probability, or of the margin between the top two answers, with respect to every leaf node's categorical weights and every passage flag. We then re-retrieve for the leaf with the largest effect, recompile, and stop when the budget is spent.

We also measure, per question, the number of trajectories, distinct passages, mean pairwise passage overlap among trajectories, compiled diagram size and compile time. This lets us report where exactness matters and what it costs.

Baselines

The naive reference point is a greedy chain with beam width one. Each sub-question's top answer is passed upward, with no aggregation at all. It shows how much any multi-candidate method recovers from cascading errors, and it anchors the re-retrieval experiment.

The strongest existing method is BeamAggR's probabilistic aggregation run on our cached beams. The research file reports relative numbers for it: an 8.5% average gain over ProbTree across the four datasets and 8.2% on Bamboogle. There is no reported result on Lacuna for BeamAggR's absolute exact-match or F1 scores in the file, so we will reproduce it ourselves rather than quote a figure. Fairness comes from caching. Every aggregation method sees identical trees, candidates, confidences and passages, so aggregation is the only difference. BeamAggR's scores also receive the same learned temperature, tuned on the same training split with the same search budget as ours. Beating it means a statistically significant exact-match gain on at least three of the four datasets, together with lower expected calibration error and Brier score. The gain must be concentrated in the high-overlap stratum.

A max-propagation baseline in the style of Flow-of-Options scores an answer by its single best chain. It represents the idempotent way of avoiding double-counting.

Two ablations isolate the key ingredient. The first, "independent chains," gives every trajectory its own private copies of the passage flags. This reduces our model to a noisy-or over chains and removes sharing while keeping exclusivity. The second, "no exclusivity," replaces each node's categorical variable with independent Bernoullis, which keeps sharing but lets rival candidates both be true. If the full model does not beat both ablations, the specific claim about shared and exclusive events fails.

We also include a Monte Carlo estimate of the same model, described below, and a learned trajectory verifier that rescores full chains with the same language model.

Why not just…?

Why not just keep max aggregation, which already avoids double-counting? Max avoids overcounting by ignoring all but one chain. Suppose an answer is reached by three moderately reliable chains through different passages. That answer should beat one reached by a single slightly stronger chain, and max cannot express this. The max baseline and the independent-chains ablation together measure how much accumulated support is worth. If max matches the full model, the overlap problem is not practically important for these benchmarks, and we will report that.

Why not just sample instead of compiling? This is the most serious alternative. On beams of width three to five over two to four hops, ten thousand samples of the same latent model would estimate answer probabilities to within about a hundredth, by the usual inverse-square-root sampling error. If sampling matches compilation on accuracy and calibration, then the contribution is the shared-and-exclusive event model, not exactness. We will say so plainly. Compilation still offers two things we will test. The first is exact gradients for learning temperatures and for sensitivity-guided re-retrieval, where noisy sampled gradients may pick the wrong leaf. The second is deterministic latency. We therefore run the sampling estimator at matched wall-clock time, for both answer selection and leaf selection.

Why not just use inclusion–exclusion over the beam? For tiny beams it gives the same number, and we use it as a correctness check. Its cost grows exponentially in the number of trajectories, while compiled diagrams merge shared sub-chains. We will plot both costs against beam width to find where inclusion–exclusion stops being viable. If that never happens at practical widths, we will recommend it as the simpler implementation.

Why not just train a verifier over full chains? A learned rescorer can implicitly discount redundant evidence, but it gives no guarantee and no per-leaf sensitivity. We include it at equal training data. We also test the combination of verifier scores fed in as event weights, since the two approaches are complementary rather than exclusive.

Proposed Experiments

Benchmarks and metrics. The main study uses HotpotQA in its distractor and full-wiki settings (HotpotQA), 2WikiMQA, MuSiQue and Bamboogle, as used by BeamAggR. For orientation only, HotpotQA reports a BiDAF distractor answer F1 of 58.28 against a human level of 91.40. We report exact match, F1, expected calibration error, Brier score, and selective accuracy at fixed coverage.

Decisive check 1: stratified gains. We sort questions into bins by measured passage overlap among their chains. The full model should tie the independent-chains ablation in the zero-overlap bin and pull ahead as overlap grows. A flat gain across bins would point to better temperature fitting rather than correct evidence counting.

Decisive check 2: controlled overlap. In a synthetic setting we take a set of HotpotQA trees and inject duplicated distractor passages that support a wrong answer through several chains. Score-summing aggregation should be pulled toward the wrong answer as duplicates increase, and exact aggregation should not.

Decisive check 3: re-retrieval at matched budget. With one, two or three extra retrieval calls per question, we compare sensitivity-guided leaf selection against random, lowest-confidence-leaf and deepest-leaf selection, plus a sampled-gradient version. We measure exact-match gain per call.

Cost. We report compile time and diagram size against beam width and hop count. The aim is to show compilation is negligible next to language-model calls at practical widths, and to find the width at which it is not.