Elamur Research⌕
☰
home / papers / 2024 / Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens

Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens

Paper · 2024 · Jiacheng Liu, Sewon Min, Luke Zettlemoyer et al.

Summary

Classical n-gram language models are usually limited to small n (often 5) and modest data, because count tables grow explosively with n. This paper asks whether n-gram models still have value alongside neural LLMs. The authors build one over roughly 5 trillion tokens from Dolma, RedPajama, Pile and C4 and remove the cap on n. Their ∞-gram LM backs off only when a context has never been seen. In effect, it conditions on the longest prompt suffix found in the corpus, which gives a proper distribution without discounting. Rather than storing counts, the infini-gram engine indexes the tokenized corpus with a suffix array and answers count and probability queries in milliseconds directly from disk. On human-written text, ∞-gram predicts the next token far better than short-context n-grams. Mixing it with neural LMs, including Llama-2 70B, substantially lowers perplexity. The resource also supports corpus analysis and source attribution, and is publicly released.

Key points

  • The index uses about 7 bytes per token, a 3.5x overhead over raw data. Building it for RedPajama (1.4T tokens) took about 48 hours on one 128-CPU node with 1 TiB RAM.
  • Counting queries average under 20 ms, and other queries, including ∞-gram probabilities, finish in under 200 ms.
  • Next-token accuracy is 47% for ∞-gram versus 29% for conventional small-n n-grams.
  • Linear interpolation with neural LMs cuts perplexity by up to 73%. Llama-2 13B plus ∞-gram outperforms Llama-2 70B alone, and Llama-2 70B drops below 4.0 perplexity. However, gains do not carry over to open-ended generation.
  • Released resources include a web demo, an API, the infini-gram Python package and the GitHub code. They cover Dolma, RedPajama, Pile and C4.

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 WashingtonSeattle · United States353 works · 200,043 citations🔬Allen Institute for Artificial IntelligenceSeattle · United States275 works · 97,634 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 1Research subjects and languages the work is about.Language models & pretraining · 3,320 works

💡 Concepts 1Key ideas and methods explained on our concept pages.N-gram · 26 works

Cite

Cite as Jiacheng Liu, Sewon Min, Luke Zettlemoyer, Yejin Choi and Hannaneh Hajishirzi. 2024. Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens. arXiv:2401.17377.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2401.17377 · arXiv 2401.17377

@misc{liu2024infini,
  title = {{Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens}},
  author = {Jiacheng Liu, Sewon Min, Luke Zettlemoyer, Yejin Choi and Hannaneh Hajishirzi},
  year = {2024},
  doi = {10.48550/arxiv.2401.17377},
  eprint = {2401.17377},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2401.17377}
}

