constrained decoding
In plain wordsForcing an AI model's output to follow a required format — such as valid code or a fill-in form — by blocking, at every step, any word that would break the rules.
A decodingdecoding, n.: The method a language model uses to turn its predictions into actual text — for example, always picking the most likely next word, or choosing somewhat at random among the likely ones. technique that restricts which tokenstoken, n.: The small chunk of text an AI language model reads and writes — often a word, part of a word or a punctuation mark. AI usage, limits and prices are counted in tokens. a language modellanguage model, n.: A system that has learned how likely different sequences of words are, so it can predict the next word in a text and, by doing that repeatedly, write text of its own. may produce at each step so that the output is guaranteed to satisfy a formal constraint, typically by masking the logitslogit, n.: A raw score that a model gives each possible answer before the scores are turned into probabilities. In statistics, the 'log-odds': a probability rewritten on a scale running from minus to plus infinity. of disallowed tokens before sampling. Constraints may be lexical (required words or phrases, as in grid beam search for translation), a regular expression, a JSON SchemaJSON Schema, prop. n.: A standard way of writing down exactly what a piece of JSON data must look like — which fields, of which types — so that software and AI models can check it or follow it. or a context-free grammar. Efficient implementations compile the constraint into a finite-state machine or pushdown automaton and precompute, for each state, which vocabulary tokens are valid, taking care with tokens that span several grammar symbols. Constrained decoding underlies the strict modes of structured outputsstructured outputs, n.: Getting an AI model to answer in an exact, machine-readable format — like a form with fixed fields — so other software can use the answer without guesswork. and JSON modeJSON mode, n.: A setting on some AI services that makes the model reply only in JSON, a standard text format for data, so that programs can read the reply reliably. in commercial APIs and the grammar features of open-source engines. It guarantees syntax, not correctness, and overly tight constraints can lower quality by pushing the model away from its preferred phrasing.
With constrained decoding against the schema, every response parses — we deleted the retry logic.
Origin
Lexically constrained decoding with grid beam search was introduced by Chris Hokamp and Qun Liu (April 2017; ACL 2017). Brandon T. Willard and Rémi Louf's finite-state formulation and Outlines library (July 2023), llama.cpp's GBNF grammars (2023) and OpenAI's strict structured outputs (August 2024) brought grammar-constrained generation into mainstream use.
Related
- structured outputsstructured outputs, n.: Getting an AI model to answer in an exact, machine-readable format — like a form with fixed fields — so other software can use the answer without guesswork.
- JSON modeJSON mode, n.: A setting on some AI services that makes the model reply only in JSON, a standard text format for data, so that programs can read the reply reliably.
- JSON SchemaJSON Schema, prop. n.: A standard way of writing down exactly what a piece of JSON data must look like — which fields, of which types — so that software and AI models can check it or follow it.
- logit biaslogit bias, n.: A setting that lets developers make specific words more or less likely in an AI model's output — even ban a word outright — by adjusting the model's scores before it chooses.
- decodingdecoding, n.: The method a language model uses to turn its predictions into actual text — for example, always picking the most likely next word, or choosing somewhat at random among the likely ones.
- beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility.
Sources
- Hokamp, C. & Liu, Q. (2017). Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search. ACL 2017. arxiv.org/abs/1704.07138
- Willard, B. T. & Louf, R. (2023). Efficient Guided Generation for Large Language Models. arXiv:2307.09702. arxiv.org/abs/2307.09702
Mentioned in
beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility., decodingdecoding, n.: The method a language model uses to turn its predictions into actual text — for example, always picking the most likely next word, or choosing somewhat at random among the likely ones., function callingfunction calling, n.: A feature of AI model services that lets the model reply with a neatly formatted request to run one of a program's functions, rather than with ordinary text; the program, not the model, then runs it., JSON SchemaJSON Schema, prop. n.: A standard way of writing down exactly what a piece of JSON data must look like — which fields, of which types — so that software and AI models can check it or follow it., llama.cppllama.cpp, prop. n.: A free, open-source program that runs AI language models on ordinary computers and phones, without needing a powerful graphics card, by using compact low-precision versions of the models., steeringsteering, n.: Guiding what an AI model does — its topic, tone or behavior — while it runs, by changing its instructions, its internal signals or how its next word is chosen, rather than by retraining it., stop sequencestop sequence, n.: A piece of text that tells an AI model to stop writing as soon as it produces it — for example, stopping at a blank line or just before the next question., structured outputsstructured outputs, n.: Getting an AI model to answer in an exact, machine-readable format — like a form with fixed fields — so other software can use the answer without guesswork., JSON modeJSON mode, n.: A setting on some AI services that makes the model reply only in JSON, a standard text format for data, so that programs can read the reply reliably., logit biaslogit bias, n.: A setting that lets developers make specific words more or less likely in an AI model's output — even ban a word outright — by adjusting the model's scores before it chooses., SGLangSGLang, prop. n.: A free, open-source engine for running AI language and image models on servers, built to be fast when many requests begin the same way, as in chat and agent workloads.