- 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
- 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?
- Does the effect persist when the encoder trained from scratch is instead a pretrained language encoder (domain adapted on Lean)?
- 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 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.
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:
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.