References

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

  1. Erez Lieberman Aiden and Jean-Baptiste Michel. Quantitative analysis of culture using millions of digitized books. Science, 331:176 – 182, 2011. URL https://api.semanticscholar.org/CorpusID:40104730. ↗
  2. Miltiadis Allamanis and Charles Sutton. Mining source code repositories at massive scale using language modeling. 2013 10th Working Conference on Mining Software Repositories (MSR), pp. 207–216, 2013. URL https://api.semanticscholar.org/CorpusID:1857729. ↗
  3. Akari Asai, Sewon Min, Zexuan Zhong, and Danqi Chen. Acl 2023 tutorial: Retrieval-based language models and applications.
  4. Akari Asai, Zexuan Zhong, Danqi Chen, Pang Wei Koh, Luke Zettlemoyer, Hanna Hajishirzi, and Wen tau Yih. Reliable, adaptable, and attributable language models with retrieval. 2024. URL https://api.semanticscholar.org/CorpusID:268248911. ↗
  5. Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. In Proceedings of the International Conference on Learning Representations, 2019. find
  6. Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George Bm Van Den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, et al. Improving language models by retrieving from trillions of tokens. In Proceedings of the International Conference of… find
  7. T. Brants, Ashok Popat, Peng Xu, Franz Josef Och, and Jeffrey Dean. Large language models in machine translation. In Conference on Empirical Methods in Natural Language Processing, 2007. URL https://api.semanticscholar.org/CorpusID:633992. ↗
  8. Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, L. Sifre, and John M. Jumper. Accelerating large language model decoding with speculative sampling. ArXiv, abs/2302.01318, 2023. URL https://api.semanticscholar.org/CorpusID: 256503945. ↗
  9. Jesse Dodge, Ana Marasovic, Gabriel Ilharco, Dirk Groeneveld, Margaret Mitchell, and Matt Gardner. Documenting large webtext corpora: A case study on the colossal clean crawled corpus. In Conference on Empirical Methods in Natural Language Processing, 2021. URL https://api.semanticscholar.org/Corpus… ↗
  10. Yanai Elazar, Akshita Bhagia, Ian Magnusson, Abhilasha Ravichander, Dustin Schwenk, Alane Suhr, Pete Walsh, Dirk Groeneveld, Luca Soldaini, Sameer Singh, Hanna Hajishirzi, Noah A. Smith, and Jesse Dodge. What’s in my big data? ArXiv, abs/2310.20707, 2023. URL https://api.semanticscholar.org/CorpusID… ↗
  11. Alex Franz and Thorsten Brants. All our n-gram are belong to you. Google Machine Translation Team, 20, 2006. URL https://blog.research.google/2006/08/ all-our-n-gram-are-belong-to-you.html. ↗
  12. Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. The Pile: An 800GB dataset of diverse text for language modeling. arXiv preprint arXiv:2101.00027, 2020. find
  13. Xinyang Geng and Hao Liu. Openllama: An open reproduction of llama, May 2023. URL https://github.com/openlm-research/open llama. ↗
  14. Dirk Groeneveld. The big friendly filter. https://github.com/allenai/bff, 2023. ↗
  15. Dirk Groeneveld, Iz Beltagy, Pete Walsh, Akshita Bhagia, Rodney Kinney, Oyvind Tafjord, Ananya Harsh Jha, Hamish Ivison, Ian Magnusson, Yizhong Wang, Shane Arora, David Atkinson, Russell Authur, Khyathi Chandu, Arman Cohan, Jennifer Dumas, Yanai Elazar, Yuling Gu, Jack Hessel, Tushar Khot, William M… find
  16. Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. Retrieval augmented language model pre-training. In Proceedings of the International Conference of Machine Learning, 2020. — REALM: Retrieval-Augmented Language Model Pre-Training
  17. Zhenyu He, Zexuan Zhong, Tianle Cai, Jason D Lee, and Di He. Rest: Retrieval-based speculative decoding. 2023. URL https://api.semanticscholar.org/CorpusID:265157884. ↗
  18. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. ArXiv, abs/1904.09751, 2019. URL https://api.semanticscholar.org/CorpusID:127986954. ↗
  19. Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi-Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave. Few-shot learning with retrieval augmented language models. arXiv preprint arXiv:2208.03299, 2022.
  20. Dan Jurafsky and James H. Martin. Speech and language processing - an introduction to natural language processing, computational linguistics, and speech recognition. In Prentice Hall series in artificial intelligence, 2000. URL https://api.semanticscholar.org/CorpusID: 60691216. ↗
  21. Juha Kärkkäinen, Peter Sanders, and Stefan Burkhardt. Linear work suffix array construction. J. ACM, 53:918–936, 2006. URL https://api.semanticscholar.org/CorpusID:12825385. ↗
  22. Slava M. Katz. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Trans. Acoust. Speech Signal Process., 35:400–401, 1987. URL https://api.semanticscholar.org/CorpusID:6555412. ↗
  23. Casey Redd Kennington, Martin Kay, and Annemarie Friedrich. Suffix trees as language models. In International Conference on Language Resources and Evaluation, 2012. URL https://api.semanticscholar.org/CorpusID:12071964. ↗
  24. Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. In Proceedings of the International Conference on Learning Representations, 2020. find
  25. Tian Lan, Deng Cai, Yan Wang, Heyan Huang, and Xian-Ling Mao. Copy is all you need. In Proceedings of the International Conference on Learning Representations, 2023. find
  26. Katherine Lee, Daphne Ippolito, Andrew Nystrom, Chiyuan Zhang, Douglas Eck, Chris Callison-Burch, and Nicholas Carlini. Deduplicating training data makes language models better. In Proceedings of the Association for Computational Linguistics, 2022. find
  27. Huayang Li, Deng Cai, Jin Xu, and Taro Watanabe. Residual learning of neural text generation with n-gram language model. In Findings of the Association for Computational Linguistics: EMNLP 2022, 2022. URL https://aclanthology.org/2022.findings-emnlp.109. ↗
  28. Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Hannaneh Hajishirzi, and Daniel Khashabi. When not to trust language models: Investigating effectiveness of parametric and non-parametric memories. In Annual Meeting of the Association for Computational Linguistics, 2022. URL https://api.semantics… ↗
  29. Marc Marone and Benjamin Van Durme. Data portraits: Recording foundation model training data. ArXiv, abs/2303.03919, 2023. URL https://api.semanticscholar.org/ CorpusID:257378087. — [arXiv:2303.03919](https://arxiv.org/abs/2303.03919) ↗
  30. Tomas Mikolov and Geoffrey Zweig. Context dependent recurrent neural network language model. 2012 IEEE Spoken Language Technology Workshop (SLT), pp. 234–239, 2012. URL https://api.semanticscholar.org/CorpusID:11383176. ↗
  31. Sewon Min, Suchin Gururangan, Eric Wallace, Hannaneh Hajishirzi, Noah Smith, and Luke Zettlemoyer. SILO language models: Isolating legal risk in a nonparametric datastore. arXiv preprint arXiv:2308.04430, 2023a. URL https://arxiv.org/abs/2308.04430. ↗
  32. Sewon Min, Weijia Shi, Mike Lewis, Xilun Chen, Wen-tau Yih, Hannaneh Hajishirzi, and Luke Zettlemoyer. Nonparametric masked language modeling. In Findings of ACL, 2023b. find
  33. Daichi Mochihashi and Eiichiro Sumita. The infinite markov model. In Neural Information Processing Systems, 2007. URL https://api.semanticscholar.org/CorpusID:1279894. ↗
  34. Fabio Petroni, Tim Rocktäschel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, Alexander H. Miller, and Sebastian Riedel. Language models as knowledge bases? ArXiv, abs/1909.01066, 2019. URL https://api.semanticscholar.org/CorpusID:202539551. ↗
  35. Aleksandra Piktus, Christopher Akiki, Paulo Villegas, Hugo Laurenccon, Gérard Dupont, Alexandra Sasha Luccioni, Yacine Jernite, and Anna Rogers. The roots search tool: Data transparency for llms. In Annual Meeting of the Association for Computational Linguistics, 2023. URL https://api.semanticschol… ↗
  36. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019. find
  37. Edward Raff, William Fleming, Richard Zak, H. Anderson, Bill Finlayson, Charles K. Nicholas, and Mark McLean. Kilograms: Very large n-grams for malware classification. ArXiv, abs/1908.00200, 2019. URL https://api.semanticscholar.org/CorpusID: 199064443. — [arXiv:1908.00200](https://arxiv.org/abs/1908.00200) ↗
  38. Colin Raffel, Noam M. Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res., 21:140:1–140:67, 2019. URL https://api.semanticscholar.org/CorpusI… ↗
  39. Ehsan Shareghi, Matthias Petri, Gholamreza Haffari, and Trevor Cohn. Compact, efficient and unlimited capacity: Language modeling with compressed suffix trees. In Conference on Empirical Methods in Natural Language Processing, 2015. URL https://api.semanticscholar.org/CorpusID:225428. ↗
  40. Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih. REPLUG: Retrieval-augmented black-box language models. arXiv preprint arXiv:2301.12652, 2023.
  41. Luca Soldaini, Rodney Kinney, Akshita Bhagia, Dustin Schwenk, David Atkinson, Russell Authur, Khyathi Chandu, Jennifer Dumas, Li Lucy, Xinxi Lyu, Ian Magnusson, Aakanksha Naik, Crystal Nam, Matthew E. Peters, Abhilasha Ravichander, Zejiang Shen, Emma Strubell, Nishant Subramani, Oyvind Tafjord, Evan… find
  42. Herman Stehouwer and Menno van Zaanen. Using suffix arrays as language models: Scaling the n-gram. 2010. URL https://api.semanticscholar.org/CorpusID:18379946. ↗
  43. Together. RedPajama: An open source recipe to reproduce LLaMA training dataset, 2023. URL https://github.com/togethercomputer/RedPajama-Data. ↗
  44. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. LLaMA: Open and efficient foundation language models. arXiv prepri…
  45. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023b.
  46. Thuy-Trang Vu, Xuanli He, Gholamreza Haffari, and Ehsan Shareghi. Koala: An index for quantifying overlaps with pre-training corpora. In Conference on Empirical Methods in Natural Language Processing, 2023. URL https://api.semanticscholar.org/CorpusID: 257766452. ↗
  47. Ben Wang and Aran Komatsuzaki. GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model. https://github.com/kingoflolz/mesh-transformer-jax, May 2021. ↗
  48. Frank D. Wood, C. Archambeau, Jan Gasthaus, Lancelot F. James, and Yee Whye Teh. A stochastic memoizer for sequence data. In International Conference on Machine Learning, 2009. URL https://api.semanticscholar.org/CorpusID:11199892. ↗
  49. Zexuan Zhong, Tao Lei, and Danqi Chen. Training language models with memory augmentation. In Proceedings of Empirical Methods in Natural Language Processing, 2022. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/liu-2024-infini-gram-scaling-unbounded-n/