Theoretical Computer Science: A Verifiable Yardstick for Evaluating LLM Research Capabilities
As large language models iterate faster, benchmark leaderboards are refreshed every few weeks with ever-higher scores. Yet rising numbers make it harder, not easier, to answer a basic question: can a model actually solve exam-style problems, or can it do research? Using theoretical computer science (TCS) as a lens, this article examines how to build an evaluation system that stays close to real research while remaining objectively verifiable, and what developers and enterprises should take away about judging model capabilities.
$$Recently, topics like “AI is disrupting mathematics” have become frequent talking points. As large models iterate faster, benchmark leaderboards refresh almost every few weeks, the numbers keep climbing, and yet it grows harder to truly judge one thing: is a model good at “solving problems,” or is it good at “doing research”? A gap that is often overlooked sits between the two. This article takes theoretical computer science (TCS) as an entry point to analyze how to build an evaluation system that both resembles real scientific research and can be objectively verified, and then extends that discussion to how developers and enterprises should think about model capability evaluation.
What Theoretical Computer Science Actually Tests
Theoretical computer science sits at the intersection of mathematics and computer science. Nearly every problem revolves around “computation” as its core, and its research method relies heavily on mathematical proof rather than engineering implementation.
A helpful analogy: ordinary software engineering is more like “driving a car that has already been built”—you care about engine performance, interior features, and whether the functions run end to end. TCS research is more like studying “the transportation system itself.” It asks: what is the theoretical minimum time to travel from point A to point B? Is there a route that is mathematically impossible to traverse? These questions do not care whether you have ready-made libraries and frameworks on hand; they care about “where the boundaries of computation lie.” Precisely because its conclusions are presented as theorems and proofs, TCS naturally possesses a valuable property: the correctness of a conclusion can be independently and mechanically verified.
The Gap Between “Solving Problems” and “Doing Research”
Most popular leaderboards essentially test “exam-taking ability”: given a problem with a standard answer, can the model get it right? Such evaluations have clear thresholds and simple scoring, but they carry a structural limitation—the more a problem resembles “real research,” the harder it becomes to grade automatically.
Real research differs fundamentally from exam questions:
- Research has no prescribed solution steps. You cannot know in advance which approach to use, and you may not even know whether an answer can be reached at all.
- Conclusions are unpredictable in advance. Many open problems do not even have a known correct answer for the person posing them, so you cannot simply “fill it in and check” the way you would with Sudoku.
- Grading costs are extremely high. Verifying whether a piece of research is correct often requires substantial effort from domain experts.
As a result, a high score on a leaderboard only shows that a model is good at solving problems whose answers have already been verified. It does not directly mean the model can propose conjectures, explore the unknown, or independently advance open problems. This is exactly the blind spot that current evaluation systems commonly share.
Why a “Verifiable” Discipline Is an Ideal Yardstick
One important reason math-type problems are a favorite showcase for AI companies is the “verifiability” of their answers. This is like Sudoku: filling in the answer is hard, but checking whether a completed grid is correct only requires mechanically running through the rules. This asymmetry—“hard to generate, easy to verify”—makes evaluation objective, reproducible, and automatable.
TCS stands out especially in this direction: the vast majority of its conclusions can be verified by a machine. A proof either holds or it does not, with almost no gray zone open to interpretation. This means evaluation need not rely on subjective scoring or manual grading, which greatly reduces the risk of score gaming, cheating, and scoring bias, so that the score genuinely reflects a model’s underlying reasoning ability.
Below is an illustrative “automatic grading” flow showing how the verification step operates independently of the generation step:
# Illustrative code: decoupling "generation" from "verification" in evaluationdef evaluate_model(model, problem):answer = model.solve(problem) # Generation: the model produces a proof or solution# Verification: no human needed; an independent checker decides validityresult = verifier.check(problem.statement, answer)return {"is_valid": result.valid, # Whether the conclusion holds (objective binary)"checks_passed": result.passed, # Number of key reasoning steps passed"verified": result.machine_checked # Whether it passed machine/strict proof checking}
The core idea of this design is: hand the question of “did it get the right answer” back to a verifiable checker, rather than making evaluators guess at the model’s intent. This is precisely the value of a “verifiable discipline” as an evaluation yardstick.
Key Design Points for an Evaluation System
A rigorous evaluation of research ability is typically organized around the “core activities of real scientific research,” rather than simply piling up practice problems. Taking a scale of 100 problems as an example, a reasonable breakdown would cover several kinds of work that theoretical computer scientists engage in most often day to day (the following are typical activity types summarized from general practice in the field):
- Proposing and proving conjectures: faced with an undecided problem, can the model give a correct and verifiable argument?
- Algorithm design and analysis: construct an algorithm for a problem and provide a rigorous analysis of its correctness and complexity.
- Lower bounds and impossibility proofs: show that a class of problems “has a speed limit no matter how fast you go,” or that a certain route is “doomed to fail.”
- Constructive results: give a concrete, checkable construction and explain the constraints it satisfies.
In this kind of evaluation, one key and profound finding deserves special attention: for conjectures that remain open to this day, not one of the reference models tested was able to crack them independently on its own. This shows that current frontier models perform impressively on “closed-form exam-taking” but still face a clear capability ceiling on “open-ended research.” By distinguishing “problems with known answers” from “open conjectures,” the evaluation system can clearly present these two capabilities as separate layers.
Why Verifiability Is the Cornerstone of Evaluation
The credibility of an evaluation depends largely on whether it is “cheat-resistant and reproducible.” If a problem’s answer requires subjective human judgment, problems such as scoring drift, non-reproducible results, and even models “catering to the grader’s preferences” can easily arise. An evaluation system centered on machine verification naturally avoids these pitfalls:
- Objective results: a proof holds or it does not, eliminating ambiguous interpretation.
- Controllable cost: verification costs far less than generation, so it can run at scale and be automated.
- Reproducibility: for the same model and the same problem, anyone re-running the evaluation reaches a consistent conclusion.
This is also the fundamental reason it differs from ordinary “leaderboards”—what it measures is not exam-taking technique but a depth of reasoning closer to real scientific research.
Practical Takeaways for Developers and Enterprises
For developers and enterprises that care about deploying large models and want to build their own evaluation capability, this approach offers several actionable lessons:
- Separate the two needs: “exam-taking” and “research.” If your scenario only requires the model to complete tasks with fixed formats and clear answers, traditional leaderboards still offer reference value. But if the work involves complex reasoning or solution design—open-ended tasks—you must be wary that “a high leaderboard score does not equal high capability.”
- Prioritize verifiable evaluation methods. When building an internal evaluation set, decouple “generation” from “verification” as much as possible, and score using objective means such as rules, unit tests, and formal verification, avoiding the bias introduced by subjective scoring.
- Build reusable evaluation infrastructure. A complete evaluation pipeline typically needs to cover problem management, batch inference scheduling, result storage, automated verification, and visualized reporting. By leveraging general capabilities available on cloud platforms—for example, object storage to keep evaluation data, message queues to decouple generation from verification tasks, container platforms to elastically scale inference resources, and logging and monitoring/alerting services to track the evaluation process—enterprises can build a stable, reproducible evaluation pipeline at relatively low cost without reinventing the wheel.
- Establish a “capability layering” mindset. The real value of evaluation lies not in producing a single aggregate score, but in revealing which task types a model is strong or weak at, thereby providing a basis for model selection, fine-tuning, and scenario matching.
Conclusion
The evaluation built on theoretical computer science carries weight precisely because its conclusions can be objectively verified by a machine, which narrows the grand question of “can a model do research” down to a measurable, reproducible yardstick. The cold water it throws serves as a reminder: a rising leaderboard score does not mean a leap in research capability. For developers and enterprises, the truly pragmatic attitude is to make good use of verifiable evaluation to objectively understand a model’s boundaries while not blindly trusting a single score—only by viewing “generation ability” and “verification ability” separately can you make reliable technical judgments in real business contexts.
