acceptodds
Under review as a conference paper at ICLR 2027

InstaGrammar: Compiling Stack Signatures for Grammar-Constrained Decoding

Abstract

Grammar-constrained decoding (GCD) enforces syntactic constraints by masking invalid tokens at each generation step. Context-free grammars complicate this operation because token validity can depend on an unbounded parser stack. We present INSTAGRAMMAR, which compiles stack-dependent compatibility for a fixed grammar and vocabulary into finite response signatures. A first-pop decomposition makes these signatures compositional: a push follows a compiled transition and a pop restores the signature saved in its frame, so online masking selects and combines precomputed rows instead of simulating candidate tokens against the stack. On MaskBench, INSTAGRAMMAR’s mean per-token matcher cost is 7.4 μs, falling to 3.6 μs when a grammar is reused, with a P99 of 10 μs under reuse against 118 μs for llguidance and 604 μs for XGrammar. It is faster than llguidance on 99.7% of schemas under reuse. These gains cost more preprocessing, a median of 96 ms per schema, recovered at mean per-token cost after about 1,800 (XGrammar) and 7,500 (llguidance) tokens of grammar reuse. In vLLM serving on schemas where existing engines incur heavy online cost, INSTAGRAMMAR delivers 5.4–5.9 times XGrammar’s throughput and 1.6–1.9 times llguidance's.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Constrained Generation, Structured Generation, Decoding, Neurosymbolic, Grammar Constrained Decoding

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_eVfVOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents InstaGrammar, an approach for reducing the online cost of grammar-constrained decoding. For a fixed grammar and vocabulary, it groups parser stacks according to their answers to token-suffix queries across parser states. A first-pop decomposition allows these stack signatures to be updated incrementally: a push follows a precomputed transition, while a pop restores a previously saved signature. During decoding, the system selects and combines precomputed mask information instead of testing candidate tokens against the full stack. The evaluation includes MaskBench matcher timings, compilation and storage measurements, and vLLM serving experiments. The main empirical benefit is lower matcher latency, particularly in the tail, with substantial serving improvements on schemas that are expensive for existing engines.

Critical strengths
  1. The method is principled and well justified. It uses incrementally maintained stack signatures to reduce online masking work, with theoretical analysis supporting the construction.
  2. The experimental results demonstrate practical benefits. InstaGrammar substantially reduces matcher latency and improves end-to-end serving throughput.
Critical weaknesses

Missing comparison with the closest prior work. PSC also precomputes masks by classifying parser stacks. InstaGrammar avoids PSC’s repeated stack traversal by maintaining signatures incrementally, but the experiments do not compare the two. The reported results therefore do not establish the practical benefit of this distinction. A direct comparison of runtime, preprocessing, and memory costs is needed to assess the contribution over the closest existing approach.

Questions for authors
  1. Can you provide a comparison with PSC on the grammars supported by both systems, using the same tokenizer and token traces? In particular, how do online matcher time, compilation time, and memory usage compare, and how does the online difference change with stack depth?
  2. What are the main causes of the validation failures in Table 4? Are they due to unsupported JSON Schema features or errors in the implementation? Please provide a breakdown of the causes.
2 comments
AuthorsOpenReview ↗

Response to Reviewer eVfV

We thank the reviewer for their positive assessment and clear questions. We hope that our answers below are sufficient to address any remaining concerns.

Q1: Comparison with PSC. We added PSC to the MaskBench benchmark runner in order to evaluate their system under conditions consistent with our other experiments. Both systems ran on all 9,795 MaskBench schemas with test instances, with the same Llama 3.1 tokenizer, compute node, and per-schema limits (900 s, 28 GiB).

PSCInstaGrammar
Median / P99 compile to first mask (s)28.2 / 472.50.21 / 4.1
Schemas compiled, of 9,7958,0389,794
Median peak memory (GiB, 87 schemas)2.450.46
Per-token mean, original pass (µs)2.808.30-8.34
Per-token mean, regenerated pass (µs)1.711.44-1.45
Regenerated: schemas where InstaGrammar is faster92-93%

