Structured and Constrained Generation

A response that begins with prose or a Markdown code fence is not a raw JSON document, even if it contains a valid JSON object. Extracting the object afterward requires deciding which surrounding text to discard.

A JSON parser needs the object without that surrounding prose. Constrained decoding restricts which tokens can be sampled, so a completed response follows a supported grammar.

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.

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.

Masking works with the existing model: intercept the logits at each step, mask the invalid ones, and sample from what remains. A completed output can be guaranteed to conform to the supported grammar. A length limit, refusal, unsupported schema, or execution failure still needs explicit handling. Syntax validity does not establish factual correctness.

The causal mask sets attention scores for future positions to $-\infty$. Here the same operation applies to vocabulary logits, excluding tokens that would violate the grammar.

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. For a regular language that can be a finite-state machine; recursive nesting requires richer parser state, such as a stack.

From a grammar to a mask

Regular expressions without nonregular extensions such as backreferences can be compiled into finite-state automata. General context-free grammars cannot: unbounded nested objects or balanced parentheses need a stack or an equivalent parser mechanism. A fixed, nonrecursive JSON shape is a useful small example, but it is not a model of every JSON Schema.

The widget below deliberately uses a tiny token vocabulary and a fixed format. It accepts exactly one object with a name chosen from Alice or Bob and an age chosen from 25 or 30, in that order and without optional whitespace. Those restrictions define the toy language; they are not rules of JSON itself.

(empty prefix)

At each state, the parser determines which candidate chunks keep the output on a valid path. If only one candidate survives, it gets probability one. If several survive, their relative weights are preserved. A mask restricts the choices; it does not supply evidence that Alice is the right name or 30 the right age.

The token-level complication

In the toy vocabulary above, the opening chunk is {"name":, spanning several characters and parser transitions. Real vocabularies are more complicated. 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 matcher must handle the complete decoded bytes, including tokens that cross parser-state boundaries.

For regular-language constraints, Outlines describes precomputing valid token transitions for automaton states. 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. This can make later matching cheap. General grammar backends combine precomputation with runtime parser state; not every supported schema reduces to a fixed table.

def compute_token_mask(fsm_state, token_to_chars, fsm, eos_id):
    """
    For a given FSM state, find all vocabulary tokens
    that remain prefixes of some accepted string.
    fsm.can_finish(state) tests reachability of an accepting state.
    Ordinary tokens decode to nonempty text; EOS is handled separately.
    """
    valid_token_ids = []
    for token_id, chars in token_to_chars.items():
        if token_id == eos_id:
            if fsm.is_accepting(fsm_state):
                valid_token_ids.append(token_id)
            continue
        if not chars:
            continue
        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 and fsm.can_finish(state):
            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]

JSON Schema: the practical sweet spot

JSON Schema specifies the structure of the output: for example, an object with a string name field and an integer age field.

A schema-aware matcher tracks required fields, allowed value types, enums, and the supported nesting rules. Implementations support different subsets of JSON Schema, so check the backend's contract.

OpenAI Structured Outputs and Anthropic strict tool use offer schema enforcement on supported schemas. Ordinary tool use and JSON mode are separate contracts; passing a tool definition does not by itself establish strict decoding.

Worked example

For the restricted language in the first widget, the prefix {"name": is fixed. The next chunk can be "Alice" or "Bob". After that, ,"age": is fixed and the value can be 25 or 30, followed by }.

A general string schema would allow many more names and lengths; it would not force a closing quote immediately after the displayed word. Optional whitespace and key ordering can also create multiple valid continuations.

Beyond JSON: regex and CFGs

Grammar-guided decoding also supports formats other than JSON. Libraries such as Outlines and Guidance support regular-language and grammar-based constraints, while LMQL also provides program-level constraints. Supported syntax and semantics depend on the backend.

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 supports Python-like constraints on generated variables, such as membership in a fixed set. It evaluates constraints during generation to restrict continuations; the supported operations and checking cost depend on the constraint.

Microsoft’s Guidance library interleaves generated text with fixed template text. Templates can combine model-generated values with constrained choices and grammar rules.

These tools combine mechanisms rather than falling into mutually exclusive categories. Compare supported constraints and measured matching cost for the chosen backend.

The performance question

Constrained decoding adds matching work at each step, but can also reduce the number of tokens the model needs to generate.

Precomputed regular-language transitions can make matching a table lookup; richer grammars require runtime parser work. Constraining the format can also remove unwanted output tokens: a JSON-only response starts at the JSON value instead of generating a preamble or code fence.

When the grammar fixes a run of text, SGLang’s jump-forward decoding can skip repeated sampling decisions and process the forced text to update model state. Whitespace choices, variable-length values, and tokenizer boundaries limit which runs are deterministic.

Suppose the schema requires an age field with type integer. The model might give high probability to "twenty-five", but an integer constraint excludes that string. It must choose a numeric continuation; the grammar does not ensure that the number is 25. Now say the schema requires a status field with enum ["active", "inactive"] and the model's learned distribution wants to say "pending". Masking renormalizes the probabilities of the allowed values; argmax picks the larger one and sampling can pick either. The output is valid, but the constraint has removed the highest-probability status.

Data extraction needs semantic correctness as well as conformance: a schema that excludes the correct value cannot produce a correct extraction. Choose constraints that admit the task’s valid answers.

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: completed payloads follow the schema the client expects.
• Tool calls: when a model decides to call a function, it needs to emit arguments that match the function's signature. Strict grammar-guided decoding can enforce the supported argument structure.
• Code generation: constraining output to valid syntax for a specific language.

Bad use cases:

• Creative writing: unnecessary constraints can restrict the available wording.
• 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

Function calling requires structured arguments, but an ordinary tool-use API may rely on training to produce them. Strict modes can additionally enforce a supported argument schema during decoding.

Schema enforcement does not select the right tool or establish that its arguments are correct. The host still validates permissions and executes the call.

The function-calling post separates these layers in detail: training, optional strict decoding, validation, and runtime execution.

Common misconceptions

"JSON mode means the model understands JSON." JSON mode and schema enforcement are output contracts, not evidence about the model’s understanding. A grammar engine can restrict syntax independently of the model’s learned distribution. 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." Logit masking excludes invalid continuations before sampling, keeping each prefix on a path allowed by the supported grammar. Post-processing examines text already generated. A completed constrained response must still be parsed, and applications must handle interruptions, refusals, and semantic errors.

What's next

Arc 6 opens with what an inference engine actually does: how a serving stack combines model execution, KV storage, and request scheduling.

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. Structured Outputs guide. Supported schemas, SDK parsing, refusals and incomplete output.

• Anthropic. Strict tool use. Distinguishes schema-enforced arguments from ordinary tool definitions.