ImProver: Agent-Based Automated Proof Optimization
Authors: Riyaz Ahuja
Jeremy Avigad
Prasad Tetali
Sean Welleck
Venue: ICLR 2025 Poster (2025)
Keywords: Automated Proof Optimization
Neural Theorem Proving
Formal Mathematics
Lean Theorem Prover
Proof Generation
Large Language Models
Symbolic Reasoning
Interactive Theorem Proving
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
TL;DR: ImProver optimizes formal mathematical proofs for arbitrary metrics using LLM agents, automatically improving proof readability and length in Lean as well as generalizing NTP.

Abstract: Large language models (LLMs) have been used to generate formal proofs of mathematical theorems in proofs assistants such as Lean.
However, we often want to optimize a formal proof with respect to various criteria, depending on its downstream use.
For example, we may want a proof to adhere to a certain style, be declaratively structured, or concise. Having suitably optimized proofs is also important for learning tasks, especially since human-written proofs may not optimal for that purpose.
To this end, we study a new problem of automated proof optimization: rewriting a proof so that it is correct and optimizes for an arbitrary criterion, such as length or declarativity.
As a first method for automated proof optimization, we present ImProver, a large-language-model agent that rewrites proofs to optimize arbitrary user-defined metrics in Lean.
We find that naively applying LLMs to proof optimization falls short, and we incorporate various improvements into ImProver, such as the use of symbolic Lean context in a novel Chain-of-States technique, as well as error-correction and retrieval. We test ImProver on rewriting real-world undergraduate, competition, and research-level mathematics theorems, finding that ImProver is capable of rewriting proofs so that they are substantially shorter and more declarative in structure.

