Llm Buildx

Constrained Decoding: How We Actually Get Structure Out of LLMs

Somewhere in every codebase that shipped an LLM feature before mid-2024, there is a function that looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def extract_json(text):
    try:
        return json.loads(text)
    except json.JSONDecodeError:
        pass
    # remove the fence
    m = re.search(r"```(?:json)?\s*(.*?)\s*```", text, re.S)
    ...
    # remove the prefix eg. "Sure! Here's the JSON:"
    ...
    # remove the trailing comma
    ...
    # yikes! I give up, let's retry

Mine had three levels and a retry counter. I was not proud of it, but I was also not the only one who wrote it. The comments got shorter and angrier as they went down the file.

These functions are dead now, and the way they died is more interesting than the fact that they did. This post is about what actually changed between “please respond in JSON” and a hard guarantee, and why the guarantee is real.

The four eras

Era 1: JSON mode (November 2023)

response_format: {"type": "json_object"}. A real improvement and a genuinely misunderstood one.

JSON mode guarantees the output is syntactically valid JSON. It guarantees nothing about which JSON. You could ask for {name, age, skills} and get back {"person": {"full_name": "Arun"}}, and it would still be considered a success. It solves parsing but says nothing about matching your schema.

Era 2: function calling as schema smuggling

If you look at it, our goal is to receive a typed object from the model. And back then, function calling was the only place in the API that accepted a JSON Schema. So the process was to declare a fake tool (record_extraction, in the example code below), force the model to call it, and read the arguments as a JSON object.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

tools = [{
    "type": "function",
    "function": {
        "name": "record_extraction",
        "parameters": {                # the JSON Schema, smuggled in as "parameters"
            "type": "object",
            "properties": {"name": {"type": "string"}, "age": {"type": "integer"}},
            "required": ["name", "age"],
        },
    },
}]
response = client.chat.completions.create(
    model="gpt-3.5-turbo", messages=messages, tools=tools,
    tool_choice={"type": "function", "function": {"name": "record_extraction"}},
)
args = json.loads(response.choices[0].message.tool_calls[0].function.arguments)

In fact, the pattern was so popular that Instructor built a good library around this. Pydantic model in, validated object out and automatic retry (reference here). The retry isn’t free, obviously. As with retries in agentic loops, it appended the model’s own bad answer plus the validator’s error and resent the whole conversation. Every retry is, therefore, a full extra round trip with a longer prompt. Tokens and tail latency go for a toss for a mistake that the model made.

Era 3: constrained decoding

Across 2024 and 2025, vLLM, Gemini, OpenAI and Anthropic all shipped constrained decoding, in that order. They all landed on the same name for it, structured outputs, and differ mainly in how the schema gets passed.

Anthropic’s version takes a JSON Schema on output_config.format:

1
2
3
4
5
6
7
8

response = client.messages.create(
    model="claude-opus-5",
    max_tokens=1024,
    messages=messages,
    output_config={
        "format": {"type": "json_schema", "schema": SCHEMA},
    },
)

What each one accepts differs. vLLM is the most permissive: JSON Schema, regex, EBNF grammars (for full-blown languages) and plain choice lists. The hosted APIs take JSON Schema, or a Pydantic class that their SDK quietly converts to JSON Schema before sending.

That’s the story, but let’s deep dive into how it actually works behind the scenes.

How it actually works

We all know that an LLM generates one token at a time. At each step (aka the model’s forward pass) it produces a vector of logits: a raw score per token in its vocabulary. A softmax converts those logits into a probability for each token. The sampler then picks from that distribution, while considering temperature, top-p, top-k and so on.

Constrained decoding is a step that’s inserted between logits and the actual selection of the token (sampling). To visualise this:

As you can see, the grammar engine never touches the model weights. It simply assesses which tokens are valid as the next token to comply with the output schema. Based on this assessment, it sets the invalid tokens’ logits to negative infinity. This way, the softmax gives the invalid ones a probability of zero, making them unsampleable. Temperature, top-p and top-k all still run, just after the mask, over whatever valid tokens are left standing.

Show me

The easiest way to understand this is to shrink the problem and visualise it. The following is a trace from a real run of XGrammar, the engine vLLM defaults to, against a vocabulary of thirteen tokens.

All we want back is a severity record, nothing more:

1

{"sev":"high"}

Here’s an EBNF representation of the grammar. Every legal output is four or five tokens, then <eos>:

1
2

root ::= "{" "\"sev\"" ":" sev "}"
sev  ::= "\"low\"" | "\"high\""

The vocabulary, token id as the column number:

id0123456789101112
token{}"sev":"low""high""High"Sure!"low"}"high"}"<eos>

Some of these are traps, introduced on purpose. "High", Sure and ! are added to simulate what an “unconstrained” model would generate. "low"} and "high"} each cross a grammar boundary in a single token: a value plus the brace that belongs to the next rule.

Let’s trace the matcher one step at a time:

The mask at every step, with and without it applied. Click to enlarge.

Read the last two columns together. With the mask: {"sev":"high"}. With the same scores and no mask: Sure"sev":"High"}, which is the retry loop’s entire failure mode compressed into one string. Step 3’s mask, 0xe30, is 111000110000 in binary: bit 5 ("high") and bit 4 ("low") are on, bit 6 ("High") is off. That’s the whole mechanism, in one number.

Four of these six steps have exactly one legal token. The model gets any real say at only two of them: step 1 (2 options) and step 3, picking the severity itself (5 options). Zoom into what happens to the scores at step 3, the model’s favourite token going in:

Step 3: what the mask does to the model’s scores. Click to enlarge.

Three things happen, in this order. Wherever the bit is 0, the score becomes -∞; "High" held 42% of the probability and now has none. Softmax runs over what’s left; the five legal tokens held about 47% between them and now hold 100%. And the model’s relative preferences among the survivors don’t move: "high" was 4.5× as likely as "low" before the mask (0.282 vs 0.063), and it still is after (0.607 vs 0.135).

The model did not get better. It got fewer options.

That observation is also an optimisation waiting to be claimed. If only one token is legal, there’s no need to run the forward pass at all. Just append it and move on. This idea goes by several names, jump-forward decoding, fast-forwarding or coalescence, and it pays off on schema-heavy output, where fixed key names make up most of the text.

In practice

One thing that’s easy to miss in the trace above is that tokens don’t respect grammar boundaries. In our vocabulary, "low"} is a single token carrying a value and the closing brace that belongs to the rule around it. Grammar rules and token boundaries simply don’t always line up, which is why engines like XGrammar work at the byte level rather than the token level.

So what changed

That extract_json function didn’t die because somebody finally wrote a better regex. It died because we don’t need it anymore.

For three eras we were doing the same thing in different costumes: let the model emit whatever it likes, then inspect the wreckage. Fence-stripping regexes, JSON mode, a fake tool with a schema smuggled into its parameters and, of course, the retry loop. The fixes got cleverer, but it was still post-generation validation.

Constrained decoding removed the need for that. The schema stopped being something we check the output against, and became part of the machinery that produces it.

The grammar guarantees shape, and only shape. Our grammar will happily emit {"sev":"low"} for an incident that was very much critical, and constrained decoding is not going to solve that. That’s a different problem space.