Constrained decoding: grammars and JSON schema so tool calls always parse

The most common agent failure I debug isn’t a wrong answer. It’s a right answer the harness can’t parse: a missing brace, a trailing comment, a field name the schema doesn’t know. Asking the model nicely reduces this. Constrained decoding makes it impossible.

The mechanism: mask the logits

At every step, the engine knows which tokens would keep the output valid under a grammar. It sets the logits of every other token to −∞ before sampling. The model still chooses, but only among tokens that can lead to valid output. Sampling, temperature and everything else in the sampling note run on the masked distribution.

Valid output is then guaranteed by construction, not by hoping.

Regular formats: a finite-state machine

If the format is regular, such as a date, an enum or a fixed-shape record, it compiles to a finite-state machine. The engine tracks the current state and allows only tokens whose characters lead to a valid next state.

Outlines (Willard and Louf, 2023) made this fast by precomputing, for every FSM state, which vocabulary tokens are allowed. Each step becomes a table lookup instead of a scan over the whole vocabulary.

Nested formats: you need a stack

JSON isn’t regular. Objects nest inside arrays inside objects to any depth, and matching brackets needs memory that a finite-state machine doesn’t have. Real JSON support needs a context-free grammar, executed as a pushdown automaton: a state machine plus a stack.

llama.cpp uses GBNF, its grammar format (--grammar, --grammar-file). It can also convert a JSON Schema into a grammar for you (--json-schema, or response_format on the server). The grammar is enforced token by token during generation.

The token-boundary problem

Grammars are written in characters. Models emit tokens, and a single token can span several grammar symbols: "},{" can be one token, and it closes a string and an object and opens another. The engine has to check each candidate token character by character against the automaton, from the current state, which is expensive with a vocabulary of 150K tokens.

Modern implementations split the work. Most tokens’ validity depends only on the current automaton state and can be precomputed. Only tokens whose validity depends on the stack contents are checked at runtime. XGrammar (Dong et al., 2024) is built around this split, and it’s why grammar-constrained decoding can now run at close to unconstrained speed.

Constraints can make reasoning worse

Forcing the format from the first token has a cost. Tam et al. (2024) found that strict format restrictions measurably degraded reasoning on several tasks, compared with letting the model answer freely and converting afterwards. A model forced to emit {"answer": before it has worked anything out has nowhere to think.

The pattern that works for agents:

1. Let the model reason in free text, or in a dedicated reasoning block.
2. Constrain only the tool call: a grammar or schema that applies when the model starts the call, once the reasoning is done.
3. Validate against the real schema anyway. A grammar guarantees syntax, not that "path" points at a file that exists.

What it fixes in practice

On my own agent benchmark, one of the three harness bugs that cost 52.5 points was bare-JSON extraction: the harness failed to extract the answer when a model replied with bare JSON (the amber-bench note has the story). Constrained tool calls remove that whole class of failure. The parser and the generator agree on the format, because the format is enforced by the same grammar both sides use.

Rules I use

1. Constrain tool calls, not thinking. Free reasoning first, a strict grammar for the call.
2. Generate grammars from the same schema your tools validate against, so there’s one source of truth.
3. Keep schemas shallow and closed. No additionalProperties, enums wherever the set is known. Every constraint the grammar carries is a mistake the model can’t make.
4. Still handle refusal and timeouts. A grammar can’t force the model to finish; set a token limit and a sensible error path.

Sources: Willard and Louf, Efficient Guided Generation for Large Language Models (2023). Dong et al., XGrammar (2024). Tam et al., Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models (2024). llama.cpp’s GBNF and JSON-schema documentation.