Deduplication: Exact, Near-Duplicate, and Substring Methods

Training a large language model costs tens of millions of dollars and months of compute. The decisions you make about your training data determine whether that investment produces a capable model or an expensive mistake. One of the most impactful decisions is deduplication: removing copies and near-copies of documents before they enter the training set.

The intuition seems straightforward. If your corpus contains the same Wikipedia article scraped from five hundred different mirror sites, the model will see that content five hundred times. It will memorize it rather than learn from it. The model's parameters, instead of encoding broadly useful language patterns, become increasingly optimized to reproduce those repeated documents verbatim. Duplicate-heavy training data creates problems beyond storage: it degrades generalization, inflates benchmark scores without improving real-world capability, and causes models to hallucinate by confidently reproducing memorized text in inappropriate contexts.

The research community has quantified these effects precisely. Lee et al. (2022) found that training on a single-deduplicated version of C4 versus an 8-times-deduplicated version produced measurable differences in memorization rates, perplexity, and downstream task performance. The LLaMA models trained on deduplicated data consistently outperformed alternatives on standardized benchmarks despite using fewer total tokens, because unique tokens carry more information per training step than repeated ones. The practical conclusion is unambiguous: deduplication is not an optional cleanup step but a core investment in training effectiveness.

Deduplication sits at the fourth step of the data curation pipeline. After web crawling collects raw pages and document extraction strips boilerplate HTML into clean text, you have a corpus with structure and content but potentially massive redundancy. Deduplication cleans that redundancy out so that quality filtering and toxicity removal in subsequent steps operate on a corpus where every document earns its place on its own merits rather than on the merits of how many copies of it exist.

This chapter covers the full spectrum of deduplication strategies: exact hashing for perfect copies, Jaccard similarity over character shingles for near-duplicates, suffix array-based substring deduplication for repeated passages within otherwise unique documents, MinHash for scalable near-duplicate detection, and the systems engineering challenges that arise when you need to apply these methods to trillions of tokens on hundreds of machines.

Before diving into algorithms, it is worth understanding just how pervasive duplication is in web-scale corpora. A raw Common Crawl snapshot contains hundreds of billions of tokens, but a surprising fraction of that content is duplicated. Legal boilerplate appears on millions of pages. Navigation menus, cookie consent notices, and footer text repeat across entire domains. News articles get syndicated across dozens of outlets with identical or near-identical text. Stack Overflow answers get scraped into tutorial sites, StackExchange clones, and programming forums. Books that entered the public domain appear on Project Gutenberg, Archive.org, and hundreds of derivative sites simultaneously.

The scale of this problem is larger than most practitioners expect. When the EleutherAI team deduplicated the Pile, a 825 GB text corpus assembled from diverse sources, they found that roughly 30% of its raw content was duplicate or near-duplicate material. The RedPajama dataset preparation process applied aggressive deduplication across all seven of its component datasets and found similar rates. In some individual sources like GitHub code repositories, duplication rates can exceed 50%, because developers fork repositories, copy boilerplate license headers, and reuse utility functions across thousands of projects.

Carlini et al. (2021) demonstrated that GPT-2 would verbatim reproduce sequences from its training data when prompted with the beginning of those sequences. The sequences most likely to be reproduced were the most duplicated ones in the training set. This has serious practical implications: a model that memorizes legal terms of service or personal information scraped from web pages represents a privacy and liability risk in addition to being a technical shortcoming. From a legal standpoint, a model that can output a full copyrighted text on demand creates exposure under copyright law. From a safety standpoint, a model trained on chat logs containing personal data may reconstruct those conversations when prompted with fragments.

Duplication also distorts what the model learns to value. A language model trained on data where tech blog posts outnumber medical literature by a hundred to one will develop strong priors for tech blog prose style and vocabulary. If those tech blog posts are themselves duplicated across aggregator sites, the effective imbalance is even worse than it appears from document counts alone. Deduplication is therefore partly a data balance problem as well as a storage optimization.

There is also a subtler effect on training dynamics. Stochastic gradient descent treats each training example as an independent sample from the data distribution. When the same document appears repeatedly in the training set, the model's gradient updates reinforce that document's patterns at the expense of all other patterns. In the extreme case, a document appearing thousands of times effectively becomes the training objective for a portion of the model's parameters. The model stops being a general language model and starts becoming a specialized reproducer of that document. This dynamic is particularly dangerous because it is not reflected in training loss: a model that memorizes repeated documents can achieve low perplexity on a validation set constructed from the same corpus, yet perform poorly on truly novel text.

The relationship between duplication and benchmark performance deserves special attention. Many popular benchmarks draw from the same web sources that constitute training data. If a question-answer pair or its near-duplicate appears thousands of times in training data, the model may be scoring well on the benchmark by retrieval rather than by reasoning. Deduplication both reduces this benchmark inflation and forces models to achieve good benchmark performance through generalization to unseen examples.

