Elamur Research⌕
☰
home / papers / 2023 / Locally Typical Sampling

Locally Typical Sampling

Summary

Neural language models assign high likelihood to held-out text, yet the text they generate often reads poorly. Maximization-based decoding tends toward dull or degenerate output, and ordinary sampling can drift into nonsense. Meister et al. argue that this gap comes from the decision rule used for generation, not from flawed models. They treat generation as a discrete stochastic process, which lets them analyse it with information theory. Drawing on psycholinguistic evidence that people spread information fairly evenly across an utterance, they introduce local typicality: each word's information content should stay near its expected value, which is the model's conditional entropy given the context. Their decoder, locally typical sampling, enforces this by restricting each step's candidates to tokens whose surprisal is close to that entropy. They tested it on abstractive summarization and story generation with automatic metrics and crowdsourced human judgments. Its quality matched or slightly exceeded nucleus and top-k sampling, and it consistently produced fewer degenerate repetitions. The method is cheap, simple, and offers a principled explanation for why the most probable text is often not the most human-like.

Key points

  • The paper formally distinguishes a language model (a distribution over whole strings) from a language process. A process is a valid model only if it is "tight", meaning no probability mass leaks to infinite strings. Their toy example of a non-tight process loses about 0.58 of its mass to such strings.
  • Baselines include nucleus (η = 0.9/0.95), top-k (k = 30/40), temperature, Mirostat and beam search. Locally typical sampling is evaluated with τ = 0.2 and τ = 0.95.
  • Story generation uses GPT-2 medium and large fine-tuned on WritingPrompts. Evaluation combines human ratings (coherence, fluency, interestingness, relevance) with MAUVE, Zipf's coefficient and the REP repetition measure.
  • Typical sampling achieves REP values comparable to human-written text, and human quality scores are on par with or slightly above other stochastic decoders.
  • An implementation is available in the HuggingFace Transformers library. Crowdworkers were paid at least $15 per hour.

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

Fields: Natural language processing

Cited by

82 papers of our library cite it (of the 140884 whose bibliographies we read); 3 of them have a page here, 79 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/tacl_a_00536

@article{meister2023locally,
  title = {{Locally Typical Sampling}},
  author = {Meister, Clara and Pimentel, Tiago and Wiher, Gian and Cotterell, Ryan},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2023},
  doi = {10.1162/tacl\_a\_00536},
  url = {https://doi.org/10.1162/tacl_a_00536}
}

