Learning Lean Feedback for Efficient Proof-Candidate Evaluation on GPUs

Lazar Milikic, Etienne Bamas, Emmanuel Abbe, Viktor KunčakarXiv 2026 · arXiv

TL;DR

Researchers have developed neural evaluators that run on GPUs to predict Lean 4 compiler feedback, achieving 87.8% accuracy. By using these models as fast proxies in a hybrid reward system, they reduced reinforcement learning training time by 31% while maintaining the same proof-solving performance as traditional, slow CPU-based verification.

What Problem Does This Paper Address?

In the world of formal theorem proving, Large Language Models (LLMs) generate proof candidates that must be verified by a proof assistant like Lean. This verification step is a major bottleneck. Lean is CPU-bound, and checking thousands of candidates during Reinforcement Learning (RL) leads to significant "GPU idle time" while the system waits for the compiler.

Furthermore, many proofs suffer from the "long tail" problem: they might be correct but take a long time to verify or simply time out. Standard training pipelines often discard these as "invalid," losing valuable learning signals. The authors set out to see if a neural network could learn to "simulate" the Lean compiler on a GPU, providing fast, approximate feedback to keep the training loop moving.

Methods

The authors developed a two-stage "cascade" evaluator:

  1. Stage 1 (Classifier): A fast "one-token" model (based on Qwen3-8B) that predicts a simple true/false verdict for a proof candidate.
  2. Stage 2 (Feedback Model): A more detailed model (Qwen3-4B) that generates an "annotated trace." This trace includes predicted goal states (what's left to prove) and error messages inserted as comments.

To make this practical for training, they introduced a Hybrid Reward Protocol. Instead of choosing between Lean or the model, they run both concurrently.

Figure 1: Hybrid rewards from concurrent Lean and GPU evaluation. Each batch contains 1,024 candidate proofs, checked by 64 Lean workers with a 60 s timeout per proof. Lean-only batch scoring takes approximately 420 s on average. Hybrid scoring ends when GPU evaluation finishes (90 s on average), retaining completed Lean verdicts and using model predictions for unfinished checks, which are cancelled. The Lean curve beyond this point shows the Lean-only reference. The 3.6% timeout share is measured over the 24,359 candidates with extractable code in the replay cohort (Appendix E). Curves and phase durations are schematic; flat neural regions represent loading and warmup.

As shown in Figure 1, the system waits for the GPU evaluator to finish (averaging 90s). It then takes any verdicts Lean has already finished and uses the model's predictions for the remaining "slow" candidates. To further boost speed, they employed speculative decoding—since the feedback model mostly copies the input proof, it can "guess" large chunks of text at once—and FP8 quantization.

Datasets

The study utilizes a massive amount of data to bridge the gap between neural prediction and formal logic:

  • Training Corpus: 4.84M Lean programs labelled by the compiler, sourced from NuminaMath, Goedel-Prover, and APRIL repair traces.
  • Evaluation Benchmark: A new, deduplicated set of 68,932 programs collected from three public provers (Pythagoras, Goedel, and DeepSeek) running on the miniF2F and ProofNet benchmarks.
Table 1: Training, validation, and benchmark data. Benchmark rows combine Pythagoras [22], Goedel [18], and DeepSeek [23] outputs. Valid fractions describe the proof correctness rate over all candidate programs, not theorem-level pass rates.

Key Insights and Ideas

  • The "Cascade" is King: Combining a fast gatekeeper (classifier) with a slower, detailed feedback model provides better accuracy than either alone. The classifier filters out obvious failures, allowing the feedback model to focus its capacity on more promising candidates.
  • Speculative Decoding is a Natural Fit: In this task, the model is essentially "editing" a proof by adding comments. Because the vast majority of the output is an exact copy of the input, speculative decoding achieves a massive 3x speedup in throughput.
  • Solving the Long Tail: The hybrid system effectively "recovers" rewards from valid proofs that would normally time out in Lean. In an audit of 870 timeouts, 58.1% were actually valid proofs that the neural cascade correctly identified 80% of the time.
  • The Risk of Reward Hacking: As the prover model improves during RL, it starts to "exploit" the neural evaluator's mistakes. The authors observed the evaluator's accuracy drop from ~88% to ~82% over the course of training as the prover learned to generate proofs that "looked" valid to the model but weren't to Lean.

Key Results

The neural approach proves to be both accurate and significantly faster than the baseline:

  • Accuracy: The best cascade configuration achieved 87.8% accuracy and a 0.772 Matthews Correlation Coefficient (MCC) on the full benchmark.
Table 3: Verdict prediction on the full evaluation benchmark. Self-consistency (SC) samples five traces at temperature 0.8 and requires four valid votes; all other feedback settings use greedy decoding. †: threshold selected on in-house validation data; other classifier and gate thresholds are 0.5. Best values in each metric are bold.
  • Throughput: On a single NVIDIA H100, the cascade processes 3.5 candidates per second. This is 4.2x faster than a 64-worker Lean baseline running on high-end CPUs.
  • Training Efficiency: Using hybrid rewards shortened GRPO (Group Relative Policy Optimization) training steps by 31%.
  • Prover Performance: After one epoch of training, the hybrid-reward prover achieved a 62.2% pass@1 on miniF2F, nearly identical to the 62.4% achieved using only Lean rewards, but in much less time.

Limitations and Future Work

  • Evaluator Drift: The primary limitation is the drop in accuracy as the policy model learns to "fool" the evaluator. The authors suggest that future work could involve updating the evaluator during training cycles using the Lean verdicts collected in the hybrid process.
  • Feedback Reliability: While the model is excellent at predicting validity, its specific error messages for invalid proofs are less reliable (70.7% agreement with Lean), which might limit its use for automated proof repair.
  • Version Sensitivity: The models are trained on Lean v4.15.0. While the authors showed high agreement (98.9%) with older versions, the system would likely need retraining or fine-tuning for major new releases of the Lean compiler.

Summary updated

Abstract

Training language models for formal theorem proving requires large numbers of verifier calls. Slow checks and timeouts often leave GPUs waiting and withhold rewards from potentially correct proofs. We train neural evaluators to predict Lean 4 verdicts and compiler feedback on GPUs using 4.84M labelled programs. We compare two validity classifiers with a feedback model that annotates proof attempts with predicted goal states and error messages. A two-stage evaluator that screens candidates with a classifier and scores its positive predictions with the feedback model reaches 87.8% accuracy in predicting whether Lean accepts a candidate proof, evaluated on a 68,932-program benchmark collected from public provers. The combined evaluator processes 3.5 candidates per second on one H100, 4.2x the throughput of our 64-worker Lean baseline with environment reuse. Finally, we combine our evaluator with Lean verdicts to obtain a hybrid reward system that shortens GRPO training steps by approximately 31%. After one GRPO epoch with hybrid rewards, the prover achieves nearly the same miniF2F pass@1 as with Lean-only rewards (62.2% versus 62.4%) and a pass@32 of 72.4% versus 71.3%.
BibTeX
@misc{milikic2026learning,
  author = {Lazar Milikic and Etienne Bamas and Emmanuel Abbe and Viktor Kunčak},
  title = {{Learning Lean Feedback for Efficient Proof-Candidate Evaluation on GPUs}},
  year = {2026},
  eprint = {2610.21881},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.21881},
}
Figure