acceptodds
Under review as a conference paper at ICLR 2027

Error Analysis of Masked Discrete Diffusion under Low Complexity Structure

Abstract

Masked Diffusion Models have emerged as a discrete analogue of continuous Gaussian diffusion. They provide a new framework for learning distributions on discrete spaces and an alternative to autoregressive models for text generation. Despite the strong empirical performance of these models, theoretical analysis has been limited, focusing primarily on score estimation error, sampling guarantees and studying the structure of its Markov kernel. In this paper, we take a step towards end-to-end error analysis, derive approximation and finite-sample statistical error bounds for a Transformer-based predictor, analogous to the corresponding theory of continuous diffusion models. Our analysis identifies structural conditions on the clean-data conditional distributions under which their logits can be efficiently approximated by Transformers, and combines this approximation guarantee with Transformer complexity bounds to control estimation error. We further test empirically whether these structural conditions are supported by some common discrete distributions. This provides the first approximation-estimation theory for Transformer-based Masked Diffusion Models trained with a continuous-time NELBO loss and a data-dependent scaling law for the Transformer's attention window.

Primary area:
learning theory
Keywords:
discrete diffusion, masked diffusion models, transformer, low complexity structure, approximation error, estimation error

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 4 reviews, above 27% of the others.
Reviewer_zaiGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper gives approximation and estimation error bounds for masked diffusion models with a sliding-window Transformer. It assumes that each token mainly depends on a few nearby tokens, with exponentially decaying dependence on distant ones. Under this assumption, a window size growing as log⁡m\log m is enough, where mm is the sample size. The assumption is checked on Ising and GTR models.

Critical strengths

A first end-to-end error analysis for masked diffusion trained with the NELBO loss.

Critical weaknesses

I am not familiar with the approximation theory of Transformers or the theoretical analysis of masked diffusion models. I therefore lack the expertise to properly assess the value and novelty of the theoretical contributions, and I did not check the proofs in detail. My comments below are only based on the more general aspects of the paper, and I would ask the AC to give my assessment less weight.

  • Strong Assumptions: The locality assumption holds for Ising models at high temperature, but already fails at low temperature (Figure 1a). Natural language has long-range dependencies, so it is unclear what the results mean for practical masked diffusion language models.
  • No Validation of the Bounds: The experiments only check the assumption. No model is trained to check the predicted log⁡m\log m window scaling.
Questions for authors

Could you train sliding-window Transformers on the Ising or GTR models to verify the predicted window scaling?

3 comments
AuthorsOpenReview ↗

Locality assumption

We thank the reviewer for recognizing our contribution to the error analysis for masked diffusion models. We address the concern regarding the strong assumptions below.

We agree that for certain large values of β\beta, the assumption fails for the Ising model at low temperature. However, Figure 1a shows that even at low temperature, the assumption can be satisfied by choosing a lower β\beta. Here, β\beta is not explicitly present in the definition of the data distribution (Ising in this case). To understand the effect of choosing a lower β\beta, consider the window size Km∼log⁡m2βlog⁡2K_m \sim \frac{\log m}{2\beta \log 2} derived in the appendix section “Tradeoff between Approximation and Finite Sample statistical errors” (A.9 in the current version). Thus, whenever the spatial-decay condition holds for some fixed β>0\beta > 0, the logarithmic scaling in mm is preserved, albeit with a larger coefficient proportional to 1/β1/\beta. This illustrates that weaker spatial decay does not necessarily change the main scaling result.

We also agree that exponential decay is not a good condition for distributions with long-range dependencies. We acknowledge this limitation at the end of Section 5.2.1 of the main text. To address a broader class of distributions, the appendix section “Changes under Polynomial Spatial Weights” (Appendix H in the current version of the manuscript) extends our analysis by replacing exponential with polynomial weights. This extension is motivated in part by observations of power-law correlations in natural language data.

Thank you for the response. As noted in my review, I am not familiar with the theoretical aspects of this area. My main remaining concern is the lack of experiments validating the bounds, so I will keep my score.

Dear reviewer,

