MCMC-Guided Remasking for Discrete Diffusion: Bias-Controlled Parallel Inference

Masked diffusion models (MDMs) offer a promising alternative to autoregressive language models by enabling parallel token generation. Recent self-correction techniques, such as remasking, can improve generation quality, but their behavior under parallel token updates still remains poorly understood. In particular, the induced transition kernels can deviate from the desired sampling dynamics, undermining the motivation of diffusion-based generation. In this work, we introduce **BReSC** (**B**alanced **Re**masking with **S**taleness **C**ontrol), a training-free remasking sampler grounded in a principled Markov chain Monte Carlo (MCMC) viewpoint. We identify two fundamental biases in parallel remasking: drift bias caused by unbalanced transitions, and a staleness bias caused by simultaneously updating coupled tokens from stale contexts. BReSC addresses these biases through an entropy-balanced remasking policy satisfying coordinate-wise detailed balance, together with an online optimization routine that reduces staleness proxy by suppressing high-interference parallel updates. We theoretically characterize both biases under idealized assumptions, guiding the design of our practical sampler. We benchmark BReSC on OpenWebText unconditional generation and downstream LLaDA tasks against existing baselines.