Verifiable AI Research Benchmarks: Evaluating LLMs on Real Theoretical Computer Science Tasks

    This article examines a new verifiable benchmark for theoretical computer science (TCS) that evaluates whether large language models can perform genuine research tasks—proposing conjectures, constructing counterexamples, proving theorems, and tightening bounds. It explains why verifiable artifacts matter more than answer matching, breaks down the benchmark's task categories and key results (including improved extremal graph constructions and tightened coding-theory bounds), and distills practical principles for designing AI research evaluations, while outlining where AI still falls short of independent scientific work.

    When AI Starts “Doing Research”: A Verifiable Benchmark for Theoretical Computer Science, Explained

    Introduction: From Answering Questions to Doing Research

    Over the past few years, large language models have posted record scores on standardized exams and programming competitions. But performing well on tests is fundamentally different from conducting research. Real research is defined by open-ended problems, answers with no existing reference, and intermediate steps that must be independently verifiable by peers. Recently, a theoretical computer science (TCS) benchmark jointly proposed by an AI research team and university scholars has drawn attention—it attempts to package real research workflows such as “proposing conjectures, constructing counterexamples, proving theorems, and tightening upper and lower bounds” into a single, automatically verifiable evaluation system. This offers a rare quantitative lens on the question: how far is AI from doing independent research?

    Why Research Evaluation Must Be “Verifiable”

    Traditional model evaluation follows an “answer matching” paradigm: multiple-choice questions are graded right or wrong, math problems are checked against final values, and code is run against test cases. This approach fails for research tasks for three reasons:

    1. Answers take many forms. For an extremal graph construction task, there may be infinitely many valid solutions, so no single answer can be predefined.
    2. Process matters more than the result. The value of research output often lies in intermediate lemmas, construction parameters, or proof structure—not the final conclusion.
    3. Reproducibility is the baseline. A “plausible new answer” from AI is worthless unless it can be turned into an object that an independent program or proof checker can verify.

    The key design principle of this new benchmark is exactly this: rather than judging whether an answer “looks” correct, it requires the model to produce a verifiable artifact—a concrete graph structure, a set of coding parameters, or a machine-checkable proof. A verifier determines whether the artifact satisfies the constraints, converting subjective “research quality assessment” into objective “constraint satisfaction checking.”

    Which Research Activities Does the Benchmark Cover?

    The benchmark draws on classic problems in theoretical computer science and covers multiple stages of the research workflow:

    • Construction tasks: For example, in extremal graph theory, models must construct graphs with as many edges as possible that avoid specific subgraphs (such as triangles or 4-cycles). The model outputs explicit vertex and edge sets, which the verifier checks against constraints while counting the size.
    • Bound-improvement tasks: For example, tightening upper bounds in coding theory, where the model must produce new parameter proofs that compress a previously published upper bound.
    • Reliability verification tasks: For example, alphabet reliability constructions related to PCP (probabilistically checkable proofs), which test how deeply a model understands complex proof systems.
    • Proof completion tasks: Models may choose whether to output intermediate lemmas, and the benchmark records success rates in both “with lemmas” and “direct proof” modes.

    One notable design choice is multi-attempt statistics: the benchmark records not only single-attempt success or failure, but also the overall success rate across dozens of attempts and the number of distinct theorems solved—distinguishing “lucky guesses” from “stable capability.”

    What the Key Results Reveal

    On the full leaderboard, the top two models show a clear performance gap: the leader solved 14 of 20 theorems without intermediate lemmas, a success rate of roughly 70%; the runner-up succeeded 23 times in 60 attempts, covering 9 distinct theorems, a success rate of about 38%; all other participating agents achieved success rates of no more than around 12%.

    But the more interesting detail lies beneath the numbers: this is not simple across-the-board dominance. The second-place model solved the PCP alphabet reliability task on all three attempts, while the top model failed to solve it at all. This shows that current models have uneven capability profiles—they resemble “specialists” excelling at different research skills rather than one universally stronger “generalist.”

    Two representative results also illustrate the practical form of AI research contributions:

    1. In the extremal graph task with girth 5, a model constructed a graph with 124 vertices and 630 edges containing no triangles or 4-cycles—exceeding the reference value of 629 edges used by the task. This is a genuine construction improvement, not a restatement of known results.
    2. In the coding theory upper-bound problem, a model proved that a parameter’s upper bound could be tightened from the published 84 down to 82—a classic “improving a known result” research contribution.

    What these two examples share is that the outputs can be directly verified by a program, with no need for human experts to judge whether they “look right.”

    Lessons for Designing AI Research Evaluations

    Several general principles for designing research-capability benchmarks can be drawn from this work:

    First, prioritize problem domains that are machine-verifiable. Mathematics, theoretical computer science, combinatorial optimization, and formal proof are naturally suited because correctness can be deterministically checked. For domains that are hard to verify automatically (such as experimental sciences), simulation environments or proxy metrics are needed.

    Second, evaluate “artifacts,” not “narratives.” Models should output structured constructions, parameters, or proof scripts rather than natural-language exposition. An illustrative verification flow looks like this:

    1. def verify_construction(artifact, constraints):
    2. """Generic verification framework: check whether the artifact satisfies all constraints"""
    3. for constraint in constraints:
    4. if not constraint.check(artifact):
    5. return False, constraint.violation_detail()
    6. return True, artifact.score() # Quantitative metrics such as edge count or bound value

    Third, record attempt distributions rather than single-shot outcomes. Research is inherently exploratory. Success-rate curves across multiple attempts and breadth of theorem coverage characterize real capability better than a single pass rate.

    Fourth, preserve “counterintuitive samples.” Problems that most models fail but a few solve are often the key signals distinguishing capability structures, and they should not be averaged away in aggregate scores.

    A Sober Look at the Boundaries: What AI Still Cannot Do

    This “capability map” of AI research also clearly marks the boundaries. When three conditions are met—a well-defined problem, sufficient compute budget, and a verifiable feedback signal—models can already complete parts of proofs, program optimization, and construction improvements. But the following stages still require humans:

    • Choosing research directions autonomously: Judging “which problems are worth studying” requires deep understanding of field trends—something models do not yet possess.
    • Assessing the value of results: Whether a result is important or publishable depends on the taste and consensus of the academic community.
    • Solving major open problems: Hard problems requiring long-term accumulation, cross-domain insight, and the invention of entirely new concepts remain far beyond current agents.

    For enterprises and developers, a more realistic framing is to treat these models as “powerful auxiliary engines in the research workflow”—after humans define the problem and the verification criteria, machines efficiently search and iterate over vast candidate spaces. At the engineering level, such intensive reasoning and search workloads place high demands on compute scheduling, task orchestration, and result-validation pipelines. Using general cloud infrastructure capabilities—such as container platforms, object storage, task queues, and logging and monitoring services—to build scalable evaluation and experimentation environments is a common practical path for integrating these capabilities into real R&D workflows.

    Conclusion

    The value of this joint research lies not in any particular leaderboard ranking, but in the paradigm it establishes: replace subjective scoring with verifiable artifacts, replace single-shot luck with multi-attempt distribution data, and replace the vague label of “research ability” with fine-grained task structures. Only when evaluation is rigorous enough can we see both the genuine progress AI has made in theorem proving and construction optimization, and the clear boundaries it faces in choosing directions and judging value. Can AI do research independently? The current answer is: it has become a competent “research executor,” but there is still a long road ahead before it becomes a “research decision-maker.”