The paper introduces TCSAlgBench, a of 398 theorem-level challenges from 138 STOC and COLT 2026 papers. The benchmark is designed to test automated proof discovery in theoretical computer science, a domain that requires justifying algorithms with human-inspectable arguments. Ten model configurations from four families were evaluated under direct inference and prover-verifier discussion, and four agent workflows were compared with matched model-call opportunities. The best model, GPT-5.6 Sol max, achieved 23.6% verifier-accepted coverage after 10-round discussion. The best agent workflow using GPT-5.5 xhigh with agentic planning reached 25.4% coverage. These results highlight that current models still struggle with research-level reasoning, contrasting with strong performance on competition math benchmarks.
New benchmark tests automated theorem proving for research-level theoretical computer science
TCSAlgBench comprises 398 theorem-level challenges from recent STOC and COLT papers, and shows that current large language models achieve at most 25.4% coverage in verifier-accepted proofs.
Big Tech
Chutong Yang · Xiyuan Zhang · Yu Huang · Boran Han · Soonho Kong · Shuai Zhang · +4 more
University of Texas at Austin · Amazon · University of Pennsylvania
Research Digest··2 min read
Thread:Theorem Proving Benchmarks
In one line
TCSAlgBench benchmarks automated proof discovery on 398 research-level TCS theorems; top models achieve about 25% coverage.
Before you read this
Three ideas this paper builds onbenchmarkA standard set of tasks or data used to evaluate and compare the performance of AI systems.366 papers →verificationChecking outputs for correctness before accepting them, often to catch errors or reward hacking.341 papers →large language modelA neural network trained on massive text corpora to generate coherent text and perform diverse language tasks.329 papers →
Read it as
The authors introduce TCSAlgBench, a benchmark and reusable pipeline for natural-language proof discovery in theoretical computer science.
Yang et al. constructed TCSAlgBench by extracting theorem statements from 138 papers published at STOC and COLT 2026.
How it works
stage by stageThe Daily Edition
The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.