acceptodds
Under review as a conference paper at ICLR 2027

Sample the Order, Not the Token: Test-Time Scaling for Masked Diffusion Language Models

Abstract

Standard test-time scaling methods like temperature-sampled self-consistency are highly effective for autoregressive models, but we show it is not true for masked diffusion language models (dLLMs). Attempting to scale dLLMs via temperature sampling collapses generation length and plummets accuracy (e.g., from 35% to 6% on MATH500), failing to yield the diversity required for ensembling. Motivated by this misalignment, we propose Order-Space Exploration (OSE), a novel decoding strategy demonstrating that dLLM diversity should originate from the order of token generation, not the token distribution itself. We first observe that a perfect model's answer distribution is invariant to unmasking order, thus shuffling this schedule yields "free" diversity driven entirely by the model's internal disagreement across generation paths, avoiding the accuracy penalty of temperature scaling. OSE introduces a one-parameter Plackett–Luce perturbation of the sampler's position ranking and aggregates the N draws with a majority vote over their answers. Empirically, OSE raises answer diversity by 2-5 while leaving single-draw accuracy unchanged. This unlocks test-time scaling for dLLMs, beating standard self-consistency on Dream by up to 45.5 points on a variety of downstream tasks. Additionally, OSE rollouts restore the learning signal in GRPO, removing nearly all zero-gradient steps on generation tasks and about half on multiple choice. It improves the trained policy where the base model has room to learn (+7.6 on MATH500, +8.5 on Countdown), with no change to the model or the inference cost.

Primary area:
generative models
Keywords:
Diffusion Language models, LLMs, Test time scaling.

Reviews

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

This paper shows that self-consistency, which generates multiple answers and takes a majority vote, can be ineffective for dLLMs because the samples are often nearly identical. As a result, the authors propose Order-Space Exploration (OSE), which creates diversity by perturbing the order in which tokens are revealed rather than changing how tokens are sampled, and then uses majority voting to select answers. They provide a theoretical analysis of this approach and evaluate it on Dream and LLaDA across six tasks. OSE increases answer diversity by 2–5× without hurting single-sample accuracy, outperforms standard self-consistency, and achieves competitive results at lower cost than alternative decoding ensembles. They additionally show that using OSE samples for GRPO training improves learning.

Critical strengths
  • Novel test-time scaling approach: using the unmasking order as a source of diversity is specific to dLLMs and the proposed method requires only one hyperparameter, no verifier, and no retraining. Each sample also costs the same as one from the default sampler.
  • Useful connection to RL training: the authors show that the same order-perturbed samples can serve as GRPO rollouts. This results in improvements in the trained policy (+7.6 on MATH500 and +8.5 on Countdown).
  • Theoretical motivation: the core results seem correct and they seem to help explain why perturbing the order should be cheaper than raising the temperature.
  • Well-executed experiments: within its scope, the evaluation is thorough, and it covers two models and six tasks. It also includes results over three seeds and CIs, temperature sweeps, a temperature-matched HEX comparison, ablations and wall-clock costs.
Critical weaknesses
  • Related work and citations: the introduction states that confidence-based ranking is the most widely adopted approach without citing the relevant methods, and related work is discussed only in Appendix. Confidence-based decoding methods and prior work on sampler equivalence could be better referenced in the introduction. In addition, related test-time scaling methods are also not discussed or compared empirically in the main text.
  • Limited evidence for the decoder analysis: the decoder analysis focuses on Dream’s default settings, so it is unclear whether OSE provides general benefits or mainly fixes a degenerate sampler configuration. The results on LLaDA suggest the effect may depend on the model.
  • Theoretical claims could be better supported: the interpretation of OSE’s cost bound is somewhat unclear, and the bound would benefit from empirical validation. Some claims about on-policy sampling also require further justification.
  • Dense presentation and inconsistent notation: while the paper is generally easy to follow, sometimes the main text feels a bit too dense. The notation and terminology used is sometimes inconsistent (for example, T denotes temperature and the number of steps, and OSE is called both "Order-Space Exploration" and "Order-Ensemble Decoding"), which makes the claims harder to verify.
  • Limitations are not reported: they authors do not openly report limitations which include issues about voting, and model-dependent gains.
