HNSW Index: Architecture for Fast Vector Search

In the previous chapter, we explored vector similarity search and the fundamental challenge it presents: given a query vector, find the most similar vectors in a collection. The brute-force approach, computing distances between the query and every vector in the database, delivers perfect accuracy but scales linearly with the number of vectors. For a million-document corpus with 768-dimensional embeddings, every single query requires a million high-dimensional distance computations. For ten million documents, it requires ten million. This quickly becomes impractical for the real-time retrieval that RAG systems demand.

Approximate nearest neighbor (ANN) search addresses this scalability issue. Rather than guaranteeing exact nearest neighbors, ANN algorithms trade a small amount of accuracy for dramatic speed improvements, often returning results in milliseconds even across billion-vector collections. Among the many ANN algorithms developed over the years, one has emerged as the dominant choice for vector search in production systems: Hierarchical Navigable Small World graphs, or HNSW.

HNSW, introduced by Yuri Malkov and Dmitry Yashunin in 2016, combines two powerful ideas: the "small world" property of certain graphs (where any node can reach any other node in surprisingly few hops) and a hierarchical layering scheme inspired by skip lists. The result is an index structure that supports both fast construction and fast search, with tunable parameters that let you precisely control the tradeoff between speed and recall. HNSW powers the vector search behind libraries like FAISS, Hnswlib, and vector databases such as Pinecone, Weaviate, Qdrant, and Milvus.

Before HNSW, approximate nearest neighbor search was fragmented across several methods. Tree-based methods like KD-trees work well in low dimensions but collapse under the curse of dimensionality: with 100+ dimensional vectors, every leaf becomes nearly equidistant from any query. Locality-sensitive hashing (LSH) offers provable guarantees but typically requires many hash tables to achieve good recall, leading to substantial memory overhead and tuning complexity. Quantization methods like IVF (Inverted File Index) partition the space into clusters and only search nearby partitions, but their recall degrades on datasets with complex distributions. Graph-based methods were known to have promise but lacked a principled way to maintain efficient routing as the graph grew. HNSW solved all of these problems simultaneously, and the elegance of its solution is worth understanding in depth.

To understand HNSW, we need to start with the concept that gives it half its name: small world graphs.

In the 1960s, psychologist Stanley Milgram conducted his famous "small world" experiment, asking people to forward letters to a target person through chains of acquaintances. He found that most letters arrived in about six steps, giving rise to the popular phrase "six degrees of separation." This phenomenon, where nodes in a large network can reach each other through surprisingly short paths, is the small world property.

To appreciate why this property is remarkable, consider the contrast with what we might naively expect. If a graph has a million nodes and each node connects only to a few neighbors, you might imagine that traversing from one side of the graph to the other would require thousands or even hundreds of thousands of hops. In a chain or grid structure, that intuition holds true: the number of hops scales with the diameter of the structure, which can be proportional to $n$ or $\sqrt{n}$. But small world graphs defy this expectation. Even as the number of nodes grows into the millions or billions, the average path length between any two nodes increases only logarithmically.

What makes social networks "small worlds" is the combination of two structural features:

• Local clustering: People tend to know others in their immediate community, creating dense local neighborhoods. Your friends are likely friends with each other, forming tightly knit clusters of mutual connections. Mathematically, this is captured by a high clustering coefficient: the fraction of a node's neighbors who are also neighbors of each other is large.
• Long-range connections: A few connections bridge distant communities (a friend who moved abroad, a colleague in a different industry). This provides shortcuts across the graph. These rare but critical links act as express highways. This allows you to jump from one cluster to a completely different one in a single step.

The interplay between these two features creates the small world property. Local clustering alone would produce a graph where short paths exist only within communities, and reaching a distant community would require traversing the entire structure. Long-range connections alone would create a graph where you can jump anywhere quickly but lack the dense local structure needed for precise navigation once you are in the right neighborhood. Together, they enable a style of traversal where long-range hops bring you close to your target quickly, and then dense local connections let you zero in on exactly the right node.

The mathematical characterization of small world graphs comes from Watts and Strogatz (1998), who studied the transition between regular lattices (high clustering, long path lengths) and random graphs (low clustering, short path lengths). By rewiring a small fraction of edges in a regular lattice to create random long-range connections, they produced graphs that simultaneously exhibited high clustering and short path lengths. This combination is exactly what we want for navigation: the local structure provides precision, and the long-range structure provides speed.

This same structure turns out to be incredibly useful for nearest neighbor search. If we build a graph where vectors are nodes and edges connect similar vectors, we can move from any starting point to any query's nearest neighbor by repeatedly jumping to the most promising neighbor, much like forwarding Milgram's letters. The key realization is that vector similarity naturally provides the notion of "closeness" needed to organize these connections: nearby vectors in the embedding space form the local clusters, while occasional connections to more distant vectors serve as the long-range bridges.

A small world graph guarantees that short paths exist between any two nodes, but that alone is not enough. We also need to be able to find those short paths efficiently, without knowing the global structure of the graph. This introduces navigability, a subtle but critical distinction.

The existence of a short path is a property of the graph's topology. Navigability, by contrast, is a property of how easily a simple, local algorithm can discover and follow that path. Imagine being dropped into a massive city with no map. Knowing that every location is reachable within a few blocks is reassuring, but useless if you have no way to decide which direction to walk at each intersection. Navigability means that at every intersection, looking only at the streets immediately available to you, you can make a locally informed decision that consistently brings you closer to your destination.

Consider a simple greedy search on such a graph. You start at some entry node and want to reach the node closest to your query vector $q$. At each step, you look at all neighbors of your current node, compute their distances to $q$, and move to whichever neighbor is closest. You stop when no neighbor is closer to $q$ than your current node. This is a classic greedy best-first search, and its elegance lies in its simplicity: no priority queues spanning the entire graph, no global routing tables, and no precomputed shortest paths. The only information the algorithm uses at each step is the set of neighbors of the current node and their distances to the query.

For this to work well, the graph needs those same two structural ingredients we discussed above, but now viewed through the lens of routing. Dense local connections ensure that once you are near the target, you can find it precisely. Without them, the greedy search might reach the right neighborhood but be unable to take the final steps to the exact nearest neighbor, because no edge connects the current node to the true answer. Long-range connections ensure that you can quickly traverse from distant regions of the vector space to the target's neighborhood. Without them, the greedy search would have to take many small steps, inching across the space one local cluster at a time, turning what should be a logarithmic traversal into a linear one.

