Compare greedy decoding, sampling (temperature / top-p), and beam search at inference time along three axes: per step compute cost, per step KV-cache cost, and what use case each is appropriate for. Why has beam search nearly disappeared from modern chat APIs?
Greedy and sampling are both 1x cost on one KV trajectory; beam search at width B costs roughly Bx compute and Bx KV memory, which is why chat APIs dropped it.
Imagine writing a story one word at a time. Greedy decoding always picks the single most likely next word, like a writer who never second-guesses. Sampling rolls a weighted die instead, so the story varies and feels more natural, but it still writes just one story. Beam search is different: it keeps several half-finished stories alive at once, extends each, and keeps only the best few. That is smarter for short, low-creativity tasks like translation. But keeping many stories alive means many notebooks of running notes, and that gets expensive fast. For a long, chatty answer those extra notebooks cost a lot and the result often turns repetitive, so chat systems stopped bothering.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Decoding strategy is where model quality meets serving economics. The same trained model can be cheap or ruinously expensive to run depending only on how you turn its next-token distribution into text. That makes this a favorite interview question: it tests whether a candidate can separate the parts of inference that cost nothing extra from the parts that multiply your GPU bill. The naive intuition is that fancier decoding means more compute, full stop. The precise reality is sharper, because two of the three classic strategies cost exactly the same and only one of them multiplies your resource budget.
The central fact is that every strategy shares the same forward pass. A transformer decode step takes the running KV cache plus the latest token, runs attention and feed-forward layers, and emits a probability distribution over the vocabulary. Greedy, sampling, and beam all consume that identical distribution. They differ only in the selection rule applied afterward and, crucially, in how many candidate sequences they keep alive at the same time. The number of live sequences is the variable that drives cost, because each live sequence carries its own KV cache and demands its own forward pass per step.
This deep dive works through the three classic strategies along compute and KV-cache cost, explains why decode is bandwidth bound and why that makes beam search uneconomical, then steps through the entropy and alignment arguments that finished beam off in chat. It closes with the broader cost ladder of best-of-n, self-consistency, and speculative decoding, plus a concrete worked example so you can do the arithmetic on a whiteboard. The throughline is a single principle: pay a cost multiplier only when the quality gain justifies it, and know exactly which resource each strategy multiplies.
Greedy and sampling: the 1x baseline
Greedy decoding takes the argmax of the next-token distribution at every step. It runs exactly one forward pass per token, appends one new key and value to a single KV cache, and emits one token. Cost is the 1x baseline against which everything else is measured. Because argmax is deterministic, the same prompt always yields the same output, which is exactly what you want for regression tests and strict structured generation. The trade is that greedy can get locally trapped, committing to a high-probability first token that leads into a worse overall sequence, since it never reconsiders.
Sampling reshapes the logits and then draws a token at random. Temperature divides the logits by a scalar before softmax: lower temperature sharpens toward greedy, higher temperature flattens toward uniform. Top-p (nucleus) keeps the smallest set of tokens whose cumulative probability reaches p and renormalizes over that set, so the candidate pool grows when the model is uncertain and shrinks when it is confident. Top-k instead keeps a fixed number of top tokens. Production chat typically combines a temperature near 0.7 to 1.0 with top-p around 0.9 to 0.95.
The key insight: none of this changes the forward pass. The expensive matmuls already happened to produce the distribution. Temperature scaling, truncation, and the random draw are vector operations over the vocabulary, negligible next to the attention and feed-forward compute. So sampling is also 1x compute and 1x KV cost. It holds exactly one trajectory and one cache, identical to greedy. The only thing it sacrifices is determinism, which is precisely what chat wants and what reproducible test harnesses do not.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| Strategy | Per-step compute | Per-step KV cost | Best use case |
|---|---|---|---|
| Greedy (argmax) | 1x | 1x (one cache) | Deterministic, reproducible output |
| Sampling (temp / top-p) | 1x | 1x (one cache) | Open-ended chat, diversity |
| Beam search (width B) | ~Bx | ~Bx (one cache per beam) | Translation, summarization |
| Best-of-n / self-consistency | ~nx (parallel) | ~nx across streams | Reasoning quality boost |
Real products, models, and research that use this idea.
- OpenAI's chat completions API exposes temperature and top_p but quietly dropped the legacy best_of beam-style parameter for chat models.
- vLLM and SGLang default to sampling with continuous batching; enabling beam search collapses their throughput because each beam claims a separate paged KV allocation.
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy does beam search multiply KV memory and not just compute?
Each beam is a distinct partial sequence with its own attention history. That history is exactly what the KV cache stores, so B beams need B caches living in HBM simultaneously, on top of the B forward passes.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Claiming temperature sampling costs more than greedy. The forward pass is identical; only a cheap random draw differs. The real cost multiplier is beam width, not the sampling logic.
60 second bullets to scan on the way to the call.
Why greedy and sampling share identical compute and cache cost
How beam width multiplies both KV memory and decode compute
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.