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:

    1. from dataclasses import dataclass
    2. from typing import Optional
    3. @dataclass
    4. class TCSProblem:
    5. problem_id: str
    6. domain: str
    7. statement: str
    8. formal_statement: Optional[str]
    9. expected_output: str
    10. ref_solution: Optional[str]
    11. is_open_problem: bool
    12. difficulty: str
    13. verifier: str
    14. public_since: Optional[str]
    15. private: bool
    16. prompt_version: str
    17. model_version: str
    18. verifier_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:

    1. def run_eval(problem: TCSProblem, model):
    2. candidate = model.solve(problem.statement, domain=problem.domain)
    3. if problem.verifier in {"kernel_check", "constraint_check", "simulator"}:
    4. result = verify(candidate, problem.verifier)
    5. if result.valid:
    6. return {
    7. "status": "correct",
    8. "by": "automatic",
    9. "verifier_version": problem.verifier_version,
    10. }
    11. if result.uncertain or result.risk:
    12. return {
    13. "status": "manual_review",
    14. "queue": "expert_review",
    15. "candidate": candidate,
    16. "reason": result.reason,
    17. "by": "uncertain",
    18. }
    19. return {
    20. "status": "incorrect",
    21. "by": "automatic",
    22. "reason": result.reason,
    23. "verifier_version": problem.verifier_version,
    24. }
    25. if problem.is_open_problem or problem.verifier == "expert_review":
    26. return {
    27. "status": "pending",
    28. "queue": "expert_review",
    29. "candidate": candidate,
    30. }
    31. return {
    32. "status": "manual_review",
    33. "queue": "expert_review",
    34. "candidate": candidate,
    35. "reason": "Unable to decide automatically; manual review required",
    36. }

    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:

    1. Is the task automatically verifiable? If not, is there human review?
    2. Is the evaluation set private or dynamically updated? Is there data contamination?
    3. Are the model version, prompt version, and verifier version fully recorded?
    4. Does the evaluation assess the reasoning process, not just the final conclusion?
    5. 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.