🤖 AI

Process-Verified Reinforcement Learning for Theorem Proving via Lean

This paper introduces a reinforcement learning framework that leverages the Lean proof assistant as a symbolic process oracle to provide dense, fine-grained, and sound tactic-level feedback, significantly improving theorem proving performance on benchmarks like MiniF2F and ProofNet compared to traditional outcome-only reward methods.

Original authors: Minsu Kim, Se-Young Yun

Published 2026-06-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Minsu Kim, Se-Young Yun

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

Imagine you are teaching a robot to solve complex math puzzles. In the past, the way we taught these robots (which are Large Language Models) was like playing a game of "Hot or Cold" with a very strict referee.

The Old Way: The "Pass or Fail" Coach
Previously, the robot would write out a full solution to a math problem. The referee (a computer program called Lean) would look at the final answer and say only one thing: "You got it right!" or "You got it wrong."

If the robot got it wrong, it had no idea why. Did it make a mistake in the very first step? Did it use the wrong formula in the middle? Or did it just run out of time? It was like a student getting an "F" on a test without seeing the graded paper. The robot had to guess what went wrong and try again, which is slow and inefficient.

The New Way: The "Step-by-Step" Coach
This paper introduces a smarter way to train the robot. Instead of just waiting for the final answer, the Lean referee watches the robot's thinking process step-by-step.

Think of a math proof like building a tower out of blocks.

The Old Way: You build the whole tower, and if it falls at the end, the coach just says, "Bad tower." You have to guess which block caused the collapse.
The New Way (This Paper): The coach watches you place every single block.
- If you place a block correctly, the coach gives you a tiny "Good job!" (a positive signal).
- If you place a block incorrectly, the coach immediately says, "Stop! That block is wrong."
- Crucially: The coach explains that because that block was wrong, every single block you put on top of it is now invalid, even if they look okay on their own. This is called "First-Error Propagation." It teaches the robot that one mistake ruins the whole foundation.

How It Works in the Paper
The researchers used a method called Reinforcement Learning. Here is the breakdown of their "secret sauce":

The Oracle: They used the Lean proof assistant not just as a final judge, but as a process oracle. This means it acts like a super-teacher that understands the rules of logic perfectly and can spot errors in real-time.
The Feedback Loop: When the robot tries to solve a problem, Lean breaks the solution down into a sequence of "tactics" (small logical steps).
- If the whole proof works, the robot gets a big reward.
- If the proof fails, Lean tells the robot exactly which step failed. The robot learns that the steps before the failure were okay, but the step at the failure and everything after it are wrong.
The Credit System: The paper found that the most important part of a step is the very first word (or token) of that step. It's like the "command word" (e.g., "Add," "Multiply," "Assume"). The researchers decided to give the reward or penalty specifically to that first word. This helps the robot learn to pick the right "command" for the job, rather than just memorizing the whole sentence.

The Results
When they tested this new method on famous math benchmarks (MiniF2F and ProofNet):

The robots learned faster and made fewer mistakes.
They became more stable and reliable than robots trained only on "Pass/Fail" feedback.
They performed better than robots that tried to use other, less precise methods to guess which steps were good.

The Big Picture
The main takeaway is that formal proof assistants (like Lean) shouldn't just be used to check answers at the end. They can be used as coaches during the training process. By giving the AI dense, specific feedback on how it thinks, rather than just what it concludes, we can build smarter, more reliable AI for solving hard logical problems.

What They Didn't Do
The paper is very specific about what it achieved. It did not claim to solve all math problems, nor did it claim this method works for writing stories or chatting with people. It is strictly about teaching AI to prove mathematical theorems using the Lean language. They also noted that they didn't compare their method to other "learned" coaches because those require huge amounts of human-written examples that don't exist yet for this specific type of math.

Technical Summary: Process-Verified Reinforcement Learning for Theorem Proving via Lean

Problem Statement

Automated Theorem Proving (ATP) aims to generate formal proofs for mathematical theorems. While Large Language Models (LLMs) have advanced reasoning tasks, they typically rely on natural language (NL) or binary outcome rewards (correct/incorrect) during Reinforcement Learning (RL). This creates a gap:

Sparse Feedback: Standard RL approaches often use only a final binary signal (proof passed/failed), which provides sparse credit assignment and struggles to guide the model through long reasoning chains.
Unstructured vs. Structured: Unlike symbolic proof assistants (e.g., Lean, Coq, Isabelle) which offer fine-grained, type-theoretic verification of every reasoning step, LLMs are trained on token sequences with scalar rewards.
Process Reward Models (PRMs): While recent work uses PRMs to provide step-level rewards, these often require large annotated datasets or rely on NL-based CoT supervision, lacking the rigorous soundness of symbolic verification.

The core challenge addressed is how to leverage the rich, structured feedback from a symbolic proof assistant (Lean) to train LLMs without relying on external, potentially noisy PRMs or human annotations.

Methodology

The paper proposes Process-Verified Reinforcement Learning, a framework that integrates Lean's symbolic feedback directly into a Group Relative Policy Optimization (GRPO) objective. The method consists of three main components:

