What does beam search trade away, and what is it controlled by?

Answer

It trades away completeness (it can discard the only or optimal solution path) in exchange for bounded memory. It is controlled by the beam width k — the fixed number of best states kept on the open list.

Beam width 1 ~ hill-climbing; beam width infinite = full best-first. Wider beams are more likely to find the optimum but use more memory.