HNSW: Vector Search with a Graph Highway System

Why it exists

The core problem is finding similar items in a dataset of millions or billions of vectors, like text embeddings or image features. A linear scan, comparing a query vector to every other vector, is computationally impossible for real-time applications. We need a way to find 'good enough' matches very quickly.

The mental model

Imagine finding a specific address in a huge, unfamiliar city. You wouldn't drive down every single street. You'd use a highway to get to the right district, then an arterial road to get to the neighborhood, and finally a local street for the last block. HNSW builds this exact structure for data. The top layers are 'highways' with long-distance links between distant data points, while the bottom layer is the dense 'local streets' connecting every point to its immediate neighbors.

How it works

HNSW organizes vectors into a series of graph layers. The top layer is very sparse, containing only a few points with long-range connections. Each layer below it becomes progressively denser, adding more points and more connections. A search starts at an entry point in the top 'highway' layer and greedily moves from node to node, always getting closer to the query vector. When it can't get any closer on the current layer, it drops down to the next, denser layer to refine its path. This process repeats until it reaches the bottom layer, where it performs a final, localized search.

When to use it

Use HNSW when you need extremely fast similarity search on high-dimensional data and can accept approximate results. It's the de facto standard for vector databases powering semantic search, recommendation engines, image retrieval, and anomaly detection. It excels when query latency is critical.

When not to use it

Do not use HNSW if your application requires the guaranteed, provably correct nearest neighbor for every query. The 'approximate' nature is a feature for speed, not a bug. Also, while HNSW supports insertions, its performance can degrade with frequent updates or deletions, as this can fragment the graph structure over time.

One canonical example

A user searches an e-commerce site for a 'blue floral dress'. The query is converted to a vector. HNSW searches a database of millions of product vectors. It starts on the top layer, quickly jumping from 'clothing' to 'dresses'. It then drops to a lower layer to navigate from 'dresses' to 'floral dresses', and finally to the bottom layer to find the specific vectors for blue floral dresses that are closest to the query vector's style and pattern, all in milliseconds.