grammar-based sampling

**Grammar-based sampling** is a structured generation technique that constrains LLM token generation to follow a **formal grammar** — typically a **context-free grammar (CFG)** — ensuring that output always conforms to a specified syntactic structure. It is more powerful than regex-based constraints because grammars can express **recursive** and **nested** structures. **How It Works** - **Grammar Definition**: You specify a formal grammar (often in **EBNF** or **GBNF** notation) that defines valid output structures. For example, a JSON grammar defines the recursive rules for objects, arrays, strings, numbers, etc. - **Parse State Tracking**: At each generation step, the system maintains the current position in the grammar's parse tree. - **Token Masking**: Only tokens that represent valid continuations according to the grammar are allowed. All others are masked out (set to probability zero) before sampling. - **Guaranteed Compliance**: By construction, the final output is always a valid sentence in the specified grammar. **Grammar Formats** - **GBNF (GGML BNF)**: Used by **llama.cpp** — a simple BNF variant for specifying generation grammars. - **Lark/EBNF**: Used by **Outlines** library — supports full EBNF grammars with regular expression terminals. - **JSON Schema → Grammar**: Many tools automatically convert JSON schemas into grammars for structured output generation. **Advantages Over Simpler Constraints** - **Recursive Structures**: Unlike regex, grammars can handle **nested JSON**, **code with matched parentheses**, **XML/HTML**, and other recursive formats. - **Complex Formats**: Can enforce **SQL syntax**, **function call formats**, **API response structures**, and domain-specific languages. - **Composability**: Grammar rules can be modular and reused. **Implementations** - **llama.cpp**: Built-in GBNF grammar support for local model inference. - **Outlines**: Python library supporting Lark grammars and JSON schema constraints with HuggingFace models. - **Guidance**: Microsoft's library for constrained generation with grammar-like control flow. Grammar-based sampling enables the **most reliable structured output generation** from LLMs, making it essential for applications that require format-perfect data extraction, code generation, or API response formatting.