Deduplication at Scale: MinHash and LSH From Scratch

Why deduplication matters

It is tempting to treat deduplication as janitorial work, but empirical experiments say it changes the model. Lee et. al, in their 2021 paper "Deduplicating Training Data Makes Language Models Better", found that standard datasets are riddled with repetition, to the point that the C4 corpus contained a single 61-word sentence repeated over 60,000 times. Models trained on such data copy it back: more than one percent of their unprompted output was reproduced verbatim from the training set. Deduplicating the data cut that memorized emission by roughly a factor of ten, let the models reach the same or better accuracy in fewer training steps, and removed a train-test overlap that affected more than four percent of the validation examples in standard benchmarks, which had been quietly inflating reported numbers. Carlini et. al, in "Quantifying Memorization Across Neural Language Models" (2022), showed that the probability a model regenerates a training sequence rises with how many times that sequence was duplicated, and another paper from Kandpal et. al, "Deduplicating Training Data Mitigates Privacy Risks in Language Models" (2022), connected the same duplication to concrete privacy risk. Deduplication is, for these reasons, a standard stage in modern dataset pipelines.

The rest of this cookbook details how deduplication happens. We will be leveraging and using established methods from the literature, in particular the following ones:

• The overlap estimator: Andrei Broder's MinHash, originally introduced in "On the resemblance and containment of documents" (1997).
• The candidate-finding scheme: Locality-Sensitive Hashing (LSH) by Piotr Indyk and Rajeev Motwani, detailed in "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality" (1998).
• The band-and-row analysis (S-curve): The standard architectural treatment from Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman's textbook, "Mining of Massive Datasets".

Finding Near-Duplicates (at scale)

Exact deduplication, hashing each document and dropping collisions, is straightforward, but it also misses the point: near-duplicates that differ by a header, a changed date, or a few reworded sentences share no exact hash yet are effectively carry the same information or meaning. Consider these two examples:

• "The model achieved a 94.2% accuracy on the evaluation set, trained on 2023-10-12."
• "The model achieved a 94.2 percent accuracy on the eval set, trained on 2023-10-14."

While not strictly identical, allowing this kind of redundant data, can inflate evaluation metrics as mentioned above or cause a more costly, potentially less efficient training. Catching these cases means measuring similarity, and the natural measure for this is the Jaccard similarity, the size of the intersection over the size of the union. The trouble is that computing it for every pair of documents is quadratic; and even for a relatively small corpus of ten thousand documents, that is over fifty million comparisons.

The approach that makes this process tractable has two parts. First, replace each document with a small fixed-size signature from which Jaccard can be estimated, so we never store or intersect the full sets. Second, use those signatures to bucket similar documents together so that only documents landing in the same bucket are ever compared, which turns the quadratic all-pairs problem into a near-linear one.

Jaccard and the MinHash estimator

Document A                                    Document B
    │                                             │
[ Shingling (n-grams) ]                       [ Shingling (n-grams) ]
    │                                             │
{ "the", "he ", "e m" }                       { "the", "he ", "e c" }
    │                                             │
[ Hash Fns (h₁, h₂... hₖ) ]                   [ Hash Fns (h₁, h₂... hₖ) ]
    │                                             │
Signature A: [ min(h₁(A)), min(h₂(A))... ]    Signature B: [ min(h₁(B)), min(h₂(B))... ]
    │                                             │
    └───────────────────────┬─────────────────────┘
                            │
              Estimated Jaccard = (Matching MinHashes) / k

The MinHash technique mainly relies on one elegant trick: instead of operating on raw text, we represent each document as a set of overlapping character n-grams, or "shingles". Imagine taking a random permutation of the universe of all possible shingles. For a given document, we record only the shingle that appears first under that permutation, calling it the "minimum". For two documents, the probability that their minima agree is exactly their Jaccard similarity. Why? Because the first element of their union is equally likely to be any of the union's members, and it lands in the intersection precisely when the minima match. A single permutation yields an unbiased but very noisy one-bit estimate of Jaccard. By averaging over k independent permutations, we get a more stable estimate. In practice, shuffling massive arrays is computationally prohibitive, so the permutations are replaced by k independent hash functions, and the minimum hash value stands in for the first element under the permutation.

