Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 53 ยท Sampling and Decoding

Greedy Decoding, Beam Search and Repetition Penalties

Compare greedy decoding, beam search and sampling, then learn repetition and frequency penalties, stop sequences and logit bias with a toy decoder.

Once a model has probabilities for the next token, decoding is the loop that picks tokens one after another until the text is finished. You have seen random sampling with temperature and top-p. This lesson covers the deterministic alternatives, greedy decoding and beam search, and the extra controls most APIs offer to steer the output: repetition penalties, stop sequences and logit bias.

Greedy decoding

Greedy decoding always picks the single most probable token. It is fast, deterministic and often good enough for short factual answers. Its flaw is short-sightedness: the best token now can lead into a poor sentence later, because a locally attractive choice may have only weak continuations.

Beam search keeps the B best partial sequences (the "beam") at each step. Every candidate is extended by every possible next token, all the new sequences are scored by their total log probability, and only the top B survive. With B = 1 it is greedy decoding. Beam search looks for the most probable whole sequence, not just the most probable next token. It was the standard for machine translation and summarization.

Three ways to decode

Greedy Best token now. Fast, short-sighted.
Beam search Track several best sequences.
Sampling Draw randomly. Varied, less predictable.

Chat models mostly sample; translation often uses beams.

1 / 2

A toy language model

To compare them we need a tiny model. This one looks only at the last token, and its probabilities are chosen so greedy decoding falls into a trap: "the" is the likeliest first word, but everything after "the" is uncertain, while "a" leads to a very confident phrase.

Python Greedy versus beam search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Greedy picks "the", then "cat", ending with the sentence "the cat" at a probability of about 0.153. Beam search with two beams keeps "a" alive after the first step, finds "a cat" and gets a probability above 0.32, more than double.

Length bias

Beam search has a known bias. Every extra token multiplies in a probability below 1, so the total probability of a sequence shrinks as it grows, and short sequences win. Left alone, beam search likes to end early. The usual fix is length normalization: divide the log probability by the length raised to a power alpha, so the score becomes an average per token.

Python Length normalization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Raw probability prefers the short sequence (0.27 against 0.33... check the numbers in your run), while the per-token average prefers the long, confident one. The right alpha depends on the task.

Beam search also has a deeper limit for open-ended chat: the most probable text is often bland, repetitive and generic. Studies of human text show that people do not always choose likely words, which is why chatbots mostly sample instead.

Repetition control

Greedy and beam decoding easily fall into loops ("I think that I think that I think..."). Samplers can too. APIs offer penalties that lower the logit of tokens that have already appeared.

Setting What it does
Repetition penalty Divides (or subtracts from) the score of any token that already appeared, once, whatever the count
Presence penalty Subtracts a fixed amount from tokens that appeared at least once
Frequency penalty Subtracts an amount proportional to how many times a token appeared

Names and exact formulas differ between providers and runtimes, so read your API's documentation. The common OpenAI-style formula is logit - count ร— frequency_penalty - (count > 0) ร— presence_penalty.

Logit bias and stop sequences

A logit bias adds a fixed number to the logit of chosen tokens before softmax. Large positive values force a token, large negative ones ban it. It is useful for forcing one of a few labels ("yes" or "no") or blocking unwanted words.

A stop sequence is a string that ends generation as soon as it appears, and the string itself is not returned. Typical uses are a delimiter such as "\n\n" or "###", or the start of a role label like "User:" so the model does not continue a fake conversation.

A toy decoder with all the controls

This decoder runs on fixed logits per step with a simple repeating model, so you can watch each control change the result.

Python Penalties, bias and stop sequences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without help greedy decoding repeats "ha" forever. Penalties push it to rotate through other tokens, a ban removes "ha" entirely and a strong bias makes the stop token win straight away.

Penalties are blunt. Penalizing repetition too hard punishes words that must repeat, such as names, code keywords or JSON keys, and can make output worse. Start small.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does greedy decoding do?

    Greedy decoding takes the highest-probability token at every step.
  2. 2. Why can beam search find a better sequence than greedy decoding?

    Keeping several candidates lets a path whose first token was not the best, but whose continuation is strong, overtake the greedy path.
  3. 3. What problem does length normalization address?

    Multiplying probabilities below 1 makes long sequences score lower, so short ones win unless you normalize.
  4. 4. What is the difference between a frequency penalty and a presence penalty?

    Frequency penalties scale with the count, presence penalties apply once regardless of the count.

Summary

  • Greedy decoding picks the top token each step; it is fast but short-sighted.
  • Beam search keeps B candidate sequences and favors high total probability; it needs length normalization and tends toward bland text.
  • Frequency, presence and repetition penalties discourage loops but can hurt tokens that should repeat.
  • Logit bias shifts specific token scores; stop sequences end generation at a chosen string.

Next, move from decoding to what you tell the model in The Anatomy of a Good Prompt.