GamePad: A Learning Environment for Theorem Proving

Daniel Huang, Prafulla Dhariwal, Dawn Song, Ilya Sutskever

Abstract: In this paper, we introduce a system called GamePad that can be used to explore the application of machine learning methods to theorem proving in the Coq proof assistant. Interactive theorem provers such as Coq enable users to construct machine-checkable proofs in a step-by-step manner. Hence, they provide an opportunity to explore theorem proving with human supervision. We use GamePad to synthesize proofs for a simple algebraic rewrite problem and train baseline models for a formalization of the Feit-Thompson theorem. We address position evaluation (i.e., predict the number of proof steps left) and tactic prediction (i.e., predict the next proof step) tasks, which arise naturally in tactic-based theorem proving.

Introduction

Theorem proving represents a "grand challenge" for artificial intelligence, requiring a unique blend of rigid symbolic reasoning and human-like intuition to navigate vast search spaces. While automated solvers excel at low-level logic, they often lack the high-level guidance necessary for complex mathematical proofs. Interactive Theorem Provers (ITPs) like Coq bridge this gap by allowing human-computer collaboration. However, Coq's architecture was not originally designed for integration with modern deep learning frameworks.

To address this, we present GamePad, a learning environment that treats theorem proving as a structured "game." GamePad provides a programmatic interface to extract data from Coq and interact with it as a reinforcement learning environment, enabling the training of models that can predict subsequent proof steps or estimate the remaining distance to a completed proof.

The GamePad Framework

GamePad introduces several technical innovations to make formal logic amenable to deep learning. It functions as a patch to the Coq interpreter, logging "proof traces" that include intermediate states, tactics used, and underlying Abstract Syntax Trees (ASTs).

Figure 1: A Coq proof script (left) and its corresponding state-space graph (right) as represented in GamePad.

Key methodological features include:

  • Interpreter-Inspired Embeddings: Rather than treating mathematical statements as raw text, GamePad utilizes the tree structure of the logic. To handle arbitrary variable names, we employ a "random vector" technique where variables are assigned stable random vectors within their local scope, allowing models to learn functional roles rather than specific identifiers.
  • Computational Optimizations: To manage massive proof trees, we implemented embedding sharing (memoizing sub-trees) and dynamic batching. These optimizations resulted in a 190x speedup on GPU hardware, making large-scale training feasible.

Datasets and Tasks

We evaluate our framework on two distinct scales:

  1. Synthetic Algebraic Rewrites: A dataset of 400 generated theorems involving basic algebraic identities, used to test end-to-end proof synthesis.
  2. The Feit-Thompson Theorem: A real-world formalization of a landmark result in group theory, containing over 83,000 proof states.

Our models focus on two primary tasks: Position Evaluation, which predicts the number of steps remaining in a proof, and Tactic Prediction, which identifies the most likely next command.

Experimental Results

Our experiments demonstrate that deep learning models can effectively capture the structure of formal proofs. On the Feit-Thompson dataset, TreeLSTM and GRU models achieved approximately 68% accuracy in position evaluation and 60% accuracy in tactic category prediction.

Table 2: Performance comparison of baseline models on position evaluation (Pos) and tactic prediction (Tac) tasks.

In the end-to-end synthesis task for algebraic rewrites, a model using a greedy search strategy successfully generated complete, valid proofs for 14 out of 50 test cases without human intervention. We also observed that "mid-level" proof representations, which omit some of Coq's internal bookkeeping, perform as well as lower-level representations, suggesting that models can effectively ignore certain types of formal "noise."

Conclusion and Future Work

GamePad successfully bridges the gap between formal verification and machine learning. While current results are promising, significant challenges remain. Future work will explore more sophisticated search strategies, such as Monte Carlo Tree Search (MCTS), to improve proof synthesis. Additionally, improving "argument synthesis"—the ability to select specific lemmas or variables for a tactic—remains a critical hurdle for automating more complex mathematical reasoning.

Summary updated

Abstract

In this paper, we introduce a system called GamePad that can be used to explore the application of machine learning methods to theorem proving in the Coq proof assistant. Interactive theorem provers such as Coq enable users to construct machine-checkable proofs in a step-by-step manner. Hence, they provide an opportunity to explore theorem proving with human supervision. We use GamePad to synthesize proofs for a simple algebraic rewrite problem and train baseline models for a formalization of the Feit-Thompson theorem. We address position evaluation (i.e., predict the number of proof steps left) and tactic prediction (i.e., predict the next proof step) tasks, which arise naturally in tactic-based theorem proving.
BibTeX
@inproceedings{huang2019gamepad,
  author = {Daniel Huang and Prafulla Dhariwal and Dawn Song and Ilya Sutskever},
  title = {{GamePad: A Learning Environment for Theorem Proving}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=k2aHUXosFpY},
}

Loading related content...

Figure