TCSExam: Evaluating Frontier LLMs on Theoretical Computer Science Research
TCSExam is a benchmark that assesses frontier large language models on theoretical computer science research. Built by five co-authors—including a Turing Award laureate and the founder of Moonshot AI—and graded with the help of domain experts, it asks nine leading models to tackle problems spanning computational complexity, graph theory, coding, cryptography, and more. Its headline finding is striking: no evaluated model could independently solve a single open conjecture. This article explains what theoretical CS actually tests, why open problems expose the limits of current models, how mathematical verifiability shapes AI performance, how the benchmark is graded, and how to build a reproducible evaluation system—along with a developer checklist for judging whether a model's math capabilities are trustworthy.
Introduction: A Defense That Tests Reasoning and Proof
A preprint co-authored by five researchers appeared on a public preprint server on November 5. The authors come from a university interdisciplinary information research institute, a research institute led by a Turing Award laureate, and an LLM startup. One author is a Turing Award winner and dean of Tsinghua University’s Institute for Interdisciplinary Information Sciences; another is Yang Zhilin, founder of Moonshot AI. The paper turns theoretical computer science into a set of evaluation problems, invites nine mainstream or representative large models to take part, and involves domain experts in both setting and grading the questions.
Titled “TCSExam: A Comprehensive Assessment of Frontier Large Language Models on Theoretical Computer Science Research,” the work aims at more than a ranking. It tries to answer a deeper question: are large models just solving problems, or are they already showing the first signs of being able to do research?
1. What TCSExam Is: What Theoretical Computer Science Actually Tests
To understand the benchmark, first understand theoretical computer science. It is not “how to fix a computer,” nor “how to write a program that runs.” It studies computation itself: at best, how fast can you get from point A to point B? Under given constraints, is there a route that simply cannot work? Can a given algorithm or construction be rigorously proven?
TCS sits at the intersection of mathematics and computer science. Typical directions include computational complexity, circuits and lower bounds, graph theory and combinatorial optimization, coding and cryptography, learning theory, and quantum computing and interactive proofs. All of these rely on rigorous proof: premises must be clear, each step must be checkable, and conclusions must be reproducible by others.
In terms of the capability structure, a TCS benchmark examines at least four abilities:
| Capability | Meaning | Scenario |
|---|---|---|
| Formalization transfer | Turning natural-language, graph, or constraint descriptions into precise formal definitions | Abstracting a call-count problem into a graph-theory model |
| Direction selection | Judging whether a statement is true or false, and deciding whether to prove an upper or lower bound | Determining the direction of the error in approximation-algorithm analysis |
| Long-range reasoning | Completing multi-step derivations under limited resources while keeping the argument consistent | Constructing reductions, inductions, or counterexamples |
| Error localization and correction | Finding gaps in an argument and providing a fix | Handling missed edge cases or insufficient lemma conditions |
2. Why LLMs Can’t Crack Open Conjectures: Knowledge Boundaries and Long-Range Consistency
The most striking result of the evaluation is this: no reference model was able to independently solve a single open conjecture. An open conjecture is a mathematical proposition that has been neither rigorously proved nor disproved. It is a “no reference answer” task: no one knows the standard solution, so a model cannot bypass reasoning through memorization or retrieval alone.
This result reflects two kinds of boundaries. The first is the boundary between recombining knowledge and creating knowledge. Current models are good at transferring, analogizing, and combining existing knowledge, and they usually give fairly stable answers when conditions are swapped out. But open problems often require proposing new lemmas, constructing new objects, or identifying where an existing framework breaks down. The second is the boundary of long-range consistency. Research-grade proofs often contain long chains of logic that require trial and error, backtracking, and internal consistency. Model generation is a probabilistic process: the longer the chain, the greater the risk that a local error propagates downstream. A model may also be unable to reliably judge which step of its own argument is pivotal and which is suspect.
This is why involving domain experts in setting and grading is necessary. Whether a model’s output holds up, and whether it touches a known technical difficulty, can often be judged only by experts.
3. Mathematical Verifiability: Why AI Tends to Score Well, and Where the Boundary Lies
Mathematics is often seen as a field where AI more easily earns recognition, because of verifiability. Many mathematical propositions can be broken into lemmas, each step of the derivation written in a checkable form, and then handed to an automated checker for confirmation. Mathematician Terence Tao has said publicly that AI tends to make hard-to-verify errors in many areas, while mathematical proofs are relatively better suited to machine checking. This makes math benchmarks easier to yield objective conclusions.
But verifiability also has limits. Competition-style problems have objective criteria, yet research-grade proofs still require expert review. First, verifiable is not the same as discoverable: a machine can check a proof but cannot replace the creative step of “figuring out what to prove.” Second, formalization is itself a barrier: turning a natural-language proposition into a logical formula or type signature requires semantic understanding and technical expertise. Third, formal verification is more effective for problems with clear definitions and concrete propositions; open-ended research within complex theoretical frameworks usually still requires human involvement and expert review.
4. Solving Problems vs. Doing Research: Why TCSExam Is More Discriminative
Model leaderboards update quickly, but a leaderboard shows that a model can solve problems, not necessarily that it can do research. Solving problems usually has a known answer, a fairly fixed path, and clear evaluation criteria; research often has an unknown answer, requires constructing the path yourself, and is judged on correctness, rigor, and novelty.
| Dimension | Problem-solving benchmark | Research-style benchmark |
|---|---|---|
| Is the answer known | Usually yes | Often no |
| Solution path | Existing patterns can be reused | Must construct the argument path yourself |
| Evaluation | Mainly answer comparison | Assesses proof correctness, novelty, and rigor |
| Data contamination risk | Higher | Relatively lower |
| Typical questions | Math competition problems, programming problems, exam questions | Open conjectures, new theorems, provable lower bounds |
By choosing open conjectures, TCSExam essentially pushes evaluation from a test of memory toward a test of reasoning. It is more like a thesis defense: a model must not only give a conclusion but also show its chain of argument and submit to expert scrutiny.
5. How Grading Works: Process Evaluation and Contamination Control
Open problems have no standard answer, so the evaluation must solve the question of “who grades.” The design typically approaches this from three angles.
First, accuracy should not be judged by the final result alone but through a combination of expert review, formal checking, and peer reproduction. Second, process evaluation matters more than result evaluation. Derivation steps, key lemmas, error backtracking, and verifier feedback can all serve as process metrics that help identify where a model gets stuck. Third, anti-contamination design. If a problem or its answer already appears in the training data, a model’s performance may be inflated, so the evaluation set needs to be updated dynamically and to retain private, unpublished new problems.
6. Engineering Perspective: Building a Reproducible Evaluation System
From an engineering standpoint, this kind of evaluation must handle problem construction, version management, verifier selection, and pipeline scheduling. A simplified problem structure looks like this:
from dataclasses import dataclassfrom typing import Optional@dataclassclass TCSProblem:problem_id: strdomain: strstatement: strformal_statement: Optional[str]expected_output: strref_solution: Optional[str]is_open_problem: booldifficulty: strverifier: strpublic_since: Optional[str]private: boolprompt_version: strmodel_version: strverifier_version: str
Different problem types are verified in different ways: decision-type problems can be answer-compared; construction-type problems can be checked by running the result; proof-type problems need formal checking combined with human review; and open conjectures mainly rely on expert review and peer reproduction.
The evaluation pipeline can follow logic like this:
def run_eval(problem: TCSProblem, model):candidate = model.solve(problem.statement, domain=problem.domain)if problem.verifier in {"kernel_check", "constraint_check", "simulator"}:result = verify(candidate, problem.verifier)if result.valid:return {"status": "correct","by": "automatic","verifier_version": problem.verifier_version,}if result.uncertain or result.risk:return {"status": "manual_review","queue": "expert_review","candidate": candidate,"reason": result.reason,"by": "uncertain",}return {"status": "incorrect","by": "automatic","reason": result.reason,"verifier_version": problem.verifier_version,}if problem.is_open_problem or problem.verifier == "expert_review":return {"status": "pending","queue": "expert_review","candidate": candidate,}return {"status": "manual_review","queue": "expert_review","candidate": candidate,"reason": "Unable to decide automatically; manual review required",}
Engineering also needs containerized isolation, a task queue, object storage, logging and monitoring, and elastic compute. Teams can rely on the general-purpose capabilities that mainstream cloud platforms provide—container services, object storage, message queues, and logging and monitoring—without building a full infrastructure stack themselves. More importantly, record the problem version, model version, prompt version, verifier version, and random seed; otherwise a single evaluation result is hard for peers to trust.
7. Developer Checklist: Judging Whether a Model’s Math Ability Is Trustworthy
Faced with the capabilities a model advertises, developers can check against a list:
- Is the task automatically verifiable? If not, is there human review?
- Is the evaluation set private or dynamically updated? Is there data contamination?
- Are the model version, prompt version, and verifier version fully recorded?
- Does the evaluation assess the reasoning process, not just the final conclusion?
- Can you reproduce the evaluation environment, problem versions, and results?
Conclusion: Evaluation Is Not the Endpoint but a Measurement of the Boundary
This TCS evaluation, carried out with the participation of a Turing Award laureate and a large-model team, reaches a conclusion that is not flashy but solid: no reference model independently solved a single open conjecture. This is both a truthful picture of current large-model capability and a real-world boundary drawn for AI mathematics research.
But boundaries are not static. The point of an evaluation is not to “sentence” a model but to keep measuring where the boundary lies. Each evaluation is like taking a temperature: only by knowing the temperature can you judge the condition. For developers and researchers, what really matters is not the score but where the model gets stuck—formalization transfer, long-range reasoning, error correction, or knowledge creation? Understanding these steps is what lets us design more reliable evaluation systems and take the next step in AI mathematics research on firmer ground.
