The Needle in a Billion Haystacks: Approximate Nearest Neighbor Search, HNSW, and the Architecture of Vector Databases

The Hook: The Question No Database Index Can Answer

Imagine that what you type into a search box is no longer a keyword but a meaning. You are not asking for "documents that contain the word notice period" but for "passages that mean roughly the same thing as this paragraph here." This is exactly what modern AI systems do all the time: they turn texts, images, faces, molecules, or pieces of music into long sequences of numbers—vectors with hundreds or thousands of dimensions—and claim that proximity in that numeric space corresponds to similarity in meaning. A language model embeds the sentence "How do I cancel my contract?" as a point; the matching answer in the manual lies nearby.

This shifts the very nature of search. The question is no longer "Where is this exact value stored?" but rather: "Which of the billion stored points lie closest to this query point?" That is the nearest neighbor problem, and it is the silent infrastructure behind semantic search, recommendation systems, face recognition, plagiarism detection, and—since the boom of large language models—behind Retrieval-Augmented Generation (RAG), the technique by which a chatbot first fetches the relevant snippets of knowledge from a database before it answers.

The catch: the obvious solution—simply compare the query point with every stored point and take the closest ones—is hopelessly slow for billions of high-dimensional vectors. And the classic tricks of computer science, with which we organize one- or two-dimensional data into trees, fail in high dimensions in a downright uncanny way. This article tells how a surprising detour through the sociology of the 1960s—the famous "six degrees of separation" experiment—led to a data structure called HNSW that today sits inside almost every vector database in the world and cracks the problem in logarithmic time.

Part 1: The Problem—and Why It Turns Vicious in High Dimensions

What "Nearest Neighbor" Precisely Means

Formally, the task is simple. Given a set of N points in a d-dimensional space and a query point q, find the one point (or the k points) closest to q under some distance measure. In practice the distance measure is usually the Euclidean distance (L2), the inner product, or the cosine similarity—the latter measures the angle between two vectors and ignores their length, which is the usual choice for normalized text embeddings.

The brute-force solution, the linear scan, computes the distance to every single point. It is mathematically exact and perfectly fine for a few thousand points. But the cost grows linearly with N and linearly with d: for a billion vectors of 768 dimensions each, a single query means a billion distance computations over 768 numbers apiece. At web scale, with thousands of queries per second, that is economically hopeless.

The Curse of Dimensionality

The classic algorithmic escape route is: build a search tree. In two or three dimensions this works brilliantly. A k-d tree subdivides space recursively along the axes, an R-tree or SR-tree groups points into nested rectangles, and a search need only visit a small part of the tree. Spatial databases and mapping services live on this.

But the higher the dimension, the more thoroughly this idea breaks down—a phenomenon that Richard Bellman christened the curse of dimensionality. The heart of the problem is geometrically counterintuitive: in very high-dimensional spaces the distances between an arbitrary query point and all other points crowd ever closer together. The nearest and the farthest neighbor barely differ in their distance. As a result, the notion of "nearest neighbor" loses its discriminating power, and—worse for the tree methods—the pruning rules no longer bite: a search tree can no longer exclude branches in good conscience, because almost every branch might harbor a candidate that is similarly close.

The result is well documented empirically and sobering: from roughly ten to twenty dimensions onward, exact tree-based methods barely beat the plain linear scan—often they are even slower, because they visit nearly all nodes while still carrying management overhead. There is, moreover, theoretical evidence that exact nearest-neighbor search in high dimensions carries the curse at a fundamental level: all known exact algorithms degrade exponentially with dimension. Text embeddings typically have 384, 768, 1536, or more dimensions. Exact is not affordable here.

The Way Out: Approximation

The saving insight is pragmatic. In the vast majority of applications we do not actually need the guaranteed nearest neighbor. If a semantic search returns, instead of the ten objectively most similar documents, the nine most similar plus one almost as good, no human notices. So we may allow a small, controlled error and get an enormous speed gain in return. That is Approximate Nearest Neighbor Search (ANN).

