Where Are the Limits of Large Language Models in Theoretical Computer Science Research?

    This article examines what large language models can—and cannot yet—do in theoretically verifiable theoretical computer science research. It explains the difference between benchmark performance and research capability, introduces the machine-checkable design of TCSExam, discusses the scope and limitations of its findings, and outlines a practical generate-and-verify workflow for evaluating model-produced proofs.

    Introduction: High Scores Do Not Equal Research Capability

    Large language model benchmarks have been improving rapidly, with new scores appearing regularly. At the same time, some AI organizations have published mathematics papers generated by models in areas such as number theory, geometry, and theoretical computer science. These developments have prompted broader questions about whether AI will change how mathematical research is conducted.

    Beyond the attention, a more specific question matters: how well can models perform on genuine research tasks? An evaluation in theoretical computer science (TCS) offers one way to examine this question. This article follows the evaluation’s underlying approach to explain its design, scope, limitations, and a validation workflow that developers can reuse. The discussion is limited to problems that can be formally verified; its conclusions should not be generalized to all mathematical research.

    Theoretical Computer Science: Studying the Limits of Computation

    Theoretical computer science, or TCS, studies the nature and limits of computation. It asks how efficiently a particular class of problems can be solved, which problems cannot be solved efficiently in principle, and how much of a given resource—such as time, space, or randomness—is required.

    This field differs significantly from everyday software engineering. Product development focuses on whether a system runs reliably and whether an interface can be delivered quickly. TCS focuses on proofs: why a statement is true and how broadly it applies. Its primary method is rigorous logical reasoning rather than calling a library or getting a program to run successfully. This makes TCS a useful setting for examining a model’s logical reasoning ability.

    Solving Problems vs. Doing Research

    High scores on standard benchmarks mainly reflect a model’s ability to solve well-defined problems. These problems usually have a clear prompt, a known solution method, and a standard answer. In essence, the model identifies the correct steps within a known pattern. It is similar to following a recipe: the steps are specified and the result can be checked against a standard.

    Research is different. A research problem often has no established procedure, and the answer may be unknown to everyone before the work begins. In some cases, even the person who proposed the problem does not know whether a solution exists. Evaluation is also more difficult. If a model produces hundreds of pages of “proof” claiming to resolve a longstanding open problem, experts may struggle to verify every line. Generation is inexpensive, but validation is costly.

    This is a blind spot in traditional benchmarks. Benchmark questions usually have standard answers, so they can measure a model’s familiarity with known problem types. They do not necessarily show whether the model can develop a useful approach to an unfamiliar problem, or whether its errors can be detected easily.

    The following table summarizes the differences among three settings:

    Dimension Conventional problem solving Open-ended research Machine-verifiable evaluation
    Input A clearly stated problem with a standard answer The problem itself may be ambiguous A formally expressible proposition
    Output An answer or solution steps A new idea, proof, or conjecture A proof accepted by a checker
    Evaluation Comparison with a reference answer Peer review, often time-consuming A proof checker and scoring script
    Common failures Applying the wrong known pattern Proof gaps that are difficult to detect Modeling errors or incomplete checker coverage
    Appropriate use Measuring proficiency Long-term expert judgment Formally verifiable subproblems

    Machine Verification: The Basic Idea Behind TCSExam

    The central idea behind TCSExam is to select only problems that can be checked by a machine. Here, “machine-verifiable” has a specific meaning. The problem statement must be translated into a formal language, and the proof must be checked step by step by a proof assistant such as Lean, Coq, or Isabelle. If the checker accepts the proof, the proof is valid within that formal system. If the checker rejects it, the proof cannot be accepted.

    This is similar to solving a Sudoku puzzle. Finding a solution may require substantial effort, but checking the completed grid is quick. TCSExam relies on the same principle: verification is easier than generation. It shifts much of the cost of expert grading to machine checking and reduces subjective variation in scoring.

    This approach depends on three conditions. First, the problem must be formalized accurately. If a condition is omitted during modeling, the checker is verifying a different proposition. Second, the formal system must support the mathematical tools required by the problem. Otherwise, a valid proof may be difficult or impossible to express. Third, the checker itself must be reliable.

    Machine-verifiable evaluation therefore does not mean that the entire process is automated. Formal modeling still requires human work and independent review.

    Evaluation Framework: Scope and Dimensions

    According to the evaluation materials, TCSExam contains 100 problems covering several core areas of theoretical computer science. These are not simple conceptual questions. They are intended to simulate a complete process involving reasoning, complexity analysis, and proofs of boundary conditions. The dimensions described in the materials include:

    1. Upper- and lower-bound proofs for algorithmic complexity: Deriving limits on the time or space required by a problem.
    2. Randomness and pseudorandomness: Evaluating reasoning related to probabilistic computation and derandomization.
    3. Security proofs for cryptographic protocols: Constructing security assumptions in an abstract model and checking whether reduction arguments are rigorous.
    4. Computational geometry and topology: Examining a model’s ability to reason about high-dimensional discrete structures.

    The specific problem sources, scoring protocol, and baseline models should be confirmed against the original evaluation document. These details should be checked carefully when cited; this article is not a substitute for the source material.

    Results: How Far the Conclusions Apply

    The main conclusion reported by the evaluation is that, under its testing setup, no participating model was observed to independently produce a correct proof that passed machine verification, particularly for unresolved open conjectures. Open conjectures are difficult to score automatically in the first place. The finding should therefore be understood more narrowly: among answers that could be formalized and confirmed by a checker, no successful model-generated solutions were observed.

    Several qualifications are important.

    First, this describes the result of a specific evaluation. It does not mean that every model will fail on every problem. Second, the evaluation materials do not fully disclose the participating model versions, sample sizes, or exact evaluation criteria, so readers cannot independently reproduce all reported figures. Third, a rejected proof is not necessarily mathematically false. A checker may reject a proof because the proof contains an error, but it may also reject it because of a problem in the formalization or because the formal system cannot express the required reasoning.

    The broader message is that models still struggle to produce reliably verifiable results where original breakthroughs are required. Models are effective at interpolating and combining information within existing knowledge, but they remain significantly short of being dependable research assistants for problems that require genuinely new ideas.

    Common Sources of Misjudgment and How to Investigate Them

    When building a similar evaluation, errors usually come from several sources:

    • Incorrect formalization: A condition may be omitted from the problem statement, or a quantifier may be changed during translation. One way to investigate this is to have two experts formalize the same problem independently and compare the results.
    • Incomplete proof-checker support: Some valid reasoning may not be expressible in the chosen formal system, causing a reasonable proof to be rejected. Record the exact point of every rejection and distinguish between an incorrect proof and insufficient expressive support.
    • Model hallucinations: A model may cite a nonexistent lemma or skip a critical derivation. Check every cited result against the formal library and review all omitted steps.
    • Scoring-script defects: A script may use string matching instead of genuine verification or fail to handle timeouts correctly. Run regression tests with known-correct and known-incorrect examples to confirm that the script distinguishes between them.

    Practice: A Generate-and-Verify Pipeline

    A research team can divide the evaluation process into the following six steps, with explicit checks at each stage:

    1. Formalize the problem: Translate the proposition into a formal language. Check that all conditions and quantifiers are correct, and compare the formal statement with the original problem line by line.
    2. Generate with the model: Ask the model to produce a proof or derivation. Record the model version, prompt, sampling parameters, and random seed so that the result can be reproduced.
    3. Run automatic verification: Submit the output to the proof checker or scoring script. Set timeouts and resource limits, and keep the checker version fixed.
    4. Perform manual sampling: Review samples that passed and samples that failed. Define the sampling ratio in advance and record the review results.
    5. Roll back failures: When the checker rejects an output, preserve the original record rather than overwriting it. Move the sample into a failure queue and classify it by cause.
    6. Archive the results: Preserve the problem statement, proof, checker logs, and score. The archive should support traceability.