A heuristic graph/tree search algorithm that explores the search space by keeping only a fixed number (beam width) of the highest-ranked partial solutions at each depth, pruning lower-ranked alternatives to limit computational cost while sacrificing completeness or optimality depending on beam size and ranking heuristic.

Principle

At each expansion level, score partial candidates by a heuristic or model likelihood, retain the top-B candidates (beam), expand them for the next level, and repeat; this breadth-limited strategy trades exhaustive exploration for tractable breadth control using a ranking criterion.

Demonstration

In sequence decoding (e.g., machine translation), beam search keeps the top-B most probable partial output sequences at each time step according to the model's conditional probabilities; it produces plausible outputs efficiently but can miss globally optimal sequences due to early pruning or poor scoring.

Misapplication

Using an overly small beam for tasks with long-range dependencies, relying on naive local scoring that favors short or high‑probability prefixes, or assuming beam search yields optimal or diverse outputs without adjustments (e.g., length normalization, diversity-promoting heuristics).

Consequence

Enables practical decoding and search in large combinatorial spaces by controlling branching with beam width; results are faster and often high-quality in practice but may be biased by scoring, underrepresent low-probability but globally good paths, and lack completeness guarantees unless beam is unbounded.

Reversal

Full breadth-first or exhaustive search (beam width equal to the entire frontier) is the reversal: it restores completeness and optimality guarantees at far higher computational cost and memory requirements.

Boundary

Applicable where partial solutions can be meaningfully scored and compared; not appropriate when scoring is unreliable, when completeness is required, or when memory/beam must be extremely small relative to branching factor; adjustments needed for stochastic or adversarial settings.

Semantic Tension

Often equated with greedy search or best‑first search; beam search generalizes greedy by keeping multiple candidates per level (B>1), whereas greedy is the B=1 special case and best‑first may expand based on global frontier score rather than fixed-level beams.

Synthesis

Beam search is a level-wise, beam-limited heuristic that retains a fixed number of top-ranked partial solutions to keep search tractable: an efficient approximation that depends critically on scoring quality and beam width, balancing speed and memory against completeness and optimality.