Confidence-Based Decoding is Provably Efficient for Diffusion Language Models

• URL: http://arxiv.org/abs/2603.22248v1
• Date: Mon, 23 Mar 2026 17:43:21 GMT
• Title: Confidence-Based Decoding is Provably Efficient for Diffusion Language Models
• Abstract summary: Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive (AR) models for language modeling.<n>We develop the first theoretical analysis framework for confidence-based decoding in DLMs.
• Score: 8.527157686215117
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive (AR) models for language modeling, allowing flexible generation order and parallel generation of multiple tokens. However, this flexibility introduces a challenge absent in AR models: the \emph{decoding strategy} -- which determines the order and number of tokens generated at each iteration -- critically affects sampling efficiency. Among decoding strategies explored in practice, confidence-based methods, which adaptively select which and how many tokens to unmask based on prediction confidence, have shown strong empirical performance. Despite this success, our theoretical understanding of confidence-based decoding remains limited. In this work, we develop the first theoretical analysis framework for confidence-based decoding in DLMs. We focus on an entropy sum-based strategy that continues unmasking tokens within each iteration until the cumulative entropy exceeds a threshold, and show that it achieves $\varepsilon$-accurate sampling in KL divergence with an expected number of iterations $\widetilde O(H(X_0)/\varepsilon)$, where $H(X_0)$ denotes the entropy of the target data distribution. Notably, this strategy yields substantial sampling acceleration when the data distribution has low entropy relative to the sequence length, while automatically adapting to the intrinsic complexity of data without requiring prior knowledge or hyperparameter tuning. Overall, our results provide a theoretical foundation for confidence-based decoding and may inform the design of more efficient decoding strategies for DLMs.

Related papers

• Escaping Confidence Trap: Evolutionary Decoding for Mathematical Reasoning in Diffusion LLMs [69.52853771994451]
  We analyze the decoding trajectories of LLaDA 2.0 and identify a recurring diffusion confidence trap.<n>We propose Evolutionary Decoding, a training-free test-time scaling framework that views diffusion decoding as an evolutionary process.
  arXiv  Detail & Related papers  (2026-08-01T11:48:25Z)
• Stability-Weighted Decoding for Diffusion Language Models [8.670026899042483]
  Existing decoding strategies rely on static confidence metrics computed at a single denoising step, ignoring temporal history and often leading to premature unmasking of unstable tokens.<n>We propose Stability-Weighted Decoding (SWD), a training-free, plug-and-play strategy that incorporates temporal stability into token scoring and acts as a universal modulator for arbitrary score-based decoding policies.
  arXiv  Detail & Related papers  (2026-04-18T17:04:10Z)
• Attention-Based Sampler for Diffusion Language Models [16.008464195041984]
  We propose a new training-free decoding algorithm, termed Attn-Sampler.<n>We show that optimal sequence likelihood can be approximately achieved by decoding tokens in descending order of their attention column sums.
  arXiv  Detail & Related papers  (2026-03-18T07:49:13Z)
• Think Twice Before You Write -- an Entropy-based Decoding Strategy to Enhance LLM Reasoning [32.332197731504046]
  Decoding strategies play a central role in shaping the reasoning ability of large language models.<n>Traditional methods such as greedy decoding and beam search often suffer from error propagation.<n>We propose an entropy-guided decoding framework that introduces token-level adaptivity into generation.
  arXiv  Detail & Related papers  (2026-03-10T23:08:26Z)
• Self-Rewarding Sequential Monte Carlo for Masked Diffusion Language Models [58.946955321428845]
  This work presents self-rewarding sequential Monte Carlo (SMC)<n>Our algorithm stems from the observation that most existing MDLMs rely on a confidence-based sampling strategy.<n>We introduce the trajectory-level confidence as a self-rewarding signal for assigning particle importance weights.
  arXiv  Detail & Related papers  (2026-02-02T09:21:45Z)
