2025/05/29 by Tarun Suresh, Debangshu Banerjee, Suresh, Tarun +7 · 4 citations
Arts and Humanities · Computer Science · #Digital Humanities and Scholarship #FOS: Computer and information sciences #Machine Learning (cs.LG) #Natural Language Processing Techniques #Programming Languages (cs.PL) #Software Engineering (cs.SE) #Topic Modeling
paper · pdf · doi:10.48550/arxiv.2505.23061
openalex publication_date 2025/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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