Chapter 21 Data Filtering and Deduplication Algorithms

21.1 Quality Filtering Algorithms

21.1.1 n-gram Models and KenLM

An interviewer designing a pre-training data pipeline will almost always ask how you distinguish high-quality web text from garbage, and the first tool you should name is a language-model perplexity filter backed by KenLM. This question shows up at the senior engineer level because it sits at the intersection of classical NLP, large-scale distributed processing, and model quality-getting it wrong can mean millions of wasted GPU-hours training on near-random bytes. The n-gram approach is deliberately crude, but that crudeness is a feature: it runs at a fraction of the cost of any neural scorer while filtering the most egregiously low-quality pages before anything more expensive touches the data.

The abstract primitive is: given a small set of high-quality target documents $T$ and a massive raw corpus $R$ (e.g., a Common Crawl dump), find a subset $R^{\prime} \subseteq R$ whose distribution resembles $T$ . All three methods in this section-n-gram models, fastText classifiers, and importance sampling-are instances of this same recipe. What changes is how you estimate the scoring function.

An n-gram language model estimates the probability of a token $w_{n}$ given the preceding $n - 1$ tokens:

P ( w_{n} | w_{n - 1} , . . . , w_{1} ) \approx \frac{C ( w_{1} , . . . , w_{n} )}{C ( w_{1} , . . . , w_{n - 1} )}

where $C ( \cdot )$ denotes corpus count. In practice, many $n$ -gram sequences never appear even in large corpora, so raw maximum-likelihood estimates assign zero probability to perfectly grammatical sentences. Kneser-Ney smoothing addresses this by backing off to lower-order $n$ -grams when counts are sparse, interpolating between orders rather than hard-cutoff discounting. KenLM is the standard open-source implementation: it uses on-disk trie structures so that models with hundreds of millions of $n$ -grams fit in memory and score millions of tokens per second on a single CPU.

Given a trained KenLM model, the score for a document is its perplexity under the target distribution:

\text{PPL} ( d ) = \exp \Biggl( - \frac{1}{| d |} \sum_{i} \log P ( w_{i} | w_{i - 1} , . . . , w_{i - n + 1} ) \Biggr)

Low perplexity means the document looks like the target; high perplexity indicates it is out-of-distribution. Documents are sorted by perplexity and a top fraction is retained.

The north-star summary: train KenLM on a clean reference corpus, score every raw document by its perplexity, and keep the low-perplexity fraction-this is the cheapest defensible filter you can run at web scale.

The key trade-off is cost vs. sophistication. A neural classifier can judge quality more accurately, but scoring a trillion tokens with a BERT-scale model would cost roughly the same in FLOPs as the pre-training run itself-you cannot spend that budget on filtering. KenLM, by contrast, is a counting procedure: fitting a 5-gram model on Wikipedia takes minutes and produces a file of a few gigabytes. Inference is a trie lookup, not a matrix multiply; throughput on a single core routinely exceeds $10^{7}$ tokens per second.

The limitation is equally clear: $n$ -grams are local. A document composed of individually plausible bigrams but globally incoherent content (shuffled sentences, SEO keyword stuffing) can fool the filter. In practice this is acceptable because the primary goal is to remove true garbage-pages filled with binary content, encoding artifacts, or character-level noise-not to make fine-grained quality judgments. The model is intentionally crude so that it can be extremely fast.

Before KenLM-based filtering became widespread, pipelines relied entirely on heuristic rules: URL blocklists, minimum word count, fraction of alphabetic characters, and so on. Rules are brittle and require constant maintenance as the web evolves. A perplexity filter generalizes from whatever reference corpus you supply, which makes it easy to retarget for new domains without rewriting logic.

A Worked Example

The CCNet pipeline-the foundation for the first LLaMA pre-training dataset-illustrates the approach concretely. The setup:

Target corpus: Wikipedia (all languages, split by language).
Raw corpus: Common Crawl WET files (one monthly snapshot $\approx$ 40B tokens after HTML stripping).
Unit of scoring: paragraph (not full document), to allow partial retention.

Step 1: Train one KenLM 5-gram model per language on the corresponding Wikipedia dump. For English, this produces a model of roughly 5-8 GB.

Step 2: For each paragraph in Common Crawl, compute perplexity under the English model (or whichever language model matches the fastText language-identification label).

Step 3: Sort paragraphs by perplexity in ascending order and retain the bottom third (lowest perplexity = most Wikipedia-like). In CCNet’s English slice this cut reduced the token count from roughly 400B to $\approx$ 130B while measurably improving downstream benchmark scores.

Arithmetic check: a 5-gram lookup over a 1,000-token paragraph requires roughly $10^{3}$ trie traversals. At $10^{7}$ tokens per second per core, scoring a 40B-token dump completes in about $40 , 000$ core-seconds-under 12 core-hours, which is negligible compared to any GPU budget.

What You Actually Decide in Practice

Reference corpus choice matters more than smoothing details. If you train KenLM on Wikipedia, you bias toward encyclopedic prose; if you train on GitHub commit messages, you bias toward code. Match the reference to the downstream use case. Mixing reference corpora (Wikipedia + books) is fine-just concatenate and retrain.
Score at the paragraph level, not the document level. Long documents often contain both excellent and garbage paragraphs. Scoring paragraphs independently lets you perform surgical removal rather than discarding entire pages. C4 uses three-sentence spans; CCNet uses single paragraphs. Both work; paragraph is usually the safer default.
Set the threshold by inspection, not formula. Examine the text at the 33rd, 50th, and 67th perplexity percentiles before committing. The right cut point varies by domain: code corpora show different perplexity distributions than news. CCNet’s top-third heuristic is a reasonable starting point for English web text.
KenLM does not replace rule-based filters; it complements them. Run basic heuristics first (minimum length, non-ASCII fraction, URL spam detection), then KenLM, then a neural classifier if budget allows. Each stage is cheap and removes material the next stage would struggle with.
Beware of perplexity collapse on short sequences. Paragraphs under 50 tokens have high variance in perplexity estimates; their scores are unreliable. Set a minimum token threshold (50-100 tokens is typical) before applying the perplexity filter.

How This Shows Up in Interviews

“Walk me through how you would filter Common Crawl to produce a high-quality English pretraining corpus.” A strong answer names the pipeline stages in order: language identification, heuristic rules, perplexity filtering with KenLM trained on a clean reference, then optionally a fastText or neural quality classifier. Quantify the expected token retention at each stage.
“Why use KenLM instead of a BERT-based classifier for quality scoring?” The key point is FLOPs budget: scoring $10^{12}$ tokens with BERT at $\sim$ 10 ms per sentence would cost millions of GPU-hours, exceeding the training budget. KenLM runs on CPUs at $10^{7}$ tokens per second; the entire web can be scored in hours on a modest CPU cluster.
“What are the failure modes of perplexity-based filtering?” Name: (1) n-grams are local, so globally incoherent text can pass; (2) the filter is language-model-centric, so stylistically unusual but valid text (poetry, code-switching) is penalized; (3) the reference corpus must match the target domain or the filter misfires.
Senior follow-up: “If your target domain is scientific papers and Wikipedia is a poor reference, how do you adapt the pipeline?” Train KenLM on a seed set of high-quality papers (arXiv abstracts, PubMed, Semantic Scholar). If the seed set is tiny ( $<$ 1B tokens), supplement with Kneser-Ney’s backoff to lower-order $n$ -grams for robustness. Alternatively, switch to an importance-sampling estimator that explicitly models both the target and raw distributions-this gives principled weighting rather than a hard threshold and handles small target sets more gracefully.

Key Takeaways

The universal filtering recipe: estimate a model on target data, score raw documents with it, keep high-scoring examples-KenLM operationalizes this with near-zero compute cost.
Kneser-Ney smoothing handles unseen $n$ -grams by interpolating with lower-order models; the implementation detail matters less than the choice of reference corpus.
KenLM throughput ( $> 10^{7}$ tokens/sec per CPU core) makes it feasible to score an entire Common Crawl snapshot in core-hours, not GPU-hours.
Score at the paragraph or sentence level, not the document level, to allow partial retention of otherwise heterogeneous pages.
KenLM is a first-pass filter, not a final verdict-follow with a discriminative classifier or importancesampling reweighter for finer-grained quality control.

21.1.2 fastText Classifiers and Importance-Sampling Filters

Once a perplexity filter has removed the worst of the web, the next question in a data-pipeline interview is how you build a supervised quality classifier without labeling millions of documents by hand-and how you justify the classifier’s compute budget relative to the training run. This topic separates engineers who have built real pipelines from those who have only read about them. The two dominant answers are fastText discriminative classifiers and importance-sampling reweighters; each has a distinct theoretical motivation and a concrete set of production trade-offs worth articulating on a whiteboard.

Both methods share the same abstract recipe: estimate the ratio of the target distribution $p$ to the raw distribution $q$ , then use that ratio to preferentially select examples from the raw corpus. They differ in whether the ratio is estimated discriminatively (fastText) or generatively (importance sampling).

fastText trains a shallow log-linear classifier over hashed $n$ -gram features. Given a vocabulary of size $V$ and $K$ output classes, a naive bag-of-words classifier needs a $V \times K$ weight matrix-unwieldy when $V$ is large. fastText adds a bottleneck hidden layer of dimension $h$ (typically $h = 16$ ), reducing parameters from $V \cdot K$ to $V \cdot h + h \cdot K$ :

\hat{y} = \operatorname{softmax} ( W_{2} \cdot \mathrm{mean} ( W_{1} \cdot \mathbf{x} ) )

where $\mathbf{x}$ is the average of hashed $n$ -gram embeddings over the document. To avoid an unbounded bigram vocabulary, all $n$ -grams are hashed into a fixed bucket count (e.g., $10^{7}$ bins) before lookup. For quality filtering specifically, $K = 2$ (positive / negative), so the output is effectively a single logistic unit. Training uses asynchronous SGD, and inference is a pair of dense matrix products-extremely fast even for documents measured in thousands of tokens.

Importance-sampling filters take a generative approach. Fit a unigram or $n$ -gram probability model $\hat{p}$ to the target corpus $T$ and a second model $\hat{q}$ to the raw corpus $R$ . The importance weight for document $d$ is:

w ( d ) = \frac{\hat{p} ( d )}{\hat{q} ( d )}

Resample documents from $R$ with probability proportional to $w ( d )$ . Documents that look more like $T$ than $R$ receive high weight and are sampled more often; documents that look more like $R$ than $T$ are down-weighted. In practice, both $\hat{p}$ and $\hat{q}$ are estimated using hashed unigram counts-exactly as in the fastText feature hashing trick-so the whole procedure is as cheap as fastText while having a clearer distribution-matching interpretation.

The key insight is that fastText asks “is this document in-distribution?” (a classification boundary) while importance sampling asks “by how much is this document over- or under-represented relative to target?” (a density ratio)-the latter is more principled for preserving diversity.

The fastText compute argument is the one interviewers probe hardest. If you are filtering a corpus to 1% of Common Crawl, the classifier sees the full raw corpus. Every FLOP you spend on the classifier must be amortized over the data retained. A BERT-style encoder scoring each document at $\sim$ 10 ms per 512-token chunk would consume $\sim$ 10 $5$ GPU-hours to $\text{score} 10^{12}$ raw tokens-rivaling the training cost itself. fastText on the same corpus, running on CPUs at $10^{6}$ documents per second, finishes in hours. The rule of thumb: if filtering discards 99% of data, the per-token classifier cost must be under $\sim$ 1/100th of the per-token training cost. fastText clears that bar; BERT does not.

Importance sampling offers a diversity guarantee that fastText lacks. A discriminative classifier optimizes the decision boundary; once most of the data cluster in the positive region, the model does not care whether it samples uniformly from that region. An importance-sampling filter explicitly adjusts for density mismatch: rare but target-consistent topics receive higher weights and are more likely to appear in the final corpus. Empirically, importance-sampling-curated corpora outperform fastText-curated ones on GLUE-style benchmarks when the target set is small, though the absolute gains are often modest ( $\lesssim$ 2-3 points).

The principal limitation of importance sampling is that the target corpus $T$ must be large enough to estimate $\hat{p}$ reliably. When $T$ is very small, the unigram estimates for rare tokens are noisy. A practical fix is Laplace or add- $\epsilon$ smoothing so that zero-count tokens receive a small but nonzero probability.

A Worked Example

phi-1 code quality filter is the clearest end-to-end example because it shows how to construct the target set $T$ when none exists a priori.

Define $T$ by prompting GPT-4 with a rubric: “Rate the educational value of this Python snippet for a student learning basic coding concepts.” Apply this to 100,000 documents sampled from the Python subset of The Stack.
Label: documents with high GPT-4 educational ratings become positive examples; the rest become negatives. This produces a labeled set of $\sim$ 100K examples-small enough that GPT-4 annotation is affordable (roughly $2,000-$5,000 at 2023 API prices for 100K $\times$ 500-token snippets).
Train classifier: embed each document with a small pre-trained code encoder, then train a random forest on those embeddings. A random forest is used rather than a neural classifier because the labeled set is small and training must be fast.
Score raw corpus: run the random forest across the full Python subset of The Stack ( $\sim$ 200B raw tokens). Random forest inference is CPU-bound and parallelizes trivially across shards.
Retain documents classified as high educational value ( $\sim$ 3B tokens selected).

Result: a 1.3B-parameter model trained on this 3B-token filtered corpus reached 17% on HumanEval at 36K training steps. The same architecture trained on the unfiltered 200B-token corpus reached only 12% at 96K steps-roughly $6 \times$ more efficient in both tokens and compute.

