acceptodds
Under review as a conference paper at ICLR 2027

What Should a Theorem Prover See? Names, Notation, and Structure in Lean

Abstract

Research on machine theorem proving has mostly improved models and search, and has paid less attention to a more basic choice: how a proof state is represented to the learner. The same proof state can be written in quite different surface forms, which may change the statistical structure a model can exploit. We study this problem in Lean, where a proof state can be written in several equivalent ways and every generated proof can be checked mechanically. We define a representation by three independent choices: identifiers (I), preserving or standardizing local variable and hypothesis names; core syntax (C), writing terms in conventional notation or in Lean’s elaborated core syntax; and relations (R), supplying or withholding explicit links between related parts of the state. We introduce ICR, a framework for controlled factorial experiments over these three factors. Training small encoder-decoder models from scratch on Mathlib proof states, with architecture, optimization, and examples held fixed, we compare all eight combinations of I, C, and R. We find that the representation has a large effect on theorem proving, and that the three factors behave very differently. For C, contrary to the common intuition that a more explicit input helps the learner, conventional mathematical notation consistently outperforms Lean’s elaborated core syntax: it improves prediction of the next step and proves 24 to 43% more unseen Mathlib theorems, a larger gain than nearly tripling the model size. This advantage persists even when both representations fit within the model context, so input length alone cannot explain it. For I, we find that models use statistical signal in identifier names: renaming variables and hypotheses more than halves, on average, the probability assigned to the author’s next proof step, even when that step does not mention them. Standardizing names removes this sensitivity, although its effect on proving theorems varies across benchmarks. For R, removing the explicit links from trained models barely changes the probability of the correct step, suggesting that providing structure does not mean that a model will use it. In our setting, the choice of representation mattered as much as a substantial increase in model scale, and sometimes more.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
automated theorem proving, proof state representation, representation learning, formal reasoning, Lean, tactic prediction, inductive biases

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_8U9rOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper asks whether representation affects machine theorem proving. Representation is decomposed into Identifier labels, Core syntax, and Relations between different parts of the state. All 8 possible variations are studied by training an encoder-decoder pair from scratch, with evaluation along each decomposed axis done by averaging the 4 runs with the other factors varied.

Critical strengths
  • The paper draws attention to an interesting idea that most in the AI community might be unfamiliar with, while two correct proofs of the same theorem are equivalent for Lean, they can have very different likelihood of being produced by a language model.
  • The ICR decomposition is a useful framing for analysing which proofs are easier to produce for a statistical model.
Critical weaknesses
  • Likelihood of next proof step is a flawed evaluation metric since multiple proofs for the same statement are possible. It is also more trivial to state that representation influences the predictability of the next step rather than the correctness of the final proof produced.
  • Since all configs are trained from scratch, it becomes harder to estimate how this finding will find application in LLMs, which have already been exposed more to some representations over others during pretraining.
  • While the results are interesting, the setting in which the effect is studied feels poorly motivated given the actual usage of theorem provers by the AI community. The representation choices supported by the paper's findings are also largely used already, which further makes the findings less actionable.
Questions for authors
  1. Since the effects are only established on Lean, it is unclear if the finding reflects something in Lean or theorem provers in general. Can the authors justify why they believe this will hold for other theorem provers?
  2. Does the effect persist when the encoder trained from scratch is instead a pretrained language encoder (domain adapted on Lean)?
  3. Since the encoder-decoder was trained from scratch, do the authors have a mechanistic guess for why aligning with conventions of human mathematics improved performance?
4 comments

Thank you for your time and thoughtful questions. Your review showed us that the paper does not make some central points prominent enough, and we are sorry for the effort this cost you. We are not uploading a revised PDF right now; we will upload it in a few days, with these points made clearer.

W1. Likelihood as a metric. We fully agree: many proofs establish the same statement, so next-step likelihood alone would be a weak basis, and final-proof correctness is what matters. We should have made clearer that this is what our main results measure. Section 3.3 opens: "Our primary measure is Solve@64, the fraction of theorems proved within 64 search expansions, with every proof checked by Lean." It accepts any proof Lean verifies, not only the author's. Table 1 and Figure 1 report only theorems proved. Surface-notation models prove 24–43% more held-out Mathlib theorems than core-syntax models in all four size/seed blocks, and every Small surface model at 16 expansions outproves every Medium core model (2.7× the parameters) at 64 (Section 4.1). Likelihood serves only as a diagnostic of what a trained model relies on. The revision will state this distinction up front.

