HyperTree Proof Search for Neural Theorem Proving

Introduction

Over the course of history, the complexity of mathematical proofs has increased dramatically. The nineteenth century saw the emergence of proofs so involved that they could only be verified by a handful of specialists. This limited peer review process inevitably led to invalid proofs, with mistakes sometimes remaining undiscovered for years (e.g. the erroneous proof of the Four Colour Conjecture ). Some mathematicians argue that the frontier of mathematics has reached such a level of complexity that the traditional review process is no longer sufficient, envisioning a future where research articles are submitted with formal proofs so that the correctness can be delegated to a computer .

Unfortunately, very few mathematicians have adopted formal systems in their work, and as of today, only a fraction of existing mathematics has been formalized. Several obstacles have hindered the widespread adoption of formal systems. First, formalized mathematics are quite dissimilar from traditional mathematics, rather closer to source code written in a programming language, which makes formal systems difficult to use, especially for newcomers. Second, formalizing an existing proof still involves significant effort and expertise (the formalization of the Kepler conjecture took over 20 person years to complete ) and even seemingly simple statements sometimes remain frustratingly challenging to formalize.

To write a formal proof, mathematicians typically work with Interactive Theorem Provers (ITPs). The most popular ITPs provide high-level “tactics” that can be applied on an input theorem (e.g. the initial goal) to generate a set of subgoals, with the guarantee that proving all subgoals will result in a proof of the initial goal (reaching an empty set means the tactic solves the goal). An example of a proof in Lean , an interactive theorem prover, is given in Figure 1 and the corresponding proof hypertree is illustrated in Figure 3. A tactic, induction k, is applied on the root goal ($n+k\leq m+k$) to start a proof by induction A hypergraph is a graph where an edge leads to a set of nodes that is potentially empty in our set-up. A hypertree is a hypergraph without cycles. More formal definitions can be found in Appendix A.1. The formal system returns two subgoals: $n+0\leq m+0$ (the initial case) and $n+k\leq m+k\Rightarrow n+k+1\leq m+k+1$ (the induction step). As the first subgoal is our initial hypothesis, it can be solved using the exact tactic. To prove the second subgoal, we first rewrite it using nat.succ_le_succ_iff, a theorem from the Lean library stating that $m+1\leq n+1\iff m\leq n$. The new subgoal then becomes our induction hypothesis $n+k\leq m+k$, and can again be solved using the exact tactic, thereby solving the last remaining subgoal and completing the proof of the initial statement. Starting from a goal and reducing it to subgoals until these can be solved, is commonly referred to as backward proving.

In this paper, we aim at creating a prover that can automatically solve input theorems by generating a sequence of suitable tactics without human interaction. Such a prover could significantly reduce the effort required to formalize existing mathematics. The backward procedure naturally suggests a simple approach where a machine learning model trained to map goals to tactics interacts with an ITP to build the proof of an input goal in a backward fashion. The automated prover builds a hypergraph with the theorem to be proved as the root node, tactics as edges and subgoals as nodes. The prover recursively expands leaves by generating tactics with our model until we find a proof of the initial theorem. A proof in this setup is a hypertree rooted in the initial theorem whose leaves are empty sets. As many different tactics can be applied to a goal, and each tactic application can result in multiple subgoals, the number of goals in the graph grows exponentially and it is critical to reduce the search to the most promising branches. This can be done through techniques like alpha-beta pruning or Monte Carlo Tree Search (MCTS) , known for its recent successes in difficult two player games . However, challenges arise in search algorithms for theorem proving that do not occur in two player games. For instance:

The action space, i.e. the amount of possible “moves” in a given state, is infinite (there is an unlimited number of tactics that can be applied to a given theorem). This requires sampling possible actions from a language model for which training data is scarce. Moreover, if all tactics sampled at a goal fail, we have no information on what region of the probability space to sample next.

In the context of theorem proving, we need to provide a proof of all subgoals created by a tactic, whereas AlphaZero for two player games is allowed to focus on the most likely adversary moves.

In Chess or Go, playing a sub-optimal move does not necessarily lead to losing the game, thus exploring these branches can provide information. In theorem proving, it is frequent to generate tactics that result in subgoals that can no longer be proved and on which the model will waste significant search budget.

This paper presents an in-depth study of our approach to overcome these difficulties and the resulting model, Evariste. In particular, we make the following contributions:

A new MCTS-inspired search algorithm for finding proofs in unbalanced hypergraphs.

A new environment (Equations) to easily prototype and understand the behavior of the models we train and our proof search.

A detailed ablation study and analysis of the different components used in our approach on three different theorem proving environments. We study how data is selected for training the policy model after a successful or failed proof-search, what target should be used to train the critic model, and the impact of online training vs. expert iteration.

State-of-the-art performance on all analyzed environments. In particular, our model manages to prove over $82.6\%$ of proofs in a held-out set of theorems from set.mm in Metamath, as well as $58.6\%$ on miniF2F-valid in Lean.

We begin by introducing related work in Section 2 and present the three theorem proving environments that we study in Section 3. Then, we present our proof-search algorithm in Section 4, our online training pipeline in Section 5, and all experimental details in Section 6. Finally, we describe our main results and ablation studies in Section 7 before concluding in Section 8.

Related work

Automated theorem proving has been a long-standing goal of artificial intelligence, with the earliest work dating from the 1950s . Early approaches focused on simpler logics, culminating in extremely efficient first-order provers such as E or Vampire . However, these approaches are insufficient when it comes to theorems written in modern proof assistants such as Isabelle , Coq , or Lean . Recently, the rising success of deep language models and model-guided search methods has spurred a renewed interest in the problem of automated theorem proving.

Recent work applying deep learning methods to theorem proving are the closest to this work and obtained impressive results on difficult held-out sets for Metamath and Lean. The main differences between their approach and ours are the proof-search algorithm we propose, the training data we extract from proof-searches and our use of online training compared to their expert iterations. We validate experimentally that these differences lead to improved performances as well as faster training times. Another similar approach is Holophrasm , which is based on a different tree exploration technique which expands paths in an AND/OR tree, while we expand entire proof subtrees in a proof hypergraph. Their model is only trained once from supervised data and does not benefit from online training or expert iteration, which we found to be critical. DeepHOL focuses on the HOL-Light environment . Their model relies on a classifier that can select among a restricted set of tactics and arguments, while we rely on a seq2seq model that can generate arbitrary tactics. The suggested tactics are then used in a breadth-first search. TacticToe uses an MCTS without learned components, using ranking on predefined features to guide the search. Machine learning has also been used to improve classical provers by re-ranking clauses . Overall, previous studies always focus on a single proving environment (e.g. Metamath, Lean, or HOL-Light).

Impressive performance of large language models in one or few shot learning , machine translation or more recently code generation spurred interest into the reasoning capabilities of large transformers. These model perform quite well on formal tasks such as expression simplification , solving differential equations , symbolic regression , or predicting complex properties of mathematical objects . These studies suggest that deep neural networks are well adapted to complex tasks, especially when coupled with a formal system for verification.

