What similarity means as geometry

Every index on this site — graphs, clusters, codebooks — is machinery for one primitive: given a point, find the points near it. Before any of that machinery makes sense, it’s worth being precise about what “near” is doing, because the geometry is not decoration on top of the search. It is the only reason the search can skip anything.

The naive approach

You want to find documents similar to a query. The obvious method is to compare the words.

Count how many terms the query and the document share. Rank by that count, perhaps weighting rare terms more heavily. This is a real and durable technique and it is not to be sneered at — it is exact, cheap, and it explains itself.

How it fails: it has no notion of degree of relatedness between two different words. “Cancel my subscription” and “how do I stop being billed” share almost no terms. The overlap count is near zero, and there is no threshold you can set that fixes this, because the problem isn’t the scoring — it’s that the representation is a set of symbols and sets only support membership. A symbol is either present or absent. Two absent symbols have no relationship at all.

What we want is a representation where “billed” and “subscription” are close to each other, so that a document mentioning one is partially credited for a query mentioning the other. That means we need somewhere for things to be close in. We need a space.

The idea: put meaning in coordinates

Assign every document a list of numbers, and treat that list as coordinates of a point. Do the same for the query. Now “similar” can mean “nearby”, and nearby is a spatial question with spatial answers.

This is the whole move, and it buys three things a symbol set can’t provide.

A degree, not a verdict. Any two points have a distance between them. Every pair of items is comparable, including pairs sharing no vocabulary. There is always an answer to “which of these two is closer”, which is what ranking needs.

A neighbourhood. A point has surroundings. Things near it are related to it, and — this is the part indexes exploit — things near each other are related to each other. Relatedness becomes transitive-ish, which is what lets you reason about regions rather than pairs.

Structure you can precompute. If document A is near document B, that fact is true before any query arrives. A symbol-overlap score can only be computed once you have both sides. A distance relationship among documents exists independently of the query, which means it can be computed once and stored. Every index in this field is some way of storing that.

What the space actually is

The coordinates come from a model, and the model’s job is to place things so that distance corresponds to whatever notion of relatedness it was trained on. Two properties of the result surprise people.

The axes mean nothing individually. There is no dimension for “sports” and no dimension for “sentiment”. Meaning is distributed across all of them, and the space can be rotated arbitrarily without changing any distance — a rotation is exactly the transformation that preserves every pairwise distance. So the information lives in the relative positions, never in a coordinate. Any story you tell about dimension 412 is a story about the model’s arbitrary basis, not about meaning. This is also why an index can apply a rotation to your vectors as a preprocessing step without destroying anything.

The occupied region is much smaller than the box. A 768-dimensional embedding does not fill 768-dimensional space. Real embeddings concentrate on a curved, much lower-dimensional surface inside it — a sheet crumpled up in a very large room. The number of coordinates is the nominal dimensionality; the dimensionality of the sheet is the intrinsic dimensionality, and it is the one that governs how hard the search is. Holding these two apart is the single most useful distinction in this subject, and the curse of dimensionality is mostly a story about the gap between them.

The properties indexes depend on

A distance function that behaves like a distance is called a metric, and the definition is four conditions:

d(a, b) ≥ 0 — distances aren’t negative.
d(a, b) = 0 exactly when a = b — only a point is at zero distance from itself.
d(a, b) = d(b, a) — symmetry.
d(a, c) ≤ d(a, b) + d(b, c) — the triangle inequality.

The first three are housekeeping. The fourth is the load-bearing one, and it is worth seeing why in geometric terms before any algebra: it says there are no shortcuts. Going from a to c via b cannot be shorter than going straight there.

That single property is what makes pruning possible. Suppose you know d(a, b), and you have measured d(query, a). Then without ever computing d(query, b), you know it is at least d(query, a) − d(a, b). If that lower bound already exceeds the worst result in your current top-k, b cannot be an answer, and you can discard it — along with anything else clustered near a at a similar remove. This is the mechanism behind every form of pruning in similarity search. A cluster index skips a whole partition by measuring one centroid and reasoning about everything assigned to it. A graph index stops walking because nothing in the direction it was heading can be closer. Both are triangle-inequality arguments wearing different clothes.

The corollary matters as much: when a similarity function isn’t a metric, that reasoning is unavailable. Raw inner product violates the second and fourth conditions, which is why maximising inner product is not the same problem as nearest neighbour and needs its own treatment.

The primitive operations

Once you have a space, several distinct questions can be asked in it, and they have different costs.

k-nearest neighbours. Return the k closest points to the query. This is the one everything implements, because it always returns exactly k results regardless of how the query is positioned.
Range search. Return every point within radius r. Honest, and unusable in practice: because distances concentrate in high dimensions, an r that returns a handful of results for one query returns thousands for another. This is the deep reason absolute score thresholds don’t transfer.
Approximate k-NN. Return k points that are probably the closest. Cheaper than exact by orders of magnitude, and the entire field is built on it. What “probably” is permitted to mean is worth pinning down.

What the map loses

The geometry is only as good as the placement, and the placement is learned. Three consequences.

Distances are only meaningful within one space. Vectors from two models, or two versions of one model, are two different maps. A distance computed across them is arithmetic without meaning. Nothing errors; the results simply stop corresponding to anything.

Relatedness collapses to one number. Two documents can be similar in topic and opposite in sentiment, or the same event described from two positions. A single scalar cannot express that, so the model must have chosen, during training, which axis of similarity to encode. Queries that ask about a different axis get plausible, wrong neighbours.

Perfect retrieval of a bad map is still bad. An index that returns the exact nearest neighbours of a query, in a space where “nearest” doesn’t track what your users mean, is functioning perfectly and answering the wrong question. This is why recall measures index fidelity and not result quality, and why the two are worth diagnosing separately.

Everything downstream assumes the map is good enough. Given that, the question becomes how to find neighbours in it without measuring every point — which is where the naive answer starts failing for reasons that are entirely geometric.