MinHash: Jaccard Similarity, LSH, Near-Duplicate Detection

When you train a language model on web-scale text, you quickly discover that the internet contains vast amounts of duplicate and near-duplicate content. The same news article republished on dozens of sites. Forum posts copied and pasted across communities. Product descriptions cloned from manufacturers to retailers. Blog posts scraped, lightly paraphrased, and reposted under different bylines. Wikipedia content mirrored across hundreds of fansites. Legal boilerplate repeated verbatim across thousands of documents.

If you include all of this duplicated content in your training data, the consequences are concrete and measurable. The model sees certain texts disproportionately often, which distorts the learned token distribution toward the most replicated documents on the web. Models trained on unprocessed Common Crawl data memorize popular web content more readily, producing outputs that closely mirror specific training examples rather than generalizing from patterns. Benchmark contamination becomes a serious concern when test set passages appear verbatim or near-verbatim in training data, inflating reported performance metrics beyond what the model would achieve on previously unseen text.

The naive solution to this problem is exact deduplication: remove files with identical content. This works perfectly for verbatim copies but fails the moment someone changes a single word, adjusts the formatting, or reorders a sentence. A paraphrase that alters 10% of words is still functionally duplicate content from a training-data perspective. Near-duplicate detection requires measuring textual similarity, and measuring similarity between billions of document pairs using brute-force comparison is computationally infeasible.

MinHash is an algorithm that makes near-duplicate detection tractable at scale. It compresses each document into a compact numerical signature, called a MinHash signature, such that the probability of two signatures agreeing on any position equals the Jaccard similarity of the original documents. With these compact signatures, you can estimate similarity without ever comparing the full documents. With an extension called Locality Sensitive Hashing (LSH), you can find all near-duplicate pairs in a large corpus without comparing every pair, reducing what would be a quadratic-time problem to something approaching linear time in practice.

This chapter covers Jaccard similarity as the mathematical foundation, the probabilistic mechanism behind MinHash, how to implement it efficiently from first principles, and how LSH scales the approach to billions of documents. As we discussed in the deduplication chapter, MinHash is one of the dominant techniques used in cleaning training corpora for large language models, appearing in the pipelines that produced C4, RefinedWeb, RedPajama, and many other influential datasets.

Before building MinHash, you need to understand what similarity measure it estimates: Jaccard similarity. This measure has a long history in ecology and information retrieval, and its properties make it particularly well suited for detecting near-duplicate documents.

The Jaccard similarity between two sets $A$ and $B$ measures overlap as a fraction of union:

where:

• $|A \cap B|$: the number of elements appearing in both $A$ and $B$
• $|A \cup B|$: the number of distinct elements appearing in either $A$ or $B$

Jaccard similarity ranges from 0 to 1. A score of 0 means the sets share no elements at all. A score of 1 means the sets are identical, containing exactly the same elements. For text documents, you represent each document as a set of overlapping substrings (called shingles or n-grams), then compute Jaccard similarity over those sets.

The intuition behind using Jaccard for documents is straightforward. If two documents are near-duplicates, they share most of their substrings, so the intersection of their shingle sets is nearly as large as the union. If two documents are completely unrelated, they share almost none of their characteristic phrases, so the intersection is tiny relative to the union. The ratio captures exactly how much of the content is shared.

Cosine similarity is another popular choice for comparing text representations, but it has different properties that make it less ideal for near-duplicate detection. Cosine similarity measures the angle between two vectors in a shared feature space, which makes it insensitive to magnitude differences. Two documents can have high cosine similarity even if one is much longer than the other, as long as their term frequencies are proportionally similar. For duplicate detection, you typically want a measure that penalizes documents that share only a small fraction of their content, and Jaccard does this naturally through the union in the denominator.

Jaccard is also naturally defined over sets, which maps cleanly onto the shingling representation of documents. There is no need to build a vocabulary or construct term-frequency vectors; you just extract substrings and compare sets. This simplicity is computationally important when processing billions of documents.

