Constrained Beam Search

The foundational decoding algorithm that maintains multiple hypotheses (the 'beam') at each step. Unlike greedy search, which picks only the single most probable token, beam search keeps the top-k most probable partial sequences. This allows the model to explore alternatives that might have a slightly lower initial probability but lead to a much higher overall sequence probability. The beam width k is a critical hyperparameter balancing exploration against computational cost.

The core mechanism that physically enforces constraints during generation. Before the softmax step, a mask sets the logit value of invalid tokens to negative infinity, making their post-softmax probability exactly zero. This is not a post-hoc filter; it mathematically prevents the model from selecting tokens that violate the schema. In constrained beam search, this mask is applied to every active hypothesis in the beam, pruning branches that would lead to syntactically invalid sequences.

An abstract computational model that defines the set of all valid states and transitions for a structured output. During constrained generation, a compiled FSM tracks the current grammatical context (e.g., 'inside a string value', 'expecting a comma'). At each step, the FSM provides the exact set of permissible next tokens. This index-based approach is used by libraries like Outlines to guarantee output adherence to a formal schema without costly re-parsing.

The broader category of techniques that force a language model's output to conform to a formal grammar, typically a Context-Free Grammar (CFG). A CFG defines recursive production rules that describe all valid strings in a language. Frameworks like llama.cpp use GBNF grammars to specify these rules. Constrained beam search is one specific decoding strategy used to efficiently navigate the search space defined by these grammatical constraints.

A softer alternative to strict token masking. Instead of setting invalid token probabilities to zero, logit bias adds a positive or negative scalar value to specific token logits before sampling. A large negative bias can effectively suppress a token, while a positive bias can encourage it. This is useful for nudging the model toward preferred formatting without the rigid enforcement of a mask, though it does not provide a mathematical guarantee of validity.

A sampling parameter that eliminates all randomness from the token selection process. When temperature is set to zero, the model always selects the single most probable token from the masked distribution. Combined with constrained beam search, this produces a fully deterministic output: given the same input, schema, and seed, the result is perfectly reproducible. This is essential for production APIs where non-determinism is unacceptable.