Evaluating $n$-Gram Novelty of Language Models Using Rusty-DAWG

William Merrill, Noah A. Smith, Yanai Elazar

TL;DR

Researchers have introduced Rusty-DAWG, a high-performance tool that enables constant-time search for arbitrary-length $n$-grams across massive datasets like the 334B-token Pile. Their analysis reveals that while large language models (LLMs) are more "creative" with short word combinations than humans, they are significantly more likely to verbatim copy longer sequences (n > 4) from their training data—a tendency that worsens as models grow larger or decoding strategies become more constrained.

What Problem Does This Paper Address?

The "stochastic parrot" debate centers on whether LLMs truly understand compositionality or if they are simply sophisticated copy-pasters. Quantifying this is difficult because searching for every possible $n$-gram in a terabyte-scale training corpus is a computational nightmare.

Previous studies were limited to small models and datasets. This paper tackles the challenge of measuring verbatim novelty at scale: how much of what an LLM generates is actually "new" versus a direct excerpt from its training history? This has major implications for both scientific understanding of model generalization and legal questions surrounding copyright and fair use.

Methods

The authors developed Rusty-DAWG, an open-source Rust library built on the Compacted Directed Acyclic Word Graph (CDAWG).

Unlike standard suffix arrays that require logarithmic time to search, a CDAWG allows for searching a query string in time linear to the query length ($O(|Q|)$) and constant time relative to the corpus size ($|C|$). This efficiency allowed the team to index the entire 334B-token Pile.

Figure 1: Illustration of CDAWG and resulting novelty curves with character-level tokenization for simplicity.

They introduced two primary metrics:

  1. $n$-novelty: The proportion of $n$-grams in a generated text that never appeared in the training set.
  2. Non-novel Suffix Length (NNSL): At any given token, how long is the longest suffix that appeared in the training corpus?

Datasets

  • Training Corpus: The non-deduplicated version of The Pile (334B tokens).
  • Models: The Pythia suite, ranging from 70M to 12B parameters, all trained on The Pile.
  • Baselines:
    • Pile Validation Set: Used to check for data contamination.
  • Dolma: Specifically, Reddit and scientific texts written after the Pile's cutoff date to serve as a "clean" baseline for human-written novelty.

Key Insights and Ideas

  • The Crossover Point: LLMs exhibit a "novelty crossover." For very short sequences ($n \le 4$), models are actually more novel than humans, likely because they mix and match common words in slightly unusual ways. However, for $n > 4$, the models become significantly less novel, frequently lapsing into long strings of training text.
  • The Scaling Law of Copying: As models get bigger, they don't just get smarter; they get better at memorizing. The mean NNSL increases linearly with the log of the model size.
  • Decoding is a Double-Edged Sword: Strategies that improve text quality (like low temperature, top-p, or beam search) work by pruning low-probability tokens. Unfortunately, the highest-probability paths are often those the model has seen before, meaning "better" looking text is often less novel.
  • Frequency Bias in Evaluation: Models complete $n$-grams with much lower loss if those sequences appeared frequently in training. This suggests that benchmarks like MMLU might be measuring memorization of common phrasing rather than pure reasoning.

Key Results

The study found that Pythia-12B frequently generates 64-grams that appear tens of thousands of times in The Pile, often consisting of boilerplate code or licenses.

Figure 2: n-novelty curve for Pythia-12B with naive sampling. Compared to Dolma, LM-generated text is more novel for n > 4 and slightly less novel for n ≤4. The gap between the dark gray Dolma curve and the green Pythia-12B curve quantifies the novelty difference. LM-generated text is more novel than the Pile validation set across n-gram sizes due to contamination.

Quantitatively, the gap between the model and the human baseline (Dolma) is stark at higher $n$ values. Furthermore, the researchers discovered significant contamination in the standard Pile validation set: 2.4% of 1,000-token validation documents were exact matches for sequences found in the training data.

Figure 3: Both n-novelty and mean NNSL suggest larger LMs generate less novel text than smaller LMs.

Limitations and Future Work

The authors acknowledge that they focused strictly on verbatim novelty. A model could rewrite a training sentence using synonyms (semantic copying), which this $n$-gram approach would label as "novel."

Additionally, the memory overhead of CDAWGs is significant—roughly 29 bytes per corpus token—making it expensive to run without high-RAM clusters or fast NVMe storage. Future work could involve optimizing this data structure or using Rusty-DAWG to track how memorization develops epoch-by-epoch during the training process.

Summary updated

Abstract

How novel are texts generated by language models (LMs) relative to their training corpora? In this work, we investigate the extent to which modern LMs generate $n$-grams from their training data, evaluating both (i) the probability LMs assign to complete training $n$-grams and (ii) $n$-novelty, the proportion of $n$-grams generated by an LM that did not appear in the training data (for arbitrarily large $n$). To enable arbitrary-length $n$-gram search over a corpus in constant time w.r.t. corpus size, we develop Rusty-DAWG, a novel search tool inspired by indexing of genomic data. We compare the novelty of LM-generated text to human-written text and explore factors that affect generation novelty, focusing on the Pythia models. We find that, for $n > 4$, LM-generated text is less novel than human-written text, though it is more novel for smaller $n$. Larger LMs and more constrained decoding strategies both decrease novelty. Finally, we show that LMs complete $n$-grams with lower loss if they are more frequent in the training data. Overall, our results reveal factors influencing the novelty of LM-generated text, and we release Rusty-DAWG to facilitate further pretraining data research.
BibTeX
@inproceedings{merrill2024evaluating,
  author = {William Merrill and Noah A. Smith and Yanai Elazar},
  title = {{Evaluating $n$-Gram Novelty of Language Models Using Rusty-DAWG}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  doi = {10.18653/v1/2024.emnlp-main.800},
}
Figure