# Greedy and beam search

> Greedy decoding takes the argmax token; beam search keeps the B best prefixes and ranks them by log P / len^α. Both maximise likelihood, so they suit closed tasks but loop on open-ended LLM text.

Source: https://www.mlfoundry.in/learn/greedy-and-beam-search  
Section: Generative AI › Decoding and Generation Control  
Level: core · 8 min read · updated 2026-10-21

**Greedy and beam search:** are the two **deterministic** decoding rules for an autoregressive model. **Greedy** decoding appends $y_t=\arg\max_w P(w\mid y_{<t},x)$ at every step. **Beam search** keeps the $B$ highest-scoring partial outputs, extends each by every token, and keeps the best $B$ again; $B=1$ is greedy. Both try to find the most probable output. Holtzman, Buys, Du, Forbes and Choi ("The Curious Case of Neural Text Degeneration", ICLR 2020) showed why that goal fails for open-ended text.

This article is the practitioner's view. The algorithm, its bookkeeping and its history in machine translation are in **Beam search**. Here the questions are what greedy and beam search do to LLM output, which knobs matter, and when to choose them over **Temperature sampling** and **Top-k and top-p sampling**.

In an LLM stack the decoding rule sits after the forward pass that produces next-token logits and before detokenisation. Greedy is what you get from Hugging Face `generate` with `do_sample=False` and `num_beams=1` (the default), and roughly what hosted APIs give at `temperature=0`. Beam search is available in open-source stacks such as Hugging Face `generate` (`num_beams`) and vLLM. Hosted chat APIs generally expose sampling parameters only.

## The two rules

$$
\text{greedy: } y_t=\arg\max_{w\in\mathcal V}\log P(w\mid y_{<t},x)\qquad\qquad \text{beam: } \hat Y=\arg\max_{Y\in\mathcal F}\ \frac{\sum_{t=1}^{|Y|}\log P(y_t\mid y_{<t},x)}{|Y|^{\alpha}}
$$

- $\mathcal V$: the vocabulary, including the end-of-sequence token </s>
- $\mathcal F$: finished hypotheses collected by a width-$B$ beam (plus the alive ones if the length limit is hit)
- $\alpha$: length penalty exponent; Hugging Face `length_penalty`, default 1.0. $\alpha=0$ ranks by raw log-probability, which favours short outputs

> Figure: Two steps after the prompt "Paris is". Greedy commits to "the" (0.50) and then "capital" (0.36), for a joint probability of 0.180. A beam of width 2 also keeps "a" (0.40), scores 2 × 3 = 6 continuations and finds "a city" at 0.40 × 0.85 = 0.340. The locally second-best first token leads to the better sequence.

Greedy costs one forward pass per token. Beam search costs $B$ forward passes per token (batched together) and $B$ copies of the **KV cache**, reordered by parent beam after every step. Paged KV memory lets beams share the blocks of their common prefix (see **PagedAttention**), but at batch level a beam of 4 still takes roughly the serving capacity of 4 requests.

## Why maximisation degenerates

Holtzman et al. continued WebText passages with GPT-2 Large. Greedy and beam outputs fell into loops: the model repeats a phrase, and each repetition makes the next more likely. Xu et al. ("Learning to Break the Loop", NeurIPS 2022) measured this **self-reinforcement** directly: the probability of repeating a sentence grows with the number of times it already appears in the context.

The second finding is that human text is not the most probable text. Its per-token probability varies widely, with frequent low-probability words. Beam output stays uniformly high-probability. So searching harder for the argmax sequence moves the output further from human text, not closer.

Holtzman et al. (2020), Table 1: GPT-2 Large continuations of WebText. Perplexity is the model's own perplexity of the generated text; repetition is the share of continuations that end in a repeating loop.

| Decoding | Perplexity | Repetition % |
| --- | --- | --- |
| Human text | 12.38 | 0.28 |
| Greedy | 1.50 | 73.66 |
| Beam search, b = 16 | 1.48 | 28.94 |
| Pure sampling | 22.73 | 0.22 |
| Nucleus, p = 0.95 | 13.13 | 0.36 |

Length normalisation makes this worse for chat. A loop has a high **average** log-probability per token, so dividing by $|Y|^\alpha$ rewards running on. In the figure below, the loop wins once $\alpha\ge0.97$.

> Figure: A toy bigram model whose likeliest path loops ("i do not know . i …"), decoded for at most 12 tokens. Defaults (B = 4, α = 1): greedy and beam return the same cut-off loop, log P −6.907, p = 0.0010, 50% repeated trigrams; the beam scored 105 candidates. Exhaustive search over all 1,722 finished outputs agrees that the best by log P / len is a loop that then stops ("… know . </s>", −6.415 / 11 = −0.583). At α = 0 the beam returns "i do not know . </s>" (p = 0.0284) for B = 2–4. Only B ≥ 5 finds the true maximum "what you mean </s>" (p = 0.0576). Turn on no_repeat_ngram size 3 at α = 1: B = 5 returns "i do not know what you mean . </s>" (−0.591), now the exhaustive best.

## Worked example: when length normalisation picks the loop

