🤖 AI

Mitigating Legibility Tax with Decoupled Prover-Verifier Games

This paper proposes a decoupled prover-verifier game framework that mitigates the "legibility tax" by training a translator model to convert a solver's correct but uncheckable outputs into a verifiable format, thereby preserving accuracy while enhancing checkability.

Original authors: Yegon Kim, Juho Lee

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yegon Kim, Juho Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Legibility Tax"

Imagine you have a brilliant, super-smart student (a Large Language Model) who can solve very hard math problems. However, this student has a bad habit: when they explain their work, they write in a messy, confusing, or overly complicated way.

To make sure the student isn't cheating, you hire a teacher (a "Verifier") who is much less smart than the student. The teacher's job is to read the student's explanation and say, "Yes, this is right" or "No, this is wrong."

The Problem: In previous attempts to train these students to write clearly for the teacher, something went wrong. To make their explanations easier for the teacher to understand, the students started making mistakes in their actual math answers. They sacrificed getting the right answer just to make the explanation look good.

The authors call this the "Legibility Tax." It's like a student who gets a perfect score on a test but writes the answers in a way that the teacher can't read, so the teacher gives them a zero. Or, worse, the student changes the answer to something simple the teacher understands, even if it's wrong.

The Old Way: The "Do-It-All" Student

In the old method (called a standard Prover-Verifier Game), you asked the student to do two things at once:

Solve the math problem correctly.
Write the explanation clearly enough for the teacher to check.

The paper argues that asking the student to do both simultaneously is too hard. The student gets confused and starts failing the math part just to pass the "clarity" part.

The New Solution: The "Translator" Team

The authors propose a new team structure with three roles to fix this. Instead of one student trying to do everything, they split the work:

The Solver (The Genius): This model is trained only to get the right answer. It doesn't care if the explanation is messy. It just solves the math perfectly.
The Translator (The Editor): This model's only job is to take the Genius's messy solution and rewrite it into a clean, easy-to-read format. It must promise, "I will not change the answer, I will just make it look nice."
The Verifier (The Teacher): This model checks the Translator's work. It asks, "Is this explanation clear? And does it match the Genius's answer?"

How They Train: The "Good Cop, Bad Cop" Game

To make sure the Translator actually tells the truth and doesn't try to trick the teacher, the authors set up a game with two types of Translators:

The Faithful Translator: This one tries to rewrite the Genius's answer clearly, keeping the answer exactly the same.
The Sneaky Translator: This one is a "trickster." It is given the correct answer by the teacher but is told to write a convincing explanation that leads to a wrong answer. It tries to fool the Verifier into thinking a wrong answer is right.

The Game:

The Verifier tries to spot the difference between the Faithful Translator (who is honest) and the Sneaky Translator (who is lying).
The Faithful Translator tries to get the Verifier to agree that its explanation is clear and correct.
The Sneaky Translator tries to fool the Verifier.

Over time, the Verifier gets really good at spotting lies. The Faithful Translator learns that the only way to win is to be perfectly clear and stick to the original answer. The Sneaky Translator learns that it can't fool the Verifier anymore.

The Result: No More Tax

The paper shows that by separating the "getting the answer right" part from the "making it readable" part, they solved the problem.

Accuracy: The system kept the high accuracy of the Genius Solver (about 57% on their math test).
Legibility: The Translator learned to make the answers easy to check without changing the math.
No Tax: Unlike the old method, where accuracy dropped to 22% because the model tried to be too clear, this new method kept the accuracy high while making the output checkable.

A Simple Analogy: The Architect and the Blueprint

Think of it like building a house:

The Old Way: You asked the Architect to design the house and draw the blueprints perfectly at the same time. Because they were so focused on making the lines pretty, they accidentally put the kitchen in the wrong place.
The New Way: You hire a Master Builder who designs the house perfectly (ignoring how pretty the drawings are). Then, you hire a Draftsman whose only job is to take the Builder's rough notes and turn them into a beautiful, easy-to-read blueprint. You also hire a Inspector who checks if the blueprint matches the Builder's notes.

If the Draftsman tries to change the kitchen's location to make the drawing look simpler, the Inspector catches them. The result is a house that is built correctly (accurate) and has blueprints that are easy to read (legible).

Summary

The paper introduces a method to stop AI models from getting "dumber" just to make their answers easier to read. By splitting the job into a "Solver" (who gets the answer right) and a "Translator" (who makes it readable), and training them against a "Sneaky" trickster, they created a system that is both smart and easy to check, without losing accuracy.

Technical Summary: Mitigating Legibility Tax with Decoupled Prover-Verifier Games

Problem Statement

