Abstract: Discrete diffusion models achieve strong performance in text and image generation, but inference remains slow
and requires balancing sampling efficiency with sample quality. We systematically study how the degree of
stochasticity in Markov transitions governs this tradeoff, finding that deterministic transitions converge quickly but
accumulate errors, while stochastic transitions converge more slowly but can achieve better final sample quality.
Through an information-theoretic analysis, we show that redundant transitions that symmetrically exchange
probability mass between states can contract sampling errors, providing an error-correcting effect. Motivated by
this insight, we introduce Discrete Churn and Restart Sampling (DCRS), which injects controlled stochasticity by
alternating between forward and reverse diffusion. Across synthetic, image, and language benchmarks, DCRS
improves the speed-quality tradeoff at low numbers of function evaluations, achieving up to a 10× reduction in
image sampling steps while revealing more nuanced behavior for language generation.

Bio: William Yuan is a Ph.D. student in Electrical and Computer Engineering at the Georgia Institute of Technology,
advised by Prof. Amirali Aghazadeh. His research focuses on developing methods to accelerate the inference in
deep generative models. He received his B.S. from Cornell University.