A Top-Down Tree Model Counter for Quantified Boolean Formulas

Florent Capelli, Jean-Marie Lagniez, Andreas Plank, Martina SeidlIJCAI 2024

Abstract

This paper introduces d4-QBF, the first model counter capable of handling Quantified Boolean Formulas (QBF) with arbitrary quantifier prefixes. By treating solutions as "tree models" and employing sophisticated caching and decomposition techniques, the authors significantly outperform existing methods and solve complex problems that were previously out of reach.

The Challenge of #QBF

In Boolean logic, Satisfiability (SAT) asks if an assignment exists, while model counting (#SAT) asks how many exist. Quantified Boolean Formulas (QBF) introduce universal ($\forall$) and existential ($\exists$) quantifiers, making the problem significantly harder. A solution to a QBF is not a single assignment but a tree model—a strategy that ensures the formula remains true regardless of the universal player's moves.

A completed tree model representing a winning strategy for a QBF.

While #SAT is well-studied, #QBF (counting these tree models) has remained largely theoretical or limited to simple formulas with only two layers of quantifiers. The challenge lies in the massive search space and the structural dependencies created by the quantifier order.

The d4-QBF Approach

The authors present d4-QBF, a top-down compiler based on the successful D4 #SAT solver architecture. Its key innovations include:

  • Quantifier-Aware Branching: Respecting the quantifier prefix order by branching on outermost variables first to maintain tree model integrity.
  • Component Decomposition: Identifying independent parts of the formula. If a formula can be split, the total count is the product (for universal) or sum (for existential) of the counts of its parts.
  • Canonical Prefix Caching: Using a Shrink function to normalize quantifier prefixes, allowing the solver to recognize and reuse results for sub-problems even if they appear in different contexts.
  • Hybrid Aggregation: Combining results using multiplication for $\forall$ variables and addition for $\exists$ variables.

Key Results

The evaluation on 2QBF and deeply nested "Crafted" benchmarks demonstrates d4-QBF's efficiency. It solved nearly all 2QBF instances and handled formulas with up to 25 quantifier blocks—tasks that existing counters simply could not perform.

Runtime comparison of d4-QBF against baseline and qCounter solvers. Points above the diagonal indicate d4-QBF is faster.

As shown in the runtime comparison, d4-QBF consistently outperforms both the enumerative qcounter and baseline solvers, often by orders of magnitude. On 2QBF benchmarks, it solved all but 10 of 2,586 instances, demonstrating superior speed and robust handling of increasing complexity.

Conclusion

d4-QBF represents a major step forward in QBF reasoning. By extending top-down compilation techniques with quantifier-aware optimizations, it enables the counting of complex tree models in domains like formal verification and synthesis. Future work will explore improved propagation logic and more compact model representations to handle even larger problem instances.

Summary updated

BibTeX
@inproceedings{capelli2024top,
  author = {Florent Capelli and Jean-Marie Lagniez and Andreas Plank and Martina Seidl},
  title = {{A Top-Down Tree Model Counter for Quantified Boolean Formulas}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure