Lemma Discovery in Agentic Program Verification DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Software and its engineering Formal software verification CCS: Security and privacy Logic and verification

Huan Zhao, Haoxin Tu, Zhengyao Liu, Martin Rinard, Abhik Roychoudhury · 2026

Read Lemma Discovery in Agentic Program Verification DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Software and its engineering Formal software verification CCS: Security and privacy Logic and verification by Huan Zhao, Haoxin Tu, Zhengyao Liu, Martin Rinard, Abhik Roychoudhury (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22114.txt.

Introduction

Zhao and co-authors present LemmaNet, an agent that finds helper lemmas for program verification. Deductive verification gives strong correctness guarantees, but proving verification conditions is slow expert work. LemmaNet mines the source code and specs to propose lemmas ahead of time. As a proof unfolds, it adapts stored lemmas to the current proof state. Built on the AutoRocq agent, it is tested on SV-COMP and real code, including Linux kernel modules. The authors report it beats prior state-of-the-art approaches by a wide margin.

Catalog record

CREATORHuan Zhao, Haoxin Tu, Zhengyao Liu, Martin Rinard, Abhik Roychoudhury
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65081
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.22114

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lemma Discovery in Agentic Program Verification DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Software and its engineering Formal software verification CCS: Security and privacy Logic and verification Huan Zhao, Haoxin Tu, Zhengyao Liu, Martin Rinard, Abhik Roychoudhury Abstract . Deductive verification provides strong correctness guarantees for code by extracting verification conditions (VCs) and writing formal proofs for them. The expertise-intensive task of VC proving is the main bottleneck in this process, and has been partly automated owing to recent advances in Large Language Model (LLM) agents. However, existing proof agents are not able to discover helper lemmas – auxiliary lemmas that aid in proving – and thus fall short as programs grow in size and complexity. In this paper, we argue that VC proving for program verification is more than a purely mathematical task, and benefits considerably from program comprehension. Our key insight is that human proof engineers often discover and apply helper lemmas based on their understanding of the program semantics, which are not directly reflected in the VCs produced by VC generators. Inspired by this insight, we propose an LLM agent, LemmaNet , that discovers helper lemmas in two ways. Specifically, the agent first synthesizes lemmas offline by directly analyzing the source code and specifications, and then relating this semantic understanding to the mechanical, verbose encoding produced by VC generators. As the proof unfolds, LemmaNet then adapts existing helper lemmas online to accommodate evolving proof states, enabling the agent to effectively discharge complex VCs on-the-fly. We evaluate LemmaNet on SV-COMP and established real-world subjects, including modules of the Linux kernel, Contiki OS, standard C++ library, and X.509 parser. Our experimental results demonstrate that LemmaNet significantly outperforms state-of-the-art approaches, highlighting the importance of program comprehension aided lemma discovery in agentic program verification. 1. Introduction Trusted software is critical for the safety and security of modern computing systems, especially in safety-critical domains such as aerospace, automotive, and healthcare ( 8 ; 36 ; 31 ) . In pursuit of this goal, formal verification is a powerful technique that can provide strong guarantees that the software correctly implements its specification ( 55 ; 35 ; 42 ) . One widely used approach is deductive verification , which involves generating mathematical verification conditions (VCs) from source code and specifications, then using interactive theorem provers to generate formal machine-checked proofs of these VCs ( 1 ) . Proving these VCs is currently an extremely labor- and expertise-intensive undertaking, which has significantly hindered its adoption in practice ( 31 ; 36 ) . With recent advances in the mathematical reasoning ability of large language models (LLMs) ( 2 ; 15 ) , there has been growing interest in leveraging LLM agents to assist in the formal verification process ( 38 ; 58 ; 61 ) . Limitations of Existing Approaches. Existing theorem-proving approaches formulate VC proving as a purely mathematical exercise ( 53 ; 52 ; 38 ) , where the input to the system is a theorem statement and the output is a sequence of proof steps that establish its correctness. Recent approaches that adopt this paradigm have therefore focused on improving various aspects of this process ( 61 ; 58 ; 59 ; 54 ) . Human proof engineers take a different approach. When discharging complex obligations, they typically start with an understanding of the program semantics and propose helper lemmas that capture relevant aspects of the program structure and properties ( 18 ; 48 ) . These helper lemmas often identify key observations and/or intermediate results that can considerably simplify the proving process, with the helper lemmas often refined and enhanced in light of new information obtained as the proof progresses. This aspect of proof development remains largely overlooked by existing approaches. As such, they struggle to discharge complex VCs that benefit from insights into the program semantics, structure, and properties. New Angle to VC Proving. We argue that program VC proving is not purely a matter of mathematical reasoning, but should be deeply coupled with program comprehension. Our argument is based on the fact that proofs are easier to develop and interpret when they align with program structure and source-level semantics, with the alignment driven by intermediate lemmas that capture important insights into the program structure, semantics, and properties ( 18 ; 48 ) . For example, to prove a loop invariant obligation (e.g., line 14 in Figure 1 ), a human proof engineer usually first tries to understand the loop’s behavior and write a proper semantics-aware VC that is amenable to straightforward proof (e.g., the semantics-aware VC in Figure 2(b) ). This informal reasoning process is crucial for effectively discharging complex VCs and is often guided by the program semantics, which are not directly reflected in the proof-targeted VCs (e.g., the proof-targeted VC in Figure 2(a) ) generated by existing VC generators (e.g., Frama-C ). We therefore propose to mimic this human proof process by developing an LLM agent that discovers helper lemmas informed by program structure and semantics, aiming to bridge the gap between the program semantics and the proof-targeted VCs, and thus facilitate the proving process. Challenges. Two challenges need to be addressed to enable such a human-like proving process for effective automated verification. First, existing VC generators model the full complexity of the language semantics, including aspects such as integer overflow, pointer arithmetic, and memory addressing. The generated VCs obscure the conceptual structure of the program semantics in low-level details that generators use to model these and other aspects of the underlying language semantics. While a naive LLM-based approach can more clearly reflect the program structure, the approach is fundamentally unsound, and the VCs come with no correctness guarantees. Second, as VC complexity grows, it becomes difficult to foresee a priori how proof states will evolve throughout the proving process. As such, proof strategies must dynamically adapt as new information is updated during proving while still preserving the coherence and relevance of the existing reasoning trajectory. Our Solution We propose a new solution, LemmaNet , that addresses the above two challenges through a carefully-designed mechanism of helper lemma discovery . LemmaNet discovers helper lemmas in two stages of the verification workflow. First, LemmaNet performs offline analysis before theorem proving starts to extract a semantics-aware VC directly from the annotated source code. To mitigate the potential untrustworthiness of LLM-based analysis, the semantics-aware VC is used merely as a reference for synthesizing helper lemmas to bridge source-level concepts with the proof-targeted VC. These helper lemmas are ultimately used to discharge the VC produced by a trusted VC generator, ensuring soundness throughout the process. Second, LemmaNet performs online lemma adaptation as proving progresses. This adaptation is achieved by iteratively refining and enhancing the helper lemmas based on the feedback from the theorem prover. Our results indicate that this online adaptation process often enables the agent to effectively discharge complex, otherwise intractable VCs while maintaining the alignment with the program semantics captured by the semantics-aware VC (c.f. Section 5.4 ). By integrating both offline lemma synthesis and online lemma adaptation, LemmaNet is able to effectively discover and apply helper lemmas that are crucial

Read the complete text