The simplest form of deduplication removes documents that are bit-for-bit identical. Given a document $d$, you compute a deterministic hash function $h(d)$ and store the hash in a lookup set. If you encounter the same hash again, you discard the duplicate and keep the original.

Exact deduplication works on two levels: the document level and the line or paragraph level.

At the document level, you compute a single hash for the entire document and check it against a set of previously seen hashes. For a document $d$ consisting of a sequence of bytes, we want a compact fingerprint that uniquely identifies its content. SHA-256 maps the document to a fixed-size bit string:

where:

• $d$: the document represented as a sequence of bytes
• $\text{SHA256}$: the SHA-256 cryptographic hash function
• $\{0,1\}^{256}$: the output space of 256-bit binary strings, giving $2^{256} \approx 10^{77}$ possible fingerprints

You maintain a global set $S$ of seen fingerprints. For each incoming document:

1. Compute $h(d)$
2. If $h(d) \in S$: discard $d$ as a duplicate
3. If $h(d) \notin S$: add $h(d)$ to $S$ and keep $d$

The collision probability for SHA-256 is negligibly small, approximately $2^{-128}$ for any two distinct documents in a corpus of practical size, so treating equal hashes as identical documents is safe in practice. MD5 has known theoretical collisions but produces false positives so rarely in practice that most deduplication pipelines use it for speed. The 128-bit MD5 output is half the size of SHA-256, which matters when your lookup set needs to hold fingerprints for billions of documents: a billion MD5 fingerprints require about 16 GB of memory for the fingerprint store alone, compared to 32 GB for SHA-256.

An implementation requirement is normalization before hashing. Raw documents from different sources may encode the same content with different whitespace, Unicode normalization forms (NFC vs NFD), or HTML entities. Two copies of the same article might differ only in whether smart quotes are used versus straight quotes, or whether newlines are \r\n versus \n. If you hash without normalizing, these formatting differences will cause you to keep both copies, defeating the purpose. This is a deceptively common failure mode: a team that believes their deduplication pipeline is working well may be keeping thousands of near-identical copies that differ only in invisible whitespace or encoding artifacts.

Standard normalizations applied before hashing include:

• Lowercasing the entire text
• Stripping leading and trailing whitespace from each line
• Collapsing multiple consecutive whitespace characters to a single space
• Unicode normalization to NFC (Canonical Decomposition followed by Canonical Composition)
• Stripping HTML entities

The choice of normalization is a policy decision. If you apply aggressive normalization (stripping all punctuation, collapsing to bare words), you will catch more variants of the same content but also risk merging documents that are materially distinct. Most production pipelines normalize conservatively, targeting only the kinds of formatting variation that arise from scraping rather than from content differences.

Document-level exact deduplication catches only perfect or near-perfect copies. It misses the common case where the same article appears with slightly different headlines, updated timestamps, or added comments. For that, you need fuzzy matching.

A subtler form of exact deduplication operates at the line level. Rather than hashing entire documents, you hash individual lines and track which line hashes appear frequently across the corpus. Lines that appear in more than some threshold fraction of documents are removed from all documents.

This catches repeated boilerplate that is not enough to trigger document-level matching. A cookie consent notice appears on millions of pages but constitutes only a few lines in each document. Removing those lines cleans the corpus without discarding the entire document.

The C4 dataset used line-level exact deduplication as one of its core cleaning steps, removing any three-sentence span that appeared more than once in the corpus. This removed approximately 70% of the raw text from Common Crawl before the dataset was released, an indication of just how much redundant boilerplate exists in raw web data. The magnitude of that reduction is striking: the majority of the raw Common Crawl content, by volume, is repeated content. The unique, high-value text is a minority of what you scrape.

Line-level deduplication requires a two-pass algorithm. In the first pass, you collect all line hashes and count their frequencies across the corpus. In the second pass, you revisit each document and remove any line whose frequency exceeds your threshold. This two-pass structure is necessary because you cannot know a line's global frequency until you have seen the entire corpus.

The trade-off is that aggressive line-level deduplication can break document coherence. If you remove every line that appears in more than 1% of documents, you might inadvertently remove common transition phrases, list formatting conventions, or formulaic sentence starters that appear frequently but carry legitimate semantic content in context. The resulting documents may have coherent paragraphs separated by visible gaps where lines were removed, which the model then learns to produce. This is a real problem that appeared in some early C4-trained models, which would occasionally produce text with strange rhythmic gaps corresponding to places where boilerplate lines had been excised.

Most real-world duplication is not exact. Articles get paraphrased, headlines change, paragraphs get reordered, and syndication services add or remove bylines and footers. To catch these near-duplicates, you need a similarity measure that tolerates small differences.

The standard approach uses Jaccard similarity over sets of character n-grams. The appeal of this approach is its simplicity and its direct connection to what we intuitively mean by "similar content": two documents that share most of their character sequences are probably expressing similar information, even if the exact wording differs.

Given a document $d$, you convert it to a set of overlapping character sequences of length $k$, called k-shingles or k-grams. For example, with $k = 5$, the string "the cat sat" produces shingles: {"the c", "he ca", "e cat", " cat ", "cat s", "at sa", "t sat"}.

