Constrained decoding: making the model return valid JSON

Willard & Louf, 2023 · Geng et al., 2023

Stop asking the model nicely. Make the invalid output unrepresentable.

Download structured_output_from_scratch.py — everything below runs from it. NumPy and plain Python. There is no language model anywhere in it: a model contributes exactly one thing to this idea — a vector of logits over the vocabulary — so I generate that with numpy and spend the file on the part that does the work.

I'm an AI Engineer. I've shipped models, done the MLOps, and for two years my answer to "the JSON came back malformed" was a better prompt and a retry loop. It worked. That is the worst thing that can be said about it. It worked in dev, it worked in staging, it worked for the demo, and then it failed in production at a rate nobody could put a number on, and the retry loop hid it until the invoice arrived.

Nobody told me there was a version of this problem with an actual guarantee, and that the guarantee is one line long.

It's the causal mask, pointed somewhere else

You already know the retry shape. You've written it for flaky HTTP: 

for attempt in range(5):
    text = model(prompt)
    try:
        return json.loads(text)      # hope
    except ValueError:
        continue                     # hope again, with feeling
raise                                 # and now what?

That is validation. It runs after the fact, it can fail, and its cost is a random variable. Now the other version. At every step the model hands you one vector of logits over the whole vocabulary. A parser knows which of those tokens could possibly continue a valid document. So: 

state = parser.start
while not parser.done(state):
    logits = model(prefix)                  # unchanged. the model is innocent
    logits[not_allowed(state)] = -np.inf    # <-- the entire paper
    tok = sample(logits)
    state = parser.step(state, tok)

That loop is the sampling loop from the GPT page with one line inserted into it. If you read the attention page you have seen that middle line before. It is the causal mask — set the forbidden entries to −∞ before the softmax so they come out at exactly 0. The only difference is what it runs over. The causal mask runs over positions and is driven by time. This one runs over the vocabulary and is driven by a parser.

Validation after the fact is a test. Constrained decoding is a type.

TermMeansProgrammer's analogy
GrammarThe set of strings you will acceptThe schema, before anything is written
Parser stateWhere in the document you areThe cursor in a state machine
Allowed setToken ids that keep the document validThe whitelist for this one step
Logit mask−∞ on everything elseA read-lock on the rest of the vocabulary
Indexstate → allowed set, precomputedA dict you build at boot instead of a scan per request

Why the retry loop is worse than it looks

Say one attempt returns parseable JSON with probability p. Attempts until success is a geometric distribution: mean 1/p, and the quantiles are a log away. My script prices it.

Don't take my word for it. Here's the actual output:

A request costs 400 tokens. You retry until the JSON parses.
p = probability one attempt returns valid JSON.

     p  E[attempts]  p95 attempts   p99.9  tokens/1k reqs  worst case
  0.70         1.43             3       6         571,428   unbounded
  0.90         1.11             2       3         444,444   unbounded
  0.95         1.05             1       3         421,052   unbounded
  0.99         1.01             1       2         404,040   unbounded

simulated 20,000 requests at p=0.95: mean attempts 1.053, max 4

Look at the last column, not the second. 95% costs you about 5% extra tokens, which is fine, and it has no worst case — there is no n at which you can tell your on-call "this will have succeeded". At p=0.99 you still can't. You have bought yourself a tail you haven't measured yet, and a latency budget you can't write down.

The interview question is the last column. Anyone can say "retry with a validator". The answer they're listening for is that a retry loop turns a correctness problem into an unbounded cost-and-latency problem, and constrained decoding turns it into 1.00 attempts.

The one formula

p̃(t | s) = softmax( ℓt + ms(t) ) where ms(t) = 0 if t ∈ A(s), −∞ otherwise

ℓ is the logit vector the model gave you. s is the parser state. A(s) is the set of tokens allowed from that state. That's it — everything else in both papers is how you compute A(s) fast enough to run per token. Read it as pipeline stages:

StepShapeWhat it does
ℓ(V,)One logit per vocabulary entry. The model's whole contribution
A(s)a setThe paper. Which token ids keep the document parseable
+ ms(V,)0 on the allowed ones, −∞ on the rest. Before the softmax
softmax(V,)Renormalises over what's left. Still sums to 1
sampleone idOrdinary sampling. Temperature, top-p, all unchanged
parser.stepnew sAdvance the state machine by the token you actually emitted

One step, before and after

