Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
To evaluate LLMs on genuine research reasoning beyond competition mathematics, this work establishes TCSAlgBench, a dynamic benchmark of 398 natural-language proof challenges extracted from 138 STOC and COLT 2026 papers. The framework tasks models with discovering proof arguments and algorithmic constructions given theorem statements and cited prior work while rigorously withholding paper solutions. Evaluating frontier systems across multi-round prover-verifier discussion and agent decomposition workflows reveals that even the top-performing setup—GPT-5.5 xhigh with agentic planning—reaches only 25.4% five-run verifier-accepted coverage.
Even the strongest LLM agent workflows top out at just 25.4% proof coverage on STOC and COLT theorems, exposing a massive capability overhang between competition math performance and genuine theoretical computer science research.
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.