acceptodds
Under review as a conference paper at ICLR 2027

Lean Graph Search for Formal Theorem Proving

Abstract

Retrieving relevant lemmas is crucial for formal theorem proving, enabling provers to build machine-checkable proofs from established mathematical results. Recent retrieval systems match library declarations to a target theorem or its intermediate proof steps, but make limited use of multi-hop dependencies among declarations. These dependencies can reveal supporting lemmas that are not necessarily lexically similar to the target theorem but recur in proofs of related problems. To this end, we propose LeanGraphSearch, a graph-based retrieval method for Lean 4 that constructs a graph from Mathlib's forward dependencies and traverses it to uncover supporting lemmas through multi-hop dependency chains. Specifically, LeanGraphSearch links each declaration to the premises it depends on, uses a graph-based ranking algorithm to propagate relevance from semantically matched declarations to their dependencies, and reranks the expanded candidates against the original query. Across two mathematical retrieval benchmarks, LeanGraphSearch improves recall by up to 12% over the strongest baseline, LeanSearch v2, on MathlibQR and increases coverage of complete annotated proof routes on MathlibMPR, covering up to 3.7% of extra groups. More importantly, we evaluate whether these retrieval gains translate into improved end-to-end theorem proving by integrating LeanGraphSearch into an iterative proving loop guided by Lean feedback. Across three theorem proving benchmarks, LeanGraphSearch improves pass rate at reflection turns by as much as 40% compared to vanilla prover and at most 10% compared to LeanSearch v2, showing higher accuracy-cost efficiency. These findings highlight the value of dependency graph search for theorem proving and motivate further research on structure-aware search for proof discovery.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Formal Theorem Proving, Premise Retrieval, Graph-Based Retrieval, Retrieval-Augmented Generation, Large Language Models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_3qovOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper argues that lemma retrieval is important for effective automated theorem proving and introduces LeanGraphSearch, a retrieval method that combines semantic search with graph-based expansion and reranking to identify relevant premises. The method starts with semantic retrieval based on a target query, which can consist of an informal mathematical description, a formal statement, a proof state, or a combination of these. It then leverages structural dependencies between premises to expand and rerank the retrieved results, using PageRank to determine edge weights in the dependency graph. The graph is extracted using Jixia, with each node representing a formal statement and its corresponding informal description. The authors report improvements on formal mathematical retrieval benchmarks and an increase of up to 3.7% in end-to-end theorem-proving performance. For the authors, end-to-end theorem proving refers to agentic proof generation with feedback from Lean but does not include formalisation of informal mathematical statements.

Critical strengths
  • The results demonstrate promising performance improvements on Mathlib-related retrieval benchmarks.
  • The integration of hierarchical dependency information into the retrieval process provides an interesting approach to improving premise relevance.
  • The method shows promising performance gains on Mathlib-related agentic theorem-proving tasks.
Critical weaknesses
  • The paper lacks details about the Qwen embedding model and reranker. It is unclear whether the authors use the base checkpoints or models that have been fine-tuned on Lean-specific corpora.
  • The descriptions of the benchmarked methods lack important implementation details, including the specific models, training data and parameter counts.
  • The evaluation lacks ablation studies examining the contributions of the individual retrieval stages, both on retrieval benchmarks and in end-to-end theorem proving. It would be useful to compare semantic retrieval only, semantic retrieval + query-aware propagation and the full LeanGraphSearch pipeline.
  • The evaluation does not examine the impact of the underlying embedding and reranking models. While the authors attribute the improvements on retrieval benchmarks primarily to the proposed graph-based search, they do not demonstrate whether these gains generalize to other model backbones, such as EmbeddingGemma.
  • LeanGraphSearch improves performance for benchmarks including mathlib-related problems. These performance benefits cannot be observed for Lean-IMO-Bench, where the only other benchmarked retrieval method, LeanSearch-v2, performs on par.
Questions for authors
  • What are specific theorems or problems, where other retrieval methods fail?
  • Are there specific examples for lemmas that LeanSearchGraph retrieves and that are absent from other lean search methods?
  • What is the frequency distribution of premises across theorems? Assuming that there are premises that are shared across various theorems: How do you prune the search tree during premise retrieval?
  • How could you integrate dependencies outside of Mathlib, i.e. user-defined lemmas or lemmas from a different Lean library?
4 comments
AuthorsOpenReview ↗

Response to Reviewer 3qov

We thank the reviewer for recognizing the value of dependency information for premise retrieval and the promising results on Mathlib-related tasks. We have addressed the concerns below and have incorporated the clarifications and supporting analyses into the revised manuscript.

1. RE: the Qwen embedding model and reranker

We use the publicly released Qwen/Qwen3-Embedding-8B and Qwen/Qwen3-Reranker-8B checkpoints on huggingface, and didn’t perform any additional fine-tuning on Lean-specific or other formal-mathematics corpora. Both reranking stages use the same checkpoint and score candidates against the original query.

2. RE: baseline implementations

For prior baselines, the original papers and model releases report the following retrieval backbones and training procedures:

