acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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. The tasks are publicly available at https://github.com/TCSBench/TCSBench.

Primary area:
datasets and benchmarks
Keywords:
AI, Benchmark, TCS

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_WG9kOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces a new benchmark consisting of 300 proof tasks from academic papers in theoretical computer science. In addition, it develops an LLM-as-a-judge-based verifier that achieves 90% agreement with human experts. In the evaluation, the best performance achieved by the models and agents on this benchmark is around 70%, demonstrating that the benchmark poses a certain level of challenge.

Critical strengths
  1. Whether AI can be used to prove theorems in research papers is a question of interest to many scientists, and the motivation behind this benchmark is clear.

  2. The verifier developed in this paper achieves 90% agreement with human experts, which is a very good result for a verifier.

Critical weaknesses
  1. Lack of empirical analysis of benchmark difficulty. The paper uses Dependency Rank to measure task complexity and increases difficulty by hiding intermediate lemmas. However, the authors do not sufficiently demonstrate whether model performance actually decreases as the rank increases or more dependencies are hidden.

  2. Lack of fine-grained analysis of model reasoning capabilities. Beyond the overall success rates, the paper does not provide analyses of common failure modes, Pass@k, performance across different subfields of theoretical computer science, or the impact of long dependency chains on model capabilities.

Questions for authors
  1. The authors design the benchmark to be self-contained, and Section 3.5 explicitly states that model responses must follow the provided context and cannot rely on external sources: “All justifications must follow from results present in the provided context and the solver is prohibited from accessing the original paper or external sources.” However, how is this restriction enforced in practice? A model might use a higher-level mathematical theorem memorized during pretraining to complete a proof, even if that theorem is not provided in the context. Can the verifier identify cases where a model uses mathematical results beyond the provided context? How can the authors distinguish between general mathematical knowledge that is permissible to use in a proof and external research results that should not be cited? Since the benchmark is derived from papers published between 2020 and 2026, is it possible that some models encountered the original proofs during pretraining, resulting in data contamination?

  2. Are there any analyses of model performance on this benchmark beyond the final success rates? For example, are there any common failure modes? Is model failure correlated with the benchmark difficulty factors discussed by the authors, such as dependency rank and the hiding of intermediate lemmas? Can models improve their success rates through multiple attempts (Pass@k)? Are the specific differences or challenges involved in proving theorems from research papers, as opposed to mathematical theorems in general, reflected in the solutions generated by LLMs?

  3. In Section 4, the authors introduce an LLM-as-a-judge-based verifier agent to evaluate the tasks, achieving 90% agreement with human expert evaluations. Could this verifier be used to supervise model training or being used as a test-time verification to improve model performance on this benchmark?

  4. Were the data used to optimize the verifier prompt with GEPA independent of the data used to report the final 90% accuracy? Does the verifier achieve comparable accuracy across proofs of different difficulty levels and types?

I would be happy to reconsider my rating if the authors can adequately address the questions and concerns raised above.

Reviewer_HnR2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces TCS-BENCH, comprising 300 natural-language proof tasks constructed from STOC, FOCS, and SODA papers published between 2020 and 2026. Tasks are built through dependency extraction, context compression, and intermediate-result masking. An LLM verifier developed using expert-labeled proofs evaluates submissions. Under this verifier, GPT 5.6 Pro achieves 68% accuracy, while the Colosseum cross-model selection system reaches 71%. The benchmark targets contextual proof generation within research literature.

Critical strengths
  1. The benchmark addresses contextual dependencies in research proofs, requiring models to reason with bespoke definitions, established lemmas, and their relationships. Dependency graphs and intermediate-result masking provide a reasonable approach to systematically varying the mathematical support available to solvers.
  2. The construction includes structural and semantic quality filtering, and verifier development uses expert-labeled correct and incorrect proofs. Cross-model candidate selection is explicitly separated from final grading and has no access to reference proofs or human labels, avoiding answer-informed candidate selection.
