Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens
Authors: Jiacheng Liu
Sewon Min
Luke Zettlemoyer
Yejin Choi
Hannaneh Hajishirzi
Venue: COLM (2024)
Keywords: infini-gram,n-gram,language model,suffix array
TL;DR: We built the largest ever n-gram LM on trillions of tokens and with unbounded n, developed a method to efficiently train and serve it, and showed its great utility in this era of neural LLMs.

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 one of the largest $n$-gram LMs 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.

Published as a conference paper at COLM 2024
Infini-gram:
Scaling Unbounded n-gram Language Models to Trillion Tokens
Jiacheng Liu
Sewon Min
Luke Zettlemoyer Yejin Choi Hannaneh Hajishirzi
Paul G. Allen School of Computer Science & Engineering, University of Washington
Allen Institute for Artificial Intelligence
liujcêcs. washington. edu
Abstract
Are n-gram language models still relevant in this era of neural large lan- guage models (LLMs)? Our answer is yes, and we showcas. their values both text analysis and improving neural LLMs. This was done by mod- ernizing n-gram LMs in two aspects. First, we train them at the same data scale as neural 5 trillion tokens. This the largest l-gram LM ever built. Second, existing "-gram LMs use small which hinders their performance; we instead allow to be arbitrarily large, by introducing a new co-gram LM with backoff. Instead of pre-computing #-gram count tables (which would be very expensive), we develop an engine named sefni-ggram-poweeee by suffix arrays that can compute oo-gram (as well as n-gram with arbitrary πτ) probabílities with millisecond-leve latency. The co-gram framework and infini-gram engine enable us to conduct many novel and interesting analyses of human-written and pachine--generaee text: we find that the o0-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 ir- regularities in the machine-co-gen agreement level with respect to the suffix length, which indicates deficiencies in neural LLM pretraining and the positional embeddings of Transformers.
Project Page
infini-gram io infini-ge grrim..gaam..m io/demo infini-gan infini-gram.io/ppi... io/api_doc pypi. pygi.oor//rrojett//iiiiiinngga
Web Interface
API End
Python Package
Prompt
conducts research at the Paul G. Allen School of Computer Science and Enginearing, University of
5-gram LM
(71 5)
oc- -r-g-am LM
(/ 16 for this case)
ent(Engineering, University of) 274644
cnt(research at Paul Allen School Computer Science and Engineering. University 0
Engineering, University of)
enti Paul Allen School Computer Science and Engineering, University of)
P( * the Paul Allen School Computer Science Engineering, University of)
Jiliinssa (1063: / 204244)
200644)
Jashington
1908
Solouods (6498 200644)
Southers (6388 200644)
5-gram (28 TIB)
Infini-gram (10 Tie)
_uschingtoe (6343 2766443
An example where a 5-gram LM gives an incorrect prediction but the c0-gram gives the correct prediction by using the longest suffix of the prompt that has non-zero count in the corpus. The counting and distribution estimate co-gram LM are powered by our infini-gram engine.
Figure 1:

---

Published as a conference paper at COLM 2024
1 Introduction
When pretrained on trillion-token corpora, neural large language models (LLMs) achieve groundbreaking performance (Touvron et al., 2023a; Geng & Liu, 2023; Groeneveld et al., 2024). However, we do not yet know how such data scale would benefit other language modeling approaches. In particular, how well does the classical, 1-gram language model (LM) perform if estimated from such massive corpora? In other words, are n-gram LMs sfill relevant in this era of neural LLMs?
Our answer is yes. As we will show, n-gram LMs are useful for both text analysis and improving neural LLMs. Yet we need to first modernize the canonical r--rrm LM in two aspects: the training data size, and the value of 11. To achieve broader data coverage, we scale up the training data for n-gram LMs to 5 trillion tokens, by combining some of the largest open-source text corpora. This is the largest 1--ram LM ever built. Historically, n-gram indexes have been built only for small n's (e.g. n S 5; Brants et al. (2007)), because the size of naive n-gram count table grows almost exponentially wrt n. We instead find significant value in increasing the value of n. As illustrated in Figure 1, a 5-gram LM is poorly predictive of the next token, because it discards the rich context in the prompt; meanwhile, we can use a larger и (in this case n 16), the prediction becomes much more accurate. As such, we develop our n-gram LM with unbounded n, or in other words, an oo-gram LM. We use a variant of backoff (Jurafsky & Martin, 2000), where we resort to smaller when longer n n-grams have zero count. Due to sparsity in the co-gram estimates, in some of the later experiments (65), we will interpolate between the oo-gram LM and neural LMs to yield a hybrid LM upon which perplexity can be computed.
We develop a low-latency, resource-efficiet engine to serve this massive co-gram LM. Instead of building an explicit n-gram count table, which is infeasible for arbitrarily large and such extreme data scale, we power the oo-gram LM with suffix array of the dataset- data structure that supports fast n-gram counting, and is efficient in both storage space and compute. Our index takes 7 bytes of storage per token (3.5x overhead compared to the raw dataset), and on dataset with 1.4 trillion tokens, it can be built with a single 128-code CPU node in about 2 days, using 10 TB of disk storage. Average inference latency is less than 20 milliseconds for counting an n-gram and finding all positions of its occurrence (regardless of how large ı is or how frequently the n-gram appears), and under 200 milliseconds for all other query types including co-gram language modeling and decoding. All indexes stay on-disk at inference time. We refer to this engine as infini-gram.
Analyses with co-gram (64) offers new insights into human-written and machine-generated text. We found that co-gram has fairly high accuracy (47%) when predicting the next token given a prefix of a human-written document, and this accuracy is higher on tokens where the effective n is larger. In contrast, conventional æ--rams (with small n) are insufficient in capturing a long enough context to predict the next token (29% accuracy). Moreover, we show that oo-gram can complement neural LMs and reach better performance when combined: heuristically interpolating between the estimates made by oo-gram and neural LMs can greatly reduce perplexity (by up to 73%) compared to the neural LMs alone, even when the neural LM is as large as 70B ($5). When analyzing the level of agreement with oo-gram, nucleus sampling (Holtzman et al., 2019) from neural LMs produces machine- generated text with an agreement plot most similar to human-written text, among other decoding methods like greedy decoding and temperature sampling; for greedy decoding, we observe significant fluctuation in the agreement level wrt the suffix length, which indicates deficiencies in neural LM pretraining and the positional embeddings of Transformers.
We are hosting host public web interface and an API endpoint that serve n-gram co-grrm queries on several popular open corpora: Dolma (Soldaini et al., 2023), RedPajama (Together, 2023), Pile (Gao et al., 2020), and C4 (Raffel et al., 2019). We hope these tools can enable more insightful analysis and understanding of large text corpora, and open up new avenues for data-driven language modeling.
2

---

Published as a conference paper at COLM 2024
2 o0-gram LM: Extending n-gram LMs with Unbounded n
Background: n-gram LM.
The n-gram LM is classical, statistical language model based
on counting the occurrences of n-grams. In its most simple form, the probability of token
cnl( [i (1a--1))111
wi given a context Wi-(x-1)--1 is estimated as Pn (w; wi-(n-1)--1)
cnt (1----)) D)
where cnt(w) D) is the number of times the n-gram w appears in the training data D (i.e., a corpus), and и pre-defined hyperparameter. (When 1, we define (n-1111)a-1 as the empty string e, whose count is equal to [D].) However, this naive version of æt-gram LM faces the sparsity issue: the numerator may be zero, resulting in an infinite perplexity. One common solution is backoff (Jurafsky & Martin, 2000): on an instance-wise basis, when the numerator zero we decrease by one, and do this repeatedly until the numerator becomes positive. One caveat in backoff is that it does not yield a valid distribution for Ps (+|w; (1-)-((-)))-1)) because the effective is dependent on wp Therefore, further probability discounting is required to normalize this distribution (e.g,, Katz backoff (Katz, 1987)).
Conventionally, #-gram LMs have been implemented by building an R--ram count table of the training data. This table stores all unique n1 11-ramms that appear in the training data, each associated with its count. Such 1--gam count tables are huge and grow almost exponentially wrt n. For example, the 5-gram count table for a 1.4-trillion-tkerr corpus would consume 28 TB of disk space. As result, previous 1--ram LMs are limited to very small и, most commonly n = 5, and to frequent n-grams only (e.g, Franz & Brants (2006)). As we illustrated in Figure 1 and will further quantify in $4, the problem with small is that discards richer context, making such 1-gram LMs poorly predictive of future tokens.
o0-gram LM. The oo-gram LM is a generalization of the æt-ram LM, where conceptually we start backing off from л co. We use variant of backoff: we backoff only when the denominator is zero. This means we stop backing off as soon as the denominator becomes positive, upon which the numerator might still be zero. On an instance-wise basis, the effective n is equal to one plus the length of the prompt's 's longest suffix that appears in the training data.
For the rest of this paper, we will use "oo-gram" to refer to the co-gram LM. oo-gram is formally defined
Poo (wi wh--1) (n 1) 1):- D)
cnt(w)-(1-1)j-1 D)
where w all tokens preceding wy in the document, and
n max(n' E [1,i] cnt(#) D) 0}.
valid distribution by construction and does not require discounting. This is because the effective is solely dependent on Win 1 and does not depend on w;, and Em,ev cnt(w) (n 1) 120;
Unlike Katz backoff, Poo (*|w);i-1)
(D) cnt(w, (n 1) D).
Further, we define the sparsity of this co-gram estimate: an estimate sparse iff P(w;| 1)ri 1) = for one of the w; V. and is zero for all other tokens in the vo- cabulary. Intuitively, this means there is only one possible next token given this context, according to the traíning data. As we will show in $4, sparse estimates are more predictive of the actual tokens than non-sparse ones.
Interpolating with neural LMs. co-gram estimates contain zero probabilities, which may lead to infinite perplexity. We do not attempt to compute the perplexity of the co-gram itself. Instead, we interpolate it with neural LMs and show perplexity improvement over the neural LMs alone ($5). The combined model is
P(y xx) = APo x) + (1 A) Pneurat x),
where A E [0, 1] is hyperparameter.
3

---

