Research map / Image generation / Fast diffusion sampling

Confidence-Based Decoding is Provably Efficient for Diffusion Language Models

NeurIPS 2026 · Image generation › Fast diffusion sampling · approach: Masked diffusion language model decoding · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first convergence analysis for confidence-based (entropy sum-threshold) unmasking in masked diffusion language models, showing KL-accurate sampling in expected O~(H(X_0)/ε) iterations under an optimal mask predictor.

Problem

Confidence-based decoding strategies for diffusion language models perform well empirically, but their adaptive unmasking order and batch sizes lack theoretical sampling-efficiency guarantees.

Approach

Random-order unmasking that keeps adding tokens to a batch until the cumulative pointwise conditional entropy exceeds a threshold; a mutual-information decomposition with dyadic size envelopes shows KL error scales with the threshold times log L, while iteration count is bounded by total entropy divided by the threshold.

Key results

• Entropy sum-based decoding achieves eps-accurate sampling in KL with E[T] <= 4(H(X_0)/eps + 1)(log2 L + 1) + 1 under an optimal mask predictor.
• Maximum entropy-based decoding achieves E[T] <= 2 sqrt(H(X_0) L / eps) + 1, which is looser and requires knowing H(X_0) to set parameters.
• Iteration complexity is sublinear in L when H(X_0) << L, adapting automatically to data without hyperparameter tuning.

Limitations

• Analysis assumes an optimal (true-marginal) mask predictor; no training error considered.
• Uses a random unmasking order rather than the deterministic confidence-sorted order used in practice.
• Only entropy is analyzed; other confidence measures are left open.

Experimental setup

Metrics: KL divergence expected number of iterations

Baselines: uniform random step-size schedules maximum entropy-based decoding

Builds on: masked diffusion models uniform decoding convergence analysis (mutual information) randomized step-size schedules

Closest papers by meaning

• PACE-dLLM: Elastic Block Decoding via Confidence Cliff Estimation for Diffusion Language Models (NeurIPS 2026 · similarity 0.92)
• Re-evaluating Confidence Remasking in Masked Diffusion Language Models (NeurIPS 2026 · similarity 0.92)
• Fast and Fluent Diffusion Language Models via Convolutional Decoding and Rejective Fine-tuning (NeurIPS 2025 · similarity 0.91)
• Dynamically Structured Diffusion Language Model Decoding via Bayesian Inference (NeurIPS 2026 · similarity 0.91)
• Fast-dLLM++: Fr\'{e}chet Profile Decoding for Faster Diffusion LLM Inference (NeurIPS 2026 · similarity 0.90)
• Entropy-informed Decoding: Adaptive Information-Driven Branching (ICML 2026 · similarity 0.90)