acceptodds
Under review as a conference paper at ICLR 2027

Tree Depth for Masked Diffusion: Exact Unmasking in Ferromagnetic Ising Models

Abstract

Masked models predict every unrevealed coordinate in one evaluation, but independent parallel commitments can distort the joint law even when the one-coordinate conditionals are exact. Block size or marginal confidence alone does not determine which variables are conditionally independent given prior reveals, or the minimum number of rounds for exact sampling. To characterize both from the dependency graph, we study ferromagnetic Ising models, classical graphical models from statistical physics with local attractive interactions. We prove that independent parallel sampling is exact if and only if removing previously revealed vertices leaves no path between any two variables sampled together. Layers of a minimum-height elimination forest attain the minimum round count for exact fixed commit-once sampling, equal to tree depth, the minimum forest height. Below this round threshold, every fixed schedule incurs positive forward Kullback–Leibler divergence, which measures distributional mismatch; for learned conditionals, an exact decomposition separates this factorization cost from model error. With planner-aware training, our schedules improve conditional prediction quality at matched model-call budgets and better preserve dependencies in generated samples. In-distribution comparisons with dependency-guided baselines show lower prediction error at comparable or shorter end-to-end decoding times.

Primary area:
generative models
Keywords:
masked generative models, parallel decoding, ferromagnetic Ising models, tree depth, conditional independence, exact sampling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_V4EcOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work tries to speed up sampling by devising a parallel schedule that, in principle, allows for exact sampling. Then it combines this sampling schedule with an approximate conditional diffusion sampler to produce a practical method that is both faster and more accurate. One can always sample exactly from any distribution using an AR schedule: sample one variable at a time conditional on the already-sampled variables. That approach is exact, but takes as many sampling rounds as variables one wants to sample. The insight of the paper is that when the already sampled variables break the graph structure of the graphical model into disjoint regions, it is possible to sample one variable per region in parallel without losing exactness. By recursively breaking a graph into disjoint regions in this way, one can create a "sampling tree", whose depth indicates how many rounds of sampling are needed to achieve exact sampling. Depending on the graph topology, this can speed things up significantly: from a naive AR sampler that needs O(N) rounds to a tree-depth sampler that with a favorable topology only needs O(log(N)) rounds.

The target model in the study is ferromagnetic Ising. Although the ferromagnetic property is not needed for the proposed method to work, it is needed to prove the optimality of the proposed schedule.

Of course, for all of this to work, we need to be able to sample from the conditionals that the parallel schedule requires. This is only done approximately, using a conditional diffusion sampler. The sampler can be trained following the proposed schedule, which is the combination that makes this approach the best among the compared approaches. However, note that the benefits of this are a) topology dependent and b) require prior knowledge of the topology of the Ising model. The main experiment in Table 1 only considers the most favorable settings.

Overall, interesting paper, but the practical benefits might be very limited and the shown experiments give a structural advantage to the proposed method, see the Weaknesses section below.

Critical strengths
  1. Two theorems (Residual-component criterion and Tree-depth upper bound and exact characterization) that usefully answer the question of how and how much it is possible to parallelize sampling while keeping exactness (assuming exact conditionals).

  2. A clear separation in the KL decomposition of the two relevant types of error. On the one hand we have the error introduced due to sampling in parallel variables that are not conditionally independent (the type of error the proposed scheme avoids), and on the other hand we have the error due to the use of approximate conditionals.

Critical weaknesses

