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

Diffusion Language Models (DLMs) have recently emerged as a strong alternative to autoregressive language models (AR-LMs), due to their comparable accuracy and faster inference speed via parallel decoding. However, standard DLM decoding strategies, which rely on unmasking only high-confidence tokens, encounter an inherent information-theoretic bottleneck that restricts decoding progress and ultimately slows down generation. We demonstrate this through an information-theoretic lower bound that the number of decoding rounds must grow linearly with the sample's total information and inversely with the per-round information budget, establishing a bits-to-rounds principle. Motivated by this theory, we 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 across diverse benchmarks verify our theoretical bounds and demonstrate that ETE consistently reduces the number of decoding rounds compared to confidence-only baselines without compromising generation quality. Furthermore, ETE integrates efficiently with KV caching, translating these algorithmic gains into improved tokens-per-second throughput.

Common large language models produce one word or token at a time, but diffusion language models try to speed this up by filling in many blanks at once. In practice, these models often play it safe: they fill only the blanks they are most confident about, which can make each step add very little new information. Our work explains why this strategy can still be slow. We prove a “bits-to-rounds” principle: the more information an output contains, and the less information the model commits to in each step, the more decoding rounds it must take. Guided by this idea, we design Explore-Then-Exploit, a method without retraining the model. Instead of always choosing the easiest blanks, it sometimes tests uncertain but important positions, such as a word that may determine many later words, and then quickly fills in the blanks that become obvious. Across math, coding, and knowledge benchmarks, this reduces the number of generation rounds and improves throughput while maintaining output quality. Our results suggest that faster diffusion language models should not only be confident, but also strategically exploratory.