acceptodds
Under review as a conference paper at ICLR 2027

Multi-Hop Attention Graph Sampling for Masked Diffusion LLMs

Abstract

Masked Diffusion LLMs can accelerate language generation through parallel decoding, but unmasking incompatible token combinations can degrade quality. Recent attention-based dependency-aware samplers construct a graph where the masked positions are nodes and the edges correspond to direct attention map weights. Though achieving impressive acceleration, these consider only direct or single-hop relations in the graph, disregarding multi-hop connectivity. We introduce GRID - *Graph Resistance Independent Decoding* - a training-free sampler that replaces the direct-edge coupling score with *effective resistance*, a parameter-free connectivity measure that aggregates both direct and indirect routes between masked positions. To analyze how samplers perform on complex multi-hop graph structures, we introduce *Dep-Bench*, a controlled benchmark with five datasets spanning four graph structures and known dependencies at varying depths. On Dep-Bench, GRID's advantage over direct-edge methods grows consistently with depth. On ParallelBench, a public benchmark focused on parallel decoding, GRID achieves up to decoding-step speedup over the fastest competing sampler, for a given quality threshold of % of the category-level top-1 score. Finally, across 16 leading model and LLM reasoning benchmark combinations, GRID achieves speedup over top-1 decoding and % improvement over the fastest competing sampler, at comparable accuracy. The combined results validate that multi-hop connectivity is a valuable and underutilized signal for dependency-aware parallel decoding.

Primary area:
foundation or frontier models, including LLMs
Keywords:
masked diffusion models, diffusion language models, parallel decoding, dependency-aware decoding, effective resistance

Reviews

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

This paper proposes GRID, a training-free parallel decoding method for masked diffusion language models. To address the limitation of existing attention-based samplers that primarily consider direct dependencies between tokens, GRID leverages effective resistance to aggregate direct and multi-hop connectivity information in the attention graph, thereby estimating inter-token dependency strength. It then combines this dependency estimation with a confidence-guided greedy selection strategy for parallel decoding. Additionally, the authors introduce Dep-Bench, a benchmark with controllable dependency structures, and demonstrate the effectiveness of the proposed method across multiple diffusion language models and tasks involving code generation and mathematical reasoning.

Critical strengths
  1. Insightful Multi-hop Dependency Modeling. The paper points out that existing attention-based parallel sampling methods primarily consider direct dependencies between tokens while overlooking indirect dependencies mediated by intermediate tokens. By introducing effective resistance to measure multi-hop connectivity, the proposed method offers a valuable new perspective on parallel decoding for diffusion language models.

  2. Comprehensive Experimental Evaluation. The authors construct Dep-Bench, a benchmark with known dependency structures, to systematically evaluate performance across different dependency depths. They also use counterfactual dependencies as a reference metric, demonstrating the advantages of effective resistance over direct attention.

  3. Practical Effectiveness and Generalizability. GRID requires no additional training and achieves consistent inference speedups across multiple diffusion language models and tasks involving code generation and mathematical reasoning, while maintaining overall comparable accuracy.

Critical weaknesses
  1. Limited Methodological Novelty. GRID largely follows DAWN's attention-based graph construction and confidence-guided token selection framework, replacing direct attention-based dependency scores with effective resistance, a classical concept from graph theory. Although this modification yields practical improvements, the overall approach is more of a combination and application of existing techniques, with relatively limited algorithmic novelty.

  2. Insufficient Analysis of Real-world Multi-hop Dependencies. Although Dep-Bench demonstrates the advantages of multi-hop dependency modeling on synthetic tasks, the paper lacks a systematic analysis of the prevalence and distribution of multi-hop dependencies in real-world language generation tasks, as well as their relationship with inference speedups. Therefore, the general applicability of the core motivation in realistic settings remains insufficiently validated.

Questions for authors
  1. Could the authors further analyze the distribution of multi-hop token dependencies in real-world language generation tasks and their relationship with GRID's inference speedups, to validate the general benefits of multi-hop dependency modeling?

  2. How does the computational overhead of effective resistance affect end-to-end inference throughput at larger decoding block sizes? Can GRID still maintain its speedup advantages over lightweight sampling methods?

  3. Is there a theoretical or empirical quantitative relationship between the token dependency strength measured by effective resistance and actual parallel decoding errors? Could the authors further explain how the dependency threshold affects the trade-off between speed and accuracy?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 6JGj

We thank the reviewer for their thoughtful review and constructive feedback. We are grateful for their positive assessment of our work and appreciate their recognition of the value of multi-hop dependency modeling, the comprehensive experimental validation, and GRID's practical effectiveness.

W1: Methodological Novelty

We thank the reviewer for this observation. Rather than proposing a new greedy sampling approach, we deliberately build on DAWN's optimized selection framework and focus on the underlying dependency measure, investigating the value of multi-hop graph connectivity beyond direct, single-hop attention edges. To isolate this contribution, we conduct controlled experiments on Dep-Bench (Fig. 4) and standard code and math benchmarks (Appendix H), stripping away additional selection components and using the same simplified greedy procedure for both methods. These experiments demonstrate a stronger accuracy--steps trade-off with ER, with the advantage increasing with dependency depth on Dep-Bench, directly supporting the value of multi-hop dependency modeling.