Published as a conference paper at COLM 2024
Dataset
Hello
world
Byte array
b
Token IDs
0x0C72
Suffix array
Byte array
C3
3A
C4
74
72
0c
27
75
(Littie-endaa))
suffix
Suffix array
0x:06
0xc04
0x00
0x02
Lexicographical
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.
Infini-gram: A Performant Engine for 1-gram/co-ggrm Queries
We train co-gram on modern, trillion-token text corpora. However, it practically infeasible to build n-gram count tables with unbounded и for such massive datasets. In this section, we describe our infini-gram engine that processes N-gram/ /oo-grmm queries efficiently. Infini- gram is powered by data structure called suffix array. We will show how to build this suffix array index and how to perform 1--rrmm te-gramco-grran oo-aaammmmmmmmm inferences with it.
Suffix array. The essence of R-gram and co-gram LMs is counting given r-gram in the training data. As such, we leverage the suffix array data structure, which is originally designed for efficiently counting the number of times given "needle" string (length L) appears as substring of a huge "haystack" string (length N). When the suffix array is built for a haystack string, counting given needle string has time complexity O(L ((L+log log N).
suffix array represents the lexicographical ordering of all suffixes of an array (or a string, which is array of characters). For array of length N, the suffix array contains N unique integers, where the i-th element is the starting position of the suffix ranked i-th among all suffixes. Figure 2 (left) shows the suffix array for a toy string, aabaca.
As shown in Figure (right), we build the suffix array on the byte array of the tokenized dataset (i.e., token array). Documents are separated by the \xfflxff token. In the token array, each consecutive two bytes represent a token ID (assuming that [V] < 26 65536). Given that the dataset has N tokens, the token array has 2N bytes. The suffix array contains N elements, each pointing to a token in the token array by storing its byte offset. Every tokens in the token array appears exactly once in the suffix array. Each pointer can be stored with [log2 (2N) bytes. For corpora with 2B to 500B tokens (which is the range we deal with, after sharding (SA.3)), this is bytes per pointer, and thus the suffix array has 5N bytes. Therefore, the combined size of token array and suffix array (i.e., the infini-gram index) is 7N bytes.
Building the suffix array. Suffix arrays can be built in linear time with respect to the size of the token array (Kärkkäinen et al., 2006). We adapted from the suffix array implementation in Lee et al. (2022) and further optimized it for efficiency. It took us 48 hours to build the suffix array for RedPajama on a single node with 128 CPUs and 1TiB RAM. We have built the suffix arrays for Dolma (3T tokens), RedPajama (1.4T tokens), Pile (380B tokens), and C4 (200B tokens). Since infini-gram indexes are additive (SA.2), together these can be easily combined into a larger index with a total of trillion tokens, and the implicit count table contains at least 2 quadrillion unique n-grams (5A.1).
Inference with the suffix array. Computing the n-gram LM probability involves counting the number of occurrences of a token string, i.e., cnt(x]...x,). By construction, the occurrence positions of strings starting with X1...,, lies in single, consecutive segment in the suffix array. Thus we only need to find the first and last occurrence positions, and the count would be the difference between them. Beyond counting and n-gram co-gram language modeling, infini-gram can also be used to retrieve documents containing an n-gram, or CNF expression with multiple n-grams (SA.4).
--gram/oo-rram
4

---

Published as a conference paper at COLM 2024
During inference, the entire infini-gram index can stay on-disk, which minimizes the compute resources needed (no GPU, and minimal CPU / RAM). In $A.4, we discuss several optimization techniques applied to the inference engine: parallelized shard processing, hinted search, memory pre-fetching, fast effective-n lookup, and amortized query processing. On RadPajama, our most optimized infini-gram engine can count given n-gram with average latency of less than 20 milliseconds. It can compute the probability and next- token distribution in 40 milliseconds for n-gram LMs, and in 200 milliseconds for the oo-grmm. See $A.5 for the full list of supported query types and additional details on latency benchmarking.
Analyzing Human-written and Machine-generated Text using co-gram
In this section, we present some analyses of human-written and machine- text from the perspective of co-gram, mostly focusing on the token-wise agreement between o0-gram's 's prediction and the actual text. In summary, we found that:
1. o0-gram has a fairly high accuracy (47%) when predicting the next token given prefix of a human-written document, and this accuracy is higher when longer suffix of the prompt can be used (i.e., when the effective и is larger);
2. Conventional и-gram LMs (n1 I 5) are insufficient for capturing a long enough context to determine the next token, while our oo-gram method is highly predictive of human- written and machine-generated text;
3. oo-gram has significant potential to complement and improve neural LMs when predict- ing human-written text (which we further investigate in $5);
4. When plotting the agreement level with respect to the suffix length, text generated by neural LMs with nucleus sampling is most similar to human-writter text, among other decoding methods like greedy decoding and temperature sampling. For greedy decoding, the agreement plot suffers from significant fluctuation, which may be rooted in deficiencies in neural LM pretraining and the positional embeddings of Transformers.
oo-gram training data. For analyses in this section, we use a decontaminated version of Pile's training set ("Pile-train") (Gao et al., 2020) training data for the co-gram. We built an infini-gram index on Pile-train using the Llama-2 tokenizer (Touvron et al., 2023b), and yield 360 billion tokens.
Decontamination. It is important that the training data is decontaminated against the evaluation data, because otherwise it is very easy for co-gram to cheat by copying from the very same document in the training data. We run decontamination of Pile-train against its valídation and test sets ("Pile-val" and "Pile-test", which we will use for evaluation below and also in $5), using the method from Groeneveld (2023) that filters out a document has excessive nt-gram overlap with the evaluation data. See SB for more details.
Decontamination non-trivial, and its definition could vary (e-g., when there is an identical sentence, is it contamination, or is it quote that naturally occurs in real test-time scenarios?) Thus we followed the standard best practices for decontamination.
4.1 Humtnnwritten text
Setup. We use Pile-val set as the human-written text. For this analysis, we sampled 50 documents from each domain of Pile-val, and truncated each document 1024 tokens (so the total number of tokens per domain is about 50k). We aggregate results from all domains.
We measure the token-wise agreement between co-gram's prediction and the actual human- written text. Since computing the full next-token distribution (or the argmax of it) in co-gram is relatively slow, we compute the oo-gram probability of the actual next-token, and deem as accurate if this probability is higher than 0.5. (This is a lower-bound of argmax accuracy, though the gap is small.) We further categorize all tokens by their effective n, ie., one plus the length of their prompt's longest suffix that has non-zero count in the training data.
5

---

Published as a conference paper at COLM 2024
S-gram
>-gram
a-gram, on tokens with sparse estimates
1.0
mediare 7.0
1.3
agresmen with s-gram
10c
med 119
1202
median
0.
1001
20k
00L-
-04
-0.4
07 m 0.20
-02
5c
effective
Figure 3: Tosen-wise agreement between human-written text and n-gram n-gram/oo-gram
oo-gram LMs.
On all tokens
tokens with sparse w-gram estimates
1.0
agresment a-gram
agreement with e-gram
0.8
0.6
10
-066
100
0.4
0.4
0.2
0.2
0.0
10a
0.0
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.5
0.8
1.0
Probability assigned Uamo 2-708
Probability assigned Uiam:
Figure 4: Distribution of probabilities assigned by neural LMs to human-written text tokens, and co-gram's 's agreement with these tokens. Takeaway: oo-gram and neural LMs are predictive of actual human text on different tokens, and thus co-gram estimates especially sparse oo-gram estimates- - can be used to complement neural LMs. See Figure for extended results on Llama-2 13B/7B models.
For each category, we visualize the number of such tokens (in gray bars) as well as the agreement level (in green dots) in the middle plot of Figure 3.
Results. Overall, co-gram agrees with the human-written text on 47% of the tokens. We see that co-gram becomes more accurate with the increase of effective when the effective n 2 16, agreement is higher than 75%. Further analysis (Appendix Figure 7) shows that the count of this longest suffix in the training data does not affect agreement substantially.
In the left plot of Figure 3, we show the same analysis for a 5-gram LM trained on the same data, and it has much lower agreement than the oo-gram. 5-gram LMs, which has been used extensively in previous literature (Franz & Brants, 2006; Aiden & Michel, 2011), does not capture long enough context to correctly predict the next token: over 90% tokens in the evaluation data has an effective π of at least 5, and the co-gram analysis shows that the median of effective is 7 (and mean is 9.1).
In the right plot of Figure 3, we show the same analysis for only tokens with a sparse oo-gram estimate, which covers more than 50% of all tokens. The overall agreement is even higher (75%), and when the effective π 2 14, agreement is higher than 80%. This means when the next token unique according to the training data, that unique token is very likely to be the actual token in human-writteer text.
Qualitatively, we found that co-gram is often good at completing multi-token words (e.g., hippopotamus, correctly predicted tokens are underlined), common phrases (e.g., born in), and entity names (e.g., educated at Trinity College). oo-gram is not very good at recalling factual knowledge (e.g., predicting the first token of an entity name), likely due to insufficient contextualization.
oo-gram can shine where neural LMs fail. In Figure 4, we plot the distribution of probabil- ities assigned by the Llama-2 70B/13B/7B models (Touvron et al., 2023b) to the actual tokens in human-written text, and the human cuiman-oo-grane oo-gram agreement for tokens in each probability bucket. (The higher the assigned probability, the higher agreement Llama-2 has with the actual tokens.) We observe positive, yet imperfect, correlation between neural LMs and oo-gram regarding their agreement with the actual text. In particular, when the neural LM performance is very poor (left side of the histogram), oo-gram still gives non-trivial agree- ment of above 20%; if only considering tokens with sparse co-gram estimates, the agreement is as high as 50%. This indicates huge potential of complementing and improving the

---

Published as a conference paper at COLM 2024
Uama-2-70b, greedy
Uama-2-70b, p-0.8
Llama-2-70b. t-1.0
m63n-30
agreeement with m-gramm
100-
306
bill
mc33-B.0
agreameee m-rram
-08
234-
20k
20k
Count
25k
22L=
13k
222 -5..0.
10k
54
54
56
effective
Lama-2-130. greedy
Llama-2-7b, greedy
GPT-j-5D, greedy
agreement with graaa
agreen with s--gamm
252-
25k-
25k-
23k-
20k
count
15k
with
15k
0.46
-0.6
countt
200 0.41
10t
108
30k-
-02
04
offective
effective
effactive
Figure 5: Token-wise agreement between machine-generated text and oo-gram. All tokens
are considered. See Figure for results on GPT-Neo models.
performance of neural LMs with co-gram for predicting human-written text, which we further investigate in $5.
4.2 Machine-generated text
Setup. Similar to the analysis with human-written text, we sampled 50 documents from each domain of Pile-val. We use the first 50 tokens of each document to prompt neural LMs to generate continuation. Generation continues up to the original length of the document, or when an [FOS] token is generated. We experiment with three decoding methods: greedy decoding, temperature sampling, and nucleus sampling (Holtzman al., 2019). The neural LMs are Llama-2 /t////BB/B GPTT- 6B (Wang & Komatsuzaki, 2021), and GPT-Neo 2.7B/ 1/3B// /12MM (Gao et al., 2020). The tokenizer GPT-Neo/] is different from Llama-2, we built separate version of infini-gram index for Pile-train based on the GPT-Neo/J tokenizer.
Impact of decoding method. The top row of Figure 5 shows results of the three decoding method on the same neural LM Llama-2 70B. In general, increasing stochasticity shifts the effective n to the smaller side, and also decreases the agreement level. Nucleus sampling has the most similar distribution of effective compared to human-written text (Figure 3, middle plot), which is probably why nucleus sampling is usually preferred in text generation. Greedy decoding has even higher effective и than human-written text, which implies that greedy decoding could lead to over-memorization of training data as well as lack of diversity.
Impact of model size. The bottom row of Figure 5 shows the same analysis for different sizes of neural LM under greedy decoding. In general, increasing model size slightly increases the effective ı1 and also increases the agreement level. This indicates that larger models memorizes more from the training data, and are also more inclined to copy verbatim. The agreement level of GITT-Neo/] models higher than Llama-2 models, probably because GPT-Neo/] are trained on the same data as the oo-gram (i.e., Pile-train). Overall, text generated by these neural LMs has similar agreement level with co-gram as human text.
One very curious phenomenon is that, as effective n increases, the agreement level fluctuates greatly in greedy decoding (but not nucleus or temperature sampling, where agreement level almost increases monotonically). Such fluctuation is even more rapid for smaller models (Llama-2 13B/7B and GPT-Neo/] models), and for Llama-2 7B the fluctuation is even periodic (rapidly dropping at effective = 20, 24, 28, 32; this is statistically significant, two-proportion z-test gives p-value of < 10.99). We suspect that this may be caused by the application of positional embeddings when pretraining these Transformer-ban models, and we welcome further investigation from the community.
7

