Open a random shard of a web crawl and count how often each paragraph appears. Most appear once. A few appear thousands of times. Cookie banners, "All rights reserved" footers, product descriptions copied across a hundred shops, news wires syndicated to a thousand local papers, and the same license text at the bottom of every page of a forum. When Lee et al. (2022) looked inside C4, a dataset that had already been filtered and exact-deduplicated at the level of three-sentence spans, they found one 61-word sentence repeated 61,036 times.

A model sees each copy as a fresh training example. So a document that appears 10,000 times is trained on for 10,000 epochs while the rest of the corpus gets one, and the model does what any learner does with something it sees 10,000 times. It memorizes it. This section is about finding those copies, exact ones, near ones, shared substrings, and paraphrases, at the scale of billions of documents, and about the special kind of duplicate that silently ruins evaluations, the benchmark question that also lives in the training set.

Why duplicates hurt

There are three separate costs, and they call for slightly different tools.

Wasted compute and a distorted mixture. Every repeated token is compute spent on something the model has already learned, and heavy repetition quietly changes the data mixture of §8.4, since whatever is copied most gets the most weight. Hernandez et al. (2022) measured how bad this can be. Repeating just 0.1 percent of the data 100 times (so those copies made up 10 percent of the tokens) degraded an 800M-parameter model to the performance of a 400M-parameter one, even though the other 90 percent of the tokens were unique.

Memorization and regurgitation. Text that is seen many times is reproduced verbatim. Lee et al. (2022) found that about 1.9 percent of the tokens a model trained on raw C4 generated without a prompt were part of verbatim copies of training text, and that training on deduplicated data cut this to between 0.1 and 0.2 percent, roughly tenfold. Verbatim regurgitation is a privacy problem (phone numbers, addresses) and a copyright problem, and it also means the model spent capacity storing strings rather than learning to generalize.

Leakage between training and evaluation. If a validation document, or a benchmark question, also sits in the training set, the measured loss or accuracy is a memory test. Lee et al. found that 4.6 percent of C4's validation documents had a near-duplicate in its training set, and 14.4 percent for the news dataset RealNews. We return to this in the last part of the section.

Duplicates come in four kinds, and each needs its own detector.

Exact deduplication with hashing

The cheapest case first. Two documents are exact duplicates if they are equal after a normalization that removes differences nobody cares about (case, runs of whitespace, sometimes punctuation and digits). Compute a hash of each normalized document, keep the first document for each hash, and drop the rest. A hash set does this in one pass, in time linear in the corpus.

How many bits does the hash need? If $n$ documents get independent uniform $h$-bit hashes, each of the $\binom{n}{2} \approx n^2/2$ pairs collides with probability $2^{-h}$, so the expected number of false collisions is

In plain words, collisions grow with the square of the corpus size, the birthday paradox. For $n = 10^{10}$ documents, a 64-bit hash gives $10^{20}/2^{65} \approx 2.7$ expected collisions, so a couple of unrelated documents would be wrongly dropped. A 128-bit hash makes it about $10^{-19}$. Pipelines use 64-bit hashes when a rare false drop is acceptable and 128 bits otherwise.

The same idea works below the document level. C4 removed every three-sentence span that appeared more than once, and Dolma removes repeated paragraphs (Soldaini et al. 2024). At that granularity the set of hashes no longer fits in memory on one machine, which is where a Bloom filter helps. It is a bit array of $m$ bits and $k_b$ hash functions (a separate count from MinHash's $k$ below). To insert an item, set the $k_b$ bits it hashes to. To query, report "seen" if all $k_b$ bits are set. It never misses an item it has seen, but it can report a false "seen".

In plain words, about 10 bits per paragraph buy a 1 percent false-drop rate, roughly six times less memory than storing hashes. DCLM's baseline dataset was deduplicated with a Bloom filter of this kind (Dolma's BFF tool), which removes repeated paragraphs and near-duplicate documents in a single pass and came within a fraction of a point of a MinHash plus suffix-array pipeline in their ablations (Li et al. 2024).

import hashlib, re

def exact_dedup(docs):
    return list(range(len(docs)))      # placeholder: keeps everything

Near duplicates and the Jaccard similarity

Exact hashing misses the most common case. Two crawls of the same news article differ in a timestamp, a "related stories" box, and a cookie notice. Hashes of the two texts are completely different, because a good hash changes completely when one character changes. We need a similarity that degrades gracefully with small edits.

