The Cluster Geometry of Scale-Free SAT, and What It Means for Decimation

Real-world SAT formulas from hardware and software verification differ from the random formulas theorists study. In real formulas a few "hub" variables appear in a huge share of clauses and most variables appear rarely; the degree counts follow a power law. Two separate literatures touch this fact without meeting. Statistical physicists have a precise map of how the solution space of uniform random SAT breaks into isolated clusters as constraints are added. That map explains when message-passing solvers succeed or fail. SAT researchers know that heavy-tailed formulas become dramatically easier for standard backtracking solvers, but they have no account of why in terms of solution-space geometry. This note proposes to compute the cluster phase diagram of power-law random SAT directly. We then use it to predict, and test, which variable-fixing strategies work across the range from uniform to strongly heavy-tailed formulas.

The central question is sharp. When the power-law exponent drops, does the shattered, clustered phase disappear, or does it survive with the hubs acting as an easily identified frozen skeleton? The two answers predict different behavior for a measurable experiment. Under the first, a cheap hub-first fixing rule should be as good as anything. Under the second, a survey of cluster states is needed to decide which value each hub takes. In both cases the theory should predict where belief-propagation decimation breaks as a function of the exponent. Nobody has measured that.

Background and the gap

Three terms need plain definitions. Decimation is a solving loop: estimate how biased each unassigned variable is toward true or false, permanently fix the most confident ones, simplify the formula, and repeat. One-step replica symmetry breaking (1RSB) is a physics approximation. It describes the solutions as an exponential number of separate clusters, each internally well connected. It tracks the complexity $\Sigma$, the logarithm of the number of clusters per variable, as clause density $\alpha = m/n$ grows. Two transitions matter in this description. At the clustering point $\alpha_d$ the solution space shatters into clusters. At the condensation point $\alpha_c$ a handful of giant clusters come to hold almost all solutions. Survey propagation (SP) is the message-passing algorithm derived from 1RSB. It estimates, for each variable, the fraction of clusters in which that variable is frozen to true, frozen to false, or free.

The physics line supplies both the method and the benchmarks we must match. Survey propagation: an algorithm for satisfiability derives SP from the zero-temperature cavity method and builds survey-inspired decimation on top of it. It solves uniform 3-SAT with 10 million variables at $\alpha=4.2$ and works up to about $\alpha \approx 4.252$. Gibbs states and the set of solutions of random constraint satisfaction problems and Clusters of solutions and replica symmetry breaking in random k-satisfiability locate $\alpha_d \approx 9.38$, $\alpha_c \approx 9.547$ and $\alpha_s \approx 9.931$ for 4-SAT, where $\alpha_s$ is the density beyond which no solutions exist. The first of these two papers also shows that belief-propagation decimation succeeds past clustering but fails at condensation. Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem dissects how SP decimation fails on a related problem. All four works assume Poisson or regular degrees. That is the restriction we remove.

The power-law line motivates the work and supplies the instance model. Towards Industrial-Like Random SAT Instances measures power-law variable occurrences in the SAT Race 2008 industrial suite and gives generators that reproduce them. Satisfiability and Algorithms for Non-uniform Random k-SAT defines the configuration model we will use: sample degrees from a Zeta law, clone, match clones into clauses, and sign literals at random. It also bounds the satisfiability threshold. Phase Transitions for Scale-Free SAT Formulas and Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT give combinatorial threshold bounds, closed form only for 2-SAT. On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition finds two things: backtracking solvers overtake local search once the exponent $\beta \le 3.5$, and the hardness peak collapses near $\beta \approx 2.5$. These papers obtain thresholds by counting arguments and runtimes by running solvers. None asks about clusters, condensation or freezing, and none runs SP or BP decimation. Throughout this note, $\beta$ denotes the variable-degree exponent and $\alpha$ the clause density. The file's sources sometimes swap these letters.

Core Claim

We claim the cavity method can be carried out on configuration-model $k$-SAT with power-law degrees. The resulting $\beta$-dependent phase diagram, $\alpha_d(\beta)$, $\alpha_c(\beta)$, the freezing point, and the 1RSB estimate of $\alpha_s(\beta)$, then predicts three things: where belief-propagation decimation fails, where survey decimation fails, and whether hubs are frozen. The technical obstacle is specific. In the cavity recursion, a variable reached along a random edge has excess degree distributed as

