Constrained Decoding

The core mechanism involves directly manipulating the raw logit scores (unnormalized predictions) before the softmax function. At each generation step, a logit bias is added to the scores of allowed tokens, making them overwhelmingly likely, while a large negative bias (effectively -infinity) is applied to disallowed tokens. This token masking ensures the model's probability distribution is zeroed out for invalid continuations, forcing selection strictly within the permitted set.

This technique guarantees that generated output conforms to a specified context-free grammar (CFG) or formal schema, such as JSON Schema. A parser state is maintained during generation, and only tokens that represent valid continuations according to the grammar's production rules are unmasked. This is the definitive method for ensuring syntactically valid JSON, XML, or custom data formats, eliminating malformed structural errors entirely.

A simpler form of constrained decoding limits the model's output to a predefined closed vocabulary or a list of valid strings. Common applications include:

• Classification: Forcing the next token to be one of a set of class labels (e.g., ["positive", "negative", "neutral"]).
• Entity Linking: Restricting generation to only entities present in a provided knowledge base or catalog.
• Code Generation: Limiting function calls to a specific, pre-approved API list.

Unlike prompt-based formatting requests, which are probabilistic and prone to hallucination, constrained decoding provides a deterministic guarantee of structural integrity. By operating at the token-sampling level, it bypasses the model's linguistic reasoning entirely for syntax decisions. This is critical for machine-to-machine communication where a single misplaced bracket or invalid key can crash a downstream parser, making it a foundational component of reliable tool calling and API execution.

A flexible implementation method uses regular expressions to define valid token sequences. At each step, a finite-state automaton derived from the regex determines the set of valid next tokens. This allows for complex pattern constraints like enforcing date formats (YYYY-MM-DD), specific identifier patterns, or sanitizing outputs to exclude profanity. Libraries like Outlines and Guidance use this approach to interleave free-text generation with strictly controlled slots.

Applying a token mask requires computing the valid set at every generation step, which introduces a computational overhead. The cost varies by method:

• Vocabulary restriction is the cheapest, requiring a simple set lookup.
• Grammar/Regex enforcement requires maintaining and stepping a parser state, which can add latency, especially for complex schemas.
• Optimized implementations pre-compile grammars into efficient index lookup tables to minimize the per-token cost, making the overhead negligible for most production use cases.