AlphaVerus: Bootstrapping Formally Verified Code Generation through Self-Improving Translation and Treefinement
Abstract
Automated code generation with large language models has gained significant traction, but there remains no guarantee of 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 the 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
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
7 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Tree of Thoughts: Deliberate Problem Solving with Large Language Models cites Self-Refine: Iterative Refinement with Self-Feedback
- VERINA: Benchmarking Verifiable Code Generation cites SWE-bench: Can Language Models Resolve Real-world Github Issues?
- Propose, Solve, Verify: Self-Play Through Formal Verification cites Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation
- SWE-bench: Can Language Models Resolve Real-world Github Issues? cites Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation
Cited by top-tier papers7
- VERINA: Benchmarking Verifiable Code GenerationZhe Ye, Zhengxu Yan, Jingxuan He, Timothe Kasriel et al.ICLR 2026 · 34 citations
- Propose, Solve, Verify: Self-Play Through Formal VerificationAlex Wilf, Pranjal Aggarwal, Bryan Parno, Daniel Fried et al.ICML 2026 · 6 citations
- ExVerus: Verus Proof Repair via Counterexample ReasoningJun Yang, Yuechun Sun, Yi Wu, Rodrigo Caridad et al.ICML 2026 · 3 citations
- KaPilot: LLM-Assisted Generation of Kani Specifications for Unsafe Rust VerificationMinghua Wang, Yuxi Ling, Mingzhi Gao, Yuwei Liu et al.ISSTA 2026
- Can LLMs Reason Like Automated Theorem Provers for Rust Verification? VCoT-Bench: Evaluating via Verification Chain of ThoughtZichen Xie, Wenxi WangICML 2026
Builds on28
- Toolformer: Language Models Can Teach Themselves to Use ToolsTimo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu et al.NeurIPS 2023 · 5,989 citations
- Tree of Thoughts: Deliberate Problem Solving with Large Language ModelsShunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran et al.NeurIPS 2023 · 5,068 citations
- Self-Refine: Iterative Refinement with Self-FeedbackAman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan et al.NeurIPS 2023 · 4,972 citations
- Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code GenerationJiawei Liu, Chunqiu Steven Xia, Yuyao Wang, Lingming ZhangNeurIPS 2023 · 2,317 citations
- SWE-bench: Can Language Models Resolve Real-world Github Issues?Carlos E. Jimenez, John Yang, Alexander Wettig, Shunyu Yao et al.ICLR 2024 · 2,082 citations
Related papers
- LEVER: Learning to Verify Language-to-Code Generation with ExecutionAnsong Ni, Srini Iyer, Dragomir Radev, Veselin Stoyanov et al.ICML 2023 · 318 citations
- Agentic Verification of Software SystemsHaoxin Tu, Huan Zhao, Yahui Song, Mehtab Zafar et al.FSE 2026 · 1 citation
- AlphaTrans: A Neuro-Symbolic Compositional Approach for Repository-Level Code Translation and ValidationAli Reza Ibrahimzada, Kaiyao Ke, Mrigank Pawagi, Muhammad Salman Abid et al.FSE 2025 · 8 citations
- Towards AI-Assisted Synthesis of Verified Dafny MethodsMd Rakib Hossain Misu, Cristina V. Lopes, Iris Ma, James NobleFSE 2024 · 26 citations
- AutoVerus: Automated Proof Generation for Rust CodeChenyuan Yang, Xuheng Li, Md Rakib Hossain Misu, Jianan Yao et al.OOPSLA 2025 · 11 citations
