MinHash › MinHash

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.