import numpy as np
rng = np.random.default_rng(0)
P = (1 << 61) - 1                                  # a large Mersenne prime for the hash family

def jaccard(A, B):
    return len(A & B) / len(A | B)

def minhash_signature(S, a, b):                    # k affine hashes h(x) = (a*x + b) mod P
    x = np.fromiter(S, dtype=np.int64)
    return np.array([np.min((ai * x + bi) % P) for ai, bi in zip(a, b)])

def estimate_jaccard(A, B, k, seed):
    r = np.random.default_rng(seed)
    a, b = r.integers(1, P, size=k), r.integers(0, P, size=k)
    return np.mean(minhash_signature(A, a, b) == minhash_signature(B, a, b))

# two sets with 300 shared elements and 350 unique to each -> Jaccard = 300/1000 = 0.30
elems = rng.choice(10**9, size=1000, replace=False)
A = set(elems[:650]); B = set(elems[:300]) | set(elems[650:])
print("exact Jaccard        :", round(jaccard(A, B), 4))
print("mean MinHash estimate:", round(np.mean([estimate_jaccard(A, B, 256, s) for s in range(200)]), 4))

exact Jaccard        : 0.3
mean MinHash estimate: 0.3011

Averaged over many random hash families the estimate will be very close to the true value (which is what unbiased means). A single run of 256 hashes will not be exactly 0.30, and estimating how far off it can be is the next question.

How many hashes? Estimating Variance

Each of the k hashes contributes an independent yes-or-no outcome that is one with probability equal to the Jaccard similarity and zero otherwise. The estimate is their average, so it is the mean of k independent Bernoulli trials with success probability J, and its variance is therefore J times one minus J, divided by k. The standard error shrinks like 1/√k, which sets the cost of precision: halving the error costs four times the hashes. This is why production signatures use somewhere between 64 and 256 hashes, enough to pin the estimate down without paying for precision the downstream threshold does not need.

for k in [64, 256, 1024]:
    e = [estimate_jaccard(A, B, k, s) for s in range(400)]
    J = jaccard(A, B)
    print(f"k={k:5d}  empirical SE={np.std(e):.4f}   theory sqrt(J(1-J)/k)={ (J*(1-J)/k)**0.5:.4f}")

k=   64  empirical SE=0.0554   theory sqrt(J(1-J)/k)=0.0573
k=  256  empirical SE=0.0271   theory sqrt(J(1-J)/k)=0.0286
k= 1024  empirical SE=0.0147   theory sqrt(J(1-J)/k)=0.0143

Small residual gaps come from using an affine hash family rather than true random permutations and from finite trials; they do not change the overall picture.

From documents to signatures

To apply this to text we first turn each document into a set of features by shingling (i.e., creating n-grams): sliding a window of a few consecutive words and collecting the resulting overlapping tuples. Two documents that share most of their text share most of their shingles, and a small edit changes only the few shingles that touch it, which is what makes near-duplicates show up as high Jaccard. Each shingle is hashed to an integer once, and then the k affine hashes reduce the whole set to a k-length signature. The signatures for a corpus stack into a matrix with one row per document.

import zlib

def shingles(tokens, w=3):                          # set of overlapping word w-grams
    return {tuple(tokens[i:i+w]) for i in range(len(tokens) - w + 1)}

def base_hash(shingle):                             # stable integer id for a shingle
    return zlib.crc32(str(shingle).encode()) & 0x7fffffffffffffff

K = 128
a_h = rng.integers(1, P, size=K); b_h = rng.integers(0, P, size=K)

def signature(tokens):
    ids = np.fromiter((base_hash(s) for s in shingles(tokens)), dtype=np.int64)
    return np.min((np.outer(a_h, ids) + b_h[:, None]) % P, axis=1)   # (K,) minima

