📘

DDIM Timestep Subsequence

MediumDiffusion Models 📚 Diffusion Models 1

Problem Statement

Build the strided timestep subsequence a DDIM sampler walks when it generates an image in 50 steps from a model trained with 1000, together with the $\bar{\alpha}$ lookup that handles the final step.

Background

Because the DDIM update only ever references $\bar{\alpha}$ at the current and target timesteps, nothing forces the sampler to visit every trained timestep. It can walk any decreasing subsequence $\tau_S > \tau_{S-1} > \dots > \tau_1$ , which is why DDIM turns 1000 network evaluations into 20-50 with little quality loss.

The standard uniform stride, as implemented in diffusers, is:

step = T // num_steps (integer division).
Take 0, step, 2*step, ..., keeping the first num_steps values.
Reverse to get descending sampling order.
The target of timestep t is t - step. For the last step this goes negative, which signals "target is clean data": $\bar{\alpha}_{prev} = 1$ .

That final convention is final_alpha_cumprod = 1.0 in the reference code, and it is what lets the last step land on $\hat{x}_0$ exactly.

Your Task

Implement two functions:

def ddim_timesteps(T, num_steps):
def alpha_bar_at(alpha_bars, t):

ddim_timesteps returns a list of (t, t_prev) tuples of Python ints in descending sampling order, with t_prev set to -1 whenever the strided target falls below zero. alpha_bar_at returns float(alpha_bars[t]), or 1.0 when t < 0.

Input Format

T (int): number of training timesteps.
num_steps (int): number of sampling steps, 1 <= num_steps <= T.
alpha_bars: 1-D NumPy array.
t (int): index, possibly negative.

Output Format

ddim_timesteps returns a list of 2-tuples of ints; alpha_bar_at returns a float.

Sample

print(ddim_timesteps(1000, 5))

The stride is 200, so the ascending grid is [0, 200, 400, 600, 800]; reversed and paired with t - 200 this gives [(800, 600), (600, 400), (400, 200), (200, 0), (0, -1)].

Example:

Input:

print(ddim_timesteps(1000, 5))

Output:

[(800, 600), (600, 400), (400, 200), (200, 0), (0, -1)]

Reasoning:

step = 1000 // 5 = 200, so the ascending grid is [0, 200, 400, 600, 800]. Reversed, sampling walks 800, 600, 400, 200, 0, and each target is 200 lower. The last target would be -200, which is below zero, so it is reported as -1 -- the signal that alpha_bar_prev is 1 and this step lands on clean data.

Constraints:

Use integer division for the stride; T need not be divisible by num_steps.
Keep exactly num_steps timesteps -- np.arange(0, T, step) can return one extra when the division is inexact.
Return Python ints inside the tuples, not NumPy scalars (the tuples are printed directly).
t_prev is -1, never a smaller negative number.
alpha_bar_at must return 1.0 for any negative t, and never index with a negative number.

More from Diffusion Models 1

Classifier-Free Guidance: Uncond/Cond MixingEasy DDPM Posterior Mean and Variance from x0Medium Adaptive CFG Scheduling over the TrajectoryHard Classifier Gradient Guidance StepMedium Negative Prompt as the Unconditional BranchMedium

1. Background Knowledge

Diffusion Models operate by gradually adding noise to data over a fixed number of timesteps $T$ (typically 1000) during training, and then learning to reverse this process. The forward process is defined by a variance schedule $\beta_t$ , and the cumulative noise coefficient is denoted as $\bar{\alpha}_t = \prod_{s=1}^{t} (1 - \beta_s)$ . During sampling, the model predicts the noise or the original image $x_0$ from the noisy input $x_t$ .

DDIM (Denoising Diffusion Implicit Models) is a deterministic sampling method that allows for faster generation by skipping timesteps. Unlike DDPM, which requires visiting every timestep from $T$ down to $1$ , DDIM only needs the values of $\bar{\alpha}_t$ and $\bar{\alpha}_{t-1}$ (or rather, $\bar{\alpha}_{t_{prev}}$ ) to compute the next state. This property enables strided sampling, where the sampler jumps from $t$ to $t - \text{step}$ , significantly reducing the number of network evaluations from $T$ to $S$ (e.g., 50 steps).

The key insight for this problem is the timestep indexing convention. In many implementations (like diffusers), the timesteps are 0-indexed. The sampling process starts at the highest timestep in the subsequence and moves downwards. The "target" timestep for a current timestep $t$ is $t_{prev} = t - \text{step}$ . If $t_{prev} < 0$ , it indicates that the next state is the clean data $x_0$ , which corresponds to $\bar{\alpha} = 1.0$ . This special case must be handled explicitly in the lookup function.

2. Algorithm Approach

The problem requires implementing two distinct but related functions: one for generating the sampling schedule and one for safely retrieving noise coefficients.

Stride Calculation: The core of the schedule generation is determining the step size. Given $T$ training timesteps and $S$ desired sampling steps, the stride is calculated using integer division: $\text{step} = T // S$ . This ensures the steps are evenly distributed across the range $[0, T-1]$ .
Grid Generation: Create an ascending list of timesteps starting from $0$ with the calculated stride. We need exactly $S$ timesteps. The sequence is $0, \text{step}, 2 \cdot \text{step}, \dots, (S-1) \cdot \text{step}$ .
Reversal and Pairing: Since diffusion sampling goes from noisy (high $t$ ) to clean (low $t$ ), reverse the generated list. Then, pair each timestep $t$ with its target $t_{prev} = t - \text{step}$ .
Boundary Handling: If $t_{prev} < 0$ , set it to $-1$ . This sentinel value signals the lookup function to return $1.0$ .
Safe Lookup: The alpha_bar_at function must handle the sentinel value $-1$ by returning $1.0$ instead of accessing an invalid array index.

3. Step-by-Step Strategy

Implementing ddim_timesteps(T, num_steps)

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.