---

Published as a conference paper at COLM 2024
Validation
Test
Neural LM
Size
Reference Data
Neural
corgram
Neural
corgram
GPT-2
117M
Pile-train
22.82
13.71
(12%)
22.86 86
13.58
(42%)
GPT-2
345M
Pile-train
16.45
11.22
(34%)
16.69
11.18
(89%)
GPT-2
774M
Pile-train
15.35
10.39
(36%)
15.40
10.33
(39%)
GPT-2
1.6B
Pile-train
14.42
9.93
(38%)
14.61
9.93
(5P%)
GPT-Neo
125M
Pile-train
13.50
10.76
14.08
10.79
(25%)
GPT-Nco
1.3B
Pile-train
(13%)
7.36
(16%
GPT-Neo
2.7B
Pile-train
7.46
(12%)
7.77
6.76
(15%
GPT-J
6.7B
Pile-train
6.25
5.75
(10%)
6.51
5.85
(12%)
Llama-2
7B
Pile-train
5.69
(14%)
5.83
5.06
(16%)
Llama-2
13B
Pile-train
5.30
4.75
(13%)
5,43
4.76
(15%)
Llama-2
70B
Pile-train
4.59
4.21
(11%)
4.65
4.20
(12%)
Llama-2
7B
Pile-train RedPajama
5.69
(22%)
5,83
4.66
(24%)
lama-2
13B
Pile-train RedPajama
5.30
4.41
(21%))
5.43
4,42
(23%)
Llama-2
70B
Pile-train RedPPajama
4.59
3.96
(18%)
4.65
3.95
(19%)
Table 1: Perplexity (lower better) on Pile's validation and test sets. Numbers in parentheses are the relative perplexity improvement. The first eight rows share the same tokenizer, and the last six rows share the same tokenizer.
Improving Neural LMs with the co-gram
The results in $4 motivate us to combine neural LMs and oo-gram ($2) to yield better language models. this section, we will show strong experimental results of the combined model. In 54 we found that the oo-gram estimate has higher agreement with human-written text when it is sparse. Therefore, we use two separate interpolation hyperparameters: Å₁ for sparse and A2 for non-sparse co-gram estimates. These hyperparameters are tuned on the validation set to minimize the perplexity the combined model.
5.1 Experimental setup
Evaluation and metric. We measure the perplexity of each model on Pile's validation and test sets, as well as the relative improvement of perplexity between models. To show generalization, we also evaluate on time-shifted data (i.e,, data created after the cutoff date of the oo-gram training data). The relative improvement of model M against model Mo PPL(M)-1 is defined as (1 PPL(M,)-1) x 100%, which is the percentage of perplexity gap closed towards perfect language modeling (i.e., PPL = 1). Additional details on evaluation data processing in SD.1.
Reference data. To reduce confusion, in this section will use reference data to refer to the training data of the co-gram. In addition to Pile's training set that we used in the previous analyses (54), also consider RedPajama (Together, 2023) reference data. The decontaminated Pile-train and Redpajama have 360 billion and 1.4 trillion tokens, respectively, summing up to 1.8 trillion tokens (based on the Llama-2 tokenizer). We later perform ablations on varying sizes and domains of the reference data.
Neural LMs. We use a range of large, competitive neural LMs, both as baselines and as models to interpolate with the co-gram. In total, 14 models are considered: GPT-2 TMMM//355/7744/1..
(Radford et al., 2019), GPT-Neo 225M/1.3B/22 7B//1BB/ /OBB and SILO PD/ PDPPDPPS /DDSW/DW///// /PDSWBY (Min et al., 2023a). See $D.1 for additional details about these models and their training data.
GPT-J-6B, Llama-
Tokenizers. Among these models, GPT-2, GPT-Neo and GPT-J share the same tokenizer, but Llama-2 and SILO use different tokenizers. We therefore built three versions the infini-gram index Pile-train and RedPajama, one for each tokenizer. Due to the tokenizer variation, the perplexity of GPT-2, GPT-Neo and GPT-J are comparable to each other, but perplexity of 2lama-2 and SILO are not comparable to them nor to each other.
8

---

Published as a conference paper at COLM 2024
Validation
Test
Neural LM
Neural
co-gram
RNN-LM + RIC-LM Neural co-gram +NN--MM + RIC-LM
Eval data: Wikipedia
Silo PD
26.60
15.30
(43%)
20.62
27.91
28.42
14.44 (51%)
Silo PDSW
18.93
12.36
(36%)
14.10
18.90
20.02
11.84 (1%%
14.5
19.4
Silo PDSWBY
10.66
8.77 (19%)
10.14
10.87
10.76
8.41 (24%)
Pythia
9.00
8.50
8.84
9.1
Eval data: Enron Emails
Silo PD
19.56
6.31
(70%)
8.56
15.45
15.71
4.85
Silo PDSW
14.66
5.58 (6%%
6.70
10.80
11.23
4.35 (66%)
5.9
9.9
Silo PDSWBY
14.67
5.61
(6%%
7:24
10.91
11.52
4.44 (66%))
Pythia
7.577
4.99
6.16
6.9
Eval data: NIH ExPorters
Silo PD
27.46
16.26
(41%)
19.27
25.51
27. 94
16.00 (4%)
Silo PDSW
19.35
12.70
(38%)
14.95
18.35
19.12
12.39
(37%)
15.0
18.5
Silo PDSWBY
15.01
10.62
(50%)
12.33
14.29
14.81
10.33
Pythia
11.20
11.20
10.83
11.1
Table 2: Perplexity (the lower the better) on the validation and the test catasets of the Wikipedia, Enron Emails, and NIH ExPorters of the Pile. All neural models are 1.3B models, and the reference data is always the Pile. indicates in-domain; indicates out-of-domain; indicates out-of-domain but has relevant data in-domain, all with respect to the training data of the neural LM. t: Results retrived from Min et al. (2023a), which use much smaller reference data: 45-million to 1 1.2-billion tokens, compared to our 360-billion tokens.
5.2 Results
Experimental results with GPT-2, GPT-Neo/J, and Llama-2 on Pile's evaluation sets are shown in Table 1. Results time-shifted data can be found in SD.2, and we show the impact the size and domain of reference data in SD.3.
Interpolating with co-gram greatly and consistently improves the perplexity of neural LMs. The magnitude of improvement trends smaller as the neural LM size grows within the same family, while the largest models can still benefit lot from our method (e.g., Pile-train alone improves Llama-2 70B by 12%).
However, this trend does not hold across different families of LMs. For example, co-gram can improve GPT-2 1.6B by 34%, but only improves a smaller model, GPT-Neo 1.3B, by 16%. This may be because GPT-Neo/] models trained precisely Pile, while GPT-2 models are not. o0-gram works better when the reference data distribution differs from, or complements, the pretraining data distribution, which emphasizes the importance of data diversity. Meanwhile, the fact that co-gram also improves neural LMs already pretrained on its reference data shows that there is consistent advantage in introducing oo-gram.
On the choice of co-gram reference data, the union of Pile-train and RedPajama yields larger improvements on the Llama-2 models than Pile-train alone. The combination of Llama-2 13B and co-gram with Pile-train + RedPajama outperforms Llama-2 70B, and interpolating with co-gram pushes the perplexity of Llama-2 70B below 4.0.
When the neural LM is SILO (which is trained on permissive-license data only and thus has less training data), adding the co-gram component is more helpful when SILÓ is trained on more restrictive data (i.e., PD PDSW > PDSWBY), The usage of co-gram can be precisely traced back to the contributing document(s) the reference data, which is in-line with the philosophy of SILO: to allow crediting the source data when using them for language modeling. When compared to the existing vetrieval-augmentaa ie., KNN-LM and RIC-LM, co-gram yields better improvement in perplexity. Therefore, co-gram can serve as a better alternative as the retrieval-augmentatie method for SILO.
methods used by SILO,
A note text generation. While co-gram can be interpolated with neural LMs and greatly improve their perplexity, our preliminary experiments show that such method might not be helpful, and even harmful, to open-ended text generation tasks. During generation,

---

Published as a conference paper at COLM 2024
oo-gram can make odd mistakes (e.g., predicting totally irrelevant tokens) which makes the model to digress. Thus this combined model is not ready to replace neural LMs. Additional investigation is required to make co-gram best contribute to text generation.
Related Work
We discuss closely related work here. See ŞE for extended discussion, and Table for comparison with other n--ram models and nonparametric language models.
#-gram language models. n--ram has been one of the most classical language modeling methods since the inception of natural language processing (Jurafsky & Martin, 2000). People have been pushing the limits of it-rram LMs by scaling up its training data. To date, the largest u--rram table (Brants et al., 2007) counts 5-grams in a corpus of 2 trillion tokens.
While n-gram LMs are currently largely surpassed by neural LMs, there has been recent work that revisit n-grams and n-gram LMs. Mikolov & Zweig (2012) finds that interpolating with 5-gram Kneser-Ney model improves the perplexity of RNN models, whereas Khandelwal et al. (2020) finds that interpolating u-gram models with Transformers does not improve perplexity substantially. et al. (2022) finds that the n--ram model is as competitive small neural LM, and training neural model to be complementary to the æ-gram model and using both at inference time outperforms the neural-only L.M However, both use limited reference data (101M tokens) and compare with small neural LMs (117-250M parameters). Some prior work has found value in scaling up the n-gram training data (Allamanis & Sutton, 2013).
Our work scales up the training data of n-gram LMs trillions of tokens. With the addition of scaling up the value of in the n-gram, our model can significantly improve state-of-the, art neural models as large as 70B.
Unbounded n-grams, suffix arrays, suffix trees. Previous work has explored using suffix- based data structures to enable n-gram queries with unbounded with limited scale of the training data. Stehouwer & van Zaanen (2010) proposes to use suffix arrays for oo-gram, and yet their formulation does not yield proper probability distributions and, consequently, a language model. Kennington et al. (2012) proposes to use suffix trees for the same purpose, and yet the storage overhead of suffix trees very high such that it hinders scaling, which may be mitigated with highly intricate compression techniques (Shareghi et al., 2015). Among the three aforementioned papers, only the third evaluates on the general language modeling task, and the perplexity numbers are too high to be practically useful. Our training data is 500x larger than the largest one in these previous work.
Nonparametric language models. Nonparametric LMs refer to LMs whose complexity is not bounded priori, because the complexity (Khandelwal et al., 2020; Borgeaud et al., 2022; Asai et al., 2023). The co-gram LM is one instance of nonparametric LMs, and its simplicity makes it possible to significantly scale the reference data with modest resources (53). To the best of our knowledge, our oo-gram LM is the largest in both the size of the reference data (5 trillion tokens) and the size of the base neural LM (70B).
change according to the reference data
7 Conclusion
In this paper, we modernized the classical и-gram language model by scaling it up to trillion tokens and extending to unbounded n. We presented the infini-gram engine that performs efficient training and inference under this extreme setup. We also proposed the oo-gram language model, powered by the infini-gram engine, and showed that it can offer novel insights into human-written and machine-generate text and can improve existing neural language models.
10

---

Published as a conference paper at COLM 2024
Acknowledgments
We would like to thank Zexuan Zhong, Mike Lewis, Yanai Elazar, Will Merrill, Tim Dettmers, Ximing Lu, Alisa Liu, Weijia Shi, Xiaochuang Han, members of the H2lab, and Ziqi Ma for their invaluable feedback.
References
Erez Lieberman Aiden and Jean-Baptiste Michel. Quantitative analysis of culture using mil- 182, 2011. URL https: //api. semanticscholar
lions of digitized books. Science, 331:176 -
org/CorpusID: 40104730.
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. www.nticschollaattt.....etcataae org. hhtg///orpsID:::: 1 1857729.
Akari Asai, Sewon Min, Zexuan Zhong, and Danqi Chen. Acl 2023 tutorial: Retrieval-based language models and applications. ACL 2023, 2023.
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: / /appi. semant www.holarccc....cccccc.ccaar wwwooollrrrrroooooooooooooo Orgg/CorpuIID : 268248911.
Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. In Proceedings of the International Conference on Learning Representations, 2019.
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 Machine Learning, 2022.
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./ppp....// mnmaantisccoolar www.org///oooo wwtgg//CrousID.... 633992.
Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, L. Sifre, and John M. Jumper. Accelerating large language model decoding with speculative sam- pling. ArXiv, abs/2302.00313, 2023. URL https://aapp httpss///app.ssmmtiiccchtieeeeee semanticscoolar org Crg/CCrp 256503945.
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 Natural Language Processing, 2021. URL https://appi. semanticscholar
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 's in my big data? ArXiv, abs/2310.20707, 2023.
URL http:://///i..imtttt//m/// L
www.eteeeiiiie commanticscholar..om org 15:
Alex Franz and Thorsten Brants. All our n-gram are belong to you. Google Machine Translation Team, 20, 2006. URL https://blog. research. reeseacch.oogge/2886666666 goggge/200///8////////
parpuuu---gra--ar---eellooooo homm......
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. ar preprint arXio:2101.00027, 2020.
Xinyang Geng and Hao Liu. Openllama: An open reproduction of Ilama, May 2023. URL https://githhu. com/ ctmm:pppennnmmrreeercccoco....o
Dirk Groeneveld. The big friendly filter. https: btops://gitte https://github..cm/allllea 2023 2023.
11

---

Published as a conference paper at COLM 2024
Dirk Groeneveld, Iz Beltagy, Pete Walsh, Akshita Bhagia, Rodney Kinney, Oyvind Tafjord, Ananya Harsh Jha, Hamish Ivison, lan Magmusson, Yizhong Wang, Shane Arora, David Atkinson, Russell Authur, Khyathi Chandu, Arman Yuling Gu, Jack Hessel, Tushar Khot, William Merrill, Jacob Morrison, Niklas Muen- nighoff, Aakanksha Naik, Crystal Nam, Matthew E. Peters, Valentina Pyatkin, Abhilasha Ravichander, Dustin Schwenk, Saurabh Shah, Will Smith, Nishant Subramani, Mitchell Wortsman, Pradeep Dasigi, Nathan Lambert, Kyle Richardson, Jesse Dodge, Kyle Lo, Luca Soldaini, Noah A. Smith, and Hannaneh Hajishirzi. Olmo: Accelerating the science of language models. Preprint, 2024.
Dumas, Yanai Elazar,
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.
Zhenyu He, Zexuan Zhong, Tianle Cai, Jason D Lee, and Di He. Rest: Retrieval-based spec- ulative decoding. 2023. URL h semant csscholar wwg//orppss[/// 2651
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. ArXiv, abs/1904.09751, 2019, URL htttps://ai.. semanticscholar, org/CorpusID: 127986954.
Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseíni, Fabio Petroni, Timo Schick, Jane Dwivedi-Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave. Few-shot learning with retrieval augmented language models. arXiv preprint ar Xriv:22088.0399, 2022.
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 patps://apt semant www.hlllrc......ccooooccco.cc..c org/CorpusID: 60691216.
Juha Kärkkäinen, Peter Sanders, and Stefan Burkhardt. Linear work suffix array construction. J. ACM, 33:918-936, 2006. URL https://api. coomanticscooll.. wwrg/CorpusID. : 12825385.
Slava M. Katz. Estimation of probabilities from sparse data for the language model compo- nent of speech recognizer. IEEE Trans. Acoust. Speech Signal Process., 35:400-401, 1987.
URL https://api.
6555412.
Casey Redd Kennington, Martin Kay, and Annemarie Friedrich. Suffix trees as language models. In International Conference Language Resources and Evaluation, 2012. URL
https://api. semanticscholar org/CorpusID:
Urvashi Khandelwal, Omer Levy, Dan Juraísky, Luke Zettlemoyer, and Mike Lewis. Gener- alization through memorization: Nearest neighbor language models. In Proceedings of the International Conference on Learning Representations, 2020.
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.
Katherine Lee, Daphne Ippolito, Andrew Nystrom, Chiyuan Zhang, Douglas Eck, Chris Burh, and Nicholas Carlini. Deduplicating training data makes language models better. In Proceedings of the Association for Computational Linguistics, 2022.
Huayang Li, Deng Cai, Jin Xu, and Taro Watanabe. Residual learning of neural text genera- tion with n-gram language model. In Findings of the Association for Computational Linguis- fics: EMNLP 2022, 2022. URL https: / httpss///claathhllggo.o/ org/2022. indings-ennlp. 109.
Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Hannaneh Hajishirzi, and Daniel Khashabi. When not to trust language models: Investigating effectiveness of parametric and mar-mmmmet memories. In Anmual Meeting of the Association for Computational Linguistics, 2022. URL https: //api. wwwanticscholaatee htt.oo/a.....r/orrroor/2252//2/0
12

---

Published as a conference paper at COLM 2024
Marc Marone and Benjamin Van Durme. Data portraits: Recording foundation model training data. ArXio, abs/2303.03919, 2023, URL https://app httpss//aapp.smmattsssssseeeee semanticscholar.orrrr Lorpus1D:257378087.
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. semanti wttpscchhhla..ooooorrrreereeeeee org/CorpusID: 1388176.
Sewon Min, Suchin Gururangan, Eric Wallace, Hannaneh Hajishirzi, Noah Smith, and Luke Zettlemoyer. SILO language models: Isolating legal risk in nonparametric datastore. arv preprint wwxi::2308.045500 2023a. URL htttt:://aaaiiii http://akivv.orgbbb//////// 04430..
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.
Daichi Mochihashi and Eicchiro Sumita. The infinite markov model. In Neural Information Processing Systems, 2007. URL https: httt:s://ap..emmnticccooooo//// wttpsschhooaa..oooorroppppeeeeep org/CCrpusID: 1279894.
Fabio Petroni, Tim Rocktäschel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, Alexan- der H. Miller, and Sebastian Riedel. Language models as knowledge bases? ArXiv, abs/1109.01066, 2019, URL https: stm.aaiiiismmmtiiicccocoolaaaar htt.:/oo....orrrrrruuui02222233.
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.. semanticscholar org/ Corp//orrisID:::: 2tte//oopusI:::22219822 257219882.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Edward Raff, William Fleming, Richard Zak, H. Anderson, Bill Finlayson, Charles K. Nicholas, and Mark McLean. Kilograms: Very large n-grams for malware classifica- tion. ArXiv, abs/1198.00020 2019. URL https://app www.sseeassnioeeeeee iichannacccooar....o. org/CorpusID: 199064443.
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. Mach. Learn. Res., 21:140:1-110:67, 2019. URL https://api. www.nticschollla..... www.ccccoooooooo//orrrrt.a... orgg/ooppsII::244333 204.330000
Ehsan Shareghi, Matthias Petri, Gholamreza Haffari, and Trevor Cohn. Compact, effi- cient and unlimited capacity: Language modeling with compressed suffix trees. In Conference Empirical Methods in Natural Language Processing, 2015. URL https: //aaiitseanticssei Stseaanniissscoll...orrr/rrrlrss 225428.
Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih. REPLUG: Retrieval-augmented black-box language mod- els. ar Xiv preprint ar Ntt::231.116552 2023.
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 Pete Walsh, Hannaneh Hajishirzi, Noah A. Smith, Luke Zettlemoyer, Iz Beltagy, Dirk Groeneveld, Jesse Dodge, and Kyle Lo. Dolma: An Open Corpus of 3 Trillion Tokens for Language Model Pretraining Research. Technical report, Allen Institute for AI, 2023. Released under ImpACT' License as Medium Risk artifact, https: / //gi thub. com/ allenaillaaaaaaaaaaaaaaaaiaaaall eeeaindolaaaa dolma.
Herman Stehouwer and Menno van Zaanen. Using suffix arrays as language models: Scaling the n-gram. 2010. URL httph::t///tt http:::://app.smannisssssseeoeee semanticscholar wtwpttiicccooaaooooooooooee 18379944.
Together. RedPajama: An open source recipe to reproduce LLaMA training dataset, 2023. URL https: //gi thub. www.//oogeeerrcootteooooo wwwpuuteeeeeeeeaaeeeeeeee RedPajjam--Dar Data.
13

---

Published as a conference paper at COLM 2024
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. ar arviv preprint arXi::2302. 13977,, 2023a.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, al. Llama Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09228, 2023b.
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: semanticcchollarr org/CorpusID: 257766452.
Ben Wang and Aran Komatsuzaki. GPT-J-6B: A 6 Billion Parameter Autoregressive Lan- guage Model. https://gi http:://ttt....cooo//o/ooooo///t
jax, May 2021.
Frank 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 D 11 199892.
Zexuan Zhong, Tao Lei, and Danqi Chen. Training language models with memory augmen- tation. In Proceedings of Empirical Methods in Natural Language Processing, 2022.
14

---

Published as a conference paper at COLM 2024
A Additional Details on the Infini-gram Engine
A.1 What is the size of the r-gram count table implied by an infini-gram index?
The size of an n-gram LM is often measured by the number of unique n-grams indexed, each associated with its count in the dataset. This size is easy to obtain when indexing is done as the classical n--ram count tables, but non-trivial to compute for infini-gram.
If we consider all possible values of in the n-gram, then dataset with N tokens would contain about N 1r-grmms, and since most of these n-grams are long and thus very likely to be distinct, there would be about N2 unique n-grams, Since we index N = 5 trillion tokens, the size of the n-gram count table implied by our infini-gram index would be approximately 1.2 x 1025, or equivalently, 20 mol (using NA- 6.02 1023/mol) /mol).
However, the document separator is meaningless and should not be part of the n-grams, and we should probably only count ıt-grams within the document boundaries. There are N x 10 tokens and D = 6 10 documents, and on average each documents have 857 tokens. Using the Cauchy-Sch inequality, we have the total number of 1t-grams
Σト
N
N2 = 2 x 1015
d
D
2D
Therefore, there are at least 2 quadrillion unique n-grams in the count table implied by infini-gram.
A.2 Additional details on the infini-gram index
Infini-gram indexes are additive and subtractive. If we have two or more indexes built on disjoint datasets (with the same tokenizer), we can easily combine them into single index by adding up the n-gram counts from each index. This feature is useful in the sharding
RedPajama Dataset (1.4 Trillion Tokens, 2.8 TB)
0e0000000000
tuught Morvig's Intelligance, Modorn Syprosxd
io...
Oal 7544arr
All abous ArtiBoolal Intelllgenne, Auturtstie AnAl about ATt.nggllosttooooccooooo of
Artidicaal Intetliganoe,
0x330
Apple Toouses On ArtiBolaa Intelllgenne,, Apolc Theees, Rerponatie Al Maca Goal...
experacce Artidoial Intellignnoe, Modere Aupeoai IaDon't stared
0N0000036000
0x942997 cus
0x943997466
0x9439944AA
5H0000080202
Sx3A08AG3008
0x4012108085
5x18GBOCDAA66
0x17934APPGE
ORTROFD-164OA
matchings Artifieaa Intelligenoe, Modern
Suffix Array (1.4 Trillion Entries, 7.0 TB)
Figure 6: n--ramm/ /o--ramm queries on a training data are supported by an associated suffix array. Both the training data and the suffix array are stored on-disk as regular files. Contents on the white strips are file data, and redsesses above the strips are byte offsets. Querying for a particular n-gram returns a consecutive segment of the suffix array, where each element pointer into the training data where the n--ram appears. E.g., in the trillion-token training data, Artificial Intelligence, A Modern appears 42 times, and in all cases the following token is Approach.
15

---

Published as a conference paper at COLM 2024
technique that we discuss in $A.3 and $A.4. Similarly, if we have built indexes big dataset and a subset of it, we can easily obtain an index of their difference by taking the difference of ---gamm counts. Compared to having single index, both operations incur some additional inference operations (which can be parallelized to mitigate latency overhead), but they would spare from re-indexing the union or difference sets from scratch.
Document offsets and metadata. To enable efficient document retrieval, the infini-gram index stores additional data about documents, A document offset file stores the byte offset of each document in the tokenized dataset, and its format is similar to the suffix array. A document metadata file stores comma-separater string for each document that contains its metadata (e.g., document ID, source, URL), and document metadata offset file stores the byte offset of each document's 's metadata in the document metadata file. All the above files are negligible in size compared to the suffix array, because there are far less documents than the total number of tokens.
A.3 Additional details on building the suffix array
Sharding. Building the suffix array requires heavy random access to the byte array, and thus the entire byte array must be kept in RAM so that the building time is reasonable. However, the byte array may be too large fit into RAM. In such cases, we shard the byte array into multiple shards, and build suffix array for each shard. Sharding would induce additional inference latency, which we discuss and mitigate below ($A.4).
A.4 Additional details on inference with the infini-gram index
Both the first and last occurrence positions can be found with binary search, with time complexity O( log N) and Olog N) random array accesses. The two binary searches can be parallelized, reducing the latency by roughly 2x. The impact of query length is negligible, because computers usually fetch memory in pages of 4K bytes, and string comparison is much faster than page fetching. Therefore, when we analyze time complexity below, we refer to the number of random array accesses.
Finding occurrence positions and documents. n-gram counting with suffix arrays has by-product: we also get know all positions where the n-gram appears in the training data, for free. This position information is implicitly contained in the suffix array segment we obtained during counting, and to retrieve the original documents where the n-gram appears, all we need to do is to follow each pointer within this segment back into the tokenized dataset, and find the starting and ending position of the enclosing document by performing binary search on the document offset index. (Note that if we don't 't have the document offset index, the latency of document search cannot be bounded because we would need to expand the pointer in both directions in the tokenized dataset until hitting the document separator. In practice, we see documents as large as 20M tokens.)
Impact of sharding. When the suffix arrays are built on sharded byte arrays, we can simply perform counting on each individual shard and accumulate the counts across all shards. The latency is proportional to the number of shards: time complexity would become O(S log N). The processing of different shards can be parallelized, reducing the time complexity back to O(log N).
Speeding up n-gram computation by re-using previous search results. On the suffix array, the segment for x,..Xpp must be a sub-segment of that for X1...X,-1- Therefore, when computing the 1-gram probability (x x1..xx=1),, we can first count -1 and then when counting xq,..Xn, we only need to search for the first and last occurrence positions within the segment of xn...xn, which reduces the latency by at most 2x.
On-disk search. The byte array and suffix array may be too large to fit into RAM, so in practice, we keep them on disk and read them as memory-mapped files. However, this creates significant latency as the binary search requires random access to the byte array and suffix array. To mitigate this, we implemented memory pre-fetching method that informs the system of the array offsets we will likely be reading in the near future. Pre-fetching reduces average latency by roughly 5x
16