W2. Training from scratch. This is a fair limitation, and we accept it. We trained from scratch for the reason you mention: pretrained LLMs have seen some representations far more than others, so a comparison on top of pretraining would mix that exposure with the representation itself. Identical random initial weights let us attribute differences to the representation alone. The cost is as you describe: we cannot say how the effects transfer, and our Limitations note they "may weaken or reverse for larger or pretrained provers." We see this as a controlled first step, not an answer.

W3. Motivation and actionability. Thank you; we did not motivate the setting well. Our aim was a measurement, not a competitive prover. We followed the step-prover formulation of earlier work such as PACT (Han et al., 2022) and LeanDojo (Yang et al., 2023): a tactic generator that reads the proof state, with search and verification, minus pretraining (see W2). You are right that our notation result supports common practice. We would only add that the question still seems open: work discussed in Section 2 gives models structured kernel terms or graphs (CoqGym, Graph2Tac). Two other findings concern things current practice does not check:

  • Names: renaming hypotheses leaves the mathematics unchanged but lowers the correct tactic's probability by 2.0–2.5× (Section 4.2). Original-name evaluations cannot reveal this.
  • Structure: relation biases can be removed from trained models with almost no change (Section 4.4).

Both checks can be run on any prover. We also show that token loss can improve while whole tactics become less likely (Eq. 4).

Q1. Other provers. We cannot answer with evidence: our experiments use only Lean, and we do not claim more. The revision will say so in the Limitations. It seems worth testing because Coq and Isabelle share the ingredients (human-facing notation over explicit internal terms, author-chosen names, human-written tactic scripts), and Passport (Sanchez-Stern et al., 2023) finds that identifiers help in Coq. Magnitudes may differ, as Lean's elaboration is heavy (core states are about 8× longer).

Q2. Pretrained encoder. We have not run this, so we do not know. Such an encoder has already seen surface Lean, so it answers a different and practically important question. We list it as future work and agree it is the natural next study.

Q3. Mechanism. We can offer only a guess. Training from scratch removes prior knowledge from the model, not from the data. Every Mathlib tactic was chosen by a person looking at the surface state with those names, so a randomly initialized model can learn the conventions as statistical regularities. For names we have direct evidence: the renaming intervention changes only the names, and the penalty persists on the 73 states with unchanged token count (Section 4.2). For notation, one possibility is that tactics are written in surface syntax and so share vocabulary with surface inputs (Section 4.1). Our checks rule out the context limit but do not separate the other candidates; we will state this more carefully.

Thank you again. If these clarifications resolve some of your concerns, we would be very grateful if you would consider them in your assessment. Again, we thank you very much for engaging with our work so closely.

Thank you for the detailed response. I noted that the final metric is Solve@64 initially, was just confused why likelihood was used however I can see that it doesn't need CPU cycles on lean processing so can act as a useful proxy.

Overall, I have no doubts about the soundness of the contribution but am not convinced that the scope and choice of the experiments leaves the community with many actionable insights. The systems that are generally used by the community to produce machine-checkable proofs are often fairly different from the ones trained from scratch evaluated in the paper. Further, since the experiments only use lean, we also can't guess if the results are caused by some fundamental principle of machine-checkable representations which would be a generalizable finding. As a result, I do not wish to revise my score.

Thank you for the follow-up, and for confirming that you have no concerns about soundness. As promised, we have uploaded the revised PDF. Changes made for your review are in teal: the introduction now states that verified proof search is the primary outcome and likelihood a diagnostic, the Limitations state that all experiments use Lean, and the conclusion lists a pretrained encoder adapted to Lean, and other proof assistants, as future work.

We understand your view on scope. We agree that one proof assistant and small models trained from scratch cannot establish a general principle, and the paper does not claim one. What we expect to be most directly useful is less a recommendation about notation than three checks that need no retraining, so they can be run on existing step provers, including pretrained ones, as they are: renaming local names in a fixed checkpoint, deleting supplied structure at inference, and comparing likelihood per action rather than per token. Thank you again for engaging with the paper.

Dear Reviewer, given the divergence in the current ratings, please let us know whether the authors’ rebuttal and other reviewers’ comments change your opinion.

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

