Theoretical Computer Science Benchmark: Revealing the Research Boundaries of Large Language Models
A recent preprint paper by a joint academic and industry team shifts LLM evaluation from "answering questions" to "conducting research" by introducing a benchmark for Theoretical Computer Science (TCS). Using 100 questions, the benchmark assesses frontier models on real research activities. The findings are sobering: while models demonstrate some reasoning and generation capabilities on auto-verifiable tasks, none can independently solve unresolved open conjectures. This result highlights the need to move LLM evaluation away from leaderboard competitions and towards the verifiable boundaries of research capabilities.
A recent preprint paper by a joint academic and industry team shifts the evaluation focus from “whether models can solve problems” to “whether models can conduct research.” The work constructs an evaluation benchmark covering the entire field of Theoretical Computer Science (TCS), using 100 questions to assess the performance of frontier large language models in real research activities. The paper reaches a sobering conclusion: while models have demonstrated certain reasoning and generation capabilities on automatically verifiable tasks, none of the models in the reference set can independently provide credible answers to unresolved open conjectures. This result is not surprising but highly important, as it pulls LLM evaluation back from leaderboard competitions to the verifiable boundaries of research capability.
1. Why General Leaderboards Fail to Measure Research Capability
LLM benchmarks update almost every two months, covering scenarios like multiple-choice, QA, coding, and math problems. The issue is that most leaderboards prove that “models can solve problems” rather than “models can do research.” Solving problems is like cooking from a recipe: steps are relatively fixed, evaluation criteria are clear, and input/output boundaries are well-defined. Research, however, has no ready-made recipe or standard answer; even the proposers of many problems do not know where the final proof will emerge from.
Grading is even more troublesome. A model can generate hundreds of pages of “proofs” at once, making it impossible for human reviewers to verify page by page. A model can also claim to have solved a years-long conjecture, but without formal checks or rigorous peer review, such claims have little engineering value. Previously, institutions have published hundreds of AI-generated math manuscripts, sparking discussions on social media about whether “AI is revolutionizing mathematical research.” Despite the high buzz, the core question remains: which conclusions in these manuscripts can be reliably verified by machines or humans?
TCS offers a breakthrough. It studies “computation” itself, focusing on fundamental issues like computability, complexity, algorithmic lower bounds, and proof complexity. Conclusions are usually presented as definitions, theorems, and proofs. Compared to long natural language texts, formal proofs are more suitable for verification by automated proof checkers. In other words, TCS tasks are more like “Sudoku”: filling it out is hard, but whether it is correct can be checked against the rules. Because of this, it serves as an excellent testing ground for research capability evaluation.
However, verifiability does not equal research value. If a benchmark only tests questions with existing standard answers, models might score high through memorization or pattern matching; if it only tests open conjectures, auto-grading becomes difficult. Therefore, evaluation design must strike a balance between “real research distribution” and “machine-gradable.”
2. Why TCS Serves as an Ideal Touchstone for Research Capability
TCS is not a discipline about fixing computers or writing business code. Engineering implementation focuses on how systems are built, whereas TCS focuses on the limits of computational models: how fast one can get from point A to point B, which paths are inherently dead ends, whether certain problems have polynomial-time algorithms, and whether proofs themselves can be efficiently checked. It resides at the intersection of mathematics and computer science, relying primarily on definitions, constructions, reductions, and proofs.
This disciplinary characteristic brings two evaluation advantages. First, many conclusions can be formally expressed, allowing their correctness to be automatically verified by checkers, thereby reducing manual review costs. Second, research activities can be decomposed into multiple observable capabilities: whether it can accurately understand definitions, construct counterexamples, perform reductions, discover proof gaps, and adjust strategies after failure. Compared to simple answer matching, these signals are closer to the actual research process.
Of course, not all TCS tasks can be auto-graded. The “value judgment” of open conjectures, the simplicity of proof ideas, and the interestingness of research directions still require human review. Therefore, a reasonable approach is not to claim that the benchmark can completely replace mathematicians, but to divide the evaluation into two tiers: one for machine-verifiable correctness checks, and the other for sampled research quality assessments. The former provides scaled signals, while the latter offers directional judgments.
3. Benchmark Design: 100 Questions, Four Activities, and an Auto-Grading Pipeline
The benchmark consists of 100 questions, categorized into four types based on the typical research activities of theoretical computer scientists. From a research process perspective, these activities usually cover formal definitions, constructive results, proof checking, and open problem exploration. The key to question design is not to pile up difficult problems, but to ensure that each question produces a checkable artifact: whether the definition is self-consistent, whether the construction meets constraints, whether the proof passes the checker, and whether the counterexample actually disproves the proposition.
An engineering evaluation pipeline can be abstracted as follows:
def evaluate(model, problem):draft = model.generate(problem.statement,budget=problem.token_budget,tools=problem.allowed_tools)artifact = normalize(draft)if problem.verification == "formal":result = proof_checker.verify(artifact, problem.spec)elif problem.verification == "constructive":result = constraint_checker.check(artifact, problem.constraints)else:result = rubric_review(artifact, problem.rubric, sample_reviewers=3)return {"problem_id": problem.id,"verified": result.passed,"evidence": result.log,"cost": draft.usage}
This pseudocode highlights three principles. First, the problem statement must include verifiable specifications, not just a natural language prompt. Second, the model’s output must be normalized into verifiable artifacts, such as formal proof scripts, constructed instances, or counterexamples. Third, all inspection processes must retain logs for reproducibility and auditing. For open-ended questions, a combination of small-sample human review and scoring rubrics is used to avoid mistaking “text that looks like a proof” for an actual proof.
The benchmark also requires anti-contamination measures. Specific actions include using private question sets and variants, dynamically generating parameterized instances, restricting the model’s access to external retrieval tools, logging whether the model attempts to guess the checker rules, and cross-validating different phrasings of the same concept. Otherwise, models might achieve artificially high scores by memorizing public answers.
4. Interpreting Results: Unsolved Open Conjectures Do Not Mean AI is Useless
The most discussed conclusion from the paper is that reference models cannot independently crack open conjectures. This conclusion needs accurate interpretation. It shows that current models still have clear boundaries in long-range logical reasoning, definition construction, counterexample search, and proof strategy selection; however, it does not mean models lack auxiliary value. On the contrary, in verifiable subtasks, models can help researchers generate candidate lemmas, check proof gaps, enumerate small-scale counterexamples, and organize known results. These tasks do not equate to “solving conjectures” but can reduce mechanical costs in research.
For developers, a more important takeaway is the shift in evaluation perspective: do not just look at the model’s accuracy on standard questions, but focus on its success rate, failure modes, and costs on “verifiable research tasks.” A model that can iteratively correct itself based on proof checker feedback may hold engineering value even if its initial pass rate is low; a model that only generates long, unverifiable texts is unsuitable for the research assistance pipeline.
5. Recommendations for Evaluation Platforms and Engineering Implementation
Building such an evaluation system requires unified management of problem statements, model outputs, checker logs, and human review records. General cloud platforms can provide object storage to save question sets and proof artifacts, container platforms to orchestrate evaluation tasks, and logging and monitoring services to record the entire process. The key is not relying on a specific proprietary interface, but ensuring that the evaluation protocol is reproducible, checkers are replaceable, and results are auditable.
In practice, four guidelines can be followed: first, prioritize auto-verifiable tasks before gradually introducing human review; second, establish difficulty tiers to distinguish between “reproducing solved problems,” “solving variant problems,” and “exploring open problems”; third, require models to output evidence chains, prohibiting bare conclusions; fourth, include failure cases in the dataset to analyze whether the model failed at definition understanding, construction search, or proof checking.
Overall, the value of this benchmark lies not in sentencing LLMs or awarding them trophies, but in providing an evaluation method closer to real research. It reminds the industry that the reason mathematics and TCS are suitable for evaluating AI is not because the problems are easy, but because correctness can be strictly verified. The fact that open conjectures remain unsolved by models precisely illustrates that research capability evaluation should move towards a verifiable, reproducible, and auditable engineering system, rather than stopping at leaderboard scores and demo videos.
