acceptodds
Under review as a conference paper at ICLR 2027

GARNET: Graph-Augmented Reranking for Premise Retrieval in Lean

Abstract

Premise retrieval is a central component of LLM-based theorem proving: a prover must identify useful lemmas from a library containing hundreds of thousands of declarations. Most existing retrievers rely on direct matching with either a natural-language query or a local proof state, ignoring the structural relationships encoded in the library's dependency graph. We propose GARNET, a graph-augmented reranking framework for Lean that expands query- and state-conditioned anchor sets along local dependency neighborhoods and reranks candidates by combining direct retrieval evidence with structural context. On end-to-end retrieval benchmarks, GARNET improves R@20 by over 20 absolute points against strong baselines on Mathlib 4.28 and maintains strong performance on Lean Workbook. When integrated into an LLM-based proving agent for proof-sketch completion on a curated 60-theorem subset of ProofNet-Verified, it achieves % mean single-attempt accuracy and 88.3% pass@5, the highest among all evaluated systems, with a substantial margin over learned state-only retrievers. More broadly, our results show that effective premise retrieval benefits from combining complementary query- and state-conditioned evidence with structural relationships among library declarations.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Automated theorem proving, premise selection, Lean, LLM agents,retrieval-augmented language models

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_oBZpOpenReview ↗
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

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.

Test setRankerCandidate poolR@20C@20MRR
Mathlib RandomFull (E+G)Graph expansion0.6070.4920.384
Direct evidenceGraph expansion0.5810.4690.372
Direct evidenceDirect (Q:S = 1:1)0.5740.4650.369
Direct evidenceDirect (Q:S = 3:1)0.5700.4620.368
Direct evidenceDirect (Q:S = 1:3)0.5760.4660.369
Novel PremisesFull (E+G)Graph expansion0.5210.4040.320
Direct evidenceGraph expansion0.5040.3920.318
Direct evidenceDirect (Q:S = 1:1)0.4950.3870.315
Direct evidenceDirect (Q:S = 3:1)0.4910.3840.312
Direct evidenceDirect (Q:S = 1:3)0.4970.3890.315
LeanWorkbookFull (E+G)Graph expansion0.6070.5170.351
Direct evidenceGraph expansion0.5920.5090.346
Direct evidenceDirect (Q:S = 1:1)0.5680.4900.353
Direct evidenceDirect (Q:S = 3:1)0.5590.4830.352
Direct evidenceDirect (Q:S = 1:3)0.5710.4920.353

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.

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 setQuery-onlyState-onlyJoint
Mathlib Random0.4830.4890.607
Novel Premises0.4200.3760.521
LeanWorkbook0.5310.5270.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.

Reviewer_gom8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

GARNET is a system for finding useful Mathlib lemmas for Lean proof generation. It first retrieves declarations using a natural language query and the current proof state. It then adds selected one hop neighbors from Mathlib’s dependency graph and uses a learned model to rerank the resulting candidates. The method is evaluated on retrieval on Mathlib random and novel premise splits and on Lean Workbook. It also tests the retriever in an LLM agent that fills holes in 60 proof sketches. The joint query and state system gives the best offline retrieval results among the systems tested, while the adaptive version has the highest downstream success rate.

Critical strengths
  • On the Mathlib random split, its joint version reaches 60.7% Recall@20, vs 36.9% for the strongest reported baseline, this is a pretty large margin. The novel premise and Lean Workbook results also suggest that the gain is not limited to one random split.
Critical weaknesses
  • My main concern is that the paper has not isolated the value of its graph expansion rule. The default anchor pool has about 279 candidates, while the expanded pool has about 1372. Removing expansion lowers recall@30 by 5.6 , but that comparison also removes most of the candidates. with the same pool size, direct query and state retrieval already covers 91.44% of gold premises, vs 93.16% with graph expansion. I would better if the authors can provide comparison of passing through the same reranker and compared at the final top20 cutoff. The work also does not separately test the low degree neighbor selection rule against simpler one hop selection. I find a related work called TheoremGraph[1] that had already tested one hop dependency expansion, maybe the authors want to mention and compare to this method.

  • The authors said they removed the theorem being proved from the graph, but I could not find a precise statement that all remaining candidates and edges respect that theorem’s imports and declaration order. Later or heldout declarations could contain useful dependency information even if the target theorem itself is removed.

  • The quality of figure 1 seems to be low resolution

