Rigorous foundations of the survey-propagation equations in random constraint satisfiability problems (Parisi's conjectures)

Survey propagation (SP), the message-passing scheme derived from the one-step replica-symmetry-breaking cavity method, is the statistical-physics approach to random constraint satisfaction problems such as random K-satisfiability and random graph coloring: it predicts the satisfiability threshold, the complexity density $\Sigma(\alpha)$ (the exponential growth rate of the number of solution clusters), and underlies the best algorithms near threshold. Parisi (2008) consolidated the conjectures on which this approach rests and left them unproved: (a) below a critical density $\alpha_U$ the SP equations on the random infinite tree have a unique, iteration-stable solution; (b) for a typical large finite random instance the SP equations have a solution close to the infinite-tree (Aldous-unwrapped) solution; (c) in the satisfiable (colorable) phase the belief-propagation (TAP) equations provably possess bona fide solutions, constructed from extremal directional whitenings, whereas in the unsatisfiable (uncolorable) phase they provably admit at least 'quasisolutions' (satisfied except on a vanishing fraction of sites) but may lack bona fide global solutions; (d) clusters of solutions correspond one-to-one to extremal directional whitenings, so that $\Sigma(\alpha)$ equals the exponential growth rate of the number of whitenings. The problem is to prove or refute these conjectures rigorously for the source's models. Later rigorous work has confirmed 1RSB predictions of thresholds and free energies model by model (random regular NAE-SAT, large-$k$ SAT, graph-coloring condensation) and built rigorous descendants of the tree picture, but the conjectures themselves remain open in their original generality.

Background

Random constraint satisfaction problems (CSPs) are a canonical meeting ground of statistical physics, combinatorics, and algorithm design. In random $K$-satisfiability ($K$-SAT), $N$ Boolean variables are constrained by $M=\alpha N$ randomly chosen clauses, each a disjunction of $K$ randomly negated literals; $\alpha$ is called the clause density. In random graph $q$-coloring, the vertices of a random graph with $M=\alpha N$ edges must receive one of $q$ colors so that adjacent vertices differ. For both ensembles a sharp satisfiability (colorability) threshold $\alpha_c$ is expected: below it a random instance is satisfiable with probability tending to one as $N\to\infty$, above it with probability tending to zero. For 3-SAT the physics prediction is $\alpha_c\approx 4.27$, and the exact value is still unproven.

Instances are sparse and their factor graphs (the bipartite graphs joining each clause to the variables it contains) are locally tree-like: the neighborhood of a variable is, with high probability, a tree up to depth of order $\log N$. On trees, marginal probabilities are computed exactly by belief propagation (BP), the sum-product or, at zero temperature, min-sum message-passing algorithm, a finite-connectivity generalization of the TAP (Thouless–Anderson–Palmer) equations of spin-glass theory; on the loopy finite graph the same equations are only heuristic. Writing self-consistent equations for one variable with the rest of the system removed is the 'cavity' construction of spin-glass theory, and the resulting framework is called the cavity method.

The physics picture (Mézard–Parisi–Zecchina 2002 for $K$-SAT; Mulet–Pagnani–Weigt–Zecchina 2002 for coloring) is that as $\alpha$ grows the set of solutions shatters into exponentially many well-separated clusters — 'pure states' in spin-glass language — and each cluster supports its own BP fixed point. This organization is called one-step replica symmetry breaking (1RSB). Survey propagation is the resulting second-level message passing: a message (a 'survey') is the distribution, across clusters, of the BP message at a variable, coarse-grained for $K$-SAT into a three-component vector $\mathbf{s}=(s_T,s_I,s_F)$ giving the fraction of clusters in which the variable is forced true, forced false, or unconstrained. Solving the SP equations yields the complexity $\Sigma(\alpha)$, defined by $\#\text{clusters}=\exp(N\Sigma(\alpha))$, and the predicted threshold $\alpha^*$ where $\Sigma$ vanishes, together with the SP decimation algorithm that finds solutions near threshold. Krzakala, Montanari, Ricci-Tersenghi, Semerjian and Zdeborová (2007) organized the full threshold landscape: a clustering threshold $\alpha_d$, a condensation threshold at which the solution measure collapses onto $O(1)$ clusters, and the satisfiability threshold.

The SP equations themselves are solved on the infinite random tree — the Poisson Galton–Watson factor tree (the random tree in which each variable meets an independent Poisson-distributed number of clauses, of mean $K\alpha$ for $K$-SAT) that is the local weak limit (the $N\to\infty$ local limit of a random graph around a vertex, the construction Aldous introduced for the random assignment problem) — by population dynamics: one iterates a stochastic map on an ensemble of $L$ messages $I$ times and reads off a fixed distribution $\mathcal{P}(\mathbf{s})$. Parisi (2008) consolidated exactly what remains uncontrolled in this chain. Numerically (instances up to $N=10^6$, populations up to $L=10^6$), the coupled iteration of two differently initialized runs converges for 3-SAT clause densities below $\alpha_U\approx 4.36$ at rate $\exp(-\lambda(\alpha)t)$ with $\lambda>0$, and turns chaotic above; below $\alpha_L\approx 3.9$ the SP fixed point is trivial; the complexity changes sign at $\alpha^*\approx 4.27$. For coloring, Parisi introduced the whitening procedure: starting from a legal coloring, a node is whitened if its color can be changed while keeping the coloring legal, iterated to an extremal (unwhitenable) whitening; the directional version $w(i|k)$ records the color node $i$ could take if the neighbor $k$ were absent, and its extremal form satisfies local equations equivalent to zero-temperature BP — in the colorable phase each legal coloring yields a unique such extremal directional whitening, so bona fide local-equilibrium solutions exist there. Finally, in the uncolorable phase of random graphs the local-equilibrium (BP/TAP) equations may fail to hold exactly, and the provable objects are quasisolutions: assignments of messages satisfying the equations at all but a vanishing fraction of sites.

Rigorous work has since confirmed parts of the surrounding picture, model by model: Achlioptas and Ricci-Tersenghi (2006) proved clustering with frozen variables in a large-$K$/large-$q$ regime; Bapst, Coja-Oghlan, Hetterich, Raßmann and Vilenchuk (2015) proved the condensation transition in random graph coloring; Ding, Sly and Sun proved exact satisfiability thresholds equal to the 1RSB prediction for random regular NAE-SAT (the 'not-all-equal' SAT variant; STOC 2014) and for random $K$-SAT with $K$ large (Annals of Mathematics, 2022); Sly, Sun and Zhang (2016) matched the 1RSB prediction for the number of solutions of regular NAE-SAT through a rigorous analysis of a 'survey propagation model'; Nam, Sly and Sohn (2020–2024) and Sly and Sohn (2023) established condensation onto $O(1)$ clusters and the local weak limit of solutions in the condensation regime for regular NAE-SAT; Gu (2026) developed a computer-assisted rigorous population-dynamics algorithm. None of these constructs the SP fixed points or proves the correspondence conjectured in the source for its models.

Problem Statement

Establish a rigorous foundation for survey propagation in random constraint satisfaction problems by proving or refuting, for the random $K$-satisfiability and random graph $q$-coloring ensembles (the models treated in the source, with 3-SAT and coloring as the running examples), the following conjectures of Parisi (2008), which consolidates arXiv:cs/0212009 and arXiv:cs/0212047. The four components share one scientific objective — replacing the heuristic cavity/SP analysis by theorems about the actual solution-space geometry of random instances — and each may be settled separately, by proof or by counterexample: a rigorous proof or refutation of any one component is by itself a complete resolution of this task, while the four together constitute the full program.

(a) Infinite-tree uniqueness and stability. Prove (or refute) that the SP equations on the random infinite tree (the Poisson Galton–Watson factor tree, with mean $K\alpha$ clauses per variable — $3\alpha$ for 3-SAT) have a unique solution $\mathcal{P}(\mathbf{s})$, invariant under the tree recursion, that is stable under iteration for densities $\alpha$ below a sharp critical value $\alpha_U$; determine $\alpha_U$ rigorously (the source's numerics give $\alpha_U\approx 4.36$ for 3-SAT), and relate $\alpha_U$ to the sign of the Lyapunov exponent $\lambda(\alpha)$ of the coupled two-run population-dynamics iteration (convergence for $\lambda>0$, chaos for $\lambda<0$). This includes a rigorous replacement of the heuristic population-dynamics fixed-point and stability analysis, with control of the population-size limit $L\to\infty$ and the iteration limit $I\to\infty$.

(b) Finite-instance correspondence. Prove (or refute) that for a typical large finite random instance with $\alpha<\alpha_U$, the SP equations on that instance have a solution close to the solution computed on the associated infinite rooted tree (the Aldous unwrapping of the instance around a variable); in particular that the unique stable tree solution is an approximate solution of the instance's SP equations.

(c) Quasisolutions. In the unsatisfiable (uncolorable) phase — where the source proves that the local-equilibrium (BP/TAP) equations on a random graph admit quasisolutions, i.e. assignments of messages satisfying the equations at all but a vanishing fraction of sites — prove (or refute) that bona fide global solutions also exist, or show that they may be missing; in the satisfiable (colorable) phase the source proves bona fide solutions exist, via the unique extremal directional whitening associated with each legal configuration, whose local equations are equivalent to the zero-temperature BP/TAP equations. Resolve also the source's side question of whether extremal directional whitenings exist that cannot be obtained by whitening any legal configuration.

(d) Cluster–whitening correspondence and complexity. Prove (or refute) the conjectured one-to-one correspondence between clusters (pure states) of solutions and extremal directional whitenings, and the identity $\#(\text{extremal directional whitenings})=\exp(N\Sigma(\alpha))$ in the clustered satisfiable regime, where $\Sigma(\alpha)$ is the complexity density computed from the SP solution and vanishes at the satisfiability threshold $\alpha^*$. Here a cluster (pure state) means a connected component of the set of solutions under single-variable moves — two solutions lie in the same cluster when they are joined by a path of solutions each differing from the previous one in one variable (one Boolean flip, or one vertex recoloring in the coloring case) — that is, one of the source's local-equilibrium states; the complexity $\Sigma(\alpha)$ counts exactly these clusters, and the correspondence and counting identity are asserted for this notion. The source reports numerically the ordering $\alpha_U>\alpha^*>\alpha_L$ ($\approx 4.36 > 4.27 > 3.9$ for 3-SAT) and heuristically identifies $\alpha^*=\alpha_c$; these threshold relations are numerical/heuristic context accompanying the conjectures, not separately mandated requirements.

The conjectures are posed for the random $K$-satisfiability and random graph $q$-coloring ensembles and for the source's notion of cluster; the solution measure in place of the SP equations, regular or large-$K$/large-$q$ variants, and other notions of cluster — such as local weak limits or overlap blocks in lieu of the cluster–whitening correspondence — concern neighboring problems.

References

1. Giorgio Parisi, 'On the survey-propagation equations in random constraint satisfiability problems', Journal of Mathematical Physics 49, 125216 (2008). DOI: 10.1063/1.3030862. https://doi.org/10.1063/1.3030862
2. Giorgio Parisi, 'On the survey-propagation equations for the random K-satisfiability problem', arXiv:cs/0212009 (2002). https://arxiv.org/abs/cs/0212009
3. Giorgio Parisi, 'On local equilibrium equations for clustering states', arXiv:cs/0212047 (2002). https://arxiv.org/abs/cs/0212047
4. M. Mézard, G. Parisi, R. Zecchina, 'Analytic and Algorithmic Solution of Random Satisfiability Problems', Science 297, 812–815 (2002). DOI: 10.1126/science.1073287. https://doi.org/10.1126/science.1073287
5. R. Mulet, A. Pagnani, M. Weigt, R. Zecchina, 'Coloring Random Graphs', Physical Review Letters 89, 268701 (2002). DOI: 10.1103/PhysRevLett.89.268701. https://doi.org/10.1103/PhysRevLett.89.268701
6. Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, Lenka Zdeborová, 'Gibbs states and the set of solutions of random constraint satisfaction problems', Proceedings of the National Academy of Sciences 104, 10318–10323 (2007). DOI: 10.1073/pnas.0703685104. https://doi.org/10.1073/pnas.0703685104
7. David J. Aldous, 'The ζ(2) limit in the random assignment problem', Random Structures & Algorithms 18, 381–418 (2001). DOI: 10.1002/rsa.1015. https://doi.org/10.1002/rsa.1015
8. Dimitris Achlioptas, Federico Ricci-Tersenghi, 'On the Solution-Space Geometry of Random Constraint Satisfaction Problems', Proc. 38th ACM Symposium on Theory of Computing (STOC) (2006). DOI: 10.1145/1132516.1132537; arXiv:cs/0611052. https://arxiv.org/abs/cs/0611052
9. Amin Coja-Oghlan, Konstantinos Panagiotou, 'Catching the k-NAESAT threshold', Proc. 44th ACM Symposium on Theory of Computing (STOC) (2012), pp. 899–908. DOI: 10.1145/2213977.2214058; arXiv:1111.1274. https://arxiv.org/abs/1111.1274
10. Amin Coja-Oghlan, Konstantinos Panagiotou, 'The asymptotic k-SAT threshold', Advances in Mathematics 288, 985–1068 (2016). DOI: 10.1016/j.aim.2015.11.007. https://doi.org/10.1016/j.aim.2015.11.007
11. Jian Ding, Allan Sly, Nike Sun, 'Satisfiability threshold for random regular NAE-SAT', Proc. 46th ACM Symposium on Theory of Computing (STOC) (2014), pp. 814–822. DOI: 10.1145/2591796.2591862; journal version: Communications in Mathematical Physics 341, 435–489 (2015), DOI: 10.1007/s00220-015-2492-8; arXiv:1310.4784. https://arxiv.org/abs/1310.4784
12. Jian Ding, Allan Sly, Nike Sun, 'Proof of the satisfiability conjecture for large k', Annals of Mathematics 196 (1) (2022). DOI: 10.4007/annals.2022.196.1.1; arXiv:1411.0650. https://arxiv.org/abs/1411.0650
13. Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, Dan Vilenchuk, 'The Condensation Phase Transition in Random Graph Coloring', Communications in Mathematical Physics 341, 543–606 (2015). DOI: 10.1007/s00220-015-2464-z. https://doi.org/10.1007/s00220-015-2464-z
14. Allan Sly, Nike Sun, Yumeng Zhang, 'The number of solutions for random regular NAE-SAT', Probability Theory and Related Fields 182, 1–109 (2021). DOI: 10.1007/s00440-021-01029-5; arXiv:1604.08546. https://arxiv.org/abs/1604.08546
15. Danny Nam, Allan Sly, Youngtak Sohn, 'One-step replica symmetry breaking of random regular NAE-SAT', Proc. 62nd IEEE Symposium on Foundations of Computer Science (FOCS) (2021). DOI: 10.1109/FOCS52979.2021.00039; arXiv:2011.14270. https://arxiv.org/abs/2011.14270
16. Danny Nam, Allan Sly, Youngtak Sohn, 'One-Step Replica Symmetry Breaking of Random Regular NAE-SAT II', Communications in Mathematical Physics 405, 3 (2024). DOI: 10.1007/s00220-023-04868-6; arXiv:2112.00152. https://arxiv.org/abs/2112.00152
17. Allan Sly, Youngtak Sohn, 'Local geometry of NAE-SAT solutions in the condensation regime', Probability Theory and Related Fields 191, 979–1033 (2024). DOI: 10.1007/s00440-024-01337-6; arXiv:2305.17334. https://arxiv.org/abs/2305.17334
18. Florent Krzakala, Marc Mézard, Lenka Zdeborová, 'Reweighted Belief Propagation and Quiet Planting for Random K-SAT', Journal on Satisfiability, Boolean Modeling and Computation 8, 149–171 (2014). DOI: 10.3233/SAT190096; arXiv:1203.5521. https://arxiv.org/abs/1203.5521
19. Raffaele Marino, Giorgio Parisi, Federico Ricci-Tersenghi, 'The backtracking survey propagation algorithm for solving random K-SAT problems', Nature Communications 7, 12996 (2016). DOI: 10.1038/ncomms12996; arXiv:1508.05117. https://arxiv.org/abs/1508.05117
20. Yuzhou Gu, 'Exact reconstruction thresholds on hypertrees over a symmetric binary alphabet', arXiv:2606.21699 (2026). https://arxiv.org/abs/2606.21699
21. Wei Xu, Fuzhou Gong, Guangyan Zhou, 'Clustering phase of a general constraint satisfaction problem model d-k-CSP', Physica A: Statistical Mechanics and its Applications 537, 122708 (2020). DOI: 10.1016/j.physa.2019.122708. https://doi.org/10.1016/j.physa.2019.122708
22. Wei Xu, Zhe Zhang, 'The solution space structure of planted constraint satisfaction problems with growing domains', Journal of Statistical Mechanics: Theory and Experiment 2022, 033401 (2022). DOI: 10.1088/1742-5468/ac4e86; arXiv:2108.01761. https://arxiv.org/abs/2108.01761
23. Wei Xu, Zhe Zhang, Guangyan Zhou, 'Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length', Physica A: Statistical Mechanics and its Applications 609, 128367 (2023). DOI: 10.1016/j.physa.2022.128367. https://doi.org/10.1016/j.physa.2022.128367