acceptodds
Under review as a conference paper at ICLR 2027

TCSALGBENCH: BENCHMARKING AUTOMATED PROVING FOR RESEARCH-LEVEL THEORETICAL COMPUTER SCIENCE

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.

Primary area:
datasets and benchmarks
Keywords:
LLM for Math, Benchmarks and evaluation, automated theorem proving, math reasoning, agentic reasoning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_QovAOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

TCSALGBENCH is a benchmark of 398 proof tasks from 138 STOC/COLT papers. To build the benchmark, the authors first extract a graph structure of the proof, select 1–4 headline theorems per paper, and then apply a fixed sequence of LLM-driven "repair" passes to make each statement self-contained (inserting definitions, notation, assumptions and information-access rules, stripping source-paper lemmas, and rewriting named algorithms as existence claims when algorithm design is part of the task). Provers receive the statement plus an offline library of cited prior work (but not the source paper) and must return a natural-language proof, which is graded by a 2-of-3 majority of GPT-5.5 judges. The paper evaluates ten model configurations under direct inference and 10-round prover–verifier discussion (best: GPT-5.6 Sol max, 23.6% five-run coverage), and four call-matched agent workflows on GPT-5.5 xhigh (discussion, root-only decomposition, MCTS, agentic planning; best five-run coverage 25.4% for planning). Validation consists of a manual fidelity/self-containment check of 61 statements (40 held out), an author check of 10 accepted proofs, an Opus 4.8 re-scoring, and a pre-/post-knowledge-cutoff split.

Critical strengths
  1. A novel LLM repair layer that enables a refreshable, "living" benchmark in an important, under-served area. Turning extracted theorems into fair proof-discovery tasks is the hard part of mining research papers, and the paper's fixed sequence of repair passes (App. B.3) targets exactly the failure modes generic extraction misses: completing paper-specific definitions and notation, preserving computational models and information-access/action-order rules, stripping source-paper lemmas, and rewriting named algorithms as existence claims with a check against unintended constructions. Because this is automated, the pipeline can generate versioned batches from newly released papers, which directly addresses contamination; the pre-/post-cutoff split (Fig. 8, Table 6) shows no consistent pre-cutoff advantage. Research-level TCS (algorithm design with sample/runtime guarantees) is also a good target for research-level proving. This is the main reason the work could be valuable to the community.

  2. A controlled setting for comparing agent designs. Using an offline sandbox with a fixed library of cited prior work, a fixed backbone, and matched call opportunities across four representative workflows (discussion, decomposition, MCTS, planning), while reporting token usage, is a useful framework for studying proof-agent design beyond single-model leaderboards.

Critical weaknesses

1. Benchmark quality and faithfulness. The low pass rate is not interpretable without a validity/ceiling estimate for the tasks. The paper markets low coverage (~24%) as evidence of difficulty, but a benchmark with broken tasks would also produce a low pass rate. Full human validation of all 398 tasks is not a reasonable expectation given the cost, but the human pass that was done reports too little to gauge dataset quality:

  • The manual check of 61 statements (40 held out; Sec. 3.1, App. B.4) is reported only as a single binary "faithful and self-contained" verdict. There is no rubric, no description of the reviewers or their expertise, no breakdown of which repair passes produced errors on the development set, and no check of whether tasks remain provable once source lemmas are withheld.
  • Since the repair passes intentionally modify statements (LLM-written standard definitions, notation/assumption normalization, pseudocode removal, and existence rewrites that may add an LLM-written scoping clause; App. B.3, E.1.2), the paper should report how often each pass fires and how faithfulness was judged. Terms that cannot be matched "remain unresolved" (pass 2), with no count of how many final tasks still contain such gaps. Prompts are given for only three of the ten passes.
  • The pipeline already collects cheap signals of broken tasks but does not report them: the judge prompts ask for "SPECIFICATION GAP" labels / flagging for human review, and provers can concede and request disproof attempts (App. E.2). Roughly three-quarters of tasks are never solved by any run; a small expert audit of a random sample of those would bound how much of the gap is difficulty versus defects.