Recently, AlphaZero demonstrated good performances on two player games, replacing the Monte-Carlo evaluations of MCTS with evaluations from a deep neural network and guiding the search with an additional deep policy. This recent success follows extensive literature into search methods for two player games, notably alpha-beta search . Theorem proving can be thought of as computing game-theoretic value for positions in a min/max tree: for a goal to be proven, we need one move (max) that leads to subgoals that are all proven (min). Noticing heterogeneity in the arities of min or max nodes, we propose a search method that goes down simultaneously in all children of min nodes, such that every simulation could potentially result in a full proof-tree.

Proving environments

In this paper, we develop and test our methods on three theorem proving environments: a) Metamath, b) Lean and c) Equations. Metamath comes with a database of $30k$ human-written theorems called set.mm. We also evaluate our methods on the Lean proving environment, which provides a level of automation that is helpful to solve more complex theorems. Lean comes with a human-written library of $27k$ theorems called Mathlib . Finally, since Metamath proofs can be quite difficult to understand and Lean requires more computing resources, we developed our own environment called Equations, restricted to proofs of mathematical identities. Its simplicity makes it ideal for prototyping and debugging. We briefly introduce these environments below.

Metamath’s only rule is string substitution. Starting from a theorem to be proven, variables are substituted until we reach axioms. In our setup, we consider a tactic to be the label of a theorem in set.mm, along with the necessary substitutions. As shown in Figure 2, to show that $2+2=4$, the first step uses eqtr4i which states that $A=B\wedge C=B\Rightarrow A=C$ with substitutions: $A=(2+2)$, $B=(2+(1+1))$, and $C=4$. We are then left with two subgoals to prove: $(2+2)=(2+(1+1))$ and $4=(2+(1+1))$.

The simplicity of Metamath makes it a great test bed for our algorithms. However, its lack of automation leads to larger proof sizes and its syntax and naming conventions make each step difficult to interpret for neophytes. Similar to GPT-f, we implement a parser for Metamath in order to automatically prove the syntactic correctness of statements. Moreover, we use this parser to allow generating only substitutions that cannot be inferred from the goal.

2 Lean

Lean is a full-fledged programming language and benefits from more powerful automation than Metamath, with tactics such as ring (able to prove goals using manipulations in semirings), norm_num (able to prove numerical goals) or linarith (able to find contradictions in a set of inequalities). An example of a Lean proof-tree is shown in Figure 3.

States are more complex in Lean than in Metamath: metavariables can appear which are holes in the proof to be filled later. Subgoals sharing a metavariable cannot be solved in isolation. This is addressed in Polu and Sutskever by using as input the entire tactic state. Instead, we inspect tactic states to detect dependencies between subgoals, and split the tactic state into different subgoals where possible in order to maximize state re-use and parallelization in the proof search algorithm.

Finally, Lean’s kernel type checker has to be called after each tactic application as tactics sometimes generate incorrect proofs and rely on the kernel for correctness. For every goal in the previous tactic state, we type check the proof term inserted by the tactic. Since the kernel does not support metavariables, we replace every metavariable by a lambda abstraction.

3 Equations

We developed the Equations environment as a simpler analogue to existing proving environments. Its expressivity is restricted to manipulating mathematical expressions (e.g. equalities or inequalities) with simple rules (e.g. $A+B=B+A$, or $A<B\Rightarrow-B<-A$). This reduced expressivity makes goals and tactics easy to understand, helping with interpretability and debugging: plotting the set of goals explored during a Metamath proof search does not give a lot of insights on whether it is on track to find a proof. In Section B of the appendix, we give an in-depth presentation of this environment, of how we represent goals (Section B.1), tactics (Section B.2) and how we prove statements (Section B.3).

Unlike in Metamath or Lean, we do not have access to a training set of human annotated proofs for this environment. Instead, we create a training set composed of randomly generated synthetic theorems and their proofs (see Sections B.6 and B.6 for details), and manually create an out-of-domain set of non-trivial mathematical identities for which we do not provide proofs, e.g. $\cosh(3x)=4\cosh(x)^{3}-3\cosh(x)$ or $\sin(4x)=(4\sin(x)-8\sin(x)^{3})\cos(x)$. We refer to this evaluation split as Identities, a set of 160 mathematical expressions.

As synthetic theorems randomly generated are much simpler and significantly differ from statements in the Identities split, we can evaluate the ability of our model to generalize to complex and out of domains data. An example proof-tree in Equations is shown in Figure 4.

HyperTree Proof Search

Given a main goal $g$ to automatically prove, proof search is the algorithm that interacts with our learned model and the theorem proving environment to find a proof hypertree for $g$. Proof search progressively grows a hypergraph starting from $g$. A proof is found when there exists a hypertree from the root to leaves that are empty sets.

In this section, we assume a policy model $P_{\theta}$ and critic model $c_{\theta}$. Conditioned on a goal, the policy model allows the sampling of tactics, whereas the critic model estimates our ability to find a proof for this goal. Our proof search algorithm will be guided by these two models. Additionally, and similar to MCTS, we store the visit count $N(g,t)$ (the number of times the tactic $t$ has been selected at node $g$) and the total action value $W(g,t)$ for each tactic $t$ of a goal $g$. These statistics will be used in the selection phase and accumulated during the back-propagation phase of the proof search described in Section 4.1 and Section 4.3.

The algorithm iteratively repeats the three steps described below to grow the hypergraph until either a proof is found or we exceed our expansion budget. We show an example of these three steps of proof search in Figure 5. We refer to this algorithm as HyperTree Proof Search (HTPS) throughout this work. A more detailed comparison between HTPS, MCTS, and the best-first search algorithm of Polu and Sutskever can be found in Appendix A.4.

The number of nodes in the proof hypergraph grows exponentially with the distance to the root. Thus, naive breadth-first search is infeasible to find deep proofs and some prioritization criteria is required to balance depth and breadth. This is the family of best-first search algorithms, of which A* and MCTS are instances. Similar to MCTS, we balance the policy model’s prior with current estimates from the critic. In particular, we experiment with two different search policies: PUCT and Regularized Policy (RP) , detailed in Appendix A.2. These search policies use the tactic prior from the policy model, the visit count $N$, and the estimated value of the tactic given by $Q=W/N$. A higher visit count will lead to a higher confidence in the estimated value than in the prior policy model, and vice-versa for low visit counts.

The key difference between previous work and ours is that our proof search operates on a hypergraph. Thus, whereas an algorithm like MCTS will go down a path from the root to an unexpanded node during its selection phase, our algorithm will instead create a partial proof hypertree, leading to a set of either solved or unexpanded nodes. The selection phase algorithm, described in more details in Appendix A.3, consists in recursively following the search policy from the root until we find leaves of the current hypergraph.

In Figure 5, we illustrate the selection step. We start at the root node $g$, which has three tactics $t_{0},t_{1},t_{2}$. The search policy selects $t_{2}$, leading to the set of subgoals $\{g_{0},g_{1}\}$. Then, for both $g_{0}$ and $g_{1}$, we again select the best tactic according to the search policy and finally reach the sets of unexpanded subgoals $\{g_{2},g_{3}\}$ and $\{g_{4}\}$. The final selected proof hypertree $T$ is composed of $g,\{g_{0},g_{1}\},\{g_{2},g_{3}\},\{g_{4}\}$ and is colored in dark blue in Figure 5.