Formally, the shingle set of document $d$ with shingle size $k$ is defined as all substrings of length $k$ that appear in $d$:

where:

• $d$: the document as a string of characters
• $k$: the shingle length (number of characters per shingle)
• $d[i : i+k]$: the substring of $d$ starting at position $i$ with length $k$
• $|d|$: the total length of the document in characters
• $S_k(d)$: the resulting set of unique k-character substrings (a set, not a multiset, so duplicates within one document are collapsed)

The choice of character-level shingles rather than word-level n-grams is deliberate. Word-level shingles are sensitive to tokenization choices and vocabulary differences across languages. Character-level shingles are language-agnostic and naturally capture morphological variations (for example, "running" and "runner" share most of their characters). They also gracefully handle misspellings and OCR errors, where individual words may differ but most character sequences remain shared.

Why convert a document to a set rather than a sequence? Because sets abstract away the positions of shingles and focus entirely on their presence or absence. Two documents that express the same ideas in different paragraph orders would have very different sequence representations, but highly overlapping set representations. For deduplication, we care about content overlap, not structural alignment, so sets are the right data model.

Common choices for $k$ range from 5 to 10. Shorter shingles ($k=3$ or $k=4$) are too common across unrelated documents, producing many false positives: every document in English contains the shingle "the" repeatedly, so short shingles create apparent similarity between unrelated texts. Longer shingles ($k=15$ or $k=20$) become too document-specific, missing near-duplicates that differ in small ways. The sweet spot at $k=5$ to $k=8$ produces shingles specific enough to carry content signal but common enough to appear across near-duplicate pairs even when wording differs slightly.

The key insight behind Jaccard similarity is that two documents sharing most of their content will share most of their shingles. Representing documents as shingle sets lets us quantify how much their content overlaps. Given two documents represented as shingle sets $A$ and $B$, Jaccard similarity measures the fraction of shingles they share:

where:

• $A$: the shingle set of the first document
• $B$: the shingle set of the second document
• $|A \cap B|$: the number of shingles that appear in both documents (the intersection)
• $|A \cup B|$: the total number of distinct shingles across both documents (the union)
• $J(A, B)$: the similarity score, ranging from 0 (no shared shingles) to 1 (identical shingle sets)

The denominator normalizes by the union rather than by either set's size alone, which is important. If you normalize by the smaller set's size, a short document that is entirely contained within a long document would receive a similarity of 1.0, even if the long document has substantial additional content. Jaccard's union normalization penalizes both asymmetry and total mismatch: documents are judged similar only when their shared content is large relative to everything both documents contain.

To build intuition, consider two documents $A$ and $B$ where $|A \cap B| = 40$ and $|A \cup B| = 50$. The Jaccard similarity is $40/50 = 0.8$, meaning 80% of all shingles appearing in either document appear in both. This suggests the documents share most of their content. If instead $|A \cap B| = 10$ and $|A \cup B| = 100$, the Jaccard similarity drops to $0.1$, indicating the documents share only 10% of their combined vocabulary. These interpretations are intuitive and directly meaningful for deduplication decisions.

Documents with Jaccard similarity above some threshold $\tau$ (typically 0.7 to 0.8 for deduplication) are treated as near-duplicates, and one copy is discarded.

The problem with computing Jaccard similarity directly is the cost. For a corpus of $N$ documents, a naive pairwise comparison requires $O(N^2)$ similarity computations. At 100 million documents, that is $5 \times 10^{15}$ comparisons. Even at one million comparisons per second, completing the computation would take more than 150 years. This is where MinHash comes in: a locality-sensitive hashing technique that estimates Jaccard similarity efficiently without comparing all pairs directly. We cover MinHash in full detail in the next chapter, but we introduce its key ideas in the Deduplication at Scale section below.

The deduplication strategies we have discussed so far operate on whole documents. Either an entire document is too similar to another and gets discarded, or it is kept in full. But duplication does not always occur at the document level.

Consider a web-crawled corpus containing:

• News article A: a 1000-word article about climate change
• News article B: a different 1000-word article about climate change that happens to contain a 400-word quote from a famous report

Both articles are unique at the document level. Their Jaccard similarity might be 0.15, well below any reasonable deduplication threshold. Yet article B contains a 400-word passage that appears verbatim in hundreds or thousands of other documents in the corpus, because it is a widely quoted passage.

When you train a model on this data, it will see that 400-word passage disproportionately often, not because any individual document is a duplicate, but because the passage recurs across many documents. The result is the same memorization problem, just distributed differently. The model learns to associate certain prompts with that memorized passage, because regardless of what document context surrounds the passage, the passage itself is always the same. This can manifest as the model producing accurate-sounding but unhelpfully generic responses on topics where the training data was dominated by frequently quoted boilerplate.

Substring deduplication addresses this by finding and removing repeated passages within documents, even when those documents are unique at the document level.