This work studies how proof-state representations affect neural theorem proving in Lean. It introduces ICR, a controlled factorial framework that varies three representation factors: identifiers, core syntax, relations. They then train 32 encoder-decoder models across eight configurations, 2 model sizes, and 2 random seeds. Evaluation includes next-tactic likelihood and kernel-verified proof search on Mathlib, miniF2F, and ProofNet Verified. Overall, surface notation substantially outperforms elaborated core syntax; identifier names provide useful predictive information; explicit structural relations have negligible direct influence on trained models using the proposed attention-bias mechanism.

Critical strengths

The complete factorial design, matched training conditions, and mechanically verified proof search make this a particularly convincing empirical study. The experiments substantially reduce architectural and training confounders. This strengthens the credibility of the observed representation effects.

The semantics-preserving renaming experiment provides strong evidence that models exploit incidental identifier information. Similarly, the relation-removal interventions distinguish improvements associated with training from reliance on structural information at inference. This demonstrates an important evaluation pitfall when comparing representations with different target lengths. These insights have methodological value beyond the specific prover studied.

Critical weaknesses

The core representation simultaneously introduces longer sequences, explicit type information, fully qualified constants, a different serialization grammar, and reduced syntactic alignment with the output tactics. Although it is established that context-window truncation alone cannot explain the performance difference, it does not establish that familiar notation is the main causal factor. Even short core sequences may be substantially more difficult to learn. A length-controlled comparison or an intermediate representation that preserves familiar notation while exposing additional information would be helpful.

Both evaluated architectures are small and trained from scratch. Consequently, it remains unclear whether the conclusions extend to large pretrained theorem provers, where mathematical notation and structural information may already be represented differently.

Questions for authors

Clarifications / additional analysis that resolve some of the main concerns above would be helpful. For example, some questions worth answering might be: Is there any additional analysis or ablation that isolates the effect of familiar notation from the much greater sequence length and input-output mismatch of core syntax? In particular, would the authors expect the conclusion to hold for a more compact elaborated representation? Given the sparsity of the relation biases, is there evidence that the model actually attends to the structurally related token pairs? How can the negligible ablation effect be distinguished from insufficient capacity or strength of the chosen relation-injection mechanism?

Evaluating larger pretrained models and more expressive structural encoders would be valuable, but I do not consider these necessary here. Might be good to explore in future work.

3 comments

Thank you for the careful review, and for separating what you consider necessary from what belongs to future work. We have uploaded a revised PDF. Changes made for your review are in orange. Where another reviewer asked the same question, the change carries that reviewer's colour, so we give locations below.

W1 / Q1. Notation versus length and input–output mismatch. We agree. Enabling C changes input length, explicit types and implicit arguments, fully qualified constants, the serialization grammar, and the match with the tactics, all at once. Our checks rule out context-window overflow, not length, and they do not show that familiar notation is the cause. The revision now says so. The abstract reads "context-window overflow alone does not explain it". Section 4.1 lists the bundled changes and labels the input–output match as a hypothesis we do not test. Section 4.1 and the introduction no longer attribute the result to "familiar" notation.

Our data do not allow a length-controlled comparison. No core input among the 7,616 test examples is as short as its surface form, and at most four are within a factor of two. Even in the shortest stratum (689 states, all views within 512 tokens), core inputs are 3.7–3.9 times as long, and core models still have 0.086–0.107 nats more loss per token. The penalty is positive in every length stratum and in every quartile of the core/surface length ratio, which is consistent with your point that even short core inputs may be harder to learn.

Two conditions in the paper keep surface notation and add information, though neither isolates notation. In the exploratory PAIR runs (Appendix D), which add structural records to cell 101 (records reach about 5% of states), Mathlib solves (PAIR vs 101) are 74 vs 74, 71 vs 69, 80 vs 72, and 77 vs 77. Adding relations to surface inputs changes Mathlib solves by −3 to +3 theorems per cell (Table 1), and the overall R effect on Mathlib has an interval that includes zero in every block.

Q2. A more compact elaborated representation. We do not know. The gap might narrow, since elaboration writes out implicit arguments and instances that a selective representation could omit, but we have not measured how much of the extra length they account for. The conclusion now lists this as future work.

