Theoretical Computer Science: A Machine-Verifiable Yardstick for Evaluating LLM Research Ability

    As leaderboard scores for large language models refresh roughly every two months, it becomes harder to tell top models apart—and a high score only proves a model can "solve problems," not that it can "do research." Using theoretical computer science (TCS) as an entry point, this article breaks down an evaluation approach built on machine verifiability: why it poses problems the way it does, how a formal verification pipeline grades them automatically, and the counterintuitive key finding that no evaluated model could independently solve the open conjectures. It also explains what TCS actually studies, why the timing matters, the blind spots of leaderboards, and practical takeaways for building sound, scalable model evaluations.

    When Leaderboards Get Crowded, How Do We Really Evaluate a Model’s Research Ability?

    Benchmarks for large language models are entering an awkward phase: scores on various leaderboards refresh roughly every two months, yet the gap between top models grows harder and harder to read from the numbers alone. More worryingly, an impressive score only proves a model can “solve problems”—it does not show that it possesses genuine “research ability.” Using theoretical computer science (TCS) as an entry point, this article breaks down an evaluation approach premised on “machine verifiability”—why it poses problems the way it does, how it grades automatically, and what real weaknesses in frontier models it exposes.

    What Is Theoretical Computer Science Actually About?

    Many people mistake it for “writing code” or “fixing computers,” which understates the problem. A more apt analogy is driving: programmers are more like drivers, concerned with the details of the car itself—engine, transmission, interior. TCS, by contrast, studies “traffic” as a whole: how fast a trip from A to B can theoretically be, which routes are fundamentally impassable, and exactly where the lower bound of a problem lies.

    Sitting at the intersection of mathematics and computer science, every TCS problem revolves around “computation”: what resources are needed to complete a computation, whether a problem is hard or easy, and whether a better algorithm exists. Unlike most engineering practice, TCS results depend almost entirely on proofs—a claim is either rigorously proven or refuted by a constructed counterexample. This “proof-centered” nature is precisely what sets it apart from other fields.

    From public research practice, a researcher’s daily work roughly falls into a few categories: determining a problem’s complexity, designing new algorithms, proving that a lower bound cannot be beaten, and tackling open problems that remain unsolved. Designing an exam around these categories is what makes it possible to approximate “real research.”

    Why Now: An Expectation Set Alight

    The timing is telling. Not long ago, a leading AI lab publicly released hundreds of AI-generated mathematical manuscripts at once, grouped by relevance into dozens of “result families” spanning number theory, theoretical computer science, geometry, mathematical physics, and many other directions. The question “is AI about to take over mathematics too?” triggered widespread discussion.

    A well-known mathematician once pointed out that AI has a fatal weakness in almost every field—it makes errors that cannot be verified. Mathematics is the exception, especially proofs, where whether something is right can be handed to a machine for automatic checking. It is a bit like Sudoku: filling it in is hard, but once it is filled, you can check in one pass whether it is correct. So the least controversial results from AI tend to appear in mechanically verifiable domains like mathematics.

    It is precisely under this expectation that one evaluation scheme for theoretical computer science delivers a somewhat cold-water conclusion.

    The Blind Spot of Leaderboards: Solving Problems ≠ Doing Research

    A leaderboard can only show that a model can “solve problems”; it cannot reflect its true research level. The reason lies in the fundamental difference between the two.

    Solving a problem is essentially cooking by a recipe: the steps are ready-made, the taste has a standard, and you can hardly imagine adding chocolate to a sweet-and-sour pork dish and still calling it “done right.” Research, by contrast, has no prescribed steps, and no one can say in advance whether it will succeed; worse, for many problems even the person posing them does not know the answer.

    Grading is even more troublesome. A model can churn out hundreds of pages of “proof” in one go—who has the energy to check them page by page? When it claims to have cracked a conjecture that no one has solved for decades, who can prove it got it right? The hundreds of AI manuscripts mentioned earlier are a ready example: considerable in number, but their credibility must be verified one by one, and verification is extremely costly.

    This means that if the evaluation standard is chosen wrongly, a model’s ability will be systematically over- or under-estimated, and the leaderboard loses its reference value.

    The Breakthrough: Only Pose Problems a Machine Can Grade

    The key design of this evaluation scheme is simple: only pose problems a machine can grade automatically. Here lies a natural tension—the more a problem resembles real research, the harder it is to score automatically. Theoretical computer science is precisely the exception: most of its results can be verified by a machine, so it can satisfy two seemingly contradictory goals at once—“close to research” and “automatically gradable.”

    In pseudocode, the automated scoring process looks roughly like this:

    1. def evaluate(model, problem):
    2. # The model produces a candidate "proof" for the problem
    3. candidate = model.generate(problem.statement)
    4. # Step 1: syntax and type checks; reject anything malformed
    5. if not checker.is_well_formed(candidate):
    6. return 0
    7. # Step 2: hand off to a formal verification environment for correctness
    8. ok = formal_verifier.verify(
    9. statement = problem.statement,
    10. proof = candidate
    11. )
    12. # For problems with a ground-truth answer: compare the results directly
    13. if problem.has_ground_truth:
    14. return 1 if candidate.answer == problem.answer else 0
    15. # For open problems: passing means it can be machine-verified as correct
    16. return 1 if ok else 0

    In this pipeline, no human has to read through hundreds of pages of proof line by line—the verification burden is handed to the formal verification environment. The full exam contains about a hundred problems, divided into several categories that each correspond to a different type of work a TCS researcher handles day to day, aiming to cover multiple facets of the field rather than testing a single ability.

    The Key Conclusion: Open Conjectures No One Can Solve

    The conclusion matters because it is counterintuitive: faced with open conjectures that remain unsolved to this day, none of the reference models participating in the evaluation could solve any of them on its own.

    This means that although frontier models perform impressively at solving problems and even reproducing existing results, once they enter a research setting where “no one knows the answer in advance and genuine creation is required,” a clear gap remains between them and a competent researcher. There is a chasm that must be faced squarely between the optimism of “AI taking over mathematics” and the reality that “AI cannot yet independently crack open problems.”

    This is not a dismissal of the models’ value, but a reminder that a high score in a verifiable setting does not equal research ability that transfers to unknown problems.

    Takeaways: Judge Ability Rationally, Build Evaluations Soundly

    For developers and teams, this approach offers at least three insights:

    • Distinguish “solving problems” from “doing research.” When evaluating a model, do not equate the pass rate on standardized problems with the ability to solve unknown ones; evaluation sets should stay as close as possible to real, open scenarios.
    • Prefer verifiable goals. Whether evaluating mathematical reasoning, code correctness, or complex logic, try to make “whether the result can be automatically verified by a machine” a design principle, so you can escape manpower-heavy manual grading.
    • Support large-scale evaluation with engineering infrastructure. Large-scale, reproducible automated evaluation usually relies on general capabilities such as containerized compute scheduling, object storage for saving evaluation data and results, logging services for recording each run, and monitoring and alerting to track task status; such infrastructure capabilities can be supported by general product categories from mainstream cloud platforms (for example, the container platform, object storage, logging service, and monitoring and alerting offered by Baidu AI Cloud), making it easy for teams to turn the evaluation pipeline into a long-running, sustainable process.

    To return to the original analogy: a score on a leaderboard is like a speedometer—attractive, but not necessarily reliable; a “machine-verifiable” evaluation is more like a standardized driving test. It may not measure every driving skill, but at least on the critical stretches it delivers an answer everyone accepts. Only when we shift our gaze from “how fast can it go” to “can it actually get through” do we truly begin to understand where the boundaries of large language models lie.