acceptodds
Under review as a conference paper at ICLR 2027

Uniform Discrete Diffusion Models Are Minimax Optimal for Estimating Distributions with Small Effective Support Size

Abstract

Discrete diffusion models have emerged as a practically successful framework for generative modeling on discrete product spaces, yet their statistical generalization properties remain poorly understood. Discrete real-world data such as text or biological sequences often concentrate on a small fraction of the astronomically large ambient space because of semantic or physical constraints, but existing bounds fail to capture this distributional structure and instead scale with the size of the ambient space, giving rise to almost vacuous error bounds. We address this gap for uniform discrete diffusion, one of the two dominant discrete diffusion paradigms alongside masking diffusion, by deriving statistical guarantees governed by the effective support size, a sample-size-dependent measure of distributional complexity. Given independent and identically distributed (i.i.d.) samples from an unknown data distribution on , we show that, with appropriate choices of network size and hyperparameters, the expected total variation (TV) loss scales as , while the expected Kullback–Leibler (KL) divergence is bounded by . Furthermore, we show that the TV rate is minimax optimal and that the KL rate is minimax optimal up to a factor of . Together, these upper and lower bounds show that uniform discrete diffusion successfully avoids the curse of dimensionality for distributions with small effective support size: the TV error rate depends on the ambient state-space size only through , while the corresponding KL rate incurs only an additional logarithmic dependence on the ambient state-space size.

Primary area:
learning theory
Keywords:
discrete diffusion models, uniform discrete diffusion, distribution estimation, effective support size, generalization bounds, minimax rates

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_doFUOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the sample complexity of estimating a discrete distribution supported on [K]d[K]^d with uniform discrete diffusion model, where the effective support size sn(P0)=∑x∈[K]dmin⁡(nP0(x),1)s_n(P_0)=\sum_{x \in [K]^d} \min (nP_0(x),1) serves as a distribution-dependent measure of the problem complexity. For fixed-grid samplers satisfying a standard assumption on the entropy loss used for training the discrete diffusion model, the authors obtain an expected TV rate of magnitude O(sn(P0)/n)O(\sqrt{s_n(P_0)/n}) and an expected KL rate of magnitude O((sn(P0)/n)log⁡(eKd/sn(P0))log⁡n)O((s_n(P_0)/n)\log(eK^d/s_n(P_0))\log n). (Almost) matching minimax lower bounds are also provided to show optimality of uniform discrete diffusion models in terms of both TV and KL divergences (up to a negligible log⁡n\log n factor). The paper also gives an exact one-step empirical reverse sampler and controlled SEDD experiments to support interpretation of the effective-support size.

Critical strengths

Firstly, the reviewer finds the statistical theory presented in this paper to fairly strong and rigorous. The formulation based on the effective support size provides substantially sharper guarantees than bounds based on ambient state-space and yields almost matching minimax rates in terms of both TV and KL. I particularly appreciate that the results recover the classical unrestricted rates under the regime n≪Kdn \ll K^d, where the effective support saturates but remains informative. Secondly, results in terms of the KL divergence gives a useful interpretation of discrete diffusion model's generalization capability. The exact one-step construction in the appendix also turns out to be useful as it separates the statistical phenomenon from the unfavorable complexity caused by the fixed-grid implementation.

Critical weaknesses

The first weakness is that the statistical guarantee presented in the paper seems to be derived by the approximation of the empirical diffusion process rather than the generalization property of a realistically trained score network. Specifically, the proof constructs a sufficiently expressive ReLU class that approximates the discrete score function associated with the empirical distribution. The resulting sampler is then compared against the forward empirical measure smoothed by early stopping. This is valid statistically, but it makes the headline statement that ``uniform discrete diffusion models are minimax optimal'' a little bit stronger.

