Certified Decimation for Hashing-Based Model Counting

Counting the satisfying assignments of a Boolean formula (model counting, or #SAT) underlies probabilistic inference and quantitative verification. The most scalable counters with guarantees work by adding random parity (XOR) constraints that split the solution set into small cells, counting one cell with a SAT solver, and scaling the result up. Their weak point is well documented: solving the combined clause-plus-parity formula takes over 90–99% of runtime, and that cost grows with the number of variables the parities range over. A separate tradition from SAT solving, iterative decimation, does the reverse. It runs a message-passing algorithm to estimate how strongly each variable leans toward true or false, permanently fixes the most confident ones, simplifies the formula, and repeats. Decimation shrinks problems quickly, but it throws away every solution on the unchosen side, so it has been unusable for counting.

We propose a way to make decimation lossless for counting. Before fixing a literal, the counter checks whether the solutions it would discard number at most a small budget $T$. If they do, it enumerates and counts them exactly with a plain SAT solver, which needs no parity constraints and is therefore the cheap kind of query. Only then does it fix the literal. The remaining, smaller formula is handed to a standard hashing counter. Since the discarded mass is counted exactly, the final estimate keeps the hashing counter's $(\epsilon,\delta)$ guarantee whether or not the message-passing marginals are accurate. Bad marginals cost time, never correctness. In two sentences: use decimation to strip out variables that are nearly fixed across all solutions, pay for each one by exactly counting the few solutions it would remove, and run hashing only on what is left. This removes near-frozen variables from the hash support, which existing support-reduction methods cannot do because those variables are not logically determined by the others.

Core Claim

Let $F_0 = F$, and let $\ell_1,\dots,\ell_t$ be the literals accepted by decimation, with $F_i = F_{i-1} \wedge \ell_i$ after simplification. Writing $M(\cdot)$ for the number of models projected onto the counting support, the exact identity

$$M(F) \;=\; M(F_t) \;+\; \sum_{i=1}^{t} M(F_{i-1} \wedge \neg \ell_i)$$

holds for any sequence of literals. We accept $\ell_i$ only if a budgeted enumeration shows $M(F_{i-1}\wedge\neg\ell_i) \le T$, which makes every term in the sum exact. If $\hat M_t$ is an $(\epsilon,\delta)$ estimate of $M(F_t)$, then adding exact nonnegative terms leaves the relative error within $(1+\epsilon)$ with the same confidence $1-\delta$. The estimate $\hat M_t + \sum_i M(F_{i-1}\wedge\neg\ell_i)$ is therefore an $(\epsilon,\delta)$ approximation of $M(F)$. The empirical claim is that on many structured and near-threshold instances, a large share of the independent support is near-frozen, meaning a literal holds in all but a handful of solutions. Removing those variables makes the remaining parity constraints shorter and the cells better balanced. The result should be more instances solved than the best hashing pipeline at equal time, with the same accuracy guarantee.

Relation to Prior Work

The decimation side supplies the mechanism and also motivates the safety-net design. Survey-propagation-guided decimation, as described by Aurell et al., freezes variables that keep the same value throughout a solution cluster, and it finds those variables without first needing any solution. Wainwright shows that one-shot assignment of many variables cascades into errors, which is why we re-run inference after each batch of fixings. The closest conceptual precedent is Streamlining Variational Inference for Constraint Satisfaction Problems. That paper replaces hard fixings with softer disjunctions so that a wrong guess is less likely to destroy satisfiability, but it is built to find one witness and deliberately discards other clusters. We keep the "safety net" spirit and change what the net protects. Our check preserves the count, not just satisfiability, and it does so exactly rather than in expectation.

On the counting side, ApproxMC (A Scalable Approximate Model Counter) and its successors supply the hashing back-end that we reuse unchanged: ApproxMC2's logarithmic search (Algorithmic Improvements in Approximate Counting), BIRD and BIRD2 solver engineering (BIRD, Tinted, Detached, and Lazy CNF-XOR Solving), and sparse concentrated hashing (Sparse Hashing for Scalable Approximate Model Counting). These works all make the XOR solve faster. We instead reduce what the XORs range over, so the two efforts compound.

Arjun is the strongest prior support-reduction method. It drops variables that are logically defined by others, through gate detection and Padoa's theorem. Near-frozen variables are not defined in that sense, so Arjun keeps them, and our step runs after Arjun. One point about correctness matters here. Fixing a support variable $x$ leaves $I\setminus\{x\}$ an independent support of the residual, because every variable outside $I$ is still determined once $x$ is constant. Arjun's guarantee therefore survives decimation.

Two papers use marginals for counting and limit what we can claim. BPCount in Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting uses belief-propagation marginals to guide variable fixing inside a sampling-based estimator. It yields probabilistic lower bounds without $(\epsilon,\delta)$ guarantees, because loopy belief propagation is biased. This is exactly why our design never multiplies by an estimated marginal and instead counts the discarded side. Adaptive Hashing for Model Counting estimates marginals from SAT witnesses and uses them to choose hash variables near probability 0.5, which improves lower bounds. It keeps every variable in play and targets bounds rather than guaranteed estimates. Our step removes the strongly biased variables outright and certifies the removal.

Exact counters with learned or heuristic branching, from Combining Component Caching and Clause Learning to Learning Branching Heuristics for Propositional Model Counting, and the anytime compiler PartialKC (Fast Converging Anytime Model Counting) also split on literals. They explore both branches by search. We explore only the minority branch, which is small by construction, and send the majority branch to hashing.

Research Program

We will build the method as a preprocessing and inprocessing layer in front of ApproxMC with Arjun.

The first component is a proposer. It runs damped belief propagation, and survey propagation on random instances, over the Arjun-reduced formula. It ranks support literals by bias and passes the top candidates forward in batches.

The second component is a certifier. For each candidate $\ell$, it asks a CDCL solver for up to $T+1$ distinct projected solutions of $F_{i-1}\wedge\neg\ell$, using blocking clauses over the support. If it finds at most $T$, it records that count, fixes $\ell$, and unit-propagates. If it finds more, it rejects $\ell$ and leaves the formula unchanged. A rejection costs only time. Certifier queries contain no XORs, and when $\ell$ is truly near-frozen they are typically unsatisfiable after a few solutions, so they are the cheap kind of query.

After each batch, inference is re-run on the simplified formula. Decimation stops when the yield, measured as accepted literals per second, falls below a threshold set as a fixed fraction of the measured per-XOR solve cost. ApproxMC then counts $F_t$ over the reduced support.

The analysis has two parts. The first is the guarantee proof sketched above, extended to the case where the certifier's budget is exceeded mid-run. The second is a cost model for when decimation pays: removing $t$ variables shortens each sparse parity constraint and removes constant-valued variables that make sparse hashes split poorly, while the certifier adds up to $t\,(T+1)$ SAT calls. We expect gains to track the fraction of the support that is near-frozen. That prediction can be checked per instance.

Baselines

The naive reference point is ApproxMC4 with Arjun and no decimation, run on identical hardware with a 5,000-second timeout. On the 1,896-instance suite, Arjun let ApproxMC4 solve 387 more benchmarks and cut PAR-2 (a runtime score that charges twice the timeout for unsolved instances) from 3800 to 1707 (Arjun). This is the strongest reported pipeline with guarantees in the file, and it is the number to beat.

We will also run the sparse-hashing variant (ApproxMC5), whose reported observed error is about 0.05 against a theoretical bound of 0.8 (Sparse Hashing). No reported solved-instance count for ApproxMC5 on this suite was found on Lacuna, so we will measure it ourselves. Our layer sits in front of both back-ends with identical $\epsilon=0.8$, $\delta=0.2$, and the same seeds. Beating the baseline means solving strictly more instances and achieving lower PAR-2 with the same $\epsilon$ and $\delta$, while observed error against exact counts stays within the same range.

Among methods without guarantees, PartialKC is the comparison point for accuracy. It reports convergence on 933 of 1,103 exactly solvable instances and an average log-relative error of 0.0075 (Fast Converging Anytime Model Counting). We will run it on the same suites at equal wall-clock time. We do not claim to beat its accuracy where it converges. We do claim more solved instances in the near-threshold and dense regime, where compilation stalls.

Three ablations isolate the key ingredient. The first sets $T=0$, which is pure backbone fixing: only literals true in every solution are removed. If this matches the full method, the near-frozen idea contributes nothing. The second replaces the message-passing proposer with witness-derived marginals in the style of Adaptive Hashing, which tests whether global inference matters. The third decimates in one shot with no re-inference, which tests the feedback loop.

Why not just…?

Why not just compute backbones and drop them? Exact backbones are the $T=0$ special case, and on many instances they may capture most of the benefit. That is a real threat, and the $T=0$ ablation settles it directly. Our bet is that on structured and near-threshold formulas, many variables are frozen in nearly all solutions but not all. Statistical physics predicts this for clustered solution spaces (Aurell et al.), and strict backbones miss such variables. We will report the per-instance gap between the $T=0$ support and the $T>0$ support. If that gap is negligible, we will report the method as a backbone result.

Why not just keep improving the CNF-XOR solver? BIRD and BIRD2 delivered large gains, a 284.40x mean speedup over ApproxMC2 and 77 additional instances for ApproxMC4 (BIRD, Tinted, Detached, and Lazy CNF-XOR Solving). Yet XOR handling still dominates runtime. Our layer is orthogonal: it runs on top of BIRD2, so any gain is additive by construction. We will report the XOR-time fraction with and without decimation to show where the savings come from.

Why not just bias the hash toward balanced variables using marginals, as adaptive hashing does? Biasing keeps near-frozen variables in the support and, in the cited work, yields lower bounds rather than two-sided $(\epsilon,\delta)$ estimates (Adaptive Hashing). It also depends on finding witnesses, which becomes slow on tightly constrained formulas. Our witness-proposer ablation tests whether the message-passing proposer earns its keep. If witnesses propose literals as well as belief propagation does, we will adopt the simpler proposer, since the certifier makes the guarantee independent of which proposer is used.

Why not use knowledge compilation instead of hashing? PartialKC is strong where formulas decompose into independent components. Near-threshold random and densely coupled instances do not decompose, and that is the regime this proposal targets. The head-to-head comparison on random k-SAT across clause densities will show where each method wins.

Proposed Experiments

We will use three benchmark suites: the standard 1,896-instance counting suite (circuits, probabilistic networks, synthesis, planning, information flow), the 100 public MCC 2022 instances, and random 3-SAT and 4-SAT with 100–300 variables swept across clause density up to the satisfiability threshold. The random instances stay small enough that exact counters supply ground truth.

Metrics are solved instances and PAR-2 at 5,000 seconds, observed relative error against exact counts wherever they are available, support size after Arjun versus after decimation, average XOR length, and the share of time spent in certifier calls versus XOR solving. $T$ ranges over 0, 8, 64, and 512.

The decisive check is a per-instance scatter of the near-frozen support fraction against speedup over ApproxMC4 with Arjun. The method predicts a monotone relationship and no gain on instances with no near-frozen variables. A flat scatter, or a full method no better than the $T=0$ ablation, would falsify the core claim. Separately, any instance whose observed error leaves the guarantee band would indicate an implementation error, because correctness does not depend on marginal quality.