MDM-VGB boosts masked diffusion with reward-guided remasking

Masked diffusion models (MDMs) are powerful for generative tasks, but they often struggle when outputs must satisfy structural constraints or optimize downstream rewards. Traditional test-time scaling methods like best-of-N sampling can be computationally prohibitive due to exponential complexity from error accumulation. In a new paper, Kijung Jeon, Thuy-Duong Vuong, and Molei Tao introduce MDM-VGB (Value-Guided Backtracking for Masked Diffusion), a sampler that integrates reward guidance directly into the generation process. Inspired by the Jerrum-Sinclair backtracking Markov chain, MDM-VGB extends the random walk from a fixed prefix tree to a masked-state graph. This allows tokens to be unmasked and remasked at arbitrary positions, with each move favoring higher-value partial configurations. The result is a sampler that can both generate high-reward samples from scratch and efficiently repair low-reward ones.

The theoretical contributions are significant: MDM-VGB is proven to have quadratic complexity in the number of tokens, a vast improvement over the exponential complexity of best-of-N. The authors also show robustness to noise from process verifiers. Empirically, MDM-VGB excels on constraint-satisfaction problems (e.g., Sudoku) and scientific benchmarks (e.g., QM9 for molecular generation), achieving higher reward satisfaction with far fewer sampling steps. This work opens the door to practical, efficient test-time scaling for discrete diffusion models, making them more viable for applications where structural fidelity and reward optimization are critical.