DepCap: Adaptive Block-Wise Parallel Decoding for Efficient Diffusion LM Inference
DepCap uses cross-step dependency and conflict-aware decoding, reaching up to 5.63× speedup with negligible quality loss.
Key Findings
Methodology
DepCap is a training-free, plug-and-play framework with DepGA-Block and CAP-Decoding. DepGA-Block measures how the last decoded block changes future predictive distributions through KL divergence, while entropy represents residual uncertainty; their normalized difference determines the next boundary. CAP-Decoding first forms a confidence-filtered candidate pool, then removes pairwise-conflicting tokens before parallel commitment.
Key Results
- Across LLaDA-8B-Instruct, Dream-v0-base-7B, and LLaDA-1.5 on GSM8K, Math-500, MBPP, and HumanEval, DepCap improves the speed-quality frontier; on the LLaDA family it averages 3.57× speedup over vanilla decoding without significant degradation.
- On MBPP with LLaDA-1.5, DepCap reaches up to 5.63× speedup while improving relative accuracy by 7.4%. On LLaDA-8B-Instruct, CAP-Decoding with 32-token blocks reaches 21.6 TPS and NFE 71.5 on GSM8K.
- Ablations show complementary roles: DepGA-Block stabilizes adaptive boundaries, while CAP-Decoding increases safe parallelism. The information-theoretic analysis links expected KL influence to conditional mutual information and approximate token-wise additivity.
Significance
The paper addresses the central deployment tension of DLMs: parallel generation is attractive, but multi-step denoising and unsafe simultaneous commitments can erase its benefit. DepCap requires no retraining and uses only inference-time distributions, so it transfers across LLaDA and Dream backbones and remains compatible with block-wise KV-cache methods. For reasoning and coding services, fewer model evaluations and higher TPS can reduce latency and cost without the quality collapse caused by oversized blocks or indiscriminate confidence thresholds.
Technical Contribution
DepCap replaces fixed schedules and current-step heuristics with a cross-step signal: last-block influence. Its score is S_k=I~_k−λH~_k; scanning to the first negative score determines the boundary, with length clipped to [L_min,L_window]. CAP-Decoding defines D_ij=log p_i(ŷ_j)+log p_j(ŷ_i), then uses high-confidence priority followed by greedy conflict-aware selection. The analysis interprets expected KL as I(Z_k;B|c), and under limited local overlap supports approximate additivity across candidate positions.
Novelty
AdaBlock, Swordsman, and GeoBlock use special-token structure, entropy changes, or attention geometry, mainly from the current decoding state. DepCap instead explicitly uses the already decoded block as a temporal information source and separately models token-level conflicts. Its fundamental novelty is the division of labor between a cross-step dependency signal for block partitioning and a pairwise conflict signal for parallel selection, achieved without training.
Limitations
- The method assumes predictive distributions are sufficiently calibrated and that KL shifts reflect useful semantic dependence. If these assumptions fail, especially under long-range dependencies, boundaries may become too aggressive or too conservative.
- Pairwise conflict scoring can add overhead when blocks contain many candidates. Evaluation is concentrated on four benchmarks, 256-token generation, and a single A100, leaving long-context, sampling, batching, and very large-model behavior less established.
Future Work
Promising directions include subquadratic conflict-graph approximations, online calibration of λ and confidence thresholds, and joint optimization with KV-cache refresh policies. Broader evaluation should cover long-context reasoning, stochastic sampling, high-concurrency serving, LLaDA 2.0-scale models, and hardware-aware scheduling. A learned but lightweight controller could combine dependency, uncertainty, and semantic-boundary signals while preserving the no-retraining deployment advantage.
AI Executive Summary
Diffusion language models (DLMs) can revise many token positions simultaneously and exploit bidirectional context, offering a possible alternative to left-to-right generation. Yet multi-step denoising creates a difficult speed-quality trade-off. Fixed block sizes waste available parallelism on easy regions and become risky on dependent regions, while confidence-only decoding may commit mutually conflicting tokens at once.
DepCap is a training-free framework designed around the two decisions in block-wise inference. DepGA-Block compares predictive distributions before and after the last decoded block, using KL divergence I_k as a cross-step influence signal and entropy H_k as uncertainty. It stops expansion when S_k=I~_k−λH~_k becomes negative. CAP-Decoding creates candidates with confidence at least 0.8, prioritizes tokens above 0.95, and filters pairwise conflicts using D_ij=log p_i(ŷ_j)+log p_j(ŷ_i), with γ=-16.0 in the default setting.
Experiments on LLaDA-8B-Instruct, Dream-v0-base-7B, and LLaDA-1.5 cover GSM8K, Math-500, MBPP, and HumanEval. DepCap averages 3.57× speedup over vanilla decoding on the LLaDA family; on LLaDA-1.5 MBPP it reaches 5.63× speedup with a 7.4% relative accuracy improvement. The results suggest that temporal dependency and explicit token conflict are more informative controls than rigid schedules or confidence alone, although broader long-context and systems evaluation remains necessary.
Deep Analysis
Background
DLMs generate text by iterative masked denoising, enabling parallel updates and bidirectional attention. LLaDA, Dream, and Mercury have made the paradigm increasingly practical, but repeated model evaluations remain expensive. Fast-dLLM and related block-wise methods restrict refinement to sequential blocks; AdaBlock uses special tokens, Swordsman entropy changes, and GeoBlock attention geometry. These methods improve efficiency but mostly use fixed or current-step signals, missing temporal information accumulated across denoising steps.
Core Problem
Block-wise inference must decide both the next boundary and the subset of positions to decode simultaneously. Fixed lengths cannot adapt to input structure or generation stage. Confidence-only parallel decoding treats positions independently: lowering its threshold increases throughput but may commit interacting tokens together. The challenge is to obtain cross-step and token-level signals from existing model outputs, without retraining or sacrificing cache compatibility.
Innovation
DepGA-Block treats the last decoded block as an information-bearing intervention: it measures the KL shift in each future position and balances that support against predictive entropy. CAP-Decoding explicitly constructs a conflict-free subset rather than trusting confidence alone. Both modules are inference-only and can be layered onto existing block-wise DLM systems and KV-cache strategies. The accompanying analysis connects the empirical score to conditional mutual information.
Methodology
- �� Initialize the target as [MASK] and define a local window L_window=min(L_max,L_remain).
- �� For each future position compute I_k=KL(p_curr^k||p_prev^k) and H_k=H(p_curr^k); smooth and locally normalize them.
- �� Form S_k=I~_k−λH~_k, stop before the first S_k<0, and clip the resulting length to [L_min,L_window]; use L_min for cold start.
- �� Within the selected block, define confidence c_i=max_v p_i(v) and retain c_i≥τ_low.
- �� Compute D_ij=log p_i(ŷ_j)+log p_j(ŷ_i). Select τ_high candidates first, remove their conflicts, then greedily add remaining candidates by confidence while deleting conflicts.
- �� If no safe set exists, decode the highest-confidence position. The theory approximates cumulative influence by an additive sum when local information overlap is limited.
Experiments
The study evaluates LLaDA-8B-Instruct, Dream-v0-base-7B, and LLaDA-1.5 on one NVIDIA A100 40GB GPU with generation length 256. Tasks are 5-shot GSM8K, 4-shot Math-500, 3-shot MBPP, and 0-shot HumanEval, evaluated through lm-eval. Baselines include vanilla one-token decoding, confidence decoding with fixed 16/32/64-token blocks, AdaBlock, DepGA-Block, and full CAP-Decoding. Metrics are accuracy, tokens per second, and NFE. Defaults are λ=1.2, L_min=8, L_max=128, τ_low=0.8, τ_high=0.95, and γ=-16.
Results
DepCap consistently improves the speed-quality frontier across backbones and tasks. On the LLaDA family it averages 3.57× speedup over vanilla decoding. On LLaDA-1.5 MBPP, it reaches 5.63× speedup and a 7.4% relative accuracy gain. For LLaDA-8B-Instruct on GSM8K, 32-token CAP-Decoding obtains 21.6 TPS, NFE 71.5, and 77.3 accuracy; the full DepCap configuration obtains 21.4 TPS, NFE 74.8, and 78.8 accuracy. Large fixed blocks can be faster but less reliable.
Applications
DepCap is directly relevant to high-throughput DLM serving for code completion, mathematical reasoning, document drafting, and interactive assistants. Operators can integrate it into LLaDA or Dream inference, retain KV-cache acceleration, and tune λ and thresholds against a quality budget. Its strongest immediate value is latency-sensitive GPU serving where repeated denoising calls dominate cost. Calibration and conflict computation should be profiled for large batches.
Limitations & Outlook
The information-theoretic motivation assumes limited overlap among local future positions; long-range syntax or semantic dependencies may violate this assumption. KL influence is also not guaranteed to be a causal measure of useful information under poorly calibrated distributions. CAP-Decoding may incur pairwise overhead for large candidate pools. The evidence is limited to four benchmarks, 256-token outputs, and one A100, with limited analysis of sampling, batching, long context, and billion-scale deployment.
Plain Language Accessible to non-experts
Imagine a restaurant with many orders and a kitchen that can prepare several dishes at once. A rigid system always handles exactly the same number of orders per round. That is wasteful when the orders are simple, but dangerous when the next dishes depend heavily on the previous round. DepCap first checks how much the last completed batch changed the plan for upcoming orders. If the change is strong and the next orders look clear, it expands the next batch; if the plan becomes uncertain, it stops earlier.
It also checks whether two dishes are fighting over the same ingredient or whether choosing one would change the other. Highly reliable, non-conflicting dishes are prepared together, while risky pairs are separated. The kitchen therefore gains parallel speed without blindly doing everything at once. DepCap does not retrain the chefs or change the recipes; it changes the scheduling rule. In the paper, this scheduling reaches up to 5.63× speedup and can even improve accuracy on a code benchmark, although complicated orders and the checking process still impose limits.
ELI14 Explained like you're 14
Picture a super-smart writing bot filling a story with many blank spaces. It does not write strictly from the first word to the last. Instead, it guesses lots of spaces, checks the whole story, and keeps fixing mistakes. That can be fast—but if it changes two connected sentences at the same time, they might disagree. If it changes only one space per turn, it becomes painfully slow.
DepCap acts like a clever team captain. After one group of words is finished, it asks: “Did this group give strong clues about the next spaces?” If yes, the next group can be bigger. If the next part still looks confusing, the group becomes smaller. No fixed rule like “always 32 words” is required.
Then it checks for arguments between blank spaces. Very confident spaces that do not interfere can be solved together. Spaces that might change one another wait their turn. In experiments, the method made LLaDA-family generation about 3.57 times faster on average. On the MBPP coding test with LLaDA-1.5, it reached 5.63 times the speed and improved relative accuracy by 7.4%.
So DepCap does not magically add knowledge to the model. It helps the model choose a smarter work order—like a game team assigning easy, independent quests in parallel while separating quests that need the same character. It may still struggle with very long connections, and checking conflicts costs some time, but it is a practical way to be faster without becoming careless!
Glossary
Diffusion Language Model (DLM)
A language model that generates text through repeated denoising or unmasking rather than strict left-to-right prediction. It can update multiple positions and use bidirectional context.
DepCap is an inference framework for masked DLMs.
Block-wise decoding
A strategy that partitions the target sequence into blocks and decodes them sequentially. Restricting updates to the current block reduces repeated full-sequence refinement.
DepCap adapts the block boundary and block-internal selection.
Last-block influence
The KL divergence between a future position’s predictive distributions before and after the last block is decoded. A larger value indicates a stronger distributional shift caused by that block.
It is the cross-step signal in DepGA-Block.
CAP-Decoding
Conflict-Aware Parallel Decoding, which combines confidence filtering with pairwise conflict detection. It selects a safe subset of positions for simultaneous decoding.
It controls within-block parallelism.
Function evaluations (NFE)
The number of model or denoising calls used during generation. Lower NFE generally indicates lower computation, whereas TPS also reflects hardware and sequence-length effects.
The paper reports NFE alongside accuracy and TPS.
Conditional mutual information
Information that one variable provides about another given a context variable. In the analysis, expected last-block KL influence equals I(Z_k;B|c).
It theoretically motivates the dependency score.
Open Questions Unanswered questions from this research
- 1 It remains unclear whether KL distributional shifts reliably represent useful semantic dependence under long contexts, stochastic sampling, or poorly calibrated models. Large-scale controlled studies are needed.
- 2 The practical trade-off between pairwise conflict computation and GPU throughput is underexplored, especially for large batches, long blocks, and high-concurrency serving.
Applications
Immediate Applications
Code-generation serving
Integrate DepCap into LLaDA or Dream code assistants, reuse block-wise KV-cache, and calibrate λ, τ_low, τ_high, and γ on MBPP or HumanEval-like workloads. The expected outcome is lower latency while preserving functional correctness.
Reasoning APIs
Use adaptive boundaries and conflict filtering for GSM8K- or Math-500-style requests. Providers can select thresholds using a joint accuracy, TPS, and NFE budget instead of optimizing speed alone.
Long-term Vision
Adaptive DLM inference controllers
Combine dependency signals, uncertainty, conflict graphs, and cache-refresh policies into a hardware-aware runtime controller. Such a system could automatically target a requested quality level while maximizing throughput across models and tasks.
Abstract
Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive language generation due to their potential for parallel decoding and global refinement of the entire sequence. To unlock this potential, DLM inference must carefully balance generation quality and decoding speed. Recent block-wise DLM decoding methods improve this trade-off by performing diffusion-based decoding sequentially in blocks. However, existing methods typically rely on fixed block schedules or current-step local signals to determine block boundaries, and use conservative confidence-based parallel decoding to avoid conflicts, limiting the quality-speed trade-off. In this paper, we argue that block-wise DLM inference requires more suitable signals for its two core decisions: cross-step signals for determining block boundaries, and token-level conflict signals for parallel decoding. Based on this view, we propose DepCap, a training-free framework for efficient block-wise DLM inference. Specifically, DepCap instantiates the cross-step signal as the influence of the last decoded block and uses it to adaptively determine how far the next block should extend, while identifying a conflict-free subset of tokens for safe parallel decoding within each block, enabling substantial inference acceleration with negligible quality degradation. DepCap is a plug-and-play method applicable to various DLMs, and compatible with existing KV-cache strategies for block-wise DLM. An information-theoretic analysis further suggests that the cumulative last-block influence on a candidate block is approximately additive across tokens, supporting the proposed block-partitioning criterion. Experimental results show that DepCap achieves favorable speed-quality trade-offs across multiple DLM backbones and reasoning and coding benchmarks, with up to 5.63$\times$ speedup without significant performance degradation.