The cover of “Compilers: Principles, Techniques, and Tools” (Aho, Sethi, Ullman, 1986) shows a knight fighting a dragon. Every piece is labeled: the dragon is “Complexity of Compiler Design”, the lance is “LALR parser generator”, the shield is “Syntax Directed Translation”, the horse is “Data Flow Analysis”. Generations of engineers know it simply as the Dragon Book, and Aho and Ullman received the 2020 Turing Award for the work it teaches.

I want to show you that in 2026 the dragon changed its name. It is now called free-form LLM output, and the weapons that slay it are the same ones from that cover: regular expressions compiled to automata, and grammars. This is not a metaphor. Every reliable tool call your agent makes runs through a finite-state machine, and the numbers below come from my own machine, a local Qwen served by llama.cpp, no API key involved.

Step 1: the dragon, measured

Ask a small local model for JSON and it will mostly comply, in the way a cat mostly stays off the kitchen counter. Three runs from the experiment below, all real outputs from Qwen2.5-1.5B-Instruct:

```json
{ "category": "billing", ... }
```                                     <- markdown fence around perfect JSON
Sure! Here is the JSON: {"tool": ...}   <- chatter before perfect JSON
{"tool": "set_reminder", ...}           <- a tool that does not exist

The first two break json.loads even though the payload is fine. The third parses beautifully and then crashes your dispatcher, because the model invented a tool name outside your catalog. Across 80 free-form runs in this experiment (two models, two temperatures), 25 outputs, that is 31 percent, would have failed a strict parser.

Step 2: the lance: regex to automaton

Constrained decoding attacks this at the only place it can be fully won: the sampling step. Recall how generation works: at each position the model produces logits over the whole vocabulary, and a sampler picks one token. Constrained decoding inserts an automaton between the two.

Before generating, your output contract is compiled into a finite-state machine, exactly like a compiler compiles a regex (Dragon Book, chapter 3). During generation the automaton sits in some state, and that state defines which tokens are legal next. Illegal tokens get their logit set to negative infinity, their probability becomes zero after the softmax, and the model literally cannot choose them. The chosen token advances the automaton one state, and the loop repeats.

Two consequences that confused me until I traced them:

• Nothing is ever repaired. An invalid output is not detected and fixed; it is prevented from existing. The token that would break the JSON never gets sampled.
• Incomplete output is impossible too, because the end-of-sequence token is just another token to mask. While the automaton is not in an accepting state, EOS is illegal, so the model cannot stop with a half-open brace.

The contract can be written directly as a grammar. This is the actual GBNF file from the experiment for the tool-call task, the whole thing:

root   ::= "{" ws "\"tool\"" ws ":" ws tool ws "," ws "\"argument\"" ws ":" ws string ws "}"
tool   ::= "\"create_reminder\"" | "\"send_email\"" | "\"search_web\"" | "\"none\""
string ::= "\"" char* "\""
char   ::= [^"\\\x00-\x1f] | "\\" (["\\/bfnrt] | "u" [0-9a-fA-F]{4})
ws     ::= [ \t\n]?

Look at the tool rule: the enum of valid tools is part of the grammar, so set_reminder is not a bug you catch later, it is a sequence of tokens that cannot be emitted. In practice you rarely write GBNF by hand; llama.cpp accepts a JSON Schema through the standard response_format field and compiles it to a grammar for you. vLLM and Ollama do the equivalent. The overhead is microseconds per token against tens of milliseconds of inference.

Step 3: the experiment

Ten real-world cases across three tasks, each with known ground truth so correctness is verified, not eyeballed: receipt extraction (a Colombian supermarket receipt, an AWS invoice, a Rappi delivery summary), agent tool dispatch (four user messages, including one that needs no tool), and support-ticket triage. Four of the ten inputs are in Spanish, because local models break format more often outside English.

Every case runs in two modes against the same server: free (the prompt asks for JSON and we trust the model) and grammar (same prompt, plus the schema as response_format, which llama.cpp compiles to GBNF). Each output is checked at three levels, strictest last: parse (does json.loads accept it), schema (required keys, types, enums, no extras), semantic (do the values match ground truth). The free mode also gets a lenient fallback that extracts the first {...} block, which is the repair heuristic every production pipeline ends up writing.

Models: Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct, q4_k_m, llama.cpp. Three samples per case at temperature 0.8 plus one deterministic pass at temperature 0.

Step 4: results

Read the first row: one output in three from free mode would kill a strict parser, and every one of those failures was formatting noise around correct content, markdown fences and helpful chatter. The lenient regex rescues them all here, which is the honest caveat: on short tasks like these, a good small model plus repair heuristics reaches the same schema validity. But that regex is doing real work in every run, it is a hand-rolled grammar you maintain in your parser instead of a declared one the sampler enforces, and it has nothing to say about enums or types. The grammar column needs no repair code at all: 100 percent strict validity is not a measurement, it is a property of the construction.

The semantic row is the anti-hype row: 76 against 74 is sampling noise (at temperature 0 both modes tie exactly, 19/20 each). Constraining the output neither helped nor hurt the model’s understanding on tasks this size.

Step 5: what the automaton cannot do

The Rappi receipt says “Total pagado: $62.400 (pesos colombianos)”. Qwen2.5-1.5B extracted "total": 62.4 in seven of its eight runs on that case, including every grammar-constrained run and the deterministic pass. The grammar was satisfied: a number is a number. The value is wrong by three orders of magnitude, because the model read the Colombian thousands separator as a decimal point. The 7B model got it right in all eight of its runs.

That is the boundary, stated by my own data: the automaton guarantees form, never truth. It cannot know that 62.4 pesos does not buy lunch in Medellín. Semantic validation stays your job downstream, which is exactly where typed claims with provenance earn their keep, the subject of my previous post.

The takeaway

If you run local models, constrained decoding is the closest thing to free reliability you will find: the retry-on-parse-failure loop disappears, enum hallucinations disappear, truncated JSON disappears, and on these tasks it cost nothing in answer quality. It is also what makes a 1.5B model usable for tool calls at all. Just keep the boundary in sight, since a grammar-perfect wrapper can still carry a wrong value.

Everything is reproducible with no API key, one Python file plus its test suite (18 tests, including the live one) in my dojo repo:

brew install llama.cpp
llama-server -m qwen2.5-1.5b-instruct-q4_k_m.gguf -c 4096 --port 8081

cd dojo/agents/constrained-decoding
python3 test.py -v          # validators + a live grammar check
python3 experiment.py       # free vs grammar, 3 samples, temp 0.8
python3 experiment.py --temp 0 --samples 1

The dragon changed its name, and the sixty-year-old weapons still work.

References: Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools (the Dragon Book); llama.cpp GBNF grammars; Geng et al., Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning; ACM Turing Award 2020, Aho and Ullman.