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

Authors: jiacheng  liu
♡  sewon
min ♡ luke zettlemoyer
yejin  choi
hannaneh  hajishirzi
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-12 19:17:33

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.

Main paper: 
 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, n-gram language model (LM) perform if estimated from such massive corpora? In other words, are n-gram LMs still 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 n-gram LM in two aspects: the training data size, and the value of n. 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 n-gram LM ever built. Historically, n-gram indexes have been built only for small n's (e.g., n ≤ 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, if we can use a larger n (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 ∞-gram LM. We use a variant of backoff (Jurafsky & Martin, 2000) , where we resort to smaller n when longer n-grams have a zero count. Due to sparsity in the ∞-gram estimates, in some of the later experiments ( §5), we will interpolate between the ∞-gram LM and neural LMs to yield a hybrid LM upon which perplexity can be computed.We develop a low-latency, resource-efficient engine to serve this massive ∞-gram LM. Instead of building an explicit n-gram count table, which is infeasible for arbitrarily large n and such extreme data scale, we power the ∞-gram LM with a suffix array of the dataset -a 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 a 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 n is or how frequently the n-gram appears), and under 200 milliseconds for all other query types including ∞-gram language modeling and decoding. All indexes stay on-disk at inference time. We refer to this engine as infini-gram.Analyses with ∞-gram ( §4) offers new insights into human-written and machine-generated text. We found that ∞-gram has a 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 n-grams (with small n) are insufficient in capturing a long enough context to predict the next token (29% accuracy). Moreover, we show that ∞-gram can complement neural LMs and reach better performance when combined: heuristically interpolating between the estimates made by ∞-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 ∞-gram, nucleus sampling (Holtzman et al., 2019) from neural LMs produces machinegenerated 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 a public web interface and an API endpoint that serve n-gram/∞-gram 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. 
