An all-pairs comparison is quadratic, so the candidate set comes from a self-join

Finding near-duplicates in a corpus means deciding, for some set of pairs of passages, whether the two members of each pair say the same thing. The definition contains a quantity nobody usually looks at, which is the set of pairs, and the obvious value for it is all of them. That value is not available, and the whole of this chapter is a consequence of that one fact. Candidate generation is the name for the step that proposes a manageable set of plausible pairs instead, and everything downstream — a threshold, a policy, an evaluation — operates only on what this step proposed.

Two instruments do the proposing. An exact hash turns a passage into a fixed-length fingerprint such that identical text produces identical fingerprints, which lets copies be grouped by a lookup rather than by a comparison. An approximate nearest neighbour index, ANN for short, stores vectors in a structure that can be navigated towards a query's neighbourhood without scanning every vector, at the price of a small chance of missing a true neighbour. Neither instrument compares everything to everything, and that is what they are for.

The quadratic term is survivable exactly once#

Start with the count. Every unordered pair drawn from n items is n(n−1)/2 in total: each of the n items can be paired with the other n−1, which counts every pair twice, once from each end, so the product is halved. At n = 4.2M that is 8.8 trillion pairs.

Turn each pair into work. Comparing two vectors that have been scaled to unit length is a dot product — one multiply and one add for every dimension — so a 768-dimensional comparison is 1,536 floating-point operations, twice the dimension count. Multiplying the pair count by the operations per pair gives about 1.35 × 10^16 FLOPs for the whole job.

That number is not obviously impossible, which is what makes the trap worth walking through. Dense matrix multiplication is the operation hardware is best at. Assuming a well-tuned BLAS — the basic linear algebra subprograms, the tuned matrix kernels NumPy and every framework call down into — on a 16-core server sustaining about 200 GFLOP/s, and an A100 sustaining a conservative 12 TFLOP/s in fp32 on this shape, the job costs:

Every row of that table is the same three operations, and working the smallest row in full is enough to have the rest. A hundred thousand chunks give about five billion pairs, since halving the square of a hundred thousand is five billion. Five billion pairs at 1,536 operations each is 7.7 × 10^12 FLOPs. Dividing that by 200 GFLOP/s gives 38 seconds, and dividing the same figure by 12 TFLOP/s gives 0.6 seconds. Nothing changes in the other three rows except the first column.

The relationship between the two time columns is worth naming, because it makes the table easier to hold and easier to distrust. The assumed GPU throughput is sixty times the assumed CPU throughput, so the GPU column is the CPU column with its unit stepped down one notch on a clock face. Sixty-four minutes becomes sixty-four seconds. Eighteen point eight hours becomes eighteen point eight minutes, printed as nineteen. Seventy-eight days becomes a little over a day, printed as thirty-two hours. Four rows and one division, which means the shape of that column is a statement about the hardware ratio assumed rather than about the corpus.

The shape of the first two columns is the argument. Between rows the chunk count rises by one order of magnitude and the pair count rises by two, because halving the square of a tenfold larger number is a hundredfold larger result. That gap between the two columns is the entire problem, and it is invisible if the table is read as a list of levels rather than as a set of steps.

Nineteen GPU-minutes for a corpus of four million chunks looks affordable, and that is the trap. Growing the corpus by 10× multiplies the work by 100×, so the connector that adds a customer's Slack export takes the job from a coffee break to a day and a half. The cost also has to be paid again on every ingest, because a new chunk has to be compared against everything already there, and it has to be paid a third time whenever the embedding model changes and every vector is recomputed.

The compute is not even the binding constraint. The output is. Every one of those 8.8 trillion comparisons produces a float32 score, and four bytes apiece comes to 35 TB, so the thresholding has to be fused into the inner loop rather than applied to a materialised result. If the threshold is loose the surviving pairs still overwhelm anything you write them to — 340 million pairs from 11% of the corpus, on the way to roughly three billion. Any workable pipeline replaces the exhaustive comparison with a candidate generation step whose job is to propose a manageable set of plausible pairs, and accepts that this step, not the threshold, is what decides which duplicates exist as far as the rest of the system is concerned.

