Why do production chat APIs almost never offer beam search as a decoding option?
Greedy and sampling cost roughly one forward pass per token. Beam search multiplies that by beam width and best-of-n by n, so they raise serving cost most in a memory-bound regime.
Imagine writing one sentence at a time. Greedy decoding is writing the single best next word and moving on, one pass of thought per word. Sampling is the same effort, but you roll dice to pick among the good words. Beam search is keeping several half-finished drafts alive at once and extending all of them every step, so four drafts means four times the work and four times the scratch paper. Best-of-n is writing the whole answer from scratch n separate times and keeping your favorite, so n full passes. The lesson: greedy and sampling are cheap because they keep one draft. Beam and best-of-n are expensive because they keep many, and on a busy server that extra memory and compute is what hurts.
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 the layer that sits on top of the model's logits and decides which tokens actually come out. It is easy to treat this as a quality knob alone, but every decoding strategy also carries a serving cost, and those costs differ by orders of magnitude. The interview question hiding inside almost every decoding discussion is: which strategy raises serving cost the most, and why?
The answer turns on one structural fact. Greedy decoding and sampling are single-path strategies. They follow exactly one sequence and spend roughly one forward pass per generated token. Beam search and best-of-n are multi-path strategies. They keep many candidate sequences alive, and the number of paths is a direct multiplier on both compute and, more importantly, on KV-cache memory.
This deep dive walks the full cost ladder. We classify each strategy by its path count, derive the multiplier each one applies, and then explain why in a 2026 memory-bandwidth-bound serving regime the multiplier on the cache, not on FLOPs, is what actually decides throughput and dollar cost per token. By the end you should be able to rank greedy, sampling, beam search, and best-of-n by serving cost on a whiteboard and defend the ranking, and explain why speculative decoding sits below all of them.
The two cost classes: single-path versus multi-path
Every decoding strategy reduces to a question of how many sequences you keep alive at once. That count is the dominant cost driver, far more than any logit math. Get this classification right and the cost ranking falls out automatically.
Single-path strategies follow one sequence. Greedy decoding takes the argmax token each step. Sampling draws from the distribution, usually after shaping it with temperature, top-k, top-p, or min-p. Both do one forward pass per token and hold one KV cache. Their costs are essentially identical, because the sampling math is a trivial transform over a logit vector that the forward pass already produced. A temperature divide and a top-p sort cost nothing measurable next to the matmuls of a forward pass.
Multi-path strategies keep several sequences. Beam search holds a frontier of width B and extends all of them each step. Best-of-n produces n complete independent generations. In both cases the path count becomes a multiplier on the work and the memory. That multiplier is the entire story of why some strategies are cheap to serve and some are not.
The subtlety that separates beam search from best-of-n is interaction. Beam search couples its paths: at every step it pools all expansions and re-prunes to the global top B, so the beams share a synchronized clock and a joint scoring frontier. Best-of-n does not couple at all; the n sequences are fully independent runs that only meet at the final scoring step. That difference does not change the raw multiplier, but it changes everything about how you can schedule and amortize the cost, as the later sections show.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
Real products, models, and research that use this idea.
- OpenAI and Anthropic chat APIs expose temperature and top-p but not beam search, since sampling fits memory-bound serving.
- vLLM and SGLang implement best-of-n by batching n parallel sequences so the independent samples amortize HBM reads.
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy does the beam-width multiplier hurt more on KV-cache memory than on FLOPs?
Decode is memory-bandwidth-bound, so the binding resource is HBM traffic streaming the cache, not arithmetic. Batch size is set by available cache memory. Multiplying cache by B directly divides the number of concurrent requests you can serve, which is what sets throughput economics.
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.
Treating all decoding strategies as equal cost. Greedy and sampling are about one pass per token; beam search multiplies by beam width and best-of-n multiplies by n, including the KV cache.
60 second bullets to scan on the way to the call.
Cost of greedy versus sampling and why they are about equal
What beam width multiplies and on which two axes
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.