MizAR 60 for Mizar 50

Jan Jakubuv, Karel Chvalovský, Zarathustra Amadeus Goertzel, Cezary Kaliszyk, Mirek Olsák, Bartosz Piotrowski, Stephan Schulz, Martin Suda, Josef Urban

TL;DR

By combining saturation automated theorem provers (E and Vampire) with graph neural networks, decision trees, and learning-based premise selection, the authors automate proof generation for 58.4% of the Mizar Mathematical Library (MML) in large-theory ("hammer") mode, and over 75% when provided with human-selected premises. This marks a massive leap over the 40.6% / 56% benchmarks established a decade earlier, largely completing a public ten-year challenge on automated reasoning.

What Problem Does This Paper Address?

Interactive Theorem Provers (ITPs) allow mathematicians and computer scientists to construct computer-verified proofs, but doing so is notoriously labor-intensive. "Hammers" automate parts of this process by:

  1. Selecting a small subset of relevant lemmas from massive libraries with tens of thousands of theorems (premise selection).
  2. Passing those premises to first-order Automated Theorem Provers (ATPs) to find a contradiction or formal derivation (internal guidance).

In 2014, researchers bet that by 2024, AI/TP systems would automatically prove 60% of top-level theorems in major libraries like MML and Flyspeck. In 2014, the "Mizar40" benchmark solved only 40.6% unassisted (and 56% with human-annotated premises). This paper evaluates whether a decade of progress in machine learning, strategy invention, and neuro-symbolic guidance can close the gap.

Methods

The authors built an end-to-end learning-and-reasoning pipeline spanning several core components:

  • Internal ATP Guidance (ENIGMA & Deepire): In saturation-based provers like E and Vampire, provers repeatedly pick a "given clause" to infer new clauses. ENIGMA guides E Prover using Gradient Boosted Decision Trees (GBDT via LightGBM) and Message-Passing Graph Neural Networks (GNNs) to prioritize promising clauses. It also employs parental guidance (freezing inferences between parent clauses unlikely to interact) and multi-phase evaluation (fast GBDTs and subsumption indexing pre-filter clauses before passing them to slower GNNs). Deepire adds neural clause guidance to Vampire based on derivation histories.
  • Premise Selection: To filter thousands of background lemmas down to manageable sets, the system combines multilabel classifiers ($k$-NN, Naive Bayes) with binary relevance models (LightGBM and GNNs), aggregated using weighted harmonic-mean ensembling.
  • Subproblem Premise Minimization: Because long human proofs cannot easily be solved in one leap, the authors decomposed them into intermediate natural deduction steps. Successfully proving subproblems reveals exactly which premises were necessary, generating cleaner training dependencies for premise selectors.
  • Prove-Learn Feedback Loops: Systems were trained over millions of proof steps in continuous loops, generating new proofs, retraining models, and using intermediate inferred clauses to restart searches (leapfrogging).
  • Robust Portfolio Scheduling: To avoid overfitting a portfolio of provers and premise-selection slices to development problems, the authors used randomized split-half greedy covers over 1,000 iterations to select the most balanced 420-second schedule.

Datasets

  • Mizar40 / MML 1147 Benchmark: The primary evaluation corpus, consisting of 57,897 first-order logic formulas translated via the MPTP export. To prevent data leakage, it was partitioned using a 90:5:5 split (52,125 training, 2,896 development, and 2,896 holdout problems).
  • MML 1382 (Transfer Benchmark): A significantly newer version of the library featuring 242 new articles and 13,370 unseen theorems, used specifically to evaluate out-of-distribution transfer to novel mathematical vocabulary.

Key Insights and Ideas

  • Anonymous, Logic-Aware ML Naturally Generalizes: Unlike Large Language Models (LLMs)—which often degrade when confronted with novel variable and symbol definitions—the GNN and anonymized GBDT representations abstract away specific names, encoding only structural connectivity and arities. When tested on MML 1382's unseen mathematical concepts, ENIGMA outperformed standard E Prover by 58.2%, proving its representations transfer seamlessly without fine-tuning.
  • Guided Provers Can Synthesize Non-Trivial Witnesses: Guided clause selection enables provers to autonomously assemble constructive mathematical witnesses. For example, in proving that prime numbers are infinite (NEWTON:72), ENIGMA synthesized the witness $n!
  • 1$ from supplied arithmetic facts in just 6 seconds.
  • Multi-Stage Pruning Beats Raw Model Power: Pure neural evaluation inside the main loop of an ATP is prohibitively slow. Employing parental guidance, forward subsumption, and lightweight decision trees pruned up to 70% of redundant clauses before querying the GNN server, making real-time neural proof search viable.

Key Results

  • Bushy Setting (Human Premises): The collective methods proved 75.53% (43,717 problems) across the entire library, up from 56% in Mizar40. A single 3-phase ENIGMA strategy proved 60% in 120 seconds, outperforming the entire 2014 portfolio combined.
  • Hammering Setting (Fully Unassisted): The 420-second, 95-slice portfolio solved 58.36% of the unseen holdout set (and 60.4% on development), approaching the 60% bet target and jumping from Mizar40’s 40.6%.
  • Rapid Single-Strategy Performance: A single GNN-guided strategy proved 39.5% of holdout problems in only 30 seconds—virtually matching the success rate of the entire 420-second Mizar40 ensemble.

Limitations and Future Work

  • Compute Constraints: Running GNN evaluations in real-time required a dedicated Python GPU server managing multiple parallel E Prover instances; GBDT evaluation still suffered from CPU model-loading overheads.
  • Deep Structural Induction: Provers still struggle with inductive proofs spanning hundreds of lines (such as Carmichael’s Theorem on Prime Divisors) unless premise selection fortuitously discovers an alternative non-inductive library lemma.
  • Next Horizons: The authors point toward extracting lightweight, CPU-efficient predictors from GPU-trained models, as well as advancing generative neural synthesis of conjectures and intermediate lemma witnesses.

Summary updated

Abstract

As a present to Mizar on its 50th anniversary, we develop an AI/TP system that automatically proves about 60% of the Mizar theorems in the hammer setting. We also automatically prove 75% of the Mizar theorems when the automated provers are helped by using only the premises used in the human-written Mizar proofs. We describe the methods and large-scale experiments leading to these results. This includes in particular the E and Vampire provers, their ENIGMA and Deepire learning modifications, a number of learning-based premise selection methods, and the incremental loop that interleaves growing a corpus of millions of ATP proofs with training increasingly strong AI/TP systems on them. We also present a selection of Mizar problems that were proved automatically.
BibTeX
@inproceedings{jakubuv2023mizar,
  author = {Jan Jakubuv and Karel Chvalovský and Zarathustra Amadeus Goertzel and Cezary Kaliszyk and Mirek Olsák and Bartosz Piotrowski and Stephan Schulz and Martin Suda and Josef Urban},
  title = {{MizAR 60 for Mizar 50}},
  booktitle = {ITP},
  year = {2023},
  url = {https://openreview.net/forum?id=6TqgktVy2n},
}

Loading related content...

Figure