Constrained decoding intersects a language model's probability distribution with a formal grammar's automaton at every generation step, masking out any token that would leave the valid language.
next_state = delta(state, token) if token in Sigma(state)
reject otherwise, resample
- Grammar states — nodes of the finite-state machine encoding the target format (JSON, regex, DSL...).
- Branching factor — how many valid next-tokens each state permits — density of the transition graph.
- Sampling rate — how fast candidate tokens arrive from the language model's logits.
- Acceptance threshold — minimum logit mass required before a transition is taken instead of resampled.
Libraries like guidance, outlines and llama.cpp's grammar mode implement exactly this automaton to guarantee outputs that always parse, regardless of what the raw model would have said.