Beam search explained: how it works, and when it beats greedy decoding

Before you start

Why interviewers ask this

Beam search is the standard test of whether you understand that generating text is a search problem, not a lookup. A candidate who says "the model picks the most likely word" has described greedy decoding and nothing else. An interviewer then asks what goes wrong, and the answer separates levels. A weak answer repeats the definition. A strong answer explains why the best first token does not always start the best sentence, why the score needs a length correction, and why chat models usually do not use beam search at all.

The question appears in machine learning (ML) coding rounds, where the prompt is often "implement beam search", sometimes with a length penalty, and in design rounds on translation, speech and captioning. The ML coding round guide places it among the other from-scratch questions.

Beam search from first principles

Beam search

Beam search is a decoding algorithm that keeps the B most probable partial output sequences at each step, extends each by every possible next token, and prunes back to B, then returns the best finished sequence.

Beam width

The beam width is the number B of partial sequences, called beams, that beam search keeps alive after each step; a width of one is greedy decoding.

Length penalty

A length penalty is a divisor applied to a sequence's log probability so that sequences of different lengths can be compared fairly, because every extra token otherwise lowers the score.

In plain words

Imagine finding a route through a town where every junction has several roads. Greedy decoding always takes the road that looks best right now. Beam search sends B scouts instead. After each junction it keeps the B scouts that are doing best and calls back the rest. The analogy breaks in one place. Real scouts see the road ahead. A language model scores only the path already walked, so a good start can still lead nowhere.

Stated precisely, beam search chooses the output sequence with the highest total log probability, searching only a narrow band of the possible sequences. Greedy decoding is the special case where the band holds one sequence. The Hugging Face documentation says greedy search "selects the next most likely token at each step" and that beam search "can look ahead" and pick a sequence with a higher overall probability even if its first tokens had lower probability (Hugging Face, read October 2026).

Step 1: Start with one empty beam

The first step sets up the search with a single beam that holds no tokens and a score of zero. The input is the prompt, or, in a translation model, the encoder's summary of the source sentence. The output is a list with one entry. The score is a log probability.

A log is used because the probability of a sequence is the product of many numbers below one, and a product of twenty such numbers can underflow, while a sum of logs stays well behaved. In Sutskever et al., the decoder "maintains a small number B of partial hypotheses, where a partial hypothesis is a prefix of some translation" (Sutskever et al., 2014). What you now know: the beam list starts with one empty entry.

Step 2: Expand every beam by every token

The second step asks the model for next-token probabilities once per beam and creates one candidate for every token in the vocabulary. The input is B beams; the output is B times V candidates, where V is the vocabulary size. Each candidate's score is its parent's score plus the log probability of the new token. Sutskever et al. describe the same move: "we extend each partial hypothesis in the beam with every possible word in the vocabulary" (Sutskever et al., 2014). This step is where the cost sits, since the model runs B times per step instead of once. What you now know: one step turns B beams into many scored candidates.

Step 3: Score all candidates together and keep the top B

The third step ranks all candidates from all beams in one list and keeps only the best B. The input is the full candidate list; the output is a new beam list of size B. The ranking is global: two children of one strong parent can both survive while a weaker parent loses all its children. The same paper says the decoder discards "all but the B most likely hypotheses according to the model's log probability" (Sutskever et al., 2014). This pruning is why the search is approximate: a sequence pruned at step three is gone, even if it would have won at step ten. What you now know: the beam never grows past B.

Step 4: Normalise the score for length

The fourth step handles beams that have ended with an end-of-sequence token, and it fixes a bias. A finished sequence leaves the beam and joins a set of complete hypotheses. Their scores cannot be compared raw, because each token adds a negative number, so a short sequence tends to score higher.

Wu et al. state that without length normalisation "regular beam search will favor shorter results over longer ones on average" (Wu et al., 2016). They divide the log probability by a length penalty, $lp(Y)=(5+|Y|{)}^{\alpha }/(5+1{)}^{\alpha }$, where $|Y|$ is the number of tokens in the sequence and alpha sets the strength (0 means no penalty), and report that a value of alpha between 0.6 and 0.7 was usually best on their development set, the held-out examples used to compare settings. In the worked example below, this division reverses a ranking. What you now know: the final choice is made on normalised scores.

Step 5: Stop and return the best finished sequence

The fifth step decides when to stop and which sequence to return. The search stops when it reaches a maximum length or when the best finished hypothesis can no longer be beaten by any beam still running. The output is the finished sequence with the best normalised score, not the beam that happens to be first. Wu et al. add a pruning rule that ends the search quickly once a good finished sequence exists, which sped up their central processing unit (CPU) search by 30 to 40 percent (Wu et al., 2016). Libraries expose this choice as an early-stopping option. What you now know: the answer is the best of the finished sequences.

Worked example

A hand-written toy model shows greedy decoding losing to a beam of two. The model has a vocabulary of a few words and gives each next-token probability from a fixed table (illustrative: these are not measurements of a trained model). Sequences are three tokens long. At the start the model gives "the" 0.5, "a" 0.4 and "one" 0.1. After "the" its best next word is "cat" at 0.4, and after "a" it is "cat" at 0.9.

