Width-Certified Preprocessing for Model Counting

Model counting asks how many assignments satisfy a Boolean formula. Exact counters used in verification, probabilistic inference, and network reliability rely on two tools that work against each other. The first is treewidth, a number measuring how tree-like the formula's variable-interaction graph is. Small treewidth lets a counter run dynamic programming over a tree decomposition, which groups variables into small overlapping "bags" arranged in a tree, in time exponential only in the width. The second is preprocessing, which simplifies the formula before counting. Its most effective rule, bounded variable elimination (BVE), removes a variable by resolving together all clauses that contain it. The trouble is that BVE turns the removed variable's neighbours into a clique, which can raise treewidth and undo the benefit of the later dynamic programming.

This proposal makes preprocessing width-certified. The preprocessor computes a tree decomposition first. It then applies only those rules that provably do not raise its width, and it returns the simplified formula together with an updated decomposition as a certificate. The theory side draws on cross-composition, the standard method for proving that no efficient preprocessing can shrink every instance to size polynomial in a parameter. We use it to state exactly what width-certified preprocessing can and cannot achieve. We also target one counting-specific incompressibility result that the decision literature cannot supply.

Core Claim

Most count-preserving simplification rules are width-safe for free. Width can only grow when a rule adds edges between variables that do not already share a bag. The standard rules sort cleanly by how they change the primal graph, meaning the graph that links two variables when they appear in a common clause. Unit propagation, subsumption, and removal of satisfied clauses delete vertices or edges. Substituting equivalent literals that already share a clause contracts an edge. Treewidth never increases under deletion or contraction, because it is monotone under taking graph minors.

That leaves two unsafe cases: BVE, and merging equivalent variables that never co-occur in a clause. Eliminating a variable $v$ keeps the decomposition's width if every variable sharing a clause with $v$, together with $v$ itself, lies inside a single bag. The resolvents then add edges only within that bag, so the old decomposition, with $v$ removed, still covers the new formula. This test is local. The claim is that restricting BVE and merging to decomposition-compatible choices keeps most of the size reduction that preprocessing gives, while ruling out the width inflation that the SharpSAT-TD authors hint at.

Where the Directions Meet

The motivation comes from the solver literature. Knowledge Compilation and More with SharpSAT-TD compiles formulas into compact circuits under decomposition-guided heuristics. It reports that variable elimination helped "particularly [on encodings] not already optimized for low treewidth." That is indirect evidence that elimination and width optimization can conflict. Preprocessing for Propositional Model Counting introduced the count-preserving pmc preprocessor and showed large runtime gains, but it gave no guarantee about width. Model Counting in the Wild shows that decomposition-based counters pay heavy setup costs, up to 600 seconds for treewidth heuristics. That cost argues for reusing one decomposition across preprocessing and counting rather than recomputing it. Neither solver paper, as described in the file, certifies width, and establishing whether SharpSAT-TD's elimination already respects its decomposition is our first measurement.

Cross-composition sets the ceiling. Limits of Preprocessing proved that constraint satisfaction parameterized by treewidth has no polynomial kernel, meaning no polynomial-time shrinking to size polynomial in the width, unless NP ⊆ coNP/poly. Kernelization of Counting Problems supplies the counting machinery. It defines a reduce-and-lift compression, which shrinks the instance and recovers the original count from the small instance's count in polynomial time. It also defines EXACT-cross-composition, used to show that #Min (s,t)-Cut is incompressible under treewidth.

One point needs saying plainly: the obvious gap, "#SAT by treewidth has no polynomial compression," is close to trivial. OR-composing CNF formulas with $\log t$ selector variables adds only $\log t$ to the width, which proves decision SAT by treewidth incompressible. Any reduce-and-lift compression for #SAT would decide SAT, so the counting bound follows. We will write this down as the ceiling for width-certified preprocessing: no rule set can guarantee output size polynomial in the width. The achievable goal is therefore shrinking the number of variables while holding width fixed, not polynomial kernels.

The genuinely counting-specific question lies where decision is easy. Take #monotone-2-CNF, equivalently counting independent sets in a graph, parameterized by treewidth. Its decision version is trivially satisfiable, so decision lower bounds say nothing about it. Yet implication-heavy 2-CNF fragments are exactly what remains after unit propagation on many encodings. We will attempt an EXACT-cross-composition in the style Lokshtanov et al. used for #Min (s,t)-Cut. The plan is a selector gadget of width $O(\log t)$ plus padding variables, so that the composed count encodes each instance's count in a separate block of bits. The hard technical point is building that selector within 2-CNF, where a naive "exactly one of $t$" constraint forms a clique of width $t$. If a direct construction fails, the fallback is a SUM-cross-composition, conditional on the SUM-conjecture from the same paper.

Research Program

