MinHash › MinHash in LLM Training Pipelines

MinHash LSH is the dominant deduplication method for web-scale LLM training corpora. Its practical dominance comes from a combination of properties that make it uniquely suited to this application: linear time signature computation, compact storage, tunable precision-recall tradeoffs, and easy parallelization.

The landmark C4 dataset, used to train the T5 family of models from Google, applied MinHash deduplication to Common Crawl data. The authors found that deduplicated data significantly improved downstream task performance compared to training on the raw corpus. This result has been replicated consistently: removing near-duplicate content improves model quality by reducing memorization of repeated text and improving the diversity of patterns learned.

The Pile, a large open training corpus assembled by EleutherAI, used MinHash LSH to remove near-duplicate documents within each of its 22 constituent datasets. The RedPajama dataset, an open reproduction of the LLaMA training data, applied MinHash deduplication at multiple stages of processing. RefinedWeb, which underpins the Falcon models, ran aggressive MinHash deduplication as a central component of its data processing pipeline, retaining approximately 65% of the documents after deduplication and other filtering steps.

At web scale (trillions of tokens across billions of documents), the MinHash LSH pipeline is distributed across a large compute cluster. The processing proceeds in stages.

In the first stage, documents are partitioned across worker nodes. Each worker computes MinHash signatures for its shard of the corpus independently, since signature computation is embarrassingly parallel. Workers output (document ID, signature) pairs.

In the second stage, the signatures are processed to perform LSH bucketing. This requires a distributed shuffle: for each band, all documents whose $r$ signature values in that band are identical must be grouped together. In Spark or MapReduce frameworks, this is a natural reduce-by-key operation where the key is the (band index, band hash value) pair and the value is the document ID. After the shuffle, each reducer receives all document IDs that share a given band hash, which become candidate pairs.

In the third stage, candidate pairs are verified. For each candidate pair, the exact MinHash similarity is computed from the full signatures. Pairs exceeding the threshold are confirmed as near-duplicates.

In the fourth stage, clusters are formed. Near-duplicate detection identifies pairs, not clusters. If document A is a near-duplicate of B, and B is a near-duplicate of C, but A and C do not exceed the threshold directly, all three should be deduplicated together. Connected component analysis on the candidate graph identifies maximal clusters. One document is kept from each cluster, typically the one appearing earliest in the data or the one from the highest-quality source.

The typical configuration for LLM training data deduplication uses:

• Shingle type: character-level 5-grams, normalized and lowercased
• Number of hash functions: $k = 128$ or $k = 256$
• Similarity threshold: 0.70 to 0.90, depending on aggressiveness
• Band configuration: $b$ and $r$ chosen so the S-curve midpoint matches the desired threshold

For a threshold of 0.8 with $k = 128$, a common configuration is $b = 16$ bands of $r = 8$ rows, giving a threshold near $(1/16)^{1/8} \approx 0.72$. A more aggressive threshold of 0.65 might use $b = 25$ bands of $r = 5$ rows.

Research consistently shows that deduplication improves model quality in measurable ways. Models trained on deduplicated data exhibit lower memorization of training examples, meaning they are less likely to reproduce verbatim text from training data when prompted. This is both a quality improvement (the model generalizes better) and a safety improvement (the model is less likely to inadvertently reproduce copyrighted or sensitive text).

Deduplication also improves benchmark integrity. When test benchmarks are contaminated by near-duplicate examples from the training set, reported scores are inflated relative to true generalization ability. Removing near-duplicates reduces this contamination. The GPT-3 paper reported that near-duplicate test examples in training data led to modestly inflated benchmark scores, and subsequent models have been more careful about this.

Beyond near-duplicate removal, MinHash is a lightweight pre-filter for more expensive deduplication checks. You first run MinHash to find approximate duplicate clusters, then verify the most suspicious pairs with exact string matching or more expensive similarity methods. This two-stage approach dramatically reduces the cost of exact deduplication without sacrificing recall.