Evaluating Frontier LLMs on Theoretical Computer Science: Capabilities and Limits
A look at how large language models perform on theoretical computer science tasks, why TCS is a good benchmark for reasoning, a three-tier capability framework, key evaluation challenges such as data contamination and proof grading, and practical advice for using models in mathematical research workflows.
What Is Theoretical Computer Science?
Theoretical computer science (TCS) studies the mathematical laws of computation itself. The questions it cares about include: whether a class of problems can in principle be solved by an algorithm, how much time or memory solving them requires, and which tasks cannot be completed efficiently in practice. Programming, system building, and performance tuning belong to the engineering layer; TCS focuses on the theoretical boundaries behind these engineering activities.
A transportation system offers a useful analogy. Engineers care about vehicle design and road construction, while theorists ask whether the shortest path between two locations can be computed in polynomial time, and whether there are bottlenecks no algorithm can overcome.
The field mainly includes the following areas:
- Computational complexity: characterizing difficulty hierarchies of problems and determining which complexity class a decision problem belongs to.
- Algorithm design and analysis: proving an algorithm’s correctness and deriving bounds on its time and space usage.
- Foundations of cryptography: defining security in mathematical language and studying reductions between different assumptions.
- Information theory and randomness: characterizing information content, compression limits, and randomness.
- Game theory and mechanism design: studying equilibria in multi-party decision-making and resource allocation.
Why TCS Is Well Suited to Testing Model Reasoning
TCS results mostly take the form of theorems and proofs, and this format has two useful properties. First, problems can be defined precisely—every object in a problem statement has a clear mathematical meaning. Second, whether a conclusion holds can be verified by checking the proof step by step. Compared with open-ended writing, this makes evaluation far easier to quantify.
This resembles math competition problems, but the difference is significant. Competition solutions usually exist in training materials; a solver only needs to recognize the problem type and apply a template. Research-level problems often require new constructions, new invariants, or new reductions, and existing templates rarely cover them directly. High scores on competition problems therefore do not imply research ability.
A practical analogy: solving problems is like cooking from a recipe, where the steps and expected taste are already fixed; research is like designing a new dish, requiring judgment about which ingredient combinations might work and repeated retries after failures. Evaluations need to observe these two capabilities separately.
Three Levels of Model Capability
For evaluation purposes, model performance on TCS tasks can be divided into three tiers.
- Knowledge reproduction: accurately restating definitions, theorem statements, and the steps of classic algorithms. Models are usually stable at this level.
- Method application: completing derivations for new instances within a known technical framework, such as applying an existing reduction to a slightly modified problem. Performance varies considerably here, depending on how close a problem is to training material.
- Original proof construction: proposing new ideas and carrying out rigorous argumentation. This is currently the hardest to achieve reliably, and the results are also the hardest to judge.
Tiering gives evaluation results a clear interpretive target. A high score at the first level does not mean a model can do third-level work.
Core Challenges in Evaluation Design
Problem Sources and Data Contamination
Research papers and course materials enter large public corpora. If evaluation problems are taken directly from published results, a model may have seen the original problem or proof during training, so the test measures memorization rather than reasoning. Countermeasures include: using new problems published after the training data cutoff; applying equivalent rewrites of problems and checking whether results stay consistent; and keeping part of a private, unpublished problem bank.
Grading Proofs
Computation problems usually require only a final answer, but proof problems must be checked step by step. Three common grading approaches exist:
- Expert human review: the most accurate, but costly and slow, and difficult to scale.
- Formal verification: translating the proof into a formal language and having a proof assistant check it step by step. This yields a reliable verdict, but requires the problem to be formalizable and involves substantial upfront work.
- Rubric-based scoring: breaking the proof into key steps and evaluating each for correctness, completeness, and skipped reasoning. This is currently the most practical compromise.
Grading is also complicated by proofs that merely “look correct.” A model’s output may be grammatically smooth and structurally complete, while a key lemma is asserted without justification. Scoring criteria should require evidence for every non-trivial claim.
Open Problems Have No Standard Answer
When the problem is an unsolved conjecture, no reference answer exists. A reasonable approach is to have domain experts review the model’s output and record valuable contributions, rather than simply counting right and wrong answers. This style of assessment is closer to how research collaboration actually works.
An Illustrative Evaluation Workflow
The following code shows only the workflow structure; the functions are placeholder implementations and do not correspond to any specific tool or interface.
from dataclasses import dataclass@dataclassclass ProofItem:problem_id: strmodel_output: stris_new_problem: bool # whether the problem postdates the training data cutoffdef run_evaluation(items, model, grader):results = []for item in items:proof = model.generate(item.problem_id, item.model_output)steps = grader.split_into_steps(proof) # split into checkable stepsstep_scores = [grader.check(step) for step in steps]results.append({"problem": item.problem_id,"new_problem": item.is_new_problem,"complete": all(s.valid for s in step_scores),"gaps": [s.note for s in step_scores if not s.valid],})return results
The key point of this structure is that every result retains error locations instead of a single overall score. Error locations help researchers identify where the model fails, so they can improve training or prompting accordingly.
Where the Current Capability Boundaries Lie
Based on the analysis above, several fairly stable boundaries can be summarized:
- For proofs with clear definitions and familiar structure, models can usually produce readable derivations.
- When a proof spans multiple technical areas, models tend to skip steps in intermediate lemmas.
- Models may produce confident but incorrect arguments, so fluency alone cannot be used to judge correctness.
- On open problems, a model’s main value lies in suggesting ideas and candidate directions; final judgment still requires experts.
These boundaries shift with model versions. Evaluation conclusions should note the testing date and the scope of the problems used, so they are not treated as permanently valid.
Practical Recommendations
If you want to introduce models into your own mathematical or algorithmic research workflows, consider the following practices:
- Break tasks into verifiable subproblems—for example, “check every step of this inequality derivation” is easier to control for quality than “prove this theorem.”
- Keep the model’s full reasoning chain intact so humans can review it.
- Add independent verification for key conclusions, such as numerical checks, small-scale exhaustive testing, or formal verification.
- Maintain an internal problem bank and scoring rubric, updated regularly, to reduce the impact of data contamination.
- Make clear to users that model output is a candidate result and should not be trusted before verification.
Conclusions in mathematical and algorithmic research often influence subsequent system design, so investment in verification should be proportional to the importance of the conclusion.
