Pretraining data curation and cleaning: Visual walkthrough

We are answering one concrete question the whole way:

How do we find document pairs that are almost the same, without comparing every pair to every other pair?

Step 1 — What "the same" even means: shingles

WHAT. We chop each document into overlapping little word-chunks and forget the order — we keep only the set of chunks that appeared.

WHY. Two web pages that differ by a menu item or a date are still 99% the same chunks. A raw string comparison says "different". A set-of-chunks comparison says "almost identical". We want the second notion. Using overlapping windows (not disjoint blocks) means a one-word insertion only damages $k$ shingles, not the whole document — the representation is robust to small edits. This is exactly the vocabulary Deduplication and Memorization and MinHash and LSH are built on.

Figure — Pretraining data curation and cleaning

In the figure, the sentence becomes coloured tiles. Each tile is one shingle. Document $A$ is the set ${$ tile $_{1}$ , tile $_{2}$ , $\dots}$ — order thrown away, duplicates collapsed.

Step 2 — Measuring overlap: Jaccard similarity

WHAT. Count the tiles the two docs share, divide by the total distinct tiles across both.

WHY this ratio and not raw overlap count? A raw count $∣ A \cap B ∣$ is unfair: two huge documents share many tiles just by being long. Dividing by the union makes the score length-invariant — it always lands in $[0, 1]$ . $J = 1$ means identical sets; $J = 0$ means no shared tile at all. We declare "near-duplicate" when $J \geq θ$ (the parent used $θ = 0.8$ ).

Look at the overlapping circles: the mint lens in the middle is $A \cap B$ , the whole coloured region is $A \cup B$ . $J$ is literally lens area over total area.

Step 3 — One random ordering, one fingerprint: the minhash

WHAT. Give every tile a random number, then remember only the single smallest number your document owns. That one number is the document's fingerprint.

WHY the minimum? The minimum is a way of picking one specific tile at random out of the whole document — namely the one that happened to win the lowest lottery number. Because the ordering is random, this is a fair random draw from the document's tiles. That fairness is the whole secret, and it powers Step 4.

Each tile gets a random number (butter labels). The coral-circled tile is the winner — the one with the smallest number. Its number is $minhash (A)$ .

Step 4 — The magic equality, seen not memorised

WHAT. The probability that two documents produce the same fingerprint equals their Jaccard similarity — the exact number from Step 2.

WHY — the picture argument. Assume the no-ties property from Step 3 (all lottery numbers distinct, so there is a unique front-runner). Pool all tiles from $A \cup B$ and line them up by their lottery number, smallest first. Now ask: which tile sits at the very front of the line?

The two fingerprints agree exactly when that front tile lives in the shared lens $A \cap B$ . (If the winning tile is in both sets, both documents claim it as their minimum. If it belongs to only one set, only that document owns it as its minimum, so the fingerprints differ.)
The winning tile is a uniformly random member of $A \cup B$ — every tile was equally likely to draw the lowest number.
So the chance the winner sits in the lens is $\frac{∣ A \cap B ∣}{∣ A \cup B ∣} = J (A, B) .$

That is the equality. Nothing more — it is just "probability the random front-runner falls in the shared region." (Ties would blur which tile is the front-runner; Step 8 shows why that never matters in practice.)

The tiles are sorted by lottery number. The front-runner (leftmost) is highlighted; if it is a mint (shared) tile the fingerprints match. Shared tiles form a $J$ fraction of the line, so the match happens with probability $J$ .

Intuition From one coin flip to a good estimate

Let $\hat{J}$ (read "J-hat"; the hat always means our empirical estimate of the true $J$ ). One hash gives a single yes/no (match or not) — that is one coin flip whose probability of "heads" is exactly $J$ . Run all $m$ independent hashes $h_{1}, \dots, h_{m}$ and count the matches $M$ ; define $\hat{J} = \frac{M}{m} .$ Why unbiased: $M$ is a sum of $m$ independent 0/1 coin flips each with success probability $J$ , i.e. $M \sim Binomial (m, J)$ . A binomial has mean $m J$ , so $E [\hat{J}] = E [M] / m = J$ — on average it hits the truth exactly. Why the noise shrinks like $1/ m$ : the same binomial has variance $m J (1 - J)$ , so $\hat{J}$ has variance $J (1 - J) / m$ and standard deviation $J (1 - J) / m \propto 1/ m$ (Central Limit Theorem for a mean of i.i.d. flips). Quadruple $m$ ⇒ halve the error. This is exactly MinHash and LSH Example 2 in the parent: $J = 0.8$ , $m = 200$ ⇒ expect $M = 160$ matches, $\hat{J} = 0.8$ .

Step 5 — Still $O (N^{2})$ : why banding is needed

WHAT. We replaced heavy set-intersection with cheap fingerprint comparison. But we still have to compare each document's $m$ fingerprints against every other document's — that is still $N^{2}$ comparisons. We have not escaped the 16 years.

WHY we need a new idea. We want to compare a document only against a handful of likely candidates, not all $N$ . The trick: turn "similar fingerprints" into "landed in the same bucket", so hashing does the matchmaking for us.

The red arrow shows the wall we hit: an $N \times N$ grid of comparisons, almost all of them between totally unrelated documents. We need to grey out that whole grid except a thin diagonal band of real candidates.

Step 6 — Bands and rows: the bucketing trick

