Equilibrium-Checked Debate Protocols for High-Precision Verification

When several language models debate whether a proof or answer is correct, the result depends heavily on the rules of the debate. These rules decide who must produce evidence, when a debater may give in, how many rounds run, and what count of "supported" votes accepts a solution. Today those rules are chosen by trial and error, and the outcomes show it. The strongest debate verifier for competition mathematics accepts solutions with 92.5% precision but rejects more than a third of correct ones. Debaters routinely abandon correct positions under peer pressure. We propose to treat the debate rules as a small game that can be analyzed mathematically before any model is run. The game's moves are abstract actions such as "object with a concrete counterexample" or "concede without new evidence." The probability that each action is truthful is measured from real model behavior. We then use rational verification, a branch of formal methods that checks properties only over the stable outcomes that self-interested players would reach rather than over every conceivable behavior, to search for rules that keep false acceptances low in every stable outcome while keeping correct acceptances high.

The opportunity is that the two literatures fix each other's blind spots. Debate research has rich empirical evidence about how language-model debaters behave, and almost no way to reason about how a rule change will play out against a debater who adapts to it. Rational verification has exactly that reasoning machinery, but it has only been applied to synthetic games, collision-avoidance controllers, and robot coordination, never to dialogue between language agents. In two sentences: we fit a small stochastic game to measured debater behavior, use equilibrium-based model checking to pick debate rules that are safe against a strategic solution author, and then test whether those rules beat hand-tuned protocols on real benchmarks, especially when the author is actively trying to get wrong answers accepted.

Core Claim

The precision–recall trade-off in debate-based verification is largely a protocol-design problem. It can be analyzed with an equilibrium filter, which sits between two cruder analyses. Worst-case analysis assumes any agent may do anything, and it recommends rejecting nearly everything. This is the over-approximation problem that motivates rational verification in Wooldridge et al. and Abate et al.. Average-case analysis assumes every agent follows its measured habits, and it is blind to a solution author who adapts to the rules. We claim that rules chosen by checking properties across all equilibria of a calibrated debate game will dominate both hand-designed and dev-set-tuned protocols under adaptive attack, while matching them on ordinary benchmarks.

Concretely, let $\theta$ be a protocol: gate threshold, evidence obligations, concession rules, round cap, and per-action rewards. Let $\mathrm{NE}(G_\theta)$ be the set of Nash equilibria of the resulting game. Let $\mathrm{FA}(\sigma)$ and $R(\sigma)$ be the false-acceptance probability and the recall under strategy profile $\sigma$. The synthesis problem is

$$\max_{\theta} \; \min_{\sigma \in \mathrm{NE}(G_\theta)} R(\sigma) \quad \text{subject to} \quad \max_{\sigma \in \mathrm{NE}(G_\theta)} \mathrm{FA}(\sigma) \le \epsilon ,$$

where $\epsilon$ is a target false-acceptance rate. The constraint is a universal-equilibrium ("A-Nash") check. The objective asks for recall that survives even the worst stable outcome.

How This Differs From Existing Work

The closest bridging papers each supply one piece and stop short of this.

From Debate to Equilibrium (ECON) recasts multi-agent reasoning as an incomplete-information game. It uses reinforcement learning to tune decoding temperature and repetition penalty toward a Bayesian Nash equilibrium. Its equilibrium is a training target over sampling knobs. Ours is a verification object over the rules of argument, with checked guarantees on acceptance behavior.

A Diagnostic Study of Multi-Agent LLMs for Real-World Debates measures after the fact whether a finished debate sits at a Nash-stable state, and it scores process health with an LLM judge. Its finding that consensus and outcome proxies barely beat chance on subjective tasks constrains us: we never use stability as a quality signal. We use equilibria as a threat model.

Peacemaker or Troublemaker shows that sycophancy tracks abandonment of correct answers ($r = 0.902$) and that a mix of personas works best. It controls sycophancy only through static prompts. We reuse its abandonment rates as calibration data and model sycophancy as a payoff for agreement.

AEGIS-D is the method we most directly build on and compete with. It contributes the evidence-gated design: five roles, a scheduler that forces weak supporters to falsify or switch sides, and acceptance only when at least three agents affirm. Its rule was hand-chosen and has no analysis of how a motivated author could game it.

