Beam Search

The beam width (k) is the core hyperparameter that defines the number of candidate sequences (or beams) the algorithm keeps in memory at each step. A width of k=1 is equivalent to greedy search, while a larger k explores more possibilities at the cost of increased memory and computation. The optimal value is task-dependent, balancing output quality and inference latency.

• Small k (e.g., 4-10): Common for machine translation, offering a good quality/speed trade-off.
• Large k (e.g., 50-100): Used in tasks requiring high precision, like automated theorem proving, but incurs significant overhead.

At each step, beam search prunes the exponentially growing tree of possible sequences. It expands all k current beams, generating k * V possible next tokens (where V is vocabulary size). It then scores each new partial sequence (e.g., using log probability) and selects only the top-k overall to carry forward. This process of hypothesis management prevents combinatorial explosion.

• Scoring: Typically uses the sum of log probabilities for the sequence so far.
• Efficiency: Pruning makes the search tractable, with complexity roughly O(k * n * log(V)), where n is sequence length.

A critical refinement to the basic probability scoring is length normalization. Since longer sequences naturally accumulate lower probabilities (more multiplicative terms < 1), the algorithm would unfairly favor shorter, often incomplete outputs. To correct this, scores are divided by the sequence length (or length^α, where α is a tunable parameter).

• Formula: score = (1 / (length^α)) * Σ log(P(token))
• Impact: Ensures the final selected sequence is not artificially short, leading to more coherent and complete generations in tasks like summarization or dialogue.

Beam search requires explicit termination criteria to decide when to stop generating tokens for all beams. The most common method is to wait until a predefined number of beams have produced an end-of-sequence (EOS) token. Once a beam hits EOS, it is considered complete and is set aside. Generation stops when a target number of beams (e.g., all k beams or a minimum batch) are complete, or when a maximum sequence length is reached.

• Early Stopping: Can halt once a minimum number of beams are finished, improving latency.
• Max Length: A hard stop to prevent infinite loops in degenerate cases.

Beam search occupies a middle ground between two extremes:

• Greedy Decoding (k=1): At each step, selects the single most probable next token. It's fast but can get trapped in sub-optimal sequences due to local maxima (e.g., producing repetitive text).
• Exhaustive Search (k=∞): Explores all possible sequences to find the globally optimal one. This is computationally intractable for all but the shortest sequences.

Beam Search provides a tunable compromise, exploring multiple high-probability paths simultaneously to find a better overall sequence than greedy search, without the prohibitive cost of an exhaustive search.

Primary Applications:

• Machine Translation: The classic use case, generating fluent, accurate translations.
• Text Summarization: Producing coherent summaries from long documents.
• Speech Recognition: Decoding audio features into word sequences.
• Image Captioning: Generating descriptive sentences from visual features.

Key Limitations:

• Lack of Diversity: All beams can become very similar, leading to generic outputs. Techniques like diverse beam search address this.
• Fixed Computation: Allocates the same compute to easy and hard parts of a sequence.
• Not Optimal: It's a heuristic; the final sequence is not guaranteed to be the globally best one.

Beam search is the standard decoding algorithm for sequence-to-sequence models in neural machine translation (NMT). It generates fluent, grammatically correct translations by exploring multiple partial translation hypotheses in parallel.

• At each step, it expands the top-k (beam width) most probable sequences of target-language words.
• This prevents the model from committing to a single, potentially suboptimal word choice early on, which is a common failure mode of greedy decoding.
• The algorithm effectively navigates the vast space of possible translations to find a sequence that maximizes overall probability, not just local choices.

For abstractive text summarization and autoregressive language model output (e.g., from GPT, Llama), beam search produces coherent, multi-sentence text.

• In summarization, it constructs a concise summary by sequentially generating words, using the beam to maintain several promising summary candidates.
• For open-ended generation, it helps avoid repetitive or nonsensical output by considering a broader set of plausible continuations than greedy sampling.
• It is often combined with length normalization to prevent the algorithm from unfairly favoring shorter sequences, which inherently have higher cumulative probability.

In end-to-end ASR systems that directly map audio spectrograms to text (using models like Connectionist Temporal Classification), beam search decodes the most probable word sequence.

• The audio signal is processed into a sequence of frame-level predictions over characters or subword units.
• Beam search merges paths that result in the same transcript so far, summing their probabilities, which is crucial for handling the alignment ambiguity between audio frames and output symbols.
• This allows the system to recover from local mispredictions in noisy audio, yielding more accurate transcripts.

Beam search generates descriptive natural language captions for images in encoder-decoder architectures (e.g., where a CNN encodes the image and an RNN/Transformer decodes the caption).