Compile times are over the 8,038 schemas both systems compile. Per-token rows use the 4,034 of them where both systems replay identical token traces, with ranges over our two runs. The traces differ on 4,004 schemas because the two systems stop at different tokens. On 3,201 of them PSC rejects a valid instance or raises an error during replay, and on 642 both reach the same verdicts but reject at different positions. Each instance is replayed twice with the same tokens; in the regenerated pass, parser configurations have been seen before.

Stack depth. To isolate stack depth, we replayed one trace per depth on expr: "a" | "(" expr ")" three times, and report per-token means below:

Nesting depth101001,00010,000
PSC (µs)3.134.8023.75212.83
InstaGrammar (µs)1.731.531.191.32

In summary:

  • Preprocessing. InstaGrammar compiles 125x faster at the median, compiles 9,794 schemas against PSC's 8,038 (82%), and uses about one fifth of the memory. It finds signatures bottom-up without building and determinizing PSC's global automaton.
  • Online, at MaskBench depths. In the regenerated pass, costs are close and InstaGrammar is faster on 92-93% of schemas. PSC is generally faster in the first pass.
  • Online, with depth. PSC re-runs its classifier over the stack at every step, so its per-token cost grows linearly past depth 100 (4.80 µs at 100, 212.8 µs at 10,000). InstaGrammar's stays between 1.2 and 1.7 µs.

Q2: Attribution of the Table 4 failures. Every engine suffers some errors on the MaskBench JSON Schemas. These engines first translate the schema into a grammar, which can introduce failures due to inconsistency between the resulting grammar and the true schema specification. Llguidance refuses 886 of the 9,795 schemas, and XGrammar compiles all but 142 but over-approximates keywords, so 1,526 of the schemas it compiles produce an error. Counting both failure types, the version of InstaGrammar submitted with our paper (which incurs 2,073 schemas with an error) was in the same range as XGrammar (1,668).

As stated above, these errors do not come from grammar compilation or the matcher. They come from the preprocessing step that converts JSON Schema to a grammar. We checked each schema's first failing instance and found that 1,677 of the 2,073 failures (81%) are keywords the converter did not faithfully encode. A brute-force PDA simulation on 1,000 random schemas agrees with our masks and EOS decisions everywhere (see acfZ, Q1).

We therefore made targeted converter fixes: numeric bounds, patternProperties, ECMA-262 pattern semantics, references, and common format values. Failures fall from 2,073 to 583, and median compile time is unchanged:

CauseOriginal converterAfter fix
Unsupported: format, numeric bounds, multipleOf, uniqueItems, not, dependencies, min/maxProperties1,269177
Partial: oneOf, anyOf, pattern, length bounds15766
Keys out of declared order251269
Other: additionalProperties, type, enum14946
Not attributed (valid instance rejected)24523
Matcher configuration cap22
Total2,073583

With the fixes, all three engines on 9,795 schemas and 37,011 tests:

InstaGrammarllguidanceXGrammar
Schemas that do not compile1886142
Compiled schemas with an error583201,526
Correct decisions, of 37,01136,09133,11833,476

Errors are false accepts, false rejects, or runtime errors. Tests on schemas that do not compile count as incorrect. InstaGrammar now compiles all but one schema, fails on fewer schemas than either baseline in total (584, against 906 for llguidance and 1,668 for XGrammar), and makes the most correct decisions.

Thank you for the clarifications. The additional experiments adequately address my concerns, and I maintain my positive score.

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

This paper presents InstaGrammar, an efficient grammar-constrained decoding method based on stack signatures. Through a first-pop decomposition, the proposed approach compiles stack-dependent token validity into finite response signatures and maintains them incrementally during decoding, avoiding repeated traversal of the complete parser stack. The method is evaluated on JSON Schema-derived grammars and further integrated into vLLM, demonstrating improvements in online latency and serving throughput.

