Towards Learning Quantifier Instantiation in SMT

Mikolás Janota, Jelle Piepenbrock, Bartosz PiotrowskiSAT 2022 · OpenReview

TL;DR

This paper introduces a machine learning approach to improve the efficiency of SMT solvers when dealing with quantified formulas. By training a model to rank potential terms for instantiation, they significantly increase the number of problems solved and reduce the computational effort required, outperforming both the base solver and a randomized approach.

What Problem Does This Paper Address?

Satisfiability Modulo Theories (SMT) solvers are powerful tools for verifying software and hardware properties. However, they struggle with formulas containing quantifiers (like "for all x" or "there exists y"). These quantifiers introduce undecidability and high computational complexity, making it difficult for solvers to determine if a formula is satisfiable. A common technique to handle quantifiers is "instantiation," where quantified variables are replaced by specific ground terms. The challenge lies in selecting the right ground terms to instantiate, as an incorrect choice can lead to an explosion of irrelevant terms and computational dead ends. This paper tackles the problem of intelligently guiding this instantiation process using machine learning.

Methods

The core idea is to train a machine learning model to act as a "smart advisor" for the SMT solver's instantiation module. Specifically, they focus on enumerative instantiation, a strategy that systematically generates ground terms to replace quantified variables.

Here's how they integrate ML:

  • Learning to Rank: The ML model's task is to learn a scoring function that ranks candidate ground terms. A higher score indicates a term is more likely to lead to a successful proof or contradiction.
  • Featurization: To train the model, they extract various features from the SMT solver's current state. These include:
  • Procedural Features (P): Information about the solving process itself, like the "age" of a term (when it was introduced) and how many times it has been tried.
  • Bag-of-Words (BOW) Features (B): Counts of different symbol types (variables, operators, etc.) within the quantified expression and candidate terms.
  • Context Features (C): Information about the symbols surrounding the variable in the quantified expression and the "head symbol" of the candidate term.
  • Numeral Features (N): Minimum and maximum numerical values present in the expression and term, useful for arithmetic problems.
  • Parent Label Propagation (P): A technique to label intermediate instantiations as "positive" if they contribute to a final proof, even if they don't immediately lead to a contradiction.
  • Model: They use Gradient Boosted Decision Trees (GBDT), specifically the LightGBM library, due to its speed and effectiveness. This model is trained on previously solved problems to predict whether a given instantiation is likely to be useful.
  • Integration: The ML model's predictions are used to reorder the list of candidate terms for instantiation. This guides the enumerative instantiation process towards more promising terms, aiming to find contradictions or satisfiability faster. The integration is designed to be efficient, allowing predictions to be made quickly during the solving process without significantly slowing it down.

Datasets

The paper uses several standard SMT-LIB benchmarks, categorized into six families: UFLIA boogie, UFLIA grasshopper, UFLIA tokeneer, UFNIA sledgehammer, UFNIA Preiner, and UFNIA vcc havoc. These benchmarks represent various SMT logics, including non-linear and linear integer arithmetic with uninterpreted function symbols, and are derived from formal verification projects. The datasets were split into target (for training) and holdout (for evaluation) sets. No new benchmarks were introduced.

Key Insights and Ideas

  • Quantifiers are a Bottleneck: The paper strongly emphasizes that quantifiers are a major hurdle for SMT solvers, often leading to undecidability or extreme complexity. This makes them a prime target for ML-driven improvements.
  • Learning to Rank is Key: Instead of just filtering out "bad" terms, the ML model learns to rank terms, guiding the solver towards the most promising ones. This is a more nuanced and effective approach than simple elimination.
  • Procedural Features Matter Most: The ablation study reveals that procedural features (like term age and frequency) are crucial for the ML model's success. This suggests that the solver's own internal state and history are highly informative for guiding future decisions.
  • ML as a Smart Advisor, Not a Replacement: The ML component doesn't replace the core SMT logic but acts as an intelligent guide, reordering candidate terms. This preserves the solver's soundness while improving its efficiency.
  • Iterative Improvement is Powerful: The "looping-style" training approach, where the solver is run, data is collected, the model is retrained, and then the solver is run again, creates a positive feedback loop, leading to progressively better performance.

Key Results

The experimental evaluation demonstrates significant improvements:

  • Cumulative Goal: The ML-guided solver consistently solved more problems over multiple training iterations compared to a randomized solver. For the UFLIA-boogie benchmark, the ML-guided solver solved 284.4% more problems cumulatively than the randomized solver.
  • Single-Instance Goal: On unseen problems (holdout set), the ML-guided solver, using the model from the final iteration, also showed improvements. For instance, it solved 290.9% more problems in the UFLIA-boogie benchmark compared to the base solver.
  • Reduced Instantiations: The ML-guided solver significantly reduced the number of quantifier instantiations required to solve problems, as evidenced by scatterplots showing most points below the diagonal.
  • Mixed Results on Time: While instantiations were reduced, the CPU time for solving was not always improved, and in some cases (like UFNIA vcc havoc), it worsened. This is attributed to the overhead of ML prediction, suggesting room for optimization in the ML predictor's efficiency.

Limitations and Future Work

  • CPU Overhead: The ML prediction process introduces a computational overhead, which can sometimes negate the benefits of reduced instantiations, particularly in terms of solving time. Better engineering of the predictor is needed.
  • Specific Logics: While the approach is generic, its performance might be further enhanced by tailoring ML models and features to specific SMT logics.
  • Feature Importance: The ablation study highlights the importance of procedural features. Future work could explore deeper integration of these features or investigate new ones.
  • Beyond Single Variables: The current approach focuses on reordering terms for a single variable at a time. Future work could explore predicting good combinations of terms for tuples of variables.
  • Other Instantiation Methods: The paper primarily focuses on enumerative instantiation. Applying ML guidance to other instantiation techniques (e.g., e-matching, model-based instantiation) is a promising avenue.

Summary updated

Abstract

This paper applies machine learning (ML) to solve quantified satisfiability modulo theories (SMT) problems more efficiently. The motivating idea is that the solver should learn from already solved formulas to solve new ones. This is especially relevant in classes of similar formulas. We focus on the enumerative instantiation - a well-established approach to solving quantified formulas anchored in the Herbrand’s theorem. The task is to select the right ground terms to be instantiated. In ML parlance, this means learning to rank ground terms. We devise a series of features of the considered terms and train on them using boosted decision trees. In particular, we integrate the LightGBM library into the SMT solver cvc5. The experimental results demonstrate that the ML-guided solver enables us to solve more formulas than the base solver and reduce the number of quantifier instantiations. We also do an ablation study on the features used in the machine learning component, showing the contributions of the various additions.
BibTeX
@inproceedings{janota2022towards,
  author = {Mikolás Janota and Jelle Piepenbrock and Bartosz Piotrowski},
  title = {{Towards Learning Quantifier Instantiation in SMT}},
  booktitle = {SAT},
  year = {2022},
  url = {https://openreview.net/forum?id=c17m8p-y6P},
}
Figure