Abstract
Model counting (#SAT) is a #P-complete problem central to probabilistic reasoning and formal verification. While modern solvers typically rely on search-based DPLL procedures, they often struggle with the high clause density found in structured problems. This paper introduces CNFTetris, an implementation of the Tetris algorithm that treats #SAT as a geometric problem analogous to database natural joins. By employing SIMD-optimized compressed tries and novel variable ordering heuristics, CNFTetris achieves performance gains of several orders of magnitude on large-scale graph benchmarks compared to state-of-the-art solvers.
Introduction
The Boolean Satisfiability problem (SAT) asks whether a formula has at least one satisfying assignment. Its counting variant, #SAT, seeks the total number of such assignments. Despite its theoretical complexity, #SAT is essential for real-world applications like network reliability analysis and planning. Current solvers are often optimized for sparse formulas but falter when faced with "structure-heavy" instances. We bridge this gap by adapting the Tetris algorithm—originally developed for database join optimization—into a practical, high-performance model counter.
Methodology
Geometric Representation
The core innovation of Tetris is the conceptualization of SAT clauses as "forbidden boxes" within an $n$-dimensional hypercube. Each variable represents a dimension, and a clause restricts a specific volume of the search space. A satisfying assignment corresponds to any point not contained within the union of these forbidden regions.
Hardware-Aware Data Structures
To translate this geometric theory into performance, we utilize SIMD-based compressed tries. Traditional implementations use "3-tries" to represent True, False, and $\lambda$ (don't care) states. We optimize this by compressing four logical layers into a single 128-bit "mega-layer." This allows the hardware to process multiple potential solutions simultaneously using SIMD instructions, significantly reducing the overhead of tree traversal.
Heuristic Variable Ordering
The efficiency of the geometric decomposition is highly sensitive to variable ordering. We developed Heuristically Grouped Degree Descent, which prioritizes variables based on their frequency in clauses (degree) while grouping interconnected variables to maintain local structure. This approach minimizes the fragmentation of the geometric space during processing.
Key Insights: The Join-SAT Duality
The fundamental "aha moment" of this work is the realization that computing a natural join in a database is mathematically equivalent to finding satisfying assignments in SAT. Tetris succeeds by focusing on "ruling out" large geometric volumes of incorrect solutions rather than searching for correct ones incrementally.
Furthermore, we found that selective caching is superior to exhaustive caching. By only storing "learned" boxes that cover significant portions of the search space (high $\lambda$ count), we prevent the memory explosion that typically plagues theoretical join algorithms.
Experimental Results
We evaluated CNFTetris against leading counters including sharpSAT, dSharp, and Cachet using both standard SATLIB benchmarks and new graph-based datasets derived from the SNAP collection (e.g., Wikivotes, Facebook).
- Graph Queries: On $k$-clique and $k$-path queries for large networks, CNFTetris completed tasks in 20 to 300 seconds. In contrast, all competing solvers timed out after 40,000 seconds.
- Scalability: CNFTetris demonstrated unique robustness when scaling to formulas with millions of clauses, such as the Soc-Epinions dataset (4.5 million clauses), where traditional unit propagation becomes a bottleneck.
- General Performance: On classic benchmarks like AIS10, CNFTetris remained competitive, typically staying within one order of magnitude of the fastest specialized solvers.
Conclusion and Future Work
CNFTetris demonstrates that geometric, join-based approaches to #SAT are not only theoretically sound but practically superior for structured, clause-heavy problems. Future work will focus on improving the handling of "pure variables" and exploring the application of this framework to MaxSAT and probabilistic graphical models.
Summary updated