Learning Equational Theorem Proving

Jelle Piepenbrock, Tom Heskes, Mikolás Janota, Josef UrbanarXiv 2021 · arXiv

Introduction

Automated Theorem Proving (ATP) is a fundamental challenge in formal verification and mathematical research. The goal is to navigate an infinite and undecidable search space of logical steps to prove a conjecture. Equational theorem proving—the task of demonstrating that two mathematical expressions are equivalent based on a set of axioms—is particularly difficult for standard machine learning approaches.

Traditional Reinforcement Learning (RL) methods struggle in this domain due to three primary factors:

  1. Sparse Rewards: Feedback is only provided upon successful completion of a proof, offering no guidance for intermediate steps.
  2. Recursive Structures: Mathematical formulas are naturally represented as recursive trees rather than flat vectors, requiring specialized neural architectures.
  3. Data Imbalance: During training, models often discover long, inefficient proofs. Standard RL treats all steps in a successful trajectory as positive signals, which can reinforce suboptimal search behaviors.

Stratified Shortest Solution Imitation Learning (3SIL)

To address these challenges, researchers introduced Stratified Shortest Solution Imitation Learning (3SIL). Unlike standard RL, which often relies on complex value functions to estimate the quality of a state, 3SIL focuses on pure imitation of the most efficient successful outcomes.

The 3SIL Algorithm

The core of 3SIL is a history buffer that stores the $k$ shortest successful proofs found for every problem encountered during training. The model is then trained to imitate these specific actions. This approach bypasses the instability of learning a value function in sparse-reward environments.

Stratified Sampling and Tree Neural Networks

To prevent the model from being biased toward long, complex problems that generate a disproportionate amount of training data, 3SIL employs stratified sampling. This ensures that every solved problem contributes equally to the training process, regardless of its proof length.

Furthermore, the system utilizes Tree Neural Networks (TreeNN). In this architecture, each mathematical operator (e.g., addition, multiplication) is associated with a specific neural module. This allows the model to process the nested, recursive structure of equations effectively, preserving the underlying logic of the mathematical expressions.

Comparison of training progress between 3SIL and standard RL baselines. 3SIL variants reach higher difficulty levels significantly faster.

Experimental Evaluation

The 3SIL method was evaluated across three domains of increasing complexity:

  • Robinson Arithmetic (RA): A foundational theory of non-negative integers.
  • Polynomial Arithmetic: Normalization tasks based on Tarski’s high school axioms, including exponentiation.
  • AIM Conjecture Dataset: A benchmark consisting of approximately 3,500 theorems related to the Abelian Inner Mapping (AIM) Conjecture in quasigroup theory—a significant open problem in mathematics.

Key Results and Insights

The 3SIL-trained model demonstrated superior performance and generalization capabilities compared to both standard RL baselines and hand-engineered systems.

Outperforming Expert Systems

In standalone trials on the AIM dataset, the 3SIL model achieved a success rate of 70.2% within a 60-second limit. This outperformed Waldmeister, a highly optimized, hand-engineered equational prover, which solved 65.5% of the same problems.

Cooperative Speedups

The model also proved highly effective as a "guide" for classical provers. When used to suggest intermediate lemmas for the Prover9 system, the combined approach solved in just 2 seconds what standalone Prover9 required 60 seconds to complete—a 30x speedup.

Generalization Across Difficulties

A critical finding was the model's ability to generalize. Models trained on simpler problems maintained high success rates when tested on "medium" and "high" difficulty conjectures, significantly outperforming standard Behavior Cloning (BC) and previous Monte Carlo Tree Search (MCTS) approaches.

Success rates of 3SIL versus Behavior Cloning (BC) across different problem difficulty levels.

Limitations and Future Work

While 3SIL represents a significant advancement, several challenges remain. Attempts to utilize Transformer architectures—the backbone of modern Large Language Models—failed to converge in this setting. This is likely due to the limited initial data available in theorem-proving environments compared to the massive datasets typically used to train Transformers.

Additionally, the current implementation is specialized for equational reasoning. Extending these techniques to more general first-order or higher-order logic is a key area for future research. Finally, the authors suggest exploring "meta-learning" strategies to identify which proofs are most instructive, potentially moving beyond a simple "shortest-path" heuristic.

Summary updated

Abstract

We develop Stratified Shortest Solution Imitation Learning (3SIL) to learn equational theorem proving in a deep reinforcement learning (RL) setting. The self-trained models achieve state-of-the-art performance in proving problems generated by one of the top open conjectures in quasigroup theory, the Abelian Inner Mapping (AIM) Conjecture. To develop the methods, we first use two simpler arithmetic rewriting tasks that share tree-structured proof states and sparse rewards with the AIM problems. On these tasks, 3SIL is shown to significantly outperform several established RL and imitation learning methods. The final system is then evaluated in a standalone and cooperative mode on the AIM problems. The standalone 3SIL-trained system proves in 60 seconds more theorems (70.2%) than the complex, hand-engineered Waldmeister system (65.5%). In the cooperative mode, the final system is combined with the Prover9 system, proving in 2 seconds what standalone Prover9 proves in 60 seconds.
BibTeX
@misc{piepenbrock2021learning,
  author = {Jelle Piepenbrock and Tom Heskes and Mikolás Janota and Josef Urban},
  title = {{Learning Equational Theorem Proving}},
  year = {2021},
  eprint = {2102.05547},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.05547},
}
Figure