CS Paper Radar

How Path Integral Diffusion Decides a Finite Spin Glass

Michael Chertkov

cs.AI cond-mat.dis-nncond-mat.stat-mechstat.ML ·submitted 2026-11-09 03:44 UTC · v1

Abstract

When an AI diffusion-type generator samples a frustrated spin glass, which macroscopic alternatives does it decide first, and when? We study this for bridge-diffusion models of the Path Integral Diffusion (PID) type started from a point source. We show that every isotropic PID is a time-changed Gaussian stochastic localization, and conversely every signal-to-noise schedule is realized by a PID protocol. What a continuous-time generator decides therefore does not depend on the protocol, which only sets when and at what cost. We describe the generator's state by its partial commitments: the probabilities it assigns, at each moment, to nested classes of configurations fixed by the target. The partial commitments are martingales that move only along class contrasts. Their ensemble average gives the information about each level at an exact rate set by squared magnetization contrasts. Each split is decided, approximately, like a binary Gaussian channel at signal-to-noise ratio 1.04/λ_P, with λ_P the leading eigenvalue of the parent's correlation matrix. The theory is applied to Bethe-lattice and Sherrington--Kirkpatrick (SK) glasses with up to 64 spins. It is observed generically that a trajectory first shifts its weight to one of the two mirror halves of the zero-field measure and then to the glassy classes inside it. These classes appear near the glass transition and keep their identity on cooling. Nested glassy levels have similar λ_P and are decided together, so a trajectory commits in one or two distinct events---the mirror choice and a compound glassy decision---which separate further with coupling and size, as the spectra predict. For a generator that takes finitely many steps, the protocol matters through the late, local stage rather than the macroscopic decisions.

Comment
42 pages, 15 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Discrete Diffusion Models via Evolving Variational Autoregressive Networks

cs.LG cond-mat.dis-nnstat.ML ·2026-09-23 ·Kewen Pan, Ying Tang
similarity 0.59
Abstract

Conventional score-based diffusion models learn scores without representing normalized densities, whereas tractable normalized models support both sampling and direct likelihood evaluation. A recent tensor-network approach provides such a representation but is largely restricted to low-dimensional lattices. Here we introduce a discrete diffusion model that parameterizes normalized probability distributions using variational autoregressive networks. Explicit Markov jump operators govern the forward noising and reverse denoising dynamics, extending discrete diffusion models with normalized distributions to spin systems on higher-dimensional lattices. We apply this framework to the two- and three-dimensional Ising models across ordered, critical, and disordered regimes, accurately computing thermodynamic quantities including free energy, energy, and magnetization. We further integrate the framework with Monte Carlo sampling, using adaptive diffusion steps to maintain high acceptance rates even at low temperatures while enhancing sample diversity. These results establish a neural-network framework for the discrete diffusion model with normalized probability distributions.

0.17

Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry

cs.CC quant-phcond-mat.dis-nncs.DS+1 ·2026-09-30 ·Leo Zhou, Noah Shutty, Mark Sellke, Stephen P. Jordan
theoryhot direction similarity 0.52
Abstract · 44 pages, 1 figure, 3 tables

We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising $k$-spin glasses (or Max-$k$-XORSAT) on random Erdős-Rényi hypergraphs with average degree $D\ge k$. In a temperature range beginning asymptotically at the predicted dynamical phase transition, $β_{\rm dyn}(k,D) = \sqrt{(2\ln k)/D}\times [1+o_{k\to\infty}(1)]$, we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when $D=αk$ with fixed $α>1$, both Prange's algorithm and DQI can sample at any inverse temperature $β< \tanh^{-1}(1/α)$ for sufficiently large $k$, well beyond the dynamical threshold $β_{\rm dyn} \sim \sqrt{2\ln k / (αk)}$. Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.

0.61

Some remarks on the connection between generative diffusion and optimal transport

cs.LG stat.MLcond-mat.dis-nn ·2026-10-09 ·Giulio Biroli, Marc Mézard
similarity 0.52
Abstract

