Theoretical Computer Science Benchmarks Reveal the Boundaries of LLM Research Capability

    This article examines why theoretical computer science (TCS) offers a useful benchmark for evaluating whether large language models can do real research rather than only solve well-formed problems. It explains how TCS tasks can be designed around problem understanding, proof construction, error localization, and open-problem exploration; discusses verification-first grading, contamination control, and difficulty tiers; and summarizes the key finding that current models can assist with local reasoning and proof completion but still cannot independently resolve open conjectures. It also offers practical guidance for developers and enterprises building verifiable evaluation and collaboration workflows.

    Theoretical Computer Science Benchmarks Reveal the Boundaries of LLM Research Capability

    The Benchmark Boom: Solving Problems Is Not the Same as Doing Research

    Large language model leaderboards are refreshed constantly. Code generation, mathematical problem solving, logical reasoning, and knowledge question answering all have their own benchmarks, and scores continue to rise. Yet for people who actually build systems and make technical decisions, a more important question is emerging: how much do these scores really say about a model’s research ability?

    There is a clear gap between “solving a problem” and “doing research.” Solving a problem usually means working from a clear statement, established steps, and a standard answer. A model can score well by finding patterns close to its training distribution. Research is different. The path is often not predefined, key steps must be constructed independently, and it may be difficult to judge in the short term whether the final conclusion is correct. A model can fluently produce hundreds of pages of derivation, but whether those pages contain a valid proof or only language that “looks reasonable” requires strict checking.

    This is the central difficulty of research-oriented evaluation. Traditional benchmarks can be graded automatically through multiple-choice questions, fill-in-the-blank items, or unit tests. Research tasks often involve long chains of argument, definition construction, counterexample analysis, and exploration of open problems. Without a reliable grading mechanism, the more “proofs” a model generates, the higher the human review cost becomes, and the less credible the evaluation conclusions are.

    A more reasonable approach is therefore to choose research areas whose conclusions can be verified by machines and to build evaluation sets that approximate real research activity while still allowing automatic or semi-automatic grading. Theoretical computer science (TCS) has exactly this property. TCS focuses on computation itself: problem solvability, computational complexity, algorithm lower bounds, proofs, and constructions. Many TCS results are presented as theorems and proofs, and proof correctness can be confirmed through formal verifiers or rigorous semi-formal checks. This provides a relatively objective testbed for evaluating LLM research ability.

    Why TCS: Verifiability Is the Key to Research-Oriented Evaluation

    TCS may seem far from everyday software development, but its methodology is very pure: state a problem, give definitions, construct proofs, and check counterexamples. A programmer is more like a driver who cares about the engine, interior, and road conditions. TCS is more like transportation planning: it asks about the fastest possible route from A to B, which paths are fundamentally impossible, and under what conditions a problem becomes unsolvable. It does not depend on a specific code implementation; it depends on mathematical argument.

    This property brings two benefits.

    First, TCS tasks can be designed to feel sufficiently like research. An evaluation problem does not have to be a simple knowledge question. It can require the model to understand the problem background, choose a proof strategy, construct auxiliary definitions, complete multi-step derivations, and even determine whether a candidate proof contains a flaw. The model cannot rely only on memorized answers, because many problems require combining existing results and generating a new argument chain.

    Second, many TCS results are suitable for machine grading. For highly formalized proofs, a verifier can check whether each step follows the inference rules. For semi-formal proofs, structured answers, key lemma matching, and counterexample checks can assist scoring. Compared with open-ended natural language answers, this grading approach is more stable and easier to reproduce.

    It is important to note that verifiability does not mean ease. Writing a proof is difficult, but checking it is relatively easier, similar to Sudoku: filling the grid is hard, but checking whether the completed grid satisfies the rules is not complex. Research-oriented evaluation uses this property to separate “generating an answer” from “verifying an answer,” reducing the burden on human reviewers and improving evaluation credibility.

    Evaluation Design: Breaking Research Activity into Gradable Tasks

    From an engineering perspective, a TCS-oriented research benchmark usually needs to cover the research activity chain rather than testing only the final answer. Evaluation tasks can be abstracted into the following categories:

    1. Problem understanding and modeling: Given a theoretical problem or a piece of research background, the model must extract core definitions, identify known conditions, and point out the key difficulties. This tests whether the model can accurately understand the research context rather than paraphrase generically.

    2. Proof construction and argument completion: Given a theorem statement or a partial proof, the model must fill in key lemmas, construct counterexamples, or explain why a certain step holds. This is close to “filling gaps” in real research, but the answer can be verified through structured checks.

    3. Result verification and error localization: Given a proof that appears complete but may contain subtle errors, the model must judge its correctness and locate the problem. This is closer to peer review and collaborative research than simply generating a proof.

    4. Open-problem exploration: Around unresolved conjectures or open problems, the evaluation examines whether the model can propose valuable research directions, testable intermediate propositions, or reasonable failure boundaries. These tasks are the hardest to grade automatically and usually require human review or a combination with formal checks.

    The value of an evaluation set of roughly one hundred problems across the field lies not in the number of questions but in the diversity of task forms. It should include basic definition questions and long-chain proof questions; closed tasks with verifiable standard answers and open tasks that allow multiple routes. Scoring should not look only at the final conclusion. It should also consider proof structure, key steps, counterexample quality, and argument completeness.

    A general evaluation pipeline can be described with the following pseudocode:

    1. function evaluate(model, problem):
    2. submission = model.solve(problem.statement)
    3. if problem.has_formal_verifier:
    4. result = formal_verify(problem.verifier, submission.proof)
    5. else if problem.has_structured_answer:
    6. result = check_structured_answer(problem.rubric, submission)
    7. else:
    8. result = human_review(problem.rubric, submission)
    9. return aggregate_score(result, problem.difficulty, problem.weight)

    The key to this pipeline is not any specific tool. It is the design principle of “verification first”: verify by machine wherever possible, and use structured rubrics plus human review as a fallback where machine verification is not possible. For enterprise R&D teams, the same idea applies to internal model evaluation: first define verifiable output structures, then design scoring rules, and only then compare model scores.

    Key Finding: Open Conjectures Remain a Hard Boundary

    The conclusions from this type of evaluation are not optimistic, but they are valuable: frontier models already show usable ability on some derivation, proof completion, and error localization tasks, but when faced with open conjectures that remain unresolved, no reference model can independently produce a complete solution. In other words, models can become research assistance tools, but they cannot yet replace researchers in attacking truly open problems.

    This conclusion needs to be understood correctly. It does not mean that models “have no mathematical ability.” It means that their capability boundary is concentrated in combining existing knowledge, local reasoning, and pattern matching. Open conjectures often require new definitions, new invariants, cross-domain tools, or proof strategies that have not been seen for a long time. These are precisely the areas where current models are weakest. A model may generate many seemingly relevant ideas, but the proportion that are genuinely verifiable and capable of advancing a problem remains limited.

    This also explains why “AI automatically writing large amounts of mathematical manuscripts” can easily cause misunderstanding. The amount of generated text is not equal to the number of research conclusions, and certainly not equal to the number of correct proofs. Without strict verification, more manuscripts mean higher screening costs. The purpose of research-oriented evaluation is to separate “generation” from “verification”: models can generate boldly, but the final output must pass machine checks or expert review.

    Grading and Contamination Control: The Lifeline of Research Benchmarks

    For a research benchmark to be credible, it must address three issues: grading, leakage prevention, and difficulty stratification.

    For grading, formal verifiers should be preferred for checking formalizable proofs. For semi-formal tasks, structured rubrics should be used, with explicit dimensions such as key lemmas, counterexample conditions, and definition completeness. For open tasks, double-blind human review or multi-reviewer consistency checks should be used. Scoring should not be limited to binary correct or incorrect judgments. It should record fine-grained signals such as partial correctness, missing key steps, and argument jumps.

    For leakage prevention, TCS problems may come from public papers or classic textbooks, and model training data may already contain related conclusions. Evaluation sets need variant problems, rewritten problems, and combined problems to prevent models from directly retrieving memorized answers. For open problems, it is important to distinguish “restating known progress” from “proposing verifiable new steps.” Only the latter should count toward research ability.

    For difficulty stratification, tasks should be divided into basic understanding, standard proof, research-level construction, and open exploration. Different difficulty levels should carry different scoring weights so that a model cannot hide weaknesses on research-level tasks behind high scores on easy questions. Enterprises building internal evaluations should follow the same principle: do not use a single total score to cover all scenarios. Instead, output a capability profile by task type.

    Practical Lessons for Developers and Enterprises

    First, do not treat public leaderboards as the direct basis for model selection. Leaderboard scores can reflect relative performance on certain tasks, but they cannot directly prove that a model can handle research, architecture design, or complex defect localization. When selecting models, build a task set close to your own business and prioritize verifiable output forms.

    Second, establish a “generate, verify, feed back” loop. Let the model generate candidate solutions, proofs, tests, or patches, and then screen them with automatic verifiers, unit tests, static checks, or human review. The value of the model is not that it gives the correct answer in one pass. It is that it lowers the cost of generating candidate solutions while keeping verification cost within an acceptable range.

    Third, value process scoring rather than looking only at the final answer. For complex R&D tasks, the final result may be accidentally correct, but the process may not be reproducible. Evaluation should record intermediate steps, cited evidence, failure reasons, and verifiable evidence to form an auditable capability record.

    Fourth, control data contamination and evaluation obsolescence. Models iterate quickly, and evaluation sets also need regular updates. Variant problems, private task sets, and dynamic scoring criteria can reduce memorization effects. For research-oriented tasks in particular, it is essential to distinguish “knowing the conclusion” from “being able to construct a proof.”

    Limitations and Future Directions

    The advantage of TCS benchmarks is verifiability, but this also limits their generalization. TCS tasks are highly formalized, and proofs can be checked by machines. Software engineering, product design, and business analysis often have no single answer and higher verification costs. Therefore, conclusions from TCS evaluation cannot simply be extrapolated to all R&D scenarios. Still, it provides a methodology: first find verifiable subproblems, then gradually expand toward more open tasks.

    Future research-oriented benchmarks may evolve in three directions. First, combine formal and semi-formal methods so that more proofs can be checked automatically. Second, introduce multi-turn research interaction to examine how models perform in questioning, rebuttal, and correction. Third, build dynamic open-problem banks to reduce leakage risk and track changes in model boundaries.

    Conclusion

    The core contribution of a research-oriented benchmark for theoretical computer science is not another leaderboard. It is a clearer redefinition of the question: can large language models do research, in which parts of the research process can they contribute, and which boundaries remain uncrossed? The evidence shows that models can assist with derivation, complete proofs, and locate errors, but open conjectures remain a hard boundary. For developers and enterprises, the practical path is not to rely on benchmark scores but to build verification-first evaluation and collaboration workflows, allowing models to create value inside checkable loops.