💻 computer science

Benchmarking Testing in Automated Theorem Proving

This paper introduces "T," a novel framework that evaluates the semantic correctness of AI-generated formal theorems by verifying if dependent successor theorems compile successfully, revealing a significant gap in current large language models' theorem generation capabilities compared to traditional lexical or manual evaluation methods.

Original authors: Jongyoon Kim, Hojae Han, Seung-won Hwang

Published 2026-04-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jongyoon Kim, Hojae Han, Seung-won Hwang

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 hiring a team of architects to design a new bridge.

The Old Way of Testing (Compilation)
In the past, when evaluating these architects (which, in this paper, are AI models), we only checked if their blueprints were "grammatically correct." We asked: Does the blueprint follow the rules of grammar? Do the lines connect? Does the computer say "Syntax OK"?

If the blueprint looked perfect on paper, we assumed the bridge would hold up. But here's the problem: An architect could draw a blueprint that says, "This bridge is made of solid gold," and the computer would say, "Syntax OK!" because the sentence is grammatically correct. However, if the blueprint was actually supposed to be for a "steel suspension bridge," the architect failed the real job, even though the grammar was perfect.

In the world of math and computer code, this is called Compilation. The AI writes a theorem (a mathematical statement), and the computer checks if it compiles (runs without errors). The paper argues that this is a terrible way to judge if the AI actually understood the math.

The New Way of Testing (T2 Framework)
The authors of this paper propose a new method called T2 (Theorem Testing). Instead of just checking the grammar of the blueprint, they ask: Does this blueprint actually work when we try to build the rest of the city around it?

They use a concept called Integration Testing. Imagine the bridge is just one part of a massive city.

The Target: The AI is asked to prove a specific theorem (e.g., "Addition is commutative," meaning $a + b = b + a$ ).
The Successors: In real math, once you prove a small fact, other mathematicians use that fact to prove bigger, more complex things. The paper looks at all the other theorems that depend on the AI's answer.
The Test: The AI's answer is plugged into these "downstream" proofs.
- If the AI gave a "fake" answer (like a tautology that is always true but says nothing useful), the downstream proofs will crash. They will fail to compile because they relied on a specific meaning that the AI didn't provide.
- If the AI gave the correct answer, the downstream proofs will run smoothly.

The Big Discovery
The authors built a massive test suite using 2,206 real-world math problems from the "Lean" programming language. They tested 18 of the smartest AI models available (including models from Google, OpenAI, and Anthropic).

Here is what they found, using our bridge analogy:

The "Grammar" Trap: Most AIs were great at passing the old test. They wrote blueprints that looked perfect and compiled without errors. On the old test, they scored around 80% success.
The Reality Check: When the authors applied the new "City Integration" test, the scores plummeted. The best AI only got about 39% right.
The Gap: This means that for every 100 bridges the AI claimed to build, about 60 of them would collapse the moment someone tried to build a road on top of them. The AI was good at faking the look of math, but bad at the meaning.

Why This Matters
The paper shows that current ways of measuring AI math skills are lying to us.

Lexical Similarity (BLEU): Checking if the AI's words look like human words is useless. The AI can write gibberish that looks like math and still pass.
Specialized Models: Even models specifically trained to be "math experts" didn't do much better than general chatbots. They just got better at faking the syntax.
The Solution: The only way to know if an AI truly understands math is to see if its work holds up when other proofs try to stand on it.

In a Nutshell
The paper introduces a new "stress test" for AI math. It stops asking, "Does this sentence look like math?" and starts asking, "Does this math actually work when we try to use it to solve bigger problems?" The result is a harsh reality check: today's best AI models are still struggling to do real, meaningful math, even though they look like they are doing it perfectly.

1. Problem Statement

The rapid advancement of Large Language Models (LLMs) has improved their ability to generate formal proofs in systems like Lean. However, current evaluation methods suffer from a critical flaw: they conflate syntactic validity with semantic correctness.

The Limitation of Compilation: Existing benchmarks (e.g., MiniF2F, ProofNet) primarily evaluate models by checking if a generated theorem compiles. While compilation verifies that the code is syntactically valid and logically consistent in isolation, it does not guarantee that the theorem captures the intended mathematical meaning.
The "Tautology" Problem: A model can generate a trivial tautology (e.g., $a + b = a + b$ ) that compiles successfully but fails to prove the intended non-trivial statement (e.g., commutativity $a + b = b + a$ ).
Inadequacy of Proxies: Existing attempts to measure semantic correctness rely on unreliable proxies such as lexical overlap (BLEU scores) against human-annotated references or manual inspection. These methods are either noisy, require expensive human labor, or fail to distinguish between correct and incorrect semantic meanings.

2. Methodology

The authors propose a paradigm shift inspired by integration testing in software engineering. Instead of evaluating a theorem in isolation, they evaluate it based on how it interacts with the rest of the codebase.

