Diversifying to Verify: When Task-Equivalent Programs Differ in Verifiability

2026-07-13 · Source: cs.SE updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Software Development & Engineering · Depth: Expert, extended

Summary

Diversify2Verify is a staged LLM-based pipeline designed to enhance automated program verifiability in Why3 by generating diverse task-equivalent implementations. It infers representation-specific contracts, generates recursive and imperative array/list implementations, and attempts verification with bounded verifier-guided annotation repair. Utilizing a benchmark of 73 tasks, which produced 292 implementation variants, Diversify2Verify initially verified 96 artifacts (32.9%). After two repair passes, this improved to 154 verified artifacts (52.7%). At the task level, at least one variant was verified for 49 of 73 tasks, achieving a 67.1% success rate. These findings highlight that implementation structure significantly influences verifiability and that diversity aids in finding verification-friendly artifacts.

Key takeaway

For Research Scientists and Software Engineers aiming to generate formally verified software, recognize that task-equivalent implementations vary significantly in verifiability. You should actively diversify implementation styles, such as recursive vs. imperative or array vs. list, to increase the likelihood of finding a verification-friendly artifact. Implement a staged pipeline, separating contract generation from implementation and proof annotation, and utilize bounded, verifier-guided repair to improve success rates.

Key insights

Task-equivalent program implementations differ in verifiability, and generating diverse variants improves verification success.

Principles

• Implementation structure affects automated verifiability.
• Recursive implementations often align with recursive specifications.
• Frozen contracts prevent specification weakening during repair.

Method

Diversify2Verify uses a staged LLM pipeline: contract inference, diverse implementation generation (array/list, recursive/imperative), and verifier-guided annotation repair.

In practice

• Generate diverse implementation variants for tasks.
• Separate contract, implementation, and proof annotation stages.
• Apply bounded, feedback-guided repair for verification failures.

Topics

• LLM-assisted Verification
• Program Verification
• Deductive Verification
• Why3
• Implementation Diversity
• Annotation Repair

Code references

• forge-lab/Diversify2Verify

Best for: AI Scientist, Research Scientist, Software Engineer

Related on AIssential

• Diversifying to Verify: When Task-Equivalent Programs Differ in Verifiability — Task-equivalent program implementations vary significantly in automated verifiability, and diversity aids verification success.
• Reasoning about concurrent loops and recursion with rely-guarantee rules — Mechanically verified rely-guarantee rules enable compositional reasoning for concurrent loops and recursion without assuming atomic expression evaluation.
• Diversity of Extensions in Abstract Argumentation — Symmetric-difference quantifies how far apart accepted viewpoints are in abstract argumentation frameworks.
• Untrusted Authors, Trusted Answers: A Calculus of Fidelity-Graded Translations — Trust in multi-language translations stems from architectural checks and graded fidelity, not author provenance.
• Your AI Just Wrote 500 Lines of Code. Can You Prove Any of It Works? — A framework classifies AI-generated code by its formal verifiability based on five structural properties.
• Proof-Refactor: Refactoring Generated Formal Proofs into Modular Artifacts — LLM-generated proofs benefit from process-guided refactoring to enhance modularity and readability beyond simple length optimization.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.SE updates on arXiv.org.