Abstract
The past decade has witnessed a surge of interest in practical techniques for projected model counting. Despite significant advancements, performance scaling remains a critical challenge. A key innovation in modern counters is the use of an independent support (IS)—a subset of the projection set that functionally determines the remaining variables. While effective, this approach is limited by the constraint that the support must be a subset of the projection set. In this paper, we introduce Upper Bound Support (UBS), a generalization that allows the support set to include variables outside the projection set. We show that a UBS can be exponentially smaller than the smallest independent support, significantly improving performance. Counting models projected on a UBS guarantees a provable upper bound of the true projected model count, which suffices for many applications like neural network verification and power grid reliability. Our experiments on 2,632 benchmark instances demonstrate that UBS-based counting solves hundreds of instances beyond the reach of state-of-the-art IS-based counters while maintaining high-quality bounds.
Introduction
Projected model counting is the task of determining the number of unique assignments to a specific subset of variables, $P$, that satisfy a given Boolean formula. This problem is #NP-complete and underpins critical tasks in formal verification and reliability analysis. Modern approximate counters, such as ApproxMC4, utilize hashing-based techniques that add random XOR constraints to partition the solution space. The efficiency of these solvers depends heavily on the size of the support set used for hashing; smaller sets lead to sparser XOR clauses, which are easier for underlying SAT solvers to process.
Traditionally, researchers have relied on Independent Support (IS), a subset of $P$ that functionally determines all other variables in $P$. However, the requirement that the support must be a subset of $P$ can be a significant bottleneck. This paper explores the counter-intuitive idea that looking "outside the box"—selecting support variables from the entire formula—can lead to massive scalability gains.
Upper Bound Support (UBS): A New Paradigm
We propose Upper Bound Support (UBS) as a more flexible alternative to IS. A set of variables $U$ is a UBS for a projection set $P$ if any two satisfying assignments that agree on $U$ must also agree on $P$. Unlike IS, $U$ does not need to be a subset of $P$.
While counting over a UBS may over-count the true projected models, it provides a rigorous upper bound. In many engineering contexts, such as safety verification, a tight upper bound is often as valuable as an exact count. The primary advantage of UBS is the potential for a dramatic reduction in support size.
Theoretical Foundations and Exponential Scaling
Theoretically, a UBS can be exponentially smaller than the smallest IS. Consider a projection set $P = \{x_1, x_2, \dots, x_{n-1}\}$ where only one variable can be true at a time. An independent support would require all $n-1$ variables. However, if the formula includes auxiliary variables $y_1, \dots, y_{\log_2 n}$ that represent the binary encoding of the active $x_i$, then the set of $y$ variables constitutes a UBS of size $\log_2 n$.
To find these sets in practice, we developed the FindUBS algorithm. Based on Padoa’s Theorem—a classic result in logic regarding definability—the algorithm iteratively tests variables to identify a minimal set that maintains the upper bound property.
Experimental Evaluation
We integrated UBS into the ApproxMC4 framework and evaluated it against a massive suite of 2,632 benchmark instances across four categories: Binarized Neural Networks (BNN), circuits with parity constraints, and two classes of QBF-derived formulas.
Key findings include:
- Increased Coverage: UBS+ApproxMC4 solved 208 more instances than the standard IS-based approach.
- Performance Gains: On QBF-exist benchmarks, the PAR-2 score dropped from 7,493 seconds to 5,238 seconds.
- High Bound Quality: The estimates were remarkably tight, with a geometric mean log-ratio error of only 1.32.
- Portfolio Synergy: UBS solved many instances that IS could not, suggesting that a portfolio approach combining both strategies is highly effective.
Conclusion
By relaxing the subset constraint of traditional independent support, Upper Bound Support enables a new level of scalability in projected model counting. The ability to find exponentially smaller support sets allows modern solvers to tackle complex verification problems that were previously intractable, providing high-quality bounds with significantly reduced computational effort.
Summary updated