Lookahead-Then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars

Abstract

Diffusion Large Language Models (dLLMs) have demonstrated promising capabilities and are increasingly used to produce formal languages defined by context-free grammars, such as source code and chemical expressions. However, as probabilistic models, they still struggle to generate syntactically valid outputs reliably. A natural and promising direction to address this issue is to adapt constrained decoding techniques to enforce grammatical correctness during generation. However, applying these techniques faces two primary obstacles. On the one hand, the non-autoregressive nature of dLLMs renders most existing constrained decoding approaches inapplicable. On the other hand, current approaches specifically designed for dLLMs may allow intermediate outputs that are impossible to complete into valid sentences, which significantly limits their reliability in practice. To address these challenges, we present LAVE, a constrained decoding approach specifically designed for dLLMs. Our approach leverages a key property of dLLMs, namely their ability to predict token distributions for all positions in parallel during each forward pass. Whenever a new token is proposed by the model, LAVE performs lookahead using these distributions to efficiently and reliably verify the validity of the proposed token. This design enforces reliable constraints by preserving the potential for intermediate outputs to be extended into valid sentences. Extensive experiments across four widely used dLLMs and five representative benchmarks demonstrate that LAVE consistently outperforms existing baselines and achieves improvements in syntactic correctness, while incurring negligible runtime overhead.