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

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

## Key facts

- Cited by 153 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 51 references that are in the map.
- First posted on arXiv 30 Jan 2024.

## Builds on (most cited first, 25 of 25)

- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Atlas: Few-shot Learning with Retrieval Augmented Language Models](https://mlsanity.com/paper/2208.03299/) (2022)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [REPLUG: Retrieval-Augmented Black-Box Language Models](https://mlsanity.com/paper/2301.12652/) (2023)
- [Deduplicating Training Data Makes Language Models Better](https://mlsanity.com/paper/2107.06499/) (2021)
- [Documenting Large Webtext Corpora: A Case Study on the Colossal Clean Crawled Corpus](https://mlsanity.com/paper/2104.08758/) (2021)
- [Adaptive Input Representations for Neural Language Modeling](https://mlsanity.com/paper/1809.10853/) (2018)
- [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023)
- [What's In My Big Data?](https://mlsanity.com/paper/2310.20707/) (2023)
- [Training Language Models with Memory Augmentation](https://mlsanity.com/paper/2205.12674/) (2022)
- [SILO Language Models: Isolating Legal Risk In a Nonparametric Datastore](https://mlsanity.com/paper/2308.04430/) (2023)
- [Nonparametric Masked Language Modeling](https://mlsanity.com/paper/2212.01349/) (2022)
- [The ROOTS Search Tool: Data Transparency for LLMs](https://mlsanity.com/paper/2302.14035/) (2023)
- [Data Portraits: Recording Foundation Model Training Data](https://mlsanity.com/paper/2303.03919/) (2023)
- [Copy Is All You Need](https://mlsanity.com/paper/2307.06962/) (2023)
- [Koala: An Index for Quantifying Overlaps with Pre-training Corpora](https://mlsanity.com/paper/2303.14770/) (2023)
- [KiloGrams: Very Large N-Grams for Malware Classification](https://mlsanity.com/paper/1908.00200/) (2019)

## Built on by (most cited first, 30 of 153)

- [A General Framework for Inference-time Scaling and Steering of Diffusion Models](https://mlsanity.com/paper/2501.06848/) (2025)
- [Conditional Memory via Scalable Lookup: A New Axis of Sparsity for Large Language Models](https://mlsanity.com/paper/2601.07372/) (2026)
- [Generalization v.s. Memorization: Tracing Language Models' Capabilities Back to Pretraining Data](https://mlsanity.com/paper/2407.14985/) (2024)
- [SuperBPE: Space Travel for Language Models](https://mlsanity.com/paper/2503.13423/) (2025)
- [Demystifying Verbatim Memorization in Large Language Models](https://mlsanity.com/paper/2407.17817/) (2024)
- [Gender, Race, and Intersectional Bias in Resume Screening via Language Model Retrieval](https://mlsanity.com/paper/2407.20371/) (2024)
- [Can LLM Graph Reasoning Generalize beyond Pattern Memorization?](https://mlsanity.com/paper/2406.15992/) (2024)
- [Theoretical Benefit and Limitation of Diffusion Language Model](https://mlsanity.com/paper/2502.09622/) (2025)
- [Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling](https://mlsanity.com/paper/2501.16975/) (2025)
- [Safety Pretraining: Toward the Next Generation of Safe AI](https://mlsanity.com/paper/2504.16980/) (2025)
- [AI as Humanity's Salieri: Quantifying Linguistic Creativity of Language Models via Systematic Attribution of Machine Text against Web Text](https://mlsanity.com/paper/2410.04265/) (2024)
- [Tracing the Representation Geometry of Language Models from Pretraining to Post-training](https://mlsanity.com/paper/2509.23024/) (2025)
- [Diffusion Tree Sampling: Scalable inference-time alignment of diffusion models](https://mlsanity.com/paper/2506.20701/) (2025)
- [DAPE: Data-Adaptive Positional Encoding for Length Extrapolation](https://mlsanity.com/paper/2405.14722/) (2024)
- [OLMoTrace: Tracing Language Model Outputs Back to Trillions of Training Tokens](https://mlsanity.com/paper/2504.07096/) (2025)
- [Understanding Transformers via N-gram Statistics](https://mlsanity.com/paper/2407.12034/) (2024)
- [WikiBigEdit: Understanding the Limits of Lifelong Knowledge Editing in LLMs](https://mlsanity.com/paper/2503.05683/) (2025)
- [Evaluating n-Gram Novelty of Language Models Using Rusty-DAWG](https://mlsanity.com/paper/2406.13069/) (2024)
- [Avoiding Copyright Infringement via Large Language Model Unlearning](https://mlsanity.com/paper/2406.10952/) (2024)
- [Deriving Neural Scaling Laws from the statistics of natural language](https://mlsanity.com/paper/2602.07488/) (2026)
- [Language Models are Surprisingly Fragile to Drug Names in Biomedical Benchmarks](https://mlsanity.com/paper/2406.12066/) (2024)
- [The Illusion of Certainty: Uncertainty Quantification for LLMs Fails under Ambiguity](https://mlsanity.com/paper/2511.04418/) (2025)
- [Synthesizing Privacy-Preserving Text Data via Finetuning without Finetuning Billion-Scale LLMs](https://mlsanity.com/paper/2503.12347/) (2025)
- [Cross-Care: Assessing the Healthcare Implications of Pre-training Data on Language Model Bias](https://mlsanity.com/paper/2405.05506/) (2024)
- [Speculative Speculative Decoding](https://mlsanity.com/paper/2603.03251/) (2026)
- [From Loops to Oops: Fallback Behaviors of Language Models Under Uncertainty](https://mlsanity.com/paper/2407.06071/) (2024)
- [Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Index](https://mlsanity.com/paper/2506.12229/) (2025)
- [Reverse Question Answering: Can an LLM Write a Question so Hard (or Bad) that it Can't Answer?](https://mlsanity.com/paper/2410.15512/) (2024)
- [Language Model Behavioral Phases are Consistent Across Architecture, Training Data, and Scale](https://mlsanity.com/paper/2510.24963/) (2025)
- [The Responsible Foundation Model Development Cheatsheet: A Review of Tools & Resources](https://mlsanity.com/paper/2406.16746/) (2024)

## Abstract (arXiv)

Are n-gram language models still relevant in this era of neural large language models (LLMs)? Our answer is yes, and we showcase their values in both text analysis and improving neural LLMs. This was done by modernizing n-gram LMs in two aspects. First, we train them at the same data scale as neural LLMs -- 5 trillion tokens. This is the largest n-gram LM ever built. Second, existing n-gram LMs use small n which hinders their performance; we instead allow n to be arbitrarily large, by introducing a new ∞-gram LM with backoff. Instead of pre-computing n-gram count tables (which would be very expensive), we develop an engine named infini-gram -- powered by suffix arrays -- that can compute ∞-gram (as well as n-gram with arbitrary n) probabilities with millisecond-level latency. The ∞-gram framework and infini-gram engine enable us to conduct many novel and interesting analyses of human-written and machine-generated text: we find that the ∞-gram LM has fairly high accuracy for next-token prediction (47%), and can complement neural LLMs to greatly reduce their perplexity. When analyzing machine-generated text, we also observe irregularities in the machine--∞-gram agreement level with respect to the suffix length, which indicates deficiencies in neural LLM pretraining and the positional embeddings of Transformers.