Exact solution, state definitions, and rigorous foundations of the zero-temperature cavity method for the Bethe lattice spin glass

The zero-temperature cavity method of Mézard and Parisi (J. Stat. Phys. 111, 1 (2003)) computes, at the one-step replica-symmetry-breaking (1RSB) level, the ground-state energy and the complexity of local ground states of the Ising spin glass on Bethe lattices (sparse random regular graphs), for example $U \simeq -1.2717$ per spin for 3-regular graphs with $J=\pm 1$ couplings, but it explicitly leaves the exact solution and the mathematical foundations open: the 1RSB ansatz is only an approximation (full replica symmetry breaking is expected to be required, as in the Sherrington–Kirkpatrick limit), the definition of local ground states and the assumed one-to-one correspondence of states under graph operations are unproven hypotheses, the computed complexity $\Sigma(\epsilon)$ has an unexplained second (convex) branch, the counts of TAP solutions, $q$-spin-flip-stable configurations, and Legendre-transform states are mutually inconsistent, and no rigorous derivation of the cavity predictions exists. This problem asks for the completion of that program: an exact (full-RSB, or provably adequate 1RSB) solution of the zero-temperature Bethe lattice spin glass, a settlement of the local-ground-state definitions and hypotheses, an interpretation of the two-branch complexity, a reconciliation of the state counts, and rigorous results for the cavity predictions.

Background

A spin glass is an Ising model with quenched random couplings of mixed sign, so that no configuration satisfies all interactions simultaneously. The archetypal mean-field example is the Sherrington–Kirkpatrick (SK) model, in which every pair of spins interacts with a Gaussian coupling of variance $1/N$; its exact solution requires Parisi's full replica symmetry breaking (full RSB), a continuous hierarchy of pure-state organizations of the Gibbs measure. A harder and structurally richer family consists of diluted (sparse) spin glasses on Bethe lattices, that is, random $(k+1)$-regular graphs: each spin has $k+1$ neighbors, the graph is locally tree-like yet globally loopy, and the model is the natural finite-connectivity interpolant between lattice spin glasses and the SK model (which is recovered formally as $k\to\infty$ after rescaling the couplings).

The cavity method exploits local tree-like structure: one adds or removes a spin (or an edge) and tracks how the ground state responds, which yields recursive distributional equations for the cavity fields $h$ (the messages the neighbors send a spin) and for the energy shifts. The order parameter at the replica-symmetric (RS) level is the distribution $P(h)$; at the one-step RSB (1RSB) level it is a distribution of distributions, $\mathcal{Q}[P(h)]$, giving the probability that a randomly chosen site carries a given local field distribution. These equations are solved numerically by population dynamics, in which distributions are represented by large populations of samples iterated under the recursion.

Mézard and Parisi (J. Stat. Phys. 111, 1 (2003)) developed the cavity method directly at zero temperature for this model. Beyond the global ground state (GGS, the energy-minimizing configuration), they counted local ground states (LGS): configurations whose energy cannot be decreased by flipping any finite number of spins, a definition meaningful only in the $N\to\infty$ limit. Their 1RSB hypotheses are: (a) exponentially many LGS exist; (b) there is a one-to-one correspondence between the low-energy LGS before and after adding a spin or link, i.e. a perturbation propagates to only an infinitesimal fraction of the lattice; (c) the low-energy LGS energies form a Poisson extreme-value process with density $\rho(E_0)=\exp(\mu(E_0-E_{\mathrm{ref}}))$; (d) cavity fields within one state are uncorrelated and site-dependent. The complexity $\Sigma(\epsilon)=(1/N)\log(\text{number of LGS with energy density }\epsilon)$ is then computed through a Legendre transform of a potential $\Phi(\mu)$, and the ground-state energy is the energy where $\Sigma$ vanishes. For $k=2$ (3-regular graphs) with $J=\pm 1$ they find the RS value $U\simeq -1.2777$ and the 1RSB value $U\simeq -1.2717$; in the $k\to\infty$ (SK) limit the corresponding values are $-0.798$ (RS), $-0.766$ (1RSB), versus the conjectured exact $-0.763$, illustrating that the 1RSB scheme is an approximation to a full-RSB solution. The paper itself states that the 1RSB explored is 'an approximation to the problem', and its computed $\Sigma(\epsilon)$ has an unusual two-branch structure: a concave branch from the ground state to the maximal-LGS energy, and a convex branch interpolating to the RS point whose physical meaning was left unexplained.

