EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models

arXiv:2606.00722 · cs.CL, cs.AI · Submitted 2026-05-30 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models".

Jane: Controlling language model outputs is essential for ensuring structural validity, reliability, and downstream usability, and diffusion language models are no exception.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: Now that we understand the context, let's look closer at exactly what they are calling this work: EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models.

Jane: The title tells us immediately that the main focus is on two things working together: efficiency and parallel inference, specifically when you introduce these context-free grammar constraints into diffusion language models.

Lu: It’s clear they are tackling a major problem where adding grammar rules slows down the speed of generation, which is a big deal since diffusion models are known for their ability to generate multiple tokens simultaneously.

Meng: So the title sets up the tension: you want parallelism, but you have these grammar rules that seem to force a slow, sequential check on every single step.

Tom: Right. The paper points out that existing methods can be up to four times slower than just running models without any constraints, which is a really big number when we're talking about inference time.

Jane: And the authors are saying that this slowdown happens because sequential validity checking introduces significant overhead during parallel generation, which is the key issue they want to fix.

Lu: They are proposing EPIC as a framework designed to address these limitations by combining several specific techniques to reduce the computational work involved in those checks.

Tom: So what’s the big promise here? It’s not just making it run faster; it's about preserving that parallel generation capability, which is a key strength of diffusion models over other types of models.

Jane: That means they want to show that you can have the structure control you need without losing the speed advantage that makes these models so popular for things like image or video generation.

Lu: They are doing this by focusing on three main sources of overhead: repeated lexing, DFA construction, and sequential candidate validation.

Meng: That sounds like a very targeted approach; they aren't trying to fix everything at once but hitting the specific points where the slowdown is most visible.

Tom: Exactly. They are targeting those three bottlenecks directly with their three main components: lexical memoization, DFA-free validation using Earley-style parsing, and relaxed compatible subset selection.

Jane: It sounds like a very surgical fix rather than a complete overhaul of the entire decoding pipeline from scratch.

Lu: The goal is to show that you can handle these constraints efficiently while keeping the core benefit of diffusion models—the ability to propose multiple tokens at once—which is what they call parallel decoding.

Tom: So, before we get into the details of *how* they do this, I want to explain what the paper actually proposes in plain terms.

Jane: Basically, it’s a new way to check if adding a new token keeps you on track for finishing a sequence that follows your grammar rules.

The paper's summary: Tom: So let’s break down what EPIC actually summarizes in the paper. It explains the problem formulation using some formal notation, but the gist is about checking if a partial output remains completable under the target grammar G after applying a candidate update.

Jane: They define this as whether there is an intersection between two languages: the language of all possible lexeme sequences that can be made from our current partial output and the set of lexeme sequences accepted by our grammar.

Lu: They write this out formally as L(G) intersect Cx not being empty, where Cx represents the completion language induced by x and M(x) is just the set of masked positions in our model's output.

Meng: So they are essentially asking: given what we have generated so far, can we still complete this sequence into something that fits the grammar?

Tom: And then they define a valid update delta as one where this intersection remains non-empty, which means the new set of possible completions still has at least one path that follows the grammar.

Jane: The key challenge is that to check this validity predicate efficiently in a setting where you're proposing multiple tokens in parallel during diffusion decoding.

Lu: The prior work, like Mündler et al.’s work on context-free grammars, shows that checking this requires repeated lexing, deterministic finite automaton construction and minimization and sequential CFG-based validation.

Tom: So the summary is essentially: we need a faster way to calculate that validity predicate without having to rebuild those complex automata every time.

Jane: And EPIC claims it achieves this by changing the pipeline structure to reuse computations and replacing slow automata checks with faster parsing techniques.

The paper's improvements: Tom: So let’s talk about the actual improvements they propose in the paper. They focus on how they solve those three main overhead sources we discussed earlier.

Jane: First, lexical memoization is used to exploit locality by reusing stored results for segments adjacent to masks when that same local context appears again.