In order to batch calls to the policy and critic models over more nodes to expand, we run several selections sequentially, using a virtual loss to produce different partial proof-trees. Note that solving all unexpanded leaves of any of these trees would immediately lead to a full proof of the root. In the next section, we describe how nodes are expanded.

2 Expansion

To expand a node $g$, we use the policy model to suggest tactics that would make progress on the goal, then evaluate these tactic suggestions in the theorem proving environment. Each valid tactic will lead to a set of new subgoals to solve, or to an empty set if the tactic solves the goal. Finally, we add a hyperedge for each valid tactic $t_{i}$ from the expanded node $g$ to its (potentially empty) set of children for this tactic $\{g_{i}^{0},...,g_{i}^{k}\}$. Note that these children might already be part of the hypergraph. For new nodes, visit counts $N(g,t)$ and total action values $W(g,t)$ are initialized to zero. There are three types of nodes in the hypergraph:

Solved: at least one tactic leads to an empty set, or has all its children solved.

Invalid: all tactics sampled from the policy model were rejected by the environment, or lead to invalid nodes.

Unsolved: neither solved nor invalid, some tactics have unexpanded descendants.

Note that the definitions for Solved or Invalid are recursive. These status are updated throughout the hypergraph anytime a hyperedge is added. Tactics leading to invalid nodes are removed to prevent simulations from reaching infeasible nodes. Once this is done, we back-propagate values from the expanded nodes up to the root, as described in the next section.

In Figure 5, we show an example of expansion. After selecting a hypertree $T$ during the selection step, for each unexpanded leaf goal of $T$, we generate $B=2$ tactics with our policy model and keep only the valid ones. This results in two tactics for $g_{2}$ and $g_{4}$ and one for $g_{3}$. We apply these tactics in our formal environment and obtain new sets of subgoals and add them to the hypergraph. One tactic of $g_{2}$ solves $g_{2}$, resulting in an empty set of subgoals. Note that because $g_{3}$ is not solved yet, $g_{0}$ remains unsolved.

3 Back-propagation

For each expanded goal $g$ in a simulated proof tree $T$, its value is set to $v_{T}(g)=1$ if it is solved, and $v_{T}(g)=0$ if it is invalid. Otherwise, its value is estimated by the critic model: $v_{T}(g)=c_{\theta}(g)$. This provides $v_{T}$ for all leaves of $T$ and we can then back-propagate in topographic order (children before parents) through all nodes of $T$. Interpreting the value of a node as the probability that it can be solved, since solving a goal requires solving all of its children subgoals, the value of a parent is the product of values of its children (we assume that the solvability of subgoals is independent, for simplicity):

In particular, the value of a goal $g$ is the product of the values of all leaves in $T$ that remain to be solved to obtain a proof of $g$. Once all values in $T$ are computed, we increment the corresponding visit count $N(g,t)$ in the hypergraph as well as the total action values: $W(g,t)\mathrel{+}=v_{T}(g)$. For a goal $g$, the estimated value for tactic $t$ is then the mean of the total action value:

We give an example of back-propagation in Figure 5. First, we evaluate the values of the leaf nodes of $T$. Because $g_{2}$ is solved, we set $v_{T}(g_{2})=1$. The values of $g_{3}$ and $g_{4}$ are estimated with the critic model, e.g. $v_{T}(g_{3})=c_{\theta}(g_{3})=0.1$. The values of the internal nodes are obtained by computing the product of their children values. Thus, we first compute $v_{T}(g_{0})=v_{T}(g_{2})\times v_{T}(g_{3})$ and $v_{T}(g_{1})=v_{T}(g_{4})$, then $v_{T}(g)=v_{T}(g_{0})\times v_{T}(g_{1})=(v_{T}(g_{2})\times v_{T}(g_{3}))\times(v_{T}(g_{4}))$. Then, for every (goal, tactic) pair $(g,t)$ in $T$, we increment the visit count, $N(g,t)\mathrel{+}=1$ and update the total action value: $W(g,t)\mathrel{+}=v_{T}(g)$.

Online training from proof searches

In the previous section, we considered the policy and critic models as given. In this section, we explain how proof search is used to create training data for these two models. Provers are asynchronously running proof searches using a version of the models synchronized with the trainers, coupling training and data extraction in an online procedure that leads to continuous performance improvements.

Both the policy model $P_{\theta}$ and the critic model $c_{\theta}$ are encoder-decoder transformers with shared weights $\theta$, which are trained with a tactic objective and a critic objective respectively.

The policy model $P_{\theta}$ takes as input a tokenized goal and generates tactics. It is trained with a standard seq2seq objective , where we minimize the cross-entropy loss of predicted tactic tokens conditioned on an input goal.

In order to decode a floating point value with our seq2seq critic model $c_{\theta}$, we start decoding with a special token, restrict the output vocabulary to the two tokens PROVABLE and UNPROVABLE, and evaluate the critic with $c_{\theta}(g)=P(\texttt{PROVABLE}|g,\texttt{CRITIC})$. The critic objective is identical to a seq2seq objective where the cross-entropy is minimized over the two special tokens.

2 Online training

We use a distributed learning architecture reminiscent of AlphaZero or distributed reinforcement learning setups . A distributed data parallel trainer receives training data from a set of asynchronous provers that run proof searches on tasks chosen by a controller that also centralizes statistics. Provers, in turn, continuously retrieve the latest model versions produced by the trainers in order to improve the quality of their proof search. This set-up is represented in Figure 6. Once a prover finishes a proof-search, we extract two types of training samples from its hypergraph:

At the end of a successful proof search, we extract (goal, tactic) pairs of a minimal proof hypertree of the root node as training samples for the policy model. This selection has a large impact on performances, other options such as selecting all solved nodes are investigated in Section 7.2.1. We use a different minimality criteria depending on the environment: total number of proof steps for Metamath and Equations, and total tactic CPU time for Lean (see Appendix E for details).

In the proof search hypergraph, we select all nodes that are either solved, invalid, or with a visit count higher than a threshold. Then, we use $c(g)=1$ as the training target for solved nodes. For internal nodes, we use the final estimated action value $c(g)=W(g,t^{*})/N(g,t^{*})$ where $t^{*}$ is the tactic that maximizes the search policy at $g$. Finally, for invalid nodes, we use $c(g)=0$.

The trainers receive training samples that are stored into two separate finite-size queues, one for each objective. When a queue is full, appending a new sample discards the oldest one. In order to create a batch for a task, we uniformly select samples in the corresponding queue. The two training objectives are weighted equally. Additionally, during online training, we continue sampling from the supervised tasks which provide high-quality data.

Our proof-search depends on many hyper-parameters, and the optimal settings might not be the same for all statements, making tuning impractical. Thus, the controller samples these hyper-parameters from pre-defined ranges (see Appendix C for details) for each different proof-search attempt.

3 Full training pipeline

In order to bootstrap our online learning procedure we require a policy model $P_{\theta}$ that outputs coherent tactics. While the critic is left untrained, the policy model is fine-tuned on a pretrained transformer using a supervised dataset specific to the target environment. Overall, the full training pipeline can be summarized as follows:

