Source-linked AI summary
Sparse-dLLM: Accelerating Diffusion LLMs with Dynamic Cache Eviction
Yuerong Song, Xiaoran Liu, Ruixiao Li, Zhigeng Liu, Zengfeng Huang, Qipeng Guo, Ziwei He, Xipeng Qiu
TL;DR
dLLMs face quadratic inference costs and memory overhead because their sequence-wide states are repeatedly recomputed, while existing full-layer caching can remain memory-intensive. Sparse-dLLM is a training-free method that uses attention-guided, delayed bidirectional cache eviction based on stable token saliency. It achieves comparable downstream performance, up to 10× higher throughput than vanilla dLLMs, and nearly identical memory costs.
Problem
dLLMs require costly sequence-wide recomputation, while full-layer caching accelerates decoding at substantial memory cost that limits long-context applications.
Method
Sparse-dLLM combines sparse attention with delayed bidirectional cache eviction, retaining salient tokens while evicting low-importance prefix and suffix entries.
Results
Sparse-dLLM delivers comparable downstream performance, up to 10× higher throughput than vanilla dLLMs, and nearly identical memory costs.
Takeaways & Limitations
Stable, sparse attention patterns support training-free cache pruning that improves dLLM efficiency without materially increasing peak memory.
Abstract
from arXiv · showhide
Diffusion Large Language Models (dLLMs) enable breakthroughs in reasoning and parallel decoding but suffer from prohibitive quadratic computational complexity and memory overhead during inference. Current caching techniques accelerate decoding by storing full-layer states, yet impose substantial memory usage that limit long-context applications. Our analysis of attention patterns in dLLMs reveals persistent cross-layer sparsity, with pivotal tokens remaining salient across decoding steps and low-relevance tokens staying unimportant, motivating selective cache eviction. We propose Sparse-dLLM, the first training-free framework integrating dynamic cache eviction with sparse attention via delayed bidirectional sparse caching. By leveraging the stability of token saliency over steps, it retains critical tokens and dynamically evicts unimportant prefix/suffix entries using an attention-guided strategy. Extensive experiments on LLaDA and Dream series demonstrate Sparse-dLLM achieves up to 10$\times$ higher throughput than vanilla dLLMs, with comparable performance and similar peak memory costs, outperforming previous methods in efficiency and effectiveness. The code is available at https://github.com/OpenMOSS/Sparse-dLLM.
Introduction
dLLMs offer parallel decoding and advanced reasoning but face quadratic inference cost because they recompute sequence-wide states. Sparse-dLLM exploits persistent attention sparsity and stable token saliency to evict unimportant cache entries while preserving performance and memory efficiency.
- Motivation: dLLMs incur O(L^2) decoding complexity because QKV states for the entire sequence are recomputed at every inference step.This includes the prompt, generated tokens, and mask tokens.
- Attention analysis: Attention in dLLMs is sparse across layers, combining local neighbor focus with vertical concentration on a few pivotal keys.These patterns persist across layers, while most positions receive minimal attention weights.
- Attention analysis: Tokens receiving significant attention remain stable across decoding steps, while low-salience tokens remain persistently minimally relevant.This stability motivates selective eviction of unimportant KV cache entries.
- Sparse-dLLM: Sparse-dLLM is a training-free framework that combines delayed bidirectional sparse caching with dynamic eviction of low-importance prefix and suffix entries.Cache updates are delayed by one step, and attention-guided retention preserves critical tokens.
- Results: Up to 10× higher throughput than vanilla dLLMs is achieved while maintaining comparable performance and nearly identical memory costs.The reported gains span experiments on LLaDA and Dream series models.
Related Work
KV-cache optimization addresses the memory and computation costs of long-context autoregressive decoding, while newer methods adapt caching ideas to bidirectional dLLMs. These approaches rely on the near-identity of KV states across consecutive decoding steps to accelerate inference without compromising output quality.
- Autoregressive LLMs: Autoregressive KV caches trade memory for computation, but cache size grows with input length and limits long-context deployment.Token eviction is a common strategy for reducing this cache burden.
- Autoregressive LLMs: Existing autoregressive cache-sparsification methods use fixed rules, past attention scores, or filtering based on previous tokens.
- dLLM caching: dLLM caching methods exploit near-identical KV states across consecutive decoding steps to accelerate bidirectional decoding without compromising output quality.Examples include dLLM-Cache, dKV-Cache, FreeCache, and Fast-dLLM.
Method
Sparse-dLLM accelerates dLLM inference by exploiting sparse, temporally stable token saliency to retain important KV entries and evict unimportant prefix and suffix entries. Its delayed bidirectional caching strategy reduces cache size while supporting efficient decoding.
- Inference background: dLLMs iteratively unmask sequences, but recomputing attention states for the full sequence at every step creates substantial inference overhead.The sequence transitions from a fully masked initial state to a final unmasked output through T decoding steps.
- Attention analysis: Attention is sparse across layers, combining local neighbor focus with vertical concentration on a few pivotal keys.Most positions receive minimal attention weights, and these patterns persist uniformly across layers.
- Attention analysis: Token saliency outside the current block remains remarkably consistent across inference steps, allowing low-salience entries to be identified early and evicted.The method does not specifically optimize the stable local pattern because its effective window is much smaller than the block length.
- Dynamic bidirectional cache eviction: Sparse-dLLM dynamically evicts low-importance KV entries from both prefix and suffix tokens using attention-aware sparse patterns and a predefined retention ratio.This extends cache eviction beyond autoregressive approaches that sparsify only prefix tokens.
- Efficiency outcome: Dynamic bidirectional eviction reduces KV cache entries, decreasing memory consumption while boosting inference throughput.Sparse-dLLM is presented as a training-free framework integrating dynamic cache eviction with sparse attention.
- Delayed cache updates: The method delays cache updates by one step because KV-state variation is relatively significant between steps 0 and 1.The delay is intended to mitigate instability before cached states have stabilized.
Experiment
Experiments on LLaDA and Dream evaluate accuracy, throughput, and peak memory across benchmarks and context lengths. Sparse-dLLM delivers the strongest throughput gains while maintaining comparable performance and near-baseline memory costs.
- Evaluation setup: Experiments evaluate benchmark accuracy, throughput in tokens per second, and peak memory consumption in GB across multiple dLLM models.Performance averages use three independent trials, while efficiency averages use ten shared randomly sampled instances.
- Main results: Sparse-dLLM achieves the most significant throughput improvement while maintaining or slightly enhancing performance with nearly identical peak memory to vanilla dLLMs.
- Throughput: 5.8× speedup raises LLaDA-8B-Instruct throughput from 4.57 TPS to 26.45 TPS on GSM8K.
- Throughput: 5.2× acceleration raises Dream-v0-7B-Instruct throughput from 6.29 TPS to 32.63 TPS on GPQA.
- Memory: Sparse-dLLM keeps LLaDA peak memory within 0.5 GB of baseline and can use less memory than baseline on Dream.On Dream, block-wise decoding requires logits only from the current block.
- Performance boundary: Sparse-dLLM improves efficiency while maintaining comparable performance, but underperforms baseline and cache methods on Dream HumanEval.The authors conjecture that code tasks require a complete context.
- Long-context efficiency: At 4k sequence length, Sparse-dLLM reaches up to 10× the throughput of vanilla dLLMs and avoids the long-context memory growth that causes Fast-dLLM OOM errors.Other cache methods provide limited throughput improvements compared with the baseline.
- Long-context efficiency: Sparse-dLLM combines high throughput with low memory consumption for long-context processing.
Ablations and Analysis
Ablations identify one-step delayed cache updates, bidirectional sparsification, and retention ratio 0.5 with kernel size 3 as effective design choices. These settings balance accuracy, throughput, and memory across the tested configurations.
- N-Step Delayed Cache Updates: 1-step cache-update delay is selected as optimal because longer delays progressively reduce throughput while accuracy varies non-monotonically.Accuracy peaks at a 3-step delay, but the authors select 1-step for its near-optimal accuracy-efficiency trade-off.
- Sparsity Strategy: Figure 5 compares efficiency across context lengths for LLaDA and Dream, with missing points denoting OOM on an NVIDIA 4090 with 48 GB memory.
- Sparsity Strategy: Bidirectional sparsification outperforms prefix-only sparsification, especially on Dream MATH, and better mitigates LLaDA performance degradation.
- Hyperparameters: Retention Ratio and Kernel Size: Figure 6 reports GSM8K 4-shot accuracy and peak memory while varying retention ratio and kernel size.
- Hyperparameters: Retention Ratio and Kernel Size: Retention ratio 0.5 is selected because higher ratios yield diminishing accuracy gains while memory consumption grows linearly.
- Hyperparameters: Retention Ratio and Kernel Size: Kernel size 3 produces the highest accuracy on both LLaDA and Dream when retention ratio is fixed at 0.5.Both smaller kernels and kernels of at least 5 reduce accuracy.
Conclusion
Sparse-dLLM is a training-free method that combines sparse attention with dynamic bidirectional cache eviction for dLLMs. It delivers comparable downstream performance, up to 10× higher throughput than vanilla dLLMs, and nearly identical memory costs.
- Sparse-dLLM dynamically evicts unimportant KV cache entries for both prefix and suffix tokens.The method combines sparse attention with bidirectional cache eviction.
- 10× higher throughput than vanilla dLLMs is achieved while maintaining comparable downstream-task performance.
- Sparse-dLLM has nearly identical memory costs to vanilla dLLMs.
Algorithmic Pseudocode
The algorithms identify important KV states outside the current decoding block, retain a ratio-selected subset, and reuse cached states according to delayed cache-management logic. Prefix-sparse processing evicts only states before the current block while preserving complete states after it.
- Dynamic Bidirectional Cache Eviction: KV states outside the current decoding block are scored from average query attention, max-pooled, and filtered by retention ratio r.Top-ranked indices identify pivotal tokens whose KV states are stored for subsequent computation.
- Delayed Cache Updates: A one-step delayed strategy assigns the first decoding step to cache updating and later steps to cache reuse.The cache states are 1 for updating and 2 for reusing cached states after the first step.
- Prefix-Sparse: Prefix-sparse processing evicts KV states before the current block and concatenates complete KV states after the current block.
- Cache Management Logic: Cache management either performs full-sequence attention, updates the cache, or concatenates cached states with current-block states.
Experiment Details
Experiments cover seven benchmarks with mostly consistent configurations designed to test generalization while limiting task-specific tuning. Comparative cache methods use model-series-specific refresh intervals and listed prompt-response settings.
- Benchmark Configurations: The benchmark suite includes MMLU, ARC-C, PIQA, GPQA, GSM8K, Math, and HumanEval.HumanEval uses more decoding steps and a longer generation length because of its distinct task nature.
- Benchmark Configurations: Configurations are kept consistent across benchmarks except HumanEval to minimize task-specific hyperparameter tuning.
- Comparative Method Settings: dKV-Cache uses refresh intervals of 8 for LLaDA models and 4 for Dream models.
- Comparative Method Settings: dLLM-Cache uses prompt and response refresh intervals denoted Kp and Kr, with model-specific values listed for four models.The configurations include LLaDA-8B-Instruct, LLaDA-1.5, Dream-v0-7B-Base, and Dream-v0-7B-Instruct.
More Results
Long-context experiments evaluate Sparse-dLLM on LongBench using a 4k-token input, 32-token blocks, and 512 decoding steps and generated tokens. The reported results indicate an almost negligible impact on long-context capability.
- Long-Context Evaluation: LongBench experiments use 4k-token inputs, block length 32, and 512 decoding steps and generation tokens.
- Long-Context Evaluation: Sparse-dLLM has an almost negligible impact on the model’s long-context capability.
More Ablations and Analysis
The ablations evaluate GSM8K accuracy across retention ratios and kernel sizes, and compare pooling operations. Attention heatmaps show that most pivotal tokens carry no semantic information, while both pooling operations improve performance with marginal differences between them.
- Retention and kernel ablations: GSM8K (4-shot) accuracy is evaluated across retention ratios and kernel sizes for LLaDA-8B-Instruct.Table 7 marks the top-1 and top-2 performance for each retention ratio.
- Attention analysis: Most pivotal tokens identified in attention heatmaps carry no semantic information, including line breaks and spaces.The observation motivates future fine-grained acceleration approaches for dLLMs.
- Pooling ablation: The two pooling operations show marginal performance differences, with both improving model performance.The comparison is conducted on LLaDA-8B-Instruct.