Critical strengths
  1. The paper addresses the overhead of stack-dependent online masking in grammar-constrained decoding through a systematic approach. The first-pop decomposition and formal construction of stack signatures are technically interesting and provide a theoretical foundation for incrementally maintaining stack-dependent information.

  2. The experimental results are promising, particularly on schemas with expensive online masking, where the proposed method substantially reduces latency and improves tail performance, leading to significant serving throughput gains.

  3. The paper provides a reasonably comprehensive experimental analysis, including comparisons with existing constrained decoding engines, compilation overhead, and break-even analysis, which helps characterize the benefits and applicable scenarios of the proposed approach.

Critical weaknesses
  1. The significance of the algorithmic novelty relative to prior work remains somewhat unclear. PSC has already demonstrated that stack-dependent token validity can be compiled into finite-state parser stack classification with precomputed vocabulary masks. In comparison, the main additional contribution of this paper appears to be the compositional construction and incremental maintenance of stack signatures, avoiding repeated stack traversal in PSC's original approach. Although the first-pop decomposition is technically meaningful, the paper does not sufficiently clarify its distinct algorithmic advantages over existing stack-classification methods and potential incremental alternatives, such as differences in state-space size, compilation complexity, or practical runtime efficiency. Consequently, the extent of the algorithmic advancement remains insufficiently established.

  2. The experimental setting limits the assessment of the method's generality and practical benefits. Although the approach is formulated using a general PDA model, the evaluation primarily focuses on JSON Schema-derived grammars, without direct experiments on other grammar families such as SQL or programming languages. Furthermore, the end-to-end serving evaluation uses only a 1B model, and the most substantial improvements are observed on schemas with high online masking costs. While the paper provides a useful break-even analysis and a randomly sampled control workload, it remains unclear whether similar benefits would hold for more complex grammars, larger language models, or more representative serving workloads.

Questions for authors
  1. Compared with PSC, is the primary algorithmic advantage of the first-pop decomposition and stack-signature representation the elimination of repeated parser-stack traversal? Could the authors further clarify its nontrivial contribution beyond existing finite-state stack-classification techniques?

  2. How would the preprocessing overhead and number of signatures scale on SQL or programming-language grammars? Would the online masking improvements still translate into significant end-to-end serving gains with larger language models?

2 comments
AuthorsOpenReview ↗

Response to Reviewer sxNw

We thank the reviewer for the careful reading. Below we compare directly with PSC, add four programming-language grammars, and evaluate end-to-end throughput across batch and model sizes.

Q1 / W1: Contribution beyond PSC. Our approach differs from PSC in how classes are computed and maintained online, and in measured performance.

  1. Construction. PSC builds a union automaton over stack contents (its Eq. 9), then determinizes and minimizes it. Our first-pop decomposition computes a pushed stack's response vector from the signature beneath it and per-symbol summaries. A worklist therefore finds the signatures bottom-up without building or determinizing a global automaton (Theorem 1).
  2. Online maintenance. Each frame stores its predecessor's signature, so a push is one transition and a pop restores a saved value. PSC re-runs its classifier over the stack at every step.
  3. Practical performance. We ran PSC's released code on all 9,795 MaskBench schemas with test instances (full tables in eVfV, Q1). Median compile time is 0.21 s for InstaGrammar against 28.2 s for PSC (P99 4.1 s vs 472.5 s); InstaGrammar compiles 9,794 schemas against PSC's 8,038, and median peak memory is 0.46 vs 2.45 GiB. When decoding revisits parser configurations, per-token cost is 1.44-1.45 µs against 1.71 µs, and InstaGrammar is faster on 92-93% of schemas. With nesting depth, PSC's cost grows linearly (4.80 µs at depth 100, 212.8 µs at 10,000), while ours stays at 1.2-1.7 µs.

