🤖 AI

Pythagoras-Prover: Advancing Efficient Formal Proving via Augmented Lean Formalisation

Pythagoras-Prover is a compute-efficient family of open-source Lean theorem provers that leverages curriculum-based supervised fine-tuning and Augmented Lean Formalisation to achieve state-of-the-art performance on formal proving benchmarks with significantly fewer parameters than existing models.

Original authors: Joshua Ong Jun Leang, Zheng Zhao, Mihaela Cătălina Stoian, Qiyuan Xu, Haonan Li, Wenda Li, Shay B. Cohen, Eleonora Giunchiglia

Published 2026-06-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joshua Ong Jun Leang, Zheng Zhao, Mihaela Cătălina Stoian, Qiyuan Xu, Haonan Li, Wenda Li, Shay B. Cohen, Eleonora Giunchiglia

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 trying to teach a robot to solve extremely difficult math puzzles, but with a catch: the robot must write its solution in a strict, computer-readable language called Lean. If the robot makes even a tiny logical mistake, the computer rejects the answer. This is the world of Automated Theorem Proving.

For a long time, the only way to get a robot good at this was to feed it massive amounts of data and use a "brain" (a computer model) so huge it cost millions of dollars to run. It was like trying to win a chess tournament by hiring a team of 1,000 grandmasters to think for you.

The paper introduces Pythagoras-Prover, a new family of robot mathematicians that proves you don't need a giant brain or a million-dollar budget to win. They achieved this through three clever tricks:

1. The "Training Camp" (Curriculum Learning)

Instead of throwing the robot into the deep end with the hardest problems immediately, the researchers built a training camp with three levels: Easy, Medium, and Hard.

The Analogy: Imagine teaching a child to ride a bike. You don't start them on a mountain trail. You start them on a flat sidewalk (Easy), then a gentle hill (Medium), and finally the mountain trail (Hard).
How they did it: They created a huge library of math problems. If a problem was too hard for the robot to solve, they didn't just throw it away. They used a "rubric" (a checklist of common mistakes) to break the problem down into a simpler version that the robot could solve. This allowed the robot to learn step-by-step, building confidence and skill before tackling the giants.

2. The "Mad Libs" Machine (Augmented Lean Formalisation)

The biggest problem in this field is a lack of good practice problems. The researchers realized they could create more practice problems without needing a human to write them or a supercomputer to check them.

The Analogy: Imagine you have a perfect math story. Instead of writing a whole new story from scratch, you play a game of "Mad Libs." You swap out the numbers, change the names of the characters, or rearrange the order of the steps, but the logic of the story stays the same.
How they did it: They took their verified problems and used a tool called ALF to mutate them. They created variations (simpler versions, harder versions, or just different wording). They didn't check every single new variation with the strict computer (which is slow and expensive); they just checked that the new problem looked like a valid math problem. This exploded their library of practice problems by 2.5 times, giving the robot way more material to learn from.

3. The "Self-Reflection" Loop (Self-Distillation)

Once the robot learned the basics, they let it teach itself.

The Analogy: Imagine a student who has studied hard. Instead of just taking a test, they try to solve new variations of the problems they just learned. If they get it right, they write it down as a new example for themselves to study later.
How they did it: The robot generated proofs for those "Mad Libs" variations. Even though the computer didn't double-check every single one, the fact that the robot could generate a proof for a mutated version meant it truly understood the logic, not just memorized the answer. This "self-taught" data made the robot even smarter.

The Results: Small Brain, Big Wins

The paper compares their new robots to the current "giants" in the field:

The 4B Robot: This robot has 4 billion "neurons" (parameters). It is roughly 167 times smaller than the previous champion (DeepSeek-Prover-V2, which has 671 billion neurons).
- The Result: Despite being tiny, the 4B robot solved more problems correctly than the giant robot. It's like a high school math whiz beating a team of PhDs because the whiz was trained better.
The 32B Robot: This slightly larger robot became the best open-source robot ever tested on these benchmarks, solving 93% of the problems.

The "Diffusion" Experiment

The researchers also tried a different way of thinking called Diffusion.