Lee et al. (2022) introduced suffix array-based substring deduplication, which became the method used to produce the C4 and T5 training data. The algorithm works by finding all substrings of length at least $L$ (typically 50 to 100 tokens) that appear in more than one document in the corpus.

A suffix array is a data structure that allows efficient substring search across an entire corpus. If you concatenate all documents into a single string $T$ separated by a special delimiter character, the suffix array $SA$ is a permutation of $\{0, 1, \ldots, |T|-1\}$ such that the suffixes $T[SA[0]:], T[SA[1]:], \ldots, T[SA[|T|-1]:]$ are in lexicographic order.

To understand why sorting suffixes is useful, consider what happens to two identical substrings when you sort all suffixes lexicographically. Two suffixes that start with the same long substring will be placed adjacent to each other in the sorted order, because their first $L$ characters are identical and thus sort identically. A linear scan over the sorted suffixes can then identify all pairs of suffixes that share a long common prefix, which corresponds to a long repeated substring in the original corpus.

The data structure that captures this prefix information is the Longest Common Prefix (LCP) array, constructed alongside the suffix array. The LCP array stores, for each consecutive pair of sorted suffixes, the length of their common prefix. Formally, $\text{LCP}[i]$ is the length of the longest common prefix between $T[SA[i-1]:]$ and $T[SA[i]:]$. Entries where $\text{LCP}[i] \geq L$ correspond to locations where a repeated passage of length at least $L$ exists. By scanning the LCP array, you can enumerate all such passages in linear time.

The advantage of suffix arrays is that they can be built in $O(|T| \log |T|)$ time and then scanned linearly to find all shared substrings. The disadvantage is memory: the suffix array for a trillion-character corpus requires on the order of terabytes of RAM, which forces you to use distributed suffix array construction or to shard the corpus and process shards independently. The Lee et al. implementation used a multi-stage approach: they sharded the corpus, built suffix arrays for each shard, merged the results to find cross-shard duplicates, and then applied the removals in a final pass.

Let us trace through a small example to make suffix arrays concrete. Suppose your corpus (after concatenation) contains the string:

The suffix array, after sorting all suffixes lexicographically, would place the suffix starting at position 0 ("machine learning is hard. machine...") adjacent to the suffix starting at position 26 ("machine learning is hard. deep..."), because both start with "machine learning is hard." The LCP value between these two consecutive sorted suffixes would be 25 (the length of "machine learning is hard."), which exceeds any reasonable threshold $L$, which identifies this as a duplicated passage.

In practice, the corpus is tokenized before building the suffix array, so the "characters" in $T$ are tokens rather than bytes. Token-level suffix arrays have the advantage of operating on a more semantically meaningful unit than bytes, at the cost of a larger alphabet (50,000 token types rather than 256 byte values).

The choice between document-level and substring-level deduplication involves a fundamental trade-off between aggressiveness and information loss.

Document-level deduplication is conservative. It discards entire documents only when they are nearly identical to another document. This means that even a 600-word unique document containing a 400-word duplicated passage survives the dedup step. The model trains on both the unique 200 words and the repeated 400 words, but you at least do not lose the unique content.

Substring deduplication is more aggressive. It removes the repeated passage from some documents (typically keeping one copy of each repeated passage across the corpus and removing it from all other occurrences). This can leave some documents with large gaps where passages were removed, which you must either stitch together carefully or address by discarding any document that lost more than some fraction of its content. Lee et al. used a threshold of 80%: if more than 80% of a document's content was flagged as duplicated passages, the entire document was discarded rather than left as a fragment.

The decision also involves a coverage argument. When you remove a passage from a document, you are reducing the number of contexts in which that passage appears. If the passage is a legitimate scientific finding cited across many papers, removing it from all but one document means the model learns that finding from fewer contexts, potentially reducing its robustness in understanding references to that finding. If the passage is a legal disclaimer appearing identically in thousands of contracts, removing it is clearly beneficial.

In practice, most large-scale data curation pipelines apply both: document-level near-duplicate detection first to remove the most egregious copies, followed by substring deduplication to clean up repeated passages within the surviving documents.

Let us work through a small example to make these concepts concrete. Consider a tiny corpus of five documents:

• D1: "The quick brown fox jumps over the lazy dog"
• D2: "The quick brown fox jumps over the lazy dog" (exact copy of D1)
• D3: "A quick brown fox leaped over the sleeping dog" (paraphrase of D1)
• D4: "Machine learning requires large amounts of training data"
• D5: "Machine learning requires large amounts of labeled data" (minor variation of D4)

Step 1: Exact deduplication. We hash each document after normalization:

• $h(D1) = h(D2)$ because the strings are identical after normalization
• $h(D3)$, $h(D4)$, $h(D5)$ are all different from each other and from $h(D1)$

Result: D2 is removed. We keep D1, D3, D4, D5.