Q2 / W2: Other grammars, larger models, representative workloads.

Our engine is not specific to JSON. We compile Java, Go, SQL and Python grammars using the Llama 3.1 tokenizer and report compilation metrics below. Construction takes under a minute and at most 1.3 GiB. On JSON, compile time also tracks |K| (see acfZ, Q3).

JavaGoSQLPython
Parser states425389208707
Signatures |K|1,0871,42980514,052
Signature compile (s)2.52.91.942.7

Larger models. Masks are computed on the CPU while the GPU runs the forward pass, so a GCD engine slows decoding only when masking takes longer than the forward pass. With a small model the forward pass is short, so engine time shows up directly. On the same GPU, a larger model has a longer forward pass that hides more of the engine's work. We ran the same 155 masking schemas on Llama models from 1B to 70B. We report output throughput in tokens/s by concurrent requests (higher is better), and the engine's mask time per decode step in ms at 64 requests (lower is better):

ModelEngine16642561,024ms/step
1BUnconstrained5,38914,88024,36923,440
IG (ours)5,05513,77121,02522,3810.15
LLG4,3806,45215,20517,7117.1
XGR1,9552,3365,6507,53922.9
3BUnconstrained2,3225,5399,02910,698
IG (ours)2,2915,4118,54610,3900.17
LLG2,2725,1938,42310,5065.1
XGR1,5201,7883,5876,47330.0
8BUnconstrained1,2183,1345,4676,601
IG (ours)1,1933,0465,4446,5420.17
LLG1,1923,0685,4056,5325.4
XGR1,0771,7703,9635,34127.8
70BUnconstrained4661,1521,6842,082
IG (ours)4651,1561,7272,1490.17
LLG4571,1551,7172,1444.8
XGR4561,1171,6832,13624.6

Models are Llama-3.2-1B/3B, Llama-3.1-8B and Llama-3.3-70B (FP8), with vLLM 0.27.1 on one RTX Pro 6000 (two for 70B); throughput is the median over three passes. At 64 requests, InstaGrammar's mask takes 0.15-0.17 ms per step in every configuration, against 4.8-7.1 ms for llguidance and 23-30 ms for XGrammar. Its throughput is 86-96% of unconstrained decoding with the 1B model and at least 94% from 3B on. llguidance roughly matches InstaGrammar from 3B on, and XGrammar's loss shrinks at 8B. With 70B, where the forward pass is long for every engine, all engines tie. InstaGrammar stays close to unconstrained in all of them. Smaller models also make more format errors on their own, so they benefit most from constrained decoding, while larger models rely on it less.

Importance of GCD overhead reductions. Grammar masking is pure CPU-side overhead added to every generated token, so an end-to-end throughput improvement of even 1% translates directly into serving capacity. At industrial scale, 5% higher throughput on structured-output traffic is 5% fewer GPUs for the same load.

Broader applications. Fast GCD is important for high-throughput batched serving, constrained beam search for code and SQL generation, and agentic workflows with structured tool calls. Its impact may be even greater in accelerated decoding. Speculative decoding verifies multiple draft tokens in one target-model pass, while grammar enforcement still steps through each token prefix, so it can become a bottleneck that limits the speedup. The engineering required to integrate our approach into these pipelines is beyond the scope of this paper.

Thank you for the detailed responses and additional experiments. The direct comparison with PSC, the evaluation on programming-language grammars, and the expanded serving experiments across different model sizes have substantially addressed my main concerns.

I have therefore raised my rating from 2 to 3.

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