RetrieverPublished retrieval backboneReported retrieval training or adaptation
LeanExplorebge-base-en-v1.5, 109MUses the pretrained BGE embedding model to index Lean declarations and their informal descriptions; the paper does not report an additional Lean-specific training stage.
LeanFinderDeepSeek-Prover-V1.5-RL, 7BContrastive training on synthetic user queries, formal/informal statements, and augmented proof states from Mathlib and other Lean repositories, followed by preference alignment using user and LLM feedback.
INF-X-Retrieverinfly/inf-retriever-v1-pro, 7BContinued training of inf-retriever-v1 with long-query adaptation. The specific training corpora and mixture are not disclosed in the official documentation.
ReasonIRReasonIR-8B, initialized from Llama3.1-8BPublic retrieval datasets combined with synthetic reasoning-intensive retrieval data generated using Llama3.1-70B-Instruct.
DIVERDiver-Retriever-4B, initialized from Qwen3-Embedding-4BMathematical, coding, and medical retrieval data with domain-specific negatives; the model card lists RaDeR MATH, ReasonIR, MedQA, and PRGB-ZH.
ReProverByT5-small encoder, approximately 218MPremise-retrieval training on proof-state–premise pairs from LeanDojo’s Mathlib4 training data.
LeanPremiseall-distilroberta-v1, 82MContrastive training on state–premise pairs extracted from Mathlib proofs, with premises drawn from Mathlib, Batteries, and Lean core.
LeanStateSearchPublished BERT retriever, approximately 67MPretraining on formal Mathlib4 text, followed by premise-retrieval training on proof-state–premise pairs.

We have updated the manuscript to include more details about these related works in Appendix A.

3. RE: ablations of the individual retrieval stages

We rerun the experiments of semantic only (LeanSearch v2), semantic + graph, semantic + graph + rerank fusion (LeanGraphSearch) on MathlibQR.

nDCG @ k

kSemantic onlySemantic + GraphSemantic + Graph + fusion
10.4800.4820.531
50.6040.6090.641
100.6270.6320.661

Recall @ k

kSemantic onlySemantic + GraphSemantic + Graph + fusion
100.7780.7940.801
500.8470.8950.900
1000.8580.9330.941

These results demonstrate the contributions of the individual retrieval stages, which have been incorporated into the revision. For the theorem proving task, running a full set of proving benchmarks costs nearly $20k, which is not affordable due to limited budget.

4. RE: dependence on the embedding and reranking backbones

We thank the reviewer for raising this point. Our work focuses on graph-based search. To make the comparison with our strongest baseline LeanSearch v2 as direct as possible, we adopted its experimental setup and used the same embedding and reranking models for both methods. Holding these components fixed helps isolate the effect of the search method under this setup. A promising direction for future work is to develop stronger embedding and reranking models tailored to formal mathematics and evaluate them in both LeanSearch v2 and our method, which is out of the scope of this work.

AuthorsOpenReview ↗

Response to Reviewer 3qov (continued)

5. RE: the results on Lean-IMO-Bench

The two retrievers achieve similar performance on Lean-IMO-Bench in the reported evaluation. We guess this is because under 32 reflection turns with searching tools, both LeanSearch v2 and LeanGraphSearch reach some capability upper bound for Gemini 3.1 Pro. To do better comparison, we rerun the Lean-IMO-Bench experiments under 32 reflections turns with at most 8 searching opportunities, and the result is as follows:

Retrieval conditionSolved Basic Set ProblemsSolved Advanced Set Problems
FAILURE MEMORY DISABLED
No retrieval168
LeanSearch v2 (standard mode)168
LeanGraphSearch (standard mode)2010
LeanSearch v2 (reasoning mode)189
LeanGraphSearch (reasoning mode)1910
FAILURE MEMORY DISABLED
No retrieval178
LeanSearch v2 (standard mode)168
LeanGraphSearch (standard mode)199
LeanSearch v2 (reasoning mode)179
LeanGraphSearch (reasoning mode)1812

The result suggests that LeanGraphSearch is more efficient and could accelerate the discovery of potentially useful declarations, especially with limited reasoning budgets.

6. RE: specific problems and additional retrieved lemmas

We have already introduced some examples in Appendix C, where our method is able to find hidden objects behind constructors or declarations ignored by the baselines. For another concrete example of a premise found through dependency expansion:

In our equal-candidate-pool MathlibQR ablation, consider the query “monotone countably-subadditive set function with μ(∅)=0\mu(\emptyset)=0.” Semantic retrieval identifies MeasureTheory.OuterMeasure.trim as a seed. The implementation of this definition directly references MeasureTheory.OuterMeasure.empty, the lemma stating that an outer measure assigns zero to the empty set. Following this value-reference edge introduces the lemma into the graph-expanded candidate pool. With the fixed rank-fusion weight λ=0.005\lambda=0.005, our method returns it at rank 10, whereas it is absent from the dense baseline’s 200 initial candidates. Both methods retain 200 candidates for final reranking. This example traces an additional query-relevant lemma to a concrete dependency edge from a semantically retrieved construction.

7. RE: premise-frequency distribution and control of the search

We measured premise-sharing frequency directly on the dependency graph used for retrieval. The graph contains 310,579 declarations and 4,528,330 dependency edges. Across all declarations, the most frequently referenced 1% declarations receive 84.50% of all dependency edges. This concentration quantifies shared dependencies in the retrieval graph and provides a rationale for the bounded, degree-penalized candidate selection described below.

For controlling expansion, we control retrieval through bounded candidate selection on the declaration dependency graph. Each declaration has a single graph score, including when it is reached through multiple dependency paths, so shared premises do not create separate branches in an explicit search tree.

After query-conditioned PPR, we retain the top 200 graph candidates and merge them with the semantic candidates. Before the second reranking stage, we filter this union using hi=mm⁡(qi)+mm⁡(pi)−0.05log⁡(1+deg⁡in(i)+deg⁡out(i))h_i = \operatorname{mm}(q_i) + \operatorname{mm}(p_i) -0.05 \log \left( 1 + \deg_{\mathrm{in}} (i) + \deg_{\mathrm{out}} (i) \right), where qiq_i and pip_i are the semantic and PPR scores, and mm⁡\operatorname{mm} denotes min–max normalization over the candidate union. The degree penalty softly downweights highly connected declarations while allowing frequently shared premises to remain when their query relevance supports their inclusion.