The decisive metric is called recall: the fraction of the true nearest neighbors that a method actually returns. A recall of 0.95 means that, on average, 95% of the "correct" hits are found. The whole art of ANN consists in achieving high recall (close to exact search) at drastically reduced compute time—and in making both finely tunable through a handful of parameters. Historically there were several families for this: Locality-Sensitive Hashing (LSH), which deliberately throws similar points into the same hash buckets; inverted-file methods (IVF), which partition the space into cells and search only the nearest cells; and product quantization (PQ), which compresses vectors. But the method that has risen to become the de-facto standard in recent years comes from an entirely different corner: from the graph theory of social networks.

Part 2: The Small World—From Milgram's Letters to Kleinberg's Proof

Six Handshakes

In 1967 the social psychologist Stanley Milgram mailed letters to randomly chosen people in the American Midwest. The task: forward the letter to a specific target person in Massachusetts—but only through personal acquaintances, always one step onward, to someone believed to be closer to the target. Astonishingly, many letters reached their goal, and the average chain length was about six. From this finding grew the popular talk of the "six degrees of separation."

Two things about this experiment are remarkable, and computer science long attended to only one half. The first, obvious statement: the social network has a small diameter—any two people are connected through few intermediaries. The second, subtler statement lies in the procedure itself: the people found these short paths in a decentralized way, each using only local knowledge of their own acquaintances, without a map of the entire network. Short paths not only exist—one can also find them efficiently with a simple greedy strategy.

Watts, Strogatz, and the Structure

In 1998 Duncan Watts and Steven Strogatz gave this phenomenon a mathematical model (Nature). They showed that many real networks—from neural wiring to power grids—unite two seemingly contradictory properties: high local clustering (my acquaintances know each other) and at the same time a small diameter. Their recipe: take a regular lattice with many local connections and "rewire" a few of them randomly to distant nodes. Even a handful of such long-range links suffices to reduce the diameter of the whole network dramatically while the local structure is preserved. This is the birth of the term small-world network.

Kleinberg's Decisive Refinement

Watts and Strogatz explained why short paths exist. But they did not explain why Milgram's participants could also find those paths. Jon Kleinberg closed this gap in the year 2000 (Nature, "Navigation in a small world"). For our purposes his result is the pivot.

Kleinberg considered a lattice model in which every node has short connections to its immediate neighbors plus one long-range connection whose target is chosen at random—but not uniformly, rather with a probability that falls off with distance r like r^(−α). The exponent α controls whether the long-range links point more nearby or clear across the network. Kleinberg's theorem: a greedy routing, in which each node simply passes the message to whichever of its acquaintances lies geometrically closest to the target, finds short paths only at one single, distinguished value of α (namely α equal to the dimension of the lattice)—and then even in polylogarithmic time. At any other exponent the greedy search needs a polynomial number of steps.

The lesson to carry over into the construction of data structures is profound: a network is navigable—that is, quickly traversable with purely local, greedy search—precisely when its connections have the right mixture of reaches: many short ones for fine adjustment, few long ones for the coarse jump, and these balanced across all distance scales. It is exactly this property that HNSW graphs will produce artificially.

Part 3: From NSW to HNSW—Turning the Data Space into a Navigable Graph

The Leap from Social Networks to Vectors

The igniting idea is to treat the data space itself as a small-world network. One builds a graph in which every stored vector is a node and edges connect nodes that lie close to each other in vector space. A search then becomes navigation: you start at some node and greedily walk on toward whichever neighbor lies closer to the query point—until no neighbor is closer than the current node. This local minimum is the (approximate) nearest neighbor.

The first complete embodiment of this idea, the Navigable Small World (NSW) method of Malkov and colleagues (2014), built the graph simply by incremental insertion: each new point is connected to its M nearest already-present neighbors. The clever part is that the early-inserted links tend to become long (because the graph was still sparse) and the late ones short—so the long-range links that Kleinberg demanded arise on their own. NSW worked well but had a weakness: greedy search could take many unnecessary steps in densely populated regions, and in the worst case the search time degenerated toward polylogarithmic to linear magnitudes, because there was no clean separation between "big" and "small" jumps.

The Hierarchical Twist