The work has three parts, and the measurement comes first because it can kill the idea. Part one quantifies width inflation. On the benchmark suites below, we compute a heuristic decomposition width before and after pmc (in both its equivalence-preserving and count-preserving modes) and after SharpSAT-TD's own preprocessing. The decomposition heuristic and time budget are fixed. We record how often width rises and by how much.

Part two builds the width-certified preprocessor. It has the following steps:

  1. Compute one time-bounded decomposition.
  2. Apply the minor-monotone rules freely.
  3. Apply BVE only when the eliminated variable's neighbourhood fits in one bag.
  4. Apply non-adjacent literal merging only when both variables share a bag.
  5. Hand the updated decomposition directly to the counter, so there is no second decomposition pass.

We will prove the safety lemma: output width is at most input width, and the model count is preserved. We will also study a greedy ordering that prefers eliminations lying in leaf bags.

Part three is the cross-composition work above. It comprises the simple ceiling theorem and the attempted counting lower bound for independent sets by treewidth.

Baselines

The naive reference point is SharpSAT-TD run on unpreprocessed input, which isolates what any preprocessing contributes.

The strongest existing method is SharpSAT-TD with its default built-in preprocessing, the top individual exact counter in the file. On the non-projected instances of the wild suite it solved 811 of 1,080 (Model Counting in the Wild). On the knowledge-compilation suite it solved 1,727 instances, against 1,656 for d4 (Knowledge Compilation and More with SharpSAT-TD). For reference, the virtual best solver across six counters solved 2,106 of 2,262 wild-suite instances.

The second external baseline is pmc placed in front of SharpSAT-TD. Preprocessing for Propositional Model Counting reports that pmc cut C2D's total time on SATLIB from over 123,000 to about 53,000 seconds, and let Cachet solve 132 additional instances.

Every configuration runs under the same conditions:

  • the same machine and per-instance timeout;
  • the same decomposition heuristic and decomposition time budget;
  • the same downstream counter;
  • the same preprocessing time cap;
  • preprocessing time included in reported runtime.

Beating SharpSAT-TD default means solving more non-projected instances than it does under identical conditions, with a lower penalized average runtime. Beating it also requires strictly lower output width on the instances where default preprocessing inflated width. A tie in solved count paired with smaller compiled circuits counts as a partial win.

Two ablations isolate the key ingredient. The first is unrestricted BVE with the same elimination budget, which shows what the bag-containment test costs in size reduction. The second is BVE followed by a global check: after each batch of eliminations, recompute the heuristic width and revert the batch if it grew. This ablation separates the value of a local certificate from the value of merely avoiding inflation.

Why not just…?

Why not just recompute treewidth after preprocessing and roll back if it grew? This is the most serious alternative, and it is the second ablation. Its weakness is cost and granularity. Decomposition heuristics can take hundreds of seconds, per the 600-second overhead reported in Model Counting in the Wild, so checks must be batched. A rejected batch throws away harmless eliminations along with harmful ones. If batched rollback matches our solved counts and runtimes, the contribution shrinks to the safety theorem and the measurement study, and we will report it that way.

Why not just skip preprocessing on instances that already have low width? A per-instance switch between "preprocess" and "don't" can be modelled as the better of the naive and default configurations on each instance, an oracle upper bound for any such switch. If width-certified preprocessing cannot beat that oracle, the conflict between preprocessing and width is a scheduling problem rather than a rule-design problem.

Why not just use approximate counting, which sidesteps exact decompositions? Model Counting in the Wild finds hashing-based and compilation-based counters complementary rather than interchangeable. In domains such as quantitative information flow, exact compilation counters succeed where ApproxMC struggles. Applications that need exact counts or compiled circuits remain, and our experiments stay within that regime.

Why prove lower bounds at all if heuristics work in practice? The ceiling tells us what guarantee to aim for. Because no rule set can reach size polynomial in the width, "never raise the width, shrink the variable count" is the strongest worst-case promise available. The counting-specific result for independent sets would show that 2-CNF residues, which decision preprocessing discards as trivial, carry incompressible counting hardness. That is a concrete reason counting preprocessors cannot simply copy SAT preprocessors.

Proposed Experiments

We use three benchmark suites:

The metrics are:

  • solved instances;
  • penalized average runtime, with preprocessing time included;
  • heuristic width before and after preprocessing;
  • reduction in the number of variables;
  • compiled circuit size for the compilation runs.

The first decisive check is the inflation study. If default preprocessing raises heuristic width on only a negligible fraction of instances, and the inflated instances are not among those SharpSAT-TD fails to solve, the premise is wrong and we stop the algorithmic line. The second check is the head-to-head against SharpSAT-TD default and against batched rollback on the wild non-projected subset, broken down by domain. Gains should concentrate in the domains where inflation was measured, and a uniform gain would suggest a confound such as saved decomposition time. The third check is theoretical: we either obtain the EXACT-cross-composition for counting independent sets by treewidth, or we document precisely where the width-$O(\log t)$ selector fails in 2-CNF. That boundary is informative in its own right for counting kernelization.