Technical Summary: Continuous Diffusion Models Can Obey Formal Syntax

Problem Statement

Diffusion language models offer a compelling alternative to autoregressive models by enabling global, non-causal generation processes, which are beneficial for tasks requiring bidirectional context or global revision (e.g., infilling, long-horizon planning). However, a significant limitation persists: the continuous latent dynamics of these models make it difficult to impose discrete syntactic constraints, such as ensuring the output conforms to a JSON schema or a specific regular expression (regex).

In autoregressive models, syntactic validity is typically enforced via constrained decoding, which filters next-token choices to ensure the final output is well-formed. This mechanism relies on maintaining an explicit discrete prefix. In contrast, continuous diffusion models operate on continuous latent representations of the entire sequence at each timestep, lacking an explicit discrete prefix. Consequently, the core primitive of constrained decoding—masking next-token choices that render a prefix uncompletable—does not transfer directly. Existing adaptations for diffusion often target specialized discrete variants or rely on classifier guidance, which requires training an auxiliary model for each specific constraint, a resource-intensive and impractical approach for the vast space of possible regular expressions.

Methodology: DIFFINITY

The authors introduce DIFFINITY, a training-free guidance method designed to steer continuous diffusion language models to satisfy formal syntactic constraints expressed as regular expressions. The approach mirrors the principle of classifier guidance but replaces the need for a trained auxiliary classifier with an analytically computed score.

Core Mechanism

The method operates by modifying the denoising step of the diffusion process. Instead of sampling from the base model's predicted distribution, the sampling trajectory is shifted using a gradient term derived from the probability of syntactic validity.

1. Analytic Score Computation:
   The method constructs an analytic estimate of the probability that a latent state $x_t$ will decode to a valid string accepted by a given regular language $L$.

   • The decoder $Dec(x_t)$ is treated as emitting a unigram distribution over the vocabulary for each token position.
   • The regular language $L$ is represented as a Deterministic Finite Automaton (DFA).
   • To handle the mismatch between character-level regex definitions and token-level model vocabularies, the authors introduce a vocabulary-aligned automaton construction. This aligns the DFA with the model's tokenizer, ensuring all valid tokenizations of a string are accounted for.
   • Using dynamic programming, the method computes weighted transition matrices ($M_1, \dots, M_l$) based on the current unigram distribution. The expected probability $E_{s \sim Dec(x_t)}[s \in L]$ is calculated by propagating the initial state distribution through these matrices and summing the probabilities of reaching accepting states.

2. Guided Sampling:
   The denoising step is modified as follows:
   $$x_{t-1} = \mu_\theta(x_t, t) + \gamma \sigma_t^2 \nabla_{x_t} \log E_{s \sim Dec(x_t)}[s \in L] + \sigma_t \epsilon$$
   Here, $\mu_\theta(x_t, t)$ is the base model's prediction, and the gradient term $\nabla_{x_t} \log E_{s \sim Dec(x_t)}[s \in L]$ acts as a steering force. This gradient pushes the latent trajectory toward regions of the continuous space that decode to syntactically valid strings. The hyperparameter $\gamma$ controls the strength of this constraint.

3. Theoretical Justification:
   The authors demonstrate that this approach approximates conditioning the diffusion sampler on syntactic validity. By using the exact analytical expectation rather than a learned proxy, the method targets the conditional distribution $Pr(x_0 | L)$ without the instability or cost of training a separate classifier.

Key Contributions

1. Training-Free Guidance: The paper proposes a method to steer continuous diffusion models to satisfy discrete regex constraints without training auxiliary classifiers. The guidance score is computed analytically from the constraint itself.
2. Theoretical Framework: The authors provide a formal justification showing that the resulting sampler targets the base model conditioned on syntactic validity, connecting the approach to standard score-based conditional generation theory.
3. Implementation and Evaluation: The method is implemented as DIFFINITY on top of the PLAID diffusion model. It is evaluated on 180 regular-expression constraints covering JSON schemas and natural language patterns.

Results

The evaluation compares DIFFINITY against autoregressive constrained decoding (using GPT-2 variants with the Guidance library) and discrete diffusion models with constrained decoding (LLaDA + DINGO).

• Constraint Satisfaction: DIFFINITY achieves high constraint satisfaction rates, ranging from 68% to 96% across benchmarks.
  • On JSON schema benchmarks, it achieves 68.4% satisfaction (compared to ~77% for GPT-2 Large, but with different padding constraints) and 91.4% Pass@10.
  • On natural language benchmarks, it achieves an average satisfaction rate of 92.9%, significantly outperforming GPT-2 Large (20.5%) and comparable to LLaDA+DINGO (near 100%).
• Quality and Perplexity:
  • Unlike autoregressive constrained decoding, which often suffers from the "infinite repetition trap" (stalling in low-probability regions) and distorts the model distribution, DIFFINITY maintains high text quality.
  • DIFFINITY incurs only a small perplexity cost relative to unconstrained sampling. For natural language benchmarks, the perplexity of DIFFINITY (60.0) is comparable to the unconstrained base model (61.6), whereas constrained autoregressive models often show higher perplexity or lower fluency.
  • In terms of fluency, DIFFINITY (35.8) surpasses GPT-2 Small and Medium and is comparable to GPT-2 Large.
• Comparison with Classifier Guidance: Standard classifier guidance (trained on noisy latents) performed poorly, achieving 0% satisfaction on JSON benchmarks and very low rates on natural language tasks, highlighting the difficulty of learning these discrete constraints via auxiliary classifiers.
• Computational Overhead: DIFFINITY incurs a latency of roughly 2–3 times that of unconditional generation, primarily due to the computation of dense sums over automaton transitions. Memory usage scales with the number of transitions and states in the aligned automaton.

Significance and Claims

The paper claims that continuous diffusion models can be effectively steered to obey formal syntax without the need for training or the distributional distortions often associated with constrained decoding in autoregressive models.

• Robustness: DIFFINITY is shown to be more reliable than autoregressive constrained decoding, particularly under finite token budgets where autoregressive models may fail to complete valid sequences.
• Distribution Preservation: The method successfully enforces constraints while preserving the underlying probability distribution of the base model, avoiding the "ad hoc" heuristics that degrade output quality in other constrained generation methods.
• Generalizability: While currently limited to regular constraints, the framework provides a principled, training-free mechanism for steering continuous diffusion models, offering a viable alternative to the resource-heavy training of classifiers or the structural limitations of discrete diffusion constrained decoding.

The authors conclude that while the current computational overhead is non-trivial, the ability to generate syntactically valid structured outputs with high fidelity suggests a promising direction for structured generation in diffusion models. Future work is suggested to focus on memory-efficient data structures and kernel optimizations to reduce latency.