Here is a single concrete step from my toy 45-token vocabulary, at the very start of the document, where the only legal thing is an opening brace. The model wanted a newline. It does not get a newline. 

parser state 0: the document is empty, only '{' can start it
allowed tokens: ['{', '{"']

     token    logit   p before    p after
      '\n'    2.718     0.2016     0.0000  <- forbidden
     '","'    2.680     0.1942     0.0000  <- forbidden
      '0}'    2.122     0.1111     0.0000  <- forbidden
    'null'    1.769     0.0780     0.0000  <- forbidden
       'g'    1.391     0.0535     0.0000  <- forbidden
    'name'    0.980     0.0355     0.0000  <- forbidden
     'age'    0.714     0.0272     0.0000  <- forbidden
       '}'    0.597     0.0242     0.0000  <- forbidden
       '{'    0.002     0.0133     0.8793  <- the only survivors
      '{"'   -1.983     0.0018     0.1207  <- the only survivors

total probability on invalid tokens before masking: 0.9848
total probability on invalid tokens after  masking: 0.0000
probabilities still sum to 1: 1.000000

same mask written with 0.0 instead of -inf: 0.9742 of the
probability mass is STILL on invalid tokens.

Two things worth staring at. The 98.5% of probability mass that the model put on tokens which cannot appear here — that is the fraction of the retry loop's failures you are pre-emptively deleting. And the last line: write the mask as 0.0 instead of −∞ and 97% of the mass is still on garbage. 0 is not "off". 0 is a perfectly ordinary logit. Exactly the bug the attention page's mask table warns about, in a different file.

A real state machine, and what "by construction" means

My grammar is one fixed schema, no whitespace: {"name":"<letters>","age":<digits>}. That language is regular, so a finite-state machine is enough — 20 states, 15 of which are just single steps inside the fixed literals. Then the loop runs, and at each step the mask is whatever that state allows. 

20 states in all, 15 of them single
steps inside a fixed literal. The five that mean something:

  state 0 start            1 chars '{'                  ->  2/45 tokens
  state 1 in name string  28 chars ' "abcdefghij...'    -> 18/45 tokens
  state 2 need a digit     9 chars '123456789'          -> 13/45 tokens
  state 3 in age          11 chars '0123456789}'        -> 16/45 tokens
  state 4 done             0 chars ''                   ->  0/45 tokens

one generation, traced:
  state 0 -> allowed  2/45 -> emitted '{'
  state 5 -> allowed  1/45 -> emitted '"'
  state 6 -> allowed  2/45 -> emitted 'name'
  state 10 -> allowed  3/45 -> emitted '":"'
  state 1 -> allowed 18/45 -> emitted 'ada'
  state 1 -> allowed 18/45 -> emitted 'nam'
  state 1 -> allowed 18/45 -> emitted 'ada'
  state 1 -> allowed 18/45 -> emitted '","'
  state 15 -> allowed  2/45 -> emitted 'age'
  state 18 -> allowed  2/45 -> emitted '":'
  state 2 -> allowed 13/45 -> emitted '36}'

  emitted: {"name":"adanamada","age":36}
  final state 4, accepting: True
  json.loads says: {'name': 'adanamada', 'age': 36}

500 constrained generations: 500 parsed, 0 failed, 0 retries
lengths 19-173 chars, all schema-conformant, 0 cut off by the step cap

500 for 500 is not a good hit rate. It is not a hit rate at all. The parser cannot leave the set of valid prefixes, because the tokens that would take it out of that set were never sampleable. The logits are random noise from rng.normal — a genuinely terrible model — and the output still parses every time. That's the claim: the guarantee comes from the mask, not from the model having been persuaded.

Be precise about "JSON" in an interview. A fixed schema like mine is a regular language, and a finite-state machine handles it. JSON in general is not regular — arbitrary nesting needs a stack, which means a context-free grammar and a pushdown automaton. The state-machine story covers the schemas most applications actually want; it does not cover "any JSON".

The hard part: grammars speak characters, models emit tokens

This is where most explanations stop, and it's the part that actually costs you. Your grammar is defined over characters. The model emits tokens, and a token is a multi-character string that some compression algorithm picked years ago without consulting your schema — see the tokenisation page. So a single token can straddle a grammar boundary.

Sitting inside the name string, 28 characters are legal here. Watch what that does and does not tell you about tokens: 

     token  first char ok?  whole token ok?  why
      '"}'            True            False  walks off the DFA
     '","'            True             True  ends in state 15