The problem with a flat (single-layer) NSW graph is that the greedy search can get trapped in local minima. As the graph grows, long-range connections become increasingly diluted by short-range ones. Early in the search, when you are far from the target, you need long-range jumps to make progress quickly. But in a large flat graph, the probability of finding a useful long-range connection among a node's fixed-size neighbor list diminishes as the graph grows.

Consider what happens during graph construction: when a node is inserted, its neighbors are chosen from the closest existing nodes. In a large graph, those closest nodes are very nearby, so the resulting edges are short-range. Long-range edges, which were created early when the graph was small and "closest" meant "relatively far away," become a smaller and smaller fraction of the total edges. The search degrades, requiring more hops and more distance computations, and the greedy algorithm's performance begins to approach the very linear scaling we are trying to avoid.

There is also a deeper problem: the greedy algorithm can get stuck at a local minimum that is not the global nearest neighbor. Imagine a query $q$ positioned in the vector space. The greedy search might reach a node $v$ that is reasonably close to $q$, but none of $v$'s neighbors are closer. The algorithm terminates and reports $v$ as the nearest neighbor, even though the true nearest neighbor $u$ exists elsewhere in the graph and is closer to $q$. This happens because the path from $v$ to $u$ requires moving temporarily away from $q$, and the greedy algorithm refuses to do so. In a flat graph, there is no mechanism to escape this trap. The hierarchical structure of HNSW is the solution.

The problem shown above is fundamental: no matter how many steps the greedy algorithm takes from node C, it cannot reach T without first moving farther from the query Q. The flat NSW graph provides no escape hatch. This is the core motivation for the hierarchical structure.

HNSW solves the long-range navigation problem with an elegant idea borrowed from skip lists, a probabilistic data structure for sorted sequences.

In a skip list, elements exist on multiple levels. The bottom level contains all elements. Each higher level contains a random subset of the elements from the level below, with roughly half as many elements per level. Searching starts at the top level, where elements are sparse and each hop covers a large range, then descends to lower levels for finer-grained search. This gives $O(\log n)$ search time. A skip list achieves the efficiency of a balanced binary search tree without requiring complex rebalancing operations, relying instead on simple randomization to maintain its structure.

HNSW applies the same principle to graph-based nearest neighbor search, translating the one-dimensional skip list into a multi-dimensional navigable graph hierarchy. Instead of a single graph, HNSW builds a hierarchy of graphs across multiple layers:

• Layer 0 (the bottom layer) contains all vectors, connected to their nearest neighbors with short-range edges. This layer is the most densely populated and provides the fine-grained resolution needed to identify the true nearest neighbors.
• Layer 1 contains a subset of vectors, connected with edges that naturally span longer distances (because the nodes are more spread out). Since fewer nodes exist on this layer, even connecting to "nearest neighbors" produces edges that cover more ground in the vector space.
• Layer 2 contains an even smaller subset, with even longer-range connections. The sparser the layer, the more each edge acts as a highway through the space.
• The top layer contains just a handful of nodes. This provides a coarse "highway" across the entire vector space. A single hop on this layer might span a distance that would require dozens of hops on layer 0.

HNSW determines which layer each node belongs to using a randomized assignment process that mirrors the probabilistic structure of skip lists. Each node is assigned a maximum layer using a random process. Most nodes exist only on layer 0. Fewer nodes reach layer 1, fewer still reach layer 2, and so on. The maximum layer $l$ is assigned using a formula that ensures this exponential decay:

We examine each component and its role in producing the desired distribution of layers:

• $l$: the maximum layer assigned to the node. A node assigned layer $l$ will exist on every layer from 0 up to $l$, meaning it participates in the graph at multiple levels of the hierarchy.
• $\text{uniform}(0, 1)$: a random value drawn from a uniform distribution between 0 and 1. This is the source of randomness that ensures different nodes end up on different layers. Each insertion draws independently from this distribution.
• $-\ln(\text{uniform}(0, 1))$: this transformation is a classic technique known as inverse transform sampling. The negative natural logarithm of a uniform random variable produces a value that follows an exponential distribution with rate parameter 1. Most of the time, the uniform draw is close to 1, making $-\ln(\text{uniform}(0,1))$ close to 0, which means most nodes will be assigned to low layers. Occasionally, the uniform draw is close to 0, producing a large value of $-\ln(\text{uniform}(0,1))$ and placing the node on a high layer. This naturally produces the "many nodes at the bottom, few at the top" structure we need.
• $m_L$: the level multiplier, typically set to $1/\ln(M)$. This scaling factor controls how quickly the exponential distribution decays and, consequently, how many nodes appear on each successive layer. By tying $m_L$ to $M$, the formula ensures that the probability of reaching layer $l$ is proportional to $M^{-l}$. In other words, each layer has roughly $1/M$ times as many nodes as the layer below it.
• $\lfloor \dots \rfloor$: the floor function, which discretizes the continuous exponential value into integer layers. Since layers are discrete (layer 0, 1, 2, ...), the continuous value must be rounded down to the nearest integer.

The net effect of this formula is that each layer has roughly $1/M$ times as many nodes as the layer below, mirroring the skip list structure. This exponential thinning is what gives HNSW its logarithmic search complexity: the number of layers grows as $O(\log_M n)$, and each layer requires only a bounded number of greedy steps, so the total search cost scales logarithmically with the number of vectors.

Why does this hierarchy solve the local minimum problem? Because on the upper layers, the graph is so sparse that a node's "nearest neighbors" on that layer span large distances in the vector space. The global structure of the embedding space is visible even through simple greedy routing, because the sparser a layer is, the more each edge functions as a long-range bridge. When the search descends to lower layers, it arrives with a much better starting point than any random entry would provide, and the denser connectivity of lower layers ensures that the greedy algorithm can refine its answer without getting permanently stuck.

This design naturally separates the two phases of search:

