SEMANTEQ: FAITHFUL BIDIRECTIONAL EQUIVALENCE OF FORMAL STATEMENTS
Summary (Overview)
- SemantEq introduces a principled equivalence relation for formal mathematical statements in Lean 4, defining when two statements are "mathematically equivalent in meaning" through a chain of four allowed step types: logical rearrangement, bridge rewriting, change of variables, and structural weakening.
- SemantEq-Eval, a deterministic search without a language model, achieves 100% precision and 65.6% recall on the ProofNetVerif test split (under adjudicated labels), outperforming the prior BEq+ system (95.8% precision, 61.8% recall).
- SemantEq-ProofAudit audits proof terms from any prover (including language models), accepting 330 of 407 equivalent pairs under the best prompt while rejecting all 104 non-equivalent pairs — a key improvement over compilation-only checks which accept ~40% of non-equivalent pairs.
- The paper demonstrates that separating proof generation from proof acceptance allows stronger provers to raise recall without compromising precision, as acceptance criteria remain fixed regardless of the prover.
- The method requires a trusted formal reference and checks agreement with it, not with the informal source directly.
Introduction and Theoretical Foundation
Background and Motivation
Formal theorem proving has advanced rapidly on benchmarks like miniF2F, ProofNet, and PutnamBench, driven partly by the Lean kernel's reliable verification signal. However, while the kernel checks proofs against formal statements, it cannot verify that a formal statement faithfully captures its informal source. As provers grow stronger, the bottleneck shifts from proof correctness to statement correctness.
The core problem, termed "the Key Problem" (Biderman et al., 2024), is that many syntactically different outputs express the same content, yet the best tools for detecting semantic equivalence are the same language models being evaluated. For formal mathematics, a natural test — proving logical equivalence — proves too much: in Lean, Nat.Prime 5 and Irrational (Real.sqrt 2) are logically equivalent because Mathlib proves both, allowing each implication to ignore its antecedent entirely.
Prior Approaches and Their Limitations
BEq (Liu et al., 2025b) restricts proofs to limited transformations, using exact? and a language model restricted to eleven tactics. BEq+ (Poiroux et al., 2025) replaces the model with fixed deterministic strategies. Both check for the antecedent's name in the proof script, but this fails because:
- A closing tactic can prove the goal from library facts alone.
- A name appearing in a script does not prove the antecedent did any work.
Theoretical Foundation
The paper defines a faithful derivation relation with four step types:
Definition 1 (Faithful derivation). A statement faithfully derives with respect to library , written , when one of the following holds:
- Logical rearrangement: and where , holds under every interpretation, and every atom matters on both sides.
- Bridge rewriting: and (or exchanged) for some bridge whose hypotheses are provable in context.
- Change of variables: Either for a new variable, or and for a term built from context variables.
- Structural weakening: One-directional moves of pure logic (dropping conjuncts, adding disjuncts, witnessing existentials, adding hypotheses, removing implied hypotheses).
Definition 2 (SemantEq). Statements and are SemantEq over , written , if there are chains of faithful derivations from to and from to .
Proposition 1. The relation is an equivalence relation, and for all statements :
Proposition 2 (Strictly finer). Rearrangement, change of variables, and weakening alone relate strictly fewer statements than logical equivalence, meaning logic alone never identifies two statements by truth values alone.
The key assumption is that bridges — library theorems whose conclusion is an equality or biconditional — reflect how the mathematical community identifies objects and formulas of similar meaning.
Methodology
SemantEq-Eval: Proof Search Without a Model
Given reference and candidate , SemantEq-Eval:
- Accepts immediately if identical up to renaming and definitional unfolding.
- Attempts and , accepting only if both directions succeed.
Each direction runs five stages in order (cheap to expensive):
- Stage 1: Apply the antecedent directly to the goal.
- Stage 2: Rewrite both statements into normal form with fixed logical identities.
- Stage 3: Decompose into logical components and match piece-by-piece.
- Stages 4–5: Collect library equations/biconditionals matching parts of statements and rewrite with them.
Four audits guard against false acceptances:
| Audit | Purpose |
|---|---|
| Relevance | Refuses if stage procedures prove a goal part without the antecedent that the antecedent doesn't assert |
| Proof-term grading | Expands auxiliary constants, admitting only antecedent, logical rules, bridges |
| Explosion check | Fails proofs deriving False from context to conclude the goal (but allows refutations inside negations) |
| Antecedent-free replay | Reruns accepting transformations without the antecedent; discards if goal still closes |
SemantEq-ProofAudit: Auditing Supplied Proofs
For language-model-generated proofs, SemantEq-ProofAudit:
- Reads the proof term (not tactic script) that Lean checks.
- Assigns each position one of three roles: goal derivation, argument to antecedent, or rewrite justification.
- Admits only the antecedent, logical rules, and bridges on the goal derivation.
- Covers model-specific constructs: local lemmas, antecedent instantiation, and library facts at antecedent hypotheses.
Empirical Validation / Results
Head-to-Head on ProofNetVerif
Table 1: Equivalence judgements on the ProofNetVerif test split (1,303 of 1,452 pairs)
| Labels | System | TP | FP | FN | TN | Precision | Recall | F1 |
|---|---|---|---|---|---|---|---|---|
| Published | Ours | 242 | 0 | 229 | 832 | 100.0 | 51.4 | 67.9 |
| Published | BEq+ | 230 | 8 | 241 | 824 | 96.6 | 48.8 | 64.9 |
| Adjudicated | Ours | 242 | 0 | 127 | 934 | 100.0 | 65.6 | 79.2 |
| Adjudicated | BEq+ | 228 | 10 | 141 | 924 | 95.8 | 61.8 | 75.1 |
The review changed 102 labels (all from equivalent to non-equivalent), with every final decision made by a person.
Audit Ablation
Table 2: Contribution of each audit on the ablation set of 100 non-equivalent pairs
| Configuration | ProofNetVerif (50) | Added claim (18) | Neighboring theorem (14) | Unrelated fact (14) | Vacuous hypotheses (4) | Total |
|---|---|---|---|---|---|---|
| Ours, all checks | 0 | 0 | 0 | 0 | 0 | 0 |
| Without relevance | 0 | 15 | 4 | 0 | 0 | 19 |
| Without proof-term grading | 0 | 0 | 2 | 6 | 0 | 8 |
| Without explosion check | 2 | 0 | 0 | 0 | 1 | 3 |
| Without antecedent-free replay | 0 | 0 | 1 | 1 | 0 | 2 |
| Without all four | 2 | 17 | 7 | 7 | 2 | 35 |
| BEq+ (our toolchain) | 10 | 18 | 9 | 13 | 4 | 54 |
Each audit catches its own family of errors, and removing all four admits 35 pairs — more than the sum of single removals.
Search Saturation
On the equivalent set (407 pairs), the base configuration accepts 65.4%. Increasing search budget shows diminishing returns:
- Doubling bridge pool adds 2 pairs; second chained rewrite adds 1 (total 66.1%).
- Eight stronger configurations add zero additional pairs.
- Mean time grows from 50.7 to 271.3 seconds; median stays at 2.0 seconds.
The saturation reflects that missed pairs need steps the search cannot take (building new objects, proving new bridges) — the bottleneck is the operation set, not the budget.
Language Model Results
Table 3: Certificates on the certification set (407 equivalent, 104 non-equivalent pairs)
| System | Equiv. both | Non-equiv. both | Precision | Recall |
|---|---|---|---|---|
| BEq+ | 245 | 2 | 99.2 | 60.2 |
| SemantEq-Eval (default) | 266 | 0 | 100.0 | 65.4 |
SemantEq-ProofAudit by prompt style:
| Prompt | Equiv. both (407) | Non-equiv. both (104) | Precision | Recall |
|---|---|---|---|---|
| Expedient | 309 | 0 | 100.0 | 75.9 |
| Unrestricted | 322 | 0 | 100.0 | 79.1 |
| Faithful | 330 | 0 | 100.0 | 81.1 |
| Rewrite | 329 | 0 | 100.0 | 80.8 |
Critically, under expedient and unrestricted prompts, the model compiled both directions for 43 and 45 of 104 non-equivalent pairs — a compilation-only judge would accept them all, while SemantEq-ProofAudit rejected every one.
Theoretical and Practical Implications
Theoretical Contributions
- SemantEq provides a principled definition of statement equivalence that sits between too-strict definitional equality and too-loose logical equivalence, with proven properties (equivalence relation, implication of logical equivalence, strict fineness).
- The relation is library-dependent through bridges, making explicit that mathematical equivalence is relative to the community's identified identifications.
- Proof-term auditing (rather than tactic-script inspection) provides a more robust foundation for verifying that antecedents actually do work.
Practical Implications
- For benchmark evaluation: SemantEq-Eval offers a deterministic, CPU-only judge with perfect precision, suitable for filtering training data and evaluating formalizers.
- For training formalizers: Separating generation from acceptance means stronger provers can be used to find more proofs without changing what acceptance means — a critical property for scalable training.
- The 102 relabeled benchmark pairs highlight that existing benchmarks contain errors, and automatic tools can help audit them.
- SemantEq-ProofAudit can serve as a standalone judge or provide feedback to provers in a loop, with each rejection naming the specific check that failed.
Conclusion
SemantEq defines an equivalence relation capturing when two formal statements are mathematically equivalent in meaning, fixing the allowed steps by their effect and judging proofs by their proof terms. The deterministic search (SemantEq-Eval) improves on BEq+ in both precision (100% vs. 95.8%) and recall (65.6% vs. 61.8%), while the proof auditor (SemantEq-ProofAudit) enables language models to certify 330 of 407 equivalent pairs (81.1% recall) while accepting no non-equivalent pairs.
Key limitations include:
- SemantEq checks agreement with a formal reference, not the informal source — a candidate copying a reference's mistake still passes.
- A rejection means only that no proof passed the search/audits, not that statements differ.
- The relabeled test set reflects the authors' own adjudication.
- Only one prover model was tested, in one session per pair.
Future work: Evaluating formal statements against informal sources when no trusted reference exists is identified as the natural next step.
Related papers
- Language Models Can Rewrite Their Own Weights
A 27B language model improved its own accuracy by 6.6 points and repaired a damaged copy of itself using only forward passes, with no gradients or training.
- Do Halting Heads Really Save Compute in Looped Language Models?
Halting heads in looped language models save far less compute than reported because mixture-trained heads rarely stop tokens and batching overhead eliminates most remaining gains.
- When Can Self-Play Fix a False Belief? Answer Keys, Pass Bands and Replacement Rules in an Execution-Grounded Loop
Self-play with execution-grounded keys cannot correct false beliefs because the generator's own code inherits its misreadings, and decorrelated keys are necessary but insufficient for correction.