TCSAlgBench: Benchmarking Automated Proving for Research-Level Theoretical Computer Science

Problem

The paper addresses a significant gap in the evaluation of large language models (LLMs) regarding their ability to perform research-level reasoning in theoretical computer science. Specifically, it highlights the lack of benchmarks that assess the reasoning capabilities of LLMs on complex theorem-level challenges derived from recent theoretical computer science literature. This work is presented as a preprint and has not undergone peer review.

Method

The authors propose TCSAlgBench, a benchmark consisting of 398 theorem-level challenges sourced from 138 papers presented at the 2026 Symposium on Theory of Computing (STOC) and the Conference on Learning Theory (COLT). The benchmark is designed with expert-crafted rules that provide context, outline computational assumptions, and establish quantitative guarantees for the reasoning tasks. The input for the proving systems includes theorem statements along with access to cited prior work, allowing models to leverage existing knowledge.

The evaluation involves ten configurations from four distinct model families, employing both direct inference and a prover-verifier discussion method. The authors implement four different agent workflows that are matched to model-call opportunities, facilitating a comprehensive assessment of the models' reasoning capabilities.

Results

The results indicate that the GPT-5.6 Sol max configuration achieved a verifier-accepted coverage of 23.6% after a 10-round discussion, marking a significant performance metric against the baseline of no reported coverage. Additionally, the GPT-5.5 xhigh configuration, which utilized agentic planning, achieved a higher verifier-accepted coverage of 25.4%, again compared to the baseline of none reported. These results demonstrate the potential of LLMs in tackling complex theoretical challenges when appropriately configured and evaluated.

Limitations

The authors do not report any limitations in their study. However, the absence of a peer review process may imply that the findings should be interpreted with caution until validated by the community. Additionally, the benchmark's reliance on specific papers from STOC and COLT may limit its generalizability to other areas of theoretical computer science.

Why it matters

The introduction of TCSAlgBench has significant implications for future research in automated reasoning and the application of LLMs in theoretical domains. By providing a structured framework for evaluating LLMs on complex reasoning tasks, this benchmark can facilitate the development of more capable models and encourage further exploration into the intersection of AI and theoretical computer science. The results also suggest that with appropriate configurations and workflows, LLMs can achieve meaningful performance in research-level reasoning, paving the way for advancements in automated theorem proving and related fields.