The Analogy:
- Standard (Autoregressive): Writing a sentence one word at a time, from left to right. If you make a mistake early, you have to rewrite the whole thing.
- Diffusion: Imagine a blurry sketch of a sentence. The robot looks at the whole sketch and fills in the missing words all at once, refining the picture until it's clear. It can fix a mistake in the middle without rewriting the beginning.
The Result: This "Diffusion" robot was 2.5 times faster at generating answers than the standard robot, though it was slightly less accurate. It shows a new way to trade speed for precision.

The "Stress Test" (MiniF2F-ALF)

To see if the robots were just memorizing answers or actually learning, the researchers created a "stress test." They took the test questions and slightly mutated them (changing numbers, swapping variables) using the same "Mad Libs" technique.

The Result: Most robots failed this test because they had memorized the original questions. Pythagoras-Prover, however, handled the mutations much better. This proves they learned the logic of math, not just the specific answers.

Summary

Pythagoras-Prover shows that you don't need a super-computer to solve hard math proofs. By using a smart training schedule, creating endless variations of practice problems, and letting the robot teach itself, you can build a small, efficient robot that outperforms the massive, expensive giants of the past.

Technical Summary: Pythagoras-Prover

Problem Statement

Modern Lean theorem provers have achieved strong performance but rely heavily on substantial training and inference compute, often requiring frontier-scale models (hundreds of billions of parameters) or computationally intensive inference procedures like extensive search, self-correction, and large sampling budgets. This reliance is driven by the scarcity of verified proof data and the long reasoning traces required for formal proof search, which make supervised fine-tuning (SFT) and sampling expensive. Consequently, a significant gap exists between small open-source provers and their largest counterparts, limiting accessibility for researchers and practitioners without massive compute resources.

Methodology

The authors introduce Pythagoras-Prover, a compute-efficient family of open-source Lean 4 theorem provers. The approach relies on a staged, compute-frugal data pipeline and training strategy rather than raw model scale.

1. Data Construction and Curriculum Learning

The training corpus is constructed in three difficulty tiers (Easy, Medium, Hard), all gated by the Lean type-checker to ensure correctness:

Easy and Medium Tiers: Generated via a three-stage pipeline inspired by "Theorem Prover as a Judge." Natural language problems from datasets like DART-Math-Hard, DeepScaleR, and OpenR1-Math are autoformalized into Lean statements. Failed proofs are analyzed, and a rubric-guided distillation process generates simplified synthetic variants targeting specific error categories (e.g., tactic failures, type mismatches). This process yields a 30% relative improvement in autoformalization success rates.
Hard Tier: Sourced from competition-level problems (Olympiads, AIME, AMC) from Big-Math-RL-Verified. Unlike the easier tiers, these are not simplified to preserve their difficulty for reinforcement learning (RL).
Curriculum SFT: Models are trained using a difficulty-ordered curriculum (Easy $\to$ Medium $\to$ Hard) with LoRA (Low-Rank Adaptation) to maintain parameter efficiency. A dynamic proof-reasoning filtering scheme is applied during SFT to manage the 8k-token context budget: if the reasoning chain plus proof exceeds the limit, the reasoning is dropped while retaining the proof; if the proof alone exceeds the limit, the instance is discarded.

2. Augmented Lean Formalisation (ALF) and Self-Distillation

To overcome the bottleneck of Lean verification throughput, the authors introduce Augmented Lean Formalisation (ALF).

Mechanism: ALF applies five structured mutation operators (simplification, generalization, lemma proposal, proof-step decomposition, reformulation) to verified seed instances.
Efficiency: Instead of verifying every mutated instance with Lean (which is computationally prohibitive), ALF uses a lightweight statement-alignment check. It verifies that the generated proof references the mutated statement, ensuring structural validity without full compilation.
Self-Distillation: The post-RL model generates proofs for these mutated statements. This expands the corpus by roughly 2.5 $\times$ (to ~2M instances) without requiring per-instance verification. This expanded corpus is used for continued SFT and to train a diffusion-based prover.

3. Model Architectures

The family spans two generation paradigms:

Autoregressive Provers: 4B and 32B parameter models trained with the above pipeline.
Diffusion-Based Prover: Pythagoras-Prover-Diffusion-4B, the first proof-of-concept diffusion-based theorem prover for Lean. It utilizes tactic-based masking, where entire Lean tactics are masked and denoised as units rather than individual tokens, aligning the denoising objective with discrete reasoning steps.

4. Reinforcement Learning (RL)

RL is performed on held-out hard problems using GRPO (Group Relative Policy Optimization) with full-parameter fine-tuning. The reward is binary (proof compiles and aligns with the statement). The authors note that RL yields only modest gains over the curriculum-SFT model, suggesting the high quality of the supervised corpus already internalizes strong proof-search behavior.

Key Contributions

Compute-Efficient Provers: A family of open-source Lean provers (4B, 32B, and a 4B diffusion model) that challenges the assumption that strong formal reasoning requires frontier-scale models.
ALF Data Pipeline: A structured mutation scheme that expands verified corpora by ~2.5 $\times$ using lightweight sanity checks instead of per-instance Lean verification, decoupling corpus expansion from verifier throughput.
MiniF2F-ALF Benchmark: A contamination-sensitive perturbation benchmark created by applying ALF mutations to the MiniF2F-Test set. It serves as a stress test to evaluate whether models rely on exact benchmark recall or possess transferable proof behaviors.
First Diffusion Theorem Prover: A viable diffusion-based prover for Lean, demonstrating that iterative refinement is a feasible decoding strategy for formal proofs, albeit with current context length limitations.

Experimental Results

Evaluated on MiniF2F-Test, PutnamBench, and MiniF2F-ALF:

MiniF2F-Test (Pass@32):
- Pythagoras-Prover-4B achieves 86.1%, surpassing DeepSeek-Prover-V2-671B (82.4%) despite being roughly 167 $\times$ smaller. It also outperforms Goedel-Prover-V2-8B (84.6%) and Kimina-Prover-70B (84.0%).
- Pythagoras-Prover-32B achieves 89.8%, leading all open-source provers evaluated without self-correction.
MiniF2F-Test (Pass@2048):
- Pythagoras-Prover-32B reaches 93.03%, setting a new state-of-the-art for open-weight neural Lean provers without self-correction, outperforming Goedel-Prover-V2-32B (92.2% at Pass@8192) with a quarter of the sampling budget.
PutnamBench:
- Pythagoras-Prover-32B solves 93 out of 672 problems at Pass@2048, the strongest open-source result, surpassing Goedel-Prover-V2 (86 at Pass@184 with self-correction).
MiniF2F-ALF (Robustness):
- All evaluated models degrade on this perturbed benchmark, confirming that high accuracy on the original split does not guarantee robustness to structural variants.
- Pythagoras-Prover-32B remains the strongest (85.0%), and Pythagoras-Prover-4B (83.2%) achieves parity with the 8 $\times$ larger Goedel-Prover-V2-32B (83.6%), degrading less under perturbation.
Diffusion Efficiency:
- Pythagoras-Prover-Diffusion-4B achieves 63.25% Pass@32 on MiniF2F-Test. While less accurate than its autoregressive counterpart, it generates proofs 2.58 $\times$ faster (10.56 vs 4.10 tokens/sec), offering a higher throughput-per-GPU-second.

Significance and Claims

The paper claims that strong Lean theorem proving need not rely exclusively on frontier-scale models. The results demonstrate that careful data construction (curriculum learning, ALF augmentation, self-distillation) and efficient training recipes (LoRA, dynamic filtering) can substitute, in part, for raw model scale.

Specifically, the authors highlight:

Efficiency: Pythagoras-Prover-4B outperforms a 671B-parameter model, suggesting that the proposed training recipe transfers cleanly to small-model regimes where billion-scale baselines are impractical.
Robustness: The use of ALF mutations during training improves robustness to statement-level perturbations, as evidenced by the smaller performance drop on MiniF2F-ALF compared to baselines.
New Paradigms: The introduction of a diffusion-based prover establishes an initial baseline for iterative refinement in formal proving, opening a complementary direction where provers can be compared by throughput and proofs-per-GPU-second, not just accuracy.

The authors conclude that the "compute-frugal" data pipeline is the primary driver of these results, enabling state-of-the-art performance under practical compute budgets.