DDIM Timestep Subsequence

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:

1. step = T // num_steps (integer division).
2. Take 0, step, 2*step, ..., keeping the first num_steps values.
3. Reverse to get descending sampling order.
4. 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)].