Greedy decoding takes "the" because 0.5 beats 0.4, then "cat" at 0.4, then "sat" at 0.6, for a total probability of 0.12. Beam search with width two keeps both "the" (0.5) and "a" (0.4). At step two the best candidate is "a cat" at 0.36, ahead of "the cat" at 0.2, and "a cat sat" finishes at 0.252. The best of all 16 possible sequences is also "a cat sat", so a width of two finds the optimum here, and a width of three changes nothing.¹

The trace below shows the width-two run itself. At step one the beam keeps "the" at 0.5 and "a" at 0.4 and prunes "one" at 0.1. At step two the beam keeps "a cat" at 0.36 and "the cat" at 0.2. At step three it ends with "a cat sat" at 0.252 against "the cat sat" at 0.12.¹

The length penalty can be shown with two finished sequences, again illustrative. A short one of two tokens has probability 0.30 and a longer one of five tokens has probability 0.25. On raw log probability the short one wins, at minus 1.204 against minus 1.386. With the penalty above and alpha of 0.6, the penalty is 1.097 for two tokens and 1.359 for five, so the normalised scores are minus 1.098 and minus 1.020, and the longer sequence wins.¹

The size of the problem explains why a narrow beam is needed at all. For an illustrative vocabulary of 32,000 tokens and an output of 20 tokens, there are about 10 to the power 90 possible sequences, and a beam of width four scores 128,000 candidates per step instead.¹

Trade-offs and edge cases

A wider beam is not always better. Beam search maximises probability, and for open-ended text the most probable text is often poor. Holtzman et al. report that "maximization-based decoding methods such as beam search lead to degeneration", meaning output that is "bland, incoherent, or gets stuck in repetitive loops" (Holtzman et al., 2019). Their experiments show that for the two largest models they tested, with 774 million and 1.542 billion parameters, a beam of 64 or more prefers to stop generating straight after the given context. They also note that for tasks like translation, where the output is tightly scoped by the input, repetition and genericness are less of a problem.

A second case is the cost. Each step runs the model once per beam, so compute and memory grow with B. Each beam also needs its own attention cache, so beam search multiplies cache memory as well as compute; the key-value (KV) cache page explains what that cache holds. Sutskever et al. found that "a beam of size 2 provides most of the benefits of beam search" on translation (Sutskever et al., 2014), and Wu et al. kept 8 to 12 hypotheses but saw only slight losses with 4 or 2 (Wu et al., 2016).

A third case is what beam search actually optimises. Meister et al. argue it is the exact solution to a different objective, one that pushes text toward an even spread of information across the sentence, and in their translation experiments, adherence to that objective correlated with translation quality scores (Meister et al., 2020). Reported practice differs on the best setting, so treat beam width and the penalty as settings you tune on held-out examples.

For attention and decoder background, see self-attention and causal masks in decoders.

How to answer it in an interview

The spoken structure is: say what greedy does wrong, say what the beam keeps, then name the length penalty and the use case.

Common mistakes

1. Calling beam search exact. (wrong) "Beam search finds the most likely sequence." (right) "Beam search searches a narrow band, so it can miss the best sequence; a wider beam usually makes that less likely, though not always."
2. Forgetting the length penalty. (wrong) "Pick the beam with the highest log probability." (right) "Compare finished sequences after dividing by a length penalty, or short ones win."
3. Assuming a bigger beam is always better. (wrong) "Set the beam to 100." (right) "Past a small width the gain is tiny, the cost grows with B, the result may not improve, and open-ended text can get worse."
4. Keeping one beam per first token only. (wrong) "Run B separate greedy searches." (right) "Rank all candidates from all beams together, so one strong parent can supply several survivors."
5. Using it for chat. (wrong) "Beam search gives the best chat answers." (right) "It optimises probability, which tends to give bland or repetitive open-ended text."

import heapq, math

EOS = "</s>"

def length_penalty(n, alpha):                 # Wu et al. (2016)
    return ((5 + n) ** alpha) / (6 ** alpha)

def beam_search(next_probs, width, max_len, alpha=0.6):
    beams = [((), 0.0)]                       # running: (tokens, sum of log probs)
    finished = []                             # (normalised score, tokens)
    for _ in range(max_len):
        cands = [(lp + math.log(p), toks + (tok,))
                 for toks, lp in beams
                 for tok, p in next_probs(toks).items()]
        beams = []
        for lp, toks in heapq.nlargest(width, cands):   # top-k, no full sort
            if toks[-1] == EOS:
                body = toks[:-1]
                finished.append((lp / length_penalty(len(body), alpha), body))
            else:
                beams.append((toks, lp))
        if not beams:
            break
        if len(finished) >= width and max(f[0] for f in finished) >= \
                max(l for _, l in beams) / length_penalty(max_len, alpha):
            break                             # no running beam can still win
    else:                                     # ran to max_len: close open beams
        for toks, lp in beams:
            finished.append((lp / length_penalty(len(toks), alpha), toks))
    return max(finished)