• The image encoder produces a fixed context vector.
• The decoder language model uses this context to initialize generation, with beam search exploring the space of possible descriptive phrases.
• By keeping multiple candidates, it can balance between generic captions ("a dog in a park") and more specific, likely correct ones ("a golden retriever playing fetch on a grassy field").

AI-powered code assistants use beam search to generate syntactically correct and semantically plausible code snippets from natural language prompts or partial code.

• The search space is constrained by programming language syntax, making beam search effective for navigating valid token sequences (keywords, identifiers, operators).
• It helps produce code that compiles by considering multiple structural pathways, reducing the likelihood of early syntax errors that derail generation.
• For code completion, a narrow beam can quickly provide the top few most likely completions for the next line or function block.

Beam search can be modified to incorporate hard or soft constraints, forcing the output sequence to contain specific keywords, follow a template, or avoid certain terms.

• Constrained beam search algorithms, like Grid Beam Search, treat constraints as finite-state machines, allowing the beam to track satisfaction progress.
• This is critical for task-oriented dialogue systems where responses must include specific information (e.g., a booking code) or for generating text that adheres to a predefined schema.
• It demonstrates beam search's flexibility beyond pure probability maximization, enabling controlled, deterministic output behavior when required.

Greedy search is the simplest decoding strategy for sequence models. At each generation step, it selects the single token with the highest predicted probability, committing to that path irrevocably. This is equivalent to beam search with a beam width of 1.

• Pros: Extremely fast and computationally cheap.
• Cons: Prone to suboptimal outputs, as an early high-probability token can lead to a low-probability overall sequence (a local optimum). It cannot recover from early mistakes.

Example: In machine translation, greedy search might choose a common but incorrect word early on, derailing the entire translation.

Top-k sampling and top-p sampling (nucleus sampling) are stochastic decoding methods that introduce randomness for more creative and diverse outputs.

• Top-k: Filters the vocabulary to the k most probable next tokens, then samples from this restricted distribution.
• Top-p: Dynamically selects the smallest set of tokens whose cumulative probability exceeds p (e.g., 0.9), then samples from this set.

Contrast with Beam Search: While beam search explores multiple deterministic high-probability paths, sampling explores probabilistic paths. Sampling is preferred for open-ended generation (e.g., storytelling), while beam search is better for tasks requiring precision (e.g., code generation, translation).

Exhaustive search (or breadth-first search in this context) is the theoretical upper bound for finding the globally optimal sequence. It explores every possible sequence path from the start token to the end token.

• Mechanism: It evaluates the joint probability of all complete sequences and selects the one with the maximum score.
• Computational Cost: Prohibitively expensive for all but the smallest vocabularies and sequence lengths. The complexity is O(V^L), where V is vocabulary size and L is sequence length.

Beam search is a heuristic approximation of exhaustive search, trading guaranteed optimality for tractable computation by pruning all but the b best paths at each step.

The Viterbi algorithm is a dynamic programming algorithm that finds the most likely sequence of hidden states in a Hidden Markov Model (HMM). It is guaranteed to find the global optimum efficiently for models with the Markov property.

• Key Similarity: Like beam search, it maintains multiple candidate paths and uses a pruning step, but its pruning is exact due to the Markov assumption (the future is independent of the past given the present state).
• Key Difference: Beam search is used for generative sequence models (like transformers) where each step depends on the entire generated history, breaking the Markov assumption. The Viterbi algorithm is designed for discriminative state sequence models with fixed, known state transition probabilities.

Length normalization is a critical scoring adjustment applied during beam search to counteract its inherent bias towards shorter sequences.

• The Problem: The probability of a sequence is the product of its token probabilities. Longer sequences naturally have more terms <1, making their total product (score) smaller, unfairly penalizing them.
• The Solution: Scores are normalized by sequence length, typically using a formula like (log_score) / (length^α), where α is a tunable parameter (often between 0.6 and 1.0).

Without length normalization, beam search will often prematurely generate end-of-sequence tokens, producing truncated and incomplete outputs.

Constrained beam search is a variant that forces the generated sequence to include specific pre-defined keywords, phrases, or sub-sequences. This is essential for tasks requiring strict adherence to formatting, inclusion of entities, or compliance with schemas.

• Use Cases: Generating API calls with required parameters, creating text that must mention certain products, or adhering to a strict JSON/XML output format.
• Mechanism: The algorithm modifies the candidate scoring or generation process to ensure that beams failing to meet the constraints are penalized or eliminated, while beams satisfying constraints are promoted. Frameworks like Hugging Face Transformers provide built-in support for this.