Theoretical Computer Science Benchmarks: A Litmus Test for AI Research Capability

    As frontier LLMs keep setting new records on public leaderboards in math and coding, the harder question—whether AI can actually *do research*—remains largely untested. This article explains why Theoretical Computer Science (TCS) works as a yardstick for AI research capability, walks through a benchmark of 100 problems organized into four task categories, and offers a careful reading of the finding that no model independently solved any open conjecture. It closes with a practical guide to building a verifiable benchmark pipeline—task design, scorer architecture, deployment, and statistics—plus three takeaways for engineering and research teams.

    1. After Benchmark Saturation: The Missing Dimension Is “Research Capability”

    Over the past two years, the composite scores of frontier large models on public leaderboards have been broken almost every few months. Gains in math- and code-oriented tasks have been especially visible. The reason is easy to see: these tasks usually have a single answer or can be checked automatically, so scoring is extremely cheap and they are naturally suited to large-scale automated evaluation. As a result, posts like “AI can already do math” show up on social media often—high engagement, but the conclusion usually does not hold up.

    The key problem is this: most leaderboards measure the ability to produce a given answer under a given problem statement, whereas the core action of research is something else entirely—converging a vague phenomenon into a decidable problem, choosing the right definitions for it, constructing a proof or an algorithm, and judging whether what you constructed actually holds. The former is like the parking portion of a driving test; the latter is planning a route no one has traveled before, and proving that it is genuinely connected.

    Theoretical Computer Science (TCS) sits exactly at the intersection of these two abilities. It studies computation itself: how much time, space, and randomness a problem needs to be solved under a given model; whether certain lower bounds can be broken; whether some class of structures is destined to be unprocessable efficiently. Researchers mostly write proofs rather than programs. If engineering practice cares about the engine and the interior, TCS cares about the topology of the road network and its traffic limits—how fast two points can possibly be connected, and which roads are, in principle, impassable.

    A recent piece of work, jointly produced by an interdisciplinary information research institution and a large-model research team, turns this kind of research task into a benchmark: 100 problems organized into four categories by the different forms that research work takes, then used to test several frontier models available at the time. The timing was chosen when the debate over “has AI already replaced mathematical research” was at its hottest, and the conclusion is measured—among the models evaluated, not a single one could independently produce a correct answer to the still-open, research-level conjectures. Below, we break down from a benchmark-design perspective why this approach is worth borrowing for both engineering and research teams.

    2. Why TCS Works as a Yardstick for “Research Capability”

    For a benchmark to measure research capability, it must satisfy three conditions at once: the tasks must be close enough to real research, the scoring must be automatable and hard to get wrong, and it must span difficulty levels from routine to open-ended. TCS has natural advantages on all three.

    First, answers are highly structured, so verification costs far less than solving. The correctness of an algorithm design can be split into three checks—termination, partial correctness, and a complexity upper bound; a lower-bound argument can be split into an induction base, an induction step, and a key lemma. This is similar to Sudoku: filling in a complete solution is hard, but checking whether it satisfies the constraints takes only a single pass. What benchmarks fear most is unreliable scoring, and formal proofs plus executable verification turn scoring from “subjective grading” into “programmatic judgment.”

    Second, the difficulty spectrum is continuous, with a steep enough tail. Within the same field there are exam-level definition problems, routine lemma problems, constructions that take multiple papers to reproduce, and conjectures left open in the field for a long time. This continuous spectrum keeps the benchmark from saturating too early—after a model gets full marks on the easy layers, harder layers keep discriminating between models.

    Third, errors can be localized. When an open-ended writing task fails, it usually just says “written poorly,” but a proof problem typically exposes the failure at a specific step: the wrong model was used in a definition, the wrong parameter was chosen for an induction quantity, a construction ignored the boundary scale, or a complexity analysis dropped a factor. This structured failure mode gives the benchmark results direct diagnostic value.

    3. Four Task Types, Mapping to Four Kinds of Real Work

    Judging from the public description, this benchmark is organized into four categories by the different forms of research work. Using a widely accepted division of capabilities, each category tests something distinct:

    1. Problem understanding and formalization. Given a phenomenon with an engineering background or a semi-formal description, the model must write precise mathematical definitions and specify inputs, outputs, and the cost model. Get this wrong and everything downstream is wrong—and in real research this step takes far more time than outsiders imagine.
    2. Construction and algorithm design. The model must provide an existence construction or an algorithm, together with correctness and complexity analysis. This tests “whether an idea can be turned into a checkable argument,” not “whether the model has heard of the result.”
    3. Lower-bound and impossibility arguments. The model must prove that a bound cannot be improved, or that a reduction does not hold. The defining feature here is that the model must carry the burden of “ruling out all possibilities” itself; a common error is claiming a complete proof after discussing only a special case.
    4. Exploration and decomposition of open problems. Facing a conjecture with no accepted answer, the model must propose verifiable partial results, suggest counterexample-search strategies, or reduce it to a known problem. This layer tests not memory but research taste and a sense for problem structure.

    The score differences between the four categories are often more informative than the total score. Most models do well on definition problems that require retrieval-style memory, drop noticeably on medium problems that require multi-step construction, and broadly fail at the open layer. This decay curve is the real output of the benchmark.

    4. How to Read “No Model Solved the Open Conjectures”

    The finding that “no model solved any open conjecture” is easy to read into two extremes: “AI has no hope in research,” or “the models just memorized a question bank.” Both readings are too crude. Three more accurate points follow.

    First, open conjectures are an extreme tail of the problem distribution. A zero pass rate indicates that current models still have a structural gap in “long-chain, self-consistent, reference-free” reasoning—not that they are ineffective across all tasks. On the same benchmark, medium-difficulty tasks usually show fairly respectable accuracy.

    Second, the value of a benchmark lies in providing a reproducible lower bound. In the past, judging “can AI do research” relied on individual cases and anecdotes—one successful demo, one paper that thanked a model. Only after tasks, scorers, and sampling protocols are all fixed does the conclusion become comparable and iterable: when the next model ships, you rerun the same test set, and any progress or regression is attributable.

    Finally, guard against mistaking the benchmark metric itself for research capability. A benchmark is a sample, not the whole picture. A zero at the open layer only shows that models cannot yet independently cross the full span “from problem to verifiable conclusion”; it does not mean they add no value in supporting steps such as literature review, counterexample search, organizing proof drafts, or transcribing proofs into formal systems. These steps are exactly where human-machine collaboration currently delivers the clearest returns.

    5. Building Your Own Benchmark Pipeline: Putting “Verifiable” into Engineering

    If a team wants to reproduce a similar benchmark, five methodological issues need to be handled.

    Task construction and contamination prevention. Problems must come from data released after training cutoff, or at least from forms uncommon in public corpora. Common practices include: rewriting new results from recent preprints into problems, keeping a private holdout set undisclosed, doing semantic-level rewriting of prompts rather than just swapping symbols, and running memory probes on the model (asking it to restate related results to see whether it can recite the answer directly).

    Scorer design. The priority order should be: formal checking > executable verification > structured rules > human review. Formal checking hands the proof to a proof assistant’s kernel for verification; executable verification turns a construction into code and runs it against adversarial tests; structured rules check whether required lemmas and boundary cases appear. Only when none of these can cover a case should you bring in multi-person cross-review, with clearly defined review criteria.

    1. # Skeleton for a verifiable benchmark (pseudocode; expresses evaluation logic only)
    2. # Each task contains: prompt, formal statement or reference solution, verifier, difficulty label, task category
    3. TASKS = load_tasks("tcs_bench")
    4. def evaluate_one(task, model, k=8, max_tokens=8192, temperature=0.6):
    5. passed = 0
    6. for _ in range(k): # Sample multiple times; measure stability rather than one-off luck
    7. answer = model.generate(task.prompt,
    8. max_tokens=max_tokens,
    9. temperature=temperature)
    10. if task.verify(answer): # Formal checking + adversarial cases + boundary checks
    11. passed += 1
    12. return passed
    13. # Unbiased pass@k estimator: n = number of samples, c = number of passes
    14. def pass_at_k(c, n, k):
    15. if n - c < k:
    16. return 1.0
    17. return 1.0 - comb(n - c, k) / comb(n, k)
    18. # Aggregate by "task category x difficulty layer", not a single total score
    19. report = {}
    20. for layer in DIFFICULTY_LAYERS:
    21. for cat in TASK_CATEGORIES:
    22. rs = [evaluate_one(t, model) for t in TASKS.filter(layer, cat)]
    23. report[(layer, cat)] = mean(pass_at_k(c, SAMPLES, K) for c in rs)

    Statistical protocols. At the scale of 100 problems, random fluctuation is not negligible, and any score difference should be reported with a confidence interval. You must also fix and publish: number of samples, temperature, token budget, whether external tools are allowed, and whether multi-round self-correction is allowed. Comparisons under inconsistent protocols are meaningless—allowing tool use and disallowing it measure two different capabilities.

    Process metrics. Recording only pass/fail wastes a great deal of information. Worth capturing as well: at which step the first verifiable draft appears, which category errors cluster in (definition bias, induction-quantity selection, missing complexity factors, ignoring boundary scale), and whether self-correction after a failure is effective. The direct value of these metrics for improving models and prompting strategies often exceeds that of the total score itself.

    6. Deployment Architecture and Engineering Implementation

    Once a benchmark becomes routine, it stops being a script and becomes a pipeline that must run. Expressed with common cloud components, a typical layering looks like this:

    • Object storage: holds the problem set, formal files, model output trajectories, and historical evaluation results as the single source of truth, with version-based traceability.
    • Container platform + isolated sandbox: verifiers and executable checks must run in a restricted environment with limits on network, filesystem, and CPU time, so untrusted code cannot affect the host.
    • Message queue: distributes problems as fine-grained tasks, naturally supporting retries, rate limiting, and concurrency scaling—so growth in problem count and number of models requires no changes to business logic.
    • Logging service and monitoring/alerting: records the protocol parameters and latency distribution for each run, with threshold alerts for verifier anomalies, sandbox timeouts, and sudden spikes in scoring failure rate—the scorer itself breaking is the most common silent failure in such systems.

    For this kind of pipeline, general capabilities from Baidu AI Cloud—object storage, message queue, containers, and log monitoring—can serve as one infrastructure option, letting teams focus their energy on problem quality and scoring logic. The latter is the real source of a benchmark’s credibility.

    7. Three Takeaways for R&D Teams

    First, make verification solid before talking about capability gains. Auto-verifiability is the prerequisite that lets TCS be benchmarked at all. When designing their own benchmarks, teams should start with areas where verification is cheap, rather than immediately taking on open-ended tasks.

    Second, manage capability boundaries instead of chasing the total score. The layered decay curve a benchmark produces carries more decision value than a nice-looking total: it tells you directly which steps can be handed to the model and which must keep human review.

    Third, structure the human-machine division around the verification step. The model’s current weakness is independently crossing the long chain “from problem to verifiable conclusion,” while its strength lies in literature review, counterexample enumeration, generating proof drafts, and formalization transcription. Putting these steps into the workflow, with humans taking the key judgments and final sign-off, is currently the most cost-effective combination.

    A single exam paper won’t let mathematicians breathe a sigh of relief, nor will it put anyone out of work. Its real function is to give the vague debate over “will AI do research” a reproducible scale: when the next model iteration arrives, you rerun the same problems, and the answer is right there—comparable, attributable, and improvable.