In proving-time retrieval, this prefilter retains at most 100 candidates for reranking against the original query, after which the combined semantic and PPR score selects at most 50 returned declarations. PPR computation is also bounded by a maximum of 50 iterations, with earlier termination at an ℓ1\ell_1 convergence tolerance of 10−610^{-6}.

8. RE: user-defined lemmas and other Lean libraries

The retrieval formulation can be extended to another Lean library by extracting its declarations and available dependencies, adding their semantic representations to the index, and running retrieval over the combined graph. A proved user-defined lemma can then become a retrieval candidate or a seed for further expansion. This requires compatible Lean and library versions and consistent declaration identifiers.

Since Mathlib is the largest, most widely used formal-math basic library, there is quite a little probability that other user-defined libraries will share some foundational declarations in Mathlib, and therefore will become part of our whole graph.

Thank you for the detailed response. While I believe the additional experiments and updated paper substantially improved the quality of the work, I remain concerned that the method provides improvements beyond Mathlib-centered benchmarks. I therefore believe my previous score remains appropriate.

AuthorsOpenReview ↗

Clarification of Mathlib Setting

Thank you for the follow-up and for your positive assessment. We would like to clarify the practical scope of the Mathlib setting.

Mathlib is the de facto standard mathematical infrastructure for Lean 4, providing shared declarations across most of the basic math fields. Independent projects such as Fermat’s Last Theorem build on it, so proving new results still requires Mathlib premises.

Our evaluation also includes independently sourced problems: FATE-H draws its algebra problems from human-written literatures, and our gains there show benefits when Mathlib is the underlying library, rather than a centric one.

Extending the approach to other formal libraries is a natural direction for future work. This paper contributes improved premise retrieval and proof construction within the shared infrastructure used by many Lean 4 projects.

Reviewer_p9uCOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper argues that Mathlib retrievers miss useful premises that are lexically dissimilar to the query, and proposes LeanGraphSearch, a training-free retrieval layer over Mathlib's forward dependency graph (310,579 declarations and 4.5M edges extracted with jixia). For a query, a Qwen3-Embedding-8B plus Qwen3-Reranker-8B pipeline first selects 50 semantic seeds. Personalized PageRank (restart 0.15) is run from the normalized seed scores, and the top 200 PPR candidates are merged with the seeds through a degree-penalized prefilter. The merged pool is reranked a second time, and the final score adds a small z-scored PPR term (weight 0.005). The authors evaluate standalone retrieval and theorem proving. On the 810-query MathlibQR fair subset, Recall@100 rises from 0.827 to 0.947 and Recall@50 from 0.821 to 0.899 over LeanSearch v2 (standard mode); nDCG@1 stays flat (0.472 vs 0.473).

Critical strengths
  1. The proving evaluation is carefully controlled and consistent in standard mode. Both retrievers return the same top-50 output per query, prompts and budgets are fixed across conditions, cost accounting includes failed problems, and a proof-hole integrity check guards against statement tampering. This is the most convincing evidence that better retrieval translates into proof success at no extra cost.

  2. The method is simple, needs no training, and plugs into existing pipelines. It improves deep recall on MathlibQR by 12.0 points at k=100 and complete-route coverage on MathlibMPR at every cutoff.

Critical weaknesses
  1. The methodological delta is thin and the source of the gain is not isolated. Seeding personalized PageRank from dense-retrieval hits follows HippoRAG, LeanExplore already uses dependency PageRank, and the graph is the one released with LeanSearch v2 (Appendix B.1). The paper has no ablation. Since the PPR weight in the final score is only 0.005 and nDCG@1 is unchanged, the Recall@50/100 gains may simply come from reranking a larger candidate pool rather than from multi-hop dependencies (see Question 1).

  2. The proving gains are small and statistically fragile. Each configuration is a single run with one prover backbone, and many differences are one to three problems. Without failure memory, reasoning-mode LeanGraphSearch solves fewer problems than LeanSearch v2 (143 vs 145 of 210), so the claim of the highest total holds only with memory (151 vs 142). The decoding setup is also inconsistent (temperature zero in Appendix B.4, provider default in Appendix D.2).

Questions for authors

The following clarifications could change my assessment.

  1. What retrieval quality does LeanSearch v2 reach when it reranks a candidate pool of the same size as LeanGraphSearch's merged pool? Is any ablation available (no PPR, random or one-hop expansion, no degree penalty, different r or N)?

  2. Were the proving runs decoded at temperature zero (B.4) or at the provider default (D.2)? Can you report repeated runs, or paired per-problem tests, for at least FATE-H and MathlibMPR-Prop?

  3. Why do LeanSearch v2's Recall@50 and Recall@100 on MathlibQR (0.821 and 0.827) fall below LeanFinder (0.824 and 0.875)? Is this caused by the 200-candidate dense pool used before reranking, and does the same cap apply to LeanGraphSearch?

  4. Does the graph include proof-body references in the reported runs, and how does excluding them change the results?

4 comments
AuthorsOpenReview ↗

Response to Reviewer p9uC

We thank the reviewer for the careful assessment of the proving setup and the improvements in retrieval coverage. The questions about candidate-pool size, component ablations, and run-to-run variation are particularly helpful for identifying the source and reliability of the gains.

