MinHash › Limitations and Practical Considerations

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.