GRID: Grammar-Railed Decoding for Enterprise SQL Generation

# Grammar-Railed Decoding for Enterprise SQL GenerationA condensed version of this paper is under review at KDD 2027.
Source: [https://arxiv.org/html/2607.11951](https://arxiv.org/html/2607.11951)
\(July 2026\)

###### Abstract

Large language models can write SQL, but enterprise deployment demands more than plausible text: outputs must be syntactically valid, must respect per\-role and per\-schema policy, must come with provable—not best\-effort—guarantees, must not slow down as generations grow, and must leave a compliance\-grade record of every decision\. We present GRID \(Grammar\-Railed Decoding\), a grammar\-constrained decoding engine that keys exact next\-token masks on*parser configurations*\(lexer scan state×\\timesLALR\(1\) stack\) rather than on token sequences, uses the incrementally advanced LALR\(1\) parser itself as a viable\-prefix oracle, and bridges LLM tokens to grammar terminals through a byte\-level trie walk with a context\-independent/context\-dependent split that makes cache\-key soundness hold by construction\. Role\-based access control is compiled*into the language*: role projections subset the grammar’s productions and schema lexicons restrict identifier terminals, so forbidden verbs and identifiers are unreachable at mask level\. Four guarantees—soundness, completeness, termination, and near\-constant per\-token cost \(requirement R\)—are stated with explicit preconditions and each is paired with the test or benchmark that verifies it\. Rust kernels bring the warm serving step to 1\.33 µs per request and the per\-token mask to a 3\.6–6\.7 µs median—ahead of llguidance at both p50 and p90 on both benchmarked tokenizers, with zero false rejects, while llguidance keeps the flattest p99\. On a declared H100 SXM5 runner, end\-to\-end serving overhead under vLLM is\+1\.51%\+1\.51\\%time\-per\-output\-token at batch 32 with 27\.3 ms cold\-schema specialization; a fresh \(never\-seen\) schema pays∼\\sim0\.7 ms first\-token latency and then decodes at1\.00×1\.00\\timeswarm speed\. A v7 kernel that keeps the entire cold mask miss in Rust \(fused walk→\\toblob→\\toregister, one GIL\-released call\) holds the warm co\-tenants’ worst engine step to 15\.3 ms on real hardware; the one residual cost—a transient co\-batched TPOT slowdown \(∼\\sim34%\) during the fresh schema’s∼\\sim0\.66 s specialization window—is genuine host CPU/memory\-bandwidth contention between the cold walk and the engine forward loop \(it shrinks as walk threads grow\), a compute\-isolation trade\-off noted as future work rather than a defect\. Per\-token guard cost is position\-flat \(slope≈0\\approx 0atn=16,000n\{=\}16\{,\}000, all nesting depths\)\. On Spider, constrained decoding is worth\+13\+13execution\-accuracy points at 0\.5B; at 7B the mask alone is worth∼\\sim\+1\+1point, and one checker\-guided repair pass over the provably mask\-unenforceable residue \(column\-level policy\) lifts execution to94\.5%94\.5\\%and EX to\+2\.3\+2\.3over unconstrained\. A hash\-chained per\-token audit trail replays bit\-identically \(1,000 generations across a cache\-namespace rollover;100%100\\%tamper detection\)\. We state honestly what the mask cannot do—distribution faithfulness, column\-level RBAC, non\-LALR\(1\) languages—and where measured cost remains \(cold trie walks; the serving cold\-window compute contention; one characterized engine\-side artifact exogenous to GRID\)\.

## 1Introduction

We are concerned with generating SQL \(and, more generally, sentences of any LALR\(1\)\-parsable language\) from a large language model under the operating conditions of an enterprise CRUD/RBAC deployment\. In that setting, “the model usually writes valid SQL” is not an acceptable contract\. Six problems, each of which shapes the design, must be solved*simultaneously*:

1. P1\.Validity and policy, jointly\.Output must parse under the SQL dialect*and*comply with per\-role policy \(allowed verbs, banned clauses\) and per\-schema vocabulary \(only real tables and columns\)\. Policy is not a post\-hoc filter: a role that may onlyselectmust be unable to emitdeleteat all, and identifiers must be schema\-valid*by construction*\.
2. P2\.Provable guarantees\.Soundness \(never emit a token that leaves the language’s prefix set\), completeness \(never block a token that could still lead to a valid sentence\), and termination \(every stop is a complete sentence\) must be theorems with explicit preconditions, each paired with the test that verifies it—not emergent properties of a test suite\.
3. P3\.Flat per\-token cost \(requirement R\)\.Guard\-rail cost per token must be amortizedO​\(1\)O\(1\)in the current output lengthnn\(worst case bounded by grammar/nesting constants, never bynn\), so total guard cost isO​\(n\)O\(n\)over a generation\. A guard whose per\-token cost grows with context is unusable for long generations; §[8\.2](https://arxiv.org/html/2607.11951#S8.SS2)shows a 2023\-era system for which per\-token overhead grows by∼\\sim1\.19 ms*per position*\.
4. P4\.A replayable audit trail\.In a compliance setting, “what was the model allowed to say at steptt, and why?” must be answerable after the fact: a hash\-chained, per\-token record of permit/block decisions, replayable bit\-identically against versioned grammar artifacts\.
5. P5\.Serving reality\.Production decoding is batched, grammars are heterogeneous across co\-batched requests, and new schemas arrive while a hot batch is running\. The guard must overlap mask computation with the GPU forward pass, never stall co\-batched requests on one request’s cold miss \(the*cold\-schema\-into\-hot\-batch*problem\), and never substitute an approximate mask under deadline pressure\.
6. P6\.An honest boundary for the unenforceable residue\.Some policy is*provably*not enforceable by any left\-to\-right context\-free mask—column\-level RBAC being the canonical case \(Proposition[11](https://arxiv.org/html/2607.11951#Thmproposition11)\)\. The system must name that boundary rather than blur it, enforce it post\-parse, and—where a capable model is available—convert the named violations into a checker\-guided repair loop\.

GRID answers these with one architectural idea and its consequences:*key everything on parser configurations*\. A configuration—the pair of the lexer’s scan state over a partial lexeme and the LALR\(1\) parser stack—is exactly the information that determines which continuations are viable\. Masks are computed from configurations, cached under configuration\-derived keys whose soundness is a stated obligation \(a Myhill–Nerode\-style refinement, §[4\.3](https://arxiv.org/html/2607.11951#S4.SS3)\), and audited under a rolling configuration hash\. The mask cost therefore tracks the*grammar configuration*, not the output position, which is requirement R by construction; the benchmarks in §[8](https://arxiv.org/html/2607.11951#S8)measure that this holds on real vocabularies atn=16,384n=16\{,\}384\.

#### Contributions\.

\(1\) A formal framework for configuration\-keyed constrained decoding: the incremental LALR\(1\) parser as a viable\-prefix oracle with exact EOS gating under table compression \(§[3](https://arxiv.org/html/2607.11951#S3)\); a byte\-level token↔\\leftrightarrowterminal bridge with a context\-independent/context\-dependent split that makes cache\-key soundness hold by construction \(§[4](https://arxiv.org/html/2607.11951#S4)\); the cache\-key soundness obligation OBL\-KEY1 and the identifier composition rule, with the scanner normal form that maximizes sound cross\-request sharing \(§[4\.3](https://arxiv.org/html/2607.11951#S4.SS3)\)\. \(2\) Four guarantees stated as propositions with explicit preconditions, including the honest negative result that column\-level RBAC is mask\-unenforceable \(§[5](https://arxiv.org/html/2607.11951#S5)\)\. \(3\) A system realizing the framework—grammar pipeline, Rust kernels \(v4→\\tov7, warm serving step7\.39→1\.337\.39\\to 1\.33µs/request, then a v7 fused cold\-miss path\), two\-tier write\-back mask cache, a serving contract for batched heterogeneous decoding, and a hash\-chained audit log \(§[6](https://arxiv.org/html/2607.11951#S6)\)—with worked examples \(§[7](https://arxiv.org/html/2607.11951#S7)\)\. \(4\) A committed benchmark record: per\-token mask latency against XGrammar, llguidance, and Outlines on two tokenizers; requirement\-R slope measurements; MaskBench; Spider execution accuracy with checker\-guided repair; and an end\-to\-end vLLM serving record including a cold\-miss stress arm \(§[8](https://arxiv.org/html/2607.11951#S8)\)\.

#### Design lineage\.

The initial patent filing captured an early, partial snapshot of this design \(v0\.0\.5, designed August 2023\): a precomputed validity table over token sequences against a pushdown automaton, with decode\-time logit masking\. Planned iteration carried the design forward: v0\.0\.6 \(September 2023\) already outperformed the July\-2023 release ofguidanceon the scaling benchmarks of that era, and v0\.0\.7 \(November 2023\)—the system described in this paper, and the line the final patent application followed—replaced sequence keys with configuration keys and acceptance semantics with prefix viability, added the byte\-level token↔\\leftrightarrowterminal bridge, the write\-back cache, RBAC/schema projections, the audit chain, and checker\-guided repair; the work has continued to improve since\. Sections[3](https://arxiv.org/html/2607.11951#S3)–[4](https://arxiv.org/html/2607.11951#S4)present the design analysis behind the two load\-bearing revisions\. The design drew inspiration from published work—notably Willard and Louf’s Outlines paper\[[1](https://arxiv.org/html/2607.11951#bib.bib1)\], whose finite\-state\-machine formalization of guided generation this paper deliberately parallels in register—while GRID’s design and implementation are our own throughout\.

## 2Preliminaries

#### Masked decoding\.

LetVVbe a tokenizer vocabulary with\|V\|=N\|V\|=Nand letΣ\\Sigmabe the byte alphabet\. An autoregressive LM defines logits𝜶=LM​\(s1\.\.t,𝜽\)∈ℝN\\boldsymbol\{\\alpha\}=\\mathrm\{LM\}\(s\_\{1\.\.t\},\\boldsymbol\{\\theta\}\)\\in\\mathbb\{R\}^\{N\}; guided generation applies a maskm∈\{0,1\}Nm\\in\\\{0,1\\\}^\{N\}before sampling,𝜶~=m⊙𝜶\\tilde\{\\boldsymbol\{\\alpha\}\}=m\\odot\\boldsymbol\{\\alpha\}\(implemented as an in\-placemasked\_fill\_\(−∞\-\\infty\)\), and samplesst\+1∼Categorical​\(𝜶~\)s\_\{t\+1\}\\sim\\mathrm\{Categorical\}\(\\tilde\{\\boldsymbol\{\\alpha\}\}\)\. Constructingmmat each step is the entire problem: done naively it costs a parse of the whole prefix per candidate token per step\.

#### Tokens are byte strings\.

Each token has a canonical spellingbytes:V→Σ∗\\mathrm\{bytes\}\\colon V\\to\\Sigma^\{\\ast\}\(token\_bytes\): byte\-level\-BPE unicode remaps inverted, SentencePiece/BPE space markers normalized to0x20, byte\-fallback literals<0xNN\>mapped to their byte\. One definition serves the trie build, the fast path, and the reference oracle\. Distinct token ids may share a spelling \(*alias classes*\); masks are over ids, not spellings\.

#### Three grammar layers, one language\.

- •L1 \(dialect core\)\.A CFGG=\(𝒩,T,P,S\)G=\(\\mathcal\{N\},T,P,S\)whose terminalsτ∈T\\tau\\in Tcarry regular lexeme languagesRτ⊆Σ∗R\_\{\\tau\}\\subseteq\\Sigma^\{\\ast\}, with an ignored subsetI⊆TI\\subseteq T\(whitespace, comments\) that is first\-class\. Production SQL grammars \(PostgreSQL, MySQL, SQLite\) are LALR\(1\), so deterministic\-PDA coverage suffices\. Lexing is maximal munch over the union automaton with*contextual resolution*: a forced emission event carries the full candidate terminal set at the longest match and the consumer picks the highest\-priority*parser\-viable*candidate \(this is what letsTABLE\_NAMEandCOLUMN\_NAMEshare one regex, and what resolves JSON’s property\-key\-vs\-string overlap with no new mechanism\)\.
- •L2 \(role projection\)\.A production subsetProle⊆PP\_\{\\mathrm\{role\}\}\\subseteq P\(verb subsets, clause bans\) followed by*mandatory*useless\-symbol elimination and a verifiedL​\(Grole\)≠∅L\(G\_\{\\mathrm\{role\}\}\)\\neq\\emptyset\. Reducedness is load\-bearing: without it, “non\-empty action set⇒\\Rightarrowviable prefix” fails and dead ends return\.
- •L3 \(schema lexicon\)\.For identifier categoriesC⊆TC\\subseteq T, finite allow\-listsWc⊆Σ∗W\_\{c\}\\subseteq\\Sigma^\{\\ast\}realized as lexer tries; the lists are generated from the database catalog \(information\_schema\)\. Precondition, validated at guide build rather than assumed:Wc⊆RcW\_\{c\}\\subseteq R\_\{c\}for every category \(each allowed word must be scannable to an accepting state of its terminal\)\.

The constrained languageL=L​\(Grole,schema\)L=L\(G\_\{\\mathrm\{role\}\},\\mathrm\{schema\}\)is the set of byte strings that lex and parse under the projected grammar with every category\-cclexeme inWcW\_\{c\}\. Both the policy bundle and the schema snapshot are fingerprinted, immutable inputs; grammars, tries, and reserve tables are content\-addressed artifacts\.

## 3The viable\-prefix oracle

### 3\.1Design analysis: why sequence keys and acceptance semantics fail

The v0\.0\.5 design snapshot precomputed an in\-memory table tagging LLM*token sequences*as accepted or rejected by a pushdown automaton, and masked per step from table lookups\. Two observations, made during the planned design review of that snapshot, force the shape of everything that follows\.

###### Proposition 1\(Sequence\-keyed tables scale combinatorially\)\.

A total validity table over token sequences of length≤m\\leq mhasΘ​\(\|V\|m\)\\Theta\(\|V\|^\{m\}\)entries\. At\|V\|=32,768\|V\|=32\{,\}768andm=3m=3this is already≈3\.3×1013\\approx 3\.3\\times 10^\{13\}entries \(≈400\\approx 400TB at 12 bytes/entry\); atm=18m=18it exceeds the number of atoms in the observable universe\.

A “representative subset” of that table is defined by outcome, not by a construction, so it offers no build recipe\. The information the table was trying to enumerate is, however, finitely presentable: by the viable\-prefix property of LR automata\[[2](https://arxiv.org/html/2607.11951#bib.bib2)\], the set of viable prefixes of an LR grammar is characterized by the parser’s configurations, a*grammar\-sized*key space \(10410^\{4\}–10610^\{6\}for SQL\-class grammars\)\.

###### Proposition 2\(Acceptance semantics deadlock at step 1\)\.

Let the tag semantics be “the PDA accepts this sequence” \(membership inLL\)\. For anyLLcontaining no sentence of length one token, every single\-token continuation of the empty prefix is tagged rejected, so the step\-1 mask is empty and generation cannot start\. Masking requiresPrefix​\(L\)=\{w:∃w′,w​w′∈L\}\\mathrm\{Prefix\}\(L\)=\\\{w:\\exists w^\{\\prime\},\\ ww^\{\\prime\}\\in L\\\}, notLL\.

Both conclusions are constructive, not merely destructive: they identify the correct key space \(configurations\) and the correct semantics \(prefix viability\), which the rest of this section formalizes\.

### 3\.2Configurations and the correct\-prefix property

###### Definition 1\(Parser configuration\)\.

A*configuration*is a pairκ=\(σ,ρ\)\\kappa=\(\\sigma,\\rho\)whereσ\\sigmais the LALR\(1\) parser stack \(a persistent, immutable\-node chain of states\) andρ\\rhois the lexer scan state over the current partial lexeme—concretely the remainder bytesrrof the single in\-progress lexeme, which determine the scanner\-DFA state, the maximal\-munch hypothesis set, and the last\-accept position deterministically\.

###### Definition 2\(Viable prefix\)\.

w∈Prefix​\(L\)⇔∃w′∈Σ∗:w​w′∈Lw\\in\\mathrm\{Prefix\}\(L\)\\iff\\exists w^\{\\prime\}\\in\\Sigma^\{\\ast\}:w\\,w^\{\\prime\}\\in L\. Operationally: the incremental scan\-and\-shift ofwwsucceeds and the trailing partial lexeme is live for some allowed\-or\-ignored terminal\.

###### Proposition 3\(The incremental parser is the oracle\)\.

Under the preconditions of §[2](https://arxiv.org/html/2607.11951#S2)\(reduced projected grammar; validated lexiconsWc⊆RcW\_\{c\}\\subseteq R\_\{c\}\), the incrementally advanced LALR\(1\) parser with the maximal\-munch contextual lexer accepts exactlyPrefix​\(L\)\\mathrm\{Prefix\}\(L\): by the correct\-prefix property\[[3](https://arxiv.org/html/2607.11951#bib.bib3)\], an LR parser detects an error at the first terminal that cannot extend any sentence, so “no error so far”≡\\equiv“viable prefix\.” No separate recognizer is needed\.

Two refinements make this exact in practice rather than merely in principle\.

#### Allowed terminals under table compression\.

LALR tables with default reductions over\-approximate raw action rows \(spurious reduces\)\. The allowed\-terminal set is therefore computed by*simulation*:A​\(σ\)=\{τ:simulate​\(σ,τ\)​reaches a SHIFT\}A\(\\sigma\)=\\\{\\tau:\\mathrm\{simulate\}\(\\sigma,\\tau\)\\text\{ reaches a SHIFT\}\\\}, wheresimulateruns the reduce chain on a virtual overlay stack \(pop\|rhs\|\|\\mathrm\{rhs\}\|, GOTO, repeat\) until shift or error\. Cost isO​\(\|row\|×depth\)O\(\|\\mathrm\{row\}\|\\times\\mathrm\{depth\}\)worst case, amortized far less, and memoized per stack node\.

#### EOS gating by reduce\-chain simulation, mid\-lexeme aware\.

EOS may enter the mask only when the current output is a*complete sentence*\. A raw row read is wrong twice: compressed tables have spurious reduces, and after\.\.\.FROM tthe pending lexemetis a complete identifier still awaiting maximal\-munch finalization—the stack alone would wrongly report EOS illegal\. The rule: EOS is legal iff \(the remainder is empty*or*the pending lexeme finalizes as exactly one winning hypothesis\) and, after virtually shifting that finalized terminal on a scratch stack, ACCEPT is reachable via the reduce chain of$end\.

## 4The token–terminal bridge

LLM tokens do not align with grammar lexemes:sel\+ectspellsSELECT, and schema identifiers are never single tokens\. Masking out “fragment” tokens destroys completeness; admitting them requires scoring every token’s bytes against the live configuration\. The early design snapshot illustrated this misalignment and left the mechanism as later work; this section is that mechanism\.

### 4\.1The trie walk and the exact mask

###### Definition 3\(Token trie\)\.

The*token trie*is a byte trie over\{bytes​\(t\):t∈V\}\\\{\\mathrm\{bytes\}\(t\):t\\in V\\\}, stored as one DFS\-contiguous array of packed 8\-byte nodes \(edge byte, token id, subtree size\) plus an alias table mapping each node to*all*token ids sharing its spelling\. One trie per tokenizer fingerprint; special tokens are excluded and permanently masked \(EOS enters masks only via the explicit gate\)\.

###### Definition 4\(The mask\)\.

For configurationκ\\kappawith current outputww,

M​\(κ\)=\{t∈V∖\{EOS\}:w⋅bytes​\(t\)∈Prefix​\(L\)\}∪\{EOS​iff​w∈L\}\.M\(\\kappa\)\\;=\\;\\\{\\,t\\in V\\setminus\\\{\\mathrm\{EOS\}\\\}:w\\cdot\\mathrm\{bytes\}\(t\)\\in\\mathrm\{Prefix\}\(L\)\\,\\\}\\;\\cup\\;\\\{\\,\\mathrm\{EOS\}\\ \\text\{iff\}\\ w\\in L\\,\\\}\.

M​\(κ\)M\(\\kappa\)is computed by a DFS over the trie that carries anO​\(1\)O\(1\)\-updatable scan state per frame \(DFA state, current segment, last\-accept, pending forced\-emission cascade\): a byte that kills the DFA triggers maximal\-munch emission of the last accept and requeues the unconsumed tail\. Rejection is monotone under extension, so rejected subtrees are skipped wholesale via the packed subtree size\. At identifier positions the DFA runs against the L3 trie intersection\. Masks are complete over*ids*via alias expansion\.

### 4\.2The context\-independent/context\-dependent split

###### Proposition 4\(Boundary\-crossing tokens are not\(ρ,A\)\(\\rho,A\)\-determined\)\.

Let tokentt’s bytes cross a terminal boundary*and continue*\(e\.g\.’\),’or’1;’\): they complete a terminalτ1\\tau\_\{1\}and begin material beyond it\. The viability ofttatκ=\(σ,ρ\)\\kappa=\(\\sigma,\\rho\)depends on the allowed\-terminal set*after shifting*τ1\\tau\_\{1\}, i\.e\. on the stackσ\\sigma\. Hence no cache entry keyed only on the lexer state and the current allowed setAAcan decidettsoundly\.

The walk therefore classifies every admitted token asCI\(context\-independent: resolvable within the current lexeme, or ending exactly at one terminal boundary with that terminal inAA\)—cacheable—orCD\(context\-dependent: boundary\-crossing continuation\)—returned as a residue list and checked against the*live stack*every step, never cached\. Without this split, the cache\-key soundness obligation of §[4\.3](https://arxiv.org/html/2607.11951#S4.SS3)is violated*by construction*, not merely unverified\. The CD residue is the main hot\-path cost and gets its own machinery:

#### Verdict\-equivalence grouping\.

The per\-step verdict of a CD entry depends on the entry only through its per\-event candidate terminal sets, its segments and trailing remainder*only via the lexicon predicates*, and the live set of its remainder’s scan state\. Entries are therefore partitioned once, at publish time, into*verdict\-equivalence classes*; each step evaluates one stack\-dependent verdict per class and extends the mask with the class’s alias\-expanded ids\. On the SQL bench this turned∼\\sim25k per\-step entry checks into∼\\sim150 class verdicts \(measured mean 143–150 classes/step atn=16,000n\{=\}16\{,\}000; §[8\.2](https://arxiv.org/html/2607.11951#S8.SS2)\), and a later kernel round that keyed classes by verdict equivalence instead of raw bytes collapsed∼\\sim55k singleton groups to∼\\sim1\.4k classes, a9\.3×9\.3\\timescold\-build reduction \(§[6\.2](https://arxiv.org/html/2607.11951#S6.SS2)\)\.

### 4\.3Configuration\-keyed caching: OBL\-KEY1 and the identifier rule

The write\-back mask cache carries the v0\.0\.5 table’s spirit—precomputed where cached, computed on miss—to its workable form: entries are keyed on configurations, published idempotently \(content\-hashedentry​\_​id=BLAKE2b​\-​128​\(key​‖encoding tag‖​payload\)\\mathrm\{entry\\\_id\}=\\mathrm\{BLAKE2b\\text\{\-\}128\}\(\\text\{key\}\\,\\\|\\,\\text\{encoding tag\}\\,\\\|\\,\\text\{payload\}\), so racing writers produce the same id\), immutable, and versioned under namespaces that roll over when grammars are superseded\.

###### Definition 5\(T1 key\)\.

The per\-grammar \(T1\) cache key of a configuration is

k​\(κ\)=\(kind∈\{ident,generic\},r,sorted​\(A\),schema​\_​fp\),k\(\\kappa\)=\\big\(\\,\\mathrm\{kind\}\\in\\\{\\text\{ident\},\\text\{generic\}\\\},\\;r,\\;\\mathrm\{sorted\}\(A\),\\;\\mathrm\{schema\\\_fp\}\\big\),whererris the remainder bytes \(which determine the lexer scan state\),AAthe allowed\-terminal signature from the live stack, and the schema fingerprint is carried by identifier\-position keys as a*distinct key type*\.

###### Proposition 5\(Cache\-key soundness obligation, OBL\-KEY1\)\.

Any two configurations sharing a key must produce byte\-identical context\-independent masks: the key must refine the Myhill–Nerode classes of the \(lexer product\-DFA×\\timesallowed\-terminal set×\\timesidentifier\-lexicon\) product\. The CD residue is exempt*because it is never cached*\.

OBL\-KEY1 is verified, not assumed: differential tests check cache\-on≡\\equivcache\-off over randomized replays including cross\-role hits, and publish is content\-addressed so a racing writer of the same key with a different mask trips a runtime assertion\.

###### Proposition 6\(Identifier composition rule\)\.

At identifier positions the mask must come from the L3 allow\-list trie intersection; unioning a cached generic\-identifier verdict is unsound\. A generic verdict admits tokens spelling*forbidden*identifiers, and the parser will not reject them later—they are grammatical*as identifiers*—so the error would be a silent RBAC violation, invisible to any downstream syntactic check\.

The rule is enforced structurally: identifier\-position keys are a distinct key type that cannot collide with generic keys, and consulting a generic entry at an identifier position raises an error in all builds \(a test injects the condition and asserts it fires\)\.

#### The cross\-family tier \(T2\) and the scanner normal form\.

A second tier shares entries across the grammar*family*—the enterprise shape is many roles×\\timesschemas over one dialect\. Role projections share the L1 terminal numbering \(assigned at freeze; projections subset productions, never renumber\), so two roles reaching the same normalized configuration share entries\. To maximize sharing soundly, non\-identifier keys normalize the remainder to the*genN scanner normal form*: scanningrrwith last\-accept tracking yields\(q,ℓ,p\)\(q,\\ell,p\)—the live DFA stateqq, the last\-accept lengthℓ\\ell, and the last\-accept statepp—and the key becomes

\(genN,p,q,v,sorted\(A\),schema\_fp\),v=r\[ℓ:\]\(the post\-accept suffix bytes\),\\big\(\\text\{genN\},\\;p,\\;q,\\;v,\\;\\mathrm\{sorted\}\(A\),\\;\\mathrm\{schema\\\_fp\}\\big\),\\qquad v=r\[\\ell\{:\}\]\\ \\text\{\(the post\-accept suffix bytes\)\},sound only under the*lexicon\-visibility guard*\(live​\[q\]∪accepts​\[p\]\)∩LEX=∅\(\\mathrm\{live\}\[q\]\\cup\\mathrm\{accepts\}\[p\]\)\\cap\\mathrm\{LEX\}=\\emptyset: every terminal whose lexicon predicates the walk could consult on remainder\-derived bytes lies in that set, so under the guard those checks are lexicon\-inert and the walk’s future is a function of\(p,q,v,A\)\(p,q,v,A\)and the lexicons alone—remainders the walk provably cannot distinguish share one entry\. The suffixvvis load\-bearing \(e\.g\.b"1e"andb"1E"share\(q,ℓ,p\)\(q,\\ell,p\)but requeue different bytes on emission\)\. Guard failure falls back to the raw key\.

## 5Guarantees

Each guarantee is stated with its exact preconditions; each clause is paired with the test or benchmark that verifies it \(§[8](https://arxiv.org/html/2607.11951#S8)\)\.LLis the role/schema\-projected language of §[2](https://arxiv.org/html/2607.11951#S2)\.

###### Proposition 7\(Soundness\)\.

Every emitted token keeps the detokenized output inPrefix​\(L\)\\mathrm\{Prefix\}\(L\)\.*Preconditions:*exact masks \(no lookahead approximation\); hard−∞\-\\inftymasking \(soft down\-weighting leaves nonzero mass on illegal tokens and voids the guarantee\); the identifier composition rule \(Proposition[6](https://arxiv.org/html/2607.11951#Thmproposition6)\)\.

###### Proposition 8\(Completeness and dead\-end freedom\)\.

No token is blocked whose byte string extends the current viable prefix toward a member ofLL; consequently every viable prefix has at least one legal token and generation cannot wedge\.*Preconditions:*\(a\) byte\-complete vocabulary \(all byte values reachable viabytes\\mathrm\{bytes\}; verified per tokenizer adapter—degradation is an explicit warning that voids completeness, never soundness\); \(b\) reduced projected grammar; \(c\) exact trie walk with alias expansion \(masks over ids, not spellings\); \(d\) validated lexiconsWc⊆RcW\_\{c\}\\subseteq R\_\{c\}\.

Precondition \(d\) earned its “validated, not assumed” status empirically: the first real\-world schema violation \(a Spider database column namedOfficial\_ratings\_\(millions\), whose parentheses lie outside the column\-name regex\) produced an empty mask at a viable state within 100 generations—every prefix of the word passes the lexicon\-prefix check, yet no token can ever complete the lexeme\. The precondition is now checked at guide build\.

###### Proposition 9\(Termination\)\.

In mode 1 \(the GRID\-owned decode loop\): every non\-error stop satisfiesoutput∈L\\mathrm\{output\}\\in L\.*Preconditions:*EOS\-iff\-ACCEPT gating \(§[3](https://arxiv.org/html/2607.11951#S3)\); a*token\-denominated*reserve—per\-configuration minimal\-completion costs counted in vocabulary tokens \(a terminal\-denominated reserve under\-reserves: one identifier terminal can span many tokens\), summed incrementally on the stack—with the triggerbudget≤\|completion\|\+safety\\mathrm\{budget\}\\leq\|\\mathrm\{completion\}\|\+\\mathrm\{safety\}answeringWrite​\(shortest legal completion\+EOS\)\\mathrm\{Write\}\(\\text\{shortest legal completion\}\+\\mathrm\{EOS\}\), never a bare EOS away from ACCEPT; and a finite length budget\. In mode 2 \(processor\-only serving, where a logits processor cannot append tokens\), the guarantee*weakens*to EOS\-only\-at\-ACCEPT: reserve completion is unavailable, truncation at budget exhaustion is possible, and the downgrade is recorded in the audit seal\.

###### Proposition 10\(Complexity: requirement R\)\.

Guard\-rail cost is amortizedO​\(1\)O\(1\)per token andO​\(n\)O\(n\)total; the per\-step worst case is bounded by*nesting depth*\(one terminal can trigger a reduce cascade proportional to stack depth; SQL’s prefix operators are inherently right\-recursive, so cascades cannot be linted away\), never by the output positionnn\. Per\-stream space isO​\(depth\)O\(\\mathrm\{depth\}\)beyond the shared artifacts\.*Preconditions:*nothing in the hot loop may read state proportional tonn—the processor keys per\-row states incrementally \(a splitmix64 chain, not prefix hashing\), the audit configuration hash is a rollingO​\(1\)O\(1\)\-per\-push mix carried in stack nodes, and mask cost is a function of the configuration\.

###### Proposition 11\(The RBAC boundary\)\.

Grammar masking enforces verb\-level and table\-level policy\. Per\-table*column*restrictions are not enforceable by any left\-to\-right CFG mask: in SQL the SELECT list precedes FROM, so the alias→\\totable binding needed to judge a column is unknown at column\-mask time, and alias binding is context\-sensitive\. Column\-level policy is a post\-parse semantic check on the completed statement \(one AST walk\) or a view/rewrite layer in the database\.

Proposition[11](https://arxiv.org/html/2607.11951#Thmproposition11)is not an apology but a load\-bearing design input: it defines the residue that theSemanticCheckernames precisely, which in turn is what makes checker\-guided repair work at scale \(§[8\.4](https://arxiv.org/html/2607.11951#S8.SS4)\)\.

## 6System

### 6\.1Architecture

Figure[1](https://arxiv.org/html/2607.11951#S6.F1)shows the three time scales\. Everything expensive is offline and content\-addressed; everything per\-request is a registry lookup with single\-flight construction; the per\-token hot path touches only configuration\-sized state\.

OFFLINE / PER DEPLOYMENTPolicyBundle\(RBAC store\)RoleProjection \(L2\)subset→\\toreduceDialectGrammar \(L1\)SchemaSnapshotSchemaLexicon \(L3\)identifier triescompose→\\toreduce→\\toLALR\(1\) compileCompiledGrammar\(fingerprinted\)TokenizerAdaptertoken\_bytesTokenTrie\(per tokenizer fp\)ReserveTable\(grammar fp, tokenizer fp\)PER REQUESTGrammarRegistry lookup\(single\-flight on miss, E17\)GridGuide\(compiled, trie,cache, audit\)GridLogitsProcessor /vLLM structured\-output backendPER TOKEN \(hot path\)parser stackσ\\sigmaallowed terminalsAAMaskProducerMaskCache T1/T2hit∣\\midmiss: trie walk\+ write\-backCD residue check\(live stack, uncached\)masked\_fill\_\(−∞\-\\infty\)→\\tosampleradvance: lexer scan→\\toshift/reduceAuditLog\.append\(config hash, entry id,token, blocked count\)Figure 1:GRID architecture at its three time scales \(mirrors the normative design document\)\. Offline artifacts are immutable and fingerprinted; per\-request construction is single\-flight; the per\-token loop reads only configuration\-sized state\.#### The per\-token hot path

\(normative order; every step audited\):

1. 1\.A←A\\leftarrowallowed terminals by reduce\-chain simulation on the virtual stack \(memoized per node\)\.
2. 2\.eos​\_​ok←\\mathrm\{eos\\\_ok\}\\leftarrowmid\-lexeme\-aware ACCEPT\-reachability \(§[3](https://arxiv.org/html/2607.11951#S3)\)\.
3. 3\.Reserve trigger \(session budget, not grammar state\): ifbudget≤\|completion\|\+safety\\mathrm\{budget\}\\leq\|\\mathrm\{completion\}\|\+\\mathrm\{safety\}, returnWrite​\(shortest completion\+EOS\)\\mathrm\{Write\}\(\\text\{shortest completion\}\+\\mathrm\{EOS\}\)\.
4. 4\.Key←\\leftarrowDefinition[5](https://arxiv.org/html/2607.11951#Thmdefinition5)/ the genN normal form; T1 then T2 lookup; miss⇒\\Rightarrowtrie walk \(CI mask\+\+CD residue\), publish idempotently\.
5. 5\.Mask←\\leftarrowCI∪\\cupCD\-pass \(live\-stack class verdicts\)∪\\cup\{EOS​iff eos\_ok\}\\\{\\mathrm\{EOS\}\\ \\text\{iff eos\\\_ok\}\\\}; empty mask raises—a bug by Proposition[8](https://arxiv.org/html/2607.11951#Thmproposition8), asserted throughout the test suite\.
6. 6\.Singleton masks extend to a maximal forced span \(jump\-forwardWrite, bounded chain length\); otherwise return the*full*exact mask, applied as a hard in\-place fill\.
7. 7\.On the sampled token: bytes→\\tolexer advance \(maximal munch, candidate sets, parser\-viable pick\)→\\toshift/reduce on the persistent stack→\\toappend the audit record\.

Two implementations of this semantics coexist: a∼\\sim140\-line pure\-Python*executable specification*\(brute\-force trial\-parse over the vocabulary\) and the fast path, bound bit\-identically by differential and parity tests\. This discipline caught—before any debugging session—alias ids silently dropped from masks, lexicon\-blind reserve completions, and a real Rust/Python divergence in a CD group key\.

### 6\.2The kernel line: v4→\\tov5→\\tov5\.1→\\tov6→\\tov7

Four hot symbols \(trie walk, CD verdicts, LALR advance, bitmask fill\) are bound to Rust kernels; the Python spec path remains and a flag forces it\. The performance history is a lesson in*where*the cost actually was:

- •v4— a persistent, structurally interned stack arena with cross\-token memos and a one\-call assembled hit pass: warm\-hit p5012\.9→3\.512\.9\\to 3\.5µs \(dev host\)\. The interning insight: once a hot path is in Rust, the next win is usually*not calling it*—parser configurations recur massively across positions\. v4 also releases the GIL on the cold walk; measured main\-thread liveness during a cold replay rose from9%9\\%\(walk holding the GIL: “overlap” was a lie\) to88%88\\%\.
- •v5— scheduler\-sidefill\_bits: the whole per\-request bitmask row \(pre\-packed CI bit words\+\+live CD bits\+\+EOS\) written into vLLM’s buffer in one FFI call\. Motivated by the first real batched run: batch\-1 overhead\+1\.26%\+1\.26\\%but batch\-8\+3984%\+3984\\%and batch\-32\+5151%\+5151\\%—three stacked serving\-only defects \(a fill path that skipped the warm kernel; a prefetcher that scheduled*every*successor onto one worker; per\-request copies re\-registering every entry\)\. Fixes in dependency order took the batch\-32 step from 708 ms to 16 ms\.
- •v5\.1— verdict\-equivalence CD grouping \(Remark in §[4\.2](https://arxiv.org/html/2607.11951#S4.SS2)\): cold CD\-heavy mask builds124→13\.3124\\to 13\.3ms \(9\.3×9\.3\\times\); warm fill p9038→3\.838\\to 3\.8µs\. Both prior theories of this cost \(“151k\-vocab walks are superlinear,” “the warm gap is Python dispatch”\) failed under component\-level measurement; the real causes were CD keys embedding raw bytes and re\-packing∼\\sim47k CD ids per fill\.
- •v6— the whole per\-request serving step in\-kernel \(session\_accept/session\_fill, one FFI call each\): warm serving step7\.39→1\.337\.39\\to 1\.33µs/request \(accept6\.16→0\.566\.16\\to 0\.56, fill1\.22→0\.771\.22\\to 0\.77; local M\-series measurement\), restricted to audit\-off serving paths; audit\-enabled and processor\-mode guides keep v5\. A 200\-seed lockstep fuzz of v6 against v5 showed zero divergence and the pre\-implementation review surfaced a real v5 bug \(post\-COMPLETE state resurrection under speculative decoding\), now pinned by the differential suite\.
- •v7— the entire cold mask*miss*moved into Rust \(RustWalker\.walk\_payload\+\+RustVerdicts\.register\_blob\): walk, group\-blob, CI pack, adaptive encode, BLAKE2bentry\_id, and registration in*one*GIL\-released call; Python receives a handle plus a thinMaskEntryV7shell\. The red\-team’s original premise—that the per\-cold\-entry Python cost wasmake\_entry/encode/hash—was wrong on inspection \(those are microseconds\); the real source of the measured 6\.8–8\.7 ms per boundary entry was theWalkResultglue buildingCDEntryreps plus∼\\sim30–60k gc\-tracked objects per miss, whose allocation triggered gen\-2 GC pauses*inside*the walk\. Keeping the miss in Rust removes both: the per\-boundary\-entry cost falls6\.86\.8–8\.7→0\.0038\.7\\to 0\.003ms\.entry\_idis byte\-identical \(so the audit trail replays unchanged\);GRID\_V7defaults on and=0is byte\-identical to v6\. The win is localized to the serving cold\-entry path—the warm hit path, the R\-microharness, and the engine\-comparison latencies are v7\-unchanged\.

### 6\.3The serving contract

Under vLLM, GRID implements the structured\-output backend contract \(scheduler\-side bitmask fill, rollback natural on persistent states\) and a logits\-processor mode\. The contract that keeps a batch healthy:

- •Overlap, cold\-only\.Mask computation runs on CPU overlapped with the GPU forward pass\. The prefetcher schedules a successor’s mask onto the worker pool*only when it is not already warm*: the warm steady state never touches the pool \(unconditionally scheduling every successor serialized the steady state behind one worker’s queue—one of the three batched\-run defects\)\.
- •Skip\-a\-round defer\.If a request’s mask is not ready at sampling time \(worst case: a cold identifier\-position walk\), that request is deferred from the current scheduling round and rejoins the next step; co\-batched requests are never stalled, and an approximate mask is never substituted—by design there is no over\-approximating deadline fallback, because one over\-admitted token exitsPrefix​\(L\)\\mathrm\{Prefix\}\(L\)and voids Proposition[7](https://arxiv.org/html/2607.11951#Thmproposition7)\. In vLLM this is realized as a scheduler mask\-readiness guard \(one small patch site; upstream PR drafted\)\.
- •Single\-flight everything\.One build per artifact fingerprint;NNconcurrent waiters share the result or the same exception; failures are negatively cached with a TTL\.
- •An honest negative result: warmup\-at\-admission fails on the GIL\.The tempting alternative to the defer—warm the fresh request’s masks while it sits in the WAITING queue—was implemented and measured harmful: the tier work is GIL\-bound, so admission warmup starved the live engine \(fresh\-request TTFT10×10\\timesworse*and*multi\-second batch stalls\)\. It defaults off\. The defer, plus genN key normalization and rayon\-parallel cold walks \(bit\-identical;2\.05×2\.05\\timesat 8 threads locally\), is the shipped cold\-schema stack\.

### 6\.4The audit chain

Every step appends a record\(step,config​\_​hash,mask​\_​entry​\_​id,token,blocked​\_​count,kind,prev​\_​hash\)\(\\mathrm\{step\},\\mathrm\{config\\\_hash\},\\mathrm\{mask\\\_entry\\\_id\},\\mathrm\{token\},\\mathrm\{blocked\\\_count\},\\mathrm\{kind\},\\mathrm\{prev\\\_hash\}\)—including each interior token of a forced span and the EOS tail record—chained by BLAKE2b from a genesis constant and sealed with the stop reason, artifact fingerprints, and mode flags \(e\.g\. processor\-only downgrades\)\. The configuration hash is rolling andO​\(1\)O\(1\)per push,

H​\(node\)=low64​BLAKE2b​\-​128​\(H​\(parent\)​‖u32​\(state\)‖​u32​\(goto\)\),H​\(root\)=0,H\(\\mathrm\{node\}\)=\\mathrm\{low\}\_\{64\}\\,\\mathrm\{BLAKE2b\\text\{\-\}128\}\\big\(H\(\\mathrm\{parent\}\)\\,\\\|\\,\\mathrm\{u32\}\(\\mathrm\{state\}\)\\,\\\|\\,\\mathrm\{u32\}\(\\mathrm\{goto\}\)\\big\),\\qquad H\(\\mathrm\{root\}\)=0,since hashing the stack from scratch would be a hiddenΘ​\(depth\)\\Theta\(\\mathrm\{depth\}\)\-per\-token dependence\. Because mask entries are immutable and content\-addressed and the hash pins the parser trajectory, a log replays against archived artifacts to bit\-identical masks; §[8\.7](https://arxiv.org/html/2607.11951#S8.SS7)reports the full\-scale replay measurement\.

## 7Worked examples

### 7\.1Masking mid\-identifier under a schema lexicon

Take the CRUD\-subset grammar \(lowercase keywords;TABLE\_NAMEandCOLUMN\_NAMEshare the regex\[a\-z\_\]\[a\-z0\-9\_\]\*and are L3 categories\), the roleanalystwhose L2 projection keeps onlyselect\_stmtamong the query productions, and the schema lexicon

WTABLE=\{employees,employees\_public,orders\},W\_\{\\mathrm\{TABLE\}\}=\\\{\\texttt\{employees\},\\ \\texttt\{employees\\\_public\},\\ \\texttt\{orders\}\\\},with a tablesalariesexisting in the database but absent from the role’s lexicon\. The model has emitted

select \* from emplo

so the configurationκ\\kappahas: stackσ\\sigmawithselect,\*,fromshifted \(allowed next terminal setA=\{TABLE​\_​NAME\}A=\\\{\\mathrm\{TABLE\\\_NAME\}\\\}\), and remainderr=emplor=\\texttt\{emplo\}scanning inside an identifier lexeme with the L3 category context set\. BecauseAAcontains an identifier category, the cache key is the*ident*type and carries the schema fingerprint \(Proposition[6](https://arxiv.org/html/2607.11951#Thmproposition6)\); the walk intersects the token trie with the lexicon trie from the state reached byemplo\(Figure[2](https://arxiv.org/html/2607.11951#S7.F2)\)\. Representative verdicts:

- •tokenyees\(bytesyees\): completes exactlyemployees, a lexeme boundary withTABLE​\_​NAME∈A\\mathrm\{TABLE\\\_NAME\}\\in A⇒\\RightarrowCI, admitted\(and cached in the entry’s CI payload\)\.
- •tokeny: extends toemploy, a live lexicon prefix⇒\\RightarrowCI, admitted\(mid\-lexeme continuation\)\.
- •tokenyees where: crosses the boundary \(emitsTABLE\_NAME = employees, skips ignored whitespace, beginswhere\) and continues⇒\\RightarrowCD: its verdict depends on whetherwherecan shift*after*table\_ref, i\.e\. on the live stack—checked this step, never cached \(Proposition[4](https://arxiv.org/html/2607.11951#Thmproposition4)\)\. Here it passes\.
- •tokenyer:employeris not a prefix of any allowed word⇒\\Rightarrowblocked, monotonically with its whole trie subtree\.
- •At the earlier positionselect \* from\(empty remainder\): tokensalmatches the generic identifier regex but is a prefix only of the absentsalaries⇒\\Rightarrowblocked\. A generic\-IDENT cache entry would have admitted it and the parser would never have objected—the silent RBAC violation the identifier composition rule exists to prevent\.
- •At the statement head, tokens spellinginsert,update,deleteare blocked for this role because L2 removed those productions and reduction pruned their terminals: the verbs are not merely improbable, they are*outside the language*\. No prompt can path to them \(the model\-independent RBAC test probes every reachable identifier position with an exhaustive multi\-token speller; §[8\.6](https://arxiv.org/html/2607.11951#S8.SS6)\)\.
- •EOS isnotin the mask: simulating$endafter virtually finalizingemploasTABLE\_NAMEdoes not reach ACCEPT \(the grammar requires the closing;\), even thoughemplo’s finalization itself is legal\. After a later\.\.\. ;the reduce chain reaches ACCEPT and EOS enters the mask through the explicit gate only\.

employees\_publicordersscan state afteremployees: CI \(boundary,TN∈A\\mathrm\{TN\}\\in A\)yees where: CD \(crosses boundary, live\-stack verdict\)yer: blocked \(no allowed word; whole subtree pruned\)Figure 2:Example[7\.1](https://arxiv.org/html/2607.11951#S7.SS1): the L3 lexicon trie forWTABLEW\_\{\\mathrm\{TABLE\}\}during the walk at remainderemplo\. Double circles are allowed\-word accepts\. Candidate tokens are classified CI \(cacheable\), CD \(checked against the live stack, never cached\), or blocked \(whole trie subtrees pruned monotonically\)\.
### 7\.2A cold schema entering a hot batch

Thirty\-two requests are decoding at steady state \(warm caches, kernel fills of a few microseconds\) when a request arrives for a schema the deployment has never seen\. The fresh request pays, in order: a single\-flight grammar\+lexicon specialization \(27\.3 ms cold, measured; every concurrent duplicate waits on the same build\), then—at its first identifier\-heavy positions—cold trie walks that are milliseconds\-scale by nature \(vocabulary\-sized DFS\)\. The contract of §[6\.3](https://arxiv.org/html/2607.11951#S6.SS3)makes these costs*private to the fresh request*: the walk runs GIL\-released on the pool, overlapped with the forward pass; if it is still unfinished at sampling time, the scheduler’s mask\-readiness guard defers only that request for the round \(Figure[3](https://arxiv.org/html/2607.11951#S7.F3)\)\. Measured on the declared H100 SXM5 runner \(§[8\.5](https://arxiv.org/html/2607.11951#S8.SS5)\): at kernel v7 the serving record holds the 31 warm co\-tenants to a 15\.3 ms worst engine step while the fresh request’s∼\\sim0\.66 s cold window induces a transient\+33\.8%\+33\.8\\%co\-batched TPOT slowdown—no longer a GIL\-bound software cost \(the v7 fused cold\-miss path removed that\) but host CPU/memory\-bandwidth contention between the cold walk and the forward loop, which shrinks as walk threads grow\. The defer remains the load\-bearing protection: with it disabled the same leg reads\+373%\+373\\%and 65\.7 ms\. The fresh request itself sees TTFT0\.70\.7ms and then runs at1\.00×1\.00\\timeswarm speed: a never\-seen schema trades its own first\-token latency for exact masks throughout—no approximation is ever substituted\.

fresh window \(∼\\sim0\.66 s\)engine stepskkk\+1k\+1k\+2k\+2k\+3k\+3k\+4k\+4k\+5k\+531 warm requestswarm fills stay µs\-scale; contention bounded to the fresh window \(§[8\.5](https://arxiv.org/html/2607.11951#S8.SS5)\)fresh schema req\.single\-flight specialize \(27\.3 ms\)cold ident\-position walk \(on pool, GIL\-released\)mask not ready⇒\\Rightarrowdeferred this roundrejoins next round; then1\.00×1\.00\\timeswarm \(TTFT0\.70\.7ms\)Figure 3:Example[7\.2](https://arxiv.org/html/2607.11951#S7.SS2): the cold\-schema\-into\-hot\-batch timeline\. The fresh request’s compile and cold walks run off the critical path; the mask\-readiness guard defers only the fresh request from the rounds where its mask is late \(k\+1k\{\+\}1,k\+2k\{\+\}2\)\. Co\-batched requests never wait, and no approximate mask is ever substituted; the shaded band is the fresh window, the only span in which they see \(bounded\) contention\.

## 8Evaluation

All numbers below are from committed benchmark reports in the repository \(bench/RESULTS\*\.md\) or the measured\-results log; each table carries its host label verbatim\.*Declared runner*= a named cloud instance type and image recorded in the report \(Lambda 1×\\timesH100 PCIe or SXM5 80GB, or 1×\\timesA10 24GB; Ubuntu 24\.04; virtualized\);*local dev*= an unpinned Apple\-Silicon workstation\. Cross\-engine*ratios*proved host\-invariant; absolute constants carry the host label\.

### 8\.1Per\-token mask latency vs\. XGrammar, llguidance, Outlines

The engine\-comparison harness measures the wall time to produce the full next\-token mask at each replay step, for all engines on the same SQL\-subset grammar \(expressed in each engine’s native format\) and tokenizer, 11 replays\. Table[1](https://arxiv.org/html/2607.11951#S8.T1)reports both tokenizers on the declared H100 SXM5 runner at kernel v7 \(re\-recorded; within noise of v6, as expected—v7’s win is localized to the serving cold\-entry path, not this per\-token latency path\)\.

Table 1:Per\-token mask latency, SQL\-subset grammar, kernel v7\. Host: Lambda 1×\\timesH100 SXM5 80GB, Ubuntu 24\.04 \(declared runner\)\. Top:gpt2\(491 steps\); bottom: Qwen2\.5\-0\.5B\-Instruct tokenizer \(151k vocab; 509 steps\)\. “Rejected” counts language\-parity corners between grammar encodings \(maximal munch vs\. explicit whitespace\), not correctness bugs\.enginecompilep50p90p99slope \( µs/pos\)rej\.*gpt2*GRID \(Rust kernels: walk \+ CD \+ LALR\)378\.0 ms3\.6 µs80\.0 µs5,347\.4 µs−9\.292\-9\.2920XGrammar 0\.2\.3 \(EBNF\)94\.1 ms72\.2 µs7,503\.3 µs25,586\.7 µs−43\.759\-43\.7590llguidance 1\.7\.6 \(lark, driven directly\)285\.9 ms6\.6 µs223\.9 µs351\.7 µs−1\.176\-1\.1762Outlines 1\.3\.1 \(CFG backend = llguidance\)22,115\.1 ms73\.9 µs431\.5 µs582\.4 µs−2\.152\-2\.1522*Qwen2\.5\-0\.5B\-Instruct \(151k vocab\)*GRID1,297\.2 ms6\.7 µs109\.0 µs15,906\.2 µs−48\.903\-48\.9030XGrammar 0\.2\.3342\.7 ms588\.6 µs10,026\.9 µs31,774\.6 µs−63\.015\-63\.0150llguidance 1\.7\.6979\.5 ms14\.9 µs384\.4 µs1,200\.2 µs−1\.819\-1\.8191Outlines 1\.3\.113,796\.8 ms61\.7 µs459\.5 µs558\.7 µs−2\.215\-2\.2151Reading the table honestly: at kernel v7 GRID leads llguidance—the strongest prior engine in our measurements—at*both*p50 and p90 on both tokenizers \(3\.63\.6vs\.6\.66\.6µs p50 and8080vs\.224224µs p90 on gpt2;6\.76\.7vs\.14\.914\.9µs and109109vs\.384384µs on Qwen\), beats XGrammar at every reported percentile, and is the only engine with zero rejected replays\. Its cache split is p503\.53\.5µs hit /4\.84\.8ms miss at92%92\\%hit rate \(gpt2;6\.76\.7µs /13\.913\.9ms /92%92\\%on Qwen\), so the p99 remains cold\-miss trie walk on this recursive SQL grammar: llguidance’s Earley/derivative core keeps the flattest p99 \(352352µs vs\. GRID’s5\.35\.3ms on gpt2\), and we say so plainly\. Outlines≥\\geq1\.x has no CFG engine of its own:outlines\.types\.CFGroutes to a backend, default llguidance, so its row is the same matcher plus Outlines’ logits\-processor wrapper—identical rejects by construction\. The steep negative table slopes are an artifact of cold misses clustering early in replays; the warm\-replay check \(slope\+0\.002\+0\.002µs/pos on gpt2, first\-half p50 3 µs vs\. second\-half 4 µs;−0\.004\-0\.004µs/pos and 5 µs vs\. 5 µs on Qwen\) is the R\-relevant statistic\.

### 8\.2Requirement R: flat per\-token cost

#### The R microharness

\(declared H100 SXM5 runner, kernel v7;gpt2;n=16,000n=16\{,\}000tokens per stream, 20 seeded runs per nesting depth, warm\-pass OLS;ε=10−4\\varepsilon=10^\{\-4\}µs/pos\) isolates guard cost from the model \(Table[2](https://arxiv.org/html/2607.11951#S8.T2)\)\. Slope confidence intervals sit well over an order of magnitude underε\\varepsilonat every depth; hit p50 is4\.84\.8–6\.86\.8µs; the steady\-state hit rate is100%100\\%; cumulative\-cost fits are linear withR2≥0\.9998R^\{2\}\\geq 0\.9998\.

Table 2:R microharness: mask latency vs\. position, no model\. Host: Lambda 1×\\timesH100 SXM5 80GB, Ubuntu 24\.04 \(declared runner\), kernel v7;gpt2;n=16,000n\{=\}16\{,\}000/stream; 20 seeded runs per depth \(320,000 steps each\)\. GC is disabled during the warm timed pass\.
#### Head\-to\-head scaling vs\.guidance, three eras

\(local dev Mac, unpinned; slopes and shape are the claim, absolutes indicative\)\. The project’s founding claim—guard cost flat as generated context grows—was measured againstguidancein three vintages on the same growing WHERE\-chain statements,n∈\{512,…,16,384\}n\\in\\\{512,\\ldots,16\{,\}384\\\}\. Atn=16,384n=16\{,\}384: GRID runs at3\.23\.2µs/step with slope−3\.3×10−5\-3\.3\\times 10^\{\-5\}µs/pos \(kernels active\); guidance 0\.3\.1 \(today’s llguidance core\) is also flat but at a∼\\sim30×\\timeshigher constant \(97\.797\.7µs\); guidance 0\.1\.5 \(November 2023, Python Earley\) holds a flat*median*\(∼\\sim114 µs\) while its worst\-case single step grows67\.5→106\.267\.5\\to 106\.2ms across one generation’s quarters \(gen\-2 GC scanning the growing Earley chart, verified viagc\.callbacks\); and guidance 0\.0\.64 \(July 2023, the release the v0\.0\.5 design was conceived against\)breaks requirement R outright: measured overhead\-vs\-position slopes\+1,105\+1\{,\}105to\+1,189\+1\{,\}189µs/pos \(mechanism confirmed in its code: full\-string regex rebuilds per candidate per token, whole\-prompt re\-encoding per operation\), i\.e\. quadratic total cost—it spent 898 s reaching position 873 and could not completen=2,048n=2\{,\}048; the linear fit extrapolates \(labeled as such, not measured\) to≈\\approx19\.5 s/token at position 16,384\. Total constraint cost over one 16k replay: GRID0\.05 svs\. 1\.88 s \(0\.3\.1\) vs\. 2\.52 s \(0\.1\.5\) vs\.≈\\approx44 h \(0\.0\.64, extrapolated\)\.

### 8\.3MaskBench \(JSON Schema\)

GRID claims extensibility to any LALR\(1\)\-parsable language; MaskBench \(guidance\-ai/jsonschemabench\[[7](https://arxiv.org/html/2607.11951#bib.bib7)\]\) is the cheapest public test of where that is true\. GRID enters via a JSON\-Schema→\\togrammar compiler and a protocol\-exact runner \(TTFM/TBM semantics verbatim; llama\-3\.1 tokenizer; 315\-schema stratified sample; host: local dev, unpinned\)\. Table[3](https://arxiv.org/html/2607.11951#S8.T3)shows the three\-way comparison\.

Table 3:MaskBench, 315\-schema stratified sample, llama\-3\.1 tokenizer, local dev host \(unpinned\)\. TBM = time between masks; TTFM = time to first mask \(compile\)\. Compile errors are*declared*non\-support; validation errors \(valid instance rejected\) and invalidation errors \(invalid accepted\) are silent correctness gaps\.GRID’s p25–p75 \(14/28/34 µs\) is the kernel hit path, with kernels active on100%100\\%of compiled schemas, and GRID is the only engine with*zero*validation errors—every valid instance of every schema it compiled was accepted; its 68 invalidation errors are all traceable to deliberately ignored value constraints \(the XGrammar\-default convention, itemized in the report\)\. Its honesty boundary is llguidance\-style: 79/315 schemas are declared compile errors \(allOf, patternProperties, if/then/else, …, including 5 genuine LALR conflicts\)\. The TBM p90 traces a clean kernel lineage across the identical 315\-schema sample: v3\-era27\.827\.8ms→\\tov5\.1 verdict\-equivalence grouping208208µs→\\tov7 fused walk→\\toblob→\\toregister7575µs\. This is the kernel\-v7 re\-record: the correctness columns are byte\-identical to the earlier records, while the last step—v5\.1 to v7—cut TBM p90 a further∼\\sim2\.8×2\.8\\times\(208→75208\\to 75µs\) and the TBM average from683683to562562µs by moving the per\-cold\-entry Python materialization/glue \(and its gen\-2 GC pauses\) into Rust; the llguidance and XGrammar latency arms moved under10%10\\%between records, a host\-noise control placing the delta on GRID’s side\. Two structural facts explain the remaining tails: the TBM p95\+\+tail is the cold trie walk, which MaskBench’s one\-shot\-per\-schema protocol never lets the write\-back cache amortize \(the serving benchmark is where that design choice pays\), and TTFM is a pure\-Python table build \(19×19\\timesllguidance’s at p50, but 26–43×\\timesahead of XGrammar’s p75\+\+compile blowups\)\.

### 8\.4Spider: execution accuracy and checker\-guided repair

Executability is measured where it matters: the full 1,034\-question Spider dev set\[[8](https://arxiv.org/html/2607.11951#bib.bib8)\], greedy decoding, grammar with100%100\\%dev\-gold coverage plus per\-database L3 lexicons—every constrained output parses with schema\-valid identifiers by construction \(Table[4](https://arxiv.org/html/2607.11951#S8.T4)\)\.

Table 4:Spider dev execution accuracy\. 7B rows: Qwen2\.5\-7B\-Instruct, full 1,034 questions \(grid/unconstrained on the declared H100 PCIe runner; the repair pair reproducedgridexactly on the declared A10 runner\)\. 0\.5B rows: Qwen2\.5\-0\.5B\-Instruct, 100 questions, local dev host\. EX = result\-set match on the Spider databases\.modelarmexecutesEXEX deltatruncatedtok/query0\.5B \(n=100n\{=\}100\)GRID \(repair inert at this scale\)57\.0%29\.0%\+13\.0\+13\.04\.0%410\.5Bunconstrained31\.0%16\.0%—9\.0%617B \(n=1034n\{=\}1034\)GRID \(with repair\)94\.5%55\.2%\+2\.3\\mathbf\{\+2\.3\}0\.5%407BGRID \(repair off, ablation\)91\.3%53\.7%\+0\.8\+0\.80\.9%357Bunconstrained91\.0%52\.9%—0\.2%33The scale finding, measured at both ends: the mask alone is worth\+13\+13EX points at 0\.5B—it erases the syntax\-error class a weak model commits constantly \(\+26\+26points of syntactic validity\)—but only∼\\sim\+1\+1at 7B, because a capable model rarely errs syntactically\. The repair half closes the loop at scale: GRID’s residual 7B failures are alias↔\\leftrightarrowcolumn binding—exactly the class Proposition[11](https://arxiv.org/html/2607.11951#Thmproposition11)proves out of mask scope, and exactly what the alias\-awareSemanticCheckernames precisely\. One constrained retry with the violations quoted back converts a third of that floor \(91\.3→94\.5%91\.3\\to 94\.5\\%executes;21%21\\%of kept retries newly correct\) at\+5\+5tokens/query \(\+14%\+14\\%\) on the∼\\sim7% of queries that engage\. The*capability symmetry*is measured in both directions, not asserted: at 0\.5B the same feedback is worthless \(an interim run of 55 questions: repair metrics identical to plain GRID—the model repairs its binding mistakes into different\-but\-equally\-wrong queries\), while at 7B the mask matters less but the feedback converts—constraint quality determines feedback quality, because the checker can only name violations precisely when the mask has already guaranteed everything else\. Ablations on the same harness \(EX\-invariant by construction\): disabling the write\-back cache costs32%32\\%of generation throughput \(2\.5→1\.72\.5\\to 1\.7tok/s,n=20n\{=\}20\); audit\-off and jump\-forward\-off move throughput within noise\.

### 8\.5Batched serving under vLLM

The end\-to\-end serving benchmark runs vLLM 0\.24 \(V1 engine\) with Qwen2\.5\-7B on the declared H100 SXM5 runner: heterogeneous grammars \(4 distinct\) across batches 1/8/32, unconstrained control arm, warm\-through protocol, kernel v7 \(Table[5](https://arxiv.org/html/2607.11951#S8.T5)\)\.

Table 5:Serving record, kernel v7\. Host: Lambda 1×\\timesH100 SXM5 80GB, Ubuntu 24\.04 \(declared runner\), vLLM 0\.24, Qwen2\.5\-7B, heterogeneous grammars\. The cold\-miss stress arm injects a fresh never\-warmed schema into a warm batch\-32; its metric is per\-request TPOT over the 31 warm co\-batched requests, computed with artifact\-robust estimators \(median\-over\-legs degradation; min\-over\-legs max step\) for the reason given in §[8\.5](https://arxiv.org/html/2607.11951#S8.SS5)\.Warm serving overhead is low at every batch size—\+1\.51%\+1\.51\\%time\-per\-output\-token at batch 32—warm and cold TTFT are1\.511\.51and27\.327\.3ms, and both single\-flight behaviors hold\. In the cold\-miss stress arm the warm co\-tenants’ worst engine step is 15\.3 ms \(thread\-invariant at 15–18 ms across walk threads0/2/80/2/8\)\. The one residual cost is a transient co\-batched TPOT slowdown of\+33\.8%\+33\.8\\%, confined to the fresh schema’s cold window; we characterize it below\.

What v7 changed\. On the v6 stack the cold window cost more—a\+114\.7%\+114\.7\\%co\-batched slowdown and a 36\.0 ms worst step—and both were attributed to GIL\-bound mask\-entry materialization in the fresh request’s cold window\. That attribution was half right\. Moving the entire cold miss into Rust \(§[6\.2](https://arxiv.org/html/2607.11951#S6.SS2): fused walk→\\toblob→\\toregister, one GIL\-released call\) collapsed the per\-boundary\-entry cost6\.86\.8–8\.7→0\.0038\.7\\to 0\.003ms and, with it, the worst engine step on real hardware \(36\.0→15\.336\.0\\to 15\.3ms\)\. The residual glue theory \(“make\_entry/encode/hash is the cost”\) was disproved by the fix: the real culprit was theWalkResultglue allocating∼\\sim30–60k gc\-tracked objects per miss, whose gen\-2 pauses landed*inside*the walk—which is exactly why keeping the walk in Rust removed them\.

The estimators\. The cold\-window metrics are computed with artifact\-robust estimators \(median\-over\-legs degradation; min\-over\-legs max step, with the raw per\-leg maxima always printed\) because vLLM 0\.24’s multiprocess engine exhibits a once\-per\-leg 0\.7–2 s frozen engine step that we exonerated five ways before believing it: it fires in all\-warm baselines with zero GRID work in flight, is invariant to the defer, warmup, walk\-thread, and JIT\-warming levers and to both child\- and driver\-side GC control, and vanishes entirely with the engine in\-process—an engine\-topology artifact, filed upstream as vllm\-project/vllm issue \#48229 \(the repository’s LESSONS\.md §6\.8–6\.9 holds the exoneration record\)\. The raw per\-leg step maxima\[15,15,16,16,16\]\[15,15,16,16,16\]ms show the v7 max step is now clean and tight, with no exogenous 1–2 s outliers polluting the min\-over\-legs estimator\.

The cold\-window slowdown, characterized\. At v6 the co\-batched degradation was called a Python/GIL/software cost with a kernel fix pending\. That fix has shipped, and the degradation did not go to zero—because it was never primarily a software cost\. It is genuine host CPU/memory\-bandwidth contention between the cold walk and the engine forward loop during the fresh schema’s∼\\sim0\.66 s specialization window\. The diagnostic evidence is direct: the slowdown*decreases*as walk threads increase, because more threads shrink the window in which the contention occurs—a software\-serialization cost would not behave this way\. Walk/pool thread niceness mitigates the residual\. Full closure is therefore a compute\-isolation trade\-off \(throttle the walk and lengthen the fresh request’s TTFT, or accept the number\), noted as future work rather than a defect to fix\. Throughout, the fresh request itself pays only its own cost: TTFT0\.70\.7ms, and1\.00×1\.00\\timeswarm effective TPOT once specialized—there is zero steady\-state co\-tenant interference\. As a pre\-v7 observation \(superseded by this record, retained only for lineage\): an artifact\-free JIT\-warmed lockstep leg on the v6 stack read−1\.75%\-1\.75\\%co\-batched slowdown and a 23\.9 ms max step; the same leg with the defer disabled read\+373%\+373\\%and 65\.7 ms, the attribution that makes the defer the load\-bearing protection\. Finally, the tempting admission\-time warmup alternative was measured harmful on the GIL and ships disabled \(§[6\.3](https://arxiv.org/html/2607.11951#S6.SS3)\); negative results are recorded next to the positive ones\.

### 8\.6Policy enforcement and end\-to\-end correctness at scale

The guarantees of §[5](https://arxiv.org/html/2607.11951#S5)are checked directly, each against the test that exercises the corresponding property\.

#### Soundness, completeness, termination end\-to\-end\.

Two arms exercise the whole decode loop\. The walk arm generates 10,000/10,000 outputs that parse, with 0 dead ends and 0 budget overruns \(local dev\)\. The model arm, driving Qwen2\.5\-0\.5B on the declared H100 runner, generates 1,000/1,000 parseable and audit\-verified outputs, again with 0 dead ends, and 706 reserve\-completed stops \(the termination machinery of Proposition[9](https://arxiv.org/html/2607.11951#Thmproposition9)firing as designed\)\.

#### Policy/RBAC enforcement\.

A model\-free exhaustive speller probes every reachable identifier position: across 58 role×\\timesposition×\\timestarget probes it records0 bypasses, with 9/9 positive controls reachable so the test is non\-vacuous\. A 12\-prompt injection suite \(the adversarial\-prompt arm\) emits 0 forbidden lexemes on the declared H100 runner, and column\-violation fixtures are 100% flagged by the post\-parse checker \(the residue Proposition[11](https://arxiv.org/html/2607.11951#Thmproposition11)places out of mask scope\)\.

#### Differential correctness, cache soundness, and kernel parity\.

The fast path is checked bit\-exact against the trial\-parse oracle over quota\-counted corpora including multi\-terminal tokens, across a four\-tokenizer matrix; the viable\-prefix oracle is checked by corpus, mutation, and mid\-lexeme EOS differentials against lark\. Cache\-key soundness \(OBL\-KEY1\) is verified by cache\-on≡\\equivcache\-off runs including cross\-role hits, namespace rollover, and racing publishes\. Grammar\-pipeline reducedness and deterministic fingerprints have property tests\. All of these run in CI\.

### 8\.7Audit replay and tamper detection

Over 1,000 generations spanning 29,242 audited steps and one cache\-namespace rollover, every log replays bit\-identically \(1,000/1,000\) against its archived artifacts, and tamper detection catches every injected mutation \(1,000/1,000\), on local dev\.

### 8\.8Cross\-engine comparison, summarized

Taken together with §[8\.1](https://arxiv.org/html/2607.11951#S8.SS1): on per\-token mask latency GRID leads llguidance and XGrammar at p50 on both tokenizers \(Table[1](https://arxiv.org/html/2607.11951#S8.T1)\), by more than2×2\\timesover XGrammar; llguidance retains the flattest p99\. The SynCode and GBNF arms were dropped by decision \(2026\-07\-10\) as the engine comparison had already settled on this front\.

## 9Limitations and honest boundaries

- •Distribution faithfulness\.Masking changes the sampling distribution \(Remark[2](https://arxiv.org/html/2607.11951#Thmremark2)\); GRID measures the downstream effect \(EX deltas\) rather than claiming neutrality\. GAD/ASAp\-style faithful sampling and CRANE\-style two\-phase decoding are compatible, deferred arms\.
- •Column\-level RBAC is post\-parse by proof\(Proposition[11](https://arxiv.org/html/2607.11951#Thmproposition11)\)\. The mask guarantee is verb\- and table\-level; the checker covers the residue and feeds repair\.
- •LALR\(1\) languages only \(v1\)\.MaskBench draws the boundary concretely: 79/315 schemas are declared compile errors, 5 of them genuine LALR conflicts\. An Earley fallback is a recorded option, unexercised because no target dialect construct has forced it\.
- •Cold\-walk tails\.The cold trie walk over a 100k\+ vocabulary is milliseconds by nature; the write\-back cache amortizes it across requests \(86–98% hit rates in replay\- and serving\-shaped workloads\) and the serving contract keeps it off co\-tenants’ critical path, but one\-shot workloads see it \(MaskBench p95\+\+\)\. Walk\-level pruning is the named next kernel target\.
- •The cold\-window serving contention\.A fresh, never\-before\-seen schema induces a transient co\-batched slowdown \(∼\\sim34% during its∼\\sim0\.66 s first\-request specialization window\)\. The kernel\-v7 fused cold\-miss path removed the GIL\-bound entry\-materialization cost that dominated at v6, so the residual is genuine host CPU/memory\-bandwidth contention between the cold walk and the engine forward loop; it shrinks as walk parallelism rises and is mitigated by scheduling niceness\. The fresh request itself runs at warm speed and steady\-state co\-tenant requests are unaffected\. Fully eliminating it is a compute\-isolation trade\-off, noted as future work \(§[8\.5](https://arxiv.org/html/2607.11951#S8.SS5)\)\.
- •One characterized exogenous artifact\.The serving record’s per\-step tail on vLLM 0\.24’s multiprocess topology contains a once\-per\-leg frozen step that is provably not GRID’s \(five\-way exoneration, §[8\.5](https://arxiv.org/html/2607.11951#S8.SS5)\); the serving metrics use artifact\-robust estimators and the issue is filed upstream \(vllm\-project/vllm \#48229\) rather than papered over\.
- •Termination is mode\-dependent\.The full termination guarantee \(reserve\-completed stops\) holds in the GRID\-owned loop; processor\-only serving weakens to EOS\-only\-at\-ACCEPT with truncation recorded \(Proposition[9](https://arxiv.org/html/2607.11951#Thmproposition9)\)\.
- •Host honesty\.Headline performance numbers run on declared cloud runners; local\-dev numbers are labeled and used for shape, not records\.

## 10Related work

Outlines\[[1](https://arxiv.org/html/2607.11951#bib.bib1)\]reformulated guided generation as FSM state transitions with a vocabulary index, extending to CFGs via lexer\-aware scanning over parser states—the paper whose problem statement and formal register this work parallels, and an explicit inspiration for GRID’s design\. GRID differs in what it keys and what it promises: masks keyed on live LALR configurations with a write\-back cross\-request cache rather than a per\-automaton precomputed index; policy \(roles, schemas\) compiled into the language; guarantees stated with preconditions and empirically verified; an audit trail\. Notably, current Outlines releases delegate CFG constraining to llguidance\[[9](https://arxiv.org/html/2607.11951#bib.bib9)\], so the engine\-level comparison collapses into the llguidance one \(§[8\.1](https://arxiv.org/html/2607.11951#S8.SS1)\)\.guidance/llguidance\[[10](https://arxiv.org/html/2607.11951#bib.bib10),[9](https://arxiv.org/html/2607.11951#bib.bib9)\]pair an Earley/derivative core with a token trie; llguidance keeps the flattest p99 tails and the fastest compiles in our measurements and is the bar GRID names—at kernel v7 GRID leads it at p50 and p90 on both tokenizers \(§[8\.1](https://arxiv.org/html/2607.11951#S8.SS1)\) while llguidance retains the p99 edge\. GRID’s answer is also architectural rather than raw\-constant: configuration\-keyed write\-back caching across grammar families, mask\-level RBAC/schema projection, requirement R as a committed contract, and the audit chain\.XGrammar\[[11](https://arxiv.org/html/2607.11951#bib.bib11)\]introduced the context\-independent/context\-dependent vocabulary split with compile\-time precomputation and scheduler overlap; GRID adopts the CI/CD idea but makes the split a*cache\-key soundness*requirement \(never cache CD\), computes on miss with write\-back \(rewarding the per\-role/per\-tenant family shape\), and adds the identifier composition rule that per\-schema policy needs\.SynCode\[[12](https://arxiv.org/html/2607.11951#bib.bib12)\]formalizes grammar masks over lexer\-state×\\timesremainder tables with soundness/completeness theorems; its shippeddd\-lookahead masks are sound but incomplete, which is incompatible with dead\-end freedom—GRID chooses exact byte\-level masks for exactly that reason\.PICARD\[[13](https://arxiv.org/html/2607.11951#bib.bib13)\]pioneered constrained SQL decoding by incremental parsing over beam candidates \(reject\-and\-filter rather than exact masks\)\.Grammar\-aligned decoding\[[4](https://arxiv.org/html/2607.11951#bib.bib4)\]andCRANE\[[6](https://arxiv.org/html/2607.11951#bib.bib6)\]address the distribution and reasoning costs of strict masking; both are complementary layers above an exact\-mask engine like GRID\. Automata\-theoretic treatments of the token–terminal misalignment\[[14](https://arxiv.org/html/2607.11951#bib.bib14)\]give the detokenization correctness framing our byte\-trie bridge instantiates\.JSONSchemaBench\[[7](https://arxiv.org/html/2607.11951#bib.bib7)\]supplies the cross\-engine schema corpus used in §[8\.3](https://arxiv.org/html/2607.11951#S8.SS3)\. Serving integration follows the vLLM structured\-output interface\[[15](https://arxiv.org/html/2607.11951#bib.bib15)\]\. Classical foundations: viable prefixes and LR parsing\[[2](https://arxiv.org/html/2607.11951#bib.bib2),[3](https://arxiv.org/html/2607.11951#bib.bib3)\]; linear Earley parsing on LR\-regular grammars\[[16](https://arxiv.org/html/2607.11951#bib.bib16)\]\(the recorded fallback engine\)\.

## 11Conclusion

GRID shows that the properties an enterprise actually needs from constrained decoding—policy compiled into the language, guarantees with preconditions, position\-flat guard cost, a replayable audit trail, and batch\-safe serving with honest cold\-start behavior—all follow from one commitment: key every mask, cache entry, and audit record on the parser configuration, and prove \(then verify\) that the keys refine the equivalence the semantics requires\. The residue the mask provably cannot enforce is not hidden but named, checked post\-parse, and—at model scales that can use feedback—repaired\. The committed record spans engine microbenchmarks, a public schema corpus, full\-dataset execution accuracy, and an end\-to\-end serving benchmark, each number carried with its host label; the remaining open costs \(cold\-walk tails, the once\-per\-schema cold\-window serving contention, one upstream engine artifact\) are stated as precisely as the wins\.

## References

- \[1\]Brandon T\. Willard and Rémi Louf\.Efficient guided generation for large language models\.arXiv preprint arXiv:2307\.09702, 2023\.
- \[2\]Donald E\. Knuth\.On the translation of languages from left to right\.Information and Control, 8\(6\):607–639, 1965\.
- \[3\]Alfred V\. Aho and Stephen C\. Johnson\.LR parsing\.ACM Computing Surveys, 6\(2\):99–124, 1974\.
- \[4\]Kanghee Park, Jiayu Wang, Taylor Berg\-Kirkpatrick, Nadia Polikarpova, and Loris D’Antoni\.Grammar\-aligned decoding\.InAdvances in Neural Information Processing Systems \(NeurIPS\), 2024\.arXiv:2405\.21047\.
- \[5\]Zhi Rui Tam, Cheng\-Kuang Wu, Yi\-Lin Tsai, Chieh\-Yen Lin, Hung\-yi Lee, and Yun\-Nung Chen\.Let me speak freely? A study on the impact of format restrictions on performance of large language models\.arXiv preprint arXiv:2408\.02442, 2024\.
- \[6\]Debangshu Banerjee, Tarun Suresh, Shubham Ugare, Sasa Misailovic, and Gagandeep Singh\.CRANE: Reasoning with constrained LLM generation\.InProceedings of the 42nd International Conference on Machine Learning \(ICML\), PMLR 267, 2025\.arXiv:2502\.09061\.
- \[7\]Saibo Geng, Hudson Cooper, Michał Moskal, Samuel Jenkins, Julian Berman, Nathan Ranchin, Robert West, Eric Horvitz, and Harsha Nori\.Generating structured outputs from language models: Benchmark and studies\.arXiv preprint arXiv:2501\.10868, 2025\.
- \[8\]Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev\.Spider: A large\-scale human\-labeled dataset for complex and cross\-domain semantic parsing and text\-to\-SQL task\.InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing \(EMNLP\), 2018\.arXiv:1809\.08887\.
- \[9\]Guidance AI\.llguidance: Super\-fast structured outputs\.[https://github\.com/guidance\-ai/llguidance](https://github.com/guidance-ai/llguidance), 2024\.
- \[10\]Guidance AI\.guidance: A guidance language for controlling large language models\.[https://github\.com/guidance\-ai/guidance](https://github.com/guidance-ai/guidance), 2023\.
- \[11\]Yixin Dong, Charlie F\. Ruan, Yaxing Cai, Ruihang Lai, Ziyi Xu, Yilong Zhao, and Tianqi Chen\.XGrammar: Flexible and efficient structured generation engine for large language models\.arXiv preprint arXiv:2411\.15100, 2024\.
- \[12\]Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh\.SynCode: LLM generation with grammar augmentation\.Transactions on Machine Learning Research, 2024\.arXiv:2403\.01632\.
- \[13\]Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau\.PICARD: Parsing incrementally for constrained auto\-regressive decoding from language models\.InProceedings of the 2021 Conference on Empirical Methods in Natural Language Processing \(EMNLP\), 2021\.arXiv:2109\.05093\.
- \[14\]Terry Koo, Frederick Liu, and Luheng He\.Automata\-based constraints for language model decoding\.arXiv preprint arXiv:2407\.08103, 2024\.
- \[15\]Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E\. Gonzalez, Hao Zhang, and Ion Stoica\.Efficient memory management for large language model serving with PagedAttention\.InProceedings of the 29th ACM Symposium on Operating Systems Principles \(SOSP\), 2023\.arXiv:2309\.06180\.
- \[16\]Joop M\. I\. M\. Leo\.A general context\-free parsing algorithm running in linear time on every LR\(kk\) grammar without using lookahead\.Theoretical Computer Science, 82\(1\):165–176, 1991\.