On the nature of the low-temperature phase in discontinuous mean-field spin glasses

Andrea Montanari, Federico Ricci‐TersenghiThe European Physical Journal B 2003 · DOI · arXiv

On the nature of the low-temperature phase in discontinuous mean-field spin glasses

For decades, the study of complex systems—ranging from structural glasses to hard combinatorial optimization problems—has relied on "discontinuous mean-field spin glasses" as primary theoretical models. The $p$-spin model, in particular, has served as a benchmark for understanding how systems relax and where algorithms fail. The prevailing consensus was that these systems are adequately described by a one-step replica symmetry breaking (1RSB) Ansatz. While a transition to a more complex Full Replica Symmetry Breaking (FRSB) phase (the Gardner transition) was known, it was widely believed to occur only at temperatures or energies far below those relevant to the "threshold" states where dynamics typically stall. This paper fundamentally challenges that intuition, demonstrating that the states governing out-of-equilibrium dynamics and algorithmic limits are almost always in an FRSB phase.

The Failure of the 1RSB Approximation

The authors employ the replica method to conduct a rigorous stability analysis of the 1RSB solution. They identify a critical free-energy density, $f_G$, above which the 1RSB solution becomes unstable against further levels of symmetry breaking. This instability is not a minor correction; it signals a qualitative change in the landscape of metastable states.

Transition from 1RSB to FRSB in the complexity function and overlap distribution.

As shown in Figure 1, the 1RSB Ansatz assumes a simple step-function for the overlap distribution $q(x)$. However, beyond the instability point $f_G$, the distribution becomes continuous, indicating that the "threshold" states—the highest-energy metastable states—are not simple basins but rather fractal-like families of states with internal FRSB structure. The authors highlight that the spherical $p$-spin model, often used as a textbook example, is a degenerate case where this instability is suppressed, leading to the misleading "common wisdom."

Quantitative Refinement and Algorithmic Hardness

To move beyond the 1RSB failure, the authors perform a two-step (2RSB) calculation at zero temperature. This provides a more accurate approximation of the true FRSB behavior. Their results show a significant quantitative shift: the energy level $e_d$ at which dynamics are predicted to "get stuck" by 1RSB is an overestimate. The true bottleneck for local search algorithms is the instability point $e_G$, which lies at a lower energy.

Energy-temperature phase diagram showing the instability of the 1RSB solution ($e_d$) and the emergence of the Gardner point ($e_G$).

Figure 5 illustrates this energy-temperature landscape. The gap between the 1RSB threshold $e_d(T)$ and the instability point $e_G(T)$ is crucial for understanding algorithmic performance. Empirical validation through simulated annealing on Ising models with finite connectivity (e.g., $c=5, 6$) confirms this. The systems reach energies well below the 1RSB threshold, settling at levels perfectly compatible with the calculated $e_G$. This identifies $e_G$ as the fundamental energy barrier that local search algorithms cannot easily penetrate in polynomial time, providing a theoretical basis for the "hardness" of these problems.

Implications for Aging and Future Work

The discovery of FRSB structure in threshold states has profound implications for the physics of aging. Instead of the two time scales predicted by 1RSB, the relaxation process in an FRSB landscape should involve an infinite hierarchy of time scales. While the 2RSB approximation used here is a significant improvement, a full FRSB solution would be necessary for exact quantitative results in the unstable region. Future research should extend this framework to specific combinatorial problems like $k$-SAT to better understand the "algorithmic gap" between what local searches can find and the true global optimum.

Summary updated

BibTeX
@article{montanari2003nature,
  author = {Andrea Montanari and Federico Ricci‐Tersenghi},
  title = {{On the nature of the low-temperature phase in discontinuous mean-field spin glasses}},
  journal = {The European Physical Journal B},
  year = {2003},
  doi = {10.1140/epjb/e2003-00174-7},
}
Figure