Constrained Decoding of Diffusion LLMs with Context-Free Grammars
Authors: Niels Mündler
Jasper Dekoninck
Martin Vechev
Venue: ICLR 2026 Poster (2026)
Keywords: diffusion llm
constrained decoding
llm
code generation
json
multi-region infilling
fill in the middle
code synthesis
Primary area: generative models
TL;DR: We reduce constrained decoding for generalized code generation paradigms to an operation on formal languages, enabling constrained decoding for infilling and diffusion LLMs.

Abstract: Large language models (LLMs) have shown promising performance across diverse domains. Many practical applications of LLMs, such as code completion and structured data extraction, require adherence to syntactic constraints specified by a formal language. Yet, due to their probabilistic nature, LLM output is not guaranteed to adhere to such formal languages. To address this, prior work has proposed constrained decoding to restrict LLM generation to particular formal languages. However, existing works are not applicable to the emerging paradigm of diffusion LLMs, as this requires supporting token generation in arbitrary order instead of the traditional left-to-right order. In this paper, we address this challenge and present the first constrained decoding method for diffusion models, one that can handle formal languages captured by context-free grammars. We begin by reducing constrained decoding to the more general additive infilling problem, which asks whether a partial output with holes can be completed to a valid word in the target language. This problem also naturally subsumes the previously unaddressed multi-region infilling constrained decoding. We then reduce this problem to the task of deciding whether the intersection of the target language and a regular language is empty and present an efficient algorithm to solve this task for context-free languages. Empirical results on various applications, such as C++ code infilling and structured data extraction in JSON, demonstrate that our method achieves near-perfect syntactic correctness while consistently preserving or improving functional correctness. Importantly, our efficiency optimizations ensure that the computational overhead remains practical.

Published as a conference paper at ICLR 2026
CONSTRAINED DECODING OF DIFFUSION LLMs WITH FREE GRAMMARS
Niels Mündler, Jasper Dekoninck, Martin Vechev
Department of Computer Science ETH Zurich, Switzerland
jasper dew.nninck,mrrin...eeetieee /tt.ddddee..ppppeeeeeeeeeeeeeaer eethhe
https://conttrahnelldiffiuuus httt:://ggthhii..cm//tttsstt/sss diffusion
ABSTRACT
Large language models (LLMs) have shown promising performance across di- verse domains. Many practical applications of LLMs, such as code completion and structured data extraction, require adherence syntactic constraints specified by a formal language. Yet, due to their probabilistic nature, LLM output is not guaranteed to adhere to such formal languages. To address this, prior work has proposed constrained decoding to restrict LLM generation to particular formal languages. However, existing works are not applicable to the emerging paradign gm of diffusion LLMs, as this requires supporting token generation in arbitrary order instead of the traditional left-to-right order. In this paper, we address this chal- lenge and present the first constrained decoding method for diffusion models, that can handle formal languages captured by context-free grammars. Our method relies on solving newly defined additive infilling problem, which asks whether a partial output with holes can be completed to a valid word in the target language. We reduce this problem to deciding whether the intersection of the target language and particular regular language is empty, and present an efficient decision algo- rithm for context-free languages. Empirical results on various applications, such as C++ code infilling and structured data extraction in JSON, demonstrate that our method achieves near-perfect syntactic correctness while consistently preserving improving functional correctness. Importantly, our efficiency optimizations sure that the computational overhead remains practical.
INTRODUCTION
Large language models (LLMs) have recently achieved promising performance across a wide range of tasks (OpenAI, 2023; Google DeepMind, 2025). Due to their capabilities in code synthesis, they achieve impressive scores on diverse code benchmarks (Chen et al., 2021; Vero et al., 2025; Jimenez al., 2024; Jain et al., 2025) and integrated into developer workflows programming copilots (GitHub, 2025; Tabnine, 2025). Further, they are used for processing information into machine- readable formats in various domains (Schmidt al., 2025; Schiling-Wilhelln
al., 2024; Goel et al.. 2023). Despite these successes, LLMs are inherently probabilistic and offer no guarantees about syntactic validity of generated output, providing an inherent limitation for LLM users.
Constrained decoding A promising approach that mitigates this limitation is constrained decod- ing (Poesia et al., 2022; Beurer-Kellne et al., 2024; Ugare et al., 2024; Melcer et al., 2024). This technique leverages the formal grammar of target language to guide the generation process, ensur- ing that the output remains within the language's 's bounds. Constrained decoding leverages parsing and validation of the generated output in lockstep with the incremental generation process, allowing the model to avoid invalid continuations without restarting inference. It has been widely adopted in practice, with commercial providers offering the option restrict output to JSON context-free grammars (OpenAI, 2025a; Anthropic, 2025).
Current limitations of constrained decoding Constrained decoding is usually applied to context- free grammars (CFGs), which capture the syntax of common programming languages and popular data formats, like C++ and JSON (Knuth, 1965; Cogumbreiro, 2020). In this context, they can only be applied left-to-right prefix completion, common LLM generation setting. However,

---

