Constrained Decoding of Diffusion LLMs with CFGs

What is special about multi-region infilling and diffusion LLMs?

Classical LLM generation is strictly left-to-right. The classical setting is to generate the next token to append to a given fixed prefix (PRE). This allowed constrained decoding method to rely on techniques to determine whether an output is a valid prefix of any word in the target language.

How does the method work?

We check partial output validity by computing the intersection of the target language's context-free grammar (CFG) with the language of all possible completions. We first generalize the formal framework of constrained decoding by adapting the standard constrained decoding algorithm to unordered updates of a partial output with arbitrarily many infilling regions.

What are your key techniques?

We formalize the constrained decoding problem for multi-region infilling and diffusion LLMs, shown next to this text. The formalization allows us to reason about the requirements of an incremental verifier for constraining diffusion LLMs and multi-region infilling.

What are the results of your method?

We observe a drastic increase in syntactic correctness, with 99.5% of the generated solutions being syntactically correct. This leads to an increase in functional correctness of up to 7% for the best-performing model. We also show that our method is efficient, less than doubling the decoding time compared to standard methods. We evaluate a number of recent code infilling models on a HumanEval translation into C++.