acceptodds
Under review as a conference paper at ICLR 2027

Directed Multi-Relational GCNs for Premise Selection in Lean

Abstract

Premise selection is a central bottleneck for interactive theorem proving over large formal libraries. Semantic similarity can miss syntactic roles that govern premise applicability, while Lean elaboration can give similar expressions different tree representations through implicit arguments and typeclass evidence. We present R-DGCN, which learns from expression graphs designed to reduce this variation while retaining role distinctions. Retrieval preprocessing reduces recurring expression-tree variation. Typed edges encode constructor-field roles, and paired reverse edges expose subterms to their surrounding context. A relation-specific graph convolutional encoder combines mean and attention pooling to capture global structure and emphasize informative nodes in shared query–theorem embeddings. Precomputed theorem embeddings support retrieval, followed by directed collapse-match (CM) reranking that refines learned similarity using explicit structural coverage. Retrieval comparisons show complementary benefits from learned and structural scores, with recall gains most consistent at larger retrieval cutoffs. Precomputed theorem embeddings enable low online retrieval latency.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Premise Selection, Interactive Theorem Proving, Graph Neural Networks, Lean4

Reviews

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

The paper presents R-DGCN, a graph neural network-based framework for theorem retrieval from large formal libraries to support interactive theorem proving. As part of this larger framework, the authors introduce steps for Lean-specific retrieval preprocessing, construct directed graphs with edge types, and train a relational GCN on these graphs. On several theorem retrieval tasks, the R-DGCN system improves upon existing approaches in terms of recall, precision, and F1, often by a wide margin. Additionally, the R-DGCN is orders of magnitude faster. Ablations covering alternative encoder approaches and pre-processing choices are also provided, as are some uncertainty measurements across random seeds.

Critical strengths
  • Good empirical performance: across all three query sets in table 1, the R-DGCN system shows consistent and often substantial gains over existing Lean search tools. The gains seem to be most pronounced for recall @ 10 on test set B, where R-DGCN outperforms the second best approach considered by more than 35 percentage points. The ablation studies in tables 3 and 4 provide further valuable insights into the main components that drive the system’s success. Finally, the gains in retrieval latency over baseline approaches such as tree-based search are substantial and could be a significant advantage for interactive theorem proving over very large libraries.
  • Clear writing and easy to follow: the paper is overall well-structured and written in a clear and approachable way. Figures 1 and 2 provide good visualizations of the core ideas of the pipeline and the main components of the model. The paper also manages to cover all its primary ideas in reasonable detail in the main text. Only information that might otherwise interrupt the flow of the paper is relegated to the appendix.
Critical weaknesses
  • Limited novelty: While the design choices made for the overall system all seem reasonable and are presented in an unconvoluted way, many of the components of the final pipeline still seem to be existing ideas or architectures. As such, the novelty of the paper seems to be more the combination of these individual components and their successful application to the particular problem of retrieving theorems from large formal libraries for interactive theorem proving, rather than the introduction of a novel architecture, for example. This might also somewhat limit the relevance of the paper to other areas of machine learning, for example because the utility of some of these components or their combination might not transfer.
  • Limited exploration of the GNN design space: the ablation results in table 4 seem to indicate that the GNN plays a crucial role for the overall system and that it needs both directions and types for good performance. Additional experiments with other relational GNNs would be valuable here to determine to what extent using a stronger GNN can further lift the performance of the overall system.
Questions for authors
  • Could the authors repeat the variation across seed checkpoints experiments in table 5 with Test A and Test C? Some uncertainty quantification for settings where the system’s performance gains were less pronounced would be cause for additional confidence.
  • Could the authors repeat at least some of their experiments with a GNN architecture that is not R-DGCN? For example, could (local) attention mechanisms (as in GAT) be beneficial here?
2 comments
AuthorsOpenReview ↗

Response to Reviewer v6pA

Thank you for recognizing the empirical performance and clarity of the paper and for your suggestions on methodological contributions, seed stability, and alternative GNN architectures.