1. Coarse navigation (upper layers): With few, widely-spaced nodes, each greedy step covers a large distance. You quickly zoom into the right region of the space. Because the nodes on upper layers are sparse representatives of the entire collection, the graph on each upper layer acts like a coarse map, and greedy routing on this map efficiently narrows the search to the correct neighborhood.
2. Fine-grained search (lower layers): With many densely-connected nodes, you refine your search to find the actual nearest neighbors. Once the upper layers have brought you to approximately the right region, layer 0's dense connectivity ensures that the final, precise answer is reachable within a few more hops.

HNSW builds its index incrementally: vectors are inserted one at a time, and each insertion both places the new node into the graph and establishes connections to existing nodes. This incremental approach means the graph evolves as data is added, with each new vector benefiting from the structure already in place and simultaneously enriching that structure for future insertions. The construction algorithm has two main phases for each inserted element.

When a new element $q$ is inserted, the first decision the algorithm must make is which layers this element will inhabit. This is determined by assigning a maximum layer $l$ using the randomized formula:

As we discussed in the previous section, this formula turns a uniform random draw into a geometrically decaying layer assignment. Let us revisit each component briefly in the context of construction:

• $l$: the maximum layer assigned to the node. The element will be present on every layer from 0 through $l$, and edges will be created for it on each of these layers.
• $\text{uniform}(0, 1)$: a random value drawn from a uniform distribution between 0 and 1. This is drawn independently for each inserted element. This keeps the layer assignments are uncorrelated.
• $-\ln(\text{uniform}(0, 1))$: a transformation using inverse transform sampling to convert the uniform value into an exponential distribution. Because the exponential distribution is heavily concentrated near zero, most nodes receive small values, and consequently low layer assignments.
• $m_L$: the level multiplier (typically $1/\ln(M)$), which scales the distribution to control the decay rate of layer probabilities. The choice of $m_L = 1/\ln(M)$ ties the layer structure directly to the connectivity parameter $M$. This keeps the hierarchy has the right density at each level.
• $\lfloor \dots \rfloor$: the floor function, which discretizes the continuous value into integer layers, since the hierarchy consists of discrete levels numbered 0, 1, 2, and so on.

This formula produces an exponential distribution of layers. With $M = 16$ and $m_L = 1/\ln(16) \approx 0.36$, the probabilities work out roughly as:

• ~94% of nodes exist only on layer 0
• ~6% reach layer 1
• ~0.4% reach layer 2
• A negligible fraction reach layer 3 or higher

These numbers convey an important structural insight: the vast majority of nodes live only on the bottom layer, where they contribute to the dense, fine-grained connectivity needed for precise nearest neighbor identification. A small fraction of nodes are "promoted" to higher layers, where they serve as landmarks and waypoints for long-range navigation. And only a tiny handful reach the topmost layers, where they act as universal entry points from which any search can begin. This exponential decay is precisely what creates the skip list-like structure. Each layer is roughly $M$ times sparser than the one below it.

The insertion order matters less than you might think, because of the random layer assignment. Whether a node is inserted early or late in the construction process, its layer is determined by the random draw, not by its position in the insertion sequence. This stochastic nature is also what makes HNSW resilient: no adversarial input sequence can force all nodes to the top layer, creating a degenerate hierarchy. The randomness ensures that, in expectation, the layer distribution always follows the intended exponential decay.

Once the new element $q$ has its assigned layer $l$, the algorithm needs to find good neighbors to connect it to on each layer from $l$ down to 0. The quality of these connections is critical: they determine whether the graph will be navigable and whether future searches will be able to efficiently route through this part of the space. This happens in two phases.

Phase 1: Descend to the insertion layer. Starting from the global entry point at the top layer, perform a simple greedy search (beam width of 1) on each layer above $l$. At each layer, walk greedily toward $q$ until no closer neighbor can be found, then descend. This phase finds a good starting point for the actual insertion work. No connections are made during this descent. By the time the algorithm reaches layer $l$, it has identified a node that is reasonably close to $q$ in the vector space. This provides a high-quality starting point for the neighbor search that follows.

Phase 2: Insert and connect. Starting from layer $l$ down to layer 0, perform a broader search (with beam width ef_construction) to find the closest existing nodes to $q$. The parameter ef_construction governs how thoroughly the algorithm explores the neighborhood around $q$. A larger ef_construction means more candidate nodes are examined, increasing the likelihood of finding the truly best neighbors at the cost of additional distance computations. From these candidates, select the best $M$ neighbors and create bidirectional edges between $q$ and each selected neighbor. The bidirectionality is essential: it ensures that $q$ is reachable from its neighbors and that $q$'s neighbors are reachable from $q$, maintaining the graph's navigability in both directions.

The selection of which $M$ neighbors to connect is critical and deserves careful attention. The simplest approach is to pick the $M$ closest nodes, but HNSW uses a more sophisticated heuristic that favors diversity. The heuristic prefers neighbors that are close to $q$ while covering different "directions" in the vector space. This prevents all connections from clustering in one region and ensures better navigability.

To understand why diversity matters, imagine a scenario where a new node $q$ is positioned at the edge of a dense cluster. The $M$ closest nodes might all be members of that same cluster, all lying in roughly the same direction from $q$. If $q$ connects only to these nearby cluster members, there would be no edge leading outward from $q$ toward other regions of the space. Future searches passing through $q$ would find it easy to reach the nearby cluster but impossible to exit toward other clusters. The diversity heuristic avoids this trap by ensuring that $q$'s connections reach outward in multiple directions.

The neighbor selection heuristic works as follows. Candidates are sorted by distance to $q$. For each candidate $c$ (in order of increasing distance), $c$ is added to the neighbor set only if it is closer to $q$ than it is to any already-selected neighbor. In other words, a candidate is rejected if it is "covered" by an already-chosen neighbor:

We define the meaning and purpose of each symbol in this condition:

• $c$: the candidate neighbor being considered. Candidates are examined one at a time, in order of increasing distance from $q$, so the closest candidates are considered first.
• $q$: the newly inserted element, the node for which we are selecting neighbors.
• $d(x, y)$: the distance between $x$ and $y$, measured using whatever metric the index employs (Euclidean, inner product, or cosine distance).
• $\text{selected}$: the set of neighbors already chosen for $q$. This set starts empty and grows as candidates pass the heuristic test.
• $\min_{n \in \text{selected}} d(c, n)$: the distance from the candidate $c$ to the closest already-selected neighbor. This is the crux of the heuristic. If $c$ is very close to some already-selected neighbor $n$, then $n$ already "covers" the direction that $c$ would provide. Adding $c$ would be redundant, as searches arriving at $q$ could reach $c$'s region of the space by going through $n$ instead.