Critical weaknesses
  1. Independent verifier evaluation is unclear. The paper does not specify the data split between GEPA prompt optimization and final testing, making it difficult to assess whether the reported accuracy above 90% generalizes to unseen proofs.
  2. Difficulty control lacks empirical validation. The paper does not compare the same theorems under different dependency masks, leaving the intended difficulty changes unverified.
Questions for authors
  1. Could you clarify the data split between GEPA optimization and final evaluation, and report accuracy and false-accept/false-reject counts for the deployed three-of-four voting rule on an untouched test set?
  2. Could you evaluate matched variants of the same target theorems under different dependency masks, to validate the proposed difficulty-control mechanism?
  3. Could you explain how you check that context compression and dependency masking do not inadvertently omit definitions, assumptions, or algorithm descriptions necessary to understand and prove the target statement, and provide supporting quality-assessment results?
  4. Section 3 links removing proofs from the input to avoiding memorization. Could you provide evidence addressing possible memorization of source proofs, or qualify this claim? Withholding a proof from the input does not rule out exposure during pretraining.

Minor Comment: The in-text citations use numerical references rather than the author–year format specified by the ICLR 2027 template. Please revise them accordingly.

Reviewer_8hZXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces TCS-Bench, a benchmark of 300 natural-language proof-generation tasks extracted from theoretical computer science papers. Its construction pipeline identifies dependencies between mathematical statements, assembles self-contained contexts, and withholds intermediate results to vary the reasoning required. The paper also develops an automated proof grader and evaluates several language models and an agentic proof-search system. The strongest reported configuration achieves a grader-assessed success rate of 71%.

Critical strengths
  1. Proof completion within a research paper's specialized definitions and intermediate results captures an aspect of mathematical reasoning that isolated competition problems do not directly assess. A reliable benchmark in this setting would be a useful resource for research-oriented model evaluation.

  2. Holding a target statement fixed while withholding intermediate results could distinguish combining supplied lemmas from reconstructing missing arguments. This design has diagnostic value beyond reporting a single aggregate success rate, although its intended effects still need empirical validation.

Critical weaknesses
  1. Section 1.1 reports evaluation on a held-out set of 100 expert-labeled proofs, whereas Section 4 describes constructing 50 correct and 50 incorrect proofs and optimizing the grader prompt on this alignment task to achieve over 90% accuracy. The relationship between the optimization and test sets is not specified. Being disjoint from the benchmark tasks does not establish that the reported test examples were held out from prompt optimization. Exact test counts, false-acceptance and false-rejection rates, and performance across proof-generating models are also missing. Since all headline results depend on this grader, this ambiguity materially limits confidence in both the reported success rates and small differences between systems. An untouched, paper-disjoint expert-labeled evaluation of the frozen grading procedure would directly address this concern.

  2. The validity and intended difficulty of the constructed tasks are insufficiently demonstrated. Dependency extraction, context pruning, compression, and semantic filtering involve language models, but the paper does not report an expert audit establishing that the final contexts retain the information required to prove their targets. Moreover, controllable difficulty is a central motivation, yet Figures 1-3 are schematic examples and the experiments do not compare matched variants with different intermediate results withheld. Dependency rank alone is not a validated difficulty measure when the relevant lemmas are supplied. These omissions make it difficult to distinguish reasoning failures from construction artifacts, or to assess what the difficulty progression measures. A targeted audit of final tasks and paired evaluations of difficulty variants would provide the most relevant evidence.

Questions for authors
  1. How were the 100 expert-labeled proofs divided between prompt optimization and final testing? Can you report exact error counts on a frozen-grader test set whose source papers were not used during optimization?
  2. Have experts checked that the final compressed contexts are sufficient for their target statements, rather than only checking the correctness of the original reference proofs? What issues were found?
  3. How are the 300 tasks distributed across source papers and difficulty variants? For the same target statement, how does withholding intermediate results affect success rates and failure types?
  4. Can you provide the frozen grader prompt, exact evaluation configurations, and main inference budgets? Please also clarify how the 32.77% entry in Table 1 is computed, since it does not correspond to an integer number of successes out of 300 in a single binary-scored run.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.