What is HNSW?
Also called Hierarchical Navigable Small World.
HNSW, short for Hierarchical Navigable Small World, is a graph based algorithm for approximate nearest neighbor search. It stores vectors as nodes in a layered proximity graph and answers a query by walking from a coarse top layer down to a dense bottom layer, moving toward closer neighbors at each step. It is the default index in many vector databases.
The structure is built from several graph layers. The top layer holds a small random sample of vectors with long range links, and each layer below holds more vectors with shorter links, until the bottom layer contains everything. A search enters at the top, greedily follows edges that reduce distance to the query, drops a layer when no neighbor is closer, and repeats until it settles in the bottom layer.
Two build parameters dominate behavior. One controls how many links each node keeps, which sets memory use and graph quality; the other controls how wide the candidate list is during construction, which sets build time and accuracy. At query time a separate search width parameter decides how many candidates are kept in flight, giving a direct dial between latency and recall without rebuilding the index.
HNSW is popular because it delivers strong recall at low latency and supports incremental inserts, so new documents can join without a full rebuild. The main costs are memory, since the graph and the full vectors usually sit in RAM, and deletions, which many implementations handle by marking nodes as removed and reclaiming space only during a later compaction.
The algorithm was published by Malkov and Yashunin in 2016 and has open implementations that most vector stores wrap or reimplement. Alternatives such as inverted file indexes with product quantization, or disk resident graph indexes, are often preferred when a collection is too large to hold in memory or when write throughput matters more than query latency.
Key points
- Layered proximity graph searched from coarse to fine
- Query time search width dials latency against recall
- Supports incremental inserts without full rebuilds
- Memory hungry because the graph usually stays in RAM
- Deletions are typically soft until compaction
In practice
A team indexes two million product description vectors with HNSW, giving each node thirty-two links. At a search width of forty, queries return in about eight milliseconds with roughly ninety-five percent recall. Raising the search width to two hundred lifts recall above ninety-nine percent and pushes latency to about thirty milliseconds. Nothing is rebuilt; only the query parameter changes, so the team tunes it per endpoint.