{"id":"6e75839e-1966-45a9-9f42-9f08e1306ae2","arxiv_id":"2604.08564","paper_version":2,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":5.5,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Sampling diffusion LMs by descending attention column sums optimally approximates NP-hard log-likelihood maximization and yields a training-free Attn-Sampler with better quality and parallelism.","lead":"The paper claims that for diffusion language models, sampling tokens in descending order of attention-matrix column sums optimally approximates log-likelihood maximization. It introduces Attn-Sampler, a training-free algorithm that uses this rule plus dynamic thresholds to improve generation quality and parallelism.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"Abstract-only review leaves the NP-hard-to-tractable reduction and the optimality proof for attention column sums unverified; without those, the central claim that ranking by column sums improves likelihood remains an uncheckable assertion.","rationale":"The Reader already isolates the critical soft spot: the sampling-rank approximation may not stay tight enough for real attention patterns, and no quantitative bound is supplied. My concern is essentially the same gap viewed one step earlier—the entire reduction and optimality proof are inaccessible in an abstract-only setting—so the verdict remains CONDITIONAL with low confidence. No new objection is manufactured; the concrete test simply operationalizes the verification the Reader already requires. Once the proofs and experiments are visible, the same check will either confirm the claim or expose a concrete flaw in the ranking argument.","tokens_in":1991,"tokens_out":459,"duration_ms":4886,"concrete_test":"Obtain the full paper (or arXiv source) and independently re-derive the claimed optimality result: start from the stated sampling-rank objective, verify that it is optimized by sorting attention column sums, and check whether any hidden assumptions (e.g., positive attentions, fixed mask structure, independence of future tokens) are required. If the derivation fails or requires extra conditions not satisfied by pretrained dLLMs, the central justification collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim rests on two linked steps that the abstract only asserts: (1) an optimal sampling-rank approximation that renders the NP-hard log-likelihood objective tractable, and (2) a proof that this tractable objective is maximized exactly by ordering tokens according to descending attention-matrix column sums. Because the full text is unavailable, neither the definition of the sampling-rank objective, the approximation argument, nor the optimality proof can be inspected. Consequently it is impossible to confirm that the attention-column-sum ranking is optimal for the stated objective, that the approximation remains tight under real dLLM attention patterns, or that the claimed quality/parallelism gains follow from the theory rather than from an incidental heuristic. The reader correctly flags the missing quantitative bound; the deeper load-bearing gap is that the entire theoretical chain is currently opaque.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The manuscript studies the sampling-order selection problem for diffusion-based large language models (dLLMs) from the standpoint of log-likelihood maximization. It asserts that exact order selection is NP-hard, introduces a sampling-rank approximation that renders the objective tractable, and claims a proof that this tractable objective is optimized by ordering tokens in descending order of attention-matrix column sums. The authors instantiate the result as a training-free algorithm (Attn-Sampler), add dynamic attention thresholding for acceleration, and report that the method improves generation quality while increasing sampling parallelism across multiple benchmarks.","tokens_in":2191,"tokens_out":744,"duration_ms":14589,"significance":"If the NP-hardness reduction, the sampling-rank approximation, and the optimality proof for attention column sums are correct and the approximation remains tight on real pretrained dLLMs, the work would supply a theoretically grounded, training-free alternative to greedy or purely token-level sampling schedules. That would be a useful contribution to inference for diffusion language models, linking an internal model quantity (attention column sums) to a likelihood-motivated objective and offering both quality and parallelism gains. The abstract also advertises a training-free algorithm and empirical validation, which, if substantiated, would make the result immediately usable.","major_comments":[{"comment":"The central theoretical chain—NP-hardness of order selection, definition and optimality of the sampling-rank approximation, and the claim that descending attention-matrix column sums exactly optimize the tractable objective—is only asserted in the abstract. No problem statement, reduction, approximation gap, or proof sketch is available for inspection. Without those, it is impossible to verify that the ranking is optimal for the stated objective or that the approximation remains faithful under real dLLM attention patterns (the load-bearing assumption for the quality claims).","section":null},{"comment":"The abstract asserts that Attn-Sampler yields superior generation quality and enhanced sampling parallelism, but supplies no quantitative results, baselines, ablations, or approximation-error measurements. The practical claim that ranking by column sums improves likelihood (rather than merely reordering noise) therefore cannot be assessed from the available text.","section":null},{"comment":"Dynamic attention thresholding is introduced as a practical acceleration device, yet the abstract does not state how the threshold interacts with the optimality argument for column-sum ranking, nor whether the acceleration preserves the claimed likelihood ordering. This interaction is load-bearing if the method is to be presented as theoretically justified rather than heuristic.","section":null}],"minor_comments":[{"comment":"The abstract uses both “dLLMs” and “diffusion language models” without a single expanded definition on first use; a consistent expansion would improve clarity.","section":null},{"comment":"Phrases such as “optimal sampling-rank-based approximation” and “principled justification” would be more informative if the abstract briefly indicated the approximation criterion (e.g., rank constraint, error measure) rather than only naming the device.","section":null}],"recommendation":"uncertain","confidential_remarks":"Only the abstract was available for this review; the full manuscript (proofs, algorithm details, tables) was not provided. Under those conditions a definitive accept/reject decision is not possible. If the full paper is supplied and the theoretical chain plus quantitative results hold up, the contribution looks potentially suitable for the venue; if the approximation gap is large or the experiments are weak, major revision or rejection would follow. I recommend obtaining the full text before any editorial decision."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing you need to know is that this is an abstract-only claim about a training-free sampler for diffusion LMs. They cast sampling-order selection as log-likelihood maximization, assert it is NP-hard, give a tractable rank approximation, and claim that ranking tokens by attention-matrix column sums optimally solves that approximation. Attn-Sampler is the resulting algorithm, plus a dynamic threshold for more parallelism. If the proofs and numbers hold, it is a clean inference-time win inside the dLLM subfield.\n\nWhat looks new and useful is the framing: not just another confidence or attention heuristic, but an explicit reduction from likelihood to a rank objective whose optimum is the column-sum order. That is a better justification than most attention-guided decoding papers offer. The method is training-free, reuses quantities the model already computes, and claims both quality and parallelism gains. No free parameters or invented entities jump out of the abstract; the circularity burden looks low because attention is internal, not fitted to the eval metrics.\n\nThe soft spots are exactly the ones the stress-test flags, and they are load-bearing. We cannot inspect the definition of the sampling-rank objective, the approximation gap, or the optimality proof. Without those, “column sums maximize the tractable objective” is an assertion, not a result we can verify. The further claim that the approximation stays tight under real dLLM attention patterns is also uncheckable from the abstract alone. Experiments are said to be extensive and positive, but there are no numbers, ablations, or baselines here. So soundness has to stay provisional.\n\nThis is for people already working on non-AR / diffusion language models who care about sampling order and inference efficiency. A serious referee should see the full paper: the theoretical chain is the kind of thing that either lands cleanly or falls apart under inspection, and the training-free angle makes it worth that look. I would not cite or bring it to reading group on the abstract alone, but I would accept it for peer review rather than desk-reject. Send it out; the proofs and tables will decide.","headline":"Abstract-only: promising theory-to-sampler story for dLLM order selection, but the NP-hardness reduction and attention-column optimality proof are currently uncheckable assertions.","tokens_in":2783,"tokens_out":532,"would_cite":false,"duration_ms":5782,"reading_group":"no","serious_thinker":"unclear","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Diffusion language models generate better text by sampling tokens in descending order of attention-matrix column sums, a ranking that optimally approximates NP-hard log-likelihood maximization and raises both quality and parallelism without","keywords":["diffusion language models","sampling order","attention matrix","log-likelihood maximization","parallel decoding","training-free inference","NP-hard approximation"],"falsifier":"On a fixed pretrained dLLM and benchmark suite, replace Attn-Sampler with a random or reverse-attention ranking of the same tokens and measure whether log-likelihood and generation quality drop; if they do not drop, the claimed optimality of attention column sums fails.","tokens_in":2881,"feed_emoji":"⚡","tokens_out":724,"duration_ms":6888,"temperature":0.7,"pith_summary":"Current diffusion language models can sample tokens in parallel rather than left-to-right, but existing strategies decide the order using only local token scores and therefore ignore global sequence structure. This paper frames the choice of sampling order as a log-likelihood maximization problem, proves the exact problem is NP-hard, and derives a tractable sampling-rank surrogate that can be optimized efficiently. The authors then prove that the surrogate is maximized by ranking tokens according to the column sums of the model’s own attention matrix, giving a clean, training-free rule called Attn-Sampler. Dynamic attention thresholding further accelerates the procedure by skipping low-impact tokens. Experiments on standard generation benchmarks show higher quality scores together with greater sampling parallelism, establishing attention-guided ranking as a practical and theoretically justified replacement for greedy search.","feed_headline":"Sample tokens by attention column sums for better dLLMs","feed_subtitle":"A training-free ranking that optimally approximates NP-hard likelihood and lifts quality plus parallelism","key_machinery":"The sampling-rank objective: a computationally tractable surrogate for the NP-hard log-likelihood maximization problem whose unique maximizer is the ranking of tokens by their attention-matrix column sums; Attn-Sampler simply materializes this ranking (with an optional dynamic attention threshold for speed).","core_discovery":"The NP-hard problem of choosing a token sampling order that maximizes sequence log-likelihood under a diffusion language model admits a tractable sampling-rank approximation whose optimum is exactly the descending order of attention-matrix column sums; the resulting Attn-Sampler therefore improves generation quality while increasing parallelism, all without additional training.","pith_inferences":["The same column-sum ranking may transfer to other non-autoregressive or masked language models that already expose attention matrices.","If the approximation gap can be bounded, the method could be turned into a certified improvement guarantee rather than an empirical heuristic.","Attention-column statistics might also serve as a cheap proxy for uncertainty or importance sampling in other generative pipelines."],"forward_implications":["Sampling order can be decided solely from the model’s own attention matrix without any extra training or auxiliary network.","Generation quality and parallelism improve simultaneously rather than trading off against each other.","Dynamic attention thresholding can prune low-impact tokens at runtime, further reducing wall-clock sampling cost.","Greedy token-level search is no longer the default; attention-guided ranking supplies a theoretically preferred alternative."],"fun_headline_variants":["Order dLLM tokens by descending attention column sums","Attention column sums optimize tractable dLLM sampling ranks","Attn-Sampler ranks by attention for quality and parallelism","Sample via attention-matrix column sums in diffusion LMs","Attention-guided order approximates max dLLM log-likelihood"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"That the sampling-rank approximation stays tight enough under the attention patterns of real pretrained diffusion language models for column-sum ranking to raise true likelihood and quality rather than merely reordering noise.","fun_headline_variants_meta":{"raw":{"variants":["Order dLLM tokens by descending attention column sums","Attention column sums optimize tractable dLLM sampling ranks","Attn-Sampler ranks by attention for quality and parallelism","Sample via attention-matrix column sums in diffusion LMs","Attention-guided order approximates max dLLM log-likelihood"]},"model":"grok-4.5","effort":"low","cost_usd":0.004518,"raw_usage":{"total_tokens":1317,"prompt_tokens":750,"num_sources_used":0,"completion_tokens":61,"cost_in_usd_ticks":45180000,"prompt_tokens_details":{"text_tokens":750,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":506,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":750,"tokens_out":61,"duration_ms":6165,"temperature":1.0,"reasoning_tokens":506,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T23:08:52.534166+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On a fixed pretrained dLLM and benchmark suite, replace Attn-Sampler with a random or reverse-attention ranking of the same tokens and measure whether log-likelihood and generation quality drop; if they do not drop, the claimed optimality of attention column sums fails.","supporting_citations":[],"review_version":2}