CreditDecoding: Accelerating Parallel Decoding in Diffusion Large Language Models with Trace Credit

1. Problem Statement

Diffusion Large Language Models (dLLMs) generate text through iterative denoising, offering advantages in reasoning and bidirectional context over autoregressive models (ARMs). However, their inference efficiency is a major bottleneck due to:

• Computational Redundancy: In standard parallel decoding, tokens are often predicted correctly early in the denoising process but are not "decoded" (finalized) until their confidence exceeds a high threshold. This forces the model to repeatedly predict and remask the same correct tokens, wasting iterations.
• History-Agnostic Decoding: Current methods rely solely on instantaneous confidence scores at each step. They ignore historical evidence, meaning transient fluctuations or temporary mispredictions can delay decoding or propagate errors, undermining convergence.
• Lack of KV Cache: Unlike ARMs, dLLMs typically cannot use lossless KV caches due to bidirectional attention, further increasing latency.

2. Core Methodology: CreditDecoding

The authors propose CreditDecoding, a training-free parallel decoding strategy that leverages Trace Credit to accelerate inference without modifying the model weights.

Key Concepts

• Trace Credit ($C_{i,v}^t$): A token-level score that accumulates historical evidence across denoising steps. It quantifies a token's "decoding potential" based on its consistency in the denoising trace.
• Temporal Consistency: The authors observe that the confidence of the eventual target token exhibits a consistently increasing trend as denoising progresses. Even if a token is temporarily masked, its historical trajectory suggests it is likely to be the correct token.

Algorithm Mechanics

1. Credit Accumulation:
   At each denoising step $t$, for every masked position $i$, the model maintains a credit value $C_{i,v}^t$ for each candidate token $v$.

   • Focused Enhancement: If the model's current top-1 prediction $\tilde{x}_i^t$ matches token $v$, the credit is updated using an Exponential Moving Average (EMA) rule:
     $$C_{i,v}^t = \beta C_{i,v}^{t+1} + (p_{i,v}^t)^\gamma$$
     where $\beta$ controls decay (forgetting stale evidence) and $\gamma$ is a concave transform that up-weights low-confidence values.
   • Global Decay: If a token is not the current top-1 prediction, its credit decays by $\beta$. This suppresses noise from transient spikes.

2. Logit Fusion:
   The accumulated credit is fused with the current logits to boost the confidence of consistent tokens:
   $$\hat{l}_{i,v}^t = l_{i,v}^t + \alpha \cdot \log(C_{i,v}^t + 1)$$
   This effectively applies a multiplicative gain to the probability of tokens that have shown historical stability, allowing them to cross the decoding threshold $\tau$ earlier.

3. Tuning-Free Variant:
   To avoid hyperparameter tuning, the authors propose an adaptive schedule where the fusion strength $\alpha$ and decay $\beta$ are coupled to the mask ratio $\eta_t$ (progress of denoising). As the process nears completion ($\eta_t \to 0$), the credit strength increases automatically.

3. Key Contributions

• Identification of Redundancy: The paper identifies the "temporal gap" between early correct prediction and late decoding as a primary source of inefficiency in dLLMs.
• Trace Credit Mechanism: Introduction of a novel, training-free method to accumulate historical logits into a "credit" score, acting as a prior to stabilize and accelerate decoding.
• Orthogonality: CreditDecoding operates purely on logits, making it compatible with existing optimizations like KV caching, kernel fusion, and EOS early stopping.
• Comprehensive Evaluation: Extensive testing across diverse dLLM architectures (Dense, MoE), scales (8B to 100B), and benchmarks (reasoning, coding, knowledge).

4. Experimental Results

The method was evaluated on eight benchmarks (MMLU, SQuAD2.0, GSM8K, MATH, HumanEval, etc.) using models like LLaDA-8B-Instruct and LLaDA-MoE-Instruct.

• Speedup: CreditDecoding achieves up to 5.48× speedup (measured in Tokens Per Forward, TPF) on LLaDA-8B-Instruct compared to the baseline.
• Accuracy: Contrary to typical speed-accuracy trade-offs, the method improves average accuracy by +0.48 points on LLaDA-8B-Instruct.
• Scalability:
  • Model Scale: Effective across models from 8B to 100B parameters.
  • Context Length: Performance scales well to long contexts (up to 4096 tokens), maintaining a consistent ~7× TPF speedup.
• Orthogonality: When combined with other acceleration techniques (e.g., Fast-dLLM, KV Cache, PyTorch Compiler), CreditDecoding further boosts speed and mitigates accuracy drops caused by aggressive compression.
• Robustness: It outperforms state-of-the-art methods like Fast-dLLM across diverse decoding strategies (Threshold, Top-K, Top-K Margin).

5. Significance and Impact

• Practical Deployment: As a training-free, plug-and-play module, CreditDecoding can be immediately integrated into existing dLLM inference pipelines without retraining.
• Bridging the Gap: It effectively narrows the gap between the theoretical acceleration limit (the "ideal decoding boundary") and actual performance by reducing redundant iterations.
• Future of dLLMs: By addressing the inherent inefficiencies of parallel decoding, this work makes dLLMs more viable for real-world applications requiring low latency and high throughput, potentially accelerating their adoption alongside autoregressive models.

In summary, CreditDecoding transforms the denoising process from a memoryless, step-by-step gamble into a history-aware, credit-based accumulation system, significantly accelerating dLLM inference while enhancing robustness.