Designing a Verifiable Evaluation System for LLM Theorem Proving and AI Research
Traditional LLM benchmarks focus on closed-answer knowledge QA, code completion, and competition math, but real research requires proposing conjectures, constructing counterexamples, tightening known bounds, writing independently checkable proof scripts, and judging whether a result is worth pursuing. This article describes a TCSExam-like evaluation system that organizes tasks into verifiable tiers, combines programmatic checkers, automated theorem provers, and budget/attempt constraints, and reports both aggregate scores and success/coverage metrics. It examines the resulting capability profile, including task-specific reversals, two representative results—a 630-edge triangle-free and C4-free construction and an improved coding-theory bound A(22,10) ≤ 82—and practical recommendations for building verifiable evaluations and selecting models by task profile.
From “Looks Plausible” to “Can Be Checked”: Reframing AI Research Evaluation
1. Background: Why Traditional Benchmarks Miss “Research Capability”
For years, LLM evaluation has centered on knowledge QA, code completion, and competition math problems. These tasks share a key feature: closed answers and relatively single evaluation criteria. Real research goes far beyond that—it includes proposing conjectures, constructing counterexamples, tightening known upper bounds, writing proof scripts that can be independently reviewed, and judging whether a result is worth further investment.
When models begin to participate in this kind of work, an old problem becomes obvious: a “plausible-looking” proof and a “machine-verifiable” proof have completely different value. Theoretical computer science (TCS) is an especially suitable testbed: topics such as extremal combinatorics, coding theory bounds, and the PCP theorem often produce conclusions that can be written as formal lemmas and checked by automated theorem provers, naturally imposing the hard constraint of verifiability.
This motivated the construction of a TCSExam-like evaluation system: gathering outputs that were previously scattered across different research workflows—formal proofs, program constructions, parameter calculations—into one verifiable system, so that scores reflect conclusions that withstand machine review rather than fluent text.
2. Core Design of the Verifiable Evaluation System
2.1 Task Tiers: From Lemmas to Complete Theorems
A high-quality evaluation must first address how task difficulty is calibrated. The system organizes tasks into progressive verification levels:
- Tasks with intermediate lemmas: the model receives validation feedback after each step, testing whether it can complete a proof with scaffolding.
- Tasks without intermediate lemmas: the model must fill in the entire lemma chain itself, testing its ability to complete a proof independently.
- Construction tasks: concrete instances of graphs, codes, or parameters are required to satisfy constraints and reach target metrics.
- Upper/lower bound tightening tasks: the model must make non-trivial improvements over published results.
The significance of this tiered design is that it makes the research process itself measurable, rather than measuring only the final answer.
2.2 Validation Mechanism: Three Lines of Defense
Verifiability is the soul of the system, typically supported by three layers:
- Programmatic checker: directly validates the properties of construction outputs. For example, for “construct a graph containing no triangles and no quadrilaterals,” the checker enumerates all triples and quadruples to confirm that no such cycles exist, and counts vertices and edges. This validation does not depend on any model judgment; it is pure deterministic logic.
- Automated theorem prover (ATP): performs machine review of formal proofs. If the proof script output by the model is accepted by the prover, it is considered valid—turning “is the proof correct?” from subjective review into objective judgment.
- Budget and attempt constraints: records the model’s success rate under a given number of attempts and token budget, rather than only checking whether it eventually succeeds. This distinguishes “lucky success” from “stable capability.”
Schematically, a construction-task validation flow can be abstracted as:
model_output = model.generate(task_prompt, budget)assert checker.validate(model_output.graph,property=no_triangle_no_cycle4) # property validationassert model_output.graph.edges >= reference # metric improvement
2.3 Scoring Dimensions: More Than One Total Score
The leaderboard reports two types of metrics:
- Leaderboard score: a cross-task aggregate score reflecting the overall level of research capability.
- Success rate and coverage: for example, “M successes in N attempts, covering K distinct theorems,” reflecting both stability and diversity. If a model succeeds 23 times in 60 attempts and covers 9 theorems, it is not merely overfitting to a few problems.
This dual-dimensional design prevents a single score from hiding differences in capability structure.
3. What the Data Reveals: Leaders Do Not Dominate Everywhere
The leaderboard shows a phenomenon worth considering: the top model scores about 71.9, while the second model scores about 57.4, an apparently clear gap. But in specific task profiles, the leader completes 14/20 theorem tasks without intermediate lemmas (about 70% success), the second model reaches about 38.3% success under a strict attempt budget, and the remaining evaluated agents all have success rates no higher than 11.7%—there is a large capability gap between the top and the mid-tier.
More interesting is “local reversal”: on the high-difficulty PCP alphabet reliability task, the second model completed all three attempts, while the overall top model did not solve it. This shows that current model capabilities are highly task-dependent and closely related to architecture and domain coverage in training data; aggregate scores cannot fully predict single-task performance.
The practical implication is clear: model selection must match the task profile, not simply rank by total score.
4. Two Representative Cases: AI Outputs That Verifiably Beat Reference Values
Two of the most intuitive results represent two forms of AI research output:
4.1 Extremal Graph Construction: From Satisfying Constraints to Breaking a Reference Record
In the Erdős girth-5 extremal graph task, the goal is to construct a triangle-free and quadrilateral-free (C4-free) graph with as many edges as possible. The reference construction has 629 edges, while the model produced a graph with 124 vertices and 630 edges that fully satisfies the constraints under validation—the edge count exceeds the reference value, and every edge and every excluded cycle can be independently checked.
The value of this result is not the extra edge itself, but what it proves: the model’s output is not a “plausible-looking new answer,” but an independently verifiable object. This is a qualitative change in the research workflow—reviewers do not need to trust the model; they only need to run the checker.
4.2 Tightening a Combinatorial Upper Bound: A(22,10) ≤ 82
On a classic coding-theory parameter problem, the model tightened a published upper bound from 84 to 82. Tightening a known upper bound is a typical “incremental but real” research action: it does not rely on guessing an open problem, but completes a verifiable optimization within the existing methodological framework.
Together, these two cases outline a new paradigm: a three-stage research pipeline of “model output + machine review + literature comparison,” in which the human role shifts from “validating every derivation” to “setting problems and assessing the value of conclusions.”
5. Capability Boundaries: A Terrain Map, Not a Report Card
What does this evaluation really tell us?
The optimistic part: under conditions of clear problems, sufficient budget, and verifiable feedback, the strongest current models can already stably complete some theorem proofs, program optimizations, and construction improvements, with outputs that can be machine-checked. This was almost unimaginable two years ago.
The sobering part: task directions, value judgments, and success criteria are all set by humans. Models cannot yet autonomously choose research directions, judge whether an intermediate result is worth pursuing, or sustain attacks on major open problems without a clear objective function. A 70% success rate on theorem tasks also means that in nearly one-third of cases the model fails or requires extensive retries.
Therefore, the leaderboard is more like a terrain map of AI research capability: it marks areas where models can already stand—structured proofs, verifiable constructions, parameter optimization—and areas that remain human territory—problem formulation, value judgment, and direction selection.
6. Practical Recommendations
- Prioritize verifiability when building evaluations: instead of subjective scoring, turn tasks into forms backed by a checker or prover, even if the number of tasks is smaller.
- Select models by task profile: test candidate models on your real task distribution for success rate and coverage, rather than citing general leaderboards.
- Include review cost in process design: adopt a three-stage pipeline of “model generation + deterministic validation + human final review,” where the model expands the candidate solution space and the checker guarantees correctness.
- Keep failure sample analysis: failure modes under an attempt budget—directional errors, getting trapped in local constructions, lemma selection mistakes—are more useful for guiding prompt strategy and toolchain improvements than success samples.
Conclusion
Verifiable evaluation marks a shift in AI research capability assessment from a “language exam” to “experimental science.” When every score is backed by a machine-checkable object, we can avoid being fooled by polished text and avoid underestimating real progress because of occasional model failures. Humans ask questions and judge value; models search and construct in a verifiable space. This clearly divided collaboration path may be the mainstream form of intelligent research assistance in the next stage.