Published as a conference paper at ICLR 2026
Inpat
Update x' ~ M()
int
O { return
Proposal
Proposal
Constraint Language (CFG)
int foo() () return 2
int too () { return
S + Def () Lines
Regex
Regex
Lines Line Lines Def <type> <name>
int foo() () return
int too () { return 2
CFG
CFG
Output a²'
X
Rejected
int foo () { return 2
Figure 1: An overview of our approach. In each step, the input consists of partial text with arbitrarily many infilling regions and a context-free grammar (CFG) specifying formal constraints. During decoding, we sample updated input x' from M. obtained, e-g., by inserting token in one of the regions in x. Our method then intersects the CFG with the regular language of all possible completions of x'. If the intersection is empty, the update is rejected and a new x' sampled. Otherwise, it is accepted and the decoding continues from r'. In the example, the invalid update inserting "foo ()" is rejected and "foo" is accepted instead.
this setting does not capture more advanced use cases with L.Ms,, such as diffusion LLMs. While Melcer et al. (2024) extend constrained decoding to completions between fixed prefix and suffix, and Suresh et al. (2025) constrain diffusion LLMs to regular languages, no prior work supports diffusion LLM constraining with CFGs.
This work: Constrained decoding for MRT and DLMS In this work, we present a generalized method for constrained decoding of diffusion LLMS (DLM), which also naturally subsumes the pre- viously unaddressed setting of multi-region infilling (MRI). We first generalize the formal framework of constrained decoding to support unordered updates of a partial output with arbitrarily many infill- ing regions, capturing both MRI and DLM. The decoding process is illustrated in Figure 1. A model iteratively updates, e.g., inserting a token a specific location. We verify that the updated output valid by intersecting the target language's CFG with the language of all possible partial output completions. This intersection is non-empty if and only if a valid completion exists.
A key challenge in this approach is efficiently determining the intersection's 's emptiness. To this end, we first show that the set of possible completions is described by regular language, allowing us to describe the intersection using standard formal language operations. We then drastically reduce the worst case cubic cost of checking the emptiness of the resulting intersection language using special- ized methods for grammar size reduction and search optimizations, including a custom normal form and an implicit search that avoids generating the entire language.
Experimentally confirmed consistent improvements Our experiments demonstrate a substantial improvement in the reliability of formal language adherence across all evaluated settings. Specif- ically, the algorithm guarantees valid completions in all settings, up to sampling timeouts. Addi- tionally, improves functional correctness by up 7%. Importantly, our approach incurs no initial latency and only modest runtime overhead on tested models, with inference time less than doubling on average, enabling practical usage even for complex constraining grammars.
Key contributions Our three key contributions are: (i) generalized formal constrained decoding framework for the MRI and DLM settings, (ii) novel constrained decoding algorithm for these settings, and (iii) an extensive evaluation our method using state-of-the-ar open-weight infilling and diffusion LLMs, demonstrating consistent improvements in syntactic and functional correctness on C++ code generation, JSON schema extraction, and chemical molecule description.
2 BACKGROUND
We outline the necessary background relevant to this work, including generation paradigms with I.L constrained decoding, and the relevant properties of regular and context-free languages.
2

---

Published as a conference paper at ICLR 2026
PRE waint)
return 2:3
MRI <type>
(1
<
<intac)
(a) Generation paradigms
(b) NFA accepting all possible completions of the MRI example.
Figure/ 2: We consider three left-to-right (PRE, FIM, MRI) and one out-of-order (DLM) generation paradigms (a). The NFA in (b) describes the language of all additive completions for the MRI task.
2.1 LLM GENERATION PARADIGMS
We focus on four generation settings with LLMs illustrated in Figure 2a. The first three approaches are commonly used with autoregressive models and generate outputs left-to-right.
PRE, FIM and MRI The first approach, Prefix generation (PRE) completes a fixed prefix, and is commonly used for synthesizing text code from scratch. Second, Fill-In-the-Mo the-Middle (FIM) completes text between a given prefix and suffix, and is widely used in code completion assistants (GitHub, 2025; JetBrains, 2025). Third, Multi-Region Infilling (MRI) generalizes FIM by allowing prefix and suffix constraints as well as fixed segments in between, with the model infilling the gaps. This enables more flexible editing, useful for repository-level code modifications (Wei al., 2024).
Generation with DLMS Diffusion Language Models (DLMS) (Ye et al., 2025; Nie et al., 2025) iteratively insert tokens into an initially empty or partially filled sequence (I1, T2, Fn) where each is either token from the vocabulary V or mask 1. At each step, the model predicts one or more indices of masked token, i.e., Th = L, and a token E to produce the updated sequence (#1...., Tg-1 10k.... (, Tg+11..... Fn)) This process continues until no masks remain. The number of predicted indices and tokens per forward pass is a hyperparameter that controls a trade-off between increased generation speed and quality (Nie et al., 2025). In the example in Figure 2a, the model time, first producing the return keyword ①. then the
would generate index and token function name 2) and finally the return value 33)
Constrained generation Constrained generation restricts the model to produce outputs that con- form to predefined syntactic or structural rules, ensuring syntactically valid code or adherence to structural patterns (Poesia et al., 2022). Formally, the model must generate an output E L, where is a formal language defining admissible outputs for the given task. Constrained generation is implemented by restricting the model's probability distribution, either using precomputed masks (Ugare et al., 2024; Poesia et al., 2022), sampling and rejecting invalid tokens (Melcer et al., 2024; Mündler al., 2025) or combination of these (Dong et al., 2024; Beurer- al., 2024).
2.2 REGULAR AND CONTEXT- FREE LANGUAGES
We briefly outline the properties and notation of regular and context-free languages that relevant to our method. We provide a more detailed introduction in Appendix A.
Regular Languages regular language a set of strings that can be described by a deterministic
finite automaton (DFA). A DFA is defined symbols, (3) : Q Σ + Q is a transition function that maps a state and an input symbol to the next state, (4) du E Q is the initial state, and (5) F C Q the set of accepting states. The language a DFA consists of those strings that transition the automaton from the initial to accepting state through the transition function. Non vinemtteriiiistic finite automata (NFA) additionally allow multiple next states for the same state and symbol and traversing e-transitions without consuming symbol. An example is depicted in Figure 2b. Every
tuple (Q, E, 6, go. F), where: (1) Q is finite set
of states, (2) is a finite alphabet
NFA is equivalent to some DFA.
Context-Free ree Languages Context-free languages (CFLs) are a superset of regular languages, in- cluding languages that enforce recursive structures, such as balanced parentheses or nested control statements. They can be described by context- grammars (CFGs). A CFG is a tuple (V, E, P.S).. where: (1) V is a finite set of nonterminals, (2) Σ is a finite set of terminals (with V 2 2), (3)
3

---

Published as a conference paper at ICLR 2026
P is set of productions A a, with A e V and a E (VUE)", and (4) E V is the start symbol. The language is defined as all strings generated by the following procedure: Starting with S, apply rule A + from P to replace nonterminal A with a, until the result contains only terminals.
CONSTRAINED DECODING FOR INFILLING AND DIFFUSION
In this section, first define the decision problem that enables MRI and DLM generation settings, and then introduce our algorithm for efficiently deciding the problem. We then provide adapted constrained decoding algorithms for MRI and DLM. Finally, we show how to apply the algorithm to LLMs, where additional challenges arise from the need to handle tokens instead of terminals.
3.1 THE CONSTRAINED INFILLING PROBLEM
Constrained decoding with infilling First, us define a partial output sequence of strings I; E E" interleaved with infilling regions c & >, i.c., x = Ii m22 ... DZ In constrained decoding. illustrated in Algorithm 1, we com- plete x using model M and target language L. We iteratively sample an updated partial output x' from M (Lines and 2). All updated outputs are derived via additive modifications to x, meaning they either insert string into infilling regions, e.g., insert b into Ic resulting in a bi ic, or remove region by merging adjacent strings, c.g., converting ambme ambe.. We then check whether the updated output can be completed into a valid word in L (Line 3). If not, we reject the update and remove from the model distribution, preventing the loop from resampling the update (Line 8). However, if the update is completable, we replace x with x' (Line 4) and return the output if the update removes the last infilling region (Lines and 6). This is valid since x is both completable and has no infilling regions, implying E L. Since completability is preserved in updates, there always exists a series of additive updates that completes x to be in L.
Algorithm Constrained decuding
Input: Input x, model M, larget language L Output: Completed output x C L
while true do
x' ~ M(x)
if COMPLETTBLL((X" L) then
if then return x
else
reject
Deciding update validity To enable constraining additive generation, need incremental verifier COMPLETABLE to determine whether the regions in partial output can be filled to produce valid output in L. We formalize the decision problem solved by COMPLETABLE as follows:
Definition 1 (Constrained infilling problem). For a language L, partial output I1 ... 7 with 24 E E' and r denoting infilling regions, the constrained infilling problem asks whether there exists a list of
words y [y1,.... Un-1)) such that 21 y1 T2 ... Yn-1 Fn, is in T..
Thus, with the incremental verifier deciding the constrained decision problem, we have effectively reduced constrained decoding with infilling the constrained infilling problem.
Applications of the constrained infilling problem We now reduce constrained decoding for MRI and DLM generation to the constrained infilling problem. For MRI, the list of words corresponds to the list of fixed strings 22, with infilling regions in between. For the DLM setting, we add implicit tokens at the beginning and end of the partially filled sequence and then merge all consecutive non- mask tokens to build x. For example, the sequence (a, 1, I, b, c, 1) becomes x anbens. Note that, similar to prior work (Beurer- Kellner et al., 2024; Ugare et al., 2024), we slightly overapprox- imate the space of possible completions in these representations by allowing infillings of arbitrary size. In practice, there might be practical limitations to the number of tokens an LLM could insert. We discuss this in more detail in Appendix E.
3.2 DECIDING THE CONSTRAINED INFILLING PROBLEM EFFICIENTLY
Overview We now give a brief overview of how to solve the constrained infilling problem eff- ciently. The problem is determined by two separate constraints: (1) the structural constraints on the output, described by the context-free language L, and (2) all possible completions of the partial output x. which form a language Cx. For example, L could be the language of syntactically valid C++ programs, and Cx the language of completions of partial program x =int () (m2;). The infilling problem is answered positively if and only if the intersection Ln L n Cx is not empty, ie., some infilling of the partial output exists to generate a valid word L. We will show that Cx regular language that describe with a simple DFA, and that In can be described by
4

---

Published as a conference paper at ICLR 2026
context-free grammar, which we can construct from L's grammar and Cx's DFA. The constrained infilling problem is then reduced to checking whether Ln is empty, for which we design an efficient algorithm. In the example, word in the intersection language is int main() {return 2;}.
Constructing the regular language The language Cx of all possible completions of T10. I contains all words that start with 21, end with In, and contain the strings x; (1 I i n) in the correct order, with arbitrary symbols in between. We prove that Cx is regular by constructing an NFA that accepts Cx. We first construct automata D;, which accept exactly x;.- Then, we con- catenate Dj with an additional state qi that accepts any string in Σx, i.e., 8(9s; 0) 9 for all a E. For the concatenation, we add an E-edge from the accepting states of D, to qi and from to the start state of D A visualization for the prior example is shown in Figure 2b. In our algorithm, we construct this NFA for each update. We then transform it into an equivalent DFA and minimize the DFA using standard methods (Hoperoft and Ullman, 1979), as shown in Figure 3b.
Constructing the intersection language We leverage the well-established facts that (a) the inter- section Ln of CFL L and regular language Cxx is a CFL, whose grammar can be constructed from Il's grammar G and Cx 's DFA, and (b) that the emptiness of a CFL can be checked in time polyno- mial to the size of the grammar (Gasarch, 2014; Hopcroft and Ullman, 1979). The symbols in the intersection language have the form P "Ā" for p,4 Σ and A E V, where each symbol intuitively represents deriving a word from A that also traverses the DFA from state to q. The language is nonempty if we can derive a word from 5 for start symbol S and initial and final state qu and qy- An example of deriving a word in the intersection language is shown in Figure 3c. The inter- section grammar Gn (Vn, E, Pn.Sn) will have a cubic size in nonterminals and productions, with |Vol E O(IVIQQ? and [Prl E O(P[[Q|| + |P|[Q| (|X)) (Gasarch, 2014; 4; Bar-Hillel et al., 1961). While we can not reduce the worst case complexity of this blowup, carefully construct the intersection language to keep its size at a minimum, and employ several heuristics to reduce the practical cost of determining its emptiness, explained next.
Efficient normalization The standard intersection algorithms require G to be transformed to Chomsky normal form, which only allows rules of the form A + BC or A + where A, C E V and E Σ (Hopcroft and Ullman, 1979). The resulting grammar may have a quadratic increase in the number of production rules (Lange and Leiß, 2009). To avoid this increase, we ex- tend the standard construction to support CFGs in C2F+e, a normal form that additionally allows productions of the form A + E and A + B. We provide an example of the normalized C++ gram- mar in Figure 3a. This normal form can be obtained with only a linear increase in production rules (Lange and LeiB, 2009). Our adaptations to the standard intersection algorithm and a proof of its correctness are provided in Appendix B.1. In Appendix B.2, we describe several further heuristics to reduce the size of the normalized CFG of G. After this step, we intersect the languages and determine the emptiness of the intersection language.
Avoiding nongenerating nonterminals The standard algorithm to determine whether language is empty determines whether the start symbol S is generating, i.e., whether there is sequence of production applications S + ... + w such that w E Σ.. This property can be decided in time linear to the size of L. (Hopcroft and Ullman, 1979). When applied to intersection language Ln. it is important to note that intersection languages contain a significant fraction of non-generating symbols (Nederhof and Satta, 2008; Hanneforth, 2011). We therefore adopt a bottom-up search, that by construction only explores generating symbols (Sipser, 1996), and adapt it to C2F The algorithm starts with symbols that generate terminals or empty strings directly, i.c., all A with productions A + a and A + E. It marks these symbols as generating and inserts them into queue. Next, for each symbol X in the queue, it checks whether some production has X on the right-hand side (i.e., either A + XC, A + BX or A + X), and whether the other symbol (B or C') in the production was previously marked as generating.
so, A is marked as generating and added to the queue. As soon as the start symbol S is marked, we conclude that the language is non-empty. We confirm in our experiments that this avoids exploring 98% to 99.99% of productions in Ln-
Searching through the implicit intersection language To speed up the emptiness check, we avoid constructing the entire intersection language. Instead, we only construct the parts of the lan- guage visited during the search. All symbols in the intersection language have the form "A" for p.q E Σ and A E V. All production rules in the intersection grammar are directly derived from corresponding rules in the original CFG. Specifically, all rules of the form P 'A" E and P "A"
5

---

Published as a conference paper at ICLR 2026
(e) Nommllzzd CPG (C2FT)))
Minimiood completions
5- ber 51
slypee
<ints
51 - T( 52
52
Lines 1)
Lines - Line Lines1
<typex
<hange
Lines: - Lines
dy-ieh Tomas-
Lines
Tatpe- Def1
Oct: - Taxame
do-+d Teryee
doondd Defy
T1
[]
dg mn da Det
Tetypa <type>
Tenars <02E0>>
Desivation word in Japt
Figure 3: Examples of Figures 1 and processed during our method. (a) The grammar is first normalized into C2F+s, and (b) the NFA is transformed into a minimal DFA. (c) To determine emptiness of Ln, the algorithm then searches the initial state reverse, starting from the terminals.
d0 5 through the productions in
are based on corresponding rules A and A a in the original grammar without further depen- dencies, allowing us to iterate over directly generating symbols without constructing the remaining grammar. Further, all other rules are of the form p "x "B" and " "13" based original productions A + BC and A - B, for all p. r E Q. This enables enumerating all such rules for a given "B" "O" "B" during the search. We present the corresponding pseudo-code and additional explanations in Appendix B.3.
Sampling a valid completion from the intersection language The algorithm presented above decides intersection emptiness. We now extend it to return valid completion from the intersection language. To achieve this, we modify the algorithm to track production rules that were applied when marking symbols as generating- These rules describe a parse tree for some word in the intersection language. We traverse the terminals at the leaf nodes of this tree from left to right to reconstruct valid completion number of rejected updates from the LLM. Since the algorithm leverages the results from the prior emptiness search, it can be run at no additional cost.
the intersection language. This complction is used after a fixed
3.3 APPLICATION OF CONSTRAINED INFILLING TO LLMS
We briefly outline how apply the algorithm from $3.2 to LLMs, which generate arbitrary Unicode text rather than language terminals. Full details are provided in Appendix C.
Lexing For typical applications of CFGs, a string of Unicode characters is converted to terminals 11.. ..... & in a process called lexing. First, note that every terminal t corresponds language R. over Unicode characters. During lexing, é is obtained by finding the terminal & such that Rt matches prefix p of u, i.e., u = p 8. The lexing process then recurses on u' to obtain the remainder of continuing until the string is empty. In principle, apply this procedure to sequence with infilling regions 81 L8 1. 2;} would be lexed to <type> D { <int> }.
regular
Sk. we would lex each consecutive string s; to obtain x =
40... D(,, For example, int However, several caveats to this procedure need to be addressed.
Handling infilling regions First, it does not accurately handle partial terminals that border infilling regions, since L.M tokens are Unicode strings that may not align with terminals. For example, the partial LLM output 12 could correspond to both <int> and <ident>, The ambiguity stems from the possibility to fill the gap with, e.g., either the token x or 1, resulting in x2 or 12 respectively.
To address this, treat the text around an infilling region as possibly belonging to incomplete terminal. Specifically, in the lexing process, we additionally look for terminals such that the current output is prefix of word in R, right before an infilling region Further, we include terminals t that could span across one or more infilling regions by determining if prefixes and suffixes be infilled to form single word in Rr, as in the example above. We
suffix right after region.

---

Published as a conference paper at ICLR 2026
can thus generate all terminal sequences consistent with partial output. If any such sequence be completed to a valid program. then the partial output itself admits a valid completion. In the example above, algorithm would yield two possible lexings, both t <int> and <ident>, and intersect both with the context-free grammar..
Efficiency optimizations The number of possible terminal sequences grows quickly with the num- ber of regions and ambiguities. To improve efficiency, we introduce optimizations. First, for each 2, we directly construct a single NFA for all possible terminal sequences. This allows us to apply the intersection algorithm once rather than for each sequence. Second, we reduce ambigu- ity by preprocessing terminals: whenever the accepted language of terminal E& is contained within terminal 12, we remove the overlap from tz and adapt the CFG to allow ig wherever lz allowed.
Sampling valid completion The sampling method from $3.2 returns a sequence of terminals rather than Unicode characters. To sample a Unicode completion, we first concatenate the regular languages the terminals the sampled completion. We then construct a regular language for the current partial LLM output and intersect the two languages. Sampling random string from this intersection yields a valid completion at the Unicode level. In the given example, we would con- struct regular language of terminals R(<type>) R(<name>) R(O) RO) R(() R(<int>) R()) and intersect with int * (){ * 2;), resulting in int x()
3.4 SOUNDNESS, COMPLETENESS, AND ALIGNMENT
In this subsection, we briefly analyze desirable properties of our algorithm. We first show that the algorithm is sound and complete with respect to the constrained grammar, and fulfills the minimal invasiveness guarantees introduced by Beurer-Kellner et al. (2024).
Soundness and Completeness Our algorithm is sound, i.e., all generated output is valid according to the formal grammar and lexer. This requires the assumption that the lexer of the target language uses maximal munch for lexing, is common in many programming languages (Park et al., 2024; Melcer et al., 2024). Moreover, our algorithm is complete, i.e., it allows sampling any token that would result in a correct output. A detailed proof of these properties is provided in Appendix C, together with a more precise description of the employed lexing algorithm.
Minimally invasive Our algorithm minimally invasive (Beurer-Kellner et al., 2024). This means that, if the model M without constraints would generate valid output L, it will also produce the valid output when our constraining algorithm is applied. This follows from the algorithm's 's completeness; does not reject any partial variants of valid output. Therefore, in Algorithm 1 for the case where M suggests only valid partial outputs, each x' would be marked as completable, and the algorithm thus would return the same output if the check was not present.
EXPERIMENTAL EVALUATION
We evaluate our method across range of tasks and models, first in the MRI setting, and then in DLM, demonstrating improvements in both syntactic and functional correctness. We provide further experimental details, ablate DLM diffusion steps, and provide a case study in Appendix D.
4.1 EXPERIMENTAL SETUP
Metrics We compute two main metrics to evaluate the effectiveness of our method. First, we de- termine the percentage of syntactically correct completions (Syntax), which indicates how many of the obtained completions adhere to the specified grammar. We also measure functional correctness (Functional) by either comparing the sample to a golden solution, or by reporting the percentage of solutions that pass all test cases, pass @ I, depending on the dataset. All results are averaged over four independent runs with different seeds. We compute confidence intervals at 95%, boldface best method, and underline all methods over which the increase is not significant. The usual size of the confidence interval 1% to 2%.
We run unconstrained LLM sampling, reported as Vanilla (Van.) and con- strained decoding with our method (Con.). This includes sampling random completions when gen- eration aborts. As an ablation, we report Con," where these aborted instances are marked as syn- tactically and functionally invalid. To decide the cutoff for aborting generation, we method
Compared methods

---

Published as a conference paper at ICLR 2026
on development set of C++, JSON and SMILES tasks. We observe that if a task requires more than 50 resamples, it is functionally correct in only 0.7% of cases. Thus, we significantly speed up the sampling process without losing performance by aborting after 100. Further, all tested tasks can be solved within 256 tokens, which we set as a maximum output size for all methods. On the instruction tuned Ms, further compare the baseline of Grammar Prompting (G.P.) (Wang et al., 2023), where the model is provided with the Grammar Rules in its prompt.
4.2 FILL-IN-THEE-MDDII AND MULTI- REGION--NFILLING
Models We compare the performance of five recent open-weight infilling models, including STAR- CODER2 7B (Lozhkov et al., 2024b), CODEGEMMA 7B (Zhao al., 2024), and the DEEPSERK CODER Family (Guo et al., 2024), covering 7B parameter models from three distinct model families and model sizes from 1.3B to 33B.
Tasks and benchmarks Infilling is commonly used to complete partial code (Bavarian et al., 2022; Fried et al., 2023). We therefore evaluate our method on the C++ translation of the HumanEval dataset (Zheng et al., 2023; Chen et al., 2021), of 164 diverse basic coding tasks. Similar to Bavarian et al. (2022), we construct an infilling dataset by removing random spans from the numan-writter reference implementation. We evaluate up to three removed spans, resulting in 1-MRI, being equiv- alent to FIM, and 2-MRT and 3-MRI, with two and three infilling regions respectively. We design a CFG for the subset of C++ syntax needed solve the tasks in HumanEval. We report adherence to this CFG as syntactic correctness, Functional correctness is measured by computing the pass @ score on provided test cases (Brown et al., 2020). In Appendix D.4, we also evaluate our method when removing specific lines of code rather than random spans, observing similar improvements.
Syntactic correctness As shown in Table 1, our method increases syntactic correctness signifi- cantly across all models and numbers of infilling regions. Our method (Con.) recovers syntac- tically valid completion in on average 95.8% of instances. Remaining errors are due to timeouts. Constrained decoding without completions (Con. increases syntactic correctness more for code with multiple regions. This coincides with models struggling more, achieving an absolute increase of 5.2%, 22.5%, and 31.5% for 1-RRI, 2-MRI, and 3-MRI, respectively. These improvements are consistent across model families and sizes, ranging between 17% and 21% per model.
Functional correctness In the lower half of Table 1, we observe that constraining (Con.) consis- tently increases functional correctness, average by 2.8%, and even without randomly sampling valid completions (Con. 7) the average increase is 2.4%. This is expected, as syntactically incorrect completions can not be functionally correct and effectively prevented by our method.
Runtime overhead We compare the time per token between constrained and vanilla decoding. The median runtime overhead of constrained decoding 4.2 ms, where the overhead on the small DEEPSEEK CODER 1.3B is higher (5.8 ms) than on the 7B models (4.6 ms) and DEEPSEEK CODER 33B (4.3 ms). Moreover, median overhead increases with more complex infilling, growing from 3.1 ms 1-MRI to 7.7 ms on 3-MRI. Further details on runtime are provided in Appendix D.4.
4.3 DIFFUSION LANGUAGE MODELS
Models We evaluate our method on the instruction-tumed versions of four state-of-the-art diffusion language models, L.LADA 8B (Nie et al., 2025), DREAM 7B (Ye et al., 2025), DREAMCODER 7B (Xie et al., 2025) and DIFFUODERR 7B (Gong et al., 2025). We run all models with 32 steps on 256 tokens and with a temperature of 0.2.
Tasks and benchmarks As DLMS are generic text generation models with many different appli- cations, we design three distinct and diverse tasks:
C++
Based on the dataset used in $4.2, the model should generate the entire function specified in natural language (Chen et al., 2021; Zheng et al., 2023).
ISON
The model should extract relevant information from natural language input, adhering to -chemm specification (NousResearch, 2024).
SMILES
The model should write down a chemical molecule described in natural language in the SMILES specification language (Weininger, 1988).
For SMILES and JSON we generate synthetic benchmarks using GEMINI-2.5 P-R-PR (Google Deep- Mind, 2025) with verification to ensure that the generated samples are correct and solvable, resulting
8

---

Published as a conference paper at ICLR 2026
Table 1: Our method consistently improves the percentage of syntactically and functionally correct infillings for varying numbers of regions in MRI under standard decoding (Van.), constrained decod- ing (Con. ), and completing partially completed outputs (Con.).
I-MRI
MRI
3-MRI
Model
Van.
Con. -
Con.
Van.
Con.
Con.
Van.
Con.
Con.
STARCODER2 7B
88.2
95.0
98.9
55.4
77.7
96.3
24.5
57.2
88.3
Syntax
CODEGEMMA 7B
92.5
97.2
100.0
61.5
85.6
99.0
29.9
66.4
96.0
DEEPSEEK C. 1.3B
86.5
91.7
98.7
51.5
72.9
93.1
22.7
47.7
83.0
DEEPSEEK C. 6.7B
93.9
98.3
100.0
62.0
84.0
97.3
32.9
64.9
94.6
DEEPSEEK C. 33B
93.1
97.6
100.0
66.3
86.5
97.8
36.4
67.8
93.5
STARCODER2 7B
53.8
56.1
56.3
20.5
23.7
24.2
7.5
10.3
11.0
Functional
CODEGEMMA 7B
57.1
59.6
59.6
24.8
29.0
29.2
8.7
12.6
12.8
DEEPSEEK C. 1.3B
46.5
46.4
47.2
16.1
18.4
19.2
4.9
5.4
DEEPSEEK C. 6.7B
64.8
67.1
67.3
29.8
32.7
33.2
11.9
13.5
13.5
DEEPSEEK C. 33B
69.8
71.2
71.4
29.8
34.0
34.3
12.6
14.3
15.4
in 167 and 272 instances respectively. We implement the syntax of each language as a CFG and use it to enforce and evaluate the syntactic correctness of the generated output. For C++, we measure functional correctness using pass @ I as in $4.2. For JSON and SMILES, correctness is evaluated by normalizing and comparing to golden solution. More details about the dataset generation proce- dure and the correctness evaluation are provided in Appendix D.3.
Syntax errors We observe that our method consistently increases syntactic correctness for all tasks and models, as shown in Table 2, in stark contrast to the mixed impact of the non-constraining baseline (G.P.). Without sampling valid completions (Con. ). our method increases the percent- age of syntactically correct instances by 16.1%, 14.7%, and 26.0% for C++, JSON, and SMILES, respectively. We observe that many models fail to generate syntactically correct output even under constraints, with, for example, only 19.0% correct C++ generations for DREAMCODER 7B. How- ever, sampling valid completions (Con.) recovers the failed instances, increasing to 99.2%. JSON, constrained decoding with completion achieves 100% syntactic correctness.
Functional correctness As shown in the lower half of Table 2, the consistent positive effect of constraining on functional correctness also present for DLM, with an average increase in func- tional correctness without completions (Con. of 1.9%, and slight additional boost with comple- tions (Con.) to 2.2%. Notably, DREAM 7B performance on JSON increases by 6.9%. DREAM 7B appears benefit a lot from being provided the target syntax (G.P.) in C++ and SMILES, where it outperforms our constraining (Con.). In the SMILES setting, where models generally perform very poorly at only 1.5% average correctness, syntactic constraints not able to improve functional correctness significantly, achieving only modest average increase 0.2%
Runtime overhead We compare the runtime to complete samples constrained decoding with the vanilla setting. The median completion overhead is only 0.1 s. We observe both speed-ups of up to 1s and slowdowns of up to 7.8s. Speed-ups occur when the decoding is preemptively aborted. Further details for this experiment are provided in Appendix D.4.
Comparison to DINGO DINGO (Suresh al., 2025) is recently proposed method for strained decoding regular languages DLMS. Appendix D.5, we show that while our method is more general, being able to enforce context-free constraints, it achieves the same syntactic and similar functional correctness. Furthermore, our method has similar runtime overhead of less than 0.3 ms the tested tasks, without requiring preprocessing opposed to DINGO.
RELATED WORK
Large language models LLMs have gained traction for diverse tasks such as code generation (Tiang al., 2024) and structured output generation (LangChain Developer Documentation, 2025; OpenAI, 2025b; Anthropic. 2025). While the most common approach trains LLMs for PRE genera- tion, many modern code models also support FIM settings (Guo al., 2024; Lozhkov et al., 2024a;

---

Published as a conference paper at ICLR 2026
Table 2: Constrained decoding (Con. consistently increases the percentage of syntactically correct completions for DLMs standard decoding (Van.). Non-constraining baselines like Grammar prompting (G.P.) do not consistently improve syntactic or semantic performance.
C++
JSON
SMILES
Model
Van.
G.P.
Con.
Con.
Van.
G.P.
Con.
Con.
Van.
G.P.
Con.
Con.
DREAM 7B
40.5
48.6
58.7
99.4
22.4
15.7
44.9 100.0
67.7
84.2
93.7
99.4
Syntax
DREAMC. 7B
11.0
9.1
19.0
99.2
73.7
73.3
86.6
100.0
73.1
82.1
94.9
100.0
LLADA 8B
13.3
6.7
36.1
99.7
77.5
76.0
89.0
100.0
58.2
67.4
91.3
100.0
DIFFUC. 7B
39.2
33.1
54.7
99.7
44.9 64.5
76.3
100.0
69.3
57.3
92.2
99.1
DREAM 7B
6.6
11.6
8.8
9.5
7.4
6.6
11.4
14.3
0.6
2.7
1.1
1.1
Funct.
DREAMC. 7B
3.7
0.6
4.9
5.2
44.6
46.2
46.7
46.7
3,4
1.2
3.4
3.4
LLADA 8B
3.8
2.0
5.0
5.3
43.1
50.2
49.5
49.5
0.7
0.6
1.0
1.0
DIFFUC. 7B
12.5
7.6
13.7
14.8
34.3
21.0
38.0
38.2
1.1
0.6
1.1
1.1
Zhao et al., 2024). More recently, diffusion language models have been scaled to billion- parameeer sizes and demonstrate promising performance on variety of tasks (Nie et al., 2025; Gong et al., 2025; Xie et al., 2025). Meanwhile, LLMs are prone to errors during generation. For example, they often make mistakes in niche programming languages (Giagnorio et al., 2025) and fundamentally struggle to model specific types of formal languages (Strobl al., 2024; Ebrahimi et al., 2020).
Constrained decoding Constraining LLM generation to context languages has been explored extensively in prior work (Beurer-Kellnee et al., 2024; Poesia et al., 2022; Kellner et al., 2023: Willard and Louf, 2023). Most prior works apply these techniques the PRE setting (Poesia et al., 2022; Beurer-Kellnee et al., 2024; Ugare et al., 2024; Dong et al., 2024; Sun et al., 2025; Park et al., 2025), with some extensions to FIM and context-sensitive features (Melcer et al., 2024; Mündler et al., 2025). Suresh al. (2025) constrain DLMS specifically, but only to regular languages. To our knowledge, constrained decoding with CFGs has not yet been applied to the MRI or DLM paradigms. Additionally, unlike prior work that employs masking (Ugare et al., 2024; Poesia al., 2022; Beurer-Kellner et al., 2023) or masking-rejection hybrids (Dong et al., 2024; Beurer- al., 2024), our rejection sampling approach incurs no additional latency before starting language inference, significantly reducing friction of switching to a different CFG.
Leveraging language intersections Two similar works leverage the intersection of CFLs and reg- ular languages. First, Fazekas et al. (2024) discuss subsequence matching, which asks whether w a subsequence of any word in language L. This special case of our decision problem, with s.wi w] and can also be solved by using the emptiness check for intersection languages. Their work is not applicable to our setting, as it only handles this special case, does not consider practical performance, and does not consider how to handle lexing.
Second, Nederhof and Satta (2008) use intersections of weighted CFGs and DFAs for parsing natural language words, using the intersection language succinet representation of admissible parses of lexeme sequences. To reduce the size of these intersections, they also filter non-generating symbols during the intersection construction.
CONCLUSION
We presented the first constrained decoding method for diffusion models that is able to handle context-free languages such as C++ and JSON, We showed how to reduce the problem of valid com- pletion infilling decision problem solvable using formal language techniques. Our optimized algorithm demonstrates consistent and significant increase in syntactic and functional correctness on variety of benchmarks and models, while still ensuring efficiency inference time.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
We describe our implementation in detail in $4 and Appendix D, including details such as hy- perparameters and the used compute hardware. Further, all of our experiments fixed seeds and disabled optimizations that would introduce nondeterminism. To ensure com- plete reproducibility of our results, we publicly release the code implementation of our method, as well as datasets, models, and code used for the evaluation at https://gtt thub. com/eth- sri/ constrained di fun We also include the content of this released code an anonymized arti- fact for the double-blin review.
run with
ACKNOWLEDGEMENTS
This work has been done as part of the grant SAFEAI (Certified Safe, Fair and Robust Artificial In- telligence). The work has received funding from the Swiss State Secretariat for Education, Research and Innovation (SERI), contract no. MB22.00088.
REFERENCES
Aho Alfred, Lam Monica, and Ullman Jeffrey. Compilers principles, techniques & tools. 2007.
Anthropic. ISON Mode, 2025. build- with clwude/tool--eeeeeeeooooooaooooe use mode.
URL https://ooossaatrroooccccc/////
Richard L. Apodaca. SMILES Formal Grammar. Depth-First blog post, 2020. URL https://
depth- first.
formal forms--gaaarrr
Y. Bar- Bar-Hillel, M. Perles, and E. Shamier. On formal properties of simple phrase structure grammars. STUF, 1961. URL httpt:tttt///oooooo
wtt.:l.11//.uufffeee.e http:/sfff..99...... 1961. 14. 14. 14.14...
Mohammad Bavarian, Heewoo Jun, Nikolas Tezak, John Schulman, Christine McLeavey, Jerry Tworek, and Mark Chen. Efficient Training of Language Models to Fill in the Middle. arXiv preprint, 2022. URL https://arxxw.org//b//////
14255.
Luca Beurer-Kellner, Mare Fischer, and Martin Vechev. Prompting Is Programming: A Query Language for Large Language Models. PLDI, 2023. URL https://doi. org/10. 1145/3591300.
Luca Beurer-Kellnne Mare Fischer, and Martin Vechev. Guiding LLMs The Right Way: Fast, Non- invasive Constrained Generation. In ICML., 2024. URL http://///pppeeeeeeeeeeee//eeeee
FXaEYzrFae.
Blue Obelisk Project and OpenSMILES Community. OpenSMILES specification (HTML version), 2025. URL http::/opensmilles weweeissmmmleee.... wwwpsess.........eeeess....
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, al. Language Models Few-shot Learners. In NeurIPS, 2020. URL Abstract.hhml.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating Large Language Models Trained on Code. arXiv Preprint, 2021. URL https://arxxi http://rxxi..oor//a/////// 03374.
Karl Cobbe, Vincet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Refichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems, 2021. URL. https::/arxxv..rrr abs/2110. 14168.
Tiago Cogumbreiro. CS420: Introduction the theory of computation, lecture 15: Context-free grammars, 2020. URL https://cogumbret wwwp:ubrrrrrrr...ubbboee htt.hh/...ttacciii/////////////0 pdf.
11

---

Published as a conference paper at ICLR 2026
Leonardo De Moura and Nikolaj Bjørner. Z3: an efficient smt solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Con- struction and Analysis of Systems, TACAS CECCASSS//EAPSST 08, pages 337-340, Berlin, Heidelberg, 2008. Peringer-Verlage ISBN 3540787992.
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.
D.W. Solving the emptiness problem for a CFG in Chomsky normal form (linear). Computer Science Stack Exchange, 2018. URL https: https://cs.staacexxhaaae stackexchange com/q/92314.
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How Can Self-attention Networks Recognize Dyck-n Languages? In EMNLP, 2020. URL
findings- emnlp.384.
Szilárd Zsolt Fazekas, Tore KoB, Florin Manea, Robert Mercaş, and Timo Specht. Subsequence Matching and Analysis Problems for Formal Languages. In ISAAC, 2024. URL h /egsstuhl..deenttiiis///eeeeeeee http:////t...11/11111/// 4230/LIPICS ISAAC. 2824.22 28.
Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang. Eric Wallace, Freda Shi, Ruiqi Zhong, Wen Yih, Luke Zettlemoyer, and Mike Lewis. InCoder: A Generative Model for Code Infilling and Synthesis, 2023. URL https: www.:ntt//ooummidoooooooooo LbM6EL.
William Gasarch. The Intersection of CFG and a REG is CFG, 2014. URL https://www. wwt.wwww...ooo. umd. edl/://esscct///005/5////////// pdf.
Alessandro Giagnorio, Alberto Martin-Lopez, and Gabriele Bavota. Enhancing Code Generation for Low-resource Languages: No Silver Bullet. arXiv Preprint, 2025. URL https://doi.org:
10. 48550/arXii 2501. 1908.
GitHub. Blog, 2025.
Introducing
GitHub URL https://github. wwwg/nlwsww.ooooeo.oooooooooo.. wtwsightsproouuutteeeeee
Copilot: your AI pair programmer. GitHub
introducing wwtpuuuiiiinggtuuue-eeee
ai- wair-pprorammer/
Akshay Goel, Almog Gueta, Omry Gilon, Chang Liu, Sofia Erell, Lan Huong Nguyen, Xiaohong Hao, Bolous Jaber. Shashir Reddy, Rupesh Kartha, Jean Steiner, Itay Laish, and Amir Feder. Lims accelerate annotation for medical information extraction. arXiv Preprint, 2023. URL https:
//arxiv
wwwpxiv.oor/aaee arggabss2311 62296.
Shansan Gong, Ruixiang Zhang, Huangjie Zheng, Jiatao Gu, Navdeep Jaitly, Lingpeng Kong, and Yizhe Zhang. DiffuCoder: Understanding and Improving Masked Diffusion Models for Code Generation. arXiv Preprint, 2025. URL http://aarii...ogaa/////66/6 20639.
Google DeepMind. Gemini Pro, 2025. URL httph::t///eeeee httppss//eepiiioooooooe////eeeed pro/.
Daya Guo, Qihao Zhu, Dejian Yang. Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y. Wu, Y. K. Li, et al. DeepSeek-Coder When the Large I Language Model Meets Program- ming- The Rise of Code Intelligence. arXiv Preprint, 2024. URL httt:::/ddi..rgg/// 48550/ arXiv. 14196.
Thomas Hanneforth. A practical algorithm for intersecting weighted context-free grammars with finite-state automata. In Andreas Maletti and Matthieu Constant, editors, Proceedings of the 9th International Workshop Finite State Methods and Natural Language Processing, pages 57-64, Blois, France, July 2011. Association for Computational Linguistics. URL https:// aclanthology www.oogg.orgg/1111 wwwp/orgg///////oo/o/ooo.ow...ee 4408/.
John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Compu- tation. 1979.
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Lezamaa Koushik Sen, and Ion Stoica. LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code. In ICLR, 2025. URL https://openreviee met/fformmiddcchi2Vc3L.L.
12

---

Published as a conference paper at ICLR 2026
JetBrains. Code completion, auto- auto-complen code. html.
2025. URL http:s//wwww.eerrraaaa.cc//ooooa
Juyong Jiang, Fan Wang, Jiasi Shen, Sungju Kim, and Sunghun Kim. A Survey on Large Language Models for Code Generation. arXiv Preprint, 2024. URL https://doi.org: httg//...855//rxxi. 2406.0055
Carlos E. Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik R. Narasimhan. SWE-hench: Can Language Models Resolve Real-world Github Issues? In ICLR, 2024. http:htttt///peeeeteeee//e wtt.://www..e.eoooor///atttt////
Donald E. Knuth. On the Translation of Languages from Left Right. Inf. Control., 1965. URL
https://doi.. wrg/10..//o////o pttg///..0////00000000 (00000199999665555 984266
Greg Landrum, Paolo Tosco, Brian Kelley, Ricardo Rodriguez, David Cosgrove, Riccardo Vianello, sriniker, Peter Gedeck, Gareth Jones, Fisuke Kawashima, Nadine Schneider, Dan Nealschneider, Andrew Dalke, and tadhurst-cdd al. rdkit/rdkit: Q1 2025 Release. Zenodo, 2025. URL
https://doi.. wtt.e/////....///eeeee 5281/zenodo 16433004...44448...... 16439048.
LangChain Developer Documentation. Structured outputs, 2025. outputs..
URL https://python.
langchain. cww/
Martin Lange and Hans LeiB. To CNF or not CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didactica, 2009.
Anton Lozhkov, Raymond Li, Loubna Ben Allal, Federico Cassano, Joel Lamy-Poiries Nouamane Tazi, Ao Tang, Dmytro Pykhtar, Jiawei Liu, Yuxiang Wei, et al. StarCoder 2 and The Stack v2: The Next Generation. arXiv Preprint, 2024a. URL httpp:://oi..no www..org............ 19173.
2402.
Anton Lozhkov, Raymond Li, Loubna Ben Allal, Federico Cassano, Joel Lamy-Poirier, Nouamane Tazi, Ao Tang, Dmytro Pykhtar, Jiawei Liu, Yuxiang Wei, et al. StarCoder 2 and The Stack v2: The Next Generation. arXiv Preprint, 2024b. URL http::::/ooo.o/////////// http://o.....g///1./55///////// 2402. 19173.
Daniel Melcer, Nathan Fulton, Sanjay Krishna Gouda, and Haifeng Qian. Constrained Decoding for Fill-inthhemmidlle Code Language Models via Efficient Left and Right Quotienting of Context- sensitive Grammars. arXiv Preprint, 2024. URL https://arxiiv http//awwww...gg//////22.2/ 17988.
Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. Gsm-symbolic: Understanding the limitations of mathematical reasoning large language models, 2025. URL https::/arxxv.org//aa /211 25220000020
Niels Mündler, Jingxuan He, Hao Wang, Koushik Sen, Dawn Song, and Martin Vechev. Type- Constrained Code Generation with Language Models. In PLDI, 2025. URL https://doi.org/ 10..145/3729274.
Mark-Jan Nederhof and Giorgio Satta. Probabilistic Parsing. In SCI. 2008. URL https://link. springer. comrngeercom/cooo wwtpptaatpte..... 1007/978- 540 78291-88211000 9_7.
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. arXiv preprint, 2025. URL
https://arxxv.org//ae hww.aaawww...rrrrrr////22..0.. 89992..
NousResearch. json-mode-eval. Hugging Face Datasets, 2024. URL https::/hugginggacceet datasets/NousRese fataseet//lousseseercc//j/oo. mode-evall
Cyrus Omar, Ian Voysey, Ravi Chugh, and Matthew A. Hammer. Live functional programming with typed holes. POPI., 2019. URL https://doi http:///oooooo//././//////// org/10.
1145/3290327. 0r1..//0/...11//992227...
OpenAl. GPT-4 Technical Report. arXiv Preprint, 2023. URL 08774.
13

---

http:///perrreeeeeee.eeerrrrrmoa Published as a conference paper at ICLR 2026
OpenAl. Function calling openai api: Context-free grammars, 2025a. URL https://platfom ppenai.com//oocs//uiideee htwprunnntinnncaannnnnnnteeeeeee 12.
calling#context freeeettt-rre---o free- grammars. Accessed: 2025-08-
OpenAl. Structured Outputs, 2025b.
URL
structured outputs.
Kanghee Park. Jiayu Wang. Taylor Berg-Kirkpatiin Kirkpatrick, Nadia Polikarpova, and Loris D' A'Anton.. Grammar-aligned decoding. NeurIPS, 2024.
Kanghee Park. Timothy Zhou, and Loris D'Anooni. Flexible and efficient erammar-constraiing
decoding. In Forty-second International Conference Machine Learning, 2025. URL https:
//openreview net/ peet/formmt fo
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable Code Generation from Pre-trained Language Models. ICLR, 2022. URL htt.httts::/openreviiee
Julien Romero. Pyformlang: An Educational Library for Formal Language Manipulation. In SIGCSE, 2021. URL
htt.://..or/111111444408333033 110/11401///388333311 343344644
Mara Sechiling-Wilhellme Martiño Ríos-García, Sherjeel Shabih, María Victoria Gil, Santiago Miret, Christoph T. Koch, José A. Márquez, and Kevin Maik Jablonka. From to insight: Large language models for materials science data extraction. arXiv Preprint, 2024. URL https:// arxiv. mrxiv.org/abs/2444 16867.
Lena Schmidt, Kaitlyn Hair, Sergio Graziosi, Fiona Campbell, Claudia Kapp, Alireza Khantey- moori, Dawn Craig, Mark Engelbert, and James Thomas. Exploring the of large language model for data extraction in systematic reviews: rapid feasibility study. arXiv Preprint, 2025. URL http://///aaai..///a//////// orgg 14445.
Michael Sipser. Introduction to the theory of computation. ACM Sigact News, 27(1):27-29, 1996.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What Formal Lan- guages Can Transformers Express? A Survey. TACL, 2024. URL https://doi. 0rg/10.1. 1162/
aacl_a_006662
Xintong Sun, Chi Wei, Minghao Tian, and Shiwen Ni. Earley-driven dynamic pruning for efficient structured decoding. In Forty-second International Conference on Machine Learning, 2025. URL
https://openrevieee wtt.://wetttttooummmdd/oooooass
Tarun Suresh, Debangshu Banerjee, Shubham Ugare, Sasa Misailovic, and Gagandeep Singh. Dingo: Constrained inference for diffusion 1lms. arXiv Preprint, 2025. URL https://arxin org/abs/2505. 23061.
23061.
Tabnine. Tabnine: Al Code Assistant, 2025. URL https://www. http://wwww.aabiiie....m
Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. SynCode: LLM Generation with Grammar Augmentation. ArXiv Preprint, 2024. URL https://arxiv.
org/abs/2403. 01632.
Mark Vero, Niels Mündler, Victor Chibotaru, Veselin Raychev, Maximilian Baader, Nikola Jo- vanović, Jingxuan He, and Martin Vechev. BaxBench: Can LLMs generate correct and secure backends? In ICML, 2025. URL
Bailin Wang, Zi Wang. Xuezhi Wang, Yuan Cao, Rif A. Saurous, and Yoon Kim. Grammar prompting for -ppein- language generation with large language models, 2023. URL https://arxiv. wrw. wwwpoogg/////....oo../....o...// 192344
Jiyy Wei, Greg Durrett, and Isil Dillig. Coeditor: Leveraging repo-level diffs for code auto- editing. In ICLR, 2024. URL https: httpstt////ooceeediiig http///ooennssiieeeccc ictr. cc/ wwtppccc_p..eceeecee filles//aaprr/224/fieee Paper Conference. .ddf.
14

---

Published as a conference paper at ICLR 2026
David Weininger. SMILES, chemical language and information system. 1. Introduction to method- ology and encoding rules. JCIM, 1988. URL https:://doi.orr//1 htt.://///...11111100000000000
Brandon T. Willard and Rémi Louf. Efficient Guided Generation for Large Language Models. arXiv Preprint, 2023. URL https://doi.orr/11 48550/ 2307. 09702.
Zirui Wu, Lin Zheng, Zhihui Xie, Jiacheng Ye, Jiahui Gao, Yansong Feng, Zhenguo Li, Victoria W., Guorui Zhou, and Lingpeng Kong. Dreamon: Diffusion language models for code infilling beyond fixed-size canvas, 2025. URL https: hwtpppittttbhotooooo.oo.. /o/bbl///222222/reemmm
Zhihui Xie, Jiacheng Ye, Lin Zheng, Jiahui Gao, Jingwei Dong, Zirui Wu, Xucliang Zhao, Shansan Gong, Xin Jiang, Zhenguo Li, and Lingpeng Kong. Dream-Coder 7B. HKU NLP Blog, 2025.
URL htthtttts///hulg github..h..u... ht/blo////////// 2tllo///22////rraa coder.
Jiacheng Ye, Zhihui Xie, Lin Zheng, Jiahui Gao, Zirui Wu, Xin Jiang, Zhenguo Li, and Lingpeng Kong, Dream 7B. HKU NLP Blog, 2025. URL https::/hkuulpp.gii gitub. htwblo/g//25///////////
Heri Zhao, Jeffrey Hui, Joshua Howland, Nam Nguyen, Siqi Zuo, Andrea Hu, Christopher A. Choquette-Chon Choo, Jingyue Shen, Joe Kelley, Kshitij Bansal, et al. CodeGemma: Open Code Mod- els Based on Gemma. arXiv Preprint, 2024. URL
11409.
Qinkai Zheng. Xiao Xia, Xu Zou, Yuxiao Dong, Shan Wang, Yufei Xue, Zihan Wang, Lei Shen, Andi Wang, Yang Li, et al. CodeGeeX: A Pre-Trained Model for Code Generation with Multilin- gual Benchmarking HumanEval-X. In SIGKDD, 2023. URL https://dh http://lllacccco/oo///// www.a.o./m.//00../////////// 1145/3580305.1 3599799.
15

---

Published as a conference paper at ICLR 2026
= {S, B} (Nonterminals)
b T
[a. b)
Σ {a, bj
(Terminals)
+ aS bB |
B bB
(a) DFA where go the start state, {go, gı, qı,92 are the states, and go and şi are the accepting states. The arrows represent the transition function 6.
(b) CFG with start symbol S, terminal alphabet
Σ = fa, b}, and nonterminals V = {S, B}. The production rules are the last two lines.
Two representations of a formal language: a DFA (Figure 4a) and CFG (Figure 4b). Both accept strings that start with a's and end with b's.
Figure 4:
A EXTENDED BACKGROUND ON FORMAL LANGUAGES
Formal languages allow to unambiguously specify valid or invalid strings, usually for ensuring machine-readabilitty i.e., in the case of ISON schemas, or when specifying the syntactic rules of programming languages. Formal languages are, in their most general form, defined as a set of strings over an alphabet 2. For instance, over the alphabet > = {a, 6), one can define the formal language {e, b, aa, bb, aabb, aaaabbb,... . of strings consisting of any number a's followed by b's. In this section, we provide short explanation of two key classes of formal languages: regular and context-free languages.
A.1 REGULAR LANGUAGES
Regular languages are commonly encountered when describing string patterns with regular expres- sions. For example, the language of a's followed by b's is described by the regular expression a+b*, where the star denotes zero or more repetitions. A regular language can alternatively be described through a Deterministic Finite Automaton (DFA) that accepts the language (Hopcroft and Ullman, 1979). A DFA is a state machine that processes an input string symbol by symbol, transitioning be- tween states based a deterministic transition function. Thus, string gets processed by the DFA by starting in the initial state and following the transitions associated with the current input symbol until the end of the string is reached. A string is accepted if the DFA ends in accepting state after processing the entire string. Formally, DFA is defined as a tuple (Q, E, 5, qo, F), where: (1) Q is the finite set of states, (2) E is the finite alphabet of symbols, (3) : Q x + Q is the transition function that maps state and an input symbol to the next state, (4) E Q is the initial state, and (5) F' Q is the set of accepting states. Figure 4a depicts the DFA recognizing the previously introduced language of strings with arbitrarily many a's followed by b's. Note that in this example, the transition function is defined for every state and symbol combination. Per convention, omitted transitions implicitly transfer to state like q2, from which no accepting state can be reached.
In DFAs, the next transition thus uniquely determined for each combination of state and input symbol. In contrast, nondeterministic finite automata (NFAs) allow multiple transitions for a state and input symbol combination, making it nondeterministic. One often additionally adds the option to transition between states without consuming any input symbols, through so-called e-transitions. This added flexibility allows for a more concise depiction and simplifies construction, which is why use them throughout this work. NFAs accept word if any possible transition according the input symbols leads to an accepting state. Every NEA (including & e-transitions) can be converted to an equivalent DFA using standard algorithm (Hopcroft and Ullman, 1979). The NFAs constructed for partial L.LM outputs in our method are usually converted into a DFA of around the same number of states, even though the worst-case equivalent DFA can have exponentially many states.
A.2 CONTEXT FREE LANGUAGES
Context-Free Languages (CFLs) extend regular languages by enabling the expression of recursively nested structures, such as balanced parentheses or properly nested control statements in code. They described using Context- Free Grammars (CFGs), which consist of production rules that specify how strings in the language can be generated (Hopcroft and Ullman, 1979). For most programming languages, the syntactic rules of the language can be adequately captured by CFG.
16

---

Published as a conference paper at ICLR 2026
CFGs operate with two types of symbols: terminals, which are the actual characters of the language, and nonterminals, which are used to define the language patterns. A CFG a formal grammar that consists of finite set of production rules that describe how strings in the language can be generated. Formally, a CFG is a tuple (V, X2, P. P)S), where: (1) V is a finite set of nonterminal symbols, (2) E is finite set of terminal symbols (with V E = Ø), (3) P is set of production rules of the form A + a, with A E V and a E UZ)". and (4) S E V is the start symbol. To generate string, one starts with S and applies rules from P until the resulting string contains only terminal symbols. This process defines all valid strings in the language. Figure 4b shows CFG that generates strings over {a. b) starting with arbitrarily many a's followed by b's, demonstrating that the same language recognized by DFA can also be described by CFG. To generate the string aabb, one could apply the following sequence of production rules: + aS - anS - aabB + aabb + aabb.
CFGs are often specified in normal forms, which restrict the grammar to certain types of production rules. The benefit of the resulting language is that reduces edge cases to handle in productions and simplifies proofs about properties of the language. The most common normal form is the Chomsky normal form, where each production rule of the form A + BC or + a, with A, B,C C V and a E E. Many other normal forms exist, such C2F, which is based the Chomsky normal form but additionally allows so-called unit production rules of the form A + B (Lange and LeiB, 2009). Languages in Chomsky normal form and C2F can not produce the empty word, they lack productions that generate the empty string e (Hopcroft and Ullman, 1979). We therefore introduce C2F+s which additionally allows production rules of the form A +
B DETAILS ON EFFICIENT INTERSECTION LANGUAGE SEARCHES
In this section, we first detail generic optimizations to reduce the size of context-free grammars, then provide a detailed proof of the correctness of our intersection language construction, and finally provide some more details on the search algorithm we employ to decide emptiness.
B.I CONSTRUCTION OF THE INTERSECTION LANGUAGE FOR CFGS IN C2F+s
We now provide the full constructive proof that the intersection of CFL and a regular language is CFL, since it is rarely written out in the literature. We have further adapted it for grammars in C2F+e It forms the basis of Algorithm 2, the core algorithm of our method.
Lemma 1. The intersection language R between context language L and the regular language R is context-free.
Proof. We give a constructive proof by explicitly building CFG that generates L R. We provide the details omitted in the proof given by Gasarch (2014) and extend it to allow grammars C2F+s
Let T.n.. be generated by CFG G EV. S),), and let Ia be accepted by DFA (Q, Σ, 8, qo, F). We first convert G to C2F+e Then, we construct a new CFG Gn whose language is exactly Ln LCFL LR.
The idea to simulate the CFG G and DFA (Q, (,,E,8,q qo, F) in parallel. Specifically, we define the nonterminals of Gn to be of the form "Ā" where A E V is nonterminal of G, and p.d Q are states of the DFA. We then create production rules in such way that if there exists a sequence of productions such that "A" ... - w, then there exists a sequence of productions in G such that A + w and takes the DFA from state p state q. We then add a start symbol Sn and productions Sn - " for all E F to ensure that Ln contains exactly the words that can be derived from the start symbol S of G and that also take the DFA from the start state Zo to an accepting state f F, i.c., all words that are generated by the grammar and all words that are accepted by the DFA.
The productions of Gn are defined follows (adapting (Gasarch, 2014), additional rules in green):
1. For each production A + a, for all p. E Q where 5(p, σ) q. add 'A" +
2. For each production A e, for all p Q, add P T" 7
17

---

Published as a conference paper at ICLR 2026
3. For each production A BC,, and for all p.q.r Q, add "A" - + "B "
4. For each production A B, for all p,q q Q, add AA" "B"
The intuition behind the additional rules that the automaton in some state we can "switch the current symbol" (A B) "produce an empty string" (A + e) without affecting the state. These productions cover the two additional allowed productions in C2F+ grammars, which are not present in CNF grammars.
Finally, add new start symbol S' with productions S + 3 for all f F.
We show that the language generated by the constructed CFG Ln equivalent to the intersection language of the CFL Lert and regular language Ln, i.e., Ln LCFL O Ln- To do so, first need some additional notations:
For any P. g.q E Q and A E V, I.("(") denotes the language generated by the nonterminal A in the constructed CFG, i.e., the set of all words that can be derived with A as the start symbol. Note that Ln = UseF L( (
For any A E V, L(A) denotes the language generated by the nonterminal A in the original CFG, i.e. the set of all words that can be derived with A as the start symbol. Note that LCFI L(S).
For any p.q E Q, L(p+ denotes the language accepted by the DFA with start state p and final state q, i.e., the set of all words that can be accepted by the DFA starting in state p and ending state q. Note that L = User L(9o + f).
We will show that for any p. q E Q and A E
)(AA0) L(A)
This immediately implies that Ln LCA1 L
Ln =- U 5( ( - f)) L(S) U fEF
L(qu f) LCEL O La.
FEF
JEF
prove both inclusions separately.
(C) We show that for any p. E and A E V. L(A") S L(A)nL(p- q). Let the generation path of w L(AA") be defined as the sequence of productions that were used to derive w from "T" Denote
Ln (AA)
(w E [AA") the generation path of w has length at most n).
We show the inclusion by induction over the length of the generation path.
n 1. We show that L (AA") C L(A) n L(p + 4). Since w is a word, the only possible productions that can be used to derive from P 'A" either rule 1 or rule 2. In the first case, we know 5(p,0 a) = q. Hence, w E L(A) and w E L(p q). In the second case, we have E, A + is production of G, and q. Hence, E L(A) and L(p q)- and A V, I_-1(_'")) ("T") L(A) n L(p q). Let w L"A") be a word with generation path length n > 1. Then the first production rule applied to cannot be rules I and 2, these would yield generation path of length one. Hence, the first rule applied must be either the rules 3 and
A + is production of the original CFG G, and
> 1. Suppose that for all p.q
In the former case, know there exist two words W1 In-1( " ) u2 Lo-1('09 such that w = wi W2. By induction, we have wi E L(B) n L(p + r) and wa [(C q). Since A BC is production of G, we have L(A)
18

---

Published as a conference paper at ICLR 2026
well. Furthermore, since wi transitions the DFA from p and wy transitions from 7 to q, we have w E L(p - 9). Hence, w E L(p 1"Bi for some nonterminal B E V such that A + B is production of G. By the induction hypothesis, we have w E L(B) n
In the latter case, we have wo
[pp - q). Since A + B is a production of G, we have w L(A) as well. Hence, w E L( n L(p 9).
(2) We show that T["x")= 2 L(A) n T(p - g). Let the generation path of w now be measured with respect to the original CFG, i... the sequence of productions that were used derive w from A. Denote
(A) = {w E L(A) the generation path of w has length at most nz..
We once again show the inclusion by induction the length of the generation path.
1. We show that for any p.q E Q and A V. TA (A) n Mp 2) S ". Since w is a word, the only possible productions that can be used to derive w from A directly are A + or A E.
In the former case, we have w = and since DFA only consumes symbols one- by-one, there must be corresponding state transition, i.e., 5(p, σ) = q. Hence, w L( A'"A") by rule 1.
In the latter case, w = E, which immediately implies that = y since a DFA does not contain epsilon transitions. Hence, w E L("A") by rule 2.
n 1. Suppose that for all p.q E Q and A E V. In-1(A) Mpp g) S L((A') Let E (A) n Lp q) be word with generation path of length >> 1. Then the first rule applied cannot be A + or A + E, as these would yield a generation path of length one. Hence, the first rule applied must be either some nonterminals B, C' V.
BC or A B for
In the former case, we know there exist two words w1 E Ln), Wy E (C) such that
wi w2 and A + BC is production in the original CFG. Since w E L(p - q), we also know that consuming we transitions the DFA from state p q. We also know that, starting in q. after consuming w1, the DFA will arrive at some intermediate state r. Clearly therefore wi E L(p + r). Moreover, since Wi a W2 and w L(p - q). also W2 E L(r - q). By induction, we then have wi E (B) n L(p - r) C L("B") and similarly w2 E I((O), We know that production P "A" "B" is in the intersection language, due to rule 3 quantifying over all states in Q. Hence, w E L((A" ).
In the latter case, have E In-1(B) and E L(p q). By the induction hypothesis, we have w L("B", Since A + production of the original CFG, we have E L("Ā", well by rule 4.
This completes the proof of the lemma.
B.2 GRAMMAR SIZR OPTIMIZATIIOSS
The size of the grammar used for the intersection generation is of high importance to the overall runtime, the number of productions in the intersection grammar scales cubically with the number of productions in the original grammar. While the size of the intersection grammar also depends on the size of the intersected DFA. generic and efficient methods minimize DFAs exist. Meanwhile minimization of CFGs is undecidable (Hopcroft and Ullman, 1979).
We therefore apply several heuristics to reduce the grammar size:
Inlinable terminal elimination: Inline the productions of nonterminals that are only used in single production. In particular, when B is only used in single production A - aB, with B + 7, remove B and its production and inline it into the production of A to create A - 073.
19

---

Published as a conference paper at ICLR 2026
Shared 2-gram elimination: For the most frequent BC' such that there several rules of the form A + a BCB, (with a, non-empty) introduce A' - BC and rewrite A + a 3. Repeat until no more such BC' with more than occurrence can be found.
Left factoring: We eliminate shared prefixes using left factoring (Alfred et al., 2007). Specificallyy, if two productions of the same nonterminal A - aB and A a, share the prefix a, we can introduce a new symbol A' and replace the productions to eliminate the duplication, concretely introducing A a''' and A' 8, A' 3".
After applying these heuristics, convert the resulting CFG to uuin standard algorithm, consisting of several transformation steps, such as terminal elimination and binarization (Lange and LeiB, 2009). In between each step, detect and eliminate potentially constructed non-generating symbols.
B.3 DETAILS ON THE SEARCH ALGORITHM
We explain in detail how the search algorithm for generating nonterminals in the intersection lan- guage works. The corresponding pscudo-code is presented in Algorithm 2 and based on the algo- rithm presented by D.W. (2018). We leverage the construction rules of the intersection language to conduct the search on the implicit intersection grammar, i.e., we only build the parts of the grammar that we need to explore. Nonterminals in the intersection language have the form P " for p. 9 E E and A E V. All production rules of the form "Ø" & and "A"" a are based on the corresponding productions A - (Construction I) and A + e (Construction 2) in the original grammar. We leverage this insight to perform the initialization of the search, which iterates over all production rules of this format, the beginning of the algorithm in Lines 2-5. Further, all other productions are of the form "A" " " and "A"_ "B" as constructed by Constructions 3 and Importantly, exist. This allows us to enumerate all such rules for
all rules for all combinations of states given symbol B or on the fly, as done Lines 9-17, without expending unnecessary execution time. For example, in Line 9, we iterate over all production rules in which the nonterminal "X" occurs. The two states of the DFAs already fixate tion 3. Hence, given a production A - XC in the original grammar, which uses the nonterminal X and additional nonterminal C, we need iterate over a single additional state variable q to evaluate all corresponding constructed productions "A "X 23 0
of the three states quantified over in Construc-
C LEXING WITH LLM TOKENS
The approach described in $3.2 operates directly on the formal language alphabet Σ. LLMs produce Unicode text that can be misaligned with Σ. In this section, we describe in more detail how to handle the resulting discrepancies.
C.I LEXEMES AND LLM TOKENS
Discrepancies between alphabet and LLM tokens For practical purposes, the alphabet E of the formal language usually consists of lexemes. These represent language components abstractly, i.e., for programming languages, they could be identifiers, literals, operators, and other syntactic elements of the language, such as if and else. Before parsing a Unicode string, it thus first needs be converted into string of lexemes. This process is called lexing.
The code generation paradigms MRI and DLM generate code on Unicode level and thus require lex- ing before our method can be applied. In addition the normal lexing process, our approach needs to handle the partial nature of the LLM outputs, taking into account potential partial lexemes and consequently several possible lexing sequences for the same character-level output. In the remainder of this section, we first explain how to convert the partial LLM output to set of possible lexeme sequences, and then how apply the constrained infilling algorithm to these lexeme sequences.
Lexemes and lexing Each lexeme is associated with a regular language R where Σn is the set of Unicode characters. For example, the <number> lexeme is associated with regular expression \d+,
20

---

Published as a conference paper at ICLR 2026
and the <identifier> lexeme with [a-zA, 1.A---IWw lw.. Lexing is the process of converting Unicode- level string into a sequence of lexemes, i... a sequence of strings that match the regular expressions of the lexemes. We call such sequence of lexemes lexeme sequence. The lexing algorithm extracts these sequences by iteratively matching the maximum match for all lexemes that match a nonempty string at the beginning of the currently remaining output. Whitespace between lexemes is commonly stripped. For example, the character-level string "1234 hello12" would be lexed into the lexeme sequence (<number>, <<number>,<identii i ffirs).
C.2 CONVERTING PARTIAL OUTPUTS TO LEXEMES AND DFAS
Lexing partial outputs For a partial output with infilling regions, we extract the represented lexeme sequences for each chunk of continuous text. For instance, the output "x 1234mhello12" would be split into the chunks "x= 1234" and "hellol2", which would be lexed into the two lex- eme sequences (<identifiers, <=>, <number>) and (cidentifiers) Note that the resulting list of lexeme sequences is list of words in D that can be directly used to construct the regular lan- guage for the infilling problem as described in $3.2, for example here forming the infilling problem <identi
Handling lexemes spanning infilling regions However, infilling regions complicate the lexing process. Concretely, we need to handle strings that match lexemes partially on the border of infilling regions.
Concretely, strings before an infilling region may end with string that matches prefix of some lexeme. For example the output "C123" could be lexed as (<number>). However, the region could be filled with token "a", resulting in the overall lexing (<identifier>). Similarly, strings may match suffixes of lexemes after infilling regions.
Additionally, lexemes may span over an entire infilling region. For example, for the output "123 a trivial possible lexing is (<number>, <number>). However, it is also possible to insert token "456" into the region, such that the lexing of the final character-level text is just a single lexeme sequence (<number>). This also holds for any number of infilled gaps, e.g,, 71777475767779".. In particular, for any chunk aB ending with prefix 3 of lexeme <a>, consecutive chunks "/ that are prefix of a suffix of <a> and a final chunk nę starting with a suf- fix 7 of <a>, then valid corresponding lexeme sequence for the entire chunk sequence could be (lex(a), <a>,
We also need to ensure the prefixes and suffixes of the lexeme are compatible. For instance, for fixed- width lexemes such as <whiles wwhile>, we can not insert a token into the sequence "whi Muhiluhile" to obtain a sequence with only a single lexeme, even though both "whil" and "hile" are true prefixes and suffixes of the lexeme while. We resolve this by determining the intersection of the concrete partially generated output with the lexeme's regular language. Concretely, we construct partial character- level output C D' [ and compute the intersection with the regular language of <a> using standard algorithms for the intersection and emptiness of regular languages (Hopcroft and Ullman, 1979). If the language is not empty, (<a>) is valid lexing of the entire sequence. This effectively generalizes a similar solution to the one proposed by Melcer et al. (2024), in which they explicitly store the reached states within each prefix and suffix and ensure their reachability.
Lexing algorithm We use some helper operations on character-level DFAS for the lexing algo- rithm. For DFA D, we define the function MATCH, which returns 1, the number of characters in the string that the suffix language automaton matches maximally. For example, Adt.MATCH(1233 and MATCH lhello)
1. The function PREFIX( D)) returns the true prefix language of D, where a true prefix is prefix that can be completed to full match by appending at least one more character. For example. 123 is true prefix for \d+ but not for \d\. 12 is a true prefix for both regular expressions. The function SUFFIX( D) analogously returns the true suffix language of D. Further, we denote We: the string formed by the first i characters of w and w>i the string formed by all characters after the first i characters in w.
The lexing algorithm applied to each chunk of continuous text in x is deseribed in Algorithm 3. The main mode of operation is to keep track in S of possible lexings and remainders to be processed, starting with the empty lexing and the entire string be processed in Line 1. The method then
21

---

Published as a conference paper at ICLR 2026
Algorithm Deciding intersection emptiness of a CFG and DFA. The CFG CNE. G.ADD(a) inserts into G and returns true if x was not in G previously.
Input: CFG C, DFA (Q, E, go:
Output: L(C) = Ø
G
for all productions A + σ do 8(p | g) 4 for all productions A + 8 do
> Mark terminal and epsilon productions.
G GUGU GU
G GUG
Q}
6 s s G.CoY()
while + Ø do
Explore all remaining productions
"X" f- s.POP() for all productions A + XC, all E Q do if C'' G and G.ADD A²") then S.ADD( for all productions A + BX, all E Q do
11
"B" E G and G.ADD 9 4=
13
then
S.ADD AA for productions + X do
14
15
if G.ADD "A" then
16
S.ADD )
return Gn S
F) Ø
Whether any start symbol of I(CC) n I(R) is generating
Algorithm Extracting lexings of chunk within partial output.
Input:
Input string w, Terminals
Output: Set {(ra, 8t, posinninn of n possible lexeme sequences and optional partial matches to the first (8,) or last (p:) lexeme
S + {(E, None, None)]
2
for E T do
Determine if the string starts with suffix of any terminal if' SUUFFI(PREFII(()) MATCHI(() |w] then If the suffix prefix spans the entire word. S.ADD(L, e, w, w) 1 SUFFUX(I)
6
ifl then
b If the suffix matches non-zero prefix of w
S.ADD(t, wst: Wgi, None)
8
while S + Ø do
(Ir, uI, s.p) S.POP()
10
w = then yield (z, s,p)
for do
if PREFIX(I).MMTCHH))) S.ADD o t, s, w) + (.MATCH((W)
|w| then
b If the prefix spans the entire remaining word.
14
if then
If the suffix matches non-zero prefix of w
SAADD o WSl, 8, None)
22

---

Published as a conference paper at ICLR 2026
Algorithm Extracting lexings of an output with infilling regions.
Input: Input string w1 Winwen.... mwy, Terminals T
Output: A list of partial lexeme sequences that match the input string.
P Step Collect all possible lexings of partial outputs
1 L f- (
for in to do SOODD(LEXPPARTAALCCC PARTIAL(W; T)) L.ADD(LEX_
3
D. Apply Algorithm 3
b Step 2: Determine all possible subsequences of lexings
4 C' +- CROSS C (
5 for [(x,, 8t, p:)] C do
P Step 2.1: Determine all possible merges subsequences
6
if not Po = 8n = None continue
Reject unmatched front or back.
M < 0
8
for i in to n do
> Check for mergeable subsequences.
if s; = None continue
10
for in i + 1 to n do P; None break
11
Are the same lexemes matching partially?.
if -11 fr; (0) break
13
if = wy and = W)
>> Case distinction for all scenarios.
0 -- 08; ... Dp3
else if pj = W and +
16
0 o 8;0w;+1 D .... Op,0
else if pj A Wy and w;
18
ot 11; Up
else ot s npj
20
if (-11 no
If lexeme match the partial output we can merge from to j- > No further merges possible with s;.
22
M.ADD(i,j)
p # wy break
Step 2.2: Determine all possible combinations of merges
24
N + -[I
merge is possible sequence
for (i.j) in M do N.ADD(((i.)) (I)
26
for (C
..... (K Hbl in N do
28
[.. n (F M U... (() = Ø0
b Non-overlapping merges.
29
N.D ((C((.
(2..%) (i,1)))
30
for (i,,1), (k in N do
yield ... a DT,, 2 DT +10 ... 1ei - Di 1 D +1 ... D
23

---

Published as a conference paper at ICLR 2026
D2
int
D1
E
D2
D2
int
Dg
D
41
Q3
D2J
D2
identifier
Figure 5: A union automaton in the second half of the DFA for output "123 789", accounts for the possibility to lex the second half as either <int> or <identifiers, The resulting automaton accepts both valid lexeme sequences <int><int> and <int><identifierr.
iterates over all these lexings in Line 8, returns them if the remainder is empty (Line 10) extends them a non-empty remainder remains (Line 11). Crucially, Lines 2-7 check whether the text starts with the suffix of any lexeme. Additionally, Line 12 checks whether the remainder of the current text is the prefix to some lexeme.
Applying the constrained infilling algorithm Algorithm 4 describes how apply the lexing algorithm to partial output with infilling regions. First, we apply the lexing algorithm to each continuous chunk of text Algorithm 4. resulting list of sets of possible lexeme sequences for each chunk. Next, we take the cross product of these sets to obtain all possible combinations of lexeme sequences for the entire output. Each combination consists of a list of lexeme sequences, along with potential partial matches to the first and last lexemes in each chunk. Further steps in the algorithm enable the merging of lexemes that span infilling regions. We first find all possible indices (i,j) for which such merges are possible by checking the compatibility of the partial matches and the regular language of the lexeme, as described previously. We then construct all possible combinations of overlappapi merges and yield the resulting lexeme-level partial outputs.
Determining non-emptiness The prior algorithm returns a set of possible lexeme-level partial out- puts for the given character-level partial output. If any of the resulting sequences results in inter- section language Ln, then the current character-level partial output is valid, and we can continue generation. If no lexeme sequence results non-empty intersection, then we need to reject the current output. Thus, we have to apply the infilling algorithm to each of the word lists derived from the lexing process. In practice, we may derive a large number of lexeme sequences, as different possibilities from text chunks get combined and result in combinatorial explosion. To further op- timize the lexing process, we add two additional optimizations, which we describe in the following paragraphs.
Optimizing subset lexemes We avoid combinatorial explosion of possible lcxeme sequences by automatically removing lexemes where the accepted language is subset of the accepted language of another lexeme. For example, in SMILES, the string "5" could be interpreted as <digit> or <fifteen>, which is special lexeme only allowing numbers from automatically detecting lexemes a that accept subset of valid strings of another lexeme B, and a) remove the subset from the accepted language of lexeme and b) allow the lexeme a any position in the grammar where either the subset token or the full token is allowed, in particular we substitute terminal 3 with a 3. This optimization reduces the number of extracted sets of possible lexeme sequences for each continuous chunk of text.
15. We resolve this by
We further manually reduce the number of lexemes that overlap and lexemes that are prefixes or suffixes of other lexemes, such as <++> and <t>, to further optimize performance.
Combining lexeme sequences to a single NFA To avoid explicitly enumerating all possible com- binations of lexeme sequences of string, directly derive single, larger NEA that accepts all possible combinations of lexeme sequences at the same time. This NEA is structurally similar to the NFAs of each lexeme sequence, but adds alternative paths for mergeable lexemes.
24

---

Published as a conference paper at ICLR 2026
Dj
X
D2
int
4o
Dg
D
41
Dg
D
43
Figure 6: skip connection, highlighted in blue, in the DFA for output "123 E 789", accounts for the possibility to lex the input as single <int>. The resulting automaton accepts both valid lexeme sequences for single int and ints with intermediate tokens. This construction can be combined with Figure 5.
If text chunk has two more admissible lexings, we replace the constructed D; with NFA that accepts the union of admissible lexings. For example, the output "123m789" must also admit recognizing the second chunk the suffix of an identifier. Thus, we obtain the two sequence sets [(<int>)) and ((<int>), (<identifier>)). By generating single NFA that accepts both sequences (<int>) and (<identifier>), we can construct a single NEA by applying the concatenation con- struction to the standard NFA for the first lexeme sequence and the unionized NEA for the second sequence. The resulting NEA is presented in Figure 5.
Another example is depicted in Figure 6. Here, for the previously shown output "123 "19","89", the first chunk ends with a prefix of the lexeme <int>, and the second chunk starts with a suffix of same lexeme. In addition to the standard construction for the possible extracted list (<int>, <int>), we add an <int>-edge from the second-to-lase state of Do to the second state of D1. resulting in an alternative path that accepts the list (<int>). These paths constructed by maintaining a list of suffixes of the previous D; when constructing D;-1, and adding the edge a suffix matches prefix of the lexing of D
In contrast to the combinatorial explosion observed when considering all possible combinations of consecutive parsed lexeme sequences, this NFA grows only linearly in the number of sequences. We also observe that the generated corresponding DFA has a similar number of states, confirming that this avoids expensive combination enumeration.
C.3 SOUNDNESS AND COMPLETENESS OF LEXING APPROACH
In this section, we show soundness and completeness our lexing approach under reasonable as- sumptions. Throughout, lex denotes the lexing function that maps Unicode string to lexeme sequence. Each terminal f has a regular language R2 S Σ" over the Unicode alphabet Σ. For lexeme x, will denote R(z) for sequence of lexemes T22 Fn, we denote the regular language described by the sequence as R(x1) ) R(x2) ... R(xx), where denotes concatenation of languages. We denote substrings of WyWs+11- ... We of Unicode strings = Wi Wn, k S with Wysk, where each wy a single unicode character. Finally, we say that lexeme z; consumes substring wysk is the part of x that exactly matches the characters Wjsk.
the regular language of the terminal associated with Further,
R(x122 ... ..,,)
We make two standard assumptions about the lexer.
Assumption (Maximum Munch), The lexer matches lexemes by greedily matching the longest possible lexeme at each position. Concretely, let w W2 Wn be Unicode string, where each w; single character, and suppose lex (e((w)) = x 32 ... Tmn Then:
1. There exist indices kg. ki....,
........ km with ky < hy <... km such that for all 1 < sis S m, the substring Wh.-+t:sk, E R(x,).
2. For each k, there is no l k; and terminal such that the substring Wh.-++15 1skk R..
Intuitively, Assumption states that the lexer is greedy: at each position it chooses the terminal that extends the match as far as possible before emitting lexeme and moving on.
Assumption (Orthogonal Terminals). Let t and to be two terminals with regular languages R and R2, and # lz. Then suffix of any string in RA a prefix of any string in R2.
25

---

Published as a conference paper at ICLR 2026
This assumption be enforced for any given CFG and set of terminals by preprocessing the terminals: whenever two terminals share a prefix or suffix in this way, we factor out the intersection into a new terminal and adjust the grammar accordingly. These assumptions together imply a useful property:
Corrolary (Unique Lexing). Let w Unicode string, and I1... Zm be a lexeme sequence such that E R[ ... Em). Suppose further that, whenever Waj is consumed by 24. in the sequence, there is no > j such that waa E R(xx). Then, lex(w) = 21...
Proof. Let lex(w) = -1....y- We show that æι and y1 are equal and consume the same number of characters from w. Recursively applying this argument then shows that and Iz for all isis m.
Let 21 consume wirk, and y/1 consume Wiik-- Suppose, for the sake of contradiction, that either 11 A h2 or æı + y1- However, either w wi:k, is a prefix wikk or vice versa. By Assumption 2, this implies that 21 y1- Now, because of Assumption 1 and the assumptions in the corollary, k h2 must hold as well.
We now characterize the outputs of Algorithm 3 and Algorithm 4 under these assumptions. We denote the first and last lexeme in a lexeme sequence r with x(1) and x(-1), respectively.
forwhich there Lemma 2. Given Unicode string Algorithm 3 returns exactly all tuples (z, p) for which exist strings and v such that u o w v E R(x) and
If Wy..... W consumed by Tk. then there is no 1 >> such that wi... wi E R(xx))
2. If p w, then [x] and (0) x(-1) consumes w
3. If = None, then u 8. Otherwise, unless & = w. x consumes u a
4. p None, then e Otherwise, unless s p x11)) consumes
Proof. We prove both directions: (1) every tuple produced by the algorithm satisfies the stated conditions, and (2) every tuple satisfying the conditions is eventually produced by the algorithm.
No other tuples We show that any element (x, 8,P) S (as maintained in Algorithm 3) satisfies the following:
w can be written as w' = Waijll for some 1 S S |w|| + 1, where we set W|/|++
There exist u and u such that u w1:-11 u E R(x) and if * |mo| + 1, then e =
Condition 2, Condition 3, and Condition 4 hold with respect to W1;--1, u and v. Further, Condition holds with respect to w.
Since the algorithm yields tuples only when w' = (Line 10), it follows that all produced tuples satisfy the lemma's conditions.
The initial elements inserted in Line and Line satisfy these properties trivially. Likewise, the element inserted in Line 7 satisfies the conditions: by the check in Line 6, some non-empty prefix of w is a suffix some a E R, Choosing u such that u wer = a and setting e = E, one can check directly that all required conditions hold.
Assume inductively that all elements already in S satisfy the conditions. We show that any new element added the loop Lines 8-16 also satisfies the conditions. When Line pops (xr, w s, from S, we know by the induction hypothesis that there exist u and u such that u 11::w//-uw OUE R(x). The check in Line 10 ensures w' * E, hence e and not both
w.
If Line 12 holds, then w' is prefix of some R2. In Line 13 add (xr w.), Let a w o U. then u Loooue E R(zot), All required conditions now hold:
By construction, nowore E o(xot).
26

---

Published as a conference paper at ICLR 2026
|w| + since w/
Since r satisfies Condition so does
Condition does not apply.
Condition holds by the inductive hypothesis.
Condition holds since consumes w'
Next, consider the element added in Line 16. By Line 14, wegi is the largest prefix of w' that matches
f. Therefore, the element (Ir o t, uS 8, None) added in Line 16 satisfies all conditions:
By construction, u w1:|w||ww" o w'sl R(x
We may take j such that w/y = "//[]--
Since r satisfies Condition 1, so does x
Condition does not apply.
Condition holds by the inductive hypothesis.
Condition holds since p None and
Thus, all added elements satisfy the conditions, completing this direction of the proof.
All tuples Now let (ar, 8, p) satisfy the lemma's conditions. If p w, then ler + and (0))) xx11) consumes
v. Thus, w lies in the prefix language of the suffix language of x, and Line inserts E,, w, w) into S. It is therefore yielded in Line 10.
Further, 8 # e, then by Condition 3, x(1) consumes u 8. Hence when 1. x1)) in Line 2, Line inserts (z()), W>|s| 8, None) into
Inductively, suppose (z()) (())) w', None) has been added to S, where w' is the remain- ing suffix after consuming the prefix handled by x(1) .i-1( and S < [w]. When / = x(0)
in Line 11, the value of is precisely the length of the prefix of w' consumed by x(1), Therefore Line 14 adds (2) x((), u'',, 8, None) as required.
Now, if p None, similar argument shows that (æ,e, s, None) is added to S, knowing that (z()) ... (-2), w', s, None) was added previously, since z(-1) fully consumes the remaining suffix w/ by the conditions.
Finally, we know that (2) (-2)) ,, s, None) gets added to S, since the lexemes 2(11,, ,((),..., ....,
x122) .((2)) consume of w except p. Because p lies in the prefix language of x(1,), con- dition Line 12 holds when t= x(11) Thus, Line 12 inserts (z, s, into S.
This element is eventually popped and yielded in Line 10, completing the proof.
Lemma 3, Given a Unicode string with holes win... mW,, Algoritium returns exactly all lexeme sequences I' Zinagn ... n such that the following conditions hold: For any lexeme sequences yn, 12....... 1m there exists a w/ E R(w .... oww) n R(x1y1 F22222 ... 1m))3m) such that lex(w) Ft 322/2 1o and each full string w; is consumed by single lexeme sequence I; for some < E m.
Proof. We first show that any lexeme sequence returned by the algorithm satisfies the condition.
No other sequences First, let I E E&m be any lexeme sequence returned by the algo- rithm. By construction, for each chunk ws there exists a tuple (æ,, $s, p:) returned by Algorithm such that x is the lexeme sequence for chunk Wi. By Lemma 2, there exist strings u; and v; such that u,w;e; E R(x()- Because of the yield (Line 31), we know that 2; is either equal to of for some j. or is formed by merging a' and s'g for some j < k, where the latter can only
27

---

Published as a conference paper at ICLR 2026
happen if the intersection as given in Lines 13-20 is non-empty. Looking closely at this inter- section, can be easily determined that it implies the existence of strings 8J.... Sg-1 such that R(z;). We set w/ u for chunks that were not merged (1 U and to w = (yJ0yy)(y+1851
88-- - for merged chunks. Line 6 implies that 11 = Un = e, implying that the concatenation w/ DR'S ... DWn E R(wn .... -..)) Further, we find that, since w is exactly consumed by 24, " " n ((a111 ... Vm- 1 (Im) # Ø for any choice of lexeme sequences yl, 32........ .... 9m-11 Now, Corrolary 1 and Assumption 2 shows that ym-1Fmm for any E R(w) D Jwnn n ((
fm mm) Here, Assumption is necessary to ensure that when we fill the i-th hole with an element from R(y)), we do not change the lexing of the surrounding lexemes sequences v; and 11+1-
lex(w) 11
All sequences Now, let 21 3.20 mm be any lexeme sequence that satisfies the condition. We show that the algorithm will eventually return 210r20 D2m- Once again, we first define w/ as w..... mwy if z; is the lexeme sequence that consumes chunks wy, W/+1....: Wk. Now, the char- acterization presented Lemma 2 and the simple observation that Algorithm 4 uses cross-product (Line 5) and returns lexeme sequences of all possible mergings (Lines 24-31) directly implies that I1 M..g..... 7Zm will eventually be returned by the algorithm.
This characterization allows us to prove soundness and completeness of our lexing approach. Both of these proofs are one-liners that directly follow from Lemma 3. Importantly, completeness implics that if a proposed token by an LLM leads to updated output that can be lexed to valid lexeme sequence, we will accept the token. Further, soundness implies that we accept a proposed token by the LLM, there exists completion of the current output that can be lexed to valid lexeme sequence.
Theorem 4 (Soundness). Given a partial Unicode string w = w wwwWw...... Own with infilling regions, if Algorithm 4 returns lexeme sequence that can be completed to valid word in the language, then there exists a completion w' of w such that lex(w") is a valid word in the language.
Theorem (Completeness). Given a partial Unicode string w with infilling regions, if there exists completion w' of w such that lex( w') is valid word in the language, then Algorithm 4 will return a lexeme sequence that can be completed to valid word in the language.
D EXPERIMENTAL DETAILS, ABLATIONS AND CASE STUDY
In this section, provide additional details about the implementation, hyperparameters, datasets, runtime overhead, an ablation on the number of diffusion steps, and a case study.
D.1 IMPLEMENTATION
Overview Our implementation is written in around 7000 lines of Python and 5500 lines Rust. The main logic, concerning LLM sampling and CFG and DFA construction, is written in Python, with the more computationally expensive formal language operations, such as Algorithms 2 and 3, implemented in Rust, compiled as Python bindings. Several low-level formal language operation implementations are inspired by the educational Python implementations by Romero (2021).
Grammars Our C++ grammar covers a comprehensive but not complete subset of C++, with all features used in the canonical solutions of the test set implemented, but advanced features like template functions and user-defined classes are not supported. Moreover, we disallow the insertion of multi-line comments inside function bodies, as this allows the model generate arbitrary and broken code that is syntactically valid as long as it is finally wrapped in the multi-line comment de- limiters. We further restrict models in the MRI setting to not generate additional function signatures and bodies to prevent the generation of additional main functions test cases.
We preprocess all model outputs by marking word boundaries with special ( (add) ) tokens that do not appear in the original text and are never generated by the model!. For example, the string int main() is converted to (int) (main)(). This enables us to check for such word boundaries inside
In particular, we the bytes \x62 and \x03
28

---

Published as a conference paper at ICLR 2026
the grammar, i.e., being able to distinguish whether white-space was present between symbols after it is stripped in the lexing process.
The JSON schema grammars are obtained dynamically based the JSON Schema for each task. We recursively build up the grammar based on the provided specification. For SMILES, we implement the specification described by Apodaca (2020), which is more precise and efficient variant of prior specifications (Weininger, 1988; Blue Obelisk Project and OpenSMILES Community, 2025).
Grammar Prompting For the grammar prompting ablation, append the grammar in hu- man readable formatting into the prompt, i.e., without normalization and using descriptive symbol names. For ISON, the ad-hoe generated terminal names replaced by string representation of the respective regular expression, symbol names are S1 to Sn. An example for SMILES is shown in Figure 18
D.2 MODELS AND HYPERPARAMETERS
All methods were four times, with seeds 0 to 4, and we report the averaged results in all tables. We report the maximum among Van., Con. and Con. decoding with boldface. We underline all results where the confidence interval of the improvement over the given method is not positive at 95%. We limit the amount of generated tokens to 256 and time out if the generation does not complete after 300 seconds. We run model inference on NVIDIA RTX A6000 GPUs.
Sampling algorithms and temperature All MRI models were sampled with temperature I and greedy decoding. The diffusion models are sampled with a temperature of 0.2. To pick a token from the diffusion models distribution, we use the entropy algorithm for the DREAM 7B based models, DREAM 7B, DREAMCODER 7B, and DIFFUCODER 7B, and low confidence for the LLADA 8B model, recommended by the model developers.
Diffusion steps Diffusion language models can be run with a varying number of diffusion steps, determining how many tokens are sampled from single model inference (Ye et al., 2025; Nie et al., 2025). Lower numbers of steps imply more tokens being sampled from each inferred distribution, which in turn is updated less frequently. One of the key benefits of diffusion language models is to exploit this ability, resulting in overall faster decoding. At the same time, higher numbers of steps are usually associated with increased accuracy on the requested task, as the model can adapt its distribution more frequently to newly inserted tokens. When not explicitly stated otherwise, the diffusion models are with 32 diffusion steps. Our choice of step size 32 represents trade-off between speed and accuracy.
In each diffusion step, model inference is run once on the current state of the partially filled con- text window. Afterwards, tokens are sampled from the distribution according to the respective algorithmss (Low confidence or entropy) and replace mask tokens in the context window. While unconstrained decoding allows sampling all l tokens in parallel, during constrained decoding, we iteratively sample single token-index pairs from this distribution, with rejections leading masking out the rejected token-index pair and resampling. When a token is accepted, we remove the token's s index from the distribution. After tokens have been accepted, we run model inference again.
D.3 DATASETS
C++ We leverage the C++ translation of HumanEval in the HumanEval-X dataset (Zheng et al., 2023). It contains 164 instances of simple programming problems and canonical solutions written by humans. For the MRI tasks, we remove hetween and 3 randomly sized spans of 5 to 100 characters from these canonical solutions, generating one MRI task per instance in the original dataset. If we end up with insufficient remaining characters after removing the required number spans, we resample sizes and positions up to 3 times, aborting if we do not find valid removal. Additionally, we remove 5 human-written solutions that are not valid according to our implementation of the syntax, i.e., because they contain multi-line comments in three MRI datasets of 159, 156, and 143 samples in 1-MRI, 2-MRI and 3-MRI respectively. An example prompt for instance from the dataset is presented in Figure 9. For DLM, all 164
additional helper functions. This results
29

---

Published as a conference paper at ICLR 2026
3.5
DREAM CODER 7B
3.0
DREAM 7B
LLADA 8B
Runtinc Overhead
DIPFUCODER 7B
1.0
0.5
0.0
10
20
300
50
60
80
Grammar size (# productions))
Figure 7: The median runtime overhead of Con. grouped by size of the grammars JSON, with 2-degree polynomial fitted against the individual points. A clear increase be seen, although ranges only between and seconds.
tasks of the original dataset and extract the comment before the function as an instruction for the model. example prompt is shown in Figure
We check the functional correctness in both settings by checking whether all test cases in the dataset pass with the model-generater solution.
JSON Schema We extend the JSON-Schema dataset by NousResearch (2024). Concretely, the dataset originally contains unique schema per task. We clean the schemas by disallowing properties other than specified on the top level and repairing instances that accidentally do not require any fields. We then extend the dataset by sampling GEMINI-2.5 for 10 inputs and completions for each schema. We filter these samples in three ways to ensure high quality.
First, we filter the resulting extracted outputs for syntactic validity according the schema and discard invalid generations. Second, we require GEMINI-2. to be able to solve the task, i.c., the model must generate valid JSON object that passes the schema validation if only given the input and the schema. Third, we perform fuzzy matching to deduplicate the resulting samples. This process results 272 instances. The prompts used for generation and verification are shown in Figure 13 and Figure 14. An example prompt for this task is shown in Figure 11.
We evaluate functional correctness on this dataset by checking for exact equality between a normal- ized ISON dump of the golden solution and the model-generated solution.
SMILES To create benchmark for SMILES, we query GEMINI-2.5-PP to generate pairs of descriptions of molecules and their SMILES notation. Again, we perform three filtering steps to ensure high quality. First, we verify that the generated molecule valid using the Rdkit library (Landrum et al., 2025). Second, we ensure the model can generate the correct SMILES string for the molecule if is only given the description. Third, we filter out duplicates using fuzzy matching. This results in 167 pairs of descriptions and SMILES strings, Prompts for this generation procedure are shown Figure and Figure 16. An example prompt for this task is shown in Figure 12.
To check the functional correctness of the model-generatee molecule, we parse it using Rdkit and check the equivalence to the molecule generated by GEMINI-2.5- PRo in canonical representation.
D.4 ADDITIONAL EXPERIMENTS
Runtime overhead For all experiments in $4, measure the runtime of our constraining method and unconstrained decoding. We present detailed comparison Tables and We further measure the average number of rejections per sample.
In MRI we compare time per token, as constrained decoding often rejects finalizing the current output, thus making completions longer and finalization times incomparable. The median runtime
30

---

Published as a conference paper at ICLR 2026
Table 3: Median overhead per token for different infilling settings in milliseconds and percent in- crease over unconstrained generation. Larger models with higher inference time experience lower slowdown due to constraining. More infilling regions also increase constraining overhead.
#Regions
1 1-MRI
2-MRI
3-MRI
CODEGEMMA 7B
3. 3.14a0 147%
4. 163%
6.4-999
STARCODER2 7B 3.3 3.3
5.5
9.7 9.7-190%
DEEPSEEK C. 1.3B
3.6
5.8
1 11.8-557%
DEEPSEEK C. 6.7B
3.0 155%%
4.6 4.6490%
7.7 7.7-153%
DEEPSEEK C. 33B
3. 413%
4.3
6.5-28%
Table 4: Median time difference per completion for different diffusion models in seconds, and the overhead over the original completion percent. When the completion aborts pre-emptively, as no valid completion is sampled from the model, speed-ups are possible.
Model
C++
JSON
SMILES
DREAM 7B
1.1
0.4,20%
0.0
DREAMC. 7B
7.8+190%
0. 13%
0.0
LLADA 8B
-1.0
0.5
0.0+1%
DIFFUC. 7B
2.2,74%
0. 1.16
0.0p2%
overhead of constrained decoding is 125%. where the overhead on the small DEEPSEEK CODER 1.3B is higher (320%) than on the 7B model (100%) and DEEPSEEK CODER 33B (20%). This both due to the lower inference time of smaller models, and due smaller models making more mistakes, with the average number of rejections increasing from 8.8 per instance on 33B, over 9.7 for 7B to 10.5 in 1.3B. Moreover, more infilling regions are more difficult, leading to more rejections, growing from 4.7 on 1-MRI to 14.1 in 3-MRI. This increases the overhead from 67% to 205% respectively.
For DLM, compare the total runtime to finish the diffusion decoding process. The average com- pletion overhead is only 30,, but varies strongly between domains. We observe both speed-ups of up to 19%, for LLADA 8B C++, where many decodings preemptively aborted, and slow- downs of up to 190%, for DREAMCODER 7B on the same dataset.
We further analyze the runtime overhead based grammar size and infilling regions. We first analyze the runtime overhead per size of the normalized grammar, as the normalized grammar is the basis for our intersection algorithm. The normalized grammar sizes of C++ and SMILES 167 productions and 46 productions respectively. As shown in Table 4, this corresponds to a median runtime overhead of 2.5 and 0.0 respectively, indicating a strong correlation the grammar size. For closer analysis, we plot the median runtime overhead for each of the JSON tasks in Figure 7, where each task has an individual grammar, and regress a 2-degree polynomial against the data. An increase in runtime, according to the asymptotic complexity described in $3.2 is visible, but the constant appears very small. For an analysis of the impact of infilling regions, we refer to our results of runtime overhead for increasing number of infilling regions in MRI Table 3, where more infilling regions increase runtime from 3.2 to 8.4s.
Ablation on diffusion steps We evaluate our method on common diffusion step numbers, from 256 16 to 256, where the lowest setting 16 implies that single inference step inserts 16 8 tokens at once, while the highest setting 256 implics that every inference step inserts only a single token.
We present the results of this ablation on DREAM 7B in Table 5 and demonstrate that our method consistently improves syntactic correctness in all settings by on average 14%. Functional correct- ness JSON also significantly increases by 1.2%. while the increase in C++ is 0.7% and 0.5% in SMILES. Moreover, the runtime overhead, shown in Table 6, decreases with the number of diffusion steps, from 14% 108% down to 9% even a speed up of 3%.
31

---

Published as a conference paper at ICLR 2026
Table Percent syntactically and functionally correct generations for DREAM 7B based on varying number of diffusion steps. Our method consistently increases syntactic correctness in all settings, even when model accuracy increases with step sizes.
C++
JSON
SMILES
#Steps
Van.
Con.
Con.
Van.
Con.
Con.
Van.
Con.
Con.
16
8.1
20.3
99.2
7.3
24.4
100.0
41.1
80.5
99.7
Syntax
32
40.5
58.7
99.4
22.4
44.9
100.0
67.5
93.7
99.4
64
60.1
74.7
99.8
67.4
73.2
100.0
79.2
94.9
100.0
128
81.1
90.7
100.0
90.2
94.0
100.0
80.1
95.8
100.0
256
98.2
98.2
100.0
95.2
98.2
100.0
80.7
93.4
100.0
16
1.4
2.7
1.5
2.3
3.4
1.1
Functional
32
6.6
8.8
9.5
7.4
11.4
14.3
0.6
1.1
1.1
64
21.0
21.8
22.4
41.8
42.1
42.8
2.4
3.0
3.0
128
24.5
23.9
24.1
50.7
51.5
51.5
3.1
4.0
4.0
256
34.1
34.1
34.8
54.8
54.8
54.8
4.9
5.2
5.2
Table 6: Time difference per completion for different step sizes on DREAM 7B diffusion, in seconds, and the percentual overhead over the original completion. For larger numbers of diffusion steps, overhead reduces from 14%
108% down to 9% or even a speedup of 1%.
#Steps
C++
JSON
SMILES
16
1.7 1107%
2. 2.1
0.0
1.1 136%
0.4
0.0
64
0.6
0. 0.1
-0.2
128
0.4110%
0.2
-0.413%
256
0.8
-0.1 111%1%
0.2
32

---

Published as a conference paper at ICLR 2026
Table When infilling between I and 3 missing lines, our method consistently improves syntactic and functional correctness. Shown below the results of MRI-L under standard decoding (Van.), constrained decoding (Con. )) and completing partially completed outputs (Con.).
I I-MRI-L
2-MRI-L
3 3-MRI-L
Model
Van.
Con.
Con.
Van.
Con.
Con.
Van.
Con.
Con.
STARCODER2 7B
84.0
95.4
98.3
78.5
91.3
96.5
63.5
86.8
95.7
Syntax
CODEGEMMA 7B
94.8
95.7
98.8
83.8
93.9
97.3
70.1
91.3
96.9
DEEPSEEK C. 1.3B
62.3
69.1
87.2
30.8
44.5
75.8
23.8
39.4
76.7
DEEPSEEK C. 6.7B
64.0
74.5
95.7
29.6
52.6
93.3
24.1
49.8
89.6
DEEPSEEK C. 33B
65.2
71.2
92.8
30.0
45.0
87.3
22.9
39.1
84.4
STARCODER2 7B
69.5
71.8
72.0
48.6
49.8
49.8
28.5
31.9
31.9
Functional
CODEGEMMA 7B
82.2
79.4
79.4
53.4
55.8
55.8
34.5
40.5
40.6
DEEPSEEK C. 1.3B
0.9
5.2
8.7
1.1
2.0
2.6
0.5
1.5
1.8
DEEPSEEK C. 6.7B
0.6
8.8
13.7
1.2
2.7
3.7
0.0
0.8
1.1
DEEPSEEK C. 33B
0.6
5.9
10.1
1.4
3.4
4.0
0.0
1.4
2.1
Removing entire lines in MRI The MRI setting is based on the tasks proposed by Bavarian et al. (2022). In this work, two settings are suggested: removing random spans and removing entire lines of code. In $4, we presented the results for MRI when removing random spans. Here, we explore the alternative of removing lines, which we call MRI-L. Crucially, lines are often semantically coherent and self-contained, thus posing a different challenge. Equivalenty to MRI, we introduce 1-MRI-I, 2-MRI-L and 3-MRI-L, where we remove between one and three lines from the code. lines are adjacent, merge them into single span to complete.
We present the results Table 7, We observe that this task appears more difficult for the LLMs, contrasting the observations by Bavarian al. (2022). Concretely, model performance for the DEEPSEEK CODER family drops to near 1%. Meanwhile, matching the results observed in $4 for random spans, in all but one setting constrained decoding improves model syntactic and semantic correctness, often significantly.
D.5 COMPARISON TO DINGO
In this section we compare the performance of our method to the method DINGO proposed by Suresh et al. (2025). This method is specifically designed for diffusion language models, but can only enforce regular constraints. As such, context-free constraints. Since the method is not openly accessible, we attempt matching their gen- cration settings and datasets here and compare to the results by them.
less general than our method, which can enforce
Datasets
Suresh et al. (2025) propose two datasets for constrained decoding.
The first dataset JSON-NOUS is similar to our dataset JSON: The model is provided with a natural language text and asked to extract data matching provided JSON schema. The underlying dataset contains the 100 tasks of NousResearch (2024) on which our dataset ISON is based. As opposed to implementation, they count as syntactically correct any output that is generally valid ISON, and functionally correct any output that adheres to the JSON-Schema.
The second dataset, -YMMK--YYOOLIC (Mirzadeh al., 2025), provides the LLM with a symbolic representation of arithmetic tasks, based on the GSM8K dataset proposed by Cobbe et al. (2021)². The LLM should generate an arithmetic expression that uses basic arithmetic operators and specific variables. and that matches the ground -truh solution. An example is provided in Figure 17. We exclude the tasks whose golden solutions require conditionals (x if y else z) and interpret int and frac (y, 2) as and y/z respectively. Syntactically correct outputs must have valid arithmetic expressions in the last occurring pair of and >>, Functionally correct outputs provide an equivalent formula as the golden solution, based on assessment by Z3 (De Moura and Bjørner, 2008).
It should he pointed out however, to avoid confusion, that this evaluation utilizes the dataset produced by Mirzadeh al. (2025) in very different way than suggested by them.
33

---

Published as a conference paper at ICLR 2026
Table On JSON-NOUS, our method (Con.) achieves the same performance as DINGO. On GSM8K- SYMBOLIC, DINGO slightly outperformsn Con..
JSON-NOUS
GSMBK-SYMBOLIC
Model
Van.
DINGO
Con.
Con.
Van.
DINGO
Con.
Con.
Func. Syn.
LLADA 8B
93.0
100
88.5
100.0
72.0
100
87.0
100.0
DREAM 7B
89.0
100
91.0
100.0
65.0
100
69.0
100.0
LLADA 8B
86.2
100
87.5
100.0
24.7
29
27.7
27.7
DREAM 7B
85.0
100
90.0
100.0
25.0
34
25.0
25.0
Table 9: Pre-procesing time (Prex) and time difference per completion of DINGO and method (Con.). We observe that our method has a similar runtime overhead as DINGO while requiring no preprocessing. Notably, preprocessing done once per schema, which implies once per task on the JSON-NOUS dataset.
IONNNNOS
GSMBK-SYMBOLIC
Model
PremNoa
Precon.
DINGO
Con.
PreDIaoO
Preçon.
DINGO
Con.
LLADA 8B
13.2
0
0.1
0.3
32.1
0.1
0.3
DREAM 7B
11.9
0
0.1
0.1
37.0
0.1
0.2
Grammars Although both tasks require context-free grammars be accurately solved, Suresh et al. (2025) disallow context-free parts of the JSON-schema language and hard-code maximum nesting for arithmetic expressions to allow solving the tasks in these datasets with terms matched by regular expressions, provided in the Appendix of Suresh et al. (2025). Our implementation for JSON- NOUS constructs the same grammars as our dataset JSON. For SEMSK-SYMBBLLT new grammar that allows the language model to first reason freely (allowing any characters), and constrains only the content of the last pair of << and >> to a simple, context-free language of arithmetic expressions with addition, subtraction, multiplication, exponentiation and modulo.
we introduce
We compare the performance of LLADA 8B and DREAM 7B with 64 diffusion steps, generation length of 128, generation block and temperature 0.2 and sample 4 times compute confidence intervals.
Models and Parameters
The syntactic and functional results presented in Table 9. We observe that both method Con. and DINGO correctly ensure perfect adherence to JSON-Schemas in the task JSON- NOUS. For GSM8K-SYMBOLIC
Results
observe that DINGO and Con. both enforce 100% syntactic correctness, but DINGO slightly outperforms Con. in functional correctness. This can be due to mul- tiple reasons: The alignment of DINGO is closer to deeply grammar-aligni by Park et al. (2024) than the Heammar-constralnn approach that our method uses. Further, DINGO hardcodes the maximum nesting of arithmetic expressions, thereby biasing the model towards cor- rect solutions.
solution as proposed
Comparing the runtime overhead of both methods, we observe that our method and DINGO achieve similar runtime overhead per sample, with both impacting generation by less than 0.3s. Notably, DINGO requires additional preprocessing for each grammar, which takes up to half minute. the case of JSON-NOUS, this implies additional preprocessing for every sample, each JSON Schema defines its own grammar. Meanwhile, our method requires no preprocessing.
D.6 CASE STUDY
For qualitative evaluation, manually inspect instances where unconstrained decoding fails and our constraining approach successfully corrects errors. We showcase three such examples in Ta- ble 10.
34

---

Published as a conference paper at ICLR 2026
Table 10: Three examples demonstrating the impact of constrained decoding on DLM and MRI com- pletion. Left are unconstrained completions (Van.) with problematic tokens highlighted in red and right constrained completions (Con. with corrections highlighted in green adapted for clarity. In (a), our method forces DREAM 7B generate values of the correct type in summary of finan- cial review for task #30 in our JSON dataset. In (b), generated by DREAM DREAMCODER 7B, our method prevents closing more parentheses than opened when generating SMILES molecule for task # #166. In (c), our method forces DEEPSEEK C. 6.7B to add parentheses around a condition in an if-statement when writing string processing function in task #150 of our C++ dataset.
Vanilla
Constrained
// summarize financial review
// summarize my financial review
{
":apitallaains::
"5210.5000"
"capitalGains":
5210.5000
(a)
"InterestIncome": "1340.
"interestIncome": 1340.25
"totalReturn": "4.5"
"totalReturn": 4.5
// generate allene with axial chirality
// generate an allene with axial chirality C1=CCC=0CCC(000000c00000
(b)
CI=CC1<CCCC(00001000000 )C(00)
separate the groups nested parentheses
separate the groups of nested parentheses
(chr=='! (()
if (chr==
{
{
level+=1;
Level+=1;
(c)
current paren+=chr
current current_ paren+=chr;
else if chr )
else if (chr==')) '
35

---

Published as a conference paper at ICLR 2026
vector<string> outerroei..ittt..rrrarerrroroooo grades)
vector<strings out=(h;
for (int i=0;isgrades. size)) ;+++)
if (grades(:)>=339999 out push back("A+");
(gr3des(1)>3.7901 grades[1]<3.999))) out.push back("A");
(grades(1)=3.3801 grades[i]<<3. 7081) out.push.back("A bac"k"
if (grades[1)=330001 and grades[i]==3.3001] but.push.backk"B""
1f [grades[1)=227701 and ( buttpuuubbac(""")
[grades[1)=2.380) and grades[1) out.push.backk""-") if
11
(grades[1]=2.000)
grades[i] out-push. back("C+")
12
if [grades and grades (001) out.push. back("C");
(grades[1)>11300) grades [1] 7001) out. back("C-"):
14
if [grades[1]=1.009) 1091 and grades (10 out.push back (
(grades[1)>0.7)) grades [1] out.pustt backhbbcc(("M "DD");
back
16
1]<=3.0001) out. push. back("B");
if (gr22e5(1)=2.3001 and grades [i] [i]<=2. 7001) backk (B-")
(grades grades (10eees11
(a) STARCODER2 7B exceeds the token limit in task #81 1-MRI.
Vanilla
Constrained
Constrained
C6CCCC1)
(6CCCC.L))
(c))
(b) LLADA 8B leaves single 1 for completion task #153 in SMILES.
Figure 8: Syntax errors may remain when the model has fewer tokens left to complete than would be required to fulfil the syntactic constraints. This can happen both in MRI (a), when the model exceeds the maximum number of generated tokens and DLM (b), when the model has few mask tokens 1 remaining.
Preventing use of invalid types In Table 10a, DREAM 7B generates a summary of financial review for task #30 in our JSON dataset. The schema requires three values of type float. However, the model attempts to generate these values as strings. By applying our constraining method, it can determined that strings are misplaced, not constituting one the required values, and can not match the intended value type. All attempts at placing such strings are thus rejected during generation. Instead, our method forces the model to generate the values without inserting quotes, resulting in valid and correct result.
Preventing incorrect nesting In Table 10b DREAMCODER 7B generates an invalid SMILES molecule for task #166 by closing more parentheses than it opened. Since the CFG for SMILES correctly handles counting of nesting levels, attempts generate the closing parentheses jected by our method. Instead, the model decides to end the generation.
Preventing inadequate syntax Table 10c, DEEPSEEK C. 6.7B uses conditions without paren- theses in an if-statement when writing a string processing function in task #150 of our C++ dataset. This confusion may stem from the dominance of Python code training data, which does not re- quire parentheses in if-statements. However, this is invalid according to C++ syntax. Our method can correct this mistake successfully, resulting in a correct infilling.
E DISCUSSION
Remaining syntax errors While method achieves substantial improvements in syntactic cor- rectness, using only Con. still leaves a considerable gap until guarantecing correctness. We at- tribute most of this gap the overapproximation of allowing arbitrary number of tokens to
36

---

Published as a conference paper at ICLR 2026
fill regions in the partial output, as done in prior work (Beurer-Kellng 2024). In practice, the LLM is typically limited, ie., in FIM and MRI can only generate up to the user-defined maximum number of tokens, and in DLM it can only generate one token per mask 1. Examples of this issue occurring are presented in Figure 8a for MRI, where the model exceeds the token limit of 256 tokens generates large amounts of unnecessary code, and in Figure 8b, where the DLM model needs to open several molecule branches in a single remaining token.
al., 2024; Ugare et al.,
One approach to resolve this issue would be to accurately model the remaining number of tokens in our regular language construction. However, we observe in experiments that this significantly increases the size of the regular language. as consequently needs to keep track of the number of inserted tokens. This drastically increases the size of the intersection language, rendering our current implementation impractical.
Another approach would be to train the model to signal requiring additional tokens. In MRI, this naturally occurs when the model does not generate an end-of-string token. For DLM, a special token could be added that is replaced with two mask tokens after sampling, increasing the size of the affected infilling region. Concurrent work by Wu et al. (2025) reports that such capabilities appear to generally improve model performance for code infilling.
Our chosen approach to mitigate the issue is to automatically fill the output based on the formal language constraints (Con.). However, this solution cannot rely the model's 'ss probability distribu- tion to steer generation. Determining the most effective way to handle this limitation is an important topic for future work.
Leveraging incremental parsing While we take several steps to improve the efficiency of our method, it can still require significant amount of time to determine the emptiness of the intersec- tion language after each generated token. Future work may leverage the fact that the CFG for the intersection is fixed and the DFA is only updated using small modifications. This may lead to an approach for incrementally computing emptiness checks by reusing the results of the previous inter- section computation. Other approaches to leverage the incremental nature of the parsing, similar to the approaches of Melcer et al. (2024); Ugare et al. (2024), and Mündler et al. (2025) would likely also be able decrease the worst case and practical overhead of the constraining method.
Context-sensitive language features While our method is designed for context-free languages, an interesting future direction would be extensions to handle more powerful language classes, such as context-sensitive languages. Similar to Melcer et al. (2024) and Ugare et al. (2024), simple context-sensitive syntactic features can likely be handled by preprocessing through adequate lexers. Beyond syntactic features, prior work suggested leveraging more semantic insights. such as type systems (Mündler et al., 2025), for constructing more powerful constraint systems. Type checkers with typed holes (Omar et al., 2019) could be leveraged to achieve such systems.
F PROMPTS
In this section, we detail all prompts used for the respective models and tasks.
we provide the model with the raw code, including only comment above the function to guide the model for completions. We use the standard templating suggested for each model to format the prompt for FIM and MRT completion. If MRI is not supported explicitly, emulate it by inserting <TODO> into the remaining infilling regions and repeatedly prompting the model for FIM completion on the first infilling region. In order to prevent the models from generating main methods and tests in the MRI setting, we add main method at the end of the context that is marked with a TODO comment, An example prompt for the 2-MRI setting is provided in Figure 9.
MRI Since models used for FIM and MRI tasks are not instruction-fine
DLM The models used for DLM tasks are instruction-fine finnn-ffittttttdd... allowing us to specify the com- pletion intent in natural language. We provide general description of the task in the system prompt and the specific task content as the first user prompt. The assistant response is prefilled with the start of code fence and, in the case of C++, with the necessary header declarations and function
37

---

Published as a conference paper at ICLR 2026
signature ensure results can be extracted and tests can be executed correctly. The prompts for C++, JSON and SMILES tasks are presented in Figure 10, and 12 respectively.
Benchmark generation prompts As outlined in Appendix D, we generate the JSON and SMILES dataset synthetically by prompting SEMINI-2.5-PROO We provide the used prompts for generation and validation of the generated samples in Figures 13-16.
Miscellaneous Prompts The prompt for the GSM8K-SYMBON SSMBOLIIC experiment for DINGO is shown Figure 17. An example prompt for the grammar prompting (G.P.) is shown in Figure 18.
38

---

Published as a conference paper at ICLR 2026
region
/*
From given vector of integers, generate a vector of rolling maximum element found until given moment in the sequence.
502 rolling-max(12) max([1, 2, 3, 2, 3, 4, 2))
3, 3, 4,
*/ #include-stdio.hh
#includesvector>
using namespace std;
vector<int> rolling_max max numbers)
12
vector<ints out;
13
14 region
for (int L=0:issumbers..o
17 region
18
return out;
21 int {
22
// TODO
23
Figure 9: Example prompt for the 2-MRI task #1. The intial comment and function signature in blue are derived from the dataset prompt, and the remaining code snippets in green are the remainders of the canonical solution with two randomly removed spans. We append stub main function to prevent the model from attempting to generate main function of its own.
system
You are expert in C++ programming. Solve the given problem by writing solution code C++. When answering, insert the solution code in ""ppp..." block. Do neither include test cases not main function.
Check given vector of numbers, any numbers closer each other than given threshold.
10
>>> has close elements ((1.0, 2.0, 3.0), 0.5)
false
hasscclsseeeeement// ((1.0, 2.8, 3.0, 4.0, 5.0, 2.0), 0.3)
13
true
14
15
assistant
*** cpp
#include<stdão. has
18
#includecvector>
19
#include<math.
20
using namespace std;
#inc Linlueeealgorrrth
22
#includess Lude<s lib
bool 23
(vectorclcett numbers, float threshold)
Figure 10: Example prompt for the C++ task #1. The system prompt in black is fixed, whereas the user prompt in blue is extracted from the comment preceding the function and the assistant response prefilled with codefence, and in green, headers, and the function signature of each task.
39

---

Published as a conference paper at ICLR 2026
system
You are helpful assistant that answers in JSON. Here is the JSON schema must adhere to: <schema>
"type": "object", "properties":
"name":
"type": "string"
11
b "email": {
12
"type": "string"
>.
15
s shippingAddress"; {
16
type": "string"
},
19
"required":
20
"name",
21
"email",
"shippingAddress"
24
"addittionalPoperttees:: false
25
26
</schema>
29
We are registering 'Global Exports Ltd. for your services. The main contact person is Samantha Davis, and her corporate email is s.davis@globallepprts..cmm
30
All ship- ments and correspondence should be directed to our headquarters: Global Exports Ltd., 12 Business Park Road, Manchester, 1AB, United Kingdom. We looking forward to fruitful partner ship and are particularly interested in your international ship- ping rates.
31
33
34
35
assistant json
Figure 11: Example prompt for the JSON task. The JSON schema in green is task-specific as well as the the user prompt blue from which information should be extracted into the given schema. The system prompt and prefilled assistant response are fixed.
40

---

Published as a conference paper at ICLR 2026
system
You are specialized assistant that generates SMILES (Simplified Molecular Input Line Entry System) strings from chemical descriptions. You will be given a textual description of a chemical compound or a related task. Your goal is to produce the most accurate and valid SMILES string representing that description.
Your Task:
Based the provided "input" description, generate the corresponding SMILES string.
12
Output Requirements:
13
14
Provide only the SMILES string as your output.
Ensure the SMILES string is syntactically valid.
Represent specified chemical features accurately (atoms, bonds, rings, aromaticity, charge, isotopes, stereochemistry).
17
18
Output:
21
Provide only smiles molecule raw string between triple backticks (***). For instance:
22
23
smiles
C1=CC=CC=C1
26
27
user
28
Propan- 1-amine, primary amine with three-carbor straight chain and the amino group the first carbon.
31 assistant
32
smiles
Figure 12: Example prompt for the SMILES task. The prompt in blue varies per task.
41

---

Published as a conference paper at ICLR 2026
Your goal to create challenging and diverse JSON Schema" problems. You are given a JSON schema that describes specific schema for a JSON problem.
You should generate s== JSON benchmark samples based the provided schema. benchmark sample consists of natural language description describing how the JSON schema should filled out, along with JSON object that adheres to the schema.
For each sample, provide JSON object with the following structure:
11
12
jsssson {{
13
"input": "A natural Language description of how the JSON schema should be filled out. The input should be natural query that user might ask an LLM. The input will given to the LLM as a prompt, along with JSON schema. Based on this input, the LLM should generate a JSON object that adheres to the schema.",
15
16
17
output": "A J50N object that adheres to the provided schema. The output should a valid J50N object that matches the schema reflects the input description."
20
21
22
}}
24
25
Guidelines for generating samples:**
26
++Variety*:: Describe wide range of scenarios that can be expressed using the JSON schema. Ensure that the samples scenarios, and make them sound natural and plausible. ++Difficulty=x; User queries can and should contain distracting information and Longer backgrounds.
wide range possible
29
30
31
>*Realisme*: Test cases should reflect plausible scenarios where the JSON schema would be used.
34
**Reference**: Do not reference the JSON schena in the input description. The input should be a natural query that a user might ask an LLM. It should not reference JSON at all.
35
36
37
38
JSON Schema: (schema)
39
40
Example Input (Do not use this in your samples): (input.qquer))
43
44
Example Output (Do not use this in your samples):
45
(output-query)
Figure 13: Prompt used generate additional ISON Schema samples for the JSoN task using GEMINI-2.5-PRC. Several samples were generated at the same time to increase diversity.
42

---

Published as a conference paper at ICLR 2026
You JSON Schema assistant. You will be given textual description of how a JSON schema should be filled out. Your task to generate JSON object that adheres to the provided schema.
Your Task:
Analyze the textual task.
Construct JSON object that correctly implements the task based on the provided schema.
The JSON object should valid JSON object that matches the schema and reflects the input description.
12
13
14
Output:
Provide only the JSON object string between triple backticks json) Ensure the JSON object satisfies the JSON schema. instance:
17
"ssjson
18
{{
"key": "value", "number": 42,
21
"array": 11,
22
})
23
Json Schema: (schema)
36
27
Description: (input-query)
Figure 14: Prompt used to verify additional JSON Schema samples for the JSON task using GEMINI- 2.5-PRO.
43

---

Published as a conference paper at ICLR 2026
user
You specialized AI assistant tasked with generating benchmark samples for SMILES (Simplified Molecular Input Line Entry System) string generation. Your goal to create diverse accurate chemical structure descriptions and their corresponding SMILES strings.
Please generate *=<nns__smples)=** benchmark samples.
The difficulty these samples should be: #iddifiicutt.deesriiiiinn==
Examples of difficulty levels:
Begiinners:: Simple acyclic molecules, common functional groups (e.g., ethanol, acetic acid, propanamine), small alkanes//lleees//alynne.. *=Intermedaatee Molecules with single or multiple rings (e.g., cyclohexane, pyridine, naphthalene), basic stereochemistry (R/S, E/Z using "@0" ' "\",, сommon drugs or biomolecules (e.g., aspirin, glucose in its open-chain form). <*Advanced==; Complex polycyclic systems (e.g., steroids, bridged compounds), detailed stereochemistry, isotopic labeling, salts, mixtures, or reaction SMILES (if the task is to represent reaction).
13
14
15
17
18
19
For each sample, provide JSON object with the following structure:
21
22
jsson {{
23
24
"input": "A natural language description of chemical compound or a task that uniquely defines chemical structure representable SMILES string. This could
26
IUPAC name, a common name, structural description,
27
request to modify base structure.",
28
"output:: "The correct and valid SMILES string for the chemical structure described in the 'input'. Correctness and validity are paramount."
31
32
33
G*uidellness for generating samples**:
=Accuracys:: generated SMILES string the "output" field MUST accurately represent the chemical structure described in the "input". Ensure correct atom types, bond orders, connectivity, aromaticity, charges, isotopes, and stereochemistry
36
37
implied by the input.
+aalidiyye:: ALl generated SMILES strings must be syntactically valid. #*Clarity Inputæ#:
40
"input" description should be unambiguous provide enough information to define a specific chemical structure. Avoid overly vague descriptions.
41
42
+Vrriety**: Generate diverse set of samples covering different chemical families, structural features (rings, unsaturation, heteroatoms, functional groups), and complexities according to the specified difficulty.
45
46
47
Output Format:
Return list containing the (num_samples) generated JSON objects.
Figure 15: Prompt used to generate additional samples for the SMILES task using GEMINI-2.5-PRO. Several samples were generated the same time increase diversity.
44

---

Published as a conference paper at ICLR 2026
user
You are a specialized AI assistant that generates SMILES (Simplified Molecular Input Line Entry System) strings from chemical descriptions. You will be given textual description of chemical cal compound related task. Your goal is produce the most accurate and valid SMILES string representing that description.
Your Task:
10
Based on the provided "input" description, generate the corresponding SMILES string.
11
12
Output Requi rements: Provide only the SMILES string as your output. Ensure the SMILES string is syntactically valid.
15
16
Represent all specified chemical features accurately (atoms, bonds, rings, aromaticity, charge, isotopes, stereochemistry).
19
20
Output:
21
Provide only the smiles molecule raw string between triple backticks (***). ).
For instance:
24
smiles
25
C1=CC=CC=C1
26
28
(sample}
Figure 16: Prompt used to verify samples for the SMILES task using GEMINI-2.5-PRO.
45

---

Published as a conference paper at ICLR 2026
system
You expert in solving grade school math tasks. You will presented with grade-school math word problem with symbolic variables and be asked to solve An\nBeeore answering you should reason about the problem (using the <reasoning> field in the response described below). Intermediate symbolic expressions generated during reasoning should be wrapped in >>.Anknonly output the symbolic expression wrapped must use numbers as well as the variables defined in the question. You are only allowed to use the following operations:
that answers the question. The expression
/, /1, 8, and xt.
You will always respond the format described below: Let think step by step. <reasoning> The final answer <esymbolic expression
There are (t) trees in the {g}. {g} workers will plant trees in the {g} today. After they done, there will be (tf) trees. How many trees did the (g} workers plant today?
Let's think step by step. Initially, there are {t} trees. After planting, there are {tf) trees. The number of trees planted is <etf t>s. The final answer is <ctf t>>.
10
11 If there are (c) cars in the parking lot and (nc) more cars arrive, how many cars are in the parking lot?
13
Let's think step by step. Initially, there {c} cars. {nc} more cars arrive, the total becomes ecc nexs. The final answer exc + ne>>.
14
{p1) had {ch1} {ol} and {p2) had {ch2) {ol}. If they ate {a} {ol), how many pieces do they have left in total?
17
Let's think step by step. Initially, {pl} had {ch1) (o1), and (p2) had (ch2) (ol), making total of ecch1 + ch2>>. After eating {a} {ol), the remaining total is <cch1 ch2 ass. The final answer is <ech1 ch2 a>>.
19
(pl) had (11) fol). (p1) gave {g) (ol) to {p2). How many (ol) does (pl) have left?
20
21
Let's think step by step. (pl) started with {1I) (ol). After giving (g) (ol) to {p2
,, (pl) has <<l1 g>> {ol} left. The final answer is <<l1
ge>.
22
23
user
24
(name) picks (n1) (fruit)s {dl}. Then he picks {n2) {fruit)s on (d2). On (d3), he
picks (mult} the number of {fruit)s he did (dl). How many (fruit)s does name} have?
25
26
assistan tant
Figure 17: Prompt for the GSM8K-SYMBOLLE task with example prompt in blue at the end.
46

---

Published as a conference paper at ICLR 2026
The answer must adhere to the fol fowinwing grammar:
S -> Line
Line +> Atom Optcombochanndranchiisss
oppcommbchhhnnBBrncciistt ComboChainBranchLLe..
ComboChainBranchList -> ComboChainBranchh ement
ComboChainBrancher Lement
ComboChainBranchlisst
Combochain@ranchEleeenn Chain Branch
Chain Atom OptBond ComboAtomRnumLList
11
OptBond Bond
12
ComboAtomRnunlist -> ComboAtommnnnnEeeeeee
ConboAttonRnunEleennnt ComboxtooRRumList
13
ComboAtomRnunEleen >> Atom Rnum
Bond >> bond
Branch optBondd-DooLinnelist
16.
Opt DotLinniitt OptBondOrDottiieellleee
OptBonddrbottLineEeeemm
Opt Bondortotttiii
pottonndOrDotLLieEEeemee
OptBondOrDot Line
OptBondOrDot Bond
19
Atom >> organicSymbol | BracketAtom
20
BracketAton >> aptionalIsotope Symbol OptionalChiral OptionalHCount aptionalCharrae OptionalMap
21
OptionalIsotope Isotope
OptionalChiral chiral E
23
OptionalHCount -> HCount e
24
Chharee -> Charge
25
OptionalMap -> Map |
Rnum >> digit perc digit digit
27
Isotope digit | digit digit digit digit digit
28
HCount >> digit h
29
Charge -> | +
+ fifteen
+ digit
|
----
|
fifteen
digit
Map Isotope
Symbol organicSymbol
anorganicSymbol
Figure 18: For grammar prompting (G.P.), the grammar in EBNF is appended to the user prompt. The example grammar shown in blue is the SMILES grammar.
47


Reviews:
[{"review_id": "MnWonNy0tW", "reviewer": "Reviewer_9ABz", "summary": "This paper introduces a constrained decoding framework for diffusion language models, which enforces structural constraints during the infilling process.", "questions": "See weakness.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The research question that this paper studied is timely and interesting.", "weaknesses": "Motivation and benefit: While the paper successfully enforces syntactic validity in diffusion language models, it remains unclear whether this constraint leads to better semantic or functional outputs. Improving syntax alone doesn’t necessarily improve model accuracy or usefulness, so it would help to clarify when grammatical correctness translates to real task gains and when it simply bounds decoding behavior.\n\nPresentation and flow: The presentation of the core algorithm (Sec. 3) feels somewhat disconnected and difficult to follow. The exposition moves rapidly from defining the infilling intersection problem to dense formal descriptions (e.g., construction of regular language, grammar intersection, normalization, and emptiness checking) without sufficient intuitive explanation or consistent narrative flow. It is not always clear how these steps tie together in the overall decoding process. Including a running example throughout this section, showing how a concrete partial program or sentence evolves through each construction would make the method more accessible.\n\nFlexibility limitation: It seems that the proposed method constrains the model to remain within a fixed grammar throughout diffusion, which limits flexible reasoning (reasoning first then provide answer). This restriction could prevent diffusion models from leveraging intermediate free-form reasoning steps, which are often beneficial in complex tasks like code synthesis or semantic parsing.\n\nBaselines and comparisons: The evaluation would be stronger with additional baselines such as grammar prompting [1] (provide grammar information in the prompt without enforcing it), and recent CD method on text diffusion models[2]. Reporting results across functionality, syntax validity, and runtime overhead would help contextualize the real advantages of this approach.\n\nEfficiency and scalability: Although the paper claims practical overhead, the computational trade-offs are not deeply analyzed. A breakdown of preprocessing vs. decoding time, memory usage, and how performance scales with grammar size, number of infilling regions, or diffusion steps would strengthen the empirical section. It would also help to discuss whether the rejection-based CFG intersection introduces runtime variance or instability, especially as grammar complexity increases and validity checks become harder to perform.\n\n[1] https://arxiv.org/abs/2305.19234\n[2] https://arxiv.org/abs/2505.23061", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q39JeEbYzC", "reviewer": "Reviewer_2NnJ", "summary": "This paper proposes the first constrained decoding method applicable to Diffusion Language Models (DLMs), which can handle formal languages defined by Context-Free Grammars (CFGs). The method works by transforming the constrained infilling problem into determining whether the intersection between the target language (CFG) and the completion language of partial outputs (a regular language) is non-empty. Incorporating strategies such as grammar optimization and rejection sampling, it significantly improves the syntactic and functional correctness of generated results in tasks like C++ code infilling and JSON structured data extraction, while incurring only moderate computational overhead. Additionally, it also supports the Multi-Region Infilling (MRI) scenario.", "questions": "In the paper, \"rejection sampling\" is adopted to replace the traditional masking strategy to avoid pre-inference latency. However, the relationship between the \"number of sample re-sampling attempts\" and \"model generation diversity\" during the rejection sampling process is not clearly explained. Could you please elaborate on how the threshold for the number of re-sampling attempts (such as the 100 attempts set in the paper) is determined across different tasks (e.g., C++ code generation, SMILES molecular description)? Additionally, does there exist a scenario where \"excessive re-sampling attempts lead to a decline in generation diversity\"?\n\nNeed to add discussion on some related work:  \n[1] Dong, Yixin, et al. \"XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models.\" Eighth Conference on Machine Learning and Systems.  \n[2] Sun, Xintong, et al. \"Earley-Driven Dynamic Pruning for Efficient Structured Decoding.\" Forty-second International Conference on Machine Learning.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- It proposes the first constrained decoding method applicable to Diffusion Language Models (DLMs), filling the gap in existing technologies that fail to constrain DLMs using Context-Free Grammars (CFGs). Meanwhile, it naturally supports the previously unsolved Multi-Region Infilling (MRI) scenario, breaking through the limitation that traditional constrained decoding can only be applied to left-to-right Prefix generation (PRE) or simple Fill-In-the-Middle (FIM).\n- It achieves the first implementation of constraining models with non-fixed-order generation (DLMs) using CFGs, capable of handling complex scenarios that rely on CFG-defined syntax, such as C++, JSON, and SMILES, thereby expanding the application scope of constrained decoding.", "weaknesses": "- In practice, models are limited by the number of tokens, which may lead to failure in meeting syntactic constraints (such as unclosed parentheses and incomplete molecular structures) and leave some residual syntactic errors. Currently, there is a lack of efficient solutions for accurately modeling the number of remaining tokens.\n- In the lexing phase, if there are a large number of ambiguous terminal sequences, even though optimization via a \"unified NFA\" is applied, the risk of combinatorial explosion may still arise in extreme cases, which affects inference speed.\n- For tasks with strong syntactic dependence (e.g., JSON, C++), the improvement in functional correctness is significant. However, for scenarios where correct syntax does not directly determine functionality (e.g., SMILES molecular generation), only a slight improvement can be achieved (an average of 0.2%). This indicates that the method is more effective for scenarios with \"strong syntax-function correlation\" but has limited ability to empower tasks that require semantic understanding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TR2jshYgkc", "reviewer": "Reviewer_fqDc", "summary": "This paper introduces the constrained decoding method for diffusion language models, enabling them to generate text that adheres to formal grammars like context-free grammars. Unlike traditional left-to-right generation, diffusion models generate tokens in arbitrary order, which existing constrained decoding methods cannot handle. The paper solves this by formulating an \"additive infilling problem\" that checks whether partial outputs with holes can be completed into a valid grammar-compliant text, reducing it to testing if the intersection of the target CFG and a regular language is empty. The method achieves strong results on syntactic correctness on tasks like C++ code generation and JSON extraction while maintaining or improving functional correctness, with reasonable computational overhead.", "questions": "DINGO [Suresh et. al.] work ensures optimal decoding with regular grammar. How would the proposed approach compare against DINGO when using a regular grammar, both in terms of overhead and accuracy? \n\n> All MRI models were sampled with temperature 1 and greedy decoding.  \n\nIf you are using greedy decoding, shouldn’t the temp be set to 0?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The paper is the first work in ensuring CFG-constrained generation with diffusion LLMs. \n\n* The paper is well-written and easy to follow. The formalism is solid, and the problem is presented with great detail.  \n\n* The paper addressed a challenging technical problem. Additionally, there are several non-trivial technical contributions such as heuristics to reduce the size of the normalized CFG.  \n\n* The empirical results are consistently strong, showing syntactical and. Functional improvement. And I appreciate the inclusion of confidence intervals.", "weaknesses": "* The MRI task is not natural. Removing the arbitrary character spans is not a realistic scenario in which one would expect to use an LLM. A more realistic code will remove semantically meaningful parts of the code.  \n\n* The overhead of constraining can be large in some cases", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "09LLgO1c07", "reviewer": "Reviewer_vXC3", "summary": "This paper introduces an approach for constraining the output of diffusion LLMs (or in general any infilling model) based on a given context free grammar. The key idea of the work is to compute the space of realizable sequences of a infilling model as a regular language and then intersect it with a target grammar to check if the set is empty. If so the proposed completion is discarded. Some optimizations are presented to make the approach practical. The evaluation shows that the approach improves the quality of pass@1 rates for several models when using constraints.", "questions": "Is the presented algorithm sound/complete? Or when is it not? What does one need to assume about the lexer (1 lookahead?)\n\nIs line 193 really true? If the distribution M is adversarial the algorithm will never terminate. For example, if the probability of e.g., adding an open parenthesis, is higher than ever closing it in the constrained distribution, the one will continue expanding the string without ever completing it. I don't think there is an easy way to always guarantee termination without some strong assumptions on M. This aspect is probably why the algorithm often takes many tokens and the authors need to resort to instead generating a random string in the grammar.\n\nWhat does this mean: \"only 7% of valid completions do not appear in the first 50 selected LLM updates?\"\n\nOne of the known problems of constrained sampling is distribution distortion as discussed in this relevant related work (https://arxiv.org/abs/2405.21047). Suresh et al's Dingo have a theorem claiming that their approach to constraining DLM with regular expressions samples (\"in some sense\") optimally from the constrained distribution. What can the authors say about their approach?\n\nHow was the 256 tokens bound on line 336 chosen?\n\nMy understanding is that the proposed approach is not \"friendly\" for different sampling mechanisms (e.g., beam search) because it does not directly compute token masks? Why not directly compute token masks? The authors claim that this would require expensive preprocessing, but newer GCD algorithms do not require such expensive approaches (see llguidance and GreatGramma (https://icml.cc/virtual/2025/poster/45613), which are not cited in the paper) or at least require small-enough latency. I feel like masking would also drastically reduce the overhead as much of the overhead of the proposed method is caused by guessing and checking incorrect completions.\n\nWhat do the underlined numbers mean in table 1 and 2?\n\nFor SMILES there are existing metrics for semantic quality (https://www.cs.jhu.edu/~jason/papers/lipkin+al.colm25.pdf) why using an LLM as a judge?\n\nOTHER COMMENTS:\n- I would report the absolute latency-per-token in the main body of the paper rather than the relative increase. The latter depends on the GPU on which one runs the LLM", "limitations": "", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Constraining DLM is an emerging area and an important problem and this paper gives some initial solution\n- Encouraging evaluation on existing constrained decoding benchmarks", "weaknesses": "- The paper mostly uses well-established ideas from automata theory. E.g. I believe that the \"new\" algorithm for intersecting regular languages and CFGs presented in this paper is already known (https://aclanthology.org/2023.eacl-main.52/). Also the algorithm is introduced to avoid a complexity stated on line 238, but the complexity of the presented algorithm is not given (at least the reviewer could not find it). The contribution of lines 250-255 is also a bit over claiming. No-one would check emptiness of a grammar with quadratic algorithm as stated by the paper. The reviewer was quite surprised to see the authors citing a random stackexchange post for the CFG emptiness algorithm where what they describe is the algorithm given in any textbook for theory of computation (e.g., Michael Sipser, Introduction to the Theory of Computation, Thm 4.8). \n- The caveats in section 3.3 are what worries me most. For Grammar Constrained Decoding, we have had many papers for which the implementations were incorrect because of how they handled the difference between tokens and lexemes. Some of these errors are reported in this paper (https://icml.cc/virtual/2025/poster/45613), which the authors should perhaps cite. The paper does not state correctness (specifically for Algorithm 3) so there is no guarantee that all and only all invalid masked sequences are rejected (something for which at the very least there should be assumptions about how the lexer operates).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)