This paper addresses grammar-constrained decoding (GCD), where the validity of a vocabulary token can depend on an unbounded parser stack. It presents INSTAGRAMMAR, which compiles stack-dependent compatibility for a fixed grammar and vocabulary into finite stack signatures: a first-pop decomposition makes signatures compositional, so a push advances the signature in one transition and a pop restores the signature saved in the removed frame, reducing online masking to table lookups indexed by (state, signature). On MaskBench-driven workloads across six engines, INSTAGRAMMAR achieves the lowest per-token matcher cost (geomean 11.4 μs; mean 3.6 μs and P99 10 μs under reuse), compiles all but 3 of 9,795 schemas, and delivers 5.4–5.9× XGrammar and 1.6–1.9× llguidance vLLM throughput on tail-heavy schemas, at a median preprocessing cost of 96 ms per schema that requires roughly 1,800–7,500 reused tokens to amortize.

Critical strengths
  1. The first-pop decomposition (Theorem 1) and the induced signature DFA (Corollary 2) make stack-equivalence classes compositional, so each push updates the signature in one transition and each pop restores the saved predecessor, turning masking into constant-time table lookup.
  2. It attains the lowest per-token matcher cost among six engines on MaskBench (geomean 11.4 μs, warm P99 10 μs) and 5.4–5.9× XGrammar and 1.6–1.9× llguidance serving throughput on schemas with heavy online cost.
  3. Compilation coverage is substantially better than the baselines: only 3 of 9,795 tested schemas fail to compile, versus 886 for llguidance and 70 for XGrammar.
Critical weaknesses
  1. On the broader 11,306-input suite, INSTAGRAMMAR records 2,073 validation mismatches (Table 4), more than XGrammar's 1,664 and far more than llguidance's 22, with matched-label rates of 13,218/13,958 valid and 19,604/23,035 invalid instances (Appendix A.3); the paper does not attribute these failures across the converter, compiler, and matcher, the runner never checks EOS so "no error" is not a full-mask correctness certificate, and the enforced declared-key-order restriction rejects semantically valid JSON since objects are unordered.
  2. Four of the six Table 1 rows come from archived cluster runs without complete version and hardware pins, the XGrammar row of Table 4 was measured on a different machine and date, and engines ran under different time limits (300 vs 900 s) and address-space limits (14 vs 28 GiB), with CPU affinity and repeated-run variance unrecorded (Appendix A.1); although disclosed, the cross-engine aggregate ratios are not matched-environment comparisons.
  3. The preprocessing burden makes the advantage conditional on schema reuse: median compile is 96 ms with P99 5.88 s and a maximum of 149.8 s, serving tables average about 38 MB per schema, break-even requires roughly 1,800 (XGrammar) or 7,500 (llguidance) reused tokens at mean costs (§5.3), and peak compilation memory is unreported — short-lived dynamic schemas are unlikely to recover the cost.
Questions for authors
  1. Break down the 2,073 validation mismatches by source (converter vs compiler vs matcher), verify full masks and the EOS bit against an independent reference (e.g., brute-force PDA simulation over live stacks) on a random subset to certify matcher correctness, and analyze whether relaxing the declared-key-order restriction is feasible without sacrificing the compilation gains.
  2. Re-run the Table 2 comparison and the serving study on a single machine with pinned versions and identical time/memory limits, recording CPU affinity and multi-run variance, and report per-schema paired speedups; add PSC, the closest prior work (currently compared only in prose and Appendix H), to the same benchmark harness.
  3. Report peak compilation memory and table-size distributions as a function of |K|, include a workload of short-lived schemas without reuse to show where the cost model fails, and provide the per-schema break-even distribution rather than aggregate medians; then extend the signature machinery to SQL and programming-language grammars and quantify how fast the signature space grows in practice.
2 comments
AuthorsOpenReview ↗

Response to Reviewer acfZ

We thank the reviewer for their positive assessment and specific requests.

Q1: Correctness. Validation errors can come from three sources:

  1. Constraints a context-free grammar cannot express exactly. Some JSON Schema keywords are not context-free (uniqueItems, not) or are exponential to encode exactly (unordered keys with required). Every grammar-based engine must refuse or over-approximate them: llguidance refuses 886 of 9,795 schemas, and XGrammar compiles all but 142 but errs on 1,526 of those.
  2. Converter coverage: keywords a grammar can express but our converter did not yet encode, such as numeric bounds, pattern and format.
  3. Implementation errors in signature construction or the online matcher.

