acceptodds
Under review as a conference paper at ICLR 2027

Transformer-Based Masked Diffusion Models Provably Learn Distributions with Latent Structure

Abstract

Masked diffusion models (MDMs) generate discrete data by iteratively unmasking multiple tokens in parallel using a learned mask predictor. Their output carries two errors: parallelization error due to parallel sampling, and estimation error from the mask predictor learned with finite samples. Existing theory treats these errors separately, and the available statistical bounds typically scale with the number of length- sequences over a vocabulary of size , suffering from the curse of dimensionality. In this work, we establish end-to-end statistical guarantees showing that transformer-based MDMs learn structured distributions with a sample complexity governed by their latent structure. Specifically, we model this structure through mixtures of hidden Markov trees, which capture latent dependencies within components and heterogeneity across components. When the data distribution is well approximated by such a mixture, a transformer-based MDM with parallel unmasking schedules achieves -accurate sampling in KL divergence with training samples, where is polynomial in , , the number of hidden states, and the number of mixture components. The transformer network and sampling procedure require no knowledge of the tree topologies or component parameters, thereby adapting to the unknown latent structure automatically. Overall, our results provide theoretical justification for the empirical effectiveness of MDMs on real-world data.

Primary area:
learning theory
Keywords:
masked diffusion models, sample complexity, low-dimensional structure, Transformers

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_wuGhOpenReview ↗
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 O(LKpar/ϵ)O(L K_{par} / \epsilon).

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
  1. Can the authors please provide empirical evidence that their bounds hold in practice? In what setting should we expect this to hold?
4 comments
AuthorsOpenReview ↗

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⋆)\mathrm{Proj}_{J,R}(p^\star) 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 qq, we compute the joint KL divergence DKL(pdata∥q)D_{\mathrm{KL}}(p_{\mathrm{data}} \Vert q) exactly, where pdatap_{\mathrm{data}} is the empirical distribution of the dataset; each value is therefore an upper bound on ProjJ,R(pdata)\mathrm{Proj}_{J,R}(p_{\mathrm{data}}) (Section 6, Table 1, lines 478–492). The results are summarized below:

Dataset(V,L)(V,L)(J,R)(J,R)KparK_{\mathrm{par}}VLV^LKL divergence
SCAN [7](14, 9)(8, 4)8,3842.07×10102.07\times 10^{10}6.1×10−76.1\times 10^{-7}
Donor [8](4, 9)(16, 4)27,904262,1440.110
GATA1 [9](4, 11)(16, 8)60,9284,194,3040.018

