Decimation as an Interpolation Path: Locating Where Variable-Fixing Fails

Many hard search and inference problems are solved by decimation. You estimate how strongly each variable leans toward a value, permanently fix the most confident ones, simplify the problem, and repeat. Physicists also have a separate tool, adaptive interpolation: a proof technique that computes the exact large-system limit of an inference problem. It works by sliding continuously from the real problem to a trivial one in which each variable is observed independently through a simple noisy channel. This note argues that, for planted problems, these are the same object viewed two ways. A planted problem is one where a hidden true assignment generated the constraints. Fixing a variable to a value drawn from its exact posterior marginal is statistically equivalent to revealing the true value of that variable through an erasure channel, a channel that either shows a value perfectly or hides it entirely. A decimation run is therefore a path through a family of partially revealed problems, and adaptive interpolation is the machinery for computing exact quantities along such paths.

This matters because the reason decimation fails is a geometric event on that path. At some point the space of solutions consistent with what has already been fixed can shatter into exponentially many disconnected clusters. One-step replica symmetry breaking (1RSB) is the physicists' description of this shattered phase: they count the clusters with a quantity called the complexity and measure how similar solutions are within and across clusters. Once the solution space shatters, belief propagation (BP), the standard message-passing estimate of marginals, averages over clusters and starts making bad calls. Our two-sentence pitch is this. The free entropy at the end of a decimation path does not depend on the route taken, but whether the path crosses a shattered region does. We propose to compute that crossing rigorously where possible, predict decimation failure from it, and design fixing schedules that steer around it.

Core Claim

Consider a planted sparse model with constraint density $\alpha$. Let $\theta \in [0,1]$ be the fraction of variables revealed exactly (hard decimation), and let $\lambda \ge 0$ be the signal-to-noise ratio of an additional noisy side observation of every variable ("soft" decimation, which nudges variables without freezing them). A decimation schedule is a curve $t \mapsto (\theta(t), \lambda(t))$ from $(0,0)$ to full revelation. Under the Nishimori symmetry of Bayes-optimal planted models, the residual problem at each point of the curve is again a Bayes-optimal inference problem. Its free entropy $\Phi(\alpha,\theta,\lambda)$, meaning the log-normalizer per variable, obeys the interpolation sum rule

$$\Phi(\alpha,\theta_1,\lambda_1) - \Phi(\alpha,0,0) = \int_0^1 \Big( \partial_\theta \Phi \,\dot\theta(t) + \partial_\lambda \Phi \,\dot\lambda(t) \Big)\, dt.$$

Here the integrand is expressed through the overlap between the truth and a posterior sample. The right-hand side is path-independent, but the 1RSB complexity at Parisi parameter $m=1$ is not. This parameter value is the one that describes clustering of the Bayes posterior; call that complexity $\Sigma_1(\alpha,\theta,\lambda)$. Our central prediction is that idealized BP-guided decimation stays accurate along a schedule exactly when $\Sigma_1$ stays non-positive along the whole curve. Empirical failure densities should therefore coincide with the first density $\alpha$ at which every admissible curve, or the specific curve the algorithm follows, enters the region $\Sigma_1 > 0$.

Three things are new relative to the file. The first is the identity between decimation trajectories and adaptive interpolation paths. The second is the use of 1RSB at $m=1$ as a path-dependent failure criterion inside an otherwise replica-symmetric rigorous calculation. The third is the resulting design question of choosing the curve. Adaptive interpolation already chooses its path to control overlap fluctuations, and here the same freedom becomes an algorithm-design knob.

Relation to Prior Work

The method comes from adaptive interpolation. Mutual Information for Low-Rank Even-Order Symmetric Tensor Factorization steers the interpolation path by an ordinary differential equation so that overlaps concentrate across phase transitions. Linear paths, as in Estimation in the Spiked Wigner Model: A Short Proof of the Replica Formula, suffice only without such transitions. The closest technical ancestor is Adaptive Path Interpolation Method for Sparse Systems: Application to a Censored Block Model. It proves the replica-symmetric conditional entropy of a sparse censored block model observed through an erasure channel, using erasure-specific Griffiths-Kelly-Sherman (GKS) inequalities. That paper treats its reliance on erasure as a limitation. For us it is an asset, because hard decimation of a planted model is an erasure side channel. The proof is static and has no decimation parameter. We add $\theta$ as a second interpolation coordinate and ask what happens along the path, not only at its endpoint.

