Diversifying to Verify: When Task-Equivalent Programs Differ in Verifiability
This paper introduces Diversify2Verify, an LLM-based pipeline that demonstrates how generating diverse, task-equivalent program implementations significantly improves automated verification success rates by identifying variants that are more amenable to formal proof.
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 trying to build a robot that can solve a math puzzle. You have a super-smart AI assistant (a Large Language Model) that is great at writing code. Usually, we ask the AI: "Write code that solves this puzzle," and we check if the robot passes a few test runs. If it passes, we say, "Good job!"
But in the world of formal verification, passing a few tests isn't enough. It's like building a bridge and only driving a toy car over it. To be truly safe, you need a mathematical proof that the bridge will hold any car, any time, under any condition. This is what the paper calls "deductive verification."
The problem? Getting the AI to write code that is not only correct but also easy to prove is incredibly hard. Sometimes the AI writes a solution that works perfectly but is so messy or weirdly structured that the "proof checker" (a tool called Why3) gets confused and can't verify it.
The Big Idea: Don't Just Try One Way
The authors, Shirley Yu and Ruben Martins, asked a simple question: What if we don't just ask for one solution, but ask for many different versions of the same solution?
Think of it like trying to open a stubborn jar.
- Version A: You try twisting the lid with your right hand.
- Version B: You try twisting it with your left hand.
- Version C: You try tapping the lid with a spoon.
- Version D: You try running it under hot water.
Maybe the "right-hand twist" (the first code the AI writes) is too slippery for the proof checker to grip. But the "left-hand twist" might have a shape that fits the checker's logic perfectly. The paper calls this Diversify2Verify. Instead of hoping for one perfect code, they generate four different "flavors" of the same task:
- Array + Imperative: Like walking through a line of people one by one, checking their names.
- Array + Recursive: Like a game of "telephone" where you pass the task down a line of helpers.
- List + Imperative: Like flipping through a stack of index cards.
- List + Recursive: Like a Russian nesting doll where each doll contains the next step.
The Experiment: 73 Puzzles, 292 Attempts
The team built a special playground with 73 different programming puzzles (mostly involving numbers, lists, and arrays). For each puzzle, they asked the AI to generate all four of those "flavors." That gave them 292 different code attempts to test.
They didn't just let the AI write code; they set up a strict three-stage process:
- Stage 1 (The Contract): First, they made the AI write a "contract" (a formal rulebook) describing what the code must do, without worrying about how it does it. They checked this rulebook against examples to make sure it made sense. Once a rulebook was accepted, it was frozen. No more changing the rules later!
- Stage 2 (The Code): Next, they asked the AI to write the actual code for each of the four flavors, making sure it passed some basic test runs.
- Stage 3 (The Proof): Finally, they tried to prove that each code version satisfied the frozen rulebook. If the proof failed, they gave the AI a hint (a "repair") to fix the proof, but only the proof, not the code or the rules.
The Results: Diversity Wins
Here is what happened when they ran the numbers:
- The "One-Shot" Failure: If you just took the first code the AI wrote and tried to prove it, only 96 out of 292 (about 32.9%) worked. That's less than one in three!
- The Power of Repair: When they let the AI try to fix the proofs twice, the number jumped to 154 out of 292 (about 52.7%).
- The Power of Diversity (The Real Winner): When they looked at the 73 puzzles as a whole, they found that for 49 of them (a 67.1% success rate), at least one of the four different versions could be proven correct.
This is the main finding: Task-equivalent implementations can differ substantially in verifiability. In other words, two pieces of code that do the exact same thing can be worlds apart in how easy they are to prove.
What They Ruled Out (What It's NOT)
The paper is very careful about what it doesn't claim:
- It's not about better code: They didn't find that "Arrays are better than Lists" or "Recursion is better than Loops." In fact, the results were mixed. Recursive code was generally easier to prove than imperative (loop-based) code, but arrays and lists performed similarly overall. The key wasn't picking the "best" style; it was having options.
- It's not about changing the rules: They strictly forbade the AI from changing the "contract" (the goal) during the repair phase. If the AI tried to change the goal to make the proof easier, that was a failure. They wanted to prove the original goal, not a weaker one.
- It's not a magic bullet for everything: The study only looked at puzzles involving integers, arrays, and lists. They don't claim this works for floating-point numbers, complex 3D graphics, or programs that talk to the internet.
How Sure Are They?
The authors are confident in their measurements but cautious about the big picture.
- Measured: They have hard numbers. They ran the tools, counted the successes, and saw that diversity increased the success rate from 32.9% to 52.7% for individual artifacts, and 67.1% for tasks.
- Suggested: They suggest that the reason imperative code (loops) was harder to prove is that it requires "loop invariants" (rules about what's happening inside a loop) which are hard for AI to invent automatically. They suspect that if you give the AI better tools to guess these rules, the gap might close.
- Not Proven (Yet): They admit they didn't prove that the "Array Contract" and "List Contract" are mathematically identical. They just assumed they meant the same thing based on the task description. They also note that their "judge" (an AI checking if the rules matched the puzzle) isn't a perfect human expert, so a few subtle mistakes might have slipped through.
The Takeaway
The paper suggests that when we ask AI to write "verified" software, we shouldn't just ask for one answer and hope for the best. Instead, we should ask for a menu of options. By generating different ways to solve the same problem, we increase our chances of finding the one version that the proof checker can actually understand.
It's like trying to find a key that fits a lock. If you only have one key, you might be stuck. But if you have a whole ring of keys, even if they all open the same door, one of them is almost guaranteed to fit the lock perfectly.
Drowning in papers in your field?
Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.