Consider these two sentences:

• Document A: "the cat sat on the mat"
• Document B: "the cat sat on a mat"

If you extract 3-word shingles (overlapping windows of 3 consecutive words):

Document A generates: {the cat sat, cat sat on, sat on the, on the mat}

Document B generates: {the cat sat, cat sat on, sat on a, on a mat}

The intersection contains 2 shingles: {the cat sat, cat sat on}. The union contains 6 distinct shingles. Therefore:

Even though these documents differ by only one word ("the" vs "a"), their Jaccard similarity over 3-word shingles is only 0.33. This is because each changed word affects multiple overlapping shingles. Shorter shingles capture changes more coarsely; longer shingles are more sensitive to local edits. Choosing the right shingle size is one of the key design decisions in a MinHash pipeline.

Jaccard distance, defined as $d(A, B) = 1 - J(A, B)$, is a valid metric: it is symmetric, non-negative, zero only for identical sets, and satisfies the triangle inequality. This metric property has useful consequences. It means you can use Jaccard distance in metric data structures, and it provides theoretical guarantees for clustering algorithms based on Jaccard distance. MinHash, which approximates Jaccard similarity, inherits these properties approximately.

To apply Jaccard similarity to documents, you first convert each document into a set of overlapping substrings called shingles or k-grams. A shingle of size $k$ is a contiguous sequence of $k$ characters or $k$ words extracted by sliding a window of length $k$ across the document one step at a time.

Character-level shingles (for example, 5-character n-grams) offer fine-grained coverage of document content. The sentence "hello world" produces 5-gram character shingles: {hello, ello , llo w, lo wo, o wor, worl, world}. Notice that whitespace is included in the shingles, so word boundaries are implicitly captured.

Character-level shingles are robust to synonym substitution because replacing one word with a synonym changes many character-level shingles but preserves all the others. They are also more robust to minor formatting differences, like added punctuation or changed capitalization (after lowercasing). The main drawback is that they produce many more shingles per document than word-level shingles, increasing memory requirements during signature computation.

Word-level shingles treat words as the atomic units. A 3-word shingle captures consecutive trigrams of words, which are sensitive to phrase-level structure. Word-level shingles are better at capturing semantic phrases like "machine learning model" as a unit, making them more sensitive to reorderings and paraphrasings that preserve individual words but change their arrangement.

The downside of word-level shingles is sensitivity to synonym substitution: replacing "big" with "large" changes a word-level shingle entirely while barely changing the character-level representation. For near-duplicate detection of web documents where paraphrasing is the primary near-duplicate mechanism, character-level shingles typically perform better.

The choice of $k$ has a direct effect on sensitivity. Very short shingles (k=2 or k=3 characters) appear so frequently across unrelated documents that even dissimilar texts get high Jaccard similarity by chance. Very long shingles (k=20+ characters) become unique to each document, causing near-duplicates that differ slightly to appear unrelated.

In practice, most deduplication pipelines for LLM training use character-level shingles with $k$ between 5 and 9. The exact value is usually determined empirically by checking whether known near-duplicate pairs get high Jaccard scores and known unrelated pairs get low scores on a small labeled sample. The Pile, RefinedWeb, and similar datasets used $k = 5$ character shingles as a standard choice.

You can represent the shingle set compactly using a hash function. Rather than storing the raw strings (which can be hundreds of bytes for long shingles or many bytes even for short ones), you hash each shingle to a 32-bit or 64-bit integer. This trades a small collision probability for a large memory reduction. With 64-bit hashes, the probability of any two distinct shingles colliding is approximately $1 / 2^{64}$, which is negligible in practice.

Hashing shingles to integers also accelerates the MinHash computation, because comparing integers is faster than comparing strings, and the subsequent hash function computations operate directly on integer inputs.

Computing exact Jaccard similarity for every document pair in a large corpus is infeasible. If you have $n$ documents, there are $O(n^2)$ pairs. For a corpus with 100 billion documents, you would need to compare roughly $5 \times 10^{21}$ pairs. Even if each comparison took just one nanosecond, completing all comparisons would take over 150,000 years. No hardware can do this.

