Title: EPIC: Streamlining and Parallelizing Inference for Diffusion Language Models under CFG Constraints

Abstract

Ensuring the structural integrity, reliability, and practical applicability of language model outputs is a critical requirement, a need that extends equally to diffusion-based language models. While recent breakthroughs in decoding techniques have expanded output control to encompass context-free grammar (CFG) constraints, current approaches suffer from significant performance penalties. Specifically, these existing methods can operate up to four times slower than unconstrained decoding. More critically, they erode a primary benefit of diffusion models over autoregressive ones: the capacity for parallel decoding. This inefficiency stems from the substantial overhead introduced by sequential validity checks during parallel generation processes.

To overcome these hurdles, we introduce EPIC, a novel framework designed for efficient CFG-constrained decoding. EPIC enhances computational efficiency through a three-pronged approach: implementing lexing memoization, adopting Earley-style parsing for validation rather than deterministic automata, and employing a relaxed compatible subset selection mechanism for parallel token commitment. By minimizing redundant lexing and validation costs, EPIC enables the simultaneous commitment of multiple compatible tokens.

Our empirical evaluation across four models and three benchmarks demonstrates that EPIC significantly outperforms state-of-the-art CFG-constrained decoding methods. Specifically, the framework achieves a reduction in inference time of up to 67.5% and cuts additional overhead by as much as 90.5%. The source code for our implementation is publicly accessible at https://github.com/hyundong98/EPIC-Decoding.git.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC