Abstraction-Refinement Games for Deciding When and Where LLM Debates Should Continue

When several language models debate a math problem, the system eventually has to decide two things: whether to trust the answer, and, if not, what to argue about next. Today both decisions are made crudely. Debates run for a fixed number of rounds, and their confidence is a single judge score or a vote. Running more rounds often makes things worse, because agents talk each other out of correct answers. Formal verification faced the same problem decades ago. When a system is too large to check exactly, verifiers group many detailed states into a few coarse ones and treat the result as a two-player game. One player makes the system's real choices. A second player resolves the vagueness created by the grouping. Solving this game twice, once with the second player hostile and once with it helpful, yields a lower and an upper bound on the true probability. The width of that interval tells the verifier exactly which coarse states to split next.

We propose to import this machinery into step-level debate. A reasoning chain is treated as a small game over claims. The proponent chooses deductions, a "concretizer" chooses how each loosely stated claim is spelled out precisely, and sampled verifier judgments supply the probabilities. The game returns an interval on the chance that the argument reaches a correct conclusion, not a point score. When the interval is too wide, the system expands only the claim that contributes most to the width into finer sub-claims and re-debates that claim alone. The claim we test is narrow. Separating "this step might be wrong" from "this step is stated too loosely to judge" gives a better signal for where to spend extra debate tokens and when to abstain than any single confidence number does.

Core Claim

Two existing threads meet here. On the formal side, Game-Based Probabilistic Predicate Abstraction in PRISM and A Framework for Verification of Software with Time and Probabilities show that assigning abstraction vagueness to its own player produces sound lower and upper reachability bounds. They also show that merging that vagueness with ordinary nondeterminism makes the bounds uselessly loose. Stochastic Games for Verification of Probabilistic Timed Automata and Parameter Synthesis for Probabilistic Timed Automata Using Stochastic Game Abstractions close the loop: the game's strategies point to the coarse states that create the gap, and only those are split. These papers supply our method.

On the debate side, Debate4MATH runs a proponent–opponent debate over every reasoning step with a judge who outputs a 0–100% score, and caps debate at two rounds. Epistemic Gain, Aleatoric Cost shows that longer debates hit an "aleatoric barrier": disagreement falls while each agent's internal reasoning gets noisier. These papers motivate the work. They establish that uniform extra debate is harmful and that scalar scores hide where the uncertainty comes from.

What is new is the decision rule. Refinement targets the claim with the largest gap between its adversarial and cooperative concretizations, rather than the claim with the lowest score. Acceptance and abstention are driven by whether the whole interval clears a threshold.

We are explicit about one limit. The bounds are sound only with respect to the estimated game, meaning the sampled verifier probabilities. They are not sound with respect to mathematical truth. Whether they cover true correctness is an empirical question, and we measure it rather than assume it.

The Game

A debate state is a claim graph. Nodes are abstract claims, which are reasoning steps written at some granularity. Edges are deductions. Three kinds of move operate on this graph.

Player 1, the proponent model, chooses which deduction to apply at each claim. This plays the role of inherent nondeterminism.

Player 2 resolves abstraction vagueness. For each abstract claim, it chooses among $K$ precise restatements sampled from a separate model. Examples include "the integer $n$ is even" versus "$n$ is a positive even integer less than 10".

A stochastic move assigns each concrete restatement a probability $q$ of surviving scrutiny. The estimate comes from repeated skeptic-versus-defender exchanges judged by a verifier model, as in Towards Detecting LLMs Hallucination via Markov Chain-based Multi-agent Debate Framework.

Writing $V^{-}(s)$ and $V^{+}(s)$ for the probability of reaching the "verified correct answer" node from claim $s$, the two values satisfy

$$V^{\pm}(s) = \max_{a \in A(s)} \; \operatorname{opt}^{\pm}_{c \in C(s,a)} \; q(c)\, V^{\pm}(\mathrm{next}(c)).$$

Here $A(s)$ is the proponent's available deductions, $C(s,a)$ is the set of sampled restatements, $\operatorname{opt}^{-}$ is the minimum, and $\operatorname{opt}^{+}$ is the maximum. The interval $[V^{-}(s_0), V^{+}(s_0)]$ at the root claim $s_0$ is the debate's verdict. Because the graph is a small directed acyclic graph of tens of nodes, the game can be solved exactly in milliseconds.

Refinement works as follows. If the width $V^{+}-V^{-}$ exceeds a tolerance $\epsilon$, we find the claim whose local gap, weighted by its reach probability, contributes most to the root gap. The proponent rewrites that claim as two or three finer sub-claims, and debate runs only on the new nodes. The loop stops in one of three ways: $V^{-}$ exceeds the acceptance threshold (accept), $V^{+}$ falls below it (reject or regenerate), or the token budget runs out (abstain).

Research Program

The work has three parts.

First, we build the solver and refinement loop on open models. The main setting uses the Qwen2.5-3B/Qwen3-4B heterogeneous pairing from Epistemic Gain, Aleatoric Cost, so that results are directly comparable.

