Ranking LLM-Generated Loop Invariants for Program Verification
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 {\it
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.
652de4f884595aeba19e3475
Saikat Chakraborty
admin_assigned
2023-10-17T08:08:37.691Z
61eb45548ae3ccab3b3da983
/avatars/168a758c4b856b6cdb3c65dd772a549f.svg
Saikat Chakraborty
user
saikatc
652de4f884595aeba19e3476
Shuvendu K. Lahiri
claimed_verified
2023-10-17T15:11:46.294Z
652e4f747f4b8bd6774c627f
/avatars/fba113932a392da63d58151c66adc42d.svg
Shuvendu K. Lahiri
user
Shuvendu-lahiri
652de4f884595aeba19e3477
Sarah Fakhoury
claimed_verified
2023-11-06T10:57:27.555Z
65486006b8ac1a89ff27544a
/avatars/6d3817537b36cfd33afb9d9bba4265ef.svg
Sarah Fakhoury
user
sfakhoury
652de4f884595aeba19e3478
Madanlal Musuvathi
652de4f884595aeba19e3479
Akash Lal
652de4f884595aeba19e347a
Aseem Rastogi
652de4f884595aeba19e347b
Aditya Senthilnathan
652de4f884595aeba19e347c
Rahul Sharma
652de4f884595aeba19e347d
Nikhil Swamy
Ranking LLM-Generated Loop Invariants for Program Verification
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 {\it
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.
A re-ranking approach using a contrastive ranker improves the accuracy of synthesized loop invariants from LLMs, reducing the need for program verifier calls.
Large Language Models (LLMs) synthesize inductive loop invariants re-ranking contrastive ranker