Formal theorem proving sits at the intersection of logic, mathematics, and machine learning. In systems like Lean 4, provers must construct machine-checkable proofs by drawing on large formalized libraries of mathematical results. The quality of lemma retrieval directly determines whether a prover can bridge the gap between a theorem statement and the available infrastructure of proven results. Recent retrieval systems match library declarations to a target theorem or its intermediate proof steps, yet they rely predominantly on lexical similarity. This limitation means that declarations which are functionally relevant but lexically distant go undiscovered, particularly when proofs depend on multi-hop chains of intermediate results.
The paper identifies this gap and proposes LeanGraphSearch, a graph-based retrieval method for Lean 4 that exploits forward dependency structures within the Mathlib library. Instead of treating declarations as isolated strings, LeanGraphSearch constructs a graph where each node is a declaration and directed edges point from a declaration to the premises it depends on. A graph-based ranking algorithm then propagates relevance from semantically matched declarations across dependency chains, uncovering supporting lemmas that recur in proofs of related problems but may not share surface-level lexical overlap with the query. After propagation, the expanded candidate set is reranked against the original query to produce a final ranked list.
Evaluation across two mathematical retrieval benchmarks demonstrates the method's effectiveness. On MathlibQR, LeanGraphSearch improves recall by up to 12% over the strongest baseline, LeanSearch v2. On MathlibMPR, it increases coverage of complete annotated proof routes by up to 3.7%, revealing extra groups of related theorems that were previously unretrievable. These gains confirm that multi-hop dependency traversal surfaces lemmas that lexical matching alone cannot reach.
Beyond retrieval, the authors assess whether these improvements translate into tangible progress in end-to-end theorem proving. LeanGraphSearch is integrated into an iterative proving loop guided by Lean feedback. Across three theorem proving benchmarks, the method improves the pass rate at {8, 16, 32} reflection turns by as much as 40% compared to a vanilla prover without retrieval, and by at most 10% compared to LeanSearch v2. The paper emphasizes that these gains come with higher accuracy-cost efficiency, meaning the retrieval-enhanced prover reaches comparable success rates while requiring fewer reflection turns or less compute. The results suggest that dependency-aware search not only finds more relevant lemmas but also helps provers construct proofs more effectively when embedded in a full reasoning loop.
One notable design choice is the use of forward dependencies rather than backward chaining from the theorem goal. Forward dependency graphs capture what each lemma enables for future proofs, and the ranking algorithm propagates relevance downstream from initially matched declarations. This directionality aligns with how human mathematicians often operate: they identify a relevant result and then explore what other theorems it supports. The graph traversal effectively mimics this exploratory pattern, widening the net of discoverable lemmas without increasing the lexical search space.
The paper also acknowledges constraints. The approach relies on the existence of well-structured forward dependency data, which is available in Mathlib but may not generalize to other formal libraries or informal mathematical corpora. The ranking algorithm's performance is contingent on the quality of the initial semantic matching; if the base retriever misidentifies the query's intent, downstream graph propagation cannot recover the correct lemmas. Additionally, the method's computational cost grows with graph size, though the authors note that Mathlib's structure allows efficient traversal with appropriate indexing. The reported 3.7% coverage increase on MathlibMPR, while statistically significant, represents a modest absolute gain, and the authors caution that results may vary on libraries with different dependency patterns.
For practitioners working with formal provers, LeanGraphSearch offers a concrete method for improving lemma retrieval without retraining or redesigning the prover core. The approach can be layered on top of existing retrievers as a post-processing step: run the standard lexical or semantic retriever, propagate relevance through the dependency graph, and rerank the results. Because the method operates at the retrieval layer, it is compatible with a wide range of proving backends and does not require modification to the proof state tracking or tactic selection logic. The paper's release of code and dependency graphs facilitates experimentation and adaptation to other formal libraries.
Lean Graph Search for Formal Theorem Proving contributes a structural perspective to a problem that has largely been addressed through surface-level matching techniques. By treating the library of declarations as a graph and traversing multi-hop dependencies, the method uncovers supporting lemmas that expand the prover's effective context. The retrieval gains are meaningful on their own, and their amplification into pass rate improvements within iterative proving loops demonstrates end-to-end value. The work motivates further research on structure-aware search, not only for theorem proving but for any setting where knowledge organization is captured in dependency or relation graphs.