How to Measure the Research Ability of Large Language Models: Theoretical Computer Science Offers an Answer
Benchmarks are flooding with record-breaking scores, but do they really show whether large language models can do research? This article explores why theoretical computer science (TCS) is an ideal testing ground for evaluating AI research capability, how a 100-question evaluation framework covers the full research workflow, what the results reveal about current models, and how enterprises can apply the "open problem + automatic verification" methodology to build reliable AI assessments.
From “Solving Problems” to “Doing Research”: The Dilemma of LLM Evaluation
In recent years, large language models have refreshed their performance metrics every few months, and leaderboard rankings have become dizzying. But one problem is hard to ignore: these benchmarks mostly measure a model’s ability to memorize and reuse known question types and solution patterns, rather than its ability to explore and reason about open, unknown problems. Simply put, answering exam questions is like cooking from a recipe—the steps are explicit and the grading criteria are fixed—while scientific research means trying new recipes with no template, where even success itself is uncertain.
This is especially true for fields like mathematics and theoretical computer science, which rely on rigorous proofs. When a model claims to have “solved an open conjecture,” verifying whether the answer is correct may take human experts months or even years. This “verification difficulty” directly limits the trustworthiness of AI as a research assistant. For this reason, designing an evaluation mechanism that both mirrors the real research process and allows machines to automatically judge correctness has become a key challenge in AI evaluation.
Theoretical Computer Science: A Natural “Automatically Gradeable” Testing Ground
Theoretical computer science (TCS) studies the mathematical foundations of computation itself, covering core areas such as algorithmic complexity, computability, information theory, and combinatorial optimization. It does not focus on concrete code implementation or hardware tuning, but asks fundamental questions like “how fast can the shortest path from A to B possibly be computed?” and “are there problems that no algorithm can ever solve?”
A key property of TCS is that nearly all conclusions can be expressed as formal proofs, and the correctness of a proof can be checked automatically by dedicated verification programs. It is like solving a Sudoku: the process may be hard, but once finished, a machine can instantly verify the answer. This makes TCS an ideal touchstone for testing a model’s research ability: problems can be designed as unsolved open questions or challenging variations, while grading can be entirely delegated to formal verification tools, eliminating subjective human misjudgment.
Evaluation Design: Four Task Types Covering the Full Research Workflow
A recent evaluation paper from a research team follows exactly this approach. The team built a set of 100 questions spanning four core areas of TCS, each representing a typical part of a theoretical computer scientist’s daily work:
1. Algorithm Design and Complexity Analysis
These questions require the model to design an efficient algorithm for a given problem, or to prove that an algorithm has already achieved optimal complexity. For example, given a graph-theoretic constraint, the model must determine whether a linear-time algorithm exists. Such tasks test the model’s depth of understanding of classic algorithmic paradigms—divide and conquer, dynamic programming, greedy approaches—and its ability to combine them creatively.
2. Formal Proofs and Counterexample Construction
The model must construct a rigorous proof of a theorem within a given axiom system, or build a counterexample to refute a false proposition. The difficulty here is that the model must plan the proof path on its own, with every derivation step strictly following logical rules. Machine verification checks the validity of each step, leaving no room for “semantically vague” shortcuts.
3. Complexity Class Reductions and Undecidability
These questions involve reduction techniques—transforming a problem of unknown difficulty into one of known difficulty to prove it belongs to a certain complexity class or is undecidable. The model must understand the intrinsic relationships between complexity classes such as P, NP, and PSPACE, and construct appropriate reduction mappings.
4. Open Problem Exploration and Conjecture Testing
The set includes currently unsolved open problems or slightly modified versions, testing whether the model can propose plausible proof ideas, produce partial results, or lay out a structured research plan. Even without a complete solution, a model can earn credit for rigorous reasoning and correct intermediate conclusions—much closer to the exploratory nature of real research.
Results and Deeper Insights
The experiments showed that on open conjectures that remain unsolved to this day, no large model could independently produce a complete proof. This is unsurprising: current models are essentially probabilistic prediction systems trained on massive text corpora. Their strength lies in pattern recognition and knowledge recombination, whereas genuine mathematical creation requires abstract reasoning that crosses the semantic gap—a known weakness of existing architectures.
Still, the evaluation offered some encouraging signals. On algorithm design questions, models showed solid “pattern assembly” ability, combining known algorithmic modules to generate workable solutions. In formal proving, some models produced proof drafts with correct structure but flawed details, which—after fine-tuning—could become useful human assistants. The takeaway: rather than expecting large models to deliver final breakthroughs on their own, it makes more sense to position them as “research assistants” responsible for tasks like literature screening, preliminary counterexample testing, and filling in proof steps.
Building a More Reliable Evaluation System for AI Research Ability
The significance of this study goes beyond a single test—it proposes a reusable evaluation framework built on these core principles:
- Problems with both “open” and “verifiable” properties: Questions are either unsolved hard problems or structural variants of classic problems, but all conclusions must be machine-provable or machine-refutable.
- Distinguishing “memorization” from “reasoning”: By using question formulations that rarely appear in training data, the framework forces models to rely on reasoning rather than retrieval.
- Layered scoring: Partial derivations, wrong branches, and valid ideas receive different weights, rather than binary right-or-wrong judgments.
This framework extends naturally to other branches of mathematics. Many propositions in algebraic geometry or number theory, for instance, can already be verified by automated proof assistants such as Coq and Lean. In the future, it could grow into a large-scale, cross-disciplinary research capability benchmark, providing a trustworthy measure of AI systems’ real utility in scientific discovery.
Implications for Enterprise AI Adoption
For enterprise users, understanding this evaluation approach helps set realistic expectations for AI capabilities. When selecting models, teams should not focus only on benchmark scores in general Q&A or code generation; they should also examine a model’s reasoning depth, error rates, and explainability in specific professional domains. For industries that demand rigorous logic—such as financial risk control, intelligent operations, and scientific computing—introducing “automatically verifiable” evaluation schemes can help identify models with genuine logical reasoning ability, rather than parrots that merely recite memorized answers.
Developers can also borrow the design logic of TCS exam questions to build proprietary “professional capability test sets” for their internal AI systems. For example, a code review model could be tested on code segments containing deep logical traps, with static analysis tools automatically judging whether the review comments are correct; a legal document model could be tested on cases with contradictory clauses, with a rules engine verifying whether its judgments are consistent. This “specialized questions + automatic verification” model is a key means of ensuring AI deploys reliably in serious business scenarios.
Conclusion
The research capability of large language models has not yet reached its “singularity,” but scientific evaluation methods are making the boundaries of that capability clear. With its unique rigor and computability, theoretical computer science holds up a sharp mirror to AI’s research ability. Future breakthroughs may come not simply from scaling up model parameters, but from the evolution of evaluation systems—once machines can automatically verify complex proofs, we can genuinely trust every step AI takes in exploring the unknown. At that point, mathematicians may no longer lose sleep over whether “AI answers are reliable,” because verification will already be the first line of automated defense.
