Beam search is a search method used when a language model builds a sentence from next-token probability distributions: instead of locking in the single highest-probability token at each step as greedy decoding does, it keeps several candidate sequences alive to look ahead. This post covers beam width, cumulative probability, length penalty, repetition issues, and why open-ended chatbots rely on sampling more than beam search.
Summary
Unlike greedy decoding, which picks only the single highest-probability token at each step, beam search keeps the top k candidate sentences by cumulative probability in parallel and chooses the highest-scoring sentence at the end. This allows it to find a strong full sentence even when the first token has a lower probability, though it is not guaranteed to find the globally best sentence. Because multiplying probabilities penalizes longer sentences, a length penalty is used to offset the bias. Beam search fits tasks with a narrow answer range like translation and summarization, while sampling is used more in open-ended dialogue and stories where beam search easily becomes repetitive and predictable.
What is beam search?
One-line answer: It is a decoding method that keeps the top k candidate sentences (beams) by cumulative probability at each step and selects the highest-scoring sentence at the end.
In autoregressive language generation, the overall probability of a word sequence is the product of its conditional next-word probabilities at each step. Beam search tracks the most likely num_beams hypotheses at every time step and finally selects the hypothesis with the highest overall probability.
- Beam: A single candidate sequence (hypothesis) kept alive during the search.
- Beam width (k): The number of candidate sequences retained at each step.
- Sequence score (cumulative probability): The product of the step probabilities along the sequence, computed in practice as the sum of log probabilities (log likelihood).
For how a model counts text in tokens, see What are tokens and the context window? How LLMs count text and why length limits exist. For how tokens are appended one by one during the decode stage, see Day 3: LLM inference structure and the KV cache (Korean). The basic difference between greedy decoding and sampling—and how temperature approaching zero makes sampling equal to greedy—is covered in What are Temperature and Top-p? Why LLM answers vary every time.
Why does greedy decoding miss better sentences?
One-line answer: Because it commits to the single highest-probability token at each step, it never sees a higher-scoring full sentence hidden behind a lower-probability initial token.
Greedy decoding picks the single highest-probability word at each step and discards everything else. Its major drawback is that it misses high-probability words hidden behind a lower-probability word earlier in the sequence.
The code below was run in this post’s environment (Python 3.13.5). All probabilities shown here are values chosen by hand for explanation and are not from a real model (the structure follows the sketch idea in the Hugging Face decoding blog post).
# 장난감 예: 2단계 생성, 확률은 설명용으로 직접 정한 값(실제 모델 아님)
step1={"A":0.5,"B":0.4,"C":0.1}
step2={"A":{"x":0.4,"y":0.35,"z":0.25},"B":{"x":0.9,"y":0.05,"z":0.05},"C":{"x":0.5,"y":0.3,"z":0.2}}
g1=max(step1,key=step1.get); g2=max(step2[g1],key=step2[g1].get)
print(f"greedy: {g1}{g2} p={step1[g1]*step2[g1][g2]:.2f}")
for k in (2,):
beams=sorted(step1.items(),key=lambda t:-t[1])[:k]
cand=[(a+b,pa*pb) for a,pa in beams for b,pb in step2[a].items()]
best=sorted(cand,key=lambda t:-t[1])[:k]
print(f"beam k={k}: "+", ".join(f"{s} p={p:.2f}" for s,p in best))
greedy: Ax p=0.20
beam k=2: Bx p=0.36, Ax p=0.20
Tracing the two steps shows why the two methods pick different sequences:
- Step 1 probabilities (illustrative example values): the first-token candidates are
A0.5,B0.4 andC0.1. - Greedy choice: greedy keeps only
A, the highest, and dropsBandC. AfterA, the step-2 options arex0.4,y0.35 andz0.25 (all illustrative example values); greedy picksx, producingAxwith a cumulative probability of 0.5 × 0.4 = 0.20 (illustrative example values). - Beam search (k=2) choice: beam search keeps the top two first tokens,
AandB. AfterB, the continuations arex0.9,y0.05 andz0.05 (all illustrative example values), soBxscores 0.4 × 0.9 = 0.36 (illustrative example values) and beatsAxat 0.20 (illustrative example values). Greedy never seesBxbecause it discardedBat step 1.

