acceptodds
Under review as a conference paper at ICLR 2027

Walk Fast but Be Careful: Understanding Parallel Sampling in Masked Diffusion

Abstract

In this paper, we use random walks on graphs as a verifiable sandbox for studying parallel sampling strategies in masked diffusion models (MDMs). We train an MDM on random walk samples from a fixed graph. The graph and transition kernel are never shown to the model and serve as latent structure that is both controllable and enables evaluation. The framework provides a validity check for generated walks and a measure of distributional fidelity through the estimated transition kernel. Using simple graphs, we theoretically prove that parallel unmasking via widely used scores such as lowest entropy is not uniformly better than random parallel sampling; even with exact conditional probabilities, performance critically depends on the conditional dependence structure induced by the graph, a phenomenon difficult to isolate in benchmarks like Sudoku. We also develop training-free bisection samplers for MDMs, which take logarithmically many steps in the sequence length and are provably exact for random walks if the learned marginals are exact. Experiments on graph-walk tasks confirm that different parallel samplers perform better on different graph structures. Experiments on pretrained MDMs show that bisection-style samplers provide strong speed-quality tradeoffs on OpenWebText generation and reasoning benchmarks including GSM8K, MBPP, and HumanEval. Together, these results use graph walks to uncover conditional dependence as a key principle of parallel MDM sampling and translate this insight into efficient samplers that transfer to language generation and reasoning.

Primary area:
generative models
Keywords:
masked diffusion models, parallel sampling, graph, random walks, conditional independence, bisection sampling, efficient generation, generative models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_gpuqOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies different sampling strategies for masked diffusion models (MDMs). The paper uses random walks on graphs as a testbed for a "fully controlled" evaluation of MDM samplers. It proposes a sampling strategy for MDMs called bisection samplers, which splits generation into conditionally independent subproblems. Finally, the paper performs experiments on different benchmarks comparing various sampling strategies.

Critical strengths

There has definitely been an explosion of literature on different sampling strategies for MDMs, and a principled approach for comparing them, which this paper delivers, is very welcome. The theoretical results on bisection exactness are interesting. The idea of using random walks on graphs where the full graph topology is unknown to compare sampling strategies to provide an exact validity check is well thought out and, to my knowledge, a novel application of graph random walks in model benchmarking.

Critical weaknesses
  1. The language in the paper is heavily LLM-coded and often very hard to follow. Staying away from any obvious falsities, sentences are often phrased in non-definitive ways. Terms are used sloppily, defined late, or not at all. I will refrain from posting a long list of mis- or unspecified terms and ambiguous sentences, but I encourage the authors to ask an LLM of their choice to check for such terms and phrasings, and a list will be easily generated. Just four examples:
    • Figure 3: "bottleneck gadgets" and "corridors" are, to my understanding, not terms used in graph or ML literature, and to my current understanding contradict definition 2.
    • Section 4: What a bisection level is is never defined.
    • Section 4: 'unrestricted pivots near endpoints may unbalance the subproblems'. The term pivot is not introduced, and it is not clear what "unbalancing the subproblems" means from that phrasing.
    • Conclusion: "larger community hierarchies" -> what does this mean?

etc. etc. Identical concepts are referred to in multiple different terms throughout the paper, so the reader needs to piece together what is currently being discussed. While these phrasings are too vague to be considered wrong, they are not specific enough to be considered scientific writing.

  1. The experiments section insufficiently supports the main claim of the paper. The authors acknowledge that assumption 1 does not necessarily hold in practice and show in Figure 6 that it indeed does not hold in the "sandbox" either. As I understand it, one token at a time random and entropy should give the same score. In my opinion, the results shown in the figures do not clearly follow from the sampling but are confounded by model error. Some benchmarks seem to be single-run, at least, no error bars are shown, so the small differences in score cannot clearly be identified as signal. It is also not clear how NFEs per sequence are adapted for bisection in Figure 8 and why this is not being done in Figure 5. Also, the samplers mentioned in the figure legends are not clearly identifiable with the samplers in the text. In the language section, we lack controls and ablations of different separator sizes. This is worrying because the Markov properties of text are not immediately clear. TV is not reported beyond Figure 5.

[1] Luxembourg, Omer, Haim Permuter, and Eliya Nachmani. "Plan for speed: Dilated scheduling for masked diffusion language models." arXiv preprint arXiv:2506.19037 (2025).