W1. Methodological contribution and applicability across domains

Our contribution is a Lean premise-retrieval design in which canonicalization, field-role parameterization, and directed collapse-match (CM) address different retrieval difficulties. Canonicalization reduces wrapper-related variation before encoding; relation-specific transformations distinguish functions, arguments, and message directions during relevance learning; CM checks concrete symbols and ordered substructures while accommodating additional query wrappers. FormulaNet already represents variable binding and argument order through graph structure and ordered treelets. Wang et al., 2017 Our design further combines learned relevance with explicit structural matching for Lean expressions.

The capacity-matched sequence comparison supports the graph representation, while the CM comparison on the same candidate list tests the matching refinements: replacing original CM increases fused Test-B R@10 from 55.21% to 64.40%, a gain of 9.19 percentage points, with the R-DGCN encoder, preprocessing, and fusion coefficients fixed. These results support the representation and matching choices that make the combination effective. For other symbolic languages with explicit constructors and field roles, adaptation would require corresponding canonicalization rules and relation types; the current empirical findings concern Lean Mathlib.

Q1. Stability across random seeds and results across test sets

Paired evaluations across five seeds on Test-B show that R-DGCN + CM outperforms the corresponding R-DGCN-only model on R@1, R@5, R@10, and MRR for every seed. Mean R@10 increases from 46.78% to 60.73%, a gain of 13.95 percentage points. These results show that the complementary benefits of learned and structural scores recur across all five evaluated seeds. The main experiments on Test-A/B/C assess system performance across different query sets. These two sets of evidence support stability across seeds and effectiveness across query sets, respectively. Direct quantification of seed variation currently comes from Test-B; the existing Test-A/C results do not quantify uncertainty across seeds for their smaller gains.

W2 / Q2. Alternative structural encoders and self-attention encoding

The existing controls cover tree-structured aggregation, graph relation configurations, and sequence self-attention. Our relation design determines which feature transformation is applied to each syntactic role, while local attention can further adjust the aggregation weights of neighboring messages. For example, after applying separate transformations to functions and arguments, their relative weights can still be learned based on the current node. Local attention and field-role parameterization can therefore be combined within the method.

All models use encoder-only ranking. The three GCNs share supervision, splits, negative-sampling settings, and training budgets; full R-DGCN, directed untyped GCN, and role-only undirected GCN have 399,809, 154,049, and 163,716 parameters, respectively. The role-sequence Transformer uses R-DGCN's supervision split and training settings, with 400,576 parameters (a 0.19% difference).

EncoderR@1R@5R@10MRR
Relation-agnostic tree encoder8.0926.7527.3317.47
Directed untyped GCN15.6522.2042.9921.68
Role-only undirected GCN2.2423.3827.709.40
Capacity-matched role-sequence Transformer13.0219.6823.7517.32
Full R-DGCN20.9528.0547.5826.92

Full R-DGCN leads all encoder controls on all four metrics. At essentially the same parameter count, its R@10 is approximately twice that of the role-sequence Transformer; its higher R@1 and MRR also indicate better ranking near the top. The relation ablations show lower performance when transformations are shared across syntactic roles or message directions. Whether local attention can further improve performance on this basis cannot be determined from the existing comparisons.

I would like to thank the authors for the detailed response. I remain in favor of accepting this paper and will therefore maintain my original score.

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

The paper proposes a method for premise selection/retrieval for Lean using graph networks.

Critical strengths
  • The paper presents a well-engineered system.

  • The system is shown to outperform existing systems significantly.

  • The tool resulting from this work can be genuinely useful for automated formal theorem proving.

