TL;DR
This paper introduces Upper Bound Support (UBS), a novel way to select variables for hashing-based projected model counting. By allowing the support set to include variables outside the original projection set, the authors achieve exponential reductions in support size, enabling state-of-the-art counters to solve hundreds of previously "unsolvable" problem instances while maintaining high-quality upper bounds.
What Problem Does This Paper Address?
Projected model counting is the task of counting how many unique assignments to a specific subset of variables ($P$) can satisfy a Boolean formula. It’s a computationally "hard" problem (#NP-complete) with critical applications in verifying neural networks, analyzing software reliability, and assessing power grid resilience.
Modern tools use hashing-based techniques: they add random XOR constraints to "slice" the solution space into manageable cells. However, these XOR constraints can become massive, choking the underlying SAT solvers. To fix this, researchers previously used Independent Support (IS)—a small subset of $P$ that functionally determines the rest of $P$. While IS helps, it is strictly limited to being a subset of $P$. This paper asks: What if we look for a support set outside of $P$?
Methods
The authors propose a generalization called Upper Bound Support (UBS).
- The Concept: Unlike Independent Support, which requires a two-way functional relationship, a UBS set $U$ only requires a one-sided implication: if two solutions agree on $U$, they must agree on $P$. Crucially, $U$ can contain any variables from the entire formula, not just those in $P$.
- The Benefit: Counting models projected on a UBS provides a provable upper bound of the true projected model count.
- The Algorithm (
FindUBS): Based on Padoa’s Theorem (a classic result in logic regarding definability), the authors developed an iterative algorithm to find a minimal UBS. It systematically tests variables to see if they can be removed while maintaining the "upper bound" property. - The Tool: They integrated this into ApproxMC4, a leading approximate model counter, creating a new workflow called UBS+ApproxMC4.
Datasets
The authors evaluated their approach on a massive suite of 2,632 benchmark instances across four diverse categories:
- BNN: Encodings of Binarized Neural Networks used in robustness verification.
- Circuit: ISCAS benchmarks with added parity constraints.
- QBF-exist: Formulas derived from Quantified Boolean Formula (QBF) competition tracks.
- QBF-circuit: Circuits synthesized using functional synthesis tools like Manthan.
Key Insights and Ideas
- Breaking the Subset Constraint: The most counter-intuitive finding is that projecting onto more or different variables can actually make the problem easier. By looking outside the projection set $P$, you can find a "hidden" support set that is exponentially smaller than any subset of $P$.
- The Power of Upper Bounds: In many engineering fields (like safety verification), a tight upper bound is often just as useful as an exact count. UBS exploits this by trading off exactness for massive gains in scalability.
- Minimalism Matters: A smaller support set leads to "sparser" XOR clauses. Sparser clauses are significantly easier for modern Conflict-Driven Clause Learning (CDCL) SAT solvers to process, which is the primary reason for the observed speedups.
Key Results
- Better Scalability: UBS+ApproxMC4 solved 208 more instances than the standard Independent Support (IS) approach.
- Massive Speedups: On QBF-exist benchmarks, the PAR-2 score (a standard measure of runtime performance) dropped from 7,493 seconds to 5,238 seconds.
- High Quality: Even though UBS provides an upper bound, the results were remarkably tight. The geometric mean of the log-ratio error was only 1.32, meaning the estimates were very close to the true counts.
- Portfolio Power: The authors showed that UBS can solve instances that IS cannot, and vice versa, making it a powerful addition to "portfolio" solvers that run multiple strategies in parallel.
Limitations and Future Work
- Preprocessing Overhead: Finding the UBS set itself requires running a SAT solver. In some cases, the time spent finding the UBS can outweigh the time saved during the counting phase.
- Heuristic Dependency: The quality of the UBS depends on the order in which variables are processed in the
FindUBSalgorithm. The authors noted that better heuristics for variable selection (theChooseNextVarfunction) could further improve results. - One-Sided Guarantees: By definition, this method only provides an upper bound. While the bounds are empirically tight, applications requiring strict lower bounds or exact counts cannot use UBS alone.
Future research will likely focus on optimizing the FindUBS algorithm and exploring how to combine UBS with other sparse hashing techniques to push the boundaries of model counting even further.
Summary updated