Saddle-Point Verification for Multi-Hop Question Answering

Answering a question like "where was the director of Inception born?" requires a chain of lookups: find the director first, then find the birthplace. Systems that chain retrieval and generation fail mostly at the hand-off between steps. A wrong intermediate entity, the "bridge," gets written into the context, and every later step builds on it. Current multi-agent systems guard each hand-off with a verifier agent that accepts or rejects the bridge. When the verifier rejects too much, the system rolls back and retries. But a single judge is not reliable even on easy sub-checks, and nothing tells the system when the evidence is truly ambiguous rather than just unlucky.

We propose treating each hop's verification as a small two-player game. A proposer chooses one candidate bridge entity. A refuter chooses one check to attack it with, such as "does the retrieved passage entail this?", "is it type-consistent with the question?", or "does substituting it back into the question retrieve supporting documents?". The system keeps the candidate at the game's pure-strategy saddle point: the one whose weakest check is still stronger than every rival's under that same check. Two results from game theory do the work. First, a pure saddle point does not always exist. When none exists, that is a precise, checkable sign of conflicting evidence, and it becomes the trigger for retrieving more. Second, a saddle point in a noisy game can be found with roughly $n+m$ noisy evaluations rather than all $n \times m$ candidate–check pairs. That keeps the cost of adversarial checking close to the cost of a single verifier.

Core Claim

Restricting the hop decision to a pure strategy, meaning one committed bridge entity, is usually treated as a weakness. Here it is the source of the method's two benefits. Write the payoff matrix as $A_{ij}$, the probability that candidate $i$ passes check $j$, estimated by sampling an LLM judge. A pure saddle point $(i^*, j^*)$ satisfies

$$ \max_i \min_j A_{ij} \;=\; \min_j \max_i A_{ij} \;=\; A_{i^* j^*}, $$

so $i^*$ is the candidate that is most robust to its own hardest check. When the two sides differ, every candidate is beaten by some check that another candidate survives. That is exactly the case of contradictory evidence, where committing to any bridge is unsafe.

We claim three things. Worst-case-over-checks selection reduces cascading bridge errors relative to single-verifier acceptance and relative to voting. The no-saddle signal predicts bridge errors better than score thresholds or entropy triggers. A bandit search for the saddle point recovers the accuracy of exhaustive checking at a fraction of the LLM calls.

Where this sits in prior work

Three lines of work motivate the proposal. MuSiQue builds multi-hop questions that cannot be shortcut and shows that single-hop models lose 30 F1 points relative to HotpotQA. The bridge step is therefore the bottleneck. IRCoT interleaves chain-of-thought sentences with retrieval and gains up to 15 F1, but it only moves forward, so an early wrong bridge is never revisited. Can Large Language Models Always Solve Easy Problems if They Can Solve Harder Ones? shows that models which solve hard problems still fail their easier sub-parts: Consistency Scores are about 92% for frontier models and 50–70% for 7B models. That is a direct warning against trusting one verification call per hop.

The closest systems are multi-agent and differ in mechanism. ReAgent adds a fact-verifier agent with local and global rollback. It reaches 0.795 F1 on HotpotQA with GPT-4o at about 29 calls per question, but rejection simply triggers an undo, and the authors do not analyze repeated contradictions. BELLE uses a two-level debate to choose which operators to run (decomposition, iterative retrieval). It reports a 7.6% gain on 4-hop MuSiQue, but it schedules operators and does not adjudicate individual bridges. GRAT searches over partial reasoning with Monte Carlo tree search guided by process rewards and reports 75.2% accuracy on 2WikiMultiHopQA with Llama3-70B. It scores paths with a learned reward, not with adversarial checks. Nash CoT is the only work that brings an equilibrium into LLM reasoning. It plays a two-player game between an expert persona and the base model over whole final answers, on math. We instead play a game at every hop, between candidates and refutation checks, and we use non-existence of the equilibrium as a control signal. The game-theoretic survey of LLM multi-agent systems names equilibrium coordination as an open problem but offers no implementation.

The method comes from Near-Optimal Pure Exploration in Matrix Games. Its MidSearch algorithm identifies a pure saddle point of a noisy zero-sum matrix with $O(n+m)$ samples, up to log factors, using median-based row and column elimination. That paper notes MidSearch fails when no pure saddle exists, and we turn that failure into the abstain-and-retrieve trigger. Two further results constrain the design. Iterated best response in auctions shows that deterministic best-response loops cycle when no pure equilibrium exists. This is the risk we attribute to undo-style rollback, and our loop is bounded by design rather than by best-response dynamics. Divide-and-Conquer prompting proves that splitting helps for independent sub-tasks but explicitly does not handle sequentially dependent ones. That is why we keep hops sequential and parallelize only the checks within a hop.

Research Program

We build a three-role pipeline. A decomposer emits the next single-hop sub-question, in the style of MuSiQue's single-hop compositions. A proposer retrieves passages with BM25 over the benchmark's corpus and extracts $n$ candidate bridge entities, with $n$ between 5 and 20 depending on retrieval width. A refuter supplies $m$ checks. Some come from a fixed library: passage entailment, answer-type consistency, temporal and relational consistency with earlier hops, and back-substitution retrieval. Others are generated for the specific question by the refuter.

Each payoff query asks an LLM judge whether candidate $i$ passes check $j$, sampled at nonzero temperature. Its pass rate is therefore a bounded, and so sub-Gaussian, noisy estimate of $A_{ij}$, which matches the MidSearch setting. MidSearch then runs within a per-hop call budget. If it certifies a saddle point, the bridge is committed and logged. If it detects the no-saddle case, or exhausts its budget without certifying one, the hop is marked ambiguous. The system then widens retrieval by adding candidates (new rows) and re-plays the game, at most twice. After that it commits the max–min candidate and flags the answer as low-confidence. Because widening only adds rows, the loop cannot cycle.

