LLM Inferencing strategies —Review of Greedy Search and Beam Search

Photo by Nathan Dumlao on Unsplash

LLM inference refers to the process where a trained language model generates text in response to a given input prompt. Transformer-based generative models build internal representations of their input through Self-Attention, enabling them to dynamically evaluate and prioritize different parts of the input based on their relevance to the current prediction point. Broadly speaking, text generation in LLMs centers on predicting the next token in a sequence, with each prediction influenced by the cumulative probability of the tokens generated so far. This process is guided by internal probability distributions shaped by:

• The model’s learned weights, which have been refined through extensive training on massive datasets
• The full input context (including the prompt and any additional supporting documents)
• The sequence of tokens generated up to the current point

During decoding, the model continuously assesses how different parts of the input contribute to the unfolding output, primarily through Cross-Attention mechanisms. To determine the next token, the model starts by producing raw scores (logits) for every word in its vocabulary. Several parameters control this inference process:

• Raw Logits: The model’s learned, unnormalized probabilities for each possible next word
• Temperature: A setting that adjusts the randomness of the output; higher temperatures (>1.0) lead to more diverse and creative responses, while lower temperatures (<1.0) produce more focused and deterministic outputs
• Top-p (Nucleus) Sampling: A strategy that narrows the candidate pool to the smallest set of words whose cumulative probability exceeds a chosen threshold (e.g., 90%)
• Top-k Filtering: Instead of considering all words, the model restricts choices to the top k most probable options

Decoding methods such as nucleus sampling (top-p), temperature scaling, and beam search offer different balances between creativity and coherence. Just as a writer might decide between being imaginative or precise, we can tweak the model’s decoding strategies to influence the style of the generated text. Among these strategies, greedy search and beam search are two fundamental approaches we will now explore in more detail.

Greedy Search: Simplicity at a Cost

When an LLM generates text, it typically evaluates both the full input context and the ongoing output sequence. The most straightforward way to build text iteratively from these predictions is by using a greedy algorithm, where the model selects the most likely next token at every step.

In greedy search, the model always picks the token with the highest probability at each generation step. While this method is simple and computationally efficient — requiring just one inference per output token — it often leads to suboptimal sequences.

https://huggingface.co/learn/llm-course/chapter1/8?fw=pt

The process works like this: at every point, the model chooses the most probable next token, appends it to the sequence, and continues. While efficient, this approach has a critical weakness: it can get trapped in local optima. What looks like the best token choice immediately may not lead to the best overall output in the long run.

For example, given some initial context, the model might generate “We can treat it as a matter of course” — a sequence that feels natural token-by-token. However, a better, contextually accurate sentence might have been “We can treat it as a matter of cause and effect.” Since greedy search can’t backtrack or reconsider earlier choices, once it commits to “course,” it’s locked into a suboptimal path.

This inability to anticipate better outcomes further down the sequence is one reason why more sophisticated strategies, like beam search, are often preferred.

LLMs using greedy search often exhibit certain issues:

• Repetition Loops: The model can prioritize immediate high-probability choices, causing it to repeat itself and cycle over the same ideas.
• Path Blindness: By always choosing the next highest-probability token, the model can miss sequences that would have been better overall if it had temporarily selected a slightly less probable token.

To counter these issues, models apply penalties during token selection

• Presence Penalty: Reduces the likelihood of selecting a token that has already appeared in the sequence, encouraging new word usage.
• Frequency Penalty: Penalizes tokens proportionally to how often they’ve already been used, making repeated words progressively less likely.

These penalties are applied early in the token selection process, adjusting the raw probabilities before other sampling strategies are applied. Think of them as gentle nudges encouraging the model to explore new vocabulary.

Beam Search: Balancing Exploration and Cost

In LLM inference, beam search is a decoding strategy designed to enhance text generation quality by evaluating multiple potential output sequences at once, rather than following only the single most probable path. This leads to more coherent, accurate, and contextually appropriate outputs.

Rather than committing to the highest-probability token at every step (as greedy search does), beam search keeps several possible sequences (called “beams”) open simultaneously, much like a chess player who plans several moves ahead. It adopts a broader view, considering multiple paths before deciding which one to continue.

Here’s a basic overview of how beam search works:

• Maintain a set of multiple candidate sequences (typically between 5–10).
• For each candidate, compute the probabilities of possible next tokens.
• Expand all candidate sequences by adding potential next tokens.
• Keep only the top-scoring sequences based on overall probability.
• Repeat the process until a stopping condition is met (e.g., reaching a maximum sequence length or generating an end-of-sequence token).
• Select the highest-probability full sequence as the final output.

Using a graph-search analogy, if we wanted to find the most optimal text sequence for a given query, we would ideally explore all possible token combinations — a task similar to the **A*** search algorithm (which seeks the lowest-cost, most efficient path, not necessarily the shortest). However, because natural language generation involves an enormous search space, exhaustive exploration is computationally impractical.

Beam search trims this search space to a manageable set of candidate paths — typically exploring only 4, 8, or 12 alternatives. It approximates an A-like optimal outcome by continually pruning the list of candidates to retain only the top k* most promising sequences at each step, based on cumulative likelihood scores.

https://huggingface.co/learn/llm-course/chapter1/8?fw=pt

Advantages of Beam Search:

• Improved Output Quality: By evaluating multiple possible continuations, beam search tends to produce more coherent, fluent, and contextually accurate text.
• Better for Complex Tasks: Especially beneficial for tasks like machine translation, summarization, and dialogue generation, where the best sequence isn’t always the most immediately probable one.

Limitations:

• Higher Computational Cost: Because it processes multiple sequences at once, beam search requires significantly more computation than greedy search.
• Need for Hyperparameter Tuning: Choosing the appropriate beam width (number of beams) is crucial. A narrow beam may miss better sequences, while a wide beam increases computational burden without guaranteed gains.

Summary

Both strategies rely on the transformer’s self-attention mechanism to contextualize input tokens and cross-attention (in encoder-decoder models) to align output with source context. The model’s hidden states evolve dynamically during generation, with each token choice influencing subsequent predictions through these attention layers

While beam search generally produces higher-quality text, its computational demands make greedy search preferable for applications prioritizing speed over linguistic perfection. Modern systems often hybridize approaches-using beam search for critical sections and falling back to greedy methods for efficiency

Appendix

1. https://towardsdatascience.com/temperature-scaling-and-beam-search-text-generation-in-llms-for-the-ml-adjacent-21212cc5dddb/
2. The Stanford CS224N course materials are a great resource for these concepts.