1. RE: reranking an equally sized candidate pool and component ablations

To mitigate the reranking size concern, we rerun the MathlibQR experiments under the same 200 candidate pool size, with semantic only (LeanSearch v2), one-hop graph expansion, PPR graph expansion and full LeanGraphSearch pipeline.

nDCG @ k

kSemanticOne-hopPPRFull
10.4800.4800.4820.531
50.6040.6060.6090.641
100.6270.6290.6320.661

Recall @ k

kSemanticOne-hopPPRFull
100.7780.7880.7940.801
500.8470.8890.8950.900
1000.8580.9240.9330.941

These results further verified the effectiveness of our method. We have updated the manuscript to include the equal-candidate results.

2. RE: decoding settings

Both of Claude Sonnet 5 and Gemini 3.1 Pro do not support specific temperatures under reasoning mode, and the temperature will be set by default. The “zero temperature” described in Appendix B.4 is a typo which has been fixed.

3. RE: statistical reliability and questions about failure memory

For the reliability of the proving comparison, we rerun the full set of experiments of FATE-H and MathlibMPR-Prop for the second time. The result is as follows:

FATE-H Experiment

Retrieval conditionpass@8pass@16pass@32Relative Cost
FAILURE MEMORY DISABLED
No retrieval3339481.00x
LeanSearch v2 (standard mode)4863681.10x
LeanGraphSearch (standard mode)5668711.10x
LeanSearch v2 (reasoning mode)5268741.41x
LeanGraphSearch (reasoning mode)5669761.36x
FAILURE MEMORY ENABLED
No retrieval3345521.00x
LeanSearch v2 (standard mode)5363711.01x
LeanGraphSearch (standard mode)5366731.02x
LeanSearch v2 (reasoning mode)5465731.31x
LeanGraphSearch (reasoning mode)5876811.20x

MathlibMPR-Prop Experiment

Retrieval conditionpass@8pass@16pass@32Relative Cost
FAILURE MEMORY DISABLED
No retrieval1519231.00x
LeanSearch v2 (standard mode)3136390.82x
LeanGraphSearch (standard mode)3238410.77x
LeanSearch v2 (reasoning mode)3237411.02x
LeanGraphSearch (reasoning mode)3337401.08x
FAILURE MEMORY ENABLED
No retrieval1519231.00x
LeanSearch v2 (standard mode)3335390.77x
LeanGraphSearch (standard mode)3537410.78x
LeanSearch v2 (reasoning mode)3336400.99x
LeanGraphSearch (reasoning mode)3038410.95x

We found that the variance is relatively small. Since the cost of each full-set running is nearly $20k with 5-6 days, a large number of runs is not affordable.

For the failure memory settings related to the reasoning mode, we basically run the reasoning mode of LeanGraphSearch to compare it with LeanSearch v2 more completely. However, our analysis shows that as LeanGraphSearch already provides deeper hidden theorems and the frontier backbone LLMs are relatively strong, the role of another independent model reasoning is not so important and may even confuse the prover, as the information provided by graph-aware searching could be more accurate and consistent. Therefore, the reasoning mode of our method could fail to beat LeanSearch v2 sometimes.

4. RE: proof-body references

In our current setting, we do not use proof-body value references in both retrieval and proving experiments. We have clarified this in our revision.

Thank you for the additional experiments. The equal-pool ablation and the second proving run are helpful. They also raise three questions that I would like the authors to clarify.

  1. In Table 1, nDCG@1 is almost the same for LeanSearch v2 and LeanGraphSearch (0.472 vs 0.473). In the new ablation, it is 0.480 for semantic retrieval vs 0.531 for the full method. Why do the two results differ?

  2. In the new ablation, one-hop expansion already raises Recall@100 from 0.858 to 0.924, and PPR reaches 0.933. Most of the gain therefore seems to come from adding the direct dependencies of the seeds to the candidate pool, rather than from multi-hop propagation, which the paper presents as its key idea. Could you discuss this?

  3. The reported runs exclude theorem proof-body references, but the paper motivates the method with lemmas used in proofs of related problems. How do the results change when proof-body references are included?

AuthorsOpenReview ↗

2nd Response to Reviewer p9uC

We thank the reviewer for valuing our additional experiments. We provide the requested clarifications below.

1. RE: Different results in the MathlibQR table

We thank the reviewer for carefully checking the MathlibQR results. During the revision, following the request of AKWq to add the Claude Sonnet 4.5 experiments, results from two experimental configurations were combined in the same table entry. Specifically, the previous entries also drew on an auxiliary run with a candidate pool size of 100. We are grateful to the reviewer for catching this inconsistency and we have updated Table 1 accordingly.

2. RE: On the necessity of multi-hop

In our motivation, we do not regard multi-hop/PPR propagation as the sole contributor to retrieval, but rather as an additional exploration mechanism that can help find more deeply hidden declarations. Many real-world math problems may require only shallow exploration, such as one-hop retrieval or even direct retrieval; a small number of hard problems may require deeper exploration, which can only be reached through multi-hop routes. Because only a relatively small number of problems require multi-hop, its contribution may appear limited, but its role cannot be ignored, especially for harder problems such as open research problems.

3. RE: Proof-body references

In our preliminary retrieval experiments, we found that including all proof-body value references would generate a graph 3–4× larger and affect computation efficiency. Therefore, we used the same graph as that used for LeanSearch v2 corpus generation. However, we agree with the reviewer that introducing proof-body references would have some advantages over the current method, and this is part of our future work. We thank the reviewer for this helpful suggestion.

