Prompting a model to “return valid JSON” fails at a rate that is invisible until it isn’t: at low volume a 2% malformed-output rate is a retry. At 5M calls/day, 2% is a retry storm, a poisoned S3 batch, a cron job silently inserting null rows, and an on-call page at 2am. “Retry the prompt” papers over it but costs TTFT multiples and still never bounds the failure to zero. Constrained decoding does: instead of asking the model to format output correctly, you make malformed output un-sampleable by masking the logits during generation.

The idea: turn a grammar into a mask

The generation loop gives you one natural choke point — the logits over the vocabulary at each step. If you know the partial output so far, you can compute which next tokens would keep the output matching a regex, a CFG, or a JSON schema, set every illegal token’s logit to -inf, and sample from what’s left. The model chooses content freely within the allowed set; the format is enforced structurally. This is what Outlines, llama.cpp’s GBNF grammars, vLLM’s guided decoding (2024), and XGrammar (October 2024, the engine vLLM ships today) all do under the hood.

The engineering trick is that you don’t re-derive validity from the raw text on every step — that would be O(vocab × text-length) per token. You compile the pattern into a finite-state machine, then precompute, for each FSM state, the set of vocabulary tokens that are legal transitions. Generation becomes a hash lookup per step:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class GuidedSampler:
    def __init__(self, fsm, vocab):
        self.fsm = fsm
        self.vocab = vocab
        self.state = fsm.initial_state

    def __call__(self, input_ids, scores):
        allowed = self.fsm.get_next_instruction(self.state)
        mask = torch.full_like(scores, float("-inf"))
        mask[allowed.allowed_tokens] = 0.0
        return scores + mask

    def step(self, token_id):
        self.state = self.fsm.advance(self.state, token_id)

The two hidden correctness traps are both in step. First, you must advance the FSM state from the token id, not by decoding the full context to text — decoding input_ids to a string and re-running the regex each step is quadratic and, worse, non-deterministic: two different token sequences can decode to the same string, so the regex state becomes ambiguous. Second, tokenization spans byte boundaries; a token can be a partial UTF-8 codepoint or a multi-token string, which is why production implementations (Outlines, XGrammar) build the FSM over token pieces and byte-level states rather than characters. Get this wrong and valid output gets masked into a corner, producing empty generations and infinite retry loops.

JSON schemas have their own footguns

When your target is a Pydantic/JSON schema rather than a raw regex, the standard move is to translate the schema into a regex that constrains both structure and whitespace. Outlines’ build_regex_from_schema(schema, whitespace_pattern=r"[\n ]*") is the canonical example. The whitespace_pattern matters more than it looks: LLMs learn to emit {"key": "value"} with varying spacing, and if your schema regex demands one specific spacing, the sampler will fight the model’s distribution and burn tokens on backtracking (or deadlock). We run .model_dump_json(indent=2)-style canonical spacing in few-shot examples and match it in the whitespace pattern.

The other footgun is the type-level lie: a schema constrains shape, not semantics. A number field constrained by the regex to -?\d+ will happily emit -999999 where your business logic needs 0..1. Concretely: we had a pricing field come back as -5 — structurally perfect JSON, semantically poison. Constrained decoding removes parse failures, not semantic failures. Keep a Pydantic validation pass with range checks in the pipeline; the two are complementary, not redundant.

What it costs

Precompiled FSM decoding is cheap on the token-generation path: with XGrammar inside vLLM we measure single-digit-percent throughput overhead, and it actually removes the latency tail that retry storms caused. The pathological case is running a pure-Python FSM per step on a big vocabulary — that costs 2-4x tokens/s and is exactly why you should never hand-roll this in production. Measure acceptance: a good pattern accepts >90% of tokens on the first sample, and if you see the sampler constantly rejecting (masked-then-resampled), your regex is over-constrained relative to the model’s learned spacing — widen the whitespace pattern before you blame the model.

Production lessons

• Mask logits, don’t post-validate in the hot path. If you generate freely and validate downstream, malformed output still costs a full generation cycle. The constraint belongs at the sampler, which is where providers put it: OpenAI’s json_schema structured outputs and vLLM’s guided_json are this exact mechanism exposed as an API.
• Pair the mask with few-shot content guidance. Masking enforces format; it does not teach the model what to say. We keep 2-3 in-domain examples per schema and measure a 40% reduction in schema-mismatch resubmits from few-shot alone.
• Schema versioning is real. When your API contract changes, the mask changes, and old masks silently start rejecting previously-legal output. Pin schema versions to the serving engine release.
• Let grammar errors fail loudly. A regex that compiles but never accepts (a typo in the whitespace pattern is the classic) will surface as empty generations. Unit-test your compiled schema against a corpus of hand-written valid/invalid documents before it reaches the sampler.

Constrained decoding won’t make your model more capable — but it will make your pipeline stop being the thing that breaks. In our last quarter, JSON parse failures went from ~2% to 0.0004%, and the retry infrastructure we’d built around prompt-repair got deleted.