Theory-Scale Auto-Formalization of Logics for Computer Science
Yuming Feng, Frederick Pu, One An, Osbert Bastani, Li Zhang, Jiani Huang, Xujie Si, Ziyang Li
cs.LG
Jun 25, 2026 · v1
cs.LO cs.PL
TL;DR
Introduces LCS-Bench, a theory-scale Lean 4 benchmark with 4,076 declarations and 85K lines of code for evaluating auto-formalization.
Abstract
Auto-formalization is critical for scalable formal verification, but existing progress largely focuses on isolated statements, while theory-scale auto-formalization, which coherently translates hundreds of interdependent definitions, lemmas, and theorems, remains open due to challenges in consistency, faithfulness, scalability, and correctness. In this paper, we introduce LCS-Bench, a stand-alone, theory-scale benchmark based on Logics for Computer Science. LCS-Bench is built through a novel semi-automated agentic pipeline that leverages concept graphs, formal signature planning, issue tracking, sorry-filling with counter-example search, complemented by faithfulness review from human experts. The resulting artifact covers 327 textbook items, over 4,076 Lean declarations, and more than 85K lines of Lean code. The dataset supports broad evaluation through a data engine that automatically derives five tracks of evaluation benchmarks, measuring different aspects of auto-formalization and theorem-proving capabilities. We also introduce a novel evaluation protocol featuring definitional equivalence checkers, enabling more fine-grained and faithful assessment. Through extensive evaluation on 14 models, we demonstrate that (1) LCS-Bench is of high quality, consistent, and faithful; (2) the benchmark is challenging, with state-of-the-art models achieving only 20.1% on auto-formalization tasks; and (3) our analysis reveals key findings regarding theory-scale auto-formalization and suggests promising directions for future work.
Problem
Theory-scale auto-formalization (coherently translating hundreds of interdependent definitions and theorems) remains open, with existing work limited to isolated statements.
Approach
The authors build LCS-Bench through a semi-automated agentic pipeline using concept graphs, formal signature planning, sorry-filling with counter-example search, and human faithfulness review. The benchmark covers 327 textbook items from Logics for Computer Science as 4,076 Lean declarations. A data engine derives five evaluation tracks, and a novel definitional equivalence checker enables fine-grained assessment.
Results
State-of-the-art models achieve only 20.1% on auto-formalization tasks across 14 evaluated models, confirming the benchmark is challenging. The artifact covers over 85K lines of Lean code.