Decoding
How it works
1. The model runs a forward pass and, for the current position, returns a logits vector of vocabulary size. 2. The logits are divided by temperature T and passed through a softmax, giving the next-token probability distribution. 3. The decoding strategy narrows and/or transforms the distribution: greedy takes the argmax; top-k keeps the k highest probabilities; top-p keeps the smallest set summing to ≥ p; beam search expands k hypotheses in parallel. 4. One token is selected from the prepared distribution — randomly (sampling) or deterministically (greedy/beam). 5. The token is appended to the sequence, the KV cache is updated, and it is fed back as model input. 6. Steps 1–5 repeat until an end-of-sequence (EOS) token or a length limit. Parameters such as temperature, top-k, top-p, repetition/presence penalty and the number of beams control the trade-off between coherence and diversity.
Problem solved
A trained language model only returns a probability distribution over the vocabulary, not finished text — something must decide which token to pick at each step. Naively taking the most probable token (greedy) yields text that is correct but repetitive and dull, while pure sampling from the full distribution is incoherent. Decoding solves this by providing a family of strategies that balance quality, diversity and determinism of generation without retraining the model, while also letting one control the cost and speed of generation.
Components
Turning the model's raw logits (after temperature scaling) into a probability distribution over the whole vocabulary — the input for every token-selection strategy.
Picking the highest-probability token (argmax) at each step. Deterministic and fast, but locally greedy, prone to repetition and globally suboptimal.
Official
Keeping the k best partial sequences (beams) by cumulative log-probability. Better for closed-ended tasks (translation, summarization); for open-ended text it tends to be bland and repetitive.
Official
Scaling logits by temperature T before softmax: T<1 sharpens the distribution (closer to greedy), T>1 flattens it (more randomness), T=0 is equivalent to greedy.
Official
Restricting the choice to the k most probable tokens, renormalizing their probabilities and sampling from that set. Cuts off the long tail of unlikely tokens.
Official
Choosing the smallest set of tokens whose cumulative probability is ≥ p and sampling from it. The set size adapts to the shape of the distribution — more options when the model is uncertain.
Official
Implementation
Using beam search for open-ended generation gives bland, repetitive output (degeneration); top-p sampling is better for chat/creative writing.
Too high a temperature leads to incoherence and hallucination, too low to repetition and rigidity.
Without a repetition penalty the model falls into repetition loops, especially at low temperature.
The order in which temperature, top-k and top-p are applied, and how they combine, affects the result; libraries differ.
Evolution
Beam search becomes the default decoding strategy in neural machine translation and other seq2seq tasks.
Fan et al. (Hierarchical Neural Story Generation) popularize top-k sampling as a way to get livelier, less repetitive generation.
Holtzman et al. (The Curious Case of Neural Text Degeneration) show that beam search and greedy lead to text degeneration, and introduce nucleus (top-p) sampling as a better strategy for open-ended text.
Leviathan et al. and Chen et al. introduce speculative decoding: a small draft model proposes tokens and the target model verifies them — a speedup without changing the output distribution.
Advances in speculative methods (EAGLE-3) and grammar/JSON-guided decoding make faster and structurally valid generation mainstream.
Hyperparameters (configurable axes)
Scale of the logits before softmax; controls randomness. Lower = more deterministic, higher = more creative.
Cumulative-probability threshold for the sampling nucleus; 1.0 disables truncation.
Number of most-probable tokens considered; 0 disables truncation.
Number of hypotheses expanded in parallel in beam search; 1 = greedy.
Lowers the probability of already-generated tokens, reducing repetition loops.
Computational complexity
Time complexity: O(V) na krok (dobór tokenu) + O(k·V) dla beam search. Space complexity: O(V) na rozkład; O(k·L) dla hipotez beam search.
Compute bottleneck
The decoding step time is dominated by the model forward pass (reading weights and the KV cache from memory), not by token selection — so decoding inherits the memory-bound nature of the decode phase.
Execution paradigm
Decoding is a token-selection layer on top of a dense autoregressive model pass.
Decoding introduces no conditional routing — it operates on the output of a dense forward pass (unless the base model is MoE).
Parallelism
Tokens are produced sequentially (each depends on the previous). Parallelism comes across requests (batching) and across beam-search hypotheses, not within a single sequence. Speculative decoding partly breaks this sequentiality.
Hardware requirements
Generation is dominated by the memory-bound model forward pass; GPUs with high memory bandwidth (HBM) set tokens per second. Token selection itself is computationally trivial.
The decoding-strategy logic (argmax, top-k, top-p, beam) is lightweight and portable; its cost is negligible relative to the model pass on any hardware.