How to Evaluate LLMs' Automated Theorem-Proving Capabilities: A Technical Practice Framework
This article examines an evaluation framework for assessing whether large language models can perform verifiable research in theoretical computer science. Drawing on publicly reported experiments, it covers task design principles (theorem proving, extremal graph constructions, and bound tightening in coding theory), the evaluation protocol based on automated verification and multi-attempt success rates, observed performance gaps among frontier models, and the practical implications for building human-AI collaborative research workflows.
1. Background: Why “Verifiable” Evaluation Matters for AI Research Capability
Large language models have made steady progress on code generation and mathematical reasoning, but a long-overlooked problem remains: an answer that “looks right” and an answer that “can be independently verified” are two very different things.
Traditional math-reasoning benchmarks largely consist of multiple-choice and fill-in-the-blank questions, where scoring only checks whether the final answer matches a reference. This works tolerably well for everyday math problems but fails almost entirely for real research work. What researchers actually need is not “a seemingly plausible result,” but:
- An independently verifiable artifact: a compilable and runnable program, an explicit set of parameters, or a formalized proof;
- A testable construction: for example, a graph structure that a script can confirm satisfies constraints such as “triangle-free and 4-cycle-free”;
- A tightened bound: for example, improving a known upper bound on some quantity from 84 to 82 in combinatorics, with every step of the proof standing up to scrutiny.
Motivated by this gap, a leading LLM startup teamed up with a top university’s theoretical computer science group to propose an evaluation framework aimed at TCS research. It places the outputs of theorem proving, extremal constructions, and coding-theoretic bound proofs into a single automatically verifiable system. The core value of this approach is turning “the model claims it can do research” into “the model’s outputs can be machine-verified line by line,” thereby establishing a relatively objective baseline of capability.
2. Framework Design: Standardizing and Verifying the Research Workflow
2.1 Task Selection Logic
The tasks chosen for the framework share a few common traits: the results are mechanically verifiable, the process allows multiple attempts, and the difficulty is well above standard reasoning problems. Typical tasks include:
- Theorem proving: given a theorem statement, the model must produce a complete proof, with every step checked by a formal verification tool;
- Construction tasks: for example, Erdős-style extremal graph problems — constructing a graph with a given number of vertices and edges that avoids specific substructures. The verification script only needs to check whether the graph contains any triangles or 4-cycles; the logic is simple but extremely strict;
- Bound tightening: for example, the classic coding-theoretic problem A(n,d) (the maximum number of codewords for a given length and minimum distance), where the model must prove an upper bound tighter than previously published results.
The elegance of this task design lies in the fact that verification cost is far lower than solving cost. Checking whether a construction is valid takes polynomial time, but producing the construction itself may require deep combinatorial intuition from the model.
2.2 Evaluation Protocol: Success Rate Combined with Multiple Attempts
Research naturally involves trial and error, so the framework does not use a “one-shot, winner-takes-all” evaluation. Instead, it tracks:
- Per-task success rate: the proportion of successful completions across N attempts;
- Coverage breadth: the number of distinct theorems/tasks solved, rather than repeated hits on the same problem;
- Dependence on intermediate lemmas: distinguishing whether a model proves results independently through a complete reasoning chain, or stitches together lemmas under hints.
Combining these metrics distinguishes two types of models: one that “gets lucky on a handful of problems through sampling diversity,” and another that “possesses stable reasoning ability and can systematically push a proof forward.”
3. Experimental Observations: Differentiated Profiles Among Frontier Models
Publicly reported results show that current frontier models exhibit clear tiered differentiation under this framework — but the differentiation is not simple “across-the-board domination.” It is a difference in capability profiles.
3.1 Overall Level and Tiers
On the aggregate leaderboard, the top two flagship models differ significantly (on the order of roughly 70 points versus 57 points). Under the setting with no intermediate-lemma hints, the leading model completed proofs for most theorems, with a success rate of about 70%. The other model logged a non-trivial absolute number of successes across multiple attempts, but they were spread across far fewer theorem types, with a markedly lower per-problem success rate. The remaining six agent-style products all achieved success rates below 12%.
This result shows two things:
- Research-grade reasoning ability is not equivalent to general conversational ability; some products packaged as agents are nearly helpless on long-horizon proof tasks;
- Multi-round sampling does increase hit counts, but “insufficient breadth” exposes a weakness in the stability of long reasoning chains.
3.2 Task-Dimension Trade-offs
Notably, the stronger model did not dominate on every task. For example, in a PCP (probabilistically checkable proofs) related alphabet-reliability task, one model succeeded in all three attempts, while the higher-scoring model failed to solve it. This suggests:
- Differences in training data distribution and reasoning style can create “local advantages” in specific subdomains;
- A single aggregate score hides the structure of capabilities; model selection for research scenarios should be broken down by task dimension.
3.3 Signature Results on Construction Tasks
The most intuitive results in the paper come from construction tasks:
First, an explicit extremal graph construction. In the girth-5 extremal graph task (a graph containing no triangles and no 4-cycles), the model produced a graph with 124 vertices and 630 edges, exceeding the 629-edge reference value used in the task. The significance of such a result is that it requires no human post-hoc patching: the verification script can directly confirm that all three conditions — 630 edges, no triangles, no 4-cycles — hold simultaneously. The model effectively found an explicit solution better than the literature reference value within the search space.
Second, tightening a combinatorial bound. On the A(22,10) problem, the model produced a proof tightening the published upper bound on this coding-theoretic quantity from 84 to 82. Upper-bound results are harder to “get lucky” with than constructions, because a flawed proof can be refuted step by step. This indicates that the model’s reasoning chain can already support a degree of original theoretical advancement.
4. Capability Boundaries: What AI Research Assistants Can and Cannot Do
Mapping these results onto a “capability terrain” yields a sober conclusion.
4.1 Capabilities Already Present
- Given clearly defined problems, sufficient budget, and verifiable feedback, models can complete some theorem proofs, program optimizations, and construction improvements;
- They can explore beyond human literature values in search-type tasks, especially in scenarios with enormous parameter spaces but cheap verification;
- Multi-round sampling + automated verification forms an effective “generate-and-filter” workflow, well suited to chaining with formal verification tools.
4.2 Capabilities Still Missing
- Choosing research directions autonomously: models cannot judge “which problem is worth working on” — the part of research that most depends on human taste;
- Judging the value of results: a model can produce a proof of “upper bound 82,” but cannot assess the significance and novelty of that result within the field;
- Major open problems: for problems requiring months or years of human intellectual effort, current model success rates approach zero.
5. Implications for Engineering Practice
5.1 Evaluation Design: Verification Before Generation
This framework offers a methodological lesson for any team that wants to assess its own model’s research capability: design the verifier before designing the task. As long as verification is cheap and unambiguous, any candidate solution the model generates can be automatically filtered, and the cost of multiple rounds of sampling becomes controllable. The same paradigm applies to code repair, protocol verification, constraint solving, and similar engineering scenarios.
An illustrative workflow:
Task definition (theorem / construction / bound)|vModel generates candidate solutions over N samples|vFormal/scripted verifier checks each one|vAggregate success rate, coverage breadth, best solution
5.2 The Best Form of Human-AI Collaboration
The most pragmatic positioning at this stage is: the model acts as a “tireless candidate-solution generator,” while humans act as “problem definers and value judges.” For practical adoption, organizations should focus on three points:
- When integrating research-oriented AI capabilities into internal log analysis and problem-solving pipelines, prioritize task types where “answers can be machine-checked”;
- Build pipelines with multi-round attempts and automated acceptance, rather than expecting a single conversation to deliver a correct result;
- Keep a human review step for critical conclusions, especially for results involving claims of originality.
6. Conclusion
The significance of this joint research lies not in declaring that “AI can already do research independently,” nor in how many points one model leads another on a leaderboard. It lies in establishing a reproducible, verifiable, and decomposable measurement system. What the model delivers is not a seemingly plausible new answer, but a proof, a set of parameters, or a construction that can be independently verified — which is the minimum bar research places on “correctness,” and the yardstick that all AI research-capability claims should be held to.
Within a framework of well-defined problems, sufficient budget, and verifiable feedback, AI can already substantively contribute to proofs and constructions. Choosing which problems to pursue, judging which results matter, and cracking genuinely open problems remain human territory. Acknowledging this boundary is closer to the truth of technology deployment than exaggerating any single leaderboard result.
