PaperlayerView exact revision on arXiv

Source-linked AI summary

Lower Bounds for Parallel Diffusion Sampling

Yiwen Kou, Yimeng Wang

arXiv:2610.09166v1cs.DScs.AIcs.CCcs.LGstat.ML

TL;DR

Parallel diffusion sampling trades additional score evaluations for fewer sequential rounds, raising the question of how much sequential dependence remains unavoidable. This paper constructs fixed approximate score oracles that enforce access to hidden information in sequence. It proves polynomial round lower bounds for near-isotropic Gaussian mixtures and anisotropic boxes, with a matching linear upper bound for the box family.

  • Problem

    How many sequential rounds are necessary for diffusion sampling when algorithms can make polynomially many score queries in each round?

    Source: §1 · p. 3

  • Method

    The authors construct fixed approximate score oracles that hide information in ordered blocks and reveal later blocks only through queries consistent with earlier ones.

    Source: §1 · p. 3, §5 · p. 15

  • Results

    The lower bounds are Ω~(d^1/3) rounds for smooth near-isotropic Gaussian mixtures and Ω(d) for anisotropic boxes, whose family also has an O(d)-round recovery algorithm.

    Source: §1.1 · pp. 4–5

  • Takeaways & Limitations

    Even with polynomially many arbitrary-location and noise-level queries per round, approximate-score sampling can require polynomially many adaptive rounds.

    Source: §1 · p. 3, §1.1 · p. 4

    For near-isotropic mixtures, a polynomial gap remains between the Ω~(d^1/3) lower bound and the Ω~(d^5/6) sequential upper bound.

    Source: §5 · p. 15

Abstract

from arXiv · show

Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds. This raises the question of how much sequential dependence is unavoidable, even when many score queries can be made simultaneously. We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores. Specifically, we prove (1) a $\widetilde{\Omega}(d^{1/3})$-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in $R^d$, and (2) an $\Omega(d)$-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. The linear bound is tight for our box family. Our constructions use fixed approximate score oracles that enforce sequential access to hidden information while satisfying the accuracy guarantee at every noise level.

1 Introduction

The paper asks how many sequential rounds diffusion sampling requires when algorithms can batch polynomially many score queries, and proves polynomial round lower bounds with approximate scores. Its constructions enforce sequential access to hidden information, yielding a near-isotropic Gaussian-mixture bound and a tight linear bound for an anisotropic box family.

1 Introduction

  • Parallel samplers trade additional model evaluations for fewer sequential rounds, motivating the question of how many rounds remain necessary with polynomially many evaluations per round.Standard DDPM and DDIM implementations use each update to choose the next evaluation input.Source: §1 · p. 3

1.2 Related work

  • Existing parallel guarantees rely on quantitative score regularity or other assumptions beyond mean-square score error alone, leaving parallel complexity under that guarantee open.Prior sequential results for general targets often concern Gaussian-smoothed distributions or require additional conditions for strong-metric guarantees on unsmoothed targets.Source: §1 · p. 3, §1.2 · p. 5

1 Introduction

  • The oracle model permits queries at arbitrary locations and noise levels, while algorithms choose each batch before seeing its answers and may adapt later batches to previous answers.The score guarantee is mean-square error under the noisy target distribution, reflecting the distributional objective used to learn scores.Source: §1 · pp. 3–4, §1.1 · p. 4

1.1 Main results

  • Sampling requires Ω~(d^1/3) rounds for smooth near-isotropic Gaussian mixtures and Ω(d) rounds for anisotropic boxes; O(d) rounds match the box lower bound for this family.The results apply to sampling the target within total variation error 1/10.Source: §1.1 · pp. 4–5
  • Fixed approximate score oracles reveal later blocks only when queries pass consistency tests involving earlier blocks, so each batch exposes at most one additional block.At every noise level, the oracle can suppress information on atypical queries while remaining accurate under the smoothed target distribution.Source: §1 · p. 3, §1.1 · p. 4
  • Ordered codebook sizes fit eΘ(d^1/3) successive barriers while preserving near-isotropy in the Gaussian-mixture construction.After a fixed public rescaling, the targets have mean norm o(1) and covariance within o(1) of the identity in operator norm.Source: §1.1 · p. 4
  • For boxes, geometrically decreasing coordinate scales yield d barriers, but the candidate intervals are public while their selected locations are hidden.The boxes lie in the unit ball and are substantially anisotropic.Source: §1.1 · p. 5