All three engines target the online matcher (3); 1 and 2 are frontend choices largely beyond the paper's scope, and the Table 4 errors come primarily from them. With the submitted converter, InstaGrammar had 2,073 failing schemas, comparable to XGrammar’s 1,668, and 81% of these trace to unencoded keywords or key order. Converter fixes (see eVfV, Q2) reduce failures from 2,073 to 583. InstaGrammar now makes the most correct decisions: 36,091 of 37,011, against 33,118 for llguidance and 33,476 for XGrammar.

Oracle and EOS. To rule out (3), we compared InstaGrammar against a brute-force simulation of the parser PDA over live stacks on 1,000 random schemas. Full masks (about 2.1 billion token decisions) and the EOS bit agree at every sampled position, and both accept or reject every test instance identically.

Key order. Accepting any key order falls under (1). An exact encoding for objects with up to 8 properties (still enforcing required) removes 22 of 37 key-order false rejects on a 986-schema sample. It multiplies signatures by about 8x per object with 5–8 properties, however, and 4 schemas then fail to compile. We will offer it as an option and keep declared order as the default.

Q2: Matched environment. The reviewer is correct that the submission used two setups (Appendix A1). We reran all engines under one setup: one node, pinned versions, identical limits (900 s, 28 GiB), over two runs per engine. Values differ slightly from the submission, but trends are the same.

Each test instance is replayed twice with the same tokens: an original pass, and a regenerated pass in which parser configurations have been seen before. Per-token mask time in µs (original / regenerated), over the 6,418 schemas where all three engines finish and replay identical tokens:

MedianP90P99
InstaGrammar9.8/1.222.3/1.739.5/4.7
llguidance39.5/25.972.9/43.9261/231
XGrammar23.8/22.068.2/66.6724/720

InstaGrammar is fastest on 79% of schemas in the original pass and on every schema in the regenerated pass.

Serving. We also reran end-to-end serving under the same conditions (Llama-3.2-1B on one RTX Pro 6000, vLLM 0.27.1, three trials per schema). Output throughput in tokens/s on the 155 schemas with expensive online masking:

Requests16642561,024
Unconstrained5,38914,88024,36923,440
InstaGrammar5,05513,77121,02522,381
llguidance4,3806,45215,20517,711
XGrammar1,9552,3365,6507,539

Values are medians over the three passes, which vary by at most 9%. On 155 random control schemas the engines are close: at 64 requests, 12,469 (InstaGrammar), 12,214 (llguidance) and 11,645 (XGrammar) tokens/s, against 14,578 unconstrained. Our response to sxNw (Q2) adds 3B, 8B and 70B models.

See eVfV (Q1) for a comparison with PSC.

Q3: Preprocessing. The reviewer is correct that InstaGrammar's primary advantage is re-use. We report compilation metrics below. Peak memory is 1.1 GiB median, 6.6 GiB P99 and 24.9 GiB max; the 63 schemas above 8 GiB have mask tables over 1 GiB. Baselines stay under 1 GiB. Over the 9,794 schemas that compile:

|K|SchemasCompile to first mask, median/P90 (s)Table, median/max (MiB)
< 101,4090.10/0.599/251
10-1003,4380.17/0.4217/644
100-1,0004,3620.40/1.7024/2,313
1,000-10,0005303.1/9.690/7,074
≥ 10,0005554/100597/1,527

Short-lived schemas. Among engines with comparable online cost, our preprocessing is cheap: PSC compiles 124x slower at the median. We will make this scope explicit.

Break-even. For each schema, we compute the number of reused tokens nn after which InstaGrammar’s total cost falls below the baseline’s: n=(CIG−CB)/(cb−cIG)n = (C_{IG} - C_B) / (c_b - c_{IG}). Here CC is compile time and cc is the per-token mask time in the regenerated pass. InstaGrammar is faster per token on every schema in that pass, so every schema eventually breaks even.

