# A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2020.

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

- [SSD-LM: Semi-autoregressive Simplex-based Diffusion Language Model for Text Generation and Modular Control](https://mlsanity.com/paper/2210.17432/) (2022)
- [Truncation Sampling as Language Model Desmoothing](https://mlsanity.com/paper/2210.15191/) (2022)
- [Locally Typical Sampling](https://mlsanity.com/paper/2202.00666/) (2022)
- [On Decoding Strategies for Neural Text Generators](https://mlsanity.com/paper/2203.15721/) (2022)
- [Cost-Effective Hyperparameter Optimization for Large Language Model Generation Inference](https://mlsanity.com/paper/2303.04673/) (2023)
- [Unified Detoxifying and Debiasing in Language Generation via Inference-time Adaptive Optimization](https://mlsanity.com/paper/2210.04492/) (2022)
- [Stumbling Blocks: Stress Testing the Robustness of Machine-Generated Text Detectors Under Attacks](https://mlsanity.com/paper/2402.11638/) (2024)
- [On the Efficacy of Sampling Adapters](https://mlsanity.com/paper/2307.03749/) (2023)
- [Measuring Uncertainty in Translation Quality Evaluation (TQE)](https://mlsanity.com/paper/2111.07699/) (2021)
- [Diffusion Models in NLP: A Survey](https://mlsanity.com/paper/2303.07576/) (2023)
- [A Survey of Diffusion Models in Natural Language Processing](https://mlsanity.com/paper/2305.14671/) (2023)
- [Look-back Decoding for Open-Ended Text Generation](https://mlsanity.com/paper/2305.13477/) (2023)
- [Growing a Tail: Increasing Output Diversity in Large Language Models](https://mlsanity.com/paper/2411.02989/) (2024)
- [LLM Fingerprinting via Semantically Conditioned Watermarks](https://mlsanity.com/paper/2505.16723/) (2025)
- [DoubleGen: Debiased Generative Modeling of Counterfactuals](https://mlsanity.com/paper/2509.16842/) (2025)
- [An Analysis of the Effects of Decoding Algorithms on Fairness in Open-Ended Language Generation](https://mlsanity.com/paper/2210.03826/) (2022)
- [Do DALL-E and Flamingo Understand Each Other?](https://mlsanity.com/paper/2212.12249/) (2022)
- [Lingxi: A Diversity-aware Chinese Modern Poetry Generation System](https://mlsanity.com/paper/2108.12108/) (2021)
- [Local Normalization Distortion and the Thermodynamic Formalism of Decoding Strategies for Large Language Models](https://mlsanity.com/paper/2503.21929/) (2025)
- [Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs](https://mlsanity.com/paper/2506.05387/) (2025)
- [A Continuum of Generation Tasks for Investigating Length Bias and Degenerate Repetition](https://mlsanity.com/paper/2210.10817/) (2022)
- [How do decoding algorithms distribute information in dialogue responses?](https://mlsanity.com/paper/2303.17006/) (2023)
- [Your Pretrained Model Tells the Difficulty Itself: A Self-Adaptive Curriculum Learning Paradigm for Natural Language Understanding](https://mlsanity.com/paper/2507.09758/) (2025)
- [Language Model Evaluation in Open-ended Text Generation](https://mlsanity.com/paper/2108.03578/) (2021)
- [LatticeGen: A Cooperative Framework which Hides Generated Text in a Lattice for Privacy-Aware Generation on Cloud](https://mlsanity.com/paper/2309.17157/) (2023)
- [Are You Sure You're Sure? On the Impact of Instruction Tuning on Confidence and Lexical Diversity](https://mlsanity.com/paper/2608.13430/) (2026)
- [Expert-Space Exploration in MoE Reinforcement Learning](https://mlsanity.com/paper/2609.13058/) (2026)
- [Composable Decoding on the Probability Simplex: Theory and Implementation](https://mlsanity.com/paper/2609.34992/) (2026)

## Abstract (arXiv)

This work studies the widely adopted ancestral sampling algorithms for auto-regressive language models, which is not widely studied in the literature. We use the quality-diversity (Q-D) trade-off to investigate three popular sampling algorithms (top-k, nucleus and tempered sampling). We focus on the task of open-ended language generation. We first show that the existing sampling algorithms have similar performance. After carefully inspecting the transformations defined by different sampling algorithms, we identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. To validate the importance of the identified properties, we design two sets of new sampling algorithms: one set in which each algorithm satisfies all three properties, and one set in which each algorithm violates at least one of the properties. We compare their performance with existing sampling algorithms, and find that violating the identified properties could lead to drastic performance degradation, as measured by the Q-D trade-off. On the other hand, we find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms. Our data and code are available at https://github.com/moinnadeem/characterizing-sampling-algorithms