Questions for authors
  1. Would it be possible to separate the effects of token sampling and unmasking-order perturbations? This would help clarify whether the gains come specifically from the different orders.

  2. Does OSE remain effective across different samplers, decoding configurations, and dLLMs, including cases where the default sampler is already stochastic?

  3. Would it be possible to empirically validate the proposed cost bound? Could the authors also clarify the impact of the assumptions, particularly the dependence of the ranking on the model parameters?

  4. How does OSE compare with alternative test-time scaling and diversity methods under matched compute budgets? Similarly, how does Order-Diverse GRPO compare with existing approaches to generating diverse training rollouts?

  5. Figure 2 is hard to parse, please consider improving its clarity. More generally, the main text is quite dense, and some notation is used inconsistently (as mentioned in Weaknesses), so a revision for clarity would strengthen the manuscript.

4 comments

We thank the reviewer for the careful review. We've addressed the concerns below.

Q1. Separate the effect of token sampling from the order. We built a decoupled sampler that computes the ranking at the default T_rank = 0.1 but draws tokens at T_tok. With T_rank fixed, the unmasking order remains entirely unchanged at every T_tok, meaning any performance shifts come exclusively from the token draw (a full study of T_tok from 0.1 to 1.0 in App.) Below is the vote@8 on Dream:

SamplerARC-CCountdownGSM8KMATH500RACE
Coupled, T = 0.776.523.824.87.884.0
Decoupled, T_tok = 0.791.039.091.550.589.0
OSE λ = 1, T = 0.189.842.888.058.286.8

Three findings. (i) The collapse comes from temperature in the ranking: coupled T = 0.7 writes 8–23 tokens, decoupled 170–380, as at T = 0.1. (ii) With the ranking protected, token temperature is a strong baseline on short answers. (iii) But it costs single-draw accuracy and needs tuning. On MATH500 the single draw is 23.5 at T_tok = 0.7 and 4.9 at 1.0, against 38.7 for OSE (base 35.6), and the best T_tok varies by task (0.3 to 1.0), while λ = 1 is fixed. Adding OSE on top of T_tok does not help, so the two are substitutes (App. Q); our order ablation (App. S) also shows that local perturbations help and global ones collapse.


Q2. Other samplers and dLLMs, including stochastic default samplers. (a) Block decoding with raised temperature: we ran the full Dream grid (block 32/64 × T, six tasks; App. P). With the best block size and temperature for each task, block decoding lands within −0.7 to +3.0 vote points of OSE on five of six tasks (+8.5 on Countdown, where blocks also fix the answer format), but it needs that per-task search, and a high T breaks long generation (MATH500 at T = 0.9: single draw 19.1, against 38.7 for OSE). (b) Two new dLLMs, with λ = 1 as everywhere else unless stated (App. R):

  • Stable-DiffCoder-8B-Instruct (code). Its default sampler is deterministic (greedy tokens, confidence order): all 16 draws give the same result, so vote@16 = pass@1 (MBPP 63.8). Its temperature is decoupled by construction, so the temperature arm is the decoupled baseline of Q1: | Stable-DiffCoder | MBPP pass@1 | MBPP vote@16 | MBPP+ pass@1 | MBPP+ vote@16 | HumanEval pass@1 | HumanEval pass@16 (oracle) | |---|---|---|---|---|---|---| | default | 63.8 | 63.8 | 69.5 | 67.0 | 75.0 | 75.0 | | raised temperature | 63.0 | 70.4 | 70.1 | 74.2 | 75.8 | 91.3 | | OSE λ = 1 | 65.1 | 70.6 | 71.8 | 74.1 | 76.8 | 91.0 |

OSE matches the decoupled temperature's vote gain (MBPP +6.8 vs +6.6; MBPP+ +7.1 vs +7.2) with fewer distinct answers (1.48 vs 1.85), and is the only method that raises pass@1 everywhere.

  • LLaDA 2.0-mini (16B MoE, adaptive commits, coupled temperature). With λ = 0.5, OSE raises the vote on GSM8K, MATH500 and Countdown (+0.5 to +1.3) and keeps the single draw within 0.3 points on GSM8K and MATH500, where temperature costs 4.5 points on MATH500. Gains are small because the default is already stochastic and near the ceiling (vote ≈ 93% on GSM8K, ≈ 98% on Countdown), leaving little for any method.

Q3. Cost bound; assumptions. We agree the bound is loose (an 8–1–1 split already exceeds 1) and now present Prop. 4.4 as a qualitative statement. The direct check is the single draw, which moves by only −1.0 to +2.3 points at λ = 1 on all 12 settings (Table 12). Ranking depends on θ: Prop. 4.6 treats the order as part of the environment, as d1 does with its confidence ranking, and so leaves out the score term of the order. Every RL gain is measured with the default decoder, not the training sampler.