• STDD:Spatio-Temporal Dynamics-Driven Token Refinement in Diffusion Language Models [12.172699141988728]
  diffusion language models (DLMs) generate text by iteratively denoising all token positions in parallel.<n>We propose a novel remasking approach that dynamically detects Temporal Variance and Spatial Deviance of each token.<n>Our approach significantly improves the operational efficiency of DLMs across mainstream datasets, achieving speedups of up to 8.9 times.
  arXiv  Detail & Related papers  (2025-12-07T12:53:48Z)
• Principled RL for Diffusion LLMs Emerges from a Sequence-Level Perspective [85.06838178922791]
  Reinforcement Learning (RL) has proven highly effective for autoregressive language models.<n>But adapting these methods to diffusion large language models (dLLMs) presents fundamental challenges.<n>We propose a principled RL framework that treats entire sequence generation as a single action and uses the ELBO as a tractable sequence-level likelihood proxy.
  arXiv  Detail & Related papers  (2025-12-03T13:05:32Z)
• Masked Diffusion for Generative Recommendation [30.8737219110446]
  Generative recommendation (GR) with semantic IDs (SIDs) has emerged as a promising alternative to traditional recommendation approaches.<n>We propose to instead model and learn the probability of a user's sequence of SIDs using masked diffusion.<n>We demonstrate through thorough experiments that our proposed method consistently outperforms autoregressive modeling.
  arXiv  Detail & Related papers  (2025-11-28T09:36:26Z)
• From Bits to Rounds: Parallel Decoding with Exploration for Diffusion Language Models [19.97248408121574]
  Diffusion Language Models (DLMs) offer comparable accuracy with faster inference speed via parallel decoding.<n>High-confidence tokens carry negligible information and strictly relying on them limits the effective progress made in each decoding round.<n>We propose Explore-Then-Exploit (ETE), a training-free decoding strategy that maximizes information throughput and decoding efficiency.
  arXiv  Detail & Related papers  (2025-11-26T06:38:37Z)
• Inference-Time Scaling of Diffusion Language Models with Particle Gibbs Sampling [70.8832906871441]
  We study how to steer generation toward desired rewards without retraining the models.<n>Prior methods typically resample or filter within a single denoising trajectory, optimizing rewards step-by-step without trajectory-level refinement.<n>We introduce particle Gibbs sampling for diffusion language models (PG-DLM), a novel inference-time algorithm enabling trajectory-level refinement while preserving generation perplexity.
  arXiv  Detail & Related papers  (2025-07-11T08:00:47Z)
• Beyond Exponential Decay: Rethinking Error Accumulation in Large Language Models [0.0]
  We show that errors are not uniformly distributed but are concentrated at sparse "key tokens" representing critical decision junctions.<n>We propose a framework for next-generation systems centered on selective preservation of semantically vital tokens.
  arXiv  Detail & Related papers  (2025-05-30T03:57:31Z)
• Reviving Any-Subset Autoregressive Models with Principled Parallel Sampling and Speculative Decoding [55.2480439325792]
  In arbitrary-order language models, it is an open question how to sample tokens in parallel from the correct joint distribution.<n>We find that a different class of models, any-subset autoregressive models (AS-ARMs), holds the solution.<n>We show that AS-ARMs achieve state-of-the-art performance among sub-200M parameter models on infilling benchmark tasks, and nearly match the performance of models 50X larger on code generation.
  arXiv  Detail & Related papers  (2025-04-29T06:33:13Z)
• Amortizing intractable inference in large language models [56.92471123778389]
  We use amortized Bayesian inference to sample from intractable posterior distributions. We empirically demonstrate that this distribution-matching paradigm of LLM fine-tuning can serve as an effective alternative to maximum-likelihood training. As an important application, we interpret chain-of-thought reasoning as a latent variable modeling problem.
  arXiv  Detail & Related papers  (2023-10-06T16:36:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.