Secondly, the KL fixed-grid construction is not computationally meaningful in high dimension, and the experiment only validates the theory in an indirect way. As the authors describe in the paper, the explicit KL instantiation requires network width/sparsity and a number of sampling steps with exponential dependence on dd. Appendix D shows that this is not intrinsic to the statistical rate, but it limits the practical interpretation of the fixed-grid result. Empirically, the lower-temperature teacher distributions plausibly have smaller effective support and are learned more accurately, but the experiment does not report sn(P0)s_n(P_0) or DnD_n, nor test the predicted dependence of error on the effective support size directly.

Questions for authors
  1. For the exponential dependence on the dimension dd in the fixed-grid KL case, is the construction primarily an artifact of the KL comparison argument, or is there a plausible route to a guarantee of polynomial complexity in terms of dd? The efficient one-step construction suggests that the such exponential dependence on dd may be an upper bound that is too loose.

  2. Would it be possible for the authors to report the number of distinct observations DnD_n or an estimate for the parameter sn(P0)s_n(P_0) for each population and training-set size in the experiments? This would make the empirical study connect more directly to the theory.

3 comments

We sincerely thank the reviewer for recognizing the statistical significance of our effective-support framework and the usefulness of our one-step sampler, as well as for their constructive suggestions. These motivated additional empirical evaluations, including a controlled synthetic experiment whose pilot results support our theory.

Weakness 1

Our main contribution is a finite-sample analysis connecting empirical score-entropy minimization, neural score approximation, and reverse sampling to minimax TV and near-minimax KL guarantees for uniform diffusion. Classical optimal estimators do not imply these guarantees for diffusion models. Our rates depend on sn(P0)\mathfrak{s}_n(P_0) and can remain informative when n≪Kdn\ll K^d, where ambient-cardinality-based bounds become vacuous. The empirical distribution and its forward-smoothed counterpart serve as intermediate estimators, rather than constituting our main contribution.

Our results hold under explicit sufficient conditions on the network class, optimization error, and sampler, rather than claiming unconditional optimality for practically trained networks. Nevertheless, the synthetic pilot described under Question 2 provides preliminary evidence that trained SEDD follows the theoretical rate. We will clarify the scope of our guarantees in the final draft.

Weakness 2 and Question 1

The exponential architecture, optimization-precision, and sampling-step requirements of our fixed-grid KL theorem are conservative worst-case sufficient conditions, not computational lower bounds. Unlike TV, KL lacks a triangle inequality; transferring sampler accuracy relative to the early-stopped empirical distribution into population KL uses the uniform density floor ((1−e−1/n)/K)d≍(Kn)−d((1-e^{-1/n})/K)^d\asymp(Kn)^{-d}. This leads to exponentially stringent requirements, which have not been established as intrinsic limitations of uniform discrete diffusion under KL loss. Regarding Question 1, our current KL-transfer argument does not establish the near-minimax KL guarantee under polynomially small optimization error, and we could not find a way to remove this exponential dependence. Developing an alternative analysis that achieves comparable guarantees for learned-score samplers under polynomial requirements remains an important open problem.

Question 2

As requested, we report sn(P0)/n\mathfrak{s}_n(P_0)/n and Dn/nD_n/n in our TinyStories experiment. Each cell gives (sn(P0)/n, Dn/n)(\mathfrak{s}_n(P_0)/n,\ D_n/n), both as percentages.

nnTemp. 0.4Temp. 0.7Temp. 1.0
10K59.36%, 54.19%93.02%, 90.92%99.96%, 99.71%
20K53.06%, 48.40%90.81%, 88.80%99.85%, 99.48%
50K44.93%, 40.79%87.60%, 85.58%99.58%, 99.09%
100K39.14%, 35.50%85.15%, 82.95%99.23%, 98.62%
200K33.91%, 30.67%82.67%, 80.30%98.76%, 98.05%
500K27.72%, 24.96%79.22%, 76.83%97.98%, 97.19%
1M23.59%, 21.20%76.48%, 74.05%97.27%, 96.39%

Lower temperatures yield smaller effective support sizes at fixed nn, while Dn/nD_n/n closely tracks sn(P0)/n\mathfrak{s}_n(P_0)/n, supporting the role of effective support in our statistical analysis.