The standard choice treats a document as a set of short overlapping pieces called shingles, usually word $n$-grams with $n$ around 5. "the cat sat on the mat" has the four 3-word shingles "the cat sat", "cat sat on", "sat on the", and "on the mat". Changing one word destroys at most $n$ shingles, however long the document is, so a long document with a few edits keeps most of its shingles. Two shingle sets $\mathcal{A}$ and $\mathcal{B}$ are compared with the Jaccard similarity

In plain words, the fraction of all shingles that appear in either document which appear in both. (Here $J$ is the Jaccard similarity, not an objective, and calligraphic letters are sets.)

A worked example by hand. Take "the cat sat on the mat" and "the cat sat on a mat" with 2-word shingles. The first has the five shingles "the cat", "cat sat", "sat on", "on the", and "the mat". The second has "the cat", "cat sat", "sat on", "on a", and "a mat". They share three, and the union has seven, so $J = 3/7 \approx 0.43$. One edited word in a six-word sentence is a big edit. In a 500-word article, one edited word with 5-word shingles removes at most 5 of about 496 shingles from each side, so $J \ge 491/501 \approx 0.98$.

Pipelines usually call two documents near-duplicates when $J$ is above roughly 0.7 to 0.8. Computing $J$ exactly is easy for one pair. The problem is the number of pairs. A corpus of $10^9$ documents has $5\times10^{17}$ of them. We need two tricks, one that makes each comparison cheap (MinHash) and one that avoids comparing most pairs at all (LSH).

MinHash, derived

