- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper attempts to measure the statistical error in masked diffusion models that jointly arise from (1) non-optimal learning of the denoiser and (2) factorized sampling across positions. The authors assume a hidden Markov tree structure, which allows them to bypass the curse of dimensionality that otherwise plagues many results. They find that a transformer based MDM, that employs parallel unmasking, achieves KL divergence error on the order of .
Critical strengths
Realistic Setting: the authors propose evaluating parallel MDM- sampling with both (i) imperfect learning and (ii) parallel unmasking, which both strongly mirror how MDMs are used in practice. This makes the theoretical results more rooted in practice.
Clear presentation: the paper is written clearly
Critical weaknesses
No validation of assumptions: the authors do not explain/justify clearly why the hidden Markov tree structure is suitable for language data. No experimental results: The authors do not demonstrate any empirical evidence showing that in practice, parallel sampling from MDMs satisfies their theoretical bound. Experiments on large scale models, like Llada 8B [1] would be ideal, but we can not always compute the true error in closed form. Even toy models, where we can compute the true error, would be helpful to understand.
Questions for authors
- Can the authors please provide empirical evidence that their bounds hold in practice? In what setting should we expect this to hold?
4 comments
Response to Reviewer wuGh (Part Two)
Experimental results (W2 & Q1). (continued)
Parallel sampling (Theorem 2; Section 6, lines 501–505). On SCAN [7], for each number of sampling iterations , we train a width-32, depth-2 transformer, which has far fewer parameters than , and compute the KL error of the generated distribution exactly. The results are shown in Figure 1c (lines 507–521). The error decreases rapidly as increases, consistent with the parallelization bound in Theorem 2. When one token is generated per iteration (), the error is only 0.026, which shows that the small transformer learns this language distribution accurately. The results are listed in the following table.
| Number of iterations T | Estimated KL error |
|---|---|
| 1 | 5.741895 |
| 3 | 1.040758 |
| 5 | 0.309089 |
| 6 | 0.164958 |
| 9 | 0.026189 |
Overall, we expect our bounds to be informative when the data are well approximated by an MHMT with modest , as in the settings above.
We hope that these new experiments address the reviewer's concerns, and we would be grateful if the reviewer would take them into account in the final evaluation.
Revisions addressing your concerns (marked in blue in the updated manuscript)
- W1 (validation of assumptions): new Section 6, Table 1, lines 480-492, new experiments on language and biological data.
- W2 & Q1 (experimental results): new Section 6, Figure 1, lines 494-521, experiments for learning and sampling.
References.
[1] Durbin, R., Eddy, S. R., Krogh, A., and Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.
[2] Wang, X., Zheng, Z., Ye, F., Xue, D., Huang, S., and Gu, Q. (2024). Diffusion language models are versatile protein learners. In ICML.
[3] Chiu, J. and Rush, A. M. (2020). Scaling hidden Markov language models. In EMNLP.
[4] Wei, C., Xie, S. M., and Ma, T. (2021). Why do pretrained language models help in downstream tasks? An analysis of head and prompt tuning. In NeurIPS.
[5] Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. (2021). An explanation of in-context learning as implicit Bayesian inference. arXiv preprint arXiv:2111.02080.
[6] Petrov, S., Barrett, L., Thibaux, R., and Klein, D. (2006). Learning accurate, compact, and interpretable tree annotation. In COLING-ACL.
[7] Lake, B. and Baroni, M. (2018). Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In ICML.
[8] UCI Machine Learning Repository (1991). Molecular Biology (Splice-junction Gene Sequences). https://doi.org/10.24432/C5M888.
[9] Ovek Baydar, D., Rauluseviciute, I., Aronsen, D. R., et al. (2026). JASPAR 2026: expansion of transcription factor binding profiles and integration of deep learning models. Nucleic Acids Research, 54(D1):D184-D193.
Dear Reviewer,
As the discussion period is coming to an end, I would like to ask whether the our responses have addressed your concerns or if you have any further comments regarding the paper.
Thank you for your time and effort!
I thank the authors for the thorough rebuttal and new experiments, which address my main concerns about empirical validation. The synthetic results are consistent with the predicted dependence on and , and the MHMT fits suggest the assumption is reasonable for structured sequences. One caveat is that the MHMTs are fit to the empirical distribution of small datasets, and natural language remains untested. Overall, I am raising my score to 3.
Response to Reviewer wuGh (Part One)
We thank the reviewer for the constructive comments.
Validation of assumptions (W1).
First, we would like to clarify that our scope is learning structured discrete data with MDMs, which includes but is not limited to natural language. Two important examples are:
Biological sequences. Hidden Markov models are classical models of DNA and protein sequences [1], and MDMs are increasingly used to generate such sequences [2].
Language. Hidden Markov models and their mixtures are classical models of language, capturing sequential dependence and heterogeneity across sentence types [3,4,5]. In addition, tree-structured latent variables further capture hierarchical dependence between non-adjacent positions [6].
Second, our theory does not require the data to be exactly an MHMT: the term ProjJ,R(p⋆) accounts for the approximation error. To examine this term in practice, we fit MHMTs with the EM algorithm to structured language and DNA sequence datasets: SCAN navigation commands [7], donor splice-site DNA [8], and GATA1 binding-site DNA [9]. For each fitted MHMT q, we compute the joint KL divergence DKL(pdata∥q) exactly, where pdata is the empirical distribution of the dataset; each value is therefore an upper bound on ProjJ,R(pdata) (Section 6, Table 1, lines 478–492). The results are summarized below:
On SCAN [7], a compositional language of navigation commands, a chain MHMT with modest (J,R) fits the data almost exactly, and its structural complexity Kpar=R[LJ(J+V)+J3] is far smaller than VL. MHMTs with modest (J,R) also approximate the two DNA datasets [8,9] well. We will extending this validation to broader natural-language datasets.
Experimental results (W2 & Q1). As the reviewer notes, the true sampling error cannot be computed for large models such as LLaDA. We therefore design controlled synthetic experiments in which the true distribution is known, so that the error can be computed exactly or estimated accurately. Since our bounds hold up to constants and logarithmic factors, these experiments examine whether the error follows the predicted dependence on n, L, and T, rather than the numerical values of the bounds.
Estimation error (Theorem 1; Section 6, lines 494–500). We construct an MHMT with V=40, J=8, and R=4, so that Proj8,4(p⋆)=0, and train transformers on n samples from it. We evaluate the excess loss using the exact conditional distributions of the MHMT, averaged over 65,536 random test contexts. The results are shown in Figure 1a–b (lines 507–521).
First, at L=6, the excess loss decreases at a rate close to n−1, with a slope of about −0.81 on the log–log plot. The logarithmic factors in the bound make the apparent rate slower than n−1. The results are listed in the following table.
Second, we increase only the sequence length L of the MHMT from 6 to 24, keeping V, J, and R fixed, and train the same network on n=215 samples for each L. The excess loss grows only modestly, roughly linearly in L, whereas the size of the sequence space, VL, grows exponentially and reaches 4024≈3×1038. This illustrates that, under latent structure, the estimation error is governed by the structural complexity rather than by the size of the sequence space. The results are listed in the following table.