Constrained Decoding: Using Automata to Set Illegal Token Probabilities to Zero

If you write "only return JSON" in the prompt, even if it's bolded, capitalized, or repeated three times, the model will still produce malformed output in a large number of calls. The reason is that prompts can only change the model's probability distribution; they cannot delete any candidates. As long as some illegal token sequence retains even a tiny probability in the distribution, as sampling occurs many times, it will eventually be selected. Suppose the probability of a valid output is already as high as 99.9%, then in one million calls, it is still expected that about one thousand will produce malformed output; this is the mathematical root cause of why formatting errors cannot be eradicated by prompting alone.

Constrained decoding changes where errors are eliminated: it no longer tries to make the model "more obedient", but directly intervenes at the sampler level. Its input consists of three things: the logits (unnormalized log scores) that the model gives for the next token, the sequence prefix generated so far, and a set of formal rules (usually a grammar or JSON schema). The output is a sequence sampled from the distribution as usual, but this sequence can only be composed of tokens that are legal at each step. Specifically, at each step, the probabilities of candidate tokens that violate the formal rules are set to zero, then the remaining candidates are renormalized, and sampling is performed from this trimmed distribution. Illegal tokens are therefore mechanistically impossible to select: it is not that "the model has learned not to select them", but rather those candidates no longer exist.

The guarantee boundary obtained from this is very clear: constrained decoding guarantees that the output belongs to a certain formal language—the result is always valid JSON and always conforms to the shape of the given schema. It does not guarantee that field values are truthful, that the business relationships between fields hold, or that the caller has the authority to perform the action described by the output. Formal correctness and content trustworthiness are two different things.

This characteristic determines its applicable scenarios: in locations such as tool call arguments, batch information extraction, and database interfaces, the output must be parsed by downstream programs, formal correctness is a hard prerequisite, and constrained decoding has the greatest value. Conversely, if free-form writing content forcibly applies a complex schema, it will sacrifice expressive flexibility, and masking and renormalization at each step will increase latency, resulting in a text that is structurally valid but whose content still requires human judgment.

A practical layered boundary is: constrained decoding is responsible for form; business validation is responsible for relationships between fields; authentication and transaction control are responsible for the consequences of actions. The three layers each have their own roles, and no layer can replace the other two.

At any moment the generation process sees only a prefix; it neither knows what will be generated in the future nor can it inspect the entire output at once. To determine whether the next token is legal, the rules must be compiled in advance into a parsing state that can advance step by step with the prefix.

What the compilation stage does is translate constraint sources into automata. JSON Schema corresponds to a deterministic finite automaton (DFA), context-free grammars correspond to pushdown automata (PDA), and regular expressions are likewise compiled into DFAs; it is also possible to directly construct an equivalent parsing state. This parsing state records the structural information of the current position: where in the object it currently is, whether it is currently inside an array, a string, or a number, which required fields have already appeared, and what is allowed to appear next. The runtime behavior of the whole system is: each time a complete token byte string is accepted, it advances the state once; the state machine then returns the new state and the batch of tokens that are legal from that state. When generation ends, only prefixes in an accepting state may be allowed to terminate normally.

To turn JSON Schema into such a state machine, each of its constraints must be mapped to grammar structures: type determines which kinds of values are allowed at the current position; enum becomes a set of allowed literals; required turns whether object fields have appeared into a state that must be tracked; additionalProperties determines whether unknown fields are rejected or allowed; an array's minItems and maxItems become counter lower and upper bounds; nested references ($ref and $defs) recursively embed sub-schemas into the state. However, not every implementation supports all keywords, and the compilation support table is a practical boundary. Remote references, overly complex regular expressions, and semantic constraints that cannot be expressed syntactically at the format level (such as a string having to be exactly a valid date or email address) usually can only be checked after generation.

Different constraint sources have different expressive strengths and weaknesses. Regular expressions are best at expressing local string shapes but cannot express arbitrary nesting structures and cross-field relationships. JSON Schema is good at describing objects, types, enums, and required fields but cannot express facts such as “this record exists in the database” or “the caller has this permission.” Context-free grammars can describe recursive syntax and code structure but cannot express variable semantics and runtime results. Custom state machines can characterize protocols and finite flows but cannot express open-world facts. Therefore, state compilation addresses the judgment of “structurally legal”; any constraint beyond the expressive power of formal languages must be handed to post-generation business validation.