Q3. Do the models attend to the linked pairs? Barely, if at all. For the 16 checkpoints with I=0 (with and without relations, both syntaxes, sizes and seeds) and 128 held-out states, we compared each linked pair's attention weight, per layer and head, with the mean weight on unlinked pairs at the same token offset in the same state, which controls for locality. Linked pairs receive 0.90–1.29 times that baseline with surface inputs and 0.46–1.01 times with core inputs, and only 21–32% of them exceed it. The biases do move linked attention, by 1.5–7.8% in relative terms (Section 4.4, Table 18, in crimson for Reviewer UPya), but removing them changes this ratio by at most 0.011. This analysis is new in Section 4.4 and Appendix C.3 (Table 19).

Q4. Unused information, or too weak a channel? We cannot fully separate the two, and the Limitations now say so. Three observations bear on it. First, models trained without relations attend to linked pairs just as the R=1 models do: their ratio is within 0.04 of their R=1 counterparts in seven of eight pairs (the exception, Small seed 0 with core inputs, attends less with relations). So the null result is not explained by the models already attending along these links without help. Second, core inputs carry every semantic edge, against 11% for surface inputs, yet removing the edges matters just as little; it changed no generated beam in any core checkpoint. Third, the learned biases stay small, with mean absolute values of 0.010–0.037. This leaves your reading open: one scalar per relation feature, layer, and head may simply be too weak a channel, so Section 4.4 and the conclusion now limit the claim to the scalar biases we tested.

W2. Small models trained from scratch. We accept this limitation. Training from scratch lets all eight cells share initialization and data, and it removes unequal pretraining exposure to surface notation, but it limits what we can say about pretrained provers. The conclusion now names a pretrained encoder adapted to Lean as future work.

A decoder check. Prompted by another reviewer, we reran search post hoc with the internal beam widened from 8 to 16. On Mathlib, surface inputs still prove more theorems in all four blocks: 2.10–3.03 points, or 15–24% more solves, with every interval above zero. On miniF2F the advantage shrinks to 0.10–1.54 points, with intervals that include zero, so the abstract now claims it only at the narrower width (Section 4.3, Appendix B.7). The likelihood gap (1.644–1.957 nats per action) and the renaming penalty involve no decoding.

Thank you again. We would be grateful if you would consider these changes in your assessment.

Dear Reviewer, given the divergence in the current ratings, please let us know whether the authors’ rebuttal and other reviewers’ comments change your opinion.

Thank you for the detailed rebuttal and substantial revisions. I appreciate the additional experiments and the careful narrowing of the claims.

The clarification that the surface/core comparison does not isolate notation from sequence length and other representation differences addresses my main concern about causal interpretation. The beam-width experiments strengthen the Mathlib result, while the new attention and behavioral analyses provide useful evidence that the tested relation-bias mechanism has little practical effect.

My main remaining reservation is that the underlying causes of the surface/core performance gap remain unresolved. In particular, it is still unclear how much of the advantage would persist with a more compact elaborated representation. The reduced miniF2F advantage at beam width 16 also suggests some sensitivity to decoding choices. However, I agree that resolving these issues would require additional experiments possibly beyond the current scope of this paper.

Overall, I find the revised claims appropriately qualified, and the rebuttal strengthens my confidence in the empirical conclusions. I remain supportive of acceptance and will maintain my original positive rating of 3.

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

ICR studies three Lean proof-state representation choices: canonical local identifiers (I), elaborated core syntax instead of surface notation (C), and typed attention biases (R). Its matched factorial experiment trains 32 models across eight representations, two sizes, and two seeds, evaluating tactic likelihood and verified search on Mathlib, miniF2F, and ProofNet. Surface notation yields 24–43% more Mathlib solves; its advantage also appears on miniF2F but not consistently on ProofNet. Renaming interventions demonstrate dependence on local names even when targets remain unchanged. Canonicalization removes this sensitivity without consistently improving search, while removing relation edges barely changes average gold-tactic likelihood. The paper also shows how target-length changes can make token-level loss comparisons misleading.

Critical strengths
  1. Careful controls and meaningful outcomes. The eight-cell design matches data, tokenizer, initialization, batching, and optimization within each size/seed block, then evaluates kernel-verified proofs (Section 3; Appendix A). The averaged surface/core advantage recurs across all four blocks on Mathlib and miniF2F. On Mathlib, every Small surface run at 16 expansions exceeds every Medium core run at 64 (Table 8). Short-state and root analyses strengthen the result by addressing context overflow.

  2. Informative interventions. The renaming experiment fixes model weights and target bytes while verifying semantic equivalence and successors in Lean (Section 4.2). Its 0.710–0.900 nats/action penalty demonstrates useful signal in names beyond copying them into tactics. Separating token-level from action-level likelihood also avoids misleading conclusions about canonicalization. These are useful contributions within the studied setting.

