TL;DR
This paper presents MizAR 60, an AI/TP system that significantly advances automated theorem proving for the Mizar Mathematical Library (MML). It achieves impressive results, automatically proving 60% of Mizar theorems in a "hammering" setting and 75% when aided by human-selected premises, marking a substantial improvement over previous benchmarks.
What Problem Does This Paper Address?
The paper tackles the challenge of automating the proving of mathematical theorems within the Mizar Mathematical Library (MML). MML is a vast and complex formalization of mathematics, and while automated theorem provers (ATPs) have made progress, achieving high proof rates for its theorems remains a significant hurdle. Previous evaluations, like the Mizar40, showed that only around 40-56% of theorems could be proven automatically. This paper aims to push these boundaries, leveraging recent advancements in machine learning and AI to build a more powerful AI/TP system capable of tackling a larger portion of MML.
Methods
The core of MizAR 60 is the ENIGMA system, an "Efficient Learning Based Inference Guiding Machine." ENIGMA employs several key techniques:
- Learning-Guided ATP: ENIGMA integrates machine learning models (specifically Gradient Boosted Decision Trees and Graph Neural Networks) to guide the search process of ATPs like E and Vampire. These models learn from existing proofs to prioritize promising clauses and strategies.
- Premise Selection: A crucial component is learning-based premise selection. The system learns to identify the most relevant facts (premises) from the MML for proving a given conjecture. This is done using methods like k-Nearest Neighbors (k-NN), Naive Bayes, and Recurrent Neural Networks (RNNs), and more advanced techniques like GBDTs and GNNs for dependent selection.
- Multi-Phase ENIGMA: To handle computationally expensive ML models, a multi-phase approach is used. A faster model filters clauses, and only those that pass are evaluated by a slower, more powerful model.
- Robust Portfolios: The system constructs portfolios of complementary strategies. Instead of simply combining the best, a robust method is used to mitigate overfitting by randomly splitting development sets and evaluating portfolio performance.
- Incremental Prove-Learn Loop: A core experimental methodology involves an iterative loop where the system proves theorems, uses the generated proofs to train stronger ML models, and then uses these improved models to prove more theorems.
Datasets
- Mizar Mathematical Library (MML): The primary dataset used is the Mizar Mathematical Library. The experiments utilize MML version 1147 for most evaluations, and a newer version (MML 1382) for transfer learning experiments.
- ATP Proof Corpora: The system leverages large corpora of automatically generated ATP proofs extracted from ITP libraries. For training premise selection, a dataset of 638,293 unique ATP proof dependencies was created, significantly larger than previous datasets.
Key Insights and Ideas
- The Power of "Anonymous" ML: The paper highlights that their logic-aware ML methods, which learn from the structure of mathematical problems rather than specific terminology, are remarkably robust to new concepts and lemmas. This is a significant finding in contrast to large language models that often struggle with novel vocabulary.
- Synergy of ML and ATP: The research demonstrates a powerful synergy between machine learning and automated theorem proving. ML models don't just guide the search; they learn to select relevant premises and even synthesize parts of proofs, leading to substantial performance gains.
- Importance of Premise Selection: The effectiveness of premise selection is underscored. Providing ATPs with too many irrelevant facts hinders their performance, making intelligent selection a critical factor for success.
- Incremental Learning is Key: The prove-learn feedback loop is essential for continuously improving the AI/TP system. By iteratively training on newly generated proofs, the system becomes progressively stronger.
Key Results
- 60% Proof Rate in Hammering Mode: The MizAR 60 system can automatically prove 60% of Mizar theorems in a "hammering" setting (where ATPs can use any available premises). This is a significant increase from the 40.6% achieved in the Mizar40 evaluation.
- 75% Proof Rate with Human Premises: When aided by human-selected premises, the system proves 75% of Mizar theorems, up from 56% in Mizar40.
- Transfer Learning Success: The system shows strong performance on a newer version of MML (MML 1382) containing new terminology, outperforming the standard E prover by 58.2% on this new library.
- Single Method Performance: The strongest single AI/TP method alone can prove 40% of lemmas in 30s in hammering mode, matching the performance of the full 420s portfolio from Mizar40.
- Efficient Proof Search: The system can synthesize complex proofs, such as a 619-long proof in 60s, demonstrating efficiency gains.
Limitations and Future Work
- Hardware Dependency: While the authors argue it's not a major issue, the performance of ENIGMA relies on modern hardware, particularly GPUs, for clause evaluation. Research into extracting faster predictors for standard hardware is ongoing.
- Overfitting in Portfolios: While robust portfolio construction methods are employed, there's still a risk of overfitting, which the authors aim to mitigate further.
- New Terminology Handling: While the anonymous ML approach shows promise, the paper notes that large language models typically struggle with new terminology, suggesting an area for future research.
- Automated Strategy Invention: The paper mentions the use of BliStr/Tune for inventing ATP strategies, indicating ongoing work in this area.
- Neural Synthesis of Witnesses: The success in synthesizing witnesses has spurred research into neural synthesis of witnesses and conjectures for AI/TP settings.
Summary updated