Low-Temperature Sampling via Equilibrium Disagreements

arXiv:2611.08416 · cs.DM, cs.DS, math.PR · Submitted 2026-11-05 · Read on arXiv

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

Where the paper says it

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.

The core innovation is relating convergence within a single phase to the geometry of disagreements between two independent configurations drawn from that phase. p. 0
Where the paper says it

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.

The approach is applied to three canonical models on random regular graphs:

  1. 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).

  2. 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.

  3. 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

Where the paper says it

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).

, STOC 2025). p. 0
Where the paper says it

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).

This method works directly with the geometry of disagreements between two independent samples from the target phase distribution. p. 0
Where the paper says it

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.

These disagreements are characterized as splitting into small, tree-like components of size O(n). p. 0
Where the paper says it

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).

This geometric understanding is then converted into a weak Poincaré inequality via an elementary canonical-path argument between typical pairs, where exceptional pairs only contribute to additive error. p. 0
Where the paper says it

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.

This geometric criterion is amenable to techniques from the analysis of random CSPs and is verified using double-planted models. p. 0
Where the paper says it

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.

Combined with simulated annealing and monotonicity, these inequalities yield fast convergence guarantees from natural initializations. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

Similarly, for the random-cluster model (Theorem 2) and the ferromagnetic Ising model (Theorem 3), convergence to the stationary distribution (pi+G or nu+G) is shown in O(n tilde 3/2) time under appropriate conditions on beta. p. 5
Where the paper says it

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.

The framework connects equilibrium configuration geometry to Glauber dynamics convergence. p. 2

Where the paper says it

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.

The proof outline involves seeking a weak Poincaré inequality of the form Var mu(f) at most A, E P(f, f) + b(f - f) squared, established by studying two independent configurations from the same phase. p. 7
Where the paper says it

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.

This leads to bounds on the Dirichlet form and ultimately guarantees convergence for Glauber dynamics from natural initializations. p. 7
Where the paper says it

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.

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

Where the paper says it

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].

For the random-cluster model (Theorem 6), the probability of failure is bounded by 1/nD for specific sample sizes (R = C n / n and l = C' n) across a range of beta. The Ising model result (Theorem 34) also achieves an epsilon-sample from mu G within TV-distance 8 eta at most epsilon in total running time O(n 2). p. 6
Where the paper says it

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.

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

Where the paper says it

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.

The paper concludes by showing that the resulting sign is within TV-distance 5 eta of a Bernoulli with probability p about Z e+ / (Z e+ + Z e-), and conditional on the selected sign, Lemma 12 generates an eta-sample from the corresponding phase, leading to a final output within TV-distance 8 eta at most epsilon of mu G in total running time O(n 2). p. 6
Where the paper says it

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.

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

  1. 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).

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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).

  7. 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.

  8. 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

Related papers