Q4. Matched compute; diverse RL rollouts. Test time: an OSE draw costs the same forward passes as a default draw, so N OSE draws and N default draws have equal compute; HEX is 3–3.5× slower per draw in our implementation.

RL: with gold rewards, policies trained on OSE rollouts beat those trained on default rollouts under the default decoder: +8.5 on Countdown [+3.6, +13.4], +7.6 on MATH500 [+3.8, +11.4], +2.7 on GSM8K (Sec. 5.5). New runs (App. T) add MBPP+ and Zebra, a block-32 rollout baseline, and label-free rewards (plurality vote of the group, no labels). Δ = accuracy minus base, default decoder:

rolloutsCountdown label-freeMATH500 label-freeMBPP+ goldMBPP+ label-freeZebra goldZebra label-free
default (λ = 0)−0.9−2.60.0+1.70.00.0
block-32+6.3−1.9+2.7+4.0−2.2+0.3
OSE λ = 1+12.1+0.8+5.8+5.2+11.2+14.2

Default rollouts almost never give mixed groups (1–9% with gold rewards, 0.0–0.3% label-free), so label-free RL cannot start. OSE gains most in every column and, without labels, comes close to its gold-reward gain, because its vote is a far better teacher than its single draw (teacher lift +10.8 to +25.7, against +0.1 to +4.3 for block-32). Under DAPO at a matched budget (9,600 rollouts), the default order makes zero updates; OSE makes 141 and moves Countdown from 15.2 to 18.8. No importance weights are needed (Prop. 4.6).


W1. Related work and citations. The introduction now cites confidence-based decoders, sampler-equivalence results and dLLM test-time scaling methods (HEX, OTS, prefix-denoising and temporal self-consistency). Sec. 5.4 compares OSE with HEX and a tuned block decoder.

W4 / Q5. Notation and clarity. We now use K for the number of steps and T only for temperature, one name (OSE) throughout.

W5. Limitations. A new Limitations paragraph states that OSE helps most when the default sampler is near-deterministic, as deployed (Dream, LLaDA, Stable-DiffCoder, all at λ = 1); with a stochastic, near-ceiling default (LLaDA 2.0-mini), OSE and temperature are substitutes and a smaller λ is needed; the vote leaves a gap to pass@N; and the cost bound is qualitative.

We hope these answers address the reviewer's questions and would be glad to clarify further.

Reviewer_odeROpenReview ↗

Response to authors

I thank the authors for the detailed response and new experiments, which address most of my concerns. Just one concern remains: the decoupled experiment (answer to Q1) shows that the collapse comes from temperature in the ranking, and that token temperature with a protected ranking is competitive with OSE on short-answer tasks. This is in line with W2, as the motivation relies on a specific sampler configuration. I encourage the authors to revise the introduction to better clarify this and OSE's role. I thank the authors for their effort and will increase my score.

We thank the reviewer for the constructive discussion and for raising the score. We agree and have revised the introduction accordingly (in blue). It now states that the collapse at high temperature is a property of the default sampler, where the same temperature also ranks the positions, rather than of dLLMs in general, and that with a protected ranking (App. P, Q) token temperature is competitive on short-answer tasks, at the price of per-task tuning and a lower single draw on long generation. It also clarifies OSE’s role. The abstract and conclusion are scoped in the same way. The revised PDF is uploaded.

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

The authors show that temperature-based sampling, commonly used to promote diversity for test-time computation in autoregressive large language models, does not work well in diffusion large language models (dLLMs). They propose order-space exploration (OSE) as an alternative way to introduce diversity. They demonstrate that OSE can increase diversity while preserving performance in existing dLLMs, such as Dream and LLaDA, leading to better results when combined with test-time compute techniques such as self-consistency. They further show that using these diverse samples for GRPO training can yield additional performance improvements.

Critical strengths
  • Clear problem formulation: The paper clearly explains the problems that arise when increasing temperature to promote diversity in dLLMs.
  • Clear presentation of the proposed method: The authors propose introducing noise into the decoding order to obtain diverse samples. The method is clearly described, and its mathematical formulation helps readers understand the approach.
  • Extensive experimental evaluation: The paper presents comparisons across a range of benchmarks, settings, and baselines, providing substantial empirical evidence to help readers assess the method.
  • Extension to RL fine-tuning: The authors extend the approach to GRPO training and investigate whether the resulting diversity can benefit RL fine-tuning.