∞-gram lm: extending n-gram lms with unbounded n: 
 Background: n-gram LM. The n-gram LM is a classical, statistical language model based on counting the occurrences of n-grams. In its most simple form, the probability of a token w i given a context w i-(n-1):i-1 is estimated as P n (w i | w i-(n-1):i-1 ) = cnt(w i-(n-1):i-1 w i |D) cnt(w i-(n-1):i-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 n is a pre-defined hyperparameter. (When n = 1, we define w i-(n-1):i-1 as the empty string ε, whose count is equal to |D|.) However, this naive version of n-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 is zero we decrease n 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 P n ( * |w i-(n-1):i-1 ), because the effective n is dependent on w i . Therefore, further probability discounting is required to normalize this distribution (e.g., Katz backoff (Katz, 1987) ).Conventionally, n-gram LMs have been implemented by building an n-gram count table of the training data. This table stores all unique n-grams that appear in the training data, each associated with its count. Such n-gram count tables are huge and grow almost exponentially wrt n. For example, the 5-gram count table for a 1.4-trillion-token corpus would consume 28 TB of disk space. As a result, previous n-gram LMs are limited to very small n, 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 n is that it discards richer context, making such n-gram LMs poorly predictive of future tokens.∞-gram LM. The ∞-gram LM is a generalization of the n-gram LM, where conceptually we start backing off from n = ∞. We use a 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 longest suffix that appears in the training data.For the rest of this paper, we will use "∞-gram" to refer to the ∞-gram LM. ∞-gram is formally defined asP ∞ (w i | w 1:i-1 ) = cnt(w i-(n-1):i-1 w i | D) cnt(w i-(n-1):i-1 | D)where w 1:i-1 are all tokens preceding w i in the document, andn = max{n ′ ∈ [1, i] | cnt(w i-(n ′ -1):i-1 | D) > 0}.Unlike Katz backoff, P ∞ ( * |w 1:i-1 ) is a valid distribution by construction and does not require discounting. This is because the effective n is solely dependent on w 1:i-1 and does not depend on w i , and∑ w i ∈V cnt(w i-(n-1):i-1 w i | D) = cnt(w i-(n-1):i-1 | D).Further, we define the sparsity of this ∞-gram estimate: an estimate is sparse iff P(w i |w i-(n-1):i-1 ) = 1 for one of the w i ∈ V, and is zero for all other tokens in the vocabulary. Intuitively, this means there is only one possible next token given this context, according to the training data. As we will show in §4, sparse estimates are more predictive of the actual tokens than non-sparse ones.Interpolating with neural LMs. ∞-gram estimates contain zero probabilities, which may lead to infinite perplexity. We do not attempt to compute the perplexity of the ∞-gram itself. Instead, we interpolate it with neural LMs and show perplexity improvement over the neural LMs alone ( §5). The combined model isP(y | x) = λP ∞ (y | x) + (1 -λ)P neural (y | x),where λ ∈ [0, 1] is a hyperparameter. 3 Infini-gram: A Performant Engine for n-gram/∞-gram QueriesWe train ∞-gram on modern, trillion-token text corpora. However, it is practically infeasible to build n-gram count tables with unbounded n for such massive datasets. In this section, we describe our infini-gram engine that processes n-gram/∞-gram queries efficiently. Infinigram is powered by a data structure called suffix array. We will show how to build this suffix array index and how to perform n-gram/∞-gram inferences with it.Suffix array. The essence of n-gram and ∞-gram LMs is counting a given n-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 a 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 a given needle string has time complexity O(L + log N).A suffix array represents the lexicographical ordering of all suffixes of an array (or a string, which is an array of characters). For an 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 2 (right), we build the suffix array on the byte array of the tokenized dataset (i.e., token array). Documents are separated by the \xff\xff token. In the token array, each consecutive two bytes represent a token ID (assuming that |V | < 2 16 = 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 ⌈log 2 (2N)/8⌉ bytes. For corpora with 2B to 500B tokens (which is the range we deal with, after sharding ( §A.3)), this is 5 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 ( §A.2), together these can be easily combined into a larger index with a total of 5 trillion tokens, and the implicit count table contains at least 2 quadrillion unique n-grams ( §A.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 1 ...x n ). By construction, the occurrence positions of strings starting with x 1 ...x n lies in a 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/∞-gram language modeling, infini-gram can also be used to retrieve documents containing an n-gram, or a CNF expression with multiple n-grams ( §A.4).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 RedPajama, our most optimized infini-gram engine can count a given n-gram with an average latency of less than 20 milliseconds. It can compute the probability and nexttoken distribution in 40 milliseconds for n-gram LMs, and in 200 milliseconds for the ∞-gram. 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 ∞-gram: 
 In this section, we present some analyses of human-written and machine-generated text from the perspective of ∞-gram, mostly focusing on the token-wise agreement between ∞-gram's prediction and the actual text. In summary, we found that:1. ∞-gram has a fairly high accuracy (47%) when predicting the next token given a prefix of a human-written document, and this accuracy is higher when a longer suffix of the prompt can be used (i.e., when the effective n is larger);2. Conventional n-gram LMs (n ≤ 5) are insufficient for capturing a long enough context to determine the next token, while our ∞-gram method is highly predictive of humanwritten and machine-generated text;3. ∞-gram has significant potential to complement and improve neural LMs when predicting 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-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 Transformers.∞-gram training data. For analyses in this section, we use a decontaminated version of Pile's training set ("Pile-train") (Gao et al., 2020) as training data for the ∞-gram. We built an infini-gram index on Pile-train using the Llama-2 tokenizer (Touvron et al., 2023b) , and yield 360 billion tokens.It is important that the training data is decontaminated against the evaluation data, because otherwise it is very easy for ∞-gram to cheat by copying from the very same document in the training data. We run decontamination of Pile-train against its validation 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 if it has excessive n-gram overlap with the evaluation data. See §B for more details.Decontamination is non-trivial, and its definition could vary (e.g., when there is an identical sentence, is it contamination, or is it a quote that naturally occurs in real test-time scenarios?) Thus we followed the standard best practices for decontamination.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 to 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 ∞-gram's prediction and the actual humanwritten text. Since computing the full next-token distribution (or the argmax of it) in ∞-gram is relatively slow, we compute the ∞-gram probability of the actual next-token, and deem it 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, i.e., one plus the length of their prompt's longest suffix that has a non-zero count in the training data. 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, ∞-gram agrees with the human-written text on 47% of the tokens. We see that ∞-gram becomes more accurate with the increase of effective n: when the effective n ≥ 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 ∞-gram. 5-gram LMs, which has been used extensively in previous literature (Franz & Brants, 2006; Aiden & Michel, 2011) , does not capture a long enough context to correctly predict the next token: over 90% tokens in the evaluation data has an effective n of at least 5, and the ∞-gram analysis shows that the median of effective n 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 ∞-gram estimate, which covers more than 50% of all tokens. The overall agreement is even higher (75%), and when the effective n ≥ 14, agreement is higher than 80%. This means when the next token is unique according to the training data, that unique token is very likely to be the actual token in human-written text.Qualitatively, we found that ∞-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). ∞-gram is not very good at recalling factual knowledge (e.g., predicting the first token of an entity name), likely due to insufficient contextualization.∞-gram can shine where neural LMs fail. In Figure 4 , we plot the distribution of probabilities assigned by the Llama-2 70B/13B/7B models (Touvron et al., 2023b) to the actual tokens in human-written text, and the human-∞-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 a positive, yet imperfect, correlation between neural LMs and ∞-gram regarding their agreement with the actual text. In particular, when the neural LM performance is very poor (left side of the histogram), ∞-gram still gives a non-trivial agreement of above 20%; if only considering tokens with sparse ∞-gram estimates, the agreement is as high as 50%. This indicates a huge potential of complementing and improving the performance of neural LMs with ∞-gram for predicting human-written text, which we further investigate in §5.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 a continuation. Generation continues up to the original length of the document, or when an [EOS] token is generated. We experiment with three decoding methods: greedy decoding, temperature sampling, and nucleus sampling (Holtzman et al., 2019) . The neural LMs are Llama-2 70B/13B/7B, GPT-J 6B (Wang & Komatsuzaki, 2021) , and GPT-Neo 2.7B/1.3B/125M (Gao et al., 2020) . The tokenizer of GPT-Neo/J is different from Llama-2, so we built a 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 n 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 n 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 n, 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 GPT-Neo/J models is higher than Llama-2 models, probably because GPT-Neo/J are trained on the same data as the ∞-gram (i.e., Pile-train). Overall, text generated by these neural LMs has similar agreement level with ∞-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/J models), and for Llama-2 7B the fluctuation is even periodic (rapidly dropping at effective n = 20, 24, 28, 32; this is statistically significant, a two-proportion z-test gives a p-value of < 10 -99 ). We suspect that this may be caused by the application of positional embeddings when pretraining these Transformer-based models, and we welcome further investigation from the community.  
improving neural lms with the ∞-gram: 
 The results in §4 motivate us to combine neural LMs and ∞-gram ( §2) to yield better language models. In this section, we will show strong experimental results of the combined model. In §4 we found that the ∞-gram estimate has higher agreement with human-written text when it is sparse. Therefore, we use two separate interpolation hyperparameters: λ 1 for sparse and λ 2 for non-sparse ∞-gram estimates. These hyperparameters are tuned on the validation set to minimize the perplexity of the combined model.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 ∞-gram training data). The relative improvement of model M against model M o is defined as (1 -PPL(M)-1 PPL(M o )-1 ) × 100%, which is the percentage of perplexity gap closed towards perfect language modeling (i.e., PPL = 1). Additional details on evaluation data processing in §D.1.Reference data. To reduce confusion, in this section we will use reference data to refer to the training data of the ∞-gram. In addition to Pile's training set that we used in the previous analyses ( §4), we also consider RedPajama (Together, 2023) as 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 ∞-gram. In total, 14 models are considered: GPT-2 117M/345M/774M/1.6B (Radford et al., 2019) , GPT-Neo 125M/1.3B/2.7B, GPT-J-6B, Llama-2 7B/13B/70B, and SILO PD/PDSW/PDSWBY (Min et al., 2023a) . See §D.1 for additional details about these models and their training data.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 of the infini-gram index on 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 Llama-2 and SILO are not comparable to them nor to each other. Experimental results with GPT-2, GPT-Neo/J, and Llama-2 on Pile's evaluation sets are shown in Table 1 . Results on time-shifted data can be found in §D.2, and we show the impact of the size and domain of reference data in §D.3.Interpolating with ∞-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 a 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, ∞-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/J models are trained precisely on Pile, while GPT-2 models are not. ∞-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 ∞-gram also improves neural LMs already pretrained on its reference data shows that there is consistent advantage in introducing ∞-gram.On the choice of ∞-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 ∞-gram with Pile-train + RedPajama outperforms Llama-2 70B, and interpolating with ∞-gram pushes the perplexity of Llama-2 70B below 4.0.When the neural LM is SILO (which is trained on permissive-licensed data only and thus has less training data), adding the ∞-gram component is more helpful when SILO is trained on more restrictive data (i.e., PD > PDSW > PDSWBY). The usage of ∞-gram can be precisely traced back to the contributing document(s) in 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 retrieval-augmentation methods used by SILO, i.e., kNN-LM and RIC-LM, ∞-gram yields better improvement in perplexity. Therefore, ∞-gram can serve as a better alternative as the retrieval-augmentation method for SILO.A note on text generation. While ∞-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, ∞-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 ∞-gram best contribute to text generation. 
