Number Research
← Back to Explore
Information Systems Information Retrieval Approximate Nearest Neighbor Search

The Speed of Not Looking

Vector search scaled to a billion vectors by returning wrong answers on purpose—and running on maps built deliberately wrong.

S.J. Nam 7 min read
The Speed of Not Looking

A billion is a hard number to feel. Stack a billion sheets of paper and the tower runs past 60 miles, well into the thermosphere. In March 2017, Meta's research team announced it had built something stranger than a tall stack: the first k-nearest-neighbor graph across a billion high-dimensional vectors, with search implementations they clocked at roughly 8.5 times faster than the previous state of the art. The library, Faiss, would go on to sit under a large share of the recommendation systems and chatbots you now use daily. And the marketing shorthand for what it does — "search a billion documents in an instant" — gets the achievement almost exactly backwards.

Because the machine's real trick is that it refuses to search a billion documents. It reads a few thousand and skips the rest. The speed you marvel at is the speed of not looking.

The Sleight of Hand Is the Skipping

Start with what the honest version of the task would cost. To find the single closest match to your query among a billion items, the brute-force method compares your query against all billion, one at a time. Do that for every user query, at scale, and you have built a furnace that burns money. So the field made a bargain that sounds like cheating when you say it plainly: it stopped trying to find the right answer.

The technical term is approximate nearest neighbor search, and the word doing the heavy lifting is approximate. These systems deliberately trade exactness for speed. Instead of guaranteeing the closest item, they return items that are probably close, quickly, and they accept that some true matches will slip through. Engineers even have a scorecard for how often the system is wrong on purpose — recall, the fraction of the genuine nearest neighbors that actually turn up in the results. A system tuned to 95 percent recall is one that, by design, misses one in twenty of the things it was supposed to find. Nobody advertises this. It is the load-bearing compromise of the entire enterprise.

Which reframes the question. The interesting engineering was never "how do we look at everything faster?" It was "how do we look at almost nothing and still be right most of the time?"

Six Degrees of a Search Query

The answer that won borrows its intuition from a party trick you already know. You have, say, a few hundred friends, yet you can reach a stranger on another continent through a startlingly short chain of introductions — a friend of a friend of a friend. Networks with that property are called small worlds, and the useful part is that you never need a map of the whole planet to get somewhere far away. You just keep taking the step that lands you closer to the target.

The dominant algorithm for modern vector search, Hierarchical Navigable Small World graphs — HNSW — turns that social-network shortcut into a data structure. Every document becomes a point in a graph, wired to a handful of its neighbors. Search starts at a single entry point in a sparse top layer, where a few long-range links let it leap across the space in giant strides. At each node it looks only at the immediate neighbors, hops to whichever one sits closer to the query, and keeps hopping until it can get no closer. Then it drops to a denser layer and repeats the move at finer resolution, and again, until the bottom layer does a last careful sweep of the local candidates. This greedy walk — always step toward the target, never survey the room — is what lets a query touch a few thousand nodes out of a billion and call it a day.

The scheme, introduced by Yury Malkov and Dmitry Yashunin in work formally published in 2020, now hides inside almost everything: Lucene, Milvus, Qdrant, Chroma, pgvector, Redis. When a benchmark lines up the serious contenders on high-dimensional data, graph methods like HNSW consistently deliver the best speed-for-accuracy trade-off, and they pull further ahead precisely when the problem gets hard — when the data is dense and the dimensions are many. The older families of tricks, the ones based on hashing items into buckets, tend to buckle exactly there.

Why the Perfect Map Gets You Lost

Here is the finding that ought to unsettle anyone who thinks faster search is just a matter of building a cleaner index. You would assume the ideal graph is the correct one — the one where every point is genuinely linked to its true nearest neighbors, no errors, no noise. Build that, and searches should be flawless.

They aren't. Strictly optimizing the graph for quality, so that every edge connects a point to its actual closest companions, does not reliably make search better. What works better is wiring in neighbors that are spatially diversified — deliberately including some links that point off in odd directions rather than only to the nearest cluster. The intuition, once you sit with it, is almost human. A network of people who only know their immediate neighbors is a village with no way out; you can walk forever and never leave the county. It's the occasional weird, long-distance acquaintance — the college roommate now living abroad — that makes the whole world reachable in a few hops. A too-perfect graph is a graph full of dead ends. Controlled imperfection is what keeps it navigable.

So the craft here is double-edged imprecision: a system engineered to return slightly wrong answers, running on a map deliberately built slightly wrong, and the wrongness in both places is the point.

The Bill Comes Due in RAM

None of this is free, and the cost shows up somewhere unglamorous. Those graphs, with their thousands of neighbor links per node, mostly have to live in memory to move at conversational speed, which is why running vector search at real scale turns into a fight over RAM, over the drift that creeps in every time you upgrade the embedding model and have to rebuild the whole index, and over how much recall you're willing to sacrifice to keep the latency low. The demo is instant. The infrastructure behind it is a standing argument about trade-offs that never fully resolves.

That argument is the reason your chatbot can pull a relevant passage out of a corporate archive before you finish reading its first sentence, and also the reason it sometimes returns something almost-but-not-quite on point. Retrieval-augmented systems lean on vector search to fetch grounding facts and cut down on invention, and they inherit its bargain wholesale. The confident answer and the occasional near-miss come from the same design decision.

We tell ourselves a story about artificial intelligence reading everything, tirelessly, at superhuman speed. The truth underneath the vector index is more modest and more interesting. The machines got fast not by reading more than we can, but by learning, better than we ever have, what they were safe to ignore.

References