On Top-Down Pseudo-Boolean Model Counting

Suwei Yang, Yong Lai, Kuldeep S. Meel

TL;DR

While top-down search-based counters dominate propositional (CNF) model counting, existing pseudo-Boolean (PB) model counters have relied almost exclusively on bottom-up algebraic decision diagrams (ADDs). This paper presents PBMC, the first exact top-down PB model counter, combining CDCL-style pseudo-Boolean reasoning, component caching with gap saturation, and a new coefficient-aware variable decision heuristic (VCIS). PBMC outperforms state-of-the-art bottom-up PB counters and CNF counters on standard benchmarks.

What Problem Does This Paper Address?

Model counting ($#\text{SAT}$) asks: how many variable assignments satisfy a given logical formula? It is a foundational tool for probabilistic inference, network reliability, and hardware verification.

Traditionally, problems must be flattened into Conjunctive Normal Form (CNF), which often blows up formula size. Pseudo-Boolean (PB) formulas—linear inequalities over Boolean variables (e.g., $\sum a_i x_i \ge k$)—can express complex constraints (such as knapsack capacities or cardinality constraints) much more compactly.

In standard CNF counting, top-down search (using DPLL/CDCL search with component decomposition and caching) vastly outperforms bottom-up compilation (which builds decision diagrams like BDDs or ADDs). Surprisingly, state-of-the-art PB counters (such as PBCount and PBCounter) have followed only the bottom-up paradigm. The authors investigate whether a top-down architecture can work effectively for PB model counting and what domain-specific adaptations it requires.

Methods

The authors introduce PBMC, which integrates techniques from PB solvers (RoundingSat), CNF model counters (GPMC), and PB counting:

  1. Top-Down Search & Conflict-Driven Learning: PBMC branches on variables, prunes search spaces using learned PB constraints via cutting-plane-style conflict analysis, and splits independent sub-problems into variable-disjoint components.
  2. Variable Coefficient Impact Score (VCIS): In PB constraints, some variables carry massive coefficients while others carry small weights. Standard CNF decision heuristics ignore coefficients entirely. VCIS calculates an impact score for variable $x$: $$\frac{1}{|\Omega_x|} \sum_{j \in \Omega_x} \frac{b_x^j}{k_j}$$ where $b_x^j$ is the coefficient of $x$ in constraint $j$, and $k_j$ is the constraint degree. Variables with higher scores have a greater influence on the satisfiability gap and are prioritized.

  3. PB Component Caching & Gap Saturation:

  4. A component is uniquely identified by unassigned variable IDs, unsatisfied constraint IDs, and their remaining satisfiability gaps ($s = k - \sum_{\sigma(\ell)=1} a$).
  5. Cache Gap Saturation: If the remaining gap $s$ satisfies $0 < s < \min a_j$ (where $\min a_j$ is the smallest coefficient among remaining unassigned literals), setting any remaining literal to true satisfies the constraint. PBMC clamps the cached gap representation to $\min a_j$, merging isomorphic sub-problems and increasing cache hit rates.

Datasets

The authors evaluated PBMC on a standard benchmark suite of 3,500 PB instances (from Yang & Meel, AAAI 2024):

  • Auction: 1,000 instances modeling combinatorial auctions.
  • M-dim Knapsack: 1,000 instances representing multi-dimensional knapsack problems with diverse coefficients.
  • Sensor Placement: 1,500 instances with mostly unit coefficients ($\pm 1$).
  • Cost-Aware Sensor Placement: A modified variant introduced by the authors incorporating non-unit coefficients to model sensor costs and redundancy.

Key Insights and Ideas

  • Coefficients dictate branching quality: In CNF, all literals in a clause have equal weight. In PB counting, treating literals equally leads to poor branching decisions. Weighting variable decisions by coefficient-to-degree ratios (VCIS) yielded an increase of 115 solved instances in knapsack benchmarks alone.
  • Adapting PB solver saturation to caching: In PB solvers, coefficients larger than the right-hand degree are saturated ($a_i \leftarrow k$). In top-down counting, the reverse applies to the gap: if any single variable can satisfy the constraint, different remaining gap values are logically identical and can share a cache entry.
  • Top-down excels on non-unit coefficients: On formulas where PB constraints are non-trivial (knapsacks, auctions), top-down PBMC significantly outperformed bottom-up ADDs. On unit-coefficient formulas where constraints behave like clauses, bottom-up counters remain highly competitive.

Key Results

Evaluated on single cores of an AMD EPYC 7713 with a 3,600s timeout:

  • Overall Performance: PBMC counted 1,849 instances, beating:
  • PBCount (bottom-up PB): 1,773 instances
  • PBCounter (bottom-up PB): 1,508 instances
  • Ganak (state-of-the-art CNF counter): 1,164 instances
  • Unique Solves: PBMC successfully counted 104 instances that none of the other counters could solve.
  • Ablation of VCIS: Replacing VCIS with standard GPMC heuristics dropped solved instances from 1,849 to 1,772.
  • Ablation of Cache Saturation: Disabling gap saturation dropped solved instances from 1,849 to 1,844.
  • Cost-Aware Sensor Placement: On non-unit sensor placement, PBMC solved 715 instances vs. PBCount's 678.

Limitations and Future Work

  • Narrower Lead than in CNF: Top-down PBMC leads bottom-up PBCount by 76 instances (~4%), a much smaller margin than seen between top-down and bottom-up counters in CNF.
  • Heuristic Sensitivity: While VCIS helped knapsack instances immensely (+115), it lost 38 instances to GPMC's heuristic on Auction problems. Developing adaptive or portfolio-based decision heuristics is an open need.
  • Preprocessing: Top-down CNF counters rely heavily on advanced CNF simplification techniques; top-down PB-specific preprocessors are currently underdeveloped and offer clear room for performance gains.

Summary updated

Abstract

Pseudo-Boolean model counting involves computing the number of satisfying assignments of a given pseudo-Boolean (PB) formula. In recent years, PB model counting has seen increased interest partly owing to the succinctness of PB formulas over typical propositional Boolean formulas in conjunctive normal form (CNF) at describing problem constraints. In particular, the research community has developed tools to tackle exact PB model counting. These recently developed counters follow one of the two existing major designs for model counters, namely the bottom-up model counter design. A natural question would be whether the other major design, the top-down model counter paradigm, would be effective at PB model counting, especially when the top-down design offered superior performance in CNF model counting literature. In this work, we investigate the aforementioned top-down design for PB model counting and introduce the first exact top-down PB model counter, PBMC. PBMC is a top-down search-based counter for PB formulas, with a new variable decision heuristic that considers variable coefficients. Through our evaluations, we highlight the superior performance of PBMC at PB model counting compared to the existing state-of-the-art counters PBCount, PBCounter, and Ganak. In particular, PBMC could count for 1849 instances while the next-best competing method, PBCount, could only count for 1773 instances, demonstrating the potential of a top-down PB counter design.
BibTeX
@inproceedings{yang2025top,
  author = {Suwei Yang and Yong Lai and Kuldeep S. Meel},
  title = {{On Top-Down Pseudo-Boolean Model Counting}},
  booktitle = {SAT},
  year = {2025},
  url = {https://openreview.net/forum?id=a2OYzdGuzM},
}

Loading related content...

Figure