Evaluating LLMs for Theoretical Research: Machine-Verifiable Assessment in TCS

    Large language models (LLMs) have demonstrated impressive capabilities in solving standard problems, but a significant gap remains between "solving problems" and "conducting research." This article explores the use of Theoretical Computer Science (TCS) as a high-verifiability testbed for evaluating LLM research capabilities. It discusses why TCS is well-suited for machine-verifiable evaluation, the design principles of a 100-question research benchmark covering four core research activities, and a tiered machine-assisted grading pipeline. The article also analyzes the results, revealing that while LLMs excel at retrieving existing knowledge and generating standard proof templates, they struggle with long-range proof planning and independently solving open conjectures. Finally, it provides practical insights for R&D teams to integrate verifiability into their workflows and build effective human-machine collaboration loops.

    1. From “Solving Problems” to “Conducting Research”: Shifting Evaluation Goals

    The capability evaluation of large language models (LLMs) has long focused on “solving problems”: given a clear input, output the standard answer; given a function description, generate runnable code; given a multiple-choice question, select the correct option. Such benchmarks are easy to scale, easy to grade automatically, and can quickly reflect a model’s progress in knowledge coverage, pattern matching, and short-range reasoning. However, there is an obvious gap between “solving problems” and “conducting research.”

    Problem-solving steps are usually pre-defined, and the evaluation criteria are relatively fixed; research is different. Research questions often have no pre-set solution, and sometimes no known answer. Researchers need to judge which problems are worth pursuing, which proof route is more promising, whether a counterexample truly disproves a conjecture, and whether a conclusion can be generalized to a broader scenario. More importantly, verifying the correctness of research output is highly costly: manually checking a dozens-page proof line by line takes significant time, and a model’s claim of solving a long-standing open problem cannot be judged as true merely by the fluency of its language.

    Therefore, evaluations aimed at research capabilities cannot simply follow traditional leaderboards. They must meet three conditions simultaneously: the questions should closely resemble real research activities; the answers or processes should be capable of machine-assisted verification; and the evaluation results should distinguish between “memorized recitation” and “independent reasoning.” Theoretical Computer Science (TCS) happens to provide an ideal testbed with high verifiability.

    2. Why Theoretical Computer Science is an Ideal Testbed for Research Capabilities

    Theoretical Computer Science studies “computation” itself: how many resources are required to solve a problem, which problems are undecidable in principle, how different computational models reduce to each other, and what connections exist between proofs and algorithms. It does not focus on how specific software is deployed or how a piece of code is optimized; rather, it cares about the boundaries, complexity, and possibilities of computational problems.

    This gives TCS two characteristics suitable for evaluation.

    First, many conclusions can be expressed formally. Whether a proof holds can be translated into a series of logical deduction steps; whether a counterexample is valid can be checked through construction and verification; whether an algorithm is correct can be reviewed via invariants, termination, and complexity analysis. Compared to open-ended natural language discourse, TCS problems are much easier to design into a “machine-gradable” format.

    Second, the research activities covered by TCS are sufficiently diverse. It includes definition comprehension and theorem reproduction, as well as proof completion, counterexample construction, reduction design, complexity analysis, and open problem exploration. A model that only memorizes common conclusions might score well on knowledge questions, but its shortcomings will quickly be exposed when facing tasks requiring cross-definition reorganization, constructing new counterexamples, or completing long-range proofs.

    It should be emphasized that TCS evaluation does not equate to “testing the entirety of mathematical research with a single exam.” Machine-gradable questions inherently favor formal, constructive, and verifiable subsets, which may underestimate abilities that are difficult to measure automatically, such as research taste, problem selection, and value judgment. Its value lies in providing a relatively objective slice, not replacing comprehensive academic evaluation.

    3. 100 Questions, Four Activity Types: Benchmark Design for Real-World Research

    According to public descriptions, this evaluation set contains 100 questions organized by four categories of research activities. While specific question types should be based on the paper’s official explanation, from an evaluation design perspective, the core purpose of dividing into four categories is not to increase the volume of questions, but to cover the different stages of a theoretical computer scientist’s daily work.

    A reasonable research-oriented benchmark usually needs to follow these design principles:

    1. Answers must be verifiable, but the process cannot be templated
      Questions cannot only require the final conclusion; otherwise, models might score by guessing the answer or retrieving memories. Proof questions should require checkable derivation chains; counterexample questions should require constructing instances that satisfy the constraints; reduction questions should require explaining the mapping relationship and correctness conditions.

    2. Difficulty stratification to avoid focusing entirely on memory-based knowledge
      Basic questions can check definition comprehension and common theorem reproduction; intermediate questions require cross-chapter combination; advanced questions should resemble real research fragments, such as completing a non-trivial proof, discovering the boundary conditions of a construction, or judging whether several candidate directions for an open problem are self-consistent.

    3. Anti-contamination and anti-leakage
      If a research benchmark makes all questions public, they can easily enter subsequent training data. The design should retain hold-out sets, dynamic variants, or parameterized questions to prevent models from scoring through memorization rather than reasoning. Evaluation reports should also distinguish between “closed-book” and “retrieval-allowed” settings.

    4. Open questions should be labeled separately
      Open conjectures have no known answers and cannot be simply graded as right or wrong by an automatic grader. For such questions, a more reasonable evaluation goal is to check whether the model can propose verifiable intermediate lemmas, provide the boundaries of known results, and identify proof gaps, rather than claiming to have “independently solved” them.

    5. The grader itself needs auditing
      Automatic grading is not a stamp of exemption from inspection. Whether the formal specifications are accurate, whether the checker has vulnerabilities, and whether the model output is parsed correctly will all affect the conclusion. A responsible benchmark should disclose the grading process, error rate, and the proportion of manual review.

    4. Machine Grading Pipeline: Reducing Review Costs Without Eliminating Human Judgment

    The hardest part of research evaluation is not getting the model to answer, but grading the answers. A tiered, machine-assisted grading pipeline can be designed as follows:

    1. Input: Question item, model output
    2. 1. Parse output: Extract theorem statements, proof steps, constructed instances, complexity claims
    3. 2. Specification matching: Map the output to the predefined formal specifications or executable constraints of the question
    4. 3. Branch grading:
    5. - Proof questions: Invoke the proof checking process to verify whether each deduction step satisfies the rules
    6. - Counterexample questions: Execute or perform constraint verification to check if the construction satisfies all conditions
    7. - Reduction questions: Check the mapping function, parameter relationships, and correctness conditions
    8. - Open questions: Extract verifiable intermediate conclusions, transfer to manual review
    9. 4. Consistency check: Verify if the conclusion is consistent with the proof and whether there are undeclared assumptions
    10. 5. Audit record: Save parsing results, check logs, failure reasons, and manual review opinions
    11. 6. Output: Pass / Fail / Partial Pass / Needs Manual Review

    The key to this pipeline is not being “fully automated,” but “auditable.” For proof questions, the automatic checker can quickly discover logical leaps and illegal steps; for counterexample questions, executable verification prevents the model from being vague in natural language; for open questions, the machine can only assist in extracting verifiable fragments, and domain experts are still needed to ultimately judge their research value.

    At the same time, three types of errors must be guarded against: a grader that is too strict will judge correct but differently expressed proofs as wrong; a grader that is too loose will allow the model to learn to “trick the checker”; specification errors may invalidate the evaluation of the entire question. Therefore, a research benchmark should treat “grader quality” as part of the benchmark’s quality, rather than hiding it in an appendix.

    5. Interpreting Results: What the Lack of Independent Solutions for Open Conjectures Means

    One of the most noteworthy conclusions from such evaluations is that, when faced with unresolved open conjectures, no reference model was able to provide an acceptable solution entirely relying on its own capabilities. This conclusion should not be simply interpreted as “models have no value,” but should be broken down into a capability profile.

    The parts where models are strong usually include: retrieving and reorganizing existing knowledge, generating common proof templates, converting natural language conclusions into formal drafts, proposing candidate lemmas in short-range reasoning, and assisting in searching for counterexamples. The parts where models are weak are concentrated in: long-range proof planning, definition innovation, credible screening of cross-domain analogies, discovering circular reasoning in their own proofs, judging whether an open problem is worth continued investment, and maintaining consistency in multi-step reasoning without external feedback.

    This aligns with the difference between “solving problems” and “conducting research.” Exam questions have boundaries, while research questions do not; errors in exam questions are usually locally visible, while errors in research may be hidden in definition choices or overall routes. Models can significantly reduce the cost of proof drafting and formal verification, but “independently conquering open conjectures” requires more than language generation—it requires a continuous, auditable, and self-correcting research process.

    For developers, this means the more realistic goal is not to have models replace researchers, but to build a collaborative loop of “humans proposing questions and routes, models generating candidate proofs and counterexamples, machine checkers providing rapid feedback, and humans judging value and direction.”

    6. Practical Insights for R&D Teams: Prioritizing Verifiability

    If a team wants to use LLMs to assist in mathematical, algorithmic, or theoretical research, they can start with the following practices:

    • Define verifiable specifications first: Before letting the model generate a proof or algorithm, clearly write down the inputs, outputs, constraints, and correctness conditions. The clearer the specification, the more reliable the subsequent grading.
    • Establish a tiered evaluation set: Track knowledge reproduction, proof completion, counterexample construction, and open problem exploration separately to avoid having a single total score mask the capability structure.
    • Retain a manual review channel: Automatic grading is responsible for high-throughput screening, while manual review handles open problems and edge cases; both are indispensable.
    • Record failure modes: Record not only the pass rate, but also failure types such as circular reasoning, undeclared assumptions, constructions failing to meet constraints, and incorrect complexity claims.
    • Prevent benchmark contamination: Apply variant processing to public questions, retain internal hold-out sets, and periodically update question parameters.
    • Integrate formal checking into the workflow: Directing model outputs into an executable constraint or proof checking process before human reading can significantly reduce review costs.

    7. Conclusion: Verifiable Research Benchmarks as a Necessary Reality Check

    The progress of large models in mathematical and coding tasks is worth taking seriously, but evaluation oriented towards Theoretical Computer Science provides a necessary “reality check”: models can become research assistance tools, but they have not yet proven themselves capable of independently conducting open research. Machine-gradable TCS benchmarks are not meant to negate model capabilities, but to break down “research ability” into observable, verifiable, and auditable stages.

    For academia and industry, a more valuable direction is to continue building high-quality, anti-contamination, and auditable research benchmarks, and to design the human-machine collaboration process into a closed loop of “generate—check—review—iterate.” The reason mathematics and theoretical computer science are ideal testbeds is precisely because they have strict requirements for correctness; and strict verifiability is exactly the scarcest yardstick for evaluating intelligent research capabilities.