The main problems with this paper are that the experimental setup gives a structural advantage (oracle graph, speed-tuned baselines, planner-aware training) to the proposed method and that its applicability is likely to be very limited in practice once realistic settings are used. In the following I break down those two critical weaknesses further:

  1. In Table 1 the "planner-aware" column uses LLaDA and Dream trained according to the TD/LSE policy for all rows. So we are comparing how different policies perform while using an adapter that is optimized for TD/LSE. Baselines don't get training that is matched to their own policies. A missing reference point is the NLL of sequential decoding when adapters are trained under that policy. Although I understand that that would require more rounds than TD/LSE, NLL might be better, better showcasing the performance/speed trade-off.

  2. PUNT, DEMASK and DOS use "the fastest configuration within 0.01 nats per coordinate of sequential validation NLL". That pins the NLL to sequential rather than surfacing the best NLL achievable by each method. A more fair experiment would be to show NLL vs wall-clock time for each method.

  3. TD/LSE "uses graph adjacency directly, while these selectors infer dependencies from model signals." That means that TD/LSE has access to privileged information. The benefit of TD/LSE is a combination of scheduling quality with oracle structure. This is not a realistic setting, unless the graph is truly known, which isn't the case in most problems. The TD/LSE + LLaDA/Dream in Table 1 should use an estimated graph (which is also proposed in the paper, in C.4), rather than the oracle one. That'd be fair and realizable.

  4. Related to the previous point: "End-to-end times include online probes, dependency features, selection, and planning". My understanding is that TD/LSE is also given a speed advantage by not having to spend as much time on this because it has access to the ground truth graph. (Particularly wrt PUNT).

  5. The framing is that this approach can benefit masked diffusion workflows. However, all the experiments are on synthetic Ising problems. I think that the paper should pick a lane. Either claim that this approach allows for faithful and fast sampling on Ising models (and compare with the best such samplers, e.g., exact coupling from the past (Propp–Wilson) and Swendsen–Wang), or claim that the approach is truly to benefit masked diffusion, and then do performance comparison on tasks that use masked diffusion, i.e., natural language, or some other natural data problem. As it stands now, the experimental results don't match the claimed application.

  6. Although the proposed theorems are correct, the usefulness seems very limited in practice. There are many structures, even sparse random ones, that have near-linear tree depth. Table 9 shows a sparse graph with 2048 nodes where LSE needs 694 rounds, closer to linear than logarithmic. And if we knew the ground truth to correspond to a tree or star structure, we would know to sample efficiently without this paper's contributions (in the case of a tree, and knowing couplings and fields as the paper does, belief propagation gives us exact conditionals, so we can sample efficiently without learning). Real, sparse, messy graphs are the interesting regime, and the advantage there isn't clear.

Questions for authors

Each of the above weaknesses points to a deficiency in the experimental protocol. Things that could be tested more fairly, or missing experiments. Each of them has an implicit question: what is the result if you do the fair test? For 5 and 6, the question would be answered by practical experiments applying your approach to natural language and sparse unstructured graphs with thousands of nodes.

The following work seems very relevant, are you aware of it? I understand that it can be considered as concurrent. "Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling" https://arxiv.org/abs/2608.25505 and "The Lattice of Transition Laws" https://arxiv.org/abs/2610.11216

Similarly for classical combinatorics to measure parallel elimination depth: "Rankings of graphs" by Hans L. Bodlaender et al. and "The Role of Elimination Trees in Sparse Factorization" by Joseph W.H. Liu.

1 comment
AuthorsOpenReview ↗

Response to Experimental Questions on Training Fairness and Baseline Comparisons

Please see the revised manuscript for the added experimental comparisons and analysis discussed below.

  1. Matched training

    TD/LSE achieves lower conditional NLL than sequential decoding in the policy-matched comparison (Table 27). This holds for both LLaDA and Dream on ID and topology-OOD graphs. In a complementary sampling comparison, TD/LSE also yields lower edge-correlation error and a closer energy distribution (Figure 7), showing that generated spins better reproduce the target model's interactions.

  2. Baseline comparison

    TD/LSE achieves lower conditional NLL and shorter decoding time than PUNT and DEMASK at their best validation-NLL configurations on the ID graphs (Table 3). Thank you for suggesting this quality-focused comparison. Our schedule combines accurate conditional prediction with low decoding cost, as the comparisons with DOS and the other policies also show (Figure 6A,B).

  3. Graph recovery and decoding

    TD/LSE achieves an average end-to-end speedup above 2.2× over sequential decoding for both LLaDA and Dream using estimated graphs (Table 4; Figure 6C). Our Ising theory shows that early separators split remaining variables into independent components and a minimum-height elimination forest attains the fewest rounds required for exact sampling. The same idea guides the estimated-graph schedule: choose early reveals that simplify what remains, so more later predictions can proceed in parallel.

  4. Language tasks and large graphs

    The complete GSM8K and MBPP tests show accuracy and latency gains over static TD/LSE for both LLaDA and Dream (Tables 1–2). The large-graph study samples from exact conditionals on sparse graphs up to 2,048 vertices (Figure 8). Our theory explains the parallelism: early separators create independent residual components, and elimination-forest height determines the number of sampling rounds. The language planner carries over this insight by using estimated dependencies to choose early context that helps later parallel predictions.

