TCS Benchmark for LLMs: A Litmus Test for Frontier Model Research Ability
A new evaluation targeting theoretical computer science (TCS) tests frontier large language models on full-domain research ability through 100 tasks across four categories. Notably, no participating model solved any of the listed open conjectures, exposing a clear layering of current model capabilities. This article explains why general leaderboards fail to measure research, how machine-verifiable problems make grading tractable, how to correctly interpret the results, and how engineering teams can apply a generate-verify-measure loop to put AI to reliable use in both research and development.
1. Introduction: Why Mathematicians Wanted a “Cold Shower” Exam
In November 2025, a paper posted to a public preprint platform drew attention. Its authors came from universities, research institutes, and frontier model teams, and included a Turing Award laureate along with the head of a frontier large-model team. The paper targets theoretical computer science (TCS) and proposes a full-domain research evaluation for frontier large language models.
TCS studies “computation” itself. It is not concerned with how a particular machine is assembled or how a piece of code is written, but with the fundamental laws of everything that can be computed: whether a problem can be solved, the minimum time and space resources it requires, and which problems are provably unsolvable. If programmers are like drivers, TCS studies traffic itself—the fastest way to get between any two points, and which routes are simply impassable. It sits at the intersection of mathematics and computer science; its core method is mathematical proof, and its frontier advances often come from resolving a long-standing open conjecture.
The timing of this evaluation is telling. In early October that year, a frontier model team publicly released a batch of AI-generated mathematical manuscripts—several hundred in total—spanning number theory, theoretical computer science, geometry, mathematical physics, and more. Social media soon filled with debate about “AI disrupting mathematical research.” Indeed, the most convincing results from AI companies today are concentrated in mathematics, precisely because the correctness of mathematical conclusions—especially proofs—can be checked automatically by machines, without relying on experiments or the subjective judgment of experts, leaving far less room for dispute.
Yet this TCS research evaluation produced a surprising scorecard: on the listed open problems (conjectures that remain unsolved), no participating model was able to solve any of them on its own. This poured cold water on the optimistic expectation that “AI is about to replace researchers.” More importantly, it is worth understanding why the test was designed this way and how its results should be interpreted correctly.
2. Why “Research Ability” Needs Its Own Exam
2.1 Why General Leaderboards Can’t Measure Research
LLM benchmarks refresh their rankings almost every few months. But the vast majority measure “problem-solving,” not “research.” The essential differences can be summarized as follows:
- Process: Problem-solving usually follows a fixed, learnable routine; research has no ready-made path, and every step requires judgment.
- Answer: Problem-solving answers exist in advance and are standardized; the problems research faces often have no known answer, not even to the person who posed them.
- Verification: Problem-solving only requires checking against a standard answer; research demands proof that a conclusion holds, or a verified counterexample or construction.
- Samples: Classic problem sets have been circulated for a long time and may already be in a model’s training data—a high score may not reflect genuine reasoning ability.
So a high leaderboard rank only shows that a model can “solve problems”; it does not mean the model has research ability.
2.2 Grading Is the Biggest Bottleneck
Even with carefully selected open-ended research problems, grading remains the hardest part. A model may generate hundreds of pages of proof at once; if a single irreparable logical flaw is buried within, the entire output loses its value, while manually reviewing it page by page is extremely costly. When a model claims to have cracked a conjecture that lay dormant for decades, who confirms—and by what standard—that it actually wrote it correctly? The debate over the batch of AI-generated mathematical manuscripts mentioned earlier arises precisely at this point.
2.3 TCS: One of the Few Fields Where “Machines Can Grade”
TCS is one of the few fields that can bypass this bottleneck. Its core outputs are theorems and proofs: all the information needed to determine correctness (definitions, assumptions, reasoning steps) is contained within the text and can be handed directly to the kernel of an automated theorem prover for checking. The classic four-color theorem is a famous precedent: mathematicians used computers to exhaustively check over a thousand irreducible configurations and completed the verification, and later related work produced a formal proof that can be verified in a proof assistant. Such work has always been accompanied by the debate over “whether a machine proof counts as a mathematical proof.” But objectively, TCS conclusions have the property of being mechanically verifiable—and this is precisely the premise that makes them suitable for evaluation.
3. Evaluation Design: Let “Grading” Come Before “Question-Setting”
This evaluation makes one key inversion in its approach: first ensure that every problem’s result can be determined by machine, then select and design the specific problems.
3.1 Four Task Types, Corresponding to Four Everyday Actions of Researchers
The full test contains 100 problems, divided according to four core categories of a theoretical computer scientist’s work:
- Solving open problems: Facing an unsolved conjecture, the model must provide a complete proof or a convincing advance. This is the category closest to “research itself,” and it is where all models collectively failed.
- Retrieving known results: Tests whether the model can accurately reproduce important known results in the field and their proof ideas. This checks mastery of domain knowledge, and models performed relatively stably here.
- Construction and design: Requires providing algorithms, data structures, or combinatorial structures that satisfy specific constraints, testing the model’s ability to construct objects “from nothing.”
- Classification and distinction: Distinguishing which problems are solved and which remain open, or judging whether two superficially similar problems are fundamentally different at the complexity level, testing the model’s grasp of the state of research.
3.2 Problem Bank Selection: Three Hard Criteria
For these 100 problems to form a credible “research exam,” candidate problems must satisfy at least three conditions simultaneously:
- Verifiable: The conclusion can be confirmed by mechanical means.
- Uncontaminated: The problem and its answer have not appeared in public corpora, or the answer itself is unknown.
- Gradable: The scoring rules are clear, and different evaluators using the same standard reach the same result.
This design provides a transferable paradigm for building “research-grade evaluations.” Conversely, if a company wants to assess a model’s true ability in its own business, it should likewise prioritize tasks that can be automatically verified: for code generation, whether it passes unit tests and static checks; for data analysis, whether conclusions can be recomputed; for document processing, whether extracted fields align with a standard answer. Only by designing the “acceptance criteria” before the “problems” can evaluation results be credible.
4. Interpreting the Results: What It Means That No Model Solved the Open Conjectures
The conclusion should not be simplified to “large models can’t do research.” A more accurate understanding is to see the current layering of model capabilities:
- Layer 1: Reproducing and restating knowledge. For classic results and proof lines in a domain, models have a good grasp and can give key steps fairly accurately.
- Layer 2: Routine derivation and construction. For problems with clear goals and relatively definite steps, models can complete a fairly large proportion of solutions.
- Layer 3: Long-chain, cross-module synthesis reasoning. Once reasoning must span multiple lemmas and stay logically consistent across several to dozens of pages, the error rate rises noticeably.
- Layer 4: Original research toward open problems. Currently, no model can complete this independently.
Open problems form a watershed for three reasons:
- They require proposing new ideas, not just applying old methods. The core difficulty of research lies in finding the “right angle of attack,” which usually means a fresh understanding of a problem’s structure rather than a rearrangement of existing techniques.
- There are no samples to imitate. Training corpora contain almost no complete solutions to such problems, so models can only rely on internal reasoning.
- Failures are hard to localize. In open-ended solving, a model’s errors are often an entire line of thought going in the wrong direction, rather than a single miscalculation—precisely the self-correction scenario at which current models are worst.
5. Engineering Implications: How to Apply This Evaluation Approach in Development
5.1 Replace “One-Shot Generation, Manual Acceptance” with a “Generate-Verify” Loop
Whether doing research or engineering, the most reliable way to use AI is to combine the high-speed generation that machines are good at with the automatic verification that machines can reliably perform, while humans set the direction and make judgments.
# Illustrative code: the evaluation logic of a generate-verify loopMAX_ROUNDS = 3 # maximum attempts per taskdef evaluate(model, task, verifier):# 1. Understand: have the model first give a formal statement of the problem, then have a human quickly confirm itunderstanding = model.parse(task)assert reviewer.approve(understanding), "Problem understanding is off; terminate and correct"# 2. Solve: allow the model to iterate based on verification feedbackfor attempt in range(MAX_ROUNDS):candidate = model.solve(task, context=understanding)# 3. Verify: hand the mechanically checkable parts to the verifier# proof problems use formal proof checking, construction problems use constraint tests, engineering problems use unit testsreport = verifier.check(candidate)if report.passed:return candidate, reportcandidate = model.revise(candidate, feedback=report.errors)# 4. Fall back: when automatic verification is not possible, hand off to human review and record the failure reasonreturn None, report
Applied to concrete scenarios, this can be summarized in four practical principles:
- Task decomposition: Break research or complex tasks into small, independently verifiable pieces, each with a clear set of acceptance criteria.
- Verification first: Define “what counts as correct” before letting the model generate answers, avoiding large amounts of rework.
- Independent checking: Verify results by means that are independent of the generation process—for example, checking code with unit tests and checking logic with formal tools.
- Human in the loop: Set up human confirmation points at key stages, especially where automatic verification cannot cover matters requiring judgment.
Cloud providers are also productizing these capabilities. For example, Baidu AI Cloud offers a full set of tools around LLM applications—from model access and agent orchestration to application hosting. These tools connect with engineering practice: model capabilities are invoked through standardized interfaces, verification logic is plugged into business systems via function calls, and runtime performance is continuously measured through logging, monitoring, and evaluation services. In other words, a complete “generate-verify-measure” loop is a key link in taking large models from demo to production.
5.2 Key Points for Designing an Evaluation System
| Dimension | Common practice | Research-grade / production-grade recommendation |
|---|---|---|
| Problem source | Public problem sets | Private bank + dynamic generation + regular updates |
| Scoring method | Comparing against standard answers | Machine-verifiable targets + formal or test-based checking |
| Levels tested | Memory and reproduction | Four-layer coverage: knowledge, reasoning, construction, originality |
| Metrics | Single accuracy score | Accuracy + pass rate + stability (variance across multiple runs) |
| Feedback | Only right/wrong | Localizable error information that supports iterative correction |
6. Conclusion
TCS itself is a “verifiable” field: whether its propositions are right or wrong is determined by logic, not by authority. For AI, this means it can be tested at research level in a nearly objective way for the first time—something valuable for the entire AI community. When models collectively halt before open conjectures, what we get is not a verdict of “AI is incompetent,” but a clear capability boundary: models excel at operating efficiently within a given framework, while posing questions and finding direction remain the most irreplaceable work of human researchers. For engineering teams, incorporating automatic verification into the development workflow—letting models do their best work where they are reliable—is the most pragmatic approach.
