- 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
- The method is principled and well justified. It uses incrementally maintained stack signatures to reduce online masking work, with theoretical analysis supporting the construction.
- 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
- 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?
- 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
Thank you for the clarifications. The additional experiments adequately address my concerns, and I maintain my positive score.
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).
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:In summary:
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-262patternsemantics, references, and commonformatvalues. Failures fall from 2,073 to 583, and median compile time is unchanged:format, numeric bounds,multipleOf,uniqueItems,not, dependencies,min/maxPropertiesoneOf,anyOf,pattern, length boundsadditionalProperties,type,enumWith the fixes, all three engines on 9,795 schemas and 37,011 tests:
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.