Deduplication at Scale With Embeddings

Exact duplicates are a hash join and take an afternoon. Near-duplicates — the same article on two domains, the same answer reworded, the same product with a different SKU — are where embeddings earn their place, and where two specific mistakes turn a working pipeline into a corpus that has been silently mangled.

Decide what duplicate means first

“Duplicate” is not one relation, and the threshold you end up with depends entirely on which one you meant. Write it down before you compute anything:

• Byte-identical. Use SHA-256. No embeddings, no threshold, no ambiguity.
• Near-identical text — whitespace, boilerplate, tracking parameters differing. MinHash or SimHash over shingles is faster, cheaper and more predictable than embeddings here. Reach for embeddings only past this rung.
• Same content, rewritten. A press release and the article derived from it. This is the embedding case.
• Same subject, different content. Two independent reviews of one product. Usually not duplicates, and the threshold that catches the previous case will start catching this one if you set it too low.

The third and fourth categories are adjacent in vector space, which is why the threshold is the entire problem.

Finding candidates without O(n²)

All-pairs is not an option and the arithmetic says so immediately. Ten million documents give n(n-1)/2 ≈ 5 × 10^13 pairs; at 1536 dimensions each pair is 1,536 multiply-adds, so the total is around 7.7 × 10^16 operations. That is not a job you run.

Instead, index once and ask each document for its own neighbours:

build HNSW over all N vectors        (N * ef_construction * M distance ops)
for each document d:
    neighbours = index.search(d, k=20, ef_search=64)
    emit (d, n, sim) for n in neighbours where sim > candidate_floor

query cost: N * ef_search * M = 10e6 * 64 * 16 = 1.0e10 distance ops
vs all-pairs:                                    5.0e13 pair comparisons

Three or four orders of magnitude, and the recall loss does not matter much here: a near-duplicate is by construction a close neighbour, which is precisely the case approximate indexes handle best. Set candidate_floor generously — say 0.75 — because you are about to choose the real threshold from data, and you cannot choose it from pairs you never generated.

Choosing the threshold by labelling

There is no universal number. Cosine scores are not calibrated, and a value that means “the same article” for one model means “vaguely related” for another. But you can find your number in about an hour with 200 labels, if you sample them correctly.

• Stratify by similarity band. Take 25 candidate pairs from each of 0.75–0.80, 0.80–0.85, 0.85–0.90, 0.90–0.92, 0.92–0.94, 0.94–0.96, 0.96–0.98 and 0.98–1.00. Uniform random sampling would put nearly everything in the low bands, where the answer is obvious and uninformative; the decision lives in the narrow bands at the top, which is why they are narrower.
• Label each pair yourself against the definition you wrote down. Duplicate or not. Two hundred judgements is around an hour and it is the only part of this that cannot be automated.
• Compute precision per band — the fraction of pairs in that band you called duplicates. You will typically see something near zero in the low bands, a transition zone, and near-perfect precision at the top.
• Pick the band where precision crosses your tolerance. For deleting data, demand very high precision, because a false positive destroys a document. For flagging into a review queue, a lower threshold and higher recall is correct. The threshold is a product decision that this procedure turns into an informed one.

Keep the labelled pairs. They become the regression test for the next model change, and re-running the precision table is the fastest way to answer “does the new embedding model need a new threshold”. It always does, incidentally: thresholds are a property of a model, not of a corpus, and carrying one across a model change is how a deduplication job that behaved for a year suddenly starts merging unrelated documents.

The transitivity trap

Similarity is not transitive and duplicate-grouping treats it as if it were. Suppose A~B at 0.94 and B~C at 0.94, but A~C at 0.86 — entirely possible, because the two similarities can point in different directions in the space:

threshold 0.90, union-find over pairs above it:
    A-B joined, B-C joined  =>  group {A, B, C}
    but A and C are not duplicates of each other

on a real corpus this chains:
    lower the threshold from 0.94 to 0.88 and a "group" of 12 documents
    can become a component of 40,000 - the corpus has percolated

Connected components over a similarity graph undergo a percolation transition: below some threshold the giant component appears, and one chain of weak links merges half your corpus into a single “duplicate group”. The symptom is a run that produces sensible groups at 0.94 and one absurd group at 0.88, and it is catastrophic if the pipeline deletes all but one member.

Guard it three ways. Cap group size and send anything larger to review rather than resolving it automatically. Prefer a stricter grouping rule than plain connected components — require that every member be above threshold against the group’s representative, not merely against some member. And always log the component-size distribution per run: a maximum component size that jumps from 14 to 9,000 between runs is the alarm, and it is one number.

Running it continuously

The batch job is the easy version. Incrementally, each new document is one index query against the existing corpus before insertion, which is a millisecond and turns deduplication into an ingestion-time check rather than a periodic clean-up. Two details make it survive contact with production: keep the canonical document stable — deleting the older copy and keeping the newer one rewrites ids that other systems hold — and record the pair and score for every merge, so that when someone asks why their document disappeared there is an answer.

One more reason to bother, beyond storage: near-duplicates degrade retrieval. Ten copies of the same page fill your top-10 with one answer, and they fill an HNSW node’s neighbour list with copies of each other, which wastes the graph connectivity the index depends on. Deduplication is a retrieval-quality intervention that happens to save money.