Beam Search and Decoding Strategies

Open WhatsApp, tap the message box, and start typing "Sending you the". Above the keyboard, Gboard or SwiftKey usually offers three small word suggestions — perhaps "money", "link", "file" — guesses at what comes next. You are not forced to take any of them, and notice that the keyboard is not fully committing to a single guess either: it keeps a few reasonable continuations visible at once, because the best full sentence is not always the one you get by grabbing whichever word looks best right now and never looking back.

That everyday habit — keeping more than one option open instead of betting everything on whatever looks best at this exact instant — sits at the heart of this chapter. Every AI system that produces text one word at a time, from a translation app converting a Hindi sentence into English, to a customer-support chatbot replying to "Where is my order?", to a captioning system turning speech into subtitles, runs into the same underlying problem. The model only ever answers one narrow question: given the words so far, how likely is each possible next word? It never directly tells you which complete sentence is best. Turning that stream of probabilities into an actual sentence is called decoding, and the strategy chosen for this last step changes the quality, style, and even the personality of the output far more than most people realize.

From Probabilities to a Sentence: Why Decoding Is a Search Problem

A neural sequence model — whether it powers translation, summarization, or a chat assistant — never outputs a full sentence in one shot. Given some context (a source sentence to translate, a question, or the words generated so far), it produces a probability distribution over its entire vocabulary for what the very next token should be. To produce a whole sequence, the model is applied again and again, each time feeding its own earlier output back in as part of the input for the next step. This repeated, self-feeding process is called autoregressive generation, and it means the probability of an entire finished sequence is simply the product of all these one-step conditional probabilities, chained together:

P(y1, y2, ..., yT | x) = P(y1|x) × P(y2|y1,x) × P(y3|y1,y2,x) × ... × P(yT|y1,...,y(T-1),x)

Turning this chain of probability distributions into one concrete sequence of words is the decoding problem. The most obvious strategy — try every possible sequence and keep whichever has the highest total probability — is called exhaustive search, and it sounds simple until the numbers are laid out. GPT-2, for example, uses a vocabulary of 50,257 subword tokens (word pieces, not always whole words). Exhaustively checking every possible 20-token sequence built from that vocabulary means evaluating roughly 50,257^20, which works out to about 10^94 candidate sequences. Physicists estimate the observable universe contains somewhere on the order of 10^80 atoms — so the number of candidate sentences already dwarfs the number of atoms in the universe, for a sentence you could read aloud in a few seconds. Exhaustive search is not merely slow; beyond a handful of words it is permanently, mathematically out of reach on any computer that will ever exist. Every practical decoding strategy is therefore a heuristic: a way of searching for a good sequence without ever examining all of them.

Greedy Decoding: Fast but Short-Sighted

The simplest heuristic is greedy decoding (also called greedy search): at every step, pick the single highest-probability next token, append it to the sequence, and move on, never reconsidering the choice. If the vocabulary has V tokens and the target sequence has T steps, greedy decoding only needs to evaluate the model T times, each time comparing V options — a total of T×V comparisons, compared with V^T for exhaustive search. This makes it extremely fast, and for many steps along the way it is a perfectly sensible choice.

Its flaw is that once a token is chosen, greedy decoding can never undo it, even if that choice turns out to trap the sequence in a mediocre continuation. A word that looks slightly better than the alternatives right now might lead only to weak words later, while a word that looks slightly worse right now might open the door to a far better sentence a few steps ahead. Greedy decoding has no way of looking that far ahead — it commits blindly, one step at a time.

Beam Search: Keeping Several Options Alive

Beam search is the middle ground between greedy decoding's single guess and exhaustive search's impossible completeness. Instead of tracking only the one best partial sequence at each step, it tracks the best k, where k is called the beam width (or beam size). At every step, the algorithm:

• takes each of the k sequences currently being tracked (usually called beams, or hypotheses),
• extends every one of them with every possible next token, producing k × V candidate sequences,
• scores each candidate by its cumulative probability, and
• keeps only the top k candidates, quietly discarding the rest.

This repeats until every surviving beam has produced an end-of-sequence token (a special marker meaning "the sentence is complete") or a maximum length is reached, at which point the highest-scoring completed sequence is returned as the output. Beam search is a genuine generalization of the two extremes already introduced: set the beam width k = 1 and it behaves exactly like greedy decoding, since only the single best candidate ever survives each round of pruning; remove the cap on k entirely, so that no candidate is ever pruned away, and every one of the V^T complete sequences survives to the end — which is exactly exhaustive search. The entire value of beam search lies in choosing a k large enough to escape greedy decoding's short-sightedness, but small enough to stay computationally practical — typically a modest number such as 4, 5, or 10, not thousands.