Furthermore, we have completed a controlled synthetic pilot with K=4,d=5K=4,d=5, three Zipfian populations (α∈{1.5,2,3}\alpha\in\{1.5,2,3\}), and an exponential population (λ=0.1\lambda=0.1), varying nn from 6464 to 65,53665{,}536. The small state space permits direct population TV and KL evaluation. Across all four scenarios, the observed TV and KL errors of trained SEDD exhibit convergence behavior closely matching the theoretical rate curves, providing strong preliminary empirical evidence for our guarantees. We are currently conducting the full experiment and will add a dedicated subsection with the complete results and rate comparisons to the final draft.

Reviewer_doFUOpenReview ↗

Response

The reviewer thanks the authors for the detailed response, which has addressed most of the reviewer's concerns. Hence, the reviewer would be glad to increase the rating from 3 to 4.

Dear reviewer,

Thank you for your support for our paper. We have uploaded a revised version of our manuscript, which includes the promised synthetic experiment that validates our theory (Section 4.1), and also the effective support size table for the TinyStories experiment (Section 4.2). We have also clarified that sampling and network complexity are sufficient conditions for the statistical guarantee ("Interpretation" paragraphs in Sections 3.1&3.2). Please let us know if you have any remaining questions or concerns. We would be happy to provide further clarification.

Reviewer_GnN5OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the statistical generalization properties of uniform-rate discrete diffusion models. Different from many prior studies which assume the estimation error to be controlled, this paper connects the two parts by considering the estimator structure and providing an estimator- and distribution-dependent error bound. Experiments are also provided.

Critical strengths
  1. The paper is well written and readable, with clear motivation and results.
  2. The theory part is sound, without any identifiable errors.
Critical weaknesses
  1. Given the theoretical analyses, it is unclear what the experiment is trying to validate. What results are targeting here? Note that the error bounds are in TV and/or KL, but the metrics used in the experiments (i.e., log-likelihoods and MAUVE) are neither of these. Also, what is sns_n in the experiment? Is the scale over nn correct?
  2. While the theory presents a better TV error, the step-complexity (i.e., how many steps for the algorithm to implement) still remains linear to the ambient dimension. This might cast some concern on the practical relevancy of the current result.
Questions for authors

Questions:

  1. See my question on the experiment above.
  2. How is the theory relevant to practice, especially on the algorithmic level (whether training or sampling)?
  3. In both TV and KL results, you need RA\mathcal{R}_A to be controlled by some function in nn. Since the left-hand-side depends on the sampling procedure, this seems to provide a constraint that nn should not be too large. Could you remark on this?

Writing suggestions:

  1. Currently the key related works are condensed in one paragraph. A table to compare prior estimation results would be helpful.
3 comments

We sincerely thank the reviewer for their careful reading and constructive feedback, particularly their recognition of the clarity and soundness of our theory. Their suggestions motivated additional empirical analyses, including a controlled synthetic experiment whose pilot results support our theory.

Weakness 1 and Question 1

Our TinyStories experiment investigates whether uniform discrete diffusion exhibits better distributional estimation performance for populations with smaller effective support sizes, holding KdK^d fixed. The teacher-NLL KS and 1−MAUVE1-\mathrm{MAUVE} metrics provide indirect measures of distributional agreement, since the enormous ambient cardinality KdK^d makes exact TV/KL evaluation, or sufficiently precise estimation, computationally infeasible.

We additionally report sn(P0)/n\mathfrak{s}_n(P_0)/n for each training size and temperature. Since sn(P0)\mathfrak{s}_n(P_0) depends on nn, this normalization directly reflects the statistical complexity appearing in our guarantees. The table confirms that lower temperatures yield substantially smaller effective support sizes at fixed nn.

nnTemp. 0.4Temp. 0.7Temp. 1.0
10K59.36%93.02%99.96%
20K53.06%90.81%99.85%
50K44.93%87.60%99.58%
100K39.14%85.15%99.23%
200K33.91%82.67%98.76%
500K27.72%79.22%97.98%
1M23.59%76.48%97.27%