Tokens, vsP10MeanMedianP90
llguidance3,2007,5008,500-8,60048,000-50,000
XGrammar1,000-1,1001,8009,900-10,00039,000-40,000

Programming languages. See sxNw (Q2) for parser states, signatures and compile times on Java, SQL, Python and Go grammars.

Thank you to the authors for adding new experimental results in response to my concerns. I will therefore maintain my positive score of 3. I hope the authors will incorporate these additional experiments into the next version.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the rebuttal, discussion, and revisions

We thank the AC and all reviewers for their careful and constructive reviews. Of the three reviewers, we've received two responses. The first is from reviewer eVfV, who is satisfied with our response and maintains their positive assessment. The second is from sxNw, who reports that their concerns have been substantially addressed and has raised their score from a 2 to a 3. The reviewers raised four main concerns: how InstaGrammar relates to PSC, whether our comparisons were run under matched conditions, where the validation errors came from, and to what degree our method generalizes to different grammars. Below we summarize our new findings and analyses. The full results tables and details of these experiments can be found in our responses to each reviewer and in our revised submission.

How InstaGrammar compares with PSC (sxNw, eVfV). We added PSC to our benchmark runner and ran both systems on all 9,795 MaskBench schemas under the same conditions. The clearest difference is in preprocessing. InstaGrammar compiles a schema in 0.21 s at the median against 28.2 s for PSC, and it handles 9,794 schemas against PSC's 8,038. At the stack depths found in MaskBench, the two systems have similar online cost, and PSC is somewhat faster on first visits. As nesting deepens, however, PSC must re-scan a growing stack at every step, and its cost rises to 212.8 µs per token at depth 10,000. Ours stays near 1.5 µs. Both differences come from how signatures are built and maintained: the first-pop decomposition finds them bottom-up without constructing a global automaton, and each push or pop updates the signature in constant time.

Matched evaluation (acfZ). We reran all engines under identical conditions and resource limits, and the conclusions are unchanged. InstaGrammar is the fastest engine on 77% of schemas the first time a grammar is used and on every schema once it is reused. Its advantage is largest in the tail, which is what limits serving throughput. Under reuse, its 99th-percentile cost is 11 µs per token, compared with 422 µs for llguidance and 1,278 µs for XGrammar.

Where the validation errors came from (acfZ, eVfV). Tracing each failure to its source showed that most came from JSON Schema keywords our converter did not yet encode accurately, not from grammar compilation itself. To check the matcher directly, we compared it against a brute-force simulation of the parser on 1,000 random schemas, about 2.1 billion token decisions in total, and found complete agreement, including on when generation may end. After targeted fixes to the converter, failing schemas fell from 2,073 to 583, and InstaGrammar now makes the most correct decisions of the three engines (36,091 of 37,011).

Generality and cost (acfZ, sxNw). The method is not specific to JSON. Signatures for Java, Go, SQL and Python grammars are each constructed in under a minute. In serving experiments with Llama models from 1B to 70B, InstaGrammar's masking time stays below 0.3 ms per step at 64 concurrent requests, while existing engines take several to tens of milliseconds. The throughput benefit is largest for smaller models, whose fast forward passes expose masking overhead, and the engines converge at 70B. We also now report compile time alongside per-token cost in Table 2 and by signature count in the appendix.

Revisions. We have uploaded a revised PDF with changes marked in blue. It adds the comparison with PSC that all reviewers requested, replaces the archived runs in Table 2 with the matched-environment results, and includes the correctness outcomes and the source of the validation errors (eVfV Q2) and the programming-language and model-scaling results. It also expands the limitations section to cover key order, preprocessing cost and short-lived schemas.

We thank the reviewers again for their engagement. Their feedback has substantially strengthened the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.