acceptodds
Under review as a conference paper at ICLR 2027

From Grammar Deltas to Token Masks: Incremental Constrained Decoding under Runtime Grammar Evolution

11 views

Abstract

Grammar-constrained decoding enables large language models to generate outputs that satisfy formal constraints, but in code and domain-specific language generation, the relevant constraints are not always fully available before decoding and may emerge progressively from new declarations, inferred type information, or runtime analysis feedback. Existing structured-decoding engines efficiently handle fixed, predeclared, or previously seen constraint structures; however, when a first-seen grammar update changes the parser state induced by an already committed prefix, the straightforward solution reconstructs the constraint state under the updated grammar, repeating parsing work already performed over the prefix. We introduce GramDelta, an incremental framework for constrained decoding with append-only runtime grammar updates. GramDelta maintains parse state over the committed prefix and propagates only changes induced by newly added grammar rules through historical dependencies, avoiding prefix replay. It further incrementally maintains next token validity from these parser state changes, reusing an unchanged mask or rechecking only affected tokenizer-trie regions when the impact is localized. GramDelta therefore preserves the result of full reconstruction while making update cost sensitive to the actual impact of a grammar change. Experiments across four model configurations show that GramDelta reduces median first-seen grammar-update latency by – relative to XGrammar and reduces the additional TPOT overhead over unconstrained serving by –. These results enable efficient constrained decoding when constraints progressively emerge and evolve with the generated prefix.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Constrained Decoding, Structured Generation, Incremental Parsing, Dynamic Grammars, Earley Parsing, Large Language Models

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_eWK5OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces GramDelta, a framework for grammar-constrained decoding when previously unseen productions are added after a generation prefix has already been processed. GramDelta retains historical Earley charts, locates the entry points of new productions through persistent waiting dependencies, and propagates newly enabled Predict, Scan, and Complete deductions. It then attempts to update the next-token mask through direct reuse, localized tokenizer-trie traversal, or full reprojection. The paper evaluates GramDelta against XGrammar within SGLang using dynamic grammars Across four model configurations, it reports 1.33–1.69× lower median update latency and an 83.9–87.3% reduction in additional TPOT overhead relative to unconstrained decoding.

Critical strengths
  1. The paper addresses an important efficiency problem in grammar-constrained decoding. When new grammar rules arrive during generation, rebuilding the parser repeats work on output that has already been processed. GramDelta avoids this by retaining the existing Earley charts and propagating only the additional states enabled by the new rules. The paper provides a detailed argument that these updates produce the same charts as parsing the prefix again under the updated grammar. This approach is useful when rules are added repeatedly during a long generation.

  2. The experiments show consistent efficiency gains across models. GramDelta improves both update latency and TPOT across four model configurations, providing useful evidence that the approach can reduce decoding costs in the tested setting.

Critical weaknesses
  1. An unchanged parser frontier does not necessarily mean that the token mask is unchanged. Section 3.4 allows reusing the old mask when the current parser frontier, acceptance status, and lexical state remain unchanged. However, a token can contain several bytes. A new grammar rule may be used after scanning the first byte of that token, even if it does not affect the parser state for the generated prefix. For example, consider: S -> x a B; B -> b. The generated prefix is x. The update adds: B -> c. The parser state after x is unchanged: it still expects a. However, a token containing ac becomes valid, because the updated grammar accepts xac. Reusing the old mask would miss this token. The implementation may store additional information that prevents reuse in this case, but the paper does not explain it. The paper also does not explain how it chooses which tokens to recheck during local repair and why this procedure cannot miss a newly valid token. Both points need to be resolved to support the claim that the updated mask exactly matches full recomputation.

  2. The paper lacks necessary ablation experiments. The experiments show that GramDelta is faster than XGrammar, but they do not show how much of the speedup comes from incremental parser updates versus mask reuse and local repair. For example, the authors could keep incremental parser updates but recompute the full mask after every update. Comparing this version with the complete system would show the benefit of the mask optimizations. A comparison under a fixed grammar, with no runtime updates, is also missing.