We discuss three simple connections between generative diffusion and optimal transport. First, the joint law of the data and of their Ornstein-Uhlenbeck noising is, at every time, the solution of an entropic optimal-transport problem, at a temperature set by the noise level. Backward diffusion can consequently be read as an annealing which gradually decreases the entropic regularization. Second, we study the speciation transition--how the modes of the data distribution emerge during generation--and compare how it happens in diffusion and flow matching with respect to optimal transport. Using Gaussian mixtures as high-dimensional example, we show that the dynamical instability through which diffusion and flow matching separate the modes becomes, for optimal transport, an exponentially thin boundary layer at the beginning of generation, which is rounded by entropic regularization. Third, considering a generic forward dynamics with a general confining potential, we show that the backward process driven by the score also satisfies a drift-based variational principle whose minimal cost is the entropy difference between initial and final distributions.

0.29

Regev's Reduction Reaches Reconstruction

cs.DS quant-phcond-mat.dis-nn ·2026-11-06 ·Stephen P. Jordan, Quynh T. Nguyen, Leo Zhou
similarity 0.52
Abstract · 30 pages, 4 figures

Regev's reduction uses a quantum Fourier transform to carry out reductions between various problems related to lattices and codes. We apply it to the problem of sampling from Gibbs distributions of certain classical spin glass Hamiltonians, which can equivalently be thought of as cost functions for average-case instances of an optimization problem called $D$-regular max-$k$-LINSAT. This problem becomes hard at low temperature. Here, we use a quantum decoding algorithm called Belief Propagation with Quantum Messages (BPQM) to solve the decoding problem arising from Regev's reduction. Our main contribution is a proof that the minimum temperature reachable using Regev+BPQM is exactly equal to the reconstruction threshold temperature for noisy channels transmitting signals on a tree network. This equality can be understood via Renes' duality between classical and quantum channels, which we use to show that quantum decoding is possible exactly when classical reconstruction on the dual problem is impossible. M{é}zard and Montanari identified this reconstruction temperature with a dynamical glass transition predicted by the one-step replica-symmetry breaking (1RSB) cavity equation. It is conjectured that local samplers such as Metropolis Monte Carlo and Glauber dynamics cannot equilibrate efficiently below this reconstruction temperature but may do so above it; our large numerical experiments show close agreement with this prediction across hundreds of different problem parameters. Therefore, our results rigorously show that Regev+BPQM reaches a temperature for which, to our knowledge, there is no matching classical guarantee, and brings Regev+BPQM to the conjectured limit of efficient Gibbs sampling by classical local dynamics.

0.18

Generative diffusion in long-range correlated landscapes: Speciation cascade and the foam structure of the score

cs.LG cond-mat.dis-nncond-mat.stat-mech ·2026-11-02 ·Jerome Garnier-Brun, Giulio Biroli, Marc Mézard, Jean-Philippe Bouchaud
similarity 0.51
Abstract · 25 pages, 7 figures

While state of the art for image and video generation, the fundamental reasons for the effectiveness of generative diffusion remain unclear. In particular, the observed advantage of following an entire reverse process with respect to single-shot or autoregressive methods, and for what type of data it may hold, is not well understood. In this work, we aim to better understand the role of the reverse process by considering a complex yet analytically tractable data model, the Gibbs measure of a high-dimensional Gaussian random potential with long-range correlations. Focusing on the exact score, we show that the speciation threshold, in which a trajectory commits to one class of the data, becomes a speciation window, in which the reverse process progressively resolves the Parisi tree of pure states of the full replica-symmetry breaking measure, committing to ever finer branches down to a single pure state. Importantly, these commitments take place at noise levels where the noisy sample distinguishes the pure states only through an energy of order one, beyond the reach of standard replica saddle points. Constructing a Larkin argument suited to such $O(1)$ energy gaps, we describe the score as a foam, with slab-like cells separated by shock-like boundaries. In the variance-exploding process we consider, this window is followed by a shrinkage of the samples towards the data support, and finally by reconstruction within the selected pure state. The denoising error of the exact score follows these stages, dropping during the speciation window with a profile set by the Parisi function alone, and then within the selected state. We believe that the generative foam we describe, and in particular the boundaries between cells, could play an important role in determining where the errors of trained diffusion models redistribute the mass of the generated samples when the data are long-range correlated.

0.29

Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model

cs.DS math.PR ·2026-10-07 ·Zhe Hou, Jingcheng Liu, Yixiao Yu
similarity 0.51
Abstract

