Skip to content
The methodOpen data
Back to the collection

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

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

2024 · arXiv

Language models
Read the paper
HN score
1
Mentions
6
Readers
4
Months
4
What’s in a score?

From the 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.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

6 selected excerpts · 6 total mentions

shenberg
Recommendation · rule
The short and unsatisfying answer is that an LLM generation is a markov chain, except that instead of counting n-grams in order to generate the posterior distribution, the training process compresses the statistics into the LLM's weights. There was an interesting paper a while back which investigated using unbounded n-gram models as a complement to LLMs: https://arxiv.org/pdf/2401.17377 (I found the implementation to be clever and I'm somewhat surprised it received so little follow-up work)
Original comment Ask HN: How are Markov chains so different from tiny LLMs?
yorwba
Neutral mention · rule
You can build an unlimited-order Markov chain by, instead of pre-computing a table of counts for all possible contexts, using a substring-search index on the training data to count possible continuations on the fly: https://arxiv.org/abs/2401.17377 That paper uses suffix arrays, but more compact indices are possible: https://arxiv.org/abs/2506.12229
Original comment Soul Player C64 – A real transformer running on a 1 MHz Commodore 64
astrange
Neutral mention · rule
> This is entirely different from saying it can only reproduce samples which it was trained on. It is not a memory machine that is surgically piecing together snippets of memorized samples. (That would be a mind bogglingly impressive machine!) You could create one of those using both a Markov chain and an LLM. https://arxiv.org/abs/2401.17377
Original comment Ask HN: How are Markov chains so different from tiny LLMs?
yorwba
Neutral mention · rule
In this case, the curse of dimensionality is working in our favor, as the volume of an n-dimensional simplex also grows exponentially, so it is perfectly suited to hold the exponential state space of the mixed-state presentation. Updating from one mixed-state to another just involves updating for each pure state in the mixture and then mixing the resulting states together, so everything is neatly linear. One way to represent the training data would be to have one state per token position that emits the corresponding token and advances to the next position, or to a randomly sampled other document if there's no next position. That matches the way LLMs are actually trained,…
Read the full comment
but of course typical transformers have a much smaller residual stream dimension than the number of training tokens, so it needs to conflate some states, and synchronizing with the training data is also not what we want models to do, otherwise we would be using infini-gram https://arxiv.org/abs/2401.17377 to regurgitate exact matches.
Original comment Transformers Represent Belief State Geometry in Their Residual Stream

Keep following the thread.

More in Language models

More from the same topics.