Elamur Research⌕
☰
home / papers / 2025 / Balancing Diversity and Risk in LLM Sampling: How to Select Your Method and Parameter for Open-Ended Text Generation

Balancing Diversity and Risk in LLM Sampling: How to Select Your Method and Parameter for Open-Ended Text Generation

Paper · 2025 · Yuxuan Zhou, Margret Keuper and Mario Fritz

Summary

Truncation sampling methods for LLM decoding are usually compared on open-ended generation benchmarks. Those comparisons are fragile for two reasons. First, outcomes depend heavily on hand-tuned parameters, which are typically swept over a coarse grid. Second, the reference texts are limited. The authors propose an intrinsic, tuning-independent evaluation built on a Context-Preserving Trie (CP-Trie). This is a word-level prefix tree built from English Wikipedia using only sentence-initial n-grams, so each node keeps the full sentence context. For each prefix, a method's allowed token set is checked against the data support recorded in the trie, yielding per-step Recall (diversity) and Risk (tokens outside the support). Methods are then compared at matched average Risk using Average Recall and Risk Standard Error (stability). The benchmark ranks Top-k, Top-p, Mirostat, η-sampling and Adaptive Decoding and maps out their useful parameter ranges. These scores correlate strongly with TruthfulQA accuracy. A re-run of an earlier study shows that sampling methods had been undervalued, which gives practitioners a principled way to choose a method and its parameters.

Key points

  • CP-Trie design: Plain n-gram tries overestimate how many next tokens are plausible after a prefix. Using only sentence-starting n-grams avoids this. Optimal truncation sizes for gpt2-xl vary widely across prefixes, so Top-k serves as a zero-adaptability baseline.
  • Correlation with TruthfulQA: At average Risk 1, 5 and 15:
    • Risk Standard Error correlates with accuracy at −0.87, −0.92 and −0.94.
    • Mean recall correlates at 0.83, 0.83 and 0.50.
  • Re-examination of Shi et al. (2024a) with Llama-2-7B:
    • On MBPP, greedy decoding still wins (24.00 Pass@1).
    • On HumanEval, every sampling method beats greedy (2.44).
    • On GSM8K, Top-p (14.13) and η-sampling (13.72) beat greedy (13.19) at average Risk 1.
  • Mirostat on code and math: Mirostat performs poorly on these tasks, plausibly because it relies on Zipf-law assumptions about natural language.
  • Limitations: The data is English-only. Locally Typical Sampling and Min-P are not yet evaluated. The code and benchmark are public.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of MannheimMannheim · Germany29 works · 8,347 citations🔬Max Planck Institute for InformaticsSaarbrücken · Germany16 works · 4,453 citations🔬Helmholtz Center for Information SecuritySaarbrücken · Germany14 works · 1,172 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,320 worksText generation · 202 works

Cite

Cite as Yuxuan Zhou, Margret Keuper and Mario Fritz. 2025. Balancing Diversity and Risk in LLM Sampling: How to Select Your Method and Parameter for Open-Ended Text Generation. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2025.acl-long.1278

