How Theoretical Computer Science Benchmarks Evaluate Large Language Model Research能力
Traditional benchmarks measure whether models can solve well-defined problems, but research requires choosing paths, handling uncertainty, and producing verifiable new results. A recent 100-task benchmark for theoretical computer science evaluates these abilities through machine-checkable research activities and finds that no evaluated model independently solved an open conjecture. The benchmark highlights both the value of TCS as a testbed and the need for stronger leakage controls, verifiable grading, failure analysis, and more precise descriptions of model capabilities.
Large language model scores on public leaderboards continue to rise. Code generation, mathematical problem solving, logical reasoning, and knowledge answering all have their own benchmarks. Yet an increasingly important distinction is becoming clear: solving problems is not the same as conducting research.
Most benchmark questions have known procedures, definite answers, and predefined grading criteria. Research is different. There may be no established path to follow, and even the person who poses the question may not know the answer. Evaluating a model’s ability to participate in genuine research is therefore becoming a major challenge for the evaluation community.
Recently, researchers from industry and academia developed a benchmark focused on Theoretical Computer Science (TCS). It uses a set of machine-checkable research tasks to evaluate leading large language models. The benchmark contains 100 questions organized around four types of activity common in TCS research. One notable finding is that none of the evaluated reference models independently solved an unresolved open conjecture.
This result does not mean that models have no value in mathematics. Instead, it shows that research-oriented evaluations need more rigorous designs and that model capability boundaries must be described more precisely.
Why Traditional Leaderboards Struggle to Measure Research Ability
Most traditional benchmarks focus on problem solving. Given an input, a model produces an answer, and it receives a score when that answer matches the reference result. This approach is inexpensive, reproducible, and convenient for comparing models. However, it differs substantially from real research.
First, problem-solving procedures are often partially predetermined. The process is similar to following a recipe: the ingredients, sequence, and expected outcome are already available. Research has no fixed recipe. Researchers must decide which uncertain paths are worth exploring, which failures are acceptable, and which intermediate results are meaningful.
Second, grading research output is extremely difficult. A model can generate dozens or even hundreds of pages of proof that appear plausible but contain subtle errors. If it claims to have solved a conjecture that has remained open for years, who can verify every step? Human review alone is expensive and difficult to scale. Model-based self-evaluation introduces another risk: a model may produce a self-consistent assessment that is still factually wrong.
Third, public leaderboards are vulnerable to data contamination and overfitting. A model may have encountered similar questions during training, leading to an inflated score. Unless research benchmarks control for leakage, it becomes difficult to determine whether a model is actually reasoning or simply recalling material.
The core challenge of a research benchmark is therefore not just question design. It also involves how to grade answers, prevent leakage, and interpret results. A leaderboard that focuses only on scores cannot answer a complex question such as whether a model truly possesses research ability.
Why TCS Is a Useful Testbed for Research Evaluation
Theoretical Computer Science sits at the intersection of mathematics and computer science. It studies computation itself: under what conditions a problem is computable, how much time and space a solution requires, which lower bounds are unavoidable, and how different problems are related through reductions.
A programmer may be compared with a driver who cares about the engine, interior, and driving experience. TCS is more like transportation science: it asks how quickly someone can travel from one place to another and whether some routes are fundamentally impossible.
Many TCS results have an important property: they are relatively verifiable. In principle, the correctness of a theorem proof can be checked by a formal verifier or symbolic tool. A counterexample can be confirmed through enumeration or constructive validation. Some complexity-theoretic claims can also be checked by examining the derivation step by step. This makes TCS a relatively suitable domain for machine-graded research evaluation.
That does not make TCS evaluation easy. Proofs written in natural language still need to be converted into checkable forms, and formalization can be expensive. Some proof steps depend on domain knowledge that automated checkers may not cover. Partial progress on an open problem is also difficult to represent with a single score.
The value of a TCS benchmark is therefore not that it completely replaces expert review. Rather, it provides a scalable, reproducible, and machine-verifiable evaluation framework.
100 Tasks and Four Types of Research Activity
The benchmark contains 100 questions divided into four categories based on common activities in theoretical computer science research. The precise categories should be understood according to the benchmark paper, but at a high level, these tasks typically cover:
- Problem understanding and modeling
- Construction and counterexample exploration
- Proof construction and verification
- Complexity and lower-bound analysis
The goal is to move beyond tasks such as calculating a number or selecting an option. Models must demonstrate capabilities associated with the research process.
A simplified evaluation pipeline can be represented as follows:
for task in benchmark:prompt = build_research_prompt(task)answer = model.generate(prompt)verdict = machine_check(task, answer)record(task, answer, verdict)function machine_check(task, answer):if task.type == "counterexample":return verify_counterexample(task.statement, answer)if task.type == "proof":return formal_check(task.statement, answer)if task.type == "bounded_check":return exhaustive_check(task.statement, answer)return human_review_if_needed(task, answer)
The task metadata can be abstracted as:
{"task_id": "tcs-001","statement": "Mathematical or computational statement to be verified","task_type": "proof | counterexample | bounded_check | derivation","checker": "formal | symbolic | exhaustive | human_review","difficulty": "research_level","leakage_control": "private_holdout"}
The key principle is that the closer a task is to real research, the more difficult it becomes to grade. Research evaluations must therefore prioritize tasks whose conclusions can be verified. TCS offers a relatively controlled setting: a model can freely generate proof ideas, but the final result must pass machine checks or rigorous human review.
The Finding on Open Conjectures: Capability Boundaries Matter More Than Scores
One of the study’s most important findings is that none of the evaluated reference models independently solved an open conjecture that remains unresolved. This result needs to be interpreted carefully.
On one hand, it shows that current frontier models still face clear limitations on genuinely open research problems. Models can help organize ideas, generate candidate proofs, search for counterexamples, and identify gaps in derivations. Independently solving an open conjecture, however, requires a higher level of ability involving problem selection, long-term exploration, recovery from failed approaches, and creative breakthroughs.
On the other hand, the result does not mean that models have no research value. A more realistic role is that of a research assistant handling verifiable subproblems, such as:
- Checking a counterexample within a finite range
- Verifying algebraic steps in a proof
- Generating multiple candidate constructions
- Helping identify equivalences between definitions
Evaluations should distinguish between independent solutions, assisted discovery, intermediate progress, and complete failure. A single accuracy score cannot adequately summarize all of these capabilities.
Practical Principles for Building Research Benchmarks
Teams developing similar evaluations should consider the following principles.
1. Define the evaluation goal
Is the benchmark measuring problem-solving speed or research potential? Is it evaluating the final answer or the proof process? Different goals require fundamentally different task and grading designs.
2. Establish levels of verifiability
Tasks can be classified into several levels:
- Formally checkable
- Symbolically verifiable
- Exhaustively testable within a finite range
- Requiring expert review
The greater the proportion of machine-verifiable tasks, the easier the benchmark is to scale. However, human review should remain part of the process to avoid selecting tasks that are easy to check but have little research value.
3. Prioritize contamination controls
Time-based splits, private holdout sets, dynamic generation, deduplication, and variant detection can reduce the risk that models achieve high scores through memorization. Leakage is particularly important for open problems because relevant papers and discussions may already have appeared in training data.
4. Create difficulty tiers
A useful benchmark should progress from textbook exercises to research-level problems and then to open questions. Open problems should not be scored only as “solved” or “unsolved.” Evaluators can instead assess intermediate lemmas, counterexample construction, proof frameworks, and checkability.
5. Report failure modes
Was the model unable to understand the definitions? Did it skip essential proof steps? Was the counterexample invalid? Could it not complete the formalization? Failure analysis is often more informative than the aggregate score.
6. State conclusions cautiously
Evaluation reports should describe the task sources, grading methods, contamination controls, and statistical confidence. Results from a limited benchmark should not be exaggerated into claims that models can replace scientists or that mathematics has been solved.
Conclusion
Research-oriented evaluation in theoretical computer science provides a view of model behavior that is closer to real research activity. By taking advantage of the relative verifiability of TCS results, it transforms the question “Can a model conduct research?” into a collection of machine-checkable tasks while also exposing clear limitations on open conjectures.
For developers and enterprise readers, the central lesson is that evaluation should not focus only on leaderboard scores. It should be designed around verifiability, contamination prevention, failure analysis, and task difficulty levels.
Large language models can be powerful assistants in the research workflow. However, they remain clearly—and realistically—far from independently solving unresolved scientific problems.
