Survey Propagation and the Shattered Solution Space
When one cavity marginal stops being enough — clustering, warnings, surveys over pure states, and the thresholds they separate
Part 2 ended on an admission. When the solution space of a constraint-satisfaction problem fragments into many well-separated clusters, a single cavity marginal averages over clusters that no individual assignment can straddle — and the message itself becomes the wrong object, not merely a badly-estimated one.
This chapter takes that seriously. The route is: specialize belief propagation to satisfiability, take the zero-temperature limit already derived in Part 2 to obtain warning propagation, watch it fail for a structural rather than numerical reason, and then rebuild the message one level up as a survey — a probability distribution over the warnings a clause would send, one per cluster. That construction is survey propagation
It is also the chapter where the epistemic labels matter most. Much of what follows is a prediction of the one-step replica-symmetry-breaking (1RSB) cavity method, not a theorem. Some of it is a theorem. The two are interleaved in the literature, and separating them is most of the work.
Satisfiability as a factor graph
A $k$-SAT formula over Boolean variables $x_1,\dots,x_n$ is a conjunction of clauses, each a disjunction of $k$ literals. Write it as a factor graph exactly as in Part 1: variables are circles, clauses are squares, and an edge $(i,a)$ exists when variable $i$ appears in clause $a$.
Each clause $a$ contributes a hard indicator factor,
\[f_a(\mathbf x_{\partial a})=\mathbf 1\!\left[\text{clause } a \text{ is satisfied by } \mathbf x_{\partial a}\right],\]so the uniform measure over satisfying assignments is the factor-graph law of Part 1 with $g_i\equiv1$:
\[P(\mathbf x)=\frac{1}{Z}\prod_{a}f_a(\mathbf x_{\partial a}), \qquad Z=\#\{\text{satisfying assignments}\}.\]Two pieces of notation make the SAT case readable. Each edge carries a sign: literal $x_i$ appears in clause $a$ either positively or negatively. For a variable $i$ and a clause $a\ni i$, split the other clauses containing $i$ into
\[\partial_a^{s}i=\{b\ne a:\ b \text{ agrees with } a \text{ on } i\}, \qquad \partial_a^{u}i=\{b\ne a:\ b \text{ disagrees with } a \text{ on } i\},\]where “agrees” means $b$ is satisfied by the same value of $x_i$ that satisfies $a$. The $s$ and $u$ stand for satisfying and unsatisfying relative to $a$’s demand on $i$.
Warnings are zero-temperature messages
Part 2 derived min-sum by writing $m=\exp(-\beta M)$ and taking $\beta\to\infty$. For hard constraints the energy of a clause is $0$ when satisfied and $+\infty$ when violated, and the surviving information in a message collapses to a single bit.
Define the warning $u_{a\to i}\in{0,1}$:
\[u_{a\to i}=1 \quad\Longleftrightarrow\quad \text{clause } a \text{ forces } x_i \text{ to the value that satisfies } a.\]A clause forces its remaining variable exactly when every other variable in it has already been pushed the wrong way by its own other clauses. That gives the warning-propagation recursion:
\[\boxed{ u_{a\to i}=\prod_{j\in\partial a\setminus i} h_{j\to a}, \qquad h_{j\to a}=\mathbf 1\!\left[\textstyle\sum_{b\in\partial_a^{u}j}u_{b\to j}\;>\;\sum_{b\in\partial_a^{s}j}u_{b\to j}\right]. }\]Read it in words: the local field $h_{j\to a}$ is $1$ when $j$’s other clauses push it away from the value $a$ needs, strictly more than they push it toward that value. If every other variable in $a$ is pushed away, then $a$ has one option left and must issue a warning.
This is not a new algorithm either. It is min-sum from Part 2, restricted to a two-state message and written in the sign conventions of satisfiability
From min-sum to a single bit, carefully
It is worth doing the collapse explicitly, because the step from “a message is a distribution” to “a message is one bit” is where SAT stops looking like Part 2.
Take a variable $j$ and write its cavity distribution toward clause $a$ in log-odds form, $h_{j\to a}=\log\frac{\chi^{j\to a}(\text{sat }a)}{\chi^{j\to a}(\text{unsat }a)}$. At inverse temperature $\beta$ with hard clauses, each incoming warning contributes an amount that diverges linearly in $\beta$, and everything else contributes $O(1)$. Writing $h=\beta H+O(1)$ and keeping only the leading term,
\[H_{j\to a}=\sum_{b\in\partial_a^{s}j}u_{b\to j}\;-\;\sum_{b\in\partial_a^{u}j}u_{b\to j},\]a difference of integer counts. The sign of $H$ is all that survives: a strictly negative $H_{j\to a}$ means $j$ is being pushed away from what $a$ needs, which is the indicator in the boxed recursion above. Ties ($H=0$) mean $j$ is genuinely free, and the convention that $\mathbf 1[\cdot]$ uses a strict inequality is what encodes that.
This is the same collapse Part 2 performed for the hard-core model, where $\frac1\beta\log(1+e^{\beta U})\to\max(0,U)$ turned a soft competition into a hard one. Hard constraints simply push it further: the surviving object is not a real-valued score but a bit, because the only question a clause can ask is “am I down to my last option?”
When one marginal is not enough
Now put the formula on a random graph and increase the clause density $\alpha=m/n$, the ratio of clauses to variables.
At low $\alpha$ the satisfying assignments form, in the 1RSB picture, a single connected blob: you can walk from any solution to any other by short sequences of single-variable flips that stay satisfying. A single cavity marginal describes this well, because there is one thing to describe.
Above a clustering (or dynamical) threshold $\alpha_d$, the picture changes qualitatively. The solution set shatters into exponentially many clusters, each internally connected but separated from the others by extensive Hamming distance — you cannot walk between clusters without passing through violated assignments
where $\Sigma$ is the complexity. The support of $\Sigma\ge0$ is the range of cluster types that exist; where $\Sigma$ first hits zero at the dominant $f$, only sub-exponentially many clusters carry the measure — the condensation threshold $\alpha_c$.
Here is why this breaks the message, not merely its accuracy. A BP cavity marginal $\chi^{i\to a}(x_i)$ is a single distribution. In a shattered landscape, the honest answer to “what is $x_i$?” is cluster-dependent: frozen to $1$ in some clusters, frozen to $0$ in others, free in a third group. Averaging those into one number produces something near $1/2$ that describes no cluster at all — and, worse, the fixed-point equations that produced it assumed a single pure state to begin with.
What belief propagation actually returns there
The gadget is small enough to run sum–product on directly, so we need not speculate about what BP would say.
Running ordinary BP on the uniform-over-solutions measure of $\varphi’$ converges immediately to
\[b_i(x_i{=}1)=\tfrac12 \qquad\text{for all four variables},\]which is exactly the true marginal — each variable is $1$ in two of the four solutions. BP is not wrong here. It is answering the question it was asked, correctly, and the answer is useless.
That is the distinction this chapter turns on. In Part 1, loopy BP was inaccurate: it computed exact marginals of the wrong model. Here BP is accurate and still unhelpful, because the marginal itself does not carry the information needed to build a solution. Rounding each variable to its most likely value is a coin flip per variable, and only $4$ of the $16$ roundings are satisfying. The failure is in the choice of summary statistic, not in its estimation.
A survey is a distribution over messages
The fix is to stop asking for a marginal and start asking for a distribution over cluster-conditional answers.
Fix a cluster. Inside it, warning propagation is well defined and returns a warning $u_{a\to i}\in{0,1}$ on every edge. Different clusters return different warnings. So define the survey
\[Q_{a\to i}(u)\;=\;\Pr\!\left[\text{a randomly chosen cluster sends warning } u \text{ on edge } a\to i\right],\]a probability distribution over ${0,1}$ rather than a bit. This is the object one level up: BP’s messages are distributions over variable values; surveys are distributions over messages. That hierarchy is exactly what the 1RSB cavity method formalizes
For $k$-SAT the surveys can be reduced to a single number per edge, $\eta_{a\to i}=Q_{a\to i}(1)$, the probability that clause $a$ warns $i$. The update, in the notation established above, is
\[\boxed{ \eta_{a\to i} =\prod_{j\in\partial a\setminus i} \frac{\Pi^{u}_{j\to a}} {\Pi^{u}_{j\to a}+\Pi^{s}_{j\to a}+\Pi^{0}_{j\to a}}, }\]with the three cavity weights
\[\begin{aligned} \Pi^{u}_{j\to a}&=\Big[1-\prod_{b\in\partial_a^{u}j}(1-\eta_{b\to j})\Big]\prod_{b\in\partial_a^{s}j}(1-\eta_{b\to j}),\\ \Pi^{s}_{j\to a}&=\Big[1-\prod_{b\in\partial_a^{s}j}(1-\eta_{b\to j})\Big]\prod_{b\in\partial_a^{u}j}(1-\eta_{b\to j}),\\ \Pi^{0}_{j\to a}&=\prod_{b\in\partial_a^{u}j}(1-\eta_{b\to j})\prod_{b\in\partial_a^{s}j}(1-\eta_{b\to j}). \end{aligned}\]The three cases are: $j$ is pushed away from what $a$ wants ($u$), pushed toward it ($s$), or pushed neither way ($0$). Clause $a$ warns $i$ only when every other variable is in the first case.
The joker, and why it is not a third truth value
The third state deserves its own paragraph, because it is the piece most often misread. Alongside “must be true” and “must be false”, survey propagation carries a symbol usually written $\star$ — the joker, meaning this variable is unconstrained within this cluster. It is not a third logical value that variables can take; assignments remain Boolean throughout. It is a statement about a cluster: within this pure state, $x_i$ is free to flip.
Formally the joker is what makes $\Pi^0$ a separate case rather than folded into $\Pi^s$. Maneva, Mossel and Wainwright made this precise by constructing an explicit Markov random field over the enlarged alphabet ${0,1,\star}$ and proving that survey propagation is ordinary belief propagation on that enlarged model
Counting clusters: the complexity
Surveys buy more than a per-variable answer. Because each cluster contributes its own Bethe free entropy, the 1RSB construction yields an estimate of how many clusters there are at each free-energy density — the complexity $\Sigma(f)$ introduced above.
Operationally, one introduces a Parisi parameter $y$ conjugate to the cluster free energy and computes a generalized partition function over clusters,
\[\mathcal Z(y)=\sum_{\text{clusters }\gamma} e^{-y\,n f_\gamma}\;\simeq\;\int \mathrm df\; e^{\,n[\Sigma(f)-yf]},\]whose saddle point ties $y$ to a particular cluster free energy through $\Sigma’(f)=y$. The complexity is then recovered by a Legendre transform of $\frac1n\log\mathcal Z(y)$.
Two special values matter. At $y=0$ every cluster is weighted equally, so the calculation counts clusters rather than weighting them by size — this is survey propagation as normally run, and it is why SP answers “in what fraction of clusters is $x_i$ frozen to $1$?” rather than “in what fraction of solutions”. At the $y$ that maximizes $\Sigma-yf$ one recovers the thermodynamically dominant clusters instead. The distinction is easy to lose and changes what the output means.
Survey propagation as usually implemented is the $y\to0$ member of a one-parameter family, where $y$ is a reweighting (Parisi) parameter conjugate to cluster free energy. At the other end of the family the equations degenerate to ordinary BP. So SP is not a different algorithm bolted on beside BP — it is BP evaluated on a richer message space, with a parameter that interpolates back to the original
Reading the update as three exclusive cases
The survey update looks forbidding until one notices it is just a normalized three-way case split, written once per neighbour.
Fix a clause $a$ and a variable $j\in\partial a$, and ask what the rest of the formula does to $j$ in a randomly chosen cluster. Exactly one of three things happens.
| Case | Meaning | Weight |
|---|---|---|
| $u$ | $j$'s other clauses push it away from what $a$ needs | $\Pi^{u}_{j\to a}$ |
| $s$ | $j$'s other clauses push it toward what $a$ needs | $\Pi^{s}_{j\to a}$ |
| $0$ | $j$ is unconstrained — the joker | $\Pi^{0}_{j\to a}$ |
Each weight is built the same way: “at least one clause on the relevant side warns, and none on the other side does.” The bracket $\bigl[1-\prod(1-\eta)\bigr]$ is precisely “at least one warning arrives,” and the bare product $\prod(1-\eta)$ is “none arrives.” A configuration in which both sides warn is a contradiction and is excluded — which is why the three weights need not sum to one before normalizing.
Clause $a$ then warns $i$ only when every other variable is in case $u$, giving the boxed product. Set every $\eta$ to $0$ or $1$ and the whole thing collapses back to warning propagation; that limit is a useful implementation check.
Decimation, and what it does not prove
Surveys are not assignments. The standard way to convert them is SP-guided decimation, the same pattern as the BP-guided decimation of Part 2 with a different message underneath.
- Run SP to a fixed point on the current formula.
- From the converged surveys compute, for each free variable, its bias — the imbalance between the probability of being frozen to $1$ and to $0$ across clusters.
- Fix the most biased variable to its preferred value.
- Simplify the formula (remove satisfied clauses, shorten the rest) and return to step 1.
- When the surveys become trivial — all $\eta\approx0$, meaning no clause constrains anything — stop and finish with a local search such as WalkSAT.
Empirically this works remarkably far. On large random 3-SAT it finds solutions at clause densities close to the satisfiability threshold $\alpha_s\approx4.267$, a regime where every previously known method stalls
The failure mode is worth naming precisely, because it is the same shape as Part 2’s decimation caveat. Each fixing step is irreversible and is made on the basis of a fixed point computed before that step. If an early, confidently-biased variable is set wrongly, nothing later revisits it, and the residual formula can become unsatisfiable while every individual step looked well-justified. Backtracking variants exist and improve the reachable density, at the cost of no longer being a single forward pass.
Where the variational picture went
Part 1 gave BP a second reading: fixed points are stationary points of the Bethe free energy, and that variational view explained why the same equations keep appearing on graphs where the tree derivation is invalid. It is fair to ask what happened to that reading here.
It survives, one level up. The 1RSB construction has its own variational object — a free energy over distributions of messages rather than over messages — and survey propagation’s fixed points are its stationary points, exactly as BP’s fixed points were stationary points of Bethe
This is the sense in which SP is not an ad-hoc patch. It is the same variational machinery applied to a richer space of order parameters, and the hierarchy continues: two-step replica-symmetry breaking would carry distributions over distributions over messages, and so on. For random $k$-SAT, one step is believed to suffice near the threshold; for other models it demonstrably does not.
The Maneva–Mossel–Wainwright result gives the cleanest statement of what this buys, and it is worth repeating precisely because it is the rigorous anchor of the chapter: SP is belief propagation, on a specific enlarged Markov random field over ${0,1,\star}$
Four thresholds that are not the same threshold
Part 2 insisted on threshold discipline for the hard-core model. Random $k$-SAT needs it more, because at least four distinct thresholds appear in the same discussions and are routinely conflated.
| Threshold | What it marks | Status |
|---|---|---|
| $\alpha_{\mathrm{alg}}$ | where the best known polynomial-time algorithm still succeeds w.h.p. | Rigorous achievability results exist |
| $\alpha_d$ | solution space shatters into exponentially many clusters | 1RSB prediction |
| $\alpha_c$ | sub-exponentially many clusters carry the measure | 1RSB prediction |
| $\alpha_s$ | satisfiable below, unsatisfiable above | Theorem for all large $k$ |
For large $k$ these are ordered
\[\alpha_{\mathrm{alg}}\;\ll\;\alpha_d\;<\;\alpha_c\;<\;\alpha_s,\]and the first inequality is the uncomfortable one. Known polynomial-time algorithms stall at roughly $2^k\ln k/k$ clauses per variable
The satisfiability threshold is the one genuine theorem in this list, and its history is instructive: existence of a sharp threshold came first without its location
The gap that clustering does not explain
The ordering $\alpha_{\mathrm{alg}}\ll\alpha_d$ deserves more than a line, because it undercuts the tidiest version of the story.
The appealing narrative runs: solutions shatter at $\alpha_d$, shattering traps local algorithms, therefore algorithms fail above $\alpha_d$. The numbers refuse to cooperate. For large $k$, known polynomial-time algorithms stall around $2^k\ln k/k$, while clustering sets in at a density that is larger by a factor growing with $k$
So clustering cannot be the cause of algorithmic hardness, because hardness arrives first. What clustering plausibly explains is why certain specific local strategies fail, and why SP outperforms BP where it does. The broader question of why any polynomial-time algorithm should stop where it does remains open, and is one of the more interesting open problems the cavity method has surfaced without solving.
This is worth stating plainly because the opposite claim is common and comfortable. A reader who takes away only “clustering makes SAT hard” has acquired a memorable sentence that the numbers do not support.
When to reach for a survey
| Situation | Reach for | Why |
|---|---|---|
| Tree or near-tree factor graph | BP / warning propagation | Exact; a survey adds nothing to describe one cluster |
| Loopy graph, BP converges, marginals look decisive | BP with decimation | A single pure state is plausibly being described |
| BP converges but every marginal sits near $1/2$ | Suspect shattering | The gadget above is the minimal instance of this symptom |
| BP oscillates on a random CSP near threshold | Survey propagation | Non-convergence and clustering are frequently the same fact |
| Structured/industrial instance, not a random ensemble | A real SAT solver | SP's evidence base is random ensembles; CDCL dominates elsewhere |
The last row matters more than its length suggests. Everything in this chapter is about random formulas near a threshold. Modern conflict-driven clause-learning solvers routinely dispatch structured industrial instances with millions of variables that no message-passing method would touch, and SP is not competitive there. The regime where SP is remarkable — large random instances close to $\alpha_s$ — is exactly the regime where CDCL struggles. They are complementary tools aimed at different distributions, and the honest comparison names the distribution first.
What has actually been proved
| Claim | Status |
|---|---|
| Warning propagation is the $\beta\to\infty$ limit of BP for hard constraints | Exact identity |
| WP is exact on a tree formula; warnings identify frozen variables | Theorem (Part 1's argument) |
| SP is BP on an enlarged $\{0,1,\star\}$ MRF | Theorem |
| Clusters exist above $\alpha_d$; complexity $\Sigma(f)$ counts them | 1RSB prediction |
| SP marginals describe per-cluster freezing | 1RSB prediction |
| SP-guided decimation solves random 3-SAT near $\alpha_s$ | Empirical |
| $\alpha_s(k)$ for large $k$ | Theorem |
A note on what SP does not do
Three clarifications, because each is a common over-reading.
SP does not sample uniformly from solutions. At $y=0$ it weights clusters equally, so a cluster containing one solution counts as much as a cluster containing $2^{0.01n}$ of them. If the goal is uniform sampling, that bias is a defect rather than a feature, and it must be corrected for explicitly.
SP does not certify unsatisfiability. If it converges to trivial surveys, the correct reading is “this method found no constraint structure,” not “no solution exists.” Refutation is a genuinely different problem, and message passing has nothing to say about it.
SP is not a general-purpose replacement for BP. Below $\alpha_d$ the surveys concentrate on a single warning per edge and SP reduces to warning propagation with extra bookkeeping. Running it everywhere costs constant-factor time for no gain, and the extra machinery obscures what is happening.
The chapter’s structural lesson generalizes past SAT. When a method fails, there are two very different diagnoses available: the estimate is poor, or the estimated object is wrong. Parts 1 and 2 dealt with the first — loopy BP computing exact marginals of the wrong model, the computation tree. This chapter dealt with the second. No amount of damping, scheduling or reinitialization repairs a single cavity marginal in a shattered landscape, because the quantity being computed does not summarize the thing being asked about. The repair was to enlarge the message.
That is a move worth keeping. Whenever a message-passing scheme fails stubbornly, it is worth asking whether the message has enough room to carry the answer — before concluding that message passing was the wrong idea.
Part 4 turns to a family of methods that make the opposite trade: they keep the local aggregation pattern and discard the probabilistic content entirely, learning the update from data instead of deriving it from a distribution.