In actual retrieval, declarations may also contain value references, which act like lemmas in proof bodies; these also helped LeanGraphSearch.

Thank you for the clarifications. I will keep my rating at 3.

Reviewer_AKWqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

Mathlib is a huge library to support Math in Lean. So efficiently retrieving the relevant lemmas for a theorem from a natural-language or formal query is an important problem. The paper proposes LeanGraphSearch, a graph-based premise retrieval method for Lean 4 and Mathlib. Nodes are Mathlib declarations (definitions, theorems, type classes, instances, etc.). Edges are extracted by static analysis. An edge i -> j means that declaration i uses declaration j. In other words, j is referenced in the type of i (its statement) or in its value (its proof or definition body).

This lets retrieval start from seed declarations and traverse to the statements they are built on. The seeds are the top-K declarations for the query (a natural language or formal description of a proof hole), retrieved by a Qwen3 embedding model and reranked by a Qwen3 reranker, identical to LeanSearch-v2. The main idea is that those underlying statements can also be useful for proving the target (the proof hole), even when they are not lexically or semantically similar to the query.

The method has three steps:

  1. Retrieve semantic seed declarations with an embedding retriever and a reranker (the LeanSearch-v2 pipeline).
  2. Run personalized PageRank (PPR) from the seeds: random walks follow dependency edges and intermittently restart at one of the seeds. The top-N declarations by PPR score are added as expansion candidates.
  3. Merge the seeds and the expanded candidates, rerank them against the original query, and combine the reranker score with the z-scored PPR score.

Validation covers two retrieval benchmarks (MathlibQR and MathlibMPR) and three theorem-proving benchmarks (FATE-H, MathlibMPR-Prop, Lean-IMO-Bench), where retrieval is plugged into an iterative prover loop with Lean feedback and evaluated at 8, 16 and 32 reflection turns. One reflection turn is one round of the prover loop, it revises its proof using Lean's feedback on the previous attempt, and issue one retrieval query for the next turn.

The paper also adds an optional failure-memory component to the prover loop, which records recurring Lean errors for each problem and tells the prover to try a different proof instead of repeating the same failed one. The main results are 12.0% increase in Recall@100 over LeanSearch-v2 on 3.7% increase in correct declaration coverage in MathlibQR without agentic reasoning.

Critical strengths
  1. The abstract is clear and motivates the rest of the paper, and the paper is easy to follow. The problem formulation in Sec. 3.1 is easy to follow.
  2. The closest prior retrievers (LeanExplore, LeanFinder, LeanSearch-v2) do not use multi-hop dependency reasoning at retrieval time. Leveraging the dependency of Lean declarations in a graph structure to assist declarations retrieval from huge library in Mathlib is a well-motivated idea.
  3. The method improves the number of solved problems on FATE-H: the best setting solves 11% more problem than LeanSearch-v2.
Critical weaknesses
  1. Contamination guarantee is not preserved when the backbones change. Gao et al. built MathlibMPR from merged Mathlib PRs, all merged more than six months after the knowledge cutoff of their prover model (Claude Sonnet 4.5), "ensuring no data contamination" (Gao et al., p. 15; they also say the PRs "postdate the corpora of all search engines compared"). This paper switches to newer models (Claude Sonnet 5) to decompose theorem into detail queries in Reasoning Mode before retrieve relevant declaration. Claude Sonnet 5 whose knowledge cutoffs may be later than those PRs, so the contamination-free guarantee may no longer hold. This is a significant design issue. It may also be why Table 4 (MathlibMPR-Prop) shows no clear advantage for graph augmentation: without failure memory, LeanSearch-v2 in reasoning mode solves more problems at pass@32 than LeanGraphSearch in reasoning mode (41 vs. 39).

Here is the verbatim quote from Gao et. al. design choice:

MathlibMPR contains 69 mathematical problems extracted from merged Mathlib pull requests.

formalization experts selected merged PRs that postdate the corpora of all search engines compared in our experiments

All selected PRs were merged more than six months after the knowledge cutoff of the prover model used in our experiments (Claude Sonnet 4.5, Section 4.3), ensuring no data contamination.

  1. Baselines are not run under the same models. The baselines are quoted from Gao et al. (Sonnet 4.5), while only LeanSearch-v2 and LeanGraphSearch are rerun with the newer models (Sonnet 5). Changing the backbone increases LeanSearch-v2 (reasoning) by up to about 5% relative to Gao's result. Also, the paper gives no reason for the change of reasoning models.

  2. The gain is large only in one setting. In Tab. 1, LeanGraphSearch is similar to LeanSearch-v2 at small cutoffs, e.g., Recall@10 (+2.9 pp). The gain is also marginal in nDCG. The gain is large only in k=50k=50 or k=100k=100 in recall, which is on one-third of the result.

  3. Minor q~i\tilde q_i and zscorequery(⋅)\mathrm{zscore}_{\text{query}}(\cdot) are not introduced near Eq. (3), which hinders the flow of reading. The z-score normalization is only partly described in Appendix B.1. Similarly, the paper does not describe how PP in Eq. (2) is constructed.

