Beam Search vs Sampling: Two Ways to Generate Text

// In plain English

An LLM writes text one token at a time. At every step it produces a probability for each possible next token (see next-token prediction), then something has to choose one of them. That choosing step is called decoding, and beam search and sampling are the two big families of how to do it.

Picture writing a sentence with sticky notes, one word per note. Sampling is like rolling a weighted die at each word: the most likely word usually wins, but now and then a less likely word slips in, so the sentence feels fresh and human — and a little unpredictable. Beam search is the opposite personality. It refuses to commit early. It keeps several half-finished sentences alive at once, grows each of them, and at the end hands you the single sentence whose words multiply out to the highest overall probability.

So the one-line difference: sampling chases variety by rolling dice token by token; beam search chases the most likely whole sentence by exploring several candidates in parallel before deciding. A third, simpler cousin — greedy decoding — just grabs the single highest-probability token every step and never looks back; you can think of beam search as greedy decoding that hedges its bets.

// Why it matters

The decoding strategy you pick changes the character of the output more than people expect — same model, same prompt, wildly different text. Understanding the trade-off is the difference between a translation system that sounds crisp and a chatbot that sounds like a broken record.

Here is the core tension. The most probable sentence is not always the best sentence. Beam search is very good at finding the high-probability output, but for open-ended writing the high-probability output is bland, generic, and weirdly repetitive — because safe, common phrases are exactly what a language model rates as most likely. Sampling deliberately gives up a little probability to buy variety, surprise, and a human feel.

• Builders of translation, summarization, or code tools care because there is often one right-ish answer, and squeezing out the most likely sequence genuinely helps — this is beam search's home turf.
• Builders of chatbots and creative writing tools care because beam search makes their product sound robotic and loopy, which is the single biggest reason chat models sample instead.
• Anyone tuning generation care because temperature, top-k, and top-p are sampling knobs, while num_beams is a beam-search knob — knowing which family you are in tells you which dial actually does anything.

This builds directly on greedy decoding vs sampling: greedy and sampling are the two extremes (always-the-top-token vs roll-the-dice), and beam search is the more elaborate strategy that sits beside greedy on the "hunt for the most likely text" side.

// How it works

Both strategies start from the same place. At each step the model outputs raw scores called logits, which softmax turns into a probability for every token in the vocabulary. The two families then differ in what they do with that probability distribution — and that one decision is the entire story.

Sampling: roll a weighted die each step

Sampling treats the probability distribution as exactly that — a distribution to draw from. If "blue" has probability 0.6 and "green" has 0.3, then roughly 60% of the time you get "blue" and 30% of the time "green". You pick one token, append it, and repeat. Because it is random, the same prompt produces different text on every run. Knobs like temperature flatten or sharpen the distribution, and top-k / top-p chop off the unlikely tail so the dice can never roll true nonsense.

Beam search: keep the top-N candidates alive

Beam search never rolls dice. With beam width k, it keeps the k best partial sequences so far. At each step it expands every surviving beam by every possible next token, scores each resulting longer sequence by its total probability, and keeps only the top k of all those candidates. It repeats until the sequences end, then returns the single highest-scoring complete sequence. The point is that a token which looks weak right now might lead to a much stronger sentence later — beam search keeps that door open instead of slamming it shut the way greedy does.

Because multiplying many probabilities (each below 1) shrinks toward zero fast, real implementations add log-probabilities instead of multiplying raw ones — same ranking, no numeric underflow. A length penalty is usually added too, since otherwise the math quietly favors shorter sequences (fewer terms to multiply means a higher score).

Note the deepest split: greedy and beam search are deterministic (same prompt, same output every time), while sampling is stochastic. That single property — repeatable vs varied — drives almost every choice between them.

// A tiny worked example

Suppose after the prompt the model gives these next-token probabilities, and we want a two-token continuation. Watch how greedy can lose to beam search.

Greedy picks the highest first token, "nice" (0.50), commits to it, then best-continues to "day" — final probability 0.15. It never discovers anything better because it threw away "sunny" at step one.

Beam search with width 2 keeps both "nice" and "sunny" alive, expands both, and compares whole sequences. "sunny morning" scores 0.32 — more than double greedy's "nice day." Beam search wins precisely because it did not commit early. This is the entire reason the strategy exists, shown in five numbers.

# Beam search: hunt for the most likely whole sequence
out = model.generate(
    **inputs,
    num_beams=5,            # beam width k; 1 == greedy decoding
    early_stopping=True,
    length_penalty=1.0,     # > 1 favors longer, < 1 favors shorter
)

# Sampling: trade likelihood for variety (what chat models use)
out = model.generate(
    **inputs,
    do_sample=True,
    temperature=0.8,        # higher = more random
    top_p=0.9,              # nucleus sampling: keep the top 90% mass
)

// When each one wins

There is no universally better strategy — it depends entirely on whether your task has roughly one correct answer or many good answers.

This is the answer to the most-searched question on the topic: why don't chatbots use beam search? Because the most likely sentence is the most generic one. Beam search relentlessly optimizes for high probability, and the high-probability path in open conversation is full of safe filler and repeated phrases. It produces text that is technically likely yet lifeless. Sampling sacrifices a sliver of probability to escape that trap, which is exactly why ChatGPT and similar chat models sample by default.

// Common pitfalls

• Assuming beam search = better quality. It maximizes probability, not human preference. For open-ended text, wider beams often make output more repetitive and dull, not less — a well-known and counter-intuitive result.
• Forgetting the length penalty. Without it, beam search systematically prefers short sequences, because each extra token multiplies in another probability below 1 and drags the score down. Tune length_penalty for your task.
• Paying for beams you don't need. Beam width k means roughly k times the compute and memory of greedy decoding. For chat, where you sample anyway, that cost buys you nothing.
• Confusing the knobs. temperature, top-k, and top-p only affect sampling. Setting temperature while using pure beam search does little — you are turning a dial that isn't connected.
• Expecting variety from beam search. It is deterministic. If you need different outputs across runs, you need sampling (or beam-search sampling variants), not a bigger beam.

// Going deeper

The clean greedy / beam / sampling split is the foundation, but production systems blur the lines. A few directions worth knowing once the basics click.

Hybrids exist. Beam-search multinomial sampling runs several beams but samples each expansion instead of taking the top tokens, blending beam's structure with sampling's variety. Diverse beam search explicitly pushes beams apart so you don't get five near-identical sentences. Contrastive search is a newer decoding method aimed at fluent, non-repetitive open-ended text without the dullness beam search suffers from.

Why beam search repeats itself is a genuine research finding, not just folklore. Because all generation here is autoregressive — each token conditions on the ones before it — a model that emits a likely phrase can find that repeating it is also locally likely, and beam search, which optimizes probability, happily follows that loop. Sampling's randomness is what breaks the cycle, which is part of why pure greedy and beam fell out of favor for open-ended chat.

The compute angle. Beam search multiplies the work per step by the beam width, which matters because LLM inference is already expensive (see why LLMs need GPUs). At chat scale, running width-5 beam search for every reply would multiply serving cost for output that users like less — another practical nail in beam search's coffin for chatbots, even setting quality aside.

Where to go next. Solidify the upstream mechanics with logits and softmax — the probabilities every decoder consumes — and read greedy decoding vs sampling for the temperature / top-k / top-p knobs in depth. The durable takeaway: beam search and sampling are not better or worse, they answer different questions — what is the single most likely text? versus what is one good, varied, human-sounding text? Pick the question first, and the strategy follows.