On SCAN [7], a compositional language of navigation commands, a chain MHMT with modest (J,R)(J,R) fits the data almost exactly, and its structural complexity Kpar=R[LJ(J+V)+J3]K_{\mathrm{par}} = R[LJ(J+V)+J^3] is far smaller than VLV^L. MHMTs with modest (J,R)(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 nn, LL, and TT, rather than the numerical values of the bounds.

Estimation error (Theorem 1; Section 6, lines 494–500). We construct an MHMT with V=40V=40, J=8J=8, and R=4R=4, so that Proj8,4(p⋆)=0\mathrm{Proj}_{8,4}(p^\star)=0, and train transformers on nn 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=6L=6, the excess loss decreases at a rate close to n−1n^{-1}, with a slope of about −0.81-0.81 on the log–log plot. The logarithmic factors in the bound make the apparent rate slower than n−1n^{-1}. The results are listed in the following table.

Sample size nEstimated loss
2,0481.433676
4,0960.887438
8,1920.471592
16,3840.264528
32,7680.158803

Second, we increase only the sequence length LL of the MHMT from 6 to 24, keeping VV, JJ, and RR fixed, and train the same network on n=215n=2^{15} samples for each LL. The excess loss grows only modestly, roughly linearly in LL, whereas the size of the sequence space, VLV^L, grows exponentially and reaches 4024≈3×103840^{24}\approx 3\times 10^{38}. 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.

Sequence length Lspace size VLV^LEstimated loss
64.10×1094.10\times10^{9}0.158803
86.55×10126.55\times10^{12}0.198597
101.05×10161.05\times10^{16}0.236442
121.68×10191.68\times10^{19}0.272097
164.29×10254.29\times10^{25}0.344743
201.10×10321.10\times10^{32}0.401682
242.81×10382.81\times10^{38}0.441562
AuthorsOpenReview ↗

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 T∈{1,3,5,6,9}T \in \lbrace 1,3,5,6,9 \rbrace, we train a width-32, depth-2 transformer, which has far fewer parameters than VL≈2.1×1010V^L\approx 2.1\times 10^{10}, 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 TT increases, consistent with the O(1/T)O(1/T) parallelization bound in Theorem 2. When one token is generated per iteration (T=9T=9), 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 TEstimated KL error
15.741895
31.040758
50.309089
60.164958
90.026189

Overall, we expect our bounds to be informative when the data are well approximated by an MHMT with modest (J,R)(J,R), 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 nn and LL, 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.

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

This work studies bounds on training and sampling errors for masked diffusion models. Typical existing bounds study either training error, or parallelization error (obtained from unmasking multiple tokens at once). This work assumes a target distribution which is well approximated by a mixture of hidden Markov trees (MHMT), and derives bounds for the end-to-end error, involving both imperfect training and sampling error, assuming a transformer diffusion model. The structured nature of the data results in bounds which depend on the MHMT parameters rather than the total number of sequences VLV^L, or the support of the target distribution.

Critical strengths
  • Clear and logical presentation
  • The paper provides an intuitive understanding of the technical results presented.
  • Bounding the end-to-end procedure, involving both learning and parallelization error is interesting and useful
Critical weaknesses
  • The degree to which the MHMT model is reasonable for realistic datasets is under-discussed. Studying how well these models fit to different domains would shed light on which tasks the presented results are more relevant for.
    • In particular, what parameters J and R are reasonable for certain standard datasets?
  • From my understanding, the results require the architecture to be selected based on certain parameters of the MHMT (namely J,RJ, R) - but in realistic settings these parameters are unclear, and will often be mis-specified. The impact of this misspecification on the resulting bounds is unclear (in particular, how do these effect the projection error?).
  • The sampling strategy specifies picking the unmasked positions uniformly at random (line 164-165) - which limits the parallelization results since in practice heuristics (such as token confidence) are used for adaptive unmasking.
Questions for authors
  • Is the MHMT model a reasonable approximation for natural language data (in particular for tasks such as math and coding), or is it better suited to more ‘structured’ tasks - eg. biological sequence tasks (eg. DNA, proteins), combinatorial tasks etc.
5 comments
AuthorsOpenReview ↗

Response to Reviewer RtGv (Part One)

We appreciate the reviewer's thoughtful comments and positive evaluation.

MHMT approximation of realistic datasets (W1 & Q1). We thank the reviewer for this suggestion. In the new Section 6 (lines 480–492), we fit MHMTs with the EM algorithm to three structured sequence datasets: SCAN navigation commands [1], donor splice-site DNA [2], and GATA1 binding-site DNA [3]. For each fitted MHMT qq, we compute the KL divergence DKL(pdata∣∣q)D_{\mathrm{KL}}(p_{\mathrm{data}} || q), where pdatap_{\mathrm{data}} is the empirical distribution of the dataset. Thus each value is an upper bound on ProjJ,R(pdata)\mathrm{Proj}_{J,R}(p_{\mathrm{data}}). The table below reports, for each dataset, a choice of (J,R)(J,R) that we found sufficient:

Dataset(V,L)(V,L)(J,R)(J,R)KparK_{\mathrm{par}}VLV^LKL divergence
SCAN [1](14, 9)(8, 4)8,3842.07×10102.07\times 10^{10}6.1×10−76.1\times 10^{-7}
Donor [2](4, 9)(16, 4)27,904262,1440.110
GATA1 [3](4, 11)(16, 8)60,9284,194,3040.018

On all three datasets, MHMTs with modest (J,R)(J,R) achieve a small KL error, and the structural complexity KparK_{\mathrm{par}} is also far smaller than the support size VLV^L.

Regarding Q1, we expect our results to be most informative for structured sequences, such as compositional languages, biological sequences, and combinatorial tasks, where a modest latent state space captures the dependence, as in the examples above. For general natural language, including math and code, the dependence between tokens is more complex, so larger JJ and RR may be needed. Even in this case, our theory remains informative: the sample complexity grows polynomially in JJ and RR rather than exponentially in LL, and the term ProjJ,R(p⋆)\mathrm{Proj}_{J,R}(p^\star) shows how the error depends on how well MHMTs approximate the data.

Unknown structural parameters and misspecification (W2). We apologize for the presentation that may cause misunderstanding, and we would like to clarify that our guarantees do not require JJ and RR to be known or correctly specified. The pair (J,R)(J,R) is not a parameter of the data. Instead, it only indexes the class of MHMTs that we compare against in the analysis. Theorems 1 and 2 hold for every p⋆p^\star, which need not be an MHMT, and the term ProjJ,R(p⋆)\mathrm{Proj}_{J,R}(p^\star) is exactly the price of misspecification, whose size depends on the structure of the data.

In practice, one chooses the network size rather than (J,R)(J,R), and our theory makes the resulting tradeoff explicit. For a given network class Θ\Theta, Propositions 1 and 2 give

E[L(θ^)]≲min⁡(J,R) representable by Θsmax⁡LProjJ,R(p⋆)+C(Θ)npolylog⁡(n).\mathbb{E}\big[\mathcal{L}(\widehat\theta)\big] \lesssim \min_{(J,R)\text{ representable by }\Theta} \frac{s_{\max}}{L}\mathrm{Proj}_{J,R}(p^\star) + \frac{C(\Theta)}{n}\mathrm{poly}\log(n).

A larger network can represent MHMTs with larger (J,R)(J,R), which reduces the approximation error ProjJ,R(p⋆)\mathrm{Proj}_{J,R}(p^\star), but it also increases the complexity C(Θ)C(\Theta) and hence the estimation error. As is standard in practice, the network size that balances these two terms can be selected on validation data.

Our theory also indicates how large the network should be: the more structured the data, the smaller the network needed. If ProjJ,R(p⋆)\mathrm{Proj}_{J,R}(p^\star) is already small for modest (J,R)(J,R), then a network with O~(Kpar(J,R))=poly(L,V,J,R)\widetilde O(K_{\mathrm{par}}(J,R)) = \mathrm{poly}(L,V,J,R) parameters suffices, rather than one whose size scales with VLV^L. Appendix A.2 provides two examples to highlight this: (1) for distributions with a smooth kk-dimensional latent representation, ProjJ,R(p⋆)\mathrm{Proj}_{J,R}(p^\star) decays polynomially in RR at a rate determined by kk; (2) for distributions with small Rényi entropy, the required RR is determined by the entropy rather than by VLV^L.

Our newly added experiments in Section 6 are consistent with this in two settings. On synthetic data from an exact MHMT with V=40V=40, the estimation error of a width-64, depth-2 transformer grows only modestly as LL increases from 6 to 24, even though VLV^L reaches about 3×10383\times 10^{38} (lines 494-500). On the SCAN dataset [1], a compositional command language that is only approximately an MHMT, a width-32, depth-2 transformer with far fewer than VL≈2.1×1010V^L \approx 2.1\times 10^{10} parameters learns the data distribution accurately (lines 501-505).

We have added this discussion of how our theory guides the choice of network size to Section 4 (lines 404–407).

AuthorsOpenReview ↗

Response to Reviewer RtGv (Part Two)

Confidence-based decoding (W3). We agree that developing guarantees for confidence-based unmasking strategies is an important direction. We focus on a uniformly random unmasking strategy because the masks it produces at sampling time have the same distribution as the masks used to train the predictor. This match allows us to translate the training error into a guarantee for the generated samples.

Confidence-based unmasking raises two additional difficulties.

  • Distribution shift: the masks depend on the tokens generated so far. This adaptivity makes the mask distribution differ from the one used in training, so the training error cannot be directly translated into a bound on the sampling error.

  • Error in the confidence scores: an imperfectly learned predictor changes not only the distributions from which tokens are sampled, but also the confidence scores that decide which positions are unmasked. The prediction error therefore creates an additional source of sampling error. Addressing both difficulties requires new tools beyond the scope of this work.

Our main contribution is to control the estimation error of transformer-based mask predictors under latent structure. Our result (Theorem 1) does not depend on the unmasking strategy, so we expect it to serve as a building block for analyzing more complex decoding strategies. We have added a discussion of how our analysis may extend to adaptive sampling. in Section 7 (lines 534–536).

We hope that these responses address the reviewer's concerns, and we are happy to answer any further questions.

Revisions addressing your concerns (marked in blue in the updated manuscript)

  • W1 & Q1 (MHMT approximation of realistic datasets): new Section 6, Table 1, lines 480-492, new experiments on language and biological data.
  • W2 (unknown J & R): Section 4, lines 404-407.
  • W3 (adaptive sampling): Section 7, lines 534–536.

References.

[1] Lake, B. and Baroni, M. (2018). Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In ICML.

[2] UCI Machine Learning Repository (1991). Molecular Biology (Splice-junction Gene Sequences). https://doi.org/10.24432/C5M888.

[3] 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!

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

The paper asks whether masked diffusion models can learn structured discrete distributions without sample complexity exponential in sequence length. The approach approximates the data distribution by a mixture of hidden Markov trees, constructs a sparse transformer that computes their masked-token conditionals, and analyzes empirical risk minimization followed by parallel unmasking. The architecture’s budgets depend on the model sizes, but require no supplied tree topology or latent parameters.

Critical strengths
  1. The paper establishes finite-sample guarantees for transformer-based masked diffusion on mixtures of hidden Markov trees, with polynomial dependence on structural parameters. This meaningfully connects representational capacity to statistical learnability.

  2. The constructive belief-propagation argument handles arbitrary tree topologies, mixtures, and masking patterns. This generality makes the technical contribution substantial.

Critical weaknesses
  1. The guarantees require exact global empirical-risk minimization and a specialized transformer architecture. Without an efficient optimization guarantee, their implications for practical training remain limited.

  2. The statistical bounds appear loose even for product distributions: the joint-KL bound scales as approximately L^2V/n, whereas coordinate-wise estimation achieves LV/n. This limits conclusions about statistical efficiency.

Questions for authors
  1. Is the additional factor of L in the product-distribution case intrinsic to the proposed estimator, or an artifact of the analysis?

  2. Please clarify the specific technical advances over earlier transformer belief-propagation constructions, particularly Oko et al. (2025), beyond incorporating the known sampling-error decomposition.

3 comments
AuthorsOpenReview ↗

Response to Reviewer mr3o (Part One)

We thank the reviewer for the thoughtful and constructive comments.

Exact ERM and specialized transformer architecture (W1). We agree that optimization is an important issue. However, establishing guarantees for transformers trained with practical optimization algorithms would require an analysis of non-convex training dynamics of neural network optimization, which is beyond current theory. Since our focus is on statistical guarantees and achievability results for transformer-based MDMs, we follow prior statistical analyses in the literature [1,2] and study the ERM to separate statistical guarantees from optimization.

Nevertheless, our analysis extends to approximate minimizers and preserves the order of the sample complexity when the optimization error is sufficiently small. Specifically, let θ~∈Θ\widetilde\theta \in \Theta satisfy R^n(θ~)≤inf⁡θ∈ΘR^n(θ)+Δopt,Δopt≥0,\widehat R_n(\widetilde\theta) \le \inf_{\theta\in\Theta} \widehat R_n(\theta) + \Delta_{\mathrm{opt}}, \qquad \Delta_{\mathrm{opt}} \ge 0, where Δopt\Delta_{\mathrm{opt}} denotes the optimization error. The argument of Proposition 1 then extends Theorem 2 to

E[DKL(p⋆∥pYθ~∣S)]≲(εparall(p⋆;s)+smax⁡ProjJ,R(p⋆)+LKparn)polylog⁡(n,L,V,J,R)+LE[Δopt].\mathbb{E}\big[D_{\mathrm{KL}}(p^\star \Vert p_{Y_{\widetilde\theta} | S})\big] \lesssim \Big(\varepsilon_{\mathrm{parall}}(p^\star; s) + s_{\max}\mathrm{Proj}_{J,R}(p^\star) + \frac{L K_{\mathrm{par}}}{n}\Big) \mathrm{poly}\log(n,L,V,J,R) + L \mathbb{E}[\Delta_{\mathrm{opt}}].

Here, the expectation is also taken over the randomness of the optimization algorithm. Hence, the sample complexity in (19) still holds whenever E[Δopt]≲ε/L\mathbb{E}[\Delta_{\mathrm{opt}}] \lesssim \varepsilon/L. We have added a discussion of the gap between exact ERM and practical optimizers in Section 7 (lines 536–539).

Regarding the architecture, our network class uses standard components (embeddings, attention, and feed-forward layers) and does not depend on the tree topology. As is common in statistical analyses of neural networks [1,3], we impose sparsity and norm constraints only to control statistical complexity through the number of nonzero parameters.

We have added new experiments (new Section 6) to support the theory. A standard transformer trained with Adam shows an estimation error that decreases with the sample size nn and grows only modestly with the sequence length LL, although training is not guaranteed to attain ERM. Establishing guarantees for general transformers remains an important direction for future work.

Product distributions and the extra factor of LL (W2 & Q1). We thank the reviewer for pointing out this gap. Product distributions are MHMTs with J=R=1J=R=1, for which Kpar=O(LV)K_{\mathrm{par}} = O(LV). Theorem 2 gives a bound of order O~(L2V/n)\widetilde O(L^2V/n), whereas coordinate-wise estimation achieves O(LV/n)O(LV/n). Our bound is thus suboptimal by a factor of LL in this special case.

This extra factor of LL arises from the generality of our construction, where we use a single transformer architecture to accommodate all distributions in the MHMT class. This generality sacrifices optimality for product distributions, as their coordinate independence is not exploited. If prior information about the target distribution (such as a product structure) is available, the architecture can be tailored accordingly, which removes the extra factor of LL and gives the optimal rate.

Since our main objective is to break the curse of dimensionality by reducing the dependence of sample complexity on LL from exponential to polynomial, we did not optimize this factor. Achieving optimal rates across the class while keeping a single network architecture remains an important direction for future work. We have added a remark acknowledging this limitation in Section 4 (Remark 3, lines 394–396).

AuthorsOpenReview ↗

Response to Reviewer mr3o (Part Two)

Technical advances over Oko et al. (2025) (Q2). Our construction differs from [4] in two main ways: (i) it covers general underlying tree structures, including unbalanced trees of height Θ(L)\Theta(L), with only O~(log⁡L)\widetilde O(\log L) transformer blocks, whereas the transformer depth in [4] grows with the tree height; and (ii) it handles mixtures of trees with different, unknown topologies, which [4] does not consider. We have added this comparison to Section 5 (lines 470–474).

Depth. The construction in [4] propagates messages by one tree level per transformer block, so its depth grows with the tree height and its analysis focuses mainly on balanced trees. Our height-dependent construction in Appendices C.4–C.5 follows a similar approach. However, our main construction (Appendices C.1–C.2) removes a constant fraction of the remaining nodes at each stage and then recovers the conditionals at the removed nodes. This allows it to handle any LL-node tree with O~(log⁡L)\widetilde O(\log L) blocks. Therefore, our analysis covers general trees, which need not be balanced or have small height, including trees of height Θ(L)\Theta(L) such as chains.

Mixtures. The analysis in [4] does not consider mixtures of trees with different topologies. Extending the construction to mixtures requires more than combining the predictions of individual components, because the posterior weights of the components depend on the observed context. Our network therefore also approximates the likelihood of the context under each component. Mixtures are important for modeling heterogeneous data [5], as different components can have different tree structures, and each component can capture a different dependence pattern with a small hidden state space.

We hope that these responses address the reviewer's concerns, and we are happy to answer any further questions.

Revisions addressing your concerns (marked in blue in the updated manuscript)

  • W1 (ERM): Section 7, lines 536–539, discusses the gap between the exact ERM and practical optimizers.
  • W2 & Q1 (extra factor of LL): New Remark 3, lines 394–396.
  • Q2 (comparison with Oko et al., 2025): Section 5, lines 470–474.

References.

[1] Oko, K., Akiyama, S., and Suzuki, T. (2023). Diffusion models are minimax optimal distribution estimators. In ICML.

[2] Fan, J., Gu, Y., and Li, X. (2025). Optimal estimation of a factorizable density using diffusion models with ReLU neural networks. arXiv preprint arXiv:2510.03994.

[3] Azangulov, I., Deligiannidis, G., and Rousseau, J. (2024). Convergence of diffusion models under the manifold hypothesis in high-dimensions. arXiv preprint arXiv:2409.18804.

[4] Oko, K., Lin, L., Cai, Y., and Mei, S. (2025). A statistical theory of contrastive pre-training and multimodal generative AI. arXiv preprint arXiv:2501.04641.

[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.

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!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.