acceptodds
Under review as a conference paper at ICLR 2027

Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models

Abstract

Controlling language model outputs is essential for ensuring structural validity, reliability, and downstream usability, and diffusion language models are no exception. Recent advances in diffusion language model decoding have extended output control beyond regular constraints to context-free grammar (CFG) constraints. However, the prior CFG-constrained decoder can be up to four times slower than unconstrained decoding, forcing a trade-off between the correctness benefits of CFG constraints and the decoding efficiency of diffusion models. A key source of this overhead is sequential validity checking, which limits parallel token commitment and adds repeated validation costs. We propose EPIC, a CFG-constrained decoding framework designed to improve this efficiency-correctness trade-off. In order to reduce decoding overhead without sacrificing syntactic correctness, EPIC combines lexing memoization, relaxed compatible subset selection for parallel commit, and validation using Earley-style parsing instead of deterministic automata. This design enables multiple compatible tokens to be committed together while avoiding repeated lexing and expensive validation. Experiments on three benchmarks using four models show that EPIC improves the efficiency-correctness trade-off, bringing runtime close to unconstrained levels while maintaining comparable syntactic and functional correctness. Relative to the prior CFG-constrained decoder, EPIC achieves a best-case inference-time reduction of 67.2%. Our implementation is available at https://anonymous.4open.science/r/EPIC-83DE/.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Constrained Decoding, Diffusion Language Models, Context-free Grammars, Structured Generation

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_J6v4OpenReview ↗
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

  1. 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?
  2. Why does EPIC sometime run slower than prior work on Dream and DreamCoder with the SMILES benchmark?
  3. 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?
  4. Due to relaxed compatible subset selection, EPIC is no longer an unbiased constrained decoding method. Is this correct?
4 comments

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.

AuthorsOpenReview ↗

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.

Reviewer_iLRYOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the efficiency of CFG-constrained decoding in Diffusion Language Models (DLMs). Whilst existing methods can guarantee the syntactic correctness of the generated output, repetitive lexical analysis, automaton transformations and token-by-token verification incur significant inference overhead and undermine the parallelisation advantages of DLMs. The authors propose EPIC, which optimises existing CFG-constrained decoding frameworks through three components: Lexing Memoisation, which caches the results of repeated lexical analysis; Relaxed Compatible Subset Selection, which utilises Regular Cover to filter tokens that can be submitted in parallel; and DFA-Free Validation, which employs Earley-style graph parsing to avoid repeated NFA-to-DFA conversions. The authors conducted experiments on four DLMs and three structured generation tasks (C++, JSON, SMILES). EPIC significantly reduces inference time in most settings—by up to 67.2 per cent in the best-case scenario—whilst maintaining syntax and functional correctness rates close to those of the original CFG-constrained baseline.

Critical strengths
  1. Existing CFG-constrained decoding requires the verification of candidate tokens one by one, which undermines the parallel generation advantages of DLMs. By utilising caching, batch candidate filtering and DFA-free validation to reduce redundant computations whilst retaining precise CFG verification, EPIC improves inference efficiency without relaxing syntactic constraints. In particular, the design combining ‘Regular Cover’ with ‘Exact Verification’ enables multiple candidate tokens to be submitted safely together, which has clear practical significance.

  2. The paper evaluates the approach across four models, three tasks and five sampling steps, including comprehensive ablation studies of component combinations, runtime decomposition, accuracy before and after recovery, ‘Regular Cover’ analysis and output consistency analysis.

Critical weaknesses
  1. The three components of this paper are primarily based on established techniques: Lexing Memoisation is a standard caching optimisation, Earley-style Graph Parsing is a well-established approach to syntactic analysis, and Regular Cover and recursive grouping filtering also have corresponding foundations in formal languages and algorithms. The most distinctive aspect of this paper is the use of Regular Cover to implement Parallel Commit; however, it remains unclear whether the introduction of this additional approximate checker is necessary. A natural alternative would be to directly use the authors’ proposed DFA-Free Exact Validator to check the entire batch of candidates; if the check fails, the batch would be recursively split according to the same Confidence Ordering, without resorting to Regular Cover.

  2. Firstly, the time differences between the ‘Lexing’, ‘DFA Conversion’ and ‘Validation’ stages shown in Table 3 do not fully account for the improvement in total running time reported in Table 6. For example, in the DreamCoder C++ 32-step scenario, the cumulative time difference across the three components is approximately 355 seconds, whilst the total running time was reduced by 758 seconds. This discrepancy may stem from other decoding overheads, the number of model forward passes, early termination, or changes in generated trajectories; however, the paper has not yet adequately decomposed these factors. Consequently, it is currently difficult to accurately determine the extent to which the acceleration stems from optimisations to the syntax checking process itself.