Worked Example: Decoding a Railway Chatbot's Reply

Suppose you are building a simple chatbot for a railway enquiry service, and it needs to generate a short reply to the question "Train status?", one word at a time. To make every step checkable by hand, assume a toy version of the model that only ever considers a handful of candidate words at each position — a real model would choose from tens of thousands of tokens, but the mechanics are identical. Two decoding strategies will be traced side by side: greedy decoding, and beam search with beam width k = 2.

For the very first word, the model predicts:

• P("Train") = 0.50
• P("Your") = 0.35
• P("Sorry") = 0.15

Greedy decoding picks the single highest-probability word, "Train" (0.50), and commits to it permanently. Beam search with k = 2 keeps the top two candidates alive instead — "Train" (0.50) and "Your" (0.35) — and quietly drops "Sorry" (0.15).

Now the model predicts the second word, conditioned on whichever first word was chosen. Given the prefix "Train", it predicts:

• P("is" | "Train") = 0.40
• P("status" | "Train") = 0.35
• P("no" | "Train") = 0.25

Given the prefix "Your", it predicts:

• P("train" | "Your") = 0.80
• P("ticket" | "Your") = 0.20

Greedy decoding only ever explored "Train", so it extends that single beam with its best next word, "is" (0.40), reaching the cumulative score 0.50 × 0.40 = 0.20 for "Train is".

Beam search extends both of its surviving beams by every option, scores all five resulting candidates by cumulative probability, and keeps only the best two:

• "Train is" → 0.50 × 0.40 = 0.200
• "Train status" → 0.50 × 0.35 = 0.175
• "Train no" → 0.50 × 0.25 = 0.125
• "Your train" → 0.35 × 0.80 = 0.280
• "Your ticket" → 0.35 × 0.20 = 0.070

Something important has already happened. "Your train" (0.280) now outscores "Train is" (0.200), even though "Train" alone (0.50) beat "Your" alone (0.35) at the very first step. Greedy decoding, having committed to "Train" and discarded "Your" forever, has no way of ever discovering this. Beam search, having kept both alive for one more step, survives with "Your train" (0.280) and "Train is" (0.200) as its two beams, dropping "Train status", "Train no", and "Your ticket".

One more step. Given "Train is", the model predicts:

• P("late" | "Train is") = 0.30
• P("delayed" | "Train is") = 0.45
• P("on-time" | "Train is") = 0.25

Given "Your train", it predicts:

• P("arrived" | "Your train") = 0.70
• P("delayed" | "Your train") = 0.20
• P("cancelled" | "Your train") = 0.10

Greedy decoding, still only tracking "Train is" (0.20), picks its best next word, "delayed" (0.45), and finally outputs "Train is delayed", with score 0.20 × 0.45 = 0.090.

Beam search expands both of its beams into six candidates:

• "Train is late" → 0.200 × 0.30 = 0.060
• "Train is delayed" → 0.200 × 0.45 = 0.090
• "Train is on-time" → 0.200 × 0.25 = 0.050
• "Your train arrived" → 0.280 × 0.70 = 0.196
• "Your train delayed" → 0.280 × 0.20 = 0.056
• "Your train cancelled" → 0.280 × 0.10 = 0.028

The winner is "Your train arrived", with a probability of 0.196 — more than double the 0.090 that greedy decoding settled for. Beam search reached a better answer for precisely the reason greedy decoding could not: it kept a second, slightly-less-promising-looking option alive long enough to discover that it blossomed into the best sentence overall. Notice, too, that this is not a guarantee of finding the true best sentence — the path starting with "Sorry" (0.15) was pruned away after the very first step, and if it happened to lead to an even better continuation than "Your train arrived", beam search with k = 2 would never find out. A wider beam reduces the chance of a good sequence being pruned too early, but short of setting the beam width to the full vocabulary size, it never eliminates that risk entirely.

Implementing Beam Search in Python

The trace above is exactly what the following implementation computes. The toy model is written as a lookup table instead of a neural network, but the beam search logic itself is the same logic a production system uses on top of a real model's output.

import math

# Toy "model": given the words generated so far, return next-word probabilities.
# In a real system this table would come from a neural network's softmax output.
def next_word_probs(prefix):
    if prefix == ():
        return {"Train": 0.50, "Your": 0.35, "Sorry": 0.15}
    if prefix == ("Train",):
        return {"is": 0.40, "status": 0.35, "no": 0.25}
    if prefix == ("Your",):
        return {"train": 0.80, "ticket": 0.20}
    if prefix == ("Train", "is"):
        return {"late": 0.30, "delayed": 0.45, "on-time": 0.25}
    if prefix == ("Your", "train"):
        return {"arrived": 0.70, "delayed": 0.20, "cancelled": 0.10}
    return {"<end>": 1.0}