This condition ensures that we only add $c$ if it is closer to $q$ than to any existing neighbor. The geometric intuition is that each selected neighbor "claims" a region of space around it, and a new candidate is accepted only if it lies in an unclaimed direction. This encourages connections that spread outward in different directions, creating the diverse connectivity that makes the graph navigable.

The result of the diversity heuristic is a neighbor list where each connection opens up a distinct corridor through the vector space, maximizing the routing options available to future searches passing through $q$. The heuristic is applied during both construction and overflow pruning. This keeps the graph maintains its diverse connectivity as new nodes are added.

When a new edge is added between $q$ and an existing node $v$, the node $v$ might end up with more than $M_{\text{max}}$ connections. This overflow can happen because the bidirectional edge creation means that $v$ receives a new neighbor even though $v$'s original neighbor list was already full. In this case, $v$'s neighbor list is pruned back to $M_{\text{max}}$ using the same heuristic selection described above, keeping the most useful connections and discarding redundant ones.

The pruning re-evaluates all of $v$'s current neighbors (including the newly added $q$) and retains the set that best satisfies the diversity criterion. This keeps $v$'s connections continue to cover multiple directions. The paper uses $M_{\text{max}} = M$ for layers above 0, and $M_{\text{max0}} = 2M$ for layer 0, since the bottom layer benefits from denser connectivity. The rationale for doubling the connection limit on layer 0 is that this is where the most precise search occurs, and having more edges per node increases the probability that the greedy search can reach the exact nearest neighbor without getting stuck in a local minimum.

The full construction algorithm for inserting element $q$:

1. Assign random layer $l$ to $q$
2. Set entry point $ep$ to the current graph's entry point
3. For each layer from the top down to $l+1$: greedily search for the nearest node to $q$, update $ep$
4. For each layer from $l$ down to 0: a. Search for ef_construction nearest candidates to $q$ starting from $ep$ b. Select up to $M$ neighbors from candidates using the heuristic c. Add bidirectional edges between $q$ and selected neighbors d. For any neighbor that now exceeds $M_{\text{max}}$ connections, prune its neighbor list
5. If $l$ is higher than the current maximum layer, update the entry point to $q$

Step 5 deserves a brief note: whenever a newly inserted node reaches a layer higher than any existing node, it becomes the new global entry point for the entire index. This ensures that searches always begin at the topmost layer, where the sparsest, most globally connected node provides the starting point for the coarse navigation phase.

The construction cost is $O(n \log n)$ in total. Each insertion requires finding neighbors across the layers it inhabits, and the hierarchical structure ensures that this neighbor search takes $O(\log n)$ time per layer. Most nodes are on layer 0 only, so the dominant cost is the layer 0 search, which scales as $O(\log n)$ with a constant proportional to ef_construction. In practice, construction is typically 10 to 100 times slower than search, because construction uses a wider beam (ef_construction) and must run many insertions sequentially.

Searching an HNSW index follows the same two-phase pattern as construction, but optimized for finding the $k$ nearest neighbors of a query vector $q$. The search algorithm uses the hierarchical structure to decompose the problem into a fast coarse approach followed by a thorough local exploration, and this decomposition is what gives HNSW its characteristic efficiency.

Starting from the entry point on the top layer, perform a simple greedy search with beam width 1. At each layer, repeatedly move to the neighbor closest to $q$ until no improvement is possible. Then descend to the next layer, using the current best node as the entry point for the layer below.

This phase is fast because upper layers are sparse. Each greedy step on the top layer might skip over millions of vectors in a single hop. The descent quickly narrows the search to the right neighborhood. To build a concrete intuition, consider a graph with 10 million vectors and $M = 16$. The top layer might contain only a handful of nodes, and a single greedy step on this layer could jump from one end of the vector space to the other. Layer 2 might contain a few thousand nodes, and each hop covers a correspondingly smaller but still substantial distance. By the time the algorithm reaches layer 1, it has narrowed the search region from the entire collection down to a small neighborhood containing perhaps a few thousand nearby vectors. The total number of distance computations during this descent is remarkably small, typically just a few per layer, because only a single candidate (the current best) is tracked.

The greedy descent with beam width 1 is intentionally narrow. Using a wider beam during the descent would slow it down without providing much benefit, because the goal here is not to find the exact nearest neighbor but to land in the right neighborhood. The coarse structure of the upper layers ensures that even a single-node beam finds an excellent starting point for the beam search on layer 0.

Once you reach layer 0, the algorithm switches strategy. The greedy descent with beam width 1 was efficient but coarse; it found a good starting neighborhood but may not have identified the exact nearest neighbors. Layer 0, which contains all vectors, is where the precise answer lives. To find it, the algorithm performs a more thorough search using a beam width of ef_search (where ef_search $\geq k$). This is essentially a best-first search that maintains a dynamic candidate list:

1. Initialize a candidate set $C$ and a result set $W$ with the entry point from Phase 1.
2. While $C$ is not empty: a. Extract the nearest unvisited candidate $c$ from $C$ b. If $c$ is farther from $q$ than the farthest element in $W$, stop (no more useful candidates) c. For each neighbor $n$ of $c$ that has not been visited:
   • If $n$ is closer to $q$ than the farthest element in $W$ (or $|W| <$ ef_search), add $n$ to both $C$ and $W$
   • If $|W| >$ ef_search, remove the farthest element from $W$
3. Return the $k$ closest elements from $W$

The stopping condition in step 2b is the key to this algorithm's efficiency: the moment the best remaining candidate is worse than the worst element already in the result set, the search terminates. This means the algorithm does not exhaustively explore all reachable nodes; instead, it expands outward from the entry point in order of proximity to the query, and stops as soon as further expansion cannot possibly improve the results.

The parameter ef_search controls how thorough this search is. A larger ef_search explores more candidates, improving recall at the cost of more distance computations. Setting ef_search = k gives the fastest (but least accurate) search, while larger values progressively improve accuracy. The reason is straightforward: with a larger beam, the algorithm keeps more "backup" candidates alive during the search, reducing the chance that an early wrong turn causes it to miss the true nearest neighbor. Conversely, a very small beam means the search commits aggressively to its initial direction, finishing quickly but occasionally missing better answers in adjacent regions.

