Advanced Deduplication: MinHash, LSH, & Suffix Arrays
Web data contains millions of near-identical documents, news syndications, privacy disclaimers, and boilerplate footers. Deduplication prevents memorization, reduces loss spikes, and saves thousands of GPU hours.
Document-Level MinHash + LSH
Documents are split into n-gram sets (shingles). MinHash computes signature vectors. Locality-Sensitive Hashing (LSH) hashes signature bands into buckets to catch near-duplicates with Jaccard similarity > 0.8 without pairwise comparisons.
Line-Level & Sub-String Dedup
Common headers, footers, and cookie banners span across otherwise distinct documents. Suffix arrays locate repeated byte spans >= 50 tokens across multi-terabyte datasets.
Impact on Pre-Training
Deduplication reduces corpus size by 20%-50% while improving downstream benchmark accuracy, as models spend FLOPs learning concepts rather than repeating memorized text.
The probability that two document shingle sets produce identical minimum hash values equals their exact Jaccard overlap.
- Llama 3 data processing pipelines execute multi-stage LSH dedup across Spark/Ray clusters spanning thousands of CPU cores.