Decoding Performance: Beam Search vs Sampling — Latency, Throughput, Memory, and the Full Design Space

A transformer-based language model does not produce text. It produces logits — a vector of raw scores over a vocabulary of tens or hundreds of thousands of tokens. The question of how you turn those logits into an actual token sequence is the decoding problem, and it is simultaneously a question about output quality, inference latency, memory consumption, and throughput. Get it wrong and you either produce degenerate text or burn three times the GPU budget you need.

This post is a comprehensive treatment of the decoding design space. We will start from the simplest possible strategy (greedy argmax), build up through temperature scaling, top-k, and top-p sampling, cover beam search in detail, analyze the performance characteristics of each approach with real numbers, examine the emerging world of constrained and grammar-guided decoding, and conclude with a practical decision framework for production systems.

The decoding design space

After the model’s final layer produces a logit vector $z \in \mathbb{R}^V$ (where $V$ is the vocabulary size), every decoding strategy answers the same question: which token do we emit next? The answer determines not just the quality of the output but also the computational cost of producing it.

The design space breaks down along two axes. The first axis is determinism vs stochasticity: do we always pick the highest-scoring token, or do we inject randomness? The second axis is single-hypothesis vs multi-hypothesis: do we maintain one partial sequence or several?

Every strategy shares the same forward pass through the model. The differences lie entirely in what happens after the logits are produced. This is important from a performance perspective: the model forward pass typically dominates wall-clock time, so the selection overhead is often small — but not always, and when you move to beam search the forward pass itself gets multiplied.

Greedy decoding

The simplest possible strategy is greedy decoding: take the argmax of the logit vector at every step.

$$x_t = \arg\max_{i \in \{1, \dots, V\}} z_i$$

There is no softmax, no sampling, no randomness. You just find the index of the largest logit and emit that token. The computational cost of this selection step is $O(V)$ — a single linear scan.

Why greedy decoding matters

Greedy decoding is not a strategy you would typically deploy in production for user-facing text generation. Its outputs tend to be repetitive and dull. The model often falls into loops, repeating the same phrase or sentence structure because the locally highest-probability token at each step tends to reinforce patterns that lead back to the same locally highest-probability token.

However, greedy decoding is extremely useful as a performance baseline. Because it has essentially zero overhead beyond the forward pass, any latency you measure under greedy decoding represents the floor — the minimum time the model needs to produce a token. When you switch to a more sophisticated strategy, the difference in latency tells you exactly how much overhead that strategy introduces.

Greedy decoding is also deterministic, which makes it valuable for debugging and regression testing. The same prompt will always produce the same output, eliminating one source of variance when tracking down issues.

Performance profile

• Forward passes per token: 1
• Selection cost: $O(V)$ argmax
• KV cache: 1x (single sequence)
• Memory overhead: Negligible beyond model weights and KV cache

This is the cheapest possible decoding strategy and the one against which everything else should be measured.

Temperature sampling

Temperature sampling introduces stochasticity by converting logits into a probability distribution and then sampling from it. The key insight is that a temperature parameter $T$ controls how peaked or flat the distribution is.

Given logits $z \in \mathbb{R}^V$, we compute:

$$P(x_t = i) = \frac{\exp(z_i / T)}{\sum_{j=1}^{V} \exp(z_j / T)}$$

The temperature $T$ is a positive scalar that divides the logits before the softmax. Its effect is intuitive:

• $T \to 0$: The distribution becomes infinitely peaked. The highest logit gets probability approaching 1. In the limit, this is greedy decoding.
• $T = 1$: The distribution is the model’s “native” output — whatever the training process produced.
• $T \to \infty$: The distribution becomes uniform. Every token in the vocabulary is equally likely. The output becomes random noise.

Choosing temperature for different use cases

Temperature is the most commonly tuned decoding parameter, and the right value depends heavily on the application.

Performance profile

