Evaluating LLMs on Theoretical Computer Science Research: TCSExam and Its Implications

    A new evaluation, TCSExam, examines how far current large language models can go on real theoretical computer science research tasks. It uses 100 problems across four task types—proof reconstruction, open-conjecture exploration, constructive tasks, and analysis/judgment—to combine research-like difficulty with machine-checkable scoring. The results show strong performance on known problems but no tested model independently solving open conjectures, pointing to a near-term role as research assistants and to the need for process-oriented evaluation and targeted training.

    Introduction: When Benchmark Scores Meet the Question of Research Capability

    In recent years, benchmark scores for large language models have been refreshed almost every month or two, and leaderboards have become increasingly crowded. Yet a sharper question is now facing researchers: what do these scores actually demonstrate?

    Most mainstream evaluations essentially test “problem-solving ability”: the problem has a standard answer, and the solution path is relatively fixed. Real scientific research is entirely different. Research has no prescribed steps, no one knows in advance whether it will succeed, and for many questions even the person posing the problem does not know the answer. Moreover, determining whether a research result holds often requires peer experts to spend weeks or even months on rigorous verification.

    Against this backdrop, an evaluation involving a Turing Award winner and frontline large-model entrepreneurs attracted industry attention. The research team comprised five researchers from an industry LLM R&D organization, an interdisciplinary information research institute at a top university, and a new basic research institution. They released an evaluation called “TCSExam,” which attempts to answer a key question:

    If real research tasks were given to the strongest current AI models, how far could they actually go?

    Why Theoretical Computer Science?

    Machine Verifiability Is the Core Prerequisite

    The biggest obstacle in designing this kind of evaluation is the grading problem. When a model claims to have proved a conjecture that has remained open for decades, who confirms that it got it right?

    Theoretical Computer Science (TCS) happens to be an exception to this difficulty. TCS is an intersection of mathematics and computer science, and its core methodology is proof: how fast a problem can be solved computationally, whether there are inherent difficulty gaps between classes of problems, and which computational goals are impossible to achieve. Most of these conclusions can be formally verified—either through strict, machine-checkable derivation chains or through executable constructions and tests.

    This creates an ideal evaluation loop: questions can be close enough to real research, while scoring can remain objective and uncontroversial.

    An Analogy: Cooking and Road Building

    An analogy can help explain TCS’s place in the wider computing world. If programmers are like drivers who care about engine performance and interior experience, then TCS studies “traffic itself”: the speed limit from point A to point B, and whether there are roads that cannot be taken no matter what. All questions revolve around the fundamental concept of “computation.” This high level of abstraction makes TCS a touchstone for testing a model’s abstract reasoning and rigorous proof abilities.

    Evaluation Design: Four Research Task Types, One Hundred Problems

    The exam contains 100 problems covering four typical types of work that theoretical computer scientists do. The classification itself reflects an important idea: research capability is multidimensional, and a single question type cannot capture the whole picture.

    1. Proof and Restatement of Known Results

    These problems test a model’s understanding and reconstruction of classical theorems: given a core proposition, can it provide a logically rigorous and complete proof? This tests not only whether the model “knows the conclusion,” but also whether it can string the reasoning chain together rigorously—which is a basic research skill.

    2. Exploration and Attempts on Open Conjectures

    This is the most difficult category and the closest to real research: when facing open problems that remain unresolved, can the model propose meaningful ideas, construct promising intermediate lemmas, or even give partial results?

    This is also the most sobering part of the evaluation conclusions: no tested model could independently solve these open conjectures. Amid the public enthusiasm that “AI is about to conquer mathematics,” this result provides an important corrective.

    The timing of this conclusion was notable. At the time, arguments such as “AI will make mathematicians unemployed” were trending in social media discussions. In fact, mathematics has become one of the most visible showcases for AI partly because verification is convenient—like Sudoku: filling it in is hard, but checking whether it is correct is easy. As a result, the field is prone to seemingly impressive results. But the TCSExam results show that where genuine original breakthroughs are required, there is still a fundamental gap between current models and mature researchers.

    3. Constructive Tasks

    Much of the output in TCS is constructive: designing an algorithm, constructing a counterexample, or giving a complexity lower bound that satisfies specific properties. These problems directly test a model’s ability to create mathematical objects “from nothing,” and they reflect research potential better than multiple-choice or true/false questions.

    4. Analysis and Judgment

    This includes complexity analysis, judgment of reduction relationships, property derivation, and similar tasks. These tasks require the model to maintain logical rigor across multi-step reasoning; if any link fails, the conclusion collapses. They therefore place high demands on the stability of long-chain reasoning.

    Why Is Such an Exam Needed?

    Leaderboard Inflation and the Gap With Research Capability

    Current LLM evaluation shows obvious “inflation”: models are optimized against public test sets, scores keep rising, but these scores reflect “exam-taking ability” rather than “research level.” Real research means facing problems without standard answers, accepting that failure is normal, and taking full responsibility for the correctness of results.

    The Essential Difference Between Problem Solving and Research

    Problem solving is essentially “cooking from a recipe”: the steps are ready-made, and taste has a standard. Research is exploration in the face of the unknown; one may not even know whether “the problem has a solution.” Using the former to infer the latter is like using a driving-test score to predict whether someone can design a car—there is a fundamental gap between the two.

    The contribution of TCSExam is that it found a domain where “research” and “gradability” are compatible, thereby systematically quantifying, for the first time, the baseline level of model performance on real research tasks.

    Deeper Implications of the Evaluation Conclusions

    For AI Capability Claims: Return to Rationality

    The results clearly draw a boundary: the strongest current models perform impressively on known problems with mature methodologies, but remain powerless before open conjectures. This reminds the industry that “AI replacing top researchers” is unrealistic in the near term. A more reasonable positioning is research assistant: taking on supporting work such as literature review, intermediate calculations, and preliminary constructions.

    For Evaluation Methodology: From “Correct Answer” to “Correct Process”

    Traditional evaluation looks only at the final answer, while the core of research capability lies in the reasoning process. The unique verifiability of TCS suggests that the key to building higher-quality evaluations is not to add more questions, but to choose domains whose conclusions can be strictly verified, let models output complete reasoning chains, and subject them to formal checks. This approach also applies to domains with deterministic evaluation standards, such as code generation and formal verification.

    For Model Iteration: Research Capability Requires Targeted Training

    The shortcomings exposed by the evaluation suggest that improving research capability may not emerge naturally from scaling general-purpose corpora alone. It may require targeted training paradigms—for example, strengthening formal proof ability, introducing an “explore–verify–reflect” loop, and injecting research trajectory data on open problems into training.

    Conclusion

    The value of TCSExam is not in creating another ranking, but in providing a new measurement framework: it tells us that beyond “exam scores,” there is a stricter yardstick—real, verifiable research capability. The distance between current models and the top of that yardstick is exactly where the field should focus next.

    For developers and enterprise users, the implications are equally direct: when choosing AI capabilities for specific business scenarios, it is important to distinguish “problem-solving tasks” from “research tasks.” Current models can already handle many of the former, while the latter still requires human-AI collaboration with humans in the lead. A rational understanding of capability boundaries is the prerequisite for realizing AI’s value.