acceptodds
Under review as a conference paper at ICLR 2027

Dependence Cost of Independent Updates in Masked Diffusion

Abstract

Parallel token generation makes masked diffusion a useful approach to language modeling with fewer sequential sampling steps. However, sampling tokens independently can miss dependencies, and errors in the sampling trajectory can differ from errors in the final output distribution. We study progressive unmasking with distinct data and mask states, where masking decisions are independent across tokens and independent of their values. We express the smallest conditional approximation error exactly through the dependence among tokens revealed together, after conditioning on previously revealed tokens. For sequences built from independent pairs of correlated tokens, we analyze optimal schedules starting from the true fully masked distribution. We prove that the path error in relative entropy decreases inversely with the number of steps. For the sampler using exact conditional marginals, the output error in the same metric decreases with the inverse square of that number. For this family, exact representation by a finite mixture of product distributions requires exponentially many components as sequence length grows, while a suitable ordering permits exact sampling in two conditional rounds. Our results connect conditional dependence to sampling error and representation requirements.

Primary area:
learning theory
Keywords:
masked diffusion models, parallel sampling, information theory, conditional total correlation, sampling error bounds

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

The paper studies the cost of sampling several tokens independently in masked diffusion models, under random reveal patterns that are independent of the token values. It shows that the minimum conditional approximation error of one step is an average of the conditional total correlation of the newly revealed tokens (closely related to Lavenant & Zanella and Chen et al.). For a family of independent correlated pairs it computes the output distribution of the exact-marginal sampler in closed form, and shows that the optimal path error decays as 1/T in the number of steps while the output error decays as 1/T². For noisy parity blocks it derives a non-uniform optimal schedule, and it shows that representing the pair family as a finite mixture of product distributions needs exponentially many components, while a suitable ordering allows exact sampling in two rounds. Experiments check the formulas numerically and, on constructed span-infilling texts with MDLM and a Qwen3 diffusion model, compare reveal policies.

Critical strengths
  1. A precise and checkable separation between path error and output error. The paper gives exact closed forms for a simple but non-trivial family, and shows that the cumulative conditional (path) error and the error of the final distribution scale differently with the number of steps. This clarifies that step budgets derived from path-level bounds can be conservative for output accuracy, and the formulas are verified numerically.

  2. Clean theory that exposes how dependence structure shapes scheduling and representation. For noisy parity blocks all proper marginals are uniform, yet the optimal schedule is non-uniform, which shows that pairwise independence does not determine the optimal allocation of reveals. The component-count lower bound for mixtures of products and the two-round exact sampler are a neat illustration of what independent updates can and cannot represent. The assumptions (random reveal, exact marginals, specific families) are stated honestly.

Critical weaknesses
  1. The strict results are limited to toy families and their practical meaning is unclear. The core identity for the single-step error is essentially known (Lavenant & Zanella; Chen et al.), as the paper acknowledges, so the new content lies in the explicit computations for independent pairs and parity blocks and the mixture-component bound. The headline 1/T versus 1/T² separation is proved only for independent correlated pairs, and it comes from the quadratic behaviour of the divergence near the target; the paper gives no argument that it carries over to general dependence structures (for the parity blocks only costs and schedules are derived, not output rates). The analysis also assumes exact marginals and data-independent random reveal, whereas practical samplers choose positions adaptively and learned marginals add an error that accumulates over steps. As a result, the reader learns that such effects exist in a simple model, but not how they should change the design or step budget of a real masked diffusion sampler.

  2. There are no results on standard tasks and no improvement is proposed. The paper analyses the problem but proposes no method that can be used on real models, and there are no results on benchmarks such as math or code. The constructive procedures in the paper are existence-style constructions that require known dependency blocks and exact conditionals, and an appendix description of schedule selection from finite samples on tiny binary laws for which no results are reported. The only experiment with pretrained models uses constructed span-infilling texts, and its "dependency-aware" policy uses dependency spans that are supplied to the sampler, i.e. information that is not available in practice; the metric is reference-token NLL under argmax infilling rather than the quality of the generated text. This shows that knowing the dependencies helps, but not that the theory leads to any gain in actual generation, nor how to obtain the dependence information for natural text.

Questions for authors
  1. Which conclusions from the structured pair and parity examples do the authors expect to generalize to more realistic dependence patterns?
  2. How should these theoretical results guide the schedule or number of steps for a practical masked diffusion model when the dependence structure is unknown?
Reviewer_oY2yOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies how independent parallel token generation in masked diffusion loses dependencies between tokens. It characterizes the approximation error using conditional total correlation. For a specific correlated binary-pair distribution, it proves that path KL decreases as O(L/T)O(L/T) while output KL decreases as O(L/T2)O(L/T^2). It also derives optimal unmasking schedules and analyzes mixture representation complexity. The authors validate their findings through synthetic experiments and pretrained diffusion language models, showing benefits from dependency-aware token selection.