Questions for authors
  1. Algorithm 3 uses a worklist and a visited set to process parser items, but the description of the completion operation is not yet sufficiently precise. In particular, if a completed item has already been processed and the corresponding waiting item is added subsequently, how does the algorithm ensure that the waiting item can still be correctly advanced? Are there corresponding handling mechanisms for ε-transitions, cycles and nullable non-terminals?

  2. Could a baseline be introduced: using the same lexing cache, Earley-style validator and confidence ordering, performing exact CFG validation directly on the candidate set, with recursive splitting upon failure, without introducing regular cover?

4 comments

We thank the reviewer for the constructive feedback and for recognizing EPIC's practical significance and extensive evaluation. We address the concerns regarding methodological novelty, the necessity of Regular Cover, runtime attribution, and parser correctness below.

W1. Methodological Novelty & Q2. Exact-only Baseline

We acknowledge that memoization, Earley-style parsing over finite automata, and regular approximations are established techniques. EPIC's contribution lies in addressing the challenges of CFG-constrained decoding for nonsequential DLMs. Specifically, Lexing Memoization reuses local lexing alternatives across masked regions while preserving lexical ambiguity. DFA-Free Validation adapts automaton-based Earley parsing to repeated CFG-completability checking over dynamically changing partial-output ε-NFAs, avoiding repeated determinization and minimization in the exact validation pipeline.

Importantly, joint validation and recursive subset splitting for parallel token commitment are contributions independent of Regular Cover. Rather than checking candidate tokens individually, EPIC evaluates their joint compatibility and recursively splits incompatible subsets according to confidence ordering. Regular Cover provides an additional screening mechanism intended to reduce the number of expensive exact CFG evaluations, but is not required for parallel commitment or correctness.

Following the reviewer's suggestion, we evaluated an Exact-only baseline that retains the same Lexing Memoization, DFA-Free Earley Validator, confidence ordering, and recursive splitting procedure, while removing Regular Cover. Under matched DreamCoder/C++ settings with 164 instances, three seeds, and 16 and 32 denoising steps, Exact-only achieved 3.402 and 4.678 s/example, compared with 3.867 and 5.104 s/example for Regular Cover. Both improved over optimized sequential validation, which required 6.419 and 6.142 s/example, respectively.

Separate profiling under matched settings shows that Regular Cover reduced the number of exact CFG evaluations by 7.8% and 5.8% at 16 and 32 steps, respectively. Thus, Regular Cover does reduce exact evaluations, but its additional cover-intersection and graph-construction overhead outweighs these savings in the evaluated settings. We do not claim that Regular Cover is universally beneficial. Its advantage depends on whether the cost saved by rejecting incompatible candidate batches exceeds the screening overhead. This trade-off may become more favorable when candidate rejection is more frequent or exact validation is more expensive. Crucially, the Exact-only results demonstrate that EPIC's parallel subset verification provides substantial acceleration independently of Regular Cover.

W2. Runtime Breakdown and Decoding Overheads

We clarify that Table 3 was intended to directly examine the operations targeted by our proposed optimizations, rather than to provide an exhaustive decomposition of end-to-end runtime. Since differences in generation trajectories or recovery behavior may also affect total inference time, we separately measured lexing, DFA conversion, and validation costs to demonstrate that substantial reductions occur in the constraint-processing operations themselves.

For DreamCoder/C++ at 32 steps, these operations account for 354.9 s of the total 758.1 s reduction. The remaining difference includes operations not individually reported in Table 3, such as partial-output graph construction, candidate processing, model evaluation, and recovery. Therefore, Table 3 provides direct evidence of reduced constraint-processing costs, although it does not fully attribute the end-to-end acceleration to individual operations.

Q1. Completion, ε\varepsilon-transitions, and Nullable Productions

