TL;DR
Existing formal theorem provers often rely on human-written helper lemmas or expensive step-by-step tree searches. Proof Decomposer (ProD-RL) trains language models to autonomously decompose proofs into hierarchical sub-lemmas, rewarding models for generating and proving correct lemmas even if the parent theorem remains unsolved.
What Problem Does This Paper Address?
Automated formal theorem proving (in systems like Isabelle or Lean) provides verifiable reasoning without relying on fallible LLM self-evaluation. However, prior research suffers from two key drawbacks:
- Unrealistic Test Setups: Most benchmarks leave human-written helper lemmas in the context or split datasets randomly across files, letting models peek at tailored lemmas. In real mathematical practice, a prover must invent its own intermediate lemmas from scratch.
- Prohibitive Compute: Step-by-step search algorithms (like $A^*$ or MCTS) constantly query LLMs on lengthy proof states, consuming massive compute (e.g., over 1,000 GPU days for a 600M-parameter model).
This paper investigates how to train a 7B-parameter model to directly plan, decompose, and verify formal proofs hierarchically in a realistic setting without test-time helper lemmas.
Methods
The authors introduce Proof Decomposer (ProD) and an accompanying reinforcement learning pipeline (ProD-RL):
- Conditional Proofs & Proof Trees: The standard proof syntax is extended with special
<invoke>tags. An LLM generates a proof that assumes newly proposed lemmas; these lemmas then become child nodes in a proof tree to be proven recursively up to a fixed depth. - Local vs. Global Correctness:
- A proof node is locally correct if the verifier accepts its steps assuming its proposed lemmas hold.
- A proof is globally correct if the node and all of its descendant lemmas are proven valid.
- Rewarding Partial Progress (Hindsight Experience): In standard RL, an unproven root theorem yields zero reward. ProD-RL borrows intuition from human mathematicians: if an LLM fails a difficult theorem but invents and proves a correct, non-trivial sub-lemma along the way, that sub-lemma is rewarded ($r = 1$) and used for gradient updates.
- Filtering & Value Weighting: Trivial lemmas (identical to the goal) and unused lemmas are filtered out. A value network ($V_\phi$) scores proof steps, and a discount factor penalizes unnecessarily long proofs.
- Low Training Footprint: Fine-tuning and RL on a 7B model took under 36 GPU days on A100s.
Datasets
- Training Data: Sourced from the Isabelle Archive of Formal Proofs (AFP) and built-in theories (e.g.,
HOL), yielding a 312k-example SFT dataset and a 104k-example RL dataset of decomposable theorems ($T_{\text{tree}}$). - Dependency-Based Split: Unlike random splits, the authors split data by file dependency so that no test entry is ever referenced by training files.
- Evaluation Sets:
- AFP Test: 4,300 holdout theorems from leaf entries in the dependency graph.
- AFP 2023: 2,000 theorems submitted after April 2023 (the pre-training cutoff date for the base Llemma model) to eliminate data contamination.
Key Insights and Ideas
- Harder, More Realistic Benchmark: Removing helper lemmas and splitting by file dependency causes standard SFT performance to drop dramatically from 45.7% to 35.7% pass@4, showing that prior benchmarks masked weaknesses in model planning.
- Vanilla RL Hits a Wall: Without lemma proposal, standard RL on full proofs failed to improve over the SFT baseline (42.4% vs. 43.4% on AFP test).
- Self-Generated Data via Exploration: ProD-RL broke this bottleneck because 37.7% of the lemmas proven during training were completely novel (absent from the human training corpus), acting as an automated mathematical curriculum.
Key Results
- Higher Pass Rates: On the holdout AFP test set, ProD-RL achieved 45.5% pass@16, outperforming ProD-SFT (40.8%), SFT without lemma proposal (43.4%), and RL without lemma proposal (42.4%).
- Contamination-Free Generalization: On AFP 2023, ProD-RL reached 39.5% pass@16 compared to 36.5% for ProD-SFT and 37.7% for baseline RL.
- Sweet Spot at Moderate Difficulty: Improvements came primarily from theorems of low-to-moderate complexity (ground-truth proof depths $\le 2$). Deep, complex theorems (depth $\ge 3$) remain challenging across all tested approaches.
Limitations and Future Work
- Simplicity of Generated Lemmas: Qualitative inspection shows that proposed lemmas typically represent basic case distinctions (e.g., $x \in A$ vs. $x \notin A$) or direct rephrasings rather than profound mathematical leaps.
- Heavy Distribution Shifts: On the temporally separated AFP 2023 benchmark, ProD-RL showed more modest gains over the non-decomposed baseline, suggesting vulnerability to shifts in mathematical domain.
- Future Work: Scaling the architecture to larger base models, allowing deeper search trees, and incorporating unlabeled or auto-formalized natural language math datasets into the RL loop.
Summary updated