W2 + Q1: Real-World Multi-Hop Dependencies

We thank the reviewer for this thoughtful suggestion. Standard language benchmarks do not provide ground-truth token-dependency graphs, making it difficult to directly characterize multi-hop dependencies and their relationship with decoding performance. This motivated the design of our Dep-Bench, which provides known dependency structures and demonstrates that GRID's advantage increases with dependency depth (Fig. 4). Importantly, our counterfactual experiments on four real-world code and math benchmarks (Fig. 2 and Appendix B) show that inverse ER selects token sets with lower model-measured counterfactual dependency than direct attention under the same selection procedure, supporting the practical value of incorporating multi-hop connectivity. This is further reflected in improved accuracy--steps trade-offs under controlled comparisons (Appendix H) and higher end-to-end throughput at comparable accuracy (Table 2). While these results support the benefits of multi-hop modeling beyond controlled benchmarks, directly characterizing the prevalence and distribution of multi-hop dependencies in natural language remains an interesting direction for future work.

Q2: Computational Overhead at Larger Block Sizes

We address this question in our response to reviewer zHCP (Q3), with full results and runtime analysis in Appendix J of our revised manuscript. Our new end-to-end evaluations show that GRID achieves fewer decoding steps and higher throughput than DAWN across all eight benchmark--block combinations at block sizes 6464 and 128128, with broadly comparable accuracy. The runtime breakdown in Fig. 15 shows that while per-step latency increases with block size, most of the additional cost comes from general sampler operations, including attention handling and graph construction, rather than ER computation itself. ER accounts for only 0.2%0.2\% and 1.5%1.5\% of GRID's step time at ∣M∣=32|M|=32 and 128128, respectively. Thus, ER is not the primary computational bottleneck at the evaluated block sizes.

Q3: Dependency Strength, Parallel Decoding Error, and Threshold Trade-off

We thank the reviewer for this insightful question. Inverse ER serves as a structural proxy for pairwise token dependency, rather than a direct estimate of decoding error. As discussed in Section 3, parallel decoding approximates the joint conditional distribution by a product of token marginals, which can lead to inconsistent predictions when strongly coupled tokens are decoded together. Empirically, Fig. 2 shows that inverse ER selects token sets with lower counterfactual dependency than direct attention, while the additional analysis in Appendix B demonstrates stronger correlation with counterfactual KL across all four benchmarks. Furthermore, Fig. 4(c) directly evaluates the trade-off between incorrectly co-decoding dependent tokens and unnecessary decoding steps on Dep-Bench, showing that GRID achieves a more favorable trade-off. The dependency threshold controls this balance: increasing it allows more strongly coupled tokens to be decoded together, reducing decoding steps but potentially degrading accuracy, while a stricter threshold avoids more conflicts at the cost of additional steps. This trade-off is illustrated by the accuracy--steps frontiers in Fig. 4(a) and Appendix H.

Thanks for the author's rebuttal response. I maintain my score.

Reviewer_jST8OpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2(+1)
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper argues that existing attention-based dependency-aware samplers for masked diffusion LLMs, such as DAPD and DAWN, primarily consider single-hop dependencies based on direct attention, potentially overlooking dependencies mediated by indirect paths. To address this limitation, the authors propose GRID, a training-free sampler that uses effective resistance (ER) as a pairwise coupling score to capture multi-hop connectivity in attention-derived graphs. The authors empirically demonstrate that inverse ER serves as a better dependency proxy than direct attention through counterfactual pairwise dependency analysis, which measures changes in the model's predictive distributions. They also introduce Dep-Bench, a new benchmark with known dependency structures and depths, showing that GRID's advantage increases with dependency depth. Finally, experiments on ParallelBench and various code and mathematical reasoning benchmarks demonstrate fewer decoding steps and higher generation throughput than competing samplers at comparable accuracy.

Critical strengths

1. Meaningful empirical evidence for multi-hop dependency modeling.

The counterfactual dependency experiment in Section 3 provides evidence that inverse ER captures token dependencies more effectively than direct attention. Dep-Bench further supports this motivation by showing that GRID's advantage increases with dependency depth while reducing dependent co-decoding and excess serialization. Together, these experiments provide valuable evidence beyond downstream performance gains.

2. Strong empirical performance across models and benchmarks.

GRID achieves competitive accuracy–speed trade-offs across multiple MDMs and code/math benchmarks, consistently improving generation speed over competing methods. These results demonstrate the practical potential of the proposed approach beyond controlled synthetic settings.

Critical weaknesses

1. The independent contribution and validity of ER are not sufficiently established.

GRID introduces several changes beyond ER, including modularity denoising, degree normalization, and a step-dependent threshold. Although Appendix H controls the selection rule, modularity denoising is applied only to ER, leaving even the basic comparison between raw attention and raw inverse ER missing. It is therefore unclear how much of the improvement actually comes from ER.

Moreover, while ER is proposed as a better dependency proxy, its alignment with actual token dependency is not directly established. A score-level comparison against counterfactual dependency (e.g., correlation or ranking AUC), ideally across different samplers, would help validate this central claim.

