acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Diffusion language models (DLMs) enable parallel token generation, but structured-output constraints are difficult to enforce because token choices at unresolved positions can depend on one another. Automata-based DLM constrained decoding resolves this interdependence through joint inference, which requires exact token-labeled successors for many hypothetical parser configurations rather than validity information for a single realized prefix. Existing finite-state pipelines bind runtime parsing contexts into explicit states and materialize vocabulary-level transitions, duplicating reusable grammar logic across contexts. We present DConstrain, which instead compiles context-parameterized transition programs: token consumption is specialized to local grammar states and tokenizer tokens, while the runtime stack and parsing environment remain unbound. Warm compilation executes these reusable programs only for reached configurations, recovering the exact successors required by DLM joint inference. Token-effect grouping further shares successor construction across equivalent tokens. On BFCL with LLaDA2.2, DConstrain compiles 100% of schemas under arbitrary property order versus 71.3% for an optimized finite-state baseline, with a paired cold-compilation speedup. It also reduces constrained-decoding overhead by while preserving 100% schema validity and matched task accuracy.

Primary area:
generative models
Keywords:
diffusion language models, constrained decoding, grammar compilation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_mBc7OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes DConstrain, a pushdown automaton algorithm for constrained decoding with diffusion language models (DLMs), assuming joint inference over a block of masked tokens. Instead of compiling the full DFA over the vocabulary, it compiles per-(local grammar state, token) programs that leave the parser stack and environment unbound (cold compilation, Section 4.1), and executes them only for configurations reached at decode time (warm compilation, Section 4.2), and groups tokens with identical transitions (token-effect grouping, Section 4.3). It reports 4−10×4-10\times faster cold compilation than an optimized DINGO, full coverage under arbitrary property order, and lower decoding overhead on BFCL, JSONSchemaBench and ComplexFuncBench with LLaDA2.2 and DiffusionGemma.

Critical strengths
  • Addresses a real failure of DFA-based methods (state explosion with nesting and any-order objects); coverage results are convincing (Table 1, Figure 3) even though code is not uploaded with the submission.
  • Integrated into SGLang and vLLM; the baseline was re-implemented (DINGO-Opt) for fair comparisons.
Critical weaknesses
  1. Limited novelty in LLM constrained decoding. The design of DConstrain closely follows existing PDA-based constrained decoding engines. Online compilation of reached states is a classic lazy-compilation approach, and grouping tokens is standard vocabulary compression. This is a reasonable engineering contribution, but the paper should state the relationship explicitly instead of introducing uncommon terminology ("successor-construction interface," "pushdown factorization," "warm compilation") for known ideas.

  2. Missing baselines in main content. Several comparisons are relegated to the Appendix without proper justification (LAVE, Constrained Diffusion, EPIC, Direct-PDA-Opt), and some controls are missing.

    • Beating a DFA on nested, any-order JSON is expected. The fair comparison is an existing PDA engine such as XGrammar used to enumerate successors per reached configuration, which is not evaluated. The only PDA baseline is the authors' own Direct-PDA-Opt in Appendix D.1.
    • Both methods produce the same logical graph (Theorem. A.7), so the solve-time gains likely come largely from token grouping (Table 3), which applies equally to a DFA. A DINGO-Opt + token grouping control is needed to attribute the gains to the compilation design. Similarly, fixed-order decoding in the model template's order should be reported to isolate the any-order accuracy gain on DiffusionGemma.
    • Very critical: Constrained Diffusion (Appendix D.3, Table 7, ICLR 2026) is an important baseline that enforces context-free constraints in DLMs, and it handles general CFGs (C++, JSON, SMILES). It should be included in the main content alongside DINGO.
  3. Not full compatibility with DLM decoding . The layered graph assumes a fixed set of positions per window. LLaDA2.2's DELETE and SPLIT editing operations are disabled in all experiments (Appendix B.1), so compatibility with edit-based DLMs is unestablished and should be stated as a limitation. The paper should also clarify how re-masked or revised tokens are handled (DiffusionGemma re-noising), whether graphs are rebuilt each step, and what happens when early-committed tokens to the right make the window infeasible. Static normalization does not remove all dead configurations (Eq. 12–14), and the "terminal acceptance or continuation condition" at window boundaries is never specified.

  4. Insufficient benchmarks. Only JSON Schema is evaluated, despite the general grammar framing: BFCL and ComplexFuncBench tool declarations are JSON Schema and are decoded in a JSON tool-call format. The limitations section concedes the representation only "can in principle express context-free structure", whereas Constrained Diffusion already evaluates general CFGs such as C++. Moreover, all experiments impose a nesting-depth bound (4 in the main results, 8 in Appendix D.5), under which the constraint is regular, so CFG support is claimed but not demonstrated, and it is unclear whether unbounded recursion is supported.

  5. Experimental rigor.

    • Code is not provided with the submission, so the results cannot be reproduced.
    • Single greedy seed and no variance; on 2,495 cases the 95% interval is roughly ±1.6 points, so LLaDA2.2 differences of ~1–2 points are not clearly significant.
    • Batch size is 1 in the controlled runs and unstated elsewhere, and no throughput is reported. Under batched serving, the CPU/GPU overlap argument (Figure 2) may not hold.
    • Table 2 omits paired case counts and leaves the any-order LLaDA2.2 DINGO-Opt E2E entry blank.
    • Table 7 reports 6.3–36.3% schema validity and 9–47 s latency for Constrained Diffusion, whereas the original paper reports 100% syntactic correctness on JSON Schema with completion for all four DLMs it tests, including LLaDA 8B (albeit on a different dataset and metric). The paper does not state whether completion was enabled, the token/time budgets, how JSON Schema was translated into a CFG, or task accuracy.
    • The "NFA" baseline in Tables 1 and 4 is introduced only as "an NFA adaptation" (Section 5) and is never described.
  6. Presentation and clarity (very critical). The paper is hard to follow, much more than its baselines (DINGO, Constrained Diffusion, LAVE). Some complexity is natural when moving from DFAs to PDA, but most of the difficulty comes from presentation choices:

    • I have main concerns regarding the terminology inflation in this paper, which might be obscuring the actual contribution. There are many renamed terms that correspond to familiar concepts: the "successor-construction interface" is a standard transition function; the "canvas-specific grammar graph" is DINGO's decoding with dynamic programming; and "token-effect grouping" is vocabulary compression
    • Core objects are never formally defined: the RTN, the program instructions, Exec, Canon, residuals, the normalization N and the candidate sets Vit\mathcal{V}_i^t.
    • There is no pseudocode anywhere in the paper (32 pages), and no concrete example of a compiled program for even a small schema. Section 4 describes the method only in prose and equations at a high level of abstraction. Figure 1 is overloaded and hard to follow. It combines the baseline, cold/warm compilation, token grouping and inference in one dense schematic and does not stand on its own.
    • The decoding objective is described only verbally ("a highest-weight admissible path"); DINGO and relevant work states it explicitly.
    • The paper repeats the same high-level description of DConstrain instead of progressively introducing it. The same pipeline summary appears in the abstract, introduction, contributions, opening of Section 4 and Figure 1 caption with the same jargon, while concrete details are deferred.

