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.

8 min read660 wordscore0 viewsupdated 2026-10-21

Definition

Greedy and beam search are the two deterministic decoding rules for an autoregressive model. Greedy decoding appends yt=arg⁡max⁡wP(w∣y<t,x)y_t=\arg\max_w P(w\mid y_{<t},x) at every step. Beam search keeps the BB highest-scoring partial outputs, extends each by every token, and keeps the best BB again; B=1B=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

greedy: yt=arg⁡max⁡w∈Vlog⁡P(w∣y<t,x)beam: Y^=arg⁡max⁡Y∈F ∑t=1∣Y∣log⁡P(yt∣y<t,x)∣Y∣α\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}}
V\mathcal V
the vocabulary, including the end-of-sequence token </s>
F\mathcal F
finished hypotheses collected by a width-BB beam (plus the alive ones if the length limit is hit)
α\alpha
length penalty exponent; Hugging Face length_penalty, default 1.0. α=0\alpha=0 ranks by raw log-probability, which favours short outputs
two decoding steps after the prompt "Paris is", beam width B = 2Paris isthe0.50a0.40known0.10rank 3: prunedcapital0.36P 0.180city0.34P 0.170best0.30P 0.150city0.85P 0.340beautiful0.10P 0.040place0.05P 0.0206 candidates = B × 3 continuations;P = product of step probabilitiesstep-2 ranking1 a city0.3402 the capital0.1803 the city0.1704 the best0.150greedy: the capital0.50 × 0.36 = 0.180beam: a city0.40 × 0.85 = 0.340greedy path (also kept by the beam)kept by beam onlypruned
fig.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 BB forward passes per token (batched together) and BB 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.

DecodingPerplexityRepetition %
Human text12.380.28
Greedy1.5073.66
Beam search, b = 161.4828.94
Pure sampling22.730.22
Nucleus, p = 0.9513.130.36
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.

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

toy bigram chat model · max 12 tokens · score = log P / len^α, α = 1.0greedyidonotknow.idonotknow.idolog P -6.907 · p 0.0010 · len 12 · score -0.576 · rep-3 50% · cutbeam B=4idonotknow.idonotknow.idolog P -6.907 · p 0.0010 · len 12 · score -0.576 · rep-3 50% · cutexhaustiveidonotknow.idonotknow.</s>log P -6.415 · p 0.0016 · len 11 · score -0.583 · rep-3 33%of 1722 sequencesbeam hypotheses, best score firstlenlog Pscoreendi do not know . i do not know . i do12-6.907-0.576cutwhat you mean . i do not know . i do not12-6.948-0.579cuti do not know . i do not know . </s>11-6.415-0.583EOSi do not know . </s>6-3.563-0.594EOSi do not mean . i do not know . i do12-7.130-0.594cuti do not know . i do not mean . i do12-7.130-0.594cut105 candidates scored over 12 steps · 2 finished · search error: beam missed the exhaustive best
no_repeat_ngram
fig.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

OutputTokenslog 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
Two finished outputs of the toy model (numbers from the figure's lib, checked in Python)
  1. 1log⁡P\log P of the short output: ln⁡(0.6⋅0.5⋅0.7⋅0.6⋅0.5⋅0.45)=ln⁡0.02835=−3.563\ln(0.6\cdot0.5\cdot0.7\cdot0.6\cdot0.5\cdot0.45)=\ln0.02835=-3.563.
  2. 2The loop repeats the cycle "i do not know ." at mean log⁡P\log P of −0.570-0.570 per token, so 5 more tokens cost only ln⁡(0.55⋅0.5⋅0.7⋅0.6⋅0.5)=−2.852\ln(0.55\cdot0.5\cdot0.7\cdot0.6\cdot0.5)=-2.852, giving −6.415-6.415 (p=0.0016p=0.0016).
  3. 3The scores tie when −3.563/6α=−6.415/11α-3.563/6^\alpha=-6.415/11^\alpha, i.e. α=ln⁡(6.415/3.563)/ln⁡(11/6)=0.970\alpha=\ln(6.415/3.563)/\ln(11/6)=0.970. Above that, the repetitive output ranks first, and Hugging Face's default α=1.0\alpha=1.0 is above it.
python
1from transformers import AutoModelForCausalLM, AutoTokenizer
2
3name = "Qwen/Qwen2.5-0.5B-Instruct"
4tok = AutoTokenizer.from_pretrained(name)
5lm = AutoModelForCausalLM.from_pretrained(name)
6ids = tok.apply_chat_template([{"role": "user", "content": "Translate to German: The meeting is moved to Friday."}],
7 add_generation_prompt=True, return_tensors="pt")
8
9greedy = lm.generate(ids, do_sample=False, max_new_tokens=40) # num_beams=1
10beam = lm.generate(ids, do_sample=False, num_beams=4, length_penalty=1.0,
11 early_stopping=True, max_new_tokens=40,
12 num_return_sequences=2, output_scores=True, return_dict_in_generate=True)
13guarded = lm.generate(ids, do_sample=False, num_beams=4, no_repeat_ngram_size=3,
14 length_penalty=0.6, max_new_tokens=40)
15
16for out in (greedy, beam.sequences, guarded):
17 print(tok.batch_decode(out[:, ids.shape[1]:], skip_special_tokens=True))
18print(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)

Where it's used

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.

Use when

  • +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.

Avoid when

  • −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).

Check yourself

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?

Check yourself

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

Remember

  • ✓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.
← back to Generative AI roadmap