Several notions of metastable states had been studied before and alongside: TAP (Thouless–Anderson–Palmer) equations are the self-consistent mean-field equations for local magnetizations, whose solutions define candidate states; Bray and Moore counted TAP solutions in the SK model and related that count at $T=0$ to configurations stable to single spin flips (1SF states); and the Legendre-transform construction counts states implicitly through the 1RSB free energy. The source paper found its 1RSB Legendre complexity qualitatively and quantitatively different from both the 1SF complexity and the Bray–Moore shape, and asked for a reconciliation. Appendix C of the paper moreover observes that the very definition of LGS is delicate: one may define $\Sigma_a=\lim_{q\to\infty}\lim_{N\to\infty}\Sigma_q(N)$ (stability to $q$ spin flips, with $q\to\infty$ taken after $N\to\infty$; the source paper denotes this flip number by $k$, a different use of the symbol than the connectivity) or $\Sigma_b=\lim_{\epsilon\to 0}\lim_{N\to\infty}\Sigma_{\epsilon N}(N)$ (stability to flipping a vanishing fraction of spins), and whether $\Sigma_a=\Sigma_b$ is a well-posed open mathematical question; for finite $N$ a cutoff function $f(N)$ on the number of flipped spins must be chosen and 'determining the most appropriate form of $f$ is a difficult problem'.

On the rigorous side, the SK model is now fully rigorous (the Parisi formula was proved by Guerra, Talagrand, and Panchenko), but the diluted/sparse case is not: Guerra-type interpolation bounds — the rigorous comparison technique that bounds a model's free energy by continuously deforming it into a reference model, and the key tool behind the rigorous SK solution — fail for diluted models because of connectivity fluctuations. Rigorous results exist at the RS level: Coja-Oghlan and Perkins rigorously proved that the Gibbs measure of general spin systems on Bethe lattices decomposes into Bethe states — regions of the configuration space in which the cavity messages determine all local marginals and long-range correlations vanish, the rigorous counterpart of the cavity method's state decomposition — together with a variational formula for the free energy, Dembo, Montanari, and Sen rigorously solved the extremal-cuts problem for sparse random graphs (a zero-temperature cavity computation without frustration), and Biswas, Chen, and Sen established the RS solution of general diluted spin glasses; Panchenko proved that, under a small perturbation of the Hamiltonian, all finite-RSB asymptotic Gibbs measures of diluted models satisfy the Mézard–Parisi ansatz for the distribution of spins (a hierarchical, ultrametric overlap structure, i.e. one where pairwise distances between states obey a tree-like strong triangle inequality), while the general full-RSB case remains undescribed. None of these covers the low-temperature spin-glass phase of the sparse Ising spin glass. The ground-state energy prediction $U\simeq -1.2717$ for the 3-regular $\pm J$ model thus remains a non-rigorous cavity prediction, empirically supported by numerical exact ground states but unproven, and the exact solution at the full-RSB level has never been obtained.

Problem Statement

Complete the program that Mézard and Parisi's zero-temperature cavity method left open for the Ising spin glass on Bethe lattices (random $(k+1)$-regular graphs with random couplings; the target is the general finite-connectivity model, with the $k=2$, $J=\pm 1$ case where the 1RSB benchmark $U\simeq -1.2717$ exists as the quantitative reference case). All requested results serve one objective — an exact and well-founded zero-temperature description of this model — and are linked by the cavity framework itself:

(i) Determine whether the exact solution requires full replica symmetry breaking at finite connectivity, and obtain it: either a solvable full-RSB cavity scheme (order parameter, self-consistency equations, and their quantitative solution) giving the ground-state energy $U$ and the complexity $\Sigma(\epsilon)$ of local ground states, or a demonstration that 1RSB is exact for these quantities — together with the behavior in the $k\to\infty$ Sherrington–Kirkpatrick limit and, in the full-RSB case, the size of the corrections beyond one step.