Questions for authors
  1. Since the proposed bisection is similar to the dilated unmasking scheduler, as proposed in [1], could the authors clearly delineate the difference between their proposed bisection sampler and DUS? To my knowledge, DUS uses semi-AR blocks, and the work here uses the full sequence. Does that not confound the comparison?
5 comments

We thank the reviewer for recognizing the motivation behind our graph-walk framework and the theoretical results on bisection sampling. We appreciate the specific suggestions for improving the presentation and experimental evaluation, and address them below.

1. Presentation and terminology

We appreciate the reviewer's detailed comments on the presentation. We would like to clarify that the inconsistencies in terminology arose primarily because our graph constructions are nonstandard and lack established terminology for their components, and because different sections were not fully harmonized, rather than from AI-generated writing. We have since revised the manuscript to ensure more consistent terminology and clearer mathematical descriptions throughout. These revisions are highlighted in blue in the uploaded revised manuscript.

In particular, we have revised the definitions of the Star-DAG and Bottleneck-DAG, clarified the meaning of bisection levels and pivot selection, unified the sampler terminology, and removed ambiguous expressions from the discussion and conclusion. We thank the reviewer for the specific suggestions, which have helped us improve the presentation of the paper.

2. Model approximation error and conditional dependence

The reviewer is correct that one-token-at-a-time random and entropy-based sampling generate the same target distribution under Assumption 1. This follows from the probability chain rule, as established in Lemma 5. With learned conditional marginals, however, different sampling orders can accumulate different approximation errors, as also studied by Kim et al. [1].

The two sources of error are precisely what we examine in lines 42–75 and 108–111 of Section 1. Importantly, our graph experiments explicitly separate model approximation error from the conditional dependence error introduced by parallel sampling. Equation (1), following Ben-Hamu et al. [2], bounds the sampling error by these two terms. Since the graph transition kernel is known, both can be computed directly, as detailed in Appendix J.1. In fact, Figure 1 shows that the marginal approximation error is roughly an order of magnitude smaller than the conditional total correlation (TC), suggesting that conditional dependence is the dominant source of error in these graph experiments, as also recognized by Reviewer v8ib.

3. Experimental reporting and ablations

Error bars. Our graph experiments include error bars, although some are too small to be visible. The primary graph experiments are averaged over five runs, while the higher-order experiment in Figure 6 reports variability across four batches of generated samples. We will clarify these details in the manuscript.

Regarding NFEs. Figure 5 reports fixed bisection with k=1k=1, since the random walk being considered is first-order Markov, whereas Figure 8 varies kk (and hence the NFEs) to study the accuracy–NFE tradeoff.

Regarding sampler terminology. We have clarified the sampler terminology in the revised manuscript and will make the parameter choices for the reported configurations explicit.

Regarding TV. We report transition TV for first-order random walks in Figure 5 and endpoint-conditional TV in Figure 12 (Appendix J.2). For higher-order walks, reliable estimation of transition TV requires substantially more samples, since the number of possible conditioning histories grows exponentially with the Markov order. With limited samples, many histories are observed too infrequently to estimate their conditional distributions accurately. We therefore report coherence, which can be evaluated exactly for each generated sequence using the known transition rule. For language generation experiments, since the ground-truth distribution is unavailable, we do not report TV. We will clarify these distinctions in the manuscript.

4. Comparison with DUS and application to language

We agree that DUS [3] is an important related method and that the original language experiments compared different decoding frameworks. Our original experiments compared global bisection with semi-autoregressive DUS, motivating the additional comparisons presented below.

Difference between bisection and DUS. Although both DUS and bisection seek to reduce dependence among tokens sampled in parallel, their theoretical principles differ. DUS is motivated by weaker dependence between spatially separated positions and uses a dilated schedule to reveal dispersed positions within each block. Bisection, however, relies on revealing conditioning separators. For an order-kk Markov chain, revealing a contiguous separator of width kk makes the remaining intervals conditionally independent. Thus, our exactness guarantee follows directly from the Markov property and does not require a rapid-mixing assumption, unlike the dependence-decay analysis in [3].

For a concrete example, consider a stationary binary first-order Markov chain with transition probabilities P(Xt+1=Xt)=0.9P(X_{t+1}=X_t)=0.9 and P(Xt+1≠Xt)=0.1P(X_{t+1}\neq X_t)=0.1. This chain is geometrically mixing, yet

P(X1=X3)=0.92+0.12=0.82.P(X_1=X_3)=0.9^2+0.1^2=0.82.

Sampling X1X_1 and X3X_3 independently using their exact marginals instead gives P(X1=X3)=0.5P(X_1=X_3)=0.5, introducing error despite their spatial separation. In contrast, revealing X2X_2 first ensures X1⊥X3∣X2X_1\perp X_3\mid X_2, allowing both positions to be sampled in parallel exactly. This illustrates the distinction: spatial separation reduces dependence under mixing assumptions, whereas conditioning separators eliminate it exactly for finite-order Markov chains.

To address the experimental comparison further, we have extended bisection to semi-autoregressive generation and evaluated it on GSM8K, MBPP, and HumanEval with both Dream and LLaDA.

ModelBenchmarkDUS NFEDUS Accuracy (%)Semi-AR Bisection NFESemi-AR Bisection Accuracy (%)
DreamGSM8K19280.44193.2583.55
DreamMBPP19253.31193.0956.03
DreamHumanEval19239.63192.8448.78
LLaDAGSM8K19282.18198.5181.58
LLaDAMBPP19246.69209.5846.69
LLaDAHumanEval19234.76204.1036.59

DUS uses B=8B=8. Our guided semi-AR bisection uses B=16B=16 and K=1K=1, with entropy guidance for Dream and margin guidance for LLaDA. Mean NFE is reported. We also provide a similar experiment for MATH500 in response to Reviewer v8ib.

The new results show that score-guided semi-autoregressive bisection achieves competitive accuracy with DUS at comparable sampling budgets, with improvements in several settings. These results demonstrate that bisection can also be used effectively within the same semi-autoregressive framework as DUS.

We also clarify that our theoretical analysis does not require natural language to be exactly finite-order Markov. Previous work provides motivation for studying Markov-inspired structure in language [4, 5], but we do not impose a finite-order context restriction on the denoiser. At each step, it conditions on all previously revealed tokens, including distant ones. Our language experiments investigate whether the sampling strategy motivated by the graph analysis remains effective beyond the theoretical setting. Please see our response to Reviewer v8ib for further details.

References

[1] J. Kim et al. Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions. ICML, 2025. https://arxiv.org/abs/2502.06768

[2] H. Ben-Hamu et al. Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking. NeurIPS, 2025. https://openreview.net/forum?id=WBcBhT1NKO

[3] O. Luxembourg, H. Permuter, and E. Nachmani. Plan for Speed: Dilated Scheduling for Masked Diffusion Language Models. ICML, 2026. https://arxiv.org/abs/2506.19037

[4] O. Zekri et al. Large Language Models as Markov Chains. arXiv:2410.02724, 2024. https://arxiv.org/abs/2410.02724

[5] S. Sun et al. Do Long-Range Language Models Actually Use Long-Range Context? EMNLP, 2021. https://arxiv.org/abs/2109.09115

Thank you for providing these detailed responses to my review.

  1. Presentation and terminology

    • The definitions of Star-DAG and Bottleneck-DAG have indeed been clarified.
    • Many wording issues remain. Here are some more examples:
      1. "corridor" still appears and is now completely undefined.
      2. "the chain rule over levels yields correctness" — I understand what you mean, but I do not think this is a reasonable phrasing.
      3. "verifiable sandbox", "mechanistically test", "structural anchors" — all these terms appear only once and are not further established.
      4. Most sample names in the figures are never referred to in the main text.
      5. Are a round and a substep the same? If so, use the same term; otherwise, clarify the distinction.
      6. Are intrinsic block dependence error and intrinsic dependence error the same?
      7. "A contiguous block of k tokens captures the memory needed to separate the two sides" — what is meant by this?
      8. "practical decoding" — what is practical decoding?
      9. Further wording issues remain.
  2. Addressed.

  3. OK.

  4. Thanks for clearly delineating DUS and bisection and for adding these relevant experiments. However, I still have the following issue with the language generation section: "Our theoretical analysis does not require natural language to be exactly finite-order Markov" — to my understanding, it does. The authors show empirically that bisection improves performance in language generation, which is an interesting result, but it does not follow from the theory. The authors themselves argue that bisection remains effective "beyond the theoretical setting." I would ask for this to be made explicit in the text.

I have raised my score to 2 and would consider raising it further if the text is further revised.

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

The paper studies parallel unmasking in masked diffusion models, where a block of tokens is sampled from a product of one-token marginals. The resulting error splits into a marginal-approximation term and the conditional total correlation (TC) of the block, which per-token scores such as entropy or confidence do not control. The authors (i) train MDMs on random walks over a hidden graph, which gives exact validity metrics and exact per-context TC, and show that sampler rankings follow TC and change with graph structure; (ii) prove on two toy DAG families that lowest-entropy unmasking can be better or worse than random unmasking; and (iii) propose bisection samplers that reveal a separator block of k tokens and then recurse on the independent intervals, which are exact for order-k Markov walks under exact conditionals with logarithmic depth. Bisection also gives good speed–quality trade-offs for pretrained Dream/LLaDA on code benchmarks and for an OpenWebText MDM.

Critical strengths
  1. A clean, verifiable sandbox that isolates the quantity existing heuristics ignore. Language and Sudoku do not cleanly separate "which positions are certain" from "which positions can be revealed together": commonly used, heavily constrained Sudoku instances are often uniquely solvable, so TC vanishes, and in language model error, sampler error and evaluation noise are entangled. The hidden-graph walks make the dependence structure controllable and checkable, and TC and the marginal error are computed exactly for each evaluated context (App. J.1). The finding that TC dominates and tracks sampler ranking, together with the two provable separations (entropy wins on one constructed family, random wins on another), gives a convincing and simple message: per-token uncertainty is only a proxy, and the dependence among simultaneously revealed tokens must be controlled.

  2. The insight is turned into a simple, training-free algorithm with a guarantee, and it transfers to real models. Bisection is easy to implement, needs no extra model, is exact for order-k Markov chains under exact conditionals, and has logarithmic parallel depth. Experiments show that the guarantee-driven design matters on graphs (coherence close to one-at-a-time sampling with far fewer NFEs, and coherence rising as the separator size approaches the true order). The same schedule also gives good trade-offs on MBPP/HumanEval and OpenWebText with pretrained models. Papers that combine a controlled analysis, a provable method and real-model evidence are not common in this area.

Critical weaknesses
  1. The link between the graph-walk theory and the language results is not established, and the closest prior method is not compared on the graph benchmark. The exactness of bisection relies on the data being order-k Markov with a known k. Language is not, and the paper itself writes only that the gains on language "may be because" the model uses long-range context. Without a mechanism, it is unclear whether the real-model gains come from the conditional-independence principle or simply from a coarse-to-fine spaced schedule. A closely related method, DUS (Luxembourg et al., 2025), is also a coarse-to-fine dilated schedule; it appears only as a semi-AR baseline in the language experiments, is not discussed in the related work, and is absent from all graph-walk experiments, which are exactly where the claimed advantage (separator width k, exactness) could be tested directly, especially on order-k walks. In addition, the paper provides no way to estimate or exploit dependence in language (k is a given hyperparameter), so the "dependence" diagnosis does not guide the method outside of the sandbox.

  2. The real-model evaluation is narrow, and the evidence is not as strong as the claims. Reasoning is evaluated on only three tasks (GSM8K, MBPP, HumanEval) and two models; harder standard benchmarks such as MATH500 are missing, which matters because on GSM8K the dilated semi-AR sampler is better than bisection at larger budgets, and the authors attribute this to the left-to-right structure of math solutions, a claim that is not tested. The comparison is made by reading curves in small figures, without tables, error bars or matched-NFE numbers, and an adaptive confidence-threshold baseline such as Fast-dLLM is not included.

Questions for authors
  1. Could the authors clarify whether bisection's gains on language come from exploiting approximate conditional independence or more generally from its coarse-to-fine spacing, and how it relates conceptually to DUS?
  2. How should the separator width and schedule be chosen for natural language, where the order-k Markov assumption does not directly apply?
3 comments

We thank the reviewer for the thoughtful assessment and for recognizing the value of our graph-walk framework, theoretical guarantees, and experiments on pretrained models. We address the connection to language generation, the distinction from DUS, and the additional experimental comparisons below.

1. Connection between graph analysis and language generation: Our graph-walk framework allows us to isolate model approximation error from the conditional dependence error introduced by parallel sampling, as demonstrated in Figure 1. This analysis motivates a bisection sampler that is provably exact for finite-order Markov distributions under perfect conditional marginals.

Previous work provides motivation for studying Markov-inspired structure in language. Zekri et al. [1] establish a finite-order Markov representation of finite-context autoregressive language models. Khandelwal et al. [2] find that neural language models rely more strongly on nearby context, while Sun et al. [3] observe that distant context benefits relatively few predictions in their evaluated models. Furthermore, Hahn et al. [4] study information locality in natural language, providing an information-theoretic motivation for considering local dependencies.

Importantly, when applying bisection to language models, we do not restrict the denoiser to a finite-order Markov context. Each prediction conditions on all previously revealed tokens, including distant ones. Thus, while the Markov property provides the theoretical motivation for the sampling order, the method can still use long-range dependencies in language. Our goal is not to claim that natural language exactly satisfies our theoretical assumptions, but to investigate whether the sampling strategy developed from this analysis also performs well on language generation tasks.

2. Comparison with DUS: We agree that DUS [5] is an important related method and will expand its discussion in the paper. Although both DUS and bisection seek to reduce dependence among tokens sampled in parallel with logarithmic sampling budget, their theoretical principles differ significantly. DUS is motivated by weaker dependence between spatially separated positions: in each parallel sampling round, it reveals the positions that are maximally dispersed within a block. Bisection, however, relies on the principle of revealing conditioning separators: for an order-(k) Markov chain, revealing a contiguous separator of (k) positions makes the remaining intervals conditionally independent. Thus, our exactness guarantee follows directly from the Markov property and does not require a rapid-mixing assumption.

We compare bisection with AR-style DUS in the paper since it is their strongest setting: the performance of the DUS sampler degrades as its block size increases (worst at the global block). However, to address your comment, we have now extended bisection to semi-autoregressive generation and evaluated it on GSM8K, MBPP, and HumanEval with both Dream and LLaDA. The new results show that score-guided semi-AR bisection achieves competitive or better accuracy than DUS at comparable sampling budgets, including at larger NFE budgets where the original global bisection results were weaker. The numerical comparisons are summarized below.

ModelBenchmarkDUS NFEDUS Accuracy (%)Semi-AR Bisection NFESemi-AR Bisection Accuracy (%)
DreamGSM8K19280.44193.2583.55
DreamMBPP19253.31193.0956.03
DreamHumanEval19239.63192.8448.78
LLaDAGSM8K19282.18198.5181.58
LLaDAMBPP19246.69209.5846.69
LLaDAHumanEval19234.76204.1036.59
DUS uses B = 8. Our guided semi-AR bisection uses B = 16 and K = 1, with entropy guidance for Dream and margin guidance for LLaDA. Mean NFE is reported. These experiments demonstrate that bisection can also be effectively combined with semi-autoregressive decoding.

3. Choosing the separator width: In our theoretical analysis, the separator width k matches the Markov order, ensuring conditional independence between intervals. For natural language, k is instead a hyperparameter balancing additional conditioning context against sequential denoising steps, and can be selected based on validation performance at a given inference budget. Figure 6 already examines separator widths from 1 to 6 on order-4 random walks, illustrating how the choice of separator width affects coherence. We will clarify this distinction between the theoretical and practical roles of k.

4. Additional experiments: In addition to the existing set of experiments on GSM8K, MBPP, HumanEval, we have now added an experiment comparing score-guided semi-autoregressive bisection and DUS on MATH500. Guided semi-AR bisection improves accuracy by 4.6 percentage points on Dream and 5.8 percentage points on LLaDA, with comparable NFEs and wall-clock latency.

ModelSamplerCorrect / 500AccuracyMean NFEMean latency
DreamDUS173 / 50034.6%192.0035.25 s
DreamGuided semi-AR bisection196 / 50039.2%194.7635.91 s
LLaDADUS191 / 50038.2%192.0038.21 s
LLaDAGuided semi-AR bisection220 / 50044.0%190.4437.96 s

Regarding Fast-dLLM [6], they combine block-wise KV caching with confidence-aware parallel decoding. Our bisection sampler addresses the latter aspect and can, in principle, be incorporated within Fast-dLLM's block-wise decoding framework while retaining its caching mechanism. Thus, the two approaches are complementary. Our experiments focus on comparing sampling strategies under the same pretrained model and inference implementation, rather than combining different inference optimizations.

References

[1] O. Zekri et al. Large Language Models as Markov Chains. arXiv:2410.02724, 2024. https://arxiv.org/abs/2410.02724

[2] U. Khandelwal et al. Sharp Nearby, Fuzzy Far Away: How Neural Language Models Use Context. ACL, 2018. https://aclanthology.org/P18-1027/

[3] S. Sun et al. Do Long-Range Language Models Actually Use Long-Range Context? EMNLP, 2021. https://arxiv.org/abs/2109.09115

[4] M. Hahn, J. Degen, and R. Futrell. Modeling Word and Morpheme Order in Natural Language as an Efficient Trade-Off of Memory and Surprisal. Psychological Review, 2021. https://doi.org/10.1037/rev0000269

[5] O. Luxembourg, H. Permuter, and E. Nachmani. Plan for Speed: Dilated Scheduling for Masked Diffusion Language Models. ICML, 2026. https://arxiv.org/abs/2506.19037

[6] C. Wu et al. Fast-dLLM: Training-free Acceleration of Diffusion LLM by Enabling KV Cache and Parallel Decoding. ICLR, 2026. https://arxiv.org/abs/2505.22618

Thank you for the response and additional experiments. The new DUS comparisons and MATH500 results address most of my concerns. I will maintain my score of 3.

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

This paper focuses on parallel sampling for MDM. The author first claimed that the problem of parallel sampling comes from i. Approximation error; ii. dependency between tokens. To verify this, the author uses a graph random walk to study the conditional dependency. It demonstrates that the optimal sampler for a graph varies. To fix this, the author proposed a bisection sampler to break the dependency and showed improved performance on text and reasoning tasks.

Critical strengths
  1. The paper properly formulates the root cause of the error in parallel sampling of MDM.
  2. The experiments on graph random walks are interesting and reasonable, indicating that there is coupling between sampler choices and graph type.
  3. The proposed bisection sampler is simple and easy to follow.
Critical weaknesses
  1. The connection between graph analysis and language model results is not sufficiently supported in the paper. Improved results do not necessarily mean the proposed method fixes the dependency problem.
  2. The comparison with DUS is not fully controlled. DUS uses semi-AR, but bisection uses global.
  3. Latency is not reported. This paper only reports NFE.
Questions for authors
  1. Can the author provide some evidence that the improvement in MDM comes from the dependency fix? The Bisection sampler does work in graph random walks, but do these assumptions still hold in LM?
  2. Does the bisection sampler still gain its improvement under matched block settings with DUS?
  3. Can the authors provide the stopping criteria and latency results?
4 comments

We thank the reviewer for the positive assessment of our error decomposition, graph experiments, and proposed sampler. We address the connection to language generation, the comparison with DUS, and latency below.

1. Connection between graph walks and language generation: Our graph-walk framework allows us to separate model approximation error from the conditional dependence error introduced by parallel sampling, as demonstrated in Figure 1. This analysis motivates a bisection sampler that is provably exact for finite-order Markov distributions under perfect conditional marginals.

Previous work provides motivation for studying Markov-inspired structure in language. Zekri et al. [1] establish a finite-order Markov representation of finite-context autoregressive language models. Khandelwal et al. [2] find that neural language models rely more strongly on nearby context, while Sun et al. [3] observe that distant context benefits relatively few predictions in their evaluated models. Furthermore, Hahn et al. [4] study information locality in natural language, providing an information-theoretic motivation for considering local dependencies.

Importantly, when applying bisection to language models, we do not restrict the denoiser to a finite-order Markov context. Each prediction conditions on all previously revealed tokens, including distant ones. Thus, while the Markov property provides the theoretical motivation for the sampling order, the method can still use long-range dependencies in language. Our goal is not to claim that natural language exactly satisfies our theoretical assumptions, but to investigate whether the sampling strategy developed from this analysis also performs well on language generation tasks.

2. Comparison with DUS: We thank the reviewer for raising this concern. The original experiments compared global bisection with semi-autoregressive DUS[5]. We did so to compare bisection with the strongest setting of the DUS sampler: the performance of the DUS sampler degrades as its block size increases (worst at the global block). To address this further, we have conducted additional experiments applying bisection within the same semi-autoregressive decoding framework.

The new results show that score-guided semi-autoregressive bisection achieves competitive or better accuracy than DUS at comparable sampling budgets, including at larger NFE budgets where the original global bisection results were weaker. The numerical comparisons are summarized below.

ModelBenchmarkDUS NFEDUS Accuracy (%)Semi-AR Bisection NFESemi-AR Bisection Accuracy (%)
DreamGSM8K19280.44193.2583.55
DreamMBPP19253.31193.0956.03
DreamHumanEval19239.63192.8448.78
LLaDAGSM8K19282.18198.5181.58
LLaDAMBPP19246.69209.5846.69
LLaDAHumanEval19234.76204.1036.59