What does the beam width k change?
One-line answer: A larger k keeps more candidate paths alive and increases the chance of finding a higher-scoring sentence, but it also increases computation at every step; k=1 is the same as greedy decoding.
The beam width k controls how many parallel candidate continuations are kept at each step. A larger k keeps more candidates and gives the search a better chance of finding a higher-scoring sentence, but because every step must score the continuations of all k candidates, computation grows with k.
num_beamsin the Transformers library: Beam search requiresnum_beamsto be greater than 1; settingnum_beams=1(k=1) keeps only a single sequence and is equivalent to greedy search.- No optimality guarantee: While beam search reduces the risk of missing hidden high-probability sequences compared to greedy search, it is not guaranteed to find the most likely output overall.
num_return_sequences: This parameter returns several top beams at the end (it must be less than or equal tonum_beams). In practice, the top returned beams are often only marginally different from each other.early_stopping: Settingearly_stopping=Truefinishes generation as soon as all beam hypotheses reach the end-of-sequence token. It also accepts"never", which stops only when no better candidates can exist (canonical beam search).
Why is a length penalty needed?
One-line answer: Multiplying probabilities below 1 makes the score shrink as a sentence gets longer, favoring short sentences unless the score is divided by a power of the sequence length.
Because each step probability is below 1, multiplying more of them together makes the product smaller as a sentence grows longer. Without correction, beam search naturally favors shorter sentences that end early over longer ones.
To offset this bias, beam-based generation applies an exponential penalty to the sequence length. In the Transformers library’s GenerationConfig, the length_penalty parameter is applied as an exponent to the sequence length, which divides the score of the sequence. Because the score is a log likelihood (a negative number), length_penalty > 0 promotes longer sequences, while length_penalty < 0 encourages shorter ones.
Why do conversational chatbots use sampling more?
One-line answer: In open-ended dialogue the target length varies widely and beam search tends to repeat itself and sound predictable, so sampling’s diversity produces more natural responses.
As explained in the Hugging Face decoding blog post, beam search is often not the best fit for open-ended generation such as dialogue and story writing for three main reasons:
- Unpredictable output length: Beam search works well where the desired output length is roughly predictable, as in machine translation or summarization, but not in dialogue or story generation where length varies greatly.
- Repetitive generation: Both greedy and beam search tend to produce repetitive text, and in story generation that repetition is hard to control cleanly with penalties alone.
- Predictable, unsurprising text: High-quality human language does not simply follow a distribution of high-probability next words; people want text that surprises them rather than predictable text (argued in Holtzman et al., 2019).
One common remedy for repetition is an n-gram penalty (no_repeat_ngram_size, which prevents any n-gram from appearing twice), but it must be used with care. For example, in a text about the city "New York", a 2-gram penalty would allow the city name to appear only once in the entire output.
At the same time, the blog notes a balanced conclusion: while top-p and top-k sampling tend to produce more fluent text on open-ended generation than greedy and beam search, there is evidence that repetition flaws stem from the model and training objective rather than the decoding method alone (Welleck et al., 2019), sampling can also repeat (Welleck et al., 2020), and there is no one-size-fits-all decoding method.
When is beam search the right choice?
One-line answer: It fits tasks where the output is tightly grounded in the input and the target length is fairly predictable, such as translation, summarization, image description, and speech recognition.
According to the Transformers library documentation, greedy search is the default decoding strategy and works for short outputs where creativity is not a priority, though it begins to repeat itself on longer sequences. Beam search can look ahead to pick a sequence with higher overall probability and is best suited for input-grounded tasks such as describing an image or speech recognition; the Hugging Face blog adds translation and summarization. Sampling (do_sample=True, num_beams=1) reduces repetition and generates more creative, diverse outputs.
| Aspect | Beam Search | Sampling |
|---|---|---|
| Primary goal | Keep top k candidate sequences to find a hypothesis with higher overall probability | Draw from the probability distribution to introduce variety and creativity |
| Best suited for | Input-grounded tasks with fairly predictable output length: translation, summarization, image description, speech recognition | Open-ended generation where output length varies and diversity matters: dialogue, story generation |
| Key trade-offs | Prone to repetition and predictable phrasing in open-ended text; computation grows with beam width k | Can drift if low-probability tokens are drawn, and sampling can still exhibit repetition |

What are the frequently asked questions?
One-line answer: Here are answers on how beam search differs from speculative decoding, whether it can be combined with sampling, and whether it guarantees the best sentence.
Are beam search and speculative decoding the same thing?
No. Beam search is a search strategy that compares multiple candidate sequences to find a higher-scoring sentence, whereas speculative decoding is an inference acceleration technique where a small model drafts tokens and a large model verifies them while preserving the large model’s output distribution. See What is speculative decoding? Why a small draft model makes LLM answers faster.
Can beam search and sampling be used together?
Yes. In the Transformers library, do_sample=True can be combined with beam search (num_beams > 1), though beam search still prunes low-probability sequences between steps.
Does beam search always produce the best sentence?
No. It only searches within k kept candidates rather than guaranteeing the globally highest-probability sequence, and the highest-probability sequence is not always the most natural human text (Holtzman et al., 2019).
What related posts are worth reading?
One-line answer: These related posts cover decoding parameters, tokens and context windows, inference caching, speculative decoding, and attention scaling.
- What are Temperature and Top-p? Why LLM answers vary every time
- What are tokens and the context window? How LLMs count text and why length limits exist
- Day 3: LLM inference structure and the KV cache (Korean)
- What is speculative decoding? Why a small draft model makes LLM answers faster
- “Can a language model work without attention? Why self-attention cost grows with the square of sequence length, and the alternatives” (related post)
What are the sources?
One-line answer: These are the official documentation pages, technical blog post, and execution environment checked for this post.
- Hugging Face blog: How to generate text: using different decoding methods for language generation with Transformers (checked 2026-11-02)
- Hugging Face Transformers docs: Generation strategies (checked 2026-11-02)
- Hugging Face Transformers docs: Generation (GenerationConfig) (checked 2026-11-02)
- Measurement: Python 3.13.5, 2026-11-02