LLM Decoding and Structured Output
Consider a hypothetical service that reads customer reviews and must return a JSON object such as {"label": "pos", "score": 7} to the next stage of a pipeline. The same prompt sent twice returns slightly different answers. One response in fifty starts with “Sure, here is the JSON” and breaks the parser. Another is perfectly valid JSON, passes every type check, and carries a label that contradicts the review. Lowering a setting called temperature seems to help with the first problem and does nothing for the second.
These symptoms come from one place: the step that turns a language model’s output distribution into actual text. The model does not produce text. It produces a probability distribution over the next token, and a separate procedure, the decoder, chooses a token from it, appends it, and asks the model again. How that choice is made decides how repeatable the output is, how diverse it is, and whether it can be forced into a required format. It cannot decide whether the content is true. The chain runs from greedy and beam search through temperature, top-k and top-p, to token masking for structured output, and ends with the question of what a format guarantee leaves open and how to evaluate a configuration.
The next-token view of a language model from Language Models: Objectives, Capabilities, and Limits (the prerequisite for this article) and the softmax function (see Softmax and Multiclass Classification Explained) are assumed. All programs use Python 3.12 and the standard library only. The “model” in the larger experiments is a stub with hand-set logits so that results are exactly reproducible and every mechanism is visible; its numbers describe the stub, not any real model.
From logits to one token
An autoregressive language model defines the probability of a token sequence \(y_1,\dots,y_n\) given a prompt \(x\) as a product of per-step conditionals:
\[p(y \mid x)=\prod_{t=1}^{n} p(y_t \mid y_{<t}, x)\]
At step \(t\) the network outputs one real number per vocabulary entry, the logits \(z_t\in\mathbb{R}^{V}\), and softmax converts them to probabilities, \(p(v \mid y_{<t},x)=e^{z_{t,v}}/\sum_{u}e^{z_{t,u}}\). The vocabulary size \(V\) is typically tens of thousands to a few hundred thousand tokens (see Tokenization Explained: BPE, WordPiece, and SentencePiece). Everything in this article happens after those probabilities exist and before the chosen token is appended to the context.
Decoding therefore faces two separate questions. The first is a search problem: which whole sequence \(y\) is best? The number of sequences grows as \(V^n\), so exact maximization of \(p(y\mid x)\) is infeasible for any realistic \(n\), and every practical decoder commits to tokens one at a time. The second is a diversity problem: should the same prompt always yield the same text? A classifier-like task (extract a field, choose a label) wants the answer the model considers most likely, every time. A brainstorming task wants different answers on different calls. Different decoders serve these two needs, and mixing them up is the most common source of confusing behavior.
One limit applies throughout. A decoder only selects from what the model already assigns probability to. It cannot add knowledge, and a setting that makes output look more varied does not make the model better informed.
Greedy and beam search: choosing the likeliest sequence
Greedy decoding takes the highest-probability token at every step. It is cheap, needs one model call per token, and is deterministic given identical logits. Its weakness is that the best token now can lead to a poor sequence later. The program below makes this concrete with a two-step toy model whose conditional probabilities are written by hand, so every sequence probability can be enumerated.
import itertools, math
# A two-step toy language model over tokens A, B, C. Probabilities are hand-written.
first = {"A": 0.50, "B": 0.40, "C": 0.10}
second = { # p(next token | first token)
"A": {"A": 0.34, "B": 0.33, "C": 0.33},
"B": {"A": 0.90, "B": 0.05, "C": 0.05},
"C": {"A": 0.40, "B": 0.30, "C": 0.30},
}
def seq_prob(s):
return first[s[0]] * second[s[0]][s[1]]
# Greedy: take the most probable token at each step.
g1 = max(first, key=first.get)
g2 = max(second[g1], key=second[g1].get)
greedy = g1 + g2
# Exhaustive search over all 9 two-token sequences.
all_seqs = {a + b: seq_prob(a + b) for a, b in itertools.product("ABC", repeat=2)}
best = max(all_seqs, key=all_seqs.get)
# Beam search with width 2: keep the 2 best prefixes after each step.
beam = sorted(first.items(), key=lambda kv: -kv[1])[:2]
cands = {a + b: p * second[a][b] for a, p in beam for b in "ABC"}
beam_best = max(cands, key=cands.get)
print(f"greedy : {greedy} p={seq_prob(greedy):.3f}")
print(f"exhaustive : {best} p={all_seqs[best]:.3f}")
print(f"beam (w=2) : {beam_best} p={cands[beam_best]:.3f}")
print("sum of all sequence probabilities:", round(sum(all_seqs.values()), 6))greedy : AA p=0.170
exhaustive : BA p=0.360
beam (w=2) : BA p=0.360
sum of all sequence probabilities: 1.0After token A (probability 0.50) the model has no strong continuation: the three next tokens share the mass almost equally. After token B (probability 0.40) the model is nearly certain that A follows. Greedy search takes A first and ends with sequence AA at probability 0.170. The sequence BA has probability 0.360, more than twice as large, and greedy search cannot see it because it looks one step ahead only.
Beam search keeps the \(B\) best prefixes at each step instead of one, extends each by every token, and keeps the \(B\) best extensions. With width 2 it keeps A and B after step one, scores all six extensions, and recovers BA. Beam search costs about \(B\) times more computation and still offers no guarantee of finding the maximum-probability sequence: a prefix outside the beam can never return. Because every extra token multiplies the sequence probability by a number below one, plain beam search also prefers short sequences, which is why implementations add a length normalization of the score.
Highest probability is not always the goal. Holtzman et al. observe that for open-ended text generation, likelihood-maximizing decoding produces text that is bland and repetitive, and they use that observation to motivate sampling from a truncated distribution (covered below). For tasks that have a single right answer, such as extraction or classification, the observation does not apply, and greedy or beam decoding is the natural choice.
A word on “deterministic”. Greedy decoding is a deterministic function of the logits. The logits themselves can differ slightly between runs because of floating-point reduction order, batch composition or hardware, and when two tokens are nearly tied a tiny difference flips the argmax, after which the two continuations diverge. Treat repeatability of greedy output as likely but not guaranteed unless the serving stack documents otherwise.
Temperature: reshaping the distribution
Temperature divides the logits by a positive scalar \(T\) before softmax:
\[p_i(T)=\frac{e^{z_i/T}}{\sum_{j}e^{z_j/T}}\]
The ratio of any two probabilities becomes \(p_i/p_j=e^{(z_i-z_j)/T}\). A logit gap of 2 means a probability ratio of \(e^{2}\approx 7.4\) at \(T=1\), \(e^{4}\approx 54.6\) at \(T=0.5\), and \(e^{1}\approx 2.7\) at \(T=2\). Dividing by \(T<1\) widens every gap, so the distribution sharpens toward the largest logit. Dividing by \(T>1\) narrows the gaps, so it flattens toward uniform. Two limits bound the behavior. As \(T\to 0^{+}\) all mass goes to the largest logit (to the tied tokens, if several share the maximum), which is greedy decoding, and APIs that accept \(T=0\) commonly implement exactly that special case because division by zero is undefined. As \(T\to\infty\) the distribution approaches uniform over the whole vocabulary. Temperature never changes the ranking of tokens, only how much probability the ranking gets.
The program below computes the effect on a six-token example, using entropy in bits, \(H(p)=-\sum_i p_i\log_2 p_i\), as a summary of how spread out the distribution is (see Probability and Information Theory for Deep Learning for entropy).
import math, random
from collections import Counter
def softmax(z, T=1.0):
m = max(z)
e = [math.exp((x - m) / T) for x in z]
s = sum(e)
return [x / s for x in e]
def entropy_bits(p):
return -sum(x * math.log2(x) for x in p if x > 0)
tokens = ["the", "a", "this", "that", "one", "zebra"]
logits = [3.0, 2.2, 1.5, 1.0, 0.2, -2.0]
print(f"{'T':>5} {'p(top)':>7} {'p(zebra)':>9} {'entropy(bits)':>14}")
for T in (0.25, 0.5, 1.0, 1.5, 3.0):
p = softmax(logits, T)
print(f"{T:>5} {p[0]:>7.3f} {p[-1]:>9.4f} {entropy_bits(p):>14.3f}")
def top_k_filter(p, k):
keep = set(sorted(range(len(p)), key=lambda i: -p[i])[:k])
q = [x if i in keep else 0.0 for i, x in enumerate(p)]
s = sum(q)
return [x / s for x in q]
def top_p_filter(p, top_p):
order = sorted(range(len(p)), key=lambda i: -p[i])
keep, total = set(), 0.0
for i in order:
keep.add(i)
total += p[i]
if total >= top_p:
break
q = [x if i in keep else 0.0 for i, x in enumerate(p)]
s = sum(q)
return [x / s for x in q]
peaked = softmax([6.0, 2.0, 1.0, 0.5, 0.0, -1.0])
flat = softmax([1.2, 1.1, 1.0, 0.9, 0.8, 0.7])
for name, p in (("peaked", peaked), ("flat", flat)):
kept_p = sum(1 for x in top_p_filter(p, 0.9) if x > 0)
kept_k = sum(1 for x in top_k_filter(p, 3) if x > 0)
print(f"{name:>6}: top-p(0.9) keeps {kept_p} tokens, top-k(3) keeps {kept_k}; max prob {max(p):.3f}")
# Check that sampling reproduces the filtered, renormalized distribution.
rng = random.Random(0)
q = top_p_filter(softmax(logits, 1.0), 0.9)
draws = Counter(rng.choices(range(len(q)), weights=q, k=20000))
print("top-p(0.9) at T=1: theory ->", [round(x, 3) for x in q])
print(" sample ->", [round(draws[i] / 20000, 3) for i in range(len(q))]) T p(top) p(zebra) entropy(bits)
0.25 0.958 0.0000 0.266
0.5 0.785 0.0000 0.991
1.0 0.533 0.0036 1.806
1.5 0.415 0.0148 2.131
3.0 0.288 0.0545 2.431
peaked: top-p(0.9) keeps 1 tokens, top-k(3) keeps 3; max prob 0.968
flat: top-p(0.9) keeps 6 tokens, top-k(3) keeps 3; max prob 0.211
top-p(0.9) at T=1: theory -> [0.553, 0.249, 0.123, 0.075, 0.0, 0.0]
sample -> [0.55, 0.252, 0.123, 0.075, 0.0, 0.0]The table at the top shows the logits [3.0, 2.2, 1.5, 1.0, 0.2, -2.0] under five temperatures. At \(T=1\) the top token has probability 0.533 and the implausible token “zebra” 0.0036. At \(T=3\) the top token drops to 0.288 and zebra rises to 0.0545, about fifteen times more likely. Entropy rises from 0.266 bits at \(T=0.25\) to 2.431 bits at \(T=3\); the maximum for six tokens is \(\log_2 6\approx 2.585\) bits.
Small per-token probabilities matter because a sequence has many tokens. If an unwanted tail token has probability 0.005 at each of 200 steps, the chance of at least one such token somewhere is \(1-0.995^{200}\approx 0.63\). Higher temperature multiplies this exposure, and a single off-path token early in a response conditions everything after it.
Temperature appears in a second place in machine learning, where it has a different job. In classifier calibration, one scalar is fit on held-out data to make predicted probabilities match observed frequencies (see Temperature Scaling). The formula is identical. The purpose is not: the calibration temperature is estimated from data to minimize a loss, while the sampling temperature is a chosen knob that trades repeatability against variety. A sampling temperature of 0.7 is not a statement that the model is 70% sure of anything.
Truncation: top-k and top-p
Softmax assigns every token a nonzero probability. With a vocabulary of 100,000 entries, thousands of implausible tokens each holding a tiny probability can together hold noticeable mass, and sampling draws from that tail at a rate equal to its mass. Truncation methods remove the tail before sampling and renormalize what is left.
Top-k keeps the \(k\) highest-probability tokens. Its weakness is that a fixed \(k\) fits neither situation. When the model is nearly certain, \(k=40\) still admits 39 tokens that should not be there. When many continuations are plausible, a small \(k\) cuts off reasonable ones. Top-p, introduced as nucleus sampling by Holtzman et al., keeps the smallest set of tokens whose cumulative probability reaches \(p\). The size of the set adapts: one token when the distribution is peaked, many when it is flat. The second half of the program output above shows this. For a peaked distribution (maximum probability 0.968) top-p with \(p=0.9\) keeps one token, while top-k with \(k=3\) keeps three. For a flat distribution (maximum probability 0.211) top-p keeps all six tokens, while top-k with \(k=3\) still keeps three.
The last two lines of the output check the sampler itself. Filtering the \(T=1\) distribution with top-p 0.9 leaves four tokens with renormalized probabilities 0.553, 0.249, 0.123 and 0.075 (the excluded tokens 0.0), and 20,000 draws reproduce those frequencies to within about 0.003. The check confirms that “sample with truncation” means sampling from the filtered, renormalized distribution and nothing more mysterious. A PyTorch implementation of the same filters, with temperature and a full generation loop, appears in Building a Transformer Language Model in PyTorch.
Three implementation details change results. First, order: many implementations apply temperature before truncation, but that is a convention to confirm in the library, because truncating first and then applying temperature selects a different token set. Second, ties and boundary tokens: top-p includes the token that crosses the threshold, so the kept set always has cumulative mass of at least \(p\). Third, other logit adjustments such as repetition penalties, which lower the logits of tokens already generated, are applied to the logits before softmax and interact with all of the above.
Sampling parameters are tuned per task rather than set once. A starting point to tune on a task’s own evaluation set, not a rule: greedy or a low temperature for extraction, classification and code; moderate temperature with top-p for open-ended writing; several samples at higher temperature when the application combines candidates, for example by majority vote or by choosing the one that passes a verifier. Combining samples helps only when sample errors are not all the same error, which is itself something to measure.
Decoding speed-ups interact with sampling. Speculative decoding drafts several tokens with a smaller model and verifies them with the large one, and with the acceptance rule described in LLM Inference Optimization it preserves the target model’s sampling distribution, including temperature and truncation, so it changes latency rather than the distribution of outputs.
Constrained generation: masking invalid tokens
Prompting a model to “return only valid JSON” shifts probabilities but guarantees nothing, because every invalid token keeps a nonzero probability at every step. Constrained generation changes the guarantee by changing the sampler. At each step, a constraint determines the set \(A_t\) of tokens that can still lead to an acceptable output. The logits of all tokens outside \(A_t\) are set to \(-\infty\) before softmax, so their probability becomes exactly zero. The effective distribution is
\[\tilde p(v \mid y_{<t},x)=\frac{p(v \mid y_{<t},x)\,\mathbf{1}[v\in A_t]}{\sum_{u\in A_t}p(u \mid y_{<t},x)}\]
where \(\mathbf{1}[\cdot]\) is 1 when the condition holds and 0 otherwise. The model is untouched; only the choice is restricted. Any decoding method from the previous sections (greedy, temperature, top-p) can run on top of the masked distribution. The remaining question is how to compute \(A_t\) quickly.
The constraint as an automaton
A format described by a regular expression corresponds to a deterministic finite automaton (DFA): a set of states, a start state, and a transition for each character. A state is accepting if the text read so far is a complete valid output. Feeding the generated text through the DFA tells the decoder which state it is in; the allowed set at that state is every token whose characters keep the automaton alive. Willard and Louf describe this view of generation as transitions through a finite-state machine and build an index from automaton states to allowed vocabulary tokens, so the per-step cost is a table lookup instead of a scan of the vocabulary. Formats with arbitrary nesting, such as general JSON with objects inside arrays inside objects, cannot be recognized by a finite automaton and need a context-free grammar and a stack. Geng et al. study grammar-constrained decoding of this kind for structured NLP tasks without fine-tuning.
The code below implements the mechanism for a small format: {"label": "pos|neg|neu", "score": 0-9}. Because that language has only 30 strings, the DFA is built directly as the set of prefixes of valid strings. A regular expression compiler would produce the same kind of object from a pattern.
import math, random, zlib
# ---- 1. The constraint: a character-level DFA -------------------------------
# Language: {"label": "<pos|neg|neu>", "score": <0-9>}
LABELS = ["pos", "neg", "neu"]
VALID = [f'{{"label": "{l}", "score": {d}}}' for l in LABELS for d in range(10)]
def build_dfa(strings):
"""States are prefixes of valid strings; a state is accepting if it is a full string."""
states = {s[:i] for s in strings for i in range(len(s) + 1)}
accepting = set(strings)
def step(state, ch):
nxt = state + ch
return nxt if nxt in states else None # None = dead state
return step, accepting
step, ACCEPT = build_dfa(VALID)
# ---- 2. The vocabulary: multi-character tokens, as in a real tokenizer -------
VOCAB = (['{"', 'label', '": "', 'pos', 'neg', 'neu', '", "', 'score', '": ',
'"}', '}', '{', '"', ' ', ':', ',', 'Sure', 'Here', ' is', '\n', '```', 'json',
'positive', 'negative', 'label"', 'pos"', '": "pos', '10']
+ [str(d) for d in range(10)] + ['<eos>'])
EOS = VOCAB.index('<eos>')
def advance(state, token):
"""Feed a token's characters through the DFA. Returns the new state or None."""
for ch in token:
state = step(state, ch)
if state is None:
return None
return state
# ---- 3. The index: for every DFA state, which tokens are allowed ------------
def build_index():
states = {s[:i] for s in VALID for i in range(len(s) + 1)}
index = {}
for st in states:
allowed = {}
for tid, tok in enumerate(VOCAB):
if tid == EOS:
if st in ACCEPT:
allowed[tid] = st # EOS is legal only in an accepting state
continue
nxt = advance(st, tok)
if nxt is not None:
allowed[tid] = nxt
index[st] = allowed
return index
INDEX = build_index()
# ---- 4. Masked sampling -------------------------------------------------------
def softmax(z, T):
m = max(z)
e = [math.exp((x - m) / T) for x in z]
s = sum(e)
return [x / s for x in e]
def sample_step(logits, T, rng, allowed=None):
"""Sample one token id. If `allowed` is given, every other token gets probability 0."""
z = list(logits)
if allowed is not None:
z = [x if i in allowed else -math.inf for i, x in enumerate(z)]
p = softmax(z, T)
return rng.choices(range(len(p)), weights=p, k=1)[0]Two design points are visible in the code. The vocabulary contains multi-character tokens, as real tokenizers do, so the index is built by pushing each token’s characters through the DFA for every state; a token is allowed in a state only if all its characters survive. And the end-of-sequence token is allowed only in an accepting state, which is how the constraint decides when the output is complete. The next program inspects the index.
from constrained import *
print("vocabulary size:", len(VOCAB), "| DFA states:", len(INDEX))
for st in ['', '{"label": "', '{"label": "pos", "score": ']:
toks = sorted(VOCAB[t] for t in INDEX[st])
print(f"state {st!r:34} allows {len(toks):2d} tokens: {toks}")
# Two different token sequences that spell the same string
a = ['{"', 'label', '": "', 'pos', '", "', 'score', '": ', '7', '}']
b = ['{"', 'label"', ': "pos', '", "', 'score', '": ', '7', '}']
for name, seq in (("a", a), ("b", b)):
st = ''
for t in seq:
st = advance(st, t)
if st is None: break
print(name, "->", "dead" if st is None else st, "| accepted:", st in ACCEPT)vocabulary size: 39 | DFA states: 115
state '' allows 2 tokens: ['{', '{"']
state '{"label": "' allows 4 tokens: ['neg', 'neu', 'pos', 'pos"']
state '{"label": "pos", "score": ' allows 10 tokens: ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
a -> {"label": "pos", "score": 7} | accepted: True
b -> {"label": "pos", "score": 7} | accepted: TrueAt the start state only { and {" are legal, so 37 of the 39 tokens are masked before any sampling happens. After {"label": " the legal tokens are the three label names plus pos", a token that straddles the label and the closing quote. After "score": exactly the ten digits are legal, and the two-character token 10 present in the vocabulary is masked because its second character would leave the language.
The last two lines show a subtlety. The string {"label": "pos", "score": 7} can be spelled by different token sequences, and both are accepted. A mask built from characters therefore permits tokenizations that the tokenizer would never produce for that string. The model may have seen non-canonical segmentations rarely, so forcing one can place it in a region where its predictions are poorer. Implementations that match characters rather than canonical tokenizations accept this risk; whether it matters is an empirical question for the model and format at hand.
From JSON Schema to a constraint
JSON Schema is the common way to describe the structure of a JSON document. The JSON Schema validation vocabulary defines keywords such as required, enum, minimum and additionalProperties. A schema compiler turns these into a grammar: a fixed object skeleton with keys in a set order, enum as an alternation of literals, a bounded integer as a restricted digit pattern. Constraints that need counting or comparison across fields (the sum of line items must equal the total) are not regular or context-free in a useful way and fall outside what masking can enforce.
Hosted services support a subset of the schema language. OpenAI’s Structured Outputs documentation describes a JSON Schema subset in which every field must be listed as required and additionalProperties must be false, and it separates the mode from plain JSON mode, which only guarantees syntactically valid JSON. The same documentation lists cases where a schema-conforming response does not appear: a model refusal is reported in a separate field, and a response that reaches the maximum token limit is incomplete. These details are specific to one provider and can change, but the lesson transfers: a guarantee holds for completed generations inside the supported schema subset, and the application still needs handling for refusal and truncation.
Truncation is easy to reproduce. The harness at the end of this article runs the constrained decoder with a limit of 12 tokens, while complete outputs in the stub take between 9 and about 19 steps, counting the end-of-sequence token, depending on how the text is segmented. Many generations stop before the closing brace, and the result is not schema-valid even though every token chosen was legal.
What masking does to the distribution
Masking removes invalid tokens at each step but does not look ahead. A token can be a legal prefix and still lead to a state in which the model assigns almost all of its probability to forbidden continuations. Renormalizing at that state hands the leftover probability to whatever is legal, however unlikely the model found it. Park et al. analyze this effect for grammar-constrained decoding and propose an alternative that samples in proportion to the model’s probabilities conditioned on grammatical validity. The following example computes both distributions exactly on a tiny model.
# Tokens: a, b (first position); x, y, z (second position). Valid strings: ax, bx, by.
first = {"a": 0.6, "b": 0.4}
second = {
"a": {"x": 0.01, "y": 0.00, "z": 0.99}, # after "a" the model expects z, which the grammar forbids
"b": {"x": 0.50, "y": 0.50, "z": 0.00},
}
valid = {"ax", "bx", "by"}
# 1. The model's own distribution restricted to valid strings (the conditional p(s | s is valid)).
joint = {f + s: first[f] * second[f][s] for f in first for s in "xyz"}
mass = sum(joint[s] for s in valid)
conditional = {s: joint[s] / mass for s in sorted(valid)}
# 2. Token masking: at each step keep only tokens that can still lead to a valid string, renormalize.
legal_next = {"": {"a", "b"}, "a": {"x"}, "b": {"x", "y"}}
def masked_step(dist, legal):
z = sum(p for t, p in dist.items() if t in legal)
return {t: p / z for t, p in dist.items() if t in legal}
masked = {}
m1 = masked_step(first, legal_next[""])
for f, p1 in m1.items():
for s, p2 in masked_step(second[f], legal_next[f]).items():
masked[f + s] = p1 * p2
print(f"model probability of any valid string: {mass:.3f}")
print(f"{'string':>6} {'model joint':>12} {'p(s | valid)':>13} {'token masking':>14}")
for s in sorted(valid):
print(f"{s:>6} {joint[s]:>12.4f} {conditional[s]:>13.4f} {masked[s]:>14.4f}")model probability of any valid string: 0.406
string model joint p(s | valid) token masking
ax 0.0060 0.0148 0.6000
bx 0.2000 0.4926 0.2000
by 0.2000 0.4926 0.2000The model’s first token is a with probability 0.6. After a, though, the model expects the token z, which the grammar forbids; the legal continuation x holds only 0.01 of the mass. The probability that the model assigns to the string ax is 0.6 × 0.01 = 0.006, and among valid strings that is 1.5% (column “p(s | valid)”). Token masking sees only that a is a legal first token, keeps 0.6 for it, and then renormalizes the single legal continuation to probability 1. The string ax comes out 60% of the time, forty times more often than the model’s own preferences among valid outputs imply (0.6 versus 0.0148).
The practical reading: constrained decoding guarantees the output is in the language, and it can shift which in-language outputs appear. The shift is largest when the schema forces the model through prefixes it considers unlikely, for example a required key that the model would not have written first, or an enum that does not contain the model’s natural answer. Schema design is part of decoding design, and the evaluation harness at the end of this article is how to see whether the shift costs accuracy.
Constraints and reasoning quality
Tam et al. report that requiring structured formats such as JSON or XML can reduce LLM performance on reasoning tasks, with stricter formats associated with larger drops. The mechanism most relevant to engineers follows from the product rule at the start of this article: tokens are generated left to right, and each token conditions the rest. If a schema places the field "answer" before any field in which the model can write its reasoning, the answer is produced with no intermediate computation in the text. Placing a free-text "reasoning" or "evidence" field before "answer" restores room to think. The schema is also where a fabrication risk enters: a required field with a closed set of values forces the model to emit something when the input does not contain the information. Allow an explicit null or "unknown" value, and make the application treat it as a valid outcome.
Alternatives and their guarantees
Constrained decoding is one of several ways to get structured output. They differ in what they guarantee and in what a failure looks like.
| Approach | What it guarantees | Typical failure | Cost |
|---|---|---|---|
| Prompt only, then parse | Nothing; the output is whatever the model samples | Prose around the JSON, unclosed brackets, wrong key names | No extra cost; failures surface in the client |
| Syntax-only JSON mode | Output parses as JSON (per the provider’s description) | Valid JSON with missing keys, wrong types, invented keys | Small |
| Schema-constrained decoding | Completed output conforms to the supported schema subset | Refusal, truncation at the token limit, valid but wrong values | Mask computation and schema compilation; restricted schema features |
| Validate and retry or repair | Output that is eventually accepted by your validator | Repeated identical failure on hard inputs; retry cost and latency | Extra generations on every failure |
| Fine-tuning on the target format | Higher probability of the format, no guarantee | Rare format breaks that remain at scale | Training data and training cost |
Retrying works when failures are independent between attempts. If one attempt is valid with probability \(v=0.9\) and attempts are independent, three attempts fail all together with probability \(0.1^{3}=0.001\). Failures are rarely independent: the same hard input tends to fail the same way each time, so the true failure rate is higher than the independent calculation, and measuring it on real inputs is the only way to know. Retrying also costs latency and tokens, which a masking decoder avoids. The surrounding engineering (request contracts, timeouts, retry policy) belongs to Integrating Model APIs: Retries, Schemas, and Failure Handling, which builds on the validity levels discussed next.
Schema validity versus semantic correctness
A structured output can be right at several different levels, and each level needs its own check:
- Syntax: the text parses as JSON.
- Schema: required keys are present, types and enums match, no extra keys.
- Internal consistency: values agree with each other, such as line items that sum to the total.
- Grounding: values come from the input, such as a date that actually appears in the source document.
- Correctness: the value matches the truth, including cases that no check on the text alone can verify.
Constrained decoding addresses levels 1 and 2. Levels 3 to 5 depend on what the model understood, and masking does nothing for them. The next program applies the first four levels to five candidate outputs for a hypothetical invoice-extraction task. The source text and the candidates are synthetic and written for this example.
import json, re
SOURCE = """Invoice INV-2041, issued 2024-03-09 to Northwind Traders.
Widget x4 @ 12.50 = 50.00
Gasket x10 @ 1.20 = 12.00
Total due: 62.00 EUR"""
SCHEMA = {
"required": ["invoice_id", "issue_date", "lines", "total", "currency"],
"types": {"invoice_id": str, "issue_date": str, "lines": list, "total": (int, float), "currency": str},
"enum": {"currency": {"EUR", "USD", "GBP"}},
}
def check_schema(obj):
errs = []
if not isinstance(obj, dict):
return ["not an object"]
for k in SCHEMA["required"]:
if k not in obj: errs.append(f"missing {k}")
for k in obj:
if k not in SCHEMA["types"]: errs.append(f"unexpected key {k}")
for k, t in SCHEMA["types"].items():
if k in obj and not isinstance(obj[k], t): errs.append(f"{k} has wrong type")
for k, allowed in SCHEMA["enum"].items():
if k in obj and obj[k] not in allowed: errs.append(f"{k} not in enum")
return errs
def check_semantics(obj, source):
errs = []
lines = obj["lines"]
line_sum = round(sum(l["qty"] * l["unit_price"] for l in lines), 2)
if abs(line_sum - obj["total"]) > 0.005: errs.append(f"total {obj['total']} != line sum {line_sum}")
if obj["invoice_id"] not in source: errs.append("invoice_id not found in source")
if obj["issue_date"] not in source: errs.append("issue_date not found in source")
return errs
candidates = {
"A correct": '{"invoice_id": "INV-2041", "issue_date": "2024-03-09", "lines": [{"qty": 4, "unit_price": 12.5}, {"qty": 10, "unit_price": 1.2}], "total": 62.0, "currency": "EUR"}',
"B wrong total": '{"invoice_id": "INV-2041", "issue_date": "2024-03-09", "lines": [{"qty": 4, "unit_price": 12.5}, {"qty": 10, "unit_price": 1.2}], "total": 50.0, "currency": "EUR"}',
"C invented date": '{"invoice_id": "INV-2041", "issue_date": "2024-03-01", "lines": [{"qty": 4, "unit_price": 12.5}, {"qty": 10, "unit_price": 1.2}], "total": 62.0, "currency": "EUR"}',
"D bad enum": '{"invoice_id": "INV-2041", "issue_date": "2024-03-09", "lines": [], "total": 0, "currency": "euro"}',
"E trailing comma": '{"invoice_id": "INV-2041", "issue_date": "2024-03-09", "lines": [], "total": 0, "currency": "EUR",}',
}
for name, text in candidates.items():
try:
obj = json.loads(text)
except ValueError as e:
print(f"{name:17} syntax: FAIL ({e.__class__.__name__})"); continue
s = check_schema(obj)
if s:
print(f"{name:17} syntax: ok | schema: FAIL {s}"); continue
m = check_semantics(obj, SOURCE)
print(f"{name:17} syntax: ok | schema: ok | semantics: {'ok' if not m else 'FAIL ' + str(m)}")A correct syntax: ok | schema: ok | semantics: ok
B wrong total syntax: ok | schema: ok | semantics: FAIL ['total 50.0 != line sum 62.0']
C invented date syntax: ok | schema: ok | semantics: FAIL ['issue_date not found in source']
D bad enum syntax: ok | schema: FAIL ['currency not in enum']
E trailing comma syntax: FAIL (JSONDecodeError)Candidate A passes every level. Candidate E fails at syntax because of the trailing comma, and candidate D fails at schema because "euro" is not in the currency enum; a constrained decoder would have prevented both. Candidates B and C are the dangerous ones: they parse, match the schema, and would pass a type-checking client. In B the total is 50.00 although the line items sum to 62.00, so the model copied a partial figure. In C the date 2024-03-01 does not appear in the source, which is a fabricated value. Only the semantic checks catch them, and only because this task offers redundancy to check against (line items versus total, value versus source text). Level 5 has no such shortcut. Nothing in the text of candidate A proves that the invoice was read correctly; that needs labeled examples, which is what evaluation provides.
The semantic checks have their own failure modes. The substring test for the date flags “March 9, 2024” in the source as missing if the model normalizes it to ISO format, so grounding checks usually compare normalized values. The consistency check depends on rounding rules. Validators are code and need tests like any other code.
Strict validity can also hide uncertainty. A free-form model that cannot find a currency may write “unknown”, producing a visible failure. A constrained model with a closed enum must pick one of the allowed values, and the failure becomes a plausible wrong answer that passes validation. The more completely a decoder enforces the schema, the more the remaining errors look like valid data, so monitoring has to shift from “did it parse” to “is it right”.
Evaluating decoding configurations
A decoding configuration (greedy or sampled, temperature, truncation, constrained or not, token limit) is a design choice that should be evaluated like one. The measurements need to separate the levels above, because one aggregate “accuracy” mixes parse failures with wrong answers and hides which lever to pull.
The unit of analysis is the input, not the sample. Several samples for the same input are correlated, so ten samples for each of 300 inputs are not 3,000 independent observations. Compute a rate per input, average across inputs, and estimate uncertainty by resampling inputs (a bootstrap over inputs). For deterministic settings one run per input suffices, but the interval still reflects which inputs were in the set.
Report these rates side by side: share of outputs that parse, share that satisfy the schema, share that are exactly correct, and field-level correctness. Report rates over all inputs, not only over valid outputs. A rate conditioned on validity reflects which outputs survived, and configurations with different validity rates are then not comparable.
The harness below runs seven configurations on 300 synthetic inputs, ten samples per input for sampled configurations. The generation loop that it uses is shown first. It calls the stub model for logits, applies the optional mask from the index built earlier, and either takes the argmax (T == 0) or samples. The stub gives the correct tokens a large logit bonus, adds seeded Gaussian noise, gives a prefix such as “Sure” a probability of opening the response, and for some inputs “believes” a wrong label or score with a reduced residual logit on the correct one. None of those choices describes a real model.
def generate(doc, T, rng, constrained, max_tokens=24):
text, state = "", ""
for _ in range(max_tokens):
z = stub_logits(doc, text)
allowed = INDEX[state] if constrained else None
if T == 0:
cand = allowed if allowed is not None else range(len(z))
tid = max(cand, key=lambda i: z[i])
else:
tid = sample_step(z, T, rng, allowed)
if tid == EOS:
return text, True
text += VOCAB[tid]
if constrained:
state = INDEX[state][tid]
return text, False # ran out of tokens without EOSimport random
from stub_model import *
DOCS = make_docs(300)
K = 10 # samples per document for T > 0
def run(T, constrained, max_tokens=24, seed=0):
rng = random.Random(seed)
k = 1 if T == 0 else K
per_doc = []
for d in DOCS:
rows = [score_output(d, *generate(d, T, rng, constrained, max_tokens)) for _ in range(k)]
per_doc.append([sum(r[j] for r in rows) / k for j in range(4)])
return per_doc
def mean_ci(vals, B=1000, seed=5):
rng = random.Random(seed)
n = len(vals)
ms = sorted(sum(rng.choice(vals) for _ in range(n)) / n for _ in range(B))
return sum(vals) / n, ms[int(0.025 * B)], ms[int(0.975 * B) - 1]
configs = [("greedy", 0, False), ("T=0.7", 0.7, False), ("T=1.0", 1.0, False), ("T=1.5", 1.5, False),
("T=1.0 constrained", 1.0, True), ("T=1.5 constrained", 1.5, True),
("T=1.0 constrained, max 12 tokens", 1.0, True, 12)]
print(f"{'config':34} {'schema-valid':>13} {'label|valid':>12} {'exact match':>12} exact 95% CI")
for c in configs:
name, T, con = c[:3]
mt = c[3] if len(c) > 3 else 24
pd = run(T, con, mt)
v, lo, hi = mean_ci([r[1] for r in pd]); l = sum(r[2] for r in pd) / max(sum(r[1] for r in pd), 1e-9)
e, elo, ehi = mean_ci([r[3] for r in pd])
print(f"{name:34} {v:>13.3f} {l:>12.3f} {e:>12.3f} [{elo:.3f}, {ehi:.3f}]")config schema-valid label|valid exact match exact 95% CI
greedy 0.983 0.858 0.617 [0.563, 0.670]
T=0.7 0.884 0.872 0.568 [0.518, 0.618]
T=1.0 0.625 0.871 0.367 [0.331, 0.403]
T=1.5 0.120 0.894 0.024 [0.018, 0.030]
T=1.0 constrained 1.000 0.890 0.693 [0.649, 0.739]
T=1.5 constrained 1.000 0.886 0.659 [0.620, 0.700]
T=1.0 constrained, max 12 tokens 0.165 0.941 0.121 [0.103, 0.137]In the table, label|valid is label accuracy among schema-valid outputs only, and the other columns are rates over all inputs. Reading it row by row, with the caveat that it describes the stub:
- Unconstrained decoding gets less reliable as temperature rises. Schema-valid output is 0.983 at greedy, 0.884 at \(T=0.7\), 0.625 at \(T=1.0\) and 0.120 at \(T=1.5\). The stub’s noise accumulates across the roughly twelve to eighteen tokens of an output, so each small per-step deviation chance compounds, the same arithmetic as the 200-token example earlier. All five greedy failures have the same form: a complete valid object followed by extra text, which is a parse failure for a client that expects exactly one object.
- Constrained decoding gives schema-valid rate 1.000 at both temperatures, as it must. Exact match is 0.693 at \(T=1.0\) and 0.659 at \(T=1.5\); the intervals [0.649, 0.739] and [0.620, 0.700] overlap, so the data do not separate the two. What the temperature costs here is the gap between 1.000 validity and exactness: the format is always right and the content is right two-thirds of the time.
- Constrained sampling at \(T=1.0\) beats unconstrained greedy on exact match (0.693 versus 0.617) with non-overlapping intervals. In this stub that is partly because greedy always follows a wrong belief while sampling sometimes picks the correct label from the residual probability, and partly because greedy sometimes emits trailing text. It is a property of the stub’s construction and should not be read as evidence about real models, where the opposite ordering is just as possible.
- The last row restricts the constrained decoder to 12 tokens. Schema-valid drops to 0.165. The mask guarantees every token is legal, not that the output finishes. The label accuracy among valid outputs rises to 0.941 only because the outputs that finished within 12 tokens are a selected subset, which is the reason to report rates over all inputs.
An evaluation set for a real system should come from the real input distribution, include the hard cases that fail the semantic checks, and record the decoding parameters, model version and schema version with every result. Provider-side changes to default sampling parameters, supported schema features or model versions can alter all of these numbers without any change in your code, so the evaluation needs to be rerunnable. Building and maintaining such test sets is the subject of Evaluating AI Applications with Reproducible Test Sets. When correctness cannot be checked with code, a model-based grader can stand in for part of the check, with its own error rate to be measured (see LLM-as-a-Judge).
Cost belongs in the comparison as well. Constrained decoding adds mask computation per step (small when the index is precomputed, larger for grammars that need a stack), and a schema compiled for the first time may add latency before the first token. Retries add whole extra generations. Measure median and tail latency and tokens per successful output, not only quality.
| Symptom | Likely cause | Where to look |
|---|---|---|
| Output fails to parse after a few percent of requests | Sampling tail tokens, trailing text, truncation at the token limit | Parse rate by temperature; finish reason; output length distribution |
| Output parses but fails the schema | Prompt-only or syntax-only mode; schema drift between prompt and validator | Schema version used by prompt, decoder and validator |
| Output always matches the schema but accuracy is low | Constraint forces unlikely prefixes, closed enum without an unknown value, answer field before reasoning | Field order, enum design, accuracy by field |
| Results change between identical runs at greedy settings | Numerical nondeterminism, provider-side model or serving change | Repeat runs on a fixed set; logged model and parameter versions |
| Constrained and unconstrained results disagree sharply | Distribution shift caused by masking, non-canonical tokenization | Compare field accuracy per configuration on the same inputs |
References
- Holtzman, Buys, Du, Forbes, Choi. The Curious Case of Neural Text Degeneration (nucleus sampling)
- Willard, Louf. Efficient Guided Generation for Large Language Models
- Geng, Josifoski, Peyrard, West. Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning
- Park, Wang, Berg-Kirkpatrick, Polikarpova, D’Antoni. Grammar-Aligned Decoding
- Tam, Wu, Tsai, Lin, Lee, Chen. Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models
- OpenAI API documentation: Structured Outputs
- JSON Schema Validation: A Vocabulary for Structural Validation of JSON (2020-12)
Discover more from Insightful Data Lab
Subscribe to get the latest posts sent to your email.