acceptodds
Under review as a conference paper at ICLR 2027

HIGH-ACCURACY PARALLEL DIFFUSION SAMPLING: NEAR-LINEAR QUERIES AND SQUARE-ROOT DEPTH

Abstract

Standard diffusion samplers are sequential: every denoiser call depends on the previous state. Parallel proposals reduce this dependency, but at high accuracy they can require far more denoiser calls. We give a parallel sampler with near-linear query complexity under only a finite-second-moment assumption. For any zero-mean distribution on with a known second-moment bound and exact access to its Gaussian posterior mean, the sampler uses expected full-vector queries and expected adaptive rounds. We use Euler discretization only for parallel proposals and correct them by rejection sampling against the high-accuracy FORS diffusion path of Chen et al. (2026). We introduce a mechanism we call a causal guard to handle rare, large changes in the diffusion drift. Compared with the recursive parallel result of Anari et al. (2026), this removes bounded support and replaces polynomial dependence on accuracy, smoothing, and support radius with polylogarithmic dependence.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
parallel Diffusion sampling, high-accuracy sampling, rejection sampling

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_MEHXOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a high-accuracy parallel diffusion sampling algorithm with theoretical guarantees. By combining FORS with the existing parallel sampling method of Anari et al. and introducing an additional mechanism (causal guard), the authors achieve nearly linear query complexity and square-root adaptive depth.

Critical strengths

This paper addresses an important limitation of the existing parallel sampling method (Anari et al.), namely, the polynomial dependence of the expected query complexity on the accuracy parameter ε\varepsilon.

Critical weaknesses
  • It is unclear whether the proposed algorithm can reduce inference time in practical settings.
  • The proposed algorithm lacks experimental validation.
Questions for authors

No questions.

Reviewer_eDiWOpenReview ↗
Rating
2(−1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Assuming exact access to the posterior mean and only a finite second moment, the paper gives a parallel diffusion sampler that reaches ε\varepsilon total-variation accuracy with O~(n)\tilde{O}(n) expected queries and O~(n)\tilde{O}(\sqrt{n}) expected adaptive rounds, by placing the high-accuracy FORS path [2] inside the autospeculation framework of [1] and adding a "causal guard" that replaces the bounded-support assumption of [1].

Critical strengths
  1. The paper removes the bounded-support assumption of [1] and improves the query complexity from polynomial to polylogarithmic in the accuracy

  2. The causal guard is a clean technical idea for controlling drift changes on the sampled path without support or smoothness assumptions.

Critical weaknesses
  1. The contribution is incremental. The recursive framework and the n\sqrt{n} depth come from [1] and the target path from [2]; the improvement is in the number of queries, not in depth.

  2. Table 1 omits parallel samplers that reach polylogarithmic depth under smoothness assumptions [3], and it does not include sequential FORS [2], whose depth is already no worse than n\sqrt{n} when the intrinsic dimension is at most n\sqrt{n}.

  3. The analysis requires an exact denoiser, whereas [1] tolerates approximate ones, and all bounds hold only in expectation; turning them into fixed-depth guarantees by standard truncation would reintroduce a polynomial dependence on 1/ε1/\varepsilon.

Missing citations: [4].

[1] Parallel Sampling via Autospeculation. STOC 2026.

[2] High-Accuracy Sampling for Diffusion Models and Log-Concave Distributions. ICML 2026.

[3] Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel. ICLR 2025.

[4] The Adaptive Complexity of Parallelized Log-Concave Sampling. ICLR 2025.

Questions for authors
  1. How large are the constants of the algorithm in practice? Could the authors illustrate the predicted trade-off between queries and depth on a case where the exact posterior mean is available, such as a Gaussian mixture?
1 comment
Reviewer_eDiWOpenReview ↗

Score updated

As reflected in my confidence rating, I do not work directly on the topic of this paper. Having read the discussion with Reviewer n4Do, I am lowering my score to 2 for now. I would welcome the authors’ response to the points raised in my review and will reconsider my score in light of it.

Reviewer_n4DoOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes a parallel diffusion sampler with an exact posterior-mean oracle, claiming near-linear expected queries and square-root expected adaptive rounds in the dimension under only a finite second moment. It corrects parallel Euler proposals toward the FORS transition of Chen et al. (2026) using recursive rejection, with a new “causal guard” to control drift variation.

Critical strengths

(1) The paper proves a new result for parallel diffusion.

(2) The proof has been formally verified in Lean.

Critical weaknesses

(1) The motivation of the paper is ambiguous. Many concepts, such as “neural evaluations” “noisy level” “denoiser query at the next” “oracle model” “different resources” “while worsening the other”, are not well defined and explained. Therefore, it’s hard to understand what tradeoff the paper is going to study.

(2) Many key ingredients are not well motivated. Why early-stopped diffusion? Directly introducing the content of the theorem is not helpful. Before that, introduce the motivation first. The introduction of function ff comes from nowhere, the same is for the introduction of FORS. We do not know what problem the paper is going to solve, and why FORS can help. In this sense, the three ingredients are not helpful for readers.

(3) The algorithm is never introduced before the main theorem. Section 2.1 starts with “the proof”, but it is never clear what will be proved. Because of this, Section 2 is almost impossible to read, including the two figures which do not show the reason to place them there.

(4) There is no comparison with prior work, including the settings and results. This makes it hard to place the work in the literature.

(5) The paper only contains 7 and a half pages of main contents. There is enough room for a clear description of the main algorithm, including the motivation and design.

Questions for authors

See weaknesses

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.