The compute budget check: GPT-4 annotation of 100K examples at 500 tokens each = 50M tokens at roughly $0.03/1K tokens = $1,500. Random forest scoring of 200B tokens takes perhaps 200 CPU-hours. Both are negligible versus a multi-day GPU training run.

What You Actually Decide in Practice

Use fastText when you have a natural source of positive and negative labels. GPT-3 and LLaMA used Wikipedia-referenced pages as positives and raw Common Crawl as negatives. If your domain has an obvious high-quality source (GitHub starred repos, arXiv accepted papers, curated forums), this is the fastest path. Training fastText takes minutes; inference scales to the full web on a CPU cluster in hours.
Use importance sampling when diversity matters or your positive set is tiny. If $| T | < 1$ B tokens, discriminative classifiers have too little signal to learn a reliable boundary. An importance-sampling unigram model needs only enough data to estimate token frequencies reliably-a few hundred million tokens suffices.
Use GPT-4 annotation to synthesize $T$ when no natural target exists. Label 1,000-100,000 examples (not more-beyond that cost grows without proportional gain). Train a cheap classifier (random forest, fastText) on those labels and apply it to the full corpus. This is now the dominant approach for domainspecific data curation.
Stochastic retention sharpens the boundary without hard cutoffs. Both GPT-3 and CCNet use a sigmoid sharpening function: documents near the threshold are kept or dropped probabilistically rather than by a hard threshold. This prevents the model from memorizing the exact boundary and improves diversity at the margin.
Never skip a compute budget check before choosing a classifier architecture. If the raw corpus is $N$ tokens and the training compute budget is $C$ FLOPs, the classifier can spend at most $C / ($ retention fraction $)$ FLOPs on scoring. At 1% retention, that means the classifier budget is roughly $C / 100$ . fastText almost always fits; BERT-scale almost never does.

How This Shows Up in Interviews

“How did GPT-3 build its quality classifier, and why did that approach work?” Strong answer: positive examples came from web pages linked by Reddit with $\geq$ 3 upvotes, negatives from raw Common Crawl. This required no human annotation at scale-Reddit karma acts as a noisy but free quality signal. A linear classifier (fastText) was trained on these labels and applied stochastically (not with a hard cutoff) to retain high-scoring documents.
“What is importance sampling in the context of data filtering, and when would you use it over fastText?” A strong answer defines the importance weight $\hat{p} ( d ) / \hat{q} ( d )$ , explains the resampling procedure, and names when it wins: small target sets, domains where diversity is critical, or when the discriminative boundary is ill-defined because positive and negative data overlap heavily.
“You want to add more chemistry data to a pre-training corpus. Walk me through end-to-end how you would do it.” A complete answer: (1) define $T$ using arXiv chemistry papers + textbook excerpts, (2) train KenLM on $T$ for a fast first-pass perplexity filter, (3) optionally train fastText with $T$ as positive and raw web as negative, (4) score the full corpus and retain documents above threshold, (5) deduplicate the result with MinHash LSH before mixing into the main corpus.
Senior follow-up: “fastText uses hashed $n$ -grams. What are the implications of hash collisions for quality filtering?” Collisions cause distinct $n$ -grams to share a weight. For binary classification this means the model learns a weight that represents the average behavior of all colliding $n$ -grams. With $10^{7}$

bins and a typical English vocabulary of $\sim 10^{5}$ unigrams and $\sim 10^{9}$ possible bigrams, collision probability for any single bigram is low ( $\sim$ 10 ppm), but with enough training the model adapts. The key insight is that importance-sampling unigram models have no collision problem because they only use single-token counts; this is one reason importance sampling can match fastText quality on small target sets.

Key Takeaways

fastText is a shallow log-linear model over hashed $n$ -gram features; at $K = 2$ it is binary classification that runs at $> 10^{6}$ documents per second on CPU-the dominant choice when labeled positive/negative data exists.
Importance-sampling reweighting estimates $\hat{p} ( d ) / \hat{q} ( d )$ from two $n$ -gram models and resamples accordingly; it matches distributions rather than drawing a decision boundary, which helps preserve diversity when the target set is small.
When no natural $T$ exists, use a strong LLM to annotate $\sim$ 100K examples and train a cheap classifier (fastText or random forest) on those labels-compute cost is negligible relative to pre-training.
The compute budget rule: classifier scoring cost must be less than (training cost) divided by (raw corpus size / retained size); this almost always rules out BERT-scale encoders and almost always clears fastText.
All three filtering methods (KenLM, fastText, importance sampling) share the same recipe: score raw documents relative to a target, keep the high-scoring fraction-they differ only in how the score is estimated and whether it is a hard threshold or a probabilistic retention.

21.2 Targeted Filtering Tasks

21.2.1 Language Identification

Every serious pre-training pipeline applies language identification before any other filter, because feeding multilingual noise into a monolingual model wastes tokens and measurably hurts benchmark performance. This topic comes up at the mid-level when interviewers ask how you would clean a Common Crawl dump, and it is a good test of whether candidates understand that the same lightweight classification machinery used for quality scoring can be repurposed for an entirely different dimension of the data. Getting it wrong is not catastrophic, but getting it subtly wrong - a threshold that is too loose, a model that misclassifies code as Estonian - compounds quietly across hundreds of billions of tokens.

Language identification (LID) is document-level multi-class classification: assign a language label and a confidence score to a piece of text, then threshold. The dominant tool in production is the fastText LID model, which supports 176 languages and runs at several hundred thousand paragraphs per second on a single CPU core. Its architecture is a bag of character n-grams fed into an averaged embedding layer, then a softmax over language classes - no non-linearity beyond that final softmax.

Formally, for a document $d$ with character n-gram multiset $\mathcal{G} ( d )$ , the model computes:

\log p ( \ell | d ) = \mathbf{w}_{\ell}^{\top} \Biggl( \frac{1}{| \mathcal{G} |} \sum_{g \in \mathcal{G}} \mathbf{e}_{\phi ( g )} \Biggr) - \log Z

where $\phi ( g )$ hashes n-gram $g$ into one of $B \approx 10^{7}$ buckets, $\mathbf{e}_{b}$ is a learned bucket embedding, and $Z$ is the partition function over all classes. The hashing trick bounds memory regardless of vocabulary size and is the same technique fastText uses in its text classifier. The DOLMA pipeline applies this model at the paragraph level and keeps paragraphs where $p ($ en $) > 0 . 5$ .

Language identification is the same bag-of-n-gram classification machinery used for quality and toxicity filtering - the only difference is that the label space is a set of language codes rather than a binary quality judgment.

The obvious alternative is rule-based detection: check Unicode script ranges, use curated word lists, or rely on HTML lang attributes. This works well for well-separated scripts - Latin versus Cyrillic versus CJK - but collapses on Latin-script languages that share large vocabularies (Spanish, Portuguese, Italian, Galician). A character n-gram model implicitly encodes each language’s orthographic distribution at exactly the granularity where the signal lives, without requiring a hand-curated lexicon per language.