Pretraining of the encoder-decoder model on a large unsupervised corpus (c.f. Section 6.2).

Fine-tuning of the policy model on supervised datasets detailed in (c.f. Section 6.1).

Online training of both the policy and critic models on data extracted from proof search.

Experiments

In this section, we provide details about our experimental training and evaluation protocols. We first describe the supervised datasets used to fine-tune our policy models, as well as the tokenization used. We then give practical details on pretraining and the model architecture. Finally, we discuss the evaluation datasets and methodology.

Starting the HTPS procedure described in Section 5 from a randomly initialized model would be sub-optimal, as no valid tactic would ever be sampled from the policy model. Thus, starting the online training from a non-trivial model is critical. To this end, we first fine-tune our policy model $P_{\theta}$ on a supervised dataset of theorems specific to each environment.

In Metamath, we extract all proofs from the set.mm library, composed of 37091 theorems (c.f. Section D for the version of set.mm). We first derive a graph of dependencies between statements, and generate a random train-valid-test split of theorems, with 1000 valid and test theorems. We use the DAG to ensure that each theorem in the valid or test set is not used to prove another theorem. Moreover, this DAG is used to build a table of forbidden tokens: if the proof of $A$ depends on $B$, we set to zero the probability of generating the token $A$ during a proof-search of $B$. We use a seq2seq training objective, where the model is conditioned on a goal to prove, and is trained to output a sequence of the following format:

LABEL is the label of the rule to apply, MANDATORY_SUBSTS is a serialized version of the substitutions in the rule that cannot be inferred from syntactic parsing of the input goal and the theorem statement. During proof-search, decoding is stopped at the (End Of Useful) token and we do not generate predictable substitutions, as this would unnecessarily increase decoding time and the probability that our model generates invalid substitutions. Training the model to output predictable substitutions and the rule statement serves as a co-training task and helps reduce overfitting. The training set is composed of around 1M goal-tactic pairs; more statistics about the training data are provided in Table 1. Tokenization in Metamath is trivial, as statements are composed of space-separated tokens.

Following , we extract a supervised dataset from the Mathlib library. The training set is composed of 24k theorems and 144k goal-tactic pairs. In addition, we co-train with the dataset of proof-artifacts of Han et al. to reduce overfitting. To facilitate experimentation and reproducibility, we use fixed versions of Lean, Mathlib, and miniF2F (c.f. Appendix D). Finally, we add another supervised co-training task by converting to Lean a synthetic dataset of theorems generated by the Equations environment (c.f. Appendix B.7). In order to avoid hooking into the Lean parser, we tokenize goals and tactics using byte-pair encoding (BPE ) following previous work . Statistics about the training set are available in Table 1.

Unlike Metamath or Lean, the Equations environment does not come with with a dataset of manually annotated proofs of theorems. Instead, we generate supervised data on the fly using the random graph generator described in Appendix B.6. As the model quickly reaches a 100% proving accuracy on these synthetic theorems, there would be no benefit in using them during online training. Thus, we fine-tune on the synthetic dataset, and only leverage statements from the Identities split during online training. As in Metamath, tokenization of statements for this environment is natural, as each statement can be tokenized using the list of symbols from its prefix decomposition .

2 Model pretraining

Model pretraining can be critical in low-resource scenarios where the amount of supervised data is limited . Thus, we do not immediately fine-tune our model but first pretrain it on a large dataset to reduce overfitting and improve generalization. In particular, we pretrain our model with a masked seq2seq objective (MASS ) on the LaTeX source code of papers from the mathematical section of arXiv. After tokenization, our filtered arXiv dataset contains around 6 billion tokens for 40GB of data. Similar to Polu and Sutskever , we observed large performance gains using pretraining. However, we found that arXiv alone provides a better pretraining than when it is combined with other sources of data (e.g. GitHub, Math StackExchange, or CommonCrawl).

3 Model Architecture and Training

Our transformer architecture uses a 12-layer encoder and a 6-layer decoder in all experiments. We use an embedding dimension of 1600 in the encoder and 1024 in the decoder for both Metamath and Lean. For Equations, where we expect the model to require less decoding capacity, the decoding dimension is lowered to 512. We found that reducing the decoder capacity increases the decoding speed without impacting the performance, as previously observed by Kasai et al. in the context of machine translation. Our models are composed of 440M parameters for Equations and 600M parameters for Metamath and Lean (for comparison, GPT-f uses a 770M parameter, 36-layer model).

During fine-tuning, we train our models with the Adam optimizer and an inverse square-root learning rate scheduler . We use a dropout of 0.2 to reduce the overfitting of our models. We also apply layer-dropout with a dropout rate of 0.1 to further reduce overfitting and stabilize training. We implement our models in PyTorch and use float16 operations to speed up training and to reduce the memory usage of our models.

During online training, we alternate between the goal-tactic objective, used during fine-tuning on the supervised dataset, and the goal-tactic and goal-critic objectives on data generated by the provers. As the model and the data generated by the provers are constantly evolving, we do not want the learning rate to decrease to 0, and we fix it to $3\times 10^{-5}$ after the warm-up phase. Unless mentioned otherwise (e.g. for large experiments), we run all Metamath and Equations experiments with 16 trainers and 32 provers for a total of 48 V100 GPUs.

4 Evaluation settings and protocol

In Polu et al. , the model is fine-tuned on theorems from the training set and expert iteration is done on theorems from different sources: train theorems, synthetic statements, and an extra curriculum of statements without proofs (miniF2F-curriculum). The produced model is then evaluated on unseen statements, namely the validation and test splits of the miniF2F dataset .

In this work, we also consider the transductive setup: on a corpus of unproved statements available at train time, how many proofs can our method learn to generate? This protocol is also sensible, as allowing the model to learn from a failed proof-search can lead to more focused exploration on the next attempt, proving more statements overall than a model that would not be trained online.

Following , we also evaluate the pass@k by running $k$ proof searches on the evaluated statements with the policy and critic obtained by online training. In the transductive setup, we also report the cumulative pass rate, i.e. the proportion of theorems solved at least once during online training.

Results

In this section, we present our results and study the moving parts of our pipeline through ablations. Each experiment is run on a single environment (e.g. Lean, Metamath, or Equations). We compare our model with GPT-f which represents the state of the art on Metamath and Lean.

In Lean, we run our experiments on A100 GPUs with 32 trainers and 200 provers. Each prover runs our Lean API on 48 CPU cores. Unlike Polu et al. , we sample statements equally from mathlib-train and miniF2F-curriculum, to avoid giving too much importance to statements from a different domain than the target. After 1 day of training (i.e. $(200+32)$ A100 days of compute), each statement from miniF2F-curriculum has been sampled on average $250$ times, and $110$ out of the $327$ statements have been solved. Our model outperforms GPT-f on miniF2F-test, with an approximately $10\times$ training time speed-up. After $7$ days, we solve $139$ statements of miniF2F-curriculum ($100$ for GPT-f), and observe further improvements on miniF2F-valid or miniF2F-test.

