REVIEW 2 major objections
Computational bottlenecks for denoising diffusions
T0 review · 2 major / 0 minor · reviewed 2026-05-23 · grok-4.3
Pith's one-line read Denoising diffusions fail to sample some distributions that are otherwise easy to sample from.
desk verdict The paper gives a conditional separation: an easy-to-sample distribution where diffusion drifts that are superpolynomially close to the best poly-time one still produce bad samples, but only assuming a standard info-comp conjecture. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
A reduction that encodes a hard statistical estimation task into the score function of the diffusion process for a carefully chosen distribution.
What would settle it
A polynomial-time algorithm that learns a drift sufficiently close to the optimum for the paper's constructed distribution, such that the generated samples are close in distribution to the target, would falsify the underlying conjecture.
Extended reading notes
Core claim
For a specially constructed probability distribution μ, sampling is tractable by other means, but the drift of the associated denoising diffusion cannot be learned in polynomial time under a common conjecture on statistical estimation. Moreover, there exist drifts that are superpolynomially close to the optimum among all polynomial-time computable drifts, yet the distribution of the samples they generate remains far from μ.
Load-bearing premise
The conjecture that certain statistical estimation problems cannot be solved by any polynomial-time algorithm holds for the distribution constructed in the paper.
Editorial extensions
If this is right
- Denoising diffusion sampling can require superpolynomial computation even when other sampling methods succeed in polynomial time.
- Near-optimal solutions to the score-matching objective can still produce samples whose law is far from the target distribution.
- The gap between information-theoretically optimal drifts and those learnable in polynomial time can be arbitrarily large in some cases.
- Tractability of sampling from μ does not imply tractability of sampling from μ via a learned diffusion process.
Reading between the lines
- Methods that avoid explicit drift learning, such as direct samplers or alternative generative models, may be necessary for certain classes of distributions.
- The result raises the question of whether similar computational bottlenecks appear in other score-based or flow-based generative approaches.
- Practitioners might need to verify whether a given target distribution admits an efficiently learnable diffusion drift before relying on the method.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims that there exist distributions μ that admit efficient (polynomial-time) sampling, yet the problem of learning a denoising diffusion drift for μ via score matching is computationally intractable under a popular conjecture on information-computation gaps in statistical estimation. The key technical contribution is a construction of μ together with a family of drifts that are superpolynomially close (in the relevant norm) to the best polynomial-time drift, yet whose induced output distributions remain bounded away from μ in total variation or Wasserstein distance.
Significance. If the construction and reduction hold, the result would provide conditional evidence of a separation between tractable sampling and tractable diffusion-based sampling, with implications for the scope of denoising diffusion models. The linkage to information-computation gap conjectures is a positive aspect of the work. No machine-checked proofs or reproducible code are mentioned.
major comments (2)
- The central hardness claim (abstract and presumably the main theorem) is routed entirely through an external conjecture on information-computation gaps rather than a self-contained reduction; the superpolynomial closeness and intractability statements are therefore conditional. The manuscript should state the precise conjecture, the reduction, and the quantitative dependence of the superpolynomial gap on the conjecture parameters.
- Abstract: no derivation details or explicit construction of μ or the family of drifts are provided. Without these, it is impossible to verify that the exhibited drifts are indeed superpolynomially close while producing output distributions bounded away from μ.
Simulated Author's Rebuttal
We thank the referee for their careful reading and constructive feedback. Below we respond point-by-point to the major comments.
read point-by-point responses
-
Referee: The central hardness claim (abstract and presumably the main theorem) is routed entirely through an external conjecture on information-computation gaps rather than a self-contained reduction; the superpolynomial closeness and intractability statements are therefore conditional. The manuscript should state the precise conjecture, the reduction, and the quantitative dependence of the superpolynomial gap on the conjecture parameters.
Authors: We agree that the result is conditional on the conjecture and that greater explicitness would strengthen the presentation. In the revised manuscript we will (i) quote the precise statement of the information-computation gap conjecture employed, (ii) spell out the reduction from the conjectured hard estimation problem to the task of learning a polynomial-time diffusion drift, and (iii) state the quantitative dependence of the superpolynomial separation on the conjecture parameters. These additions will be placed in the introduction and in the statement of the main theorem. revision: yes
-
Referee: Abstract: no derivation details or explicit construction of μ or the family of drifts are provided. Without these, it is impossible to verify that the exhibited drifts are indeed superpolynomially close while producing output distributions bounded away from μ.
Authors: Abstracts are intentionally concise high-level summaries and do not contain full derivations; this is standard practice. The explicit construction of the distribution μ, the family of candidate drifts, the proof that they are superpolynomially close to the optimal polynomial-time drift in the relevant norm, and the demonstration that the induced output distributions remain bounded away from μ in total variation (or Wasserstein) distance are all contained in the main body of the paper. We therefore do not believe additional technical content belongs in the abstract itself. revision: no
Circularity Check
No circularity; central claim conditional on external conjecture
full rationale
The paper's derivation establishes an intractability result for drift learning conditional on a popular external conjecture regarding information-computation gaps in statistical estimation. This conjecture is invoked as an assumption rather than derived or fitted within the paper, and the construction of the distribution μ and the superpolynomial closeness of drifts are presented as consequences under that assumption. No self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations appear in the provided abstract or reader's summary. The result is therefore self-contained against the stated external benchmark and does not reduce to its own inputs by construction.
Assumptions & free parameters
assumptions (1)
- domain assumption A popular conjecture on information-computation gaps in statistical estimation holds.
Cite this review
Pith. "Pith review of Computational bottlenecks for denoising diffusions." pith.science (2026). https://pith.science/paper/2503.08028
@misc{pith2026250308028,
author = {Pith},
title = {Pith review of: Computational bottlenecks for denoising diffusions},
year = {2026},
howpublished = {\url{https://pith.science/paper/2503.08028}},
note = {Machine review of arXiv:2503.08028}
}
abstract
Denoising diffusions sample from a probability distribution $\mu$ in $\mathbb{R}^d$ by constructing a stochastic process $({\hat{\boldsymbol x}}_t:t\ge 0)$ in $\mathbb{R}^d$ such that ${\hat{\boldsymbol x}}_0$ is easy to sample, but the distribution of $\hat{\boldsymbol x}_T$ at large $T$ approximates $\mu$. The drift ${\boldsymbol m}:\mathbb{R}^d\times\mathbb{R}\to\mathbb{R}^d$ of this diffusion process is learned my minimizing a score-matching objective. Is every probability distribution $\mu$, for which sampling is tractable, also amenable to sampling via diffusions? We provide evidence to the contrary by studying a probability distribution $\mu$ for which sampling is easy, but the drift of the diffusion process is intractable -- under a popular conjecture on information-computation gaps in statistical estimation. We show that there exist drifts that are superpolynomially close to the optimum value (among polynomial time drifts) and yet yield samples with distribution that is very far from the target one.
Reviewed May 23, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.