Beam Search¶

A heuristic search method — instantiates Search Space Pruning

Carries only a fixed number of the most promising partial candidates from one step to the next, trading the guarantee of finding the best path for a search budget that stays constant no matter how the space explodes.

Beam Search prunes by budget. At every step of building a solution incrementally, it expands the current candidates, scores all the resulting continuations, and keeps only the top w — the beam width — throwing the rest away for good. Everything outside the beam is gone; the method never backtracks to it. Where Branch and Bound prunes only what it can prove is worse, Beam Search prunes whatever looks worse right now under a heuristic score, accepting that it may drop a partial candidate that would have blossomed later. That is the deal it offers: a search whose cost stays flat and predictable — width w times depth — even when the true space grows exponentially. The signature risk is that the surviving w candidates all descend from the same early winner and collapse into near-duplicates, so it needs an explicit rule to keep the beam genuinely diverse.

Example¶

A speech-recognition system is turning an audio clip into text, word by word. At each word position there are tens of thousands of vocabulary choices, and over a 15-word utterance the number of possible transcripts is astronomical. Beam Search keeps only the 8 highest-scoring partial transcripts alive at each step (beam width 8). At position four it might hold "recognize speech", "wreck a nice beach", and six others; low-probability continuations are dropped and never revisited. By the end, one of the eight survivors is returned as the transcript.

Widen the beam to 64 and the transcript often improves and always costs more; narrow it to 1 (pure greedy decoding) and it runs fastest but frequently locks onto a wrong early word it can never undo. A known wrinkle appears too: past a point, widening the beam can make output worse, because the highest-scoring long sequence under the model is not always the best one^[1] — a reminder that the beam's score is a heuristic, not truth.

How it works¶

Expand — take the current set of partial candidates and generate every one-step continuation.
Score — rank all continuations by a heuristic value (a model probability, a cost-so-far estimate).
Keep the top w — retain only the w best continuations as the new beam; discard the rest permanently.
Repeat to completion, then return the best finished candidate.

The distinctive commitment is the fixed width: the frontier never grows, so compute and memory are bounded in advance rather than by what the space happens to contain. A diversity rule (grouping by origin, penalizing near-duplicates) is what stops the beam from silently narrowing to one lineage.

Tuning parameters¶

Beam width w — the master dial. Wider keeps more candidates alive (fewer good paths lost) at linearly higher cost; narrower is faster and greedier, with more early-commitment mistakes.
Scoring / length normalization — how partial candidates are compared, including whether longer sequences are penalized; a bad normalization systematically favors short or long candidates.
Diversity penalty — how hard near-duplicate continuations are demoted so the beam spans distinct families rather than variants of one.
Pruning threshold — an optional score cutoff that drops candidates far behind the leader even if the beam has room, saving work.
Stopping rule — when a candidate is "finished" and whether search continues for possibly-better completions.

When it helps, and when it misleads¶

Its strength is a constant, tunable budget: it makes an exponentially branching, incremental construction tractable and lets you dial the quality/cost trade with a single number. When you must build a solution step by step and cannot afford to hold the whole frontier, it is the natural tool.

It misleads because it offers no optimality guarantee and prunes irreversibly. A good path that scores poorly early is discarded and never recovered, so the answer is only as good as the heuristic score at each step — and a narrow beam amplifies early mistakes. Left unguarded, the beam collapses into near-clones of one candidate, giving a false sense of having "searched" when it explored a single lineage. And because more search is not always better search, blindly widening the beam can degrade results.^[1] The disciplines are to keep the beam diverse on purpose and to treat w as an empirical dial tuned against held-out cases, not a knob to crank ever higher.

How it implements the components¶

candidate_or_region_representation — the beam is the representation: a fixed-size set of partial candidates, each a prefix that can be extended, kept, or dropped.
cost_of_evaluation_estimate — the fixed width is an explicit evaluation budget; width times depth caps the work spent regardless of how large the true space is.
diversity_preservation_rule — the diversity penalty keeps the surviving set from collapsing into one lineage, protecting good paths that share a weak early prefix.

It does not test candidates against hard constraints (Constraint Filtering) or prove any region dominated (Branch and Bound); its cuts are heuristic and irreversible, with no built-in false-negative review — that belongs to Sample Audit of Exclusions.

Instantiates: Search Space Pruning — Beam Search is the fixed-budget heuristic end of the spectrum, opposite Branch and Bound's proof-based end.
Sibling mechanisms: Branch and Bound · Shortlisting · Constraint Filtering · Decision Tree Pruning · Dominated-Option Removal · Eligibility Screening · Negative Keyword Filter · Red-Flag Screen · Safety or Compliance Exclusion · Sample Audit of Exclusions · Triage Filter

References¶

[1] In sequence decoding it is well observed that increasing the beam width past a modest value can lower output quality — the model's highest-probability full sequence is not always its best one. The gap between "the search missed the top-scoring path" (search error) and "the top-scoring path is itself wrong" (model error) is why more search does not monotonically help. ↩