Random Remasking Scales Masked Diffusion Inference

Zhaoyi Zhou, Frank Wu, Andrea ZanettearXiv 2026 · arXiv

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:

  1. 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.
  2. 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.
Figure 1: Inference scaling on Sudoku-Hard and 3-SAT. R2D and ReMDM are run on standard training checkpoints, both using the standard variant; ProSeCo has its own training method. R2D scales near-log-linearly on both tasks and stays above ReMDM at every budget, whereas ProSeCo plateaus after a handful of correction steps.
  • 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.
Figure 2: HumanEval+ accuracy with the off-the- shelf LLaDA2.1-mini (16B). The three colored bars are inference methods we run ourselves, and the two grey bars are the model’s own published Q-mode and S-mode results. R2D achieves the top accuracy, surpassing the official Q-mode perfor- mance.

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

Abstract

Masked diffusion models (MDMs) generate sequences by progressively unmasking tokens, but errors introduced during decoding are typically irreversible. Recent work has shown that iterative correction can improve sample quality, yet existing theory fails to explain this given a learned, imperfect denoiser model. We re-formulate MDM inference as a Markov chain on the clean sequence space, defined by a remask-denoise kernel that randomly re-introduces masks and then denoises. This helps us analyze the actual denoising trajectory towards the data distribution. The analysis motivates Random Remask-Denoise (R$^2$D) inference, a purely test-time, finetuning-free, reward-free procedure. To further improve performance, we propose Trajectory Correction Training (TCT), a denoiser-training procedure that exposes the model to its own errors along the generation trajectory. On logical tasks, our approach exhibits a striking near-log-linear test-time scaling, achieving over 97% accuracy on hard Sudoku puzzles and over 99% accuracy on 3-SAT. Our approach also applies to pretrained models on actual language tasks, beating iterative correction baselines and the official Q-mode accuracy of LLaDA2.1-mini on HumanEval+.
BibTeX
@misc{zhou2026random,
  author = {Zhaoyi Zhou and Frank Wu and Andrea Zanette},
  title = {{Random Remasking Scales Masked Diffusion Inference}},
  year = {2026},
  eprint = {2610.30744},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30744},
}
Figure