Voting or Consensus? shows that the aggregation rule should depend on the task. Consensus wins on knowledge tasks, while voting wins on multistep reasoning (54.8% vs 28.4% on MuSR murder mysteries). We treat that choice as one coordinate of $\theta$ rather than a fixed hyperparameter.

On the formal side, our machinery comes from three sources. The complexity analysis of equilibrium checking in On the complexity of rational verification tells us which questions to ask. The incentive-synthesis construction in Incentive Design for Rational Agents shows how to search over rewards that steer equilibria. The stochastic-game extensions surveyed in Probabilistic Model Checking for Strategic Equilibria-based Decision Making and Rational Verification for Probabilistic Systems are needed because whether a debater's evidence is real is a matter of chance, not logic.

Two negative constraints also shape the design. The 2EXPTIME worst case for general temporal goals rules out modeling debate at the level of tokens. The restriction of neural-symbolic tools to feed-forward ReLU networks (Verifying Strategic Abilities of Neural-Symbolic Multi-agent Systems) rules out verifying the language models themselves. Both push us toward a small, measured abstraction with a bounded horizon. Within such an abstraction, checking reduces to solving a finite-horizon stochastic game over a few thousand states.

Research Program

The first component is the debate abstraction. Each debater, at each round, picks one of roughly six abstract actions: support with a checkable derivation, support without one, object with a concrete counterexample or flagged step, object vaguely, concede, or hold. A seventh player, the solution author, can defend, patch, or rephrase. The protocol $\theta$ determines which actions are legal for which roles, how the scheduler reassigns weak supporters, the acceptance gate, the round cap (at most three, given the drift past two or three rounds reported by Kaesberg et al. and Yao et al.), and small per-action rewards. Ground truth enters through action reliability: a "concrete counterexample" is genuine with one probability when the solution is wrong and fabricated with another when it is right.

The second component is calibration. For each base model, we log real debates on held-out problems under several protocols. A deterministic parser maps each turn to an abstract action using structural cues (does the turn cite a specific step, give a numeric check, or contain a concession phrase), with an LLM tagger only as a fallback. We audit the tagger against a few hundred hand labels. From these logs we estimate the reliability probabilities and the "habit" policies of honest, sycophantic, and contrarian debaters. Concession rates are cross-checked against the negative-agreement-rate measurements of Yao et al.

The third component is the payoffs. Honest verifiers are rewarded for correct verdicts. Sycophantic debaters are rewarded for ending in the majority, with a weight fitted to their measured concession behavior. The author is rewarded for acceptance regardless of correctness. This adversarial author is the player the A-Nash check protects against. It is realistic whenever the author is a model trained to pass the verifier.

The fourth component is checking and synthesis. For each candidate $\theta$, we solve the stochastic game for its equilibria, using correlated-equilibrium relaxations where Nash enumeration is too slow, as in Huang et al.. We then compute worst-equilibrium false acceptance and recall. We search over $\theta$ using the outer loop of the incentive-design construction, restricted to a discrete grid of rewards. That grid restriction is a known limitation of that framework, and we accept it here.

The fifth component is deployment. The chosen $\theta$ is compiled back into a real debate: prompts, scheduler logic, and gate. It is then evaluated on benchmarks the calibration never saw.

Baselines

The naive reference point is a single LLM judge with the same base model and a careful verification prompt. On the AEGIS-D stress test, the AEGIS-D paper reports 55.1% precision for this setup, with 24.7 false positives per run. Any method that does not clearly beat it fails outright.

The strongest existing method is AEGIS-D itself (When Wrong Answers Look Right). It reports 92.5% precision, 63.8% recall, and 59.8% problem-level accuracy on its 195 hard-to-verify variants. It is the strongest competitor because it already uses evidence gating and forced falsification, the same ingredients our search space contains. Any gain we show must therefore come from choosing those ingredients better, not from having them. We will re-run AEGIS-D with its published roles and gate on the same base models. Our verified protocol will get the same token budget per variant, the same round cap, and the same five-agent count. Beating AEGIS-D means one of two outcomes. The first is equal or higher precision with recall at least 10 points above its 63.8%. The second is markedly lower false acceptance under the adaptive-author attack described below, at matched recall.