I would encourage the authors to restructure Sections 3-4 following previous work: state the objective explicitly, define all objects before use, give pseudocode for cold compilation, warm compilation and grouped inference, and walk through a small schema showing the compiled programs and resulting successors.

Questions for authors
  1. Can DConstrain support LLaDA2.2's DELETE/SPLIT operations? How are re-masked or revised tokens and window-boundary completability handled?
  2. How is Vit\mathcal{V}_i^t chosen? What fraction of schemas need depth > 4?
  3. What are throughput and latency under realistic batch sizes?
  4. What is the precise terminal acceptance / continuation condition at window boundaries?
  5. What exactly is the NFA baseline in Tables 1 and 4? How is it constructed, why is it omitted from the any-order rows, and why does it have more states than the DFA?
  6. How was Constrained Diffusion configured in Table 7 (completion enabled or not, token/time budgets, JSON-Schema-to-CFG translation)? Why does it reach only 6–36% validity when the original paper reports 100% on JSON Schema? What is its task accuracy?
17 comments
AuthorsOpenReview ↗

Response to Reviewer mBc7

Response to W1/W3: Novelty Beyond PDA and Lazy Compilation (1/3)

How does CPTP differ from standard PDA engines and lazy compilation, and is Direct-PDA-Opt a sufficient PDA comparison?

We thank the reviewer for raising this important distinction. Our contribution is not the use of PDA or lazy state expansion, but a different compilation and reuse abstraction: Context-Parameterized Transition Programs (CPTP). Rather than compiling transitions for concrete parser configurations, CPTP compiles reusable transition logic that can be instantiated across different stack and environment contexts.

For DLM joint inference, the solver requires an explicit constraint graph covering the reachable configurations within a decoding window. Eager PDA expansion incurs finite-state materialization costs, while lazy PDA expansion constructs only reachable configurations. However, lazy expansion does not eliminate the repeated structural computation across different parser contexts. Even with transition caching, an H=32 window may require constructing numerous configurations with different stacks or environments that share the same underlying transition logic.

CPTP addresses this bottleneck by changing what is compiled and reused, rather than merely when configurations are expanded. It compiles stack operations, environment guards/updates, and residual continuations into reusable programs, separating shared structural expansion from context-specific environment application.

To establish that these benefits extend beyond a direct PDA interpreter, we conduct two additional controlled comparisons against optimized lazy PDA implementations, including a mechanism-transfer experiment that isolates CPTP's structural reuse.

Comparison with optimized lazy PDA.