LSH banding

Document A Signature                              Document B Signature
   (k = b × r)                                     (k = b × r)

[ Band 1: r rows ] ─── HASH ──> [ Bucket 42 ] <─── HASH ─── [ Band 1: r rows ] (Match!)

[ Band 2: r rows ] ─── HASH ──> [ Bucket 17 ]      
                                [ Bucket 99 ] <─── HASH ─── [ Band 2: r rows ] (Miss)
       ...                                ...

[ Band b: r rows ] ─── HASH ──> [ Bucket 05 ] <─── HASH ─── [ Band b: r rows ] (Match!)

Result: Documents A and B collided in at least one band. They are a candidate pair.

Signatures make similarity cheap to estimate, but we still cannot afford to compare every pair. Banding is the trick that avoids it. Split each k-length signature into b bands of r rows, so that k = b x r, and hash each band to a bucket. Two documents become a candidate pair if they land in the same bucket in at least one band, meaning they agreed on all r rows of that band. The intuition is that similar documents are likely to match exactly on some band by chance, while dissimilar ones almost never do, so we only ever compare documents that already collided somewhere.

def candidate_pairs(sigs, bands, rows):
    pairs = set()
    for band in range(bands):
        block = sigs[:, band*rows:(band+1)*rows]
        buckets = {}
        for i in range(len(sigs)):
            key = (band, block[i].tobytes())        # exact match on all r rows of this band
            buckets.setdefault(key, []).append(i)
        for members in buckets.values():
            for x in range(len(members)):
                for y in range(x + 1, len(members)):
                    pairs.add((members[x], members[y]))
    return pairs

The S-curve

Banding works because of a single probability, and that same probability is what the choice of bands and rows lets you tune. For a pair of documents with Jaccard similarity s, we can follow the chance that they end up as a candidate step by step:

• Two signatures agree on a single row with probability s, the Jaccard similarity itself.
• They agree on all r rows of one band with probability s^r, since the rows are independent.
• They therefore fail to match on a given band with probability 1 − s^r.
• They fail on all b bands with probability (1 − s^r)^b.
• So they match on at least one band, and become a candidate pair, with probability 1 − (1 − s^r)^b.
• The threshold, where that probability crosses one half, sits approximately at (1/b)^(1/r).

Plotted against s, this traces an S-shaped curve: flat and near zero for dissimilar pairs, rising steeply through the threshold, then flat and near one for similar pairs. Moving rows and bands slides that steep region left or right, which is the entire tuning knob. This derivation and its S-curve are the standard treatment from Mining of Massive Datasets.

def collision_prob(s, b, r):
    return 1 - (1 - s**r)**b

# verify the formula against direct simulation of banding on real signatures
def make_sets(shared, uniq):
    e = rng.choice(10**9, size=shared + 2*uniq, replace=False)
    return set(e[:shared]) | set(e[shared:shared+uniq]), set(e[:shared]) | set(e[shared+uniq:])

b_, r_ = 20, 5
for target in [0.3, 0.5, 0.7, 0.85]:
    uq = int(round(700 * (1 - target) / (2 * target)))
    A2, B2 = make_sets(700, uq); s = jaccard(A2, B2)
    hits = 0
    for seed in range(300):
        rr = np.random.default_rng(seed)
        aa, bb = rr.integers(1, P, size=b_*r_), rr.integers(0, P, size=b_*r_)
        sa, sb = minhash_signature(A2, aa, bb), minhash_signature(B2, aa, bb)
        hits += any(np.array_equal(sa[j*r_:(j+1)*r_], sb[j*r_:(j+1)*r_]) for j in range(b_))
    print(f"s={s:.3f}  simulated P={hits/300:.3f}   formula 1-(1-s^r)^b={collision_prob(s, b_, r_):.3f}")

