DINGO: Constrained Inference for Diffusion LLMs

Thanks for your constructive feedback.

Q1. Only applies to regular language constraints. Not super scalable. However, these limitations are understandable and have been mentioned in the paper.

R1: We have added additional experiments to substantiate the scalability of DINGO with DFAs with larger state sizes.

We 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. These 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.

Table 1: Ablation Study of DINGO overhead for varying number of DFA states

I acknowledge that I have read the new experimental result about scalability, which has addressed my concern. I evaluated positively on the paper, and would like to maintain the score.

Thanks for your constructive feedback.

Q1. Empirical evaluation against other constrained decoding approaches for diffusion models.

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.

For 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.

For 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.

For all experiments, we used a single block, a generation length of 128, and 64 diffusion steps.

Table 1: Comparison of Different Methods for JSON-Mode.

[1] huggingface.co/datasets/ChristianAzinn/json-training

[2] github.com/dllm-reasoning/d1/tree/main

Q2. Impact of varying output lengths and different unmasking schedules.

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.

Table 2: Ablation Study For Different Output Lengths for JSON-Mode.

All experiments in Table 2 use a single block, 64 diffusion steps and generation length of 128.

Table 3: Ablation Study For Different Unmasking Schedules for JSON-Mode.

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?

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. We believe that efficiently supporting multiple regular constraints while maintaining both optimality and correctness is an interesting direction for future work.

[1]"On the State Complexity of Intersection of Regular Languages", ACM SIGACT News, 1991.
[2] docs.rs/regex-automata/latest/regex_automata/

Thanks for your constructive feedback.

Q1. Could you clarify whether the reported number reflect a parallelized implementation, or if they were obtained from sequential computation?

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.

Q2. Are there opportunities to save more computation or offload more computation to an offline preprocessing stage?

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.

[1] "PyTorch: an imperative style, high-performance deep learning library", NeurIPS 2019

[2] docs.rs/regex-automata/latest/regex_automata/

Q3. Does 'diffusion step' in lines 233-234 mean 'token index' or 'generation length'? seems like a output length, not the diffusion steps.

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.

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 no further questions and have updated my rating to 5, as the rebuttal satisfactorily addressed my concerns.

Thanks for your constructive feedback.

Q1. Extreme samples/constraints where this could be suboptimal

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.

Q2. Be more clear about limitations of regex-based constraints.

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.

Q3. For multiple blocks, are there cases where you don’t hit 100 parse?

R3: Please refer to the response to Q1.

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.

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.

Q5. Could you add the computational complexity of the Greedy Constrained method (autoregressive proxy)?

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.

[1] SynCode: LLM Generation with Grammar Augmentation, TMLR, 2025.

Q6. Other Suggestions.

R6: Thank you for pointing this out. We will address these issues in the revised version of the paper.

Thanks for your constructive feedback.

Q1. Diverse topk Sampling with DINGO.

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.

We 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.

Table 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.

Q2. Scalability with large states in the DFA.

R2: We already report the number of states in the DFAs used in our experiments, with the largest DFA containing 455 states. To 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. These 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.

Table 2: Ablation Study of DINGO overhead for varying number of DFA states

Q3. Comparison with other potential baselines

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.

For 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.

For 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.

For all experiments, we used a single block, a generation length of 128, and 64 diffusion steps.

Table 3: Comparison of Different Methods for JSON-Mode.

[1] huggingface.co/datasets/ChristianAzinn/json-training

[2] github.com/dllm-reasoning/d1/tree/main

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]

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.