Critical weaknesses
  • Limited advantages over block denoising with high temperature, with insufficient analysis of the underlying reasons: The paper clearly explains that temperature-based diversity can be problematic in dLLMs because EOS tokens may be denoised prematurely, and demonstrates this issue convincingly when applying high temperatures to Dream-Instruct. However, block-based decoding methods, such as those used in LLaDA and HEX, can avoid this issue even at high temperatures by denoising earlier blocks first. This is supported by LLaDA’s stable single-draw performance in Table 14 and by the more stable performance obtained when applying HEX to Dream in Table 15, compared with decoding without HEX in Figure 2. Nevertheless, the paper lacks a systematic comparison and analysis against this combination of block denoising and high temperature. For the advantages of OSE over HEX with high temperature on MATH500 and Countdown in Figure 5, the analysis also does not appear to go much beyond differences in single-draw performance. For example, on RACE with LLaDA, the gap is 7.1 percentage points for single-draw accuracy but only 0.8 percentage points for voting accuracy. In contrast, on Countdown, the gap increases from 5.5 to 11.2 percentage points. These contrasting patterns warrant further analysis.

  • An overly loose cost bound with limited practical significance (Proposition 4.4): One of the paper’s central claims is that the cost of OSE, measured as the change in accuracy, is bounded by a quantity associated with its benefit in diversity, 2I(σ;y∣q)\sqrt{2I(\sigma;y|q)}, as stated in Proposition 4.4. However, this bound appears too loose to be particularly informative. For example, if differences in decoding order lead to 10 outputs distributed across three outcomes—eight identical outputs and two distinct singleton outputs—then 2I(σ;y∣q)≈1.13\sqrt{2I(\sigma;y|q)}\approx 1.13, exceeding the full 0–1 range of accuracy. This suggests that, once a meaningful degree of diversity is achieved, the bound may no longer provide a nontrivial guarantee on the change in accuracy.

Questions for authors
  • In Proposition 4.3, I understand “free” to mean that accuracy remains unchanged in the order-consistent case. However, I do not find this terminology immediately intuitive. Could you use a more explicit description, such as “distribution-preserving”?
  • In line 262, how can D increase when the model is exact?
  • For LLaDA with high-temperature sampling, as evaluated in Table 14, could you provide analyses analogous to those in Figures 3 and 4?
8 comments

We thank the reviewer for the positive assessment and the concrete questions. We ran the comparison with block decoding at a high temperature that the reviewer asked for.

W1. Block decoding + high temperature, and the reasons for the differences.

We ran the full grid on Dream: block sizes 32 and 64, with T ∈{0.1,0.3,0.5,0.7,0.9,1.0}\in \{0.1, 0.3, 0.5, 0.7, 0.9, 1.0\} across six tasks (summary at the end of this reply; full results in App. P).

We agree with the reviewer that blocks protect against the early end-of-text commit. With the best block size and temperature tuned per task, block decoding reaches −0.7 to +8.5 vote points over OSE (the largest gap is on Countdown, where blocks also help fix the answer format). We have added this baseline to the abstract and Sec. 5.4. However, OSE has four distinct practical advantages:

  1. No temperature to tune, and no setting that breaks. The optimal T varies heavily by task (0.3 on RACE, 0.5 on ARC-C, 0.7 on GSM8K/Countdown, 0.9 on MMLU). A wrong T is costly for long generation: at HEX's T = 0.9 , the MATH500 vote falls to 45.0 (19.1 single draw). Over its range, block-32 swings the MATH500 vote by 23 points (T = 0.3–1.0), whereas OSE swings it by only 9 points (λ = 0.5–4). OSE relies on a fixed λ = 1 across all tasks.
  2. Superior on long generation. On MATH500, OSE achieves the highest vote (58.2), pass@8 (69.8), andamong high-vote setting, the highest single-draw accuracy (38.7, vs. 35.0 for block-32 at T = 0.7).
  3. Preserves the token distribution. At the default T = 0.1, blocks alone add almost no diversity (0.04–0.18). Block+ T gets its diversity purely from the temperature, which alters every conditional. OSE keeps the default temperature intact (Prop. 4.3). Furthermore, when T is set too high, adding OSE actually repairs part of the loss (MATH500, block-32, T = 1.0 : +6.0 vote, +5.9 single draw).
  4. Transfers to other models. LLaDA's default sampler already decodes in blocks, so LLaDA at T = 0.9 is exactly block + high T. Even there, OSE gains more vote on long tasks and preserves the single draw better (see Q3 below).

