Getting a large language model to write syntactically plausible SQL is a solved problem. Getting it to write SQL that is provably valid, respects per-role access control, costs a bounded amount per token regardless of output length, and leaves a tamper-evident audit trail is a substantially harder engineering and theoretical challenge. GRID (Grammar-Railed Decoding) addresses all of these requirements simultaneously, and the paper is worth reading carefully because it is unusually honest about what it can and cannot guarantee.
The enterprise SQL generation setting motivates six distinct requirements the authors enumerate precisely: joint validity and policy enforcement, provable guarantees with explicit preconditions, position-flat per-token cost, a replayable compliance audit trail, safe batch serving when new schemas arrive mid-batch, and a clearly named boundary for policy the mask provably cannot enforce. Most constrained decoding work addresses one or two of these. GRID attempts all six, which shapes every design decision.
Key Contributions
The central architectural idea is to key masks on parser configurations rather than on token sequences. A configuration is the pair of the lexer's current scan state and the LALR(1) parser stack. This is exactly the information that determines which token continuations keep the partial output within the viable-prefix set of the grammar. Keying on configurations rather than sequences means the cache is shared across requests that happen to reach the same parser state, which is the mechanism behind the cross-request hit rates of 86-98% reported in the benchmarks.
- Policy compiled into the language: Role-based access control is not a post-generation filter. Role projections subset the grammar's productions directly, and schema lexicons restrict identifier terminals. A role without DELETE permission cannot emit the token at all; it is unreachable by construction at mask time.
- Four stated guarantees: Soundness (no token emitted that exits the viable-prefix set), completeness (no token blocked that could still complete a valid sentence), termination (every stop is a complete parse), and position-flat cost. Each guarantee carries explicit preconditions and is paired with the test that verifies it. This is more careful than most systems, which treat these as emergent properties of a test suite.
- Byte-level trie bridge with CI/CD split: LLM tokens are bridged to grammar terminals via a byte-level trie walk. The context-independent/context-dependent split, borrowed conceptually from XGrammar, is made a cache-key soundness requirement: context-dependent tokens are never cached, which avoids the unsound cache-key problem that afflicted earlier sequence-keyed designs.
- Hash-chained audit trail: Every per-token permit/block decision is recorded in a hash-chained log that replays bit-identically, with 100% tamper detection verified across 1,000 generations spanning a cache-namespace rollover.
Methodology and Implementation
The system is implemented in Rust for the hot path, with integration into vLLM's structured-output interface. The three-tier architecture separates offline grammar compilation (per deployment), per-request registry lookup with single-flight construction on cache miss, and the per-token hot path that reads only configuration-sized state.
The LALR(1) parser serves double duty: it advances the configuration on each accepted token and acts as the viable-prefix oracle for mask computation. Cold schema specialization (a grammar never seen before) costs 27.3 ms and then decodes at warm speed. The warm serving step reaches 1.33 µs per request and 3.6-6.7 µs median per-token mask cost on an H100 SXM5, which the paper reports as faster than llguidance at p50 and p90 on both benchmarked tokenizers. llguidance retains the flattest p99 tails, a distinction the authors acknowledge rather than paper over.
The position-flatness of per-token cost is tested concretely at n=16,384 tokens with slope approximately zero across nesting depths. This matters because at least one 2023-era system shows per-token overhead growing by roughly 1.19 ms per position, which makes it unusable for long generations.
Results
The Spider benchmark results are the most practically meaningful numbers. At 0.5B parameters, constrained decoding adds 13 execution-accuracy points over unconstrained generation. At 7B, the mask alone contributes roughly 1 point, and adding one checker-guided repair pass over the column-level policy residue (the part the mask provably cannot enforce) lifts execution accuracy to 94.5%, a gain of 2.3 points over unconstrained. The repair loop is important: it handles exactly the cases GRID's own proof says the mask cannot reach.
The serving benchmark on a real H100 shows end-to-end overhead of +1.51% time-per-output-token at batch 32. The one honest blemish is a transient ~34% co-batched slowdown during the ~0.66 second specialization window for a fresh schema, traced to CPU and memory-bandwidth contention between the cold trie walk and the GPU forward loop. The paper attributes this correctly to a compute-isolation trade-off rather than a GRID design flaw, and notes it shrinks as walk parallelism increases.
Limitations and Broader Implications
The limitations section is unusually candid, which is itself worth noting. The mask cannot enforce column-level RBAC: Proposition 11 in the paper proves this is impossible for any left-to-right context-free mask, not just for GRID. The system handles it post-parse with a checker, which is the correct response. Distribution faithfulness is not claimed; masking changes the sampling distribution and the paper measures downstream effects rather than asserting neutrality.
The LALR(1) restriction excludes 79 of 315 schemas in the MaskBench corpus, with 5 genuine LALR conflicts. An Earley fallback is recorded as an option but not implemented because no target SQL dialect construct has forced it yet. Cold trie walks over 100k+ vocabularies remain milliseconds by nature; the write-back cache amortises this well in practice but one-shot workloads see the full cost.
Relative to the existing literature, GRID sits in a well-populated space. Outlines and llguidance are the direct performance comparators. XGrammar introduced the CI/CD split that GRID adopts and extends. SynCode provides soundness and completeness theorems for grammar masks but ships incomplete masks by design; GRID's choice of exact byte-level masks is a deliberate trade-off for dead-end freedom. PICARD's reject-and-filter approach over beam candidates is architecturally different and predates the exact-mask generation of systems. The audit trail and RBAC compilation appear to be genuinely novel contributions with no close prior work.
The paper's broader significance is in demonstrating that the full set of enterprise requirements, which practitioners often treat as incompatible with each other or with acceptable latency, can be addressed within a single coherent design. The commitment to stating guarantees as theorems with preconditions rather than as benchmark observations is a methodological standard the field should adopt more widely. Whether the LALR(1) restriction proves limiting as SQL dialects evolve, and whether the cold-window contention can be eliminated without sacrificing throughput, are the open questions most worth watching.
The full paper is available at arXiv:2607.11951.