# Semantic Prefix Oracles for LLM Decoding: Contracts and Differential Validation

arXiv: https://arxiv.org/abs/2609.35425 · HTML: https://mlsanity.com/paper/2609.35425/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 27 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Builds on (most cited first, 14 of 14)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [CRANE: Reasoning with constrained LLM generation](https://mlsanity.com/paper/2502.09061/) (2025)
- [Type-Constrained Code Generation with Language Models](https://mlsanity.com/paper/2504.09246/) (2025)
- [IterGen: Iterative Semantic-aware Structured LLM Generation with Backtracking](https://mlsanity.com/paper/2410.07295/) (2024)
- [ChopChop: a Programmable Framework for Semantically Constraining the Output of Language Models](https://mlsanity.com/paper/2509.00360/) (2025)
- [Hazelnut: A Bidirectionally Typed Structure Editor Calculus](https://mlsanity.com/paper/1607.04180/) (2016)
- [Earley-Driven Dynamic Pruning for Efficient Structured Decoding](https://mlsanity.com/paper/2506.01151/) (2025)
- [Merlin: A Language Server for OCaml (Experience Report)](https://mlsanity.com/paper/1807.06702/) (2018)

## Abstract (arXiv)

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 safe pruning: it rejects only prefixes whose semantic contradictions cannot be repaired by any continuation. A separate, grammar-dependent, 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 (textttocamlc, textttcc). 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.