Step 2: Near-duplicate detection with $k=5$ character shingles. The 5-shingles for D1 ("the quick brown fox...") and D3 ("a quick brown fox...") share many substrings like "quick", "uick ", "ick b", "ck br", etc. The documents differ primarily in the first character ("the " vs "a qu") and in a few words later on, but most of the character content is shared. Their Jaccard similarity over 5-shingles is noticeably above zero.

For D4 and D5, the only content difference is "training" versus "labeled". Both words have different character sequences, but the surrounding words ("large amounts of ", " data") are identical, and those surrounding characters contribute many shared shingles. The net effect is high Jaccard similarity because the differing segment is short relative to the shared segments.

With threshold $\tau = 0.5$, we would remove D3 (similar to D1) and D5 (similar to D4), leaving D1 and D4 as the deduplicated corpus. The exact cutoffs depend on the actual Jaccard values, which depend on document length and the specific character content. Shorter documents are more sensitive to small changes because the differing characters represent a larger fraction of the total content.

We will implement exact deduplication, Jaccard similarity computation, and a simple near-duplicate detection pipeline in Python. The implementation follows a natural progression: first, we build exact matching using cryptographic hashes; then we build fuzzy matching using shingles and Jaccard similarity; finally, we measure how aggressively different thresholds prune the corpus.

The exact deduplication function normalizes each document and computes its SHA-256 hash. Documents with the same hash are duplicates. The normalization step is the most important part: without it, two copies of the same article that differ only in whitespace or capitalization would pass through as distinct documents.

Exact deduplication caught both the identical copy and the whitespace variant because normalization strips leading and trailing whitespace before hashing. This is why normalization is a critical preprocessing step: two documents that look identical to a human but differ in a trailing space will have completely different SHA-256 hashes without normalization. In a production corpus of billions of documents, whitespace and encoding variants are not edge cases; they are the rule. Scrapers use different HTML parsers, different character encoding libraries, and different newline conventions. Normalization unifies these variations before the hash function ever runs.

Next, we implement the shingling function and Jaccard similarity computation. The shingling function slides a window of size $k$ across the normalized document, collecting all substrings. The Jaccard function then computes the overlap between any two such sets.

With similarity scores in hand, we can apply a threshold to decide which documents to remove. The standard approach is greedy: process documents in order, and when a near-duplicate is found, discard the later document. The earlier document survives because we want to process sources in decreasing quality order, keeping the best version.

The greedy approach processes documents sequentially and keeps the first document in each near-duplicate cluster. The order of processing matters: you typically want to process higher-quality sources first so that when you encounter a near-duplicate cluster, you keep the highest-quality version. In practice this means pre-sorting documents by quality signal (source domain, length, readability score) before running the greedy deduplication pass. Wikipedia articles, academic papers, and curated books should be processed before raw web pages, so that when a web page is a near-duplicate of a Wikipedia article, the web page is the one discarded.

A useful diagnostic is to plot how the corpus size shrinks at different similarity thresholds. Lower thresholds (0.1) are very aggressive and remove even loosely similar documents. Higher thresholds (0.9) are conservative and only remove near-identical documents. By sweeping over thresholds, you can understand the sensitivity of your pipeline to this hyperparameter and choose a value appropriate for your quality requirements.

Practitioners typically choose thresholds in the 0.7 to 0.8 range for character-based Jaccard similarity, but the right value depends on the corpus and the tolerance for false positives. In this deliberately noisy synthetic corpus, that conventional range is too conservative: changing 15% of characters destroys enough 5-shingle overlap that all copies remain. A news corpus, where articles frequently quote the same source material, may require a higher threshold to avoid over-removal. A code corpus, where many files are functional duplicates with minor variable renames, may benefit from a lower threshold. Understanding the nature of duplication in your specific corpus is essential before choosing a threshold.

The shingle size $k$ is another key parameter. Smaller shingles generate many common substrings, causing unrelated documents to appear similar. Larger shingles are more specific but may miss near-duplicates that differ in small sections. The plot below shows how shingle size affects the Jaccard scores for the same document pair at different levels of similarity.

Understanding the key parameters lets you tune deduplication appropriately for your corpus and use case.

• k (shingle size): Controls the granularity of near-duplicate detection. Values of 5 to 10 work well for character-level shingles. Smaller values increase false positives because short substrings appear frequently in any text. Larger values increase false negatives because long substrings are specific to particular phrasings. For short documents (under 200 characters), smaller $k$ values risk high false-positive rates; for long documents, larger $k$ values are safe.
• threshold ($\tau$): The Jaccard similarity threshold above which two documents are considered near-duplicates. Typical range is 0.7 to 0.8 for conservative deduplication and 0.5 to 0.6 for aggressive. Lowering the threshold removes more documents but risks removing materially distinct content. Raising it keeps more content but misses more near-duplicates. There is no universally correct value; the right threshold depends on the corpus and the application.
• normalization: The text normalization steps applied before hashing or shingling. Must be consistent across the entire corpus. Inconsistent normalization is a common source of deduplication failures, where the same document is kept in multiple variants because different preprocessing steps produced slightly different normalized forms.
• duplicate removal strategy: Whether to keep the first occurrence (greedy), keep the highest-quality version, or apply source-based priority. For most LLM training pipelines, keeping the highest-quality version is preferred, which requires computing quality scores before or alongside deduplication.