Questions for authors
  1. In the example in Weakness 1, does GramDelta allow the token ac after adding B -> c? What tells the algorithm to update the mask when the parser states for the prefix x remain unchanged?
  2. How much do mask reuse and local repair reduce decoding time? Please compare full GramDelta with a version that keeps incremental parser updates but recomputes the entire mask after every grammar update.
  3. How do the decoding speeds of GramDelta and XGrammar compare when the grammar remains unchanged throughout generation?
  4. What practical applications need grammar rules to change during generation while allowing the set of valid outputs only to expand?
2 comments
AuthorsOpenReview ↗

Response to Reviewer eWK5

We thank Reviewer eWK5 for identifying the token-projection correctness issue and for asking how much the projection optimization contributes beyond incremental parser maintenance. We also clarify the application setting targeted by append-only grammar evolution.

1. Response to W1 and Q1: Correctness for Multi-Byte Tokens

Yes. After adding B→cB\rightarrow c, the token ac must be admitted. We agree that the original frontier-based mask-reuse condition was insufficient: the parser state after the committed prefix x remains unchanged, but the new production can become applicable after scanning the first byte a of a multi-byte token.

We therefore removed the frontier-only mask-reuse shortcut and the heuristic local-repair path. In the revised §3.4, Factorized Token Projection evaluates uncertain token continuations under the updated productive grammar. In this example, speculative Scan/Complete/Predict traversal scans a, predicts the newly added production B→cB\rightarrow c, and then scans c, correctly admitting ac.

Proposition 2 and Appendices A.4 and B.2 establish the equivalence of the revised projection with full token projection.

2. Response to W2 and Q2: Isolating the Benefit of Exact Token Projection

To isolate projection cost from parser-update cost, we keep incremental Earley maintenance enabled and compare the revised factorized projector with recomputing the full vocabulary mask through naive prefix-trie reprojection after every update:

Projection workloadFactorized projectionNaive full-vocabulary reprojectionSpeedup
4K narrow update0.019 ms3.608 ms190×
Wide open-string state0.041 ms2,466.382 ms>60,000×

The results show that incremental parser updates alone do not make full-vocabulary mask recomputation efficient.

The broader update-stage breakdown is given in our response to Reviewer GzYm (Q2), and the serving-level component ablations are covered in that reviewer's Q3 response. We avoid repeating those broader tables here.

3. Response to Q3: Decoding with a Fixed Grammar

With no runtime updates ((K=0)), Table 5 shows that GramDelta remains close to both baselines across four models and 1K/4K prefixes: its median TPOT is only 0.06–0.25 ms/token higher than XGrammar and within 0.13 ms/token of llguidance (e.g., on Qwen3-8B, 18.05/19.19 ms/token for GramDelta versus 17.94/19.01 for XGrammar and 18.03/19.09 for llguidance). Turning persistent indices on changes TPOT by only −0.13% to +0.12%, indicating negligible steady-state cost from index retention. GramDelta is therefore not the fastest static decoder; its static behavior is close to the reconstruction control, and the persistent indices themselves add negligible overhead.

The broader steady-state measurements and the marginal cost of retaining historical indices are reported in our response to Reviewer GzYm (Q2) and Appendix D, Table 5.

4. Response to Q4: A Concrete Application of Append-Only Grammar Evolution

A practical setting we target is repository-level, type-constrained code generation with progressive declaration discovery. Consider a code generator working in a large project. It may initially receive only the declarations available in the current local context. As generation proceeds and the relevant import, receiver type, or dependency is resolved, a repository index or type-information service can retrieve additional API declarations and member signatures. These newly discovered signatures can be added as grammar productions, expanding the set of valid identifier and member-call continuations while leaving previously discovered declarations valid under the same project snapshot.

For example, after the generated prefix establishes a receiver s of type String and reaches s., additional member signatures may be surfaced progressively from the project's declaration files. Each newly revealed signature adds another valid member completion. The grammar therefore grows during generation even though the already generated prefix is unchanged. Without incremental grammar evolution, the constraint backend would need to rebuild its state and reprocess that prefix whenever another declaration becomes available. GramDelta instead incorporates the newly revealed productions into the persistent Earley state.