def beam_search(beam_width, num_steps):
    beams = [((), 0.0)]  # each beam: (sequence_so_far, cumulative_log_probability)
    for step in range(num_steps):
        candidates = []
        for seq, score in beams:
            for word, prob in next_word_probs(seq).items():
                candidates.append((seq + (word,), score + math.log(prob)))
        candidates.sort(key=lambda pair: pair[1], reverse=True)
        beams = candidates[:beam_width]
        print(f"After step {step + 1}:")
        for seq, score in beams:
            print(f"  {' '.join(seq):25s} prob = {math.exp(score):.4f}")
    return beams[0]

def greedy_search(num_steps):
    seq, score = (), 0.0
    for _ in range(num_steps):
        probs = next_word_probs(seq)
        best_word = max(probs, key=probs.get)
        seq = seq + (best_word,)
        score += math.log(probs[best_word])
    return seq, score

best_seq, best_score = beam_search(beam_width=2, num_steps=3)
print("\nBeam search output:", " ".join(best_seq), f"(probability = {math.exp(best_score):.4f})")

greedy_seq, greedy_score = greedy_search(3)
print("Greedy search output:", " ".join(greedy_seq), f"(probability = {math.exp(greedy_score):.4f})")

Running this program prints:

After step 1:
  Train                     prob = 0.5000
  Your                      prob = 0.3500
After step 2:
  Your train                prob = 0.2800
  Train is                  prob = 0.2000
After step 3:
  Your train arrived        prob = 0.1960
  Train is delayed          prob = 0.0900

Beam search output: Your train arrived (probability = 0.1960)
Greedy search output: Train is delayed (probability = 0.0900)

Every number matches the hand trace exactly, because it is the same computation. The only difference is that the code tracks cumulative log-probabilities internally (score + math.log(prob)) rather than multiplying raw probabilities directly, and only converts back with math.exp for the printout. Real production systems make the same choice, for the reason explored next.

Why Log-Probabilities? Numerical Stability and the Length Bias Problem

Probabilities are numbers between 0 and 1, so multiplying many of them together shrinks the result extremely fast. Even a modest 20-word sequence made of moderately confident predictions (say, around 0.3 each) has a true probability near 0.3^20 ≈ 3.5 × 10^-11, and realistic sentences are often far longer than that. Neural networks are frequently run using reduced-precision number formats for speed, which have a far smaller representable range than ordinary double-precision arithmetic, and multiplying enough small probabilities together in that format can underflow all the way to a stored value of exactly 0.0 — at which point two genuinely different candidate sequences become computationally indistinguishable, both looking equally, and wrongly, impossible. Taking the logarithm sidesteps the problem entirely: log(a × b) = log(a) + log(b), so a long chain of multiplications becomes a long chain of additions, and because the logarithm is a strictly increasing function, it never changes which of two sequences scores higher. Working in log-space is simply a numerically safer way to compute the exact same comparison — which is exactly why the Python code above accumulates score + math.log(prob) instead of score * prob.

This trick exposes a side effect that every decoding system has to correct for. Because probabilities never exceed 1, their logarithms are always zero or negative, so every additional word appended to a sequence can only make its cumulative log-probability more negative, never less. A short, safe, generic sequence therefore tends to score better than a longer, more informative one, simply because it accumulates fewer negative terms — not because it is actually the better answer. This is the length bias problem, and left uncorrected it pushes beam search toward short, clipped outputs.

The standard fix is length normalization: instead of comparing raw cumulative log-probabilities, divide by the sequence length before comparing finished candidates (production systems often divide by length raised to a tunable power between roughly 0.6 and 1, rather than by the raw length, but plain length division already illustrates the idea). Consider two finished candidates: sequence A has a cumulative log-probability of −1.6 after 3 words, an average of about −0.53 per word; sequence B has a cumulative log-probability of −2.4 after 6 words, an average of about −0.40 per word. Compared without normalization, A looks better, since −1.6 is greater than −2.4. Compared after dividing by length, B looks better, since −0.40 is greater than −0.53 — and B is, on a per-word basis, actually the more confident sequence; it only looked worse before because it was being penalized simply for saying more. Any production system that runs beam search over outputs of varying length — translation being the classic case — applies some form of length normalization for exactly this reason.

Beyond Beam Search: Sampling-Based Decoding

