acceptodds
Under review as a conference paper at ICLR 2027

Unmasking Nondeterminism in Masked Diffusion Language Models

Abstract

Greedy decoding of masked diffusion language models (MDLMs) is nominally deterministic, yet the same prompt can yield different outputs when only the batch size or the GPU changes, while accuracy barely moves and so hides the problem. In autoregressive models, the first differing token permanently separates two generations, but MDLMs also decide at every step where to write, and how nondeterminism develops under this second decision is not understood. Tracking the partially decoded response over 512 steps for LLaDA and Dream, we find that forks arise mainly from the position decision. These forks are often transient: on LLaDA, 92.6% of prompts return to an identical intermediate response, and the token conflicts that make a difference permanent appear much later. Treating the two decisions separately, we freeze the position order under periodic LayerCast refresh and recheck only tokens within a few ULPs of a tie, cutting LLaDA's MATH500 output divergence from 69.2% to 1.0% at less than half the cost of LayerCast, and most of Dream's. Freezing changes the decoding rule, however, so the recipe's outputs agree with each other but often not with LayerCast's, and accuracy can shift. Reproducible MDLM evaluation should therefore track states beyond the first fork and report agreement across executions and accuracy separately. More broadly, locating where nondeterminism enters the decoding rule lets a remedy target the fragile decision instead of paying for full precision.

Primary area:
foundation or frontier models, including LLMs
Keywords:
diffusion language models, nondeterminism, reproducibility, trajectory analysis, mixed-precision inference, selective verification

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_pTKyOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies numerical nondeterminism in greedy masked diffusion decoding. It distinguishes position-selection and token-selection forks, tracks subsequent state reunions and irreversible conflicts, and proposes periodic high-precision ranking with frozen reveal orders and selective token verification.

Critical strengths
  1. The trajectory analysis provides a meaningful advance beyond final-output disagreement statistics. Distinguishing temporary position-order differences from irreversible token conflicts explains why the first fork alone is an inadequate measure of reproducibility.
  2. The experiments cover multiple execution conditions and separately report agreement, accuracy, and computational cost. The disclosure that freezing changes outputs and can reduce accuracy makes the method’s trade-offs clear.
Critical weaknesses
  1. The mitigation’s components are not sufficiently disentangled. Periodic refresh simultaneously introduces high-precision ranking and freezes the reveal order. Without a matched low-precision-ranking-plus-freezing baseline, the experiments cannot determine how much improvement comes from precision rather than fewer opportunities to reorder positions.
  2. The practical quality–cost trade-off and scope remain uncertain. The method changes the decoder: only 61 of the 495 mutually consistent LLaDA outputs match LayerCast, and Dream’s MATH500 accuracy decreases from 43.8% to 40.0%. Its cost remains above BF16, while mitigation results focus on one-token-per-step decoding. Residual disagreement also makes “guarantees agreement” an overstatement.
Questions for authors
  1. Does low-precision ranking with identical frozen windows achieve comparable agreement, accuracy, and latency?
  2. Can the mitigation retain its benefits under parallel and block-wise decoding?
  3. Is there a configuration that substantially reduces disagreement without the observed accuracy loss, and what additional cost does it incur?
  4. What causes the residual token-mismatch forks in Table 11, and how are they reconciled with §6.2’s attribution of remaining disagreement to position forks?
Reviewer_LpSSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates nondeterminism in greedy decoding of Masked Diffusion Language Models (MDLMs), where outputs can change across batch sizes or GPUs despite identical prompts. The authors find that initial decoding divergence predominantly arises from unmasking position selection rather than token selection, and that such divergence can be transient. Based on these findings, they propose periodically freezing the unmasking order using LayerCast and selectively verifying near-tied token predictions at higher precision, substantially improving output reproducibility at a lower cost than full LayerCast inference.

Critical strengths

Important practical problem

The paper addresses a meaningful reproducibility issue in MDLM inference that can be obscured by nearly unchanged aggregate accuracy.

Insightful trajectory analysis

Distinguishing position mismatches, token mismatches, and intermediate re-convergence provides useful insights into how nondeterminism develops in MDLMs.

Effective and relatively lightweight mitigation

The proposed approach requires no retraining or architectural modification and reduces LLaDA MATH500 output divergence from 69.2% to 1.0%, at less than half the inference cost of full LayerCast.

Critical weaknesses

Decoding-rule modification and limited fidelity

Freezing the unmasking order ignores confidence changes after intermediate token commitments, fundamentally changing the original greedy decoding rule. Although cross-execution agreement improves, only 61/500 LLaDA MATH500 outputs match the unfrozen LayerCast decoder, and Dream exhibits accuracy degradation. Thus, improved reproducibility comes at the expense of fidelity to the original decoding procedure.

Limited task diversity

The evaluation covers only MATH500 and HumanEval. Given the observed accuracy changes under order freezing, evaluation on more diverse tasks is needed to assess its general applicability.

Limited generalization across decoding configurations

The main mitigation experiments use only a fixed response length (512 tokens) and single-block decoding, without evaluating LLaDA's multi-block decoding. Although alternative decoding schedules are analyzed for divergence, the proposed mitigation is not evaluated under these settings. Its effectiveness across different response lengths and larger batch sizes also remains unverified.

Heuristic verification threshold

The 8-ULP threshold is selected post hoc on LLaDA MATH500. Although transferred to HumanEval and Dream without retuning, substantial residual divergence on Dream raises questions about its robustness across models and tasks.

Computational overhead and deployment relevance

Despite being substantially cheaper than full LayerCast, the method incurs roughly 2× the inference cost of BF16. Its throughput and memory overhead under realistic serving workloads remain unverified.

Questions for authors

EOS overflow in single-block LLaDA decoding

Given the use of 512-token single-block decoding, to what extent does the EOS overflow phenomenon identified in Rainbow Padding [1] affect the reported divergence and re-convergence statistics? Could the authors clarify whether this issue was observed and how it was accounted for in the analysis?

Mitigation under multi-block decoding

The appendix evaluates divergence under LLaDA's 32-token block schedule, but not the proposed order-freezing and ULP-verification method. Could the authors evaluate whether the reported reproducibility gains and computational trade-offs hold under multi-block decoding?


[1] Kim et al., “Rainbow Padding: Mitigating Early Termination in Instruction-Tuned Diffusion LLMs,” ICLR 2026.

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

The paper studies the "underdetermination" of the diffusion models., which is a more complex question, as masked diffusion model needs to decide where and what for token generation. In the paper, the author checks the partial generation of the MDLMs and summarised that the position decision is a more significant factor than token itself. They also proposed an according method to reduce the "nondetermination" by fixing the position decision. The results are significant, from 69.2% to 1.0% on LLaDA's MATH500 outputs.

Critical strengths
  1. The paper's writing and motivation is clear, easy to follow.

  2. The two framing of "position and token" are insightful and specifically designed for MDLMs.

  3. The fix is effective.

Critical weaknesses

The main concern is that "when fixing the position, we are actually changing the original MDLMs's original working mechanisms.". And we can observed the response discrepancies before and after "position fix"

Questions for authors
  1. how to select k? k = 8 is based on the results on MATH500, but the performances across different models are different. so, any dataset-agnostic way to select k?

  2. Any consistent patterns to explain the accuracy loss? any ideas of not losing too much accuracy (the response also keep similar) while doing the alation study.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.