related work: 
 We discuss closely related work here. See §E for extended discussion, and Table 6 for comparison with other n-gram models and nonparametric language models.n-gram language models. n-gram 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 n-gram LMs by scaling up its training data. To date, the largest n-gram table (Brants et al., 2007) counts 5-grams in a corpus of 2 trillion tokens.While 2012) proposes to use suffix trees for the same purpose, and yet the storage overhead of suffix trees is 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 a priori, because the complexity can change according to the reference data (Khandelwal et al., 2020; Borgeaud et al., 2022; Asai et al., 2023) . The ∞-gram LM is one instance of nonparametric LMs, and its simplicity makes it possible to significantly scale the reference data with modest resources ( §3). To the best of our knowledge, our ∞-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). 
conclusion: 
 In this paper, we modernized the classical n-gram language model by scaling it up to a 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 ∞-gram language model, powered by the infini-gram engine, and showed that it can offer novel insights into human-written and machine-generated text and can improve existing neural language models. 
 
 Appendix: 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-gram count tables, but non-trivial to compute for infini-gram.If we consider all possible values of n in the n-gram, then a dataset with N tokens would contain about 1 2 N 2 n-grams, and since most of these n-grams are long and thus very likely to be distinct, there would be about 1 2 N 2 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 × 10 25 , or equivalently, 20 mol (using N A = 6.02 × 10 23 /mol).However, the document separator is meaningless and should not be part of the n-grams, and we should probably only count n-grams within the document boundaries. There are N = 5 × 10 12 tokens and D = 6 × 10 9 documents, and on average each documents have 857 tokens. Using the Cauchy-Schwarz inequality, we have the total number of n-grams as∑ d 1 2 N 2 d ≥ 1 2 D • ( N D ) 2 = N 2 2D = 2 × 10 15Therefore, there are at least 2 quadrillion unique n-grams in the count table implied by infini-gram.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 a single index by adding up the n-gram counts from each index. This feature is useful in the sharding technique that we discuss in §A.3 and §A.4. Similarly, if we have built indexes on a big dataset and a subset of it, we can easily obtain an index of their difference by taking the difference of n-gram counts. Compared to having a single index, both operations incur some additional inference operations (which can be parallelized to mitigate latency overhead), but they would spare us 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 a comma-separated string for each document that contains its metadata (e.g., document ID, source, URL), and a document metadata offset file stores the byte offset of each document'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.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 to fit into RAM. In such cases, we shard the byte array into multiple shards, and build a suffix array for each shard. Sharding would induce additional inference latency, which we discuss and mitigate below ( §A.4).Both the first and last occurrence positions can be found with binary search, with time complexity O(n • log N) and O(log N) random array accesses. The two binary searches can be parallelized, reducing the latency by roughly 2x. The impact of query length n 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 a by-product: we also get to 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 a binary search on the document offset index. (Note that if we don'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 1 ...x n must be a sub-segment of that for x 1 ...x n-1 . Therefore, when computing the n-gram probability P n (x n | x 1 ...x n-1 ), we can first count x 1 ...x n-1 , and then when counting x 1 ...x n , we only need to search for the first and last occurrence positions within the segment of x 1 ...x n , 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 a significant latency as the binary search requires random access to the byte array and suffix array. To mitigate this, we implemented a 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. + 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.To compute the ∞-gram probability, we need to count the occurrence of each suffix x l-n+1 ...x l up to the maximum n 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 ∞-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 O(log L), and thus the time complexity for each ∞-gram computation becomes O(log L • log N).Speeding up dense ∞-gram computation. During evaluation, we need to compute the ∞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).Infini-gram supports the following types of n-gram/∞-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 ∞-gram LM (INFGRAMPROB); 5. Computing the full next-token distribution from ∞-gram LM (INFGRAMDIST); 6. Returning documents containing an n-gram, or a CNF logical expression of n-gram terms, connected with AND's and/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 ∞-gram queries, and show results in Table 3 . 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 a token probability from ∞-gram LM on consecutive tokens", where we sampled 10 documents and processed 1000 consecutive tokens in each document).All types of queries demonstrate sub-second latency on the trillion-token training data.Computing a token probability from the ∞-gram with RedPajama takes merely 135 milliseconds. Furthermore, our implementation supports counting the occurrence of an n-gram with arbitrarily large n, with roughly constant latency at 20 milliseconds (we experimentally validated up to n = 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 ∞-gram.To properly evaluate the effectiveness of ∞-gram LM on Pile's evaluation sets, we performed data decontamination on the Pile's training set and RedPajama before using them as reference data for the ∞-gram LM. We run the Big Friendly Filter (BFF)1 (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 BFF, we always remove whole documents, instead of by paragraphs. Following the default settings, we consider n-grams where n = 13, and discard the document if at least 80% of its n-grams are present in the evaluation set. For Pile's training set, we lowercase all documents to capture more potential contaminations. Figure 7 is an extension to the middle plot of Figure 3 , and shows a more fine-grained analysis of the token-wise agreement between human-written text and ∞-gram. Figure 8 extends Figure 4 with results on Llama-2-13b/7b. Figure 9 extends Figure 5 with results on GPT-Neo models.Evaluation data processing. We split each document in the evaluation data into batches with a maximum sequence length of 1024 and a sliding window of 512, a setup that is standard in prior language modeling literature (Baevski & Auli, 2019; Khandelwal et al., 2020) . The neural model is Llama-2 (13B), and the ∞-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 to 1.6B. Their training data is a 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) , a 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.To further show the effectiveness of ∞-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 ∞-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 5 reports the perplexity of neural LM as well as the combined model. On documents in four out of the five months, interpolating with ∞-gram improves the perplexity of the neural LM. We find that this improvement can be further boosted by applying a Random Forest to decide an instance-wise interpolation hyperparameter, where the features of the Random Forest are the suffix lengths (1 up to the effective n) as well as the frequency of each suffix in the reference data. When Random Forest is applied, the perplexity improvement ranges from 3% -20%.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 2x (up to 256x, resulting in 9 sizes). We see the improvement brought by ∞-gram widens as reference data size grows, and the relationship is roughly log-linear (except for the NIH ExPorter domain, where ∞-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 ∞-gram uses either the full reference data or only the in-domain reference data. Using only the in-domain reference data is roughly as powerful as using the full reference data, which implies that almost all improvement we have achieved is thanks to in-domain data (which has been decontaminated). This means it would not hurt to use 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.In §4 and §5, we showcased some very preliminary use cases of the infini-gram engine. However, 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 (Elazar et al., 2023) . Infini-gram can be a useful tool to quickly find out what is in the corpus and what is not, using n-gram lookup (the COUNT query).Data curation. Data engineers often want to remove problematic content in corpora scraped from the Internet, such as toxicity, hate 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 additive/subtractive, so we can obtain an index of the corpus after round one removal, by indexing the removed set and take the difference of the original index and the removal index.The scale of datastore is key to the effectiveness of retrievalaugmented 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 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 are prone to generating 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 ∞-gram can greatly outperform Llama-2-70B on factual probing benchmarks such as LAMA (Petroni et al., 2019) .Detecting data contamination, memorization, and plagiarism. Measuring popularity of entity. Mallen et al. (2022) showed that LMs have better memorization 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 n-gram 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 et al., 2023) speeds up text generation by employing a fast and a slow decoder, where the fast decoder is a 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 ∞-gram as the fast decoder, similar to He et al. (2023) .We welcome the community to collaboratively build toward the aforementioned directions, by leveraging our publicly released web interface and API endpoint.n-grams beyond n = 5. Mochihashi & Sumita (2007) and Wood et al. (2009) consider infinitely-ordered Markov models, to which the ∞-gram LM is a special case. Aside from the ∞-gram LM, some other work has found value in scaling the value of n in n-grams. For example, KiloGrams (Raff et al., 2019) uses 1024-grams as 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 a BM25 index on the ROOTS corpus, and supports document searching via both exact match and fuzzy match of n-grams. Data Portraits (Marone & Durme, 2023) proposes a lightweight index based on Bloom Filter, and is tailored for probabilistic membership inference (exact match of n-grams of 50 characters, where n ≈ 8) against the Pile and Stacks. ElasticSearch is a proprietary search engine based on 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 n-grams and list most frequent n-grams in various corpora up to 480B tokens.Nonparametric language models. A nonparametric LM refers to the LM whose complexity is not bounded as a 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 a 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 a chunk retrieval approach that represents each chunk of text as a 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 et 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.2 (Detailed comparisons in Table 6 .) https://github.com/allenai/bffThis 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. 


