LLM Evaluation in Theoretical Computer Science: How Far Are They from Doing Research?

    While Large Language Models frequently refresh benchmark scores, their ability to solve problems does not equate to the ability to conduct research. A recent evaluation targeting Theoretical Computer Science (TCS) tests mainstream LLMs' reasoning abilities using machine-verifiable questions. This article explores the difference between solving problems and conducting research, analyzes the evaluation results, and provides actionable advice for developers on integrating formal verification, exploring neuro-symbolic systems, and preparing appropriate compute resources.

    Large Language Models (LLMs) refresh their scores on various benchmarks almost every few months. While these numbers demonstrate a model’s proficiency in solving problems, they rarely prove its capacity to conduct actual research. Recently, an evaluation tailored to Theoretical Computer Science (TCS) has drawn attention. By using a new set of questions to test the reasoning abilities of current mainstream LLMs, the results offer valuable references for developers.

    1. What Does Theoretical Computer Science Study?

    Software developers typically care about how to implement features, optimize performance, and fix bugs. Theoretical Computer Science focuses on more fundamental questions: What are the inherent laws of computation? How fast can a specific class of problems be solved? Are there certain problems that algorithms fundamentally cannot solve?

    Located at the intersection of mathematics and computer science, this field primarily includes algorithmic complexity analysis, computability theory, cryptographic foundations, and graph theory. Its primary working method involves constructing rigorous mathematical proofs rather than writing executable programs. Once a theoretical conclusion is established, it influences a vast array of engineering practices, such as compiler design, cryptographic protocols, and database indexing.

    2. The Difference Between Solving Problems and Conducting Research

    Currently, the strength of LLMs lies in learning patterns from massive training data. When encountering problems similar to their training data, models can provide standard solutions. This is akin to cooking from a recipe: the steps are written, the taste is standardized, and one only needs to follow the instructions.

    However, the conditions for scientific research are different. Researchers often do not know the answer to a problem or which path will lead to a solution. A conclusion may only be proven after repeated trial and error. Furthermore, judging whether an answer is correct is inherently difficult. When someone claims to have solved a decades-old conjecture, reviewers must scrutinize pages of reasoning line by line. Manual verification is costly and prone to omissions and errors.

    The differences between the two can be summarized in four points:

    • Input: Problem-solving relies on existing problem types, while research depends on the ability to pose questions about unknown problems.
    • Evaluation Criteria: Problem-solving has standard answers, whereas research relies on peer verification.
    • Common Failures: Problem-solving often fails due to calculation errors or misunderstandings, while research often fails in intermediate reasoning steps with arguments that seem plausible but are fundamentally unsound.
    • Verification Method: Problem-solving can be checked by directly comparing answers, whereas research requires strict examination of the proof itself.

    3. Why Only Use Machine-Verifiable Questions?

    The core design of this evaluation is to use only questions that machines can grade.

    This design relies on the characteristics of Theoretical Computer Science. Many conclusions and proofs in this field can be translated into formal logical languages and then checked by automated theorem provers or formal verification tools. This is similar to Sudoku: finding a complete solution may be difficult, but checking whether a filled-in answer complies with the rules is simple and objective. As long as a proof can be formalized, grading can be detached from human judgment, making the evaluation results easier to reproduce.

    The evaluation includes 100 questions covering four core tasks that TCS researchers engage in daily. The questions range from extensions of classical theories to explorations of open problems. The quantity and types of questions help determine the evaluation’s coverage. For specific task divisions and scoring rules, readers should consult the original paper directly.

    4. What Do the Evaluation Results Indicate?

    In this test, none of the participating LLMs independently solved the unresolved open conjectures using their own capabilities. This conclusion applies only to the models evaluated, the difficulty of the questions, and the test settings that did not allow external tool assistance. It cannot be generalized to suggest that all models are incapable of all research tasks.

    The evaluation also exposed three common issues:

    1. Broken Logical Chains: When reasoning requires dozens or even hundreds of steps, models are prone to hallucinations in intermediate steps. A single error invalidates the entire proof.
    2. Lack of Originality: Models excel at reorganizing and expressing existing knowledge, but their performance noticeably weakens when facing problems that require constructing new tools or proposing new concepts.
    3. Overconfidence in Expression: Models often generate proof paragraphs with rigorous tone and complete structure that actually contain logical fallacies. Without automated checking, readers find it difficult to spot these on the spot.

    The third point is particularly alarming. If an incorrect proof is written fluently, readers can easily be misled. Therefore, automated verification is more reliable than a reader’s intuition.

    5. What Developers Can Do

    The insights from this evaluation are primarily aimed at developers. The following three directions are still being explored, and their effectiveness depends on the specific task.

    First, combine generation with formal verification. LLMs are responsible for providing proof sketches and high-level ideas, while formal tools like proof assistants check each logical step and fill in details. This division of labor can reduce hallucination-induced errors, but it is limited by the coverage of the verification tool. Content beyond this coverage still requires manual review. Systems should also have fallback plans, such as returning “uncertain” when verification fails, rather than outputting a seemingly complete answer.

    Second, explore neuro-symbolic systems. Pure neural networks have structural difficulties with precise logical reasoning. Neuro-symbolic systems allow models to understand ambiguous semantics while delegating rigorous logical deductions to a symbolic reasoning engine. This architecture promises to balance generalization with rigor, but its engineering complexity is high and requires step-by-step verification based on scenarios.

    Third, prepare appropriate compute environments for training and verification. Formal verification and large-scale reasoning typically require stable computing resources and reliable data storage. General cloud computing platforms can support these needs, but selection requires evaluating cost, data security, toolchain compatibility, and the team’s operational capabilities.

    6. Pre-Deployment Checklist

    Before applying the above methods to actual projects, you can confirm the following items:

    • Can the correctness standard of the task be transformed into an automatically checkable format?
    • Have proof assistants or other verification tools been integrated, and are their coverage scopes clearly defined?
    • Are the model-generated proof sketches retained for subsequent traceability?
    • Is manual sampling inspection arranged for content outside of automated verification?
    • Are failure cases recorded and used to improve prompts and tool configurations?
    • Did the evaluation specify the model version, question scope, and whether tool usage was allowed?

    7. Conclusion

    This evaluation provides a relatively objective reference. While LLMs are improving rapidly at solving problems, there is still a significant gap when it comes to open-ended scientific research. For developers, the most practical approach is to prioritize verifiability in design: hand over to machines the steps that can be checked by machines, and leave the judgment to humans.