acceptodds
Under review as a conference paper at ICLR 2027

MCMC-Guided Remasking for Discrete Diffusion: Bias-Controlled Parallel Inference

Abstract

Masked diffusion models (MDMs) offer a promising alternative to autoregressive language models by enabling parallel token generation. Recent self-correction techniques, such as remasking, can improve generation quality, but their behavior under parallel token updates still remains poorly understood. In particular, the induced transition kernels can deviate from the desired sampling dynamics, undermining the motivation of diffusion-based generation. In this work, we introduce **BReSC** (**B**alanced **Re**masking with **S**taleness **C**ontrol), a training-free remasking sampler grounded in a principled Markov chain Monte Carlo (MCMC) viewpoint. We identify two fundamental biases in parallel remasking: drift bias caused by unbalanced transitions, and a staleness bias caused by simultaneously updating coupled tokens from stale contexts. BReSC addresses these biases through an entropy-balanced remasking policy satisfying coordinate-wise detailed balance, together with an online optimization routine that reduces staleness proxy by suppressing high-interference parallel updates. We theoretically characterize both biases under idealized assumptions, guiding the design of our practical sampler. We benchmark BReSC on OpenWebText unconditional generation and downstream LLaDA tasks against existing baselines.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
discrete diffusion language models, masked diffusion models, MCMC, parallel sampling, remasking, online optimization, bias reduction

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_h22tOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In masked diffusion models, remasking can help bypass the "locked-in" problem and potentially improve generation performance. The paper identifies two biases in parallel remasking: drift bias and staleness bias. They proposed a training-free method BReSC to address these biases: the method uses an entropy-balanced remasking policy with coordinate-wise detailed balance, also an online optimization routine by avoiding high-interference parallel updates. A theoretical justification is presented, and BReSC is empirically shown to surpass baselines in many benchmarks.

Critical strengths
  1. The theoretical derivations look correct to me. On many settings, the method outperforms a strong baseline ReMDM. The method may serve as a strong inference-time remasking strategy.
Critical weaknesses
  1. The theoretical guarantee is limited. Detailed balance assumes frozen entropy estimates, but in practice the sampler refreshes them dynamically.
Questions for authors
  1. The dependency-aware controller seems to contribute a substantial fraction of the reported improvements. This impact may be larger than the contribution of entropy-balanced remasking. Could the authors provide a controlled 2×2 ablation comparing uniform and entropy-balanced policies, with and without the staleness controller, across matched decoding budgets?
  2. The authors may consider refining the presentation of figure 1.
3 comments

We sincerely thank the reviewer for the assessment and for the suggestions on the ablation and presentation. New material is highlighted in red in the revised PDF.

W1: Limited theoretical guarantee.

A: Theorem 1 in fact gives BReSC the local guarantee it needs for practical inference. As discussed in Inference-time Adaptation (Section 3.2), Theorem 1 holds entropy fixed, while BReSC refreshes it as generation progresses. This is a practical adjustment for inference time. Empirical work on LLM inference has shown that generation can benefit from tilting the model’s sampling distribution using information available during decoding [1,2]. Our contribution is to use entropy to express these preferences and still satisfy detailed balance. As more tokens are revealed or revised, the preferred target can change. BReSC refreshes its entropy estimates so the target can adaptively capture the evolving inference preference.

Therefore, Theorem 1 can be understood as the local guarantee BReSC needs in practice. It tells us how to balance the moves for the target we prefer at the current stage of inference. When BReSC refreshes entropy, the same construction gives balanced moves for the new target. The full inference trajectory can thus follow a changing target, with Theorem 1 providing a principled MCMC design rule at each stage. Importantly, our experiments support the value of this adaptive design in practice. We believe this shows how principled MCMC can guide adaptive sampling in practice in a setting where effective decoding rules are still poorly understood.

Q1: Uniform/entropy × controller-off/on ablation.

