Walk fast but be careful: Understanding Parallel Sampling in Masked Diffusion
Graph random walks are used as a test to study parallel sampling methods in masked diffusion models. The research found that bisection-style samplers, which use Markov separators, significantly improve speed and quality compared to other parallel strategies by achieving logarithmic depth. This shows that the graph's structure is more important than local uncertainty scores for successful decoding.