The key trade-off is precision versus recall in a compute-constrained training regime. If the LID threshold is too permissive, non-English text contaminates the corpus and steals token budget from the target language. If it is too strict, you drop legitimate text from code-switched documents, low-resource dialects, and informal registers that look statistically unusual to the model. BLOOM was trained with only 30% English tokens; in a compute-limited regime, that dilution measurably hurt English benchmark scores relative to English-only models at the same parameter count. Monolingual labs typically accept a recall penalty to guarantee high precision.

The character n-gram approach degrades gracefully on short texts: it becomes less confident, not wrong. A single sentence might score 0.71 for English; a full paragraph by the same author might score 0.98. This is why LID should run at the paragraph or document level, not the sentence level - longer units produce better-calibrated scores.

A Worked Example

Consider building an English pre-training corpus from a 100-billion-token Common Crawl dump. Assume paragraphs average 200 tokens, giving roughly $5 \times 10^{8}$ paragraphs. The fastText LID model runs at $4 \times 10^{5}$

paragraphs per second on 4 CPU threads at 2.5 GHz. Total CPU-core-time:

\frac{5 \times 10^{8} \text{paragraphs}}{4 \times 10^{5} \text{paragraphs/core-s}} \approx 1 , 250 \text{core-seconds} \approx 21 \text{core-minutes}

Distributed across 64 cores in a Spark or Ray cluster, LID finishes in under two minutes of wall time. The compute budget is negligible compared to any downstream neural scoring step. Applying the threshold $p ($ en $) > 0 . 5$ retains roughly 45-50% of Common Crawl by token volume, since the web carries substantial non-English traffic.

Now the edge cases appear immediately. Math content scores p(en) around 0.35-0.45 because L $\text{A}$ TEX expressions and formula tokens look like no known language to the model. Inline code (Python identifiers, function names) is classified as Russian or Estonian 15-20% of the time due to identifier-character patterns. OpenWebMath handles this with a two-tier threshold: documents that pass a L $\text{A}$ TEX heuristic (more than 5% of lines contain \frac, \sum, or similar macros) are kept at $p ($ en $) > 0 . 3$ , while everything else requires $p ($ en $) > 0 . 65$ . The result was a 15-billion-token math corpus that outperformed models trained on 20 times more unfiltered data on mathematical reasoning benchmarks.

What You Actually Decide in Practice

Threshold: Start at 0.5 for a general-purpose English corpus; push to 0.65 if you prioritize precision. Drop to 0.3-0.4 for domain corpora (math, code) where the LID model is miscalibrated by design. Audit 500 randomly sampled rejections before locking the threshold - you will find surprising failures.
Classification unit: Document-level is coarser but preserves document coherence. Paragraph-level improves precision on multilingual pages but can produce incoherent documents downstream if you excise individual paragraphs. Use paragraph-level only when you are building passage-level retrieval datasets; use document-level for general pre-training corpora.
Script-level pre-filter: Before running the neural model, check Unicode script frequency. If a document is more than 50% CJK, Devanagari, or Arabic characters, assign the script’s dominant language directly and skip fastText. This saves roughly 15% of inference compute and avoids weak-signal classifications on script-heavy documents.
Code-switching: Pages that mix two languages will be classified confidently as whichever language dominates by token count. If purity matters, run sentence-level LID within paragraphs and keep only paragraphs where at least 80% of sentences agree on the majority language.
Off-the-shelf vs. fine-tuned: The public fastText LID model is sufficient for high-resource languages. For low-resource languages with fewer than $10^{7}$ training tokens in the model’s corpus, the confusion rate with geographically proximate languages can exceed 20%. In those cases, fine-tune a new output layer on dialect-specific data (Wikipedia, CommonVoice transcripts) while keeping the base embeddings frozen.

How This Shows Up in Interviews

“How would you isolate English documents from a 100 TB Common Crawl dump?” A strong answer names the fastText LID classifier, describes the character n-gram architecture, proposes a threshold with justification (0.5-0.65), and proactively raises edge cases: code, math, short texts, and languages that look similar to English at the surface. Weaker answers jump straight to regex or Unicode ranges without addressing Latin-script language confusion.
“What happens to model quality if you skip language filtering?” Strong answer: non-English tokens dilute the training budget proportionally. Cites BLOOM as a concrete example: 30% English pretraining produced noticeably weaker English benchmark scores than comparably sized English-only models under the same compute budget. The effect scales with the fraction of off-language tokens in the corpus.
Senior follow-up - “Your LID model misclassifies Python files as non-English. How do you fix this without retraining?” The senior answer: apply a two-tier threshold controlled by a domain heuristic. Documents containing more than a threshold fraction of Python keywords (def, class, import) or a high density of ASCII special characters (brackets, colons, underscores) get a relaxed LID threshold of 0.3; everything else stays at 0.65. No model retraining is needed because the heuristic compensates for the LID model’s domain blind spot. This is the same two-tier strategy OpenWebMath applies to math content.

Key Takeaways

Language identification reuses the same bag-of-character-n-gram classifier architecture as quality and toxicity filtering - there is nothing architecturally special about LID.
The fastText LID model runs at 400K paragraphs per second per core, imposing negligible compute overhead compared to any downstream neural scorer.
Training on a diluted multilingual corpus in a compute-limited regime measurably hurts target-language performance; filtering with a precision-biased threshold is almost always the right default for monolingual labs.
The classifier degrades on short texts, code, and math - compensate with domain heuristics that adjust the threshold rather than retraining the model.
Classify at the document level when downstream processing must respect document boundaries; use paragraph-level only for passage-centric datasets where intra-document coherence is not required.

21.2.2 Toxicity and Safety Filtering

Interviewers at frontier labs routinely ask how you would prevent a pre-training corpus from poisoning a model with hate speech, graphic content, and targeted harassment. The question probes two things: whether you understand that toxicity filtering uses the same classifier machinery as quality and language filtering, and whether you can articulate the precision-recall trade-off when a false positive means discarding legitimate content and a false negative means baking harmful content into a production model. This shows up at mid-to-senior level and often comes paired with a harder follow-up about what you do when the classifier is miscalibrated on marginalized dialects or domain-specific terminology.

Toxicity filtering is binary classification applied to a harm dimension rather than a quality or language dimension. The standard approach trains one or more fastText classifiers on a labeled dataset of harmful text, then scores every document in the raw corpus and discards those that exceed a threshold. The key dataset that anchors most production pipelines is the Jigsaw Toxic Comment Classification corpus: comments scraped from Wikipedia talk pages and annotated by crowdworkers across six harm categories - toxic, severe toxic, obscene, threat, insult, and identity hate.

