Beam Search
Keep a few best guesses alive at each word instead of locking in one, then keep the few full sentences with the best total score.
Why Does This Exist?
Greedy decoding takes the best word right now and never looks back. That feels safe until one confident pick ruins the sentence. Say the model rates The at 0.60 and A at 0.30, so you take The. The next words after The then fall flat, while A cat would have sailed through. You can't undo the first call, and the full sentence pays for it.
Beam width is the fix for that regret. Instead of one live sentence you keep of them, where is just a count you choose. Each step you grow every kept sentence by one word, score each grown sentence by its whole history, and keep only the best . You pay about times the work to avoid betting everything on the first word.
This page is about that loop and its bill: how totals are scored, how pruning picks winners, and where the habit bites back. The full menu of choices lives in decoding strategies. The numbers being added come from next-token prediction, where the model turns a prompt plus words so far into a probability for each next word.
Think of It Like This
A search party with two radios
You and a friend are hunting for the best food street in a new city at night. You split at the first corner. You take the wider street while your friend follows a smell down the narrower one.
At each next corner you both split again and radio back what you see, so four walks exist for a moment. Then you compare the whole evening so far, keep the two walks with the best night to this point, and call the other two back. You repeat this at every corner.
The number of walks you keep out is the beam width. Splitting is expansion. Judging the whole evening is the cumulative score. Calling walkers back is pruning.
Where it stops: streets hide one real best dinner, while language has no single right next sentence, only higher scoring ones. And calling a friend back costs one text, while cutting a beam still leaves its memory and compute bill behind. That's why wide beams get expensive.
How It Actually Works
You've already met the raw material. At each step the model hands you one probability per vocabulary word, given the prompt and the words picked so far. Beam search never changes those beliefs. It only decides which histories get to continue.
Call the prompt , in plain words the text you started from. Call the words picked through position by , meaning the full prefix so far. Call one candidate for position by . Then is the model's probability for that candidate next word given the prefix and the prompt. Call the beam width, the count of guesses you keep. Call the cumulative score, the sum of log probabilities along one full guess:
In words: walk along the guess, take the log of each step's probability, and add them. Order is preserved because the log keeps order, and sums replace products that would shrink toward zero in floating point.
Each step runs the same three moves. Start with live prefixes. Expand each one by asking the model for its next word distribution and growing a shortlist of continuations, up to per prefix. Score every grown guess with . Prune back to the best and drop the rest. Repeat until the survivors pick the end token or hit your length cap, then return the best finished guess.
Why add logs instead of multiplying
A path's honest probability is the product of its steps, but products of small numbers collapse fast and hide differences. Logs turn that product into a sum with the same ranking, and sums stay readable. So the code adds at each step instead of multiplying . Lower still means worse here, because every log probability is zero or negative: a total closer to zero outranks one further below it.
Worked example with beam width 2
Take and the tiny choice from the picture. First words: The at 0.60, A at 0.30. In logs that is about and , so both survive the first cut as your two beams.
Next the model scores continuations. After The: cat at 0.50, dog at 0.40. After A: cat at 0.90, bird at 0.05. Add each continuation's log to its prefix:
The cat:The dog:A cat:A bird:
As plain products that is 0.30, 0.24, 0.27, and 0.015, the same order. Keep the best two: The cat at and A cat at . Cut The dog at and A bird at . Notice the recovery: A started weaker, but A cat still beats The dog because the second step was strong. That's the whole point. Greedy would have locked in The and then been stuck choosing between its children. Beams let the weaker start prove itself one step later.
Stopping and the length catch
A guess ends when it picks the end token or hits your cap. You'll usually pick the best finished guess, not the best live one, because live ones haven't paid their full price yet.
And totals tilt short. Every extra word adds one more zero or negative log, so longer guesses run lower by construction. Without a fix, beams return stubs. The standard repair divides the total by length before comparing, so a good long sentence can beat a bland short one. You'll meet that repair again under length handling in decoding strategies.
The trade is plain. You buy better totals with about times the memory and compute, since each beam carries its own context through the KV cache. Returns shrink fast past small widths, and the extra winners tend to look alike. The bet underneath is that higher model probability means better text. That holds for tight tasks with one compact right answer, like translation or short factual summaries, especially paired with constrained decoding. It fails for open chat, stories, and jokes, where the best line is often the rarer one. Don't pay beam prices there.
Code
The point of this snippet is the check, not the formula. It replays the worked example's prune step so you can see the weaker start survive in code you'd actually run.
import math
def add_log(prefix_logp: float, next_p: float) -> float: return prefix_logp + math.log(next_p)
the: float = math.log(0.60)a: float = math.log(0.30)
cands: list[tuple[str, float]] = [ ("The cat", add_log(the, 0.50)), ("The dog", add_log(the, 0.40)), ("A cat", add_log(a, 0.90)), ("A bird", add_log(a, 0.05)),]cands.sort(key=lambda c: c[1], reverse=True)kept = cands[:2]
print(f"{kept[0][0]} {kept[0][1]:.2f}") # -> The cat -1.20print(f"{kept[1][0]} {kept[1][1]:.2f}") # -> A cat -1.31Both kept guesses match the hand totals above to two decimals, and A cat outranks The dog exactly as the picture shows. Sums of logs pick the same winners as products of probabilities, which is the behavior the prune step relies on.
Watch Out For
Short answers always win the sum
Your beam keeps returning stubs. One word plus the end token beats two good sentences, and raising the width only finds shorter stubs faster.
That's length bias, not bad luck. Every step adds zero or a negative number, so totals fall as guesses grow. A one word guess paid once while a twelve word guess paid twelve times.
Fix it before you judge quality. Divide each finished total by its length before comparing, and only rank finished guesses against each other. If your stack exposes a length penalty setting, start with plain division by length and tune from there. Don't compare a live prefix against a finished sentence.
Safe text that loops
You aim beam search at a story or open chat and get the dullest paragraph in the room, then the same clause twice. Lowering the width a little doesn't cure it.
Beams reward what the model finds most predictable, and predictable means frequent and safe. Rare words die in the first prune even when they're the interesting choice, and once a safe phrase leads, its continuations look safe too, so the beam walks in circles. That's why open ended sampling plus repetition penalties reads more alive for creative work.
Use beams where one compact right answer exists, and put shape rules in constrained decoding instead of hoping the scores enforce them.
The Quick Version
- Beam search keeps full guesses alive and grows them together instead of locking in one word at a time.
- Each guess carries the sum of its log probabilities, so the whole history decides who survives the next prune.
- With ,
The catat andA catat survive whileThe dogat is cut, even thoughThestarted stronger. - Beam search costs about times the memory and compute of greedy, and finished guesses need length normalization because longer sums run lower.
- Beam search favors safe frequent words and can loop, so open chat and stories read better with sampling plus a repetition penalty.
- Beam search fits tight tasks with one compact right answer, and hard output shapes belong in constrained decoding.