Testing Real Research Ability in Large Language Models with Theoretical Computer Science Benchmarks

    A joint evaluation by academic and AI industry researchers uses theoretical computer science to test whether frontier large language models can do research, not just solve standardized problems. Models perform strongly on well-defined questions but show clear limits on open research problems. This article explains why standard math benchmarks fall short, how machine verification can reduce evaluation error, why models often produce proofs that look correct but are not, and what these findings mean for building AI research systems.

    In recent years, the mathematical abilities of large language models have drawn growing attention. Models can solve competition problems, generate proof steps, organize mathematical manuscripts, and even score close to expert level on some specialized tests. These advances are encouraging, but they raise a more basic question: are models following established patterns, or do they already have the abilities needed for theoretical research?

    A joint evaluation by academic institutions and AI company researchers approaches this question from the perspective of theoretical computer science. The research team designed a test covering the full field to examine how frontier large language models perform on theoretical computer science research tasks. The results show that models are already strong on some standardized problems, but they still have clear limitations when faced with truly open research questions that have no fixed solution method.

    1. Why Large Language Model Math Abilities Need Re-evaluation

    Most current large language model leaderboards focus on multiple-choice questions, competition problems, coding tasks, or standard question answering. These tests have clear advantages. Questions are easy to standardize, answers are usually unambiguous, scoring is inexpensive, and models can be compared directly.

    Standardized tests have an inherent limitation, however. They measure problem-solving ability well, but they do not necessarily measure research ability.

    Solving a problem usually means:

    1. The problem has been clearly stated;
    2. The input conditions are relatively complete;
    3. A predictable solution path exists;
    4. The final answer can be compared with a reference answer.

    Theoretical research often differs from this. A researcher may first need to decide whether a problem is worth studying. Then the researcher may look for definitions, construct counterexamples, propose conjectures, design proof strategies, or even reformulate the problem itself. At the start of a project, there is often no clear algorithmic procedure. The researcher also cannot know in advance whether the result will hold, fail, or need to be rewritten as a different question.

    A model that scores well on math problems therefore shows strong pattern recognition, language reasoning, and formal computation. That alone does not show that it can carry out theoretical research independently.

    2. Why Theoretical Computer Science Suits High-Quality Evaluation

    Theoretical computer science studies whether computation can be carried out, how many resources it requires, and whether general methods exist. The field connects algorithms, complexity, logic, cryptography, combinatorial structures, and formal verification.

    Two features make this field well suited to evaluating AI systems.

    First, the problems are highly abstract. A model cannot rely on surface keywords. It must understand how definitions relate to one another. For example, a question might ask whether a class of computational tasks has a polynomial-time algorithm, or what the computability boundary is under a given resource limit. To answer correctly, the model must distinguish between “an algorithm exists,” “an efficient algorithm exists,” and “an algorithm is known to exist.”

    Second, the conclusions are usually verifiable. Even complex proofs can be broken down into definitions, lemmas, corollaries, and logical links. If formal languages or automated verifiers are used, parts of a proof can be checked by a machine. Evaluators do not have to judge answers by how fluent they sound. They can check whether a conclusion holds, whether the reasoning is complete, and whether a hidden missing condition exists.

    3. Evaluation Should Not Focus Only on Final Answers

    An evaluation for theoretical research cannot look only at the final conclusion. A better approach breaks research tasks into several levels.

    1. Understanding Basic Concepts

    A model first needs to understand the definitions a problem uses. Complexity classes, reductions, decidability, randomized algorithms, and approximation algorithms differ in strict ways. An answer that looks reasonable but confuses these definitions can fail completely in later reasoning.

    Basic concept tests show whether a model has actually mastered the theoretical framework, rather than just memorizing common conclusions.

    2. Deriving from Known Propositions

    The second task asks the model to complete a proof, transformation, or derivation using known theorems. These problems have a clear goal, but they often require combining several pieces of knowledge. For example, a model may need to prove an intermediate property first, then use a reduction to extend it to the target problem.

    This level mainly tests long chains of reasoning. The model must not only know the conclusion. It must also explain why the conclusion holds and which premises each step uses.

    3. Counterexamples and Boundary Analysis

    Theoretical research does not always aim to prove a claim. Many important results show that a plausible judgment does not hold, then construct a counterexample to identify where it applies and where it fails.

    Counterexample construction is demanding. The model must actively look for special structures, extreme cases, or hidden conditions, rather than continuing in the direction the problem suggests. For AI systems, this is usually harder than restating a theorem.

    4. Open Problems and Unsolved Conjectures

    Open problems best separate exam-style ability from research ability. These problems have no verified standard answers. When a problem is first posed, researchers may not know which direction will succeed.

    The evaluation found that current models still struggle to reach reliable breakthroughs on these tasks independently. Models can generate many proofs that look complete. Common problems include changing concepts midway through an argument, omitting boundary conditions, reasoning in circles, and treating unproven intermediate claims as established facts.

    This does not mean models lack value. It means they are currently better suited as research assistants than as fully independent theoretical researchers.

    4. How Machine Verification Reduces Evaluation Error

    Traditional human grading is easily influenced by writing style. A fluent argument can look rigorous even when it is not. A concise answer with correct logic can be underrated because it gives little explanation.

    Machine verification can improve this in several ways.

    First, it can check whether formal expressions match definitions. After a proposition is converted into a logical structure, a verifier can check variable scopes, quantifier order, and whether premises are stated correctly.

    Second, it can verify local steps in a proof. Complex proofs may not be fully automated in one pass. They can, however, be split into smaller subgoals, and each step can be checked to see whether existing conditions imply it.

    Third, algorithmic properties can be tested with programs. If a model proposes a construction method, random samples, edge cases, and counterexample searches can check whether the method has the expected properties. Testing cannot prove that an algorithm works for every input, but it can quickly expose obvious errors.

    A reliable evaluation pipeline usually includes the following steps:

    1. Model generates an answer
    2. ↓
    3. Extract definitions, assumptions, and conclusions
    4. ↓
    5. Convert them into a verifiable form
    6. ↓
    7. Check local reasoning and boundary conditions
    8. ↓
    9. Human review of difficult or open-ended parts
    10. ↓
    11. Produce layered scoring results

    Machine verification does not mean full automation. For open research problems, a verifier may confirm only some local steps and cannot judge whether a conjecture has real research value. Automated checks and expert review therefore need to work together.

    5. Why Models Produce Proofs That Look Correct

    The core strength of large language models is generating high-probability text based on context. Mathematical proofs have a consistent structure: definitions come first, then lemmas, then derivations, and finally a conclusion. Models imitate this structure well, but a complete structure does not guarantee correct content.

    Common errors include the following.

    Changing Problem Conditions

    A model may quietly turn “holds for all inputs” into “holds for typical inputs,” or stretch “an algorithm exists” into “an efficient algorithm exists.”

    Using Unproven Intermediate Claims

    Answers often contain phrases such as “obviously” or “it is easy to see.” These phrases often mark the exact place where the key difficulty of a proof is hidden.

    Ignoring Counterexamples

    Models tend to follow the most common positive pattern and rarely check extreme cases. A single special input can invalidate the original conclusion.

    Terms in theoretical computer science often differ by one qualifier, such as deterministic versus randomized, exact versus approximate, finite versus countable, or local versus global. A model that relies on semantic similarity can easily merge these concepts.

    When evaluating a model’s mathematical ability, the question is therefore not whether an answer looks like a proof. The question is wh