Critical weaknesses
  1. The abstract overstates what the length controls establish. Section 4.1's short-input and first-root-candidate checks show that context overflow is not the sole explanation for the surface/core gap. They do not separate the burden of longer sequences from changes in notation, types, implicit arguments, and qualified names. The limitations explicitly acknowledge this, so the abstract's “input length alone cannot explain it” should be narrowed accordingly. This concerns the explanation of the result; the measured performance advantage remains supported.

  2. The relation intervention lacks behavioral validation (a minor concern). Section 4.4 reports tiny mean gold-tactic NLL changes, with every 95% interval within ±3.5×10⁻⁵ nats/token: strong evidence of negligible average loss effects. However, Appendix C.2 does not evaluate altered relations during generation or proof search. Conclusions about “barely used” structure should remain specific to this loss metric and scalar-bias mechanism unless supported by beam or search diagnostics. This is a limit on interpretation, not evidence of substantial hidden effects.

Questions for authors
  1. Is there evidence beyond context-overflow controls for the abstract's claim that “input length alone cannot explain” the surface/core gap? Otherwise, can the statement be narrowed to match Section 4.1 and the limitations?

  2. After removing/shuffling relation edges, what fraction of generated beams changes? Absolute per-state action-NLL changes would also show whether the small average effect is consistent across states.

  3. As a clarification, does finite token-level beam search or the 64-token cap contribute to canonicalization's miniF2F result? I changes both inputs and output encoding, while frontier normalization leaves generation unchanged. Candidate-length/cap diagnostics could assess this possible contribution; longer tokenization alone does not establish a disadvantage.

3 comments

Thank you for distinguishing so clearly between the result and its explanation, and we thank you for engaging with our work so carefully. We narrowed the abstract as you suggested, ran both relation checks you asked for, and reran full search with a wider beam. The main result holds: on Mathlib, surface inputs still beat core inputs at beam width 16 in all four blocks. Changes are in purple: Abstract, Introduction, Sections 3.3, 4.1, 4.3, 4.4, Conclusion, Limitations, and Appendices B.7 (Tables 13–15) and C.3 (Table 18).

Main result under a wider beam. We reran all 32 checkpoints on the 512 Mathlib test theorems with the internal beam widened from 8 to 16. The surface-minus-core Solve@64 advantage is +2.10 to +3.03 points across the four blocks (15–24% more solves, against 24–43% at width 8), and every paired 95% theorem-bootstrap interval is above zero. Only in Medium seed 1 does the narrowing exclude zero (4.74 to 2.64 points; change −2.10 [−3.61, −0.63]). The 17 worker errors count as nonsolves. The Small-versus-Medium comparison you cite (Table 8) is now labelled width 8; at width 16, seed 1, it fails even at the full budget (Appendix B.7). These reruns are exploratory; their intervals condition on the trained checkpoints and are not adjusted for multiple comparisons.

W1 / Q1. Input length and context overflow. You are right. Our checks show that context-window overflow alone does not explain the surface/core gap; they do not separate length from notation, explicit types and implicit arguments, qualified names, or input–output mismatch. Even in the short-state subset (689 states, all views within 512 tokens), core inputs are still 3.7–3.9 times as long on average. The abstract now reads: “This advantage persists even when both representations fit within the model context, so context-window overflow alone does not explain it.” We have also narrowed Section 4.1.

W2 / Q2. Do the relations change predictions? On the original 1,024 held-out states and eight R-on, I-off checkpoints, the per-checkpoint mean absolute change in complete gold-action NLL is 0.0002–0.0047 nats for removing edges and 0.0002–0.0053 for shuffling them. Per-checkpoint 95th percentiles reach 0.0175 and 0.0195 nats. The largest individual changes, 0.116 and 0.115 nats, are 6–8 times smaller than the average renaming penalty in Section 4.2 (0.71–0.90 nats). We also generated beams on the first 128 states in the existing hash order, for the same eight checkpoints. Removing edges changed the ordered eight-candidate beam in 10/1,024 checkpoint–state comparisons (0.98%); shuffling changed it in 14/1,024 (1.37%). The candidate set changed in 6 and 8 cases, and the top candidate in 1 and 3. No beam changed in any core checkpoint, even though core inputs carry every edge. These are repeated states across checkpoints, and they measure generation, not proof search. We now restrict our conclusion to the scalar attention biases tested; we do not claim that structure in general is unused.

