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

arXiv: https://arxiv.org/abs/2406.13069 · HTML: https://mlsanity.com/paper/2406.13069/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 44 references that are in the map.
- First posted on arXiv 18 Jun 2024.

## Builds on (most cited first, 24 of 24)

- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [GLM: General Language Model Pretraining with Autoregressive Blank Infilling](https://mlsanity.com/paper/2103.10360/) (2021)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Deduplicating Training Data Makes Language Models Better](https://mlsanity.com/paper/2107.06499/) (2021)
- [GPT-NeoX-20B: An Open-Source Autoregressive Language Model](https://mlsanity.com/paper/2204.06745/) (2022)
- [What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation](https://mlsanity.com/paper/2008.03703/) (2020)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Deduplicating Training Data Mitigates Privacy Risks in Language Models](https://mlsanity.com/paper/2202.06539/) (2022)
- [Targeted Syntactic Evaluation of Language Models](https://mlsanity.com/paper/1808.09031/) (2018)
- [Data Contamination: From Memorization to Exploitation](https://mlsanity.com/paper/2203.08242/) (2022)
- [Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens](https://mlsanity.com/paper/2401.17377/) (2024)
- [What's In My Big Data?](https://mlsanity.com/paper/2310.20707/) (2023)
- [How much do language models copy from their training data? Evaluating linguistic novelty in text generation using RAVEN](https://mlsanity.com/paper/2111.09509/) (2021)
- [Autoregressive Search Engines: Generating Substrings as Document Identifiers](https://mlsanity.com/paper/2204.10628/) (2022)
- [Preventing Verbatim Memorization in Language Models Gives a False Sense of Privacy](https://mlsanity.com/paper/2210.17546/) (2022)
- [How Do Large Language Models Acquire Factual Knowledge During Pretraining?](https://mlsanity.com/paper/2406.11813/) (2024)
- [Paloma: A Benchmark for Evaluating Language Model Fit](https://mlsanity.com/paper/2312.10523/) (2023)
- [Standardizing the Measurement of Text Diversity: A Tool and a Comparative Analysis of Scores](https://mlsanity.com/paper/2403.00553/) (2024)
- [Linear-size CDAWG: new repetition-aware indexing and grammar compression](https://mlsanity.com/paper/1705.09779/) (2017)
- [Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved](https://mlsanity.com/paper/2401.04509/) (2024)

## Built on by (most cited first, 25 of 25)

- [Generalization v.s. Memorization: Tracing Language Models' Capabilities Back to Pretraining Data](https://mlsanity.com/paper/2407.14985/) (2024)
- [Detection and Measurement of Syntactic Templates in Generated Text](https://mlsanity.com/paper/2407.00211/) (2024)
- [AI as Humanity's Salieri: Quantifying Linguistic Creativity of Language Models via Systematic Attribution of Machine Text against Web Text](https://mlsanity.com/paper/2410.04265/) (2024)
- [Emergent Abilities in Large Language Models: A Survey](https://mlsanity.com/paper/2503.05788/) (2025)
- [Data Contamination Report from the 2024 CONDA Shared Task](https://mlsanity.com/paper/2407.21530/) (2024)
- [Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Index](https://mlsanity.com/paper/2506.12229/) (2025)
- [Reverse Question Answering: Can an LLM Write a Question so Hard (or Bad) that it Can't Answer?](https://mlsanity.com/paper/2410.15512/) (2024)
- [To model human linguistic prediction, make LLMs less superhuman](https://mlsanity.com/paper/2510.05141/) (2025)
- [Linguistic Characteristics of AI-Generated Text: A Survey](https://mlsanity.com/paper/2510.05136/) (2025)
- [Measuring LLM Novelty As The Frontier Of Original And High-Quality Output](https://mlsanity.com/paper/2504.09389/) (2025)
- [ParaPO: Aligning Language Models to Reduce Verbatim Reproduction of Pre-training Data](https://mlsanity.com/paper/2504.14452/) (2025)
- [The Inverse Scaling Effect of Pre-Trained Language Model Surprisal Is Not Due to Data Leakage](https://mlsanity.com/paper/2506.01172/) (2025)
- [Death of the Novel(ty): Beyond n-Gram Novelty as a Metric for Textual Creativity](https://mlsanity.com/paper/2509.22641/) (2025)
- [Interrupting the Loop: Periodic Subject Changes Raise Judged Surprise and Connection in Base Language Models](https://mlsanity.com/paper/2608.19893/) (2026)
- [Low-Perplexity LLM-Generated Sequences and Where To Find Them](https://mlsanity.com/paper/2507.01844/) (2025)
- [The Proxy Presumption: From Semantic Embeddings to Valid Social Measures](https://mlsanity.com/paper/2605.07409/) (2026)
- [Measuring Form and Function in Language Models](https://mlsanity.com/paper/2605.28616/) (2026)
- [A Pre-Training Analogue of Grokking in Language Models: Tracing Delayed Grammatical Generalization](https://mlsanity.com/paper/2606.00230/) (2026)
- [Tokenizer-Agnostic Engram Module](https://mlsanity.com/paper/2607.29065/) (2026)
- [Black Big Boxes: Tracing Adjective Order Preferences in Large Language Models](https://mlsanity.com/paper/2407.02136/) (2024)
- [Readability ne Learnability: Rethinking the Role of Simplicity in Training Small Language Models](https://mlsanity.com/paper/2510.13915/) (2025)
- [LLM generation novelty through the lens of semantic similarity](https://mlsanity.com/paper/2510.27313/) (2025)
- [A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks](https://mlsanity.com/paper/2605.28556/) (2026)
- [GENIE: A Fine-Grained Measure for Novelty](https://mlsanity.com/paper/2606.12790/) (2026)
- [Evaluating LLM Creativity through Long-Tail Performance](https://mlsanity.com/paper/2610.12998/) (2026)

## Abstract (arXiv)

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.