When Diffusion Model Can Ignore Dimension: An Entropy-Based Theory

Technical Summary: When Diffusion Model Can Ignore Dimension: An Entropy-Based Theory

1. Problem Statement

Diffusion models have demonstrated remarkable empirical success in generating high-dimensional data (e.g., images, audio) using a relatively modest number of reverse-time steps. However, existing theoretical convergence guarantees often fail to explain this efficiency. Prior analyses typically bound the discretization error (the gap between the continuous reverse process and its numerical approximation) in terms of the ambient dimension $d$ of the data space. While some recent works have improved these bounds by assuming geometric structures (e.g., low-dimensional manifolds) or specific distributional forms (e.g., Gaussian mixtures with bounded component means), a fundamental theoretical question remains: Why do diffusion samplers remain efficient in high-dimensional spaces when the data admits a compact latent representation?

The authors argue that measuring complexity via ambient dimension, covering numbers, or geometric intrinsic dimension may not be the correct metric for diffusion sampling. Instead, they propose that the relevant complexity is the amount of latent uncertainty the reverse process must resolve.

2. Methodology and Problem Setup

The paper adopts an information-theoretic perspective, shifting the focus from geometric dimension to Shannon entropy.

Target Model:
The authors consider data generated from a latent Gaussian mixture:
$$Z = U + \epsilon G_0, \quad U = \mu_J$$
where:

• $J$ is a discrete latent variable indexing a mixture component with probabilities $(\pi_j)$.
• $\mu_j \in \mathbb{R}^d$ are the mixture centers (latent codes mapped to pixel space).
• $G_0 \sim \mathcal{N}(0, I_d)$ is Gaussian noise.
• $\epsilon \ge 0$ controls the reconstruction/residual noise.
• The ambient dimension $d$ can be arbitrarily large, but the dominant uncertainty is carried by the discrete index $J$.

Sampling Procedure:
The authors analyze a score-based reverse sampler. Unlike standard discretizations that freeze the posterior mean of the full data variable, this sampler utilizes the latent posterior mean.

• The score function is related to the latent posterior mean $M_t(x) = \mathbb{E}[U \mid X_t = x]$ via Tweedie's formula.
• The proposed sampler (Equation 1) freezes the estimate of the latent center $\hat{M}_{t_{k-1}}$ during each time interval $(s_{k-1}, s_k]$, rather than the full data posterior.
• This formulation allows the algorithm to remain fully score-based (using learned scores $\hat{s}_t$) while theoretically leveraging the structure of the latent variable.

Error Decomposition:
The total Kullback–Leibler (KL) divergence between the target distribution and the sampler's output is decomposed into three terms:

1. Initialization error: Distance from the prior.
2. Score-approximation error: Error due to imperfect score estimation.
3. Discretization error: Error due to the finite number of time steps $K$.

The core contribution lies in bounding the discretization error.

3. Key Contributions and Theoretical Results

A. Entropy-Based Discretization Bound
The main result (Theorem 1) establishes that for Gaussian mixture targets, the discretization error is controlled by the Shannon entropy $H(J)$ of the latent component, rather than the ambient dimension $d$.

Specifically, for a suitable $K$-step sampling grid, the KL divergence is bounded by:
$$\text{KL}(P_\delta \parallel \hat{P}_{T-\delta}) \le \frac{R}{2T} + \frac{4H(J)}{K} \left( 2 + \log^+ \frac{R \eta_{\max}}{2H(J)} \right)^2 + \frac{1}{2} e_{\text{apx}}$$
where:

• $R = \mathbb{E}\|Z\|^2$ is the second moment.
• $\eta_{\max}$ relates to the endpoint signal-to-noise ratio.
• $e_{\text{apx}}$ is the score-approximation error.
• $\log^+(x) = \max\{\log x, 0\}$.

Key Implications of the Bound:

• Linear Scaling with Entropy: The leading term scales linearly with $H(J)$ and inversely with $K$.
• Logarithmic Dependence on Scale: The dependence on the second moment $R$ and signal-to-noise level is only logarithmic, contrasting sharply with linear or polynomial dependencies on $d$ found in prior works.
• Infinite Components: The bound holds for countably infinite mixture components as long as $H(J) < \infty$.

B. Technical Mechanism: I-MMSE Identity
The proof converts the numerical analysis problem into an information-theoretic one.

1. The discretization error is rewritten as an area functional involving the Minimum Mean-Square Error (MMSE) of the Gaussian channel associated with the latent variable $U$.
2. Using the I-MMSE identity (Guo, Shamai, and Verdú), the authors relate the integral of the MMSE to the Mutual Information $I(U; U + \text{noise})$.
3. By the data processing inequality, $I(U; \cdot) \le H(J)$.
4. This yields a pointwise bound on the MMSE: $\text{mmse}(\eta) \le \min\{R, 2H(J)/\eta\}$.
5. A hybrid grid construction (uniform in low-SNR, geometric in high-SNR) is used to integrate this bound, resulting in the final entropy-dependent complexity.

C. Extension to Discrete Targets
The analysis extends to the limit $\epsilon \to 0$, where the Gaussian mixture collapses to a discrete distribution supported on embedded codewords. In this regime, the complexity is governed strictly by the entropy of the target distribution itself. This applies to:

• Vector-quantized latent codes (e.g., VQ-VAE, VQGAN).
• Embedded discrete sequences (e.g., Diffusion-LM).

4. Significance and Claims

The paper claims that its results provide a theoretical explanation for the efficiency of diffusion sampling in high-dimensional spaces when data possesses a compact latent representation.

• Beyond Ambient Dimension: The results suggest that the "effective dimension" for diffusion sampling is not the pixel dimension $d$, but the information content (entropy) of the latent code. For natural images, which are believed to lie on low-dimensional manifolds or be representable by compact tokens, $H(J)$ can be orders of magnitude smaller than $\log(\text{ambient space size})$.
• Comparison to Prior Work:
  • Unlike Total Variation (TV) bounds that may saturate or depend on the worst-case number of mixture components ($\log K_{\text{mix}}$), this KL bound depends on the effective uncertainty $H(J)$. If mixture weights are non-uniform, $H(J) \ll \log K_{\text{mix}}$, offering a sharper guarantee.
  • Unlike discrete diffusion samplers (e.g., $\tau$-leaping) whose complexity scales with vocabulary size $S$, this Gaussian diffusion bound scales with $H(J) \le d \log S$, offering a potentially sharper dependence on vocabulary size for embedded discrete data.
• Modesty of Claims: The authors explicitly note limitations. The analysis is specific to Gaussian-mixture targets and the latent-posterior freezing sampler. It does not prove that arbitrary high-dimensional data distributions admit such a compact latent representation; rather, it explains the efficiency conditional on such a representation existing.

In summary, the paper posits that diffusion models are efficient in high dimensions not because the ambient space is small, but because the latent uncertainty they must resolve is small, a property captured by Shannon entropy rather than geometric dimension.