The complexity of the full search is $O(\log n)$ for the greedy descent plus $O(\text{ef\_search} \cdot \log(\text{ef\_search}))$ for the beam search on layer 0. In practice, the dominant cost is the layer 0 beam search, and the total number of distance computations typically falls between a few hundred and a few thousand even for billion-vector indexes, a dramatic reduction from the billions of computations that brute-force search would require.

HNSW is metric-agnostic: the algorithm works with any distance function, and the choice of metric has a significant impact on search quality and speed. Understanding which metric to use, and why, is an important practical consideration.

The three most common distance metrics in vector search are:

• Euclidean distance ($L_2$): measures the straight-line distance between two vectors. If $\mathbf{u}$ and $\mathbf{v}$ are vectors in $\mathbb{R}^d$, then $d_{L2}(\mathbf{u}, \mathbf{v}) = \sqrt{\sum_{i=1}^{d} (u_i - v_i)^2}$. Euclidean distance is sensitive to the magnitude of vectors, not just their direction. It is the natural choice when the absolute position in the embedding space carries meaning.
• Inner product (dot product): $d_{IP}(\mathbf{u}, \mathbf{v}) = -\mathbf{u}^T \mathbf{v} = -\sum_{i=1}^{d} u_i v_i$. The negative sign converts similarity into a distance (higher inner product means smaller "distance"). Inner product is maximized when two vectors point in the same direction and have large magnitudes.
• Cosine distance: $d_{cos}(\mathbf{u}, \mathbf{v}) = 1 - \frac{\mathbf{u}^T \mathbf{v}}{\|\mathbf{u}\| \|\mathbf{v}\|}$. This measures the angle between two vectors, ignoring their magnitudes. Cosine distance is equivalent to inner product on unit-normalized vectors, so normalizing your embeddings before indexing with inner product gives you cosine similarity.

For RAG systems with sentence embeddings (from models like all-MiniLM-L6-v2 or text-embedding-3-small), cosine similarity is almost always the right choice. Sentence embedding models are trained to encode semantic meaning in the direction of the vector, not its magnitude. Two sentences about the same topic should have similar directions even if they have different lengths (and thus different embedding magnitudes). Using inner product on unnormalized embeddings would conflate semantic similarity with embedding magnitude, giving misleading results. The standard practice is to normalize all embeddings to unit length before indexing, then use inner product (which equals cosine similarity on unit vectors) for maximum speed.

Euclidean distance is more appropriate in settings where the raw vector coordinates carry meaning, such as item embeddings trained with specific geometric objectives, or audio features where amplitude matters. For most NLP applications, cosine or inner product is preferred.

One important subtlety: HNSW's navigability relies on the distance metric being consistent with the graph's connectivity. The algorithm works best when the metric produces a smooth embedding space where nearby vectors are semantically similar and distant vectors are semantically different. Metrics that produce poorly separated embeddings (where many unrelated vectors end up at similar distances) degrade HNSW's performance by making it harder for the greedy search to make directional progress.

HNSW has a small set of parameters that give you fine-grained control over the index's behavior. Understanding these parameters is essential for tuning HNSW to your specific use case, and one of HNSW's practical strengths is that this parameter set is compact: only three values govern the entire structure. These three values interact in subtle ways. Choosing them wisely determines whether an index delivers millisecond queries with 99% recall or wastes memory and misses results.

$M$ controls the maximum number of bidirectional connections each node maintains on layers above 0. On layer 0, the maximum is $M_{\text{max0}} = 2M$. This parameter is the most fundamental architectural choice for an HNSW index, because it determines the density and shape of the graph at every level.

A higher $M$ means each node is connected to more neighbors, which improves recall (more paths exist to any target) but increases memory usage and slows down both construction and search (more neighbors to evaluate at each step). To understand why more connections improve recall, consider what happens when the greedy search reaches a node that is close to the query but not the true nearest neighbor. If that node has many connections, there is a high probability that one of its edges leads to a node that is even closer to the query. If it has few connections, the search might find no improving neighbor and terminate prematurely at a local minimum.

The relationship between $M$ and practical behavior:

• Low $M$ (4-8): Compact index, faster construction, but lower recall, especially for high-dimensional data. The graph is sparse, meaning fewer alternative paths exist between any two nodes. This can work well for low-dimensional data or applications where modest recall is acceptable.
• Medium $M$ (12-24): The sweet spot for most applications. $M = 16$ is a common default. At this level, the graph is dense enough to provide excellent navigability without excessive memory overhead. Most nodes have enough connections that the greedy search rarely gets stuck.
• High $M$ (32-64): Better recall for very high-dimensional or difficult datasets, at the cost of memory and speed. In high-dimensional spaces, where the "curse of dimensionality" makes all vectors roughly equidistant, denser connectivity helps the search algorithm distinguish between subtly different candidates.

Memory usage scales linearly with $M$. Each node stores $M$ neighbor IDs (or $2M$ on layer 0), so doubling $M$ roughly doubles the graph's memory overhead beyond the raw vector storage.

ef_construction determines how many candidates are considered when finding neighbors during index construction. It directly controls the quality of the graph. While $M$ determines how many connections each node will have, ef_construction determines how carefully the algorithm searches for the best candidates to fill those connections.

• Low ef_construction (50-100): Faster construction, but the graph may miss optimal connections, leading to lower search quality. With a narrow beam, the construction search might settle for neighbors that are merely good rather than optimal, especially in regions of the space where the nearest vectors are not immediately reachable from the current entry point.
• High ef_construction (200-500): Slower construction, but produces a higher-quality graph with better connectivity. Searches on this graph will be faster and more accurate. The wider beam means the construction algorithm explores more of the neighborhood around each new node, increasing the likelihood that the selected $M$ neighbors are truly the best available.

This is a one-time cost paid during index building. For most applications, it is worth using a higher ef_construction since you build the index once but search it many times. A common default is ef_construction = 200. The investment in construction quality amortizes over every future query: a well-built graph requires fewer hops and fewer distance computations at search time, and this benefit compounds across millions of queries.

ef_search controls the beam width during the layer 0 search phase. This is the most important runtime parameter because it directly controls the speed-recall tradeoff at query time.