To directly evaluate our TV/KL guarantees, we have completed a controlled synthetic pilot with K=4,d=5K=4,d=5, three Zipfian populations (α∈1.5,2,3\alpha\in\\{1.5,2,3\\}), and an exponential population (λ=0.1\lambda=0.1), varying nn from 6464 to 65,53665{,}536. Across all four scenarios, the observed TV and KL errors of trained SEDD closely follow the corresponding theoretical convergence-rate curves, providing strong preliminary empirical evidence for our theory. We are conducting the full experiment and will add a dedicated subsection with the complete results and rate comparisons to the final draft.

Weakness 2 and Question 2

The practical relevance of our work lies primarily in establishing (near-)minimax statistical guarantees governed by the effective support size sn(P0)\mathfrak{s}_n(P_0), rather than the ambient cardinality KdK^d. These guarantees can remain meaningful in the practically relevant regime n≪Kdn\ll K^d, where ambient-cardinality-based bounds become vacuous. The synthetic pilot described above further demonstrates that trained SEDD models exhibit convergence behavior consistent with our theoretical predictions.

Regarding algorithmic efficiency, our results provide worst-case sufficient conditions on network architecture, optimization accuracy, and sampling complexity, without additional structural or smoothness assumptions on the underlying distribution. The τ\tau-leaping iteration complexity N=O~(dn/sn(P0))N=\widetilde O(dn/\mathfrak{s}_n(P_0)) follows from combining existing sampler guarantees with our statistical accuracy requirements. We view its linear dependence on dd as favorable compared with exponential dependence, particularly given the worst-case nature of our guarantees. Moreover, our sampler-agnostic framework (Assumption 2) allows improved sampler guarantees to be incorporated without modifying the statistical analysis.

We also provide a one-step exact empirical reverse sampler achieving the same near-minimax KL rate with computational cost O(d(Dn+K))O(d(D_n+K)) per sample. Although it does not involve neural score estimation, it demonstrates that our statistical guarantees can be attained with polynomial-cost sampling under uniform diffusion. A detailed analysis of practical training efficiency remains an important future direction, which we will discuss in the final draft.

Question 3

The condition on RA\mathcal R_{\mathsf A} specifies the sampling accuracy required to achieve the target statistical rate, rather than imposing an upper bound on nn. Our framework allows sampling parameters to depend on nn. For example, the τ\tau-leaping remainder satisfies Rτ=e−Tdlog⁡K+Δdlog⁡(K/Δ)\mathcal R_\tau=e^{-T}d\log K+\Delta d\log(K/\Delta), and Corollaries 4 and 7 explicitly choose TT and Δ\Delta as functions of nn to satisfy the TV and KL requirements. Thus, while a fixed sampling configuration may eventually become insufficient as nn grows, adjusting its parameters preserves the guarantees. This reflects a natural statistical-computational trade-off: improved statistical accuracy may require more accurate sampling. We will clarify this interpretation in the final draft.

Writing Suggestion

We thank the reviewer for this helpful suggestion. We will add a table comparing our statistical assumptions and guarantees with the relevant prior work in the final draft.

Thank you for your clarifications. I already have a positive score, and I would maintain it.

Dear reviewer,

Thank you for your support for our paper. We have uploaded a revised version of our manuscript, which includes the promised synthetic experiment that validates our theory (Section 4.1), and also the effective support size table for the TinyStories experiment (Section 4.2). We have also clarified that sampling and network complexity are sufficient conditions for the statistical guarantee ("Interpretation" paragraphs in Sections 3.1&3.2).

Unfortunately, due to the limited space, we could not add a table for literature review. We will add a table in the final draft when more space becomes available. Please let us know if you have any remaining questions or concerns. We would be happy to provide further clarification.