Byte-identical copies cost nothing to find#

Before any of that, there is a pass that is linear in the corpus and finds a large fraction of the problem for free. Two chunks whose normalised text is byte-identical do not need a vector comparison; they need a hash table.

import hashlib, re, unicodedata

_WS = re.compile(r"\s+")

def exact_key(text: str) -> str:
    # NFKC folds width and ligature variants; whitespace collapse
    # absorbs the newline and indentation damage that exporters do.
    t = unicodedata.normalize("NFKC", text)
    t = _WS.sub(" ", t).strip()
    return hashlib.sha256(t.encode("utf-8")).hexdigest()

buckets: dict[str, list[str]] = {}
for chunk_id, text in iter_corpus():          # streams from the store
    buckets.setdefault(exact_key(text), []).append(chunk_id)

exact_clusters = [ids for ids in buckets.values() if len(ids) > 1]

The reason this is linear rather than quadratic is the hash table, and it is worth being explicit about why a lookup replaces a comparison. Two identical strings produce the same key, so every copy of a passage lands in the same bucket without any copy ever being compared to any other. Each chunk is touched once, the work is proportional to the number of chunks, and the pairs fall out of the grouping rather than being searched for.

On a payments corpus of 4.2M chunks this took 4 minutes over 8.4 GB of text, dominated by reading rather than by SHA-256, and it grouped 470,000 chunks — 11.2% of the index — into 148,000 exact clusters. The largest single cluster held 610 copies of a legal disclaimer that appeared at the foot of every exported PDF.

Choosing what to normalise before hashing is where this pass earns or loses its value. Collapsing whitespace and applying NFKC is safe and catches the export artefacts. Lowercasing is usually safe for prose and destructive for code and identifiers. Stripping punctuation catches a few more mirrors and starts merging things that differ meaningfully, which defeats the point of having a cheap pass whose results you trust without review. Keep it conservative: this pass exists to be free and certain, and everything ambiguous belongs to the embedding stage.

Running it first also shrinks the input to the expensive stage. Reducing 4.2M chunks to 3.73M representatives cuts the pair count by 21%, because the quadratic term rewards even modest reductions.

Two figures in that sentence look as though one of them must be wrong, and neither is. The number leaving the expensive stage is the full 470,000 rather than 470,000 less one representative per cluster, and the diagram at the end of this chapter is what settles it: a chunk that matched exactly is routed straight to the clustering step and never enters the embed-and-search path at all. Nothing about its cluster needs to be rediscovered by a vector search, so all 470,000 leave. The second figure then follows from the first. Removing 11.2% of the chunks removes about 21% of the pairs, because pairs go as roughly the square of the count and a small proportional reduction is therefore roughly doubled when it is squared.

Asking the index for its own neighbours#

Everything the hash misses — the paraphrases, the exports with a changed footer, the forked runbook with two edited paragraphs — needs vector comparison, and the vector index already answers the question "what is near this?" in sublinear time. That index is an approximate nearest neighbour index, where approximate means it navigates a structure built over the vectors instead of scanning them all and accepts a small chance of missing a true neighbour in exchange. A self-join, in the database sense of joining a table to itself, is that question asked once per vector with the vector's own row excluded.

import faiss, numpy as np

X = load_embeddings()   # (n, 768) float32, L2-normalised → inner product is cosine

index = faiss.IndexHNSWFlat(768, 32, faiss.METRIC_INNER_PRODUCT)
index.hnsw.efConstruction = 200
index.add(X)
index.hnsw.efSearch = 128

M, FLOOR = 50, 0.85
pairs: list[tuple[int, int, float]] = []

for lo in range(0, len(X), 8192):
    hi = min(lo + 8192, len(X))
    scores, ids = index.search(X[lo:hi], M + 1)      # +1 for self
    for row, (srow, irow) in enumerate(zip(scores, ids)):
        i = lo + row
        for score, j in zip(srow, irow):
            if j != i and j >= 0 and score >= FLOOR:
                pairs.append((min(i, j), max(i, j), float(score)))