The DOLMA pipeline trains two separate fastText classifiers on this data: one for hate speech (collapsing threat, insult, and identity hate into a single positive class) and one for NSFW content (collapsing severe toxic and obscene into a positive class). Both classifiers use the same architecture described in the quality-filtering section - a bag of character n-grams hashed into a fixed embedding table, averaged, then classified with a linear head. Each classifier outputs a scalar in $[ 0 , 1 ]$ , and documents that exceed separate per-classifier thresholds are discarded. Using two classifiers rather than one multi-label head is a practical decision: it lets you tune precision and recall independently across harm types, since the consequences of under-filtering hate speech versus under-filtering NSFW content differ by deployment context.

Toxicity filtering is harm-dimension classification with the same lightweight n-gram machinery as every other filter - the only thing that changes is the label definition and the labeled dataset you train on.

The alternative is rule-based blocklisting: maintain a list of slurs, profanity, and explicit terms and reject any document containing them. This has two failure modes. First, it generates high false-positive rates on legitimate educational, journalistic, and clinical text that necessarily discusses the same terms in context. A document explaining the history of racial slurs in American legislation and a document celebrating that history look identical to a keyword filter. Second, it is trivially bypassed by creative spelling (letter substitutions, zero-width characters, non-ASCII lookalikes) that a character n-gram model handles naturally because it operates below the word level.

The fastText classifier generalizes across these surface variants because the n-gram representation captures sub-word patterns. A model trained on the Jigsaw corpus learns that certain character sequences cluster near toxicity labels without being hard-coded to any specific word form. This is the same reason character n-grams work well for LID on closely related languages: the signal is in the distributional statistics of character transitions, not the lexicon.

The key trade-off is recall versus collateral damage to legitimate content. A conservative threshold that catches 99% of hate speech will also remove a meaningful fraction of news articles, academic discussions of extremism, and creative fiction that engages with dark themes. I have seen pipelines that aggressively filtered toxicity produce models that refused to discuss historical atrocities because the training data had been scrubbed of all documents containing relevant terminology. Tuning the threshold requires evaluating both the corpus’s downstream task performance and the rate at which known-safe documents are incorrectly discarded.

A Worked Example

Suppose you are building a 300-billion-token English corpus from Common Crawl and want to apply DOLMA-style toxicity filtering. You have two classifiers: a hate-speech classifier and an NSFW classifier, each a fastText model with a 16-dimensional hidden layer and $10^{7}$ hashed n-gram buckets.

Inference throughput for each classifier is roughly $2 \times 10^{5}$ documents per second per CPU core. A 300B-token corpus at 500 tokens per document contains $6 \times 10^{8}$ documents. Running both classifiers sequentially on 128 CPU cores:

\frac{6 \times 10^{8} \text{docs}}{2 \times 10^{5} \text{docs/core-s} \times 128 \text{cores}} \approx 23 \text{seconds per classifier}

Total wall time for both passes: under one minute. Compute cost is negligible relative to any neural quality scorer.

With the DOLMA hate-speech threshold set at 0.3 and the NSFW threshold at 0.1 (both intentionally conservative, erring toward recall), you expect to discard roughly 1-2% of the corpus. Auditing 1,000 random discards reveals the classifier’s failure modes: it flags medical and legal text discussing assault, removes news articles about far-right extremism, and incorrectly labels some African American Vernacular English as toxic. This audit is not optional - it tells you whether the precision-recall trade-off is acceptable for your deployment context and whether you need to adjust thresholds per domain.

What You Actually Decide in Practice

Threshold calibration: Never pick a threshold from the paper. Always calibrate on a human-audited sample of 500-1,000 random positives (discards) and negatives (retains). What matters is not the classifier’s accuracy on Jigsaw test data - it is the false positive rate on the domain you actually care about.
One classifier vs. multiple: A single multi-label classifier is simpler to train and maintain. Multiple single-label classifiers let you tune thresholds independently and trace discards to specific harm categories, which is valuable when explaining filtering decisions to policy and legal teams. Use multiple classifiers whenever deployment context requires accountability by harm type.
Dialect and register bias: fastText classifiers trained on Jigsaw are known to over-flag African American Vernacular English and LGBTQ+ community language. Before deploying, run the classifier on a balanced sample that includes these dialects and measure false positive rates per demographic group. If they exceed 3-5 $\times$ the baseline false positive rate, either adjust the threshold or curate additional training data for those groups.
Domain-specific thresholds: Medical corpora, legal corpora, and fiction corpora require relaxed thresholds because they legitimately discuss explicit content. A single global threshold applied across all domains is almost always wrong. Tag documents by domain before filtering and apply per-domain thresholds.
Bootstrapping the classifier with a stronger model: If you want better recall on subtle or implicit toxicity - dog whistles, coded language, context-dependent slurs - use a larger model (BERT-scale or larger) to label 100K samples from your target distribution, then distill those labels into a fastText classifier. The expensive model runs once; the fast classifier runs on the full corpus. This is the same bootstrap strategy phi-1 used for quality filtering.

How This Shows Up in Interviews

“How would you remove toxic content from a web-scale pre-training corpus?” A strong answer identifies the Jigsaw dataset as the standard training source, names the fastText classifier as the standard production tool, specifies that two classifiers (hate and NSFW) are typically trained separately, and immediately raises the precision-recall trade-off. Weak answers propose rule-based blocklists without addressing bypass mechanisms or false positive rates.
“What is the risk of over-filtering for toxicity?” Strong answer: aggressive filtering creates systematic blind spots in the trained model. A model that has never seen text discussing violence, discrimination, or explicit content in any context will refuse to engage with those topics - even in clearly beneficial settings like academic analysis, clinical documentation, or counter-speech. It also produces a biased corpus if the classifier has differential false positive rates across demographic groups.
Senior follow-up - “Your toxicity classifier was trained on Wikipedia talk-page comments. How does that affect its performance on Reddit or Twitter-style text?” The senior answer: domain shift is the central risk. Wikipedia talk pages are longer, more formal, and less code-switched than social media text; the classifier’s precision on short, informal, and heavily abbreviated posts will degrade. The fix is targeted data collection: sample 10K documents from the target domain, have annotators label them, and either fine-tune the classifier’s output layer or use the labels to recalibrate the decision threshold. The key insight is that the embedding layer trained on Jigsaw generalizes reasonably well; it is the classification boundary that shifts with domain.

Key Takeaways

Toxicity filtering reuses the same fastText n-gram classifier machinery as language and quality filtering - train on a labeled harm dataset, score the corpus, threshold.
The Jigsaw Toxic Comment corpus is the standard training source; DOLMA trains two separate classifiers (hate speech and NSFW) to allow independent threshold control.
Always audit random samples of discarded documents before deploying a threshold - false positive rates on legitimate content are the critical failure mode, not classifier accuracy on the training benchmark.
fastText toxicity classifiers are known to over-flag marginalized dialects; measure per-group false positive rates before deploying and adjust thresholds or training data accordingly.
Use a stronger model (BERT or larger) to bootstrap labels on your target domain, then distill into fastText - the expensive model runs once on 100K samples, the fast model runs on hundreds of billions of tokens.