For other evaluations, we depart from the set-up of Polu et al. , directly using the statements from the miniF2F-valid split in our online training, obtaining 58.6% cumulative pass rate. We then evaluate the final model on miniF2F-test, reaching 41% pass@64, against 36.6% for GPT-f.

Without the synthetic data co-training task, the performance drops to $54.9\%$ cumulative pass rate on the miniF2F-valid split, and $38.5\%$ pass@64 on the miniF2F-test split. Examples of proofs found by our model can be found in Appendix F.

1.2 Metamath

On Metamath, we train our model on V100 GPUs, with 128 trainers and 256 provers, whereas ablations are run on 16 trainers and 32 provers. We report our results in Table 3 for the supervised model and for a model trained with online training. During online training, we sample equally statements from the training and from the validation splits of set.mm.

Online training dramatically improves performances on valid statements, going from a $61\%$ pass@8 to a cumulative pass rate of $82.6\%$ on this split. This improvement cannot solely be explained by the high number of attempts on validation theorems during training. Indeed, the ablation in Figure 7 (right) shows that Evariste significantly outperforms a supervised model with the same number of attempts. The supervised model plateaus at $66\%$ while Evariste keeps improving beyond $74\%$ after 7 days of training, showing that the model is able to learn from previous proof searches through online training.

On test theorems, for which statements were not provided during online training, the pass@32 accuracy increased by $10\%$ compared to the supervised model, from $55.8\%$ to $65.6\%$. Note that the supervised model already obtains an accuracy of $65.4\%$ (resp. $61.2\%$) on the validation (resp. test) split, compared to GPT-f’s $56.5\%$ (resp. $56.2\%$) after expert iteration, showing the benefits of HTPS.

1.3 Equations

In Equations, we run our main experiment with 32 trainers and 64 provers, whereas ablations are run on 16 trainers and 32 provers. In this environment, the model easily learns the training distribution of our random generator, and solves all synthetically generated problems. Thus, online training is run on the Identities statements only. Our main experiment reaches a cumulative pass rate of $91.3\%$ on the Identities split, while a supervised model never exceeds $36\%$ even after a similar number of proof attempts. In Appendix 9, we give examples of Identities statements proved during online training, as well as the size and depth of proofs found by the model.

In particular, Evariste managed to find the proof of complex mathematical statements, such as $\sinh(x/2)=\sinh(x)/\sqrt{2(1+\cosh(x))}$ and $\tan(3x)(1-3(\tan(x))^{2})=3\tan(x)-(\tan(x))^{2}\tan(x)$ that required 82 and 117 proof steps respectively, showing the abilities of HTPS to prioritize subgoals and guide the search in very large proof graphs. This shows that online training is able to adapt our policy and critic models to a completely new domain, going from automatically generated statements to identities found in math books. Examples to understand the gap between these two domains can be found in Appendix B.

2 Ablation study

In this section, we present an ablation study on several components of our system. Since Lean experiments are CPU intensive, we run most of our ablations on the Equations and Metamath environments. On Lean, we ran experiments on a smaller subset of hyper-parameters that consistently performed well on the other environments.

The way we filter tactics sent to the trainers has a large impact on final performances. We investigated several filtering methods and report the results in Table 4. The first method is similar to the one used in AlphaZero and exposed in : we select all nodes of the proof search hypergraph where the visit count is above a certain threshold and we filter tactics above a given search policy score. At training time, tactics are sampled according to the filtered search policy. With this method the model reaches 51.6% pass@8 on the valid set of Metamath and 37.5% cumulative pass rate on Equations.

We then experimented with other filtering criteria, selecting only goal-tactic pairs that are part of proofs: either a proof of the root node, or of any solved node in the hypergraph. Then, we learn from all possible proofs, or only from proofs that are minimal according to a criteria (number of proof steps for Equations and Metamath, cumulative CPU time for Lean).

Learning only from the minimal proofs always leads to improved performance, regardless of the selected roots. Learning from the minimal proofs of all solved nodes, we reach a cumulative pass rate of 78.1% on Equations, compared to 40.6% when learning from all proofs. On Metamath, only learning from the root’s minimal proof gives the best result on the validation set, reaching a pass@8 of 68.6%.

2.2 Critic

To measure the impact of our critic model, we run an experiment where the proof search is only guided by the policy model. During the back-propagation phase, we set $v_{T}(g)$ to $0.5$ for the leaves of $T$. In that context, our model is no longer trained with a critic objective. We run this experiment for both Equations and Metamath, and report the results in Table 5. In both environments, using a critic model improved the performance significantly, by $5.2\%$ and $12.5\%$ on Metamath and Equations respectively.

As mentioned in Section 5, to train the critic objective, we set the training targets as $c(g)=1$ for solved nodes, $c(g)=0$ for invalid nodes and $c(g)=W(g,t^{*})/N(g,t^{*})$ where $t^{*}$ is the tactic that maximizes the search policy at $g$., for internal nodes. We also tested a hard critic estimation of the target values, following Polu and Sutskever , where $c(g)=1$ for solved nodes and $c(g)=0$ for both invalid and internal nodes. We report results in Table 5. For both Metamath and Equations, estimating the critic target of internal nodes with the HTPS action value estimate allows Evariste to reach its best performance. In Equations, the model reaches a cumulative pass rate of 78.1%, compared to 63.1% with hard critic estimates. In Equations, using hard critic targets gives worse performances than having no critic model at all, showing that these targets are a bad estimation: setting all internal nodes to zero is too pessimistic.

2.3 Fixed proof search parameters

We study the impact of sampling HTPS hyper-parameters for each attempt during online training. We run experiments with fixed, chosen search parameters for Equations and Metamath to compare with random sampling, and report results in Table 5. Evariste achieves better performances than the model trained with fixed search parameters on Metamath test set and Equations Identities, reaching 78.1% pass rate compared to 73.8% in Equations Identities.

2.4 Model update frequency during online training

In our online training procedure, the policy and critic models are updated every five minutes on the provers. We measure the impact of the frequency of these updates by trying different refresh rates: 5 minutes, 1 hour, 6 hours for Equations, and no updates at all for both Equations and Metamath. We report the cumulative pass rate over training hours in Figure 7. The higher the refresh rate, the better the cumulative pass rate over time, confirming the benefits of online training over expert iteration.

Conclusion

In this work, we introduce HTPS, an AlphaZero-inspired proof search algorithm for automated theorem proving, along with an online training procedure. We run an extensive study of our pipeline, and present state-of-the-art results on multiple proving environments. We show that online training provides large speed-ups over expert iteration, and allows generalization of the policy and critic models to completely new domains. Despite large number of attempts per theorem, proving the entirety of datasets like miniF2F remains elusive, and generating data from proof-search on the currently available corpora will likely be insufficient in the long term. As manually annotated formal datasets are limited, another way of providing exploration and additional training data (in the spirit of self-play for two player games) is required. Automated generation of new theorems is likely to be one of the future milestones.

We thank the Meta AI and FLARE teams for useful comments and discussions throughout this work, notably, Faisal Azhar, Antoine Bordes, Quentin Carbonneaux, Maxime Darrin, Alexander Miller, Vincent Siles, Joe Spisak and Pierre-Yves Strub. We also thank the members of the Lean community for their help, notably Fabian Glöckle for valuable feedback on this project.