Setting an illegal token's probability to zero is not simply "throwing away" probability and being done. The original model's distribution sums to 1; after directly deleting a batch of candidates, the sum of the remaining candidates' probabilities is less than 1 and is no longer a valid probability distribution. Therefore the standard constrained sampling process has two steps: first mask on the legal set, then renormalize on the legal set. The output is a new distribution: illegal items have probability exactly 0, and legal items' probabilities sum to exactly 1 again.

This process can be written exactly as a formula. Let P(t|s) be the original probability that the model assigns to token t in parsing state s, and let M(s) be the set of tokens from state s that can still lead to a complete legal result. The constrained sampling probability is then:

P′(t|s) = P(t|s) × 1[t ∈ M(s)] ÷ Σ_{u∈V} P(u|s) × 1[u ∈ M(s)]

Here 1[·] is the indicator function: it is 1 when the condition holds and 0 otherwise; u ranges over all candidates in the vocabulary; the denominator is the sum of the probability mass of the remaining legal candidates and serves to perform normalization. When an illegal token is substituted in, the indicator function is 0, so the numerator as a whole is 0; when a legal token is substituted in, it receives its original probability divided by the total probability mass of the legal set, so the sum over the legal set returns to exactly 1. The degenerate case where the denominator is zero is discussed separately later.

It is worth emphasizing that this transformation changes the shape of the distribution, not the model's capabilities. The constraint mechanism does not know the task answer; it only removes options that do not conform to the grammar. When the high-probability candidates the original model most wants to output happen to be all illegal tokens, the model is forced to choose among low-probability legal candidates. In that case, although the format is guaranteed to be correct, the content quality may deteriorate noticeably. This is precisely the mathematical expression of "structural legality does not equal content reliability."

The sampling order also affects the result. The correct order is to first obtain the logits, then apply the grammar mask, and then sample over the legal set; temperature, top-k, and top-p truncation operations have semantic differences depending on the step at which they occur. If top-k is applied first and the truncation happens to delete all legal tokens, then no legal candidate remains in the remaining distribution, constituting an erroneous dead end. Therefore implementations must clearly specify and test the processing order they use.

Finally, there is the case of an empty candidate set. If M(s) is empty in a certain state, it should not be treated as an occasional fluctuation that can be recovered by "trying again." It usually means there is an incompatibility among the schema, the tokenizer, the current prefix, or the truncation order, and the system should return a diagnosable failure state, exposing the conflict instead of silently retrying.

