Abstract
Formal verification via theorem proving enables the expressive specification and rigorous proof of software correctness, but it is difficult to scale due to the significant manual effort and expertise required. While Large Language Models (LLMs) show potential in proof generation, they frequently produce incorrect proofs on the first attempt and require additional strategies for iterative refinement. However, existing approaches employ fixed refinement strategies and cannot dynamically choose an effective strategy based on the particular issues in a generated proof, which limits their performance. To overcome this limitation, we introduce Adapt, a novel proof refinement framework that leverages an LLM-guided decision-maker to dynamically select a suitable refinement strategy according to the state of the proof assistant and available context of an incorrect proof. We evaluate Adapt on two benchmarks against four existing methods and find that it significantly outperforms the best baseline on both by proving 16.63% and 18.58% more theorems, respectively. Furthermore, we demonstrate Adapt's generalizability by evaluating it across five different LLMs. We also conduct ablation studies to measure the contribution of each component and compare the trade-offs of alternative decision-maker designs.
Introduction
Formal verification represents the "gold standard" of software reliability, employing mathematical proofs to ensure code is bug-free. However, authoring these proofs in languages like Coq or Lean is notoriously difficult and time-consuming, often requiring years of specialized expertise. While Large Language Models (LLMs) have shown promise in generating these proofs automatically, they rarely achieve success on the first attempt.
Current "iterative refinement" tools attempt to fix errors but are often constrained by rigid, "one-size-fits-all" strategies. For instance, they might always search for more context regardless of whether the failure is a simple syntax error or a deep logical gap. This lack of flexibility limits their effectiveness on complex theorems. To address this, we present Adapt, a framework that mimics human experts by dynamically selecting the most appropriate refinement strategy based on the specific failure context.
The Adapt Framework
Adapt treats proof refinement as a strategic decision-making process. The workflow follows an iterative loop designed to overcome the limitations of static refinement methods.
The process begins with an initial proof attempt generated using Retrieval-Augmented Generation (RAG). If the proof assistant (e.g., Coq) rejects the proof, Adapt captures the "stuck state," including the error message, the partial proof that was accepted, and the current goals.
An LLM-based decision-maker then analyzes this feedback to select one of three specialized strategies:
- Lemma Discovery: If the goal is too complex, Adapt proposes and attempts to prove a new "helper lemma" to bridge the logical gap.
- Context Enrichment: If the model lacks necessary information, it generates keywords to search the project for relevant definitions or theorems.
- Regeneration: If the proof is fundamentally flawed or contains minor syntax errors, Adapt attempts to rewrite or repair the script from scratch.
This decoupling of lemma discovery—where the statement is generated and proven separately—prevents the model from becoming overwhelmed by a single, massive failing script.
Experimental Setup and Benchmarks
We evaluated Adapt on two primary benchmarks:
- CoqStoq: A standard benchmark featuring 1,171 theorems from real-world Coq projects.
- CoqDev: A new benchmark introduced in this work to better simulate real-world development. It contains 1,720 theorems mined from GitHub. Crucially, CoqDev masks helper lemmas written alongside the target theorem, forcing the LLM to actually "discover" them rather than retrieving them from the immediate context.
Results and Analysis
Adapt demonstrates significant performance gains over state-of-the-art (SOTA) baselines such as PALM and Rango.
On the CoqStoq benchmark, Adapt proved 41.33% of theorems, representing a 16.63% improvement over the best baseline. On the more challenging CoqDev benchmark, it proved 37.85%, outperforming baselines by 18.58%.
Analysis of the strategy selection reveals that "Lemma Discovery" is particularly critical for difficult proofs, while "Regeneration" is often preferred for simpler fixes. Interestingly, the LLM decision-maker significantly outperformed hard-coded rules and traditional machine learning models, suggesting that high-level semantic reasoning is essential for understanding why a proof failed and choosing the right corrective action.
Conclusion and Future Work
Adapt provides a robust, model-agnostic framework for formal verification, showing strong results across various LLMs including GPT-4o, Claude 3.7, and DeepSeek-V3. However, challenges remain regarding the quality of proposed lemmas—which can occasionally be trivial or unprovable—and the increased token cost associated with strategic decision-making. Future work will focus on expanding Adapt to other proof assistants like Lean and Isabelle, and integrating symbolic methods to further refine the quality of generated helper lemmas.
Summary updated