Temperature sampling adds two operations beyond the forward pass: dividing the logit vector by $T$ (an $O(V)$ elementwise operation that is trivially cheap), computing the softmax ($O(V)$), and sampling from the resulting distribution. The sampling step itself is typically implemented as computing the cumulative distribution function (CDF) and performing a binary search for a uniform random number, which is $O(V)$ for the CDF and $O(\log V)$ for the search.

In practice, the total overhead of temperature sampling over greedy decoding is negligible. The softmax and sampling together take microseconds on a GPU, while the model forward pass takes milliseconds. You would need an extraordinarily small model or an extraordinarily large vocabulary before this overhead became measurable.

Top-k sampling

Pure temperature sampling has a problem: even at moderate temperatures, the long tail of the vocabulary distribution can produce nonsensical tokens. If the model assigns probability 0.001 to a completely irrelevant token, temperature sampling will occasionally select it — and in a long generation, “occasionally” becomes “frequently enough to be annoying.”

Top-k sampling addresses this by truncating the distribution. After computing logits (optionally scaled by temperature), we:

1. Find the $k$ tokens with the highest logits.
2. Set all other logits to $-\infty$ (effectively zeroing their probabilities after softmax).
3. Apply softmax to the remaining $k$ logits.
4. Sample from this truncated distribution.

