Embeddings, and why exact indexes fail

Why is an embedding model a schema, and why do trees fail in high dimensions while ANN works?

Embedding storage and normalization

Three metrics, one ranking

Three similarity measures circulate: cosine similarity, dot product and Euclidean distance. They are not three real choices. If vectors are unit-normalized (each scaled to length 1), then:

• cosine equals the dot product;
• ‖a−b‖² = 2 − 2(a·b), which decreases as the dot product increases.

Check: for unit vectors, ‖a−b‖² = ‖a‖² + ‖b‖² − 2(a·b) = 1 + 1 − 2(a·b).

So all three induce the same ranking. Normalize once at write time and the metric question dissolves.

Skipping normalization is worse than it looks

Un-normalized dot product is not a metric: it fails the triangle inequality (the rule that the distance from A to C is never more than the distance A to B plus B to C). Every classical geometric pruning argument, "the nearest point in this region is at least x away, therefore skip the region", is a triangle-inequality argument. Maximum inner product search (MIPS) is therefore structurally harder than metric search, not merely differently tuned. The standard remedy is a transformation that converts it back into a metric problem.

This is a small instance of a general rule: the algebraic properties of your comparison function decide which optimizations exist.

An embedding model is a schema

Normalization is also early binding, and of a heavier kind than it looks. The index is built for one metric, at one dimensionality, under one embedding model. All three are frozen into the structure. Change the model and every stored vector is meaningless, not degraded: the coordinate system itself has changed. (This is Amara's third problem. Diego's new model puts "similar" things in different places than the old one.)

There is no such thing as a backward-compatible embedding model. There is no migration path short of re-embedding and rebuilding the entire corpus. The only escape people actually use is a dual-write window: build the new index alongside the old, write to both, then cut over. The price is double storage and double write cost for the duration. Until the cut-over is complete, the failure is silent: a query embedded by the new model against vectors from the old one returns worse results, never an error. So the vectors and the model version must be tracked together, as one definition.

Storage sizing

768 dims × 4 bytes ≈ 3 KB per vector. A billion vectors is about 3 TB of raw float32, before any index structure.

• Half precision (float16) halves it.
• int8 quarters it.
• Product quantization takes it to tens of bytes.

The jump from "fits in one machine's RAM" to "does not" is the single largest discontinuity in this family's cost model, and quantization exists primarily to postpone it.

One line: normalize once and the three metrics collapse into one; the embedding model is a schema whose version bump rewrites the world.

---

Why exact indexes fail, stated correctly

The usual explanation is distance concentration: in high dimensions the ratio of farthest to nearest distance approaches one, so "nearest" becomes meaningless. That result is real, but it is proven for uniformly random points, and real embeddings are not uniformly random: they lie near low-dimensional manifolds. Quoting concentration as the reason ANN is necessary is imprecise, and it also proves too much, since it would imply ANN cannot work either.

The cleaner, combinatorial argument

A KD-tree (a tree that splits the space on one dimension per level) must cut every dimension at least once to separate neighbourhoods. In 768 dimensions that needs 768 levels. But a balanced tree over 10 million points has only about 23 levels (since 2²³ ≈ 8.4 million, and 2²⁴ ≈ 16.8 million). You run out of points before you run out of dimensions.

The partition therefore never isolates a neighbourhood, and a range query must visit nearly every leaf. Space-partitioning trees degrade to a full scan well below a hundred dimensions. This is the same underlying impossibility as linearizing space (no total order preserves proximity in more than one dimension), now expressed as: no bounded-depth partition separates proximity in high dimensions either.

ANN works when the data is lower-dimensional than it looks

The honest synthesis: ANN works to the degree that the data's intrinsic dimension is low. That is an empirical property of your embeddings, not a guarantee of the algorithm. The structure assumes something about the data distribution that it cannot verify, and when the assumption fails, recall degrades silently rather than erroring.

Two layers of approximation

One peculiarity separates this family from text. Recall against brute force is exactly measurable. You can compute the true top-k offline and score the index. So vector search has a rigorous, quantitative tuning surface that text relevance does not. The artefact you actually tune against is the recall-versus-QPS curve; without it, none of the knobs below has meaning.

But the exact top-k is itself only a proxy for "semantically relevant". So there are two layers of approximation stacked, one measurable and one not. Conflating them produces bad engineering: teams tune recall from 95% to 99% at triple the cost, while the underlying embedding makes far larger errors invisibly.

One line: trees fail because depth is logarithmic while dimensions are not; ANN works because real embeddings are lower-dimensional than they look, which is a property of your data, not a promise.