为大模型验证系统设计可预测的收敛机制,确保安全软件验证可靠完成。
The 4/$δ$ Bound: Designing Predictable LLM-Verifier Systems for Formal Method Guarantee
- 将验证流程建模为四阶段吸收马尔可夫链,实现理论保证。
- 证明系统在任意成功概率δ>0下几乎必然收敛,平均耗时≤4/δ。
- 实测9万次验证均成功,验证了理论边界精准有效。
将形式化验证工具与大语言模型(LLM)结合,可突破人工流程限制,实现大规模软件验证。但现有方法不可靠:缺乏理论基础,优化过程如黑箱,可能导致振荡、循环或发散。本文提出首个具有可证明保证的多阶段验证流水线收敛定理,将交互建模为四个关键工程阶段:CodeGen、Compilation、InvariantSynth 和 SMTSolving。证明只要每个阶段的成功概率 δ > 0,系统几乎必然到达 Verified 状态。由于流水线的顺序性,推导出精确的期望延迟界:𝔼[n] ≤ 4/δ。通过超过90,000次的应力测试验证该预测,结果与理论高度一致:所有运行均成功达成验证,实测收敛因子约1.0,表明4/δ边界准确反映系统行为而非松散缓冲。据此识别出三种运行区域——边缘、实用与高性能,并提出动态校准策略以应对真实环境中的参数漂移。这些贡献将启发式猜测替换为严谨架构基础,实现对安全关键软件的可预测资源规划与性能预算。
原文摘要 · Abstract (English)
The integration of Formal Verification tools with Large Language Models (LLMs) offers a path to scale software verification beyond manual workflows. However, current methods remain unreliable: without a solid theoretical footing, the refinement process acts as a black box that may oscillate, loop, or diverge. This work bridges this critical gap by developing an LLM-Verifier Convergence Theorem, providing the first formal framework with provable guarantees for termination in multi-stage verification pipelines. We model the interaction not as a generic loop, but as a sequential absorbing Markov Chain comprising four essential engineering stages: \texttt{CodeGen}, \texttt{Compilation}, \texttt{InvariantSynth}, and \texttt{SMTSolving}. We prove that for any non-zero stage success probability ($δ> 0$), the system reaches the \texttt{Verified} state almost surely. Furthermore, because of the sequential nature of the pipeline, we derive a precise latency bound of $\mathbb{E}[n] \leq 4/δ$. We stress-tested this prediction in an extensive empirical campaign comprising over 90,000 trials. The results match the theory with striking consistency: every run reached verification, and the empirical convergence factor clustered tightly around $C_f\approx 1.0$, confirming that the $4/δ$ bound accurately mirrors system behavior rather than serving as a loose buffer. Based on this data, we identify three distinct operating zones -- marginal, practical, and high-performance -- and propose a dynamic calibration strategy to handle parameter drift in real-world environments. Together, these contributions replace heuristic guesswork with a rigorous architectural foundation, enabling predictable resource planning and performance budgeting for safety-critical software.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。