'lovelace'            True             True  ends in state 1
     'ace'            True             True  ends in state 1
       '}'           False            False  walks off the DFA
     'age'            True             True  ends in state 1
     '":"'            True            False  walks off the DFA

The same token flips legality with the state. Token '0}':
  from state 0 (start          ): None
  from state 1 (in name string ): None
  from state 2 (need a digit   ): None
  from state 3 (in age         ): 4
  from state 4 (done           ): None

'"}' is the one to hold on to. Its first character is legal — the quote closes the name string. The } welded to it is not, because the schema still owes us an age field. A character-level check on the first character says yes; the token as a unit is a no; and you cannot emit half a token. That is why you run the whole token through the automaton and keep only tokens that survive end to end.

'0}' shows the other direction: the same token is illegal in "need a digit" (JSON forbids a leading zero) and legal one state later. Legality is a property of the pair, not of the token. So the answer is a table: 

So the answer is an index -- parser state -> allowed token ids:
  state 0 (start          )  2 tokens  ['{', '{"']
  state 1 (in name string ) 18 tokens  [' ', '"', '","', 'a', 'ace', 'ada', '...']
  state 2 (need a digit   ) 13 tokens  ['1', '180', '2', '3', '36', '36}', '...']
  state 3 (in age         ) 16 tokens  ['0', '0}', '1', '180', '2', '3', '...']
  state 4 (done           )  0 tokens  []
  ... and the other 15 literal states, 1 or 2 tokens each

That table is Willard and Louf's contribution. Not the masking — people were masking already, and Geng et al. had wired a grammar to a decoder the same year. The Outlines claim is about when you compute the allowed set: once per (grammar, tokeniser) pair, at load time, instead of once per generated token.

What the index costs, and what it saves

I count DFA character-steps rather than milliseconds, so the script prints the same numbers on your laptop as on mine. It's also the more honest unit: it's the work, not my machine's mood. 

vocabulary 45 tokens, grammar 20 states

  parser state   naive scan   index lookup
         start        46 steps         1 lookup
in name string        82 steps         1 lookup
  need a digit        51 steps         1 lookup
        in age        52 steps         1 lookup
          done        45 steps         1 lookup

index built once, at load time: 986 character-steps, 68 entries

and the scan grows with the vocabulary while the lookup does not:
  vocab    45: naive      82 steps per generated token, index 1
  vocab   180: naive     487 steps per generated token, index 1
  vocab   720: naive    2107 steps per generated token, index 1
  vocab  2880: naive    8587 steps per generated token, index 1

The whole index cost 986 character-steps to build — under a dozen naive scans — and after that every step is a dict lookup. Multiply the left column by a real vocabulary (50k–200k entries), a real grammar, and every token of every request, and you have the difference between a technique and a product. That is the word "Efficient" in the title, and all it claims.

What this does not buy you

Six outputs from the constrained decoder. All six parse. All six match the schema. Zero of them are true. 

ground truth: {'name': 'ada lovelace', 'age': 36}

                            output  parses  schema  correct
           {"name":"age","age":36}     yes     yes       NO
             {"name":"","age":479}     yes     yes       NO
              {"name":"","age":30}     yes     yes       NO
               {"name":"","age":8}     yes     yes       NO
     {"name":"","age":93594505170}     yes     yes       NO
         {"name":"null","age":390}     yes     yes       NO

6 distinct outputs, all valid JSON, all matching the
schema. The number that were right about Ada Lovelace: 0

Schema validity is a property of the output's syntax. It says nothing about the world. My "model" here is random noise, which makes the point loudly, but the same thing is true of a good model: constraining moves the failures from "unparseable" to "parseable and wrong", and parseable and wrong is the one that gets into your database. Whether the age is 36 is an eval question — see the evals page.

One honest cost, while we're here. Masking renormalises over a subset, so the constrained distribution is not the model's distribution conditioned on validity — it's a greedy, per-step approximation of it, and people have measured quality shifts from it in both directions. Don't sell constrained decoding as free. Sell it as a guarantee you're buying with a known, small distortion.

The code

Plain Python and NumPy. No torch, no model, no training — the automaton, the mask and the index, so you can watch the allowed set shrink. Every function under 20 lines.

Download the full script — nine short functions plus seven runnable demos. Then: 

python3 structured_output_from_scratch.py
def step_char(state, ch):
    """One character. None means 'this character cannot continue the doc'."""
    return DELTA.get(state, {}).get(ch)


