A new preprint testing large language models on formal theoretical computer science found a sharp gap between generating proof ideas in ordinary language and expressing theorems in a form a proof checker can verify. Its FormalTCS benchmark contains 175 instances drawn from STOC, FOCS, SODA and COLT papers accepted in 2025 and 2026. Claude Opus-5 had the strongest showing on most tasks, scoring 68.7 for natural-language proof elicitation and 11.5 for theorem formalization.
The hardest step is the translation
The benchmark divided the research process into four tasks: theorem elicitation, autoformalization, proof elicitation and theorem proving. The first and third tasks used an LLM-based scoring rubric. Autoformalization required a Lean theorem to be equivalent to a reference statement in both directions, while theorem proving used Pass@k—the chance that at least one of several attempts would be accepted by Lean. The formal tasks used eight candidate outputs per instance; the natural-language tasks used one.
The contrast was similar for GPT-5.6-SOL: its proof-strategy score was 67.9, compared with 10.6 for theorem formalization. Across the evaluated models, autoformalization was the lowest-scoring stage, with no model exceeding 11.5. Formal proof generation reached 28.6 Pass@8 when a human-annotated formal theorem was supplied. The authors identify the translation into formal mathematical language as the main bottleneck.
Six claims survived a tougher test
In a separate exploratory experiment, the authors used a three-agent framework made up of a planner, a formalizer and a judger. The formalizer could use at most three rounds of compiler feedback, and candidates that still failed to compile were discarded.
The framework synthesized 64 core claims. Experts removed claims already established in the literature, then assessed novelty and potential theoretical value; each candidate was independently reviewed by two experts, with no automated claim-quality evaluator. Six claims remained after human evaluation and proof verification.
A useful scorecard, with clear limits
Human review was built into the benchmark. Five experts with substantial theoretical computer science research experience took part in annotation, while language models were used only as assistive tools and final annotations were manually inspected and revised when necessary. Agreement between experts was 86% for core claims, 90% for natural-language claims and 93% for formal-language proofs. LLM-assisted outputs required substantive revision at rates ranging from 13% to 31%.
The scorecard was not a single fully chained run: each task received human-annotated inputs independently, so a model’s output at one stage was not automatically passed into the next. The benchmark also covers selected papers from four conferences and two accepted-paper years, meaning the results describe this test set rather than theoretical computer science as a whole.
An output-only black-box audit found aggregate completion similarity below 9.6% for both queried models. The authors treated that as relatively low contamination risk, but not as proof that the source papers were absent from model training data.
Taken together, the study’s strongest evidence concerns high-level reasoning, formalization and claim screening inside a controlled benchmark. It does not establish that language models can conduct reliable, open-ended autonomous theoretical computer science research.
Paper data and sources
Original title: FormalTCS: Benchmarking End-to-End Frontier Formal Theoretical Computer Science Research of Large Language Models
Authors: Dingzirui Wang, Xuanliang Zhang, Keyan Xu et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text