{"id":"4cac91f0-af1e-4929-a199-5240d4d6e940","arxiv_id":"2505.24857","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"EB-Sampler dynamically unmasks multiple low-entropy tokens per function evaluation, accelerating masked diffusion model sampling by 2-3x with negligible accuracy loss.","lead":"A new sampling algorithm for masked diffusion models decides how many tokens to unmask per step based on an entropy bound, speeding up generation by roughly 2-3x on coding and math benchmarks without losing accuracy. The method is a drop-in replacement for existing samplers and needs no retraining.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equation 8's bound is on data entropies H(q), but EB-Sampler's stopping rule (Eq. 2) uses model entropies H(pθ); without a calibration argument, the advertised 'predefined approximate error tolerance' is unsupported.","rationale":"The central claim is an empirical acceleration claim, and the paper provides consistent Pareto-front evidence across two large MDMs and two controlled tasks; that evidence is real and supports the practical value of EB-Sampler. However, the theoretical apparatus in Section 5 is the only mechanism offered to explain why unmasking multiple tokens does not degrade accuracy, and that mechanism relies on Eq. 8, a bound on data entropies, while the implementation (Eq. 2 and Algorithm 1) uses model entropies. The authors explicitly acknowledge the approximation in words ('approximately bounds', 'Assume we can identify low model error tokens'), but the abstract's phrase 'with predefined approximate error tolerance' overstates what is established. This is the weakest load-bearing step: if model entropy is not a reliable surrogate for data entropy, the safety property that justifies 'entropy bounded' unmasking is not guaranteed, and the method's success on these benchmarks could be model- and task-specific rather than a consequence of the stated bound. The reader's weakest_assumption identifies exactly this substitution, and I agree. The concern is addressable via calibration analysis or a controlled empirical check on tasks with known q, so it does not warrant rejection; the conditional verdict is appropriate and unchanged.","tokens_in":18913,"tokens_out":11873,"duration_ms":135323,"concrete_test":"Use the controlled Sudoku and maze setups where the data distribution q is known from the generator. For each EB-Sampler step, compute exact or high-sample Monte Carlo estimates of the true joint dependence DKL(q(x_U|x_c), ∏_{l∈U} q(x_l|x_c)) for the selected set U, and compare with Σ_{l∈U} H(pθ(x_l|x_c)) − max_{l∈U} H(pθ(x_l|x_c)). If the proxy criterion exceeds the true error by more than a small slack on a meaningful fraction of steps, Eq. 9 fails as a bound; if the two track closely, the concern is resolved. Repeat with randomly chosen U to control for selection effects.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The error decomposition in Section 5 is internally consistent: DKL(q(x_zi|x_{z<i}), ∏_{l∈z_i} q(x_l|x_{z<i})) ≤ Σ_l H(q(x_l|x_{z<i})) − max_l H(q(x_l|x_{z<i})) (Eq. 8). But the algorithm replaces q by pθ in both the entropy values and the error-proxy ordering, yielding Eq. 9 / Eq. 2. The substitution is valid only where pθ(x_l|x_{z<i}) ≈ q(x_l|x_{z<i}); the paper assumes 'we can identify low model error tokens' but never measures this, and no calibration or consistency check is provided. Because joint dependence error is a property of q, an overconfident pθ with H(pθ) << H(q) can make the criterion accept a set U whose true data-dependence error is much larger than γ; the bound then provides no predefined error tolerance, and the 'without loss in performance' finding is not explained by the theory. This is the load-bearing step: if the entropy proxy is miscalibrated on a new task or model, EB-Sampler degrades to a heuristic adaptive-k rule with no safety margin. The paper's empirical Pareto-front evidence mitigates but does not remove the gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces EB-Sampler, a drop-in replacement for the sampling procedures used with masked diffusion models (MDMs). At each function evaluation, EB-Sampler sorts the currently masked tokens by an error proxy (model confidence, entropy, or margin), then unmasks a prefix of that sorted list whose cumulative model-prediction entropies satisfy sum(U) - max(U) <= gamma, so that the number of tokens unmasked per step varies adaptively. The authors provide a KL error decomposition (Section 5, Appendix A.1) that splits the discrepancy between the sampler's distribution and the data distribution into a model error term and a joint dependence error term, and they upper-bound the latter by sum-minus-max of data entropies. They then motivate the entropy stopping rule by replacing data entropies with model entropies under an explicit approximation assumption. Empirically, on LLaDa 8B and Dream 7B, EB-Sampler improves the accuracy-versus-NFE Pareto frontier on HumanEval, MBPP, GSM8K, and MATH, reporting 2-3x speed-ups at matched accuracy, and shows similar advantages on small maze and Sudoku models. The paper also discusses measurement subtleties in MDM efficiency, introducing a generate_until logic and semi-autoregressive ablations to avoid overstating gains.","tokens_in":19116,"tokens_out":5949,"duration_ms":70130,"significance":"If the empirical results hold, this is a practically valuable contribution: it offers a simple, training-free way to speed up sampling from existing large masked diffusion models, with code-level clarity and honest efficiency measurements. The theoretical error decomposition is clean and self-contained, and the connection between the bound and the algorithm is clearly laid out, even where it relies on assumptions. The paper is commendably careful about efficiency evaluation, including the generate_until post-process and semi-autoregressive ablations, and it makes the implementation change explicit in a short PyTorch snippet. The main caveat is that the rigorous bound (8) uses data entropies while the implemented rule (2) uses model entropies, with no calibration evidence; this weakens the advertised 'predefined approximate error tolerance' but does not invalidate the empirical Pareto-front findings.","major_comments":[{"comment":"The rigorous joint dependence bound in Eq. (8) is stated in terms of data entropies H(q(x_l | x_{z<i})), but the EB-Sampler stopping rule in Eq. (2) uses model entropies H(p_theta(x_l | x_{z<i})). The only justification is the sentence in Section 5, 'Assume we can identify low model error tokens and we design phi to only select z_i from such tokens, where for all l in z_i, p_theta(...) ≈ q(...).' No calibration or consistency check is provided. If the model is overconfident, model entropy can be much smaller than data entropy, so the selected set U may have true joint dependence error well above gamma. Consequently, the abstract's claim of a 'predefined approximate error tolerance' and the phrase in Section 4 that Eq. (2) 'approximately bounds a rigorous joint dependence error' are not substantiated by the theory as written. Please either add an empirical calibration study (e.g., comparing model and data entropies on a held-out set, and/or measuring the actual joint dependence error of EB-Sampler-selected subsets) or soften the claims to describe gamma as a tuned hyperparameter with empirical justification.","section":"Section 4, Eq. (2) and Section 5, Eqs. (8)-(9)"},{"comment":"The theoretical motivation rests on the assumption that the error proxies (entropy, confidence, margin) identify low-model-error tokens, but the paper never directly measures model error (e.g., D_KL(q(x_l | x_{z<i}), p_theta(x_l | x_{z<i}))) or verifies that the proxy ordering correlates with it. Figures 2 and 3 show downstream accuracy improvements from these proxies, which is suggestive but not the same as validating the assumption. As a result, the reader cannot tell from the paper whether the observed gains come from the entropy bound per se or from the adaptive-k heuristic that unmask more tokens when the model is confident. A direct test of the bound's components, or at least a discussion of this gap, would strengthen the claim that the theory 'motivates' the algorithmic choices.","section":"Section 5, 'Expressiveness of phi' and Eq. (7)"}],"minor_comments":[{"comment":"The sentence 'This second KL divergence is precisely joint mutual information' is technically imprecise for subsets of more than two tokens: the divergence between a joint distribution and the product of its marginals is total correlation (multi-information), not mutual information. The mathematical content is unaffected, but the terminology should be corrected.","section":"Section 5, after Eq. (7)"},{"comment":"The text states that 'gamma = 0 will unmask one token each step,' but the condition sum(U) - max(U) <= 0 also permits multiple tokens with zero model entropy (e.g., deterministic predictions under zero-temperature sampling) to be unmasked in one step. The statement is therefore not strictly accurate and could be clarified.","section":"Section 4, paragraph after Eq. (2)"},{"comment":"There is an incomplete sentence: 'the sum and expectation can be interchanged since the sum does not' breaks off mid-phrase. Please complete or rephrase.","section":"Appendix A.1, first paragraph"},{"comment":"The name 'Messionic' appears to be a typo for 'Meissonic' (the reference list entry uses 'Meissonic'). Please correct.","section":"Related Work, Section 7"}],"recommendation":"major_revision","confidential_remarks":"The paper is fundamentally sound in its empirical core and its KL decomposition is correct, but the gap between the data-entropy bound and the model-entropy implementation is a load-bearing point for the theoretical claims. The authors are already fairly honest about the approximation assumption, so I believe a revision that either adds calibration evidence or carefully rewords the 'error tolerance' claim could bring this to an acceptable level. The empirical evaluation appears carefully done, including the generate_until and semi-AR ablations, which speaks well of the authors' scientific integrity."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper for one idea: instead of unmasking a fixed number of tokens per step, EB-Sampler sorts tokens by a model-error proxy (entropy, confidence, margin) and then unmasks the longest prefix whose entropy sum minus the max entropy stays below a threshold gamma. That is a legitimate new contribution, and it is a 10-line change to any existing Top-k sampler. The paper places this in a clean framework of adaptive unmasking samplers and derives a KL error decomposition into model error and joint dependence error, where Eq. (8) upper-bounds the joint dependence term by the entropy sum-minus-max. That theory is internally consistent and is not circular; it motivates the algorithm rather than proving a formal guarantee for it.\n\nWhat the paper does especially well is the evaluation. The authors test on two large open MDMs (LLaDa 8B, Dream 7B) across four benchmarks, provide Pareto fronts, and are unusually honest about measurement pitfalls. They introduce generate_until logic, discuss the bias in NFE counting, add a semi-autoregressive baseline, and explicitly refrain from claiming the 6x speed-up that naive counting would give. The consistent Pareto improvement across models and tasks is real evidence that the heuristic works. The maze and Sudoku experiments are smaller but the trend is the same.\n\nThe soft spots are in proportion. The main one is the gap between the theoretical bound and the implementation: Eq. (8) bounds joint dependence using true data entropies H(q), but the stopping rule uses model entropies H(p_theta). The paper says the substitution is valid when p_theta is close to q for selected tokens, and the error-proxy sorting is meant to select such tokens, but there is no calibration or consistency check. So the `predefined approximate error tolerance` in the abstract is stronger than what the theory actually delivers; in a new model or task, the entropy proxy could be miscalibrated. This is a legitimate concern, but it is a bridgeable one, and the empirical evidence does not depend solely on the theory. Other minor issues: gamma is per-task tuned, no code is released, and no error bars or seed variance are reported. The LLaDa MBPP speed-ups under semi-AR are closer to 1.2-2.2x than the advertised 2-3x, so the headline number is somewhat model- and task-dependent, though the paper is transparent about that in Table 1.\n\nOverall, the core contribution is solid and the honesty of the evaluation is a credit. The theoretical gap is worth pushing on, but it is not a load-bearing flaw. This paper deserves a serious referee.\n\nRecommendation: send to peer review, and ask for code release and a calibration/ablation analysis for the entropy substitution as part of the revision. I would cite it if I work on MDM sampling.","headline":"A simple, well-motivated adaptive multi-token unmasking rule for masked diffusion models, with honest experiments and a real but bridgeable gap between the theory and the implementation.","tokens_in":19733,"tokens_out":1848,"would_cite":true,"duration_ms":21833,"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":"Entropy-bounded unmasking speeds masked diffusion sampling 2-3x","keywords":["masked diffusion models","efficient sampling","entropy-bounded unmasking","adaptive multi-token sampling","joint dependence error","non-autoregressive generation","code and math reasoning"],"falsifier":"On a held-out corpus, estimate the true joint dependence term $D_{\\mathrm{KL}}(q(x_U \\mid x_{z_{<i}}) \\,\\|\\, \\prod_{l\\in U} q(x_l \\mid x_{z_{<i}}))$ for the subsets $U$ that EB-Sampler actually selects, and compare it with the entropy expression computed from model entropies; if the model-entropy expression frequently underestimates the true term, or if the selected subsets show large true dependence at matched accuracy, the central acceleration claim fails.","tokens_in":18628,"feed_emoji":"⚡","tokens_out":7073,"duration_ms":73018,"temperature":0.7,"pith_summary":"EB-Sampler is a drop-in replacement for the standard sampling loop of masked diffusion models. It observes that one forward pass of the model often contains reliable predictions for several masked tokens at once, and it unmasks a variable number of tokens per step, stopping when the sum of the chosen tokens' entropies minus the largest entropy exceeds a threshold $\\gamma$. The paper claims this entropy bound approximately controls the joint dependence error of sampling tokens independently, and that the resulting sampler sits on a better accuracy-versus-compute Pareto frontier than fixed Top-k samplers. On the LLaDa 8B and Dream 7B models it reports 2-3x fewer function evaluations on code and math reasoning benchmarks without loss in pass@1 accuracy, and similar gains on maze and Sudoku tasks.","feed_headline":"Entropy bound unlocks 2-3x faster masked diffusion sampling","feed_subtitle":"New sampler unmasks several tokens per model pass with no measured loss on code and math benchmarks.","key_machinery":"The load-bearing mechanism is the entropy-bound criterion of Equation (2): unmask the largest subset $U$ of masked tokens sorted by error proxy such that $\\sum_{l\\in U} H(p_\\theta(x_l \\mid x_{z_{<i}})) - \\max_{l\\in U} H(p_\\theta(x_l \\mid x_{z_{<i}})) \\leq \\gamma$. This expression approximates a rigorous upper bound on the joint dependence error $D_{\\mathrm{KL}}(q(x_U \\mid x_{z_{<i}}) \\,\\|\\, \\prod_{l\\in U} q(x_l \\mid x_{z_{<i}}))$, replacing true data entropies with model entropies. The bound decides both which tokens are unmasked (low error-proxy first) and how many tokens are unmasked at once, making the step count adaptive to how predictable the remaining sequence is.","core_discovery":"The central claim is that a single function evaluation of a masked diffusion model carries enough information to determine several tokens at once, provided those tokens are highly predictable, and that a sampler can exploit this by unmasking multiple tokens per step subject to an entropy bound. The paper formalizes sampling as an ordered partition generated by an adaptive policy $\\varphi$, and decomposes the KL divergence between the sampler's distribution and the true data distribution into a model-error term and a joint dependence error term. It then shows the joint dependence error is upper-bounded by the sum of the data entropies of the selected tokens minus their maximum, which in practice is approximated by model entropies. EB-Sampler applies this by sorting masked tokens by a model-error proxy (confidence, entropy, or margin) and unmasking the longest prefix whose cumulative entropy minus the running maximum stays below $\\gamma$. The paper reports that this accelerates LLaDa 8B and Dream 7B by roughly 2-3x on standard code and math reasoning benchmarks at matched accuracy.","pith_inferences":["If model entropies are reasonably calibrated, EB-Sampler's adaptive step count can double as a difficulty signal: easy continuations decode in few evaluations and hard ones in many, which could guide early stopping or test-time compute allocation.","The same entropy-bounded selection criterion should transfer to other structured discrete generation tasks, such as protein or molecule design, wherever a model outputs factorized conditionals; the paper's maze and Sudoku results are initial evidence.","EB-Sampler is complementary to speculative decoding schemes: it could be used to speed up the draft model, since the paper's sampling loop does not change the underlying distribution of the target model.","A stronger theoretical variant would replace model entropies with calibrated uncertainty estimates or a learned proxy for true joint dependence, tightening the bound without altering the algorithm."],"forward_implications":["Any pre-trained masked diffusion model can adopt EB-Sampler without retraining, since the change is confined to the sampling loop.","At matched pass@1 accuracy, EB-Sampler needs roughly 2-3x fewer function evaluations than one-token-per-step sampling on HumanEval, MBPP, GSM8K, and MATH.","At matched function-evaluation budgets, EB-Sampler achieves higher accuracy than fixed Top-k samplers, improving the accuracy-NFE Pareto frontier.","On maze navigation and Sudoku, EB-Sampler retains near-full accuracy at around 10-15 function evaluations where fixed Top-k samplers degrade.","The KL decomposition implies that any adaptive unmasking policy's error is the sum of model error and joint dependence error, giving a principled target for future sampler design."],"supporting_citations":[{"why":"Supplies LLaDa 8B, the large masked diffusion model whose sampling EB-Sampler accelerates.","marker":"Nie et al., 2025b"},{"why":"Supplies Dream 7B, the second large masked diffusion model evaluated on coding and math benchmarks.","marker":"Ye et al., 2025"},{"why":"Establishes that masked diffusion models learn the clean-data conditionals q(x_l | x_{\\bar M}), the premise for using p_theta as an error proxy.","marker":"Ou et al., 2025"},{"why":"Supplies the ELBO inequality used to decompose sampling error into model error and joint dependence error.","marker":"Kingma and Welling, 2019"},{"why":"Supplies the confidence-based greedy unmasking criterion that EB-Sampler reuses as one error proxy.","marker":"Chang et al., 2022"},{"why":"Provides analysis of token ordering in masked diffusion, motivating the error-proxy ordering step.","marker":"Kim et al., 2025"},{"why":"Supplies the semi-autoregressive block generation scheme used as a baseline for measuring efficiency gains.","marker":"Arriola et al., 2025"},{"why":"Supplies the HumanEval benchmark used to measure pass@1 accuracy versus function evaluations.","marker":"Chen et al., 2021"}],"fun_headline_variants":["Entropy-bound unmasking gives 2-3x faster MDM sampling","EB-Sampler: multi-token unmasking for 2-3x speedup","Faster masked diffusion via entropy-bounded multi-token unmask","Adaptive unmasking policy speeds MDMs 2-3x without loss","Entropy bound enables simultaneous unmasking for 2-3x speed"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the model's predicted entropy and error-proxy scores are reliable stand-ins for true data uncertainty and true model error; if they are miscalibrated, the entropy bound no longer bounds the real joint dependence error and the speedups rest on an empirical heuristic.","fun_headline_variants_meta":{"raw":{"variants":["Entropy-bound unmasking gives 2-3x faster MDM sampling","EB-Sampler: multi-token unmasking for 2-3x speedup","Faster masked diffusion via entropy-bounded multi-token unmask","Adaptive unmasking policy speeds MDMs 2-3x without loss","Entropy bound enables simultaneous unmasking for 2-3x speed"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000364,"raw_usage":{"total_tokens":1963,"prompt_tokens":951,"completion_tokens":1012,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":567,"completion_tokens_details":{"reasoning_tokens":911}},"tokens_in":567,"tokens_out":1012,"duration_ms":11384,"temperature":1.0,"reasoning_tokens":911,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:11:36.662975+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a held-out corpus, estimate the true joint dependence term $D_{\\mathrm{KL}}(q(x_U \\mid x_{z_{<i}}) \\,\\|\\, \\prod_{l\\in U} q(x_l \\mid x_{z_{<i}}))$ for the subsets $U$ that EB-Sampler actually selects, and compare it with the entropy expression computed from model entropies; if the model-entropy expression frequently underestimates the true term, or if the selected subsets show large true dependence at matched accuracy, the central acceleration claim fails.","supporting_citations":[{"cited_title":"Block diffusion: Interpolating between autoregressive and diffusion language models","cited_arxiv_id":null,"evidence_quote":"Supplies the semi-autoregressive block generation scheme used as a baseline for measuring efficiency gains."}],"review_version":1}