s=0.300  simulated P=0.040   formula 1-(1-s^r)^b=0.047
s=0.500  simulated P=0.490   formula 1-(1-s^r)^b=0.470
s=0.700  simulated P=0.970   formula 1-(1-s^r)^b=0.975
s=0.850  simulated P=1.000   formula 1-(1-s^r)^b=1.000

The simulated collision rates track the formula across the whole curve. The threshold approximation is by definition not an exact measure. It is best to plot the real curve for any candidate setting.

Choosing bands and rows

With the number of hashes fixed, the split into bands and rows is the whole precision-recall tradeoff. More rows per band demands longer exact agreement, which pushes the threshold up: fewer false positives, but genuine near-duplicates also starts being flagged and create false negatives. More bands gives more chances to collide, which pulls the threshold down: higher recall, but more dissimilar pairs will count as false positives. Computing the table below makes it easier to understand the trade-off, in this example for a fixed budget of 128 hashes.

K = 128
print(f"{'bands':>5} {'rows':>5} {'threshold~':>11}   P(cand) at s=0.5   at s=0.8")
for bands, rows in [(64, 2), (32, 4), (16, 8), (8, 16)]:
    thr = (1/bands)**(1/rows)
    print(f"{bands:5d} {rows:5d} {thr:11.2f}   {collision_prob(0.5, bands, rows):15.3f}   "
          f"{collision_prob(0.8, bands, rows):8.3f}")

bands  rows  threshold~   P(cand) at s=0.5   at s=0.8
   64     2        0.12             1.000      1.000
   32     4        0.42             0.873      1.000
   16     8        0.71             0.061      0.947
    8    16        0.88             0.000      0.204

At 64 bands of 2, almost everything collides, including pairs at similarity 0.5, so recall is near total and precision is poor. At 8 bands of 16, only very similar pairs survive, so precision is high and moderately similar duplicates are missed. The middle rows are where most deduplication lives, and which one you pick depends on how similar two documents must be before you are willing to call them the same.

Deduplicating a corpus in practice

Putting the parts together, we build a corpus where the answer is known: generate unique documents, and for some of them add a near-duplicate that changes ten percent of the words. Running signatures, banding, and candidate generation should recover those planted pairs and few others.

VOCAB = 3000; L = 50
def random_doc():    return list(rng.integers(VOCAB, size=L))
def near_dup(seq, frac=0.10):
    s = seq.copy()
    for idx in rng.choice(L, size=int(L*frac), replace=False):
        s[idx] = rng.integers(VOCAB)
    return s

docs, truth = [], set()
for _ in range(8000):
    docs.append(random_doc())
    if rng.random() < 0.3:                          # 30% get a planted near-duplicate
        docs.append(near_dup(docs[-1]))
        truth.add((len(docs)-2, len(docs)-1))
N = len(docs)

import time
t0 = time.time(); sigs = np.stack([signature(d) for d in docs]); t_sig = time.time() - t0
t0 = time.time(); cand = {tuple(sorted(c)) for c in candidate_pairs(sigs, 32, 4)}; t_lsh = time.time() - t0

tp = len(cand & truth); fp = len(cand - truth); fn = len(truth - cand)
print(f"documents={N}  planted pairs={len(truth)}")
print(f"candidates={len(cand)}  TP={tp} FP={fp} FN={fn}  precision={tp/(tp+fp):.3f}  recall={tp/(tp+fn):.3f}")
print(f"signatures {N/t_sig:,.0f} docs/s;  LSH {t_lsh:.2f}s")
print(f"pairs examined {len(cand):,} vs all-pairs {N*(N-1)//2:,} ({100*len(cand)/(N*(N-1)//2):.4f}%)")

documents=10342  planted pairs=2342
candidates=2235  TP=2235 FP=0 FN=107  precision=1.000  recall=0.954
signatures 2,846 docs/s;  LSH 0.40s
pairs examined 2,235 vs all-pairs 53,473,311 (0.0042%)