Q3. Does decoding contribute to the miniF2F result? Yes: the finite beam can contribute substantially; we found little evidence that the cap does. We agree that frontier normalization leaves the token-level beam unchanged, and checkpoints, 3 of 372,613 candidates reach 64 tokens. On 64 hash-selected miniF2F roots and the eight 000/100 checkpoints, raising the cap from 64 to 128 tokens changed none of the 512 ordered root beams. In a separate example selected because a candidate reached the cap, the higher cap added two longer candidates, so we cannot rule out a cap effect elsewhere in search.

We then reran full miniF2F search for all 32 checkpoints at width 16. Both widths use the 64-token cap and 64-expansion budget and submit at most eight tactics to Lean per expansion; width 16 uses more decoding compute. The I-on minus I-off Solve@64 effects (surface inputs, averaged over R) change from −1.02 to +0.82, −7.58 to +3.48, −4.92 to −1.23, and −3.48 to −6.15 points for Small seed 0, Small seed 1, Medium seed 0, and Medium seed 1. The Small seed-1 change is +11.07 points [+6.35, +15.98]; the other change intervals include zero. At width 16, only the Medium seed-1 effect has an interval excluding zero, so the original-name advantage persists there. Canonicalization's miniF2F effect therefore can depend substantially on the decoder; this experiment does not identify why. The wider beam also shrinks the miniF2F surface-minus-core advantage to +0.10 to +1.54 points, with intervals that include zero, so the abstract now claims the miniF2F advantage only at the narrower width.

In short: the likelihood gaps and the renaming penalty involve no decoding, and the Mathlib advantage holds at both widths; the miniF2F search effects depend on beam width, and the paper now says so.

We would be grateful if you would consider these results in your re-assessment. We also apologize for the delay in replying back.

Dear Reviewer, given the divergence in the current ratings, please let us know whether the authors’ rebuttal and other reviewers’ comments change your opinion.

Thank you again for your careful and thoughtful review of our work.

We sincerely apologize for following up once more. As the discussion period is nearing its end, we would be very grateful if you could kindly take another look at our response and the revised manuscript, and let us know whether the additional analyses and clarifications have addressed your concerns.

We completely understand that you may be busy, and we genuinely appreciate the time and effort you have already devoted to reviewing our paper.

Thank you very much again for your time and consideration.

Reviewer_UPyaOpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how the representation of a proof state affects learning-based theorem proving in Lean. The authors introduce ICR, a factorial framework that varies three representation factors: identifier naming (I), surface notation versus elaborated core syntax (C), and explicit structural relations (R). They train 32 encoder-decoder models across two model sizes and two random seeds, keeping the training data and optimization protocol matched across conditions. On Mathlib and miniF2F, surface notation consistently outperforms core syntax. The paper also finds that models are sensitive to local identifier names, while the provided relation-based attention biases have almost no effect on predictions once the models are trained. These findings are supported by likelihood measurements, Lean-verified proof search, and interventions on fixed checkpoints.

Critical strengths
  1. A carefully controlled comparison of representation choices: The paper isolates representation changes while holding the training population, tokenizer, initialization, optimization schedule, and search procedure fixed. The advantage of surface syntax is substantial on Mathlib and miniF2F.
  2. The interventions reveal behavior that ordinary benchmark comparisons would miss: The identifier-renaming experiment is useful. By changing local names while preserving the proof state semantics and leaving the gold tactic unchanged, the authors demonstrate that models trained with original identifiers rely on their spelling. The complete-action NLL analysis also correctly identifies a potential problem with comparing token-level losses when the target representation changes.
