TCSExam: A Unified Arena for LLMs Battling Theoretical Computer Science

Can large language models advance theoretical computer science (TCS) and solve its open conjectures? This question has long remained at the level of philosophical discussion, but now there is a quantifiable experimental framework. The newly proposed TCSExam attempts to provide a unified benchmark for evaluating frontier LLMs' capabilities across the full spectrum of TCS research, measuring theorem proving, solver engineering, constructive work, and direct attacks on open conjectures on the same scale.

Four tracks covering the full TCS research pipeline

According to the original paper, TCSExam is designed to cover the complete chain of TCS research rather than testing a single capability. It includes four parallel tracks: theorem proving, solver engineering, construction, and direct attempts to solve open conjectures. The first three correspond to concrete research outputs, while the fourth targets long-unsolved research goals, examining whether models can make progress on genuinely open problems.

The significance of this division lies in distinguishing "being good at solving problems" from "being good at doing research." Theorem proving and construction have clear right-or-wrong criteria, whereas attempts at open conjectures may produce independently verifiable special cases or bounds even without a complete solution—these intermediate results themselves have academic value.

Theoretical computer science (TCS) is the mathematical foundation branch of computer science, studying the fundamental limits and possibilities of computation, with typical topics including P vs NP, algorithmic lower bounds, communication complexity, and cryptographic assumptions. Unlike engineering-oriented systems research, its outputs are primarily theorems, proofs, and asymptotic bounds, with strict verification standards that often require formal reasoning. For this reason, TCS has long been regarded as one of the fields least suited to being directly tackled by statistical language models—a proof either holds or it doesn't; there is no "roughly correct." TCSExam divides TCS research into four tracks—theorem proving, solver engineering, construction, and open conjectures—precisely because it recognizes that the field encompasses both purely formal reasoning and an engineering side that requires actually running algorithmic solvers.

Dual verification and two benchmark tiers

TCSExam employs hard verification in its scoring mechanism. TCSExam-Full contains 100 expert-reviewed tasks, and all submissions are verified by the Lean kernel or executable task checkers. This means model outputs cannot slip through with linguistically plausible-sounding answers; they must pass formal verification or actual runtime testing.

To reduce evaluation costs, the team also designed TCSExam-Lite: 20 tasks selected from the full set, five per track, reducing the number of task attempts by 80% while keeping the single-attempt budget unchanged.

The paper shows that Full and Lite rankings are highly consistent across eight shared agents, with a Spearman correlation coefficient of 0.93, providing statistical support for Lite as a compact yet discriminative benchmark. For researchers with limited compute, Lite offers a practical alternative.

Lean is an interactive theorem prover led by Microsoft Research, and also a dependently typed programming language. Its core feature is "kernel verification": before any proof is accepted, a small trusted kernel code checks each inference step against type rules, so model outputs cannot pass verification through vague or ambiguous language. The Lean community has built large-scale formalized mathematics libraries such as mathlib, making it possible to extend formal verification from pure mathematics to computer science theorems. In TCSExam, the Lean kernel serves as the "hard judge" for the theorem proving track and some construction tasks, while solver engineering and executable construction tasks are verified by actual running task checkers—the former ensures logical correctness, the latter ensures algorithmic behavior meets expectations, and together they form the objectivity basis of "dual verification."

Who's leading: eight agents on the leaderboard

The research team evaluated eight agents on Full and nine on Lite. The TCSExam Index aggregates scores across the four tracks, with GPT-6 Astra leading Full at 71.9 and Opus 5.5 leading Lite at 72.3.

More noteworthy than the rankings are the substantive outputs generated during evaluation. The paper notes that these evaluations produced improved solver outputs and mathematical constructions, as well as independently verified special cases and bounds from attempts at open conjectures. In other words, the benchmark doesn't just score models—it also incidentally produces intermediate results that can serve as research material.

In benchmark evaluation, the Spearman rank correlation coefficient measures the consistency between two rankings, ranging from -1 to 1, with values closer to 1 indicating that the two scoring systems produce more concordant rankings. TCSExam reports a Spearman ρ=0.93 between Full and Lite, meaning that ranking agents using the 20-task Lite version is nearly identical to ranking them using the 100-task Full version. This statistic is critical because the risk of compact benchmarks is that task sampling bias could distort rankings; high rank correlation shows that Lite substantially reduces evaluation costs while preserving discriminative power, offering a credible alternative for researchers with limited compute.

Open framework emphasizing reproducibility

TCSExam is positioned as an extensible framework, with the paper providing task sources, Docker build recipes, and evaluation tools for reproducible community use. This is crucial for the long-term value of benchmark work—TCS research is broad, and 100 tasks will inevitably have limited coverage; an extensible task integration mechanism allows subsequent researchers to add new problems under the same specification.

What this benchmark changes

The emergence of TCSExam lies in decomposing the vague question of "can LLMs do research" into multiple executable, verifiable sub-problems. Lean kernel verification and executable checkers ensure scoring objectivity, the four-track division makes capability profiles more three-dimensional, and the Lite version offers a compromise between cost and discriminative power.

For researchers focused on AI for Science, the value of this framework lies not only in the current leaderboard but also in providing an evaluation protocol that can continuously incorporate new tasks. As model capabilities continue to evolve, score changes under the same protocol will become a reliable window for observing genuine progress of LLMs in formal mathematics and algorithm research.

One-line Summary

TCSExam uses four tracks and Lean kernel verification to quantitatively evaluate LLMs' ability to advance theoretical computer science research.

Paragraph Summary

TCSExam is a benchmark for theoretical computer science (TCS) aimed at large language models, designed to decompose the vague question of "can LLMs do research" into executable, verifiable sub-problems. It features four tracks—theorem proving, solver engineering, construction, and direct attempts at open conjectures—covering the full TCS research pipeline. TCSExam-Full contains 100 expert-reviewed tasks, with all submissions hard-verified by the Lean kernel or executable task checkers; TCSExam-Lite has only 20 tasks, reducing attempts by 80%, and its rankings are highly consistent with Full at Spearman ρ=0.93. Eight agents were evaluated on Full, with GPT-6 Astra leading at 71.9; Opus 5.5 tops Lite at 72.3. The evaluation process also produced improved solver outputs, mathematical constructions, and independently verified special cases and bounds for open conjectures.