LimICE: Integrating LLM into ICE Framework for Efficient Loop Invariant Inference
增量ICE框架让LLM推断循环不变量解得更多也更快:如果你的工具用LLM合成循环不变量,一次性生成整条的方案在复杂循环上经常失败。LimICE改让LLM按序生成一条条引理,每步用已验证引理过滤反例:在367个线性基准上解349题(均值15.2秒),比最优LLM基线多解12-24%实例且快36-63%。
现有LLM方法把循环不变量当作单一公式一次生成,复杂问题下无法同时满足所有约束而失败;LimICE把不变量拆成有序引理序列逐步推导,每步用已得引理过滤反例来约束后续生成。在367个线性和50个非线性基准上,它比最优LLM基线多解12-24%实例且快36-63%,7B模型仍能解326个线性问题。
把循环不变量拆成有序引理序列并增量推导,比一次性整体生成多解12-24%实例且快36-63%;依据是367个线性和50个非线性基准上的对比实验。
1. 旧假设缺口:现有LLM方法整体生成循环不变量,无法严格约束生成过程,复杂问题时遗漏必要约束导致失败;ICE框架中反例持续累积也会过度约束合成、损害可扩展性。 2. 构造与受控检查:把不变量拆成有序引理序列(bounding lemma+essential lemma)并定义引理专属目标,每推出新引理就过滤相关反例以控制反例集规模;LLM生成序列、SMT校验、ICE-DT兜底,在367线性+50非线性基准上与最优LLM及多个非LLM基线对比。 3. 决定性结果与行动:线性349/367(15.2秒)、非线性47/50(8.8秒),比最优LLM基线多解12-24%且快36-63%;7B模型线性解326题但非线性仅32题,部署小模型时先确认目标场景以线性为主。
线性基准367题,非线性50题。LimICE线性解349/367(均值15.2秒),非线性解47/50(均值8.8秒)。对比最优LLM基线:多解12-24%实例,速度快36-63%。对比非LLM强基线:线性多解至少86题,非线性多解至少27题。7B小模型测试:线性解326题,非线性仅解32题,暴露小模型在复杂非线性引理生成上的局限。
- 它要解决什么
- 现有LLM方法为什么在复杂循环不变量合成中频繁失败?把不变量拆成有序引理序列、逐步增量推导,能不能同时提高解题率和速度?
- 研究路径
- 框架把不变量ψ₁,...,ψₙ分成bounding lemma(约束变量范围)和essential lemma(捕获语义),两类引理之间存在相对归纳依赖关系(IC3中的relative inductiveness)。每推导出新引理后,用它过滤已有的归纳反例和负反例,阻止反例集膨胀。LLM按引理顺序生成候选,SMT求解器校验正确性,ICE-DT补全LLM未覆盖的引理。
- 这对工程意味着什么
- 第一行动:把验证工具中的LLM接口改为逐步输出引理序列,并用已验证引理过滤后续反例。要避免的捷径:不要让LLM端到端一次生成完整不变量,这种方式在复杂约束下会漏掉关键条件。
- 证据定位
- 线性基准解349/367,均值15.2秒;非线性基准解47/50,均值8.8秒。对比最优LLM基线:多解12-24%实例,速度快36-63%。对比非LLM强基线:线性多解至少86题,非线性多解至少27题。(筛选维度:形式化验证、可复核评测)
- 适用边界
- 基准仅覆盖367个线性和50个非线性程序验证题,规模有限;非线性场景下7B模型只解32题,小模型的泛化边界尚未充分探明;文本摘录未披露基准来源的多样性与程序类型分布。
方法与英文摘要
实验覆盖367个线性和50个非线性程序验证基准。框架把不变量建模为两类引理组成的有序序列:bounding lemma约束变量范围,essential lemma捕获语义,并为每类引理定义专属学习目标。每推出一条新引理,就用它过滤已有的归纳反例和负反例,防止反例集膨胀。LLM按顺序生成引理候选,SMT求解器负责校验,ICE-DT兜底补全LLM没覆盖到的引理。
Loop invariant synthesis is a fundamental problem in program verification, yet the inherent undecidability makes it highly challenging. Recent studies have increasingly employed various machine learning techniques to generate loop invariants. However, most of these methods adopt a monolithic approach. Due to the inability to strictly constrain the learning process, learning-based methods struggle to simultaneously consider all necessary conditions and generate complete invariants when tackling complex problems. In fact, a loop invariant is often an ordered sequence of lemmas, rather than a single invariant formula. This motivates us to propose Incremental ICE, a novel learning framework for incremental synthesis. Our framework integrates the incremental philosophy of IC3 into the general invariant learning framework ICE. By defining a lemma-specific learning objective and introducing a counterexample filtering mechanism, we can achieve sound incremental learning. Under this framework, we instantiate a loop invariant synthesis tool, LimICE, which leverages LLMs to generate the ordered sequence of lemmas and incorporates ICE-DT as a fallback mechanism to complement the lemma sequence. Experiments on 367 linear benchmarks and 50 nonlinear benchmarks demonstrate the effectiveness of the proposed approach. LimICE solves 349 (out of 367) linear problems on an average of 15.2 seconds and 47 (out of 50) nonlinear problems on an average of 8.8 seconds. Compared to the state-of-the-art LLM-based baseline, our approach solves 12-24% more instances while running 36-63% faster across linear and nonlinear benchmarks. LimICE also consistently outperforms strong non-LLM baselines and solves at least 86 and 27 additional instances on the linear and nonlinear benchmarks, respectively.