Search papers, labs, and topics across Lattice.
This paper introduces decode-time grammars, a novel approach that enhances large language model (LLM) generation by constraining output to valid references based on the current runtime environment. By implementing a region-specific policy that selects grammar fragments and a tightening operator that replaces open reference positions with valid candidates, the method ensures both grammatical and semantic correctness in code generation. The results demonstrate that gproj effectively eliminates ghost references across various programming languages, significantly improving the reliability of LLM-generated code with only moderate overhead compared to standard constrained decoding.
Ghost references in LLM-generated code can be eliminated by constraining generation to valid runtime environments, ensuring both grammatical and semantic correctness.
Large language models now write a growing share of the world's code, increasingly inside agents and serving systems that compile, execute, or dispatch generated code without line-by-line review. This works well for mainstream languages but remains brittle for low-resource programming surfaces such as domain-specific languages, custom library APIs, and command-line tools. Even under grammar-constrained decoding, a model can still produce references invalid in the current environment: a buffer never declared, a column absent from the schema, a function the library does not provide, or an unsupported CLI option. This paper introduces decode-time grammars: grammar fragments instantiated during generation from a runtime environment Gamma. A region-specific policy selects a fragment for each hole, and a tightening operator replaces open reference positions with Gamma-typed slots whose candidates are exactly the names, fields, APIs, or options available at that point. Newly generated declarations enter Gamma before later regions are decoded, so the constraining grammar can depend on the prefix already generated. This ensures not only grammatical correctness but also semantic correctness, by preventing references to undefined symbols. We formalize grammar fragments as environment-indexed grammars ordered by refinement, prove No-Ghost soundness for Gamma-slotted fragments, show that refinement preserves this support-set guarantee, and characterize the boundary of mask-enforceable properties. We implement the approach in gproj with offline grammar induction and online policy resolution. Across TileLang, SQL, and P4, with models from 0.6B to 236B parameters, gproj eliminates ghost references by construction at moderate overhead over standard constrained decoding.