2 Preliminaries

The preliminaries define the paper’s distribution, smoothing, score, and norm notation, then formalize approximate score oracles and adaptive parallel-query algorithms. They also specify how sampling success is measured against the target distribution.

Notation and distributions

  • The paper uses Unif(S) for the uniform law on a finite set, Unif(K) for normalized Lebesgue measure, and L(X) for the law of X.It defines Euclidean, operator, and Frobenius norms, and describes near-isotropy through the mean and covariance deviation from the identity.Source: §2 · p. 6

Gaussian smoothing and scores

  • Gaussian smoothing defines π(σ) as the law of Y + σZ, and its score is the gradient of the log density of that smoothed target.The score is defined at every query point; smoothing preserves product structure, and total noise for an already-smoothed target satisfies τ^2 = γ^2 + σ^2.Source: §2 · pp. 6–7
  • Tweedie’s formula relates the score at a query point to a posterior mean, with the posterior formed by weighting the target law by the Gaussian likelihood.The identity holds at every point, not merely almost everywhere.Source: §2 · p. 6

Approximate oracles and parallel rounds

  • A legal approximate score oracle is fixed for the target and interaction, with mean-square error measured under the true noisy target at each noise level.No pointwise accuracy, spatial Lipschitz bound, or representation as another density’s score is required; a lower bound may choose a particular legal oracle for each target.Source: §2 · p. 7
  • Each adaptive round submits a batch of queries before receiving answers, while later batches may depend on the preceding transcript; success is measured by total variation from the target itself.Queries may use arbitrary locations and noise levels, and computation between rounds is unrestricted.Source: §2 · p. 7

3 Parallel lower bounds for near-isotropic targets

This section studies parallel sampling for constructed near-isotropic targets, using gated approximate-score oracles to hide codebook information and establish a d^(1/3)-scale round lower bound. It also gives an accuracy-matched sampler using eO(d^5/6) score queries, after verifying denoiser regularity.

3 Parallel lower bounds for near-isotropic targets

  • The approximate oracle gates each block’s score on a test of the preceding block, returning a null score when an earlier gate is closed while satisfying the required score-error guarantee.This makes access to later blocks depend on supplying a point that passes the earlier-block test.Source: §3 · pp. 8–9

3.1 Only one additional block per round

  • A parallel batch reveals information about at most one additional codebook, even when its queries use different noise levels.Sparse blocks tend to close their gates, while sufficiently dense later blocks return null scores; the resulting simulation after R rounds depends only on the first R codebooks.Source: §3.1 · p. 10

3.2 An unseen block gives a TV gap

  • An unseen block distinguishes genuine samples from the sampler’s output: genuine samples pass its test with probability at least 0.999, whereas points independent of its codebook rarely pass.The construction conditions on near-isotropy and preserves total variation under its fixed public rescaling, yielding the claimed lower-bound guarantee.Source: §3.2 · pp. 11–12

3 Parallel lower bounds for near-isotropic targets

  • The sampler-independent hard-instance distribution is supported on near-isotropic targets with legal oracles; with B^3 log d ≲ d, the stated parameter choice is the origin of exponent 1/3.Any sampler for the rescaled targets induces one for the original targets with the same query and round budgets, and invertible rescaling preserves total variation.Source: §3.2 · p. 12, §3.3 · p. 12

3.3 Why the exponent is 1/3

  • The exponent arises by spacing block codebook sizes by about √m log d and fitting B such levels into d coordinates, which requires B^3 log d ≲ d.The logarithmic spacing makes failure probabilities small enough for polynomially many queries and accommodates inverse-polynomial oracle accuracy.Source: §3.3 · p. 12
  • Together with the total variation gap, this establishes Theorem 3.1.Source: §3.3 · p. 12
  • Every target in the constructed family can be sampled to total variation error at most 1/10 with eO(d^5/6) score queries, one per round, for every fixed legal oracle.This is the upper bound for the same family used in the lower-bound analysis.Source: §3.3 · p. 12
  • The proof verifies the denoiser’s required regularity conditions before specializing the sampling guarantee from.Appendix A.6 contains the complete error and query bounds.Source: §3.3 · p. 12

4 Linear parallel-round lower bounds for anisotropic boxes

The section proves a linear parallel-round lower bound for sampling uniform distributions over a constructed family of anisotropic boxes, and gives a matching-round upper bound. Its construction uses hidden interval labels and a fixed gated approximate oracle to enforce sequential information access.

