# SemantEq: Faithful Bidirectional Equivalence of Formal Statements

> SemantEq defines a principled equivalence relation for formal statements and achieves perfect precision with 65.6% recall, outperforming prior systems while rejecting all non-equivalent pairs.

- **Source:** [arXiv](https://arxiv.org/abs/2610.32919)
- **Published:** 2026-11-21
- **Permalink:** https://picx.dev/p/LhcmJN
- **Whiteboard:** https://picx.dev/p/LhcmJN/image

## Summary

# 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 $P \leftrightarrow Q$ — **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:

1. A closing tactic can prove the goal from library facts alone.
2. A name appearing in a script does not prove the antecedent did any work.

### Theoretical Foundation

The paper defines a **faithful derivation** relation $\rightarrow_{\mathcal{L}}$ with four step types:

**Definition 1 (Faithful derivation).** A statement $S$ faithfully derives $T$ with respect to library $\mathcal{L}$, written $S \rightarrow_{\mathcal{L}} T$, when one of the following holds:

- **Logical rearrangement**: $S = \mathcal{C}[\varphi]$ and $T = \mathcal{C}[\varphi']$ where $\text{atoms}(\varphi) = \text{atoms}(\varphi')$, $\varphi \leftrightarrow \varphi'$ holds under every interpretation, and every atom matters on both sides.
- **Bridge rewriting**: $S = \mathcal{C}[\sigma(u)]$ and $T = \mathcal{C}[\sigma(v)]$ (or exchanged) for some bridge $b \in \mathcal{B}$ whose hypotheses are provable in context.
- **Change of variables**: Either $T = \forall y : D. S$ for a new variable, or $S = \Pi\, \forall x : D. \varphi$ and $T = \Pi\, \varphi[t/x]$ for a term $t$ 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 $P$ and $Q$ are SemantEq over $\mathcal{L}$, written $P \simeq_{Sem, \mathcal{L}} Q$, if there are chains of faithful derivations from $P$ to $Q$ and from $Q$ to $P$.

**Proposition 1.** The relation $\simeq_{Sem, \mathcal{L}}$ is an equivalence relation, and for all statements $P, Q$:

$$
P \simeq_{Sem, \mathcal{L}} Q \quad \Longrightarrow \quad \mathcal{L} \vdash (P \leftrightarrow Q)
$$

**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 $R$ and candidate $C$, SemantEq-Eval:
1. Accepts immediately if identical up to renaming and definitional unfolding.
2. Attempts $R \Rightarrow C$ and $C \Rightarrow R$, 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.

---

_Markdown view of https://picx.dev/p/LhcmJN, served by PicX — AI-generated visual whiteboard summaries of research papers._
