- 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
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.
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).
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.