Questions for authors
  • Q1: In general the writing is clear and easy to follow, but Fig. 1 is hard to understand and not described well enough. What is the output of the retrieval in Fig. 1a? What is the role of d3 and d4, and why are they different from d1 and d2? Could you give a concrete toy example of a dependency graph for a specific theorem, to improve readability and intuition?

  • Q2: How is P in Eq. (2) built? It is called row-stochastic, but dangling nodes have empty rows. Please define the adjacency matrix, the out-degree, the set D and P explicitly, and state whether the unit edge weights in Appendix B.1 mean a uniform split over out-neighbours.

  • Q3: How do you tune λ\lambda in Eq. (3)?

  • Q4: The baselines are quoted from Gao et al. (Sonnet 4.5, Kimi K2), while only LeanSearch-v2 and LeanGraphSearch use the newer models (Claude Sonnet 5). Is this fair to LeanExplore, LeanFinder and the other agentic baselines? Could you explain why you evaluate on newer models Claude Sonnet 5 instead of reusing Gao's Claude Sonnet 4.5 and Kimi K2? Can you rerun LeanSearch-v2 and LeanGraphSearch on the older model (Sonnet 4.5, Kimi K2) to ensure the integrity of the comparison?

4 comments
AuthorsOpenReview ↗

Response to Reviewer AKWq

We thank the reviewer for recognizing the motivation for dependency-based retrieval and the improvements on theorem proving benchmarks. We have addressed the concerns below and have incorporated the clarifications and supporting analyses into the revised manuscript.

1. RE: “Contamination guarantee is not preserved when the backbones change” and “Baselines are not run under the same models”

Our preliminary results show that Claude Sonnet 4.5 has relatively poor capability on formal math problem reasoning. We therefore switched to Sonnet 5, the frontier Sonnet model at that time, to test stronger reasoning mode on the latest backbone. Given our limited budget, we only used Claude Sonnet 5 to conduct a head-to-head comparison with the strongest baseline LeanSearch v2.

To mitigate the contamination concern, we therefore use Claude Sonnet 4.5 and Kimi K2 to rerun the reasoning-mode experiments on MathlibMPR for the integrity of the comparison. The results are as follows:

kLeanSearch RecallGraph RecallLeanSearch CoveredGraph Covered
538.05%41.77%26.09%28.99%
1047.76%47.48%36.23%33.33%
2053.36%55.95%40.58%40.58%
3055.84%57.80%40.58%42.03%
5058.68%60.46%43.48%47.83%
10060.01%61.18%46.38%49.28%

These results further support our conclusions and confirmed no contamination issue. We have included the Sonnet 4.5 / Kimi K2 results into our revision.

2. RE: “The gain is large only in one setting”

The strongest improvement in Table 1 is in recall at larger cutoffs, while the changes in early-rank metrics are relatively smaller. Our analysis suggests that LeanGraphSearch primarily improves the candidate discovery, which is consistent with our manuscript. While the best baselines like LeanSearch v2 already have good performances on finding the best-matched several theorems, our method can reach deeper hidden ones through graph expansion.

3. RE: the construction of P and the definitions near Eq. (3)

We agree that the transition matrix and score normalization should be defined where they are first used and appreciate the questions about dangling nodes. Our implementation stores a row-normalized dependency matrix with zero rows for dangling nodes and redistributes their probability mass explicitly through the last term of Eq. (2). For the dependency-only graph, define Aij=1[(i,j)∈E]A_{ij} = \mathbf{1} [(i,j) \in E], where i→ji \to j means that declaration ii references declaration jj. Self-references and duplicate targets are removed during graph construction. The out-degree and dangling-node set are diout=∑jAijd_i^{\mathrm{out}}=\sum_j A_{ij} and D=iout=0D={i^{\mathrm{out}}=0}.

Thus, the unit edge weights specified in Appendix B.1 give a uniform split over each node’s distinct outgoing neighbours. With dangling rows left at zero, PP is row-substochastic.

For query-specific z-score normalization, Let CC be the candidate set retained after prefiltering and before the final top-KK selection. For the current query, we compute μC=1∣C∣∑j∈Cpj,σC=std⁡(pj∈C)\mu_C=\frac{1}{|C|}\sum_{j\in C}p_j, \sigma_C=\operatorname{std}\bigl({p_j\in C}\bigr), and define zscore⁡query(pi)=(pi−μC)/σC if σC>0 otherwise 0\operatorname{zscore}_{\mathrm{query}}(p_i)= (p_i-\mu_C)/\sigma_C \text{ if } \sigma_C>0 \text{ otherwise } 0. Both statistics are computed over the same retained candidate set (C).

We thank the reviewer for pointing this out and have updated the manuscript to include these definitions next to Eqs. (2) and (3), so that the transition probabilities and normalization can be reproduced directly from the main text.

4. RE: “How do you tune lambda in Eq. (3)?”

We tuned the coefficient λ\lambda using a simple search on a small set of prior Mathlib PRs. We searched λ∈{0.001,0.003,0.005,0.008,0.01,0.03,0.05,0.08,0.1,0.3,0.5,0.8}\lambda \in \{ 0.001, 0.003, 0.005, 0.008, 0.01, 0.03, 0.05, 0.08, 0.1, 0.3, 0.5, 0.8 \} and chose λ=0.005\lambda = 0.005 for the best performance. The problem set for tuning does not contain any benchmark problems, and the same setting is applied across all the experiments.

AuthorsOpenReview ↗

Response to Reviewer AKWq (continued)

5. RE: Figure 1 and a concrete dependency-graph example

The roles of the declarations and the retrieval output are:

The input qq describes the target theorem or proof goal. The blue nodes d1,d2d_1,d_2 are semantic seeds selected by embedding retrieval and first-stage reranking; the dashed arrows indicate query matching. Solid arrows represent formal dependencies, directed from a declaration to another declaration referenced in its type or proof/definition body. The green nodes highlight supporting premises discovered through these dependencies: ℓ1\ell_1 is shared by both seeds, while ℓ2\ell_2 is reached through the two-hop paths d1/d2→ℓ1→ℓ2d_1/d_2\rightarrow\ell_1\rightarrow\ell_2.

