CMU Advanced NLP Spring 2026 (9): Decoding Algorithms

Introduction and Decoding Basics00:00:00

The lecture introduces decoding algorithms as methods for generating text from language models. The instructor recaps previous course topics on modeling, parameterization, and learning, and sets the stage for focusing on inference. The auto-regressive formulation of language models is reviewed, breaking sequence generation into conditional distributions over next tokens given previous context.

Decoding as Optimization00:07:04

Decoding is framed as an optimization problem where the goal is to find the sequence that maximizes the model's probability (maximum a posteriori). Greedy decoding is introduced as a simple local approach that picks the highest probability token at each step, but it is shown to be suboptimal because locally optimal choices can lead to lower overall sequence probabilities.

Beam Search00:12:30

Beam search is presented as an improvement over greedy decoding by maintaining multiple candidate paths (beams) rather than just one. Beam size one is equivalent to greedy decoding, while an infinite beam size would solve the optimization exactly but is computationally infeasible. Practical beam sizes typically range from 8 to 32. The lecture notes that beam search was common pre-LLM but is less used now, and discusses issues like repetition loops and assigning high probability to empty sequences.

Decoding as Sampling00:30:12

The lecture transitions to decoding as sampling, where the goal is to draw samples from the model's distribution rather than find the mode. Ancestral sampling is explained as drawing a token from the distribution at each step. Problems with naive sampling are discussed, including heavy tails and compounding errors where small probabilities of sampling bad tokens accumulate over long sequences.

Truncation and Temperature Sampling00:39:24

Techniques to address sampling issues are covered, including top-k sampling (keeping only the top k tokens) and top-p sampling (keeping tokens until cumulative probability exceeds p). Temperature sampling is explained as rescaling logits to sharpen (temperature < 1) or spread out (temperature > 1) the distribution, with temperature approaching zero being equivalent to greedy decoding.

Efficient Inference and Key-Value Caching00:49:01

The lecture covers efficient inference, starting with key-value caching for transformers. Since keys and values from previous tokens remain constant during auto-regressive generation, caching them avoids recomputation and reduces complexity from quadratic to linear with respect to sequence length. Empirical results show significant latency improvements with caching.

Compute vs Memory Bound and Advanced Speedups00:57:02

Sources of slowdown are categorized as compute-bound (floating point operations) and memory-bound (data transfer latency). The lecture surveys techniques to speed up inference including quantization, group-query attention, FlashAttention, custom kernels, mixture of experts, and non-auto-regressive models. Speculative decoding is introduced as a method using a small draft model to propose tokens that a large model verifies in parallel.

Batching and Conclusion01:14:10

The final section discusses speeding up inference at a higher level through batching and shared state caching, such as reusing KV caches across multiple generations with shared prefixes. Inference libraries like vLLM and SGLANG are mentioned. The lecture concludes by summarizing the progression from basic decoding algorithms to efficient inference techniques.