Every candidate the pipeline returned was a real planted duplicate, so precision is perfect here, and it recovered about ninety-five percent of them; the missed pairs are the ones whose ten-percent edit happened to drag their similarity below the band threshold, which is the false-negative side of the S-curve. The number that matters for scale is the last line: the pipeline compared about two thousand pairs instead of fifty-three million, four thousandths of one percent of the all-pairs work, and that ratio is the entire reason to go for this kind of approach.

Does it scale?

The signature step is linear in the number of documents and the banding step examines only colliding pairs, so the pipeline is near-linear overall, which is what lets it reach real corpus sizes. At the few thousand documents per second measured above in plain Python, a million documents is a few minutes of signature building and ten million is on the order of an hour, and an optimized or vectorized hasher moves that up considerably. The constraint at ten million is not time but memory: a signature matrix of ten million rows by 128 sixty-four-bit hashes is about ten gigabytes, more than many laptops hold at once, so at that size you either drop to 32-bit hashes, use fewer of them, or stream the documents through banding in shards rather than materializing every signature.

Existing Libraries

In practice, this whole process can be done using libraries such as datasketch, which implements exactly this MinHash and LSH. We run a quick comparison with our from scratch implementation below.

# pip install datasketch  (run in your environment)
from datasketch import MinHash, MinHashLSH

def ds_minhash(tokens, num_perm=128):
    m = MinHash(num_perm=num_perm)
    for s in shingles(tokens):
        m.update(str(s).encode())
    return m

mins = [ds_minhash(d) for d in docs]

# 1) our estimate vs datasketch on a few planted pairs
for i, j in list(truth)[:5]:
    print("ours:", round(float(np.mean(sigs[i] == sigs[j])), 3),
          " datasketch:", round(mins[i].jaccard(mins[j]), 3))

# 2) candidate sets should largely agree
lsh = MinHashLSH(threshold=0.5, num_perm=128)
for idx, m in enumerate(mins):
    lsh.insert(idx, m)
ds_pairs = set()
for idx, m in enumerate(mins):
    for j in lsh.query(m):
        if j != idx: ds_pairs.add(tuple(sorted((idx, j))))
print("overlap with our candidates:", len(ds_pairs & cand), "/", len(ds_pairs))

ours: 0.609  datasketch: 0.562
ours: 0.562  datasketch: 0.578
ours: 0.539  datasketch: 0.5
ours: 0.617  datasketch: 0.68
ours: 0.5  datasketch: 0.508
overlap with our candidates: 1763 / 1843

Practical Impact of Dedup

The payoff for all of this shows up in the trained model, and the literature is fairly consistent about the direction. Lee et. al (2021) found that removing near-duplicates let their models reach the same or better accuracy in fewer training steps, cut memorized verbatim emission by roughly a factor of ten, and, by removing the train-test overlap that had contaminated more than four percent of standard validation sets, produced more trustworthy evaluations. The gain is partly about not spending compute learning the same passages repeatedly, and partly about not overfitting the ones that happen to be duplicated thousands of times.

The idea also generalizes past exact and near-exact text matching. Abbas et. al, in "SemDeDup: Data-efficient Learning at Web-scale through Semantic Deduplication" (2023), removed pairs that are close in an embedding space rather than close in surface tokens, and reported reaching comparable performance while training on substantially less data. Tirumala et. al built on this in "D4: Improving LLM Pretraining via Document De-Duplication and Diversification" (2023), pairing semantic deduplication with a diversification step and reporting improved pretraining efficiency over training on the raw pool. The common thread across all of these is that a large share of a scraped corpus is redundant, and cutting the redundancy buys back compute and, often, quality.

Going Further

What we built is the mechanism in miniature. A production pipeline keeps the same MinHash and banding at its core but hardens everything around it: text is normalized before shingling so cosmetic differences do not defeat the match, the candidate pairs become the edges of a graph whose connected components are the duplicate clusters, exact-substring deduplication over suffix arrays runs alongside to catch long repeated spans that document-level matching misses, and the whole thing is sharded across machines because even near-linear work is not fast enough at web scale. Different implementation tricks make this process robust and parallel.

