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
Preguss: It Analyzes, It Specifies, It Verifies
Wang, Z. Y., Lin, T.-H. J., Chen, M., Yang, M., Li, H., Yi, X., Qin, S., & Yin, J. (2025) · ACM SIGPLAN International Workshop on Language Models and Programming Languages (LMPL) · doi:10.1145/3759425.3763394 · Cited by 1
Seeking Specifications: The Case for Neuro-Symbolic Specification Synthesis
Granberry, G., Ahrendt, W., & Johansson, M. (2026) · Formal Aspects of Computing · doi:10.1145/3785411 · Cited by 7
“For contract-based verification tools, the majority of research on annotation generation has been centered on generating loop invariants (e.g., [14, 17, 21, 35]) needed to verify correctness of programs wrt. a given functional specification.”
Fan, G., Wei, D., & Yin, B. (2026) · Electronics · doi:10.3390/electronics15061148 · Cited by 2
Incorrectness Proofs with Underapproximation Invariants
Takhar, G., & Roy, S. (2026) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3821419 · Cited by 1
Can LLM Aid in Solving Constraints with Inductive Definitions?
Feng, W., Shen, S., Liu, J. J., Chen, T., Song, F., & Wu, Z. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-26220-2_6 · Cited by 1
“LLMs have demonstrated remarkable capabilities in code generation [15,46,45,53], program specification inference [50,31], loop-invariant generation [5,51,36], and interactive theorem proving [39,49].”
Self-citationOn the Use of LLMs to Explain Model Checking Counterexamples
Moreira, E. J. V. F., & Campos, J. C. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-26051-2_8
Bit-Vector CHC Solving for Binary Analysis and Binary Analysis for Bit-Vector CHC Solving
Bembenek, A., & Murray, T. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-28079-4_10
Path-Sensitive Loop Invariant Inference via Large Language Models and Abstract Interpretation
Fan, G., Chen, L., Yao, P., Yin, B., Zhang, W., & Wang, J. (2026) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3834570
I3DP: Neuro-Symbolic Inductive Invariant Inference for Distributed Protocols
Cao, W., Wu, G., Yao, Y., Wei, H., Chen, T., & Ma, X. (2026) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/3830418.3843876
Self-citationLLM-Based Invariant Generation for Multi-Loop Programs via Forward and Backward Iterative Refinement
Zhang, W., Fan, G., Wei, D., Yin, B., & Chen, L. (2026) · IEEE International Conference on Joint Cloud Computing (JCC) · doi:10.1109/jcc72984.2026.00055
“Wu et al. [13] prompt LLM generte clauses for single-loop programs, and combine them to form candidate invariants.”
SpecGuru: Hierarchical LLM-Driven API Points-to Specification Generation with Self-Validation
Kan, S., Li, Y., Cheng, X. Y., & Sui, Y. (2026) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/3744916.3773209 · Cited by 1
Towards Formal Knowledge Routing for Forward Engineering in the ADM Lifecycle
Akik, E., Kordić, S., Vještica, M., Бубњевић, В., Čeliković, M., & Ristić, S. (2026) · Communications in computer and information science · doi:10.1007/978-3-032-39823-9_33
Steering Tree-of-Thought Reasoning via Deductive Verification
Haoliang, C., Tang, E., Zhang, S., Mao, J., Fu, Y., Ma, J., Cui, K., Liu, Y., Tian, Y., Gao, X., et al. (2026) · Proceedings of the ACM on software engineering. · doi:10.1145/3832200
NEAT: Agentic Interpretation: Lattice-Structured Evidence for LLM-Based Program Analysis
Mitchell, J., & Wang, C. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-40374-2_15
Fully Automating Template Polyhedral Analysis by Leveraging LLMs
Huang, R., Chen, L., Fu, H., Yin, B., Wei, D., & Wang, J. (2026) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/3832783.3837472
Verifier-in-the-Loop LLM Solving of Heap Constraints for Concolic Execution
Xia, S., Cheng, L., Dong, C., She, D., Wang, B., Peng, X., & Dong, Z. (2026) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/3832783.3834410
“LLMs have also been applied to property-based testing [58], invariant inference [41, 57], and hybrid analysis.”
Assessing Postcondition Completeness in Auto-Generated Function Contracts for Software Verification
Silveira, C. V. P., & Ferreira, M. F. T. (2026) · Simpósio Brasileiro de Testes de Software Sistemático e Automatizado (SAST) · doi:10.5753/sast.2026.30683
“Other lines of work focused on the generation of loop invariants [39, 41] which were required to prove an already available top-level specification.”
Augmenting Symbolic Execution with Artificial Intelligence: A Systematic Review and Research Agenda
Iavich, M., Kuchukhidze, T., & Lopata, A. (2026) · Applied Sciences · doi:10.3390/app16199969
Functional Verification Using Large Language Models
Andrews, E., & Mishra, P. (2026) · Springer eBooks · doi:10.1007/978-3-032-34116-7_4
Position: Vibe Coding Needs Vibe Reasoning: Improving Vibe Coding with Formal Verification
Mitchell, J., & Shaaban, Y. (2025) · arXiv · 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]).”
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.