TL;DR
This paper introduces Random Remask-Denoise ($R^2D$) and Trajectory Correction Training (TCT), a framework that enables Masked Diffusion Models (MDMs) to fix their own mistakes during inference. By treating decoding as a Markov chain on the clean sequence space, the authors achieve near-log-linear test-time scaling, reaching over 97% accuracy on hard Sudoku puzzles and surpassing state-of-the-art results on coding benchmarks.
What Problem Does This Paper Address?
Masked Diffusion Models (MDMs) generate data by starting with a fully masked sequence and progressively "filling in the blanks." A major flaw in standard MDM decoding is that once a token is unmasked, it is usually frozen. If the model makes a mistake early in the trajectory, that error propagates and ruins the final output.
While researchers have tried "iterative correction" (re-masking and re-predicting), there hasn't been a strong theoretical explanation for why it works when the model itself is imperfect. Furthermore, we lack a principled way to "scale" compute at test-time—essentially, how can we spend more time "thinking" or "refining" to get a better answer?
Methods
The authors propose two main contributions:
- Random Remask-Denoise ($R^2D$) Inference: This is a training-free inference algorithm. Instead of a one-way path from masks to tokens, $R^2D$ treats inference as a Markov chain. At each step, it randomly re-masks a portion of the sequence and asks the model to re-denoise it. Crucially, it uses an adaptive timestep schedule: the model keeps iterating at a specific noise level until its predictions stabilize before moving to a lower noise level.
- Trajectory Correction Training (TCT): While $R^2D$ works on off-the-shelf models, TCT makes them even better. Standard training teaches models to fill masks in perfect data. TCT instead trains the model on its own imperfect intermediate generation steps, teaching it to recognize and override its own previous mistakes.
Datasets
The authors evaluated their methods on three challenging domains:
- Sudoku-Hard: 2.3 million puzzles from the Sudoku-Extreme dataset, filtered for high difficulty (rating > 10).
- 3-SAT: A synthetic dataset of 1 million 3-SAT instances (logical satisfiability problems).
- HumanEval+: A rigorous version of the standard HumanEval coding benchmark, used to test the method on large-scale pretrained language models like LLaDA2.1-mini.
Key Insights and Ideas
- The Markov Chain View: By viewing MDM inference as a transition between "clean" sequences rather than a progression of masking ratios, the authors derived a single-step update bound. This bound shows that "contraction" (moving closer to the true data distribution) depends on the noise level and model quality.
- Randomness is a Feature, Not a Bug: Surprisingly, re-masking tokens uniformly at random is more effective for scaling than re-masking "low-confidence" tokens. Random re-masking prevents the model from getting stuck in local minima and allows it to better exploit local constraints (like the rules of Sudoku).
- Test-Time Scaling: The approach exhibits "near-log-linear" scaling. This means that as you increase the number of correction steps (compute budget), the accuracy improves predictably and significantly.
- Early Exit Efficiency: Unlike other iterative methods that use a fixed budget, $R^2D$ can stop early once the prediction stabilizes. This makes it much more compute-efficient than baselines like ReMDM.
Key Results
The results demonstrate that $R^2D$ and TCT turn MDMs into powerful reasoners:
- Logical Tasks: On Sudoku-Hard, accuracy jumped from a baseline of 48.7% to a staggering 97.5% using $R^2D$ and TCT. On 3-SAT, accuracy reached 99.3%.
- Test-Time Scaling: As shown in Figure 1, $R^2D$ scales much better than previous methods like ProSeCo, which tends to plateau quickly.
- Coding Performance: Applied to the off-the-shelf LLaDA2.1-mini (16B) model, $R^2D$ achieved 85.4% on HumanEval+, surpassing the model's official "Q-mode" performance of 82.9% and other iterative baselines.
Limitations and Future Work
The authors note that the effectiveness of random re-masking is tied to the "token coupling" nature of the task. It works exceptionally well for tasks with local constraints (like Sudoku or SAT), where a few revealed tokens can "force" the value of others.
Future work could explore how these methods apply to domains with more global or diffuse dependencies, such as biological sequence design (e.g., proteins) or long-form creative writing. Additionally, while $R^2D$ is more efficient than other iterative methods, it still requires significantly more compute than a single-pass standard decode.
Summary updated