Beam Search

The beam width (k) is the algorithm's core hyperparameter, representing the maximum number of candidate sequences retained at each step of the search. It creates a memory and compute budget, trading off between:

• Greedy Search (k=1): Only the single best hypothesis is kept, highly efficient but prone to local optima.
• BFS-like Search (k=∞): All hypotheses are kept, guaranteeing optimality but at prohibitive exponential cost. A typical beam width ranges from 4 to 10 for language generation tasks, providing a practical balance.

Beam search achieves polynomial time and space complexity relative to sequence length, unlike the exponential growth of exhaustive search. At each time step t, the algorithm:

• Expands the k best hypotheses from step t-1.
• Scores the resulting k * V candidates (where V is vocabulary size).
• Prunes back to the top-k for the next step. This results in O(k * V * T) time complexity, making it feasible for large vocabularies and long sequences where exhaustive search is impossible.

The algorithm maintains a beam—a priority queue of the top-k partial sequences ranked by a scoring function (typically log probability). At each iteration:

• Each hypothesis in the beam is expanded by all possible next tokens.
• New scores are computed (cumulative log probability).
• All new hypotheses are pooled and sorted; only the top-k survive. This pruning is aggressive and deterministic, discarding potentially good long-term paths for short-term gains, which is its primary limitation versus optimal algorithms like A*.

Beam search is a best-first, breadth-limited variant of Breadth-First Search (BFS).

• Similar to BFS: It explores the tree level-by-level.
• Difference from BFS: Instead of keeping all nodes at a level (which grows exponentially), it keeps only the k most promising nodes.
• Result: It approximates BFS's ability to avoid the depth traps of DFS but within a fixed memory budget. It is not complete (may not find a solution) and not optimal (may not find the best solution) due to this pruning.

Beam search is the dominant decoding algorithm for autoregressive sequence generation tasks:

• Machine Translation: Generating the most fluent and accurate translation from a source sentence.
• Text Summarization: Producing a concise summary from a long document.
• Speech Recognition: Decoding the most probable word sequence from acoustic features.
• Code Generation: Generating syntactically correct code from natural language descriptions. In these tasks, the scoring function is usually the log probability assigned by a trained model (e.g., an LLM), and the beam width is tuned for a balance of quality and latency.

Standard beam search has known limitations, leading to several algorithmic variants:

• Lack of Diversity: The beam can become filled with nearly identical sequences. Mitigation: Use diversity-promoting penalties (e.g., Hamming diversity) or group beam search.
• Length Bias: It favors shorter sequences due to the multiplicative nature of probabilities. Mitigation: Apply length normalization (e.g., dividing score by length).
• Suboptimality: Pruning can discard the globally best path. Mitigation: Increased beam width (costly) or integrated use with top-k/top-p sampling for a stochastic hybrid approach. These trade-offs make beam search a tunable engineering component rather than a purely theoretical optimizer.

Best-First Search is a graph traversal algorithm that expands the most promising node according to an evaluation function, typically implemented with a priority queue. Unlike beam search, which maintains a fixed-width beam of candidates, best-first search explores a single, globally optimal path at each step, which can require significant memory for the open list.

• Key Mechanism: Uses a heuristic function f(n) to prioritize node expansion.
• Primary Use Case: Pathfinding (e.g., A* algorithm) and optimization problems where finding any optimal path is critical.
• Contrast with Beam Search: Beam search is a memory-constrained variant of best-first search, sacrificing global optimality guarantees for efficiency by pruning all but the top-k (beam width) nodes at each depth level.

Breadth-First Search is an uninformed search algorithm that explores a tree or graph by visiting all nodes at the present depth level before moving to nodes at the next depth level. It guarantees finding the shortest path in an unweighted graph but suffers from exponential memory complexity O(b^d), where b is the branching factor and d is the solution depth.

• Key Mechanism: Uses a First-In-First-Out (FIFO) queue.
• Primary Use Case: Exhaustive exploration where solution depth is minimal or shortest-path guarantees are required.
• Contrast with Beam Search: Beam search can be viewed as a memory-bounded approximation of BFS. Instead of keeping all nodes at a level, it retains only the top-k most promising nodes, trading completeness for tractability in large state spaces.

Greedy Search (or Greedy Best-First Search) is a heuristic algorithm that always expands the node that appears to be closest to the goal, based solely on a heuristic function h(n). It is highly efficient but often incomplete and non-optimal, as it can become stuck in local optima.

• Key Mechanism: Expands the node with the lowest heuristic cost h(n) to the goal.
• Primary Use Case: Problems where computational speed is prioritized over solution quality, or where the heuristic is highly reliable.
• Contrast with Beam Search: Beam search with a width of k=1 is equivalent to greedy search. However, with k>1, beam search maintains multiple hypotheses in parallel, making it more robust to heuristic errors and local optima than a purely greedy approach.

The Viterbi Algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states (the Viterbi path) in a Hidden Markov Model (HMM). It is mathematically analogous to beam search with a beam width equal to the total number of possible states.

• Key Mechanism: Computes the maximum a posteriori probability estimate for each state sequence by recursively evaluating all paths and retaining only the most probable path to each state.
• Primary Use Case: Sequence decoding in signal processing, speech recognition, and bioinformatics.
• Contrast with Beam Search: The Viterbi algorithm is exact and considers all states. Beam search applied to sequence models (like in neural machine translation) is an approximation that prunes all but the k best partial sequences at each time step, vastly improving speed for large vocabularies.

Top-k Sampling is a decoding strategy for autoregressive language models where, at each generation step, the probability distribution over the vocabulary is truncated to only the k most likely tokens, from which one is sampled. This balances diversity and coherence.

• Key Mechanism: Filters the vocabulary to a shortlist of size k before sampling, preventing low-probability, nonsensical tokens.
• Primary Use Case: Text generation with large language models to improve output quality.
• Contrast with Beam Search: Both methods use a width parameter k. However, top-k is a sampling-based method (stochastic) that produces diverse outputs, while beam search is a deterministic search for the highest-scoring overall sequence according to the model's probabilities. Beam search often leads to more fluent but potentially generic and repetitive text.

Monte Carlo Tree Search is a best-first, heuristic search algorithm for decision processes that combines tree search with random sampling. It builds a search tree asymmetrically, focusing computational resources on the most promising regions of the state space through repeated iterations of selection, expansion, simulation, and backpropagation.

• Key Mechanism: Uses random rollouts (simulations) to estimate the value of leaf nodes, guiding future exploration via the Upper Confidence Bound for Trees (UCT) formula.
• Primary Use Case: Game-playing AI (e.g., AlphaGo, AlphaZero), complex planning, and combinatorial optimization.
• Contrast with Beam Search: MCTS is adaptive and asymmetric, deeply exploring promising lines. Beam search is synchronous and breadth-oriented, exploring all retained branches equally to a fixed depth. MCTS is often more sample-efficient for problems with deep, complex state spaces where heuristic evaluation is difficult.