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:
- 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."
- 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?
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.
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