Path-Sensitive Loop Invariant Inference via Large Language Models and Abstract Interpretation
ACM Transactions on Software Engineering and Methodology · 28.07.2026
DOI: 10.1145/3834570 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Software Engineering and Methodology, online erschienen am 28.07.2026. Verfasst von Guangsheng Fan und 5 weiteren Autor:innen. Die Arbeit nennt 80 Literaturangaben.
Abstract (Originalsprache)
Loop invariant inference remains a core challenge in program verification, particularly when disjunctive invariants are required. In this paper, we present a path-sensitive loop invariant inference approach based on Large Language Models (LLMs) and abstract interpretation. We apply abstract interpretation to derive initial invariants, which, if insufficient to verify the program, guide an LLM-based agent to generate more precise, path-specific clauses. The core of our method is Counterexample-Guided Clause Combination (CEGCC), a novel strategy that constructs candidate invariants as disjunctions of clause conjunctions satisfied by counterexamples across loop paths, and iteratively refines them using counterexamples generated by the SMT solver during verification. This shifts the focus of invariant synthesis from blind enumeration to semantic refinement driven by genuine counterexample verification and generation. To further refine this approach, we leverage dependencies across different loop paths, apply abstract interpretation to improve SMT solving, and deploy a second LLM-based agent for counterexample verification and mutation. Results show PAL2Inv matches state-of-the-art LLM methods on linear benchmarks and verifies 53–142% more programs on multi-phase benchmarks, while remaining competitive with specialized symbolic multi-phase verifiers.
Zitieren
APA
Fan, G., Chen, L., Yao, P., Yin, B., Zhang, W., & Wang, J. (2026). Path-Sensitive Loop Invariant Inference via Large Language Models and Abstract Interpretation. ACM Transactions on Software Engineering and Methodology. https://doi.org/10.1145/3834570
Vancouver
Fan G, Chen L, Yao P, Yin B, Zhang W, Wang J. Path-Sensitive Loop Invariant Inference via Large Language Models and Abstract Interpretation. ACM Transactions on Software Engineering and Methodology. 2026. doi:10.1145/3834570
BibTeX
@article{Fan2026,
author = {Fan, Guangsheng and Chen, Liqian and Yao, Peisen and Yin, Banghu and Zhang, Wenyu and Wang, Ji},
title = {Path-Sensitive Loop Invariant Inference via Large Language Models and Abstract Interpretation},
journal = {ACM Transactions on Software Engineering and Methodology},
year = {2026},
doi = {10.1145/3834570}
}
EUVIMED