Deduplication and MinHash

Why bother?

Lee and colleagues found a single 61-word English sentence repeated over 60,000 times in the C4 dataset Established. A model sees such text thousands of times and memorises it. Deduplicating the training data let them train models that emitted memorised text ten times less often and needed fewer training steps for the same or better accuracy Established. Duplicates also leak between training and test sets: over 4% of the validation sets of standard datasets overlapped with their training data Established.

From documents to sets

Exact deduplication is easy: hash each document and drop repeated hashes. But a syndicated article with a different footer, or a recipe with one edited sentence, hashes completely differently.

So compare documents as sets of shingles: every run of k consecutive words. Two pages that share most of their text share most of their shingles. Their Jaccard similarity is

$$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$$

Tiny example. "the cat sat on the mat" has the 3-word shingles the cat sat, cat sat on, sat on the, on the mat. Change the last word to "rug" and only the last shingle changes: 3 shared out of 5 distinct, so J = 0.6.

MinHash: a signature that estimates Jaccard

Apply a random hash function to every shingle of both documents and keep each document's minimum. The probability that the two minimums are equal is exactly the Jaccard similarity Established (Broder, 1997). Repeat with many independent hash functions, and the fraction of matching minimums estimates J. Each document becomes a short, fixed-size signature, say 112 numbers, however long it is.

LSH: compare only likely pairs

Even with signatures, comparing every pair of a billion documents is too much. Locality-sensitive hashing splits each signature into b bands of r numbers and puts documents into buckets by each band. Only documents sharing a bucket are compared. A pair with similarity s becomes a candidate with probability

$$P = 1-(1-s^{r})^{b}$$

an S-shaped curve with its steep part near $(1/b)^{1/r}$. FineWeb used word 5-grams and 112 hash functions in 14 bands of 8, targeting documents at least 75% similar Established. Try it in the lab, and watch an edited recipe slip under the threshold.

Surprises at scale

More deduplication is not automatically better. FineWeb's team found that deduplicating across all 96 crawl snapshots at once gave worse models than deduplicating each snapshot separately: in older snapshots, the small share of data that survived global deduplication was of lower quality than what was removed Established. One explanation they offer is that the main benefit comes from removing large clusters of duplicates present in every crawl Interpretation.