Extremal Bethe-state decomposition of the Gibbs measure of general random constraint satisfaction problems

For random constraint satisfaction problems (CSPs) such as random k-SAT, graph coloring, and XORSAT on sparse random graphs, statistical-physics heuristics (the replica and cavity methods) predict that the uniform measure over solutions decomposes into a convex combination of extremal Bethe states, each well described by the Bethe–Peierls (belief-propagation) approximation. Dembo and Montanari identified this decomposition as the key unproven assumption behind the cavity method, survey propagation, and the notion of complexity (the exponential number of solution clusters) in random CSPs. The rigorous state of the art: Coja-Oghlan and Perkins proved that random factor graphs with strictly positive (soft) weights asymptotically almost surely admit a coarse Bethe-state decomposition whose canonical messages are belief-propagation fixed points, a major partial resolution. A precise open core survives, documented as open in the source: extremality of the components — the cavity method additionally predicts, heuristically and model by model, exponentially many extremal states with a positive complexity function in the coexistence regime — and the extension to hard constraints (zero-temperature models such as proper coloring, XORSAT, and k-SAT at threshold density).

Background

A random constraint satisfaction problem (CSP) asks for assignments of spins (Boolean variables or colors) to variables that satisfy randomly drawn constraints, e.g. k-SAT clauses, graph-coloring properness conditions, or parity (XORSAT) equations. A convenient general formalism is the random factor graph: a bipartite graph whose variable nodes carry spins and whose constraint (factor) nodes apply weight functions — nonnegative functions that score each assignment of the adjacent variables; the Gibbs measure is proportional to the product of the weights, so a weight function taking the value zero is a hard constraint that forbids assignments. On sparse random graphs — graphs with bounded average degree, so that neighborhoods are locally tree-like (cycles appear only at distance growing with the graph size) — the uniform measure over solutions, called the Gibbs measure in statistical physics, is the central probabilistic object. Belief propagation (BP) is a message-passing algorithm that computes marginals on trees exactly; the Bethe–Peierls approximation is the corresponding ansatz that the Gibbs measure of a locally tree-like graph is locally indistinguishable from a tree model built from BP fixed-point messages. Dembo and Montanari formalized this: a measure is $(\epsilon,r)$-Bethe approximated by a set of BP (Bethe-equation) messages if its marginal on every tree subset of variables of diameter at most $2r$ is within $\epsilon$ in total variation of the measure induced on that subset by the messages used as boundary conditions; such a measure is an $(\epsilon,r)$-Bethe state for the graph–weight pair (their Definition 3.10). Here and throughout, 'asymptotically almost surely' (a.a.s.) means with probability tending to one as the graph size tends to infinity. On infinite lattices, Gibbs measures decompose into extremal (pure) phases, and physicists conjecture the analogous statement for sparse random graphs: the Gibbs measure of a large class of models — Dembo and Montanari phrase this informally as 'a large class of models, including for instance the examples in Section 1', which include random k-SAT, graph coloring, XORSAT, the independent set model, and Ising and spin-glass models — decomposes into a unique convex combination of extremal Bethe states. Extremal is defined in their Definitions 3.12–3.13 as decay of correlations with a valid rate function: $\|\rho_{A,B} - \rho_A\rho_B\|_{TV} \le \delta(d(A,B))$ for all variable sets $A, B$, where $\delta(\cdot)$ is monotonically non-increasing and decays to zero; this plays the role that pure Gibbs states play on infinite lattices, and their Theorem 3.14 shows that an extremal canonical measure on an $R$-tree-like graph with rate $\delta$ is $(\epsilon,r)$-Bethe approximated by its standard message set with $\epsilon = \exp(c^r)\delta(R-r)$ for all $r < R-1$. This conjecture is the structural foundation of the cavity method and of one-step replica symmetry breaking (1RSB, the assumption that the solution set splits into exponentially many clusters, each a Bethe state; in the coexistence regime of Dembo and Montanari's Section 4.1, regime II, the clusters are separated by bottlenecks of exponentially small ratio $\mu(\partial_\epsilon\Omega)/\mu(\Omega) \le e^{-Cn}$, a typical family $\mathrm{Typ}_n$ of clusters carries mass at least $1 - e^{-C'n}$, and each typical cluster has mass $e^{-n\Sigma\pm o(n)}$, so that $|\mathrm{Typ}_n| = e^{n\Sigma+o(n)}$, defining the complexity (configurational entropy) $\Sigma$ jointly with the cluster decomposition), of survey propagation (a BP-type algorithm operating on cluster statistics), and of the condensation transition (their regime III: the density above which the number of clusters is sub-exponential and almost all of the mass is carried by finitely many clusters, the number covering any fixed mass fraction converging to a finite random variable). Krzakala, Montanari, Ricci-Tersenghi, Semerjian, and Zdeborová (PNAS 2007) gave the physics picture of these Gibbs states and solution clusters. Rigorous partial results exist: Achlioptas and Coja-Oghlan (FOCS 2008) proved the geometric clustering (well-separatedness) of solutions for random coloring and k-SAT without establishing any Bethe-state property; Dembo and Montanari proved the conditional first step that an extremal Gibbs measure on a random tree-like graph is a Bethe state (their Theorem 3.14) but left the decomposition conjecture open, calling it the key unproven assumption of statistical-physics approaches; Coja-Oghlan and Perkins then proved that random factor graphs with strictly positive weight functions asymptotically almost surely admit a decomposition into a number of Bethe states bounded by an arbitrarily slowly growing function of the graph size covering $1-\epsilon$ of the Gibbs mass, with essential uniqueness in the cut metric (a metric on probability distributions over spin assignments under which two measures are close when their joint local statistics agree), both for Poisson-type random factor graphs (ensembles whose local neighborhoods converge to Galton–Watson trees with Poisson or binomial offspring, the standard Erdős–Rényi-type models) and (with free-energy and variational applications) for random regular graphs; Panchenko proved that the 1RSB and finite-RSB (finitely many levels of replica symmetry breaking, the hierarchical decomposition scheme of spin-glass theory) asymptotic Gibbs measures of diluted models satisfy the Mézard–Parisi ansatz (the Parisi-type variational description adapted by Mézard and Parisi to diluted, sparse models), with the full-RSB regime (an unbounded number of replica-symmetry-breaking levels) still undescribed. Model-specific verifications of cavity predictions include the condensation transitions in random graph coloring (Coja-Oghlan–Krzakala–Perkins–Zdeborová) and in the regular k-SAT model (Bapst–Coja-Oghlan), the satisfiability threshold for large k equal to the 1RSB prediction (Ding–Sly–Sun), correctness of BP on random k-SAT wherever replica symmetry holds (Coja-Oghlan–Müller–Ravelomanana), the replica-symmetric regime of general diluted spin glasses (Biswas–Chen–Sen), and the Gibbs-uniqueness threshold of random k-SAT (Chatterjee–Coja-Oghlan–Greenhill–Pfenninger–Rolvien–Zakharov–Zampetakis). None of these delivers the general extremal decomposition, and the Coja-Oghlan–Perkins theorems exclude hard constraints by requiring strictly positive weight functions and bound the number of Bethe states by an arbitrarily slowly growing function, whereas static (full) replica symmetry breaking predicts unboundedly many extremal states in the condensed phase.

