# Foundations of Top-k Decoding For Language Models

arXiv: https://arxiv.org/abs/2505.19371 · HTML: https://mlsanity.com/paper/2505.19371/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 65 references that are in the map.
- First posted on arXiv 25 May 2025.

## Builds on (most cited first, 28 of 28)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Adaptively Sparse Transformers](https://mlsanity.com/paper/1909.00015/) (2019)
- [Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs](https://mlsanity.com/paper/2407.01082/) (2024)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Truncation Sampling as Language Model Desmoothing](https://mlsanity.com/paper/2210.15191/) (2022)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Locally Typical Sampling](https://mlsanity.com/paper/2202.00666/) (2022)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Noisy Natural Gradient as Variational Inference](https://mlsanity.com/paper/1712.02390/) (2017)
- [An elementary introduction to information geometry](https://mlsanity.com/paper/1808.08271/) (2018)
- [Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application](https://mlsanity.com/paper/1309.1541/) (2013)
- [Explicit Sparse Transformer: Concentrated Attention Through Explicit Selection](https://mlsanity.com/paper/1912.11637/) (2019)
- [Closing the Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/2310.01693/) (2023)
- [Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives](https://mlsanity.com/paper/2001.06471/) (2020)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Uncertainty Estimates of Predictions via a General Bias-Variance Decomposition](https://mlsanity.com/paper/2210.12256/) (2022)
- [L0Learn: A Scalable Package for Sparse Learning using L0 Regularization](https://mlsanity.com/paper/2202.04820/) (2022)
- [Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies](https://mlsanity.com/paper/2410.03968/) (2024)
- [Analysis of Generalized Bregman Surrogate Algorithms for Nonsmooth Nonconvex Statistical Learning](https://mlsanity.com/paper/2112.09191/) (2021)
- [Re-examination of Bregman functions and new properties of their divergences](https://mlsanity.com/paper/1803.00641/) (2018)
- [Best-Subset Selection in Generalized Linear Models: A Fast and Consistent Algorithm via Splicing Technique](https://mlsanity.com/paper/2308.00251/) (2023)
- [Exact continuous relaxations of l0-regularized criteria with non-quadratic data terms](https://mlsanity.com/paper/2402.06483/) (2024)
- [Learning Sparse Distributions using Iterative Hard Thresholding](https://mlsanity.com/paper/1910.13389/) (2019)
- [Efficient sparse probability measures recovery via Bregman gradient](https://mlsanity.com/paper/2403.02861/) (2024)

## Built on by (most cited first, 10 of 10)

- [Statistical Methods in Generative AI](https://mlsanity.com/paper/2509.07054/) (2025)
- [A Practical Investigation of Training-free Relaxed Speculative Decoding](https://mlsanity.com/paper/2607.08690/) (2026)
- [Decoding as Optimisation on the Probability Simplex: From Top-K to Top-P (Nucleus) to Best-of-K Samplers](https://mlsanity.com/paper/2602.18292/) (2026)
- [Conformal Sparsification for Bandwidth-Efficient Edge-Cloud Speculative Decoding](https://mlsanity.com/paper/2510.09942/) (2025)
- [Relative-Based Scaling Law for Neural Language Models](https://mlsanity.com/paper/2510.20387/) (2025)
- [Towards Reproducibility in Predictive Process Mining: SPICE -- A Deep Learning Library](https://mlsanity.com/paper/2512.16715/) (2025)
- [On Temperature-Constrained Non-Deterministic Machine Translation: Potential and Evaluation](https://mlsanity.com/paper/2601.13729/) (2026)
- [Entropy-Guided k-Guard Sampling for Long-Horizon Autoregressive Video Generation](https://mlsanity.com/paper/2601.19488/) (2026)
- [Entropy-informed Decoding: Adaptive Information-Driven Branching](https://mlsanity.com/paper/2605.09745/) (2026)
- [Composable Decoding on the Probability Simplex: Theory and Implementation](https://mlsanity.com/paper/2609.34992/) (2026)

## Abstract (arXiv)

Top-k decoding is a widely used method for sampling from LLMs: at each token, only the largest k next-token-probabilities are kept, and the next token is sampled after re-normalizing them to sum to unity. Top-k and other sampling methods are motivated by the intuition that true next-token distributions are sparse, and the noisy LLM probabilities need to be truncated. However, to our knowledge, a precise theoretical motivation for the use of top-k decoding is missing. In this work, we develop a theoretical framework that both explains and generalizes top-k decoding. We view decoding at a fixed token as the recovery of a sparse probability distribution. We consider Bregman decoders obtained by minimizing a separable Bregman divergence (for both the primal and dual cases) with a sparsity-inducing ℓ0 regularization. Despite the combinatorial nature of the objective, we show how to optimize it efficiently for a large class of divergences. We show that the optimal decoding strategies are greedy, and further that the loss function is discretely convex in k, so that binary search provably and efficiently finds the optimal k. We show that top-k decoding arises as a special case for the KL divergence, and identify new decoding strategies that have distinct behaviors (e.g., non-linearly up-weighting larger probabilities after re-normalization).