DConstrain: Compiling Context-Parameterized Transitions for Diffusion Language Model Constrained Decoding

Introduction

Diffusion language models (DLMs) generate text by iteratively denoising multiple tokens in parallel ([2, 19, 27, 22, 36]). Parallel decoding reduces latency and makes DLMs attractive for agentic tasks such as tool calling ([28 Qin et al.] 2024), API interaction, and structured data extraction. These tasks require outputs that strictly follow a schema ([24, 11]), yet unconstrained DLMs often violate schema rules ([30, 5]). In autoregressive (AR) models, schema compliance is enforced by masking invalid next tokens for a fixed left-to-right prefix ([33, 20, 7]). This mechanism does not carry over directly to DLMs. Because a DLM fills several masked positions at once, two tokens that are each valid on their own can be invalid together.

Existing DLM constrained decoders follow two main paradigms. Verification-based methods sample masked positions independently and then check whether the proposed output can still be completed ([21, 37, 14]). Because independent proposals ignore dependencies among positions, decoding many tokens at once causes frequent conflicts and requires repeated resampling or heuristic fallbacks under finite budgets ([21, 14]). Conversely, automata-based methods enforce compatibility through joint inference ([30, 5, 31]). For the active denoising window (the canvas), they propagate the grammar position by position into a canvas-specific grammar graph whose paths represent sequences of mutually compatible tokens. The decoder then identifies the highest-scoring path or samples according to the graph’s path weights. However, these inference algorithms assume a finite automaton with readily accessible token transitions, leaving the cost of constructing this representation for complex schemas largely unaddressed.

This bottleneck arises because DLM joint inference requires a richer successor-construction interface than AR decoding. An AR decoder only needs a boolean mask of valid next tokens for a single realized prefix ([7]). In contrast, joint inference must compute the exact successor parser configurations for candidate tokens across many hypothetical configurations before any token is committed. Each configuration consists of a local grammar state (a position inside one grammar rule) and a runtime context (a stack of return points and a parsing environment, such as the set of fields already written). Finite-state methods encode runtime contexts as separate automaton states, and DINGO additionally precomputes transitions across the full vocabulary ([30]). In real schemas, nested objects multiply possible stack contexts, while unordered properties introduce exponentially many field histories. Even context-free grammars (CFGs) can require exponential size to represent all permutations of distinct fields ([9]). To keep compiled automata tractable, prior exact decoders restrict schemas to a fixed property order ([30, 5, 31]), excluding valid JSON outputs that the model may prefer.

Our key observation is that context-specific successors need not be compiled as context-specific transitions. Consider a token containing two closing braces, }}, in a nested JSON object. After the first brace closes the inner object, parsing the remaining brace requires returning to the caller. If the parent still lacks a required field, the token is rejected; otherwise, it may close the parent. The return point depends on the stack, and field completion depends on the parsing environment. These contexts can share one compiled procedure: check field completion, return to the caller, and resume parsing the remaining bytes. Rather than precomputing successors for every combination of stack and field history, we compile how to compute them with the runtime context left as a parameter. This separation allows exact successors to be constructed at runtime without enumerating all possible contexts during compilation.

Building on this insight, we propose DConstrain, which compiles schemas into context-parameterized transition programs (Figure 1). Cold compilation specializes token consumption to local grammar states: it precomputes byte-level parsing and local transitions wherever inputs are known, and retains context-dependent stack operations, environment guards, and deferred parsing symbolically. Tracking field histories as runtime values supports arbitrary property order without enumerating field subsets offline. At runtime, warm compilation instantiates these programs for configurations reachable in the current canvas, resolves context-dependent operations, and constructs the exact successor relations required for joint inference. Since warm graph construction does not require model scores, it overlaps with the model forward pass. Finally, token-effect grouping identifies equivalent compiled token effects during cold compilation, before runtime contexts are bound. The resulting groups can be reused across different stacks and environments, sharing successor computation even when the concrete successors differ across contexts. Objective-specific score aggregation and token restoration preserve the exact Viterbi optimum and token-labeled path distribution.

Our contributions are summarized as follows:

• Successor-Construction Bottleneck. We identify token-labeled successor construction as the primary scalability bottleneck in automata-based DLM decoding. Materializing context-specific transitions incurs combinatorial growth with nesting and field histories. Even CFGs can require exponential size for arbitrary permutations of distinct fields, motivating fixed property orders in prior exact decoders.

• Context-Parameterized Compilation. We introduce context-parameterized transition programs paired with a two-stage compiler and compile-time token-effect grouping. We prove that program execution preserves the reference successor relation and that grouping preserves both the Viterbi optimum and the full token-labeled path distribution of ungrouped inference. The compiled programs can be reused by any constrained-decoding algorithm that consumes token-labeled grammar successors.

• Exact Unordered Decoding. Across three structured-output benchmarks and multiple DLM tokenizers, DConstrain substantially improves compilation coverage and latency under arbitrary property order. On BFCL, exact unordered constraints also improve task accuracy over both fixed-order constraints and unconstrained decoding.

Related Work

Autoregressive Constrained Decoding. Grammar-constrained decoding is widely used to guarantee structured outputs in autoregressive LLMs. At each step, the decoder masks invalid tokens for the realized prefix and advances the parser with the selected token. Early methods introduced incremental parsing and semantic constraints for structured NLP tasks ([29, 25, 10]). Subsequent work corrected the distributional distortion of token-level masking through adaptive sampling ([23]). Later systems focused on efficient tokenizer-aware mask generation ([33, 3, 15, 20, 7]), and XGrammar 2 added JIT compilation with cross-grammar cache reuse ([17]). Our compiler design is closest to two of these systems. XGrammar ([7]) precomputes stack-independent valid tokens at each grammar position and checks only the remaining tokens at runtime. Koo et al. [15] compose a detokenizing transducer with a pushdown automaton so that each token transition carries explicit stack operations. DConstrain also compiles context-independent work once, but it targets a different successor-construction interface. A validity mask only identifies admissible next tokens for a single prefix. In contrast, DLM joint inference requires the full transition map $(c,v) \mapsto T_G(c,v)$ across many hypothetical configurations before any token is committed. DConstrain further keeps the written-field history as a runtime parameter, which no compact grammar can encode (Proposition 3.2).

DLM Constrained Decoding. Early diffusion language models supported soft control by steering continuous latents with classifier gradients ([18]), but soft guidance cannot guarantee valid syntax. Decoders for hard constraints fall into two families. The first family consists of verification-based decoders, which sample candidate tokens independently and resample or recover when a grammar check fails. Constrained Diffusion ([21]) checks whether the partial output can still be completed. LAVE ([37]) validates each proposed token against sampled lookahead completions. EPIC ([14]) accelerates completion checks with memoized lexing and Earley-style parsing ([8]) to commit verified token batches in parallel. Although these decoders avoid finite-state materialization, a feasibility check only ensures that some valid continuation exists. At each step, it recovers neither the highest-scoring joint assignment nor an exact sample from the constrained distribution. In our BFCL experiments, LAVE-Opt and EPIC-Opt have lower completion rates and throughput than DConstrain (Table 2 and Table 3).

Schema-order
Method	\multicolumn{7}{c	}{DiffusionGemma}	\multicolumn{7}{c	}{LLaDA2.2}
	$N$	Cold (%)	Run (%)	Valid. (%)	TPF	Acc. (%)	TPS	Overhead (%) ↓	$N$	Cold (%)	Run (%)	Valid. (%)	TPF	Acc. (%)	TPS	Overhead (%) ↓
Native-Opt	2495	—	100.00	89.50	8.04	76.39	165.14	0.0	2495	—	100.00	94.87	7.40	80.80	752.25	0.0
Verification-based
LAVE-Opt	2272	100.00	91.06	91.06	6.05	36.71 ↓39.68	6.00	2652.3	2480	100.00	99.40	99.40	4.67	72.55 ↓8.25	221.51	239.6
EPIC-Opt	2024	100.00	81.12	80.92	2.94	36.63 ↓39.76	3.43	4714.6	2463	98.88	98.72	98.72	5.62	63.41 ↓17.39	24.80	2933.3
Automata-based
DINGO-Opt	2495	100.00	100.00	100.00	8.11	37.19 ↓39.20	23.13	614.0	2495	100.00	100.00	100.00	6.86	72.63 ↓8.17	101.32	642.4
DConstrain	2495	100.00	100.00	100.00	8.13	37.27 ↓39.12	130.47 5.64×	26.6 23.10×	2495	100.00	100.00	100.00	6.89	72.71 ↓8.09	437.94 4.32×	71.8 8.95×
Any-order
Method	\multicolumn{7}{c	}{DiffusionGemma}	\multicolumn{7}{c	}{LLaDA2.2}
	$N$	Cold (%)	Run (%)	Valid. (%)	TPF	Acc. (%)	TPS	Overhead (%) ↓	$N$	Cold (%)	Run (%)	Valid. (%)	TPF	Acc. (%)	TPS	Overhead (%) ↓
Native-Opt	2495	—	100.00	90.34	8.14	76.55	167.90	0.0	2495	—	100.00	94.95	7.21	80.68	736.38	0.0
Verification-based
LAVE-Opt	2408	97.07	96.51	96.47	7.71	79.20 ↑2.65	9.50	1667.4	2420	97.07	96.99	96.99	5.74	79.24 ↓1.44	313.71	134.7
EPIC-Opt	2212	92.38	88.66	88.18	7.44	74.71 ↓1.84	6.28	2573.6	2151	86.41	86.21	86.21	6.09	65.05 ↓15.63	37.35	1871.6
Automata-based
DINGO-Opt	2141	85.81	85.81	85.81	8.13	69.85 ↓6.70	2.96	5572.3	1779	71.30	71.30	71.30	8.11	59.30 ↓21.38	42.39	1637.2
DConstrain	2495	100.00	100.00	100.00	8.15	81.56 ↑5.01	103.82 35.07×	61.7 90.28×	2495	100.00	100.00	100.00	8.10	81.60 ↑0.92	386.70 9.12×	90.4 18.10×

	DiffusionGemma ($N = 1{,}874$)					LLaDA2.2 ($N = 2{,}448$)
Method	Valid. (%)	TPF	Acc. (%)	TPS	Overhead (%) ↓	Valid. (%)	TPF	Acc. (%)	TPS	Overhead (%) ↓
Native-Opt	89.70	7.07	78.50	145.71	0.0	94.97	7.42	81.04	754.40	0.0
Verification-based
LAVE-Opt	100.00	5.89	48.19 ↓30.31	6.76	2055.5	100.00	4.67	72.74 ↓8.30	221.32	240.9
EPIC-Opt	99.73	3.19	48.72 ↓29.78	3.81	3724.4	100.00	5.63	64.65 ↓16.39	25.00	2917.6
Automata-based
DINGO-Opt	100.00	7.13	48.88 ↓29.62	21.48	578.4	100.00	6.95	72.99 ↓8.05	93.03	710.9
DConstrain	100.00	7.13	48.88 ↓29.62	115.10 5.36×	26.6 21.75×	100.00	6.95	72.99 ↓8.05	443.47 4.77×	70.1 10.14×
Any-order
	DiffusionGemma ($N = 2{,}201$)					LLaDA2.2 ($N = 2{,}149$)
