07 — Structured / Guided Decoding

Constraining LLM output to a grammar (JSON schema, regex, EBNF) via per-step logit masking. Powers tool calling, function calling, JSON mode, and any “output must parse” workflow — a large fraction of your agentic day job traffic.

---

The problem

An LLM’s next-token distribution over the ~<phone_number_or_numberic_id_or_random_id_37>k vocab includes many tokens that would be syntactically invalid given the current output prefix. If we’re mid-way through a JSON object and just emitted "user":, legal next tokens are things like ", {, [, 42, null — not random prose tokens. Yet the raw model has nonzero probability on those invalid tokens, and greedy sampling will occasionally pick them, breaking your parser.

Solution: mask illegal tokens’ logits to −∞ before sampling. The model then samples only from legal continuations. Provably valid output, zero retry loops, zero “clean up the JSON” post-processing.

This is called guided decoding, structured output, or constrained decoding. All the same thing.

---

The three libraries

1. Outlines — Rémi Louf et al.

https://github.com/dottxt-ai/outlines. First mover in the modern era.

Mechanism: compile the grammar to a finite-state machine (FSM). States are grammar positions; transitions are token IDs. On each step, look up the current FSM state → set of allowed token IDs → mask.

Precomputation cost: compiling a JSON schema FSM can take seconds (indexes must be built over the full vocab per state). Runtime cost: O(1) per step after compilation.

Strength: elegant, well-tested, extensive schema support. Weakness: compilation time hurt cold start; couldn’t handle context-free grammars (only regular).

2. XGrammar — Yixin Dong et al.

arXiv: <phone_number_or_numberic_id_or_random_id_37>. Repo: https://github.com/mlc-ai/xgrammar. Current leader; used by SGLang and integrated in vLLM.

Two key innovations over Outlines:

a. Vocabulary is partitioned into:

• Context-independent tokens — whose validity doesn’t depend on the full parse state (just on the last token or so). Precomputed once per grammar. This is the ~80-90% of the vocab.

• Context-dependent tokens — whose validity requires runtime PDA (pushdown automaton) traversal. Only ~10-20% of the vocab.

At each step, XGrammar first applies the precomputed context-independent mask (cheap), then runs the PDA only over the context-dependent subset (also cheap because subset is small). Result: per-step overhead falls to ~1-10 μs — essentially free.

b. Adaptive Token Mask Cache — memoize the (grammar_state, recent_context) → mask mapping. Big win for grammars with repetitive states (JSON objects have many).

Supports context-free grammars (JSON schemas naturally become CFGs for nested structure), so it handles more expressive constraints than Outlines could originally.

XGrammar 2 (arXiv <phone_number_or_numberic_id_or_random_id_38>) adds JIT compilation, an Earley parser for dynamic grammars, and TagDispatch for agentic tool calling where the legal grammar depends on which tool was invoked (grammar switches mid-generation).

3. llguidance — Microsoft, used by Guidance library

https://github.com/microsoft/llguidance. Rust-based grammar engine with focus on low latency and lark-syntax grammars. Used inside Microsoft’s Guidance framework. Competitive with XGrammar on many benchmarks.

Comparison for your practical use

Feature	Outlines	XGrammar	llguidance
JSON schemas	✓	✓ (fastest)	✓
Regex	✓	✓	✓
Context-free grammar	Partial	✓	✓
Per-step overhead	~100 μs	~1-10 μs	~10-30 μs
Compilation time	Seconds	Milliseconds	Milliseconds
In vLLM V1	✓	✓ (default)	✓
In SGLang	Partial	✓ (native)	Partial
Dynamic grammar (mid-gen switch)	No	✓ (XGrammar 2)	Limited

In 2026, XGrammar is the default. Use it unless you have a specific reason not to.

---

How the mask actually applies (mechanism level)

In vLLM’s pipeline, structured decoding is a logit processor: after the model produces logits for the next token, but before sampling, apply:

def apply_grammar_mask(logits: Tensor, grammar_state: GrammarState) -> Tensor:
    mask = grammar_state.get_allowed_token_mask(vocab_size)  # bool tensor
    logits.masked_fill_(~mask, -float("inf"))
    return logits

Then normal sampling (temperature, top-p, etc.) runs on the masked logits. Because illegal tokens have logit −∞, softmax gives them probability 0. The sample is guaranteed legal.

After sampling, the grammar state advances by the chosen token:

grammar_state.advance(sampled_token)

That’s the entire runtime loop. All the complexity is in get_allowed_ token_mask and advance, which is where XGrammar’s context- independent/dependent split does its magic.

---

