A map is worth the questions you can ask it
There are about four questions anyone ever asks an embedding space: what is near this?, what is near all of these at once?, what groups are in here?, and has this moved since last time? This chapter works all four by hand.
There is a fifth question nobody thinks to ask, and it is the one the chapter ends on. When a search system says it found the nearest match, how do you know it looked? In production it almost certainly did not look at everything, and the fraction it missed is a number somebody chose.
Nearest neighbors
A new word arrives. Counted in the same ten sentences from Chapter 5, cocoa appears twice near drink, twice near hot, once near feed, never near walk. The two hand-summed axes turn that into a position the same way they did for every other word:
cocoa $= [2, 2, 1, 0] \rightarrow [4, 1]$.
Now ask the map what cocoa is like. Nearest-neighbor search is what it sounds like: score every word against the query and sort. The score is Chapter 2's cosine, which compares headings and ignores lengths.
$$\cos(\mathbf{q},\, \mathbf{v}_w) = \frac{\mathbf{q} \cdot \mathbf{v}_w}{\|\mathbf{q}\|\,\|\mathbf{v}_w\|}$$In words: the cosine between the query $\mathbf{q}$ and a word's position $\mathbf{v}_w$ is their dot product divided by both of their lengths. Dividing by the lengths is what throws the lengths away, so what comes back is a statement about direction alone.
Worked example: cocoa against milk
cocoa sits at $[4, 1]$ and milk sits at $[3, 1]$. The dot product is $4 \times 3 + 1 \times 1 = 13$. The lengths are $\sqrt{4^2 + 1^2} = \sqrt{17} \approx 4.123$ and $\sqrt{3^2 + 1^2} = \sqrt{10} \approx 3.162$, which multiply to $13.038$. So the cosine is $13 \div 13.038 = 0.997$.
Six times over, the whole map ranks itself: milk 0.997, then tea 0.970 and coffee 0.970, then cat 0.471, horse 0.428, dog 0.399.
In words: cocoa's nearest neighbor is milk, at 0.997. The gap between the drinks and the animals is wide, which is the map telling us it learned the one distinction the ten sentences contained.
The tie, and what it costs
Look again at those two middle numbers. Tea scores 0.970 against cocoa and so does coffee, and that is not a rounding coincidence. The two values are equal to every decimal place. Ask this map for cocoa's second-nearest word and it cannot tell you.
The reason is visible on the picture. Tea sits at $[6, 0]$ and coffee at $[5, 0]$: the same ray out of the origin, same heading, different lengths. Cosine deletes length, so any question asked with a cosine sees one direction where there are two words. Their cosine to each other is 1.000, the number Chapter 5 warned us about.
Now go back to the counts, where nothing has been summed away. Tea was counted $[3, 3, 0, 0]$ and coffee $[3, 2, 0, 0]$; cocoa was $[2, 2, 1, 0]$. In those four dimensions cocoa scores 0.943 against tea and 0.925 against coffee. The tie is gone, and it was never real. The two additions we did to make the map drawable manufactured it.
This is Chapter 4's rule with a name attached. A projection can only lose information, and what it loses here is the ability to tell apart directions it flattened together. When a ranking hands you a tie, the question to ask is how many dimensions ago those two items stopped being different.
Centroids: one position that stands for many
The second question is what is near all of these at once? Average the positions and search from the average. That average has a name.
$$\mathbf{c} = \frac{1}{k}\sum_{i=1}^{k} \mathbf{v}_i$$In words: the centroid $\mathbf{c}$ of $k$ positions is their sum divided by $k$. Add the first coordinates and divide by how many you added, do the same for the second, and that is the whole operation.
Take our three drinks. Across: $(6 + 5 + 3) \div 3 = 4.667$. Up: $(0 + 0 + 1) \div 3 = 0.333$. Use that centroid as a query and the map answers tea 0.997, coffee 0.997, milk 0.969, then cat 0.311, horse 0.265, dog 0.234. It behaves like a word meaning "drink," which no word in our vocabulary means: a query for a category we never had a label for.
Now the limit, and it is a sharp one. Average two drinks and two animals, tea, coffee, dog and horse, and you get $[3.250, 2.750]$, a point in a gap where the map has nothing. Its nearest member is 3.182 away and the set it summarizes spans 7.810. The arithmetic never complained. A centroid is always defined, and it describes something real only when the set it came from is one lump rather than two.
Clusters: letting the map group itself
If a centroid of a two-lump set is a lie, the repair is to find the lumps first. k-means clustering does it in a loop. Pick how many groups you want and drop that many centers anywhere. Then assign every point to its nearest center, move every center to the centroid of the points that chose it, and repeat until nothing changes. Each half of that loop is an operation we already did by hand.
Press Step twice and watch the two centers slide into the drinks and the animals. Then set the clusters to four and watch a group that was never in two pieces get split. Nothing in the method can tell you four was wrong, because nothing in it knows what a cat is. The number is an input, and the clusters are named by you afterward. The AI/ML book works through choosing it in The Classical Toolbox.
Drift: the same word at two different times
The fourth question is about time. Re-count a corpus a year later, or retrain the model, and every word moves. Embedding drift is that movement, measured the only way we have: the cosine between the old position and the new one.
Re-count after a year in which nobody fed cocoa to anything but people still drank it hot. Its counts go from $[2, 2, 1, 0]$ to $[2, 2, 0, 0]$, its position moves from $[4, 1]$ to $[4, 0]$, and the cosine between old and new is $16 \div (4.123 \times 4) = 0.970$. The word did not change meaning. Its company changed and the position followed, because the position was only ever a summary of the company.
Positions move when the text moves, and again when the training moves. A different run, even a different random seed, produces a different space. Two versions of a model share no axes, so a coordinate stored last year cannot be compared to a fresh one. It has to be re-embedded, all of it.
| Question | Operation | What it returns | Where it lies |
|---|---|---|---|
| What is like this? | Rank every item by cosine to the query | An ordered list with scores | Ranks counted company, not meaning; a tie means the projection merged two directions |
| What is like all of these? | Average the positions, rank by cosine to the average | One query standing for a set | Always defined, even when the set has two lumps and the average describes nothing |
| What groups are in here? | k-means: assign, move the centers, repeat | Exactly as many groups as you asked for | You chose the number, and the groups arrive unnamed |
| Has this moved? | Cosine between the old position and the new | One number per item per version | Comparable within one space only; two models share no axes |
Why exact search dies
Everything above assumed we score every candidate. On six words that is free. Price it at a realistic size: a million passages, each embedded in 384 dimensions, which is what a small self-hosted model produces today.
$$\text{multiply-adds per query} = N \times d = 1{,}000{,}000 \times 384 = 384{,}000{,}000$$In words: scoring one query against $N$ stored items of $d$ dimensions each takes $N$ times $d$ multiply-and-add operations, which for a million items at 384 dimensions is 384 million pieces of arithmetic, for one query, before anything is sorted.
A processor does that in a fraction of a second, so at a million items exact search is merely expensive. At a hundred million, with a thousand queries a second, it is impossible, and no amount of better code fixes a number that grows with the product of two things you do not control.
There is a deeper problem underneath the cost, and we met it in Chapter 3. That result is about Euclidean distance between random points in many dimensions: as dimensions pile up, the gap between the nearest point and a far-down-the-list point shrinks as a share of the typical distance. At 384 dimensions the guaranteed true top one is often barely further from the query than the fiftieth answer, so you are paying full price for a distinction that is already smeared. Two caveats apply. It is a statement about distance rather than cosine, and the two rank differently once lengths vary. And it says nothing about six words in two dimensions: milk at 0.997 and dog at 0.399 are miles apart, because concentration is a high-dimensional effect and we are nowhere near high dimensions here.
Highways through the data
The fix is to stop looking at everything, which means giving up the guarantee. An approximate nearest neighbor index answers "what is near this?" without scoring every candidate, and the most common family today builds a layered graph, the structure Malkov and Yashunin published in 2016 and everyone now calls HNSW.
The idea is a road network. Every item is a node in a bottom-layer graph wired to a handful of its nearest neighbors. Above it sits a sparser layer holding a random sample, wired the same way, and above that, sparser still. A search enters at the top and walks greedily toward the query, always stepping to whichever neighbor is closer, and when no neighbor improves it drops a layer and carries on with finer roads. The top layer is a map of the map.
What you buy is speed. What you spend is recall, the share of the genuinely nearest items the index hands back. Recall is a dial rather than a property of the algorithm. Probe more of the structure and recall climbs while queries slow down.
See it move
Where you'll meet this
What you now know
- Nearest-neighbor search is one cosine per candidate and a sort: cocoa at $[4, 1]$ scores 0.997 against milk and under 0.5 against every animal.
- A tie in a ranking is usually evidence that a projection flattened two directions into one: tea and coffee both score 0.970 against cocoa on the drawn map, and 0.943 and 0.925 in the counts.
- A centroid is the average of a set of positions and is always defined, so it will hand you a point in empty space when the set has two lumps instead of one.
- k-means finds exactly as many groups as you ask for and leaves them unnamed, so the number of clusters is a claim you made rather than a discovery.
- Exact search costs items times dimensions per query, 384 million multiply-adds for a million short passages, and in high dimensions the distance guarantee you are buying is worth less than it sounds.
- Approximate indexes walk a layered graph instead of scanning, and what they trade away is recall: the share of true neighbors returned, which is a measurable setting someone chose.
Where we're headed
Six words were enough to show every operation and every failure, and few enough to check by hand. But a six-word map cannot surprise you, and a map that cannot surprise you cannot teach you what a real one feels like. The next chapter loads ten thousand real embeddings into your browser and lets you walk them: look up an article you know, read its ten nearest neighbors, find the one that is near for a reason nobody intended, and watch this part's caveats print themselves live on the same plot.