EMNLP Findings2023
Ranking LLM-Generated Loop Invariants for Program Verification
Saikat Chakraborty, Shuvendu K. Lahiri, Sarah Fakhoury, Akash Lal, Madanlal Musuvathi, Aseem Rastogi, Aditya Senthilnathan, Rahul Sharma, Nikhil Swamy
Abstract
Synthesizing inductive loop invariants is fundamental to automating program verification. In this work, we observe that Large Language Models (such as gpt-3.5 or gpt-4) are capable of synthesizing loop invariants for a class of programs in a 0-shot setting, yet require several samples to generate the correct invariants. This can lead to a large number of calls to a program verifier to establish an invariant. To address this issue, we propose a re-ranking approach for the generated results of LLMs. We have designed a ranker that can distinguish between correct inductive invariants and incorrect attempts based on the problem definition. The ranker is optimized as a contrastive ranker. Experimental results demonstrate that this re-ranking mechanism significantly improves the ranking of correct invariants among the generated candidates, leading to a notable reduction in the number of calls to a verifier.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
24 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Verified Code Transpilation with LLMs cites Language Models are Few-Shot Learners
- Verified Code Transpilation with LLMs cites Can Large Language Models Reason about Program Invariants?
- SpecGen: Automated Generation of Formal Program Specifications via Large Language Models cites Language Models are Few-Shot Learners
- SpecGen: Automated Generation of Formal Program Specifications via Large Language Models cites Can Large Language Models Reason about Program Invariants?
- LLM Meets Bounded Model Checking: Neuro-symbolic Loop Invariant Inference cites Training language models to follow instructions with human feedback
- LLM Meets Bounded Model Checking: Neuro-symbolic Loop Invariant Inference cites Can Large Language Models Reason about Program Invariants?
- LLMDFA: Analyzing Dataflow in Code with Large Language Models cites Language Models are Few-Shot Learners
- LLMDFA: Analyzing Dataflow in Code with Large Language Models cites Can Large Language Models Reason about Program Invariants?
- Laurel: Unblocking Automated Verification with Large Language Models cites Dense Passage Retrieval for Open-Domain Question Answering
- Laurel: Unblocking Automated Verification with Large Language Models cites Can Large Language Models Reason about Program Invariants?
- Large Language Models are Zero-Shot Reasoners cites Language Models are Few-Shot Learners
- Large Language Models are Zero-Shot Reasoners cites Training language models to follow instructions with human feedback
- Training language models to follow instructions with human feedback cites Language Models are Few-Shot Learners
Cited by top-tier papers24
- LLMDFA: Analyzing Dataflow in Code with Large Language ModelsChengpeng Wang, Wuqi Zhang, Zian Su, Xiangzhe Xu et al.NeurIPS 2024 · 51 citations
- Verified Code Transpilation with LLMsSahil Bhatia, Jie Qiu, Niranjan Hasabnis, Sanjit A. Seshia et al.NeurIPS 2024 · 36 citations
- SpecGen: Automated Generation of Formal Program Specifications via Large Language ModelsLezhi Ma, Shangqing Liu, Yi Li, Xiaofei Xie et al.ICSE 2025 · 25 citations
- Laurel: Unblocking Automated Verification with Large Language ModelsEric Mugnier, Emmanuel Anaya Gonzalez, Nadia Polikarpova, Ranjit Jhala et al.OOPSLA 2025 · 12 citations
- LLM Meets Bounded Model Checking: Neuro-symbolic Loop Invariant InferenceGuangyuan Wu, Weining Cao, Yuan Yao, Hengfeng Wei et al.ASE 2024 · 9 citations
Builds on6
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Training language models to follow instructions with human feedbackLong Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida et al.NeurIPS 2022 · 24,707 citations
- Large Language Models are Zero-Shot ReasonersTakeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo et al.NeurIPS 2022 · 8,168 citations
- Dense Passage Retrieval for Open-Domain Question AnsweringVladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis et al.EMNLP 2020 · 142 citations
- Can Large Language Models Reason about Program Invariants?Kexin Pei, David Bieber, Kensen Shi, Charles Sutton et al.ICML 2023 · 128 citations
Related papers
- Not All Invariants Are Equal: Curating Training Data to Accelerate Program Verification with SLMsIdo Pinto, Yizhak Elboher, Haoze Wu, Nina Narodytska et al.ICML 2026 · 1 citation
- Enchanting Program Specification Synthesis by Large Language Models Using Static Analysis and Program VerificationCheng Wen, Jialun Cao, Jie Su, Zhiwu Xu et al.CAV 2024 · 60 citations
- Towards AI-Assisted Synthesis of Verified Dafny MethodsMd Rakib Hossain Misu, Cristina V. Lopes, Iris Ma, James NobleFSE 2024 · 26 citations
- HoarePrompt: Structural Reasoning About Program Correctness in Natural LanguageDimitrios Stamatios Bouras, Yihan Dai, Tairan Wang, Yingfei Xiong et al.ICSE 2026
- Code Repair with LLMs gives an Exploration-Exploitation TradeoffHao Tang, Keya Hu, Jin Zhou, Sicheng Zhong et al.NeurIPS 2024 · 85 citations
