- 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
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 condition | Solved Basic Set Problems | Solved Advanced Set Problems |
|---|---|---|
| FAILURE MEMORY DISABLED | ||
| No retrieval | 16 | 8 |
| LeanSearch v2 (standard mode) | 16 | 8 |
| LeanGraphSearch (standard mode) | 20 | 10 |
| LeanSearch v2 (reasoning mode) | 18 | 9 |
| LeanGraphSearch (reasoning mode) | 19 | 10 |
| FAILURE MEMORY DISABLED | ||
| No retrieval | 17 | 8 |
| LeanSearch v2 (standard mode) | 16 | 8 |
| LeanGraphSearch (standard mode) | 19 | 9 |
| LeanSearch v2 (reasoning mode) | 17 | 9 |
| LeanGraphSearch (reasoning mode) | 18 | 12 |
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 .” 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 , 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 , where and are the semantic and PPR scores, and 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 convergence tolerance of .
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.
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.
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-8BandQwen/Qwen3-Reranker-8Bcheckpoints 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:
bge-base-en-v1.5, 109MDeepSeek-Prover-V1.5-RL, 7Binfly/inf-retriever-v1-pro, 7BReasonIR-8B, initialized fromLlama3.1-8BLlama3.1-70B-Instruct.Diver-Retriever-4B, initialized fromQwen3-Embedding-4BByT5-smallencoder, approximately 218Mall-distilroberta-v1, 82MWe 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
Recall @ k
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.