The second strong competitor is a dev-set-tuned protocol. We run the same $\theta$ search space, but select parameters by direct grid search on real debate outcomes from the calibration split, with the same number of evaluated configurations our synthesis uses. This baseline asks whether the formal machinery adds anything beyond search. For the sycophancy benchmarks, we also include the judge-centralized configuration of Yao et al., which cut disagreement collapse on CommonsenseQA from about 81% to 41%. For MuSR, we include the voting protocol of Kaesberg et al. (54.8% on murder mysteries). ECON is included on its own GSM8K and MATH settings, as a game-theoretic method that does not verify.

Two ablations isolate the key ingredient by keeping the calibrated abstraction and changing only the analysis. The first is average-case selection, where all players follow their measured habits as a plain Markov chain and nobody deviates. The second is worst-case selection, where the author and debaters may take any legal action. If the equilibrium filter matters, it should beat average-case under attack and beat worst-case on recall.

Why not just…?

Why not just grid-search the protocol on a development set? This is the real threat, and the proposal is built to confront it. Grid search optimizes against today's behavior of non-adversarial authors. It has no way to anticipate an author who adapts to whatever gate is chosen. The equilibrium analysis is designed to anticipate exactly that. If the dev-tuned protocol matches ours under the adaptive-author attack, then the formal component buys only cheaper search. We will report that outcome plainly and reframe the contribution as a fast surrogate for protocol search.

Why not just red-team protocols with an adversarial LLM author directly? Empirical red-teaming is how we evaluate, but it is a poor design tool. Each attack run costs full multi-round debates, and finding no exploit says little about exploits not tried. The calibrated game lets us enumerate every deviation within the abstraction for every candidate $\theta$, at negligible cost. The empirical attack then checks whether the abstraction missed anything. If red-team discoveries routinely fall outside the abstraction, its action vocabulary is too coarse, and we will measure how often that happens.

Why not just use majority voting or self-consistency? Kaesberg et al. show that voting is the better aggregator on multistep reasoning, so on MuSR it may well be competitive. Voting also has no evidence requirement. The AEGIS-D results show that undifferentiated agreement admits fluent-but-wrong solutions far more often than evidence-gated acceptance does. Voting is one point in our $\theta$ space. If synthesis selects it for reasoning tasks, that is a valid outcome, and it would mean the synthesis recovered the task-dependent split on its own.

Why not just reduce sycophancy with better persona prompts? Yao et al. found that prompt-level control trades unsteerable debates against collapse, with no setting dominating. Our approach keeps personas as measured player types and changes the rules around them. The direct test is disagreement collapse on CommonsenseQA and MMLU-Pro, holding personas fixed and varying only $\theta$.

Proposed Experiments

The main test uses the AEGIS-D stress test: 195 variants from 58 IMO/USAMO/Putnam-level problems, plus 69 invalid statements. Calibration and synthesis use problems disjoint from evaluation. We report precision, recall, problem-level accuracy, and false positives per run, then test transfer to Omni-MATH and OlymMATH. No reported result was found on Lacuna for AEGIS-D's numerical performance on those two transfer sets, so we will establish both baselines ourselves.

The decisive adversarial check fine-tunes or iteratively prompts an author model, using only the gate's accept/reject signal, to get the known-wrong variants accepted. We do this separately against AEGIS-D, the dev-tuned protocol, and our verified protocol, with equal attack budgets. The core claim lives or dies here: verified protocols should show the smallest rise in false acceptance as the attack proceeds.

We also run three secondary tests. On sycophancy, we measure disagreement collapse and negative agreement rates on CommonsenseQA and MMLU-Pro, following Yao et al.'s definitions. On multistep reasoning, we run MuSR's three domains. Here the human ceiling (94.1% murder mystery, 95.0% object placement) and GPT-4 chain-of-thought (80.4%, 60.9%) from MuSR frame the scale.

The abstraction-fidelity check asks whether the game's predictions match reality. Across at least twenty protocol variants, we compute the rank correlation between predicted and observed precision and recall. A Spearman correlation below roughly 0.5 would mean the abstraction is not trustworthy enough for its guarantees to mean anything, and we would report the formal results as heuristic only.

Finally, the ablation contrast compares average-case, worst-case, and equilibrium selection on both clean and attacked evaluations. The equilibrium filter should land closer to worst-case under attack and closer to average-case on recall. If it does not separate from both, the central mechanism has no effect.