# 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.

<div data-sim="beam"><p>Interactive simulation. It needs JavaScript; the text below explains what it shows.</p></div>

## 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.

<div class="cl-start"></div>

### Step 1 · Beam search over a toy language model

```python
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

```python
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.

<div class="cl-end"></div>

## More simulations

[← KV cache](/ai-simulations/kv-cache) · [All AI Simulations](/ai-simulations) · [LoRA →](/ai-simulations/lora)