Reviewer_KBNaOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Uniform discrete diffusion on [K]d[K]^{d} is studied through the effective support size sns_{n}. A near-optimal minimizer of the empirical score-entropy loss is shown to achieve expected TV error of order sn/n\sqrt{s_{n}/n} and KL error of order (sn/n)log⁡(eKd/sn)log⁡n(s_{n}/n)\log(eK^{d}/s_{n})\log n. Matching lower bounds lead to the conclusion that the method is minimax optimal in TV and optimal up to a log⁡n\log n factor in KL, with only logarithmic dependence on KdK^{d}. A TinyStories-teacher experiment varies the training-set size and the temperature.

Critical strengths

Relevance is evident because several existing worst-case bounds scale with KdK^{d}, and sns_{n} is a natural complexity measure. The writing is clear, and the results are stated precisely.

Critical weaknesses
  1. Guarantees describe a training-set reproducer. The central concern is that the guarantees describe a model reproducing its training set. The network size used in the theorems grows with the number of distinct training points. Under the KL theorem, the trained model is close to the early-stopped empirical distribution. When d/nd/n is small, that distribution places at least 1−d/n1-d/n of its mass on exact training sequences, so most generated samples are copies. The work frames the result as generalization rather than memorization. Population KL is indeed controlled, but simple smoothing estimators already attain these rates. What the result shows is that diffusion can reproduce such an estimator, not something specific to how diffusion models generalize.

  2. The KL theorem demands extreme precision. It requires an optimization error of roughly (Kn)−d(Kn)^{-d}, about 10−29810^{-298} at the largest training size in the experiment. The sufficient number of sampling steps and the network width also grow like (Kn)d(Kn)^{d}. These limitations are acknowledged, but their distance from any trainable regime is not discussed.

  3. Substantial overlap with known rates. Mourtada (2026) already proves a high-probability KL lower bound of the same order for ss-sparse distributions over a range of ss. That lower bound is not discussed, so the novelty of Theorem 8 needs clarification.

  4. Only indirect experimental evidence. The experiment never estimates sns_{n}, and its proxy metrics are not quantitatively tied to the theorems. Observed trends are not compared with the predicted rates, and the fraction of samples copying the training data is not reported.

Questions for authors
  1. For small d/nd/n, would you agree that most samples from a model satisfying the KL guarantee are training sequences? If not, where does this reading fail?

  2. Is the KL result provable with polynomially small optimization error?

  3. Beyond the result of Mourtada (2026), what is added by your lower bound?

4 comments

We thank the reviewer for their thoughtful feedback, particularly on practical relevance and empirical validation. Their suggestions motivated a controlled synthetic experiment whose pilot results support our theory.

Weakness 1 and Question 1

Our main contribution is a finite-sample analysis connecting empirical score-entropy minimization, neural score approximation, and reverse sampling to (near-)minimax TV/KL guarantees for uniform diffusion. Classical optimal estimators do not establish these guarantees for diffusion models. Our rates depend on effective support sn(P0)\mathfrak{s}_n(P_0) and can remain informative when n≪Kdn\ll K^d; empirical estimators are proof intermediates, not our main contribution.

Statistical generalization (small population TV/KL) is distinct from generating unseen sequences. Copying does not contradict statistical generalization: even the empirical distribution is minimax optimal in TV. Finite KL requires positive model probability on unseen sequences with positive population mass, although it does not guarantee frequent novel generations.

Regarding Question 1, the reviewer is correct under our KL theorem's sufficient conditions: the early-stopped empirical distribution places at least 1−d/n1-d/n probability on training sequences, and the sampler closely approximates it. This is not a necessary feature of KL generalization or practically trained SEDD. Nevertheless, copying does occur in practical uniform diffusion (see table of Weakness 4). Explaining generation of novel sequences beyond this sufficient construction remains open.

Weakness 2 and Question 2

The exponential architecture, optimization-precision, and sampling-step requirements for fixed-grid KL are worst-case sufficient conditions, not computational lower bounds. They arise from our KL transfer argument: because KL lacks a triangle inequality, our proof uses the uniform density floor ((1−e−1/n)/K)d≍(Kn)−d((1-e^{-1/n})/K)^d\asymp(Kn)^{-d} to transfer accuracy relative to empirical diffusion into population risk. The resulting stringent requirements are not known to be necessary.

