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:
- 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.
- 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.
- 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.
- 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.
- 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.
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.
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