References

Appendix A Proof search in more details

We begin with some useful notations and concepts for our hypergraphs.

Formally, let $\mathcal{G}$ be a set of nodes, and $\mathcal{T}$ a set of tactics. A hypergraph is a tuple $H=(G,r,T,U)$ with $G\subset\mathcal{G}$ the nodes, $r\in G$ the root, and $T\subset G\times\mathcal{T}\times\mathcal{P}(G)$ the admissible tactics. An element of $T$ is written $(g,t,c)$ where $g$ is the start goal, $t$ is the applied tactic and $c$ is the potentially empty set of children that the tactic creates when applied to $g$ in the proving environment.

Let $S\subset G$ be the set of solved nodes. A node $g\in G\setminus U$ is solved if one of its tactic leads to no subgoals, or one of its tactics leads to only solved nodes. Formally: $\exists(g,t,\emptyset)\in T$ or $\exists(g,t,c)\in T$ such that $c\subset S$. We say that a tactic $t$ is solving for $g$ if all the children it leads to are solved. Conversely, let $U\subset G$ be the set of invalid nodes. A node $g\in G\setminus U$ is invalid if it has been expanded but has no tactics in the hypergraph, or all of its tactics have an invalid child. Formally: $\{(g,t,c)\in T\}=\emptyset$ or $\forall(g,t,c)\in T$, $c\cap I\neq\emptyset$.

These recursive definitions naturally lead to algorithms MaintainSolved and MaintainStatus to maintain sets $S$ and $I$ when elements are added to $H$.

A sub-hypertree $H_{T}$ of $H$ is a connected hypertree rooted at some goal of $H$. Its leaves $\textrm{leaves}(H_{T})$ are its subgoals without children (either elements of $U$ or $S$). The set of proofs of $g$ in $H$, $\textrm{Proofs}(g,H)$ are all the hypertrees rooted at $g$ that have all their leaves in $S$. Similarly, the expandable subtrees of $H$ rooted in $g$, $\textrm{Expandable}(g,H)$ are the subtrees with at least one leaf in $U$. A tactic is said to be expandable if it is part of an expandable subtree, this can be computed with a graph-search ComputeExpandable.

We can now reformulate the process of proof-search. Starting from a hypergraph that contains only the root theorem $r$, we produce a sequence of expandable subtrees. The unexpanded leaves of these subtrees are expanded in the hypergraph, then the new value estimates are backed-up. The hypergraph grows until we use all our expansion budget, or we find a proof of $r$.

A.2 Policies

When a goal $g$ is added to the hypergraph, its visit count $N(g,t)$ and total action value $W(g,t)$ are initialized to zero. Its virtual visit count $VC(g,t)$ are updated during proof search. Let $C(g,t)=N(g,t)+VC(g,t)$ be the total counts. These values are used to define the value estimate with a constant first play urgency :

Notice that the value of solving tactics decreases with virtual counts, allowing exploration of already solved subtrees.

Given the visit count $N$, the total counts $C$, value estimates $Q$, the model prior $P_{\theta}$ and an exploration constant $c$. The policy used in Alpha-Zero is PUCT:

Notice that more weight is given to the value estimate $Q$ as $N$ grows which decreases the second term. Another work obtains good performances using as search policy the greedy policy regularized by the prior policy.

Again, note that this policy balances the prior with the value estimates as the count grows, but does not account for individual disparities of visits of each tactics. In our experiments, we obtained better performances with $\pi_{RP}$ on Equations, and better performances with $PUCT$ on Metamath and Lean.

A.3 Algorithms

During simulation, we only consider subtrees that could become proofs once expanded. This means we cannot consider any invalid nodes or consider subgraphs containing cycles. If we encounter a tactic that creates a cycle during a simulation, this tactic is removed from the hypergraph, virtual counts from this simulation are removed and we restart the search from the root. This may remove some valid proofs, but does not require a backup through the entire partial subtree which would lead to underestimating the value of all ancestors. Removing tactics from the hypergraph also invalidates computations of expandable tactics. This is dealt with by periodically calling MaintainExpandable if no valid simulation can be found. A full description of the algorithm that finds one expandable subtree is available in Algorithm 1. Selection of nodes to expand requires finding expandable subtrees until a maximum number of simulations is reached, or no expandable tactic exists at the root.

The policy model produces tactics for an unexpanded node $g$. These tactics are evaluated in the proving environments. Valid tactics are filtered to keep a unique tactic (e.g. the fastest in Lean) among those leading to the same set of children. Finally, we add the filtered tactics and their children to the hypergraph. If no tactics are valid, the node is marked as invalid and we call MaintainInvalid. If a tactic solves $g$, the node is marked as solved and we call MaintainSolved.

The backup follows topological order from the leaves of a simulated partial proof-tree $T$, updates $W$ and $N$, and removes the added virtual count. The algorithm is described in Algorithm 2

A.4 Comparison with other search algorithms

This best-first search expands goals one at a time according to a priority-queue of either a value model or the cumulative log-prior from the language model. Since the priority is equal among siblings but strictly decreasing with depth, this means siblings will always be expanded together. However, nothing prevents the algorithm from jumping from one potential proof-tree to another, and potentially favoring breadth over depth. In comparison, depth does not appear in the value estimate we compute, but rather the remaining number of nodes to solve a particular proof-tree. Moreover, our algorithm leads to value estimates that can be used to train our critic, which performs better than 0-1 estimates provided by best-first search (c.f. Section 7.2.2).

MCTS has been famously used as part of AlphaZero to obtain great performances on two player games. This two player set-up can be mapped to theorem-proving by assigning one player to choosing the best tactics while the other player picks the most difficult goal to solve (a method explored in Holophrasm ). However, since we need to provide a proof of the root theorem, we need to ensure that we can solve all goals that a tactic leads to. This set-up has been studied for two player games when attempting to compute the game-theoretical value of positions. Using MCTS in this set-up is suboptimal , ignoring unlikely but critical moves from the opponent (in our case, a subgoal that looks easy but is impossible to solve). We decided to exploit the highly asymmetrical arities of our two players (most tactics lead to one or two goals) which makes simulating partial proof-trees computationally feasible. Thus, the values we back-propagate always take into account all possible moves from the opponent, while only requiring a few expansions per simulation.

Appendix B Equations environment

In this section, we give additional details about the environment Equations. First, we described its main elements, theorems (resp. tactics) in Section B.1 (resp. B.2). Then, we describe a proof in this environment in Section B.3, how numerical expressions are evaluated in Section B.4 and what vulnerabilities this can lead to in Section B.5. Finally, we describe our random theorem generator in Section B.6 and how theorems and their proofs can be translated to Lean in Section B.7.

Each theorem in Equations consists in proving mathematical expressions composed of functions of real numbers, by manipulating and rewriting expressions. A theorem to prove can be an inequality or an equality, conditioned to a set (potentially empty) of initial assumptions. For instance:

Equalities and inequalities are represented as trees with the three following elements:

Leaves: represent a variable, an integer, or a constant (e.g. $\pi$).