In 2016 Yury Malkov and Dmitry Yashunin solved this problem with an elegant addition and named the result Hierarchical Navigable Small World (HNSW) (arXiv 1603.09320; the mature version appeared in 2020 in the IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 42, pp. 824–836). The basic idea: instead of a single graph, one builds a stack of layers, like the floors of a high-rise.

• The bottom layer (Layer 0) contains all points and is the most densely connected—this is where the fine search happens.
• Each higher layer contains only an exponentially shrinking subset of the points, but with far-reaching connections. The top layer has only a handful of nodes that coarsely span the whole space.

Which highest layer a point lands in is determined randomly on insertion, with an exponentially decaying probability. Concretely, one draws a random number and computes the level via a formula whose factor—the so-called level multiplier mL—ideally sits at 1 / ln(M). A point is always present in all layers below its highest level as well.

The Skip-List Analogy

Anyone who knows the skip list data structure (Pugh, 1990) recognizes HNSW immediately: a skip list speeds up search in a sorted linked list by inserting additional, ever sparser "express levels" with skip pointers above the base list. You begin at the top, jump in big steps as far as possible, then drop down a level and refine. HNSW is essentially the generalization of this idea from the one-dimensional, sorted case to a high-dimensional, unordered vector space: the upper layers are the express levels for the coarse jump, Layer 0 is the complete base list for the final fine adjustment. It is precisely this clean separation of distance scales—Kleinberg's mixture of long and short links, now organized explicitly across floors—that gives HNSW the coveted logarithmic scaling of search time.

Part 4: How HNSW Searches and Builds

The Search: From Coarse to Fine

A query always runs from top to bottom:

1. Entry at the top. The search begins at a fixed entry node in the topmost, sparsely populated layer.
2. Greedy descent. Within a layer you walk greedily to the neighbor lying closer to the query point, until no neighbor yields an improvement. This locally best node is taken as the entry point into the next-lower layer.
3. Repeat. You work your way down floor by floor, each level narrowing the search region further.
4. Fine search on Layer 0. On the bottom layer the algorithm switches from pure greed to a beam-search-like exploration: it maintains a dynamic candidate list of the best hits so far and expands their neighbors until the list no longer improves. At the end it returns the best k candidates.

The size of this dynamic candidate list is the most important search parameter and is called ef (or efSearch, from "size of the dynamic candidate list"). A large ef lets the algorithm consider more candidates at once and lowers the danger of getting stuck in a bad local minimum—this raises recall but costs more time. A small ef is lightning fast but less accurate. Important: ef must be at least as large as the desired k.

The Build: The Same Search, Used in Reverse

The index is built incrementally through insertion, and the astonishing thing is that insertion uses almost the same procedure as search. For each new point:

1. Draw its maximum level at random (exponentially decaying).
2. Run a search from the top for the nearest already-present nodes to find good entry points.
3. Connect the new point in each layer, from its maximum level downward, to a selection of its nearest neighbors.

Two parameters govern the build. M is the number of connections a node keeps per layer—in a sense the branching factor of the graph. (In the bottom layer one often allows twice as many, M0 ≈ 2·M, because the neighborhood is densest there.) efConstruction is the counterpart of ef during building: the size of the candidate list from which the best neighbors are chosen on insertion. A high value produces a more careful, higher-quality graph but lengthens build time.

An often underestimated detail is the neighbor-selection heuristic. Instead of simply connecting the M absolutely nearest points, HNSW uses a heuristic that also attends to diversity of directions: it prefers neighbors that span the space around the node in different directions, rather than choosing several very close points in the same direction. This prevents clusters from being well connected only internally but poorly to one another—an effect that would otherwise destroy the "bridges" between dense regions and lead the greedy search into dead ends.

Why This Scales Logarithmically

The intuitive justification for the logarithmic search time: the number of layers grows only logarithmically with the point count (each level is sparser than the one below by a constant factor). On each layer the greedy search does, thanks to the bounded branching factor M, only a constant or slowly growing amount of work. The product of "logarithmically many layers" and "little work per layer" yields an overall complexity that in practice scales like O(log N)—the reason HNSW still answers even at billions of vectors, long after the linear scan has capitulated.

