Checking Only the Facts the Answer Depends On: Proof-Guided Verification for Fast Multi-Hop Question Answering

Multi-hop questions such as "Where was the director of the film that won the 1998 festival prize born?" can be split into small sub-questions. Each sub-question can be answered by a cheap small language model that sees only the few passages retrieved for it. The weakness is that a single wrong sub-answer silently corrupts the final answer. Two responses are common today. Some systems check every step with a large model, which brings back the latency that splitting was meant to remove. Others trust a neural scorer, which is fooled by fluent but ungrounded text. This proposal takes a third route. We treat each small-model sub-answer as an uncertain fact inside a small probabilistic logic program. A probabilistic logic program is a set of if-then rules whose base facts carry probabilities, so the probability of the final answer is computed from the probabilities of those facts. The program shows exactly how much the final answer's probability would move if any single fact turned out to be false. The large model is then called only on the few facts that could change the answer, and it checks them in parallel rather than regenerating the reasoning step by step.

The idea addresses three problems at once. Isolating each sub-question with its own passages limits distraction from irrelevant context. The logic program makes a missing connection visible: when no chain of facts links the evidence to an answer, the answer gets little or no probability, where a neural model would tend to invent a link. And because the large model does short parallel checks instead of long sequential generation, it spends far less time decoding tokens one at a time. In two sentences: split the question into a logic program whose leaves are drafted by a small model, then use the program's own sensitivities to choose which leaves the large model verifies and when to stop. This should match large-model accuracy at a fraction of large-model decoding cost, and it should detect unanswerable questions better, because the symbolic layer can tell when no proof exists.

Core Claim

In a decomposed multi-hop question, the answer usually depends heavily on only a few leaf facts, such as the bridge entity in a two-hop chain. A probabilistic logic engine can identify these facts cheaply and exactly. Concretely, let $P(a)$ be the probability of candidate answer $a$ computed from the top-$k$ proofs over leaf facts $f$ with small-model probabilities $p_f$. Under the usual assumption that leaf facts are independent, $P(a)$ is multilinear in each $p_f$, meaning linear in any single $p_f$ when the others are held fixed. Verifying fact $f$ therefore changes $P(a)$ by exactly

$$\Delta_f(a) = \left|\frac{\partial P(a)}{\partial p_f}\right| \cdot \max(p_f,\, 1-p_f),$$

where the second factor is the largest possible move of $p_f$ toward 0 or 1. We rank leaves by $\Delta_f$ for the current top answer and send the highest-ranked ones to the large model in one batched check.

The same quantity gives a stopping rule. Let $a_1$ and $a_2$ be the top two candidate answers. We stop once $P(a_1)-P(a_2)$ exceeds the summed $\Delta_f$ of all still-unverified leaves, because at that point no remaining check can flip the answer. This is a bound only within the model's independence assumption, not a guarantee about the world. What is new is to use provenance gradients to allocate verification compute and to decide when to stop, rather than to train a network. Provenance gradients are the derivatives that neuro-symbolic systems already compute during training.

Research Program

The pipeline has four stages.

Compile. A compact model compiles the question into a structured query. We reuse the grammar of the Neuro-Symbolic Query Compiler, which parses questions into trees of atomic, dependent (sequential), and list (parallel) operations and executes them deterministically. We translate its tree into Datalog rules instead: a sequential "entity passing" step becomes a rule joining two relations, and a parallel union becomes a disjunction.

Draft leaves. Each leaf sub-question is answered by a small model using only the passages retrieved for that leaf. This localizes context in the way Superposition Prompting isolates documents into parallel branches. Their work stops at the prefill stage; ours also isolates the reasoning. The small model returns up to $m$ candidate answers with normalized probabilities, and each candidate becomes a probabilistic fact.

Speculate over bridge entities. For sequential hops we do not wait on a single bridge answer. Every bridge candidate spawns its own downstream leaves in parallel. This is the sub-question analogue of multi-candidate token trees in Multi-Candidate Speculative Decoding, which verifies several draft branches at once instead of committing to one.

Infer and verify. We run Scallop, a Datalog language whose provenance tracking with top-$k$ proofs yields differentiable answer probabilities. Scallop gives us $P(a)$ and the gradients $\partial P(a)/\partial p_f$. We then batch the top-ranked leaves to the large model, which scores each leaf's claim against that leaf's passages in a single prefill pass. The resulting probability replaces $p_f$, and we iterate until the stopping rule fires or a budget of $B$ checks is spent. Unanswerability is declared when total proof mass across answers falls below a threshold calibrated on development data.

Prior work that motivates the design. SpecReason drafts whole reasoning steps with a small model and has a large model score each one from 0 to 9, reporting 1.4x to 3.0x speedups on math reasoning. SpecSearch drafts tree-search thoughts and filters them with a process reward model, a neural scorer of intermediate steps. It also reports that thought generation takes over 91% of runtime. Both methods check every step in sequence with a neural scorer, and the research file notes that such scorers approve plausible but ungrounded steps. We check only the steps the structure marks as decisive, and we check them against their own retrieved evidence.

Prior work that supplies a method. VeriCoT verifies chain-of-thought steps with a logic solver and reaches 94.1% verification precision on ProofWriter. It makes several dependent language-model calls per step and uses true/false satisfiability. We borrow its insight that symbolic structure exposes ungrounded steps, but we replace exhaustive per-step formalization with probability-weighted, selective checks.

Prior work that constrains the design. Analytica argues that nonlinear AND/OR aggregation creates "tipping points", where one leaf error swings the root, and recommends linear averaging of child probabilities instead. We take this seriously but draw the opposite design conclusion. Tipping points are exactly the leaves with large $\partial P/\partial p_f$, so a gradient-guided verifier spends its budget on them. Averaging would blur the logical necessity that a multi-hop chain actually has. We test this directly against linear aggregation. Finally, Safe Abductive Learning in the Presence of Inaccurate Rules warns that wrong rules break symbolic learning. Here the rules come from a compiler that may be wrong, so we measure how often compile errors occur and how much they cost.

