Beam Search › Beam Search

When a sequence model generates text, it faces a combinatorial explosion. At every time step, the vocabulary might contain 30,000 tokens. After just 10 steps, the number of possible sequences is $30{,}000^{10}$, a number so large it dwarfs the atoms in the observable universe. You obviously cannot evaluate all of them. The decoder must make choices, and those choices determine whether the final output is fluent, accurate, or coherent.

As we covered in the Encoder-Decoder Framework chapter, the decoder operates autoregressively: it consumes its own previous output to predict the next token. And in the Teacher Forcing chapter, we saw that during training the decoder receives ground-truth tokens as input. But at inference time, ground-truth tokens are unavailable. The decoder must choose which token to feed itself next based purely on its probability estimates.

This chapter is about how to make that choice well. We will start with the simplest strategy, show why it systematically fails, and then build up to beam search, the approximate best-first algorithm that has powered machine translation, summarization, and caption generation for years. Along the way, we will examine length normalization, diversity mechanisms, stochastic alternatives, and the practical engineering realities of running beam search at scale. Understanding beam search deeply means understanding how it works, why those design choices exist, and what tradeoffs they reflect.