- 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
-
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.
-
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.
-
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
-
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.
-
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
-
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?
-
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?
-
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
Thanks for the author's rebuttal response. I maintain my score.
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 64 and 128, 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% and 1.5% of GRID's step time at ∣M∣=32 and 128, 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.