$$z'_i = \begin{cases} z_i & \text{if } z_i \text{ is among the top-}k \text{ logits} \\ -\infty & \text{otherwise} \end{cases}$$ $$P(x_t = i) = \frac{\exp(z'_i / T)}{\sum_{j=1}^{V} \exp(z'_j / T)}$$

The $k = 40$ default and its history

The value $k = 40$ became a widely used default after the 2018 paper by Fan et al. on hierarchical story generation. They found that $k = 40$ produced a good balance between diversity and coherence for their task. This default propagated through the Hugging Face Transformers library and became the de facto standard.

However, $k = 40$ is not universally optimal. For large vocabulary models (100k+ tokens), $k = 40$ might be too restrictive, cutting off legitimate continuations. For highly structured tasks like code generation, even $k = 40$ might be too permissive.

The fundamental problem with top-k

Top-k has a conceptual flaw: it uses a fixed cutoff regardless of the shape of the distribution. Consider two scenarios:

Scenario A: The model is very confident. The top token has probability 0.9, the second has 0.05, and the rest are negligible. Here, $k = 40$ keeps 38 tokens that the model considers extremely unlikely. You are sampling from noise.

Scenario B: The model is uncertain. The probability is spread fairly evenly across 200 plausible next tokens, each with probability around 0.005. Here, $k = 40$ cuts off 160 perfectly reasonable continuations. You are artificially restricting the model’s expressiveness.

This inflexibility is what motivated the development of top-p sampling.

Performance profile

The main computational cost of top-k is the partial sort needed to find the $k$ largest elements. A naive implementation takes $O(V)$ using a selection algorithm like introselect. A heap-based approach takes $O(V \log k)$. On GPUs, radix-sort-based implementations can find top-k in $O(V)$ time with good parallelism.

Even at $V = 250k$, the top-k selection takes roughly 20 microseconds on an A100 — still negligible compared to the forward pass. The overhead only becomes relevant for very small models (sub-1B parameters) where the forward pass itself is fast.

Top-p (nucleus) sampling

Top-p sampling, introduced by Holtzman et al. in 2019 under the name “nucleus sampling,” solves the adaptivity problem of top-k. Instead of keeping a fixed number of tokens, it keeps the smallest set of tokens whose cumulative probability exceeds a threshold $p$.

The algorithm:

1. Compute softmax probabilities from the (optionally temperature-scaled) logits.
2. Sort tokens by probability in descending order.
3. Compute the cumulative sum of probabilities.
4. Find the smallest index $k^*$ such that the cumulative sum exceeds $p$.
5. Zero out all tokens beyond index $k^*$.
6. Renormalize the remaining probabilities.
7. Sample from the renormalized distribution.

$$k^* = \min \left\{ k : \sum_{i=1}^{k} P_{\text{sorted}}(i) \geq p \right\}$$

Why top-p is preferred over top-k

The key advantage is adaptivity to the distribution shape. When the model is confident (peaked distribution), top-p naturally keeps fewer tokens — perhaps only 2 or 3. When the model is uncertain (flat distribution), top-p keeps many more — perhaps 100 or 200. The parameter $p$ controls the total probability mass retained, not the count of tokens.

This means $p = 0.95$ is a much more stable default than $k = 40$. Regardless of whether the model is outputting the only plausible next word in a fixed expression or choosing among dozens of valid continuations, $p = 0.95$ ensures that the sampled token is always within the model’s “plausible set” while excluding only the lowest-probability tail.

Practical top-p values

• $p = 1.0$: No truncation. Equivalent to pure temperature sampling.
• $p = 0.95$: The most common default. Keeps the top 95% of the probability mass, which usually eliminates obviously wrong tokens while retaining diversity.
• $p = 0.9$: Slightly more conservative. Good for tasks where you want diversity but not too much risk.
• $p = 0.5$: Aggressive truncation. Only tokens in the upper half of the probability mass are considered. Produces more predictable, less diverse output.

Performance profile

Top-p is slightly more expensive than top-k because it requires a full sort of the probability vector (or at least a partial sort until the cumulative sum exceeds $p$). A full sort is $O(V \log V)$ compared to top-k’s $O(V \log k)$ or $O(V)$.

However, efficient GPU implementations use radix sort, which is $O(V)$ in practice for the fixed-width floating-point values used in inference. The overhead remains in the microsecond range.

The critical takeaway: all single-hypothesis sampling strategies have negligible overhead compared to the model forward pass. The performance differences between greedy, top-k, and top-p are academically interesting but practically irrelevant for models larger than about 1B parameters.

Beam search

Beam search is fundamentally different from all sampling strategies because it maintains multiple hypotheses simultaneously. Instead of committing to one token at each step, beam search explores $B$ partial sequences (called “beams”) in parallel, keeping the $B$ highest-scoring sequences at each step.

The algorithm

1. Start with $B$ copies of the input prefix.
2. At each generation step, for each of the $B$ beams, compute the logits (run the model forward pass).
3. For each beam, consider all $V$ possible next tokens. Score each candidate as the beam’s accumulated log-probability plus the new token’s log-probability.
4. Among all $B \times V$ candidates, select the top $B$ by total score.
5. Update the beams to these $B$ sequences.
6. Repeat until all beams produce an end-of-sequence token or hit the maximum length.

The scoring for a beam at step $t$:

$$\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log P(y_i \mid y_{1:i-1})$$

And the selection step:

$$\text{beams}_{t} = \operatorname{top\text{-}B}\left(\bigcup_{b=1}^{B} \left\{ (\text{beam}_b, w) : w \in \{1, \dots, V\} \right\}, \text{by score}\right)$$

Compute cost: $B$ times the forward passes

The most obvious cost of beam search is that it requires $B$ forward passes per generation step — or equivalently, one batched forward pass with batch size $B$. If a single forward pass takes time $T_{\text{model}}$, then beam search takes:

$$T_{\text{beam}} \approx \frac{B \cdot T_{\text{model}}}{E(B)} + T_{\text{select}}$$

where $E(B)$ is the batching efficiency. On GPUs, batching efficiency is high for small $B$ (the forward pass is memory-bandwidth-bound and can process small batches with near-zero overhead), so $E(B) \approx 1$ for $B \leq 4$ on typical hardware. This means 4-beam search costs about $4\times$ the compute but only about $1.5$-$2\times$ the wall-clock time of single-beam decoding, because the batched forward pass amortizes some overhead.

However, as $B$ grows, batching efficiency degrades because:

• KV cache memory grows linearly with $B$, potentially causing memory pressure.
• The batched matrix multiplications become compute-bound rather than memory-bandwidth-bound.
• Cache locality suffers as $B$ beams compete for GPU memory.

Memory cost: $B$ times the KV cache

This is the real killer. The KV cache stores the key and value tensors for all previous tokens in the sequence, and beam search requires a separate KV cache for each beam (since each beam has a different token history).

For a model with $L$ layers, $H$ attention heads, head dimension $d$, and sequence length $S$, the KV cache for a single beam is:

$$\text{KV}_{\text{single}} = 2 \times L \times H \times d \times S \times \text{dtype\_bytes}$$

For a typical 7B parameter model (32 layers, 32 heads, dimension 128, FP16):

$$\text{KV}_{\text{single}} = 2 \times 32 \times 32 \times 128 \times S \times 2 = 524{,}288 \times S \text{ bytes}$$

At $S = 2048$ tokens, that is roughly 1 GB per beam. With $B = 4$ beams, you need 4 GB just for the KV cache — on top of the model weights, activations, and other overhead.

def kv_cache_bytes(layers, heads, head_dim, seq_len, beams=1, dtype_bytes=2):
    """Calculate KV cache memory in bytes."""
    # Factor of 2 for K + V
    per_beam = 2 * layers * heads * head_dim * seq_len * dtype_bytes
    return per_beam * beams

# Example: 7B model, 2048 tokens, 4 beams
single = kv_cache_bytes(32, 32, 128, 2048, beams=1)  # ~1.07 GB
beam_4 = kv_cache_bytes(32, 32, 128, 2048, beams=4)   # ~4.29 GB
beam_8 = kv_cache_bytes(32, 32, 128, 2048, beams=8)   # ~8.59 GB

Selection overhead: top-B over $B \times V$ candidates

At each step, beam search must select the top $B$ candidates from $B \times V$ total options. For $B = 4$ and $V = 128{,}000$, that is a top-4 selection over 512,000 candidates. This is more expensive than the top-k selection in sampling (which operates over $V$ candidates), but it is still $O(B \times V)$ and well within the “negligible compared to the forward pass” regime.

The more significant overhead is the beam management: tracking which beams survive, reordering KV caches to match the surviving beams, and handling the bookkeeping for early termination of beams that have produced an end-of-sequence token.

Performance analysis: the full picture

Now let us put concrete numbers on these strategies. We will analyze three dimensions: latency per token, throughput (tokens per second across a batch of requests), and peak memory consumption.

Sampling: the lean path

A single-hypothesis sampling strategy (greedy, temperature, top-k, or top-p) has the following per-token cost:

$$T_{\text{sample}} = T_{\text{forward}} + T_{\text{softmax}} + T_{\text{select}} + T_{\text{sample}}$$

Where:

• $T_{\text{forward}}$: the model forward pass (dominates, typically 8-15 ms for a 7B model on A100)
• $T_{\text{softmax}}$: $O(V)$ exponentiation and normalization (~5-15 us)
• $T_{\text{select}}$: $O(V)$ for top-k, $O(V \log V)$ for top-p (5-15 us)
• $T_{\text{sample}}$: CDF computation and binary search (~2-5 us)

Total selection overhead: roughly 10-35 microseconds, or less than 0.3% of the forward pass time.

Memory consumption is simply the model weights plus one KV cache:

$$M_{\text{sample}} = M_{\text{model}} + \text{KV}_{\text{single}}$$

Beam search: the multiplicative path

Beam search at width $B$ has per-token cost:

$$T_{\text{beam}} = \frac{B \cdot T_{\text{forward}}}{E(B)} + T_{\text{select}}(B \times V) + T_{\text{reorder}}$$

Where:

• $\frac{B \cdot T_{\text{forward}}}{E(B)}$: batched forward pass for $B$ beams
• $T_{\text{select}}(B \times V)$: top-B selection over all candidates
• $T_{\text{reorder}}$: KV cache reordering for surviving beams

The batching efficiency $E(B)$ is crucial. Let us look at measured values.

The overhead factor tells the real story. At $B = 4$, beam search takes about $1.75\times$ the wall time of sampling — not $4\times$, thanks to batching. But at $B = 8$, the overhead jumps to $3.17\times$ as memory pressure starts to dominate. At $B = 16$, you are paying $6\times$ for a strategy that rarely provides meaningfully better output than $B = 4$.

Memory scaling

Memory is where beam search truly hurts. The KV cache scales linearly with beam width, and at long sequence lengths this dominates GPU memory.

At $B = 16$ and $S = 2048$, the KV cache alone consumes roughly 16 GB — more than the model weights for a 7B model in FP16. If you are serving multiple concurrent requests, this memory pressure forces smaller batch sizes, which destroys throughput.

Throughput comparison

Throughput (tokens per second across concurrent requests) is the metric that matters most for serving. Because beam search consumes more memory per request, it allows fewer concurrent requests, which reduces aggregate throughput.

The numbers are stark. Beam search with $B = 4$ delivers one-fifth the throughput of sampling. At $B = 8$, it is less than one-fourteenth. This is not because beam search is computationally expensive per se — it is because the KV cache memory consumption limits how many requests you can serve concurrently.

Latency breakdown at different model scales

The relationship between beam width and overhead changes with model size. Larger models have longer forward passes, which means the fixed overhead of beam management becomes proportionally smaller — but the KV cache also grows.

For the 70B model, beam search at $B = 4$ costs nearly $2\times$ the latency of sampling. The KV cache reordering becomes non-trivial (2.1 ms) because there are more layers to reorder and the caches are physically larger.

Structured output and constrained decoding

A rapidly growing area of the decoding design space is constrained decoding, where the generation is forced to conform to a grammar, schema, or set of rules. The most common application is generating valid JSON that matches a specific schema, but the technique generalizes to any context-free grammar.

How it works

Constrained decoding operates by modifying the logit vector at each step. Before sampling or argmax, it sets the logits of all tokens that would violate the grammar to $-\infty$. This is called logit masking or logit biasing.

The process:

1. Maintain a grammar state (e.g., a position in a finite state machine or pushdown automaton).
2. At each generation step, determine which tokens are valid continuations from the current state.
3. Set all other logits to $-\infty$.
4. Proceed with normal decoding (sampling, greedy, or beam search) over the remaining valid tokens.
5. After emitting a token, advance the grammar state.

For JSON generation, the grammar state tracks things like “we are inside a string literal,” “we expect a colon after a key,” or “we need to close this array bracket.” The set of valid next tokens changes at each step based on this state.

Performance implications

The main cost of constrained decoding is computing the valid token mask at each step. For a simple grammar (like JSON), the number of grammar states is small (on the order of dozens) and the mask computation is fast — typically a lookup table indexed by grammar state, returning a precomputed bitmask over the vocabulary.

For more complex grammars, the mask computation can be more expensive. However, several frameworks have developed efficient implementations:

Outlines (by .txt) precompiles regular expressions and context-free grammars into finite state machines and precomputes the valid token set for each state. The per-step cost is a single lookup plus a bitmask application — $O(V)$ for the mask but with excellent memory access patterns.

SGLang takes this further with FSM (finite state machine) acceleration that caches state transitions and uses RadixAttention for prefix sharing. Their constrained decoding adds less than 5% overhead over unconstrained generation for typical JSON schemas.

Combining with beam search

Constrained decoding can be combined with beam search to explore multiple valid structured outputs. However, this multiplies both the KV cache cost (from beam search) and the grammar state tracking (one state per beam). In practice, constrained decoding with sampling is almost always sufficient because the grammar constraints eliminate most of the “bad” outputs that beam search was meant to avoid.

The KV cache killer: beam search and memory optimization

We have established that beam search’s primary cost is the $B\times$ multiplication of the KV cache. Let us examine the optimizations that mitigate this.

Shared-prefix optimization (copy-on-write)

In beam search, all beams start from the same prefix. For the first several steps, many beams share identical token histories. The shared-prefix optimization (also called copy-on-write) exploits this by sharing KV cache pages across beams that have identical prefixes.

The implementation mirrors virtual memory copy-on-write:

1. All beams initially point to the same physical KV cache pages.
2. When a beam diverges (selects a different token than another beam), only the new page is allocated and the previous shared pages remain shared.
3. When a beam is pruned, its unique pages are freed.

The savings depend on how quickly beams diverge. In practice:

With shared-prefix optimization, $B = 4$ beam search uses roughly $2.0$-$3.0\times$ the KV cache memory instead of a naive $4.0\times$. This is a 30-60% reduction in memory overhead, which can translate to significantly more concurrent requests in a serving environment.

Paged attention and beam search

Systems like vLLM use paged attention, which manages the KV cache as a set of fixed-size pages (analogous to OS virtual memory pages). This naturally enables copy-on-write for beam search: beams share pages for their common prefix and allocate new pages only for divergent suffixes.

Paged attention also eliminates the memory fragmentation that plagues naive KV cache implementations. Without paging, each beam’s KV cache must be a contiguous allocation, leading to fragmentation as beams are created and pruned. With paging, the physical memory can be reused efficiently.

Even with all optimizations, beam search at $B = 4$ still uses roughly $2\times$ the memory of sampling. The fundamental issue remains: beam search requires distinct state for distinct hypotheses, and there is no way around that.

Speculative decoding interaction

Speculative decoding (using a small draft model to propose tokens that the large model verifies in parallel) interacts poorly with beam search. Speculative decoding assumes a single hypothesis — the draft model proposes one sequence, and the large model verifies it. Extending this to $B$ beams would require the draft model to propose $B$ sequences, eliminating most of the speedup.

For this reason, speculative decoding is almost exclusively used with sampling strategies. This further widens the practical performance gap between sampling and beam search in production deployments that use speculative decoding.

When to use what: a practical decision framework

Given everything we have covered, here is a concrete decision framework for choosing a decoding strategy.

Chat and conversational AI: top-p sampling

Recommended: $T = 0.7$, $p = 0.95$, with a repetition penalty of 1.1.

Conversational applications require low latency (users expect responses within 100-200 ms per token for streaming) and high throughput (many concurrent users). Top-p sampling delivers both while providing sufficient diversity to keep conversations natural.

Beam search is inappropriate here. The quality improvement is marginal for conversational text (where there is no single “correct” answer), and the memory overhead would slash your concurrent user capacity by 3-5x.

Code generation: low temperature

Recommended: $T = 0.1$-$0.3$, $p = 0.95$ (or even greedy with repetition penalty).

Code has a much narrower distribution of correct continuations than natural language. A missing semicolon or wrong variable name produces a syntax error. Low temperature keeps the model on its most confident path, which is usually the syntactically and semantically correct one.

Some code generation systems use a slightly higher temperature ($T = 0.4$-$0.6$) and generate multiple samples independently, then rank them with a separate verifier (execution-based or model-based). This “sample-and-rank” approach achieves similar quality to beam search while maintaining the throughput advantages of sampling.

Machine translation: small beam search

Recommended: $B = 4$-$5$, with length normalization.

Translation is the classic beam search use case, and it remains one of the few tasks where beam search demonstrably outperforms sampling. The reason is that translation has a relatively peaked output distribution (there are only so many ways to say the same thing in the target language), and the quality metric (BLEU) rewards finding the single best translation rather than a diverse set.

However, even here, the trend is toward sampling. Recent work on quality-aware decoding shows that sampling with a reranker can match beam search quality at lower compute cost, especially for large models that are already well-calibrated.

Batch inference and offline processing: sampling with high throughput

Recommended: Top-p sampling, maximize batch size.

When processing large datasets offline (e.g., generating summaries for millions of documents), throughput is everything. Sampling allows you to pack the maximum number of requests per GPU, achieving 5-15x the throughput of beam search at the same hardware cost.

If quality is critical, generate $N$ samples per input and select the best one with a reward model or heuristic. This “best-of-N” approach is more hardware-efficient than $N$-beam search because the $N$ samples do not require KV cache sharing or beam management overhead.

Structured output (JSON, SQL, etc.): constrained sampling

Recommended: Constrained decoding with top-p sampling, $T = 0.3$-$0.7$.

When the output must conform to a grammar, constrained decoding eliminates the possibility of format violations. This makes beam search unnecessary for format correctness — the grammar mask handles it. Use low temperature for accuracy-critical schemas and moderate temperature when the content within the structure should be diverse.

Advanced topic: combining strategies

Modern inference frameworks often combine multiple strategies. Some noteworthy combinations:

Min-p sampling

A recent alternative to top-p that sets a minimum probability threshold relative to the top token. If the top token has probability $p_{\text{max}}$, min-p keeps all tokens with probability at least $\text{min\_p} \times p_{\text{max}}$. This is even more adaptive than top-p because the threshold scales with the model’s confidence on the top token.

Top-k then top-p

Apply top-k first (as a hard ceiling on the number of candidates), then top-p within the survivors. This provides a safety bound: even if the distribution is very flat, you never consider more than $k$ tokens. Typical values: $k = 100$, $p = 0.95$.

Sample-and-rank (best-of-N)

Generate $N$ independent samples with sampling, then select the best one using a reward model, log-probability, or task-specific metric. This achieves many of the quality benefits of beam search without the memory overhead, because the $N$ samples can be generated sequentially or in parallel without sharing KV cache state.

The performance advantage is significant. Generating 4 independent samples costs $4\times$ the compute but only $1\times$ the KV cache memory (processing sequentially) or $4\times$ (processing in parallel, but without the beam management overhead). Compare this to $B = 4$ beam search, which costs $4\times$ the KV cache memory and requires beam management.

Putting it all together: a performance summary

Let us conclude with a comprehensive comparison across all dimensions.

The story these charts tell is clear. Sampling strategies (greedy, temperature, top-k, top-p, constrained) all live in a narrow band of 1.0-1.03x overhead. They are, for all practical purposes, free beyond the model forward pass. Beam search starts at 1.2x and escalates rapidly, with both compute and memory costs scaling super-linearly for large beam widths due to batching inefficiency and memory pressure.

Conclusion

The decoding strategy you choose is a systems decision as much as a quality decision. Here are the key takeaways:

Sampling is almost always the right default. Top-p sampling with $T = 0.7$ and $p = 0.95$ is a good starting point for most tasks. The overhead is negligible, the memory footprint is minimal, and the output quality is good. Constrained decoding adds another 1-3% overhead to guarantee structured output.

Beam search is a specialized tool. It is justified for tasks where finding the single highest-probability sequence matters (machine translation, some summarization tasks) and where you can afford the 2-6x memory overhead and 1.5-3x latency increase. It is almost never justified for serving interactive applications.

The KV cache is the bottleneck, not compute. Beam search’s real cost is not the extra forward passes (which batch well) but the extra KV cache memory, which limits concurrency and destroys throughput. Shared-prefix optimization and paged attention reduce this by 30-60%, but the fundamental overhead remains.

Sample-and-rank is the modern alternative to beam search. Generating N independent samples and selecting the best one with a reranker achieves comparable or better quality than beam search while maintaining sampling’s memory efficiency.

The decoding strategy landscape continues to evolve. Min-p sampling, speculative decoding, and grammar-guided generation are all active areas of research. But the core performance tradeoff is unlikely to change: maintaining multiple hypotheses costs memory, and memory determines throughput. Choose accordingly.