How Many Directions Must a Truncated Diffusion Sampler Retain? Matching Bounds Under Power-Law Spectra

Radmehr Karimian; Ali Mohades; Johannes Lederer

math.STOct 7, 2026

How Many Directions Must a Truncated Diffusion Sampler Retain? Matching Bounds Under Power-Law Spectra

Authors: Radmehr Karimian, Ali Mohades, Johannes Lederer

Organizations: Universit´e de Gen`eve · Universität Hamburg

Abstract

Diffusion samplers can reduce computation by generating selected spectral coordinates and filling the remaining directions with noise. How many directions must they retain? We study this question for data with power-law covariance spectra. For Gaussian data compared to a smoothed target, we prove matching bounds on the required number of retained directions, provided that the ambient dimension is sufficiently large. The truncation error depends on the combined Wiener gains of the omitted directions, regardless of the accuracy of the sampler on the retained coordinates. Keeping only directions whose signal exceeds the output noise level can therefore leave a non-vanishing error: many individually weak directions remain significant in aggregate. Combining this characterization with a diffusion convergence bound yields sufficient sampling-step complexity under exact scores. The upper bounds also extend to estimated principal components and, componentwise, to Gaussian mixtures. The practical prescription is to select the retained subspace using an aggregate spectral-tail error budget, then to choose the diffusion noise level accordingly.

Figures & tables

Panel of Figure 1 — Figure 1: Roadmap of the results. The error decomposition of Section 2 splits the problem into a truncation error, computed exactly for Gaussian data in Section 3 , and a sampling error on the retained coordinates, bounded for general data in Section 4 ; the two combine in Theorem 4 . Grey boxes are supporting results in the appendix; bold boxes are the main theorems.

Appendix figures & tables23 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Patch	$d$	Vectors	Sources	Window $[\ell,h]$	$\hat{b}/d$
CIFAR-10	8 $\times$ 8	192	6000/2000/2000	6000/2000/2000	$[8,48]$	0.09
CIFAR-10	16 $\times$ 16	768	6000/2000/2000	6000/2000/2000	$[8,192]$	0.10
CIFAR-100	8 $\times$ 8	192	6000/2000/2000	6000/2000/2000	$[8,48]$	0.17
CIFAR-100	16 $\times$ 16	768	6000/2000/2000	6000/2000/2000	$[8,192]$	0.10
DIV2K	8 $\times$ 8	192	1600/1280/1600	100/80/100	$[8,48]$	0.17
DIV2K	16 $\times$ 16	768	1600/1280/1600	100/80/100	$[8,192]$	0.10

Appendix

Table 1: Data used for the check. Vectors and independent sources (images; artists for FMA( Defferrard et al. (2017) )) per train/val/test split; fitting window

[\ell,h]

; fitted breakpoint relative to dimension,

\hat{b}/d

. † Audio, outside the scope of the paper.

		$\hat{\beta}$			Test log-MSE			Broken power law
Dataset	Patch	train	val	test	power	exp.	broken	$\hat{\beta}_{1}$	$\hat{\beta}_{2}$	$\hat{b}$
CIFAR-10	8 $\times$ 8	1.82	1.85	1.83	0.009	0.022	0.004	1.28	2.04	16
CIFAR-10	16 $\times$ 16	1.57	1.60	1.60	0.018	0.161	0.003	1.42	2.05	74
CIFAR-100	8 $\times$ 8	1.84	1.83	1.83	0.009	0.031	0.005	1.74	2.43	34
CIFAR-100	16 $\times$ 16	1.56	1.57	1.58	0.016	0.167	0.004	1.43	1.96	74
DIV2K	8 $\times$ 8	1.65	1.68	1.70	0.011	0.029	0.010	1.51	2.43	34

Appendix

Table 2: Model comparison on the common window.

\hat{\beta}

: power-law exponent fitted separately on each split. Test log-MSE of the power, exponential and broken power laws (smallest in bold).

\hat{\beta}_{1},\hat{\beta}_{2},\hat{b}

: broken-law head and tail exponents and breakpoint (training split).

		Window $[\ell,h]$				Bulk $[8,m]$
Dataset	Patch	train	val	test	broken law	$m$	$m/d$	train	val	test	$U$
CIFAR-10	8 $\times$ 8	1.66	1.68	1.55	1.47	89	0.46	3.21	3.20	3.28	1.0
CIFAR-10	16 $\times$ 16	1.63	1.70	1.79	1.57	295	0.38	3.25	3.18	3.30	1.0
CIFAR-100	8 $\times$ 8	1.62	1.64	1.53	1.23	96	0.50	3.11	3.29	3.05	1.0
CIFAR-100	16 $\times$ 16	1.55	1.61	1.68	1.46	306	0.40	3.12	3.05	3.21	1.1
DIV2K	8 $\times$ 8	1.51	1.37	1.39	1.32	76	0.40	2.93	2.21	2.57	5.1

Appendix

Table 3: Envelope ratios

C/c

of Assumption 1 with the training exponent

\hat{\beta}

. Window: observed ratio per split, and the ratio implied by the fitted broken power law alone (Proposition 5 ). Bulk: end

m

on the test split, and the ratio on

[8,m]

per split.

U

: factor by which including every resolved rank (in particular

i<8

) raises the upper constant, maximum over splits.

Figure 2: Sample covariance spectra of image patches (train and test splits; FMA audio in the last two panels). Shading: fitting window

[\ell,h]

. Dashed: power-law fit; dotted: broken power-law fit; thin vertical line: fitted breakpoint

\hat{b}

. Ranks beyond the sample rank are not shown.

Figure 3: Compensated spectra

\hat{\sigma}_{i}^{2}\,i^{\hat{\beta}}

, normalised by the training-window minimum

c

, for the three disjoint splits;

\hat{\beta}

is fitted on the training split only. An exact power law is a horizontal line. Solid horizontal lines: training envelope

[c,C]

on the window (shaded). Dashed line:

c/2

, which defines the bulk end

m

(dotted vertical line, test split). Values below

0.03

are clipped.

Figure 4: Dependence on patch size (image datasets). (a) Single power-law exponent; bars span the estimates on the three disjoint splits. (b) Broken-law head and tail exponents. (c) Envelope ratio on the test split, over the fitting window and over the bulk

[8,m]

. Dashed horizontal lines in (a,b):

\beta=1

$\beta$	points	used	$\mathrm{TV}/\\|(g_{i})_{i>K}\\|_{2}$	TV/Pinsker
1.25	4779	3242	0.276-0.290	0.78-0.82
1.5	4757	3763	0.276-0.290	0.77-0.81
2	4725	3838	0.276-0.302	0.77-0.81

Appendix

Table 4: Theorem 1 on all truncation curves. Points: evaluated

(\eta,K)

pairs; ratio range over the points with

10^{-5}<\|(g_{i})_{i>K}\|_{2}<\tfrac{1}{2}

and a Monte Carlo signal-to-noise ratio above

5

. No point violates the bounds

\tfrac{1}{100}G_{K}\leq\mathrm{TV}\leq\tfrac{3}{2}G_{K}

or the Pinsker bound.

Figure 5: Theorem 1. (a) Truncation error

\mathrm{TV}(\tilde{q}^{\eta}_{K},q^{\eta})

against

K

for

\beta=1.5

and five resolutions (solid), with the explicit Pinsker bound of Theorem 1(a) (dashed). (b) All points for all

\beta

and

\eta

against the Wiener-gain tail norm; dashed lines are the constants

3/2

and

1/100

of Theorem 1(a). (c) Their ratio, which is constant until the error saturates at one.

$\beta$	$\frac{2}{2\beta-1}$	$1/\varepsilon$	$C_{\mathrm{sp}}/\eta^{2}$	$n$	$1/\varepsilon$	$C_{\mathrm{sp}}/\eta^{2}$	$K_{\varepsilon}/K^{\star}$	$K^{\star}/K_{\rm nec}$	$x_{K^{\star}+1}\sqrt{K^{\star}}/\varepsilon$
		Asymptotic points			$K^{\star}\geq 16k_{\eta}$
1.25	1.333	$1.347\pm 0.005$	$1.340\pm 0.007$	32	1.337	1.333	1.32-1.51	521-528	4.24-4.57
1.5	1.000	$1.005\pm 0.003$	$1.001\pm 0.003$	34	0.997	0.999	1.24-1.33	110-114	4.77-5.21
2	0.667	$0.670\pm 0.002$	$0.669\pm 0.001$	31	0.668	0.668	1.15-1.21	26-26	5.60-6.18

Appendix

Table 5: Theorem 2. Fitted exponents of

1/\varepsilon

and of

C_{\mathrm{sp}}/\eta^{2}

K^{\star}

(joint least squares,

95\%

intervals), over asymptotic points (

4k_{\eta}\leq K^{\star}\leq d/8

) and over

K^{\star}\geq 16k_{\eta}

; sharpness of the sufficient choice

K_{\varepsilon}

of Theorem 2(a) and of the necessary bound

K_{\rm nec}

of Theorem 2(b) (

\varepsilon<1/200

); and the signal-to-noise ratio of the first discarded direction at the required cut,

x_{K^{\star}+1}\sqrt{K^{\star}}/\varepsilon

(Theorem 2(c)).

Figure 6: Theorem 2. (a) Required dimension against accuracy for

\beta=1.5

and five resolutions (markers), with the sufficient choice of Theorem 2(a) (dashed) and the necessary bound of Theorem 2(b) where it applies,

\varepsilon<1/200

(dotted). (b) Required dimension for all settings against the predicted variable; open markers are outside the asymptotic range. (c) Fitted exponents against the prediction

2/(2\beta-1)

Figure 7: (a) Signal-to-noise ratio of the first discarded direction at the required cut, scaled by

\sqrt{K^{\star}}/\varepsilon

(Theorem 2(c)), for all asymptotic points. (b) Error of truncating exactly at the noise level,

K=k_{\eta}

, against

k_{\eta}

(Corollary 1); dotted lines, the guaranteed lower bound. (c) Required dimension for four ambient dimensions; crosses mark

2K^{\star}>d

Rule	Meets	$K/K^{\star}$ : median, range
Noise level, $K=k_{\eta}$	1%	0.034	0.000-1.33
95% variance	36%	0.35	0.002-2,047
99% variance	64%	4.10	0.008-21,479
99.9% variance	90%	30	0.078-47,499
Theorem 2(a), $K_{2\varepsilon}(\eta)$	100%	1.26	1.04-2.00
Tail budget, Theorem 1(a)	100%	1.25	1.00-1.60

Appendix

Table 6: Selection rules over all

(\beta,k_{\eta},\varepsilon)

: share of cases meeting

\mathrm{TV}\leq\varepsilon

(upper end of the Monte Carlo interval), and retained dimension relative to the minimum

K^{\star}

. Variance rules keep the smallest

K

explaining the stated share of

\sum_{i}\sigma_{i}^{2}

; the Theorem 2(a) rule is the smallest

K

whose explicit bound (11) is at most

\varepsilon

; the tail-budget rule is the smallest

K

whose Pinsker bound in Theorem 1(a) is at most

\varepsilon

Figure 8: Selection rules over all

(\beta,k_{\eta},\varepsilon)

. (a) Achieved truncation error relative to the target (values below

10^{-3}

are drawn at

10^{-3}

). (b) Retained dimension relative to the minimum.

$\varepsilon$	$K$	$\sigma^{2}$	$T$	trunc.	$N$	total	$\mathrm{TV}(p,q_{K})$
0.1	320	$1.7\times 10^{-4}$	17.0	0.039	32	0.074	0.78
0.05	640	$6.2\times 10^{-5}$	19.4	0.020	64	0.027	0.63
0.02	1600	$1.6\times 10^{-5}$	22.6	0.008	128	0.010	0.57

Appendix

Table 7: Exact-score sampler in the settings of Theorem 4 (

\beta=1.5

k_{\eta}=16

, Wiener-gain rates). Trunc.: truncation error

\mathrm{TV}(\tilde{q}^{\eta}_{K},q^{\eta})

;

N

: fewest grid steps with total

\mathrm{TV}\leq\varepsilon

; total:

\mathrm{TV}(\tilde{p}^{\eta},q^{\eta})

at that

N

;

\mathrm{TV}(p,q_{K})

: unsmoothed sampling error at that

N

Figure 9: (a) Samplers with perturbed retained variances: total error (markers), truncation error (dashed), and the upper bound of (10) (dotted). (b) Exact-score sampler in the settings of Theorem 4: total error (solid), truncation error (dashed), unsmoothed sampling error (dotted). (c) Steps needed for unsmoothed sampling error

\leq\varepsilon/2

against

K

, for Wiener-gain and equal rates; the dashed line has the slope of the bound of Theorem 3.

$M$	val.	test	EM iter.	val.	test	EM iter.
	CIFAR-10			CIFAR-100
1	0.000	0.000	-	0.000	0.000	-
2	0.294	0.293	16	0.333	0.333	17
4	0.416	0.420	58	0.453	0.452	50
8	0.488	0.493	100 ‡	0.550	0.549	72
16	0.549	0.558	100 ‡	0.611	0.611	100 ‡

Appendix

Table 8: Held-out log-likelihood gain over a single Gaussian (bits per dimension) and number of EM iterations; ‡ iteration cap reached, (

\cdot

) number of reseeded components.

	CIFAR-10	CIFAR-100
pooled $\hat{\beta}$	1.82	1.84
pooled $\hat{C}_{\mathrm{sp}}/\hat{c}_{\mathrm{sp}}$	1.60	1.65
components: $\hat{\beta}_{m}$ , weighted median	2.04	2.00
weighted 10%-90% quant.	1.70-2.27	1.72-2.25
range over components	1.57-2.57	1.56-2.57
weight with $\hat{\beta}_{m}>1$	1.00	1.00

Appendix

Table 9: Power-law fits on ranks

8

48

for the

M=32

mixtures. Weighted quantiles use the mixture weights

\pi_{m}

Figure 10: (a) Held-out log-likelihood gain of the patch mixtures over a single Gaussian. (b,c) Eigenvalues of the

32

component covariances (blue) and of the pooled covariance

\Sigma

(black). The shaded band is the rank window

[8,48]

used for the power-law fits; the dashed line has the fitted pooled slope, shifted vertically for visibility.

Figure 11: Truncation error on CIFAR-10 patches (

M=32

mixture, shared basis); lighter colours are coarser resolutions

k_{\eta}

. (a) Mixture error (solid) and the error predicted by Theorem 1 for the moment-matched Gaussian (dashed). (b) Ratio of the two. (c) Error achieved by six truncation rules (Appendix I.3.5 ), relative to the target

\varepsilon\in\{0.3,0.2,0.1,0.05,0.02,0.01\}

, with the percentage of the 30 (resolution,

\varepsilon

) pairs that meet the target:

K=k_{\eta}

; the smallest

K

keeping

95

99

99.9\%

of the variance; the smallest

K

at which the explicit bound of Theorem 1(a) for

\mathcal{N}(0,\Sigma)

is at most

\varepsilon

(T1(a)); and the smallest

K

at which bound (11) with fitted

(\hat{\beta},\hat{C}_{\mathrm{sp}})

is at most

\varepsilon

(T2(a)). Triangles mark T2(a) choices with

K=d

, i.e. no truncation. CIFAR-100 is in Figure 13 .

				$\varepsilon=0.1$					$\varepsilon=0.01$
$k_{\eta}$	$\eta^{2}/\sigma_{1}^{2}$	$\mathrm{TV}_{\mathrm{NG}}$	$\mathrm{TV}(k_{\eta})$	$K^{\star}$	$K_{\mathrm{G}}$	$K_{\mathrm{T1}}$	$K_{\mathrm{T2}}$	$\bar{K}_{\mathrm{comp}}$	$K^{\star}$	$K_{\mathrm{G}}$	$K_{\mathrm{T1}}$	$K_{\mathrm{T2}}$	$\bar{K}_{\mathrm{comp}}$
2	0.1922	0.039	0.22	6	6	7	9	7.3	35	34	39	46	32.3
4	0.1081	0.064	0.21	10	10	12	13	11.3	47	45	51	71	41.4
8	0.0234	0.199	0.41	31	30	35	40	28.8	84	79	84	192 ∗	67.4
16	0.0102	0.330	0.43	49	46	52	75	41.8	108	97	102 †	192 ∗	82.1
32	0.0025	0.602	0.56	84	78	83 †	192 ∗	66.1	152	128	134 †	192 ∗	107.5

Appendix

Table 10: Retained directions needed on CIFAR-10 patches.

\eta^{2}/\sigma_{1}^{2}

: evaluation level relative to the top pooled eigenvalue.

\mathrm{TV}_{\mathrm{NG}}

: distance

\mathrm{TV}(q^{\eta},\mathcal{N}(0,\Sigma+\eta^{2}I))

between the smoothed mixture and its moment-matched Gaussian.

\mathrm{TV}(k_{\eta})

: error when exactly the directions above the evaluation level are retained.

K^{\star}

and

K_{\mathrm{G}}

: smallest

K

with error at most

\varepsilon

for the mixture and for

\mathcal{N}(0,\Sigma)

K_{\mathrm{T1}}

K_{\mathrm{T2}}

: rules T1(a) and T2(a) of Appendix I.3.5 ; † misses the target, ∗ no truncation (

K=d

\bar{K}_{\mathrm{comp}}

: expected number of retained directions,

\sum_{m}\pi_{m}K_{m}

, when each component uses its own basis with per-component budget

\varepsilon

, which guarantees error at most

\varepsilon

by Proposition 4 (Appendix I.3.6 ). CIFAR-100 is in Table 11 .

Figure 12: Component-basis truncation. (a) Mixture truncation error against the bound of Proposition 4 for all budgets, resolutions and both datasets. (b) CIFAR-10: expected number of retained directions

\sum_{m}\pi_{m}K_{m}

for component bases (solid), and the number

K^{\star}

needed with the shared basis (dashed), as functions of the achieved mixture error.

Figure 13: As Figure 11 , for CIFAR-100 patches.

				$\varepsilon=0.1$					$\varepsilon=0.01$
$k_{\eta}$	$\eta^{2}/\sigma_{1}^{2}$	$\mathrm{TV}_{\mathrm{NG}}$	$\mathrm{TV}(k_{\eta})$	$K^{\star}$	$K_{\mathrm{G}}$	$K_{\mathrm{T1}}$	$K_{\mathrm{T2}}$	$\bar{K}_{\mathrm{comp}}$	$K^{\star}$	$K_{\mathrm{G}}$	$K_{\mathrm{T1}}$	$K_{\mathrm{T2}}$	$\bar{K}_{\mathrm{comp}}$
2	0.1656	0.050	0.24	6	6	8	9	7.5	36	35	40	47	32.6
4	0.1255	0.063	0.16	8	8	10	11	9.1	42	41	46	58	37.0
8	0.0324	0.169	0.29	23	23	27	29	22.5	77	73	78	158	61.0
16	0.0082	0.385	0.46	54	50	56	79	43.6	119	105	110 †	192 ∗	86.2
32	0.0026	0.610	0.53	85	78	83 †	188	64.6	155	132	137 †	192 ∗	107.6

Appendix

Table 11: As Table 10 , for CIFAR-100 patches.

Explore similar work

May 8, 2026cs.LG

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

Diffusion models perform remarkably well on high-dimensional data such as images, often using only a modest number of reverse-time steps. Despite this practical success, existing convergence theory does not fully explain why such samplers remain efficient in high dimensions. Many prior KL guarantees bound the discretization error in terms of the ambient dimension, while other improved results replace this dependence using intrinsic-dimensional or geometric structure assumptions. In this work, we develop an alternative information-theoretic perspective on diffusion sampler convergence. We prove that, for Gaussian mixture targets, the discretization error is controlled by the Shannon entropy of the latent mixture component rather than by the ambient dimension. Consequently, the leading step complexity scales linearly with latent entropy and depends only logarithmically on the second moment of the data. Our analysis also extends to discrete target distributions, where the relevant complexity is the entropy of the target rather than the dimension of the embedding space. These results suggest that diffusion sampling can remain efficient in high-dimensional spaces when the data distribution admits a compact latent representation, as is widely believed to be the case for natural images.

Ahmad Aghapour, Erhan Bayraktar

Department of Mathematics, University of Michigan, Ann Arbor, 48109

Diffusion Sampling

Ask PDF

Oct 8, 2026stat.ML

Diffusion Removes Langevin's Conditioning Dependence: A Sharp Gaussian Analysis

Despite their empirical success, why diffusion models overcome the bottlenecks of classical score-based samplers remains unclear. In this work, we leverage Gaussian distributions to isolate this phenomenon. We establish 2-Wasserstein convergence bounds for optimized hyperparameters, showing that diffusion processes achieve a sampling error of

O(\sqrt{dλ_{\max}}\log N/N)

, where

d

is the dimension,

N

the number of sampling steps, and

λ_{\max}

the largest eigenvalue of the target covariance matrix. Unadjusted and underdamped Langevin dynamics suffer from an additional

\sqrtκ

factor, where

κ

is the condition number. These rates follow from spectral bounds which are sharp: we confirm them via matching first-order asymptotics as

N\rightarrow\infty

. Our analysis provides a rigorous characterization, in the Gaussian setting, of how time-dependent score trajectories remove condition-number dependence during sampling. By contrast, in the learning phase, we show that estimating the unnoised score by gradient descent leads to essentially the same estimator as estimating a noisy score, which suggests that the benefits of noising do not come from the learning phase.

Adam Perbost, Francis Bach, Pierre Marion

Inria, École normale supérieure – PSL Research University Paris, France

Diffusion Sampling Score-Based Generative Modeling Langevin Dynamics

Ask PDF

Apr 12, 2026cs.LG

Query Lower Bounds for Diffusion Sampling

Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for

d

-dimensional distributions, given access to score estimates with polynomial accuracy

\varepsilon=d^{-O(1)}

(in any

L^p

sense), any sampling algorithm requires

\widetildeΩ(\sqrt{d})

adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over

\widetildeΩ(\sqrt{d})

distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.

Zhiyang Xun, Eric Price

UT Austin

Query Complexity Diffusion Sampling Information-Theoretic Lower Bounds Diffusion Models

Ask PDF