Gen AI

Constrained Decoding

Instead of hoping the model generates valid JSON or follows your rules, use a strict mathematical mask at every step to physically block the model from generating anything other than what your schema allows.

Why Does This Exist?

LLMs are notoriously bad at strictly adhering to complex formatting rules. If you ask an LLM to "output valid JSON with exactly these keys," it will almost always work for the first 100 requests. On the 101st request, it will inexplicably add a conversational preface like, "Sure, here is your JSON:", completely breaking the parsing pipeline in your downstream application.

Historically, engineers tried to fix this with prompt engineering ("I will tip you $500 to only output JSON") or complex regex parsing.

Constrained decoding fundamentally solves the problem at the engine level. It guarantees, with 100% mathematical certainty, that the output will conform to your requested structure, making it the most important mechanism for integrating LLMs into robust software systems.

Think of It Like This

The auto-completing typewriter

Imagine an LLM as a highly creative author using a magical typewriter. The author wants to write a poem, but you need them to fill out a strict tax form.

Without constrained decoding, you just hand them the tax form and ask nicely. Maybe they fill it out, or maybe they write a poem in the margin.

With constrained decoding, you install a physical lock on the typewriter's keys. When the author's cursor is in the "Age" box, every letter key is physically locked. The author can only press the number keys. The author's creativity is still used to decide which numbers to press, but they are physically prevented from breaking the rules of the form.

How It Actually Works

The Schema and The State Machine

When you provide a JSON schema or a formal grammar (like regex or BNF) to the inference engine, the engine compiles it into a Finite State Machine (FSM). This FSM tracks exactly where the model is in the generation process.

If the schema requires a JSON object to start, the FSM knows the very first character must be {.

Logit Masking (The Physical Lock)

At generation step 1, the LLM produces its standard raw logits (predictions) for all 100,000 tokens in its vocabulary. Before the engine applies temperature or sampling, it consults the FSM.

The FSM says: "The only valid next character is {." The engine immediately masks out the logits of the other 99,999 tokens, setting their probabilities to exactly 0. The token representing { becomes the only mathematical possibility, so it is guaranteed to be sampled.

At step 2, the FSM advances. "We need a string key, so we need a quote \"." The engine masks out everything except \".

At step 3, the FSM is inside a string value. "Any alphanumeric character is allowed, but no unescaped quotes." The engine leaves the alphanumeric tokens alone, but masks out the bare quote token. The LLM is now free to use its intelligence to choose the actual word, but it cannot break the JSON syntax.

The Speed Advantage

Constrained decoding is often faster than standard decoding. If the FSM determines that there is only one valid token (e.g., closing a required JSON bracket), some engines can bypass the massive LLM forward pass entirely and simply append the required token, saving significant compute time.

Show Me the Code

This conceptually models how logit masking enforces a simple constraint: "The output must be a number."

1import numpy as np2
3# Vocabulary: ["2", "5", "apples", "cats", "}"]4raw_logits = np.array([4.0, 3.5, 8.0, 1.2, -2.0])5
6# The LLM really wants to say "apples" (highest logit)7print(f"Unconstrained Choice: index {np.argmax(raw_logits)} ('apples')")8
9# The Constraint: We are inside a JSON integer field. 10# Only numeric tokens (indices 0 and 1) are allowed.11# Create a boolean mask of allowed tokens.12allowed_mask = np.array([True, True, False, False, False])13
14def apply_constraint(logits: np.ndarray, mask: np.ndarray) -> np.ndarray:15    constrained_logits = logits.copy()16    # Force disallowed tokens to negative infinity (0% probability after softmax)17    constrained_logits[~mask] = -np.inf18    return constrained_logits19
20masked_logits = apply_constraint(raw_logits, allowed_mask)21
22print(f"Masked Logits: {masked_logits}")23print(f"Constrained Choice: index {np.argmax(masked_logits)} ('2')")24
25# -> Unconstrained Choice: index 2 ('apples')26# -> Masked Logits: [  4.    3.5 -inf -inf -inf]27# -> Constrained Choice: index 0 ('2')

Even though the model desperately wanted to talk about apples, the constraint forced it to pick the most likely numeric token, guaranteeing valid output.

Watch Out For

The Tokenization Trap

Constrained decoding operates on tokens, not characters. If your grammar requires the letter 'A', but the LLM's vocabulary doesn't have a token for just the letter 'A' (perhaps 'A' is only available inside larger word tokens), the constraint engine can crash or produce bizarre results. High-quality constrained decoding engines (like Outlines or Guidance) spend immense engineering effort bridging the gap between character-level regex and the model's specific byte-pair tokenization scheme.

The Quick Version

Prompting an LLM to output valid JSON or strict formatting is inherently unreliable.
Constrained decoding fixes this by taking a formal schema and compiling it into a state machine.
At every generation step, the state machine determines which characters are legally allowed next.
The engine uses this list to heavily mask the LLM's logits, forcing the probability of illegal tokens to 0.
The model still uses its intelligence to choose the content, but the engine mathematically forces the syntax to be perfect.