Draft, Sketch, and Prove: Guiding Formal Theorem Provers with Informal Proofs
Authors: Albert Qiaochu Jiang
Sean Welleck
Jin Peng Zhou
Timothee Lacroix
Jiacheng Liu
Wenda Li
Mateja Jamnik
Guillaume Lample
Yuhuai Wu
Venue: ICLR 2023 notable top 5% (2023)

Abstract: The formalization of existing mathematical proofs is a notoriously difficult process. Despite decades of research on automation and proof assistants, writing formal proofs remains arduous and only accessible to a few experts. While previous studies to automate formalization focused on powerful search algorithms, no attempts were made to take advantage of available informal proofs. In this work, we introduce Draft, Sketch, and Prove (DSP), a method that maps informal proofs to formal proof sketches, and uses the sketches to guide an automated prover by directing its search to easier sub-problems. We investigate two relevant setups where informal proofs are either written by humans or generated by a language model. Our experiments and ablation studies show that large language models are able to produce well-structured formal sketches that follow the same reasoning steps as the informal proofs. Guiding an automated prover with these sketches enhances its performance from $20.9\%$ to $39.3\%$ on a collection of mathematical competition problems.

Published as a conference paper at ICLR 2023
DRAFT, SKETCH, AND PROVE: GUIDING FORMAL THEOREM PROVERS WITH INFORMAL PROOFS
Albert Q. Diaingg 122tt
Sean Welleck
Jin Peng Zhou
Wenda Li²
Jiacheng Liu
Mateja Jamnik?
Timothée Lacroix
Guillaume Lample'
Yuhuai Wu7.
Meta AI University of Cambridge
University of Washington Stanford University
4 Allen Institute for Al
Google Research "Conell University
ABSTRACT
The formalization of existing mathematical proofs is a notoriously difficult process. Despite decades of research automation and proof assistants, writing formal proofs remains arduous and only accessible to a few experts. While previous studies to automate formalization focused powerful search algorithms, no attempts were made to take advantage of available informal proofs. In this work, we introduce Draft. Sketch, and Prove (DSP), method that maps informal proof's to formal proof sketches, and uses the sketches to guide an automated prover by directing its search easier sub-prot bob-problems. We investigate two relevant setups where informal proofs are either written by humans or generated by language model. Our experiments and ablation studies show that large language models are able produce well- structured formal sketches that follow the same reasoning steps as the informal proofs. Guiding an automated prover with these sketches enhances its performance from 20.9% to 39.3% on collection of mathematical competition problems.
Formal sketch
Verified formal proof
Statement
Informal proof
using "1-28
gedlj, and
We know that godio. b) lemba 8) ab hence 1-25
using
Ieminn. 4) 28, show that n is
ithen have c2: 1*20/6" <preads
Chen have 02) "n 1+28/4"
comoleting proof.
then show ithesia
ichen show Pchesis
Informal Proof Writer
Autoformalizer
Off-cho-hallf Prover
Draft informal proof
Generate formal sketch
Prove remaining gaps
Figure I: Draft, Sketch, and Prove. Starting with an informal statement, our framework yields formal proof through three-stage process: drafting informal proof's, mapping them into formal sketches. and proving the remaining conjectures. Concretely, an informal statement a mathematical problem described in a mixture natural and mathematical languages (c.g., formulae иАΕ{)). Then, we use a large language model to autoformalize each informal proof into formal sketch, which is a skeleton of the formal proof with open conjectures left unproven (indicated by the <proof> blocks). The formal sketch mirrors the structure of the informal proof. Finally, the open conjectures/gaps inside each formal sketch proved by an off-the-shelf prover.
Equal contributions as leading authors. Correspondence to: gj213@cam, ac, uk.
1 Equal contributions senior authors.

---

