Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
To move beyond purely syntactic constrained decoding, this work introduces semantic grammar specifications that attach typing, scoping, and declaration constraints directly to context-free grammars during Earley parsing. The framework formally guarantees safe pruning—rejecting only prefixes with irrecoverable semantic violations—and establishes dead-end freedom conditions to ensure valid token-level continuations exist. Differentially validated against production compilers, the semantic oracle achieved zero false prunes on valid prefixes, detected 25 of 30 invalid programs mid-stream where syntax-only baselines detected none, and improved model task correctness by up to 15.2 percentage points.
Constrained decoding no longer has to stop at syntax: embedding type and scope checks directly into Earley parser descent prunes dead-end code mid-stream to deliver up to a 15-point gain in program correctness.
Constrained decoding can enforce regular or context-free output formats, but many program-generation failures are semantic: scope, typing, and declaration effects depend on context. We present semantic grammar specifications, a declarative formalism that attaches such constraints to a context-free surface and executes them during Earley descent. Our implementation enforces \emph{safe pruning}: it rejects only prefixes whose semantic contradictions cannot be repaired by any continuation. A separate, grammar-dependent, \emph{dead-end freedom} property guarantees the existence of a realizable witness for each remaining branch. We give simple sufficient conditions based on surface productivity, type coverage, and left-to-right constraint flow. Our finite-lambda, core ML, and C-like fragments satisfy them, while the STLC instance used in our experiments does not: plain STLC can violate type coverage, and we show how restricting its type universe recovers it. A tokenizer-lifting lemma carries character-level witnesses to token sequences under an explicit vocabulary-coverage hypothesis. We validate the implementation differentially against production compilers (\texttt{ocamlc}, \texttt{cc}). Across every prefix of 65 compiler-valid programs we observe zero false prunes. The semantic oracle localizes 25/30 invalid programs mid-stream, against 0/30 for a syntax-only oracle, and agrees on 42/42 recursion probes. A twelve-model generation study, including a matched semantic-versus-syntactic ablation for nine models, finds nonnegative observed semantic-minus-syntactic point estimates for every model-language pair, with maxima of $+15.2$ points on STLC task correctness and $+14.3$ points on ML validity.