Survey Propagation

Survey propagation is a message-passing algorithm derived from the one-step replica symmetry breaking (1RSB) version of the cavity method, designed to solve random constraint satisfaction problems in regimes where local search and belief propagation both fail. Unlike standard belief propagation, which passes messages about variable marginals, survey propagation passes messages about the "surveys" of clusters — distributions over partial assignments that represent distinct clusters of solutions in the solution space.

The algorithm was introduced by Mézard and Zecchina in 2002 and achieved the remarkable feat of solving random 3-SAT instances with up to millions of variables near the satisfiability threshold — a regime previously considered intractable. Its success provided striking empirical confirmation of the physical picture in which the solution space shatters into exponentially many clusters, each requiring a distinct search strategy.

Survey propagation remains one of the most dramatic demonstrations that statistical physics predictions about computational hardness are not merely heuristic metaphors but precise, actionable insights.