A Theoretical Computer Science Exam for LLMs: How to Evaluate AI's Research Ability
Benchmarks scores for large language models keep climbing, but can they actually do scientific research? This article examines a theoretical computer science evaluation created with input from a Turing Award winner, explaining why solving problems differs fundamentally from doing research, how the four question types in this exam probe different capability dimensions, and what its methodology and findings mean for developers and enterprises adopting AI.
A Theoretical Computer Science Exam for LLMs: How to Evaluate AI’s Research Ability
From Benchmark Mania to Sober Questions
Over the past year, large language models have刷新ed leaderboard results in waves… (processing notes: rewritten below)
Over the past year, large language models have refreshed benchmark scores almost every month or two. Math competition problems, code generation, reading comprehension—leaderboard numbers keep rising, and there has even been talk of “AI disrupting mathematical research.” Yet a recent evaluation, jointly released by a Turing Award winner and a Chinese LLM team, poured cold water on the hype: on this exam covering the full breadth of theoretical computer science, not a single participating model could independently solve an unsolved open conjecture.
This result deserves careful reflection from every developer and business decision-maker concerned with the boundaries of AI capability: solving problems and doing research are two fundamentally different abilities.
Why Existing Benchmarks Can’t Measure Research Ability
Solving Problems Is “Cooking from a Recipe”
Most mainstream benchmarks share one trait: the problems have standard answers, and the solutions follow well-established patterns. Models are essentially “cooking from a recipe”—the steps already exist, and there is a standard for the final taste. Even the hardest competition problems have solution paths that human contestants have refined over and over, and training corpora likely contain many similar patterns.
Research Has No Predetermined Steps
Genuine scientific research is entirely different:
- The path is unknown: there is no prescribed procedure, and success cannot be guaranteed in advance.
- The answer is unknown: for many open problems, even the person posing them doesn’t know the answer.
- Grading is hard: if a model claims to have cracked a decades-old conjecture, who verifies whether its write-up is correct? The industry has already seen cases of AI generating hundreds of “mathematical manuscripts,” a substantial portion of which contained proofs that didn’t hold up.
Verifiability Is the Key
There is an inherent contradiction here: the more a problem resembles real research, the harder it is to grade automatically. Theoretical computer science (TCS) is a rare exception. Sitting at the intersection of mathematics and computer science, TCS revolves entirely around “computation” itself, and its results take the form of proofs—most of which are machine-verifiable. It’s like a Sudoku puzzle: filling it in is hard, but once filled, checking correctness is trivial. This makes TCS an ideal testing ground for evaluating AI’s research ability.
How the Exam Is Designed: The Logic Behind Four Question Types
The evaluation contains roughly 100 problems, organized into four categories that mirror how theoretical computer scientists actually work, each targeting a different dimension of research capability:
Proof Problems: A Stress Test for Logical Rigor
Models must produce complete mathematical proofs. These problems test not whether the model “knows the conclusion,” but whether it can build a rigorous chain of reasoning step by step from axioms and known theorems. A single logical gap invalidates the entire proof—and this is exactly where today’s LLMs are weakest: they excel at generating text that “looks like a proof” but frequently fail on fine-grained logical consistency.
Construction Problems: From Argument to Creation
Models must construct algorithms, protocols, or combinatorial structures with specified properties. Compared with proofs, constructions add a layer of creativity: the answer is not unique, but it must satisfy all constraints. Crucially, a program can automatically verify whether a construction is valid, balancing openness with gradability.
Analysis and Counterexample Problems: Critical Thinking
Models must decide whether a given statement holds—proving it if it does, producing a counterexample if it doesn’t. These problems are particularly tricky: the model must first “commit” to a direction, then execute the corresponding strategy. In practice, LLMs often fall into traps by leaning toward answers that “look correct,” exposing a lack of genuine critical reasoning.
Open Conjecture Problems: The Ultimate Test
These are actual unsolved open problems in the field. Their purpose is not scoring but probing the ceiling of capability. The conclusion is unambiguous: none of the current frontier models made any progress on these problems. AI can serve as a research assistant—accelerating literature review, verifying intermediate lemmas, generating candidate ideas—but there remains a fundamental gap before it can achieve original breakthroughs independently.
Engineering Lessons from the Evaluation Methodology
The design of this evaluation also offers practical guidance for developers building their own model evaluation pipelines:
First, distinguish retrieval ability from generation ability. When designing evaluation sets, use newly constructed problems that don’t appear in public corpora, so models can’t score by memorization.
Second, prefer machine-verifiable task domains. When evaluating models internally, borrow the TCS approach: require that conclusions be programmatically checkable. For example:
# Sketch: an evaluation pipeline with automatic verificationdef evaluate(model, task):response = model.generate(task.prompt)# For construction answers, verify programmatically with a checkerif task.type == "construction":return task.verifier.check(response)# For proof answers, use formal tools for syntactic and logical checksif task.type == "proof":return formal_checker.validate(response)return human_review(response)
Third, replace average scores with “capability ceiling tests.” Averages hide the distribution of failure modes. Including a proportion of out-of-scope problems reveals how models behave when facing the unknown—whether they honestly admit they can’t solve it, or confidently fabricate an answer.
Practical Advice for Enterprises Adopting AI
Based on these findings, enterprises introducing LLMs should keep a clear head:
- Know the capability boundaries. LLMs excel at tasks with standard answers and established workflows—code completion, document generation, knowledge Q&A. But for tasks requiring original argumentation and rigorous logical reasoning, human review must remain in the loop.
- Build private evaluation sets. Public leaderboards can’t tell you how a model performs in your specific business context. Following the “machine-verifiable” principle, build automated evaluation pipelines based on your own business data—this is the foundation for model selection and iteration. Cloud platforms offering LLM services and compute can help you quickly set up the evaluation and application environment.
- Use human-AI collaboration, not full replacement. The evaluation shows AI works best as a research assistant—handling literature search, verifying intermediate steps, and brainstorming ideas—while final judgment and creative decisions stay with human experts.
Conclusion
The value of this theoretical computer science exam lies not in ranking models but in establishing a yardstick for “research ability.” It reminds us that score inflation in LLMs does not equal a fundamental leap in intelligence; between solving problems and doing research lies a gap that has yet to be crossed. For developers, understanding where that gap begins is both the prerequisite for rational model selection and the starting point for designing the next generation of human-AI collaborative systems. Mathematicians can breathe a little easier for now—but the exploration of AI’s capability boundaries has only just begun.