Here is the idea that makes near-duplicate detection possible at web scale, due to Broder (1997), who built it to cluster 30 million pages of an AltaVista web crawl into groups of near-identical documents. (Broder's own sketch keeps the smallest few values under one permutation. The version with $k$ independent permutations that we derive here behaves the same way and is the one pipelines use.)

Put every possible shingle in a random order, a random permutation $\pi$ of the universe of shingles. For a set $\mathcal{A}$, let $h_\pi(\mathcal{A}) = \min_{x\in\mathcal{A}}\pi(x)$ be the position of whichever of its shingles comes first in that random order. The claim is

In plain words, the probability that two sets have the same first element under a random ordering is exactly their Jaccard similarity.

The proof takes three sentences, so let's go slowly. Look at the union $\mathcal{A}\cup\mathcal{B}$ and ask which of its elements comes first under $\pi$. Because $\pi$ is a uniformly random permutation, every element of the union is equally likely to be that first one, each with probability $1/\lvert\mathcal{A}\cup\mathcal{B}\rvert$. If the first element of the union lies in the intersection, it is in both sets and is the first of each, so $h_\pi(\mathcal{A}) = h_\pi(\mathcal{B})$. If it lies in only one set, say $\mathcal{A}$, then it is $\mathcal{A}$'s minimum but not in $\mathcal{B}$, and $\mathcal{B}$'s minimum is a different element with a larger position, so the minima differ. The minima agree exactly when the first element of the union is in the intersection, which happens with probability $\lvert\mathcal{A}\cap\mathcal{B}\rvert/\lvert\mathcal{A}\cup\mathcal{B}\rvert$. $\square$

One permutation gives one coin flip whose probability of heads is $J$. Use $k$ independent permutations $\pi_1, \dots, \pi_k$, store the signature $\big(h_{\pi_1}(\mathcal{A}), \dots, h_{\pi_k}(\mathcal{A})\big)$ for every document, and estimate the similarity by the fraction of positions where two signatures agree,

Each indicator is a Bernoulli variable with mean $J$ and variance $J(1-J)$, and they are independent because the permutations are, so

In plain words, the estimate is unbiased, and its error shrinks like $1/\sqrt{k}$, largest at $J = 1/2$ and zero when the documents are identical or disjoint.

Two consequences matter in practice. First, the signature has a fixed size. A 100-word tweet and a 100,000-word book both become $k$ integers, so similarity costs $O(k)$ regardless of length. Second, $k$ is a precision dial. With $k = 128$, at $J = 0.8$ the standard deviation is $\sqrt{0.16/128} \approx 0.035$, so a pair at the threshold is estimated anywhere from about 0.73 to 0.87 (two standard deviations). Pinning $J$ to within $\pm 0.02$ at 95 percent confidence would need $k \ge (1.96/0.02)^2\cdot 0.16 \approx 1{,}537$ hashes. That is expensive, which is why MinHash is used to propose candidates, and the final decision is often an exact comparison of the shingle sets, affordable because there are few candidates.

Real implementations never build a permutation of all possible shingles. They hash each shingle to an integer $x$ and apply $k$ random affine hash functions, $h_i(x) = (a_i x + b_i) \bmod p$ for a large prime $p$, taking the minimum over the shingles. These functions are not exactly min-wise independent, and the gap can show. Applied directly to consecutive integers such as 0, 1, 2, and so on, affine hashes give visibly biased estimates. Applied to ids that are themselves hashes of the shingle text, which look random, they behave as derived (Broder et al. 1998 studied exactly how close to min-wise a family must be). Let's check the whole derivation numerically, with ids that come from hashing.

Each shingle here is a single "word", which is fine, since MinHash only sees sets of integers. The mean estimate sits at the true $J = 0.5$ for every $k$, and the spread follows $\sqrt{J(1-J)/k}$, halving each time $k$ is multiplied by four.

import numpy as np

def minhash_signatures(id_sets, a, b, p):
    raise NotImplementedError

def estimate_jaccard(sig1, sig2):
    raise NotImplementedError

LSH banding and the S-curve

MinHash made each comparison cheap. Now we avoid most comparisons. The trick is the same amplification you met for random hyperplanes in §7.4 and §1.3, now with MinHash values as the bits.

Split each signature of length $k$ into $b$ bands of $r$ consecutive values, with $k = br$. For each band, hash its $r$ values into a bucket. Two documents become a candidate pair if they land in the same bucket in at least one band. Only candidate pairs are ever compared.

Let's derive the probability that a pair with Jaccard similarity $s$ becomes a candidate. Each MinHash value agrees with probability $s$, independently. A band of $r$ values matches only if all $r$ agree, an AND,

The bands use disjoint hash functions, so they are independent. The pair is missed only if every band fails, and becomes a candidate if any band matches, an OR,

In plain words, rows make each band strict, so only very similar pairs match a given band, and many bands give a similar pair many chances. The result is a steep S-curve. Pairs above some similarity almost always become candidates and pairs below it almost never do.

Where is the step? A clean way to locate it is to ask when the expected number of matching bands, $b s^r$, equals one. That gives the usual rule of thumb

The point where the curve crosses one half is slightly lower. Setting $(1 - s^r)^b = 1/2$ and using $\ln(1 - y) \approx -y$ for small $y = s^r$ gives $s_{1/2} \approx (\ln 2/b)^{1/r}$. More rows make the step steeper, and more bands move it to the left.

Two worked examples. FineWeb computed $k = 112$ hashes of 5-word shingles, arranged as $b = 14$ bands of $r = 8$ (Penedo et al. 2024), aiming at pairs above about 75 percent similarity. The rule of thumb gives $s^\star = 14^{-1/8} \approx 0.72$. At $s = 0.8$, a band matches with probability $0.8^8 = 0.168$, and the pair is a candidate with probability $1 - 0.832^{14} \approx 0.92$. At $s = 0.5$, $0.5^8 = 0.0039$ and the probability falls to $1 - 0.9961^{14} \approx 0.053$. Lee et al. (2022) computed $k = 9{,}000$ hashes of 5-word shingles, arranged as $b = 450$ bands of $r = 20$ (their paper writes the formula with the letters swapped, so watch out when reading it), a much steeper curve, with $s^\star = 450^{-1/20} \approx 0.74$.

The two kinds of error have different costs, and this is what should drive the choice of $b$ and $r$. A false positive (a dissimilar pair that becomes a candidate) costs one extra comparison, after which a check of the estimated or exact Jaccard throws it out. A false negative (a true near-duplicate that never becomes a candidate) is lost forever, and the copy stays in the corpus. So pipelines set the curve's step a little below the similarity they actually care about, and verify candidates afterwards.

import numpy as np

def lsh_candidates(sigs, b, r):
    raise NotImplementedError

def candidate_probability(s, b, r):
    raise NotImplementedError

Choosing $b$ and $r$ is itself an interview question, and a good one, because it forces you to say what you are trading. With a budget of $k$ hashes there are only a few factorizations $k = br$, and each fixes a curve. A principled choice weighs the probability mass of false positives below the threshold against false negatives above it.

import numpy as np

def choose_bands(k, threshold, fn_weight=1.0, fp_weight=1.0):
    return (k, 1)        # placeholder: one row per band

From candidate pairs to a deduplicated corpus

LSH hands us candidate pairs. Three steps turn them into a decision about which documents to keep.

1. Verify. For each candidate, compare the full signatures (or the exact shingle sets, when they are cheap to fetch) and keep only pairs with estimated $J$ above the threshold. This removes the false positives of banding.
2. Cluster. Treat verified pairs as edges of a graph and find its connected components with union-find. Every component is one group of near-duplicates.
3. Keep one. From each component, keep one document (the first crawled, the longest, or the one with the best quality score) and drop the rest.

The clustering step has a subtlety worth naming. Similarity is not transitive. A can be 0.8 similar to B and B 0.8 similar to C while A and C are only 0.6 similar, and connected components will still put A and C in one cluster. On real web data this chaining is mostly harmless (long chains of slowly drifting copies are themselves a kind of duplication), and every large pipeline accepts it, because the alternatives (clique finding, or keeping one document per pair) are far more expensive.

Here is the whole pipeline on a toy corpus with planted duplicates.

The four stories land in one cluster and the two recipes do not, which is worth understanding. The story with two substituted words has a true Jaccard of 0.68 with the original, just under the 0.7 threshold, and it merged anyway because 128 hashes estimate 0.68 with a standard deviation of about 0.04. The two recipes differ in a single word, yet their Jaccard is only 0.65, because a 16-word text has just 14 shingles and one changed word destroys 3 of them. The same edit is a bigger fraction of a short document, so short documents need either shorter shingles or a different threshold. Try it yourself in the explorer below, which runs the same pipeline on a slightly larger corpus.

import numpy as np, re, zlib

def near_dedup(texts, k=128, b=32, r=4, threshold=0.6, n=3, seed=0):
    return list(range(len(texts)))       # placeholder: keeps everything

How does this scale? Computing signatures is embarrassingly parallel, one pass over the data. Banding is a big group-by on $(j, \text{band hash})$, which distributed systems do well. Union-find over billions of edges is the only step that needs care, and libraries such as Hugging Face's datatrove (used for FineWeb) split it into stages that each fit on a cluster.

Substring deduplication with suffix arrays

Document-level near-dedup asks whether two whole documents are similar. It misses unique documents that share a long passage. A forum post with a 200-word legal disclaimer appended, or ten thousand product pages with the same paragraph of shipping terms, each have plenty of unique text, so their Jaccard with each other is low, yet the shared passage is seen ten thousand times.

Lee et al. (2022) attacked this with a suffix array, a sorted list of every suffix of the entire concatenated corpus. The key fact is simple. If a substring of length $L$ occurs at two different places, then the two suffixes starting there share a prefix of length at least $L$, and in sorted order, suffixes that share a long prefix sit next to each other. So every repeated substring of length at least $L$ shows up as a pair of adjacent suffixes whose longest common prefix (LCP) is at least $L$. One linear scan of the LCP array finds them all.

The 13-word shipping paragraph is found as one repeated span, even though the two pages it sits on are different products. The six adjacent pairs are the same repeat seen from different starting points, since every suffix of a repeated span is itself repeated, and real tools merge them into maximal spans before removing anything. Lee et al. removed every span of at least 50 tokens that occurred more than once, which they called ExactSubstr. On C4 it removed 7.2 percent of the tokens, and 77 percent of the documents that MinHash flagged as near-duplicates also contained such a 50-token verbatim match. The real suffix array for a corpus of $n$ tokens is built in $O(n)$ time with algorithms such as SA-IS, and it costs several bytes per token of memory and disk, which is why it is run on shards or on datasets of a few hundred billion tokens rather than on everything.

Removing spans from the middle of a document has a cost of its own. It can leave a document that reads oddly, with a paragraph missing. Most recent pipelines prefer line-level or paragraph-level exact dedup with a Bloom filter (Dolma, DCLM), which catches most boilerplate at a fraction of the cost, and keep suffix arrays for measuring memorization and contamination.

Semantic deduplication

The last kind of duplicate shares no words. A blog post that rewrites a Wikipedia article in its own words, a tutorial translated from another language, a thousand slightly different "top ten tips for productivity" listicles. Shingles cannot see these, but embeddings can (§7.3).

SemDeDup (Abbas et al. 2023) is the standard recipe. Embed every document with a pretrained encoder, normalize, run k-means to group the corpus into clusters (so the expensive comparisons stay inside a cluster), and within each cluster remove one document from every pair whose cosine similarity exceeds $1 - \varepsilon$. Within each group of duplicates they keep the item farthest from the cluster centroid, which favors the least typical example. On 440 million image-text pairs from LAION, they removed half the data with less than half a point of performance loss, halving training time. Tirumala et al. (2023) combined this with a step that also removes "prototypical" documents near cluster centers (D4) and reported faster training for language models.

Semantic dedup needs more care for text than for images. Two documents can be close in embedding space and still teach different things, for example two proofs of the same theorem or the same API used in two programs. It is used with conservative thresholds, and it works best as a way to thin out clusters of low-value templated content.

Benchmark contamination

The duplicates that do the most damage are not the ones in the training set. They are the ones shared between the training set and the test set. Benchmarks are published on the web, discussed on forums, and pasted into homework sites, so a crawl will contain many of them. A model that has seen a benchmark's questions with answers scores higher on that benchmark without being more capable, and nobody can tell from the score alone.

The standard detector is word $n$-gram overlap. GPT-3 (Brown et al. 2020) flagged a test example as contaminated if any of its 13-grams appeared in the training data (after lowercasing and removing punctuation), and later work uses similar rules with different $n$. The test is asymmetric on purpose. We ask what fraction of a test item's $n$-grams appear anywhere in the training data, which a hash set of training $n$-grams answers in one pass. Long $n$ avoid false alarms on common phrases ("one of the most important"), and normalization (lowercase, strip punctuation) avoids misses from formatting.

Overlap checks catch verbatim leaks but miss paraphrased or translated ones, and they say nothing about leaks introduced later, for example by synthetic data generated with a model that had seen the benchmark (§8.4). Two habits help. Decontaminate before training, by removing training documents that overlap any benchmark you plan to report. And put a unique canary string in your own benchmarks (BIG-bench did this) so that you can later test whether a model has seen it. The broader science of contamination, including membership inference and benchmarks built to be robust to it, is a large part of how the field evaluates models it did not train itself.

import re

def contaminated(train_docs, test_items, n=8, min_frac=0.0):
    raise NotImplementedError

How real pipelines combine them

No pipeline uses every tool, and the choices tell you what each team worried about.

The FineWeb row deserves a sentence. Deduplicating all 96 snapshots against each other removed up to 90 percent of the oldest snapshots, and the model trained on the globally deduplicated data was worse than one trained on per-snapshot dedup. In one 2013 snapshot, the 10 percent that global dedup kept trained a worse model than the 90 percent it removed. The data that survived global dedup in older snapshots turned out to be low quality, since good pages tend to be recrawled and get removed as duplicates of a later copy while spam is unique. More dedup is not automatically better. What matters is what is left.

In PyTorch

On a GPU, signatures for a batch of documents are one broadcasted operation, and semantic dedup is a matrix multiply between normalized embeddings. Here are both, checked against the NumPy versions.

Read more

• Broder (1997). On the resemblance and containment of documents. The original MinHash paper, short and readable.
• Lee et al. (2022). Deduplicating Training Data Makes Language Models Better. ExactSubstr with suffix arrays, NearDup with MinHash, and the measurements of memorization and train-test leakage.
• Leskovec, Rajaraman, and Ullman. Mining of Massive Datasets, Chapter 3. The clearest textbook treatment of shingling, MinHash, and the banding S-curve.
• Penedo et al. (2024). The FineWeb Datasets. A full deduplication ablation at scale, including the surprising result on cross-snapshot dedup.
• Hernandez et al. (2022). Scaling Laws and Interpretability of Learning from Repeated Data. How a small amount of heavily repeated data damages a model.
• Abbas et al. (2023). SemDeDup. Semantic deduplication with embeddings and clustering.
• Brown et al. (2020). Language Models are Few-Shot Learners. Appendix C describes the 13-gram contamination analysis.

Watch next

▶

▶

▶