Lecture 14 · Part 4

Data: Filtering, Deduplication

Percy walks the pre-training data pipeline past acquisition — transform raw HTML and PDFs to text, filter with fast classifiers trained on a small target set, deduplicate at web scale with MinHash and locality-sensitive hashing, and mix sources with regression fits at small scale. The running constraint is that every step must be near-linear time over 100 trillion tokens, and the running trap is epoching: put too much weight on a small high-quality source and you silently train on it 50 times.

▶ Lecture video Executable lecture (.py) ↗

From HTML and PDFs to text

Last lecture established where data comes from: live services get dumped or crawled, and then processed — with terms of service and copyright hanging over all of it. This lecture is the processing: transformation, filtering, deduplication, and mixing, topped off with a tour of post-training data.

Raw data does not come as text. Common Crawl is HTML, sometimes PDFs; GitHub is directories. HTML-to-text is the main event: remove boilerplate (navigation, ads), extract content — and even “content” is fuzzy, since navigation elements might teach a model what web pages look like. The process is inherently lossy, because hierarchical, visual HTML must be linearized into a token sequence; simple tables survive as markdown, nested tables force you to “give up at some point or approximate at some point.” The tools (Trafilatura, Resiliparse, jusText) are rule-based because rule-based is fast and the task doesn’t need much intelligence — but the choice matters: on DCLM’s extended evals, Resiliparse extraction beats the alternatives.

PDFs get their own treatment in Hugging Face’s FinePDFs: many PDFs in Common Crawl are truncated (PDFs are big), forcing recrawls; conversion means OCR with a VLM, far more expensive than HTML parsing; and layout-first formats discard the semantic structure that HTML tags like h1 and p preserve. But PDFs punch above their weight: “if you bother to make a PDF, that means you probably have something interesting to say.”

Filtering: a target, a raw pool, and a fast classifier

Almost every kind of filtering instantiates this schema — language identification, quality filtering, toxicity filtering — and the scorer comes in two flavors: a cheap generative model of $T$ (KenLM, a 5-gram model, scoring $p_T(x)$ ) or a cheap classifier (fastText, essentially a linear bag-of-words model, scoring $p(T \mid x)$ ). Older datasets deliberately avoided model-based filtering to avoid bias; “these days, I think basically everyone does some amount of model-based filtering,” because unless you’re compute-plentiful, unfiltered training is wasted FLOPs.

The instantiations all rhyme. Meta’s off-the-shelf fastText language ID covers 176 languages; Dolma keeps pages with $p(\text{English}) \geq 0.5$ . OpenMathText stacked rules (contains LaTeX commands?), a KenLM trained on ProofPile (keep if perplexity is below 15,000), and a fastText math classifier with two thresholds — 0.17 if the page has LaTeX, 0.8 if not — to distill 14.7B tokens that trained 1.4B models beating models trained on 20x the data. GPT-3 took Wikipedia, WebText2, and books as positives, Common Crawl samples as negatives, and kept documents stochastically:

def keep_document(score: float) -> bool:
    return np.random.pareto(9) > 1 - score

LLaMA used pages referenced by Wikipedia as positives. Toxicity filtering in Dolma trains on the Jigsaw Toxic Comments dataset — annotated Wikipedia talk-page comments.

Deduplication: comparing everything to everything, in linear time

Filtered data is still full of duplicates. Exact duplicates come from mirror sites and forked repos; near duplicates are the same text differing by a few tokens — the MIT license embedded in different pages, articles differing by one comma, templated ads with “Canada” swapped for “USA”. Look at your data: one audit found a single gas-mask product description repeated 61,036 times in C4. Deduplication saves FLOPs without losing information and reduces memorization of copyrighted or private text; its cousin, decontamination (keep the test set out of the training set), is arguably even more important.

The design space has three axes: what’s an item (sentence, paragraph, document), what’s a match (exact, common subitem, fraction of common subitems), and what action to take (remove all, or all but one). The algorithmic challenge is that dedup is fundamentally pairwise — and $n^2$ comparisons are impossible at web scale, so everything runs through hash functions. Not cryptographic ones (SHA-256 is collision-resistant but slow); fast hash-table ones like MurmurHash, where collisions aren’t the end of the world.

Exact dedup is then simple and MapReduce-parallelizable — hash every item, keep one per hash bucket:

items = ["Hello!", "hello", "hello there", "hello", "hi", "bye"]
hash_items = itertools.groupby(sorted(items, key=mmh3.hash), key=mmh3.hash)
deduped_items = [next(group) for h, group in hash_items]

C4 did exactly this with three-sentence spans as items, removing all but one — which rips three sentences out of the middle of documents and breaks coherence. “But this is what they did.”

Near duplicates: MinHash and locality-sensitive hashing

