Beam search is a heuristic decoding algorithm that generates sequences by maintaining a fixed-size set of candidate sequences — called the beam — at each generation step. At every step, all candidates in the beam are extended by every possible next token, scored by the model, and only the top-k scoring partial sequences (where k is the beam width) are kept for the following step. This approach explores more of the output space than greedy decoding, which always picks the single highest-probability next token, without the exponential cost of exhaustive search over all possible sequences.

Think of it like navigating a large maze by sending out a small team of scouts rather than one person. Each scout takes a different path; at each junction the weakest routes are abandoned so the team stays at a manageable size, and at the end the scout who found the best route wins.

Beam search with a width of 4 might proceed like this for a short translation task:

Step 1 candidates (beam=4):
  [The, A, This, One]

Step 2 (expanding each, keeping top 4 sequences):
  ["The cat", "The dog", "A cat", "This is"]

Step 3:
  ["The cat sat", "The dog ran", "A cat sat", "The cat lay"]

The final sequence is chosen once an end-of-sequence token is generated. A length penalty is often added to prevent the algorithm from favouring shorter sequences, which tend to accumulate higher log-probabilities.

Beam search relates to the Autoregressive Model framework it operates within, Temperature (which modifies the distribution before beam search samples from it), and the Loss Function used during training (which does not directly optimise for beam search at test time, a gap known as exposure bias). It is commonly contrasted with sampling-based decoding methods.

You will encounter beam search in machine translation systems, summarisation pipelines, and any generative task where deterministic, high-quality output is preferred over diverse or creative outputs.