- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes EPIC, a constrained decoding framework for diffusion language models with context-free grammars (CFG). EPIC reduces the overhead of the prior work (Mündler et al., 2026) from 3 perspectives: lexing memoization, relaxed compatible subset selection and DFA-free validation.
- Lexing memoization: The same text segments are repeatedly lexed in the same lexing contexts during the decoding process, so EPIC caches the lexing results.
- Relaxed compatible subset selection: Diffusion models can propose multiple tokens per step, but the prior work inefficiently checks them one by one. When simultaneous checking of multi-token proposals fails, EPIC tries to find a compatible subset with two-step filtering with (1) a regular language relaxed from the CFG and (2) the actual CFG.
- DFA-free validation with Earley-style parsing: Prior work checks CFG-compabiltity by intersecting the ENFA with the CFG, which requires the heavy overhead of DFA determination and minimization. EPIC uses an Early-style graph parser to serach on the ENFA directly.
Critical strengths
- Concrete optimization effort based on prior work.
- Explicit effiency improvements with roughly equivalent performance.
- Clear writing and explanation of motivations for these improvements.
Critical weaknesses
- The efficiency improvements mostly seem to come from better engineering rather than better theory for this problem. This might make this paper more suitable to, for example, MLSys than ICLR.
Questions for authors
Major issues
Is there some theoretical improvement rather than engineering improvement in this paper?
Minor issues
- The second part of EPIC is described as 'Filter-based Parallel Commit' in Figure 1, while in the main text, this is 'relaxed compatible subset selection'. Probably typo?
- Why does EPIC sometime run slower than prior work on Dream and DreamCoder with the SMILES benchmark?
- How often does simultaneous checking of multi-token proposals (i.e. the direct solution to the problem that relaxed compatible subset selection tries to solve) fail?
- Due to relaxed compatible subset selection, EPIC is no longer an unbiased constrained decoding method. Is this correct?
4 comments
Request for Discussion Engagement
Thank you for your time and constructive feedback. We greatly appreciate your positive assessment of our work.
As the discussion period approaches its end, we would appreciate it if you could review our responses and the revised manuscript. In particular, we have:
- W1: Clarified EPIC's algorithmic contributions to correctness-preserving parallel decoding, while distinguishing them from improvements in worst-case parsing complexity.
- Q1/Q2: Corrected the terminology inconsistency and explained the occasional runtime slowdown on SMILES.
- Q3: Added measurements of initial full-batch rejection rates, demonstrating the practical necessity of compatibility checking and subset selection.
- Q4: Clarified that EPIC preserves exact CFG-completability but does not guarantee preservation of the generation distribution, and discussed output agreement and functional correctness.
We hope these clarifications and results adequately address your concerns. We would appreciate it if you could confirm whether your concerns have been resolved or let us know if any questions remain.
We would be happy to provide further clarification.
Thank you for your replies.
W1: Although the authors repeated why and how each components in EPIC is designed, at most I can only barely say that DFA-free validation can be counted as algorithmic contribution.
I also thank the authors for addressing the minor issues (Q1, Q2, Q3, Q4). However, due to the major issue (W1), I will maintain my score of 3.
We thank the reviewer for the follow-up and for acknowledging our responses to Q1–Q4.
We once again thank you for highlighting the strengths of our work, particularly its practical efficiency improvements and clear presentation. Your constructive feedback has also helped us better clarify the scope of EPIC's algorithmic contributions and improve the revised manuscript.
We thank the reviewer for recognizing EPIC's practical efficiency improvements and clear presentation. We clarify the algorithmic contributions and address the questions below.
W1 & Major Question. Algorithmic and Theoretical Contributions
We agree that EPIC primarily targets inference efficiency rather than improving the worst-case complexity of CFG recognition. However, its contributions extend beyond implementation-level engineering by addressing algorithmic challenges specific to nonsequential DLM decoding.
Lexing Memoization preserves lexical alternatives across arbitrarily updated masked regions through mask-boundary-aware caching. DFA-Free Validation adapts automaton-based Earley parsing to repeated CFG-completability checking over dynamically changing partial-output ε-NFAs, eliminating repeated determinization and minimization from exact validation. Furthermore, joint validation and recursive subset splitting recover parallel token commitment while preserving exact CFG-completability. Regular Cover provides an additional screening mechanism with sound rejection guarantees, since the cover language contains the CFG language and every committed subset undergoes exact verification.
We do not claim a new parsing theory or improved asymptotic complexity. Rather, EPIC contributes a correctness-preserving decoding algorithm that addresses the computational bottlenecks and lost parallelism of existing CFG-constrained DLM decoding.
Q1. Terminology in Figure 1
We thank the reviewer for identifying the terminology inconsistency. We used "Filter-based Parallel Commit" in Figure 1 for brevity. To improve consistency with the main text, we have revised it to "Relaxed Subset Selection."
Q2. Runtime on SMILES
The occasional slowdown on Dream and DreamCoder with SMILES arises because the grammar and lexical specification are substantially smaller than those of C++ and JSON. Consequently, the prior constrained decoder already operates close to unconstrained inference time, leaving little constraint-processing overhead to eliminate. In this setting, the additional costs of caching and subset selection may outweigh the relatively small savings from lexing and validation.
For example, on DreamCoder/SMILES at 32 steps, the baseline and EPIC require 100.72% and 101.34% of unconstrained inference time, respectively. This difference is small compared with the substantial gains on C++ and JSON. LLaDA benefits more consistently on SMILES because its block-wise decoding schedule allows more effective parallel commitment.
Q3. Failure Rate of Joint Multi-token Proposals
We additionally measure how often the initial full batch of multi-token proposals fails exact CFG compatibility checking. We evaluate DreamCoder/C++ with 164 instances, three seeds, and 16 and 32 denoising steps, using Regular Cover.
At 16 and 32 steps, 36.06% and 18.39% of initial full-batch proposals were incompatible with the CFG, respectively. Among all initial proposals, Regular Cover rejected 23.91% and 11.47%, while an additional 12.15% and 6.92% passed the cover but failed exact CFG validation.
These results show that directly committing all proposed tokens is frequently infeasible, particularly at smaller denoising-step budgets. They also motivate recovering compatible subsets rather than abandoning parallel commitment when the initial full batch fails.
Q4. Bias in Constrained Decoding
We agree that EPIC does not guarantee preservation of the baseline's generation distribution. Parallel commitment and confidence-ordered subset selection may change the sequence of accepted updates and subsequent model predictions. However, this distinction concerns generation trajectories and sampling distributions, rather than syntactic correctness. Every committed subset is verified against the same exact CFG-completability criterion as the baseline.
The original decoder also uses sequential rejection and witness-based recovery, so neither approach is claimed to provide unbiased sampling from the model distribution conditioned on the grammar. Our main experiments use greedy decoding rather than unbiased stochastic sampling.
We explicitly examine output differences in Appendix F.6. EPIC achieves 73.13% exact text agreement with the constrained baseline, while functional accuracy remains comparable at 18.86% versus 18.72%, with a 94.20% correct-set Jaccard similarity. Thus, EPIC can alter generation trajectories while largely preserving functional performance and the original syntactic validity criterion.