Conformal Answer Sets for LLM Debates with a Strategic Participant

When several language models debate a question and then vote, the result is usually reported as one answer with no statement of how much to trust it. Worse, the vote assumes that every participant is honest. If one agent is compromised, whether it is a jailbroken model, a third-party tool with its own agenda, or a persona prompted to push a conclusion, it can sway the group. It can cast a tactical ballot, or it can argue persuasively for a wrong answer that sits close to the right one. We propose to wrap a debate in conformal prediction, a calibration method that turns any model's scores into a set of candidate answers guaranteed to contain the truth at a chosen rate (say 90%), assuming only that test questions resemble the calibration questions. We then make that guarantee hold even when one agent behaves strategically. The output is an answer set: small when the debate is reliable, larger when an attacker could have steered it. A large set is a natural signal to defer to a human.

The hard part is that "worst case over what the attacker could do" requires running the whole debate again for each candidate attack. Each rerun costs thousands of tokens. We treat the attacker's choices as a small, low-dimensional search space: which wrong answer to promote, which persuasion style, how persistently, and from which round. We fit a Gaussian process (a probabilistic regression model that predicts both a value and its own uncertainty from a handful of evaluations) over that space, and use it to find near-worst attacks per calibration question in a few rollouts. We then use a second conformal correction, fitted on a small audited subset, to cover the gap between what the cheap search found and what an expensive search finds. The result is a robust answer set whose coverage holds relative to an explicitly declared threat model, at a cost we can afford.

Core Claim

Our claim is that robust coverage under a strategic debater can be purchased for a small fraction of the cost of exhaustive attack search. With a fixed rollout budget, a surrogate-guided search plus a conformal correction for its own search error yields tighter answer sets than random search or closed-form worst-case bounds. We also make a second, falsifiable claim: on questions where agents are moderately uncertain, debate among heterogeneous models produces smaller robust answer sets than simply pooling independent answers. If that fails, we will report it. It would mean interaction costs more in attack surface than it buys in accuracy.

Where This Sits

Three strands motivate the problem. Voting or Consensus? Decision-Making in Multi-Agent Debate compares seven aggregation rules in LLM debates and finds that voting beats consensus on reasoning tasks (MuSR 54.8% vs 28.4%), but it assumes sincere ballots. Social choice theory says that assumption is fragile. How many candidates are needed to make elections hard to manipulate? builds on the Gibbard–Satterthwaite result that any non-dictatorial rule over three or more options is manipulable. Nonexistence of Voting Rules That Are Usually Hard to Manipulate and Complexity of and Algorithms for Borda Manipulation, where heuristics find optimal manipulations in over 99% of Borda elections, show that computational hardness is no shield. For LLMs specifically, Beyond Correctness: Distance-Based Social Dynamics of Multi-Agent Debate documents a "plausibility trap": agents resist absurd peers but are swayed by near-correct wrong ones. That is exactly the lever a strategic agent would pull. Together these papers tell us the threat is real and cheap to execute, so our threat model includes both ballot tactics and persuasion.

The method comes from Strategic Conformal Prediction. That paper shows that standard conformal coverage collapses under strategic feature changes (from a nominal 90% to 16% on spambase). It restores coverage by calibrating on the worst-case score over an admissible set of manipulations, and it notes that computing this supremum over complex move spaces is expensive. That work covers tabular classifiers whose features an individual can nudge. We move the idea to a setting where the "manipulation" is a sequence of messages and a ballot inside an interactive process. There the supremum has no closed form and each evaluation is a full debate. Debate as Optimization already puts an adaptive conformal filter inside a debate for event extraction, but it uses conformal thresholds to prune candidate spans and assumes honest agents. We instead calibrate the debate's final aggregated outcome against an adversary.

The surrogate side reuses standard Bayesian optimization, which chooses the next point to evaluate by trading predicted value against uncertainty, as in the upper confidence bound $\mu(x)+\beta\sigma(x)$. This mirrors how GP surrogates stand in for costly simulators elsewhere, for example BOAT for antibody design. The known weaknesses constrain our design. GPs scale cubically in data size and struggle on discrete, symbolic inputs. We therefore never put text into the kernel. The GP lives only on a few attack parameters and runs a separate small search per question. We also do not trust its uncertainty for the guarantee; the conformal correction does that work.

Finally, Efficient Multi-Agent Reasoning via Confidence-Guided Adaptive Debate (LASE) triggers debate only when a leader's token-level confidence is low, and reports 65.2% on GPQA-Diamond against 62.7% for majority voting. It is our strongest accuracy baseline. Its heuristic confidence carries no guarantee and fails exactly when the leader is confidently wrong, which is also when an attacker would push. Stop Overvaluing Multi-Agent Debate finds debate beats chain-of-thought in under 20% of scenarios with homogeneous agents and argues for heterogeneity. This paper directly threatens our second claim, so we adopt heterogeneous agents and keep self-consistency as a first-class baseline.

Research Program

The debate has five agents drawn from at least three model families. They produce independent first answers, then two rounds of exchange, then a ranked ballot over the multiple-choice options. The non-conformity score for option $y$ on question $x$ is $S(x,y)=1-b(x,y)$, where $b(x,y)$ is the Borda share of $y$ in the final ballots.

One agent may be replaced by an adversary with parameters $\theta$. These comprise the promoted wrong option; a style drawn from three: near-correct argument, confident assertion, and sincere-looking argument paired with tactical ranking that buries the truth; a persistence level; and an entry round. Let $D_\theta(x)$ denote the attacked debate. The ideal robust score is $S^*(x,y)=\max_\theta S(D_\theta(x),y)$. For the correct label $y$, the attacker wants to maximize this.

