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 .”
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: LLM Meets Bounded Model Checking: Neuro-symbolic Loop Invariant Inference. https://app.cochat.ai/papers/10.1145/3691620.3695014
- The paper
- Wu, G., Cao, W., Yao, Y., Wei, H., Chen, T., & Ma, X. (2024). LLM Meets Bounded Model Checking: Neuro-symbolic Loop Invariant Inference. Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering. https://doi.org/10.1145/3691620.3695014
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.