The naive near-duplicate detection algorithm is $O(N^2)$ in the number of documents, which is completely infeasible for web-scale corpora. Industrial deduplication pipelines use a combination of techniques to scale to billions of documents.

MinHash is the key technique that makes near-duplicate detection tractable at scale. Rather than computing Jaccard similarity directly between all pairs of documents, you compute a compact signature (a MinHash signature) for each document. Two documents with similar signatures are likely near-duplicates, and you only need to compare those candidate pairs.

The theoretical foundation of MinHash rests on a remarkable probabilistic guarantee. For any single hash function $h$ drawn from a min-wise independent family, and for any two sets $A$ and $B$:

where:

• $\min_{x \in A} h(x)$: the minimum hash value obtained by applying $h$ to every element of set $A$
• $J(A, B)$: the Jaccard similarity of the two sets
• The probability is taken over random draws of the hash function $h$

This identity says that the probability of the two sets having the same minimum hash value exactly equals their Jaccard similarity. The proof follows from the definition of Jaccard similarity: if we think of the union $A \cup B$ as a pool of shingles and apply a random hash function that assigns each shingle a unique random rank, then the minimum-ranked shingle in the pool is equally likely to come from $A$, from $B$, or from $A \cap B$. The minimum-ranked shingle comes from $A \cap B$ if and only if the minimums of $A$ and $B$ are equal, and the probability of that happening is $|A \cap B| / |A \cup B| = J(A, B)$.

By using $m$ independent hash functions and computing $m$ minimum hash values per document, you obtain a MinHash signature of length $m$ that is an unbiased estimator of Jaccard similarity. The estimation variance decreases as $m$ increases; in practice, $m = 128$ or $m = 256$ provides good accuracy with manageable signature size.

We cover MinHash in full mathematical detail in the next chapter, including Locality-Sensitive Hashing (LSH), which groups documents by their signature into buckets to avoid exhaustive pairwise comparison. The combination of MinHash signatures and LSH bucketing reduces the deduplication problem from $O(N^2)$ comparisons to a manageable number of comparisons within each bucket, making billion-document deduplication computationally feasible.

Once you have identified which pairs of documents are near-duplicates, you need to decide which member of each cluster to keep. The standard data structure for this is union-find (also called disjoint set union, or DSU).

Union-find maintains a forest of trees where each tree represents a cluster of near-duplicate documents. The algorithm proceeds in three phases. First, initialization assigns each document to its own singleton cluster by setting $\text{parent}[d] = d$ for all documents $d$. Second, for each near-duplicate pair $(d_i, d_j)$ identified by the MinHash LSH step, you merge their clusters with the union(d_i, d_j) operation. Third, after processing all pairs, each tree in the forest contains all near-duplicates of a given document, and you keep one representative from each tree.

The representative selection step is where quality information enters the picture. If you have a quality score for each document (based on source domain, length, readability, or other signals), you select the highest-scoring member of each cluster as the representative and discard the rest. Without quality scores, you typically keep the first document added to the cluster, which is equivalent to greedy deduplication.

Union-find with path compression and union by rank runs in nearly $O(N \alpha(N))$ time, where $\alpha$ is the inverse Ackermann function. For practical purposes, $\alpha(N) \leq 5$ for any $N$ representable in the universe, so the algorithm runs in effectively linear time. This efficiency is important because, after MinHash LSH produces millions of near-duplicate pairs, you need to process all those pairs efficiently to identify the actual clusters.

For trillion-token corpora, even the MinHash plus LSH approach requires distributed computing. The standard architecture uses a MapReduce or Apache Spark pipeline organized around three phases.

The map phase assigns each document a set of LSH bucket identifiers based on its MinHash signature. A document's MinHash signature is divided into $b$ bands of $r$ hash values each ($m = b \times r$). Two documents that share all $r$ hash values in any single band are placed into the same bucket for that band. The probability that two documents with Jaccard similarity $s$ end up in the same bucket for at least one band is $1 - (1 - s^r)^b$, and the parameters $b$ and $r$ can be tuned to achieve a desired false-positive and false-negative rate.

The shuffle phase, handled by the distributed computing framework, collects all documents assigned to each bucket. Since each document may be assigned to multiple buckets (one per band), this step can involve significant data movement. The total number of bucket assignments per document is $b$, so the total data moved is $O(b \times N)$ where $N$ is the number of documents.

The reduce phase performs exact Jaccard similarity computation within each bucket on the small subset of documents that share a bucket. Because LSH guarantees that only documents with sufficiently similar signatures end up in the same bucket, these within-bucket comparisons are vastly fewer than the $O(N^2)$ comparisons that naive pairwise matching would require. The reduce phase also applies union-find to merge near-duplicate pairs into clusters and select representatives.

