Technical Summary: TCS-Bench

Problem Statement

While Large Language Models (LLMs) have demonstrated superhuman performance on standardized benchmarks and even competition-level mathematics (e.g., IMO), a significant gap remains between these achievements and the capabilities required for active scientific research. Existing benchmarks often rely on self-contained problems that lack the deep contextual dependencies, bespoke definitions, and interconnected lemma structures characteristic of real-world theoretical computer science (TCS) research. Furthermore, current evaluation methods struggle to assess a model's ability to generate rigorous, context-dependent proofs without access to external information or the original source material. There is a need for a benchmark that accurately reflects the workflow of human researchers: reasoning within a specific theoretical framework to derive proofs for cutting-edge results.

Methodology

Benchmark Construction (TCS-Bench)

The authors introduce TCS-Bench, a benchmark comprising 300 theorem-proving tasks derived from papers published at top-tier theoretical computer science venues (FOCS, STOC, and SODA) between 2020 and 2026. The construction process involves:

1. Data Acquisition: LaTeX sources are obtained from arXiv for papers under permissive licenses (CC-0 or CC-BY-4.0).
2. Dependency Graph Construction: A directed acyclic graph (DAG) is extracted for each paper, mapping logical dependencies between statements (theorems, lemmas, definitions). Statements are assigned a "rank" based on the longest path of dependencies leading to them.
3. Task Formulation: Each task is a self-contained proof-completion problem. The model receives:
   • A Context: A curated set of definitions, prior lemmas, and condensed references, truncated to prevent information leakage.
   • A Target Statement: A specific theorem or lemma from the paper to be proved.
   • Constraint: The model must generate a complete proof using only the provided context, without accessing the original paper or the internet.
4. Difficulty Stratification: Tasks are generated with varying difficulty levels by systematically masking intermediate results (lemmas) within the context. This forces the model to either utilize provided dependencies or reconstruct intermediate proofs to reach the target.
5. Quality Filtering: Automated structural and semantic checks (including LLM-based verification of well-definedness and coherence) ensure tasks are self-contained, free of information leakage, and fit within standard context windows (≤10,000 tokens).

Automated Verification

To address the scalability challenge of evaluating mathematical proofs, the authors developed a specialized Verifier Agent:

• Input: The task context, the target statement, the ground-truth proof, and the model's generated proof.
• Mechanism: The verifier uses four calls to a lightweight model (Gemini 3.1 Flash) to determine if the generated proof is correct. A proof is accepted if at least three of the four verdicts are positive.
• Calibration: The verifier was tuned using a dataset of 100 human-labeled proofs (50 correct, 50 incorrect), achieving over 90% accuracy against human expert judgments.

Experimental Setup

The benchmark was used to evaluate five frontier models:

• Gemini 3.1 Pro
• Gemini 3.1 DeepThink
• Opus 5
• GPT-5.6 Pro
• Colosseum: An agentic proof-search harness that decomposes problems, explores multiple strategies, and assembles/revises proofs. It was tested using Gemini 3.1 Pro and Gemini 3.6 Flash, with a cross-model selection strategy to choose the best proof.

Key Contributions

1. TCS-Bench: The first benchmark specifically designed to evaluate LLMs on research-level TCS proof generation, moving beyond competition math to context-dependent reasoning within published literature.
2. Automated Verification System: A validated verifier agent that achieves >90% accuracy against human experts, enabling scalable evaluation of mathematical proofs without prohibitive manual costs.
3. Task Generation Framework: A novel method for creating tasks of varying difficulty by manipulating the dependency graph (masking intermediate lemmas), allowing for fine-grained tracking of model progress from basic to complex reasoning.
4. Cross-Model Critique: An evaluation strategy using "Colosseum" where proofs generated by one model are critiqued by another, demonstrating that cross-model rejection signals are highly informative for filtering correct proofs.

Results

• Baseline Performance: Among the evaluated models, GPT-5.6 Pro achieved the highest accuracy at 68% (204/300 tasks). Gemini 3.1 DeepThink achieved 52%, while Gemini 3.1 Pro and Opus 5 scored 30.3% and 32.77%, respectively. Opus 5 frequently exhausted its token budget before generating an answer.
• Agentic Performance: The Colosseum harness, utilizing a cross-model selection strategy between Gemini 3.1 Pro and Gemini 3.6 Flash, achieved an accuracy of 67.7% (203/300 tasks).
• Verification Analysis: The study found that while a model's self-acceptance of its own proofs carries little information (93.4% of accepted proofs were unanimously accepted), self-rejection is highly informative. Cross-model critique (Gemini 3.6 Flash judging Gemini 3.1 Pro) significantly improved accuracy, separating correct from incorrect proofs with an AUC of 0.854.
• Performance Ceiling: Despite the strong performance of the best models, a gap remains between the current state-of-the-art (68%) and perfect performance (100%), indicating fundamental limitations in current architectures for constructing multi-step arguments within complex dependencies.

Significance

The paper claims that TCS-Bench provides a targeted measure of the sophisticated, context-dependent reasoning required to contribute to the frontiers of mathematical knowledge. By isolating the task to proof synthesis within the context of a research paper, the benchmark moves beyond "solving isolated problems" to evaluating the ability to navigate interconnected theoretical scaffolds. The authors position this work as a step toward evaluating AI agents on complex, long-horizon scientific tasks, adapting the "research-as-benchmark" paradigm to theoretical computer science. The results suggest that while significant progress has been made in automated mathematical reasoning, substantial room for advancement remains before models can fully emulate the rigorous discovery processes of human researchers.