Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Hengyuan Hu, Aniket Das, Dorsa Sadigh, Nima Anari · 2025
Read Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation by Hengyuan Hu, Aniket Das, Dorsa Sadigh, Nima Anari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-03983.txt.
Introduction
Hengyuan Hu, Aniket Das, Dorsa Sadigh, and Nima Anari showed in twenty twenty-five that diffusion models hide a symmetry. It lets their slow generation run in parallel. Denoising diffusion models make great samples. But they must run step by step, in a strict chain. The team links diffusion to stochastic localization. They prove the step increments are exchangeable under a reparametrization. In stats terms, order does not matter.
That point lets them import tools from autoregressive models. Their Autospeculative Decoding adapts speculative decoding to diffusion. It needs no extra draft model. The steps speculate on each other. Theory promises a near cubic-root speedup in parallel runtime, set by the step count. Working code sped up inference in several fields. That hints that exchangeability is a broad lever. It can speed up samplers of many kinds.
Catalog record
| CREATOR | Hengyuan Hu, Aniket Das, Dorsa Sadigh, Nima Anari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-03983
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation Hengyuan Hu, Aniket Das, Dorsa Sadigh, Nima Anari Abstract Denoising Diffusion Probabilistic Models (DDPMs) have emerged as powerful tools for generative modeling. However, their sequential computation requirements lead to significant inference-time bottlenecks. In this work, we utilize the connection between DDPMs and Stochastic Localization to prove that, under an appropriate reparametrization, the increments of DDPM satisfy an exchangeability property. This general insight enables near-black-box adaptation of various performance optimization techniques from autoregressive models to the diffusion setting. To demonstrate this, we introduce Autospeculative Decoding (ASD), an extension of the widely used speculative decoding algorithm to DDPMs that does not require any auxiliary draft models. Our theoretical analysis shows that ASD achieves a O ~ ( K 1 / 3 ) \operatorname{\mathnormal{\widetilde{O}}}\mathopen{}\lparen K^{\nicefrac{{1}}{{3}}}\mathclose{}\rparen parallel runtime speedup over the K K step sequential DDPM. We also demonstrate that a practical implementation of autospeculative decoding accelerates DDPM inference significantly in various domains. † † affiliationnotice: Equal contribution 1 Introduction Diffusion models have emerged as one of the leading tools in generative modeling ( Sohl-Dickstein et al., 2015 ; Ho et al., 2020 ; Song et al., 2021b ) . They are widely used to generate samples in continuous spaces, such as when an image ( Dhariwal & Nichol, 2021 ; Nichol et al., 2021 ; Kingma et al., 2021 ; Rombach et al., 2022 ) or a sequence of continuous actions ( Reuss et al., 2023 ; Chi et al., 2023 ) is desired. A major limitation of diffusion models, particularly limiting in real-time applications such as continuous control or robotics, is their slow inference time. Standard implementations of Denoising Diffusion Probabilistic Models (DDPMs) take a large number of denoising steps, \approx 1000 steps in image models ( Ho et al., 2020 ; Rombach et al., 2022 ) , and \approx 100 steps in robotics models ( Chi et al., 2023 ) , to generate samples. Using fewer steps empirically results in a loss of quality; theoretical analysis of DDPMs suggests that \approx\operatorname{\mathnormal{\widetilde{O}}}\mathopen{}\lparen d\mathclose{}\rparen steps are needed for high-fidelity samples from d -dimensional distributions ( Benton et al., 2023 ) . Numerous works have attempted to address slow inference. Works like DDIM ( Song et al., 2021a ) and DPMSolver ( Lu et al., 2022 ) have lowered the number of steps by altering the inference method to a deterministic one, barring the initialization, and utilizing ODE solvers. Other works ( Meng et al., 2022 ; Song et al., 2023 ; Watson et al., 2022 ; Lu & Song, 2024 ) have changed the underlying model, requiring new training, to enable fewer steps during inference. These speedups are all achieved by trading off the quality of the generated samples. Recently, Shih et al. (2024) showed that instead of trading off quality for speed, one can trade compute for speed by leveraging parallelization (e.g., utilizing multiple GPUs). However, the proposed method in ( Shih et al., 2024 ) still leaves a small but tunable error as it utilizes a fixed point iteration method with early stopping. Our work also focuses on accelerating inference in DDPMs via parallelization— albeit without changing the quality of the generated samples. Surprisingly, we show that it is possible to produce samples identically distributed as the sequential process, i.e., thereby ensuring zero quality loss, while also achieving a theoretically guaranteed speedup over sequential sampling. We prove that our method needs \approx\operatorname{\mathnormal{\widetilde{O}}}\mathopen{}\lparen d^{\nicefrac{{2}}{{3}}}\mathclose{}\rparen parallel calls to the model, much smaller than \approx\operatorname{\mathnormal{\widetilde{O}}}\mathopen{}\lparen d\mathclose{}\rparen in sequential sampling ( Benton et al., 2023 ) . Our algorithm adapts speculative decoding, an acceleration technique for autoregressive models such as large language models (LLMs), to the setting of diffusion models. Traditionally speculative decoding uses an additional smaller LLM (or model), called the draft, to accelerate sampling from the main LLM. The draft model produces tokens that are then in parallel verified by the main model – leading to possible parallel speedup. At first sight, adapting speculative decoding to diffusion models seems challenging for two reasons: first, the space is continuous; and second, a draft diffusion model is likely to follow very different trajectories from the main diffusion model, unlike two LLMs which can plausibly predict a few similar tokens at a time. We overcome these challenges by eschewing a draft model altogether , and instead show how to use the main diffusion model itself as its own draft. Our main insight enabling this autospeculation behavior is that the distribution of denoising trajectories in a diffusion model exhibits certain time symmetries. In technical terms, we show that after a syntactic time/scale change, the increments \mathbf{y}_{t+\mathop{}\!\mathrm{d}t}-\mathbf{y}_{t} of a denoising trajectory (\mathbf{y}_{t})_{t\in[0,T]} form an exchangeable sequence of random variables – in other words, their distribution remains unchanged under any permutation. This allows us to use independent samples from the distribution of the next denoising step as speculations for all future denoising steps. We emphasize that this secret property of diffusion models, which we refer to as hidden exchangeability is surprising. For example, in LLMs, a similar property would only hold if the sequences of tokens in the underlying distribution are permutation-invariant; that is the probability of “hello world” in the language is the same as “world hello.” In addition to enabling autospeculation, we use exchangeability to derive our theoretically guaranteed \approx\operatorname{\mathnormal{\widetilde{O}}}\mathopen{}\lparen d^{\nicefrac{{1}}{{3}}}\mathclose{}\rparen speedup. Our contributions can be summarized as follows: Hidden Exchangeability in DDPMs: We leverage the equivalence between DDPMs and Stochastic Localization ( Eldan, 2013 ; Chen & Eldan, 2022 ) , recently established by Montanari (2023) to uncover a fundamental hidden exchangeability property for the trajectories of DDPM. In particular, we show that, after an appropriate transformation, the increments of the DDPM process are exchangeable, i.e., their joint law is permutation-invariant. This insight enables us to view DDPMs through the lens of any-order autoregressive models ( Shih et al., 2022 ) , potentially allowing the adaptation of performance optimization techniques previously limited to traditional autoregressive architectures. Autospeculative Decoding for DDPMs: We use the hidden exchangeability property to design an efficient inference algorithm, which, at any given timestep a , makes a single call to the DDPM model to predict future increments, and subsequently makes calls to the same model, all in one parallel step to verify these predictions via rejection sampling. Our algorithm extends the Speculative Decoding ( Leviathan et al., 2023 ) paradigm, widely used for LLM inference, to the diffusion model setting. Unlike traditional speculative decoding, our algorithm eschews an auxiliary draft model and instead leverages the hidden exchangeability property to make the original DDPM speculate about itself. Hence, we call our algorithm Autospeculative Decoding (ASD) and show that it performs error-free DDPM inference with massive parallelization. Theoretical Guarantees: We prove that ASD is an error-free parallelization algorithm , whose output is identically distributed as sequential samples from the DDPM. Furthermore, under a minimal second-moment assumption, we prove that ASD makes at most \operatorname{\mathnormal{\widetilde{O}}}\mathopen{}\lparen d^{\nicefrac{{2}}{{3}}}\mathclose{}\rparen parallel calls to the model on d -dimensional distributions, as compared to \operatorname{\mathnormal{\widetilde{O}}}\mathopen{}\lparen d\mathclose{}\rparen calls needed in the sequential implementation of DDPM ( Benton et al., 2023 ) . To the best of our knowledge, our result is the first parallel inference algorithm for DDPMs that shows empirical speedups