Reviewer_92ZBOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the minimum number of rounds required to eliminate parallel sampling errors for masked diffusion models. The core theoretical insight is Theorem 2, the minimum exact round count is at most the depth of tree depth. The experiments on Ising model support the theoretical analysis.

Critical strengths

Generally this paper is easy to follow, it prove that the least sampling round to eliminate parallelization error is exactly the depth of dependency graph. Experiments on Ising model is supportive.

Critical weaknesses

My first concern is the significance of this draft. The theoretical part is not surprising to me, since many previous works have demonstrated that the parallelization error can be eliminated if the proposed tokens are conditionally independent. For many rounds, exact sampling means tokens in each rounds are conditionally independent conditioned on there prefix. Since there are multiple choices of decomposition satisfy this kind of decomposition, we would like to choose the decomposition with the least rounds.

Second, the experiments only conducted on Ising models and have no language tasks. While the experiments on Ising model are convincing, I wonder if this offers any useful insights for real-world application scenarios. At least, it would be beneficial to estimate the dependency graph and the shortest tree for language tasks, to see if it can bring gains in quality or speed.

Another minor weakness is the writing. Some contents in Section 3 are not the invention of this draft, e.g., Proposition 1 and Proposition 2. I appreciate the author to cite previous works, but I guess it would be better to put them in the Background section.

Questions for authors

Could the authors characterize the gap between a "simple greedy revelation strategy" and an "optimal tree-depth schedule"? Specifically, consider a strategy that, in each round, selects a set of unrevealed variables—subject to the constraint that the variables in this set are conditionally independent given the values ​​of the variables already revealed—such that the cardinality of this set is maximized. How many additional rounds might this strategy require compared to the optimal tree-depth, td(G)\mathrm{td}(G)?

1 comment
AuthorsOpenReview ↗

Response to Experimental Questions on Reveal Ordering and Global Planning

Please refer to the revised manuscript for the updated language experiments and discussion of sampling order.

  1. Sampling order

    Residual TD/LSE improves Dream-MBPP accuracy by 22.20 percentage points over DOS ordering, the strongest control in that ordering comparison (Figure 4B). Earlier reveals change the dependencies left for later rounds, and the language planner applies this idea by choosing early tokens that help later predictions. This scheduling advantage explains why choosing which positions to reveal in each round yields accuracy gains.

  2. Language generation

    The complete GSM8K and MBPP tests show higher accuracy and lower latency than static TD/LSE on both LLaDA and Dream (Tables 1–2). Unlike static TD/LSE, which relies on a fixed initial graph, the residual method updates dependency estimates as text grows and selects each parallel group using current dependencies and confidence in the current predictions. Newly generated content thus helps determine which positions to fill next, making the reveal order more responsive to the dependencies in the developing text.

  3. Sampling depth

    Global planning can save n−2 exact sampling rounds relative to largest-admissible-block greedy selection. On an n-vertex Ising star (n ≥ 2), revealing the center first separates all leaves, which can be sampled together in the second round. Leaf-first tie-breaking can instead take n rounds (Section 4; Appendix B). Choosing a separator early lets many remaining variables be sampled together, and fewer forest layers mean fewer serial rounds. In the forest-construction experiment on a 15-vertex path, LSE uses 4 rounds versus 8 for multi-start DFS (Table 9).

Reviewer_tcTMOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies parallel unmasking schedules for masked diffusion models using ferromagnetic Ising distributions. Theoretical analysis proves the minimum number of rounds for exactly sampling with parallel updates and KL-divergence bounds for shorter schedules. Numerical experiments using LLaDA and Dream aim to show that tree-depth based unmasking schedules improve prediction accuracy and sampling quality compared to existing methods.

