Low-Temperature Sampling via Equilibrium Disagreements
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Low-Temperature Sampling via Equilibrium Disagreements".
Jane: Here's the gist of the paper. The framework develops a new method for sampling at low temperatures using Glauber dynamics, addressing bottlenecks caused by phase coexistence in this regime, which can otherwise lead to exponentially slow mixing times.
Tom: The core innovation is relating convergence within a single phase to the geometry of disagreements between two independent configurations drawn from that phase.
Jane: The approach is applied to three canonical models on random regular graphs: 1.
Tom: Hard-core model on random bipartite d-regular graphs: Glauber dynamics initialized from either one-sided independent set mixes within the corresponding phase in n 3/2+o(1) steps throughout the non-uniqueness regime lambda > lambda c(d).
Paper summary: Tom: So to recap, the paper "Low-Temperature Sampling via Equilibrium Disagreements" introduces a new framework for sampling at low temperatures using Glauber dynamics that overcomes bottlenecks caused by phase coexistence, which usually leads to exponentially slow mixing times.
Jane: The main thesis is relating convergence within a single phase to the geometry of disagreements between two independent configurations drawn from that same phase, which provides a path toward fast convergence from natural initializations.
Lu: They apply this idea to three canonical models on random regular graphs: the hard-core model on random bipartite d-regular graphs, the random-cluster model on random d-regular graphs, and the ferromagnetic Ising model >
Meng: For these models, they establish fast convergence times for Glauber dynamics starting from natural initializations within each phase, specifically showing mixing within n to the power of three over one plus o one steps under certain conditions on parameters like lambda or beta >
Lalam: They also contribute an algorithm that combines these phase samples into an epsilon sample from the full distribution, which avoids time-costly approximations of the partition functions and this is especially important for models like the hard-core and ferromagnetic Ising model >
Tom: Essentially, they've moved from a problem where we had to wait for potentially exponential times to a situation where we have concrete time bounds based on geometric properties of the configurations >
Jane: It matters because these results apply across different types of phase transitions; for example, the hard-core phases merge at the uniqueness threshold, while the random-cluster phases remain distinct and stable even at beta sub c of d >
Conclusion: Tom: So looking at the whole paper "Low-Temperature Sampling via Equilibrium Disagreements" and its authors, they've provided concrete runtime bounds for sampling in regimes where standard methods would struggle due to phase coexistence.
Jane: The big takeaway is that by focusing on the geometry of disagreement between two samples from the same phase, they’ve created a new way to guarantee fast convergence for Glauber dynamics using natural starting points >
Lu: This framework connects equilibrium configuration geometry directly to Glauber dynamics convergence, leading to bounds like n to the power of three steps for several key models >
Meng: For someone who has to deploy this at scale, the practical implication is that we can expect much faster sampling times than what's currently guaranteed by standard theoretical approaches when dealing with these multi-modal distributions >
Lalam: The authors also developed a fast algorithm to get an epsilon sample from the full distribution in time proportional to n squared, which is significant because it avoids those slow approximation techniques for partition functions >
Department of Computer Science, University of Oxford · Department of Computer Science, University of Rochester
cs.DM, cs.DS, math.PR
Submitted: 2026-11-05
Updated: 2026-11-05
Comments: Abstract shortened to fit arXiv requirements
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 97/100
The gist: The framework develops a new method for sampling at low temperatures using Glauber dynamics, addressing bottlenecks caused by phase coexistence in this regime…
Key concepts
- Glauber Dynamics
- This is a method used to simulate physical systems, like spin models, by making local changes randomly. In this paper, it's used to sample configurations from the target phase of a model at low temperatures. The goal is to ensure the simulation reaches the correct equilibrium state quickly.
- Phase Coexistence
- This occurs when a system can exist in multiple stable states simultaneously, which often leads to very slow mixing times in simulations. The paper addresses this bottleneck by relating convergence to how two independent samples from the same phase disagree geometrically.
- Weak Poincaré Inequality
- This is a mathematical tool used to prove fast convergence rates for Markov chains like Glauber dynamics. The authors derive a simple version based on the geometry of disagreements between two independent configurations, which allows them to bound the variance and guarantee rapid mixing.
Terminology
Summary
The framework develops a new method for sampling at low temperatures using Glauber dynamics, addressing bottlenecks caused by phase coexistence in this regime, which can otherwise lead to exponentially slow mixing times. p. 0 Low-Temperature Sampling via Equilibrium Disagreements
Andreas Galanis∗ Daniel Štefankovič†
5 November 2026
Abstract
We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases) creates
bottlenecks that can make worst-case mixing exponentially slow. In this regime, the coexistence of competing modes (commonly referred to as phases) creates
bottlenecks that can make worst-case mixing exponentially slow. The main new ingredient in
our framework is to relate convergence within a phase to the geometry of disagreements between
two independent configurations drawn from that phase.Where the paper says it
Where the paper says it
The approach is applied to three canonical models on random regular graphs:
-
Hard-core model on random bipartite d-regular graphs: Glauber dynamics initialized from either one-sided independent set mixes within the corresponding phase in n 3/2+o(1) steps throughout the non-uniqueness regime lambda > lambda c(d).
-
Random-cluster model on random d-regular graphs: For every real q > 2, Glauber dynamics initialized from the all-in edge set mixes within the ordered phase in n 3/2+o(1) steps for all beta at least beta c. Similarly, initialization from the all-out edge set mixes within the disordered phase in n 3/2+o(1) steps for beta at most beta c. p. 0
Where the paper says it
• For the random-cluster model on random d-regular graphs, for every real q > 2, Glauber dynamics initialised from the all-in edge set mixes within the ordered phase in n 3/2+o(1) steps for all β ≥ βc. Similarly, Glauber dynamics initialised from the all-out edge set mixes within the disordered phase in n 3/2+o(1) steps for β ≤ βc.
-
Ferromagnetic Ising model on random d-regular graphs: Glauber dynamics initialized from all-plus or all-minus mixes within the corresponding phase in n 3/2+o(1) steps throughout the low-temperature regime beta > beta c(d).
A key technical contribution is a simple combinatorial route to weak Poincaré inequalities, motivated by previous work (Huang et al. p. 0 These results resolve previously open parts of the
low-temperature regime that either required sufficiently strong interactions or large degree d. Our main contribution is a simple combinatorial route to weak Poincaré inequalities, motivated by the sampling framework of Huang, Mohanty, Rajaraman, and Wu (STOC 2025). These results resolve previously open parts of the
low-temperature regime that either required sufficiently strong interactions or large degree d. Our main contribution is a simple combinatorial route to weak Poincaré inequalities, motivated by the sampling framework of Huang, Mohanty, Rajaraman, and Wu (STOC 2025). Their approach to such inequalities is analytical, relying on spectral-norm bounds under typical
pinnings or along localization processes. Our approach instead works directly with the geometry
of disagreements between two independent samples from the target phase distribution. Our approach instead works directly with the geometry
of disagreements between two independent samples from the target phase distribution. These
disagreements typically split into small, tree-like components of size O(log n). These
disagreements typically split into small, tree-like components of size O(log n). We then convert
this geometric understanding of the disagreements into a weak Poincaré inequality via an elementary canonical-path argument between typical pairs, with exceptional pairs of configurations
contributing only to the additive error in the resulting weak Poincaré inequality. We then convert
this geometric understanding of the disagreements into a weak Poincaré inequality via an elementary canonical-path argument between typical pairs, with exceptional pairs of configurations
contributing only to the additive error in the resulting weak Poincaré inequality. This geometric
criterion is amenable to techniques from the analysis of random CSPs, and we verify the required
conditions using double-planted models. This geometric
criterion is amenable to techniques from the analysis of random CSPs, and we verify the required
conditions using double-planted models. Combined with simulated annealing and monotonicity,
the resulting inequalities yield fast convergence of Glauber dynamics from natural initialisations.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
For bipartite independent sets, Theorem 1 states that for any K > 0, whp over G about G bip n,d, the configuration (X+t) t at least 0 is within TV-distance epsilon = 1/nK from mu+G in t = O(n tilde 3/2) steps. p. 2 This bimodality causes bottlenecks and makes Glauber dynamics mix exponentially slowly from
worst-case configurations; in fact, this bimodality on the random bipartite graph is behind strong
inapproximability results for λ > λc(d), see [Sly10, SS12, GŠV16]. To state our phase sampling results, let I
+
G denote the independent sets with at least as many
vertices occupied on the + side versus on the - side. Our framework analyses
convergence within the original phases and gives substantially sharper running-time guarantees for
sampling, while removing the restriction to sufficiently large degrees altogether. Random-Cluster/Ferromagnetic Potts model.Where the paper says it
Where the paper says it
The framework connects equilibrium configuration geometry to Glauber dynamics convergence. p. 2 Extending our hard-core guarantees to activities whose
distance from λc(d) vanishes with n remains an interesting open direction. Our framework connects the geometry of equilibrium configurations to the convergence of Glauber
dynamics. 2 Proof Outline/Organization
Our starting point is that the variance of a function f under a distribution can be expressed through
its difference on two independent samples. This makes the geometry of equilibrium disagreements
(capturing the difference of the two samples) a natural tool for studying convergence. The resulting approach turns a geometric understanding of equilibrium configurations into
guarantees for Glauber dynamics from natural initialisations. Various parts of this work have been produced with the help of ChatGPT Astra 6.Where the paper says it
Where the paper says it
Where the paper says it
The full-sampling assertion is demonstrated via a combination of phase partition-function estimators derived from simulated annealing and weak Poincaré inequalities, coupled with a phase selection algorithm based on upper-tail estimators, resulting in an O(n 2+o(1)) -time algorithm. p. 6 By spin-flip symmetry, the same running time suffices to
sample from the full distribution. Weak Poincaré Inequalities Our approach is motivated by the work of Huang, Mohanty,
Rajaraman, and Wu [HMRW25] who developed a framework combining weak Poincaré inequalities
with simulated annealing to obtain sampling guarantees beyond worst-case mixing; see also the
recent follow-up [DHMR26]. Our result establishes n
3/2+o(1) convergence from all-plus or all-minus within the corresponding
phase for every fixed d ≥ 3 and β > βc(d). By spin-flip symmetry, the same running time suffices to
sample from the full distribution.Where the paper says it
Where the paper says it
The final result for the hard-core model (Theorem 1) is an algorithm that outputs an epsilon-sample from the full distribution mu G in time O(n 2). p. 3 There is an algorithm that outputs in time O˜(n
2
) an ε-sample from the full distribution µG. We give the proof of the first part of Theorem 1 in Section 3. Our result establishes n
3/2+o(1) convergence from all-plus or all-minus within the corresponding
phase for every fixed d ≥ 3 and β > βc(d). By spin-flip symmetry, the same running time suffices to
sample from the full distribution.Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved low-temperature sampling for hard-core models on random bipartite graphs can achieve mixing in n 3/2+o(1) steps throughout the non-uniqueness regime lambda > lambda c(d).
-
The framework can be used to provide an n 2+o(1)-time algorithm that combines phase samples into samples from the full distribution, avoiding time-costly approximations of partition functions.
-
The system can derive a simple combinatorial route to weak Poincaré inequalities by relating convergence within a phase to the geometry of disagreements between two independent configurations drawn from that phase.
-
For random-cluster models on random d-regular graphs, Glauber dynamics can mix within the ordered phase in n 3/2+o(1) steps for all beta >= beta c.
-
The framework enables fast convergence of Glauber dynamics from natural initialisations for the ferromagnetic Ising model throughout the low-temperature regime beta > beta c(d) in n 3/2+o(1) steps.
-
The system can perform phase selection using upper-delta-tailed estimators derived from simulated annealing and weak Poincaré inequalities to produce an epsilon sample from the full distribution with a running time of O˜n 2).
-
The system can generate samples from the random-cluster model by leveraging double phase planting, where the probability of getting a good pair is bounded by n K g(n) for appropriate constants.
-
For Ising models, the system can perform full sampling with a total running time of O˜n 2), using an algorithm that combines O(log n) estimator repetitions and an O˜n 3/2) phase sample cost.
Abstract
We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases) creates bottlenecks that can make worst-case mixing exponentially slow. The main new ingredient in our framework is to relate convergence within a phase to the geometry of disagreements between two independent configurations drawn from that phase. As applications of our approach, we consider three canonical models on random regular graphs that have been central to low-temperature sampling, and establish fast convergence from natural initialisations of Glauber dynamics for every fixed degree. We show: --- For the hard-core model on random bipartite d-regular graphs, Glauber dynamics initialised from either one-sided independent set mixes within the corresponding phase in n 3/2+o(1) steps throughout the non-uniqueness regime λ>λ c(d). --- For the random-cluster model on random d-regular graphs, for every real q>2, Glauber dynamics initialised from the all-in edge set mixes within the ordered phase in n 3/2+o(1) steps for all β at least β c. Similarly, Glauber dynamics initialised from the all-out edge set mixes within the disordered phase in n 3/2+o(1) steps for β at most β c. --- For the ferromagnetic Ising model on random d-regular graphs, Glauber dynamics initialised from all-plus or all-minus mixes within the corresponding phase in n 3/2+o(1) steps throughout the low-temperature regime β>β c(d). We also give an n 2+o(1) -time algorithm that combines phase samples into samples from the full distribution, avoiding in particular time-costly approximations of the corresponding partition functions to the target sampling accuracy.
Sources
- Rapid mixing of Potts Glauber dynamics throughout uniqueness
- Uniqueness and Mixing in the Low-Temperature Random-Cluster Model on Trees and Random Graphs
- Rapid Mixing on Random Regular Graphs beyond Uniqueness
- Characterizing the limiting critical Potts measures on locally regular-tree-like expander graphs
- Planting and MCMC Sampling from the Potts model
- Rapid phase ordering for Ising and Potts dynamics on random regular graphs
- Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
- Near linear mixing of random-cluster Glauber dynamics on random regular graphs
- Improved rapid phase ordering for Ising dynamics on random regular graphs
- The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities
- On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics
Related papers
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns
- Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds