Constrained decoding

Deep dive

How it works

In: logits of the next token, the automaton state of this sequence, the compiled constraint · Out: masked logits and the next state · State: one automaton state (plus a stack for a CFG) per sequence · Cost: one bitset row read per step after a one-time index build; about 50 µs CPU per token for a CFG on a 128k vocabulary (llguidance README)

1. Compile the constraint (regex, JSON schema converted to a regex or grammar, GBNF) to a byte-level automaton.
2. Index the vocabulary: for each state s and token t, feed the token's bytes through the automaton from s. The token is allowed iff the walk never dies and ends in a state from which an accepting state is still reachable. Record next[s][t].
3. Decode: run the model, mask the logits with the bitset of the current state, sample as usual (greedy, top-p, temperature), advance the state with next[s][t].
4. The end-of-sequence token is allowed only in accepting states.

state 2 (digits so far)   vocab: "7" "12" ".5" "-" "abc" <eos>
mask:                            1    1    1   0    0      1     (accepting state)
state 0 (start)                  1    1    0   1    0      0     (".5" needs a digit first)

Code

Number grammar -?[0-9]+(\.[0-9]+)? over a toy vocabulary with multi-character tokens. A property test drives random logits through the mask and checks every output.

/// Byte-level DFA: `trans[state][class(byte)]`, `u16::MAX` = dead.
pub struct Dfa { pub trans: Vec<[u16; 3]>, pub accept: Vec<bool> }
const DEAD: u16 = u16::MAX;

fn class(b: u8) -> usize { match b { b'0'..=b'9' => 0, b'-' => 1, b'.' => 2, _ => return 3 } }

impl Dfa {
    /// JSON-style number: -?[0-9]+(\.[0-9]+)?
    pub fn number() -> Dfa {
        //            digit  '-'   '.'
        let trans = vec![[2, 1, DEAD], [2, DEAD, DEAD], [2, DEAD, 3], [4, DEAD, DEAD], [4, DEAD, DEAD]];
        Dfa { trans, accept: vec![false, false, true, false, true] }
    }
    fn step(&self, s: u16, b: u8) -> u16 {
        let c = class(b);
        if s == DEAD || c == 3 { DEAD } else { self.trans[s as usize][c] }
    }
    /// States from which an accepting state is still reachable.
    fn live(&self) -> Vec<bool> {
        let mut live = self.accept.clone();
        loop {
            let mut changed = false;
            for s in 0..live.len() {
                if !live[s] && self.trans[s].iter().any(|&t| t != DEAD && live[t as usize]) {
                    live[s] = true; changed = true;
                }
            }
            if !changed { return live; }
        }
    }
}

/// Per-state token mask (bitset over the vocabulary) + next-state table.
/// Built once per grammar; decoding is then one table lookup per step.
pub struct TokenIndex { pub words: usize, pub mask: Vec<u64>, pub next: Vec<Vec<u16>>, pub eos: usize }

impl TokenIndex {
    pub fn build(dfa: &Dfa, vocab: &[&str], eos: usize) -> TokenIndex {
        let (n, live) = (dfa.accept.len(), dfa.live());
        let words = (vocab.len() + 63) / 64;
        let mut mask = vec![0u64; n * words];
        let mut next = vec![vec![DEAD; vocab.len()]; n];
        for s in 0..n {
            for (t, tok) in vocab.iter().enumerate() {
                let ok = if t == eos { dfa.accept[s] } else {
                    // walk the token's bytes through the DFA; it must stay alive to the end
                    let end = tok.bytes().fold(s as u16, |q, b| dfa.step(q, b));
                    next[s][t] = end;
                    !tok.is_empty() && end != DEAD && live[end as usize]
                };
                if ok { mask[s * words + t / 64] |= 1 << (t % 64); }
            }
        }
        TokenIndex { words, mask, next, eos }
    }
    #[inline] pub fn allowed(&self, s: u16, t: usize) -> bool { self.mask[s as usize * self.words + t / 64] >> (t % 64) & 1 == 1 }
}

/// Mask logits in place: disallowed tokens get -inf.
pub fn apply_mask(ix: &TokenIndex, s: u16, logits: &mut [f32]) {
    for (t, l) in logits.iter_mut().enumerate() { if !ix.allowed(s, t) { *l = f32::NEG_INFINITY; } }
}

/// Greedy decode from any logits source; returns (text, stopped by EOS).
/// If `max` cuts generation short, the text is only a valid *prefix*.
pub fn decode(ix: &TokenIndex, vocab: &[&str], max: usize, mut model: impl FnMut(&str) -> Vec<f32>) -> (String, bool) {
    let (mut s, mut out) = (0u16, String::new());
    for _ in 0..max {
        let mut logits = model(&out);
        apply_mask(ix, s, &mut logits);
        let t = (0..logits.len()).max_by(|&a, &b| logits[a].total_cmp(&logits[b])).unwrap();
        if t == ix.eos { return (out, true); }
        out.push_str(vocab[t]);
        s = ix.next[s as usize][t];
    }
    (out, false)
}