Our Direct-PDA-Opt baseline already incorporates token-effect grouping (TG), edge merging, shared token memberships, and grouped GPU reductions. On matched BFCL300, it produces identical output tokens but requires 878.10 ms/request, compared with 136.63 ms for DConstrain (6.43× faster).

We further compare against stronger lazy PDA implementations using LLaDA2.2, BFCL300, TP4, batch size 1, H=32, and the same full FP32 MAP solver. Under schema order, the lazy PDA directly interprets transitions with TG and transition caching. Under any order, the symbolic lazy PDA additionally precompiles symbolic guard/effect token programs while retaining graph construction over concrete parser configurations.

Field OrderMethodCold Preparation (ms/schema)Construction + Packing (ms/block)Hot E2E (ms/request)
SchemaLazy-PDA + TG88.04345.847229.347
SchemaOur CPTP Stack Backend114.7310.532121.341
AnySymbolic Lazy PDA + TG110.66389.563367.789
AnyOur CPTP Stack Backend116.9366.487132.582

CPTP accelerates graph construction and packing by 86.18× under schema order and 13.81× under any order, translating into 1.89× and 2.77× faster end-to-end inference, respectively. All 300 paired outputs and MAP-solve counts match.

Importantly, these improvements arise despite comparable or slightly higher cold preparation costs for CPTP. The dominant advantage comes from avoiding repeated structural graph construction at runtime, rather than shifting computation into more expensive preprocessing. Moreover, the symbolic lazy PDA already incorporates token-effect grouping, symbolic token precompilation, and caching. Its remaining construction overhead demonstrates that these optimizations alone do not eliminate the redundancy across distinct parser contexts.

Response to W1/W3: Novelty Beyond PDA and Lazy Compilation (2/3)

Mechanism transfer into the same symbolic lazy PDA.

To further isolate the source of the improvement, we directly transplant shared structural expansion, batched environment processing, and range-based output into the symbolic lazy PDA, without replacing its underlying lazy expansion framework.

Both symbolic implementations retain byte-identical cold token programs, identical token-effect grouping, and the same membership-cache policy. This controlled comparison isolates the benefits of CPTP's structural reuse from token grouping, symbolic token compilation, and the choice of eager versus lazy expansion.

Any-Order MethodCold Preparation (ms/schema)Construction + Packing (ms/block)Hot E2E (ms/request)
Original Symbolic PDA + Caching109.32388.239363.902
Symbolic PDA + Our CPTP112.2658.079134.411
Our CPTP Stack Backend138.9903.451125.453

Introducing CPTP's structural reuse into the same symbolic lazy PDA reduces construction and packing time by 10.92× and improves end-to-end latency by 2.71×, without changing its cold token programs, token grouping, or membership caching. All three methods produce identical outputs and MAP-solve counts on 300 cases.

Most importantly, the enhanced symbolic lazy PDA approaches the performance of our dedicated CPTP backend (134.41 vs. 125.45 ms/request), recovering most of the performance advantage without replacing the lazy PDA framework itself. This demonstrates that the central benefit is transferable structural reuse, rather than a particular parser backend or an optimized implementation of lazy expansion.

Together, these experiments establish three conclusions. First, the improvement is not explained by replacing a naive PDA interpreter, as it persists against optimized lazy and symbolic PDA baselines. Second, it is not attributable solely to token-effect grouping, transition caching, or symbolic token precompilation, since these mechanisms are already present in the controlled baselines. Third, transplanting CPTP's reuse mechanisms into the same symbolic lazy PDA recovers most of the end-to-end performance advantage while preserving identical inference results. The contribution lies in the representation and reuse of context-parameterized transition logic, which is orthogonal to eager or lazy PDA expansion and directly addresses the repeated graph-construction costs of DLM joint inference.

W3 Existing-PDA Control: XGrammar

How does DConstrain compare with an existing PDA engine such as XGrammar used to enumerate successors per reached configuration?

We emphasize that adapting an autoregressive PDA engine to DLM joint inference is not a prerequisite for establishing the novelty or effectiveness of CPTP. Our preceding controlled experiments already demonstrate the efficiency of our PDA-based construction against Direct-PDA-Opt, optimized lazy PDA, and symbolic lazy PDA baselines. These comparisons further show that directly transferring AR-style lazy PDA expansion to DLM joint inference does not eliminate the substantial structural redundancy in multi-step constraint graph construction. The mechanism-transfer experiment additionally isolates the benefit of CPTP's structural reuse.

Response to W1/W3 Novelty Beyond PDA and Lazy Compilation (3/3)

XGrammar is primarily designed for autoregressive token masking, rather than explicit multi-step successor enumeration over numerous hypothetical parser configurations. Its native interface is therefore not directly suited to DLM joint inference, and adapting it requires substantial engineering effort beyond its intended use.

