# Learning to Give Checkable Answers with Prover-Verifier Games

arXiv: https://arxiv.org/abs/2108.12099 · HTML: https://mlsanity.com/paper/2108.12099/

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Spatial Transformer Networks](https://mlsanity.com/paper/1506.02025/) (2015)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [When Does Label Smoothing Help?](https://mlsanity.com/paper/1906.02629/) (2019)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Rationalizing Neural Predictions](https://mlsanity.com/paper/1606.04155/) (2016)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)
- [Spatial Broadcast Decoder: A Simple Architecture for Learning Disentangled Representations in VAEs](https://mlsanity.com/paper/1901.07017/) (2019)
- [Rethinking Cooperative Rationalization: Introspective Extraction and Complement Control](https://mlsanity.com/paper/1910.13294/) (2019)
- [Training verified learners with learned verifiers](https://mlsanity.com/paper/1805.10265/) (2018)
- [On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach](https://mlsanity.com/paper/1910.07512/) (2019)
- [A Game Theoretic Approach to Class-wise Selective Rationalization](https://mlsanity.com/paper/1910.12853/) (2019)
- [Deep Verifier Networks: Verification of Deep Discriminative Models with Deep Generative Models](https://mlsanity.com/paper/1911.07421/) (2019)
- [Reasoning on Knowledge Graphs with Debate Dynamics](https://mlsanity.com/paper/2001.00461/) (2020)

## Built on by (most cited first, 30 of 32)

- [Self-critiquing models for assisting human evaluators](https://mlsanity.com/paper/2206.05802/) (2022)
- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [Probabilistic Inference in Language Models via Twisted Sequential Monte Carlo](https://mlsanity.com/paper/2404.17546/) (2024)
- [Prover-Verifier Games improve legibility of LLM outputs](https://mlsanity.com/paper/2407.13692/) (2024)
- [ReMA: Learning to Meta-think for LLMs with Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2503.09501/) (2025)
- [Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification](https://mlsanity.com/paper/2502.01839/) (2025)
- [Debate Helps Supervise Unreliable Experts](https://mlsanity.com/paper/2311.08702/) (2023)
- [Neural Network Verification with Proof Production](https://mlsanity.com/paper/2206.00512/) (2022)
- [Avoiding Obfuscation with Prover-Estimator Debate](https://mlsanity.com/paper/2506.13609/) (2025)
- [ImProver: Agent-Based Automated Proof Optimization](https://mlsanity.com/paper/2410.04753/) (2024)
- [Interpretability Guarantees with Merlin-Arthur Classifiers](https://mlsanity.com/paper/2206.00759/) (2022)
- [PAC Verification of Statistical Algorithms](https://mlsanity.com/paper/2211.17096/) (2022)
- [Models That Prove Their Own Correctness](https://mlsanity.com/paper/2405.15722/) (2024)
- [Neural Interactive Proofs](https://mlsanity.com/paper/2412.08897/) (2024)
- [Retrospective Learning from Interactions](https://mlsanity.com/paper/2410.13852/) (2024)
- [Pseudo-Formalization for Automatic Proof Verification](https://mlsanity.com/paper/2605.20531/) (2026)
- [FindTheFlaws: Annotated Errors for Detecting Flawed Reasoning and Scalable Oversight Research](https://mlsanity.com/paper/2503.22989/) (2025)
- [Agentic Systems as Boosting Weak Reasoning Models](https://mlsanity.com/paper/2605.14163/) (2026)
- [Divide and Cooperate: Role-Decomposed Multi-Agent LLM Training with Cross-Agent Learning Signals](https://mlsanity.com/paper/2606.10684/) (2026)
- [How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofs](https://mlsanity.com/paper/2607.03561/) (2026)
- [Mitigating Legibility Tax with Decoupled Prover-Verifier Games](https://mlsanity.com/paper/2602.23248/) (2026)
- [Hardness of Deceptive Certificate Selection](https://mlsanity.com/paper/2306.04505/) (2023)
- [Neural Concept Verifier: Scaling Prover-Verifier Games via Concept Encodings](https://mlsanity.com/paper/2507.07532/) (2025)
- [Addressing Over-Refusal in LLMs with Competing Rewards](https://mlsanity.com/paper/2606.31748/) (2026)
- [Sharding Prevents LLM Oversight Failures and Adversarial Exploitation](https://mlsanity.com/paper/2608.06422/) (2026)
- [Human-LLM Deliberation as Interactive Proof: Conditions for Verifiability Without Transparency](https://mlsanity.com/paper/2609.24895/) (2026)
- [Contract monitoring: governing AI via separation of powers](https://mlsanity.com/paper/2609.32061/) (2026)
- [How the Audit Rule Shapes Faithful Factor Explanations in LLMs](https://mlsanity.com/paper/2610.01514/) (2026)
- [Can AI Oversight Be Zero Knowledge?](https://mlsanity.com/paper/2610.01995/) (2026)
- [How to Have a Sensitive Debate: An Instance-Optimal Protocol for AI Debate](https://mlsanity.com/paper/2610.02557/) (2026)

## 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.