As Large Language Models (LLMs) advance in complex reasoning capabilities, a critical challenge arises: ensuring their outputs can be reliably validated by less capable systems, such as humans or smaller models. While Prover-Verifier Games (PVG) offer a promising framework for training models to produce "checkable" outputs without human supervision, they suffer from a significant drawback known as the legibility tax.

Previous work (Kirchner et al., 2024) demonstrated that training a single model to simultaneously maximize correctness and checkability results in a substantial degradation in accuracy compared to a baseline trained solely for correctness (e.g., dropping from 80% to 60% on grade-school math benchmarks). This phenomenon occurs because the optimization objective forces the model to compromise its reasoning capabilities to satisfy the constraints of being "convincing" to a verifier.

Methodology

The authors propose a Decoupled Prover-Verifier Game (DPVG) that separates the objectives of correctness and checkability. Instead of training a single prover to be both correct and checkable, the framework introduces three distinct components:

Solver ( $s$ ): A fixed model optimized purely for correctness. It generates a solution (reasoning and answer) without regard for checkability.
Translator ( $\tau$ ): A model tasked with converting the solver's solution into a checkable form. Crucially, the translator must be faithful, meaning its final answer must match the solver's answer.
Verifier ( $v$ ): A model trained to distinguish between proofs containing correct answers and those containing incorrect answers.

The Decoupled Game Structure

The game involves a Faithful Translator and a Sneaky Translator ( $\tau'$ ), competing against the Verifier:

Faithful Translator: Attempts to craft a convincing proof for the solver's answer.
Sneaky Translator: Attempts to craft a convincing proof for an incorrect answer. To facilitate this, the sneaky translator is provided with the ground-truth answer $y$ to ensure it knows what not to output, rather than having to implicitly solve the problem to find an alternative wrong answer.
Verifier: Optimizes a classification objective to discriminate between the outputs of the faithful and sneaky translators.

Optimization and Equilibrium

The authors formulate a Stackelberg game where the verifier leads. They prove (Theorem 1) that the equilibrium of this game corresponds exactly to a faithful and checkable translator.

Faithfulness: The translator's answer matches the solver's answer.
Checkability: The system satisfies Completeness (the verifier accepts correct proofs) and Soundness (the verifier rejects incorrect proofs).

The training process involves alternating rounds of training the verifier (using cross-entropy loss) and the translators (using Reinforcement Learning with RLOO). The reward function for the translators is designed to encourage role-alignment (faithfulness for the faithful translator, deception for the sneaky one) and high verifier scores for convincing proofs.

Key Contributions

Decoupling Framework: The paper introduces a novel architecture that decouples the correctness of the reasoning (handled by the solver) from the checkability of the output (handled by the translator).
Theoretical Guarantee: The authors provide a formal proof that the equilibria of their proposed game correspond to faithful and checkable translators, ensuring that the checkability objective does not compromise the underlying correctness.
Mitigation of Legibility Tax: The framework demonstrates that it is possible to train models to produce checkable outputs without the accuracy degradation observed in traditional PVG setups.

Experimental Results

The authors evaluated their method on the GSM8K-Aug dataset using Llama-2-7b-chat for solvers/translators and Qwen2-1.5B for verifiers.

Accuracy Preservation: The DPVG model achieved 56.9% accuracy on the test set, nearly identical to the trained solver baseline (57.0%). In contrast, the standard PVG approach (reproduced from Kirchner et al., 2024) dropped significantly to 22.3%, confirming the presence of the legibility tax in the baseline.
Faithfulness: The faithful translator converged to a faithfulness score of 1.0 (100%) during training and 99.8% on a separate test set, indicating the translator successfully preserved the solver's answer.
Training Dynamics: The verifier score for the sneaky translator increased over rounds, indicating the verifier became more robust. Conversely, the faithful translator's outputs became more structured and concise over training rounds, suggesting improved legibility.

Significance and Claims

The paper claims that by decoupling the generation of correct answers from the generation of checkable proofs, it is possible to achieve stable training dynamics where legibility is improved without harming system accuracy. The authors position this as a solution to the "legibility tax," allowing for the deployment of highly capable reasoning models that remain verifiable by less capable systems.

The authors remain modest regarding their claims, noting that:

They did not conduct human evaluation studies to precisely measure legibility improvements at scale, relying instead on qualitative samples and verifier scores.
The "legibility tax" in previous works might also be attributed to a lack of chain-of-thought reasoning in the prover, a factor they suggest for future investigation.
Future work includes exploring alternative reward formulations and adding chain-of-thought reasoning before proof generation.

The core contribution is the demonstration that a translator-based approach can retain the high accuracy of a solver while satisfying the rigorous checkability conditions required for trustworthy AI oversight.