- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper argues that premise retrieval is essential for theorem proving. The authors claim that existing retrieval methods primarily rely on direct matching with natural language queries or local proof states, while overlooking structural relationships and dependencies within premise libraries. However, prior work by Liu et al. 2025 and Petrovcic et al. 2025 has already incorporated structural hierarchy into retriever training. The authors propose GARNET, a graph-augmented reranking method that uses structural information from premise dependencies. The method uses two separate encoders: one for the natural language proof-intent query q and another for the current proof state s. Premises are retrieved independently for the query and proof state, and the resulting sets are combined and deduplicated before reranking. The authors report a 20% improvement on retrieval benchmarks and claim state-of-the-art performance in end-to-end theorem proving using GPT-5.6 as a base model.
Critical strengths
- The paper provides useful ablation studies examining the individual contributions of natural language queries and proof states as retrieval contexts.
- The method demonstrates promising performance improvements in both premise retrieval and end-to-end theorem proving.
- The proposed gating mechanism is an interesting approach to incorporating graph dependencies into premise retrieval.
- The authors suggest that the method could be extended to incorporate additional techniques, i.e. query decomposition and reasoning modes from LeanSearch-v2.
Critical weaknesses
- The evaluation lacks a baseline measuring the end-to-end theorem-proving performance of GPT-5.6 without any retrieval method.
- The ablation study in Appendix G suggests that graph information improves retrieval performance but is not the primary factor behind GARNET's improvements over existing methods. The performance of the “w/o graph branch” variant raises the question of which components primarily drive the improvements over LeanSearch and LeanFinder.
- The paper lacks a qualitative analysis of the retrieved premises and their impact on theorem proving. It remains unclear which types of premises GARNET retrieves more effectively than existing methods and how these improvements translate into better end-to-end theorem-proving performance.
- The authors describe premises used by a retrieved theorem as “missed” premises. However, these direct (1-hop) dependencies are already included in the formal statement or proof of the retrieved theorem and are therefore available in the prover's context. The premises that may actually be missed are indirect (2-hop) dependencies, i.e., dependencies of the retrieved theorem's direct dependencies.
- The retrievers are both trained and evaluated on Mathlib data. The experimental results do not include other libraries or user-defined code.
Questions for authors
- How does GARNET avoid over-retrieving frequently used premises?
- How could GARNET be extended to other mathematical libraries and user-specific definitions?
- Which retrieval context contributes more to GARNET's performance: natural language queries or the current proof state?
- How does GARNET handle cycles in the Mathlib dependency graph?
- What is the distribution of gating scores in GARNET? Do these scores vary across different types of mathematical problems or fields?
- Why do both the query-only and state-only variants of GARNET outperform LeanFinder and LeanSearch? What are the main factors driving these improvements?
6 comments
W3. Which types of premises does GARNET retrieve more effectively than existing methods, and how do these improvements translate into better end-to-end theorem-proving performance?
Thank you for suggesting this qualitative analysis. To illustrate how retrieved premises contribute to theorem proving, we examined two cases in which GARNET retrieves auxiliary lemmas that are subsequently used in Lean-verified proofs.
In Rudin 5.7, the proof requires rewriting a quotient of function values in terms of slopes on a punctured neighborhood. The query-conditioned retrieval identifies slope_def_field, which supports the algebraic rewriting, while proof-state-conditioned retrieval identifies self_mem_nhdsWithin, a neighborhood lemma used to establish the necessary eventual condition t ≠ x. Both premises are returned in a single M11 retrieval call and used in the immediately following Lean-verified proof proposal.
For the same theorem, LeanFinder retrieves slope-related lemmas, while State-ByT5 retrieves neighborhood/filter-related lemmas in their respective trajectories. This illustrates the complementary roles of the two retrieval contexts: the natural-language query captures the intended mathematical transformation, while the proof state provides information about the local conditions required to carry it out. GARNET combines both types of evidence within a single retrieval call.
In Herstein 2.3.16, graph expansion retrieves Nat.finite_of_card_ne_zero and Nat.card_eq_fintype_card, neither of which appears in direct query retrieval. The former is used to discharge a finiteness side condition, while the latter supports rewriting the cardinality expression. Both are used in the next Lean-verified proof, illustrating how dependency expansion can surface auxiliary premises needed to apply a directly retrieved theorem.
W4. Concern that direct (1-hop) dependencies are already included in the retrieved theorem's statement or proof.
We appreciate the reviewer's question and would like to clarify what we mean by "missed" premises.
Although a theorem's dependencies are available within Mathlib, retrieving the theorem does not necessarily expose every declaration referenced in its proof as a separate candidate to the proving agent. For example, retrieval systems such as Loogle, LeanSearch, LeanFinder, and TheoremSearch typically return declaration names, statements, or descriptions rather than complete proof-dependency lists.
Our use of "missed" therefore refers to premises not explicitly returned by direct retrieval, rather than premises unavailable in Mathlib. GARNET uses one-hop expansion to surface these dependencies as independently rankable candidates, allowing the reranker to assess their relevance to the current proof.
W5/Q2. The retrievers are trained and evaluated on Mathlib data. How could GARNET be extended to other mathematical libraries and user-specific definitions?
We appreciate the reviewer's question about generalization beyond Mathlib. Please note that although our premise bank and dependency graph are built from Mathlib, our evaluation also includes LeanWorkbook mathematical problems and SketchFill-60 textbook-derived proof tasks, whose target theorems are external to Mathlib.
These evaluations examine whether GARNET can retrieve useful Mathlib premises for external proof tasks, rather than testing transfer to a different premise library. Extending GARNET to other Lean libraries or user-defined projects would require indexing their declarations and dependencies, with possible adaptation of the encoders and reranker.
Q1. How does GARNET avoid over-retrieving frequently used premises?
We appreciate the reviewer's concern that frequently used premises could dominate graph expansion. To mitigate this, GARNET prioritizes lower-degree neighbors, limits expansion to D=20 outgoing and R=4 incoming neighbors per anchor, and deduplicates candidates.
To evaluate this design, we compared degree-aware selection with uniform one-hop sampling under the same neighbor budgets, using the same full graph-aware reranker for both settings. Degree-aware selection achieves R@20 of 0.652 and R@30 of 0.708, compared with 0.649 and 0.703 for uniform sampling (averaged over three seeds). These results show modest improvements from degree-aware selection under matched expansion budgets.
Q3. Which retrieval context contributes more to GARNET's performance: natural language queries or the current proof state?
Thank you for asking about the relative contributions of natural-language queries and formal proof states. We compared query-only (M10), state-only (M01), and joint query–state (M11) retrieval across all three principal test sets.
| Test set | Query-only | State-only | Joint |
|---|---|---|---|
| Mathlib Random | 0.483 | 0.489 | 0.607 |
| Novel Premises | 0.420 | 0.376 | 0.521 |
| LeanWorkbook | 0.531 | 0.527 | 0.607 |
All values are R@20.
Neither individual view consistently dominates across datasets, while joint retrieval achieves higher R@20 on all three.
In end-to-end proving on SketchFill-60, query-only, state-only, and joint retrieval achieve pass@5 of 86.7%, 70.0%, and 81.7%, respectively. Adaptive, which dynamically selects between query-only and joint retrieval, reaches 88.3%. These results suggest that the relative usefulness of each context depends on the retrieval setting, supporting the motivation for combining and adaptively selecting retrieval views.
Q4. How does GARNET handle cycles in the Mathlib dependency graph?
We thank the reviewer for raising this question about graph cycles. GARNET uses the public MathlibGraph declaration-dependency graph from Li et al. (2026, The Network Structure of Mathlib), where directed edges represent references to named Lean declarations in elaborated statements or proof terms.
We retain dependencies between declarations in our premise bank, remove self-loops, and deduplicate expanded candidates. Since GARNET only performs one-hop expansion rather than recursively traversing the graph, cycles do not cause repeated traversal or infinite expansion.
Q5. What is the distribution of gating scores in GARNET? Do these scores vary across different types of mathematical problems or fields?
Thank you for suggesting this analysis. We examined both the overall distribution of graph gating scores and their variation across mathematical domains on the namespace-matched test set (n=16,329).
For candidates with nonempty graph neighborhoods, the gate values have a mean of 0.84 and a median of 0.90. Approximately 78% exceed 0.75, while only 1.6% fall below 0.25. By construction, gates are set to zero when no graph neighbors are available.
Across mathematical domains, the mean gate values are 0.829 for Analysis, 0.858 for Algebra, and 0.842 for RingTheory, differing by less than 0.03. We also observe a negative correlation between gate values and the number of selected graph neighbors (Pearson r = −0.33).
These findings indicate that gate values are generally concentrated toward the higher end when graph neighbors are available, with limited variation across the three mathematical domains. The negative correlation with neighborhood size suggests that the learned gate tends to attenuate graph contributions in denser neighborhoods.
We thank the reviewer for recognizing the query/state ablations and gated graph component. We address the concerns with added controls, proof traces, and gate analyses.
W1. The evaluation lacks a baseline measuring the end-to-end theorem-proving performance of GPT-5.6 without any retrieval method.
Thank you for highlighting the importance of a no-retrieval baseline. We evaluated GPT-5.6-Luna on SketchFill-60 without retrieval, using the same proving agent and evaluation protocol as GARNET. Without retrieval, the agent achieves 63.3% pass@5 and 42.7% mean single-attempt accuracy, compared with 88.3% and 77.7% for GARNET Adaptive. The results show that retrieval substantially improves proof completion in this setting.
W2. The performance of the "w/o graph branch" variant raises the question of which components primarily drive GARNET's improvements over LeanSearch and LeanFinder.
We thank the reviewer for raising this important question about component attribution. We would like to clarify that the original "w/o graph branch" ablation removes graph-aware scoring while retaining dependency-guided candidate expansion. To examine their contributions separately, we conducted additional matched-size comparisons on all three principal test sets.
For each test instance, we compare graph-expanded candidates with equally sized direct query–state retrieval pools using the same frozen direct-evidence reranker, trained on expanded candidates. We also evaluate the full graph-aware ranker on the same expanded pool. Q:S denotes the query-to-state retrieval ratio.
Compared with the strongest matched-size direct retrieval baseline on each test set, graph expansion improves R@20 by 0.5, 0.7, and 2.1 percentage points on Mathlib Random, Novel Premises, and LeanWorkbook, respectively. On the same expanded pools, graph-aware scoring provides additional gains of 2.6, 1.7, and 1.5 percentage points.
These results distinguish the contributions of graph-guided candidate selection and graph-aware scoring within GARNET. The improvements over LeanSearch and LeanFinder also involve differences in training supervision and retrieval architecture: GARNET uses proof-step-derived queries and proof-used premises for training, together with complementary query/state retrieval and task-trained reranking. We discuss these differences further in Q6.