Diffusion language models write a whole block of text at once. They start from a row of blank "mask" tokens and fill them in over a few rounds, and they can revise their own drafts by re-masking tokens they are unsure of. That ability to revise is what lets them turn extra inference compute into better answers. Separately, these models can now be forced to emit valid JSON or code by intersecting each round's predictions with a grammar. The two capabilities do not fit together. The current grammar-enforcement step picks the single most likely valid string, which is a deterministic choice. Spending more compute, by drawing many samples and keeping the best or by remasking and resampling, depends on randomness. Run a deterministic constrained decoder N times and you get the same answer N times. Bolt remasking onto it and the revision step has no way to know which tokens the grammar wants changed.
This note proposes a single change and studies what follows from it. The change is to replace "find the most probable valid string" with "draw an exact random sample from the model's predictions restricted to valid strings." The same dynamic-programming pass that makes the sampling exact also tells us which committed tokens the grammar finds implausible, and that signal can choose what to remask. The outcome is one constrained sampler that keeps every output syntactically valid, keeps parallel samples diverse, and lets each additional denoising round fix grammar-relevant errors. Its per-step cost is the same as today's constrained decoders. The questions are whether this produces a better accuracy-versus-latency curve on structured-output tasks than the obvious alternatives, and whether constraint-aware remasking does more than confidence-only remasking.
Core Claim
DINGO handles a diffusion model's block of predictions in three steps. It turns a regular-expression constraint into a finite automaton, treats a still-masked position as a wildcard transition, and runs Viterbi dynamic programming to choose the highest-probability path that ends in an accepting state. The paper reports 100% parse rate on JSON-Mode-Eval at almost no added latency (6.43s versus 6.37s unconstrained). Viterbi computes a maximum. If the max over states is replaced with a sum, the result is the forward algorithm. Following it with backward sampling (the forward-filtering backward-sampling procedure from hidden Markov models) produces an exact sample from
$$p_c(x) \propto \prod_{i=1}^{L} p_\theta(x_i \mid z_t)\,\mathbb{1}[x \in \mathcal{L}],$$
Here $x$ is a candidate block of $L$ tokens, $p_\theta(x_i \mid z_t)$ is the model's per-position prediction given the current partially masked state $z_t$, and $\mathcal{L}$ is the set of strings the grammar accepts. The cost is the same as Viterbi's. The same pass also gives each position's posterior marginal under $p_c$. Our claim is that this marginal is a better signal for remasking than raw model confidence. A committed token that the grammar-restricted posterior assigns little mass is one the constraint is pushing against, so it should be revised first. One further detail matters: the lattice has exactly $L$ positions and only accepting end states are allowed. As a result, every sample can be closed within the remaining token budget. This removes the truncation failure that Constrained Decoding of Diffusion LLMs with Context-Free Grammars identifies for parsers that assume unbounded completion length.
We are careful about what "exact" means here. The sampler is exact with respect to the product of per-position predictions, not the model's unknown joint distribution over the block. This factorization is the same one DINGO and ordinary masked-diffusion sampling already use, so it adds no new approximation.
Research Program
The first component is the sampler for regular constraints. We start from DINGO's automaton construction, add sparse forward-backward over the automaton-by-position lattice, and batch N independent backward samples over a shared forward table. N samples therefore cost one forward pass plus N cheap backward passes, which keeps the latency penalty of parallel search small.
The second component is constraint-aware remasking. It reuses the remasking schedule of ReMDM. ReMDM introduced a non-Markovian remasking schedule and confidence-based selection of tokens to remask, and it showed that this turns extra steps into error correction. We change only the selection score. In place of the model's own confidence in a token, the score combines that confidence with the token's posterior marginal under $p_c$, using one mixing weight that we tune on held-out data. ReMDM's remasking ignores grammars, so remasked and resampled tokens can introduce syntax errors. In our version they cannot, because every resample goes through the constrained sampler.
The third component extends the method to context-free grammars, which nested schemas and code require. We use the formal-language intersection machinery of Constrained Decoding of Diffusion LLMs with Context-Free Grammars. That paper intersects a grammar with the regular language of hole-filled completions and reports a median overhead of 4.2ms per token. We swap its validity check for inside-algorithm sampling over the length-bounded intersection. This step is the riskiest. The grammar transformations may blow up the inside tables for large grammars, and we treat a negative result here as acceptable. The regular-constraint results stand regardless.
The stochastic-incompatibility direction enters as a design principle and an analysis target, not as a continuous SDE question. Many continuous-diffusion methods are tied to one regime. Inversion-based watermarks such as Tree-Rings need a deterministic sampler. Accelerated Diffusion Models via Speculative Sampling needs a stochastic one and explicitly cannot run on DDIM. Constrained decoding for discrete diffusion has quietly settled on the deterministic side. We measure what that choice costs by tracking the number of distinct valid outputs among N samples, and by checking whether accuracy keeps rising with N or levels off.
Baselines
The naive reference point is unconstrained LLaDA-8B sampling followed by a parser check. On JSON-Mode-Eval, DINGO reports 57% accuracy for unconstrained LLaDA-8B-Base against 100% with DINGO. We rerun both numbers in our setup rather than copying them.
The strongest existing constrained method is DINGO, together with its context-free counterpart from Constrained Decoding of Diffusion LLMs with Context-Free Grammars, which reports 100% syntactic validity on JSON extraction and gains of up to 7% in functional correctness on infilling. To use DINGO for best-of-N, we give it the most favorable randomization we can find: Gumbel noise added to the per-position log-probabilities before Viterbi (perturb-and-MAP), with the noise scale tuned. All methods get the same model, prompts, block length, step budget N, and selector. The selector is the model's own likelihood, or self-consistency voting on GSM-Symbolic, so that no method benefits from an external reward model. Every method gets the same hyperparameter-search budget. To beat this baseline, our sampler must reach higher functional accuracy at the same wall-clock time for N≥4, with parse rate held at 100%.
The test-time-scaling reference is ReMDM with confidence-only remasking. We run it in two forms, as published and with a final constrained projection step, at matched step counts. For context, it reaches MAUVE 0.656 at T=4096 on OpenWebText, but we found no reported result on Lacuna for ReMDM on JSON-Mode-Eval or GSM-Symbolic.
The ablation that isolates the main ingredient keeps our exact sampler but switches the remasking score back to confidence only. If grammar-aware selection adds nothing over this ablation, the remasking half of the claim fails.
Finally, for practical relevance, we include an autoregressive reference: SynCode on a comparably sized autoregressive model with best-of-N sampling. SynCode reports eliminating 100% of JSON syntax errors with Gemma2-2B. We compare against it by latency, and we do not claim the two model families are matched.
Why not just…?
Why not just sample unconstrained and reject invalid outputs? On flat JSON this is a real threat. If about half of raw samples parse, rejection costs only a constant factor in compute. Two facts work against it. Constrained decoding improves functional correctness beyond parse rate, by up to 7% according to Constrained Decoding of Diffusion LLMs with Context-Free Grammars, so validity is not just a filter. And acceptance rates should fall quickly for nested schemas and code infilling. We report accuracy-versus-latency curves split by schema depth. If rejection matches us on deep schemas, we will say so.
Why not just add noise to DINGO's Viterbi? Perturb-and-MAP is cheap and gives some diversity, so we include it as the main baseline rather than dismissing it. It does not produce samples from $p_c$, and it provides no posterior marginals to guide remasking. Our diversity and best-of-N scaling curves compare the two directly at equal cost.
Why not just run more denoising steps, or use ReMDM unmodified? Scaling Inference Time Compute for Diffusion Models found that adding steps alone quickly stops helping in image diffusion. ReMDM's remasking ignores the grammar, so revisions can break validity. Our confidence-only ablation and the step-matched ReMDM baseline show whether constraint-aware selection is what makes extra steps useful.
Why not just use an autoregressive model with SynCode? This may well be the better choice in production today, and we do not argue around that. The question here is whether diffusion models' parallel revision gives a better latency curve on structured tasks once constraint enforcement and sampling are compatible. The SynCode reference answers that question in either direction.
Proposed Experiments
All experiments use LLaDA-8B, the model DINGO and ReMDM both evaluate. The regular-constraint experiments use JSON-Mode-Eval and DINGO's GSM-Symbolic setup, which constrains the output format of answers. The context-free experiments use NousResearch JSON-Schema extraction and MRI HumanEval. Countdown serves as a search-heavy check. The metrics are parse rate, functional accuracy (schema-field accuracy, final-answer accuracy, pass@1 after selection), number of distinct valid outputs among N, and wall-clock latency per query on a fixed GPU at batch sizes 1 and 16.
Three results would decide the outcome. First, best-of-N accuracy with our sampler should keep rising from N=1 to 16, while Gumbel-perturbed DINGO levels off as its samples collapse onto a few strings. Second, at matched steps, grammar-aware remasking should beat confidence-only remasking on GSM-Symbolic and nested JSON, while keeping parse rate at 100%. ReMDM's ungrammatical remasking cannot guarantee that. Third, per-step overhead should stay within the small range DINGO reports over unconstrained generation. We also report the context-free sampler's table sizes, to show where the inside-algorithm extension stops being tractable. If the first result fails, the deterministic-versus-stochastic framing is wrong for discrete diffusion. If only the second fails, the contribution narrows to a sampler without the remasking component, and we will report it that way.
References
- DINGO: Constrained Inference for Diffusion LLMs
- Constrained Decoding of Diffusion LLMs with Context-Free Grammars
- Remasking Discrete Diffusion Models with Inference-Time Scaling
- Tree-Rings Watermarks: Invisible Fingerprints for Diffusion Images
- Accelerated Diffusion Models via Speculative Sampling
- SynCode: LLM Generation with Grammar Augmentation
- Scaling Inference Time Compute for Diffusion Models