The implementation maintains indexed waiting items and completed constituents. When a new waiting item is discovered, previously completed matching constituents are retrieved and applied. Conversely, when a new constituent is completed, existing matching waiting items are advanced. Completion requires the current graph node of the waiting item to match the origin node of the completed constituent. This bidirectional bookkeeping ensures that completion is independent of worklist processing order, including for nullable productions. ε\varepsilon-transitions advance graph nodes without consuming grammar symbols, while duplicate-item detection prevents infinite revisits along graph cycles.

AuthorsOpenReview ↗

Request for Discussion Engagement

Thank you for your time and constructive feedback. We have carefully addressed your concerns through detailed clarifications and additional experiments.

As the discussion period approaches its end, we would greatly appreciate it if you could review our responses and newly added results. In particular, we have:

  • W1/Q2: Added an Exact-only batch validation baseline without Regular Cover, reporting runtime and exact CFG evaluation counts. We also clarified the conditions under which Regular Cover's screening overhead can outweigh its benefits.
  • W2: Clarified the runtime breakdown and distinguished the measured constraint-processing improvements from other sources of end-to-end latency reduction.
  • Q1: Explained the parser's bidirectional completion bookkeeping and its handling of epsilon-transitions, cycles, and nullable nonterminals.

We hope these clarifications and results adequately address your concerns. If you find our responses satisfactory, we would be grateful if you could reconsider your evaluation, including the overall score.

Please let us know if any concerns remain. We would be happy to address them.

Thank you for the detailed response and additional experiments. I appreciate the authors' efforts to address my concerns, particularly the Exact-only baseline and the clarification of parser correctness.

However, the Exact-only results raise further questions about the necessity of Regular Cover, as removing it actually improves efficiency. Additionally, the runtime breakdown still does not fully explain the end-to-end speedup. While the rebuttal has addressed several of my concerns, I still have reservations about the independent technical contribution. I will therefore maintain my current rating.

We thank the reviewer for the follow-up and for acknowledging the additional experiments and clarifications.

We agree that Regular Cover does not provide additional runtime benefits over Exact-only in the evaluated settings. We have explicitly acknowledged this limitation in the revised manuscript. Importantly, our intended contribution is not Regular Cover alone. The Exact-only results demonstrate that joint validation and recursive subset splitting can recover parallel token commitment independently of Regular Cover, achieving 1.89x and 1.31x speedups over optimized sequential validation at 16 and 32 steps, respectively. Together with mask-aware Lexing Memoization and DFA-Free Validation, these constitute our algorithmic adaptations for CFG-constrained nonsequential DLM decoding.

Regarding runtime attribution, we would like to clarify that our analysis does not rely solely on Table 3. Table 3 directly measures the reduction in the constraint-processing operations targeted by EPIC, including lexing, automaton construction, and validation. In addition, Table 5 and Appendix F.3 provide end-to-end ablations of individual components and their combinations, while Appendix F.8 further isolates the contribution of joint batch validation from Regular Cover.

We acknowledge that the measured operations in Table 3 account for 354.9 s of the total 758.1 s reduction in the DreamCoder/C++ 32-step setting. However, end-to-end runtime also depends on operations outside these measured stages and on decoding trajectories, which can differ between methods. Since these effects interact, the remaining difference cannot be uniquely attributed to individual components by subtracting the measured stage times. Nevertheless, the existing operational breakdown and component ablations provide complementary evidence that EPIC's proposed mechanisms contribute to the observed end-to-end acceleration. We have clarified the scope of the runtime analysis in the revised manuscript.

The additional experiments also help clarify the nature of EPIC's independent contribution. In particular, the Exact-only results isolate joint CFG validation and confidence-ordered recursive subset splitting from Regular Cover, demonstrating that parallel token commitment can be recovered without relying on approximate screening. This addresses a fundamental difficulty of nonsequential DLM decoding, where individually compatible token proposals need not be jointly compatible. Combined with mask-aware Lexing Memoization and DFA-Free Validation over dynamically changing partial-output automata, EPIC provides an algorithmic adaptation of established techniques to a decoding setting where conventional sequential verification limits parallelism. We believe the resulting framework and its demonstrated end-to-end efficiency improvements constitute a meaningful technical contribution, independently of the effectiveness of Regular Cover.