Critical weaknesses
  • It is not clear how novel the proposed approach is and how it is different from Wang et al. 2017, which used graph networks to map symbolic expressions to embeddings.

  • There's no controlled baseline that fine-tunes a sequence encoder that is pretrained, such as the one used in ReProver. The result of this would be informative to include. It would not be an apples-to-apples comparison necessarily, but it would tell us how much sequence pretraining can make up for not using the explicit graph structure.

  • Given the current capabilities of frontier models, is such a retrieval system still useful or necessary? The answer may well be yes. But the paper does not appear to have addressed this question either conceptually or experimentally.

Questions for authors

I'd appreciate responses on the weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer CQYT(1/2)

Thank you for recognizing the system's practical value and for your questions on methodological novelty, pretrained sequence baselines, and retrieval for frontier proving models.

W1. Differences from Wang et al. (2017)

FormulaNet already preserves variable binding through graph structure and represents argument order through ordered treelets. Wang et al., 2017 R-DGCN builds on graph-based expression encoding by assigning relation-specific transformation matrices to constructor fields and message directions. A subexpression therefore contributes through different learned transformations when it appears as a function or an argument. Canonicalization reduces variation from Lean wrappers before encoding, while directed CM permits query-side collapses during reranking and retains constraints on concrete symbols and the order of candidate subexpressions.

The capacity-matched role-sequence Transformer comparison supports the evaluated graph representation at a comparable parameter budget. To test the matching refinements, we compare original and proposed CM on the same Test-B candidate lists, with preprocessing, the R-DGCN model, and fusion coefficients fixed. Replacing original CM increases fused R@10 from 55.21% to 64.40%, a gain of 9.19 percentage points. This comparison provides direct evidence for the added matching rules with the learned encoder held fixed.

W2. Comparison with a fine-tuned pretrained sequence encoder

All methods are evaluated on the same 6,104 Test-B queries. For each query, R-DGCN and ReProver retrieve from the same set of theorem declarations visible in the current Lean proof state, with the parent declaration excluded. The resulting rankings are evaluated using the same hit criterion. ReProver fine-tuning matches R-DGCN's supervision source, sample composition, and negative-sampling policy, using 44,000 records with a 90/10 training/validation split and checkpoint selection by validation loss.

MethodR@1R@5R@10MRR
R-DGCN-only20.9528.0547.5826.92
R-DGCN + CM29.5141.8464.4037.91
ReProver (public checkpoint)3.676.247.635.02
ReProver (fine-tuned with the same supervision)8.7514.8917.5011.78
ReProver (fine-tuned with the same supervision) + CM7.8314.1917.4611.04

Fine-tuning improves ReProver on all four metrics, while R-DGCN-only retains its lead before CM reranking. The encoder-only comparison therefore supports the competitiveness of the learned graph representation against a pretrained sequence retriever adapted to the same premise-retrieval task.

CM improves all four metrics for R-DGCN, while slightly lowering fine-tuned ReProver's scores in this comparison. The gains therefore support the specific combination of learned graph relevance and structural matching in R-DGCN + CM.

AuthorsOpenReview ↗

Response to Reviewer CQYT(2/2)

W3. The value of retrieval for frontier proving models

Premise retrieval connects a proving model's mathematical reasoning to the concrete declarations available in the current formal library. Even when a model identifies the mathematical result it needs, executable Lean steps require exact theorem names and types compatible with the proof state. R-DGCN supplies visible premises from the goal and local context and updates candidates as proof search proceeds, reducing reliance on memorizing the library. The following paired experiment evaluates the practical benefit of this interface with a fixed ReProver generator.

With the generator and search budgets fixed, R-DGCN + CM closes 47 more single-step goals than Tree-based Search on 6,104 Test-B queries, a gain of 0.77 percentage points (95% confidence interval: 0.50–1.06, paired bootstrap clustered by parent declaration). On 200 preselected declarations, it completes 48 proofs versus 41, a gain of 7 proofs or 3.5 percentage points (paired 95% confidence interval: −0.5–8.0). These results support a single-step proof benefit; the positive difference in complete proofs remains uncertain because its interval includes zero.

