Greedy vs Sampling vs Beam Search: Decoding Cost from a Serving Perspective

If you've ever noticed TPS jump noticeably after setting temperature to 0 — same model, same input — your instinct is right. Writing it off as "greedy is obviously faster" only captures half the picture. Looking at which operations are eliminated, how that gap amplifies with larger batch sizes, and why beam search is a categorically different problem at the GPU kernel level reveals that decoding parameters are not just output-quality knobs — they are cost variables that directly determine serving economics.

Where logit processing sits in the decode step

Breaking down a single token-generation step in autoregressive decoding:

1. Forward pass — attention + FFN end-to-end. Matrix operations on the order of batch × seq_len × hidden_dim. This dominates step latency.
2. lm_head projection — hidden state → logit vector. Shape: [batch_size, vocab_size]
3. Logit processing — temperature scaling, top-k/top-p filtering, sampling
4. Embedding lookup — selected token_id → input for the next step

Because the forward pass dominates, logit processing looks cheap. The catch is that its cost scales with batch_size × vocab_size. Llama-3's vocab size is 128,256. At batch=32, the logit tensor is 32 × 128,256 ≈ 4.1M elements — 8 MB in fp16. What you do with that tensor determines the additional cost of each decode step.

The actual compute cost of greedy decoding

Greedy decoding reduces to torch.argmax(logits, dim=-1): a single linear scan over the full vocabulary — O(V) reduction.

The A100's HBM2e memory bandwidth is roughly 2 TB/s. The bandwidth consumed just reading the logit tensor at batch=32, for various vocab sizes:

A few microseconds sounds negligible, but this operation runs 1,000 times when generating 1,000 tokens. And argmax reduction requires collecting partial reductions across warps, so actual kernel time exceeds a simple sequential read. Treating greedy argmax as "zero compute cost" on models with vocab sizes above 128K is a mistake.

The real cost of top-p sampling is the sort

The processing sequence for top-p (nucleus) sampling:

logits / temperature          # element-wise, O(V)
softmax(logits)               # O(V)
torch.sort(probs, descending) # O(V log V) ← bottleneck
torch.cumsum(sorted_probs)    # O(V)
mask where cumsum > top_p     # O(V)
torch.multinomial(probs)      # O(k), k = nucleus size

This maps directly to HuggingFace Transformers' TopPLogitsWarper:

sorted_logits, sorted_indices = torch.sort(scores, descending=False)
cumulative_probs = sorted_logits.softmax(dim=-1).cumsum(dim=-1)
sorted_indices_to_remove = cumulative_probs <= (1 - self.top_p)
sorted_indices_to_remove[..., -self.min_tokens_to_keep:] = 0
indices_to_remove = sorted_indices_to_remove.scatter(
    1, sorted_indices, sorted_indices_to_remove
)
scores_processed = scores.masked_fill(indices_to_remove, self.filter_value)

The temperature division, softmax, cumsum, and masking are all O(V) linear passes. Only the sort is O(V log V). At V=128,256, log₂V ≈ 17, so the sort alone performs more comparisons than all other steps combined. This is why sorting dominates compute cost across cumulative decoding methods that include nucleus sampling.

Applying top-k first changes the picture entirely. Filter to top-k=50 candidates before applying top-p, and the sort operates over 50 elements instead of 128,256. The comparison count drops from O(128,256 × 17) ≈ 2.18M to O(50 × 6) ≈ 300. Generation quality is barely affected, while the dominant cost of the sampling path nearly disappears.

Extra cost from heterogeneous parameters within a batch

In a continuous batching environment where request A has temperature=0.8, top-p=0.9 and request B has temperature=0 (greedy), the two requests cannot share a single sampling kernel. vLLM's sampler inspects SamplingParams and routes greedy and random sampling through separate code paths. The more heterogeneous the parameters across a batch, the more kernel launches branch out and the lower the GPU stream utilization.

The operational decision to standardize decoding parameters across a batch inference API — fixing temperature=0, or enforcing a uniform top-k/top-p across all requests — has a direct impact on throughput. What looks like a minor configuration detail produces measurable differences at the serving layer.

Why beam search has been structurally pushed out of production serving

With beam width B, a single request must maintain B independent sequences simultaneously. KV cache usage grows by a factor of B.

For Llama-3 8B (layers=32, heads=8, head_dim=128, fp16):

KV cache for one sequence (seq_len=512)
= 2 (K+V) × 32 (layers) × 512 (seq_len) × 8 (heads) × 128 (head_dim) × 2 (fp16)
= 67,108,864 bytes = 64 MB

KV cache is 4× larger for the same batch. Even on an 80 GB A100, subtract model weights (~16 GB) and activations, and the KV cache budget is constrained. A single beam=4 batch displaces four greedy batches.

The more fundamental problem is the conflict with continuous batching. Continuous batching recycles a slot the moment a sequence finishes, filling it with a new request. With beam search, all B beams must complete before the slot is released. Dynamic slot recycling becomes impossible, and throughput degrades structurally.

The vLLM team has documented this conflict explicitly. GitHub Issue #8306 states that "beam search is a search algorithm while the rest of vLLM is a sampling algorithm, and they are fundamentally at odds" — beam search is explicitly blocked in speculative decoding and multi-step decoding, and is currently being migrated to a separate interface (LLM.beam_search) decoupled from the vLLM core.

Choosing a decoding strategy by serving SLA

For throughput-oriented batch inference, temperature=0 greedy is the right choice. It has the lowest computational complexity, and every request in the batch follows the same kernel path. The ~195 tok/s figure for Llama-3 8B on an A100 with batch=8 in vLLM assumes greedy or simple sampling.

For interactive services that require diversity, use top-k=50 combined with top-p=0.9. Sort cost is dramatically lower than top-p alone, and standardizing parameters across the batch eliminates kernel branching.

Beam search does not belong in a real-time serving path. It is only viable for offline evaluation or single-request high-quality generation. Given the 4× KV cache expansion and the slot inefficiency it introduces against continuous batching, there is no reason to use it within a production serving SLA.