Decision: 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.

Reviews: review: paper_summary: paper_summary: Authors present a non-parameteric language model based on suffix trees, they extend the ngram tables in the following ways:
(1) The consider the longest prefix that has non-zero count in the training corpus (n is variable and tend to be large)
(2) The probability estimate is an interpolation between the neural LM and count based LM
(3) Training corpus is in the scale of LLMs (trillion of tokens)

The authors combine parameteric models NeuralLM with their count based \inf-gram method.

The 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.
strength_weakness: strength_weakness: (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.
(2) Lack of scaling law analysis with the impact of the training corpus (data) on perplexity.
questions: questions: (1) Can you comment or possibility of extending the agreement analysis as a basis for machine detection of human writing?

(2) Would extending the training corpus of the ngrams follow a scaling law trend?


(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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
paper_summary: paper_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.

Strengths:
* Shows that an n-gram model can be scaled to substantially large corpora with trillions of tokens.
* Shows that an n-gram model can yield perplexity improvements when combined with neural LMs
* 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. 

Weaknesses:
* There are some critical metrics which are not reported in the paper
e.g. next token prediction for neural LM, perplexity of the infini-gram by itself
*  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
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/rnn_ctxt.pdf
* The paper does not report comparison with other non-parametric approaches such as kNN LMs (Khandelwal et al. 2020)
strength_weakness: strength_weakness: * The paper does not report key metrics such as next-token prediction accuracy of neural LM, the perplexity of infini-gram LM by itself.
* The paper does not compare the proposed approach to other non-parametric LM approaches such as the kNN LM (Khandelwal et al)
* 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: questions: * "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"
It is unclear how this finding is related to infini-gram. 
*  Figure 3: what is the next token prediction accuracy for neural LM?
paper_summary: paper_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).
strength_weakness: strength_weakness: 1. The model proposed in the paper lacks practical experiments, making it difficult to see its future prospects.
questions: questions: 1. Compared to LLMs, besides calculating PPL, in what scenarios can the infinity ngram model apply?
2. How can the Ngram model complement LLMs?
3. Is it possible to directly generate text like auto regressive model?
4. How does the generalization of the Ngram model?

Comments: comment: Thank you for your response. Thanks for such an interesting paper
Thank you for your response. I agree that the research direction is very relevant and that there could be use cases with the need for such models. I don’t see a reason to change the score.
Thanks to the authors for providing additional details on metrics and answering my questions. I have increased my scores.