ProofFlow: A Dependency Graph Approach to Faithful Proof Autoformalization
Rafael Cabral, Tuan Manh Do, Yu Xuejun, Wai Ming Tai, Zijin Feng, Xin Shen · 2025
Read ProofFlow: A Dependency Graph Approach to Faithful Proof Autoformalization by Rafael Cabral, Tuan Manh Do, Yu Xuejun, Wai Ming Tai, Zijin Feng, Xin Shen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-15981.txt.
Introduction
Rafael Cabral and five co-authors present ProofFlow, a pipeline that turns human proofs into machine-checked code without mangling the argument. Translating theorems into verifiable form is key to using language models in rigorous maths, yet current tools often produce code that runs while losing the original meaning and logical shape.
ProofFlow first draws the proof as a directed acyclic graph of dependencies between steps. Each step is then formalised as its own intermediate lemma, which preserves the structure of the human argument. To judge such work they add a benchmark of undergraduate problems with hand-annotated steps and graphs, plus ProofScore, a metric joining syntactic correctness, semantic faithfulness, and structural fidelity. Their pipeline sets a new best score, far above whole-proof and step-by-step baselines, and all parts are open-sourced.
Catalog record
| CREATOR | Rafael Cabral, Tuan Manh Do, Yu Xuejun, Wai Ming Tai, Zijin Feng, Xin Shen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-15981
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ProofFlow: A Dependency Graph Approach to Faithful Proof Autoformalization Rafael Cabral, Tuan Manh Do, Yu Xuejun, Wai Ming Tai, Zijin Feng, Xin Shen Abstract Proof autoformalization, the task of translating natural language theorems and proofs into machine-verifiable code, is a critical step for integrating large language models into rigorous mathematical workflows. Current approaches focus on producing executable code, but they frequently fail to preserve the semantic meaning and logical structure of the original human-written argument. To address this, we introduce ProofFlow , a novel pipeline that treats structural fidelity as a primary objective. ProofFlow first constructs a directed acyclic graph (DAG) to map the logical dependencies between proof steps. Then, it employs a novel lemma-based approach to systematically formalize each step as an intermediate lemma, preserving the logical structure of the original argument. To facilitate evaluation, we present a new benchmark of 184 undergraduate-level problems, manually annotated with step-by-step solutions and logical dependency graphs, and introduce ProofScore , a new composite metric to evaluate syntactic correctness, semantic faithfulness, and structural fidelity. Experimental results show our pipeline sets a new state-of-the-art for autoformalization, achieving a ProofScore of 0.545, substantially exceeding baselines like full-proof formalization (0.123), which processes the entire proof at once, and step-proof formalization (0.072), which handles each step independently. Our pipeline, benchmark, and score metric are open-sourced to encourage further progress at https://github.com/Huawei-AI4Math/ProofFlow . 1 Introduction The effort to automate mathematical reasoning is advancing on two key fronts. Recent advances in large language models (LLMs) have greatly enhanced their ability to solve mathematical problems ( Liang et al. 2025 ) . Meanwhile, symbolic engines such as Lean ( Moura & Ullrich 2021 ) and Isabelle ( Hales et al. 2017 ) provide machine-verifiable frameworks that enforce strict logical correctness. LLM-based automated theorem provers (ATPs), such as Goedel-Prover ( Lin et al. 2025 ) and Kimina-Prover ( Wang et al. 2025a ) , generate formal proofs for problems that are written in a symbolic language, which are then checked by the symbolic engine to ensure logical correctness. This paper studies automated proof formalization: the task of faithfully translating the natural language theorem and proof into a machine-verifiable formal representation. This task is distinct from the aforementioned ATPs, where the goal is to discover a proof from an already formalized problem. Here, the goal is to translate an existing proof, a crucial step for verification in real-world mathematical workflows. After composing a proof, a mathematician may wish to formalize it to verify its correctness, uncover missing assumptions, or fill logical gaps. Given the steep learning curve of formal languages like Lean, a system that can automate this translation is highly desirable. The manual effort these automated proof formalizers seeks to automate is immense, as demonstrated by landmark efforts such as the Flyspeck project, which took over 20 years to formalize the Kepler conjecture ( Hales et al. 2017 ) ; the Blue-Diamond project for the Polynomial Freiman-Ruzsa conjecture ( Tao 2023 ) ; and the ongoing formalization of Fermat’s Last Theorem ( Buzzard & Taylor 2025 ) , among other projects ( Math Inc. 2025 ; Scholze 2021 ; Gonthier et al. 2013 ) . Figure 1: Comparison of our ProofFlow “Lemma Approach” and the common “Tactic Approach” in formalizing a natural language (NL) theorem and its proof into Lean 4 code. The Lemma Approach directly mirrors the sequence of steps and their dependencies in the NL proof. By contrast, the Tactic Approach produces tactics that fail to adhere to the structure of the initial NL proof. A key challenge in autoformalization is the fundamental mismatch between the flexible and high-level nature of human language and the rigid, low-level syntax of formal systems. To bridge this gap, ATPs typically generate “tactics” for formal proof assistants like Lean 4. However, this tactic-based approach often fails to preserve the logical structure of the original human argument. For instance, as shown in Figure 1 , under “Lean 4: Tactic Approach”, the generated tactics do not follow the sequence of steps in the natural language proof. Furthermore, a single tactic, linarith , consolidates three distinct steps from the original proof (TS, L2, and L4). This disparity creates two major issues. First, not all natural language mathematical expressions can be directly translated into low-level tactics, which can cause the formalization process to fail. Second, even if an automated system generates a verifiable proof, it may take shortcuts or skip intermediate steps, arriving at the correct conclusion without mirroring the explicit, step-by-step reasoning of the original proof. This makes it difficult to verify that the formal proof truly captures the human’s intended logic. To address these issues and ensure faithful autoformalization, we propose a novel approach that avoids direct translation into limited, low-level formal tactics. Instead, we deconstruct the natural language proof into a sequence of structured, high-level lemmas, as illustrated by the “Lemma Approach” in Fig. 1 . The key advantage of this method is that it enables us to explicitly follow the sequence of steps in the original proof with low friction 1 1 1 While we currently use the placeholder “by sorry” for unproven parts, our ultimate goal is to generate Lean tactics to prove each lemma and the final solution. . This stands in sharp contrast to the conventional tactic-based approach, which is often convoluted and hinders mirroring the human proof structure. Second, our lemma-based approach preserves the logical structure of the natural language proof by explicitly defining dependencies. As shown in Figure 1 , the final step, lemma TS (the theorem’s solution), depends only on lemma L2 and lemma L4 . This explicit dependency management is crucial in enforcing structurally faithful formalization, which is often not achieved in a standard tactic-based workflow. For instance, a common tactic like “have” in Lean 4 feeds the entire preceding context to each new step, not just the specific premises required by the original proof logic. In contrast, our approach of explicitly defining how lemmas depend on one another prevents the system from incorrectly using unintended dependencies, a common failure in tactic-based proving. These two innovations, high-level lemma generation and explicit dependency tracking, form the core of our new autoformalization pipeline, ProofFlow . Another primary challenge is defining what constitutes a “faithful” formalization. In existing work, researchers either focus on syntactic correctness ( Hu et al. 2025 ) , i.e., no compilation errors, or use a simple BLEU score for semantic measurement ( Poiroux et al. 2024 ; Wu et al. 2022 ) , while ignoring the structural fidelity of the proof. To properly evaluate proof formalizations, we propose viewing a proof not as a monolithic block of text, but as a structured sequence of theorem conditions, definitions, and lemmas that form a logical progression toward the final theorem solution or solutions (see Figure 1 ). Based on this, we introduce a new and more comprehensive proof autoformalization scoring metric ( ProofScore ), and we also address the lack of an advanced benchmark by providing a new university-level dataset tailored for this task ( ProofFlowBench ). Drawing on our new framework, we make the following key contributions: • ProofFlow : In Section 3 , we propose a novel pipeline for translating natural language theorems and proofs