Reviewer_j8nKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents EPIC, a framework for accelerating CFG-constrained decoding of diffusion language models. It combines lexing memoization, regular-cover-based selection of candidate batches, and exact validation with an Earley-style graph parser. Experiments on four models and three structured-generation tasks show substantial runtime reductions over the completion-based baseline, with largely unchanged syntactic and functional correctness.

Critical strengths
  1. The paper addresses a practical bottleneck in constrained diffusion decoding. The reported speedups are substantial in several settings, particularly on C++, and extend across multiple models and decoding budgets.

  2. The analysis includes all component combinations, correctness before and after recovery, and output agreement with the baseline. These results help explain the speedups and support the claim that task performance is largely maintained.

Critical weaknesses
  1. The benefit of regular-cover selection over simpler batching is not fully isolated. The ablations evaluate the complete selection module, but do not compare it with directly validating candidate batches and recursively splitting failed batches, using the same memoization and graph parser. This would clarify how much the regular cover contributes to the parallel-commit gains.

  2. The comparison with LAVE is difficult to interpret. Appendix F.7 uses different temperatures and decoding schedules, and the reported effective steps are upper bounds rather than measured forward-pass counts. A comparison under a common decoding protocol would better establish the relative quality–latency trade-off.

Questions for authors
  1. With memoization and the graph parser held fixed, how does regular-cover selection compare with direct exact batch validation followed by recursive splitting? Please report runtime and the number of exact checks.

  2. How do EPIC and LAVE compare under a common temperature and block schedule, in terms of wall-clock latency and syntactic and functional correctness? Please also clarify the termination and recovery policies used in this comparison.

4 comments

We thank the reviewer for recognizing EPIC's practical benefits and comprehensive evaluation. We clarify the contribution of Regular Cover and provide additional comparisons addressing both questions.

W1 & Q1. Regular Cover and Exact-only Batch Validation

We clarify that joint validation and recursive subset splitting for parallel token commitment are themselves contributions of EPIC, independent of Regular Cover. Regular Cover is an additional screening mechanism designed to reduce expensive exact CFG evaluations, rather than a requirement for parallel commitment or correctness.

Following the reviewer's suggestion, we evaluated an Exact-only variant that retains the same Lexing Memoization, DFA-Free Earley Validator, confidence ordering, and recursive splitting procedure while removing Regular Cover. Under matched DreamCoder/C++ settings with 164 instances, three seeds, and 16 and 32 denoising steps, Exact-only achieved 3.402 and 4.678 s/example, compared with 3.867 and 5.104 s/example for Regular Cover. Both outperformed optimized sequential validation at 6.419 and 6.142 s/example.

Separate profiling showed that Regular Cover reduced exact CFG evaluation counts by 7.8% and 5.8%, respectively. However, the additional cover-intersection and graph-construction overhead outweighed these savings. We therefore do not claim that Regular Cover is universally beneficial. We expect it to become more advantageous when candidate rejection is more frequent or exact validation is more expensive, provided that screening costs remain sufficiently low. Importantly, these results independently demonstrate the effectiveness of joint validation and recursive splitting without Regular Cover.

W2 & Q2. Comparison with LAVE under a Common Decoding Protocol

We agree that Appendix F.7 does not provide a fully controlled comparison because LAVE uses semi-autoregressive decoding with fixed-size blocks and EOS-triggered early stopping, whereas our original experiments preserve the native decoding schedules of individual DLMs. Moreover, the reported effective steps are estimates rather than measured model forward-pass counts.

We therefore conduct an additional comparison using LLaDA-8B-Instruct, which supports semi-autoregressive generation. Both methods use HumanEval-X C++, 128 denoising steps, block length 32, temperature 0.2, maximum generation length 256, and identical evaluation instances. We additionally enabled EOS-triggered early stopping in EPIC to match LAVE's termination behavior.

Under this configuration, EPIC achieved 9.397 s/example, compared with 12.117 s/example for LAVE in the matched comparison, corresponding to a 1.29× speedup (22.4% latency reduction). The correctness evaluation also showed strong syntactic correctness for EPIC (100.00% versus 89.63% for LAVE), with comparable functional correctness (16.67% versus 17.48%).

