The DDIM Sampling Algorithm

The DDPM sampling algorithm provides a principled way to reverse the diffusion process. However, it often requires simulating many small steps (equal to the number of forward steps, $T$), which can be computationally expensive and slow. Imagine needing 1000 steps to generate a single image; this quickly becomes impractical for many applications.

Fortunately, Denoising Diffusion Implicit Models (DDIM), introduced by Song, Meng, and Ermon (2020), offer a more flexible and often significantly faster alternative. The insight behind DDIM is that the objective function used to train the noise prediction network $\epsilon_\theta$ doesn't strictly depend on the Markovian property of the forward process assumed by DDPM. DDIM uses this by proposing a different generative process (reverse process) that is non-Markovian but still uses the same trained network $\epsilon_\theta$.

The Core Idea of DDIM

Recall the DDPM reverse step aims to approximate $p(x_{t-1}|x_t)$. DDIM takes a different approach. It starts from the property that given the original data $x_0$ and the noise $\epsilon$ used to generate $x_t$, we can write:

$$x_t = \sqrt{\bar{\alpha}_t} x_0 + \sqrt{1 - \bar{\alpha}_t} \epsilon$$

We can rearrange this to get an estimate of the original data $x_0$ based on the current noisy sample $x_t$ and the predicted noise $\epsilon_\theta(x_t, t)$:

$$\hat{x}_0(x_t, t) = \frac{x_t - \sqrt{1 - \bar{\alpha}_t} \epsilon_\theta(x_t, t)}{\sqrt{\bar{\alpha}_t}}$$

This $\hat{x}_0$ represents a prediction of the final clean data point, made from the noisy intermediate $x_t$.

DDIM then defines the step to $x_{t-1}$ by combining this predicted $\hat{x}_0$ with the predicted noise $\epsilon_\theta(x_t, t)$, but in a way that allows for deterministic transitions and skipping steps. The general DDIM update rule is:

$$x_{t-1} = \underbrace{\sqrt{\bar{\alpha}_{t-1}} \hat{x}_0(x_t, t)}_{\text{Predicted } x_0 \text{ scaled}} + \underbrace{\sqrt{1 - \bar{\alpha}_{t-1} - \sigma_t^2} \epsilon_\theta(x_t, t)}_{\text{Direction pointing to } x_t} + \underbrace{\sigma_t z}_{\text{Random noise}}$$

where $z \sim \mathcal{N}(0, \mathbf{I})$ is standard Gaussian noise, and $\sigma_t$ controls the amount of stochasticity.

Deterministic Sampling ($\eta=0$)

A significant feature of DDIM is that we can choose the standard deviation $\sigma_t$. A common choice is to set $\sigma_t = 0$. This makes the update step completely deterministic given $x_t$ and the prediction $\epsilon_\theta(x_t, t)$:

$$x_{t-1} = \sqrt{\bar{\alpha}_{t-1}} \hat{x}_0(x_t, t) + \sqrt{1 - \bar{\alpha}_{t-1}} \epsilon_\theta(x_t, t)$$

Substituting the expression for $\hat{x}_0(x_t, t)$:

$$x_{t-1} = \sqrt{\bar{\alpha}_{t-1}} \left( \frac{x_t - \sqrt{1 - \bar{\alpha}_t} \epsilon_\theta(x_t, t)}{\sqrt{\bar{\alpha}_t}} \right) + \sqrt{1 - \bar{\alpha}_{t-1}} \epsilon_\theta(x_t, t)$$

This deterministic nature means that starting from the same initial noise $x_T$, we will always generate the same final output $x_0$. This is quite different from DDPM, where the added noise $\sigma_t z$ at each step leads to variations even from the same starting $x_T$.

Faster Sampling with Subsequences

The non-Markovian nature and the deterministic update rule (when $\sigma_t=0$) allow DDIM to work effectively even when using only a subsequence of the original timesteps $[1, ..., T]$. For instance, instead of taking 1000 steps, we might define a sampling sequence $S$ of only 50 or 100 timesteps, say $S = (T, T-\frac{T}{N_{steps}}, T-2\frac{T}{N_{steps}}, ..., 1)$, where $N_{steps}$ is the desired number of sampling steps (e.g., 50).

The DDIM update then proceeds by stepping between consecutive timesteps in this subsequence. If $t$ and $t'$ are two consecutive timesteps in the subsequence $S$ (with $t' < t$), the update calculates $x_{t'}$ based on $x_t$, using the same formulas but substituting $t-1$ with $t'$. This allows for much larger "jumps" in the denoising process, significantly accelerating generation.

The DDIM Algorithm

Here is the procedure for sampling using DDIM, often with the deterministic setting ($\sigma_t=0$):

1. Choose Timesteps: Select a subsequence of $N_{steps}$ timesteps $S = (s_1, s_2, ..., s_{N_{steps}})$ from $(1, ..., T)$, typically in descending order (e.g., $s_1=T, s_2 \approx T-\frac{T}{N_{steps}}, ..., s_{N_{steps}} \approx 1$). Let $s_0=0$.
2. Initial Noise: Sample the starting noise $x_{s_1} = x_T \sim \mathcal{N}(0, \mathbf{I})$.
3. Iterative Denoising: For $i = 1, ..., N_{steps}$:
   • Get the current timestep $t = s_i$ and the previous timestep $t' = s_{i+1}$ (using $t'=0$ if $i=N_{steps}$).
   • Predict the noise using the trained model: $\epsilon_\theta(x_t, t)$.
   • Predict the clean data: $\hat{x}_0(x_t, t) = \frac{x_t - \sqrt{1 - \bar{\alpha}_t} \epsilon_\theta(x_t, t)}{\sqrt{\bar{\alpha}_t}}$.
   • Clip $\hat{x}_0$ if necessary (e.g., to $[-1, 1]$ for normalized images).
   • Calculate the variance $\sigma_t$. A common generalization uses a parameter $\eta \in [0, 1]$: $$\sigma_t = \eta \sqrt{\frac{1 - \bar{\alpha}_{t'}}{1 - \bar{\alpha}_t}} \sqrt{1 - \frac{\bar{\alpha}_t}{\bar{\alpha}_{t'}}}$$ Setting $\eta=0$ gives $\sigma_t = 0$ (deterministic DDIM). Setting $\eta=1$ gives a stochastic version.
   • Calculate the next sample $x_{t'}$: $$x_{t'} = \sqrt{\bar{\alpha}_{t'}} \hat{x}_0(x_t, t) + \sqrt{1 - \bar{\alpha}_{t'} - \sigma_t^2} \epsilon_\theta(x_t, t) + \sigma_t z$$ where $z \sim \mathcal{N}(0, \mathbf{I})$ if $\sigma_t > 0$, and $z=0$ if $\sigma_t=0$. Note that if $t'=0$, then $\bar{\alpha}_{t'}=1$ and the formula simplifies: $x_0 = \hat{x}_0(x_t, t)$.
4. Output: Return the final sample $x_0$.

Comparison of DDPM and deterministic DDIM ($\eta=0$) sampling. DDPM uses small, stochastic steps based on the Markovian assumption. DDIM calculates a predicted $x_0$ at each step and uses it to take larger, deterministic steps according to a chosen subsequence $S$, significantly reducing the number of required network evaluations.

The ability to use fewer steps ($N_{steps} \ll T$) makes DDIM a very popular choice for practical applications where generation speed is important. In the next section, we'll discuss the trade-offs between these two sampling methods.