DINGO, a dynamic programming-based decoding strategy, enhances diffusion language models by enforcing structured output constraints, significantly improving performance on symbolic math and JSON generation tasks.
Diffusion LLMs have emerged as a promising alternative to conventional
autoregressive LLMs, offering significant potential for improved runtime
efficiency. However, existing diffusion models lack the ability to provably
enforce user-specified formal constraints, such as regular expressions, which
makes them unreliable for tasks that require structured outputs, such as
fixed-schema JSON generation. Unlike autoregressive models that generate tokens
sequentially, diffusion LLMs predict a block of tokens in parallel. This
parallelism makes traditional constrained decoding algorithms, which are
designed for sequential token prediction, ineffective at preserving the true
output distribution. To address this limitation, we propose DINGO, a dynamic
programming-based constrained decoding strategy that is both efficient and
provably distribution-preserving. DINGO enables sampling of output strings with
the highest probability under the model’s predicted distribution, while
strictly satisfying any user-specified regular expression. On standard symbolic
math and JSON generation benchmarks, DINGO achieves up to a 68 percentage point
improvement over unconstrained inference