$$q_d = \frac{(d+1)\,p_{d+1}}{\langle d \rangle},$$

where $p_d \propto d^{-\beta}$ is the degree distribution and $\langle d \rangle$ its mean. When $\beta \le 3$ this distribution has infinite variance. A naive population-dynamics solver, which represents the message distribution by a sampled pool, will almost never sample a hub, so it underestimates exactly the variables we care about. We will solve the 1RSB equations with population dynamics stratified by degree class. High-degree classes are oversampled and reweighted, and the hub cutoff is set to the finite-$N$ maximum degree, which grows like $N^{1/(\beta-1)}$. This makes the predictions finite-size statements that can be checked directly against instances.

Our working hypothesis, which we hold loosely, is the second scenario. Shattering persists for moderate $\beta$. Hubs freeze early, because many incoming warnings from their clauses pile up on them, and fixing them leaves a residual formula whose degrees are close to uniform but at lower effective density. If so, the collapse of hardness reported in On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition would be explained by decimation trajectories that move the formula out of the hard region of the uniform phase diagram, not by an absence of clusters.

Research Program

The work has three parts. The first is theory and numerics: stratified population dynamics for BP and for 1RSB at Parisi parameter $m=1$ (which locates clustering and condensation) and $m=0$ (which gives the SP fixed point and the frozen backbone). We will run this for $k=3$ and $k=4$ on a grid of $\beta$ from 2.5 to 6 plus the uniform limit. We will use 4-SAT as the main testbed because there $\alpha_d < \alpha_c$ are distinct, whereas in 3-SAT they coincide near 3.86. The outputs are complexity curves $\Sigma(\alpha;\beta)$ and, for each degree class, the predicted fraction of frozen variables. Below $\beta=3$, short cycles through hubs may break the tree-like assumption the cavity method relies on. We therefore treat that region as one where predictions must be validated against instances before they are trusted, and we report the residual mismatch rather than hide it.

The second part is instance-level measurement. We will build SP and BP for configuration-model formulas with $N$ from $10^4$ to $10^6$ and record four things: convergence rates, iteration counts, and oscillation; the joint distribution of degree and survey state, meaning how often a hub is frozen versus free; and how the degree distribution and effective density of the residual formula evolve along a decimation trajectory. That trajectory can be plotted onto the uniform phase diagram.

The third part is algorithms. We will compare decimation orderings: survey bias, BP marginal bias, raw degree, and a combined rule. The combined rule fixes hubs first but takes each hub's value from its survey. Every run uses the same simplification step and the same local-search finisher on the residual formula. The goal is not a new solver that beats CDCL everywhere. It is a theory-backed account of which ingredient matters in which $\beta$ range, with the algorithms serving as tests of that account.

Baselines

The naive reference points are WalkSAT run directly on the full formula, and decimation in random variable order with the same unit propagation and WalkSAT finisher. Random-order decimation separates the value of any guidance from the value of 1RSB guidance specifically. Both baselines get the same wall-clock budget as the proposed methods.

The strongest existing competitor on heavy-tailed instances is a modern conflict-driven solver: MiniSat and CryptoMiniSAT with standard activity-based branching. Towards Industrial-Like Random SAT Instances reports MiniSat solving 500,000-variable Double-powerlaw instances in seconds at $\beta=0.75$. On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition reports that such solvers beat local search for $\beta \le 3.5$. On uniform formulas the strongest competitor is survey-inspired decimation itself, reported to solve 3-SAT with $10^7$ variables at $\alpha=4.2$ and to work up to $\alpha \approx 4.252$ (Survey propagation: an algorithm for satisfiability). Belief-propagation decimation is the cheaper physics-based competitor; it is reported to succeed up to $\alpha_c \approx 9.547$ on 4-SAT with $N=10^5$ (Gibbs states and the set of solutions of random constraint satisfaction problems). For any of these methods on power-law formulas, there is no reported result on Lacuna for SP- or BP-guided decimation, so we will produce those numbers ourselves.

All methods run on identical instance sets with the same per-instance time limit, a single core, and equal tuning effort. For decimation methods, that tuning covers the fraction of variables fixed per round and the damping. For the conflict-driven solver, we use default settings plus one tuned configuration. Success is measured as the fraction of instances solved within the limit and the median time to solution, both as functions of $(\beta, \alpha)$. The proposal beats the CDCL baseline only if a 1RSB-guided method solves a larger fraction at matched time in some band of $\beta$ near the crossover, for example 3 to 4.5, at densities near the empirical threshold and at $N \ge 10^5$. If no such band exists, we report that 1RSB machinery is unnecessary for scale-free SAT, and we still deliver the phase diagram.