Thank you for the clarifications. The revised paper addresses the correctness concern I raised in W1, and the response to Q4 clarifies the motivation. These improvements strengthen the paper, so I decide to raise my score.

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

This paper presents GramDelta, an incremental constrained-decoding framework for runtime grammar evolution. When a first-seen additive grammar update changes the parser state induced by an already committed prefix, existing structured-decoding engines must reconstruct the constraint state and replay the prefix from scratch. GramDelta instead performs three incremental steps — historical delta localization (locating where new productions can enter the old Earley closure via a HistWait index, proving that charts before the earliest entry point remain unchanged), delta Earley closure (semi-naive rules that propagate only newly enabled Predict/Scan/Complete deductions, with a fixed point provably identical to full reconstruction), and token-mask repair (reprojecting only affected tokenizer-trie regions while reusing the rest). Across four model configurations (Qwen3-8B/32B, Granite-4.1-3B/8B) in SGLang, GramDelta reduces first-seen update latency by 1.33–1.69× and the extra TPOT overhead of runtime grammar evolution by 83.9–87.3% relative to XGrammar, while preserving exact equivalence to full reconstruction.

Critical strengths
  • Existing engines either target fixed grammars or support dynamic selection and construction of constraints, yet none incrementally maintains the historical parser state induced by a committed prefix when a grammar update arrives late; this is a real and previously unhandled gap, and the motivation of constraints progressively emerging from declarations, type inference, and runtime analyses in code and DSL generation is convincingly argued.
  • The three delta rules (factorized Predict, sparse Scan, origin-sensitive Complete) cleanly transfer semi-naive incremental evaluation from databases to Earley parsing, and the first-new-fact characterization, historical left boundary, exact incremental closure, and exact projection are all proved in the appendix.
  • Stable dotted-state identifiers, three reverse indices (HistWait/WaitAdv/CompletedByStart), an event-driven worklist, and a shared tokenizer trie give the approach a concrete implementation path rather than a purely theoretical one.
  • The first-seen update protocol forbids preloading future grammar fragments, the shared-token protocol neutralizes tokenization-policy differences, and the dual metrics (Update Latency vs. request-level TPOT) cleanly separate constraint-side cost from end-to-end cost, with consistent results across four models and two tokenizer families.
Critical weaknesses
  • XGrammar is the sole baseline and is forced onto a reconstruct-and-replay path under the first-seen protocol (as the paper admits); no incremental or automata-route baselines (e.g., llguidance, Pre³) are included, and XGrammar's abnormally high 946.2% TPOT overhead on Qwen3-8B is unexplained — the paper does not decompose rebuild, replay, and projection costs, so the reader cannot tell whether the gains come from the incremental algorithm itself or from the protocol construction.
  • The dependence of the incremental benefit on update locality is only discussed qualitatively, with no sensitivity curves of incremental time versus affected-region size, delta size, or trigger position; the critical point where incremental cost degrades toward reconstruction is never identified, and no steady-state overhead comparison without updates is reported.
  • The controlled dynamic grammars and BFCL-derived traces are not real code-generation tasks, with no end-to-end validation on HumanEval-style or real agent tool-calling traces; only single-run medians are reported without variance or confidence intervals, and batch/concurrent serving, the norm in practice, is not evaluated.
  • The paper defers the memory–update-cost tradeoff of persistent historical dependencies to future work without any memory-growth experiments or worst-case analysis, leaving unclear where the space–time tradeoff remains favorable for long prefixes, large grammars, and frequent updates.
Questions for authors
  • Add incremental or automata-route baselines such as llguidance or Pre³, provide a time breakdown of XGrammar's 946% overhead, and include a "reconstruction-plus-caching" control to separate the incremental algorithm from cache reuse; also report GramDelta's steady-state overhead without updates to show the maintenance tax is negligible.
  • Plot incremental update time against the size of the affected region to expose the critical point where incremental cost approaches reconstruction; report means, standard deviations, or confidence intervals over repeated runs, and add end-to-end validation on real code-generation or agent tool-calling traces plus a batch/concurrent serving scenario.
  • Quantify the memory growth of the persistent indices against prefix length and grammar size, and provide a worst-case complexity analysis of the incremental update, to demonstrate under which workloads the space–time tradeoff remains favorable.
