acceptodds
Under review as a conference paper at ICLR 2027

Fast Parallel Sampling for Masked Diffusion Models via Dependence Partitions Prediction

Abstract

Masked diffusion models enable parallel generation of discrete data, but simultaneously revealing multiple tokens can introduce error by neglecting their conditional dependencies. Recent methods address this challenge through adaptive unmasking schedules and dependency-aware token selection. However, explicit dependence checks can incur additional model evaluations, while inexpensive dependency estimates need not provide rigorous guarantees on sampling accuracy. In this work, we develop a theoretical framework for sampling with partition prediction. A partition oracle groups masked coordinates into bounded-size blocks, which our sampler processes in parallel while performing successive conditional updates within each block. Under quantitative assumptions on score estimation and partition quality, we establish nonasymptotic KL error bounds that separate initialization error, score estimation error, and residual cross-block dependence and quantify how the block size controls the trade-off between sampling accuracy and parallel query depth. We further construct partition oracles for ferromagnetic Ising models with bounded susceptibility, and masked language-model predictors with stable neural network.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
mask diffusion, parallel sampling, Ising model, algorithm with prediction

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_gDieOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a theoretical framework for masked diffusion sampling, featuring sequential “first-hitting” updates within blocks and parallel updates across blocks. Under an assumption regarding the average score entropy error, the authors derive a KL-divergence error bound—decomposed into initialization error, score estimation error, and cross-block dependency error—and provide upper bounds for the total number of queries and the parallel query depth. Furthermore, the authors construct grouping oracles for the ferromagnetic Ising model and masked language model predictors. The primary contribution of this work is establishing a connection between cross-block dependencies, sampling accuracy, and the computational cost of sequential updates within blocks.

Critical strengths

The problem is significant. The framework explains how distributions with strong global dependencies can still be sampled in parallel, provided that these dependencies are concentrated within small blocks. Additionally, by varying the choice of grouping, it bridges the gap between “modified truncated τ-leaping” and sequential “first-hitting” methods.

The analysis involves substantial technical work. In particular, it addresses the mixed-context issue arising from intra-block updates and bounds the sampling error based on an assumption regarding the average score error.

The authors provide concrete constructions for grouping oracles and analyze their computational costs. The example of an Ising model with independent pairs yields both an upper bound for the proposed sampler and a lower bound for the specified “modified truncated τ-leaping” baseline.

Critical weaknesses
  1. The demonstrated advantage in query depth has a limited scope of application.

In the example involving independent pairs, the cross-block dependency is exactly zero. For the Ising model on a square lattice, however, the derived bounds do not clearly demonstrate an advantage over the “first-hitting” baseline (which requires dd queries). Specifically, setting r≡dr\equiv\sqrt d and Bpart≲d3/4B_{\mathrm{part}}\lesssim d^{3/4} leads—via Corollary 1—to a number of synchronization intervals N=O~(d+d3/4/ε)N=\widetilde O(\sqrt d+d^{3/4}/\varepsilon) and a parallel query depth upper bound of O~(d+d5/4/ε)\widetilde O(d+d^{5/4}/\varepsilon). Providing an example that features non-zero cross-block dependencies—and demonstrates a provable advantage in terms of depth—would better illustrate how the general theory balances parallelization errors against sequential computation within blocks.

  1. The benefits of the language model (LM) construction require further substantiation.

There are two related issues here.

First, the error bound in Theorem 3 includes an exponential amplification factor, ed(t−tk)e^{d(t-t_k)}, which is not directly constrained by the condition r(tk)hk≤1r(t_k)h_k\le1. Controlling the resulting error might necessitate smaller time steps or more precise score estimates. The authors should provide representative conditions under which Theorem 3—combined with Theorem 1 and Corollary 1—yields a query depth strictly less than dd.

