DL S049 · Quality Filters and Deduplication in Practice

Series: Deep Learning & LLMs From Scratch — 80 sessions · Session 49 / 80 · Module M08 · ~2 hours

The story we're starting with

In S046 we hand-waved "then we dedup" and moved on. That was a lie by omission — because at 100 GB of corpus, exact hashing catches maybe 30% of the duplication. The remaining 40–60% of "duplicated content" is near-duplicate: the same news article rewritten, syndicated across 40 sites, mirrored in RSS aggregators, or reposted with a different headline. Exact hash misses all of it. And if you skip near-dedup, your model memorizes news templates instead of learning language.

This is the session where we implement MinHash + LSH from scratch — the algorithm that lets you find "documents 80%+ similar to each other" in sub-quadratic time across a corpus of 100M+ documents. Every serious modern corpus (SlimPajama, RefinedWeb, FineWeb, DCLM) is built on MinHash-LSH. You need to understand it well enough to tune the parameters and debug when it misbehaves.

We'll also cover the newer half of quality filtering: classifier-based scoring. Traditional heuristic filters (Gopher-style, from S046) catch obvious junk. But if you want to compete with FineWeb-Edu, you need a small trained classifier that scores each doc for "educational value" or "coherent prose" and thresholds. It's ~200 lines of fastText. It reliably adds 3–5 points to downstream evals.

Prerequisites

• S046 (Pretraining dataset) — we're adding the near-dedup and quality-classifier stages that were placeholders there.
• S011 (MNIST in NumPy) — general Python + a bit of hashing comfort.

1 · Why exact hashing isn't enough

Toy example. Two docs:

A: "The president visited Tokyo on Tuesday to discuss trade."

B: "On Tuesday, the president visited Tokyo to discuss trade issues."

Exact hash: totally different (different bytes → different hash). Jaccard similarity on 5-gram shingles: ~0.8. To a language model, these are the same document. Train on both and you're wasting compute + risking memorization.

Now imagine the same story reprinted on 30 news sites with slightly different intros, different photo captions, and different editor byline. That's the actual scale of the problem. Lee et al. (2022) measured on C4 that ~1% of exact duplicates and another ~3% of near-duplicates existed. On raw CC pre-C4, near-dup levels are 15–40%.

Jaccard similarity between two documents:

J(A, B) = |shingles(A) ∩ shingles(B)| / |shingles(A) ∪ shingles(B)|

Where shingles(A) is the set of overlapping n-grams (usually 5-word shingles). Computed on the set, so word order sort-of matters but repetition doesn't.

Computing J pairwise for N docs is O(N²) — for 100M docs that's 10^16 comparisons. Impossible. MinHash + LSH gives you the same answer in O(N log N) with tunable false-positive rate.

2 · MinHash — the "unbiased Jaccard estimator" trick

The claim (Broder, 1997) is magical: pick a random permutation of the universe of all possible shingles. For any doc D, let h(D) = the minimum shingle (under the permutation) that appears in D. Then Pr[h(A) = h(B)] = J(A, B) exactly.

Read that again. If two docs have Jaccard 0.7, then 70% of random permutations will assign them the same "min shingle". Which means: if I compute 128 such min-hashes per doc and count how many agree, I estimate Jaccard to ±5% accuracy — with no pairwise comparison of full documents.

2.1 The 30-line implementation

Real permutations of "all possible shingles" are infeasible, so we simulate them with hash functions. Each hash function h_i acts as an independent random permutation.

import mmh3  # MurmurHash3 — fast, good enough randomness
 
def shingles(text: str, n: int = 5) -> set[str]:
    words = text.lower().split()
    return {" ".join(words[i:i+n]) for i in range(len(words) - n + 1)}
 
def minhash(text: str, num_perm: int = 128, seed_base: int = 0) -> list[int]:
    shs = shingles(text)
    if not shs:
        return [0] * num_perm
    sigs = []
    for i in range(num_perm):
        # h_i is the i-th "random permutation"
        min_h = min(mmh3.hash(sh, seed=seed_base + i, signed=False) for sh in shs)
        sigs.append(min_h)
    return sigs

That's the whole algorithm. For each of 128 hash seeds, hash every shingle and take the minimum. The 128-vector is the doc's "signature".

2.2 Estimating Jaccard from signatures

def est_jaccard(sig_a: list[int], sig_b: list[int]) -> float:
    return sum(a == b for a, b in zip(sig_a, sig_b)) / len(sig_a)

That's it. Count matching positions, divide by length. Standard error is sqrt(J(1-J)/K); for K=128 and J=0.5 that's ±0.044.

