{"id":"c129a345-9b6c-477d-a43d-cc0763743d8d","arxiv_id":"2508.10111","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A decoding algorithm that keeps diffusion LLM outputs inside a context-free grammar by turning constrained decoding into an infilling problem and then into a classical grammar-and-pattern emptiness check.","lead":"Researchers built the first constrained decoding method for diffusion large language models, forcing their outputs to obey grammar rules for languages like C++ and JSON. If it works, diffusion-based code generators can produce syntactically valid output without losing functional quality.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The syntactic mask is exact for CFGs, but neither exactness nor the abstract's 'near-perfect' wording establishes the empirical claim that constrained decoding preserves or improves functional correctness, especially for an approximated C++ grammar.","rationale":"The reader's weakest_assumption already foregrounds functional-correctness preservation and the C++ CFG approximation. I agree those are the load-bearing empirical premises, but I would sharpen the concern: the formal emptiness reduction does not, by itself, imply anything about functional correctness, and the shift from 'formally correct' to 'near-perfect' signals an unstated approximation. The algorithmic core of the paper is plausible and classically grounded; the issue is not the reduction's internal validity but the strength of the application-level claims. Since the reader already assigned CONDITIONAL with low confidence and no artifacts, my stress test does not move the verdict; it reinforces that the conditions are necessary. The concrete test is the direct way to resolve the functional-correctness premise, which is the most consequential unsupported claim.","tokens_in":39194,"tokens_out":5401,"duration_ms":76962,"concrete_test":"Run the implemented decoder on a C++ code-generation benchmark (e.g., HumanEval-C++ or MBPP) with hidden unit tests. Compare constrained-decoding pass@1 against the unconstrained baseline on executable correctness, and separately record the fraction of outputs that fail compilation. If constrained pass@1 drops significantly, the claim that constrained decoding consistently preserves or improves functional correctness fails. If pass@1 is not worse and compilation failures are near zero, the concern is answered.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim bundles a formal reduction (constrained decoding → additive infilling → CFL∩REG emptiness) with an empirical guarantee: 'near-perfect syntactic correctness while consistently preserving or improving functional correctness'. The reduction only certifies syntax, and only relative to the supplied context-free grammar. It does not certify that a hard per-step mask, which prunes every token whose partial completion would empty L∩R, preserves the diffusion model's conditional distribution. Such pruning can remove the model's high-probability, functionally correct completions whenever those completions first pass through a syntactically disfavored region. The paper's own hedge from 'formally correct' to 'near-perfect' is unexplained at the abstract level. A natural source of the gap is that production C++ is not genuinely context-free (preprocessor, template instantiation, name lookup), so any practical grammar is an approximation: an over-approximation admits invalid programs, an under-approximation rejects valid C++. Either way, 'formally correct C++' overstates what the emptiness-based mask can guarantee. Because the full text supplied here is too corrupted to verify how syntactic correctness and functional correctness were measured, the empirical half of the central claim remains unsecured.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a constrained decoding method for diffusion LLMs that enforces context-free-grammar (CFG) constraints during generation. The authors reduce constrained decoding to an 'additive infilling' problem—whether a partially generated output can be completed to a word of the target language—and then reduce that problem to deciding emptiness of the intersection of a context-free language and a regular language. They claim an efficient algorithm based on this reduction, and report experiments on C++ code infilling and JSON extraction showing near-perfect syntactic correctness with preserved or improved functional correctness and practical overhead.","tokens_in":39354,"tokens_out":5045,"duration_ms":60862,"significance":"If the reduction is correct, this is a valuable and elegant contribution: it gives a principled way to apply hard syntactic constraints to diffusion LLMs, whose parallel/generative structure prevents using the token-level masking techniques developed for autoregressive LLMs. The reduction to CFL∩REG emptiness is a standard, well-understood decision problem, and the ability to handle multi-region infilling within the same framework is a genuine plus. The formal syntax guarantee for any CFG would be significant for structured data extraction and code generation. However, the empirical claim about functional correctness is not entailed by the syntax-only reduction and is the main risk; the manuscript as provided does not allow verification of the experiments or the algorithmic details.","major_comments":[{"comment":"The reduction to additive infilling provides a syntactic oracle only: it answers whether a partial output can be completed to some word in L∩R. It does not answer whether the completion is the one the diffusion model would have produced, nor whether it is functionally correct. Masking out every token whose addition would empty the intersection renormalizes the plausible distribution and can delete the model's highest-probability functionally correct completion whenever that completion first passes through a syntactically disfavored region. The abstract's claim of 'consistently preserving or improving functional correctness' is therefore not a consequence of the reduction; it is a separate empirical premise that currently lacks support in the readable portions of the manuscript. The experiments should report functional metrics (e.g., compilation success, execution pass rate, JSON parse +","section":"Abstract, second paragraph; Additive Infilling reduction"},{"comment":"The paper repeatedly frames its C++ experiments as producing 'formally correct C++'. Production C++ is not a context-free language: preprocessor directives, template instantiation, name lookup, and overload resolution involve context-sensitive and semantic conditions. Any CFG used in practice is therefore an approximation: an over-approximation accepts invalid programs, while an under-approximation rejects valid ones. The paper must state which approximation is used and define 'formally correct C++' relative to that grammar, not relative to the C++ standard. The move in the abstract from 'formally correct C++' to 'near-perfect syntactic correctness' hints at this gap, but the gap is never explained or quantified. This affects how the headline claim should be interpreted.","section":"Abstract, first paragraph ('formally correct C++')"},{"comment":"The supplied manuscript text is heavily corrupted: most of the body, including algorithms, proofs, tables, and even section numbers, is unreadable mojibake. I could not verify the Bar-Hillel construction, the claimed complexity of the emptiness test, the incremental optimization, the grammar definitions, or the experimental protocol and numbers. This is a blocking condition for a journal submission. The authors should resubmit a complete, readable version; without it I cannot certify soundness of the algorithmic or empirical claims.","section":"Full text (as provided)"}],"minor_comments":[{"comment":"The term 'additive infilling' is introduced without a formal definition in the abstract. Please define it in the introduction and in the problem statement, since it is central to the reduction.","section":"Abstract"},{"comment":"The abstract states this is 'the first constrained decoding method for diffusion models.' The related-work section should verify this priority against recent diffusion LLM decoding and discrete diffusion constrained generation methods; the readable fragments do not allow this check.","section":"Related Work"},{"comment":"The abstract promises that computational overhead remains 'practical.' Please report the asymptotic and empirical per-step cost of the emptiness check, including the size of the constructed automaton and whether results are cached across decoding steps.","section":"Efficiency Optimizations"},{"comment":"The phrase 'near-perfect syntactic correctness' should be quantified: how many outputs are exact grammar members, what happens when the mask fails, and how are failures distributed between grammar approximation and model-tokenization issues?","section":"Experiments"}],"recommendation":"major_revision","confidential_remarks":"The core reduction is plausible and potentially publishable, but the current manuscript cannot be accepted in this state: the full text is unreadable, and the functional-correctness claim is conceptually under-supported. The authors should be invited to resubmit a readable version with clear experiments and a precise statement of what the syntactic guarantee does and does not imply."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I couldn't read the full text—what I received is garbled, mostly mojibake, with a header from a different arXiv ID—so my read rests on the abstract and a few legible fragments around the algorithm. That caveat shapes the verdict.\n\nThe genuinely new thing is the reduction: constrained decoding for diffusion LLMs to additive infilling, then to CFL∩REG emptiness, with multi-region infilling as a special case. That's a clean framing, and I don't know prior work doing it for diffusion models. The decision procedure itself is classical (Bar-Hillel, CYK), but the application and the subsumption of multi-region infilling are new. The fragments I could read are consistent with a CYK-style algorithm carrying per-step invariants, so the formal core is credible.\n\nThe soft spots are real but not fatal. The abstract moves from 'formally correct C++' to 'near-perfect' without explaining the gap. Production C++ isn't context-free; any CFG is an approximation. Over-approximation admits invalid programs, under-approximation rejects valid ones. So the syntax guarantee is only relative to the grammar, and 'formally correct C++' overstates what the mask can promise. Second, the claim that functional correctness is preserved or improved is empirical, not entailed by the reduction. A hard mask that prunes tokens when L∩R empties can remove the model's high-probability completion if that completion first passes through a syntactically disfavored region. The reduction doesn't rule that out. The abstract doesn't give enough detail to judge how syntax and functional correctness were measured, and I can't check baselines or overhead numbers from what I have.\n\nThese are addressable, not demonstrated, flaws. A competent group could reimplement the classical core, and if the full paper ships code and documents the CFG approximation, the central claim would likely hold. As it stands, I'd treat the empirical half as unsecured.","headline":"A fresh and plausible reduction for CFG-constrained decoding of diffusion LLMs, but the functional-correctness guarantee is empirical and not yet supported by the evidence I can see.","tokens_in":39928,"tokens_out":2809,"would_cite":true,"duration_ms":31933,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that constrained decoding for diffusion LLMs can be reduced to testing whether the intersection of a context-free language and a regular language is empty, yielding near-perfect syntactic correctness on C++ and JSON at pra","keywords":["constrained decoding","diffusion LLMs","context-free grammars","additive infilling","regular language intersection","C++ code generation","JSON extraction","syntactic correctness"],"falsifier":"Find a code-infilling prompt where the set of tokens that keep $L \\cap R$ nonempty excludes the only tokens appearing in every functionally correct completion, then run the proposed decoder and show the output compiles but fails functional unit tests while an unconstrained model succeeds.","tokens_in":38998,"feed_emoji":"🧩","tokens_out":4709,"duration_ms":58410,"temperature":0.7,"pith_summary":"This paper sets out to do for diffusion-based large language models what constrained decoding already does for autoregressive models: guarantee that generated tokens belong to a formal language. Its central claim is that this can be done for any language generated by a context-free grammar by reducing the problem to asking whether a partially filled output can still be completed, and then to asking whether the intersection of the target language with a regular language is empty. The paper reports that this emptiness test can be run efficiently enough to be practical, that it also covers the previously unaddressed case of filling several regions at once, and that experiments on C++ infilling and JSON extraction show near-perfect syntactic correctness while keeping or improving functional correctness. If the claim holds, diffusion LLMs become usable for code generation and structured data extraction with the same reliability guarantees that autoregressive decoders already enjoy.","feed_headline":"Diffusion LLMs can now emit valid C++ and JSON","feed_subtitle":"A CFG-regular emptiness check lets diffusion models fill code and JSON with near-perfect syntax.","key_machinery":"The central machinery is the additive infilling problem and its reduction to the emptiness of $L \\cap R$, where $L$ is the target context-free language and $R$ is the regular language of all completions of the partially filled output. Because the intersection of a context-free language and a regular language is itself context-free, emptiness is decidable, and this decidability becomes the per-step test that masks invalid tokens. The same emptiness primitive also handles multi-region infilling, since multiple holes can be encoded inside the regular language $R$.","core_discovery":"The paper presents the first constrained decoding method for diffusion LLMs that supports context-free grammars. It reduces constrained decoding to the additive infilling problem: given a partially generated output with holes, can it be completed to a word of the target language? It then reduces that problem to deciding whether the intersection of the target context-free language $L$ with a regular language $R$, which encodes all possible hole fillings, is empty. Since $L \\cap R$ is again context-free and emptiness for context-free grammars is decidable, the check can be run efficiently. The decoder uses this check to mask every token whose addition would make the intersection empty, guarant","pith_inferences":["The same emptiness-check primitive could be reused for beam search or lookahead guidance rather than greedy masking, which might avoid locally valid choices that commit to globally wrong programs.","The paper's C++ experiments rely on a context-free approximation of C++, so the strength of the syntactic guarantee is bounded by how faithfully that approximation captures real C++; a stricter grammar could change both syntax and functional results.","A natural testable extension is to apply the same reduction to other mildly structured output domains, such as typed data schemas or domain-specific languages, where the target language is already given by a context-free grammar.","The reduction suggests that any future improvement to context-free-regular intersection emptiness checking would directly improve this decoding method, independent of the diffusion model itself."],"forward_implications":["Diffusion LLMs can be constrained to any context-free language, not just regular templates, making grammar-conforming C++ and JSON generation achievable.","The additive infilling formulation naturally covers multi-region infilling, so several holes in a program or data record can be filled simultaneously under the same grammar constraint.","Masking tokens only when no valid completion exists yields near-perfect syntactic correctness, so the method can be used where malformed output is unacceptable.","The reported preservation or improvement of functional correctness means the grammar constraint does not come at the cost of what the model is trying to say.","The practical overhead claim suggests that this kind of constrained decoding can be deployed in interactive code completion and structured data extraction pipelines."],"supporting_citations":[],"fun_headline_variants":["Grammar-constrained decoding for diffusion LLMs","CFG-constrained infilling for diffusion LLMs","First CFG-constrained decoding for diffusion LLMs","Diffusion LLMs now honor context-free grammars","CFG-emptiness check enables diffusion LLM decoding"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The decoder rests on the assumption that masking every token that cannot lead to any valid grammatical completion never removes the functionally correct continuation, and that the context-free grammar used for C++ faithfully represents the real language.","fun_headline_variants_meta":{"raw":{"variants":["Grammar-constrained decoding for diffusion LLMs","CFG-constrained infilling for diffusion LLMs","First CFG-constrained decoding for diffusion LLMs","Diffusion LLMs now honor context-free grammars","CFG-emptiness check enables diffusion LLM decoding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0005,"raw_usage":{"total_tokens":2301,"prompt_tokens":780,"completion_tokens":1521,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":524,"completion_tokens_details":{"reasoning_tokens":1460}},"tokens_in":524,"tokens_out":1521,"duration_ms":15736,"temperature":1.0,"reasoning_tokens":1460,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T20:39:46.202000+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a code-infilling prompt where the set of tokens that keep $L \\cap R$ nonempty excludes the only tokens appearing in every functionally correct completion, then run the proposed decoder and show the output compiles but fails functional unit tests while an unconstrained model succeeds.","supporting_citations":[],"review_version":1}