@inproceedings{zhou2025balancing,
  title = {{Balancing Diversity and Risk in LLM Sampling: How to Select Your Method and Parameter for Open-Ended Text Generation}},
  author = {Yuxuan Zhou, Margret Keuper and Mario Fritz},
  booktitle = {Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2025},
  doi = {10.18653/v1/2025.acl-long.1278},
  url = {https://doi.org/10.18653/v1/2025.acl-long.1278}
}

References

42 references, 22 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774.
  2. Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. 2021. Program synthesis with large language models. arXiv preprint arXiv:2108.07732.
  3. Sourya Basu, Govardana Sachitanandam Ramachandran, Nitish Shirish Keskar, and Lav R Varshney. 2021. Mirostat: A neural text decoding algorithm that directly controls perplexity. International Conference on Learning Representations (ICLR). find
  4. Yoshua Bengio, Réjean Ducharme, and Pascal Vincent. 2000. A neural probabilistic language model. Advances in Neural Information Processing Systems (NeurIPS)), 13. find
  5. Yung-Sung Chuang, Yujia Xie, Hongyin Luo, Yoon Kim, James Glass, and Pengcheng He. 2023. Dola: Decoding by contrasting layers improves factuality in large language models. The Twelfth International Conference on Learning Representations (ICLR).
  6. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. 2021. Training verifiers to solve math word problems. URL https://arxiv.org/abs/2110.14168. ↗
  7. Hantian Ding, Zijian Wang, Giovanni Paolini, Varun Kumar, Anoop Deoras, Dan Roth, and Stefano Soatto. 2024. Fewer truncations improve language modeling. International Conference on Machine Learning (ICML). find
  8. Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. 2024. The llama 3 herd of models. arXiv preprint arXiv:2407.21783.
  9. Angela Fan, Mike Lewis, and Yann Dauphin. 2018. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics.
  10. Matthew Finlayson, John Hewitt, Alexander Koller, Swabha Swayamdipta, and Ashish Sabharwal. 2024. Closing the curious case of neural text degeneration. International Conference on Learning Representations (ICLR). find
  11. Edward Fredkin. 1960. Trie memory. Communications of the ACM, 3(9):490–499. find
  12. Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021. Simcse: Simple contrastive learning of sentence embeddings. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing.
  13. Chavoosh Ghasemi, Hamed Yousefi, Kang G Shin, and Beichuan Zhang. 2019. On the granularity of trie-based data structures for name lookups and updates. IEEE/ACM Transactions on Networking, 27(2):777– 789. find
  14. John Hewitt, Christopher D Manning, and Percy Liang. 2022. Truncation sampling as language model desmoothing. Findings of the Association for Computational Linguistics: EMNLP.
  15. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration. The curious case of neural text degeneration.
  16. Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. 2023. Mistral 7b. arXiv preprint arXiv:2310.06825. find
  17. Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al. 2024. Mixtral of experts. arXiv preprint arXiv:2401.04088. find
  18. Dan Jurafsky. 2000. Speech & language processing. Pearson Education India. find
  19. Bofang Li, Zhe Zhao, Tao Liu, Puwei Wang, and Xiaoyong Du. 2016. Weighted neural bag-of-n-grams model: New baselines for text classification. In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 1591–1600. find
  20. Stephanie Lin, Jacob Hilton, and Owain Evans. 2021. Truthfulqa: Measuring how models mimic human falsehoods. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics.
  21. Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. 2023. Locally typical sampling. Transactions of the Association for Computational Linguistics, 11:102–121.
  22. Clara Meister, Gian Wiher, Tiago Pimentel, and Ryan Cotterell. 2022. On the probability-quality paradox in language generation. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics. find
  23. Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. 2017. Pointer sentinel mixture models. International Conference on Learning Representations (ICLR).
  24. Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017. Automatic differentiation in pytorch. find
  25. Krishna Pillutla, Swabha Swayamdipta, Rowan Zellers, John Thickstun, Sean Welleck, Yejin Choi, and Zaid Harchaoui. 2021. Mauve: Measuring the gap between neural text and human text using divergence frontiers. Advances in Neural Information Processing Systems (NeurIPS), 34:4816–4828.
  26. Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. 2018. Improving language understanding by generative pre-training. find
  27. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9. find
  28. Ehsan Shareghi, Daniela Gerz, Ivan Vulic, et al. 2019. Show some love to your n-grams: A bit of progress and stronger n-gram language modeling baselines. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. find
  29. Chufan Shi, Haoran Yang, Deng Cai, Zhisong Zhang, Yifan Wang, Yujiu Yang, and Wai Lam. 2024a. A thorough examination of decoding methods in the era of llms. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing.
  30. Weijia Shi, Xiaochuang Han, Mike Lewis, Yulia Tsvetkov, Luke Zettlemoyer, and Scott Wen-tau Yih. 2024b. Trusting your evidence: Hallucinate less with context-aware decoding. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human La…
  31. Ramesh Nallapati, Bowen Zhou, Caglar Gulcehre, Bing Xiang, et al. 2016. Abstractive text summarization using sequence-to-sequence rnns and beyond. In Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning.
  32. Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. 2023. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805.
  33. Yatin Nandwani, Vineet Kumar, Dinesh Raghu, Sachindra Joshi, and Luis A Lastras. 2023. Pointwise mutual information based metric and decoding strategy for faithful generation in document grounded dialogs. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. find
  34. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288.
  35. Minh Nguyen, Andrew Baker, Clement Neo, Allen Roush, Andreas Kirsch, and Ravid Shwartz-Ziv. 2024. Turning up the heat: Min-p sampling for creative and coherent llm outputs. arXiv preprint arXiv:2407.01082. — [arXiv:2407.01082](https://arxiv.org/abs/2407.01082) find
  36. X Wang, J Wei, D Schuurmans, Q Le, E Chi, S Narang, A Chowdhery, and D Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. International Conference on Learning Representations (ICLR).
  37. Sean O’Brien and Mike Lewis. 2023. Contrastive decoding improves reasoning in large language models. arXiv preprint arXiv:2309.09117.
  38. Xuezhi Wang and Denny Zhou. 2024. Chain-of-thought reasoning without prompting. Advances in Neural Information Processing Systems (NeurIPS). find
  39. Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. 2020. Neural text generation with unlikelihood training. International Conference on Learning Representations (ICLR).
  40. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pier-ric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2020. Huggingface’s transformers: State-ofthe-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natur… find
  41. Wenhong Zhu, Hongkun Hao, Zhiwei He, Yiming Ai, and Rui Wang. 2024. Improving open-ended text generation via adaptive decoding. International Conference on Machine Learning (ICML). find
  42. Yaoming Zhu, Sidi Lu, Lei Zheng, Jiaxian Guo, Weinan Zhang, Jun Wang, and Yong Yu. 2018. Texygen: A benchmarking platform for text generation models. In The 41st international ACM SIGIR conference on research & development in information retrieval, pages 1097–1100.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhou-2025-balancing-diversity-risk-llm-sampling/