Accelerating Diffusion LLMs via Adaptive Parallel Decoding

Dear Reviewer ezv3,

Thank you for your feedback. We hope to address your questions and concerns.

The proof relying on Bonferroni’s inequality (Property 1) is flawed. As noted in Line 122, $P_{APD}=P_{AR}$ holds only if $|g|=n$; when $|g|<n$, they are not equivalent. Thus, applying Bonferroni’s inequality is mathematically unsound. This also invalidates the heuristic justification for Property 2.

We are not making a formal statement about $p\_{APD}$ or $\hat{p}\_{AR}$. Our proof shows that if $p\_D(x)=1$, then $p\_{AR}(x)=1$. Because the goal of $p_T$ is to approximate $p_{AR}$, we are stating that the same property must hold: if $p\_D(x)=1$, then $p\_{T}(x)=1$. This is our justification of Property 1.

The author directly uses the KV cache method, but this method has already been proposed and there are different variants, so it cannot be considered an innovative point.

We are unsure which papers are being referred to here and respectfully ask for clarification. If the reviewer is referring to the use of KV cache more broadly for AR models, indeed there are many works which use it. KV caching in dLLMs is very natural in APD because we are decoding left to right, and the decoding order is similar to autoregressive. The challenge of KV caching in a dLLM is that because of bidirectional attention, previously computed keys and values can change. In practice, we show in the paper that only KV from a small window from the most recently generated tokens need to be updated to maintain performance. We do not consider KV caching the central point of the paper, but an optimization to achieve better results.

Experiments are confined to GMS8K, GPQA, and MATH without theoretical guarantees, leaving generalization to other datasets unverified.

Because ADP exploits conditional dependence, which is a property of the data, to further parallel decoding, it is difficult to give theoretical guarantees on the speedups achievable. We emphasize that the advantage of ADP is that it dynamically adapts to the data to speed up decoding when it is possible without significantly degrading quality, but we are unable to formalize the precise impact on performance.

Llada’s reference paper tested more diverse datasets. Why restrict evaluation to only three?

Many of the datasets for evaluating Llada such as MMLU and Hellaswag follow likelihood-based evaluation (eg, using multiple-choice questions) and are not generative, which is a requirement for evaluating our method. In light of the reviewers’ concern, we added a coding benchmark: Humaneval.

ADP Config 1: Dream 7B + Qwen 2.5 0.5B, (R = 0.6, W = 32, M = 200)

ADP Config 2: Dream 7B + Qwen 2.5 0.5B, (R = 0.7, W = 16, M = 100)

As can be seen in this table, ADP works well for code. It maintains most of the accuracy of the underlying base model at K=1 but can achieve 34x the throughput of the base model. Additionally, it is firmly Pareto optimal by improving on Qwen 7B in throughput and Qwen 0.5B in quality.

The reference to "Dream 7B" (Citation 39) appears incorrect—no matching work was found. Is this a citation formatting error?

We are citing the bibtex directly from the Dream 7B blog. There is currently no paper associated with the model.

@misc{dream2025, title = {Dream 7B}, url = {omitting link due to rebuttal rules}, author = {Ye, Jiacheng and Xie, Zhihui and Zheng, Lin and Gao, Jiahui and Wu, Zirui and Jiang, Xin and Li, Zhenguo and Kong, Lingpeng}, year = {2025} }

We thank the reviewer for their valuable critiques, and we hope that our response provides enough assurance to increase our score.

Dear Reviewer 4Kag,

Thank you for your positive feedback. We hope to also answer your insightful questions and attend to your concerns.

APD requires dLLMs specifically trained for left-to-right decoding, with non-left-to-right implementations such as Llada exhibiting substantially weaker performance as evidenced in Table 1.

To be clear, ADP does not require a dLLM trained for left to right decoding. Dream 7B’s training objective trains for random decoding, but because it was initialized from an autoregressive model it will have better representations in a left to right setting than Llada. However, Table 1 shows that Llada can also perform left to right decoding, and on GSM8K left to right decoding is even better than confidence based decoding. While ADP does not require any left to right training, the success of ADP does indicate that that parallel prediction can be performed left to right, and additional left-right fine tuning on top of dLLMs will likely improve the results of ADP.

Q1: How much latency does the small AR model introduce? Does KV caching sufficiently offset its computational overhead to justify inclusion?

Thank you for the suggestion. We have compiled a table for GSM8K to show the impact of the small AR model.

ADP Config 1: Dream 7B + Qwen 2.5 0.5B, (R = 0.6, W = 32, M = 200)

ADP Config 2: Dream 7B + Qwen 2.5 0.5B, (R = 0.7, W = 16, M = 100)

Overall, the latency using ADP is much lower than the default diffusion generation in Dream. However, the impact of the AR verification step is significant, and the model spends roughly half the time in this step. We see this as an opportunity for further optimizations. More efficient implementations of Gumbel sampling and better KV cache management using Paged Attention would likely reduce the latency significantly. The current implementation of ADP is purely PyTorch.

