Greedy decoding vs beam search, with length penalty
Picking the most likely word at every step does not give the most likely sentence. Beam search keeps several partial sentences alive and finds better ones; see exactly how.
Interactive simulation. It needs JavaScript; the text below explains what it shows.
What you are looking at
The tree shows every candidate at every step with its probability; kept beams are bright, pruned ones faint. The panel ranks the finished and live sentences by log-probability divided by length to the power α.
Things to try
- Run with width 1 (greedy), then with width 2.
- Raise the length penalty and see longer sentences win.
- Step through slowly to see where greedy goes wrong.
How it works in real systems
Machine translation and speech recognition use beam widths of about 4 to 10. Chat models sample instead (see the sampling simulation), because beam search tends to produce generic, repetitive text.
Code lab
The same idea in real code, step by step. Copy each block into a notebook or a file and run it in order.
Step 1 · Beam search over a toy language model
import math
LM = {"The": {"nice": .5, "dog": .4, "car": .1}, "nice": {"woman": .4, "house": .3, "guy": .3}, "dog": {"has": .9, "runs": .05, "and": .05},
"car": {"drives": .5, "is": .3, "turns": .2}, "woman": {".": 1}, "house": {".": 1}, "guy": {".": 1}, "has": {"a": .5, ".": .5},
"runs": {".": 1}, "and": {".": 1}, "drives": {".": 1}, "is": {".": 1}, "turns": {".": 1}, "a": {"ball": 1}, "ball": {".": 1}}
def beam_search(k, alpha=0.0, max_len=6):
beams, done = [(["The"], 0.0)], []
for _ in range(max_len):
cand = [(toks + [w], lp + math.log(p)) for toks, lp in beams for w, p in LM.get(toks[-1], {".": 1}).items()]
cand.sort(key=lambda c: c[1] / (len(c[0]) - 1) ** alpha, reverse=True)
beams = []
for toks, lp in cand[:k]:
(done if toks[-1] == "." else beams).append((toks, lp))
if not beams: break
return sorted(done + beams, key=lambda c: c[1] / (len(c[0]) - 1) ** alpha, reverse=True)
print(beam_search(1)[0]) # greedy: The nice woman .
print(beam_search(2)[0]) # beam: The dog has ... (higher total probability)
Step 2 · In Hugging Face
from transformers import AutoTokenizer, AutoModelForSeq2SeqLM
tok = AutoTokenizer.from_pretrained("Helsinki-NLP/opus-mt-en-de"); m = AutoModelForSeq2SeqLM.from_pretrained("Helsinki-NLP/opus-mt-en-de")
x = tok("The dog has a ball.", return_tensors="pt")
for k in (1, 4):
out = m.generate(**x, num_beams=k, length_penalty=1.0, num_return_sequences=1, max_new_tokens=30)
print(k, tok.decode(out[0], skip_special_tokens=True))
Translation and speech recognition use beam search; open-ended chat uses sampling, because beam search tends to produce bland, repetitive text.