Nevertheless, we implemented an additional XGrammar comparison to directly address the reviewer's concern. We developed a successor adapter exposing parser-state keys and a C++ enumeration bridge while retaining XGrammar's native parsing and masking. Due to the substantial integration complexity and repeated timeouts on more demanding cases, we conducted an exploratory evaluation on a subset of BFCL instances, as reported below. Both approaches use the same XGrammar grammar, full vocabulary, H=32, and CPU solver. Reported times cover the entire preparation process through solver readiness, including preprocessing, averaged over two runs.

BFCL indexOur compiler + XGrammar frontend (s)XGrammar adapter: per-token Fork (s)
00.0620.080
10.7073.807
21.41410.496
40.7982.481
100.8045.441
242.03027.211
382.808>30
433.873>30
893.678>30
2990.98116.741
Mean over seven jointly completed cases0.9719.465

All 14 completed trial pairs have identical solver outputs. Mean preparation over seven jointly completed cases is 0.971 s versus 9.465 s (9.75×). Adapter cases 38, 43 and 89 exceed 30 seconds in both repetitions and are excluded from that paired ratio.

With AcceptToken/Rollback, forking only new successors, mean graph-construction times on empty-prefix cases 0, 1 and 2 are 0.023, 1.578 and 3.984 s; case 89 exceeds 12 s in all three trials.

W1 Local Token Grouping versus Global Classes

What distinguishes local token-effect grouping from standard vocabulary compression?

Section 4.3 groups tokens by canonical effects at local compiled program points, including stack actions, environment guards/updates and residual continuations. These groups share successor construction across concrete contexts; their scope differs from a grammar-wide equivalence partition.

Tokens such as alpha and beta can have identical effects inside a string but differ at a fixed-order field-name position. A grammar-wide partition retains that distinction everywhere; a local group merges them where effects coincide. A group remains reusable across concrete environments.

Using CFGzip's official Python global classes, we compare global representatives with local grouping under the same CPTP backend, tokenizer, H=32 and template settings, without canvas-graph caching.

Fixed-Order FieldsGrouped Edges: Global → LocalConstruction Time (ms): Global → LocalSpeedup
2562 → 3590.0371 → 0.03281.13×
41,283 → 7460.0682 → 0.05841.17×
82,871 → 1,5180.1363 → 0.09971.37×
164,256 → 1,9320.1686 → 0.11201.51×

At 16 fields, local grouping reduces grouped edges by 54.6%. Across all ten grammars, weighted-MAP and sum-product checks agree; local grouping is faster in five. The grouping-boundary ablation preserves token effects and reduces emission/template records, with unchanged byte-level compilation work.

For Viterbi inference, a group takes the maximum member-token score and restores an attaining token. Sum-product uses the sum of member weights with weighted token restoration. Appendix A.4 proves that both operators preserve the corresponding ungrouped token-level inference, including the optimal score and token-labeled path distribution.

Thus TG combines local compiled effects with exact weighted inference. The mechanism-transfer experiment in part 2 separately isolates construction benefits while holding grouping and cold programs fixed.

Reviewer_YMtDOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

DConstrain accelerates grammar-constrained decoding for diffusion language models by compiling reusable token-transition programs while leaving parser stacks and environments as runtime parameters. It instantiates reachable successors on demand and groups tokens with identical transition effects. The paper establishes transition preservation and weighted-inference equivalence relative to the same underlying graph. Experiments on BFCL, JSONSchemaBench, and ComplexFuncBench demonstrate improved compilation coverage, lower compilation and decoding costs, and preserved validity and task accuracy on evaluated cases.

Critical strengths
  • A well-motivated compiler abstraction with practical value. Separating reusable grammar–token behavior from runtime stack and field-history context directly addresses redundant finite-state expansion. The correctness arguments carefully preserve source–successor associations and handle context-dependent residual execution, supporting the central design.

  • Substantial gains supported by meaningful controls. On BFCL with LLaDA2.2 and arbitrary property order, compilation coverage increases from 71.3% to 100%, with a 9.43× speedup on paired successful cases. The optimized DINGO baseline, component ablations, and 6.43× runtime advantage over grouped direct pushdown interpretation strengthen the evidence that the benefits extend beyond implementation-language improvements (Table 1; Appendix D.1).

Critical weaknesses
  • The evaluated runtime graph construction is underspecified. The guarantees depend on candidate-token sets and terminal/continuation conditions, but the experimental settings do not clearly identify the actual choices, any candidate pruning, or numerical graph/memory limits. These choices determine both reachable graph size and the scope of exact inference, making the reported warm-compilation efficiency difficult to reproduce and assess.

  • The verification-based comparisons need stronger diagnostic support. Table 7 reports very low validity for some baselines, but does not provide method-specific rejection budgets, recovery settings, or a failure breakdown. This matters particularly because EPIC includes witness-based recovery. Appendix D.3 appropriately acknowledges several possible failure causes, but does not determine which explain the measured results. Consequently, the broader superiority claims are less convincing than the controlled compiler comparisons.

Questions for authors

