LLM Meets Bounded Model Checking: Neuro-symbolic Loop Invariant Inference
The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Abstract
Loop invariant inference, a key component in program verification, is a challenging task due to the inherent undecidability and complex loop behaviors in practice. Recently, machine learning based techniques have demonstrated impressive performance in generating loop invariants automatically. However, these methods highly rely on the labeled training data, and are intrinsically random and uncertain, leading to unstable performance. In this paper, we investigate a synergy of large language models (LLMs) and bounded model checking (BMC) to address these issues. The key observation is that, although LLMs may not be able to return the correct loop invariant in one response, they usually can provide all individual predicates of the correct loop invariant in multiple responses. To this end, we propose a "query-filter-reassemble" strategy, namely, we first leverage the language generation power of LLMs to produce a set of candidate invariants, where training data is not needed. Then, we employ BMC to identify valid predicates from these candidate invariants, which are assembled to produce new candidate invariants and checked by off-the-shelf SMT solvers. The feedback is incorporated into the prompt for the next round of LLM querying. We expand the existing benchmark of 133 programs to 316 programs, providing a more comprehensive testing ground. Experimental results demonstrate that our approach significantly outperforms the state-of-the-art techniques, successfully generating 309 loop invariants out of 316 cases, whereas the existing baseline methods are only able to tackle 219 programs at best. The code is publicly available at https://github.com/SoftWiser-group/LaM4Inv.git.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
International Conference on Learning Representations (ICLR 2013)
松尾, 豊. (2013) · 人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence · Cited by 6,286
Cousot, P., & Cousot, R. (1977) · Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '77 · doi:10.1145/512950.512973 · Cited by 6,279
An axiomatic basis for computer programming
Hoare, C. A. R. (1969) · Communications of the ACM · doi:10.1145/363235.363259 · Cited by 4,002 · cited 1×
“By well-known Hoare logic [25], for a given loop while 𝐵 do 𝑆 , the loop invariant inference problem aims to identify a loop invariant 𝐼 that satisfies where 𝑃 is the pre-condition , 𝑄 is the post-condition , and 𝑆 is the loop body with 𝐵 as the loop condition.”
Systematic design of program analysis frameworks
Cousot, P., & Cousot, R. (1979) · Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '79 · doi:10.1145/567752.567778 · Cited by 1,621
Automatic discovery of linear restraints among variables of a program
Cousot, P., & Halbwachs, N. (1978) · Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '78 · doi:10.1145/512760.512770 · Cited by 1,614 · cited 1×
“Traditional loop invariant inference meth-ods mainly rely on symbolic methods such as abduction analysis [6, 16], dynamic analysis [18, 19, 31], model checking [26, 47], Craig interpolation [27, 34], abstract interpretation [12–14, 29] , random search [ 43], Learning-based approaches .”
Mathematical Principles of Fuzzy Logic
Novák, V., Perfilieva, I., & Močkoř, J. (1999) · Springer eBooks · doi:10.1007/978-1-4615-5217-8 · Cited by 1,240
Counterexample-guided abstraction refinement for symbolic model checking
Clarke, E., Grumberg, O., Jha, S., Lu, Y., & Veith, H. (2003) · Journal of the ACM · doi:10.1145/876638.876643 · Cited by 994
Barrett, C., Conway, C. L., Deters, M., Hadarean, L., Jovanović, D., King, T., Reynolds, A., & Tinelli, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22110-1_14 · Cited by 655
cvc5: A Versatile and Industrial-Strength SMT Solver
Barbosa, H., Barrett, C., Brain, M., Kremer, G., Lachnitt, H., Mann, M., Mohamed, A., Mohamed, M., Niemetz, A., Nötzli, A., et al. (2022) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-99524-9_24 · Cited by 468
Affine relationships among variables of a program
Karr, M. (1976) · Acta Informatica · doi:10.1007/bf00268497 · Cited by 439 · cited 1×
“Traditional loop invariant inference meth-ods mainly rely on symbolic methods such as abduction analysis [6, 16], dynamic analysis [18, 19, 31], model checking [26, 47], Craig interpolation [27, 34], abstract interpretation [12–14, 29] , random search [ 43], Learning-based approaches .”
Linear Invariant Generation Using Non-linear Constraint Solving
Colón, M. A., Sankaranarayanan, S., & Sipma, H. B. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45069-6_39 · Cited by 351
ICE: A Robust Framework for Learning Invariants
Garg, P., Löding, C., Madhusudan, P., & Neider, D. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-08867-9_5 · Cited by 186
A Practical and Complete Approach to Predicate Refinement
Jhala, R., & McMillan, K. L. (2006) · Lecture Notes in Computer Science · doi:10.1007/11691372_33 · Cited by 185 · cited 1×
“Traditional loop invariant inference meth-ods mainly rely on symbolic methods such as abduction analysis [6, 16], dynamic analysis [18, 19, 31], model checking [26, 47], Craig interpolation [27, 34], abstract interpretation [12–14, 29] , random search [ 43], Learning-based approaches .”
ESBMC 5.0: an industrial-strength C model checker
Gadelha, M. R., Monteiro, F. R., Morse, J., Cordeiro, L. C., Fischer, B., & Nicole, D. A. (2018) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/3238147.3240481 · Cited by 153 · cited 1×
“We compare LaM4Inv with 8 existing methods including LoopInvGen [38], CVC5 [3], Code2Inv [46], LIPUS [54], CLN2INV [42], G-CLN [52], ESBMC [21], and LEMUR [50].”
Deep learning-based software engineering: progress, challenges, and opportunities
Chen, X., Hu, X., Huang, Y., Jiang, H., Ji, W., Jiang, Y., Jiang, Y., Liu, B., Liu, H., Li, X., et al. (2024) · Science China Information Sciences · doi:10.1007/s11432-023-4127-5 · Cited by 152 · cited 1×
“Recently, machine learning and deep learning techniques have been employed in various software engineering tasks [8].”
Software Verification Using k-Induction
Donaldson, A. F., Haller, L., Kroening, D., & Rümmer, P. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23702-7_26 · Cited by 142
State of the Art in Software Verification and Witness Validation: SV-COMP 2024
Beyer, D. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-57256-2_15 · Cited by 123 · cited 2×
“Additionally, we have manually crafted 84 problems from the 2019 SyGuS competition [1] and 99 problems from the 2024 SV-COMP benchmarks [5].”
Lazy Annotation for Program Testing and Verification
McMillan, K. L. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14295-6_10 · Cited by 119 · cited 1×
“Traditional loop invariant inference meth-ods mainly rely on symbolic methods such as abduction analysis [6, 16], dynamic analysis [18, 19, 31], model checking [26, 47], Craig interpolation [27, 34], abstract interpretation [12–14, 29] , random search [ 43], Learning-based approaches .”
Sharma, R., Nori, A. V., & Aiken, A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31424-7_11 · Cited by 108 · cited 1×
“Specifically, for the loop invariant inference problem, existing methods mainly use decision tree [20, 22, 23, 41, 51], support vector machine [32, 45], PAC learning [44], reinforcement learning [46, 54], continuous logic networks [42, 52], and LLMs [7, 28, 33, 48, 50] under the guess-and-check…”
Verification as Learning Geometric Concepts
Sharma, R., Gupta, S., Hariharan, B., Aiken, A., & Nori, A. V. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38856-9_21 · Cited by 88 · cited 1×
“…for the loop invariant inference problem, existing methods mainly use decision tree [20, 22, 23, 41, 51], support vector machine [32, 45], PAC learning [44], reinforcement learning [46, 54], continuous logic networks [42, 52], and LLMs [7, 28, 33, 48, 50] under the guess-and-check framework.”
Validating SMT solvers via semantic fusion
Winterer, D., Zhang, C., & Su, Z. (2020) · Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/3385412.3385985 · Cited by 82 · cited 1×
“This limitation becomes a bottleneck for some methods [49, 54].”
Horn-ICE learning for synthesizing invariants and contracts
Ezudheen, P., Neider, D., D’Souza, D., Garg, P., & Madhusudan, P. (2018) · Proceedings of the ACM on Programming Languages · doi:10.48550/arxiv.1712.09418 · Cited by 77 · cited 2×
“Indeed, various machine learning techniques have been applied to generate candidate invariants including decision tree [20, 23, 51], reinforcement learning [46, 54], continuous logic networks [42, 52] and large language models (LLMs, [7, 28, 33, 50]).”
Wen, C., Cao, J., Su, J., Xu, Z., Qin, S., He, M., Li, H., Cheung, S.-C., & Tian, C. (2024) · Lecture Notes in Computer Science · doi:10.1007/978-3-031-65630-9_16 · Cited by 69
Learning invariants using decision trees and implication counterexamples
Garg, P., Neider, D., Madhusudan, P., & Roth, D. (2016) · ACM SIGPLAN Notices · doi:10.1145/2914770.2837664 · Cited by 63
Gupta, A., Majumdar, R., & Rybalchenko, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00768-2_24 · Cited by 59
Data-driven precondition inference with learned features
Padhi, S., Sharma, R., & Millstein, T. D. (2016) · ACM SIGPLAN Notices · doi:10.1145/2980983.2908099 · Cited by 52
Inductive invariant generation via abductive inference
Dillig, I., Dillig, T., Li, B., & McMillan, K. L. (2013) · ACM SIGPLAN Notices · doi:10.1145/2544173.2509511 · Cited by 46
From invariant checking to invariant inference using randomized search
Sharma, R., & Aiken, A. (2016) · Formal Methods in System Design · doi:10.1007/s10703-016-0248-5 · Cited by 40 · cited 1×
“Traditional loop invariant inference meth-ods mainly rely on symbolic methods such as abduction analysis [6, 16], dynamic analysis [18, 19, 31], model checking [26, 47], Craig interpolation [27, 34], abstract interpretation [12–14, 29] , random search [ 43], Learning-based approaches .”
Bi-abductive Resource Invariant Synthesis
Calcagno, C., Distefano, D., & Vafeiadis, V. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10672-9_19 · Cited by 37 · cited 1×
“Traditional loop invariant inference meth-ods mainly rely on symbolic methods such as abduction analysis [6, 16], dynamic analysis [18, 19, 31], model checking [26, 47], Craig interpolation [27, 34], abstract interpretation [12–14, 29] , random search [ 43], Learning-based approaches .”
Ranking LLM-Generated Loop Invariants for Program Verification
Chakraborty, S., Lahiri, S., Fakhoury, S., Lal, A., Musuvathi, M., Rastogi, A., Senthilnathan, A., Sharma, R., & Swamy, N. (2023) · Findings of the Association for Computational Linguistics: EMNLP 2023 · doi:10.18653/v1/2023.findings-emnlp.614 · Cited by 37
Automatic loop-invariant generation anc refinement through selective sampling
Li, J., Sun, J., Li, L., Le, Q. L., & Lin, S. (2017) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.2017.8115689 · Cited by 36 · cited 1×
“Specifically, for the loop invariant inference problem, existing methods mainly use decision tree [20, 22, 23, 41, 51], support vector machine [32, 45], PAC learning [44], reinforcement learning [46, 54], continuous logic networks [42, 52], and LLMs [7, 28, 33, 48, 50] under the guess-and-check…”
Loop Invariant Inference through SMT Solving Enhanced Reinforcement Learning
Yu, S., Wang, T., & Wang, J. (2023) · ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) · doi:10.1145/3597926.3598047 · Cited by 36 · cited 8×
“This limitation becomes a bottleneck for some methods [49, 54].”
InfluentialInterval counterexamples for loop invariant learning
Xu, R., He, F., & Wang, B.-Y. (2020) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/3368089.3409752 · Cited by 31 · cited 2×
“Indeed, various machine learning techniques have been applied to generate candidate invariants including decision tree [20, 23, 51], reinforcement learning [46, 54], continuous logic networks [42, 52] and large language models (LLMs, [7, 28, 33, 50]).”
SLING: using dynamic analysis to infer program invariants in separation logic
Le, T. C., Zheng, G., & Nguyen, T. H. (2019) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/3314221.3314634 · Cited by 21 · cited 1×
“Traditional loop invariant inference meth-ods mainly rely on symbolic methods such as abduction analysis [6, 16], dynamic analysis [18, 19, 31], model checking [26, 47], Craig interpolation [27, 34], abstract interpretation [12–14, 29] , random search [ 43], Learning-based approaches .”
Finding Inductive Loop Invariants using Large Language Models
Kamath, A., Senthilnathan, A., Chakraborty, S., Deligiannis, P., Lahiri, S. K., Lal, A., Rastogi, A., Roy, S., & Sharma, R. (2023) · arXiv · doi:10.48550/arxiv.2311.07948 · Cited by 17
Zhu, H., Nori, A. V., & Jagannathan, S. (2015) · ACM SIGPLAN Notices · doi:10.1145/2858949.2784766 · Cited by 15
Multi-phase invariant synthesis
Riley, D., & Fedyukovich, G. (2022) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/3540250.3549166 · Cited by 13
Ilinva: Using Abduction to Generate Loop Invariants
Echenim, M., Peltier, N., & Sellami, Y. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-29007-8_5 · Cited by 8
Towards General Loop Invariant Generation: A Benchmark of Programs with Memory Manipulation
Liu, C., Wu, X., Feng, Y., Cao, Q., & Yan, J. (2023) · arXiv · doi:10.48550/arxiv.2311.10483 · Cited by 7
Learning nonlinear loop invariants with gated continuous logic networks
Yao, J., Ryan, G., Wong, J., Jana, S., & Gu, R. (2020) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3385412.3385986 · Cited by 2 · cited 7×
“Previous tools (e.g., LoopInvGen [38], Code2Inv [46], CLN2INV [42], G-CLN [52], and LIPUS [54]) have struggled to identify the correct solution in this example.”
Influential
Research works printed but not linked: 15
- Rajeev Alur, Dana Fisman, Saswat Padhi, Rishabh Singh, and Abhishek Udupa. 2019. SyGuS-Comp 2018: Results and Analysis. CoRR abs/1904.07146 (2019). arXiv preprint arXiv:1904.07146 (2019). · arXiv
- Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. 2017. Sygus-comp 2017: Results and analysis. arXiv preprint arXiv:1711.11438 (2017). · arXiv
- Edmund Clarke, Armin Biere, Richard Raimi, and Yunshan Zhu. 2001. Bounded model checking using satisfiability solving. Formal methods in system design 19 (2001), 7--34.
- 10.5555/1792734.1792766 · doi:10.5555/1792734.1792766
- Michael D Ernst, Jeff H Perkins, Philip J Guo, Stephen McCamant, Carlos Pacheco, Matthew S Tschantz, and Chen Xiao. 2007. The Daikon system for dynamic detection of likely invariants. Science of computer programming 69, 1--3 (2007), 35--45.
- 10.1145/3276501 · doi:10.1145/3276501
- Hossein Hojjat and Philipp Rümmer. 2018. The ELDARICA horn solver. In 2018 Formal Methods in Computer Aided Design (FMCAD). IEEE, 1--7.
- Chris Lattner. 2008. LLVM and Clang: Next generation compiler technology. In The BSD conference, Vol. 5. 1--20.
- Long Ouyang Jeffrey Wu Xu Jiang Diogo Almeida Carroll Wainwright Pamela Mishkin Chong Zhang Sandhini Agarwal Katarina Slama Alex Ray et al. 2022. Training language models to follow instructions with human feedback. Advances in neural information processing systems (NeurIPS) 35 (2022) 27730--27744.
- Kexin Pei, David Bieber, Kensen Shi, Charles Sutton, and Pengcheng Yin. 2023. Can large language models reason about program invariants?. In International Conference on Machine Learning. PMLR, 27496--27520.
- Mukund Raghothaman and Abhishek Udupa. 2014. Language to specify syntax-guided synthesis problems. arXiv preprint arXiv:1405.5590 (2014). · arXiv
- Xujie Si, Hanjun Dai, Mukund Raghothaman, Mayur Naik, and Le Song. 2018. Learning loop invariants for program verification. Advances in Neural Information Processing Systems (NeurIPS) 31 (2018).
- Hari Govind Vediramana Krishnan, YuTing Chen, Sharon Shoham, and Arie Gurfinkel. 2023. Global guidance for local generalization in model checking. Formal Methods in System Design (2023), 1--29.
- Haoze Wu, Clark Barrett, and Nina Narodytska. 2024. Lemur: Integrating Large Language Models in Automated Program Verification. In The Twelfth International Conference on Learning Representations (ICLR).
- Jianan Yao, Ziqiao Zhou, Weiteng Chen, and Weidong Cui. 2023. Leveraging large language models for automated proof synthesis in rust. arXiv preprint arXiv:2311.03739 (2023). · arXiv
Cited by
Clause2Inv: A Generate-Combine-Check Framework for Loop Invariant Inference
Cao, W.-Q., Wu, G., Xu, T., Yao, Y., Wei, H., Chen, T., & Ma, X. (2025) · Proceedings of the ACM on software engineering. · doi:10.1145/3728920 · Cited by 31
Self-citationPosition: Vibe Coding Needs Vibe Reasoning: Improving Vibe Coding with Formal Verification
Mitchell, J., & Shaaban, Y. (2025) · Proceedings of the 1st ACM SIGPLAN International Workshop on Language Models and Programming Languages · doi:10.1145/3759425.3763390 · Cited by 8
“…methods to filter out solutions that do not satisfy a certain specification, and provide feedback (e.g., a counterexample) to the LLM, iterating until a valid solution is reached (e.g., loop-invariant synthesis with formal tools in the loop [2, 12, 20, 21, 38], static analysis-guided repair [27]).”
Automatic Generation of Loop Invariants in Dafny with Large Language Models
Faria, J. P., Trigo, E., & Abreu, R. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-87054-5_10 · Cited by 6
ClassInvGen: Class Invariant Synthesis Using Large Language Models
Sun, C., Agashe, V., Chakraborty, S., Taneja, J., Barrett, C., Dill, D. L., Qiu, X., & Lahiri, S. K. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-99991-8_4 · Cited by 17
Understanding Formal Reasoning Failures in LLMs as Abstract Interpreters
Mitchell, J., Kim, B. H., Zhou, C., & Wang, C. (2025) · ACM SIGPLAN International Workshop on Language Models and Programming Languages (LMPL) · doi:10.1145/3759425.3763389 · Cited by 5
Metadata
- Authors
- Wu, G., Cao, W., Yao, Y., Wei, H., Chen, T., & Ma, X.
- Affiliations
- Nanjing University (CN)
- State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu, China
- Birkbeck, University of London (GB)
- Venue
- Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering
- Publisher
- ACM
- Published
- 2024-10-27
- Pages
- 406-417
- OpenAlex
- W4403536765
- Cited by
- 24
- References
- 39
- Citations by year
- 2026: 18 · 2025: 6
- FWCI
- 15.60
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE/ACM International Conference on Automated Software Engineering (ASE) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Formal Methods in Verification
- Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Keywords
- large language models, bounded model checking, program verification, neuro-symbolic reasoning, SMT solvers, immediate feedback, invariant generation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.