We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature $0\leqβ<1$ and every fixed $M,D>0$, we give a polynomial-time simulated annealing algorithm whose output distribution is within $n^{-M}$ total-variation distance of the Gibbs distribution, with probability at least $1-n^{-D}$ over the interaction matrix. The algorithm starts from uniform product spins and uses Glauber dynamics along an increasing inverse-temperature schedule. The same approach also yields partition-function estimates with relative error $n^{-M}$. The key ingredient is a quantitative weak Poincaré inequality. Building on the stochastic-localization approach to weak Poincaré inequalities [Davies, Lee, Sandhu, and Shi, arXiv:2607.08160, 2026], we use Gaussian isoperimetry to directly compare exact stochastic localization paths. Our comparison tolerates failures of local Lipschitz continuity of the posterior mean by controlling their accumulated cost. The local Lipschitzness comes from approximating the posterior means by stationary points of the Thouless-Anderson-Palmer (TAP) free energy in locally strongly convex regions located by approximate message passing, a paradigm introduced by algorithmic stochastic localization [El Alaoui, Montanari, and Sellke, 2025; Celentano, 2024]. The approximation errors are roughly characterized by the validity of the TAP gradient equations, but in a different coordinate. To show that the errors rarely accumulate too much, we need a strong concentration control. A direct argument would require solving a variant of an open problem by Talagrand [2010, Research Problem 1.7.9]. We bypass this open problem with an intermediate conditioning step and transfer the control back by establishing the stability of the TAP gradient under deletion of coordinates.

0.39

Stochastic Diversity Windows: Diagnosing Noise Influence in Robotic Diffusion Sampling

cs.RO cs.LG ·2026-11-17 ·Tina Lakhani, Jing Wu, Yu-Kun Lai, Ze Ji
similarity 0.51
Abstract · 26 pages, 3 figures, 6 tables

Diffusion models are increasingly adopted in robotics and control due to their capability to express multiple feasible solutions to a given task. However, the role of stochasticity in the diffusion model-sampler across denoising remains poorly understood. We introduce a per-timestep counterfactual diagnostic that tests how changing the sampled noise affects the final output. Across five model-sampler configurations spanning three robotics benchmarks, diverse architectures, domains, and conditioning mechanisms, we reveal highly varied temporal sensitivity profiles, where noise-induced deviations can amplify, partially contract, or undergo near-total attenuation downstream. From these profiles, we define stochastic diversity windows (SDWs): compact intervals that identify where sampler stochasticity has the strongest measured influence on the final output. Guided by these windows, we apply two heuristic interventions: targeted stochastic amplification, which increases sample diversity exploration of the solution space, and an SDW-hybrid sampler, which replaces DDPM steps with DDIM skips in low-impact regions, resulting in network evaluation reductions of up to 40-60% and wall-clock time by up to 85%, with no consistent changes detected in feasibility, cost, or diversity across held-out tasks.

0.32

The Lattice of Transition Laws

cs.LG cs.CL ·2026-10-08 ·T. Y. Tsui, Jiatao Gu, Lingjie Liu
code/data similarity 0.51
Abstract

Diffusion and autoregression (AR) have long been seen as different categories of generative models, with diffusion specialising in continuous fields and AR specialising in discrete tokens. Recent work seeks to combine the advantages of the two models, and each hybrid fixes its decoding schedule by design. In this paper, we ask whether the performance of decoding schedules of one model can be predicted before decoding at a fixed number of steps. We describe diffusion, AR, and models in between as paths on one corruption lattice, and define the cost of a schedule as the dependence its parallel steps discard. The cost shows that the fewest steps of a zero-cost schedule are set by the geometry of the data, in the same way for tokens and for continuous fields. In particular, for data that are Markov on a graph and dependent along its paths, the fewest steps equal the graph's treedepth, which is logarithmic in the length of a sequence and linear in the side length of a grid. With fewer steps than the treedepth, every schedule pays a positive cost, whose ranking we predict before decoding with a kernel of pairwise dependence estimated from pretrained weights. Across text generation, image generation, and video generation, we verify most of the predictions about the rankings of different schedules under different metrics and benchmarks. This work therefore provides a design principle for decoding for future AR models, diffusion models, and anything in between. Our code is available at https://github.com/TSUITUENYUE/The-Lattice-of-Transition-Laws.

0.32