These are clarification requests about the reported experiments:

  1. What candidate-token sets and block-end acceptance/continuation predicates were used in Table 2? Was the full vocabulary considered at every unresolved position, and what pruning and resource limits were applied?
  2. For Table 7, what schema-to-grammar frontends, rejection budgets, timeouts, and recovery settings were used? Can failures be separated into schema-translation errors, invalid completed outputs, and budget exhaustion?
8 comments
AuthorsOpenReview ↗

Response to Reviewer YMtD

Response to W1/Q1: Candidate Domains, Window Boundaries, and Resource Limits

Which candidate tokens, window-boundary conditions, and resource limits were used in the runtime comparisons?

We thank the reviewer for these detailed reproducibility questions. To clarify our experimental setup, we provide the exact candidate-token domains, window-boundary conditions, and resource limits used in our runtime comparisons. Both DConstrain and DINGO use FP32 maximum a posteriori (MAP) inference under identical logits, candidate masks, initial parser configurations, decoding horizons, and endpoint conditions, ensuring a controlled comparison.

Candidate domains. Fixed positions admit only their current token, while editable positions use the full configured output-token domain without top-k, top-p, or beam pruning:

  • LLaDA2.2: 157,147 admitted IDs out of 157,184.
  • DiffusionGemma: 262,123 out of 262,144 in plain JSON mode; 262,126 with native tool controls; 262,128 with the channel header.

Exclusions remove input/masking/editing controls, unused slots, and interface-inapplicable protocol/multimodal markers. End-of-sequence/end-of-turn (EOS/EOT) controls remain grammar-governed. commitment thresholds select positions only. Prefixes remain fixed; LLaDA opens positions selected for editing, while Gemma permits active-canvas re-noising. Token grouping preserves the MAP optimum.

Termination. Let AA denote the admitted domain, Reach⁡(c,z)\operatorname{Reach}(c,z) the configurations reachable after sequence zz, and T\mathcal T the terminal/padding states reached after grammar acceptance and a permitted stop:

\mathbf1[\exists z\in A^*: \operatorname{Reach}(c,z)\cap\mathcal T\neq\varnothing]$$ $$B_{\mathrm{final}}(c)=\mathbf1[c\in\mathcal T].$$ Intermediate endpoints require a finite legal continuation; final endpoints require completed acceptance after a permitted stop. The parser stack and environment are carried across windows. This continuation predicate concerns the existence of a finite completion; the final window enforces completion within the available output budget. Termination is permitted only when at least one parsing path reaches a grammar-accepting state, all nested structures are properly closed, the return stack contains no pending parsing obligations, and all environment constraints are satisfied. A valid path that can still be extended does not, by itself, constitute a completed output. The original Appendix A.3, Eqs. 12–14 and Lemma A.1, already defines static normalization as sound pruning: a finite abstract distance need not imply concrete feasibility. Window admissibility is checked separately using the concrete parser configuration. If no admissible path exists, the solver reports failure. **Resource limits.** | Audited backend | $H$ | Configurations / graph cells | Environment states | Grouped edges/window | |---|---:|---:|---:|---:| | LLaDA | 32 | 100,000 | 100,000 | 5,000,000 | | Gemma | 256 | $2^{28}$ | $2^{32}-1$ | $2^{28}$ | Retained GPU caches allow 8 workspaces / 2 GiB; stack CPU caches allow 16 MiB/schema and 8 MiB/session; the publication pool allows 32 slots / 2 GiB combined pinned-host/device payload. Stack return-stack entries are capped at 100,000.

Response to W2/Q2 Baseline Comparisons (1/3)

How were the baselines configured, and why was their reported validity low?

We thank the reviewer for raising these concerns. To ensure a fair and comprehensive comparison, we revisited the baseline configurations, corrected the evaluation pipeline, and conducted additional experiments across four model backbones and three tasks. We identified several factors contributing to the previously reported low validity: some successfully completed CPU outputs were not included in the final statistics, recovery and control-marker handling required correction, and stricter JSON Schema validation exposed failures that were not necessarily captured by the baselines' original evaluation protocols. Furthermore, differences between the baselines' sampling schedules and the native decoding policies of newer models affected their performance.

To address these issues, we corrected output recovery and control-marker handling, included all successfully recovered outputs, and extended our evaluation to the baselines' original LLaDA-8B and Dream-7B backbones. The updated results show that DConstrain achieves the highest throughput among constrained methods in all 12 comparisons, outperforming the fastest LAVE/EPIC/CD baseline by 1.45–10.48×. It also achieves the best or tied grammatical validity in all 12 comparisons and the best or tied semantic accuracy in 11. We have incorporated these expanded results into the main paper (Table 5) and provide the detailed baseline configurations and failure analysis below.

Datasets. We evaluate BFCL300, SMILES167, and the authors' JSON272 benchmark in place of JSB. Excluding the same three reference-invalid instances for every method yields JSON269.

Setup. Following our evaluation settings, baseline runs use T=32 (an iteration cap for Gemma/LAVE) and a 256-token generation budget. CD [3] and EPIC use their authors' schema converters on LLaDA-8B/Dream-7B; LAVE uses per-instance Lark grammars with LLGuidance. On LLaDA2.2/DiffusionGemma, serialization adapters use schema order, depth four, and the configured tool syntax. SMILES uses its task grammar.

CD/EPIC allow 100 cumulative rejections per request, with CPU completion enabled. LAVE uses 5/5/5 lookahead settings, five retries per token-acceptance search, and cache/AR recovery. Model sampling and CPU recovery share the request deadline; recovery time is included in latency. CD/BFCL runs on LLaDA2.2/DiffusionGemma use a 60-second request limit and cover 300/300 requests.

Decoding and metrics. Native/Ours use default adaptive decoding; baselines retain their respective sampling algorithms. TPS is output tokens/s; TPF is tokens per actual model forward. Validity and semantic accuracy are percentages. BFCL uses the official offline evaluator. Boldface identifies Ours.

Model / DatasetMethodTPS ↑TPF ↑Validity ↑Semantic ↑
LLaDA2.2 / BFCL300Native513.606.9994.3381.00
LAVE51.063.7895.0081.33
EPIC65.133.2999.6777.33
CD5.593.2899.6777.33
Ours395.546.12100.0084.33
LLaDA2.2 / SMILES167Native105.931.2671.8622.75
LAVE16.152.1587.4317.37
EPIC26.181.5499.4017.37
CD24.791.5699.4017.37
Ours83.281.08100.0023.95
DiffusionGemma / BFCL300Native162.826.6591.0080.00
LAVE9.943.6196.6777.67
EPIC31.933.35100.0083.67
CD2.593.04100.0083.33
Ours144.326.69100.0084.33
DiffusionGemma / SMILES167Native38.811.2969.4620.36
LAVE6.061.6698.2018.56
EPIC11.261.34100.0022.16
CD8.311.29100.0022.16
Ours23.831.20100.0026.35

Across the four BFCL/SMILES groups above, Ours combines 100% validity with the highest semantic accuracy and 2.12–6.07× the throughput of the fastest verification baseline. On BFCL, semantic accuracy reaches 84.33% on both newer backbones.

Part 2 reports LLaDA-8B/Dream-7B results; Part 3 gives request-level failure and recovery counts.

Response to W2/Q2 Baseline Comparisons (2/3)

How do the baselines compare in task accuracy and runtime under their documented decoding protocols?

On JSON269 and SMILES with LLaDA-8B/Dream-7B, DConstrain achieves 100% validity and the highest throughput in all four groups below. The same compiler supports MAP→Top-K, demonstrating that its reusable transition representation works with different token-commitment policies.

Setup. All methods below use G256. Our MAP→Top-K sampler fixes committed tokens, computes a highest-scoring legal MAP completion, and commits the scheduled positions ranked by the model probabilities of their MAP-selected tokens.

Protocol. Native uses each model's original decoder, temperature 0.2, and numerical precision, without added EOS early stopping. Constrained methods use temperature 0 and stop when the output is complete. Constrained requests use a 60-second limit, with one 180-second retry after failure. CPU recovery time is included in hot-run timing, and recovered outputs are scored. TPS is output tokens/s; TPF uses actual forwards.

Results. Validity and semantic accuracy are percentages. JSON269 excludes the same three reference-invalid cases from JSON272 and compares normalized outputs with references. Boldface identifies Ours.

Model / DatasetMethodTPS ↑TPF ↑Validity ↑Semantic ↑
LLaDA-8B / JSON269Native26.673.0071.3843.87
LAVE25.106.9795.1752.79
EPIC63.297.4196.2849.44
CD27.767.4196.6549.81
Ours91.997.60100.0052.04
LLaDA-8B / SMILES167Native6.920.5241.925.39
LAVE4.502.0897.016.59
EPIC18.983.41100.005.39
CD14.193.36100.005.39
Ours101.817.42100.006.59
Dream-7B / JSON269Native30.652.2173.9843.87
LAVE25.656.5786.9949.44
EPIC28.212.2298.8849.81
CD20.812.2298.1449.44
Ours95.967.41100.0049.81
Dream-7B / SMILES167Native6.930.3426.354.19
LAVE7.522.3698.204.19
EPIC4.650.30100.004.19
CD4.710.30100.004.19
Ours78.786.12100.004.79

The advantage persists on the baselines' original backbones: SMILES throughput is 5.36×/10.48× higher than the fastest verification baseline on LLaDA-8B/Dream-7B. Across these four groups, Ours has the best or tied semantic accuracy in three; on LLaDA-8B/JSON269, LAVE scores 52.79% versus Ours' 52.04%.

Why TPS can exceed Native. Following EPIC's evaluation protocol, Ours, EPIC, LAVE, and CD use completion-based EOS early stopping, whereas Native retains the original decoding implementation without added early stopping. This avoids unnecessary model forwards and can yield higher TPS than Native, as also observed for EPIC and LAVE. The same stopping rule is applied to all constrained methods for fairness.

Part 3 reports the causes of baseline validity failures after recovery.

Reviewer_urXzOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents DConstrain, a compilation framework for constrained decoding in diffusion language models. It precompiles reusable transition programs and binds parser context at runtime, reducing the cost of constructing state graphs for joint inference. It also groups tokens with identical transition effects while preserving the corresponding graph inference objectives. Experiments show improved compilation coverage and lower decoding overhead while maintaining schema validity and task accuracy.

Critical strengths
  1. Comparisons against an optimized DINGO baseline provide convincing evidence of benefits beyond implementation-level improvements. The direct-PDA comparison further supports the value of compiled transition reuse rather than merely avoiding finite-state expansion.

  2. The evaluation clearly distinguishes compilation coverage, constraint overhead, and overall latency, while acknowledging worst-case limitations. The grouping argument carefully preserves the corresponding graph inference objectives.

Critical weaknesses

W1. Evaluation is limited to JSON Schema–based workloads, leaving the applicability and efficiency of the approach on more general grammars unverified.

W2. Reported end-to-end latency excludes cold compilation and artifact loading. Although compilation costs are evaluated separately, the overall latency benefit for one-off or frequently changing schemas remains unclear.

Questions for authors

Q1. Can the authors evaluate a representative non-JSON grammar and explain how grammar complexity affects runtime graph construction and token-effect grouping?

Q2. How do the proposed transition programs and token-effect grouping differ technically from the parser preprocessing in PSC and token compression in CFGzip?

Q3. What is the total first-request latency, including compilation and loading, and how does the benefit change with schema reuse?

8 comments
AuthorsOpenReview ↗

Response to Reviewer urXz

Response to W1/Q1: Non-JSON Evaluation and Complexity (1/2)

W1/Q1 Non-JSON Evaluation

Can the authors evaluate a representative non-JSON grammar?

We thank the reviewer for suggesting evaluation beyond JSON. To address this concern, we extend our experiments to two representative non-JSON tasks: GSM-Symbolic arithmetic expressions (100 questions) and SMILES molecular strings (167 questions). These tasks directly impose grammatical constraints on arithmetic expressions and molecular representations, allowing us to evaluate DConstrain beyond JSON-based generation.

Experimental setup. We evaluate both LLaDA2.2 and DiffusionGemma. Native and DConstrain use default adaptive decoding, while LAVE, EPIC, and Constrained Diffusion (CD) use the selected 32 setting. We report throughput (TPS, tokens/s), tokens per actual forward pass (TPF), grammatical validity, and semantic accuracy. SMILES semantic accuracy is evaluated using containment.

DConstrain achieves 100% grammatical validity on both GSM-Symbolic and SMILES across both models, demonstrating that our approach extends beyond JSON constraints while preserving the grammatical correctness of generated outputs.

SMILES167.

ModelMethodTPS ↑TPF ↑Valid. ↑Semantic ↑
LLaDA2.2Native105.931.2671.8622.75
LAVE16.152.1587.4317.37
EPIC26.181.5499.4017.37
CD24.791.5699.4017.37
Ours83.281.08100.0023.95
DiffusionGemmaNative38.811.2969.4620.36
LAVE6.061.6698.2018.56
EPIC11.261.34100.0022.16
CD8.311.29100.0022.16
Ours23.831.20100.0026.35

GSM-Symbolic100. This uses a matched DINGO-Opt comparison. Cold is ms/grammar; warm E2E is ms/request.

ModelMethodColdE2ETPSValid (%)Semantic (%)
LLaDA2.2Native0584.59309.0062.0043.00
DINGO-Opt684.862271.1684.36100.0048.00
Ours85.621009.24195.75100.0048.00
DiffusionGemmaNative0722.74273.3247.0029.00
DINGO-Opt1215.831571.19130.48100.0044.00
Ours120.19798.94249.62100.0044.00

On GSM-Symbolic, Ours matches DINGO-Opt's semantic accuracy with 8.00–10.12× faster cold compilation and 1.97–2.25× faster warm E2E. On SMILES, Ours improves throughput and semantic accuracy over the constrained baselines on both models.

Response to W1/Q1: Non-JSON Evaluation and Complexity (2/2)

Q1 Grammar Complexity and Token Grouping

How does grammar complexity affect runtime graph construction and token-effect grouping?

We thank the reviewer for this important question. Grammar complexity affects two key aspects of our method: the number of reachable parser configurations that must be represented in the constraint graph, and the diversity of token transition effects that determines grouping efficiency. To systematically investigate these factors, we evaluate 34 controlled grammars and 12 fixed BFCL schemas using the same tokenizer, an H=32 partial window, and an empty prefix. The table reports DConstrain's graph construction time averaged over three fresh-session runs, excluding cold compilation, model inference, and cached canvas graphs. Token-edge compression is measured as the ratio of token-labeled edges to grouped edges.

