{"id":"005c2439-6944-4fa0-bd23-7d2868297314","arxiv_id":"2606.00722","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"EPIC reduces CFG-constrained inference time in diffusion LMs by up to 67.5% via lexing memoization, Earley-style parsing, and relaxed compatible subset selection for parallel commits.","lead":"The paper presents EPIC, a decoding framework that speeds up context-free grammar constrained generation in diffusion language models using memoization, Earley-style parsing, and relaxed parallel token commitment. A smart generalist might read it to understand how to make parallel generative models practical for tasks requiring structured, valid outputs like code or data formats.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Correctness of relaxed compatible subset selection for parallel commits rests only on empirical results, not formal argument","rationale":"The reader's weakest assumption matches the load-bearing point exactly: the engineering combination is claimed to be both faster and fully correct, but only the former is quantified while the latter is left to benchmark outcomes. No other internal inconsistency appears in the abstract description of the three techniques. Because the full manuscript was referenced but not supplied here, the empirical-only status of correctness remains the clearest soft spot; the proposed check directly tests whether that status is justified.","tokens_in":1717,"tokens_out":354,"duration_ms":13655,"concrete_test":"Take the smallest non-trivial CFG from the paper's benchmarks (e.g., balanced parentheses or JSON subset) and run both EPIC and a slow but provably exact sequential CFG decoder on 1000 identical prompts; count any output that EPIC produces but the exact decoder rejects. Zero mismatches on this set would support the assumption; any mismatch falsifies it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline efficiency claim (67.5% time reduction, 90.5% overhead drop) requires that lexing memoization + Earley-style parsing + relaxed subset selection together preserve exact CFG membership for every committed token sequence. The abstract describes the third component as 'relaxed' and the method as enabling 'multiple compatible tokens to be committed together,' yet supplies no inductive argument, invariant, or proof that the relaxation never admits a token that would later violate the CFG. All support is empirical on three benchmarks; if the relaxation is incomplete for some grammars or token distributions, the reported speedups would be measured on an incorrect procedure.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces EPIC, an efficient CFG-constrained decoding framework for diffusion language models. It combines lexing memoization, Earley-style parsing, and relaxed compatible subset selection to reduce repeated overhead and enable parallel token commits, reporting up to 67.5% inference time reduction and 90.5% overhead decrease versus prior CFG methods across three benchmarks and four models, with code released at the cited GitHub repository.","tokens_in":1841,"tokens_out":363,"duration_ms":15733,"significance":"If the relaxed selection preserves exact CFG membership, the work would restore much of the parallel-decoding advantage of diffusion models under structural constraints, addressing a practical bottleneck in controlled generation. The open implementation is a clear strength supporting reproducibility.","major_comments":[{"comment":"The section describing relaxed compatible subset selection (and the associated claim in the abstract that the full pipeline 'preserves full correctness of the CFG constraints') provides no inductive argument, invariant, or proof that the relaxation never admits a token sequence that would later violate the grammar; correctness is asserted solely via empirical results on the three chosen benchmarks.","section":"Method (relaxed compatible subset selection)"},{"comment":"Experiments section: the headline speedups (67.5% time, 90.5% overhead) are reported without specification of exact baselines, statistical significance tests, error bars, number of runs, or controls for post-hoc benchmark/model selection, undermining assessment of the central efficiency claims.","section":"Experiments"}],"minor_comments":[{"comment":"Abstract does not name the four models or three benchmarks, forcing the reader to locate this information later in the text.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the constructive comments. We address each major comment below and will revise the manuscript to strengthen the presentation of correctness and experimental details.","responses":[{"response":"We agree that an explicit inductive argument or invariant would strengthen the correctness claim. The relaxed selection is constructed so that every committed token remains compatible with the current Earley parser state and no future violation is introduced; however, the submitted manuscript presents this only descriptively and relies on the three-benchmark empirical results. In revision we will add a short subsection containing a proof sketch that maintains the invariant that the partial derivation remains a valid prefix under the CFG at every parallel commit step.","revision_made":"yes","referee_comment":"[Method (relaxed compatible subset selection)] The section describing relaxed compatible subset selection (and the associated claim in the abstract that the full pipeline 'preserves full correctness of the CFG constraints') provides no inductive argument, invariant, or proof that the relaxation never admits a token sequence that would later violate the grammar; correctness is asserted solely via empirical results on the three chosen benchmarks."},{"response":"We will expand the experiments section to specify the exact prior CFG-constrained baselines (the deterministic-automata methods cited in Related Work), report results over five independent runs with error bars and standard deviations, include paired statistical significance tests, and state that the three benchmarks and four models were chosen before any experiments were run. These additions will be made in the revised manuscript.","revision_made":"yes","referee_comment":"[Experiments] Experiments section: the headline speedups (67.5% time, 90.5% overhead) are reported without specification of exact baselines, statistical significance tests, error bars, number of runs, or controls for post-hoc benchmark/model selection, undermining assessment of the central efficiency claims."}],"tokens_in":1325,"tokens_out":400,"duration_ms":16716,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that this paper delivers an engineering improvement that makes CFG-constrained decoding noticeably faster in diffusion language models without changing the core generation process. They combine lexing memoization to avoid repeated work, switch to an Earley-style parser instead of automata, and introduce a relaxed rule for committing multiple compatible tokens at once. On three benchmarks with four models the reported gains reach 67.5% less inference time and 90.5% less overhead versus prior constrained methods.\n\nWhat stands out is the practical focus on preserving the parallel advantage of diffusion models while adding CFG control. The open-source release helps, and the approach targets a real bottleneck that existing sequential checks create.\n\nThe soft spot is the relaxed compatible subset selection. The abstract calls it relaxed and says it lets multiple tokens commit together, yet supplies no inductive argument or invariant showing that every committed sequence still satisfies the grammar. All support comes from the chosen benchmarks. If the relaxation admits invalid tokens on other grammars or token distributions, the speedups would be measured against an incorrect procedure. The abstract also gives no details on baseline implementations, variance, or how the three benchmarks were selected.\n\nThis is useful for groups already working on constrained decoding for diffusion models or anyone who needs faster structured output from those models. It is not a broad theoretical advance. The work is clear enough on its own terms to deserve referee time, mainly so the empirical claims and the relaxation can be checked against the full implementation and additional test cases.","headline":"EPIC gives measurable speedups on CFG decoding for diffusion LMs through memoization and relaxed parallel commits, but the relaxation's correctness is only shown empirically.","tokens_in":2303,"tokens_out":378,"would_cite":false,"duration_ms":17621,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"EPIC enables parallel CFG-constrained decoding in diffusion language models by using memoization and relaxed subset selection to cut overhead.","keywords":["diffusion language models","context-free grammar","constrained decoding","parallel inference","CFG constraints","Earley parsing","memoization"],"falsifier":"Running EPIC on a new grammar or benchmark and finding that any generated sequence violates the CFG rules would show that correctness is not preserved.","tokens_in":2612,"feed_emoji":"⚡","tokens_out":581,"duration_ms":16684,"temperature":0.7,"pith_summary":"The paper introduces EPIC to solve the slowdown and loss of parallelism that CFG constraints impose on diffusion language model decoding. Existing approaches rely on sequential validity checks that add substantial overhead. EPIC combines lexing memoization, Earley-style parsing for validation, and relaxed compatible subset selection to reduce repeated work and commit multiple tokens at once. A sympathetic reader would care because the changes restore much of the speed advantage diffusion models hold over autoregressive ones while keeping outputs structurally valid.","feed_headline":"EPIC cuts CFG decoding time for diffusion models by 67.5%","feed_subtitle":"Memoization and relaxed subset selection let multiple tokens commit in parallel while outputs stay valid.","key_machinery":"The central mechanism is the combination of lexing memoization, Earley-style parsing, and relaxed compatible subset selection that permits parallel commits under CFG constraints.","core_discovery":"The authors show that lexing memoization, validation via Earley-style parsing rather than deterministic automata, and relaxed compatible subset selection together reduce repeated lexing and validation overhead and allow multiple compatible tokens to be committed together, yielding up to 67.5 percent lower inference time and up to 90.5 percent lower additional overhead than prior CFG-constrained methods on three benchmarks with four models.","pith_inferences":["The same memoization and relaxed selection pattern might apply to other non-autoregressive generation settings that need structural constraints.","Lower overhead could make CFG-guided diffusion models practical for interactive applications that require valid outputs.","Formal proofs of correctness rather than only empirical checks on chosen benchmarks would strengthen the method's reliability."],"forward_implications":["Inference time drops by up to 67.5 percent compared with existing CFG-constrained methods.","Additional overhead falls by up to 90.5 percent.","Parallel decoding remains feasible under CFG constraints.","Structural validity of outputs is maintained on the evaluated benchmarks."],"fun_headline_variants":["EPIC cuts CFG decoding time 67.5% for diffusion models","67.5% faster CFG decoding in diffusion models via EPIC","EPIC reduces CFG overhead by 90.5% for diffusion LMs","Parallel commit lowers CFG time 67.5% with EPIC"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The combination of lexing memoization, Earley-style parsing, and relaxed compatible subset selection preserves full correctness of the CFG constraints while enabling parallel commits.","fun_headline_variants_meta":{"raw":{"variants":["EPIC cuts CFG decoding time 67.5% for diffusion models","67.5% faster CFG decoding in diffusion models via EPIC","EPIC reduces CFG overhead by 90.5% for diffusion LMs","Parallel commit lowers CFG time 67.5% with EPIC"]},"model":"grok-4.3","cost_usd":0.009382,"raw_usage":{"total_tokens":4191,"prompt_tokens":661,"num_sources_used":0,"completion_tokens":76,"cost_in_usd_ticks":93824500,"prompt_tokens_details":{"text_tokens":661,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3454,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":661,"tokens_out":76,"duration_ms":24268,"temperature":1.0,"reasoning_tokens":3454,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-28T18:58:21.715424+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Running EPIC on a new grammar or benchmark and finding that any generated sequence violates the CFG rules would show that correctness is not preserved.","supporting_citations":[],"review_version":1}