1. Symbolic Process Oracle

Instead of treating Lean merely as a final verifier, the authors utilize it as a process oracle during training.

Parsing: Generated proofs are parsed into sequences of tactics ( $T_1, \dots, T_N$ ) based on the Abstract Syntax Tree (AST).
Verification: Lean's elaboration process provides two types of signals:
- Outcome Signal: A global binary score $g(Y) \in \{0, 1\}$ indicating if the entire proof is valid.
- Process Signal: Fine-grained feedback for each tactic, identifying locally sound steps and the specific location of the first error.

2. Credit Assignment Strategy

To bridge the gap between symbolic feedback and token-level RL, the authors introduce specific assignment rules:

First-Error Propagation: If a tactic $T_j$ fails, all subsequent tactics ( $T_k$ where $k \ge j$ ) are treated as erroneous. This reflects the causal nature of proofs: an invalid prefix invalidates the entire subsequent reasoning chain.
Tactic-Level Scoring ( $\phi$ ):
- If the proof passes ( $g(Y)=1$ ), all tactics receive a positive score (1).
- If the proof fails ( $g(Y)=0$ $g (Y) = 0$ ):
  - Tactics before the first error receive a partial score ( $d_1$ ).
  - The first erroneous tactic and all subsequent ones receive a penalty score ( $d_2$ ).
Token-Level Mapping: The tactic-level advantage is assigned only to the first token of each tactic (the keyword, e.g., intro, apply). This aligns with the semantic decision point where the proof strategy is determined.

3. RL Objective (GRPO Integration)

The framework combines outcome and process advantages into a single GRPO objective:

Outcome Advantage ( $A_{outcome}$ ): Calculated based on the global pass/fail status relative to the group mean.
Process Advantage ( $A_{process}$ ): Calculated based on the tactic-level scores, normalized by the group's mean outcome reward to account for problem difficulty.
Combined Advantage: For a token $t$ belonging to the first token of tactic $j$ in response $i$ :
$A_{i,t} = A_{outcome, i, t} + A_{process, i, j}$
For non-first tokens, only the outcome advantage is applied. This formulation avoids the need for a value model or auxiliary PRM, relying solely on the verifier's ground truth.

Key Contributions

Formalization of Symbolic Feedback: The authors formalize Lean's tactic-level feedback into scalar training signals, enabling fine-grained, token-level credit assignment without natural language guidance.
Symbolic Verifier-Guided RL: They integrate outcome and tactic-level rewards derived directly from Lean into an RL framework, providing dense and verifiable credit assignment.
Stable Benchmark Improvements: The approach demonstrates consistent improvements on MiniF2F and ProofNet benchmarks, outperforming outcome-only RL and vanilla baselines without requiring external PRMs or NL notation.

Experimental Results

Experiments were conducted using STP-Lean and DeepSeek-Prover-V1.5 (7B models) on the MiniF2F-Test and ProofNet-Test benchmarks.

Performance Gains:
- STP-Lean: The proposed method improved MiniF2F pass@64 by +2.5% (from 56.7% to 59.2%) and ProofNet pass@32 by +1.4%.
- DeepSeek-Prover-V1.5: Consistent, albeit marginal, improvements were observed across all settings.
Comparison to Baselines:
- The method outperformed "Outcome-only" GRPO, which showed instability and failed to improve on ProofNet in some configurations.
- It achieved competitive results against strong tree-search baselines (e.g., InternLM2.5-StepProver, DeepSeek-Prover-RL+RMaxTS) while using a single-shot generation approach without massive inference-time search budgets.
Ablation Studies:
- Token Assignment: Assigning credit to the first token of a tactic yielded the most stable results compared to distributing credit across all tokens or the last token.
- First-Error Propagation: Removing this rule significantly degraded performance, confirming the necessity of treating subsequent steps as invalid after an error.
- Timeouts: A 15-second verification timeout provided the best balance, encouraging concise proofs without discarding valid complex ones.

Significance and Claims

The paper claims that symbolic proof assistants should not be viewed solely as evaluation tools but as active process-level reward oracles during training. By leveraging the "rich, fine-grained structured feedback" inherent in formal reasoning systems, the authors demonstrate a path toward RL frameworks that combine the scalability of LLMs with the reliability of symbolic verification.

The study highlights that:

Dense, Verifiable Signals: Using the prover's own error logs and elaboration trees provides a sound, dense reward signal that is superior to sparse binary outcomes or learned PRMs.
Stability: The combination of global outcome rewards and local tactic rewards stabilizes training, preventing the premature convergence seen in tactic-only training and the sparsity issues of outcome-only training.
Efficiency: This approach achieves state-of-the-art or competitive performance without the computational overhead of tree search or the data requirements of training separate PRMs.

The authors remain modest regarding limitations, noting that their method relies on fixed reward scores ( $d_1, d_2$ ) rather than learned advantage estimators and currently focuses on non-CoT, pure Lean proofs, leaving open the design of rewards for long-form natural language reasoning.