From Schema to Mask: The Automaton Index

Start with the simplest useful class of formats: those describable by a regular expression. Phone numbers, dates, identifiers, enumerations, numeric literals, and a surprising share of the fields inside a JSON schema.

Every regular expression can be converted mechanically into a finite state machine. The construction is standard: the expression becomes a nondeterministic automaton, which is then converted to a deterministic one by the subset construction, and optionally minimised.

A deterministic finite automaton has a set of states, one start state, a set of accepting states, and a transition function taking a state and a character to exactly one next state.

The property that matters for us is determinism. From a given state, reading a given character leads to exactly one place. There is no search, no backtracking, and no ambiguity about where you are.

That is what turns validation into something cheap. The automaton's current state is a complete summary of everything the prefix so far implies about what may come next.

This is the observation the whole technique rests on, and it is worth stating carefully because everything else is an implementation of it.

Two different strings that lead the automaton to the same state are, from that point onward, completely interchangeable. Whatever completions are valid after one are valid after the other. The history is irrelevant; only the state matters.

So the question which tokens may be generated next does not actually depend on the text generated so far. It depends only on which state that text landed in.

That converts an expensive per-step question into a cheap per-state one. Instead of asking, at every generation step, which of 128,000 tokens keeps this particular string valid, you ask once per state which of 128,000 tokens are legal from that state, and record the answer.

The number of states is a property of the format, not of the traffic. A schema might compile to a few hundred or a few thousand states. Whether you serve ten requests or ten million, the work of answering the question is done that many times, once.

The construction, from Willard and Louf's work on guided generation, is direct once the insight is in place.

For each state of the automaton, walk the entire vocabulary. For each token, feed its characters through the automaton starting from that state. If every character has a defined transition and the token does not lead into a dead state, the token is permissible, and you record both that fact and the state it lands in.

The result is a map from state to a set of allowed tokens, together with the resulting state for each. That map is the index.

At generation time the work collapses. You hold the current state, look up its entry, and apply the stored mask. When a token is sampled, you read off the next state from the same entry. No string manipulation, no parsing, no scanning of the vocabulary.

The 64 million validity checks per response from the previous lesson become 500 dictionary lookups.

The cost has not vanished; it has moved. It is now paid once, when the schema is compiled, rather than repeatedly at every generation step.

The pipeline splits cleanly into a compile phase and a serve phase, and knowing which side a cost lands on answers most performance questions about this technique.

Compile time runs once per schema. The JSON Schema or regex is converted into an automaton, the automaton is determinised, and then the vocabulary is walked for every state to build the index. This is the expensive part, and it is proportional to the number of states times the vocabulary size.

Serve time runs once per generated token. Look up the current state, apply the stored mask to the logits, sample, and follow the stored transition to the next state. Constant work, independent of both schema complexity and output length.

The practical consequence is a caching question rather than an algorithmic one. If your service uses a fixed set of schemas, compile them at startup and the per-request cost is nil. If callers supply arbitrary schemas at request time, the compile lands on the first request that uses one, so you want a compiled-grammar cache keyed by schema hash, and you should expect a slow first call.

JSON Schema is not a regular expression, so a translation step sits in front of the machinery.

The conversion is largely mechanical for the common subset. A string type with a pattern becomes that pattern. A string without one becomes the regex for a JSON string literal, including escape handling. An integer becomes an optional minus sign followed by digits. An enum becomes an alternation of its literal values.

An object becomes the concatenation of an opening brace, its properties in a fixed order, each as a quoted key, a colon, the recursively translated value regex, separated by commas, and a closing brace.

Optional properties turn each into an alternation between present and absent, which is where the state count grows quickly: n optional fields can produce combinatorially many orderings unless the implementation pins an order.

That detail explains a behaviour people notice. Constrained generation usually emits fields in schema order rather than in whatever order the model would prefer, because pinning the order keeps the automaton small.

And it explains why deeply nested or highly optional schemas compile slowly: the state count, not the text length, is what grows.

The index trades memory for speed, and it is worth knowing the shape of that trade before enabling it on a large schema.

