HNSW

HNSW — Hierarchical Navigable Small World — is an index structure for approximate nearest-neighbour search in which vectors are the nodes of a graph, each linked to some of its near neighbours, and the graph is built in stacked layers so that a search can start with long jumps in a sparse top layer and finish with short steps in a dense bottom one.

The name states the construction. Small world is the property that any node can be reached from any other in few hops, which is what makes a graph navigable by greedy walking rather than by exhaustive comparison. Hierarchical is the layering: the bottom layer holds every vector, and each layer above holds a random sample of the one below, so the upper layers act as an express network over the lower ones.

A search enters at a single node in the top layer and repeatedly moves to whichever neighbour is closer to the query, stopping when no neighbour improves on the current node. That node becomes the entry point for the layer below, and the walk repeats at finer resolution. In the bottom layer the walk keeps a list of the best candidates found rather than a single node, and that list is the result.

Nothing in the procedure guarantees the true nearest neighbours are found. A greedy walk can settle in a region that is locally best and globally wrong, and the layering reduces but does not remove that possibility. HNSW is therefore an approximate method by construction, not an exact method with a speed setting.

The structure is a graph, not a partition. It never divides the vector space into regions and never assigns a vector to a cluster; there is no notion of the part of the index a query belongs to.

In practice

HNSW appears as one of the index types a vector store offers, usually the default for in-memory search. Where a product exposes a choice of index, HNSW is the option contrasted with cluster-based and flat alternatives.

Its behaviour is governed by two kinds of parameter, set at different times. One controls how many links each node keeps and how hard the builder works to choose them; it is fixed when the index is built and changing it requires rebuilding. The other controls how many candidates the walk holds at query time, and can be varied per query. The first buys quality permanently at the cost of memory and build time; the second buys quality per search at the cost of latency. Implementations commonly call these M and ef, with the build-time effort parameter distinguished as efConstruction, though the names are not standardised.

The structure lives in memory, because a graph walk follows links to arbitrary locations and cannot be read in large sequential blocks. Memory consumption is the vectors plus the links, and the link overhead grows with the number of links per node. Disk-resident variants exist and change the traversal to compensate.

Insertion is incremental. A new vector is placed in a layer chosen at random, connected by running the same search procedure to find its neighbours, and linked to them. That makes the index buildable one vector at a time, without a separate training pass over a sample of the data.

Deletion is the awkward operation. Removing a node would break the links other nodes depend on for connectivity, so implementations commonly mark the vector as deleted, exclude it from results, and continue traversing through it. The space and the traversal cost persist until the structure is rebuilt. See upsert.

Commonly confused with

Approximate nearest neighbour. The problem and the class of methods; HNSW is one method in that class. Material that says “the index uses ANN” has named the goal, not the structure. Cluster-based and hash-based indexes are equally ANN and behave differently. See approximate nearest neighbour.

Vector index. The general category. HNSW is a particular implementation of a vector index, and a vector index need not be HNSW. The words are used interchangeably in writing about systems where HNSW happens to be the default. See vector index.

IVF. A cluster-based alternative: the space is partitioned, centroids are computed from a sample, and a query is compared against vectors in the nearest few partitions. It requires a training pass, which HNSW does not, and it partitions rather than links. The two are the usual pair of choices, not variants of one another.

Small-world network. The general graph property HNSW’s name borrows, studied long before vector search and describing many naturally occurring networks. HNSW builds a graph with that property deliberately; the property itself is not a retrieval method.

A library. Several open-source implementations of the algorithm exist and their names are sometimes used as though they named the structure. The structure is the algorithm; an implementation is one realisation of it, with its own parameter names, memory layout, and deletion behaviour.

Usage notes

The acronym is far more common than the expansion. Most writing uses “HNSW” without ever spelling it out, and the expanded form appears mainly in the first sentence of documentation.

“HNSW” is often used as a synonym for vector search itself, particularly in material comparing a vector store to a keyword engine. Such a comparison is usually about dense retrieval in general rather than about this structure. See dense retrieval.

Recall figures attributed to HNSW are properties of a configuration, not of the algorithm. The same structure over the same vectors returns different results at different query-time effort settings, so a quoted recall number is meaningful only alongside the parameters and the collection that produced it.

Parameter names vary and their meanings are not always identical across implementations. A value carried from one library to another may not describe the same quantity, and defaults differ.

HNSW is frequently combined with compression. Storing quantised vectors in the graph reduces memory and changes the distances the walk sees, so the combination has its own recall behaviour distinct from either part. See quantisation.

See also

Approximate nearest neighbour · Vector index · Quantisation · Cosine similarity · Top-k