Two finished outputs of the toy model (numbers from the figure's lib, checked in Python)

| Output | Tokens | log P | α = 0 | α = 0.5 | α = 1 |
| --- | --- | --- | --- | --- | --- |
| i do not know . </s> | 6 | −3.563 | −3.563 | −1.455 | −0.594 |
| i do not know . i do not know . </s> | 11 | −6.415 | −6.415 | −1.934 | −0.583 |

1. $\log P$ of the short output: $\ln(0.6\cdot0.5\cdot0.7\cdot0.6\cdot0.5\cdot0.45)=\ln0.02835=-3.563$.
2. The loop repeats the cycle "i do not know ." at mean $\log P$ of $-0.570$ per token, so 5 more tokens cost only $\ln(0.55\cdot0.5\cdot0.7\cdot0.6\cdot0.5)=-2.852$, giving $-6.415$ ($p=0.0016$).
3. The scores tie when $-3.563/6^\alpha=-6.415/11^\alpha$, i.e. $\alpha=\ln(6.415/3.563)/\ln(11/6)=0.970$. Above that, the repetitive output ranks first, and Hugging Face's default $\alpha=1.0$ is above it.

```python
from transformers import AutoModelForCausalLM, AutoTokenizer

name = "Qwen/Qwen2.5-0.5B-Instruct"
tok = AutoTokenizer.from_pretrained(name)
lm = AutoModelForCausalLM.from_pretrained(name)
ids = tok.apply_chat_template([{"role": "user", "content": "Translate to German: The meeting is moved to Friday."}],
                              add_generation_prompt=True, return_tensors="pt")

greedy = lm.generate(ids, do_sample=False, max_new_tokens=40)            # num_beams=1
beam = lm.generate(ids, do_sample=False, num_beams=4, length_penalty=1.0,
                   early_stopping=True, max_new_tokens=40,
                   num_return_sequences=2, output_scores=True, return_dict_in_generate=True)
guarded = lm.generate(ids, do_sample=False, num_beams=4, no_repeat_ngram_size=3,
                      length_penalty=0.6, max_new_tokens=40)

for out in (greedy, beam.sequences, guarded):
    print(tok.batch_decode(out[:, ids.shape[1]:], skip_special_tokens=True))
print(beam.sequences_scores)   # sum log P / length ** length_penalty, best first
```

Greedy, beam and a guarded beam with Hugging Face transformers (not run here: needs transformers and a model download)

- **Translation and summarisation:** One acceptable meaning, length roughly set by the input: beam 4–5 with length normalisation is the classic choice (see **Machine translation**, **Text summarization**).
- **Speech recognition:** Whisper decodes with 5 beams and falls back to sampling at rising temperature when the output looks repetitive (see **Whisper**).
- **Extraction, classification, short answers:** Greedy at temperature 0 gives the model's single best label or span; add **Constrained decoding** or **Structured output (JSON mode)** to fix the format.
- **Evaluation runs:** Greedy makes benchmark scores repeatable across runs, up to floating-point non-determinism on GPUs.

> **Temperature 0 is not bit-exact:** Greedy is deterministic only if the logits are. Batched GPU kernels can reduce in a different order depending on batch size and load, so two near-tied logits can swap and the outputs diverge from that token on. Treat temperature 0 as "nearly reproducible", and store outputs you need to audit.

> **Fixes for loops:** `no_repeat_ngram_size` bans any token that would recreate an n-gram already in the output, which is blunt: it also blocks legitimate repeats such as a name or a code identifier. Penalties on already-used tokens are gentler (see **Repetition and frequency penalties**). Diverse beam search (Vijayakumar et al., AAAI 2018) splits the beam into groups and penalises tokens other groups chose. For open-ended text the usual fix is to stop maximising and sample.

**Strengths**

- Deterministic: the same input gives the same output, easy to cache and test.
- Highest-likelihood outputs: best for tasks with one right answer.
- Greedy is the cheapest rule: one forward pass and one KV cache per sequence.

**Limitations**

- Repetitive, generic open-ended text; loops self-reinforce.
- Beam costs B× compute and KV memory, and has to be tuned for length.
- Wider beams can return shorter, worse outputs (the beam search curse, see **Beam search**).

**Question:** A chatbot uses beam search with B = 8 and length_penalty = 1.0, and its answers often repeat a sentence until max_new_tokens. What is the most direct fix?

- A. Raise the beam width to 16 so the search finds the true maximum
- B. Switch to sampling (for example temperature 0.7, top-p 0.9), or at least add a repetition guard
- C. Set length_penalty to 2.0
- D. Lower max_new_tokens to 2,048

**Answer:** B. Switch to sampling (for example temperature 0.7, top-p 0.9), or at least add a repetition guard — The loop is a high-likelihood output, so a better search finds it more reliably, not less. A larger $\alpha$ rewards long outputs even more. Sampling from a truncated distribution avoids maximisation altogether; a repetition guard treats the symptom.

**Question:** In the diagram, greedy returns "the capital" (P = 0.180). Why does B = 2 find "a city" (P = 0.340)?

- A. Beam search samples randomly
- B. It keeps "a" (0.40) alive at step 1, and "a" has a very likely continuation (0.85)
- C. It applies a length penalty
- D. It uses a larger vocabulary

**Answer:** B. It keeps "a" (0.40) alive at step 1, and "a" has a very likely continuation (0.85) — Greedy discards every prefix except the top one. The beam keeps the second-best prefix long enough to see that 0.40 × 0.85 beats 0.50 × 0.36.

**Key points**

- Greedy = argmax each step = beam with B = 1; both maximise likelihood and are deterministic.
- Beam ranks finished hypotheses by log P / len^α (Hugging Face length_penalty, default 1.0) and costs B× compute and KV memory.
- On open-ended text both loop: GPT-2 Large greedy output looped in 73.66% of continuations (Holtzman et al., 2020).
- Length normalisation favours loops, which have high per-token log-probability; in the toy, α ≥ 0.97 makes the loop win.
- Use them for translation, summarisation, ASR, extraction and evaluation; sample for chat and creative text.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