A: Thank you for the suggestion! Following your request, we compared three policies on OWT at T=128T = 128. BReSC (EE) uses entropy for remasking and decoding. EU uses entropy for remasking and uniform decoding. UU uses uniform rates for both. EE satisfies detailed balance for the entropy-tilted target. EU and UU both break detailed balance. We tested each policy with and without the controller.

PolicyController off (MAUVE ↑ / PPL ↓)Controller on (MAUVE ↑ / PPL ↓)
EE (BReSC)0.119 / 29.20.150 / 28.9
EU0.120 / 29.50.110 / 29.2
UU0.026 / 54.90.026 / 55.6

Overall, the balanced policy (EE) performs better than the others, and the controller is specifically useful for BReSC (EE). With EE, the controller raises MAUVE from 0.119 to 0.150 and lowers PPL from 29.2 to 28.9. The results are added in Appendix E.1.1.

The controller's benefit is less clear with EU and UU, but this is consistent with how the two components work together. The entropy-balanced policy and the staleness controller are tightly coupled. Theorem 1 gives us a drift-free sequential reference for Theorem 2. Theorem 2 bounds the extra error from using cached predictions, and its interaction terms guide which tokens the controller updates together. With EU and UU, even fresh sequential updates can drift from the target. Staleness control alone leaves that drift in place. These results show the practical value of our theory.

Q2: Refine Figure 1 presentation.

A: We have redrawn Figure 1 as vector artwork, with clearer labels and more consistent typography and layout. See Figure 1 in the revised PDF.

Thank you again for your suggestions. We hope the clarification of Theorem 1’s role during inference and the new ablations address your main concerns. We would appreciate it if you reconsidered your assessment in light of these additions.

[1] The Curious Case of Neural Text Degeneration. ICLR 2020.
[2] Locally Typical Sampling. TACL 2023.

I thank the authors for their insightful rebuttal. My concerns are mostly addressed, so I will raise my score to 3.

Thank you so much for your thoughtful engagement and for raising the score! We’re glad we could address your concerns, and we appreciate your feedback, which definitely helped us improve the paper!

Reviewer_BiohOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper adopts an MCMC perspective on remasking in masked diffusion models and proposes BReSC, a training-free sampler. It distinguishes two sources of sampling bias: imbalance between remasking and decoding transitions, and parallel updates that rely on stale context. The method combines entropy-balanced transition probabilities with a controller that discourages strongly interacting tokens from changing together. The analysis establishes target preservation for an idealized sequential sampler and derives a discrepancy bound to motivate the controller. Experiments on OpenWebText and several LLaDA downstream tasks report improvements in generation quality and task performance, along with fewer sampling steps needed to reach comparable MAUVE.

Critical strengths

1/ The MCMC formulation provides a useful way to reason about remasking. By separating imbalance in local transitions from interference between parallel updates, it clarifies two distinct problems that a sampler needs to address. The balanced construction also provides a concrete design principle, with a clear guarantee under its stated assumptions (§2–3).

2/ The unconditional-generation improvements are substantial. Without additional training, BReSC achieves MAUVE 0.451 at 256 steps, compared with ReMDM's 0.403 at 1,024 steps. The controller comparison and the entropy-weighted decoding ablation also provide evidence that both components contribute to the quality improvements (Tables 1 and 6). These results are the strongest argument for acceptance.

Critical weaknesses

1/ The methodological advance is limited, and the most distinctive component remains insufficiently validated. The entropy-balanced rates are a relatively direct application of detailed balance to the existing correction loop. The controller is more distinctive, but the staleness bound concerns independent parallel updates, while the implementation uses correlated, approximately calibrated updates. Appendix C.4 explicitly limits the optimization guarantee to a proxy cost, and no numerical marginal-calibration errors or direct measurements of sampling bias are reported. I am therefore not convinced that the quality gains establish the claimed bias-control mechanism.