Without isolating and validating ER itself, the paper's main methodological contribution remains insufficiently supported.

2. Concerns about the fairness and reproducibility of baseline evaluations.

The baseline evaluations may not be sufficiently optimized. In particular, the fixed block size of 32 may disadvantage methods such as DAPD and PUNT. More importantly, some reproduced baseline accuracies differ substantially from the original papers. DAPD shows a large accuracy degradation and is excluded from the main comparison, while discrepancies also appear for DAWN and CLAD. The authors should clarify these differences and provide complete evaluation configurations and tuning details.

These issues undermine confidence that GRID's reported performance gains reflect a fair and reliable comparison.

Questions for authors
  1. Could the authors provide additional controlled experiments on actual benchmarks to better isolate the contribution of ER? For example, comparing raw attention against raw inverse ER, or applying attention and ER under the selection procedures of DAWN, DAPD, and GRID, with independently tuned thresholds, would help clarify whether the gains arise from the dependency score itself rather than other design choices.

  2. Could the authors provide the complete hyperparameters (including block sizes), search ranges, and evaluation protocols for all methods across all experiments, and explain the discrepancies between the reproduced baseline results and those reported in the respective original papers?

  3. Could the authors clarify what probabilistic dependency inverse ER is intended to capture and how it relates to joint-marginal mismatch, and provide a more direct comparison of inverse ER and direct attention against counterfactual dependency using correlation or ranking AUC?

6 comments
AuthorsOpenReview ↗

Response to Reviewer jST8 (1/4)

We appreciate your detailed review and specific suggestions for strengthening the paper. Thank you for highlighting the empirical evidence for multi-hop dependency modeling and GRID’s practical potential. Below, we address your concerns about ER’s independent contribution and validity, as well as the fairness and reproducibility of the baseline comparisons.

W1 + Q1: Independent Contribution of ER

We thank the reviewer for raising this concern. We would like to draw the reviewer's attention to Appendix I.1, where we already provide a controlled ablation comparing direct attention, modularity-denoised attention, and inverse ER on the denoised graph. All three variants use the same simplified confidence-ordered selection procedure, with additional selection stages and the step-dependent threshold schedule disabled, and independently swept coupling thresholds. Importantly, comparing modularity-denoised attention and inverse ER on the same graph isolates the contribution of ER beyond modularity denoising. While denoising alone can improve performance, it covers a restricted range of decoding steps: modularity denoising sets many direct-edge coupling scores to zero, leaving few conflicts and allowing many positions to be decoded in parallel even at low thresholds. Increasing the threshold therefore changes the number of decoded positions only modestly, whereas ER captures indirect connectivity and achieves a stronger accuracy--steps trade-off over a substantially broader range across all four benchmarks.

Regarding degree normalization, unlike direct attention, which measures individual edge weights, inverse ER depends on the connectivity of the entire masked graph. As this graph shrinks during decoding, the scale of inverse ER can change, potentially making the coupling threshold inconsistent across steps. We therefore divide inverse ER by the graph's mean weighted degree dˉ\bar d to remove uniform graph-weight scale effects. Importantly, this is mathematically equivalent to rescaling the threshold: Rij−1dˉ>qt⋆⟺Rij−1>dˉ qt⋆\frac{R_{ij}^{-1}}{\bar d}>q_t^\star \quad\Longleftrightarrow\quad R_{ij}^{-1}>\bar d\,q_t^\star. Thus, this purely multiplicative correction preserves the ranking of all token pairs within each step and introduces no additional dependency information. Direct attention does not depend on whole-graph connectivity in the same way and does not use this correction in its original formulation.

Regarding the step-dependent threshold schedule, while Appendix I.1 primarily isolates the contribution of ER beyond modularity denoising, its controlled selection procedure also disables the schedule for all variants, demonstrating ER's advantage independently of it. To further validate this in the full end-to-end setting, we conducted an additional ablation disabling the schedule (δ=0\delta=0), reported in the new Appendix I.4 of our revised manuscript. For this ablation, we recalibrated the remaining hyperparameters on HumanEval and applied the selected configuration unchanged to the other benchmarks.

MethodHumanEval Acc. (%) ↑ / Steps ↓ / TPS ↑MBPP Acc. (%) ↑ / Steps ↓ / TPS ↑GSM8K Acc. (%) ↑ / Steps ↓ / TPS ↑MATH Acc. (%) ↑ / Steps ↓ / TPS ↑
DAWN36.6 / 58.8 / 25.5241.3 / 53.7 / 9.9377.6 / 55.5 / 9.2932.3 / 72.6 / 9.93
GRID (δ=0\delta=0)36.6 / 52.8 / 27.8042.8 / 46.6 / 10.9078.4 / 51.0 / 10.0033.2 / 65.9 / 10.80
GRID (δ=0.15\delta=0.15)37.8 / 49.9 / 29.1142.4 / 43.4 / 11.3478.1 / 47.9 / 10.6732.1 / 62.3 / 11.46

