Faster Smarter Proof by Induction in Isabelle/HOL

Yutaka NagashimaIJCAI 2021 · DOI

TL;DR

This paper introduces sem_ind, a tool that automatically suggests the best way to perform proofs by induction in the Isabelle/HOL proof assistant. sem_ind significantly improves upon previous methods by being faster and more accurate, making formal verification more accessible.

What Problem Does This Paper Address?

Formal verification, the process of mathematically proving that software or hardware meets its specifications, is crucial for building trustworthy systems. Proof assistants like Isabelle/HOL are powerful tools for this, but they require users to manually construct complex proofs. Proof by induction is a fundamental technique in this domain, but it's notoriously difficult to get right. Human users must answer tricky questions like "which term should I induct on?", "which variables should I generalize?", and "which induction rule should I use?". Previous tools, like smart_induct, offered some help but were too slow, couldn't handle certain types of induction, and struggled with generalization. This paper addresses the need for a more intelligent, faster, and more accurate tool to guide users through the intricacies of inductive proofs.

Methods

sem_ind tackles this problem through a five-step architecture:

  1. Syntax-Directed Candidate Construction: Instead of trying every possibility (which would be computationally explosive), sem_ind intelligently generates a set of plausible induction arguments by traversing the syntax tree of the proof goal. This approach prioritizes common and effective patterns.
  2. Filtering Unpromising Tactics: sem_ind quickly discards candidate arguments that lead to immediate errors or don't make progress in the proof.
  3. Heuristic Ranking (SeLFIE): The remaining candidates are ranked using 36 pre-defined heuristics encoded in a domain-agnostic language called SeLFIE. These heuristics analyze both the structure of the proof goal and the definitions of relevant functions to assess the quality of the proposed induction.
  4. Generalization Variable Construction: sem_ind explores different combinations of variables to generalize in the induction hypothesis, which is a critical step for making proofs succeed.
  5. Heuristic Ranking for Generalization: A further set of 8 heuristics specifically evaluate the quality of the generalization choices, refining the ranking.

The tool is designed to be seamlessly integrated into the Isabelle/HOL environment, allowing users to apply recommended tactics with a single click.

Datasets

The evaluation of sem_ind was performed on a substantial dataset of 1,095 inductive problems extracted from 22 theory files within the Archive of Formal Proofs (AFP). The AFP is a curated collection of peer-reviewed formal proofs, ensuring the quality and diversity of the benchmark. This dataset is significantly larger and more diverse than those used in previous work.

Key Insights and Ideas

  • The Importance of Definition Analysis: A key insight is that simply looking at the syntax of a proof goal isn't enough. sem_ind's success in handling generalization stems from its ability to analyze the definitions of relevant functions, not just their occurrences in the goal. This allows it to understand how variables change across recursive calls.
  • SeLFIE for Domain-Agnostic Heuristics: Using SeLFIE, a meta-language for encoding heuristics, allows sem_ind to create rules that are applicable across a wide range of problem domains, making it more generalizable than tools relying on domain-specific languages.
  • Balancing Exploration and Pruning: The architecture effectively balances generating a sufficient number of promising candidates (Step 1) with aggressively pruning bad ones (Step 2) and intelligently ranking the rest (Steps 3 & 5). This is crucial for achieving both speed and accuracy.
  • Generalization is Key: The paper highlights that correctly identifying which variables to generalize is a major challenge in inductive proofs, and sem_ind's dedicated heuristics for this are a significant factor in its improved performance.

Key Results

  • Improved Accuracy: sem_ind achieved a coincidence rate of 38.2% for the top recommended candidate, a significant increase from its predecessor smart_induct's 20.1%. This represents a 90.0% increase in accuracy for the most promising suggestions.
  • Faster Execution: The median execution time for sem_ind was 1.06 seconds, a 62.0% reduction compared to smart_induct's 2.79 seconds. This speedup is achieved even with more sophisticated analysis.
  • Better Generalization Handling: sem_ind significantly outperformed smart_induct on problems involving variable generalization, demonstrating the effectiveness of its definition-aware heuristics.

Limitations and Future Work

  • Manual Heuristic Weights: Currently, sem_ind uses manually specified weights for its heuristics. The authors suggest that optimizing these weights using evolutionary computation is a promising future direction.
  • Omission of Simultaneous Induction: The syntax-directed candidate generation intentionally omits certain complex induction strategies like simultaneous induction (used for mutually recursive functions). While the evaluation shows this doesn't hinder performance on common problems, it's a known limitation.
  • Integration into Larger AI Tools: The authors plan to integrate sem_ind into a larger AI tool for Isabelle/HOL, suggesting a path towards more comprehensive automated reasoning assistance.

Summary updated

BibTeX
@inproceedings{nagashima2021faster,
  author = {Yutaka Nagashima},
  title = {{Faster Smarter Proof by Induction in Isabelle/HOL}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/273},
}
Figure