Part 5: The Adjustment Knobs—The Trade-off Between Recall, Speed, and Memory

HNSW is no automatic win but a system of deliberately chosen trade-offs. Three parameters span the space of possibilities, and it pays to understand their effect precisely, because they reappear under the same names in every vector database—whether FAISS, pgvector, Milvus, or Qdrant.

The practical consequence is illuminating: efSearch can be adjusted at runtime, per query, without rebuilding the index. So you can use the same index once with a low ef for fast, tolerant queries and another time with a high ef for precision-critical cases. M and efConstruction, by contrast, are "baked into" the graph—whoever wants to change them must re-index.

The great price HNSW pays is memory. The graph with all its edges must reside in main memory for fast access, and the edges come on top of the already voluminous vectors. A higher M improves recall but inflates exactly this edge memory. For billions of 1536-dimensional vectors, the RAM requirement quickly becomes the dominant cost factor of an entire system.

The second, often overlooked weakness concerns deletions and changes. HNSW is by nature an "append-friendly" structure: insertion is cheap, but cleanly removing a node is delicate, because it may serve as an important bridge in the graph. In practice one resorts to "tombstones" (marking instead of truly deleting) and periodic rebuilds—a compromise that can become unpleasant in write-intensive, constantly changing datasets. I am of the opinion that this very point—not raw search speed—is the actual bottleneck in many production systems, and that it deserves more weight in the choice of a vector database than the usual benchmark tables suggest.