Both retrievers use the same initial Lean states and fixed ReProver generator, supplied only with the current proof state and top 10 visible premises. Single-step success requires Lean-verified closure of the goal and all subgoals within 32 suggestions per query. For complete proofs, we remove proofs from 200 distinct parent declarations selected by a prespecified rule and run best-first search from their initial goals, retrieving at every expansion with a 600-second limit per declaration. Initial states were restored for 3,734 of 6,104 queries and 194 of 200 declarations; restoration failures and timeouts count as failures. All successful proofs undergo independent Lean compilation and axiom-dependency checks.

Retrieval methodSingle-step tactic success (%)Proof completion (%)
Tree-based Search7.7520.50
R-DGCN + CM8.5224.00

The additional Lean-verified steps show that improved premise selection helps the same generator close more goals within the same suggestion budget. This provides a practical benefit beyond retrieval metrics: better premises improve proof generation without increasing the number of supplied premises or the generation budget.

Thank you again for your constructive feedback. We hope that our responses have adequately addressed your concerns and would greatly appreciate your consideration of our clarifications in your overall assessment. We would be happy to address any further questions.

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

This paper proposes R-DGCN, a graph-based premise retrieval framework for Lean that combines expression canonicalization, directed multi-relational graph convolution, and structural reranking. The model preserves syntactic roles through relation-specific edges and uses contrastive learning to align proof goals with relevant premises. A directed collapse-match score further improves retrieval by measuring structural correspondence between queries and candidate theorems. Experiments on three benchmarks demonstrate substantial retrieval improvements over existing methods, alongside significantly reduced inference latency.

Critical strengths
  1. the method achieves substantial improvements over Tree-based Search, particularly on Test-B, where Recall@10 increases from 28% to 64%.

  2. combining graph embeddings with structural matching is well motivated, and the ablations demonstrate that these components provide complementary benefits.

  3. precomputed theorem embeddings enable fast retrieval over 218K theorems, with a median latency of 0.39 seconds for the complete system versus 79.44 seconds for Tree-based Search.

Critical weaknesses
  1. potential data leakage and insufficient split validation. The training and validation sets use record-level splitting, explicitly allowing examples from the same declaration in both sets (Appendix D.3). Moreover, the paper does not clearly establish declaration-level disjointness between training data and evaluation benchmarks, particularly Test-C, which is also extracted from Mathlib tactic traces. This raises concerns about generalization.

  2. the comparisons include a frozen MiniLM encoder and a relatively small, capacity-matched Transformer. Comparisons with stronger fine-tuned pretrained code or mathematical language models would better establish the competitiveness of the proposed graph representation. Some tool-level comparisons also use different evaluation criteria. Also, the paper lacks comparison with recent retrieval engines like LeanSearch V2.

  3. the paper evaluates retrieval of recorded premises but does not demonstrate whether the improvements translate into higher proof success rates when integrated into an automated theorem prover. This limits the evidence for practical impact.

Questions for authors
  1. How do the authors ensure no overlap between training and evaluation data, particularly Test-C? Could they report results using declaration-level splits?

  2. Why are stronger retrieval models and recent systems such as LeanSearch V2 not included in the comparisons?

  3. Do the retrieval improvements translate into higher proof success rates when integrated into an automated theorem prover?

3 comments
AuthorsOpenReview ↗

Response to Reviewer UHgx(1/2)

Thank you for recognizing the retrieval gains and efficiency of our system and for your suggestions on data independence, stronger baselines, and proof success.

W1 / Q1. Independence between supervision and Test-C

The supervision pool and each of Test-A/B/C are disjoint at the canonicalized complete-query level, where a complete query consists of the proof-state goal and local context. We audited all 44,000 supervision records, including original and selected perturbed queries, and found zero complete-query overlaps with each test set. This also holds for Test-C, although its queries and the supervision records both originate from Mathlib rw steps.

As specified in the paper, the retriever uses the goal expression obtained by reverting the local hypotheses; the parent-declaration identifier is not supplied to the ranker. Different proof steps within one declaration can yield different goals and local contexts, while the same complete query can occur in different declarations. Parent-declaration identity therefore does not determine whether retrieval inputs are duplicates. For the supervision–test overlap check, we compare complete canonicalized queries directly. An additional exclusion of all queries sharing a parent declaration is unnecessary for removing duplicate query inputs and would also discard distinct proof states.

As described in Appendix D.3, we combined 40,000 original query–premise pairs and 4,000 selected syntactically perturbed pairs. Perturbations modify the query expression while retaining its premise label. The combined records were shuffled and split 90/10 at the record level into 39,600 training records and 4,400 validation records. We compared both original and selected perturbed queries against the test sets and excluded duplicates at the complete-query level.

Both the supervision data and Test-C come from Mathlib rw steps. Test-A and Test-B are from Wang et al. (2025). A contains 100 small problems constructed through transformations, while B is built from exact steps in real proofs and retains 6,104 queries after Mathlib version alignment. Test-C contains 12,494 queries, and the examples in the three test sets are mutually disjoint. Wang et al., 2025, Section 5.1 and Appendix E.2.2

W2 / Q2. Comparisons with ReProver and LeanSearch v2

ReProver. All methods are evaluated on the same 6,104 Test-B queries. For each query, R-DGCN and ReProver retrieve from the same set of theorem declarations visible in the current Lean proof state, with the parent declaration excluded. The resulting rankings are evaluated using the same hit criterion. ReProver fine-tuning matches R-DGCN's supervision source, sample composition, and negative-sampling policy and checkpoint selection by validation loss.

MethodR@1R@5R@10MRR
R-DGCN-only20.9528.0547.5826.92
R-DGCN + CM29.5141.8464.4037.91
ReProver (public checkpoint)3.676.247.635.02
ReProver (fine-tuned with the same supervision)8.7514.8917.5011.78
ReProver (fine-tuned with the same supervision) + CM7.8314.1917.4611.04

Fine-tuning improves ReProver on all four metrics, while R-DGCN-only retains its lead before CM reranking. The encoder-only comparison therefore supports the competitiveness of the learned graph representation against a pretrained sequence retriever adapted to the same premise-retrieval task. CM improves all four metrics for R-DGCN, while slightly lowering fine-tuned ReProver's scores in this comparison. The gains therefore support the specific combination of learned graph relevance and structural matching in R-DGCN + CM.

LeanSearch v2. To ensure that every target theorem is available in LeanSearch v2's library, we retain the 3,738 Test-B queries satisfying this condition and evaluate both systems on this subset. LeanSearch v2 takes the pre-tactic goal and local context in native standard mode with its reranker.

MethodR@1R@5R@10MRR
LeanSearch v29.8722.1224.9115.25
R-DGCN + CM29.6141.7167.3138.37

These comparisons demonstrate the advantages of R-DGCN + CM over both a task-fine-tuned pretrained retriever and LeanSearch v2. The encoder-only and full-system results support its competitiveness for Lean premise retrieval.

AuthorsOpenReview ↗

Response to Reviewer UHgx(2/2)

W3 / Q3. Single-step tactic success and proof completion

The retrieval gains translate into higher Lean-verified single-step success with the same ReProver generator and generation budget. With both methods supplying the top 10 currently visible premises, R-DGCN + CM closes 47 additional goals across 6,104 Test-B queries, improving success by 0.77 percentage points (95% confidence interval: 0.50–1.06, paired bootstrap clustered by parent declaration). On 200 preselected declarations, the complete-proof evaluation yields 48 successful proofs versus 41, a difference of 3.5 percentage points (paired 95% confidence interval: −0.5–8.0). All successful proofs pass independent Lean compilation and axiom-dependency checks.

Both retrievers use the same initial Lean states and fixed ReProver generator, supplied only with the current proof state and top 10 visible premises. Single-step success requires Lean-verified closure of the goal and all subgoals within 32 suggestions per query. For complete proofs, we remove proofs from 200 distinct parent declarations selected by a prespecified rule and run best-first search from their initial goals, retrieving at every expansion with a 600-second limit per declaration. Initial states were restored for 3,734 of 6,104 queries and 194 of 200 declarations; restoration failures and timeouts count as failures.

Retrieval methodSingle-step tactic success (%)Proof completion (%)
Tree-based Search7.7520.50
R-DGCN + CM8.5224.00

When integrated into ReProver, R-DGCN + CM increases Lean-verified tactic success and yields a higher complete-proof rate in the evaluated sample. The statistically supported single-step gain demonstrates a contribution to proof generation, while the positive complete-proof estimate suggests that these benefits can extend to end-to-end proof search.

Thank you again for your constructive feedback. We hope that our responses have adequately addressed your concerns and would greatly appreciate your consideration of our clarifications in your overall assessment. We would be happy to address any further questions.

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

R-DGCN retrieves Lean premises using canonicalized expression graphs with constructor-field relations and separate reverse edges. A contrastively trained relational GCN produces query/theorem embeddings, and weighted directional collapse-match (CM) reranks the top 2,000 visible candidates. Experiments on three query sets over a 218,415-theorem Mathlib library report improved premise recall and lower online latency than Tree-based Search. Test-B includes encoder/component comparisons and a five-seed analysis supporting the complementarity of learned and structural scores.

Critical strengths
  1. Learned and structural scores show complementary benefits. On Test-B, fusion reaches 64.40% R@10 versus 47.58% for the encoder and 42.69% for CM reranking, with CM and fusion sharing the same shortlist (Table 4; Appendix C.3). Across five seeds, fusion improves every reported metric in each paired run; mean R@10 rises from 46.78% to 60.73% (Table 5).

  2. The system offers a practical, well-documented retrieval design. Constructor-field roles provide a sensible inductive bias, supported by a capacity-matched Transformer comparison. Precomputed embeddings yield reported median latencies of 0.019 seconds for encoder-only retrieval and 0.39 seconds with CM over 218,415 theorems. The appendices document preprocessing, visibility filtering, training, and timing boundaries.

Critical weaknesses
  1. Test-query independence is insufficiently documented. Appendix D.3 permits records from the same parent declaration across training and validation after combining original and perturbed queries. Appendices A.3-A.4 do not report supervised-query overlap counts or an exclusion procedure against Tests A/B/C. This leaves generalization to unseen query contexts uncertain; it does not establish test leakage. An overlap audit and clarification of test construction are needed.

  2. The ablations do not fully isolate the proposed CM and graph refinements. Table 4 and Appendix C.3 demonstrate complementary learned and structural scores, but do not compare the proposed weighted/type-sensitive CM with original CM on the same shortlist. The graph controls merge 22 relation channels into two or eleven (Appendix D.8), while the encoder uses separate relation transformations. Their parameter counts and any capacity compensation are unreported. These omissions limit attribution to the new matching rules and role/direction distinctions, despite the useful capacity-matched Transformer comparison and robust fusion results.

  3. The preprocessing analysis is incomplete. Table 4 compares the full pipeline with binder-only, wrapper-only, and arithmetic-only variants, all using the same CSE pass. It lacks a baseline without these rewrites and full-pipeline-minus-one comparisons. The results support combining the rules relative to the tested single-rule variants, but do not establish each rule's incremental contribution or whether all three are necessary.

Questions for authors
  1. What source-record, parent-declaration, and canonicalized-query overlaps exist across supervision and each test set? Were perturbations grouped with originals? Please provide the exclusion procedure/manifests, or results with declaration-disjoint splits formed before augmentation.

  2. On the same shortlist, how does the proposed CM compare with original CM? What are the graph controls' parameter counts, and do gains persist with matched capacity?

  3. Can ReProver or LeanPremise be compared on common eligible queries, visible candidates, and hit criteria? Is there evidence that the retrieval gains improve tactic success or proof completion?

  4. How much does each preprocessing step contribute? Could you report a raw baseline and leave-one-step-out results, since Table 4 compares the full pipeline only with individual-rule variants?

