Technical Summary: Decode-Time Grammars

1. Problem Statement

Large Language Models (LLMs) are increasingly used to generate code for agents and serving systems where generated output is compiled or executed without human review. While this works for mainstream languages, it remains brittle for low-resource programming surfaces such as domain-specific languages (DSLs), custom library APIs, and command-line tools.

A recurring failure mode in these environments is the ghost reference: a syntactically valid token (e.g., a variable name, column, API function, or CLI option) that does not exist in the current runtime environment $\Gamma$.

• Examples: Referencing a buffer never declared in a TileLang kernel, selecting a column absent from a SQL schema, or calling an intrinsic not available in a specific library version.
• Root Cause: These errors often stem from negative transfer, where the model applies knowledge of a neighboring dialect, an older API version, or a different tool interface to the target environment.
• Limitations of Existing Remedies:
  • Fixed Grammars: Standard grammar-constrained decoding (e.g., CFGs) ensures syntactic validity but treats reference positions as open classes (e.g., identifier), admitting both valid and invalid names.
  • Model-Side Remedies: Prompting, fine-tuning, or retry mechanisms can reduce the probability of errors but cannot remove invalid continuations from the model's support set. They rely on the model "preferring" the correct path, which is insufficient when the wrong path is fluent and high-probability.

2. Methodology: Decode-Time Grammars

The paper introduces decode-time grammars, a framework where grammar fragments are instantiated dynamically during generation based on a runtime environment $\Gamma$.

Core Mechanism

1. Runtime Environment ($\Gamma$): A snapshot of the current state, containing in-scope names, sorts, shapes, schema entries, API members, or tool state. $\Gamma$ evolves as declarations are generated.
2. Grammar Fragments & Refinement Order: Instead of a single fixed grammar, the system uses a library of grammar fragments ordered by refinement ($\sqsubseteq$).
   • Fragments range from coarse (e.g., accepting any identifier) to tight (e.g., accepting only names declared in $\Gamma$).
   • A per-region policy $\pi(s, \Gamma)$ selects the appropriate fragment for a specific "hole" (a typed position in the generation) based on the expected sort $s$ and current environment.
3. The $\tau_\Gamma$ Operator (Tightening): This is the critical mechanism. It transforms an open reference position in a fragment into a $\Gamma$-typed slot.
   • The slot's candidate set is exactly the names available in $\Gamma$ (e.g., Gamma.names(sort=Buffer)).
   • These candidates are compiled into an escaped alternation (e.g., "A" | "B" | "C") and injected into the token-level recognizer before decoding that region.
4. Self-Extending Generation: As the model generates declarations, they are extracted and added to $\Gamma$ before subsequent reference holes are decoded. This ensures that references are constrained by the prefix already generated.

System Architecture

The implementation, gproj, consists of two components:

• TemplateInductor (Offline): Uses anti-unification on small corpora to induce grammar fragments and policies. It validates fragments against a "hard gate" using corpus positives and auto-generated negatives (including mined ghost references) to ensure executability and correctness.
• gproj Executor (Online): An online masked executor that maintains $\Gamma$, queries the policy $\pi$, instantiates fragments via $\tau_\Gamma$, and compiles the resulting grammar into a token mask for the LLM decoder (e.g., XGrammar).

3. Key Contributions & Formal Results

Theoretical Contributions

• No-Ghost Soundness: The paper proves that for any fragment where reference positions are realized as $\Gamma$-typed slots, the generated strings are scope-safe by construction. Every emitted reference is guaranteed to be in $\text{dom}(\Gamma)$.
• Refinement Preservation: It is proven that if a looser fragment is sound, any tighter refinement (via $\tau_\Gamma$) preserves this soundness. This allows the system to switch between fragment strengths dynamically without reintroducing errors.
• Necessity of Dynamic Support (Proposition 3): The paper proves that no finite family of precompiled grammars with fixed reference supports can be both sound (no ghost references) and non-blocking (allowing all valid continuations) for unbounded identifier spaces.
  • Implication: Exact reference support must be synthesized during decoding based on the prefix. Static pre-compilation is theoretically insufficient for declaration-consistent languages.

Practical Contributions

• Division of Labor: The approach separates environment-bound correctness (handled by the mask) from open-ended program decisions (handled by the model). The mask guarantees that references are valid; the model chooses the algorithm, strategy, or intent.
• Induction Pipeline: A method to automatically generate the required grammar fragments and policies from small corpora, making the approach applicable to new DSLs without manual grammar engineering.

4. Evaluation Results

The system was evaluated across TileLang (tensor-kernel DSL), SQL (Spider dataset), P4 (data-plane language), and CLI tools (git, FFmpeg), using models ranging from 0.6B to 236B parameters.

• Elimination of Ghost References:
  • Across all surfaces, the $\Gamma$-typed arm (using $\tau_\Gamma$) achieved 0% ghost references by construction.
  • In contrast, open identifier arms (free decoding) failed due to ghost references in 100% of cases for TileLang, SQL, and P4, regardless of model size (0.6B to 236B).
  • Example: On SQL, open identifiers resulted in 0% execution match; $\Gamma$-constrained decoding achieved 100%.
• Model Independence: The guarantee transfers across model sizes. Even the 236B frontier model (DeepSeek-V4-Flash) failed to generate valid references without the mask, while the 0.6B model succeeded with the mask.
• Comparison to Alternatives:
  • Prompting/Retry: On SQL, prompting with schema and retrying up to 4 times achieved 90% execution match but still produced 5 ghost columns. The mask achieved 100% match with 0 ghosts in a single pass.
  • Cost: The approach incurs a moderate overhead. Relative to unconstrained decoding, end-to-end throughput reduction averaged 17.3%. Relative to standard constrained decoding (XGrammar), gproj reduced throughput by 10.6–17.8%.
• Offline Induction: The TemplateInductor successfully induced valid fragments for complex surfaces (e.g., AscendC operators, FFmpeg filters) that were not hand-written, validating the "induction + hard gate" workflow.

5. Significance and Claims

The paper claims that decode-time grammars provide a precise, stable slice of correctness that is orthogonal to model capability.

• Mechanical Guarantee: It transforms reference safety from a probabilistic outcome (dependent on model quality) into a construction-level guarantee.
• Scalability: By separating the "semantic sketch" (model's job) from "environment-bound references" (mask's job), the system allows weaker models to generate valid code in low-resource environments where they would otherwise hallucinate.
• Theoretical Necessity: The proof that static grammars cannot simultaneously be sound and non-blocking for declaration-consistent languages establishes the necessity of the proposed runtime instantiation approach.

The authors position this work not as a solution for whole-program semantic correctness (e.g., algorithmic logic or termination), but as a robust mechanism for eliminating the specific class of mechanically enumerable errors (undefined symbols) that plague code generation in constrained environments.