Embedding targeting is usually explained as comparing two vectors. The step before that, picking which vectors to compare against at all, is where most of the work sits.
Last post: you cannot put vectors in order, and you cannot rule out a group without looking inside it. So whatever makes this fast has to be built before any request arrives. There are thirty years of methods for doing that. Trees, which cut the space into smaller and smaller boxes, stopped working above about ten numbers per vector. Hashing, which sorts vectors into buckets using random cuts, needs too many buckets to get accurate. Grouping, which clusters everything and opens only the nearest few clusters, survives underneath the others. And one approach won outright, a graph of neighbours called HNSW, for hierarchical navigable small world. Of the ready-made databases sold for storing and searching vectors, Qdrant offers nothing else at all, and Weaviate makes it the default.
It works like walking downhill in fog. You cannot see the valley, but from where you stand you can feel which way the ground drops, so you step that way and check again. You stop when every direction goes up. The structure is exactly that. Every vector gets a list of about sixteen of its nearest neighbours, stored right beside it, and that list is all it can see from where it stands. A request drops in somewhere, checks those neighbours, moves to whichever one sits closer to what it is looking for, and does the same again from there, until none of them is closer than where it already is. Then it stops. A few hundred steps out of a million, and everything it never walked past is never seen.
There is one shortcut on top of that. The map comes in layers: a sparse top layer where the few points sit far apart and every hop covers a lot of ground, then denser layers below with shorter hops. A request crosses the rough map first to get into the right region, then drops down and refines. Flights, then trains, then walking.
What goes wrong comes out of the same picture. You can end up at the bottom of a small dip with the ground rising in every direction, while the real valley sits over the ridge you never crossed. The fix is to walk several routes at once instead of one, and how many is a configurable number. Walk more of them and you land in the real valley more often, and it takes longer. None of this is free. Those sixteen links per vector get stored alongside them, so the structure takes up more room than the data it was built from, and assembling it for a million takes time. You are buying query time with space, paid once in advance, and in bidding query time is the one thing you cannot get more of.
That trade is what makes matching by meaning possible inside an auction at all. A bid response has about a hundred milliseconds. Comparing one vector against every stored one does not fit inside that but walking to a few hundred of them does.