FSM compilation: a JSON example

Say the schema is {"name": string, "age": integer}. Compile to an FSM (simplified):

[start] --'{'--> [expect_key]
[expect_key] --'"name"'--> [expect_colon_name]
[expect_colon_name] --':'--> [expect_string_value]
[expect_string_value] --'"..."'--> [expect_comma_or_close]
[expect_comma_or_close] --','--> [expect_next_key]
[expect_next_key] --'"age"'--> [expect_colon_age]
[expect_colon_age] --':'--> [expect_int_value]
[expect_int_value] --int--> [expect_close]
[expect_close] --'}'--> [DONE]

At each state, the mask over the vocab is derived: which token IDs start with a byte sequence that could match a legal edge out of this state? (Handling BPE tokens crossing byte boundaries is the messy part — a token like "na might be legal here but "n alone isn’t; the FSM must handle token-level transitions, not character-level.)

This token-boundary problem is where Outlines and XGrammar do the heavy engineering. Handling it correctly for tens of thousands of token IDs against a schema is why the compilation used to take seconds — and why XGrammar’s precomputed context-independent mask is such a win.

---

Integration in vLLM V1

vLLM V1 supports structured output via the OpenAI-compatible API:

from openai import OpenAI
client = OpenAI(base_url="http://localhost:8000/v1", api_key="...")

response = client.chat.completions.create(
    model="...",
    messages=[{"role": "user", "content": "Give me a person."}],
    response_format={
        "type": "json_schema",
        "json_schema": {
            "name": "Person",
            "schema": {
                "type": "object",
                "properties": {
                    "name": {"type": "string"},
                    "age": {"type": "integer"}
                },
                "required": ["name", "age"]
            }
        }
    }
)

Internally: vLLM parses the schema, compiles with XGrammar, wires the resulting logit processor into the sampling pipeline. Also supports "type": "json_object" (any valid JSON), "type": "regex", "type": "grammar" (raw EBNF).

For tool calling the model card’s tool schema is converted to a union-typed JSON schema per tool + a discriminator on the tool name. XGrammar 2’s TagDispatch handles the mid-generation switch when the model picks a specific tool.

---

Overhead reality

On XGrammar with a moderate JSON schema on Llama-3-8B on H100:

• Compilation: ~5 ms (JIT-compiled on first request; cached thereafter)

• Per-step masking: ~2-5 μs (essentially noise compared to the ~10-30 ms forward pass)

• Token generation slowdown: <3% end-to-end

Compare to Outlines’ original numbers (~5-15% overhead, seconds of compilation): XGrammar collapsed the cost by ~10×.

Actionable: in 2026 there is essentially no performance reason not to turn on structured output for any parser-consuming endpoint.

---

Failure modes to know

1. Grammar unsatisfiable given prompt. Model is prompted “write a poem” but the response_format demands JSON. Legal tokens still exist, but the model is fighting them → outputs something like {} quickly or hits max_tokens. Quality suffers because the sampling space excluded what the model wanted to say.

2. Token-boundary ambiguity in edge grammars. A grammar that requires exact byte-level constraints (e.g., specific whitespace) can occasionally lack any legal token from certain states. Modern libraries detect this and emit a <phone_number_or_numberic_id_or_random_id_39> byte-level fallback token; older ones threw.

3. JSON with unbounded strings + max_tokens. Model can start a string and never close it before running out of tokens → output truncates mid-string, unparseable. Fix: cap string length in the schema ("maxLength": <phone_number_or_numberic_id_or_random_id_40>).

4. Nested schemas exploding compilation. Deeply recursive schemas (linked list of arbitrary depth) blow up FSM state count. Fix: bound recursion depth in the schema.

---

Reading exercise

1. Skim XGrammar §3 (the algorithm section). Understand the context-independent / context-dependent split.

2. Look at python/sglang/srt/constrained/xgrammar_backend.py (or equivalent). Trace one call: prompt arrives with a JSON schema → compilation → per-step masking.

3. Try to find a corner case: JSON with a pattern regex that XGrammar handles slowly. Reproduce it. This is a plausible OSS contribution area.

---

The intuition to internalize

Structured decoding is a logit processor. That’s it. All the libraries are competing on one narrow question: “how fast can I compute the legal-token mask for the current grammar state?” The mechanism is simple; the engineering is in the constant factors, and XGrammar currently owns them.

For your agentic day job: turn it on. Every tool call gets a schema. Every schema goes through XGrammar. You never write JSON repair code again. Zero retries from malformed output. If your platform doesn’t use structured decoding yet, that’s a Phase 4 quick win alongside prefix caching (file 05).