A root node: represents a comparison operator, e.g. $=$, $\leq$, $<$, $\geq$, $>$, $\neq$. More advanced comparison operators such as $|$ (divides) are possible when dealing with integers.

B.2 Tactics

Equations allows to deduce equalities and inequalities from simpler subgoals, using elementary rules (i.e. tactics). The environment contains two types of rules: transformations, which consist in matching a pattern in an expression and replacing it by an equivalent expression; and assertions, which consist in asserting that an expression is true. Both types of rules can have assumptions.

A transformation rule (TRule) consists in a set of two expressions, $L$ and $R$, equivalent under a set of assumptions $S$. For instance $\texttt{TRule}(A+B,B+A)$ is the transformation rule stating the commutativity of the addition, namely that $A+B=B+A$ for any expressions $A$ and $B$. Note that in this case, the set of assumption $S$ is empty as the equality always holds. Another example is $\texttt{TRule}(\sqrt{A^{2}},A,[A\geq 0])$ that states that $\sqrt{A^{2}}=A$ provided that $A\geq 0$.

Applying such a rule to an existing equation works as follows:

matching a term $T$ in the expression that has the pattern of $L$

identifying the matching variables and substituting them in $R$

return the resulting equation with the set of hypotheses required for the transformation

Applying $\texttt{TRule}(\sqrt{A^{2}},A,[A\geq 0])$ on this expression will result in two subgoals:

The same expression, where $\sqrt{A^{2}}$ has been replaced by $A$: $e^{x}=e^{x}$

The hypothesis required for the assumption to hold: $e^{x}\geq 0$

More generally, a transformation rule will result in $N+1$ subgoals, where $N$ is the number of hypotheses required by the rule.

An assertion rule (ARule) expresses the fact that an expression is true, provided some hypotheses. It is represented by a main expression, and a set of assumptions sufficient for the main expression to hold. For instance, the rule $\texttt{ARule}(A\leq C,[A\leq B,B\leq C])$ states the transitivity of the partial order $\leq$, i.e. $A\leq C$ provided that there exists an expression $B$ such that $A\leq B$ and $B\leq C$.

Assertion rules do not always have hypotheses, for instance the reflexivity rule $\texttt{ARule}(A=A)$, or the rule $\texttt{ARule}(e^{A}>0)$ stating that $e^{A}$ is positive, for any real value $A$. Note that the two subgoals generated in the previous paragraph ($e^{x}=e^{x}$ and $e^{x}>0$) can be respectively solved by these two assertion rules (i.e. by matching $A=e^{x}$ and $A=x$).

Unlike transformation rules that always result in at least one subgoal (the initial expression on which we applied the transformation), assertion rules will only generate $N$ subgoals, where $N$ is the number of hypotheses. As a result, being able to apply an assertion rule without hypotheses to an expression is enough to close (e.g. solve) the goal. Assertion rules are in fact very similar to rules in Metamath.

In Table 6, we provide the number of Equations rules in different categories. Some examples of transformation and assertion rules are given in Table 7.

B.3 Proving a statement with Equations

In order to prove a theorem with Equations, the user (or automated prover) has to apply tactics on the current expression. A tactic can correspond either to a transformation rule, or to an assertion rule.

For transformation rules, the model needs to provide:

the direction in which the rule is applied (a Boolean symbol, for forward or backward)

an integer that represents the position where the rule is applied

an optional list of variables to specify (c.f. paragraph below)

The direction of the rule indicates whether we want to transform $L$ by $R$ or $R$ by $L$ (e.g. replace $A$ by $\sqrt{A^{2}}$, or the opposite). The position where the rule is applied is given by the prefix decomposition of the input expression. For instance, the prefix notation of $(x+y)+1$ is given by + + x y 1. Applying the commutativity rule $A+B=B+A$ to the expression in position 0 will result in $1+(x+y)$. Applying it in position 1 will result in $(y+x)+1$, since the rule was applied to $(x+y)$. Note that for the commutativity rule, the direction in which we apply the rule does not matter. The list of variables to specify is required when variables in the target patterns are absent from the source pattern. For instance, applying the transformation rule TRule(A,A+B-B) in the forward direction will require to provide the value of $B$.

For assertion rules, the format is simpler. We no longer need to specify a direction or a position (the position is always 0 as the assertion statement must match the expression to prove), but only:

In this case, the list of variables to specify corresponds to variables that appear in hypotheses and that cannot be inferred from the main expression. For instance, to apply the assertion rule $A\leq B\wedge B\leq C\implies A\leq C$, we need to specify the value of $B$. We will then be left with two subgoals: $A\leq B$ and $B\leq C$.

Proving a statement in Equations requires to recursively apply tactics to unproved subgoals, until we are left with no subgoals to prove. An example of proof-tree in Equations is shown in Figure 4. Figure 8 shows an example of proof of the statement $\mathbf{(x-y)-(x+y)+2y=0}$ using rules from the environment. Although simple, this statement already requires 22 proof steps and highlights the difficulty proving complex mathematical identities when using elementary proof steps. In the rest of this appendix, we give more details about how we represent expressions in Equations, how we generate random theorems to provide initial training data, the list of rules we provided to the environment, and the set of expressions we use to evaluate the model.

B.4 True expressions and numerical evaluation

Some theorems are trivial, either because their statements match the pattern of an assertion rule that has no assumptions (e.g. $x^{2}\geq 0$ or $e^{y-x}\neq 0$), or because they do not contain any variable and an exact numerical evaluation can attest that they are true (e.g $(-1)/2<6$ or $1-7/4=-6/8$).

To prevent the model from wasting budget in “uninteresting” branches, we automatically discard generated subgoals that can be trivially verified. However, we only perform numerical verification of expressions without variables when they exclusively involve rational numbers. For instance, we will automatically close subgoals such as $5<(-3)^{2}$ or $\frac{1}{2}>\frac{1}{4}$, but not $e^{1}<e^{2}$ or $\cos(3)\neq 0$. To prove that $e^{1}<e^{2}$ the model will need to use, for instance, an assertion rule such as $A<B\implies e^{A}<e^{B}$ ($1<2$ will then be closed automatically).

B.5 Environment vulnerabilities due to initial numerical approximations

In early implementations of the Equations environment, we found that the model was able to leverage vulnerabilities in the environment to reach a 100% accuracy and to prove any statement. These issues where coming from numerical approximations that were initially allowed during the numerical verification of constant expressions (c.f. Section B.4). To prevent these vulnerabilities, we restricted the numerical verification to rational expressions, in order to have an exact numerical evaluation and to avoid errors due to approximations. We give two examples of vulnerabilities found by the model when expressions were verified with an approximate numerical evaluation.

In Figure 9, the model manages to prove that $2=3$ by using the injectivity of the exponential function, and the fact that for NumPy, $\exp(-\exp(\exp(2)))=\exp(-\exp(\exp(3)))$. Evaluating the left and the right-hand side both numerically evaluate to $0.0$, and the environment incorrectly considered the expression to be valid.