DUS uses B = 8. Our guided semi-AR bisection uses B = 16 and K = 1, with entropy guidance for Dream and margin guidance for LLaDA. Mean NFE is reported. These experiments demonstrate that bisection can also be effectively combined with semi-autoregressive decoding.

3. Latency and stopping criteria: Our samplers terminate when all masked positions are revealed (Algorithms 1–2, Appendix E). We primarily report NFEs because all methods use the same pretrained model and generation length, making per-evaluation costs comparable. We additionally report wall-clock latency for MATH500 in our response to Reviewer v8ib, finding a consistent ratio of approximately 5.5 NFEs per second.

References

[1] O. Zekri et al. Large Language Models as Markov Chains. arXiv:2410.02724, 2024. https://arxiv.org/abs/2410.02724

[2] U. Khandelwal et al. Sharp Nearby, Fuzzy Far Away: How Neural Language Models Use Context. ACL, 2018. https://aclanthology.org/P18-1027/

[3] S. Sun et al. Do Long-Range Language Models Actually Use Long-Range Context? EMNLP, 2021. https://arxiv.org/abs/2109.09115

[4] M. Hahn, J. Degen, and R. Futrell. Modeling Word and Morpheme Order in Natural Language as an Efficient Trade-Off of Memory and Surprisal. Psychological Review, 2021. https://doi.org/10.1037/rev0000269

[5] O. Luxembourg, H. Permuter, and E. Nachmani. Plan for Speed: Dilated Scheduling for Masked Diffusion Language Models. ICML, 2026. https://arxiv.org/abs/2506.19037

I thank the authors for the rebuttal. I have read the rebuttal carefully. However, I find the connection between graph random walks and LLMs vague. The analysis within graph random walks is reasonable and well-motivated. But I don't see why this applies to LLMs. The guarantees for exactness for bisection rely on order-k Markov separators. But this assumption doesn't hold for natural language. The bisection sampler therefore becomes a heuristic. The paper should offer more evidence that the bisection sampler does improve the conditional independence principle. The proposed sampler is quite simple. So analysis of why it works becomes the core contribution of the work. However, for the current work, this is missing. Therefore, I maintain my score.

AuthorsOpenReview ↗

Conditional dependence for natural language

We thank the reviewer for the follow-up. We agree that improvements in downstream performance alone may not establish that bisection reduces conditional dependence in language. To address this concern, we conducted additional experiments on the pretrained OpenWebText MDM using the conditional-dependence diagnostic from PUNT [Azangulov et al., Sec. 4.3, Eq. (3)].

Measuring dependence among parallel updates. Let UrU_r denote the positions revealed before generation step rr, and let Br=(br,1,…,br,mr)B_r=(b_{r,1},\ldots,b_{r,m_r}) denote the positions committed in that step, ordered by decreasing model confidence. Following Azangulov et al., for each j≥2j\geq2, we compute δr,j=KL(pθ,br,j(⋅∣xUr,ybr,<j) ∥ pθ,br,j(⋅∣xUr)),\delta_{r,j}=\mathrm{KL} \left(p_{\theta, b_{r,j}}(\cdot\mid x_{U_r},y_{b_{r,<j}})\,\middle\|\,p_{\theta, b_{r,j}}(\cdot\mid x_{U_r})\right), where ybr,<jy_{b_{r,<j}} contains the sampled values of the preceding tokens in the same parallel update.

Thus, δr,j\delta_{r,j} measures how much a token’s predicted distribution changes when tokens committed alongside it become visible. We aggregate these changes across the sequence as Dparallel(x)=∑r∑j=2mrδr,j.D_{\mathrm{parallel}}(x)=\sum_r\sum_{j=2}^{m_r}\delta_{r,j}. Smaller values indicate that jointly committed tokens are more stable under this additional conditioning. We evaluate 64 generated sequences of length 1024 per setting and report the mean cumulative diagnostic in nats per sequence, together with its standard error.

Comparison with DUS. Plain bisection substantially reduces DparallelD_\mathrm{parallel} (lower is better) at closely comparable generation budgets:

