Evaluating LLM Research Capabilities: Why Theoretical Computer Science Is the Key Yardstick
LLM benchmarks are advancing quickly, yet most leaderboards measure problem-solving rather than genuine research ability. This article explains why theoretical computer science (TCS) is a compelling ground for evaluating research capability: its conclusions are far cheaper to verify than to produce, which makes automated grading feasible even for frontier-level problems. It walks through a representative research-grade benchmark built around four core research actions, machine-checkable scoring, and roughly 100 problems spanning multiple TCS subfields. The key finding—that no evaluated model could independently solve the open conjectures—exposes the gap between exam performance and real research ability. The article closes with practical guidance for teams that want to build reliable, reproducible research evaluations.
1. The Evaluation Dilemma: Scores Keep Rising, but “Research” Stays Untested
Over the past two years, LLM benchmark scores have been refreshed every month or two, and new leaderboards appear constantly. Yet these leaderboards share a common limitation: most of them measure problem-solving ability, not research ability.
The difference can be illustrated with an analogy. Solving problems is like cooking from a recipe—the steps are given, the standard answer is clear, and the final dish is judged against a common scale. Even if you occasionally improvise, judges can immediately tell whether you have gone off track. Real research has no ready-made recipe: there are no fixed steps, no one knows in advance whether a result will hold, and in many cases even the person who posed the problem cannot produce the answer.
This leads to two direct consequences:
- Capability mismatch: A model that tops every question bank is not necessarily equipped with the research qualities of posing new problems, designing proof strategies, or judging whether a conclusion is sound.
- Scoring difficulty: If a model claims to have settled a conjecture that has remained open for decades, who verifies that the proof it wrote is correct? The field has repeatedly seen models generate large volumes of “research manuscripts” that are difficult to check one by one. The reliability of scoring directly determines the credibility of the evaluation.
So the first step in evaluating an LLM’s research ability is to design problems that are both close to real research and automatically gradeable. Theoretical Computer Science (TCS) is one of the few fields that satisfies this condition.
2. Why Theoretical Computer Science
TCS sits at the intersection of mathematics and computer science. Every problem revolves around “computation,” and the primary tool of research is the formal proof.
An analogy helps here. If programmers writing code are like drivers focused on the car itself—the engine, the interior—then TCS studies “traffic”: the theoretical fastest way to get from point A to point B, and which routes are fundamentally impassable. It does not ask how a specific engineering task is implemented; it asks where the boundaries of computation itself lie.
The core reason TCS is well suited to research evaluation is a single property: the verifiability of its conclusions far exceeds the cost of verifying them.
This is similar to Sudoku: filling in a solution can be very hard, but checking whether it is correct is just a quick scan. In TCS, once many results are written up as proofs in a standard form, they can be checked by a verifier or by peers through mechanical steps. In other words:
- Proposing and solving is hard, and sometimes open;
- Checking a result is comparatively easy and can be automated.
This “hard to generate, easy to verify” asymmetry makes TCS an ideal evaluation vehicle—we can probe a model’s research depth without falling into the trap of “no one able to grade the papers.”
3. Building the Evaluation System: From “Doing Problems” to “Doing Research”
A representative study offers a methodological framework: academic institutions and frontier model teams worked together to build a research-grade benchmark covering the full breadth of TCS. Its design is worth breaking down into a few key steps.
3.1 Define the Goals: Four Research Actions
The problems are not assembled at random. They correspond to four kinds of work that theoretical computer scientists actually do every day. This layered design ensures coverage:
- Prove a given proposition: Complete a rigorous proof within an existing framework, testing the soundness of reasoning.
- Construct a counterexample or algorithm: Produce a construction that meets a specific complexity requirement, testing divergent and constructive thinking.
- Decide whether a proposition is true or false, with justification: Make the correct call under incomplete information, testing grasp of the essence of a problem.
- Attempt an open problem: Push forward on a conjecture that has no accepted answer yet.
The first three categories lean toward abilities with definite answers, while the fourth points directly at the research frontier. This gradient design both yields clear scores and reveals how models perform on genuinely unknown problems.
3.2 Machine-Gradeable Scoring as a Hard Constraint
The entire problem set follows one rule: only include problems a machine can grade.
The closer a problem gets to real research, the harder it usually is to score automatically. TCS is a fortunate exception, since most of its conclusions can be formally verified. The scoring pipeline can be abstracted into the following illustrative logic:
def evaluate_response(problem, model_output):"""Scoring pipeline for research-capability evaluation (illustrative)problem: problem description with a well-defined, verifiable goalmodel_output: the proof / construction / decision submitted by the modelreturns: whether the response passes strict verification"""# 1. Structural parsing: extract proof steps or the constructed objectproof = parse_formal_proof(model_output)# 2. Verifiability check: is it in a machine-checkable form?if not is_machine_checkable(proof):return Score.INVALID # not verifiable -> scored as failure, no "human fallback"# 3. Mechanical verification: the verifier checks the reasoning chain step by stepif verifier.check(proof, problem.spec):return Score.CORRECTreturn Score.INCORRECT
The value of this design is that it cleanly separates “having the ability” from “sounding convincing.” A model cannot slip through with polished wording; only a proof that genuinely holds will pass.
3.3 Problem Set Size and Difficulty Distribution
A usable benchmark needs enough problems and a range of difficulty levels. The framework described contains about 100 problems spanning multiple TCS subfields, from relatively standard questions all the way to open conjectures. This scale is large enough to distinguish models statistically, without letting evaluation costs spiral out of control.
3.4 Contamination Control and Timeliness
The thing a research benchmark fears most is “problem leakage.” Because frontier models are trained on ever-expanding data, the benchmark must continually refresh its problems and control their visibility, so that models have not “seen the answers” during training. This is the hidden engineering that keeps the evaluation valid.
4. What the Results Actually Tell Us
The most informative conclusion from this evaluation is not “who scored highest,” but a more fundamental finding: when faced with the open conjectures that remain unresolved to this day, not a single participating model could crack them independently.
The significance of this result is that it pours cold water on the hype:
- It separates “exam ability” from “research ability.” Models perform excellently on standard problems, but they still fall short on genuinely unknown ones.
- It demonstrates the effectiveness of the evaluation method. Precisely because the problems are hard enough and close enough to the research frontier, the method can surface this gap—which is itself an endorsement of the benchmark’s quality.
- It gives practitioners a sober point of reference. A boom in benchmark scores does not mean research capability has matured; the value of evaluation lies in exposing gaps, not manufacturing surprises.
In a sense, this kind of study offers some relief to those wondering “will AI replace mathematicians”: at least when it comes to posing and cracking truly open problems, current models still have a clear distance to cover.
5. How to Build a Reliable Research Evaluation in Practice
For teams that want to build similar evaluation capability, a few general practices stand out:
- Prioritize verifiable domains. Fields like mathematics, formal methods, and complexity theory—where conclusions can be machine-checked—are naturally suited to research-grade evaluation. The more objective the scoring step, the more credible the conclusion.
- Separate capability levels. Layer the design into “standard problem-solving,” “construction and refutation,” and “open exploration” so you can see a model’s true level across different dimensions.
- Automate scoring; refuse human fallback. Once you allow subjective human score adjustments, the reproducibility of the evaluation breaks down. The third step of the illustrative pipeline must be executed strictly by the verifier.
- Control problem timeliness and visibility. Continuously refreshing problems and isolating access to reduce contamination risk is the lifeline of any long-term evaluation.
- Provide engineering support. Evaluation often involves large-scale concurrent model calls, problem version management, logging of verification results, and traceback of failed samples. Mature, general-purpose infrastructure can significantly lower the cost of building this. For example, a container platform can host the isolated execution environment for the verifier, object storage can archive problems and submissions, a message queue can schedule large volumes of evaluation tasks, and logging with monitoring and alerting can track overall progress and anomalies. On cloud platforms such as Baidu AI Cloud, these general product categories are typically available and can be combined into a stable, scalable evaluation pipeline, without building everything from scratch.
6. Conclusion
LLM evaluation is shifting from “who scores higher” toward “who is closer to real capability.” Theoretical computer science is a key yardstick not because of how deep or obscure it is, but because it possesses two things at once: problems that are close enough to the research frontier, and conclusions that a machine can strictly verify.
What this evaluation tells us is that truly measuring AI’s research potential requires problems that can test the “unknown,” along with a grading mechanism that can hold the line on “true versus false.” When the noise of benchmark scores fades, evaluation that is verifiable, reproducible, and clearly layered is the reliable foundation for understanding this technology and pushing it forward.
