{"id":"ad3fc0c7-23e1-48df-90cd-d783dbdfcd4c","arxiv_id":"2502.06768","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Masked diffusion models trained order-agnostically can solve puzzles better than autoregressive models when inference unmasking order is chosen adaptively by confidence.","lead":"A study of masked diffusion models (MDMs) shows that adaptively choosing the token decoding order at inference time can dramatically improve accuracy on logic and reasoning tasks. On Sudoku, using the model's confidence to pick which cell to unmask raises solved puzzles from under 7% to about 90%, outperforming autoregressive models with far more parameters.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The hardness theorem conflates full-assignment recovery with single-token marginal prediction: Conjecture B.13 only limits optimal overlap for recovering the latent vector, so Proposition 3.3's conclusion about predicting one masked token does not follow from the stated reduction.","rationale":"Read in good faith, the paper has two coupled claims: MDMs train on hard subproblems, and adaptive inference can sidestep them. The Sudoku result (89.49% vs 6.88% vanilla and 87.18% for a 42M order-aware ARM, Table 2) is a strong, falsifiable empirical finding, and the ARM-with-ordering baseline is a meaningful comparator. I credit that core: it is internally consistent, and the adaptive-ordering mechanism (fill high-confidence cells first, then use the now-denser context to solve the rest) is plausible. My objection targets the formal support for the 'train for the worst' half. The reduction in Appendix B.4 equates the masking subproblem with planted-CSP inference, but planted-CSP hardness in the D_cond < D < D_KS window is stated as a limitation on full-assignment overlap, not on coordinate-marginal estimation. The proposition's conclusion requires the latter. This is a genuine logical gap: it is possible for Conjecture B.13 to hold and yet for a simple algorithm to predict a single masked latent token noticeably better than chance, in which case MDMs do not train on the claimed intractable subproblems. The reader's weakest-assumption statement already points at this issue ('or if hardness of full assignment recovery does not imply hardness of predicting a single masked token marginal'); I agree with that identification and sharpen it: even granting the conjecture, the implication is missing. Secondary concerns (no released code, no error bars or test-set sizes for the 2.31-point Sudoku gap, oracle hyperparameters such as the Gumbel coefficient 0.5 possibly tuned on the test split) reinforce the conditional verdict but are not the load-bearing issue. The reader's CONDITIONAL verdict remains appropriate: the empirical claim can stand while the theory is softened or supplied with the missing reduction.","tokens_in":25184,"tokens_out":10799,"duration_ms":106102,"concrete_test":"Re-derive the reduction in Appendix B.4 as an explicit implication: given any polynomial-time algorithm that, for a planted CSP instance at average degree D in (D_cond, D_KS), predicts a single latent coordinate (or approximates its posterior marginal) with accuracy bounded away from 1/m, construct a polynomial-time algorithm that recovers the full assignment with the information-theoretically optimal overlap. If such a reduction cannot be supplied, then Proposition 3.3's 'no polynomial-time algorithm can predict any masked token' conclusion does not follow from Conjecture B.13, and the theory claim should be reworded as conditional hardness of exact joint recovery/sampling.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 3.3 is the paper's main formal evidence that MDMs train on intractable subproblems. Its proof (Appendix B.4) shows that, when all latent tokens are masked and a suitable number of observations are visible, the masking subproblem 'reduces exactly' to inference for a planted CSP at average degree D in (D_cond, D_KS), then invokes Conjecture B.13 (the 1RSB cavity prediction). But that conjecture is only about overlap when recovering the entire planted assignment sigma: it says every polynomial-time algorithm has overlap strictly below the information-theoretically optimal overlap. It does not say that no polynomial-time algorithm can predict a single coordinate's value, or approximate its Bayes marginal, on the same instances. The required missing step is a reduction showing that an efficient algorithm for the single-token marginal/prediction problem would imply an efficient algorithm achieving optimal overlap on the planted CSP. Without it, the proposition's conclusion is unsupported even if Conjecture B.13 is true. Since the abstract and intro describe the intractability of MDM training subproblems as 'provable,' the theory half of the paper is stated more strongly than the appendix establishes. The empirical likelihood-imbalance evidence in Sections 3.2-3.3 is suggestive but measures the achievable loss of a particular trained model, not computational intractability.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":25464,"tokens_out":9479,"duration_ms":87944,"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":[{"comment":"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.","section":"Proposition 3.3 / Appendix B.4"},{"comment":"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.","section":"Appendix B.4, proof of Proposition 3.3"},{"comment":"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.","section":"Appendix B.2, Proposition B.5"}],"minor_comments":[{"comment":"The text says 'Table 1 in the appendix' but Table 1 appears in the main text; the cross-reference should be corrected.","section":"Section 4.2"},{"comment":"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.","section":"Appendix D.2 / Section 4.2"},{"comment":"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.","section":"Section 3.2"},{"comment":"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.","section":"References and text"}],"recommendation":"major_revision","confidential_remarks":"The theoretical gap in Proposition 3.3 is the main obstacle to acceptance. The empirical sections are strong and likely sufficient for a major-revision route. I would encourage the authors to either supply the missing marginal-to-overlap reduction or weaken the abstract and introduction to state the result as conditional on Conjecture B.13 and an additional unproven reduction. The paper's empirical core—especially the Sudoku, Zebra, and easy-to-hard results—does not depend on that reduction and should survive a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this paper has a genuinely useful empirical finding and a theory section that overstates its case. The adaptive inference oracle — top probability margin — turns a 6M MDM from 6.88% to 89.49% on their Sudoku test set, beating a 42M ARM trained with teacher-forced ordering (87.18%). That's a clean, training-free win and a meaningful baseline comparison. The Zebra results (98.3% vs 76.9%) and the easy-to-hard generalization (49.88% vs 32.57%) make the empirical core internally consistent. The paper also reframes MDM inference as an ordering problem and shows the ordering can be selected from the model's own confidence. The new top probability margin heuristic is simple and works where top probability fails because it distinguishes \"confident between two values\" from \"confident about one value.\" I'd cite that part.\n\nThe soft spots are mostly in the theory. Proposition 3.3 says a constant fraction of masking subproblems are \"computationally intractable\" under the 1RSB cavity prediction, but the reduction in Appendix B.4 only connects the masking problem to planted CSP inference for recovering the full assignment. Conjecture B.13 is about overlap for full recovery; it doesn't say anything about predicting a single masked token's value or its Bayes marginal, which is what the MDM actually does at inference. The paper needs an additional reduction from single-token prediction back to full recovery, or it should soften the claim. As written, the abstract's \"provably\" is not supported. The SLPN-based example in Appendix B.1 has a similar gap, though the reduction there is more plausible.\n\nReproducibility is also thin: no code, no seeds, no error bars. The Gumbel coefficient (0.5) and the temperature/noise in the text oracle are not ablated. And there's a small internal inconsistency: Figure 3 says a 170M MDM for the GenPPL experiment, Appendix D.1.2 says 1.1B. The LLaDA-8B gains are real but modest — a few points on HumanEval and Math, flat on MMLU and ROCStories. That doesn't undercut the Sudoku story, but the abstract's tone oversells the breadth.\n\nNet: the empirical core is solid enough to deserve a serious referee. I'd send it to review with a request to fix the theoretical claims and release the artifacts. The practical finding will be useful to anyone working on discrete diffusion inference.","headline":"Sudoku adaptive-inference result is the real contribution; the computational-hardness claims are overstated and need a missing step.","tokens_in":25997,"tokens_out":3785,"would_cite":true,"duration_ms":32236,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["masked diffusion models","autoregressive models","adaptive inference","token ordering","computational hardness","planted constraint satisfaction problems","Sudoku","discrete diffusion"],"falsifier":"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.","tokens_in":24996,"feed_emoji":"🧩","tokens_out":11389,"duration_ms":88934,"temperature":0.7,"pith_summary":"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.","feed_headline":"Adaptive decoding lifts masked-diffusion Sudoku from 7% to 90%","feed_subtitle":"Revealing the most confident tokens first lets a 6M masked diffusion model beat a 42M ordered autoregressive baseline.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the proposition used to rewrite the MDM loss as an average over all masking subproblems.","marker":"Zheng et al., 2024"},{"why":"Defines the masked diffusion training objective and score-entropy loss that the paper builds on.","marker":"Sahoo et al., 2025"},{"why":"Provides the simplified masked diffusion / absorbing-state framework used for the forward and reverse processes.","marker":"Shi et al., 2024"},{"why":"Supplies the planted-CSP thresholds and belief-propagation analysis underlying Proposition 3.3.","marker":"Krzakala & Zdeborová, 2009"},{"why":"Supplies the stable-algorithm hardness for the symmetric perceptron that Appendix B.2 translates to masking hardness.","marker":"Alaoui & Gamarnik, 2024"},{"why":"States the Sparse Learning Parity with Noise assumption used in Appendix B.1 for parity-observation hardness.","marker":"Alekhnovich, 2003"},{"why":"Provides the Sudoku and Zebra datasets and the order-aware ARM baseline that adaptive MDM is compared against.","marker":"Shah et al., 2024"},{"why":"Provides the MDM training and inference codebase and earlier Sudoku results that the paper re-runs and surpasses.","marker":"Ye et al., 2024"},{"why":"Releases LLaDA 8B, the masked diffusion model used for the coding and math evaluations.","marker":"Nie et al., 2025"},{"why":"Supplies the scaling-law baselines and codebase for the pi-learner text experiments.","marker":"Nie et al., 2024"}],"fun_headline_variants":["Confidence-first decoding: MDM Sudoku 7% → 90%","Adaptive unmasking order lifts MDM to 90% Sudoku","Masked diffusion beats 7x larger auto-regressive on Sudoku","Smart token order turns 7% MDM into 90% Sudoku solver"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Confidence-first decoding: MDM Sudoku 7% → 90%","Adaptive unmasking order lifts MDM to 90% Sudoku","Masked diffusion beats 7x larger auto-regressive on Sudoku","Smart token order turns 7% MDM into 90% Sudoku solver"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000206,"raw_usage":{"total_tokens":1455,"prompt_tokens":1060,"completion_tokens":395,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":676,"completion_tokens_details":{"reasoning_tokens":312}},"tokens_in":676,"tokens_out":395,"duration_ms":3990,"temperature":1.0,"reasoning_tokens":312,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T14:24:00.225582+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}