21.3 Deduplication at Scale

21.3.1 Exact Deduplication with Bloom Filters

Exact deduplication is the first quality gate every serious pre-training pipeline runs, and it matters more than most engineers expect. A 2022 audit of C4 found a single product-description sentence appearing 61,000 times; training on that corpus without dedup is equivalent to taking 61,000 gradient steps on the same data point. Interviewers at frontier labs ask about exact dedup at every seniority level, but the senior-level question is not “do you hash things?”-it is “how do you dedup 10 trillion tokens without running out of memory?” The answer is Bloom filters.

Exact deduplication has a three-axis design space. First, the unit: sentence, paragraph, or document. Second, the match criterion: exact character equality. Third, the action: remove all copies, or keep one. The algorithmic challenge is that duplicate detection is fundamentally pairwise: to know whether item $a$ is a duplicate, you must compare it against every other item. For $n$ items that is $O ( n^{2} )$ comparisons, which is infeasible at web scale. Hashing collapses this to $O ( n )$ by converting pairwise equality into shared bucket membership: compute $h ( x )$ for every item and group by hash value. Items in the same bucket are candidate duplicates; with a collision-resistant hash such as MurmurHash3, same bucket means same content.

The standard distributed formulation-a MapReduce over hash buckets-is correct and parallelizable, but it requires persisting all hashes in a random-access structure. At 100 billion items you are building a hash table that occupies tens of gigabytes of cluster RAM. A Bloom filter solves the memory problem.

A Bloom filter is a bit array of $m$ bits, initialized to zero, with $K$ independent hash functions $h_{1} , . . . , h_{K}$ each mapping items to $\{ 0 , . . . , m - 1 \}$ . To insert item $x$ : set bits $h_{1} ( x ) , . . . , h_{K} ( x )$ to 1. To query item $x$ : return present iff all $K$ bits are already set. The filter has no false negatives-an inserted item is always reported present-but it has a tunable false positive rate. The false positive probability is approximately

P_{\mathrm{FP}} \approx \Bigl( 1 - e^{- K n / m} \Bigr)^{K} ,

where $n$ is the number of inserted items. Setting $K = ( m / n ) \ln 2$ minimizes $P_{\mathrm{FP}}$ for fixed $m$ and $n$ , yielding

P_{\mathrm{FP}} \approx \bigl( \frac{1}{2} \bigr)^{K} = 2^{- K} .

A Bloom filter trades an exactly-zero false positive rate for a predictable, tunable one-and that tradeoff buys an order-of-magnitude reduction in memory over a full hash table.

The memory savings are the decisive factor. Storing 10 billion paragraph hashes as 64-bit integers requires $10^{10} \times 8$ bytes $= 80$ GB. A Bloom filter targeting $P_{\mathrm{FP}} = 10^{- 9}$ for the same $n = 10^{10}$ items needs

m = \frac{- n \ln P_{\mathrm{FP}}}{( \ln 2 )^{2}} \approx \frac{10^{10} \times 20 . 7}{0 . 48} \approx 4 . 3 \times 10^{11} \text{bits} \approx 54 \text{GB}

of bits and nothing else-no hash table overhead, no collision chains, no string storage. Distributed across a cluster, each shard holds a slice of the filter and processes its slice of the corpus independently.

The only downside is false positives: a unique paragraph is occasionally misclassified as a duplicate and silently discarded. At $P_{\mathrm{FP}} = 10^{- 6}$ you lose roughly one paragraph per million insertions-an acceptable quality hit for a multi-trillion-token corpus. DOLMA sets $P_{\mathrm{FP}} = 10^{- 15}$ to make false discards practically zero.

C4 takes a slightly different approach: it deduplicates at the three-sentence-span level using exact matching via a hash set rather than a Bloom filter, then removes the duplicate span and leaves the surrounding document intact. The tradeoff is that post-surgery documents may no longer be coherent. Industry consensus is that this is acceptable because the model trains on billions of documents and learns to handle imperfect prose.

A Worked Example

Consider the deduplication stage for a 70B model pre-training run over 100 billion paragraphs (roughly 5 trillion tokens). You want paragraph-level dedup with $P_{\mathrm{FP}} = 10^{- 9}$ .

Size the filter. $n = 10^{11}$ , $\ln P_{\mathrm{FP}} \approx - 20 . 7$ :

m = \frac{10^{11} \times 20 . 7}{0 . 48} \approx 4 . 3 \times 10^{12} \text{bits} \approx 537 \text{GB} .

Distributed across 64 nodes, each shard holds approximately 8.4 GB-fits in a single node’s DRAM.

Choose $K$ . Optimal $K = ( m / n ) \ln 2 \approx 43 \times 0 . 693 \approx 30$ hash functions.

Verify. $P_{\mathrm{FP}} \approx 2^{- 30} \approx 9 \times 10^{- 10} \approx 10^{- 9}$ . Confirmed.

Operate. Stream paragraphs through MurmurHash3 with 30 distinct fixed seeds. For each paragraph: if any of the 30 bit positions is zero, the paragraph is unique-insert it and emit it downstream. If all 30 are set, discard. Partition paragraphs by $h_{0} ( x ) \mathrm{mod} 64$ so each node owns a disjoint shard of the bit array and a disjoint slice of the corpus.

Throughput estimate. MurmurHash3 runs at approximately 3 GB/s per core on modern hardware. For 30 hash functions on a 500-byte paragraph: $500 \times 30 / ( 3 \times 10^{9} ) \approx 5 \mu$ s per paragraph, or roughly 200,000 paragraphs per second per core. Across 64 nodes at 32 cores each: approximately 400 million paragraphs per second-the full 100 billion-paragraph corpus processes in under 5 minutes.

What You Actually Decide in Practice

Unit of deduplication. Paragraph-level is the industry default (DOLMA, RedPajama). Document-level is faster but misses partial duplicates such as boilerplate footers, license text, and templated ads. Sentencelevel catches more overlap but risks producing incoherent post-surgery documents. Choose paragraph unless you have a specific reason to differ.
False positive rate. At $P_{\mathrm{FP}} = 10^{- 6}$ you discard about 1 in a million unique paragraphs-negligible for trillion-token corpora. Setting $P_{\mathrm{FP}} = 10^{- 15}$ (DOLMA) essentially eliminates false discards but costs approximately $2 . 5 \times$ more bits. For most pipelines, $P_{\mathrm{FP}} = 10^{- 9}$ is the right default: it keeps memory reasonable and false-discard losses below measurement noise.
Hash function. Use MurmurHash3 with distinct integer seeds as the $K$ independent hash functions. Never use Python’s built-in hash(): it is randomized per process via PYTHONHASHSEED and will give inconsistent results across distributed workers.
Action: keep-first vs. remove-all. Keep-first (retain the earliest occurrence, discard later ones) is simpler and retains the data. Remove-all is appropriate for boilerplate that should never appear-but the MIT license is valid training signal; you just do not want 10,000 copies.
Exact vs. near. Exact dedup is high-precision but blind to near-duplicates differing by punctuation or one substituted word. Plan to follow with a MinHash LSH pass if your corpus contains templated content, scraped mirrors, or synthetic data.

