Beam Search Decoding

The beam width is the single most critical hyperparameter, defining the number of candidate sequences retained at each time step. A width of k=1 reduces to greedy decoding, always selecting the single most probable token. A larger k explores more of the search space, increasing the chance of finding a globally optimal sequence, but at a linear increase in computational cost and memory usage. Typical values range from 3 to 10 for text generation tasks.

Without normalization, beam search exhibits a length bias, unfairly penalizing longer sequences because the product of many probabilities (each < 1) becomes vanishingly small. To correct this, the cumulative log-probability score is divided by a length penalty term. A common formula is:

• score = (1 / length^α) * Σ log P(token)
• The hyperparameter α (often 0.6–1.0) controls the strength of the normalization, preventing the model from favoring short, generic outputs.

Standard beam search often produces sequences that differ by only a single token, creating a lack of diversity in the candidate set. To combat this, advanced variants enforce diversity constraints:

• Diverse Beam Search: Divides the beam into groups and penalizes tokens already selected by other groups.
• N-gram Blocking: Explicitly prevents the generation of repeated n-grams within a single beam candidate, reducing degenerate repetition.

The time complexity of beam search is O(k * V * L), where k is the beam width, V is the vocabulary size, and L is the sequence length. At each step, the algorithm must evaluate k * V possible next tokens, sort them, and select the top k. This makes it significantly more expensive than greedy decoding but far more tractable than an exhaustive breadth-first search, which would explode exponentially with sequence length.

Beam search excels in tasks requiring high-precision, deterministic outputs where a single optimal answer exists:

• Machine Translation: Finding the most probable translation.
• Speech Recognition: Mapping audio to the most likely transcript.
• Code Generation: Producing syntactically correct code.

However, it is poorly suited for open-ended creative tasks like story generation or dialogue, where it produces bland, generic, and repetitive text. For these, stochastic methods like top-p (nucleus) sampling are preferred.

To prevent wasted computation, beam search often employs early stopping heuristics. A candidate sequence is considered complete when it generates a dedicated End-of-Sequence (EOS) token. The search can terminate when k complete sequences are found, or when the score of the best incomplete candidate falls below the score of the worst completed candidate, guaranteeing no better sequence can be discovered.

The simplest decoding strategy that selects the single token with the highest probability at each step, with no backtracking or consideration of future outcomes. While computationally efficient, greedy decoding often produces suboptimal sequences because a locally optimal choice can lead to a globally poor path. It is deterministic and lacks diversity, making it unsuitable for creative text generation but adequate for tasks where speed is paramount and output variability is low.

A stochastic decoding method that randomly samples the next token from the k most likely candidates at each step, where k is a fixed integer. By truncating the tail of the probability distribution, top-k sampling balances fluency with diversity. However, a static k value struggles with dynamic distributions: a flat distribution may still include improbable tokens, while a peaked distribution may exclude valid alternatives. This limitation led to the development of nucleus sampling.

A dynamic sampling strategy that selects from the smallest set of tokens whose cumulative probability mass exceeds a threshold p. Unlike top-k, the candidate pool size adapts to the shape of the distribution at each step. A peaked distribution yields a small candidate set, while a flat distribution expands it. This adaptability makes nucleus sampling the preferred method for open-ended generation tasks where both coherence and diversity are required.

A hyperparameter applied during beam search to prevent the algorithm from favoring abnormally short sequences. Because the log-probability of a sequence is the sum of negative values, shorter sequences naturally accumulate higher scores. Length penalty normalizes scores by sequence length using the formula: score = log_prob / (length ^ alpha), where alpha typically ranges from 0.6 to 1.0. Without this correction, beam search often produces truncated, incomplete outputs.

An extension of standard beam search that partitions the beam into groups and penalizes similarity between them. By adding a dissimilarity term to the scoring function, diverse beam search encourages the generation of syntactically or semantically distinct hypotheses. This is critical for applications like machine translation and image captioning, where a user benefits from seeing multiple, meaningfully different output options rather than minor variations of the same sequence.

A generation technique that forces a model's output to conform to a predefined formal grammar, schema, or set of valid tokens at each step. Unlike beam search, which optimizes for probability, constrained decoding optimizes for validity. It is implemented via finite-state automata or token masking, ensuring outputs like valid JSON, SQL queries, or domain-specific structured formats. This is essential for programmatic content infrastructure where outputs must be machine-readable.