Grammar-Based Sampling

The primary feature is the guarantee of syntactically correct output. By defining a formal grammar (e.g., a JSON Schema or a context-free grammar), the model's token-by-token generation is constrained to only select tokens that are valid according to the grammar's production rules. This eliminates malformed brackets, missing commas, or invalid keywords, producing outputs that are machine-parseable by default. For example, when generating an API response, the grammar ensures every opening { has a corresponding closing } and all required fields are present.

Grammar-based sampling is implemented via constrained decoding algorithms at inference time. These algorithms, such as guidance or integrated library features, work within the model's beam search or sampling process. At each generation step, the algorithm:

• Consults the defined grammar to determine the set of allowable next tokens.
• Masks out all tokens that would lead to an invalid parse tree.
• Allows the model to distribute probability only over the valid token subset. This happens transparently to the underlying language model, which still generates the content, but its choices are funneled through the grammar's structure.

The technique enforces not just syntax, but data structure and types. When using a JSON Schema, the grammar specifies required properties, data types (string, integer, boolean), allowed enumerations, and nested object structures. This moves beyond simple formatting to content validation. For instance, a schema can force a "temperature" field to be a number, a "status" field to be one of ["success", "error"], and an "items" field to be an array of objects with a specific shape. The model must generate content that fits this typed schema.

By structurally preventing invalid outputs, grammar-based sampling drastically reduces the need for post-processing and retry loops. In traditional prompting, a model might generate a nearly-correct JSON object with a subtle syntax error, requiring parsing, validation, and a corrective API call—a process prone to failure. With grammar constraints, the output is guaranteed to be parseable, eliminating entire classes of integration errors. This increases reliability in production pipelines and reduces latency by avoiding multiple round-trips to the model for correction.

The technique is not limited to simple lists or flat objects. Modern implementations support recursive and nested grammars, enabling the generation of complex outputs like:

• Full HTML documents with proper tag nesting.
• Programming language code (e.g., Python, SQL) that must follow the language's syntax.
• Mathematical expressions in LaTeX.
• Multi-turn dialogue structures with specific turn-taking rules. The grammar acts as a scaffold, guiding the model through the hierarchical generation of deeply nested structures that would be extremely error-prone with unstructured generation.

Grammar-based sampling is foundational for reliable function calling in agentic systems. Instead of asking a model to "generate a function call," the system provides a grammar that exactly matches the signature of the available tools (function name, parameter object schema). The model's generation is constrained to produce a valid function invocation object. This ensures the output can be directly passed to a code interpreter or API dispatcher without risky eval() statements or JSON parsing attempts, making agent-tool interactions deterministic and secure.

The primary use case is generating syntactically valid JSON, XML, YAML, or SQL directly from natural language requests. This is critical for API integration, where a model's output must be parsed by downstream software without errors.

• Example: A user asks, "List the top 3 products with price > $50." The grammar restricts the model to output only valid JSON matching a predefined schema: {"products": [{"name": "...", "price": ...}]}.
• Benefit: Eliminates post-processing regex or error-prone manual correction, enabling fully automated workflows.

Grammar-based sampling can enforce the syntax of custom configuration files, query languages, or internal DSLs.

• Example: Generating valid AWS CloudFormation templates, Kubernetes manifests, or GraphQL queries from a plain English description of infrastructure needs.
• Example: A model instructed to create a data pipeline could be constrained to output valid Apache Airflow DAG code. The formal grammar ensures every required parameter and bracket is correctly placed, producing executable code.

Beyond simple snippets, grammars can enforce correct syntax for entire function blocks, class definitions, or API calls in programming languages like Python, JavaScript, or Go.

• Example: A prompt asks for "a Python function that validates an email address." The grammar ensures the output is a complete, syntactically valid function definition with proper indentation, colons, and parentheses.
• Benefit: This drastically reduces the rate of syntax errors and runtime exceptions in generated code, allowing for safer integration into developer IDEs and CI/CD pipelines.

Grammars can be used to structure multi-turn dialogue or enforce specific response formats in chat applications.

• Example: A customer service agent model can be constrained to always output a response containing three structured fields: {"acknowledgment": "...", "answer": "...", "follow_up_question": "..."}.
• Example: For a game, a model's narrative output could be forced to follow a story grammar that requires a [SETTING], [CHARACTER_ACTION], and [DIALOGUE] tag in a specific order, creating predictable, parsable narrative chunks.

While JSON Schema is a common constraint, grammar-based sampling is a more general and powerful superset.

• JSON Schema: Defines valid data shapes (required fields, data types). It is a specific grammar for JSON objects.
• Formal Grammar (CFG): Can define any recursive, nested structure, including code, configuration languages, and complex markup. It operates at the token sequence level.

Key Difference: A JSON Schema ensures {"name": "John"} is valid. A formal grammar can ensure if (x > 0) { return true; } is a valid JavaScript statement block, or that <div><p>Hello</p></div> is valid, well-formed HTML.

The overarching category of techniques for producing model outputs that adhere to a predefined format. This includes:

• Grammar-based sampling as a formal, token-level constraint.
• JSON Schema enforcement via prompting.
• Output format directives that specify syntax like XML or YAML.
• Response schemas provided as blueprints within the prompt. The goal is deterministic formatting for reliable machine parsing.

A family of inference-time algorithms that restrict the model's token generation to a valid set. Grammar-based sampling is a specific implementation.

Other methods include:

• Token masking: Dynamically disabling invalid tokens at each step.
• Finite-state machine guidance: Using regex or automata to validate partial outputs.
• Speculative decoding: Using a smaller draft model to propose tokens validated by a larger model. All aim to guarantee output structure without model fine-tuning.

A prompting technique where a formal JSON Schema definition is provided in-context to guide the model's output. Unlike grammar-based sampling, it operates at the instruction level, relying on the model's ability to understand and follow the schema.

Key differences from grammar-based sampling:

• Operates via instruction, not token-level constraints.
• More flexible but less guaranteed; the model may still produce invalid JSON.
• Often used in conjunction with a post-processing validator to catch errors.

The engineering goal of ensuring a language model's output consistently matches a precise, repeatable structure for downstream integration. Grammar-based sampling is a primary technical solution to achieve this.

Why it matters for production:

• Enables reliable parsing by other software systems.
• Eliminates manual cleanup or error-handling for malformed outputs.
• Is critical for agentic systems where output is fed directly into tools or APIs.
• Contrasts with free-form natural language generation.

An instruction within a system prompt that mandates the structure or syntax of the model's response. This is a high-level, instruction-based approach to structured generation.

Examples:

• "Always output your answer as a valid JSON object."
• "Format the list in Markdown table syntax."
• "Use YAML with the following keys: ..."

Relationship to grammar-based sampling: A format directive is the instruction; grammar-based sampling is a mechanism to enforce it deterministically. They are often used together.

A blueprint or template that defines the required fields, data types, and often examples for the model's output. It is commonly provided within a prompt as a code comment or structured example.

Implementation:

pythonCopy
# Output schema:
# {
#   "summary": "<string>",
#   "confidence": <float 0-1>,
#   "keywords": ["<string>", ...]
# }

Usage: The model is instructed to follow the schema. Grammar-based sampling can then use a formal grammar derived from this schema to make compliance guaranteed, not just probable.