While both methods use the same EOS-triggered termination policy, LAVE retains its lookahead-based retry mechanism with a retry budget of five, whereas EPIC retains the resampling-budget recovery procedure of Mündler et al. (2026).

AuthorsOpenReview ↗

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 newly added experimental results. In particular, we have:

  • W1/Q1: Added an Exact-only batch validation baseline without Regular Cover, reporting runtime and exact CFG evaluation counts. We also clarified the conditions under which Regular Cover's screening overhead can outweigh its benefits.
  • W2/Q2: Conducted a matched-protocol comparison with LAVE using identical temperature, block length, and denoising steps, including latency, syntactic correctness, functional correctness, and termination policies.

We hope these additional experiments 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 the additional experiments. My concerns have been substantially addressed, although the benefits of Regular Cover remain limited, as it is slower than exact-only validation in the evaluated settings. I maintain my original score of 3.

We thank the reviewer for considering our responses and additional experiments. We appreciate your acknowledgment of EPIC's contributions and that your concerns have been substantially addressed. Your constructive feedback has helped us improve the revised manuscript by clarifying the role and limitations of Regular Cover and strengthening the comparison with LAVE.

Reviewer_zfRvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper targets context-free-grammar (CFG) constrained decoding for masked diffusion language models. The prior completion-based rejection-sampling decoder (Mündler et al., ICLR 2026) validates each proposed token sequentially. For every token, it re-lexes the partial output, builds and determinizes an automaton of its possible completions, and tests the intersection with the grammar. This can make constrained decoding several times slower than unconstrained decoding, and it forgoes the model's parallelism.

The authors identify three sources of overhead: repeated lexing, sequential candidate validation and DFA construction. They propose EPIC, which keeps the same acceptance criterion and adds three components:

  • memoized lexing of unchanged spans;
  • relaxed compatible-subset selection, which uses a regular over-approximation of the grammar to screen batches of high-confidence proposals before exact verification, so that several tokens can be committed per step;
  • a DFA-free validator that runs an Earley-style parser directly over the ε-NFA.
Critical strengths

S1. Substantial speedups that preserve the baseline's validity criterion.

  • Same acceptance criterion as the baseline. EPIC keeps the completable-output criterion of the prior constrained decoder. A batch of tokens is committed only after it passes the exact check, and the regular cover is used only to reject candidates soundly. The method therefore "changes the search strategy, not the validity criterion" (L970–971).
  • Runtime. Within this guarantee, EPIC lowers the mean runtime relative to unconstrained decoding (Table 1)
    • It is faster than the prior decoder in 39 of the 40 C++ and JSON settings.
    • The largest gain is on DreamCoder/C++ at 16 steps: 388.60% → 127.34%, a 3.05× speedup.
  • Correctness. After recovery, both constrained methods reach nearly 100% syntactic correctness. EPIC's functional correctness is within 0.6 percentage points of the baseline in the worst case, and higher in several settings (Table 2).
  • Why it matters: the cost of CFG-constrained decoding for diffusion LMs is reduced to nearly that of unconstrained decoding, without weakening the correctness guarantee that structured generation relies on.
Critical weaknesses

