mlsanityData to 7 Oct 2026

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

arXiv 2406.13069 ↗First posted 18 Jun 2024cs.CL cs.AIcited by 24

Not on the map. Why?

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.

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

Builds on

24 of 44 references.

References · 24

  1. 2020Measuring Massive Multitask Language Understandingcited by 7,768
  2. 2019The Curious Case of Neural Text Degenerationcited by 2,881
  3. 2020The Pile: An 800GB Dataset of Diverse Text for Language Modelingcited by 2,346
  4. 2023Pythia: A Suite for Analyzing Large Language Models Across Training and Scalingcited by 1,734
  5. 2018Hierarchical Neural Story Generationcited by 1,182
  6. 2021GLM: General Language Model Pretraining with Autoregressive Blank Infillingcited by 1,026
  7. 2019Generalization through Memorization: Nearest Neighbor Language Modelscited by 788
  8. 2022GPT-NeoX-20B: An Open-Source Autoregressive Language Modelcited by 711
  9. 2021Deduplicating Training Data Makes Language Models Bettercited by 705
  10. 2020What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimationcited by 492
  11. 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 452
  12. 2022Deduplicating Training Data Mitigates Privacy Risks in Language Modelscited by 309
12 more
  1. 2018Targeted Syntactic Evaluation of Language Modelscited by 239
  2. 2022Data Contamination: From Memorization to Exploitationcited by 234
  3. 2024Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokenscited by 148
  4. 2023What's In My Big Data?cited by 129
  5. 2021How much do language models copy from their training data? Evaluating linguistic novelty in text generation using RAVENcited by 124
  6. 2022Autoregressive Search Engines: Generating Substrings as Document Identifierscited by 112
  7. 2022Preventing Verbatim Memorization in Language Models Gives a False Sense of Privacycited by 97
  8. 2024How Do Large Language Models Acquire Factual Knowledge During Pretraining?cited by 86
  9. 2023Paloma: A Benchmark for Evaluating Language Model Fitcited by 53
  10. 2024Standardizing the Measurement of Text Diversity: A Tool and a Comparative Analysis of Scorescited by 50
  11. 2017Linear-size CDAWG: new repetition-aware indexing and grammar compressioncited by 1
  12. 2024Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improvedcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 11; 2026: 7.

24 papers.

Sort:

By area:

  1. 2024Generalization v.s. Memorization: Tracing Language Models' Capabilities Back to Pretraining Datacited by 83
  2. 2024Detection and Measurement of Syntactic Templates in Generated Textcited by 44
  3. 2024AI as Humanity's Salieri: Quantifying Linguistic Creativity of Language Models via Systematic Attribution of Machine Text against Web Textcited by 40
  4. 2025Emergent Abilities in Large Language Models: A Surveycited by 34
  5. 2024Data Contamination Report from the 2024 CONDA Shared Taskcited by 19
  6. 2024Reverse Question Answering: Can an LLM Write a Question so Hard (or Bad) that it Can't Answer?cited by 13
  7. 2025Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Indexcited by 13
  8. 2025To model human linguistic prediction, make LLMs less superhumancited by 11
  9. 2025Linguistic Characteristics of AI-Generated Text: A Surveycited by 7
  10. 2025ParaPO: Aligning Language Models to Reduce Verbatim Reproduction of Pre-training Datacited by 6
  11. 2025Measuring LLM Novelty As The Frontier Of Original And High-Quality Outputcited by 5
  12. 2025Death of the Novel(ty): Beyond n-Gram Novelty as a Metric for Textual Creativitycited by 4
12 more
  1. 2025The Inverse Scaling Effect of Pre-Trained Language Model Surprisal Is Not Due to Data Leakagecited by 3
  2. 2026Interrupting the Loop: Periodic Subject Changes Raise Judged Surprise and Connection in Base Language Modelscited by 2
  3. 2025Low-Perplexity LLM-Generated Sequences and Where To Find Themcited by 1
  4. 2026The Proxy Presumption: From Semantic Embeddings to Valid Social Measurescited by 1
  5. 2026Measuring Form and Function in Language Modelscited by 1
  6. 2026A Pre-Training Analogue of Grokking in Language Models: Tracing Delayed Grammatical Generalizationcited by 1
  7. 2026Tokenizer-Agnostic Engram Modulecited by 1
  8. 2024Black Big Boxes: Tracing Adjective Order Preferences in Large Language Modelscited by 0
  9. 2025Readability ne Learnability: Rethinking the Role of Simplicity in Training Small Language Modelscited by 0
  10. 2025LLM generation novelty through the lens of semantic similaritycited by 0
  11. 2026A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarkscited by 0
  12. 2026GENIE: A Fine-Grained Measure for Noveltycited by 0