Second, we analyze whether the two sources of uncertainty actually come apart in language. On a set of chains, we record whether a step's gap shrinks under refinement, or whether its lower and upper values instead both collapse toward zero. The first pattern indicates vagueness. The second indicates a genuine error. We then check both patterns against final-answer correctness.

Third, we connect this to the debate pathologies. Refinement adds tokens only at contested claims. We expect it to avoid the late-round answer flipping reported by Qiao et al. and the distraction effect of stubborn weaker partners documented in Examining Inter-Consistency of Large Language Models Collaboration. We test that expectation by tracking how often correct answers flip to incorrect ones as the budget grows.

Baselines

The naive reference point is single-agent chain-of-thought with self-consistency majority voting. It receives the same total token budget as our method, measured in generated plus consumed tokens per problem. This baseline shows whether any debate structure is worth its cost.

The second baseline is standard fixed-round debate: two to five rounds with the same pair of models. It reproduces the setting in which Qiao et al. report the weaker agent's MATH-family average accuracy rising from 54.8% to 66.5% by round 5 under their trained UMAD method. We also run their untrained debate curve to expose the aleatoric barrier.

The strongest competitor on the efficiency question is RUMAD. It learns which agents speak and who hears whom, and it reports 68% on MMLU against 49% for standard debate and 61% for a static sparse method, with over 80% fewer tokens, plus 89% zero-shot on GSM8K. We use its released recipe if available, train it on the same data, and compare on the accuracy-versus-tokens curve.

The strongest competitor on the where-to-debate question is Debate4MATH-style step scoring. Its judge assigns each step a scalar confidence, and its trained 8B model reaches 83.4% on GSM8K and 45.1% on MATH. For our comparison we use the same judge model as ours to produce scalar scores, and we spend extra debate on the lowest-scoring step.

The key ablation removes Player 2. Restatements are averaged rather than taken as min and max, so the game becomes a one-player decision process that yields a single value, and refinement targets low value instead of a large gap. A second ablation keeps the interval but chooses which claim to refine uniformly at random.

Every method gets the same models, problems, and token budgets, and an equal hyperparameter search of twenty configurations on a held-out MATH split. Beating a baseline means a higher area under the accuracy-versus-tokens curve on MATH500 and GSM8K, with bootstrap confidence intervals over problems. It also means higher selective accuracy at matched coverage. For hallucination detection, the reference is Sun et al.'s 72.00% on Factool and 76.00% on HaluEval dialogue.

Why not just…?

Why not just debate the lowest-confidence step longer? This is the real threat. It is cheaper, and it may capture most of the benefit. Our method only earns its complexity if gap-targeted refinement beats lowest-score refinement at equal tokens. The single-value ablation (Player 2 removed) is exactly that comparison. If the two tie, we will report that the separation adds nothing in natural language and that the useful ingredient is localized refinement alone.

Why not just stop when agents agree? Agreement-based stopping is implicit in RUMAD's thresholds and in Qiao et al.'s disagreement measure. Agreement measures consensus, not correctness. Sycophantic collapse, documented in Peacemaker or Troublemaker, produces confident agreement on wrong answers. Our selective-prediction experiment tests this directly. We compare abstaining when the interval straddles the threshold against abstaining when the agents disagree, and measure error among accepted answers on problems where both agents agreed but were wrong.

Why not just sample more and vote? Voting cannot locate errors. Voting or Consensus? reports that correlated mistakes outvote a correct minority. Still, voting at matched budget is a strong baseline on GSM8K. Where the problems are easy, we expect it to stay competitive and will say so. Our claimed advantage is on MATH500 problems that require five or more steps.

Why not just train a process reward model? A process reward model is a learned scorer of individual reasoning steps. It gives point scores that cannot distinguish a vague step from a wrong one. It is also orthogonal to our method: it can supply the survival probabilities $q$. We run the game both with an off-the-shelf learned step scorer as $q$ and with debate-estimated $q$ to separate these contributions.

Proposed Experiments

The decisive check has three parts, all on MATH500 and GSM8K at three token budgets.

The first is the accuracy-versus-tokens comparison against the step-scoring and single-value ablations described above.

The second is interval coverage. The fraction of problems whose true correctness (1 or 0) lies within $[V^{-},V^{+}]$, after thresholding, should exceed the fraction for an equally wide band centered on the scalar judge score. If our intervals cover no better than that band, the bounds are decorative.

The third is a stress test of the aleatoric barrier. At budgets equivalent to five or more debate rounds, refinement should keep the flip rate from correct to incorrect below that of uniform debate.

A secondary transfer test applies the same loop to claim verification on Factool and HaluEval. There, each claim's restatements are evidence-specific readings, and the comparison is against the Markov-chain debate figures above.

Success means that, at matched tokens, gap-targeted refinement wins against lowest-score refinement and the intervals show better coverage than equally wide bands around the scalar score. If neither holds, the formal-methods analogy fails for language reasoning, and that negative result is worth reporting.