How do Greedy Decoding and Beam Search differ?

Greedy Decoding and Beam Search differ in how many paths they keep while an LLM writes text. Greedy Decoding always picks the single best next word and never looks back, while Beam Search keeps a few of the best sentence options alive at every step and picks the best complete sentence at the end.

In this blog, we will learn about how Greedy Decoding and Beam Search differ. We will also see what decoding means, how Greedy Decoding works step by step, where it fails, how Beam Search fixes that failure by keeping multiple options, the cost and the problems of Beam Search, and when to use which one.

We will cover the following:

• How does an LLM write text?
• What is decoding?
• What is Greedy Decoding?
• The problem with Greedy Decoding
• What is Beam Search?
• How does Beam Search work step by step?
• Greedy Decoding vs Beam Search on the same example
• Greedy Decoding and Beam Search in code
• Two practical details of Beam Search
• The problems with Beam Search
• Greedy Decoding vs Beam Search
• When to use which one

I am Amit Shekhar, Founder @ Outcome School, I have taught and mentored many developers, and their efforts landed them high-paying tech jobs, helped many tech companies in solving their unique problems, and created many open-source libraries being used by top companies. I am passionate about sharing knowledge through open-source, blogs, and videos.

I teach AI and Machine Learning at Outcome School.

Let's get started.

How does an LLM write text?

Before jumping into Greedy Decoding and Beam Search, we must know how an LLM writes text.

An LLM (Large Language Model) writes text one small piece at a time. These small pieces are called tokens. For the sake of understanding, we can think of one token as one word.

At every step, the LLM looks at all the words written so far and gives a probability to every word it knows. A bigger number means more likely.

Let's say the text so far is "The". The LLM gives probabilities like below:

Text so far: "The"

Next word    Probability
nice         0.5
dog          0.4
car          0.1

Here, the LLM thinks "nice" is the most likely next word, "dog" is also quite likely, and "car" is less likely.

Then, one word is chosen and added to the text. Now the text becomes, for example, "The nice". The LLM again gives probabilities for the next word. This repeats until the text is complete.

So, an LLM does not write the full sentence at once. It writes it word by word. We have a detailed blog on Autoregressive Models that explains this in depth.

What is decoding?

Now, the question is: at every step, which word do we pick?

The LLM only gives us probabilities. It does not pick the word. We need a rule that picks a word from those probabilities.

Decoding is the rule that decides which next word to pick from the probabilities given by the LLM, step after step, until the text is complete.

There are many decoding rules. In this blog, we will focus on the two classic rules: Greedy Decoding and Beam Search.

Before we start, one more important idea. The score of a full sentence is found by multiplying the probabilities of all its words:

Score of "The nice woman" = P(nice) * P(woman after "The nice")

Here, P means probability. A higher score means the LLM believes the whole sentence is more likely. Our goal is to find a sentence with a high total score.

Now, let's learn our first rule.

What is Greedy Decoding?

Greedy Decoding is a decoding rule that always picks the word with the highest probability at every step.

The name comes from the word greedy. A greedy person grabs whatever looks best right now, without thinking about what comes later. Greedy Decoding does exactly this.

Suppose we are driving to a city, and at every crossing we simply take the road that looks the widest. We never check a map. We never think, "This road is wide now, but where will it take me later?". Often, this works fine. But sometimes, a wide road leads to a traffic jam, while a small road would have taken us to the city much faster.

Greedy Decoding works the same way. At every step, it takes the widest road, which means the word with the highest probability.

Let's see it on our example. We will add 2 words after "The".

Step 1: The text is "The". The probabilities are:

nice  0.5   <- highest, pick this
dog   0.4
car   0.1

Greedy Decoding picks "nice". The text becomes "The nice".

Step 2: The text is "The nice". The probabilities are:

woman  0.4   <- highest, pick this
house  0.3
guy    0.3

Greedy Decoding picks "woman". The text becomes "The nice woman".

The score of this sentence is:

0.5 * 0.4 = 0.20

This is how Greedy Decoding works. It is very simple and very fast, because at every step it does only one thing: pick the top word.

To learn LLM Fundamentals and LLM Internals, including how an LLM picks every next token, check out our AI and Machine Learning Program at Outcome School.

The problem with Greedy Decoding

Let's look at what would have happened if we had picked "dog" in Step 1, even though it was only the second best.

Text so far: "The dog"

Next word    Probability
has          0.9
runs         0.05
and          0.05

After "The dog", the LLM is very confident that the next word is "has". So, the sentence "The dog has" has the score:

0.4 * 0.9 = 0.36

Let's compare:

"The nice woman"  -> 0.5 * 0.4 = 0.20   (picked by Greedy Decoding)
"The dog has"     -> 0.4 * 0.9 = 0.36   (missed by Greedy Decoding)

Here, we can see that "The dog has" is a better sentence as per the LLM itself. Its score is 0.36, which is almost double of 0.20. But Greedy Decoding missed it, because "dog" was not the top word at Step 1.

The main problem with Greedy Decoding is this: a word that looks best now can lead to a worse sentence later, and a word that looks second best now can lead to a better sentence later. Greedy Decoding never goes back to fix its early choice.

So, how can we solve this? One idea is to check every possible sentence. But this is impossible. If the LLM knows 50,000 tokens and we want a sentence of 10 tokens, the number of possible sentences is 50,000 multiplied by itself 10 times. No computer can check all of them.

We need something in the middle. Not just one path like Greedy Decoding, and not every path. So, here comes Beam Search to the rescue.

What is Beam Search?

This was all about Greedy Decoding. Now, it's time to learn about Beam Search.

Beam Search is a decoding rule that keeps the top few partial sentences at every step, instead of just one. At the end, it picks the complete sentence with the highest total score.

The number of sentences it keeps at every step is called the beam width. Let's say the beam width is 2. Then, Beam Search always keeps the 2 best partial sentences alive.

The name comes from a beam of light, like a torch. A torch does not light up the whole dark room. It lights up only a narrow area in front of us. Beam Search does the same. It does not explore every possible sentence. It explores only a narrow set of the most promising ones.

Note: Beam Search with a beam width of 1 is exactly the same as Greedy Decoding. It keeps only one sentence, which means it always picks the top word.

Planning your move into AI?

No matter which tech domain you work in today, with your effort, you can transition to these roles:

• AI Engineer
• Forward Deployed Engineer
• AI Agent Engineer
• Harness Engineer
• Voice AI Engineer
• AI Architect
• LLM Engineer
• LLM Inference Engineer
• Gen AI Engineer
• MLOps Engineer
• ML Engineer
• Deep Learning Engineer

Our AI and Machine Learning Program at Outcome School takes you there.

How does Beam Search work step by step?

Let's use the same example and a beam width of 2.

Step 1: Start with "The". Look at all possible next words, and keep the top 2.

Candidates:
"The nice"   0.5      <- keep
"The dog"    0.4      <- keep
"The car"    0.1      <- drop

Now, we have 2 partial sentences alive: "The nice" and "The dog".

Step 2: Extend each alive sentence with every possible next word, and compute the score of each new sentence.

From "The nice" (0.5):
"The nice woman"   0.5 * 0.4  = 0.20
"The nice house"   0.5 * 0.3  = 0.15
"The nice guy"     0.5 * 0.3  = 0.15

From "The dog" (0.4):
"The dog has"      0.4 * 0.9  = 0.36
"The dog runs"     0.4 * 0.05 = 0.02
"The dog and"      0.4 * 0.05 = 0.02

Now, we put all 6 candidates together and keep only the top 2:

"The dog has"      0.36   <- keep
"The nice woman"   0.20   <- keep
others                    <- drop

Step 3: We have reached the end of our example. The best complete sentence is "The dog has" with a score of 0.36.

Here, we can see that Beam Search found the better sentence that Greedy Decoding missed. In Step 1, Beam Search did not throw away "dog" just because it was second. It kept it alive, and in Step 2, "dog" proved to be the better path.

We can draw it like below:

                        The
            /            |            \
   nice (0.5)        dog (0.4)      car (0.1)
  /     |    \     /     |     \    (dropped)
woman house guy   has   runs  and
0.20  0.15  0.15  0.36  0.02  0.02

Greedy picks:      The -> nice -> woman  = 0.20
Beam (2) picks:    The -> dog -> has     = 0.36

This is how Beam Search works. At every step, it expands all alive sentences, scores them, and keeps only the top few.

In a real LLM, the number of candidates at every step is much bigger. If the beam width is 5 and the LLM knows 50,000 tokens, there are 5 * 50,000 = 250,000 candidates at every step. But Beam Search still keeps only the top 5. This is what keeps it practical, while checking every possible sentence is impossible.

Greedy Decoding vs Beam Search on the same example

Let's put both results side by side:

Rule                     Sentence          Score
Greedy Decoding          The nice woman    0.20
Beam Search (width 2)    The dog has       0.36