The BigScience workshop, which produced the BLOOM language model, published their deduplication pipeline for the 341 billion token ROOTS corpus as part of a broader data transparency effort. EleutherAI's deduplication of the Common Crawl for the Pile used distributed MinHash LSH and removed roughly 30% of the initial corpus before further filtering. The Dolma dataset, produced by the Allen Institute for AI, applied MinHash deduplication across each of its component sources independently, then applied a cross-source deduplication pass to remove documents that appeared in both web crawl data and more curated sources like Wikipedia.

Large-scale models increasingly use retrieval-augmented generation (RAG) architectures or are trained with long context windows that span multiple retrieved passages. For these use cases, deduplication at the passage level becomes relevant in addition to document-level deduplication.

Passage-level deduplication uses the same MinHash approach but applied to fixed-length chunks (typically 256 to 512 tokens) rather than entire documents. A document might be unique at the document level but contain several passages that appear verbatim in many other documents. Removing those repeated passages requires either suffix array methods or passage-level MinHash applied across all fixed-size chunks in the corpus.

The challenge with passage-level deduplication is boundary sensitivity. Whether a chunk falls exactly on a sentence boundary or cuts through a sentence in the middle can significantly affect its shingle set, potentially causing two identical passages to have different shingle sets because their chunk boundaries fell differently. Handling this correctly requires either sentence-boundary-aware chunking or overlapping chunks with stride less than chunk size, so that any sentence appears fully within at least one chunk regardless of how the chunking was applied.

To see how all these components fit together, consider the pipeline used for a production LLM training dataset at the billion-document scale.

The first step is document-level exact deduplication using MD5 hashing on normalized text. This pass is extremely fast (hashing one billion documents takes a few hours on a small cluster) and removes all perfect or near-perfect copies. Because it is so cheap, it is always worth running this step first; it reduces the input size for the more expensive near-duplicate detection pass.

The second step applies MinHash LSH near-duplicate detection at the document level with a threshold around 0.7. This pass is the computationally expensive one: computing MinHash signatures for one billion documents requires significant distributed compute, and the LSH bucketing and within-bucket comparison steps require careful implementation to avoid memory bottlenecks. In practice, this pass runs on a Spark cluster over several hours to a day.

The third step applies union-find to cluster near-duplicates and select representatives. With quality scores computed in an earlier quality filtering step, this selection step retains the highest-quality version of each cluster. Documents below a quality threshold are discarded even if they would have been the first representative in a greedy approach.

The fourth step, applied only in pipelines targeting high data quality, is substring deduplication using suffix arrays or token-level ngram matching. This step is the most expensive and most complex; some pipelines skip it entirely and rely on the combination of exact and near-duplicate deduplication to achieve sufficient cleaning.

The final step is an audit: checking the deduplication results by sampling random clusters, verifying that clustered documents are true near-duplicates, and spot-checking whether any materially distinct documents were incorrectly grouped. This manual validation is essential because the parameters (threshold, shingle size, MinHash parameters) interact in complex ways with the specific corpus, and only empirical validation can confirm the pipeline is working as intended.

Deduplication is powerful but not a silver bullet, and the choices you make have consequences that extend beyond the deduplication step itself.

Every deduplication algorithm has false positives: documents it incorrectly identifies as near-duplicates and removes. A document that discusses a well-known fact using standard phrasing might appear similar to many other documents discussing that fact, even though each version contributes unique context, reasoning, or examples.

This is particularly acute for factual domains. Legal documents, scientific papers, and news articles often use standardized language to describe the same facts. Aggressive deduplication might remove most of the corpus's coverage of a particular topic because all discussions of that topic share common terminology and sentence structures. The resulting trained model may lack robustness on those topics: it has learned only the single surviving version of the content, rather than developing invariance across multiple phrasings and contexts.

A practical mitigation is to perform topic-aware deduplication: apply lower similarity thresholds for sources with naturally diverse language (fiction, opinion pieces, creative writing) and higher thresholds for sources with naturally formulaic language (legal documents, scientific abstracts, patent filings). This requires segmenting your corpus by source type before applying deduplication, which adds pipeline complexity but significantly improves the quality of the result.

Deduplication is agnostic to quality by default. If you have one high-quality and one low-quality version of the same content, which one you keep depends entirely on which one you process first (in the greedy approach) or on which cluster representative selection criterion you use.

In practice, you want to run quality filtering before or alongside deduplication, and use quality scores to select which member of each near-duplicate cluster to retain. Documents with higher readability scores, fewer grammatical errors, or higher source quality signals (from Wikipedia versus random web pages) should be preferred as the cluster representative. This requires that quality scores be computed before the deduplication step selects representatives, which means the quality filtering and deduplication steps are not entirely independent. The pipeline design must account for this dependency.

Web-scale corpora are crawled over months or years. A news article might appear in your corpus multiple times with different timestamps: once when it was originally published, once a week later when it was syndicated, and once a year later when it was included in a retrospective. Document-level deduplication will correctly identify these as near-duplicates, but you might want to keep the most recent version, not the first one seen.

