DINGO: Constrained Inference for Diffusion LLMs
Authors: Tarun Suresh
Debangshu Banerjee
Shubham Ugare
Sasa Misailovic
Gagandeep Singh
Venue: NeurIPS 2025 poster ()
Keywords: Constrained Decoding
Diffusion LLM
Primary area: deep_learning
TL;DR: We propose the first constrained decoding algorithm for diffusion LLMs.

Abstract: Diffusion LLMs have emerged as a promising alternative to conventional autoregressive LLMs, offering substantial potential for improving runtime efficiency. However, existing diffusion models fail 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, which generate tokens sequentially, diffusion LLMs predict a block of tokens in parallel. This parallelism makes traditional constrained decoding algorithms, designed to enforce constraints with 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 adhering to any user-specified regular expression. On standard symbolic math and JSON generation benchmarks, DINGO achieves up to a $68$\% points of improvement over unconstrained inference.  The code is available at [**DINGO**](https://github.com/uiuc-focal-lab/DINGO).

DINGO: Constrained Inference for Diffusion LLMs
Tarun Suresh", Debangshu Banerjee; Shubham Ugare, Sasa Misailovic, Gagandeep Singh Department of Computer Science, University of Illinois Urbana-Champaign
Abstract
Diffusion LLMs have emerged as a promising alternative to conventional autore- gressive LLMs, offering substantial potential for improving runtime efficiency. However, existing diffusion models fail to provably enforce user-specified formal constraints, such regular expressions, which makes them unreliable for tasks that require structured outputs, such as fixed-schema JSON generation. Unlike autoregressive models, which generate tokens sequentially, diffusion LLMs predict a block of tokens in parallel. This parallelism makes traditional constrained decod- ing algorithms,, designed enforce constraints with 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 seebbttioo-peeeeving DINGO enables sam- pling of output strings with the highest probability under the model's predicted distribution while strictly adhering to any user-specifies regular expression. On standard symbolic math and ISON generation benchmarks, DINGO achieves up to 68% points of improvement over unconstrained inference. The code is available at DINGO
Introduction
Autoregressive L.MMs demonstrate impressive performance across a wide range of tasks, including
logical reasoning [Pan et al.) 2023). theorem proving (Yang et al. 2023], and code generation (et]
al. 2021]. However, because they generate one token at a time, they can be slow when producing long responses. Recent work has explored using diffuusion models to accelerate token generation by predicting blocks of tokens in parallel. For tasks such as logical reasoning, where the LLM output is fed into symbolic solvers like Z3 [Fedoseev al. 2024 syntactic correctness of the output is essential. Prior works [Pesia et al.) [022] Ugare et al.) 2222a Loula et al.) 2025] have shown that LLMs frequently make syntactic and semantic errors, often generating structurally invalid outputs that cause downstream tasks to fail due to unparsable input. To mitigate this issue, constrained decoding has emerged promising approach that provably ensures structural correctness by projecting the LLM output onto a set of valid strings, typically defined by a regular grammar or, more generally, context-free grammar (CFG). However, existing constrained decoding techniques are designed specifically for autoregressive LLMs and rely on their step-by-step generation process to prune invalid tokens that cannot lead to structurally valid outputs. At each generation step, the decoder selects the gighest-probablig token from the set of valid options, based on the LLM's output distribution.
In contrast, diffusion LLMs predict blocks of tokens in parallel without sequential dependencies, making existing constrained decoding algorithms incompatible. Furthermore, greedy token selection in autoregressive models maximizes the probability locally at each step but be suboptimal over an entire sequence, potentially leading to structurally valid yet lower-quality outputs that fail to maximize the overall probability of valid strings. Lew et al. (2023) Park al. (2224)) have reported this distortion in output distribution for autoregressive LLMs under constrained decoding. Therefore,
Equal contributing authors ordered randomly
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

