# Parallelising Glauber dynamics

arXiv: https://arxiv.org/abs/2307.07131 · HTML: https://mlsanity.com/paper/2307.07131/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2023.

## Built on by (most cited first, 3 of 3)

- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [Parallel Sampling via Counting](https://mlsanity.com/paper/2408.09442/) (2024)
- [Leveraging Pretrained Language Models as Energy Functions for Glauber Dynamics Text Diffusion](https://mlsanity.com/paper/2605.04291/) (2026)

## Abstract (arXiv)

For distributions over discrete product spaces prodi=1n Omegai', Glauber dynamics is a Markov chain that at each step, resamples a random coordinate conditioned on the other coordinates. We show that k-Glauber dynamics, which resamples a random subset of k coordinates, mixes k times faster in chi2-divergence, and assuming approximate tensorization of entropy, mixes k times faster in KL-divergence. We apply this to obtain parallel algorithms in two settings: (1) For the Ising model μJ,h(x)propto exp(frac1 2leftlangle x,Jx rightrangle + langle h,xrangle) with |J|<1-c (the regime where fast mixing is known), we show that we can implement each step of widetilde Theta(n/|J|F)-Glauber dynamics efficiently with a parallel algorithm, resulting in a parallel algorithm with running time widetilde O(|J|F) = widetilde O(√ n). (2) For the mixed p-spin model at high enough temperature, we show that with high probability we can implement each step of widetilde Theta(√ n)-Glauber dynamics efficiently and obtain running time widetilde O(√ n).