💻 computer science

GRID: Grammar-Railed Decoding for Enterprise SQL Generation

The paper introduces GRID, a grammar-constrained decoding engine that leverages LALR(1) parser states and byte-level trie walks to generate syntactically valid, policy-compliant SQL with provable guarantees, near-constant decoding costs, and tamper-evident audit trails, significantly improving execution accuracy in enterprise settings.

Original authors: Mohsen Arjmandi

Published 2026-07-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohsen Arjmandi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a super-smart robot friend (a Large Language Model) who loves to write computer instructions called SQL. This robot is great at guessing the next word in a sentence, but it's also a bit of a chaotic dreamer. In a normal conversation, if the robot says something silly like "DELETE ALL THE TABLES" when it was only supposed to "SELECT," nobody gets hurt. But in a bank or a hospital, that mistake is a disaster.

Enter GRID (Grammar-Railed Decoding). Think of GRID not as a teacher who yells "No!" after the robot makes a mistake, but as a magic train track that the robot must ride on. The robot can still be creative, but it physically cannot steer the train off the rails. If the track doesn't exist, the robot can't even think about that word.

The Magic Train Track

Usually, when you ask a robot to write code, you let it guess the next word, and then you check if the whole sentence makes sense. If it doesn't, you delete it and try again. That's slow and risky.

GRID changes the game. Instead of checking the whole sentence at the end, it checks every single step before the robot is even allowed to pick a word. It does this by looking at a "map" of the grammar (the rules of the language) and the robot's current position on that map.

The Problem with Old Maps: Previous methods tried to memorize every possible sentence the robot could ever write. The paper explains that this is impossible. If you tried to list every valid sentence of even moderate length, the list would be bigger than the number of atoms in the entire universe.
The GRID Solution: Instead of memorizing sentences, GRID memorizes configurations. Imagine the robot is a hiker. Old methods tried to memorize every possible path the hiker could take. GRID just checks: "Is the hiker currently standing on a valid part of the trail?" If yes, the robot can keep walking. If no, the path is blocked. This keeps the system fast, even for very long sentences.

The "No-Go" Zones (Policy and Rules)

In a big company, different people have different rules. A junior employee might only be allowed to look at data (SELECT), while a manager can delete it.

GRID builds these rules directly into the train tracks.

Role-Based Tracks: If the robot is acting as a "Junior Employee," the tracks for "DELETE" or "UPDATE" simply do not exist. The robot can't even imagine them. It's not that the robot is being told "No, don't do that"; it's that the word "DELETE" is invisible to it in that mode.
Schema Tracks: The robot also knows exactly which tables and columns exist in the database. If a table doesn't exist, the track to it is gone. The robot can't accidentally type a fake table name.

The paper is very honest about what this magic track cannot do. It proves that the track cannot stop the robot from picking the wrong column for a specific row (like picking "salary" when it should pick "name") because that decision depends on context that only appears after the sentence is finished. For those tricky cases, GRID uses a "checker" that looks at the finished sentence and fixes it if needed.

Speed and Safety: The "Flat" Cost

One of the biggest worries with these safety checks is speed. Usually, the longer the sentence gets, the slower the safety check becomes. The paper calls this "Requirement R."

GRID promises something special: The cost of checking stays flat.