3 comments
AuthorsOpenReview ↗

Response to Reviewer nzY2

We thank Reviewer nzY2 for the thorough systems-oriented review and for recognizing the algorithmic contributions of GramDelta. In the revision, we replaced the earlier frontier-only token-mask reuse path with exact Factorized Token Projection (§3.4, Proposition 2; Appendices A.4 and B.2). We also rebuilt the evaluation around in-process serving and expanded it with matched reconstruction and incremental/automaton-based baselines, an reconstruction-plus-caching control, a source-grounded code-generation workload, and additional locality, scaling, batching, and memory analyses.

1. Response to W1 and Q1: Baselines, Cache Control, and Cost Attribution

We added Fresh baseline to isolate incremental maintenance from engine implementation, llguidance as an incremental Earley baseline. We additionally added persistent XGrammar-Cache alongside uncached XGrammar to distinguish incremental maintenance from reconstruction with cross-grammar cache reuse. The previously reported 946.2% TPOT overhead is not an intrinsic XGrammar overhead. It was measured with an out-of-process evaluation wrapper. The revised evaluation removes this asymmetry by using an in-process serving.

The results of the supplementary experiments are presented in Table 3, which confirm the advantage of GramDelta in dynamic grammatical scenarios.

Under the first-seen update protocol, each newly composed grammar contains productions not seen by the compiler cache. It therefore misses the full-grammar cache entries while still incurring insertion costs. Consistent with this, XGrammar-Cache is slower than uncached XGrammar on BFCL.

We also quantifies the first-seen update path. The instrumented fields are grouped into four stages:

Update stage (mean ms)GramDeltaFreshllguidanceXGrammarXGrammar-Cache
Dispatch and host-spec preparation1.48738.65812.25612.52112.381
Backend construction / update1.48010.91823.001514.676663.804
Committed-prefix replay0.0007.23520.6551.9272.330
Localization/closure, projection, and post-processing0.8490.5810.0990.0760.078
Total3.81657.39156.011529.200678.592

The breakdown shows that backend construction/update accounts for 514.676 ms of XGrammar's 529.200 ms total, whereas committed-prefix replay accounts for 1.927 ms. Thus, the large first-seen update cost in this workload is dominated by backend construction rather than prefix replay. The breakdown and attribution of TPOT's performance can be seen in the response to Reviewer Q2 of GzYm.

The static-decoding results distinguish total decoding overhead from the marginal cost of retaining historical indices. At K=0K=0, GramDelta's total TPOT overhead is 5.57%, compared with 1.06% for XGrammar and 1.37% for llguidance. In the separate index-retention control, retaining HistWait, WaitAdv, and CompletedByStart changes GPU TPOT by only −0.13% to +0.12% across four models at 1K/4K(Appendix D, Table 5). Thus, the measured marginal serving cost of retaining these indices is negligible, although GramDelta's total static-decoding overhead remains higher than that of the precompiled baselines.

2. Response to W2 and Q2: Update Locality, Sensitivity Axes, and Statistical Reliability

Figure 2(c) and the table below reports the update-locality sensitivity analysis:

Affected historical rowsActual affected rowsGramDelta (ms)Fresh (ms)
0%00.1322.829
5%2040.2592.935
25%1,0240.7493.580
50%2,0481.4704.394
75%3,0722.3825.366
100%4,0963.4146.037

The results show that GramDelta's update latency increases smoothly as the affected region grows, while its speedup over Fresh narrows from 21.4× to 1.77×. The 100% point is still faster than Fresh in this controlled fixture.

The remaining sensitivity dimensions are covered by the other panels of Figure 2: update count KK in Figure 2(a), prefix length from 512 to 16K tokens in Figure 2(b), and batch size B∈{1,4,8}B\in\{1,4,8\} in Figure 2(d).