References

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

  1. Noam Chomsky. 1995. The Minimalist Program. MIT Press, Cambridge, MA. find
  2. Matthew Aylett and Alice Turk. 2004. The smooth signal redundancy hypothesis: A functional explanation for relationships between redundancy, prosodic prominence, and duration in spontaneous speech. Language and Speech, 47(1):31–56. https://doi.org/10.1177/00238309040470010201, PubMed: 15298329 ↗
  3. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emi… find
  4. Sourya Basu, Govardana Sachitanandam Ramachandran, Nitish Shirish Keskar, and Lav R. Varshney. 2021. Mirostat: A perplexity-controlled neural text decoding algorithm. In Proceedings of the 9th International Conference on Learning Representations. find
  5. Taylor L. Booth and Richard A. Thompson. 1973. Applying probability measures to abstract languages. IEEE Transactions on Computers, C-22(5):442–450. https://doi.org/10 .1109/T-C.1973.223746 find
  6. Mark Braverman, Xinyi Chen, Sham Kakade, Karthik Narasimhan, Cyril Zhang, and Yi Zhang. 2020. Calibration, entropy rates, and memory in language models. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 1089–1099. PMLR. find
  7. Leo Breiman. 1957. The individual ergodic theorem of information theory. The Annals of Mathematical Statistics, 28(3):809–811. https://doi.org/10.1214/aoms/1177706899 — [doi:10.1214/aoms/1177706899](https://doi.org/10.1214/aoms/1177706899) ↗
  8. Christophe Coupé, Yoon Mi Oh, Dan Dediu, and François Pellegrino. 2019. Different languages, similar encoding efficiency: Comparable information rates across the human communicative niche. Science Advances, 5(9). https://doi.org/10.1126/sciadv.aaw2594, PubMed: 32047854 — [doi:10.1126/sciadv.aaw2594](https://doi.org/10.1126/sciadv.aaw2594) ↗
  9. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chr… find
  10. Thomas M. Cover and Joy A. Thomas. 2012. Elements of Information Theory. John Wiley & Sons. find
  11. Alexandra DeLucia, Aaron Mueller, Xiang Lisa Li, and João Sedoc. 2021. Decoding methods for neural narrative generation. In Proceedings of the 1st Workshop on Natural Language Generation, Evaluation, and Metrics (GEM 2021), pages 166–185, Online. Association for Computational Linguistics. https://d… find
  12. Noam Chomsky. 1957. Syntactic Structures. Mouton and Co., The Hague. https://doi.org/10.1515/9783112316009 — [doi:10.1515/9783112316009](https://doi.org/10.1515/9783112316009) ↗
  13. Sander Dieleman. 2020. Musings on typicality. find
  14. Sergey Edunov, Myle Ott, Michael Auli, and David Grangier. 2018. Understanding back-translation at scale. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 489–500, Brussels, Belgium. Association for Computational Linguistics. https://doi.org/10 .18653/… find
  15. John Hale. 2001. A probabilistic Earley parser as a psycholinguistic model. In Second Meeting of the North American Chapter of the Association for Computational Linguistics. https://doi.org/10.3115/1073336 .1073357 ↗ our card
  16. Bryan Eikema and Wilker Aziz. 2020. Is MAP decoding all you need? The inadequacy of the mode in neural machine translation. In Proceedings of the 28th International Conference on Computational Linguistics, COLING, pages 4506–4520, Barcelona, Spain (Online). International Committee on Computational L… find our card
  17. Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, E… find
  18. 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
  19. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration. In Proceedings of the 8th International Conference on Learning Representations. find
  20. August Fenk and Gertraud Fenk. 1980. Konstanz im Kurzzeitgedächtnis-Konstanz im sprachlichen Informationsfluß. Zeitschrift für ex-perimentelle und angewandte Psychologie, 27(3):400–414. find
  21. Fred Karlsson. 2010. 3. Syntactic recursion and iteration. In Recursion and Human Language. De Gruyter Mouton, Berlin, New York. https://doi.org/10.1515/9783110219258.43 ↗
  22. Edward Gibson, Richard Futrell, Steven T. Piantadosi, Isabelle Dautriche, Kyle Mahowald, Leon Bergen, and Roger Levy. 2019. How efficiency shapes human language. Trends in Cognitive Sciences, 23(5):389–407. https://doi.org/10.1016/j.tics.2019.02.003, PubMed: 31006626 — [doi:10.1016/j.tics.2019.02.003](https://doi.org/10.1016/j.tics.2019.02.003) ↗
  23. Urvashi Khandelwal, He He, Peng Qi, and Dan Jurafsky. 2018. Sharp nearby, fuzzy far away: How neural language models use context. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 284–294, Melbourne, Australia. Association for C… find
  24. Kartik Goyal, Chris Dyer, and Taylor Berg-Kirkpatrick. 2019. An empirical investigation of global and local normalization for recurrent neural sequence models using a continuous relaxation to beam search. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Comp… find
  25. Konrad Knopp. 1954. Theory and Application of Infinite Series. London, Blackie & Son Ltd. find
  26. Jey Han Lau, Alexander Clark, and Shalom Lappin. 2017. Grammaticality, acceptability, and probability: A probabilistic view of linguistic knowledge. Cognitive Science, 41(5):1202–1241. https://doi.org/10 .1111/cogs.12414, PubMed: 27732744 find
  27. Jian Guan, Fei Huang, Zhihao Zhao, Xiaoyan Zhu, and Minlie Huang. 2020. A knowledge-enhanced pretraining model for commonsense Roger Levy and T. Florian Jaeger. 2007. Speakers optimize information density through syntactic reduction. In Advances in Neural Information Processing Systems, volume 19. M… — [doi:10.18653/v1/2020](https://doi.org/10.18653/v1/2020) find
  28. Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020. BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension. In Proceedings of the 58th Annual Meeting of the… find our card
  29. Clara Meister, Tim Vieira, and Ryan Cotterell. 2020b. If beam search is the answer, what was the question? In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, Online. Association for Computational Linguistics. https://doi.org/10.18653/v1/2020.emnlp-main.170 ↗
  30. 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 (Volume 2: Short Papers), pages 36–45, Dublin, Ireland. Association for Computat… find
  31. Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. 2016. A diversity-promoting objective function for neural conversation models. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pag… find our card
  32. Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. 2017. Pointer sentinel mixture models. In Proceedings of the 5th International Conference on Learning Representations. find our card
  33. Margaret Li, Stephen Roller, Ilia Kulikov, Sean Welleck, Y-Lan Boureau, Kyunghyun Cho, and Jason Weston. 2020. Don’t say that! Making inconsistent dialogue unlikely with unlikelihood training. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4715–4728… find our card
  34. 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
  35. Kyle Mahowald, Evelina Fedorenko, Steven T. Piantadosi, and Edward Gibson. 2013. Info/information theory: Speakers choose shorter words in predictive contexts. Cognition, 126(2):313–318. https://doi.org/10 .1016/j.cognition.2012.09.010, PubMed: 23116925 find
  36. Ramesh Nallapati, Bowen Zhou, Cicero dos Santos, Caglar Gulçehre, and Bing Xiang. 2016. Abstractive text summarization using sequence-to-sequence RNNs and beyond. In Proceedings of The 20th SIGNLL Conference on Computational Natural Language Learning, pages 280–290, Berlin, Germany. Association for… find
  37. Brockway McMillan. 1953. The basic theorems of information theory. The Annals of Mathematical Statistics, 24(2):196–219. https://doi.org/10.1214/aoms/1177729028 — [doi:10.1214/aoms/1177729028](https://doi.org/10.1214/aoms/1177729028) ↗
  38. Clara Meister, Elizabeth Salesky, and Ryan Cotterell. 2020a. Generalized entropy regularization or: There’s nothing special about label smoothing. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 6870–6886, Online. Association for Computational Lingui… find
  39. Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ott, Michael Auli, and Sergey Edunov. 2019. Facebook FAIR’s WMT19 news translation task submission. In Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1), pages 314–319, Carson T. Schütze. 2016. The empirical b… find our card
  40. Florence, Italy. Association for Computational Linguistics. find
  41. Gabriel Pereyra, George Tucker, Jan Chorowski, Łukasz Kaiser, and Geoffrey E. Hinton. 2017. Regularizing neural networks by penalizing confident output distributions. In Proceedings of the 5th International Conference on Learning Representations. find our card
  42. Abigail See, Aneesh Pappu, Rohun Saxena, Akhila Yerukola, and Christopher D. Manning. 2019. Do massively pretrained language models make better storytellers? In Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), pages 843–861, Hong Kong, China. Association for Com… find
  43. Steven T. Piantadosi, Harry Tily, and Edward Gibson. 2011. Word lengths are optimized for efficient communication. Proceedings of the National Academy of Sciences, 108(9):3526–3529. https://doi.org/10.1073/pnas.1012551108, PubMed: 21278332 — [doi:10.1073/pnas.1012551108](https://doi.org/10.1073/pnas.1012551108) ↗
  44. Claude E. Shannon. 1948. A mathematical theory of communication. Bell System Technical Journal, 27:623–656. find
  45. 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… find our card
  46. Claude E. Shannon. 1951. Prediction and entropy of printed English. Bell System Technical Journal, 30(1):50–64. https://doi.org/10 .1002/j.1538-7305.1951.tb01366.x Felix Stahlberg and Bill Byrne. 2019. On NMT search errors and model errors: Cat got your tongue? In Proceedings of the 2019 Conference… find our card
  47. Tiago Pimentel, Clara Meister, and Ryan Cotterell. 2022. Cluster-based evaluation of automatically generated text. arXiv preprint arXiv:2205.16001. — [arXiv:2205.16001](https://arxiv.org/abs/2205.16001) find
  48. Tiago Pimentel, Clara Meister, Elizabeth Salesky, Simone Teufel, Damián Blasi, and Ryan Cotterell. 2021. A surprisal–duration trade-off across and within the world’s languages. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 949–962, Online and Punta… find
  49. Chris van der Lee, Albert Gatt, Emiel van Miltenburg, Sander Wubben, and Emiel Krahmer. 2019. Best practices for the human evaluation of automatically generated text. In Proceedings of the 12th International Conference on Natural Language Generation, pages 355–368, Tokyo, Japan. Association for Comp… find
  50. Tiago Pimentel, Brian Roark, and Ryan Cotterell. 2020. Phonotactic complexity and its trade-offs. Transactions of the Association for Computational Linguistics, 8:1–18. https://doi.org/10.1162/tacl a 00296 ↗
  51. Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. 2020. Neural text generation with unlikelihood training. In Proceedings of the 8th International Conference on Learning Representations. find our card
  52. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. find
  53. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Peter A. Reich. 1969. The finiteness of natural language. Language, 45(4):831–843. https://doi.org/10.2307/412337 — [doi:10.2307/412337](https://doi.org/10.2307/412337) ↗
  54. Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language P… find
  55. Noga Zaslavsky, Charles Kemp, Terry Regier, and Naftali Tishby. 2018. Efficient compression in color naming and its evolution. Proceedings of the National Academy of Sciences, 115(31):7937–7942. https://doi.org/10 .1073/pnas.1800521115, PubMed: 30021851 find
  56. Hugh Zhang, Daniel Duckworth, Daphne Ippolito, and Arvind Neelakantan. 2021. Trading off diversity and quality in natural language generation. In Proceedings of the Workshop on Human Evaluation of NLP Systems (Hum-Eval), pages 25–33, Online. Association for Computational Linguistics. find
  57. Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, N… find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/meister-2023-locally-typical-sampling/