Critical weaknesses
  1. The main surface-versus-core comparison does not identify which representation difference causes the performance gap: Enabling C changes several properties simultaneously. The authors provide useful controls for context overflow, but these do not separate the effect of longer sequences from the effect of unfamiliar notation or the mismatch between input and output syntax. The short-state results, for example, eliminate truncation as an explanation without eliminating the difficulty of learning from a much longer serialization. The results establish a clear performance difference between the two representations, but do not identify which aspects of the core serialization are responsible for that difference. This limits the mechanistic interpretation and practical guidance that can be drawn from the comparison.
  2. Limited generalizability of the representation findings: The results are convincing within the controlled experimental setting, but their broader applicability remains uncertain. In particular, R is implemented as learned scalar attention biases on directly linked token pairs. Although only 11.02% of semantic edges are projected in surface inputs, all edges are projected in core inputs, where removing the biases also has negligible impact. These results demonstrate the limited use of this particular structural encoding, but do not establish whether richer structural representations would be similarly ineffective. More broadly, the experiments use relatively small models trained from scratch with only two seeds, and the surface-over-core advantage is not consistent on ProofNet Verified. It therefore remains unclear whether the main findings extend to larger pretrained provers or alternative structural encoders.
Questions for authors
  1. Section 4.1 suggests that the mismatch between core inputs and surface-form tactics may contribute to the observed gap. Is there evidence that favors this explanation over the increased sequence length or the additional syntactic detail?
  2. Section 4.4 reports the magnitudes of the learned relation biases, but their scale relative to the ordinary attention logits remains unclear. Could the authors quantify whether these biases meaningfully alter the attention weights assigned to linked token pairs?
3 comments

Thank you for the detailed review. We agree with both weaknesses and have narrowed the paper accordingly. We have uploaded a revised PDF. Changes made for your review are in crimson. Where another reviewer asked the same question, the change carries that reviewer's colour, so we give locations below.

W1. Which difference causes the surface/core gap? Our experiment does not identify it. The short-state and first-root-candidate checks rule out truncation and later-state overflow; they do not rule out length. In the 689-state stratum where every view fits in 512 tokens, core inputs are still 3.88 and 3.68 times as long as their surface forms (original and canonical names). No core input among the 7,616 test examples is as short as its surface form, and at most four are within a factor of two, so our data cannot separate length from the other changes. Section 4.1 now says this and lists what enabling C changes at once. What the matched comparison establishes is a performance difference between the two renderers as implemented. We agree that this limits the practical guidance: the result argues against feeding this core serialization directly, not against every elaborated representation. The conclusion now lists a more compact elaborated representation as future work.

Q1. Evidence favouring input–output mismatch? No. We proposed the mismatch as one plausible explanation, and nothing we measured favours it over the alternatives. The revision labels it a hypothesis we do not test (Section 4.1). The abstract now says "context-window overflow alone does not explain it". We also corrected the sentence that said the root comparison occurs "before length can interfere": the core root is itself longer.

Q2. Scale of the relation biases. We measured this on the eight R=1, I=0 checkpoints, using the first 32 states of the intervention sample. For each linked pair, head, and encoder layer, we compared the attention weight with and without that layer's relation bias, holding the layer's inputs fixed. Across checkpoints, the mean absolute bias is 1.4–6.3% of the standard deviation of the query's ordinary attention logits, and the mean absolute relative change in the linked attention weight is 1.5–7.8%. So the biases alter linked attention weights by a few percent: a real but small shift. This is a same-layer calculation on linked pairs and does not recompute earlier layers (Section 4.4; Appendix C.3, last two columns of Table 18).

Prompted by Reviewer 5wd7, we also asked whether the models favour linked pairs at all. For all 16 I=0 checkpoints and 128 states, we compared each linked pair's attention weight with the mean weight on unlinked pairs at the same token offset. Linked pairs receive 0.90–1.29 times that baseline with surface inputs and 0.46–1.01 times with core inputs, in models trained with or without relations, and removing the bias changes this ratio by at most 0.011 (Section 4.4; Appendix C.3, Table 19, in orange). So the bias shift does not make linked pairs stand out.

Downstream, removing the relations changes complete-action NLL by a per-checkpoint mean absolute 0.0002–0.0047 nats, with a largest single change of 0.116, and changes the ordered eight-candidate beam in 10 of 1,024 checkpoint–state comparisons (14 for shuffling). All of those beam changes occur in surface checkpoints; none occurs in a core checkpoint, where every edge is projected.

