Goedel-Code-Prover: Hierarchical Proof Search for Open State-of-the-Art Code Verification

Zenan Li, Ziran Yang, Deyuan He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin · 2026

Read Goedel-Code-Prover: Hierarchical Proof Search for Open State-of-the-Art Code Verification by Zenan Li, Ziran Yang, Deyuan He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin (2026) 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-2603-19329.txt.

Introduction

Li and co-authors teach a model to prove that code meets its specs in Lean 4. Their Goedel-Code-Prover first splits a hard goal into simpler subgoals, then proves each piece. A single score grades each split by sound logic and structural gain. That score serves as both training reward and test-time ranker. One policy learns both splitting and proving, tuned by supervised steps and hybrid reinforcement learning. On 427 tasks, the model proves 62 percent of cases. That is 2.6 times the best baseline rate.

Catalog record

CREATORZenan Li, Ziran Yang, Deyuan He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69626
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.19329

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Goedel-Code-Prover: Hierarchical Proof Search for Open State-of-the-Art Code Verification Zenan Li, Ziran Yang, Deyuan He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin Abstract Large language models (LLMs) can generate plausible code but offer limited guarantees of correctness. Formally verifying that implementations satisfy specifications requires constructing machine-checkable proofs, a task that remains beyond current automation. We propose a hierarchical proof search framework for automated code verification in Lean 4 that decomposes complex verification goals into structurally simpler subgoals before attempting tactic-level proving. Central to our approach is a principled decomposition score that combines constructive justification with structural effectiveness. Crucially, this score serves as both the training reward and the inference-time ranking criterion, ensuring strict alignment between optimization and deployment. We train Göedel-Code-Prover-8B , a single unified policy for both decomposition and completion, via supervised initialization followed by hybrid reinforcement learning, where a continuous decomposition reward drives planning exploration while supervised replay stabilizes proof generation. On three Lean-based code verification benchmarks comprising 427 tasks, our 8B-parameter model achieves a 62.0% prove success rate, a 2.6 × \times improvement over the strongest baseline, surpassing neural provers up to 84 × \times larger. We further observe consistent inference-time scaling: success rates improve monotonically with search iterations and sampling budget, with our trained model achieving greater efficiency than frontier off-the-shelf models of comparable scale. 1 Introduction Large language models (LLMs) have rapidly advanced code generation, achieving strong performance on programming benchmarks and increasingly serving as real-world coding assistants ( 9 ; 25 ; 4 ; 24 ) . Yet while LLM-based coding agents routinely generate unit tests and reproduction scripts to validate their outputs, empirical studies show that such testing cannot certify the absence of subtle logical errors, boundary-case violations, or specification mismatches ( 16 ; 29 ; 3 ) . As LLMs are deployed in safety-critical environments, bridging the gap between “code that appears to work” and “code that is provably correct” becomes increasingly urgent. Formal verification offers a principled solution by expressing specifications (see Figure 1 for an example) in a formal language and constructing machine-checked proofs of correctness. Lean 4 ( 32 ) , a modern interactive theorem prover, provides a powerful platform for such verification tasks, with a growing ecosystem of libraries (e.g., Mathlib ( 30 ) and CSLib ( 7 ) ). Figure 1 illustrates a typical verification task: given a function FindSingleNumber that returns the unique element from a list, the specification encodes a precondition and a postcondition as Lean predicates, and the top-level theorem asserts that the implementation satisfies this specification. The sorry placeholder marks the proof obligation to be discharged. Even for this seemingly simple problem, constructing a complete proof requires discovering auxiliary lemmas about list filtering, membership, and inductive reasoning over the input structure, none of which are suggested by the specification itself. Writing such proofs by hand remains labor-intensive and demands substantial expertise, limiting widespread adoption of formal verification. ⬇ def FindSingleNumber_precond ( nums : List Int ) : Prop := let numsCount := nums . map ( fun x = > nums . count x ) numsCount . all ( fun c = > c = 1 \vee c = 2) \wedge numsCount . count 1 = 1 ⬇ def filterlist ( x : Int ) ( nums : List Int ) : List Int := nums . filter ( fun y = > y = = x ) def FindSingleNumber ( nums : List Int ) ( h : FindSingleNumber_precond nums ) : Int := match nums . filter ( fun x = > ( filterlist x nums ). length = = 1) with | x :: _ = > x | [] = > 0 ⬇ def FindSingleNumber_postcond ( nums : List Int ) ( result : Int ) ( h : FindSingleNumber_precond nums ) : Prop := nums . length > 0 \wedge ( filterlist result nums ). length = 1 \wedge \forall ( x : Int ), x \in nums \rightarrow x = result \vee ( filterlist x nums ). length = 2 ⬇ theorem FindSingleNumber_spec ( nums : List Int ) ( h : FindSingleNumber_precond nums ) : FindSingleNumber_postcond nums ( FindSingleNumber nums h ) h := by sorry Figure 1: A code verification task in Lean 4. The blue blocks define the specification: a precondition constraining valid inputs and a postcondition characterizing correct outputs. The green block contains the implementation. The red block states the top-level verification goal, where sorry marks the proof obligation to be synthesized automatically. The complete proof synthesized by our framework is shown in Appendix A . Recent work has explored leveraging LLMs to automate proof synthesis in interactive theorem provers (ITPs) such as Lean 4 and Isabelle ( 26 ; 47 ) . State-of-the-art systems have achieved remarkable success in formal mathematics, reaching competition and olympiad level performance ( 36 ; 28 ; 45 ; 15 ; 41 ) . These methods typically operate in a decompose-and-prove paradigm: the model first decomposes a complex theorem into simpler intermediate lemmas (or subgoals), then proves each lemma individually using tactic generation. Despite this progress, these methods do not transfer directly to code verification due to two fundamental mismatches. The first problem is ungrounded decomposition . In mathematics, correctness is central to the discipline: mathematicians routinely write proofs by hand, and the resulting reasoning pervades textbooks, papers, and online discussions. LLMs absorb this rich corpus during pretraining, acquiring the intuition needed to propose meaningful proof decompositions even before formal verification. No comparable corpus exists for program correctness. Most software developers treat testing as a sufficient proxy for correctness ( 33 ; 5 ) and never articulate formal reasoning about their code. In the few domains where formal guarantees are required, practitioners rely on automated tools such as SMT solvers ( 12 ; 6 ) and model checkers ( 11 ; 17 ) rather than hand-written proofs, producing little natural-language proof reasoning in the process. Consequently, LLMs lack the informal-to-formal bridge that enables effective decomposition in mathematics: when applied to code verification, their proposed subgoals are frequently imprecise, semantically invalid, or no simpler than the original goal. The second issue is compound domain shift : even when a decomposition is valid, proving the resulting subgoals faces a dual challenge. On one hand, program verification introduces a fresh conceptual universe with every program ( concept proliferation ): each function definition brings new computational behavior, control flow patterns, and data-structure invariants whose properties must be discovered without prior library support, unlike mathematics where shared libraries such as Mathlib provide a closed vocabulary of reusable lemmas. On the other hand, discharging these subgoals requires program-specific automation ( tactic distribution shift ): tactics such as grind , SMT-backed lemmas, and computational reflection ( native_decide ) that differ substantially from the algebraic tactics prevalent in mathematics; models trained on mathematical corpora routinely fail to invoke these tools correctly. Theorem G : FindSingleNumber satisfies specification 18 operator footprint d(\cdot) LLM \pi L_{1} : result is the unique element 7 L_{2} : other elements appear exactly twice 8 \checkmark proof reconstruction \checkmark quickcheck filter \checkmark operator footprint \downarrow LLM \pi L_{1.1} : filterlist length equals List.count 4

Read the complete text