Linear parallel-round lower bound

  • Ω(d) rounds are necessary for some uniform distributions over full-dimensional axis-aligned boxes contained in the unit ball.The lower bound applies to randomized samplers using fewer than d rounds with a fixed legal approximate oracle.Source: §4 · p. 13

Construction

  • The construction assigns each coordinate a hidden interval label, with candidate intervals at rapidly decreasing scales, making the resulting boxes substantially anisotropic.The candidate intervals are public, but their selected labels and any interior point are not supplied.Source: §4 · p. 13, Figure 2 · p. 14

Approximate oracle

  • A fixed gated approximate oracle reveals later-coordinate corrections only when earlier-coordinate consistency tests pass, and satisfies the score-error guarantee at every noise level.At sufficiently high noise levels, later corrections are discarded; at lower levels, gates test proximity to the selected earlier interval.Source: §4 · pp. 13–14

Lower-bound argument

  • With fewer than d rounds, a sampler’s output can be coupled to one depending only on its seed and the first R hidden labels, leaving the next label unrevealed.The proof uses this one-new-coordinate-per-round property to bound the probability that the output lies in the hidden box.Source: §4 · p. 14

Matching upper bound

  • O(d) rounds and O(log d) queries per round suffice to sample every target in the constructed family to total variation error at most 1/10.The sampler recovers selected intervals one coordinate at a time, then samples uniformly from their product.Source: §4 · p. 15

5 Conclusion and future directions

The paper establishes polynomial parallel-round lower bounds for approximate-score diffusion sampling and describes open questions about their tightness, geometric scope, and oracle models. The near-isotropic Gaussian-mixture bound remains separated from the cited upper bound, while the box construction relies on strong anisotropy.

Tightening the near-isotropic bounds

  • For near-isotropic Gaussian mixtures, an eΩ(d1/3) lower bound leaves a polynomial gap to the eO(d5/6) upper bound obtained by specializing.The cited upper bound uses a sequential algorithm; the paper raises whether parallel queries or a sharper lower-bound construction can close the gap.Source: §5 · p. 15

Near-isotropic convex bodies

  • The linear lower bound for uniform sampling from convex bodies uses strong anisotropy, leaving open whether polynomial round lower bounds hold for near-isotropic convex bodies.The paper frames this as a question about whether convexity and near-isotropy together suffice for efficient parallel sampling in this model.Source: §5 · p. 15

Sequential and parallel lower bounds

  • Whether sequential query lower-bound techniques can yield comparable parallel-round lower bounds for near-isotropic targets remains open.The discussion points to the eΩ(d1/2) sequential query lower bound of and the counting-oracle setting.Source: §5 · p. 15

Other oracle models

  • The paper leaves open whether polynomial parallel lower bounds hold for exact scores or approximate scores with uniform pointwise guarantees at every noise level.It also asks about round complexity for convex-body membership queries and approximate first-order queries for log-concave distributions.Source: §5 · p. 15

A Deferred proofs from Section 3

This appendix supplies deferred proof details and shared notation for the constructions in Section 3. It specifies the block and codebook parameters, noise conventions, and polynomial accuracy and query-budget conventions.

Shared notation and instance law

  • The appendix identifies d as ambient dimension, B as the number of hidden blocks, and m = ⌊d/B⌋ as their common dimension.It also defines padding coordinates and the codebook sizes and rates.Source: A Deferred proofs from Section 3 · p. 20
  • The noise notation distinguishes additional query noise σ from total noise τ, with the target at τ = γ.The instance uses independent codebooks, each uniformly chosen among subsets of its prescribed size.Source: A Deferred proofs from Section 3 · p. 20

Polynomial bounds

  • The proof conventions fix a public polynomial query budget and inverse-polynomial score accuracy before choosing the instance family.The failure tolerance is likewise bounded below by an inverse polynomial.Source: A Deferred proofs from Section 3 · p. 20

A.1 Parameters and near-isotropy

The appendix chooses public block and codebook parameters to construct near-isotropic targets, then records technical inputs used in the proofs. The construction’s target instances are near-isotropic with high probability, and the technical inputs include Gaussian-smoothing estimates and a without-replacement adaptation from.

