- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper studies the problem of determining whether two Lean formalizations are semantically equivalent.
Given two Lean formalizations, the goal is to determine whether they express the same mathematical statement.
A previous approach, BEq, checks equivalence by using a theorem prover to establish both directions of implication. Specifically, it assumes one statement and attempts to prove the other, then reverses the direction. If both implications are successfully proved in Lean, the statements are declared equivalent.
However, this approach can produce false positives. In particular, two mathematically unrelated statements may be declared equivalent if both are independently provable. A sufficiently powerful prover can establish each statement without relying on the other, thereby proving their logical equivalence even though they express different mathematical claims.
To alleviate this issue, the authors propose Structure-Aware Equivalence (SAE), implemented through the ACE framework.
The approach works as follows.
First, each Lean statement is normalized into a logical form consisting of a quantifier prefix, a sequence of hypotheses, and a conclusion. This involves a revert-like transformation of theorem arguments, extracting admissible quantifiers into an outer prefix, identifying the top-level hypotheses, and treating the remaining expression as the conclusion.
Next, ACE enumerates admissible alignments between the variables of the two statements. Each alignment must preserve variable types, quantifier kinds, and dependencies. For statements containing hypotheses, ACE then checks whether the conjunctions of their hypotheses are logically equivalent and whether their conclusions are logically equivalent under the same variable alignment. Both equivalences must be established independently of the original hypotheses. For statements without hypotheses, ACE instead compares the relational structure and corresponding operands of the conclusions.
If at least one admissible alignment satisfies all the required conditions, the statements are declared SAE-equivalent. If all alignments are ruled out, they are declared SAE-inequivalent. Otherwise, the result is inconclusive.
Experimental results show that ACE reduces false positives compared with existing approaches, particularly for unrelated but independently provable statements. However, this improvement comes at the cost of rejecting some genuinely equivalent formalizations. Moreover, since SAE still relies on logical equivalence within individual components, it mitigates rather than fundamentally eliminates the shared-provability problem.
Critical strengths
- The proposed approach can detect certain edge cases, such as mathematically unrelated but logically equivalent statements, that previous approaches fail to distinguish.
Critical weaknesses
- One criticism of BEq is that it may incorrectly classify mathematically unrelated statements as equivalent. However, I am not convinced that the proposed approach fundamentally change the situation. For example, consider:
theorem thm1 (a b : ℕ) (h : a + 0 = b) : a = b := by
sorry
theorem thm2 (a b : ℕ) (h : a * 1 = b) : a = b := by
sorry
After normalization, ACE can still prove the equivalence of the two hypotheses, since both a + 0 = b and a * 1 = b are equivalent to a = b. The conclusions are also identical. Thus, ACE would classify these statements as equivalent despite their different mathematical expressions. This suggests that the proposed method mitigates, rather than fundamentally eliminates, the limitations of BEq.
Questions for authors
see weaknesses
3 comments
Thank you for the response. I agree that my original example may not have been the most appropriate illustration of my concern.
However, unless I have fundamentally misunderstood the proposed approach, I believe my broader concern remains. I understand that SAE deliberately adopts a particular equivalence criterion rather than attempting to capture every human interpretation, and that this helps address certain failure modes of existing approaches. Nevertheless, I remain unconvinced that relying on component-level logical equivalence fundamentally resolves the shared-provability issue that motivates the paper.
Thank you for the follow-up. We would like to assert that component-level logical equivalence in SAE is substantially more restrictive than equivalence of complete theorem statements.
Under a single admissible alignment, SAE requires the corresponding premises and conclusions to be equivalent for every assignment of the aligned variables. Crucially, conclusion equivalence must hold independently of the premises, different from the whole-statement equivalence.
For example, consider:
Both statements are provable, and their binders, types, and premises are identical. However, SAE rejects their equivalence: the conclusions and are not equivalent for every integer (e.g., ). This distinction cannot be obtained through basic binder or type alignment alone.
Our new controlled experiments for reviewer MGZj confirm this difference. We constructed 30 pairs with matching variables, types, dependencies, and premises. On 10 premise–conclusion leakage cases, BEq accepted all 10 as equivalent, whereas ACE certified 4 as inequivalent and returned Inconclusive for the other 6, with no false equivalence judgments.
We also explicitly tested the remaining limitation. Among 10 pairs with distinct independently provable conclusions, ACE accepted 9. A stricter recursive comparator prevents some such acceptances, but also rejects legitimate reformulations: on 10 faithful-rewrite cases, ACE accepted all 10, whereas the stricter comparator accepted only 1. On 257 naturally occurring premise-bearing pairs already certified equivalent by ACE, the stricter comparator retained 228 as equivalent, rejected 3, and left 26 inconclusive.
SAE therefore does not universally eliminate shared provability, but its role-aligned, assignment-uniform equivalence provides a substantive restriction beyond whole-statement logical equivalence. The experiments make both its benefits and its remaining limitations explicit. Our contribution is to specify and certify this intermediate relation, rather than claim a universal solution to mathematical-intent ambiguity.
We thank the reviewer for the constructive feedback and welcome further questions.
The fundamental problem is specifying translation correctness before attempting to verify it. Syntactic equivalence is a precise but overly restrictive criterion: it rejects algebraic rewrites that preserve mathematical meaning. SAE instead explicitly specifies which mathematical roles must be preserved. Our goal is not to reproduce every human judgment, but to define an explicit equivalence criterion whose guarantees and empirical behavior can be systematically analyzed.
The proposed counterexample
The proposed example is correctly classified as equivalent under SAE's intended preservation policy. For all a,b∈N, a+0=b⟺a=b⟺a⋅1=b. Both hypotheses express exactly the same predicate over the same mathematical objects, and the conclusions are identical. SAE deliberately accepts such algebraic reformulations. Rejecting them would require a stricter, expression-sensitive criterion that also rejects legitimate rewrites, such as
Odd nversus¬ Even nin the ProofNetVerif equivalent caseexercise_1_27.The example illustrates why correctness must be specified before it can be certified. Whether translation fidelity requires preserving the original arithmetic expressions or merely the mathematical conditions they express is a choice of equivalence criterion. Human experts may reasonably differ on this selection. Neither follows automatically from the formal statements. SAE deliberately adopts the latter, more permissive policy within matched mathematical roles. By making this choice explicit, SAE allows its guarantees and limitations to be analyzed independently of proof-search strength. We do not claim that SAE captures every human interpretation or eliminates every shared-provability ambiguity.