Statistical reliability is documented in Appendix D. Tables 3 and 4 report 20 paired runs per GPU configuration, 95% bootstrap confidence intervals for median update latency and TPOT, and p95 update latency.

AuthorsOpenReview ↗

Response to Reviewer nzY2-2

3. Response to W3: Code-Generation Workload and Batched Serving

Based on the code generation application cases of Mündler et al. (2025) and Zhang et al. (2026) under constrained decoding, we designed a new benchmark called CodeEvo as an additional evaluation criterion. During the generation process, the grammar will be continuously updated according to the current whitelist.

On CodeEvo, across four model configurations, GramDelta achieves 10.70–11.50× lower median update latency than Fresh and reduces additional TPOT overhead by 53.08–76.82% relative to the best baseline (Appendix D, Table 4).

We also report the CodeEvo-specific fused-batching results at B=8B=8, 8K tokens, and K=8K=8 (Figure 2(d)):

CodeEvo metricUnconstrainedGramDeltaFreshllguidanceXGrammar
Staggered throughput (tok/s)118.07102.1882.75100.2337.63

At eight-way batching, GramDelta reaches 102.18 tok/s on CodeEvo, close to llguidance (100.23 tok/s) and above Fresh (82.75 tok/s) and XGrammar (37.63 tok/s).

4. Response to W4 and Q3: Retained-State Memory and Complexity

We added two isolated-process memory sweeps: one varies prefix length at a fixed 2,848-production BFCL, and the other varies grammar size at a fixed 4K prefix:

Memory versus prefix length

Prefix length (nominal)GramDelta tracked (MB)GramDelta RSS (MB)Fresh RSS (MB)llguidance RSS (MB)XGrammar RSS (MB)
5123.6025.6036.95511.76025.330
1K4.0546.4237.82713.02125.981
4K6.71211.22312.64022.04129.790
8K10.15817.27718.69436.29535.267
16K17.04529.40130.81854.24745.146

As the prefix grows from 512 to 16K tokens, GramDelta remains below Fresh, llguidance, and XGrammar in RSS at all five measured prefix lengths.

Memory versus grammar size

Nominal grammar sizeActual productionsGramDelta tracked (MB)GramDelta RSS (MB)llguidance RSS (MB)XGrammar RSS (MB)
5005091.4962.9667.23819.816
1,5001,5022.4534.0359.05221.406
2,8002,8024.2086.07811.60423.511
5,6005,6058.25910.81815.70428.197

At a fixed 4K prefix, increasing the grammar from 509 to 5,605 productions raises GramDelta's tracked state from 1.496 to 8.259 MB and its RSS delta from 2.966 to 10.818 MB. Its measured RSS remains below both external baselines at every grammar size.

The complexity analysis in Appendix A.5 gives output-sensitive update bounds over newly derived facts �2��2�. When no new seed states are introduced, the work is limited to production activation, �3��3�. Under bounded active origins, update time and persistent space are �4��4�. For arbitrary ambiguous CFGs, worst-case update time is �5��5�, with �6��6� worst-case persistent space.

The time–space trade-off is favorable when updates affect a localized portion of the historical chart and the number of active origins per dotted state remains bounded. For broad or global updates, or for highly ambiguous recursive grammars, the worst-case growth can dominate, full reconstruction may then be preferable.

[1] Mündler N, He J, Wang H, et al. Type-constrained code generation with language models[J]. Proceedings of the ACM on Programming Languages, 2025, 9(PLDI): 601-626.

[2] Zhang S, Xu R, Li H, et al. Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments[J]. arXiv preprint arXiv:2607.18357, 2026.

Thank you for the extensive revisions and new experiments. All my previous concerns are largely addressed. The authors have added more baselines, latency breakdowns, tests on update impact scope, the CodeEvo code generation benchmark, batch processing performance results, memory usage measurements and complexity analysis. I am updating my score to 3.

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