Near-dedup first needs a similarity: Jaccard, the intersection over the union. For $A = \{1,2,3,4\}$ and $B = \{1,2,3,5\}$ , that’s $3/5 = 0.6$ . Two documents are near duplicates if their Jaccard exceeds a threshold. The question is how to find such pairs in linear time.

Code walkthrough — Checking MinHash approximates Jaccard

Each seed gives an independent random hash function; the collision rate across 100 of them estimates Jaccard:

def minhash(S: set[str], seed: int):
    return min(mmh3.hash(x, seed) for x in S)

matches = [minhash(A, seed) == minhash(B, seed) for seed in range(100)]
estimated_jaccard = sum(matches) / len(matches)   # ≈ 0.6

No pairwise comparison needed: compute each set’s MinHash independently and look for collisions.

One MinHash is too stochastic — a collision doesn’t certify Jaccard above a threshold. Locality-sensitive hashing sharpens the probabilities with an and-or structure: use $n = b \cdot r$ hash functions, split into $b$ bands of $r$ each, and declare a collision if for some band all $r$ hash functions agree.

Concretely: at $s = 0.8$ with $b=5, r=10$ , the collision probability is about 0.43. With $b = r = 10$ , similarity 0.7 collides with probability 0.25; bump $r$ to 20 and that falls to 0.008 while high similarities stay near 1. A real deduplication paper used $n = 9{,}000$ hash functions as $b = 20$ bands of $r = 450$ — a threshold around 0.99. You can drive the transition as sharp as you like by spending more hash functions. One practical note: dedup within each dataset isn’t enough — datasets duplicate each other, so dedup across the whole collection. “Sometimes that’s not done, but it should be.”

Data mixing and the epoching trap

Models train on many sources — The Pile assigned each component a weight; Marin’s token viewer tracks dozens. A mixture is just a distribution over sources, and the baselines are honest about their crudeness: vibes (“more often than you might think, what people do”), uniform sampling, or proportional-to-token-count mixing. Intuition says upweight quality, but two forces push back: diversity (literature, code, and papers are incomparable — don’t put all mass on papers), and finiteness.

Worked example — Fifty epochs by accident

Low-quality source: 10T tokens. High-quality source: 10B tokens. Naive 50/50 mixture, training for 1T tokens. Epochs over each source: $\text{epochs} = \frac{p(s) \cdot \text{train tokens}}{\text{source tokens}}$ Low: $0.5 \cdot 10^{12} / 10^{13} = 0.05$ — you touch 5% of it once. High: $0.5 \cdot 10^{12} / 10^{10} = 50$ epochs. Best case you’re wasting compute; worst case you’re overfitting — and “some big model runs have messed this up.” UniMax’s fix, born in multilingual training: sample uniformly but hard-cap epochs, requiring $p(s) \cdot \text{train tokens} \leq C$ for every source.

The principled way to choose weights is regression-based mixing (RegMix, Olmix): sample mixtures from a distribution over distributions (e.g., Dirichlet), train a swarm of small proxy models (tens to hundreds of millions of parameters), fit a regression — log-linear works well — from mixture weights to loss, then optimize it and train the big model on the argmin. It’s the scaling-laws move: cheap computation at small scale, extrapolate up. Two leaps of faith, though: that the regression stays accurate at its minimizer (optimization pushes toward extremes where coverage is thin), and that optimal mixtures transfer across scale. And targets built from downstream evals invite overfitting — load up on code evals and “guess what? You’re going to upweight all the code data.”

Post-training data: teachers, tasks, and environments

Pre-training data is task-agnostic; post-training data is task-dependent, and in the open community it is almost all synthetic. The recipe: define environments, define tasks or prompts, collect responses from a strong teacher model (humans work too, but slowly and expensively).

OpenThoughts, motivated by the o1 reasoning wave, built 1.2M examples from 27 human and synthetic question sources (Stack Exchange, NuminaMath, chemistry) with QwQ-32B as teacher. Findings: sampling 16 responses per prompt helps; a few good sources beat all sources; answer filtering didn’t help; and better models aren’t necessarily better teachers — QwQ-32B out-taught the stronger DeepSeek-R1.

Agentic coding data is scaling fast. SWE-smith uses an LM to make 128 GitHub repos installable and generate bug-introduction tasks — 50K of them. SWE-Zero noticed that SWE tasks drown in dependency hell (“most GitHub repos don’t even run”) but strong models solve many tasks without execution feedback — they carry an internal world model of code semantics — yielding 300K agent trajectories over 150K real PRs, distilled from Qwen3-Coder-480B under a no-execution prompt (with filtering, since the model sometimes tries to execute anyway), plus 13K execution-required SWE-Hero trajectories. SWE-rebench ground through 450K PRs to get 21K interactive tasks from 3.4K repos; and — released the day of the lecture — the SWE-Zero idea scaled to 12M trajectories on SWE-rebench-v2’s 32K executable plus 120K non-executable tasks. Percy’s closing caveat: real data work is grungy, domain-specific, and lives in concrete examples — “this lecture is not really representative of what data work is like.”

