A 100-Problem Theoretical Computer Science Benchmark for Evaluating AI Research Capabilities

    A recent preprint study jointly completed by academic institutions and an industry team introduces a 100-problem benchmark for testing how well frontier large language models handle research tasks across theoretical computer science. Rather than focusing on another leaderboard score, the work examines whether models can understand problems, construct proofs, find counterexamples, and assess open questions in ways that resemble real research. The article explains why general benchmarks are insufficient for measuring research ability, how the benchmark is designed, how a verifiable evaluation pipeline works, what the findings suggest about current model limitations, and what the work implies for research and engineering practice.

    A 100-Problem Theoretical Computer Science Benchmark for Evaluating AI Research Capabilities

    A recent preprint study jointly completed by academic institutions and an industry team has built a 100-problem benchmark for testing the research capabilities of frontier large language models across theoretical computer science (TCS). The work is notable not because it sets another benchmark score, but because it attempts to answer a more fundamental question: when AI is no longer merely solving exercises but is asked to understand problems, construct proofs, search for counterexamples, and evaluate open questions like a researcher, how far can it actually go?

    Why General Leaderboards Struggle to Measure Research Ability

    General-purpose evaluation leaderboards for large models are updated frequently, and scores continue to rise, but high leaderboard scores do not directly translate into research ability. Solving exercises is more like cooking from a recipe: the steps are relatively fixed, the evaluation criteria are clear, and the input and output boundaries are well defined. Research is more like finding a path through unknown terrain: the path may not exist, the goal may not be immediately decidable, and even the person posing the question may not know the final answer.

    This creates two difficulties. First, research tasks are hard to standardize. Open conjectures, complex constructions, and counterexample searches often have no ready-made answers. A model that outputs a seemingly reasonable proof has not necessarily solved the problem. Second, research results are hard to grade. When a model claims to have cracked a long-standing open problem, reviewers may need to spend substantial time verifying the claim. If an error is hidden inside a long chain of reasoning, the cost of manual review rises sharply.

    Theoretical computer science offers a special entry point. TCS focuses on the nature of computation itself, with research questions centered on computability, complexity, algorithm lower bounds, proof complexity, and related topics. Its core outputs are usually definitions, theorems, proofs, counterexamples, and impossibility results. Compared with long natural-language articles, many conclusions in TCS can be expressed formally and checked by machines. In other words, whether a proof is correct can be relatively objectively reviewed by a formal verifier. This does not mean that all TCS problems can be automatically graded, but it at least provides a feasible foundation for machine-checkable evaluation of research ability.

    Core Design Principles of the Benchmark

    The benchmark uses 100 problems divided into four categories according to the types of research activities performed by theoretical computer scientists. Public materials do not detail every problem, but from the logic of the evaluation design, the four categories are not simply difficulty tiers. They correspond to different stages in the research workflow and can be abstracted as: problem understanding and formalization, constructive proofs and algorithm design, counterexamples and impossibility arguments, and open-problem decomposition and research-plan evaluation. This classification is closer to real research than multiple-choice and fill-in-the-blank questions, and it is also easier to grade than purely open-ended question answering.

    A qualified benchmark for research ability should satisfy at least the following principles:

    1. Machine-checkable or reviewable: Model outputs should be converted as much as possible into formal proofs, algorithm descriptions, counterexample instances, or checkable structured conclusions, reducing the subjective space for answers that merely “look plausible.”
    2. Research authenticity: Problems should not be mere variants of course exercises. They should cover real research actions such as clarifying definitions, proving theorems, analyzing complexity, and constructing counterexamples.
    3. Full-field coverage: Subfields within TCS differ greatly. The benchmark must avoid testing only one type of proof technique; otherwise, a high score may reflect only local overfitting.
    4. Resistance to data contamination: Problems, variants, and answers need controlled overlap with public release timelines and training corpora, preventing models from scoring through memorization rather than reasoning.
    5. Reviewable process: For open problems that cannot be fully machine-judged, the design needs human review or subgoal-checking mechanisms that clarify which conclusions can be automatically verified and which can only serve as research signals.

    Evaluation Pipeline and Scoring Workflow

    A typical verifiable evaluation pipeline can be abstracted into the following pseudocode:

    1. def evaluate(model, problem_set):
    2. results = []
    3. for problem in problem_set:
    4. raw_answer = model.generate(problem.statement)
    5. formal_artifact = parse_to_formal(raw_answer)
    6. if formal_artifact is None:
    7. results.append(("unparseable", problem.id))
    8. continue
    9. check_result = formal_checker.verify(formal_artifact, problem.spec)
    10. if check_result.status == "failed":
    11. results.append(("invalid", problem.id))
    12. else:
    13. results.append(("verified", problem.id))
    14. return aggregate(results)

    This pseudocode reflects a key idea: model output cannot stop at natural-language explanation; it must be parsed into checkable artifacts. The verifier checks proof steps, type correctness, boundary conditions, or counterexample validity. Parts that cannot be formalized go to human review. Statistical metrics should also go beyond “accuracy” and focus on verified pass rate, formalization coverage, counterexample validity, proof-step completeness, and the quality of research progress on open problems.

    Interpreting the Key Findings

    The study’s conclusions have a sobering tone: for open conjectures that remain unresolved to date, no reference model was able to provide a verifiable complete solution on its own. More commonly, models can restate definitions, imitate common proof patterns, and produce local derivations, but they are clearly lacking in long-chain constructions, innovative counterexamples, research taste, and global strategy. A model may generate a fluent-looking proof but introduce unverifiable jumps at key steps. It may also repackage known results as “new discoveries.”

    The significance of this work is therefore not a claim that “AI makes mathematics obsolete,” nor a simple denial of model capabilities. It draws a boundary of ability: on tasks with a high degree of formalization and clear evaluation criteria, models can serve as efficient assistants; on open research problems, they are currently better suited to literature organization, proof-sketch generation, candidate counterexample search, and formal completion rather than independently taking responsibility for final conclusions.

    Implications for Research and Engineering Practice

    For research teams, when building domain evaluation sets, the priority should be to choose verifiable outputs, convert natural-language answers into structured artifacts, and then connect automatic checking with human review. For companies and developers, general leaderboards are insufficient for model selection. They should build small, repeatable, contamination-resistant evaluation sets around real tasks. From an engineering perspective, teams can borrow the “generate-parse-verify-review” pipeline: have models output unit tests, property tests, formal specifications, or executable scripts, then check them with automated tools. High-risk conclusions must retain human review.

    When building such evaluation pipelines on cloud infrastructure, general object storage, container platforms, logging services, monitoring, and alerting can be combined. The focus remains evaluation methodology, data governance, and traceability of results. For example, when building an evaluation pipeline on Baidu AI Cloud, teams should also manage problem versions, model outputs, verification results, and human review records in a unified way, rather than treating a one-off benchmark run as a long-term capability conclusion.

    Limitations and Future Directions

    The benchmark still has limitations: 100 problems cannot cover all subfields of TCS; formalization costs are high; automatic judgment of open problems remains difficult; model self-evaluation is unreliable and must rely on external verification; and the benchmark itself needs dynamic updates to prevent contamination. A more feasible future direction is to build a layered evaluation system: basic definition and proof checking, complex construction and counterexample search, open-problem subgoal decomposition, and evaluation of human-AI collaborative research workflows. Only by doing both “verifiability” and “research authenticity” well can AI research-capability evaluation avoid degenerating into another ordinary exam paper.