Exploiting Instantiations from Paramodulation Proofs in Isabelle/HOL
Lukas Bartl (🖂), Jasmin Blanchette, Tobias Nipkow · 2025
Read Exploiting Instantiations from Paramodulation Proofs in Isabelle/HOL by Lukas Bartl (🖂), Jasmin Blanchette, Tobias Nipkow (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-2508-20738.txt.
Introduction
Lukas Bartl, Jasmin Blanchette, and Tobias Nipkow present, in a 2025 paper, a tool that mines theorem-proving runs for reusable hints. Inside the Isabelle proof assistant, a prover called Metis closes goals from a list of lemmas, usually gathered by the Sledgehammer tool from outside provers. When Metis succeeds, the exact choices it made for variables are often thrown away.
Their tool reads a successful Metis proof and extracts those choices. Feeding them back raises Sledgehammer's success rate and speeds up the proofs it builds. The hints also help users see why a goal follows from the lemmas at hand. The work shows that a finished proof holds more value than its yes-or-no verdict.
Catalog record
| CREATOR | Lukas Bartl (🖂), Jasmin Blanchette, Tobias Nipkow |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20738
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exploiting Instantiations from Paramodulation Proofs in Isabelle/HOL Lukas Bartl (🖂), Jasmin Blanchette, Tobias Nipkow Abstract Metis is an ordered paramodulation prover built into the Isabelle/HOL proof assistant. It attempts to close the current goal using a given list of lemmas. Typically these lemmas are found by Sledgehammer, a tool that integrates external automatic provers. We present a new tool that analyzes successful Metis proofs to derive variable instantiations. These increase Sledgehammer’s success rate, improve the speed of Sledgehammer-generated proofs, and help users understand why a goal follows from the lemmas. 1 Introduction Sledgehammer [ 31 ] is undoubtedly one of the interactive proof assistant Isabelle/HOL’s [ 27 ] most popular components. This component gives Isabelle access to many external automatic theorem provers (ATPs), which can mechanize routine proofs [ 12 , 16 ] . When the user invokes Sledgehammer on a proposition to be proved, it performs the following steps: 1. It invokes a number of external ATPs with the goal and the background library of facts (definitions, lemmas, theorems, etc.); this involves translating the goal and facts from higher-order logic to the ATPs’ logics. 2. For any proof that is found, the used facts are extracted from it and the internal prover Metis [ 20 ] , based on ordered paramodulation, is invoked to reconstruct an Isabelle proof based on this list of facts only. This paper is about obtaining and exploiting the instantiations of the facts used in the proofs. Our motivation is that using instantiated facts – can speed up proof reconstruction (and even turn timeouts into successes); – can improve readability of proofs for humans; and – can lead to simpler proofs. Example 1 We start with a simple example where we believe human readability is improved. We work in a linear order with \bot and \top . Sledgehammer proves that in the context of the facts \top\nless x\kern 5.0pt(1)\hskip 20.00003ptx\neq\bot\leftrightarrow\bot<x\kern 5.0pt(2) the assumption \bot\nless\top implies \mathtt{a}=\mathtt{b} , where \mathtt{a} and \mathtt{b} are arbitrary constants. Why is that? It turns out that the following instantiations are used: \displaystyle\top\nless\mathtt{a}\kern 5.0pt(1\mathtt{a})\hskip 20.00003pt\top\nless\mathtt{b}\kern 5.0pt(1\mathtt{b}) \displaystyle\mathtt{a}\neq\bot\leftrightarrow\bot<\mathtt{a}\kern 5.0pt(2\mathtt{a})\hskip 20.00003pt\mathtt{b}\neq\bot\leftrightarrow\bot<\mathtt{b}\kern 5.0pt(2\mathtt{b})\hskip 20.00003pt\top\neq\bot\leftrightarrow\bot<\top\kern 5.0pt(2\top) Clearly \bot\nless\top implies \bot=\top via (2\top) . This implies \bot\nless\mathtt{a} and \bot\nless\mathtt{b} via (1\mathtt{a}) and (1\mathtt{b}) . Now we obtain \mathtt{a}=\bot and \mathtt{b}=\bot via (2\mathtt{a}) and (2\mathtt{b}) , and thus \mathtt{a}=\mathtt{b} . Although this deduction still needs some thought, we believe that it is far simpler than if we had to work out the derivation from (1) and (2) alone. This paper is structured as follows. Section 2 presents the necessary background about Isabelle, Sledgehammer, and Metis. Section 3 presents further introductory examples. The core of the paper is in Section 4 , which explains how to obtain the instantiations used during a Metis proof and translate them into instantiations of the corresponding Isabelle facts. Section 5 explains how Sledgehammer was extended to cooperate with the extended Metis prover. Section 6 presents our empirical evaluation of how instantiations improve the performance of Sledgehammer. We end with related work and the conclusion. Our extensions are available as part of Isabelle starting with version 2025. 1 1 1 https://isabelle.in.tum.de/website-Isabelle2025/ They are documented in the Sledgehammer user’s manual [ 5 ] . The raw data for our evaluation is available online. 2 2 2 https://nekoka-project.github.io/pubs/instantiations˙data.zip 2 Background Isabelle. Isabelle/HOL [ 41 , 27 ] is a proof assistant for polymorphic higher-order logic enriched with type classes [ 34 ] . It is written primarily in Standard ML. It has an inference kernel through which all logical inferences must go to be deemed acceptable. At the user level, notations largely follow mathematical practice. Sledgehammer. The Sledgehammer tool [ 31 ] consists of six main components: 1. The relevance filter (or “premise selector”) heuristically selects a subset of the available facts as likely relevant to the current goal. Typically, hundreds of facts can be chosen without overwhelming ATPs. Sledgehammer includes two relevance filters [ 23 , 8 ] , which can be combined. 2. The translation module constructs an ATP problem from the selected facts and the current goal, translating Isabelle’s polymorphic higher-order logic to the ATP’s logic [ 22 , 7 ] . 3. The ATP tries to prove the problem. Actually, multiple ATPs can be run in parallel. Commonly used ATPs include cvc5 [ 3 ] , E [ 39 ] , Leo-III [ 35 ] , SPASS [ 10 ] , Vampire [ 4 ] , veriT [ 13 ] , Z3 [ 25 ] , and Zipperposition [ 38 ] . 4. If one or more ATPs find a proof, the proof minimization module repeatedly invokes each ATP with subsets of the facts referenced in the respective proof, trying to reduce the number of dependencies and speed up the next steps. 5. The proof reconstruction module transforms each ATP proof into a textual Isabelle proof. Reconstruction means that Sledgehammer and the ATP need not be trusted. Typically, the structure of the ATP proof is discarded, and the Isabelle proof consists of a single proof method (often metis ) invoked with the facts referenced in the ATP proof. Detailed Isabelle proofs, or Isar proofs [ 40 ] , are available as an experimental feature [ 6 ] . 6. For each ATP proof, the preplay module tries out various proof methods before they are presented to the user. If several methods succeed, the fastest one is chosen [ 6 ] . As an example, suppose Sledgehammer selects 512 facts f_{1},\dots,f_{512} and passes them, along with the goal, to E. Then E finds a proof involving three facts, f_{10} , f_{73} , and f_{359} , and minimization reduces this list to two: f_{10} and f_{359} . By trial and error (and preplaying), Sledgehammer determines that the proof method metis with f_{10} and f_{359} as arguments solves the Isabelle goal in 23 ms, and no other proof method succeeds, so this metis call is suggested to the user. The Metis ATP. Metis [ 20 ] is an ATP for untyped first-order logic with equality written in Standard ML. It is based on ordered paramodulation, a variant of superposition [ 2 ] . Although Metis was developed as a standalone program, it is also incorporated in Isabelle’s source code, so that it is always available. Thanks to its calculus, Metis is reasonably performant, although it cannot compete with state-of-the-art superposition provers such as Vampire [ 36 ] . Metis’s main strengths are the readability of its source code and the simplicity and fine granularity of its proof format. Proofs are expressed using the following six inference rules: Axiom C Assume A\lor\lnot A Subst C C\sigma Refl t=t Equality s\neq t\lor\lnot L[s]_{p}\lor L[t]_{p} Resolve C\lor A \lnot A\lor D C\lor D Notice that substitution is captured by the explicit Subst rule instead of being part of Resolve . Moreover, all equality reasoning is reduced to Refl and Equality . For proof search, Metis relies on a more efficient calculus that performs ordered paramodulation, but the proofs are then translated to the above fine-granular rules. The metis Proof Method. Isabelle’s metis (with a lowercase m) proof method [ 32 ] builds on the Metis (with an uppercase M) ATP to provide general-purpose proof automation. The metis