---

Published as a conference paper at COLM 2024
Reference Data (+)
Pile-train
RPJ
Time Complexity
= 0.36T N = 1.4T
(measured by number
Query Type (1)
of random disk accesses)
1. Counting an R-gram
Ollog N)
(11 =
7 ms
9 ms
(n = 2)
13 ms
20 ms
(n
14 ms
19 ms
10)
13
18
(1 100)
13 ms
19 ms
(12 1000)
14 ms
19 ms
2. Computing a token probability from x-gram LM (t 5)
19 ms
30 ms
O(log N)
3. Computing full next-token distribution from n-gram LM
31
39
OoV log
4. Computing token probability from oo-gram LM on consecutive tokens
90 ms
135 ms
O[log L log N)
12 ms
20 ms
Ollog N)
5. Computing full next-token distribution from oo-gram LM
88 ms
180 ms
O + v) log N)
Table 3: Inference-time latency of infini-gram on different types of queries. Average latency per query is reported. Benchmarked with inference engine written in C++ (with parallelized shard processing) and running on a single, 8-core CPU node. Notations for time complexity: N number of tokens in the reference data; S number of shards for the suffix array; L number of tokens in the query document; V = vocabulary size.
Speeding up co-gram computation. To compute the oo-gram probability, we need count the occurrence of each suffix x/-n=1...;, up to the maximum so that the suffix still meets the sufficient appearance requirement (we denote this maximum n as L). This means O(L) counting operations, and the time complexity for each co-gram computation is O(L log N). However, a simple binary-lifting binary-search algorithm for searching L can reduce the number of counting operations to Ollog L), and thus the time complexity for each co-gram computation becomes O(log L- log N).
Speeding up dense co-gram computation. During evaluation, we need to compute the co- gram probability of each token in the test document. We can save computation by observing that the effective n for one token is at most one token longer than that for the previous token. This brings the amortized time complexity for evaluating each token down to O(log N).
A.5 Supported query types and latency benchmarking
Infini-gram supports the following types of n-gram/co-gram queries:
1. Counting an n-gram (Count);
2. Computing a token probability from n-gram LM (with given n, no backoff) (NGRAMPROB);
3. Computing the full next-token distribution from n-gram LM (NGRAMDIST);
4. Computing a token probability from o--gram LM (INFGRAMPROB).
5. Computing the full next-token distribution from co-gram LM (INFGRAMDIST);
6. Returning documents containing an n-gram, or a CNF logical expression of n--rrmm terms, connected with AND's and/or or OR's (e.g., (natural language processing OR artificial intelligence) AND (deep learning OR machine learning)) (SEARCHDoc).
We benchmark the latency of infini-gram on different types of n-gram and co-gram queries, and show results in Table During inference, the training data and the suffix array are stored on an SSD. For each type of query, the benchmarking is conducted on 1,000 tokens randomly and independently sampled from Pile's validation data (except for the task "computing token probability from co-gram LM on consecutive tokens", where sampled 10 documents and processed 1000 consecutive tokens each document).
All types of queries demonstrate sub-second latency the trillion-token training data. Computing a token probability from the oo-gram with RedPajama takes merely 135 millisec- onds. Furthermore, our implementation supports counting the occurrence of an n-gram
17

---

Published as a conference paper at COLM 2024
with arbitrarily large with roughly constant latency at 20 milliseconds (we experimentally validated up to и 1000). Decoding requires computing the full next-token distribution and is thus slightly slower: 39 milliseconds per token with n-gram LMs and 180 milliseconds per token with oo-gram.
B Decontamination of Reference Data
To properly evaluate the effectiveness of co-gram LM on Pile's evaluation sets, we per- formed data decontamination on the Pile's training set and RedPajama before using them as reference data for the c-gram LM. We run the Big Friendly Filter (BFF)* (Groeneveld, 2023) on Pile's training set and RedPajama, filtering out documents with too much n-gram overlap with Pile's evaluation sets. Table 4 reports the statistics of decontamination.
When using BEF, we always remove whole documents, instead of by paragraphs. Following the default settings, we consider и-grams where и = 13, and discard the document if at least 80% of its rt-grmm are present in the evaluation set. For Pile's training set, we lowercase all documents to capture more potential contaminations.
PILE (TRAIN)
Ardv
2377741
1089
BookCorpus2
25355
Books3
277655
99
DM Mathematics
1918535
0
0%
REDPAJAMA
Enron Emails
9261.32
18236
2%
EuroParl
131723
21
Subset
Total docs
Fillered docs
Ratio filtered
FreeLaw
5069088
11821
0.2%
arxiv
book
1558306
205744
711
213
0.01%
0.3%
Gutenberg (PG-19)
Github
18044218
66981
961726
70
5,3%
0.1%
common
github
of
364868892
476276019
28793312
614259
58195
2%
0.01%
OpenSubtilles
NIH ExPorter
HackerNews
OpenWebText2
32333654
1571968
1777926
632485
136914
3739
5734
14
0.2%
0.4%
0.9%
stackexchange
29825086
40086
0.01%
PhilPapers
63875
2324
0.4%
wikipedia
29834171
21973
0.07%
Pile-CC
19928
Total
981361530
730437
0.08%
PubMed Abstracts
29329202
2312
PubMed Central
5679903
4230
0.1%
StackFxchange
USPTO Backgrounds
11123325
80088
0.7%
Ubuntu IRC
20067
Wikipedia
16939503
YoutubeSubiitles
328030
871
0.3%
Total
210607728
1296376
0.6%
Table 4: Statistics of de-contamination in RedPajama (left) and Pile's training set (right).
C Additional Analysis
Figure 7 is extension to the middle plot of Figure 3, and shows more fine-grained analysis of the token-wise agreement between human-written text and co-gram. Figure extends Figure 4 with results Llama-2-13b/71 Figure 9 extends Figure 5 with results GPT-Neo models.
D Additional Experiments on Improving Neural LMs with oo-gram
D.1 Additional details experimental setup
Evaluation data processing. We split each document in the evaluation data into batches with maximum sequence length of 1024 and sliding window of 512, setup that is standard in prior language modeling literature (Baevski & Auli, 2019; Khandelwal et al., 2020).
"httts::/ggttiee http://gttuuu.cccmaaleaaaaaa////
18