The two methods also differ fundamentally in RL training; see our reply to Reviewer odeR, Q4, and App. T.

Why RACE and Countdown behave differently (LLaDA, Fig. 5). The vote is correct when the right answer is the most frequent one in the pool (see our reply to the first reviewer). On RACE there are four options. Even with HEX's weaker members, the right letter stays the most frequent, and both methods have the same pool (pass@8: OSE 93.2, HEX 95.0; vote 87.5 vs 87.0). On Countdown the answer space is large and the right answer is rare: HEX's weaker members (single draw 12.6 vs 18.1) remove it from the pool (pass@8: OSE 69.0, HEX 58.0), so the vote cannot recover it (42.0 vs 31.0). So the vote gap follows the pool gap, not the single-draw gap.

W2. The cost bound (Prop. 4.4) is loose. We agree, and the reviewer's example is correct, an 8–1–1 split already makes the right-hand side larger than 1. We now present Prop. 4.4 as a qualitative statement (the cost goes to zero when the disagreement between orders goes to zero), not as a guarantee. Also we point to the direct measurement of the cost which is the single-draw accuracy, which changes by −1.0 to +2.3 points at λ = 1.


Q1. The word "free".

We agree; "free" was imprecise and could be misread to mean the vote improves at no cost. What Prop. 4.3 actually states is narrower: for an order-consistent model, the output distribution is identical under every order, meaning single-draw accuracy cannot change with λ. To clarify this, we now use the explicit term distribution-preserving throughout the manuscript and have renamed Prop. 4.3 to "Order perturbation is distribution-preserving; temperature is not." At exactness, the vote remains unchanged; any empirical gain arises specifically because the real model is not perfectly order-consistent. Additionally, we rewrote Sec. 4.3 to state exactly when the vote is correct (new Prop. 4.5): when the correct share p⋆ strictly exceeds the top-wrong share w. OSE keeps p⋆ roughly the same while successfully lowering w (as shown in the new App. O, p⋆ shifts by at most 2.3 points, while w drops across all 12 model–task pairs).

Finally, we updated the abstract, replacing "free diversity" with "diversity that keeps the answer distribution unchanged at exactness," and adjusted similar phrasing throughout the draft accordingly.

Q2. How can D increase when the model is exact?

The confusion stems from our previous sentence conflating two different meanings of "exact."

  1. Order-consistent model (Def. 4.2): If the sampler’s conditionals are perfectly order-consistent, every order yields the exact same answer distribution. In this scenario, diversity D does not change with λ, and the average member error Ā remains perfectly flat (dĀ/dλ = 0).
  2. Exact denoiser at deployed temperature: An exact denoiser sampled at T = 0.1 is tempered, meaning its conditionals are no longer order-consistent (Example C.4). Because of this tempering, different orders naturally reach different outputs, each with high confidence. This is why D can and does grow in practice (as we see on Dream). In this regime, Ā is no longer perfectly flat, but its change is strictly bounded by Prop. 4.4.

The new Sec. 4.3 states the two cases separately: "for an order-consistent model, dĀ/dλ = 0 (Prop. 4.3) and D does not change; for a tempered model, D can grow, and Prop. 4.4 bounds dĀ/dλ".

Q3. LLaDA at high temperature.

We ran LLaDA with its default block sampler at T = 0.9 on the full test sets. Below we compare OSE and T = 0.9 at the same N = 4 draws (added to the paper in App. K.1, Table 18).

LLaDA, Δ vs defaultGSM8KMATH500CountdownARC-CMMLURACE
T = 0.9, Δ vote@4+4.2+1.7+2.2+5.3+3.4+3.9
OSE λ = 1, Δ vote@4+4.5+4.8+9.6+5.3+4.0+2.7
T = 0.9, Δ single draw−2.0−4.2−2.8+0.1−0.1−3.5
OSE λ = 1, Δ single draw+0.1+0.8+1.3+2.5+1.6−0.3

On short-answer tasks (GSM8K, ARC-C, MMLU, RACE), T = 0.9 and OSE yield similar vote gains, much like on Dream. On the two long-generation tasks, however, OSE gains clearly more (MATH500 +4.8 vs +1.7, Countdown +9.6 vs +2.2).

The single-draw accuracy explains this divergence: T = 0.9 drops single-draw accuracy on five of six tasks (by up to 4.2 points), while OSE preserves or raises it (shifting −0.3 to +2.5). This perfectly matches the pool argument from Part 2: on RACE (4 options), weaker draws still leave the correct letter as the most frequent answer; on Countdown and MATH500, weaker draws cause the rare correct answer to vanish from the pool, preventing the vote from recovering it.