3 comments
AuthorsOpenReview ↗

Response to Reviewer J9F9(1/2)

Thank you for recognizing the complementarity of learned and structural scores and for your detailed suggestions on data independence, controlled comparisons, and preprocessing ablations.

W1 / Q1. Independence between supervision and test queries

The supervision pool and each of Test-A/B/C are disjoint at the canonicalized complete-query level, where a complete query consists of the proof-state goal and local context. We audited all 44,000 supervision records, including original and selected perturbed queries, and found zero complete-query overlaps with each test set. This also holds for Test-C, although its queries and the supervision records both originate from Mathlib rw steps.

As specified in the paper, the retriever uses the goal expression obtained by reverting the local hypotheses; the parent-declaration identifier is not supplied to the ranker. Different proof steps within one declaration can yield different goals and local contexts, while the same complete query can occur in different declarations. Parent-declaration identity therefore does not determine whether retrieval inputs are duplicates. For the supervision–test overlap check, we compare complete canonicalized queries directly. An additional exclusion of all queries sharing a parent declaration is unnecessary for removing duplicate query inputs and would also discard distinct proof states.

As described in Appendix D.3, we combined 40,000 original query–premise pairs and 4,000 selected syntactically perturbed pairs. Perturbations modify the query expression while retaining its premise label. We compared both original and selected perturbed queries against the test sets and excluded duplicates at the complete-query level.

The supervision data come from Mathlib rw steps. Test-A and Test-B are from Tree-Based Premise Selection for Lean4: A contains 100 small problems constructed through transformations; B is extracted from exact tactic calls in real Lean proofs, pairing the proof state before execution with the theorem used. The original B contains 6,119 pairs; after aligning the Mathlib version and removing unavailable theorems, we retain 6,104 queries. Wang et al., 2025, Section 5.1 and Appendix E.2.2 We extracted Test-C from rw tactic steps, yielding 12,494 queries that record the goal and local context before rewriting, together with the theorem used. The test examples in A/B/C are mutually disjoint.

W2 / Q2. CM refinements and graph encoder controls

Original CM versus proposed CM. On the same top-2,000 embedding shortlist, we compare both CM variants and their fusion with R-DGCN on all Test-B queries. Original CM uses the open-source implementation of Wang et al. (2025).

Ranking methodR@1R@5R@10MRR
original CM15.9923.9725.8719.62
R-DGCN-only20.9528.0547.5826.92
proposed CM23.5340.2442.6932.07
R-DGCN + original CM22.9032.0855.2130.29
R-DGCN + proposed CM29.5141.8464.4037.91

With the encoder, preprocessing, top-2,000 visible-premise shortlist, and fusion coefficients fixed, the proposed CM improves all four retrieval metrics over original CM, including a 9.19-percentage-point gain in fused R@10. This controlled comparison supports the matching refinements as a group. The refinements preserve flexible matching for variables and instance evidence while distinguishing concrete symbols and respecting the order of candidate subexpressions.

Model capacity and graph structure. The three GCNs share supervision, splits, negative-sampling settings, and training budgets, with encoder-only ranking. All three GCNs have parameter counts on the order of 10510^5. Merging relations shares transformation matrices and reduces parameters. The role-sequence Transformer matches R-DGCN's parameter count to within about 0.19%.

Encoder / relation configurationParametersR@1R@5R@10MRR
Full R-DGCN399,80920.9528.0547.5826.92
Capacity-matched role-sequence Transformer400,57613.0219.6823.7517.32
Directed untyped GCN154,04915.6522.2042.9921.68
Role-only undirected GCN163,7162.2423.3827.709.40

R-DGCN outperforms the role-sequence Transformer on all four encoder-only metrics. The relation ablations show lower performance when transformations are shared across syntactic roles or message directions.