The motivating evidence comes from decimation analyses. Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation tracks randomized BP decimation on infinite trees. It finds a spinodal cascade point near $\alpha \approx 8.05$ for 4-SAT, beyond which forced-assignment cascades blow up, but no such transition for 3-SAT. It also assumes exact tree marginals and uniform variable selection. Our criterion is a different object: clustering of the residual posterior rather than divergence of unit-propagation cascades. It may therefore explain the 3-SAT case where cascades do not. Survey propagation: an algorithm for satisfiability and Comparing Beliefs, Surveys, and Random Walks show that decimation guided by cluster-level surveys works deep into the clustered regime, while BP guidance breaks down. Neither describes how the cluster structure evolves as variables are fixed. The Decimation Scheme for Symmetric Matrix Factorization analyzes a column-by-column decimation with the non-rigorous replica method. It introduces "reversed decimation" to undo early errors, which is a discrete instance of the path-reshaping we want to make principled.

Two results constrain the design. Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem proves that balanced sequential local algorithms with constant message-passing radius fail above roughly $\frac{2^{K-1}}{K}\log^2 K$ in Not-All-Equal $K$-SAT (NAE-$K$-SAT). No schedule we design can beat that barrier if it stays local with constant radius. Our schedules must therefore be judged against it, and the theory should reproduce it rather than contradict it. Backtracking Dynamical Cavity Method shows that cavity methods can follow short dynamical trajectories accurately, matching a limiting energy to three decimals. It is a tool we may borrow for non-ideal decimation, not a competitor.

Research Program

The first stage is a theorem. We extend the sparse adaptive-interpolation proof to the censored block model with an additional fraction $\theta$ of variables revealed through an erasure channel. We prove that the conditional entropy equals the supremum of a replica-symmetric functional that depends jointly on $(\alpha,\theta)$. The proof should go through with modest changes, because erasure revelation preserves the GKS and Nishimori structure the original argument uses. We then prove the decimation identity rigorously: if the marginals used for fixing were exact, the residual instance after fixing a fraction $\theta$ has the same law as the $\theta$-revealed planted instance. Together these give an exact formula for the overlap, the free entropy, and the BP-optimal error at every point of an ideal hard decimation path.

The second stage is a non-rigorous, cavity-level phase diagram. On the $(\alpha,\theta,\lambda)$ space we solve the 1RSB cavity equations at $m=1$, computed by population dynamics. This locates the clustering surface where $\Sigma_1$ becomes positive. We do this first for the censored block model, then for planted NAE-$K$-SAT and planted $K$-SAT. In the soft directions $\lambda > 0$ we must leave the erasure channel, so rigor is not available there. The file is explicit that noisy-channel sparse interpolation lacks the needed tools. We will say so plainly and treat those parts as physics predictions checked numerically.

The third stage connects the theory to real solvers. Real decimation fixes the most biased variable rather than a random one, and it uses BP marginals that are only approximate on loopy graphs. We measure how far real runs drift from the ideal path by tracking the overlap with the planted assignment at each step. For random rather than planted instances, we use the standard planted-to-random transfer argument, which is valid only below the condensation density. Above that density, comparisons are empirical only.

The fourth stage is algorithmic. We define an adaptive schedule that, at each step, chooses between hard fixing and a soft update, and chooses the step size. The choice is made to keep the estimated $\Sigma_1$ of the residual instance non-positive. This is the algorithmic analogue of steering $R(t)$ in adaptive interpolation. In the soft limit the schedule resembles reinforcement-style message passing, and its distinctive content is the stopping and switching rule derived from the phase diagram.

Baselines

The naive reference points are running WalkSAT, a random-walk local search, on the full formula, and one-shot assignment from a single round of BP marginals without re-running inference. For WalkSAT alone, Comparing Beliefs, Surveys, and Random Walks reports over 27,000 seconds on 100 random 3-SAT formulas at $\alpha = 4.2$, versus 300 seconds with survey-propagation decimation first. We rerun WalkSAT on our own instances with the same time cap rather than relying on those wall-clock numbers.

