Evaluating LLM Research Capability: How to Choose Theoretical Computer Science Benchmarks

    Benchmark scores do not automatically prove that a large language model can conduct research. This article explains why theoretical computer science provides a useful evaluation setting, which task types to use, how to design verifiable scoring, and what limits teams should place on their conclusions.

    Conclusion first: benchmark scores cannot be treated as equivalent to research capability. To judge whether a large language model has research potential, we should not rely only on scores from multiple-choice questions, fill-in-the-blank questions, or closed-ended questions. Instead, the model should be placed in research-like tasks that are verifiable, traceable, and reproducible. Theoretical computer science provides a suitable reference framework: it tests whether a model can handle open-ended reasoning tasks while keeping conclusions checkable through mathematical derivation, formal verification, or expert review.

    This article is written for technical teams and researchers. It focuses on three questions:

    1. Why theoretical computer science is suitable for evaluating research capability.
    2. How evaluation tasks should be designed.
    3. How teams can build an executable judgment checklist.

    A special note: this article is based on second-hand material that cannot be fully verified. It does not fabricate specific paper titles, IDs, or links. Before formal citation, the original source information should be completed.

    1. Why Rising Benchmark Scores Do Not Directly Represent Research Capability

    When large language models achieve new benchmark results, technical teams and researchers often ask: does the model already have research capability? Answering this question requires more than looking at scores from multiple-choice, fill-in-the-blank, or closed-ended questions. It requires placing the model in tasks that are closer to real research workflows.

    Benchmark scores usually depend on fixed questions, fixed prompts, and fixed scoring scripts. They mainly measure a model’s ability to match, retrieve, complete, and derive answers within a specific question format. Real research, however, often has no preset answer, and sometimes not even a preset question.

    Researchers need to judge what is worth studying, where boundary conditions lie, whether a proof holds, whether a method is reproducible, and whether a conclusion can be reviewed by peers. Therefore, “being good at solving problems” is part of research capability, but it is not sufficient for research capability.

    These differences can be summarized in three layers.

    First, problem source. Benchmark questions are usually already given. Research questions must be discovered from context, gaps, and counterexamples.

    Second, evaluation criteria. Benchmark questions can be scored with standard answers or automatic matching. Research conclusions require proof checking, formal verification, expert review, and reproduction experiments.

    Third, risk control. Benchmarks focus on whether the answer is correct. Research focuses more on where errors may occur and whether an error can cause the entire conclusion to collapse.

    Therefore, if benchmark scores alone are used to judge AI research potential, it is easy to mistake “question-type proficiency” for “research ability.”

    2. Why Theoretical Computer Science Is Suitable for Testing Research Capability

    Theoretical computer science lies at the intersection of mathematics and computer science. Its core questions are usually centered on “computation” itself: how quickly can a problem theoretically be solved? Is a certain path inherently impossible? What are the upper and lower bounds of an algorithm? Under a given computational model, is the problem tractable, hard, or unsolvable?

    Unlike applied engineering practice, this field mainly relies on rigorous mathematical proofs to advance.

    An analogy may help. Software engineers are more like drivers. They care about engine performance, route selection, driving strategy, and vehicle stability. Theoretical computer science studies “traffic” itself: how far one can theoretically travel in the shortest time, and which routes are logically impossible. The former focuses on implementation; the latter focuses on possibility and limits.

    Theoretical computer science is relatively suitable for evaluating research capability because it combines openness with verifiability. The closer a task is to real research, the harder it is to score. However, conclusions in this field can usually be verified through mathematical derivation, formal checking, or expert review.

    In other words, it is one of the few fields that is relatively hard to design but relatively easier to grade objectively. This property makes it a useful setting for simulating research openness while reducing scoring subjectivity.

    To understand the technical concepts, we can add a few basic definitions.

    Asymptotic complexity describes how algorithm running time or space usage grows as input size increases. For example, O(n log n) indicates an asymptotic upper bound on running time. If tight order is required, Θ(n log n) should be used.

    Worst-case analysis focuses on the worst behavior an algorithm may encounter on any valid input. Average-case analysis focuses on expected behavior under a certain input distribution or random model.

    Formal verification refers to expressing proofs or constraints as specifications that can be checked mechanically, then verifying correctness step by step with proof assistants, proof checkers, or formal tools.

    These concepts make the question “Can AI solve research-level problems?” less subjective and more connected to checkable technical objects.

    3. Which Four Task Types Should Be Evaluated?

    In such evaluations, four task types are especially important: theorem proving, counterexample construction, complexity analysis, and rigor review.

    Theorem Proving

    Given a proposition, the model needs to construct a rigorous derivation chain and prove that it holds. The key is not whether the conclusion seems reasonable, but whether each step is valid, whether it relies on unproved assumptions, and whether necessary premises are omitted.

    For example, if the model is asked to prove that a sorting algorithm has an O(n log n) upper bound in the worst case, it needs to provide recurrence relations, reduction ideas, master theorem or recursion tree analysis, and explain boundary conditions.

    In real research, theorem proving usually does not mean reverse-engineering a persuasive explanation from the conclusion. It means starting from known axioms, definitions, and existing theorems to form a checkable argument.

    Counterexample Construction

    For a conjecture or proposition, the model needs to construct a concrete instance that makes it fail. The more specific and reproducible the counterexample is, the better it reflects the model’s grasp of boundary conditions.

    For example, if a proposition claims that “linear time is maintained for all input sizes,” the model needs to provide an instance that clearly violates linear time at a larger scale or under a specific distribution, and explain why it fails.

    A high-quality counterexample should not only show that “the proposition is false.” It should also explain under which assumption the proposition fails, why it fails, and whether it reveals a deeper issue.

    Complexity Analysis

    The model needs to provide an upper bound or lower bound for an algorithm or problem, such as “how fast it can be at most” or “how slow it must be at least.”

    This task requires the model to distinguish asymptotic complexity, worst-case behavior, average-case behavior, and specific model assumptions. If a model only outputs a big-O notation but cannot explain the reduction target, recurrence relations, or lower-bound argument, its complexity analysis ability is still insufficient.

    Rigor Review

    The model needs to review existing proofs, identify logical gaps, erroneous steps, or missing boundary cases.

    This task is close to peer review in real research and places high demands on long-chain reasoning.

    Rigor review in research is not simply finding typos. It means judging whether the reasoning chain relies on unproved assumptions at critical nodes, whether sufficient and necessary conditions are confused, and whether the scope of a conclusion is incorrectly extended.

    The common feature of these four task types is that the process depends on creative thinking, while the results can be checked through mathematical methods. This makes evaluation close to research openness while preserving the possibility of objective scoring.

    4. How to Design Evaluation: From Tasks to Scoring

    Theoretical computer science evaluations usually revolve around researchers’ daily tasks. Because this article cannot verify the specific number of questions, difficulty distribution, model versions, or reasoning budgets in the original material, it does not provide unconfirmed numerical details. Readers who cite question counts, difficulty tiers, or model performance should rely on the original paper’s appendix tables or public evaluation reports. When evidence is missing, the boundary should be preserved as “no specific number is given.”

    A rigorous evaluation design should include at least the following elements.

    1. Problem Source and Difficulty Tiers

    Questions may come from adapted public research problems, private questions, open conjecture-related questions, or variant reasoning tasks.

    Difficulty should be tiered. For example, distinguish “tasks with known answers,” “variant reasoning tasks,” and “open problem tasks.”

    Different difficulty levels should not be mixed into one vague total score. They should be reported separately with success rates, failure types, and review costs.

    2. Model Scope and Versions

    The evaluation should clearly state which models are involved, which versions are used, what reasoning budget is provided, whether the environment is connected to the internet, and whether tool calls or code execution are allowed.

    This article does not cite specific model versions or specific model conclusions. To judge the performance of a particular version, readers should refer to the original evaluation appendix and experiment records.

    3. Prompts and Number of Attempts

    Prompts, maximum reasoning steps, token budgets, and sampling conditions should be unified.

    Open-ended tasks may allow multiple draft attempts, but the final submission should be treated as one independent response. Human assistance, toolchain results, or external retrieval results should not be mistakenly counted as the model’s own capability.

    4. Scoring Method

    Verifiable tasks can use proof checkers, formal verifiers, test cases, or scripts. Tasks that require semantic judgment should be reviewed by domain experts.

    Scoring should distinguish full pass, partial pass, and failure, rather than giving only a single score.

    Partial pass is especially important because research proofs often involve cases such as “the direction is correct but boundary conditions are missing” or “the counterexample is valid but the argument is incomplete.”

    5. Verifiable Examples

    If a task asks the model to prove that an algorithm has an O(n log n) upper bound, the model needs to provide a reduction, recurrence relations, master theorem, or amortized analysis. The verifier needs to check mathematical steps, boundary conditions, and assumptions.

    If a task asks the model to construct a counterexample, the model must provide a concrete instance and prove that it indeed breaks the original proposition. Abstract statements alone should not count as valid answers.

    To make evaluation easier to implement, the following minimal evaluation template can be used.

    Field Requirement Example
    Task ID Unique ID for each question, for tracking TCS-001
    Problem Source Adapted, private, open conjecture, or variant Adapted from a textbook exercise, with memorization risk removed
    Model Version Model name, version, context length Example Model-v1, 128k context
    Prompt Full prompt or prompt template ID prompt-001: requires proof steps and boundary conditions
    Reasoning Budget Maximum steps, token budget, sampling count Maximum 4096 tokens, 3 samples, select best
    Scorer Automatic checker or expert scoring rule Script check + expert review of proof completeness
    Partial Pass Criterion How to score when direction is correct but steps are missing Correct proof direction but missing boundary: 1 point
    Reviewer Review role or ID Reviewer A, theoretical computer science track
    Failure Type Record failure reason for later analysis Unproved assumption, missing boundary conditions

    5. Source Verification and Citation Boundaries

    This article does not fabricate paper titles, IDs, or links. Because the original material has incomplete or anonymized information about institutions and papers, the current content can only be treated as second-hand paraphrase and requires verification.

    If readers need to cite this topic, they should rely on original literature that can be found in public preprint platforms or academic databases. For example, readers may try searching public preprint platforms for papers related to “Theoretical Computer Science benchmark large language models.”

    Accessible summary: this article is a second-hand paraphrase and does not provide specific paper titles, authors, institutions, preprint IDs, or links. Before formal citation, the following should be completed: original title, author or institution, preprint ID or link, publication time, access date, conclusion excerpt, and applicable conditions. If this cannot be completed, it should be clearly marked as “second-hand paraphrase, pending verification.”

    To avoid misleading readers through second-hand paraphrase, a source verification checklist is recommended.

    Verification Field Verification Question
    Original Title Does it match the actual paper title?
    Authors and Institutions Are they traceable? Is there anonymization or incorrect attribution?
    ID or Link Is there a stable identifier such as arXiv or DOI?
    Access Date Is the verification time recorded to avoid bias from version updates?
    Conclusion Excerpt Does it only paraphrase conclusions explicitly stated in the original text, rather than extended inference?
    Applicable Conditions Are test sets, model versions, reasoning budgets, and prompt conditions specified?
    Second-hand Paraphrase Mark If original information cannot be completed, is it marked as “second-hand paraphrase, pending verification”?

    This kind of verification is not formalism. For research capability evaluation, any conclusion that cannot be traced back to original material may be misread as “all models have completed a certain type of research task,” leading to biased technical selection or research judgment.

    6. Core Findings and Boundaries: Do Not Extrapolate One Performance into a Permanent Conclusion

    According to second-hand material that cannot be fully verified, under specific test conditions, the evaluated model versions did not independently solve the open conjecture tasks in the evaluation.

    This conclusion needs strict limitations. It cannot be understood as “all models can never solve open problems.” It also cannot be understood as “future versions will inevitably fail.” It reflects performance under a specific test set, specific model versions, and specific evaluation conditions.

    This result indicates at least two points.

    First, it distinguishes between “solving tasks with known answers” and “exploring questions with unknown answers.” The former is closer to pattern matching, training optimization, and question-type proficiency. The latter is closer to the essence of research: genuine exploration when no one knows the answer. A model may be able to complete steps within an existing proof framework, but it may not independently propose an entirely new proof route.

    Second, it suggests that current large language models still have shortcomings in long-chain, multi-step, rigorous reasoning. Research-level proofs often require crossing multiple levels of abstraction. A subtle logical break at any point can invalidate the conclusion. A model may present a seemingly complete derivation while introducing unproved assumptions, confusing complexity conditions, or missing boundary cases midway.

    The following table can help understand the differences between two task types.

    Task Type Scoring Method Main Risks Suitable Judgment
    Known-answer tasks Standard answers, automatic verification, or matching score Training data leakage, pattern matching, question-type overfitting Quickly screening basic model capability
    Open problem tasks Proof checking, counterexample verification, expert review False proofs, boundary omissions, irreproducibility Testing real research potential, requires human-AI collaboration

    Therefore, the fact that an open conjecture was not independently solved does not mean the model has no value. It means that at the current stage, a more reasonable use is not to let the model independently make research conclusions. Instead, the model can be used for draft generation, counterexample attempts, flaw detection, and formalization assistance. Human researchers should still take responsibility for problem definition, key judgment, conclusion review, and reproduction verification.

    7. From Leaderboard Chasing to Real Research: Executable Checklist and Scorecard

    The greater value of this work is not just providing one evaluation result. It provides a shift in evaluation paradigm: moving from “leaderboard-style capability measurement” to “real research capability testing.”

    For technical teams and researchers, the following checklist can be used.

    1. Task Verifiability

    Does each task have a machine-checkable scoring standard, or a clear human expert review rule? If the task conclusion cannot be verified, it should not be simply used to judge research capability.

    2. Difficulty Tiers

    Does the evaluation distinguish known-answer questions, adapted variant questions, and open problem questions? Are success rates calculated separately instead of mixing everything into one total score? Difficulty tiers prevent low-difficulty high scores from masking weaknesses in open tasks.

    3. Sample Size and Evaluation Conditions

    Does the evaluation report the number of questions, difficulty distribution, number of models, model versions, number of attempts, reasoning budget, prompts, and failure counts?

    This article does not provide unverified specific question counts or model counts. If readers need to cite them, they should refer to the original appendix.

    4. Human Review

    Are expert review, reproduction processes, and dispute resolution mechanisms established for high-risk conclusions? This is especially important when involving proof validity, counterexample correctness, and complexity lower bounds.

    5. Failure Case Archiving

    Does the evaluation record failure types, such as logical breaks, missing assumptions, complexity confusion, incorrect counterexamples, and irreproducible proofs? Failure samples and evaluation scripts should also be retained.

    Recommended archive template fields include: failure type, task ID, model output, erroneous step, reviewer, reproduction script, and disposition conclusion.

    6. Source Verification

    Any evaluation result cited for external publication or internal decision-making should retain the original title, authors, ID, link, access date, conclusion excerpt, and applicable conditions. If the original material is anonymized or missing, it should be marked as “second-hand paraphrase, pending verification.”

    To facilitate internal team review, a simple scorecard can be added. Each item is scored from 0 to 2.

    Review Item 0 Points 1 Point 2 Points
    Task verifiability Conclusion cannot be verified Requires substantial human explanation Can be reliably reviewed by machine or expert
    Difficulty tiers All questions mixed into one total score Difficulty labels exist but no tiered statistics Success rates and failure types are tiered
    Evaluation condition disclosure Model, prompt, or budget missing Partial disclosure but incomplete Key conditions complete and traceable
    Scoring reproducibility No script or no review Script exists but is hard to reproduce Scripts, examples, and review records are complete
    Human review No review mechanism Sampling review only Mandatory review for high-risk conclusions
    Failure archiving Only total score recorded Failure count recorded but not classified Failure types, samples, and disposition are complete
    Source verification No source fields Links exist but applicable conditions missing Source fields complete and boundaries marked

    This scorecard can help teams avoid directly equating “high score” with “research capability.” Instead, evaluation results can be transformed into engineering and research evidence that can be discussed, reproduced, and improved.

    8. FAQs: How to Judge Whether a Large Language Model Has Research Potential?

    How can large language model research capability be evaluated?

    Research capability can be evaluated from four dimensions: task verifiability, openness, reasoning chain length, and failure types. Scores from closed-ended questions, objective questions, or multiple-choice questions alone are not enough to demonstrate research capability. The ability to construct proofs, discover counterexamples, and review flaws is closer to research tasks.

    Why can benchmark scores not represent research capability?

    Because benchmark scores often measure performance on known question types, while research requires handling unknown problems, boundary conditions, method selection, and result verification. The two differ in goals, scoring, and risk control. High benchmark scores may mean the model is good at test-taking, but not that it can independently propose research questions or support rigorous conclusions.

    How can verifiable tasks be selected?

    Prefer tasks whose conclusions can be reviewed by machines or experts, such as theorem proving, complexity analysis, counterexample construction, and proof review. Difficulty tiers should also be set to avoid mixing all questions together, which can distort interpretation.

    How should theoretical computer science evaluation questions be selected?

    They can be selected from four task types: proving known propositions, constructing counterexamples, analyzing complexity upper or lower bounds, and reviewing logical flaws in existing proofs. When selecting questions, also consider whether the question is public, whether training data leakage is possible, whether formal tools are required, and whether partial pass criteria can be set.

    How should failure cases be archived?

    Recommended fields include failure type, task ID, model output, erroneous step, reviewer, reproduction script, and disposition conclusion. When archiving, do not retain only the final score. Retain the key intermediate steps that led to failure so that model weaknesses can be analyzed later.

    What are common misuses of theoretical computer science evaluations?

    Common misuses include:

    1. Treating performance on training sets or public questions as open research capability.
    2. Using a single result instead of a stable conclusion.
    3. Looking only at total score and not failure types.
    4. Mistakenly counting tool-assisted results as the model’s own capability.
    5. Ignoring contamination risk after questions become public.
    6. Extrapolating performance under a specific version and specific prompts into a permanent conclusion for all models or future models.

    Conclusion

    As large language model benchmark scores continue to rise, theoretical computer science evaluation provides a calm reference framework. It acknowledges AI’s continued progress on verifiable tasks while clearly marking the distance to open research exploration.

    For developers and research teams that hope to use AI in rigorous technical work, understanding the gap between “doing problems” and “doing research,” and understanding the fundamental importance of verifiability, is more valuable than chasing any specific leaderboard score.

    A more robust path is not to let AI independently announce conclusions. Instead, AI should participate in drafting, counterexamples, review, and formalization assistance, while human researchers complete final verification.