InstaGrammar: Compiling Stack Signatures for Grammar-Constrained Decoding

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.