Parallel Sampling from the Ising $p$-Spin Model

Abstract

We study the parallel complexity of sampling from the high-temperature Ising mixed $p$-spin Gibbs measure, a canonical instance of a mean-field spin glass on the hypercube $\{\pm 1{\}}^n$. We propose two different algorithms for this problem, corresponding to two different regimes of accuracy. Our first algorithm is a parallel implementation of a Markov chain known as block dynamics, combined with an approximate rejection sampling step that uses an Ising model in a novel way as a proposal distribution to approximate the quadratic interaction terms of the $p$-spin Hamiltonian. For any $\epsilon >0$, this algorithm runs in $n^{\frac{1}{3}}\mathrm{polylog}(\frac{n}{\epsilon })$ parallel time with $\mathrm{poly}(n,\log (\frac{1}{\epsilon }))$ work, and outputs a sample whose law is $\epsilon$-close to the $p$-spin measure in total variation distance. Our second algorithm uses Picard iterations to parallelize the Algorithmic Stochastic Localization (ASL) process of El Alaoui, Montanari, and Sellke (2025), and for any $\epsilon >{\epsilon }_n$, takes $\mathrm{polylog}(\frac{n}{\epsilon })$ parallel time and $\mathrm{poly}(\frac{n}{\epsilon })$ work to produce a sample that is $\epsilon$-close to the $p$-spin measure in the normalized 2-Wasserstein metric. Here, ${\epsilon }_n>0$ is a threshold that goes to $0$ as $n\to \infty$. Our result constitutes a doubly exponential improvement in the $\epsilon$ dependence of the runtime and an exponential improvement in the $\epsilon$ dependence of the total work when compared to naïve ASL, whose runtime scales as $\exp (\mathrm{poly}(\frac{1}{\epsilon }))$.

RANDOM 2026, to appear

Topics & keywords