For each calibration question we run a Gaussian-process search with $B$ rollouts, using a mixed discrete–continuous kernel over $\theta$, and record the best score found, $\hat S_B(x)$. On a random audit subset of $m$ calibration questions we also run a much larger search with $B'\gg B$ rollouts to get $\hat S_{B'}(x)$, and record the shortfall $r(x)=\hat S_{B'}(x)-\hat S_B(x)$. The threshold used at test time is

$$\hat q=\mathrm{Quant}_{1-\alpha_1}\{\hat S_B(x_i)\}+\mathrm{Quant}_{1-\alpha_2}\{r(x_j)\},$$

with $\alpha_1+\alpha_2=\alpha$, the total miscoverage we allow. By a union bound, the calibration score adjusted for search shortfall exceeds the large-budget worst case with probability at least $1-\alpha$. The answer set is every option whose unattacked-or-attacked score falls below $\hat q$.

We will state the guarantee plainly: it covers attacks within the declared family, as well as the large-budget search can find them. We will measure its degradation against attacks outside the family rather than claim more. Because labels are fixed multiple-choice answers, we avoid the moving-label problem Strategic Conformal Prediction leaves open.

Baselines

The naive reference point is an unattacked-calibrated debate: standard split conformal prediction on final Borda shares, calibrated on clean debates, then evaluated under attack. This measures how bad the problem is. We expect coverage to fall well below 90%. No reported result on Lacuna quantifies conformal coverage of an LLM debate under a strategic agent, so this number is itself a first deliverable.

The strongest accuracy method is LASE (Efficient Multi-Agent Reasoning via Confidence-Guided Adaptive Debate), which reports 65.2% on GPQA-Diamond. We rerun it with the same model pool and token budget, with and without the attacker. We convert its confidence into sets by thresholding at the level that gives 90% coverage on clean calibration data. Beating it means reaching nominal coverage under attack, which we expect it to miss, while keeping its clean-data accuracy within one point.

The strongest robustness competitor is a closed-form worst-case bound. The attacker's own ballot shifts Borda shares by a known maximum, and persuasion is bounded by assuming the attacker can flip every honest agent within one option of the truth. This needs no search but should inflate sets. Beating it means equal robust coverage with smaller average set size.

The random-search ablation replaces the Gaussian process with uniform sampling of $\theta$ at the same budget $B$, mirroring the iterative random search regime of Strategic Conformal Prediction. This isolates what the surrogate adds. We count a win if, at matched rollouts, the correction term $r$ is smaller and sets are tighter.

The no-interaction baseline is self-consistency. The same five agents answer independently, and robust conformal prediction is applied with only the ballot bound, since without exchange there is no persuasion channel. All methods share the calibration questions, model pool and per-question token cap. Search hyperparameters get the same tuning budget on a held-out development split.

Why not just…?

Why not just drop the debate and pool independent answers? Without messages, only the ballot can be manipulated, and that has a cheap exact bound. Given the evidence in Stop Overvaluing Multi-Agent Debate, this is a real threat to the second claim. The no-interaction baseline settles it directly by comparing robust set sizes at equal coverage. We expect debate to win only on moderately uncertain questions, following the "ambiguity zone" finding of LASE. If it does not win there either, we will report that the attack surface of interaction outweighs its benefit, and that finding is useful for anyone deploying debate in adversarial settings.

Why not just use random search, as Strategic CP already does? Random search is unbiased and simple. The attack space mixes discrete choices with thresholds, and the plausibility-trap evidence suggests damage concentrates in a narrow region: near-correct targets pushed persistently. A surrogate should find that region in fewer rollouts. The matched-budget ablation measures this. If random search matches the Gaussian process, we will drop the surrogate and keep the two-level conformal correction, which is the part carrying the guarantee.

Why not just trust the Gaussian process's own uncertainty to bound the worst case? Its variance rests on a smoothness and Gaussian-noise assumption that debate outcomes, which jump when one agent flips, do not satisfy. We use the GP only to aim the search and let the audited residual quantile provide the guarantee. We will report how often the GP's upper confidence bound undercovers the audited maximum as a direct test.

Why not just harden the debate protocol, for example by filtering outlier agents? Filtering in the style of masked collaboration or winnowing (Separate the Wheat from the Chaff) targets erratic agents. A strategic agent arguing for a near-correct answer is not an outlier. Such filters are compatible with our wrapper, and we will include one as a protocol variant to test whether it shrinks robust sets.

Proposed Experiments

We use four multiple-choice benchmarks from the file. GPQA-Diamond and MMLU-Pro stand in for knowledge, MuSR for multi-step reasoning, and TruthfulQA-MC for adversarial distractors, which are natural near-correct targets. Each gets a split of roughly 300 calibration questions, a 50-question audit subset, and a held-out test set. The per-question search budget $B$ ranges from 4 to 16 rollouts, with $B'=64$ on the audit subset. Metrics are coverage under the strongest in-family attack found at test time, average set size and the fraction of singleton sets, accuracy of the top answer, and total tokens. All are reported separately for clean and attacked conditions and for questions binned by first-round agreement.

Four checks decide the proposal. First, clean-calibrated conformal debate must visibly undercover under attack; otherwise the problem is not worth solving. Second, the two-level robust method must reach 90% coverage under in-family attack across all four benchmarks while producing smaller sets than the closed-form bound. Third, at matched rollouts, the Gaussian-process search must beat random search on the audited shortfall; if not, we simplify. Fourth, we hold out one attack style from the family entirely, for example tactical ranking alone. Coverage should degrade gradually rather than collapse, mirroring the graceful degradation under misspecified alteration sets reported by Strategic Conformal Prediction. Throughout, the comparison against pooled independent answers on moderately uncertain questions determines whether robustly certified debate earns its cost.