W2. Generality. We agree that these results concern one structural encoding. Section 4.4 is retitled and limited to scalar attention biases on directly linked token pairs. The Limitations state that richer encoders may use the same information, and now also that our results cannot tell whether the models do not need these relations or whether this channel is too weak to deliver them. We also agree with the other limits you list: two small sizes trained from scratch, two seeds (the second added after the first was observed, so it is a replication, not part of a preregistered design), and no consistent surface/core effect on ProofNet Verified. The abstract no longer says surface notation "consistently" outperforms core syntax; it names the benchmarks where it does. We do not claim that the findings extend to larger pretrained provers.

A decoder check. Prompted by another reviewer, we reran search post hoc with the internal beam widened from 8 to 16. On Mathlib, surface inputs still prove more theorems in all four blocks: 2.10–3.03 points, or 15–24% more solves, with every interval above zero. On miniF2F the advantage shrinks to 0.10–1.54 points, with intervals that include zero, so the abstract now claims it only at the narrower width (Section 4.3, Appendix B.7). The likelihood gap (1.644–1.957 nats per action) and the renaming penalty involve no decoding.

Thank you very much again. We would be grateful if you would consider these changes in your assessment.

Dear Reviewer, given the divergence in the current ratings, please let us know whether the authors’ rebuttal and other reviewers’ comments change your opinion.

Thank you for the detailed response and additional analyses. The rebuttal addresses my main concerns.

I appreciate the clearer distinction between the observed surface/core performance gap and its possible explanations. The revised interpretation appropriately limits the conclusion to the two renderers evaluated, without attributing the gap to a particular mechanism that has not been isolated.

The additional attention diagnostics also help clarify the role of the relation biases. Together with the original intervention results, they provide stronger evidence that the models make limited use of this particular relation channel, while leaving open whether richer structural representations could be more effective.

The beam-width experiment is also informative. It strengthens the evidence for the Mathlib result while showing that the miniF2F advantage is less robust to decoding choices than initially suggested.

Overall, I find the response satisfactory. The remaining limitations primarily concern the generalizability of the findings rather than the validity of the controlled comparisons. I therefore maintain my Weak Acceptance recommendation.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revisions and new Analyses

We thank all four reviewers for their careful reading. Their questions led directly to the new analyses below: the beam-width reruns, the behavioural checks of the relation intervention, and the attention comparison. We took a few extra days so that these could be completed before posting. We have uploaded a revised PDF, with changes coloured by reviewer: purple (Dykw), orange (5wd7), crimson (UPya), and teal (8U9r).

What holds. On 512 held-out Mathlib theorems, surface notation proves more theorems than elaborated core syntax in all four size and seed blocks: 24–43% more at the original beam width of 8, and 15–24% more (2.10–3.03 points, every paired interval above zero) in a new rerun of all 32 checkpoints with the beam widened to 16. The core-syntax likelihood gap (1.644–1.957 nats per action) and the renaming penalty (0.71–0.90 nats per action) involve no decoding.

What we narrowed.

  1. Cause of the surface/core gap (Dykw, 5wd7, UPya). Our checks rule out context-window overflow, not input length. The abstract and Section 4.1 now say so, list everything that enabling C changes at once, and label the input–output match as a hypothesis we do not test.
  2. miniF2F (Dykw). At width 16 the surface advantage shrinks to 0.10–1.54 points, with intervals that include zero, and the effect of canonical names changes with the block. The abstract now claims the miniF2F surface advantage only at width 8.
  3. Relations (Dykw, 5wd7, UPya). All claims are limited to the scalar attention biases we tested.
  4. Scope (5wd7, 8U9r, UPya). Lean only, with small models trained from scratch; pretrained encoders and other proof assistants are listed as future work.

New analyses, all post hoc on the existing checkpoints:

  • Mathlib and miniF2F search at beam width 16 for all 32 checkpoints (Appendix B.7, Tables 13–15).
  • Absolute loss changes and generated-beam changes when relations are removed or shuffled: about 1% of beams change, none in a core checkpoint (Appendix C.3, Table 18).
  • The scale of the relation biases relative to ordinary attention logits (Table 18).
  • Attention on linked versus distance-matched unlinked token pairs, in models trained with and without relations: linked pairs receive 0.90–1.29 times the baseline with surface inputs and 0.46–1.01 times with core inputs (Section 4.4; Appendix C.3, Table 19).

The matched factorial design, the 32 trained models, and the primary width-8 results are unchanged.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.