Evaluating n -Gram Novelty of Language Models Using Rusty- DAWG (2024)

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 despite an explosion of new applications of language models (lms), a core question about lms as text generators has not been fully answered: how novel is the text they generate compared to their training corpus? this question has both scientific value and practical relevance for lm deployment. from a scientific perspective, language understanding is often theorized as hinging on compositionality, meaning that an infinite range of meanings can be expressed by combining a small set of words or morphemes. if lms were largely copying sentences or spans they had seen before, this would suggest they cannot compositionally generate new sentences like humans can. from a societal perspective, the novelty of lm-generated text may also be relevant to legal questions of whether copyrighted materials can be used in lm pretraining data. for instance, a lawsuit between the new york times and openai (ongoing at the time of writing) hinges on the legal ambiguity of whether including copyrighted material in training data is allowed under fair use @xcite . scientific evaluation of copying behavior in lms may help guide the resolution of such questions. in past work, @xcite evaluated the novelty of text generated by sampling from small lms, finding that small n-grams in lm-generated text are less novel than in validation text, though larger n-grams are more novel. however, @xcite 's lms were trained on webtext (40 gb; @xcite , which is 3% of the size of the pile (1254 gb; @xcite , which is more representative of recent pretraining datasets. thus, it is unclear how their conclusions would transfer to larger-scale, modern lms. in this work, we evaluate the n-gram generation novelty of lms of varying sizes trained on large-scale web data. specifically, we measure the proportion of generated n-grams that are novel w.r.t. the training set across many n, which we call n-novelty. scaling the analysis of n-novelty to large corpora is challenging because measuring large-n-gram statistics over large corpora is infeasible when implemented naively. to solve this problem, we develop rusty-dawg, a search tool that uses the compacted directed acyclic word graph @xcite data structure for arbitrarylength n-gram matching over a corpus in constant time w.r.t. the corpus size and linear w.r.t the query size. while similar approaches were previously applied to genome data, we develop new algorithms for inference and extending the cdawg with frequency information, and we are the first, to our 1. we find large n-grams (@xmath1, though small n-grams (@xmath2, section 5.1). ## operationalizing novelty with n-grams there are different ways to measure lm generation novelty: one could assess the verbatim overlap between the text and training data @xcite or attempt to capture semantic and syntactic novelty @xcite . we target verbatim novelty, which is understudied at large model scale and conceivably provides an upper bound on more semantic notions of novelty (any instance of verbatim repetition likely also constitutes semantic repetition). we formalize verbatim novelty via two n-gram-based metrics: n-novelty and non-novel suffix length (nnsl). nnsl. we propose a new measure of aggregate novelty across different values of n. we define nnsl at token i of q as the length of the longest suffix of q[: i] that appeared in corpus c. we then aggregate with mean or max. example. let @xmath3, where $ is a document boundary. query @xmath4, 2-gram novelty 2/4 (oy and yd are novel), 3-gram novelty 2/3 (only llo is non-novel), and 4-gram novelty 2/2. the nnsl at each position is ⟨1, 2, 3, 0, 1⟩, with mean 1.4 and max 3. we intuitively demonstrate this example in figure 1a . ## measuring novelty with cdawgs naively computing our novelty metrics is prohibitively expensive over a large pretraining corpus like the pile (334b tokens). to make the searches fast, we use a compacted directed acyclic word graph (cdawg; @xcite , a data structure which returns the nnsl at each position in q against c in constant time (w.r.t. the size of c), and linear time (w.r.t. the size of q), from which nnovelty can be computed. we describe how to compute nssl using cdawg in appendix a. this constant-time querying is crucial for our application of searching the pile. we first discuss querying cdawgs (section 3.1), then their memory costs (section 3.2), their construction (section 3.3), and our open-source implementation (section 3.4). ## discussion a note on generation quality. in this work, we focus on quantifying n-gram novelty in model generations with respect to the model's training data. one confounding factor that may influence the cause of novelty in such generations is the quality of the text. for example, consider a model that generates the sequence "n-gram n-gram n-gram n-gram." this sequence is of low quality and is unlikely to appear in a corpus (it does not appear in dolma), making it a novel 4-gram. investigating how n-gram novelty interacts with text quality is left for future work. other cdawg use cases. several recent studies have explored memorization during training @xcite . these studies performed interventions on the data used for training lms at different checkpoints to study the effect of model size, training step, etc. on memorization. since cdawg is constructed sequentially, future research could leverage this property to mirror the order in which the data was presented to the model during training. this would enable the use of cdawgs for studying how novelty evolves over the course of pretraining for a specific data ordering. ## conclusion we introduce rusty-dawg, an efficient index for finding unbounded length n-gram overlap against a pretraining corpus whose runtime is independent of the corpus size. using rusty-dawg, we show that, at large n, pythia generates less novel n-grams than novel human-written text. we also find that increasing model size, constrained decoding (e.g., with temperature 0), or prompting with training data decrease novelty -in particular, low temperature has a dramatic effect. finally, more frequent training n-grams are completed by lms with lower loss, suggesting lms are more prone to memorizing frequent n-grams. we hope rusty-dawg enables further analysis of pretraining data as well as decontamination @xcite and retrieval language modeling @xcite research.