Guided Generation Math

The distribution you are actually sampling from

At each decoding step a transformer produces a logit vector z ∈ R^|V|, one score per vocabulary token, and turns it into a distribution p = softmax(z), so p_i = exp(z_i) / Σ_j exp(z_j). Sampling picks the next token from p, and nothing in this process knows you asked for JSON.

Prompt engineering shifts p so valid tokens carry most of the mass, but it never makes the invalid mass zero: there is always a nonzero chance the model emits a stray comma or a prose preamble, and one bad token can invalidate the whole output. Guided generation attacks the distribution directly. If we know the set of tokens A ⊆ V that are structurally legal at this step, we force p_i = 0 for every i ∉ A before sampling. The model still chooses among the legal tokens by its own preferences — we only delete the illegal branches of the tree.

Logit masking: the one operation everything is built on

Deleting tokens is done with a mask, not by renormalizing after the fact. Build a vector m ∈ R^|V| with m_i = 0 for allowed tokens and m_i = -∞ (in practice a large negative constant like -1e9) for disallowed ones, then sample from softmax(z + m).

z   = model_logits(context)      # [|V|]
m   = mask_for_state(state)      # 0 or -inf per token
p   = softmax(z + m)             # illegal -> exp(-inf) = 0
tok = sample(p)                  # guaranteed legal
state = step(state, tok)         # advance the FSM

Because exp(-∞) = 0, the softmax denominator drops the masked terms automatically and the survivors renormalize to sum to 1 — no separate normalization pass. The entire cost of the guarantee is one vector add plus whatever it takes to compute m; make that cheap and constrained decoding is nearly free. The rest of the subject is really the study of computing m fast.

Structure as a language, and a machine that recognizes it

The valid outputs of a constraint form a formal language, and formal-language theory hands us recognizers for such sets directly. A regular language (anything a regex describes: a phone number, an ISO date, a choice among fixed options) is recognized by a finite-state machine: a set of states Q, a start state, accepting states, and a transition function δ: Q × Σ → Q over an alphabet Σ.

The FSM is exactly the bookkeeping guided generation needs. At any moment the machine sits in some state q; the characters that keep it on a path to an accepting state are the only legal continuations, and anything else is a dead end. So the recipe is: keep the FSM in sync with what has been generated, and at each step allow only tokens whose characters are accepted from the current state. The subtlety — where the real engineering lives — is that the FSM's alphabet is characters, while the model emits multi-character tokens.

From regex to an FSM over the vocabulary

A regex compiles to a character-level FSM by the standard Thompson / subset construction, but masking needs the legal set over the token vocabulary, not over characters. The bridge, introduced by the Outlines approach, is to precompute for every FSM state which whole tokens are acceptable.

A token is a fixed string of characters, e.g. "true". It is valid from state q if feeding its characters one by one through δ, starting at q, never hits a dead state — and doing so also tells you the resulting state. So for each state we build a map:

index[q] = { token : q'  for each token whose chars
                        run q -> q' without dying }

With this index, decoding is trivial: the allowed set at state q is keys(index[q]), the mask follows from it, and after sampling token t the new state is index[q][t] — all the character-walking done ahead of time.

The near-zero-overhead index

The payoff of precomputation is that the per-token cost at inference collapses to a dictionary lookup and a scatter of the mask — O(|A_q|) in the number of allowed tokens, independent of how complex the regex is. Building the index is a one-time cost paid when the schema is compiled, not per request and not per token.

Constructing it naively looks like |Q| × |V| token-walks, which for a 128k vocabulary is not free, but it is done once and cached, and it is heavily prunable: most tokens are invalid from most states and can be skipped by walking the vocabulary as a trie against the FSM. The result is that a hard structural guarantee adds essentially no latency per token — the mask is looked up, not computed — which is what makes guided generation practical in production, and especially attractive when the model itself is slow.

A worked example: a boolean JSON field

Say the required output is {"ok": <bool>}, with a tiny vocabulary { '{"ok": ', 'true', 'false', 'yes', '}' }. The regex \{"ok": (true|false)\} compiles to a short FSM. At the start state q0 only the opener token is valid, so the mask kills everything else and the model must emit {"ok": , moving to q1.

From q1 the FSM accepts only t or f as next characters, so the index marks true and false valid but yes invalid — even if the model's raw logits ranked yes highest, its probability is forced to 0 and it picks the better legal option. After that, the only path to acceptance is }. At no step could a malformed string escape; validity is a structural guarantee.

Beyond regex: grammar-constrained decoding

Regular languages cannot count or match nested brackets — a finite-state machine has no memory of how deep it is. Arbitrarily nested JSON, balanced parentheses, or a programming-language syntax are context-free, described by a grammar (a set of production rules) and recognized by a pushdown automaton: an FSM plus a stack.

The masking idea carries over unchanged; only the state is richer. The parser tracks a configuration (roughly, the stack of partially completed rules) and enumerates the terminals that could legally come next — a set turned into a token mask exactly as before, recomputed cheaply after each token. This is what libraries such as guidance, llguidance and XGrammar do to enforce full grammars at speed: the stack supplies the unbounded memory that nesting requires, which a plain FSM lacks.

JSON Schema is just a compilation target

Most practical guided generation is phrased as ‘match this JSON Schema (or this Pydantic model)’ — a convenience layer, not a new mechanism. A schema is mechanically lowered into a regex or grammar: a patterned string field becomes that regex; an enum becomes an alternation (A|B|C); an integer becomes -?[0-9]+; an object becomes the concatenation of its quoted keys, colons, field-value sub-patterns and separating commas, wrapped in braces. Once lowered, everything reduces to the automata already described — and because the pattern fixes key order and required fields, the model is never allowed to omit a required key in the first place. The compiler, not the prompt, carries the contract.