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

Thanks for your feedback! We appreciate your recognition of our contributions in scaling n-gram LMs and using them to enhance neural LLMs.

[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.

[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.

[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.

[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.

Thanks for recognizing the values in scaling n-gram LMs and their effectiveness to performance improvements and analysis.

[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”).

• Accuracy of next-token prediction:
  • Neural-only: 62%, 63%, and 65%, with Llama-2 7B, 13B, and 70B, respectively
  • Neural + ∞-gram: 66%, 67% and 69%, with Llama-2 7B, 13B, and 70B, respectively
  • ∞-gram only: 47%
• Consistent with the perplexity results, ∞-gram supplements neural LMs, although using ∞-gram alone does not outperform neural LMs.
• 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).
• We highlight that ∞-gram alone does not outperform neural LMs; rather, ∞-gram supplements neural LLMs, making smaller LLMs comparable to larger LLMs.

[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).

[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.

[RR3] Error analysis: We did some qualitative analyses, and found that ∞-gram is often good at completing multi-token words (e.g., hippopotamus, correctly predicted tokens are bolded), 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. We’ll include this analysis in the next revision.

[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.

Thanks to the authors for providing additional details on metrics and answering my questions. I have increased my scores.

Thanks for recognizing the novelty of our method, which enabled training n-gram LMs at unprecedented scale.

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.

In 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.

We really appreciate your recognition of our paper, especially the applications that may be enabled by the technology we develop.

Here is our response to your questions:

[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.

[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.

[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.