Ancestral Sampling Trajectory Norm

hardPRODDPM and DDIM SamplingDiffusion ModelsDiffusion Models 1

Problem Statement

Run a short deterministic DDIM trajectory end-to-end over a given alpha-bar subsequence, using a constant noise prediction at every step (a toy oracle), and report the L2 norm of the final sample. This checks that you chain the per-step updates correctly.

Background

Given a descending list of alpha-bar values abs = [ab_0, ab_1, ..., ab_{K}] (from noisiest to a final 1.0) and a fixed predicted noise eps, run deterministic DDIM (eta=0) starting from x_start:

for each consecutive pair (ab_t, ab_prev):

x0_hat = (x - sqrt(1-ab_t)*eps)/sqrt(ab_t)
x      = sqrt(ab_prev)*x0_hat + sqrt(1-ab_prev)*eps

After the loop, return round(||x||_2, 4) where ||.||_2 is the Euclidean norm over all dimensions.

Your Task

Implement:

def trajectory_norm(x_start, eps, alpha_bars):

alpha_bars: list of K+1 alpha-bar values (descending, last is the target, e.g. 1.0).

Return the final sample's L2 norm rounded to 4 decimals.

Input Format

x_start, eps: lists of length D.
alpha_bars: list of >= 2 values in (0, 1].

Output Format

A float rounded to 4 decimals.

Sample

print(trajectory_norm([1.4142, 0.0], [1.0, -1.0], [0.5, 1.0]))

Output:

1.4142

Example

Input

print(trajectory_norm([1.4142, 0.0], [1.0, -1.0], [0.5, 1.0]))

Output

1.4142

Reasoning

Initialize the state vector $x$ with the input $[1.4142, 0.0]$ and the noise vector $\epsilon$ with $[1.0, -1.0]$ . The algorithm iterates through the alpha-bar pairs; here, there is only one step from $ab_t = 0.5$ to $ab_{prev} = 1.0$ .
Compute the estimated clean sample $x_0$ $x_{0}$ using the current noise level $ab_t = 0.5$ $a b_{t} = 0.5$ . The term $\sqrt{1 - 0.5} = \sqrt{0.5} \approx 0.7071$ $1 - 0.5 = 0.5 \approx 0.7071$ scales the noise, and dividing by $\sqrt{0.5} \approx 0.7071$ $0.5 \approx 0.7071$ normalizes the signal.
- Dimension 0: $x_0[0] = (1.4142 - 0.7071 \cdot 1.0) / 0.7071 = 0.7071 / 0.7071 = 1.0$
- Dimension 1: $x_0[1] = (0.0 - 0.7071 \cdot (-1.0)) / 0.7071 = 0.7071 / 0.7071 = 1.0$
- Resulting $x_0 = [1.0, 1.0]$ .
Update $x$ $x$ to the next step using $ab_{prev} = 1.0$ $a b_{p re v} = 1.0$ . Since $\sqrt{1.0} = 1.0$ $1.0 = 1.0$ and $\sqrt{1 - 1.0} = 0$ $1 - 1.0 = 0$ , the noise term vanishes, and $x$ $x$ becomes exactly $x_0$ $x_{0}$ .
- $x[0] = 1.0 \cdot 1.0 + 0 \cdot 1.0 = 1.0$
- $x[1] = 1.0 \cdot 1.0 + 0 \cdot (-1.0) = 1.0$
- Resulting $x = [1.0, 1.0]$ .
Calculate the L2 norm of the final vector $x$ : $\sqrt{1.0^2 + 1.0^2} = \sqrt{2} \approx 1.41421356$ .
The final output is 1.4142

Constraints

len(x_start) == len(eps); len(alpha_bars) >= 2, values in (0, 1].
Chain deterministic DDIM steps over consecutive alpha-bar pairs.
Return the Euclidean norm of the final sample, rounded to 4 decimals.

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

Diffusion models learn to generate data by gradually adding Gaussian noise to a sample over many timesteps, then learning to reverse that process. The forward process is parameterized by a schedule of noise levels, often expressed through $\bar{\alpha}_t$ , the cumulative product of per-step retention factors. A larger $\bar{\alpha}_t$ means less noise has been added; $\bar{\alpha}_T \approx 0$ corresponds to pure noise, while $\bar{\alpha}_0 = 1$ corresponds to the clean data.

DDIM (Denoising Diffusion Implicit Models) provides a deterministic sampling scheme that, given a predicted noise $\epsilon_\theta(x_t, t)$ , can jump directly between any two noise levels without simulating every intermediate step. The key identity is that the predicted clean sample $\hat{x}_0$ can be recovered from the noisy sample $x_t$ and the predicted noise $\epsilon$ via:

\hat{x}_0 = \frac{x_t - \sqrt{1 - \bar{\alpha}_t}\,\epsilon}{\sqrt{\bar{\alpha}_t}}

Once $\hat{x}_0$ is known, the next (less noisy) sample at level $\bar{\alpha}_{t-1}$ is reconstructed as:

x_{t-1} = \sqrt{\bar{\alpha}_{t-1}}\,\hat{x}_0 + \sqrt{1 - \bar{\alpha}_{t-1}}\,\epsilon

This is the deterministic update ( $\eta = 0$ ); no stochastic term is added. In this problem, $\epsilon$ is a fixed constant vector (a "toy oracle"), so the trajectory is fully determined by the input and the $\bar{\alpha}$ schedule.

The L2 norm $\|x\|_2 = \sqrt{\sum_i x_i^2}$ measures the overall magnitude of the final sample across all dimensions.

2. Algorithm Approach

This is a straightforward iterative chain of vector operations. You process consecutive pairs of $\bar{\alpha}$ values from the noisiest end toward the cleanest end. For each pair $(\bar{\alpha}_t, \bar{\alpha}_{t-1})$ :

Compute $\hat{x}_0$ from the current $x$ and the constant $\epsilon$ .
Reconstruct the next $x$ at the previous $\bar{\alpha}$ level.
Update $x$ in place.

After all pairs are processed, compute the Euclidean norm of the final $x$ and round to 4 decimal places. There is no branching, no optimization, and no state beyond the current vector $x$ .

3. Step-by-Step Strategy

Initialize: Set x to a copy of x_start (avoid mutating the input).
Loop over indices i from 0 to len(alpha_bars) - 2:
Let ab_t = alpha_bars[i] and ab_prev = alpha_bars[i+1].
Compute sqrt_ab_t = sqrt(ab_t) and sqrt_1_minus_ab_t = sqrt(1 - ab_t).
Compute x0_hat element-wise: (x - sqrt_1_minus_ab_t * eps) / sqrt_ab_t.
Compute sqrt_ab_prev and sqrt_1_minus_ab_prev similarly.
Update x element-wise: sqrt_ab_prev * x0_hat + sqrt_1_minus_ab_prev * eps.
Final norm: Compute sqrt(sum(x_i^2 for all i)).
Return round(norm, 4).

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