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.
They introduced two primary metrics:
- $n$-novelty: The proportion of $n$-grams in a generated text that never appeared in the training set.
- 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.
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.
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