Problem Statement

Prove or disprove the Bethe-state decomposition conjecture for general random constraint satisfaction problems on sparse (locally tree-like) random graphs, in the formulation of Dembo and Montanari: for random factor-graph models with bounded nonnegative weight functions (their Eq. (1.23): the Gibbs measure is proportional to the product of the factor weight functions, so weight functions may take the value zero as hard constraints) on locally tree-like random graph ensembles (their Section 1.2.4: configuration models with prescribed degree distributions, random regular graphs, Erdős–Rényi-type graphs) — the class informally described in the source as 'a large class of models, including for instance the examples in Section 1', which includes the hard-constraint CSPs random k-SAT, graph coloring, XORSAT, and the independent set model — the canonical (Gibbs) measure asymptotically almost surely (with probability tending to one as the graph size grows) decomposes, up to small error terms, as a unique convex combination of extremal Bethe states, each of whose components is accurately treated within its Bethe–Peierls (belief-propagation) approximation. Here 'extremal' means decay of correlations with a valid rate function (their Definitions 3.12–3.13), and an $(\epsilon,r)$-Bethe state is a measure whose marginals on all tree subsets of diameter at most $2r$ are within $\epsilon$ in total variation of the measure induced by a set of BP messages, in particular the standard message set (their Definition 3.10). The admissible class is deliberately informal in the source and is not defined by permissiveness: permissiveness (their Definition 1.1, stated for pairwise specifications: a 'permitted state' exists whose entire rows and columns in the weight matrices are bounded below by a positive fraction $\kappa\psi_{\max}$ of the maximum weight) is a hypothesis of their rigorous Theorem 3.14 and of subsequent work, not of the conjecture; among hard-constraint models it covers the independent set model (their Section 3.3, with permitted state $x_i^{\rm p}=0$) but is violated by proper coloring and XORSAT, and the source defines no permissiveness condition for general $k$-ary factor weights. The source states the conjecture informally, without fixing the order of quantifiers over $\epsilon$, $r$, and the graph size, or the precise sense in which the 'small error terms' vanish; formulating these asymptotics rigorously, in a nondegenerate regime where the approximation errors genuinely tend to zero rather than under a vacuous tolerance, is part of the task. Because the source fixes no such formalization, a complete answer must state explicitly the formalization it addresses — a definite quantifier order over $\epsilon$, $r$, and the graph size, and a definite nonvacuous sense in which the error terms vanish — and any self-contained rigorous formalization that is faithful to Definitions 3.10 and 3.12–3.13 and covers the model class above counts as resolving the task. The source's own instantiation is their Theorem 3.14, whereby an extremal canonical measure on an $R$-tree-like graph with rate $\delta$, under a permissive specification, is $(\epsilon,r)$-Bethe approximated by its standard message set with $\epsilon = \exp(c^r)\delta(R-r)$ for all $r < R-1$; it covers the case where the canonical measure is itself already extremal and therefore does not fix the quantifier structure of the general decomposition. The single overarching objective, a rigorous form of the structural foundation of the cavity method, comprises jointly: (i) existence of the decomposition for model classes with hard constraints, not only strictly positive weights; and (ii) extremality — that the components are the extremal (finest) Bethe states. The cavity method further predicts — heuristically, and in the source concretely for random graph coloring (their Section 4.1, regime II, and their Section 4.3) — that in the coexistence regime the configuration space splits into clusters separated by bottlenecks of exponentially small ratio $\mu(\partial_\epsilon\Omega)/\mu(\Omega) \le e^{-Cn}$, with a typical family $\mathrm{Typ}_n$ of clusters carrying mass at least $1 - e^{-C'n}$ and each typical cluster of Gibbs mass $e^{-n\Sigma\pm o(n)}$, hence $|\mathrm{Typ}_n| = e^{n\Sigma+o(n)}$ for a complexity (configurational entropy) $\Sigma > 0$; this prediction motivates and contextualizes the conjecture but is not part of the source's open assumption, the source supplies no single closed-form $\Sigma$ for the whole class, and in parameter regions where the cavity picture predicts a single lump (their regime I, e.g. below the coexistence threshold, and trivially for $q=2$ coloring) the conjecture is correspondingly consistent with a unique extremal component and no positive complexity. These facets are scientifically linked as successive levels of the same decomposition statement; a complete answer establishes or refutes the finest extremal decomposition for the general class, while partial progress (e.g. extremality for soft models only, or existence for a specific hard-constraint CSP) is meaningful precisely as a fragment of this objective. Disproof may take the form of a single model within this locally tree-like class whose Gibbs measure provably admits no such extremal Bethe-state decomposition.