Summary of the Block + Temperature Grid (W1)

To summarize the ablation requested in W1, the table below shows the range across block sizes 32 and 64 at T ∈ {0.3, 0.7, 0.9}, compared against the single fixed setting of OSE λ = 1 (T = 0.1, no blocks). The full grid covering all other temperatures is in App. P.

DreamGSM8KMATH500CountdownARC-CMMLURACE
vote@8: block + T83.0–90.745.0–57.530.5–51.389.2–91.568.3–73.287.8–89.8
vote@8: OSE88.058.242.889.870.787.8
single draw: block + T80.9–82.919.1–39.214.1–24.679.0–86.862.5–66.178.6–84.7
single draw: OSE82.238.715.084.562.882.2
pass@8: block + T87.3–96.557.0–69.748.8–78.893.8–97.380.5–92.591.5–95.5
pass@8: OSE95.769.864.396.388.295.0
diversity: block + T0.07–0.210.49–0.610.54–0.790.09–0.230.19–0.340.09–0.21
diversity: OSE0.180.580.590.140.320.21

With one fixed setting of OSE it is inside or above the block + T range in 21 of 24 entries. The low end of each block + T range is the cost of a wrong temperature.

We hope these results fully address the reviewer's concerns.

Thank you for the additional experiments and clarifications. W1 and Q1–Q3 are resolved.

W2 is my only remaining clarification. I agree with the qualitative interpretation of Proposition 4.4 in your response: the cost approaches zero as disagreement between orders approaches zero. Could you point me to the passage in the revised manuscript that makes this interpretation explicit?

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

The paper studies test-time scaling for masked diffusion language models. It identifies a flaw in Dream’s default decoder: under published settings, most masked positions tie at zero entropy, ties go leftmost, and decoding becomes effectively greedy and left-to-right. Self-consistency thus has little diversity, while higher temperature makes the sampler fill end-of-text padding first and collapse outputs. The proposed fix keeps the token sampler unchanged and randomizes only the unmasking order by softly perturbing the sampler’s position ranking with one parameter, then majority-votes over several draws at no extra per-draw cost. Unlike temperature, this perturbation leaves an idealized model’s output distribution unchanged. The same order-perturbed sampling extends to training, providing diverse rollouts for GRPO groups that would otherwise have no gradient. Experiments on Dream and LLaDA across math, multiple-choice, and Countdown tasks show higher answer diversity at similar single-draw accuracy, better majority-vote accuracy than standard self-consistency, and stronger policies than GRPO with default rollouts.

Critical strengths
  1. I found the diagnosis of Dream's default sampler the most interesting part. The authors trace its lack of diversity to confidence-score ties and the resulting almost left-to-right decoding order. This gives a concrete explanation for why repeated sampling brings little benefit, and points to a problem that could easily be missed when evaluating these models.

  2. The proposed fix is simple and appears useful in practice. It requires no model changes or extra forward passes per sample, and the reported voting gains are substantial—for example, from 39.4% to 58.7% on Dream's MATH500 evaluation. The results on LLaDA also provide some evidence that the idea may be useful beyond the particular issue identified in Dream.

Critical weaknesses
  1. I am less convinced by the choice of perturbation than by the diagnosis. The paper gives a reasonable explanation for perturbing ranks rather than confidence scores, but why use this particular exp⁡(−rank/λ)\exp(−rank/\lambda) weighting? The λ\lambda sweeps and adaptive variants are useful, but they stay within the same basic design. Without comparisons against other simple local order perturbations, it is hard to tell how much the proposed form matters, or whether modest randomization around the default order would work just as well.

  2. The theoretical argument does not quite explain the improvement in voting accuracy. Keeping single-sample accuracy roughly unchanged while increasing diversity sounds promising, but it does not guarantee that the correct answer becomes more likely to win. In particular, Section 4.3 analyzes the squared error of the answer distribution, whereas the method ultimately uses a majority vote; Appendix C.8 acknowledges this distinction. The empirical gains are encouraging, but I think the main text draws a stronger conclusion from this analysis than the result supports.

