Definition
Hierarchical Navigable Small World (HNSW) is a graph-based index for approximate nearest neighbor search. It organizes stored vectors into layers of connected nodes. Every vector appears in the bottom layer. Progressively fewer appear in the layers above it. Connections are chosen using distances between vectors.
To answer a query, HNSW starts in a sparse upper layer and follows connections toward vectors closer to the query. It then moves down through denser layers and searches a set of candidates near the bottom. That route can avoid comparing the query with every stored vector.
HNSW organizes the search. It does not create embeddings or choose a distance measure. The index must be built and queried with the same measure.
Simple example
Suppose a documentation search system stores one million passage embeddings. For a new question, an exact search could calculate the distance to all one million vectors. An HNSW index uses the upper layers to reach a promising part of the graph, then examines nearby candidates in the bottom layer. It can return close passages after examining far fewer vectors, though it might miss a passage that exact search would rank in the top five.
Why it matters
HNSW can reduce query work when exact vector search becomes too slow for a large collection. The graph also takes space and time to build. For a RAG application, compare its results with exact search on representative queries. A missed passage can remove evidence the answer needs.
One important nuance
The upper layers guide the search. They do not settle the final ranking. At the bottom layer, HNSW explores multiple candidates rather than stopping at the first promising node. Wider exploration can find more of the exact nearest neighbors but takes more query work. Measure that tradeoff on your own data.