[1] Kurgan et al., “TheoremGraph: Bridging Formal and Informal Mathematics,” arXiv:2606.25363, 2026. https://arxiv.org/abs/2606.25363

Questions for authors
  • I'd like to understand how much does the graph expansion itself help. So could the authors compare it with an equally large pool from direct query and proof state retrieval, using the same reranker and reporting final top20 recall? It would also help to compare your low degree neighbor rule with a simpler one hop rule, and to explain how this differs from TheoremGraph.

  • For each theorem being proved, are all graph nodes and edges limited to declarations available under its imports and declaration order? If not, could you report results with that restriction?

3 comments

We thank the reviewer for recognizing GARNET's retrieval improvements across the three test sets. We have expanded the matched-size ranking comparisons, tested degree-aware selection, clarified declaration availability, and addressed the relation to TheoremGraph.

W1/Q1 (1/3). Could you compare graph expansion with an equally sized direct query–state pool using the same reranker and reporting final top-20 recall?

Thank you for suggesting this controlled comparison. Following your suggestion, we compared graph expansion against equally sized direct query–state retrieval pools using the same frozen direct-evidence reranker trained on expanded candidates. Candidate-pool sizes are matched for each test instance, and Q:S denotes the query-to-state retrieval ratio.

On the namespace-matched ablation test set (n=16,329), we obtain:

Candidate poolR\@20C\@20MRR
Graph expansion0.6240.5070.397
Direct (Q:S = 1:1)0.6110.4970.393
Direct (Q:S = 3:1)0.6080.4940.393
Direct (Q:S = 1:3)0.6120.4990.393

Graph expansion improves R@20 by 1.2–1.6 percentage points over matched-size direct retrieval, while also improving C@20 and MRR.

We further conducted the same comparison on all three principal test sets: Mathlib Random (n=48,332), Novel Premises (n=64,904), and LeanWorkbook (n=15,695). With the direct-evidence reranker fixed, graph expansion improves R@20 by 0.5–1.1, 0.7–1.3, and 2.1–3.3 percentage points, respectively, over matched-size direct retrieval. The corresponding C@20 improvements are 0.3–0.7, 0.3–0.8, and 1.7–2.6 percentage points.

Separately, applying the full graph-aware ranker to the same expanded pools provides additional R@20 improvements of 2.6, 1.7, and 1.5 percentage points, respectively. These comparisons distinguish the contribution of graph-guided candidate selection from that of graph-aware scoring.

W1/Q1 (2/3). Does degree-aware selection help relative to uniform one-hop sampling?

Thank you for suggesting this comparison. We evaluated degree-aware selection against uniform one-hop sampling under the same per-anchor neighbor budgets (D=20, R=4), using the same full graph-aware reranker for both settings. Degree-aware selection achieves R@20 = 0.652 and R@30 = 0.708, compared with 0.649 and 0.703 for uniform sampling (mean over three seeds). These results show modest but consistent improvements from degree-aware neighbor selection under matched expansion budgets.

W1/Q1 (3/3). How does the method differ from TheoremGraph?

We thank the reviewer for bringing TheoremGraph to our attention. We have added this relevant work to the Related Work section and clarified the motivation behind GARNET.

Our work focuses on a retrieval setting where a theorem may be semantically relevant to the query but not directly useful for the current proof, while its dependencies may contain the required auxiliary premises. To address this, GARNET expands the dependency neighborhoods of both query- and proof-state-retrieved anchors and uses a learned graph-aware reranker to prioritize proof-relevant candidates.

We further examined this motivation through the gold-premise similarity analysis on the namespace-matched test set. For the 64.2% of gold premises outside query-direct top-150, query similarity is close to the expanded-pool average (0.450 vs. 0.446), while proof-state similarity is substantially higher (0.509 vs. 0.208). These findings help explain why complementary proof-state and dependency information can be useful in our setting.

W2/Q2. For each theorem, are all graph nodes and edges limited to declarations available under its imports and declaration order? If not, could you report results with that restriction?

