Quadratic Stride Timestep Subsequence

mediumPRODDPM and DDIM SamplingDiffusion ModelsDiffusion Models 1

Problem Statement

The DDIM paper's "quadratic" spacing places more sampling steps near the low-noise end, which improves sample quality for very few steps. Build that descending subsequence.

Background

For S steps out of T, quadratic spacing takes S points evenly on [0, sqrt(T * 0.8)], squares them, and floors to integer timesteps:

$t_i = \left\lfloor \left(\frac{i}{S-1}\,\sqrt{0.8\,T}\right)^2 \right\rfloor, \quad i = 0, \dots, S-1$

then reverse for high-to-low sampling. (The 0.8 factor keeps the largest index below T.) For S == 1 return [0].

Your Task

Implement:

def quadratic_timesteps(T, S):

Return the descending list of S integer timesteps.

Input Format

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

Output Format

A list of S ints, descending.

Sample

print(quadratic_timesteps(1000, 5))

Output:

[800, 450, 200, 50, 0]

Example

Input

print(quadratic_timesteps(1000, 5))

Output

[800, 450, 200, 50, 0]

Reasoning

Since $S = 5 > 1$ , we first determine the upper bound for the square root calculation: $\sqrt{0.8 \times 1000} = \sqrt{800} \approx 28.284$ .
We generate the ascending sequence of $S=5$ points by evaluating $t_i = \lfloor (\frac{i}{4} \times 28.284)^2 \rfloor$ for $i = 0, 1, 2, 3, 4$ .
For $i=0$ and $i=1$ , the values are $\lfloor 0 \rfloor = 0$ and $\lfloor (7.071)^2 \rfloor = \lfloor 50.0 \rfloor = 50$ .
For $i=2$ and $i=3$ , the values are $\lfloor (14.142)^2 \rfloor = \lfloor 200.0 \rfloor = 200$ and $\lfloor (21.213)^2 \rfloor = \lfloor 450.0 \rfloor = 450$ .
For $i=4$ , the value is $\lfloor (28.284)^2 \rfloor = \lfloor 800.0 \rfloor = 800$ , yielding the ascending list $[0, 50, 200, 450, 800]$ .
Reversing this list to create the descending timestep sequence results in the final output [800, 450, 200, 50, 0].

Constraints

1 <= S <= T <= 1000000.
t_i = floor((i/(S-1) * sqrt(0.8*T))**2), then reversed; S==1 gives [0].
Return exactly S descending ints.

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 DDIM (Denoising Diffusion Implicit Models) sampling, you do not need to run all $T$ training steps to generate a sample. Instead, you pick a subsequence of $S$ timesteps to evaluate the denoiser at. The choice of which timesteps to use is called the schedule or spacing. A uniform spacing (e.g., every $T/S$ steps) wastes capacity at the high-noise end where the signal is already very noisy and the denoiser has little to do, while under-sampling the low-noise end where fine detail is recovered.

The quadratic spacing from the DDIM paper addresses this by concentrating steps near the low-noise (small $t$ ) end. The idea is to sample $S$ points uniformly on the square root of the timestep axis, then square them back. Because the square function is convex and grows faster for larger inputs, equal spacing in $\sqrt{t}$ -space becomes increasingly sparse in $t$ -space as $t$ grows. This means the early (high- $t$ ) steps are far apart, while the later (low- $t$ ) steps are packed closely together, giving the model more resolution where it matters most.

The factor $0.8$ in $\sqrt{0.8\,T}$ ensures that even the largest computed timestep stays safely below $T$ , avoiding an out-of-range index into the precomputed noise schedule arrays. The final list is returned in descending order because DDIM sampling proceeds from high noise ( $t \approx T$ ) to low noise ( $t = 0$ ).

2. Algorithm Approach

This is a direct formula evaluation problem. There is no search, no dynamic programming, no sorting. You simply:

Handle the edge case $S = 1$ .
For each index $i$ from $0$ to $S-1$ , compute the closed-form expression for $t_i$ .
Reverse the resulting list so it is descending.

The key mathematical operation is: evaluate a linearly-spaced sequence on $[0, \sqrt{0.8\,T}]$ , square each element, and floor to an integer. You can think of it as a two-stage transform: linear spacing → square → floor.

3. Step-by-Step Strategy

Edge case: If $S == 1$ , return ** immediately.
Compute the upper bound: Let $U = \sqrt{0.8 \times T}$ . This is the maximum value in the square-root domain.
Generate the linearly-spaced values: For each $i \in \{0, 1, \dots, S-1\}$ , compute $x_i = \frac{i}{S-1} \cdot U$ . Note that $x_0 = 0$ and $x_{S-1} = U$ .
Square and floor: Compute $t_i = \lfloor x_i^2 \rfloor$ . This gives you the ascending subsequence of integer timesteps.
Reverse: Return the list in reverse order so the largest timestep comes first.

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