HNSW Index: Architecture for Fast Vector Search › HNSW Parameters

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.