Compared with standard GRID (δ=0.15\delta=0.15), disabling the schedule slightly increases decoding steps and reduces throughput while maintaining comparable accuracy. Importantly, even without the schedule, GRID remains faster than the fastest competing sampler at its original operating point in Table 2 across all four benchmarks. Together with the controlled experiments in Appendix I.1, these results support the independent contribution of ER beyond modularity denoising and the threshold schedule. We address the complementary score-level validation against counterfactual dependency in W1 + Q3.

AuthorsOpenReview ↗

Response to Reviewer jST8 (2/4)

W1 + Q3: ER as a Dependency Proxy

We thank the reviewer for this question. Direct attention offers an efficient measure of pairwise coupling, but captures only single-hop interactions, whereas counterfactual KL [1] offers a richer, model-grounded dependency measure but requires additional forward passes. Inverse ER offers a middle ground by capturing multi-hop connectivity from the attention graph without additional model evaluations. We assess its correspondence to pairwise dependency using symmetric counterfactual KL, which measures how much revealing one token changes another token's predicted distribution.

Our original counterfactual experiment (Fig. 2 and Appendix B) already demonstrates that inverse ER selects token sets with lower dependency regret than direct attention. To directly address the reviewer's request for score-level validation, we additionally computed Spearman correlations between both coupling scores and symmetric counterfactual KL using the same diagnostic states and candidate pairs. The new figure in Appendix B of our revised manuscript shows higher correlation for inverse ER across all four benchmarks and eight confidence thresholds. The table below reports the corresponding mean per-state correlation differences, Δρ=ρER−ρattn\Delta\rho=\rho_{\mathrm{ER}}-\rho_{\mathrm{attn}} (higher is better), at each confidence threshold τ\tau.

Benchmarkτ=0.2\tau=0.2τ=0.3\tau=0.3τ=0.4\tau=0.4τ=0.5\tau=0.5τ=0.6\tau=0.6τ=0.7\tau=0.7τ=0.8\tau=0.8τ=0.9\tau=0.9
HumanEval+0.053+0.059+0.059+0.057+0.058+0.051+0.054+0.053
MBPP+0.051+0.057+0.059+0.064+0.066+0.064+0.064+0.065
GSM8K+0.052+0.068+0.076+0.083+0.089+0.093+0.078+0.069
MATH+0.038+0.052+0.069+0.077+0.084+0.084+0.070+0.060

All correlation differences are positive, with strictly positive 95% confidence intervals under prompt-level clustered bootstrap resampling (Appendix B). This complements the original selection-based evidence by demonstrating that inverse ER also ranks candidate pairwise dependencies more accurately.

[1] Azangulov, I., et al. Parallel Sampling from Masked Diffusion Models via Conditional Independence Testing (2026).

W2 + Q2: Baseline Fairness, Reproducibility, and Evaluation Discrepancies

We thank the reviewer for raising these concerns. Our examination of diffusion LLM sampler papers reveals that evaluation protocols are far from standardized, with substantial differences in prompting, scoring, and generation settings. To ensure fair comparisons within our paper, we evaluate all samplers using the same benchmark-specific pipeline, including identical model checkpoints, prompts, test examples, scoring procedures, and hardware within each model. The following table summarizes representative differences between the evaluation procedures used or provided by the respective papers:

Evaluation aspectGRID paperDAWN paperCLAD paperKLASS paperDAPD paper
LLaDA promptingChat templateChat templateChat templateChat templateRaw text; no chat template or BOS$^{*}$
GSM8K few-shot55505 (DAPD); 3 (baselines)∗^{*}
MATH benchmarkFull MATH (5,000)Full MATH (5,000)Full MATH (5,000)MATH-500MATH-500
MATH scoringSymbolic equivalenceSymbolic equivalenceSymbolic equivalenceCustom extracted-answer matchingMinerva-format exact match
HumanEval outputExtract code; sanitize; testExtract code; sanitize; testExtract code; sanitize; testExtract code; testStop-word truncation; no sanitization
MBPP outputExtract code; sanitize; testRaw code executionRaw code executionMBPP-sanitized dataset; extract code; testRaw code execution
Block setup (method + baselines)8×328\times328×328\times328×328\times324×644\times641×2561\times256 (DAPD); 4×644\times64 (baselines)

∗^{*} These entries reflect the default configurations in the evaluation scripts of DAPD's official repository. We cannot verify whether these exact settings were used to produce the results reported in the paper.

These differences are particularly pronounced in DAPD's evaluation. For example, DAPD's released LLaDA scripts use raw prompts without a chat template or BOS token, whereas the evaluation protocols of GRID, DAWN, CLAD, and KLASS use the LLaDA chat template. The code-processing procedures also differ across these evaluations. DAPD also uses MATH-500 rather than the full MATH used by GRID, DAWN, and CLAD, with a different scoring protocol. Moreover, its released scripts use different GSM8K few-shot defaults and decoding-block configurations for DAPD and its own baselines. These substantial protocol differences make direct cross-paper comparisons unreliable.

AuthorsOpenReview ↗

Response to Reviewer jST8 (3/4)

W2 + Q2: Baseline Fairness, Reproducibility, and Evaluation Discrepancies (Continued)