In Figure 10, the model manages to prove that $0\neq 0$ by first proving that $\cos(\pi/2)\neq 0$, and combining this result with the fact that $\cos(\pi/2)=0$. The imprecision came from the NumPy approximation of $\cos(\pi/2)$ in $6.123\times 10^{-17}$, and in particular the fact that $(((\cos(\pi/2)^{0.5})^{0.5})^{0.5})\approx 9.4\times 10^{-3}$, which was considered large enough by our threshold to be considered non-zero. By using this approximation, and the assertion rule $\sqrt{A}\neq 0\implies A\neq 0$, the model was able to conclude that $(((\cos(\pi/2)^{0.5})^{0.5})^{0.5})\neq 0\implies\cos(\pi/2)\neq 0\implies 0\neq 0$.

B.6 Random theorem generator

While Metamath and Lean come with a collection of annotated theorems that can be used for training, Equations does not have an equivalent of manually proved statements. Instead, we generate a supervised training set of theorems to pretrain the model before we start the online training. We propose two simple generation procedures: a random walk, and a graph generation approach.

The random walk is the simplest way to generate a theorem. We start from an initial expression $A_{0}$ and a set of initial hypotheses, both randomly generated following the method of Lample and Charton . Then, we randomly apply an admissible transformation rule on $A_{0}$ to get an equivalent expression $A_{1}$. The process is repeated, to get a sequence $A_{0},A_{1},\dots,A_{N}$ of equivalent expressions. The final theorem consists in proving that $A_{0}=A_{N}$, and the proof corresponds to the sequence of rules sequentially applied. To increase the diversity of generations, and to avoid sampling only rules without or with simple assumptions, we add a bias in the random sampling of rules to over-sample the underrepresented ones.

Because of the simplicity of the random walk approach, the generated theorems usually tend to be very easy to prove, and the model quickly reaches a perfect accuracy on the generated theorems. Moreover, proofs generated by the random walk are only composed of transformation rules. To generate a more diverse set of theorems, we also use a graph generation procedure, that creates a large acyclic graph of theorems, where each node is connected to its children by a rule in the environment. To create such a graph, we proceed as follows. We first generate a set of initial hypotheses, and initialize the graph with a node for each hypothesis. We then randomly apply a transformation or assertion rule on nodes already in the graph.

For instance, if $A\leq B$ and $B\leq C$ are two nodes in the graph, then we can add the node $A\leq C$ using the assertion rule $A\leq B\wedge B\leq C\implies A\leq C$. If $x=y\times(z-1)$ is a node in the graph, we can use the transformation rule $B\neq 0\implies A/B=C\iff A=B\times C$ to add the node $x/y=z-1$, provided that the node $y\neq 0$ is also in the graph. Required hypotheses that are trivially verifiable (e.g. $2>0$ or $e^{-x}>0$) are automatically added to the graph.

B.7 Translating Equations theorems to Lean

To enrich the existing Lean supervised dataset with synthetic data, we built a translator from Equations to Lean. Although Equations statements are easy to translate, proofs can only be translated if they involve rules that also exist in Lean. Since Equations is a modular environment where rules can be specified by the user, we created a collection of Equations rules from existing Mathlib statements. Synthetic theorems can then be generated using the random walk or random graph approaches described in Section B.6, and converted into Lean to augment the existing supervised dataset. Examples of randomly generated Lean proofs are provided in Figure 11.

To allow interfacing Equations and Lean, we automatically parsed Mathlib statements from the Lean library, and extracted theorems with a statement compatible with the Equations environment. Compatible theorems are converted into Equations transformation or assertion rules. Overall, we converted 1702 theorems from the Lean Library into our Equations environment. Details about the number of converted theorems are provided in Table 8.

B.8 Examples of identities solved by the model on Equations

In this section, we give some examples of identities solved by the model. For each statement, we indicate the proof size and the proof depth, for the first proof found by the model, and for the optimal proof. We observe that the first proofs are sometimes very large, with more than 100 nodes, and that the model later manages to find shorter proofs as it improves.

Appendix C Proof Search Hyper-Parameters

HTPS depends on many hyper-parameters: the decoding hyper-parameters of the policy model and the search hyper-parameters. Selecting their optimal values would be difficult in practice, if not impractical, for several reasons. First, the model is constantly evolving over time, and the optimal parameters may evolve as well. For instance, if the model becomes too confident about its predictions, we may want to increase the decoding temperature to ensure a large diversity of tactics. Second, even for a fixed model, the ideal parameters may be goal-specific. If an input statement can only be proved with very deep proofs, we will favor depth over breadth, and a small number of tactics per node. If the proof is expected to be shallow and to use rare tactics, we will want to penalize the exploration in depth and increase the number of tactics sampled per node. Finally, there are simply too many parameters to tune and running each experiment is expensive. Thus, we do not set HTPS hyper-parameters to a fixed value, but sample them from pre-defined ranges at the beginning of each proof.

The decoding parameters and the chosen distribution are the following:

Number of samples: the number of tactics sampled from the policy model when a node is expanded. Distribution: uniform on discrete values $$.

Temperature: temperature used for decoding. Distribution: uniform on range $[0.8,2.0]$.

Length penalty: length penalty used for decoding. Distribution: uniform on range $[0,1.2]$.

Number of expansions: the search budget, i.e. the maximum number or nodes in the proof graph before we stop the search. Distribution: log-uniform with range $$.

Depth penalty: an exponential value decay during the backup-phase, decaying with depth to favor breadth or depth. Distribution: uniform on discrete values $[0.8,0.9,0.95,1]$.

Exploration: the exploration constant $c$ in the policy (PUCT or RT). Distribution: log-uniform with range $[0.01,100]$.

When sampling proof search parameters during evaluation, we use the same distributions than at training time, with two differences: we fix the number of expansions to 5k in Lean and 10k in Metamath.

Appendix D Metamath Lean versions

To compare our models in the same setup while working on this project, we ran all our experiments with a fixed version of Metamath and Lean. In particular, all experiments were run with the following GitHub commits of set.mm, Lean, miniF2F, and Mathlib:

https://github.com/metamath/set.mm: 861bd3552636dcdb9cbc8df59d01b14520c72f82

https://github.com/leanprover/lean/: tag/v3.3.0

https://github.com/openai/miniF2F: 21723db70bbd030e034ed374db74cea4be1bf681

https://github.com/openai/miniF2F/tree/statement_curriculum_learning: c9d827c871aff2ab0f5ec64a0d72e61111a7f072

https://github.com/leanprover-community/mathlib: 9a8dcb9be408e7ae8af9f6832c08c021007f40ec

Appendix E Time vs Depth minimization

In Lean, powerful tactics like ring, linarith, or simp are helpful when it comes to proving theorems, but the model might become over-reliant on these automations and never learn what the underlying arguments of the proofs were. Since these tactics are usually slower than rewrite or apply, we experimented with minimizing the total Lean CPU time of the proof. After 3 days of training, the cumulative pass-rate is higher when minimizing this objective, with $50.4\%$ problems solved on miniF2F-valid, compared to $47.5\%$ with the depth objective. Besides, we found that a model trained to minimize the execution time will reduce the fraction of tactics that timeout by $40\%$. In Table 10 we provide a comparison of the tactic usage for two models trained with different minimization objectives, and we show the average Lean proof execution time in Figure 12.

Appendix F Example Lean proofs

In this section, we show examples of proofs found by our model.