Compiled and run: with vocabulary 0 1 7 - . 12 99 .5 1. -- abc -3 00 <eos> the start state rejects ., .5, --, abc and EOS but allows 1. and -3; 2000 random-logit runs all produced valid numbers (or valid prefixes when cut by the length cap).

Complexity and constants

• Index build: states x V x average token bytes. Done once per grammar; for a 128k vocabulary and a few hundred states, order of 10^8 byte steps. Production engines share token prefixes via a trie so one walk covers many tokens.
• Per step, regex: one bitset row read, then masking V logits. Bitset memory: states x V / 8 bytes (16 KB per state at V = 128k). A dense next table costs states x V x 2 bytes, so store it sparsely (only allowed tokens) or compute the one transition you need from the chosen token.
• Per step, CFG: the stack-independent part of the mask is precomputed; only tokens that depend on the stack contents are checked at runtime.

Efficiency

• Cost: CPU work on a small table beside a memory-bound forward pass. Regex: one bitset row of V/8 bytes (16 KB at V = 128k) per step. CFG: about 50 µs single-core per token at 128k tokens; with 16 cores and a 10 ms forward pass, batches up to 3200 run unslowed (llguidance README). It hurts only when computed serially after the logits.
• Levers:
  • precomputed per-state masks — one row read instead of V automaton walks per step (Outlines paper) — regular constraints
  • split context-independent tokens from stack-dependent ones, check only the latter — near-zero end-to-end overhead (XGrammar paper) — CFGs, JSON
  • overlap the CPU mask with the GPU forward pass (XGrammar paper) — batched serving
  • cache compiled grammars by schema hash — compile once per server — stable tool schemas
  • jump-forward: emit forced tokens ({"name": ") as prefill — fewer forward passes — rigid formats
• Naive → standard → state of the art:
  • test every vocabulary token against a parser each step · order of V = 128k checks per step
  • DFA with precomputed per-state bitset (Outlines) · one row read per step, heavy build for complex schemas
  • on-the-fly CFG masks overlapped with the GPU step (llguidance, XGrammar) · about 50 µs per token, hidden

Implementation notes

• Apply the mask before temperature, top-k and top-p. Masking after top-k can leave an empty candidate set.
• Mask on the logits' device (boolean tensor and masked_fill on GPU): copying a 16 KB bitset is cheap, copying 128k floats to the CPU is not.
• Walk bytes, not characters: tokens may end mid-UTF-8 sequence, and the DFA must accept partial code points.
• Use a trie over the vocabulary when building: tokens sharing a prefix share the automaton walk.
• Batched serving: keep one state per request and stack the mask rows into a [batch, V] tensor.
• Put a length bound in the grammar or in max_tokens; whitespace and digit loops are otherwise unbounded.

Pitfalls

• Tokenization mismatch: a model trained on canonical BPE segmentations is pushed into unusual splits when the mask only allows some tokens (e.g. " + } instead of "}). Subword-aligned engines (DOMINO) and token healing at the prompt boundary reduce the accuracy loss.
• Dead ends: an allowed token that leads to a state with no way to finish traps the decoder. Prune to live states (the live check above).
• Truncation: hitting max_tokens mid-object yields invalid output despite the constraint; validate or raise the cap.
• Prompt and constraint disagree: if the prompt never mentions the schema, the model fights the mask and fills fields with garbage that is syntactically valid.
• Free whitespace: a grammar allowing arbitrary whitespace lets weak models emit endless newlines; restrict it.
• Schema features: pattern, format, oneOf and numeric ranges are only partly expressible; check what the engine supports, then still validate with JSON Schema.
• Beam search and sampling: every beam and every parallel sample needs its own automaton state.

Variants and alternatives

In production

vLLM, SGLang, TensorRT-LLM and MLC-LLM integrate XGrammar; llama.cpp ships GBNF grammars and has llguidance integration; llguidance backs JSON-schema structured outputs at OpenAI (per its README); Outlines is the reference regex-index implementation. Text-to-SQL (PICARD on Spider and CoSQL) and industrial robot command parsing use the same masking idea with a SQL grammar or an action-frame grammar.

Implementations

Sources

• Brandon T. Willard, Rémi Louf, Efficient Guided Generation for Large Language Models, 2023. paper · code
• Yixin Dong et al., XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models, 2024. paper · code
• Luca Beurer-Kellner, Marc Fischer, Martin Vechev, Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation (DOMINO), 2024. paper
• Saibo Geng et al., Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning, EMNLP 2023. paper
• Terry Koo, Frederick Liu, Luheng He, Automata-based constraints for language model decoding, 2024. paper
• Torsten Scholak, Nathan Schucher, Dzmitry Bahdanau, PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models, EMNLP 2021. paper · code
• Precise Robot Command Understanding Using Grammar-Constrained Large Language Models, 2026. paper
• llguidance README (performance, adoption). code