MinHash offers an elegant probabilistic approximation. Rather than computing the full shingle sets and comparing them, you compute a compact signature for each document such that signature similarity approximates Jaccard similarity. The idea originates in a 1997 paper by Broder, and it is built on a beautiful probabilistic identity about random permutations.

Imagine all possible shingles arranged in some arbitrary order, a permutation of the shingle universe. For a given document, look at the shingles it contains, then find the first shingle in the permutation that appears in the document. This is the minimum element under that permutation, hence the name "MinHash."

The key insight is a clean probabilistic fact. If you draw a uniformly random permutation $\pi$ of the shingle universe and compute the minimum element for documents $A$ and $B$ separately, the probability that both minima are the same equals the Jaccard similarity:

The proof is elegant and worth understanding. Consider the union $A \cup B$, which is the set of all shingles appearing in either document. Under a random permutation $\pi$, exactly one shingle in $A \cup B$ lands in the minimum position, that is, appears first in $\pi$ among all shingles in the union. Call this element $e^*$.

There are two cases:

1. $e^*$ falls in $A \cap B$ (it appears in both documents). Then $\min_\pi(A) = e^*$ and $\min_\pi(B) = e^*$, so the minima agree.
2. $e^*$ falls in $A \setminus B$ or $B \setminus A$ (it appears in only one document). Then one minimum is $e^*$ and the other is some different element, so the minima disagree.

By symmetry of a uniformly random permutation, each element in $A \cup B$ is equally likely to be $e^*$. The fraction of elements in $A \cup B$ that also belong to $A \cap B$ is precisely $|A \cap B| / |A \cup B|$, which is the Jaccard similarity. Therefore:

This is a single-bit estimator: it tells you whether the minima match, but a single comparison gives a binary answer (match or no match) with no granularity. To build a useful estimator, you need many independent trials.

To estimate Jaccard similarity reliably, you generate $k$ independent random permutations $\pi_1, \pi_2, \ldots, \pi_k$ and compute $k$ minima per document. These $k$ values form the MinHash signature: a vector of $k$ integers. The fraction of positions where two signatures agree gives an estimate of Jaccard similarity:

where $\mathbf{1}[\cdot]$ is the indicator function, equal to 1 when the condition holds and 0 otherwise.

The variance of this estimator decreases with $k$ following the formula for a Bernoulli average:

With $k = 128$ hash functions, the standard deviation at $J = 0.5$ (the worst case) is $\sqrt{0.25 / 128} \approx 0.044$. With $k = 256$, it falls to roughly $0.031$. The tradeoff is memory: $k$ 32-bit hash values per document requires $4k$ bytes, so 128-hash signatures cost 512 bytes and 256-hash signatures cost 1024 bytes per document. For a billion documents, this is 512 GB and 1 TB respectively, manageable in a distributed system.

Generating $k$ actual random permutations over a large shingle universe is impractical in two ways. First, a permutation over a universe of $2^{32}$ elements requires $2^{32}$ integer entries, or 16 GB just to store one permutation. Second, applying the permutation to find the minimum requires scanning all elements.

Instead, you simulate permutations using random hash functions. For each of the $k$ "permutations," define a hash function $h_i$ that maps shingle integers to a range of integers. The minimum hash value of the document's shingles under $h_i$ approximates the minimum element under a random permutation $\pi_i$, provided the hash function distributes values approximately uniformly.

A classic approach from the universal hashing literature uses linear functions modulo a prime:

where:

• $x$: the integer-hashed shingle value
• $a$: a random integer drawn uniformly from $\{1, \ldots, p-1\}$
• $b$: a random integer drawn uniformly from $\{0, \ldots, p-1\}$
• $p$: a large prime number larger than $M$ (for example, the Mersenne prime $2^{31} - 1$)
• $M$: the size of the hash space (for example, $2^{32}$)