Bisection NFEsBisection Dparallel(↓)D_{\mathrm{parallel}} (\downarrow)DUS NFEsDUS Dparallel(↓)D_{\mathrm{parallel}} (\downarrow)Ratio: DUS / bisection
5715.6±1.0215.6\pm1.0256265.1±4.73265.1\pm4.73≈17×\approx17\times
976.26±0.596.26\pm0.5996233.3±4.65233.3\pm4.65≈37×\approx37\times
1612.47±0.272.47\pm0.27160183.7±6.51183.7\pm6.51≈74×\approx74\times

Importantly, the improvements in DparallelD_\mathrm{parallel} persist even when the average marginal entropies of the revealed positions are similar. For example, at roughly 160160 NFEs, marginal entropies are comparable for bisection and DUS (2.902.90 versus 2.832.83 nats), however the mean conditional-dependence diagnostic (normalized by sequence length) is substantially smaller for bisection (0.00290.0029 versus 0.21260.2126). This directly supports our central hypothesis that marginal uncertainty alone does not capture the dependence introduced by parallel sampling.

Other samplers. At exactly 11 NFEs, plain bisection achieves a cumulative diagnostic of 333.4, compared with 720.6 for greedy entropy selection and 548.7 for random selection using exponential schedules. Entropy-guided bisection also achieves a diagnostic comparable to EB with substantially fewer evaluations: 1.90±0.191.90\pm0.19 at 234.2 NFEs, compared with 2.03±0.532.03\pm0.53 at 608.9 NFEs for EB.

We have included the complete dependence-versus-NFE comparison in Figure 10 in the main paper (page 9, 10). These measurements provide direct empirical evidence that our bisection sampler reduce conditional dependence for language-generation. Please let us know if any further concerns remains, and we would be happy to answer.

[1] Azangulov et al., Parallel Sampling from Masked Diffusion Models via Conditional Independence Testing. arXiv:2510.21961.

As the author/reviewer discussion period comes to an end, please let us know if our response addresses your questions. We would be happy to provide any further clarification if needed.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Comment

We thank the reviewers for their careful assessment and constructive feedback. We would like to emphasize the main contributions of our work and clarify how the theoretical and empirical results fit together. Our main contribution is a controlled framework for understanding parallel sampling in masked diffusion models, together with a sampling algorithm motivated by this analysis. The work has three components.

1. Understanding parallel sampling through graph walks. We introduce a setting where the underlying distribution is known, allowing us to separately measure model approximation error and conditional dependence error. Our experiments show that the relative performance of popular parallel sampling algorithms, including entropy, confidence, margin, and random unmasking, depends on the graph structure. We further prove that entropy-based and random parallel sampling can each outperform the other on different graphs, even with perfect conditional marginals.

2. A theoretically justified sampling algorithm. Motivated by this analysis, we propose bisection sampling, which reveals conditioning separators before sampling the remaining intervals in parallel. For finite-order Markov chains, this yields exact sampling under perfect conditional marginals, with logarithmic parallel depth.

3. Empirical transfer to diffusion language models. Previous work provides supporting motivation for studying Markov structure in language models. Zekri et al. [1] formulate finite-context autoregressive language models as Markov chains, while Sun et al. [2] find that distant context has limited influence on predictions in certain settings. While Natural language may not exactly satisfy the Markov assumptions in our theory, these studies provide theoretical and empirical motivation for considering Markov properties to the distributions represented by language models. Building on these findings, we study whether our theoretical intuition behind the bisection algorithm transfers to language and reasoning benchmarks, with encouraging results presenting a smooth tradeoff between speed and accuracy while outperforming several parallel sampling algorithms.

In response to the reviewers, we have conducted additional experiments comparing bisection with DUS under the same semi-autoregressive decoding framework on Dream and LLaDA. On the new MATH500 benchmark, guided bisection improves accuracy from 34.6% to 39.2% on Dream and from 38.2% to 44.0% on LLaDA, with comparable NFEs and wall-clock latency. We also observe improvements on GSM8K, MBPP, and HumanEval in several settings, notably on Dream HumanEval, where accuracy increases from 39.63% to 48.78%. Together with our original comparisons against other parallel sampling methods, these results further support the practical effectiveness of bisection beyond graph walks, while maintaining favorable accuracy–efficiency tradeoffs.

References

[1] O. Zekri et al. Large Language Models as Markov Chains. arXiv:2410.02724, 2024. https://arxiv.org/abs/2410.02724

[2] S. Sun et al. Do Long-Range Language Models Actually Use Long-Range Context? EMNLP, 2021. https://arxiv.org/abs/2109.09115

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.