A.1 Parameters and near-isotropy

  • B can be chosen on the order of (d/log d)^(1/3), with block dimension m = ⌊d/B⌋ and public codebook sizes chosen to create separated rates.The parameter choices are independent of the algorithm and sampled codebooks.Source: §A.1 · pp. 20–21
  • The selected target mixtures have near-zero mean and covariance close to identity with probability at least 1 − exp(−Ω(m)).The construction uses codebooks sampled independently as uniform subsets of the Boolean cube.Source: §A.1 · pp. 21–22

A.2 Technical inputs from [XP26]

  • The appendix uses Gaussian-smoothing identities and a KL–Fisher comparison from, and proves a without-replacement adaptation of an lemma.The listed analytic estimates apply at positive noise levels, including levels below γ where noted.Source: §A.2 · pp. 23–24

A.3 Proof of Lemma 3.2

The construction uses fixed, blockwise approximate score oracles whose responses depend on prefix gates. Their error remains controlled across noise levels, while dependence on earlier gates makes later-block information sequentially accessible.

A.3 Proof of Lemma 3.2

  • At fixed total noise τ, the oracle uses either a null score, with expected squared error at most η²/(4τ²), or an exact local score, whose error arises only if an earlier gate fails.In the exact-score branch, the squared error norm is at most 4m/τ⁴ and is zero when every preceding gate equals one; the probability that any such gate fails is at most (j−1)ζ(τ).Source: §A.3 · pp. 25–26
  • For each fixed codebook, the gate-completeness estimate and the continuity of the mixture scores and gates support a fixed oracle construction across positive noise levels.The response switch itself need not be continuous in noise.Source: §A.3 · pp. 25–26
  • At each fixed noise level, the constructed oracle is spatially Lipschitz, although spatial Lipschitzness is not an assumption of the oracle model.The stated full-dimensional bound is Lip(bs_Sτ) ≤ τ^-2 + 4dτ^-4.Source: §A.3 · p. 26

A.4 Proof of Lemma 3.3

The proof combines codebook hiding estimates with a progressive coupling: each batch is unlikely to distinguish the full oracle from one truncated at the first unknown block. This makes the simulated interaction depend only on the codebooks exposed in earlier rounds.

A.4 Proof of Lemma 3.3

  • For algorithms with fewer than B rounds, the coupled simulated transcript and output depend only on the random seed and the first R codebooks.The coupling bounds the probability that the actual transcript or output differs from the simulation; the stated parameter choice makes this probability small.Source: §A.4 · pp. 27, 29
  • The codebook estimates combine sparse hiding with dense null responses to control the chance that queries reveal information from unknown blocks.The null-response event can mean equality of the oracle response functions, not merely equality at one query point.Source: §A.4 · pp. 27–28
  • A batch of at most P queries differs between the full and r-truncated oracles with probability at most PBδ, even when queries use different noise levels.Conditioning on the prefix and seed fixes the batch while leaving the suffix codebooks independent; no discretization of noise levels is needed.Source: §A.4 · p. 28
  • Progressive simulation turns the fixed-batch indistinguishability bound into an adaptive one, with transcript and output disagreement probability at most Rδbatch.The simulated interaction in round r uses the oracle truncated at r, so its transcript depends only on the seed and the first r coordinates.Source: §A.4 · p. 29

A.5 Proof of Lemma 3.4

A target-level test identifies a high-probability region for each fixed codebook that an algorithm's output is unlikely to reach if it has not exposed the corresponding hidden block. Averaging the resulting total-variation separation yields the lower-bound argument.

Every fixed codebook satisfies

  • The target-level test is evaluated at noise γ, where the gate-completeness estimate gives high target probability for the codebook-specific region.For a random codebook, an independent point lands in the associated region with probability at most e^-c0m.Source: Every fixed codebook satisfies · pp. 29–30
  • For algorithms using R < B rounds, an unseen block yields a total-variation separation between the target and the algorithm's output law.The test region has target mass at least 1 − ζ(γ), while its output probability is bounded by e^-c0m + RPBδ.Source: Every fixed codebook satisfies · p. 30
  • The proof averages the fixed-instance total-variation inequality over the instance law, although the test region need not be available to the algorithm.The prescribed codebook rates are necessary for the stated failure bounds; the result does not cover arbitrary subsets of the full cube.Source: Every fixed codebook satisfies · p. 30

A.6 Proof of Lemma 3.5