Questions for authors
  1. Beyond the λ\lambda sweeps and adaptive/spatial variants, did you compare against other local order perturbations, such as randomizing within a small window of the ranking? If so, how do they compare at the same sampling budget? This would help me judge whether the particular Plackett–Luce design is an important part of the contribution.

  2. How should the statement in Section 4.3 that "order perturbation pays as soon as D grows" be interpreted for the actual voting rule? Given the caveat in Appendix C.8, what additional assumptions would be needed to conclude that voting accuracy improves? I would like to understand which part of this argument is established theoretically and which part is supported by the experiments.

4 comments

We thank the reviewer for the two questions. We ran a new ablation for the first and rewrote the theory section for the second.

Q1. Other local order perturbations at the same budget. We compared OSE against four alternative order perturbations on Dream (averaged over seeds; App. S, Table 28). Only the committed positions change; the token sampler, commits per step, and budget remain fixed:

  • Local (stay close to the sampler's ranking, like OSE):
    • Uniform within top-2 / top-4: pick uniformly among the 2 (or 4) highest-ranked positions at each commit.
    • One random commit (first step only): perturb only the first committing step, then follow the default order.
  • Global (can commit any position):
    • Softmax over confidence: sample position ii with P(i)∝confi1/TposP(i) \propto \text{conf}_i^{1/T_{\text{pos}}} for Tpos∈{0.1,0.2,0.5,1.0}T_{\text{pos}} \in \{0.1, 0.2, 0.5, 1.0\} (similar to the position temperature of Olausson et al., 2026).
    • Uniformly random order.

Entries are vote@8 (single-draw accuracy); the softmax row reports the min–max range across TposT_{\text{pos}}. References are recomputed in the same run (L=256L=256 on all tasks, vs. L=512L=512 on MATH500 in Table 15).

MethodTypeGSM8KMATH500CountdownARC-C
Default (λ=0\lambda = 0)none82.2 (81.9)48.7 (46.3)15.0 (13.6)83.2 (81.6)
OSE λ=1\lambda = 1 (Plackett–Luce)local88.0 (82.2)51.7 (41.7)42.1 (14.6)90.6 (85.6)
Uniform within top-2local87.5 (82.9)49.5 (39.8)45.4 (15.2)90.4 (85.1)
Uniform within top-4local88.0 (82.8)56.7 (42.3)39.6 (14.1)90.5 (85.0)
One random commit (first step)local, once87.9 (81.6)54.7 (42.3)39.0 (22.8)91.0 (85.9)
Softmax over confidence (TposT_{\text{pos}})global54.2–60.3 (42.2–44.4)29.2–31.6 (19.3–20.6)32.6–36.4 (15.0–16.7)88.7–89.0 (82.3–83.2)
Uniformly random orderglobal56.1 (42.5)29.0 (19.2)31.3 (13.9)89.0 (82.3)

Three conclusions:

  1. Locality is the key property. Every local variant preserves single-draw accuracy (GSM8K ≈82%\approx 82\%) and raises vote@8 across tasks (e.g., Countdown 39.0–45.4%39.0\text{–}45.4\% vs. 15.0%15.0\%; MATH500 +0.8+0.8 to +8.0+8.0). Every global variant collapses single-draw accuracy (GSM8K ≈43%\approx 43\%, MATH500 ≈20%\approx 20\%) by committing the end-of-text tail early and truncating outputs. Because many positions have confidence near 1, softmax over confidence spreads commits globally at every TposT_{\text{pos}} tested which confirming that locality must come from perturbing ranks, not scores (Sec. 4.1).
  2. A single early perturbation captures most of the gain. Perturbing only the first step recovers most of the vote gain and lifts Countdown single-draw accuracy from 13.6%13.6\% to 22.8%22.8\%: trajectories branch early, so a small initial push suffices to reach diverse answers.
  3. The specific Plackett–Luce form is more robust and simplest but not essential. Top-kk windows work as well on individual tasks, but the best kk is task-dependent (top-2 leads on Countdown but is the weakest local variant on MATH500). We keep Plackett–Luce because a single continuous parameter smoothly interpolates from the default order (λ=0\lambda = 0) to random, and λ=1\lambda = 1 is never the weakest local variant on any task. We now frame our contribution as local randomization around the sampler's ranking, with Plackett–Luce as its simplest one-parameter form.

Q2. Squared error versus the majority vote. The reviewer is right that Sec. 4.3 analyzed the squared error of the averaged answer distribution, which does not guarantee that the majority vote improves. We have rewritten Section 4.3 and added Appendix O to cleanly separate what is mathematically proved from what is empirically measured.

What is proved: For a given prompt, let p(a) be the probability that one draw returns answer a, and a⋆ the correct answer. With N independent draws, the plurality vote is correct with probability tending to 1 as N grows if and only if a⋆ is the unique mode: p(a⋆) > max_{a ≠ a⋆} p(a). (For finite N, the margin p(a⋆) − max_{a≠a⋆} p(a) controls the error, by a standard multinomial concentration argument.)

Prop. 4.3 establishes that for an order-consistent model, the order perturbation leaves p unchanged. So the condition under which OSE improves the vote is where it keeps p(a⋆) about the same while splitting the wrong probability mass over more distinct answers, so that the largest wrong answer becomes smaller than a⋆.

What is measured: We evaluated both halves of this condition on the draws (new App. O). For each prompt, we compute two shares of its N draws: the correct share p⋆ (draws with the correct answer) and the top-wrong share w (draws with the most frequent wrong answer). The vote is right exactly when p⋆ > w.

The first two columns below are means over prompts, and the last is the % of prompts where p⋆ > w (Default → OSE):

Model · TaskCorrect share p⋆Top-wrong share wPrompts with p⋆ > w (vote right)
Dream · MATH50032.8 → 35.135.0 → 15.338.6 → 56.7
Dream · Countdown15.2 → 15.327.3 → 9.715.2 → 54.9
Dream · GSM8K82.6 → 81.716.4 → 11.782.4 → 88.4
LLaDA · Countdown18.0 → 19.571.8 → 19.918.2 → 38.3
LLaDA · MATH50035.1 → 36.248.5 → 24.534.9 → 43.8

Ties (p⋆ = w; on Countdown, mostly prompts where no draw gives a parsable answer) are broken arbitrarily by the vote and are not counted as right, so the last column is slightly below the vote@N of Table 12. Because the vote is decided per prompt, the two means need not be ordered identically to the final vote (e.g., LLaDA Countdown has a mean p⋆ of 19.5 vs. mean w of 19.9, yet the share of right votes successfully doubles).

We found:

  1. On all 12 model–task pairs, p⋆ remains stable (shifting by −0.9 to +2.3 points), while w falls significantly (by 0.5 to 52 points). OSE wins votes almost entirely by fragmenting wrong answers, not by making single draws more often right, as the plurality condition predicts.
  2. The primary gain comes from rescuing prompts where all default draws agree on one wrong answer (w = 100%), which no vote can fix. OSE successfully fractures these failures (new Fig. 12): mean w drops from 19.0 to 14.0 (Dream) and from 27.3 to 19.1 (LLaDA).
  3. On contested prompts (25% ≤ p⋆ ≤ 75%), w drops on 50% of prompts and rises on 32% (Dream; LLaDA 47% vs 23%). Paired per prompt, OSE fixes 1.7–8.8× more prompts than it breaks. When it does break a prompt, the cause is the opposite: the correct draws vanish (mean change in p⋆ ≈ −58 points), which is the inherent risk of moving a draw off a successful trajectory.

To align the text with these findings, we removed the sentence stating that order perturbation "pays as soon as D grows". The ambiguity decomposition is now explicitly framed as intuition, rigorously backed by the plurality condition and this new empirical measurement.

We thank the reviewer again; both points made the paper much more precise.

Dear Reviewer,

As the discussion period ends soon, we wanted to check whether our response addresses your questions. We would be glad to clarify anything further. Thanks in advance.

Dear reviewer, we are following up before the discussion period closes on Nov 18. We would be grateful to know whether our reply addresses your concerns. If it does, we would appreciate it if you would consider updating your score.

Comments on the paper

1 comment

We thank all reviewers for their careful and constructive feedback. We have uploaded a revised PDF that addresses every comment and question; all changes are in blue. The main additions:

  • Theory: Sec. 4.3 now states the exact condition for a correct vote (new Prop. 4.5) and measures it (App. O): OSE keeps the correct share and lowers the top-wrong share on all 12 model–task pairs.
  • Baselines: block decoding with a tuned temperature (App. P), a decoupled token temperature (App. Q), other local and global order perturbations (App. S), and LLaDA at T = 0.9 (App. K).
  • Generality: two new dLLMs, Stable-DiffCoder (code) and LLaDA 2.0-mini (App. R).
  • Training: label-free GRPO, a block-32 rollout baseline, two more tasks, and DAPO (App. T): with OSE rollouts, label-free RL works where default rollouts give no gradient.
  • Clarity: consistent notation (K for steps, T for temperature), one method name, and expanded references in the introduction.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.