- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies the decoding algorithm for masked diffusion models. The paper assumes an underlying target distribution that admits a forest-like structure. They prove that we could achieve approximate sampling using sub-linear (to sequence length) calls to the approximate conditional oracle and decoding. It also provides a lower-bound for the problem. The paper also provides simulated experiment for the advantage of the proposed decoding algorithm.
Critical strengths
This paper studies a relevant problem, proposes a nice formulation, and gives decent results. In particular, it proves that approximately sampling a forest-like distribution is possible in (omitting other factors) calls to the oracle and decoding. It also proves that the problem admits a lower bound of .
Critical weaknesses
The biggest weakness is presentation. Though I have directly worked on relevant subject, it is hard for me to follow some details as well as the motivations. The authors should do a better job explaining relevant concepts, setting up notations, and interpreting the technical results. See more in the question section.
Questions for authors
- Can authors provide better motivations for studying a forest-like distribution? A forest-like distribution is not general enough to capture natural language or protein structures. For example, in 'John wants to leave', John is the subject of wants and leave, while leave is a complement of wants, and hence they form a triangle relation instead of a tree-like relation. It could be equally useful if the authors could provide experiments on real-world data, including but not limited to language and protein, rather than just synthetic data.
- Can authors provide high level intuitions about the technical contents in section 2.1? Now they are just listing definitions without explanation.
- Could the authors provide comparison between the upper bound and lower bound, and provide some interpretations?
- Could the authors provide analysis of how existing decoders would perform on the proposed distribution?
Response to Reviewer V5Vt
We thank the reviewer for the detailed review.
W1 (presentation). The revision clarifies the motivation for hidden forests in the introduction (Q1), adds intuition for the notation and assumptions in Section 2 (Q2), and explains what the bounds establish and leave open (Q3).
Q1 (why forests; real data). We agree that a forest cannot represent the triangle in your example. Our aim is to understand, in a tractable setting, how selected tokens can simplify generation of the rest. This question is motivated in part by SAID [1] and ADLM [2], which use selected tokens or their predictions to reduce uncertainty about the remaining tokens. In a forest, revealing separator tokens makes the remaining components independent, allowing one token per component to be sampled in parallel. With exact conditionals, a known forest permits O(logN) rounds; we study the cost of discovering and exploiting this structure.
Syntax provides complementary structural intuition. Basic dependency parses [3] connect words to their heads, while program syntax trees organize nested expressions and statements. These hierarchies motivate our use of forest factorization as a tractable model of token dependencies.
On real data, we added experiments using frozen CoDA-v0-Instruct [4] on all 90 MBPP validation tasks [5], with one completion per task and setting. Among evaluated settings, some of ours lie on the empirical Pareto frontier for test failure rate versus total model calls and versus sampling time (Fig. 3; Appendix L).
Q2 (intuition for Section 2.1). The revision adds intuition alongside the definitions.
Q3 (upper vs. lower bound). At fixed accuracy, Theorem 3.1 gives Q=O~(d2N1/(3s)) probes and R=O~(N/d) commit rounds. Here s>1 is the rank-frequency exponent and d the degree cutoff. In Q, N1/(3s) bounds the number of token values tested per position, and d2 covers screening up to degree d; N/d in R covers singleton peeling. Q's bound grows with d and R's falls; balancing them gives O~(N2/3+1/(9s)) total submissions.
Theorem 3.2 requires Q=Ω(N1/(3s)) or R=Ω(N1/3) in the worst case. It uses an adversarial approximate oracle satisfying our accuracy assumption to hide informative tokens among Θ(N1/(3s)) candidates. Thus the vocabulary-search factor agrees, but the lower bound does not show that our extra screening and peeling costs are necessary. We suspect these costs can be reduced, but making the hidden graph harder to infer may also strengthen the lower bound. The bounds do not match, and the optimal total cost remains open.
Q4 (existing decoders on hidden forests). As a representative example, consider entropy-based decoders [7,8]. Even conditionally independent positions can have high marginal entropy, making entropy budgets conservative. Larger batches, however, risk sampling dependent positions independently. We conjecture that this tradeoff can limit their efficiency on hidden forests. Our probes instead seek to identify dependencies and exploit conditional independence.
We added fixed-count and entropy-bounded decoder comparisons on four exact-oracle forest families (Fig. 3; Appendix K). Among tested settings, some of ours lie on the empirical TV–query Pareto frontier in all four families, and the TV–time frontier in three (excluding binary trees).
[1] Li et al. (2026), SAID, arXiv:2606.04974.
[2] Rout et al. (2025), ADLM, arXiv:2505.18456.
[3] de Marneffe et al. (2021), Universal Dependencies, CL 47(2):255–308.
[4] Chen et al. (2025), CoDA, arXiv:2510.03270.
[5] Austin et al. (2021), MBPP, arXiv:2108.07732.
[6] Zipf (1949), Human Behavior and the Principle of Least Effort.
[7] Ben-Hamu et al. (2025), arXiv:2505.24857.
[8] Cai & Li (2026), arXiv:2603.22248.