首个统一评估经典算法验证生成的基准,揭示不同系统间真实差距。
AlgoVeri: An Aligned Benchmark for Verified Code Generation on Classical Algorithms
- 构建跨语言统一测试集,77个经典算法在Dafny/Verus/Lean中保持相同接口。
- 顶尖模型在Dafny成功率达40.3%,在Lean仅7.8%,凸显系统差异。
- 发现迭代修复能显著提效,且语言设计深刻影响模型推理路径。
验证编程指从严格规格生成形式化验证代码。近期人工智能模型在该任务展现潜力,但缺乏跨范式统一评估方法。现有基准仅覆盖单一语言或工具(如Dafny、Verus、Lean),且任务差异大,性能指标不可比。本文提出AlgoVeri,一个在Dafny、Verus和Lean中评估77个经典算法验证生成的基准。通过强制一致的功能契约,揭示验证系统的关键能力差距:前沿模型在Dafny中达40.3%成功率(Gemini-3 Flash),而由于系统级内存限制,Verus中降至24.7%,在需显式证明的Lean中仅7.8%。此外,测试时计算动态显示:Gemini-3能通过迭代修复提升性能(如在Dafny中使通过率翻倍),而GPT-OSS早期即饱和。错误分析表明,语言设计影响细化路径:Dafny允许聚焦逻辑正确性,而Verus与Lean则使模型陷入持续的语法与语义障碍。
原文摘要 · Abstract (English)
Vericoding refers to the generation of formally verified code from rigorous specifications. Recent AI models show promise in vericoding, but a unified methodology for cross-paradigm evaluation is lacking. Existing benchmarks test only individual languages/tools (e.g., Dafny, Verus, and Lean) and each covers very different tasks, so the performance numbers are not directly comparable. We address this gap with AlgoVeri, a benchmark that evaluates vericoding of $77$ classical algorithms in Dafny, Verus, and Lean. By enforcing identical functional contracts, AlgoVeri reveals critical capability gaps in verification systems. While frontier models achieve tractable success in Dafny ($40.3$% for Gemini-3 Flash), where high-level abstractions and SMT automation simplify the workflow, performance collapses under the systems-level memory constraints of Verus ($24.7$%) and the explicit proof construction required by Lean (7.8%). Beyond aggregate metrics, we uncover a sharp divergence in test-time compute dynamics: Gemini-3 effectively utilizes iterative repair to boost performance (e.g., tripling pass rates in Dafny), whereas GPT-OSS saturates early. Finally, our error analysis shows that language design affects the refinement trajectory: while Dafny allows models to focus on logical correctness, Verus and Lean trap models in persistent syntactic and semantic barriers. All data and evaluation code can be found at https://github.com/haoyuzhao123/algoveri.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。