There is also a more interesting question hiding under the definition. We have treated a duplicate as two documents that share many tokens. One step deeper is semantic: two passages can carry nearly the same meaning with almost no shared tokens, which is what Abbas et. al target in SemDeDup (2023) by deduplicating in an embedding space rather than a token space. A step deeper still is to define redundancy by a sample's effect on training. Each example, during a gradient step, pushes the weights in some direction by some amount, and two examples that push the model the same way are, in a pragmatic sense, redundant even if they look nothing alike. This is the intuition behind gradient- and influence-based data selection: coreset methods that pick a subset whose gradients approximate the full dataset's (Mirzasoleiman et. al, "Coresets for Data-efficient Training of Machine Learning Models", 2020), influence functions that estimate how a training point changes the model (Koh and Liang, "Understanding Black-box Predictions via Influence Functions", 2017), the trajectory-influence view of Pruthi et. al ("Estimating Training Data Influence by Tracing Gradient Descent", 2020), and their scaling to instruction tuning through low-dimensional gradient similarity in Xia et. al's "LESS: Selecting Influential Data for Targeted Instruction Tuning" (2024). These are usually framed as data selection or pruning rather than deduplication proper, and applying them at pretraining scale is still an open and active area of research, but they point at the same goal from the other end: spend training on what actually moves the model.

Common questions

Is MinHash an exact similarity?

No. It is an unbiased estimator of Jaccard similarity whose variance is J times one minus J over the number of hashes, so more hashes means a tighter estimate at a one-over-root-k rate. You choose the number of hashes to make the estimate precise enough for the threshold you care about, not to make it exact, because exactness would cost storing the full sets, which is the thing MinHash exists to avoid.

Why LSH instead of comparing all pairs?

Because all-pairs comparison is quadratic and dies at scale. On the ten thousand documents above it would have been over fifty million comparisons; LSH examined about two thousand, four thousandths of one percent, by only ever comparing documents that already collided in some band. The banding turns a quadratic problem into a near-linear one, which is the difference between a method that runs on a corpus and one that does not.

How do I pick the similarity threshold?

Through the bands and rows. For a fixed number of hashes, the split into b bands of r rows sets where the S-curve rises, approximately at one over b to the power one over r, so you choose the pair that puts the steep part at the similarity above which you consider two documents duplicates. More rows raises the threshold and favors precision; more bands lowers it and favors recall. Plot the actual curve for your candidate settings rather than trusting the approximation, since it is only a guide.

References

The algorithms in this cookbook are established methods from the literature; none of them are ours. The works referenced above, in order of appearance:

• Broder, "On the Resemblance and Containment of Documents" (1997) — MinHash.
• Indyk and Motwani, "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality" (1998) — LSH.
• Leskovec, Rajaraman, and Ullman, "Mining of Massive Datasets" — the band-and-row S-curve analysis.
• Lee et. al, "Deduplicating Training Data Makes Language Models Better" (2021).
• Carlini et. al, "Quantifying Memorization Across Neural Language Models" (2022).
• Kandpal et. al, "Deduplicating Training Data Mitigates Privacy Risks in Language Models" (2022).
• Abbas et. al, "SemDeDup: Data-efficient Learning at Web-scale through Semantic Deduplication" (2023).
• Tirumala et. al, "D4: Improving LLM Pretraining via Document De-Duplication and Diversification" (2023).
• Mirzasoleiman, Bilmes, and Leskovec, "Coresets for Data-efficient Training of Machine Learning Models" (2020).
• Koh and Liang, "Understanding Black-box Predictions via Influence Functions" (2017).
• Pruthi et. al, "Estimating Training Data Influence by Tracing Gradient Descent" (2020).
• Xia et. al, "LESS: Selecting Influential Data for Targeted Instruction Tuning" (2024).