Second, the explicit sensitivity construction may not provide meaningful guidance for selecting groupings. Under the assumptions of full attention, position-independent attention bias, shared token-wise parameters, and the uniform radius bounds from Lemmas 16–17, all off-diagonal sensitivity weights become identical. In this scenario, the grouping strategy is determined solely by tie-breaking rules, and bLM(q)b_{\mathrm{LM}}(q) depends only on the sizes of the blocks; consequently, this criterion cannot distinguish between different groupings with the same block sizes. Furthermore, the norm-based bounds effectively discard the positional information encoded in RoPE. This raises a specific question: how does this construction identify useful groupings within a dense Transformer architecture?

Computing sensitivity weights, deriving specific groupings, and calculating upper bounds on errors for small-scale models would help demonstrate the effectiveness of this construction.

  1. Numerical validation and presentation could be improved.

The paper lacks numerical experiments. Small-scale simulations could explore the trade-off between sampling error and query depth, while also illustrating how conservative the theoretical upper bounds are.

Most of the core proof logic is relegated to the appendix. Including a brief proof sketch near the main theorems would help highlight the advancements made over the analysis presented by Dmitriev et al. (2026). Additionally, a direct comparison or discussion with CoDiLA[1], ParaSolver[2], PUNT[3], DAPD[4], and Self-refining diffusion [5] would clarify the distinctions regarding grouping selection, intra-block update mechanisms, and theoretical guarantees.

Minor Issues

  • In Appendix C, the term Γpart(t)≤d2log⁡S\Gamma_{\mathrm{part}}(t)\le d^2\log S is used to bound an integral that includes εpart\varepsilon_{\mathrm{part}}, an upper bound on Γpart\Gamma_{\mathrm{part}}. This step requires clarification—for instance, by explicitly using a truncated certificate such as min⁡{εpart,d2log⁡S}\min\{\varepsilon_{\mathrm{part}},d^2\log S\}.
  • The variable rmax⁡r_{\max} in Corollary 1 is not explicitly defined.
  • The sentence following Equation (6) in Section 4.1 is grammatically awkward.
  • The publication year cited for the “first-hitting” sampler in Appendix D is inconsistent with the citation in the main text.

[1] Locally Coherent Parallel Decoding in Diffusion Language Models[J]. arXiv preprint arXiv:2603.20216, 2026.

[2] Parasolver: A hierarchical parallel integral solver for diffusion models[C]//International Conference on Learning Representations. 2025, 2025: 41678-41704.

[3] Parallel sampling from masked diffusion models via conditional independence testing[C]//International Conference on Learning Representations. 2026, 2026: 140485-140521.

[4] DAPD: Dependency-Aware Parallel Decoding via Attention for Diffusion LLMs[J]. arXiv preprint arXiv:2603.12996, 2026.

[5] Self-refining diffusion samplers: Enabling parallelization via parareal iterations[J]. Advances in Neural Information Processing Systems, 2024, 37: 5429-5453.

Questions for authors
  1. Under what representative conditions can the language model construction achieve a query depth of less than dd for a given KL-divergence precision?
  2. How does the explicit sensitivity construction distinguish between different pairs of positions within a dense Transformer? Does this require tighter upper bounds or additional architectural features?
  3. Could the authors provide an example where cross-block dependencies are non-zero and a provable depth advantage is demonstrated?
Reviewer_DxkpOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the problem of sampling tokens in masked diffusion models without losing the dependence between them. The authors propose an algorithm that tackles this problem by dividing tokens into different groups and generating tokens within a group one at a time. As a tradeoff the algorithm has to run many different groups in parallel. Different parallel groups are combined periodically in order to obtain an overall prediction. However, the authors do not evaluate the proposed algorithm in any experiments so its their claims remain experimentally unverified.

Critical strengths

The studied research question is very relevant for masked diffusion models, because once a token is unmasked it cannot be changed anymore.

Critical weaknesses

There are no experiments to experimentally verify the claims.