2/ The downstream evaluation does not adequately separate sampler improvements from tuning advantages. Appendix D.2 states that BReSC's hyperparameters were selected using benchmark-specific evaluations without held-out selection, whereas ReMDM uses settings adopted from prior work. HumanEval and GSM8K are also reported as point estimates without uncertainty estimates. While the sensitivity results are helpful, they do not resolve whether the gains persist under comparable tuning budgets and independent evaluation. This matters particularly for the smaller improvements on GSM8K and TruthfulQA.

3/ Not critical weakness, but Firgure 1 resolution is bad, this is not professional.

Questions for authors

1/ Which downstream results use the full staleness controller, and how does the fixed-k remasking procedure in Appendix D.2 correspond to the balanced transition probabilities in Eq. (13)?

2/ What speedup is obtained from directly measuring runtime at matched MAUVE, including controller overhead? Appendix E.1.2 derives the reported 2.7× speedup by extrapolating from separate step-count and timing measurements?

5 comments
AuthorsOpenReview ↗

Response to Reviewer Bioh (Part 1/2)

We sincerely thank the reviewer for recognizing the MCMC perspective and the unconditional-generation results. We address the issues raised below. New material is highlighted in red in the revised PDF.

W1: Methodological contribution and validation of the staleness controller.

A: We first emphasize that the entropy-balanced policy is also a major methodological advance in its own right. To our knowledge, BReSC is the first method for diffusion LLMs to use an entropy-based policy that satisfies detailed balance. In Section 4, even without the controller, BReSC wins over ReMDM by a significant margin for both MAUVE and PPL, showing that the policy makes a substantial difference on its own.

Most existing methods use confidence-based rules without an MCMC design and generally fail to satisfy detailed balance. Finding a balanced kernel that also adapts as the context changes during inference is highly nontrivial. We tried several approaches, including local Metropolis–Hastings, and found that those other balanced approaches can be very conservative at inference time, with poor generation quality. The entropy policy is principled and captures the information required for better inference.

Furthermore, the balanced policy and the staleness controller are tightly coupled. Theorem 1 gives us a drift-free sequential reference for Theorem 2. Theorem 2 bounds the extra error from using cached predictions, and its interaction terms guide which tokens the controller updates together. Without detailed balance, even fresh sequential updates can drift from the target. Staleness control alone leaves that drift in place. Our newly added results in Appendix E.1.1 show that an unbalanced policy may not benefit from the staleness controller, while BReSC combines the two effectively. See also our response to Reviewer h22t. Making detailed balance work in a practical diffusion LLM is therefore an important part of the method.

We agree that the controller uses a proxy and that more validation would help. We added new experiments to test whether the proxy helps the controller choose which tokens to update together. On 36 saved OpenWebText contexts, we compared the controller with independent updates that changed each token equally often on average. We scored the same update choices using the proxy weights and, on selected pairs, using weights measured with extra denoiser calls.

Weights used to score simultaneous updatesCost reduction95% interval
Proxy weights used at inference, all pairs22.44%[19.29%, 25.36%]
Weights measured with extra calls, selected pairs3.34%[0.85%, 5.81%]

The proxy helped the controller reduce the cost of updating interacting tokens together. The reduction held on the selected pairs when we measured their interactions with extra model calls. The new results are included in Appendix C.5.

Following the reviewer's suggestion, we also measured how closely the controller follows the requested update probabilities (calibration errors). Directly measuring sampling bias on OWT is impractical because we lack a tractable reference distribution over complete sequences. We therefore checked on OWT whether the controller follows the requested update probabilities and reduces interference between tokens updated together. On 54 saved OpenWebText contexts, we replayed the controller 256 times per context and compared how often each token changed with its requested probability.

Saved contextsMean absolute error (percentage points)Mean extra updates vs. requested count
Middle and late steps (36)2.11+6.89%
All steps (54)4.51+15.53%

In the middle and late stages, the update probabilities were off by just 2.11 percentage points per token on average. On those same contexts, the original proxy weights lowered this error by 0.49 percentage points compared with shuffled weights.

AuthorsOpenReview ↗

Response to Reviewer Bioh (Part 2/2)

W2: Tuning advantages and uncertainty.

