🔢 mathematics

Sampling from the Sherrington-Kirkpatrick Model up to Criticality

This paper proves that the simulated annealing algorithm efficiently samples from the Sherrington-Kirkpatrick model at inverse temperatures below the critical threshold of $\beta < 1$ with arbitrary inverse polynomial accuracy in total variation distance.

Original authors: Hang Du, Brice Huang, Sidhanth Mohanty, Amit Rajaraman

Published 2026-10-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hang Du, Brice Huang, Sidhanth Mohanty, Amit Rajaraman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast, complex landscape made of countless tiny switches, each capable of pointing either up or down. In the world of physics, this is a model for how materials behave when their internal parts interact in complicated ways, a scenario known as a spin glass. The specific landscape this research explores is called the Sherrington–Kirkpatrick model. It is a mathematical representation of a system where every switch influences every other switch, creating a web of connections so dense that predicting the final arrangement of the switches becomes a monumental challenge. Scientists have long been interested in this model not just for understanding magnets, but because it serves as a testing ground for how computers can solve difficult optimization problems and make sense of noisy data. The central question has been whether a computer can efficiently find a random, typical arrangement of these switches that matches the natural state of the system, especially when the system is warm enough to be fluid but not so hot that it is chaotic.

For decades, researchers believed that a standard method called Glauber dynamics, which slowly flips switches one by one to reach a stable state, would work quickly in this warm regime. However, proving this has remained one of the most stubborn open problems in the field. The difficulty lies in the fact that the landscape is filled with deep valleys and high peaks; a computer trying to find the right spot might easily get stuck in a local valley, unable to see the true global arrangement. While previous attempts could only guarantee success in very specific, limited conditions, a new study has finally cracked the code for the entire warm regime. The researchers proved that a technique called simulated annealing, which is a clever variation of the standard method, can successfully sample from this complex system with high precision.

The team, led by researchers from MIT, Stanford, and Northwestern, demonstrated that by starting with a very hot, disordered system and slowly cooling it down while letting the switches settle, a computer can reach the correct statistical distribution of states in a reasonable amount of time. This result holds true for any temperature below a critical threshold where the system begins to freeze into a rigid, glassy state. The proof is significant because it confirms that the algorithm does not get trapped in the wrong configurations, a fear that had persisted for years. The researchers showed that the algorithm works with a level of accuracy that can be made arbitrarily high, meaning the output is virtually indistinguishable from the true natural state of the system.

To reach this conclusion, the authors had to develop a new way of looking at the problem. They focused on a concept called the covariance, which measures how much the state of one switch is linked to the state of another. If these links are too strong or unpredictable, the system becomes impossible to navigate efficiently. The team proved that in this specific model, these links remain well-behaved and bounded, even as the system grows larger. They used a sophisticated mathematical framework known as stochastic localization, which can be thought of as a way of gradually revealing the hidden structure of the system by adding small amounts of information over time. By tracking how the system responds to this gradual revelation, they were able to show that the landscape does not contain the hidden traps that would stop the algorithm.

A key part of their work involved comparing the actual system to a slightly modified version where a specific pattern is secretly planted. This allowed them to simplify the complex interactions and prove that the system's behavior is stable and predictable with high probability. They established that the mathematical properties governing the system's stability hold true across the entire range of temperatures they studied. This finding is not just a theoretical victory; it has direct implications for how we understand statistical inference, which is the process of drawing conclusions from data. In fields ranging from machine learning to signal processing, algorithms often need to recover a hidden signal from noisy data, a task mathematically similar to finding the right arrangement of switches in this model. The success of simulated annealing in this context suggests that these algorithms can be trusted to find the correct answer even in very difficult scenarios.

The paper also addresses the limits of what can be proven. The researchers were careful to show that their method works specifically for the zero-field model, where there is no external force pushing the switches in a particular direction. They noted that extending this proof to cases with an external force is a logical next step but requires additional work. Furthermore, they highlighted that while their proof relies on the random nature of the connections between switches, it does not yet provide a simple, checkable condition that a user could verify before running the algorithm. This distinction is important because it means the success of the method is guaranteed by the statistical properties of the random system itself, rather than by a quick test of the input data.

Ultimately, this work resolves a long-standing question about the efficiency of sampling from complex systems. It confirms that the simulated annealing algorithm is a powerful tool capable of navigating the intricate landscape of the Sherrington–Kirkpatrick model up to the very edge of its critical temperature. By proving that the system's internal correlations remain manageable, the authors have provided a rigorous foundation for using these algorithms in both theoretical physics and practical applications. The result is a clear demonstration that, contrary to earlier fears, the complexity of the system does not prevent efficient computation, provided the right strategy is used to guide the process. This insight opens the door to more reliable methods for solving some of the most challenging problems in data science and statistical physics.

