Theoretical Computer Science: A Litmus Test for LLM Reasoning
A recent theoretical computer science benchmark evaluates frontier large language models on textbook-level and research-level problems. The results show that models perform well on established exercises but fail to solve open conjectures, highlighting the gap between retrieving existing knowledge and producing genuinely new proofs.
1. Background: What One Exam Paper Reveals
A team of academic researchers and industry research organizations recently released a systematic evaluation in theoretical computer science. They built an exam paper covering major directions in the field and used it to test some of the most advanced large language models available. The result was telling: when faced with open conjectures that remain unresolved, none of the evaluated models was able to produce a correct answer solely through its own reasoning.
The timing is interesting. Shortly before this, a research organization publicly released hundreds of AI-assisted mathematical manuscripts, grouped by topic into several “result families” spanning number theory, geometry, mathematical physics, theoretical computer science, and other areas. This sparked a wave of commentary suggesting that AI might soon replace mathematicians. The theoretical computer science exam paper, however, poured cold water on that optimism: on truly open problems whose answers are unknown even to humans, the models still fell short.
2. What Is Theoretical Computer Science?
TCS stands for Theoretical Computer Science. It is less concerned with which machine model you use or which programming language you write in, and more focused on computation itself: how fast the optimal solution to a problem can be, whether a certain lower bound can be broken, and whether some problems are inherently unsolvable.
An analogy may help clarify the division of labor. Programmers are somewhat like drivers, paying attention to the engine, transmission, and interior—that is, concrete implementation, engineering details, and performance tuning. Theoretical computer scientists are more like researchers studying transportation and route planning. They ask questions such as: what is the theoretical minimum travel time from point A to point B, and do some routes simply never exist mathematically? The field sits at the intersection of mathematics and computer science. Nearly all of its conclusions are presented as theorems and proofs, and its core action is proving rather than implementing.
3. Why Use TCS to Evaluate LLMs?
There is one particularly important reason for choosing TCS as an evaluation standard: verifiability.
A top mathematician once pointed out that AI has the same fatal weakness in almost every domain—it can generate incorrect content that cannot be verified, sounding plausible at first glance but falling apart under scrutiny. Mathematics, and proofs in particular, are among the few exceptions. Whether a proof is correct can be checked automatically by a machine with almost no need for subjective human judgment. This is somewhat like solving a Sudoku puzzle: filling in the answer may be difficult, but once it is filled in, checking whether it is correct can be done immediately.
For this reason, mathematics and theoretical computer science are areas where AI can produce results with relatively little dispute—right is right, and wrong is wrong. Evaluating models in such a domain helps remove the noise of subjective judgment and provides a more reliable signal about their real reasoning ability.
4. How the Benchmark Is Designed
A high-quality benchmark usually involves careful design across several dimensions:
- Difficulty stratification. Problems are divided into “textbook-level” and “research-level” categories. Textbook-level problems have publicly known standard answers and test how well models have mastered existing knowledge. Research-level problems correspond to unresolved open conjectures and test whether models can produce genuinely novel reasoning.
- Breadth of problem types. The benchmark covers upper and lower bound proofs in complexity, algorithm design and analysis, counterexample construction, reduction transformations, and other subfields, so models cannot rely on tricks from only one type of problem.
- Scoring mechanism. For problems with standard answers, the evaluation uses strict comparison. For proof-based problems, it relies as much as possible on formal verifiers or expert review rather than simply judging whether an answer “looks correct.”
- Data contamination prevention. Techniques such as time cutoff, deduplication, and constructing new variants are used to reduce the chance that benchmark problems and answers have already appeared in training corpora. Otherwise, the resulting score reflects memorization rather than ability.
5. Core Findings and Interpretation
The results can be understood on two levels.
The first level concerns textbook-level problems with standard answers. Frontier models generally perform reasonably well, confirming their strong capacity for knowledge storage and pattern matching.
The second level is the more important one: on open conjectures that remain unresolved to this day, none of the evaluated models was able to complete a proof using its own capabilities. This distinction matters because it separates two fundamentally different abilities: efficiently retrieving and combining information from massive corpora, and constructing from scratch a new proof that no one has known before. Current models perform very well on the former but have not truly crossed over to the latter.
In other words, models can fluently “invoke” knowledge that humans have already written down. But when confronted with problems that humans themselves have not solved, they cannot automatically create a path from the problem to a new proof. This result is both a cold shower and a clarification: evaluating AI capabilities must be grounded in benchmarks that are verifiable and reproducible.
6. Formal Verification: Letting Machines Decide Correctness
As noted earlier, the idea that “proofs can be checked automatically by machines” reflects the approach of formal verification. With theorem provers, or formal verification tools, proofs written by humans or models can be converted into machine-checkable forms. The system then checks each step of reasoning to determine whether it is valid. The advantage of this mechanism is that the judgment criteria are objective, the results are reproducible, and the outcome is largely unaffected by the evaluator’s personal preferences.
However, formalization also comes at a cost. Strictly translating a natural-language or semi-formal proof into a form that a machine can accept often requires substantial additional effort. In practical evaluations, this usually leads to a verification pipeline: first, a model generates an answer; then formal tools or experts verify it; finally, only results that truly pass verification are retained.
A schematic evaluation flow might look like this. It is intended only to illustrate the logic and does not represent a specific product interface:
def evaluate(model, benchmark):results = []for item in benchmark.by_difficulty(): # textbook-level / research-level stratificationwith sandbox(item): # isolated sandbox execution to prevent contamination and unauthorized accessanswer = model.generate(item.prompt)# For items with standard answers, compare them; proof problems are checked by formal verifierspassed = check_proof(answer) if item.is_proof else match(answer, item.gold)results.append({"id": item.id, "passed": passed})return summarize(results)
7. Implications for Evaluation and Engineering Practice
Whether you are reproducing this kind of benchmark or building a similar capability-validation system inside an organization, several general engineering practices are worth considering:
- Isolated evaluation environments. Run model inference and verification logic in containerized sandboxes to keep the execution environment clean and recoverable, preventing contamination between tasks.
- Separation of data and results. Use object storage services to centrally manage evaluation datasets and historical results, making versioning and reproduction easier.
- Full-link observability. Use logging services to record each call and judgment process, and use monitoring and alerting to detect anomalies promptly, such as verifier timeouts or sudden changes in result distributions.
- Elastic compute scheduling. Research-level proofs are often computationally intensive. Container platforms and elastic compute resources can be scaled as needed, significantly reducing evaluation costs.
These capabilities are commonly provided as standard cloud product categories by providers such as Baidu AI Cloud, including object storage, container platforms, logging services, monitoring and alerting, and elastic compute. When building an evaluation system, the key is to design the “problem–reasoning–verification–logging” pipeline clearly and reproducibly, rather than relying on the opaque behavior of a specific tool.
8. Conclusion
The greatest value of this theoretical computer science exam paper is not the score it gives to any particular model. It is the demonstration of a rigorous paradigm for evaluating capabilities: using hard problems with clear right-or-wrong answers that can be verified by machines to approximate the true boundary of model ability. It tells us that AI is already strong at “recalling and using existing knowledge,” but still has a clear distance to travel in “creating unknown knowledge.” For developers and researchers, instead of chasing the astonishment of trending topics, it is more productive to build verifiable and reproducible evaluation infrastructure. That is the cornerstone for determining whether progress in AI is genuine and reliable.