W1. Limited methodological novelty.

  • Inherited pipeline. The validity criterion, recovery procedure, benchmarks, grammars and lexers come from Mündler et al. (ICLR 2026).
  • Each component builds on established techniques:
    • Regular over-approximation of CFGs is classical, as the paper acknowledges (Pereira & Wright, 1991; Nederhof, 2000).
    • Earley-style parsing over a finite automaton or word lattice instead of a string follows the classical intersection of context-free and regular languages (Bar-Hillel, Perles & Shamir; see also Nederhof & Satta's survey of tabular parsing). The authors describe the DFA-free validator as "a practical optimization rather than an improvement in the worst-case asymptotic complexity of validity checking" (L864–866).
    • Memoizing lexing and grammar computations is common in constrained-decoding engines for autoregressive models, for example XGrammar (MLSys 2025) and llguidance, which runs an Earley parser on top of a lexer.
  • What is new. Using the regular cover as a group test for committing tokens in batches (§4.2, Alg. 4) is new in this setting. Overall, however, the contribution consists of technical optimizations of an existing pipeline rather than new methodology or scientific insight.

Why it matters: in my assessment, the paper does not offer a sufficiently substantial contribution for ICLR. It mainly introduces technical optimizations built on existing foundations, without clear methodological novelty or significant new insight.

W2. Limited clarity, technical rigor and reproducibility.

  • Few visualizations. All experimental results in the main text are tables (Tables 1–5). Trend plots appear only in the appendix comparison with LAVE (Figs. 3–5). Additional figures and visual analyses would make performance trends and the method's behavior easier to understand.
  • Informal method description. Beyond the problem formulation in §3, the three components are described largely informally in the main text.
  • Completeness argued only informally. The claim that the Earley-style validator decides the same predicate as the baseline is argued only informally (L959–971). Standard subtleties, such as the handling of nullable nonterminals, are not discussed.
  • Missing experimental details. Several details are not stated, including the number of instances per benchmark, the resampling budget and the timeout values.

Why it matters: these shortcomings limit the technical clarity and reproducibility of the paper, and contribute to the impression that the work needs further development and refinement.

Questions for authors

Scientific significance and novelty (clarification). Could the authors further clarify the scientific significance and novelty of this work? From my perspective, the primary contribution is an optimized implementation of the constraint-checking pipeline for CFG-constrained diffusion decoding: memoized lexing, batch screening with a regular cover, and Earley-style validation over the ε-NFA. Which aspects do the authors view as methodologically new, and which insights generalize beyond this implementation?

4 comments

We thank the reviewer for recognizing EPIC's substantial speedups and preservation of CFG-completability. We clarify our technical contributions and address the concerns about presentation and reproducibility below.

W1. Methodological Novelty and Scientific Significance

We agree that memoization and Earley parsing are established techniques. Our contribution is not to reinvent these algorithms, but to address three technical challenges arising from the nonsequential generation process of DLMs.

1. Mask-aware Lexing Memoization

Unlike autoregressive decoding, which extends a fixed prefix, DLMs update arbitrary masked positions. Multiple masked regions introduce lexical ambiguity because lexeme boundaries may depend on the unknown contents of adjacent masks. Consequently, conventional prefix caching or caching a fixed tokenization cannot directly handle such partial outputs. EPIC addresses this challenge by caching local lexing alternatives under mask-boundary conditions, including possible prefix and suffix lexings. This enables reuse across nonsequential updates while preserving the same partial-output language as uncached lexing.

2. DFA-Free Earley-style Validation

While Earley-style parsing over finite automata has been studied previously, applying it to CFG-constrained DLM decoding introduces distinct challenges. Unlike conventional fixed-string parsing, DLM decoding requires repeated validation of dynamically changing ε\varepsilon-NFAs representing partial outputs with multiple masked regions. EPIC adapts Earley-style parsing to these graphs by tracking origin and current graph nodes, handling nondeterministic lexeme transitions and ε\varepsilon-transitions, and maintaining completion bookkeeping. This enables exact CFG-completability checking directly on the partial-output FA, eliminating repeated determinization and minimization. Our contribution lies in adapting and integrating DFA-free graph parsing into repeated CFG-completability checking for nonsequential DLM decoding.

3. Parallel Token Commitment

Independently valid proposals at different masked positions are not necessarily jointly valid. Existing sequential verification therefore sacrifices DLM parallelism. EPIC addresses this through joint subset verification and recursive splitting of incompatible candidates. The regular cover provides conservative screening, while every committed subset must pass exact CFG validation. This recovers parallel commitment without weakening the original acceptance criterion.

These contributions form an efficient exact constrained-decoding framework tailored to DLM. The challenges are not specific to code generation and arise whenever nonsequential generation must satisfy structured constraints. Experimentally, EPIC improves runtime in 39 of 40 C++ and JSON settings, achieving a 3.05x speedup on DreamCoder/C++ at 16 steps.

W2. Technical Clarity and Reproducibility

1. Formal Correctness

Appendix D.2 already discusses the correctness of DFA-free validation. We have further clarified the soundness and completeness arguments in the revised appendix, with particular attention to nullable productions, -transitions, and completion bookkeeping.

Soundness follows because each parser operation preserves a valid partial CFG derivation along a path in the ε\varepsilon-NFA. Prediction introduces grammar productions, scanning follows matching terminal transitions, and completion connects constituents through their graph endpoints. Thus, an accepting item witnesses a valid CFG derivation along an accepting graph path. Completeness follows by induction on CFG derivations, as the parser explores all applicable productions and graph transitions, including ε\varepsilon-transitions that do not consume grammar symbols. Nullable productions are handled through zero-length completions, while waiting/completed-item bookkeeping ensures that nullable constituents are recognized regardless of processing order. Duplicate-item detection prevents infinite revisits along graph cycles. Consequently, in the absence of resource-limit interruptions, the parser preserves exact CFG-completability without DFA determinization or minimization. Since EPIC commits tokens only after exact validation, CFG-completability is also preserved under arbitrary-order and parallel token commitments in DLMs.

2. Reproducibility

Several details mentioned by the reviewer are already provided in Section 5.1 and Appendix E, including the maximum generation length, denoising steps, greedy decoding, random seeds, and wall-clock measurement excluding model/tokenizer loading, common grammar/lexer preprocessing, and downstream evaluation. Section 4.4 also explains the resampling-budget recovery procedure. We have additionally specified the exact evaluation instance counts, resampling budget (100), and separated generation and CFG-validation timeout values.

AuthorsOpenReview ↗

Request for Discussion Engagement

Thank you for your time and constructive feedback. We have carefully addressed your concerns through detailed clarifications and revisions.

As the discussion period approaches its end, we would greatly appreciate it if you could review our responses and the revised manuscript. In particular, we have:

  • W1: Clarified EPIC's methodological contributions and scientific significance, emphasizing mask-aware lexing, DFA-free validation, and correctness-preserving parallel token commitment in nonsequential DLM decoding.
  • W2: Strengthened the soundness and completeness arguments for DFA-free validation, including nullable productions and epsilon-transitions, and added implementation details to improve reproducibility.

We hope these clarifications adequately address your concerns. If you find our responses satisfactory, we would be grateful if you could reconsider your evaluation, including the overall score.

Please let us know if any concerns remain. We would be happy to address them.

I thank the authors for their reply and the additional experiments. The expanded correctness argument for the DFA-free validator and the added experimental details resolve my concerns about rigor and reproducibility. My main remaining concern is the significance of the novelty. I agree that the paper addresses a practical technical challenge and makes a meaningful technical contribution. Joint validation with recursive splitting clearly improves over sequential checking. However, the new Exact-only results show that Regular Cover, the component I had considered most novel, slows decoding in the evaluated settings, and the remaining components adapt established techniques. I therefore still believe the methodological contribution does not reach the level expected of an ICLR paper. I will keep my score, but I will not oppose acceptance.

We sincerely thank the reviewer for the follow-up and for recognizing EPIC's practical significance and meaningful technical contribution. We also appreciate your confirmation that our revisions have resolved the concerns regarding rigor and reproducibility.

We would like to clarify one point regarding Regular Cover and the Exact-only results.

Both Regular Cover and confidence-based recursive subset splitting are contributions of EPIC's proposed decoding scheme. Importantly, Exact-only is not an independently developed method or natural baseline, but an ablation derived from EPIC by removing only Regular Cover. It retains our confidence-based joint validation and recursive subset splitting, along with Lexing Memoization and DFA-Free Validation. Therefore, its 1.89x and 1.31x speedups over optimized sequential validation demonstrate the effectiveness of EPIC's decoding scheme rather than an independent alternative.

Although Regular Cover introduces additional overhead in the evaluated settings, it remains a sound screening mechanism whose benefits depend on the trade-off between screening overhead and avoided exact CFG validation costs. Thus, the Exact-only results isolate the contribution of EPIC's subset selection strategy without diminishing the algorithmic contributions of the overall framework.

We once again thank the reviewer for the constructive feedback, which has helped us strengthen the rigor and reproducibility of the revised manuscript.

Comments on the paper

1 comment

We thank the reviewers for their constructive feedback. We have revised the manuscript to clarify EPIC's algorithmic contributions, strengthen the correctness discussion of DFA-free validation, and provide additional implementation and experimental details. We also added an Exact-only batch validation comparison, a matched-protocol evaluation against LAVE, and an analysis of initial full-batch rejection rates. Furthermore, we clarified runtime attribution, the limitations of Regular Cover, and the distinction between CFG-completability and generation distribution preservation. All revisions are highlighted in blue in the updated manuscript for ease of reference.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.