Indeed, substantial discrepancies also appear in the reported results of identical methods. The following table presents representative cross-paper comparisons:

Model / Benchmark / MethodDAPD paper Acc. (%) / StepsDAWN paper Acc. (%) / StepsCLAD paper Acc. (%) / StepsGRID paper (ours) Acc. (%) / Steps
Dream / GSM8K / Fast-dLLM47.7 / 90.2--75.9 / 62.577.9 / 62.9
Dream / GSM8K / KLASS45.1 / 154.471.7 / --73.5 / 107.075.0 / 111.3
Dream / MBPP / Top-1--54.2 / 25654.8 / 25655.3 / 256
Dream / MBPP / Fast-dLLM30.6 / 67.7--56.0 / 62.754.4 / 33.5
LLaDA / MBPP / Top-1--29.6 / 25631.6 / 25642.0 / 256
LLaDA / MBPP / DAWN--30.8 / --30.6 / 49.741.3 / 53.7
LLaDA / MBPP / CLAD----30.2 / 52.541.6 / 52.7
LLaDA / MBPP / EB-Sampler19.4 / 52.6----41.0 / 52.6
LLaDA / MBPP / Fast-dLLM20.6 / 41.5--31.8 / 69.342.0 / 51.5

The Dream results reveal particularly large discrepancies between DAPD and the other papers, even for identical samplers. On LLaDA/MBPP, our evaluation also yields accuracies more than 10 percentage points higher than those reported by DAWN and CLAD, including for Top-1 decoding, independently of any parallel sampling algorithm. Yet DAWN's accuracy relative to its corresponding Top-1 baseline remains similar across the three evaluations. As shown in the first table, unlike the released DAWN and CLAD MBPP evaluation paths, we extend the code sanitization used for HumanEval to MBPP for consistency, applying it uniformly to all samplers. This increases LLaDA/MBPP accuracy and illustrates how evaluation-protocol differences can substantially affect reported results.

Regarding DAPD, the results already reported in Appendix F use its original block size of 256256, now explicitly clarified in our revised manuscript. We also tested block size 3232 and observed similarly degraded accuracy. We calibrated DAPD's dependency-threshold schedule, prioritizing accuracy at decoding-step counts roughly comparable to DAWN, with the search ranges and selected configurations now detailed in Appendix F.1. Nevertheless, DAPD's accuracy remains substantially lower under our common evaluation protocol. We believe the substantial differences in prompting, benchmark settings, and scoring procedures documented above largely explain the discrepancy with its published results. We therefore report DAPD separately rather than include a lower-accuracy operating point in Table 2. DAWN remains our main direct-attention baseline, although its selection procedure differs from DAPD's.

Regarding block-size fairness, we use block size 3232 consistently across all samplers in Table 2, following the standard settings used in the original LLaDA-8B and LLaDA 2 evaluations [1, 2]. As clarified above, DAPD was separately evaluated at its original block size of 256256. To address the concern regarding PUNT, we additionally evaluated it at block size 256256, sweeping ϵ∈{0.01,0.02,0.03,0.04}\epsilon\in\{0.01,0.02,0.03,0.04\} under our LLaDA-8B-Instruct evaluation protocol with generation length 256256. The table below reports accuracy (%) / average decoding steps / TPS, with the original block-3232 PUNT results from Table 2 included for reference.

Blockϵ\epsilonHumanEval Acc. / Steps / TPSMBPP Acc. / Steps / TPSGSM8K Acc. / Steps / TPSMATH Acc. / Steps / TPS
32--39.6 / 53.6 / 5.5539.8 / 44.1 / 2.1175.9 / 54.9 / 1.9433.3 / 64.5 / 2.29
2560.0142.1 / 80.4 / 2.5641.0 / 63.8 / 0.8959.4 / 70.9 / 0.9624.2 / 78.3 / 1.22
2560.0240.2 / 61.5 / 3.3840.2 / 44.8 / 1.2356.0 / 52.6 / 1.3123.7 / 58.5 / 1.64
2560.0339.0 / 50.0 / 4.1638.2 / 37.3 / 1.5054.0 / 43.5 / 1.5924.0 / 48.1 / 2.01
2560.0437.2 / 43.6 / 4.7837.2 / 31.9 / 1.7055.9 / 37.3 / 1.8624.5 / 41.1 / 2.36

At block size 3232, PUNT achieves broadly comparable accuracy to the other samplers. At block size 256256, conservative settings retain similar accuracy on HumanEval and MBPP, but accuracy decreases substantially on GSM8K and MATH. Moreover, PUNT's dependency testing requires approximately ⌈log⁡2∣M∣⌉\lceil\log_2 |M|\rceil additional model evaluations per decoding step, increasing computational overhead at larger blocks and explaining why fewer steps do not necessarily yield higher TPS. PUNT's original paper uses generation length 512512 for HumanEval, MBPP, and GSM8K, whereas our evaluation uses 256256 consistently across methods. We retain this common protocol for fairness, with the complete new results provided in Appendix F.2.

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

