MinHash and LSH for Deduplication

CommonCrawl's April 2023 snapshot contains roughly 3.1 billion web pages. A naive pairwise similarity check against even a million-document subset requires trillions of comparisons. That arithmetic is why every serious LLM pretraining pipeline - from RefinedWeb to FineWeb to Dolma - uses MinHash combined with Locality-Sensitive Hashing (LSH) to reduce that quadratic problem to something closer to linear.

The consequences of skipping this step are well-documented. Lee et al. (2021) showed that language models trained on deduplicated data memorise less verbatim content and can reach comparable perplexity with fewer training tokens, because the optimiser is not wasting gradient steps re-learning content it has already seen hundreds of times.

Why exact deduplication is not enough

Exact URL or MD5-hash deduplication removes nothing but byte-for-byte copies. In practice, web data is littered with near-duplicates: the same news story scraped by fifty aggregators, a Wikipedia article mirrored across thousands of educational sites, a Stack Overflow answer republished with the ads stripped. These are textually distinct enough to pass exact deduplication, yet semantically redundant.

The right notion of similarity for this task is the Jaccard coefficient over token n-gram sets:

J(A, B) = |A ∩ B| / |A ∪ B|

Two documents with Jaccard similarity above a chosen threshold (commonly 0.7 to 0.8) are considered near-duplicates, and one of the pair is discarded. Computing this exactly for every pair is O(n²) in the number of documents, which is infeasible at pretraining scale.

MinHash: compressing a document into a fixed-length sketch

MinHash, due to Broder (1997), reduces each document to a short integer vector called a signature while preserving Jaccard similarity in expectation.

The core idea. Represent a document as the set of its k-gram shingles (e.g., character 5-grams or word unigrams/bigrams). Apply h independent hash functions to each shingle, and record the minimum hash value produced by each function across all shingles in the document. The resulting vector of h minimum values is the MinHash signature.

The key property: the probability that two documents agree on the minimum value for any given hash function equals their Jaccard similarity.

P[ min_h(A) = min_h(B) ] = J(A, B)

So the fraction of positions where two signatures agree is an unbiased estimator of Jaccard similarity. With h = 128 or 256 hash functions, the estimation variance is small enough for practical deduplication thresholds.

Critically, signature generation is O(|document| × h) and the resulting signature is a fixed-length vector of h integers regardless of document length. You can represent the entire 3.1-billion-page CommonCrawl as a matrix of fixed-width rows.

A minimal Python sketch using the datasketch library:

from datasketch import MinHash

def make_signature(text: str, num_perm: int = 128) -> MinHash:
    m = MinHash(num_perm=num_perm)
    for shingle in get_shingles(text, k=5):          # 5-char shingles
        m.update(shingle.encode("utf-8"))
    return m

# Estimated Jaccard between two documents:
# sim = sig_a.jaccard(sig_b)

Typical corpora use 64 to 256 permutations. Fewer permutations means faster processing and lower memory but higher estimation variance; 128 is a common production choice.

LSH: finding near-duplicates without comparing every pair

Even with O(1)-cost signature comparison, comparing every document against every other document is still O(n²). LSH solves this by engineering hash collisions so that similar documents are mapped to the same bucket.

Band decomposition. Partition the h-dimensional signature into b bands of r rows each (so h = b × r). For each band, hash the sub-vector of r values into a bucket. Two documents that share their entire sub-vector for at least one band end up in the same bucket and become candidate pairs.

The probability that two documents with Jaccard similarity s share at least one band is:

P(candidate) = 1 - (1 - s^r)^b

This is an S-curve in s. By tuning the ratio r/b you control the threshold behaviour: a steep transition near the target similarity, low false-negative rate above it, low false-positive rate below it.

After bucketing, only candidate pairs require an exact Jaccard check (or acceptance by policy). The number of candidate pairs is typically a tiny fraction of all O(n²) pairs.

Scale in practice. The FineWeb pipeline processes roughly 15 trillion tokens from CommonCrawl. Running MinHash-LSH on this corpus in a distributed setting (e.g., PySpark or Ray) partitions the band-bucket computation across workers; each worker only sees documents that hashed to the same bucket for a given band, making the inter-worker communication proportional to the number of near-duplicate clusters rather than to n².

Shingle choice and preprocessing decisions

The choice of shingle type affects what you catch. Character n-grams (k = 5 is common) are robust to tokenisation differences and catch paraphrase variants. Word n-grams are faster to compute but miss whitespace-normalised copies. Most production pipelines apply light normalisation first: lowercase, collapse whitespace, strip HTML entities.

One non-obvious tradeoff: very short documents produce very few distinct shingles. A 50-word paragraph and a 48-word version of it may both produce only 40 distinct shingles, making their Jaccard similarity appear higher than it really is because the intersection set dominates. Some pipelines discard documents below a minimum length threshold before running MinHash precisely for this reason.

Corpus-level deduplication also raises a sequencing question: deduplicate before or after quality filtering? Deduplicating first means you may keep a low-quality copy of a document pair while discarding a higher-quality copy. Most practitioners deduplicate after the initial quality pass but before domain mixing, so that the retained copy per cluster is more likely to be the cleaner variant.

When it falls down

High-similarity boilerplate inflation. Navigation menus, legal boilerplates, and cookie-consent banners appear in millions of pages. At a 0.7 Jaccard threshold they will generate enormous clusters, potentially discarding documents that are genuinely distinct in their body text but share a 200-word footer. Some pipelines remove boilerplate before shingling; others use a paragraph-level deduplication pass instead.

Threshold sensitivity near the boundary. The LSH S-curve is steep but not a step function. Documents at exactly the threshold similarity (say 0.72 when the target is 0.7) have roughly 50% recall, meaning about half of near-duplicate pairs at that similarity will be missed entirely. If you need high recall at a specific threshold, increase h; if you need low false-positive rate, widen the bands.

Language and encoding effects. A document in UTF-8 and its Windows-1252 re-encoding produce different byte sequences. Normalising to Unicode NFC before shingling avoids spurious misses. Similarly, mixing character and word shingling on multilingual corpora can produce signature distributions with different effective similarities across languages.

Exact substring deduplication is complementary, not redundant. MinHash-LSH finds documents that are globally similar. It will not reliably flag a corpus where 10,000 documents each contain the same 500-word boilerplate embedded in otherwise distinct text. Suffix-array based exact substring deduplication (as in the Google deduplicate-text-datasets toolkit) catches this class of repeated spans; both approaches are used in production pipelines.

Parallelism hazards. In distributed implementations, documents that fall in the same band-bucket must be collected to the same worker. With very large corpora, a single bucket for a near-ubiquitous document (e.g., a Creative Commons licence text) can create a data-skew hotspot that stalls the entire job. Cluster-size caps and bloom-filter pre-screening help here.

Further reading

• Lee et al. (2021). "Deduplicating Training Data Makes Language Models Better." arXiv:2107.06499. The foundational empirical study showing the downstream quality and memorisation effects of deduplication.
• Penedo et al. (2024). "The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale." arXiv:2406.17557. Detailed deduplication and filtering methodology for a 15-trillion-token corpus.
• datasketch documentation. MinHash and MinHash LSH. https://ekzhu.com/datasketch/minhash.html and https://ekzhu.com/datasketch/lsh.html. The reference Python implementation with parameter tuning guidance.
• Soldaini et al. (2024). "Dolma: an Open Corpus of Three Trillion Tokens for Language Model Pretraining Research." arXiv:2402.00159. Describes a full open-source pipeline including MinHash-LSH deduplication at multi-trillion token scale.