Problem Statement
The paper addresses the problem of efficiently sampling from the Sherrington–Kirkpatrick (SK) model, a mean-field spin glass model defined by the Gibbs distribution $\mu_{\beta W}(\sigma) \propto \exp(\frac{\beta}{2} \langle \sigma, W\sigma \rangle)$ , where $W$ is a random matrix drawn from the Gaussian Orthogonal Ensemble (GOE). The primary focus is the high-temperature regime where the inverse temperature $\beta < 1$ . While it is widely believed that Glauber dynamics mixes rapidly in this regime, proving this has remained a major open problem. Previous algorithmic results for sampling from the SK model were limited to $\beta < 1/2$ or achieved only sub-constant total variation (TV) distance guarantees. The goal is to design an algorithm that samples from the SK model for all $\beta < 1$ with arbitrary inverse polynomial accuracy in total variation distance.

Methodology
The authors employ simulated annealing, a time-dependent Markov chain where the inverse temperature is slowly incremented from 0 to the target $\beta$ . The algorithm's success relies on the existence of a weak Poincaré inequality for the intermediate distributions along the annealing path. Specifically, the paper utilizes the localization schemes framework (Chen–Eldan) to reduce the problem of proving a weak Poincaré inequality for the Gibbs measure to establishing high-probability covariance bounds for a suitably modified SK model along a stochastic localization path.

Key technical steps include:

Stochastic Localization: The Gibbs measure is decomposed into a martingale of measures $(\mu_t)_{0 \le t \le T}$ . The authors show that if the endpoint measure $\mu_T$ satisfies a Poincaré inequality and the covariances $\text{Cov}(\mu_t)$ are spectrally bounded along the path, then the initial measure satisfies a weak Poincaré inequality.
Planted Model Reduction: To make the analysis of the localization path tractable, the authors shift from the zero-field SK model to a "planted" model where a hidden spin configuration $x$ is introduced. This allows for a more precise characterization of the posterior distribution during localization.
Covariance Prediction via TAP Equations: The core technical contribution involves proving that the covariance matrix of the planted model is close to a prediction derived from the Thouless–Anderson–Palmer (TAP) equations (specifically, the inverse of the TAP Hessian, denoted $K$ ).
Decoupling and Expansion: The authors use the cavity method and Taylor expansions to decouple the disorder $W$ from the cumulants of the Gibbs measure. They analyze the error terms involving higher-order cumulants ( $\kappa_r$ ) and show they are negligible with high probability.
Spectral Bounds: They establish that the predicted inverse covariance matrix $K$ is bounded away from zero (positive definite) with high probability, utilizing techniques from Approximate Message Passing (AMP) and previous work on the local convexity of the TAP free energy.

Key Contributions and Results

Main Theorem (Theorem 1.1): The authors prove that simulated annealing, run for $O(N \log N)$ steps of Glauber dynamics per iteration with a specific temperature schedule, samples from the SK model $\mu_{\beta W}$ for any $\beta < 1$ with total variation distance at most $N^{-a}$ (for any constant $a > 0$ ) with high probability over the disorder $W$ . This is the first algorithm to achieve arbitrary inverse polynomial accuracy for all $\beta < 1$ .
Weak Poincaré Inequality (Theorem 1.2): They establish that the SK model satisfies an $(O(N), N^{-a})$ -weak Poincaré inequality with high probability. This is achieved by proving high-probability covariance bounds for the localized measures.
Covariance Bounds (Theorem 1.3 & 1.4): The paper provides high-probability bounds showing that $\|\text{Cov}(\mu_{\beta W})\|_{op} \le L$ for the zero-field model and for the model at nonzero localization time. This resolves a question regarding the boundedness of the covariance operator norm in the high-temperature regime.
Technical Innovations: The work introduces a refined analysis of the TAP Hessian and its inverse, utilizing a combination of cavity expansions, Wick's formula for moment bounds, and Gaussian concentration to control error terms that previous methods could not handle up to $\beta = 1$ .

Significance
The paper claims to be the first to provide an efficient sampling algorithm for the SK model across the entire high-temperature regime ( $\beta < 1$ ) with strong accuracy guarantees. This result has implications for statistical inference, particularly in the spiked Wigner model, where it suggests that Markov chains can succeed at non-trivial recovery for all signal-to-noise ratios $\lambda > 1$ , matching the BBP phase transition threshold.

The authors note that while their proof relies heavily on the distributional assumptions of the input (the GOE matrix), it does not yield a "certifiable" sampler (one with an efficiently checkable condition for success) in the same way previous spectral-gap-based proofs did. They acknowledge that concurrent work by OpenAI has also established a spectral gap for $\beta < 1$ using a different approach involving a "stability" criterion and a more refined boosting of weak Poincaré inequalities to true ones. The authors position their work as providing a flexible framework that successfully establishes weak Poincaré inequalities, which may extend to other models like $p$ -spin glasses up to their respective shattering thresholds.

Limitations and Future Directions
The paper explicitly states that it does not extend to the de Almeida–Thouless line (the regime with an external field), though it poses this as a future direction. It also highlights the distinction between sampling and counting (computing the partition function) in average-case models, noting that while their result improves sampling, the complexity of counting in the shattered phase remains an open area of investigation. The authors do not claim their techniques immediately solve the sampling problem for general $p$ -spin models or models with external fields, but suggest their covariance bound techniques could be adapted if sufficiently good overlap concentration results are established for those regimes.

More like this