Beam search & the informedness/cost trade-off

Beam search: a fixed-width frontier

Beam search is best-first search with a hard cap on the open list. After generating successors, it keeps only the $k$ heuristically best states (the beam width) and discards the rest. This bounds memory and concentrates effort on the most promising lines.

The cost is completeness: by throwing away states, beam search can discard the *only* path to a solution, or the optimal one — so it may return a sub-optimal answer or none at all. Beam search sits exactly between the two extremes you have already met:

- beam width 1 ≈ hill-climbing (one state, no recovery); - beam width ∞ = full best-first search (every state retained).

The width $k$ is a tunable knob: wider beams are likelier to find the optimum but cost more memory. Beam search is heavily used where the space is enormous — e.g. beam-search decoding in NLP and sequence models.

The informedness / computation trade-off

A central, easily-forgotten point from this chapter: a more informed heuristic is not automatically better in practice. More informedness prunes more states (less search) — but evaluating a richer heuristic costs more per state. The quantity that actually matters is *total* cost:

$$\text{total} = (\text{heuristic eval cost per state}) \times (\text{states expanded}) + \dots$$

A heuristic so expensive that its evaluation time exceeds the time it saves by pruning is counter-productive, even though it is theoretically more informed. This is the classic chess design tension — simple-fast-heuristic + deep search (Deep Blue's specialized hardware) versus rich-slow-heuristic + shallow search. The right blend is an empirical question that depends on the problem, the hardware, and the time budget.

Branching factor: why any of this is necessary

The reason pruning is not optional is the branching factor $B$ — the average number of children per state. Searching to depth $L$ generates roughly $B^{L}$ states. For chess $B \approx 35$, so exhaustive search is hopeless at any real depth. Trimming $B$ — by symmetry reduction, heuristic ordering, alpha-beta cutoffs, or a beam — is what turns an intractable space into a searchable one.