The strongest prediction baseline is the tree density-evolution analysis of Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation. It reports a failure threshold for uniform BP decimation in 4-SAT of $\alpha_{spin} \approx 8.05$, matching simulation, and gives no threshold for 3-SAT. Beating it means two things. In 4-SAT, our $\Sigma_1$-crossing criterion must predict a failure density at least as close to measured failure as 8.05. In 3-SAT, where the tree analysis is silent, it must predict a failure density that matches simulation within finite-size error bars.

The strongest algorithmic baseline is survey-inspired decimation from Survey propagation: an algorithm for satisfiability. It is reported to solve random 3-SAT with 10 million variables at $\alpha = 4.2$ and to remain effective up to $\alpha \approx 4.252$, against a threshold of about 4.267. We run it and our schedules on identical instances, with the same WalkSAT finisher, the same per-instance time budget, and equal tuning effort for step sizes and convergence tolerances. On 3-SAT, beating it means a higher success probability at fixed time for $\alpha \in [4.2, 4.26]$, or equal success at lower cost. We consider this unlikely and do not stake the proposal on it. On planted problems with posterior marginals, where survey propagation's zero-temperature cluster counting is less natural, we expect a real advantage.

Two ablations isolate the key ingredient. In the first, we compare the adaptive schedule against hard-only and soft-only schedules with the same number of inference calls. This tests whether the path shape, rather than more computation, matters. In the second, we keep the adaptive schedule but replace the $\Sigma_1$-based switching rule with a rule based on raw marginal confidence. This tests whether the 1RSB signal adds anything beyond bias magnitude.

Why not just…?

Why not just use survey-propagation decimation, which already works almost to threshold? On random 3-SAT it is very strong, and we do not expect to beat it there. The proposal's main value is explanatory and predictive. It gives a criterion that says when and why a given decimation schedule will fail, which Survey propagation: an algorithm for satisfiability does not provide. It also applies to Bayes-optimal inference problems where the goal is accurate marginals, not just any satisfying assignment. If our schedules cannot match survey propagation even on planted inference tasks, the algorithmic stage fails and we report that.

Why not just run tree density evolution, as Montanari, Ricci-Tersenghi and Semerjian did? It already predicts the 4-SAT failure point, and our criterion might simply reproduce it. That would be a real threat, so the decisive test is 3-SAT. The tree cascade analysis shows no spinodal there, yet BP decimation still fails in practice. If $\Sigma_1$-crossing predicts the 3-SAT failure and cascades do not, the clustering mechanism is distinct. If both are silent or both agree everywhere, our contribution shrinks to the rigorous erasure-channel theorem.

Why not just fix fewer variables per step, or add backtracking and repair as in GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming? Smaller steps and repair reduce the damage from errors, but they do not change which partially fixed problems the path visits. Ideal decimation with infinitesimal steps still crosses the clustered region if the path does. Our hard-versus-soft ablation at matched inference budget tests this directly. If a tuned constant step size with repair performs as well as the adaptive schedule, we will conclude that the phase diagram is useful for diagnosis but not for design.

Proposed Experiments

On the censored block model, we generate instances with $N$ from $10^4$ to $10^6$. We run ideal decimation, using BP marginals with fixing to sampled values, and measure the overlap with the planted labels as a function of $\theta$. We compare against the proven formula. Agreement up to the clustering surface and divergence beyond it would confirm both the identity and the criterion.

On 4-SAT and 3-SAT, as well as planted NAE-4-SAT and NAE-5-SAT, we scan $\alpha$ under uniform and most-biased BP decimation and record success probability, the fraction of variables fixed at failure, and the drift from the ideal path. We compare the measured failure densities with the predicted $\Sigma_1$-crossing densities and with the 8.05 tree prediction. For NAE-$K$-SAT we also check that predicted and measured failure for constant-radius variants respect the Gamarnik–Sudan scaling.

Finally, on random 3-SAT at $\alpha \in [4.15, 4.26]$ with $N$ up to $10^6$, and on planted instances, we compare the adaptive schedule, its two ablations, survey-inspired decimation, and WalkSAT alone under equal time budgets. The decisive check of the core claim is the 3-SAT failure point. The decisive check of the algorithmic claim is whether path shape matters at a fixed inference budget.