Critical strengths
  • The characterization of the minimum number of exact parallel decoding rounds in terms of tree depth is an interesting theoretical result.

  • The paper provides a relatively comprehensive theoretical analysis, including lower bounds for adaptive schedules and quantification of the error introduced in approximate parallel sampling.

  • The experiments include comparisons with several recent dependency-aware decoding methods.

Critical weaknesses
  • The proposed scheduling strategy essentially consists of recursively removing graph separators and sampling the resulting disconnected components in parallel. This construction seems to rely on quite a standard variable elimination and graph decomposition techniques, with limited novelty.

  • The theoretical guarantees assume access to the underlying dependency graph which cannot be obtained in practice for a high-dimensional language distribution.

  • The numerical experiments are restricted to synthetic Ising distributions, despite using large pretrained diffusion language models as backbones. It is unclear if the proposed scheduling strategy can improve realistic language generation.

  • A substantial portion of the paper is dedicated to proving exact-round threshold and KL-divergence bounds. However, some of the bounds appear extremely conservative, while the observed model error is several order of magnitude larger.

Questions for authors

Q1) How does the proposed tree-depth scheduling approach differ from existing graph-separator based parallel sampling ? See for e.g.: https://arxiv.org/abs/2606.22976

Q2) How realistic is the residual-faithfulness assumption for masked diffusion language models? Could the authors characterize graph structures for which the proposed method provides meaningful acceleration?

Q3) Could the authors include experiments on natural language generation or other realistic discrete generative modeling task?

Q4) How informative are the theoretical KL lower bounds for the numerical experiments ?

3 comments
AuthorsOpenReview ↗

Response to Experimental Questions on Realistic Generation Tasks and Sampling Quality

Please see the revised manuscript for the added language experiments and analysis discussed below.

  1. Language generation

    Residual TD/LSE achieves the highest reported QPS₄ in three of the four primary comparisons on GSM8K and MBPP (Tables 1–2). Across all four LLaDA and Dream benchmarks, it also improves accuracy and decoding speed over static TD/LSE. On Dream MBPP, for example, accuracy rises by 24.20 percentage points and decoding is nearly twice as fast. These results bring dependency-guided scheduling to real language and code generation, showing that quality and speed can improve together.

  2. Sampling order

    Our sampling order is more accurate than confidence, random, and DOS ordering at the same reveal counts (Figure 4A,B). The planner prioritizes tokens that help predict the rest of the text. Choosing this early context helps the remaining tokens be predicted more accurately in parallel.

  3. Estimated graphs and decoding

    Decoding with estimated graphs achieves an average end-to-end speedup above 2.2× over sequential decoding for both models (Table 4; Figure 6C). In our Ising analysis, revealing early separators creates independent residual components. A minimum-height elimination forest organizes these components into parallel layers and attains the fewest rounds required for exact sampling. Tree depth therefore gives a structural basis for choosing early reveals that shorten the sequential part of sampling.

  4. KL bounds and sampling quality

    The tree-depth schedule combines parallel sampling with a more accurate joint distribution in the Ising experiment. On the 15-vertex path, the four-round tree-depth schedule gives a forward KL of 0.0301, compared with 0.7434 when compressed to three rounds (Figure 4C; Table 13). By revealing separators first, it arranges later variables into valid parallel groups. The KL decomposition identifies the benefit of this order: it removes the factorization error from parallel grouping and keeps the total distributional error low.

Thank you for the response. The new language-generation experiments are useful. I have increased my score. My remaining concern is that it is unclear how much of the gain comes specifically from tree-depth scheduling.

AuthorsOpenReview ↗

Accuracy Gains from Reveal Scheduling

Thank you for taking another look at our paper and for raising your score. On GSM8K and MBPP, our strategy for choosing which tokens to reveal together improves accuracy by 20.6–29.6 percentage points over the strongest ordering control for each model and task. On each example, all methods reveal the same number of tokens in each round. This measures the gain from our full reveal strategy, with the elimination forest guiding which positions to reveal first (Figure 4A–B and Table 34).

Overall, compared with static TD/LSE, our decoder improves accuracy by 7.96–24.20 percentage points and achieves a 1.46–4.66× end-to-end speedup across the four model and task settings (Tables 1–2).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.