This paper introduces STAC (Satisfiability Testing based Approximate Counter), a new hashing-based algorithm for model counting. By replacing slow solution enumeration with simple satisfiability queries and employing a dynamic stopping criterion, the authors achieve speedups of one to two orders of magnitude over state-of-the-art counters while maintaining rigorous theoretical guarantees.
TL;DR
Model counting is a notoriously difficult problem (#P-complete) essential for AI and formal verification. This paper proposes a new algorithm that avoids the bottleneck of counting solutions in small "cells" by instead using simple "is this satisfiable?" queries, resulting in massive speedups without sacrificing accuracy.
What Problem Does This Paper Address?
Model counting (or #SAT) asks: "How many assignments satisfy this set of constraints?" It is the backbone of probabilistic inference, planning, and software reliability analysis. However, it is significantly harder than the standard SAT problem; while SAT asks if any solution exists, #SAT asks for the exact total.
Recent breakthroughs used "hashing-based" counting. These methods use universal hash functions (XOR constraints) to slice the search space into smaller and smaller "cells" until a cell contains a manageable number of solutions. The algorithm then counts the solutions in that one cell and multiplies by the number of cells to estimate the total. The bottleneck? Even counting solutions in a tiny cell (enumeration) is computationally expensive compared to a simple satisfiability check.
Methods
The authors propose STAC, which shifts the paradigm from counting solutions in a cell to simply checking for existence.
- SAT-only Queries: Instead of asking "How many solutions are in this cell?", STAC asks "Is this cell empty?" at various levels of hashing. There is a known probabilistic correlation between the total model count and the probability that a hashed formula becomes unsatisfiable at a specific "depth" (number of hash constraints).
- Iterative Hashing: The algorithm repeatedly adds XOR hash constraints until the formula becomes unsatisfiable. The "depth" at which this happens provides a noisy signal about the total count.
- Dynamic Stopping Criterion: Standard algorithms run for a fixed, theoretically safe number of iterations ($T$). STAC uses the Wilson score interval to calculate confidence intervals in real-time. If the estimate converges within the desired error bounds ($\epsilon, \delta$) early, the algorithm terminates immediately.
- Leap-frogging: To avoid checking every single depth, the algorithm uses a heuristic to "jump" to depths near the expected boundary of unsatisfiability, further reducing the number of calls to the SAT solver.
Datasets
The authors evaluated STAC on a wide range of benchmarks:
- Propositional Logic (CNF): Benchmarks from domains like grid networks, plan recognition, circuit synthesis, and logistics.
- SMT(BV): Satisfiability Modulo Theories for Bit-Vectors, which are common in software verification (e.g., program synthesis tasks).
- Baselines: They compared STAC against state-of-the-art tools including ApproxMC2 (for CNF) and SMTApproxMC (for bit-vectors), as well as several "guarantee-less" counters like SampleCount and MBound.
Key Insights and Ideas
- SAT is Cheaper than Enumeration: The core "aha" moment is that modern SAT solvers are incredibly optimized for finding one solution or proving none exist. By reframing the counting problem as a series of existence checks, the authors tap into the full power of these solvers.
- Theory vs. Practice in Termination: Theoretical bounds for the number of iterations required to guarantee accuracy are often overly conservative. By using a dynamic stopping rule based on binomial proportion confidence intervals, the authors show that you can often stop much earlier than the math suggests while still being correct.
- Universal Framework: Because the method relies on XOR hashes and standard SAT/SMT queries, it is easily adaptable to different logic formats (CNF, SMT, etc.) without changing the underlying probabilistic logic.
Key Results
- Performance: STAC_CNF outperformed ApproxMC2 by approximately one order of magnitude. For SMT(BV) formulas, STAC_BV was one to two orders of magnitude faster than SMTApproxMC.
- Efficiency: The dynamic stopping criterion was highly effective. In tests where the theoretical iteration bound was $T=22$, the algorithm frequently terminated after only ~12 iterations.
- Scalability: The advantage of STAC over previous methods increased as the problem instances grew larger, suggesting it is better suited for industrial-scale verification tasks.
- Accuracy: Despite the speedup, the statistical results fit the theoretical $(\epsilon, \delta)$ bounds perfectly, succeeding within the error margin in roughly 80-90% of trials as predicted.
Limitations and Future Work
- Theoretical Gap: The authors note that while Equation (1) (the link between unsat probability and model count) works perfectly in practice, a rigorous proof for the specific 3-independent hash functions used remains an open challenge.
- "Loose" Formulas: There is a theoretical concern that formulas where almost every assignment is a solution might cause issues, though the authors' tests on extreme "loose" cases (like
special-1) showed the algorithm remained robust. - Generalization: The authors suggest extending this SAT-only approach to other types of constraints beyond propositional logic and bit-vectors as a primary direction for future research.
Summary updated