GramDelta addresses constrained decoding when previously unseen productions are added after a prefix has been generated. It indexes historical nonterminal waits, propagates newly enabled Earley deductions, and proposes incremental token-mask repair to match reconstruction under the updated grammar. Experiments use controlled dynamic grammars and BFCL-derived progressive-reveal traces within SGLang. Across four model/tokenizer configurations, the method reports 1.33–1.69× lower median update latency than XGrammar and an 83.9–87.3% reduction in additional TPOT overhead relative to unconstrained serving.

Critical strengths
  1. The paper tackles an important problem: maintaining prefix-dependent parser state after late production additions. Historical waiter indexing and bidirectional completion joins provide a principled mechanism for reusing prior computation.

  2. The reported improvements are consistent across four model/tokenizer configurations. The shared-token protocol controls the committed prefix and update chronology, making the backend comparisons more interpretable.

Critical weaknesses

W1. Token-mask repair is underspecified. Sections 3.4 and B.2 do not explain how mask reuse accounts for grammar changes beyond the current frontier or how conservative affected trie regions are computed, leaving exactness insufficiently justified.

W2. The evaluation lacks component ablations, scaling analyses, and historical-state memory measurements, limiting attribution of the reported speedups and assessment of performance on longer prefixes or broader updates.

Questions for authors

Q1. How does the implementation handle the counterexample above? Please specify any grammar dependencies represented in the projection state and the algorithm for selecting conservative affected trie roots. Differential tests involving tokens spanning multiple grammar symbols would help substantiate the current correctness claim.

Q2. Can the authors separate backend construction, prefix replay, incremental closure, and token projection costs, including non-update decoding steps? Please report updates per output token and latency distributions to explain the 2.84–4.76× TPOT speedup versus the 1.33–1.69× median update speedup.

Q3. Can the authors provide ablations of historical localization and incremental mask repair, together with runtime and retained-state memory as prefix length and update locality vary? These measurements would directly test the claimed dependence on the actual impact of a grammar change.

3 comments
AuthorsOpenReview ↗

Response to Reviewer GzYm

We sincerely thank Reviewer GzYm for the constructive comments. In response to the concerns regarding token-mask correctness, update-cost attribution, and component contributions, we revised the algorithmic description (§3.4) and expanded the ablation, performance attribution, and memory-scaling evaluations (§4.3–4.4, Appendices A and D).

Q1. Exactness of Token-Mask Repair

We revised the token projection procedure in §3.4 by replacing the frontier-based mask-reuse shortcut with exact factorized token projection, which evaluates uncertain token candidates under the updated productive grammar and handles newly activated productions across token boundaries. Proposition 2 establishes that the revised factorized projection is equivalent to full token projection.

Q2. Component-level Cost Breakdown and Non-update Decoding

We agree that update latency alone does not explain end-to-end decoding performance. We therefore profiled individual constraint-processing stages within the same decoding loop, using Qwen3-8B on our original BFCL benchmark on an RTX PRO 6000. All methods follow the same token trajectory, with 20 paired requests per method and warmups excluded.

Fresh reconstructs the backend under the updated grammar and replays the committed prefix from scratch in GramDelta. Update latency is measured from update submission until the updated token mask is available.

The following table reports mean processing time in milliseconds, with related bookkeeping operations combined.

Update-stage breakdown (mean ms)

Update stageGramDeltaFreshllguidanceXGrammarXGrammar-Cache
Dispatch and host preparation1.48738.65812.25612.52112.381
Backend construction/update1.48010.91823.001514.676663.804
Prefix replay07.23520.6551.9272.330
Historical lookup and incremental closure0.0010000
Token projection and mask generation0.0980.0540.0620.0080.008
Post-projection bookkeeping and mask return0.7280.5040.0250.0040.004
Total update latency3.81657.39156.011529.200678.592

The end-to-end update latency is measured independently of the individual stage timings; therefore, a small residual (approximately 0.01–0.07 ms) remains between the sum of the reported stages and the total. The decomposition highlights two main advantages of GramDelta: it avoids committed-prefix replay entirely and replaces expensive backend reconstruction with lightweight incremental maintenance. XGrammar's update cost is dominated by backend construction and cache bookkeeping, whereas Fresh and llguidance incur substantial prefix-replay costs. GramDelta retains a small projection and bookkeeping overhead, but its overall update cost remains substantially lower.

To examine how these update costs affect actual decoding performance, we further measure the inter-token latency (ITL) at ordinary and update positions, as well as request-level TPOT. Update latency measures the time spent on constraint processing, whereas ITL measures the elapsed time between consecutive generated tokens. Since update processing may overlap with model execution, update latency is not directly added to ITL. The results are reported below.

Decoding latency (mean ms; TPOT in ms/token)

MetricGramDeltaFreshllguidanceXGrammarXGrammar-CacheUnconstrained
Ordinary-step ITL21.11621.43420.49920.85121.20619.575
Update-step ITL22.86063.25357.621530.981680.35519.569
Additional update-step delay over ordinary steps1.74441.81937.122510.130659.149-0.006
Request TPOT21.49830.60028.635132.660165.67719.574

The additional delay at update positions reflects how much constraint processing extends the decoding interval beyond an ordinary step. GramDelta avoids prefix replay and full backend reconstruction, so its update work adds only 1.744 ms to the observed token interval. Fresh and llguidance incur much larger penalties because they rebuild or reinitialize backend state and replay the committed prefix; XGrammar and XGrammar-Cache are dominated by backend compilation and cache-management work for first-seen updates. These penalties are not equal to the standalone update latencies, because part of the update processing overlaps with model execution. Since only parts of post-first-token intervals contain updates, the additional delay is amortized across the request. Consequently, GramDelta achieves 15.03× lower mean update latency and 1.42× lower mean request TPOT than Same-engine Fresh, while keeping request TPOT close to unconstrained decoding.

AuthorsOpenReview ↗

Response to Reviewer GzYm-Q3

Q3. Component Ablation, Runtime Scaling, and Retained-State Memory

We added component ablations and systematic runtime and memory measurements to evaluate the contributions of historical localization and incremental token projection, as well as their sensitivity to prefix length and update locality. Fresh reconstructs the backend under the updated grammar and replays the committed prefix from scratch.

Component ablation (§4.3, Table 2). We isolate the contributions of the main components on Qwen3-8B, covering narrow CPU updates, wide-string projection, and 8K GPU decoding with (K=32).

VariantNarrow CPU Update (ms)Wide Projection (ms)GPU Update (ms)GPU TPOT (ms/token)
Fresh2.3980.03841.32429.659
GramDelta w/o HistWait0.1260.0366.31621.233
GramDelta w/o Shared History13.7710.752193.368242.196
GramDelta w/o Complement Partition0.109543.0813.85221.240
Full GramDelta0.1040.0343.75721.208

Removing HistWait increases GPU update latency from 3.757 to 6.316 ms (1.68×), while removing shared-history support increases it to 193.368 ms. Removing complement partitioning increases wide-string projection from 0.034 to 543.081 ms. These results demonstrate the distinct contributions of historical localization, shared-history maintenance, and efficient token projection.

Runtime scaling (§4.4, Figure 2b–c). Figure 2(b) evaluates prefix lengths from 512 to 16K tokens on Qwen3-8B and BFCL (K=8).

Prefix LengthGramDelta (ms)Fresh (ms)llguidance (ms)XGrammar (ms)
5122.01323.19630.539203.426
1K2.09123.24331.439220.242
4K3.07430.78639.225330.702
8K3.64939.73049.908490.604
16K4.76459.87176.902826.058

Figure 2(c) evaluates update locality on a fixed 4,096-token prefix with 64 initial rules and one newly added rule per update. Each point is the median of 30 paired updates, excluding one warmup.

Affected Historical RowsGramDelta (ms)Fresh (ms)
0%0.1322.829
5% (204 rows)0.2592.935
25% (1,024 rows)0.7493.580
50% (2,048 rows)1.4704.394
75% (3,072 rows)2.3825.366
100% (4,096 rows)3.4146.037

As the prefix grows, GramDelta increases from 2.013 to 4.764 ms, consistently remaining faster than the reconstruction and replay baselines. More importantly, as affected historical rows increase, its speedup over Fresh decreases from 21.42× to 1.77×. This identifies the dependence of incremental maintenance on update locality and the regime in which its advantage approaches reconstruction.