Back of the chalk tray — what to remember

Transformation is lossy and rule-based because it must be fast; extractor choice (Resiliparse vs. others) measurably changes model quality.
All filtering is one schema: small target set $T$ , huge raw pool $R$ , cheap scorer (KenLM or fastText) trained to find the subset of $R$ like $T$ — and the right threshold depends on how long you’ll train.
Dedup must be linear time, so it runs on hashes: exact dedup via hash buckets, near-dedup via MinHash, whose collision probability equals Jaccard similarity.
LSH’s $b$ bands of $r$ hash functions turn stochastic collisions into a phase transition at $(1/b)^{1/r}$ — sharp enough to threshold Jaccard at 0.99.
Mixing weights are found by regression at small scale, but always compute epochs per source: cap them (UniMax) or simulate scarcity by downsampling proportionally.
Post-training data is mostly synthetic — environments, tasks, and a teacher model — and better models aren’t necessarily better teachers.

Check yourself

Exercises in the lecture’s spirit — hash arithmetic and epoch accounting on paper.

Problem 14.1 Jaccard and MinHash

Documents $A$ and $B$ are represented as sets of shingles: $A$ has 60 shingles, $B$ has 50, and they share 40. What is their Jaccard similarity? If you compute MinHash with 200 independent seeds, how many collisions do you expect?

Show solution

Union $= 60 + 50 - 40 = 70$ , so $\text{Jaccard} = 40/70 \approx 0.571$ . Each seed’s MinHash collides with probability equal to the Jaccard, so expected collisions $= 200 \cdot 0.571 \approx 114$ . Each seed is an independent Bernoulli trial with the Jaccard as its success probability — that identity is the entire reason MinHash (rather than an ordinary hash) is used for near-dedup.

Problem 14.2 LSH band arithmetic

You run LSH with $b = 4$ bands of $r = 5$ hash functions. Compute the collision probability for pairs with Jaccard 0.5 and Jaccard 0.9. Where is the phase-transition threshold, and what happens to it if you double $r$ ?

Show solution

Fixed band matches with probability $s^r$ . For $s = 0.5$ : $0.5^5 = 0.03125$ , so $\Pr[\text{collide}] = 1 - (1 - 0.03125)^4 \approx 0.119$ . For $s = 0.9$ : $0.9^5 \approx 0.590$ , so $1 - (0.410)^4 \approx 0.972$ . Threshold: $(1/b)^{1/r} = 0.25^{1/5} \approx 0.758$ . Doubling $r$ to 10 gives $0.25^{1/10} \approx 0.871$ — increasing $r$ sharpens the transition and moves it right, making everything harder to match.

Problem 14.3 epoch accounting

You plan a 2T-token run over three sources: web (20T tokens, weight 0.7), code (500B tokens, weight 0.2), and curated encyclopedic text (5B tokens, weight 0.1). Compute the epochs over each source. Which weight is dangerous, and what is the largest weight the curated source can carry under a UniMax-style cap of 4 epochs?

Show solution

Epochs $= p(s) \cdot \text{train tokens} / \text{source tokens}$ . Web: $0.7 \cdot 2\times10^{12} / 2\times10^{13} = 0.07$ . Code: $0.2 \cdot 2\times10^{12} / 5\times10^{11} = 0.8$ . Curated: $0.1 \cdot 2\times10^{12} / 5\times10^{9} = 40$ epochs — the overfitting trap. The cap requires $p \cdot 2\times10^{12} \leq 4 \cdot 5\times10^9$ , so $p \leq 2\times10^{10} / 2\times10^{12} = 0.01$ . The high-quality source you love most is exactly the one whose weight must be smallest.

Problem 14.4 filtering schema design

You want a corpus of high-quality chemistry text from a 50T-token web crawl, and you have API access to a strong (expensive) LLM. Design a filtering pipeline in the lecture’s schema — name your $T$ , your $R$ , your cheap scorer, and where the phi-1 trick fits. Why can’t the strong LLM score the crawl directly?

Show solution

$R$ is the 50T-token crawl. Build $T$ phi-1-style: prompt the strong LLM to judge “educational chemistry value” on a small random subset of $R$ (order 100K documents); the positives become $T$ . Train a fastText classifier with $T$ as positives and random $R$ samples as negatives, then score all of $R$ and keep documents above a threshold — chosen with the scale-dependence caveat in mind (training longer tolerates a lower bar). The strong LLM can’t score $R$ directly because filtering must run over the entire pool: 50T tokens through an LLM is exactly the wasted compute filtering exists to avoid. The expensive model labels a sliver; the linear model extrapolates.