Authors propose attention graph electrical resistance (e.g. the more connections there are between two tokens the lower is the resistance) and use it as a proxy to how the tokens are connected. They filter out the attention sinks and unmasked tokens and use this proxy to speed up decoding in diffusion llms. The approach is training free and offers a substantial improvement with the predecessors. Authors also propose Dep-Bench to evaluate their method.

Critical strengths

The approach works, with decoding performance increase from 1.06x to 2.02x, the idea is novel and elegant and the evaluations are mostly solid, with 5 new benchmarks proposed and 4 different diffusion models evaluated. The overhead is not large and does not impact final performance.

Critical weaknesses

The experiments were carried out on block size 32, so there is no definite proof that this approach will scale to larger block size, considering O(N^3) overhead computation cost. The authors give a table showing overhead for each N size, but there are no end-to-end experiments showing that. This is a nitpick, however, there are no other substantial weaknesses in this paper :)

Questions for authors

Show the TPS for each block size.

1 comment
AuthorsOpenReview ↗

Response to Reviewer uAdm

Thank you for your thoughtful review and constructive feedback. We are grateful for your positive assessment of our work and appreciate your recognition of the novelty and elegance of our approach.

Scalability to Larger Block Sizes

We thank the reviewer for this suggestion. We present our new block-size experiments in detail in our response to reviewer zHCP (Q3), comparing GRID, DAWN, and Top-1 at block sizes 3232, 6464, and 128128. GRID achieves fewer decoding steps and higher throughput than DAWN across all eight new benchmark--block combinations, with broadly comparable accuracy. The complete results and runtime analysis are also provided in Appendix J of our revised manuscript.

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

This paper proposes GRID, a training-free sampler that speeds up masked diffusion language models by choosing which tokens to generate together. Unlike methods that use only direct attention links, GRID also considers indirect connections through other masked positions, using effective resistance as a dependency score. It then selects weakly connected positions for parallel decoding. Experiments on controlled dependency tasks, ParallelBench, and code and math benchmarks show a better speed–accuracy trade-off, with average throughput gains of about 7–11% over the fastest competing sampler across the standard benchmarks.

Critical strengths
  1. GRID offers a well-motivated way to capture indirect dependencies that direct attention scores can miss. The controlled dependency tasks and counterfactual tests provide evidence that this helps select more compatible tokens for parallel decoding.

  2. The evaluation covers four models and several benchmarks, reporting actual throughput alongside decoding steps. The consistent speed gains, supported by ablations and overhead measurements, make the method practically promising.

Critical weaknesses
  1. GRID is tuned on HumanEval and then evaluated on the same benchmark. This may make its results look better than they would on unseen problems. A separate tuning set is needed.

  2. The main throughput results in Table 2 are not always at the same accuracy, and GRID receives more tuning than most baselines. The paper includes matched-quality analyses elsewhere, but a matched-accuracy throughput comparison with similar tuning budgets would make the claimed advantage more convincing.

Questions for authors
  1. Can you tune GRID on a separate set and report results on untouched HumanEval problems? This would help rule out gains from tuning on the evaluation benchmark.

  2. How much of the speed advantage remains when all methods reach the same accuracy? Please report matched-accuracy throughput comparisons with similar tuning budgets.

  3. Does GRID still improve throughput with larger decoding blocks and longer outputs? End-to-end measurements would show whether fewer decoding steps outweigh the added graph computation.

  4. Does the multi-hop score still help on distilled models that already generate in few steps? This would test its value when there is less room for acceleration.

  5. How stable are the gains across repeated runs? Confidence intervals for accuracy and throughput would help establish whether the smaller improvements in Table 2 are reliable.

3 comments
AuthorsOpenReview ↗

Response to Reviewer zHCP (1/3)

We thank the reviewer for their thoughtful review. We appreciate their assessment that GRID offers a well-motivated approach to modeling indirect dependencies and shows practical promise. We address their concerns and questions below.

W1 + Q1: Cross-Dataset Hyperparameter Calibration

We thank the reviewer for raising this concern. Following DAWN's practice of benchmark-based hyperparameter selection, we calibrated GRID once per model on HumanEval and transferred the selected configuration unchanged to the remaining benchmarks (Appendix D). We acknowledge that HumanEval is therefore not an independent evaluation of the original configuration. To address this, we additionally calibrated GRID on MBPP and GSM8K separately using LLaDA-8B-Instruct, selecting the fastest configuration meeting DAWN's accuracy on the calibration dataset. We then evaluated each configuration across all four benchmarks without further tuning. These results are also reported in the new Appendix I.5 of our revised manuscript.

Method / Calibration DatasetGRID hyperparameters (q0,τlow,δ)(q_0,\tau_{\mathrm{low}},\delta)HumanEval Acc. (%) ↑ / Steps ↓MBPP Acc. (%) ↑ / Steps ↓GSM8K Acc. (%) ↑ / Steps ↓MATH Acc. (%) ↑ / Steps ↓ / TPS ↑
DAWN (paper)--36.6 / 58.841.3 / 53.777.6 / 55.532.3 / 72.6 / 9.93
GRID / HumanEval (paper)(0.01,0.25,0.15)(0.01,0.25,0.15)37.8 / 49.942.4 / 43.478.1 / 47.932.1 / 62.3 / 11.46
GRID / MBPP(0.01,0.25,0.15)(0.01,0.25,0.15)37.8 / 49.942.4 / 43.478.1 / 47.932.1 / 62.3 / 11.46
GRID / GSM8K(0.01,0.30,0.20)(0.01,0.30,0.20)36.5 / 47.340.1 / 40.477.8 / 46.231.7 / 60.4 / 11.80

