Abstract
We introduce a machine-learning-based tool for the Lean proof assistant designed to suggest relevant premises for theorems during interactive proof construction. The tool prioritizes tight integration with the proof assistant, ease of installation, and a lightweight, high-speed architecture. To achieve this, we implemented a custom Random Forest model directly in Lean 4, leveraging its efficient metaprogramming and general-purpose programming capabilities. The model supports online learning and is trained on data extracted from mathlib. Our results demonstrate that this approach provides low-latency, context-aware suggestions that significantly assist in navigating large mathematical libraries.
Introduction
Formalizing mathematics in a proof assistant like Lean is a complex task, largely due to the "discovery problem." To prove a new theorem, a user must identify which of the tens of thousands of existing lemmas in mathlib are relevant to their current goal. Existing search tools, such as library_search or suggest, typically rely on exact pattern matching. If a lemma is conceptually relevant but does not perfectly match the goal's syntax, these tools often fail. Manual searching is slow and requires significant expertise. This paper addresses the premise selection problem: given a proof state, can we use machine learning to rank the most likely useful premises from the entire library?
System Design and Implementation
Lean 4 as a Machine Learning Platform
A primary innovation of this work is the implementation of the machine learning backend entirely within Lean 4. This demonstrates that Lean 4 is not only a logic engine but also a performant general-purpose language. By avoiding external dependencies (like Python or C++ libraries), we ensure the tool is easy to install and maintains low communication overhead.
The Random Forest Model
We designed a custom Random Forest (RF) model optimized for the premise selection task. Unlike standard "batch" learners, our implementation supports online learning. This allows the model to be updated sequentially as a user writes new proofs, enabling it to learn from a user's current project in real-time without requiring a full retraining cycle.
Featurization
To represent theorems for the ML model, we utilize a bag-of-words approach based on syntactic features:
- Names: Literal names of constants and functions.
- Structural Features: Bigrams and trigrams of symbols appearing near each other in the theorem's syntax tree.
Our experiments found a "sweet spot" using names and bigrams; including trigrams tended to cause overfitting, where the model focused too heavily on specific complex patterns that failed to generalize.
The suggest_premises Tactic
The user interface is provided via the suggest_premises tactic. When called, it displays suggestions in the Lean editor's "infoview." To prevent "hallucinations" or irrelevant suggestions, the tool uses Lean 4’s RPC (Remote Procedure Call) features to asynchronously test suggestions. It attempts to run standard tactics like apply, rw, or simp with the suggested lemmas in the background, highlighting those that successfully advance the proof state.
Evaluation and Results
Datasets
Models were trained on mathlib3port using different filters to define "relevance":
- Source: Only premises explicitly written by the user in the original source code.
- Math: Premises appearing on a curated whitelist of mathematical theorems.
- Intermediate: Proof states extracted from within proofs using
LeanInk.
Performance Metrics
We compared the Random Forest model against a k-Nearest Neighbors (k-NN) baseline. The Random Forest significantly outperformed k-NN in both speed and accuracy:
- Inference Speed: RF generated suggestions in approximately 0.28 seconds, compared to 5.65 seconds for k-NN, making RF much more suitable for interactive use.
- Accuracy: On the
sourcedataset, the RF achieved a Cover score of 0.29. This indicates that for a theorem requiring $n$ premises, nearly 30% of them were found within the model's top $n$ suggestions.
Conclusion and Future Work
This tool provides a lightweight, integrated solution to the discovery problem in Lean 4. By implementing classical ML algorithms directly in the proof assistant, we achieve a balance of performance and usability. Future work will explore the integration of this tool into a full "Lean Hammer" system—combining premise selection with automated theorem provers to solve complex goals automatically. Additionally, while hand-engineered features are efficient, we aim to investigate how modern neural architectures might be integrated without sacrificing the tool's lightweight nature.
Summary updated