Abstract
This paper presents a novel decision procedure for determining the satisfiability of quantified formulas in linear arithmetic. By framing the problem as a game between two players—SAT and UNSAT—the authors introduce a strategy improvement algorithm that avoids the computational bottlenecks of traditional quantifier elimination. The resulting tool, SIMSAT, demonstrates superior performance on a variety of benchmarks, particularly those involving complex quantifier alternations where standard SMT solvers often struggle.
Introduction
Satisfiability Modulo Theories (SMT) solvers have become indispensable tools in formal methods, providing efficient reasoning for "ground" formulas. However, many critical tasks in program verification, synthesis, and planning require the use of universal ($\forall$) and existential ($\exists$) quantifiers. Handling these quantifiers remains a significant challenge.
Historically, solvers have relied on two main techniques: Quantifier Elimination (QE) and Heuristic Instantiation. QE transforms a formula into an equivalent quantifier-free version, but the process is often subject to an exponential or even doubly-exponential increase in formula size, making it impractical for large-scale problems. Conversely, heuristic instantiation is fast but incomplete, frequently failing to provide a definitive answer for complex formulas. This paper introduces a "lazy" approach to quantifier elimination through strategy improvement, providing a complete procedure for Linear Rational Arithmetic (LRA) and Linear Integer Arithmetic (LIA) that scales to industrial-sized problems.
Methodology: Strategy Improvement and Game Semantics
The authors' approach is rooted in Game Semantics. A quantified formula is interpreted as a game played between two opponents:
- Player SAT aims to prove the formula true by selecting values for existential variables.
- Player UNSAT aims to prove the formula false by selecting values for universal variables.
The Strategy Improvement Loop
Instead of exploring the entire infinite domain of real or integer values, the algorithm operates on "strategy skeletons"—finite sets of candidate terms. The procedure follows an iterative loop:
- Proposal: Player SAT proposes a candidate strategy from their skeleton.
- Verification: An SMT solver checks if this strategy is winning. If it is, the formula is satisfiable.
- Counter-Strategy: If the strategy is not winning, Player UNSAT finds a counter-strategy that defeats it.
- Improvement: Player SAT incorporates the counter-strategy to refine their own strategy, ensuring the new version defeats all previous counter-strategies.
This back-and-forth continues until a winning strategy is found or one player is proven to have no possible winning move.
Theoretical Foundations
The efficiency and correctness of this approach rely on two key properties:
- Anti-Symmetry: The authors prove that if one player has a counter-strategy against the other, the reverse cannot be true for the same round. This ensures monotonic progress toward a solution.
- Finite Image Property: This is the most critical theoretical result. It states that for any given formula, the term selection function only ever needs to pick from a finite set of "interesting" terms. This guarantees that the strategy improvement loop will always terminate, making the procedure complete.
Experimental Evaluation
The authors implemented their procedure in a tool called SIMSAT and evaluated it against industry-standard solvers: Z3, CVC4, and Yices. The benchmarks included the SMT-LIB2 library, the Mjollnir suite, and a large set of randomly generated LRA and LIA instances.
As shown in the cactus plot above, SIMSAT demonstrates a significant performance advantage. It scales better than both Z3 and CVC4, solving more instances within the same time limits. Notably, SIMSAT's performance on random benchmarks highlights its robustness where standard heuristics often fail.
The quantitative results in the table above further underscore SIMSAT's effectiveness. On 2,030 random LRA benchmarks, SIMSAT solved 1,881 instances (93%), compared to 1,743 for Z3 and 1,432 for CVC4. In terms of speed, SIMSAT was often orders of magnitude faster; for instance, it could solve as many instances in approximately 5.3 seconds as Z3 could in 300 seconds. The method also successfully extended to Linear Integer Arithmetic (LIA) using virtual substitution, solving 71% of random instances.
Conclusion and Future Work
SIMSAT represents a significant step forward in handling quantified linear arithmetic. By combining game semantics with strategy improvement, it provides a complete and efficient alternative to traditional quantifier elimination.
However, several avenues for future research remain. The algorithm's performance is sensitive to the specific models provided by the underlying SMT solver, suggesting that better model-selection heuristics could further improve efficiency. Additionally, while the finite image property has been established for LRA and LIA, extending this framework to other theories like bit-vectors or non-linear arithmetic remains an open challenge. Finally, the winning strategies generated by SIMSAT could potentially be leveraged for applications in program synthesis and automated controller design.
Summary updated