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:
- 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.
- 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 ∧ Bsuggests asplittactic, regardless of the specific content ofAandB). - 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