For each of the $k$ hash functions, you pick different $(a, b)$ pairs. The minimum over all shingles in the document under $h_{a,b}$ gives one component of the MinHash signature.

Modern implementations often use faster non-cryptographic hash functions like MurmurHash3 or xxHash with different seeds for each of the $k$ positions. The critical requirement is that the hash functions distribute values uniformly and independently, which both MurmurHash and xxHash achieve with high quality. In very large pipelines, a technique called "one permutation MinHash" (or densified one permutation MinHash) uses a single hash of the document into a partitioned range, computing one minimum per partition rather than $k$ separate hashes, which is significantly faster.

It may seem surprising that simply taking the minimum hash value encodes useful similarity information. The intuition is that under a hash function with uniform output distribution, the minimum hash value of a large set of shingles is essentially a random sample from the shingle distribution. If two documents share many shingles, there is a high chance that the shingle with the smallest hash value appears in both. If they share few shingles, the minimums are likely to come from their non-overlapping portions and will differ.

More precisely, the minimum hash value is a random representative of the shingle set. Two documents with high Jaccard similarity are likely to pick the same representative because their shingle sets are nearly the same. Two documents with low Jaccard similarity are likely to pick different representatives.

Let's walk through a concrete MinHash computation with a small example that you can follow step by step. This will solidify both the mechanics of the algorithm and the intuition behind why it works.

Suppose we have two documents:

• Document A: "data science is great"
• Document B: "data science is wonderful"

We extract 2-word shingles:

• A's shingles: {data science, science is, is great}
• B's shingles: {data science, science is, is wonderful}

The intersection is {data science, science is}, with 2 elements. The union has 4 distinct shingles: {data science, science is, is great, is wonderful}. So the exact Jaccard similarity is:

Now suppose we assign integer IDs to the 4 distinct shingles: data science = 0, science is = 1, is great = 2, is wonderful = 3. We use two hash functions:

Computing hash values for each shingle ID:

• $h_1(0) = 1$, $h_1(1) = 4$, $h_1(2) = 2$, $h_1(3) = 0$
• $h_2(0) = 2$, $h_2(1) = 3$, $h_2(2) = 4$, $h_2(3) = 0$

Document A contains shingle IDs $\{0, 1, 2\}$, so its MinHash signature is:

Document B contains shingle IDs $\{0, 1, 3\}$, so its MinHash signature is:

The estimated Jaccard similarity is the fraction of positions where the signatures agree:

Both positions disagree, giving an estimate of 0. The true Jaccard is 0.5. This is a bad estimate, but that's expected: with only 2 hash functions, variance is enormous. The standard deviation at $J = 0.5$ with $k = 2$ is $\sqrt{0.25 / 2} \approx 0.35$, so getting an estimate anywhere from 0 to 1 is quite plausible.

With $k = 128$ hash functions, the standard deviation would be $\sqrt{0.25 / 128} \approx 0.044$, and the estimate would almost certainly fall close to 0.5. This variance reduction is why practical MinHash implementations use 128 to 256 hash functions.

Computing MinHash signatures reduces the comparison problem: instead of comparing full documents (potentially thousands of characters), you compare compact $k$-dimensional integer vectors. But you still face the $O(n^2)$ pair comparison problem. For a billion documents with 128-dimensional signatures, comparing all pairs would require roughly $6.4 \times 10^{16}$ integer comparisons. Even at 10 billion comparisons per second, this would take over 6 million seconds, or about 74 days, on a single machine.

Locality Sensitive Hashing solves this by converting the problem into a bucketing problem. Instead of comparing all pairs, you organize documents into buckets such that similar documents tend to fall into the same bucket. You then only compare documents within the same bucket, dramatically reducing the number of comparisons without losing many true near-duplicate pairs.

Locality Sensitive Hashing is a general framework for approximate nearest neighbor search. The key requirement is a hash function family that is "locally sensitive," meaning pairs with high similarity hash to the same bucket with high probability, while pairs with low similarity hash to different buckets with high probability.

