Beam Search

Beam search keeps a bounded-size frontier: the $k$ best nodes (by $f$ or any other ranking). Everything else gets discarded.

Algorithm

``` function beam_search(initial, goal, k, score): beam = [initial] while beam not empty: next_beam = [] for node in beam: if node is goal: return node for action in actions(node): next_beam.append(transition(node, action)) next_beam.sort by score beam = next_beam[:k] return failure ```

Properties

• Complete: no — can prune away every path to the goal if $k$ is too small.
• Optimal: no — can prune the optimal path.
• Time: $O(kbd)$ — at each depth, expand $k$ nodes and keep best $k$ children.
• Space: $O(kd)$ if you track parents, $O(k)$ if you only need the goal.

When it's still the right call

Most domains where beam search dominates:

• Machine translation, summarization, sequence generation: at each decoder step, keep the $k$ best partial sequences by log-likelihood. Beam size 4–8 is typical.
• Speech recognition: same logic, beam sizes 50–500.
• Code synthesis, LLM generation: beam search is one of several decoding strategies (greedy, sampling, beam, nucleus).
• Robotics motion planning: when you need fast, good-enough plans rather than optimal ones.

In all these cases, the state space is too large for exact methods, the cost function is approximate anyway (a language model isn't a true probability), and "good enough fast" is what matters.

Beam size trade-off

• $k = 1$: greedy. Cheapest, often surprisingly close to optimal in practice for LMs.
• Larger $k$: closer to exhaustive search but linearly more compute.
• Diminishing returns past some point — empirically, beam size 5–10 captures most of the achievable gain for LM decoding.

Modern alternatives

• Diverse beam search: penalize beams that look too similar, encouraging exploration.
• Best-first beam: maintain $k$ but pick which to expand by best score globally, not by depth.
• Stochastic beam search / nucleus sampling: sample from the top-$k$ probability mass instead of taking the deterministic top-$k$. Used for generation tasks where deterministic beam search produces dull, repetitive text.