Uniform Stride Timestep Subsequence

mediumPRODDPM and DDIM SamplingDiffusion ModelsDiffusion Models 1

Problem Statement

Fast samplers run on a sparse subset of the T training timesteps. Build the uniformly strided DDIM subsequence used by most implementations.

Background

To take S sampling steps out of T training steps, use a constant stride c = T // S and pick timesteps 0, c, 2c, ..., (S-1)c, then reverse them so sampling runs from high noise to low:

$\text{seq} = [\,(S-1)c,\; (S-2)c,\; \dots,\; c,\; 0\,]$

This is the "uniform" spacing from the DDIM paper (as opposed to "quadratic").

Your Task

Implement:

def ddim_timesteps(T, S):

Return the descending list of S timesteps.

Input Format

T (int): number of training steps.
S (int): number of sampling steps, 1 <= S <= T.

Output Format

A list of S ints, descending.

Sample

print(ddim_timesteps(1000, 5))

Output:

[800, 600, 400, 200, 0]

Example

Input

print(ddim_timesteps(1000, 5))

Output

[800, 600, 400, 200, 0]

Reasoning

Calculate the uniform stride $c$ by performing integer division of the total training steps $T$ by the sampling steps $S$ : $c = 1000 // 5 = 200$ .
Generate the ascending sequence of timesteps by multiplying the stride $c$ by indices from $0$ to $S-1$ : $[0 \cdot 200, 1 \cdot 200, 2 \cdot 200, 3 \cdot 200, 4 \cdot 200] = [0, 200, 400, 600, 800]$ .
Reverse the ascending sequence to create the descending order required for sampling from high noise to low noise: $[800, 600, 400, 200, 0]$ .
The final output is [800, 600, 400, 200, 0]

Constraints

1 <= S <= T <= 1000000.
Stride c = T // S; timesteps are 0, c, ..., (S-1)c, then reversed.
Return exactly S descending ints.

Learn this in

Sampling & AccelerationDiffusion Study Plan

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

Concept primerPREVIEW

1. Background Knowledge

In DDPM (Denoising Diffusion Probabilistic Models), a model is trained to reverse a gradual noising process across $T$ discrete timesteps. Sampling from the trained model by stepping through all $T$ timesteps is computationally expensive. DDIM (Denoising Diffusion Implicit Models) introduced a deterministic, accelerated sampling scheme that allows the model to take only $S$ steps, where $S \ll T$ , while still producing high-quality samples.

The choice of which timesteps to visit is critical. The most common strategy is uniform striding: divide the total range $[0, T)$ into $S$ equally spaced intervals. The stride (or step size) is computed as $c = T // S$ . The selected timesteps are then $0, c, 2c, \dots, (S-1)c$ . Because diffusion sampling proceeds from high noise to low noise, the sequence must be reversed so that the largest timestep comes first. This uniform schedule is simpler and often sufficient compared to more complex schedules like quadratic spacing, which concentrate more steps near the high-noise end.

Understanding this problem requires familiarity with integer division in Python (//), which performs floor division. For example, $1000 // 5 = 200$ , but $1000 // 3 = 333$ (the remainder is discarded). This means the last selected timestep $(S-1) \cdot c$ may not exactly equal $T - c$ or $T$ ; it will be the largest multiple of $c$ that is strictly less than $T$ .

2. Algorithm Approach

This is a straightforward arithmetic sequence generation problem. The core pattern is:

Compute the stride $c = T // S$ .
Generate the ascending sequence $[0, c, 2c, \dots, (S-1)c]$ using a range or list comprehension.
Reverse the sequence to get the descending order required for DDIM sampling.

No complex data structures or iterative refinement are needed. The entire solution is a one-liner or a few lines of Python that leverage range() and slicing or reversed().

3. Step-by-Step Strategy

Step 1: Compute the stride. Calculate c = T // S. This gives the spacing between consecutive selected timesteps.

PRO

Continue the full explanation

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

PRO

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