• ef_search must be $\geq k$ (the number of nearest neighbors requested). Setting it smaller than $k$ would mean the algorithm cannot even return $k$ results.
• Low ef_search (close to $k$): Fastest search, lowest recall. The beam is so narrow that the search commits quickly to a small neighborhood and may miss true nearest neighbors lying just outside its field of view.
• High ef_search ($10\times$ to $100\times$ $k$): Slower search, recall approaching 100%. The wider beam explores a much larger region around the entry point, making it increasingly unlikely that any true nearest neighbor is missed.

Unlike $M$ and ef_construction, ef_search can be changed after the index is built. This means you can dynamically adjust it based on latency requirements: use a smaller ef_search when speed matters most, and a larger one when accuracy is critical. This flexibility is one of HNSW's most practical advantages: the same index can serve both fast, approximate queries (for example, in an interactive search interface where sub-millisecond latency is essential) and slow, high-recall queries (for example, in a batch evaluation pipeline where accuracy matters more than speed).

These parameters interact in important ways, and understanding these interactions is essential for effective tuning:

• Increasing $M$ without increasing ef_construction will not help much, because the construction search will not find good enough candidates to fill the larger neighbor lists. A node with 32 connection slots is only valuable if those slots are filled with truly useful neighbors, and finding 32 good neighbors requires searching more of the graph during construction than finding 8.
• A well-constructed graph (high ef_construction, appropriate $M$) can achieve the same recall with a lower ef_search compared to a poorly constructed graph. Investing in construction quality pays off in search efficiency. In other words, a graph built with ef_construction = 400 and $M = 16$ might achieve 99% recall at ef_search = 50, while a graph built with ef_construction = 50 and the same $M$ might need ef_search = 200 to reach the same recall level.
• For high-dimensional data ($d > 100$), higher $M$ values become increasingly important because high-dimensional spaces are harder to search. In these spaces, the notion of "nearest neighbor" becomes less distinctive (all distances tend to converge), and having more connections per node gives the search algorithm more options for finding the subtle gradients in distance that lead to the true nearest neighbors.
• The total memory per vector in an HNSW index is approximately $d \times 4$ bytes (for the raw float32 vector) plus $2M \times 4$ bytes (for the layer 0 connections) plus a small overhead for the upper layers. With $d = 768$ and $M = 16$, this works out to about $3200$ bytes per vector, or roughly 3.2 GB per million vectors. Understanding this formula lets you plan capacity accurately before building the index.

We trace through HNSW search with a small example to demonstrate the algorithm's two-phase strategy. Suppose we have 8 two-dimensional vectors and an HNSW index with $M = 2$ and 3 layers.

The index has the following structure across three layers. At the top, layer 2 contains only two nodes: A and F, connected by a single long-range edge. Layer 1 adds two more nodes, C and H, creating a four-node graph where A connects to C, C connects to F, and F connects to H. Finally, layer 0 contains all eight nodes arranged in sequence: A connects to B, B connects to C, C connects to D, D connects to E, E connects to F, F connects to G, and G connects to H. Each node that appears on a higher layer also appears on every layer below it, maintaining the hierarchical invariant.

Node A exists on all three layers (it is the entry point). Nodes C, F, and H were randomly assigned to layer 1. Node F was also assigned to layer 2. The actual 2D positions are:

Now let's search for the nearest neighbor of query $q = (6.5, 2.5)$ using Euclidean distance with ef_search = 3. We will walk through each layer of the search, computing every distance explicitly, so you can see exactly how the algorithm makes its decisions.

Layer 2 (greedy, beam width 1): Start at entry point A at position (1, 1). Check A's neighbors on layer 2: only F at (6, 1). We compare the distances to the query $q = (6.5, 2.5)$:

where:

• $d(x, y)$: the Euclidean distance between points $x$ and $y$
• $A$: the entry node at coordinates $(1, 1)$
• $F$: the neighbor node at coordinates $(6, 1)$
• $q$: the query vector at coordinates $(6.5, 2.5)$

Since $d(F, q) < d(A, q)$, F is closer, so we move to F. Notice the dramatic improvement: a single hop reduced the distance from 5.70 to 1.58, covering most of the journey in one step. This is exactly the coarse navigation behavior that the upper layers are designed to provide. F has no closer neighbor on layer 2, so we descend with F as entry point.

Layer 1 (greedy, beam width 1): Start at F on layer 1. F's neighbors on layer 1 are C and H. We calculate the distances:

where:

• $C$: the neighbor node at coordinates $(3, 1)$
• $H$: the neighbor node at coordinates $(8, 2)$
• $q$: the query vector at coordinates $(6.5, 2.5)$

H is at the same distance as F (1.58). We break the tie by choosing H. Move to H. Notice that C, despite being a neighbor on this layer, is much farther away at 3.81, so the greedy algorithm correctly avoids it. Check H's neighbors: F. F offers no improvement (1.58). Stop and descend with H as entry point.

Layer 0 (beam search, ef_search = 3): Now we switch from the fast greedy descent to the more thorough beam search. Start at H (8, 2). Initialize candidates $C = \{H\}$, result set $W = \{H\}$. Process H's neighbors: G at (7, 3). We calculate the distance:

where:

• $G$: the neighbor node at coordinates $(7, 3)$
• $q$: the query vector at coordinates $(6.5, 2.5)$

G is closer than anything in $W$, so we add it to both sets. This is a significant improvement: the distance dropped from 1.58 to 0.71, showing how the dense layer 0 connectivity reveals nearby nodes that the sparser upper layers could not directly access. Process G's neighbors: F at (6, 1). Distance from F to $q$: 1.58. Add F. Now $|W| = 3$, which equals ef_search. Continue: Process F's neighbors. For E at (5, 2):

where:

• $E$: the neighbor node at coordinates $(5, 2)$
• $q$: the query vector at coordinates $(6.5, 2.5)$

E is not closer than the farthest element in W (H at distance 1.58), so we are done exploring. The stopping criterion has been met: the best remaining candidate offers no improvement over the worst element in our result set.

