# Prover-Verifier Games improve legibility of LLM outputs

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

## Key facts

- Cited by 85 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 64 references that are in the map.
- First posted on arXiv 18 Jul 2024.

## Builds on (most cited first, 30 of 48)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Universal and Transferable Adversarial Attacks on Aligned Language Models](https://mlsanity.com/paper/2307.15043/) (2023)
- [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2307.15217/) (2023)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [RobustBench: a standardized adversarial robustness benchmark](https://mlsanity.com/paper/2010.09670/) (2020)
- [Sleeper Agents: Training Deceptive LLMs that Persist Through Safety Training](https://mlsanity.com/paper/2401.05566/) (2024)
- [Weak-to-Strong Generalization: Eliciting Strong Capabilities With Weak Supervision](https://mlsanity.com/paper/2312.09390/) (2023)
- [Scalable agent alignment via reward modeling: a research direction](https://mlsanity.com/paper/1811.07871/) (2018)
- [On Evaluating Adversarial Robustness](https://mlsanity.com/paper/1902.06705/) (2019)
- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [Self-critiquing models for assisting human evaluators](https://mlsanity.com/paper/2206.05802/) (2022)
- [A Holistic Approach to Undesired Content Detection in the Real World](https://mlsanity.com/paper/2208.03274/) (2022)
- [Explainability for Large Language Models: A Survey](https://mlsanity.com/paper/2309.01029/) (2023)
- [Are aligned neural networks adversarially aligned?](https://mlsanity.com/paper/2306.15447/) (2023)
- [Recursively Summarizing Books with Human Feedback](https://mlsanity.com/paper/2109.10862/) (2021)
- [Faithful Chain-of-Thought Reasoning](https://mlsanity.com/paper/2301.13379/) (2023)
- [Debating with More Persuasive LLMs Leads to More Truthful Answers](https://mlsanity.com/paper/2402.06782/) (2024)
- [Measuring Progress on Scalable Oversight for Large Language Models](https://mlsanity.com/paper/2211.03540/) (2022)
- [Scalable and Transferable Black-Box Jailbreaks for Language Models via Persona Modulation](https://mlsanity.com/paper/2311.03348/) (2023)

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

- [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025)
- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [Reasoning Models Don't Always Say What They Think](https://mlsanity.com/paper/2505.05410/) (2025)
- [Monitoring Reasoning Models for Misbehavior and the Risks of Promoting Obfuscation](https://mlsanity.com/paper/2503.11926/) (2025)
- [Absolute Zero: Reinforced Self-play Reasoning with Zero Data](https://mlsanity.com/paper/2505.03335/) (2025)
- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [Emergent Misalignment: Narrow finetuning can produce broadly misaligned LLMs](https://mlsanity.com/paper/2502.17424/) (2025)
- [SPIRAL: Self-Play on Zero-Sum Games Incentivizes Reasoning via Multi-Agent Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2506.24119/) (2025)
- [ReMA: Learning to Meta-think for LLMs with Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2503.09501/) (2025)
- [WoW: Towards a World omniscient World model Through Embodied Interaction](https://mlsanity.com/paper/2509.22642/) (2025)
- [Evolving Deeper LLM Thinking](https://mlsanity.com/paper/2501.09891/) (2025)
- [The Limits of Inference Scaling Through Resampling](https://mlsanity.com/paper/2411.17501/) (2024)
- [SPC: Evolving Self-Play Critic via Adversarial Games for LLM Reasoning](https://mlsanity.com/paper/2504.19162/) (2025)
- [Preference Optimization for Reasoning with Pseudo Feedback](https://mlsanity.com/paper/2411.16345/) (2024)
- [Think or Not? Exploring Thinking Efficiency in Large Reasoning Models via an Information-Theoretic Lens](https://mlsanity.com/paper/2505.18237/) (2025)
- [Adaptive Deployment of Untrusted LLMs Reduces Distributed Threats](https://mlsanity.com/paper/2411.17693/) (2024)
- [Shrinking the Generation-Verification Gap with Weak Verifiers](https://mlsanity.com/paper/2506.18203/) (2025)
- [Teaching Models to Verbalize Reward Hacking in Chain-of-Thought Reasoning](https://mlsanity.com/paper/2506.22777/) (2025)
- [Adversarial Training of Reward Models](https://mlsanity.com/paper/2504.06141/) (2025)
- [Rethinking Inference-Time Scaling: Efficiency Limits and Linguistic Signals](https://mlsanity.com/paper/2504.14047/) (2025)
- [Training Language Models to Win Debates with Self-Play Improves Judge Accuracy](https://mlsanity.com/paper/2409.16636/) (2024)
- [Conformal Language Model Reasoning with Coherent Factuality](https://mlsanity.com/paper/2505.17126/) (2025)
- [Avoiding Obfuscation with Prover-Estimator Debate](https://mlsanity.com/paper/2506.13609/) (2025)
- [The Road to Artificial SuperIntelligence: A Comprehensive Survey of Superalignment](https://mlsanity.com/paper/2412.16468/) (2024)
- [SPADE: Self-Play in Adaptive Synthetic Executable Environments](https://mlsanity.com/paper/2608.19197/) (2026)
- [Can Theoretical Physics Research Benefit from Language Agents?](https://mlsanity.com/paper/2506.06214/) (2025)
- [Reasoning Models Sometimes Output Illegible Chains of Thought](https://mlsanity.com/paper/2510.27338/) (2025)
- [Hardening Agent Benchmarks with Adversarial Hacker-Fixer Loops](https://mlsanity.com/paper/2606.08960/) (2026)
- [Improving Rationality in the Reasoning Process of Language Models through Self-playing Game](https://mlsanity.com/paper/2506.22920/) (2025)
- [Outcome Rewards Do Not Guarantee Verifiable or Causally Important Reasoning](https://mlsanity.com/paper/2604.22074/) (2026)

## Abstract (arXiv)

One way to increase confidence in the outputs of Large Language Models (LLMs) is to support them with reasoning that is clear and easy to check -- a property we call legibility. We study legibility in the context of solving grade-school math problems and show that optimizing chain-of-thought solutions only for answer correctness can make them less legible. To mitigate the loss in legibility, we propose a training algorithm inspired by Prover-Verifier Game from Anil et al. (2021). Our algorithm iteratively trains small verifiers to predict solution correctness, "helpful" provers to produce correct solutions that the verifier accepts, and "sneaky" provers to produce incorrect solutions that fool the verifier. We find that the helpful prover's accuracy and the verifier's robustness to adversarial attacks increase over the course of training. Furthermore, we show that legibility training transfers to time-constrained humans tasked with verifying solution correctness. Over course of LLM training human accuracy increases when checking the helpful prover's solutions, and decreases when checking the sneaky prover's solutions. Hence, training for checkability by small verifiers is a plausible technique for increasing output legibility. Our results suggest legibility training against small verifiers as a practical avenue for increasing legibility of large LLMs to humans, and thus could help with alignment of superhuman models.