How This Shows Up in Interviews

“Walk me through how you would deduplicate a 10-trillion-token web corpus.” Strong answer: name the three-axis design space (unit, match, action), explain hash-based bucketing for $O ( n )$ complexity, introduce Bloom filters to handle the memory constraint at scale, give the sizing formula $m \approx - n \ln P_{\mathrm{FP}} / ( \ln 2 )^{2}$ , mention MurmurHash3 and distributed sharding by hash prefix.
“What is a Bloom filter, and why use one instead of a hash set?” Strong answer: bit array with $K$ hash functions; no false negatives, tunable false positive rate $P_{\mathrm{FP}} \approx 2^{- K}$ . A hash set at $10^{10}$ items needs roughly 80 GB of RAM; a Bloom filter for the same $n$ at $P_{\mathrm{FP}} = 10^{- 9}$ needs approximately 54 GB of bits. The filter cannot be queried for keys or iterated-it only supports membership tests-so the use case fits dedup exactly.
Senior follow-up: “A false positive in your Bloom filter causes a unique paragraph to be discarded. What is the impact, and how would you detect calibration drift?” A false positive silently reduces recall with no signal-you cannot know from the output alone that a unique paragraph was lost. At $P_{\mathrm{FP}} = 10^{- 6}$ you lose roughly $n \times 10^{- 6}$ paragraphs. To audit calibration, run a random sample of discarded items through an exact hash-set lookup against the corpus; if the measured false positive rate exceeds the target, either $n$ has grown beyond the designed capacity or $m$ was sized too small. Recalibrating requires rebuilding the filter-there is no in-place resize.

Key Takeaways

Exact dedup reduces an $O ( n^{2} )$ pairwise problem to $O ( n )$ by mapping items to hash buckets; same bucket means same content.
A Bloom filter is a bit array with $K$ hash functions supporting constant-time set membership with no false negatives and tunable $P_{\mathrm{FP}} \approx 2^{- K}$ at optimal $K = ( m / n ) \ln 2$ .
Size the filter with $m \approx - n \ln P_{\mathrm{FP}} / ( \ln 2 )^{2}$ ; at $P_{\mathrm{FP}} = 10^{- 9}$ and $n = 10^{11}$ that is approximately 5 bytes per item.
Use MurmurHash3 with fixed integer seeds; never use Python’s hash() in distributed pipelines.
Paragraph granularity with keep-first action is the production default; follow with a MinHash LSH pass to catch near-duplicates.

21.3.2 Near-Deduplication with MinHash and LSH

Exact deduplication removes verbatim copies; near-deduplication removes everything else that provides nearly zero additional signal. The web is full of templated ad copy where only a city name changes, scraped articles where one synonym differs, and terms-of-service boilerplate that picks up or loses a comma across a thousand mirror sites. After exact dedup, these near-duplicates can still represent 20-40% of a large crawl. MinHash LSH is the standard algorithm for catching them at linear time complexity, and it appears in interviews as a deep-dive on probabilistic data structures applied to ML infrastructure-the kind of question that separates engineers who know the algorithm from those who have debugged it at scale.

The similarity measure for near-deduplication is Jaccard similarity. For two sets $A$ and $B$ of n-gram shingles extracted from a document:

J ( A , B ) = \frac{| A \cap B |}{| A \cup B |} .

Two documents are near-duplicates if $J ( A , B ) \geq \theta$ for some threshold $\theta$ (typically 0.8-0.99). Computing $J$ explicitly for all pairs is $O ( n^{2} )$ -infeasible at billions of documents.

MinHash solves the first part. Given a hash function $h$ drawn from a min-wise independent family, define

h_{\min} ( S ) = \min_{x \in S} h ( x ) .

Then:

P ( h_{\min} ( A ) = h_{\min} ( B ) ) = J ( A , B ) .

The argument is direct: $h_{\min} ( A ) = h_{\min} ( B )$ iff the element with the globally smallest hash value belongs to $A \cap B$ , which happens with probability $| A \cap B | / | A \cup B |$ .

Using $K$ independent MinHash functions gives a $K$ -dimensional signature vector per document. The expected fraction of matching positions between $\sigma_{A}$ and $\sigma_{B}$ equals $J ( A , B )$ , but a single signature is too noisy for a binary near-duplicate decision.

Locality-Sensitive Hashing (LSH) sharpens this estimator into a binary flag. Divide the $K$ hash functions into $b$ bands of $r$ rows each (so $K = b \times r$ ). Declare two documents as candidate near-duplicates iff at least one band has all $r$ hash values identical:

P ( \text{collision} ) = 1 - ( 1 - s^{r} )^{b} , \qquad s = J ( A , B ) .

The threshold-the similarity at which $P ($ collision $) \approx 1 - 1 / e \approx 0 . 63$ -is:

\theta \approx \biggl( \frac{1}{b} \biggr)^{1 / r} .

Increasing $r$ sharpens the sigmoid (steeper transition from near-zero to near-one probability around $\theta$ ). Increasing $b$ shifts the threshold leftward, making it easier to flag similar pairs.

MinHash LSH converts the pairwise near-duplicate problem into a linear-time bucket-collision problem by ensuring that similar documents hash to the same bucket with high probability and dissimilar documents do not.

Without LSH, the cheapest correct approach is $O ( n^{2} )$ pairwise comparisons. For $n = 5 \times 10^{9}$ documents that is $\sim 10^{19}$ comparisons-computationally hopeless. LSH reduces this to $O ( n \times b )$ hash lookups: for each document, hash each of its $b$ bands into a bucket; collect all documents sharing any bucket; optionally run exact Jaccard verification on those candidates only. The total work is proportional to the number of documents, not pairs.

The band-and-row construction creates a sigmoidal collision curve. A single MinHash function gives $P ($ collision $) = s$ -a linear ramp with no threshold behavior. The and-within-band, or-across-bands structure introduces the non-linearity that approximates a step function at $\theta$ . This is the entire point: you get near-certainty of flagging pairs above the threshold and near-certainty of missing pairs below it, without ever comparing any two documents directly.

Embedding-based similarity (FAISS with dense vectors) gives a more semantic notion of near-duplicateuseful for paraphrase detection-but costs roughly $100 \times$ more compute per document, requires a GPU-resident encoder, and is harder to parallelize on a CPU cluster. MinHash LSH runs on commodity hardware at high throughput using MurmurHash3 and is used in production by DOLMA, SlimPajama, and RedPajama-v2.

