mlsanityData to 14 Oct 2026

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

arXiv 2605.25133 ↗First posted 24 May 2026cs.AI cs.CLcited by 4

Not on the map. Why?

Abstract (arXiv)

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 textscAccept, textscChallenge, or textscReject. 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. ANC separates reliable from unreliable answers, yielding a ~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.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 29 of its 37 references that are in the map. First posted on arXiv 24 May 2026.

Builds on

29 of 37 references.

References · 29

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  2. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  3. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  4. 2017On Calibration of Modern Neural Networkscited by 4,960
  5. 2023Reflexion: Language Agents with Verbal Reinforcement Learningcited by 4,276
  6. 2023Let's Verify Step by Stepcited by 3,789
  7. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,442
  8. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  9. 2023GPQA: A Graduate-Level Google-Proof Q&A Benchmarkcited by 2,879
  10. 2022Language Models (Mostly) Know What They Knowcited by 1,856
  11. 2023Improving Factuality and Reasoning in Language Models through Multiagent Debatecited by 1,784
  12. 2023Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debatecited by 1,011
17 more
  1. 2023Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMscited by 974
  2. 2017Selective Classification for Deep Neural Networkscited by 852
  3. 2023Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedbackcited by 812
  4. 2023SelfCheckGPT: Zero-Resource Black-Box Hallucination Detection for Generative Large Language Modelscited by 810
  5. 2022Teaching Models to Express Their Uncertainty in Wordscited by 751
  6. 2025Humanity's Last Examcited by 491
  7. 2020How Can We Know When Language Models Know? On the Calibration of Language Models for Question Answeringcited by 445
  8. 2022Self-critiquing models for assisting human evaluatorscited by 380
  9. 2019SelectiveNet: A Deep Neural Network with an Integrated Reject Optioncited by 350
  10. 2023Chain-of-Verification Reduces Hallucination in Large Language Modelscited by 324
  11. 2022Large Language Models are Better Reasoners with Self-Verificationcited by 307
  12. 2024Debating with More Persuasive LLMs Leads to More Truthful Answerscited by 266
  13. 2020Selective Question Answering under Domain Shiftcited by 238
  14. 2023Debate Helps Supervise Unreliable Expertscited by 43
  15. 2022Two-Turn Debate Doesn't Help Humans Answer Hard Reading Comprehension Questionscited by 17
  16. 2024Deep Neural Network Benchmarks for Selective Classificationcited by 12
  17. 2024Neural Interactive Proofscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Maintaining Benchmarks Against Increasingly Capable Agents: Detection and Remediation of Unearned Passescited by 1
  2. 2026Uncertainty Quantification for LLM Agents: A Taxonomy, an Evaluation Protocol, and an Empirical Studycited by 0
  3. 2026Human-LLM Deliberation as Interactive Proof: Conditions for Verifiability Without Transparencycited by 0
  4. 2026L3M: A Verifiable Harness and Runtime for Self-Extending and Self-Improving Agentscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Scaling Generative Verifiers For Natural Language Mathematical Proof Verification And Selection
  2. 2026Automating Formal Verification with Reinforcement Learning and Recursive Inference
  3. 2024Prover-Verifier Games improve legibility of LLM outputs
  4. 2025Leanabell-Prover-V2: Verifier-integrated Reasoning for Formal Theorem Proving via Reinforcement Learning
  5. 2025Trust but Verify! A Survey on Verification Design for Test-time Scaling
  6. 2025Reinforcing General Reasoning without Verifiers
  7. 2026Viva La Vida: Verification and Accumulation Failures in Multi-Agent Proof Search
  8. 2026Verify to Amplify: Improving Reasoning via Learned Chain-of-Thought Verification