M5-009M5: NLP & Large Language ModelsPretraining Objectives & Data CurationMedium
⚡Flashcard Drill➔Mastery:

Data Deduplication Methods and Why It Matters in LLM Pre-training

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M5-010 →
📐 Mathematical Definition
Jaccard(A,B)=∣A∩B∣∣A∪B∣;MinHash:P(hmin⁡(A)=hmin⁡(B))=Jaccard(A,B)\text{Jaccard}(A,B)=\frac{|A\cap B|}{|A\cup B|};\qquad \text{MinHash}: P(h_{\min}(A)=h_{\min}(B))=\text{Jaccard}(A,B)
⚡ One-Sentence Core Answer
Data deduplication removes verbatim and near-duplicate text via exact hash matching and MinHash LSH, preventing model memorization, privacy leakage, and inefficient compute waste.

📌 Key Takeaways

  • •
    Why it matters: duplicate documents cause models to memorize text verbatim, amplify web crawl bias, increase vulnerability to privacy extraction attacks, and waste expensive GPU training cycles
  • •
    Exact deduplication: line-level or document-level SHA-256 hash matching; fast and removes exact duplicates (e.g., license headers, terms of service)
  • •
    Fuzzy (near-duplicate) deduplication: MinHash combined with Locality Sensitive Hashing (LSH) and connected component clustering to remove re-written or templated documents

📐 Mathematical Derivations

Mathematical Mechanism: 1. Jaccard Similarity of Shingle Sets: For document DD, extract set of kk-shingles (contiguous character or word kk-grams) S(D)S(D). The similarity between D1D_1 and D2D_2 is: J(D1,D2)=∣S(D1)∩S(D2)∣∣S(D1)∪S(D2)∣J(D_1, D_2) = \frac{|S(D_1) \cap S(D_2)|}{|S(D_1) \cup S(D_2)|} 2. MinHash Theorem (Broder): Let h:S→Rh: S \to \mathbb{R} be a random permutation hash function. The probability that the minimum hash value of two sets matches equals their Jaccard similarity: P(min⁡s∈S1h(s)=min⁡s∈S2h(s))=J(S1,S2)P\left(\min_{s \in S_1} h(s) = \min_{s \in S_2} h(s)\right) = J(S_1, S_2) By applying MM independent hash functions h1,…,hMh_1, \dots, h_M, each document is represented by a compact signature vector sig(D)=[min⁡h1(S),…,min⁡hM(S)]∈RM\mathbf{sig}(D) = [\min h_1(S), \dots, \min h_M(S)] \in \mathbb{R}^M. 3. Locality Sensitive Hashing (LSH): Partition the MM hash values into bb bands of rr rows (M=b⋅rM = b \cdot r). Two documents are hashed into the same bucket if they match identically in all rr rows of at least one band. The probability of collision is: Pcandidate=1−(1−Jr)bP_{\text{candidate}} = 1 - (1 - J^r)^b This creates an S-curve that efficiently identifies candidate pairs with J>τJ > \tau in O(N)O(N) linear time without comparing all O(N2)O(N^2) document pairs.

🏭 Production Trade-offs

Deep Dive & Engineering Trade-offs: ① Lee et al. (2022) Deduplication Findings: Deduplicating Common Crawl removed 10%10\% of tokens, but reduced memorization by an order of magnitude and resulted in models that trained faster and reached lower perplexity with identical compute. ② Exact vs Fuzzy Granularity: - Exact Hash (SHA-256): Catches boilerplate headers, footers, and copyright notices. - Fuzzy MinHash: Catches scraped news aggregators, slightly modified blog posts, and spam templates. ③ Cross-Split Leakage Removal: Deduplication between the training corpus and standard evaluation benchmarks (MMLU, GSM8K, HumanEval) is mandatory to prevent benchmark data contamination. ④ Distributed Pipeline Architecture: Deduplicating 10TB+ of text requires distributed Spark or Ray clusters; documents are partitioned by LSH bucket IDs and connected components are solved via distributed GraphX. ⑤ Interview Strategy: Derive the MinHash equality theorem, sketch the LSH band probability formula 1−(1−Jr)b1 - (1 - J^r)^b, and quantify the benefits (reduced memorization, privacy protection, compute savings).
⚠️ Common Interview Pitfalls
  • ✕
    Attempting pairwise Jaccard comparisons across billions of documents (O(N2)O(N^2) is computationally impossible without LSH)
  • ✕
    Using only exact hashing, which misses slightly modified spam, news reprints, and templated web pages
  • ✕
    Deduplicating too aggressively (e.g., removing common code function signatures or standard idiomatic language patterns)
🎯 Interviewer Follow-up Inquiries
  • ?
    How do the parameters bb (bands) and rr (rows) in LSH control false positives and false negatives for target Jaccard threshold τ\tau?
  • ?
    Why does training on duplicate data dramatically increase the risk of privacy extraction attacks?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM5-008: Impact of Data Quality and Mixture Ratios on Pre-training📋 Back to BankNext →M5-010: Curriculum Learning and Data Ordering in LLM Pre-training