- 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
-
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.
-
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
-
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.
-
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
- 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?
- 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.
- How do the decoding speeds of GramDelta and XGrammar compare when the grammar remains unchanged throughout generation?
- What practical applications need grammar rules to change during generation while allowing the set of valid outputs only to expand?
2 comments
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.
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→c, the token
acmust be admitted. We agree that the original frontier-based mask-reuse condition was insufficient: the parser state after the committed prefixxremains unchanged, but the new production can become applicable after scanning the first byteaof 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→c, and then scansc, correctly admittingac.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:
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
sof typeStringand reachess., 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.