pairs = sorted(set(pairs))

The cost is n index queries rather than n² dot products, and it is linear in n rather than quadratic. HNSW — a hierarchical navigable small-world graph, the layered neighbour graph most vector stores use as their default index, whose efSearch parameter sets how many candidates a query keeps alive as it walks that graph — at efSearch=128 on this index answers a single query in about 1.2 ms; across 16 threads, 3.73M queries take 4.7 minutes. At 42M chunks it takes 47 minutes rather than 32 GPU-hours, which is the difference that matters — the self-join scales with the corpus instead of with its square.

Those two wall-clock figures are one multiplication and one division, and they are worth doing because they show what linearity buys. Three point seven three million queries at 1.2 ms each is a little over an hour of single-threaded work, and dividing that across sixteen threads leaves the 4.7 minutes quoted. Ten times as many chunks is ten times as many queries and therefore ten times the wall clock, which is the 47 minutes, where the exhaustive comparison over the same growth took a hundred times longer.

The same thing is expressible in SQL if the vectors live in Postgres, with a lateral join standing in for the loop:

SELECT c.chunk_id AS a, n.chunk_id AS b, 1 - (c.embedding <=> n.embedding) AS cosine
FROM chunks c
CROSS JOIN LATERAL (
  SELECT chunk_id, embedding
  FROM chunks n
  WHERE n.chunk_id <> c.chunk_id
  ORDER BY n.embedding <=> c.embedding      -- index-backed
  LIMIT 50
) n
WHERE 1 - (c.embedding <=> n.embedding) >= 0.85;

Two parameters control everything the self-join produces. The neighbour count m caps how many partners a chunk can have, so a document with 200 copies will have its cluster reconstructed transitively rather than directly — copy 1 finds 50 of them, each of those finds 50, and the union-find pass that follows — the standard algorithm for turning a list of pairwise links into groups, by walking the pairs and merging the two groups each link touches — stitches the component together. The floor is deliberately loose, well below any threshold you would actually merge at, because its job is to keep the candidate file small enough to store and to label, not to decide anything. At 0.85 the payments corpus produced 61 million candidate pairs, about 1.4 GB as Parquet.

Being linear also makes the job incremental in a way all-pairs never is. A daily ingest of 40,000 new chunks needs 40,000 queries against the existing index rather than a comparison against the whole corpus, which takes about 50 seconds and can run as part of the ingest itself. The new chunks find their duplicates among the old ones and among each other, and the union-find structure is extended rather than rebuilt. This changes what deduplication is operationally: a batch job that has to be scheduled, watched and re-run becomes a step in the pipeline that has already happened by the time anyone queries the new documents. The only work that still needs a full pass is a change to the embedding model, which invalidates every vector and therefore every pair.

Clustering is the other standard route to candidates, and it is the one the SemDeDup paper popularised: run k-means over the corpus, which partitions the vectors into a chosen number of groups around learned centre points called centroids, then compare pairs only within each cluster. With 4.2M vectors and 50,000 centroids the assignment pass is 4.2M × 50,000 distance computations, and the within-cluster comparisons are 50,000 × (84)²/2 ≈ 176M pairs, which is four orders of magnitude below all-pairs. It has the same character as the ANN self-join and the same weakness in a sharper form, since a duplicate pair split across two cluster boundaries is never compared at all.

Blocking is the pre-vector version of the same idea and it is worth keeping in the toolkit for corpora with strong structure. Group chunks by a cheap key — the first 64 tokens hashed, the document title's trigram signature, the byte length rounded to the nearest 5% — and compare only within groups. It is nearly free, it catches export-style duplicates well, and it fails on exactly the cases embeddings are for, since a translated or heavily paraphrased copy shares no cheap key with its original.

Whatever the self-join misses does not exist#

The property that matters most about this stage is not its speed. Approximate nearest neighbour search is approximate, and a genuine duplicate pair the search never returns is not merely unmerged — it is absent from the candidate file, absent from the labelled sample drawn from that file, absent from the false-miss rate computed against those labels, and absent from every report anyone reads. The pipeline cannot know it exists.

That is the shape of a defence that carries no information about the thing it is supposed to guard. A false-miss rate is meant to tell you how much duplication is being left behind, and it reads the same whether the search returned nearly every true pair or a fraction of them, because the pairs it did not return are not in the population the rate is computed over. Believing the threshold is what decides which duplicates get found is the tempting version of this mistake, and it is tempting because the threshold is the number a person chooses. The search chose first, and it chose silently.

That makes the self-join's recall a hard ceiling on the whole system, and it is measurable. Take a random 200,000-chunk subset, where exhaustive comparison costs about 3 GPU-minutes, compute the true set of pairs above cosine 0.90, then run the self-join over the same subset and see what fraction it returns:

Pair recall runs higher than the per-query recall of the same index, and the reason is that a pair has two chances rather than one. It survives if either member retrieves the other, so the search has to fail from both ends for the pair to be lost, which makes the pair-level miss rate roughly the square of the per-query miss rate. Squaring a number below one makes it smaller, which is why the column reads high, and squaring never reaches zero, which is why there is no configuration in the table at 1.0. At efSearch=128 roughly 4% of true near-duplicate pairs in the corpus are structurally invisible. That is an acceptable number as long as it is written down and quoted next to every later figure, which chapter 4 does explicitly when it comes to reporting false-miss rates.

The table is more useful read as steps than as levels. Moving from the first row to the second buys about seven points of pair recall for thirty-seven extra seconds; the second to the third buys two points for sixty-three seconds; the third to the fourth buys under three points for a hundred and sixty. The return per second of search falls at every step, which is the ordinary shape of an approximate index being pushed towards exactness. The candidate-pairs column tells a second story: it barely moves between the middle two rows while recall does move, so the size of the candidate file is not a proxy for how much of the truth is in it, and a pipeline tuned by watching that column would have stopped one row too early.

The whole sequence, from raw corpus to candidate file, is short:

Where shingles beat vectors#

Embeddings are not the only instrument for this, and on some corpora they are the wrong one. MinHash over token shingles — shingles being the overlapping runs of a few consecutive words a document is cut into, and MinHash a compact sketch of that set — estimates the Jaccard overlap between two documents, which is the fraction of the shingles they have in common out of all the shingles either one carries, and it finds lexical near-duplicates without a single GPU forward pass. The BigCode team's account of deduplicating their training corpus is the useful reference here: on source code, where copies differ by a renamed variable or an added licence header rather than by rephrasing, MinHash LSH — locality-sensitive hashing, which buckets sketches so that similar ones collide and only colliding pairs are ever compared — found duplicates at a fraction of the cost, streamed on CPU, and did not require embedding tens of millions of files first.

The trade is legible. MinHash measures shared tokens, so it is blind to a passage rewritten in different words and completely blind to a translation of the same policy into German. Embeddings measure meaning, so they find both, at the price of a full inference pass over the corpus — 3.73M chunks at 2,000 chunks/s on a single A10 is 31 minutes before the self-join even starts — and at the price of a similarity score whose meaning depends on the model, which is the subject of chapter 4. On prose knowledge bases, where the copies came from humans pasting and tools exporting, embeddings win on recall and the inference cost is one-off. On code and on log-like data, MinHash is often both cheaper and more accurate.

The choice between them is not settled by which is more accurate in general, because the two instruments are answering different questions. One asks whether two passages share tokens and the other asks whether they share meaning, and which question is the right one is a fact about how your copies were made. A corpus whose duplicates came from exports and pastes has copies that share nearly all their tokens, so the cheap question is nearly as good as the expensive one. A corpus whose duplicates came from people rewriting the same policy for a different audience has copies that share almost none, and there the cheap question returns nothing.

The self-join over the payments corpus returned 61 million candidate pairs, of which 41,000 scored above 0.97. That is a small enough number to look at, and looking at it is where the trouble starts, because a sample of fifty of those pairs contained forty-four that no one would want merged and that no threshold could have excluded. The next chapter is about those two families of false positive, both of which come from the structure of the corpus rather than from the arithmetic.