Graph construction and evaluation setting. Thank you for asking us to clarify how the graph is constructed and which declarations are available during retrieval. GARNET uses the public MathlibGraph declaration-dependency dataset from Li et al. (2026, The Network Structure of Mathlib). Graph nodes represent named Mathlib declarations, and directed edges represent dependencies extracted from their elaborated types and proofs. We project these dependencies onto our premise bank, removing self-loops and duplicate edges.

Our setting reflects a practical theorem-proving workflow: when constructing a new proof, the initially imported modules may not contain all the required premises. The proving agent may therefore need to discover useful lemmas from other modules and introduce additional imports. We adopt library-wide retrieval to support this workflow, rather than enforcing historical import or declaration-order restrictions.

Target-dependent information. We appreciate the reviewer's observation that removing the target theorem and its incident edges may still leave dependency information from later declarations that rely on the target. To examine this concern, we conducted an additional test-time experiment that excludes all declarations directly or transitively dependent on the target theorem. We reconstruct the filtered subgraph and its structural features for candidate expansion and reranker neighborhood construction, while keeping the trained reranker fixed.

On the namespace-matched test set (n=16,329), retrieval performance remains stable: R@20 changes from 0.652 to 0.653, C@20 from 0.532 to 0.533, and MRR from 0.416 to 0.420.

For LeanWorkbook and SketchFill-60, the target theorems are external to Mathlib and are not present in the Mathlib dependency graph. Thus, the specific concern of retaining graph dependencies on the target theorem does not arise in these evaluations.

W3. The quality of Figure 1 seems to be low resolution.

Thank you for pointing out the resolution issue with Figure 1. We have replaced it with a higher-resolution version to improve its clarity and readability.

Dear Reviewer gom8,

Thank you again for your detailed and constructive review. As the author–reviewer discussion period is approaching its end, we would like to kindly follow up and ask whether our responses have sufficiently addressed your main concerns.

In particular, we hope that the matched-size graph expansion comparisons, the degree-aware selection ablation, the clarification and additional experiments regarding target-dependent declarations, and the discussion of TheoremGraph have addressed the key questions raised in your review.

If there are any remaining concerns or points that require further clarification, please do not hesitate to let us know. If you feel that our responses have addressed the main issues, we would greatly appreciate your consideration of updating your evaluation accordingly.

Thank you again for your time and careful consideration.

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

GARNET combines query- and proof-state retrieval for premise selection in Lean. It expands their anchor sets through one-hop Mathlib dependencies, then reranks candidates using direct matching and a gated graph residual. View dropout supports query-only, state-only, and joint inference. Evaluation covers Mathlib random and novel-premise splits, Lean Workbook, and 60 curated proof-sketch completion tasks. Joint retrieval reaches R@20 of 60.7%, 52.1%, and 60.7% on the three retrieval sets. Adaptive retrieval achieves 77.7% mean single-attempt accuracy and 88.3% pass@5 on SketchFill-60, although its advantage over strong query baselines remains uncertain.

Critical strengths
  1. Retrieval gains are substantial across settings (Tables 1–2): joint GARNET improves R@20 over the strongest standalone baseline by 23.8, 23.7, and 32.4 points on Mathlib random, novel-premise, and Lean Workbook. Single-input variants also improve substantially. The split-specific State-ByT5 baseline and premise-bank alignment analyses (Appendix F.3) strengthen these comparisons.

  2. The ablations support the use of graph structure. With the expanded pool fixed, removing the graph branch lowers R@30 from 70.8% to 68.2%; removing both graph components lowers it to 63.3% (Tables 13–14). The separation of candidate discovery and structural scoring is useful, while downstream interface/oracle diagnostics and paired uncertainty estimates make the evaluation informative.

