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

Jiacheng Liu, Sewon Min, Luke Zettlemoyer, Yejin Choi, Hannaneh Hajishirzi

TL;DR

The authors modernize classical $n$-gram language models by scaling them to 5 trillion tokens and allowing the context window ($n$) to be arbitrarily large. By using a suffix-array-based engine called infini-gram, they achieve millisecond-level latency and demonstrate that these "unbounded" models can significantly reduce the perplexity of state-of-the-art neural LLMs.

What Problem Does This Paper Address?

In the era of Large Language Models (LLMs), classical $n$-gram models—which predict the next word based on a fixed window of previous words—are often dismissed as obsolete. Historically, they suffered from two major limitations:

  1. Small Context Windows: Because $n$-gram count tables grow exponentially with $n$, researchers typically limited $n$ to 5 or less, making the models "short-sighted."
  2. Data Scale: While neural LLMs are trained on trillions of tokens, the largest $n$-gram models were significantly smaller.

This paper asks: Are $n$-gram models still relevant if we scale them to the same data and context levels as neural LLMs?

An example showing how a 5-gram model fails while an $\infty$-gram model succeeds by using a longer context.

Methods

The researchers introduced two key innovations:

  • $\infty$-gram LM with Backoff: Instead of a fixed $n$, this model uses the longest possible suffix of the current prompt that actually appears in the training data. If a 100-token sequence exists in the corpus, it uses it; if not, it "backs off" to shorter sequences until it finds a match.
  • Infini-gram Engine: To handle unbounded $n$ without massive count tables, they used suffix arrays. This data structure allows for extremely fast counting of any sequence (the "needle") within a massive corpus (the "haystack"). Their implementation is highly optimized, keeping the index on-disk to minimize RAM usage while maintaining millisecond-level query speeds.
Figure 2: Left: the suffix array for a toy string. Right: illustration of the suffix array in the infini-gram index, with N = 4 tokens in the dataset.

Datasets

The authors built an index totaling 5 trillion tokens, combining several massive open-source corpora:

  • Dolma: 3 trillion tokens.
  • RedPajama: 1.4 trillion tokens.
  • The Pile: 380 billion tokens.
  • C4: 200 billion tokens.

They evaluated their models on the Pile’s validation and test sets, using a rigorous "decontamination" process to ensure the model wasn't simply "cheating" by looking up the exact test documents in its training data.

Key Insights and Ideas

  • Verbatim Matching is Powerful: On human-written text, the $\infty$-gram model achieves 47% accuracy for next-token prediction. When the model is "sparse" (meaning only one possible next token exists in the 5-trillion-token corpus for a given context), accuracy jumps even higher.
  • Complementary Strengths: Neural LLMs are great at general reasoning and "vibe," but they sometimes struggle with exact factual sequences or rare phrases. The $\infty$-gram model excels exactly where neural models are weak.
  • Transformer Deficiencies: By comparing machine-generated text to the $\infty$-gram index, the authors found that "greedy" decoding in Transformers leads to weird, periodic fluctuations in how much the model agrees with the training data. This suggests underlying issues with how Transformers handle positional embeddings.

Key Results

  • Perplexity Reduction: Interpolating (mixing) $\infty$-gram probabilities with neural LLMs (like Llama-2 70B) reduced perplexity by up to 73%.
  • Efficiency: The infini-gram engine can count an $n$-gram in less than 20 milliseconds and compute a full $\infty$-gram next-token distribution in about 200 milliseconds.
  • Storage: The index requires about 7 bytes per token, meaning a 1.4-trillion-token corpus fits into roughly 10 TB of disk space—manageable for a single high-end server.

Limitations and Future Work

  • Not for Open-Ended Generation: On its own, the $\infty$-gram model can make "odd mistakes" (like predicting totally irrelevant tokens if a weird context match is found), making it unsuitable for standalone text generation.
  • Factual Recall: While good at completing phrases, it struggles to recall factual knowledge if the specific entity name hasn't appeared yet in the prompt.
  • Future Directions: The authors suggest using infini-gram for speculative decoding (using the fast $n$-gram model to draft tokens for a slower neural model) and for detecting data contamination and plagiarism in LLM outputs.

Summary updated

Abstract

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 $\infty$-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 $\infty$-gram (as well as $n$-gram with arbitrary $n$) probabilities with millisecond-level latency. The $\infty$-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 $\infty$-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--$\infty$-gram agreement level with respect to the suffix length, which indicates deficiencies in neural LLM pretraining and the positional embeddings of Transformers.
BibTeX
@inproceedings{liu2024infini,
  author = {Jiacheng Liu and Sewon Min and Luke Zettlemoyer and Yejin Choi and Hannaneh Hajishirzi},
  title = {{Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens}},
  booktitle = {COLM},
  year = {2024},
  url = {https://openreview.net/forum?id=u2vAyMeLMm},
}
Figure