Lu: That directly addresses the problem of repeated lexing by not having to calculate the same local structure twice when it looks similar in two different places in the partial output.

Meng: That sounds like a smart way to reduce redundant work, especially if the diffusion model is generating sequences with repeating patterns or structures.

Tom: Next up is the DFA-free validation using Earley-style parsing, which avoids repeated determinization and minimization by checking compatibility directly on the ENFA using an Earley-style graph parser.

Jane: So they are avoiding building and minimizing those rigid finite automata entirely, opting for a more flexible approach that parses the graph as it goes.

Lu: That avoids the huge computational cost of repeatedly converting to and from DFA structures, which is what makes the previous validation so slow.

Tom: And finally, they have relaxed compatible subset selection for parallel commit, which tries to solve the sequential commitment problem by first selecting a subset under a cheaper condition based on intersecting a regular cover FG with the completion automaton induced by x XOR C.

Jane: So instead of committing tokens one-by-one, they find a set of tokens that are likely compatible under a less strict rule first, which allows them to commit multiple candidates together in parallel.

Lu: This is the mechanism that directly addresses the issue where even when the diffusion model suggests several options, the constrained decoder was still doing sequential validation checks on them individually.

Conclusion: Tom: So to wrap things up on EPIC, it’s a framework that systematically reduces those three major overhead sources—repeated lexing, DFA construction, and sequential validation during CFG constraint checking.

Jane: The main result is that they prove this approach preserves the same completable-output criterion as the baseline decoder through three mechanisms: lexical memoization, DFA-free validation with Earley-style parsing, and using a regular cover FG for their relaxed subset selection.

Lu: The experiments confirm that this method keeps the syntactic and functional correctness of CFG-constrained decoding while keeping the overall runtime close to unconstrained decoding.

Meng: For practical use, it means we’re getting a speedup that’s substantial, like reducing relative inference time by up to sixty-seven point five percent on some benchmarks.

Tom: That’s a significant reduction in time, and it shows that we can still get the structural control we need without paying a huge price in performance.

Jane: The paper suggests that this approach has serious implications for how we deploy diffusion models in structured tasks, allowing us to leverage their power more effectively.

Lu: We can start thinking about integrating these kinds of efficient validation methods into other constrained generation pipelines, not just diffusion models but any system where structure matters.

Meng: It moves the conversation toward making these powerful generation tools faster and more practical for real-world applications where speed really counts.

Lalam: For me, this means we can explore more complex and nuanced output structures in our generated content without hitting those severe runtime walls that used to limit our creativity.

Tom: So that’s the summary of EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models. We’ll be diving into another paper next time.

Hyundong Jin Yo-Sub Han

Yonsei University

cs.CL, cs.AI

Submitted: 2026-05-30

Updated: 2026-10-04

Code: https://github.com/hyundong98/EPIC-Decoding

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 81/100

The gist: Controlling language model outputs is essential for ensuring structural validity, reliability, and downstream usability, and diffusion language models are no exception.

Key concepts

Completability Criterion: This is the core question: can a partial output be extended to form a complete sequence that satisfies the grammar? A partial output is completable if there exists at least one valid lexeme sequence from the grammar that contains the current partial string as a prefix.
Lexing Memoization: The method stores results from previous local context checks. If the same small segment appears near a mask again, EPIC reuses the stored result instead of recalculating it. This exploits locality to avoid redundant work during decoding.
DFA-free Validation: Instead of building a full Deterministic Finite Automaton (DFA), EPIC uses an Earley-style graph parser to check grammar validity directly on the Nondeterministic Finite Automaton (ENFA). This avoids the costly process of repeatedly determinizing and minimizing the automaton.

Terminology

