Continuous Diffusion Models Can Obey Formal Syntax

Diffusion language models offer a promising alternative to autoregressive models due to their global, non-causal generation process, but their continuous latent dynamics make discrete constraints---e.g., the output should be a JSON file that matches a given schema---difficult to impose. We introduce a training-free guidance method for steering continuous diffusion language models to satisfy formal syntactic constraints expressed using regular expressions. Our approach constructs an analytic score estimating the probability that a latent state decodes to a valid string accepted by a given regular expression, and uses its gradient to guide sampling, without training auxiliary classifiers. The denoising process targets the base model conditioned on syntactic validity. We implement our method in Diffinity on top of the PLAID diffusion model and evaluate it on 180 regular-expression constraints over JSON and natural-language benchmarks. Diffinity achieves 68-96\% constraint satisfaction while incurring only a small perplexity cost relative to unconstrained sampling, outperforming autoregressive constrained decoding in both constraint satisfaction and output quality. Diffinity is open-sourced at github.com/large-loris-models/Diffinity.

We focus on the task of making text diffusion models generate outputs satisfying regular expressions. We focus in particular on continuous diffusion models, and show that despite relying on continuous latent spaces, continuous diffusion models can be guided to generate outputs that satisfy regular expressions with minimal impact on quality. Our key contribution is to develop a method for computing, during the denoising steps, the expected probability that the diffusion model's output will satisfy the given regular expression. Our approach outperforms existing methods for regular constraint satisfaction on autoregressive LLMs and discrete text diffusion.