Stepwise: Neuro-Symbolic Proof Search for Automated Systems Verification

Baoding He, Zenan Li, Wei Sun, Yuan Yao, Taolue Chen, [0.5em] Xiaoxing Ma, Zhendong Su, [0.8em] State Key Laboratory of Novel Software Technology, Nanjing University, China · 2026

Read Stepwise: Neuro-Symbolic Proof Search for Automated Systems Verification by Baoding He, Zenan Li, Wei Sun, Yuan Yao, Taolue Chen, [0.5em] Xiaoxing Ma, Zhendong Su, [0.8em] State Key Laboratory of Novel Software Technology, Nanjing University, China (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-19715.txt.

Introduction

He and co-authors present a neuro-symbolic framework that automates proof search for systems software checks. The system runs a best-first tree search over proof states. At each step it asks a large language model for the next proof step. The models are fine-tuned on pairs of proof states and steps. Symbolic tools repair bad steps, rank states, and close stuck subgoals. On the seL4 benchmark it proved up to 77.6 percent of theorems. That beat earlier language model systems and the Sledgehammer tool alone.

Catalog record

CREATORBaoding He, Zenan Li, Wei Sun, Yuan Yao, Taolue Chen, [0.5em] Xiaoxing Ma, Zhendong Su, [0.8em] State Key Laboratory of Novel Software Technology, Nanjing University, China
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60042
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Stepwise: Neuro-Symbolic Proof Search for Automated Systems Verification Baoding He, Zenan Li, Wei Sun, Yuan Yao, Taolue Chen, [0.5em] Xiaoxing Ma, Zhendong Su, [0.8em] State Key Laboratory of Novel Software Technology, Nanjing University, China Abstract Formal verification via interactive theorem proving is increasingly used to ensure the correctness of critical systems, yet constructing large proof scripts remains highly manual and limits scalability. Advances in large language models (LLMs), especially in mathematical reasoning, make their integration into software verification increasingly promising. This paper introduces a neuro-symbolic proof generation framework designed to automate proof search for systems-level verification projects. The framework performs a best-first tree search over proof states, repeatedly querying an LLM for the next candidate proof step. On the neural side, we fine-tune LLMs using datasets of proof state–step pairs; on the symbolic side, we incorporate a range of ITP tools to repair rejected steps, filter and rank proof states, and automatically discharge subgoals when search progress stalls. This synergy enables data-efficient LLM adaptation and semantics-informed pruning of the search space. We implement the framework on a new Isabelle REPL that exposes fine-grained proof states and automation tools, and evaluate it on the FVEL seL4 benchmark and additional Isabelle developments. On seL4, the system proves up to 77.6% of the theorems, substantially surpassing previous LLM-based approaches and standalone Sledgehammer, while solving significantly more multi-step proofs. Results across further benchmarks demonstrate strong generalization, indicating a viable path toward scalable automated software verification. 1 1 footnotetext: These authors contributed equally to this work. 2 2 footnotetext: Corresponding authors. 1 Introduction Formal verification plays a vital role in ensuring the correctness and reliability of software systems, especially in safety- and security-critical domains where failures can be catastrophic ( Clarke1996 ; Blanchet2003 ; Woodcock2009 ) . Interactive theorem proving (ITP) stands out for its expressiveness and ability to provide the strongest assurance. With ITPs, landmark projects such as CompCert (a formally verified optimizing C compiler whose correctness is mechanically proven in Rocq leroy2016compcert ) and seL4 (formally verified OS microkernel whose functional correctness, security properties and reliability guarantees are proven in Isabelle/HOL klein2014comprehensive ) have been successfully delivered, which demonstrate that formally verified systems can achieve both practical usability and rigorous correctness. While ITP offers unparalleled assurance, it also incurs substantial costs, preventing its wide adoption, especially in large-scale, systems-level software ( ringer2019qed ) . Specifically, a typical software verification workflow involves 1) writing precise formal specifications to be proved and 2) constructing rigorous proofs for these specifications, both of which demand immense human effort. For example, the seL4 verification project required approximately 20 person-years of work, and produced over 100K lines of proof scripts, compared to only about 10K lines of C implementation and merely 3K lines in its simplest abstract specification in Isabelle klein2014comprehensive . Moreover, developing such specifications and proofs necessitates specialized expertise in both theorem proving and the target domain, a combination that is challenging to acquire. In this work, we focus on the proof generation step in systems-level software verification projects. Recently, large language models (LLMs) have demonstrated encouraging mathematical reasoning capabilities, which inspire research into their application for software verification, particularly for proof generation qin2025can ; thompson2024rango ; zhang2024selene ; lin2024fvel . Unfortunately, both prior studies and our initial experiments show that, even when theorem statements are well formalized and relevant libraries are fully provided in advance, current LLMs still struggle to generate complete, correct proofs. We summarize two challenges as follows. ❶ Lack of specialized expertise . The first challenge lies in that software verification often relies on numerous domain-specific lemmas and specialized proof tactics. Although modern LLMs perform well in general reasoning tasks, they are not well-versed in these specialized domains, leading to limited effectiveness when applied to proving corresponding theorems. For example, LLM4FSCQ qin2025can evaluated models such as GPT-4o and Gemini 1.5 Flash on FSCQ (a Rocq-based file system verification project fscq ) and achieved only 38% proof coverage. Moreover, in the larger seL4 project, which involves extensive lemma libraries and customized tactics, Selene zhang2024selene found that GPT-4 succeeded on only 20% of a benchmark theorem set, despite the fact that nearly 40% of them require one-line proofs. ❷ Pausity of usable data . The second challenge, which is closely related to the first, is the shortage of high-quality (training) data for software verification. For instance, the seL4 project contains only around 20K theorems and lemmas, and most proofs are written in a procedural style, where much of the reasoning is implicit and encoded in the interaction with the theorem prover. This substantially limits their usefulness in effective LLM training/fine-tuning. Indeed, FVEL lin2024fvel , which systematically extracted theorems from seL4 to fine-tune Mistral-7B-Instruct jiang2023mistral and Llama-3-8B-Instruct dubey2024llama models, reported a success rate below 10% (88 out of 1,077 theorems in the test set). 1 1 1 Selene only extracts a small subset of the seL4 project, and its collected theorems are relatively easy, with proof lengths ranging from one to five. In contrast, the FVEL benchmark is more comprehensive and challenging, as it extracts all the theorems to be proved from seL4. Approach. In this paper, we propose a proof generation framework that synergistically combines LLMs and ITPs, aiming for automated systems-level software verification. Our approach adopts a proof step-based tree-search pipeline that iteratively queries a fine-tuned LLM to predict the next proof step until the target theorem is successfully proved. To address the first challenge, our framework adopts a neuro-symbolic approach tailored to the nature of software verification. First, to address challenges posed by domain-specific lemmas and tactics, we incorporate a proof-step revision module that repairs or refines LLM-generated steps whenever they fail to compile or make no progress. Second, to efficiently prune unpromising branches, we utilize Nitpick ( blanchette2010nitpick ) and QuickCheck ( claessen2000quickcheck ) to “test” each candidate proof state and discard those that admit counterexamples; the remaining candidates are then ranked by the LLM according to their plausibility. Finally, if the tree search still fails to resolve the goal, Sledgehammer ( bohme2010sledgehammer ) acts as a backstop that scans the local library for potentially relevant lemmas and attempts to complete the current proof. To address the second challenge, our tree-search pipeline facilitates direct interaction between the LLM and the theorem prover, by extracting the prover’s internal proof state to LLM, which can inform and guide subsequent step predictions. This pipeline also enables “bootstrapping” training data generation. Namely, during the tree-search process, training data for proof-step prediction can be extracted on-the-fly. For example, if a theorem’s proof consists of five steps, a successful tree search could yield five training instances, which can later be used for, e.g., fine-tuning ( wu2024internlm2 ; xin2025bfs ) . Experiments. We evaluate our framework on seL4 klein2014comprehensive proof construction. The results show that, with a fine-tuned language model, our approach achieves a total proof success rate of up to 77.6%, significantly surpassing prior automated proof-generation approaches for seL4. Noteably, it excels, compared to the two preceding systems, at successfully handling a larger number of multi-step proofs, a challenge that has not been addressed by prior work. Moreover, our framework substantially alleviates manual proof-engineering effort, reducing expert proof-writing effort by 71.1% on average in an AI–human collaboration setting.

Read the complete text