---

Published as a conference paper at COLM 2024
10*
10a
10a
freq
16
effective n
1
Figure Token-wise agreement between human- generated text and co-gram, broken down by "effective n and frequency of the corresponding longest suffix in the reference data. The height of each bar represents token count, and the color represents agreement (red is 0.0, green is 1.0).
tokens
On tokens with sparse =-gram estimates
agieammnt win --ram
2g agieammnnt WBB -gaam
0.0
0.0
count
count
0.6
0.2
0.2
Probability assigned by Llarna-2-13B
Probability assigned by Llama-2-138
On all takens
On tokens with sparse =-gram estimates
Sgnsmmmnt with -gra
sgnsemmnt with -9mm
count
0.6
count
0.6
0.2
0.2
0.0
0.0
Probability assigned by Llama-2-76
Probability assigned by Llama-2-76
Figure Continuation of Figure 4, with results on Llama-2-13b/70
GPT-Neo-2.70, greedy
GPT-Neo-1.33 1.3b, greedy
GPT-Neo-1222 -15me. greedy
314
1.4
304
1.0
30k
megaan-2
maan-33
gram
agreement with gmmm
77k
count
15k
0.48
15k
201 0.46
-0
count
35k
-0x
agreement
106
06
30
02
0.0
offective
offective
offective
Figure 9: Continuation of Figure with results GPT-Neo models. Token-wise agreement between machine-generanl text and co-gram. All tokens are considered.
Neural LMs.
Below are additional details about the families of neural LMs
19

---

Published as a conference paper at COLM 2024
Eval Data (Wikipedia)
simple interpolation w/ Random Forest
Neural
+ co-gram
Neural + co-gram
April 2023
5.64 5.48
(3%)
5.86 4.89 (27%)
May 2023
5.43 5.27
(4%)
6.01 5.70 (6%)
June 2023
5.49 5.21
(6%)
5.69 4.87 (17%)
July 2023
4.93 4.93
(0%)
4.91 4.78 (3%)
August 2023
4.64 4.46
(5%)
4.81 4.50 (8%)
Table 5: Evaluation time-shifted data. The evaluation data is taken from newly-added Wikipedia articles since April 2023, which is after the creation of both the Pile and Red aajma. The neural model is Llama-2 (13B), and the oo-gram reference data is Pile RPJ.
GPT-2 (Radford et al., 2019), one of the earliest autoregressive language models whose sizes range from 117M, 345M, and 774M 1.6B. Their training data is diverse set of web text, although is not public.
GPT-Neo (Gao et al., 2020) and GPT-J (Wang & Komatsuzaki, 2021), language models trained on the Pile whose sizes vary from 125M, 1.3B, and 2.7B to 6.7B.
Llama-2 (Touvron et al., 2023b), subsequent version of LLaMA (Touvron et al., 2023a) trained on two trillion tokens and has sizes of 7B, 13B, and 70B. Llama-2 is one of the most competitive language models whose weights are available at the time of writing the paper. The training data of Llama-2 is unknown, although the precedent version is trained on a large corpus of Common Crawls, Wikipedia and code, which is replicated by RedPajama (Together, 2023).
SILO (Min et al., 2023a), 1.3B language models trained on permissively licensed data only. The original paper showed that training on permissively licensed data leads to the challenge of extreme domain generalization because the training data is skewed to highly specific domains like code and government text. We use three different variants, PD, PDSW and PDSWBY, which are trained on different levels of permissivity, leading to varying levels of the domain generalization challenge.
D.2 Evaluating on time-shifted data
To further show the effectiveness of oo-gram and eliminate doubts that our performance gains might be due to insufficient decontamination, we evaluate on time-shifted data: documents that were created after the cutoff time of the co-gram reference data. We use new Wikipedia articles created during April and August, 2023, which is after the cutoff time of both Pile and RedPajama.
Table reports the perplexity of neural LM as well as the combined model. On documents in four out of the five months, interpolating with co-gram improves the perplexity of the neural LM. We find that this improvement can be further boosted by applying Random Forest decide an instance-wise interpolation hyperparameter where the features of the Random Forest are the suffix lengths (1 up to the effective π) as well as the frequency of each suffix in the reference data. When Random Forest applied, the perplexity improvement ranges from 3% 20%.
D.3 Ablations
Effect of the size of reference data. Figure 10 reports performance of the combined model wrt the size of reference data. To create progressively smaller reference data, we repeatedly downsampled the full reference data by (up 256x, resulting in 9 sizes). We see the improvement brought by co-gram widens as reference data size grows, and the relationship roughly log-linear (except for the NIH ExPorter domain, where co-gram doesn't help when the reference data is too small).
Effect of the domain of reference data. Figure 10 also compares performance of the combined model where the co-gram uses either the full reference data or only the in-domain reference data. Using only the in-domain reference data is roughly powerful as using
20

---

Published as a conference paper at COLM 2024
70
-O-
70 [domsin)
130
-O- 133 (doman)
-
7GB
-O-
700 [domain)
Enron Emails
TreeLom
Githubb
Nill Exportar
Wikipedla
5.5
4.0
21
4.50
4.00
E 4.5
5.5
2.75
1.
5.0
3.50
3.5
3.4
1.8
3.20
2.00
10H 100N
38
100
1000
37
1000!
100
1000
17.
18
305
1200
37.
30M 100M
1000
17
103M
18
100
1000
17
cata (cokens))
Figure 10: Impact of scaling the datastore of the co-gram, all using the 2 models (7B, 13B, and 70B) as neural LMs, and the Pile as the reference data. - neural LM only (baseline). e: o--gram uses the full Pile; o: co-gram uses only the in-domain portion of the Pile. Gains increase consistently as the datastore scales.
the full reference data, which implies that almost all improvement we have achieved is thanks to in-domain data (which has been decontaminatedy This means it would not hurt to the full reference data, especially when the test domain is unknown or an in-domain reference data is unavailable; however, having in-domain reference data is most helpful.
E Extended Discussion
In $4 and $5, we showcased some very preliminary use cases of the infini-gram engine. How- ever, we believe that infini-gram can enable much broader investigations and applications, including but not limited to:
Understanding massive text corpora. Text corpora used for pretraining language models have become prohibitively large, and we have relatively limited understanding of their contents (Blazar al., 2023). Infini-gram can be useful tool to quickly find out what is in the corpus and what is not, using 1--rrmm lookup (the COUNT query).
Data curation. Data engineers often want to remove problematic content in corpora scraped from the Internet, such as toxicity, speech, and personal identifiable information (PII). Using infini-gram's SEARCHDOC query (which can be easily modified to return all documents), one can retrieve all documents containing an n-gram term (or a CNF expression with multiple n-gram terms) and remove them from the corpus. Removal can even be done iteratively: infini-gram indexes are aaditive/subtracie corpus after round one removal, by indexing the removed set and take the difference of the original index and the removal index.
so we can obtain an index of the
Document retrieval. The scale of datastore is key to the effectiveness of retrieval- augmented LMs (Asai et al., 2024). However, vector-based indexes are difficult to scale up due to compute limit, storage limit, and inference efficiency. Infini-gram's 's SEARCHDOC function can retrieve documents from datastores as large as the full pretraining corpora, and can potentially boost the performance of retrieval-augmented LMs.
Reducing hallucination in factual knowledge. Parametric-only models prone to generating non non-factual statements, which is widely known as the hallucination problem. Infini-gram can potentially be used to mitigate hallucination by reading verbatim from the training data. We have found evidence that the co-gram can greatly outperform Llama-2-70B on factual probing benchmarks such LAMA (Petroni et all,2011)
Detecting data contamination, memorization, and plagiarism. Test set contamination has become major issue for language model evaluation. n-gram lookup enables us to check if evaluation queries have sneaked into the training data of neural LMs. It also opens up possibility to detect memorization in aechine-generater text, or plagiarism in human-written text.
Preventing copyright infringement. Recently, generative Als are facing numerous law- suits for generating arguably copyrighted materials. Infini-gram may be helpful for pre-
21

---

Published as a conference paper at COLM 2024
Method
# tokens (1)
# entries (1)
Storage usage (+)
max
Vecfor-based index
RETRO (Borgeaud al., 2022)
1.8
1010
432 TB (16k bytes / entry)
Atlas (Izacard et al., 2022)
27 B
x 10*
200 GB (8 bytes / entry)
KNN-LM (Khandelwal et al., 2020)
3
3 x 109
200 GB (64 bytes / entry)
NPM (Min et al., 2023b)
1 B
x 109
1.4 TB (~ 2k bytes / entry)
n-gram-basedd index
Brants (2007)
2T
10 x 10
unreported GB
Google's (Franz Brants, 2006)
Google Books Ngram (Aiden Michel, 2011)
500 B
unreported
unreported
Stehouwer van Zaanen (2010)
90 M
unreported
unreported
Kennington (2012)
M
10 8 x 10
330 MB (110 bytes token)
Shareghi et al. (2015)
9B
63 GB (7 bytes / token)
00
infini-gram (ours)
5T
1 1025
35 TB (7 bytes token)
Table 6: Comparison with other nonparametric language modeling methods. # tokens: number of tokens in the inference-time reference data. # entries: number of representations (counts) in the index. max maximum number of context tokens considered. For infini- gram, we consider the combination of Pile-train and RedPajama as reference data.
venting copyright infringement, by diverting neural LMs to alternative (yet still plausible) generation paths when they are about to generate long n-grams that appear in the training data, especially if they mostly appear in documents from copyrighted sources.
Measuring popularity of entity. Mallen et al. (2022) showed that LMs have better mem- orization of facts about popular entities than less popular ones. In that paper, heuristic metrics like Wikipedia pageviews are used as proxy to popularity. A better proxy may be the number of appearances of the entity's name in a massive text corpus, which can be easily computed by infini-gram's COUNT query.
Measuring novelty and creativity of text. Are neural LMs generating genuinely novel text, or are they simply copying from its pretraining data? We need a metric for text novelty and creativity, and this metric can be potentially defined by the n-gram overlap between the generated document and the pretraining corpus.
Attribution. When using neural LMs to make predictions, people might want to know which training data most influenced the model's decision. Using 1--ram lookup with key phrases, we can trace back to related documents in the training data of neural LMs.
Non-parametric speculative decoding. Speculative decoding (Chen al., 2023) speeds up text generation by employing fast and a slow decoder, where the fast decoder is smaller model that does the autoregressive token generation, and the slow decoder checks the fast decoder's proposals by parallelizing the forward passes of multiple tokens. Given the low latency of infini-gram, we can potentially use co-gram as the fast decoder, similar to He al. (2023).
We welcome the community to collaboratively build toward the aforementioned directions, by leveraging our publicly released web interface and API endpoint.
Extended Related Work
n-grams beyond n = 5. Mochihashi & Sumita (2007) and Wood et al. (2009) consider infinitely-ordered Markov models, which the co-gram LM is a special case. Aside from the oo-gram LM, some other work has found value in scaling the value of n in n-grams, For example, KiloGrams (Raff al., 2019) uses 1024-grams features for malware detection.
Other data structures for text indexing. Beside suffix arrays and suffix trees, other data structures have been used to index text corpora to satisfy different trade-offs. Koala (Vu et al., 2023) builds a compressed suffix array to analyze overlap between text corpora. The ROOTS Search Tool (Piktus et al., 2023) builds BM25 index on the ROOTS corpus, and
22

---

Published as a conference paper at COLM 2024
supports document searching via both exact match and fuzzy match of n-grams. Data Portraits (Marone & Durme, 2023) proposes lightweight index based on Bloom Filter, and is tailored for probabilistic membership inference (exact match of n-grams of 50 characters, where и 22 8) against the Pile and Stacks. ElasticSearch is a proprietary search engine based the Lucene index, and it has been used by Dodge et al. (2021) to search documents in C4, and also by Elazar et al. (2023) to count æ-grams and list most frequent 11-grams in various corpora up 480B tokens.
Nonparametric language models. A nonparametric LM refers to the LM whose com pleexity is not bounded as priori, because the complexity can grow or update according to the data given at inference time. Prior work is broadly divided into two categories: a token retrieval approach that represents each token as one vector and uses nonparametric prediction function (Khandelwal et al., 2020; Zhong et al., 2022; Lan et al., 2023; Min et al., 2023b;a; Shi et al., 2023), and chunk retrieval approach that represents each chunk of text vector and incorporates nearest chunks to the neural language model (Guu et al., 2020; Izacard et al., 2022; Borgeaud et al., 2022). Scaling the reference data in nonparametric LMs is very expensive as it requires storing a vector for every unit (either token or chunk). To the best of our knowledge, prior work with the largest reference data is RETRO (Borgeaud al., 2022), which uses the 7B-parameter LM and the reference data consisting of 1.8 trillion tokens. It stores and searches over 28 billion vectors, estimated to consume 432TB of disk space. (Detailed comparisons Table 6.)
G Example Queries and Web Interface
Figures 11 to 16 show one example for each of the six query types supported by infini-gram. We query the Dolma corpus in these examples. Screenshots are taken from our web interface.
gram
Ta counta the number tameu or rugure ap paur thecerpus. Fyousabeett an wwwpttinnuu livel ieturn the sotal nour bur to indh
Pik aeriirrree
Eammge euery natucal language precessing the output Contutaol angunge processngg)
Oway
netunal
1,012,875
Engirz
Pydive
Cherr
Submnit
Leteerte Bnveeebl
Taken ml
V__ Iuggage" wpw.osssogg
Figure 11: Example for query type (COUNT): Counting an n-gram.
2This is in part because RETRO does not use any approximation in KNN search. Even if RETRO used approximate search as Khandelwal et al. (2020) did, it would still use 10TB. Moreover, there is no open-sourced software that easily supports fast kNN search over tens of billions of vectors.
23