Regarding Question 2, our neural-score proof does not establish the KL rate under polynomially small optimization error. Yet our one-step exact empirical reverse sampler (Appendix D) attains the same near-minimax KL rate at O(d(Dn+K))O(d(D_n+K)) cost per sample. Though it does not train a neural score, it demonstrates that exponential computation is not intrinsic to uniform-diffusion statistical guarantees. Extending this result to learned-score samplers remains open.

Weakness 3 and Question 3

Building on Mourtada's (2026) proof strategy, Theorem 8 gives a direct, self-contained expected-KL lower bound over the effective-support class Ps\mathcal P_s for 2≤s≤min⁡n,Kd2\le s\le\min\\{n,K^d\\}. Mourtada's high-probability result concerns ss-sparse classes with s≤Kd/55s\le K^d/55. Our characterization also recovers classical ambient-cardinality minimax rates when s=min⁡n,Kds=\min\\{n,K^d\\}, while providing refined rates for smaller effective support. We will clarify this relationship in the revision.

Weakness 4

We have completed a controlled synthetic pilot with K=4,d=5K=4,d=5, three Zipf populations (α∈{1.5,2,3}\alpha\in\{1.5,2,3\}), and an exponential population (λ=0.1\lambda=0.1), measuring population TV and KL of trained SEDD for n=64n=64 to 65,53665{,}536. Across all four scenarios, both errors show convergence behavior closely matching the theoretical rate curves computed from the actual sn(P0)\mathfrak{s}_n(P_0). These results provide strong preliminary evidence for our theory. We are conducting the full experiment and will add a dedicated subsection with plots to the revised manuscript.

For TinyStories, enormous KdK^d makes exact TV/KL evaluation, or sufficiently precise estimation, computationally infeasible; hence our original indirect metrics. We additionally report effective support and training-set copying. Each cell is (sn(P0)/n,copying rate)(\mathfrak{s}_n(P_0)/n,\text{copying rate}), in percentages.

nnTemp. 0.4Temp. 0.7Temp. 1.0
10K59.36%, 24.158%93.02%, 1.123%99.96%, 0.001%
20K53.06%, 39.402%90.81%, 3.672%99.85%, 0.005%
50K44.93%, 53.642%87.60%, 7.941%99.58%, 0.056%
100K39.14%, 61.751%85.15%, 11.367%99.23%, 0.171%
200K33.91%, 68.470%82.67%, 14.486%98.76%, 0.382%
500K27.72%, 75.353%79.22%, 19.415%97.98%, 0.887%
1M23.59%, 78.727%76.48%, 22.116%97.27%, 1.450%

Lower temperature produces smaller effective support and higher copying at fixed nn. We will include these results in the revised manuscript.

Dear Reviewer,

We would like to kindly follow up on our previous response. We hope that our explanations have addressed your concerns. Please let us know if you have any remaining questions or concerns. We would be happy to provide further clarification.

Thanks.

Thank you for addressing all of the remarks. I have changed the score to 3.

Dear reviewer,

Thank you for your support for our paper. We have uploaded a revised version of our manuscript, which includes the promised synthetic experiment that validates our theory (Section 4.1), and also the effective support size and copying rate table for the TinyStories experiment (Section 4.2). Especially, the copying rates show that practical SEDD both memorizes and generalizes beyond training samples, and for small sn(P0)/ns_n(P_0)/n, copying rates are high, meaning that empirical distributions are already a good distributional estimator. Although we do not claim that practical uniform diffusions should be similar to empirical distribution, this phenomenon is consistent with the proof strategy of using P^0\widehat P_0 or P^1/n\widehat P_{1/n} as an intermediate distribution.

We have also clarified that sampling and network complexity are sufficient conditions for the statistical guarantee ("Interpretation" paragraphs in Sections 3.1&3.2), and our novelty about the KL minimax rate("Minimax lower bound" paragraph in Section 3.2). Please let us know if you have any remaining questions or concerns. We would be happy to provide further clarification.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.