Structured and Constrained Generation

Ask a model to return JSON and there's a good chance you'll get back something like "Sure! Here is the JSON you requested:\n\n```json\n{...}. The actual JSON is in there somewhere, buried under pleasantries and markdown formatting that no parser will accept. The usual fix is a regex to fish it out, which works until the model rephrases its preamble.

The model was trained on text where humans write things like "Here is the JSON:" before pasting a code block. That's what natural language looks like. When you need machine-readable output, natural language is the problem.

So how do you force a language model to produce syntactically valid structured output, every single time, without relying on post-hoc parsing or retry loops?

You reach into the decoding process itself and constrain it at the source.

Prerequisites

This post builds on sampling strategies (Post 5.5), where we covered how logits become token probabilities via softmax, and how temperature, top-k, and top-p shape the distribution before sampling. You'll also want familiarity with BPE tokenization (Post 3.1), since the mismatch between character-level grammars and token-level vocabularies is a core engineering challenge here.

The mechanism: logit masking

Back in Post 5.5, we looked at how sampling works. The model produces logits, we apply temperature and top-p or top-k, then we sample from the resulting distribution. Structured generation adds one more step before all of that: mask out every token that would break the grammar.

The idea is almost too simple. At each decode step, you have a grammar (or schema, or regex) that defines which tokens are legal continuations of the output so far. You look at the model's logit vector, find every token that isn't a valid continuation, and set its logit to $-\infty$. After softmax, those tokens get probability zero. The model literally cannot pick them.

You don't retrain the model. You don't fine-tune anything. You just intercept the logits at each step, mask the invalid ones, and let the model sample from what remains. The output is guaranteed to conform to your grammar.

If you've been following along, this should feel familiar. The mechanism is the same one we saw in the causal mask from Post 4.3, just applied to a different dimension. There, we masked future positions so the model couldn't attend to tokens it hasn't seen yet. Here, we mask vocabulary entries so the model can't emit tokens that would violate the grammar. Same idea, different axis.

But how do you know which tokens are valid at each step? You need something that tracks the current parse state and tells you what can legally come next. That something is a finite-state machine.

Compiling grammars into FSMs

The key insight from Willard and Louf's 2023 paper on Outlines is that you can compile a regular expression (or a context-free grammar) into a finite-state machine, and then use that FSM to drive the masking at each decode step.

The easiest way to see this is with JSON. Imagine you want the model to produce a simple JSON object like {"name": "Alice", "age": 30}. The grammar for this can be expressed as a state machine with states like START, OPEN_BRACE, KEY, COLON, VALUE, COMMA_OR_CLOSE, and DONE. Each state has transitions labeled with the characters (or tokens) that are valid from that state.

