Paper Overview
Field: Machine Learning Authors: Kijung Jeon, Thuy-Duong Vuong, Molei Tao Published: 2026-06-26 arXiv: 2606.28301
Abstract
Inference-time scaling is a promising paradigm to improve generative models, especially when outputs must satisfy structural constraints or optimize downstream rewards. We consider Masked Diffusion Model (MDM) and introduce MDM-VGB, a discrete diffusion sampler that augments unmasking generation with theoretically principled reward-guided remasking.
Inspired by the recent success of the classical Jerrum-Sinclair backtracking Markov chain in reward-tilted generation, MDM-VGB extends the backtracking random walk from a fixed prefix tree to a masked-state graph, allowing tokens to be unmasked and remasked at arbitrary positions. The resulting sampler favors unmasking and remasking moves that lead to higher-value partial configurations, enabling both effective high-reward generation and efficient repair of low-reward samples.
Key Contributions
- Reward-guided remasking: Extends the Jerrum-Sinclair backtracking random walk from a fixed prefix tree to a masked-state graph, permitting unmasking and remasking at arbitrary token positions.
- Robustness: MDM-VGB is provably robust to noise in process verifiers.
- Efficiency: The method achieves quadratic complexity, whereas popular test-time heuristics such as best-of-N can suffer exponential complexity due to error accumulation.
- Empirical validation: Strong experimental performance, particularly on Sudoku and QM9 benchmarks.