Evaluating LLM Research Ability with Theoretical Computer Science (TCS): Why Grading Is the Hard Part
A recent paper co-authored by a Turing Award laureate, academic researchers, and AI startup founders proposes a new way to measure whether large language models can do real research: give them roughly 100 theoretical computer science problems, then grade the answers automatically. This article explains what theoretical computer science actually studies, why standard leaderboards only show that a model can solve exercises rather than conduct research, why TCS is unusually well suited to machine grading, and what the results mean for AI engineering teams. Key takeaways: research ability is hard to evaluate mainly because grading is hard; TCS results are mathematical claims that can in principle be verified by a machine; current top models did not independently solve any of the open problems in the benchmark; and the "generate, formalize, verify" pattern is a reusable approach for building objective, reproducible model evaluations.
A Well-Timed Paper
A recent paper on evaluating the research ability of large models has attracted considerable attention. The author list spans a Turing Award laureate, heads of interdisciplinary computer science research institutes at universities, and founders of newer AI companies, cutting across academia and research labs.
What the paper does is straightforward: it builds an exam and hands it to the strongest models currently available.
The core shorthand in the paper is TCS — theoretical computer science. It deserves separate attention because it targets the most awkward weak point in the whole enterprise of evaluating model research ability: grading.
Understanding why the paper matters requires answering three questions, each building on the last. What does theoretical computer science actually study? Why do existing leaderboards fail to capture real research ability? And why is TCS, specifically, able to offer a relatively objective answer?
Theoretical Computer Science: It Is Not About Repairing Computers
People often take the name literally and assume theoretical computer science is about how to use computers or how to write code. That is a common misunderstanding.
Consider an analogy. If a programmer is like a driver, focused on how to tune the engine or fit out the interior, then theoretical computer science is concerned with traffic itself: what is the theoretically fastest possible time to travel from point A to point B? Are there routes that are provably impassable? What performance lower bound can a computation reach when resources are constrained?
The field sits at the intersection of mathematics and computer science, and every question in it revolves around computation. Its central method is not writing programs and running experiments, but producing rigorous mathematical proofs. Its typical subfields include:
- Algorithms and complexity theory: the efficiency with which problems can be solved, and whether an entire class of problems admits no efficient algorithm at all, such as the classic P versus NP question.
- Computational geometry: algorithm design over geometric objects, for example convex hulls of point sets and closest-pair problems.
- Foundations of cryptography: the computational hardness assumptions that security proofs rest on.
- Theory of distributed and parallel computing: what performance is achievable, and what conclusions hold, when multiple parties must cooperate.
What these areas share is that the correctness of a result can, in principle, be checked automatically by a machine. That single property is exactly what makes the field interesting as a substrate for evaluating large models.
Benchmark Leaderboards: Solving Problems Is Not Doing Research
Leaderboards for large models get refreshed every few weeks, and the sheer number of rankings is bewildering. But these leaderboards share a fundamental mismatch: they demonstrate that a model can solve exercises, not that it can do research.
The gap is easiest to see through cooking. Solving exercises is fundamentally following a recipe: the steps are given, the heat and timing are specified, and there is a reference dish to compare against. It is hard to imagine adding chocolate to guō bāo ròu and still counting it as correct. Real research has no recipe. The steps are not prescribed, nobody knows in advance whether the path works, and for some problems even the person posing the question does not know the answer.
That is the first layer of the problem: the gap between solving and researching. A model that scores highly on a leaderboard may have no ability to pose new questions, design new proofs, or explore paths that nobody has walked. Those capabilities are the core of what “research” means.
The Grading Problem: Who Says It Is Right, and Who Checks?
Harder than “research is difficult” is “evaluating research is difficult,” and the difficulty concentrates on grading.
Imagine a model claims to have settled a conjecture that has stood open for decades, and outputs a long chain of argumentation. Who decides whether the argument is correct? If the expert doing the grading cannot verify it within a reasonable amount of time either, then the credibility of the claimed result drops sharply.
Not long ago, an AI research organization released several hundred AI-generated mathematical manuscripts at once, grouping them by relevance into a number of “result families” spanning number theory, theoretical computer science, geometry, and mathematical physics. “AI is going to replace mathematicians” briefly trended on social media. But it is precisely this kind of volume that makes the verification question more acute, not less.
A well-known mathematician has observed to leading international scientific journals that AI has a fatal flaw in many fields: it makes errors that cannot be checked. Mathematics is the exception, and especially so for proofs, where right and wrong can be handed to a machine for automatic inspection. It works a bit like Sudoku: filling in a complete solution is hard, but once it is filled in, a quick pass tells you whether it is correct.
So the logic becomes clear. The places where AI is most likely to produce solid results, with the least room for dispute, are mathematics and verifiable reasoning. Applying that verifiability to the assessment of research ability requires a discipline whose properties are naturally suited to machine grading — and theoretical computer science fits the bill.
Why TCS Specifically: Tailored for Machine Grading
Putting these threads together, the case for choosing TCS as the evaluation substrate is quite tight:
- The closer a problem is to real research, the harder it usually is to grade. Open-ended problems and open-ended designs often have no reference answer at all. They are hard even for human graders, let alone automated ones.
- TCS is the exception. Its results are mostly stated as mathematical propositions, and in principle can be verified by a machine. Whether an answer is right or wrong does not depend on subjective scoring and can move toward objective judgment.
- TCS therefore satisfies two requirements that look contradictory at once: problems that are genuinely research-like, and problems that a machine can grade.
This is the real cleverness of the methodology. It does not dodge the difficulty that research ability is hard to evaluate. It deliberately selects an entry point where evaluation becomes operable and reproducible.
How the Benchmark Is Designed: Around 100 Problems Across Four Research Task Types
According to the paper, the exam contains roughly one hundred problems, grouped into four categories based on the kinds of work theoretical computer scientists actually do, with the aim of covering different facets of research activity. The individual problems have not been made public, but benchmarks of this kind generally follow these methodological principles:
- Coverage of real research actions: not just recalled results, but the process of derivation — for instance, whether a correct proof can be constructed under given conditions.
- Difficulty aligned with research: problems typically require multi-step reasoning and synthesis across knowledge areas, rather than recalling a single fact.
- Machine-verifiable conclusions: answers are either definite mathematical propositions, or can be checked by formal verification tooling.
- Open boundaries: some problems are labeled as currently unsolved open questions, used to test whether a model can genuinely explore the unknown.
One engineering detail is worth attention from technical teams. To make machine grading actually work in practice, natural-language proofs generally need to be converted into formal expressions and then handed to an interactive theorem prover or dedicated checking logic for automated inspection. This “generate — formalize — verify” pipeline is itself a fairly typical automated evaluation system.
A Reality Check: No Open Conjecture Was Independently Solved
The results, to some degree, cool the enthusiasm. For the open conjectures in the set that remain unresolved, none of the models evaluated was able to solve one on its own.
The finding deserves a balanced reading, neither exaggerated nor dismissed:
- It shows a real gap between bulk output and solving genuine problems. Models can generate large volumes of text that looks rigorous, but when facing truly unknown hard problems, they remain visibly short of independent breakthroughs.
- It also validates the value of verifiable evaluation. Precisely because the results can be machine-checked, it is possible to make a clear and credible judgment here — far more reliable than subjective assessments of the form “I think the model is strong” or “I think the model is weak.”
Put differently, verifiability is not only what makes the evaluation possible; it is also what makes the sober conclusion itself credible. That is precisely the distinctive advantage of mathematics and theoretical computer science over many other fields.
Practical Takeaways for Developers
Setting the specific paper aside, this methodology offers several transferable lessons for teams building AI applications:
- Separate “solving ability” from “research ability.” If your scenario consists of standardized tasks, conventional leaderboards are sufficient. If it involves open-ended reasoning, complex proofs, or solution design, you need evaluation that sits closer to real tasks.
- Prefer evaluation substrates that can be verified. For any task whose answer can be checked automatically — code passing unit tests, a query returning the expected result set, a proof passing formal verification — you can borrow the same objective-grading approach and avoid the subjectivity and poor reproducibility of human review.
- Build a generate-and-verify loop. Take code generation: have the model produce an implementation, then filter it automatically with test cases and static checks, producing a quantifiable pass-rate metric.
- Prepare infrastructure for large-scale evaluation. Running hundreds of multi-step reasoning problems, invoking formal verification, and recording and comparing results across model versions all require stable compute scheduling and workflow orchestration. Teams can build the evaluation pipeline on general-purpose cloud capabilities such as container platforms, task orchestration, object storage, and monitoring and alerting; platforms like Baidu AI Cloud typically provide components of this kind and can serve as the foundation for a self-built evaluation system.
Summary
What the paper is really trying to answer is a plain question: if you actually put a large model to work on research, how far does it get?
The answer has two layers. Methodologically, theoretical computer science — thanks to results that can be machine-verified — supplies a scarce measuring stick for a capability that is otherwise hard to evaluate objectively, and it neatly sidesteps the dead end of grading. In terms of findings, current top models still could not independently crack the genuinely open problems. That is a reminder that AI has become remarkably good at cooking from a recipe, and still has a long way to go on cutting a new path from scratch.
For technical teams, a more useful question than “how strong is the model” is how to measure, in a verifiable and reproducible way, the model’s real ability on the tasks you actually care about. That is both the science of evaluation and the step you should least want to skip when deploying AI into serious settings.
