Summary (Overview)
- Problem: LLM-based theorem provers struggle to leverage newly contributed or rare lemmas because existing premise selectors rely on semantic similarity, which suffers from frequency-skewed retrieval, isolated pairwise ranking, and degradation on out-of-distribution queries.
- Key Insight: Mathematics is structured by dependencies rather than similarities. The authors restore dependency structure to both training data and model architecture.
- Resources: The paper mines two underused dependency resources: (1) a typed multi-level dependency graph from Mathlib4 (275k+ nodes, 6.5M edges), and (2) the first systematic mining of 53 Lean Blueprint projects (3,805 manually curated informal+formal nodes capturing rare, research-level premises).
- Method (DAPS): A dependency-aware premise selector with a structural neighborhood encoder, a group-level contrastive objective, and a Mathlib-then-Blueprint adaptation procedure.
- Results: DAPS achieves 78.74 Recall@16 on Mathlib4-Heldout (+11.41 over LeanHammer), a 7× recall margin on competition-style queries, and improves downstream theorem proving: Goedel-Prover-V2-8B Pass@4 on miniF2F rises from 49.90 to 54.03, with up to +11.4% relative improvement on informal IMO-ProofBench.
Introduction and Theoretical Foundation
LLM-based Lean 4 theorem proving has advanced rapidly (DeepSeek-Prover-V2, Kimina-Prover, Goedel-Prover-V2), yet these provers operate self-contained, generating subgoals and reusing memorized constants. They cannot leverage newly contributed lemmas in Mathlib4 or theorems from collaborative formalization projects because they lack a reliable way to identify appropriate premises among hundreds of thousands of declarations.
Existing neural selectors frame premise selection as semantic retrieval, with three intrinsic limitations:
- (P1) Frequency-skewed retrieval: Rare and recently added premises with weak text signal are displaced in top-K by popular foundational lemmas.
- (P2) Group-level relevance: Pairwise similarity ranks each lemma in isolation, missing whether the top-K cohere as a usable proof toolkit.
- (P3) Distribution shift: Mathlib-trained semantic features degrade on out-of-distribution queries (competition problems, research blueprints, informal language).
Root cause: Mathematics is structured by dependencies rather than similarities. What makes a lemma useful is its position in the dependency graph — the classes it presupposes, the lemmas it composes with, and its distance to known premises.
Two dependency resources in Lean 4:
- Mathlib4's compiled constant graph: A typed, heterogeneous DAG with 275k+ nodes and 6.5M edges. Directionally asymmetric: statement nodes (theorem, lemma) have high out-degree/low in-degree, while foundational constructs (class, structure, instance) show the opposite pattern.
- Lean Blueprint projects: Collaborative formalization repositories contributing 3,805 manually curated nodes (71.7% formal, 28.3% informal) across 53 research projects. Sparse (average degree 1.2) but containing rare, advanced premises absent from Mathlib4.
Methodology
Problem Formulation
Let denote a Lean library as a typed multi-level dependency DAG, where is the set of declarations and is a typed edge set. For each query declaration , let denote its positive premises. Premise selection produces a ranking evaluated by:
DAPS learns dependency-based embeddings and ranks by cosine similarity .
Structural Neighborhood Encoding (for P1)
For each candidate , DAPS encodes both itself and a sampled neighborhood from its 2-hop dependency subgraph:
- Semantic encoding: A text encoder maps name, category, signature, docstring, statement, and proof to a base feature , fine-tuned with masked contrastive loss and then frozen.
- Dynamic subgraph sampling: Collect 1- and 2-hop neighbors, randomly sample , score with a learnable FFN, retain top- as .
- Per-neighbor structural features: (1) Type embedding ; (2) Hop embedding ; (3) Positional encoding ; (4) Degree embedding capturing in-/out-degree asymmetry.
Fusion:
where .
Group-Level Contrastive Objective (for P2)
Instead of pulling a query toward a single positive, DAPS pulls multiple positives as a group relative to negatives. For each query , a positive set and negative set (via temporal, global, and cross-batch sampling) are used:
Mathlib-to-Blueprint Adaptation (for P3)
- Mathlib4 pretraining on abundant typed graph data.
- Blueprint continual training on the Blueprint training split with smaller sampling budget, where queries are informal statements and candidates encode both formal and informal statements.
Informal-Query Adaptation
For informal queries, DAPS is paired with a formalizer producing a Lean statement , then retrieves Lean-side premises (formalize-then-retrieve).
Empirical Validation / Results
Retrieval Results (K=16)
| Method | Mathlib4-Random (R) | Mathlib4-Heldout (R) | DAPS-Collection (R) | DAPS-Blueprint (R) |
|---|---|---|---|---|
| MePo | 14.14 | 7.98 | 0.53 | - |
| ReProver | 26.97 | 32.32 | 0.75 | 25.37 |
| LeanHammer | 61.13 | 67.33 | 1.98 | 31.36 |
| Qwen3-Embedding-8B | 11.54 | 6.74 | 0.24 | 11.02 |
| DAPS | 66.01 | 78.74 | 13.84 | 42.21‡ |
‡ After Blueprint continual training. DAPS achieves +11.41 Recall@16 over LeanHammer on Mathlib4-Heldout, and 7×/9× improvements in recall/precision on DAPS-Collection.
Formal Theorem Proving (miniF2F-test)
| Method | Goedel-Prover-V2-8B Pass@4 | DeepSeek-Prover-V2-7B Pass@4 |
|---|---|---|
| w/o premises | 49.90 | 48.23 |
| LeanExplore | 52.36 | 48.72 |
| LeanSearch | 51.43 | 47.32 |
| Qwen3-Embedding-8B | 51.84 | 47.68 |
| MePo | 50.60 | 47.75 |
| ReProver | 50.01 | 48.66 |
| LeanHammer | 48.93 | 49.19 |
| DAPS | 54.03 | 49.06 |
DAPS improves Pass@1 by +3.48 (Goedel-Prover-V2-8B) and +4.04 (DeepSeek-Prover-V2-7B) over no-premise baselines.
Informal Theorem Proving (IMO-ProofBench, Pass@8)
| Model | LeanExplore | LeanSearch | Qwen3 | DAPS | Δ% |
|---|---|---|---|---|---|
| Qwen3-235b | 18.45 | 17.01 | 19.08 | 21.25 | +11.37 |
| DeepSeek-V3.1 | 11.96 | 12.38 | 13.75 | 13.90 | +1.09 |
| kimi-k2-instruct | 8.66 | 8.26 | 8.27 | 9.08 | +4.85 |
| Gemini-3.6-Flash | 46.13 | 44.04 | 45.51 | 48.69 | +5.55 |
Key Ablation
Replacing the group-level contrastive objective with single-positive InfoNCE drops Recall@32 to 56.48 (Mathlib4-Random), 56.00 (Mathlib4-Heldout), and 15.25 (DAPS-Collection) — absolute decreases of 23.14, 33.30, and 9.13.
Frequency Breakdown
On Mathlib4-Heldout, DAPS leads LeanHammer in every premise-frequency bucket, with the gap widening toward the tail (91.6 vs 89.3 on head; 50.1 vs 39.4 on rarest bucket), confirming the P1 prediction that rare premises benefit most from dependency structure.
Theoretical and Practical Implications
- Theoretical: The paper demonstrates that dependency structure, not semantic similarity alone, is the organizing principle of mathematical knowledge. The directional asymmetry of the dependency graph (statement nodes vs. foundational constructs) provides a principled feature space for retrieval.
- Practical: DAPS enables LLM provers to leverage newly contributed and rare lemmas, closing the gap between self-contained provers and the growing body of formalized mathematics. The formalize-then-retrieve pipeline extends benefits to informal theorem proving with general-purpose LLMs.
- Resource contribution: The Blueprint corpus and four benchmarks (Mathlib4-Random, Mathlib4-Heldout, DAPS-Collection, DAPS-Blueprint) provide standardized evaluation with increasing distribution shift.
- Bottleneck insight: End-to-end proof success depends jointly on selected premises and the prover's ability to use them — retrieval metrics alone do not imply proof success. Premise-conditioned generation is an important remaining bottleneck.
Conclusion
DAPS addresses three intrinsic limitations of premise selectors (frequency-skewed retrieval, group-level relevance, distribution shift) by restoring dependency structure to both training data and model architecture. It curates two underused Lean 4 dependency resources (typed Mathlib4 graph and Blueprint corpus) and introduces a structural neighborhood encoder, group-level contrastive objective, and two-stage adaptation. DAPS outperforms strong selectors on all four benchmarks, with +11.41 Recall@16 over LeanHammer on Mathlib4-Heldout and 7× recall on competition-style queries. Downstream, it raises Goedel-Prover-V2-8B Pass@4 on miniF2F from 49.90 to 54.03 and improves four general-purpose LLMs on informal IMO-ProofBench (up to +11.4% relative).
Future directions: Training provers for premise-conditioned generation (rather than retrieval alone) is a promising direction, as the evaluated provers were not trained to condition on a supplied premise list, suggesting the observed gains are likely a lower bound.
Related papers
- BaseRSI: Recursive Self-Improvement of a Base Vision-Language Model via Training-Free Harness Internalization
BaseRSI lets a vision-language model improve its own weights via training-free per-block activation edits, gaining +11.7 points in-distribution and +6.1 out-of-distribution across ten benchmarks.
- Do Halting Heads Really Save Compute in Looped Language Models?
Halting heads in looped language models save far less compute than reported because mixture-trained heads rarely stop tokens and batching overhead eliminates most remaining gains.
- Inside the Loop: A Mechanistic Study of Looped Transformers on Permutation Traversal
Looped transformers solve sequential algorithmic tasks untied models of equal effective depth cannot, by executing one algorithm step per iteration without intermediate supervision.