The analysis has three parts. We measure how often a pure saddle point exists, per hop type, using MuSiQue's reasoning-graph structure. We measure how well the no-saddle flag predicts that the committed bridge is wrong, against gold bridge annotations from MuSiQue's decompositions. We measure how many calls MidSearch actually uses compared with $n \times m$ as $n$ grows.

Baselines

The do-nothing reference is single-pass retrieval-augmented generation: retrieve the top-k passages for the full question and answer in one step. It shows how large the multi-hop gap is under our retriever and model.

The forward-only iterative baseline is IRCoT, run with the same LLM, the same BM25 index, and the same few-shot exemplars. It is the strongest cheap competitor, and it isolates whether hop-level adjudication adds anything beyond interleaving.

The strongest existing multi-agent method is ReAgent. It reports 0.795 F1 on HotpotQA with GPT-4o, against 0.661 for o1 and 0.696 for o3. No reported result was found on Lacuna for ReAgent on MuSiQue or 2WikiMultiHopQA as absolute numbers. We will reimplement it with its four execution agents and its supervisor, on GPT-4o and Llama3-70B, and confirm that our reimplementation comes close to the 0.795 HotpotQA figure before trusting other comparisons.

GRAT is the tree-search competitor. It reports 75.2% accuracy on 2WikiMultiHopQA with Llama3-70B. We run it at a matched LLM-call budget, without its self-training stage, so that inference-time methods are compared on equal footing.

BELLE is included on MuSiQue. No absolute reported number was found on Lacuna, only the 7.6% relative gain on 4-hop questions, so we will reimplement it.

All methods share data, retriever, judge model, and a tuning budget of equal size on a 500-question development split. The main comparison holds the per-question LLM call budget fixed at ReAgent's reported 29 calls. We also report full accuracy–cost curves.

Ablations isolate the key ingredients. Setting $m=1$ gives single-verifier argmax. Using the row mean instead of the row minimum gives average-score selection. Exhaustive $n \times m$ evaluation replaces bandit search. A confidence-threshold trigger replaces the no-saddle trigger.

Beating ReAgent means higher answer F1 on MuSiQue 4-hop and 2WikiMultiHopQA at no more than its call budget, with a lower rate of wrong committed bridges. Matching it at substantially fewer calls also counts as a positive result.

Why not just…?

Why not just sample several candidates per hop and take a majority vote? Hop-level self-consistency is cheap and strong. But voting rewards the answer that is most frequent, and on shortcut-prone multi-hop questions the frequent answer is often the shortcut, which MuSiQue was built to expose. Our matched-budget comparison will report, separately, the questions where the majority bridge is wrong. If voting matches us there too, worst-case checking adds nothing and we will say so.

Why not just score each candidate with one strong verifier, as ReAgent does? The hard-to-easy inconsistency result implies that a single verification call fails at a rate that compounds across hops. The $m=1$ ablation tests this directly. If $m=1$ performs as well as $m=6$ with a frontier judge, the contribution narrows to small models, where Consistency Scores of 50–70% suggest the gap should be largest.

Why not just evaluate every candidate–check pair and take the max–min? This is the real threat. With $n=5$ and $m=6$, the full grid costs 30 calls per hop. With repeated samples for noise, MidSearch may save little. We will report the crossover $n$ at which bandit search beats the grid at matched accuracy. If the crossover is beyond practical retrieval widths, the paper's claim reduces to max–min selection plus the no-saddle trigger, both of which the grid also provides.

Why not just trigger extra retrieval on low judge confidence or token entropy, as DRAGIN does? A threshold flags candidates that score uniformly low. It misses the case of conflicting checks, where each candidate fails a different test. The trigger ablation compares the precision and recall of the no-saddle flag against threshold and entropy flags for predicting wrong bridges.

Why not just use GRAT-style tree search? Tree search spreads its budget over whole reasoning paths and needs a reward model. Our method spends its budget only at bridge decisions. The matched-call comparison on 2WikiMultiHopQA settles which allocation is better.

Proposed Experiments

Evaluation uses MuSiQue-Ans (reported by hop count), HotpotQA in the distractor and full-wiki settings, 2WikiMultiHopQA, and Bamboogle as a small held-out test. Models are Llama3-8B, Llama3-70B, and GPT-4o. Metrics are answer exact match and F1, MuSiQue support F1, the bridge error rate against gold decompositions, LLM calls per question, and the loop or rollback rate.

The first decisive check is selective accuracy. On hops where a saddle point is certified, accuracy should be clearly higher than on hops flagged no-saddle. The no-saddle flag should also beat threshold triggers at predicting bridge errors. If neither holds, the central idea fails.

The second check is the ablation pair. Max–min selection should beat both single-verifier and mean-score selection on MuSiQue 3- and 4-hop questions, and the gap should be larger for the 8B model than for the 70B model.

The third check is cost. As $n$ grows from 5 to 20, MidSearch's call count should grow roughly linearly, while the grid's grows with the product $n \times m$, and accuracy should stay the same.

The fourth check is the head-to-head at the 29-call budget against reimplemented ReAgent, IRCoT, BELLE, and GRAT. We also count questions on which ReAgent rolls back more than three times and compare our answers on those questions, which tests whether bounded widening helps exactly where undo-style rollback cycles.