🤖 AI

The Faithfulness Gap: Certifying Semantic Equivalence Between Natural-Language and Formal Mathematical Statements

This paper introduces Bidirectional Provability Fingerprinting (BPF), a framework that certifies the faithfulness of autoformalized mathematical statements by comparing their logical consequence neighborhoods against natural-language probes, thereby significantly reducing semantic drift through novel components like Counterfactual Probe Generation and Faithfulness-Guided Decoding.

Original authors: Noor Islam S. Mohammad, Tamim Sheikh

Published 2026-06-16

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Noor Islam S. Mohammad, Tamim Sheikh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a translator trying to convert a complex mathematical idea written in plain English into the strict, rigid language of a computer proof system (like Lean 4). The goal is to make sure the computer version means exactly the same thing as the human version.

The paper identifies a major problem: The "Faithfulness Gap."

The Problem: The "Well-Typed" Lie

Currently, when computers translate math, they check two things:

Does it look right? (Does the code compile without errors?)
Can it be proven? (Can the computer find a logical path to the answer?)

The authors say this isn't enough. A computer can produce a statement that is grammatically perfect and provable, but it might still be wrong. It might prove a slightly different theorem than the human intended.

The Analogy: Imagine you ask a chef to make a "spicy chicken dish."

The chef brings you a dish that is perfectly cooked (it "typechecks").
It is delicious and safe to eat (it is "provable").
But it's actually chicken curry, not the spicy grilled chicken you asked for.
The dish is valid, but it's not what you wanted. This is the "Faithfulness Gap."

The Solution: The "Fingerprint" Test

To fix this, the authors created a system called Bidirectional Provability Fingerprinting (BPF). Instead of just checking if the code works, they check if the meaning matches.

How it works (The Detective Analogy):
Imagine the original English sentence is a suspect, and the computer's translation is a suspect's alibi.

The Probes: The system generates a list of "what-if" questions (probes) based on the original sentence.
- Example: "If the original statement is true, does it imply that X is true?"
- Example: "If Y is true, does it force the original statement to be true?"
The Fingerprint: The system checks both the original sentence and the computer translation against these questions.
- If the computer translation says "Yes" to a question the original says "No" to (or vice versa), they have different "fingerprints."
- If their fingerprints match perfectly, they are semantically equivalent.

The Four Drifts (The "Drift" Classes)

The paper identifies four specific ways a translation can "drift" away from the truth while still looking okay:

Quantifier Swapping: Mixing up "For every person, there is a hat" with "There is one hat for every person." (A subtle but huge difference).
Hypothesis Omission: Forgetting a rule. (e.g., "All birds fly" vs. "All birds fly except penguins").
Conclusion Generalization: Making the conclusion too broad. (e.g., Proving "All squares are rectangles" when you only needed to prove "This specific shape is a rectangle").
Type Coercion: Silently changing the category of numbers or objects (e.g., treating a specific number as a general variable).

The New Tools

To make this fingerprinting work better, the authors added four smart features:

Counterfactual Probe Generation (CPG): Instead of asking random questions, the system asks tricky questions designed specifically to catch the four types of errors mentioned above. It's like a detective who knows exactly what kind of lie the suspect is likely to tell and asks the perfect question to expose it.
The Equivalence Spectrum: Instead of a simple "Pass/Fail" (Binary), the system gives a score from 0 to 1. This helps catch cases that are "mostly right" but need a human to double-check, rather than just rejecting them outright.
Adaptive Budget Allocation (APBA): Checking every single question takes time. This tool is like a smart manager that decides which questions are most likely to reveal a lie and focuses the time there, saving effort.
Faithfulness-Guided Decoding (FGD): This is a feedback loop. If the system catches a mistake, it tells the AI translator, "Hey, you made this specific error; try again." This helps the AI learn to write better translations in the future.

The Results

The authors tested this on a new dataset they created called DRIFTBENCH (a collection of 2,183 math problems with known errors).

Old methods (checking if code compiles or using standard AI judges) caught about 41% to 63% of the errors.
The new BPF system caught 89.6% of the errors while rarely flagging good translations as bad (only 3% false alarms).
When used to help the AI re-write its own mistakes, it reduced the error rate by nearly half (47%).

Summary

The paper argues that for AI to be truly trustworthy in mathematics, we can't just check if the code runs. We must verify that the meaning hasn't drifted. Their new "Fingerprint" system acts like a rigorous quality control inspector, using smart questions to ensure the computer's math means exactly what the human intended.

Technical Summary: The Faithfulness Gap in LLM Autoformalization

1. Problem Definition: The Faithfulness Gap

Modern autoformalization systems, which translate natural-language (NL) mathematics into formal proof assistants (e.g., Lean 4, Isabelle/HOL), are currently bottlenecked not by translation fluency but by faithfulness. While a generated formal statement may be syntactically well-formed (typecheck) and even provable, it may encode a theorem semantically distinct from the source NL statement.

The authors identify this as the faithfulness gap. Unlike code, where unit tests provide an executable oracle, mathematical formalization lacks a direct bridge between NL (interpreted under tacit conventions) and formal logic (interpreted under dependent type theory). Standard evaluation metrics—such as BLEU scores against a reference, expert spot checks, or downstream prover success—fail to detect "insidious" failures where the formalization is fluent and provable but semantically wrong.

The paper formalizes this problem via an interpretation distribution ( $D_N$ ), representing the set of formal statements competent mathematicians would accept as expressing a given NL statement $N$ . A candidate formalization $F$ is $\epsilon$ -faithful if it is provably equivalent to $1-\epsilon$ of the statements in $D_N$ . The authors categorize semantic drift into four canonical classes:

