On the Error-Correcting Effects of Stochasticity in Discrete Diffusion
For practitioners using discrete diffusion models, this work provides a principled method to improve sampling efficiency without sacrificing quality, though the gains are domain-dependent.
The paper studies how stochasticity in discrete diffusion models affects the tradeoff between sampling speed and quality, identifying an error-correcting mechanism from redundant transitions. It proposes DCRS, which improves the speed-quality tradeoff, achieving up to a 10x reduction in sampling steps on image datasets while maintaining competitive quality.
Discrete diffusion models achieve strong performance in text and image generation, but their inference remains slow and must inherently balance sampling efficiency and sample quality. In this work, we present a systematic study of how the \emph{degree of stochasticity} in Markov transitions governs the sampling tradeoff. We show that highly deterministic transitions converge rapidly but suffer from error accumulation, while more stochastic transitions converge more slowly yet can achieve higher final sample quality. Using an information-theoretic analysis, we identify the underlying mechanism as an error-correcting effect induced by \emph{redundant transitions} that symmetrically exchange mass between states, and show that these transitions can provably contract sampling errors. Motivated by this analysis, we propose \emph{Discrete Churn and Restart Sampling} (DCRS), a novel inference algorithm that injects controlled stochasticity by alternating between forward and reverse diffusion processes. Experiments on synthetic datasets and large-scale benchmarks show that DCRS improves the speed-quality tradeoff in the low number of function evaluations regime. On image datasets, DCRS achieves up to a $10\times$ reduction in sampling steps compared to standard samplers while maintaining competitive sample quality, whereas on language benchmarks, we observe more nuanced behavior depending on the corruption process and sampling procedure.