Critical weaknesses
  1. Graph-guided expansion is not fully compared against an equally large direct-retrieval pool at the final ranking stage. Table 5 reports about 279 anchors versus 1,372 expanded candidates; a matched-size query–state mixture reaches 91.44% candidate coverage versus 93.16% with expansion. Yet Table 14 compares final ranking against the smaller anchor pool, without a trained graph-free reranker over the matched-size direct pool. The fixed-pool ablation supports structural scoring, but the expansion result mixes graph-based selection with candidate-count effects. This limits attribution of the headline gains to the graph.

  2. The proving evidence is narrow and does not isolate a graph-specific advantage. SketchFill-60 selects premise-rich proofs, preserves reference subgoal decompositions, and uses recorded rather than evolving proof states (Appendix I). Adaptive solves 53/60 theorems versus LeanFinder's 51/60; the pass@5 difference is +3.3 points with 95% CI [-3.3, +10.0] (Table 18). The authors acknowledge this uncertainty. These results demonstrate feasibility more clearly than a general proving advantage from graph augmentation.

Questions for authors
  1. Could you compare graph expansion with a matched-size direct query–state pool using the same encoders, training data, and direct-evidence reranker? R@20, C@20, and MRR on the principal test sets would clarify the graph's contribution.

  2. Could you evaluate a graph-free baseline with the same Adaptive interface on SketchFill-60 and report retrieval calls, tokens, or wall time across all attempts? Table 17 reports only successful-trace costs.

  3. Do candidate retrieval and graph construction enforce import/declaration-order availability, including excluding declarations dependent on the target? If only the target is removed from the full library, please clarify Appendix C's claim that this simulates a theorem not yet in the library. This is a protocol clarification, not an allegation of leakage.

3 comments

We thank the reviewer for recognizing the substantial retrieval gains across the three datasets and the value of our graph ablations. We address the attribution and proving-protocol concerns with matched-size retrieval controls, a graph-free Adaptive evaluation, and a clarification of declaration availability.

W1/Q1. Could you compare graph expansion against an equally sized direct query–state pool using the same reranker and report final-ranking metrics? Thank you for suggesting this controlled comparison. We agree that the original no-expansion ablation also changes the candidate-pool size, making it difficult to isolate the contribution of graph expansion. Following your suggestion, we conducted matched-size comparisons on all three principal retrieval test sets: Mathlib Random (n=48,332), Novel Premises (n=64,904), and LeanWorkbook (n=15,695).

For each test instance, we compare graph-expanded candidates against equally sized direct query–state pools, using the same frozen direct-evidence reranker trained on expanded candidates. This holds the candidate-pool size and ranking model fixed while varying candidate selection. Q:S denotes the query-to-state retrieval ratio. We also report the full graph-aware ranker on expanded candidates for reference.

Mathlib Random

ModelCandidate poolR\@20C\@20MRR
Full (E+G)Graph expansion0.6070.4920.384
Direct evidenceGraph expansion0.5810.4690.372
Direct evidenceDirect (Q:S = 1:1)0.5740.4650.369
Direct evidenceDirect (Q:S = 3:1)0.5700.4620.368
Direct evidenceDirect (Q:S = 1:3)0.5760.4660.369

Novel Premises

ModelCandidate poolR\@20C\@20MRR
Full (E+G)Graph expansion0.5210.4040.320
Direct evidenceGraph expansion0.5040.3920.318
Direct evidenceDirect (Q:S = 1:1)0.4950.3870.315
Direct evidenceDirect (Q:S = 3:1)0.4910.3840.312
Direct evidenceDirect (Q:S = 1:3)0.4970.3890.315

LeanWorkbook

ModelCandidate poolR\@20C\@20MRR
Full (E+G)Graph expansion0.6070.5170.351
Direct evidenceGraph expansion0.5920.5090.346
Direct evidenceDirect (Q:S = 1:1)0.5680.4900.353
Direct evidenceDirect (Q:S = 3:1)0.5590.4830.352
Direct evidenceDirect (Q:S = 1:3)0.5710.4920.353

With the direct-evidence reranker fixed, graph expansion improves R@20 by 0.5–1.1 percentage points on Mathlib Random, 0.7–1.3 on Novel Premises, and 2.1–3.3 on LeanWorkbook relative to matched-size direct pools. Graph-aware scoring provides additional improvements of 2.6, 1.7, and 1.5 percentage points, respectively, on the expanded pools. These results show that graph-guided candidate expansion improves final ranking beyond simply increasing the candidate-pool size, with further gains from graph-aware scoring.

