# TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability

arXiv: https://arxiv.org/abs/2608.09538 · HTML: https://mlsanity.com/paper/2608.09538/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 166 of its 228 references that are in the map.
- First posted on arXiv 10 Aug 2026.

## Builds on (most cited first, 30 of 166)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [AGIEval: A Human-Centric Benchmark for Evaluating Foundation Models](https://mlsanity.com/paper/2304.06364/) (2023)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [AI and the Everything in the Whole Wide World Benchmark](https://mlsanity.com/paper/2111.15366/) (2021)
- [PaperBench: Evaluating AI's Ability to Replicate AI Research](https://mlsanity.com/paper/2504.01848/) (2025)
- [MathArena: Evaluating LLMs on Uncontaminated Math Competitions](https://mlsanity.com/paper/2505.23281/) (2025)
- [Gold-medalist Performance in Solving Olympiad Geometry with AlphaGeometry2](https://mlsanity.com/paper/2502.03544/) (2025)
- [GFlowNets for AI-Driven Scientific Discovery](https://mlsanity.com/paper/2302.00615/) (2023)
- [CHAMP: A Competition-level Dataset for Fine-Grained Analyses of LLMs' Mathematical Reasoning Capabilities](https://mlsanity.com/paper/2401.06961/) (2024)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Near-Optimal Algorithms for Omniprediction](https://mlsanity.com/paper/2501.17205/) (2025)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [CombiBench: Benchmarking LLM Capability for Combinatorial Mathematics](https://mlsanity.com/paper/2505.03171/) (2025)
- [The Open Proof Corpus: A Large-Scale Study of LLM-Generated Mathematical Proofs](https://mlsanity.com/paper/2506.21621/) (2025)
- [The transformative potential of machine learning for experiments in fluid mechanics](https://mlsanity.com/paper/2303.15832/) (2023)
- [BrokenMath: A Benchmark for Sycophancy in Theorem Proving with LLMs](https://mlsanity.com/paper/2510.04721/) (2025)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Proving Olympiad Inequalities by Synergizing LLMs and Symbolic Reasoning](https://mlsanity.com/paper/2502.13834/) (2025)
- [MathConstruct: Challenging LLM Reasoning with Constructive Proofs](https://mlsanity.com/paper/2502.10197/) (2025)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Pricing Query Complexity of Revenue Maximization](https://mlsanity.com/paper/2111.03158/) (2021)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [LemmaBench: A Live, Research-Level Benchmark to Evaluate LLM Capabilities in Mathematics](https://mlsanity.com/paper/2602.24173/) (2026)
- [Measuring Progress in Reasoning Toward Mathematical Discovery with Automatic Verification](https://mlsanity.com/paper/2603.15617/) (2026)
- [Single-Sample Prophet Inequalities via Greedy-Ordered Selection](https://mlsanity.com/paper/2111.03174/) (2021)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [Breaking the 3/4 Barrier for Approximate Maximin Share](https://mlsanity.com/paper/2307.07304/) (2023)
- [Certifying almost all quantum states with few single-qubit measurements](https://mlsanity.com/paper/2404.07281/) (2024)

## Built on by (most cited first, 3 of 3)

- [FormalTCS: Benchmarking End-to-End Frontier Formal Theoretical Computer Science Research of Large Language Models](https://mlsanity.com/paper/2608.20153/) (2026)
- [Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science](https://mlsanity.com/paper/2609.15983/) (2026)
- [TCSAlgBench: Benchmarking Automated Proving for Research-Level Theoretical Computer Science](https://mlsanity.com/paper/2609.35606/) (2026)

## Abstract (arXiv)

We introduce TCS-Bench, a benchmark for evaluating Large Language Models (LLMs) on research-level Theoretical Computer Science (TCS) proof generation. TCS-Bench consists of theorem-proving tasks from papers published at top theoretical computer science venues (STOC, FOCS, and SODA). Each task provides the necessary context to derive a self-contained proof for a target result. We evaluate state-of-the-art models on this benchmark. We verify the correctness of generated proofs via a verification agent, and further benchmark the verifier against human-expert proof judgements on a set of target statements and generated proofs pairs. Our reference verifier achieves over 90% accuracy on the expert labeled set.