Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice

Kuldeep S. Meel, S. Akshay

Abstract

Approximate model counting (#SAT) is a critical yet computationally intensive task in computer science. Traditional methods rely on dense 2-universal hash functions that often overwhelm SAT solvers with complex XOR constraints. This paper presents ApproxMC5, an algorithm that leverages "sparse" hash functions to significantly accelerate computation while maintaining rigorous theoretical $(\epsilon, \delta)$ guarantees. By establishing a novel link between hashing variance and isoperimetric inequalities on Boolean hypercubes, the authors introduce the $H_{Rennes}$ family of sparse hash functions. Empirical results across 1,893 benchmarks demonstrate that ApproxMC5 provides substantial speedups and solves instances previously beyond the reach of state-of-the-art tools.

Introduction

Model counting, the #P-complete problem of determining the number of satisfying assignments for a Boolean formula, is fundamental to fields such as network reliability and hardware verification. To handle its inherent complexity, researchers employ approximate counting techniques. These methods typically use hash functions to partition the solution space into smaller "cells," counting solutions in a single randomly selected cell to estimate the total.

Historically, this approach has utilized 2-universal hashing with dense XOR constraints. However, these constraints—where each variable has a 50% chance of inclusion—create a performance bottleneck for modern SAT solvers. While sparse XORs are more efficient, they have previously lacked the theoretical backing to ensure accuracy. This work bridges that gap by introducing "concentrated hashing."

Methods: Concentrated Hashing and ApproxMC5

The core innovation of this work lies in the formalization of concentrated hashing, which relaxes the requirements of universal hashing without sacrificing reliability.

The Isoperimetric Connection

The authors discovered a mathematical link between the variance of hash functions and isoperimetric inequalities on Boolean hypercubes. By applying results from Boolean functional analysis, they proved that solution sets remain well-distributed even with significantly sparser constraints. This allows for a reduction in the "density" of the hash matrix without losing the concentration of solutions in individual cells.

The $H_{Rennes}$ Family

The researchers designed $H_{Rennes}$, a new family of sparse hash functions. In this family, the probability of a variable appearing in a constraint is approximately $O(\frac{\log m}{m})$, where $m$ is the number of hash bits. This drastically reduces the length of XOR strings, making them easier for Conflict-Driven Clause Learning (CDCL) solvers to process.

Notation for cells and counts in the hashing process.

As shown in the notation table above, the algorithm estimates the total count by analyzing a specific cell $\text{Cell}_{\langle S,m \rangle}$. ApproxMC5 integrates these sparse functions while maintaining the "gold standard" $(\epsilon, \delta)$ guarantees, ensuring the estimated count is within a specified error tolerance with high probability.

Evaluation and Results

The algorithm was tested on a comprehensive suite of 1,893 benchmarks, including real-world problems from probabilistic reasoning, neural network verification, and network reliability.

Performance Gains

ApproxMC5 showed significant runtime improvements over its predecessor, ApproxMC4. Notably, it successfully solved many benchmarks that previously timed out under a 5,000-second limit. The efficiency of the algorithm actually improves as the number of solutions increases, as the density of XORs can be further decreased.

Theory vs. Practice

Empirical data revealed that the actual error observed (approximately 0.05) was much lower than the theoretical bound (0.8). This suggests that the mathematical guarantees are conservative and that the algorithm is even more robust in practice than predicted. The paper confirms that the size of XOR constraints is the primary performance killer for modern solvers, and that sparsity is a safe, effective remedy.

Conclusion and Future Work

ApproxMC5 represents a major step forward in scalable model counting by proving that sparsity is safe. By replacing dense bottlenecks with lightweight constraints, the authors have made complex counting tasks more accessible. Future research aims to refine the theoretical constants and develop "universal" sparse constructions that work optimally for sets of any size. Beyond model counting, the concept of concentrated hashing holds promise for fields like data streaming, discrete integration, and cryptography.

Summary updated

BibTeX
@inproceedings{meel2020sparse,
  author = {Kuldeep S. Meel and S. Akshay},
  title = {{Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice}},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394809},
}
Figure