Published as a conference paper at ICLR 2025
IMPROVER: AGENT-BASED AUTOMATED PROOF OPTIMIZATION
Riyaz Ahuja Jeremy Avigad
Prasad Tetali Sean Welleck
Carnegie Mellon University (r (riyaza, ptetali swe 1 lleck @andrew. cmu edu
ABSTRACT
Large language models (LLMs) have been used to generate formal proofs of mathematical theorems in proofs assistants such Lean. However, we often want to optimize a formal proof with respect to various criteria, depending on its downstream use. For example, we may want proof to adhere to a certain style, be declaratively structured, or concise, Having suitably optimized proofs is also important for learning tasks, especially since human-we wrrtten proofs may not optimal for that purpose. To this end, we study new problem of automated proof optimization: rewriting a proof so that it correct and optimizes for an arbitrary criterion, such as length or declarativity. As first method for automated proof optimization, we present ImProver, a large-languag--modee agent that rewrites proofs to optimize arbitrary user-defined metries in Lean. We find that naively applying LLMs to proof optimization falls short, and we incorporate various improvements into ImProver, such the of symbolic Lean context in novel Chain-of-States technique, as well as error-correction and retrieval. We test ImProver on rewriting real-world undergraduate, competition, and research-level mathematics theorems, finding that ImProver is capable of rewriting proofs so that they are substantially shorter and more declarative in structure.
INTRODUCTION
The fundamental virtue of a mathematical proof is that it provides certainty: deductive argument shows that the assumptions of a mathematical statement logically guarantee the conclusion. In practice, however, informal, latural-language proofs are prone to imprecision. ambiguity, and error. Using a formal language such as Lean (de Moura Ullrich, 2021) removes such ambiguity and imprecision and enables a proof assistant to verify correctness down the primitives of a formal axiomatic system.
Although any correct formal proofs of statement equally establish the validity of their conclusion, there are various criteria on which one of them may be preferred over another. When an expert formalizer finishes a proof, they always go back and revise it, aiming, for example, to improve readability and robustness. Instructors show their students how to shorten their proofs and structure them better, and the maintainers of Lean's Mathlib (mathlib Community, 2020) demand revisions to submissions to improve their robustness and adhere to style guidelines.
To this end, study a new problem of automated proof optimization: rewriting proof that is correct and optimizes a user- user-specified criterion such length or readability. To mathematicians and formalizers, the ability to improve proofs automatically invaluable to the maintenance and development of libraries for research and pedagogy alike. For example, the development of Mathlib as an evolving corpus maintained by hundreds of human formalizers requires strict guidelines to ensure efficient and generalized theorems a task that proof optimizers can excel at automating, in order to generate proofs that rely on existing lemmas with concision and generalizability.
Moreover, automated proof optimization is not only useful in its own right, but also for the purposes of improving Al that can find proof on its own. At the very least, it provides a form of data augmentation: the limited amount of formal training data is currently bottleneck for machine learning, and our methods provide ways generating additional data automatically. More interestingly. our methods also provide means of optimizing training data. For example, other work (Jiang al., 2023)

---

Published as a conference paper at ICLR 2025
suggests that promising means for generating formal proofs is to have LLM sketch a high-level outline of a proof that can be filled in by symbolic automated reasoning methods. For that purpose, useful to have a corpus of proofs that are written in such structured form. Our methods provide means of generating such proofs from less structured ones.
Our work shows that naively applying LLMs to proof optimization falls short, often resulting in incorrect or poorly optimized proofs. We develop various improvements that can be applied on top of black-box language model, including Chain-of-States prompting - an analogy to chain-of-thought prompting (Wei et al.. 2022) that shows intermediate proof states, contextual information, error- correction, and retrieval. We incorporate these into ImProver: large language model agent that rewrites proofs to optimize arbitrary user-defined metrics in Lean. We test ImProver on rewriting real-world undergraduate theorems, competition problems, and research-level mathematics, finding that ImPProve is capable of rewriting proofs so that they are substantially shorter and more declarative in style.'
Original (human-written)
ImProver (length-optimized)
Lemma 1emma0 [o: Sype) 1p : + a + Propł
Cemma
lemmač
Type]
+ prop)
(hi :
31 Y, x
(h1 : Y x, 3t y, y)
(h2 : V x y, pxx xxyy y
t pyP x1
(h2 : V yr P P
M, Clasaical .choose
x, welbssicoll.chaco.
(h1 (Claseical. choose (h1
(h1 IClassical..coom (NC
x) [b.exists)..xxiittee. :=
x) (eexxatst).exxsteeee
2800F START
PROOF START
intro
intro x
obeain (y, hie, hin) :- : h1 x
(y, hls, hlu) h1
have h2" Claseical.choog (h1 .exitts
h1u aassiccll.choom choossssppeccccceeoeeecoooooo spec _
:-
obtain (M, ble', hlu') ;- h1 y
hlu - (Clessictl.chooee__gg
"bl'' (th2 _ mpr hlei]
x) .exexists)
exact hlu' chhooeeep.ccoose_pps
Fw [h2']
cheain (s, hie', hlu') := hi y
have h4 :- Claastcal. wtw.selll.cocoesssssssssssss (h1 y) .exists
have hxw : x
by
apply hiu"
[1:2]
exact hic
[hxw] exact Elu" h4
Figure 1: Prover automatically rewrites formal proofs to optimize a criterion such length or readability while remaining correct. this example, Innrr optimizes a human-writter -writen lemma from the 2022 International Math Olympiad (Question 2, solution from Compfiles (David Renshaw, 2024)) for length. ImProver's optimized proof is correct and more concise.
2 RELATED WORK
Recently there has been wide interest in automating theorem proving in interactive proof assistants; see (Lu et al., 2023; Li al., 2024) for surveys. Indeed, a high level, proof assistants constitute sound verifier in a prover-veriffer game (Anil et al., 2021), suggesting that muchine-learning based prover that interfaces with such verifier is a natural next step for formal reasoning systems.
A typical approach to developing machine learning provers (Polu & Sutskever, 2020) is to train on a large corpus of mathematical proofs such as Lean's Mathlib (mathlib Community, 2020; Han et al., 2022; Polu et al., 2022b; Lample et al., 2022; Yang al., 2023; Hu et al., 2024). A model learns from the distribution of proofs in the corpus, such as Mathlib-style proofs. Recently, the AlphaProof (AlphaProof & Teams, 2024) system was shown produce proofs with arcane, non-hum hom-human structure and syntax. We consider the new problem of rewriting a proof to optimize a metric. such rewriting proof into more declarative more concise one. Proof optimization is more general than theorem proving, since we can also rewrite an empty proof to optimize correctness. Finally, there is rich literature the varied styles of (human) formal proofs (e.g., (Autexier & Dietrich, 2010; Wiedijk, 2004)). Our model, ImProver, builds on neural theorem proving techniques
Cooe available http::/ggghaaa.ccommmmyaaaaagnpp
2

---

Published as a conference paper at ICLR 2025
including full proof generation (Jiang al., 2023; First et al., 2023), conditioning example proofs (Jiang et al., 2023), retrieval (Yang et al., 2023; Thakur et al., 2024), and preceding file context (First et al., 2023; Hu et al., 2024), as well as eπror correction (Madaan et al., 2023; Chen et al., 2023) and documentation retrieval (Zhou et al., 2023) from code generation. ImProver brings these code generation techniques, along with new Chain-of-States prompting and meta-programmed contextual information, into a unified proof optimization agent.
AUTOMATED PROOF OPTIMIZATION WITH Im Irover
Given theorem statement z, additional context c, and initial proof you proof optimization consists of generating new proof that is correct and minimizes (or maximizes) a metric (1 c, yo, v) + I.
3.1 METRICS
By varying the metric, we can perform tasks such as shortening proofs, making them more declarative in structure, or even automated proving. We consider four metrics:
Length Metric: The length metric measures the number of tactic invocations in the tactic proof, aiming to reduce the proof's length while ensuring its correctness. Note that shorter proofs often represent more efficient proofs.
Declarative Metric: We aim to rewrite proofs to be written in a declarative style (Autexier & Dietrich, 2010; Wiedijk, 2004), which is related to the number of independent subproofs in a proof. Intuitively, this corresponds with a sense of structure for the proof, and can be interpreted as being more readable, explicit, or modular in style. Concretely, we evaluate declarativity using the ratio of number of explicitly typed have tactics to total number of tactic invocations.
Mixed Metric: We aim combine the length and declarative metrics described above generate proofs that are both concise and declarative. This is done by penalizing all tactics, and rewarding declarative tactics (e.g. have) in order amortize the net total. We then aim to maximize the net score. In practice, we assign a value of -1 to each tactic in the proof, and a value of +5 for declarative tacties, meaning that each declarative tactic "pays" for 4 additional tactics.
The completion of a proof simply describes its correctness. This is a trivial metric which measures the number of errors present. The completion metric is used for concretely viewing proof optimization as generalization of neural theorem proving.
Completion Metric:
Degenerate Solutions. Our goal here has been provide a flexible means to optimize proofs with respect to any metric that might prove useful. The particular metrics we use here are intentionally simplistic, in that they are used only to test and evaluate the method. The task of designing metrics that correspond more accurately to human criteria or are optimal for various training tasks is left to later work as what defines good metric are dependent on the use case.
Additionally, we note the possibility of degenerate solutions, as in, generations of proofs that score highly on a certain metric, while not corresponding to the intuitive sense of that metric. For example, overuse of have statements can greatly increase the declarativity of the proof, despite not being used the proof's deductive process whatsoever. It is undesirable for a model to generate such degenerate solutions, and to account for this, we guide the model with many human-written examples of each metric in question, rather than requiring it to solely maximize a reward function. For more complex, user-defined metrics, the possibilities for degenerate solutions only increases, and as such, guiding models using concrete examples as well as using reward models rather than reward functions to score metrics may mitigate the risks of such degenerate solutions.
3.2 IMPROVER
We develop several improvements that can be applied a black-box LLM generator yout G(- (raa). ). such as GPT-4 (OpenAl et al., 2024), and specify ImProver with respect to these parameters. The explicit prompts and templates that are sent the L.M can be found in ($A).
3

---

Published as a conference paper at ICLR 2025
Without Chain-of-States
With Chain-of-States
example : s n U.S. n & U =- by
exampie UiU.a S u
rintro ([xs, xt) (xs, xu))
rintro x ((x5, xt) (xs, xu)i
lett; exaact use 257 right? exact xu
case intro
Type
s u Set a
xt :E:EE
F E EEEnn (S
case inr.intro
Type
5 Set
x E
xu ::xE0
ExES U.
x2; left;
Goals Solved!
use xs1 right; exact xu
Goals Solved!
Figure A Lean proof (left) with Chain-of-States prompting annotations (right).
3.2.1 CHAIN-OF-STATEE PROMPTING
Typical formal proofs are sequence of tactics (akin to steps) and states that show the hypotheses and goals each step. The intermediate states often contain valuable information (e.g., an expression after it has been simplified) that is not present in the tactics. To allow the model to reason about these intermediate goals and hypotheses, we use tools from Lean metaprogramming to automatically annotate each proof state comment prior to each tactic. We refer to this method as Chain-of- States (CoS) prompting since makes intermediate states explicit, akin to how chain-of-thought prompting (Wei et al., 2022) makes intermediate steps of a solution explicit.
These states are extracted directly and symbolically from the underlying Lean compilation steps using Lean's 's rich metaprogramming suite. The implementation of this extraction system is modeled from the work (Kim Morrison, 2024). Specifically, in the compiler's elaboration and evaluation stages where the parsed theorem code is first converted into concrete syntax trees (in practice, Synt ax objects) and abstract syntax trees (Expr objects) we convert the CST and AST output objects into the relevant proof data and proof states in the form of proof trees (Lean Elab. InfoTree)) These proof trees contain detailed context and information on a tactic-by-tactic level relating to the modification of the proof state, metavariable context, and proof correctness.
After state extraction is completed and cached for efficient future access, we annotate the proof text itself to contain the intermediate states in the form as comments. Figure shows an example.
This explicit reasoning aims to help the generator model construct more optimized proofs via additional symbolic data.
3.2.2 OUTPUT FORMATTING.
LLM outputs often contain ancillary and syntactically invalid content, especially before and after the actual proof. Additionally, by applying additional structure to the LLM outputs, we may hope generate more structured proofs. To analyze this hypothesis, introduce two additional output formats in addition to the standard string output: string list and st string rre.. The former enforces the model output of proof to be tactic sequence represented list of strings, and the latter enforces proofs to be written as proof trees, represented as tree of strings.
3.2.3 SAMPLING METHOD
We also introduce different methods sampling between many (sequential or parallel) LLM inference calls, involving best-of-n and iterative refinement implementations, well combinations thereof.
4

---

Published as a conference paper at ICLR 2025
Best-of-n. The best-of-n technique generates multiple (n) calls to the language model and selects the "best" via a simple selection policy that first prioritizes output correctness, and secondly prioritizes the evaluated metric delta score.
Using temperature value 1, we ensure that our n calls to the model are diverse, as the temperature hyperparameter (ranging between 0 and 2) controls the randomness of the outputs. The default value ensures that outputs are sufficiently random without sacrificing accuracy and generating unpredictable behavior. Moreover, this allows for sufficient variance that the best-of-n scoring function has many distinct inputs to choose from.
More specifically, scoring function is given by the 2-ary comparison function S, whose arguments are output objects y. v/-
max(y, key: a + p(x)),
E(y) = Ely') =
E = 0, E(y') 0
S(y,D')=
y', mnin(y.2 y key: x - E(x)),
Ely) > 0, ((y))
E E >0
Where u(z) is the metric score of z, and E(x) is the number of errors in æ. This comparison function be extended to evaluate the best output of any finite via induction.
Error correction and Refinement. Inspired by self-debugging techniques code genera- tion (Madaan et al., 2023; Chen et al., 2023), ImProver identifies and corrects errors in the generated proofs by iteratively refining its outputs. The refinement process relies on user-defined parameters n and prev_nit specify the number of iterations and the number of previous iterations' data to forward, respectively. Each iteration carries information on the last prev_num iterations, including input, output, metric score, correctness, and error messages.
Combination Sampling and Compound Prompt Functions. Compound prompt functions utilize the curried nature of the back-end implementations of best-of-n and refinement nest these techniques within one another. For example:
best of ( (refinement, m) , n) a compound sampling method that run a best-of-n, where each call is m-step refinement.
ref inment ( (best_os _f____f__n____ m) n) a compound sampling method that runs n-step refine- ment, where each call is a best-of-m call to the LLM.
Note that with each of these compound prompt functions, there are always a total of mn iterations.
3.2.4 RETRIEVAL
ImProver uses MMR (Maximum Marginal Relevance)-based (Carbonell & Goldstein, 1998) retrieval- augmented generation to select relevant examples and documents. More specifically, for user- specified k. example retrieval selects the & most relevant examples of proof optimization on specific metric. additionally, document retrieval extracts information using MMR from a pair of fixed (vector) databases for the specified metric. The databases store syntactically chunked data from the Theorem Proving in Lean (TPiL) handbook containing syntax guides and tactic explanations and the Mathlib mathematics libary containing thousands of theorems and lemmas.
The Mathlib retriever finds the top l documents that score the highest MMR score against the current theorem, the TPiL. retriever finds the top i documents that score the highest MMR score against the current theorem in context and all current error messages. This retrieval process helps in generating more contextually accurate prompts that allow the language model to better correct its own errors as well as find useful lemmas to reference.
4 EXPERIMENTS
We test ImProver rewriting real-world undergraduate theorems, competition problems, and research-level mathematics and compare its results to those the base GPT-4o and GPT-4o-mini models. We examine the optimization capabilities of ImProver for the length and declarative metrics,
5

---

Published as a conference paper at ICLR 2025
studying the effectiveness in maintaining the correctness of the tactic proof while making it more concise as well as making it more declarative in style and structure.
4.1 SETUP
Our experimentation is split into three distinct stages. We first perform ablation testing on the ImProver model parameters ($3.2) to ensure that ImProver's parameter specification is the optimal one with respect to correctness and metric optimization score. We then evaluate this optimal parameter combination datasets of varying complexity and analyze the performance and results thereof. Lastly, we note the performance of ImProver NTP applications in comparison to the base GPT-40 and GPT-4o-mini models.
Datasets, We evaluate ImProver on subsets of the Mathematics in Lean (MIL) (leanprover- community, 2024), Compfiles (David Renshaw, 2024), and Mathlib (mathlib Community, 2020) datasets. Additionally, ablations are performed on subset of MIL, and theorem proving is bench- marked on various subsets of MIL as well as the MiniF2F (Zheng et al., 2022) dataset. Details of the datasets used in each experiment is included in appendix B.
Models. Our base generator uses GPT-4o (OpenAl et al., 2024) (gpt-44-2004-00-00)) Since no prior methods currently exist for automated proof optimization, we consider a prompted GPT- 4o without the improvements described in ($3.2) as our baseline. Additionally, the baseline and ImProver both receive a prompt containing instructions to optimize for the given metric, with the theorem statement, context, and initial proof. ImProver augments this prompt with the data from the improvements described in $3.2. Additional input information is detailed in appendix A.
Performance metrics. Since proof optimization is a new task, we define four performance metrics for measuring aspects of correctness and improvement.
100. For readability, we use the difference, /rradd (y) (y.) If no correct output is generated by the model for specifie theorem, improvement is defined to be zero. We define nonempty improvement the improvement restricted to theorems for which some output has nonzero improvement. Intuitively, improvement the expected improvement in metric score from the input output, accounting for errors in the generation. The nonempty improvement score is the expected improvement in metric score, given that there are no errors in the generation.
First, we define improvement for length percentage change in length, (Men (v)
Additionally, the accuracy is the percentage of theorems in the dataset which the model was able to generate a correct output for. The improved accuracy the percentage of theorems in the dataset which the model was able to generate a correct output for, as well as improve the metric to be nonzero.
4.1.1 ABLATION SETUP
When performing our ablation studies, we used fixed dataset (MIL; see appendix B. and metric (length) and varied the parameters of all the features to find the optimal combination. However, as there are over 8640 possible combinations, rather than test all combinations, evaluate using factorial testing method.
Testing Groups. We define the following testing groups with the specified parameter combinations:
GPT-4o-mini/GP-4:: This varies the GPT-4o model, outputting a string with no other features.
Output and CoS: We evaluate the effects of different output formatting styles (string, string 1ist, string tree) and CoS (True, False), with the model fixed as GPT-4o, with no other features enabled.
Example Retrieval: We evaluate the effects of increasing the number of examples provided (multi- shot prompting) in the range of 3, 3,5,7 7, and 10, with the model fixed as GPT-4o, CoS and output formatting fixed as the best combination from the previous test, and no other features enabled.
Sampling Method: Here, Additionally we test on the refinement cases forwarding the most recent iteration result, or all previous iteration results is the best, and if we should keep the best out of the iterations, or the most
evaluate the effects of best-of-n and refinement for fixed
5.

---

Published as a conference paper at ICLR 2025
Table 1: Average Proof optimization results.
Metric
Model
Improvement
Nonempty Improvement
Accuracy
Improved Acc.
GPT-4o
3.7
15.15
26.36%
8.31%
Length
ImPProver
20.96
55.29
100.0%
35.44 %
GPT-4o
2.21
8.02
18.75%
6.13 % 24.56%
Declarativity
ImProver
9.34
30.53
100.0%
GPT-4o
3.51
23.90
14.70%
5.11%
Mixed
ImProver
27.31
39.24
100.0%
30.55
Table 2: MII. Proof optimization results.
Metric
Model
Improvement
Nonempty Improvement
Accuracy
Improved Acc.
GPT-4o
6.25
18.58
37.5%
14.42% 50.0% %
Length
ImProver
30.54
56.56
100.0%
GPT-4o
4.18
14.48
28.85%
11.54%
Declarativity
ImProver
13.45
30.97
100.0%
34.21 %
GPT-4o
3.70
27.38
13.51%
0.0% 45.94%
Mixed
ImProver
43.55
44.76
100.0%
recent. The model is fixed as GPT-4o, CoS, output formatting, and examples are fixed as the best combination from the previous test, and no other features enabled.
and Model: Here, evaluate the effects of larger values and different models. We test n = 3,5, 5, 7, 10, 15 on GPT-4o and GPT-4o-mini, as well as n = 20 for GPT-4o-mini (as is of a far lower token cost). CoS, output formatting, examples, and sampling method are fixed as the best combination from the previous test, and no other features enabled.
Combos and RAG: We evaluate combination methods refinement (best_of of__ m) and best_of_ m
(m) ), for m * m' with mmn' equal to the optimal value m from the previous test. We also test the effect of enabling document retrieval. Model, CoS, output formatting, examples, n, and sampling method are fixed as the best combination from the previous test.
Selection. For each testing group, select the best parameter combination- which is then held as constant for the testing of all future testing groups - based on the combination that has the maximal improvement score. This improvement score represents the expected improvement in metric score, accounting for possible errors in the generation; selecting the parameter combination with the highest such score allows for rewarding both generation accuracy and large improvements in the metric score.
Comparing this with the other three performance metrics, accuracy is not prefered as a selection heuristic, as by simply returning the initial input, we can get 100% accuracy. Improved accuracy accounts for this by only counting theorems that has some positive improvement in metric score in the calculation, but this does not reward larger improvements to metric score any differently than smaller ones. Conversely, nonempty improvement ignores incorrect generations, it is also not preferable for selection. The improvement score accounts for all this, rewarding correct generations and discouraging incorrect ones, and placing a higher weight to larger improvements in metric score.
Ablation datasets. We evaluate our ablations on subset of MIL as detailed in appendix B.
4.2 RESULTS
Im is capable of optimizing proofs in all settings. From Table 2, Table 3, and Table 4, we can see that ImProver is capable of optimizing proofs on all datasets for both the length and declarative metrics, well as the mixed metric. Furthermore, Table shows that across all metrics, significantly outperforms GPT-4o on proof optimization tasks on every experimental measure that
aggregated from all datasets. Additionally, from Table 2, Table 3, and Table 4, ImProver outperforms GPT-4o on each dataset as well. We proceed to analyze this data and its implications.
7

---

Published as a conference paper at ICLR 2025
Table 3: Compfiles Proof optimization results.
Metric
Model
Improvement
Nonempty Improvement
Accuracy
Improved Acc.
GPT-4o
2.75
30.7
11.54%
5.13%
Length
ImProver
18.86
54.48
100,0%
34.62 %
GPT-4o
0.39
3.38
14.1%
1.28%
Declarativity
ImProver
5.74
24.89
100,0%
19.23%
GPT-4o
3.96
3.96
26.9%
20.0%
Mixed
ImProver
20.60
76.53
100.0% %
23.07 %
Table 4: Mathlib Proof optimization results.
Metric
Model
Improvement
Nonempty Improvement
Accuracy
Improved Acc.
GPT-4o
0.0
0.0
16.67%
0.0%
Length
ImProver
6.19
53.65
100.0%
11.54 %
GPT-4o
0.0
0.0
4.65%
0.0%
Declarativity
ImProver
4.63
33.19
100.0%
11.63% %
GPT-4o
2.92
30.14
9.30%
4.65%
Mixed
ImProver
4.16
7.45
100.0%
9.30%
Length optimization. First focusing on the length metric, we that ImProver outperforms GPT-4o with respect to the improvement score by 566% (aggregated over all datasets). Additionally, we are guaranteed that ImProver produces correct output, although that output may just be the same the input. However, 35.44% the time, it generates a correct output that is not the same length as the input, and in that case, expect average of 55.29% reduction in length. Comparing this with GPT-40, we conclude that not only can ImProver optimize at a higher level on arbitrary theorems, but its ability generate nontrivial correct outputs far greater in comparison to GPT-4o.
Declarativity optimization. Declarativity optimization is similar, with ImP ImPvre outperforming GPT-4o by 423%. Moreover, the accuracy, improved accuracy, and nonempty improvement disparities for declarativity parallel those of the length tests. However, it should be noted that for both GPT-4o and ImProver, the accuracy and improved accuracy scores were markedly smaller for declarativity than length optimization. This suggests that for both models, it was generally more "difficult" to generate a correct output, and moreover, generate correct output with better metric score than the input, for declarativity optimization than length optimization. In other words, optimizing for declarativity is more difficult for the underlying generator than optimizing for length. However, we speculate with higher-quality prompts and metrics, this disparity can be minimized. Regardless, note that different metrics can be less likely to be correctly optimized, and that model performance is correlated with the metric it seeks to optimize, both for GPT-4o and ImProver.
Mixed optimization. For the mixed optimization of both length and declarativity, we observe a 778% outperformance by ImProver in the aggregate, with similar increases across all experimental measures. is notable that the combined improvements and accuracies mirror the trends from the individual length and declarativity metries, suggesting that ImProver able scale its optimizations to align with the increased complexity of the metric. Moreover, this empirically shows that for more complex and urbitrarily-define metrics, ImProver maintains its ability to generate nontrivial optimizations, given sufficiently high-que high-quality examples, prompts, and scoring functions.
Optimization varies based on dataset difficulty. Additionally noting Table 2, Table 3, and Table we observe that the improvement score for all metrics for both GPT-4o and ImProver is highest for the MII. dataset, lower for Compfiles, and the lowest on the Mathlib theorems. This suggests that the expected improvement in metric score decreases with higher difficultly, with undergraduate- theorems having a significantly higher expected improvement than research-level theorems. However, it should be noted that for all metrics, the nonempty improvement of ImProvee stayed somewhat consistent, whereas for GPT-4o, it followed the aforementioned trend of decreasing with difficulty. Similarly, the accuracy and improved accuracy scores for both metrics and models decreased with higher difficulty datasets (disregarding ImProver's accuracy scores, as they are ensured to 100%). This suggests that although the base GPT-4o generator is less likely to generate correct output for
8

---

Published as a conference paper at ICLR 2025
higher difficulty datasets, the improvements that ImProver makes to the base generator allows it to maintain its improvement in the metric score whenever a correct output is generated. As such, can speculate that the bottleneck in the improvement score is not the model's ability to optimize the proof for a metric, but rather its ability to generate a new correct proof at all. As such, we conjecture that with more capable generator models, the accuracy and thus, the improvement score in optimization tasks will continue to increase, until the improvement scores match the nonempty improvement.
Overall, we conclude that although the performance of both ImProver and GPT-4o decreases on length and declarativity optimization on more difficult datasets, ImProver significantly outperforms GPT-4o on all datasets for length, declarativity, and mixed optimization.
4.2. 1
ABLATION TESTING
Table 5: Ablation results. Each cell in the ablation tests shows best / worst, which are the best and worst parameter combinations in the test group.
Improvement
Nonempty Improve.
Accuracy
Improved Acc.
GPT-4o-mini
0
0
3.62%
0%
GPT-4o
7.03
19.67
35.77%
15.33%
+ Output and CoS
6.04/6.3)
12.38 / 14.17
64.96%
44.53%
21.17% 16.06%
+ Example Retrieval
9.34
14.7 / 8.44
63.5% / 67.15%
21.9% / 16.79%
+ Sampling Method
15.35 99.3
18.44 / 14.7
83.21 % 63.5%
36.5% / 21 21.9%
and Model
23.51 3.65
26.28 4.66
89.47% 78.95%
45.61 % 8.77%
+ Combos and RAG
34.88/ / 28.25
57.56 33.48
60.61% 84.38%
54.55% 53.12%
ImProver
34.88
57.56
100 %
54.55
We perform ablation studies using a subset of the MIL dataset as discussed in $4.1.1. The results of this factorial study are aggregated in Table 5. We measure the baseline results from the GPT- 4o and GPT--o-mini models, noting that GPT-4o is the better-scoring model (with respect to the improvement score). Thus, fixing this model, we vary the output formatting type and if CoS enabled, and determine that outputting s string Fixing these parameters, we now vary the number of examples retrieved, noting that prompting with 10 examples maximizes the improvement score. Fixing this parameter, we vary the sampling methods (excluding compound methods and fixing n = 5) and observe that best-of-n is the best parameter combination. Now, GPT-4o-mini is significantly less computationally expensive than its GPT--4o counterpart, we test both models with the sample method fixed to best-of-n, and vary 1,3, 5, 7, 10, 15, and for GPT--4-mini, also 20. We conclude that GPT--4o with n 15 is the most effective. Fixing these parameters, we consider all mixed compound sampling methods with and without document retrieval enabled, concluding that 5-step refinement with best-of-3 on each iteration, with RAG enabled, is the optimal combination.
list with CoS enabled maximizes the improvement score.
Thus, we can see from Table the optimal parameter combination comes from gpt-4o outputting as a striing list with CoS, RAG, 10 examples, 5-step refinement with each iteration being best-of-3 evaluation. Changing any one of these parameters them leads to a reduction in performance. Additional ablation data can be found at ($B.2).
Declarativity and Chain-of-States (CoS) Ablation. We additionally examine the effects of dis- abling CoS on declarativity optimization tasks, as we speculate that CoS has a high impact on the performance of declarativity optimization tasks, as the proof states that are embedded due to CoS seem to be critical aspect to generating the explicit declarations that the declarative metric measures.
We confirm this result by considering Table and observe that enabling CoS nearly doubles the improvement score, and significantly improves the nonempty improvement score, suggesting that CoS has a large impact on optimizing for the declarative metric, as conjectured. However, we also note a significant increase in improved accuracy, which suggests that embedding the chain of states also improves the ability of the model to generate nontrivial correct outputs, implying that the symbolic information contained in the states critical effectively making proof more declarative.
Syntax Guidance Ablation. We examine the effects of syntax guidance on ImProver's performance. To test. this we consider a subset of MIL. (B. 1), and optimize for length with and without error

---

Published as a conference paper at ICLR 2025
Table 6: CoS Declarativity Ablation results.
Improvement
Nonempty Improve.
Accuracy
Improved Acc.
GPT-4o
4.97
15.89
37.5%
12.5%
ImProver, CoS Disabled
9.23
24.61
100.0%
28. 18%
ImProver
16.69
31.42
100.0% %
46.88 %
Table 7: Syntax Guidance Ablation results.
Improvement
Nonempty Improve.
Accuracy
Improved Acc.
GPT-4o
11.00
25.94 49.97
42.42%
21.21% %
ImProver, No Syntax Guidance ImProver
23.42
100.0%
46.88%
28.94
48.74
100.0%
59.38 %
message forwarding. Considering the results of this ablation in Table 7, observe that without syntax guidance and error forwarding, the ability of the model to improve the metric score is approximately unchanged, but there is significant 13% spike in improved accuracy. This signifies that the syntax guidance improves the model's 's ability to generate correct results as is expected but does not improve the model's ability optimize proofs assuming correct generations. This ensures that the large improvement in performance compared to GPT-4o is not solely due to simple syntax guidance, but moreso caused by improvements like CoS, example retrieval, retrieval,
4.2.2 NEURAL THEOREM PROVING EVALUATION
Table 8: Proof generation results. Each cell shows percent accuracy.
MIL-C04 Pass@ 15
MIL-C08 @5
MIL Pass@ 15
Minif2F-test Pass@8
GPT-4o
18.18%
25%
21.73%
9.02%
ImProver
45.45%
33.33%
39.13%
16.39%
Lean Expert Iteration
34.5
We evaluate Im ImPvere''s neural theorem proving (NTP) performance using the completion metric on subset from MIL with empty input proofs 1).Tle 8 shows the accuracy on the dataset split by topie for both ImProver and GPT-4o. ImProver substantially outperforms GPT-4o across all datasets. Thus, proof optimization systems do indeed generalize NTP systems.
Additionally, we note that specialized neural theorem proving models such as GPT-f (Zheng et al., 2022) and Lean Expert Iteration (Polu et al., 2022a) outperform ImProver, but as they are specially trained on a large corpus of Lean code (whereas ImProver an extension of GPT-4o), as well as designed for theorem proving rather than proof optimization, it is worthwhile for future works to consider fine-tuning or specializing ImProver's methodology specifically for theorem proving. We reiterate that the purpose of this experiment is to empirically prove that proof optimization systems like Prover do indeed generalize the problem of theorem proving as claimed in $3.1.
CONCLUSION
In this paper, we introduced ImProver, a novel agent-based tool for automated proof optimization Lean. By incorporating CoS, RAG, and other features, ImProver significantly outperforms base language models in proof optimization over undergraduate, competition, and research-level problems.
However, ImProver is limited by its high cost, which is exacerbated by its reliance on proprietary LLM's. In future work, we will apply SFT and RL on smaller model to match performance locally.
ImProver demonstrates its ability to generate substantially shorter and more declarative proofs while maintaining correctness. As such, we believe that ImProver sets the stage for further work on proof optimization to advance the study and use of AI in mathematics.
ACKNOWLEDGEMENTS
We thank the L3 Lab, Hoskinson Center for Formal Mathematics, Convergent Research, Lean FRO, and the OpenAl Researcher Access Program for their support.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
AlphaProof and AlphaGiemmetry Teams. Al achieves silver-medal standard solving interna- tional mathematical olympiad problems. https://deepmind. google ccover/blog/ ai ai-soll solves imo problems- at silver- 2024.
Cem Anil, Guodong Zhang. Yuhuai Wu, and Roger Grosse. Learning to give checkable answers with prover-verifier games, 2021. URL htwpt:tttps......
12099.
Serge Autexier and Dominik Dietrich. A tactic language for declarative proofs. Matt Kaufmann and Lawrence C. Paulson (eds.), Interactive Theorem Proving, pp. 99-114, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
Jaime Carbonell and Jade Goldstein. The use of mmr, diversity- basedd reranking for reordering documents and producing summaries. In Proceedings the 21 Anmual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '98, pp. 335-336, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 1581 1 30155.. doi: 10.1 10.1145/290941. 291025. URL. https:/ /tt.////oii///o/ 1ttp///..11//9992210
025.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou, Teaching large language models to self-debug. 2023. URL https://arriv..or//aabs////
05128.
David Renshaw. compfiles. https: http://....com/www/w/...//.a comp les, 2024.
com
Leonardo de Moura and Sebastian Ullrich. The lean theorem prover and programming language. In Automated Deduction CADE 28: 28th International Conference Automated Deduction, Virtual Event, July 12-15, 2021, Proceedings, pp. 625-635, Berlin, Heidelberg, 2021. Springer- Verlag. ISBN 378-3-030-79885-- doi: 10. 10000007----0000-700000 10.100710 / 978- - 70- 51776-55333 5_37.
URL http::// /ttp:////oooooo org/
Emily First, Markus N. Rabe, Talia Ringer, and Yuriy Brun. Baldur: Whole-proof generation and repair with large language models, 2023.
Jesse Michael Han, Jason Rute, Yuhuai Wu, Edward Ayers, and Stanislas Polu. Proof artifact co- training for theorem proving with language models. In International Conference on Learning Representations, 2022. URL https: / /ppnreview net forumoodrruppoo 2
Jiewen Hu, Thomas Zhu, and Sean Welleck. minictx: Neural theorem proving with 2024. URL https: / www.aaxivvvvvo..../...aa
wwwp:iiv.oor/oooooooooooo org.oorg///oo.oooo abs 2400/40000000 03350.
Albert Qiaochu Jiang, Sean Welleck, Jin Peng Zhou, Timothee Lacroix, Jiacheng Liu, Wenda Li, Mateja Jamnik, Guillaume Lample, and Yuhuai Wu. Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. In The Eleventh International Conference Learning Representations, 2023. URL https: /ttll::///ppeeeeeeeeeeeeeeeee www.wewwwwwww..eeneeeeeeeee.eeee MEAVvMMM........CCCC....
Kim
Morrison.
lean-training-date
lean-training-dat. 2024.
Guillaume Lample, Timothee Lacroix, Marie anne Lachaux, Aurelien Rodriguez, Amaury Hayat, Thibaut Lavril, Gabriel Ebner, and Xavier Martinet. Hypertree proof search for neural theorem proving. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL httpt: / http:////////eeeeee.ee.e. net wtw.rrrooiwweeeeooounnn.. forum? 1d=J4px808cxHH
leanprover.community
mathematics lean. leanprover-commen wtaeenittttttttttt http://atttmtiiiccmoo in__einnnnn 2024.
https://github.coo
Zhaoyu Li, Jialiang Sun, Logan Murphy, Qidong Su, Zenan Li, Xian Zhang, Kaiyu Yang, and Xujie Si. survey on deep learning for theorem proving, 2024.
Pan Lu, Liang Qiu, Wenhao Yu, Sean Welleck, and Kai-Wei Chang. A survey of deep learning for mathematical reasoning. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 6lst Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 14605-144 14631, Toronto, Canada, July 2023. Association for Computational
11

---

Published as a conference paper at ICLR 2025
Linguistics. doi: 10.18653/w1122233al-oonng URL https://aclaatthhoooyyyoo 2023. 1oc1--oph acl-long...............ocooolm 817.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with eeffbece In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https::/tttceccc. /tttp:://operrvtti ew. nett rumm? d= 7h0erQLB.
The mathlib Community. The lean mathematical library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, POPL '20. ACM, January 2020. doi: 10.1 10,11453337288333338822 URL http: / /t/p//xdooo////o//oo org 1 0. 1 141115/55 /35/333728555 3373824.
OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, 1ige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapine Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-I.uisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carcy, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang. Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-opess, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo. Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang. Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Lukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger. Vishal Kuo, Michael Lampe, Ikai Lan. Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski. Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reicchir Nakano, Rajeev Nayak, Arvind Neelakantan. Richard Ngo Hyeonwoo Noh, Long Ouyang, Cullen O' Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng. Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong. Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song. Natalie Staudacher. Felipe Petroski Such. Natalic Summers, Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian. Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss. Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojeiech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. Gpt-4 technical report, 2024. URL https: / / rxiv. wrg//bos 2203 2303.08774. 08774.
12

---

Published as a conference paper at ICLR 2025
Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving, 2020.
Stanislas Polu, Jesse Michael Han, Kunhao Zheng, Mantas Baksys, Igor Babuschkin, and Ilya Sutskever. Formal mathematics statement curriculum learning. CoRR, abs/2202.01344, 2022a. URL hwtphttt/////m /ttp///aavvvv.iiia/aii org/ abs/ 01344.
Stanislas Polu, Jesse Michael Han, Kunhao Zheng, Mantas Baksys, Igor Babuschkin, and Ilya Sutskever. Formal mathematics statement curriculum learning, 2022b.
Amitayush Thakur, George Tsoukalas, Yeming Wen, Jimmy Xin, and Swarat Chaudhuri. An in-context learning agent for formal theorem-proving. 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Lc, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: /wwp//eveeeeeeeeeeeeeeeeeeeeeeee net forum? id=_vjolMesB_d.
Freek Wiedijk. Formal proof sketches. In Stefano Berardi, Mario Coppo, and Ferruccio Damiani (cds.), Types for Proofs and Programs, pp. 378-393, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. ISBN 178-3-540-24849-1.
Kaiyu Yang, Aidan Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan Prenger, and Anima Anandkumar. LeanDojo: Theorem proving with retrieval-augmenned language models. In Neural Information Processing Systems (NeurIPS), 2023.
Kunhao Zheng, Jesse Michael Han, and Stanislas Polu. minif2f: cross-systend benchmark for formal olympiad-level mathematics. In International Conference on Learning Representations, 2022. URL https::tp.........p....tt / openreview. net. formm?i httee/oorumm..dePPPPPPFree d=w.aegFFPPPPP.FFF.....
Shuyan Zhou, Uri Alon, Frank F. Xu, Zhengbao Jiang, and Graham Neubig. Doeprompting: Gen- erating code by retrieving the docs. In The Eleventh International Conference on Learning Representations, 2023. URL https: httpas//////e/ee//eeeeeeee f
13

---

Published as a conference paper at ICLR 2025
A PROMPTS
In this appendix, we note the prompts used by ImProver both for general LLM prompting, as well as the metric-specific prompts.
A.1 TEMPLATE
For the main prompt sent to the LLM on each sample, we build prompt string using chat prompt template that is then invoked runtime fill in the variables.
Namely, these variables include the set of metric prompts, previous results, input theorem, context, syntax documents, Mathlib documents, and examples.
The prompt template is a conversation of the format:
Placeholder: All metric prompis with a 'System' role
System: You will be given the proof context (i.e. the lean file contents/imports leading up to the theorem declaration) wrapped by <CONTEX>>.</CONTEET
You will be given the previous num_prev input/output pairs as well as their metric (met- ric.name) score and correctness score, as well as any error messages, for your reference to improve upon. Each of these previous results will be wrapped with <PREV I=0></PREV 1=0>...<<RREV (attum_prev-/>/iieee recent result.
I=numm ppev-l>__e with L-num_ppevv' being the most
Remember use lean syntax, which has significant changes from the lean 3 syntax. To assist with the syntax relating to the current theorem and current error messages, you will be given num suntsyntax_ docs documents refer to for fixing these syntax issues. Each of these documents will be wrapped with <SYNTAX
DOC>.
You will also receive mattmmihhlibba_a docs documents relevant to the current theorem to help with formulating your modified proof. Each of these will be wrapped with <CON- TENT DOCG..</CONTENT DOC>>
You will also receive num num__xamppp examples examples of input-output pairs of proofs that were optimized for the metric metric. Each of these will be wrapped with <EXAM- T.F.....EEXAPII.E.
You will be given the tactic states as comments for reference. The current theorem will be wrapped in &CURREND.../CURRENT
System: Output format instructions
Placeholder: All retrieved syntax documentation
Placeholder: All retrieved mathlib documentation
Placeholder: All retrieved examples
User: <CONTEXT> context </CONTEXT>
Placeholder: Previous results and inputs/outputs
Placeholder: All metric prompts with a 'User' role
User: <CURRENT> theorem </CURRENT>
This prompt is then invoked and sent to the language model by filling in all the variables and placeholders. Notably, when we invoke the chain given invocation with randomized exponential rate limit throttling to account for API rate limits, especially requests like when benchmarking over a large number of theorems.
we throttle the
A.2 METRIC PROMPTS
Length Metric
System: You AI assistant who shortens Lean 4 proofs while ensuring their correctness. You will aim to reduce the number of lines of the tactic proof while ensuring that it properly compiles in Lean 4.
14

---

Published as a conference paper at ICLR 2025
User: Shorten the current theorem (wrapped in SIDEENTS../CCRRENTT> be as short in length-meastune measured in the number of lines the proof as possible, while also ensuring that the output is still syntactically correct."
Declarativity Metric
System: You AI assistant who rewrites Lean 4 proof's to be more readable while ensuring their correctness. We measure readablity by considering the ratio the number of explicitly typed have tactics against the total number of tactics in the proof, this is proportional to whether a proof is declarative in style, and thus, readable.
User: Rewrite the current theorem (wrapped in <CURRENT> </CURRENT>) so is more readable and declarative and modular.
Mixed Metric
You are an AI assistant who rewrites Lean 4 proofs to be higher quality, namely, more concise and more readatie/declaratiiee style and structure. We measure the length of proof by the number of tactics, and readability/decllaattiiy by the number of explicitly typed have tactics.
System:
User: Rewrite the current theorem (wrapped in more readable and declarative and concise, while also being correct. Namely, we penalize point for every lactic, and reward 5 points for every declarative tactic (namely, have statements). Your goal is to maximize that reward function much as possible while generating a correct proof using the provided template as a starting point.
so is
Completion Metric
System:
You are an Al assistant who automatically solves Lean proofs (as generates the tactic proof) and ensures its correctness. You will receive a Lean 4 proof you must modify to eliminate any errors so that compiles correctly and eliminate any "sorry"s with full proofs.
User: Rewrite the current theorem (wrapped in ACURRENTS..&CCURRETT formal, complete, and correct Lean proof by filling in its tactic proof.
so is
A.3 METRIC EXAMPLES
In this section, we illustrate side-by-side examples of metric optimization. These examples are part of larger set of examples provided the model as described in $A.11
Length Metric As shown in Figure 3, we provide the model an example of using more advanced tactics like rintro and inlining apply statements to shorten the proof from tactics
Suboptimal
Length Optimized
example (P Q)
R:
by
exemple : (# + 4) A. + 80 rintro (ghpq, her)1 hp hgr thpq hp)
intro E.p
roases with (a,b)
apply b
apply =
p
Figure A human-written example of length optimization.
Declarative Metric
As shown in Figure 4, provide the model example of adding intermediate result hp_ ua__ng with an explicitly written type of P + -0. Additionally, we show the model an example of simplifying tactics and exteral lemmas and dependencies to solve the problem in direct, declarative, and readable manner.
Mixed Metric
15

---

Published as a conference paper at ICLR 2025
Suboptimal
Declarativity Optimized
example (h : = Q1) - push_neg exact not_or_offing
by
excmple (h A Q01 P
have me_ng
intre
exact (P.
hp:P
right
exact hp_ng hp
left
exact hp
Figure 4: A human-writter example of declarativity optimization.
As shown in Figure 5, we provide the model an example of adding multiple intermediate results as well as using proof terms and structural modifications to shorten the number of tactics, resulting in more optimized proof.
We note that although the "Suboptimal" example is taken from MII. CO4, it is ensured to not be in our testing split to avoid data contamination.
Suboptimal
Joint Length/Readabiliyy Optimized
example : Attutss (
exemple tttts= ( (
by
by
ext constructor
ext
sintro ((xs, xnt) (xt, xas))
constructor
construstor
in_union_mat_
XEaUt
left
a x to U. (s =- by intro exact (hx, hnx)
rintro (rr xL)
contradiction
have in_diff_unte folfffuuionnno : Y 1x VXE
constructor
a) x (s USU)) t) (a
right
sintro x ((x8, xnt) (xt, xnz)]
in_onion_natt_nn tEun (, ht) - xat hLF
(Or.in1
rintro (xS, contradiction
exazt in_umicn_aot
(Ur.ing
zintro (xs | xt, nxet) left
ifun (hs, _) => xns hs)
exact in_diff_union
use
have ia_diff_or
Y KEXEUUUVA
intro xt
t) + (x É = sintro (ax, hax)
V VxEElE
apply constructor <p> sasurption
by_eases xs
right;
left; exact (xs,
(xs, bt))
apply nxst
right; exact reaolve xs, fun ha => hnx (ha, Fx. re.oveelvellets xs)) exact in_diff_or
constructor <p> assumption
Figure 5: A human-written example of mixed length/declarativvtt optimization optimization.
Completion Metric
As shown Figure 6, we provide the model an example showing property about Set's, 's, an externally defined datastructure, using simple tacties and forward reasoning. without external lemmas.
Suboptimal
Completion Optimized
example (a: Types; 1m by sorry
Set at
example
Typa+1
= by
constructer
intra
rcases with (hs,_)
exact
intro constructor
exect
exact h
Figure 6: A human-written example of proof completion.
16

---

Published as a conference paper at ICLR 2025
B ADDITIONAL EXPERIMENTAL RESULTS
In this section, we provide more detailed information on the experimental setup and results used to evaluate ImProver.
B.1 DATASET DETAILS
Main Datasets We evaluate our experiments on subsets of the following datasets:
Mathematics in Lean (MIL) (leapprove-commuiityy 2024): this dataset contains pedagogical solutions of common undergraduate--evet exercises, and as such contains many declarative, yet verbose and inefficient proofs. We use exercise solutions from set theory, elementary number theory, group theory, topology, differential calculus, and integration & measure theory. This dataset contains theorems at an undergraduate--evel of complexity. For our main results, we evaluated on 72 theorems from exercise solutions from MIL chapters 4, 5,5,5 8,9, and 10.
Compfiles (David Renshaw, 2024): Solutions of International Mathematics Olympiad (IMO) and American Mathematics Olympiad (USAMO) competition problems from 2016 to 2024. This is dataset of eetematiinnall--enowiiie
competitive math problems, many which are readable and declarative, yet quite verbose. This dataset contains theorems of competitive format, and although they contain concepts only at a high-school level, the logical complexity of internationally-reoowiii competition results far above that. For our main results, used all 26 theorems and lemmas from the Compfiles database of complete solutions to the International Mathematics Olympiad (IMO) and the American Mathematics Olympiad (USAMO) from 2016-2024.
Mathlib (mathlib Community, 2020): Mathlib contains many advanced results at the forefront of mathematics, and has been the center of research-leve' formalizations. These proofs are concise and generalized which often comes at the cost of readability, declarativity, and understandability. These results and theorems often are the cutting edge of research and highest level of complexity compared the the other two datasets.
For our main results, we evaluated our methods on 43 advanced research-level proofs from Math1 i /b/ll gebrai Sebraiccopoloo ogy wwwggyy//mmmmmetttaa Grouppiid This is the most difficult dataset.
Ablation Datasets
We evaluate our ablations on a subset of MIL. Additional details on this subset is included in appendix B. However, due to the increase in model calls for larger values, we switch a representative sample of this subset for some test groups. Namely,
GPT-4o-mini, GPT-4o, Output and Cos, Example Retrieval, and Sampling Method are tested on the 133 theorems in the solutions of c03_Logic, c04_Setssand aand_Funnttinnsss and C05 www.eeeetarrnuulllaalla
and Model are tested on 55 theorems from representative sample of the aforementioned, and Combos and RAG are tested on a representative sample of 32 theorems from the aforementioned.
Additionally, we note that both the Declarativity/CoS ablation and the Syntax Guidance ablation are performed on the same 32 theorems sample as mentioned above.
Completion Datasets
We initially evaluate our completion/NTP dataset on 23 exercises from Mathematics in Lean. Namely, we consider a representative sample of 12 exercises in group theory (Chapter 8; denoted "MIL-C08", done at 15 samples), 11 exercises in set theory (Chapter 4; denoted "MIL-CO4", done at 15 samples). Moreover, ensure that all these theorems have empty proof.
Additionally, we evaluate on the MiniF2F-test (Zheng et al., 2022) dataset with 8 samples (where ImPoover runs the samples as 2 refinement steps of best-of-4 call each).
This experiment is intended to be an initial evaluation to show that automated proof optimization systems can generalize neural theorem proving, however, future work will explore the effects of policy optimization and fine-tume mee-tuning of ImProver's methodology to perform neural theorem proving more competitively against specialized NTP models.
17

---

Published as a conference paper at ICLR 2025
B.2 ABLATION DETAILS
We now proceed to show detailed results from our ablation testing.
Table 9: Output and Chain-of of-States Ablations
Output Format
CoS
Improvement
Nonempty Improve.
Accuracy
Improved Ace.
string
True
7.53
16.12
46.72%
16.79%
string
False
7.03
19.67
35.77%
15.33%
string 1ist
True
8.04
12.38
64.96%
21.17% %
string 1ist
False
7.04
13.58
51.82%
18.98%
string tree
True
7.62
15.34
49.64%
18.25%
string tree
False
6.31
14.17
44.53%
16.06%
By Table 9, we see that the optimal combination in this testing group is string list output format with CoS enabled. Fix these values for all future tests.
Table 10: Example Retrieval Ablations
Examples
Improvement
Nonempty Improve.
Accuracy
Improved Acc.
0
5.67
8.44
67.15%
16.79%
3
8.49
13.68
62.04%
19.71% %
5
8.38
12.9
64.96%
21.17%
7
7.56
12.04
62.77%
19.71%
10
9.34
14.7
63.5%
21.9%
With the previous optimal parameters fixed, run the ablation on the number of examples. By Table 10, we see that the optimal combination in this testing group is 10 examples. Fix this value for all future tests.
Table 11: Sampling Method Ablations
Method
Forward
Keep Best
Improvement
Nonempty Improve.
Accuracy
Improved Acc.
None
N/A
N/A
9.34
14.7
63.5%
21.9%
refinement
False
14.76
30.63
48.18%
30.66%
refinement
5
False
12.5
20.88
59.85%
30.66%
refinement
True
14.95
14,95
100.0%
30.66%
refinement
5
True
13.15
13.15
100.0%
29.93%
best-of-n
N/A
N/A
15.35
18.44
83.21
36.5%
Note that forward and keep-best values are parameters for refinement of how many previous iterations to forward, and whether to keep the most recent or the best iteration in subsequent refinement steps.
Now, with the previous optimal parameters fixed, run the ablation on the sample method. By Table 11, see that the optimal combination in this testing group is best-of-n. Fix this value for all future tests.
With the previous optimal parameters fixed, the ablation the value of and model. By Table 12, we see that the optimal combination in this testing group is GPT-4o with n = 15. Fix this value for all future tests.
With the previous optimal parameters fixed, run the ablation on the combination methods and RAG is enabled. By Table 13, that the optimal combination in this testing group is 5-step refinement with each iteration being best-of-3 call, with RAG enabled.
B.3 ADDITIONAL QUALITATIVE EXAMPLES
In this section, we provide additional qualitative examples demonstrating the improvements irovr achieves in proof optimization.
18

---

Published as a conference paper at ICLR 2025
Table 12: Model and Ablations
Model
Improvement
Nonempty Improve.
Accuracy
Improved Acc.
gpt-4o
3
19.66
24.36
80.7%
38.6%
gpt-4o
5
20.12
24.97
80.56%
36.11%
gpt-4o
22.44
27.21
82.46%
42.11%
gpt-40
10
21.73
25.28
85.96%
40.35%
gpt-4o
15
23.51
26.28
89.47%
45.61 %
gpt-4o-mini
3
3.65
4.63
78.95%
8.77%
gpt-4o-mini
5
5.12
6.21
82.46%
10.53%
gpt-4o-mini
3.65
4.34
84.21%
8.77%
gpt-4o-mini
10
4.99
5.69
87.72%
12.28%
gpt-4o-mini
15
4.35
5,06
85.96%
12.28%
gpt-4o-mini
20
4.87
5.56
87.72%
14.04%
Table RAG and Combination Sampling Method Ablations
Combination
m'
RAG
Improvement
Nonempty Improve.
Accuracy
Improved Acc.
pest-of-n(refinemmntt
3
5
True
33.78
33.78
100.0%
50.0%
best-of-n(reffnnmment)
3
5
False
31.23
31.23
100.0%
46.88%
best-of-n(refnnement)
5
3
True
31.85
31.85
100.0%
50.0%
best-of-n(rcfnnmment)
5
3
False
31.35
31.35
100.0%
50.0%
(efieemen((besttofon)
3
5
True
32.66
51.32
63.64%
48.48%
(efinement(best-offnn))
3
5
False
32.88
50.1
65.62%
53.12%
refinement(best-offnn)
5
3
True
34.88
57.56
60.61 %
54.55 %
(efieeeen(beettoffn))
False
29.54
49.75
59.38%
43.75%
best-of-n
N/A
15
True
29.64
32.71
90.62%
56.25%
best-of-n
N/A
15
False
28.25
33.48
84.38%
53.12%
Compfiles: Length Optimization Consider Figure 1, lemma from the 2022 IMO Question (Compfiles) that we optimize for length. ImProver halves thr proof from 12 tactics to 6. Here, ImProver makes multiple nontrivial optimizations, such as eliminating the h2 and h4 and hxw hypotheses, well fully generating proof terms for specific rewrites and other tactics.
Declarativity Optimization Consider Figure 7, in which lemma from the 2019 IMO problem (from the Comptiles dataset) is optimized for declarativity. This introduces multiple new hypotheses, which generalize meerr_prrperty of the functions, and then reuses and instantiates that (and others, too) hypothesis throughout the proof, creating significantly more declarative proof.
Compfiles:
Original (human-written)
ImProver (declraativtt-aptiiizee)
lmmma addit! ve. to_ 11near (f : B) (he
Lemma additive to Linexx (E 2 2) the ix 21, Vi y) a e, V f www.ddfffoo.otttttneeeaaaaa <| let g AddMonoidHon. Addkoncidllom.nk have intro =fl ammml intro
Z), d.cdsmooidkom.tonntiiieee addManoi.Hom... tor.ddenn.ttnnnnneeeeee <|
y)
3 e, fa let g AddMonoidHom,
=- by
retine (2 fun 2_)
: fa
change g
rw [mul [mul_coom, +- smui_eq__ul, + LinesrMap..ees mes.baap.mepsmil,,, smul _oul_eq_mul, mul_ene]
by
:M [mul ocmn, + smul eq mul, LinearKap map_smul, smul refine (f 1, fun ?_) have f_eq_g have g_a_eg f__og_s linear prcportrrreetty 1, g_a_eg]
mul_one]
linear property proprry
g_smul
Figure 7: Optimizing a lemma from IMO 2019 Pl for declarativity
19

---

Published as a conference paper at ICLR 2025
Compfiles: Mixed Optimization Consider Figure 8, in which a lemma from the 2023 USAMO problem (from the Compfiles dataset) is optimized for mixed declarativity and length. This introduces new hypothesis, which declares powerful intermediate lemma, which is then applied to solve the problem. Moreover, this declarativity is introduced in such a way that it makes the proof more concise than the original, with tactics rather than 5.
Original (human-written
ImProver (mix-optimized)
1emma_3 la b R+] a
cema 1emma_ 3 (a b R+) (h. a
C. a :- by [h]
by
cbtain (b, hb) b
have to < th + to :- _f_ss_____pp__lott
e.val b.properly
obiain (c, ho) :-c
[e-Subtype.coe_t coc,, ccsitive.coe_ddd)
exact 1t_ of_
a hb
Positive.coe_add]
exact this
Figure 8: Optimizing a lemma from USAMO 2023 P2 for mixed declarativvttyllenthh
MIL: Length Optimization Consider Figure which optimizes an exercise solution from MIL Chapter 8, Section 1 (Group theory) for length, modifying the proof structure and introducing proof terms into the structure of the proof shorten from 9 tactic invocations to
Original (human-written)
ImProver (length-optimized)
example (pp + (6 +
Subgroup 5)
example (p G -+ HI 1 H + (9 Subgroup G)
map comp () map mS.map (P)
by
ext:
map (ef. corp by
map 18.map
simp onlyy [men_mep]
constructor
zintro (y, y_in, hy)
simp only [mam_map)
exect (p Y, (v, y_in, rEl), by)
constructor
virtra (y, (*, 7_in, hx), by)
rintro (y, y_in, by); exact (p (y, y_in,
use 2, s_in
=f1), by)
cale cocomp
(p xfl V by congr
rintro (y, (z, z_in, hz), hy); exacs (z, 2_in, (congr_arg & het itrans hy)
Figure 9: Optimizing lemma from the solutions of MIL. CH08 S01 for length
MIL Declarativity Optimization. Consider Figure 10, result from MIL that we optimize for the declarative metric. This original proof carried a score of O, as it has no have statements. In comparison, after applying ImProver, the model explicitly defines hypotheses for use in the latter half of the proof; these hypotheses can easily be converted into standalone lemmas for reuse.
Original (human-written)
ImProver (declarativityoppiiiize)
der 1801 [Fintype G] (h Diejoint K) (h" card
def iss; [Fintype G] (: Disjoiitt H K) (a) card = card card K)
card card K)
K 2 5 / 8 == by
x =+ G /
by Mune=ion.Injectiv
apply Mul oqu
injectivity
(1Quo: Lew.:eenntG:...k resteiiic 8)
I :Quottenttrropp .kk' H) rrsttrict k) by
[t- ker ver_eq_bot_iss (onocientCroup..kg
constructor
.eess_esstriet
zw It н) _ee__restriit K]
(QuotientGroup.akk
simp [h]
card_eq eard
card K
simp [h]
exact aux_card ee hi
symm
apply MalEquiv, KalEquiv.ofBäjeed ofBijective
exact aux_card_eg ht
[(QuctientGrou mkk Hi Hj.restrict K) [bl jeotive__ee construstor
exact injectivity syme exact card_eg
Figure 10: Optimizing a group-theoretic result from MIL Chapter 8 Section for declarativity.
20

---

Published as a conference paper at ICLR 2025
MIL: Mixed Optimization Consider Figure 11, which optimizes exercise solution from MIL Chapter 8, Section (Group theory) for mixed length/declaratiitty.. ImProver significantly modifies the structure of the proof, applying (via eliminating the need for manual step-by-step calculations). Moreover, the proof introduces declarativity by intermediate result, which used by the s simpa call to finish the proof in efficient and declarative manner.
general purposs tacties like s simpa to simplify the proof
Original (human-written)
ImProvee (mix-optimized)
Lemma bo_ _e__bo___E__ee ieE_card 1G : Type+1 [Group G] Subgroup GJ (Fistype
Cemma sg_bot_iff_eart (a Subgroup G; [Pintype H]
rypex; [Group G]
B ++ card II - :- by
im by have (V x E x == + mAXER Voe H, K
card B
suffices (V E x
#3EEH, V
E, a = x by stmpa [ee__ot_iff__orall, card_eg_one_irc
(A (1, H.one_nem, W), (v, hy") hx e> Ohy' H.onn_mmen -ymm hy" x hx) simpa hog_hottifff_oot using this
construetor
intro h use B.one_men
card_eg_one_iff
zintro (y, -, by" ) x hx by'
in thy" 1 B.one_men) -aym
Figure 11: Optimizing lemma from MIL CH08 S01 solution for mixed declarativvityllentth
Length Optimization Consider Figure 12, which optimizes a theorem in algebraic topology from mathlib for length, eliminating iimp calls and combining tacties to shorten it from 3 tactic invocations to 1.
Mathlib:
Original (human-written)
ImProver (length-optimized)
(E(p(t) g(g(t)))" two paths 'p" and "q", then the induced path homotopy classes
'f(pit) gig(t))" two paths "p" and "q', then the inducad path homotopy classes
"Etp)" and (g(p)"
the same well,
despize having a priori different types -/
"pl"" and "g(pt" are the
well, despite having a priori different types =/
theoren heq_pathhoff Soaathoff_ee_maaae
HBq (65m f) .map [P]] ((Tm map [q]) i= by
theoram heq_path path_ sart_hof_e__iaap__ image : HFq (Imm f),map [p]) (Imm g) .map [q])
aimp only [map_eq, +-
Path, www.tomoo..teeie..oooo.. www.oooooee.pptt...a...... exact
Path. wtt.mooopic.mpp_ul.....
apply
exact hot.hhoo.pppphptthhhhhoo
hfg
by
Figure 12: Optimizing theorem from Mathhib//undddmenttarrrroooppii Induuees
InducedMaps
for length
Declarativity Optimization Consider Figure 13, a theorem from Mathlib that we optimize for declarativity.
Mathlib:
This original proof carried score of 0, as it does not contain any declarative statements. It is concise and efficient, however, it is difficult to understand and read.
After optimizing for declarativity, we see that the model did not change the structure of the proof. Rather, it added an intermediate declaration so that users can better understand the state after the convert. This intermediate tactic greatly helps in the understandability and clarity of the proof.
Mathlib: Mixed Optimization Consider Figure 14, theorem from Mathlib that we optimize for mixed length/declaratiiity.
We observe that ImProver applies more complex tactics such as all aall_goall and split i fs to significantly decrease the number of tactics in the proofs, while maintaining the overall structure.
21

---

Published as a conference paper at ICLR 2025
Original (human-written)
ImProver (decharaiiiityoppimize))
/ Another version of
f-o Another version of
samplyy.onnecsede htt___paaa____eee_______e_eee
"stmply, coo.lleccceeee_____ frr_patts____ coaths_homotoppi""
Lheoren copply_ooneeted_iieo pat___assssspp________a_____sssp hosossooooopii
theozem Sumply_connecle Semnentte_iif_aaee
IX rype*] [Iopological$pace x1
(Y Type*] [Topol ogt ca 15pace Y]
siaplycooneettedspen Y
E.mplyyooneeteedppace
PathCannectedd$pco Y
(x y Y) IP1
RethComecteddpacee Y Pa #eth y), Path.Hemotopiic Ft P2 by
(x X) (p:
Pa by convert
x W), Homhooooo P1 P2
convert suppy..coneeeeeLii..pheeeeee
Lungly_comeeeted__i..oeoe homottpic
1 Y)
:- Y) x Subsingleton
[etold.e__top_1cii rfl
(Patà. Wattteoootcpicc Hlsoteppe..uuttier. Quotient x y) (pt
Fath x y!, Homotopic F1 P2 : by
intro simp [Path. Lomct Quotient,
Setoid.eg_tep.jft
:I1
simp only [hi]
Figure 13: Optimizing a theorem from htt.a//thhi////aaaaattaaooooooip for declarativity
Original (human-written)
ImProver (mix-optimized)
theoren Lzama Lrame_refi__eeee repaapaaaa___aa (p 2ath xa x1)
theorem ccans_refl__eeareee Path xi
p.trens (Path.refl x:)
p.trans [Path.rofl X1)
p.reporem (Sun =>
reparamm
=cansBeelRReaacnnuuu t,
transRofl t,
mem_ t)) (by
transRef Reparantux_ t)) bby
continusty:
continuity)
(Subtype.ext
(Subtype,ext
= zero) (Subtype.ex:
transsefl.epparrakkk. _nne)
(Subtype.ext
=conssoffleeprrmmuuu.oog
transRe ReparamAux_onge t
1a by
p.reporzm (Sun
p.reparam (Tun
:censkeelleeparzmuuu t,
transReflRepssennku t,
cronckeflReparammu I t)) (by
BeansterrleeparraAuu..eee. t)) Iby
nontinuttyy
continuity)
(Sublype.ext.
(Subtype.ext
=ransReflReparamuus zero) (Subtype.ex:
tran:Raf tranaRef ReparamAux_one) :-
(Subtypo.oxt
=ranssefflKeprrrmuuu.ooggg by
ext unfold LransRetlRepararduux
simp only [Path.trans_appi)
simp only [Path.trans_apply not not_le,
ieth. coe_reparam,
coe_ reparam, Funot fon. cot.ccopppppll......
sunetien.comp_egge unfold transke
one_div, reth.refi_spply]
split_ifs =fl
split_ifa
all_goala simp
xfl simp s1mp
Figure 14: Optimizing a theorem from fannaaaiii//nunnttt..coooo/////e for mixed length/declaratiiity
Full Proof Generation (MIL). in the MIL example from Figure 15. This theorem relating to group theory originally has proof, however, ImProver generates one from scratch. This generated proof is verified to be correct by Lean, utilizing all the included hypotheses as well as retrieved mathlib theorem.
analyze the application of InnProved to neural theorem proving
Original (human-writtenn
Im ImPorv (completeness-optiiizze))
example (p G + (S T Subgroup III (asT 3 comap comap by sorry
axample (p G + H1 comap yp
18 I Subgroup H) (hST
comap
intro
simp only [men__cmap] intro hs
exact hS2 he
Figure 15: Solving a group theorem exercise from MIL Chapter 8 Section
Full Proof Generation (MiniF2F). We analyze the application of ImProver to neural theorem proving in the Mi example from Figure 16. This theorem relating number theory originally
22

---

Published as a conference paper at ICLR 2025
has proof, however, ImProver generates from scratch by calculating step by step, applying theorems retrieved from Mathlib, as well as general tactics like simp.
Original (human-written)
ImProver (completeness-otimiizee)
theoren mathd_nni nwwbertheory__.. (2000 + 2001 2002 + 2003 2004 + 2005 2006) by sorzy
theorem machd_number:heery 345
12000
2002
2004
2006: 7 cale
(2000 2001 2002 2003 + 2004 2005 2005) t 7 (2 +
6)
simp [Nat.adé_mod,
mod _e___________________ dd_d, Nat. vad_de_reef), Nat mtt_mmodddddnnn Nat.mod_sel[]
4 :- by simp
by
Figure 16: Solving a number theoretic theorem from MiniF2F.
23


Reviews:
[{"review_id": "PjDwBrmW3G", "reviewer": "Reviewer_5mDw", "summary": "The paper introduces ImProver, a large language model (LLM) agent designed for automated proof optimization in the proof assistant Lean. ImProver adopts several LLM augmentation methods, including a Chain-of-States technique that provides intermediate proof states to LLM, retrieval methods, and sampling methods.\n\nThe paper defines three key metrics for evaluation: the Length Metric, which aims to minimize the number of tactic invocations; the Readability Metric, which favors a declarative haveproof style; and the Completion Metric, which measures proof correctness.\n\nIn experiments, the author compares ImProver with the baseline GPT-4o model on Mathematics in Lean (MIL), Compfiles, and Mathlib datasets. The results show that ImProver reduces the length of 35.44% of proofs compared to 8.31% for GPT-4o, and increases readability in 24.56% of proofs compared to 6.13% for GPT-4o. Proof completion was evaluated only on the selected MIL dataset, where ImProver achieved 39.13% successful proof generation compared to 21.73% for GPT-4o.", "questions": "- Could the authors clarify under what criterion the mathematical branch of the dataset for testing the neural theorem proving effect was selected and whether they have evaluated the method on the entire dataset and other commonly used datasets?\n- Could the author clarify whether they have tried any rule-based methods and compared their results to those produced by ImProver?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper first discovers a new field of automated proof optimization, and conducts a pioneering attempt in this field, marking the first significant effort to use LLMs for enhancing formal proofs with respect to certain metrics in proof assistants like Lean. A notable strength of this work is its emphasis on the role of proof states in guiding LLMs. By introducing the Chain-of-States technique, which provides intermediate proof states to the LLM, the authors demonstrate an understanding of how contextual information can significantly improve the accuracy and efficiency of proof optimization.", "weaknesses": "- The method proposed in this paper is well-suited for metrics that can be directly computed from the formal proof. However, this limits its applicability to more complex metrics such as readability. The paper defines readability as the ratio of explicitly typed have tactics to the total number of tactic invocations in line 130. This simple definition may lead to a proof with numerous unused have tactics being considered more readable than a normal proof. The reviewer considers readability to be a multifaceted metric, influenced by various factors including the use of underlines, the depth of proof terms, the naming of variables, appropriate comments within the proof, and other stylistic elements. These factors are challenging to quantify with a simple function, suggesting that the proposed method may not be effective for assessing readability or other nuanced aspects of proof quality.\n- The reviewer suggests developing a combined metric that considers both length and readability for a more accurate assessment of proof quality in real applications, since improving in one metric may significantly sacrificing other metrics. Additional experiments should test whether the framework described in the paper can effectively balance and improve these combined metrics.\n- The proof generation results in Table 7 are limited to specific selected datasets. The reviewer believes that ImProver's neural theorem proving results should also be evaluated on unselected datasets and more commonly used test sets, and compared with a wider range of models to provide a comprehensive assessment of the proposed method's performance.\n- The comparison with GPT-4o, which lacks proper Lean 4 syntax capabilities, may not accurately reflect the effect of RAG or refinement policies of ImProver. More ablation studies could be conducted to demonstrate that the rise in performance is not solely due to the guidance for correct Lean 4 syntax in the prompt.\n- The reviewer suggests that rule-based optimization methods for Lean, particularly for the length metric (e.g., using nested termwise proofs to replace tactic-based proofs), exist. The authors should compare ImProver with these methods to demonstrate its relative strengths.", "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": "", "extra_scores": {}}, {"review_id": "BR8hD4xDWO", "reviewer": "Reviewer_XEdk", "summary": "The paper tackles the proof optimization problem, which aims to optimize partly written proofs with respect to a given criterion (such as length and readability).\nThe paper also addresses the problem by querying to LLMs and ranking the outputs with the criterion.", "questions": "- It is possible to explain the benefits of solving the proof optimization problem with application domains (such as formal verification or mathematical education), references, and concrete examples that support the claim?\n- I think it is important to incorporate some kind of random in using the best-of-n technique. Does the proposed approach ensure diversity in the LLM outputs when using the best-of-n technique? If yes, how it is achieved? Otherwise, how do you address the potential issue of deterministic outputs?\n- Can you provide a detailed description of the input format for ImProver and GPT-4o in the experiment? Especially, does the input include the original proof from the dataset, a partial proof, or start with an empty proof?\n- The paper claims ImProver can rewrite proofs so that they are more modular. Can you provide a clear definition of 'modular' in the paper?  It would also be helpful to give modular and non-modular examples.\n- What does the paper mean by efficient proofs? (E.g., it says \"These proofs are extremely efficient\" in lines 266-267).", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "+ The paper tackles the proof optimization, which has not been considered yet in neural theorem proving, and proposes a (simple) approach to it.\n+ The proposed approach can outperform the baseline, which simply queries to an LLM (GPT-4o).", "weaknesses": "- Because the proposed approach to the proof optimization (described in Section 3) is simple, I find the main contribution of the paper is in applying LLMs to proof optimization, a problem in theorem proving. When evaluating the paper from such a viewpoint, I admit the proof optimization problem may be worth studying, but I don't think the paper argues its value in a convincing manner. The second paragraph of Section 1 discusses the importance of the proof optimization, but there is no reference to support the argument. That is, there is no objective material to find the importance of the problem. Therefore, it is unclear and unconvincing what benefit is expected by solving the proof optimization problem.\n\n- Some experimental setting and terminology are unclear (see the following questions).\n\nTypos:\n\n- l35: precision --> imprecision", "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": "", "extra_scores": {}}, {"review_id": "9p2vNTNGId", "reviewer": "Reviewer_3uHZ", "summary": "Authors are studying whether LLMs can optimize formal math proofs for additional criteria besides correctness, such as length and readability. They find that naively applying LLMs don’t perform great at this task, but that multiple interventions like augmenting the formal proof with comments, adding relevant context via retrieval, or selecting the best of N solutions, substantially improves performance. Finally, they ablate these interventions and find that each contributes substantially to the overall performance.", "questions": "Idle musing, feel free to ignore: Do you have thoughts about the ceiling/floor of your proposed metrics - are there degenerate solutions? In particular, could `we evaluate this using the ratio of number of explicitly typed have tactics to total number of tactic invocations.` incentivize the model to generate a lot of superfluous `have` tactics to inflate this metric?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The authors frame an interesting and potentially very impactful problem, propose a smart solution, and execute on that solution well. The paper is well-written and the results appear convincing to me.", "weaknesses": "The authors could mention interactive proofs / prover-verifier games (https://arxiv.org/abs/2108.12099), where LLMs are trained to write informal math proofs to be maximally legible to an independent verifier, as related work.\n\nI believe the caption of Figure 1 should read (left) instead of (right)?\n\nFor reproducibility, the authors should mention the exact version of GPT-4o they used for their experiments (gpt-4o-2024-08-06 ?)\n\nI’m taking it on trust that “readability” defined as in the paper is a sensible definition - to someone not familiar with Lean, the \"readability-optimized\" version of the proof in Figure 3 is not actually a lot easier to parse than the other version.", "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": "", "extra_scores": {}}, {"review_id": "m0MXpFnKPk", "reviewer": "Reviewer_gxhK", "summary": "The paper proposes ImProver, a framework designed to optimize proofs based on various metrics, such as shortening proof length and enhancing human readability. The authors establish several performance metrics to evaluate the quality of improvements and conduct comprehensive case studies across representative benchmark datasets for an extensive analysis.", "questions": "- Could the authors elaborate further on the “flat” and “structured” formats described in Section 3.1.2 and provide examples for clarity?\n- When selecting parameters in the ablation study, why was the best parameter combination chosen based on improvement rather than accuracy? Could the authors discuss the trade-offs between optimizing for improvement versus accuracy, and how this choice might impact the practical applicability of ImProver?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- As the first work in proof optimization, this paper defines novel and reasonable metrics to quantify the quality of Lean proofs.\n- The paper integrates several advancements from the LLM community, including proof generation, retrieval, chain of thought (CoT) reasoning, and self-correction in code generation, for optimizing proofs. The inclusion of these methods is well-motivated, and the experiments are extensive. Furthermore, ImProver achieves notable performance without using models fine-tuned specifically for proof generation, showing its significant contributions to proof synthesis and optimization.\n- The open-source code is well-structured and documented, facilitating easy adoption and use by the community.", "weaknesses": "While the experimental results are comprehensive, their presentation could be improved, which is particularly important for a paper focused on advancing LLM applications in proof optimization. Specifically, in Section 4.2.1 on ablation testing:\n\n- At line 450, the term “string list” is introduced without prior definition. Could the authors clarify the relationship between \"string list\" and the \"flat\" format mentioned earlier? This would help ensure consistency in terminology throughout the paper.\n- Table 5 could be clarified further. Upon cross-checking, it appears that the best/worst values are based on configurations giving the highest “improvement” scores, whereas the last row presents the best scores across all configurations. It would be helpful to explicitly state this distinction in the main text to enhance clarity.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)