AlphaVerus : Bootstrapping Formally Verified Code Generation through Self-Improving Translation and Treefinement
Pranjal Aggarwal, Bryan Parno, Sean Welleck · 2024
Read AlphaVerus : Bootstrapping Formally Verified Code Generation through Self-Improving Translation and Treefinement by Pranjal Aggarwal, Bryan Parno, Sean Welleck (2024) 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-2412-06176.txt.
Introduction
Pranjal Aggarwal, Bryan Parno, and Sean Welleck build a system that writes code with proof that the code is right, in work from twenty twenty-four. Language models now write code fast, but they give no proof of correctness. Formal proof could supply that proof, yet proof data is scarce. Proofs are also hard for models to write from scratch. The team aims to grow proof skill with no human help.
Their system, AlphaVerus, works in three looping phases. First it tries translations of programs from a data-rich language. Next a tree search, called Treefinement, refines drafts with feedback from a checker. Last it filters out drafts whose specs and code do not match. That loop lets a large open model produce checked code on its own. Tests on two known coding sets show the path works. The work lays a base for code agents users can trust.
Catalog record
| CREATOR | Pranjal Aggarwal, Bryan Parno, Sean Welleck |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-06176
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
AlphaVerus : Bootstrapping Formally Verified Code Generation through Self-Improving Translation and Treefinement Pranjal Aggarwal, Bryan Parno, Sean Welleck Abstract Automated code generation with large language models has gained significant traction, but there remains no guarantee on the correctness of generated code. We aim to use formal verification to provide mathematical guarantees that the generated code is correct. However, generating formally verified code with LLMs is hindered by the scarcity of training data and the complexity of formal proofs. To tackle this challenge, we introduce AlphaVerus , a self-improving framework that bootstraps formally verified code generation by iteratively translating programs from a higher-resource language and leveraging feedback from a verifier. AlphaVerus operates in three phases: exploration of candidate translations, Treefinement—a novel tree search algorithm for program refinement using verifier feedback, and filtering misaligned specifications and programs to prevent reward hacking. Through this iterative process, AlphaVerus enables a LLaMA-3.1-70B model to generate verified code without human intervention or model finetuning. AlphaVerus shows an ability to generate formally verified solutions for HumanEval and MBPP, laying the groundwork for truly trustworthy code-generation agents. 1 1 1 Code is available at https://alphaverus.github.io 1 Introduction There has been an enormous effort to train code-generating large language models (LLMs) ( Chen et al., 2021 ; Austin et al., 2021 ; Li et al., 2023 ; Rozière et al., 2024 ; Team, 2024 ) , leading to LLM-powered agents that can perform tasks ranging from fixing bugs in software repositories to solving Olympiad-level algorithmic problems ( Jimenez et al., 2023 ; Li et al., 2022b ) . Despite these successes, multiple studies have identified disturbing mistakes in LLM-produced code, including subtle bugs and serious security vulnerabilities ( Hendler, 2023 ; Pearce et al., 2021 ; Jesse et al., 2023 ; Zhong & Wang, 2023 ; Perry et al., 2023 ; Elgedawy et al., 2024 ) . Ultimately these mistakes stem from a fundamental property of LLMs: language models can generate any string of code, without regard to correctness. As a result, automatically checking the correctness of LLM-generated code is one of the grand challenges facing the research community. The generated code must be correct for all possible inputs it may receive. However, today’s code generation methods select or filter generations with imperfect proxies of correctness, such as runtime testing or human inspection. Achieving perfect test coverage is typically infeasible ( Li et al., 2022a ; Liu et al., 2023 ) , and incomplete coverage leads to an unreliable signal that can be exploited by a model ( Pan et al., 2022 ; Liu et al., 2023 ; Denison et al., 2024 ) . Relying on human review is equally problematic since it scales poorly and humans can struggle to tell whether LLM-generated code is correct ( Perry et al., 2023 ) . In turn, the difficulty of trusting generated code reduces the potential productivity gains from using LLMs and can lead to unexpected vulnerabilities or unreliable signals for improving models. In contrast, generating code in a verification-aware programming language such as Dafny ( Leino, 2010 ) , F ∗ ( Swamy et al., 2016 ) , or Verus ( Lattuada et al., 2023 ) offers a promising approach to addressing these challenges by providing mathematical guarantees that a program obeys a specification for all possible inputs. In this paradigm, code is paired with a specification and proof written in a specialized language, and a mechanical verifier checks whether the code meets the specification. Doing so could dramatically improve the trustworthiness of the generated code: if the verifier passes, the LLM’s generated program is mathematically guaranteed to meet the specification. However, writing formal specifications and proofs introduces additional layers of complexity. Furthermore, although LLMs have demonstrated success in automated theorem proving in mathematical domains ( Lu et al., 2023 ; Li et al., 2024 ) , their capability to generate verified code for even basic algorithms is limited ( Sun et al., 2023 ; Lohn & Welleck, 2024 ) . A significant barrier to automatically generating real-world, formally verified code is the scarcity of training data. In particular, verification-aware research languages have a rich history (e.g., Dafny ( Leino, 2010 ) , F ∗ ( Swamy et al., 2016 ) ), yet verifying real-world code in mainstream languages remains nascent. For example, Verus ( Lattuada et al., 2023 ) –a verification language for the very popular language Rust–has fewer than 10 public repositories, despite Rust itself having millions of code examples. Hence, enabling formally verified code generation in a mainstream language such as Rust faces a bootstrapping problem –how do we create an initial model that can generate even relatively simple verified programs, given the absence of training data? Figure 1 : Overview of AlphaVerus , a self-improving framework for generating formally verified code. Each iteration consists of three key steps: (1) Exploration translates programs from a source language to Verus by sampling multiple trajectories and selecting partially correct ones using verifier feedback, (2) Treefinement iteratively fixes errors guided by verifier feedback and tree search, and (3) Critique validates and filters out underspecified or incorrect translations. The framework bootstraps new exemplars after each iteration to continuously improve performance without human intervention. We propose AlphaVerus , a framework for bootstrapping a formally verified code generation model by iteratively translating programs from a resource-rich domain and self-improving using feedback from the verifier. As illustrated in Figure 1 , each iteration of AlphaVerus has three phases. First, the exploration phase generates candidate programs by translating from a source language (such as Dafny) to the target language (here, Verus) by generating multiple candidates and saving partially and completely verified attempts. Second, Treefinement refines the imperfect candidates through a novel tree search over the space of output programs using feedback from the verifier, saving the final verified program, along with its ancestors to serve as error correction examples. We show that Treefinement leads to substantial gains over vanilla refinement strategies that resemble those used in concurrent work ( Yang et al., 2024 ; Chen et al., 2024 ) . Third, critique models detect misaligned translations and specifications–the one part of the pipeline that lacks formal guarantees. Crucially, this alleviates reward hacking , in which models learn to game the system by generating trivial or incomplete specifications, or even by identifying verifier limitations that cause trivial programs to pass the verifier. While previous work has investigated methods that rely on test cases ( Sun et al., 2023 ) , our critique models address the challenging problems of automated specification generation and validation without relying on any unit test cases. Each iteration of AlphaVerus collects new exemplars that improve the models in each phase, creating a cycle of improvement. Thus, unlike recent work that relies on human experts to write correction prompts ( Yang et al., 2024 ) , our method requires no human intervention and automatically learns to generate better code. Moreover, the system operates using a single language model (e.g., Llama 70b), without the need for the expensive GPT-4 initialization used in concurrent work ( Chen et al., 2024 ) . Finally, the collected exemplars can be used to improve the verified code generation performance of any model without any finetuning. To demonstrate AlphaVerus