Evaluating AI Agents on Theoretical Computer Science: Verifiable Benchmarks and a Reproducible Research Pipeline
Large language models increasingly claim research-level reasoning, but chat-style benchmarks can't tell genuine proofs from plausible hallucinations. This article walks through a verifiable evaluation framework built on theoretical computer science (TCS), covering task design, independent verifiers, scoring metrics, and headline results—including an extremal graph construction that beat the reference value and a coding-theory upper bound tightened from 84 to 82. It closes with practical lessons for building trustworthy AI research pipelines and a candid map of where AI capability still falls short.
1. Why “Verifiable” Evaluation Matters for Research Capability
In recent years, large language models have kept improving at mathematical reasoning and code generation, raising an industry-wide question: do these models have even the seed of genuine scientific research ability? Standard Q&A-style evaluation is a poor way to answer it—models can produce derivations that look reasonable but cannot be audited, making it hard to tell whether they truly understand or are simply stitching together plausible-sounding output.
Theoretical Computer Science (TCS) offers an ideal testbed, for three reasons:
- Mechanically checkable conclusions: proofs can be inspected line by line with formal verification tools; combinatorial constructions (graphs, codes, alphabets) can be validated by direct enumeration; numerical bounds can be compared against published results.
- Clearly layered difficulty: problems range from course-level exercises to open questions, making it possible to map an “ability terrain.”
- Diverse output types: proofs, constructions, counterexamples, and bound tightening cover the main categories of research output.
A sensible evaluation paradigm, therefore, is to place the entire pipeline—“pose a question, explore directions, produce a result, verify it independently”—inside one verifiable system, so that model output is no longer unverifiable text but an independently checkable artifact.
2. Framework Design: Tasks, Verifiers, and Scoring
2.1 Task Composition
The benchmark draws on several classic TCS branches:
- Proof tasks: produce a complete proof, e.g., propositions in extremal graph theory or probabilistically checkable proofs (PCP);
- Combinatorial construction tasks: build objects satisfying given constraints, such as constructing graphs with as many edges as possible under vertex-count and girth limits;
- Parameter tasks: improve known upper or lower bounds, e.g., classical parameters in error-correcting codes and combinatorial designs.
These tasks share a key property: an objective “reference answer” exists, but solutions better than the reference value are also allowed—which is precisely what distinguishes research from test-taking.
2.2 Verifiability Design
Each problem ships with an independent verifier:
- For proof tasks, the logic chain is checked line by line, and models may produce intermediate lemmas before assembling the full proof. A “no hints” difficulty tier probes the model’s ability to discover the proof skeleton on its own;
- For construction tasks, the verifier checks whether the object satisfies all constraints and tracks quality metrics (e.g., edge count) against the reference value;
- Repeated attempts are sampled, and two dimensions—“success rate” and “number of theorems covered”—are tracked to avoid misleading judgments from a single lucky run.
2.3 Scoring Dimensions
Beyond an overall leaderboard score, finer-grained metrics include:
| Dimension | Meaning |
|---|---|
| Proof success rate | Proportion of tasks with a complete, verified proof |
| Theorem coverage | Number of distinct theorems successfully solved |
| Construction improvement | Gain over the reference value |
| Single-shot vs. multi-attempt | Separates a model’s stability from its ceiling |
3. Reading the Results: Clear Capability Tiers, Not a Clean Sweep
3.1 Top Models Can Produce Auditable Output
Under clearly stated problems, sufficient compute budget, and verifiable feedback, first-tier models completed a substantial share of proof tasks: the top-ranked model solved roughly 70% of theorems without intermediate-lemma hints, and its proofs could be independently checked. Second-tier models steadily cracked a subset of theorems over multiple attempts, with success rates around 30%. Most remaining agents stayed below 12%, revealing a sharp capability gap.
3.2 The Advantage Isn’t One-Directional
Ranking does not imply uniform dominance. In one PCP alphabet soundness task, the second-ranked model succeeded on all three attempts while the top-ranked model failed. This highlights a defining trait of current models: capability is highly unevenly distributed. Each model has a distinct “skill terrain,” and single-task wins cannot be summarized by total scores.
3.3 Two Landmark Results: Construction and Bound Tightening
The most convincing outputs came from cases that exceeded the reference answers:
- Extremal graph construction: On the Erdős extremal graph task with girth 5, a model produced a triangle-free and quadrilateral-free graph with 124 vertices and 630 edges, beating the task’s 629-edge reference. The construction is fully machine-verifiable—a genuinely research-grade result.
- Upper bound tightening: On a classical error-correcting code parameter task, a model proved A(22,10) ≤ 82, improving the published upper bound from 84 to 82. Every unit of tightening reflects a real increase in proof difficulty.
These two cases show that models are delivering not “plausible new answers” but constructions and proofs that withstand independent verification.
4. Methodology: Building a Trustworthy AI Research System
4.1 Verifiers Before Scorers
The single most important engineering lesson: design the verifier first, then the task. If an output cannot be independently checked, no claim of “research capability” is credible. The general pattern is to decouple verification logic from model output:
Model output (proof / construction / parameter)│▼Independent verifier (formal check / enumeration / literature comparison)│├── Pass → record quality metrics (edge count, bound value, etc.)└── Fail → feed back the error type; allow retries with feedback
4.2 Multi-Trial Sampling and Coverage Statistics
Research exploration is inherently stochastic, and single-shot success rates both over- and under-estimate models. A sound approach:
- Run multiple attempts per problem and measure the success rate;
- Track how many distinct problems were solved, to gauge exploration breadth;
- Distinguish “with lemma hints” from “no hints” tiers, corresponding to assisted research and autonomous research capabilities respectively.
4.3 Feedback Loops: Let Verification Drive Iteration
Feeding verifier failure details—which inference step breaks down, which constraint is violated—back to the model creates a “try–verify–revise” loop, the core driver of higher success rates. This mirrors test-driven development: an executable external specification is more reliable than natural-language judgment.
5. Capability Boundaries: Blank Spots on the AI Research Map
Returning to the original question, this kind of benchmark functions as a “capability terrain map” for AI research:
- Illuminated regions: given well-defined problems, sufficient budget, and verifiable feedback, models can complete some theorem proofs, program optimizations, and construction improvements, producing independently checkable results.
- Still dark regions: autonomously choosing research directions, judging the value and novelty of results, and posing and attacking major open problems remain heavily human-dependent. Models lack a sense of “what is worth doing”; at their core, they are powerful search and verification accelerators.
6. Conclusion
Verifiable evaluation provides a trustworthy yardstick for measuring AI research ability: independent verifiers as the foundation, success rate and coverage as the core metrics, and reference-beating constructions and tightened bounds as the mark of a capability ceiling. Results show that top models can already produce verifiable TCS results under bounded conditions, though capability is uneven and autonomous research remains limited. For engineering and R&D teams, the pragmatic path is to embed such “generate–verify–iterate” pipelines into the development toolchain—letting models handle exploration and compute-intensive work while humans retain direction-setting and value judgment. That is likely the most reasonable division of labor for AI-assisted research in the foreseeable future.