Core Concept: Theorem Testing (T2)

Drawing on the Curry-Howard correspondence (where proofs correspond to programs), the authors treat a generated theorem as a function and the theorems that depend on it as "test cases."

Dependency Graph: They construct a dependency graph where a target theorem ( $t_{GT}$ ) has predecessors (definitions/lemmas it uses) and successors (theorems that invoke or build upon it).
Integration Testing Logic: If a generated theorem ( $t_{fl}$ ) is semantically incorrect (e.g., it defines a tautology instead of the intended property), any successor theorem that relies on it will fail to compile.
Cut Elimination Analogy: The process is formally grounded in the logical principle of Cut Elimination. If a chain of proofs ( $X \to Y \to Z \to W$ ) fails when the intermediate lemma ( $Y$ ) is replaced by a generated candidate, the candidate is semantically incorrect.

The T2 Benchmark

The authors constructed a large-scale benchmark, T2, to facilitate this evaluation:

Source: Extracted from 5 real-world Lean 4 repositories (covering algebra, topology, number theory, etc.).
Scale: 2,206 problems, each paired with an average of 41 successor theorems.
Hard Subset: A subset of 389 "Hard" problems where the model must generate both the proposition (statement) and the proof, rather than just filling in a proof for a given statement.
Automation: The extraction pipeline is fully automated, requiring no human annotation for the dependency structure. Natural language (NL) descriptions were generated by a strong LLM (Claude Sonnet 4.5) and manually verified for a sample.

The Metric: Testing Accuracy (TA)

The paper introduces Testing Accuracy (TA) as the primary evaluation metric:
$TA = E_{P \sim D} \left[ \prod_{i=1}^{k} \text{compiles}(t^{(i)}_{succ} \mid t_{fl}) \right]$
A generated theorem passes only if all its dependent successor theorems compile successfully when the original theorem is replaced by the generated one.

3. Key Contributions

T2 Benchmark: The first large-scale, dependency-rich benchmark for formal theorem proving that moves beyond isolated problems to real-world repository contexts.
Testing Accuracy (TA): A novel, automatic, reference-free metric that directly verifies semantic correctness through compilation of dependent modules.
Empirical Gap Analysis: Comprehensive evaluation of 18 state-of-the-art models (both open and closed-source) revealing a massive disconnect between compilation success and semantic correctness.
Contextual Insights: Demonstrated that providing successor theorems as context significantly improves semantic correctness, whereas providing only natural language proofs does not.

4. Experimental Results

The authors evaluated 18 models (including GPT-5, Claude-Sonnet-4.5, Llama-3.1, and specialized math models like DeepSeek-Prover) on the T2 benchmark.

The Semantic Gap:
- Compilation Accuracy: Models achieved high compilation rates (e.g., Claude-Sonnet-4.5: 80.3% on the full set).
- Testing Accuracy (TA): The same models achieved drastically lower TA scores (e.g., Claude-Sonnet-4.5: 38.9% on the full set; 4.5% on the Hard set).
- False Positives: Up to 93.1% of compilable theorems were found to be semantically incorrect when tested against successors.
Failure of Existing Metrics:
- BLEU: High lexical similarity (BLEU scores) showed almost no correlation with semantic correctness (Correlation: 0.123). Models could generate textually similar but logically wrong proofs.
- Specialized Models: Models fine-tuned specifically for theorem proving often achieved higher compilation rates but performed worse or similarly to general-purpose models on TA, suggesting they overfit to syntax rather than semantics.
Impact of Context:
- Providing Successor Theorems as input context consistently improved TA (e.g., +4.9% for Claude-Sonnet-4.5).
- Providing NL Proofs alone without successors did not improve performance and sometimes degraded it.
- Few-shot prompting and iterative refinement (using compiler feedback) yielded negligible improvements on the Hard set, indicating the difficulty lies in deep semantic reasoning, not just task formatting.

5. Significance and Conclusion

This paper fundamentally challenges the current state of Automated Theorem Proving (ATP) evaluation.

Redefining Success: It proves that "compilation" is a necessary but insufficient condition for theorem generation. A model can be syntactically perfect but semantically useless.
Trustworthiness: The T2 benchmark and TA metric provide a rigorous, automatic way to assess whether an LLM truly understands mathematical concepts or is merely hallucinating syntactically valid code.
Future Direction: The work suggests that future ATP systems must be evaluated on their ability to integrate into existing codebases (dependency-aware generation) rather than solving isolated puzzles. It also highlights that providing the "test suite" (successor theorems) to the model during generation is a crucial strategy for improving semantic alignment.

In summary, the paper argues that integration testing is the missing link in evaluating LLMs for formal mathematics, revealing that current state-of-the-art models are far from achieving reliable semantic correctness in theorem proving.