acceptodds
Under review as a conference paper at ICLR 2027

FormalTCS: Benchmarking End-to-End Frontier Formal Theoretical Computer Science Research of Large Language Models

Abstract

Large language models (LLMs) have shown growing capabilities for automated theoretical computer science (TCS) research, while existing benchmarks remain far from realistic research settings. We introduce FormalTCS, a benchmark for evaluating LLMs on frontier, end-to-end TCS research. FormalTCS contains 143 instances drawn from papers accepted to top-tier TCS conferences in 2025-2026. For each instance, we annotate the theorem statements and proof processes in both natural and formal languages to evaluate the main bottlenecks of existing LLMs in TCS. Evaluations of leading LLMs reveal that current models remain far from reliably completing the full TCS research pipeline. In particular, we reveal that autoformalization is the sharpest bottleneck of TCS auto research, where the best model achieves only 11.5 for translating natural-language claims into formal theorem statements, compared with 28.6 Pass@8 when proving human-provided formal statements. Building on FormalTCS, we further develop an automated TCS research framework that generates, formalizes, filters, and proves new claims. Of 64 generated claims, only 6 ultimately pass expert evaluation and proof verification, indicating that beyond formalization, limited research taste remains another major barrier to autonomous TCS research.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Large Language Model, Theoretical Computer Science, AI4Science, Benchmark

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_4AyZOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. 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?

  2. 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?

  3. 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?

  4. Could the authors provide per-domain performance breakdowns and clarify the computational budgets allocated to different models and harnesses?

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

The paper introduces FormalTCS, a benchmark containing 143 instances from recent TCS conference papers across 13 research areas. It evaluates theorem elicitation, autoformalization, informal proof generation, and formal theorem proving, supported by expert-reviewed Lean formalizations. The experiments identify autoformalization as a major bottleneck. An additional multi-agent research framework produces 64 candidate claims, of which six pass expert evaluation and proof verification.

Critical strengths
  1. The benchmark addresses an important gap in evaluating research-level TCS reasoning. Collecting recent research theorems with expert-reviewed formal statements and proofs represents a substantial and potentially useful contribution.
  2. The four complementary tasks enable more detailed capability analysis than a single proof-generation score. The annotation cross-checks and strict Lean verification provide useful quality controls.
Critical weaknesses
  1. Cross-task scores are not directly comparable. §4.2 compares weighted rubric scores with binary verification success rates; their numerical gap alone does not establish relative task difficulty.
  2. The explanation for higher proof success on self-generated claims lacks a controlled comparison. §5.2 compares screened, model-generated claims with research-paper theorems, without separating self-generation from differences in difficulty and screening.
Questions for authors
  1. Could you manually audit a sample of compilable candidates rejected by BEq+ to distinguish genuine semantic errors from potentially correct formalizations whose equivalence the checker fails to establish? Please specify how different mathematical representations are handled, along with the equivalence-checking search configuration and budget.
  2. When a short core claim admits multiple mathematically valid theorem statements consistent with the input, how does CC2NT score these alternatives? Does scoring require recovering source-paper definitions, assumptions, or quantitative bounds not explicitly provided in the input?
  3. Could you report the time, token, and tool-call budgets, along with the reasoning settings, for each model and harness in the main experiments? Beyond the inputs listed in Table 3, is retrieval or access to reference materials, including the source papers, permitted?
Reviewer_5CuNOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces FormalTCS, a benchmark of 143 research theorems drawn from recent STOC, FOCS, SODA, and COLT papers, with natural-language claims, theorem statements, proof sketches, and expert-verified Lean proofs. It evaluates LLMs across four stages of theoretical computer science (TCS) research: theorem elicitation, autoformalization, proof elicitation, and formal theorem proving. The results show a substantial gap between natural-language reasoning and formal tasks, with the best model achieving only 11.2% on autoformalization and 28.7% Pass@8 on formal theorem proving. An additional agent-based research experiment generates 64 candidate claims, of which only six survive expert evaluation and formal proof verification, highlighting the difficulty of producing novel and valuable research ideas.

Critical strengths
  • A valuable benchmark grounded in real research problems. FORMALTCS contains 143 theorems from recent top-tier TCS papers and covers 13 research areas. By providing natural-language and Lean representations alongside verified proofs, it moves beyond textbook-style theorem proving and offers a more realistic test of research-level formal reasoning.

  • Careful annotation and useful diagnosis of model limitations. The authors involve five TCS experts, conduct independent checks, and verify the formal proofs against proof-bypassing shortcuts. The reported inter-expert agreement rates of 86%, 90%, and 93% for core claims, natural-language theorems, and formal proofs, respectively, provide useful evidence of annotation quality. More importantly, the four-task decomposition helps identify where current systems struggle, making the benchmark useful for guiding future work on autoformalization and automated theorem proving.

Critical weaknesses
  • The main benchmark evaluation does not directly measure end-to-end performance. In Section 4, each task receives human-annotated inputs rather than the outputs of the preceding stage. This is a reasonable choice for isolating individual bottlenecks, but it does not measure error propagation or the probability of completing the entire research pipeline successfully. The additional agent-based experiment is a useful proof of concept, but generating 64 claims and obtaining six expert-approved, formally verified results is insufficient to establish robust autonomous research capability. The paper should distinguish more clearly between stage-wise capability evaluation and end-to-end research performance.

  • The main autoformalization conclusion would benefit from a stronger evaluation analysis. The four tasks use different metrics: LLM-based rubric scores for natural-language tasks, BEq+ for theorem equivalence, and Pass@8 for formal proving. In particular, BEq+ requires proving equivalence in both directions, so a semantically correct formalization could potentially fail if the equivalence checker cannot establish the required proofs. Without an audit of failed candidates or a sensitivity analysis of the equivalence-checking procedure, it is difficult to determine how much of the low autoformalization score reflects incorrect formalization versus limitations of the verification procedure. The finding that autoformalization is a major bottleneck is plausible, but its magnitude is not fully isolated by the current evaluation.

Questions for authors
  1. End-to-end evaluation: Can the authors report an experiment in which the outputs of each stage are fed directly into the next stage, with the final Lean-verified success rate and a breakdown of error sources? This would clarify how the stage-wise results translate into actual end-to-end performance.

  2. Reliability of the autoformalization metric: What proof-search budget and timeout settings are used by BEq+? Have the authors manually inspected a sample of failed formalizations to distinguish semantically incorrect statements from equivalent statements for which the checker failed to find proofs? This distinction could materially affect the interpretation of the reported 11.2% result.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.