TCS Evaluation: How to Verify Large Language Model Research Capabilities
As debates heat up over whether large language models (LLMs) can move beyond solving textbook problems to genuine research, this article argues that theoretical computer science (TCS) offers an ideal testing ground. TCS results can be formalized and proofs can be checked step by step, making it possible to evaluate not just whether answers look correct, but whether the underlying research process is verifiable. The article explains why conventional leaderboards fall short, breaks a research-oriented exam into four task categories (concept and boundary judgment, constructive proofs and algorithm design, complexity reductions and lower bounds, and partial progress on open problems), and details how to build an evidence chain for grading. It also covers defenses against score-gaming, sustainable platform engineering, a multi-dimensional metric system, and practical takeaways for enterprises and R&D teams building their own evaluation pipelines.
From Solving Problems to Doing Research: What Really Changes in Evaluation
Debate over large language models’ mathematical abilities has intensified lately. On one hand, models are advancing rapidly on many math and reasoning tasks. On the other, a growing volume of model-generated mathematical material has appeared on open paper platforms, prompting a sharper question: are LLMs merely drilling practice problems, or can they genuinely participate in real research?
The crux is not whether a model can produce a polished answer, but whether it can perform the core actions of research: understanding definitions, identifying boundaries, constructing proofs, finding counterexamples, reducing problems, and verifying conclusions. In other words, the focus of evaluation needs to shift from “does the result look like research?” to “is the process verifiable?”
Theoretical computer science (TCS) happens to be an excellent domain for observing this shift. Unlike applied development, it does not depend on a specific engineering environment; unlike some experimental sciences, it does not rely heavily on real-world observation. It focuses on “computation” itself—studying computability, complexity, reduction relationships, algorithm construction, and lower-bound proofs. Many results can be expressed formally, and many proofs can be verified step by step with automated checking tools. This verifiability makes TCS an important touchstone for measuring LLM research capability.
Why Leaderboards Struggle to Reflect Real Research Ability
Today’s LLM evaluation landscape is rich, spanning knowledge Q&A, code generation, and mathematical reasoning, with new leaderboards appearing almost every month. Their value is undeniable: they help developers and enterprises quickly judge whether a model has basic capabilities and provide intuitive reference for technology selection.
But leaderboards have an inherent limitation: they typically test “problem-solving ability within the scope of existing knowledge.” Many questions come from public problem sets, historical exams, standardized tests, or cases that have been discussed repeatedly. Facing such questions, models often do not research from scratch; instead, they rely on knowledge accumulated in training data, pattern matching, template reuse, and reasoning combinations. This is like having someone solve a large number of classic worked examples: a high score shows a solid foundation, but a high score does not equal independent research ability.
Real research is entirely different. It has no ready-made steps, no standard answers, and often no clear path to success. Researchers must judge whether a problem is solvable, try different proof directions, admit failure and revise assumptions, propose new definitions, discover counterexamples, or prove that a certain direction is doomed to fail. The process is full of uncertainty, and results may remain unresolved for a long time.
Grading cost makes this even harder. If a model outputs natural-language proofs or complex derivations, human review becomes very expensive; if it outputs only conclusions, it is hard to tell whether they are merely guesses. Evaluation must solve three problems: first, whether the problems are close enough to real research; second, whether model outputs can be checked automatically; third, whether evaluation results can be reproduced.
Why TCS Is a Good Starting Point for Research-Oriented Evaluation
A core reason TCS is well suited to this kind of evaluation is that “conclusions can be formalized and processes can be checked.”
In mathematics and theoretical computer science, many propositions can be expressed in symbolic systems. Whether an algorithm is correct can be verified through input-output relationships and loop invariants; whether a reduction holds can be checked by confirming that the construction preserves problem equivalence; whether a counterexample is valid can be verified by substituting directly into the definition; whether a proof holds can be checked by examining each reasoning step.
Evaluating such tasks offers at least three advantages.
1. Clear conclusion boundaries
Many TCS problems are hard, but the propositions themselves are precise. Whether a model has solved a subproblem, provided a correct counterexample, or completed a reduction can all be judged by objective standards.
2. Decomposable proof processes
Complex proofs can be broken into lemmas, steps, boundary conditions, and assumptions. During evaluation, one can examine not only the final conclusion but also whether each step is valid, thereby identifying whether a model truly understands the structure or is merely generating plausible-looking text.
3. Highly diverse research actions
TCS is not just about proving theorems. It includes definition analysis, structure construction, complexity analysis, reductions, lower bounds, counterexamples, randomization methods, approximation algorithms, communication complexity, and many other research activities. These activities can reflect a model’s research potential fairly comprehensively.
TCS evaluation is therefore not about creating a harder set of math problems, but about building a “research-oriented task arena”: having the model complete several verifiable research actions within a limited time, and produce credible conclusions through a combination of automated checking and human review.
What a Research-Oriented Exam Should Test
Centered on theoretical computer science, evaluation problems can be abstracted into four categories of tasks. This division is not meant to increase difficulty, but to cover the different capability dimensions of a researcher’s daily work.
1. Concept and boundary judgment
These tasks test whether a model can accurately understand definitions, distinguish conditions, identify counterexamples, and judge whether a proposition holds under specific constraints.
For example, given a formal definition or structural description, the model might be asked to judge whether two objects are equivalent; or given several conditions, to identify which one cannot be omitted; or to construct a counterexample showing why a seemingly natural assumption fails.
Such problems may look less grand than “proving a theorem,” but they are crucial. In real research, many errors do not come from the derivation process but from misunderstandings of definitions and boundary conditions. Whether a model can accurately grasp the premises is the first step in judging the reliability of its research.
2. Constructive proofs and algorithm design
In theoretical computer science, many results are proven not through counterexamples or refutation, but through construction. For instance, to prove that a problem has an efficient algorithm, one must give a concrete algorithm; to prove that some object exists, one must give a construction process.
These tasks require the model not only to say “a construction is possible” but also to provide an executable or checkable solution. During evaluation, the model can be asked to output pseudocode, step descriptions, input-output constraints, and a correctness argument. Automated verifiers can check whether the construction meets the requirements, covers all boundary conditions, and runs within complexity limits.
Such problems can distinguish “knowing a result” from “being able to reproduce the construction behind the result.” For assessing research ability, construction capability is especially important because it is closer to the core output of actual scientific research.
3. Complexity reductions and lower-bound proofs
Reduction is a fundamental tool in theoretical computer science. By transforming a known hard problem into a target problem, researchers can prove that the target problem is at least as hard. Lower-bound proofs go further, answering: under a certain model or resource constraint, how much time, space, or communication does a problem require at minimum.
These tasks are difficult but very valuable. They test whether a model can identify structural relationships between problems, construct a valid mapping, and explain the necessity of each step in a reduction. During evaluation, automated checks can verify whether a reduction preserves equivalence, while human review can judge whether the reduction construction has genuine explanatory power.
If a model can provide verifiable steps on a complex reduction problem, it demonstrates strong structured reasoning ability. If it merely cites common results without explaining the construction, it is more likely relying on memory matching.
4. Partial progress on open problems
Open problems are the most sensitive and important part of research-oriented evaluation. Genuine frontier research does not always require a model to immediately solve a long-standing conjecture; it looks at whether the model can make verifiable partial progress.
For example, can a model propose a weaker but provable lemma; can it narrow the problem’s search space; can it construct a counterexample for a specific case; can it decompose an open problem into several verifiable subproblems; can it point out why a certain class of proof paths is unworkable.
The scoring criteria for such problems cannot focus only on “whether the original problem was solved.” If a model provides a valuable intermediate conclusion not previously stated explicitly, or generates a set of automatically checkable counterexamples, this too should be regarded as part of research ability.
Why Machine Grading Must Be Paired with an Evidence Chain
The biggest technical challenge of research-oriented evaluation is not writing problems, but grading them. A model can generate large amounts of text, but the evaluation system cannot judge correctness by textual fluency alone. It must establish an evidence chain so that every conclusion can be traced, verified, and reproduced.
A practical evaluation workflow typically includes the following steps:
Input: problem statement, constraints, allowed tools, time limitProcess: model generates answer, proof, pseudocode, or counterexampleVerify: automatically check conclusions, steps, boundary conditions, and complexityRecord: save full output, execution logs, verification results, and human review notesScore: combine pass rate, partial progress, error types, and evidence completeness
A schematic workflow looks like this:
def evaluate(item, model, verifier):answer = model.solve(item.prompt)ok, evidence = verifier.check(answer)return {"ok": ok,"evidence": evidence,"score": calculate_score(ok, evidence)}
In this workflow, scoring should not be a binary judgment. A more reasonable approach is a multi-level evaluation:
- Full pass: the conclusion is correct, the proof is complete, the counterexample is valid, and the construction is verifiable.
- Partial pass: the conclusion may be correct but the proof lacks a key step; or the construction is valid but the complexity analysis is insufficient.
- Counterexample found: unable to prove the target proposition, but successfully found a valid counterexample.
- Partial progress: provided a verifiable lemma, sub-conclusion, or problem decomposition.
- Failure: the conclusion is wrong, the proof is invalid, the result cannot be reproduced, or the constraints are violated.
This scoring approach reflects a model’s ability more faithfully, because real research is not limited to “success” and “failure.” More often, it involves “partial progress,” “proposing new paths,” or “ruling out a class of directions.”
Preventing Score-Gaming: Hidden Problems, Perturbed Problems, and Process Auditing
Research-oriented evaluation must account for data contamination and strategic score-gaming. If problems are public for a long time, models may memorize answers through training data; if problem formats are too fixed, models may learn to respond with templates.
For this reason, the evaluation set needs to be dynamic and variable.
1. Hide core problems
The evaluation set can retain public problems for calibration, but the core scoring problems should remain undisclosed to prevent models from memorizing them directly.
2. Condition perturbation
Based on the original problem, change parameters, constraints, or structure so that the model cannot rely on fixed templates. For example, alter resource limits, adjust input scale, replace with equivalent structures, or add extra constraints.
3. Random instance generation
For problems that can be generated automatically, random instances can ensure problem diversity. Randomness is not about increasing difficulty, but about reducing the space for memory matching.
4. Process auditing
Record the process of the model calling tools, retrieving external material, and citing intermediate results. If the goal is to evaluate research ability, one should not look only at the final answer, but also observe whether the model makes reasonable use of tools and whether it can verify its own intermediate conclusions.
5. Multiple independent evaluations
The same problem can be posed to a model multiple times to observe its stability. One important characteristic of research ability is maintaining consistent reasoning quality across similar problems, rather than occasionally hitting the right answer by chance.
Unresolved Open Conjectures Do Not Mean the Evaluation Is Meaningless
In research-oriented evaluations, a common conclusion is that current models still struggle to independently solve long-standing open conjectures. This result is not surprising.
Open problems remain open precisely because they usually reflect long-term research accumulation, involving complex structures, implicit assumptions, and a large body of existing tools. Even with strong reasoning ability, a model can hardly cross this historical accumulation in a short time. Real research is also not about generating an answer in one shot; it is a long process of trial and error, repeated verification, and gradual convergence.
Therefore, the value of evaluation should not be understood only as “whether a model immediately solves a hard problem.” More meaningful observations include:
- whether a model can propose new intermediate lemmas;
- whether it can construct valid counterexamples;
- whether it can decompose an open problem into verifiable subproblems;
- whether it can point out a fatal flaw in a certain proof path;
- whether it can generate enough candidate ideas for researchers to further screen;
- whether it can combine with automated verification tools to form a sustainable research-assistance workflow.
From this perspective, research-oriented evaluation is not meant to hand down a simple verdict on a model, but to help researchers understand where a model is useful, where it is unreliable, and where human intervention is needed.
Engineering Implementation: Building a Sustainable Research-Oriented Evaluation Platform
If enterprises, universities, or research institutions want to maintain research-oriented evaluation over the long term, they need to build an engineered system rather than produce a one-off exam. A fairly complete evaluation platform typically includes the following modules.
1. Problem management
Each problem should include a problem statement, metadata, difficulty tags, capability tags, constraints, a verifier, and human review criteria. Problem versions need to be managed so that evaluation results can be reproduced.
2. Sandboxed execution
Code, pseudocode, or executable proofs in model outputs need to run in isolation to prevent malicious input from affecting the system. The sandbox should limit resource usage, network access, and file permissions to keep the evaluation process safe and controllable.
3. Automated verifiers
Verifiers are the core of the evaluation system. They can check logical steps, execution state, counterexample validity, complexity constraints, or formal proof fragments. Verifiers themselves also need testing to avoid misjudgments caused by implementation errors.
4. Evidence storage
Every evaluation should save complete evidence, including the problem version, model output, execution logs, verification results, time consumption, and resource consumption. This supports not only review but also subsequent analysis.
5. Monitoring and alerting
The evaluation system needs to track task success rate, failure rate, average duration, resource peaks, verifier anomalies, and model output anomalies. Through monitoring and alerting, one can promptly detect whether the evaluation process has been contaminated or whether a systematic failure has occurred.
When building such a platform on the cloud, general cloud capabilities can be used. For example, on Baidu AI Cloud, problem metadata and evidence files can be stored in object storage, sandboxed evaluation tasks can be scheduled by a container platform, execution logs can be written to a logging service, and monitoring and alerting can track anomalous tasks. The capabilities used here are all general cloud capabilities and do not depend on any specific proprietary interface.
How to Design Evaluation Metrics
Research-oriented evaluation should not look at a single aggregate score. A more reasonable metric system should include multiple dimensions.
1. Strict pass rate
The proportion of problems a model successfully completes when all required conditions are met.
2. Partial progress rate
The proportion of cases where a model does not fully solve a problem but provides a valid lemma, counterexample, construction, or partial proof.
3. Counterexample discovery rate
Whether a model can effectively identify an incorrect proposition and provide a verifiable counterexample.
4. Verification stability
Whether a model performs consistently across similar problems, perturbed conditions, and repeated tests.
5. Proof conciseness
Under the premise of correctness, whether the model’s output contains a large amount of redundancy, repetition, or irrelevant content.
6. Tool-use rationality
If the model is allowed to call tools, evaluate whether it can correctly select tools, verify intermediate results, and correct errors.
7. Confidence calibration
Whether a model can identify where it is uncertain, rather than masking errors with fluent language.
8. Open-problem progress
Whether a model can produce new verifiable local results on long-standing open problems, rather than simply restating existing conclusions.
Together, these metrics form a more complete picture of research ability. Looking at the aggregate score alone can be misleading; multi-dimensional metrics help R&D teams judge which kinds of tasks a model is suited for and which stages still require human involvement.
Implications for Enterprises and R&D Teams
Research-oriented evaluation is also practically meaningful for enterprises. As large models move into scenarios like R&D assistance, knowledge management, code review, mathematical modeling, and algorithm design, what enterprises truly care about is no longer whether a model can answer a single question correctly, but whether it can reliably output verifiable results on complex tasks.
Enterprises can adopt the following practices:
- Use verifiable problems in place of purely subjective ones to improve evaluation objectivity;
- Separate training problems, calibration problems, and hidden evaluation problems to avoid data leakage;
- Value the process of proofs, counterexamples, and constructions, rather than looking only at the final answer;
- Establish complete logs and an evidence chain to support after-the-fact auditing;
- Incorporate human expert review into the workflow for key problems;
- Regularly update open problems and perturbed problems to keep the evaluation effective;
- Design domain-specific problems around business scenarios, rather than relying only on general leaderboards.
For enterprises that want to build an internal evaluation system, the focus is not on pursuing an authoritative-looking ranking, but on establishing a capability assessment mechanism that reflects the quality of real business tasks. The value of research-oriented evaluation lies precisely in pushing models from “answer-givers” to “verifiable work participants.”
Conclusion: From Exams to Verification, an Upgrade in Evaluation Methods
The debate over large models’ mathematical abilities is, in essence, a debate over evaluation methods. Traditional leaderboards can measure whether a model has memorized knowledge and can solve problems quickly, but they struggle to measure whether a model possesses research ability. Theoretical computer science offers a rare evaluation path: rigorous enough to be formalized, rich enough to cover concepts, construction, reduction, lower bounds, and open problems, and verifiable enough to reduce subjective judgment through automated checking.
The significance of this evaluation is not to prove that a model can do anything, but to make it clearer to the outside world where a model can assist research and where humans still need to be the gatekeepers. A truly mature evaluation system does not give a model a simple score; it establishes a reproducible, auditable, and iterable verification mechanism. For capability assessment in the era of large models, this mechanism is closer to the technical truth than any single leaderboard.
