Theoretical Computer Science: A Litmus Test for LLM Research Capability

    LLM benchmark scores keep rising, but high scores do not automatically translate into research capability. This article explains why most benchmarks measure pattern matching on questions with known answers rather than the ability to explore unknowns, construct proofs, and judge success or failure. It then argues that theoretical computer science (TCS) is a rare field that combines research-level difficulty with machine-verifiable answers, and walks through a machine-scorable evaluation skeleton, interface requirements for verifiers, four core categories of TCS work, a concrete sample evaluation result on open-conjecture problems, and an eight-point checklist for building credible next-generation LLM evaluations.

    1. Why High Benchmark Scores Don’t Equal Research Capability

    Every couple of months, the leaderboards get refreshed and the numbers climb at a pace that’s hard to follow. If you ask why a high leaderboard score is not the same as research capability, the answer isn’t complicated: most benchmarks measure whether a model can quickly produce the correct answer to questions that have known answers, bounded solution paths, and clearly defined goals. Research capability requires something different — exploring on your own, constructing proofs, and judging success or failure when the answer is unknown, the path is undecided, and even the evaluation criteria are not fully clear.

    The root of the problem is the evaluation method itself. Most benchmarks consist of standard answers and fixed solution procedures, and their questions resemble exams: the prompt is explicit, the goal is clear, and the solution path is unique or limited. This design has two structural flaws:

    • Data contamination: Questions and answers are easily seen by a model during training, so a high score may reflect memorization rather than reasoning.
    • Capability-level mismatch: A model that passes standardized questions demonstrates pattern matching and problem-solving fluency, not the research literacy of exploring unknowns, constructing proofs, and judging success or failure.

    In other words, leaderboards measure “how well a model performs on questions whose answers are already known,” while the core of research is precisely “moving forward on questions where nobody knows the answer.” If the benchmark items are contaminated, the answers are memorizable, and scoring only looks at the final answer, then a high score does not extrapolate into research capability.

    2. Why Research Is Hard to Evaluate: Scoring and Boundaries

    If you want an evaluation to genuinely resemble research, you have to face one reality: research has no prescribed steps, nobody can say in advance whether it will succeed, and even the person who poses the problem may not hold the answer. This creates the fundamental difficulty of evaluation — scoring.

    The more a question resembles real research, the more open the answer becomes and the harder it is to define an objective right-or-wrong standard. Having human experts review each submission one by one is not only expensive but also introduces subjectivity and consistency problems.

    One point deserves special emphasis: if an open-ended question has no known answer or no verifiable target, it can only go into human review or exploratory evaluation, and cannot be sent directly into an automated machine-scoring pipeline. Put differently, machine scoring suits questions with clearly verifiable targets; for open-ended questions where there is nothing for a machine to check, evaluation can only fall back on expert review, case comparison, or exploratory assessment — it cannot masquerade as objective automated scoring.

    This is also why “AI doing mathematics” and theoretical computer science are often seen as promising directions: many mathematical and theoretical results can be mechanically verified for correctness. But not all research tasks can be scored automatically — scoring capability sets the ceiling on what an evaluation can achieve.

    3. Why TCS Works as a Litmus Test

    Theoretical computer science (TCS) happens to be one of the few fields that satisfies both “research-level difficulty” and “machine-scorable” at the same time. Its results can mostly be formalized and checked for correctness by automated verifiers or proof assistants.

    An intuitive analogy: it’s a bit like Sudoku — filling in a legal solution is hard, but once a solution is filled in, checking whether it is correct is relatively easy. To be more precise, though, this is a discussion of the “hard to solve, easy to verify” structure in the context of computational complexity theory / complexity analysis, not a generalization about computability theory. Sudoku belongs to the class of NP-complete problems; it is used here only to illustrate that verification is easy while solving is hard, and it is not equivalent to all research tasks.

    In complexity analysis, finding a solution may require exponential search, while verifying a given solution usually takes only polynomial time. It is precisely this complexity gap between verification and solving that lets TCS build evaluations that stay close to frontier research while remaining objectively scorable. That makes it a natural litmus test for whether a large model has genuine research capability.

    4. What TCS Researchers Actually Do: Four Core Work Types

    The daily work of a theoretical computer scientist can be grouped into four categories. They correspond to different intellectual activities and are also suited to being designed as different evaluation sections:

    Work type Output Verification method Typical evaluation section
    Construct algorithms and prove upper bounds Algorithm description, proof Formal proof, complexity accounting Algorithm construction, complexity upper bound
    Prove lower bounds and impossibility Proof, counterexample, or reduction Proof checking, counterexample verification Lower bound proof, infeasibility
    Construct reductions and establish connections Reduction mapping, relation graph Reduction correctness check Problem equivalence, structural connections
    Advance open conjectures New proofs, partial results Human review or formal verification Open conjecture exploration

    A well-designed TCS evaluation typically splits its questions into sections corresponding to these four work types, covering the full spectrum of abilities a researcher needs rather than testing a single dimension of problem-solving skill. Such an evaluation is closer to the research process than a traditional “solve-the-problem” test, because it does not only look at whether the model produced an answer — it also looks at whether the model can construct objects, give proofs, state limiting conditions, and explain why a certain line of attack cannot work.

    5. A Machine-Scorable Evaluation Skeleton

    Turning this idea into an evaluation system comes down to designing the “answer” as an object that can be automatically verified. Before the verifier pseudocode, the interface constraints need to be made explicit:

    • The verifier must return passed, reason, and trace: not just a score, but also why it failed and the verification trace.
    • Algorithm questions must specify time/memory limits and a timeout policy: a correct algorithm does not mean resource consumption is within budget, so complexity must be accounted for separately.
    • Proof questions must specify the proof assistant and format version: for example Lean, Coq, Isabelle, or a project-internal formalization format — the version must be pinned to avoid drift in what counts as verified.

    Illustrative pseudocode:

    1. def evaluate_model_answer(problem, model_output):
    2. """
    3. problem: problem statement, I/O constraints, verification interface
    4. model_output: the model's answer (proof steps / algorithm / construction)
    5. """
    6. # 1. Schema check: does the answer match the format the problem requires?
    7. if not problem.schema.validate(model_output):
    8. return {"passed": False, "reason": "invalid format", "trace": []}
    9. # 2. Automated verification: call the formal verifier or checker
    10. verification = problem.verifier.check(model_output)
    11. trace = verification.trace
    12. # 3. Resource accounting: for algorithm questions, also check complexity bounds
    13. if problem.type == "algorithm":
    14. complexity_ok = problem.bound_check(model_output)
    15. verification.passed = verification.passed and complexity_ok
    16. trace.append({"bound_check": complexity_ok})
    17. return {
    18. "passed": verification.passed,
    19. "reason": verification.reason,
    20. "trace": trace
    21. }

    Three design points matter for this skeleton: answers must be parseable by a program, correctness must be decided by a verifier rather than by a human, and additional constraints such as complexity need separate accounting. Together they guarantee the objectivity and reproducibility of evaluation results.

    But a warning is also in order: the verifier itself can be flawed. Formal systems, proof checkers, and complexity estimators can all be affected by implementation bugs, version differences, or edge cases. In formal evaluations, it is therefore advisable to add two-person spot checks, random re-review, formal proof checking, and post-mortems on anomalous samples to reduce the risk of a single point of verification failure.

    6. Key Observation: Models Solve Problems, Not Open Conjectures

    Based on rigorously designed evaluations like these, you can observe a somewhat cold-water-dumping phenomenon. It should be stressed that the following conclusions apply only to a specific evaluation scope and should not be generalized into an absolute judgment about all models, all time periods, or all tasks.

    In one illustrative evaluation, it can be stated as follows: among the publicly available reference models covered by this evaluation, none of the tested samples independently solved the open-conjecture questions. The model list for this sample evaluation was: general-purpose reasoning model A, general-purpose reasoning model B, math reasoning model C, and code-proof model D. The evaluation ran from January 1, 2025 to March 31, 2025. A total of 24 newly constructed open-conjecture-related questions were used, each sampled 5 times per model, for 480 samples in total. The result describes that sample only and is not generalized to all models.

    Even so, this result carries an important signal:

    • Frontier models perform excellently on standard questions and even quite difficult ones, which shows they have already absorbed a great deal of existing problem-solving paradigms and proof techniques.
    • But once they face genuinely open, research-level problems with no known answer or only partial verifiability, they may still be unable to autonomously complete the full chain from “exploring a direction” to “constructing a complete proof.”
    • The gap between “solving problems” and “doing research” can be quantified more clearly by this kind of verifiable evaluation.

    7. How to Build a Credible Evaluation: An Executable Checklist

    From the design philosophy of TCS evaluations, we can extract general principles for building the next generation of large-model evaluations. To avoid stopping at slogans, here is a more executable checklist:

    1. Private, new question bank: use unpublished questions to reduce the probability that a model can directly recall the answer.
    2. Question perturbation: apply controlled perturbations to the prompt, parameters, and constraints to generate new questions that are related but have different answers.
    3. Hash-based deduplication: hash and compare questions, answers, and prompts to prevent duplicate questions from leaking into the training set or the evaluation set.
    4. Versioning: put questions, answers, verifiers, proof assistants, and complexity limits under version control.
    5. Independent verifier re-review: have an independent team or two-person spot check re-review key questions to avoid a single point of failure in the verifier.
    6. Difficulty calibration: calibrate difficulty using historical models, human experts, or baseline methods to avoid questions that are too easy or too hard.
    7. Confidence intervals on pass rates: when reporting results, give sample size, pass rate, and confidence intervals — don’t speak with a single point score alone.
    8. Separate capability levels: don’t just look at whether the answer is right; also look at whether it comes with a verifiable proof, whether algorithm complexity meets the bound, and whether edge cases are handled.

    In practice, large-scale evaluation usually requires sufficient compute scheduling, version management for questions and verifiers, and traceable evaluation logs. With general-purpose cloud capabilities — for example, containerized platforms to run evaluation jobs, object storage to archive questions and results, message queues to decouple scheduling, and logging plus monitoring and alerting services to track the evaluation process — a team can make the evaluation pipeline both stable and reproducible. This kind of infrastructure-driven approach is vendor-neutral and is a general pattern used across the industry for building serious evaluation systems.

    8. Extended Q&A: How to Resist Contamination? How to Tell Whether a Question Is Research-Level?

    How do you prevent question contamination?

    You can use a private question bank, question perturbation, hash-based deduplication, blind review of answers, periodic question rotation, prompt perturbation, and training-set screening. If a question has appeared on the public internet, its weight should be lowered, or it should be used only for regression testing rather than as a core measure of research capability.

    How do you tell whether a question is research-level?

    Look at whether it meets several conditions: does it have a clearly verifiable target; does it require constructing new objects, proofs, or reductions; does it have no off-the-shelf standard solution; and does it distinguish “can imitate existing methods” from “can advance a new problem”? If a question only requires applying a known template, then even if it looks complex, it is not necessarily a research-level question.

    Can machine scoring produce false judgments?

    Yes. A verifier may miss edge cases, a formal proof may depend on the version, and an algorithm complexity check may be affected by the runtime environment. That is why key conclusions should retain the trace, the reason, and human spot-check records.

    How should evaluation results be reported?

    It is advisable to report the model list, the evaluation period, the source of the questions, the sample size, the verifier version, failed samples, the pass rate, and confidence intervals. Giving only a single aggregate score hides the real capability boundary.

    Conclusion

    The verifiability of theoretical computer science makes it a scarce yardstick for testing the real research capability of large models. It makes something clear: models often perform excellently in the sea of questions with known answers, yet they have not necessarily entered the hall of research where the unknown is explored. For evaluators, what matters is not pushing one more leaderboard score, but seeing the boundary clearly — which abilities come from memory and templates, and which come from genuine research reasoning; which evaluations can be scored automatically, and which can only be reviewed by humans; which conclusions are bounded by sample and time, and which cannot be over-extrapolated. Seeing that boundary clearly is more valuable than refreshing any leaderboard score.