II · THE IDEA · ARTIFICIAL INTELLIGENCE
Constrained and Structured Generation
▶ Listen · narrated
Asking a model to produce valid JSON works often enough to feel reliable, until the day it closes an array inside a string. Constrained generation makes the grammar a hard boundary, not a request.
At a glance
- What it is
- Masking logits so only tokens that keep the output grammatically valid can be sampled
- When it runs
- At inference time, after the model produces logits but before sampling
- What it needs
- A formal grammar — JSON schema, regex, or a context-free grammar
- Cost
- Parsing overhead per token; negligible compared to the forward pass itself
Imagine a multiple-choice test where some answers are crossed out before you see the paper. You still choose from what remains based on what you know, but certain mistakes are now impossible because those options are not on the page.
Constrained generation does this for a language model. The model produces a score for every token it knows — tens of thousands of options. Before it picks one, a separate program checks the grammar: given what has been written so far, which tokens would create a syntax error? Those tokens are crossed out. Their scores are set so low they can never be chosen. The model then picks from what is left, using its learned preferences. If the grammar says only a number can come next, every token that is not part of a number disappears from consideration. The output is guaranteed to follow the rules, because rule-breaking options are removed before the choice is made.
Constrained generation operates on the logits immediately before sampling. At each generation step, the model produces a vector of raw logits, one per vocabulary token. A parser maintains the current state of the output against a formal grammar — typically a JSON schema, a regular expression, or a context-free grammar in a notation like GBNF. The parser computes the set of tokens that could legally appear next without violating the grammar. All tokens outside this set have their logits replaced with negative infinity. The modified logit vector is then passed through softmax and sampled as usual.
The parser must be efficient because it runs once per token. For regular grammars this is straightforward: the parser is a finite automaton and the valid-token check is a state transition lookup. For context-free grammars the parser must track a stack and potentially explore multiple branches, but optimisations like state caching and precompiled finite-state acceptors keep the overhead low — usually under ten percent of the per-token latency.
The technique composes with other sampling parameters. Temperature, top-p, and top-k are applied after the mask, so they operate only on the valid tokens. Beam search and speculative decoding require special handling because they involve multiple candidate sequences, each of which may be in a different parser state. The grammar must be evaluated separately for each beam or speculative branch.
One subtlety: tokenisation boundaries matter. If a grammar requires the exact string "true" and the tokeniser represents it as a single token, the mask is trivial. If "true" is split into "tr" and "ue", the parser must allow both fragments in sequence and reject any other token after "tr". This interacts badly with tokenisers that fragment rare words unpredictably, and it is one reason why structured generation works better with byte-level or character-level tokenisers in some cases.
Look closer
The mask is recomputed at every token
The model produces a vector of logits — one score for every entry in the vocabulary. Before sampling, a parser walks the grammar and the partial output generated so far, then sets the logits of all invalid continuations to negative infinity. Only tokens that could appear next in a grammatically correct document survive. The model never sees this happen; from its perspective it simply never chooses an illegal token, because those options vanish before the sampling step.
The grammar can be more specific than JSON itself
A JSON schema does more than enforce brackets and commas. It can require that a particular key must be a string, another must be an integer between one and ten, and a third must be one of five enumerated values. The mask enforces all of it. If the schema says the next value must be a boolean, the only tokens with non-masked logits are those that could start "true" or "false". The model's preference among valid options still matters — it is not choosing randomly — but invalid ones are not on the table.
It works for formats the model has barely seen
Because the constraint is external, you can generate syntactically perfect output in a niche format even if that format appeared rarely or never in training. The model's logits will be poorly calibrated — it has weak opinions about what should come next — but the grammar ensures that whatever it does choose will parse. This is particularly useful for domain-specific languages, obscure data formats, or any structure where you cannot afford a single malformed character.
The story
A model generating text produces one token at a time. At each step it outputs a vector of logits, one real number for every token in the vocabulary, representing its learned preference for what should come next. Those logits are converted into probabilities, then a token is sampled. Normally every token is a candidate, and the model's training is the only thing steering it toward coherent output.
Constrained generation intervenes between the logits and the sampling. It maintains a parser that tracks the partial output generated so far and a formal grammar describing what constitutes valid structure. At each step, before sampling, it asks: given what we have written, which tokens could appear next without violating the grammar? Every token that would create a syntax error has its logit set to negative infinity. When those logits are converted to probabilities, the invalid tokens end up with probability zero. They cannot be sampled. The model is forced to choose only from the grammatically valid options.
The grammar can be as simple as a regular expression or as detailed as a full context-free grammar with recursion and lookahead. JSON schema is a common case: you specify not just that the output must be valid JSON, but exactly which keys must appear, what type each value must have, and which string values are permitted from an enumerated list. The parser enforces all of it. If the schema says a field called "priority" must be an integer between one and five, then once the model has generated the key and the colon, the only tokens with non-zero probability are those that could begin a numeral in that range.
The overhead is real but small. At each step the parser must determine the set of valid next tokens, which requires walking the grammar and sometimes looking ahead. For simple grammars this is fast. For complex ones with deep nesting or many alternatives it can add measurable latency per token, but the cost is still a small fraction of the forward pass through the model itself. The trade is almost always worth making when the alternative is a malformed response that breaks a downstream parser.
Some implementations cache parser states to avoid redundant work, and some precompute finite-state machines from the grammar so the valid-token check becomes a table lookup. The engineering varies, but the principle does not: the model proposes, the grammar disposes, and the output is guaranteed to parse.
Why it mattered then
Structured generation emerged as a solution to a specific problem in production systems: models that could produce plausible JSON ninety-nine times out of a hundred, but whose hundredth failure would crash a pipeline or corrupt a database. Prompt engineering — asking the model politely to follow a format — improved the odds but could never make them certainties. The model had learned patterns, not rules, and under distribution shift or in low-probability branches of a conversation it would occasionally produce a string where a number belonged, or close a bracket it never opened. The technique itself borrows from decades of work in formal language theory and parser construction. Context-free grammars have been used to define programming languages since the 1960s, and the idea of using a grammar to constrain a generator is not new. What changed was the application: instead of constraining a hand-written code generator or a template system, the grammar was applied to the output of a neural network whose behaviour could not be directly controlled. The parser became a guardrail, ensuring that statistical learning and formal syntax could coexist in the same pipeline.
Why it matters now
Structured generation has become a standard feature in inference servers and local model runtimes because the cost of unreliable output is often higher than the cost of the constraint itself. A chatbot that occasionally produces malformed JSON is an annoyance. An agent that writes function calls or database queries cannot afford a single syntax error, because the downstream system will reject the entire response and the interaction fails. It also enables a model to work in domains where its training was thin. If you need output in a niche format — a domain-specific configuration language, a particular flavour of XML with strict nesting rules, or a structured log format — you can provide the grammar and the model will produce syntactically valid output even if it has never seen that format before. The semantics may be weak, but the syntax will be correct, and that is often enough to make the output usable. The technique is also appearing in tool-use and agent frameworks, where a model must produce structured commands that will be executed by external systems. The grammar ensures that the command is at least parseable, which moves the failure mode from "syntax error" to "wrong command", a much easier problem to debug and recover from.
The surprising detail
One counterintuitive property is that constraining the model can sometimes improve the quality of the content, not just the syntax. When the grammar rules out a large portion of the vocabulary at each step, the model's probability mass is concentrated on fewer options, and it is forced to commit more decisively. This can reduce the meandering or hedging behaviour that sometimes appears in unconstrained generation, where the model spreads probability thinly across many near-synonyms. The constraint acts as a kind of focus, and the output can become more direct as a side effect of being more formal.
Remember this
Constrained generation makes syntax a hard requirement by masking invalid tokens before sampling, turning a statistical tendency into a guarantee.
Test yourself
A model is generating JSON with a schema that requires a field called "status" to be one of three strings: "pending", "approved", or "rejected". The model has just generated the key and the colon. Explain what happens to the logits, and why this does not mean the model is choosing randomly among the three options.
Every token that could not begin one of the three permitted strings has its logit set to negative infinity, so its probability becomes zero. Only tokens that could start "pending", "approved", or "rejected" survive — likely the tokens for the opening quote and possibly the first few letters if the tokeniser represents them as single units. The model is not choosing randomly: its original logits still determine the relative probabilities among the valid options. If its training makes it strongly prefer "approved" in this context, that preference is preserved. The constraint removes impossible choices but does not flatten the model's opinions about the possible ones.
Go deeper
- llama.cpp/grammars/README.md at master · ggml-org/llama.cpp · GitHub · github.com
- Structured Outputs - vLLM · docs.vllm.ai
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.