Use a concrete single-step decision to see how the constraint decoder rewrites the distribution. Assume the current prefix is {"action": , and the JSON state machine has advanced to state q₃, which is “currently generating the enumeration value for the action field”. The model's raw preferences for the next token are as follows: delete probability 0.50, refund probability 0.30, ask probability 0.15, and the remaining 0.05 is spread across other candidates. The schema specifies that the action field only allows the two enumeration values refund or ask.

The constraint decoder first checks each candidate against the grammar. delete is not in the enumeration, so the indicator function returns 0, and its 0.50 probability mass is directly set to zero. The legal candidates are refund and ask; their raw probabilities total 0.30 + 0.15 = 0.45, and this 0.45 becomes the denominator for renormalization. Thus the constrained probability of refund is 0.30 ÷ 0.45 = 0.667, and the constrained probability of ask is 0.15 ÷ 0.45 = 0.333; the two sum exactly to 1. The model's originally most preferred delete completely disappears from the samplable set, and sampling can only land on refund or ask. This is an intuitive demonstration that constrained decoding changes the samplable set rather than the model's preferences.

At the same time, it must be clear what this result guarantees and does not guarantee. The constraint decoder only proves that “the action name belongs to the enumeration allowed by the schema”; it does not discuss at all whether it is safe from a business perspective: refund still requires external systems to verify refund eligibility, whether the refund amount is correct, and whether the caller is authorized to execute it; ask still requires confirmation that the question posed is necessary and is not soliciting excessive privacy information. In the table, the “business safety” column is in an undiscussed state for delete, refund, and ask. In other words, constrained decoding blocks delete at the door, but it may still let the model output refund to an unqualified caller. The gap between structural validity and action safety must be filled by post-generation business validation and permission control.

Grammar rules are written at the character level—quotes, commas, enum values, Unicode characters—but models sample token by token, and there is no one-to-one mapping between tokens and characters. Therefore a common mistaken implementation is to filter candidates by checking “whether the first character of the next token is legal.” This necessarily goes wrong, because token boundaries and character boundaries do not coincide.

A token may contain an opening quote plus a string of characters, or even swallow multiple syntactic units at once such as a quote, field name, and comma; Unicode characters may span multiple bytes; escape sequences in turn change the relationship between surface text and underlying bytes. The truly reliable test is: take the complete byte string of the candidate token, run it starting from the current parsing state, and see whether after the run it lands in a state from which it can still continue and eventually reaches an accepting state. The object of judgment is the entire token, not its first character.

This difference shows up directly with enum constraints. The enum value refund may happen to be split into one token, or it may be split into two tokens: ref and und. When the state machine expects to generate refund, a prefix token such as ref has not formed a complete enum value, but it is a prefix of a legal enum and must be allowed; the next step then verifies und. Conversely, a token that starts with r on the surface but cannot complete a legal enum through any subsequent combination should be masked no matter how correct its first character appears.

This judgment depends on the target model's actual tokenizer. Different vocabularies will split the same string into different token sequences; therefore both the compilation stage and the testing stage must use the tokenizer used in actual deployment. After changing the model or tokenizer, if you continue to reuse the old mask cache, you will apply the legal set computed for the old vocabulary to the new vocabulary: the result will either block paths that should be legal or allow candidates that should be rejected. Recompiling after changing the tokenizer is not an optimization but a prerequisite for correctness.

Constrained decoding performance is not constant. The more complex the schema structure, the more states are compiled, and the greater the cost of computing the legal token set at each step; decoding slows down and jitter becomes more noticeable. To govern complexity, the inputs to focus on are schema structure, tokenizer, and resource limits; the outputs are the number of compiled states, per-step masking cost, and the reason when rejection occurs.

Specifically, large enumerations, deep recursion, intersecting branches of oneOf/anyOf, and complex regular expressions all simultaneously increase compilation time and state space, and add to the computation of legal tokens at each step. The compiled artifacts can be cached, but the cache key must include both the schema hash and the tokenizer version — caching by schema hash alone will reuse artifacts built for the old vocabulary after changing tokenizers, thereby blocking valid paths or admitting incorrect candidates. In addition to caching, upper limits must be set: schema size, recursion depth, array length, and string length all need to be limited; otherwise a malicious or runaway schema can exhaust compilation resources.

In practice, there is a clear correspondence between symptoms and causes. If the first token is very slow, it is usually caused by the initial grammar compilation, which can be resolved with precompilation and versioned caching. If every token is slow, it indicates that legal token set computation is too complex; you need to simplify branches and cache states. Empty candidates often arise because the implementation does not support a certain schema feature or the prefix conflicts with the grammar; you should run compatibility tests and return an explicit failure. Unbounded output length occurs because no upper limits were set for arrays and strings; you need to cap it with dual limits from schema boundaries plus total token count.

Beyond these measures, the most effective governance is often to make the schema itself smaller. A minimal schema lets the model generate only the fields that truly require its judgment, with the server side filling in default values and derived fields. With fewer fields, the state space and per-step masking cost both decrease, and such configurations are usually more stable.

One tempting aspect of constrained decoding is that the prefix generated at each step is guaranteed to be extendable to a valid result, which makes it seem possible to use the output while generating it. But if you treat “the current prefix is valid” as “the object is already complete,” you will execute actions at the wrong time. The string is still continuing, the number may not yet be fully written, and the array can have elements appended at any time. A valid prefix only means there is a path to continue; it does not mean the object is closed. Network interruption makes the problem worse: the stream breaks in the middle, leaving half an object rather than a complete parseable value.

Therefore the submission boundary must be tightened. The client can display streaming progress during generation, letting users see content taking shape gradually; but tool parameters should be committed atomically only after all three conditions are satisfied: the state machine reaches an accepting state, schema validation passes, and business validation passes. If any of the three is missing, no action may be executed.

After a stream interruption, you must also distinguish among cancellation, timeout, and normal completion, handling each separately rather than treating them all alike. A particularly prohibited practice is automatically filling in truncated JSON and then executing it. The model does not know what the truncated half of the value was originally intended to be, and the content completed by the server may differ from the original intent; for an action involving funds, guessing half a value wrong can cause real loss.

The boundary for retries lies in the idempotency key. A call may have already succeeded on the server, with only the response lost on the return path; if the client resends the identical request because it did not receive the response, duplicate execution can occur, for example the same refund being processed twice. Therefore retries must reuse the idempotency key so that the server can recognize that this is the same operation and refuse to execute it again.

Finally, clarify the scope of the constraint: it only restricts the model's own output. Malicious content in the schema description text, retrieval results, and tool return values—these external inputs do not pass through decoding constraints and remain untrusted input. Sensitive free-text fields need separate content inspection and injection isolation. You must not relax protection against external text just because the overall output is valid JSON.

After JSON validity reaches 100%, a natural misconception is that evaluation is complete. But constrained decoding only guarantees the syntax layer; what teams truly need are layered metrics: send generated results sequentially through a parser, schema validation, authoritative fact-checking, subject permission checks, and tool feedback, recording pass rates separately for each layer. Syntax validity rate, schema pass rate, dead-end rate, additional TTFT (time to first token latency) and TPOT (time per output token latency), business validation pass rate, factual correctness rate, tool success rate, unauthorized access interception rate, and final task quality—these numbers must be kept separately. Reporting only parse success rate will make a system that is “format all correct, content all wrong” appear perfect, because failures in any subsequent checkpoint are not compensated by format validity rate.

The specific division of labor in layered validation is clear. The parser only validates syntactic correctness and complete termination; schema validation checks fields, types, enums, and ranges; deterministic rules validate amounts, dates, and cross-field invariants; the database or evidence layer verifies entity existence and factual truth; the execution layer re-authenticates based on the current subject before the action actually occurs and limits side effects. High-risk actions must additionally verify that idempotency and unauthorized access interception actually take effect. If any layer fails, it should return a structured failure reason, then perform a limited number of retries or hand off to a human, rather than silently swallowing the failure.

Evaluation use cases also need layered design. Adversarial regression sets should cover Unicode and escaping, extremely deep nesting, empty arrays, long enums, streaming disconnections, and keywords not supported by the implementation. These use cases strike different layers respectively: disconnection tests exercise submission boundaries, unsupported keywords test compilation compatibility, long enums and deep nesting test state size and performance, and empty arrays test upper bounds. Only by measuring each layer separately can we know whether the other layers have collapsed behind a perfect format score.

By linking the previous parts in causal order, we can obtain a practical chain that starts from the problem and ends verifiably.

The starting point is the nature of the problem: prompts can only change the probability distribution, not delete any candidate, so format errors inevitably appear periodically in large-scale calls. Constrained decoding moves the intervention point to the sampler level, using formal rules to prune the candidate set, thereby upgrading “output belongs to a formal language” from a probabilistic guarantee to a mechanistic guarantee. This is the first causal step: why errors occur determines where the intervention must happen.

The second step is how rules enter the model. Compile the minimal schema into a tokenizer-aware state machine—tokenizer-aware because the unit of judgment is the complete token byte string, not characters. The compiled artifact records parsing states; the state preserves structural information about the current position and what is allowed next. This is one link in “rules becoming runtime state.”

The third step is the per-token runtime loop: at each step, compute the legal token set under the current state, set the probabilities of illegal candidates to zero, then renormalize over the legal candidates and sample. Renormalization is the key to correctness—after removing candidates, the sum of remaining mass is less than 1; you must divide by the legal mass to restore a distribution summing to 1.

The fourth step is the commit boundary: a valid prefix does not mean the object is complete. Only in an accepting state, and after both schema and business validation pass, do we atomically commit the complete object and execute the action. This step turns the mechanistic guarantee into protection for real actions.

The fifth step is the validation layer: schema, business, facts, and permissions are evaluated and validated separately; failure in any layer is not compensated by format validity rate. The sixth step is closing the loop: record metrics such as dead-end rate, perform limited recovery from failures, and continuously run regression with adversarial cases.

Every connection in the whole chain corresponds to a clear division of labor: compilation is responsible for the correctness premise, masking and renormalization for the mechanistic guarantee, accepting-state commit for the execution boundary, layered validation for content and safety, and regression for long-term stability. If any link is omitted, the guarantees of the remaining links lose their meaning.