# DAPS: Dependency-Aware Premise Selection for LLM Theorem Proving

> DAPS restores dependency structure to premise selection, achieving +11.41 Recall@16 over LeanHammer and a 7× recall margin on rare, out-of-distribution queries.

- **Source:** [arXiv](https://arxiv.org/abs/2610.41536)
- **Published:** 2026-11-21
- **Permalink:** https://picx.dev/p/zuOF6W
- **Whiteboard:** https://picx.dev/p/zuOF6W/image

## Summary

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

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

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

### Structural Neighborhood Encoding (for P1)

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

**Fusion**:

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

$$
\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 $\mathcal{F}$ producing a Lean statement $\tilde{q} = \mathcal{F}(q_{\mathrm{nl}})$, 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.

---

_Markdown view of https://picx.dev/p/zuOF6W, served by PicX — AI-generated visual whiteboard summaries of research papers._
