🤖 machine learning

Quokka: Accelerating Program Verification with LLMs via Invariant Synthesis

该论文提出了名为 Quokka 的评估导向框架，通过直接验证大语言模型生成的循环不变式是否有助于证明目标断言，在 SV-COMP 基准测试中实现了优于现有方法的程序验证性能。

原作者： Anjiang Wei, Tianran Sun, Tarun Suresh, Haoze Wu, Ke Wang, Alex Aiken

发布于 2026-04-03

📖 1 分钟阅读☕ 轻松阅读

原作者： Anjiang Wei, Tianran Sun, Tarun Suresh, Haoze Wu, Ke Wang, Alex Aiken

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一个名为 Quokka（中文可译为“短尾矮袋鼠”，一种以快乐著称的小动物）的新工具。它的核心任务是：利用人工智能（大语言模型）来加速计算机程序的“安全体检”。

为了让你更容易理解，我们可以把整个故事想象成**“寻找失落的地图碎片”**。

1. 背景：为什么程序需要“体检”？

想象一下，你正在驾驶一辆自动驾驶汽车（这就是程序）。在出发前，工程师必须确保这辆车在任何情况下都不会撞车（这就是程序验证）。

但是，汽车在行驶过程中会经过无数个路口（循环，比如 while 或 for 循环）。要证明汽车永远安全，工程师需要知道在每一个路口，汽车的状态（速度、位置等）满足什么条件。这些条件被称为**“循环不变量”**（Loop Invariants）。

难点：自动找出这些“安全条件”非常难。就像让你在不看地图的情况下，凭空猜出穿过整个城市的所有交通规则一样。
现状：以前的方法要么太慢，要么找到的条件太弱（比如只说“车在动”，但这不足以证明“车不会撞”），导致验证过程卡住。

2. 以前的尝试：把 AI 当作“修补匠”

之前的研究尝试让大语言模型（LLM）来猜这些条件。但是，他们把 AI 生成的答案当作**“粗糙的原材料”**。

比喻：就像让 AI 随便扔给你一堆砖头（AI 生成的条件），然后工程师必须花大量时间把这些砖头打磨、切割、重新砌墙（复杂的后处理算法），才能确认这堵墙能不能挡住洪水。
问题：这个过程太复杂了，而且如果砖头本身是歪的，砌墙的人还得费劲去修，效率很低。

3. Quokka 的突破：把 AI 当作“直接考官”

Quokka 提出了一种更简单、更聪明的思路：别修砖头了，直接拿去试！

核心思想：
1. 让 AI 直接猜一个“安全条件”（比如：“在路口 B，车速必须小于 50"）。
2. 把这个条件直接交给专业的“验证机器”（Verifier）去测试。
3. 测试分两步：
  - 第一步：这个条件本身对吗？（是不是胡说八道？）
  - 第二步：如果假设这个条件是对的，能不能证明汽车最终不会撞车？
4. 结果：如果验证机器说“行，通了！”，那就证明 AI 猜对了，而且帮大忙了。如果不行，就换一个。
比喻：
以前的做法是：AI 给砖头 -> 工程师修砖头 -> 砌墙 -> 试水。
Quokka 的做法是：AI 给砖头 -> 直接扔进水里试 -> 浮起来了（证明有效）-> 继续下一块。
它不再纠结砖头是否完美，而是直接看它能不能解决问题。

4. 为什么 Quokka 这么厉害？

论文做了两件事来证明 Quokka 的优越性：

建立了“高考”题库：
他们收集了 866 个真实的、复杂的程序案例（来自著名的软件验证比赛 SV-COMP），这些案例比以前的测试题更难，包含更多循环、数组和指针。这就像给 AI 出了一套真正的“奥数题”，而不是简单的“填空题”。
训练与筛选：
- 微调（Fine-tuning）：他们给 AI 看了很多正确答案的样本，教它怎么猜得更准。
- Best-of-N（百里挑一）：让 AI 一次猜 8 个答案，然后让验证机器快速测试这 8 个，只选那个最能帮上忙的答案。这就像让 AI 同时派出 8 个探险队，谁先找到路就听谁的。

5. 结果如何？

速度更快：Quokka 配合最先进的 AI 模型，比之前所有的方法都更快、更准地证明了程序的安全性。
更简单：它不需要复杂的“修补”算法，直接“猜 - 测 - 过”，大大减少了系统的复杂度。
更强大：在那些以前验证器（Solver）算不出的难题上，Quokka 也能帮上忙，解决了很多额外的案例。

总结

Quokka 就像是一个聪明的“导航助手”。
以前的方法试图让助手先画一张完美的地图（这需要很长时间且容易出错），然后再让人去走。
Quokka 的方法是：让助手直接指路（“往左走”），然后马上让人试着走一步。如果走通了，就继续；如果走不通，马上换方向。

这种方法简单、直接、高效，证明了大语言模型在帮助计算机进行严谨的数学证明方面，有着巨大的潜力，而且不需要把 AI 的输出搞得过于复杂。

一句话概括：Quokka 不再把 AI 当作需要修理的“半成品”，而是把它当作一个可以直接上场的“天才助手”，通过快速试错，让软件验证变得又快又准。

这篇论文介绍了 Quokka，这是一个面向评估的大语言模型（LLM）不变式合成框架，旨在通过生成有用的循环不变式来加速程序验证。

以下是对该论文的详细技术总结：

1. 研究背景与问题 (Problem)

