DINGO: Constrained Inference for Diffusion LLMs
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
683fc4028de3ffc5838c3fa8
Tarun Suresh
claimed_verified
2025-06-05T07:28:21.749Z
65e7bb35e5e78134ab049942
/avatars/3c0972f0d59e51ebb5c218ee736d4458.svg
Tarun Suresh
user
tarsur909
683fc4028de3ffc5838c3fa9
Debangshu Banerjee
claimed_verified
2025-06-05T17:08:14.771Z
675f9306e0b5cb5bc241e8cc
/avatars/566385d2049b353ea38ddbb9f9105dd0.svg
Debangshu Banerjee
user
debangshubanerjee
683fc4028de3ffc5838c3faa
Shubham Ugare
claimed_verified
2025-06-04T15:03:34.977Z
656c29ed271c5c4e3308a008
/avatars/9b58072230baf3ac941d476d69356fda.svg
Shubham Ugare
user
shubhamugare
683fc4028de3ffc5838c3fab
Sasa Misailovic
683fc4028de3ffc5838c3fac
Gagandeep Singh
DINGO: Constrained Inference for Diffusion LLMs
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
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 autoregressive LLMs formal constraints regular expressions sequential token prediction parallel token prediction dynamic programming constrained decoding output distribution symbolic math generation JSON generation