mlsanityData to 7 Oct 2026

Learning to Give Checkable Answers with Prover-Verifier Games

arXiv 2108.12099 ↗First posted 27 Aug 2021cs.LG cs.AI cs.GTcited by 29

Not on the map. Why?

Abstract (arXiv)

Our ability to know when to trust the decisions made by machine learning systems has not kept up with the staggering improvements in their performance, limiting their applicability in high-stakes domains. We introduce Prover-Verifier Games (PVGs), a game-theoretic framework to encourage learning agents to solve decision problems in a verifiable manner. The PVG consists of two learners with competing objectives: a trusted verifier network tries to choose the correct answer, and a more powerful but untrusted prover network attempts to persuade the verifier of a particular answer, regardless of its correctness. The goal is for a reliable justification protocol to emerge from this game. We analyze variants of the framework, including simultaneous and sequential games, and narrow the space down to a subset of games which provably have the desired equilibria. We develop instantiations of the PVG for two algorithmic tasks, and show that in practice, the verifier learns a robust decision rule that is able to receive useful and reliable information from an untrusted prover. Importantly, the protocol still works even when the verifier is frozen and the prover's messages are directly optimized to convince the verifier.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 20 of its 40 references that are in the map. First posted on arXiv 27 Aug 2021.

Builds on

20 of 40 references.

References · 20

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  4. 2016Layer Normalizationcited by 5,579
  5. 2015Spatial Transformer Networkscited by 1,423
  6. 2016The Concrete Distribution: A Continuous Relaxation of Discrete Random Variablescited by 1,135
  7. 2019When Does Label Smoothing Help?cited by 985
  8. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  9. 2020Prevalence of Neural Collapse during the terminal phase of deep learning trainingcited by 713
  10. 2018AI safety via debatecited by 384
  11. 2018Certified Defenses against Adversarial Examplescited by 305
  12. 2016Rationalizing Neural Predictionscited by 281
8 more
  1. 2018Scaling provable adversarial defensescited by 141
  2. 2019Spatial Broadcast Decoder: A Simple Architecture for Learning Disentangled Representations in VAEscited by 116
  3. 2019Rethinking Cooperative Rationalization: Introspective Extraction and Complement Controlcited by 96
  4. 2018Training verified learners with learned verifierscited by 50
  5. 2019On Solving Minimax Optimization Locally: A Follow-the-Ridge Approachcited by 34
  6. 2019A Game Theoretic Approach to Class-wise Selective Rationalizationcited by 32
  7. 2019Deep Verifier Networks: Verification of Deep Discriminative Models with Deep Generative Modelscited by 25
  8. 2020Reasoning on Knowledge Graphs with Debate Dynamicscited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 2; 2024: 6; 2025: 6; 2026: 11.

29 papers.

Sort:

By area:

  1. 2022Self-critiquing models for assisting human evaluatorscited by 372
  2. 2025The Landscape of Agentic Reinforcement Learning for LLMs: A Surveycited by 195
  3. 2024Probabilistic Inference in Language Models via Twisted Sequential Monte Carlocited by 85
  4. 2024Prover-Verifier Games improve legibility of LLM outputscited by 79
  5. 2025ReMA: Learning to Meta-think for LLMs with Multi-Agent Reinforcement Learningcited by 78
  6. 2025Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verificationcited by 49
  7. 2023Debate Helps Supervise Unreliable Expertscited by 39
  8. 2022Neural Network Verification with Proof Productioncited by 22
  9. 2025Avoiding Obfuscation with Prover-Estimator Debatecited by 11
  10. 2024ImProver: Agent-Based Automated Proof Optimizationcited by 10
  11. 2022Interpretability Guarantees with Merlin-Arthur Classifierscited by 8
  12. 2022PAC Verification of Statistical Algorithmscited by 8
17 more
  1. 2024Models That Prove Their Own Correctnesscited by 6
  2. 2024Retrospective Learning from Interactionscited by 6
  3. 2024Neural Interactive Proofscited by 6
  4. 2025FindTheFlaws: Annotated Errors for Detecting Flawed Reasoning and Scalable Oversight Researchcited by 3
  5. 2026Pseudo-Formalization for Automatic Proof Verificationcited by 3
  6. 2026Agentic Systems as Boosting Weak Reasoning Modelscited by 2
  7. 2026Divide and Cooperate: Role-Decomposed Multi-Agent LLM Training with Cross-Agent Learning Signalscited by 2
  8. 2026Mitigating Legibility Tax with Decoupled Prover-Verifier Gamescited by 1
  9. 2026How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofscited by 1
  10. 2023Hardness of Deceptive Certificate Selectioncited by 0
  11. 2025Neural Concept Verifier: Scaling Prover-Verifier Games via Concept Encodingscited by 0
  12. 2026Addressing Over-Refusal in LLMs with Competing Rewardscited by 0
  13. 2026Sharding Prevents LLM Oversight Failures and Adversarial Exploitationcited by 0
  14. 2026Human-LLM Deliberation as Interactive Proof: Conditions for Verifiability Without Transparencycited by 0
  15. 2026Contract monitoring: governing AI via separation of powerscited by 0
  16. 2026How the Audit Rule Shapes Faithful Factor Explanations in LLMscited by 0
  17. 2026Can AI Oversight Be Zero Knowledge?cited by 0