HNSW explained: how a hierarchical navigable small world graph works

In this article

1. Before you start
2. Why interviewers ask this
3. HNSW from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is part of the embeddings and vector search learning path, and it builds on the transformer overview only for where embeddings come from.

Why interviewers ask this

A vector search question rarely stops at "use a vector database." The follow-up is how the index finds neighbors without comparing the query to every stored vector, and HNSW is one of the indexes many vector databases offer. A design round on retrieval or recommendations often reaches it.

A weak answer says "it is a graph, so it is fast." A strong answer explains why the layers make the search shortcut-friendly, names the three settings (M, efConstruction and efSearch) and says which one costs build time, which costs query time and which costs memory. A Staff-level answer adds the failure modes: memory overhead, no deletion in some libraries, and recall that depends on the data.

HNSW from first principles

Proximity graph

A proximity graph is a graph whose nodes are stored vectors and whose edges join vectors that are close to each other, so a search can walk from node to node toward a query instead of scanning every vector.

efSearch

efSearch is the size of the candidate list an HNSW search keeps while it explores the bottom layer; a larger list finds more of the true nearest neighbors and takes longer, and it can be changed for each query.

efConstruction

efConstruction is the size of the candidate list used while the index is being built; a larger list builds a better graph and takes longer to index, and it is not a query-time setting, because query cost is set mainly by efSearch.

In plain words

Picture finding a street address in a country you have never visited. You do not read every street name. You take a motorway to the right region, a main road to the right town, then local streets to the door. Each level has fewer places and longer jumps than the one below.

The analogy breaks in one place: HNSW has no map. The graph is built from the data and the "roads" are links between similar vectors, so the search is a guess that is usually right, not a certainty.

In one precise sentence, Hierarchical Navigable Small World (HNSW), an extension of the Navigable Small World (NSW) graph, builds a multi-layer structure from a hierarchy of proximity graphs. The layers cover nested subsets of the stored elements, and no separate coarse search structure is needed.

What do "navigable" and "small world" mean?

A small-world graph is a graph in which any node can be reached from any other in few hops, because it mixes short links to near neighbors with a few long links that jump across the space. Navigable means a greedy search can find the way using only local information: at each node it looks at the neighbors, moves to the one closest to the query, and needs no map of the whole graph.

The NSW graph that HNSW extends is a single flat graph of this kind. Its short and long links sit together on one level, so a search needs more hops on large data. The paper's abstract says HNSW separates links by their characteristic distance scales and puts them on different layers. It adds that starting from the upper layer with this scale separation boosts performance compared to NSW and allows a logarithmic complexity scaling.

Step 1: Layers hold nested subsets of the points

Every vector sits on layer 0, the bottom layer. Each vector also gets a top layer drawn at random, and the paper's abstract says that layer is chosen with an exponentially decaying probability, so few vectors reach the upper layers. The layers are not separate indexes: the points of layer 1 are a random subset of layer 0, and layer 2 is a subset of layer 1.

Take the common choice of scale 1 divided by the natural logarithm of M, which is an assumption of this example. The share of points on layer l or higher is then M to the power minus l. For M of 16 and one million points, the expected counts are 1,000,000 on layer 0, 62,500 on layer 1, about 3,906 on layer 2, about 244 on layer 3 and about 15 on layer 4, and about one point reaches layer 5, so the top level is about 5 (six layers counting layer 0).¹ This is the same idea as a skip list, a resemblance the authors point out.

Step 2: A search descends layer by layer

A search starts on the top layer at a fixed entry point. It looks at the neighbors of its current node, moves to the one closest to the query, and repeats until no neighbor is closer. That node is a local best, and the search drops down one layer at the same node and does it again.

Input: a query vector. Output: a good starting node on layer 0. A query starts on the sparse top layer and hops greedily toward the query. Because the upper layers are sparse, each hop there covers a long distance, and the number of hops grows slowly with the number of stored points. The authors report that starting from the upper layer gives a logarithmic complexity scaling, which beats a flat graph on large data. You now know why the layers exist: they cut the distance to the right neighborhood before the careful search begins.