For MinHash, the natural LSH family is to use each component of the signature as a hash function. If two documents have the same value at position $i$ of their signatures, they hash to the same bucket under hash function $i$. By our earlier analysis, two documents share a signature value at position $i$ with probability equal to their Jaccard similarity.

A single hash function gives very coarse bucketing. With large enough buckets, everything ends up in the same bucket; with small enough buckets, nothing shares a bucket. The banding technique refines this into a more useful filter.

The standard MinHash LSH approach divides the $k$-length signature into $b$ bands of $r$ rows each, so $k = b \times r$. For each band, you hash the $r$ values in that band (treated as a unit, for example, a tuple of $r$ integers) into a bucket. Two documents become candidate pairs if and only if they share a bucket in at least one band.

The probability that two documents with true Jaccard similarity $s$ share all $r$ values in a given band is $s^r$. The probability that they do not share all values in that band is $1 - s^r$. The probability that they fail to match in all $b$ bands is $(1 - s^r)^b$. Therefore, the probability that they share at least one band (and thus become candidates) is:

where:

• $s$: the true Jaccard similarity between the pair
• $r$: the number of rows per band
• $b$: the number of bands

This function is an S-curve in $s$: it transitions sharply from near 0 (low-similarity pairs are almost never candidates) to near 1 (high-similarity pairs are almost always candidates). The location of the transition is controlled by $r$ and $b$.

The midpoint of the S-curve transition (where the probability equals 0.5) provides a useful threshold approximation. Setting $1 - (1 - t^r)^b = 0.5$ and solving approximately:

For example, with $b = 20$ bands and $r = 5$ rows (a 100-dimensional signature), the threshold is approximately $(1/20)^{1/5} \approx 0.55$. Pairs with Jaccard similarity well above 0.55 are detected as candidates with very high probability; pairs well below 0.55 almost never become candidates.

The S-curve sharpness increases as $r$ increases. With large $r$, the condition that all $r$ rows match is stringent, producing a sharp transition. With small $r$, the transition is more gradual because matching 2 out of 2 rows is less discriminating than matching 5 out of 5.

This tunability is one of MinHash LSH's great practical advantages. By choosing $b$ and $r$, you can set the detection threshold precisely:

• For aggressive deduplication at similarity 0.7, use $b$ and $r$ such that the S-curve midpoint falls near 0.7.
• For conservative deduplication targeting only near-perfect duplicates at similarity 0.9, use parameters that push the threshold higher.
• For a fixed budget of $k$ hash functions, you trade off sharpness versus threshold by varying how you split $k$ into $b \times r$.

LSH does not give you the exact similarity of candidate pairs. It identifies a manageable set of candidate pairs that you then verify by computing exact (or more accurate estimated) Jaccard similarity from the full signatures or from the actual shingle sets. This two-stage architecture, coarse LSH filtering followed by fine verification, makes near-duplicate detection tractable at scale.

The first stage runs in linear time per document (computing the signature and performing $b$ band hash lookups) plus time proportional to the number of candidate pairs (checking each bucket). The second stage runs in time proportional to the number of candidate pairs, which is much smaller than $n^2$ for realistic similarity distributions.

In production deduplication pipelines for LLM training, the two-stage approach looks like this. All documents are processed in parallel to compute MinHash signatures. Band hashing is performed in a distributed shuffle that groups documents by band bucket. Each bucket is then checked: if it contains more than one document, those documents are emitted as candidate pairs. The candidate pairs are then verified and deduplicated, keeping one representative from each near-duplicate cluster.

The banding technique introduces two types of errors. False positives occur when two documents that are not near-duplicates happen to share a band bucket, leading you to compare them unnecessarily. False negatives occur when two true near-duplicates fail to share any band bucket, causing them to be missed.

