Understanding Parallel Samplers in Masked Diffusion via Random Walks on Graphs

This paper introduces a framework for analyzing parallel sampling strategies in masked diffusion models (MDMs) using random walks on graphs as a controlled environment. It theoretically demonstrates that the effectiveness of parallel unmasking methods, such as those based on lowest entropy scores, is highly dependent on the graph structure, and presents a new bisection sampler that operates in logarithmic time with provable accuracy under optimal training conditions. The findings highlight the potential of graph random walks as a benchmark for evaluating and optimizing sampling methods in MDMs, which could enhance the speed and quality of language generation tasks.