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.
Introduction
Researchers have long debated whether Large Language Models (LLMs) are truly creative or just "stochastic parrots" that repeat their training data. As LLMs become ubiquitous, two major questions have emerged. Scientifically, do these models actually understand compositionality, or are they just retrieving and stitching together long sequences they’ve already seen? Legally and ethically, to what extent do models output copyrighted material from their training sets?
Measuring this "novelty" is computationally challenging. Searching for every possible $n$-gram across a trillion-token dataset like The Pile using naive methods is too slow. This paper introduces Rusty-DAWG, a high-performance tool that uses a specialized data structure to find verbatim overlaps between generated text and massive datasets in constant time.
Methodology: Rusty-DAWG and the CDAWG
The authors developed Rusty-DAWG, a library written in Rust designed for massive-scale $n$-gram search. At its heart is the Compacted Directed Acyclic Word Graph (CDAWG). Unlike a standard suffix array, a CDAWG allows for "unbounded-length" $n$-gram searches. It can determine if a sequence exists in the training data in time proportional only to the length of the query, regardless of the reference corpus size.
The study utilizes the Pythia suite (70M to 12B parameters) trained on The Pile (334B tokens). To establish baselines, they use the Pile validation set and Dolma, a dataset of text written after the Pile's cutoff date, representing a "clean" human-written baseline. They define two key metrics: $n$-novelty (the percentage of generated $n$-grams that never appeared in training) and NNSL (Non-Novel Suffix Length), which measures the longest verbatim match from the training set ending at any given token.
Key Results and Insights
The Novelty Cross-Over
A significant finding is the "novelty cross-over." For very small sequences ($n \le 4$), LLMs are actually more novel than humans—likely due to the generation of unlikely or "gibberish" combinations. However, for $n > 4$, the trend flips: LLMs become significantly less novel than humans, frequently outputting long verbatim strings from their training data.
Scaling and Decoding Effects
The "stochastic parrot" tendency scales with model size. The mean NNSL (how much the model copies on average) increases linearly with the log of the model size. This suggests that larger models don't just "know" more; they memorize more verbatim. Furthermore, constrained decoding strategies like Beam Search or low-temperature sampling drastically reduce novelty. At a beam size of 8, the model essentially becomes a retrieval engine, often copying massive chunks of training documents verbatim.
Frequency Bias and Contamination
Models are much better at completing $n$-grams they saw frequently during training. The loss for $n$-grams found in the training set is roughly 50% lower than for those that aren't. Additionally, the study found that "held-out" data is often contaminated; 25% of 1,000-token documents in the Pile's validation set share at least one 50-gram with the training set.
Conclusion
Rusty-DAWG reveals that while LLMs are good at mixing small words, they frequently copy long strings of text, a tendency that worsens as models get larger or decoding strategies become more restrictive. While this study focuses on verbatim matches, it provides a crucial foundation for understanding memorization in LMs. Future work could extend this to semantic novelty and explore the evolution of novelty during the training process.
Summary updated