Greedy Decoding vs. Beam Search: Output Quality & Cost

Greedy Search: The Path of Least Resistance

The most straightforward strategy for token selection is greedy search. As its name suggests, at each step of the generation process, it simply chooses the single token with the highest probability. It's an entirely deterministic and "short-sighted" approach, always taking the immediately best option without considering future consequences.

Given your background in algorithms, you can think of this as a hill-climbing algorithm on the probability landscape of possible sequences, where each step moves to the highest adjacent point.

The textbook "Dive into Deep Learning" provides a concise formalization of this strategy.

As the reading makes clear, the core issue with greedy search is that the sequence of most likely tokens is not necessarily the most likely sequence overall. The product of probabilities along the greedy path might be lower than an alternative path that involved making a "less optimal" choice early on.

Let's break down the comparison points:

• Computational Cost: Greedy search is highly efficient. At each of the $T^{\prime }$ time steps, the model performs one forward pass and finds the argmax over the vocabulary $\mathcal{Y}$. The complexity is therefore $\mathcal{O}(|\mathcal{Y}|\cdot T^{\prime })$, which is linear with respect to the sequence length. This makes it very fast.
• Output Quality: While fast, greedy search often produces text that is generic, dull, and prone to repetition. Because it can't "look ahead," it can easily get stuck in loops or commit to a word choice that leads to an awkward or incoherent sentence structure later on. The article from AssemblyAI notes that this method is empirically found to output repetitive text sequences.

Beam Search: A Wider Path

To mitigate the short-sightedness of greedy search, we can use beam search. This strategy introduces a crucial enhancement: instead of tracking only the single best path, it maintains a "beam" of the $k$ most probable partial sequences at each time step. The hyperparameter $k$ is known as the beam size or beam width.

This approach is a heuristic search algorithm that explores a much larger portion of the search space than greedy search, without incurring the exponential cost of an exhaustive search (which would explore all possible sequences).

Andrew Ng provides an excellent step-by-step walkthrough of how beam search operates.

The process described in the video can be summarized as follows:

1. Step 1: Generate probabilities for the first token. Select the top $k$ tokens and place these one-token sequences into the beam.
2. Step 2: For each of the $k$ sequences currently in the beam, generate the probability distribution for the next token. This gives you $k\times |\mathcal{Y}|$ potential two-token sequences.
3. Step 3: Calculate the total probability for each of these $k\times |\mathcal{Y}|$ candidate sequences. The probability of a sequence $(y_1,y_2)$ is $P(y_1,y_2)=P(y_1)\cdot P(y_2|y_1)$.
4. Step 4: From this large set of candidates, select the $k$ sequences with the highest total probabilities. These become the new beam.
5. Repeat: Continue this process until an end-of-sequence token is generated for all sequences in the beam or a maximum length is reached.

The following diagram provides a clear, static illustration of this process with a beam size of $k=2$.

A Formal Comparison

Now we can directly compare the two strategies based on our learning objective.

The crucial insight is the trade-off. Beam search offers a significant quality improvement over greedy search at a linearly increasing computational cost determined by the beam size k.

Limitations and The Scoring Function

While beam search is an improvement, it's not a panacea. For open-ended creative text generation, it can still produce text that feels safe, repetitive, and lacks the natural variance of human writing. This is because it is still fundamentally optimized to find high-probability sequences.

A final important detail is how sequences are scored. Multiplying many small probabilities can lead to numerical underflow. Therefore, in practice, we use log-probabilities. The goal becomes to find the sequence that maximizes the sum of log-probabilities.

However, this sum naturally favors shorter sequences. To counteract this, a length penalty is often introduced. The final score to maximize is:

Here, $L$ is the sequence length and $\alpha$ is a hyperparameter (often around 0.75) that controls the strength of the penalty on longer sequences.

Conclusion

In this lesson, we have moved from the "what" of autoregressive generation to the "how" of token selection. We've contrasted two fundamental deterministic decoding strategies.

Here are the key takeaways:

• Greedy Search: The simplest, fastest method. It picks the most likely token at each step, but its short-sightedness often leads to suboptimal and repetitive final sequences.
• Beam Search: A more robust heuristic that improves output quality by maintaining a "beam" of $k$ candidate sequences. It offers a direct trade-off between computational cost (linear in k) and search quality.
• Greedy as a Special Case: You can view greedy search as simply beam search with a beam size of k=1.
• Deterministic Limitations: Both methods are deterministic and tend to favor high-probability, "safe" text, which may lack the diversity and creativity expected in many applications.

We have now established a solid understanding of how to find the most likely sequences. But what if we don't always want the most likely? What if we want to introduce creativity, surprise, or controlled randomness? This question leads us directly to our next topic: stochastic decoding strategies, where we will explore methods like temperature scaling, top-k sampling, and nucleus sampling.