The natural representation is one bitmask per state over the vocabulary. With 128,000 tokens that is 16 kilobytes per state. A thousand-state automaton therefore needs about 16 megabytes of masks, which is unremarkable next to model weights.

A pathological schema with a hundred thousand states would need 1.6 gigabytes, which is not.

Two properties keep this manageable in practice. Masks are extremely sparse in one direction or the other: in most states only a handful of tokens are legal, and inside a free-text string almost all are. Both extremes compress well, so implementations store token lists for restrictive states and complements for permissive ones.

And many states share identical masks. Every position inside an unconstrained string field permits the same set, so deduplicating masks by content collapses long runs of states onto one stored mask.

The number to watch when a schema behaves badly is state count, and the usual cause is optional fields or unbounded repetition rather than schema size on the page.

There is a mismatch at the heart of this that the index construction quietly handles, and that has to be understood to reason about the failures.

The automaton is defined over characters. The model emits tokens, which are multi-character pieces chosen by a tokenizer for compression rather than for any structural reason. A single token can contain a quote, a colon and the start of a word.

The index construction accommodates this by feeding each token's whole character sequence through the automaton. A token is permissible only if every one of its characters has a valid transition, and the recorded next state is where the last character lands.

The consequence is that a token straddling a structural boundary is fine, provided the whole crossing is legal. What is excluded is a token whose first half is legal and whose second half is not.

This is why the set of permissible tokens is often much smaller than intuition suggests. At a point where the grammar requires a closing brace, only tokens that begin with a closing brace and continue legally survive, and a tokenizer optimised for English prose has few of those.

The deeper version of that mismatch causes a subtle quality problem worth recognising, because it is invisible in output that parses perfectly.

A given string usually has many possible tokenizations. The tokenizer, applied to complete text, produces one canonical segmentation, generally the one using the fewest, longest pieces. That canonical form is what the model saw throughout training.

Constrained decoding does not necessarily reproduce it. The mask permits any token that keeps the string valid, and sampling may pick a shorter piece where the canonical tokenization would have used a longer one. The resulting text is identical; the token sequence is not.

The model is then conditioning on a token sequence with a shape it rarely encountered in training. The text looks right, and the internal representation is slightly off-distribution.

Related is the token healing problem: when a prompt ends mid-word, the final prompt token may be a fragment the model would never have produced there, and continuing from it degrades quality. Implementations handle this by backing up over the last token and re-generating it under a constraint that it match the fragment.

Both are reasons to prefer a well-tested implementation over rolling your own.

Finite automata recognise exactly the regular languages, and that is a real ceiling rather than an implementation limit.

A finite automaton has finitely many states and no memory beyond which state it is in. That makes it incapable of counting without bound.

JSON needs unbounded counting. An object may contain an array containing an object containing an array, to any depth, and every opening brace must eventually be matched by a closing brace. To validate that, you must remember how many are currently open, and a machine with a fixed number of states cannot remember an arbitrary number.

So JSON in full generality is not a regular language, and no finite automaton recognises it.

The practical escape is that a concrete schema usually is regular. If the schema fixes the nesting depth, and most do, the depth is bounded and a finite automaton suffices. That is why the index approach works so well for typical structured output.

It stops working when the format is genuinely recursive: arbitrary JSON, a programming language, a query dialect with nested expressions. For those you need a machine with a stack.

Three symptoms come up repeatedly with index-based constrained decoding, and each maps to a specific cause.

The first request is slow and subsequent ones are fast. That is compilation, and it is expected. Cache compiled grammars by schema hash, and pre-warm the schemas you know about at startup.

Compilation is slow or memory use is high for a schema that looks small. Look at state count rather than schema length. Optional fields, unbounded repetition and deep nesting are the usual causes. Pinning field order and bounding array lengths often reduces the automaton dramatically.

Output parses but quality dropped. This is the interesting one, and it is rarely the index's fault. Check whether the schema forces the model into fields it cannot fill, whether it is being made to answer before reasoning, and whether the field ordering matches how the model would naturally derive the answer.

That third category is not an engineering problem at all, which is why the last lesson of this path is about it rather than about automata.