Adaptive Proof Refinement with LLM-Guided Strategy Selection

Minghai Lu, Zhe Zhou, Danning Xie, Songlin Jia, Benjamin Delaware, Tianyi Zhang · 2025

Read Adaptive Proof Refinement with LLM-Guided Strategy Selection by Minghai Lu, Zhe Zhou, Danning Xie, Songlin Jia, Benjamin Delaware, Tianyi Zhang (2025) 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-2510-25103.txt.

Introduction

Minghai Lu, Zhe Zhou, Danning Xie, Songlin Jia, Benjamin Delaware, and Tianyi Zhang build Adapt, a frame that fixes failed math proofs by pick of the right fix plan for each flaw. Proof tools give strong checks of code truth, but proofs take much hand work. Chat models can draft proofs, yet first drafts are most oft wrong, and one fixed fix path fits all drafts poor.

Adapt lets a chat model read the proof tool's state and the wrong draft, then pick which fix plan to run. On two bench sets, it proved far more claims than the best past ways. The gain came from match of plan to flaw, not more brute tries.

Catalog record

CREATORMinghai Lu, Zhe Zhou, Danning Xie, Songlin Jia, Benjamin Delaware, Tianyi Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-25103

Browse the full library · About the Tower of Babel

Full text

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

Adaptive Proof Refinement with LLM-Guided Strategy Selection Minghai Lu, Zhe Zhou, Danning Xie, Songlin Jia, Benjamin Delaware, Tianyi Zhang 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. \acmCodeLink https://github.com/borisveytsman/acmart \acmDataLink htps://zenodo.org/link 1. Introduction Interactive theorem provers (ITPs) such as Coq ( The Coq Development Team 2024 ) and Lean ( de Moura et al. 2015 ) are powerful tools for formally verifying complex software systems. They have been successfully applied in critical domains, including certified compilers ( Kästner et al. 2018 ) , distributed systems ( Wilcox et al. 2015 ) , and OS kernels ( Klein et al. 2009 ) . However, these successes require significant human effort and expertise, as developers must interactively guide the proof assistant step-by-step. For example, CompCert, a verified C compiler, required 6 person-years and 100,000 lines of proof scripts ( Kästner et al. 2018 ) . Recently, there has been increasing interest in leveraging Large Language Models (LLMs) to automatically generate formal proofs ( Thompson et al. 2024 ; First et al. 2023 ; Yang et al. 2024 ; Wang et al. 2023 ; Cao et al. 2025 ; Liu et al. 2025 ) . While LLMs have demonstrated promising performance on some theorem proving benchmarks, they are far from perfect: even the best-performing tool can prove only 40.4% of theorems in the widely used CoqGym benchmark ( Lu et al. 2024 ) . Generating a correct proof in a single attempt is difficult. In practice, human developers rely on feedback from the ITP to refine their initial proofs. Similarly, many automated approaches adopt an iterative proof refinement mechanism that leverages feedback from the ITP to continuously refine an initial proof attempt ( Lu et al. 2024 ; First et al. 2023 ; Wang et al. 2023 ; Liu et al. 2025 ; An et al. 2024 ) . However, these methods typically adopt a single, fixed refinement strategy to handle all types of errors, such as proposing a helper lemma ( Wang et al. 2023 ) or calling an external tool ( Lu et al. 2024 ; Liu et al. 2025 ) . This one-size-fits-all approach is suboptimal because correcting erroneous proofs often requires different refinement strategies depending on the specific type of error, and complex errors may even necessitate a combination of multiple strategies. Consequently, even the state-of-the-art iterative refinement method can only prove 32.0% of theorems in the CoqStoq benchmark ( Thompson et al. 2024 ) . In contrast, a key factor in the success of human developers in theorem proving is their ability to select the most appropriate refinement strategy for a given proof state ( Shi et al. 2025 ) . While interactively developing a proof, developers adopt various strategies based on the current state of the proof assistant and available context (e.g., proven theorems and lemmas) ( Shi et al. 2025 ; Mehta 2008 ) . For example, they might introduce new helper lemmas when existing ones are insufficient, draw inspiration from similar proofs and reuse relevant lemmas, or iteratively repair proofs based on ITP feedback. This strategic decision-making is critical, as a suboptimal choice can increase effort or lead to outright proof failure. Figure 1 . Overview of Adapt . Inspired by this observation, we propose Adapt , an adaptive proof refinement framework. In contrast to prior work that employs a single, fixed refinement strategy, Adapt dynamically selects an appropriate strategy based on the current state of the proof assistant and available context. As illustrated in Figure 1 , when a proof attempt fails, an LLM-based decision-maker employs one of three strategies: (1) proposing new helper lemmas, (2) searching for relevant lemmas and proofs to guide the refinement, or (3) regenerating the proof. This iterative process allows Adapt to flexibly adapt its approach at each step, enabling it to effectively prove complex theorems. Our evaluation of Adapt against two state-of-the-art methods, PALM ( Lu et al. 2024 ) and Rango ( Thompson et al. 2024 ) , and two alternative refinement designs demonstrates its effectiveness. On the CoqStoq benchmark ( Thompson et al. 2024 ) , Adapt proves 41.33% of 1,171 theorems, outperforming the strongest baseline by 16.63%. This lead increases to 18.58% on our new, more challenging benchmark of 1,720 theorems. Further experiments confirm the generalizability of Adapt across five LLMs and, through ablation studies, validate the contribution of its refinement strategies and the decision-maker. In summary, we make the following contributions: (1) We propose Adapt , an LLM-based proof refinement framework that adaptively selects from different strategies based on the state of the proof assistant and available context. (2) We construct CoqDev , a new benchmark mined from real-world Coq commit histories that models the incremental development process. (3) We conduct a comprehensive evaluation of Adapt on both CoqDev and the existing CoqStoq benchmark, demonstrating that Adapt achieves significant improvements over state-of-the-art techniques. 2. Background and Motivation ⬇ 1 (* Definitions *) 2 Inductive nat : Set := 3 | O : nat 4 | S : nat -> nat . 5 Notation " n + 1" := ( S n ). 6 7 Fixpoint leb ( n m : nat ) : bool := 8 match n , m with 9 | O , _ => true 10 | _ , O => false 11 | n + 1, m + 1 => leb n m 12 end . 13 14 Inductive le : nat -> nat -> Prop := 15 | le_n ( n : nat ) : le n n 16 | le_S ( n m : nat ) ( H : le n m ) : le n ( S m ). 17 Notation " n <= m " := ( le n m ). 18 19 (* Theorems *) 20 Lemma O_le_n : forall n , O <= n . 21 Proof . 22 intros n . induction n . 23 - apply le_n . 24 - apply ( le_S O n IHn ). 25 Qed . 26 27 Lemma n_le_m_Sn_le_Sm : 28 n <= m -> ( n + 1) <= ( m + 1). 29 Proof . (*

Read the complete text