How Theoretical Computer Science Benchmarks Assess LLM Research Capabilities

    A recent preprint introduces a 100-task theoretical computer science benchmark for evaluating frontier LLMs across four research activity types. The article explains why TCS is a useful testbed for research capability, how the task categories map to real research actions, why open conjectures remain unsolved by reference models, and what these findings imply for benchmark design, contamination control, process verification, and engineering evaluation pipelines.

    I. The Evaluation Mismatch Behind Benchmark Growth

    Public evaluations of frontier LLMs refresh almost every two months. Leaderboard scores keep rising, and task coverage keeps broadening, but a key question remains: to what extent do these scores actually reflect a model’s research capability?

    “Solving exercises” and “doing research” are not the same thing. Solving an exercise is more like cooking from a recipe: the steps are already there, the taste has a relatively clear standard, and the evaluator only needs to check whether the final dish is close to what was expected. Research is different. Problems often have no ready-made route, and at the beginning it may not even be clear what counts as success. Researchers must repeatedly probe across definitions, conjectures, proofs, counterexamples, reductions, and verification, and many intermediate conclusions do not directly produce the final answer.

    This creates an evaluation problem: the closer a task is to real research, the harder it is to grade automatically; the easier it is to grade, the more likely it is to collapse into memorization, template matching, or short-range reasoning. Theoretical computer science (TCS) offers a special entry point. It sits at the intersection of mathematics and computer science, and its core object is computation itself: how many resources are needed to solve a problem, which problems are provably impossible to solve efficiently under a given model, and how reductions establish complexity relationships between different problems. TCS research relies mainly on proofs, and many conclusions can be machine-checked, making it more suitable than general open-ended research tasks for building verifiable, comparable benchmarks.

    A recent preprint study follows this line of thinking. The research team designed a 100-problem theoretical computer science evaluation set, divided tasks into four categories, and used them to examine how frontier LLMs perform across complete research activities. Its conclusion is not optimistic: within the scope of this evaluation, none of the reference models could independently solve the open-conjecture tasks that remain unresolved. The value of this conclusion is not to pour cold water on models, but to remind us that existing leaderboards may overestimate a model’s ability to advance research.

    II. Why Use Theoretical Computer Science as a Touchstone for Research Capability?

    There are at least three reasons for choosing TCS as an evaluation domain.

    First, TCS problem structures are close to mathematical research, but verification costs are relatively controllable. A complexity lower-bound proof, a counterexample construction, or a reduction process can often be checked at key steps in a formal or semi-formal way. Compared with open-ended natural-language question answering, TCS makes it easier to establish an objective boundary for answer correctness.

    Second, TCS covers both known results and open problems. If a benchmark tests only known theorems, a model may score highly through memorizing the literature; if it tests only open problems, there is no standard answer. A reasonable approach is to layer the tasks: include both machine-verifiable proof construction and open-problem analysis that requires process evaluation. This helps distinguish whether a model is restating knowledge or organizing a research route.

    Third, TCS can expose weaknesses in long-range reasoning and self-verification. Real research is not a one-shot generation of an answer. It involves proposing hypotheses, searching for counterexamples, revising proofs, checking boundary conditions, and assessing whether a reduction preserves parameters. If a model can only produce plausible text over short chains but cannot close the loop in a proof checker, it is hard to say it has research capability.

    III. Core Principles of Benchmark Design: From Answer Matching to Verifiable Research Processes

    To make evaluation closer to real research, benchmark design needs to follow several principles.

    1. Layer tasks instead of stacking difficulty

    Research activity can at least be broken into understanding a problem, constructing proofs, finding counterexamples, establishing reductions, and analyzing open problems. The value of four task categories is that they cover different research actions, not simply that they arrange problems from easy to hard. A model may be good at restating definitions but fail when constructing a counterexample; it may imitate a proof framework but fail to handle boundary conditions. Layered evaluation can provide diagnostic information, not just a total score.

    2. Prioritize machine-verifiable loops

    The advantage of TCS is that many conclusions are verifiable. A benchmark should convert the final answer into checkable objects wherever possible: whether proof steps satisfy checker rules, whether a counterexample truly violates the proposition, whether a reduction preserves parameter relationships, and whether complexity analysis is self-consistent. For open-problem analysis that cannot be fully verified automatically, process-based scoring should be used: whether the model proposes testable hypotheses, gives failure paths, identifies known obstacles, and proposes next verification steps.

    3. Prevent contamination and templating

    Once a public benchmark is absorbed into training data, scores become distorted. It is therefore necessary to retain unpublished problems, variant problems, and dynamically generated equivalent problems, and to report contamination risk. At the same time, scoring cannot look only at final conclusions; it must also check whether intermediate steps are reproducible. Otherwise, a model may learn templates that “look like proofs” without actually completing a proof.

    4. Report capability boundaries, not just rankings

    A responsible evaluation should clearly state which tasks are machine-verifiable and which require expert review; how consistent scoring is for open problems; and whether model failures come from missing knowledge, broken reasoning, or insufficient verification capability. Only by classifying failure modes can a leaderboard have engineering and research value.

    IV. What Research Actions Do the 100 Tasks in Four Categories Map To?

    Although the specific problems should not be reduced to fixed templates, from the perspective of research activity the four task categories can be understood as an abstract mapping of the daily work of theoretical computer scientists:

    Research action Evaluation focus Verifiable signal
    Problem understanding and definition clarification Whether the model can identify the computational model, resource constraints, and proposition boundaries Whether definitions are self-consistent and assumptions are not omitted
    Proof construction and step organization Whether the model can advance from known lemmas to the target conclusion Whether the proof checker passes and key lemmas hold
    Counterexample and reduction design Whether the model can construct a counterexample or establish relationships between problems Whether the counterexample is valid and the reduction preserves parameters
    Open-problem analysis and route proposal Whether the model can identify obstacles and propose testable paths Process scoring, expert review, and follow-up verifiable subproblems

    These four task categories point to one goal: do not let the model only answer “what it is”; require it to show “how it was obtained” and “how it can be checked.” This also explains why open-conjecture tasks become a key observation point. Open conjectures have no ready-made answer, so a model cannot hit them directly through memory or templates; it must propose testable intermediate propositions, identify known obstacles, and give an advancement route that can be verified later. The study observed that no reference model could independently solve such tasks, indicating that current models still have clear bottlenecks in long-range exploration, hypothesis screening, and self-verification.

    V. How to Interpret “Open Conjectures Were Not Independently Solved”

    This conclusion should not be simply understood as “models have no value for TCS.” A more accurate interpretation is that in research stages requiring long-term exploration, repeated falsification, and strict verification, current models still struggle to independently carry the mainline advancement task.

    It indicates at least three things. First, models may be good at explaining known concepts and reproducing common proof patterns, but they lack stable exploration strategies when facing unknown problems. Second, the “reasonableness” of model-generated content does not equal “verifiability”; without a checker loop, fluent proof text may contain hidden gaps. Third, research capability evaluation must focus on process metrics, such as the quality of proposed subproblems, counterexample search coverage, number of proof revisions, and verification pass rate, rather than only whether the final answer resembles a standard answer.

    The implication for evaluation practice is that open problems should not be simplified into “ask the model to write an analysis.” Instead, open problems should be broken into verifiable subtasks. For example, require the model to first give a formal definition, then list known obstacles, then propose testable lemmas, and finally explain how to fall back if a lemma fails. This preserves the complexity of open research while providing relatively objective scoring signals.

    VI. An Engineering Evaluation Pipeline

    When enterprises or teams reproduce this kind of evaluation, the focus is not on chasing a single score, but on building a reproducible, auditable pipeline. General cloud infrastructure can provide container scheduling, object storage, logging, and monitoring and alerting to support task distribution, artifact archiving, and process tracking. Specific choices should center on reproducibility and cost control rather than binding to particular interfaces.

    Below is a pseudocode sketch unrelated to any specific product:

    1. task := {
    2. id: string,
    3. category: research_activity_type,
    4. statement: string,
    5. answer_type: proof | counterexample | reduction | open_analysis,
    6. verifier: machine_checkable | expert_review
    7. }
    8. for each task in benchmark:
    9. draft := model.generate(task.statement)
    10. trace := model.export_reasoning_trace()
    11. if task.verifier == machine_checkable:
    12. verdict := run_checker(task, draft)
    13. else:
    14. verdict := expert_review(task, draft, trace)
    15. record(task.id, verdict, trace, checker_log)
    16. report:
    17. score_by_category
    18. verification_pass_rate
    19. failure_mode_distribution
    20. contamination_risk
    21. reproducibility_notes

    The pipeline should especially record failure modes: whether the model misunderstood definitions, had broken proof steps, produced an invalid counterexample, or used mismatched reduction parameters. Only when failure modes are captured as analyzable data can a benchmark guide model improvement rather than create a new leaderboard target.

    VII. Implications for R&D and Evaluation Practice

    First, when building domain benchmarks, prioritize tasks with strong verifiable signals while retaining open tasks as observations of the capability ceiling. Second, evaluation reports should distinguish memory-based scores from reasoning-based scores, avoiding the use of known-conclusion tasks to mask weaknesses on open problems. Third, model evaluation should introduce process tracing and verifier loops, encouraging models to produce checkable intermediate artifacts. Fourth, public leaderboards need contamination detection and dynamic task sets; otherwise, high scores will quickly lose explanatory power. Fifth, teams should turn evaluation results into error taxonomies and improvements to training and prompting strategies, rather than focusing only on rankings.

    The point of theoretical computer science benchmarks is not to prove that models “work” or “do not work,” but to break research capability into observable, verifiable, and reproducible stages. The fact that open conjectures remain independently unsolved indicates where next investment is worthwhile: long-range hypothesis management, counterexample-driven search, proof planning, and self-verification. For developers, this is more informative than an inflated benchmark score.