I cannot even parse the claims because they are so poorly presented, terminology is used before being properly explained.

The method comes with a large computational overhead due to parallel generation which should be quantified.

Furthermore, it would be necessary to compare their method to available baselines such as naively sampling in parallel and choosing the best solution.

Questions for authors

Can any of the authors claims be verified experimentally?

How does the algorithm perform compared to naive or more established baseline algorithms? please also compare in terms of sampling speed, since "fast parallel sampling" is one of the methods promises.

Can the authors please present a accuracy to speed and memory trade off of the proposed algorithms.

The algorithm selects groups based on conservative bounds. can the authors please validate if this conservative group is sufficient in order to identify useful groups?

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

This paper proposes and analyzes a sampler for masked diffusion models (Algorithm 1) using a partition oracle that groups masked coordinates into bounded-size blocks for parallel inter-block and sequential intra-block updates. The key contributions are threefold: (1) Theorem 1 provides a non-asymptotic KL upper bound separating initialization, score estimation, and cross-block dependence errors, highlighting the block-size trade-off between accuracy and query depth. (2) Corollary 1 quantifies query depths across step schedules, showing an O(log⁡d)O(\log d) depth for a disjoint-edge Ising example versus Ω(d)\Omega(\sqrt{d}) for a specific τ\tau-leaping baseline. (3) Theorems 2 and 3 construct sound partition oracles for ferromagnetic Ising models and masked LM predictors. No empirical evaluations are included.

Critical strengths
  • The score assumption is based on average accuracy under the true masking distribution qτq_\tau, but the algorithm queries the model in a "block-frozen" state (one block partially updated, the rest fixed). Equating these two distributions without justification would break the proof. The authors successfully handle this gap by bounding block sizes and using monotone refinement to compare distributions, rigorously deriving the erhe^{rh} factor and the rh≤1rh \le 1 condition. This is a non-trivial technical contribution.
  • Even though the external field changes depending on observed spins, the authors control cross-block information via zero-field susceptibility. Expressing the posterior as an Ising measure on the induced subgraph and handling arbitrary finite external fields are executed without apparent flaws.
Critical weaknesses
  1. The representative acceleration example loses to a fair baseline. The separation in the disjoint-edge Ising model (O(log⁡d)O(\log d) for the proposed method vs. Ω(d)\Omega(\sqrt{d}) for τ\tau-leaping) is skewed because the baseline τ\tau-leaping is not given the pairing information. If the baseline receives the same structural information as the proposed method, exact sampling is possible with only two full-vector queries under the exact score assumption: (i) concurrently sample the first token of each pair from the all-MASK state, and (ii) condition on the first tokens and concurrently sample the second token of each pair. One does not even need to know β\beta. Thus, this separation merely demonstrates the limits of a specific sampler that ignores structural information, rather than proving the proposed algorithm is superior to a simple baseline using the exact same information.

  2. The LM certificate may fail to distinguish token dependencies in common dense Transformer settings. Under standard conditions (full attention, shared projections, and no position-dependent attention bias), the explicit attention-weight bound constructed in Lemma 16 becomes identical across all token pairs: αˉij=1/(1+(d−1)exp⁡(−2gR~2))\bar{\alpha}_{ij} = 1 / (1 + (d - 1) \exp(-2g \tilde{R}^2)). Absolute positional embeddings enter the certification procedure only through a global norm bound, while RoPE rotations are handled through orthogonality. Consequently, positional distinctions are lost in this particular bound construction. This yields uniform weights, causing the certified cut cost to scale as ≥wd(d−r)\ge wd(d-r) and barely decrease (e.g., ≤3%\le 3\% reduction for d=1024,r=32d=1024, r=32), rendering the certificate vacuous for block selection.

  3. Combining Theorems 1 and 3 exponentially amplifies the score error. Substituting εpart\varepsilon_{\text{part}} from Theorem 3 into Theorem 1 for a uniform step schedule yields a score contribution of κ(r)d(edh−1)εscore\frac{\kappa(r)}{d}(e^{dh}-1)\varepsilon_{\text{score}} from the partition term. For small blocks r≪dr \ll d, κ(r)≥d−r\kappa(r) \ge d-r, making κ(r)/d≈1\kappa(r)/d \approx 1. This causes the score error coefficient to become proportional to ≈edh\approx e^{dh}. To maintain this as a dimension-independent constant, one must set h=O(1/d)h = O(1/d), which requires N=Ω(dT)N = \Omega(dT). This entirely eliminates the parallel depth advantage. While this term vanishes if the score is exact, the current manuscript provides no LM conditions where acceleration is actually achieved with non-zero score error and small blocks. Similarly, the connected square lattice Example 1 fails to show sublinear depth gains when applying r=dr=\sqrt{d} and Dpart≲d3/4D_{\text{part}} \lesssim d^{3/4} to depth ≤rN\le rN with a favorable O~(d)\tilde{O}(d) total-query bound.

