Elamur Research⌕
☰
home / papers / 2022 / Truncation Sampling as Language Model Desmoothing

Truncation Sampling as Language Model Desmoothing

Paper · 2022 · John Hewitt, Christopher Manning and Percy Liang

Summary

Sampling directly from neural language models often yields long texts that drift into nonsense. Truncation methods such as top-k and top-p help by zeroing out unlikely tokens, but it has been unclear what they are actually trying to achieve. The authors treat any neural LM as a blend of the true distribution with a near-uniform smoothing component. The smoothing exists because KL-divergence training heavily penalizes giving near-zero probability to observed words. Under this view, truncation is desmoothing: trying to recover the support of the true distribution.

From this model they derive two principles. Likely words should never be removed. When every candidate is unlikely, only words that are improbable relative to the others should be cut. Top-p violates the first principle. The authors therefore propose η-sampling, which drops a token only when its probability falls below both a fixed threshold and an entropy-dependent threshold.

They compare η-sampling with top-p, typical decoding and ϵ-sampling, tuning each method with MAUVE. η-sampling produces long English documents that humans rate as more plausible and escapes repetition more easily. It also behaves more sensibly on a diagnostic set of distributions, which matters for anyone relying on default decoding settings.

Key points

  • Motivating example: a 5-gram model smoothed with the uniform distribution degenerates into gibberish once it samples a token outside the support of the 5-gram model.
  • Over-truncation by top-p: GPT-2 large gives "Trump" probability 0.96 after "Donald", so top-p = 0.95 keeps only that one continuation. η-sampling keeps several.
  • Diagnostic battery: in CheckList-style tests, top-p and typical decoding over-truncate low-entropy distributions. ϵ-sampling, which uses only an absolute threshold, wrongly allows fewer words in high-entropy contexts such as "The…".
  • Tuning: each method's hyperparameter was set by maximizing MAUVE, for example typical 0.92 and top-p 0.95 for GPT-2 large.
  • Code and limitations: code is released at github.com/john-hewitt/truncation-sampling. Experiments cover English LMs only, and the authors note that morphologically rich languages may behave differently.

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

🎓Stanford UniversityStanford · United States310 works · 284,480 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 1,343 works

Cite

Cite as John Hewitt, Christopher Manning and Percy Liang. 2022. Truncation Sampling as Language Model Desmoothing. Findings of the Association for Computational Linguistics: EMNLP 2022.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2022.findings-emnlp.249

@inproceedings{hewitt2022truncation,
  title = {{Truncation Sampling as Language Model Desmoothing}},
  author = {John Hewitt, Christopher Manning and Percy Liang},
  booktitle = {Findings of the Association for Computational Linguistics: EMNLP 2022},
  year = {2022},
  doi = {10.18653/v1/2022.findings-emnlp.249},
  url = {https://doi.org/10.18653/v1/2022.findings-emnlp.249}
}

References

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

  1. Sourya Basu, Govardana Sachitanandam Ramachandran, Nitish Shirish Keskar, and Lav R. Varshney. 2021. MIROSTAT: A neural text decoding algorithm that directly controls perplexity. In International Conference on Learning Representations. find
  2. Christopher M Bishop. 2006. Pattern recognition and machine learning. Springer. find
  3. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901.
  4. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022. PaLM: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311.
  5. Kenneth W Church and William A Gale. 1991. A comparison of the enhanced Good-Turing and deleted estimation methods for estimating probabilities of English bigrams. Computer Speech & Language, 5(1):19–54. find
  6. Jwala Dhamala, Varun Kumar, Rahul Gupta, Kai-Wei Chang, and Aram Galstyan. 2022. An analysis of the effects of decoding algorithms on fairness in open-ended language generation. In 2018 IEEE Spoken Language Technology Workshop (SLT). IEEE. find
  7. Angela Fan, Yacine Jernite, Ethan Perez, David Grangier, Jason Weston, and Michael Auli. 2019. ELI5: long form question answering. In Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers, pages…
  8. 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 (Volume 1: Long Papers), pages 889–898, Melbourne, Australia. Association for Computational Linguistics. find
  9. Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. 2021. The Pile: An 800gb dataset of diverse text for language modeling. CoRR, abs/2101.00027. find
  10. Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. Advances in neural information processing systems, 27. find
  11. Tatsunori B Hashimoto, Hugh Zhang, and Percy Liang. 2019. Unifying human and statistical evaluation for natural language generation. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and S… find
  12. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration. In International Conference on Learning Representations. find
  13. Daphne Ippolito, Daniel Duckworth, Chris Callison-Burch, and Douglas Eck. 2020. Automatic detection of generated text is easiest when humans are fooled. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1808–1822, Online. Association for Computational…
  14. Daniel Jurafsky and James H. Martin. 2000. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, 1st edition. Prentice Hall PTR, USA. find
  15. Daniel Kang and Tatsunori B. Hashimoto. 2020. Improved natural language generation via loss truncation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 718–731, Online. Association for Computational Linguistics.
  16. S. Katz. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(3):400–401. find
  17. Wouter Kool, Herke Van Hoof, and Max Welling. 2019. Stochastic beams and where to find them: The Gumbel-top-k trick for sampling sequences without replacement. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3499–3… find
  18. Yang Liu and Mirella Lapata. 2019. Text summarization with pretrained encoders. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3730–3740, Hong Kong, China. Assoc… find
  19. Andre Martins and Ramon Astudillo. 2016. From softmax to sparsemax: A sparse model of attention and multi-label classification. In International conference on machine learning, pages 1614–1623. PMLR. find
  20. Clara Meister, Afra Amini, Tim Vieira, and Ryan Cotterell. 2021a. Conditional Poisson stochastic beams. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 664– 681, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics. find
  21. Clara Meister and Ryan Cotterell. 2021. Language model evaluation beyond perplexity. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 5328–5339, Online.… find
  22. Clara Meister, Tiago Pimentel, Patrick Haller, Lena Jäger, Ryan Cotterell, and Roger Levy. 2021b. Revisiting the Uniform Information Density hypothesis. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 963– 980, Online and Punta Cana, Dominican Republi…
  23. Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. 2022a. Typical decoding for natural language generation. CoRR, abs/2202.00666. — [arXiv:2202.00666](https://arxiv.org/abs/2202.00666) find
  24. Clara Meister, Gian Wiher, Tiago Pimentel, and Ryan Cotterell. 2022b. On the probability–quality paradox in language generation. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 36–45, Dublin, Ireland. Association for Computat… find
  25. Mehryar Mohri and Brian Roark. 2006. Probabilistic context-free grammar induction based on structural zeros. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 312–319, New York City, USA. Association for Computational Linguistics. find
  26. Moin Nadeem, Tianxing He, Kyunghyun Cho, and James Glass. 2020. A systematic characterization of sampling algorithms for open-ended language generation. In Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint… find
  27. Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan Lu, and Benjamin Van Roy. 2022. Epistemic neural networks. arXiv preprint arXiv:2107.08924. — [arXiv:2107.08924](https://arxiv.org/abs/2107.08924) find
  28. Ben Peters, Vlad Niculae, and André FT Martins. 2019. Sparse sequence-to-sequence models. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1504–1519. find
  29. 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. In Advances in Neural Information Processing Systems, volume 34, pages 4816–4828. Curran As…
  30. 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
  31. Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. 2020. Beyond accuracy: Behavioral testing of NLP models with CheckList. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4902– 4912, Online. Association for Computational Linguisti… find
  32. Maxat Tezekbayev, Vassilina Nikoulina, Matthias Gallé, and Zhenisbek Assylbekov. 2021. Speeding up entmax. CoRR, abs/2111.06832. find
  33. Jason Wei, Clara Meister, and Ryan Cotterell. 2021. A cognitive regularizer for language modeling. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 5191… find
  34. Sean Welleck, Ilia Kulikov, Jaedeok Kim, Richard Yuanzhe Pang, and Kyunghyun Cho. 2020. Consistency of a recurrent language model with respect to incomplete decoding. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 5553–5568. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/hewitt-2022-truncation-sampling-as-language-model/