The gray nodes d3,d4d_3,d_4 are other declarations reached through ℓ1→d3\ell_1\rightarrow d_3 and d2→d4d_2\rightarrow d_4. Figure 1(a) illustrates candidate discovery; the final retrieval output is the ranked list R(q)R(q) defined in Section 3.3. We merge the semantic seeds with the PPR-selected candidates, apply candidate refinement and second-stage reranking, and return up to KK declarations according to the combined relevance and graph score. Both seeds and expanded declarations can appear in this output. For a concrete example:

Consider the target y<x⇒0<(x−y)2y<x\Rightarrow 0<(x-y)^2 over the reals and a toy library containing:

  • d1:;0<a∧0<b⇒0<(a+b)2d_1:; 0<a \land 0<b \Rightarrow 0 < (a+b)^2.
  • d2:;0<a⇒0<(a+1)2d_2:; 0<a \Rightarrow 0 < (a+1)^2.
  • ℓ1:;0<t⇒0<t2\ell_1:; 0<t \Rightarrow 0<t^2.
  • ℓ2:;0<u∧0<v⇒0<uv\ell_2:; 0<u \land 0<v \Rightarrow 0<uv.

Choose proofs of d1d_1 and d2d_2 that invoke ℓ1\ell_1, and prove ℓ1\ell_1 by rewriting t2=t⋅tt^2 = t \cdot t and invoking ℓ2\ell_2. These proof bodies give the dependency edges d1→ℓ1d_1 \rightarrow \ell_1, d2→ℓ1d_2 \rightarrow \ell_1, and ℓ1→ℓ2\ell_1 \rightarrow \ell_2. The additional branches can represent d3d_3, the square-to-product identity used by ℓ1\ell_1, and d4d_4, the fact 0<10<1 used to establish positivity of a+1a+1 in d2d_2.

Suppose semantic retrieval selects d1,d2d_1, d_2. Graph propagation then exposes the shared helper ℓ1\ell_1 and the deeper product-positivity lemma ℓ2\ell_2 for final reranking. Returning ℓ1\ell_1 provides a directly applicable premise: y<xy<x gives 0<x−y0<x-y, and instantiating ℓ1\ell_1 with t=x−yt = x-y proves the target.

We have revised the figure and caption to distinguish semantic seeds, graph expansion, and the final returned premises, and added an explicit output box for R(q)R(q).

Thanks for the response.

1: Contamination guarantee is not preserved when backbone change

Thanks for clarifying the reason for choosing Sonnet 5 over Sonnet 4.5. However, looking at the experimental results, Sonnet 4.5's performance appears largely on par with Sonnet 5:

| Backbone | Recall@5 | Recall@50 | Covered@50 |
|---|---|---|---|
| Gemini 3.1 Pro and Sonnet 5 | 36.4 $\\rightarrow$ 37.9 (+1.5) | 58.2 $
\\rightarrow$ 58.3 (+0.1) | 41.3 $\\rightarrow$ 44.2 (+2.9) |
| Sonnet 4.5 and Kimi K2 | 38.05 $\\rightarrow$ 41.77 (+3.7) | 58.68 $\\
rightarrow$ 60.46 (+1.8) | 43.48 $\\rightarrow$ 47.83 (+4.3) |

These numbers support my initial thought that under the suggested configuration (Sonnet 4.5 and Kimi K2), LeanGraphSearch has noticeably stronger gains compared to the original setup with Sonnet 5 (3.7% vs. 1.5% in Recall@5).

This aligns with my concern that Sonnet 5 suffers from benchmark contamination, and may enable retrieval from memory without relying on graph-based search. Given these, I believe the contamination concern is plausible, and reporting the evaluation using Sonnet 4.5 is sufficient for the revised version of the paper.

2: Baselines are not run under the same models

As shown above, evaluating under uncontaminated models like previous baselines does not yield significantly worse performance compared to potentially contaminated models. I appreciate the additional exps, and I recommend using the Sonnet 4.5 and Kimi K2 config for the rest of experiments.

3: The gain is large only at large cutoffs (k=50 and k=100)

The response agrees with my observation that the gain is concentrated at large cutoffs (Recall@50: 7.8%, Recall@100: 12.0% in Tab. 1), while the gain at small cutoffs is much smaller (Recall@10: 2.9%). However, the end-to-end agentic proving experiments use only K = 50 declarations per query, so the largest gain is not used downstream. I suggest evaluating the agentic proving loop with a larger retrieval budget K (e.g., 100 or more), to show that the large-cutoff gain of the proposed graph search translates into end-to-end proving, which is the more practical use.

AuthorsOpenReview ↗

2nd Response to Reviewer AKWq

We thank the reviewer for pointing out that using Sonnet 4.5 is sufficient, and we have replaced the previous MathlibMPR results with the updated ones. For MathlibQR, since the standard mode of both methods does not involve LLM assistants, the results were not affected.

We address the remaining concerns below.

1. RE: “using the Sonnet 4.5 and Kimi K2 config for the rest of experiments”

For the prior baselines, the original papers and model release documentations report the following retrieval backbones and training procedures:

RetrieverPublished retrieval backboneReported retrieval training or adaptation
LeanExplorebge-base-en-v1.5, 109MUses the pretrained BGE embedding model to index Lean declarations and their informal descriptions; the paper does not report an additional Lean-specific training stage.
LeanFinderDeepSeek-Prover-V1.5-RL, 7BContrastive training on synthetic user queries, formal/informal statements, and augmented proof states from Mathlib and other Lean repositories, followed by preference alignment using user and LLM feedback.
INF-X-Retrieverinfly/inf-retriever-v1-pro, 7BContinued training of inf-retriever-v1 with long-query adaptation. The specific training corpora and mixture are not disclosed in the official documentation.
ReasonIRReasonIR-8B, initialized from Llama3.1-8BPublic retrieval datasets combined with synthetic reasoning-intensive retrieval data generated using Llama3.1-70B-Instruct.
DIVERDiver-Retriever-4B, initialized from Qwen3-Embedding-4BMathematical, coding, and medical retrieval data with domain-specific negatives; the model card lists RaDeR MATH, ReasonIR, MedQA, and PRGB-ZH.
ReProverByT5-small encoder, approximately 218MPremise-retrieval training on proof-state–premise pairs from LeanDojo’s Mathlib4 training data.
LeanPremiseall-distilroberta-v1, 82MContrastive training on state–premise pairs extracted from Mathlib proofs, with premises drawn from Mathlib, Batteries, and Lean core.
LeanStateSearchPublished BERT retriever, approximately 67MPretraining on formal Mathlib4 text, followed by premise-retrieval training on proof-state–premise pairs.

All baselines use their own retrieval models and do not rely on external LLM APIs; therefore, their results are independent of the assistant LLM configuration.

For the theorem proving benchmarks, we use Gemini 3.1 Pro in reasoning mode as the assistant model, and its knowledge cutoff is January 2025, which predates the release of lean4.28.0-rc1. Therefore, the results should not be affected by the contamination problems.

2. RE: “the largest gain is not used downstream”

We have started running the full suite of theorem proving experiments. Given that we are currently in the rebuttal phase, we are presenting the results available thus far, with further results to follow.

MathlibMPR-Prop

Retrieval Conditionpass@8pass@16pass@32
Failure Memory Disabled
LeanSearch v2 (Standard Mode)343640
LeanGraphSearch (Standard Mode)363941
LeanSearch v2 (Reasoning Mode)353741
LeanGraphSearch (Reasoning Mode)353839
Failure Memory Enabled
LeanSearch v2 (Standard Mode)313740
LeanGraphSearch (Standard Mode)343741
LeanSearch v2 (Reasoning Mode)333840
LeanGraphSearch (Reasoning Mode)323742

The results suggest that the advantage may be partly diminished in multiple turns of reasoning and searching, e.g., at pass@32. However, we still agree with the reviewer that using K=100K=100 may better reveal the advantage of our method, especially under a limited budget, and we will add the full K=100K=100 results to our manuscript once the experiments are complete.

Comments on the paper

2 comments

Dear Reviewers,

The authors have responded to your comments. Could you please review their responses and update your reviews?

AuthorsOpenReview ↗

Summary of Rebuttal and Discussion

Dear SACs and ACs,

Thank you for handling our submission, Lean Graph Search for Formal Theorem Proving (#5773). We also sincerely appreciate the reviewers’ detailed feedback.

As reviewer AKWq requested, we reran LeanSearch v2 and LeanGraphSearch using Sonnet 4.5 and Kimi K2 and replaced the corresponding results in the revision, as well as started implementing K=100K = 100 into the proving tasks. We also revised our equations and presentations. However, reviewer AKWq remained unresponsive thereafter.

To address reviewer p9uC's concern about the contribution of dependency-graph, we added ablations to identify both the sufficiency of using graph-aware search and the contribution of multi-hop exploration in hard tasks. The ablations and new results are included in the revision. We also completed a second proving run on FATE-H and MathlibMPR-Prop, whose results support the downstream benefit of graph retrieval again. Reviewer p9uC found the equal-pool ablation and second proving run helpful and, following the subsequent clarifications, maintained a rating of 3.

For reviewer 3qov, we added details of the implementation designs that contained in appendix. We also provided extra concrete retrieval example to illustrate the advantage of our method. To examine the similar results on Lean-IMO-Bench more closely, we added an evaluation with 32 reflection turns and at most 8 retrieval calls, where our method shows greater advantage on limited budget. We also clarified the foundational role of Mathlib and our scope of evaluation. Despite our clarification, reviewer 3qov retained a rating of 2 and a concern about generalization on Mathlib-unrelated benchmarks, which is rare in fact.

We would like to re-emphasize the contributions of this paper:

  • We propose a dependency-aware retrieval framework for Lean 4, allowing retrieval to move beyond direct query matching and recover supporting lemmas that are not lexically similar to the query but recur in related proofs.

  • Our method shows advantage in comprehensive evaluation on both retrieval and end-to-end proving. On MathlibQR, it improves Recall@100 from 82.7% to 94.7%, while on MathlibMPR it improves coverage of complete annotated proof routes by up to +4.3 percentage points. More importantly, when integrated into an iterative proving loop, it improves pass rates at {8, 16, 32} reflection turns by as much as 40% over the vanilla prover and at most 10% over LeanSearch v2 across FATE-H, MathlibMPR-Prop, and Lean-IMO-Bench, showing a better accuracy-cost tradeoff.

  • As mentioned by reviewers, our work introduces dependency-graph as a critical structure in the searching process, which matches the underlying logic of math and lays a possible foundation for the community.

We again genuinely thank all the reviewers and ACs for their efforts and time in reviewing our paper, as well as their constructive suggestions that contribute to the improvement to our paper.

We sincerely hope you will take the above into consideration. Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.