GANAK: A Scalable Probabilistic Exact Model Counter

Shubham Sharma, Subhajit Roy, Mate Soos, Kuldeep S. Meel

Abstract

Model counting, or #SAT, is a fundamental problem in computer science with applications ranging from probabilistic reasoning to network reliability. However, its #P-complete complexity makes it notoriously difficult to scale. This paper introduces GANAK, a scalable "probabilistic exact" model counter that bridges the gap between precise but slow exact counters and fast but imprecise approximate counters. By combining probabilistic component caching (PCC) with novel search heuristics, GANAK achieves state-of-the-art performance, solving significantly more instances than previous tools while maintaining a mathematically guaranteed high confidence in its results.

Introduction

The goal of model counting is to determine the exact number of satisfying assignments for a given Boolean formula. Unlike the decision problem (SAT), which asks if any assignment exists, #SAT asks how many. This increased complexity makes it a bottleneck for critical tasks like calculating event likelihoods in complex systems or evaluating decision paths in planning.

Historically, solvers have been divided into exact counters (e.g., sharpSAT) and approximate counters (e.g., ApproxMC3). GANAK introduces a middle ground: a probabilistic exact counter. It provides the exact count with a user-defined confidence level, allowing for massive memory savings and performance gains without sacrificing accuracy in practice.

Methods and Innovations

GANAK is built upon the architecture of sharpSAT but incorporates several transformative features:

  1. Probabilistic Component Caching (PCC): Traditional counters store entire sub-problems (components) in RAM to avoid redundant calculations. GANAK instead stores a compact hash of these components using $\epsilon$-universal hash families. This reduces memory overhead significantly, enabling a much larger cache.
  2. Search Heuristics:
    • CSVSADS: A branching heuristic that steers the search toward variables not currently represented in the cache.
  3. Independent Support (IS): Identifies a minimal subset of variables that determine the values of all others, focusing the solver's efforts.
  4. Learn and Start Over (LSO): A strategic restart mechanism that improves variable ordering after initial exploration.
Heatmap of PAR2 scores showing the performance impact of combining PCC, CSVSADS, IS, and LSO. Lower scores (redder) indicate better performance.

The synergy between these components is vital. As shown in the heatmap above, the combination of Independent Support and Probabilistic Caching (top-right quadrant) yields the lowest PAR2 scores, indicating the most efficient runtimes.

Experimental Evaluation

The authors evaluated GANAK against a suite of 2,031 benchmarks from domains such as circuit analysis, logistics, and probabilistic reasoning.

Key Results

  • Scalability: GANAK demonstrated superior performance by solving 1,587 instances, outperforming sharpSAT (1,519) and the approximate counter ApproxMC3 (1,165).
  • Speed: The solver achieved a runtime reduction of approximately 12-17% compared to sharpSAT.
  • Empirical Accuracy: In all experimental trials, GANAK's probabilistic count was identical to the true exact count, validating the robustness of its hashing approach.
Cactus plot comparing the number of instances solved vs. CPU time for GANAK, SharpSAT, and ApproxMC3. GANAK (green circles) solves the most instances within the 5,000s time limit.

Discussion and Future Work

GANAK's success highlights that deterministic caching is not a prerequisite for exact model counting. By accepting a negligible, mathematically bounded risk of error, solvers can overcome the memory walls that previously limited exact counting.

Future research directions include extending these techniques to weighted model counting and integrating GANAK's heuristics into knowledge compilation frameworks like d-DNNF. While GANAK is highly effective, the authors note that certain benchmarks still favor approximate methods, suggesting that future "meta-solvers" could benefit from dynamically switching between exact and approximate strategies based on problem characteristics.

Summary updated

Abstract

Given a Boolean formula F, the problem of model counting, also referred to as #SAT, seeks to compute the number of solutions of F. Model counting is a fundamental problem with a wide variety of applications ranging from planning, quantified information flow to probabilistic reasoning and the like. The modern #SAT solvers tend to be either based on static decomposition, dynamic decomposition, or a hybrid of the two. Despite dynamic decomposition based #SAT solvers sharing much of their architecture with SAT solvers, the core design and heuristics of dynamic decomposition-based #SAT solvers has remained constant for over a decade. In this paper, we revisit the architecture of the state-of-the-art dynamic decomposition-based #SAT tool, sharpSAT, and demonstrate that by introducing a new notion of probabilistic component caching and the usage of universal hashing for exact model counting along with the development of several new heuristics can lead to significant performance improvement over state-of-the-art model-counters. In particular, we develop GANAK, a new scalable probabilistic exact model counter that outperforms state-of-the-art exact and approximate model counters sharpSAT and ApproxMC3 respectively, both in terms of PAR-2 score and the number of instances solved. Furthermore, in our experiments, the model count returned by GANAK was equal to the exact model count for all the benchmarks. Finally, we observe that recently proposed preprocessing techniques for model counting benefit exact model counters while hurting the performance of approximate model counters.
BibTeX
@inproceedings{sharma2019ganak,
  author = {Shubham Sharma and Subhajit Roy and Mate Soos and Kuldeep S. Meel},
  title = {{GANAK: A Scalable Probabilistic Exact Model Counter}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/163},
}
Figure