(ii) Settle the definition and hypotheses of local ground states: the choice of the finite-$N$ stability cutoff $f(N)$; whether the two natural complexity definitions coincide, $\Sigma_a=\lim_{q\to\infty}\lim_{N\to\infty}\Sigma_q(N)$ (stability to $q$ spin flips, $q\to\infty$ after $N\to\infty$; the source's Appendix C writes this flip number as $k$, unrelated to the connectivity $k+1$) versus $\Sigma_b=\lim_{\epsilon\to 0}\lim_{N\to\infty}\Sigma_{\epsilon N}(N)$ (stability to flipping a vanishing fraction $\epsilon$ of the spins); the validity of the assumed one-to-one correspondence between low-energy local ground states before and after graph operations; and the Poisson extreme-value law for the low-energy state energies.

(iii) Explain the two-branch structure of the computed complexity $\Sigma(\epsilon)$: give the physical origin and significance of the convex branch that interpolates between the replica-symmetric point and the maximal-complexity point, and the regime where the one-to-one state correspondence breaks down.

(iv) Reconcile the state counts: derive the relationship at zero temperature between TAP solutions (including the quasi-solutions with a vanishing fraction of violated TAP equations), configurations stable to $q$ spin flips, and the states counted by the Legendre-transform construction, in both the Bethe-lattice model and the Sherrington–Kirkpatrick limit, resolving the discrepancy with the Bray–Moore and one-spin-flip-stable complexities.

(v) Establish which cavity predictions are rigorous: a variational principle or other rigorous derivation of the free energy or ground-state energy of the sparse Ising spin glass in the spin-glass phase, and a rigorous treatment of the hypotheses of (ii).

The one-to-one correspondence between low-energy local ground states is a single object: its validity and the regime in which it breaks down are a single determination, and that determination is the one to be made rigorous under (v). The rigorous treatment called for in (v) is a part of the program that is asked in addition to the quantitative solution sought under (i) and the decisions required under (ii).

References

1. M. Mézard and G. Parisi, 'The Cavity Method at Zero Temperature', J. Stat. Phys. 111, 1 (2003). DOI: 10.1023/a:1022221005097; arXiv:cond-mat/0207121, https://arxiv.org/abs/cond-mat/0207121 (source paper)
2. S. Boettcher, 'Numerical Results for Ground States of Spin Glasses on Bethe Lattices', Eur. Phys. J. B 31, 29 (2003). DOI: 10.1140/epjb/e2003-00005-y; arXiv:cond-mat/0208196, https://arxiv.org/abs/cond-mat/0208196
3. F. Liers, M. Palassini, A. K. Hartmann, and M. Jünger, 'Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm', Phys. Rev. B 68, 094406 (2003). DOI: 10.1103/PhysRevB.68.094406; arXiv:cond-mat/0212630, https://arxiv.org/abs/cond-mat/0212630
4. A. Pagnani, G. Parisi, and M. Ratieville, 'Metastable configurations on the Bethe lattice', Phys. Rev. E 67, 026116 (2003). DOI: 10.1103/PhysRevE.67.026116; arXiv:cond-mat/0210305, https://arxiv.org/abs/cond-mat/0210305
5. T. Rizzo, 'On the Complexity of the Bethe Lattice Spin Glass', arXiv:cond-mat/0404729 (2004), https://arxiv.org/abs/cond-mat/0404729
6. T. Rizzo, 'TAP Complexity, the Cavity Method and Supersymmetry', J. Phys. A: Math. Gen. 38, 3287 (2005). DOI: 10.1088/0305-4470/38/15/005; arXiv:cond-mat/0403261, https://arxiv.org/abs/cond-mat/0403261
7. G. Parisi and T. Rizzo, 'Zero-temperature limit of the supersymmetry-breaking complexity in dilute spin-glass models', Phys. Rev. B 72, 184431 (2005). DOI: 10.1103/PhysRevB.72.184431; arXiv:cond-mat/0411732, https://arxiv.org/abs/cond-mat/0411732
8. J. Zhou, H. Ma, and H. Zhou, 'Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses', J. Stat. Mech. (2007) L06001. DOI: 10.1088/1742-5468/2007/06/L06001; arXiv:0706.0259, https://arxiv.org/abs/0706.0259
9. S. Franz and M. Leone, 'Replica bounds for optimization problems and diluted spin systems', J. Stat. Phys. 111, 535 (2003). DOI: 10.1023/a:1022885828956; arXiv:cond-mat/0208280, https://arxiv.org/abs/cond-mat/0208280
10. G. Parisi, 'The marginally stable Bethe lattice spin glass revisited', J. Stat. Phys. 167, 515 (2017). DOI: 10.1007/s10955-017-1724-z; arXiv:1609.05327, https://arxiv.org/abs/1609.05327
11. F. Concetti, 'The full replica symmetry breaking in the Ising spin glass on random regular graph', J. Stat. Phys. 173, 1459 (2018). DOI: 10.1007/s10955-018-2142-6; arXiv:1712.00367, https://arxiv.org/abs/1712.00367
12. F. Concetti, 'Properties of the full replica symmetry breaking free energy functional of the Ising spin glass on random regular graph', arXiv:1908.03820 (2019), https://arxiv.org/abs/1908.03820
13. F. Concetti, 'Properties of the full replica symmetry breaking free energy functional of the Ising spin glass on random regular graph', arXiv:2508.17049 (2025), https://arxiv.org/abs/2508.17049
14. G. Boschi and G. Parisi, 'Free energy expansion of the spin glass with finite connectivity for $\infty$ RSB', arXiv:2001.01966 (2020), https://arxiv.org/abs/2001.01966
15. F. De Santis and G. Parisi, 'Computation of the Zero Temperature RSB parameter in Bethe Lattice Spin Glasses', arXiv:1805.01228 (2018), https://arxiv.org/abs/1805.01228
16. A. Coja-Oghlan and W. Perkins, 'Spin systems on Bethe lattices', Commun. Math. Phys. 372, 441 (2019). DOI: 10.1007/s00220-019-03544-y; arXiv:1808.03440, https://arxiv.org/abs/1808.03440
17. A. Coja-Oghlan and W. Perkins, 'Bethe states of random factor graphs', Commun. Math. Phys. 366, 173 (2019). DOI: 10.1007/s00220-019-03387-7; arXiv:1709.03827, https://arxiv.org/abs/1709.03827
18. D. Panchenko, 'Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models', J. Stat. Phys. 162, 1 (2016). DOI: 10.1007/s10955-015-1385-8; arXiv:1406.4702, https://arxiv.org/abs/1406.4702
19. R. Biswas, W.-K. Chen, and A. Sen, 'On the Replica Symmetric Solution in General Diluted Spin Glasses', Random Struct. Algorithms 66, e70013 (2025). DOI: 10.1002/rsa.70013; arXiv:2410.15599, https://arxiv.org/abs/2410.15599
20. A. Dembo, A. Montanari, and S. Sen, 'Extremal Cuts of Sparse Random Graphs', Ann. Probab. 45(2), 1190 (2017). DOI: 10.1214/15-AOP1084; arXiv:1503.03923, https://arxiv.org/abs/1503.03923
21. J.-G. Liu, L. Wang, and P. Zhang, 'Tropical Tensor Network for Ground States of Spin Glasses', Phys. Rev. Lett. 126, 090506 (2021). DOI: 10.1103/PhysRevLett.126.090506; arXiv:2008.06888, https://arxiv.org/abs/2008.06888
22. G. Perrupato, M. C. Angelini, G. Parisi, F. Ricci-Tersenghi, and T. Rizzo, 'The Ising spin glass on random graphs at zero temperature: not all spins are glassy in the glassy phase', Phys. Rev. B 106, 174202 (2022). DOI: 10.1103/PhysRevB.106.174202; arXiv:2207.06142, https://arxiv.org/abs/2207.06142
23. D. Sherrington and S. Kirkpatrick, 'Solvable model of a spin-glass', Phys. Rev. Lett. 35, 1792 (1975). DOI: 10.1103/PhysRevLett.35.1792, https://doi.org/10.1103/PhysRevLett.35.1792
24. D. J. Thouless, P. W. Anderson, and R. G. Palmer, 'Solution of "Solvable model of a spin glass"', Philos. Mag. 35, 593 (1977). DOI: 10.1080/14786437708235992, https://doi.org/10.1080/14786437708235992
25. A. J. Bray and M. A. Moore, 'Metastable states in spin glasses', J. Phys. C: Solid State Phys. 13, L469 (1980). DOI: 10.1088/0022-3719/13/19/002, https://doi.org/10.1088/0022-3719/13/19/002
26. F. Guerra, 'Broken replica symmetry bounds in the mean field spin glass model', Commun. Math. Phys. 233, 1 (2003). DOI: 10.1007/s00220-002-0773-5, https://doi.org/10.1007/s00220-002-0773-5
27. M. Talagrand, 'The Parisi formula', Ann. of Math. 163, 221 (2006). DOI: 10.4007/annals.2006.163.221, https://doi.org/10.4007/annals.2006.163.221
28. D. Panchenko, 'The Parisi formula for mixed p-spin models', Ann. Probab. 42, 946 (2014). DOI: 10.1214/12-AOP800; arXiv:1112.4409, https://arxiv.org/abs/1112.4409