HNSW (Hierarchical Navigable Small World)

What is HNSW?

HNSW, short for Hierarchical Navigable Small World, is an algorithm for approximate nearest neighbor (ANN) search over high-dimensional vectors such as text or image embeddings. It was introduced by Yury Malkov and Dmitry Yashunin in their 2016 paper on efficient approximate nearest neighbor search using hierarchical navigable small world graphs. Rather than comparing a query against every stored vector, HNSW navigates a graph to reach close neighbors in a small number of hops.

It is called approximate because it trades a small, tunable amount of recall for a large speedup. Exact nearest neighbor search scales linearly with the number of vectors, which is too slow for millions or billions of items. HNSW achieves roughly logarithmic search complexity while returning the true nearest neighbors with high probability.

Because it offers strong recall, fast queries, and incremental insertion, HNSW is the default or primary index type in many vector databases and libraries, including FAISS, pgvector, Qdrant, Weaviate, and Milvus. It is the algorithm behind most production semantic search and RAG retrieval.

• A graph-based algorithm for approximate nearest neighbor search over high-dimensional vectors.
• Introduced by Malkov and Yashunin in 2016.
• Trades a small, tunable amount of recall for roughly logarithmic search time.
• Supports incremental insertion of new vectors without a full rebuild.
• The default index in many vector databases: FAISS, pgvector, Qdrant, Weaviate, Milvus.

How does the HNSW graph work?

HNSW combines two older ideas. The first is the probability skip list, where multiple layers of linked lists let a search take long jumps at the top and short, precise steps at the bottom. The second is the navigable small world graph, a proximity graph in which each vertex keeps a list of nearby neighbors, and search proceeds by greedy routing: repeatedly move to the neighbor closest to the query until no neighbor is closer.

HNSW arranges vectors into a hierarchy of layers. The top layer is sparse and contains only a few vertices connected by long-range links. Each lower layer contains more vertices and shorter-range links, and the base layer (layer 0) contains every vector. When a node is inserted, its maximum layer is chosen randomly with an exponentially decaying probability, so most nodes live only on the bottom layer.

A search starts at the single entry point on the top layer and greedily walks toward the query until it reaches a local minimum, then drops to the next layer down and repeats. The sparse upper layers act as an express network that carries the search most of the way across the space in a few hops, while the dense lower layers refine the result. This layered descent is what avoids the early-stopping problem of a single flat small-world graph.

• Built from two ideas: probability skip lists and navigable small world graphs.
• Search uses greedy routing: move to the closest neighbor until none is closer.
• Layers form a hierarchy: sparse long-range links on top, dense short-range at the base.
• A node's top layer is chosen randomly with exponentially decaying probability.
• Search descends from a top entry point through layers, refining at each level.

The three parameters: M, efConstruction, efSearch

M sets how many bidirectional links each node keeps per layer (the base layer typically allows up to 2M). A higher M produces a denser graph that reaches higher recall and handles harder, higher-dimensional data, but it increases memory use and build time. Memory grows substantially with M, so typical values sit in the range of about 12 to 48, with 16 a common default.

efConstruction controls how many candidate neighbors the builder considers when inserting each node. A larger value produces a higher-quality graph and better recall at query time, at the cost of slower index construction. It is a build-time setting and does not affect query latency directly. Common values run from around 100 to several hundred.

efSearch (sometimes just ef) sets the size of the dynamic candidate list explored during a query. It is the main runtime dial for the recall-versus-speed tradeoff: raising it explores more of the graph and lifts recall toward 100 percent, but increases query latency. It can be tuned per query, so you can run fast, lower-recall searches and slow, high-recall searches against the same index. efSearch must be at least as large as the number of results requested (k).

• M: links per node per layer; higher means better recall but more memory and build time (common default ~16).
• efConstruction: build-time candidate breadth; higher means a better graph and recall but slower indexing.
• efSearch: query-time candidate breadth; the main recall-versus-latency dial, tunable per query.
• Base layer typically allows up to 2M links per node.
• efSearch must be greater than or equal to k, the number of neighbors requested.

Code: building and querying an HNSW index

The example below uses the widely used hnswlib library to build an index, set the parameters described above, and query it. Note that efConstruction and M are set at build time, while ef (efSearch) is set before querying and can be changed at any time.

import hnswlib
import numpy as np

dim = 768
num_elements = 100_000
data = np.float32(np.random.random((num_elements, dim)))
ids = np.arange(num_elements)

# Cosine similarity index over 768-dim vectors
index = hnswlib.Index(space="cosine", dim=dim)

# Build-time parameters
index.init_index(max_elements=num_elements, ef_construction=200, M=16)
index.add_items(data, ids)

# Query-time parameter (recall vs. speed); must be >= k
index.set_ef(64)

query = np.float32(np.random.random((1, dim)))
labels, distances = index.knn_query(query, k=10)
print(labels, distances)

# Raise ef for higher recall on a harder query
index.set_ef(256)
labels, distances = index.knn_query(query, k=10)

Strengths, costs, and when to use it

HNSW's strengths are high recall at low query latency, support for incremental inserts, and good behavior on high-dimensional data, which is why it backs so much production semantic search. The main cost is memory: the graph stores many links per vector and is typically held in RAM, so a billion-scale index can be expensive. Build time also grows with M and efConstruction.

For very large or memory-constrained corpora, HNSW is often combined with quantization (for example product quantization or scalar quantization) to shrink vector storage, or with disk-based variants that keep part of the graph off RAM. A common pattern is HNSW for the in-memory candidate stage followed by a reranking step for final precision.

Choose HNSW when you need fast, high-recall vector search and can afford the memory, which describes most RAG and semantic search workloads. If memory is the binding constraint and you can tolerate longer queries or lower recall, alternatives such as IVF-based indexes or disk-first ANN may fit better.

• Strengths: high recall, low latency, incremental inserts, good on high dimensions.
• Main cost is RAM, since the link-heavy graph is usually held in memory.
• Pair with quantization or disk-based variants for very large or memory-tight corpora.
• Often used as the candidate stage before a reranking step for final precision.
• Use it when you need fast, high-recall vector search and can afford the memory.