A: As the reviewer notes, the sensitivity analysis in Appendix D.2 shows that BReSC is stable across nearby settings. We agree that additional controlled comparisons can better separate sampler improvements from tuning effort. For HumanEval and GSM8K, we followed the LLaDA evaluation protocol in [1] and used temperature 0, and therefore decoding is deterministic. We report additional controlled comparisons below.

We first compared the two samplers at the same kk, using the same prompts and scorer.

Benchmark and metricMatched kReMDMBReSCDifference
HumanEval pass@1139.63%46.34%+6.71 pp
GSM8K flexible match379.45%80.44%+0.99 pp
GSM8K strict match339.88%48.60%+8.72 pp
TruthfulQA ΔROUGE-1/2/L628.569 / 30.151 / 28.72929.115 / 31.620 / 29.242+0.546 / +1.470 / +0.512

BReSC scores higher across all three benchmarks at matched kk. The clearest gains are 6.71 percentage points on HumanEval and 8.72 points on GSM8K under strict matching.

To further validate on GSM8K, we selected from three settings per method on the same 128 questions and evaluated on 512 separate questions. We also tested the original settings, fixed in advance, on another 512 questions. Both comparisons used questions from the training split.

GSM8K evaluationReMDM flexibleBReSC flexibleReMDM strictBReSC strict
Equal tuning budget80.86%79.69%28.13%32.03%
Original settings, fixed in advance81.05%81.84%27.54%36.72%

With the original settings fixed in advance, BReSC gained 9.18 points on strict matching. Under equal tuning, flexible-match scores were close, and BReSC scored higher on strict matching.

W3: Improve Figure 1 resolution.

A: We have redrawn Figure 1 as vector artwork, with clearer labels and more consistent typography and layout. See Figure 1 in the revised PDF.

Q1: Downstream controller usage and correspondence to Eq. (13).

A: We did not use the full staleness controller on downstream tasks. There are only a few updates to coordinate per step, with kk ranging from 1 to 6. At these small values of kk, optimizing which tokens to update together adds overhead with little room to improve coordination. The controller is a better fit for OWT because it can choose among up to 1,024 positions. The downstream experiments show the practical benefit of the entropy-based policy. The fixed-kk rule follows the same preferences as Eq. (13): remask higher-entropy tokens and decode lower-entropy positions. It implements those preferences by ranking positions.

Q2: Direct runtime comparison.

A: Thank you for raising this. The original 2.7× figure was indeed an extrapolation. We measured ReMDM at T=1024T = 1024 and optimized BReSC at T=256T = 256 in separate runs on the same NVIDIA A100 40 GB. The timings include controller overhead.

MethodMAUVE ↑PPL ↓Seconds per sample ↓
ReMDM (T=1024T = 1024)0.40328.615.7411
BReSC (T=256T = 256)0.4096319.71936.6149

The last column shows that BReSC is 2.38× faster at comparable MAUVE. This is lower than the extrapolated estimate and still cuts generation time by more than half. We updated the wall-clock speedup in the Introduction, Section 4.1, and Figure 2. Appendix E.1.2 gives the full details, and Table 9 in Appendix E.1.2 reports the separate comparison at the same step budget.

Thank you again for the detailed feedback. We hope the new controller measurements, downstream comparisons, and direct timings address your main concerns. We would appreciate it if you reconsidered your assessment in light of these results.

[1] Learn from Your Mistakes: Self-Correcting Masked Diffusion Models. NeurIPS 2026.

Thank you for your replies.

W1: Regarding your replies "entropy-balanced policy", from the paper, I do not see any analysis of the entropy or uncertainty from experiment, all results are final performance like ppl and etc., while I agree that the algorithm could make it more balanced, then the followup question is why I have to pay this much attention to carefully balance the intermediate entropies, what are the benefits? like a perfect llm diffusion model should have intermediate states all balanced or sth? is this what you claimed ? I saw you mentioned "Without detailed balance, even fresh sequential updates can drift from the target", just want to learn more here, my current understanding is balance--->less drift--->XXX--->better diffusion llm performance, I did not get what XXX should be, correct me if I miss anything, thank you.

