Pith. sign in

REVIEW 3 major objections 4 minor 14 cited by

Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A pretrained masked diffusion model that reveals tokens in order of confidence margin solves Sudoku at 89.49% accuracy—up from 6.88% for random-order decoding and beyond a 42M autoregressive model trained with the correct decoding order.

desk verdict Sudoku adaptive-inference result is the real contribution; the computational-hardness claims are overstated and need a missing step. read the letter →

arxiv 2502.06768 v3 pith:TGFNDEK2 submitted 2025-02-10 cs.LG

Jaeyeon Kim , Kulin Shah , Vasilis Kontonis , Sham Kakade , Sitan Chen This is my paper · ORCID
classification cs.LG
keywords maskeddiffusionmodelsautoregressiveadaptiveinferencetokenorderingcomputationalhardnessplantedconstraintsatisfactionproblemsSudokudiscrete
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Masked diffusion models (MDMs) trade a harder training problem for flexible inference: they must learn every possible token-infilling subproblem, but at generation time they may reveal tokens in any order. This paper argues that the training burden is real—many MDM subproblems are computationally hard even for simple distributions where autoregressive models are efficient—and that the inference flexibility more than pays for it. The central empirical demonstration is that a pretrained 6M MDM, decoded by always revealing the token whose top two probabilities are most separated (top probability margin), jumps from 6.88% to 89.49% accuracy on Sudoku, outperforming a 42M autoregressive model that was explicitly teacher-forced to learn the correct decoding order. If correct, this shows that ordering knowledge can be discovered at inference time rather than baked in at training time, and that adaptive decoding should be part of how discrete diffusion models are deployed on reasoning and planning tasks.

What carries the argument

The load-bearing identity is the reformulation of the MDM objective: for a time-embedding-free denoiser, the training loss equals a weighted sum over all infilling masks of $-\log p_\theta(x^i_0 \mid x_0[M])$, equivalently the average over all permutations of an any-order autoregressive loss: $L_\theta = -\mathbb{E}_{x_0,\pi\sim\mathrm{Unif}(S_L)}[\sum_{j=0}^{L-1}\log p_\theta(x_0^{\pi(j)}\mid x_0[\pi\{j,\ldots,L-1\}])]$. This identity makes explicit that order-agnostic training solves exponentially many subproblems while order-aware training solves only $L$ of them. The inference-side mechanism is the adaptive decoding oracle: replace random choice of the next unmasked set with $F(\theta,x_t)=\mathrm{TopK}(|p_\theta(x_i=j_1\mid x_t)-p_\theta(x_i=j_2\mid x_t)|)$, the top probability margin, which estimates positional certainty by the gap between the two most likely token values. Because an ideal MDM with exact marginals returns the same distribution under any unmasking order, the oracle can reorder decoding to avoid poorly learned subproblems without any retraining.

What would settle it

On the empirical side, evaluate the same Sudoku test set described in the paper with a 42M autoregressive model trained on the same puzzles with per-sequence teacher-forced decoding orders; if that model reaches or exceeds 89.49% accuracy, the paper's headline empirical claim is refuted. On the theoretical side, exhibit a polynomial-time algorithm that achieves Bayes-optimal overlap on planted NAE-SAT or coloring instances with average degree between $D_{\mathrm{cond}}$ and $D_{\mathrm{KS}}$; that would directly falsify Proposition 3.3's hardness conclusion.

Watch

Extended reading notes

Core claim

The paper's central claim is two-sided. On the training side, for latents-and-observations distributions with a natural order, autoregressive models face only tractable next-token subproblems, whereas masked diffusion models must solve an exponential number of infilling problems, a constant fraction of which are computationally intractable: under the 1RSB cavity prediction (Conjecture B.13) on planted constraint satisfaction problems, no polynomial-time algorithm can predict masked latent tokens when the masking fraction puts the associated planted CSP between its condensation and Kesten-Stigum thresholds (Proposition 3.3), with analogous hardness derived from the Sparse Learning Parity with Noise assumption and from stable-algorithm limits for the symmetric perceptron. On the inference side, the paper claims that a pretrained MDM's own logits contain enough information to choose a good unmasking order, and that the top-probability-margin oracle—reveal the masked token whose two most likely values are most separated—lets the model sidestep hard subproblems. The flagship result is 89.49% Sudoku accuracy for a 6M MDM versus 6.88% for random-order decoding and 87.18% for a 42M autoregressive model trained with the correct order; the same recipe improves generative perplexity on text and lifts coding and math accuracy for the 8B LLaDA masked diffusion model. The overall conclusion is that MDMs without knowledge of the correct token generation order during training and inference can outperform ARMs trained with that order.

