Trust but Verify: Prover-Verifier Deliberation for Selective LLM Prediction

João Sedoc, Baotong Zhang, Dean Foster · 2026

Read Trust but Verify: Prover-Verifier Deliberation for Selective LLM Prediction by João Sedoc, Baotong Zhang, Dean Foster (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25133.txt.

Introduction

João Sedoc, Baotong Zhang, and Dean Foster introduce prover-verifier deliberation for selective language model prediction. The protocol produces an answer and a structured verdict. A prover backs an answer with checkable sub-claims as a verifier issues challenges, giving a verdict. The main experiment pairs Claude Sonnet as prover with Claude Haiku as verifier on GPQA Diamond. The high-confidence subset is questions accepted with no answer revision. That subset separates good answers from the rest, with a 30 point high-confidence precision gap.

Catalog record

CREATORJoão Sedoc, Baotong Zhang, Dean Foster
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69927
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2605.25133

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Trust but Verify: Prover-Verifier Deliberation for Selective LLM Prediction João Sedoc, Baotong Zhang, Dean Foster Abstract Reliably knowing when a language model is correct is almost as important as being correct. We introduce prover-verifier deliberation (PVD), an inference-time protocol grounded in interactive proof theory, as a mechanism for selective prediction: the protocol produces both an answer and a structured confidence verdict, allowing a system to report high-confidence answers while abstaining on uncertain cases. In each dialogue, a prover defends a candidate answer through checkable sub-claims while a verifier issues targeted challenges and returns Accept , Challenge , or Reject . Because frozen language models are imperfect provers and verifiers operating over a noisy channel, formal soundness and completeness guarantees do not transfer; instead, we characterize the protocol empirically through its coverage-precision behavior. Our main experiment uses Claude Sonnet 4.6 as prover and Claude Haiku 4.5 as verifier on GPQA Diamond. Questions accepted with no answer revision, which we call Accept + No Change (ANC), are reported as the high-confidence subset; we evaluate this subset by its precision and coverage. PVD achieves HC-Prec 84.2% at HC-Cov 77% with roughly three LLM calls per question. ANC separates reliable from unreliable answers, yielding a ∼ \sim 30pp HC-Prec gap over the non-ANC complement. Robustness experiments with GPT and Gemini pairings show that high HC-Prec can transfer across model families, while verifier strictness and domain competence largely determine the size of the selection gap. On Humanity’s Last Exam, weaker prover-verifier pairings can collapse or invert the ANC signal, illustrating a practical failure mode when the verifier operates outside its effective region. Comparisons with self-consistency, universal self-consistency, multi-agent debate, and Reflexion suggest that prover-verifier deliberation supplies a distinct argument-defensibility signal for selective prediction rather than merely reproducing sample agreement or debate consensus. 1 1 1 Code for reproduction and Claude Code skill available at https://github.com/jsedoc/prover-verifier-deliberation . 1 Introduction Reliably knowing when a language model is correct is often as important as being correct. A system that answers 90% of questions accurately but cannot distinguish its correct answers from its errors is far less useful in deployment than one that answers 60% of questions with near-certainty and abstains otherwise. This observation motivates selective prediction [ 7 ] : rather than producing a single accuracy figure, a well-calibrated system should trade coverage for precision, reporting answers only where it is confident. Despite its practical importance, selective prediction for LLMs remains underexplored relative to the large literature on improving raw accuracy through inference-time compute. Inference-time reasoning methods have advanced rapidly since chain-of-thought prompting [ 30 ] demonstrated that intermediate reasoning steps improve accuracy on complex tasks. Subsequent work spans self-consistency [ 29 ] , which aggregates multiple independent samples via majority vote; Reflexion [ 27 ] , which refines answers through verbal self-reflection; Universal Self-Consistency [ 2 ] , which uses an LLM aggregator to select the most coherent candidate; and multi-agent debate [ 6 ] , where multiple model instances argue toward consensus. These methods improve accuracy, but their confidence signals are weak: self-consistency’s agreement rate and debate’s consensus are at best indirect proxies for correctness, and none was designed to produce a principled abstain/report decision. A more structured approach comes from interactive proof theory [ 9 ] . In the interactive proof (IP) / zero-knowledge proof (ZKP) paradigm, a computationally powerful prover convinces a skeptical verifier of a claim’s truth through a structured challenge-response dialogue; the verifier’s final verdict carries formal soundness and completeness guarantees. Recent work has explored this paradigm in learning systems: 11 study Neural Interactive Proofs (NIP), proving that NIP = PSPACE , and training prover-verifier pairs via approximate Stackelberg optimization on verifiable tasks. 34 examine human-LLM interactive proof settings. These works focus on trained agents and formal verifiability. Our work takes a complementary direction: we ask whether the structure of interactive proof dialogue (without training, without verifiable ground truth, and over open-domain knowledge questions) can serve as a practical calibration mechanism for frozen LLMs. We introduce Prover-Verifier Deliberation (PVD), a challenge-guided selective-prediction protocol in which a prover defends a candidate answer and a verifier issues targeted challenges before returning an Accept, Challenge, or Reject verdict. The dialogue terminates when the verifier reaches a verdict or a fatigue limit is hit. Because language models are imperfect agents operating over a noisy channel rather than computationally bounded reasoners, hard soundness and completeness guarantees do not transfer; instead, we characterize the protocol empirically as a selective predictor. We introduce Accept + No Change (ANC) — questions where the prover’s answer is accepted without revision — as a coverage-precision operating point, and evaluate it against standard baselines across two benchmarks and multiple hosted model pairings. Our main findings are: (i) On GPQA Diamond [ 24 ] , ANC questions achieve HC-Prec 84–98% at HC-Cov 43–77%, with a +6.6–34.8pp gap over the non-ANC complement. (ii) The strongest ANC signal comes from a within-family capability-asymmetric pairing: GPT-5.4 prover with GPT-5.4-mini verifier yields HC-Prec 97.6% at HC-Cov 43% (+34.8pp over the complement). (iii) On Humanity’s Last Exam (HLE) [ 1 ] , weak prover-verifier pairings can collapse or invert the Accept/Reject accuracy gap, providing a natural diagnostic for when deliberation cannot be trusted. (iv) Compared to self-consistency ( k{=}8 ), multi-agent debate, Universal Self-Consistency, and Reflexion, PVD occupies a distinct and favorable position on the accuracy–calibration–efficiency Pareto frontier (Figure 1 ). Figure 1: Cost–precision tradeoff on GPQA Diamond for the clean RTTR runs. Each point is a method; the y -axis shows HC-Prec (accuracy on the reported high-confidence subset), the x -axis shows mean cents per question on a log scale, and bubble area encodes HC-Cov (fraction of questions reported). PVD variants occupy the high-precision region while exposing a controllable cost–coverage tradeoff: stricter or retry-based protocols spend more compute to report on more questions, while lower-cost variants abstain more aggressively. 2 Background & Related Work Our work connects five lines of research: selective prediction and abstention, calibration and uncertainty estimation for language models A.1.1 , inference-time reasoning and aggregation A.1.2 , verification and multi-agent deliberation A.1.3 , and interactive proofs and prover-verifier games. We position prover-verifier deliberation (PVD) as a selective-prediction protocol: the goal is not only to improve the final answer, but to produce a structured report/abstain signal from the interaction itself. In this sense, PVD draws conceptual structure from interactive proof systems while remaining an empirical inference-time method for frozen, general-purpose LLMs. 2.1 Interactive Proofs and Prover-Verifier Games Interactive proof systems formalize verification as a multi-round protocol between a powerful prover and a computationally bounded probabilistic verifier [ 9 ] . Classical results such as IP = PSPACE show that interaction and randomness can greatly expand what can be efficiently verified [ 26 ] . These results provide the conceptual template for PVD: a claim is not accepted merely because it is asserted, but because it survives a challenge-response process. The closest conceptual comparison is Neural Interactive Proofs [ 11 ] . That work studies neural prover-verifier protocols as learned interaction systems, develops a unifying theoretical framework, and evaluates trained protocols on tasks with verifiable structure. Human-LLM interactive proof settings provide another related perspective, focusing on the conditions under which a human verifier can adjudicate LLM-generated arguments

Read the complete text