Evaluating Frontier LLMs on Theoretical Computer Science: Capabilities and Boundaries

    This article examines theoretical computer science as a rigorous benchmark for the mathematical reasoning of large language models. It outlines a three-layer evaluation design, process-based scoring, and common failure modes in formal proof, complexity analysis, lower bounds, counterexample construction, and open-problem research. It also proposes a verifiable generate-check-revise workflow and discusses data contamination, scoring bias, and benchmark governance for developers and platform teams.

    Evaluating Frontier LLMs on Theoretical Computer Science: Capabilities and Boundaries

    1. Why Use Theoretical Computer Science to Test Mathematical Ability

    If the mathematical ability of large models is understood simply as “computing quickly and correctly,” evaluation easily remains at the level of arithmetic, algebra, and standard word problems. Such problems can reflect a model’s basic calculation and pattern-matching ability, but they struggle to answer a more critical question: does the model have mathematical reasoning ability close to research work? Theoretical computer science provides a stricter observation window. It focuses not on “how to repair a machine,” but on the limits of computational processes: how much time and space a problem requires in the worst case, which problems have efficient algorithms, which problems are destined to have no general solution, which structures can be reduced, and which lower bounds can be proven.

    Therefore, theoretical computer science evaluation is closer to a “research ability spot check.” A problem may require constructing an algorithm, analyzing complexity, giving a counterexample, proving infeasibility, or transforming an open problem into a verifiable subproblem. The model must not only give a conclusion but also provide a reasoning chain, proof structure, and boundary conditions. For this reason, such evaluation can expose the real weaknesses of large models in long-horizon logic, formal rigor, and self-verification.

    The value of an evaluation study covering the full field of theoretical computer science and nine frontier large models does not lie in producing a simple ranking, but in mapping capability profiles: which subfields already have potential for research assistance, which steps still rely heavily on human gatekeeping, and which errors are systematic. For developers and enterprise users, this is also an entry point for understanding the boundaries of “AI mathematical ability.”

    2. Evaluation Design: From Problem Coverage to a Scoring Loop

    Theoretical computer science is broad and includes at least algorithm design and analysis, computational complexity, computability, automata and formal languages, foundations of cryptography, combinatorial optimization, randomized algorithms, approximation algorithms, and proof complexity. If an evaluation covers only a single problem type, it is easily masked by the model’s language ability. A more reasonable design should include three layers:

    1. Knowledge layer: Tests definitions, theorem conditions, classical results, and common reduction relationships to verify whether the model has an accurate conceptual foundation.
    2. Reasoning layer: Requires multi-step derivation, complexity calculation, counterexample construction, and proof drafts to observe whether the model can maintain logical consistency.
    3. Research layer: Presents simplified open problems or research fragments and requires testable ideas, identification of proof gaps, experimental design, or formalization paths.

    Scoring also cannot rely only on the final answer. In theoretical computer science, an incorrect conclusion is sometimes accompanied by a seemingly reasonable proof, and answer matching alone cannot distinguish “guessing correctly” from “reasoning correctly.” Evaluation should introduce process scoring: whether key lemmas hold, whether complexity derivations close, whether counterexamples satisfy constraints, whether proofs cover boundary cases, and whether circular reasoning exists. For formalizable problems, natural-language proofs can also be translated into formal skeletons and checked for verifiability.

    A general evaluation loop can be abstracted as follows:

    1. function evaluate(model, problem):
    2. draft = model.solve(problem.statement)
    3. normalized = normalize(draft)
    4. checks = []
    5. checks.append(check_logic_consistency(normalized))
    6. checks.append(check_complexity_bound(normalized))
    7. checks.append(check_counterexample_validity(normalized))
    8. checks.append(check_proof_gaps(normalized))
    9. if problem.requires_formalization:
    10. checks.append(check_formalizable_skeleton(normalized))
    11. score = aggregate(checks, problem.rubric)
    12. return {draft, checks, score}

    This process emphasizes “checkable evidence” rather than a single answer. For actual platforms, evaluation sets should be paired with version management, contamination detection, randomized variants, and human review to prevent inflated performance caused by memorizing public problems.

    3. Boundary 1: Formal Expression and Proof Rigor

    Large models often appear fluent on natural-language mathematics problems, but in theoretical computer science, fluency does not equal rigor. Proofs need clear quantifier order, preconditions, construction scope, and reduction direction. For example, to prove that a problem is hard, one must explain which known problem is being reduced from, whether the reduction runs in polynomial time, and whether the bidirectional mapping preserves answers. Common model problems include writing “there exists an algorithm” as “for all algorithms,” mixing asymptotic upper and lower bounds, ignoring the success probability of randomized algorithms, or skipping key base cases in inductive proofs.

    Such errors show that current large models are better at generating “proof-like text” than at maintaining a “verifiable proof state.” In engineering practice, proofs can be split into several verifiable units: definition checks, lemma dependency checks, complexity checks, and boundary condition checks. Formal proof assistants, constraint solvers, and symbolic computation tools can serve as external verifiers, but the model needs to learn when to call them, how to translate content, and how to backtrack after verification failure. Evaluation should treat “discovering one’s own proof gaps” as a separate capability dimension, rather than rewarding only final answers.

    4. Boundary 2: Complexity, Lower Bounds, and Counterexample Construction

    Complexity analysis is a highly discriminative part of theoretical computer science evaluation. Models need to distinguish input size, parameterized complexity, worst case and average case, and understand concepts such as approximation ratio, competitive ratio, and space complexity. Relying only on language patterns, a model may give plausible asymptotic bounds while making errors in recurrence expansion, logarithmic bases, amortized analysis, and randomized expectation. More difficult is lower-bound proof: it requires the model not only to construct an algorithm but also to argue that a certain class of algorithms cannot do better.

    Counterexample construction can also expose boundaries. A valid counterexample must satisfy all constraints in the problem and precisely target the weak point of the false proposition. A model may generate an instance that “looks like a counterexample,” but its size, weights, graph structure, or input conditions do not satisfy the requirements. Evaluation design should require the model to provide both the counterexample and a verification process, such as a checklist that checks constraints one by one. For algorithm problems, the model can also be asked to provide a small-scale exhaustive verification plan to demonstrate that the counterexample is valid.

    5. Boundary 3: Open Problems and Long-Horizon Research Transfer

    Open problems in theoretical computer science usually have no standard answers. Evaluation cannot simply ask a model to “solve an open problem”; instead, it should transform the task into assessable research behavior: can the model accurately restate the current status of the problem, identify known results and unknown boundaries, propose falsifiable sub-conjectures, design small-scale experiments or formalization fragments, and point out potential obstacles in an approach?

    This type of evaluation is closer to a research assistant scenario. The value of a model may lie in organizing reduction relationships, generating proof drafts, finding similar structures, and proposing directions for counterexample search, rather than independently completing theorem proofs. Evaluation should reward “valuable intermediate products” while penalizing overconfidence. If a model can clearly state “a key lemma is missing here” or “this reduction requires additional assumptions,” it is more reliable than giving a polished but incorrect complete proof.

    6. From Evaluation to Engineering: A Verifiable Reasoning Framework

    To translate evaluation conclusions into development practice, the core is to build a “generate—check—revise” loop. Large models propose candidate proofs, algorithms, and counterexamples; external tools verify the verifiable parts; human experts judge research value and open directions. A reusable framework includes:

    • Problem structuring: Split a problem into definitions, input constraints, goals, allowed tools, and scoring rules.
    • Multiple candidate sampling: Generate multiple proofs or algorithm drafts to avoid single-path lock-in.
    • Automated checks: Check logical consistency, complexity, counterexample validity, and formalization skeletons.
    • Failure attribution: Distinguish conceptual errors, computational errors, proof gaps, and expression ambiguity.
    • Human review: Retain expert review for research-style problems and record disputed points.
    • Contamination control: Use variant problems, private problems, and dynamically generated problems to reduce memorization effects.

    7. Evaluation Distortion and Governance

    Theoretical computer science evaluation especially needs to guard against three types of distortion. The first is data contamination: public problems may enter training corpora, causing models to “memorize answers.” The second is scoring bias: if natural-language proof scoring relies on another model, same-source errors may be introduced. The third is problem bias: if problems emphasize certain types of reductions or certain complexity models, conclusions may be incorrectly extrapolated.

    The governance approach is to establish multi-layer evidence: answers, proof skeletons, key lemmas, counterexample verification, and formalization checks are scored separately; disputed problems receive double review; model outputs are subjected to random perturbation tests to observe whether conclusions are stable; open problems use rubric scoring rather than unique answers. Only by placing “verifiability” at the center can evaluation reflect real research boundaries.

    8. Implications for the Boundaries of AI Mathematical Research

    The core signal from this type of evaluation is that large models can already take on some auxiliary work in theoretical computer science, such as concept organization, proof draft generation, algorithm idea expansion, and counterexample search; however, strict proofs, complexity lower bounds, long-horizon logical closure, and open-problem judgment still require external verification and human expert gatekeeping. The boundary of AI mathematical ability is not just “whether it can solve problems,” but “whether it can stably advance in a checkable reasoning space.”

    For developers, a more pragmatic goal is not to pursue “fully automated mathematical research,” but to build verifiable intelligent reasoning systems: let models propose hypotheses, let tools verify steps, and let humans decide direction. For platforms and engineering teams, evaluation sets, scorers, formal verification, and contamination governance should become the infrastructure for building this type of capability. Only then can the mathematical abilities of frontier large models move from demonstrations to trustworthy assistance, and from answer generation to reliable components in research workflows.