Here, Beam Search gives a sentence that the LLM itself considers almost twice as likely.

But this does not mean Beam Search always wins. Sometimes, the greedy path is already the best path. In that case, both give the same answer, and Beam Search does extra work. Beam Search is also not guaranteed to find the very best sentence. It only looks at a few paths, so it can also miss a great sentence that was hiding outside the beam. It is better at avoiding the short-sighted mistakes of Greedy Decoding.

A quick note for you

No matter which tech domain you work in, get familiar with these topics:

• LLM
• RAG
• MCP
• Agent
• Fine-tuning
• Quantization

We put it all together in one video:

AI Engineering Explained: LLM, RAG, MCP, Agent, Fine-Tuning, and Quantization

No need to stop reading - bookmark it and watch later when you get time. Future you will thank you.

Now, let's get back to the topic.

Greedy Decoding and Beam Search in code

Now, let's see the code for both rules in Python. We will use a tiny fake LLM in the form of a dictionary, just for the sake of understanding.

# Toy model: probability of the next word, given the words so far
next_word_probs = {
    ("The",): {"nice": 0.5, "dog": 0.4, "car": 0.1},
    ("The", "nice"): {"woman": 0.4, "house": 0.3, "guy": 0.3},
    ("The", "dog"): {"has": 0.9, "runs": 0.05, "and": 0.05},
    ("The", "car"): {"is": 0.3, "drives": 0.5, "turns": 0.2},
}

Here, each key is the text so far, and each value holds the probabilities of the next word. A real LLM computes these probabilities. Our dictionary just stores them.

Now, let's write Greedy Decoding as below:

def greedy(start, steps):
    seq, score = start, 1.0
    for _ in range(steps):
        probs = next_word_probs[seq]
        word = max(probs, key=probs.get)  # pick the single best word
        seq, score = seq + (word,), score * probs[word]
    return seq, score

Here, we have:

• seq holds the words so far, and score holds the total score, which starts at 1.0.
• In every step, max(probs, key=probs.get) finds the word with the highest probability.
• We add that word to the sentence and multiply its probability into the score.

Now, let's write Beam Search as below:

def beam_search(start, steps, beam_width):
    beams = [(start, 1.0)]
    for _ in range(steps):
        candidates = []
        for seq, score in beams:
            for word, p in next_word_probs[seq].items():
                candidates.append((seq + (word,), score * p))
        # keep only the best `beam_width` sequences
        candidates.sort(key=lambda c: c[1], reverse=True)
        beams = candidates[:beam_width]
    return beams[0]

Here, we have:

• beams holds all the alive sentences with their scores. At the start, there is only one: "The" with a score of 1.0.
• In every step, we extend every alive sentence with every possible next word and collect all of them in candidates.
• Then, we sort the candidates by score, from highest to lowest, and keep only the top beam_width of them.
• At the end, beams[0] is the sentence with the highest score.

Now, let's run both:

seq, score = greedy(("The",), steps=2)
print("Greedy:", " ".join(seq), round(score, 2))

seq, score = beam_search(("The",), steps=2, beam_width=2)
print("Beam:  ", " ".join(seq), round(score, 2))

It will print the following:

Greedy: The nice woman 0.2
Beam:   The dog has 0.36

Here, we can see the same result that we found by hand. It works perfectly.

In real projects, we do not write this ourselves. For example, in the Hugging Face Transformers library, we can choose the rule using the generate function as below:

# Greedy Decoding
output = model.generate(**inputs, max_new_tokens=20, do_sample=False, num_beams=1)

# Beam Search with beam width 5
output = model.generate(**inputs, max_new_tokens=20, do_sample=False, num_beams=5)

Here, do_sample=False means the model does not pick words randomly. num_beams=1 gives Greedy Decoding, and num_beams=5 gives Beam Search with a beam width of 5. max_new_tokens=20 means the model writes at most 20 new tokens.

If we want to go deep into LLM Internals and build a Large Language Model (LLM) from scratch, we can check out our AI and Machine Learning Program at Outcome School.

Two practical details of Beam Search

In real use, Beam Search needs two more ideas to work well.

Detail 1: Adding logs instead of multiplying probabilities.

When we multiply many probabilities, the score becomes tiny very fast. For example, if we multiply 0.1 by itself 50 times, the first non-zero digit appears only at the 50th place after the decimal point. Computers can lose accuracy with such tiny numbers.

So, in practice, we use the logarithm of each probability, called the log probability, and we add them instead of multiplying them. For the sake of understanding, we can think of the logarithm as a tool that turns multiplication into addition. Adding log probabilities gives the same ranking as multiplying probabilities, without the tiny numbers.

Detail 2: Length normalization.

Every new word multiplies the score by a number smaller than 1. So, longer sentences always get smaller scores. Because of this, Beam Search tends to prefer short sentences and can stop too early.

To fix this, we take the total log probability of a sentence and divide it by its length, or by its length raised to some power. This means we look at the average score per word instead of the total. This is called length normalization. It makes short and long sentences fair to compare. In Hugging Face, this is controlled by the length_penalty setting.

Also, a sentence is marked as complete when the LLM produces a special end-of-sequence token, which means the sentence is finished. Complete sentences are kept aside, and Beam Search continues with the others.

Stay updated: Subscribe to our newsletter to get our latest AI and Machine Learning blogs straight to your inbox.

The problems with Beam Search

Beam Search is better at finding high-score sentences. But it comes with its own issues:

• More work: With a beam width of 5, the LLM must process 5 sentences at every step instead of 1. So, it needs more computation and more memory, and it is slower.
• Boring and repetitive text: Beam Search picks what the LLM thinks is most likely. But the most likely text is often safe, generic, and repetitive. Humans do not always speak in the most predictable way. For open-ended writing like stories or chat, Beam Search often produces dull text, and sometimes repeats the same phrase again and again.
• Bigger is not always better: Increasing the beam width finds sentences with higher scores, but very large beam widths can make the output shorter and blander. So, small beam widths are common in practice.

Note: Greedy Decoding also suffers from repetition, because it always picks the safest word. This is why chat assistants usually use neither of these two for creative replies. They use sampling, which means picking the next word randomly based on the probabilities, to make the text more natural and varied. We have a detailed blog on how Temperature controls LLM output that explains how sampling can be made more or less random.

Greedy Decoding vs Beam Search

Let me tabulate the differences between Greedy Decoding and Beam Search for your better understanding so that you can decide which one to use based on your use case.

Here, we can notice that both rules give the same output every time for the same input. Neither of them uses randomness. Such rules are called deterministic.

When to use which one

Use Greedy Decoding when:

• We want the fastest answer with the least cost.
• The task has one clear correct answer, like extracting a date, answering a simple factual question, or a short classification.
• We are running on a small device with limited memory.

Use Beam Search when:

• The task needs one accurate output that closely follows the input, like translating a sentence from English to Hindi, summarizing an article, or converting speech to text.
• A small mistake early in the output can spoil the whole result.
• We can afford more time and computation.

Use neither, and prefer sampling, when:

• We want creative, natural, and varied text, like stories, poems, or friendly chat.

Now we must have understood how Greedy Decoding and Beam Search differ and when to use which one.

Frequently Asked Questions

Is Beam Search with a beam width of 1 the same as Greedy Decoding?

Yes. Beam Search with a beam width of 1 is exactly the same as Greedy Decoding. It keeps only one partial sentence at every step, which means it always picks the word with the highest probability. A bigger beam width keeps more sentences alive, which is what lets Beam Search fix an early bad choice.

Does Beam Search always find the best sentence?

No. Beam Search is not guaranteed to find the very best sentence. It only looks at a few paths at every step, so it can miss a great sentence that was hiding outside the beam. It is better at avoiding the short-sighted mistakes of Greedy Decoding, but it does not check every possible sentence.

Are Greedy Decoding and Beam Search deterministic?

Yes. Both Greedy Decoding and Beam Search give the same output every time for the same input, because neither of them uses randomness. Rules like these are called deterministic. Sampling is different, because it picks the next word randomly based on the probabilities.

Why do chat assistants not use Greedy Decoding or Beam Search for creative replies?

Because both of them tend to produce safe, generic, and repetitive text. Greedy Decoding always picks the safest word, and Beam Search picks what the LLM thinks is most likely. For creative replies, chat assistants usually use sampling, which picks the next word randomly based on the probabilities, to make the text more natural and varied.

How do we choose Greedy Decoding or Beam Search in Hugging Face Transformers?

We choose the rule using the generate function. With do_sample=False, setting num_beams=1 gives Greedy Decoding, and setting num_beams=5 gives Beam Search with a beam width of 5. The length_penalty setting controls length normalization for Beam Search.

That's it for now.

Thanks

Amit Shekhar
Founder @ Outcome School

You can connect with me on:

• X
• LinkedIn
• GitHub

Follow Outcome School on:

• X
• YouTube
• LinkedIn
• GitHub

Read all of our high-quality blogs here.