- 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
- 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.
- 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
- 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
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- Markov chain, revealing a contiguous separator of width 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 and . This chain is geometrically mixing, yet
Sampling and independently using their exact marginals instead gives , introducing error despite their spatial separation. In contrast, revealing first ensures , 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.
| Model | Benchmark | DUS NFE | DUS Accuracy (%) | Semi-AR Bisection NFE | Semi-AR Bisection Accuracy (%) |
|---|---|---|---|---|---|
| Dream | GSM8K | 192 | 80.44 | 193.25 | 83.55 |
| Dream | MBPP | 192 | 53.31 | 193.09 | 56.03 |
| Dream | HumanEval | 192 | 39.63 | 192.84 | 48.78 |
| LLaDA | GSM8K | 192 | 82.18 | 198.51 | 81.58 |
| LLaDA | MBPP | 192 | 46.69 | 209.58 | 46.69 |
| LLaDA | HumanEval | 192 | 34.76 | 204.10 | 36.59 |
DUS uses . Our guided semi-AR bisection uses and , 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.
-
Presentation and terminology
- The definitions of Star-DAG and Bottleneck-DAG have indeed been clarified.
- Many wording issues remain. Here are some more examples:
- "corridor" still appears and is now completely undefined.
- "the chain rule over levels yields correctness" — I understand what you mean, but I do not think this is a reasonable phrasing.
- "verifiable sandbox", "mechanistically test", "structural anchors" — all these terms appear only once and are not further established.
- Most sample names in the figures are never referred to in the main text.
- Are a round and a substep the same? If so, use the same term; otherwise, clarify the distinction.
- Are intrinsic block dependence error and intrinsic dependence error the same?
- "A contiguous block of k tokens captures the memory needed to separate the two sides" — what is meant by this?
- "practical decoding" — what is practical decoding?
- Further wording issues remain.
-
Addressed.
-
OK.
-
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.
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=1, since the random walk being considered is first-order Markov, whereas Figure 8 varies k (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.