The key ablation is hub-first decimation with values chosen by unit-propagation lookahead rather than by surveys. If it matches survey-guided hub-first decimation everywhere, then surveys add nothing once degree is known.

Why not just…?

Why not just run a conflict-driven solver, since it already handles heavy-tailed formulas? At small $\beta$ it may well be unbeatable, and we expect it to be. Its advantage reportedly fades as $\beta$ rises past about 3.5 (On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition). In the uniform limit, survey decimation reaches sizes that backtracking cannot (Survey propagation: an algorithm for satisfiability). The open question is the intermediate band, and the $\beta$-sweep settles it directly. The phase diagram is useful whatever the solver comparison shows, because it explains the crossover.

Why not just use pure-literal elimination, unit propagation, or the 2-SAT reduction of ISSAT? Pure-literal elimination prunes heavy-tailed formulas well (Analysis of Pure Literal Elimination Rule for Non-uniform Random (MAX) k-SAT Problem with an Arbitrary Degree Distribution). It stops once both signs of every remaining variable appear, which is exactly the situation in the hard core near threshold. ISSAT (Satisfiability and Algorithms for Non-uniform Random k-SAT) is a one-pass reduction aimed at the underconstrained regime. We will apply pure-literal elimination as preprocessing to every method, and include ISSAT as a baseline, so any remaining gain is attributable to guidance on the residual core.

Why not just fix hubs first, since degree is free to compute? This is the real threat. If hubs are almost always frozen, degree order and survey order coincide and SP is overhead. The degree-by-survey-state measurement answers this directly. If, at moderate $\beta$, hubs often turn out free or balanced in sign, a degree-only rule will fix them prematurely and should fail at lower density than survey-guided ordering. The hub-first ablation turns this into a head-to-head comparison.

Why not just use belief-propagation decimation, which is cheaper? In uniform 3-SAT it fails around $\alpha \approx 3.9$, because clustering and condensation coincide there (Clusters of solutions and replica symmetry breaking in random k-satisfiability). Heavy tails may shift condensation away from clustering or remove it altogether. The theory predicts $\alpha_c(\beta)$, and BP decimation is the instrument that tests the prediction. If $\alpha_c(\beta)$ rises close to $\alpha_s(\beta)$, BP is enough, and we will say so.

Why not just train a graph neural network to guide decimation? The GNN decimation of Understanding GNNs for Boolean Satisfiability through Approximation Algorithms raises the SR(40) solve rate from 80% to 94%. It was tested only up to 250 variables and offers no account of geometry. We will include it at $N \le 10^4$, as far as it scales, but it cannot answer the central question.

Proposed Experiments

Instances come from the configuration model of Satisfiability and Algorithms for Non-uniform Random k-SAT, for $k \in \{3,4\}$, $\beta$ in 2.5 to 6 plus uniform, and densities swept across each empirical threshold. Generation should be fast enough to make large $N$ feasible. As a realism check, we compare degree statistics with those reported for the SAT Race 2008 suite (Towards Industrial-Like Random SAT Instances). We also run SP-convergence diagnostics, but not solving claims, on available bounded-model-checking instances.

The first decisive check is calibration. The 1RSB estimate of $\alpha_s(\beta)$ must fall inside the published combinatorial bounds and match empirical satisfiability curves from CDCL at $N \sim 10^4$. A miss below $\beta = 3$ would mark where the cavity method breaks down. The second check is that the empirical failure density of BP decimation, extrapolated in $N$, tracks the predicted $\alpha_c(\beta)$, and survey decimation's tracks the predicted freezing point. This is the analogue, across $\beta$, of the 4-SAT result in Gibbs states and the set of solutions of random constraint satisfaction problems. The third check is that predicted per-degree-class frozen fractions match measured survey states on instances, which decides between the two scenarios. The fourth check is the ordering comparison against the CDCL and hub-first baselines across the crossover band. The proposal's practical claim stands only if survey-valued hub-first decimation solves more instances at matched time at $N \ge 10^5$ somewhere in $\beta \in [3, 4.5]$. Its scientific claim stands if checks one to three hold, regardless of which solver wins.