From Standardized Benchmarks to Research Intelligence: How LLMs Are Tested Against Theoretical Computer Science

    This article explains why traditional LLM benchmarks fail to measure genuine research capability, and why theoretical computer science—with its formal definitions, decomposable reasoning, and verifiable results—has become an ideal testing ground. It outlines a four-tier evaluation framework covering concept understanding, proof reproduction, algorithm design, and open-problem judgment, discusses why models still struggle with unsolved problems, and proposes a layered automated grading design combining formal verification, programmatic testing, counterexample search, and expert review.

    From Standardized Benchmarks to Research Intelligence: How LLMs Are Tested Against Theoretical Computer Science

    In recent years, large language models have steadily improved on math QA, code generation, and standardized exams, and model leaderboards have grown increasingly sophisticated. Yet one key question remains insufficiently answered: are models merely “completing known tasks at high quality,” or have they acquired the ability to participate in frontier scientific research?

    Around this question, researchers in academia and industry have begun building systematic evaluation frameworks oriented toward theoretical computer science. The core idea is not to add yet another set of ordinary exam questions, but to decompose the tasks commonly found in theoretical research and design test samples that can be verified automatically or semi-automatically—observing whether LLMs possess the complete capability chain from understanding a problem, to proposing an approach, to producing a rigorous proof.

    1. Why Traditional Leaderboards Cannot Represent Research Capability

    LLM evaluation typically relies on multiple-choice questions, knowledge QA, mathematical computation, program generation, or code repair. These tasks share a common feature: the problem itself is already defined, the objective is relatively clear, and evaluators can usually prepare a standard answer in advance.

    This approach works well for measuring foundational capability, but it differs markedly from real research.

    In conventional problems, the model faces a pre-packaged question. The prompt tells it what the inputs and outputs are, what constraints apply, and sometimes even hints at which class of methods to use. All the model needs to do is find a feasible solution within existing knowledge and reasoning paths.

    Research tasks, by contrast, begin at a much earlier stage. A researcher must judge:

    • Whether the problem is worth studying;
    • Whether the current definition is accurate;
    • Whether existing results can be applied directly;
    • Which boundary conditions might invalidate a conclusion;
    • Whether a simpler or more general proof path exists;
    • Whether a seemingly plausible conjecture is actually false.

    In other words, ordinary problem-solving is closer to “completing a task according to given rules,” while research encompasses “defining the rules, correcting the problem, constructing methods, and validating conclusions.” High scores on standard problems do not automatically imply independent research capability.

    2. Why Theoretical Computer Science Is Well-Suited for Testing Research Ability

    Research capability is hard to evaluate largely because research results usually lack immediate, uniform criteria for correctness. A new paper may require peer review, or even years of discussion, before its conclusions are confirmed as reliable. If models are asked to answer open-ended questions directly, evaluators easily fall into the trap of “the answer looks reasonable, but we cannot confirm it is correct.”

    Theoretical computer science offers a relatively special solution.

    This field contains abundant formal definitions, logical derivations, complexity analysis, and algorithmic proofs. Many conclusions can be converted into explicit mathematical objects and verified through symbolic checking, counterexample search, proof verifiers, or programmatic tests. For example, whether an algorithm satisfies correctness requirements can be checked by examining its logical derivation over all inputs; whether a complexity upper bound holds can be audited through recurrence relations, reduction procedures, or resource counting; and whether a proposition is false can often be exposed quickly by constructing a counterexample.

    Theoretical computer science therefore offers three advantages:

    2.1 Clearly Bounded Problems

    Problems typically specify precise inputs, outputs, constraints, and objectives, minimizing disputes caused by natural-language ambiguity.

    2.2 Decomposable Reasoning

    Proofs, reductions, algorithm constructions, and complexity analyses can all be broken into steps, making it easy to pinpoint exactly where a model goes wrong.

    2.3 Relatively Verifiable Results

    Final conclusions can usually be rechecked through formal rules, automated tools, or independent programs, reducing the uncertainty of manual grading.

    Note that “verifiable” does not mean “easy.” On the contrary, the closer a problem is to the research frontier, the more likely it demands that a model simultaneously perform conceptual understanding, abstract modeling, method design, and rigorous argumentation.

    3. What Research Tasks Should a Complete Evaluation Cover?

    A valuable test of theoretical research capability should not only assess final answers—it should cover the different types of work involved in the research process. These can be divided into four major tiers.

    Tier 1: Understanding Concepts and Definitions

    The first step of theoretical research is not computation, but confirming what the problem is actually about. The model must correctly understand complexity classes, reduction relationships, randomized algorithms, approximation algorithms, graph structures, combinatorial objects, and various formal conditions.

    Such questions may look basic, but errors of “similar terms, different meanings” are extremely common. For example, a model might mistake a necessary condition for a sufficient one, misread an existential statement as a constructive one, or overlook boundary restrictions in a definition. Any deviation at the definition level means that subsequent proofs, however formally complete, may rest on a false premise.

    Evaluation should therefore check whether the model can:

    • Accurately restate the formal conditions in a problem;
    • Identify containment, equivalence, or implication relationships between concepts;
    • Distinguish hypotheses, conclusions, and what remains to be proved;
    • Determine whether an existing theorem still holds after a definition is modified.

    Tier 2: Reproducing Known Theorems and Proofs

    Researchers frequently need to invoke existing theorems and confirm their applicability conditions. A model cannot merely recite a conclusion—it must explain why the theorem applies to the current problem.

    High-quality tests can ask models to complete a proof, repair a flaw in a proof, or judge whether a proof step relies on an unstated assumption. Such tasks distinguish models that have “memorized related text” from those that “genuinely understand the reasoning structure.”

    For example, a proof might use some monotonicity property in an intermediate step that the problem never guarantees, or it might incorrectly generalize a finite-scale result to the infinite case. A model that only attends to the surface of formulas will easily miss these logical gaps.

    Tier 3: Algorithm Design and Complexity Analysis

    Theoretical computer science studies not only “whether a problem is solvable” but also how to solve it efficiently. A model must design an algorithm based on the problem’s structure and explain its correctness, time complexity, space complexity, and scope of applicability.

    This category involves at least four checkpoints:

    1. Whether the algorithm terminates on all legal inputs;
    2. Whether the output satisfies the problem requirements;
    3. Whether the running cost meets the target upper bound;
    4. Whether special cases or hidden worst-case scenarios have been overlooked.

    For complexity questions, the model should also avoid giving only a vague “approximate efficiency.” A rigorous answer explicitly analyzes loop counts, recursion sizes, data structure operations, and subroutine costs, and distinguishes average-case, worst-case, and amortized complexity.

    Tier 4: Open Conjectures and Judging Research Boundaries

    The task closest to real research is asking the model to handle problems without an accepted solution. The point here is not to expect the model to immediately crack long-standing open problems, but to observe whether it can correctly assess a problem’s status, recognize the applicable boundaries of existing methods, and avoid packaging unproven intuition as a theorem.

    A reliable model should clearly distinguish among:

    • Results that have been proved;
    • Results that hold conditionally;
    • Conjectures supported empirically but lacking proof;
    • False propositions for which counterexamples are known;
    • Questions that currently cannot be resolved.

    On open problems, the greatest danger is not a model answering “this cannot be proved for now,” but rather it generating a fluent, well-structured pseudo-proof containing hidden flaws. Research evaluation must treat “refusing to fabricate conclusions” as an important capability.

    4. Why Open Problems Remain Unsolved by Models

    Current observations show that while models excel at a wide range of standardized tasks, they still face clear limitations when confronting genuinely open theoretical problems.

    First, the training mechanism of LLMs fundamentally depends on existing data. A model can extract patterns from vast numbers of papers, textbooks, and proofs, but that does not equate to stably producing new theorems beyond the boundaries of existing knowledge.

    Second, language generation tends to optimize for coherence. For ordinary QA this is an advantage; but in mathematical proof, coherent expression does not imply logical validity. A model may automatically fill in a step that “looks like it should hold” without checking whether that step truly follows from the premises.

    Third, research requires long-term iteration. Researchers typically go through cycles of conjecture, experimentation, failure, revision, counterexample analysis, and remodeling, whereas one-shot QA can hardly demonstrate this kind of sustained exploration. Even if a model generates a promising direction, external verification and multiple rounds of reflection are needed to judge its value.

    Finally, the difficulty of open problems often lies not in local computation but in discovering the right abstract perspective. A model can process local derivations quickly, yet may fail to find the key idea that reframes the problem.

    5. How Should an Automated Grading System Be Designed?

    For evaluation results to be credible, the grading system must avoid relying solely on final-text similarity. A more reasonable approach is layered verification.

    Formal Verification

    For proofs that can be converted into symbolic expressions, the system should check variable scopes, logical connectives, quantifier usage, and derivation relationships. Formal systems can catch errors that human readers easily miss.

    Programmatic Verification

    For algorithm problems, multiple sets of inputs can be generated automatically—including normal cases, edge cases, and random cases—to check whether the model’s algorithm meets functional requirements. Complexity testing should also be performed to prevent algorithms that only work on small-scale data.

    For universal claims proposed by a model, search programs can be used to look for counterexamples. A single instance that satisfies the premises but violates the conclusion is enough to show the proposition does not hold as stated.

    Expert Review

    Automated verification cannot cover everything. For novel proofs, complex reductions, or open problems, domain experts are still needed to check whether the model has swapped concepts, omitted conditions, or misused existing results.

    The ideal evaluation pipeline is therefore a combination of “machine pre-screening, formal re-verification, and expert spot-checking,” rather than reliance on a single aggregate score.

    6. What Value Does This Kind of Evaluation Bring to Model Development?

    For model developers, the significance of theoretical research evaluation is not ranking—it is locating capability gaps.

    If a model performs well on definition comprehension but frequently fails to close the loop in proofs, the problem likely stems from long-range reasoning or insufficient self-verification. If a model can complete proofs but cannot design new algorithms, its knowledge retrieval is stronger than its creative construction. If a model routinely presents conjectures as theorems, it needs stronger mechanisms for expressing uncertainty, tracing sources, and validating conclusions.

    Future improvement directions may include:

    • Combining natural-language reasoning with formal proof systems;
    • Adding multi-round counterexample search and automated error-correction loops;
    • Having the model proactively check whether assumptions are complete before drawing conclusions;
    • Using independent verifiers to cross-examine algorithms and proofs;
    • Recording the full reasoning trajectory from problem understanding to the final answer;
    • Evaluating research planning ability through staged tasks.

    These directions are not limited to theoretical computer science; they also apply to software engineering, chip design, scientific computing, and data analysis—domains that demand highly reliable reasoning.

    7. How Should Evaluation Results Be Interpreted Rationally?

    A low score on a difficult evaluation does not mean an LLM is worthless. Likewise, high scores on some problems do not directly prove that a model already possesses independent research capability.

    A more reasonable approach is to break results into multiple dimensions:

    • Mastery of foundational knowledge;
    • Comprehension of formal definitions;
    • Stability of multi-step reasoning;
    • Algorithm construction ability;
    • Proof verification ability;
    • Ability to identify errors and counterexamples;
    • Caution when facing unknown problems;
    • Efficiency in collaborating with human researchers.

    At present, LLMs are better viewed as research assistants rather than fully autonomous research agents. They can help organize literature, explain concepts, generate candidate ideas, write verification programs, and check for common mistakes—but key conclusions still require independent proof and expert review.

    Conclusion

    Moving from standardized exams to research-capability evaluation represents an important upgrade in how AI systems are assessed. A truly valuable test should not only ask whether a model can produce correct answers, but also whether it understands the problem, follows the rules of reasoning, recognizes its own uncertainty, and can demonstrate the reliability of its conclusions in a reproducible way.

    Theoretical computer science is an ideal testing ground precisely because it combines high difficulty, strong formalization, and verifiability. Such evaluations may not yet enable models to directly solve long-standing open problems, but they can reveal far more clearly which critical links still separate models from genuine research intelligence—and where future technical development should concentrate its efforts.