These results support GRID's ability to generalize to HumanEval without tuning on it. MBPP calibration recovers the original configuration, while GSM8K calibration also transfers well to HumanEval. Both configurations maintain broadly comparable accuracy to DAWN with fewer decoding steps across all four benchmarks, supporting robustness to the choice of calibration dataset. Appendix I.3 provides complementary hyperparameter sensitivity analysis.

W2 + Q2: Matched-Accuracy Throughput Comparison

We thank the reviewer for this suggestion. To directly address the accuracy differences, we conducted an additional accuracy-controlled throughput comparison on LLaDA-8B-Instruct against four competitive baselines: EB-Sampler, Fast-dLLM, DAWN, and CLAD (excluding KLASS and PUNT due to their substantially lower throughput in Table 2). We also added the complete results to the new Appendix M of our revised manuscript.

For each baseline and benchmark, we select a configuration achieving accuracy as close as possible to GRID's, without exceeding it. This comparison favors the baselines: they may use benchmark-specific configurations and operate at equal or lower accuracy, while GRID retains its original configuration calibrated on HumanEval and applied unchanged across all four benchmarks.

MethodHumanEval Acc. (%) ↑ / Steps ↓ / TPS ↑MBPP Acc. (%) ↑ / Steps ↓ / TPS ↑GSM8K Acc. (%) ↑ / Steps ↓ / TPS ↑MATH Acc. (%) ↑ / Steps ↓ / TPS ↑
EB-Sampler37.2 / 59.5 / 25.3941.0 / 52.6 / 10.1178.1 / 56.8 / 9.3032.1 / 67.6 / 10.80
Fast-dLLM37.8 / 58.7 / 26.0442.0 / 51.5 / 10.2378.1 / 53.1 / 10.0032.0 / 71.8 / 10.19
DAWN36.6 / 58.8 / 25.5241.3 / 53.7 / 9.9377.6 / 55.5 / 9.2932.1 / 70.1 / 10.30
CLAD37.8 / 60.0 / 25.2741.6 / 52.7 / 9.9277.5 / 50.9 / 10.1031.7 / 72.8 / 9.91
GRID (ours)37.8 / 49.9 / 29.1142.4 / 43.4 / 11.3478.1 / 47.9 / 10.6732.1 / 62.3 / 11.46

GRID maintains the highest throughput across all four benchmarks, outperforming the fastest competing baseline by 11.8%, 10.9%, 5.6%, and 6.1% on HumanEval, MBPP, GSM8K, and MATH, respectively. Thus, GRID's throughput advantage persists even when competing methods are allowed benchmark-specific calibration and operate at equal or lower accuracy.

These results complement the matched-quality comparisons in Table 1 and the controlled GRID--DAWN accuracy--steps trade-offs in Appendix H.

AuthorsOpenReview ↗

Response to Reviewer zHCP (2/3)

Q3: Larger Blocks and Longer Outputs

We thank the reviewer for this suggestion. We conducted additional end-to-end evaluations comparing Top-1, DAWN, and GRID at block sizes 3232, 6464, and 128128 on LLaDA-8B-Instruct. We use DAWN as our reference baseline because it is GRID's closest structural counterpart, sharing its confidence-guided selection framework while using direct attention rather than ER-based coupling. For each larger block size, we independently calibrated GRID and DAWN on HumanEval to minimize decoding steps while achieving at least 90%90\% of Top-1 accuracy at that block size, then transferred the selected configurations unchanged to the remaining benchmarks. Block-3232 results use the original paper configurations. The table below reports accuracy (%) / average decoding steps / TPS / speedup over Top-1 at the same block size. The full experimental details are provided in the extended Appendix J of our revised manuscript.

