Anything pairwise is quadratic: distances, attention and deduplication

The shape to recognise

Every time a computation compares each item with every other item, the work is proportional to the square of the item count. It arrives in many disguises: a distance matrix, an attention layer, a deduplication pass, a join without an index, a nested loop over the same list. The disguises differ; the arithmetic does not, and it is the arithmetic that decides when the pipeline stops working.

Pairwise distances

Ten thousand embeddings of dimension 768, and you want every pairwise similarity. That is n²/2 = 5 × 10^7 pairs, each a dot product of 768 multiply-adds:

5 × 10^7 × 768 × 2 ≈ 7.7 × 10^10 FLOPs   → under a second on a laptop
matrix: 10^8 entries × 4 bytes = 400 MB   → fits

Now a million embeddings:

5 × 10^11 pairs × 1536 ≈ 7.7 × 10^14 FLOPs   → about two hours at 10^11 FLOP/s
matrix: 10^12 entries × 4 bytes = 4 TB       → does not fit anywhere you own

A hundredfold more items, ten-thousandfold more work and memory. The FLOPs are survivable with patience; the matrix is not. Whatever you were going to do with all the pairs, you have to do it without materialising them.

Attention

A transformer layer computes, for every token, a score against every other token in the context. For context length L and model width d, the scores and the weighted sum together cost about 4 × L × d FLOPs per token per layer. The layer's ordinary linear parts cost about 24 × d² per token. Set them equal:

4 L d = 24 d²   →   L = 6 d

For d = 4096 the crossover is at about 24,600 tokens. Below that, attention is the smaller cost; at L = 4096 it is a sixth of the linear layers. Above it, attention dominates, and at L = 100,000 it is four times the rest. A model with a long context is a model whose cost per token grows with how much it has already read.

The memory is worse than the FLOPs. The score matrix is L × L per head. At L = 32,768 in half precision that is 32768² × 2 bytes: 2.1 GB, per head, per layer. It never fits. The technique called flash attention exists to compute the softmax and the weighted sum in blocks without ever writing that matrix out, and the reason it was necessary is on this page. The course how-llms-work covers what was built; this is the number that forced it.

Deduplication

A corpus of a million documents, and you want to remove near-duplicates. Comparing every pair is 5 × 10^11 comparisons, each of which reads two documents. At a microsecond per comparison, six days. And the corpora people actually deduplicate are a thousand times larger, which makes it sixteen thousand years.

Nobody does that. The standard replacement hashes each document into a short signature such that similar documents share signature pieces with high probability, then only compares documents that landed in the same bucket. The hashing lesson explains the mechanism; the effect is to turn n² into roughly n log n, and sixteen thousand years into an afternoon.

Four ways out

The pattern is always the same: the cost comes from comparing everything with everything, so stop.

1. Sort, then scan neighbours. Exact duplicates, and anything with a total order, fall out of a sort in n log n.
2. Bucket by a hash. Put items that could match into the same bucket, then compare within buckets. Works when a cheap key predicts a match.
3. Block by structure. Compare only within the same date, the same language, the same customer. The pairs across blocks were never going to match.
4. Accept approximation. For nearest neighbours, the index structures in the lesson on search find the right answer nineteen times in twenty at a ten-thousandth of the cost.

Spotting it in code

for a in items:
    for b in items:          # same collection twice: quadratic
        if similar(a, b): ...

The give-away is the same collection in both loops, or a call like distance_matrix, pairwise, cdist, or a join with no key. None of these is wrong at a thousand items. All of them are wrong at a million, and the code gives no warning between the two.

The one honest quadratic

Sometimes you genuinely need all the pairs, because the answer is about the pairs: a full attention matrix for a short sequence, a correlation matrix among a hundred features, a confusion matrix among fifty classes. The rule is not "never quadratic". It is: know the n, square it, and multiply by the cost of one pair before you run it. If the product is under 10^10, run it. If it is over 10^14, you are choosing among the four ways out, and the only question is which.