Beam search is an excellent choice when a task has something close to one correct answer: translating a sentence, summarizing a paragraph, transcribing speech into captions. But for open-ended generation, where many different continuations could all be perfectly good — writing a short story, chatting with a user, brainstorming ideas — beam search has a surprising weakness: it tends to produce dull, repetitive, oddly generic text. Researchers studying this problem, notably Holtzman, Buys, Du, Forbes, and Choi in their widely cited 2019 paper "The Curious Case of Neural Text Degeneration," found that forcing a language model to always output its single highest-probability sequence, whether through greedy decoding or beam search, often leads to bland or looping phrases. The genuinely highest-probability continuation of a long passage is frequently the safest, most generic one available, and once a repetitive loop becomes the highest-scoring option, beam search keeps choosing it. Human writing does not work this way: it is probable in a broad statistical sense, but rarely the single most probable word at every position.

The alternative is to sample rather than search: instead of hunting for the sequence with the highest score, draw each next token randomly from the model's predicted probability distribution, the way a loaded die favours its more likely faces without ever ruling out the others. Pure random sampling from the full distribution introduces plenty of variety, but it also gives even wildly unlikely, nonsensical tokens a small chance at every single step, and over a long passage that small chance becomes almost certain to eventually produce something broken. Three refinements keep sampling controllable:

• Temperature rescales the model's output distribution before sampling. Given the model's raw pre-softmax scores (logits) z for each vocabulary item, temperature-scaled probabilities are computed as P(i) = exp(z_i / T) ÷ Σ_j exp(z_j / T). A temperature below 1 sharpens the distribution, making the model's favourite words even more dominant and pushing output toward greedy decoding as T approaches 0; a temperature above 1 flattens the distribution, giving less-likely words a fairer chance and making output more varied and surprising, at the cost of coherence if pushed too far.
• Top-k sampling, introduced by Fan, Lewis, and Dauphin in 2018, restricts sampling to only the k most probable tokens at each step, renormalizing their probabilities to sum to 1 and ignoring everything outside that shortlist, so the model can never accidentally pick a wildly improbable word while still choosing randomly among the reasonable ones.
• Top-p sampling, also called nucleus sampling — the technique proposed in the Holtzman et al. paper mentioned above — instead keeps the smallest set of tokens whose cumulative probability adds up to at least p (a common choice is p = 0.9), then samples only from that set. Its advantage over top-k is that the shortlist size adapts automatically: when the model is very confident and one or two words dominate, the nucleus is small and the output stays precise; when the model is genuinely unsure and probability is spread thinly across dozens of plausible words, the nucleus grows and the output is allowed to explore that uncertainty.

This is why the same underlying model can feel completely different depending on how it is decoded: a translation feature answering a factual query is usually run with beam search or low-temperature decoding to stay accurate and consistent, while a conversational assistant or story-writing tool is usually run with temperature and top-p sampling so it sounds natural and does not repeat itself.

Picking a Strategy in Practice

None of these strategies is universally best — the right choice depends on the task, and production systems typically expose it as a tunable setting rather than hard-coding one answer:

• Tasks with something close to one correct target answer — translation, summarization, transcription — generally favour beam search with a modest width (commonly a single-digit number such as 4 to 10) combined with length normalization.
• Open-ended or creative tasks — chat, story generation, brainstorming — generally favour temperature and top-p sampling, sometimes combined with a light top-k cutoff purely as a safety net against nonsense tokens.
• Tasks that need one specific, highly reliable answer, such as generating code that must compile, often favour greedy decoding or a small beam, sometimes run several times at low temperature so the best of a few attempts can be selected.

Beam width itself is a trade-off, not a dial to be maximized. Widening the beam from 1 to a small number typically improves output quality quickly, because it fixes greedy decoding's worst short-sightedness. As one well-known data point, Google's 2016 neural machine translation system was commonly reported to use a beam width around 8, combined with length normalization. But researchers studying machine translation have repeatedly found that quality gains taper off, and can even reverse, once the beam grows large — a phenomenon sometimes called the beam search curse. A wider beam is better at finding the sequence the model itself rates highest, but the model's own top-rated sequence is not always the one a human reader would judge best, especially once very long or unusual candidates start entering the running. In practice, small beam widths usually capture nearly all of beam search's benefit at a fraction of the computational cost of a large one.

Next time three words hover above your keyboard while you type a message, or a translation app hands back a slightly stiff but accurate sentence, or a chatbot answers in a way that feels natural and varied rather than robotic, that is a decoding strategy at work behind the scenes. The language model itself never produces a sentence — it only ever answers the question "what could come next, and how likely is each option?" Every finished reply from a translation app, a predictive keyboard, or a conversational AI assistant was assembled, one probability distribution at a time, by an algorithm like the ones in this chapter, deciding which words to keep, which to discard, and which to gamble on.

Think About It

Think about this: How would you explain beam search and decoding strategies to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind beam search and decoding strategies, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.