Critical strengths

The technical statements are precise and are supplemented with enough comments and proof sketches. In particular, it starts from the most general distribution and defining how to measure the correlation and approximation error, and progress to correlated binary-pair distribution and parity distributions.

Critical weaknesses

The paper shows a collection of distributions and theoretical results, but does not provide enough motivation for why these distributions should be studied. While parity could be a classical distribution of TCS interest, I am not sure how the relevant technical results could provide understanding about real world data distribution. It would also be hard for binary-pair distribution to capture real-world data dependencies.

Questions for authors
  1. Could the authors provide more motivation for why the distributions presented in the paper should be studied, and how the theoretical results provide relevant understanding for real world applications.
  2. Could the authors provide experiments on real world tasks instead of just synthetic data? This would help establish theory's relevance to practice as well.
Reviewer_9JHnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

It is a well-known problem of masked diffusion models (MDMs) that generating multiple tokens in a single step leads to accumulated errors in the final output. If we allow a large number of sampling steps, the transitions can occur one token at a time. However, as the number of sampling steps decreases, generation inevitably involves generating multiple tokens per step. Thus, an important question is how the gap between the generative distribution and the data distribution varies with the number of sampling steps. To analyze this error, this work mainly focuses on a simplified paired distribution in which each token is correlated only with its unique paired token (Eq. 5). Under this data assumption, the paper reveals 1) how the generation error is influenced by the number of sampling steps, 2) how the unique optimal schedules are determined (including for noisy parity blocks), and 3) that exact representation by a finite mixture requires exponentially many components, while a specific generation order can overcome this limitation.

Critical strengths

The problem of parallel generation is difficult to examine, considering the complex nature of discrete diffusion and the unknown data distribution. The paper simplifies the problem under the paired data assumption to provide the useful intuitions described above (see Summary).

Critical weaknesses

My major concern is that the paper strongly relies on a toy data assumption but does not reveal new intuitions. I believe that if one wants to use a toy data distribution, it should reveal new intuitions that could potentially be extended to problem settings without such assumptions, but this paper does not.

  1. Hayakawa et al. [1] already revealed the relationship between output error and the number of sampling steps without any assumptions.
  • Theorem 1 of [1] establishes dTV(p,qN)=O(1/N)d_{TV}(p, q_N) = O(1/N) without restrictive assumptions on the data distribution. Furthermore, Proposition 6 of [1] establishes dTV(p,qN)≥c/Nd_{TV}(p, q_N)\ge c/N under specific assumptions on the data distribution. Combining these, the results can be interpreted as dTV(p,qN)=O(1/N)d_{TV}(p, q_N) = O(1/N) (without assumptions) and dTV(p,qN)=Θ(1/N)d_{TV}(p, q_N) = \Theta(1/N) (with assumptions).
  • The paper's main contribution is described as deriving the output-level KL gap, DKL=Θ(L/N2)D_{KL}=\Theta(L/N^2). Given Pinsker's inequality, I am aware that this is a stronger bound. However, the problems are that 1) it relies on a strong data assumption, so the tight rate is established only for a highly structured distribution, limiting its generalizability, and 2) the output-level divergence bound is already known without any assumptions on the data distribution. I cannot find any new intuition that we can gain from Section 3 as a whole.
  1. The dependence of optimal schedules on the data distribution is also known [2].
  • As the paper acknowledges, Chen et al. [2] already revealed that optimal schedules depend on the data distribution. Given this prior work, I cannot see why the exact characterization of optimal schedules for specific, artificial paired distributions and noisy parity blocks is useful. The paper does not sufficiently explain what additional generalizable insights these special-case solutions provide beyond this known principle.
  1. Section 4.2 is trivial, and I also cannot identify the contribution of the theoretical results in this section.
  • To me, the fact that the number of mixture components required to represent the exact marginal grows exponentially seems intuitively trivial. It is also well known that generation order is important in terms of conditional independence, e.g., [3].
  • More importantly, the theoretical results themselves do not provide useful insights. First, the data distribution is highly simplified, so we cannot determine how many sampling steps are required to represent real-world data distributions. Second, the existence of an optimal generation order does not imply that finding or achieving it is practically easier. Considering these points, I cannot see what Theorem 5 and the result in Section C.6 imply.

[1] Hayakawa et al., "Distillation of Discrete Diffusion through Dimensional Correlations," ICML'25.

[2] Chen et al., "Optimal Inference Schedules for Masked Diffusion Models," COLT'26.

[3] Azangulov et al., "Parallel Sampling from Masked Diffusion Models via Conditional Independence Testing," ICLR'26.

Questions for authors

Please see the weaknesses above. I appreciate the authors' hard work and personally like this research direction, but I still cannot find any new intuition that this paper provides. If the authors can provide an important and original insight that I have missed in the paper, I would be happy to increase my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.