ProofFlow: A Dependency Graph Approach to Faithful Proof Autoformalization

Rafael Cabral, Tuan Manh Do, Xuejun Yu, Wai Ming Tai, Zijin Feng, Shen Xin

Abstract

The autoformalization of mathematical proofs—translating natural language arguments into machine-verifiable code—is a critical step toward reliable AI reasoning. Traditional methods often treat proofs as monolithic text blocks, leading to "shortcuts" where the formal code bypasses the original human logic. We introduce ProofFlow, a pipeline that formalizes proofs by first extracting their underlying logical structure as a Directed Acyclic Graph (DAG). Each node in the DAG is translated into a self-contained Lean 4 lemma, ensuring structural fidelity. Evaluated on the new ProofFlowBench, ProofFlow achieves a state-of-the-art ProofScore of 0.545, vastly outperforming traditional monolithic and sentence-by-sentence formalization methods.

Introduction

Large Language Models (LLMs) have demonstrated remarkable capabilities in solving complex mathematical problems. However, their internal reasoning remains a "black box," necessitating formal verification to ensure 100% certainty. Autoformalization aims to bridge this gap by converting human-readable proofs into formal languages like Lean 4. A primary challenge in this field is faithfulness: ensuring the formal proof accurately reflects the specific logical steps intended by the human author. Current tools often produce code that compiles but ignores the intermediate reasoning of the source text, rendering the formalization less useful for mathematicians verifying specific arguments.

Methods: The ProofFlow Pipeline

ProofFlow addresses the faithfulness gap through a modular, graph-based approach. Instead of a direct translation, the pipeline operates in three distinct stages:

  1. Graph Builder: An LLM parses the natural language proof into a Directed Acyclic Graph (DAG). Nodes represent conditions (TC), intermediate lemmas (L), or the final theorem solution (TS). Edges explicitly define the logical dependencies between these components.
  2. Formalizer: Each node is translated into a standalone Lean 4 lemma. To prevent "logical leaps" or hallucinations, the LLM is only provided with the specific dependencies identified in the DAG.
  3. Tactic Completer: The system attempts to prove each individual lemma using Lean tactics. This modularity allows for granular verification; if a single lemma fails, the system identifies the exact point of logical failure.
Comparison of traditional tactic-based autoformalization versus ProofFlow's lemma-based dependency graph approach.

The transition from a monolithic "Tactic Approach" to a structured "Lemma Approach" is central to ProofFlow's success. By breaking the proof into discrete, verifiable units, the system avoids the "shortcut" problem where models skip intermediate reasoning. This granularity even allows the system to act as a "proof auto-correct," flagging errors in the original human-written text.

DAG formalization logic and a concrete theorem example.

Evaluation and Results

To evaluate structural fidelity, the authors introduced ProofFlowBench, a benchmark of 184 undergraduate-level problems across number theory, algebra, and analysis. They also proposed ProofScore, a metric that combines syntactic correctness with structural accuracy, measuring how well the formal dependencies match the original human logic.

ProofFlow sets a new benchmark for autoformalization performance:

  • ProofScore: ProofFlow achieved 0.545, compared to just 0.123 for monolithic "Full Proof" translation and 0.072 for sentence-by-sentence "Step Proof" without a graph.
  • Syntactic Accuracy: On undergraduate problems, ProofFlow reached 37.5% proof-level accuracy, a significant leap from previous benchmarks on simpler math which hovered around 6%.
  • Efficiency: By constraining the search space to specific dependencies, the system finds valid proofs more efficiently, consuming fewer tokens.

Conclusion and Future Work

ProofFlow demonstrates that explicitly modeling the dependency structure of mathematical proofs is essential for faithful autoformalization. By treating proofs as graphs rather than text blocks, the system achieves higher accuracy and provides a more transparent verification process. Future work will focus on improving the "Formalizer" stage to better capture the semantic nuances of natural language and reducing the reliance on human intervention for the most complex logical steps.

Summary updated

BibTeX
@inproceedings{cabral2026proofflow,
  author = {Rafael Cabral and Tuan Manh Do and Xuejun Yu and Wai Ming Tai and Zijin Feng and Shen Xin},
  title = {{ProofFlow: A Dependency Graph Approach to Faithful Proof Autoformalization}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=s9t2FJVsBH},
}
Figure