Greedy decoding takes the best next token and can regret it. Beam search keeps several options alive and picks at the end.
Overview
The architecture
Encoder-decoder handles the case where input and output are both sequences and their lengths differ — translation, summarisation, speech to text.
The encoder reads the input and makes a form. The decoder emits output tokens one at a time, each conditioned on the form and on all it has emitted so far.
The first version compressed the whole input into a single fixed vector, which became the bottleneck that motivated focus: let the decoder look back at each input spot rather than at one summary. That is the change the field turned on, and the transformer is its conclusion.
Autoregressive decoding isn't exact to that architecture. Any model that emits one token at a time faces the same question: at each step you've a chance over the vocab, and you've to choose.
Seq2seq and Beam Search
This module needs JavaScript: the
numbers are computed in the page rather than recorded.
Worth knowing
An encoder reads the input into a representation; a decoder emits tokens one at a time, conditioned on what it has already emitted.
Greedy decoding takes the highest-probability token at each step. It cannot reconsider.
Beam search keeps the k best partial sequences and expands all of them, choosing only at the end.
Sequence probabilities are products, so short sequences win. Length normalisation is not optional.
Seq2seq and Beam Search
How a model that emits one token at a time chooses a whole sequence. Why the obvious method isn't the best one.
Greedy decoding, and its regret
Take the most probable token each time.
Fast, simple, and it optimises the wrong thing. You want the most probable *sequence*, and the highest-chance first token can lead into a region where all that follows is bad.
The chart shows the cumulative log chance of the beam's paths. With the width at 1 you get greedy decoding, and the readout checks it against the best sequence a wider beam found. It's often worse, and the reason is always the same: it committed early to a thing that looked good and didn't pay off.
Beam search
Keep the k best partial sequences. At each step, expand all of them, score each continuation, keep the best k total, and continue. At the end, take the best complete sequence.
Drag the width from 1 upward and watch the best score improve.
It's still a heuristic. It does not find the globally best sequence — that would need searching an exponentially large tree — and a path discarded early because it looked weak can never come back, even if it led a place great. Beam search only reduces how often that happens.
The length problem
Sequence chance is a product of per-token chances, so each extra token times by a thing less than 1. Longer sequences have lower chance, always, and unnormalised beam search so has a systematic bias toward stopping early.
The standard fix cuts the log chance by the length, at times raised to a tunable power. It's a correction with no principled derivation, it's needed, and each production decoder has one.
Wider is not always better
Raise the width past about 5 and translation quality often *falls*. This is called the beam search curse, and it's well documented.
The explanation is that a wider beam finds sequences the model truly considers more probable, and the model's notion of probable isn't the same as good. Very high-chance text is bland: it's the safe, plain continuation. A wider search is a more faithful search of a flawed goal.
That is also why open-ended generation abandons beam search fully. Sampling methods — temperature, top-k, nucleus — on purpose don't take the most probable path, because for creative text the most probable path is the boring one. Beam search lives where there's a right answer: translation, speech spotting, constrained generation.
Where greedy loses, on a tree you can check
The claim that greedy decoding optimises the wrong thing is a two-step example away. Suppose the first token is A with chance 0.6 or B with 0.4, and the best continuation after each is:
first token
P(first)
best P(second)
sequence probability
A
0.6
0.5
0.30
B
0.4
0.9
0.36
Greedy takes A, because 0.6 beats 0.4, and lands on a sequence of chance 0.30. Beam search with width 2 keeps both A and B alive, discovers that B leads to a 0.9 continuation, and returns the 0.36 sequence — the more probable *sequence*, which the greedy first choice ruled out at step one. That is the entire arg for beam search: the highest-chance first token can open into a region where all after it's worse.
It's still a heuristic, not a global search, and it has its own trap. Sequence chance is a product of per-token terms. So Each extra token times by a thing below 1 and longer sequences score lower automatically — which is why unnormalised beam search truncates, and why each production decoder cuts the log-chance by length. Widen the beam too far and quality can even fall, because a more faithful search of the model's chance finds the blandest, safest text. That is the beam-search curse, and it's why open-ended generation samples instead.
The deeper reason open-ended generation abandons beam search is that the model's notion of probable isn't the same as good. A more faithful search of the chance surface settles on the safe, plain continuation — the blandest text is often the most probable. So past a beam width of about five, translation and summarisation quality can fall rather than rise. Beam search earns its place only where there's a truly correct answer to find: translation, speech spotting, constrained decoding. For creative text, temperature, top-k and nucleus sampling on purpose avoid the most probable path, because that path is just the one worth leaving.
And the cost isn't free: a beam of width k times both work and memory by k, which for a large model is often the binding constraint long before quality is, so the width is chosen against a hardware budget as much as against the translation it buys.
Where it goes wrong with Seq2seq and Beam Search
No length norming. All comes out truncated.
A very wide beam on open-ended text. Blander, not better.
Using beam search for creative generation. Use sampling.
Losing the cost. Width k times both work and memory by k, and for a large model that is the binding constraint.
Questions people ask about Seq2seq and Beam Search
What is a seq2seq model? An encoder reads the input sequence into a representation and a decoder generates the output sequence one token at a time.
Why is greedy decoding not enough? Picking the best token at each step can lock you into a poor path. A slightly worse first word may lead to a much better whole sentence.
How does beam search work? It keeps the k best partial sequences at each step and extends all of them. At the end it returns the best complete one.
Why does beam search favour short outputs? Each token multiplies in a probability below one, so longer sequences score lower. Length normalisation or a length penalty corrects this.
Is a larger beam always better? No. Past a modest width, quality can drop, and very wide beams tend to produce bland, repetitive text.
When do I sample instead? For creative generation where diversity matters. Use top-k or nucleus sampling rather than a beam, which suits tasks with a single right answer such as translation.
Greedy decoding, and the sentence it cannot find
At each step a decoder picks a token. Taking the most likely one each time isn't the same as finding the most likely sentence -- here is a case where it demonstrably isn't.
example_01.pyNumPy
import numpy as np
# a tiny decoder: at each step, the probability of the next token given the
# sequence so far. three tokens: A, B, and <end>.
TOK = ["A", "B", "."]
TABLE = {
(): [0.55, 0.45, 0.00], # A looks better than B here
("A",): [0.30, 0.30, 0.40], # ...but every path out of A is poor
("B",): [0.01, 0.01, 0.98], # ...while B has one strong ending
("A", "A"): [0.05, 0.05, 0.90],
("A", "B"): [0.05, 0.05, 0.90],
("B", "A"): [0.05, 0.05, 0.90],
("B", "B"): [0.05, 0.05, 0.90],
}
def probs(seq):
return np.array(TABLE.get(tuple(seq), [0.0, 0.0, 1.0]))
print("a decoder over three tokens: A, B and '.' (end of sentence).")
print("its first step:")
p0 = probs([])
for t, p in zip(TOK, p0):
print(" P(%s) = %.2f" % (t, p))
print()
print("GREEDY decoding takes the argmax at every step:")
seq, logp = [], 0.0
while True:
p = probs(seq)
i = int(p.argmax())
logp += np.log(p[i])
seq.append(TOK[i])
print(" step %d: picked %s (p=%.2f), sequence so far: %s"
% (len(seq), TOK[i], p[i], " ".join(seq)))
if TOK[i] == "." or len(seq) > 5:
break
greedy_seq, greedy_logp = list(seq), logp
print(" result: %s log-probability %.4f (p = %.4f)"
% (" ".join(greedy_seq), greedy_logp, np.exp(greedy_logp)))
Output
The next block exhaustively enumerates every sequence and shows which one is actually the most probable.
example_02.pyNumPy
import numpy as np
TOK = ["A", "B", "."]
T = {(): [.55,.45,0], ("A",): [.3,.3,.4], ("B",): [.01,.01,.98], ("A","A"): [.05,.05,.9],
("A","B"): [.05,.05,.9], ("B","A"): [.05,.05,.9], ("B","B"): [.05,.05,.9]}
def probs(s): return np.array(T.get(tuple(s), [0.,0.,1.]))
seq, lp = [], 0.0
while len(seq) < 6:
p = probs(seq); i = int(p.argmax()); lp += np.log(p[i])
seq.append(TOK[i])
if TOK[i] == ".": break
greedy_seq, greedy_lp = list(seq), lp
def enum_all(s=(), lp=0.0, out=None):
out = [] if out is None else out
if s and s[-1] == "." or len(s) > 4:
out.append((list(s), lp)); return out
p = probs(list(s))
for i, t in enumerate(TOK):
if p[i] > 0: enum_all(s+(t,), lp+np.log(p[i]), out)
return out
everything = sorted(enum_all(), key=lambda kv: -kv[1])
print("but here is EVERY sequence this decoder can produce, ranked:")
print("%22s %16s %14s" % ("sequence", "log-probability", "probability"))
for s, lp in everything[:6]:
mark = " <- greedy found this" if s == greedy_seq else ""
print("%22s %16.4f %14.4f%s" % (" ".join(s), lp, np.exp(lp), mark))
print()
best_seq, best_lp = everything[0]
print("the most likely sequence is '%s' at p=%.4f."
% (" ".join(best_seq), np.exp(best_lp)))
print("greedy decoding returned '%s' at p=%.4f -- it is %.1fx less likely."
% (" ".join(greedy_seq), np.exp(greedy_lp), np.exp(best_lp - greedy_lp)))
print()
p0 = probs([])
print("greedy went wrong at the very first step. A looked better than B")
print("(%.2f against %.2f), and it is -- for one token. but every path out"
% (p0[0], p0[1]))
print("of A is mediocre, while B has one strong ending. a locally optimal")
print("choice, globally wrong, and greedy has no way to find that out")
print("because it never looks past the token in front of it.")
Output
The next block runs beam search and shows how widening the beam finds the better sequence.
example_03.pyNumPy
import numpy as np
TOK = ["A", "B", "."]
T = {(): [.55,.45,0], ("A",): [.3,.3,.4], ("B",): [.01,.01,.98], ("A","A"): [.05,.05,.9],
("A","B"): [.05,.05,.9], ("B","A"): [.05,.05,.9], ("B","B"): [.05,.05,.9]}
def probs(s): return np.array(T.get(tuple(s), [0.,0.,1.]))
def beam_search(k):
beams, finished = [([], 0.0)], []
for _ in range(5):
cand = []
for seq, lp in beams:
if seq and seq[-1] == ".":
finished.append((seq, lp)); continue
p = probs(seq)
for i, t in enumerate(TOK):
if p[i] > 0: cand.append((seq+[t], lp+np.log(p[i])))
if not cand: break
beams = sorted(cand, key=lambda kv: -kv[1])[:k]
return sorted(finished + beams, key=lambda kv: -kv[1])[0]
def enum_all(s=(), lp=0.0, out=None):
out = [] if out is None else out
if s and s[-1] == "." or len(s) > 4:
out.append((list(s), lp)); return out
p = probs(list(s))
for i, t in enumerate(TOK):
if p[i] > 0: enum_all(s+(t,), lp+np.log(p[i]), out)
return out
best_lp = sorted(enum_all(), key=lambda kv: -kv[1])[0][1]
print("BEAM SEARCH keeps the k best partial sequences instead of one:")
print("%8s %22s %16s" % ("beam k", "result", "log-probability"))
for k in (1, 2, 3, 5):
s, lp = beam_search(k)
print("%8d %22s %16.4f%s"
% (k, " ".join(s), lp, " <- optimal" if abs(lp - best_lp) < 1e-9 else ""))
print(" k=1 IS greedy decoding -- that is the definition. widening the beam")
print(" to 2 is enough to find the answer here.")
print("beam search is still not guaranteed to find the best sequence. it is")
print("a heuristic that explores k times as much and can still prune the")
print("winner early. for a 50,000 token vocabulary and 20 tokens, exhaustive")
print("search would take 10^94 sequences.")
Output
The next block shows why beam search needs length normalisation.
example_04.pyNumPy
import numpy as np
TOK = ["A", "B", "."]
T = {(): [.55,.45,0], ("A",): [.3,.3,.4], ("B",): [.01,.01,.98], ("A","A"): [.05,.05,.9],
("A","B"): [.05,.05,.9], ("B","A"): [.05,.05,.9], ("B","B"): [.05,.05,.9]}
def probs(s): return np.array(T.get(tuple(s), [0.,0.,1.]))
def enum_all(s=(), lp=0.0, out=None):
out = [] if out is None else out
if s and s[-1] == "." or len(s) > 4:
out.append((list(s), lp)); return out
p = probs(list(s))
for i, t in enumerate(TOK):
if p[i] > 0: enum_all(s+(t,), lp+np.log(p[i]), out)
return out
everything = sorted(enum_all(), key=lambda kv: -kv[1])
print("one practical wrinkle: longer sequences have lower probability, always,")
print("because you multiply by another number below 1 at every step:")
for s, lp in everything[:5]:
print(" %-12s length %d, log-prob %8.4f, normalised %8.4f"
% (" ".join(s), len(s), lp, lp / len(s)))
print(" ranking by raw probability therefore favours short outputs. beam")
print(" search implementations divide by length (or length^alpha) to")
print(" correct for it, and that alpha is a real hyperparameter.")
Output
Check yourself
0 of 3
Answer without scrolling back up.
Why can greedy decoding produce a worse sequence than beam search?
The highest-probability first token can lead into a region where everything that follows is bad, and greedy decoding has no way back.
Why does beam search need length normalisation?
Unnormalised beam search has a systematic bias toward stopping early. The fix has no principled derivation and every production decoder has one.
Why does a very wide beam often make translation worse?
The beam search curse. It is also why open-ended generation uses sampling instead - for creative text the most probable path is the boring one.
Cheat sheet
Seq2seq and Beam Search
Feed a sequence into an encoder, decode one token at a time, and compare greedy search with beam search to see how wider beams change output.
DEEP LEARNING · vizlearn.in/deep_learning/seq2seq_and_beam_search.html
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.