Thank you for your reply. We have done experiments training a sliding window transformer on sequences of length 64. The data we used is generated from a one dimensional ising model with open boundary conditions.

Changes to the manuscript

We have added a subsection I.3 to the appendix describing the experimental setup. The results are in I.3.1

Implications

The main results of interest are Figures 36, 37b and 38. Figure 36 shows the exponential decay of approximation error with K. Figure 37b shows estimation error obeys a power law decay in mm. A regression fit shows the exponent to be close to −0.5-0.5 (so that the decay is 1/m1/\sqrt{m}) for K≥2K\geq 2.

Figure 38 shows the plot of sliding window size KK vs log⁡2m\log_2 m. A least squares fit has R2=0.9834R^2=0.9834, validating the linear fit.

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

This paper studies the function approximation error, finite-sample statistical error, and generation distribution error of Masked Discrete Diffusion Models (MDLMs) with low-complexity data structures. The authors assume that the smoothed logits of the true masked posterior have a finite interaction order, and that the interaction coefficients decay exponentially with spatial distance. Under these conditions, the paper first proves that a single-layer sliding-window Transformer can approximate the target conditional function with an error that decreases exponentially with the window size. It then combines the continuous-time NELBO, the reverse CTMC path KL relation, and upper bounds on the covering number of the Transformer function class to establish a finite-sample error bound for the empirical risk minimizer. Experiments on Ising and GTR probabilistic models provide a preliminary check of the relevant structural assumptions.

Critical strengths
  1. The research problem is of theoretical significance. Connecting the low-complexity structure of the data distribution with Transformer approximation ability, statistical estimation error, and MDLM generation quality is a research direction worthy of attention.

  2. The theoretical analysis is relatively systematic. The paper attempts to study function approximation, finite-sample estimation, and continuous-time generation distribution error within a unified framework, and provides relatively complete proofs and preliminary experimental analysis on simple probabilistic models.

Critical weaknesses

W1. The core data structure assumption is strong, and its reasonableness still requires more sufficient justification. Assumption 5.1 requires the smoothed masked posterior logits to have a strictly finite interaction order—that is, interaction coefficients beyond a fixed order r are zero—while also satisfying a specific spatial exponential decay condition. This is stronger than the usual Markov property, local dependence, or exponential mixing. Even if the original data follow a finite-order Markov model, random masking may cause the posterior at a target position to depend on combinations of multiple visible positions, thereby producing higher-order interactions. The current Ising and GTR experiments mainly demonstrate the decay of higher-order interaction coefficients and cannot directly verify the condition of a strictly finite interaction order. The authors are advised to provide non-trivial examples of data distributions that satisfy this assumption, or to discuss the possibility of relaxing it to an approximate low-order interaction condition.

W2. The independent contribution relative to existing theoretical work needs to be further highlighted. The Transformer construction in Theorem 4.1 mainly draws on the attention feature extraction and function approximation techniques of Takakura and Suzuki [1]; Theorem 6.1 uses the existing MDLM NELBO and path KL relation [2], as well as the standard data-processing inequality; and Theorem 6.3 uses existing covering number results and empirical process theory to control statistical error. Although Theorem 6.2 provides a connection derivation specific to MDLMs, it mainly converts the logit approximation error into a conditional KL error and then applies the NELBO relation. Such a combination is a reasonable way to conduct theoretical research, but the authors are advised to state more explicitly which steps require new mathematical techniques and what additional theoretical difficulties this paper resolves compared with existing Transformer approximation and diffusion model statistical theory. In particular, deriving the complexity of the masked posterior from the interpretable structure of the original data still appears to be a key question worthy of further study.

W3. The control of the error in practical finite-step sampling is still incomplete. Theorem 6.1 mainly provides a KL upper bound on the generation distribution for the ideal continuous-time reverse process. For practical finite-step sampling, the paper introduces an additional discretization error term Discp(T)Disc_p(T), but has not yet provided a specific upper bound or convergence rate for this term as a function of the number of sampling steps. In addition, if the finite-step process is defined as a path that jumps only at fixed grid times, whereas the true CTMC jumps in continuous time, then the relationship between the two path measures and whether the path KL used is finite need to be further clarified. The authors are advised to clearly define the finite-step path distribution and further discuss the extent to which the existing theoretical results can provide end-to-end guarantees for practical MDLM sampling.

