This paper, presented at NeurIPS 2018 by researchers from ETH Zürich, introduces fastSMT, a system that learns to automatically generate high-performance strategies for Satisfiability Modulo Theories (SMT) solvers.
TL;DR
The authors treat SMT solving as a tree search problem, using a two-phase approach: first, they train a neural network to learn a policy for selecting solver "tactics," and then they synthesize these decisions into an interpretable, branchable program. This method allows the state-of-the-art Z3 solver to solve 17% more formulas and achieve up to 100× speedups without any modifications to the solver's core engine.
What Problem Does This Paper Address?
SMT solvers are the workhorses of formal verification, scheduling, and program synthesis. To handle complex logic (like bit-vectors or non-linear arithmetic), solvers use "tactics"—heuristic transformations that simplify or restructure a formula before the final search.
The challenge is that there are hundreds of tactics, and their effectiveness depends entirely on the specific formula at hand. Modern solvers allow users to write "strategies" (scripts of tactics), but manually finding the optimal strategy for a specific domain is a "black art" that even experts struggle with. Existing automated attempts either used simple portfolios (picking one of a few pre-set solvers) or evolutionary algorithms that didn't actually "learn" from the structure of the formulas.
Methods
The authors propose a two-step pipeline to tackle this challenge:
1. Learning Candidate Strategies
They frame strategy discovery as a reinforcement learning-style tree search.
- State: The current formula and the sequence of tactics applied so far.
- Action: Choosing a tactic (e.g.,
simplify,bit_blast) and its parameters. - Model: A neural network takes formula features—using "probes" like the number of constants, or embeddings like Bag-of-Words (BOW) and Abstract Syntax Trees (AST)—and predicts the next best tactic. They use the DAgger algorithm to iteratively improve this policy.
2. Synthesizing an Interpretable Strategy
A raw neural network is a "black box" and slow to evaluate during solving. To fix this, they use Decision Tree Learning to convert the learned policy into a symbolic program. This program uses simple if-then-else branches based on formula features (e.g., "if the ratio of inequalities is high, use the Simplex tactic"). This resulting script is written in Z3’s own strategy language, meaning it can be plugged directly into the solver with zero overhead.
Datasets
The approach was evaluated on five diverse benchmarks from the official SMT-LIB repository:
- AProVE & Sage2: Program termination and fuzzing.
- hycomp: Hybrid systems verification.
- core & leipzig: Industrial and academic benchmarks.
- Logics covered: QF_NRA (Non-linear Real Arithmetic), QF_BV (Bit-Vectors), and QF_NIA (Non-linear Integer Arithmetic).
Key Insights and Results
- Interpretability is a Feature, Not a Bug: By synthesizing a symbolic program instead of using the neural network at runtime, the authors ensure the solver remains fast. The solver doesn't have to run a forward pass of a GPU-heavy model for every formula; it just checks a few simple "if" conditions.
- The Power of "Probes": The paper shows that Z3’s built-in "probes" (cheap-to-calculate statistics about a formula) are surprisingly effective features for guiding high-level strategy decisions.
- Strategy as State: One of the most interesting findings was that the sequence of tactics already applied is often as informative as the formula itself. A model that only looked at the "Strategy so far" performed remarkably well compared to models that did deep analysis of the formula's AST.
- Better Coverage and Speed: On the tested benchmarks, fastSMT solved 17.4% more formulas than the default Z3 strategy within a 10-second time limit. For formulas that both could solve, fastSMT was often orders of magnitude faster, reaching 100× runtime improvement in several cases.
- Generalization: The model was trained on "easy" formulas (solvable in 10s) but generalized to "hard" formulas. When given a 600s limit, the learned strategies solved 97.7% of the benchmarks, significantly outperforming the default solver.
- Comparison: As seen in the performance charts, the neural network approach significantly outperformed StratEVO (an evolutionary approach), which often got stuck in local minima or reduced to random search on complex tasks.
Limitations and Future Work
- Tactic Dependency: The system is limited by the tactics exported by the solver. If a solver doesn't have a rich tactic language (like Z3 does), fastSMT has fewer "building blocks" to work with.
- Search Space: While the synthesis phase creates loop-free programs, the authors note that some optimal strategies might require complex loops or recursion, which are harder to synthesize.
- Feature Engineering: While Bag-of-Words and AST features were used, the authors suggest that more advanced Graph Neural Networks (GNNs) might better capture the logical structure of formulas in the future.
Summary updated