Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Auto Speculation
Authors: Hengyuan Hu
Aniket Das
Dorsa Sadigh
Nima Anari
Venue: ICML 2025 poster (2025)
Keywords: DDPM
Stochastic Localization
speculative decoding
Primary area: theory->probabilistic_methods

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 $\tilde{O}(K^{\frac{1}{3}})$ parallel runtime speedup over the $K$ step sequential DDPM. We also demonstrate that a practical implementation of autospeculative decoding accelerates DDPM inference significantly in various domains.

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Hengyuan Hu"
Aniket Das
Dorsa Sadigh' Nima Anari
Abstract
robotics, is their slow inference time. Standard imple- mentations of Denoising Diffusion Probabilistic Models (DDPMs) take a large number of denoising steps, RV 1000 steps in image models (Ho et al., 2020; Rombach et al., 2022), and x 100 steps in robotics models (Chi et al., 2023), to generate samples. Using fewer steps empirically results in loss of quality; theoretical analysis of DDPMs suggests that RJ (d) steps are needed for high-fidelity samples from d- d-dimensional distributions (Benton et al., 2023).
Denoising Diffusion Probabilistic Models (DDPMs) have emerged 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-he 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'/s) parallel runtime speedup over the step sequential DDPM. We also demonstrate that a practical implementation of autospeculative decoding accelerates DDPM inference significantly in various domains.
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 ini- tialization, 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 com- pute 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 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.c., thereby ensuring zero quality loss, while also achieving a theoretically guaranteed speedup over sequential sampling. We prove that our method needs Ö(Pis) parallel calls to the model, much smaller than (d) in sequential sampling (Benton et al., 2023).
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 al., 2021; Rombach et al., 2022) or 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
Our algorithm adapts speculative decoding, an acceleration technique for autoregressive models such as large language models (LLMs), to the setting of diffusion models. Tra- ditionally 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 specu- lative decoding to diffusion models seems challenging for
Equaal contribution 'Computer Science Department, Stanford University, Californa, USA. Correspondence to: Hengyuan Hu <hengyuan. @hu @hhu@gmil.ccmm,, Aniket Das <aniketd@ stanford.edus.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
TWO reasons: first, the space is continuous; and second, draft diffusion model is likely to follow very different tra- jectories from the main diffusion model, unlike two LLMs which can plausibly predict a few similar tokens at 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 sym- metries. In technical terms, we show that after a syntactic time/scale change, the increments y++dr Yt of a denois- ing trajectory (Y))) form an exchangeable sequence of random variables- - in other words, their distribution re- mains 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 prove that ASD is an error- free parallelization algorithm, whose output is identically distributed as sequential samples from the DDPM. Further- more, under a minimal second-moment assumption, we prove that ASD makes at most ((1//) parallel calls to the model on d-dimensional distributions, as compared to ((d) 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 and has a theoretically guar- anteed speedup without any restrictive assumptions on the score function such as Lipschitz continuity.
Theoretical Guarantees:
We complement our theoretical contributions with extensive empirical evaluations on diffu- sion models for image generation and robot control tasks. ASD leads to 1.8-4x speedup in wall-clock time without any loss in quality.
Empirical Evaluation:
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 the sequences of tokens in the underlying distribution are cermutation-invaiian 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 xe O(d%s) speedup.
1.1. Notation
We analyze diffusion models defined on Euclidean spaces Rd, We use x, y to represent vectors and M to represent matrices. I is the identity matrix. For a random variable z, use Law(z) to denote its distribution. For random
variables x and y. we use = y to denote Law(x) Law(y). For any measure J., Cov[μi denotes its covariance. We use TV (V,..) and KL (-I1-) to denote the Total Variation distance and KL divergence. B, and We denote standard Brownian motions on Bdd unless stated otherwise. We use the O2 θ notation to suppress dependence on numerical and problem specific constants and O θ to suppress logarithmic factors. S. 2 and x denote S, 2 and = modulo universal constants.
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 fundamental hidden ex- changeability property for the trajectories of DDPM. In particular, we show that, after an appropriate transforma- tion, the increments of the DDPM process are exchangeable, i.e., their joint law is permutation-invarian This insight enables us to view DDPMs through the lens of any-order au- toregressive models (Shih et al., 2022), potentially allowing the adaptation of performance optimization techniques pre- viously limited to traditional autoregressive architectures.
2. Related Work
Several prior works, notably Shih et al. (2024) and Pokle et al. (2022), have shown how to use parallelization to em- pirically accelerate sampling from diffusion models. These works use a fixed point iteration, also called the Picard itera- tion or the collocation method, to break the sequential nature of denoising steps in diffusion models. These methods use hcuristics to stop the fixed point iteration when approximate convergence is detected, and thus leave a small error in the samples, unlike our results. Later works of Gupta al. (2024); Chen et al. (2024) provided theoretical convergence guarantees for these parallelization techniques, but under the very restrictive assumption that the score functions of the underlying distribution and all of its evolutions under the forward process of DDPM satisfy L-Lipschitzness for a very small L. In particular, when the underlying distribution is not smooth, or even when L is small polynomial of the dimension d, the guarantees become vacuous.
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 par- allel step to verify these predictions via rejection sampling. Our algorithm extends the Speculative Decoding (Leviathan et al., 2023) paradigm, widely used for L.M inference, to the diffusion model setting. Unlike traditional speculative decoding, our algorithm eschews an auxiliary draft model and instcad leverages the hidden exchangcability property to make the original DDPM speculate about itself. Hence, we call our algorithm Autospeculative Decoding (ASD) and show that it performs frror-free DDPM inference with mas- sive parallelization.
2

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
The work of Benton et al. (2023) provides the best-known theoretical analysis for the runtime of diffusion models in the sequential setting, namely (dd denoising steps for d- dimensional distributions. Without restrictive assumptions on the underlying distribution, such as Lipschitzness of scores, this (d) guarantee remained the best-known theo- retical result even in the parallel setting. Our work provides a parallel speedup under the minimal assumption of bound- edness of second moments, essentially the same assumption as in the work of Benton et al. (2023).
Variance Exploding SDE (VE-SDE) which sets h(t) 0. Under mild conditions, M Law(x;") converges tractable distribution which is easy to sample from. For instance, the choice u(t) = 2 and h(t) = -1 corresponds to the Ornstein Uhlenbeck (OU) SDE, which converges to a standard Guassian at an exponential rate (Bakry et al., 2014), and hence, satisfies Jrt R (V(0 I).
The reverse process, i... the denoising process x WT- is governed by the following SDE
dx = ftt, dt + Vu(T - dW,
Our work adapts speculative decoding (Leviathan et al., 2023; Chen et al., 2023), a parallelization technique widely used for LLMs and autoregressive models, to the setting of diffusion models. In the special setting of any-order autoregressive models (Shih et al., 2022), which excludes most LLMs, Anari et al. (2024a) provided the first the- oretically guaranteed speedup for speculative decoding. This, combined with our insight on the exchangeability of diffusion models, was the main source of inspiration for our work. Anari et al. (2024a) showed a specdup of Od'a /poly log(4)) for generating a sequence of d tokens, if the token space is of size q. We note that, while our proof adopts many elements from the work of Anari al. (2024a), there are significant challenges that we overcome: first, diffusion models live in a continuous space, roughly speaking this corresponds to g = co, for which the speedup guarantees of Anari et al. (2024a) become meaningless; and second, in diffusion models, even the sequential sampling process is discretization of a Stochastic Differential Equa- tion (SDE), and the error resulting from the discretization makes the analysis particularly challenging.
= - t)x + w(T V In HT (x
(2)
The working principle behind DDPMs is as follows: Since PT easy to approximately sample from (e.g pr R (0 I) for the OU DDPM), access to an (approximate) oracle for the score function V (x gives us genera- tive model for μ which involves sampling yo (where v R (TT) and then following the dynamics of (2). Algo- rithmically, this is implemented via the following Euler discretization:
Yi+1 = y; + 7:f((t)))) + 04416+41 Ei+1 ~ ~N(,
(3)
Where to S t1 S ... tk- are discretization points, 7) f+41 t is the step-size and 0++1 = / Vng(TT - t2).
3.1. Hidden Exchangeability of DDPMs
We now introduce Stochastic Localization (SL), an analytic tool developed by Eldan (2013), which has led to several breakthroughs in probability and theoretical computer sci- ence (Chen, 2021; EI Alaoui et al., 2022; Benton et al., 2023; Anari et al., 2024b). Given a target distribution μ on RR,, SL is defined by the following process yr:
The concurrent and independent work of De Bortoli et al. (2025), which came to our notice post-submission, also proposes the idea of parallelizing diffusion models via spec- ulative decoding. In particular, their idea of a Frozen Target Draft Model corresponds to Autospeculative Decoding. To the best of our understanding, De Bortoli et al. (2025) does not establish any parallel speedup guarantees for their algo- rithm, and their algorithm design is not based on the hidden exchangeability property.
y; m(,...) d yo 2o=0 0 m(t y) = -Ex (0. [x 1tx" + Vig yy y]
(4)
It is known that Law(s:/11) = μ (O.,It) and in particular as t -> 0o, we have Law(s:/:) + f (EI Alaoui & Monta- nari, 2022). To this end, stochastic localization resembles the reverse process in DDPMs as it can also function as generative model for μ given oracle access to m(!, y). This similarity was demystified by Montanari (2023), who proved that the OU DDPM is equivalent to the SL process. In Appendix B, we extend their result to show that arbitrary DDPMs are equivalent reparametrizations of Stochastic Lo- calization. In particular, we prove the following
3. Exchangeability in Diffusion Models
We first present a brief introduction to DDPMs and refer the readers to Song et al. (2021b); Chen et al. (2022) for broader discussion. For an unknown target distribution y Rd, we consider the following forward or noising process x, for time 1 E [0, T.
Theorem 1 (Equivalence of DDPM and SL), Letx denote the DDPM reverse process defined in (2) and let y: denote the SL process defined in (4). Then, there exist continuous invertible functions 7(t), ((t) that are uniquely determined by hi(t) and u(t) such that y a 7(1)x
dx.² = h())xx dt + vu(t)dW,, xo ~
(1)
where h((t), ut) are arbitrary continuous functions with
ut()= > 0. Notable special cases include the Variance Pre-
serving SDE (VP-SDE) which sets h(t)= = (u() and the
3

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
The key insight behind our algorithm comes from the fol- lowing time-invariance property of SL. We present proof of this result and a detailed discussion on the properties of SL in Appendix B.
one time-step in the SL formulation and then mapping it back to the DDPM formalism.
At any iteration i, the conditional distribution of the next iterate 9(y(+1lys). which we call the target distribution at step i, is of the following form:
Theorem 2 (Exchangeability in SL increments). Let Yt denote the SL process defined above. Consider any i S t2 S ... S. Im and let Tl. li+1 - t.. Then, the increments of the SL. process satisfies the following -nvvarraee property for any I E 1
((v++ll))) - Ny o;)
y.) = y: + mg((t.
(6)
Law((ye.+.. - yt))k(m--1)) = Law( (Yte Ste(s) (t(m))))(m))))
We refer to b(n), y:) as the targel mean al step i. Computing involves calling an (approximate) oracle for g. typically im- plemented via a neural network. Oracle calls to g. which we refer to as model calls, represent the primary computational bottleneck to sampling from equation Eq. (5). Note that for the SL process, g(-) is the same the mean-predicting function m (-) from Eq. (4).
In particular, if the time increments Th are all equal, then the increments A, yt..1 Yt; are exchangeable, i.e., Law((A))e((m-1) Law( (A)(((A()))))) (4)mmmmm)))))) V π E Sm-1
Since DDPMs and SL are equivalent reparametrizations of each other, we refer to Theorem 2 as the hidden exchange- ability property of DDPMs. In essence, Theorem 2 allows us use the DDPM increments at any given timestep proposal distribution for sampling the increments of future timesteps. As we shall demonstrate, this proposal and its subsequent verification can each be performed in parallel, leading to a highly efficient inference algorithm.
To leverage the hidden exchangeability property of DDPMs, our algorithm does the following: At any given step o, it tries to predict or speculate the target mean of the future timesteps by sampling from proposal distribution p. de- fined as follows. The proposal distribution is explicitly designed such that speculating the mean of future timesteps requires only one call to (i.e., one model call).
Note that, assuming a fine discretization, calls to the fune- tion m(.), equivalent to the trained model in DDPMs, pre- cisely allow to find the conditional distributions of the increments: Law( A; Ae.). So in way, one can view dif- fusion models as autoregressive models for the increments, with the major caveat that the token space here, IRd, is infi- nite. Theorem 2 shows that Law(A, (A, Ax4)) is the same for
p ((r441)22al))) = II P(y)+1lye..a)
12a
plyerlys, = -N b(nk
b(T,. y, ng)ta.y))
all j 2 i. So in particular at any point in the denoising pro- cess we can produce the marginal distribution of all future increments - it is the same as the immediately next incre- ment. Independent samples from these marginals form the proposal/speculation in our algorithm, as was done by Anari et al. (2024a) for any-order autoregressive models.
We call 6(7, yo) the proposal mean for step i at step and note that it requires only one call to g. In fact, it can even be computed in Ó(1) parallel time via prefix sums.
Equipped with the above definitions, we present Autospec- ulative Decoding in Algorithm 1. The algorithm, which resembles Speculative Decoding (Leviathan et al., 2023; Chen et al., 2024) has three key steps: 1) Sampling from the proposal distribution via one model call, 2) Speculating the means of the future target distributions via the proposal samples, 3) Verifying the accuracy of the speculations via rejection sampling and resampling at the first disagreement. The verification procedure, stated in Algorithm 2 uses Gaus- sian Rejection Sampler, Algorithm 3, to simultaneously sample from the conditional target distribution and check if the proposal agrees with the target. Algorithm 3 is mo- tivated by the reflection coupling technique of Bou-Rabee et al. (2020) and runs in ((1) time by leveraging the fact that the proposal and target are Gaussians with the same variance.
4. Autospeculative Decoding
In this section, we describe AutoSpeculative Decoding (ASD), our main algorithmic contribution. We consider the general problem of sampling from Fuler discretizations of SDEs of the following form:
y y; + y.)(t. + E Eep1 I..
(5)
where to S ... S ts denotes sequence of time-steps and 17: f++1 77s denotes the step-size. We note that it this includes the Fuler discretization of SL. as special case. Although typical discretizations of the DDPM don't 't directly fit into equation (5), this can be easily remedied by first translating the DDPM iterate to an SL iterate via the reparametrization discussed in Section 3, incrementing by
Remark 3. Although the speculated means for the DDPM process can be derived by following the recipe described before for SL and using the equivalence of SL and DDPM, the end result has an intuitive form. One can rewrite the
4

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Algorithm 1: Autospeculative Decoding (ASD)
Algorithm 2: Verifier
Input: Steps K, Step-sizes (N)) Variances
Input: Uniform Random Seeds (uo+15.... Ub).
(oε)) Initial yo- Speculation length sample (u), ux) ) ~V (n, )
Speculated Means (ma+1,.... mng) Target
Means (Mo+1....: mp), Variance Schedule
sample (GI,...,Ek) 1..d I)
(o (0+11...,,
a++1 for = a 1..... b in parallel
a 4-0
while K do
// GRS defines separately in Algorithm
Ya Ya. t min(K, +8)
// compute proposal means and proposal samples
(z b,) + GRS( E,. m, m; 0,)
3
Va + g(ta:
4
if b = True and i then
for i == a...., ., do
5
jti
m4+1 + yi %.V.
return [Ze+1,.... [b
81+1 + m;41 + +0+++++1
// speculate target means in parallel
Algorithm 3: Gaussian Rejection Sampler (GRS)
10
for a........ b- parallel
Input: ~ Uniform( 1)). & (O0,, I), Proposal mean m Target mean m, Variance a²
L m1+1 y; y4)
=
// verify speculations via rejection sampling
1 V + m m
b - 1 S min (1, NiE+o N (v1o.))
] N(E00,1
[<))acisb.]]++ Verifier((u;, m, m))acis))
if b True then
// advance until first rejection j < then
x + m + o
13
5 else
y; + 24 Vi E [a + 1,]+1]
14
x t m + o ( 2v (v.{)
15
x+j+1
6
Tv]
16
else
7 return (x,
17
y: - 2 E [a 1,1]
18
a j
19 return (Yo.... yK)
5. Theoretical Guarantees
In this section, we present our theoretical guarantees for Al- gorithm 1. Our first result, which is proved Appendix C.2, guarantees that ASD is an error-free parallelization method, i.e. it always samples exactly from the target distribution.
DDPM process (3) by expanding out f to get the form
Theorem 4 (Correctness of Algorithm 1). Algorithm I ter- minates in at most K steps and its outputs are always dis- tributed exactly according to the target distribution of the stochastic process (5).
Y++1 a,y; E(x, yıl + ViS+1
for some coefficients 0s; 3i. In many implementations of DDPM, the model is trained to output this EE[x,* | y:] directly instead of At step to speculate the means of future steps i, we simply need to plugin E E'x,' yal for E|x," y:] in the above formula.
We now analyze the parallel runtime of Algorithm for the Euler discretization of the SL process, and prove the follow- ing bound on the adaptive complexity, i.c., the number of parallel model calls, in Appendix C.3. While specific to the SL process, our result implies a similar guar- antee for DDPMs due to its equivalence to SI., as discussed in Section 3.1
proof is
Parallelization in Algorithm 1 In each iteration, ASD makes one model call in line to compute the proposal means and samples, and one parallel round of model calls in line 11 to speculate the target means. Beyond this, the remaining internal computation of ASD is also highly par- allelizable. In particular, each for loop in Algorithm and Algorithm is parallelizable and Algorithm takes O(1) time.
Theorem 5 (Adaptive Complexity of Algorithm 1). Sup- pose the data distribution satisfies Tr(Cov[μ)) < Bd and the step-sizes of the DDPM satisfy S 17. Then, for 0 x (K/3nd) Algorithm makes at most OKK4/ (Bdn)))))))) parallel calls to the DDPM in expectation. In fact, for any 8 E (0, 1), the number of parallel calls the DDPM
5

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Speedup on Latent Diffusion Model
Algorithmic Wall-clock
stpo
stop +
step
atep
1.81
1.87
1.89
1.90
Figure 1: A depiction of AutoSpeculative Decoding. Spec- ulated Gaussians with proposal means ri, are shown in dashed and Gaussians with target means m, are shown in solid. Green and orange points are proposed samples y;-
1.51
1.77
1.82
1.79
Speedup
1.51
The verifier accepts the first four proposals, rejects the fifth, and replaces the fifth proposed sample with its reflection. Proposed samples for steps beyond the fifth are ignored.
6
8
inf
bounded by (BK4)(B (og(4)/)) with probability at least 1 8.
Speculation Length (Number of Parallel GPUs)
O(K))) Parallel Speedup: accordance with prior works analyzing DDPMs, nd = O(1) usually required to ensure convergence to the target distribution (Chen al., 2022; Benton et al., 2023). Moreover, 3 is typically O(1). Under this setting, the number of parallel DDPM calls made by Algorithm is O (/*))) which represents O k/)s parallel speedup over the vanilla sequential DDPM.
Figure 2: Specdup of ASD over DDPM StableDiffusion- v2 with different speculation length 0. The algorithmic speedup measures the reduction in the number of calls to the noise prediction network while wall-clock speedup mea- sures the reduction in wall-clock time of the denoising pro- cess by running ASD.
The work of (Shih et al., 2024) proposed parallel algorithm for DDPMs based on Picard iterations but did not provide any theoretical guaran- tees. Along similar lines, the works of (Gupta et al., 2024; Chen et al., 2024) combined Picard iterations with the Ran- domized Midpoint Method to design a parallel algorithm for DDPMs with (ppoyyogg(d) (d)) parallel runtime, assuming bounded second moments and (11) uniform Lipschitzness of the score function, stringent assumption which is satis- fied for very restricted distribution families. As discussed before, these approaches are not error-free parallelization schemes due to the use of Picard iterations. On the contrary, ASD is a perfect sampler with guaranteed speedups even in the absence of any smoothness assumptions on the score function.
Comparison to Prior Works:
through multi-step speculation and parallel verification and 2) producing truthful samples of the underlying diffusion models. We consider diverse set of real-world applications where diffusion models are used, including image gener- ation with both latent- and pixel-space diffusion models (Rombach et al., 2022; Ho et al., 2020) and robot control with diffusion policies (Reuss et al., 2023; Chi et al., 2023). ASD offers 2-7x reduction in the number of sequential neural network predictions via speculation and our practi- cal implementation achieves 1.8-4x specdup measured in wall-clock time. We emphasize that our goal is not to claim any state-of-tt of-the-art acceleration results for diffusion models but to provide empirical evaluations complementary to our thcoretical contributions that enables fast, exact sampling without approximation.
From Adaptive Complexity Parallel Runtime: While Theorem upper bounds the number of parallel calls to the DDPM, note that the parallel runtime (i.e., time taken on PRAM) of the Algorithm satisfies the same guarantee modulo logarithmic factors. This is because the internal computation of Algorithm is easily parallelizable. For instance, the proposal and the target means can computed in ((1) parallel time via prefix sums, and the for loop in Algorithm 2 is also parallelizable.
To measure the speedup of ASD vanilla DDPM, consider two scenarios referred to algorithmic and wall- clock throughout the paper. For the algorithmic speedup, we divide the total number of denoising steps (e.g. 1000 in DDPM for image generation and 100 in diffusion policy for robot control) by the number of times ASD invokes the internal neural network to make predictions. This mainly helps us understand the rate at which ASD progresses. also corresponds the ideal speedup assuming perfect par- allelization where parallel predictions take the same amount of time as a single prediction, and ignoring the minor over- heads of other non-neural network computations such as speculation and rejection sampling. The wall-clock speedup measures the reduction in the wall-clock time of full denois-
6. Experiments
In the experiments, we empirically demonstrate the practi- cal benefits autospeculative decoding (ASD). We focus on two key properties of ASD: 1) accelerating inference
6

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
DDPM
ASD-2
ASD-4
ASD-6
ASD-8 32,3
ASD-00 32.1
algorithmic speedup ASD-oo. We measure the wall-clock speedup on a machine with 8 NVIDIA A40 GPUs. Our im- plementation achieves peak speedup of x with 0 = 6. In our specific implementation and hardware setup, the over- head of creating and transferring data for more speculation steps outweighs the marginal benefit of bigger 0.
32.1
32.2
32.0
32.2
Table 1: CLIP score (the higher the better) of images gen- erated from DDPM and ASD-0 with different speculation length The CLIP scores computed over 1000 captions from the COC02017 captions validation dataset. ASD does not affect the quality of generated images.
To verify that ASD produces truthful samples from the un- derlying distribution, we compute the CLIP score (Hessel et al., 2021) using 5000 images generated with languages from COC02017 captions validation dataset. Results in Ta- ble 1 show that the samples from ASD have the same quality as the ones generated by original DDPM. Fig. 3 shows the generated images from vanilla DDPM and ASD-c0 using the same prompts side by side.
DDPM 14.3
ASD-4 13.2
ASD-6
ASD-8
ASD-c0 14.3
13.2
13.2
Table 2: FID score (the lower the better) of images sampled from DDPM and ASD with different speculation length. The underlying diffusion model is trained on the LSUN Church dataset. Each score is computed with 5000 image samples. Samples from ASD have the same quality as the ones from non-speculative DDPM.
We also evaluate ASD on the LSUN Church model from Ho et al. (2020), which directly generates images of resolution 3 x 256 x 256. We use the same ASD implementation as in the latent diffusion case with up to 8 GPUs for parallel computation. Fig. 4 shows the algorithmic and wall-clock speedup of ASD on this model. ASD achieves higher speedup here than in the previous latent diffusion model, reducing the number of neural network prediction calls up to 3.1x. However, we also notice that the gap between the wall-clock and algorith- mic speedup is more significant in this case for two reasons. First, despite being a pixel space diffusion model, the com- putation cost per forward of this specific model is actually 50% cheaper than the latent model from the previous section. Second, the overhead of transferring inputs and predictions between processes is roughly 10x higher due to higher reso- lution and higher floating point precision. These two factors lead to a more prominent overhead and thus bigger gap be- tween wall-clock and algorithmic speedup than in previous experiment. A faster implementation on systems with faster inter-connection between GPUs may further close the gap. The FID scores in Table 2, computed over 5,000 samples for each method, confirm that ASD produces samples of the same quality as DDPM.
Pixel Diffusion Models:
ing loops, accounting for all extra overheads such as data transferring cost when parallelizing over multiple GPUs or the additional time for batched prediction.
6.1. Accelerating Diffusion for Image Generation
Latent Diffusion Models: We first evaluate ASD on image generation with latent diffusion models (LDM). Specifi- cally, we use open-sourced StableDiffusion-v2 (Rombach et al., 2022; Schuhmann et al., 2022) model from the dif- fusers (von Platen et al., 2022) library. To implement ASD with parallelization we first produce 0 proposals following lines 8-9 in Algorithm and then distribute the 0 model pre- diction steps in line 11 over 0 GPUs with multi-processing. Finally, we transfer the results back to the main process and run the acceptance and rejection sampling of lines 12-18. Similar to Shih et al. (2024), we choose to implement par- allel prediction through multiple GPUs instead of batching because the network is large enough that the time it takes to make a prediction grows linearly with the batch size even when the batch is small. In cases where the network is smaller, such in the robot control experiments discussed later, batching may still be valid solution to achieve high acceleration without incurring additional hardware cost.
6.2. Accelerating Diffusion for Robot Control
Diffusion models have become a popular method in learn- ing robot control policies from demonstrations (Chi et al., 2023; Reuss et al., 2023). It models the conditional distri- bution of an action sequence TT ((ars+)oo)) where o, is the observations from cameras attached to the robot. Concep- tually, the process can be viewed as generating a small 2D vector of size k where is the length of the action sequence and d is the action dimension. We consider three hard Robomimic (Mandlekar et al., 2021) simulation en- vironments namely Square, Transport and Tool Hang. We follow prior works to set k = 16 in all environments. The action dimension d = 7 in the single arm Square and Tool
Fig. 2 shows the algorithmic and wall-clock speedup of ASD relative to DDPM under 1000 denoising steps. We evaluate ASD with different speculation length 0 including infinity to understand the upper limit of ASD. As expected, longer speculation length in ASD leads to higher algorith- mic speedup as it allows for more parallelism. ASD-o0 achieves 1.9x x speedup, which corresponds to reducing the number of sequential predictions by nearly a factor of 2 when counting predictions that happen in parallel as 1. In practice, 6 or f is sufficient to achieve similar
7

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
(a) DDPM: a beautiful castle,
(b) DDPM: photo astro- naut riding a horse on mars
(c) ASD-oo: beautiful castle, matte painting
(d) ASD-c0 a photo an as- tronaut riding a horse on mars
matte painting
Figure Image generated by StahleDDiffusion->2 v2 with different sampling method, DDPM and ASD-00.
Env
DDPM
ASD--
ASD-12
ASD-16
ASD-20
ASD-24
ASD-o0
Square
88.67 + 0.27
93.00 + 1.70
91.67 + 1.66
93.00 = 0.47
93.00 + 0.47
90.00 + 1.89
90.33 + 0.27
Transport
89.00 + 1.25
90.00 + 1.25
91.33
1.52
90.00 = 0.47
91.00 + 0.00
90.00 + 0.82
90.00 + 1.25 73.67
Tool Hang
70.00 + 2.94
69.33 2.60
66.00
2.62
71.00 2.49
70.00 + 2.36
68.67 + 1.19
0.27
Table 3: Performance Robomimic Tasks. ASD with different speculation length achieves similar performance as the vanilla DDPM. The number in each cell is obtained by evaluating the diffusion policy on 100 random seeds (random initial configurations of the scene) and repeating 3 times. We report the mean + standard error of mean.
Hang tasks and d in the bi-manual Transport task.
same set 100 seeds (100 random initial configurations) and repeat three times to account for other randomness the evaluation process. ASD variants achieve similar success rate vanilla DDPM across all three environments.
The denoising neural network the diffusion policies is considerably more lightweight than the ones from image diffusion models in the previous section. Therefore, for a batching implementation for the parallel prediction step instead of parallelizing over multiple GPUs. We simply batch the proposal samples y, and call the network on the batch predict the noise using one GPU.
opt
7. Conclusion and Future Work
We introduce ASD, an error-free parallelization framework for DDPMs that achieves a guaranteed ((K3/s) parallel speedup under minimal assumptions and delivers 1.8-4x acceleration in practical domains. Our work establishes fundamental bridge between efficient inference techniques for LLMs and diffusion models, enabling coss-pollinnaton between these seemingly disjoint areas. Future directions in- clude extending our framework to discrete diffusion models like SEDD (Lou et al.) and developing theoretical guar- antees for speculative decoding in language models under realistic assumptions.
Fig. 5 shows the speedup results of ASD on diffusion poli- cies in all three tasks, relative to the vanilla DDPM that runs for 100 steps. Emperically, much higher acceptance rate for the speculated samples in these cases, leading to a 6-7x algorithmic speedup for ASD-20. Due to the high acceptance rate, it requires larger speculation length of 20 or 24 to match the efficiency of ASD-c0. The practical implementation achieves roughly 4x wall-clock speedup across the three tasks. The gap between algorithmic and wall-clock noticeably larger than the gap in image generation experiments because the overhead for speculation and rejection sampling is more prominent given the cheaper compute cost the neural network prediction. The extra cost of forwarding the network on batched input over single input also contributes the gap.
find that ASD has
We unroll the sampled actions in each environment verify that the quality of samples from ASD remains the same as the ones from original DDPM. Table 3 summarizes the results. In each environment, we evaluate the same diffusion policy with different sampling schemes over the
8

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Speedup on Pixel Diffusion Model
try of Markov diffasion operators, volume 103. Springer, 2014.
Algorithmic Wall-clock
Benton, J., De Bortoli, V., Doucet, A., and Deligiannidis, G. Linear convergence bounds for diffusion models via stochastic localization. arXiv preprint arXiv:2308. 036666 2023.
3.10
2.92
3
2.76
2.46
Speedup
2.51
2
2.13
2.30
Bou-Rabee N., Eberle, A., and Zimmer, R. Coupling and convergence for hamiltonian monte carlo. The Annals of applied probability, 1093)120 2020.
Chen, C., Borgeaud, S., Irving, G., Lespiau, J.-B., Sifre, L., and Jumper, J. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318, 2023.
6
8 inf
Speculation Length (Number of Parallel GPUs)
Chen, H., Ren, Y., Ying, L., and Rotskoff, G. M. Ac- celerating diffusion models with parallel sampling: In- ference at sub-linear time complexity. arXiv preprint 1rXiv:2405159980 2024.
DDPM using diffusion model from Ho et al. (2020). The model directly generates images with resolution x 256 x 256. ASD achieves up to 3.1x algorithmic speedup. However, compared to LDM, the overhead of data transfer between processes/GPUs is
Figure 4: Specdup of ASD
Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R. Sampling easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint arXiv:2209. //15, 2022.
bigger while the computation cost is cheaper, leading wider gap between wall-clock and algorithmic speedup.
Impact Statement
Chen, Y. An almost constant lower bound of the isoperi- metric coefficient in the kls conjecture. Geometric and Functional Analysis, 31:34-61, 2021.
This paper presents work whose goal is advance the field of Machine Learning. It focuses theoretical un- derstanding of diffusion models and accelerating inference of diffusion models. It shares the same potential societal consequences with diffusion models, which is a well es- tablished subject in ML. There are many potential socictal consequences of our work, none of which feel must be specifically highlighted here.
Chen, Y. and Eldan, R. Localization schemes: A frame- work for proving mixing bounds for markov chains. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 110-122 10--12. IEEE, 2022.
Chi, C., Feng, S., Du, Y., Xu, Z., Cousineau, E., Burch- fiel, B., and Song, S. Diffusion policy: Visuomotor policy learning via action diffusion. arXiv preprint arXiv:2303.04 040000...413.2220.. 2023.
Acknowledgment
This work supported by funds from NSF-2125511, NSF CCF-2045354 and the Stanford School of Engineering Fel- lowship.
De Bortoli, V., Galashov, A., Gretton, A., and Doucet, A. Accelerated diffusion models via speculative sampling. arXiv preprint PrXXi:2501.05370 2025.
Dhariwal, P. and Nichol, Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-880 8794, 2021.
References
Anari, N., Gao, R., and Rubinstein, A. Parallel sampling via counting. In Proceedings of the 56th Annual ACM Symposium Theory Computing, pp. 537-548, 2024a.
Alaoui, A. and Montanari, A. An cetommation-thhoretee view of stochastic localization. IEEE Transactions on Information Theory, (8(16):7444))))))) (B(11):7423-7225 2022.
Anari, N., Kochler, F., and Vuong, T.-D. Trickle-down in localization schemes and applications. In Proceedings of the 56th Annual ACM Symposium Theory of Comput- ing, pp. 1094-1105, 2024b.
El Alaoui, A., Montanari, A., and Sellke, M. Sampling from gibbs measure via algorithmic stochastic localization. In 2022 IEEE 63rd Annual Sym- posium on Foundations of Computer Science (FOCS), pp- 323-334. IEFE, 2022.
the
Bakry, D., Gentil, I., Ledoux, M., al. Analysis and geome-

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Square
Transport
Tool Hang
Algorithmic
Wall-clock
6.5
6.7
6.9
7.0
5.7
5.9
6.0
6.0
5.8
6.2
6.0
5.4
5.0
6.11
4.7
Speedhup
Specilup
Spoodup
3.44
3.7
3.7
3.5
3.7
3.9
3.5
3.9
4.1
inf
16
inf
Speculation Length
Speculation Length
Speculation Length
Figure 5: Speedup from ASD of diffusion policies in three Robomimic tasks. Unlike the image generation experiments where we parallelize across multiple GPUs, we only use GPU in these experiments and the parallel verification is achieved through batching.
Eldan, R. Thin shell implies spectral gap up to polylog via stochastic localization scheme. Geometric and Func- tional Analysis, 23(2):532- -36, 2013.
probabilistic models. arXiv preprint arXiv:2211.0109. 2022.
Mandlekar, A., Xu, D., Wong, J., Nasiriany, S., Wang, C., Kulkarni, R., Fei-Fei, L., Savarese, S., Zhu, Y., and Martin, R. What matters in learning from offline human demonstrations for robot manipulation. In arXiv preprint arXiv:2108.0320 2021.
Gupta, S., Cai, L., and Chen, S. Faster diffusion baffed sampling with randomized midpoints: Sequential and parallel. arXiv preprint arXiv:2406. 00924, 2024.
Hessel. J., Holtzman, A., Forbes, M., Bras, R. L.. and Choi,
Y. Clipscore: A reference-Fie free evaluation metric for im- age captioning. arXiv preprint arXiv:2104.08711. 2021.
Meng, C., Gao, R., Kingma, P., Ermon, S., Ho, J., and Salimans, T. On distillation of guided diffusion models. arXiv preprint arXiv: arXiv:2210.03142 2022.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in Neural Information Process- ing Systems, 33:6840-6855 2020.
Montanari, A. Sampling, diffusions, and stochastic localiza- tion. arXiv preprint arXiv:2305.. 10690, 2023.
Kingma, D., Salimans, T., Poole, B., and Ho, J. Varia- tional diffusion models. Advances in neural information processing systems, 34:21696-21707, 2021.
Nichol, A., Dhariwal, P., Ramesh, A., Shyam, P., Mishkin, P., McGrew, B., Sutskever, I., and Chen, M. Glide: Towards photorealistic image generation and editing with text-guided diffusion models. arXiv preprint arXiv:21122 10741, 2021.
Le Gall, J.-F. Brownian motion, martingales, and stochastic calculus. Springer, 2016
Oksendal, B. Stochastic differential equations: an intro- duction with applications. Springer Science & Business Media, 2013.
Leviathan, Y., Kalman, M., and Matias, Y. Fast inference from transformers via speculative decoding. In Inter- national Conference on Machine Learning, pp. 19274- 19286. PMLR, 2023.
Pokle, A., Geng, Z., and Kolter, J. Z. Deep equilibrium approaches diffusion models. Advances in Neural Information Processing Systems, 35:37975-37999 2022,
Lou, A., Meng, C., and Ermon, S. Discrete diffusion mod- cling by estimating the ratios the data distribution. In Forty-first International Conference on Machine Learn- ing.
Reuss, M., Li, M., Jia, X., and Lioutikov, R. Goal con- ditioned imitation learning using score-based diffusion policies. In Robotics: Science and Systems, 2023.
Lu, C. and Song, Y. Simplifying, stabilizing and seal- ing continuous-time consistency models. arXiv preprint arXiv:2410.11081, 2024.
Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp- 10684-10695, 2022.
Lu, C., Zhou, Y., Bao, F., Chen, J., Li, C., and Zhu. J. Dpm- solver++: Fast solver for guided sampling of diffusion
10

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Schuhmann, C., Beaumont, R., Vencu, R., Gordon, C. W., Wightman, R., Cherti, M., Coombes, T., Katta, A., Mullis, C., Wortsman, M., Schramosski, P., Kundurthy, S. R., Crowson, K., Schmidt, L., Kaczmarczyk, R., and Jitsev, LAION-5b: An open large-scale dataset for train- ing next generation image-texi models. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022. URL https: //openreview. net/ forum?
Shih, A., Sadigh, D., and Ermon, S. Training and infer- ence on any-order autoregressive models the right way. Advances in Neural Information Processing Systems, 35: 2762-2775, 2022.
Shih, A., Belkhale, S., Ermon, S., Sadigh, D., and Anari, N. Parallel sampling of diffusion models. Advances in Neural Information Processing Systems, 36, 2024.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and
Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International Conference on Machine Learning, pp. 2256-2265. PMLR, 2015.
Song, J., Meng, C., and Ermon, S. Denoising diffusion im- plicit models. In 9th International Conference on Learn- ing Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021a.
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Er- mon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. In 9th Interna- tional Conference on Learning Representations, ICLR 2021, 2021b.
Song, Y., Dhariwal, P., Chen, M., and Sutskever, Consis- tency models. arXiv preprint arXiv:2303.01466 2023.
Van Handel, R. Probability in high dimension. Lecture Notes (Princeton University). 2(3):2-3, 2014.
von Platen, P., Patil, S., Lozhkov, A., Cuenca, P., Lambert, N., Rasul, K., Davaadorj, M., and Wolf, T. Diffusers:
State-of-the-an diffusion models. https: /tt///githe githbb. honn/huggingfafee warfeface/aae /di diffusers 2022.
Watson, D., Chan, W. Ho, J., and Norouzi. M. Learning fast samplers for diffusion models by differentiating through sample quality. In International Conference on Learning Representations, 2022.

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
A. Mathematical Preliminaries
In this section, we state some standard results from probability that we use Lemma (Pinsker's Inequality (Van Handel, 2014)). For any two distributions P and Q,
KL (PIIQ)
TV 3
Lemma 7 (Doob's Maximal Inequality (Le Gall, 2016)). Let Letx,, xi..... X. be an R& valued submartingale. Then for any
p >>>
E sup ly: yoll
E Illm yoll"]
:E|m]
p
Lemma 8 (Ito's Lemma (Oksendal, 2013)). Let f R x Rd - R be differentiable function and let be stochastic process governed by the following SDE:
dx, = a o
Then Yt f(t, xx) satisfies the following SDE:
dy: = (a.f(1,x)) x.) (V, x,), +
(V/()) dB,)
(VI(t,x),,
We also make use of the following result, which is direct corollary of Girsanov's theorem (Oksendal, 2013):
Lemma (Girsanov Bound for KL Divergence). For E [0,T], ler x, and y be two stochastic processes governed by the following SDEs:
dx, (x(x)) dt dB,
dy, (y dt - a dB,
Let plo.T) and QI0.T) denote the path measures and y in the time interval (0, T). Then,
KL (plo.T111Q KK (xollyo) + o² /-" E Ex (x(() by (xxee))))
We also use the following time transformation identity for SDEs, which follows directly from Theorem 8.5.7 of (Oksendal, 2013) Lemma 10 (Time Transformation for SDEs). Let X2 denote the solution of the following SDE:
x.) + dx, = b(t, b(t
and let r R20 Rzo be continuously differentiable non-decreasing function with r(0) 0. Then y. Xr(() satisfies the following SDE:
dy: = ()
B. Properties of Stochastic Localization
In this section, we state some additional properties of the Stochastic Localization (SL) process that we use our analysis, and also present a proof of Theorem 2 Appendix B.2. Let μ be a target measure on Rd whose covariance satisfies Tr(Cov[ul) < 3dd for some 3 2 0. Recall the SL process from Section defined as follows:
y. m(t,y.) dt dBi, No
m(t.y) Ex (o.)) x² tx" VtE =y
(8)
12

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
In addition, we define Pe, m, and En as follows:
# Lawx ~u (x' ly:)
(9)
m; = mean(14)
(10)
D = Cov[pe]
(11)
It is easy to see that (o j.. Our proof of the hidden exchangeability property makes of the following result, which is proved in El Alaoui & Montanari (2022); Montanari (2023)
Theorem 11 (Alternate Representation SL.. The stochastic localization process admits the following alternate represen- tation:
dy, x dt + dW,
where x* and W2 is a standard Brownian motion on Rdd.
Our analysis also uses the following result the evolution of m, and E, which is proved in (Eldan, 2013; Chen, 2021; Chen & Eldan, 2022)
Theorem 12 (Evolution Mean and Covariance Along SL). my and E, satisfies the following
dm; M, dW,
E [ EE
dt
where We is Brownian motion on Rd and the expectation is wrt the randomness of the loculization process
To illustrate an application of Theorem 12, we show how to control the error incurred due to Euler discretization of the SL process. An adaptation of this argument in (Benton al., 2023) was used to analyze the convergence of DDPMs.
Theorem 13 (Euler Discretization SL). Consider any sequence of times I t1 S ... S tK < co satisfying Th 1,+1 - 44 S 1/. Let y. = m(t, y+) di + dB, denote the St. process and let p9 denote its path measure [L1, lk)
Define the Euler discretization of the SL process as:
dy: = V1,4.y1)) dt + dB, , (i,4te [K -1]
and let denote its path measure [4,, [k]. Suppose the initial distribution μ has finite second moments and satisfies Covlu] 3I Then, the KL divergence between the path measures is bounded as KL (PV[) 2
ndd
Proof. By Lemma 9,
prx Egwpolllmm(S? - ())
KL (P'))P)) =
to
K-
1441
Pymps|/lmett m (y d!
K-1
EynPy |/ E. dw, 1"a dt
27
K-1
ds
2
where the third step uses Theorem 12 and the last step applies the Ito isometry. From Theorem 12, we note that dTr(E(E.))
dt
13

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
-E(T((,,) 3 3 O, which implies the following:
R-1
14-1
KL (PS1IPM)
B[Tr(E))]
ds
2
44
i=1
Tr(E[E+) - dt
2
2 (141-144 - TT){ Em--l)
Σ
hd
nd
$ $2
B[Tr(E,,)] - 2
where we use the fact that E[E,] is non-increasing function (in the PSD order).
Our adaptive complexity analysis of Algorithm relies on argument similar to the proof of the above theorem.
B.1. Equivalence between DDPM and SL
The following result by (Montanari, 2023) proves that the OU Process defined in Section 3 is equivalent to Stochastic Localization
Theorem 14 (Equivalence of OU Process and SL). Let Yt denote the SL process as defined above and let z, denote the OU process defined by the following SDE:
dz 22dt vddB.
Then, the following holds:
Y1 - te((()) Za(t)
where s(t) 1 In(1 + 4/1)
Equipped with the above result, we now present a proof of Theorem
below
B.1.1. PROOF OF THEOREM
Proof. Let x denote the DDPM forward process defined in equation (1), which satisfies the following SDE
dx;² h(()x²² de Vu(t)dW,,x, Xo P
Now, let z, denote the following OU process:
2, -z dt v2dB,, x
(12)
We now define the functions att) and r(f) as follows:
att) 2 in 1+ L a(F)exp(-2 I' h(s) dr)
(()) = exp(a(t) + 1/" h(T)
Since u(t) 2 0, it is easy to check that a(t) is a non-decreasing function with a<0) = 0. Furthermore, r(t) > 0 with r(0) = 1. We shall now prove that x," = = Note that our claim holds for f = since x Zo -(0)
To prove this claim for > 0, we show that "," and r(t)za(t) follow the same SDE. Since a(t) satisfies the conditions of Lemma 10, we conclude the following:
d(za(t)) -a' -a((1)a((() dt 22a(() dB.
14

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Using the above and Ito's Lemma, obtain the following:
d(r(()za())) (r( af ((())())) Ba(t) de +r()++2(22000))
(() a'(1) r(1)aatte) di + (()(())) dB.
r(t)
a a' h(t) and 2a (t)r(t)))) u(t), i... Taking derivatives of In rt)) and (2a(t), it is easy to that the r'0 x(t)
d(r(()za())) ((())(())z())) dt + Vu(()dB
From Eq. (12) and the above, we note that x and ((t) satisfy the same SDE. Since xo" = =r(0)za(0)) we conclude that x," = r()))a(()) Then, by definition of the reverse process,
(1) xT-a 1(1) 2, = r(a (t)) r(a-
From Theorem 14, we know that Yt teel0) 20(() where where s(t) = 1 IIn(1 + 1/s). Substituting this into the above identity gives us the following:
yt - (1)
(e)(
71) = r(a (s{()))
<(t) = T a (
B.2. Proof of Theorem
Proof. By Theorem 11, we know that the stochastic localization process satisfies:
y: = tx" + W
where x ~ and W, a standard Brownian motion on Rd. By the properties of Brownian increments, the following holds for any i [m - 1] and ı E Sm-1
Law((yr.tm - Vv. m1) =
N(nx", m.)
iE(m-1)
By marginalizing x*, we complete the proof of the first claim. The second claim directly follows by setting the time increments y); to be equal.
C. Theoretical Guarantees for Auto-Speculative Decoding
In this section, we present our theoretical guarantees for Auto-Speculative decoding. To begin with, we prove the correctness of the Gaussian Rejection Sampler in Algorithm 3. We note that this result implies that the Verifier in Algorithm 2 always outputs samples (Ze+1....,,4 2x) ~ q(-lysa) that are distributed according to the conditional target distribution.
C.1. Correctness Algorithm
Theorem 15. Let & I). Then, for any m, m E Rd and a > 0, GRS(u, E, m, m) outputs (x, b) such that x~ N(m, I) and [b(b False] TV
15

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Proof. Without loss of generality, we consider o and observe that
min 1, .i + I)
Pbb = True] =
min(N DI v(0, de
min(N(g)m. (E I)) de
= (V (,
which proves the second claim. Now, let g = x m and el ea be an orthonormal basis of IR with v ||v||e] Then,
w.p. min (1. N(s+vlo. (EEO..T)
++
g
(13)
(I 2e
w.p. max 0,,
-(s+vio.1)
((E
Then, the law of g satisfies the following:
Law(g)= = / (e+v(()) min (W v de
+ / i 6(-20cT)e max
max (a (I,V,, -N de
min (V(g v + 6(1-20e7) max (0,NN(E0,I) N'(E + vv0, de (14)
where 6x denotes the Dirac measure supported x. To bound the integral on the RHS, we note that the matrix == = 1- es
a reflection operator along the e axis, i.e., for any x E IRd and y = Mx. (y,e,) = - (x. eτ) and (y,e)) - (x, ex)) for any # 1. Hence, it follows that ||yl| = ||*|| and x My
/ Ome (g) max (0, - .NE + v)), de = max (0. - A + v/0.
(15)
Now, (MM I) (Ngg 0, I) since MMgl
|g||- Moreover, since M M
Mg + v|| Mgl ||v +2 2 v)
Ilgl 2 + ||v 2| 2 Mc1) ||v]
= gl 2 + ||v - 2 (g. e1) ||v|
g v|
where we use the fact that Me, = -e; and = ||v||e Hence, AMM + v/0,1) = A(g v/0,1). Substituting into equation (15), we have:
f (0c(()) max (0.WVEE0..I) .N(E v/00,) di max (0.N(g((, N v))
Substituting this into (14), we get
Law(g) = min v|0, v. V. max (0. -Vgg - v)).
0,
Since m +g. N (m, I) which completes the proof.
C.2. Proof of Theorem
In this section, we present our analysis of Autospeculation for the Stochastic Localization Process. We use a to denote the value the index a at the end of the th iteration in Algorithm 1.
16

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Lemma 16. .Yo.....aa aa) is distributed correctly according to the target distribution g(Yo,-.. .... ......--ee Furthermore, dg is strictly increasing sequence in t.
Proof. We prove this claim by induction. Clearly, the claim holds for = O. Now, suppose it holds for some t. By definition
of the proposal means and the target means in equations (7) and (6), ma +1 Then, by Theorem 15, Algorithm 2 does not reject the index + 1, thereby ensuring that 4++1 > + 1 as per lines 13-18 of Algorithm 1. Since the verifier's outputs are always distributed according to the conditional target distribution, Law(yacth>.... yaci .......,,aa. 1yo...yo.......8 The proof is completed by removing the conditioning on .......Ja. by applying the induction hypothesis.
Since Algorithm terminates when 2 K, Lemma 16 implies Theorem 4
C.3. Adaptive Complexity of Algorithm
In this section, we analyze the adaptive complexity of Algorithm for the SL process. Our proof combines arguments from Anari et al. (2024a) with careful analysis of speculations of the SL process motivated by the hidden exchangeability property. We first define the of (u1:k; EI:k) as the maximum possible value of a such that the parallel rejection sampler does not accept the 1th proposal. Formally
af (ui., {1.K) max fa [K] Verifier(Ua++1::e Sa+1:K, Mo+ I:K: Ma+1:) <i}
where m,, m, are defined as in Algorithm 1 (with b b= K). We use R to denote the round complexity (i.e. the number of iterations) taken by Algorithm 1. Since Algorithm 1 makes exactly two parallel model calls per iteration, bounding R is equivalent to bounding the adaptive complexity. We first prove a worst case bound on R as a function of oz Lemma 17. The following holds for any integer
U1.K
[0, 1]K and σI.K E R
K + lif [K] at (u1:k, {1:K) 2 0}1
R
Proof. Let & be denoted good iteration if ar d/-1 > 0 and bad iteration otherwise. Since the algorithm halts whenever 2 K, the number of good iterations is bounded by K
0 + 1. Since a is a monotonically increasing sequence by Lemma 16, any bad iteration satisfies ax (MI-k, {1:K) ) 2 a;-1 2 Os 0, i.e., 0 E {i E [K] at (uI:,, (1.) 2 - 0). Since - ag is a bijection, we conclude that the number of bad rounds is upper bounded by {i [K] az (ui,k; ( 2 0}
We now use the above Lemma and the innerinvariance properties of the SL process to prove an expectation bound on the round complexity, which establishes the first claim of Theorem 5
Theorem 18 (Expected Round Complexity of Algorithm 1). Under the assumptions and parameter settings of Theorem 5, Algorithm I run for the discretization of the SL process with 0 x (K/3nd) 1/a makes ((K3))(dd)) parallel model calls in expectation.
Proof. From Lemma 17, we note that
K
B|R] < 1+
+ Σ (Mnx, (u:) 2 i
(16)
Note that of (uI:k: f1:K) 2 i O implies that there exists some a E [i - 0, 1] such that the proposal for step i made at step a was rejected by the Verifier. Then, by Theorem 15,
K
(lak E 2 1- 5 Σ En.g
max -1ii-
TV
9
i2
S V K
max [c(i--0;-1]
TV (V(a(xilva)
(17)
$28
17

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
By our choice of the proposal and target distributions, p(y:)ye) and (Vy: Gaussians with the same variance. To this end, their TV distance is increasing concave function of the difference of their means. Also, note that for E (i 0, i 1] p(yilya) and (Y)) are Doob Martingales with respect to the filtration generated by (uj, (ig,Si)ssi we conclude via the Doob Maximal Inequality for p = 2
Eugg
max 0
TV ((llll) - [VV
(18)
We now bound the above quantity for each index i. To this end, let |= = i 0 and define the following stochastic processes associated with the proposal and target.
dyl+: m(41, (P) dt + d. (T) m(4, (T) dt + dB
Then, by the data processing inequality and equation (18), we obtain:
S E TV (py ) 27
E
max
(V
(19)
11
We now define the following auxiliary processes:
dy (P) m(t + +t,
(P) dt + dB
dy 1,tt m(4 + (. dt + d
(T)
Similarly, let (P and ()(1) denote their respective path measures for t E [0, m.] We observe that: 1. The differential increments of y:
(P) and y: (T) match that of the SL process modulo time-shift, 2. y (P) and y! are Euler discretizations of (P)) and (T) respectively. By Pinsker's and Cauchy Schwarz Inequality.
TV ( pamm) 21
pporr) 2 TV (pvrm) p) 2 + TV (ps )
E
TV
ps
+ KL (1x"" KL (18()1)sst))))
E
KL
(20)
To upper bound KL same steps the proof of Theorem 13:
(y)
||
py(())
we use the fact that (P) corresponds to the Euler discretization of (P) and follow the
(pst"1) (1p0(())) 27
E|KL
Blllm: m., 1
11
2A 24
E[Tr(E?)]ds dt
Tr(E/E,,1 - E(E,])
Tr(( B[E
(21)
By similar computation, we also have
E|KL (pS"") ||
) $ 77-0 Tr(E -[E
(22)
Using the fact that the increments (P)) and (T) are time-shifted versions of the SL process increments via Girsanov's
18

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
theorem and Theorem 12:
91
23
El] m
111
2/
[[Tr(>?]] ds dt
2A
Tr(E [ - E E| dt
2A 77--8
Th--TT((B[ - E Em
(23)
where we use the fact that E[E,] is non-increasing in the PSD order.
Substituting equations (20) (21), (22) and (23) into equation (19) and summing over i, we obtain the following:
E
max
TV TV(((rrlya))
M e Tr(E sJ E[E,, .n))) Σ
The Tr Tr((Ee,
E sI)
AE -0,1-11
$20
Th- Tr [E o E[
2 Tr([(((())) + OhTr(B(Eo)) & 0n3d
(24)
Substituting (24) in (17) and (16), conclude the following:
K
py po)
E
TV
0
$28
$ VK
K
E
TV Py(()) p 2
8
128
K
K0n3d
0 (K/naa))) V/, we obtain the desired expected round complexity.
We now boost the expected round complexity guarantee of Theorem Theorem 18 into a high probability guarantee, thereby proving the second claim of Theorem 5. The proof adapts the arguments of (Anari et al., 2024a), Theorem 28.
Theorem 19 (High Probability Bound for Round Complexity). Let å E (0, 1) be arbitrary. Consider Algorithm for the SL process run under the assumptions and parameter settings of Theorem 18. Then, with probability at least 8, Algorithm I makes most O(K3/a(33)))) (3dh) In(1s)) ((()s) parallel model calls.
Proof. By Theorem 18 and Markov's s inequality, there exists constant M such that P|R > (K33() s 1/2. We shall now prove via induction that the following holds for any integer e 2 1 and K >
P(R cMK (n 43 2
The case 1 holds via Markov's inequality and the case K is trivially true.
Now, suppose the statement holds for any K K₁ and consider instance with K = K2. For i [K 1] let E, be the event that Algorithm 1 doesn't it terminate and has = i after running for (nBd)) rounds. Clearly, = P[EE] < 1/2. Moreover, by Lemma 16, running the algorithm for M MK3 (n ensures a 2 (ndd)
Hence, [ = 0 and for any > 1:
IP(R > cMK (1)
Σ P(R> eMK (n P(F.)
12K-1
$ 1/2
max PRR (n [.]]
(25)
19

---

Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
Note that for any E [K- 11. Eg is measurable w.r. the filtration generated by (ug, S i.e., whether E, occurs determined exactly by these random variables variables, and thus E, is independent of (ut Er)ss Furthermore, if E occurs Algorithm 1 fixes the random variables (uj. G))ssi and moves forward with a = i, Therefore, the law of the remaining iterations is equal to that of a fresh rum of the algorithm on the iterates (yi)ss conditioned on the iterates (yy)sęı being fixed to their current values (as determined by the (u,, Ej)zg() By our induction hypothesis for and the definition Eg, the number of remaining rounds (upon conditioning on E2) exceeds (c -
with probability at most 2-++1 i.e. P(R cM ((/((())3))) 1/s E, S 2 2-++1, Substituting this into equation (25) proves our claim by induction. The desired O (n3)) Va In(1/)) bound on the round complexity obtained by setting In(1/)
20


Reviews:
[{"review_id": "gTjrKhHt3H", "reviewer": "Reviewer_Ed9d", "summary": "This paper reveals the hidden exchangeability inherent in Denoising Diffusion Probabilistic Models (DDPMs) and proposes Autospeculative Decoding (ASD), a novel algorithm that leverages the model itself to generate multi-step speculations and verifies them in parallel. By eliminating auxiliary draft models, ASD achieves a theoretically guaranteed O(K^{1/3}) acceleration over sequential DDPM sampling while preserving zero quality loss. Empirical evaluations demonstrate 1.8-4x practical speedups across image generation (e.g., Stable Diffusion) and robotic control tasks, with CLIP/FID scores and policy success rates on par with original DDPMs.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\bE}{\\mathbb{E}}$\nThank you for your review and for taking the time to engage with our work. We hope to address your concerns below:\n\n## Analysis of Discrete Steps\n\nWe highlight that **all our theoretical guarantees for ASD directly consider the discrete-time regime**. To this end, our proof of Theorem 2 on the correctness of ASD *does not* make any use of the continuous time SL process, and relies only on the properties of the Gaussian Rejection Sampler. Our proof of Theorem 3, which analyzes the discrete-time parallel complexity of ASD, uses the SL process *only as an analytic tool* to interpolate between the ASD increments. Such interpolation arguments are ubiquitous in the sampling literature, particularly in the analysis of diffusion models [1,2] as well as gradient-based sampling algorithms like Langevin Monte Carlo. [3,4]\n\n## Impact of Discretization on Exchangeability\n\nWhile our discussion on hidden exchangeability in Section 3.1 focuses on the continuous case for ease of exposition (to provide intuition behind why the arguments of Anari et. al.'24 can be extended to diffusion models), **the impact of discretization on hidden exchangeability is appropriately quantified in the proof of Theorem 3**. In particular, the proof of Theorem 3 establishes that, **as long as the step-size is not too large, ASD increments aproximately satisfy the hidden exchangeability property**. This holds because the discrete trajectory of ASD is statistically indistinguishable from that of the continuous SL process (which exactly satisfies hidden exchangeability as per Theorem 1). We rigorously quantify this in the proof of Theorem 16 in Equations 20 and 21 by proving that the TV distance between ASD and the continuous process is $O(\\sqrt{\\eta \\beta d})$. Hence, the two can be made statistically indistinguishable by choosing $\\eta \\asymp \\tfrac{1}{\\beta d}$.  We shall update our draft to highlight this point in the main text. \n\n## High Dimensional Tasks\n\nOur experiments on Pixel Diffusion demonstrate the effectiveness of ASD on a 196,608 dimensional task. Evaluations on more complex modalities such as video is an interesting avenue of future work which we are unable to pursue at present due to resource constraints.\n\n## Unequal Step-Sizes\n\nWe respectfully disagree with the claim that the case of unequal step-sizes is not analyzed theoretically. We highlight that **Theorem 1 proves a general time invariance property** for the distribution of stochastic localization increments, **which holds even for unequal step-sizes $\\eta_i$**. We call this time invariance the hidden exchangeability property as it reduces to exchangeability of increments when the step-sizes are equal. However, the key result of Theorem 1 is agnostic to the choice of step-sizes. Consequently, **all our theoretical guarantees for ASD are directly applicable to unequal step-sizes.**\n\n## Assumption on $\\beta$\n\nWe first note that $\\beta = O(1)$ is a standard assumption in the theory of diffusion models [1,2]. Secondly, for arbitrary $\\beta$, the canonical choice of step-size is $\\eta \\asymp \\tfrac{1}{\\beta d}$ (e.g. [1] uses $\\eta \\asymp \\tfrac{1}{M_2}$ where $M_2 = \\beta d$, see also [2, Appendix C]). Under this setting, the parallel runtime of ASD as per Theorem 4 is $O(K^{2/3})$. Hence, **the $K^{1/3}$ parallel speedup guarantee continues to hold.**\n\n## References\n\nThank you for the helpful references, which we weren't aware of at the time of writing. We shall update our draft to include them. \n\n## Löwner-Heinz Theorem \n\n$\\bE[\\Sigma_t]$ being a decreasing function in the Löwner order directly follows from the facts that: 1. $\\tfrac{d{\\bE[\\Sigma_t]}}{dt} = -\\bE[\\Sigma_t^2]$ and, 2. $\\bE[\\Sigma_t^2]$ is a PSD matrix. To our understanding, the Löwner-Heinz theorem (which deals with the operator monotonicity of $t^p$ for $p \\in [-1,1]$) is not relevant here. Please let us know if we have made a mistake. \n\n## Comparison to Shih et. al. \n\nPlease refer to our response to Reviewer FuEw for a detailed discussion on why our results and that of Shih. et. al. cannot be compared on equal footing (and why our work and Shih. et. al. represent orthogonal axes of improvement for fast DDPM inference)\n\n## Quantifying the Acceptance Rates\n\nWe highlight that the acceptance rate is quantitatively analyzed in the proof of Theorem 4. In particular,  the total probability of rejection is upper bounded by $O(\\sqrt{K \\theta \\eta \\beta d})$ \n\n\n### Refs\n\n1. Chen et. al. : Sampling is as easy as learning the score\n2. Benton et. al. : Convergence Bounds for DDPMs via Stochastic Localization\n3. Vempala & Wibisono : Rapid Convergence of the Unadjusted Langevin Algorithm\n4. Balasubramanian et. al. : Towards a Theory of Non-Log Concave Sampling\n5. Anari et. al. : Parallel Sampling via Counting", "claims_and_evidence": "1.Practical implementations of DDPM typically use discrete steps, whereas the theoretical analysis is based on continuous SDEs. although Theorem 11 analyses the discretisation error, its impact on exchangeability (e.g., whether large step sizes destroy exchangeability) is not explicitly quantified.\n2. The effectiveness of ASD relies on exchangeability, and experimental results showing lossless acceleration indirectly support the existence of this property. However, targeted experiments (e.g., distribution consistency tests after replacement increments) were not designed to directly validate exchangeability. Theoretical derivation is rigorous but discretisation effects need further discussion, and experiments indirectly support but lack direct validation.\n3. Non-destructiveness not validated in higher dimensional tasks (e.g. video generation) or complex distributions (multimodal). Theoretical proof is sufficient, experimental support is valid but more evidence is needed for scalability.\n4. Theorem 4 relies on the covariance decay of the SL process (Theorem 10) and rejection sampling probability bounds, under the assumptions that Tr(Cov[μ])≤βd and step sizes ηk​≤η are reasonable. The derivation adapts the autoregressive framework of Anari et al. (2024a) to continuous spaces. Whether the practical value of β is dimension-independent. If β scales as β=O(1) with respect to d, the theoretical speedup holds. However, if β=O(d), the theoretical guarantees may degrade, weakening the claimed acceleration ratio.", "methods_and_evaluation_criteria": "The self-speculative decoding (ASD) method proposed in the paper addresses the core problem of slow inference of diffusion models, proves the exchangeability of denoised trajectory increments by revealing the equivalence between diffusion models and stochastic localisation (SL), provides a theoretical basis for parallelisation, and is theoretically innovative. With comprehensive assessment criteria: the experimental design of the paper covers multiple dimensions, and the assessment criteria are reasonable and persuasive. The paper has some room for improvement in comparison experiments, but the core validation is still persuasive.", "theoretical_claims": "1.The exchangeability strictly requires equal step sizes ηi​. While the authors mention this condition in Theorem 1, they do not explicitly quantify how unequal ηi​ affects practical ASD performance (tested empirically but not theoretically).\n2. In Theorem 11, The proof states E[Σt] is non-increasing in PSD order but does not explicitly cite the Löwner-Heinz theorem, which is required for this claim.", "experimental_designs_or_analyses": "In conclusion, the experimental design of the paper is generally reasonable, but there may be room for improvement in statistical significance and detailed description of the experimental setup.\n1. The advantages of ASD in terms of error and acceleration ratio compared to Picard's iterative method of Shih et al. (2024) need to be quantitatively compared (e.g., FID vs. speed profiles).\n2. ASD's computational cost of rejection sampling (e.g., rejection rate of Algorithm 3) is not quantitatively analysed. High rejection rates may weaken the actual acceleration, and acceptance rate statistics under different tasks need to be added.", "relation_to_broader_scientific_literature": "1.While prior diffusion acceleration methods (e.g., DDIM, DPM-Solver) trade quality for speed via deterministic approximations or reduced steps, ASD achieves lossless acceleration through parallelism, akin to Shih et al. (2024)’s parallel sampling but with theoretical guarantees. Unlike recent parallel DDPM methods (Gupta et al., 2024; Chen et al., 2024) that require restrictive Lipschitz assumptions, ASD operates under minimal second-moment conditions, broadening applicability.\n2.The work adapts speculative decoding (Leviathan et al., 2023; Chen et al., 2023), originally designed for discrete autoregressive models (e.g., LLMs), to continuous-state diffusion models. Crucially, it eliminates the need for a draft model—a limitation in prior speculative methods—by exploiting the exchangeability property. This aligns with Anari et al. (2024a)’s framework for any-order autoregressive models but addresses the unique challenges of infinite token spaces (i.e., continuous domains).", "essential_references_not_discussed": "The authors correctly cite speculative decoding on arbitrary order autoregressive models. However, a recent extension to continuous spaces is missing:\n1. Distilled Decoding 1: One-step Sampling of Image Auto-regressive Models with Flow Matching[J]. arXiv preprint arXiv:2412.17153, 2024.\n2. Accelerated Diffusion Models via Speculative Sampling[J]. arXiv preprint arXiv:2501.05370, 2025.", "other_strengths_and_weaknesses": "Strengths:\nThe discovery of hidden exchangeability via the DDPM-SL equivalence is novel, providing a fresh theoretical lens for diffusion models. Extending speculative decoding to continuous spaces without draft models is a significant conceptual leap.\nThe proposed ASD achieves lossless acceleration (1.8-4x wall-clock speedup) with rigorous guarantees, addressing a critical bottleneck in real-time applications like robotics.\nWeaknesses:\nThe comparative experiments are not comprehensive, and the theorems and explanations are not clear and complete enough. Refer to “Claims And Evidences”, “Theoretical Claims” and “Experimental Designs Or Analyses” sections.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1.Practical implementations of DDPM typically use discrete steps, whereas the theoretical analysis is based on continuous SDEs. although Theorem 11 analyses the discretisation error, its impact on exchangeability (e.g., whether large step sizes destroy exchangeability) is not explicitly quantified.\n2. The effectiveness of ASD relies on exchangeability, and experimental results showing lossless acceleration indirectly support the existence of this property. However, targeted experiments (e.g., distribution consistency tests after replacement increments) were not designed to directly validate exchangeability. Theoretical derivation is rigorous but discretisation effects need further discussion, and experiments indirectly support but lack direct validation.\n3. Non-destructiveness not validated in higher dimensional tasks (e.g. video generation) or complex distributions (multimodal). Theoretical proof is sufficient, experimental support is valid but more evidence is needed for scalability.\n4. Theorem 4 relies on the covariance decay of the SL process (Theorem 10) and rejection sampling probability bounds, under the assumptions that Tr(Cov[μ])≤βd and step sizes ηk​≤η are reasonable. The derivation adapts the autoregressive framework of Anari et al. (2024a) to continuous spaces. Whether the practical value of β is dimension-independent. If β scales as β=O(1) with respect to d, the theoretical speedup holds. However, if β=O(d), the theoretical guarantees may degrade, weakening the claimed acceleration ratio.\n5. The exchangeability strictly requires equal step sizes ηi​. While the authors mention this condition in Theorem 1, they do not explicitly quantify how unequal ηi​ affects practical ASD performance (tested empirically but not theoretically).\n6. In Theorem 11, The proof states E[Σt] is non-increasing in PSD order but does not explicitly cite the Löwner-Heinz theorem, which is required for this claim.\n7. The advantages of ASD in terms of error and acceleration ratio compared to Picard's iterative method of Shih et al. (2024) need to be quantitatively compared (e.g., FID vs. speed profiles).\n8. ASD's computational cost of rejection sampling (e.g., rejection rate of Algorithm 3) is not quantitatively analysed. High rejection rates may weaken the actual acceleration, and acceptance rate statistics under different tasks need to be added.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j7dEYa2bmk", "reviewer": "Reviewer_8PeN", "summary": "Diffusion models can be expensive to sample from, since sampling involves integrating a certain stochastic process, and is hence autoregressive (first one needs to take one step, then another step conditional on the result of the previous step, and so on). It would be extremely nice if there were some way to parallelize this sequential process, although it is not obvious whether a way to do this exists.\n\nThe authors adapt a recent method for parallelizing autoregressive LLM sampling to diffusion models. They provide a detailed theoretical account of this algorithm and its time complexity as a function of the data distribution's dimensionality, and also illustrate how much it empirically speeds up sampling in a variety of real settings. Their algorithm depends on a relatively surprising feature of diffusion model trajectories that they call \"exchangeability\".", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\d}{\\mathsf{d}}$\n$\\newcommand{\\vx}{\\mathbf{x}}$\n$\\newcommand{\\vy}{\\mathbf{y}}$\n$\\newcommand{\\vz}{\\mathbf{z}}$\n\nThank you for your thoughtful review and insightful questions which have helped improve our work. We hope to address your concerns below:\n\n\n## Hidden Exchangeability Beyond OU DDPMs\n\nThanks for the helpful pointer! **The hidden exchangeability property is not limited to the OU process and actually holds for a large class of generic DDPM formulations, including both VP-SDE and VE-SDE**. This is because both VP-SDE and VE-SDE can be expressed as invertible reparametrizations of the OU process. As a consequence, they are both equivalent to the Stochastic Localization process, and thus, satisfy hidden exchangeability. We shall update our draft to include a proof of this result, which we briefly sketch below:\n\nConsider an arbitrary SDE of the form $\\d \\vz_t = h(t) \\vz_t \\d t + \\sqrt{g(t)} \\d B_t$ where $g, h$ are arbitrary continuously differentiable functions with $g(t) > 0$. Note that $h(t) = -\\tfrac{1}{2}g(t)$ recovers VP-SDE and $h(t) = 0$ recovers VE-SDE. Now, consider the OU process $\\d \\vx_t = - \\vx_t \\d t + \\sqrt{2} \\d B_t$ with $\\vx_0 = \\vz_0$ and let $\\vy_t =  m(t,\\vy_t) \\d t + \\d B_t$ denote the SL process as defined in Section 3.1 Eqn 4. Now, define the functions $\\alpha(t)$ and $r(t)$ as follows:\n$$ \\alpha(t) = \\frac{1}{2} \\ln \\left(1 + \\int_{0}^{t} g(s) \\exp({-2 \\int_{0}^{s} h(u) \\d u}) \\ \\d s\\right) $$\n$$ r(t) = \\exp(\\alpha(t) + \\int_{0}^{t} h(s) \\d s)$$\n\nSince $g(t) > 0$, $\\alpha$ is a strictly increasing function with $\\alpha(0) = 0$, i.e., $\\alpha$ is an invertible function. Furthermore, $r(t) > 0 $. One can now Apply Ito's Lemma and the time transformation theorem for SDEs (see [1, Thm 8.5.7]) to prove that $\\vz_t = r(t) \\vx_{\\alpha(t)}$, i.e., $\\vz_t$ is reparametrizable to the OU process. As discussed in Section 3.1 of our work, $\\vy_t = t e^{s(t)} \\vx_{s(t)}$ where $s(t) = \\tfrac{1}{2} \\ln(\\tfrac{t+1}{t})$. It follows that $\\vz_t$ also maps to the SL process via the following parametrization:\n$$\\vy_t = \\frac{t e^{s(t)}}{r(\\alpha^{-1}(s(t)))} \\vz_{\\alpha^{-1}(s(t))}$$\nConsequently, **the hidden exchangeability property also applies to $\\vz_t$**\n\n## Effects of Autospeculation on Sample Quality \n\nAs elucidated in Tables 1, 2 and 3, our evaluations demonstrate that **ASD consistently achieves the same sample quality as the sequential DDPM implementation** (benchmarked via CLIP and FID scores for Image Generation and Task Success Rates for Robomimic Tasks) These findings corroborate our theoretical guarantee that ASD is an error-free parallelization scheme that always produces exact samples from the original DDPM's output distribution (Theorem 3).\n\n### References\n\n1. Oksendal : Stochastic Differential Equations", "claims_and_evidence": "The authors provide both detailed proofs of their theoretical claims and conduct a variety of helpful experiments to show that their method works well in practice. Both theory and experiment appear to be very high quality.", "methods_and_evaluation_criteria": "Yes. Their algorithm makes sense, and they spend significant real estate to explain its intuition and details. Their experiments also make sense, and they are careful to explain various technical details (e.g., the different relevant senses in which their algorithm can provide a speedup).", "theoretical_claims": "No, but the authors write clearly and convincingly, so I am reasonably confident their results are correct.", "experimental_designs_or_analyses": "No, but the authors write clearly and convincingly, so I am reasonably confident their results are correct.", "relation_to_broader_scientific_literature": "The authors' proposal makes an interesting bridge between making (sampling from) LLMs more efficient, and making (sampling from) diffusion models more efficient. Their theoretical work builds on a variety of previous formal-math-flavored theory for understanding diffusion models. Their proposal is also related to various other ideas about how to speed up diffusion model inference, and the authors clearly compare their approach to these ideas (e.g., by pointing out that their method has theoretical guarantees related to being error-free, unlike some other methods).", "essential_references_not_discussed": "No references come to mind.", "other_strengths_and_weaknesses": "The paper is well-written and clearly organized. The math is high-quality. The figures look great.", "other_comments_or_suggestions": "small typo in fig 3 caption, \"different sampling method\"->\"different sampling methods\"", "questions_for_authors": "My main questions are related to the surprising exchangeability result. The empirical experiments seem to indicate that exchangeability is 'true', or at least close enough in practice to 'true'. But I wonder to what extent the theoretical validity of exchangeability relates to defining the forward process as a pure OU process (Eq. 1). In particular, Eq. 1 does not involve any explicit time-dependence, and seems not to obviously include two popular schemes (VP-SDE, and the VE scheme used by EDM). \n\nFirst, is it always possible to reparameterize a given forward process (e.g., VE or VP-SDE) to obtain a pure OU process like the one the authors use? This doesn't seem to be true in the case of VE. If it's not true, is it close enough to being true? e.g., one can consider an OU process with $- \\epsilon \\ \\mathbf{x}$ for small $\\epsilon > 0$ to model the VE case.\n\nSecond, in practice, each forward process generalizes differently (for example, because common discretizations affect the corresponding reverse processes somewhat differently). So they are legitimately different, and not purely reparameterizations of one another. How can the authors' theory account for this? Also, does sampling via the authors' approach affect generalization or sample quality (e.g., FID scores) at all? A theoretical guarantee is one thing, but for various (theoretically interesting!) reasons things may be different in practice.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6M3mSdszt6", "reviewer": "Reviewer_FuEw", "summary": "This paper proposes and analyzes a parallel sampling scheme for diffusion models. The scheme is simple and natural -- instead of taking a single step from $x_t$ to $x_{t-1}$ during the reverse process in each iteration, multiple steps are taken in parallel from the expected positions $y_s$ given the position $x_t$ at time $t$, as \"proposals\" for the positions $x_s$, and then, rejection sampling is used to move back in time until a rejected sample if found. The authors show that this scheme gives an $O(d^{2/3})$ time sampling scheme whose performance exactly matches the analogous sequential scheme. Notably, the bound holds without assumption of Lipschitzness of the score, representing the first sublinear in $d$ bound for such distributions, albeit with the use of parallelism. Empirically, the authors show a speed up over DDPM.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and for taking the time to engage with our work. We hope to address your concerns below:\n\n## Comparing ASD with Prior Works\n\nPrior works based on Picard Iterations *can only produce approximate samples* from the DDPM output distribution. In particular, these approaches need to trade-off sample quality against parallel speedup by tuning the error tolerance hyperparameter of the Picard Iteration. On the contrary, ASD is an error-free parallelization scheme that *always produces exact samples* from the DDPM output distribution *for any choice of hyperparameters* (as was also noted by the reviewer). Due to this fundamental difference, we believe the two approaches cannot be compared on equal footing. \n\nOur approach of parallelizing DDPMs via autospeculation represents a novel and fundamentally different \"axis of improvement\" compared to Picard iterations. In particular, the two approaches are orthogonal to each other and can potentially be combined together for even greater parallel speedups (e.g., by using ASD to sample from each level of the Picard Iteration). This integration presents an exciting direction for future research.\n\nGiven these considerations, we believe that the original DDPM sampling method is the most appropriate and fair benchmark for evaluating ASD. We highlight that the primary objective of our experiments was to empirically validate our theoretically guaranteed speedups, while demonstrating a practical application of the hidden exchangeability property of DDPMs (which we believe has potential for broader applications beyond faster DDPM inference).", "claims_and_evidence": "Yes, the claims are supported by clear evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, they are correct.", "experimental_designs_or_analyses": "Yes, they are sound.", "relation_to_broader_scientific_literature": "This paper is part of a line of recent work proposing and analyzing sampling algorithms for diffusion models. It is the first paper that gives a sublinear in $d$ iteration complexity for sampling from distributions without a score Lipschitzness assumption, by making use of parallelism. In contrast, prior work (Gupta et al, 2024; Chen et al, 2024) has shown \\emph{polylogarithmic} in $d$ bounds, under a Lipschitzness assumption. Unlike these works which \\emph{approximate} the analogous sequential sampling algorithm, this paper proposes a scheme whose samples exactly match the sequential algorithm's.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "While the scheme is interesting, I would have liked to see experimental comparison with the parallel schemes from prior works -- currently it is unclear how well this scheme performs in practice relative to those approximation schemes. This is perhaps the biggest weakness of this work.", "other_comments_or_suggestions": "Generally the paper is well-written, but again, I would have liked to see comparison with prior parallel algorithms.", "questions_for_authors": "Can you perform experiments that compare your scheme to prior parallel sampling schemes?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors adapt the idea of speculative decoding in LLMs to provide a technique that uses parallelization to accelerate the process of drawing samples from a denoting diffusion model (DDPM).  Their innovation is based on an exchangeability property in the increments of the denoising process.  This provides exact sampling, in the sense that the distribution of the DDPM is not altered by the parallelization, but reduces iteration complexity from O(d) to O(d^{2.3}), where d is the dimension of the samples.

This seems like a very interesting idea, on a computational problem that is quite meaningful and potentially impactful. Overall, reviewers were positive, with some concerns that certain aspects could be made clearer -- more information on the exchangeability result, for example, which underpins the method; and potential "non-ideal" aspects of practical sampling processes, such as discretization effects, could undercut the theory in practice (although the authors argue that the samples remain of good quality). Reviewer FuEw also points out a number of missing references on parallel sampling using additional assumptions and providing approximate samples; comparing to these methods would strengthen the paper.
Decision: Accept (poster)