$\Delta\forall$ (Quantifier Inversion): Swapping quantifier order (e.g., $\forall x \exists y$ vs. $\exists y \forall x$ ).
$\Delta H$ (Hypothesis Omission): Dropping a premise, making the formal statement strictly stronger than intended.
$\Delta C$ (Conclusion Generalization): Strengthening the conclusion such that $F \Rightarrow N$ but $N \not\Rightarrow F$ .
$\Delta T$ (Type Coercion): Silent retagging of types (e.g., $\mathbb{R} \to \mathbb{Q}$ ), often the hardest to detect syntactically.

2. Methodology: Bidirectional Provability Fingerprinting (BPF)

The core contribution is Bidirectional Provability Fingerprinting (BPF), a reference-free framework that certifies faithfulness by comparing the "consequence neighborhoods" of the NL statement and the candidate formalization.

2.1. The Core Mechanism

BPF operates on the insight that a statement's meaning is defined by what it implies and what implies it.

Forward Fingerprint ( $\Phi^+_F$ ): The set of probes entailed by the candidate $F$ .
Backward Fingerprint ( $\Phi^-_F$ ): The set of probes that entail $F$ .
Equivalence: Two statements are semantically equivalent if their forward and backward fingerprints coincide over a sufficiently rich set of probes.

The pipeline involves:

Probe Generation: Synthesizing a set of semantic probes ( $P$ ) from the NL statement $N$ .
Autoformalization: Converting these probes into formal statements.
Entailment Checking: Using a proof assistant (Lean 4 + mathlib4) as an oracle to compute entailment relations between $F$ and the probes.
Fingerprint Comparison: Comparing the candidate's fingerprint against the predicted fingerprint derived from $N$ .

2.2. Key Components

The framework introduces four novel components to enhance detection and efficiency:

Counterfactual Probe Generation (CPG):
Instead of generic sampling, CPG uses a contrastive procedure. It mechanically generates "drifted twins" ( $N^D$ ) for each of the four drift classes (e.g., by swapping quantifiers). An LLM is then prompted to generate probes that specifically distinguish $N$ from $N^D$ . This targets the specific failure modes the certifier aims to detect.
The Equivalence Spectrum ( $E(F, N)$ ):
Replacing brittle binary verdicts (Faithful/Drifted) with a continuous score in $[0, 1]$ . This score is calibrated against expert annotations to define three decision regions:
- ACCEPT: $E \ge 0.93$
- REVIEW: $0.78 \le E < 0.93$ (requires human triage)
- REJECT: $E < 0.78$
Adaptive Probe Budget Allocation (APBA):
An information-theoretic router that allocates the limited "tactic budget" (time/cost for proof search) dynamically. APBA selects probes that maximize the expected reduction in entropy regarding the drift status, rather than sampling uniformly. This achieves the same detection accuracy with significantly fewer probes.
Faithfulness-Guided Decoding (FGD):
A feedback loop where BPF scores are used as a reward signal during the autoformalization process. In a sample-and-rerank setup, candidates are scored by BPF. If the top candidates fall into the "REVIEW" or "REJECT" zones, the highest-scoring "witness probe" (the specific probe that revealed the drift) is fed back to the LLM as an in-context hint to repair the error.

3. Theoretical Guarantees

The paper provides two main theoretical results:

Drift Detection Theorem: Proves that for any specific drift class $D$ , if the probe generator has a non-zero "witnessability rate" ( $\alpha$ ), BPF can detect the drift with probability $1-\delta$ using a probe budget of $k \ge \frac{1}{\alpha} \log(1/\delta)$ .
PAC-Faithfulness: Establishes that the equivalence class of an NL statement is learnable from $O(\log(1/\delta)/\epsilon)$ probes, assuming the probe distribution can witness any reachable drift.

The authors also acknowledge limitations: BPF cannot detect convention drift (where notation changes but logical content remains identical) and relies on the completeness of the proof oracle (incomplete proofs can lead to false negatives).

4. Experimental Results

The authors released DRIFTBENCH, a benchmark of 2,183 NL/Lean 4 pairs with controlled drift labels across six mathematical subfields.

Detection Performance:

BPF + CPG detects 89.6% of drifted formalizations at a 3.0% false-positive rate.
This significantly outperforms baselines:
- Typecheck only: 11.4% detection.
- Provability (unprovable flag): 41.2% detection.
- LLM-judge (direct faithfulness check): 63.3% detection.
- Back-translation: 58.9% detection.
APBA reduces the computational cost (wall-clock time) by 3.2× compared to uniform sampling while maintaining detection rates.

FGD Impact:
When applied as a post-processing step to a state-of-the-art autoformalizer, FGD reduced the rate of emitted drifted statements from 19.4% to 10.3% (a 47% relative reduction), primarily by re-prompting on hypothesis omission and conclusion generalization errors.

5. Significance and Claims

The paper claims that the faithfulness gap is the primary bottleneck for trustworthy autoformalization at the scale of full mathematical libraries. The significance of this work lies in:

Reference-Free Certification: It provides a method to verify faithfulness without requiring a "gold standard" formalization, which is often unavailable.
Operationalizing Semantics: It shifts the evaluation paradigm from syntactic overlap (BLEU) or provability to inferential semantics (consequence neighborhoods), aligning with proof-theoretic semantics.
Scalability: By introducing APBA and the Equivalence Spectrum, it offers a practical, cost-effective triage tool that can prioritize human expert review rather than replacing it.
Benchmarking: DRIFTBENCH is presented as the first benchmark with controlled drift labels, enabling systematic evaluation of faithfulness rather than just prover capability.

The authors position BPF not as a perfect solution that eliminates all errors (specifically noting the limitation regarding convention drift), but as a concrete step toward closing the faithfulness gap, enabling the safe integration of AI-generated formal mathematics into rigorous libraries.