- 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
-
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).
-
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:
-
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.
-
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.
-
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.
-
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).
-
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.
-
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.
Response to Experimental Questions on Training Fairness and Baseline Comparisons
Please see the revised manuscript for the added experimental comparisons and analysis discussed below.
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.
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).
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.
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.