Abstract
We introduce a machine-learning-based tool for the Lean proof assistant that suggests relevant premises for theorems being proved by a user. The design principles for the tool are (1) tight integration with the proof assistant, (2) ease of use and installation, (3) a lightweight and fast approach. For this purpose, we designed a custom version of the random forest model, trained in an online fashion. It is implemented directly in Lean, which was possible thanks to the rich and efficient metaprogramming features of Lean 4. The random forest is trained on data extracted from mathlib – Lean’s mathematics library. We experiment with various options for producing training features and labels. The advice from a trained model is accessible to the user via the tactic which can be called in an editor while constructing a proof interactively.
Introduction
Formalizing mathematics in a proof assistant like Lean is a complex task, primarily due to the "premise selection" problem. Lean’s primary library, mathlib, contains tens of thousands of theorems. When a user is stuck on a proof, they often know a relevant lemma exists but cannot recall its exact name or location. Existing tools like library_search or suggest rely on strict syntactic matching, which often fails if a lemma requires even a slight transformation to apply. This paper presents a statistical machine learning approach to bridge this gap by suggesting likely premises based on the context of the theorem being proved.
Methodology
The authors prioritized speed and ease of installation, choosing two classical machine learning architectures: k-Nearest Neighbours (k-NN) and Random Forest (RF).
Native Implementation in Lean 4
A key innovation is the implementation of these algorithms directly within Lean 4. Leveraging Lean 4's capabilities as a high-performance programming language, the authors created a "native" tool that operates without external dependencies like Python scripts or remote servers. This ensures a seamless, low-latency user experience.
The Random Forest model, illustrated in Figure 2, functions as an "eager" learner. It processes input features through a collection of decision trees to rank potential premises. To make theorems readable by the ML models, they are converted into features using bag-of-words for constants, bigrams, and trigrams of symbols in the expression tree. Interestingly, the authors found that bigrams provided the best balance, while trigrams led to overfitting.
Datasets and Featurization
The primary data source was mathlib (specifically mathlib3port). The training set comprised approximately 2,436 modules, while the testing set included 592 modules. The authors experimented with three distinct filters to define "relevant premises":
- all: Every constant in the proof.
- source: Only premises explicitly typed by the user in the source code.
- math: Only premises appearing in mathlib, filtering out basic logical boilerplate.
As shown in Table 1, the source filter provides a more focused set of premises compared to the all filter, which the authors found to be the most realistic scenario for training.
Results and Discussion
The Random Forest model demonstrated significant performance advantages over k-NN. In terms of speed, RF generated rankings in an average of 0.28 seconds, compared to 5.65 seconds for k-NN. This sub-second response time is critical for interactive use.
In terms of accuracy, using the source filter, the Random Forest achieved a Cover score of 0.29. This indicates that nearly 30% of the necessary premises were found within the top $n$ suggestions (where $n$ is the number of premises in the actual proof). The tool is exposed to users via the suggest_premises tactic, which asynchronously attempts to apply suggested lemmas using tactics like apply, rw, and simp, filtering the results to show only those that advance the proof state.
Conclusion and Future Work
While the current tool provides a lightweight and fast solution for premise selection, several areas for improvement remain. The model is currently theorem-dependent; future iterations aim to make it more proof-state-dependent to assist with intermediate steps. Additionally, while Random Forests are efficient, exploring the integration of Transformer-based models or augmenting datasets with synthetic theorems could further enhance accuracy without compromising the tool's lightweight nature.
Summary updated