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?
Free · 2 AI evals / day
Every decoding strategy runs the same transformer forward pass to produce a probability distribution over the next token. What differs is how you turn that distribution into a chosen token, and how many candidate sequences you keep alive while doing it.
**Greedy decoding** takes the single highest-probability token every step. It runs one forward pass per token and keeps one KV cache, so its cost is the 1x baseline. The output is deterministic, which is great for tests and strict code generation.
Sampling, including temperature and top-p, draws a token randomly from the distribution instead of taking the argmax. The forward pass is identical to greedy, so the compute and cache cost are also 1x. The only extra work is a cheap random draw. This is what chat uses, because a little randomness makes replies feel natural and varied.
Beam search is the expensive one. It keeps several candidate sequences alive at once, extends each, and prunes back to the best few. With width B you run roughly B model passes per step and hold B separate caches, so both compute and memory scale with B. That suits low-creativity tasks like translation but is too costly for serving open-ended chat at scale.
All three share the same per-token forward pass. The cost difference is how many sequences each keeps alive.
**Greedy** picks the argmax token, runs one pass, and is deterministic. Sampling draws from the same distribution. Its compute and cache cost match greedy exactly, plus a negligible random draw. Both are 1x baseline cost. Greedy suits reproducible tasks like tests. Sampling suits chat, where diversity helps.
Beam search at width B keeps B hypotheses alive. Each beam needs its own KV cache, so memory scales by B. Each step extends all beams, so decode compute also scales by B. It once dominated translation and summarization. There, low-entropy targets reward searching for the highest-probability sequence.
Chat APIs dropped beam for three reasons. First, open-ended chat is high entropy. Beam collapses toward bland, repetitive text. Second, the Bx KV memory wrecks serving throughput in a bandwidth-bound regime. Third, RLHF already shapes the distribution so a single sample reads well. Best-of-n and self-consistency, which sample n full outputs, cost n times but stay parallel and cache-cheap per stream.
Quick reference
TL;DR
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.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Reaching for beam search on an open-ended chat or creative writing product High entropy outputs mode collapse under beam, and the Bx KV cost wrecks serving throughput.
Using greedy decoding where output diversity is the product requirement Greedy is deterministic, so repeated calls return the same text and feel robotic in chat.
Spending best-of-n sampling on simple low ambiguity prompts The n times cost buys little when one sample is already correct, so the multiplier is wasted.
Picking high temperature sampling for strict structured or code output Randomness raises the rate of invalid syntax; low temperature or greedy is safer there.
Quick scan · 2–4 min
Everything important, quickly.
4 min: 1x cost of greedy and sampling, then beam's Bx compute and Bx KV cost, then why chat dropped beam (entropy, serving cost, RLHF), then best-of-n versus self-consistency cost tiers.
Side-by-side
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-world examples
Real products, models, and research that use this idea.
1OpenAI's chat completions API exposes temperature and top_p but quietly dropped the legacy best_of beam-style parameter for chat models.
2vLLM and SGLang default to sampling with continuous batching; enabling beam search collapses their throughput because each beam claims a separate paged KV allocation.
3Google Translate and classic summarization stacks historically used beam search width 4 to 5, where low-entropy targets reward highest-probability decoding.
4Self-consistency on Gemini 3.1 Pro and DeepSeek V4 samples many chains of thought at temperature, then majority-votes the final answer, paying n times the decode cost.
5Claude Opus 4.7 and GPT-5.5 serve chat with temperature sampling; the post-RLHF distribution is sharp enough that a single sample reads cleanly.
Interviewer follow-ups
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy does beam search multiply KV memory and not just compute?
Sign in or go Pro to see the approach for this follow-up.
QHow does best-of-n differ from beam search in both cost and quality behavior?
Sign in or go Pro to see the approach for this follow-up.
QIf beam search is gone from chat, why is self-consistency still used for reasoning?
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
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.