DepCap: Unlocking 5x Speedup in Diffusion LMs via Adaptive Dependency Mapping

TL;DR

Diffusion Language Models (DLMs) offer a promising parallel alternative to traditional autoregressive generation, but their multi-step denoising process often leads to slow inference. DepCap is a new training-free framework that shatters this bottleneck. By adaptively adjusting block sizes based on "cross-step influence" and explicitly detecting "token conflicts," DepCap achieves up to 5.63× speedup on coding tasks without sacrificing accuracy.

Problem & Motivation: The "Static Block" Trap

Traditional DLMs generate text by iteratively refining a sequence of [MASK] tokens. To speed this up, researchers recently moved toward block-wise decoding. However, these methods suffer from two major flaws:

1. Rigid Boundaries: They use fixed block sizes (e.g., 32 tokens) or simple local heuristics, ignoring the fact that different parts of a sentence require different amounts of contextual "re-thinking."
2. Conservative Parallelism: To avoid errors, they only decode tokens with extremely high confidence. If they lower this threshold, they often encounter "token conflicts"—where two decoded positions contradict each other because they weren't modeled together.

The authors of DepCap realized that the signal for the next block boundary lies in how much the previous block changed the model's mind.

Methodology: The Core Mechanics

DepCap introduces two primary modules that function at different granularities of the decoding process.

1. DepGA-Block: Adaptive Partitioning

Instead of guessing the next block size, DepCap measures the Last-Block Influence ($I_k$). It calculates the KL divergence between the predictive distribution before and after the last block was decoded.

• If the last block significantly shifted the predictions for future tokens, the block should extend further.
• If uncertainty (Entropy $H_k$) starts to outweigh this influence, the block is terminated.

2. CAP-Decoding: Fighting Token Conflicts

Within a block, DepCap doesn't just look at confidence. It computes a Conflict Score ($D_{ij}$). If two tokens have high mutual entanglement—meaning the choice of one heavily impacts the probability of the other—they are flagged as a "conflict." DepCap then selects a maximal "conflict-free" subset to decode in parallel.

Figure 1: Comparison between traditional fixed-block decoding and DepCap's adaptive, conflict-aware approach.

Experiments & Results: Performance at Scale

The authors tested DepCap on SOTA diffusion backbones like LLaDA and Dream-v0.

SOTA Comparison

In mathematical reasoning (GSM8K) and coding (MBPP/HumanEval), DepCap consistently outperformed fixed-block baselines.

• Throughput (TPS): Achieved 3.57× average acceleration.
• Accuracy: In several cases, such as MBPP with LLaDA-1.5, accuracy actually increased (by 7.4% relative) alongside the 5.63× speedup.

Ablation Study

The ablation results (Table below) show that while DepGA-Block improves the stability and accuracy of the partitioning, CAP-Decoding is the engine driving the massive jumps in inference speed (TPS).

Figure 2: Performance metrics across various benchmarks. Note the significant reduction in NFEs (Number of Function Evaluations).

Critical Analysis & Conclusion

The Takeaway: DepCap proves that the "efficiency vs. quality" trade-off in DLMs isn't a zero-sum game. By using information-theoretic signals (KL Divergence and Entropy) already present in the model's logits, we can make significantly smarter decoding decisions.

Limitations:

• The method is highly effective for block-wise decoding but hasn't yet been extended to "sliding window" diffusion, which is common in long-form generation.
• While training-free, the conflict-check ($D_{ij}$) adds a lightweight overhead that scales quadratically with the candidate pool size, though the authors mitigate this with a high-confidence priority phase.

Future Outlook: This work paves the way for "Self-Correcting" DLMs that can dynamically allocate more compute (denoising steps) to complex semantic transitions while "fast-forwarding" through predictable text. The integration of these adaptive strategies with specialized hardware kernels will likely make DLMs a fierce competitor to GPT-style autoregressive models in production environments.