MinHash still needs pairwise comparison of signatures — O(N²) — but each comparison is a fast integer vector compare instead of a set operation. That's 100× faster but still not enough for 100M docs. Enter LSH.

3 · LSH — banding to make the query sub-quadratic

The idea: split each 128-hash signature into b bands of r hashes each (with b · r = 128). Two docs "collide" if they match on at least one entire band. Use those collisions as candidate pairs; verify with full Jaccard estimate.

The collision probability for two docs with true Jaccard J:

P(collide) = 1 - (1 - J^r)^b

Plot this for a few (b, r) pairs. It's an S-curve. The steepest part of the S is around J* = (1/b)^(1/r) — the "similarity threshold" LSH is tuned to.

For pretraining corpora, b=16, r=8 targeting J=0.8 is the SlimPajama/FineWeb standard.

3.1 The 40-line LSH implementation

from collections import defaultdict
 
class MinHashLSH:
    def __init__(self, num_perm: int = 128, b: int = 16):
        assert num_perm % b == 0
        self.num_perm = num_perm
        self.b = b
        self.r = num_perm // b
        self.buckets = [defaultdict(list) for _ in range(b)]
        # buckets[i] = {band_hash: [doc_ids]} for band i
 
    def _band_hashes(self, sig: list[int]) -> list[int]:
        return [hash(tuple(sig[i*self.r:(i+1)*self.r])) for i in range(self.b)]
 
    def add(self, doc_id: str, sig: list[int]) -> None:
        for i, bh in enumerate(self._band_hashes(sig)):
            self.buckets[i][bh].append(doc_id)
 
    def query(self, sig: list[int]) -> set[str]:
        candidates = set()
        for i, bh in enumerate(self._band_hashes(sig)):
            candidates.update(self.buckets[i].get(bh, []))
        return candidates

Use:

lsh = MinHashLSH()
sigs = {}
for doc_id, text in corpus:
    sig = minhash(text)
    for cand in lsh.query(sig):
        if est_jaccard(sig, sigs[cand]) > 0.8:
            mark_duplicate(doc_id)
            break
    else:
        sigs[doc_id] = sig
        lsh.add(doc_id, sig)

Cost: O(N · b) inserts, O(N · b · avg_bucket_size) queries. Avg bucket size stays small when b is well-chosen. Empirically this is 1000× faster than pairwise Jaccard on real corpora.

3.2 Memory

Per doc: 128 × 4-byte hashes = 512 bytes for the signature. For 100M docs = 50 GB of signatures. Plus the LSH buckets (~similar order). Doable on one 64 GB RAM box; for bigger corpora shard across machines by band-hash prefix.

For 5M docs (our 1B-token target) it's <3 GB — fits comfortably in laptop RAM.

4 · Trained quality classifiers — the FineWeb-Edu trick

Heuristic filters (S046 Gopher rules) get you 80% of the way. The last 20% needs a learned filter.

The recipe (from FineWeb-Edu, Phi-1 "textbook is all you need", DCLM baseline):

1. Take ~10k documents from your corpus.
2. Label them with a strong LLM as prompt: "Rate this document on educational value (0–5)."
3. Train a small fastText supervised classifier on the labels (text -> {0,1,2,3,4,5}).
4. Score every doc in the corpus. Threshold at some cutoff.
5. Keep only docs above threshold.

4.1 Why fastText and not a transformer

• 200-line C++ underneath, ~50k docs/sec on CPU. A neural classifier is 100× slower.
• Accuracy comparable for this task (~2% worse than a fine-tuned BERT), speed 1000× better.
• Ships as a 500 MB binary you can distribute.

4.2 Implementation

# Prep labels — sample + LLM-label
python label_docs.py --sample_size 10000 --output labels.tsv
# labels.tsv format: __label__3\tThe rise of neural networks in medicine...
 
# Train
fasttext supervised -input labels.tsv -output qualifier \
    -lr 0.5 -epoch 10 -wordNgrams 2 -dim 100

Then in Python:

import fasttext
model = fasttext.load_model("qualifier.bin")
 
def is_quality(text: str, threshold: float = 3.0) -> bool:
    lbl, prob = model.predict(text[:1000].replace("\n", " "))
    score = float(lbl[0].removeprefix("__label__"))
    return score >= threshold

Empirical gains: FineWeb-Edu (trained edu classifier at threshold 3) beat FineWeb (heuristics only) by ~4 points on MMLU at fixed compute. Phi-1 reported ~7 point HumanEval gains from classifier-filtered code.

5 · The full pipeline, sequenced

Order matters — cheap stages first, expensive stages last, so expensive stages see less data.

Cost per stage on a c7i.4xlarge (16 vCPU) for 1 TB raw text:

Nine bucks to make 1 TB raw → ~50 GB clean. That is the price for a small production-grade corpus.

6 · Ablating dedup at scale — the money experiment

Lee et al. (2022) trained several small models on identical corpora with and without dedup. Results (paraphrased):

• Removing exact dupes: ~10× less memorization of specific training examples at generation time.
• Removing near-dupes (MinHash, J>0.8): ~5–10% lower validation loss and further ~3× less memorization.
• Combined effect: higher held-out perplexity, better downstream evals, no memorization of training data.

This paper singlehandedly moved dedup from "nice to have" to "table stakes". You cannot ship a serious pretrained model without it.

7 · MinHash gotchas

8 · War stories

9 · Retention scaffold

Recall

What 2024–2025 quality-filter pipelines actually do

MinHash + LSH is table-stakes in 2025 — every serious corpus uses it. But the quality half of "quality + dedup" has evolved dramatically:

FineWeb-Edu's LLM-as-judge recipe (2024): score 500k random FineWeb docs with Llama-3-70B on a 0–5 "educational value" scale, then train a small classifier (a fine-tuned Snowflake-Arctic-Embed-M with a regression head) to predict that score. Apply the classifier to the whole 15T-token corpus, keep only docs with score >= 3. Result: 1.3T tokens, and models trained on this beat models trained on 5–10× more raw FineWeb. https://huggingface.co/HuggingFaceFW/fineweb-edu-classifier

DCLM-Baseline's fastText classifier (2024): a linear model, trained on ~200k "positives" (OpenHermes-2.5 + ELI5 answers) vs ~200k "negatives" (random CC), scores docs on how "instruction-answer-like" they read. Keep top 10%. Simpler than FineWeb-Edu, cheaper to run at scale, similar quality on downstream. https://github.com/mlfoundations/dclm

Nemotron-CC's LLM rewriting (NVIDIA 2024): flip the script — don't discard low-quality docs, rewrite them with a large LLM into higher-quality versions. Doubles usable token count from a fixed CC snapshot.

And on the dedup side, 2024–2025 pushed further:

• Suffix-array exact substring dedup (Lee et al. 2021, still standard) — catches 50-char+ repeats that MinHash misses because the docs have different overall structure but share pasted passages.
• Semantic dedup with embeddings (Abbas et al. 2023, SemDeDup, arxiv 2303.09540) — embed every doc, cluster with FAISS, drop docs whose nearest-neighbor cosine sim is above 0.9. Catches paraphrased duplicates that MinHash misses. Now used in D4 and DCLM.
• Cross-corpus dedup: FineWeb and DCLM both dedup against known benchmark sets (MMLU, HumanEval, HellaSwag prompts) to prevent contamination. This is now standard hygiene and you should do it too.

Recommended 2025 stack for a serious pretraining pipeline:

1. Language ID (fastText lid.176 or GlotLID)
2. Gopher rules (still work, still cheap)
3. MinHash + LSH near-dedup (threshold ~0.8)
4. Suffix-array exact substring dedup (50+ chars)
5. Semantic dedup (optional, expensive but worth it above 100B tokens)
6. LLM-judge-trained quality classifier (FineWeb-Edu style)
7. Benchmark-contamination filter
8. Tokenize + shard

Steps 1–4 give you FineWeb-quality output. Add steps 5–6 and you're at FineWeb-Edu / DCLM-Baseline quality.

Stretch

Implement the (b,r) tuning: write a function plot_scurve(b, r) that plots P(collide) vs J on a grid of J ∈ [0, 1]. Overlay curves for (16,8), (32,4), (8,16), (64,2). Where do they cross? Which one has the sharpest transition? Why does that matter for false-positive rate?

In your own words

"MinHash beats pairwise Jaccard because ____ and LSH beats MinHash alone because ____."

Spaced-review pointer

• S046 — you were promised near-dedup. This session delivers it. Wire MinHash+LSH into the pipeline where the placeholder was.
• S048 — a well-deduped mix makes upsampling ratios more accurate (no double-counting).

Next-session teaser

Data is done. Session 050 opens Module 09 — pretraining a real foundation model. We start with architecture choices: pre-LN vs post-LN, SwiGLU vs GELU, RoPE vs learned PE, GQA vs MHA. All the "why does every 2024 LLM look the same" questions get answered with the actual empirical evidence.

Bring back tomorrow

• Equation: Pr[minhash(A)=minhash(B)] = J(A,B).
• Recipe: b=16, r=8, num_perm=128, threshold=0.8.
• Pipeline order: cheap filters → dedup → expensive classifier → tokenize.

Previous: ← DL S048 · Next: DL S050 →