Definition
Greedy and beam search are the two deterministic decoding rules for an autoregressive model. Greedy decoding appends at every step. Beam search keeps the highest-scoring partial outputs, extends each by every token, and keeps the best again; 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
- the vocabulary, including the end-of-sequence token </s>
- finished hypotheses collected by a width- beam (plus the alive ones if the length limit is hit)
- length penalty exponent; Hugging Face
length_penalty, default 1.0. ranks by raw log-probability, which favours short outputs
Greedy costs one forward pass per token. Beam search costs forward passes per token (batched together) and 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.
| 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 rewards running on. In the figure below, the loop wins once .
Worked example: when length normalisation picks the loop
| 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 of the short output: .
- 2The loop repeats the cycle "i do not know ." at mean of per token, so 5 more tokens cost only , giving ().
- 3The scores tie when , i.e. . Above that, the repetitive output ranks first, and Hugging Face's default is above it.
1from transformers import AutoModelForCausalLM, AutoTokenizer23name = "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")89greedy = lm.generate(ids, do_sample=False, max_new_tokens=40) # num_beams=110beam = 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)1516for 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 firstWhere 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.