WHAT. Instead of demanding all $m$ fingerprints agree, we ask for a whole band of $r$ of them to agree — and we give the document $b$ independent chances (one per band) to collide with a partner.

WHY it works. Sharing an entire band of $r$ fingerprints is unlikely unless the documents are genuinely similar. So similar docs collide in buckets; dissimilar docs almost never do. We only ever compute exact $J$ for docs that already share a bucket — a tiny fraction of all pairs. That is how we escape $O (N^{2})$ .

The fingerprint column (lavender) is sliced into bands. Band 2 of doc $A$ and doc $B$ hash to the same bucket (coral), so the pair is flagged as a candidate — even though we never looked at their other bands.

Step 7 — The S-curve: the tunable wall

WHAT. A formula that says, for any true similarity $s$ , how likely the pair survives into the candidate list.

WHY it is an S-curve. For small $s$ , $s^{r}$ is tiny (raising a number below 1 to a power crushes it), so $P (s) \approx 0$ — junk pairs are ignored. As $s$ climbs past a threshold, $P (s)$ snaps up toward 1 — real duplicates are caught. The steep jump is a wall we can place by choosing $b$ and $r$ .

Three S-curves for different $(b, r)$ . The dashed vertical lines are their crossovers $s_{0}$ . Tune $(b, r)$ so the wall lands just below your target $θ$ — dups above $θ$ are almost surely caught, junk below is almost surely skipped.

Step 8 — Edge and degenerate cases (never leave a gap)

Common mistake Tuning-parameter failure modes — BOTH directions

There are two ways to mis-set $(b, r)$ , and they fail in opposite directions:

$b$ too large / $r$ too small ⇒ the wall $s_{0} = (1 - 2^{- 1/ b})^{1/ r}$ slides toward $0$ . You flag far too many low-similarity pairs (false positives) and drown in exact- $J$ checks — the compute you tried to save comes right back.
$b$ too small / $r$ too large ⇒ the wall $s_{0}$ slides toward $1$ . Now even genuine duplicates at $s = 0.85$ often fail to share any band (false negatives), so they survive into training and the memorization/privacy risk of Deduplication and Memorization returns.
The practical take-away: pick the target $θ$ first, then solve $s_{0} = (1 - 2^{- 1/ b})^{1/ r} \approx θ$ for a balanced $(b, r)$ with $m = b r$ fixed by your compute budget. Place the wall just below $θ$ so real dups clear it with near-certainty while junk stays on the flat low shelf. That single placement decision is the entire art of tuning LSH.

The one-picture summary

The whole pipeline in one frame: text → shingle set → $m$ minhash fingerprints → bands → buckets → S-curve gate → candidate pairs → exact $J$ check → drop duplicate. Each arrow is one step you just built.

Recall Feynman retelling — say it in plain words

We wanted to find web pages that are almost copies, but comparing every page to every other is impossibly slow. So: chop each page into overlapping word-tiles and forget the order (a page is now a bag of tiles). Overlap of two bags = shared tiles over total tiles — that's Jaccard, a fair 0-to-1 score. Now the trick: give every possible tile a random lottery number (from a huge range, so ties are essentially impossible), and remember only your page's smallest number — one fingerprint. Because the ordering is random and tie-free, two pages get the same fingerprint exactly as often as they share tiles — that's the magic equality. To average out the noise, use $m$ hashes built from $m$ different seeds; the match fraction $\hat{J}$ estimates $J$ with error shrinking like $1/ m$ (it's a binomial mean). Then, to avoid all-pairs comparison, glue each band of fingerprints into a string, hash that string into a bucket, and only compare pages that share a bucket. Choosing how many bands versus rows moves a wall on the similarity axis — put the wall just below your duplicate threshold and you catch nearly all real copies while ignoring nearly all junk. Handle empties, identicals, and collisions at the edges, verify every candidate with an exact $J$ check, and you can deduplicate a trillion tokens on a normal budget.

Recall Quick self-test

Why divide by the union in Jaccard, not just count shared tiles? ::: Dividing by the union makes the score length-invariant and bounded in $[0, 1]$ ; a raw count unfairly rewards long documents. In one sentence, why does $Pr [minhash equal] = J$ ? ::: Assuming no ties, the smallest-lottery tile of $A \cup B$ is a uniformly random member, and the fingerprints match exactly when it falls in the shared region, which is a $J$ fraction of the union. Where do the $m$ hashes come from, and why does $\hat{J}$ have error $\propto 1/ m$ ? ::: From $m$ different seeds of a hash family; the match count is $Binomial (m, J)$ , whose mean-based estimate $\hat{J} = M / m$ has standard deviation $J (1 - J) / m \propto 1/ m$ . What does raising $s$ to the power $r$ do to the curve? ::: It crushes small $s$ toward 0 (creating the flat low part) while leaving $s$ near 1 large, producing the S-shape wall. What are the two ways to mis-tune $(b, r)$ ? ::: $b$ too large / $r$ too small pushes the wall toward 0 (too many false positives); $b$ too small / $r$ too large pushes it toward 1 (misses real duplicates). Compute $P (1)$ and $P (0)$ . ::: $P (1) = 1$ (identicals always flagged), $P (0) = 0$ (disjoint docs never flagged).

Prerequisites & neighbours: Deduplication and Memorization · MinHash and LSH · Tokenization · Benchmark Contamination · Data Mixture and Domain Weighting · Scaling Laws for LLMs · Fine-Tuning and Instruction Data