Method	Valid. (%)	TPF	Acc. (%)	TPS	Overhead (%) ↓	Valid. (%)	TPF	Acc. (%)	TPS	Overhead (%) ↓
Native-Opt	91.46	7.81	79.46	165.63	0.0	95.53	7.41	82.78	756.59	0.0
Verification-based
LAVE-Opt	100.00	7.43	83.55 ↑4.09	9.92	1569.7	100.00	5.75	82.60 ↓0.18	315.63	139.7
EPIC-Opt	99.45	7.51	84.55 ↑5.09	6.30	2529.0	100.00	6.09	75.48 ↓7.30	37.34	1926.2
Automata-based
DConstrain	100.00	7.81	84.87 ↑5.41	110.50	49.9	100.00	8.22	83.15 ↑0.37	490.98	54.1

The second family consists of automata-based methods, which couple token choices through joint inference over finite automata ([30, 5, 31]). DINGO ([30]) builds a DFA and precomputes vocabulary-level token transitions. Dang & Ermon [5] perform chain and tree inference over a finite automaton whose edges group tokens and sum their probabilities. Building on such step-exact samplers, Thimmaiah et al. [31] use twisted sequential Monte Carlo to correct trajectory bias across denoising steps. However, all three methods compile JSON schemas under a fixed property order to keep the automaton finite and small. Interpreting a pushdown automaton directly at runtime would avoid materializing context-specific states, but it would repeatedly execute token-consumption logic for every reached configuration. DConstrain resolves this tension by compiling reusable local grammar–token programs while leaving the runtime context unbound. Within this framework, our token-effect grouping generalizes the edge-level aggregation of Dang & Ermon [5] to parameterized transitions. As a result, a single token partition per local grammar state serves every runtime context.

Preliminaries

A JSON schema $\mathcal{G}$ (Wright et al., [35]) defines a grammar whose rules can nest. For example, an object property can itself hold an object. We therefore parse $\mathcal{G}$ with a pushdown parser (Hopcroft et al., [13]), where each grammar rule is represented as a small automaton and entering a nested rule pushes a return point onto a stack. At any point, the parser state is captured by a configuration $c=(q,s,e)$. Here $q$ is the local grammar state, which marks a node inside the current rule’s automaton. The stack $s$ holds pending return points, and the parsing environment $e$ records earlier parsing choices, such as which object fields have already been written. Together, $(s,e)$ form the runtime context of $c$. Given a configuration $c$ and a vocabulary token $v\in\mathcal{V}$, the token-transition relation $T_{\mathcal{G}}(c,v)$ returns the set of valid successor configurations $c'$ after consuming $v$. This set omits statically certified dead configurations that can never lead to a complete valid output (see Appendix § 7.§ 1 for formal parser semantics).

Automata-Based DLM Constrained Decoding. Automata-based methods apply $T_{\mathcal{G}}$ across an active decoding window to coordinate token choices at multiple unresolved positions (Suresh et al., [30]; Dang & Ermon, [5]). Consider a denoising iteration $t$ and its canvas of $H$ token positions. Let $\mathcal{V}_i^t\subseteq\mathcal{V}$ denote the candidate tokens at position $i$; a position that is already fixed has a singleton candidate set. Starting from the parser configurations $\mathcal{C}_0$ compatible with the fixed prefix $u$, the token-labeled transitions and reachable configurations at each position are defined recursively as

The position-indexed layers $\{\mathcal{C}_i\}_{i=0}^{H}$ and transitions $\{E_i\}_{i=1}^{H}$ form a layered canvas-specific grammar graph $\mathcal{F}_t$. A full-window path through $\mathcal{F}_t$ is admissible if its terminal configuration satisfies the required acceptance or continuation condition.

