- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces FormalTCS, a benchmark containing 143 research-level theoretical computer science problems from papers accepted to STOC, FOCS, SODA, and COLT in 2025–2026.
Each instance includes a core claim, natural-language theorem and proof, and corresponding Lean statements and verified proofs. The benchmark evaluates four stages: theorem elicitation, autoformalization, proof elicitation, and formal theorem proving.
Experiments show that autoformalization achieves only 11.2 at best, compared with 28.7% Pass@8 for formal theorem proving. The authors additionally propose an automated research framework, where 6 of 64 generated claims pass expert evaluation and formal verification.
Critical strengths
-
FormalTCS addresses an important gap between existing mathematical reasoning benchmarks and realistic TCS research. The dataset covers recent research papers across 13 TCS areas and includes substantial, paper-specific mathematical dependencies. Importantly, providing complete, expert-reviewed Lean proofs for 143 research-level problems is a significant contribution beyond benchmarks containing only formal theorem statements.
-
The decomposition into four evaluation tasks offers useful insights into different stages of mathematical research. The experiments across multiple model families provide evidence that formalization and proof construction remain challenging. The additional research-generation experiments also offer an interesting preliminary investigation of the difficulty of producing novel theoretical claims.
Critical weaknesses
-
The paper identifies autoformalization as the primary bottleneck, largely based on its substantially lower score compared with other tasks. However, these tasks use different evaluation metrics. In particular, NT2FT uses BEq+ to establish bidirectional theorem equivalence, while FT2FP uses Pass@8 for proof verification. Since automated equivalence proving is incomplete, a mathematically correct formalization may fail BEq+ simply because the equivalence prover cannot establish the required proofs. Similarly, natural-language tasks are evaluated using LLM-based rubrics, making their scores difficult to compare directly with formal verification rates. Consequently, the reported performance gaps do not conclusively establish that autoformalization is intrinsically the most difficult stage. Additional validation of the evaluation metrics would strengthen this conclusion.
-
Although the paper emphasizes end-to-end TCS research, the main benchmark evaluates each stage independently using human-annotated inputs. This avoids error propagation but does not directly measure complete research-pipeline success. The research-generation experiment partially addresses this limitation, but its conclusions rely on only 64 generated claims, with human experts determining novelty and research value. The paper provides limited analysis of evaluation consistency, generation diversity, and the role of human intervention. Without additional controls or comparisons, it is difficult to distinguish limitations in research taste from limitations introduced by the particular generation framework and evaluation protocol.
Questions for authors
-
How often does BEq+ reject semantically correct formalizations because its proof search fails? Could the authors manually inspect a sample of unsuccessful NT2FT outputs to estimate false-negative rates?
-
Can the authors report the actual success rate of sequentially executing the complete pipeline, where each stage receives the previous stage's generated output rather than a human-annotated reference?
-
For the six successfully verified generated claims, what human interventions were required during formalization and proving? How was novelty established, and how consistent were the independent expert judgments?
-
Could the authors provide per-domain performance breakdowns and clarify the computational budgets allocated to different models and harnesses?