The S-curve shape directly characterizes these errors. At similarity $s$, the probability of a false negative is $(1 - s^r)^b$: the pair falls below the detection curve. For $s$ well above the threshold, this probability is very small. At similarity $s$, the probability of a false positive (unnecessary comparison) is the same formula applied at the wrong point: $1 - (1 - s^r)^b$ for pairs that should not be candidates. For $s$ well below the threshold, this is also very small.

Near the threshold, both errors occur with non-trivial probability. This is an inherent statistical tradeoff: no threshold-based filter can simultaneously have zero false positives and zero false negatives unless the similarity distribution has a hard gap around the threshold.

For LLM training data deduplication, some false negatives are acceptable. The goal is not perfect deduplication but substantial reduction in near-duplicate content. Missing a few near-duplicate pairs is less costly than the enormous computational burden of verifying all pairs.

This section walks through a complete MinHash LSH implementation from scratch, starting with shingle extraction and working up to candidate pair detection and verification.

We begin by importing required libraries. No external packages beyond NumPy are required for the core implementation.

The first step converts each document into a set of character-level shingles. We normalize whitespace and lowercase the text before shingling to ensure consistent matching across minor formatting differences.

Documents A and B are near-duplicates (one word differs), so they share most of their 5-character shingles and receive a high Jaccard similarity score. Document C is completely unrelated to both, giving near-zero overlap with either. This confirms that the 5-gram character shingling correctly separates similar from dissimilar documents.

Next, we implement the MinHash signature computation. We use $k$ independent hash functions, each parameterized by a distinct random $(a, b)$ pair drawn from a Mersenne prime field.

The MinHash estimates closely track the exact Jaccard values. Documents A and B, which differ by a single word, receive a high estimated similarity close to the exact value. Document C, which is unrelated, receives near-zero estimates for both A vs C and B vs C. With 128 hash functions, the estimates are quite accurate.

Now we implement the banding technique that makes near-duplicate detection scalable. We divide the signature into $b$ bands of $r$ rows each, and bucket documents by their band values.

LSH correctly identifies documents A and B as candidates and correctly ignores the pairing with document C. The configuration of 16 bands times 8 rows gives a threshold near 0.72. Documents A and B, with similarity well above this threshold, are reliably detected as candidates. Document C, with near-zero similarity to the others, is correctly excluded.

Let's simulate the approach on a larger corpus to observe how MinHash LSH scales. We generate a collection of documents where some are near-duplicates, then measure the candidate reduction.

LSH reduces the number of pairs to compare by orders of magnitude. Rather than checking all nearly 500,000 possible pairs, you only compare the small fraction that share at least one LSH bucket. This reduction factor grows rapidly with corpus size, making LSH the key ingredient that allows MinHash to scale to billions of documents.

Let's visualize two key properties of MinHash: how the similarity estimate accuracy improves with more hash functions, and the S-curve behavior of LSH banding.

The heatmap reveals the two clusters of near-duplicates clearly. Documents 1 through 5 are paraphrases of the first base text; documents 6 through 10 are paraphrases of the second. Within each cluster, MinHash estimates high similarity (green). Across clusters, similarity is near zero (red). This block structure is exactly what MinHash LSH exploits: the LSH bands quickly identify the within-cluster pairs as candidates while ignoring the cross-cluster pairs.

The estimation variance of MinHash follows directly from the properties of Bernoulli trials. Each of the $k$ positions in the signature independently agrees with probability $J(A, B)$. The estimated similarity $\hat{J}$ is a sample mean of $k$ independent Bernoulli trials with success probability $J$. By standard statistics:

and the standard deviation is:

where:

• $J$: the true Jaccard similarity
• $k$: the number of hash functions
• $\hat{J}$: the MinHash estimate

The variance is maximized when $J = 0.5$, giving $\text{Var} = 0.25/k$. At the extremes ($J = 0$ or $J = 1$), the variance is zero because the answer is known exactly with no uncertainty. For deduplication, the most error-prone regime is when you are near the threshold, which is typically around 0.7 to 0.9 for LLM training pipelines. At $J = 0.8$, the variance is $0.8 \times 0.2 / k = 0.16 / k$, somewhat lower than the worst case.