Another question is too few baselines, I feel there should be more remasking strategies to compare in Table1, currently only 2 training free methods are compared?

Reviewer_QAZWOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes BReSC, a training-free remasking sampler for masked diffusion language models. The authors identify two problems with current remasking-based techniques for diffusion LMs: Drift bias where the diffusion sampler drifts away from the target distribution if the detailed balance between remasking and filling it back in is violated. The second problem is Staleness bias where coupled tokens are simultaneously updated independently which leads to incoherent generations. The method is training-free and applies to large scale diffusion language models like Llada-8b.

Critical strengths

The paper is very well written. I don't have a lot of expertise in diffusion-based language models, but I was able to follow the core motivation and idea behind the proposed method. I think there is a clear need for principled training-free methods for diffusion language models, and the paper fills that gap. Moreover, the proposed techniques clearly scale to large-scale models like Llada-8b and therefore have utility.

Critical weaknesses

I have no major concerns regarding the paper. The paper falls outside my expertise, as I don't work on diffusion language models. I hope my comments can still be useful to the authors:

  1. The only baseline in Tables 1 and 2 that is compared against is ReMDM. I do see some additional baselines in Table 10 in the Appendix, but these have not been tuned. From a quick search, I was able to find 2-3 additional training-free baselines that the authors can compare against to make the results stronger (some of these are cited but not compared against in the paper) [1,2,3,4].

  2. Can the authors clarify in the main text under what conditions the proposed sampling algorithm (used in practice) differs from the underlying theory? At some places, the presentation is quite dense, so it's difficult to understand the gap between theory and practice.

[1] Saber: An Efficient Sampling with Adaptive Acceleration and Backtracking Enhanced Remasking for Diffusion Language Model, Dong et al. (2025)

[2] WINO: Wide-In, Narrow-Out: Revokable Decoding for Efficient and Effective DLLMs, Hong et al. (2025)

[3] CORE: Context-Robust Remasking for Diffusion Language Models, Zhai et al. (2026)

[4] P2: Path Planning for Masked Diffusion Model Sampling, Peng et al. (2025)

Questions for authors

See weaknesses

3 comments

Thank you so much for the encouraging review and for pointing us to these baselines! Your suggestions helped us sharpen the comparison and explain how the theory guides the sampler. New material is highlighted in red in the revised PDF.

W1. Additional training-free baselines

A: We originally chose only ReMDM [1] because it uses the same remasking loop we study and was arguably the strongest training-free dLLM baseline at submission. We evaluated the four baselines you suggested [2-5] on HumanEval using the same LLaDA-8B-Instruct checkpoint, 164 zero-shot prompts, 256-token generation limit, 32-token blocks, and pass@1 scorer as BReSC. We adapted P2-Self to plan within each 32-token block.

MethodHumanEval pass@1 (%)
SABER37.80
WINO36.59
CoRe24.39
P2-Self39.02
ReMDM39.63
BReSC46.34

BReSC scored 7.32 percentage points above P2-Self, the strongest of the four suggested remasking baselines. We added these results in Appendix E.2.1 of the revised PDF.

We will also add the GSM8K comparison once those runs finish.

W2. Difference between the practical algorithm and theory

A: We have in fact discussed these gaps in remarks after the two theorems, in Inference-time Adaptation (Section 3.2) and Online Proxy of AijA_{ij} (Section 3.3.1), but we acknowledge that the wording could be clearer.

The first gap is that Theorem 1 holds entropy fixed, while BReSC refreshes it as generation progresses. This is a practical adjustment for inference time. Empirical work on LLM inference has shown that generation can benefit from tilting the model’s sampling distribution using information available during decoding [6,7]. Our contribution is to use entropy to express these preferences and still satisfy detailed balance. In practice, BReSC refreshes its entropy estimates so that the target can adaptively capture the evolving inference preference.