Result: The nearest neighbor is G at (7, 3) with distance 0.71, found after visiting only 4 nodes out of 8. In this small example, the savings are modest, but the pattern is clear: the hierarchical descent brought us from the entry point to the right neighborhood in just two hops across the upper layers, and then a brief beam search on layer 0 identified the precise answer. In a real index with millions of vectors, this logarithmic scaling is what makes HNSW practical. The number of layers grows as $O(\log n)$, each layer requires only a handful of greedy steps, and the beam search on layer 0 explores a small, focused neighborhood rather than the entire collection.

We build an HNSW index and explore its behavior using hnswlib, the reference implementation by the HNSW authors.

We have 50,000 normalized 128-dimensional vectors. In a real RAG system, these would be document chunk embeddings from a model like the ones discussed in the Embedding Models chapter. Normalization is essential here: we want to use inner product as the distance metric, which equals cosine similarity when vectors have unit norm.

We create the HNSW index with hnswlib:

Building the index takes time because HNSW must insert each node and compute neighbor connections. The key parameters passed to init_index control this structure:

• space='ip': Uses inner product as the distance metric. Since our vectors are normalized, inner product equals cosine similarity.
• M=16: Each node connects to up to 16 neighbors (32 on layer 0).
• ef_construction=200: During construction, the search considers 200 candidates when finding neighbors for each new node.

To measure how well HNSW performs, we first compute the exact nearest neighbors using brute force:

This brute-force search computes all 5 million pairwise distances. While accurate, the linear scaling makes it too slow for large-scale production use. We use these exact results as the ground truth to measure HNSW's recall.

The beauty of HNSW is that ef_search can be tuned after building the index. We search with several values to observe the speed-recall tradeoff:

This table reveals the core tradeoff. Low ef_search values give blazing speed but miss some true nearest neighbors. As ef_search increases, recall climbs toward 1.0 (perfect), but each query takes longer. The sweet spot depends on your application: for RAG, a recall of 0.95 or higher is typically sufficient, since the reranker (which we will cover in an upcoming chapter) can compensate for a few missed candidates.

The curve's shape is characteristic: the recall jumps quickly from moderate to high as ef_search increases from small values, because early increases allow the beam to explore the most critical neighboring nodes. However, pushing recall from 98% to 99.9% requires much larger ef_search values, because catching the remaining missed neighbors requires exploring progressively more distant candidates. This diminishing returns pattern is universal across HNSW implementations and datasets.

We also examine how the connectivity parameter $M$ affects both memory and recall:

Higher $M$ values produce better recall because the denser graph provides more paths to reach any target. However, construction time also increases because each insertion requires evaluating more potential neighbors. For most practical applications, $M = 16$ offers a good balance. Notice that doubling $M$ from 16 to 32 typically improves recall by just a few percentage points at ef_search = 100, while approximately doubling construction time and memory usage. For applications that already have high recall with $M = 16$, the cost of increasing $M$ is rarely justified unless you are working with very high-dimensional or adversarial distributions.

Understanding HNSW's memory footprint is important for capacity planning. The index stores both the raw vectors and the graph structure:

The graph overhead is significant, roughly proportional to $M$. For high-dimensional embeddings ($d = 768$ or $d = 1536$), the vectors dominate memory usage. But for lower-dimensional data, the graph structure can be a substantial fraction of total memory. This is one reason why techniques like Product Quantization, which we will explore in an upcoming chapter, are often combined with HNSW to compress the stored vectors. By quantizing each vector from 4 bytes per dimension to 1 byte or less, you can reduce vector storage by 4x to 8x while accepting a modest drop in recall. The graph structure itself remains at full precision.

To appreciate what HNSW achieves, it helps to understand the alternatives and why they fall short for high-dimensional text embeddings.

The traditional approach to nearest neighbor search uses space-partitioning trees. A KD-tree recursively splits the data along alternating dimensions, creating a binary tree where each leaf contains a small subset of vectors. Ball trees generalize this to arbitrary metrics by enclosing each node's data in a hypersphere. These structures work excellently in low dimensions (below 20): a query can prune large portions of the tree early, reducing the number of distance computations dramatically.

The problem is the curse of dimensionality. In high dimensions, the volumes of hyperspheres and hyperrectangles become so large relative to the data that almost no pruning is possible. For 512-dimensional embeddings, a KD-tree query degrades to nearly brute-force performance: the tree structure provides no benefit. This makes tree-based methods completely impractical for modern NLP embeddings.

LSH takes a different approach: rather than partitioning the space, it uses random projections (or other hash functions) to probabilistically group similar vectors into the same buckets. Vectors that hash to the same bucket are likely to be nearby, so a query can limit its comparisons to vectors sharing bucket labels. Multiple independent hash tables are used to increase recall: if two similar vectors fail to collide in one table, they might collide in another.

LSH has provable guarantees but suffers in practice. To achieve high recall, you need many hash tables (typically 20 or more), which multiplies both memory and query time. The precision-recall tradeoff is difficult to tune: adding more tables improves recall but also increases the number of false positives (vectors that hash together despite low similarity). For high-dimensional embeddings with complex distributions, LSH's theoretical guarantees often translate into poor empirical performance, and the tuning burden is significant.

IVF, used extensively in FAISS, partitions the vector space into Voronoi cells using k-means clustering. Each vector is assigned to its nearest cluster centroid, and the index stores a list (the "inverted file") of vectors per centroid. At query time, the algorithm identifies the nearest few centroids, then searches only the vectors within those cells. By searching a fraction of all cells (controlled by the nprobe parameter), IVF achieves sub-linear query time.

IVF works well for moderate-dimensional data and handles very large collections by loading only the relevant partitions from disk. Its main weakness is that recall can drop sharply if the query falls near a cell boundary: its true nearest neighbors might be in a different cell, and if that cell is not searched, they are missed. The optimal choice of cluster count is also not obvious and requires tuning per dataset. HNSW typically achieves higher recall at lower latency than IVF for in-memory search, which is why most production vector databases prefer HNSW for their primary index. IVF becomes advantageous for datasets too large to fit in RAM, because it enables selective loading from disk.

HNSW's superiority over alternatives for high-dimensional in-memory search comes from several properties working together. First, the graph structure naturally adapts to the data distribution: edges are placed between similar vectors rather than following a rigid geometric partition. Second, the hierarchical layer structure solves the routing problem in a principled way. This lets the search make directional progress without requiring global knowledge. Third, the single ef_search parameter provides an intuitive control for the speed-recall tradeoff, making HNSW easy to tune in production. Fourth, the construction algorithm's use of the diversity heuristic produces graphs that remain searchable across a wide range of data distributions, including clustered data, uniform data, and everything in between.