Step 3: efSearch widens the search on the bottom layer

On layer 0 the search stops being purely greedy. It keeps a list of the best candidates found so far, whose size is efSearch, and it keeps expanding the closest unexplored candidate until no candidate can improve the list. Then it returns the nearest k from the list.

Input: the entry node and a query. Output: k neighbors, approximately. On layer 0 a candidate list of size efSearch widens the search before it returns the nearest points. A bigger efSearch explores more of the neighborhood, so recall rises. Recall is the share of the true nearest neighbors that the search returns. The cost is time: Azure AI Search's reference says raising efSearch may improve results at the expense of slower search, and arXiv 2405.17813 says a higher efSearch increases recall at the cost of latency. The list must hold at least k candidates, so implementations typically use the larger of efSearch and k. Because efSearch is a query-time setting, you can change it without rebuilding anything.

Step 4: Building the graph links each new point to up to M neighbors

Inserting a new point links it to up to M neighbors. To insert a point, the index draws its top layer as in Step 1, searches down from the top to find close points, and links the point to neighbors on each layer from its top layer down to layer 0. The setting M is the number of bidirectional links created for every new element during construction (Azure reference). The bottom layer typically allows twice as many links, 2 times M (Faiss index factory).

The search done during insertion uses a candidate list of size efConstruction. A larger one improves index quality at the cost of indexing time. It is not a query-time setting; query cost is set mainly by efSearch. The authors also add a heuristic for choosing which neighbors to keep, which the abstract says significantly increases performance at high recall and on highly clustered data. You now have the whole index: nested layers, a greedy descent, a wide final search and links chosen at build time.

1 · Nested layers2 · Greedy descent3 · Widen on layer 04 · Insert a pointReplay

Step-by-step description

1. Higher layers hold random subsets.
2. Hop toward the query, then drop a layer.
3. efSearch sets the candidate list size.
4. A new point links to up to M neighbors.

• Every point sits on layer 0 and a random subset sits on each higher layer.
• A query starts on the sparse top layer and hops greedily toward the query.
• On layer 0 a candidate list of size efSearch widens the search before it returns the nearest points.
• Inserting a new point links it to up to M neighbors.

Worked example

Take one million vectors with 768 numbers each, stored as 4-byte floats, in a Faiss HNSW index with M of 16. The Faiss guidelines give the memory as 4 times d plus 8 times M bytes per vector, where d is the number of dimensions. That is 3,072 bytes of vector plus 128 bytes of links, 3,200 bytes per vector, or 3.2 gigabytes for the million.¹ The links add about 4% to the raw vectors.¹ The formula counts only layer-0 links, so links on the upper layers add a little more. A brute-force scan would instead cost 768,000,000 multiply-adds per query, since it compares the query to every vector.¹

Links are a larger share when vectors are short. The Faiss index factory page says that for an index with M of 32 (the Faiss index-factory string for it ends in the number 32, which is M) the bottom layer uses 32 times 2 links, or 256 bytes per vector, and calls the overhead quite significant. At 128 numbers per vector the raw vector is 512 bytes, so the links add half again as much.¹

The rows come from the Faiss benchmark of one million Scale-Invariant Feature Transform (SIFT) image descriptors, run with 20 threads. It is an old benchmark on a single dataset, so read the shape, not the values: recall climbs steeply at first, then each doubling adds less.

Text description of the diagram

• Recall at 1 rises from 0.874 at efSearch 16 to 0.992 at efSearch 256.
• Query latency rises about 9.5 times over that range.

Trade-offs and edge cases

HNSW is fast and accurate, and it pays in memory. The Faiss guidelines say that with plenty of memory or a small dataset it is the best option, a very fast and accurate index, and that it needs no training. The links come on top of the full vectors, which is why it is heavier than compressed methods.

Flat search is exact but scans everything. An inverted file is an index that splits the vectors into clusters and searches only a few of them, so it needs training. HNSW needs no training but stores links beside every vector.

