Learning to Prove Theorems via Interacting with Proof Assistants

Automated theorem proving (ATP) has evolved from early resolution-based systems like Vampire and E prover to modern neural-guided approaches. Interactive proof assistants such as Coq and Isabelle enable high-level reasoning but depend heavily on human-crafted tactics, limiting automation. Recent efforts incorporate machine learning to generate tactics or guide proof search, exemplified by Gauthier’s TacticToe and Huang’s GamePad. However, these approaches face data scarcity, limited tactic flexibility, and challenges in handling high-order logic. Large, diverse datasets and flexible models are needed to bridge the gap between human reasoning and machine automation, motivating the development of new datasets like CoqGym and models like ASTactic.

Despite progress, fully automated proof systems struggle with complex, high-order proofs due to limited data, rigid tactic sets, and insufficient semantic understanding. Existing models often rely on fixed tactic libraries, restricting their ability to adapt to new problems. The challenge is to develop a scalable, flexible approach that can learn high-level proof strategies from large datasets, generalize across domains, and generate human-like tactics dynamically, addressing the core bottleneck in automating formal reasoning.

This work introduces three key innovations: 1) CoqGym, a large-scale, multi-domain dataset with 71K proofs and rich structural annotations; 2) ASTactic, a deep learning model that generates tactics as program trees conditioned on goal and premise semantics, enabling flexible, context-aware proof strategies; 3) synthetic proof augmentation from intermediate goals, improving model robustness. These innovations collectively overcome the limitations of fixed tactic sets, data scarcity, and shallow reasoning, pushing the frontier of AI-driven proof automation.

• �� Data collection: Extracted 71K proofs from 123 Coq projects, serialized into ASTs, environments, and proof trees.
• �� Model design: Used TreeLSTM to encode goals and premises, then a sequence-to-tree decoder to generate tactic ASTs.
• �� Semantic constraints: Incorporated during decoding to synthesize valid tactic arguments dynamically.
• �� Training: End-to-end supervised learning with augmented short proofs from intermediate goals.
• �� Proof search: Applied depth-first search sampling multiple tactics, executing in Coq environment until proof completion.
• �� Evaluation: Compared success rates against Coq’s auto tactics and external ATPs, across diverse domains.

The dataset was split into training, validation, and test sets, ensuring domain separation. Hyperparameters such as learning rate, batch size, and model depth were tuned based on validation performance. Baselines included Coq’s auto tactics and TacticToe. Metrics focused on proof success rate, number of steps, and generalization to unseen domains. Ablation studies assessed the impact of synthetic data and semantic constraints. The experiments demonstrated that ASTactic significantly outperformed baselines, especially on complex theorems, validating the model’s ability to learn high-level proof strategies.

ASTactic achieved a 12.2% success rate on the test set, surpassing Coq’s internal tactics at 4.9%. When combined with external ATPs, the success rate increased to 30%. Cross-domain tests confirmed strong generalization, with notable improvements on proofs involving high abstraction. Ablation experiments revealed that synthetic proof augmentation and semantic constraints contributed substantially to performance gains, confirming their importance in model robustness.

This approach can automate proof generation in formal verification, mathematical theorem proving, and hardware/software correctness checks. It reduces reliance on manual tactic scripting, accelerates proof development, and enhances reliability. The framework can be integrated into existing proof assistants, providing intelligent proof guidance and enabling large-scale formalization efforts in industry and academia.

Current models have difficulty with very long or highly abstract proofs, indicating reasoning depth limitations. Semantic understanding of domain-specific concepts needs further improvement. Computational costs for training and inference are high, limiting scalability. Future work should focus on improving reasoning capabilities, efficiency, and semantic modeling to address these challenges.