Grammars & CFG Constrained Decoding
Compile a CFG/GBNF to an automaton, mask illegal next tokens, keep a parse stack. Same idea as JSON Schema SO, but you can constrain SQL, arithmetic, or custom DSLs.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Why a compiled CFG mask wins over generate-then-regex
Prefer
Compile CFG → mask logits every token
The partial string is always a prefix of the language. Parsers downstream see either a complete valid program or a truncated prefix — not a random bracket salad.
- Illegal tokens never enter the beam; you do not burn samples on doomed suffixes.
- Same machinery as strict JSON Schema, reused for SQL and DSLs.
- Streaming stays on a valid parse path (see the streaming lesson).
Alternative
Sample freely, then regex / parse-repair
Works until the first mismatched quote. Then you retry, slice, or ship invalid SQL to the warehouse.
- Cheap to prototype; no grammar compiler in the hot path.
- Retokens and retries dominate cost on structured tasks.
- Repair can change meaning; a CFG would have blocked the bad token.
One decode step under a grammar
Phone-friendly vertical flow. The mermaid chart is the same loop with the stack test at the bottom.
- 1
Load CFG / GBNF and First sets
Productions plus FIRST/FOLLOW, compiled once. Cache the automaton; compile is the expensive part. - 2
Stack starts at the start symbol
Push Expr (or json_object, or sql_statement). The stack is the DPDA memory. - 3
Read model logits
Full vocabulary scores, as usual. - 4
Mask with the stack top
If the top is a terminal, only those token ids live. If it is a nonterminal, union FIRST of its productions. - 5
Sample, then advance
Pop a matched terminal, or expand a nonterminal and push RHS right-to-left. Repeat until the stack is empty (and EOS). - 6
Empty mask is a dead-end
Do not softmax a zero vector. Backtrack, relax the grammar, or fail the request.
Overview
Constrained decoding forces a language model to emit only strings in a formal language. The usual formalism is a context-free grammar (CFG), often written as GBNF (GBNF adds convenient sugar for optionals and repetition). At each token, a mask zeroes logits that would leave the language.
That is exactly what strict JSON Schema does after the provider compiles your schema. This page peels the schema off so you can see the grammar. Once you can whiteboard an arithmetic Expr, SQL SELECT, or a tiny DSL is the same drawing with different terminals.
Why it matters:
- Safety. Downstream parsers stop dying on mismatched
)or an extra JSON key the schema forbade. - Cost. Pruning illegal tokens early cuts wasted samples on structured tasks (the “generate JSON, fail, retry” tax).
- Product scope. Code-assist, config-assist, and warehouse-query features can ship without a post-hoc validator as the first line of defense.
- Compliance. Some domains require a formally constrained artifact before accept.
Validity is still syntactic. A grammar-valid SELECT can drop the wrong table. You still authorize and semantically check. The CFG is not your policy engine.
CFG pieces you actually need
| Piece | Role | In the sampler |
|---|---|---|
| Terminals | Concrete pieces: +, (, a number token, "SELECT" | Mapped to one or more tokenizer ids (many-to-many) |
| Nonterminals | Expr, Term, Factor | Expanded using productions |
| Productions | Factor → NUMBER | "(" Expr ")" | What the stack pushes |
| Parse stack | Expected symbols, top = next obligation | Lives across tokens (and across stream chunks) |
| FIRST sets | Terminals that can start a nonterminal | Build the mask without expanding at runtime |
| FOLLOW / epsilon | What can come after an optional / empty production | Why left-recursion and optionals need a compiler, not a toy loop |
GBNF is the file format llama.cpp / XGrammar-style stacks like: named rules, [ optional ], { repeat }, quoted literals. JSON Schema backends are a compiler from a schema AST to the same kind of bytecode, not a second algorithm.
Tokenization wrinkle: a grammar terminal "SELECT" may be one token or many, depending on the BPE. Production engines map bytes / tokens that spell each terminal, not Python characters. The playground below pretends one char = one terminal so you can see the stack. Interviews: mention the map; do not pretend it is 1:1 in production.
The mask loop
Decisions
- 1
Load CFG and First sets
- nextStack starts with start symbol
- 2
Stack starts with start symbol
- nextLM logits over vocab
- 3
LM logits over vocab
- nextMask from stack top plus First
- 4
Mask from stack top plus First
- nextSample greedy top-k or beam
- 5
Sample greedy top-k or beam
- nextTop was terminal?
- ?
Top was terminal?
- yesPop terminal
- noExpand NT: push RHS reversed
- 7
Pop terminal
- nextStack empty?
- 8
Expand NT: push RHS reversed
- nextStack empty?
- ?
Stack empty?
- noLM logits over vocab
- yesComplete string in the language
- 10
Complete string in the language
Lesson map
Grammars & CFG Constrained Decoding
Compile a CFG/GBNF to an automaton, mask illegal next tokens, keep a parse stack. Same idea as JSON Schema SO, but you can constrain SQL, arithmetic, or custom DSLs.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB load["Load CFG and First sets"] stack["Stack starts with start symbol"] logits["LM logits over vocab"] mask["Mask from stack top plus First"] load -->|Load CFG and First sets| stack stack -->|Stack starts with start symbol| logits logits -->|LM logits over vocab| mask
On a beam, each hypothesis has its own stack. Prune a beam, discard its stack. Memory scales with beam width.
On a stream, persist the stack in session state; each new token updates it. Partial output is always a prefix of a valid sentence — which is why streaming structured output can paint completed fields without waiting for a regex to “look like JSON.”
A tiny arithmetic grammar
Expr → Term (("+" | "-") Term)*
Term → Factor (("*" | "/") Factor)*
Factor → NUMBER | "(" Expr ")"NUMBER is a digit 0–9 in the playground (one terminal) so the mask stays readable.
After 2+: you have seen a Term and a +. The production still needs a Term, which must start with a Factor. FIRST(Factor) = { NUMBER, "(" }. A closing ) is illegal — you are not looking for FOLLOW(Expr); you are in the middle of Expr → Term + Term.
After 2+3 at the root: the Expr can end, or continue with + - * /. There is no unmatched (, so ) is still illegal. Completing a number does not magically allow a closer.
After (2+3: the inner Expr is complete and the Factor → "(" Expr ")" production still has ) on the stack. Now ) is legal (and so are operators that extend the inner Expr).
That distinction is the interview. People say “) is legal after a number.” Only if the stack says so.
Deep dive · Why JSON Schema is this grammar with different terminals
A closed object schema is a CFG whose terminals are {, }, ", :, ,, and the literals for each required key and enum. additionalProperties false removes the production “any identifier.” Required keys remove epsilon productions for missing fields. Compilers (OpenAI’s schema→CFG, XGrammar, Outlines, vLLM guided_json / guided_grammar) differ in bytecode and cache layout, not in the idea: stack + mask. When a provider cannot express SQL or a DSL as JSON Schema, you hand them GBNF or a regex instead of stuffing the DSL into a string field and hoping.
Compile-time automaton vs a parser in the loop
| Design | Prefer when | Cost |
|---|---|---|
| Compile CFG → DPDA / bytecode (XGrammar, many vLLM paths) | Serving, repeated schemas/grammars | Fast mask lookup; extra build step; cache the artifact |
| Runtime parser (walk a generic CFG each step) | Prototyping, tiny vocabs | Easier to hack; too slow at 100k-BPE × every token |
Regex / choice / json shortcuts (Outlines, vLLM) | The language is a regex, enum, or JSON Schema | Less power than a full CFG; less rope |
| Post-sample filter | Legacy sampler you cannot patch | Resample loops; still can stuck |
Mask granularity. A dense bitset over the full vocab is simple and wasteful. Engines keep a sparse map from grammar terminals to token ids. Building that map is where BPE pain lives (NUMBER is “all digit tokens,” not one id).
Integration point. Mask before softmax inside the sampler. Filtering after sample means you throw away a forward pass when you reject.
Fallback. If the mask is all zeros, the grammar and the tokenizer map disagree, or you hit a buggy production. Fail the request or backtrack one token. Sampling from a uniform empty set is how you emit ) after 2+ in production.
Local serving map
- vLLM structured outputs —
guided_json,guided_grammar,guided_regex,choice. Backend choice (XGrammar, Guidance, etc.) trades TTFT vs long generation. - XGrammar — compiles GBNF (and JSON Schema) to a VM that produces masks in the sample loop.
- Outlines — Python-first constrained generation (
json,regex,choice,grammar) over several engines.
Cache repeated grammars. A new GBNF on every request pays compile on the hot path — the same ops lesson as a new JSON Schema.
What a CFG cannot do
Cross-field business rules: invoice lines summing to total_cents, “this SKU exists,” “the user may see this row.” Those belong in validation / repair loops or in tools. Do not grow the grammar into a theorem prover.
Left-recursive productions and ambiguous grammars make compilers sad. Keep the grammar LL-friendly or use a backend that accepts your GBNF dialect — then test prefixes, not just complete strings.
In-memory Expr mask (run this)
No torch, no transformers, no tokenizer. Characters are terminals. We parse as far as the prefix allows, then print the allowed next terminals from the parse stack. Watch ) after 2+ versus after (2+3.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Expected story: after 2+, allowed starts with a digit or (, and ) is false. After 2+3, operators and EOF-ish completion, not ). After (2+3, ) becomes legal. 2+3) should error — that is the root-level closer people get wrong on a whiteboard.
Interview Q&A
How does CFG constrained decoding work in one paragraph?
Answer
Compile the grammar to an automaton. Keep a parse stack of expected symbols. At each step, compute legal next terminals from the stack top and FIRST sets, zero every other logit, sample, then pop a terminal or expand a nonterminal. The string stays a prefix of the language until the stack is empty.
Why is ')' illegal after 2+?
Answer
Plus still needs a Term / Factor. FIRST of Factor is a digit or '('. A closer is not in that set. You are in the middle of a production, not at FOLLOW of a finished Expr.
Then why is ')' legal after 2+3 in some slides?
Answer
Only if an unmatched '(' sits on the stack — i.e. the prefix is really (2+3 or you started inside Factor → '(' Expr ')'. At the root, 2+3 does not make ')' legal. Ask interviewers which prefix they mean; then show the stack.
Is JSON Schema a different algorithm?
Answer
No. Strict structured outputs compile a closed schema to a CFG and run this loop. The schema language is the frontend; the mask is the backend. GBNF is the frontend when the language is SQL or a DSL.
Compile-time automaton vs calling a parser library every token?
Answer
Compiled DPDA / bytecode is O(cheap) per step and what vLLM / XGrammar want in production. A generic parser per token is fine for a demo and too slow at full vocab. Regex shortcuts cover regular languages only.
What is a dead-end mask?
Answer
Every logit is illegal — tokenizer map bug, over-constrained grammar, or a state the compiler missed. Do not sample. Backtrack, relax, or fail the request. An all-zero mask is how garbage ')' tokens sneak out of a broken integration.
Does the grammar stop bad SQL semantically?
Answer
No. It can force SELECT shape and quoted identifiers. Dropping the wrong table, leaking rows, or ignoring tenant filters is authorization and policy. Pair with tools, allowlists, and validators.
How do you stream under a grammar?
Answer
Keep the stack in session state. Each token updates the stack and the mask. UI may paint completed terminals; commit side effects only after a full parse plus business validation. Truncation leaves a non-empty stack — treat as incomplete, not as JSON.parse salvage.
Beam search?
Answer
One stack per hypothesis. Pruned beams drop stacks. Memory linear in beam width. Same mask rule per beam.
When is regex enough?
Answer
Enums, short patterns, ISO dates if the backend actually enforces them. Nested JSON, matched parens, and SQL need a CFG. If you are about to write a recursive regex, you wanted a grammar.
Pitfalls
Draw the stack after each character of 2+ and of (2+3. Circle FIRST(Factor). Put a check only next to terminals in that set. Then write “JSON Schema is this, with keys as terminals.” That sequence covers most CFG probes.
Go Deeper
Docs and code:
YouTube:
Cluster: