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.