This requires tracking metadata (publication dates, crawl timestamps) alongside document content and using that metadata to inform which cluster representative to keep. In practice, this is often implemented by assigning a priority score that combines quality signals with recency signals, then selecting the highest-priority document from each cluster.

Deduplication reduces memorization, but some memorization is desirable. A model that can accurately recall factual information, reproduce correct syntax for programming languages, or recite standard formulas is more useful than one that cannot. Aggressive deduplication can reduce this useful memorization along with the harmful variety.

The research community is still working out the optimal deduplication strategy for different model sizes and use cases. Smaller models trained on highly deduplicated corpora tend to have better generalization because they cannot afford to waste capacity on memorized content. Larger models have enough capacity to benefit from some redundancy in training data, because the redundancy reinforces important patterns rather than just memorizing them. This suggests that the optimal deduplication threshold scales with model size: very small models should be trained on heavily deduplicated data, while very large models may tolerate more redundancy without it harming generalization.

Most large training corpora assemble content from multiple sources: web crawl data, books, Wikipedia, code repositories, scientific papers, and so on. Near-duplicate detection within a single source is straightforward, but cross-source deduplication, finding near-duplicates that span different source types, is more complex.

The challenge is that different sources may have systematically different normalization and formatting conventions, making documents that contain substantially similar material appear more different than they are to a Jaccard-based detector. A Wikipedia article and a web page that mirrors the same Wikipedia content may have slightly different formatting, citation styles, and section structures. Their Jaccard similarity might be 0.5, which is below a typical deduplication threshold of 0.7, even though they express nearly identical information.

Cross-source deduplication also raises policy questions. Should you remove a web page that closely paraphrases a Wikipedia article, even if the web page adds a paragraph of original commentary? The original commentary might be low-quality, but it is unique content. The decision depends on your data quality philosophy: do you prioritize removing redundancy or preserving uniqueness?

Measuring whether your deduplication pipeline is working correctly requires building a ground-truth evaluation set. This means manually labeling a sample of document pairs as near-duplicates or not, then measuring precision (what fraction of flagged pairs are true near-duplicates) and recall (what fraction of true near-duplicate pairs were flagged).

Building this ground truth is labor-intensive but essential. Common failure modes that manual evaluation can catch include: the threshold being too aggressive for short documents (two unrelated documents that happen to be short may have high Jaccard similarity by chance), normalization inconsistencies causing the same document to appear as multiple non-duplicates, and corpus-specific idioms (e.g., programming comments like "TODO: fix this") appearing so frequently that they create false near-duplicates between unrelated code files.

A simpler diagnostic, though less rigorous, is to check the distribution of cluster sizes after running near-duplicate detection. In a well-configured pipeline, most documents should be singletons (no near-duplicates found), a substantial fraction should be in clusters of size 2 to 5, and very few should be in clusters of size 100 or more. If you see a large fraction of documents in very large clusters, your threshold may be too low, and you are grouping materially distinct documents together.

Deduplication is one of the most impactful data curation decisions you will make for a language model training pipeline. The key takeaways are:

• Exact deduplication uses cryptographic hashing to find bit-for-bit identical documents. Normalization before hashing is essential to catch formatting variants, and this step is so fast and cheap that it should always be applied first.
• Near-duplicate detection uses Jaccard similarity over character n-grams (shingles) to find documents that are similar but not identical. The Jaccard threshold, the shingle size, and the normalization scheme all affect which documents are flagged and must be chosen carefully for the specific corpus.
• Substring deduplication uses suffix arrays to find repeated passages within otherwise unique documents, addressing memorization driven by passage-level repetition rather than document-level duplication. This is the most computationally demanding deduplication method but addresses a distinct class of redundancy that document-level methods miss.
• Scalable deduplication requires MinHash signatures and Locality-Sensitive Hashing to avoid the $O(N^2)$ cost of pairwise comparison. The next chapter covers MinHash in full detail, including the mathematical derivation, LSH banding, and practical implementation.
• Union-find provides an efficient data structure for clustering near-duplicate pairs into groups and selecting a representative from each cluster, ideally the highest-quality member.
• Deduplication interacts with quality filtering: the order of these steps and the strategy for selecting cluster representatives both affect the final data distribution. In practice, quality scores should inform which cluster representative is kept.
• False positives exist: aggressive deduplication can remove legitimate content that happens to share common vocabulary or phrasing, potentially creating coverage gaps in the training corpus. Evaluation against a labeled sample of document pairs is essential to verify that the pipeline is calibrated correctly.

The choice of deduplication strategy involves balancing memorization reduction against information loss, and that balance depends on the model scale, the downstream tasks, and the nature of the corpus. Understanding these trade-offs is what separates a thoughtful data curation pipeline from a naive one. The algorithms in this chapter provide the technical foundation; calibrating them to your specific corpus requires empirical investigation and domain knowledge about where duplication arises and what forms it takes.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about deduplication in language model training pipelines.