Q2: Given Table 1 shows left-to-right decoding yields optimal dLLM performance, can APD effectively integrate with entropy/confidence-based decoding schemes (e.g., Llada’s approach) without compromising throughput gains?

As currently formulated, ADP can only work for left to right decoding. This is the case because the autoregressive verifier computes a left to right likelihood. Consider the following example where tokens are separated by commas

Prompt: The, capital, of

Diffusion Sample: France, is, is, is, is, is

The diffusion model may sample this because it will be marginally likely due to there being many continuations besides "France" that can span multiple tokens. The autoregressive verifier will find the final “is” very likely due to the repetition, so we need to reject samples after the first disagreement between the diffusion samples and verifier (only accept up to the first “is”). This accept strategy produces a left to right decoding order. Adapting ADP for arbitrary decoding orders is an interesting open research question and may require a different auxiliary model such as an Any-Order Autoregressive model [1].

Q3: Can APD achieve high parallelism (>5 tokens/step) in open-ended generation? Fig 2 suggests quality drops sharply for k>5 in naive parallelization, does APD overcome this limitation for non-reasoning domains?

The problem of parallel sampling is inherently probabilistic and therefore will be data dependent. It is likely that non-reasoning domains are less parallelizable in a fundamental way due to more interdependent tokens. Because open-ended generation is more difficult to evaluate, we do not include it in our benchmarks, but as Appendix D shows we can still achieve significant speed up over baseline diffusion models. The strength of ADP is that it can adaptively find opportunities to parallelize generation, and where this cannot be achieved, it automatically applies less parallelization so that quality is not severely impacted.

[1] Shih, Andy, Dorsa Sadigh, and Stefano Ermon. "Training and inference on any-order autoregressive models the right way." Advances in Neural Information Processing Systems 35 (2022): 2762-2775.

Dear Reviewer mTc7,

We are thankful that the reviewers recognize the novelty and impact of our work. We are also thankful for their insightful suggestions, which we aim to incorporate into the paper.

As recommended, here is a table summary similar to Table 1 for the respective benchmarks:

ADP Config 1: Dream 7B + Qwen 2.5 0.5B, (R = 0.6, W = 32, M = 200)

ADP Config 2: Dream 7B + Qwen 2.5 0.5B, (R = 0.7, W = 16, M = 100)

We will include these table results in the Appendix for more direct comparisons.

To test for generalization to the other domains, we will also include coding in our evaluation suite. These results were obtained on NVIDIA A6000 GPUs due to memory errors, so they may not be directly comparable to the rest of the paper.

As can be seen in this table, ADP results generalize beyond the existing benchmark scores. While it does not obtain the same quality as autoregressive due to a worse base model (as can be seen in the K=1 result), it is firmly on the Pareto frontier in terms of quality and throughput.

We thank the reviewer for their generous feedback, and we hope that these updates have improved the paper significantly.

Dear Reviewer SxPY,

We thank the reviewer for their positive feedback regarding our writing and empirical results. We hope to use this opportunity to clarify questions and concerns.

"The dependence on an auxiliary approximate autoregressive model limits its applicability. At the very least, ADP requires that for each dLLM, a small LLM with the same tokenizer exists."

While ADP, as currently formulated, requires a smaller model with the same tokenizer, this problem is generally recognized to be the same in speculative decoding. However, a recently published work [1] shows that it is possible to perform speculative decoding over different tokenizers by performing verification over strings. This same idea naturally extends to ADP, where in our accept criterion, we can accept strings that the diffusion model and product mixture agree on.

"I found sampling from $p_T$ as presented in eq (8) to be slightly confusing. In practice (as presented in Algorithm 1), $p_D$ is first used to generate $n$ tokens, which are then subsequently used by $\hat{p}_{AR}$. Does this not impose some conditional dependence?"

Intuitively, $p_D$ captures the marginals and $p_T$ can capture joint dependencies. We sample from $p_D$ initially because it can be performed in parallel. We then resample each token conditioned on the previous tokens in the sequence using $p_T$ and check that the original samples $p_D$ are valid under $p_T$. Thus, you are correct that $\hat{p}_{AR}$ (which is used to compute $p_T$) is adding conditional dependence between tokens. This is desirable because the inter-token dependencies are necessary to verify whether a sample should be accepted.

In Table 1, why is random decoding always slower than entropy/confidence-base decoding for Dream/Llada models?

Thank you for the perceptive question. When a diffusion model outputs the EOS token with everything to its left sampled, the generation can stop. A random generation order is not likely to satisfy this condition early, while entropy/confidence/left-right are much more likely. Thus, generation order and answer length can change the throughput significantly, as the attention operation grows O(n^2) and the diffusion model is not KV caching by default.

[1] Timor, Nadav, et al. "Accelerating llm inference with lossless speculative decoding algorithms for heterogeneous vocabularies." arXiv preprint arXiv:2502.05202 (2025).