References

[1] Takakura, S., & Suzuki, T. (2023). Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input. ICML 2023.

[2] Sahoo, S., et al. (2024). Simple and Effective Masked Diffusion Language Models. NeurIPS 2024.

Questions for authors

See Weakness

4 comments
AuthorsOpenReview ↗

W1. Approximate low-order interaction condition

We thank the reviewer for highlighting the restrictive nature of Assumption 5.1. We agree that the exact finite interaction-order condition dγ=0for ord⁡(γ)>rd_{\gamma}=0 \quad \text{for }\operatorname{ord}(\gamma)>r is stronger than what our experiments establish. In fact, the experiments support an exponentially decaying bound on the fourier weights dγd_{\gamma}

Relaxation of the assumption

The condition dγ=0d_\gamma=0 for ord⁡(γ)>r\operatorname{ord}(\gamma)>r, with fixed rr, can be relaxed by requiring the Fourier coefficient tail beyond order rr to admit a bound uniform in the sequence length LL, for instance ∑ord⁡(γ)>r∣dγ∣≤Be−αr\sum_{\operatorname{ord}(\gamma)>r}|d_\gamma|\le Be^{-\alpha r}. The value of rr for which this holds can be chosen from the properties of the data (but should be independent of the sequence length LL). Under this relaxation, the approximation bounds in Theorems 4.1 and 6.2 acquire additional terms Be−αrBe^{-\alpha r} and 2LBe−αr2LBe^{-\alpha r}, respectively. The excess-risk bound in Theorem 6.3 changes accordingly, with the additional approximation error and its contribution to the loss envelope.

Changes to the manuscript

We have left the original theorem statements unchanged and have added a note explaining the relaxation at the end of Section 6 in the main text. Appendix G now discusses the detailed changes to the theorems under the relaxation. Extra experiments testing the exact relaxation ∑ord⁡(γ)>r∣dγ∣≤Be−αr\sum_{\operatorname{ord}(\gamma)>r}|d_\gamma|\le Be^{-\alpha r} have been added to Appendix I.1.3 and I.2.3.

Implications

Note that the relaxation does not affect our main conclusion: the parameter count of the model can be bounded, and the bound avoids exponential dependence on the sequence length LL by exploiting structural assumptions on the data. As shown in Appendix G, the architectural bounds as well as the optimal choice of KK remain unchanged for fixed rr. The value of rr can be chosen based on the properties of the data and the desired approximation accuracy, but must be independent of LL.

AuthorsOpenReview ↗

W2. The independent contribution relative to existing theoretical work

We thank the reviewer again for their comments. We agree that techniques used in our analysis build on existing theoretical work, particularly Takakura and Suzuki (2023) and Sahoo et al. (2024). Below we highlight the technical modifications we needed. We have also added discussions in the Related Work section, and an appendix subsection titled "Technical Differences from Takakura and Suzuki" (Appendix A.10 in the current version) to the manuscript.

1. Transformer approximation theorem

Our Transformer construction follows the attention-based feature extraction technique of Takakura and Suzuki (2023, Appendix E), and the position-wise feed-forward network construction uses the existing approximation theory of ReLU networks. However, our function class differs from theirs. While Takakura and Suzuki consider functions satisfying mixed or anisotropic smoothness conditions, we consider functions on discrete spaces with exponentially decaying spatial coefficients and finite interaction order. Consequently, the step of bounding the truncation error requires different combinatorial estimates. In particular, we establish that the number of admissible interactions at spatial radius ss satisfies nr(s)≤Cq,r(s+1)r−1,n_r(s) \le C_{q,r}(s+1)^{r-1}, which, combined with the coefficient norm and Hölder's inequality, gives