A Worked Example

Setting. Pre-training corpus, $n = 5 \times 10^{9}$ documents, target near-duplicate threshold $\theta = 0 . 8$ . Choose $b = 10$ bands, $r = 10$ rows per band ( $K = 100$ total MinHash functions).

Verify the threshold.

\theta \approx \bigl( \frac{1}{b} \bigr)^{1 / r} = \bigl( \frac{1}{10} \bigr)^{1 / 10} = 10^{- 0 . 1} \approx 0 . 794 .

Close to 0.8. Confirmed.

S-curve at $s = 0 . 5$ (well below threshold).

P ( \text{band matches} ) = 0 . 5^{10} \approx 0 . 001 , \qquad P ( \text{collision} ) = 1 - ( 1 - 0 . 001 )^{10} \approx 0 . 01 .

Only 1% of pairs at $J = 0 . 5$ are flagged as candidates. Good.

At $s = 0 . 8$ (the threshold).

P ( \text{band matches} ) = 0 . 8^{10} \approx 0 . 107 , \qquad P ( \text{collision} ) = 1 - ( 0 . 893 )^{10} \approx 0 . 70 .

About 70% of pairs at exactly the threshold are flagged, consistent with the theoretical $1 - 1 / e \approx 0 . 63$ .

At $s = 0 . 95$ (above threshold).

P ( \text{band matches} ) = 0 . 95^{10} \approx 0 . 599 , \qquad P ( \text{collision} ) = 1 - ( 0 . 401 )^{10} \approx 0 . 9999 .

Essentially all pairs at $J = 0 . 95$ are caught.

Pipeline steps.

Tokenize each document into overlapping 5-gram character shingles. A 500-word document produces roughly 2,400 shingles.
Apply $K = 100$ MurmurHash3 functions (fixed seeds 0-99) to each shingle; record the minimum per function. This yields a 100-dimensional integer signature.
Divide the signature into 10 bands of 10 values each. Hash each band-by concatenating its 10 values and hashing the result-to a 64-bit bucket key.
Group documents by (band_index, bucket_key). Any group with $\geq 2$ members is a candidate nearduplicate cluster.
Optionally verify by computing exact Jaccard on candidate pairs to eliminate false positives from accidental band collisions.

Memory per document. $100 \times 4$ bytes $= 400$ bytes for the signature. At $5 \times 10^{9}$ documents: approximately 2 TB total, distributed across 100 nodes at 20 GB each.

What You Actually Decide in Practice

Threshold choice. Use $\theta = 0 . 99$ for strict near-verbatim dedup (SlimPajama, DOLMA: one word changed per hundred words allowed). Use $\theta = 0 . 8$ when your corpus has heavy templated content and you want aggressive repetition reduction. Below $\theta = 0 . 7$ you risk discarding topically similar but sub-stantively different documents-especially dangerous in domain-specific corpora such as code or medical text.
Sizing $b$ and $r$ . Fix $K$ from the memory budget first ( $K = 100$ for 400 bytes/document). Derive $r$ from the desired sharpness: higher $r$ steepens the sigmoid. Compute $b = K / r$ . Plug into $\theta \approx ( 1 / b )^{1 / r}$ and verify the S-curve at one similarity above and one below the threshold to confirm the transition is sharp enough.
Shingle granularity. 5-gram character shingles are robust to tokenizer differences and language variation. Word n-grams are faster but language-dependent. For code, use 10-gram character shingles: they catch copy-pasted functions that differ only in variable names better than word-level n-grams do.
Verification pass. Skip it when throughput is the bottleneck-false positives from band collisions are typically well under 1% for 64-bit bucket keys. Add it when discarding good documents is costly (domainspecific corpora under 100 billion tokens) or when you need an accurate duplicate count for auditing downstream.
Semantic deduplication. MinHash operates on n-gram shingles and is blind to paraphrase. If your corpus contains synthetic data generated by rewriting existing documents, MinHash LSH will miss those nearduplicates. In that regime, embed documents with a small encoder, index with FAISS, and threshold on cosine similarity. Expect roughly $20 \times$ higher compute cost and careful threshold tuning to avoid overpruning topically related but distinct content.

How This Shows Up in Interviews

“Why is exact deduplication not enough? What does MinHash catch that a hash set misses?” Strong answer: exact dedup requires bit-for-bit identity. Near-duplicates-the same paragraph with one word changed, the same article with a different byline-survive exact dedup but add no training signal. MinHash measures Jaccard overlap over n-gram shingles; LSH converts that into a fast bucket-based collision test with a tunable threshold.
“Explain how MinHash LSH works and why it runs in linear time.” Strong answer: MinHash gives each document a $K$ -dimensional signature where the expected fraction of matching positions equals Jac-card similarity. LSH splits the signature into $b$ bands of $r$ rows; two documents collide if any band is identical. Each document performs $b$ hash lookups in $O ( K )$ time; total work is $O ( n K )$ , linear in corpus size, with no explicit pairwise comparisons.
Senior follow-up: “How do you choose $b$ and $r$ to hit a specific threshold with sharp behavior? Walk through the math.” Senior answer: the threshold formula is $\theta \approx ( 1 / b )^{1 / r}$ ; the collision probability as a function of similarity $s$ is $P = 1 - ( 1 - s^{r} )^{b}$ . Fix $K = b \times r$ from the memory budget. Choose $r$ to control sharpness-higher $r$ steepens the transition at the cost of fewer bands. Compute $b = K / r$ and verify $\theta$ against the target. Evaluate $P$ at $\theta - 0 . 05$ and $\theta + 0 . 05$ to confirm the false positive and false negative rates are acceptable. If the transition is too shallow, increase $K$ to allow a larger $r$ while maintaining $b$ .

Key Takeaways

Jaccard similarity over character n-gram shingles measures near-duplicate overlap; MinHash reduces pairwise computation from $O ( n^{2} )$ to $O ( n )$ by converting similarity to hash collision probability: $P ( h_{\min} ( A ) = h_{\min} ( B ) ) = J ( A , B )$ .
The band-and-row LSH construction creates a sigmoidal collision curve; threshold $\theta \approx ( 1 / b )^{1 / r}$ , sharpness grows with $r$ , and the transition point shifts left as $b$ increases.
Use $b = 10$ , $r = 10$ ( $K = 100$ ) for a threshold near 0.8; use $b = 20$ , $r = 450$ ( $K = 9000$ ) for a threshold near 0.99 (the SlimPajama and DOLMA settings).
False positives from band collisions are typically well under 1% with 64-bit bucket keys; a verification pass is optional and skipped in most production pipelines.
MinHash is blind to paraphrase; switch to embedding-based near-dedup when the corpus contains synthetic or heavily paraphrased content, accepting roughly $20 \times$ higher compute cost.