# From Bits to Rounds: Parallel Decoding with Exploration for Diffusion Language Models

arXiv: https://arxiv.org/abs/2511.21103 · HTML: https://mlsanity.com/paper/2511.21103/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 35 of its 39 references that are in the map.
- First posted on arXiv 26 Nov 2025.

## Placed in

- Diffusion models / [Discrete and text diffusion](https://mlsanity.com/diffusion/discrete-and-text-diffusion/)
- Efficient LLM inference and serving / [Diffusion LLM and MoE inference](https://mlsanity.com/inference/diffusion-llm-and-moe-inference/)

## Builds on (most cited first, 30 of 35)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [MaskGIT: Masked Generative Image Transformer](https://mlsanity.com/paper/2202.04200/) (2022)
- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [Diffusion Forcing: Next-token Prediction Meets Full-Sequence Diffusion](https://mlsanity.com/paper/2407.01392/) (2024)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [Beyond the 80/20 Rule: High-Entropy Minority Tokens Drive Effective Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2506.01939/) (2025)
- [Dream 7B: Diffusion Large Language Models](https://mlsanity.com/paper/2508.15487/) (2025)
- [Fast-dLLM: Training-free Acceleration of Diffusion LLM by Enabling KV Cache and Parallel Decoding](https://mlsanity.com/paper/2505.22618/) (2025)
- [Block Diffusion: Interpolating Between Autoregressive and Diffusion Language Models](https://mlsanity.com/paper/2503.09573/) (2025)
- [Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data](https://mlsanity.com/paper/2406.03736/) (2024)
- [LLaDA 1.5: Variance-Reduced Preference Optimization for Large Language Diffusion Models](https://mlsanity.com/paper/2505.19223/) (2025)
- [Scaling Diffusion Language Models via Adaptation from Autoregressive Models](https://mlsanity.com/paper/2410.17891/) (2024)
- [Diffsound: Discrete Diffusion Model for Text-to-sound Generation](https://mlsanity.com/paper/2207.09983/) (2022)
- [Mercury: Ultra-Fast Language Models Based on Diffusion](https://mlsanity.com/paper/2506.17298/) (2025)
- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Masked Diffusion Models are Secretly Time-Agnostic Masked Models and Exploit Inaccurate Categorical Sampling](https://mlsanity.com/paper/2409.02908/) (2024)
- [Seed Diffusion: A Large-Scale Diffusion Language Model with High-Speed Inference](https://mlsanity.com/paper/2508.02193/) (2025)
- [dLLM-Cache: Accelerating Diffusion Large Language Models with Adaptive Caching](https://mlsanity.com/paper/2506.06295/) (2025)
- [A Reparameterized Discrete Diffusion Model for Text Generation](https://mlsanity.com/paper/2302.05737/) (2023)
- [Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking](https://mlsanity.com/paper/2505.24857/) (2025)
- [Dimple: Discrete Diffusion Multimodal Large Language Model with Parallel Decoding](https://mlsanity.com/paper/2505.16990/) (2025)
- [Path Planning for Masked Diffusion Model Sampling](https://mlsanity.com/paper/2502.03540/) (2025)
- [Diffusion Beats Autoregressive in Data-Constrained Settings](https://mlsanity.com/paper/2507.15857/) (2025)

## Built on by (most cited first, 23 of 23)

- [Confidence-Based Decoding is Provably Efficient for Diffusion Language Models](https://mlsanity.com/paper/2603.22248/) (2026)
- [Deferred Commitment Decoding for Diffusion Language Models](https://mlsanity.com/paper/2601.02076/) (2026)
- [Why Diffusion Language Models Struggle with Truly Parallel (Non-Autoregressive) Decoding?](https://mlsanity.com/paper/2602.23225/) (2026)
- [Residual Context Diffusion Language Models](https://mlsanity.com/paper/2601.22954/) (2026)
- [Adaptation to Intrinsic Dependence in Diffusion Language Models](https://mlsanity.com/paper/2602.20126/) (2026)
- [Locally Confident, Globally Stuck: The Quality-Exploration Dilemma in Diffusion Language Models](https://mlsanity.com/paper/2604.00375/) (2026)
- [Top 10 Open Challenges Steering the Future of Diffusion Language Model and Its Variants](https://mlsanity.com/paper/2601.14041/) (2026)
- [Plan, Verify and Fill: A Structured Parallel Decoding Approach for Diffusion Language Models](https://mlsanity.com/paper/2601.12247/) (2026)
- [TRIMS: Trajectory-Ranked Instruction Masked Supervision for Diffusion Language Models](https://mlsanity.com/paper/2604.00666/) (2026)
- [ConvergeFlow: Language Flow with Provable Convergence to Token Embeddings](https://mlsanity.com/paper/2608.23551/) (2026)
- [Can I Have Your Order? Monte-Carlo Tree Search for Slot Filling Ordering in Diffusion Language Models](https://mlsanity.com/paper/2602.12586/) (2026)
- [GeoBlock: Inferring Block Granularity from Dependency Geometry in Diffusion Language Models](https://mlsanity.com/paper/2603.26675/) (2026)
- [PSD: Pushing the Pareto Frontier of Diffusion LLMs via Parallel Speculative Decoding](https://mlsanity.com/paper/2605.15609/) (2026)
- [Visual-Redundancy-Controlled Parallel Decoding for Diffusion-Based Multimodal Large Language Models](https://mlsanity.com/paper/2605.25820/) (2026)
- [Ripple-Pivot Search: Active Parallel Decoding for Diffusion Large Language Models](https://mlsanity.com/paper/2608.11742/) (2026)
- [Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling](https://mlsanity.com/paper/2608.25505/) (2026)
- [LEAP: Unlocking dLLM Parallelism via Lookahead Early-Convergence Token Detection](https://mlsanity.com/paper/2605.10980/) (2026)
- [Diffusion Language Models for Mobile Edge Agentic AI: Foundations, Applications, and Challenges](https://mlsanity.com/paper/2609.04778/) (2026)
- [d-OPD: Future-Aware On-Policy Distillation for Block Diffusion Language Models](https://mlsanity.com/paper/2609.35362/) (2026)
- [HyperZip: Efficient Data Compression through Personalized Diffusion LLMs with Hypernetworks](https://mlsanity.com/paper/2609.36357/) (2026)
- [Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure](https://mlsanity.com/paper/2609.37841/) (2026)
- [Blackboard Intelligence Can Surpass Autoregressive on Globally Constrained Problems](https://mlsanity.com/paper/2609.38806/) (2026)
- [Fork-dLLM: Avoiding the Flexibility Trap in Diffusion Language Models](https://mlsanity.com/paper/2609.39859/) (2026)

## Abstract (arXiv)

Diffusion Language Models (DLMs) have recently emerged as a strong alternative to autoregressive language models (LMs). DLMs offer comparable accuracy with faster inference speed via parallel decoding. However, standard DLM decoding strategies relying on high-confidence tokens encounter an inherent information-theoretic bottleneck that restricts decoding progress and ultimately slows generation. We demonstrate both theoretically and empirically that prioritizing high-confidence tokens is inherently inefficient. High-probability tokens carry negligible information and strictly relying on them limits the effective progress made in each decoding round. We prove that the number of decoding rounds must grow linearly with the sample's total information (negative log-likelihood) and inversely with the per-round information budget, establishing a bits-to-rounds principle. We also propose Explore-Then-Exploit (ETE), a training-free decoding strategy that maximizes information throughput and decoding efficiency. ETE combines cross-block decoding with targeted exploration of high-uncertainty tokens to reshape the conditional distribution and trigger cascades of confident predictions. Experiments verify our theoretical bounds and demonstrate that ETE consistently reduces the required number of decoding rounds compared to confidence-only baselines without compromising generation quality.