Text description of the diagram

• Flat search is exact but scans every vector.
• HNSW needs no training and stores links beside every full vector.

Edge cases to name in an interview:

• Approximate answers. HNSW is not exact search. Recall depends on efSearch, and a 2024 study examines how the data, the insertion order and intrinsic dimensionality change recall; it reports that inserting the data in descending local intrinsic dimensionality (LID) order raised average recall by 2.6 percentage points in hnswlib and 6.2 in Faiss at efSearch 10 (arXiv 2405.17813).
• Deletion. Faiss does not support removing vectors from an HNSW index. Other engines handle deletes differently, so check the documentation of the one you use.
• Diminishing returns. Raising M or the two ef settings eventually stops helping, and the Faiss guidelines give a range of 4 to 64 for M, where higher is more accurate and uses more memory.
• Filters and ranking. Combining the graph with a metadata condition is its own problem, covered in metadata filtering, and HNSW is usually the first stage before a reranker or a hybrid search merge.
• Defaults differ. Default settings vary by engine, so state your own values and justify them.

The vector indexing page places HNSW among the other index families, and the two-tower model page shows how the vectors that fill such an index are trained.

How to answer it in an interview

The spoken structure: say what it is, walk the descent, name the three settings and what each costs, then name the memory and recall caveats.

Common mistakes

• "HNSW gives exact results." (wrong) It is approximate. (right) "It returns most of the true neighbors, and efSearch sets how many."
• "A higher efConstruction slows queries." (wrong) It slows indexing, and query cost is set mainly by efSearch. (right) "efConstruction is paid once at build; efSearch is paid on every query."
• "The layers are separate indexes." (wrong) They are nested subsets. (right) "Every point is on layer 0; higher layers hold random subsets."
• "Raising efSearch keeps improving recall." (wrong) Gains shrink as latency grows. (right) "I pick the smallest efSearch that meets the recall target."
• "HNSW saves memory." (wrong) It stores full vectors plus links. (right) "It is fast but memory-heavy; for tight memory I compare compressed indexes."

Follow-up questions

What is the difference between efSearch and efConstruction?

efConstruction is the candidate list size while building, so it affects index quality and build time, and it is not a query-time setting. efSearch is the candidate list size at query time, so it trades recall against latency and can change per query.

What does M control in HNSW?

M is the number of bidirectional links created for every new element. A larger M is more accurate and uses more memory, and the bottom layer typically uses twice that many links, as the Faiss index factory page describes.

Is HNSW exact search?

No. It is approximate nearest-neighbor search, so recall is below 100% and depends on efSearch and on the data.

Why does HNSW use so much memory?

It keeps every full vector and adds links for each one. In Faiss the cost is 4 times d plus 8 times M bytes per vector, so the overhead is larger for short vectors.

Can you delete vectors from an HNSW index?

In Faiss, removal is not supported. Other engines differ, so say which library you mean and check its documentation.

When would you choose HNSW over an inverted-file index?

Choose HNSW when memory is plentiful or the dataset is small and you want high recall at low latency without a training step. Consider an inverted file when memory is tight and a training pass is acceptable. The vector database overview covers the wider design.

Sources

1. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv 1603.09320) — arXiv (Malkov and Yashunin; IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020), 14 Aug 2018
2. Guidelines to choose an index — Meta, facebookresearch/faiss wiki (accessed 2026-10-26), 26 Oct 2026
3. The index factory — Meta, facebookresearch/faiss wiki (accessed 2026-10-26), 26 Oct 2026
4. Indexing 1M vectors — Meta, facebookresearch/faiss wiki (accessed 2026-10-26), 26 Oct 2026
5. HnswParameters interface — Microsoft Learn, Azure AI Search SDK (accessed 2026-10-26), 26 Oct 2026
6. The Impacts of Data, Ordering, and Intrinsic Dimensionality on Recall in HNSW (arXiv 2405.17813) — arXiv, 28 May 2024