Baselines

Naive reference. The do-nothing point is naive retrieval-augmented generation (RAG), meaning the passages for the whole question are concatenated and fed to the large model, with no decomposition. It shows how much isolation and decomposition help under distractors.

Strongest existing method. The strongest accuracy competitor is QCompiler executed entirely with the large model. It is the closest structured method and reports 44.5 Exact Match on 2WikiMultihopQA, against 28.2 for naive RAG and 29.8 for Iter-Retgen (Neuro-Symbolic Query Compiler). Because the retriever and model sizes in our replication will differ, we rerun QCompiler with our exact retriever, top-K, and large model, and treat its large-model-everywhere configuration as the accuracy ceiling to approach. Beating it means matching its Exact Match within noise, established by a paired bootstrap over questions, while cutting large-model decoded tokens and wall-clock latency substantially.

Strongest speed competitor. This is a SpecReason-style adaptation. The same small model answers the same leaves, and the large model scores every leaf in sequence with the 0–9 utility prompt. Rejected leaves are regenerated by the large model. For MATH500, AIME, and GPQA, SpecReason's paper reports only the aggregate 1.4x–3.0x speedup and 0.4%–9.0% accuracy gain; no isolated per-dataset score is found on Lacuna, and there is no reported result found on Lacuna for SpecReason on multi-hop QA. We therefore run it ourselves.

Fairness conditions. All systems share the retriever, the small and large models, the hardware, and a matched hyperparameter tuning budget on the same development split. Thresholds are tuned for SpecReason-style acceptance and for our stopping and unanswerability rules.

Ablations isolating the key ingredient. The key ingredient is gradient-guided selection. The ablations keep the whole pipeline fixed and change only which leaves the large model checks, at equal budget $B$. The alternatives are random leaves, the leaves where the small model is least confident, all leaves, and none. A further ablation replaces provenance aggregation with Analytica's linear averaging.

Why not just…?

Why not just have the large model answer every sub-question? This is QCompiler with a big model, and it is our accuracy ceiling rather than a rival we expect to beat on accuracy. The research file notes that QCompiler's generation stages remain ordinary unaccelerated decoding. Our claim is only about the accuracy–latency trade-off. If selective verification cannot get within noise of this ceiling at under half its large-model decoding cost, the proposal fails.

Why not just verify the leaves where the small model is least confident? This is the most serious threat, because it needs no logic engine. It misses two cases the gradient catches. The first is a confidently wrong bridge entity, where all downstream mass rests on one fact. The second is a leaf that is uncertain but irrelevant, sitting on a branch that carries no proof mass. Whether these cases are common enough to matter is empirical. The equal-budget ablation settles it, reported separately for bridge-style questions and for comparison or parallel questions, where we expect little difference. If confidence-based selection ties everywhere, we will report that the symbolic layer earns its place only through unanswerability detection, not through verification selection.

Why not just filter context better, with Superposition Prompting or a reranker, and let the large model answer in one pass? Better filtering attacks distraction but leaves long large-model decoding untouched, and the research file notes that aggressive filtering drops the intermediate evidence that multi-hop questions need. The UDA benchmark shows how severe noise can be: GPT-4 on FinHybrid scores 45.9 with retrieval but 0.4 given the whole document. We include Superposition Prompting's path pruning as the retrieval front end in one arm of the experiments, which tells us whether our gains add to good filtering or duplicate it.

Why not just aggregate leaf probabilities linearly, as Analytica recommends? Linear averaging reduces variance, but it lets a chain score well even when a required hop fails. That is precisely the "forced logical connection" failure that Dhruva et al. document. The aggregation ablation compares the two on answerable and unanswerable questions separately.

Proposed Experiments

Benchmarks. The main benchmarks are MuSiQue, 2WikiMultihopQA, HotpotQA, and Bamboogle, the multi-hop sets used by QCompiler. MuSiQue was built so that disconnected shortcuts fail; single-hop models lose 30 F1 points relative to HotpotQA, and human performance is 78.0 answer F1 and 93.9 support F1 on MuSiQue-Ans. MuSiQue-Full adds unanswerable contrast questions, and FinHybrid from UDA supplies a stress test with heavy numerical noise.

Metrics. We report answer Exact Match and F1, support F1 (whether the verified leaves match gold supporting facts), and answerability F1 on MuSiQue-Full. For cost we report large-model calls, large-model decoded tokens, and end-to-end wall-clock latency on fixed hardware.

Decisive checks. The first is the latency–accuracy frontier. We sweep the budget $B$ and plot Exact Match against wall-clock time for our method, the SpecReason-style adaptation, and large-model QCompiler. The proposal succeeds if our curve dominates the SpecReason-style curve and reaches the QCompiler ceiling at a clearly smaller cost.

The second is the equal-budget selection ablation. Gradient-guided selection must beat confidence-based selection on bridge questions at small budgets, or the core claim is refuted.

The third is noise robustness. We inject increasing numbers of distractor passages into each leaf and into the naive baseline's single context. Accuracy for isolated-leaf methods should degrade far more slowly, and proof-mass unanswerability detection should beat both the large model's own abstention and SpecReason-style scoring on MuSiQue-Full.

The fourth is a check that the stopping rule behaves as intended. We measure how often the answer flips after the rule has fired, when all remaining leaves are verified anyway. Frequent flips indicate that the independence assumption is violated in practice.

Throughout, we report compile-error rates and accuracy conditioned on a correct compile, so that failures of the rules are separated from failures of verification.