Online Machine Learning Techniques for Coq: A Comparison

Liao Zhang, Lasse Blaauwbroek, Bartosz Piotrowski, Prokop Cerný, Cezary Kaliszyk, Josef Urban

Abstract

Interactive Theorem Proving (ITP) in systems like Coq remains a labor-intensive process, requiring users to manually input tactics to navigate complex proof states. While machine learning (ML) has been applied to automate tactic prediction, most existing approaches rely on offline learning, which fails to adapt to the user's immediate context. This paper presents a comparison of online machine learning techniques integrated into Tactician, a plugin for Coq. By learning from proofs in real-time, Tactician provides a seamless interactive experience that leverages the locality of proof similarity. We evaluate approximate $k$-nearest neighbors (via Locality Sensitive Hashing) and Online Random Forests against offline Gradient Boosted Trees, demonstrating that online models can automate over 40% of lemmas in Coq’s standard library.

Introduction

In the Coq proof assistant, users construct proofs by applying tactics that transform a goal into sub-goals until the proof is complete. This process is often grueling. While static ML models can suggest tactics, they suffer from three primary limitations: they do not recognize new lemmas defined during a session, they ignore the specific stylistic "vocabulary" of a local project, and they often require significant computational resources.

To address these issues, we focus on online learning, where the model is updated immediately after every proof step. This approach ensures the "digital sidekick" evolves alongside the user, capturing the specific patterns of the current file or library.

Methodology

Online Learning Algorithms

We implemented two primary online algorithms designed to operate within the constraints of an interactive proof environment:

  1. Locality Sensitive Hashing (LSH) Forest: An optimized $k$-nearest neighbors ($k$-NN) approach. By using hashing to group similar proof states into "buckets," the system achieves near-instant retrieval of relevant tactics without searching the entire database.
  2. Online Random Forests: A custom OCaml implementation that allows for dynamic growth. Unlike traditional forests, this model can split leaf nodes into decision nodes as new data streams in, allowing it to adapt to new proof patterns on the fly.

Feature Engineering

To represent the complex syntax of Coq, we introduced several structural feature extraction techniques:

  • AST Walks: Capturing parent-child relationships within the syntax tree.
  • Top-level Structures: Abstracting complex terms into simplified patterns (e.g., identifying that a conjunction A ∧ B suggests a split tactic, regardless of the specific content of A and B).
  • Premise/Goal Separation: Treating the current goal and the available premises as distinct feature spaces to provide more granular context.

The Persistence Requirement

One unique challenge in ITP is that users frequently "undo" or "redo" steps. To maintain a consistent state, our ML models utilize functional data structures. This ensures that the model's knowledge base can be reverted instantly to match the user's current position in the proof script without requiring re-training.

Experimental Evaluation

We evaluated these techniques using the Coq Standard Library (v8.11), comprising approximately 250,000 proof states. Our primary metric was a chronological evaluation, which simulates a user building the library from scratch. In this scenario, the model only has access to proofs that occurred "earlier" in the library's development.

Key Results

  • Success Rates: The Online Random Forest proved 36.2% of lemmas within a 40-second time limit.
  • Ensemble Performance: By running $k$-NN and Random Forests in parallel (a "union" approach), the success rate increased to 40.4%. This suggests that the models have complementary strengths: $k$-NN excels at retrieving near-exact matches, while Random Forests generalize better across diverse problems.
  • Feature Impact: The introduction of structural features like Top-level Structures improved success rates from 32.7% to 35%.
  • Online vs. Offline: While offline models like XGBoost are powerful, they are currently too slow for real-time interaction. Furthermore, the "locality of similarity"—the fact that proofs in the same file are often similar—gives online models a distinct advantage that static models lack.

Conclusion and Future Work

Our findings demonstrate that online machine learning is a highly effective strategy for interactive theorem proving. The ability to learn from the user's immediate history allows Tactician to provide relevant, context-aware suggestions that outperform static baselines.

Future work will focus on addressing the computational complexity of leaf-splitting in Random Forests and bridging the "semantic gap" by developing features that represent what a tactic does to a proof state, rather than just what the state looks like. Additionally, we aim to explore Online Gradient Boosting to combine the high performance of boosting with the responsiveness of online updates.

Summary updated

Abstract

We present a comparison of several online machine learning techniques for tactical learning and proving in the Coq proof assistant. This work builds on top of Tactician, a plugin for Coq that learns from proofs written by the user to synthesize new proofs. Learning happens in an online manner, meaning that Tactician's machine learning model is updated immediately every time the user performs a step in an interactive proof. This has important advantages compared to the more studied offline learning systems: (1) it provides the user with a seamless, interactive experience with Tactician and, (2) it takes advantage of locality of proof similarity, which means that proofs similar to the current proof are likely to be found close by. We implement two online methods, namely approximate k-nearest neighbors based on locality sensitive hashing forests and random decision forests. Additionally, we conduct experiments with gradient boosted trees in an offline setting using XGBoost. We compare the relative performance of Tactician using these three learning methods on Coq's standard library.
BibTeX
@inproceedings{zhang2021online,
  author = {Liao Zhang and Lasse Blaauwbroek and Bartosz Piotrowski and Prokop Cerný and Cezary Kaliszyk and Josef Urban},
  title = {{Online Machine Learning Techniques for Coq: A Comparison}},
  booktitle = {CICM},
  year = {2021},
  url = {https://openreview.net/forum?id=KC1dWj9bE5B},
}
Figure