Random Remasking Scales Masked Diffusion Inference

The unified Markov-chain view and Proposition 2 are the strongest intellectual elements. By writing the transition as $\tilde{K}^{\theta}_t(\mathbf{x}'_0 \mid \mathbf{x}_0) = \sum_{\mathbf{x}_t} f_{\theta}(\mathbf{x}'_0 \mid \mathbf{x}_t) \, q_{t|0}(\mathbf{x}_t \mid \mathbf{x}_0)$, the authors expose that standard decoding and correction are instances of the same kernel. The bound $\KL(p_{data} \| p') \le \rho_t(p) \cdot \KL(p_{data} \| p) + \epsilon_t$ directly motivates the R2D schedule: the authors note it 'exposes three factors: Inference timestep schedule, task structure and model quality.' The early-exit mechanism is both principled—it approximates a fixed-point search at each noise level—and efficient, cutting NFE by roughly half relative to ReMDM on HumanEval+ while surpassing its accuracy.

The 'near-log-linear' scaling claim is largely restricted to synthetic logical tasks that the paper itself characterizes as having 'sparse, local constraints' where the denoising error $\epsilon_t$ is small. On the sole language benchmark (HumanEval+), the improvement over LLaDA2.1-mini's published Q-mode is modest (82.9% to 85.4%) and comes from only one model. Theoretically, Proposition 2's contraction ratio $\rho_t(p)$ depends on the unknown current chain distribution $p$, so the adaptive schedule is driven by a heuristic—Algorithm 1 declares convergence when '$\tau+1$ identical predictions in a row' occur—with no proven guarantee. Training is also brittle: ablations show that switching TCT's reveal policy from top-k confidence to random position selection drops Sudoku-Hard accuracy by 12 points, indicating that the headline numbers rely on careful, non-obvious training engineering.

On logical tasks, the comparisons to ReMDM and ProSeCo are fair and controlled: the authors note that 'R2D and ReMDM are evaluated with standard training checkpoints, while ProSeCo uses its own training method,' and all three use the same compute budget. The critique of prior theory—that 'Existing explanations, e.g., the ReMDM and the predictor-corrector framework only provide convergence analysis of the intermediate sequence marginal distribution under a pefect denoising model'—is consistent with ReMDM's own framing of its sampler as 'ancestral sampling in a probabilistic model whose ELBO is similar to that of classical masked diffusion' rather than as an analysis of trajectories under an imperfect learned denoiser. That said, the language-task evidence is thin: only HumanEval+ is reported, no reward-guided baselines are included, and the modest gain leaves open how R2D compares to other test-time scaling paradigms on general text.

The main text provides Algorithms 1 and 2 and detailed hyperparameters in Appendix E, but no public code repository is mentioned. Reproduction is complicated by the sensitivity of TCT to its trajectory design: as noted in the ablation, 'Position selection is the load-bearing choice: Revealing random positions costs 12.0 points.' The early-exit threshold $\tau$ and the per-level budget $M$ must be tuned per task (e.g., $M=256$ for Sudoku-Hard versus $M=32$ for 3-SAT), and full-budget inference is expensive: 'At the largest budget, R2D's per-sample latency is about 77\times that of standard decoding on the same checkpoint for Sudoku-Hard.' While early exit mitigates this, independent reproduction will require careful tuning and substantial compute.