Structured Generation and Constrained Decoding

Ask a model for JSON and roughly some fraction of the time you get JSON wrapped in an apology, a trailing comma, a code fence, or a hallucinated field. Retrying and regex-scrubbing the output is the folk remedy, and it is a losing game at scale. Constrained decoding removes the problem at the source: at every decode step, before sampling, you set the logits of every token that would break the required structure to negative infinity. The model can only sample from what is still legal. If the grammar says the next character must be } or a digit, every other token in the 128k vocabulary is masked out and cannot be chosen, no matter how confident the model was about emitting prose. The output is valid by construction, not by luck.

Constraints as a state machine over the vocabulary

The mechanism starts by turning the desired shape into an automaton. A regular expression or a JSON schema (which, for a fixed set of fields and types, is a regular language) compiles to a finite-state machine (FSM): a set of states, and for each state a set of characters that advance it to a next state. ^\d{3}-\d{4}$ becomes seven states in a line; a JSON object schema becomes a larger FSM that walks {, a quoted key, :, a typed value, then either , or }.

Generation then rides that FSM. You track which state you are in; the allowed next characters are exactly the outgoing edges of that state; you mask any token that does not begin with an allowed character; you sample; you advance the state. At end-of-string states you allow the EOS token, everywhere else you forbid it. Nothing invalid can ever be sampled because it was never on the table.

The naive version of this is ruinously slow. At every step you would scan all ~100k+ tokens in the vocabulary against the current FSM state to decide which are legal, at every one of hundreds of decode steps. The central contribution of Willard and Louf's Outlines paper is to do that work once, offline. For each FSM state they precompute the set of vocabulary tokens that are valid from it and store it as an index. At decode time, reading "which tokens are allowed now" is a dictionary lookup keyed by the current state, roughly O(1) in the vocabulary size rather than O(vocab). The paper frames text generation itself as FSM transitions and shows the guidance adds "little overhead to the token sequence generation process." That shift, from per-step vocabulary scan to precomputed index, is what made constrained decoding cheap enough to leave on in production.

Beyond regular: context-free grammars

Regular languages cannot count matching brackets to arbitrary depth, so an FSM cannot express arbitrarily nested JSON, a programming language, or a recursive data structure. For those you need a context-free grammar (CFG) and a pushdown automaton (an FSM plus a stack). llama.cpp's GBNF (GGML BNF) is the widely used practical form: a Backus-Naur grammar, extended with regex-style character ranges and repetition operators (*, +, ?, {m,n}), that "constrain model outputs in llama.cpp". You write production rules such as object ::= "{" ws (pair ("," ws pair)*)? "}" and the sampler enforces them. GBNF can express valid JSON, chess notation in algebraic form, arithmetic expressions, or a bespoke DSL, and llama.cpp can convert a JSON schema into GBNF for you.

The general engines specialise here. XGrammar compiles EBNF grammars and aims for "flexible zero-overhead structure generation," precomputing the per-state token masks so that even recursive grammars mask in near-constant time. vLLM exposes all of this through its structured-outputs API with several constraint types: choice (output is exactly one of a fixed list), regex, json schema, and full context-free grammar, dispatched to a backend such as XGrammar or Guidance.

JSON mode is not constrained decoding

Vendor "JSON mode" and true constrained decoding are easy to conflate and important to separate. JSON mode is typically a soft guarantee: the API biases or post-processes the model toward well-formed JSON, often by fine-tuning plus a light validity check, and it does not let you pin an arbitrary schema at the token level. Function calling / structured outputs that are backed by a compiled grammar are the hard guarantee: the schema you pass becomes the automaton that masks logits, so the result provably validates. When correctness matters (the output feeds a parser that will crash on malformed input), you want the grammar-backed path, and you want to know which one your provider actually implements. The same machinery runs across the serving stack: vLLM, Hugging Face TGI (guided decoding), llama.cpp (GBNF), and standalone engines like XGrammar and Outlines.

The tokenisation-alignment subtlety

Here is the wrinkle that makes this genuinely hard rather than merely fiddly. The grammar is defined over characters, but the model generates over tokens, and tokens do not respect character boundaries. A single token can span a boundary the FSM cares about: the byte-pair token ": covers a quote and a colon at once, and a token like _true might carry a leading space plus a keyword. So masking cannot ask "does this token equal an allowed character"; it must ask "does this token's string extend the current partial output along some legal path through the automaton", which can require advancing the FSM through several states for one token, and can leave the FSM mid-token in an intermediate position. Getting this wrong produces subtle bugs: legal completions silently pruned, or a token accepted that paints the sequence into a dead end from which no legal continuation exists. This alignment between a character-level grammar and a subword tokeniser is exactly the bookkeeping the precomputed index in Outlines and the compiled masks in XGrammar exist to handle correctly and cheaply.

When it falls down

• Syntax is not semantics. A grammar guarantees the output parses; it says nothing about whether the content is right. {"temperature_celsius": 6000} is perfect JSON and a wrong answer. Constrained decoding eliminates format errors, not factual or logical ones, and it can lull you into trusting output that is merely well-formed.
• Forcing low-probability tokens degrades quality. If the model genuinely "wanted" to answer "I cannot determine this from the passage" but the schema demands a float, masking forces it down a path it assigned low probability to. You get a confident-looking number invented to satisfy the structure. The tighter the constraint fights the model's actual distribution, the worse the answer, even as validity stays perfect.
• Grammar-compilation latency. Building the FSM and its token index is not free; a large or pathological grammar can take noticeable time to compile, paid before first token. Engines cache compiled grammars, so this bites hardest when every request carries a fresh unique schema.
• It can suppress reasoning. Force the model into a rigid JSON object from token one and you deny it the scratch space to think. Chain-of-thought lives in free-form prose; a schema with no room for it can measurably lower accuracy on hard tasks. The usual fix is to allow a free-text reasoning field before the structured fields, or to generate reasoning unconstrained and only constrain a final extraction step.
• Pathological grammars sample slowly. As llama.cpp's own docs note, some grammar patterns cause performance issues during sampling even when they are semantically correct; deeply ambiguous or heavily backtracking rules are the usual culprits.

A note on scope: constrained decoding is the hard, token-level guarantee. Prompt-side coercion (asking nicely, giving examples, threatening to reject) is a separate, softer technique that shapes the distribution without enforcing anything, and it is covered on its own. Reach for the grammar when a downstream parser must never see malformed input; reach for the prompt when you want structure but can tolerate the occasional miss.

Further reading

• Efficient Guided Generation for Large Language Models (Willard and Louf) - the Outlines paper; reframes generation as FSM transitions and introduces the per-state vocabulary index that makes masking near O(1).
• llama.cpp GBNF grammar guide - the practical BNF-with-extensions format for constraining local inference, plus JSON-schema-to-GBNF conversion.
• vLLM structured outputs documentation - the choice / regex / json / grammar constraint API and its pluggable backends (XGrammar, Guidance).
• XGrammar documentation - the "zero-overhead" grammar engine used as a backend across serving stacks.