HNSW has become the de facto standard for approximate nearest neighbor search in production vector databases because it delivers consistently high recall with low latency across a wide range of data distributions and dimensionalities. Like every algorithm, it has tradeoffs that affect design decisions.

The most significant limitation is memory consumption. HNSW requires storing the entire graph structure in RAM, including all vectors and their neighbor lists. For a billion-vector index with 768-dimensional embeddings, the vectors alone require about 3 TB of storage (at 4 bytes per float), and the graph adds substantial overhead on top of that. This makes pure HNSW impractical for very large-scale deployments without compression techniques like Product Quantization or dimensionality reduction.

In contrast, disk-based approaches like IVF indices can handle much larger collections because they only need to load a small subset of vectors into memory for each query. For truly massive collections (billions of vectors), the practical solution is to combine HNSW with quantization: use Product Quantization to compress each vector from full float32 precision to a fraction of its original size, then build the HNSW graph on the compressed representations. This reduces memory by 4x to 32x at the cost of a modest recall penalty. Modern vector databases like Faiss and Milvus support this combination natively.

Another limitation is the construction cost. Building an HNSW index is relatively slow compared to partition-based methods like IVF, because each insertion requires searching the existing graph to find neighbor candidates. The index also cannot be easily split across machines for distributed construction. HNSW indices are append-only in practice: while it is possible to add new vectors incrementally (a significant advantage over methods that require full rebuilds), deleting vectors is not natively supported in most implementations. Deleted nodes leave "holes" in the graph that degrade connectivity over time. This makes HNSW less suitable for collections that change frequently, unless you periodically rebuild the index.

Vector databases handle this in different ways. Qdrant marks deleted vectors as tombstones and periodically re-indexes to remove them. Weaviate rebuilds segments when deletions exceed a threshold. Pinecone's serverless tier handles it transparently in the background. Understanding your update patterns is important when choosing whether HNSW is right for your use case: if you have a mostly-static collection (like a corpus of product descriptions that changes monthly), HNSW is ideal. If your collection changes rapidly (like a news feed where articles expire and new ones are added hourly), a hybrid approach with more frequent rebuilds may be necessary.

For very high-dimensional embeddings (above 1024 dimensions), HNSW's performance can degrade. In these spaces, all vectors are roughly equidistant from any query (the curse of dimensionality), making it hard for the greedy search to make directional progress. Increasing $M$ helps, but at the cost of proportionally higher memory and construction time. Dimensionality reduction via PCA before indexing can mitigate this, though it introduces a small additional approximation. In practice, most sentence embedding models produce vectors in the 384 to 1536 dimensional range, where HNSW performs well without special treatment.

The tuning complexity is another practical concern. While HNSW has only three main parameters ($M$, ef_construction, ef_search), finding the right settings for a given dataset and latency budget requires experimentation. The optimal parameters depend on the data dimensionality, distribution, and the required recall level, and these interactions are not always intuitive. Many organizations run automated parameter sweeps (measuring recall vs. latency across a grid of configurations) to identify the Pareto-optimal point for their use case. The good news is that reasonable defaults ($M = 16$, ef_construction = 200, ef_search = 100) work well for most NLP applications without further tuning.

Despite these limitations, HNSW's impact on the field of vector search has been enormous. Before HNSW, practitioners had to choose between methods with known weaknesses: tree methods that fail in high dimensions, hash methods with difficult precision-recall tradeoffs, and quantization methods that require careful cluster count tuning. HNSW provided a single algorithm that works well across the board, with a clean interface and predictable tuning behavior.

The timing was also perfect. HNSW was introduced in 2016, just as dense retrieval and embedding-based search were beginning to gain traction in NLP. As BERT and its successors demonstrated the power of semantic embeddings, the demand for efficient vector search exploded. HNSW was ready: Hnswlib (the authors' reference C++ implementation) offered production-quality performance, FAISS quickly added HNSW support, and vector databases built on top of both. Today, virtually every major vector database, including Pinecone, Weaviate, Qdrant, Milvus, and Chroma, uses HNSW as either its primary or default index type. The algorithm that powers semantic search in RAG systems is a graph structure inspired by Milgram's letters and skip list pointers.

HNSW (Hierarchical Navigable Small World) is a graph-based approximate nearest neighbor algorithm that enables fast vector search by combining two key ideas:

• Navigable Small World graphs provide a structure where greedy routing efficiently finds nearby nodes using only local information. Dense local connections enable precise search, while long-range connections enable fast traversal across the space. The key challenge with a flat NSW graph is that greedy search can get trapped in local minima, especially as the graph grows.

• Hierarchical layering (inspired by skip lists) separates coarse navigation from fine-grained search. Upper layers contain sparse subsets of nodes with naturally long-range connections. This provides the global navigation that flat NSW graphs lack. The bottom layer contains all nodes with dense short-range connections for precise final search.

The algorithm's behavior is controlled by three parameters:

• $M$: connections per node (typically 16). Controls the density of the graph, affecting recall, memory, and speed.
• ef_construction: beam width during index building (typically 200). Higher values produce a better graph at the cost of slower construction. This is a one-time cost.
• ef_search: beam width during search (tunable at query time). Directly controls the speed-recall tradeoff without requiring a rebuild.

Search works in two phases: greedy descent through upper layers (fast, coarse navigation), then beam search on layer 0 (thorough, precise retrieval). This structure achieves $O(\log n)$ search complexity, making it practical for millions or billions of vectors. The neighbor selection diversity heuristic ensures that each node's connections cover multiple directions in the vector space, preventing local minima and improving navigability across the full graph.

HNSW's main limitations are its memory requirements (the full graph must fit in RAM) and the difficulty of handling deletions. For collections too large to fit in memory, partition-based indices like IVF and compression techniques like Product Quantization offer complementary solutions. In practice, many production systems combine these approaches, using HNSW as the search graph within each partition of a larger index. For most RAG applications with collections up to hundreds of millions of vectors, an in-memory HNSW index offers strong recall at low latency without excessive operational complexity.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about HNSW Index.