W2 (1/2). Concern about SketchFill-60 preserving reference subgoal decompositions and using recorded rather than evolving proof states.

We appreciate the reviewer's concern about the evaluation protocol and the scope of our end-to-end proving results.

SketchFill-60 preserves the subgoal decomposition of Lean-verified textbook proofs and asks the proving agent to construct proofs for the resulting subgoals. This design reflects subgoal-oriented theorem-proving workflows, including blueprint-guided formalization, where mathematical arguments are decomposed into intermediate proof obligations before individual subproofs are constructed. Each subgoal exposes a corresponding recorded proof state, providing a common interface for comparing query-based, state-based, and joint query–state retrieval within the same LLM proving agent.

In an unrestricted proving process, the agent must additionally decide how to decompose a theorem into intermediate subgoals and generate evolving proof states. Consequently, the availability and effectiveness of state-conditioned retrieval would also depend on the agent's ability to construct appropriate subgoals and invoke the corresponding retrieval tools. By preserving a verified decomposition, our evaluation reduces this additional source of variability and focuses on the effectiveness of premise retrieval and Lean-verified proof construction for well-defined subgoals.

W2/Q2(2/2). Could you evaluate a graph-free baseline with the same Adaptive interface on SketchFill-60 and report retrieval costs across all attempts?

Thank you for suggesting this additional comparison. To more directly assess the contribution of graph augmentation within the subgoal-based proving setting described above, we evaluated a graph-free variant under the same Adaptive interface on SketchFill-60. This variant removes both dependency-guided candidate expansion and graph-aware scoring, replacing the expanded pool with matched-size direct query/state retrieval (Q:S = 1:1) and using the same frozen direct-evidence reranker.

Full Adaptive solves 53/60 theorems, compared with 50/60 for Graph-free Adaptive. On the 49 theorems solved by both, using each system's first successful attempt, Full Adaptive achieves higher Pair@20 (22.6% vs. 18.7%), QHit@20 (73.0% vs. 70.3%), and Cov(R,U) (81.4% vs. 76.7%).

We also extended the retrieval cost analysis to all 300 attempts per system, including unsuccessful attempts. The results are summarized below.

SystemRetrieval callsCalls/attemptTokens (M)
No Retrieval——8.0
LeanPremise5,60218.748.4
LeanStateSearch5,52918.448.6
State-ByT55,01216.746.0
GARNET (M01)3,92113.137.6
LeanFinder2,3217.727.5
LeanSearchV22,4158.125.9
GARNET (M10)2,1567.223.8
GARNET (M11)3,85512.834.6
GARNET (Adaptive)3,14510.531.1
GARNET (Graph-free)3,42311.431.9

Compared with Graph-free Adaptive, Full Adaptive solves three additional theorems while using 278 fewer retrieval calls and 0.8M fewer tokens across all attempts.

Q3. Do candidate retrieval and graph construction enforce import/declaration-order availability, including excluding declarations dependent on the target theorem?

Thank you for asking us to clarify the declaration-availability protocol. Our evaluation uses library-wide retrieval rather than enforcing historical import or declaration-order restrictions. This reflects a practical theorem-proving setting where the agent can discover useful lemmas beyond the initially imported modules and add imports as needed.

In the original protocol, we only remove the target theorem and its incident edges from the premise graph. To further address your concern, we conducted an additional test-time experiment that excludes all declarations directly or transitively dependent on the target theorem from graph expansion and reranker neighborhood construction. The retrieval results remain stable, with R@20 changing from 0.652 to 0.653 and C@20 from 0.532 to 0.533.

Dear Reviewer cujr,

Thank you again for your detailed and constructive review. As the author–reviewer discussion period is approaching its end, we would like to kindly follow up and ask whether our responses have sufficiently addressed your main concerns.

In particular, we hope that the matched-size comparison for graph expansion, the additional graph-free Adaptive evaluation and retrieval-cost analysis, and the clarification and additional experiment regarding declaration availability have addressed the key questions raised in your review.

If there are any remaining questions or points that require further clarification, please do not hesitate to let us know. If you feel that our responses have addressed the main concerns, we would be grateful if you could take them into account in your final assessment.

Thank you again for your time and careful consideration.

Best, 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.