核心挑战：程序验证依赖于循环不变式（Loop Invariants）。虽然生成正确的不变式相对容易（任何恒真条件都算正确），但生成**足够强（Strong）**的不变式以证明目标断言并加速验证过程，是一个长期存在的难题。
现有方法的局限性：
- 评估不可靠：早期工作（如 Pei et al., 2023）依赖 Daikon（动态分析工具）来评估不变式，但这在逻辑上是不完备的（Soundness 问题），且无法区分“正确但弱”与“正确且强”的不变式。
- 过度工程化：后续基于 LLM 的验证器（如 LaM4Inv, LEMUR, Loopy 等）通常将 LLM 的输出视为“嘈杂的符号材料”，需要复杂的后处理算法（如谓词过滤、子句重组、Houdini 剪枝、递归修复等）来构建有效不变式。这增加了系统的复杂性，且随着模型能力提升，这种复杂的“救援”机制是否必要存疑。
研究目标：探索 LLM 是否能直接生成对验证器有帮助的不变式，并设计一个更简单、以评估为中心的框架来验证这一点。

2. 方法论 (Methodology)

2.1 Quokka 框架设计

Quokka 采用了一种**以评估为中心（Evaluation-centric）**的简化设计，摒弃了复杂的后处理逻辑：

直接验证：LLM 直接提出一个候选不变式 $q$ （包含位置和谓词）。
双重验证查询：系统并行执行两个验证器查询：
1. 正确性检查 ( $d_a$ )：验证 $q$ 是否是一个正确的不变式（即 $P \models q$ ）。
2. 效用检查 ( $d_b$ )：在假设 $q$ 成立的前提下，验证目标属性 $p^*$ 是否成立（即 $P \models_{\{q\}} p^*$ ）。
判定逻辑：
- 如果 $q$ 正确且能证明目标，则验证加速成功。
- 如果 $q$ 错误，则直接拒绝。
- 如果 $q$ 正确但无法证明目标（或超时），则判定为无效加速。
优势：这种设计消除了大部分定制化的后处理逻辑，允许并行查询，并将目标从“寻找正确不变式”转变为“寻找能加速验证的不变式”。

2.2 数据集构建

评估基准：从最新的 SV-COMP（软件验证竞赛）中提取了 866 个实例。这是目前 LLM 验证器领域最大的评估数据集。
- 特点：程序平均行数更多（52 行），包含多循环、多函数、数组和指针，比现有基准（如 LaM4Inv, Clause2Inv 等）更具挑战性。
训练数据：利用 UAutomizer 验证器生成的合成数据，构建了 3589 个实例的训练集，用于监督微调（SFT）。

2.3 增强技术

监督微调 (SFT)：使用 LoRA 对模型（如 Qwen2.5-7B）进行微调，训练数据来自 UAutomizer 生成的真值不变式。
Best-of-N 采样：生成 $N$ 个候选不变式，并行执行验证查询，选择能带来最大加速比（即最快验证时间）的那个。

3. 关键贡献 (Key Contributions)

提出 Quokka 框架：首个提供**逻辑完备（Sound）**评估且性能达到最先进（SOTA）的 LLM 不变式合成框架。它证明了简单的“生成 - 验证”范式优于复杂的“生成 - 修复 - 重组”范式。
构建大规模基准：发布了包含 866 个复杂实例的 SV-COMP 衍生基准，填补了该领域缺乏高质量、大规模评估数据集的空白。
实证分析：
- 评估了 9 个 SOTA LLM（包括 GPT-5 系列、Claude 系列、Qwen、Llama 等）。
- 证明了监督微调和Best-of-N 采样均能带来可测量的性能提升。
- 揭示了 LLM 在中等难度问题上能显著加速验证，但在极难问题上仍面临挑战。

4. 实验结果 (Results)

模型性能差异：
- 模型越大、越新，性能越好。例如，gpt-5.2 在 60 秒超时下解决了 710 个正确不变式，平均验证时间仅为 22.2 秒。
- 较小的模型（如 Llama-3.1-8B）表现较差（342 个正确不变式，41.9 秒）。
加速效果：
- 在 60 秒超时下，Quokka (gpt-5.2) 比基线验证器（UAutomizer）多解决了 21 个实例。
- 在 500 秒超时下，多解决了 1 个实例（表明在极难问题上，LLM 的边际效益递减，但仍有提升空间）。
对比现有工作：
- Quokka 在所有超时阈值下均显著优于 LEMUR、Clause2Inv、Loopy 和 LaM4Inv。
- 例如，在 LEMUR 的基准测试中，Quokka 解决的实例数量远超 LEMUR，且平均求解时间更短。
失败模式分析：
- 主要失败原因并非不变式错误，而是超时（验证器无法在限定时间内完成证明）。
- 部分失败是因为 LLM 生成了与原始断言等价但无分解价值的不变式，或生成了过于简单的不变式。

5. 意义与结论 (Significance & Conclusion)

范式转变：Quokka 证明了随着 LLM 能力的提升，程序验证不再需要复杂的、基于规则的“救援”算法。直接让 LLM 生成候选不变式，并由验证器进行严格评估，是一种更简单、更鲁棒且性能更优的策略。
新 SOTA：该工作确立了 LLM 辅助程序验证的新基准，展示了通过简单的评估导向设计即可超越复杂的神经符号系统。
未来方向：研究指出了当前 LLM 在处理极端复杂验证任务时的局限性（如无法分解困难问题），并表明通过微调（SFT）和采样策略（Best-of-N）仍有巨大的优化空间。

总结：Quokka 通过简化评估流程、构建高质量基准和实证分析，证明了 LLM 在生成强循环不变式方面的巨大潜力，为未来高效、自动化的程序验证提供了新的技术路径。