For $k = 128$ and $J = 0.5$, the standard deviation is $\sqrt{0.25 / 128} \approx 0.044$. A 95% confidence interval spans roughly $\pm 1.96 \times 0.044 \approx \pm 0.086$. For deduplication decisions, you typically only care whether similarity exceeds a threshold (say, 0.8), not the exact value. An error of 0.09 around the threshold means pairs close to the threshold are uncertain, but pairs well above or well below are reliably classified.

At $k = 128$ hash functions, the 95% confidence interval width is roughly 0.17. At $k = 256$, it narrows to about 0.12. In practice, 128 hash functions is the most common choice: it provides sufficient accuracy for deduplication decisions while keeping memory requirements manageable (512 bytes per document).

The practical question is not "how accurate is the estimate?" but "how likely are we to make the wrong deduplication decision?" If your threshold is $\tau = 0.8$ and two documents have true similarity $J = 0.85$, what is the probability that the MinHash estimate falls below 0.8, causing a false negative?

With $k = 128$ and $J = 0.85$, the standard deviation is $\sqrt{0.85 \times 0.15 / 128} \approx 0.031$. The threshold is $(0.8 - 0.85) / 0.031 \approx -1.6$ standard deviations below the true value. The probability of a false negative is approximately $P(Z < -1.6) \approx 0.055$, or about 5.5%. Increasing $k$ to 256 reduces this to about 1.5%.

This analysis explains why practitioners choose 128 to 256 hash functions rather than fewer: the marginal cost in memory and computation is small, but the reduction in deduplication errors is meaningful.

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.

MinHash is a remarkably effective tool, but understanding its limitations prevents misapplication and guides parameter selection.

Very short documents (tweets, headings, short snippets of fewer than 100 characters) have few shingles, which inflates Jaccard estimates due to small set size effects. A document with only 10 unique shingles is likely to share a few with almost any other short document by chance, leading to spuriously high Jaccard estimates. A common remedy is to require a minimum document length before applying MinHash, discarding very short documents from the deduplication pipeline or applying a separate deduplication method for short texts. Most LLM training pipelines filter out documents below a word count threshold (often 50 to 100 words) before applying MinHash.

Character-level shingles of size 5 are sensitive to most paraphrasing but may incorrectly flag documents that simply share common boilerplate text, like legal disclaimers, terms of service sections, or navigation menus in otherwise distinct web pages. Word-level shingles are more robust to character-level noise but fail to detect documents that rewrite content with synonyms. Neither choice is universally correct; the right shingling strategy depends on the type of near-duplicates you want to catch. In practice, most LLM pipelines use character-level 5-grams and accept that some boilerplate similarity is tolerable.

A more sophisticated approach uses weighted MinHash, which assigns higher weight to rare shingles and lower weight to common ones, reducing the influence of boilerplate phrases on the similarity estimate. This is analogous to the IDF weighting used in TF-IDF representations.

The banding technique trades recall for efficiency. Near-duplicate pairs with similarity near or just below the threshold may be missed entirely (false negatives). The probability of a false negative at similarity $s$ is $(1 - s^r)^b$. For pairs significantly above the threshold, this probability is negligible. For pairs at or below the threshold, it can be substantial.

For deduplication of training data, some false negatives are acceptable. The goal is to reduce redundancy substantially, not eliminate it perfectly. If 95% of near-duplicate pairs are detected and removed, the training data is dramatically cleaner than the original, even if a few pairs slip through. The computational savings from missing that 5% are significant.

MinHash identifies pairs, not clusters. Two documents A and B may each be near-duplicates of a central document C without being near-duplicates of each other (if A and C share many shingles, C and B share many shingles, but A and B have little direct overlap). Naive pair-based deduplication would retain A and B while removing only duplicates of C, leaving two near-duplicate documents in the corpus.