def step_token(state, token):
    """Feed a whole token through, character by character.

    Returns the state after the token, or None if ANY character inside it
    fell off the automaton. A token is allowed or it is not; there is no
    partial credit, because you cannot emit half a token."""
    for ch in token:
        state = step_char(state, ch)
        if state is None:
            return None
    return state


def allowed_tokens(state):
    """Naive version: walk every token in the vocabulary through the DFA.

    Cost is O(vocab x token length) PER GENERATED TOKEN. This is the thing
    the Outlines paper removes."""
    out = {}
    for i, tok in enumerate(VOCAB):
        nxt = step_token(state, tok)
        if nxt is not None:
            out[i] = nxt
    return out


def apply_mask(logits, allowed):
    """Set every disallowed logit to -inf. Not 0 -- 0 is a perfectly ordinary
    logit that softmax will happily hand probability to."""
    masked = np.full_like(logits, -np.inf)
    idx = np.fromiter(allowed, dtype=int, count=len(allowed))
    masked[idx] = logits[idx]
    return masked


def build_index():
    """state -> {token id: state after that token}. Built once, reused forever."""
    return {s: allowed_tokens(s) for s in DELTA}

build_json_dfa (which chains one state per character of each fixed literal), generate (the loop from the top of this page, plus tracing), softmax, sample and the vocabulary list are all in the script.

Now break it

This is the part that actually makes it stick. Reading won't do it. You debug for a living — reverse-engineering from broken behaviour is your native mode, and every row here is a bug someone has shipped.

Break thisWatch for
Pass mask_with_zero=True to generate — the mask writes 0.0 instead of -np.infDemo 7 prints invalid outputs: 200/200 against 0/200 for −∞. At step one, 0.9742 of the probability mass is still on tokens that cannot legally appear.
In allowed_tokens, replace step_token with step_char(state, tok[0]) — check the grammar one character at a timeToken '"}' passes the check from inside the name string and closes the document early: {"name":"ada"}. Valid JSON, wrong schema, no age field. Demo 7(b) prints the disagreement.
Sample from the raw logits and reject illegal tokens afterwards, instead of masking firstDemo 7(c): mean 23.6 samples, max 142, to get one legal first token. Masking gets it in 1, every time, from the same distribution.
Delete the retry cap: while True: around the parse in demo 1's simulationAt p=0.90 over 100,000 requests the longest run takes 6 attempts — 2,400 tokens and a timeout for one user. The mean stays a comfortable 1.109 the whole time.
Trust the values: assert only json.loads(text) succeeds in demo 6Every assertion passes. {"name":"","age":479} is well-formed, schema-conformant and completely wrong about Ada Lovelace. 0 of 6 correct.
Drop max_steps to 12 in generateDemo 3's truncated count goes from 0 to 472 of 500. A length cap can slice a valid prefix in half — the grammar guarantees the prefix stays valid, not that you gave it room to finish.
Then read Willard & Louf — the problem statement and the indexing section, which is where the finite-state-machine construction and the claim about per-token cost live. Skip the vocabulary-preprocessing details until you need to implement one. Geng et al. is a shorter read and worth it for the framing: a grammar as a decoding-time constraint rather than something you fine-tune into the weights.

On the maths anxiety

There is almost none here, and that surprised me. The retry section is one distribution — the geometric — and everything I printed from it is 1/p and a log to turn "how many attempts covers 95% of requests" into a number. You could derive that column in a spreadsheet.

The mechanism is a comparison and an assignment: is this token in a set, and if not, write −∞. The only "maths" is knowing why −∞ and not 0, and that's just knowing what exp(−∞) = 0 does inside a softmax. Same fact as the causal mask.

The genuinely useful theory is computer science, not maths, and it is the first-year kind: regular languages and finite-state machines, context-free grammars and pushdown automata, and the fact that a fixed schema lives in the first box while nested JSON lives in the second. If you can say which of those two your schema needs, you understand this paper. What you actually need on the job is different again: knowing your tokeniser, knowing your library (Outlines, guidance, llama.cpp's grammars, the structured-output modes the APIs now ship), and an eval set — because the failure mode you've just bought is confidently well-formed nonsense.

Where to go next

This page gave you the mask and the index. These give you the compiler, the competing designs, and the production ergonomics.

Order I'd take them in: Outlines docs first — run it on your own schema and see the guarantee before you read about it — then the Willard & Louf paper for the machine, then Geng et al. for whether it helps accuracy, then coalescence when you start caring about latency.