Implementation of Tetris as a Model Counter

Jimmy Dobler, Atri RudraarXiv 2017 · arXiv

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.

Geometric representation of SAT clauses as forbidden regions (boxes) in 3D space.

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.

The merging of constraints in the Tetris algorithm, where individual forbidden regions are combined to define the unsatisfiable space.

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

Abstract

Solving SharpSAT problems is an important area of work. In this paper, we discuss implementing Tetris, an algorithm originally designed for handling natural joins, as an exact model counter for the SharpSAT problem. Tetris uses a simple geometric framework, yet manages to achieve the fractional hypertree-width bound. Its design allows it to handle complex problems involving extremely large numbers of clauses on which other state-of-the-art model counters do not perform well, yet still performs strongly on standard SAT benchmarks. We have achieved the following objectives. First, we have found a natural set of model counting benchmarks on which Tetris outperforms other model counters. Second, we have constructed a data structure capable of efficiently handling and caching all of the data Tetris needs to work on over the course of the algorithm. Third, we have modified Tetris in order to move from a theoretical, asymptotic-time-focused environment to one that performs well in practice. In particular, we have managed to produce results keeping us within a single order of magnitude as compared to other solvers on most benchmarks, and outperform those solvers by multiple orders of magnitude on others.
BibTeX
@misc{dobler2017implementation,
  author = {Jimmy Dobler and Atri Rudra},
  title = {{Implementation of Tetris as a Model Counter}},
  year = {2017},
  eprint = {1701.07473},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1701.07473},
}
Figure