Published as a conference paper at ICLR 2023
INTRODUCTION
Formal proof automation is challenging task that has been the focus of increased attention in recent
years (Bansal et al.) [019b] Polu & Sutskever] 2020] Lample et al. 2022 Jiang et al.] 2022 Wu al. 2022). However, deep learning approaches have not been as successful as in other domains, mainly because of the scareity of formal data. Indeed, formalizing proofs is notoriously difficult and only accessible to handful of experts, which makes large annotation endeavors unrealistic (Wiedijk 2008). The largest formal proof corpus is written in Isabelle (Paulson 1994). and amounts to less than 0.6 GB in size, orders of magnitude smaller than datasets commonly used in vision (Deng et al.) 2009) or natural language processing (Brown et al. 2020). To address the scarcity of formal proots. previous studies have proposed to use synthetic data (Wu et al. (02Tb), self- self-supervision (Polu & Sutskever 2020; Han et al., 2022), or reinforcement learning (Bansal al., [2019a] Polu al., 2022)) to synthesize additional formal training data, Although these methods alleviate the data insufficiency to some degree, none able to capitalize the bulk of human-written mathematical proofs.
Unlike formal mathematics, informal mathematical data is abundant and widely available. Recently, large language models trained on informal mathematical data showcased impressive quantitative reasoning abilities (Lewkowycz et al.] 2022 Welleck et al. 2022). However, they often generate erroneous proofs and it is challenging to detect the faulty reasoning in these proofs automatically. Our work devises a novel approach called Draft, Sketch, and Prove (DSP) to translate informal mathemat- ical proofs into formal ones and thus enjoy both the logical rigor provided by formal systems and the wealth of informal data. We give a schematic diagram of the DSP method in Figure I] and describe it in Section 3 Recent work (Wu et al.) 2022) demonstrates the feasibility of automatically translating informal statements into formal ones with large language models. DSP goes beyond and leverages large language models to generate formal proof sketches (Wiedijk 2003) from informal proofs. Proof sketches consist of high-level reasoning steps that can be interpreted by formal systems such as interactive theorem provers. They differ from complete formal proofs in that they contain sequences of intermediate conjectures without justification. An example of informal proof with its corresponding formal proof sketch is provided in Figure 2 In the last step of DSP, we elaborate the formal proof sketch into a full formal proof using an automated prover to prove all intermediate conjectures.
We perform experiments to generate formal proofs of problems from the miniF2F dataset (Zheng eet al., (022) and show that large portion of theorems can be proved automatically with this method. We investigate two settings where the informal proofs are either written by humans or drafted by large language model trained mathematical text. These two settings correspond to situations frequently occurring during the formalization of existing theories, where informal proofs are usually available, but sometimes left as exercises to the reader or missing due to space limits in the margin.
Contributions:
We introduce a novel approach to leverage informal proofs to guide automated provers with formal proof sketches.
To evaluate our approach, we build a dataset of manually curated informal statements and informal proofs aligned with formal statements in the miniF2F dataset (Zheng et al. (022).
We increase the proportion of problems solved by an automated prover on miniF2F from 20.9% to 38. 99. given language- language-model- model -generated informal proofs, and up to 39.3% when proofs are written by humans.
Through three ablation studies, we demonstrate the performance benefit of drafting informal proofs, annotating sketches with informal segments, and using automated provers to close open conjectures for the autoformalization of proofs.
2 BACKGROUND AND RELATED WORK
Interactive theorem proving Modern verification systems for matherattics are centered around interactive theorem provers (ITPs), such as Isabelle (Paulson 1994). Lean (Moura et al. 20155) Coq (Barras et al. 1997). or Metamath (Megill & Wheeler 2019). ITPs embed the mathematical definitions and theorems onto a solid logical foundation (e.g.. Higher-Ordee Logic. Dependent Type Theory) implemented by their kernels. Every theorem must be checked by the kernel to be recognized by the ITP. To be proved formally, theorem is first stated in the ITP's programming language, and
2

---

Published as a conference paper at ICLR 2023
iteratively simplified into simpler objectives (or subgoals), until it can be reduced to already proven facts. In this paper, we will refer to proofs verified by a formal theorem prover as formal proofs, and proof's written in "standard" mathematics (e.g. in [TTXX) as informal proofs.
Machine learning for formal proof synthesis Several approaches propose to combine machine
learning with modern interactive theorem provers (Yang & Deng 2019
Gauthier et al. (021), )), and
build upon the recent success of language models (Polu & Sutskever 2020 Han et al. [022 Polu et al.
2022,
Diang et al., 2022 Lample al., 2022). These methods typically rely on seateenncet--seqeeee
models (Sutskever et al.
2014) to generate the next step of proof given the current proof state and
perform search over the generated subgoals using powerful search methods such as MCTS (Silver
al. 2018 Wu et al. 2021a Laurent & Platzer 2022). Because search is computationally expensive,
these language models are relatively small (with fewer than billion parameters). Our method contrasts with these approaches in that we use a significantly reduced number of calls to the models, but also much larger language models (with up to 175 billion parameters) that showcase outstanding
few-shot learning abilities (Brown al. 2020).
Machine learning for informal reasoning Language models have also been used in the context of purely informal mathematics (Lample & Charton 2020 Hendrycks et al., 2021 Welleck et al.)
|rori et al., 2022] Welleck et al.) 2022). Nevertheless, Lewkowycz et al. (2022) note that for quantitative question answering, models are prone to generate false positives: the model guesses the right answer while providing an incorrect proof. These errors are hard to spot without human inspection. Worryingly, the frequency of false positives increases with the difficulty of the problem. Our method builds on these findings and translates informal proofs into formal proofs. Since ITPs are logically grounded, once formal proof is checked by them, we are guaranteed its correctness.
Autoformalization In a position paper, Szegedy (2020) argued for attaining formal mathematical data from informal sources with neural networks. Wang et al. (2020) performed preliminary experi- ments where the evaluation was limited to text-level similarities on synthetic datasets. Recently, Wu et al. (2022) found that large language models (Chen et al., 2021 Chowdhery et al.) (222)) are capable of few-shot statement autoformalization. Namely, a small number of examples are enough for them
to learn to perform informal-to- to-fomaal translation of statements. In this paper, we investigate whether these findings can generalize to proof autoformalization, i.c., whether large language models can be used to translate informal proofs into formal ones.
3 METHOD
In this section, we describe our Draft, Sketch, and Prove (DSP) method for formal proof automation, which leverages informal proofs to guide automated formal theorem provers with proof sketches. We assume that each problem comes with an informal statement and a formal statement describing the problem. Our pipeline consists of three stages (depicted in |Figure 1), which we present below.
3.1 DRAFTING INFORMAL PROOFS
The initial phase of the DSP method consists in finding informal proofs for a problem according to its description in natural mathematical language (possibly with (TīІX). The resulting informal proof is seen as draft for the subsequent phases. In mathematical textbooks, proofs of theorems are in general provided, but are sometimes missing or incomplete. Therefore, we consider two settings corresponding to the presence or absence of the informal proofs. In the first, we assume that a "ground-trute truth" informal proof (i.e., one written by a human) is available. which is the typical scenario in the practice of formalizing existing mathematical theories. In the second setting, we make a more general assumption that the ground-truth informal proof is not given, and draft proof candidates with a large language model trained on informal mathematical data. The language model removes the dependence on human proofs and can produce multiple alternative solutions for every problem. Although there is no easy way to automatically verify the correctness of these proofs, the informal proof only needs to be useful for producing a sketch in the next stage.
3.2 MAPPING INFORMAL PROOFS INTO FORMAL. SKETCHES
formal proof sketch encodes the structure a solution and leaves out low-level details (Wiedijk 2003). Intuitively, it is partial proof that outlines high-level conjecture statements. A concrete example of a proof sketch is shown in Figure 2 Although informal proofs often leave aside low-level details, (e.g., by stating their triviality). these details cannot be discharged in formal proof, making
3

---

Published as a conference paper at ICLR 2023
Informal Statement: Show that for any real number 10a I 28a" + 1.
Informal Proof:
suffices to show 0 28a² 10a + 1. First, consider completing the square for 28a² 10a and
observe that (a 25 a² (5/28) Since S (a 1 we get S a² 10 (5/ (5/28)².
Multiplying by 28 and simplifying gives < 28a" 10a (25/28). Since 25/28 1, the result follows.
Formal Proof Sketch:
theorem algebra, bincmnegdiscrineg 10alt28asqp1:
fixes real
shows "10 Σ 28 a 1"
proof (* it suffices to show 0 <= 28a - 10a + *)
have <0: "0 < 2 - 10a + 1"
proof (* observe that (a (5/28)) 2 a'2 (10/28) + (5/28)
have
(5/28)) a"2 10/28a (5/28) "2" <..>>
(* we get have c2: "0 S a"2 - 10/28a + (5/28) "2" using cl < <..>>
a'2 (10/28)a (5/28) 2 *)
(* Multiplying by 28 and simplifying gives 0 <= 28a 10a + (25/28) *)
have c3: "0 I 28a"2 10a 28 (5/28) "2)" using c2 ...
have c4: "0 < 28a"2 13a 28 ( (5/28)) using c3
have c5: "0 S 28a"2 "2 10a (25/28) using o4 < ...>>
(* Since 25/28 < 1, the result follows. *)
show 7thesis using c5 ..
ged
show ?thesis >.>
qed
A proof sketch in Isabelle. The problem "Show that for any real number a, 10a S 28a² + 1" given with an informal proof an associated formal proof sketch. The sketch rewrites original statement (c0), which is proved through 5 intermediary conjectures (cl..c5). We use a special token ...... >) to indicate that the conjecture is "open" and should be tackled by automated prover later. To facilitate the alignment between the informal and formal languages, annotate the formal proof sketch examples with informal proof segments (shown in red), which are immediately followed by their formal counterparts.
Figure 2:
straightforward informal-to-fee formal proof translation difficult. Instead, we propose map informal proofs to formal proof sketches that share the same high-level structures. The low-level details missing from a proof sketch can later be filled by an automated prover. Since large informal-formal parallel corpora do not exist, standard machine translation methods are unsuitable for this task. Rather, we use the few-shot learning abilities of a large language model. Specifically, we prompt the model with few example pairs containing informal proofs and their corresponding formal sketches, followed by an informal proof yet to translated. We then let the model generate the subsequent tokens to obtain the desired formal sketch. We refer to this model as autoformalizer.
3.3 PROVING OPEN CONJECTURES IN THE SKETCHES
As the last part of the process, execute off-the-shelf automated provers fill in the missing details in proof sketches, where "automated provers" refers to systems capable of producing formally verifiable proofs. Our framework is agnostic to the specific choice of the automated prover: can be symbolic provers such as heuristic proof automation tools, neural-netwond -ettorr--eoooo provers, or hybrid approaches. If the automated prover successfully closes all the gaps in the proof sketch, it returns the final formal proof which can be checked against the problem's 's specification. If the automated prover fails (e.g., it exceeds the allocated time limit), we consider the evaluation be unsuccessful.
EXPERIMENTS
4.1 DATASET AND EVALUATION
We evaluate method the miniF2F dataset (Zheng et al. 2022). The dataset contains the formal statements of 488 problems from high-school mathematical competitions, written in three formal languages: Lean, HOL-LLggtt, and Isabelle. They split into valid set and test set, composed
4

---

Published as a conference paper at ICLR 2023
of 244 problems each. In this work, we choose to experiment with Isabelle for three reasons: (I) Isabelle's 's proof corpus is one of the largest among interactive theorem provers, conducive to the language models' mastery of its syntax; (2) Isabelle supports the declarative proof style (detailed discussion in Appendix A). enabling formal proof sketches (Wiedijk] 2003) which are central to our method; (3) although automated proving tools are available in other interactive theorem provers, none are as developed and effective as Sledgehammer (Paulson 2010) in Isabelle for proving conjectures.
The miniF2F dataset is comprised of problems from three source categories: (1) 260 problems sampled from the MATH dataset (Hendrycks et al. 202T); (2) 160 problems from actual high-school mathematical competitions (AMC, AIME, and IMO); (3) 68 crafted problems at the same difficulty level as (2). We employ three methods to obtain informal statements and proofs from these sources. For source (1), we access the informal statements and proofs from the MATH dataset; for (2), we retrieve their informal statements and proofs from the AOPS website I and for (3), we manually write down their informal statements and proofs. Thus we gather parallel set of 488 informal statements, informal proof', and formal statements. This dataset provides the informal statements and proof' for our experiment in the human-as-informan. www-iiiooooooooo-ooiiiieee-
setting and will be released upon publication.
Our task is to generate formal proofs for problems as they are formally stated in miniF2F. We consider a proof valid if and only if it (a) does not contain "cheating" keywords (sorry and oops) that exit proof without completing it, and (b) Isabelle is able to verify the corresponding formal statement with the proof. We use the Portal-to-ISA Abbelle API by Jiang et al. (2021) to interact with Isabelle.
4.2 BASELINES
Sledgehammer As a baseline, we attempt to prove the formal statement directly with Sledgeham- mer, a popular proof automation tool in Isabelle. We use the default Sledgehammer configuration in Isabelle2021, including 120-second timeout and the five automated theorem provers (733, CVC4, SPASS, Vampire, E). Appendix B gives a more thorough introduction to Sledgehammer.
Sledgehammer + heuristics Occasionally, Sledgehammer may fail without trying simple yet effective tacties. As a second, stronger baseline, we create an automated prover that tries 11 com- mon tacties (auto, simp, blast, fastforce, force, eval, presburger, sos, ar arith, linarith, auto s simp: field.s imms) for high-school level algebra and number theory prob- lems. If every attempted tactic fails, or times out after 10 seconds, it falls back to Sledgehammer.
Language models for proof search Finally, we include baselines which are representative of state-of-the-art neural theorem proving in Isabelle, specifically Thor (Jiang et al.) [202]] and Thor with expert iteration on autoformalized data (Wu et al. 2022). The methods GPT-f with expert iteration (Polu et al. 2022), and HyperTree Proof Search (HTPS) (Lample et al. 2022) can solve 36.6% and 41.0% of the problems on miniF2F-test. However, they rely on the Lean theorem prover instead of Isabelle, which greatly influences the performance due to the different tactics and automation, and are not directly comparable to our method.
4.3 EXPERIMENTAL SETUP
The experimental code is at giggttuubb.... com
Drafting When informal proofs are generated, we condition a large language model on informal statements to sample 100 informal proofs per problem. Specifically, we use the Codex code-davinci- 002 model (Chen et al. 2021) through the OpenAI API, and the 8B, 62B, and 540B versions of the Minerva model from Lewkowycz et al. (2022). We use greedy decoding for Codex and nucleus sampling (Holtzman et al. 2019) with temperature = 0.6 and top p 0.95 for Minerva models.
Sketching For sketching, we manually prepare 20 autoformalization examples of the format (informal statement, informal froof.formal formal statement, formal sketch), to form pool of high-quality demonstrations. Of these 20 examples, 10 are of the algebra type and 10 are of the number theory type. All examples are from the validation set of the miniF2F dataset and can be found in the supplementary materials. The sketches contain in-e comments as in Figure 2] If the name of the problem gives away its type (algebru or number theory), we only use examples of the corresponding type. We also ensure that the sampled few-shot examples do not contain the problem being solved. The prompt 3 uniformly randomly sampled example from the pool concatenated with the current problem's 's (informal statement, informal formal statement). We use this prompt to query the
https:://rrtofproblessss ccm/ community ty
5

---

Published as a conference paper at ICLR 2023
Table Proving success rates on the miniF dataset with Isabelle the table are the success rates of four baselines, the DSP method with human and language model informal proofs, as well as three ablation studies, on the validation and the test sets of miniF2F. The highest success rates each set are highlighted in bold. The performance difference between ablation studies and DSP with human informal proofs are enclosed in brackets.
Success rate
miniF2F-valid
miniF2F-test
Baselines
Sledgehammer Sledgehammer heuristics Thor (Jiang ct al. 2022)
9.9%
10.4%
18.0%
20.9%
28.3%
29.9%
Thor expert iteration Wu et al. 2022
37.3%
35.2%
Draft, Sketch, and Prove
Human informal proof
42.6%
39.3%
Codex informal proof
40.6%
35.3%
8B Minerva informal proof
40.6%
35.3%
62B Minerva informal proof
43.9%
37.7%
540B Minerva informal proof
42.6%
38.9%
Ablations (with human informal statements and proofs)
In-line comments
37.7%
(-1.9%)
36.5%
2.8%
Informal proofs
38.9%
3.7%)
34.0%
5.3%%
Automated provers
32.8%
9.8%)
30.3%
9.0%)
same Codex model to get the desired proof sketches. We use deterministic greedy decoding and a maximum of 2048 tokens in the generated sequence. For all the experiments, unless stated otherwise, we control the total number of queries made to Codex per problem to be 100. This means 100 queries per human informal solution and one query per language-moddl-geeeraedd solution.
Proving To prove the conjectures left open by the formal sketch, we use the Sledgehammer + heuristics automated prover described in Subsection 4.2 We execute the automated prover on every open conjecture in the sketch to synthesize a formal proof that can be verified by Isabelle.
4.4 RESULTS
In Table we display the proportion of successful formal proofs found on the miniF2F dataset with the interactive theorem prover Isabelle. The results include the four baselines described in Subsection 4.2 and the DSP method with human-writter proofs and model-generated proofs. From the table, we can see that the automated prover with 11 additional heuristic tactics significantly increases the performance of Sledgehammer, boosting its success rate from 9.9% to 18.0% the validation set of miniF2F and from 10.4% to 20.9% on the test set. The two baselines using language models and proof search (Thor and Thor + expert iteration) achieve success rates of 29.9% and 35.2% on the test set of miniF2F, respectively.
With informal proofs written by humans, the DSP method achieves success rates of 42.6% and 39.3% on the validation and test sets of miniF2F. A total of 200 out of 488 problems can be proved in this way. The Codex model and the Minerva (8B) model give very similar results in solving problems on miniF2F: they both guide the automated prover to solve 40.6% and 35.3% of problems on the validation and the test sets respectively. This is corroborated by [Lekkwyczz et al. (2022)* observation that these two models have comparable performances in solving mathematical problems.
When we switch to the Minerva (62B) model, the success rates rise up to 43.9% and 37.7% re- spectively. Compared to human-written informal proofs, its success rates are 1.3% higher on the validation set and 1.6% lower on the test set. total, the Minerva (62B) model able to solve 199 problems on miniF2F, one fewer than with human proofs. The DSP method is effective in guiding the automated prover under both settings that we study: using either human informal proofs or language- woeeuagee-odel-eeee model--eeeratte informal proofs. DSP almost doubles the prover's success rate and results in new state-of- of-te--a---rrtt performance on miniF2F with Isabelle. Moreover, the larger Minerva model almost as helpful human in guiding the automated prover in solving problems.
5
ANALYSIS
5.1 ABLATION STUDIES
Ablation of in-line comments To facilitate the alignment between the informal proofs and the formal proof sketches, we copy relevant segments of the informal proofs in-line comments in

---

Published as a conference paper at ICLR 2023
MiniF2F Problems Solved (out of 488)
MiniF2F Problems Solved (out of 488)
200
200
#Successful Proofs
#Successful Proofs
150
150
Human informal proof drafts
100
DSP with human proofs
100
Minerva (540B) proof drafts
Ablation: in-line comm
Minerva (62B) proof drafts
Ablation: no informal proofs
Minerva (8B) proof drafts
50
Ablation: no automated provers
50
Codex proof drafts
0 20
40
60
80
100
0 20
40
60
80 100
# #uutfformalization Attempts Per Problem
# #Autoformalization Attempts Per Problem
Figure 3: Number of problems solved on miniF2F against the number of autoformalization attempts per problem. Left: The figure displays the experiments carried out with the DSP method and three ablations on The curves represent the DSP method (blue), formal proof sketches without the in-line comments (orange), without informal proofs altogether (green), and without the automated provers (red), Right: The figure compares the experimental results with informal proof drafts written by humans (blue), the 540B Minerva model (orange), the 62B Minerva model (green), the 8B Minerva model (red), and the Codex model (purple).
the sketches. In the manually constructed prompt examples, these comments are prefixed to the corresponding Isabelle code blocks, as shown in miiuuee 2 (the text in red). We hypothesize that this technique is beneficial for large language models to synthesize formal sketches To validate this hypothesis, we perform an ablation study by removing the in-line comments in the prompt examples before running the experiment. The results are displayed in (Table 1 We find that without in- comments, the success rates drop by 4.9% and 2.8% on the validation and test sets respectively. We conclude that having in-line comments is helpful for generating formal proof sketches.
A Ablaiion of informal proof drafts Drafting informal proofs is the first step of the DSP method. To investigate the necessity of this step, we perform an experiment of formal sketching and proving without informal proofs at all. Because formal proof sketches are written the declarative proof style, they are fairly similar to the informal proof drafts already. Concretely, we remove the informal proofs and the in-line comments (because they are copied segments of the informal proofs) in the prompt examples. This removes the need for the informal proof writer, whether human or neural network. The results of this setup are shown in Table 1 It can be seen that the success rates on the validation and the test sets of miniF2F drop by 3.7% and 5.3% respectively compared to with suman-writted proofs. They are also inferior to success rates obtained with language- cooguagg--moel-eeeee model-generated informal proofs. This demonstrates the importance of drafting informal proofs before sketching and proving.
Ablation of automated provers Using an autoformalizer to generate proof sketches which are then completed by an automated prover is central to our method. The effect of utilizing an automated prover to close open conjectures in proof sketches is worth studying, so we conduct an ablation experiment for it. Namely, we replace the proof sketches the prompt examples with complete formal proofs. The complete formal proofs still follow the declarative proof style, but do not contain any open conjectures. As a result, the large language model will also generate full proofs instead of sketches, and we directly check whether these generated proofs are valid. The results in this setup presented in Table I The results reveal that without an automated prover to close open conjectures, the success rate mi decreases by 9.8% and 9.0% on the validation and test sets respectively. The drastic performance difference indicates the essential role of automated provers in our approach.
Scaling properties of ablation studies To understand the effect of the ablations on the DSP method's 's scaling properties. we vary the number of autoformalization attempts per problem and plot the number of successful proofs found on the miniF2F dataset Figure 3 (left). Three methods are contrasted: the original DSP method with human informal proofs, the DSP method without in-line comments, and the DSP method without sketching. It can be seen from the figure that with the original DSP method, the performance reaches plateau (no new proofs are found) after 70 autoformalization attempts are made for each problem. For the ablation study with no in-line comments, the plateau is reached much faster, after around 50 autoformalization attempts. This method solves 181 problems in total. The ablation study without sketching can solve 154 problems on FF. In comparison, with human informal proofs, only? 7 autoformalization attempts are required reach this performance.
7

---

Published as a conference paper at ICLR 2023
Statement:
Prove the fraction 2in+d irreducible every natural number n. 14m+3
Informal Proof (Minerva 62B): We must show that ged 4, 14n L. The Euclidean algorithm gives
21n + 1- (14n + 3) in
14n + 2 (7n +.
Since ged + 1, we have god(21n + 4, 14m +3)
Formal Proof:
theorem 1mo_1959_pl:
fixes
shows "god, (21+n 4) (14sn 3) 1" proof
(* The Buclidean algorithm gives 21n+4=1ledee (14n+3)++mm +7++1
14n+3=2\edot (7n+1)+1.
have c0: "21+n + 114 + 3) 7+n + 1" <ATP> by auto </ATP>
have cl: "14mn + +3 (7An + 1) + +1 using c0 <ATP> by auto </ATP>
(* Since \god( 1)=1, we have (god(2int4,14mg) 14nt))=1. *)
then. have "god (7
==
using el <AIP> by auto </AIP>
then. have "ged (21+n 4) (14en 3) = 1
using cl <AIP> by (smt (23) BitM_plus _ln one ab www.sriiinnuu..o hacpsa_add__aasaaeeee class.acc_acti. add.asscc c godmcor god_add2 god_adddmmll mult mult_numeral_"
numeral_ numeral _ee_____uu_ numerals(1) semiring </ATP>
then show ?thesis using cl <ATP> by blast </ATP>
qed
Figure 4: IMO proof guided by Minerva informal proof An informal proof of the International Math Olympiad problem imo_1953 1_9_ppl9pp generated by Minerva that leads to successful formal proof. The steps enclosed by the ATP delimiters are generated by an automated prover and all other steps are generated by the DSP autoformalizer.
5.2 LANGUAGE- WEEE-MMOODEEEAETEEEEEE PROOFS
Our experiments demonstrated that mrodel-generatee informal proofs from Minerva and Codex help guide a formal theorem prover. this section, we analyze the properties of these proofs further. Since the Minerva (62B and 540B) models give the best overall performance miniF2F, focus on the informal proofs they produce in this section.
Minerva helps solve one IMO problem Interestingly, our approach manages to solve one problem from the International Mathematical Olympiad (imo 959_1) with Minerva-genent but not with the human proof. For this problem, we present the successful Minerva-gent sinerva-generated informal proof draft and the formal proof in FFigure 4, We hypothesize that the reason behind this phenomenon that human proofs might leave gaps between conjectures that are too difficult for automated provers to solve. On the other hand, the diversity in language model informal proofs makes some of them more amenable to automated provers. InApppendix C we analyze the human and the Minerva informal proofs for this problem in greater detail. In Apppendix D present manual evaluation of Minerva proofs, and 3 more case studies comparing the human and Minerva informal proofs.
solution,
there a way to detect which Minerva proofs are correct, without human evaluation? For a preliminary investigation,
filter out all the problems that can be solved directly with the automated prover from the 50 and are left with 27 informal proofs. Of these 27, 21 are completely correct, still contain small errors, but none are nonsensical. With this simple filter, we achieve precision of 77.8% and a recall of 72. 42.4% in identifying correct Minerva informal proofs.
8

---

Published as a conference paper at ICLR 2023
Scaling properties of human and Minerva proofs To understand the influence of different infor- mal proof sources on the scaling properties of DSP, we plot the number of successful proofs found on miniF2F against the number of autoformalization attempts per problem in Figure 3 (right). Note that for each problem, we have informal proof by a human and 100 informal proof drafts by each lan- guage model. The one human proof is used 100 times for formal proof sketch generation, while each language model proof draft is used only once. The 62B and the 540B models result in more successful proof' than the smaller (8B) Minerva model and the Codex model, consistently for any number of at- tempts. The 8B Minerva model and the Codex model behave similarly, both finding 185 proofs in the end. Informal proofs written by humans help solve more problems than those by Minerva models for 1 100 autoformalization attempts. However, the difference is small (1 problem) when 100 are made.
Noticing that the number of successful proofs does not plateau for the Winerva-generater proofs, we investigate how further increasing the number of autoformalization attempts changes the number of problems solved for human-written and language-model -enegeeeedddlllgeettteeeeddddd proofs. For each problem, we use 1 human informal proof and sample 200 sketches for it; we also use the same 100 informal proof drafts by the Minerva (540B) language model and sample sketches for each draft. The total number of sketches per problem is 200 in both settings. We find that with human informal proofs, 203 theorems (106/97 /97 on valid/test) have successful formal proofs, while with language- geguuagge-odel--e moodel-generale informal proofs, 209 (111 198 on valid/test) theorems have successful formal proofs after the same informal proofs
number of attempts. This suggests that the diversity in can benefit the automated formalization process more than the "ground-truie human proofs.
5.3 MEMORIZATION
This work utilizes two language models that have been trained on large amount of internet data. Several prior works (Trinh & Le| 2018, Carlini et al.] 2022) pointed out that such models can memo- rize some fraction of the data they encounter during training. For drafting informal proof', we mainly experimented with Minerva. Lewkowyez et al. (2022) Section 5) discussed the memorization effeets within Minerva and concluded that they could not find evidence that its abilities are due memo- rization. For the autoformalization of proof sketches, the Codex (code-day sravine inci-002) model was used. Its training data was collected before June 202 at which time the miniF2F dataset had not been made public. So the model cannot benefit from memorizing the exact problems and proofs. Therefore, is inappropriate attribute the abilities of models used in this paper to memorization.
CONCLUSION
In this paper, we introduced Draft. Sketch, and Prove (DSP), a novel approach that takes advantage of informal proofs to synthesize formal proofs. We demonstrated its fcasibility and effectiveness by reaching state-of-the-art performance on the mi dataset with the Isabelle theorem prover. Central to our method are formal proof sketches that mirror the high-level reasoning structures of informal proofs. Our ablations showed that the ability to automatically convert informal proofs to proof sketches is critical to the success of DSP.
Our DSP method differs fundamentally from previous applications of machine learning to formal proof synthesis in two aspects. Firstly, while most approaches in the field focus on improving proof search, our method seeks to construct the entire formal proof structure from the informal proof in one decoding operation. The task of the automated prover is then simplified to filling the gaps between intermediate conjectures. Secondly, while existing approaches operate exclusively on formal data, DSP by design benefits from informal proofs.
In this work, we utilized a purely symbolic automated prover to close the gaps in proof sketches. In the future, we aim equip DSP with more powerful mechanisms, such HyperTree Proof Search (Lample et al. 2002). to broaden the scope of provable theorems. Similar to AlphaCode (Li et al., (022). we found that the number of generations is crucial for performance. The computational cost of the autoformalizer being bottleneck in our method, we seek to develop approaches able to generate high-quality proof sketches more efficiently.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We thank Rui Yuan and Kunhao Zheng for helping with the informal solutions used in our dataset. We thank Christian Szegedy for his feedback on the early draft.
FUNDING DISCLOSURE
AQU and WL are supported by the ERC Advanced Grant ALEXANDRIA (Project GA 742178)
REFERENCES
Kshitij Bansal, Sarah M. Loos, Markus N. Rabe, and Christian Szegedy. Learning to reason in large theories without imitation. CoRR, abs/1905.10501, 2019a. URL httptttp///aa//..rr////
1905. 10501
Kshitij Bansal, Sarah M. Looo, Markus N. Rabe, Christian Szegedy, and Stewart Wilcox. Holist: An environment for machine learning of higher order logic theorem proving. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 454 463. PMLR, 2019b. URL http::t::p:/oceeeeeeet html
mlr.
Bruno Barras, Samuel Boutin, Cristina Cornes, Judicaël Courant, Jean-Christophe Filliatre, Eduardo Gimenez, Hugo Herbelin, Gerard Huet, Cesar Munoz, Chetan Murthy, et al. The Coq proof assistant reference manual: Version 6.1. PhD thesis, Inria, 1997.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien I.in (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL httphhttp/pco. http:pppppppopccpppiittteoeoeeee newriis.nrrpppp. wwwperps..pppppppppppee http://pp...o/pppp/////////e/ee 4457
Abst .wt.raattttttmmmmmm.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramèr, and Chiyuan Zhang. Quantifying memorization across neural language models. CoRR, abs/2202.07646, 2022.
URL htt.ttsss///riii...ortt wwwp:/iwv..ioooooooooooo abs 2202. 07646)
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harrison Edwards, Yura Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, David W. Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William H. Guss, Alex Nichol, Igor Babuschkin, S. Arun Balaji, Shantanu Jain, Andrew Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew M. Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. Evaluating large language models trained on code. ArXiv, abs/2107.0333 2021.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito. David Luan, Hyeontaek Lim, Barret
10

---

Published as a conference paper at ICLR 2023
Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Er- ica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language model- ing with pathways. CoRR, 0bs/2204.00211,, 2022. doi: 10448550/rXiw.224400223
URL
https: /tpp:://oi.... www.0i.rgg11... 48550 /11350/aaXivv 2204 02311
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255 255. leee, 2009.
Iddo Drori, Sarah Zhang, Reece Shuttleworth, Leonard Tang, Albert Lu, Elizabeth Ke, Kevin Liu, Linda Chen, Sunny Tran, Newman Cheng, et al. A neural network solves, explains, and generates university math problems by program synthesis and few-shot learning at human level. Proceedings of the National Academy of Sciences, 11963))x22233433111
2022.
Thibault Gauthier, Cezary Kaliszyk, Josef Urban, Ramana Kumar, and Michael Norrish. Tactictoe: learning to prove with tactics. Journal of Automated Reasoning, 65(2):257-286, 2021.
Jesse Michael Han, Jason Rute, Yuhuai Wu, Edward W. Ayers, and Stanislas Polu. Proof artifact co-training for theorem proving with language models. In The Tenth International Conference on Learning Representations. ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
URL httpt:://
net wwwpteeeeeeeiiiieeeeeeeeeee /ttp://rrmmiaaapxXX._999090
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. NeurlPS, 2021.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. arXiv preprint 1r0iv:1904.0977 2019.
Albert Q. Jiang, Wenda Li, Jesse Michael Han, and Yuhuai Wu. LISA: Language models of Isabelle proofs. In 6th Conference on Artificial Intelligence and Theorem Proving, 2021.
Albert Q. Jiang, Wenda Li, Szymon Tworkowski, Konrad Czechowski, Tomasz Odrzygózdz, Piotr Milos, Yuhuai Wu, and Mateja Jamnik. Thor: Wielding hammers to integrate language models and automated theorem provers. CoRR, 10t//2205510893,,0. 2022. doi: 10448550/arxi.2205..899 URL / wtt.://....rr.......55/a/a./////
2205. 10893
Guillaume Lample and François Charton. Deep learning for symbolic mathematics. International Conference Learning Representations, 2020. URL httpt:::///oeeeeeeeeeeee wwt.:iiwwwweeeeeeee.....e....eee
id=81eZYeHFDS)
Guillaume Lample, Marie-Anne Lachaux, Thibaut Lavril, Xavier Martinet, Amaury Hayat, Gabriel Ebner, Aurélien Rodriguez, and Timothée Lacroix. Hypertree proof search for neural theorem proving. CoRR, 1bs/2205.111911, 2022. doi: 10:48550/a2xi..2255..1 1491. URL https://dooi org/10 48544/8555X 220... 11.911191
Jonathan Laurent and André Platzer. Learning find proofs and theorems by learning refine search strategies. CoRR, 0bb/2205..14229 2022. doi: 10.44550//2xx..2255..44 14229. (Rthtt
41ll:..oo//1..4450//raa..... 2205. 14229
Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with language models. CoRR, abs/2206. 18558, 2022. doi: 10.48550Waxiv.22066 248888 48550/arXiv. wtt.://g/g...455//ax.x..... 220..1482..222222 14858
//doi.org/10
Yujia Li, David H. Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel Mankowitz, Esme Sutherland Robson,
11

---

Published as a conference paper at ICLR 2023
Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level code generation with alphacode. CoRR, abs/2203.07814, 2022. doi: 10448500arXx..2223..778111 URL /ttpp::////oo..ogg/// wttp:///...../........22222...00
Norman D. Megill and David A. Wheeler. Metamath:
Computer Language North Carolina, 2019.
for Mathematical Proofs. http:/ /us. www.math hwwg///owoodd..s. aetamaah, pdf.
Lulu Press, Morrisville,
Leonardo de Moura, Soonho Kong, Jeremy Avigad, Floris van Doomn, and Jakob von Raumer. The lean theorem prover (system description). In International Conference Automated Deduction, pp. 778..88. Springer, 2015.
Lawrence C. Paulson. Isabelle A Generic Theorem Prover (with a contribution by T. Nipkow), volume 828 of Lecture Notes in Computer Science. Springer, 1994, ISBN 3-540-58244-4, doi: 10.1007/B760030041. URL
Lawrence C. Paulson. Three years of experience with sledgehammer, a practical link between automatic and interactive theorem provers. Renate A. Schmidt, Stephan Schulz, and Boris Konev (eds.). Proceedings of the 2nd Workshop on Practical Aspects of Automated Reasoning, PAAR-2010, Edinburgh, Scotland, UK. July 14, 2010, volume of EPiC Series in Computing, pp. 1-10. EasyChair, 2010. doi: 10.29007/tnfd. URL ht doi org/ 29007/tnfd
Stanislas Polu and Hya Sutskever. Generative language modeling for automated theorem proving. CoRR, abs/2009.03 003993, 2020. /tLhttts::/ arxiv. /tg/ htt.ttpss//ax....rroaaa/////////
03393
Stanislas Polu, Jesse Michael Han, Kunhao Zheng, Mantas Baksys, Igor Babuschkin, and Ilya Sutskever. Formal mathematics statement curriculum learning. CoRR, abs/2202.01344,, 2022.
URL wtt.:httss//atttio org. hbtp:/bs/2220 /2022.22222.22 01344
David Silver, Thomas Hubert, Julian Schrittweseer, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144 1144, 2018.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. Advances in neural information processing systems, 27, 2014.
Donald Syme. DECIARE: A prototype declarative proof system for higher order logic. Citeseer, 1997.
Christian Szegedy. A promising path towards autoformalization and general artificial intelligence. In Christoph Benzmüller and Bruce R. Miller (eds.), Intelligent Computer Mathematics - 13th Interna- fional Conference, CICM 2020, Bertinoro, Italy, July 26-31, 2020, Proceedings, volume 12236 of Lecture Notes in Computer Science, pp. 3-20. Springer, 2020. doi: URL /tt
Trieu H. Trinh and Quoe V. Le. A simple method for commonsense reasoning. CoRR, httss8886.02877, 2018.
02847
Qingxiang Wang, Chad E. Brown, Cezary Kaliszyk, and Josef Urban. Exploration of neural machine translation in autoformalization of mathematics in mizar. In Jasmin Blanchette and Catalin Hritcu (eds.), Proceedings of the 9th ACM SIGPLAN International Conference Certified Programs and Proofs, CPP 2020, New Orleans, LA, USA, January 20-21, 2020, pp. 85-98. ACM, 2020. doi: URL httsttss:: /oii 1et.g//...113337788888 00722288553333777 3373827
10.1 00.1145//372885.333333
Sean Welleck, Jiacheng Liu, Ronan Le Bras, Hannanch Hajishirzi, Yejin Choi, and Kyunghyun Cho. Naturalproofs: Mathematical theorem proving in natural language. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Truck (Round 1), 2021. URI.
fittps://opent lew net. forrmoorr///// dd= 8adr3iy
Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models. CoRR, wwwp/22s....9111112 2022. doi: 10. 00.48500/rxiv 12910. URL htRltttps:/ / .eriiiorggll 100 48550/ www.:ww............ 12910
12

---

Published as a conference paper at ICLR 2023
Freek Wiedijk. Formal proof sketches. In Stefano Berardi, Mario Coppo, and Ferruccio Damiani (eds.), Types for Proofs and Programs. International Workshop, TYPES 2003. Torino, Italy, April 30 May 2003, Revised Selected Papers, volume 3085 of Lecture Notes in Computer Science, pp- 378-397-- Springer, 2003. doi: 10. 1111107997-3-554-245555 7/doi 0.
24. URL https
24
Freek Wiedijk. Formal proof -getting started. Notices of the American Mathematical Society, 55: 1414, 2008.
Minchao Wu, Michael Norrish, Christian Walder, and Amir Dezfouli. Tacticzero: Learning to prove theorems from scratch with deep reinforcement learning. Advances in Neural Information Processing Systems, 34:9330-9923 2021a.
Yuhuai Wu, Albert Jiang, Jimmy Ba, and Roger Baker Grosse. INT: An inequality benchmark for evaluating generalization in theorem proving. In International Conference on Learning Representations, 2021b.
Yuhuai Wu, Albert Q. Jiang, Wenda Li, Markus N. Rabe, Charles Staats, Mateja Jamnik, and Christian Szegedy. Autoformalization with large language models. CoRR, abs/2205. 2022. doi: 10.485550/rXXi.2205... 12615.
http:///w....r11..1.155555////// 220. 2205. 12615
Kaiyu Yang and Jia Deng. Learning to prove theorems via interacting with proof assistants. In International Conference Machine Learning (ICML), 2019.
Kunhao Zheng, Jesse Michael Han, and Stanislas Polu. miniF2F: cross-system benchmark for formal olympiad-level mathematics. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https::/openreviees net net:/oorumioos32Peeeea
13

---

Published as a conference paper at ICLR 2023
A APPENDIX
A CONJECTURES AND THE DECLARATIVE PROOF STYLE
Interactive theorem provers such as Isabelle and Mizar use a declarative proof style (Syme) 1997). in which a proof is interleaved with conjectures and their corresponding proofs. [Syme 1997) stated that the list of conjectures a declarative proof should analogous to a proof sketch found in mathematical textbook and sufficiently convincing for the reader. In practice, ITP users often prove theorem by writing down list of conjectures (a "formal sketch"), then attempt to find a proof of each conjecture (fill "gap") with automated system.
B SLEDGEHAMMER
Sledgehammer Paullson 2010 a powerful system that automates reasoning with the interactive theorem prover Isabelle. It works by flattening the goals encoded in the higher-order logic used by Isabelle/HOL into other logics (e.g.. first-order logic) which can then be fed into automated theorem If any of these automated theorem provers succeeds in finding the proof in their own corresponding format, Sledgehammer reconstructs the proof in Isabelle/HOL. with certified provers (met meson, and smt), which is relatively more interpretable by humans.
provers such as E CVC4 I
Z3 P Vampire O and SPASS P
As a practical example of using Sledgehammer, one declare conjecture in Isabelle/HOL: have "4 dvd (a::nat) = 2 dvd a" and call Sledgehammer immediately afterwards. If Sledgehammer succeeds, it will return proof step that proves the conjecture. In this example, the step is by (meson dvd_t raass even numeral) which uses the meson resolution prover and two facts: that the division relation is transitive and that is even number. If Sledgehammer does not find the proof or timeouts, will report failure.
C A PROOF TO AN INTERNATIONAL MATHEMATICAL OLYMPIAD PROBLEM
With the Minerva-generater solutions, proof to the problem imo 1 1959 p1 is discovered. This is the first problem the first ever International Mathematical Olympiad (IMÒ). The informal problem statement, Minerva-generaaed informal solution, and DSP's formal proof are shown in Figure 4
In Figure 4
we can see that the autoformalizer DSP (a large language model), copies over parts of the informal proof generated by Minerva as in-line comments to precede their corresponding formal proof blocks. The formal proof does not use the first sentence of the informal proof solution as is already identical to the formal statement. We also notice that the large language model selects relevant premises after writing down the conjectures (the steps starting with using) despite not every premise is strictly needed.
The formal proof creates 5 conjectures (4 have statements and 1 show statement) which are all subsequently proved by our automated theorem prover. The step to prove the statement have "ged (21*n + 4) (1.4 (14*n x + 3) = 1 involves verified low-level provers smt and z3 and 10 lemmas/facts from outside the scope of the language model. It is highly unlikely that either the large language model or the automated thcorem prover can finish this proof on its own.
Unsuccessful human-written proof. In contrast, the human- human-written informal proof of this IMO problem did not lead to a successful formal proof. The human wnriten proof is:
Denoting the greatest common divisor of a, 6 as (a, 6), we use the Euclidean algorithm:
(2ln + 4, 14n + 33 = (7n + 1, 14n + 3) = (7n + 1, =
sschulz/E/E.html
https://cved httpns//evo4.iiiuuuboooo wwwthb.ioo/ide....oo html
https:/github.co http://gituub.com//PPooor http:tto..oom////////3333
https///pprovrrggihbb.io/
14

---

Published as a conference paper at ICLR 2023
It follows that 21m+4 is irreducible. Q.E.D.
14m+3
A key difference between the Minerva proof and the human proof is the way that invoking the Euclidean algorithm is described. The Minerva proof explicitly writes the results of the Euclidean algorithm (e.g. 21n + 4 1 (14n 3) + 7n 1), which are translated into the sketch (cl in Figure 4). The human proof introduces new notation to express the results indirectly in terms of greatest common divisors, which ends up being less suitable for sketching. For example, below is a sketch generated with the human proof, which has conjecture that is semantically incorrect and hence cannot be closed by the automated prover:
theorem
fixes nat
shows "god (21 4) (14en 3)
proof
have (21 4, 14 + 3) (7+n 1, 14+n + 3)"
ATP (* <- UNSUOCESSFUL +)
also have "... (7mn 1, 1)"
ATP
finally show 7thesis
ATP
qed
15

---

Published as a conference paper at ICLR 2023
D MORE ANALYSIS ON HUMAN AND MINERVA INFORMAL PROOFS
We analyze the relationship between the validity the formal proofs and the correctness of the informal proofs. For our analysis, we randomly sample 50 Minerva proofs of different problems, which are then successfully converted to formal proofs. We then manually evaluate the correctness of these 50 informal proofs. Among them, 29 proofs (58%) are entirely correct, 16 are incorrect with clearly identifiable incorrect step, and 5 "proofs" are nonsensical and simply rephrase the final conclusions of the problems.
Seeing that total of 16 + 5 = 21 incorrect informal proofs can lead to successful formal proofs, we study how they guide the automated formal prover despite having flaws themselves. The 21 proofs divide into 2 cases: In the first case, we find 13 problems for which the informal proofs are mostly ignored, and the automated prover can find proofs by itself; In the other problems, although the informal proof' are wrong, the autoformalizer manages to correct them, either by ignoring the erroneous steps or by stating their correct versions the formal proof sketches. This suggests that the autoformalizer has some understanding of the mathematical statements and is not merely translating them from an informal language to a formal language. is robust to slight noises in its input.
We present 3 case studies comparing the human and Minerva informal proofs. Particularly, Figure shows a completely correct example and one example of each pathological case.
16

---

Published as a conference paper at ICLR 2023
Statement: Given that + 3: 11 and 3( 1) 5z 68, show that = 10 and z 7.
Informal Proof (Minerva 62B):
We can solve for in the first equation, obtaining 11 3z. Then we can substitute this expression for f into the second equation,
obtaining 3(11 32 1) 52 68.
Solving for we obtain 7.
Then, we can substitute value into expression for f. obtaining = -10.
Formal Proof:
theorem algebra ieaarlinnaree__fpaeeee http:eeeee_.tmmmmneeeeeee_.eeee
fixes :complex
assumes h0: "i 3+2 11"
and hl: "3* (f - 1) 5+2 = -68" -68"
shows "f - -10 <<nnd> 2 7"
proof
(* We can solve for in the first equation, obtaining 3z. *) have c0: "f 11 3xz"
using h0
by (auto simp: field simps) ATP)
(* Then
substitute this expression for ff into the second equation,
obtaining 3 (11 3z 1) -68.
have cl: "3* (11 3+2 - 1) 5+2 = -68"
using hl c0
by auto [ATP]
(* Solving for z, obtain 7. *)
have c2: "z 7"
using cl
by auto |ATP]
(* Then, can substitute this value of into the expression for obtaining f
\odot -10.**)
have "f
3+7"
using c0 c2
by auto [ATP]
then have c3: "f -10"
by auto [ATP)
show ?thesis
using c2 c3
by auto [A7P]
qed
Figure 5: Algebra example with Minerva informal proof. An informal proof generated by Minerva that led to successful formal proof. The autoformalizer generated proof sketch containing all lines of the formal proof except for those with [ATP]. The sketch is structured according to the informal proof, containing five intermediate conjectures based on the informal proof. The autoformalizer generated in-line comments in the proof sketch (shown in red), which correctly identified an alignment between the formal and informal proofs.
17

---

Published as a conference paper at ICLR 2023
Statement: For any integer show that a² 0 (mod 4) a² (mod 4).
Statement: For any integer show that a² 0 (mod 4) a² (mod 4).
Informal Proof (Minerva 62B):
Informal Proof (Minerva 62B):
Let a = 2k for some integer k.
(mod 4) E {0, 1, 2,
Then a² = 4k
Using that for any natural number k. (mod 4) implics a" 6² (mod 4), have a² (mod 4) E {0. 1, 9).
Since 4k is divisible by 4, we have a²
(mod 4).
Now, let a = 21: + for some integer k.
Since = 0 (mod 4) and 9 = (mod 4), the result follows.
Then a² = 11k² + 1k + 1(h² + k) + 1. Since k² + k is integer, 4(k² k) is not divisible by
Thus, a² (mod 4).
Formal Proof:
Formal Proof:
theorem numberthhoory_eemmddiiio fixes int
theorem nunterthheory_smmo//inddddd fixes int
shows (a"2 mod 0)
shows " "Ia"2 mod 4 0)
\<or> (a"2 mod 4 - 1)"
\<or> (a"2 mod 4 1)" proof
proof (cases "even a")
True
(* \pmod 4 Vin (0, 1, 2, 3). have "a mod Viin {0, 1, 3)" by auto [A7P]
(* Let a=2k for some integer k. Then a²2=4k'2 2.
Since 4k'2 is divisible by 4, have a"2 \equiv \pmod(4) then obtain k where "3=2.k"
(+ Using that for any natural number k, lequiv b \amod 4 implies
a'k Vequiv b*k Apmod 4,*)
using evenE by auto [ATP]
have "a"2 modi (a mod 4) suup
2 mod 4"
then have "a"2 4*
by (ent (23) numoral eq power_moc) [ATP]
unfolding power2_eq equuuare square by auto [ATP)
(* have a'2 \pmod 4 Vin {0, 1, 4, 9) *) also have "... A<in> (0, 1, 4, 9)
then have "a"2 mod 0" by auto [A7P] then show 2thesis by auto [ATP]
using c0
by auto IATP]
next
(* Since 4 \equiv \pmod and lequiv \pmod 4,
case False
(* Now, let a=2k+1 for some integer k.
the result follows. *)
Then a 2==44 2"2==k"2+dkktee 2+4k+1=4 +1
finally show ?thesis by auto [A7P]
Since k'2+k is integer, 4 (k (2'2+)++ +1 is not divisible by 4.
ged
Thus, a'2 lequiv \pmod(4) 4) *))
then obtain k where "a=2>k+1" using oddE. by auto [A7P]
then have "a"2 4**"2+4<k+1"
unfclding power2_eg la_______uue square by (auto simp: field simps) (ATP)
then have "2"2 mod 4 - 1" by presburger [A7P]
then show ?thesis by auto [ATP]
ged
Figure 6: Alternative proofs: Minerva (left) and human-written (right). both proofs, the formal sketch structured based on the informal proof. The Minerva informal proof and its sketch break the proof into even and odd cases. These cases are not explicitly stated in the informal proof, and the formal sketch makes them explicit (cases "even a a)) Each case has three conjectures that directly based the informal proof. The sketch excludes parts that are needed the formal proof, for instance "Since b² k integer, 4(k² + k) not divisible by 4". The human proof uses different strategy than the Minerva proof, based on the facts that (mod 4) E (0, 1, 1,2,3) and (mod 4) E (0, 1, 4, 9). The sketch uses these as conjectures, synthesizes an intermediate step not in the informal proof, and excludes the last step of the informal proof.
18

---

Published as a conference paper at ICLR 2023
For each plumbing repair job, Mr. Wrench charges dollars coming out the house plus z dollars per hour that works at the house. He charged 897 for one-hour repair job and $265 for five-hour repair job. What his charge for two-hour repair job? Show that is $139.
Statement:
Statement: Show that for any real number any natural number nG, x > -1, then (1 + nx) S (1 +(+))) z)".
Informal Proof (Minerva 62B):
This is true for n 1. Now, suppose that this true for n. Then we have that
Informal Proof (Minerva 62B):
(1 nx)" 1+ 1+1++ + na
Let N be the number of dollars charged for coming out the house and let the num- of dollars per hour Mr. Wrench works.
S 1 + no n2212 +... nx" = + x)
For the one-hour repair job, we have that the total cost is N + 97.
and
For the five- hour repair job, we have that the total cost
(e) = re) "( +
+ 5
We subtract the first equation from the second equation to obtain 4x = 168 + x = 42. Plugging this back into the first equation, obtain that N 55.
21+ +2) (1 x) u+1
Therefore, this is true for n n+1 +
Therefore, for two-hour repair job, the total
Formal Proof:
cost is 55 + 2x = 55 + (22) $139
theorem Indiuction__pxxonmmll
fixes x :: real and n :: nat
Formal Proof:
assumes #-1 x"
shows "(1 n4x) \<le> (1 x) "n"
theorem matho_ @acchh__agebba_a_00
fixes n x ::real
proof (induct
assumes "n + x = 97"
case then show 7case
and "n - 5 + X = 265"
shows "n + 2 x 139"
by auto [A7P] next case (Suc n) then. show ?case by (smt (23) Bernoulli innquuaityy assms) [ATP]
proof
(* We subtract the first equation from the second equation to obtain 4x = 168 > 42. *)
ged
have "4
168"
using asems by auto [A7P]
then have "x 42n
by auto [A7P] (* Plugging this back into the first equation, obtain that
Statement: Determine remainder 1529 (mod 6). Show that is
55 *)
then. have "n 55"
using assms by auto [ATP] (* Therefore, for two-hour repair job, the total cost is
Informal Proof (Minerva 62B):
By definition, 1529 (mod 6).
55 + 2x 55 + 2(42) $139. *) then show ?hhesis
Formal Proof:
theorem haanhd__mmmeehhoorr...5 "1529 mod = (5: :at))
by (sm:: (23) (x = 42)) [ATP]
qed
by auto IATP]
Figure Three Types of Minerva proofs: correct proof (left), incorrect proof (right top), nonsensical proof (right bottom) In the correct Minerva proof, the formal sketch is structured based on the informal proof and steps are well-aligned. In the incorrect Minerva proof, the step "This is true for 1" is corrected by Codex in the formal sketch to "case 0" which starts the base case with since natural numbers include This an explicit correction made by Codex and makes slightly incorrect Minerva proof formalized successfully. Lastly, the meaningless proof contains only a single statement without any calculation or justification. However, Codex also chooses to directly show the statement without any calculation. This suggests that the problem itself could be considered simple by Codex.
19


Reviews:
[{"review_id": "u_b1XlCOPO0", "reviewer": "Reviewer_7zK6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to guide the formal theorem prover using informal proofs. The key idea is to convert the informal proofs to formal proof sketches by prompting LLM as a few-short learner. On the miniF2F-test dataset, this approach improves the performance of the Sledgehammer + heuristics prover of Isabelle from 20.9% to 39.3% with human informal proofs and 37.3 with LLM-generated informal proofs.", "summary_of_the_review": "This paper proposes an interesting approach on how to make use of informal proofs for ATP. I recommend accepting this paper.", "strength_and_weaknesses": "This paper studies a promising direction of ATP,  to guide theorem provers using informal proofs. \nThe use of proof sketches is reasonable. The steps of prompting LLMs are technically sound.\nThe proposed approach requires no additional training on ground-truth proofs but achieves impressive results. \n\nOne question is that what if replace with the Sledgehammer + heuristics prover as the Thor prover? How much improvement can we get from Thor?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "u4BGNTxPZu", "reviewer": "Reviewer_9yAP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a large language models (LLM) to automatically generate formal proofs of mathematical statements. The idea is to use Codex or Minerva model to generate an informal proof (a proof in a natural language) and then use it as a sketch to generate a formal proof. Each claim in the sketch is a some kind of proposition, which is then proved by an off-the-shelf prover, like Sledgehammer. The approach is based on the ability of LLMs to do few-shot learning. A prompt to the model contains a formal statement to be proved, generated informal statement and informal proof, and several examples of tuples <informal statement, informal proof, formal statement, formal proof>. To provide appropriate examples, the authors gathered a dataset of parallel informal-formal proofs for the problems from the MiniF2F dataset and sample 3 random examples to make the prompt.\n\nThe approach was tested on validation and test splits of the MiniF2F dataset. In the experiments, the proposed approach outperforms the baselines. The ablation study demonstrates the benefit of using sketches and aligning them with formal proofs. Also, the results show that larger models have higher proof rates.", "summary_of_the_review": "The paper introduces a novel idea to guide formal proof generation with generated informal proof using large language models in a few-shot setting. The idea was justified by the experiments and ablation study. However, more analysis of the proposed approach should be conducted to make a clear picture of what part of the approach and to what extent affects the final result.\n", "strength_and_weaknesses": "+ While using LLMs for auto-formalization seems novel enough, this is the first work where LLM is applied to generate the whole proof. The idea of guiding formal proof generation with informal proof sketches is novel. The experimental section justifies that sketching indeed helps generate more correct proofs. The study in this paper demonstrates that the model makes use of the alignment between formal and informal proofs. This is the main contribution of the paper.\n\nThe paper also contains some analysis of how the prover's performance depends on the correctness of informal proofs. It turns out that the prover can fix some simple errors in informal proof and even ignore the informal proof if it is incorrect. This observation is interesting and suggests that the model can perform some kind of formal mathematical reasoning.\n\nThe paper is generally well written, experimental section demonstrates state-of-the-art results on the MiniF2F dataset, ablation study justifies the usefulness of the guidance by the informal proofs and the alignment between informal and formal proofs. The approach is built on top of existing pre-trained models and seems easy to implement if the models are available. \n\nCons:\n1. The examples play an important role and should be carefully constructed. In the paper, the authors try to use appropriate examples: first of all, all of them are from the MiniF2F dataset, secondly, whenever the problem type is known (from the problem name, e.g. it contains \"number theory\") they use the corresponding examples. So, the approach cannot be easily applied to other datasets.\n2. More analysis of the model should be conducted. Figure 3, \"Human informal proof drafts\" implies that it is also important to have good examples as different proof attempts differ only in provided examples. How close are the examples of successful proofs to the statement compared to failed proofs?\nIt is also interesting to separate the effect of chosen examples from the effect of generated informal proofs.\nFor example, we can use the same 3 examples for all proof attempts and only change the informal proofs.\n3. The method requires access to the LLM which is not widely available and limits the reproducibility of the approach.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "i2iWNk5Ni6", "reviewer": "Reviewer_AYPt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed a novel and nice procedure for automating interactive theorem proving, which combines state-of-the-art approaches to ML for (interactive) theorem proving. The key idea is to have a proof written in natural language (either provided by a human user or generated by a language model) translated into a formal sketch which is a skeleton of a proof script that can potentially be verified by the underlying theorem prover when all the details are filled in. An automated theorem prover, which can either be a high-level tactic of the underlying system, or an external learning based system, is then used to close the gaps in the sketch.\n", "summary_of_the_review": "The paper proposed a nice procedure for high-level automation for interactive theorem proving, integrating state-of-the-art approaches to ML for (interactive) theorem proving as its subroutines. The empirical evaluation validates the approach. I recommend accepting the paper.", "strength_and_weaknesses": "Strength:\n\n+ The paper is well written and easy to follow. I enjoyed reading it.\n\n+ The approach is technically sound, conceptually simple (which is good) and empirically working. Even better, the design of entire process is quite natural: first coming up with a proof in natural language and then turning it into a formal proof, organized in a way that subgoals can be easily automated, which is exactly what a human ITP expert would do.\n\n+ The paper nicely assembles existing approaches from subareas of ML for theorem proving (i.e., theorem proving in natural language, autoformalization, and learning-based automation for ITP) to make a complete procedure that provides high-level automation for interactive theorem proving.\n\nWeakness:\n\n- The good performance is probably not that surprising. Both Minerva (used for drafting) and Codex (used for sketching) might have seen the problems somewhere on the internet, formal or informal version in different forms (e.g., comments or code from different provers, or math overflow etc). After all, the competetion problems are famous.\n\nMinors:\n\n- It is [reported](https://github.com/openai/miniF2F/issues/103) that some problems in MiniF2F are not well formalized and some are wrong. The performance should perhaps be interpreted carefully. But apparently this isn't the authors fault.\n\n- In related work the authors wrote: \"... perform search over the generated subgoals using powerful search methods such as MCTS\". Recently there have also been approaches (e.g., [1][2]) proposed where learnable search could be useful for formal reasoning. Citations are missing. \n\n[1] Wu et al. 2021, TacticZero: Learning to Prove Theorems from Scratch with Deep Reinforcement Learning\n\n[2] Jonathan Laurent, André Platzer 2022, Learning to Find Proofs and Theorems by Learning to Refine Search Strategies: The Case of Loop Invariant Synthesis", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "caL6Hn8LioU", "reviewer": "Reviewer_AVNg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The manuscript cleverly combines the ability of:\n 1. theorem provers like Isabelle to accept `sorry` statements, in which unproved statements can be accepted as if true;\n 2. large language models to fill in masked text.\n\nIt proposes a 'draft, sketch and prove' methodology that draws on the large corpus of informal (human) mathematics, converting it into a formal proof sketch with a large language model.  This sketch is then used to guide an automated theorem prover.\n\nIf I understand correctly, the methodology can use of erroneous (informal) proof sketches to generate correct proofs, as ML techniques generally make use of noisy training data to generate correct classifications.\n\nThe methodology seems to expand the class of informal mathematical problems that can be formalized and formally solved.  \n\nAs the agenda seems ambitious and fruitful, I expect that it will lay the foundations for further advances, dropping the cost of mathematics, and extending the range of mathematical results for which we can establish proofs.", "summary_of_the_review": "To me, this paper seems to represent in generating mathematical proofs at lower cost. I can see it launching significant research projects (q.v. possible future work, above).", "strength_and_weaknesses": "**Strengths**\nSee above\n\n**Weaknesses**\n1. I would like to see existing SOTA results.\n1. if you could fit it, a plot of success v the number of steps in Appendix C would be nice.\n\n**Next steps I would like to see in future work**\n1. it would be particularly nice if DSP found new or 'better' proofs (akin to Newell, Shaw & Simon's Logic Theory Machine on Russell & Whitehead).\n1. I would like to see consideration of multiple proofs of the same result: Nipkow's 2009 JAR article formalized two of Geanakoplos' three proofs of Arrow's impossibility theorem, to explore how easy different proofs mode could be formalized.  (I would _love_ to see style transfer eventually: prove this result in the style of von Neumann, or Erdős.)\n1. Can the structure of proofs be better exploited?  For example, Hilbert-type proofs correspond to trees.  Isabelle-type proofs are more complex due to local assumptions.  (Was this the concluding reference to HyperTree?)\n1. Thomas Hales' had a 'formal abstracts' project a few years ago, in which he sought to formalize abstracts of mathematical papers, easing searches across notation and terminology.  Could DSP help?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%