Abstract
Randomized hashing algorithms have seen recent success in providing bounds on the model count of a propositional formula. These methods repeatedly check the satisfiability of a formula subject to increasingly stringent random constraints. Key to these approaches is the choice of a fixed family of hash functions that strikes a good balance between computational efficiency and statistical guarantees for a hypothetical worst case formula. In this paper we propose a scheme where the family of hash functions is chosen adaptively, based on properties of the specific input formula. Akin to adaptive importance sampling, we use solutions to the formula (found during the bounding procedure of current methods) to estimate properties of the solution set, which guides the construction of random constraints. Additionally, we introduce an orthogonal variance reduction technique that is broadly applicable to hashing based methods. We empirically show that, when combined, these approaches lead to better lower bounds on existing benchmarks, with a median improvement factor of $2^{13}$ over 1,198 propositional formulas.
Introduction: The Challenge of Model Counting
Model counting, the task of determining the number of satisfying assignments for a Boolean formula, is a fundamental problem in computer science with applications in probabilistic reasoning, planning, and formal verification. However, it is #P-complete, making it computationally much harder than the NP-complete SAT problem.
Current state-of-the-art approximate counters use randomized hashing. They repeatedly add random "parity constraints" (XOR clauses) to the formula to prune the solution space. If you keep adding constraints until only a few solutions remain, you can estimate the total count by looking at how many constraints it took to get there. The challenge lies in the hash functions: dense constraints provide strong statistical guarantees but make SAT problems slow to solve, while sparse constraints are fast but often lead to inaccurate or "loose" lower bounds.
Methodology
The authors propose two main innovations to bridge the gap between speed and accuracy by moving away from fixed, a priori families of hash functions.
1. Adaptive Hashing
Instead of picking variables for parity constraints at random, the authors pick them adaptively. During the counting process, SAT solvers naturally find satisfying assignments. Usually, these are discarded; here, the authors use these solutions to estimate the marginals of each variable (how often a variable is TRUE vs. FALSE across the solution set). Variables with marginals close to 0.5 are prioritized because they are most likely to split the remaining solution set exactly in half, maximizing the pruning efficiency of each constraint.
2. Variance Reduction
The authors introduce an orthogonal technique to reduce estimate variance. Instead of checking if a single "bin" has at least $s$ solutions, they average over $K$ independent realizations. This allows the use of extremely sparse constraints—which are very fast for SAT solvers—while mathematically compensating for the increased noise that sparsity usually introduces.
Key Results
The researchers evaluated their approach on a massive suite of 1,198 non-trivial propositional formulas covering diverse domains such as ISCAS89 combinatorial circuits and functional synthesis.
As shown in the comparison of model count ratios, the combination of adaptive hashing and variance reduction significantly outperforms variance reduction alone. On the benchmark of 1,198 formulas, the adaptive method provided a median improvement factor of $2^{13}$ (8,192x) over the baseline lower bounds. In extreme cases, the adaptive lower bound was tighter by a factor of $2^{100}$.
When compared against exact counts from DSharp, the adaptive approach demonstrates much tighter bounds than standard variance reduction. Notably, the method provided useful bounds for 732 instances where the exact counter timed out after 5,000 seconds. In one challenging example, the proposed method computed a tighter bound 100x faster than the denser baseline by utilizing 10 CPU cores and sparser constraints.
Insights and Future Work
The core "aha moment" is realizing that solutions found by a SAT solver during the bounding process are approximately uniform samples. Treating them as data to guide the algorithm—rather than just a binary signal—provides "free" information about the solution set's geometry. Furthermore, the results suggest that it is often faster to solve multiple easy (sparse) SAT problems and average them than to solve one very hard (dense) problem.
Future directions include exploring more complex variable correlations to further refine hash functions and integrating these adaptive strategies more deeply into the internal heuristics of modern SAT solvers.
Summary updated