Diffusion Model — 18× in this paper · explained in 8 episodes
Ablation — 16× in this paper · explained in 1 episode
Diffusion Models — 13× in this paper · explained in 6 episodes
Benchmark — 10× in this paper · explained in 2 episodes
Verification — 8× in this paper · explained in 2 episodes
Ablation study — 4× in this paper · explained in 1 episode
Benchmarking — 2× in this paper · explained in 3 episodes
Robustness — 2× in this paper · explained in 5 episodes
Consistency — 1× in this paper · explained in 3 episodes
Core — 1× in this paper · explained in 2 episodes
Structural Control — 1× in this paper · explained in 2 episodes
Transformer — 1× in this paper · explained in 2 episodes

Summary

Controlling language model outputs is essential for ensuring structural validity, reliability, and downstream usability, and diffusion language models are no exception. The gist: EPIC reduces repeated lexing, DFA construction, and sequential validation overhead while allowing multiple compatible tokens to be committed together to improve decoding efficiency under CFG constraints.

Problem Formulation

The central question in CFG-constrained DLM decoding is whether a token-level update preserves the possibility of completing the remaining masks into a lexeme sequence accepted by the grammar. A partial output is considered completable with respect to G if L(G) ∩ Cx ≠ ∅, where Cx is the lexeme-sequence completion language induced by x and M(x) is the set of masked positions. A proposed update ∆ is valid when VALIDG(x, ∆) = 1 [L(G) ∩ Cx⊕∆ ≠ ∅]. The goal is to compute this validity predicate more efficiently in the repeated and parallel setting induced by DLM decoding.

How it works

EPIC addresses three main sources of overhead in prior work on CFG-constrained decoding for DLMs, namely repeated lexing, DFA construction, and sequential candidate validation. The framework consists of three main components:

Lexing memoization: This exploits locality by reusing stored lexing results for segments adjacent to masks when the same local context appears again.
DFA-free validation with Earley-style parsing: This avoids repeated determinization and minimization by performing witness checking directly on the ENFA using an Earley-style graph parser.
Relaxed compatible subset selection for parallel commit: This addresses the sequential commit problem by first selecting a subset under a cheaper relaxed condition, defined by intersecting a regular cover FG with the completion automaton induced by x⊕C.

EPIC Decoding Pipeline

The overall decoding procedure involves several steps to recover parallelism while preserving correctness. Algorithm 1 summarizes this process, which includes:

Parallel proposal from the diffusion model for high-confidence candidates C.
Selecting a relaxed-compatible batch B using RELAXEDSUBSETSELECT(x, C, FG, G, Λ).
Committing all candidates in B to x.
If verification fails or commits remain, falling back to sequential rejection sampling for remaining tokens.

Correctness Analysis

The method preserves the same completable-output criterion as the baseline decoder through three mechanisms. Lexing memoization does not approximate or change the represented lexeme sequence language. DFA-free validation checks exact CFG completability over the partial-output graph by searching for a path in Ax whose label sequence belongs to L(G). The regular cover FG used in relaxed subset selection is a regular cover of the CFG language, satisfying L(G) ⊆ L(FG).

Experimental Results

Experiments on three benchmarks using four models show that EPIC preserves the syntactic and functional correctness of CFG-constrained decoding while keeping the overall runtime close to unconstrained decoding. Compared with existing CFG-constrained decoding methods, EPIC reduces relative inference time by up to 67.5% . For instance, on DreamCoder with C++ at 16 denoising steps, the prior CFG-constrained baseline requires 388.60% of the unconstrained decoding time, whereas EPIC requires only 127.34%. The full ablation results show that relaxed subset selection is especially helpful on JSON and that the full configuration gives the best runtime in most settings".

REFERENCES

Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. 2021. Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems.

Yehoshua Bar-Hillel, Micha A. Perles, and Eli Shamir. 1961. On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14:143–172.

Luca Beurer-Kellner, Marc Fischer, and Martin Vechev. 2024. Guiding llms the right way: Fast, non-invasive constrained generation. In Proceedings of the 41st International Conference on Machine Learning.

