- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3(+1)
- Soundness
- 3(+1)
Read review
Paper summary
This paper introduces TCSExam, a benchmark of 100 TCS research tasks in four tracks (theorem proving, solver engineering, constructions, and open conjectures), where every submission is checked by the Lean kernel or an executable task checker. Across six frontier LLMs, the authors find large differences in theorem proving, while no system resolves an open conjecture, some attempts yield verified special cases.
Critical strengths
-
Every submission is checked by the Lean kernel or an executable task checker, so each accepted result comes with a formal or computational guarantee. The authors also check statement fidelity, test the checkers on invalid outputs, and audit the rollouts whenever a result exceeds the reference. Hence the evaluation is rigorous and reproducible.
-
The open conjectures track produces verified mathematical results. GPT-6-Astra proves the Alon–Jaeger–Tarsi conjecture over F₅ for all n ≤ 9. This goes one dimension beyond the most recent reported range, which is a concrete example of an LLM pushing the frontier of a TCS problem with a formally verified result.
Critical weaknesses
None
Questions for authors
Appendix C.3 notes that over 40 theorem problems were retired after being solved in pilot evaluations. Since this selection depends on how the screening system performs, it can affect any comparison that involves that system, as the authors also acknowledge. Could the authors specify which system was used for screening, and report how the six evaluated systems perform on the retired problems?
Response to Reviewer jzxN
Thank you for recognizing TCSExam's verification methodology, reproducibility, and independently verified mathematical results, and for finding no critical weaknesses. Your question about problem selection helps us clarify how the task set was formed.
Selection model and process. We used Kimi K3 for problem selection, task authoring, and preliminary difficulty screening. Theorem candidates first underwent a single bare-proof trial; candidates that K3 could prove in one attempt were prioritized for removal. Final selection considered difficulty, research significance, and domain representation together. During development, 17 batches of early pilot experiments covered 86 candidates, totaling 365 trial runs with grading; 43 candidates were removed after K3 proved them in bare-proof screening. This process aimed to assemble challenging research tasks, on which the main experiments compare agents' performance.
Task quality was also continually improved through interaction among human developers, K3, and Astra: questions about definitions, assumptions, or formalization arising during solving prompted checks against the original sources, revisions, and alternating retests. Overall Q2 provides the full development process, statistics, and concrete examples.
Six-model comparison on retired problems. We have not conducted a six-model comparison across all retired problems. Given the cost of long-horizon agent evaluation, we prioritized thorough evaluation of the retained problems and comparisons with additional frontier models.
We also added model results and evaluation options that are more accessible to the community. Full now includes Kimi K3.1 Pro and DeepSeek V4.1 Flash 1017, with three attempts per problem each; the 20-problem Lite further includes Opus 5.5, bringing coverage to eight agents on Full and nine on Lite. Lite was selected using the original six agents' results. After adding the later models, the Full/Lite rank correlation across the eight shared agents remains 0.93. These results demonstrate the task set's ability to distinguish new agents and offer the community a lower-cost evaluation option. See Overall: Lite, Index, and Additional Model Evaluations for detailed results.