AxDafny: Agentic Verified Code Generation in Dafny
The paper introduces AxDafny, a verifier-guided framework for agentic code generation that iteratively refines implementations and proofs, demonstrating significant improvements in verification success on the newly proposed LCB-Pro-Dafny benchmark and the existing DafnyBench compared to state-of-the-art baselines.
Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer
Imagine you are hiring a very talented but slightly reckless architect to build a house. You give them a blueprint (the rules) and say, "Build me a house that has a kitchen, a bedroom, and a roof."
In the world of computer coding, most AI models act like that architect: they build a house that looks right, but when you try to live in it, the roof might leak, or the kitchen might be missing a door. They rely on "test drives"—checking if the house works in a few specific scenarios—to see if it's good enough.
AxDafny is a new system that changes the game. Instead of just building and hoping for the best, it uses a "super-inspector" (called a formal verifier) that checks the math behind the house while it's being built.
Here is how the paper explains this, broken down into simple concepts:
1. The Challenge: Building a House with a Math Proof
The researchers wanted to see if AI could write code that is not just "working," but mathematically proven to be correct. They used a special language called Dafny.
Think of Dafny as a language where you can't just say, "I built a door." You have to prove, "This door is exactly 3 feet wide, it opens only when the handle is turned, and it will never fall off its hinges."
- The Problem: Writing code is hard. Writing code and the mathematical proof that it works is even harder. Most AIs get stuck because they can't write the "proof" part.
2. The Solution: AxDafny (The "Fix-It" Loop)
The team created AxDafny, which acts like a team of two people working together:
- The Builder (The AI): Tries to write the code and the proof.
- The Inspector (The Verifier): Checks the work immediately.
If the Builder makes a mistake, the Inspector doesn't just say "Wrong." It points exactly to the leaky roof or the missing door and says, "You forgot to prove the door stays attached."
The Builder then fixes that specific part and tries again. They keep doing this in a loop (Build → Check → Fix → Build) until the Inspector gives a perfect "Pass."
3. The New Test: "LCB-Pro-Dafny"
To see if this system actually works, the researchers created a new test called LCB-Pro-Dafny.
- Imagine taking 250 difficult puzzles from a programming competition (like a high-stakes math olympiad for coders).
- They translated these puzzles into the strict "Dafny" language.
- Now, the AI has to solve the puzzle and prove the solution is correct.
4. The Results: Who Won?
The researchers compared their new system (AxDafny) against a standard, powerful AI (GPT-5.5) that just tries to write the code once without the "fix-it" loop.
On the "Proof" Test (DafnyBench):
- The standard AI got about 54% of the proofs right.
- AxDafny (using the fix-it loop) got 92.7% right.
- Analogy: It's like the standard AI guessing the answer, while AxDafny is a student who keeps checking their work until they get an A+.
On the "Competition" Test (LCB-Pro-Dafny):
- The standard AI only solved 11.6% of the hard puzzles correctly.
- AxDafny solved 56.4%.
- Analogy: AxDafny was much better at solving the actual problems, but it still struggled with the "hard" level, showing that even with a super-inspector, some puzzles are incredibly tough.
5. The Catch: "Correct" vs. "Fast"
Here is a surprising finding from the paper.
Sometimes, AxDafny would build a house that was mathematically perfect (the Inspector said "Pass!"), but when they tried to live in it, the house was too slow or used too much electricity.
- Why? The Inspector only checks if the house is safe and correct. It doesn't check if the house is efficient.
- The AI would sometimes build a "slow" solution that was easy to prove was correct, rather than a "fast" solution that was hard to prove.
- When they tested the code on real computers, many of the "perfect" solutions failed because they took too long to run (Time Limit Exceeded) or used too much memory.
Summary
AxDafny is a system that teaches AI to write code that is mathematically proven to be correct by using a "check-and-fix" loop.
- It works great at making sure the code does exactly what it's supposed to do (no bugs).
- It is a big improvement over standard AI, which often just guesses.
- The limitation: Just because the code is "proven correct" doesn't mean it's "fast enough" for real-world competitions. The AI needs to learn how to be both correct and efficient.
The paper concludes that this approach is a powerful way to make code more reliable, but we still need to teach AI to care about speed, not just correctness.
Drowning in papers in your field?
Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.