2. Evaluation protocol issues. The evaluation protocol is not validated well enough to support the comparative conclusions.

  • Judge validity is checked only on 10 accepted proofs, reviewed by an author (Sec. 3.2, App. C.1). Rejected proofs are never audited, so false negatives are unknown, and the judge prompt explicitly biases toward rejection under any doubt (App. E.2.2) — which can depress scores on a benchmark that already looks hard.
  • Cross-family judge agreement is only reported as aggregate coverage counts with one alternative judge (Opus 4.8; Table 5), with no per-proof agreement, no third family, and Fable 5 not re-scored. On the agent comparison the two judges diverge materially (e.g., MCTS 96 vs. 84; discussion 84 vs. 72; Sec. 4.4) and even swap MCTS and root-only decomposition.
  • No error bars or variance are reported anywhere (only seed 1 and union-of-runs coverage), although 5–10 seeds were run. Agent differences of a few challenges (93 / 96 / 101) cannot be interpreted without this.
  • There is no iso-budget comparison. Workflows are matched on call opportunities (App. C.3), but realized tokens differ by ~5x (12.1M vs. 60.4M input; Table 8, measured on only 10 challenges), and the "one discussion run beats ten direct runs" claim compares ~454K input tokens per challenge against ~17K per call. The claim that the GPT-5.5 planning agent beats GPT-5.6 Sol max "demonstrating the effectiveness" of the agent (Sec. 4.1) compares different protocols and budgets, as the paper itself notes. Coverage-vs-compute curves are needed for the workflow conclusions.
Questions for authors

Questions that could change my assessment:

  1. Human audit details: Which tasks were included in the 61-statement manual review, and did the audited set include any tasks that no system ever solved? Who were the reviewers and what was their expertise, what rubric did they use, and what feedback or error types did they report (in particular on the 21 development challenges, and which repair passes caused those errors)?
  2. How often did judges emit SPECIFICATION GAP / flag-for-human-review labels, and how often did provers concede and request a disproof? What did inspection of those cases show?
  3. Faithfulness of repairs: For each repair pass, how many of the 398 challenges did it modify? In particular, how many existence rewrites added a scoping clause, and how many final challenges still contain unresolved terms? Could you include the prompts for all ten passes, and apply a back-translation consistency check (as in your Lean pipeline) to the natural-language statements?
  4. Judge validity: Can you report human audit of a random sample of rejected proofs (false-negative rate) in addition to accepted ones, similar to the audit of the accepted proofs?
  5. Can you report per-proof agreement (e.g., Cohen's kappa) between judges from multiple model families, including re-scoring Fable 5?
  6. Can you report mean ± std (or bootstrap CIs) across seeds for all model and agent results?
  7. Can you provide an iso-compute comparison (coverage vs. realized tokens or cost) for the agent workflows and for direct inference vs. discussion, with token usage measured on the full benchmark?
  8. What is the intended takeaway of the agent-workflow comparison? What should a reader conclude when agentic planning wins — that planning is a better design in general, that TCSAlgBench specifically rewards planning, or that it simply uses more tokens? Does the comparison tell us something about the benchmark itself (e.g., which tasks benefit from decomposition), or is it a separate agent-design study? Would the ordering hold with other backbones?

Clarification: 9. Beyond the 166 challenges, prompts, and the cited-document manifest, will you release the evaluation sandbox/code, the agent implementations, and the generated proofs/trajectories for all runs?

8 comments

We thank the reviewer for these questions. Every new number below was computed from our saved run artifacts. We added all tables to the appendix.

The gold set has 61 challenges from 20 papers randomly selected in each area: algorithmic fairness/calibration 21, learning theory 17, optimization 10, differential privacy 8, sampling 5. The appendix will list all 61 theorems and their papers. Only 15 were ever proven by different models or workflows and accepted by verifiers. The percentage proved is roughly the same between 61 and the whole dataset.

The expert review is conducted by the authors. The authors are theoretical computer scientists with expertise in learning theory, optimization, and sampling. The standard is that statements are understandable for humans with basic general knowledge in TCS. The error types identified during pipeline development on the 21 development challenges spanned topics primarily concerned self-containment, including missing definitions, undefined notation, and incomplete interaction rules. These observations guided the refinement of our TCS-specific repair rules and prompts. The pipeline is designed to preserve the source results’ assumptions, computational models, and quantitative guarantees while completing the context needed to interpret the target statements and withholding algorithmic constructions. In addition, we conducted a manual review of the final challenge statements to assess self-containment. We also checked for faithfulness, but it is more straightforward because the pipeline does not modify the statements unless explicitly instructed to in the prompts. This review covered the 21 development challenges and 40 additional challenges. All 40 additional challenges were judged faithful to the source results and self-contained.

These labels are emitted only by the in-loop verifier of our agent workflows, and they are not benchmark labels. The parser treats anything other than an explicit ACCEPT as a rejection, so neither label can close a node or change a score, and the external three-voter judge never uses them. Provers concede by writing CONCEDE and may request a disproof, and in all four agent-design workflows, DISPROVE was disabled, so such requests became further proof rounds. We believe this option might be helpful when the statement's correctness is less clear.

We provide these data anyway, but we note SPECIFICATION GAP is in-loop only. We inspect and believe this is just a way for models to say they give up proving the theorem. The SPECIFICATION GAP label appears in 44–67% of in-loop verifier turns and on 71–90% of challenges, and the human-review flag appears in 2.3–3.1% of turns. 71–94% of proof attempts end in CONCEDE, and 29–45% of those concessions point to a disproof.

For the 10 stages in the pipeline, we show the edits at each stage. The scaling set is the rest of the dataset generated through the pipeline.

PassGoldScaling Set
1 make_challenges61337 (verifier added 109 definitions)
2 resolve_notes48236
3 add_standard_defs23120
4 attach_internal_refs1565
5 resolve_statement_labels2053
6 attach_paper_notation59307
7 attach_protocols84
8 harmonize_assumptions1231
9 strip_lemma_blocks166
10 existential_rewrite1617

Most edits attach verbatim paper text and are edits to the statement itself. There are 33 scoping clause (existences rewritten) out of 398. Our pipeline added definitions for unresolved terms for 309 out of 398 challenges. We only call a challenge finished when the pipeline claims it does not have any unresolved terms in the end. The consistency check implementation seems unclear, since the statement should not be exactly equivalent after we intentionally omit some information. We do want to note that text editing is only allowed in the ways we specified in the prompt.

The verbatim prompts of all ten passes are in the appendix.

  1. We note that 99% of the ~56700 failed runs for direct inference or 10 rounds of discussion never produced a proof the in-loop verifier accepted. We only have 116 proofs accepted by the internal verifier and then rejected by the final verifier. We ran Astra on the proofs, and only 8 are accepted, in which Astra believes the errors pointed out by GPT 5.5 are fixable. We found the most common mistake is that a proof delegates its hardest step to a result it never establishes.

On 1,079 proofs scored by both families (three votes each), GPT-5.5 and Opus 4.8 accept almost the same number (469 vs 470) but agree on 79.7%: Cohen's κ = 0.59. Voters agree more within a family (Fleiss: κ 0.76 and 0.84) than across families (pairwise: κ 0.55). We re-scored a random sample of 177 proofs with three Fable 5 votes: κ = 0.61 [0.48, 0.74] with GPT-5.5 and 0.85 [0.76, 0.93] with Opus 4.8 (GPT-5.5 vs Opus on the same sample: 0.65). We report these next to the ranking-stability result and qualify the abstract: rankings are preserved, while per-proof agreement across families is moderate (κ ≈ 0.6).

We note that natural proof verification without formalization is still an interesting ongoing direction. For this work, we want to compare models and workflows, so an estimate consistent across models is sufficient. However, better models and workflows developed in the future will definitely make our work even more useful in other ways, like post-training.

We incorporate comprehensive tables reporting per-run mean ± sd across seeds alongside 95% bootstrap confidence intervals over challenges (10,000 resamples) for each model and agent configuration. Resampling across the 138 source papers expands these intervals by no more than 30% without altering any key conclusions. Full challenge coverage is maintained across all direct inference (10 seeds) and discussion runs (5 seeds). Direct inference (per-run acceptances): GPT-5.6 Sol max 23.9 ± 3.0, xhigh achieves 18.4 ± 3.0, and high yields 15.2 ± 2.5. GPT-5.5 11.6 ± 1.5 (xhigh) and 7.4 ± 1.2 (high). Fable 5 logs 20.7 ± 2.7 (xhigh) and 24.3 ± 3.9 (high). Opus 4.81.1 ± 0.9 (max), 1.1 ± 0.7 (xhigh), 1.2 ± 0.9 (high)

Discussion agent (per-run acceptances): Sol 73.2 ± 2.5 (max), 65.6 ± 2.5 (xhigh), and 53.8 ± 3.7(high). GPT-5.5 45.2 ± 4.6 (xhigh) and 42.0 ± 4.6 (high). Fable 5 39.2 ± 4.0 (xhigh), 40.8 ± 3.7(high). Opus 4.8 9.4 ± 2.1 (max), 9.2 ± 1.1 (xhigh), 8.6 ± 0.9 (high).

For workflow runs. Discussion with no decomposition is 66.2 ± 3.5, Root-only 68.2 ± 3.6 MCTS 70.0 ± 3.7 Agentic planning 75.2 ± 4.0.

Due to time and cost constraints, we cannot finish the sweep of the whole benchmark. But we can provide an estimation for the answer to your question using a smaller sample size (10 samples). For agent workflows, agentic planning consumes 5.0× as many input tokens and 9.0× as many output tokens as a discussion without decomposition, and uses 2.4× as many input tokens as root-only decomposition. Under seed 1, it yields 72 accepted challenges against 73 for root-only and 77 for MCTS. However, it yields 101 across five runs, indicating the highest potential for solving hard problems.

Our benchmark design is more from a user’s perspective. As TCS researchers, the authors have one question: If I have a hard TCS question I want to work on, I want to give my agent a few hours to explore which workflow I should use. I care more about whether the problems can be solved within a fixed time period, as long as the cost difference is reasonable. Accordingly, all workflows ran with the same GPT-5.5 backbone, iteration cap, and 5-hour wall-clock limit.

First, the basic takeaway: could a more complex agent workflow be helpful for solving hard problems? The answer is yes, based on our experiment. We show a gap between no decomposition and a better workflow with 60 vs 77 (MCTS) in seed 1 and 84 vs 101 (agentic planning) in 5 runs.

Second, if I want to design my own workflow, what model should I use, and what is the most important design I should have? We answer this question by showing that GPT 5.6 sol achieved SOTA in the models we tested. We further found that agentic planning gives us the most coverage. As a TCS researcher, I believe that solving hard TCS problems, or even math problems, would benefit from good decompositions. The ordering may not hold for other backbones and is worth testing in the future, but we note that the order aligns with our intuition, and our benchmark shows it has sufficient quality for people to test their workflows and identify the best workflow.

We note that the sandboxes are easy to reconstruct since they used arXiv papers listed in the previous work, which may not have the right licenses for us to release. However, all those papers with TeX on arXiv are easily accessible directly on arXiv. The code and agent implementations are very straightforward, as shown in the prompts we provided in the appendix. The only algorithm with hyperparameters is MCTS. We specify them in the appendix. Release of the generated proofs and trajectories is subject to legal review and approval. Meanwhile, we are happy to provide further clarification should the reviewer have additional questions concerning our implementation.

In particular, we want to mention that in TCS, lemmas are intermediate results for a final theorem. The Lemma is part of the proof that a prover should be generated. The correctness of the proof may be affected by missing assumptions but not lemmas.

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

This paper proposes an expert-designed data construction pipeline for extracting self-contained TCS theorem-level challenges from papers. Based on this pipeline, this paper introduces a benchmark, TCSAlgBench, consisting of 398 challenges from top-tier TCS papers. Frontier models and diverse workflows are evaluated on the benchmark. A subset of TCSAlgBench is formalized into highly challenging Lean 4 statements.

Critical strengths
  1. Scalable data construction pipeline. The elegant pipeline has the potential to mine RLVR training samples from existing literature, and maintain a rolling benchmark based on papers published in recent top conferences/journals and preprints.
  2. Comprehensive evaluation. Frontier models and diverse agentic workflows are evaluated. The results provide insights for future researchers.
Critical weaknesses
  1. Limited human validation. Only 61/398 challenges of TCSAlgBench are reviewed by human experts.
Questions for authors
  1. Could the authors provide more details about the manual review process for TCSAlgBench? e.g., how many reviewers were involved, their expertise, how the challenges were selected, and inter-reviewer agreement.
  2. Could the authors sample some formalized Lean 4 statements for review by human experts or frontier models such as GPT-6-Astra, and report the accuracy of formalization?
3 comments

We thank the reviewer for these questions.

The gold set has 61 challenges from 20 papers randomly selected in each area: algorithmic fairness/calibration 21, learning theory 17, optimization 10, differential privacy 8, sampling 5. The appendix will list all 61 theorems and their papers. Only 15 were ever proven by different models or workflows and accepted by verifiers. The percentage proved is roughly the same between 61 and the whole dataset.

The expert review is conducted by the authors. The authors are theoretical computer scientists with expertise in learning theory, optimization, and sampling. The standard is that statements are understandable for humans with basic general knowledge in TCS. The error types identified during pipeline development on the 21 development challenges spanned topics primarily concerned self-containment, including missing definitions, undefined notation, and incomplete interaction rules. These observations guided the refinement of our TCS-specific repair rules and prompts. The pipeline is designed to preserve the source results’ assumptions, computational models, and quantitative guarantees while completing the context needed to interpret the target statements and withholding algorithmic constructions. In addition, we conducted a manual review of the final challenge statements to assess self-containment. We also checked for faithfulness, but it is more straightforward because the pipeline does not modify the statements unless explicitly instructed to in the prompts. This review covered the 21 development challenges and 40 additional challenges. All 40 additional challenges were judged faithful to the source results and self-contained.

We rerun the Lean formalization pipeline, and it passes 150 Lean statements. However, Fable 5 passed 220 Lean statements. We note that there does exist an inconsistency between models as judge for Lean statement and natural language translation consistency. We believe this could be an interesting future direction and our pipeline can be used to generate more statements for such tests.

Thank you to the authors for this rebuttal. Although your response does not fully address my concerns, I will maintain my positive rating for this submission.

We sincerely thank the reviewer for taking the time to review our manuscript and for their positive and encouraging feedback.

Reviewer_d5MsOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces TCSAlgBench, a benchmark of 398 natural-language proof challenges extracted from 138 STOC and COLT 2026 papers. Its construction pipeline supplies necessary context while withholding proofs and algorithmic constructions. The paper evaluates ten model configurations and four agent workflows using LLM-based proof verification.

Critical strengths

The benchmark addresses a valuable evaluation problem. Research-level theoretical computer science provides meaningful tasks that combine algorithm design, precise assumptions, and quantitative guarantees. A reusable pipeline that converts research results into self-contained proof challenges could support systematic evaluation beyond competition mathematics.

Critical weaknesses
  1. The reliability of automated challenge construction is insufficiently established. Only 61 of the 398 challenges were manually reviewed, including 21 used to develop the construction rules. The Opus 4.8-based pipeline performs substantive mathematical transformations, but the paper does not systematically quantify construction errors or their impact on the reported results.

  2. Prior exposure and answer leakage remain insufficiently controlled. Blocking access to the source paper during evaluation does not exclude training exposure to its results or access to equivalent results and substantially overlapping proofs. The pre-/post-cutoff comparison provides indirect evidence.

  3. The final proof scores lack sufficient independent validation. Acceptance is determined by majority voting across three GPT-5.5 judgments. Re-scoring with Opus and manually checking only ten accepted proofs provide limited evidence of verification reliability across the 398 problems.

Questions for authors
  1. How were the manually reviewed challenges selected, and can you provide a broader independent audit of statement fidelity and self-containment? Do the main findings hold on the manually validated subset?

  2. Can you expand expert verification to include both accepted and rejected proofs, particularly cases where GPT-5.5 and Opus disagree? What are the estimated false-acceptance and false-rejection rates?

  3. What recurring failure patterns emerge from unsuccessful attempts? Can you distinguish these reasoning failures from defective problem statements or incorrect verifier judgments?

1 comment

We thank the reviewer for these questions.

The gold set has 61 challenges from 20 papers randomly selected in each area: algorithmic fairness/calibration 21, learning theory 17, optimization 10, differential privacy 8, sampling 5. The appendix will list all 61 theorems and their papers. Only 15 were ever proven by different models or workflows and accepted by verifiers. The percentage proved is roughly the same between 61 and the whole dataset.

The expert review is conducted by the authors. The authors are theoretical computer scientists with expertise in learning theory, optimization, and sampling. The standard is that statements are understandable for humans with basic general knowledge in TCS. The error types identified during pipeline development on the 21 development challenges spanned topics primarily concerned self-containment, including missing definitions, undefined notation, and incomplete interaction rules. These observations guided the refinement of our TCS-specific repair rules and prompts. The pipeline is designed to preserve the source results’ assumptions, computational models, and quantitative guarantees while completing the context needed to interpret the target statements and withholding algorithmic constructions. In addition, we conducted a manual review of the final challenge statements to assess self-containment. We also checked for faithfulness, but it is more straightforward because the pipeline does not modify the statements unless explicitly instructed to in the prompts. This review covered the 21 development challenges and 40 additional challenges. All 40 additional challenges were judged faithful to the source results and self-contained.

We note that 99% of the ~56700 failed runs for direct inference or 10 rounds of discussion never produced a proof the in-loop verifier accepted. We only have 116 proofs accepted by the internal verifier and then rejected by the final verifier. We ran Astra on the proofs, and only 8 are accepted, in which Astra believes the errors pointed out by GPT 5.5 are fixable. We found the most common mistake is that a proof delegates its hardest step to a result it never establishes. We also inspected a bit of Opus 4.8 vs GPT 5.5. We found some contrasting behaviors: Opus is overly strict about exact citation rules, while GPT sometimes accepts false citations. This is a very interesting observation.

The reasoning failure usually means the problem is too hard for the models. Defective problem statements with missing definitions are more likely to make problems easier, since they give models more flexibility in understanding the statements. For verifier judgment, we can check the proofs that the models and workflow claims are correct, but are not accepted by the external verifiers. We found this is a limited case as shown in the answer to the previous question. Of course, perfect natural-language proof verification remains an interesting direction for future research. This is also why we show our benchmark can serve as a Lean formalization dataset. We believe we can distinguish the reasoning failures from defective problem statements or incorrect verifier judgments.

Further, we want to address the reviewer’s comment on prior exposure. Our pipeline’s main contribution is that we provide a pipeline for live generating benchmarks from recent works. If a work is released after the cutoff date, the model cannot train on it. The only way models are trained on this data is through authors chatting with the models, and the company uses user data to train them. From my understanding, this is unlikely to happen nowadays, and TCS work tends to span several months for the authors, and it is very unlikely that the recent chat history was used for training.

Comments on the paper

1 comment

Dear Area Chair,

We thank Reviewers d5Ms, uFsg, and QovA for their careful reviews. We summarize our paper contribution as follows:

  1. The construction pipeline. All three reviewers highlight the automated, reusable pipeline that turns theorems from research papers into self-contained TCS proof challenges. Reviewer QovA calls it “the main reason the work could be valuable to the community.” Our pipeline contains detailed steps to include the right information, with prompt-specified edition of the theorem statement allowed. Hence, it preserves correctness and further ensures self-containment.

  2. A refreshable benchmark for research-level TCS. Reviewer QovA and d5Ms describe the area as “important and under-served”, and the benchmark as a way to evaluate proving “beyond competition mathematics.” Because of our automated construction design, versioned batches can be generated from newly released papers. Reviewer uFsg kindly suggests further use in mining RLVR training samples from the literature.

  3. A comprehensive and controlled evaluation. As reviewers uFsg and QovA point out, our intended sandbox study with fixed cited prior work, backbone, and wall-clock limit makes a useful framework for studying proof-agent design for models and workflows.

We also want to address some common questions from reviewers.

  1. Benchmark pipeline validation (d5Ms, uFsg, QovA): We clarified the author-led review of 61 statements: 21 development challenges and 40 additional challenges. All 40 additional challenges were judged self-contained and faithful. Following QovA’s suggestion, an expert author also audited 30 randomly sampled challenges associated with disproof requests. Of these, 27 were judged self-contained and faithful, while three had missing definitions or context attributable to pass 4. We reported the affected challenges and will correct these statements in the next dataset release.

  2. Verification (d5Ms, QovA): We added κ analysis for different verifier models (GPT 5.5 and Opus 4.8) and seed-variance reporting. QovA acknowledged that these additions, together with the per-pass edit counts in the benchmark pipeline, resolved their reporting concerns. Inspection of selected internal–external verifier disagreements revealed that many of these disagreements are caused by proofs that rely on essential intermediate results they had not established.

  3. Workflow comparison (QovA). We reframed the comparison under a shared five-hour wall-clock limit using the same GPT-5.5 backbone. Planning achieved the highest observed five-run coverage, while MCTS achieved higher seed-1 acceptance. We report token usage alongside coverage and have removed claims that planning is a more effective design.

Thank you again for your time and consideration.

Yours,

Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.