LAVE: Constrained Decoding for Diffusion Language Models (ISSTA 2026)

Diffusion language models (DLMs) generate tokens in parallel from a masked sequence, offering high‑throughput decoding but often fail to satisfy syntax constraints when producing formal languages such as source code, JSON, or SMILES. For example, Dream‑7B exhibits a 23.8% syntax error rate on the HumanEval‑CPP benchmark, indicating that existing DLMs struggle to reliably generate syntactically correct outputs.

Constrained decoding is a common remedy for autoregressive models because their left‑to‑right generation always yields a complete prefix that can be directly checked by a grammar parser. In contrast, DLMs produce incomplete prefixes containing [MASK] tokens, which standard parsers cannot evaluate.

The paper proposes LAVE (Lookahead‑then‑Verify). After the model predicts a token for a [MASK] position, LAVE temporarily writes the token into the output, extracts the rightmost generated token to form the current incomplete prefix, and samples a small set of high‑probability completions for the remaining [MASK] slots using the model’s token distribution. Each completed candidate, now free of [MASK], is fed to a context‑free‑grammar parser (e.g., Earley parser) to verify whether it can still be expanded into a syntactically valid full output. If any candidate passes, the token is accepted; otherwise the token is rejected and regenerated. return a [MASK] b ? [MASK] : b ...... A valid completion could be: return a > b ? a : b ...... Only candidates without [MASK] are sent to the parser, which checks them in parallel. Acceptance occurs when at least one candidate is verified; rejection triggers a new token generation attempt.

Experiments on four representative DLMs—LLaDA‑8B, LLaDA‑1.5, Dream‑7B, and DiffuCoder‑7B—cover generation tasks for C++, Java, Go, JSON, and SMILES. Results show that LAVE raises syntax correctness to nearly 100% across all models and tasks. Functional correctness also improves; for instance, Dream‑7B’s C++ functional correctness rises from 25.6% to 33.5%. The additional inference cost is modest, with only about a 3% increase in average runtime for JSON tasks and even a slight reduction for SMILES due to fewer irrelevant natural‑language tokens.