GrammarConfigurationsGrouped EdgesCompressionBuild (ms)
Nested arrays, depth 427254686.18×0.242
Nested arrays, depth 1251414421.38×0.356
12 fields, fixed order1481,282950.34×0.637
4 fields, any order5745,654985.02×1.808
12 fields, any order303,1103,186,602967.41×98.607
64 tag/value choices, independent1665051.00×0.390
64 tag/value choices, linked1,0422,2001.00×2.154
BFCL, fixed index 5436,887156,890391.28×235.826

Three factors explain the results:

  • Reachable contexts: increasing any-order fields from 4 to 12 gives 528× more configurations and 54.5× longer construction, despite approximately 970× compression. Increasing array depth from 4 to 12 causes much smaller growth.
  • Token-effect diversity: exact literals yield 1× compression. Linking tag/value choices restricts valid combinations and increases reachable contexts and build time; open strings permit much stronger grouping.
  • Structural reuse: BFCL index 54 has 8.2× fewer configurations than the 12-field any-order grammar but takes 2.39× longer to build, with 11,784 distinct structural-row expansions versus 201. CPTP reuses the compiled transition logic across contexts.

All 46 conditions pass full-vocabulary H=32 equivalence checks.

Response to Q2: Technical Differences from PSC and CFGzip (1/2)

We thank the reviewer for the opportunity to clarify the technical distinctions between our method and PSC/CFGzip. The fundamental difference lies in the compilation target and the granularity of structural reuse. PSC preprocesses parser-stack transformations using finite-state transducers, while CFGzip compresses vocabulary transitions through token equivalence classes. Both primarily target autoregressive constrained decoding, where transitions are evaluated from a single realized prefix. In contrast, DLM joint inference requires constructing an explicit multi-step constraint graph over numerous hypothetical parser configurations within each decoding window. Our Context-Parameterized Transition Programs (CPTP) compile reusable transition logic across different stack and environment contexts, avoiding repeated structural computation. Meanwhile, local token-effect grouping shares equivalent transitions at individual program points while preserving the successor structure and token scores required for joint MAP inference.

To isolate these differences, we conduct controlled comparisons with both methods. The experiments examine three distinct sources of redundant computation: repeated return continuations, combinatorial environment specialization, and globally constrained token equivalence. The results demonstrate that CPTP's benefits arise from its compilation and reuse mechanisms, rather than merely from implementing existing parser operations more efficiently.

PSC: Structural reuse across parser contexts.

PSC preprocesses parser-stack transformations using finite-state transducers (FSTs). In contrast, CPTP compiles parameterized programs that retain stack operations, symbolic environment guards and updates, and residual continuations, binding concrete parsing contexts only at runtime. For a controlled comparison, our output-preserving PSC adapter retains PSC's original partial lexer and FST preprocessing.

  1. Shared return continuations. CPTP reuses continuation structures across different parser histories instead of repeatedly expanding them. Using PSC's original EBNF list grammar (H=32, Apple M5 CPU, median of 21 trials):
Nesting DepthCPTP (ms)PSC (ms)Speedup
40.0420.92622.1×
60.05110.069197.9×
80.056117.4912104.3×

As nesting depth increases from 4 to 8, PSC's processing time grows by over two orders of magnitude, while CPTP remains nearly constant, reaching a 2104.3× speedup. This demonstrates the importance of sharing return-continuation logic across distinct parser contexts rather than repeatedly materializing equivalent structural computations.

  1. Symbolic environment specialization. CPTP represents unordered-field histories through symbolic guards and updates, whereas the tested PSC frontend enumerates field-history subsets as separate grammar variants. Complete cold preparation starts from a preloaded vocabulary and ends with an engine ready for graph construction:
FieldsPSC Cold (ms)Ours Cold (ms)PSC Artifact (MB)Ours Artifact (MB)
21,078.27244.9741.9621.366
41,251.14149.7312.1861.386
62,134.61948.7093.6641.406
823,027.40046.30912.5341.426
10Timeout50.367—1.445
12Timeout46.763—1.465

Timeout is 30 seconds per run.

At eight fields, CPTP achieves 497× faster cold preparation while producing a substantially smaller artifact. More importantly, CPTP's preparation time remains approximately 45–50 ms through 12 fields, whereas PSC exceeds the 30-second limit beyond eight fields. This demonstrates that retaining environment conditions as runtime parameters avoids the combinatorial grammar specialization incurred by the tested PSC frontend. The benefit is therefore not simply faster preprocessing, but avoiding the need to compile separate structures for different field-history combinations.

  1. Reusable runtime structural expansion. Beyond cold preparation, we evaluate whether CPTP's structural reuse also reduces the cost of constructing explicit constraint graphs. Both methods use their existing C++ graph builders, the same tokenizer, H=32, and identical partial-window semantics:

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.