AuthorsOpenReview ↗

Response to Reviewer J9F9(2/2)

W3 / Q4. Incremental contributions of preprocessing steps

On 604 Test-B queries selected for lower combined scores, we compare the full pipeline, Raw (all three rewrites disabled), and three leave-one-step-out variants. All configurations use the same queries, CSE pass, and fixed retriever.

Query-side preprocessing configurationR@1R@5R@10MRR
Full pipeline10.2621.1935.2616.48
Raw + CSE (all three rewrites disabled)5.4612.9126.1610.21
Full pipeline without binder simplification9.2719.5433.9415.23
Full pipeline without wrapper stripping5.4612.7526.6610.23
Full pipeline without arithmetic normalization9.7719.8733.6115.56

Retaining binder simplification, wrapper stripping, and arithmetic normalization improves R@10 by 1.32, 8.60, and 1.65 percentage points, respectively, compared with removing each step from the full pipeline. The full pipeline also leads on R@1, R@5, and MRR. Wrapper stripping provides the largest gain and enables the arithmetic normalization rules to apply in these queries, illustrating how the preprocessing steps work together.

Q3. ReProver comparison and proof success

Comparison with ReProver. All methods are evaluated on the same 6,104 Test-B queries. For each query, R-DGCN and ReProver retrieve from the same set of theorem declarations visible in the current Lean proof state, with the parent declaration excluded. The resulting rankings are evaluated using the same hit criterion. ReProver fine-tuning matches R-DGCN's supervision source, sample composition, and negative-sampling policy and checkpoint selection by validation loss.

MethodR@1R@5R@10MRR
R-DGCN-only20.9528.0547.5826.92
R-DGCN + CM29.5141.8464.4037.91
ReProver (public checkpoint)3.676.247.635.02
ReProver (fine-tuned with the same supervision)8.7514.8917.5011.78
ReProver (fine-tuned with the same supervision) + CM7.8314.1917.4611.04

Fine-tuning improves ReProver on all four metrics, while R-DGCN-only retains its lead before CM reranking. The encoder-only comparison therefore supports the competitiveness of the learned graph representation against a pretrained sequence retriever adapted to the same premise-retrieval task.

Single-step tactics and complete proofs. The retrieval gains translate into higher Lean-verified single-step success with the same ReProver generator and generation budget. With both methods supplying the top 10 currently visible premises, R-DGCN + CM closes 47 additional goals across 6,104 Test-B queries, improving success by 0.77 percentage points (95% confidence interval: 0.50–1.06, paired bootstrap clustered by parent declaration). On 200 preselected declarations, the complete-proof evaluation yields 48 successful proofs versus 41, a difference of 3.5 percentage points (paired 95% confidence interval: −0.5–8.0). All successful proofs pass independent Lean compilation and axiom-dependency checks.

Both retrievers use the same initial Lean states and fixed ReProver generator, supplied only with the current proof state and top 10 visible premises. Single-step success requires Lean-verified closure of the goal and all subgoals within 32 suggestions per query. For complete proofs, we remove proofs from 200 distinct parent declarations selected by a prespecified rule and run best-first search from their initial goals, retrieving at every expansion with a 600-second limit per declaration. Initial states were restored for 3,734 of 6,104 queries and 194 of 200 declarations; restoration failures and timeouts count as failures.

Retrieval methodSingle-step tactic success (%)Proof completion (%)
Tree-based Search7.7520.50
R-DGCN + CM8.5224.00

When integrated into ReProver, R-DGCN + CM increases Lean-verified tactic success and yields a higher complete-proof rate in the evaluated sample. The statistically supported single-step gain demonstrates a contribution to proof generation, while the positive complete-proof estimate suggests that these benefits can extend to end-to-end proof search.

Thank you again for your constructive feedback. We hope that our responses have adequately addressed your concerns and would greatly appreciate your consideration of our clarifications in your overall assessment. We would be happy to address any further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.