Skip to content
Open access

RecurIC3: Exploiting Structural Lemma Reuse to Accelerate IC3

Oct 2026 · Proceedings of the ACM on Software Engineering · Vol 3, pp. 3043 - 3061 · 0 citations · 4 references

TL;DR

RecurIC3, a framework that alleviates redundant exploration due to the lack of a cross-level memory mechanism via structural reuse, is proposed and results suggest that structural reuse can substantially accelerate IC3.

Abstract

IC3/PDR has become a widely adopted technique for safety model checking due to its high efficiency. Despite its success, the algorithm often suffers from redundant exploration due to the lack of a cross-level memory mechanism. This results in the repetitive discovery of highly similar CTIs (Counterexamples to Induction), forcing the solver to waste computational effort traversing overlapping blocking chains. We propose RecurIC3, a framework that alleviates this bottleneck via structural reuse. RecurIC3 maintains a Bad State Tree (G_bad) that persistently records CTIs together with their level-aligned predecessor–successor links along blocking chains, turning the blocking phase into a history-aware process. To reduce solver calls, RecurIC3 first retrieves and rechecks lightweight candidates from G_bad and falls back to solver queries only when reuse is exhausted. This approach can significantly reduce the search space, thereby enhancing the verification efficiency of IC3. We implemented RecurIC3 in the state-of-the-art model checker Kind2 and evaluated it on the official benchmark suite. On instances where reuse is triggered, RecurIC3 reduces the number of explored tree nodes by 27%, achieves a 1.42× cumulative speedup, and solves 16 additional instances (13 Safe and 3 Unsafe) within the same timeout. These results suggest that structural reuse can substantially accelerate IC3.

Read PDF

Similar papers

CORE: Conflict-Oriented Reasoning Elimination for Verifiable Language-Model Search

Test-time reasoning systems often respond to failure by restarting or revising the latest step, even when an earlier decision caused the error. We introduce CORE, a search controller that requests a certified conflict core from a verifier, backjumps to the latest decision in that core, and caches the conflict to avoid...

Si-Yu Song, Rui-Peng Xu, Jia Lin et al. · 0 citations
Sep 2026

SLED-IFV: Solver-Validated LLM-Guided Decomposition for Scalable Hardware Information-Flow Verification

This work identifies two recurring proof barriers in self-composed IFV: implementation complexity, where proof-hard datapath logic dominates even though the property needs only a compact boundary relation, and relational inductive complexity, where the proof depends on cross-copy public-control facts that the backend p...

Liang-Tao Dai, Yi-Min Gao, Melika Morsali et al. · 0 citations
Preprint Oct 2026

Symbolic Search Is Not Exhausted: Persistent Proof-Space Exploration in Lean4

Formal theorem proving increasingly combines learned semantic guidance with verified symbolic execution. The quality of the symbolic search substrate therefore determines how much useful mathematical structure can be accumulated, reused, and exposed under a finite inference budget. We introduce ViaLean, a Lean4 prover...

Ruoran Xu · 0 citations
Open access Oct 2026

CAST: A Compiler-Based Framework for Systematically Testing LLM Compositional Safety

This paper proposes CAST, a systematic testing framework designed to evaluate the compositional safety of LLMs in the domain of malicious code, and demonstrates that CAST systematically exposes severe safety violations in strongly aligned models that resist conventional red-teaming.

Lu Yan, Zhuo Zhang, Xiang-Zhe Xu et al. · 0 citations
Preprint Nov 2026

Verified Implementation of the Next-gen Borrow Checking Algorithm for Rust via Abstract Interpretation

Borrow checking is a central mechanism for Rust to ensure temporal memory safety. Its correctness is based on the intuition that the Aliasing XOR Mutability discipline guarantees that programs without borrow errors inherently could not access invalid references (i.e., pointers). However, existing work on formalizing bo...

Jin-Hua Wu, Yu-Ting Wang, Zhe-Min Chen · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.