The correct approach is connected component analysis. Build a graph where nodes are documents and edges connect near-duplicate pairs. Each connected component is a cluster of mutually near-duplicate documents (by transitivity). Keep one representative per component, discarding the rest. This is standard practice in production pipelines but adds a post-processing step.

On billions of documents, the LSH bucketing step requires careful engineering. The hash tables can exceed available memory on a single machine. A corpus of one billion documents with $b = 16$ bands creates up to $16 \times 10^9$ (document, band) entries for the hash tables. Storing these in memory requires specialized distributed hash table implementations or disk-backed storage.

Production systems partition the signature matrix across nodes and perform the band-hash bucketing in a distributed shuffle. Each node handles a subset of bands, and the shuffle redistributes (document, band hash) pairs so that all documents with the same band hash arrive at the same node. This is an efficient use of distributed compute resources but requires careful partitioning to avoid hot spots where one bucket contains a disproportionate share of documents.

Memory bandwidth is another bottleneck. Reading $k$ integers per document from a corpus of billions of documents involves terabytes of memory reads. Careful layout of the signature matrix in memory (row-major order for sequential access) and batched processing of documents significantly improve throughput.

MinHash detects near-duplicate surface text, not semantic similarity. Two documents can express identical ideas in completely different words and receive a Jaccard similarity of near zero. Conversely, two documents that are formally near-duplicates (high Jaccard similarity) might contain importantly different information if the differing words carry key content.

For LLM training data curation, this limitation is usually acceptable. The primary concern is surface redundancy, which distorts the training distribution and causes memorization. Semantic deduplication (removing documents that express the same ideas differently) is a separate and harder problem, typically approached using embedding-based similarity methods rather than MinHash.

Despite these limitations, MinHash LSH remains the practical gold standard for near-duplicate detection at scale. Its linear-time signature computation, compact storage, tunable parameters, and probabilistic guarantees make it uniquely suited to the data volumes required for LLM pretraining. No alternative approach comes close to its combination of efficiency and reliability at billion-document scale.

MinHash compresses each document into a compact signature that preserves Jaccard similarity: the probability that two signatures agree at any position equals the true Jaccard similarity of the underlying shingle sets. This probabilistic identity allows you to estimate document similarity without comparing the full texts, reducing per-pair comparison cost from the document size to the signature size.

Key takeaways from this chapter:

• Jaccard similarity measures set overlap as the ratio of intersection to union, ranging from 0 to 1. It is a natural similarity measure for shingled documents and is robust to length differences between documents.
• Shingling converts documents into sets of overlapping substrings. Character-level 5-grams are the standard choice for LLM training data deduplication because they are robust to minor paraphrasing and synonym substitution.
• The MinHash identity states that for a random permutation $\pi$, the probability that the minimum elements of two sets agree is exactly the Jaccard similarity: $P(\min_\pi(A) = \min_\pi(B)) = J(A, B)$.
• MinHash signatures of length $k$ are computed by applying $k$ independent hash functions and taking the minimum hash value per function. The fraction of matching positions estimates Jaccard similarity with standard deviation $\sqrt{J(1-J)/k}$.
• LSH banding divides the signature into $b$ bands of $r$ rows, bucketing documents by their band values. Documents sharing any bucket become candidate pairs with probability $1 - (1 - s^r)^b$, creating a tunable S-curve threshold at approximately $t \approx (1/b)^{1/r}$.
• Practical tradeoffs include shingle size (character vs. word level), number of hash functions ($k$), and LSH threshold ($b$, $r$). These parameters balance precision, recall, and computational cost for the specific deduplication task.
• At LLM training scale, MinHash LSH is applied to billions of documents in distributed pipelines, reducing near-duplicate content that would otherwise distort the learned distribution, inflate benchmark scores, and increase memorization of training text.

The next chapter explores quality filtering techniques that complement deduplication by removing documents that are syntactically valid but semantically poor, completing the picture of how raw web crawl data is transformed into a high-quality training corpus.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about MinHash and Jaccard similarity.