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:

  1. 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.
  2. 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 L=(V,E)\mathcal{L} = (\mathcal{V}, \mathcal{E}) denote a Lean library as a typed multi-level dependency DAG, where V\mathcal{V} is the set of declarations and E⊆V×V×T\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V} \times \mathcal{T} is a typed edge set. For each query declaration q∈Vq \in \mathcal{V}, let P⋆(q)⊆V\mathcal{P}^{\star}(q) \subseteq \mathcal{V} denote its positive premises. Premise selection produces a ranking rr evaluated by:

R@K(q)=∣TopK(r)∩P⋆(q)∣∣P⋆(q)∣\mathrm{R@}K(q) = \frac{|\mathrm{Top}_{K}(r) \cap \mathcal{P}^{\star}(q)|}{|\mathcal{P}^{\star}(q)|}

DAPS learns dependency-based embeddings h(⋅)h(\cdot) and ranks by cosine similarity sim(h(qˉ),h(p))\mathrm{sim}(h(\bar{q}), h(p)).

Structural Neighborhood Encoding (for P1)

For each candidate pp, DAPS encodes both pp 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 hfeat(p)h_{\mathrm{feat}}(p), fine-tuned with masked contrastive loss and then frozen.
  • Dynamic subgraph sampling: Collect 1- and 2-hop neighbors, randomly sample mm, score with a learnable FFN, retain top-nn as N(p)\mathcal{N}(p).
  • Per-neighbor structural features: (1) Type embedding htype(pi)h_{\mathrm{type}}(p_i); (2) Hop embedding hhop(p,pi)∈{0,1,2}h_{\mathrm{hop}}(p, p_i) \in \{0,1,2\}; (3) Positional encoding hpe(pi)h_{\mathrm{pe}}(p_i); (4) Degree embedding hdeg(pi)=Wdeg[deg⁡−(pi);deg⁡+(pi)]h_{\mathrm{deg}}(p_i) = W_{\mathrm{deg}}[\deg^{-}(p_i); \deg^{+}(p_i)] capturing in-/out-degree asymmetry.

Fusion:

h(pi)=O[hfeat(pi);htype(pi);hhop(p,pi);hpe(pi)]+hdeg(pi)+hres(p)h(p_i) = O[h_{\mathrm{feat}}(p_i); h_{\mathrm{type}}(p_i); h_{\mathrm{hop}}(p, p_i); h_{\mathrm{pe}}(p_i)] + h_{\mathrm{deg}}(p_i) + h_{\mathrm{res}}(p)

where hres(p)=Wtype⋅onehot(ϕ(p))h_{\mathrm{res}}(p) = W_{\mathrm{type}} \cdot \mathrm{onehot}(\phi(p)).

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 qq, a positive set Pq+⊆P⋆(q)\mathcal{P}_q^{+} \subseteq \mathcal{P}^{\star}(q) and negative set Pq−\mathcal{P}_q^{-} (via temporal, global, and cross-batch sampling) are used:

Lq=−1∣Pq+∣∑p∈Pq+log⁡exp⁡(sim(h(q),h(p))/τ)∑p′∈Pq+∪Pq−exp⁡(sim(h(q),h(p′))/τ)\mathcal{L}_q = -\frac{1}{|\mathcal{P}_q^{+}|} \sum_{p \in \mathcal{P}_q^{+}} \log \frac{\exp(\mathrm{sim}(h(q), h(p))/\tau)}{\sum_{p' \in \mathcal{P}_q^{+} \cup \mathcal{P}_q^{-}} \exp(\mathrm{sim}(h(q), h(p'))/\tau)}

Mathlib-to-Blueprint Adaptation (for P3)

  1. Mathlib4 pretraining on abundant typed graph data.
  2. 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 F\mathcal{F} producing a Lean statement q~=F(qnl)\tilde{q} = \mathcal{F}(q_{\mathrm{nl}}), then retrieves Lean-side premises (formalize-then-retrieve).

Empirical Validation / Results

Retrieval Results (K=16)

MethodMathlib4-Random (R)Mathlib4-Heldout (R)DAPS-Collection (R)DAPS-Blueprint (R)
MePo14.147.980.53-
ReProver26.9732.320.7525.37
LeanHammer61.1367.331.9831.36
Qwen3-Embedding-8B11.546.740.2411.02
DAPS66.0178.7413.8442.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)

MethodGoedel-Prover-V2-8B Pass@4DeepSeek-Prover-V2-7B Pass@4
w/o premises49.9048.23
LeanExplore52.3648.72
LeanSearch51.4347.32
Qwen3-Embedding-8B51.8447.68
MePo50.6047.75
ReProver50.0148.66
LeanHammer48.9349.19
DAPS54.0349.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)

ModelLeanExploreLeanSearchQwen3DAPSΔ%
Qwen3-235b18.4517.0119.0821.25+11.37
DeepSeek-V3.111.9612.3813.7513.90+1.09
kimi-k2-instruct8.668.268.279.08+4.85
Gemini-3.6-Flash46.1344.0445.5148.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