Theorem 1 thus gives a guarantee locally. BReSC intends to maintain balance according to the entropy information preferred at the current stage of inference. When BReSC refreshes entropy, the same construction gives balanced moves for the new target. The full inference process can thus follow a changing target, with Theorem 1 providing a principled MCMC design rule at each stage. Importantly, our experiments support the value of this adaptive design in practice.

The second gap is that BReSC uses a proxy for the interactions in Theorem 2. Computing every interaction from Theorem 2 directly would be computationally prohibitive at inference time, so we use a first-order Fourier approximation (Section 3.3.1) for computational efficiency, which is a standard technique in practical approximation. This proxy only uses model calls already made during sampling, so it's cheap.

To show that the proxy is effective in practice, we added new experiments in Appendix C.5. On 36 saved OWT contexts, we compared the controller with independent updates that changed each token equally often on average. We scored how often strongly interacting tokens changed together, first using the proxy weights and then using weights measured with extra denoiser calls.

Weights used to score simultaneous updatesCost reduction
Proxy weights used at inference, all pairs22.44%
Weights measured with extra calls, selected pairs3.34%

The cost reductions show that the proxy indeed helped the controller choose updates with less measured interference, supporting its use in practice.

We also modified accordingly in lines 324–328 and 369–371.

[1] Remasking Discrete Diffusion Models with Inference-Time Scaling. NeurIPS 2025.
[2] Saber: Efficient Sampling with Adaptive Acceleration and Backtracking Enhanced Remasking for Diffusion Language Model in Code Generation. ACL 2026.
[3] Wide-In, Narrow-Out: Revokable Decoding for Efficient and Effective DLLMs. ICLR 2026.
[4] CORE: Context-Robust Remasking for Diffusion Language Models. ICML 2026.
[5] Path Planning for Masked Diffusion Model Sampling. arXiv 2025.
[6] The Curious Case of Neural Text Degeneration. ICLR 2020.
[7] Locally Typical Sampling. TACL 2023.

AuthorsOpenReview ↗

Follow-up on GSM8K

Following up on W1, we report the GSM8K comparison with the four suggested baselines. We added the results to Appendix E.2.1 of the revised PDF. We used the same LLaDA-8B-Instruct checkpoint, 1,319 five-shot test prompts, 256-token generation limit, and 32-token blocks for all methods.

MethodGSM8K flexible (%)GSM8K strict (%)
SABER77.6339.80
WINO75.2143.21
CoRe74.1543.90
P2-Self77.9440.64
ReMDM79.4539.88
BReSC80.4448.60

BReSC scored highest under both scoring protocols. In particular, BReSC leads P2-Self by 2.50 points on flexible matching and CoRe by 4.70 points on strict matching.

Reviewer_QAZWOpenReview ↗

Reviewer Response

Thanks for your response. I will maintain my rating.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Thank You and a Brief Summary of Our Rebuttal

Dear Area Chair and Reviewers,

We would like to sincerely thank you all for the time and care you put into reviewing our paper. We really appreciated the discussion, and your comments greatly helped us strengthen the work. We’d like to briefly share what we added.

  • Additional training-free baselines. As suggested by QAZW and Bioh, we broadened the OWT comparison and evaluated six additional training-free samplers on HumanEval and GSM8K. BReSC performed best on every metric in the expanded baseline tables.
  • Concrete validation of BReSC’s components. Following Bioh’s and h22t’s suggestions, we added ablations, compared samplers under fair tuning budgets, and verified that the staleness proxy indeed helps choose which tokens to update together. We also measured a 2.38× wall-clock speedup over ReMDM. To answer Bioh’s follow-up on what balance adds in practice, our new OWT experiments showed that BReSC can use the model’s uncertainty to guide decoding and still keep plausible alternatives in play.
  • Practical value of our theory. In response to QAZW and h22t, we clarified how our theory guides BReSC’s adaptive updates specifically at inference time. We appreciate both reviewers' acknowledgement of our replies.

We hope our responses and new experiments have addressed your concerns. Thank you again for helping us improve the paper!

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.