Each denoising iteration constructs and resolves $\mathcal{F}_t$ in two stages. First, grammar propagation builds the graph layers from left to right: starting from $\mathcal{C}_0$, it advances every reached configuration with every candidate token to collect its successors. Notably, propagation depends only on parser configurations and candidate sets, not on model scores. Second, joint inference weights each edge $(c,v,c')\in E_i$ using the token probability $p_i(v)$ from the DLM predictions $P_t$ (defined in Appendix § 7.§ 2). Max-product dynamic programming then extracts a highest-weight admissible path via the Viterbi algorithm (Viterbi, [32]), while sum-product computes path-weight sums for exact probabilistic sampling (Goodman, [12]; Dang & Ermon, [5]).

Problem Formulation. All automata-based decoders share this two-stage pipeline, and their efficiency hinges on how grammar propagation answers each successor query $T_{\mathcal{G}}(c,v)$. In AR constrained decoding, each forward pass predicts a single position for a fixed prefix. The decoder only needs a boolean mask of valid next tokens, after which it samples one token $v$ and advances the parser once (Dong et al., [7]). In contrast, a DLM leaves many positions unresolved at once, and each position can be reached by many hypothetical parser configurations. Before committing any token, grammar propagation must return exact successor sets rather than boolean masks, and it must evaluate every candidate token at every reached configuration. Without query reuse or token grouping, exhaustive propagation requires

configuration–token queries per canvas.

To avoid expensive online parsing during propagation, finite-state pipelines such as DINGO ([30]) precompute token-level transitions offline during cold compilation. Given a materialized finite state space $Q_{\mathcal{G}}$, a dense transition table stores an entry for each of the $|Q_{\mathcal{G}}||V|$ state–token pairs, turning each online query into a table lookup. However, flattening runtime contexts into explicit finite states duplicates shared grammar logic and precomputes transitions for contexts that a canvas may never reach. The following propositions quantify this state explosion.

Proof sketch. Each context-expanded state pairs a local state with a stack of depth at most $d_{\max}$ over $g$ frame symbols and one environment value; counting these triples yields Eq. (3). For bounded-depth brackets, any two distinct stacks of open brackets require distinct closing sequences. By the Myhill–Nerode theorem ([13]), a minimal complete DFA must assign a separate state to every valid stack plus one sink state, which bounds the number of table entries required.

Proposition 3.1 leaves the environment factor $B$ abstract. When a schema includes unordered object properties, $B$ itself grows exponentially, and replacing finite automata with context-free grammars does not avoid this blow-up.

Proof sketch. Any two prefixes that have written different subsets of required fields admit different sets of valid completions, so the Myhill–Nerode theorem separates all $2^k$ subsets. For the CFG bound, intersecting the schema language with a regular language that fixes field values and counts, and then projecting onto property names, yields the language of all permutations of $k$ distinct symbols. Every CFG generating this permutation language has size $2^{\Omega(k)}$ ([9]). Because regular intersection and homomorphic projection increase CFG size by at most a polynomial factor, the original grammar must also have size $2^{\Omega(k)}$.

Propositions 3.1 and 3.2 bound the size of static finite-state and CFG representations rather than the runtime cost of parsing a single string. For offline finite-state compilers, however, representation size directly dictates compilation cost, which explains the sharp growth with nesting depth and property count observed in § 5.3.

To overcome this bottleneck, we seek a compiled artifact $A_{\mathcal{G}}$ containing executable successor-construction procedures, with the runtime context supplied at query time. These procedures must implement the exact successor-construction interface

for every configuration–token pair queried during grammar propagation. Our goal is to minimize cold-compilation cost, compiled storage, and online query latency without materializing the exponentially large context-expanded state space.

DConstrain

DConstrain compiles schemas into context-parameterized transition programs (Figure 1). These programs implement the successor interface in Eq. (4), independently of the downstream constrained-decoding algorithm. Cold compilation specializes token consumption to local grammar states while leaving the runtime context unbound and retaining context-dependent operations symbolically (§ 4.1). Warm compilation executes these programs for reached configurations to construct exact successors (§ 4.2). Token-effect grouping partitions tokens by their canonical compiled effects during cold compilation and reuses these partitions during warm compilation (§ 4.3). Appendices § 7.§ 3 and A.5 provide correctness and complexity analyses.

Context-Parameterized Transition Compilation

Given a target schema $\mathcal{G}$, DConstrain represents local grammar rules as a recursive transition network (RTN) ([34]), keeping the call stack $s$ and parsing environment $e$ outside the RTN as runtime context. Specifically, we decompose the environment as $e=(d,\eta)$, where $d$ tracks the active container depth and $\eta$ tracks the choice environment (such as the written-field history), giving the full configuration $c=(q,s,d,\eta)$. Cold compilation specializes token consumption to each local grammar state and token pair $(q,v)$ while leaving $(s,d,\eta)$ unbound:

Each program $P_k=(I_{k,1};\ldots;I_{k,\ell_k})$ is an ordered symbolic execution alternative for consuming $v$ from $q$. Its guards may reject a concrete runtime context, and its continuation may depend on a caller selected by the incoming stack. Cold compilation evaluates byte matching and local grammar operations wherever their inputs are known, retaining context-dependent operations and the input and execution state needed to resume deferred parsing. The resulting programs take two forms: residual programs with a deferred caller-dependent continuation, and compact summaries with a statically determined target state.

When token consumption or token-boundary processing must pop a return frame from the incoming stack, the caller needed to continue parsing is unknown during cold compilation. The compiler resolves pushes and pops whose return destinations can be determined locally. At the first return that requires the incoming stack, it records a residual program with the remaining token input and the current symbolic execution state. Warm compilation uses the concrete stack to resume the caller-dependent continuation. A shared program can therefore compute exact successors even when its final local state cannot be determined offline.

When a program does not require a caller from the incoming stack $s$, symbolic execution reduces it to a compact summary $P=(q',\rho,\Delta,m,\Omega)$. Here $q'$ is the resulting local grammar state, and $\rho$ is the sequence of new return frames pushed (and not yet popped) while consuming $v$. The integers $\Delta$ and $m$ record the net change and minimum intermediate change in container depth $d$. Finally, $\Omega$ is an ordered sequence of environment guards and updates on $\eta$, such as verifying that field a has not yet appeared and recording its presence. During warm compilation, binding a summary $P$ to a concrete runtime context $(s,d,\eta)$ evaluates directly to

where $\mathbin{\|}$ appends frames to the stack and $\perp$ indicates a violated guard (see Appendix § 7.§ 3 for the full specification with auxiliary metadata). For these summaries, binding evaluates the remaining guards and updates under $(s,d,\eta)$ and constructs the successor without recompiling grammar logic for that context. Together, summaries and residuals allow configurations with the same local state $q$ to reuse $\mathcal{E}(q,v)$ even when their successors differ.

The choice environment is likewise handled through guarded runtime operations. For an object with $k$ fields under arbitrary property order, $\eta$ stores the set of written fields as a runtime bitmask, while the compiled operator $\Omega$ encodes the guards for field uniqueness and required-field completion. A single program set $\mathcal{E}(q,v)$ is shared across the $2^k$ possible field histories, so cold compilation does not enumerate those subsets as local grammar states. Concrete histories remain runtime values, and program execution preserves the order and scope of their guards and updates.

Warm Compilation

Warm compilation executes the remaining operations of a compiled program under a concrete runtime context. We first specify its token-level successor interface: for a reached configuration $c=(q,s,e)\in C_{i-1}$ and a candidate token $v\in\mathcal{V}_i$ at position $i$, it returns

Here $\operatorname{Exec}(P,c)$ applies Eq. (6) to ordinary summaries, resumes residual programs under the concrete caller, and completes token-boundary processing. Failed guards contribute no successor. The resulting context-specific successors drive the layer-by-layer propagation in Eq. (1). The implementation evaluates this interface through the compile-time partitions introduced in § 4.3, using one representative token per reached configuration and active group. Transitions for unreachable contexts are never instantiated.

The following theorem establishes that the two-stage compiler and program execution preserve the reference successor relation, including caller-dependent continuations.

Token-Effect Grouping

Parameterized programs share transition logic across runtime contexts, but evaluating candidate tokens separately at each reached configuration retains the vocabulary factor in Eq. (2). We extend token aggregation in finite-state inference ([5]) to context-parameterized programs: during cold compilation, tokens are grouped by their canonical compiled effects at each local state, before any concrete stack or environment is bound. For an unconstrained string rule, for example, many text tokens compile to the same continuation program (Figure 1). We define the grouping relation at local state $q$ by

Cold compilation records the partition $\Pi_q=\mathcal{V}/\sim_q$. Canonicalization retains instruction order, operands, stack and environment operations, and execution-relevant boundary and residual metadata. Canonical equality is a sufficient, not necessary, condition for identical successor sets under every admissible runtime context (Appendix § 7.§ 3). The same partition can therefore be reused across different stacks and environments, even though their concrete successor sets may differ.

The offline partition $\Pi_q$ is shared by all configurations with local state $q$. At position $i$, the candidate set selects its active groups, $\Pi_{q,i}^t=\{G\in\Pi_q:G\cap V_i^t\ne\varnothing\}$. For each reached configuration $c=(q,s,e)$ and active group $G\in\Pi_{q,i}^t$, warm compilation evaluates the successor relation once using any representative token $v_G\in G\cap V_i^t$:

Using these representative successor sets, warm compilation directly constructs one group-level edge $(c,G,c')$ for each returned successor $c'\in\widehat{T}_G(c,G)$, without first materializing the corresponding token-level edges. This yields the grouped transition layer

As analyzed in Appendix § 7.§ 5, the number of successor evaluations now scales with active groups rather than individual tokens:

Grouping reduces successor evaluations and the number of edges traversed during joint inference. The bound above concerns successor evaluations; objective-specific score aggregation still uses the individual probabilities of active group members, whose identities remain available for token restoration.

The compile-time partition is independent of model scores and of the inference objective. Joint inference assigns weights to its group-level edges using the current predictions $P_t$. For nonnegative token weights $p_i(v)$, define the objective-specific aggregates

Sum-product inference weights each group-level edge by $M_i(G)$, whereas max-product inference uses $m_i(G)$. For any fixed source configuration $c$, the active groups are disjoint and all tokens within each group have the same successor set. These objective-specific reductions therefore preserve the weighted transition operator between $c$ and every successor configuration $c'$ for $\oplus\in\{+, \max\}$:

After selecting a group-level edge, DConstrain restores a token $v\in G\cap V_i^t$ according to the same inference objective. Sum-product restoration is applied to selected groups with positive mass $M_i(G)>0$. The restoration rules are

The following theorem shows that grouping preserves weighted inference.

Solver-agnostic inference interface. Because DConstrain preserves the exact successor relation $T_G(c,v)$ and both weighted transition operators, the same grouped graph representation supports different automata-based solvers. Appendix § 10.§ 2 evaluates both Viterbi decoding and the tree-based sampling algorithm of Dang & Ermon [5].

Runtime integration. Because neither warm compilation nor grammar propagation depends on model logits, CPU workers execute both stages concurrently while the GPU computes the DLM forward pass. Warm compilation runs only during the first forward pass of each canvas. Subsequent denoising iterations on the same canvas only shrink the candidate sets $V_i^t$ as positions are resolved, so their required successor queries are a subset of those already computed. In every iteration, grammar propagation builds $\mathcal{F}_t$ from these cached successors during the forward pass, and joint inference begins as soon as both $\mathcal{F}_t$ and $P_t$ are ready. Compact compressed sparse row (CSR) layouts and specialized GPU kernels further accelerate the joint inference solve. Appendix § 8.§ 3 details the full compiler–runtime pipeline and the optimizations enabled in each experimental setting.

Experiments

Workloads and models. We evaluate on BFCL (Patil et al. [24]), JSONSchemaBench (Geng et al. [11]), and ComplexFuncBench (Zhong et al. [39]). BFCL and ComplexFuncBench provide tool declarations for both compilation and task-level evaluation, while JSONSchemaBench stress-tests compilation with diverse and complex schemas. For end-to-end evaluation, we select two recent DLM families with different decoding granularities: LLaDA2.2 (Bie et al. [4]) with a block size of 32 and DiffusionGemma (DiffusionGemma Team et al. [6]) with a block size of 256. Both decode a long output block by block, as in block diffusion [1]. To reflect realistic serving conditions, we run LLaDA2.2 in SGLang [38] and DiffusionGemma in vLLM [16] rather than in standalone research inference loops. Cold-compilation experiments need only the corresponding tokenizers.

Comparisons. For cold compilation, we compare with DINGO’s DFA compiler [30], an NFA adaptation, and DINGO-Opt, our engineering-optimized version of DINGO, under matched schemas and tokenizers. The main BFCL runtime tables compare unconstrained Native-Opt decoding, the verification-based methods LAVE-Opt [37] and EPIC-Opt [14], DINGO-Opt, and DConstrain. Table 6 compares DConstrain and DINGO-Opt on their common successful cases, including Any-order. The -Opt suffix identifies baseline implementations with our optimizations and adaptations to the decoding setup. Appendix § 10 adds alternative solvers and further baselines.

Method	LLaDA2.2 Valid. (%) ↑	LLaDA2.2 E2E (ms) ↓	LLaDA2.2 Solve/forward (ms) ↓	DiffusionGemma Valid. (%) ↑	DiffusionGemma E2E (ms) ↓	DiffusionGemma Solve/forward (ms) ↓
BFCL — fixed order
Native-Opt	94.87	85.42	—	89.50	1948.23	—
DINGO-Opt	100.0	264.23	32.45	100.0	12874.32	216.72
DConstrain	100.0	115.21 2.29×	3.16 10.27×	100.0	2521.42 5.11×	9.95 21.78×
BFCL — any order
DINGO-Opt	100.0	813.20	74.18	100.0	145529.00	3195.39
DConstrain	100.0	122.35 6.65×	2.81 26.40×	100.0	3145.64 46.26×	29.44 108.54×
JSB — fixed order
Native-Opt	73.7	169.42	—	55.3	1894.82	—
DINGO-Opt	100.0	2282.87	172.57	100.0	54323.33	853.25
DConstrain	100.0	327.61 6.97×	11.78 14.65×	100.0	5388.21 10.08×	34.17 24.97×

Cold-compilation targets. Table 1 compares compilers that prepare token-labeled successor construction for joint solving. Verification-based methods prepare a different object: a parser and auxiliary structures for deciding whether a proposed partial output admits a legal completion [21, 37, 14]. A Boolean verifier can return after finding one witness. A joint solver needs the compatible successor alternatives so that max- or sum-product inference can combine their model weights. DConstrain compiles the programs that construct these alternatives, leaving the inference algorithm downstream. Verifier preparation and successor compilation thus have different output contracts; Table 2 and Table 3 compare their resulting decoding pipelines in completion, accuracy, and throughput.

Method	LLaDA2.2 Success (%)	LLaDA2.2 P50 (s)	LLaDA2.2 P95 (s)	LLaDA2.2 Speedup{sup}†	DiffusionGemma Success (%)	DiffusionGemma P50 (s)	DiffusionGemma P95 (s)	DiffusionGemma Speedup{sup}†
BFCL — fixed order
DINGO	90.3	54.30	132.90	92.9×	91.7	38.45	115.41	140.4×
NFA	82.5	61.30	148.50	113.4×	86.0	45.52	122.17	167.4×
DINGO-Opt*	100.0	2.21	5.64	3.92×	100.0	1.20	3.29	3.88×
DConstrain	100.0	0.58	1.48	—	100.0	0.31	0.82	—
BFCL — any order
DINGO-Opt*	71.30	5.85	12.25	9.43×	85.81	3.76	14.16	10.39×
DConstrain	100.0	0.66	1.23	—	100.0	0.41	0.90	—
JSB — fixed order
DINGO	67.7	38.00	129.11	85.0×	67.7	31.97	96.34	122.9×
NFA	63.7	45.26	128.40	102.8×	71.3	30.71	113.85	114.0×
DINGO-Opt*	74.8	2.51	70.50	4.83×	77.6	1.65	37.66	4.53×
DConstrain	81.4	0.60	14.14	—	83.3	0.37	8.27	—
CFB — fixed order
DINGO	34.8	115.18	159.24	121.9×	44.7	84.73	124.04	174.6×
NFA	32.5	131.29	175.14	132.0×	74.0	116.63	171.69	221.9×
DINGO-Opt*	100.0	4.66	7.34	4.02×	100.0	2.21	3.02	3.96×
DConstrain	100.0	1.17	1.78	—	100.0	0.56	0.76	—
CFB — any order
DINGO-Opt*	9.9	7.63	16.69	8.12×	13.7	2.90	9.40	3.54×
DConstrain	100.0	0.99	1.41	—	100.0	0.80	1.16	—

Main Results

Table 1 evaluates cold compilation under fixed and arbitrary property order, with nesting depth limited to four for comparability with the finite-state baselines. The BFCL runtime evaluation uses two complementary cohorts. Table 2 counts cold admission, runtime completion, strict-schema validity, and official semantic accuracy over all 2,495 cases; TPS and TPF use each row’s completed cases. Table 3 defines a common runtime-success cohort independently for each model and property-order condition by intersecting the four reported methods within that condition. Schema-invalid completions remain in each cohort. DINGO-Opt compiles 71.30% of BFCL schemas with LLaDA2.2 and 85.81% with DiffusionGemma under Any-order. Table 2 reports its Any-order outcomes on the full pool. Including it in the intersection would substantially shrink the common-success cohorts in Table 3; Table 6 compares DINGO-Opt and DConstrain on their paired successful cases. Each order condition has its own common-success cohort. Appendix § 8.§ 2 specifies the accounting rules.

Cold-compilation efficiency. DConstrain reduces compilation cost across both tokenizers and all datasets. Under fixed order and depth four, it is $3.88$–$4.83\times$ faster than DINGO-Opt on paired cases, even though DINGO-Opt already shares our C++ pipeline and CSR representation (Appendix § 8.§ 3). The gap widens under arbitrary property order: DConstrain keeps 100% compilation coverage on BFCL and CFB, whereas DINGO-Opt loses substantial coverage. On the cases that both methods compile, DConstrain remains $3.54$–$10.39\times$ faster. On JSB, most remaining DConstrain failures with the LLaDA2.2 tokenizer come from JSON Schema features outside the supported fragment, such as oneOf exclusivity and general allOf intersection (13.7% of all schemas); 4.8% exceed compilation resource or construction budgets (Appendix § 10.§ 5). Mature engines also support only part of this benchmark: on its GitHub-Hard split, XGrammar and Guidance declare support for 69% and 60% of the schemas [11].

Runtime completion and throughput. DConstrain completes all 2,495 cases with 100% strict-schema validity under both models and both property-order settings (Table 2). On the common cohorts in Table 3, it has the highest TPS among the constrained methods in all four settings. Its TPS is $1.56$–$17.03\times$ that of LAVE-Opt and $13.15$–$30.21\times$ that of EPIC-Opt. Under Schema-order, it reduces overhead above Native-Opt by $10.14\times$ for LLaDA2.2 and $21.75\times$ for DiffusionGemma relative to DINGO-Opt. On the paired Any-order cohorts in Table 6, DConstrain reduces end-to-end latency by $6.65\times$ and $46.26\times$, and solve latency per forward by $26.40\times$ and $108.54\times$, respectively.

Table 6 reports end-to-end and per-forward solver latency on the DConstrain/DINGO-Opt common-success cohorts. Warm compilation overlaps the model forward pass. In every plotted setting of Figure 2, at least 94% of warm-compilation calls finish within the mean forward time. Appendix § 10.§ 2 reports additional solver experiments.

Tokens per forward and GPU computation. TPF measures how many model-generated tokens are produced per generation forward, making it an important measure of GPU computation per output token in a DLM. Raising the token-acceptance threshold commits fewer tokens per step and can improve accuracy through additional refinement, reducing TPF. LAVE also uses additional model forwards for lookahead to reduce uncertainty [37]. Both approaches spend more GPU computation per generated token. DConstrain combines the highest Any-order semantic accuracy with higher TPF than the verification-based methods on both models: 81.60% accuracy at 8.10 TPF for LLaDA2.2 and 81.56% at 8.15 TPF for DiffusionGemma on the full pool. The common-success results show the same combination of high accuracy and high TPF. TPF counts non-stop model token IDs over all generation forwards for the selected cases; CPU-generated completion text is excluded.

Ablation Study

Table 4 isolates three mechanisms on BFCL with the LLaDA2.2 tokenizer and arbitrary property order. w/o Two-Stage Env binds parsing-environment values during cold compilation instead of deferring them to runtime. w/o Local-State Reuse disables memoization of transition programs for repeated occurrences of the same local grammar state but still keeps the factorized runtime environment and continuation stack. w/o Token Grouping processes tokens with equivalent effects independently. All variants share the same grammar semantics and decoding setup.

Variant	Cold (s) ↓	Solve (ms) ↓	Memory (MiB) ↓
Full (any order)	0.72	3.72	5.94
w/o Two-Stage Env	10.52 (14.61×)	3.83 (1.03×)	20.97 (3.53×)
w/o Local-State Reuse	1.87 (2.60×)	3.75 (1.01×)	12.98 (2.19×)
w/o Token Grouping	0.96 (1.33×)	25.32 (6.81×)	24.42 (4.11×)
Dataset	Method	States	Edges ($10^3$)		Recorded payload (MB)
		Mean	P50	P95	P50	P95
BFCL	DINGO	228.74	524.77	1 226.27	54.20	114.91
	NFA	233.74	352.71	1 052.08	31.95	93.55
	DConstrain	184.00	3.45	14.63	4.74	6.31
JSONSchemaBench	DINGO	182.42	350.97	1 224.94	36.86	118.83
	NFA	214.94	353.62	1 054.28	36.99	130.63
	DConstrain	163.09	3.60	264.38	5.03	31.35
ComplexFuncBench	DINGO	404.39	1 053.46	1 405.18	90.61	107.51
	NFA	409.39	1 053.28	1 405.17	121.60	139.51
	DConstrain	309.13	13.08	20.62	5.11	5.94

The three mechanisms remove different forms of redundancy. Deferring environment specialization gives the largest cold-compilation benefit: eager binding raises mean compilation latency to $14.61\times$ that of the full system. Local-state reuse avoids recompiling identical local transition logic. Token-effect grouping mainly reduces vocabulary-level work in downstream joint inference, and removing it raises mean solve latency to $6.81\times$ that of the full system. A pushdown interpreter also avoids finite-state expansion, so Appendix § 10.§ 1 further compares DConstrain with Direct-PDA-Opt, which interprets the parser at every reached configuration. Even with token grouping before interpretation, it is $6.43\times$ slower end to end on 300 BFCL cases, because it re-executes the shared transition logic for every configuration.

Analysis

Property order changes task accuracy. Schema-order is a substantive decoding restriction for DLMs. On the full 2,495-case BFCL pool in Table 2, allowing arbitrary property order raises DConstrain’s semantic accuracy from 72.71% to 81.60% for LLaDA2.2 and from 37.27% to 81.56% for DiffusionGemma: gains of 8.89 and 44.29 percentage points, respectively, with 100% schema validity throughout. Native-Opt accuracy changes by only −0.12 and +0.16 points under the corresponding prompt conditions. The much larger constrained-decoding gains indicate that fixing the field order excludes schema-valid outputs that the models prefer. These comparisons use the same full pool; the separately selected cohorts in Table 3 support within-order comparisons. The higher LLaDA2.2 TPS in the Any-order common panel reflects its easier case composition: the shared cohort contains 2,149 cases, compared with 2,448 under Schema-order.

Verification, sampling bias, and recovery. A verifier answers whether a proposed update leaves some legal completion. Weighted joint inference additionally accounts for the model probability mass of compatible continuations. For a fixed canvas graph, the sampling objective assigns each accepting token-labeled path $\pi$ probability proportional to $\prod_i p_i(v_i)$. An existential completion test supplies the support of this objective, but not the continuation masses needed to sample from it. Exact rejection of complete assignments from a fixed proposal samples that proposal conditioned on validity; local token acceptance, batch selection, and recovery introduce different update rules.

Consider an unambiguous two-position grammar accepting only $aa$ and $bb$, with $p_1(a)=p_2(a)=0.9$ and $p_1(b)=p_2(b)=0.1$. Weighted joint sampling selects $aa$ with probability $0.81/(0.81+0.01)=98.78\%$. A policy that samples the first token and commits any feasible choice selects $aa$ with probability 90%, because the second token is then forced. Every completed output is valid, yet the distributions differ. The missing factor is the probability mass of legal continuations, which a Boolean verifier replaces by an existence decision. The same distinction affects MAP decoding: selecting high-confidence feasible proposals does not jointly maximize the product of token probabilities.

Finite witness search adds another source of selection bias. LAVE tests model-sampled lookahead completions and uses cached-prefix recovery (Zhang et al., [37]). If a proposal $u$ has proposal probability $q(u)$ and witness-search success probability $a(u)$, its probability among accepted proposals is proportional to $q(u)a(u)$. Thus a feasible proposal can be rejected when its valid witnesses are missed, and acceptance depends on the lookahead distribution and search budget. EPIC uses confidence-based subset selection and shrinking before exact verification; on exhausting the rejection budget, it completes the output using a witness that is not sampled from the model distribution (Jin & Han, [14]). These policies favor different proposals and continuations from those selected by weighted joint inference.

Verification also pays for rejected work. Independent proposals can conflict across positions, so an unsuccessful check triggers resampling, a smaller batch, or recovery. Parallel batch verification reduces the number of sequential checks, but a failed batch still requires additional selection and validation. This cost depends on how often proposals are accepted, whereas automata-based inference resolves compatibility within the weighted graph. Native DLM refinement can revise temporarily incompatible assignments. Maintaining feasibility of committed updates restricts these denoising trajectories, and proposal filtering

and recovery further change which trajectories are followed. On LLaDA2.2’s Any-order common cohort, Native-Opt reaches 82.78% semantic accuracy, LAVE-Opt and EPIC-Opt reach 82.60% and 75.48%, and DConstrain reaches 83.15%. The verification-based methods obtain 100% schema validity on this cohort while losing semantic accuracy relative to Native-Opt.

Property order has opposite runtime effects. DINGO-Opt’s solve latency per forward rises from 32.45 to 74.18 ms for LLaDA2.2 and from 216.72 to 3195.39 ms for DiffusionGemma when arbitrary order is allowed (Table 6). Enumerating field histories enlarges the finite-state graph, increasing the transitions processed by Viterbi inference; Figure 3 and Appendix § 10.§ 2 show the associated state-space and solver costs. LAVE-Opt and EPIC-Opt show the opposite trend: LLaDA2.2 overhead falls from 240.9% to 139.7% and from 2917.6% to 1926.2%, respectively; DiffusionGemma shows the same direction. In our integrations, reusable schema-specific verification structures are prepared during cold compilation, and both orders use the same online verification pipeline. A broader accepted language admits more proposals and reduces repeated resampling and verification per committed token. TPF increases reflect this change: LAVE-Opt rises from 4.67 to 5.75 on LLaDA2.2, and EPIC-Opt from 3.19 to 7.51 on DiffusionGemma.

Efficient joint inference under arbitrary order. DConstrain makes arbitrary-order joint inference practical. Under Any-order, its overhead is 54.1% for LLaDA2.2 and 49.9% for DiffusionGemma on the common cohorts. It achieves the highest TPS among the evaluated constrained methods in every model–order setting and the highest Any-order semantic accuracy on the common cohorts, at 83.15% and 84.87%. On the full pool, it reaches 81.60% and 81.56% with complete coverage and 100% schema validity. The paired comparison in Table 6 shows 6.65× and 46.26× lower end-to-end latency than DINGO-Opt under Any-order. The following analyses connect these results to the compiled representation and its scaling with runtime context.

Factorized representation. Table 5 compares the stored representations. Finite-state compilation materializes context-expanded states and token-level transitions, whereas DConstrain stores the local RTN structure and symbolic transition programs. Its median recorded payload is 4.74–5.11 MB across the three datasets, compared with 36.86–90.61 MB for DINGO. The runtime experiments measure the cost of deferring work to warm compilation.

Scaling with property order and nesting depth. Figure 3 varies the two runtime-context dimensions: property order enlarges the parsing environment, and nesting enlarges the continuation stack. As either grows, DINGO-Opt increasingly hits the time or memory limit and fails all evaluated cases at depths 5–8, while DConstrain still compiles them, consistent with Table 1.

Conclusion

We presented DConstrain, a compiler for constrained decoding in diffusion language models. Finite-state compilers expand runtime contexts into states. For unordered properties, this blow-up is exponential even for context-free grammars, so existing exact decoders fix the property order. DConstrain instead compiles reusable context-parameterized transition programs, which keep the stack and the field history as runtime parameters and still give joint inference exact successors. Warm compilation and grammar propagation overlap the model forward pass, and token-effect grouping shrinks the graph while preserving the ungrouped graph’s Viterbi optimum and token-labeled path distribution. Together, these choices substantially improve compilation coverage and latency and reduce constrained-decoding overhead while preserving schema validity and task accuracy. They also make arbitrary property order practical, which further improves task accuracy over fixed-order constraints.

Additional Background and Theoretical Analysis

This appendix formalizes the parser interface used in § 3, establishes correctness of the compiler in § 4, establishes weighted inference preservation under token-effect grouping, and analyzes compilation and graph-construction costs.

Grammar Automata and Parser Configurations

Let $\mathcal{G}$ define an output language $\mathcal{L}_{\mathcal{G}}$. Finite-state constraints admit an automaton $\mathcal{M}_{\mathcal{G}} = (Q, \Sigma, \delta_{\mathrm{FA}}, q_0, F)$, with transitions $\delta_{\mathrm{FA}} : Q \times\Sigma\to2^Q$; a DFA has at most one successor per state–symbol pair, whereas an NFA may have several. For nested grammars, a pushdown representation augments local control with a runtime stack [7]. Its logical configuration is

where $s$ stores continuations and $e$ contains parsing variables. Guards, stack operations, and environment updates allow the same local transition logic to operate across different contexts.

Token-level transitions consume tokenizer tokens rather than individual grammar symbols [33, 7]. Let $T_{\mathcal{G}}^{\mathrm{raw}}(c, v)$ contain all successors after consuming $v$, including required stack, environment, and token-boundary operations. We use the normalized relation

where $N$ removes statically certified dead configurations, as defined below. Relations extend to frontiers by union over their configurations. For finite automata, $c$ reduces to a state $q$.

Diffusion Language Models

A partially resolved window $x^t \in(V \cup\{[\mathrm{MASK}]\})^H$ follows a fixed prefix $u$. At denoising iteration $t$, the model predicts distributions at all positions [27, 22]:

A decoding policy selects updates for the next iteration. Multiple unresolved positions permit joint grammar-constrained token selection [30, 5]. Let $V_i^t$ be the admitted tokens at position $i$; fixed positions can use singleton sets. All comparisons below use identical candidate sets, prefixes, protocols, and boundary conditions.

Correctness of Factorized Compilation

We expose $e = (d, \eta)$, where $d$ is container depth and $\eta$ is the choice environment, and write $c = (q, s, d, \eta)$. Execution states also retain input, cursor, and protocol phase. A token-complete state has finished all required boundary processing; an exhausted cursor alone is insufficient. We assume agreement only between corresponding primitive parser operations. All results use set semantics and concern completed computations; resource exhaustion is an error, not an empty result. Byte execution, compilation, and assembly are defined for every finite $w \in\mathbb{B}^*$ over the byte alphabet $\mathbb{B}$. Token compilation specializes $w = \operatorname{bytes}(v)$ with its initialization/finalization. Suffixes need not encode vocabulary tokens and retain the enclosing metadata and phase without fresh token initialization.

Static normalization. The abstract RTN soundly overapproximates concrete execution by relaxing environment guards while preserving call/return structure. For the set $\operatorname{Ret}(q)$ of finite abstract derivations returning from $q$’s current rule, define

Rule exits, including complete acceptance as a distinguished root exit, are productive terminals of distance zero. Consequently,

Min-plus relaxation starts with zero at terminals and infinity elsewhere. Each finite value has a derivation witness, and saturation covers every finite return, computing Eq. (19). Thus $D(q) = \infty$ excludes any concrete return; finite distance need not imply concrete feasibility. Define

Complete-output accepting configurations satisfy $P$ by their terminal distance and empty stack. Protocol steps obey the same abstract control rules and do not bypass required returns. Infinity is used only after the distance computation completes.

Proof. Every primitive step satisfies $c \to c' \land P(c') \Rightarrow P(c)$. For local and byte edges this follows from the distance inequalities. For calls, productivity of the successor implies finite distances for the callee and pushed return address. For returns, the source is an exit, and the popped address and remaining stack have finite distances. Consequently, every finite execution ending in a retained configuration contains only retained configurations. Such a path survives initial and intermediate normalization; the opposite inclusion follows from $N(X) \subseteq X$.

Write $\delta_N(X,w) = N(\delta_{\mathrm{raw}}(X,w))$. Unlike the raw relation, this semantics excludes token endpoints that are statically known never to complete the output.

Representations and admissibility. A parameterized bundle $B = (\mathbf{a},\mathbf{R},\eta_0)$ contains atoms $a_i = (q_i,d_i,\Omega_i)$ and their own stack relations $R_i$. Its logical interpretation is

Here $\Omega_i$ is an ordered program of partial choice operations. A public representation is admissible when its atom–stack–program associations are preserved; control, frames, operands, and cursor/protocol metadata are well formed in their binding scope; and its decoded frontier is normalized and in entry-closure form. Initialization creates aligned atoms and applies closure and $N$. The transfers below preserve these invariants; internal seeds carry their specified suspended phases.

Updates modify the current environment; a non-committing guard obeys

Each trial starts from the same current environment. Ordered composition satisfies $(U;V)(\eta) = V(U(\eta))$, including failure.

Source-indexed decoding. At each token query’s entry, label every source $c$ by its immutable origin $o=c$. Source selectors and stack transformations denote a relation $\mathcal{R}(\widehat{Y})$ between origins and current configurations. Define

Initially $\mathcal{R}=\{(c,c):c\in D(\widehat{X})\}$. Transfers keep the origin while changing the current configuration. Stack operations act pointwise on the selected atom’s input stack, not just its index. Merging unions these relations; shared suffixes compose them through the same intermediate configuration, never through a Cartesian product. Origins are proof annotations on existing selectors and stack maps, fixed within a query and reset at the next query.

Independent byte execution. The byte executor matches source atoms, appends call frames, partitions returns by their actual top frame, and appends choice operations in order. Its closure explores all prescribed zero-byte alternatives, deduplicates full current states with their source associations, and applies $N$ to each atom’s own stack relation. It does not invoke local-effect assembly.

Proof. Fix $o$. Primitive agreement gives the same byte, stack, and choice successors for each of its configurations, retaining $o$. Extracting an identical, equally bound prefix $U$ preserves $V_i(U(\eta_0))=(U;V_i)(\eta_0)$ and the origin associations. Merging identical current states unions their origins and shares their future relation. Newly attached origins receive those successors by propagation or reuse of that relation; saturation therefore covers every origin’s finite closure paths. Normalization acts per endpoint, so Lemma A.1 applies to each origin. Induction over bytes, followed by the same finalization argument, proves the equation. Transfers preserve scopes and phases; public exit closure and $N$ restore admissibility. $\square$

Local summaries and worklist propagation. For arbitrary $w\in\mathbb{B}^*$, cold compilation scans bytes and expands local closures using items $h=(a,\rho,\Delta,m,\Omega,\nu)$. Here $a$ includes control and execution phase, $\rho$ is the unmatched local return stack, $\Delta$ is net depth change, $m$ is its minimum prefix change including zero, and $\nu$ retains additional used metadata. Known calls and local returns modify $\rho$; choice operations append to $\Omega$. Initially $\rho=\Omega=\epsilon$ and $\Delta=m=0$. A depth change $\zeta$ updates

Every explicit alternative is explored. A return with empty $\rho$ emits a residual before accessing the unknown incoming stack. An ordinary summary $P=(q',\rho,\Delta,m,\Omega,\nu)$ binds as

Frames are appended bottom-to-top. Additional checks retain their primitive tests and operands; a depth-dependent check other than underflow also records its relative evaluation offset, or sufficient trace statistics, in keyed metadata $\nu$. Binding evaluates these tests and preserves the source selector and input-stack argument. Structural steps have no unrecorded choice effects; execution phase determines remaining closure.

The worklist keys by $(a,\rho,\Delta,\Omega,\nu)$, excluding only $m$. Each new key or strict increase of its best $m$ is enqueued. A popped item is skipped only when its $m$ is stale; otherwise all successors are explored. Ordinary and residual output tables also retain the largest $m$.

Residual resolution. Whole-token replay consumes the original token from its original source, without first applying the compiled prefix. Source-indexed byte simulation gives that source’s full normalized successor set; union with ordinary results already contained in that set does not change it or its origin.

Suffix restoration instead applies the prefix once, pops the actual source-stack return frame once, and continues in that caller with its retained environment, input, and protocol phase. The compiler’s initial residual set is empty; new records appear only after a byte is consumed, with cursor equal to its zero-based index plus one. Propagation preserves that cursor, and empty input generates only the identity effect. Hence compiler-generated residuals satisfy

Entry and caller closures handle zero-byte returns independently.

Token effects and transition preservation. Let $\mathcal{E}(q,v)$ be the token specialization of the byte-string compiler, including its prescribed initialization/finalization and residual modes. Define

where $\operatorname{Red}$ applies the proved duplicate and dominance reductions, and $\operatorname{Ser}$ completely encodes the resulting alternatives. It retains ordered operations, bindings, and all ordinary and residual token-boundary, initialization/finalization, and protocol information used by execution. Residuals additionally retain input, cursor, source bindings, and replay mode. Whole-token selectors retain token identity. Interned operands are compared within the same immutable registry and binding scope; hashing must resolve full key equality. Let $\Pi_q$ partition tokens by these keys.

Proof. The reductions preserve unions by the summary and worklist lemma. Structural equality identifies the same ordinary bindings, residual computations, and finalization for a fixed source. Their completed outcomes agree and retain that source. This is a sufficient equivalence test, not a complete semantic-equivalence procedure.

Consequently,

Proof. Fix the entry origin $c$. Source-indexed byte simulation proves replay; pointwise summary binding, worklist propagation, and suffix induction prove local-effect execution. Both preserve $c$ through closure, normalization, and finalization. Grouping reuses the same per-source relation. Public exit closure restores the established representation invariants. Union over sources gives the aggregate equation.

Window and complete-output languages

For normalized $C_0$, allowed sets $\mathbf{A}=(A_0,\ldots,A_{H-1})$, and $Y \in\{N,\mathrm{fac}\}$, define

Here $T^N=T_g$ and $T^{\mathrm{fac}}(c,v)=\mathcal{D}_c(\widehat{T}(\widehat{X}_i,v))$ for a representation of $C_i^{\mathrm{fac}}$. Stored edges use these source–successor pairs, not Cartesian products of frontiers; graph nodes retain their position. Let $\mathcal{L}_{H,B_H}^Y$ contain the token sequences labeling paths from $C_0$ to a configuration satisfying the common normalized boundary predicate $B_H$.

Proof. Induct on position. Equal frontiers and Eq. (33) give the same successors for each pair $(c,v)$, hence identical triples $(c,v,c')$ and next frontiers. Output admissibility permits the next query. Effect groups reconstruct these same edges when every admitted token label is retained. Equal labeled paths and the same boundary predicate give equal window languages.

For a fixed token sequence, normalization commutation also gives $X_H^N=N(X_H^{\mathrm{raw}})$. Thus raw-to-normalized boundary agreement holds whenever $B_H^{\mathrm{raw}}(X)=\overline{B}_H(N(X))$. This extra condition is unnecessary when comparing factorized execution directly with the normalized reference.

Let $\mathcal{L}_{\mathrm{complete}}^Y$ contain finite token sequences reaching complete-output acceptance under semantics $Y$.

Proof. Every complete accepting configuration satisfies $P$, so backward closure ensures that every raw accepting path survives normalization. Normalization only deletes alternatives, proving the reverse inclusion. The token theorem then establishes factorized agreement. The same argument preserves the existence of a finite legal completion, but not observations of dead threads.

These statements preserve logical transitions and token languages, not derivation multiplicities, arbitrary path weights, or resource-truncated results.

Weighted Inference under Token-Effect Grouping

Fix one denoising iteration and a finite layered window graph with initial configuration $c_0$, horizon $H$, terminal predicate $B_H$, and fixed nonnegative token weights $p_i(v)$. Forbidden tokens have zero weight. All comparisons use the same normalized, sourcewise transition relation $T_{\mathcal{G}}$ and count each logical edge $(i,c,v,c')$ once. Let $\Pi_q$ partition $\mathcal{V}$ and assume effect equivalence:

Positions, endpoints, and group membership are retained. An accepting path $\pi$ has weight $W(\pi)=\prod_{i=1}^{H}p_i(v_i)$; assume $Z=\sum_{\pi\ \mathrm{accepting}}W(\pi)>0$. The following equalities use exact arithmetic.

Define

For $\oplus\in\{+,\max\}$, let $r_i^{+}=M_i$ and $r_i^{\max}=m_i$. Disjoint group membership and Eq. (37) give

Both cases use multiplication to compose edge weights, with empty reductions equal to zero. Thus grouping preserves the entire sum-product or max-product transition operator, not only its support.

Proof. Equation (39) preserves every forward, backward, and interval message. Set $\beta_H=B_H$ and $\beta_{i-1}=A_i^{+}\beta_i$. Chain sampling selects a valid group edge and then a token using

Their product is $p_i(v)\beta_i(c')/\beta_{i-1}(c)$, exactly the expanded edge conditional. Multiplication along a path cancels the messages and gives $W(\pi)/Z$.

For tree inference, write $K_{\ell:r}=A_{\ell+1}^{+}\cdots A_r^{+}$. Sample the terminal state with probability $K_{0:H}(c_0,b)B_H(b)/Z$ and an interval midpoint by

At leaf $i$ with endpoints $a,b$, choose $G$ with probability $\frac{M_i(G)\mathbf{1}[b \in T_G(a,G)]}{A_i^+(a,b)}$, then restore $v$ with probability $\frac{p_i(v)}{M_i(G)}$. Associativity preserves the interval operators; cancellation of the interval and leaf normalizers again gives $W(\pi)/Z$. Only positive-mass events are sampled. Equality of full path distributions implies equality of all token marginals.

Proof. Their state-space transition matrix is

Equation (39) preserves this matrix under group-sum reduction. Thus all bottom-up interval messages, the root boundary distribution, and the conditional midpoint distributions are unchanged.

At a leaf with endpoints $c,c'$, selecting a group and restoring $v \in G$ gives

which is the same leaf token conditional. Only positive-mass events are sampled. Induction over the sampling tree therefore gives the same state-space joint distribution and hence the same output-token distribution. The identical interval operators and boundary factors also give the same partition function.

Proof. Equation (39) preserves every max-product message. For a fixed grouped state path,

Every token replacement is feasible by effect equivalence. Hence each optimal grouped path lifts to an optimal token path by choosing group maximizers, and every positive-weight expanded optimum is recovered this way. Retaining all ties preserves the full maximizing sequence set. A single argmax and backpointer return one optimum; identical selected outputs additionally require the same tie-breaking rule.

Parsing ambiguity and the probability measure. Let $n(y)$ be the number of accepting paths labeled by token sequence $y$ in the chosen token-level graph, and let $w(y)=\prod_i p_i(y_i)$. Summing path weights gives

The second distribution counts each legal sequence once. Cancelling positive $w(y)$ shows that the two distributions coincide if and only if $n(y)$ is constant on the positive-weight legal support; unambiguity is sufficient. A constant $n(y)=k$ gives the same normalized distribution but scales its partition function by $k$. For example, equal-weight sequences with path counts two and one have path probabilities $2/3$ and $1/3, rather than 1/2 each. Thus language equivalence alone does not establish sum-product equivalence across different parser representations. Grouping preserves the chosen graph’s measure, not an assumed absence of parsing ambiguity.

These results require the stated weighted conditionals; greedy selection by group mass is generally not equivalent. Extra token-dependent scores require corresponding weighted reductions and token-restoration rules. Distributional equality does not imply identical outputs under the same random seed or floating-point reduction order.

Complexity Analysis

We separate compilation and grammar propagation from model inference, token-probability processing, and joint inference.

Context expansion. Let $Q_{\mathrm{loc}}$ be the local grammar states, $g > 1$ the number of possible continuation-frame symbols, $d_{\max}$ the stack-depth bound, and $B$ the maximum number of remaining context assignments per local-state–stack pair. Then

The stack factor is $d_{\max} + 1$ for $g = 1$. The bound need not be attained. For bounded-depth brackets with $g$ types, however, each opening-only prefix has a distinct matching completion. A minimal complete DFA needs one state per stack plus a sink:

This is a worst-case DFA representation gap, not a universal runtime bound.

Unordered properties. We prove Proposition 3.2. Fix $k \ge1$ and distinct Unicode letters $a_1,\ldots,a_k$. Let $G_k$ be the object schema with properties $a_1,\ldots,a_k$, all required, no additional properties, and the value schema {"const":0} for every property. Let $L_k$ be the set of its serializations, and write $P_i$ for the pair "$a_i$:0".

DFA bound. For $S \subseteq\{1,\ldots,k\}$, let $u_S$ open the object and write the pairs $P_i$ with $i \in S$ in increasing order of $i$, separated by commas. When $\varnothing\ne S \ne\{1,\ldots,k\}$, $u_S$ also ends with a comma. Let $w_S$ write the remaining pairs in the same way and close the object, so that $u_Sw_S \in L_k$. Now take $S \ne T$ and assume without loss of generality that some $i \in S \setminus T$ exists. The string $u_Tw_S$ never writes $P_i$, because $i \notin T$ and $w_S$ writes only properties outside $S$. Since $a_i$ is required, $u_Tw_S \notin L_k$. The $2^k$ prefixes are therefore pairwise inequivalent, and by the Myhill–Nerode theorem [13] every DFA for $L_k$ has at least $2^k$ states.

Grammar bound. Let $G$ be a context-free grammar for $L_k$, and let $s$ be its size, i.e., the total length of its productions. Let $R_k$ be the regular language of strings that open an object, write exactly $k$ pairs from $\{P_1,\ldots,P_k\}$ separated by commas, and close the object. A DFA for $R_k$ has $O(k)$ states. Every property is required and $R_k$ allows exactly $k$ pairs, so $L_k \cap R_k$ contains exactly the strings that write each $P_i$ once, in some order. The product construction for intersecting a context-free language with a regular language [13] gives a grammar for $L_k \cap R_k$ whose size is polynomial in $s$ and $k$. Let $h$ be the homomorphism that keeps each $a_i$ and erases every other character. Replacing every terminal of a grammar by its image under $h$ does not enlarge the grammar, and $h(L_k \cap R_k)$ is the set of all permutations of $a_1,\ldots,a_k$. Every context-free grammar for this set has size $2^{\Omega(k)}$ [9]. Hence $\operatorname{poly}(s,k) \ge2^{\Omega(k)}$, and therefore $s = 2^{\Omega(k)}$.

Factorized representation. Under the parsing-environment factorization of § 4.1, the object needs local grammar states only for its delimiters, property names, separators, and values, so $O(k)$ of them suffice. The environment $\eta$ stores the set of properties already written, a $k$-bit value. Programs that complete a property name carry the guard “$a_i \notin\eta$” and the update “add $a_i$ to $\eta$”. The program that closes the object carries the guard “$\eta$ contains every required property”. All $2^k$ field histories share these programs.

Entry and instantiation counts. A dense context-expanded table has $S_{d_{\max}}|\mathcal{V}|$ entries; factorized compilation has at most $|Q_{\mathrm{loc}}||\mathcal{V}|$ local-state–token entries. These are counts, not constant-time operations. For reachable frontiers $C_{i-1}$, define

where $N_{\mathrm{query}} = \sum_i \sum_{c\in C_{i-1}}|\mathcal{V}_i^t|$. Repeated configurations are counted per position. With full-vocabulary candidates, the ungrouped count is $R_t|\mathcal{V}|$.

Construction cost. Let $T_{\mathrm{setup}}$ include shared schema lowering and static-distance analysis. Let $C(q,v)$ include a cold entry’s queue processing, improvement propagation, and effect/key construction. Let $W_j$ include a top-level instantiation’s binding, all residual descendants, closures, suffix compilation, and successor creation. For cold pairs $\mathcal{P}_{\mathrm{cold}} \subseteq Q_{\mathrm{loc}}\times\mathcal{V}$, actual top-level queries $|\mathcal{J}_{\mathrm{inst}}| \le N_{\mathrm{inst}}$, and additional indexing and label/graph work $A_t$,

Each shared construction is charged once; recursive work included in $W_j$ is not counted again. If $C(q,v)\le\tau_c$ and $W_j\le\tau_w$, then

Neither per-entry cost is assumed constant for arbitrary grammars. Grouping also does not remove the work needed to discover effects or emit individual token labels.

Scope. For an $L$-byte entry, if every depth prefix is at least $-\kappa L$, then $-\kappa L\le m\le0$ and each complete key admits at most $\kappa L+1$ retained values, including its first admission. This bounds re-expansion per key, not the number or size of keys. Similarly, residual progress bounds a recursive chain by $L$ strict decreases, not the total work of its branching tree. Local stacks and pending programs may still grow, $R_t$ may approach $HS_{d_{\max}}$, and $K$ may approach $|\mathcal{V}|$. Cold assets are reusable across requests with the same grammar and binding scope; graph reuse additionally requires compatible candidate sets and boundary/protocol conditions. The analysis therefore characterizes avoided replication without claiming an unconditional exponential decoding speedup.

Additional Experimental Details

This section provides additional implementation and evaluation settings for the experiments in § 5.

Implementation and Decoding Settings

Inference uses NVIDIA H20-3e GPUs with approximately 140 GiB of visible memory per device. Both models run in BF16 with model CUDA Graphs enabled. LLaDA2.2 (Bie et al., [4]) uses SGLang (Zheng et al., [38]) with tensor parallelism across four GPUs, while DiffusionGemma (DiffusionGemma Team et al., [6]) uses vLLM (Kwon et al., [16]) 0.28.0 with one GPU per model instance. DConstrain implements cold and warm compilation in C++ and joint inference in CUDA.

Cold-compilation experiments run on an Intel Xeon Platinum 8575C CPU. Each schema compilation is single-threaded, with up to 64 schemas compiled concurrently. Cold timing starts after tokenizer and service initialization and ends when the reusable compiled artifact is ready for online use. Warm compilation and model inference are excluded from cold-compilation time.

LLaDA2.2. The adaptive runtime comparison uses 32-token physical blocks, with the first block’s available positions determined by the prompt suffix. Generation is greedy with seed zero. MASK-to-token updates use a confidence threshold of 0.5, falling back to the highest-confidence MASK position when none qualifies. The token-to-token threshold is 0.0; DELETE and SPLIT are disabled. A block is committed after all MASK positions are filled and token assignments stabilize. Generation terminates at an accepted EOS or the 2,048-token output limit, with bounded update/refinement rounds; budget exhaustion is counted as failure.

DiffusionGemma. Generation uses 256-token canvases, seed zero, and the native entropy-bound sampler. The entropy budget is 0.1, and temperature decreases linearly from 0.8 to 0.4. Gumbel-max candidates are retained at entropy-selected positions while the remaining positions are re-noised, with native soft self-conditioning preserved. Generation uses at most 48 denoising iterations per canvas and terminates at EOS/EOT or the 2,048-token output limit.

Compilation and Evaluation Settings

The BFCL pool contains 2,495 cases, obtained by screening all required cases in BFCL and excluding cases whose schemas admit no valid instance. The JSONSchemaBench (JSB) pool contains all 5,754 training schemas, and the ComplexFuncBench (CFB) pool contains all 1,000 benchmark cases.

The main cold-compilation experiments and ablation study use the full corresponding pools. The main BFCL runtime tables report both all-attempted and common runtime-success cohorts, as defined below. Unless otherwise specified, other analyses and appendix experiments use fixed subsets of 300 BFCL cases and 300 JSB schemas, and the full 1,000-case CFB pool, as applicable. Table 6 uses cases successfully completed by both DINGO-Opt and DConstrain within the designated pool. Failed compilation cases are not replaced.

For cold compilation, the nominal timeout is 180 s per schema. Success rates include all attempted cases, while compilation latency statistics use each method’s successfully compiled cases. Reported speedups divide the baseline’s arithmetic mean latency by DConstrain’s over paired successful cases. Timeouts and failures affect success rates but are excluded from these latency ratios.

BFCL completion and quality cohorts. In Table 2, cold-stage admission, runtime completion, strict-schema validity, and official BFCL semantic accuracy all use the full denominator of 2,495. $N$ counts runtime completions regardless of schema validity; TPS and TPF use those $N$ cases. Native-Opt has no constraint-compilation stage. DConstrain completes all 2,495 cases with 100% cold admission, runtime completion, and strict-schema validity under both models and both order settings.

For Table 3, we define four independent cohorts, one for each combination of model and property-order condition, by intersecting the runtime-success sets of Native-Opt, LAVE-Opt, EPIC-Opt, and DConstrain. Schema-invalid completions are retained. The Schema-order and Any-order cohorts contain 1,874 and 2,201 cases for DiffusionGemma, and 2,448 and 2,149 cases for LLaDA2.2, respectively. DINGO-Opt completes all Schema-order cases; its validity, TPF, and semantic accuracy on the Schema-order common cohorts match DConstrain. Under Any-order, its cold-compilation success is 85.81% for DiffusionGemma and 71.30% for LLaDA2.2. Table 2 reports its Any-order outcomes over the full pool. Including DINGO-Opt would substantially reduce the common-success cohorts in Table 3, so Table 6 compares it with DConstrain on their paired successful cases. In Table 2, Schema-order DINGO-Opt has TPF 8.11 for DiffusionGemma and 6.86 for LLaDA2.2, semantic accuracy 37.19% and 72.63%, and TPS 23.13 and 101.32, respectively.

Schema validity is evaluated independently of solver acceptance and semantic correctness. The two main BFCL runtime tables report strict-schema validity and the official semantic evaluator separately; semantic accuracy is not filtered by schema validity. Other reported joint-correctness metrics additionally require schema validity. JSONSchemaBench validates outputs against the original schema. Timeouts and exhausted decoding budgets count as runtime failures; schema-invalid completions count against validity but remain completed runs.

Throughput accounting. For the main BFCL tables, TPF is the number of model non-stop token IDs divided by all generation forwards for the selected cases. CPU-generated completion text is excluded from model-token counts. The Overhead columns report inverse-TPS overhead over Native-Opt in the same model–order panel, $(\mathrm{TPS}_{\mathrm{Native\text{-}Opt}}/\mathrm{TPS}_{\mathrm{method}} - 1) \times100\%$. In Table 2 and the Schema-order panel of Table 3, DConstrain TPS subscripts give $\mathrm{TPS}_{\mathrm{DConstrain}}/\mathrm{TPS}_{\mathrm{DINGO\text{-}Opt}}$ in the same table and panel; its bold Overhead entries show the reduction factor $h_{\mathrm{DINGO}}/h_{\mathrm{DConstrain}}$, where $h = \mathrm{TPS}_{\mathrm{Native\text{-}Opt}}/\mathrm{TPS} - 1$. Schema and Any denote schema-order and arbitrary-order settings; for Native-Opt, they identify the prompt condition.

Runtime timing. End-to-end latency is measured by wall-clock time at the request level, while GPU joint-inference stages are measured with CUDA events. Warm compilation measures the request-local successor-construction work, which overlaps with model execution; these intervals are therefore not additive. Cold compilation and artifact loading are excluded from runtime latency. Runtime latency statistics in Table 6 are arithmetic means over the paired cases successfully completed by both compared methods.

Paired latency comparison. Table 6 reports BFCL and JSB latency on the cases successfully completed by both DINGO-Opt and DConstrain in each dataset–order setting. E2E is the mean request latency. Solve/forward is the mean joint-inference latency per generation forward. On BFCL under Any-order, DConstrain reduces end-to-end latency by 6.65× for LLaDA2.2 and 46.26× for DiffusionGemma, and reduces solve latency per forward by 26.40× and 108.54×, respectively.

Engineering Optimizations

We complement DConstrain’s compilation design with engineering optimizations that reduce execution overhead and graph-storage cost.

Native compilation pipeline. Cold and warm compilation execute in a native C++ pipeline, reducing interpreter overhead in grammar processing and transition instantiation. Reusable schema artifacts are stored in packed native arrays, avoiding per-edge Python objects and their allocation overhead.

Compact sparse graph storage. We store canvas-specific grammar graphs in compressed sparse row (CSR) format, using row offsets and contiguous edge arrays. This representation stores only existing transitions rather than allocating dense graph structures. CUDA joint-inference kernels consume the CSR representation directly, connecting grammar propagation with GPU execution.

DINGO-Opt adopts the same C++ pipeline and CSR representation while retaining finite-state compilation. Direct-PDA-Opt uses edge merging, shared token-membership storage, and grouped GPU reductions while interpreting reached parser configurations on demand, without compiling symbolic transition programs. Its + TG variant additionally applies conservative token grouping before interpretation (Appendix § 10.§ 1).

Asynchronous execution. Native CPU workers run warm compilation during the first forward pass of each canvas and grammar propagation during every forward pass. Neither stage reads the model scores. The scheduling interface supports both eager execution and model CUDA Graph replay. Data transfer and readiness tracking connect warm compilation to GPU joint inference, which begins when both graph data and model scores are available. Score-dependent operations therefore remain on the critical path. This overlap limits exposed warm-compilation latency, while workspace reuse reduces repeated setup costs. We measure end-to-end latency directly rather than summing overlapping components, and report compilation and exposed costs in § 5.1.

Additional Analyses of Constraint Semantics and Runtime

Warm Compilation Scaling and Runtime Overlap

DConstrain avoids materializing context-expanded token transitions during cold compilation, but exact joint inference still requires the runtime contexts that are reachable from the current decoding canvas. Warm compilation instantiates context-specific successors on demand from shared transition programs. This section examines whether the resulting deferred work becomes a runtime bottleneck as parsing-environment and stack complexity increase, and how this work is overlapped with model computation during execution.

Scaling with runtime-context complexity. Figure 4 complements the cold-compilation scaling analysis in Figure 3 by measuring the corresponding online cost. We consider the two sources of runtime-context growth targeted by the factorized representation. For arbitrary-order objects, increasing the number of parameter fields increases the number of possible parsing-environment configurations. For nested structures, increasing nesting depth increases the diversity of continuation-stack contexts that may be reached during grammar propagation.

On the CFB any-order sweep in Figure 4(a), median CPU warm-compilation time per 32-token block increases gradually with the maximum number of parameter fields per object. Even at the largest field counts, the median remains well below the corresponding mean model-forward time of 9.09 ms. Thus, supporting arbitrary schema-valid property order introduces additional online work, but the measured warm-compilation cost remains small relative to the model computation with which it can overlap.

Figure 4(b) and Figure 4(c) examine nesting depth on BFCL. As depth increases from four to eight, warm-compilation work increases, consistent with a larger set of reachable stack contexts. The increase is visible both in the total warm-compilation work accumulated within a request and in the mean cost of an individual warm-compilation call. At depth eight, the mean per-call CPU cost remains below the approximately 9 ms mean model-forward time, while end-to-end request latency remains comparatively stable across the depth sweep. Across the depth sweep, mean warm-compilation cost stays below the mean model-forward time, and end-to-end latency remains comparatively stable.

Warm compilation during asynchronous execution. The scaling experiments above characterize how online work changes with specific sources of context complexity. Figure 2 in the main text reports warm-compilation timings from actual asynchronous execution across the broader evaluation workloads. Native CPU workers run score-independent warm compilation concurrently with GPU model forward computation. Joint inference starts when both the graph and model scores are ready, so only warm compilation remaining at that point is exposed on the decoding critical path. The figure sorts the measured CPU warm-compilation times and shows the corresponding mean model-forward duration as a reference; the percentage annotations summarize the fraction of warm-compilation calls below that duration.

For LLaDA2.2 on CFB, arbitrary property order increases warm-compilation cost relative to schema order, as expected from the additional parsing-environment alternatives, while the distribution remains below the corresponding mean forward time over the plotted samples. On JSONSchemaBench, which contains substantially more heterogeneous schemas, the distribution has a longer tail: 97.17% of warm-compilation calls remain below the 8.90 ms mean model-forward duration, while the largest observed call reaches 34.61 ms.

The same pattern holds with the substantially larger 256-token canvases of DiffusionGemma. On BFCL and CFB with arbitrary property order, 99.47% and 94.20% of warm-compilation calls, respectively, are below the corresponding mean model-forward durations of 26.4 and 26.7 ms. On JSONSchemaBench, 99.3% are below the 25.64 ms mean forward duration, with a maximum observed warm-compilation time of 30.32 ms.

Implications for deferred instantiation. Together, Figure 4 and Figure 2 clarify the trade-off introduced by two-stage compilation. DConstrain shares compiled transition logic across the runtime contexts reached during grammar propagation. It performs context-specific instantiation only when the corresponding configurations become reachable. The resulting online work grows with runtime-context complexity, as expected, but remains modest relative to model-forward computation over the evaluated regimes and is overlapped with model execution by the asynchronous schedule. The request-level means in Table 6 account for this overlap directly.

Additional Experimental Results

These experiments complement the main runtime and compilation results in § 5. We examine direct pushdown interpretation, tree-parallelized automata inference, compiled representations, and compilation coverage.

Comparison with Direct Pushdown Interpretation

The ablations in § 5.2 vary reuse within DConstrain. Here we additionally evaluate a baseline that computes $(c,v) \mapsto T_G(c,v)$ by directly interpreting the pushdown parser at reached runtime configurations, without materializing a context-expanded DFA or compiling symbolic transition programs. This comparison tests whether on-demand interpretation alone can provide efficient successor construction.

Baseline variants. Direct-PDA-Opt already merges output edges with common destinations and uses shared token-membership storage and grouped GPU reductions. Direct-PDA-Opt + TG additionally groups tokens before interpretation: bytes are equivalent only when their raw transitions agree at every local RTN node, and token-trie paths with identical byte-class sequences are merged. It also reuses unions of token memberships. Calls, returns, and environment updates still execute in the interpreter, and all original token identities and model scores are retained. This conservative grouping uses no symbolic transition programs and differs from DConstrain’s local token-effect grouping.

Evaluation setting. We evaluate all variants on the same fixed set of 300 BFCL cases, with LLaDA2.2, BF16, tensor parallelism of four, batch size one, and 32-token blocks. All variants use the same name-first tool-call format, arbitrary parameter-field order, a nesting-depth limit of four, prompt, and MAP decoding. These controlled runs execute graph construction and model forward serially, with a fresh runtime per request. E2E spans the first prefill through runtime and parser cleanup after generation; cold preparation is excluded. Figure 5 uses the original paired runs. Figure 6 reruns DConstrain and the grouped baseline in the same service on the same 300 cases. All 300 cases produce identical output tokens across variants and satisfy their schemas.

Runtime comparison. Pre-interpretation grouping substantially reduces the direct interpreter’s online cost, but a large gap remains. In the grouped paired run, mean E2E is 878.10 ms for Direct-PDA-Opt + TG and 136.63 ms for DConstrain, a 6.43× speedup. The warm-compilation curves show that repeated runtime interpretation remains expensive even after conservative grouping. Together with the compiler ablations, these results support compiling and reusing transition programs as a contribution beyond simply avoiding DFA expansion.

Tree-Parallelized Automata Inference

DConstrain changes how the canvas-specific grammar graph is constructed while preserving the token-labeled successor relation consumed by downstream automata-based inference. It is therefore solver-agnostic rather than specialized to the Viterbi solver used in our main experiments. We verify this compatibility by applying both Viterbi inference and the inference algorithm of [5] directly to DConstrain graphs, using both sequential and tree-parallelized implementations.

We further examine whether tree parallelism can reduce the solver cost underlying Table 6. All four solver variants are evaluated on the same 300 BFCL cases using both DINGO and DConstrain graph representations. Table 7 reports results for two cases near the 25th and 95th percentiles of DINGO graph node count, denoted P25 and P95. The selected cases and inference objectives are matched across graph representations.

Graph	Method	P25 BFCL schema Time (ms) ↓	P25 BFCL schema Mem. (GiB) ↓	P95 BFCL schema Time (ms) ↓	P95 BFCL schema Mem. (GiB) ↓
Ours	Viterbi seq.	3.90	0.01	30.85	0.03
Ours	DANG seq.	4.70	0.01	48.97	0.09
Ours	Viterbi tree	30.80	1.14	7824.19	12.55
Ours	DANG tree	60.70	1.56	4344.17	12.30
DINGO	Viterbi seq.	39.80	0.01	425.08	0.08
DINGO	Viterbi tree	7.13	0.21	880.38	12.84
DINGO	DANG seq.	331.32	0.02	13536.26	0.09
DINGO	DANG tree	11.40	0.29	3577.13	17.63

We consider the log-depth tree construction proposed by [5] and apply the same reduction to MAP inference for a direct comparison with the Viterbi-style decoding used by DINGO ([30]). Let $L$ denote the decoding-window length, $S$ the automaton states, and $E$ the grammar-transition structure. Conventional Viterbi inference performs position-wise dynamic programming, where state scores at position $i$ depend on those at position $i - 1$, yielding a sequential dependency across the decoding window. Tree-based inference instead composes adjacent transition operators in a binary reduction tree, reducing the sequential depth from $O(L)$ to $O(\log L)$. For MAP inference, the same construction can be performed over the max-product semiring [12], preserving the Viterbi objective [32] while exposing tree-level parallelism.

This reduction trades sequential depth for substantially more computation and intermediate state. Under the state-space formulation, sequential message passing requires

work, whereas the tree construction requires

work while reducing the critical path to $O(\log L)$. Dang and Ermon characterize this trade-off as an $\lvert S\rvert$-fold increase in message-passing FLOPs in exchange for greater GPU parallelism. The memory cost can also increase substantially: each interval in the reduction tree materializes a state-to-state transition summary of size $O(|S|^{2})$. Retaining the summaries required by the subsequent top-down pass therefore requires $O(L|S|^{2})$ intermediate storage, compared with $O(L|S|)$ backpointer storage for conventional Viterbi reconstruction, or $O(|S|)$ score storage when reconstruction is unnecessary. This quadratic dependence on the automaton state space can become expensive for large structured-output graphs.

Table 7 shows that the benefit of tree parallelism depends strongly on graph size. On the P25 DINGO graph, tree-parallelized Viterbi reduces latency from 39.8 ms to 7.13 ms, a 5.58× speedup, but remains slower than sequential Viterbi on the DConstrain graph at 3.90 ms. On the P95 DINGO graph, tree-parallelized Viterbi instead increases latency from 425.08 ms to 880.38 ms, while sequential Viterbi on the DConstrain graph requires only 30.85 ms. Peak solver GPU memory on the DINGO graph increases from 0.01 GiB to 0.21 GiB at P25 and from 0.08 GiB to 12.84 GiB at P95, approximately 21× and 167×, respectively. Tree parallelism also increases both latency and memory for Viterbi on the DConstrain graph in these two cases. These measurements illustrate that reducing sequential depth does not guarantee lower solver cost: as the graph grows, the additional dense intermediate computation and storage can dominate the available parallelism.

Compiled Representations with DiffusionGemma

Table 8 complements the LLaDA2.2 results in Table 5. DConstrain’s median recorded memory footprint is 4.10 MB on BFCL, 4.23 MB on JSONSchemaBench, and 4.57 MB on ComplexFuncBench; the corresponding P95 values are 5.39 MB, 28.41 MB, and 5.09 MB. State counts use the three-method successful intersection, while edge and memory quantiles use each method’s successful cases.

To complement the any-order compilation results in Table 1, Table 9 compares the compiled representations produced by DINGO-Opt and DConstrain under the native tool-call protocols. All representation statistics are computed on the same successful intersection within each setting. Because DConstrain succeeds on every evaluated case, the intersection size $n$ is determined by the finite-state baseline’s compilation coverage. The results show that arbitrary property order leads to very large context-expanded transition structures for DINGO-Opt, whereas DConstrain retains compact local RTN nodes and symbolic transitions.

Cold Compilation with Additional Tokenizers

To evaluate whether DConstrain’s compilation behavior depends on the two tokenizers used in the main experiments, we additionally compile the same structured-output workloads with the Dream 7B and LLaDA 8B tokenizers. These experiments evaluate compilation only and do not run model inference. All settings use arbitrary property order and the same recursive structured-output grammar configuration.

Table 10 shows that DConstrain retains high compilation coverage and sub-second median cold-compilation latency across both additional tokenizers. BFCL and ComplexFuncBench compile successfully in all cases, while JSONSchemaBench succeeds on 281 of 300 evaluated schemas. The identical local-state counts across tokenizers reflect the tokenizer-independent pushdown grammar structure, while token-dependent symbolic transitions, payload size, and compilation latency vary with tokenization. These results indicate that the factorized compilation design is not specific to the LLaDA2.2 or DiffusionGemma tokenizers used in the main experiments.

Tokenizer	Dataset	Success	States			Edges ($10^3$)
			Mean	P50	P95	P50	P95	P50	P95
Dream 7B	BFCL	300/300	416.25	0.92	4.24	2.77	4.08	0.36	1.05
	JSONSchemaBench	281/300	616.65	1.03	157.53	2.78	24.71	0.38	12.85
	ComplexFuncBench	1000/1000	770.05	2.83	4.39	3.22	3.69	0.67	0.97
LLaDA 8B	BFCL	300/300	416.25	0.85	4.00	2.09	3.03	0.31	0.81
	JSONSchemaBench	281/300	616.65	0.93	138.53	2.08	14.90	0.33	10.78
	ComplexFuncBench	1000/1000	770.05	2.63	4.06	2.45	2.80	0.60	0.84

Failure Analysis on JSONSchemaBench

We further analyze the remaining DConstrain compilation failures on JSONSchemaBench with the LLaDA2.2 tokenizer. Table 11 categorizes all 1,072 failed schemas out of 5,754, corresponding to an 18.6% failure rate and an 81.4% success rate. Most failures arise from unsupported schema semantics rather than compiler execution failures: semantic-coverage limitations account for 789 cases (13.7% of the full benchmark and 73.6% of all failures). Resource limits account for another 274 cases (4.8% of the benchmark), primarily RSS exhaustion and the 180 s compilation timeout. Only nine cases (0.2%) are attributable to known implementation errors or unresolved compiler behavior.

Failure cause	Cases	Full set (%)
Schema coverage and semantic limitations
Unsupported keyword or keyword combination	285	5.0
oneOf branch exclusivity not provable	178	3.1
General allOf intersection unsupported	127	2.2
Nested resource scopes (id/$id) unsupported | 127 | 2.2
Nested schema-dialect switching unsupported	28	0.5
Dynamic-property constraints conflict with empty-object subset	38	0.7
Regular expression outside supported dialect	4	0.1
Tuple-style items unsupported	1	0.0
$ref and outer-type intersection not provable | 1 | 0.0
Resource and construction limits
State/transition/closure or pattern-size budget exceeded	68	1.2
RSS limit exceeded	134	2.3
Compilation timeout	72	1.3
Implementation and unresolved failures
_deduplicate_json_values implementation error	4	0.1
Duplicate enum values rejected	3	0.1
Compiled language unexpectedly empty	2	0.0
Total failures	1,072	18.6

The dominant failure modes therefore reflect the current supported schema fragment rather than failures of the factorized compilation mechanism itself. In particular, oneOf/allOf reasoning and nested resource semantics account for a substantial fraction of unsupported cases. Resource failures form the second-largest category, showing that although DConstrain substantially reduces context expansion, sufficiently complex schemas can still exceed finite construction or memory budgets.

Localizing frontend coverage limitations. To separate frontend coverage from factorized execution, we replayed the 178 oneOf branch-disjointness rejections and 127 general allOf rejections in Table 11 using the archived frontend from the reported experiment. All 305 rejections were reproduced by the schema-to-parser frontend alone, without invoking the factorized token compiler. These failures therefore precede factorized execution; their localization does not establish that downstream compilation would succeed after extending the frontend.

Frontend acceptance versus semantic preservation. We examined the same 305 original schemas using XGrammar [7]. With strict_mode=True, XGrammar 0.2.8 returned grammars for 298 schemas. A bounded search identified 124 distinct schemas for which the native matcher accepted a complete JSON text that violated the original schema. We independently replayed all 124 counterexamples and confirmed their invalidity with jsonschema 4.26.0; 104 were also confirmed by fastjsonschema 2.22.2. We additionally found valid instances for 86 schemas, establishing their satisfiability. Replaying the same invalid texts in XGrammar 0.1.27 reproduced violations for 123 schemas. Table 12 summarizes these results.

Historical rejection	Cases	Compiled XG 0.2.8	Counterexamples XG 0.2.8	Same witnesses XG 0.1.27
oneOf disjointness	178	175	43	42
General allOf	127	123	81	81
Total	305	298	124	123

The audit used an empty tokenizer and the native complete-string matching interface, requiring an accepting terminal state. It therefore tests membership in the compiled character language, rather than compilation against the LLaDA2.2 vocabulary or the likelihood of generating these texts during model inference. Validation followed each schema’s declared dialect, defaulting to Draft 2020-12 when unspecified. Optional format assertions and network reference retrieval were disabled.

For example, JSB schema o41599 specifies oneOf over integer, string, number, boolean, and null. Both tested XGrammar versions accept 0, which satisfies both the integer and number branches and thus violates the exactly-one requirement. Similarly, schema o4455 explicitly requires an object and contains a multi-branch allOf, yet both matchers accept 0. Both examples were confirmed by both validators.

Scope of the conclusions. Frontend acceptance alone is insufficient evidence that the original schema constraints are preserved. This targeted audit does not estimate overall semantic accuracy, establish DConstrain’s semantic correctness on all accepted schemas, or imply that every rejected schema is intrinsically difficult. We distinguish execution correctness relative to supported reference-parser semantics from frontend coverage and resource-bounded construction. Incomplete coverage, resource failures, and implementation issues remain limitations of the current system.

Limitations. DConstrain substantially reduces the cost of nested constraints during cold compilation by retaining a symbolic RTN representation rather than expanding stack contexts into finite states, and this representation can in principle express context-free structure. However, factorization does not eliminate the worst-case complexity of joint inference. During warm compilation, uncertainty over unresolved token choices can propagate across the decoding canvas and induce a rapidly growing set of reachable runtime contexts; in the worst case, this expansion can still be exponential in nesting depth or other sources of branching. DConstrain therefore extends the practical nesting depth substantially relative to finite-state baselines, but it does not provide unbounded or uniformly efficient compilation for arbitrary deeply nested grammars.