Whether the robot is writing the 5th word or the 16,000th word, the time it takes to check if the next word is allowed is roughly the same.
The authors measured this on powerful computers (H100 GPUs). They found that for every token (word part), the check takes between 3.6 and 6.7 microseconds (that's millionths of a second) when the system is warm and ready.
Even when the robot encounters a brand new database it has never seen before, the system handles it gracefully. The first few words might take a bit longer (about 27.3 milliseconds to set up), but once that's done, it runs at full speed. Crucially, this setup time doesn't slow down the other robots working at the same time.

The "Black Box" Receipt (Audit Trail)

In a bank, you need to know exactly what happened. If a robot made a decision, you need to be able to replay it later to prove it was safe.

GRID keeps a hash-chained audit trail. Imagine a digital receipt for every single word the robot is allowed to say. This receipt is chained together like a chain of paperclips. If anyone tries to change a single word in the past, the whole chain breaks, and you know immediately that the record has been tampered with. The paper shows that they can replay 1,000 generations of these decisions and get the exact same result every time, with 100% tamper detection.

How Well Does It Work?

The paper doesn't just claim it works; they tested it on real data (the Spider dataset, which has over 1,000 complex questions).

For smaller robots (0.5B parameters): Using GRID improved the number of correct answers by 13 percentage points. The main reason? The robot stopped making silly grammar mistakes.
For bigger, smarter robots (7B parameters): The grammar check alone helped a little (about +1 point), but when they added the "checker" to fix the tricky column mistakes, the success rate jumped to 94.5%.

The Honest Truth

The authors are very careful not to overpromise. They admit a few things:

It's not perfect for every language: It works best for languages that follow specific rules (LALR(1)), like SQL. It can't handle every possible type of grammar in the world yet.
It changes the "flavor": By forcing the robot to stay on the tracks, it slightly changes the way the robot picks words. The paper measured this and found that for very small robots, this change matters, but for big, smart robots, the benefit of being correct outweighs the slight change in style.
Cold Starts: When a brand new database arrives, there is a tiny, temporary slowdown (about 34% for a split second) while the system builds the new tracks. But this only happens once per new database, and it doesn't stop the other robots from working.

In short, GRID is like building a super-safe, high-speed train system for AI. It doesn't just tell the AI "don't crash"; it builds the tracks so that crashing is physically impossible, while keeping the train moving fast enough to be useful in the real world.

Technical Summary: GRID (Grammar-Railed Decoding for Enterprise SQL)

1. Problem Statement

The paper addresses the gap between Large Language Models (LLMs) generating "plausible" text and the strict requirements of enterprise SQL generation. In enterprise CRUD/RBAC (Role-Based Access Control) deployments, outputs must be syntactically valid, adhere to per-role and per-schema policies, and provide provable guarantees rather than best-effort results. The authors identify six critical challenges that existing solutions fail to solve simultaneously:

Joint Validity and Policy: Outputs must parse under the specific SQL dialect while strictly enforcing role-based verb restrictions and schema-specific vocabulary (real tables/columns) by construction, not via post-hoc filtering.
Provable Guarantees: Systems must offer formal theorems for soundness (never emitting invalid tokens), completeness (never blocking valid continuations), and termination, verified by specific tests.
Flat Per-Token Cost (Requirement R): The cost of the "guard rail" (masking) must be amortized $O(1)$ per token, independent of the generation length $n$ . Existing systems often suffer from costs that grow linearly or quadratically with context length.
Replayable Audit Trail: Compliance requires a hash-chained, bit-identical record of every permit/block decision to answer "what was allowed and why" after the fact.
Serving Reality: Production environments involve batched, heterogeneous requests. The system must handle "cold-schema" arrivals (new schemas not seen before) without stalling warm co-batched requests or substituting approximate masks.
Honest Boundaries: The system must explicitly acknowledge what cannot be enforced by a left-to-right context-free mask (specifically column-level RBAC) and provide mechanisms to handle this residue.

2. Methodology: Grammar-Railed Decoding

GRID introduces a novel architecture where everything is keyed on parser configurations rather than token sequences.

Core Architectural Idea

Instead of precomputing validity tables over token sequences (which scale combinatorially), GRID keys all masks, cache entries, and audit records on the parser configuration. A configuration $\kappa$ is defined as the pair $(\sigma, \rho)$ :

$\sigma$ : The LALR(1) parser stack.
$\rho$ : The lexer scan state over the current partial lexeme (remainder bytes).

This configuration uniquely determines the set of viable prefixes (continuations that can lead to a valid sentence).

Key Components

Viable-Prefix Oracle: The incremental LALR(1) parser itself acts as the oracle. By simulating the reduce chain on a virtual stack, the system determines the set of allowed terminals. This avoids the "acceptance semantics deadlock" where single-token prefixes might be rejected if the system only checked for complete sentences.
Token-Terminal Bridge: Since LLM tokens (byte strings) do not align with grammar lexemes, GRID uses a byte-level trie walk.
- Context-Independent (CI) Tokens: Tokens that resolve within the current lexeme or end exactly at a terminal boundary. These are cacheable.
- Context-Dependent (CD) Tokens: Tokens that cross a terminal boundary (e.g., completing a keyword and starting a new one). These are never cached; they are checked against the live stack at every step to ensure soundness.
Policy Compilation:
- Role Projections (L2): Subset the grammar productions (e.g., removing DELETE verbs) and eliminate useless symbols.
- Schema Lexicons (L3): Restrict identifier terminals to allow-lists derived from the database catalog.
- Identifier Composition Rule: At identifier positions, the mask is derived strictly from the intersection of the token trie and the schema lexicon trie, preventing generic cache entries from admitting forbidden identifiers.
Caching Strategy (OBL-KEY1): A two-tier write-back cache (T1 for specific grammars, T2 for shared grammar families) uses configuration-derived keys. The system enforces a "Myhill–Nerode-style refinement" where any two configurations sharing a key must produce byte-identical CI masks.
Audit Chain: Every step appends a record (step, config hash, mask entry ID, token, blocked count) chained via BLAKE2b. This allows bit-identical replay of generations against archived artifacts.

System Implementation

Rust Kernels: The hot path (trie walk, CD verdicts, LALR advance, bitmask fill) is implemented in Rust to minimize latency and release the Python GIL.
Serving Contract (vLLM): The system overlaps mask computation on the CPU with the GPU forward pass. If a cold-schema request's mask is not ready, it is deferred for one round, ensuring co-batched warm requests are never stalled.
Checker-Guided Repair: For the residue that masks cannot enforce (column-level RBAC), the system uses a post-parse semantic checker. If a violation is detected, the system can guide a repair pass to correct the query.

3. Key Contributions

Formal Framework: A configuration-keyed constrained decoding framework using an incremental LALR(1) parser as a viable-prefix oracle, with a byte-level token-to-terminal bridge and a context-independent/context-dependent split.
Provable Guarantees: Four guarantees (Soundness, Completeness, Termination, Flat Cost) stated as propositions with explicit preconditions, paired with specific tests for verification.
System Realization: A production-ready system (v4–v7 kernels) featuring a grammar pipeline, Rust kernels, a two-tier cache, and a hash-chained audit log.
Benchmark Record: Comprehensive evaluation including per-token latency, requirement R slope measurements, MaskBench (JSON Schema), Spider execution accuracy, and end-to-end vLLM serving records.

4. Results

Latency: On an H100 SXM5 runner, GRID achieves a median per-token mask latency of 3.6–6.7 µs (p50) and 80–109 µs (p90), outperforming llguidance and XGrammar at p50 and p90 on both gpt2 and Qwen tokenizers. llguidance retains the flattest p99 tail.
Requirement R (Flat Cost): At $n=16,000$ tokens, the per-token cost slope is effectively zero ( $\approx 0$ ), confirming $O(1)$ amortized cost. In contrast, older guidance versions showed quadratic growth.
Execution Accuracy (Spider):
- 0.5B Model: Constrained decoding alone yields +13 execution accuracy (EX) points over unconstrained generation (29.0% vs 16.0%).
- 7B Model: The mask alone provides ~+1 point. However, adding a checker-guided repair pass for column-level violations lifts execution to 94.5% (EX +2.3 over unconstrained).
Serving Overhead: Under vLLM with batch size 32, the overhead is +1.51% time-per-output-token.
Cold-Start Handling: A fresh schema incurs a 27.3 ms specialization time and ~0.7 ms first-token latency. While this causes a transient **34% slowdown** for co-batched warm requests during the specialization window (due to CPU/memory bandwidth contention), the warm requests are never stalled, and the fresh request runs at 1.00× warm speed thereafter.
Audit Integrity: 1,000 generations were replayed bit-identically with 100% tamper detection.

5. Significance and Honest Boundaries

The paper claims that GRID demonstrates that enterprise-grade constrained decoding is achievable by committing to configuration-keyed decoding. This single commitment enables policy compilation, provable guarantees, flat costs, and replayable audits.

The authors are explicit about the system's limitations and boundaries:

Distribution Faithfulness: The paper does not claim that masking preserves the original probability distribution $P(x | x \in L)$ ; it renormalizes locally. The impact is measured via downstream execution accuracy, not distributional neutrality.
Column-Level RBAC: The paper proves (Proposition 11) that column-level restrictions cannot be enforced by a left-to-right CFG mask because the necessary alias-to-table binding is unknown at the column-mask time. This is handled via post-parse checking and repair, not the mask itself.
Language Scope: The system is limited to LALR(1) languages. While it handles standard SQL dialects, it declares compile errors for non-LALR(1) constructs (e.g., certain JSON Schema patterns).
Cold-Window Contention: The transient slowdown for co-batched requests during a new schema's specialization is acknowledged as a genuine host CPU/memory-bandwidth contention issue, not a software defect, representing a compute-isolation trade-off.
Termination: Full termination guarantees (reserve-completed stops) hold only in the GRID-owned decode loop; processor-only serving modes may truncate.

In summary, GRID provides a rigorous, high-performance framework for enterprise SQL generation that prioritizes correctness, policy enforcement, and auditability, while honestly delineating the limits of what can be enforced via grammar masking.