---

Published as a conference paper at COLM 2024
2. Selattore
mmigian diaiiouu
Computa probability last takan n- n-gram
Rachaama tobendl
compuute the gran probenility ohehe toknn can dittoreed prnvlius tnkone ja tn-logrent
Filc tee 300 mo)mn)
Eumpli euery netural langage preeesing this eviput Mgrooosinn en suan" Tutanalla gawart und lako the beddiviion betweerr Uhs twa)
ig insture lang--pell by courding of the gran wwweerillnnggeeeeeeeeeee
chrcaa (i-10 foundlia coruus
Query
0.4588 (1,012,875/ 2,207,617)
Figure 12: Example for query type 2 (NGRAMPROB): Computing token probability from R-gram LM (with given n, no backoff).
Crrai
Deimarta takera
3. Compute the next-ttkeen distribution of an (n-1)-gram
jechtanna ii tollen)
estond
fallnee
gone thocorpus 10 gone found checoges an message will aapppi iftle ppon-sppors Lines in wheerrooooo iu resil will celllle--pppe approernate
ne. (700ta
Owiry
demtoution
Jaaall Fuot
Pyties
retuni angu
processing (1012374
Jocceeaing (3022974 2387427)
Char
Submih:
1329929 2202N07
Letoroi Bivnewol
194927 5963617)
125
Lindecstundingg (33779 32076A7)
.Test CAMAA 200061)
(35215 33RTNAT)
(21329 2207ASTI
Figure 13: Example for query type 3 (NGRAMDIST): Computing the full next-token distribu- tion from n-gram LM. Due to space limits, only top-10 tokens shown.
24

---

Published as a conference paper at COLM 2024
Calper
gar
pompre
pranent Senshhdouumee
4. Compute the ce-gram probability of the last token
Pijenui loders))
guen probes
the
rugare
lingest suffic that Fnd caguus
comple query. liewe natural langage prezeeting surpott Piproeetigg natuni beguagel, becuue "tatura languge appoorti the corpoc raturs
languaps" soaunt; chi case the officiienn 3t
Filyes (i00nol
Notei muy lkk thai theoflestivr 1-2, ridhcess Arcdisoo withi sni probuil Ilyol the tokks
Iegane
C- pefa Fool
Pybiv
Owey
Scali uibounded
0.9846 (64 65)
Submiit
Tik
Syan "gan"" to "rall "eight Jur "soaalee"" "_ "paae" Aagugee reve 2015 meee, Las, veri, siad (eu, aid
Figure 14: Example for query type 4 (INFGRAMPROR): Computing a token probability from oo-gram LM.
Coeerene For delesttre Mort Fortbrtee
prmppoe
Compute the co-gram text-token distribution
Rijenn it di sadene)
to Query,, 3, out graniinttddi regurs.
Comple query. llov ratural langugg 3he cutput Po (natued lor organgy) borthatt---
Quicy
&. Centutte
bufil qure tocle twwooeeeee guoe lang sigitall
els (64/ 65)
clerr
Subriit
alling CL
Labayy (v descanci
13312
"pant 1f "agg" "boande"" 1o "gan" vo 2ww. we 1rm sndd
rigien Leng
Figure 15: Example for query type 5 (INFGRAMDIST): Computing the full next-token distribution from co-gram LM. Due to space limits, only top-10 tokens are shown.
25

---

Published as a conference paper at COLM 2024
Delia GuT talad
Search for documents containing n-gram(s)
cecurents the sorpu thtehes your query. canaimpll enter rugron In decumeet doydd would contein your gram You canohs connectims ligle gpantermo with the AND operaora, inthe C3t lacmad in which uas diaulaycc docament conta grah that sisisst this legia constriin
deplays
Pil-tt ao si
Bux murlp quatteqquatee
eg
prooeetigg
nonural langagge processing ep AMo drep brarning the riguayed rona mone an uii roan suth tanuollang wagiagggggggg poocesiin" and "tepp meniingg
matural angaage processing ng intetige mesiigeenn deep learning machine lamming thee displayed document would lenticoe featurtt for ga processing 7" lngentt
of "cwea lraveng" "rracheno learing"?
fow rotes.
you queryin note that has nigher precedencs AND juhich contrary sonventional pl
waccen ong include document wher tarma por cla asntt are seperated by no more than 100 towes. (per
clusse
dasumorss
night
The rumntor of buant semurrent monirr di pli bng. an ronea your
jouse No corpus may conta problemaace contonts such asint, booc by. kuce spooth, and hop sroue. toel readyy present selvcce ted from thecorpes, withost any payp hen ralety Rlwwing in MOT eveating new teat This ia eeseach pa through which we expooo and namiie wolding prokenee coution, be
Approximately 78360 occurrences found. Displaying the documents of occurrences #[2526, 13007, 1920, 7775, 11136, 6112, 6312, 13600, 272]
Mumides coneresntt Deplly
1B
Cloar
Subriit
Lisecy (nlllaoord
Jacanse toa lis, songht
dappagenc
Stip terning Insural longage procmingg is sarnt vot roult ar
"_.ritaa" LLa "_roosiinng bac, soa soul
The afied modds that endio deep redeosennet catraal las que priiee loi qu bataa appaess
chibe an www.ehggggggegooooooooooo in
Figure 16: Example for query type 6 (SEARCHDoC). Returning documents containing n-gram, or a CNF logical expression of n-gram terms, connected with AND's and/ OR's.
26


Reviews:
[{"review_id": "GoBCnKpY51", "reviewer": "Reviewer_Quuz", "summary": "Authors present a non-parameteric language model based on suffix trees, they extend the ngram tables in the following ways:\n(1) The consider the longest prefix that has non-zero count in the training corpus (n is variable and tend to be large)\n(2) The probability estimate is an interpolation between the neural LM and count based LM\n(3) Training corpus is in the scale of LLMs (trillion of tokens)\n\nThe authors combine parameteric models NeuralLM with their count based \\inf-gram method.\n\nThe authors propose new metrics to analyze the performance of their \\inf-gram method by studying the agreement between the neural method probability and the count based method. They use this agreement metric to analyze models of different sizes and try to distinguish human writing from machine one.", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate your recognition of our paper, especially the applications that may be enabled by the technology we develop.\n\nHere is our response to your questions:\n\n**[Reasons-to-Reject 1/Q3] Description of suffix trees and tokenizers:** We will improve the clarity of this section in our revision. This is a token-level model, not a byte-level model, because the smallest unit is a token and we don’t use raw ASCII/Unicode bytes. We first use an existing tokenizer to convert the dataset into an array of token IDs, and then build the suffix array for this token ID array. The byte-pair thing is an implementation detail: each token ID happens to occupy 2 bytes in little-endian order, so the suffix array for the token ID array is slightly different from the suffix array for the underlying bytes of this token ID array. We made sure our handling of byte order is correct and consistent.\n\n**[RR2/Q2] Scaling law analysis:** We presented this in Appendix D.4 and Figure 10 due to space limitations. Perplexity improves more with larger ∞-gram reference data, and for most domains, perplexity decreases linearly wrt the logarithm of reference data size.\n\n**[Q1] Extending the agreement analysis for machine detection of human writing:** When comparing the agreement plots in Fig 3 (middle) and Fig 5, we didn’t observe a distinguishing feature between human-written and machine-generated text. Infini-gram may become helpful in distinguishing human and machine writings, though this might require looking at other features, e.g., how “effective n” evolves over the tokens in a document. We leave this as a future research direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "(1) I think the community will find this paper thought provoking: most of the recent work is on parameteric LM. Combining non-parameteric models shows improvement in our ability to maximize the likelihood of the evaluation corpus. Reviving this old approach might lead to the following interesting applications:\n(a) Possible ways to improve generation with a large predefined factual corpus.\n(b) Possible ways to identify (fingerprint) human-generated corpus vs machine one.\n\n\n\n(2) The paper is well written and easy to follow with honest description of what works (improving likelihood) and what does not work yet (generation). I really enjoyed the balanced tone of the work and the focus on the analysis.", "reasons_to_reject": "(1) I found the sections describing the suffix trees and how the tokenizer interact with the suffix trees not as clear as the rest of text.\n(2) Lack of scaling law analysis with the impact of the training corpus (data) on perplexity.", "questions_to_authors": "(1) Can you comment or possibility of extending the agreement analysis as a basis for machine detection of human writing?\n\n(2) Would extending the training corpus of the ngrams follow a scaling law trend?\n\n\n(3) I got confused by byte-pair and tokenized text representation used to fill the suffix tree, Would you count this a byte-level model? Maybe in the camera ready version try to walk the reader slowly with how the suffix tree being built using a toy example.", "extra_scores": {}}, {"review_id": "IV8WllXqug", "reviewer": "Reviewer_CssV", "summary": "The paper presents an approach and method to train n-gram language models with arbitrarily large n, as well as training of n-gram models on trillion-scale datasets that match in size the datasets used for training neural language models. The approach to training infini-gram models is novel and allows training of models that perform significantly better than traditional n-gram models in next token prediction task. The authors also show that combining neural language model with an infini-gram model improves model perplexity significantly.  All in all this is a good paper. It is well structured, the approach to extending n-gram context length is to my understanding novel and the results are promising. This is also the first paper to train n-gram models with a 5 trillion token dataset.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for recognizing the novelty of our method, which enabled training n-gram LMs at unprecedented scale.\n\n**Regarding Reasons to Reject (“There may be no need for n-gram models because compute resources for LLMs are already available and the n-gram model does not match neural LMs”):** While it is true that the ∞-gram LM alone does not outperform neural LMs, it is important to note that ∞-gram LMs can supplement neural LMs, making smaller models comparable to larger models, e.g., 7B model with ∞-gram matches 70B model, as shown in Table 1. We believe this is still a meaningful research direction, given that training, developing, and using massive-scale LLMs is still resource-heavy and is infeasible to do at most institutions.\n\nIn addition, we opened an API endpoint of the infini-gram engine for public use, and during the past three months, it has served over **60 million queries**. It is evident that the technology we built for this paper has become a useful research tool for the community.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The approach and method is novel, the results are good and the paper is well written.", "reasons_to_reject": "It could be argued that given the availability of compute resources and the performance of large neural language models, there is no need for n-gram models, especially as they cannot match neural language models in their capabilities. However, given the huge burden on environment that training large neural language models has, researching and developing alternative and less resource intensive methods is a welcome direction.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XGkfZVMgOo", "reviewer": "Reviewer_fyaK", "summary": "This paper presents infini-gram, an n-gram model with unbounded n-gram order trained on very sized corpora containing 5T tokens. The paper shows that infini-gram can substantially outperform vanilla 5-gram models in terms of next token prediction (62% relative improvement) and can yield improvement in perplexity upon interpolating with neural lms. The paper shows that infini-gram can be implemented efficiently using suffix arrays, a technique that has been proposed in the past but not used for scaling the LM to trillions of tokens.\n\nStrengths:\n* Shows that an n-gram model can be scaled to substantially large corpora with trillions of tokens.\n* Shows that an n-gram model can yield perplexity improvements when combined with neural LMs\n* Demonstrates how the infini-gram can be used to conduct analysis of effective n (length of longest suffix with non-zero count) in neural LMs. \n\nWeaknesses:\n* There are some critical metrics which are not reported in the paper\ne.g. next token prediction for neural LM, perplexity of the infini-gram by itself\n*  Though the infini-gram outperforms a 5-gram LM, it is still substantially weaker than a neural LM. While it is good to see that the infini-gram improves the perplexity of the neural LM, this result has been reported in prior literature\nhttps://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/rnn_ctxt.pdf\n* The paper does not report comparison with other non-parametric approaches such as kNN LMs (Khandelwal et al. 2020)", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for recognizing the values in scaling n-gram LMs and their effectiveness to performance improvements and analysis.\n\n**[Weakness 1/Reasons-to-Reject 1/Q2] Missing metrics:** We report the suggested metrics below, using the same eval data as in Sec 4.1 (“Setup”).\n* **Accuracy of next-token prediction:**\n  * Neural-only: 62%, 63%, and 65%, with Llama-2 7B, 13B, and 70B, respectively\n  * Neural + ∞-gram: 66%, 67% and 69%, with Llama-2 7B, 13B, and 70B, respectively\n  * ∞-gram only: 47%\n* Consistent with the perplexity results, ∞-gram supplements neural LMs, although using ∞-gram alone does not outperform neural LMs.\n* **Perplexity of ∞-gram LM alone:** Since ∞-gram probabilities may contain zeros, we evaluated a variant of ∞-gram that takes a weighted average of all n-gram LM predictions where n ranges from 1 to the longest suffix. **It has a perplexity of 19.82.** In comparison, GPT-2 (117M) is 22.82 and GPT-2 (345M) is 16.45 (Table 1).\n* We highlight that ∞-gram alone does not outperform neural LMs; rather, ∞-gram supplements neural LLMs, making smaller LLMs comparable to larger LLMs.\n\n**[Weakness 2] Prior literature:** We will revise our paper to highlight that the interpolation method is not new, but our key contribution is showing that ∞-gram can supplement **large** LMs (the neural model in the 2016 paper has 300 neurons, whereas we compared with neural LMs up to 70B parameters).\n\n**[Weakness 3/RR2] Comparison with kNN-LM:** We included a comparison of ∞-gram with other non-parametric methods (kNN-LM, RIC-LM) in Appendix D.2 and Table 4. We will move them to main text in the revision. ∞-gram improves perplexity much more than these alternatives. Also, as kNN-LM and RIC-LM are more resource-intensive, prior work could not scale the reference data to trillion-token scale.\n\n**[RR3] Error analysis:** We did some qualitative analyses, and found that ∞-gram is often good at completing multi-token words (e.g., hippop**otamus**, correctly predicted tokens are bolded), common phrases (e.g., born **in**), and entity names (e.g., educated at Tr**inity College**). ∞-gram is not very good at recalling factual knowledge (e.g., predicting the first token of an entity name), likely due to insufficient contextualization. We’ll include this analysis in the next revision.\n\n**[Q1] It is unclear how “When plotting ... Transformers” is related to infini-gram:** This paragraph in Sec 4 is an example of the type of insights we can gain about LLMs, using ∞-gram as a tool.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* Shows that an n-gram models can be scaled to very large corpora with trillions of tokens - which are used currently for training neural LMs\n* Shows that the n-gram model can be used to perform interesting text analysis of neural LMs using metrics such as 'effective n' - which is the length of the longest suffix with non-zero count in training data\n* Demonstrates that the infini-gram model can be implemented efficiently using suffix arrays. Although this technique has been used in the past, this paper may further popularize its application in the research community", "reasons_to_reject": "* The paper does not report key metrics such as next-token prediction accuracy of neural LM, the perplexity of infini-gram LM by itself.\n* The paper does not compare the proposed approach to other non-parametric LM approaches such as the kNN LM (Khandelwal et al)\n* The paper does not present an error analysis showing where the infini-gram either outperforms/underperforms a neural LM. e.g. is a neural LM better at generalization?", "questions_to_authors": "* \"When plotting the agreement level with respect to the suffix length, text generated by neural LMs with nucleus sampling is most similar to human-written text, among other decoding methods like greedy decoding and temperature sampling. For greedy decoding, the agreement plot suffers from significant fluctuation, which may be rooted in deficiencies in neural LM pretraining and the positional embeddings of Transformer\"\nIt is unclear how this finding is related to infini-gram. \n*  Figure 3: what is the next token prediction accuracy for neural LM?", "extra_scores": {}}, {"review_id": "PKQeUHf5Ue", "reviewer": "Reviewer_DJ1F", "summary": "This paper primarily proposes improvements to the ngram language model, enhancing its capabilities through engineering optimizations that support grams of unlimited length, while also utilizing a larger-scale corpus. The ngram language model serves as an excellent complement to Large Language Models (LLMs).", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! We appreciate your recognition of our contributions in scaling n-gram LMs and using them to enhance neural LLMs. \n\n**[Reasons-to-Reject 1/Q1/Q3] Besides PPL, in what scenarios can infini-gram be applied to/Can infini-gram directly generate text:** We believe that ∞-gram LMs have the potential to be useful for a wide array of end tasks through text generation, similar to how LLMs are being used. In our preliminary investigation, we identified some unique challenges with ∞-gram LMs in text generation, as discussed at the end of Section 5.2, e.g., not being robust to digression, and that it may require new sampling algorithms. We defer such development to future research.\n\n**[RR1] Model lacks practical experiments and future prospects:** In addition to the ∞-gram model, our key contribution also includes the infini-gram text search engine. We opened an API endpoint of the infini-gram engine for public use, and during the past three months, it has served over **60 million queries**. It is evident that the technology we built for this paper has become a useful research tool for the community.\n\n**[Q2] How can the ngram model complement LLMs:** Our paper shows one way -- by interpolating the probabilities given by both models. This method is simple but may be limited in expressiveness. In future work, it is possible to develop more advanced ways for n-gram LMs to complement neural LMs, e.g., training neural LMs to fit the residue between n-gram LMs and the ground truth, or using n-gram LMs to validate neural LM generations.\n\n**[Q4] Generalization of the n-gram model:** The n-gram LM alone has limited generalization due to data sparsity. We explored a distribution shift scenario (time shift) in Appendix D.3 and found the gains are reduced (although remain positive). We think the n-gram LM is particularly useful when verbatim memorization is more important than generalization, e.g., entity names and common expressions; see our response on “error analysis” to Reviewer fyaK for more details. Additionally, our combined model, which interpolates the n-gram LM with the neural LM, partially addresses this issue, contributing to the positive gains in Appendix D.3.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. This paper studies the Infinity-ngram model, which is an interesting issue and can also be helpful for the research on Large Language Models (LLMs).\n2. This paper, through engineering optimizations, supports a large corpus and \"infinity\" ngram length. It also provides inspiration for subsequent related research.", "reasons_to_reject": "1. The model proposed in the paper lacks practical experiments, making it difficult to see its future prospects.", "questions_to_authors": "1. Compared to LLMs, besides calculating PPL, in what scenarios can the infinity ngram model apply?\n2. How can the Ngram model complement LLMs?\n3. Is it possible to directly generate text like auto regressive model?\n4. How does the generalization of the Ngram model?", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a nonparametric language model that generalizes traditional n-gram language models to unboundedly large n, maked scalable using suffix arrays. This makes it possible to apply the model to LLM-scale training data. While the resulting performance (understandably) lags behind neural LLMs, the paper provides quantitative evidence that an LLM can be improved by interpolating it with the proposed language model.

All four reviewers provided positive recommendations. The reviewers raised some reasonable concerns, which the authors addressed convincingly.

Overall, the paper provides an original and provocative contribution to the literature on Language Models, with convincing quantitative results.
Decision: Accept