\le C(K+1)^{(r-1)/\tau'}2^{-\beta K}.$$ This differs from the smoothness-based truncation argument in Takakura and Suzuki (2023, Appendix D, Lemma D.1). Together with the existing neural-network constructions, it yields our uniform approximation bound with parameter complexity polynomial in the window size K. ### 2. Posterior approximation error As the reviewer observes, we use the continuous-time NELBO of Sahoo et al. (2024). This is different from the $L^2$ regression loss used by Takakura and Suzuki. The contribution of Theorem 6.2 is to convert the uniform Transformer logit approximation bound into an explicit conditional KL bound and then use it to bound the excess risk $R(p) - H(P)$. **Regarding complexity bounds:** We thank the reviewer for highlighting the question of deriving complexity bounds for the masked posterior. This is also an interesting direction, and we have expanded our discussion of it in the revised manuscript. The original manuscript included an observation (Lemma A.1) in Appendix A.4 that functions in our regularity class for $\tau = 1$ are Lipschitz with respect to the shift-space metric $d_{\beta}$ used in symbolic dynamics. Following the reviewer's comment, we have added Appendix A.4.1, which develops this observation into an explicit covering-number bound. Specifically, under Assumption 5.1 with $\tau = 1$, the posterior-logit functions satisfy $$\\|f_a^\lambda\\|\le R_\lambda, \qquad \operatorname{Lip}(f_a^\lambda)\le 2R_\lambda.$$ where the Lipschitz constant is measured in the $d_{\beta}$ metric. Define $$K_\varepsilon = \left\lceil \frac{1}{\beta}\log_2\frac{8R_\lambda}{\varepsilon} \right\rceil.$$ Using covering estimates for the corresponding bounded Lipschitz class, together with the fact that restriction to padded sequences does not increase the uniform distance, we establish $$\begin{aligned} \log N(\varepsilon,\mathscr G_{L,\lambda},\\|\cdot\\|\infty) &\le M Q^{2K_\varepsilon+1} \log\left(2+\frac{4R_\lambda}{\varepsilon}\right)\\\\ &\le C_{\beta,Q}M \left(\frac{R_\lambda}{\varepsilon}\right)^{ \frac{2\log_2 Q}{\beta}} \log\left(2+\frac{R_\lambda}{\varepsilon}\right), \end{aligned}$$ where $Q = M + 2$ and $\mathscr G_{L,\lambda}$ is the class of posterior-logit families defined in Appendix A.4.1. This result quantifies the complexity of the posterior-logits under our regularity assumption. The bound is independent of the sequence length $L$, but depends polynomially on the vocabulary size $Q = M + 2$. Notably, the exponent scales inversely with the ‘’smoothness’’ $\beta$.

I thank the authors for their response. The revision broadens the class of posterior functions covered by the theorems and clarifies the technical adaptations made in the proofs. However, the main results still rely on low-complexity assumptions imposed directly on the masked posterior. This makes the proofs less technically challenging, but also appears to limit the substantive novelty of the work. I will raise my score, although I still lean toward rejection.

AuthorsOpenReview ↗

W3. Error in practical finite-step sampling

Dear reviewer,

Thank you for your reply. Your recommendations have helped us improve our manuscript.

We would like to address your concern regarding finite-step sampling as well.

Definition of discretization error

Thanks for pointing out the issue with the definition. Indeed, if the true reverse process is in continuous time whereas the sampler jumps at specified finite steps, then the path KL between them will be infinite. We have changed the definition of Discp(T)Disc_p(T), replacing the path measures by their endpoint measures. (Section 5.1 of the revised manuscript)

Note that this does not change the decomposition in Theorem 6.1 (the proof is essentially the same).

End-to-end guarantees for practical finite sampling

Controlling the error due to a finite-step sampler is also an interesting question. This question is more well-studied in literature. We have added Appendix D1 which now uses the sampler studied in Li & Cai, and discusses heuristically how to combine their bounds with ours to obtain an end-to-end bound. Note that their paper does not study training error in detail. That's where our bounds on R(p)−H(P)R(p) - H(P) can be applied.

Reference

[1] Gen Li and Changxiao Cai. Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models. Neurips '25

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

This paper develops approximation and finite-sample statistical error bounds for masked discrete diffusion models with a one-block sliding-window Transformer predictor. The central assumption is that the smoothed clean-data posterior logits admit shift-equivariant representations with exponentially decaying spatial coefficients and an exactly bounded interaction order. Under this assumption, the authors construct a Transformer approximation, combine it with covering-number bounds to analyze an exact empirical risk minimizer under the continuous-time NELBO objective, and translate excess risk into a KL bound for the ideal continuous-time generative process, retaining an explicit smoothing term. Balancing the derived bounds for fixed structural parameters and smoothing level yields a logarithmic context-window choice and a parameter count polynomial in the logarithm of sample size. An appendix considers polynomial spatial decay. Validation consists of exact posterior and coefficient calculations for small Ising and GTR models, examining weighted-norm stability and interaction-order tails; the experiments do not evaluate trained Transformers or the predicted statistical/window-size scaling.

Critical strengths
  1. An explicit connection between approximation, estimation, and generative error. Theorems 4.1 and 6.2–6.3 connect a specified Transformer architecture and structural assumptions on the posterior logits to finite-sample excess NELBO risk, which Theorem 6.1 converts into a generative KL guarantee. Keeping the smoothing contribution explicit makes the scope of the result easier to assess. This is a useful contribution to understanding the statistical learning problem for masked diffusion with a concrete neural predictor class.

  2. An interpretable treatment of context length and structural complexity. The analysis separates spatial decay from interaction order and shows how these quantities determine the approximation–estimation tradeoff and a sufficient window-size choice. The exact posterior/coefficient diagnostics on Ising and GTR models are also an appropriate empirical direction for a theory paper, and Appendix H specifies the distributions, bases, and diagnostics in detail.

Critical weaknesses
  1. The connection between the theory and experiments remains incomplete. Assumption 5.1 requires dγ=0d_\gamma=0 for ord⁡(γ)>r\operatorname{ord}(\gamma)>r, whereas the interaction-order diagnostics show rapidly decaying coefficient tails rather than establish an exact cutoff. Section 8 uses this decay to justify the idealization without quantifying the uniform logit error from discarding higher-order terms. Thus, the applicability of the stated rates to these examples is not established. The experiments also do not directly evaluate approximation error versus KK or statistical estimation error versus mm.

  2. The periodic Ising experiment does not match the theorem’s all-position locality requirement. Assumption 5.1 uses padded linear geometry, but Section 7.1 uses periodic boundaries and tests only the central target. With position 11 masked and all others observed, changing xLx_L can change its posterior by an amount independent of LL, despite the represented distance being L−1L-1. This is incompatible with uniform spatial decay under fixed structural parameters. Central-position diagnostics therefore cannot validate the all-position assumption for this family.

Questions for authors
  1. Exact versus approximate interaction order. Can the authors establish that a nontrivial dependent example satisfies Assumption 5.1 with fixed rr and structural constants uniformly bounded in sequence length, and provide an approximate-order extension for the Ising/GTR examples? Such an extension should quantify the actual logit approximation error from truncating higher-order interactions in the Ising/GTR experiments rather than only reporting coefficient-tail decay, and account for its effect on the model-size and statistical guarantees when rr varies with the desired accuracy.

  2. Periodic boundary conditions and all-position locality. How is the periodic Ising experiment reconciled with the padded linear representation and the all-position requirement in Eq. (5.8), particularly the persistent dependence between positions 11 and LL described above?

  3. Direct evaluation of the theoretical guarantees. Could the authors provide a controlled synthetic evaluation of approximation error versus KK and population excess risk versus mm, and assess whether window choices motivated by Proposition A.6 provide a useful approximation–estimation tradeoff?

5 comments
AuthorsOpenReview ↗

Approximate interaction order

We thank the reviewer for pointing out that we need to quantify the uniform logit error from discarding higher-order terms. We agree that the exact finite interaction-order condition dγ=0for ord⁡(γ)>rd_{\gamma}=0 \quad \text{for }\operatorname{ord}(\gamma)>r is too strong for our experiments. In fact, the experiments support an exponentially decaying bound on the Fourier weights dγd_{\gamma}.

Relaxation of the assumption

The condition dγ=0d_\gamma=0 for ord⁡(γ)>r\operatorname{ord}(\gamma)>r, with fixed rr, can be relaxed by requiring the Fourier coefficient tail beyond order rr to admit a bound uniform in the sequence length LL, for instance ∑ord⁡(γ)>r∣dγ∣≤Be−αr\sum_{\operatorname{ord}(\gamma)>r}|d_\gamma|\le Be^{-\alpha r}. The value of rr for which this holds can be chosen from the properties of the data (but should be independent of the sequence length LL). Under this relaxation, the approximation bounds in Theorems 4.1 and 6.2 acquire additional terms Be−αrBe^{-\alpha r} and 2LBe−αr2LBe^{-\alpha r}, respectively. The excess-risk bound in Theorem 6.3 changes accordingly, with the additional approximation error and its contribution to the loss envelope.

Changes to the manuscript

We have left the original theorem statements unchanged and have added a note explaining the relaxation at the end of Section 6 in the main text. Appendix G now discusses the detailed changes to the theorems under the relaxation. Extra experiments testing the exact relaxation ∑ord⁡(γ)>r∣dγ∣≤Be−αr\sum_{\operatorname{ord}(\gamma)>r}|d_\gamma|\le Be^{-\alpha r} have been added to Appendix I.1.3 and I.2.3.

Implications

Note that the relaxation does not affect our main conclusion: the parameter count of the model can be bounded, and the bound avoids exponential dependence on the sequence length LL by exploiting structural assumptions on the data. As shown in Appendix G, the architectural bounds as well as the optimal choice of KK remain unchanged for fixed rr. The value of rr can be chosen based on the properties of the data and the desired approximation accuracy, but must be independent of LL.

AuthorsOpenReview ↗

Periodic boundary conditions

We thank the reviewer for pointing out the issue with the periodic boundary conditions. Indeed, due to the presence of the term xLxL+1=xLx1x_L x_{L+1} = x_L x_1 (under periodic boundary conditions), the Fourier expansion of the posterior may contain nonzero terms with spatial radius ϱ(γ)≥L−1\varrho(\gamma) \geq L-1. Our earlier experiments did not detect this issue because we had tested only the central site cL=(L+1)/2c_L = (L+1)/2.

Changes to the manuscript

We have revised Section 7 and Appendix I.1 as follows:

  1. We have removed the interaction term xLx1x_L x_1, thereby replacing periodic boundary conditions with open boundary conditions.
  2. Under open boundary conditions, we have rerun the experiments for the central site cL=(L+1)/2c_L = (L+1)/2.
  3. We have extended the experiments to additional sites, namely 1,2,cL−1,cL+1,L−1,1, 2, c_L-1, c_L+1, L-1, and LL.

Implications

The qualitative behavior observed previously, namely exponential decay, remains unchanged for the central site. Similar exponential decay is also observed at the additional sites under open boundary conditions.

Thank you for the detailed responses and revisions. I appreciate the authors' efforts, and I think the revisions partially address my concerns. However, my main remaining concern is that the experiments still do not directly evaluate the theoretical approximation–estimation tradeoff, particularly the dependence on window size KK and sample size mm. Overall, while the revisions have substantially improved the paper, the connection between the theoretical guarantees and empirical validation remains incomplete.

Reviewer_Py4ZOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper presents error analysis of masked discrete diffusion with one-block sliding-window transformers trained on continuous-time negative evidence lower-bound (NELBO) loss. The validity of the structural assumptions are verified empirically against some synthetic data such as Ising models and the four-state general time reversible (GTR) model.

Critical strengths

The applications of existing techniques and theory to the problem of masked discrete diffusion seems to be new, although I am not personally familiar enough with the literature to confirm this.

Critical weaknesses

To me the main aspect the paper falls short on is novelty. The authors largely follows the framework and theory laid out by Takakura & Suzuki (2023), from the sliding-window assumption to Theorem 4.1, where the input is assumed to be one-hot encoding of discrete tokens instead of continuous vectors. As far as I understand, there are no novel theoretical tools, and adopting the theory to discrete diffusion by changing the input data to one-hot and loss function to cross entropy do not feel like significant contributions to me. Discussion of the relation of this work to Takakura & Suzuki (2023) is also missing in the related works session, which the authors need to fix.

Setting aside the novelty concern, the results are also not groundbreaking in my opinion. The one-block finite-context regime is clearly a toy version of what is being practically used for discrete diffusion, and the paper doesn't give suggestions on how it might scale to more realistic scenarios or guide practice. Furthermore, the experiment section only contains synthetic datasets, and shows no agreements with data and prediction, only that Assumption 5.1 plausibly holds.

Questions for authors
  1. Can the authors discuss the technical novelties of this work relative to Takakura & Suzuki (2023)?
  2. Can the authors give more insights on the implications of the results? Specifically, do we expect the structural assumptions of the data to hold for practical datasets, and how might this theory inform practical applications of multi-layer transformers with infinite bidirectional context?
2 comments
AuthorsOpenReview ↗

1. Technical novelties relative to Takakura & Suzuki (2023)

We thank the reviewer for their comments. We agree that techniques used in our analysis build on the work of Takakura and Suzuki (2023). Below, we highlight the technical novelties specific to our setting. We have also added discussions in the Related Work section and an appendix subsection titled "Technical Differences from Takakura and Suzuki" (Appendix A.10 in the current version) to the manuscript.

1. Transformer approximation theorem

Our Transformer construction follows the attention-based feature extraction technique of Takakura and Suzuki (2023, Appendix E), and the position-wise feed-forward network construction uses the existing approximation theory of ReLU networks. However, our function class differs from theirs. While Takakura and Suzuki consider functions satisfying mixed or anisotropic smoothness conditions, we consider functions on discrete spaces with exponentially decaying spatial coefficients and finite interaction order.

Consequently, the step of bounding the truncation error requires different combinatorial estimates. In particular, we establish that the number of admissible interactions at spatial radius ss satisfies

nr(s)≤Cq,r(s+1)r−1.n_r(s) \le C_{q,r}(s+1)^{r-1}.

This, combined with the coefficient norm and Hölder's inequality, gives

∣f−fK∣∞≤C(K+1)(r−1)/τ′2−βK.\\|f-f_K\\|_\infty \le C(K+1)^{(r-1)/\tau'}2^{-\beta K}.

This differs from the smoothness-based truncation argument in Takakura and Suzuki (2023, Appendix D, Lemma D.1). Together with the existing neural-network constructions, it yields our uniform approximation bound with parameter complexity polynomial in the window size KK.

2. Posterior approximation error

Theorem 6.2 bounds approximation error under the continuous-time NELBO loss, rather than the L2L^2 regression loss studied by Takakura and Suzuki (2023). To work with this loss, we use the excess-risk identity of Theorem C.1:

R(p)-H(P)=\int_0^1 w(t)\mathbb{E}\left[\sum_{i\in\mathcal{M}(Z_t)} D_{\mathrm{KL}}\left(\pi_i(\cdot\mid Z_t)\middle\\|p_i(\cdot\mid Z_t,t)\right)\right]dt.

The additional argument, relative to the regression setting of Takakura and Suzuki (2023), is the conversion of a Transformer approximation bound into a conditional KL bound and subsequently into an excess-risk bound for the NELBO loss using the above identity.

We thank the reviewer again for their comments. In this note, we address some of their remaining concerns.

Infinite context

We agree that the exact finite interaction-order condition dγ=0d_{\gamma}=0 for ord⁡(γ)>r\operatorname{ord}(\gamma)>r is too strong for our experiments. The condition dγ=0d_\gamma=0 for ord⁡(γ)>r\operatorname{ord}(\gamma)>r, with fixed rr, can be relaxed by requiring the Fourier coefficient tail beyond order rr to admit a bound uniform in the sequence length LL, for instance ∑ord⁡(γ)>r∣dγ∣≤Be−αr\sum_{\operatorname{ord}(\gamma)>r}|d_\gamma|\le Be^{-\alpha r}. Based on feedback from reviewers, we have added a note explaining this relaxation at the end of Section 6 (after Theorem 6.3) in the main text. Appendix G now discusses the detailed changes to the theorems under the relaxation. Extra experiments testing the relaxed condition ∑ord⁡(γ)>r∣dγ∣≤Be−αr\sum_{\operatorname{ord}(\gamma)>r}|d_\gamma|\le Be^{-\alpha r} have been added to Appendices I.1.3 and I.2.3.

Implications of the results

Since the discrete input space has cardinality qLq^L, we expect naively chosen architectures to have parameter counts exponential in LL (the sequence length). Our structural assumptions allow us to avoid exponential dependence on LL. For instance, Section 6 (Theorem 6.3 and the subsequent discussion) shows that, for fixed structural parameters, the network can be chosen with Km=O(log⁡m)K_m=O(\log m) and parameter count NKm,M=O(M((log⁡m)r+1+(M+2)2(log⁡m)3)),N_{K_m,M}=O\left(M\left((\log m)^{r+1}+(M+2)^2(\log m)^3\right)\right), where mm is the sample size and MM is the alphabet size. Since the one-block Transformer used in the paper is a special case of multilayer Transformers, these existence and parameter-count bounds also apply to multilayer architecture classes.

Structural assumptions for practical datasets

In practice, masked diffusion models are trained on natural language data, which can exhibit long-range dependencies, including approximately power-law decay of correlations. We agree that exponential decay (Assumption 5.1) may not be a good condition for distributions with such long-range dependencies. We acknowledge this limitation in Section 5.2.1 of the main text. To address a broader class of distributions, the appendix section "Changes under Polynomial Spatial Weights" (Appendix H in the current version of the manuscript) extends our analysis by replacing exponential with polynomial weights. This extension is motivated in part by observations of long-range correlations in natural language data.

On the other hand, Assumption 5.1 is motivated by discrete models with local dependence and exponential mixing properties. The General Time Reversible (GTR) model, for instance, is widely used to model nucleotide substitution in phylogenetics. Our experiments use a stationary Markov-chain model constructed from its transition matrix. Thus, our framework is relevant to discrete sequence modelling beyond natural language, including applications in molecular biology.

Agreements between data and prediction

Our original manuscript didn't contain experiments validating the bounds proved theoretically. We have trained a sliding-window Transformer on sequences of length 6464 to experimentally test the approximation and estimation error scaling predicted by Theorem 4.1 and Theorems 6.2–6.3. We have added Appendix I.3 describing the experimental setup. The results are presented in Appendix I.3.1.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General clarification: Motivation and scope of the paper

We thank all reviewers for their constructive comments. Several reviews have raised questions concerning the applicability of our assumptions and empirical verification of our theorems. We recognize the importance of these concerns and will address them individually. However, we would also like to clarify the underlying motivation of the paper, which may not have been sufficiently emphasized in our presentation.

Our primary motivation is to formulate a notion of structural complexity for discrete sequence distributions and to characterize how this complexity governs the error analysis of masked diffusion models.

For functions on continuous spaces, notions of regularity (such as smoothness) provide the foundation for statistical analysis of neural networks trained to approximate such functions. Our starting question is how to formulate an analogous theory for functions of discrete sequences, with complexity parameters that reflect the structure of their dependence on the input coordinates.

To this end, we consider a class of functions characterized by two properties: bounded interaction order and spatially decaying expansion coefficients. These conditions quantify, respectively, how many input coordinates participate in an interaction and how strongly the function depends on distant coordinates. Based on reviewer comments, we also provide a relaxation to the bounded interaction order condition, which extends the results to natural classes of discrete distributions.

Note that the function class we use is inspired by similar classes used for continuous spaces. We adapt it to discrete spaces appropriately for our purpose.

Another motivation of the paper is to study how this complexity governs the approximation and finite-sample estimation errors of masked diffusion models when posterior logits are learned using a specific class of Transformers. The one-block sliding-window architecture is used as a mathematically controlled setting in which the relationship between function complexity and errors can be established explicitly.

We emphasize that the framework does not establish bounds for all architectures used in current practical MDLM implementations. There are also important limitations on the classes of distributions to which our assumptions are applicable, and we highlight some of those in our individual comments.

We hope this clarification provides a more accurate perspective on the motivation and intended scope of our results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.