The appendix gives an upper-bound comparison for the Gaussian-mixture family and supplies deferred construction details for the box family. The box gates use public candidate intervals with hidden labels and noise-dependent cutoffs.

A.6 Proof of Lemma 3.5

  • With inverse-polynomial score accuracy, the Gaussian-mixture family admits an eO(d^5/6)-query sampler with total variation error 1/10, and the sampler may use one query per round.The sampler has a worst-case query bound; the estimate for the true denoiser supplies the family-specific regularity used in the cited sampling guarantee.Source: §A.6 · pp. 30–32

B.1 Public parameters and gates

  • The box construction uses public parameters and candidate intervals, with only the coordinate labels hidden; its gates depend on spatial scales and noise cutoffs.The construction is deliberately anisotropic, and the intervals are arranged within [a_i, 2a_i] with center spacing a_i/M = 100h_i.Source: §B.1 · pp. 32–33

B Deferred proofs from Section 4

  • The box family is full-dimensional and contained in the unit ball, while low-noise gate-positive regions for distinct candidate intervals are disjoint.For a genuine noisy sample, the gate failure probability is at most 2e^(-25d^2/8) at the stated noise levels.Source: §B.1 · pp. 32–33

B.2 Proof of Lemma 4.2

The proof constructs a fixed, jointly measurable oracle from gated posterior means and shows it satisfies the score-error guarantee for every instance and noise level. The error analysis also holds as the noise level tends to zero.

B.2 Proof of Lemma 4.2

  • Posterior means of the uniform intervals provide continuous coordinate estimates that remain within their respective intervals.The construction combines them with gates and cutoff indicators.Source: §B.2 · p. 33
  • The fixed oracle is jointly measurable and satisfies the score-error guarantee for every instance and every σ > 0.Its construction is fixed before interaction and legal at accuracy εscore.Source: §B.2 · pp. 33–34
  • The proof bounds inactive-coordinate error and active-coordinate error when preceding gates fail, then sums those contributions.For active coordinates, error vanishes if all preceding gates equal one.Source: §B.2 · pp. 33–34
  • The error bound retains its dependence on σ, so the guarantee continues to apply as σ tends to zero.Source: §B.2 · p. 34

B.3 Proof of Lemma 4.3

The proof compares the actual oracle interaction with a progressive simulation that reveals hidden labels one at a time. With fewer than d rounds, their transcripts disagree with probability at most RP/M, enabling the probability lower-bound argument.

B.3 Proof of Lemma 4.3

  • The progressive interaction exposes at most one additional label per round and its transcript and output depend only on the first R labels and the seed.Source: §B.3 · p. 34
  • For R < d rounds and at most P queries per round, the actual and progressive transcripts disagree with probability at most RP/M.The bound also applies to their outputs when both interactions use the same instance and random seed.Source: §B.3 · p. 34
  • Within each batch, any query disagrees with the truncated oracle with conditional probability at most 1/M, yielding a batch bound of P/M.The argument applies separately to queries at different noise levels.Source: §B.3 · p. 34
  • Disjoint candidate intervals and Markov's inequality are used to turn the coupling bound into the claimed probability lower bound.Source: §B.3 · p. 35

B.4 Proof of Lemma 4.4

The proof gives an O(d)-round algorithm that recovers all box labels, and therefore samples the box within total variation error 1/10. It refines one coordinate at a time using batches of approximate-score queries, for any fixed legal oracle of the stated accuracy.

B.4 Proof of Lemma 4.4

  • O(d) rounds and O(log d) queries per round suffice to recover all labels with probability at least 9/10 and sample within total variation error 1/10.The result holds for every instance and every fixed legal oracle of accuracy εscore.Source: §B.4 · pp. 35–36
  • Each refinement uses median estimates from independent queries at noise level σ = 4r to update the current center estimate.Source: §B.4 · p. 35
  • The algorithm processes coordinates in order, refining each center estimate with L = O(1) rounds of queries.It starts with b0 = 3ai/2 and r0 = ai; each refinement uses a batch of N = O(log d) queries.Source: §B.4 · pp. 35–36
  • After refinement, the algorithm decodes the label whose public center is nearest to the estimate; successful refinements identify the correct label.Distinct candidate centers are 100hi apart, and the prescribed radii shrink to at most hi.Source: §B.4 · p. 36
  • Fresh uniform coordinates from the decoded box couple to a true-box sample whenever every label is correct.Source: §B.4 · pp. 35–36
Loading 2610.09166v1…