References

1. Amir Dembo and Andrea Montanari, "Gibbs Measures and Phase Transitions on Sparse Random Graphs", Brazilian Journal of Probability and Statistics 24(2), 137–211 (2010), DOI 10.1214/09-BJPS027, arXiv:0910.5460, https://arxiv.org/abs/0910.5460
2. Amin Coja-Oghlan and Will Perkins, "Bethe States of Random Factor Graphs", Communications in Mathematical Physics 366, 173–201 (2019), DOI 10.1007/s00220-019-03387-7, arXiv:1709.03827, https://arxiv.org/abs/1709.03827
3. Amin Coja-Oghlan and Will Perkins, "Spin Systems on Bethe Lattices", Communications in Mathematical Physics 372, 441–523 (2019), DOI 10.1007/s00220-019-03544-y, arXiv:1808.03440, https://arxiv.org/abs/1808.03440
4. Dmitry Panchenko, "Structure of 1-RSB Asymptotic Gibbs Measures in the Diluted p-Spin Models", Journal of Statistical Physics 155, 1–22 (2014), DOI 10.1007/s10955-014-0955-5, arXiv:1308.1944, https://arxiv.org/abs/1308.1944
5. Dmitry Panchenko, "Structure of Finite-RSB Asymptotic Gibbs Measures in the Diluted Spin Glass Models", Journal of Statistical Physics 162, 1–42 (2016), DOI 10.1007/s10955-015-1385-8, arXiv:1406.4702, https://arxiv.org/abs/1406.4702
6. Dimitris Achlioptas and Amin Coja-Oghlan, "Algorithmic Barriers from Phase Transitions", Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), 793–802, DOI 10.1109/FOCS.2008.11, arXiv:0803.2122, https://arxiv.org/abs/0803.2122
7. Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová, "Information-Theoretic Thresholds from the Cavity Method", Advances in Mathematics 333, 694–795 (2018), DOI 10.1016/j.aim.2018.05.029, arXiv:1611.00814, https://arxiv.org/abs/1611.00814
8. Victor Bapst and Amin Coja-Oghlan, "The Condensation Phase Transition in the Regular k-SAT Model", Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), Leibniz International Proceedings in Informatics (LIPIcs) 60, Article 22 (2016), DOI 10.4230/LIPIcs.APPROX-RANDOM.2016.22, arXiv:1507.03512, https://arxiv.org/abs/1507.03512
9. Jian Ding, Allan Sly, and Nike Sun, "Proof of the Satisfiability Conjecture for Large k", Annals of Mathematics 196(1), 1–388 (2022), DOI 10.4007/annals.2022.196.1.1, arXiv:1411.0650, https://arxiv.org/abs/1411.0650
10. Amin Coja-Oghlan, Noela Müller, and Jean B. Ravelomanana, "Belief Propagation on the Random k-SAT Model", Annals of Applied Probability 32(5), 3718–3796 (2022), DOI 10.1214/21-aap1772, https://doi.org/10.1214/21-aap1772
11. Arnab Chatterjee, Amin Coja-Oghlan, Catherine Greenhill, Vincent Pfenninger, Maurice Rolvien, Pavel Zakharov, and Kostas Zampetakis, "The Random k-SAT Gibbs Uniqueness Threshold Revisited", arXiv:2506.01359 (2025), https://arxiv.org/abs/2506.01359
12. Ratul Biswas, Wei-Kuo Chen, and Arnab Sen, "On the Replica Symmetric Solution in General Diluted Spin Glasses", Random Structures & Algorithms 66(4) (2025), DOI 10.1002/rsa.70013, arXiv:2410.15599, https://arxiv.org/abs/2410.15599
13. Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová, "Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems", Proceedings of the National Academy of Sciences 104(25), 10318–10323 (2007), DOI 10.1073/pnas.0703685104, https://doi.org/10.1073/pnas.0703685104