Language models generate text token by token, selecting each token from a probability distribution over tens of thousands of vocabulary entries. While this produces fluent natural language, it provides no structural guarantees — an LLM asked to output JSON might produce invalid syntax, miss required fields, or hallucinate enum values. Grammar-guided generation solves this by enforcing formal grammar constraints during the decoding process itself, making it mathematically impossible for the model to produce structurally invalid output.
The key insight is deceptively simple: at each token generation step, compute which tokens would lead to a valid continuation according to a formal grammar, then mask out all other tokens before sampling. This technique is called constrained decoding (also known as guided decoding or structured generation), and it turns the problem of output validation from a post-hoc retry loop into a compile-time guarantee.
Three major open-source engines have emerged as the standard implementations: XGrammar (from MLC-AI), Outlines (from Dottxt), and llguidance (from Microsoft/Guidance). Each takes a different approach to the same fundamental problem, and all three are now integrated into production serving engines like vLLM and SGLang.
Grammar-guided generation operates as an additional step inserted into the standard LLM decoding loop. The pipeline works as follows:
A token mask is a binary vector of size |V| (vocabulary size, typically 32k–128k tokens). A 1 at position i means token i is a valid next token according to the grammar; a 0 means it would violate the grammar. By setting masked logits to -∞ before softmax, the probability of invalid tokens becomes exactly zero.
XGrammar, developed by the MLC-AI team, achieves exceptional performance through a clever optimization: it divides the vocabulary into context-independent tokens (whose validity can be determined at compile time) and context-dependent tokens (which require runtime evaluation). For a typical JSON Schema, 90–95% of tokens are context-independent, meaning their masks can be precomputed and cached.
XGrammar uses a pushdown automaton (PDA) to track the grammar state as tokens are generated. The PDA maintains a stack of grammar states, and at each step, XGrammar uses the stack top to index into an adaptive token mask cache. This architecture achieves processing times of approximately 50 microseconds per token for a 128k-token vocabulary — fast enough to add near-zero overhead to LLM serving.
# XGrammar usage with a JSON schema
import xgrammar as xgr
# Compile grammar from JSON schema
compiler = xgr.GrammarCompiler(tokenizer_info)
compiled_grammar = compiler.compile_json_schema(json_schema_string)
# Create matcher for tracking state
matcher = xgr.GrammarMatcher(compiled_grammar)
# During generation loop
token_bitmask = xgr.allocate_token_bitmask(1, tokenizer_info.vocab_size)
while not matcher.is_terminated():
matcher.fill_next_token_bitmask(token_bitmask)
xgr.apply_token_bitmask_inplace(logits, token_bitmask)
# Sample from masked logits
next_token = sample(logits)
matcher.accept_token(next_token)Outlines, developed by Dottxt, takes a finite-state machine (FSM) approach. For each constraint type — regex, JSON Schema, or context-free grammar — Outlines builds an FSM that tracks valid next tokens at each position. The FSM approach is particularly elegant for regex constraints, where the mapping from regex to FSM is well-understood from automata theory.
Outlines supports multiple constraint types through a unified interface:
# Outlines structured generation examples
import outlines
model = outlines.models.transformers("mistralai/Mistral-7B-v0.1")
# Regex-guided generation
phone_gen = outlines.generate.regex(model, r"\(\d{3}\) \d{3}-\d{4}")
phone = phone_gen("Give me a US phone number:")
# JSON Schema from Pydantic model
from pydantic import BaseModel
class Person(BaseModel):
name: str
age: int
email: str
json_gen = outlines.generate.json(model, Person)
person = json_gen("Extract the person's info: John is 30, john@example.com")The core engine, outlines-core, has been rewritten in Rust for performance, providing the FSM construction and token masking operations as a compiled library that can be called from Python.
llguidance, developed by Microsoft as part of the Guidance project, uses a derivative-based regex engine (derivre) for lexical analysis combined with an optimized Earley parser for context-free grammar rules. This combination gives it broad grammar coverage while maintaining high performance — approximately 50 microseconds of CPU time per token for a 128k tokenizer.
llguidance has achieved wide adoption across the ecosystem. It is used by Guidance, llama.cpp, SGLang, vLLM, and as of mid-2025, OpenAI has adopted llguidance for their structured outputs feature, increasing their JSON Schema coverage and performance.
A Brzozowski derivative of a regular language L with respect to a character c is the set of strings w such that cw is in L. llguidance extends this concept to work with multi-character tokens, computing which tokens can appear at each position by taking derivatives of the remaining grammar with respect to each candidate token’s characters.
All three engines support multiple grammar representations, each with different expressiveness and performance characteristics:
The most common use case is ensuring LLM outputs conform to a JSON Schema. In production API servers using vLLM or SGLang, grammar-guided generation is enabled by passing a JSON Schema alongside the prompt. The serving engine selects XGrammar or llguidance as the backend and applies token masking transparently. This eliminates the need for retry loops when parsing model output — every response is guaranteed to be valid JSON matching the schema.
When generating SQL queries, Python code, or configuration files, a CFG constraint ensures the output is always syntactically valid. For example, a SQL grammar ensures proper keyword ordering, balanced parentheses, and valid clause structure. While this doesn’t guarantee semantic correctness (the query might reference non-existent tables), it eliminates an entire class of parsing errors.
In information extraction pipelines, grammar-guided generation ensures extracted entities are returned in a consistent, parseable format. For example, extracting product specifications from unstructured text into a schema with typed fields (price as float, dimensions as nested object, features as string array) is guaranteed to produce valid output on every call.
AI agents that invoke tools need to produce valid function call arguments. Grammar-guided generation ensures tool arguments always match the expected schema — correct parameter names, proper types, valid enum values — reducing error handling complexity in agent loops. XGrammar 2 specifically optimizes for agentic scenarios with dynamic grammar switching between tool definitions.
Grammar compilation has a one-time cost that varies by complexity: simple JSON schemas compile in under 1 millisecond, while complex CFGs may take 10–100 milliseconds. The per-token overhead is minimal — XGrammar and llguidance both achieve ~50 microseconds per token, which is negligible compared to the model’s own inference time (typically 5–50 milliseconds per token). However, constrained decoding can slightly reduce throughput in batched serving because different requests may have different masks, preventing some CUDA kernel optimizations.