Load-bearing premise

The theoretical half rests on a specific unproved statistical-physics conjecture, the 1RSB cavity prediction (Conjecture B.13): in the average-degree window between the condensation and Kesten-Stigum thresholds, no polynomial-time algorithm achieves optimal overlap on planted constraint satisfaction problems; if that conjecture is false, or if hardness of full-assignment recovery does not transfer to predicting a single masked token, the claim that a constant fraction of MDM subproblems are intractable has no support.

Editorial extensions

If this is right

  • On logic puzzles with sequence-dependent natural orders, adaptive MDM inference beats both random-order MDM and ARMs trained with supervised order information: 89.49% versus 87.18% on Sudoku, and 98.5%/98.3% versus 91.17% on Zebra for a 19M model.
  • Adaptive decoding is training-free: the gains come from the logits of an already-pretrained MDM, so the recipe transfers to existing checkpoints such as LLaDA 8B without modifying the loss or the parameters.
  • For open-ended text, adaptive inference lowers generative perplexity relative to vanilla MDM while keeping entropy roughly fixed, indicating better likelihood matching without a diversity-collapse cost.
  • The training-hardness results show that MDM quality is uneven across masks, so aggregate likelihood can hide large per-subproblem failures; the paper's own likelihood experiments demonstrate this imbalance on text and on the L&O-NAE-SAT distribution.
  • On harder Sudoku puzzles outside the training set, top-probability-margin adaptive MDM (49.88%) outperforms an order-aware ARM (32.57%), suggesting better robustness to distribution shift.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the 1RSB prediction is right, random-order decoding is not merely suboptimal—it will repeatedly hit subproblems that are genuinely hard for any polynomial-time model; adaptive ordering then becomes a necessary component for scaling order-agnostic models on structured data, not an optional heuristic.
  • The top-probability-margin oracle is one member of a broader family of confidence functionals over the denoiser's marginals; combining margin-based selection with search or verification could push accuracy further on long-horizon reasoning.
  • A testable scaling prediction follows from the paper's framing: gains from adaptive inference should persist or grow as MDMs scale on tasks where the natural generation order is instance-dependent, and should shrink on strictly left-to-right text where random-order baselines already capture most of the ordering signal.
  • The Sudoku comparison does not isolate ordering from capacity, since the MDM was trained with masking while the ARM was teacher-forced; an ablation that matches capacity and training objective while varying only the decode order would separate the contribution of adaptive ordering itself.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. This paper studies masked diffusion models (MDMs) relative to autoregressive models (ARMs), focusing on the cost of order-agnostic training and the benefit of adaptive inference. It argues that MDM training must solve many more infilling subproblems than ARM training, that some of these subproblems are computationally hard for data with a natural order, and that the resulting performance is imbalanced across subproblems. It then proposes adaptive inference oracles—top probability and top probability margin—that use the model's own confidence to choose which tokens to unmask, so as to avoid poorly learned subproblems. On Sudoku, the top-probability-margin strategy raises a 6M MDM from 6.88% to 89.49% puzzle-solving accuracy, outperforming 42M ARMs trained with teacher-forced ordering information; similar gains are reported on Zebra puzzles and on coding and math benchmarks with an 8B diffusion language model.

Significance. The empirical contribution is substantial. The adaptive-inference results are training-free, use a simple and clearly motivated margin-based uncertainty signal, and are evaluated against appropriate baselines including ARMs with and without order information. The easy-to-hard Sudoku generalization experiment is a particularly valuable falsifiable test. The paper also makes good use of public datasets and existing codebases, so the empirical comparisons are reproducible in principle. The theoretical half is more fragile: Proposition 3.3 is explicitly conditional on Conjecture B.13, and the step from planted-CSP overlap hardness to hardness of single-token marginal prediction is missing, as detailed below. The scaling-law and likelihood-imbalance experiments in Sections 3.2 and 3.3 are suggestive but measure the achievable loss of particular trained models, not computational intractability. If the theoretical claims are weakened or repaired, the central message—that adaptive inference can sidestep hard MDM subproblems—remains credible and valuable.

major comments (3)
  1. [Proposition 3.3 / Appendix B.4] The stated hardness conclusion does not follow from the cited conjecture. Conjecture B.13 concerns the overlap achievable when recovering the entire planted assignment σ; it does not address the complexity of predicting a single coordinate's value or approximating its Bayes marginal. The proof in Appendix B.4 only asserts that the masking problem 'reduces exactly to inference for a planted constraint satisfaction problem' and then invokes the conjecture. To establish Proposition 3.3, one needs an explicit reduction showing that an efficient algorithm for the single-token prediction/marginal problem would imply an efficient algorithm achieving optimal overlap on the planted CSP. As written, the direction of the reduction is also ambiguous; 'reduces exactly to' would give an upper bound rather than a hardness lower bound. The abstract's phrase 'provably computationally intractable' therefore overstates what Appendix B.4 establishes.
  2. [Appendix B.4, proof of Proposition 3.3] The reduction ignores the g=0 observation tokens. In the latents-and-observations distribution of Example 3.2, an unmasked observation token reveals the value of the predicate, which can be 0 or 1, so the learner observes both satisfied and violated constraints. The planted CSP of Definition B.9 contains only clauses with g=1, and missing clauses carry no information about violation. Because the g=0 observations add information, hardness for the clause-only planted CSP does not directly transfer to the masking problem. The proof must either handle the full observation model or explicitly argue that the g=0 observations do not destroy the hardness.
  3. [Appendix B.2, Proposition B.5] The conclusion that any stable algorithm 'must run in super-polynomial time' is not supported by Theorem B.8. That theorem states that any t_N-stable algorithm fails to sample from the posterior to Wasserstein error o(√N) in the relevant regime; it does not provide a runtime lower bound. A stable algorithm that runs in exponential time is not ruled out. The correct statement is a conditional impossibility for polynomial-time stable algorithms, unless a genuine runtime lower bound is proved.
minor comments (4)
  1. [Section 4.2] The text says 'Table 1 in the appendix' but Table 1 appears in the main text; the cross-reference should be corrected.
  2. [Appendix D.2 / Section 4.2] The top-probability-margin oracle adds Gumbel noise with coefficient 0.5 for Sudoku, and the text experiments use temperature/Gaussian noise in the oracle (Appendix D.1.2). These hyperparameters are not swept or discussed in the main text; reporting their sensitivity would strengthen the claim that the gains are not driven by this choice.
  3. [Section 3.2] The 'closer' and 'much-closer' permutation distributions are defined by L/10 and √L random swaps, but the relationship of these distances to the hardness of the corresponding π-learners is not quantified; a brief explanation of the choice would help readers interpret the scaling-law curves.
  4. [References and text] There is a typo 'NeruIPS' in the Austin et al. reference, and the model name is inconsistently written as 'LLaDa' in the main text; both should be fixed.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; the central empirical and conditional theoretical claims do not reduce to their inputs. Minor non-load-bearing self-citation to Shah et al. (2024) accounts for the low score.

full rationale

Walking the derivation chain: the adaptive-inference result (Table 2) selects decoding positions with the model's own confidence and is scored against ground-truth Sudoku solutions, so no fitted quantity is recycled as a prediction. The loss identity in Proposition 2.1 is proved in Appendix E from the prior external equivalence of Zheng et al. (2024), not from this paper's conclusions. Proposition 3.3 is explicitly conditional: it states hardness 'under the 1RSB cavity prediction (see Conjecture B.13)', and its proof reduces the masking subproblem 'exactly to inference for a planted constraint satisfaction problem' at degrees between D_cond and D_KS. That is a conditional reduction from an external conjecture, not a definitional equivalence or a self-citation chain. A real non-circular correctness risk is that Conjecture B.13 bounds overlap for recovering the full planted assignment, while Proposition 3.3 concludes hardness of predicting a single masked token; the missing marginal-to-assignment reduction is not supplied, so the abstract's 'provably' overstates the conditional result. Self-citations (Shah et al. 2024 for the puzzle datasets and ARM-with-ordering baseline; Lehnert et al. 2024 as motivation) are external artifacts and are not load-bearing inputs to the derivation, warranting only the minimal score of 2.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central empirical claim rests on pretrained MDMs and two simple confidence heuristics; no new physical entities are postulated. The theoretical claim rests on conditional hardness assumptions from planted CSPs, SLPN, and stable algorithms. The only additional hand-set knobs are the Gumbel noise coefficient and the temperature variant in the oracle.

free parameters (2)
  • Gumbel noise coefficient for oracle F = 0.5
    Appendix D.2 states 'we add Gumbel noise with a coefficient of 0.5 to the MDM inference oracle F' with no ablation, tuning, or justification. It affects which positions are selected during adaptive inference.
  • Temperature and Gaussian noise in top probability margin for text = not specified
    Appendix D.1.2 introduces a Gaussian noise term epsilon appended to the margin score to preserve diversity; the scale is not given and the effect on perplexity is not ablated.
assumptions (5)
  • domain assumption 1RSB cavity prediction (Conjecture B.13)
    Proposition 3.3 relies on it to assert that no polynomial-time algorithm beats the best efficient overlap for planted CSPs between D_cond and D_KS. Stated in Conjecture B.13 and used in the proof in Appendix B.4.
  • domain assumption Sparse Learning Parity with Noise (SLPN) assumption
    Proposition B.2 reduces hardness of masking problems to SLPN; the assumption is introduced in Definition B.3 and used for the sparse parity example.
  • domain assumption Stable-algorithm hardness framework for the symmetric perceptron
    Proposition B.5 imports Theorem B.8 from Alaoui and Gamarnik, which applies only to stable algorithms such as low-degree polynomials and MCMC, not to all algorithms.
  • domain assumption Observation functions are efficiently learnable in the PAC sense
    Definition 3.1 assumes O_j are efficiently learnable from polynomially many examples; the tractability of order-aware training depends on this assumption.
  • standard math Time-embedding-free denoising network with alpha_0=1 and alpha_1=0
    Proposition 2.1 and the equivalence between MDM loss and any-order autoregressive loss require these conditions, stated explicitly in Section 2.1.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions." pith.science (2026). https://pith.science/paper/TGFNDEK2

@misc{pith2026250206768,
  author       = {Pith},
  title        = {Pith review of: Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TGFNDEK2}},
  note         = {Machine review of arXiv:2502.06768}
}
abstract

In recent years, masked diffusion models (MDMs) have emerged as a promising alternative approach for generative modeling over discrete domains. Compared to autoregressive models (ARMs), MDMs trade off complexity at training time with flexibility at inference time. At training time, they must learn to solve an exponentially large number of infilling problems, but at inference time, they can decode tokens in essentially arbitrary order. In this work, we closely examine these two competing effects. On the training front, we theoretically and empirically demonstrate that MDMs indeed train on computationally intractable subproblems compared to their autoregressive counterparts. On the inference front, we show that a suitable strategy for adaptively choosing the token decoding order significantly enhances the capabilities of MDMs, allowing them to sidestep hard subproblems. On logic puzzles like Sudoku, we show that adaptive inference can boost solving accuracy in pretrained MDMs from $<7$% to $\approx 90$%, even outperforming ARMs with $7\times$ as many parameters and that were explicitly trained via teacher forcing to learn the right order of decoding.

Figures

Figures reproduced from arXiv: 2502.06768 by the authors.

Figure 1
Figure 1. (Top) MDM training can be seen as learning multi￾ple masked prediction problems, where some are harder to learn, leading to performance imbalance (Section 3). (Bottom) During inference, adaptive MDM can avoid difficult problem instances, improving performance (Section 4). x i t = 0). To be precise, qs|t [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Left: MDMs train on hard problems (Section 3.2). x-axis and y-axis correspond to log(FLOPs) and − log pθ(x), respectively. MDM (Blue) is worse than ARM (Orange) in likelihood modeling. Most masking problems (Other lines) that MDM is trained on are harder than those encountered by ARM, as indicated by small log-likelihoods. Right: Task error imbalance (Section 3.3). MDM’s performance varies across different tasks. Fo… view at source ↗
Figure 3
Figure 3. Generative Perplexity. We compare the resulting gener￾ative perplexity (GenPPL) of adaptive vs. vanilla MDM inference. We employ a pretrained 170M MDM and LLaMA-7B (Touvron et al., 2023) as inference and evaluation, respectively. Adaptive MDM inference (Blue) leads to a substantial reduction in genera￾tive perplexity, while maintaining the entropy. pdata(x0). Therefore, other choices of S, not necessarily following … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Overlap achieved by belief propagation initialized at ground truth versus random for planted CSP with k = 3, m = 3, and g = NAE, for N = 10000 and varying choices of average degree D. DKS/K can be shown analytically to be 64, consistent with the phase transition depict…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 14 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. HERALD: High-Throughput Block Diffusion LLM Serving via CPU-GPU Cooperative KV Cache Retrieval

    cs.LG 2026-06 unverdicted novelty 7.0 of 10

    HERALD overlaps CPU-side sparse KV-cache selection with GPU-side block-denoising to hide offloading latency, achieving up to 2.28–2.47x decode throughput over dense GPU serving at 5–10% KV budgets.

  2. The Flexibility Trap: Rethinking the Value of Arbitrary Order in Diffusion Language Models

    cs.CL 2026-01 conditional novelty 7.0 of 10

    Arbitrary-order generation lowers the reasoning Pass@k of diffusion LLMs; constraining RL to autoregressive order (JustGRPO) improves accuracy and preserves parallel decoding.

  3. Induction in Both Directions: A Mechanistic Analysis of In-Context Learning in Masked Diffusion Language Models

    cs.CL 2026-07 conditional novelty 6.5 of 10

    Masked diffusion language models implement a bidirectional induction circuit with previous-token and next-token heads, and they compute the global mask fraction as an implicit timestep.

  4. From Interface to Inference: Eliciting Any-Order Inference from Any-Order Models

    cs.LG 2026-07 conditional novelty 6.0 of 10

    Masked diffusion language models fail to exploit their any-order interface because of positional uncertainty; insertion-based (FlexMDM) and latent-segment (LatentMDM) variants recover distinct any-order inference beha...

  5. Token Time Continuous Diffusion for Language Modeling

    cs.CL 2026-05 conditional novelty 6.0 of 10

    A continuous diffusion language model where each token denoises at its own rate—sure tokens first—improves few-step generation over discrete samplers and roughly matches global-time continuous models.

  6. Orchestrating Dual-Boundaries: An Arithmetic Intensity Inspired Acceleration Framework for Diffusion Language Models

    cs.CL 2025-11 conditional novelty 6.0 of 10

    ODB-dLLM accelerates diffusion LLM inference by adaptively shortening responses and using a jump-share speculative decoding strategy, achieving 2.6-6.3x over Fast-dLLM.

  7. Fine-Tuning Masked Diffusion for Provable Self-Correction

    cs.LG 2025-10 conditional novelty 6.0 of 10

    PRISM fine-tunes any masked diffusion model with a binary-cross-entropy loss so its new head provably estimates per-token quality p(x_i=y_i|y⊕m_i) and can remask low-quality tokens at inference.

  8. Revolutionizing Reinforcement Learning Framework for Diffusion Large Language Models

    cs.CL 2025-09 conditional novelty 6.0 of 10

    TraceRL aligns the RL objective with the DLM's actual step-by-step decoding, producing TraDo-4B/8B models that beat autoregressive baselines on math reasoning.

  9. Any-Order Flexible Length Masked Diffusion

    cs.LG 2025-08 conditional novelty 6.0 of 10

    FlexMDM is a discrete diffusion model that provably supports any-order generation over variable-length sequences by learning an insertion expectation alongside the unmasking posterior, validated by length-fidelity, ma...

  10. Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking

    cs.LG 2025-05 conditional novelty 6.0 of 10

    EB-Sampler dynamically unmasks multiple low-entropy tokens per function evaluation, accelerating masked diffusion model sampling by 2-3x with negligible accuracy loss.

  11. Sudoku-Bench: Evaluating creative reasoning with Sudoku variants

    cs.AI 2025-05 conditional novelty 6.0 of 10

    A new 100-puzzle Sudoku-variant benchmark is hard for frontier LLMs, which solve under 15 percent unaided.

  12. dKV-Cache: The Cache for Diffusion Language Models

    cs.CL 2025-05 conditional novelty 6.0 of 10

    dKV-Cache reuses cached key and value states of decoded tokens during diffusion LM denoising, delivering 2-10x faster inference with near-lossless quality on several benchmarks.

  13. Theoretical Benefit and Limitation of Diffusion Language Model

    cs.LG 2025-02 conditional novelty 6.0 of 10

    Masked diffusion language models have a metric-dependent efficiency tradeoff: near-optimal perplexity in constant steps, but sequence-level correctness needs linearly many steps in the worst case.

  14. Can I Have Your Order? Monte-Carlo Tree Search for Slot Filling Ordering in Diffusion Language Models

    cs.AI 2026-02 reject novelty 5.0 of 10

    Monte Carlo tree search can pick better slot-filling orders for masked diffusion language models, but the claimed advantage over autoregressive models depends on truncating the autoregressive baselines.

Reference graph

Works this paper leans on

47 extracted references · 19 canonical work pages · cited by 14 Pith papers

  1. [1]

    Alaoui, A. E. and Gamarnik, D. Hardness of sampling solutions from the symmetric binary perceptron. arXiv preprint arXiv:2407.16627,

    arXiv

  2. [2]

    The masking problem in this case amounts to an instance of SLPN with input dimension N and sample size in [Ω(N log N ), O(N 0.49k)]

    = 1 − 1/poly(N ) we have that at least P/4N = Ω(N log N ) observation tokens are unmasked. The masking problem in this case amounts to an instance of SLPN with input dimension N and sample size in [Ω(N log N ), O(N 0.49k)]. Because of the lower bound on the sample size, prediction of xM is information-theoretically possible. Because of the upper bound on ...

    work page 2024

  3. [3]

    and Ying, L

    Chen, H. and Ying, L. Convergence analysis of discrete dif- fusion model: Exact implementation through uniformiza- tion. arXiv preprint arXiv: 2402.08095,

    arXiv

  4. [7]

    Scaling diffu- sion language models via adaptation from autoregressive models

    Gong, S., Agarwal, S., Zhang, Y ., Ye, J., Zheng, L., Li, M., An, C., Zhao, P., Bi, W., Han, J., et al. Scaling diffu- sion language models via adaptation from autoregressive models. arXiv preprint arXiv:2410.17891,

    arXiv

  5. [9]

    The curious case of neural text degeneration

    Holtzman, A., Buys, J., Du, L., Forbes, M., and Choi, Y . The curious case of neural text degeneration. arXiv preprint arXiv:1904.09751,

    arXiv 1904

  6. [11]

    Y ., Park, J., Cho, J., Lee, J

    Kim, J., Kwon, S., Choi, J. Y ., Park, J., Cho, J., Lee, J. D., and Ryu, E. K. Task diversity shortens the icl plateau. arXiv preprint arXiv:2410.05448,

    arXiv

  7. [12]

    Liu, A., Broadrick, O., Niepert, M., and Broeck, G. V . d. Dis- crete copula diffusion. arXiv preprint arXiv:2410.01949, 2024a. Liu, S., Mohanty, S., and Raghavendra, P. On statistical inference when fixed points of belief propagation are unstable . In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 395–405. IEEE Computer Society,

    arXiv

  8. [13]

    Think while you generate: Discrete diffusion with planned denoising

    Liu, S., Nam, J., Campbell, A., St¨ark, H., Xu, Y ., Jaakkola, T., and G´omez-Bombarelli, R. Think while you generate: Discrete diffusion with planned denoising. arXiv preprint arXiv:2410.06264, 2024b. Loshchilov, I. and Hutter, F. Decoupled weight decay regu- larization. arXiv preprint arXiv:1711.05101,

    arXiv

Show all 47 references
  1. [15]

    Large language diffusion models

    Nie, S., Zhu, F., You, Z., Zhang, X., Ou, J., Hu, J., Zhou, J., Lin, Y ., Wen, J.-R., and Li, C. Large language diffusion models. arXiv preprint arXiv:2502.09992,

    arXiv

  2. [17]

    Arrows of time for large language models

    Papadopoulos, V ., Wenger, J., and Hongler, C. Arrows of time for large language models. arXiv preprint arXiv:2401.17505,

    arXiv

  3. [18]

    Z., Bezemek, Z., Patel, S., Yao, S., Rector- Brooks, J., Tong, A., and Chatterjee, P

    11 Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions Peng, F. Z., Bezemek, Z., Patel, S., Yao, S., Rector- Brooks, J., Tong, A., and Chatterjee, P. Path planning for masked diffusion model sampling. arXiv preprint arXiv:2502.03540,

  4. [19]

    Rector-Brooks, J., Hasan, M., Peng, Z., Quinn, Z., Liu, C., Mittal, S., Dziri, N., Bronstein, M., Bengio, Y ., Chatterjee, P., et al

    URL https://www.kaggle.com/ dsv/1495975. Rector-Brooks, J., Hasan, M., Peng, Z., Quinn, Z., Liu, C., Mittal, S., Dziri, N., Bronstein, M., Bengio, Y ., Chatterjee, P., et al. Steering masked discrete diffusion models via discrete denoising posterior prediction. arXiv preprint ...

  5. [20]

    An overview of multi-task learning in deep neural networks

    Ruder, S. An overview of multi-task learning in deep neural networks. arXiv 1706.05098,

    arXiv

  6. [21]

    S., Phung, H., Wang, G., Boshar, S., Dalla-torre, H., de Almeida, B

    Schiff, Y ., Sahoo, S. S., Phung, H., Wang, G., Boshar, S., Dalla-torre, H., de Almeida, B. P., Rush, A., Pierrot, T., and Kuleshov, V . Simple guidance mechanisms for dis- crete diffusion models. arXiv preprint arXiv:2412.10193,

    arXiv

  7. [22]

    Causal language modeling can elicit search and rea- soning capabilities on logic puzzles

    Shah, K., Dikkala, N., Wang, X., and Panigrahy, R. Causal language modeling can elicit search and rea- soning capabilities on logic puzzles. arXiv preprint arXiv:2409.10502,

    arXiv

  8. [23]

    Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y ., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L., Ferrer, C. C., Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V ., Goyal, ...

    arXiv

  9. [24]

    Glauber gen- erative model: Discrete diffusion models via binary clas- sification

    Varma, H., Nagaraj, D., and Shanmugam, K. Glauber gen- erative model: Discrete diffusion models via binary clas- sification. arXiv preprint arXiv: 2405.17035,

    arXiv

  10. [25]

    Energy-based diffusion language models for text generation

    Xu, M., Geffner, T., Kreis, K., Nie, W., Xu, Y ., Leskovec, J., Ermon, S., and Vahdat, A. Energy-based diffusion language models for text generation. arxiv preprint arXiv: 2410.21357,

    arXiv

  11. [26]

    Beyond autoregression: Discrete diffusion for complex reasoning and planning

    Ye, J., Gao, J., Gong, S., Zheng, L., Jiang, X., Li, Z., and Kong, L. Beyond autoregression: Discrete diffusion for complex reasoning and planning. arXiv preprint arXiv: 2410.14157,

    arXiv

  12. [27]

    Tinyllama: An open-source small language model

    Zhang, P., Zeng, G., Wang, T., and Lu, W. Tinyllama: An open-source small language model. arXiv preprint arXiv: 2401.02385,

    arXiv

  13. [28]

    Masked diffusion models are secretly time- agnostic masked models and exploit inaccurate categori- cal sampling

    Zheng, K., Chen, Y ., Mao, H., Liu, M.-Y ., Zhu, J., and Zhang, Q. Masked diffusion models are secretly time- agnostic masked models and exploit inaccurate categori- cal sampling. arXiv preprint arXiv:2409.02908,

    arXiv

  14. [29]

    A reparameter- ized discrete diffusion model for text generation

    Zheng, L., Yuan, J., Yu, L., and Kong, L. A reparameter- ized discrete diffusion model for text generation. arXiv preprint arXiv:2302.05737,

    arXiv

  15. [31]

    left-to-right

    introduced D3PM with various types of transition matrices. Later, Lou et al. (2024) proposed SEDD, incorporating a theoretically and practically robust score-entropy objective. Additionally, Varma et al. (2024); Liu et al. (2024b) introduced novel modeling strategies that clas...

    2024

  16. [32]

    left-to-right

    have shown that this performance is tied to the training order of the tasks and therefore can cause brittleness from it. For example, Chen et al. (2024) showed that simply permuting the premise order on math tasks causes a performance drop of 30%. The reason behind such brittl...

    2024

  17. [33]

    Recently, discrete diffusion models have emerged as a promising approach for discrete data apart from autoregressive models

    highlighted the significance of left-to-right ordering in natural language by comparing its likelihood to that of the reverse (right-to-left) ordering. Recently, discrete diffusion models have emerged as a promising approach for discrete data apart from autoregressive models. ...

    2023

  18. [34]

    Building on these intuitions, (Shih et al., 2022; Hoogeboom et al., 2021a) proposed any-order modeling, which allows a model to generate in any desired order

    adopted a similar approach for learning image representations. Building on these intuitions, (Shih et al., 2022; Hoogeboom et al., 2021a) proposed any-order modeling, which allows a model to generate in any desired order. Shih et al. (2022) made the same observation that any-o...

    2022

  19. [35]

    ifP i xiz(j)i is odd (resp. even). Note that for k = O(1), each of these observations is efficiently learnable by brute-force. Below we show that for a certain range of masking fractions, a constant fraction of the masking problems for the correspond- ing L&O distributions are...

    2003

  20. [37]

    Theorem B.8 (Theorem 2.1 in (Alaoui & Gamarnik, 2024)4)

    As discussed at depth in (Gamarnik, 2021), many algorithms like low-degree polynomial estimators and Langevin dynamics are stable. Theorem B.8 (Theorem 2.1 in (Alaoui & Gamarnik, 2024)4). For any constant β >0, there exists cβ > 0 such that the following holds for all constant...

    2021

  21. [40]

    for the symmetric binary perceptron (Aubin et al., 2019). B.4. Proof of Proposition 3.3: sparse predicate observations Here we formally define the relevant notions needed to formalize our claim about hardness in Proposition 3.3. Definition B.9 (Planted CSPs). Given arity k ∈ N...

    2019

  22. [41]

    The prediction is that in this regime, no efficient algorithm can achieve optimal recovery (Krzakala & Zdeborov´a, 2009)

    For Dcond < kP/N < DKS, there exists some other fixed point of the BP operator whose marginals, once rounded to an assignment, achieves strictly higher overlap than does BP with messages initialized randomly. The prediction is that in this regime, no efficient algorithm can ac...

    2009

  23. [42]

    Conditioned on the above events, the masking problem thus reduces exactly to inference for a planted constraint satisfaction problem at average degree Dcond < D < DKS, from which the Proposition follows. C. Experimental details in Section 3 C.1. Experimental details in Section...

    2011

  24. [43]

    In particular, we use AdamW optimizer (Loshchilov & Hutter, 2017), setting β1 = 0.9, β2 = 0.95, and a weight decay of 0.1 and L =

    configurations. In particular, we use AdamW optimizer (Loshchilov & Hutter, 2017), setting β1 = 0.9, β2 = 0.95, and a weight decay of 0.1 and L =

    2017

  25. [46]

    For the Sudoku dataset, we use 6M GPT-2 model, and for the Zebra dataset, we use 19M model

    with keeping most of the hyperparameters default given in the codebase. For the Sudoku dataset, we use 6M GPT-2 model, and for the Zebra dataset, we use 19M model. We set the learning rate to 0.001 with a batch size of 128 to train the model for 300 epochs. For the inference, ...

    2025

  26. [47]

    Let x(n) be a sequence with n tokens being masked from x0, and xi(n) denotes the ith token value of the sequence x(n)

    for the case when the denoising network pθ does not depend on the noise-scale t explicitly. Let x(n) be a sequence with n tokens being masked from x0, and xi(n) denotes the ith token value of the sequence x(n). Let ˜q(x(n)|x0) be the probability distribution corresponding to r...

    2024

  27. [50]

    3.3 this implies a range of masking fractions at which Ω(1) fraction of masking problems are computationally hard

    By Prop. 3.3 this implies a range of masking fractions at which Ω(1) fraction of masking problems are computationally hard. with the observations. Intuitively, each observation provides some constraints and the task is to recover an assignment that satisfies the constraints. T...

    2009

  28. [512]

    To attain a proxy MDM for the Bayes optimal predictor, we further train it for 5 × 104 iterations

    Then, this MDM is trained for 2 × 103 iterations. To attain a proxy MDM for the Bayes optimal predictor, we further train it for 5 × 104 iterations. To measure the error across different tasks, we consider the following setup. For each ℓ ∈ [1, N− 1], we randomly mask ℓ tokens ...

    2024

  29. [2008]

    Scaling up masked diffusion models on text

    Nie, S., Zhu, F., Du, C., Pang, T., Liu, Q., Zeng, G., Lin, M., and Li, C. Scaling up masked diffusion models on text. arXiv preprint arXiv:2410.18514,

    arXiv

  30. [2009]

    (the factor of 2 here is simply because the observations correspond to ordered subsets of size 2). For general predicates and arities, there is an established recipe for numerically computing DKS and Dcond based on the behavior of the belief propagation algorithm (see the disc...

    2008

  31. [2011]

    BERT: Pre-training of deep bidirectional transformers for lan- guage understanding

    Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for lan- guage understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for 10 Train for the Worst, Plan for the Best: Unde...

    2019

  32. [2019]

    A., Bastings, J., Poole, B., Berg, R

    Hoogeboom, E., Gritsenko, A. A., Bastings, J., Poole, B., Berg, R. v. d., and Salimans, T. Autoregressive diffusion models. arXiv preprint arXiv:2110.02037, 2021a. Hoogeboom, E., Nielsen, D., Jaini, P., Forr´e, P., and Welling, M. Argmax flows and multinomial diffusion: Learni...

    arXiv

  33. [2020]

    Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D. d. L., Hendricks, L. A., Welbl, J., Clark, A., et al. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556,

    arXiv

  34. [2021]

    Reverse training to nurse the reversal curse

    Golovneva, O., Allen-Zhu, Z., Weston, J., and Sukhbaatar, S. Reverse training to nurse the reversal curse. arXiv preprint arXiv:2403.13799,

    arXiv

  35. [2022]

    Bormashenko, O

    URL https://arxiv.org/abs/2207.14255. Bormashenko, O. A coupling argument for the random transposition walk. arXiv preprint arXiv: 1109.3915 ,

    arXiv

  36. [2023]

    Related works Discrete diffusion models

    12 Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions A. Related works Discrete diffusion models. (Continuous) diffusion models were originally built on continuous-space Markov chains with Gaussian transition kernels (Sohl-Dickstein et al...

    2015

  37. [2024]

    A., Wang, X., and Zhou, D

    Chen, X., Chi, R. A., Wang, X., and Zhou, D. Premise order matters in reasoning with large language models. arXiv preprint arXiv:2402.08939,

    arXiv

  38. [2025]

    Your absorbing discrete diffusion secretly models the conditional distributions of clean data

    Ou, J., Nie, S., Xue, K., Zhu, F., Sun, J., Li, Z., and Li, C. Your absorbing discrete diffusion secretly models the conditional distributions of clean data. arXiv preprint arXiv:2406.03736,

    arXiv

  39. [2048]

    We also note that unless otherwise specified, we maintain the same training configuration throughout the paper

    A cosine learning rate schedule is applied, with a maximum learning rate of 4 × 10−4 and a minimum learning rate of 4 × 10−5. We also note that unless otherwise specified, we maintain the same training configuration throughout the paper. Examining scaling laws. We conduct IsoF...

    2022

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.