Retained-state memory (§4.4, Appendix D). We measure memory after prefix initialization and before the first grammar revelation on BFCL. The table reports tracked state and process RSS in MB.

Prefix Length (tokens)GramDelta Tracked (MB)GramDelta RSS (MB)Fresh Tracked (MB)Fresh RSS (MB)llguidance RSS (MB)XGrammar RSS (MB)
5123.6025.6033.6366.95511.76025.330
1,0244.0546.4234.1257.82713.02125.981
4,0966.71211.2237.00112.64022.04129.790
8,19210.15817.27710.74718.69436.29535.267
16,38417.04529.40117.12030.81854.24745.146

We additionally measure retained memory under varying update locality on a fixed 4K prefix.

Affected Historical RowsActual Affected RowsGramDelta Tracked (MB)GramDelta RSS (MB)Fresh Tracked (MB)Fresh RSS (MB)llguidance RSS (MB)XGrammar RSS (MB)
0%00.9642.9491.0303.2196.55819.493
5%2040.9913.0841.0563.3756.44719.468
25%1,0241.0883.6001.1533.8996.30019.399
50%2,0481.2104.2761.2764.5426.23819.280
75%3,0721.3334.9521.3995.1655.84119.071
100%4,0961.4565.7591.5225.8255.55819.210

The prefix-length measurements show that GramDelta has lower measured RSS than llguidance and XGrammar across all five evaluated lengths.

Taken together, the runtime and memory measurements show that GramDelta's maintenance cost tracks the actual historical impact of grammar updates: both runtime and retained memory increase as more committed rows are affected, while remaining below Fresh across all tested locality levels. Its advantage is largest for localized updates and narrows as updates approach global impact.

Thank you for the substantial revision and additional experiments. My main concerns have been addressed, and I will raise my rating from 2 to 3. Please incorporate these clarifications and results into the revised paper.

If time permits, could you provide more details on the differential tests against full reconstruction, including the number of comparisons, coverage of multiple active loops, tokens spanning grammar symbols, nullable/recursive productions, and dormant-rule activation, and whether any mismatches were observed?

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response

We sincerely thank the Area Chair and Reviewers GzYm, nzY2, and eWK5 for their constructive feedback. In response to the reviews, we have made several focused refinements:

  • Recognizer and projection correctness. We refined production activation and seed construction to account for previously dormant productions that become productive after an update. We also replaced the previous frontier-based token-mask reuse and local-repair path with exact Factorized Token Projection, using speculative Earley traversal over shared historical charts to handle uncertain multi-symbol tokens.

  • Evaluation fairness and coverage. We retained the original BFCL-derived workload and additionally introduced CodeEvo as a separate declaration-driven validation workload. The original four model configurations and GPU platform remain unchanged, while the evaluation harness is now symmetric and in-process. We also strengthened the comparisons with a matched same-engine reconstruction baseline, updated llguidance implementations, persistent XGrammar caching, and Pre³ on a compatible subset.

  • Further empirical analysis. We expanded the existing component ablation and added systematic scaling, update-locality, batching, crossover, and memory analyses to better characterize the contributions and performance boundaries of GramDelta.

Across the two sustained workloads and four model configurations, the revised evaluation shows 10.70–11.50× lower update latency and 53.08–81.93% lower additional TPOT overhead relative to the strongest reconstruction baseline for each metric.

We believe these revisions address the reviewers' main concerns while preserving the original research question and scope of GramDelta. The corresponding revisions have been updated in the PDF and supplementary materials.

AuthorsOpenReview ↗

Final Note of Appreciation

We are sincerely grateful to all three reviewers for their thoughtful feedback, constructive suggestions, and recognition of the improvements made to our work. We will ensure that the camera-ready version further incorporates the key clarifications and findings into the main paper, with more detailed experimental results and supporting analyses provided in the appendices and supplementary materials. We also sincerely thank the Area Chair for the time and consideration given to our submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.