Reinforcement Learning of Theorem Proving

Cezary Kaliszyk, Josef Urban, Henryk Michalewski, Mirek Olšák

TL;DR

Researchers have successfully applied reinforcement learning (RL) to automated theorem proving, achieving a staggering 40% performance boost over traditional methods. By replacing hand-crafted heuristics with Monte-Carlo Tree Search (MCTS) and learned policy/value functions, their system, rlCoP, learns to navigate the vast search space of mathematical proofs more effectively than human-designed algorithms.

What Problem Does This Paper Address?

Automated Theorem Proving (ATP) is the "holy grail" of formal logic, aiming to automatically prove mathematical conjectures from a set of axioms. Traditionally, ATP systems rely on complex, hand-engineered heuristics to decide which "inference step" to take next. Because the search space for a proof is effectively infinite, these heuristics are crucial but often brittle and difficult to design.

The authors tackle the challenge of replacing these human-designed rules with a system that learns from its own successes and failures. They focus on the connection tableau calculus, a specific method for proof search that is compact but highly sensitive to search strategy.

Methods

The authors built a sequence of systems starting from a "bare" prover called mlCoP (an OCaml reimplementation of the leanCoP prover). They then introduced rlCoP, which integrates several key AI techniques:

  1. Monte-Carlo Tree Search (MCTS): Instead of a rigid search, the prover runs many simulations (playouts) to explore different proof paths, balancing exploration of new paths with exploitation of known good ones using the UCT formula.
  2. Policy Learning: A model is trained to predict the probability that a specific inference step will lead to a proof, given the current state of the tableau.
  3. Value Learning: A model estimates the "value" of a proof state—essentially, how likely it is that a proof can be completed from the current configuration.
  4. Feature Engineering: To represent mathematical formulas for the models, they used "term walks" (sequences of symbols in a formula tree) hashed into a fixed-size feature space, alongside abstract features like the number of open goals and path length.
  5. Gradient Boosting: Interestingly, the authors found that XGBoost outperformed deep neural networks for this task, offering better accuracy on their structured features while being significantly faster.
Figure 1: Example of a closed connection tableau, where all branches contain contradictory literals, proving the set of clauses is unsatisfiable.

Datasets

The system was trained and evaluated on large-scale formal proof corpora:

  • Mizar Mathematical Library (MPTP): A massive collection of formalized mathematics.
  • Miz40: A dataset of 32,524 problems that have been previously proved by other state-of-the-art ATPs. The authors split this into a 90% training set and a 10% testing set of previously unseen problems.
  • M2k: A smaller subset of 2,003 problems used for rapid experimentation and hyperparameter tuning.

Key Insights and Ideas

  • Learning to Avoid Infinity: The "bare" prover is technically incomplete because it can get stuck in infinite loops. However, the RL guidance effectively "teaches" the prover to avoid these dead ends, making the theoretical incompleteness irrelevant in practice.
  • The Power of Iteration: The system uses a feedback loop. It attempts to prove theorems, learns from the successful and unsuccessful paths, updates its policy and value models, and then tries again. Performance improved significantly over 20 iterations of this cycle.
  • Policy > Value (Initially): In their experiments, learning which move to make (policy) provided a bigger performance jump than learning how good a state was (value), though combining both yielded the best results.
  • Efficiency Matters: By using XGBoost and efficient feature extraction, the authors kept the "guidance overhead" low. Even though the guided prover performs fewer total inferences per second, the inferences it does make are much higher quality.

Key Results

The results represent a major milestone in the field:

  • 42.1% Improvement: On the unseen test set of the Miz40 dataset, the RL-guided system solved 42.1% more problems than the baseline prover within the same inference limit.
  • Solving the "Unsolvable": The system solved 577 problems that the standard prover could not solve even when given a much higher inference limit (4 million vs. 200,000).
  • Generalization: The system successfully learned general mathematical strategies that applied to new, unseen problems across different domains of the Mizar library.
Figure 2: The MCTS tree for the WAYBEL 0:28 problem at the moment when the proof is found. For each node we display the predicted probability p, the number of visits n and the average reward r = w/n. For the (thicker) nodes leading to the proof the corresponding local proof goals are presented on the right.

Limitations and Future Work

While impressive, the authors note several areas for further research:

  • Feature Representation: While hashed term walks worked well, they are still somewhat manual. Future work could explore deep learning architectures (like Graph Neural Networks) that can automatically capture the syntactic and semantic nuances of mathematical objects.
  • Calculus Limitations: This work is specific to connection tableau. Applying similar RL techniques to other popular calculi, like superposition or SMT, remains an open challenge.
  • Scaling: While 32k problems is "large scale" for ATP, it is small compared to the datasets used in other RL domains like Go or Chess. Scaling to even larger libraries could yield further improvements.

In conclusion, this paper demonstrates that reinforcement learning is a powerful tool for tackling the immense search spaces of formal logic, potentially paving the way for AI assistants that can help mathematicians solve complex, real-world problems.

Summary updated

Abstract

We introduce a theorem proving algorithm that uses practically no domain heuristics for guiding its connection-style proof search. Instead, it runs many Monte-Carlo simulations guided by reinforcement learning from previous proof attempts. We produce several versions of the prover, parameterized by different learning and guiding algorithms. The strongest version of the system is trained on a large corpus of mathematical problems and evaluated on previously unseen problems. The trained system solves within the same number of inferences over 40% more problems than a baseline prover, which is an unusually high improvement in this hard AI domain. To our knowledge this is the first time reinforcement learning has been convincingly applied to solving general mathematical problems on a large scale.
BibTeX
@inproceedings{kaliszyk2018reinforcement,
  author = {Cezary Kaliszyk and Josef Urban and Henryk Michalewski and Mirek Olšák},
  title = {{Reinforcement Learning of Theorem Proving}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=SJW2jubuWS},
}
Figure