At the START state, the only valid token is {. After the opening brace, the only valid token is " (to begin a key). After a key string and its closing quote, the only valid token is :. And so on. At each step, the FSM tells you exactly which tokens are allowed.

The visualization shows the two halves of the process working together. On the left, the FSM tracks parse state, collapsing the detailed states into a simplified cycle: open brace, key, colon, value, comma, and back around. On the right, the model's token probabilities are filtered. Valid tokens (blue) are the ones the FSM allows, and everything else (gray, strikethrough) gets its logit set to $-\infty$ before sampling.

And notice something about the probability bars. When only one token is valid (like { at the START state), the model has no choice. It gets 100% of the probability mass. But when multiple tokens are valid (like choosing "Alice" vs "Bob" vs "John" for the name value), the model's own learned preferences determine the output. The grammar constrains the syntax. The model fills in the semantics.

The token-level complication

There's a real engineering challenge here that comes from the mismatch between character-level grammars and token-level vocabularies.

When I said "the only valid token is {", that was a simplification. The tokenizer might represent { as a single token, or it might be part of a larger token like {" or {\n. A BPE tokenizer (which we covered in Post 3.1) can produce all kinds of multi-character tokens, and the FSM needs to handle all of them.

Outlines solves this by precomputing a mapping from each FSM state to the set of valid token IDs. For every state in the FSM and every token in the vocabulary, you check: "If I appended this token's characters to the current output, would the FSM accept them?" This precomputation is expensive (you're checking every token in a vocabulary of 32K-128K against every FSM state), but you only do it once per grammar. After that, each decode step is just an index lookup.

def compute_token_mask(fsm_state, token_to_chars, fsm):
    """
    For a given FSM state, find all vocabulary tokens
    that produce valid transitions.
    """
    valid_token_ids = []
    for token_id, chars in token_to_chars.items():
        state = fsm_state
        valid = True
        for ch in chars:
            next_state = fsm.transition(state, ch)
            if next_state is None:  # no valid transition
                valid = False
                break
            state = next_state
        if valid:
            valid_token_ids.append(token_id)
    return valid_token_ids
 
# Precompute for every (state, token) pair at load time.
# At decode time, just look up: mask = precomputed[current_state]

Zheng et al. took this further in SGLang with a technique called "jump-forward decoding." If the current FSM state has only one possible next character (like the colon after a key), you can skip the model entirely and just emit that character. This turns long sequences of deterministic transitions into a single operation. For highly constrained schemas, this can significantly speed up generation.

JSON Schema: the practical sweet spot

Raw JSON is one thing, but the real power is constraining output to match a specific JSON Schema. You don't just want valid JSON. You want an object with a name field that's a string and an age field that's an integer.

The approach is the same, but the FSM gets more complex. Instead of a generic JSON grammar, you compile a schema-specific FSM that encodes the allowed keys, value types, enum constraints, and nesting structure. The state machine for a schema with two required fields is straightforward. A schema with optional fields, arrays of objects, and recursive types produces a much larger FSM, but the decoding mechanism is identical: at each step, mask the invalid tokens, sample from the valid ones.

This is what OpenAI's "Structured Outputs" mode and Anthropic's tool use do under the hood (or something very close to it). When you pass a JSON schema to the API and the model returns a perfectly conforming object, the decoding engine is masking logits at every step to enforce it.

Worked example

Let me walk through the first few steps explicitly, so you can see exactly what happens at each decode step.

Step 1: State = START. The FSM says the only valid transition is {. The model's logit vector has 128,000 entries. We scan the precomputed mask for the START state and find that maybe 3 or 4 token IDs correspond to tokens that start with { (like {, {", {\n). Everything else gets logit $= -\infty$. After softmax, those few tokens share 100% of the probability. The model picks {. FSM advances to OPEN_BRACE.

Step 2: State = OPEN_BRACE. Valid transitions: " (to begin a key). Same process: mask everything that doesn't start a JSON string at this position. The model picks ". FSM advances to KEY.

Step 3: State = KEY. Now it gets interesting. Any string content is a valid key. The model's actual preferences matter here, because many tokens are valid. If the schema specifies required keys (like "name"), the schema-aware FSM can restrict valid tokens to only those that begin the string name. Without schema constraints, any string token is fair game. The model picks name based on its learned distribution. FSM advances.

Steps 4-5: State = COLON, VALUE. After closing the key quote, the only valid transition is :. Then the FSM checks the schema: the value type for "name" is string, so only tokens that start a string literal are valid. The model emits ", enters the string, and now has freedom again to choose the value content. It picks "Alice" because that's what its distribution favors.

Steps 6-8: COMMA, second key-value pair. After closing the value string, the schema says there's a required "age" field, so the FSM forces a comma (not }). The second key-value pair plays out the same way, except the value type is integer, so string tokens are masked and only number tokens are valid.

The pattern repeats. At each step, the FSM narrows the valid set, the model picks from what remains, and the output builds up token by token. By the time you reach the closing }, every character in the output was validated at generation time. There's no need to parse the result and check for errors, because errors were structurally impossible.

Notice how the model's freedom varies step by step. Some steps are completely determined (the colon after a key, the closing brace at the end). Other steps give the model wide latitude (choosing a name string, choosing a number). The grammar doesn't eliminate the model's intelligence. It channels it.

Beyond JSON: regex and CFGs

JSON Schema covers a huge fraction of practical use cases, but grammar-guided decoding is more general than JSON. Outlines supports arbitrary regular expressions, and tools like Guidance from Microsoft and LMQL support context-free grammars.

A regular expression compiles directly into a deterministic finite automaton (DFA). Context-free grammars need a pushdown automaton, which adds a stack to track nesting depth. The stack is what lets you handle recursive structures like nested JSON objects or balanced parentheses. The masking logic is the same either way: at each step, query the automaton for the set of valid transitions, map them to token IDs, mask everything else.

LMQL takes a different approach entirely. Instead of compiling a grammar into an FSM, it lets you write Python-like constraints that get evaluated during generation. You can express things like "this variable should be one of these five values" or "this number should be between 0 and 100." It's more flexible than pure grammar-guided decoding, but the constraint checking has to happen at each decode step, which can add overhead.

Microsoft's Guidance library takes yet another path: it interleaves generated text with fixed template text, so you write something like a format string where some parts are filled by the model and other parts are fixed. The generation and constraint enforcement happen in the same pass. It's a nice mental model, closer to how most developers think about structured output than raw FSMs.

Each of these tools makes different tradeoffs between expressiveness and performance. Pure FSM-based approaches (Outlines, SGLang) are fast but limited to regular and context-free grammars. Constraint-based approaches (LMQL) are more flexible but do more work at each decode step. Template-based approaches (Guidance) are easiest to reason about but less composable. In practice, most production systems use FSM-based JSON Schema decoding, because that covers the use case that matters most: getting valid, schema-conforming JSON out of a model.

The performance question

You'd think constrained decoding would be slower, since you're adding computation at every step. And it can be, but the story is more nuanced than that.

The mask computation itself is fast after precomputation, basically an array lookup. The interesting effect is what the constraints do to the model's behavior. When you mask out invalid tokens, you're concentrating probability mass onto valid ones. This can actually speed up convergence to meaningful content because the model isn't wasting tokens on syntactic filler. A model that would have generated "Sure, here is a JSON object:\n\n```json\n{"name"... instead jumps straight to {"name"... because "Sure" got masked at step one.

There's also a neat trick hiding in the structure of the FSM itself. A lot of JSON steps have exactly one legal next token: the colon after a key, the closing quote after a value, the closing brace at the end. For those steps, there's no decision for the model to make, so why are we calling it? SGLang's "jump-forward decoding" skips the forward pass entirely on deterministic runs and just emits the forced tokens directly, resuming model calls only when the FSM offers real choices.

But very tight constraints can also hurt quality. If your schema demands a specific enum value and the model's distribution is spread across tokens that would express a different (but semantically correct) answer, the grammar forces it down one path. The model might produce technically valid but semantically odd output because you've pushed it into a region of the distribution it wasn't naturally heading toward.

Here's a concrete example. Say your schema requires an age field with type integer. The model might naturally want to write "twenty-five" in this context (it's generating a character bio), but the grammar forces it to emit 25. That's fine, probably what you wanted. But now say the schema requires a status field with enum ["active", "inactive"] and the model's learned distribution wants to say "pending". It gets shunted to whichever of the two allowed values has higher probability. The output is valid but the model is no longer expressing what it "thinks."

This matters less for data extraction (where you really do want exact conformance) and more for tasks where the model needs room to express nuance. The constraints should match the structure of the task. Tight constraints for structured data, loose or no constraints for free-form text.

When constraints help vs. hurt

Good use cases for constrained generation:

• Data extraction: pull structured fields from unstructured text. The model reads a resume and emits {"name": "...", "email": "...", "skills": [...]}.
• API responses: every response matches the schema the client expects. No parsing failures, no retry logic.
• Tool calls: when a model decides to call a function, it needs to emit arguments that match the function's signature. Grammar-guided decoding guarantees the arguments parse correctly. This is the big one.
• Code generation: constraining output to valid syntax for a specific language.

Bad use cases:

• Creative writing: forcing prose into a grammar destroys fluency. The model needs to flow freely.
• Open-ended Q&A: if the answer is naturally unstructured, imposing structure adds overhead without benefit.
• Cases where partial validity is fine: sometimes a best-effort JSON blob that you can fix up with a post-processing step is better than a perfectly constrained one that says something weird because the constraints fought the model's distribution.

Function calling as constrained generation

Here's where this whole arc has been heading. When you use function calling (or tool use) in a modern LLM API, what's happening under the hood is structured generation. The model decides it wants to call a tool, and then it needs to emit a JSON object with the function name and arguments. That JSON has to be valid and conform to the function's parameter schema.

This is grammar-guided decoding applied to one of the most consequential problems in the LLM stack: getting models to reliably interact with external systems. The provider compiles the function's parameter schema into an FSM. The model's logits get masked at each step to ensure the emitted JSON conforms to the tool's signature. The output always parses, which means no retry loops and no "I'm sorry, I can't produce valid JSON" failures to paper over in application code.

Before grammar-guided decoding, function calling relied on prompt engineering and post-hoc validation. You'd tell the model "respond in JSON" and validate after the fact. If the model hallucinated a closing bracket or forgot a comma, your tool executor would crash. The shift from hope-based to guarantee-based function calling is one of the most important infrastructure changes in the LLM stack between 2023 and 2025.

We'll go deep on the mechanics of function calling in Post 10.2, but the core mechanism is what you've been looking at in this post. The FSM constrains the syntax. The model fills in the content.

Common misconceptions

"JSON mode means the model understands JSON." It doesn't. The grammar engine forces syntactic validity regardless of what the model would have done on its own. A model that has never seen JSON in training could still produce valid JSON if you mask the right tokens. The model's contribution is choosing which valid tokens to emit (the content), not whether the output is well-formed (that's guaranteed by the mask).

"Constraints always improve output." Too-tight constraints can fight the model's distribution and produce awkward or semantically wrong text. If the model wants to say one thing and the grammar only allows something else, you get technically valid output that doesn't reflect the model's actual prediction. Constraints help when the task's structure matches the grammar. They hurt when you're forcing structure onto something that's naturally unstructured.

"This is the same as post-processing." No. Logit masking happens before sampling, guaranteeing validity at every step. Post-processing catches errors after the fact, which means you've already spent compute generating tokens that might be wrong. Post-processing can fail (what if the JSON is malformed in a way your fixer can't handle?). Grammar-guided decoding can't produce invalid output. The guarantee is structural, not heuristic.

What's next

Arc 6 opens with what an inference engine actually does, connecting everything we've built in Arc 5 to the shape of a production serving stack: batching, KV caches, paged attention, and the systems-level tricks that make all of this fast enough to use.

Additional reading (and watching)

• Willard, B. T. & Louf, R. (2023). Efficient Guided Generation for Large Language Models. arXiv:2307.09702.

• Beurer-Kellner, L., Fischer, M., & Vechev, M. (2023). Prompting Is Programming: A Query Language for Large Language Models. PLDI 2023.

• Zheng, L., et al. (2024). SGLang: Efficient Execution of Structured Language Model Programs. arXiv:2312.07104.

• Microsoft. Guidance: A guidance language for controlling large language models. GitHub.

• OpenAI. (2024). Structured Outputs in the API. Blog post.