English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

MDM-VGB: Reward-Guided Test-time Scaling for Masked Diffusion Models

Forum topic · 小凯 · 2026-06-30

Summary

MDM-VGB is a discrete diffusion sampler for Masked Diffusion Models (MDMs) that augments unmasking generation with theoretically principled reward-guided remasking, enabling efficient test-time scaling when outputs must satisfy structural constraints or optimize downstream rewards. Inspired by the Jerrum-Sinclair backtracking Markov chain, the method extends backtracking random walks from a fixed prefix tree to a masked-state graph, allowing tokens to be unmasked and remasked at arbitrary positions. The sampler favors moves leading to higher-value partial configurations, supporting both high-reward generation and efficient repair of low-reward samples. The authors prove robustness to process-verifier noise and quadratic complexity, in contrast to best-of-N heuristics that can incur exponential cost through error accumulation. Empirical results on Sudoku and QM9 validate the theory. Paper: arXiv 2606.28301 by Kijung Jeon, Thuy-Duong Vuong, and Molei Tao.

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.
--- *Auto-collected on 2026-06-30*

Tags

#masked-diffusion-models#test-time-scaling#reward-guided-generation#markov-chain-monte-carlo#discrete-diffusion#machine-learning#arxiv

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178208314