Large language models benchmarked on research level computer science proofs
TCSAlgBench: Benchmarking Automated Proving for Research-Level Theoretical Computer Science
Artificial IntelligenceComputation and Language
Summary
It is hard to measure how well AI models can understand and create complex proofs in theoretical computer science. The authors created TCSAlgBench, a big set of real research problems from recent top computer science papers to test AI at this. They tested different AI models and workflows to see how well they can prove these tough theorems. The results show some progress but also highlight that many challenges remain. This benchmark will help track how AI improves at high-level math and algorithm reasoning.
What this means in practice
- •For software developers: Evaluate AI tools that automatically generate or verify algorithmic proofs to improve software correctness and reliability.
- •For machine learning engineers: Test and refine AI models for reasoning and problem solving on advanced mathematical challenges using real-world computer science benchmarks.
Authors
Chutong Yang, Xiyuan Zhang, Yu Huang, Boran Han, Soonho Kong, Shuai Zhang, Vihang Prakash Patil, Zhen Han, Michael Bohlke-Schneider, Bernie Wang
Abstract
Large language models perform strongly on competition mathematics, but their research-level reasoning remains difficult to evaluate systematically. Theoretical computer science (TCS) connects algorithm design to explicit guarantees and fundamental limits, providing a setting for evaluating whether models can justify computational improvements with arguments humans can inspect. We introduce TCSAlgBench, a benchmark and reusable pipeline for natural-language proof discovery, comprising 398 theorem-level challenges from 138 STOC and COLT 2026 papers. Expert-designed rules complete paper-specific context, preserve computational assumptions and quantitative guarantees, and withhold constructions when discovering an algorithm is part of the task. For each task, prover systems receive theorem statements and access to cited prior work. The pipeline supports fresh, versioned challenge batches from newly released papers. We evaluate ten model configurations from four families under direct inference and prover-verifier discussion, and compare four agent workflows under matched model-call opportunities. All evaluations use the full benchmark. In the model comparison, GPT-5.6 Sol max achieves the highest five-run verifier-accepted coverage at 23.6% after 10-round discussion. Discussion and repeated sampling improve coverage. In the separate agent comparison using GPT-5.5 xhigh, decomposition improves coverage over discussion, and agentic planning achieves the highest five-run verifier-accepted coverage at 25.4%. TCSAlgBench provides a refreshable testbed for measuring progress in model reasoning and studying how agent workflows support research-level proof discovery.