Jay Earley. 1970. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94–102.

Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. 2023. Grammar-constrained decoding for structured NLP tasks without finetuning. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 10932–10952, Singapore. Association for Computational Linguistics.

Shansan Gong, Ruixiang Zhang, Huangjie Zheng, Jiatao Gu, Navdeep Jaitly, Lingpeng Kong, and Yizhe Zhang. 2026. Diffucoder: Understanding and improving masked diffusion models for code generation. In The Fourteenth International Conference on Learning Representations.

Jonathan Ho, Ajay Jain, and Pieter Abbeel. 2020. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840–6851.

John E. Hopcroft. 1971. An n log n algorithm for minimizing states in a finite automaton. Theory of Machines and Computations, pages 189–196.

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2006. Introduction to Automata Theory, Languages, and Computation, 3 edition. Pearson.

Wonjun Kang, Kevin Galim, Seunghyuk Oh, Minjae Lee, Yuchen Zeng, Shuibai Zhang, Coleman Richard Charles Hooper, Yuezhou Hu, Hyung Il Koo, Nam Ik Cho, and Kangwook Lee. 2026. Parallelbench: Understanding the trade-offs of parallel decoding in diffusion llms. In International Conference on Learning Representations.

Tadao Kasami. 1965. An efficient recognition and syntax-analysis algorithm for context-free languages in time n. Information and Control, 10(2):189–208.

Qinkai Zheng, Xiao Xia, Xu Zou, Yuxiao Dong, Shan Wang, Yufei Xue, Zihan Wang, Lei Shen, Andi Wang, Yang Li, Teng Su, Zhilin Yang, and Jie Tang. 2023. Codegeex: A pre-trained model for code generation with multilingual benchmarking on humaneval-x. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 5673–5684. Association for Computing Machinery.

Dream-coder 7b. https://hkunlp.github.io/blog/2025/dream-coder.

Jiacheng Ye, Zhihui Xie, Lin Zheng, Jiahui Gao, Zirui Wu, Xin Jiang, Zhenguo Li, and Lingpeng Kong. 2025. Dream 7b. https://hkunlp.github.io/blog/2025/dream.

Daniel H. Younger. 1967. Recognition and parsing of context-free languages in time n. Information and Control, 10(2):189–208.

Koo et al. 2024. Automata-based constraints for language model decoding.

Willard and Louf. 2023. Efficient guided generation for large language models. Preprint, arXiv:2307.09702.

Mündler et al., 2026. Constrained decoding of diffusion LLMs with context-free grammars. In The Fourteenth International Conference on Learning Representations.

Mehryar Mohri and Mark-Jan Nederhof. 2000. Regular approximation of context-free grammars through transformation. In Robustness in Language and Speech Technology, pages 251–261.

Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin, Ji-Rong Wen, and Chongxuan Li. 2026. Large language diffusion models. Advances in Neural Information Processing Systems.

NousResearch. 2024. Json mode eval. https://huggingface.co/datasets/NousResearch/json-mode-eval.

Kanghee Park, Timothy Zhou, and Loris D’Antoni. 2025. Flexible and efficient grammar-constrained decoding.

Improvements for AI systems

Attention mechanisms in Diffusion Language Models can be adapted to incorporate parallel token commitment through relaxed compatible subset selection. This allows for committing multiple candidate tokens simultaneously when a joint CFG check fails under exact verification, recovering parallel commitment and preserving the parallelism of DLMs.
Lexical processing overhead is reduced via lexing memoization, which reuses results across similar partial outputs. This directly addresses the bottleneck where prior work incurred repeated lexing, thereby reducing the cost of constructing the partial-output automaton.
Context-free grammar validation is accelerated by replacing deterministic automata with Earley-style parsing to perform DFA-free validation. This avoids the cost of repeated ENFA-to-DFA conversion and minimization, allowing for faster verification of the completable output criterion.

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://github.com/hyundong98/EPIC-Decoding.