Constrained decoding

Also known as: grammar-constrained decoding

On this page 7

Constrained decoding is a generation technique that masks invalid tokens at every decoding step, so the output of a language model is guaranteed to follow a predefined format such as a JSON schema, a regular expression or a context-free grammar. In the field of language models, it is also called grammar-constrained decoding, and it turns format compliance from a hope expressed in the prompt into a hard guarantee enforced by the inference engine.

The technique matters wherever model output is consumed by software rather than read by people: tool calls, structured extraction, code generation and classification into fixed labels. It does not make the model smarter, but it removes an entire class of parsing failures and malformed responses.

How constrained decoding masks the logits

Constrained decoding works by setting the logits of disallowed tokens to negative infinity before sampling, so their probability becomes exactly zero. An autoregressive model produces a score for every token in its vocabulary at each step; a constraint engine tracks how much of the required structure has already been generated and computes which next tokens keep the output valid.

The usual pipeline compiles the constraint into an automaton. A regular expression or a JSON schema becomes a finite-state machine, while recursive structures such as nested JSON or programming languages require a pushdown automaton that can track nesting depth. After each emitted token, the automaton advances its state and produces the next allowed-token mask.

The following table summarizes the stages that a typical implementation runs for every generated token.

StageWhat happensTypical cost
Forward passThe model computes logits for the full vocabularyDominant cost on accelerators
Mask computationThe engine lists tokens consistent with the current automaton stateMicroseconds to milliseconds
Mask applicationInvalid logits are set to negative infinityNegligible
SamplingTemperature, top-p or greedy selection over the remaining tokensNegligible
State updateThe automaton consumes the chosen token and moves forwardNegligible
Stages of one constrained decoding step

A central engineering problem is the mismatch between tokens and grammar symbols. Tokens produced by byte-pair encoding often span several characters, such as a closing quote followed by a comma, so the engine must check whether each multi-character token can be consumed by the automaton. Efficient libraries precompute an index from automaton states to valid tokens to keep this check fast.

Types of constraints

Constraints differ in expressive power and compilation cost, and the right choice depends on how complex the target format is. Simple lists of allowed answers are cheap, while full programming-language grammars are expensive to compile and to track.

Constraint typeFormal modelTypical use
Choice listPrefix tree of allowed stringsClassification into fixed labels
Regular expressionFinite-state machineDates, identifiers, phone numbers
JSON schemaFinite-state or pushdown automatonStructured outputs and tool calls
Context-free grammarPushdown automaton, often in EBNFSQL, domain-specific languages, code
Lexical constraintRequired or banned token sequencesTerminology control in translation
Common constraint formats and their uses

Commercial interfaces often expose the technique as structured outputs or JSON mode. JSON mode alone usually guarantees only syntactically valid JSON, whereas schema-enforced structured outputs also guarantee required fields, types and enumerated values. The difference is significant when downstream code expects specific keys.

How it compares with prompting and other decoding strategies

Constrained decoding is a modification of the decoding strategy, not a replacement for one. It sits on top of greedy decoding, beam search or sampling with temperature, top-k or min-p, and it restricts the candidate set those methods choose from.

Other ways of obtaining structured output rely on the model behaving well. The table compares the main approaches by the strength of their guarantee.

ApproachFormat guaranteeMain weakness
Prompt instructionsNone, compliance is probabilisticOccasional malformed or truncated output
Few-shot examplesNone, but higher complianceConsumes context window tokens
Fine-tuning for formatStatistical, not absoluteRequires training data and retraining
Validate and retryEventual, after repeated callsAdded latency and cost per failure
Constrained decodingHard guarantee on syntaxNeeds access to logits and engine support
Approaches to structured model output

Because it requires direct control over the logits, constrained decoding is straightforward with open-weight models served locally and depends on provider support when a model is accessed through a hosted API. Stop sequences and max tokens are much weaker controls: they only end generation, they do not shape it.

Configuring constrained decoding in practice

Effective use starts with a schema that is as strict as the application requires and no stricter. Enumerations, required fields and bounded string patterns reduce ambiguity, while unnecessary nesting and very large unions inflate compilation time and can confuse the model.

  • Order fields deliberately: put a reasoning or explanation field before the final answer field when the model benefits from working through the problem first.
  • Describe fields in the prompt as well as in the schema, because the mask enforces syntax but does not tell the model what a field means.
  • Cache compiled grammars for schemas that are reused, since compilation can take longer than generation for complex grammars.
  • Set a sufficient max tokens limit, because a response cut off by the length limit can still be incomplete even when every emitted token was valid.

The following decision table matches common situations with a suitable constraint strategy.

SituationRecommended constraintReason
Sentiment or intent labelsChoice listCheapest and fully unambiguous
API payload or tool argumentsJSON schemaGuarantees keys, types and enums
Text-to-SQL generationContext-free grammarCaptures nested queries and clauses
Free-form answer with an IDRegular expression on the ID part onlyKeeps prose unconstrained
Choosing a constraint strategy

Limitations and common misconceptions

The most common misconception is that valid syntax means correct content. Constrained decoding guarantees that output parses, but it cannot guarantee that the values are true; a model can still produce a perfectly formatted hallucination.

A subtler problem is distribution distortion. Masking renormalizes probabilities locally at each step, which is not the same as sampling from the model’s distribution conditioned on the whole output being valid. When the model’s preferred continuation is blocked, the engine can force it into an unlikely path that degrades quality, for example filling a string field with filler text because the closing quote was its only valid exit.

  • Tokenization artifacts: forcing token boundaries that differ from those seen in training can reduce output quality, a problem sometimes called token healing.
  • Reasoning suppression: very tight formats leave no room for chain-of-thought, which can lower accuracy on difficult tasks.
  • Throughput overhead: mask computation on the CPU can become a bottleneck in large batched serving if it is not overlapped with the forward pass.
  • Schema coverage gaps: some engines support only a subset of JSON schema keywords and silently ignore the rest.

A non-technical view

A language model writes one small piece of text at a time, choosing each piece from a huge list of possibilities. Constrained decoding is like giving the model a form with fixed boxes and graying out every choice that would not fit the form. The model still decides what to write, but it can only pick from options that keep the result valid.

The key point is simple: the format becomes guaranteed, but the facts do not. A neatly filled form can still contain a wrong answer, so the content still needs checking.

A concrete example

An insurance claims team uses an open-weight model to extract data from scanned damage reports. Each result must be a JSON object with a policy number matching a fixed pattern, a damage category from a list of eight allowed values, an estimated amount as a number and a free-text summary. Without constraints, about one response in a few hundred breaks the parser through a missing bracket, an invented category or an amount written as words.

The engineers compile the schema into a grammar and enable constrained decoding in their inference server. Parsing failures drop to zero, the retry loop is removed and median latency falls because no request is sent twice. Human reviewers still sample results, since the team found that a small share of valid-looking records carried wrong amounts, which the format constraint could never have caught.