Questions for authors
  1. In dense Transformers, what is a concrete example where the actual constructions of Lemmas 15–17 yield non-uniform Ωij\Omega_{ij} and practically useful partitions?

  2. In the combined accuracy-depth guarantee of Theorems 1 and 3, what is the specific regime that yields meaningful acceleration under non-zero score error, given the edhe^{dh} factor?

  3. Compared to the two-query baseline mentioned in Weakness 1, what is the advantage of the proposed algorithm? Can you provide a fair comparison with a baseline holding the same structural information, or demonstrate a clear advantage in a connected, non-trivial distribution?

  4. In what resource metric is the method 'fast'? Can you clearly distinguish the claims among the number of intervals NN, parallel depth, total model calls N+dN+d, and actual parallel resources (FLOPs, latency, peak memory)?

Reviewer_HJe9OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies parallel decoding in masked diffusion models, where independently unmasking multiple tokens can introduce error by ignoring conditional dependencies among them. It proposes a partition-based sampler that groups strongly dependent masked coordinates into the same block, processes different blocks in parallel, and performs sequential conditional updates within each block. The paper provides a nonasymptotic KL-divergence analysis that separates initialization error, score-estimation error, and residual cross-block dependence, and relates the resulting sampling accuracy to parallel query depth and block size. It also constructs partition oracles satisfying the proposed assumptions for ferromagnetic Ising models and masked language-model predictors using interaction structure and neural-network sensitivity bounds, respectively.

Critical strengths

None.

Critical weaknesses
  1. The high-level idea of using token dependencies to determine which tokens can be unmasked in parallel substantially overlaps with recent works such as DAPD [1] and DAWN [2]. The main distinction of this paper therefore appears to lie in its theoretical analysis; however, the clearest computational gains are established in an Ising setting whose connection to practical MDM decoding is unclear, while the masked-LM analysis does not go as far as showing that the proposed partitions yield nontrivial gains on actual models. As a result, it is not sufficiently clear what new insight this theory provides for realistic diffusion-LM decoding.

  2. There is also no empirical validation showing whether the proposed partition construction captures meaningful dependencies in trained MDMs, or whether it provides a better quality–speed trade-off than existing dependency-aware decoding methods. Although the authors acknowledge these practical limitations, given that the theoretical analysis alone does not appear sufficient to establish a clear practical advantage, some validation demonstrating the distinctiveness or usefulness of the proposed method and analysis seems necessary.

Questions for authors

Can the authors clarify and substantiate in what sense the proposed analysis and algorithm are substantially more powerful or novel than existing dependency-aware decoding methods?

References

[1] Kim et al., “DAPD: Dependency-Aware Parallel Decoding via Attention for Diffusion LLMs,” ICML, 2026.

[2] Luo et al., “DAWN: Dependency-Aware Fast Inference for Diffusion LLMs,” NeurIPS, 2026.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.