Online Machine Learning Techniques for Coq: A Comparison

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

This paper, presented at a recent conference on automated reasoning, explores how to give the Coq proof assistant a "digital sidekick" that learns from users in real-time.

TL;DR

The authors implement and compare online machine learning models—specifically $k$-nearest neighbors and Random Forests—integrated into the "Tactician" plugin for Coq. By learning immediately from a user’s proof steps, these models can automate up to 40% of lemmas in Coq’s standard library, significantly outperforming traditional offline learning approaches.

What Problem Does This Paper Address?

Interactive Theorem Proving (ITP) is a rigorous but grueling process. To prove a mathematical statement in a system like Coq, a human must manually enter "tactics" (commands) to transform the goal until the proof is complete.

While Machine Learning (ML) has been used to suggest these tactics, most existing systems are offline: they are trained once on a massive dataset and then remain static. This creates a disconnect because:

  1. ITP is dynamic: Users constantly define new lemmas and custom tactics that an offline model won't recognize.
  2. Locality matters: Proofs within the same file or project often share a specific style or "vocabulary."
  3. Workflow constraints: An ML assistant must run on a standard laptop, handle "undo" operations (persistence), and provide suggestions in near-constant time.

The authors tackle the challenge of building online models that update their knowledge base the second a user completes a proof step.

Methods

The researchers focused on two primary online algorithms and a suite of new feature engineering techniques:

  • Locality Sensitive Hashing (LSH) Forest: An optimized version of $k$-nearest neighbors ($k$-NN). Instead of searching the entire database (which is slow), it uses hashing to group similar proof states into "buckets" for near-instant retrieval.
  • Online Random Forests: A custom OCaml implementation designed for Tactician. Unlike standard Random Forests, this version can grow new trees and split "leaf" nodes into "decision" nodes as new proof data streams in.
  • Feature Engineering: To help the models "understand" Coq code, the authors introduced several structural features:
  • AST Walks: Capturing the relationship between parent and child nodes in the code's syntax tree.
  • Top-level Structures: Abstracting complex terms into simplified patterns (e.g., recognizing that A ∧ B suggests a split tactic regardless of what A and B actually are).
  • Premise/Goal Separation: Treating the "goal" (what you want to prove) and "premises" (what you already know) as distinct feature spaces.

Datasets

The models were evaluated using the Coq Standard Library (version 8.11).

  • The dataset contains approximately 250,000 proof states.
  • Evaluation was performed in two ways: a standard "Split" (training on one set of modules and testing on others) and a "Chronological" evaluation (simulating a user building the library from scratch, where the model only knows what has been proven "so far").

Key Insights and Ideas

  • The "Persistence" Requirement: Because Coq users frequently navigate back and forth (undoing and redoing steps), the ML models must be "persistent" in the functional programming sense. The authors used functional data structures so that the model's state can be reverted instantly without re-training.
  • Complementary Strengths: Interestingly, $k$-NN and Random Forests often found different proofs. $k$-NN is excellent at finding exact or near-exact matches from the past, while Random Forests are better at generalizing across different types of problems.
  • Online > Offline: The paper demonstrates that "locality of similarity" is a powerful signal. A model that learns from the five proofs you just wrote is often more helpful than a model trained on a million proofs from a different project.

Key Results

  • Success Rates: In the chronological evaluation of the Coq standard library, the Random Forest proved 36.2% of lemmas within a 40-second time limit.
  • The Power of the Ensemble: When running $k$-NN and Random Forest in parallel (a "union" approach), the system proved 40.4% of the lemmas.
  • Feature Impact: The new structural features (like Top-level Structures) provided a measurable boost, increasing the success rate from roughly 32.7% to 35% on their own.
  • Baseline Comparison: While offline Gradient Boosted Trees (XGBoost) are technically more powerful in a static setting, they are currently too slow to be used in an online, interactive loop.

Limitations and Future Work

  • Computational Complexity: The authors noted that as the Random Forest grows, splitting leaves becomes computationally expensive (quadratic complexity), which can occasionally lag the user interface.
  • Semantic Gap: The current features are purely structural (what the code looks like). The authors suggest that future models should use "semantic" features—essentially learning what a tactic does to a proof state, rather than just which state it appears in.
  • Boosting: The next frontier is implementing an Online Gradient Boosting algorithm to see if it can capture the high performance of XGBoost while maintaining the real-time updates required for an interactive assistant.

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},
}

Loading related content...

Figure