When building massive datasets for language models, code generation, or information retrieval, web-scale scraping inevitably introduces an enormous amount of redundant data. If you train a model on raw web scrapes, it will encounter the same news articles, boilerplate navigation menus, and open-source files thousands of times. This redundancy causes models to over-memorize repetitive text, biases training distributions, and wastes valuable computational resources.
The naive solution is exact cryptographic hashing (such as SHA-256). However, exact matching fails to capture near-duplicates—documents that are identical except for a modified timestamp, a different localized header, or a minor formatting change. To clean terabyte-scale corpora, we need a way to identify mathematically similar documents without performing an impossible $O(N^2)$ pairwise comparison across billions of files.
The standard framework for solving this problem at scale combines Shingling, MinHash, and Locality-Sensitive Hashing (LSH).
The Core Pipeline: From Text to Collisions
To understand why this approach scales, we must look at how it compresses high-dimensional text into compact signatures that preserve a geometric definition of similarity.
[Raw Text] ──> [N-Gram Shingles] ──> [MinHash Signatures] ──> [LSH Bands] ──> [Bucket Collisions]
1. Document as Sets: Shingling
First, text must be converted into a mathematical set. We do this by breaking a document into overlapping sequences of $N$ tokens or characters, known as $N$-grams or shingles. As explored by Sarah Weissman et al. in their analysis of structural redundancy in text corpora, representing sentences or documents as sets of shingles allows us to measure their overlap using the Jaccard similarity coefficient:
$$\text{Jaccard}(A, B) = \frac{|A \cap B|}{|A \cup B|}$$
If two documents share almost all of their text, their Jaccard similarity will be close to $1.0$. If they share no phrases, it will be $0.0$.
2. Dimensionality Reduction: MinHash
Computing the exact Jaccard similarity between every pair of documents is computationally prohibitive because shingle sets can be massive. MinHash solves this by compressing large shingle sets into short, fixed-length vectors called signatures while preserving the underlying Jaccard similarity.
Imagine we apply a random permutation to the entire vocabulary space of shingles. The "minhash" of a document is the index of the first shingle in this permuted order that appears in the document. Mathematically, a remarkable property emerges: the probability that two documents yield the same minhash value under a random permutation is exactly equal to their Jaccard similarity.
By applying hundreds of different random permutations (hash functions), we generate a signature vector for each document. If two documents have a Jaccard similarity of $0.8$, roughly 80% of the elements in their MinHash signatures will match. This technique forms the backbone of open-source dataset curation pipelines, such as those implemented by Maurice Weber et al. for the RedPajama: an Open Dataset for Training Large Language Models corpus.
3. Sub-Quadratic Clustering: Locality-Sensitive Hashing
Even with compact signatures, comparing every signature pair still scales quadratically. Locality-Sensitive Hashing (LSH) bypasses this bottleneck by focusing only on pairs that are highly likely to be similar.
The algorithm divides the MinHash signature matrix into $b$ bands, where each band contains $r$ rows.
Signature Matrix:
┌─────────────────────────┐
│ Band 1 (r rows) │ ───> Hash to Bucket X
├─────────────────────────┤
│ Band 2 (r rows) │ ───> Hash to Bucket Y
├─────────────────────────┤
│ ... │
└─────────────────────────┘
For each band, we hash the $r$ rows together into a single hash table. If two documents are near-duplicates, they will have identical row values in at least one band, causing them to hash into the exact same bucket. Documents that never collide in any bucket are discarded immediately.
This creates a sharp, S-curve threshold for similarity: the probability of a collision jumps rapidly once the Jaccard similarity crosses a specific target threshold. By tuning $b$ and $r$, engineers can aggressively filter out near-duplicates while minimizing false positives, a mechanism utilized by Denis Kocetkov et al. to deduplicate 3 terabytes of source code for The Stack: 3 TB of permissively licensed source code.
Granularity and Hybrid Strategies
Depending on the nature of the data, deduplication must be tuned to operate at different structural granularities.
Paragraph-Level vs. Document-Level
In web crawls, document-level deduplication can miss fine-grained boilerplate text. For example, two entirely different news articles might share identical cookie notices, privacy policies, or navigation sidebars.
To combat this, the authors of CCNet: Extracting High Quality Monolingual Datasets from Web Crawl Data introduced a paragraph-level deduplication strategy. By normalizing text (lowercasing and replacing digits with placeholders) and applying exact cryptographic hashing (SHA-1) to individual paragraphs rather than entire documents, they successfully isolated and stripped out recurring boilerplate content that document-level LSH would otherwise ignore.
Multi-Stage Pipelines
Modern large-scale datasets rarely rely on a single algorithm. Instead, they deploy multi-stage pipelines that combine exact and fuzzy matching to balance speed and thoroughness:
- Exact Filtering: Cryptographic hashes (like SHA-256 or MurmurHash) quickly eliminate identical files or exact URL matches, as seen in the processing of web corpora like iNLPSuite.
- Fuzzy Filtering: MinHash LSH is then applied to the remaining unique documents to catch near-verbatim copies, re-posts, and minor edits.
This hybrid approach is critical for building clean, massive multilingual datasets. For instance, Thuat Nguyen-Khanh et al. combined exact URL matching with fuzzy MinHash LSH to curate CulturaX, a 6.3-trillion-token multilingual corpus. A similar multi-stage strategy was leveraged by Chen Zhang et al. for the MC² corpus to prevent regional news re-posts from biasing minority-language models. For code-specific models, the authors of OpenCoder demonstrated that file-level deduplication using SHA256 alongside MinHash LSH significantly boosts downstream reasoning capabilities compared to coarse repository-level filtering.
Downstream Impact
Deduplication is not merely an optimization to save disk space; it fundamentally alters how models learn and how they are evaluated.
Preventing Memorization in LLMs
When a language model is trained on highly redundant web text, it tends to memorize repetitive sequences verbatim rather than learning generalized patterns. Sara Bourbour Hosseinbeigi et al. demonstrated this when constructing the Matina Persian corpus, showing that probabilistic document deduplication is essential to prevent models from parroting repetitive web content. Similarly, Thales Sales Almeida et al. found that intra-crawl deduplication drastically reduces the computational cost of training while protecting models from over-memorizing web snapshots.
Improving Retrieval Diversity
In Retrieval-Augmented Generation (RAG) systems, near-duplicates pose a major challenge. If a search query returns five slightly different versions of the same news article, those redundant segments will occupy all the top-$k$ slots in the context window, starving the language model of alternative perspectives.
As demonstrated by Ronak Pradeep in the development of the Ragnarök framework, applying LSH to a document collection before the retrieval phase ensures that the context provided to the model is diverse, maximizing the information density fed into the LLM.
Safeguarding Evaluation Integrity
If an evaluation benchmark contains near-duplicates of files present in its training set, the resulting performance metrics will be artificially inflated due to data contamination.
To ensure rigorous evaluation, modern benchmarks use similarity-based deduplication as a strict pre-filtering step. For example, Chloe Loughridge et al. used hashing-based similarity filtering in DafnyBench to prevent repetitive web-scraped code from biasing formal software verification metrics. In multimodal domains, Lijun Li et al. applied LSH to the T2ISafety prompt collection, ensuring that visual safety evaluations are not skewed by redundant, linguistically identical user prompts.
Key Foundational Work
Large Linguistically-Processed Web Corpora for Multiple Languages (2006) — contributed 1 concept elements to this direction.
Evaluating CETEMPublico, a Free Resource for Portuguese (2001) — contributed 1 concept elements to this direction.