any constrained decoding algorithm for diffusion LLMs should also ensure that enforcing formal constraints does not come at the cost of distorting the true output distribution.
Diffusion L.MSs generate a block of tokens starting from a fully masked string composed of special mask tokens 1, and iteratively unmask or more tokens each step until producing a fully unmasked output. Each unmasking step (referred to as a diffusion step) can unmask tokens arbitrary positions in the block, with no left-to-right sequential dependency across steps. As a result, designing constrained decoding for diffusion LLMs requires addressing the following:
Key Challenges:
RQ1: Efficiently detecting invalid tokens and restricting token choices at each diffusion step to ensure the final unmasked string is always structurally correct.
RQ2: Ensuring the generated token block maximizes the probability under the output distribution.
Contributions: We present the first constrained decoding algorithm for diffusion LLMs, making the following contributions:
We introduce DINGO, the first constrained decoding algorithm for diffusion LLMs that supports any user-specified regular expression. DINGO provably ensures that the output string is always a valid prefix of some string in the target regular language.
DINGO uses dynamic programming to ensure that the output string achieves the maximum proba- bility among all valid strings over the output block with respect to the true output distribution. This approach guarantees scalability while maintaining optimality (c.g., maximizing the probability), in contrast to existing methods such as (Park et al. 2024b), which rely on repeated resampling. Resampling-base methods are computationally expensive and unsuitable for practical deployment.
Extensive experiments on multiple open-source diffusion LLMs and benchmarks show that DINGO significantly outperforms standard unconstrained decoding, achieving up to 68% improvement on challenging tasks such as the GSM-symbolic benchmark for symbolic reasoning [Mirzadeh et al. 2024 and a JSON generation benchmark [NousResearch]] 2024).
Roadmap: We provide the necessary background in Section formalize constrained decoding for diffusion LLMs in Section 3 describe the DINGO algorithm along with its correctness and optimality proofs in Section 4 and present experimental results in Section
2 Background
Notation: In the rest of the paper, we use small case letters r for constants, bold small case letters (x) for strings, capital letters X for functions, for string concatenation, [x| to denote the length of æ.
Diffusion LLM:
The diffusion L.M Cm.. V - V" processes finite strings p E V over finite alphabet V including the special mask symbol I and produces the output string E V Typically p r with length n represents the entire output string of L where p is the input prompt. r is the
response, and m + l n. L can compute the response over single block Austin et al. [2021]
Ye ct al. 2025), Nie et al. [2255] in pure diffusion setup or over multiple blocks i.c. T1 T2 -h in
semi autoreeessvee setup where different blocks are computed sequentially from left to right (Han
et al.
2023 Arrilla et al. 2025)
At high level, to compute a block of tokens of size d, L pads the prompt p with fully masked suffix, resulting in ..d, where d denotes a sequence of d special mask tokens 1. The model then iteratively unmasks subset of these tokens at each step, ultimately producing fully unmasked output string o. Each such step is referred to as a diffusion step, and L typically applies T diffusion steps to compute o. The number of steps T' usually a fixed, predetermined constant satisfying T < d, which enables greater scalability compared to their autoregressive counterparts.
Definition 2.1 (Diffusion step). A diffusion step fx : V x N + V applics a single unmasking step to a masked (or, a partially masked) string of length to compute unmasked) string of the same length. The first argument represents the input string appended with the output block while the second argument dictates the number of masked tokens in the output string.
masked (or, possibly
Each diffusion step fn consists of two components: transformer step No : V' - |V
which predicts the token probability distribution at each output position, and mask prediction step

---

which determines which token positions to remask. Typically, for each position, the mask prediction step identifies the token with the highest probability and compares these maximum probabilities across positions. .M, then greedily remasks positions with relatively lower max pro-babbyyyy scores (Nie et al. 2025] and produces the modified token distribution. Further details about Nr, and M,, are in Appendix A
M, IR IRIV N- + RIV
Formally, the diffusion step is defined as (z = (M,
where Dm... I g!V|xa + V is the decoder. We now use the diffusion step to formally define the diffusion LLM for generating strings of length n in either a single-block or multi-block setting.
Definition 2.2 (Single block diffusion LLM). A diffusion LLM that outputs a block of d tokens given an input E V using 7 diffusion steps is function Lm. V - V", where m + d, and the output is 0 = p r = Lm.. (p). Let fn V x N- - V denote a single diffusion step. and let Pm,.: V + 4 be the padding function. Then the output is computed
L (p) = Zr,
where: Zo mm, (p) p- 1 and
fn (1) 1) for 1 S i T.
Definition 2.3 (Semi Autoregressive diffusion LLM). In the semi- autieeevtreeressvvve setup, given input P E V the output o E Vm++xx is generated over & blocks, where each block is computed via call to the single block diffusion model. The output of the i-th diffusion model call is z; (z, (x;- with Zo p and the final output o = Ik- The input and output lengths for each block are defined as 1) d and n, m i d for all S i < k.
my m
DFA and regular expression: We provide necessary definitions regarding regular expression.
Definition 2.4. (DFA) A DFA DR (Q, Σ, 6, go. F') for regular expression R is finite-state machine that deterministically processes input strings to decide membership in the language L(R) C E' defined by R. It consists of states Q, a start state qo. set of accepting states F, and transition rules : Q x - Q and the input alphabet E.
Definition 2.5 (extended transition function). The extended transition function 8' : Σ" x Q + Q maps input (w,q) to the resulting state gr. obtained by sequentially applying o to each character G in w = c ... Gw/ starting from state q.
Definition 2.6 (Live DFA states). Given DFA (Q,2, go, F), let Qi represent the set of live states such that g E Qt iff 3w E "x s.t. (w, E F.
3 Optimal Constrained Decoding
We formalize the correctness and optimality of constrained decoding for any diffusion LLM with respect to a user-defined regular expression R. Given R, let L(R) C Ex C (V\.) denote the set of all finite strings that satisfy the expression R.
Correctness: A valid constrained decoding algorithm must ensure that the output string always remains a valid prefix of some string in L(R), effectively eliminating any output that cannot be extended into valid completions. By treating the output string as a prefix rather than a fully completed string, we can accommodate the semi-autoregressivy setup, where blocks of tokens are appended to the right of the current output. This approach avoids prematurely rejecting strings that may lead to valid completions in subsequent blocks and also aligns with the notion of correctness adopted in existing constrained decoding algorithms for the autoregressive LLM [Ugare et al. 2024b Banerjee et al. 2025a). We denote the set of all valid prefixes of (.R) as (RR)..
Each diffusion step f.. produces a string over the vocabulary V, which may include one or more special mask tokens 1. These tokens act as placeholders for actual (non-mask) tokens that will be filled in during future diffusion steps. To account for these future substitutions, we define a masked (or partially masked) string valid if there exists replacement for all mask tokens such that the resulting fully unmasked string a valid prefix of some string in L(R). To formalize this notion, we first define the substitution set, which represents the set of fully unmasked strings obtained by replacing all mask tokens in a masked or partially masked string. We then use substitution sets to define the correctness of the constrained decoder.
Definition 3.1 (Substitution Set). Given masked (or, partially masked) string E V*, the substi- tution set S(x) C (V (1))" the set of all fully unmasked strings obtained by replacing each occurrence of 1 in x with token from V \ {1}. For unmasked strings with no 1, S(x) {z}
3

---

Definition 3.2 (Correctness of Constrained decoder), Any deterministic decoder Dm,,, R + 4 is valid constrained decoder if, for all n N, input prompt p and for any output distribution D, provided as probability vectors each of size [V], there exists unmasked string the substitution set S m. (P.)) of the decoded output such that actual response valid prefix i.e., E (R((R).
x is
Optimality: Given distribution D, and regular expression R. the set of decodings that valid prefixes for R (as defined in Definition 3.2) may not be unique. An optimal constrained decoder selects, among all valid strings, the string that maximizes the probability under D,, The output distribution D, is represented as n vectors V1. vi,.... Un- each of size [V], where the i-th vector v; captures the token distribution at position i. For any masked position j. v assigns probability I to the mask token 1. and to all other tokens. Assuming the input prompt has length m, the token distribution of the actual response is given by Um+ly..... Un- For any output string r bm+1 ln- let P(r 1m++1 Un denote the probability of the string r under the output distribution. Then, the optimal constrained decoding can be formalized follows:
arg max P(r Um++ Un) s.t. i V (xx S(r)) A (x Lp(R))
(1)
Since the token distributions Um+1, are independent across positions, the probability of the string can be written as P(r Um+1... vn.) mm==++ 8; [t:]]] assigned to token i by the vector U; Using this, we can rewrite the optimization problem from Eq. as follows:
where (t:) denotes the probability
n II (=++11
arg max
vilty s.t. Ex V*.(x E S(r)) (x (r(R))
(2)
r=
DINGO Algorithm
The search space for Eq. 2 exponential- [V1 where d denotes the block length, making naive enumeration- bbaed methods impractical. To efficiently retrieve the optimal output string r* from Eq. 2 DINGO leverages dynamic programming. Given regular expression R. it first modifies the transition function to handle the mask symbol 1, which is then utilized during inference.
4.1 Precomputation
For user-provided R and the corresponding DEA DR (Q, E, qu. F)) (referred to character- level DFA) with Σ C (V 1), we first construct the token-level DFA D, = (Q, (V \)) &,, Yo, F) recognizing (RR) over strings generated by L. A single token t (V \ L) span across multiple characters in f.e. t = Ci ... where G; E Σ. To construct the token-level transition function Q (V) I) + Q, we process each token & E (V \ L) and state q Q by executing the character-level DFA DR on the sequence of constituent characters -..-.. Ct, starting from state q, and record the resulting state Gr. We then define the token-level transition as 6. t) dr-
To handle the special mask token E V, we define the transition function 51 Q + 2 For each state 9 E Q, 51 (q) returns the set of states Q, Q that are reachable via single token transition using 6, Formally, دo (g) = (q' q' de t); ( {)). Since ô1 may return multiple states, resembles the transition function of non-deterministie finite automaton (NFA). The precomputation step combines 5, and d_ to define :
29, which is used in the dynamic programming step.
Using the token-level DFA D,, also construct the set of live states Q C (Definition 2.6p.
())(g.0) (2)(2)
f (1). ift=1.
8(q, t)
4.2 DINGO Dynamic Programming
Before going into details, we present two key observations that lead to the decoding algorithm.
'More precisely, if there exists at least one r that is valid prefix (i.e., r E LP(R)), then constrained decoding is always capable of retrieving one of them.

---

Observation 1: Determining whether a fully unmasked string : ti...ta E (V prefix is equivalent checking whether the resulting state gr, obtained by applying to the sequence l.... La starting from Zo. is live. Similarly, for partially (or fully) masked string r applying ō to 1....a, La yields a set of resulting states Qr- In this case, _ is valid prefix if and only if any state q E Q, is live (Definition 3.2)
\ 1 is valid
f1...
Observation 2: For optimality, it is sufficient track the maximum probability path from the start state go to each resulting state in Qr. Once these paths are computed, we select the one with the highest probability that leads to a live state. The corresponding string is the optimal string r* (or one of the optimal strings in case of multiple optimal solutions) for the optimization problem in Eq.
Based on these observations, the main challenge is to efficiently maintain the maximum probability path to each reachable state in Qr- We address this using dynamic programming (DP) approach, similar traditional graph DP algorithms such [Forney] 1973).
DP states: For each token position S i S d in the block, the DP maintains: a) WLt (t, q). which records the maximum probability with which state E Q can be reached from the start state go via transitions on some token sequence with length 2; and b) Pr[g. a]. which stores the last transition, i.e. the previous state and the corresponding token, that led to the maximum probability stored in W W[igg] If a state q is unreachable, then Wii q] = O. Formally, given the probability vectors U1 Us.....U, Wii is defined as follows where 8 is extended transition function (Definition 2.5
W ql = max f2....
,, s.t. q = 67 (fm-1 ........ tn. (o) j=1
DP state update: Given the states token position i. we describe the computation for position i+ 1. Initially, Wii g] = 0 for all q * qo. and ii, qo] = 1 (lines 3 in Algo. [}. To compute W[i + 1. 9] for each q E Q. consider all tokens E V (including the mask token 1)) that can transition to q from some previous state o' at step i. Among all such transitions, we select the one with the highest probability and add the maximum probability path reaching q' at step i. The value Prii + 1, q] stores the previous state and token that lead to the maximum probability path to step i +1 (lines 12 - 15 in Algo. D. Formally,
max (1+ s.t. g E d(d'() tEV
V4+ (g. d')
W + 1, = max W [i, x (z, P'EQ
of q. are not connected
Path construction: We consider all reachable states g at the end of the block with W(d, q] > 0. Among the live states şi E Qi satisfying this condition, we select the state Qmax with the highest value of W(d.gr 4. We then use Pr to iteratively reconstruct the token sequence backward that forms the maximum probability path starting from 9max and ending at go (lines 20 22 in Algo. D.
Semi-autoregressive setup: In semi- autoorruoorereiivve setup, we may not start from DFA start state Yo since one or more blocks of tokens 11 F, may have been generated in left the current block. Provide the string F1 ... .Ti ends at a live state qt, we can apply dynamic programming approach with the intializtion W[0, [0, a] = 1 and W00, g] 0 for all state q + qi- Details are in Appendix D
4.3 Correctness of DINGO
Proposition 4.1. [Correctness] Given any regular expression R, input prompt p E VM,, block length d output distribution D U1 ... d. if T. (V 1)a + O and ~ Um+1 Un be the decoded string, then l E V (x E S(r) A (x E (R)) holds.
Proof sketch: DINGO ensures that if a state E Q is reachable in i tokens, then Wli g] > 0 for all 1 i d. Since Lp (R) n (V (1)d # (). there exists a state qi E Qi that is reachable in d steps. Therefore, W 9maz) > O (see line 16 in [). Consequently, there exists sequence
S(r)
such that 6" (z, 9o) = qmar E Qi, implying that x E (R)).. Formal proof is in Appendix
Proposition 4.2. [Optimality) Given any regular expression R, input prompt p E V block length d, output distribution Dm+dd = U1 ....Um Un if (R) n (V \ 1)d # {} and r" ~ -mmt1... Un+d be the decoded string, then for any valid string r' satisfying 3o V 77.(xE (EE A (x E (R.)))
P(r' Um+1 Un) S P(r" Um+1.... U.).
Proof Sketch: Formal proof is in Appendix B
5

---

Algorithm DINGO DP
Require: 9o. block length d. probability vectors UI....U, for the current block, Qt. Q. 6.
I: W "0 q] f- 0 for all (9 E Q) A (q + go)
2: W 0. q0] <-
3: Pr[0.g]
(None, None) for all (q
Initialization of the DP
Vi {} for all E [l....,d]
maximum token probability transtion (4' + q) position
5: T; - {) for all E {1....,d]
D. token for the maximum probability transition (4' - g)
6: forie (1,.... d) do
7: for Q) do
8:
for do d' 8(g.1)
9:
10:
V. + MuxTransition((;.440
11:
for
f {1, (E.......dd) d) do
P DP computation loop
12:
for (q Q) (4' 4 E Q) do
13:
if W[ 9) Wi 1, x V.(g. (') then
14:
W 1 Prit. g + TTl.l( ())
Wi 1,9 V((gg))
Update maximum probability path to g
15:
b Update the parents accordingly
16: Qunnz <- arg max Q Wld. d
17: if W(d, [max] = 0 then
> No valid prefixes
18:
return None, Grax
19: r' + --,, Jours t Qmaz
20: for ffd 1 do
b Decoding the optimal string r'
21: leurr, + Pr(f, qcurr]
22: r" +-*
23: return reverse(r"), Gmaz
4.4 DINGO algorithm
Algorithm presents DINGO steps. The two main loops dominating its computational complexity involve calculating transition costs and performing the DP updates respectively.
First, for each of the d time steps, the algorithm computes the optimal single-token transition costs Vi(ge.9.) between all source states qa E Q and target states q E Q. This is achieved by iterating through each source state qa. each token & E V, and then for each state qe reached from qs via (i.e., qe E 8(qa,))) updating the cost Vi(ga, qt) with v.(d if better. The complexity for this part is Old (1Q) + Σ Eg.eQ Σiev 18(qs, ())). The sum Eg. E. 18(4,, t) represents the total number of transitions, N Q(QQ) IVI+ + NN).. where N is the maximum number of states reachable via the 1 token. Thus, this part takes Odd (1Q)2 + (Q-IIIV))
Second, the core dynamic programming update calculates Wii, for each diffusion step i and state q. This involves iterating over d diffusion steps, |Q] current states q, and for each g, considering all [Q] possible previous states q' This leads to a complexity of O(d 1Q(?).
Combining these dominant parts, the total complexity is O(d (IQ Q (V] + +d- -d-1Q(3) which
simplifies to O(d ([Q)2 + (V)).. This can be expressed as O(d [Q] (IQ1 + +IVI)..
4.5 Context freee grammars and reasoning
Currently, DINGO operates with regular grammars. For context-free grammars (CFGs), existing works [Ugare et al. (024b) perform greedy pruning of invalid tokens in a left-to-right manner. The same greedy generation strategy can also be applied to diffusion models, albeit at the cost of optimality. We already have an implementation of greedy left-to-right generation (referred as Greedy Constrained in Section which naturally extends to CFGs. However, as demonstrated by our experiments, greedy decoding (also employed more recent works Mündler et al. (2255) yields significantly worse performance compared to the optimal constrained decoder DINGO for regular expressions. Moreover, DINGO already supports 20025), allowing the inclusion of reasoning tokens that do not conform to the output grammar.
grammars Banerjee et al.)

---

5 Experiments
In this section, we evaluate DINGO on a math reasoning task (GSM-Symbolic Mirzadeh et al. (0224)
and a schema-based text-to-JSON task (JSONModeEval [NouRResaarch 2024 ) and demonstrate
significant improvement over baselines. In both tasks, we use the
(LLaDA-8BB
B) Nie et al. [025]. LLaDA-SB-Instre
(LLaDA-8B-I) Nie et al. 2023 Dream-vO-Base-77
Dreeam-B7B))
Ye et al.
2025 and Deraam-v--Instrcct
(Dream- Ye et al.
[025 models.
Experimental Setup. We experiments on 48-core Intel Xeon Silver 4214R CPU with 2 Nvidia RTX A5000 GPUs. DINGO is implemented using PyTorch Paszke et al. [2019] and the HuggingFace transformers library Wolf al. [220)]. The token-level DFA is implemented in Rust using highly efficient regex-DFA library to minimize overhead during DFA construction and LLM inference. We report the mean number of DFA states and transitions well the offline pre-computation time in
Appendix
Baselines. We compare DINGO against unconstrained diffusion LLM generation. Furthermore, to highlight the benefit of optimal constrained decoding with DINGO, we implement a constrained decoding strategy Greedy Constrained that mirrors existing autoregressive constrained generation methods [Willard and Louf (2023), Ugare et al. [2024b]. Greedy Constrained iterates over the diffusion block and at each position? computes a binary mask m E {0, 131V| based on the DFA, specifying valid tokens (m 1) and excluded tokens (m 0). Decoding is then performed on the masked probability distribution m @ 14 where @ denotes element- dlement-wise multiplication. Since in some cases, Unconstrained outperforms Greedy Constrained, we also report Best of Greedy + Unconstrained, which takes the better result of the two approaches for each problem in the dataset.
We evaluate DINGO on GSM-Symbolic Mirzadeh et al. (2024) dataset, which consists of reasoning-basee math world problems where numerical values and names are replaced by symbolic variables. Diffusion LLMs are tasked with generating correct symbolic expression solutions to those word problems. We evaluate correctness by using the Z3 solver (De Moura and Bjørner 2008) to check if the final expressions from the LLM generations are functionally equivalent to the ground truth expressions. We set the generation length to 128, number of blocks to 8, and total diffusion steps to 64 and prompt the LLMs with 4-shot examples from GSM-Symbolic (Mirzadeh ctt al. 2024] (the prompts can be found in Appendix F... We initialize DINGO and Greedy Constrained with regex (shown in Appendix F22 that permits math expressions wrapped in and and natural language text outside these expressions for reasoning as done in CRANE Banerjee et al.
Math Reasoning:
2025a
Table D compares the performance of DINGO with the baseline methods. The Accuracy (%) column reports the percentage of functionally correct LLM-ggnerated expressions, Parse (%) indicates the percentage of syntactically valid responses (i.e., expressions without invalid operations), and Time provides the average time in seconds taken to generate a completion.
As displayed in the table, DINGO significantly improves functional correctness over the baselines. For instance, for LLaDA-8B-I, DINGO outperforms unconstrained generation by 13 percentage points and Greedy Constrained generation by 5 percentage points. Furthermore, DINGO achieves 100% syntactic accuracy across all models evaluated. On the other hand, unconstrained and Greedy Constrained generation make many syntactic errors, especially for non-instruct tuned models. For these cases, generation with Greedy Constrained results in responses that are syntactically valid pre- fixes but not syntactically valid by themselves. We present case studies in Appendix F3 Importantly, DINGO is extremely efficient, introducing marginal overhead compared to unconstrained generation.
JSON Generation: We further evaluate DINGO on text-to-JSON generation task JSON-Mode- Eval, which conists of zero-shot problems specifying a JSON schema and request to generate a ISON object that contains specified contents. Generating JSON that adheres specified schema is extremely important for applications like tool use and function calling Ugare et al. [2024b), Willard and Louf 2023). We evaluate the correctness of ISON generated by an LLM by first evaluating whether the JSON string can be parsed and converted to valid JSON object. We further evaluate whether the generated JSON is valid against the schema specified in the prompt. We set the generation length to 128, number of blocks to 1, and the total diffusion steps to 64. For the constrained generation methods, we convert each problem's 's JSON schema into corresponding regular expression and guide the diffusion LLM to generate output conforming to that regex.
7

---

Table 1: Comparison of constrained and unconstrained generation methods on GSM-Symbole
Model
Method
Acc. (%)
Parse ( (%)
Time (s)
Unconstrained
25
54
9.06
Greedy Constrained
30
75
9.31
LLaDA-8B-B
Best of Greedy Unconstrained
30
75
9.08
DINGO
31
100
9.22
Unconstrained
19
35
23.78
Greedy Constrained
27
98
23.97
LLaDA-8B-I
Best of Greedy Unconstrained
27
98
23.8
DINGO
32
100
23.92
Unconstrained
17
33
16.02
Greedy Constrained
21
41
16.13
Dream-B-7B
Best of Greedy + Unconstrained
21
41
16.04
DINGO
23
100
16.19
Unconstrained
32
61
23.89
Greedy Constrained
34
93
24.01
Dream-I-7B
Best of Greedy + Unconstrained
34
93
23.9
DINGO
36
100
23.91
Table presents the results of our experiment. The Parse (%) column reports the percentage of syntactically valid LLM generations while the Accuracy (%) column reports the percentage of generations that are both syntactically valid and valid against their respective schemas. Notably, DINGO achieves 100% schema validation and syntactic accuracy, while baseline methods struggle in many cases to generate valid JSON. We attribute this the fact that Greedy Constrained may distort the distribution through its greedy approximation and can only generate a valid prefix, not fulll parsable generation Park et al. [2024a]
Table 2: Comparison of constrained and unconstrained generation methods for JSON Schema.
Model
Method
Acc. (%)
Parse %%)
Time (s)
Unconstrained
57
59
6.37
Greedy Constrained
80
80
6.47
LLaDA-SB-B
Best of Greedy + Unconstrained
88
90
6.41
DINGO
100
100
6.43
Unconstrained
87
91
6.7
Greedy Constrained
78
79
6.81
LLaDA-8B-I
Best of Greedy Unconstrained
99
99
6.73
DINGO
100
100
6.78
Unconstrained
15
18
5.31
Greedy Constrained
23
23
5.41
Dream-B-7B
Best of Greedy Unconstrained
32
35
5.34
DINGO
100
100
5.45
Unconstrained
85
87
6.4
Greedy Constrained
30
30
6.51
Dream-I-7B
Best of Greedy Unconstrained
91
93
6.43
DINGO
100
100
6.55
Comparison with finetuning and rejection sampling: We compare DINGO with two other possible baselines: (a) fine-tuning on a specific dataset's JSON schema, and (b) rejection sampling, where we iteratively sample responses and check them against regular expression (referred to as the Sample-Filter approach). For the fine-tuning approach, we perform supervised fine-tuning (SFT) dataset of 20k natural language JSON schema JSON instance pairs] Azinn (2024). We used the dl codebase Zhao al. 2025) for the SFT implementation. While for the rejection sampling approach,

---

Table Comparison of DINGO with rejection sampling and finetuning.
Model
Method
Acc. (%)
Parse (%)
Time (s)
Unconstrained
57
59
6.37
Greedy Constrained
80
80
6.47
LLaDA-8B-B
Sample-Filter
68
69
13.00
Format Fine-Tuning
60
60
6.41
DINGO
100
100
6.43
Unconstrained
87
6.70
Greedy Constrained
78
79
6.81
LLaDA-8B-I
Sample-Filter
93
97
9.80
Format Fine-Tuning
89
92
6.72
DINGO
100
100
6.78
we sampled upto 1000 responses per question. Table shows DINGO significantly outperforms both
the baselines.
Ablation Study on The Number of Diff'usion Blocks: We analyze the performance of DINGO on GSM-Symbolic using different numbers of diffusion blocks. We run generation with response length of 128, using 64 total diffusion steps, and each of 1, 2, and 8 blocks. As shown in Figure [ DINGO performs well across all block settings, outperforming baselines in both functional and syntactic correctness. The ablations on the number of diffusion blocks are presented in Appendix
Impact of varying output lengths and different unmasking schedules: We present ablation study evaluating different output lengths and three different unmasking strategies: a) random, b) top2 margin, and c) entropy-based unmasking strategies Nie al. [2025 in Appendix L
6 Related Works
To the best of knowledge, our work is the first provide provable guarantees constrained adherence for inference in diffusion language models. We next discuss the broader set of related works diffusion language models and constrained language model decoding.
Diffusion Language Models: Diffusion Language Models Austin al. [2021] have emerged as
promising alternative traditional autoregressive architectures Radford et al. [011)). offering advantages in parallel processing and controllability while addressing limitations in sequential generation. Recent advances semi-ause autorrrgrrrrrevivveeee diffusion models Han al. [2023], Nie et al.
[225), Ye et [2025), Arriola et al. (2025) have significantly narrowed the performance gap with autoregressive counterparts. SSD-LM Han et al. [023] introduced semi-autoregressivv approach that performs diffusion over the natural vocabulary space, enabling flexible output length and improved controllability by iteratively generating blocks of text while facilitating local bidirectional context updates. More recently, several breakthrough models have advanced the field: LLaDA (Large Language Diffusion with mAsking) achieved competitive performance with SOTA open-source autoregressive models of similar size like LLaMA3-SB through a forward data masking process and
30
35
Accuracy (%6
255
25
20
Accuracy
20
15
20
Method
Method
Incomstrained eindd
10
Ancorstrened
Greedd Constrained
Greedy Constrained slnod
DINGO
DINGO
2 Number Blocks
Number of Blocks
LLaDA-8B-I
(b) Dream-I-7B
Figure 1: Ablation Study on The Number of Diffusion Blocks For GSM-Symbolic

---

reverse process, parameterized by vanilla Transformer to predict masked tokens Nie et al. 2025| BD3-LMs (Block Discrete Denoising Diffusion Language Models]Arriola et 2025 introduced novel approach that interpolates between discrete denoising diffusion and autoregressive models while supporting flexible-length generation and improving inference efficiency with KV caching. Most recently, Dream-7HYe et al. [2025] emerged as strong open diffusion large language model that matches state-of-the-ar autoregressive (AR) language models of similar size.
Constrained Decoding with Autoregressive LLMs: Constrained decoding has shown promising results in augmenting autoregressive language models. Researchers have developed efficient tech-
niques for ensuring syntactic correctness in regular DDeutsch et al. 2019 Willard and Louf 2023
Kuchnik et al. [2023] or context- [Koo et al. 2024 Ugare al. [2024a] Dong et al. 2024 Banerjee
et 2025al languages. Other works have focused on semantically constrained decoding through
Monte Carlo sampling [Lew et al. [2023] Loula et al. 2025) or backtracking (Poesia et al. [022]
Ugare al.
2025 [ee et al. [202]] Park et al. [2024a] demonstrated that all these approaches
that perform greedy constrained approximation for inference can distort the sampling distribution.
DINGO addresses this challenge by performing optimal constrained sampling on blocks of tokens in a diffusion language model, which partially mitigates distribution distortion issues.
Concurrent to our work, Cardei et al. [025 performs constrained sampling from diffusion language models by minimizing loss function defindd using a surrogate model used for scoring constraints. However, their proposed method does not guarantee convergence to the constraint and necessitates a differentiable surrogate model. In contrast. our work focuses on providing provable guarantees for constraint satisfaction during inference without the need of an additional surrogate model.
Limitations DINGO is optimal for per-block generation, making it ideal for pure diffusion settings. However, this optimality may not hold in semi-autooeerresive setups involving multiple blocks. Currently, our approach is limited regular language constraints, while programming languages often belong to context-free or context-sensitive classes. As a result, our method cannot directly enforce these more expressive constraints, which have been addressed in prior work on autoregressive constrained generation. Nonetheless, we believe the core dynamic programming framework behind DINGO can be extended to support richer language classes future work. Moreover, important constraints like toxicity mitigation fall outside formal language classes, highlighting directions for further research.
7 Conclusion
We presented DINGO, a novel dynamic programming approach that enables diffusion L.MMs to generate outputs that strictly adhere to regular language constraints while preserving the model's underlying distribution. Our method overcomes the limitations of traditional constrained decoding algorithms that fail with parallel token prediction. Our experimental results symbolic math and ISON generation tasks demonstrate significant improvements over unconstrained inference, demonstrates that DINGO is an effective solution for structured output generation with diffusion models. Our work bridges an important gap in making diffusion LLMs reliable for applications requiring formal guarantees.
Acknowledgement
We thank the anonymous reviewers for their insightful comments. This work was supported by funding through NSF Grants No. CCF-2238079, CCF-2316233, CNS-2148583, CCF-2313028. CCF-2217144 1444 and a Research Gift from Amazon AGI Labs.
10

---

References
Marianne Arriola, Subham Sekhar Sahoo, Aaron Gokaslan, Zhihan Yang, Zhixuan Qi, Jiaqi Han, Justin Chiu, and Volodymyr Kuleshov. Block diffusion: Interpolating between autoregres- sive and diffusion language models. In The Thirteenth International Conference on Learning Representations, 2025, URL htt.t:ttp////.mm http://ppenrrreeeeeeeeeforomonne
Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors. Advances in Neural Information Processing Systems, 2021. URL
https://openrevier. wtt.:/viiwii.etetoormrnni.iaaaa. XixPCAL
Christian Azinn. Json training dataset. hutegs/s/nngiiggg....oo///attttt #son-training 2024. Accessed: 2025-10-23.
Debangshu Banerjee, Tarun Suresh, Shubham Ugare, Sasa Misailovic, and Gagandeep Singh. CRANE: Reasoning with constrained LLM generation. arXiv preprint arXiv:2502.09061, 2025a. URL htttp:://arii. org/ pdf 2500. 25002.90011
Debangshu Banerjee, Tarun Suresh, Shubham Ugare, Sasa Misailovic, and Gagandeep Singh. Crane: Reasoning with constrained Ilm generation, 2025b. URL httpp::/aaxxv..or//abbbtt 09061
Michael Cardei, Jacob K Christopher, Thomas Hartvigsen, Brian R. Bartoldson, Bhavya Kailkhura, and Ferdinando Fioretto. Constrained language generation with discrete diffusion models, 2025.
URL htttt:://aattttii org/ htt//bb//5005 09790
Leonardo De Moura and Nikolaj Bjørner Z3: an efficient smt solver. Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, OS/EAPS' 08, page 337-340, Berlin, Heidelberg, 2008. Ppringer-Verlage ISBN 3540787992.
Daniel Deutsch, Shyam Upadhyay, and Dan Roth. A general-purpost algorithm for constrained sequential inference. In Proceedings of the Conference Computational Natural Language Learning, 2019. URL https://aclaathoooogy www.oogg//i K19- 1045/
Yixin Dong, Charlie F Ruan, Yaxing Cai, Ruihang Lai, Ziyi Xu, Yilong Zhao and Tianqi Chen. XGrammar: Flexible and efficient structured generation engine for large language models. arXiv preprint arXiv:2411.15100 2024. /ttps:////// org/ http:/dff/2111 /411 15100
Chen et. al. Evaluating large language models trained on code, 2021. URL atttps://arxxy org/ abs/2107.03374
Timofey Fedoseev, Dimitar Iliev Dimitrov, Timon Gehr, and Martin Vechev. LLM training data synthesis for more effective problem solving using satisfiability modulo theories. In The 4th Workshop on Mathematical Reasoning and Al at NeurlPS'22 24, 2024. URL/htttss:/opperreee htt//foouumnid-RRHHHeeee
G. D. Forney. The viterbi algorithm. Proc. of the IEEE, 61:268 278, March 1973.
Xiaochuang Han, Sachin Kumar, and Yulia Tsvetkov. Ssd-Im: Semiiauttorerressvve simplex-based diffusion language model for text generation and modular control, 2023. URL https:
org/abs/2210.11 17432
Terry Koo, Frederick Liu. and Luheng He. Automata-based constraints for language model decoding. In Conference on Language Modeling, 2024. URL hatpe://ppeareriie.nnt/ooomootmt
BDBablmyzY
Michael Kuchnik, Virginia Smith, and George Amvrosiadis.
Validating large lan- guage models with RELM. Proceedings of Machine Learning and Systems, 5,
2023.
URL https::/procceddigggg. mlays org/ paper falllppppplllla_llllllllllppeeee fwwefflllpppppeee filees/paper/222//iiel

---

Alexander K Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash Mansinghka. Sequential Monte Carlo steering of large language models using probabilistic programs. In ICML 2023 Workshop: Sampling and Optimization in Discrete Space, 2023. htt.aattpss//ppperrvveee...eee U12K0qXxXy
João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alex Lew, Tim Vieira, and Tim O'Donnell. Syntactic and semantic control of large language models via sequential Monte Carlo. In The Thirteenth International Conference on Learning Representations, 2025. URL htttp::://peereviiiiiteeee pttp///errreeee.eeeepff......o wtt..///ppppd.dddoooo22000000 Fid=xxXm622200
Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. Gsm-symbollc:: Understanding the limitations of mathematical reasoning in large language models, 2024. URL :utttps://arrie wow.:.orgggaooo org/abs/ htg//bb//4100.... 05229
Niels Mündler, Jasper Dekoninck, and Martin Vechev. Constrained decoding of diffusion Ilms with context-free grammars, 2025. URL
2508. 10111
Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin. Ji-Rong Wen, and Chongxuan Li. Large language diffusion models, 2025. URL https://arxiv axg/abs/2502.095
NousResearch. json-mode-eval, 2024.
URL htttps//hhnggingffcec.c///asss
mousResearchh/son-mooeee
Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang. Logic-Im: Empowering
large language models with symbolic solvers for faithful logical reasoning, 2023. URL https
//arxiv. org/ abs/ 12295
Kanghee Park, Jiayu Wang, Taylor Birg-Kirkpatriic, Nadia Polikarpova, and Loris D' D'Antoni. Grammar-aligned decoding. Advances in Newral Information Processing Systems, 37:24547- 24568, 2024a. URL https://pproceddingg nwurips...i..p...ee..e.. www.sesscc.ppppppppeeeeeeeeeeeee wiles/paper///022 /024
pdf
Kanghee Park, Jiayu Wang. Taylor Kirkparika. Nadia Polikarpova, and Loris D' D'Antoni. Grammar-aligned decoding. In The Thirty-eighth Annual Conference on Neural Information
Processing Systems, 2024b.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32. 2019.
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In International Conference on Learning Representations, 2022. URL htttp: net/ [formm Dorumm2id-KmtVV777J333
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl, 2019. URL https: openai com www/better-oooeeoc.ooeooooeo. wewteeeeerrnaaaaeeeeeeeee language harelllssaaauuge_eeee www.moodlllsae _ar_____________________________
learntessaskk_eaeerssss.. .ddf Accessed: 2024-11-15.
Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. SynCode: Improving LLM code generation with grammar augmentation. arXiv preprint 2:X
2024a. URL http::
Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. Syncode: Lim generation with grammar augmentation, 2024b. URL httttpp:///arrii.oo///aa////////
Shubham Ugare, Rohan Gumaste, Tarun Suresh, Gagandeep Singh, and Sasa Misailovic. IterGen: Iterative structured LLM generation. In The Thirteenth International Conference on Learning Representations, 2025, URL 2025.
12

---

Brandon T Willard and Rémi Louf. Efficient guided generation for large language models. arXiv preprint arXiv:2307.09702 2023.
httptppp//aaxx.oorrrro. 22307 09702
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers: State-of-the-art natural language processing. In Conference on Empirical Methods in Natural Language Processing: System Demonstrations, 2020. URL https: httpp:://aallanhhooooyy ozg/ 2020 eanlp-demos, 6
Kaiyu Yang, Aidan M. Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan Prenger, and Anima Anandkumar. Leandojo: Theorem proving with retrieval- aurmeete- language models, 2023. URL htt.:tttt///aiii..rtrtreeeeee hbtp://bb/230..... 2306. 15626
Jiacheng Ye, Zhihui Xie, Lin Zheng, Jiahui Gao, Zirui Wu, Xin Jiang, Zhenguo Li, and Lingpeng Kong, Dream 7b, 2025. https:/::///kum .i io/blog/ 2025/ dream
Siyan Zhao, Devaansh Gupta. Qinqing Zheng, and Aditya Grover. dl: Scaling reasoning in diffusson large language models via reinforcement learning, 2025. URL httphhttp//xxiiii wwwp:iiiv.o...rrroeeeee org/abs 2504 12216
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Yes, the abstract and introductions claims are validated through the proposed approach and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
14

---

Justification:
Limitations are discussed in the Related Works section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Yes, refer to Section
4
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
All experiment details are in Section
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code is provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 /ttppp.cc/pbllc/guudeeee http://odebbbbiiiooooooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
16

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All experiment details are mentioned in Section
S
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification; All experiments used greedy decoding, which deterministic. The results will not change between runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-simma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, the details are provided in Section
5
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
17

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httppp///ooorrg...c//aaall/llllt
Answer: [Yes]
Justification:
The paper conforms NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses the impact of the work in the Introduction and validate through the experiments.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
18

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: citations for assets used are given. Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The details about the algorithm and limitations are described the paper Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
19

---

Justification:
No crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subject involved.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [No]
Justification: LLM is not used for important, original, or non-standard component of the research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy http://aarrrrececcooo/oeeeeeeeee for what should or should be described.
20

---

A Transformer and Remasking Step
Algorithm 2 Diffusion Step
Require: Transformer Nn, full output length n, prompt input prompt length m, block length d,
current diffusion step i, total diffusion steps T,, vocabulary V.
1: x t -
Pad the input prompt where = m + d
2: 01 ... - (x)
U2 b Decides which positions to remask
| VV output distribution at position i
3: + RemaskPositions((me (Um+1 Um+dd i,
4: for e
5:
1 0
6:
Set probability of all tokens except 1 O. 7: r t Dm,n(11 (VI... Un) Decoding that outputs response with first m tokens are input prompt
vy[
+
8: return
We describe the two key components of single diffusion step: a) Transformer step: Computes the output distribution over all tokens in the vocabulary (line 2 Algo. 2). b) Remasking step: Based on the output from the transformer step, it greedily decides which token positions mask. The remasking step can be viewed as updating the output distribution such that, at the masked positions, the mask token 1. is assigned probability while all other tokens receive probability (lines 3 Algo.21 2). Popular greedy remasking strategies include (line 3 Algo. 2 (i) Random: Masks tokens at randomly selected positions (Ne et al.) (025). (ii) Top token probability: Masks positions where the top-predicted token has the lowest probability Nie et al. [2025). (iii) Entropy-based: Computes the entropy the output distribution each position and masks the positions with the highest entropy Ye et al. 2025].
The number of token positions to remask the i-th step typically depends on the total number of diffusion steps T' and the block length d. At step 0, all d positions are masked, and the number of masked tokens decreases linearly over T steps. Thus, at the i-th step, the number of masked tokens is given by dx(T-i)
B Proofs
Proposition 4.1. [Correctness] Given any regular expression R, input prompt E V block length output distribution Dm+dd V1 Um+dd if (R. (V 1)d & ( and Um+11 Umtd be the decoded string, then ix E (x S(r)) A (x Lp(R) holds.
Proof. We assume that 3x LP(R) n (V \ 1 (P(x U ... .n.....mmmdd Um+dd 2 0) then the decoded
string satisfy the soundness property (see Definition 3.2). In other words, if there is at least one fully unmasked valid prefix with non-zero probability then DINGO retrieves valid string.
We show this by induction on the position of tokens. Before moving to the proof, we first define extended transition function 8* when 8 Q V 2 outputs a set of states instead of single state due to mask token 1. In this case, for any string w E V*, 8* (w, go) represents the state of reachable states starting from go- This can be defined 8 ((), 9o) {go) and 8* (t1 ...m+,, qo) Upe8 (f........ 90) 8(g, tm+1).
1. Let 0 Sii d, and let t ... V denote any token sequence with positive probability mass I[; Um-sst) O. Let E 8 (t1 ...-., 4, go). Then, W q] > 0. We prove this using induction on i.
(a) Base case 0: For empty strings only start state go is reachable. DINGO initializes
W|0, gol = 1 > 0 and for all * qo. W [0, g) = 0. (lines 1 1-3 in Algo.
(b) Inductive Step: At position i 1, let f f++1 E Vi+1 s.t. IT un > 0. Let
o' E 6"1 -.. qo) and q 8(g'. t++1). By the inductive hypothesis, for all such o'
21

---

o'i > O. Recall,
max Um+i+1(() s.t. q E ((
V2+1(g,0)= if q' are not connected
LEV
W + 1.9]
max W [i. x Vi+ila,d)) o'EQ
Thus, Vi+1 (441(9.55 q') 2 V (m+)+1(t+41) > 0 which implies Wli.9' x Vi+i(q,99) > 0. Therefore, W ( + g. ma W(i, x V++1l9.9') 0.
2. Since (R) (V 1 + O by assumption, there exists some y E (V 1)d. By the Definition 2.6
Øi o7 to) Qi- From the induction above, W[d, q) > 0. Omaa = arg qEQ: Wid, q]. Thus, by the definition of arg max. 0.
From line 16 in Algo.
W(d, [man] 2 W [d, q
3.
D. DINGO reconstructs a d-length sequence r = t.... ta E Vd such that Omax E 8 go). For any 1, E r, t, L, choose any token Tj (V \1) satisfying (z(g)-1, Substituting every 1 in this manner yields, by Definition x E S(r). 07 (z, qu) 9max. From above, W (d, 9mox]
In lines 20-22 in Algo.
qj where qj ( ... 1.,
By definition of 81, Tj exists.
3.1 I = Id E (V 1)).
4. Since qmax E Qi, by Definition 2.6 Ew E Σ" s.t. 6w 9max) x w E L(R), hence x E Lp(R).
F. Equivalently,
Proposition 4.2. [Optimality] Given any regular expression R, input prompt E V block length output distribution Dm+d= U1 ... ........ee Un+d. if (R) n (V 1)a # (} and Um+1... ... Um+dd be the decoded string, then for any valid string r' satisfying ix E V*, (x S(r P(r') Um+1.... U.) P(r" Umm+1...
(R)),,
Proof.
1. First, show that P(r Um+1-.. ... Vn) Wld, 9maa], equivalently II 1 Pmmt = WId, qmaa]. Let r' = 11 .......2 .dd and 0 S < d. We prove by induction on i that if DINGO's backtracking (lines 19 23 in Algo has brought us to state E Q at position i, then W g] II; Um [r,"].
(a) Base case i= 0: W|O, qol = = I[ um++ 1r
(b) Inductive Step: At position i, let q' rs' = Pr(i, q] (line 21 in Algo D. From lines [i.g] = W 11 x um+r(rs"). By the inductive hypothesis, Pmtslrs"). Thus, W q) [1;= um+ssrr")) x um++"rr")
14 15 in Algo W
Wii 1,
I1 Um+im (r3")
Let qa "'. rd' go). Since = anax (line 19 in Algo rd" I1 IT==1 Pmmtjryy (ry") P(r Um+1 vn.) UU))
Wld, gmaz] =
2. We show that for every valid string r' = =r'' ra' satisfying 3x E V*. E S(r') A (x (R))), II Un Iry' < W[d, [maz]. Let 0 < i < d and g 8* (*1''' .......,,,, .o). We show that i Un |ry'l - W(d, g) using induction on i.
(a) Base case = 0: W00, gol = 1 I1;-, Um+s(rr'l
(b) Inductive Step: At position i + 1, let o' E 8
('('rr.... (mi'...ri' go) and a E O(g', By the inductive hypothesis, II umt [ry'] W(i, Recall,
max (m+i+1(t) s.t. q E 8(d'tt TEV Vi+1(g,0) qf are not connected
W + 1, = max W Wii.g') x Vitigggg)
q'EQ
Thus, Um+t41(744a" S V4+1(g,9). Hence, 11 Um+ [Ty'l II; (ry)l x Unti41(F441)) & W[i.g') V4iig. < W + 1, g).
22

---

Let qu E 8 (r1'
.d'. ....d'. Imaz
Since a E V*,(z E S(r A (x Lp(R)), E Qi. From ma Wld, g). Thus, by the definition arg
line 16 in Algo.
W[d, qal I W ld Amaz]- From the inductive hypothesis above, I um+yllyy S
W(d, qal W [d. 9maz].
3. Hence, P(r P(r" Um+11..UU,
Un) [ Un+slrs S W(d, {maz)
I um um (
1m+t1...0.
C Time complexity analysis of parallelized DINGO DP
Algorithm DINGO DP
Require: go. block length d. probability vectors vI.... for the current block, Qi, Q. 6.
I: W q] <- 0 for all (q Q) (4 qu)
2: W qol f-
3: Pr[0, + (None, None) for for (q E ()
> Initialization of the DP maximum token probability transtion (q' position i token for the maximum probability transition (4' q) The computation along all can parallelized
4: V, + (} for all fl....,d
5: Ti () for aorall i
(I.
d) (1.... do 7: Parallelize for each (1....d}
for Meiek (1....,d)
8: for (q E Q) do
9: for t E V do
+ 5(g.t)
V.(, T' MaxTransition(0;:...4
for (I..... d)
b computation loop
13:
for (q (4' E Q) do
14:
i Wli
1,4'] x Va(g.9) then V((.g')
15:
W i g) Wi
1,9'
Update maximum probability path to > Update the parents accordingly
Prii. g (q (r. ))
Jmaz + arg ma Wld.g) g)
18: if [(d, [mar] = 0 then
> No valid prefixes
19: return None, Qmaz
20: r' ()1 Yourr f- Juax
21: for E (d, (d...., 1) do
Decoding the optimal string r'
22: Yeuer, &- Pr(i, 4eurc]
23:
p" 24: return reverse(r"), Gmaz
The parallelism step at line 6 in Algo. 1o.3caan be efficiently implemented using popular frameworks like PyTorch. With parallelism, the computational depth (i.e., the minimum number of sequential steps) reduces to O(max(1 |Q] x [V]) + 1Q] x d). For regular expressions, where the number of states [Q] a small constant, the computational depth becomes O(VI + d), which linear in both the vocabulary size [V| and the block length d.
D Semi-Auutoregressive
In the semi-autoregressive setup, given an input E V", the output E Vm+4xx is generated over blocks, where each block is computed via a call to the single block diffusion model. The output of and the final output
the i-th diffusion model call is Lomgon, (x;-1), with input and output lengths for each block defined as m, = m 1) x d and n, = m + i for
Zg. The
all 1 < i < k.
23

---

Algorithm 4 Semi-Autoregrresivve diffusion LLM Generation
Require: diffusion LLM L, prompt answer length n, block length d, diffusion steps T,, vocabulary V. number of blocks k.
1: I +t+
> Initialize I with input prompt
2: r r< [
Intialize the output string
3: for E {l.....,k } do
4:
T + Difffusionzz m - - 1) x d V,
D E V is i-th output block
5:
r-
6:
I t --xx-1
>> Compute the input prompt for the next block
7: Return r
Algorithm 5 Semo-uutoeerressivve Constrained diffusion LLM Generation
Require: diffusion LLM L. prompt p. answer length n, block length d, diffusion steps T, vocabulary
V. number of blocks k. regular expression R.
1: q0: Qi, 5 <- PreProcess(R)
Pre-compute the dfa start state, live states and > Initialize with input prompt p D Intialize the output string Intialize the current dfa state the response is
2:
3: r -+ 0}
4: Hearr <- 40
5: for i E {l,..... k} do
6:
Ti, Inent Difffusionzz m 1) d, T, Qi 0, (eurr)
7:
if Inezt & Qi then return None
8:
No valid completion
9:
r r
10:
+ t
Compute the input prompt for the next block D Update current DFA state for next block
11:
Yeurr + Quezt
12:
Return
In the semi-autoregressive setting, after each block, we ensure that the output generated so far ends in a live state from Qú; otherwise, we return the None string (line 7, Algo. (5). Additionally, we maintain a variable yeur to track the current DFA state at the end of each block. This state is then used as the starting state for the dynamic programming step in the constrained generation of the next block.
24

---

E Token Transitions Statistics
Table Token Transitions Pre- Crmpuutnttn Statisties
GSM-Symbolic Time(s)
ISON-Mode
Model Family
[
#States
Time(s)
#States
LLaDA-8B
126349 151667
32.09
40
13.22
169.31
Dream-7B
37.01
40
11.87
169.31
In Table 4 we report the precomputation time and the number of states in the DFA for both tasks. For ISON generation, different regular expressions are used for different schemas; therefore, we report the mean precomputation time and mean number states. The maximum number of states and precomputation times across all questions are 455 and 17.7 (Dream) 21.3 (LLaDA) seconds, respectively.
GSM-Symbolic
GSM-Symbolic Prompt
You expert solving grade achool with grade school math word problen with symbolic varisbles and be asked solve it.
presented
Before anevering you should reason about the problen (using the <reasoning? field the respanse described belox). Intermediate synbolic expressions generated during reasoning should be srapped in << >>.
Only output the symbolic expression wrapped in <c s> that answers the question. The expression must numbors sell defined in the question. You only alloved to the following 1/, %. +, and *,.
operations: +,
You will alvays reapond in the format described below: final
think step by step. cressoning' exprestion>>
<ssyubolic
There (t) trees in the (g). (g) workers will plant in the (g) today After they are done, there will be (tf) trees. Hox many trees did the g} vorkera
today?
Let's think step by step. Initially, there are (tf) trees. The number of trees planted is ecti t>>, The final ansver
(t) trees.
planting,
t>>.
there are (c) cars in the parking lat and (nc) more cars arrive, hav nany parking let?
Let's think step by step. Initially, arrive, so the total becomes <<c ne>>. The final ansver is <<c ne>>.
(c) care. (nc) more care
{p1) had (ch1) (ol) and (p2) had (ch2) (o1). If they {a} (o1), how many piacas do they have laft in total?
Let's think step by step. Initially, (p1) had (ch1) (o1), and (p2) had (ch2) ch2>>. After eating (ol), remaining total is <echt + ch2 a>>. The final ansver is <<cht ch2
(o1), making
of
{pl) had (11) foth. fp1) gave (g) fol) to (p2). Hoo nany foi) does (p1) have left?
step by step. {p1) started (11) (ol). giving {g} (o1) to {p2), {pt) has <a1 (o1) left. The final ansver is <al g>>
(question)
Listing 1: Prompt template for the GSM-Symbolic task Mirzadeh et al. 2024
25

---

F.2 GSM-Symbolic Regex
(
))+
Listing 2: GSM-Symbolic Regex
F33
GSM-Symholic Case Studies
Case Study 1:
Question: [$1] gets (b) emails day. [c]% of those emails don't require any response. He responds the rest them. How many emails does respond to in a (a] day work week?
Unconstrained:
Let's think step by step. "Reasoning
Text that require response is <eb <<c/100>>> b>> * >>>> <<b - <<c/100>>>>>> b>> a>>,The final
answer is <<b <<c/100 >> b>> a>>
Variables shown in blue
Syntax
Greedy Constrained: Let's think step by step. "Reasoning Text ..." of emails requiring require response <<b (c/100* * b ** al ** a>>. The final answer (c/100* ** b * a>>.
DINGO: Let's think step by step. "Reasoning Text
"The number of emails responded to is (b
<<c/100>> b) The final is <<(b (c 100
a>>.
Functionally incorrect
Syntactically and Functionally Correct
An example from the GSM-symbolic dataset (variables in blue), where unconstrained generation produces syntactically incorrect output, and greedy constrained generation yields syntactically valid but incorrect answer. In contrast, DINGO generates the correct answer.
Figure 2:
Case Study 2:
26

---

Question: new [s1] infects (b) people. Every day, each infected person infects (c) others. How many people are infected after [a] days?
Unconstrained: Let's think step by step. "Reasoning Text so on, effectively increasing the number of infected people by (e"a). The final answer is <<b
>>>>
Variables are shown in blue
Syntax error
Greedy Constrained: Let's think step step. "Reasoning Text c) "a 1/c b- (1 c) "a>>= <<b (1 + c) -a/o-b (11 c) 'a>>
DINGO:
Let's think step by step. "Reasoning Text
answer is
so on, resulting + {a] a day. The
answer is <<b (1 +c) a>>
Functionally incorrect
Syntactically Functionally Correct
Figure 3: An example from the GSM-symbolic dataset (variables in blue), where unconstrained generation produces syntactically incorrect output, and greedy constrained generation yields syntactically valid but incorrect answer. In contrast, DINGO generates the correct answer.
G JSON-Mode
G.1 JSON-Mode Example Prompt
You are helpful assistant that ansvers in JSOK. Here's 's the jeon schens you must adhere to:
<achema>
f'ritle": "PromotionalCappaggn:: "type': 'objact', 'propertiea"; P'aampaigaDD
": ('title': 'Capaaign ID', 'type': "string'), 'productID ('title': Product ID', "type': "string"), *startBate ('title:: 'Start Date', type"; 'string', 'format"; 'date?" 2), 'endDate'; ('title'; 'End Date', type'; 'string', 'fornat'; 'date'), "discountDetaile"" ('title'; Discount Details', 'type": 'string')), 'required'; ('campaignID', praductID', 'startbate', 'andDate
</schena>
I'm organizing promotional camрaign for our new eco eco-friendly laundry detergent, which part will start on June 1, 2023, and end on June 30, 2023. Ve 're planning to offer
household products line. canpaiga
on purchases during this pariod. CAMP123456, the product ID is PROD7891011, and the diacount details are 15% off on all purchases.
campaign
Only output JSDN objact, other
task NousResearch [2024]. The prompt includes a system message that specifies a schema and user message that explicitly instructs the model output JSON object following that schema with certain parameters.
Listing Example ISON Prompt from the
G.2 JSON-Mode Example Regex
WCC ] campaaggaa
J?. popoouttcc ] "o
1101 1?:[ 1?": 2:ttaaaaaa.aa"".....".":13111113
-"E [
(ooo1l-9]((-22000-]]]]--------= ]?, (10 (2:001--111[0-21) (1 dsscountDetaila""
?[ ]?NA)
Listing Regex for the ISON Schema in Appendix
G.2
27

---

G.3
JSON-Mode Case Studies
Question: liere's the |son schema you must adhere
Unconstrained: ('orderid': 'ORD10234' 'items::
to:sschema>.. </schema>, <Question. Please respand with valid JSON object for this order.> Only outout the JSON object, no other text comments.
I'name:: "Wireless Mouse', 'price': 15,99), ('name': 'Bluetooth Keyboard,, 'price': 29.99), ("name': 'Webcam HD', 'price': 45.50))
Syntax error (missing '
Greedy Constrained: { "orderld" "4', 'items': I'namee: 'Wirel ess Mouse', "price': 15.99), l'name: 'Bluetooth Keyboard', 'price': 29.99), name":
DINGO: l'orderld': 'ORD10234', 'items': [('name': 'Wireless Mouse', 'price': 15.99), f"name': 'Bluetooth Keyboard', 'price": 29. 99), f'name': 'Webcam HD', 'price': 45.50]]]
'Webcam HD', 'price":
1
Syntax (incomplete output)
Syntactically Correct
An example from JSON generation, where unconstrained generation produces syntac- tically incorrect output, and greedy constrained generation yields a valid but incomplete prefix. In contrast, DINGO generates syntactically correct answer.
Figure 4:
Question: Here's the json schema you must adhere to:sschema>... - s/schema>, Question ... service was very prompt and professional, but wish there was more variety in the product options. 'Only output the JSON object, other text comments.
Unconstrained: wustommerrl" "CUST29382", "feedbackScore": 4, "comments": service was very prompt and professional, but wish there was more variety in the product options.")
Syntax error (missing ({)
Greedy Constrained: "customerll""
DINGO: l'customerlD': 'CUST29382',
"1UST29382", "feedbackScore":
"JeecbakScorr': 4, 'comments', service was very prompt and professional, but wish there was more variety In the product options.')
mnnntnnn"commenn "nnts) \n\m\n". Think like the are D to a five year Bible. little about the and the human world. the author review
Syntax error (incomplete nutput)
Syntactically Correct
Figure 5: An example from JSON generation, where unconstrained generation produces a syntac- tically incorrect output, and greedy constrained generation yields valid but incomplete prefix. In contrast, DINGO generates a syntactically correct answer.
28

---

H Ablation Study on Number of Blocks for Diffusion LLM Generation (GSM-Symbolic)
We run generation with response length of 128, using 64 total diffusion steps, and each of 1, 2, and 8 blocks. Table presents the result.
Table Ablation Study on The Number of Diftusion Blocks for DSM--ymbolic
Model
#Blocks
Method
Acc. (%)
Parse (%)
Time
Unconstrained
20
54
23.66
Greedy Constrained
23.7
Best of Greedy Unconstrained
23.66
DINGO
29
100
23.73
Unconstrained
22
54
23.63
Greedy Constrained
30
96
23,81
LLaDA-8B-I
Best of Greedy Unconstrained
23.65
DINGO
32
100
23,93
Unconstrained
19
35
23.78
Greedy Constrained
27
98
23,97
Best of Greedy Unconstrained
27
23.8
DINGO
32
100
23.92
Unconstrained
23.56
Greedy Constrained
32
90
23.64
Best of Greedy Unconstrained
32
90
23.65
DINGO
34
100
23,67
Unconstrained
30
23.62
Greedy Constrained
33
23.71
Dream-I-7B 2
Best of Greedy Unconstrained
33
87
23.62
DINGO
34
100
23.65
Unconstrained
32
61
23.89
Greedy Constrained
24.01
Best of Greedy Unconstrained
34
23.89
DINGO
36
100
23.91
29

---

I Ablation Study on Number of Blocks for Diffusion LLM Generation (JSON-Mode)
We run generation with response length of 128, using 64 total diffusion steps, and each of 1, 2, and presents the result.
8 blocks. Table 6
Table 6: Ablation Study on The Number of Diffusion Blocks for JSON-Mode.
Model
#Blocks
Method
Acc. (%)
Parse (%)
Time
Unconstrained
87
91
6.7
Greedy Constrained
6.81
Best of Greedy Unconstrained
6.73
DINGO
100
100
6.78
Unconstrained
84
92
6.72
Greedy Constrained
92
6.83
LLaDA-8B-I
Best of Greedy Unconstrained
6.73
DINGO
100
100
6,86
Unconstrained
84
89
6.73
Greedy Constrained
98
98
6.87
Best of Greedy Unconstrained
100
100
6.75
DINGO
100
100
6.85
Unconstrained
6.4
Greedy Constrained
30
30
6,51
Best of Greedy Unconstrained
91
93
6,43
DINGO
100
100
6.55
Unconstrained
79
82
6.47
Greedy Constrained
37
Dream-I-7B 2
Best of Greedy + Unconstrained
86
88
6.5
DINGO
100
100
6.63
Unconstrained
70
74
6.44
Greedy Constrained
Best of Greedy Unconstrained
86
89
6,46
DINGO
100
100
6.67
30

---

J Ablation Study on Number of Steps for Diffusion LLM Generation (GSM-Symbolic)
We run generation with response length of 128, 1 block, and each of 16, 32, 64, and 128 total diffusion steps. Table presents the result.
Table 7: Ablation Study on The Number of Diffusion Steps for GSM- Myy-boli with Dream-I-7B
#Steps
Method
Acc. (%)
Parse (%)
Time (s)
Unconstrained
20
5.99
Greedy Constrained
13
78
6.18
16
Best Greedy + Unconstrained
13
5.99
DINGO
18
100
6.09
Unconstrained
18
48
11.96
Greedy Constrained
25
87
12.06
32
Best of Greedy Unconstrained
25
87
11.96
DINGO
28
100
12.03
Unconstrained
28
69
23.56
Greedy Constrained
32
23.64
64
Best of Greedy + Unconstrained
32
90
23.65
DINGO
34
100
23.67
Unconstrained
31
74
47.83
Greedy Constrained
30
89
47.88
128
Best of Greedy Unconstrained
31
90
47.83
DINGO
33
47.86
31

---

K
Ablation Study on Number of Steps for Diffusion LLM Generation (JSON-Mode)
We run generation with response length of 128, 1 block, and each of 16, 32, 64, and 128 total diffusion steps. Table presents the result.
Table 8: Ablation Study on The Number of Diffusion Steps for JSON-Mode with Dream-I-7B
#Steps
Method
Acc. (%)
Parse (%)
Time (s)
Unconstrained
54
59
1.51
Greedy Constrained
32
1.62
16
Best Greedy + Unconstrained
68
71
1.52
DINGO
100
100
1.6
Unconstrained
67
71
3.23
Greedy Constrained
35
35
3.35
32
Best of Greedy Unconstrained
78
82
3.24
DINGO
100
100
3.31
Unconstrained
85
87
6.4
Greedy Constrained
30
6.51
64
Best of Greedy + Unconstrained
91
93
6.43
DINGO
100
100
6.55
Unconstrained
85
87
13.42
Greedy Constrained
46
46
13.53
128
Best of Greedy Unconstrained
95
97
13.43
DINGO
13.51
32

---

L Impact of varying output lengths and different unmasking schedules
Table Ablation Study for Different Output Lengths for JSON-Mode. All experiments use single
block, 64 diffusion steps, and generation length of 128.
Model
Output Length
Method
Acc. (%)
Parse (%)
Time (s)
128
Unconstrained
87
91
6.70
128
Greedy Constrained
78
79
6.81
128
Best of Greedy + Unconstrained
99
99
6.73
128
DINGO Unconstrained
100
100
6.78
256
84
87
20.25
256
Greedy Constrained
74
76
20.62
LLaDA-8B-I
256
Best of Greedy + Unconstrained
95
96
20.29
256
DINGO Unconstrained
100
100
20.39
512
84
84
45.77
512
Greedy Constrained
79
80
46.24
512
Best of Greedy + Unconstrained
96
96
45.83
512
DINGO
100
100
46.05
128
Unconstrained
85
87
6.40
128
Greedy Constrained
30
30
6.51
128
Best of Greedy + Unconstrained
91
93
6.43
128
DINGO Unconstrained
100
100
6.55
256
88
89
17.73
256
Greedy Constrained
26
26
18.02
Dream-I-7B
256
Best of Greedy + Unconstrained
93
94
17.75
256
DINGO Unconstrained
100
17.86
512
90
90
36.88
512
Greedy Constrained
25
25
37.28
512
Best of Greedy + Unconstrained
95
95
36.90
512
DINGO
100
100
36.09
33

---

Table 10: Ablation Study for Different Unmasking Schedules for JSON-Mode.
Model
Unmasking Type
Method
Acc. (%)
Parse (%)
Time (s)
Low-confidence
Unconstrained
87
91
6.70
Low-confidence
Greedy Constrained
78
79
6.81
Low-confidence
Best of Greedy + Unconstrained
99
99
6.73
Low-confidence
DINGO
100
100
6.78
Random
Unconstrained
80
89
6.52
Random
Greedy Constrained
93
95
6.74
Random
Best of Greedy + Unconstrained
98
6.53
Random
DINGO Unconstrained
100
100
6.76
LLaDA-8B-I
Top2 Margin
7.03
Top2 Margin
Greedy Constrained
98
98
7.17
Top2 Margin
Best of Greedy + Unconstrained
100
7.06
Top2 Margin
DINGO Unconstrained
100
100
7.11
Entropy
6.89
Entropy
Greedy Constrained
71
72
7.03
Entropy
Best of Greedy + Unconstrained
97
98
6.91
Entropy
DINGO
100
100
7.01
Low-confidence
Unconstrained
78
82
6.32
Low-confidence
Greedy Constrained
41
41
6.46
Low-confidence
Best of Greedy + Unconstrained
90
92
6.33
Low-confidence
DINGO Unconstrained
100
100
6.42
Random
55
68
6.17
Random
Greedy Constrained
30
30
6.28
Random
Best of Greedy + Unconstrained
6.18
Random
DINGO Unconstrained Greedy Constrained
100
100
6.30
Dream-I-7B
Top2 Margin
6.71
Top2 Margin
40
40
6.85
Top2 Margin
Best of Greedy + Unconstrained
89
91
6.73
Top2 Margin
DINGO
100
100
6.83
Entropy
Unconstrained
85
87
6.40
Entropy
Greedy Constrained
30
30
6.51
Entropy
Best of Greedy + Unconstrained
91
93
6.43
Entropy
DINGO
100
100
6.55
34


Reviews:
[{"review_id": "IqCf9ylDUX", "reviewer": "Reviewer_t6qZ", "summary": "This paper proposes DINGO, a distribution-preserving, provably correct constrained decoding algorithm for diffusion LLMs. It compiles user-specified regular expressions into DFAs and applies a Viterbi-style dynamic programming step at each unmasking to enforce constraints without altering the model’s distribution. Experiments demonstrate substantial gains in output validity with only modest extra computation.", "questions": "What is the computational complexity when multiple constraints must be enforced simultaneously, and how does it scale with the number or size of DFAs?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. Seamlessly integrates DFA constraints with dynamic programming into parallel diffusion decoding, providing formal guarantees of both validity and distribution fidelity.\n2. Demonstrates substantial validity improvements on realistic tasks, with only a small increase in runtime relative to native sampling.\n\nWeaknesses\n1. The paper does not include a thorough empirical evaluation against other constrained decoding approaches for diffusion models.\n2. The impact of varying output lengths and different unmasking schedules on constraint enforcement is not fully explored.", "was_revised": true, "final_justification": "I have read the author's rebuttal and the comments from other reviewers, and after a comprehensive evaluation, I have decided to maintain my original score.", "rebuttal": "Thanks for your constructive feedback.\n\n> Q1. Empirical evaluation against other constrained decoding approaches for diffusion models.\n\n**R1:** DINGO is the first constrained decoding algorithm for diffusion LLMs. However, we have added additional experiments demonstrating the effectiveness of DINGO compared to other potential approaches, including fine-tuning and rejection sampling (referred to as **Sample-Filter**). In all cases, DINGO significantly outperformed the baselines (Table 1). We have used the same hardware setup as described in the paper.\n\nFor the **Sample-Filter** approach, we iteratively sample a response and use a DFA to check if the sampled response is a syntactically valid prefix. If not, we reject the response and sample the next one. We sample up to 1000 responses. \n\nFor the **Fine-Tuning** approach, we perform supervised fine-tuning (SFT) on a dataset of 20k natural language + JSON schema to JSON instance pairs [1]. We used the d1 codebase [2] for the SFT implementation.\n\nFor all experiments, we used a single block, a generation length of 128, and 64 diffusion steps.\n\nTable 1: Comparison of Different Methods for JSON-Mode.\n| Model      | Method         | Acc. (%) | Parse (%) | Time (s) |\n|------------|----------------|----------|-----------|----------|\n| LLaDA-8B-B | Unconstrained  | 57       | 59        | 6.37     |\n| | Greedy Constrained  | 80       | 80        | 6.47     |\n| | Sample-Filter  |    68    |   69      |  13.00    |\n| | Format Fine-Tuning  |    60    |     60    |  6.41   |\n| | DINGO  | 100       | 100        | 6.43     |\n| LLaDA-8B-I | Unconstrained  | 87       | 91        | 6.70     |\n| | Greedy Constrained  | 78       | 79        | 6.81     |\n| | Sample-Filter  |     93   |   97      |  9.8   |\n| | Format Fine-Tuning  |    89    |    92     |  6.72    |\n| | DINGO  | 100       | 100        | 6.78     |\n\n[1] huggingface.co/datasets/ChristianAzinn/json-training\n\n[2] github.com/dllm-reasoning/d1/tree/main\n\n> **Q2. Impact of varying output lengths and different unmasking schedules.**\n\n**R2:** We present an ablation study evaluating different output lengths and unmasking strategies. Using the same experimental setup as in the paper, DINGO consistently outperforms the baselines across all configurations (Tables 2 and 3). We have used the same hardware setup as described in the paper. All experiments in Table 2 were conducted with a single block, and the number of diffusion steps was always set to half the generation length.\n\nTable 2: Ablation Study For Different Output Lengths for JSON-Mode.\n\n| Model      | Output Length | Method                              | Acc. (%) | Parse (%) | Time (s) |\n|------------|---------|-------------------------------------|----------|-----------|----------|\n| LLaDA-8B-I  | 128      | Unconstrained                       | 87       | 91        | 6.70     |\n|            |         | Greedy Constrained                  | 78       | 79        | 6.81     |\n|            |         | Best of Greedy + Unconstrained      | 99       | 99        | 6.73     |\n|            |         | DINGO                               | 100      | 100       | 6.78     |\n|            | 256       | Unconstrained                       | 84       | 87        | 20.25     |\n|            |         | Greedy Constrained                  | 74       | 76        | 20.62     |\n|            |         | Best of Greedy + Unconstrained  | 95  | 96  | 20.29     |\n|            |         | DINGO                               | 100      | 100       | 20.39     |\n|            | 512      | Unconstrained                       | 84       | 84        | 45.77     |\n|            |         | Greedy Constrained                  | 79       | 80        | 46.24     |\n|            |         | Best of Greedy + Unconstrained      | 96       | 96        | 45.83    |\n|            |         | DINGO                               | 100      | 100       | 46.05     |\n|   Dream-I-7B         | 128      | Unconstrained                       | 85       | 87        | 6.4     |\n|            |         | Greedy Constrained                  | 30       | 30        | 6.51     |\n|            |         | Best of Greedy + Unconstrained      | 91       | 93        | 6.43     |\n|            |         | DINGO                               | 100      | 100       | 6.55     |\n|            | 256       | Unconstrained                       | 88       | 89        | 17.73     |\n|            |         | Greedy Constrained                  | 26       | 26        | 18.02     |\n|            |         | Best of Greedy + Unconstrained      | 93       | 94        | 17.75    |\n|            |         | DINGO                               | 100      | 100       | 17.86     |\n|  | 512       | Unconstrained                       | 90       | 90        | 36.88     |\n|            |         | Greedy Constrained                  | 25       | 25        | 37.28     |\n|            |         | Best of Greedy + Unconstrained      | 95       | 95        | 36.9     |\n|            |         | DINGO                               | 100      | 100       | 36.09    |\n\nAll experiments in Table 2 use a single block, 64 diffusion steps and generation length of 128.\n\nTable 3: Ablation Study For Different Unmasking Schedules for JSON-Mode.\n\n| Model      | Unmasking Type | Method                              | Acc. (%) | Parse (%) | Time (s) |\n|------------|---------|-------------------------------------|----------|-----------|----------|\n| LLaDA-8B-I | Low-confidence      | Unconstrained                       | 87       | 91        | 6.70     |\n|            |         | Greedy Constrained                  | 78       | 79        | 6.81     |\n|            |         | Best of Greedy + Unconstrained      | 99       | 99        | 6.73     |\n|            |         | DINGO                               | 100      | 100       | 6.78     |\n|            | Random       | Unconstrained                       | 80       | 89        | 6.52     |\n|            |         | Greedy Constrained                  | 93       | 95        | 6.74     |\n|            |         | Best of Greedy + Unconstrained      | 98       | 98        | 6.53     |\n|            |         | DINGO                               | 100      | 100       | 6.76     |\n|            | Top2 Margin       | Unconstrained                       | 80       | 81        | 7.03     |\n|            |         | Greedy Constrained                  | 98       | 98        | 7.17     |\n|            |         | Best of Greedy + Unconstrained  | 100 | 100   | 7.06     |\n|            |         | DINGO                               | 100      | 100       | 7.11     |\n|            | Entropy       | Unconstrained                       | 86       | 89        | 6.89     |\n|            |         | Greedy Constrained                  | 71       | 72        | 7.03     |\n|            |         | Best of Greedy + Unconstrained      | 97       | 98        | 6.91     |\n|            |         | DINGO                               | 100      | 100       | 7.01     |\n|   Dream-I-7B         | Low-confidence       | Unconstrained                       | 78       | 82        | 6.32     |\n|            |         | Greedy Constrained                  | 41       | 41        | 6.46     |\n|            |         | Best of Greedy + Unconstrained      | 90       | 92        | 6.33     |\n|            |         | DINGO                               | 100      | 100       | 6.42     |\n|            | Random       | Unconstrained                       | 55       | 68        | 6.17     |\n|            |         | Greedy Constrained                  | 30       | 30        | 6.28     |\n|            |         | Best of Greedy + Unconstrained      | 68       | 77        | 6.18     |\n|            |         | DINGO                               | 100      | 100       | 6.30     |\n|            | Top2 Margin       | Unconstrained                       | 76       | 80        | 6.71     |\n|            |         | Greedy Constrained                  | 40       | 40        | 6.85     |\n|            |         | Best of Greedy + Unconstrained      | 89       | 91        | 6.73     |\n|            |         | DINGO                               | 100      | 100       | 6.83     |\n|  | Entropy       | Unconstrained                       | 85       | 87        | 6.40     |\n|            |         | Greedy Constrained                  | 30       | 30        | 6.51     |\n|            |         | Best of Greedy + Unconstrained      | 91       | 93        | 6.43     |\n|            |         | DINGO                               | 100      | 100       | 6.55     |\n\n> Q3. What is the computational complexity when multiple constraints must be enforced simultaneously, and how does it scale with the number or size of DFAs?\n\n**R3:** Currently, DINGO supports a single regular expression. Theoretically, it can support multiple regular expressions enforced simultaneously, since regular languages are closed under intersection \\[1], and multiple regular constraints can be represented by a single DFA. However, with a naive implementation, the number of states $Q_A$ in the resulting DFA $A$, obtained by intersecting DFAs $A_1$ and $A_2$ with state sets $Q_{A_1}$ and $Q_{A_2}$ , can be as large as $|Q_A| = |Q_{A_1}| \\times |Q_{A_2}|$ in the worst case \\[1]. This is indeed a tight bound, and state explosion cannot be avoided in the worst case \\[1]. Note that in practice, the DFA $A$ typically is not minimal, and a much smaller equivalent DFA can often be obtained using DFA minimization techniques [2]. We already use the framework from [2] to minimize the input DFA in the preprocessing step.\nWe believe that efficiently supporting multiple regular constraints while maintaining both optimality and correctness is an interesting direction for future work.\n\n[1]\"On the State Complexity of Intersection of Regular Languages\", ACM SIGACT News, 1991. \\\n[2] docs.rs/regex-automata/latest/regex_automata/"}, {"review_id": "ezHGAVKZw5", "reviewer": "Reviewer_TRQv", "summary": "This paper tries to address a critical limitation of diffusion-based Large Language Models (LLMs): their inability to adhere to formal syntactic constraints during their parallel token generation process. The authors propose DINGO, a constrained decoding algorithm specifically designed for diffusion LLMs. DINGO utilizes a dynamic programming approach to find the single most probable output string that strictly conforms to a user-specified regular expression. The method is provably correct (always producing a valid string) and optimal (finding the string with the highest probability under the model's distribution). The authors demonstrate DINGO's effectiveness on challenging structured generation tasks like symbolic math and JSON generation, where it achieves significant accuracy improvements over unconstrained decoding with minimal computational overhead.", "questions": "I know that there are a few works trying to do constrained decoding in an asymptotically unbiased way. Can you take a look and see if similar things can be applied here? [Efficient and Asymptotically Unbiased Constrained Decoding for Large Language Models]", "limitations": "Yes, the authors have discussed limitations and I agree with the authors.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- **Novel and Important Problem Formulation:** The paper tackles a novel and important problem. As diffusion LLMs become more prominent due to their efficiency, the lack of methods to control their output structure is a major barrier to their adoption in high-stakes applications. DINGO is the first work to formally address constrained decoding in this non-autoregressive setting.\n- **Provable Guarantees:** A significant strength of this work is its theoretical rigor. Unlike heuristic-based approaches, DINGO comes with formal proofs for both correctness and optimality . It guarantees that the output will always be valid and will be the single most likely valid sequence according to the model's predictions, which is a very strong claim.\n- **High Empirical Effectiveness:** The experimental results are compelling. The substantial performance gains—up to 68 percentage points on challenging JSON generation tasks—clearly demonstrate the practical necessity and effectiveness of the proposed method. Achieving 100% syntactic and schema validity where unconstrained models fail highlights the real-world value of DINGO .\n- **Efficient Implementation:** The dynamic programming approach is computationally efficient, with a complexity polynomial in the block length and the number of DFA states . The experiments confirm that this adds only marginal overhead compared to unconstrained inference, making it a practical solution \n\n### Weaknesses\n\n- First, the algorithm's optimality guarantee leads to a **bias in the output distribution**. DINGO deterministically returns the single most probable valid sequence . While this is ideal for tasks where one best answer is desired, it is a significant modification for a generative model. A truly unbiased constrained generation process would sample from the model's original distribution conditioned on the valid set (i.e., sampling from the renormalized distribution over all valid strings). DINGO instead collapses this rich distribution to a single point (its mode). This limits its use in applications requiring diversity or stochasticity, and it would be beneficial to discuss the potential of extending the framework to support true unbiased sampling. \n- Second, the algorithm's complexity, while polynomial, **scales with the number of states in the constraint's DFA**. This means that while DINGO is efficient for constraints describable by small DFAs, its practicality may diminish for very complex regular expressions that compile to a large number of states. This limitation is even more pronounced for more expressive language classes like Context-Free Grammars (CFGs), which the paper acknowledges. Since a CFG parser can have a potentially infinite state space (when considering the stack), the current DP approach is not directly applicable, limiting its utility for tasks like generating code in many programming languages.\n- **Last is about insufficiency of baselines**. While I understand that as a novel algorithm, there might not be strong existing algorithms to perform against, I do think there is a few necessary evaluations. For instance, sample-then-filter and format fine-tuning is very standard and should be considered. Training-based methods can serve as a ceiling baselines, while comparing with training-free methods are necessary. I think the authors should add a few straightforward approaches in order to demonstrate the cost with DP.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns, and, conditioned on the fact that this response can be incorporated into the revised paper, I think it is a good work for the conference.", "rebuttal": "Thanks for your constructive feedback.\n\n>Q1. Diverse topk Sampling with DINGO.\n\n**R1:** Although the current dynamic programming (DP) approach is designed to sample the syntactically valid string with the highest probability, it is possible to extend it to draw the top-k syntactically valid strings according to the predicted output distributions. At a high level, in the modified algorithm, for each position and DFA state, we maintain the top-k valid paths from the start state, instead of only the highest-probability path as in the current implementation. For subsequent positions, the top-k paths are iteratively constructed using the top-k paths of all states at the current position and the predicted token distribution at the next position. The cost of top-k sampling grows linearly with respect to k (i.e., k times the complexity of top-1 sampling). We will include the formal proof of correctness and the time complexity of the top-k sampling algorithm in the revised version of the paper.\n\nWe have implemented top-k using the same hardware setup described in the paper. Table 1 summarizes the results on the GSM-Symbolic dataset. DINGO outperforms the unconstrained approach in both Pass\\@k and parse rate (percentage of samples that are syntactically valid out of all drawn samples). Note that the parse rate decreases as $k$ increases, since the unconstrained approach tends to sample more syntactically invalid responses with larger $k$, whereas DINGO maintains its accuracy.\n\nTable 1: Ablation Study For Top-K Sampling with DINGO and Unconstrained on GSM-Symbolic. Parse Rate represents % of all samples that are syntactically correct, respectively, for a given problem averaged over all problems. \n\n| Model      | k | Method                              | Pass@k (%) | Parse Rate (%) | Time (s) |\n|------------|---------|-------------------------------------|----------|-----------|----------|\n|   LLaDA-8B-B         | 10      | Unconstrained                       |  25      |  43.7       |   10.6   |\n|            |         | DINGO                               |  31    |   100     |  11.32    |\n|          | 50      | Unconstrained                       |      25  |   34.6    |   10.69  |\n|            |         | DINGO                               |  31    |    100    |  11.44    |\n| LLaDA-8B-I | 10      | Unconstrained                       |   19   |    38.2     |   23.14   |\n|           |         | DINGO                               |  32   |   100     |   23.68   |\n|  | 50      | Unconstrained                       |            19      |  28.38     |  23.18    |\n|            |         | DINGO                               |    32   |  100      |    23.83  |\n\n\n> Q2. Scalability with large states in the DFA.\n\n**R2:** We already report the number of states in the DFAs used in our experiments, with the largest DFA containing 455 states.\nTo further evaluate the scalability of DINGO, we randomly generated DFAs with larger state counts, where transitions between states were assigned randomly. As shown in Table 2, DINGO incurs only a marginal additional cost when the generation length scales proportionally with the size of the DFA.\nThese experiments were conducted using the same hardware setup as described in the paper. We used a single block, **generation length equal to the number of DFA states**, and the number of diffusion steps set to one-fourth of the generation length. Each experiment was run five times, and we report the 95% confidence interval across these runs. \n\nTable 2: Ablation Study of DINGO overhead for varying number of DFA states\n\n| Model      | # DFA states | Method   | Time (s) |\n|------------|---------|-------------------------------------|----------|\n|LLaDA-8B-I| 10|Unconstrained | 0.08 $\\pm$ 0.01 |\n|| | Greedy Constrained| 0.08 $\\pm$  0.01 |\n|| | Diffusion Constrained | 0.08 $\\pm$  0.01 |\n|| 100| Unconstrained |0.95 $\\pm$  0.02 |\n|| | Greedy Constrained| 0.98 $\\pm$  0.04|\n|| | Diffusion Constrained | 1.02 $\\pm$  0.04 |\n|| 1000|Unconstrained | 57.96 $\\pm$  0.32 |\n|| | Greedy Constrained| 58.68 $\\pm$  0.33 | \n|| | Diffusion Constrained |59.33 $\\pm$  0.47 |\n|| 2000| Unconstrained| 242.96 $\\pm$  0.68 |\n|| | Greedy Constrained| 244.78 $\\pm$  0.91 |\n|| | Diffusion Constrained | 245.42 $\\pm$  0.75|\n|DREAM-7B-I| 10|Unconstrained | 0.06 $\\pm$  0.01 |\n|| | Greedy Constrained| 0.06 $\\pm$  0.01 |\n|| | Diffusion Constrained | 0.06 $\\pm$  0.01 |\n|| 100| Unconstrained |0.91 $\\pm$  0.02 |\n|| | Greedy Constrained| 1.02 $\\pm$  0.03|\n|| | Diffusion Constrained | 0.98 $\\pm$  0.02 |\n|| 1000|Unconstrained | 62.36 $\\pm$  0.51 |\n|| | Greedy Constrained| 62.53 $\\pm$  0.38| \n|| | Diffusion Constrained |62.97 $\\pm$  0.27 |\n|| 2000| Unconstrained| 264.05 $\\pm$  0.84 |\n|| | Greedy Constrained| 266.42 $\\pm$  0.93 |\n|| | Diffusion Constrained | 266.25 $\\pm$  0.99 |\n\n\n> Q3. Comparison with other potential baselines\n\n**R3:** We have added additional experiments demonstrating the effectiveness of DINGO compared to other potential approaches, including fine-tuning and rejection sampling (referred to as **Sample-Filter**). In all cases, DINGO significantly outperformed the baselines (Table 3). We have used the same hardware setup as described in the paper.\n\n\nFor the **Sample-Filter** approach, we iteratively sample a response and use a DFA to check if the sampled response is a syntactically valid prefix. If not, we reject the respons and sample the next one. We sample up to 1000 responses. \n\nFor the **Fine-Tuning** approach, we perform supervised fine-tuning (SFT) on a dataset of 20k natural language + JSON schema to JSON instance pairs [1]. We used the d1 codebase [2] for the SFT implementation.\n\nFor all experiments, we used a single block, a generation length of 128, and 64 diffusion steps.\n\n\nTable 3: Comparison of Different Methods for JSON-Mode.\n\n| Model      | Method         | Acc. (%) | Parse (%) | Time (s) |\n|------------|----------------|----------|-----------|----------|\n| LLaDA-8B-B | Unconstrained  | 57       | 59        | 6.37     |\n| | Greedy Constrained  | 80       | 80        | 6.47     |\n| | Sample-Filter  |    68    |   69      |  13.00    |\n| | Format Fine-Tuning  |    60    |     60    |  6.41   |\n| | DINGO  | 100       | 100        | 6.43     |\n| LLaDA-8B-I | Unconstrained  | 87       | 91        | 6.70     |\n| | Greedy Constrained  | 78       | 79        | 6.81     |\n| | Sample-Filter  |     93   |   97      |  9.8   |\n| | Format Fine-Tuning  |    89    |    92     |  6.72    |\n| | DINGO  | 100       | 100        | 6.78     |\n\n[1] huggingface.co/datasets/ChristianAzinn/json-training\n\n[2] github.com/dllm-reasoning/d1/tree/main\n\n\n> Q4. I know that there are a few works trying to do constrained decoding in an asymptotically unbiased way. Can you take a look and see if similar things can be applied here? [Reference: Efficient and Asymptotically Unbiased Constrained Decoding for Large Language Models]\n\n**R4:** Thank you for the reference. However, the proposed approach provides only asymptotic guarantees, whereas DINGO is guaranteed to always draw the highest (or top-k) probability string(s) that forms a valid prefix of a parsable string in the language. That said, DINGO currently supports only regular expressions. For more expressive syntactic constraints such as context-free grammars (CFGs), the referenced method could serve as a promising direction for future work."}, {"review_id": "HXdWybuFAR", "reviewer": "Reviewer_kh4T", "summary": "DINGO offers an algorithm for regex-constrained inference with diffusion LLMs through dynamic programming.  It is formally correct and optimal.  The empirical results demonstrate gains on benchmarks in math (GSM-Symbolic) and JSON generation.", "questions": "1. For multiple blocks, are there cases where you don’t hit 100 parse?  I was looking at Table 4 and expected to see a number below 100, but was surprised it wasn’t there.\n2. I didn’t understand the “Best of Greedy + Unconstrained” times – is that only adding up the time from the method chosen per problem?  Part of my confusion was that the ‘best of’ can be lower than Greedy Constrained.\n3.  Could you add the computational complexity of the Greedy Constrained method (autoregressive proxy)? Is there an implication for the number of steps used in practice? Greedy Constrained presumably needs to take d steps, so are there situations in which DINGO should be faster than greedy?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "## Strengths\n* Novelty & significance: fills a significant current gap (constrained generation for diffusion), and seems like it'll be a baseline/reference for future work in this area.\n* Writing/Messaging: States contributions clearly\n* Empirical results: Strong results, and included ablations across number of steps, number of blocks, and more.  Very clearly presented.\n* Great to have proofs of both correctness and optimality\n* Owns limitations of method; demonstrates optimality within constraints.\n* Supplementary materials\n  * Code is provided.  I didn’t run, but it was clear from the structure and READMEs that thought was put into sharing this with the community and making it easy to reproduce\n  * Good case studies demonstrated\n  * Stats around states & transitions are nice (supports intuition and suggestions for areas to increase inference speed if willing to sacrifice 100% correctness)\n\n## Weaknesses\n* Multiple blocks – showing limitations\n  * Empirical results were great, but they didn’t show any deficits\n  * It would be great to show extreme samples/constraints where this could be suboptimal\n* Be more clear about limitations of regex-based constraints - this was mentioned at the end of the paper, but would be great to cover in the intro more thoroughly to motivate and constrain the work.\n\n## Small suggestions\n* Define DFA before using the acronym; would be helpful to define “live state” in more colloquial terms as well (for readers from LLM rather than formal logic backgrounds) \n* Little thing: “Algorithm 1 Dingo DP” should probably have the acronym spelled out for readers who are skimming your paper on the first pass \n* Related works just before the conclusion was a strange choice to me – seems like it belongs before the background for this paper?\n* Demonstrate the flexibility and limitations of regex-based constraints (as opposed to other methods) through a few example samples that aren't derived from benchmarks\n* [nit] \"fulll parsable generation\" (full)", "was_revised": true, "final_justification": "My initial positive review of the paper stands, and is only strengthened by the comments from the authors.", "rebuttal": "Thanks for your constructive feedback.\n\n> Q1. Extreme samples/constraints where this could be suboptimal\n\n**R1:** In the practical cases considered in the paper, we did not observe any parsing errors across multiple blocks. However, theoretically, parsing errors can occur when the generation is **only** a valid prefix of a parsable string but not parsable on its own. A simple example is when the total generation length is shorter than the length of the shortest acceptable string in the regular language. In such cases, DINGO can only generate a valid prefix of a parsable string, but not a complete one.\n\n> Q2. Be more clear about limitations of regex-based constraints.\n\n**R2:** Thank you for the suggestion. We will include a more detailed discussion of the limitations of regex-based constraints in the revised version of the paper.\n\n>Q3. For multiple blocks, are there cases where you don’t hit 100 parse? \n\n**R3:** Please refer to the response to Q1.\n\n> Q4. \"Best of Greedy + Unconstrained\" times – is that only adding up the time from the method chosen per problem? Part of my confusion was that the ‘best of’ can be lower than Greedy Constrained.\n\n**R4:** In the \"Best of Greedy + Unconstrained\" approach, we run both the Greedy and Unconstrained methods in parallel and report the runtime of the method that completes first and returns a parsable string. For this reason, the runtime of the \"Best of\" approach can be lower than that of Greedy Constrained. We will clarify this in the revised version of the paper.\n\n\n> Q5. Could you add the computational complexity of the Greedy Constrained method (autoregressive proxy)? \n\n**R5:** Assuming that the token mask indicating the set of syntactically invalid tokens at each position is precomputed \\[1], the complexity of greedy constrained decoding is $O(d \\times |V|)$, where $d$ is the block size and $|V|$ is the vocabulary size. While the greedy approach is more efficient, it is not optimal and, as demonstrated by our experiments, yields suboptimal results.\n \n\n[1] SynCode: LLM Generation with Grammar Augmentation, TMLR, 2025.\n\n> Q6. Other Suggestions.\n\n**R6:** Thank you for pointing this out. We will address these issues in the revised version of the paper."}, {"review_id": "0il7xudqat", "reviewer": "Reviewer_tkTe", "summary": "This paper introduces DINGO, a constrained decoding algorithm for diffusion LLMs that supports regular expression. DINGO uses dynamic programming to find optimal output for each masked token while ensuring entire output is a valid prefix within the grammar. Specifically, DP algorithm maintains maximum probability in which a state $q$ can be reached from the initial state $q_0$ via transitions on token sequence of length $i$, and the corresponding transition. The evaluation shows that DINGO effectively eliminates syntactic error in output, without probability distortion happening in constrained decoding for autoregressive models.", "questions": "1. Parallelism is a key advantage of diffusion LLMs, enabling time-efficient output generation. It also appears that many parts of the DINGO DP algorithm could also benefit from parallelization (e.g., parallelizing lines 12-15 for the same i). Could you clarify whether the reported number reflect a parallelized implementation, or if they were obtained from sequential computation?\n\n2. DINGO has reasonable overhead for regular expression used in the evaluation. However, the grammar used in the evaluation seems not very complicated and output length seems small. The algorithm’s scalability raises concerns, primarily because most of the computation occurs at inference time. Are there opportunities to save more computation or offload more computation to an offline preprocessing stage?\n\n3. Does 'diffusion step' in lines 233-234 mean 'token index' or 'generation length'? $d$ seems like a output length, not the diffusion steps.", "limitations": "Limitations are adequately addressed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The paper is written clearly.\n- The paper proposes first formalization of constrained decoding for diffusion LLMs, with algorithm for regular language.\n- The evaluation shows that DINGO has reasonable overhead over unconstrained generation\n\nWeaknesses\n\n- As authors addressed, DINGO is limited to regular language constraints.\n- DINGO algorithm only tracks the output with the maximum likelihood, and hence is limited to sampling only the maximum likelihood solution.", "was_revised": true, "final_justification": "The authors' rebuttal was very helpful in clarifying the implementation of the DINGO algorithm. While DINGO is a straightforward DP-based algorithm for grammatical completion, I believe an efficient Rust implementation and its parallelization are also significant practical contributions. I believe explicitly including these aspects within the paper would further strengthen the paper. Additionally, their responses to other reviewers clarified that generalization to top-k sampling also yields reasonable performance, which effectively addresses a concern I raised in my initial review. I have updated my rating to 5 and look forward to the promised updates.", "rebuttal": "Thanks for your constructive feedback.\n\n> Q1.  Could you clarify whether the reported number reflect a parallelized implementation, or if they were obtained from sequential computation?\n\n**R1:** Our implementation is highly vectorized and written in TorchScript for better thread-level and kernel-level parallelism [1]. All the reported numbers are from the parallelized implementation, as shown in Appendix C of the supplementary material. \n\n> Q2. Are there opportunities to save more computation or offload more computation to an offline preprocessing stage?\n\n**R2:** We already apply several optimizations offline to reduce runtime overhead. First, we minimize the input DFA, which reduces the number of states while preserving language equivalence. We use the framework from [2] to perform this minimization during the preprocessing stage. Additionally, we cache the DFA's transition table as 1D COO (coordinate list) form tensors [1]. This allows us to exploit sparsity in the state transitions (for instance, eliminating the for loop in line 12 of Algo 1).  There is potential to further improve on these optimizations that can be offloaded to a preprocessing step, and we leave these as future work. \n\n\n\n[1] \"PyTorch: an imperative style, high-performance deep learning library\", NeurIPS 2019\n\n[2] docs.rs/regex-automata/latest/regex_automata/\n \n\n> Q3. Does 'diffusion step' in lines 233-234 mean 'token index' or 'generation length'? seems like a output length, not the diffusion steps.\n\n**R3:** Thank you for pointing out this typographical error. As you correctly noted, $d$ refers to the length of the generated block. We will fix this in the revised version of the paper."}, {"review_id": "qBRXl7BsJ8", "reviewer": "Reviewer_aUe8", "summary": "This paper proposed an algorithm that guarantees the generated sequence of a diffusion LLM strictly satisfies a given regular expression. The special mask token $\\bot$ in diffusion LLM is regarded as a \"wildcard token\" that can represent any actual token, and the sequence generation task is formulated as a constrained optimization problem to find the sequence with the highest probability while satisfying the constraint of the given regular expression. The regular expression is transformed to a DFA, then a dynamic programming algorithm is proposed to solve the problem. For the $i$-th token position and each state $q$ in the DFA, the algorithm maintains $W[i, q]$, the maximum probability with which a state $q$ can be reached from the start state $q_0$ via transitions on some token sequence with length $i$, which can be computed via the transition function $W[i, q] = \\max_{q' \\in Q} W[i-1, q'] \\cdot V(q', q)$, in which $V(q', q)$ is the maximal transition probability from state $q'$ to state $q$ via a specific token (including via the special mask token $\\bot$). Experiments are conducted on JSON and math expressions, with 100% syntactical accuracy and improved functional accuracy.", "questions": "No questions yet", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "## Strength\n- As far as I know, this is the first work to achieve provable constrained decoding on diffusion LLM (another work Cardei et al. [2025] on diffusion LLM encourages but does not guarantee constraint satisfaction)\n- The application of dynamic programming improves efficiency \n- Efficient implementation with Rust. \n- The experimental results look promising, with 100% syntactical accuracy, improved functional accuracy, and no significant increase in time cost.\n\n## Weaknesses\n- Only applies to regular language constraints\n- Not super scalable\n\nHowever, these limitations are understandable and have been mentioned in the paper.", "was_revised": true, "final_justification": "I acknowledge that I have read the new experimental result about scalability. I evaluated positively on the paper, and would like to maintain the score.", "rebuttal": "Thanks for your constructive feedback.\n\n>Q1. Only applies to regular language constraints. Not super scalable. However, these limitations are understandable and have been mentioned in the paper.\n\n**R1:** We have added additional experiments to substantiate the scalability of DINGO with DFAs with larger state sizes. \n\nWe randomly generate DFAs with larger state counts, where transitions between states were assigned randomly. As shown in Table 1, DINGO incurs only a marginal additional cost when the generation length scales proportionally with the size of the DFA.\nThese experiments were conducted using the same hardware setup as described in the paper. We used a single block, **generation length equal to the number of DFA states**, and the number of diffusion steps set to one-fourth of the generation length. Each experiment was run five times, and we report the 95% confidence interval across these runs. \n\nTable 1: Ablation Study of DINGO overhead for varying number of DFA states\n\n| Model      | # DFA states | Method   | Time (s) |\n|------------|---------|-------------------------------------|----------|\n|LLaDA-8B-I| 10|Unconstrained | 0.08 $\\pm$ 0.01 |\n|| | Greedy Constrained| 0.08 $\\pm$  0.01 |\n|| | Diffusion Constrained | 0.08 $\\pm$  0.01 |\n|| 100| Unconstrained |0.95 $\\pm$  0.02 |\n|| | Greedy Constrained| 0.98 $\\pm$  0.04|\n|| | Diffusion Constrained | 1.02 $\\pm$  0.04 |\n|| 1000|Unconstrained | 57.96 $\\pm$  0.32 |\n|| | Greedy Constrained| 58.68 $\\pm$  0.33 | \n|| | Diffusion Constrained |59.33 $\\pm$  0.47 |\n|| 2000| Unconstrained| 242.96 $\\pm$  0.68 |\n|| | Greedy Constrained| 244.78 $\\pm$  0.91 |\n|| | Diffusion Constrained | 245.42 $\\pm$  0.75|\n|DREAM-7B-I| 10|Unconstrained | 0.06 $\\pm$  0.01 |\n|| | Greedy Constrained| 0.06 $\\pm$  0.01 |\n|| | Diffusion Constrained | 0.06 $\\pm$  0.01 |\n|| 100| Unconstrained |0.91 $\\pm$  0.02 |\n|| | Greedy Constrained| 1.02 $\\pm$  0.03|\n|| | Diffusion Constrained | 0.98 $\\pm$  0.02 |\n|| 1000|Unconstrained | 62.36 $\\pm$  0.51 |\n|| | Greedy Constrained| 62.53 $\\pm$  0.38| \n|| | Diffusion Constrained |62.97 $\\pm$  0.27 |\n|| 2000| Unconstrained| 264.05 $\\pm$  0.84 |\n|| | Greedy Constrained| 266.42 $\\pm$  0.93 |\n|| | Diffusion Constrained | 266.25 $\\pm$  0.99 |"}]

Author rebuttal:

Meta-review: The paper studies constrained decoding for diffusion models, which is an interesting and timely topic to study. The proposed algorithm is based on the conditional independency property of diffusion language models and uses dynamic programming to efficiently enforce constraints while offers strong theoretical guarantee in terms of the final decoded sequence. The author provides theoretical justifications on the algorithm's correctness and optimality. Experiments on math reasoning and text-to-json generation tasks are provided to demonstrate their advantage over unconstrained decoding and baselines base on greedy resampling. 

The reviewers all appreciated the novelty of the paper, its solid theoretical guarantee, and strong empirical performance. During the discussion phase, concerns were raised about lack of comparison to reasonable baselines, the limitation of the method to sample the maximum likelihood sequence, and scalability of the method to large state size. The reviewers were satisfied after the authors provided experimental comparison with other baseline algorithms including sample-filter and format fine-tuning, presented an extension to sequence-level top-k sampling, and discussed its scalability implications.

Overall, there is a consensus among the reviewers that the paper makes a solid contribution and should be highlighted in the conference. Hence I would recommend an acceptance for the paper. The authors should include the provided additional experiments and incorporate the reviewers' suggestions in the final revision.
Decision: Accept (poster)