Projected Model Counting: Beyond Independent Support

Jiong Yang, Supratik Chakraborty, Kuldeep S. Meel

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$.

Table illustrating the exponential gap between the size of a projection set ($x_i$) and a potential Upper Bound Support ($y_j$).

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

Abstract

The past decade has witnessed a surge of interest in practical techniques for projected model counting. Despite significant advancements, however, performance scaling remains the Achilles' heel of this field. A key idea used in modern counters is to count models projected on an \emph{independent support} that is often a small subset of the projection set, i.e. original set of variables on which we wanted to project. While this idea has been effective in scaling performance, the question of whether it can benefit to count models projected on variables beyond the projection set, has not been explored. In this paper, we study this question and show that contrary to intuition, it can be beneficial to project on variables beyond the projection set. In applications such as verification of binarized neural networks, quantification of information flow, reliability of power grids etc., a good upper bound of the projected model count often suffices. We show that in several such cases, we can identify a set of variables, called upper bound support (UBS), that is not necessarily a subset of the projection set, and yet counting models projected on UBS guarantees an upper bound of the true projected model count. Theoretically, a UBS can be exponentially smaller than the smallest independent support. Our experiments show that even otherwise, UBS-based projected counting can be more efficient than independent support-based projected counting, while yielding bounds of very high quality. Based on extensive experiments, we find that UBS-based projected counting can solve many problem instances that are beyond the reach of a state-of-the-art independent support-based projected model counter.
BibTeX
@inproceedings{yang2022projected,
  author = {Jiong Yang and Supratik Chakraborty and Kuldeep S. Meel},
  title = {{Projected Model Counting: Beyond Independent Support}},
  booktitle = {ATVA},
  year = {2022},
  doi = {10.1007/978-3-031-19992-9\_11},
}
Figure