To tame the memory hunger, one likes to combine HNSW in practice with quantization: product quantization (PQ) compresses the vectors lossily to a fraction of their size, so that the graph navigates over compact codes and the full vector is consulted only for the final accuracy check ("re-ranking"). For datasets that do not fit into RAM even then, there are disk-based relatives such as DiskANN (Microsoft's Vamana graph) or the partitioning SPANN, which offload the lion's share of the index onto SSDs and need only a few targeted read operations per query. They show that the graph idea is not confined to main memory—but HNSW in RAM remains, for most medium-sized applications, the fastest and simplest path.

Part 6: HNSW in the Wild—The Engine of Vector Databases and of RAG

Where HNSW Sits Today

You can hardly build a system for semantic search without encountering HNSW. FAISS, Meta's open-source library for similarity search, offers HNSW as one of its central index classes (often in combination with PQ). pgvector, the extension that brings vector search directly into PostgreSQL, introduced HNSW as an index type and thereby made it available to countless existing applications without a separate specialized database. Specialized vector databases such as Milvus, Qdrant, and Weaviate use HNSW as their default or core index; Milvus, for instance, additionally supports IVF and DiskANN for other operating points. This ubiquity is no accident: HNSW delivers, across a wide range of dataset sizes, an excellent compromise of high recall and low latency, without having to train the data space beforehand or split it into cells.

The Role in Retrieval-Augmented Generation

The most recent surge of popularity for vector databases comes from large language models. A language model knows only what was in its training data, and it "hallucinates" about everything it does not know. RAG solves this by slipping the model relevant knowledge before it answers: the user's question is embedded into a vector, an ANN search fetches the most similar snippets of knowledge from a vector database, and these are placed into the model's context along with the question. The quality of the whole chain depends directly on the retrieval stage—as the literature puts it, "RAG lives or dies by the quality and speed of retrieval." This is exactly where HNSW works in the engine room: it is the component that, out of millions of document snippets, finds the fitting ones in a few milliseconds.

The embeddings themselves, which HNSW handles, incidentally usually come from precisely the architectures this vault treats elsewhere: the transformer models produce the vectors whose proximity HNSW then searches. And the question of whether proximity in embedding space really captures similarity of meaning leads deep into the debate about the internal representation of neural networks.

An Honest Look at the Limits

As dominant as HNSW is, it is no panacea. Three reservations matter. First, filtered search—"find similar documents, but only from the year 2025 and only in German"—shifts the problem considerably, because filters can disturb the navigability of the graph; this is an active research field with its own methods. Second, as mentioned, dynamics (many deletions) is an Achilles' heel. Third, it still holds: approximation means approximation. For applications in which a missed hit is expensive—say in forensic search or in legally binding similarity checks—one must set recall deliberately high and, in case of doubt, combine it with exact verification.

I am of the opinion that the real conceptual beauty of HNSW lies less in the algorithm itself than in the underlying transfer: a finding about the navigability of social networks from the 1960s, mathematically sharpened around 2000, became half a century later the load-bearing infrastructure of AI search. This is a prime example of how basic research on a seemingly remote question—"How do people find short paths in their acquaintance network?"—supports, decades later, a billion-dollar application.

The Central Takeaway

The central lesson of HNSW is one about dealing with impossibility. In high dimensions, exact nearest-neighbor search is practically unaffordable—the curse of dimensionality cannot be programmed away. Instead of running into that wall, HNSW trades a tiny, measurable and tunable inaccuracy for an enormous speed gain: linear search over billions of points becomes a logarithmic walk through a navigable graph.

For your own practice this means two things. First: if you build semantic search, recommendations, or RAG, think in terms of the three quantities M, efConstruction, and efSearch—and remember that only the last is adjustable at runtime, while the first two shape the index. Second, and more generally: for every expensive exact problem, ask whether you really need exactness or whether a controlled approximation with a clear recall metric suffices. Often the pragmatic approximation is not the lazy compromise but the only solution that scales at all.

A Question to Ponder

In which of your own systems do you still treat a search or a matching as an exact problem—and would a deliberately allowed, measured inaccuracy (with a defined recall target) enable a leap in speed or cost there that you had until now considered impossible? And conversely: where would even a recall of 99% be an unacceptable risk?

Cross-References in the Vault

• Attention Is All You Need: The Transformer, Self-Attention, and the Architecture of Modern AI – the architecture that produces the embedding vectors HNSW searches.
• The Ghost in the Machine: How to Read a Neural Network From the Inside – the question of what a vector in high-dimensional space actually "means."
• How Big Is Big Enough? Scaling Laws, Chinchilla, and the Measurement of AI – the scaling laws of the models whose knowledge RAG augments with external retrieval.
• The Ring That Shares the Load: Consistent Hashing and the Art of Moving Gracefully – how to distribute vector indexes across many machines (sharding).
• Write First, Sort Later – Log-Structured Merge-Trees and the Inversion of the Database – a related storage engine and the same delete-by-tombstone problem.

Sources

• Malkov, Yashunin: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv 1603.09320, 2016; IEEE TPAMI 42(4):824–836, 2020): https://arxiv.org/abs/1603.09320
• Malkov, Ponomarenko, Logvinov, Krylov: Approximate nearest neighbor algorithm based on navigable small world graphs, Information Systems 45 (2014) – the NSW predecessor.
• Kleinberg: Navigation in a small world, Nature 406, 845 (2000): https://www.researchgate.net/publication/12350387_Kleinberg_J_Navigation_in_a_small_world_Nature_406_845
• Watts, Strogatz: Collective dynamics of 'small-world' networks, Nature 393 (1998).
• Milgram: The Small-World Problem, Psychology Today (1967) – origin of the "six degrees."
• Pinecone: Hierarchical Navigable Small Worlds (HNSW) – an accessible explanation: https://www.pinecone.io/learn/series/faiss/hnsw/
• Zilliz/Milvus FAQ: Key configuration parameters for an HNSW index (M, efConstruction, efSearch): https://zilliz.com/ai-faq/what-are-the-key-configuration-parameters-for-an-hnsw-index-such-as-m-and-efconstructionefsearch-and-how-does-each-influence-the-tradeoff-between-index-size-build-time-query-speed-and-recall
• Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement (arXiv 1610.02455) – on the curse of dimensionality and method comparison: https://arxiv.org/pdf/1610.02455
• Subramanya et al.: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node (NeurIPS 2019) – the disk-based Vamana graph.
• Chen et al.: SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search (arXiv 2111.08566): https://arxiv.org/pdf/2111.08566
• Crunchy Data: HNSW Indexes with Postgres and pgvector: https://www.crunchydata.com/blog/hnsw-indexes-with-postgres-and-pgvector

← All articles