BlockMethodHumanEval Acc. / Steps / TPS / SpeedupMBPP Acc. / Steps / TPS / SpeedupGSM8K Acc. / Steps / TPS / SpeedupMATH Acc. / Steps / TPS / Speedup
32Top-142.1 / 256 / 5.90 / ×1.0042.0 / 256 / 2.07 / ×1.0078.7 / 256 / 2.06 / ×1.0032.9 / 256 / 2.85 / ×1.00
DAWN36.6 / 58.8 / 25.52 / ×4.3341.3 / 53.7 / 9.93 / ×4.8077.6 / 55.5 / 9.29 / ×4.5132.3 / 72.6 / 9.93 / ×3.48
GRID37.8 / 49.9 / 29.11 / ×4.9342.4 / 43.4 / 11.34 / ×5.4878.1 / 47.9 / 10.67 / ×5.1832.1 / 62.3 / 11.46 / ×4.02
64Top-139.9 / 256 / 5.90 / ×1.0041.4 / 256 / 2.10 / ×1.0077.3 / 256 / 2.10 / ×1.0033.5 / 256 / 2.90 / ×1.00
DAWN36.2 / 57.75 / 25.82 / ×4.3840.5 / 52.56 / 10.11 / ×4.8178.5 / 54.41 / 9.47 / ×4.5132.9 / 71.74 / 10.04 / ×3.46
GRID36.1 / 52.18 / 28.54 / ×4.8441.4 / 45.60 / 10.96 / ×5.2277.8 / 48.10 / 10.61 / ×5.0532.7 / 64.13 / 11.12 / ×3.83
128Top-139.0 / 256 / 5.90 / ×1.0040.0 / 256 / 2.00 / ×1.0072.6 / 256 / 2.00 / ×1.0032.1 / 256 / 2.90 / ×1.00
DAWN36.2 / 52.34 / 26.42 / ×4.4839.1 / 45.14 / 10.94 / ×5.4772.4 / 49.04 / 10.49 / ×5.2430.4 / 65.66 / 10.99 / ×3.79
GRID36.5 / 44.99 / 26.80 / ×4.5440.0 / 40.71 / 11.35 / ×5.6772.9 / 44.48 / 11.37 / ×5.6831.4 / 58.92 / 11.96 / ×4.13

GRID achieves fewer decoding steps and higher end-to-end throughput than DAWN across all eight new benchmark--block combinations, with broadly comparable accuracy. Its throughput advantage ranges from 8.5%8.5\% to 12.0%12.0\% at block size 6464 and from 1.5%1.5\% to 8.9%8.9\% at block size 128128, demonstrating that the decoding efficiency gains persist after accounting for the additional computation. A detailed runtime breakdown is provided in Appendix J of our revised manuscript. Regarding longer outputs, ER operates only on the active decoding block, so increasing generation length at a fixed block size does not increase the size or computational complexity of an individual ER computation.

Q4: Compatibility with Few-Step Distilled Models

We thank the reviewer for this interesting question. GRID focuses on training-free acceleration of pretrained masked diffusion LLMs, whereas few-step distilled models achieve acceleration through additional training. In principle, GRID could complement distillation by guiding parallel token selection at inference time, provided the distilled model supports adaptive masked-token decoding. However, the reduced number of decoding steps may limit the additional speedup. Investigating this combination is beyond the scope of our current study and has not been established by the other training-free baselines considered here either. We view this as an interesting direction for future work.

AuthorsOpenReview ↗

Response to Reviewer zHCP (3/3)

Q5: Statistical Uncertainty

We thank the reviewer for this suggestion. Although the baseline papers primarily report point estimates, we agree that quantifying statistical uncertainty strengthens the comparison. We computed 95% confidence intervals for accuracy and throughput across all methods and model--benchmark combinations in Table 2, using 10,000 bootstrap resamples of benchmark examples. The table below reports the results for LLaDA-8B-Instruct, with accuracy (%) and TPS shown as point estimates ±\pm confidence-interval half-widths. The complete results for all four models, including paired comparisons, and the methodology are provided in the new Appendix L of our revised manuscript.

Importantly, the paired bootstrap comparisons in Appendix L show that GRID's throughput improvement over the fastest competing sampler has a strictly positive 95% confidence interval in 15 of 16 model--benchmark settings, as well as across all four benchmarks when averaged over models. No comparison shows a statistically significant accuracy degradation.

MethodHumanEval Acc (%)HumanEval TPSMBPP Acc (%)MBPP TPSGSM8K Acc (%)GSM8K TPSMATH Acc (%)MATH TPS
Top-142.1 ± 7.35.90 ± 0.1242.0 ± 4.42.07 ± 0.0978.7 ± 2.22.06 ± 0.0332.9 ± 1.32.85 ± 0.01
EB-Sampler37.2 ± 7.325.39 ± 1.2541.0 ± 4.410.11 ± 0.3778.2 ± 2.29.15 ± 0.1432.6 ± 1.310.00 ± 0.08
Fast-dLLM37.8 ± 7.326.04 ± 1.4042.0 ± 4.410.23 ± 0.3678.5 ± 2.29.59 ± 0.1632.0 ± 1.310.19 ± 0.09
KLASS39.6 ± 7.314.50 ± 0.6641.0 ± 4.35.82 ± 0.1974.6 ± 2.45.19 ± 0.0831.6 ± 1.36.06 ± 0.04
DAWN36.6 ± 7.325.52 ± 1.4441.3 ± 4.49.93 ± 0.3177.6 ± 2.39.29 ± 0.1632.3 ± 1.39.93 ± 0.09
CLAD37.8 ± 7.325.27 ± 1.3341.6 ± 4.39.92 ± 0.3679.3 ± 2.29.30 ± 0.1531.7 ± 1.39.91 ± 0.09
PUNT39.6 ± 7.65.55 ± 0.2439.8 ± 4.32.11 ± 0.0875.9 ± 2.31.94 ± 0.0333.3 ± 1.32.29 ± 0.01
GRID (ours)37.8 ± 7.329.11 ± 1.4942.4 ± 4.411.34 ± 0.5178.1 ± 2.310.67 ± 0.1632.1 ± 1.311.46 ± 0.10

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.