Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path →
HNSW,
explained.
Every vector search — every "find me the 10 most similar" — hides a scaling problem: comparing a query against a billion vectors one by one is hopeless. HNSW is the data structure that makes it fast, and it's one of the most widely used indexes in vector databases. Its idea is beautifully low-tech: wire the points into a graph, then walk toward the query, always stepping to the closest neighbor. Add a skip-list-style hierarchy on top and the walk becomes logarithmic. It's "six degrees of separation" turned into an algorithm. Here's the walk, and the pyramid that speeds it up.
What changes against compression: the search stops scanning
Rung 4 makes each vector cheap to score. It does not reduce how many you score — a compressed exhaustive scan is still a scan, linear in the size of the collection. This rung attacks the other factor: look at a logarithmic number of candidates instead of all of them.
The change is to build a graph over the vectors and walk it. Connect each vector to some of its near neighbours, start anywhere, and repeatedly hop to whichever neighbour is closer to the query until no neighbour improves. That greedy descent works because the graph is built to be navigable: it has enough short links to be locally accurate and enough long ones to cross the space quickly, which is the small-world property.
Greedy descent on one graph still takes many hops to travel a long way, so the structure is hierarchical. Nodes are assigned to levels by a decaying random rule — most vectors live only at the bottom, a few reach high layers — and search starts at the sparse top, where each hop covers a large distance, then descends, each layer refining the entry point for the next. This is the skip list's idea applied to a metric space, and it turns the traversal into logarithmic work. That both layer assignment and long-range connectivity come from randomness is what makes it practical: there is no global structure to compute, so the index is built incrementally by inserting one vector at a time.
Walk to the answer
The problem is approximate nearest neighbor (ANN) search: given a query vector, find the closest stored vectors among millions or billions. Exact search means comparing the query to every point — O(N) per query, which collapses at scale. The approximate relaxation trades a tiny bit of accuracy for an enormous speedup, and HNSW is the method that made that trade practical enough to power the whole retrieval stack.
HNSW's core move is to treat search as navigation. Connect the points into a graph — each point links to some near others — then, to answer a query, start somewhere and greedily hop to whichever neighbor is closest to the query, over and over, until no neighbor is any closer. You've walked to the query's neighborhood. The genius is entirely in which graph makes that walk both fast and accurate.
Wire points into a navigable small-world graph, greedily hop to the neighbor closest to the query, and stack the graph into skip-list-style layers so the search runs in O(log N).
Navigable small worlds
Greedy hopping only works if the graph is built right. A graph of just short local links is like a country road network with no highways: you'll reach anywhere eventually, but slowly, one town at a time. A small-world graph adds a few long-range links — highways — so you can cross the space in a handful of jumps, then use local links to refine. That mix of long and short edges is exactly what makes a graph navigable by greedy search.
The danger of pure greedy search is getting stuck in a local minimum — a node whose neighbors are all farther from the query than it is, even though a better point exists elsewhere. Good graph construction (enough neighbors, well-chosen, with diversity) makes such traps rare, so the greedy walk usually lands on the true nearest neighbor or something very close. Approximate, but reliably so — and you can dial the accuracy up by keeping a small candidate list during search instead of a single current node.
The skip-list trick
A single flat small-world graph is good, but HNSW's leap is to layer it, borrowing the idea of a skip list. Picture a pyramid of graphs: the bottom layer holds every point with dense local links; each layer above holds an exponentially smaller sample of points with longer-range links. Search runs top-down — greedily approach the query in the sparse top layer, then drop a layer and refine, repeating to the bottom.
The layers are built by assigning each inserted node a maximum level from an exponential distribution: most nodes stay at level 0, a geometrically shrinking fraction reach each higher level. That produces the pyramid automatically. The top layers act as an express lane that gets you into the right region cheaply; the bottom layer does the fine-grained work. This is the "hierarchical" in HNSW, and it's what turns a good graph search into a logarithmic one.
Why it's log N
A node's level is sampled from an exponential rule, where u is uniform in (0,1) and mL a normalization constant:
So a fraction of nodes sit only at level 0, fewer reach level 1, fewer still level 2 — a pyramid. The highest level present among N nodes therefore grows like ln(N).
That logarithmic height is the whole payoff. The number of layers is about ln(N)·mL, and greedy search spends a bounded number of hops per layer, so the total cost is:
Squaring the dataset only doubles the number of layers, because ln(N²) = 2·ln(N) — going from a thousand points to a million barely doubles the work. That is why HNSW stays fast as collections grow into the billions. The runnable version below greedily walks a small-world graph to the nearest node and shows the layer count growing logarithmically.
How HNSW inserts and searches, step by step
HNSW (Malkov and Yashunin; posted to arXiv in 2016, published in IEEE TPAMI later) is defined by four short algorithms — insert, search one layer, select neighbours, and k-NN search — and six parameters: M, Mmax, Mmax0, efConstruction, ef and the level multiplier mL. Here they are in the order a new vector meets them.
- Draw a level. A new element q gets a top level l = ⌊−ln(U) · mL⌋ with U uniform on (0, 1). The recommended mL = 1/ln M makes the chance of reaching each next layer 1/M, the same promotion rule as a skip list with p = 1/M.
- Descend greedily to that level. Starting from the global entry point on the top layer L, run the layer search with ef = 1 — pure greedy, one current node — on every layer above l, and use the closest node found as the entry point one layer down.
- Search wider where it will link. On each layer from min(L, l) down to 0, run the layer search with a candidate list of size efConstruction. It is a best-first search: keep a priority queue of candidates and a result list W of the best efConstruction found so far, expand the closest unexpanded candidate, add any unvisited neighbour that beats the worst member of W, and stop when the closest remaining candidate is farther than the worst result.
- Select neighbours with the heuristic. From those candidates choose M to link. The simple rule takes the M closest. The paper's heuristic walks the candidates from nearest outward and keeps one only if it is closer to q than to every neighbour already kept, optionally topping up with discarded candidates if slots remain. A candidate that sits behind an existing neighbour is skipped, so links fan out in different directions and keep the bridges between clusters that the closest-M rule drops.
- Link both ways and prune. Connect q to its chosen neighbours and each of them back to q. If a neighbour now exceeds its cap — Mmax on upper layers, Mmax0 on layer 0, recommended at 2M — its list is shrunk with the same selection rule. If l is above the current top layer, q becomes the new entry point.
- Answer a query. k-NN search repeats the greedy descent from the top layer down to layer 1, then runs one layer search on layer 0 with candidate list size ef, which must be at least k, and returns the k nearest members of W. Raising ef raises recall and cost smoothly, and it is the one parameter that can change without rebuilding the index.
The parameters, and the paper's advice
M, the links made per insertion, is the main memory and quality dial; the paper's reasonable range is 5 to 48, with small values better for low recall or low-dimensional data and large values for high recall or high-dimensional data. Mmax0 = 2M matters: setting the layer-0 cap to M degraded performance at high recall. efConstruction trades build time for graph quality; once the construction-time search is close to exact, raising it buys little. mL = 1/ln M was close to optimal, and mL = 0 gives a single flat layer, which with the layer-0 cap also lifted is the authors' earlier NSW graph. Because each insertion only reads and edits the graph near the new element, construction runs in parallel threads with locks, and total build cost grows about as N log N.
The HNSW level distribution and neighbour rule
P(l ≥ k) = e−k / mL = M^−k when mL = 1 / ln M
expected top layer ≈ logM N, mean upper-layer memberships per element = 1 / (M − 1)
keep candidate e ⟺ d(e, q) < d(e, r) for every already-kept neighbour r
mL— the level multiplier: larger values make more, sparser layers; 0 collapses everything into one layer.M— links per insertion; with mL = 1/ln M the promotion probability per layer is 1/M.N— the number of elements in the index.d(·, ·)— any distance function. The method only evaluates distances, so it is a general metric-space index, not just a vector index.
The 1/(M − 1) line, which follows from summing M^−k over k ≥ 1, shows where the memory goes: with M = 16 an element sits in an upper layer only about 0.07 times on average, so nearly all link storage is on layer 0, where the cap is 2M = 32. At the extremes: mL → 0 gives a single layer, which with an unbounded layer-0 cap is the earlier NSW graph, whose greedy search scales polylogarithmically; a very large mL stacks many nearly identical layers that cost memory without shortening the walk. The neighbour rule at its extreme keeps a single link into a dense cluster and spends the rest on other directions — which is why it helps most on clustered data.
What HNSW was benchmarked against, and what it showed
The paper compared HNSW with its predecessor NSW and with the open-source methods of the time — FLANN and Annoy (tree-based), FALCONN (locality-sensitive hashing) and a VP-tree — measuring recall against query time on random vectors of controlled dimension and on public sets including SIFT, GloVe word vectors and MNIST, partly through the ann-benchmarks suite. The journal version adds a comparison with product-quantization indexes from FAISS on 200 million SIFT vectors. The results are curves rather than single numbers, so the table records the settings tested and the direction of each effect.
| Comparison | Settings | Reported effect |
|---|---|---|
| Hierarchy vs flat NSW | mL = 1/ln M vs mL = 0 | Large speed-up on low-dimensional data, smaller on high-dimensional data |
| Neighbour selection | heuristic vs closest M | Large gain on clustered and low-dimensional data, small at high dimension |
| Layer-0 degree cap | 2M vs M | 2M better; M degrades performance at high recall |
| Connectivity | M from 5 to 48 | Small M for low recall or low dimension, large M for high recall or high dimension |
| Other open-source methods | FLANN, Annoy, FALCONN, VP-tree | HNSW faster at equal recall on the sets tested |
| Product-quantization indexes | 200M SIFT vectors | HNSW faster at high recall but needs far more memory |
Two negative results sit in the paper itself. The hierarchy's payoff shrinks as dimensionality grows: the authors present it chiefly as the fix for low-dimensional and clustered data, where NSW's polylogarithmic scaling hurt most. And the logarithmic complexity is argued under assumptions about the data, roughly a low intrinsic dimension, not proved for arbitrary sets. Later work has pressed on the first point: a 2024 study by Munyampirwa, Lakshman and Coleman, titled Down with the Hierarchy, reported that on high-dimensional benchmarks a flat graph matched HNSW, arguing that well-connected hub nodes already play the role of the upper layers.
What the authors admit, and what happened next
The costs are structural and well known. The graph's links are memory on top of the vectors, and at high recall settings that overhead is a substantial fraction of the index — which is exactly why this rung and rung 4 are usually deployed together rather than as alternatives. Deletion is awkward, because removing a node can disconnect paths that other searches depend on, so real systems tombstone and periodically rebuild. And results are approximate, with recall traded against how many candidates the walk keeps alive.
The complexity claim rests on assumptions about the data's intrinsic dimensionality; on adversarial or very high-dimensional distributions the guarantees weaken. In practice it performs well enough that this is a footnote rather than a caveat.
How it held up: it is the most common choice. Most vector databases on the market implement this graph, often alongside other index types, and the practical tuning knobs it exposes — connectivity, build-time and search-time candidate widths — are the ones an engineer actually turns. Read rungs 4 and 5 as one answer split in two: compression solves memory, the graph solves candidate count, and you need both because they are different problems.
Greedy walk, logarithmic layers
HNSW is two ideas you can run. Greedy search walks a navigable graph — from an entry node, always hop to the neighbor closest to the query, stopping when none is closer — and on a well-connected graph it lands on the true nearest point. The hierarchy assigns each node a level from an exponential rule, so a rarer draw reaches a higher layer while most nodes stay at level 0, and the number of layers grows like ln(N): squaring the dataset only doubles the layers. That log-height is why search is O(log N) instead of O(N). Change the query or the dataset size and watch the walk and the layer count move.
Write the body of greedy_search. Everything else in the file is
already written; this is the function the paper is about. Press ▶ Run to check it against
the 5 assertions below — they start red.
- Greedy search finds the exact nearest node on a navigable graph
- Greedy search takes hops when the entry is far from the query
- HNSW levels are exponential: a rarer (smaller) draw maps to a higher level
- Most nodes land on the bottom layer (level 0)
- The number of layers grows logarithmically (squaring N doubles it)
The vector-DB index
HNSW is the quiet engine under modern retrieval. When dense retrieval encodes passages into vectors, something has to find the nearest ones fast — and that something is almost always HNSW. It's a standard index in vector databases and libraries like FAISS, Qdrant, Weaviate, and Milvus (each of which also offers other index types), and therefore the layer that makes retrieval-augmented generation fast enough to feel instant. Every "search your docs" feature you've used likely walked an HNSW graph.
It also composes with the other retrieval ideas. To cut HNSW's memory appetite you can store quantized vectors in the graph, trading a little accuracy for a lot of RAM. Its elegance is that a decades-old intuition — small-world networks, six degrees of separation — plus a skip list's logarithmic staircase, together solve a billion-scale problem with a greedy walk. Not a neural network in sight, yet it's indispensable infrastructure for the neural systems built on top of it.
HNSW's speed is bought with memory: it keeps many neighbor links per node and works best fully in RAM. That's the main reason production systems pair it with quantization or disk-based variants when collections outgrow memory.
Questions people ask about HNSW
What do M, efConstruction and ef control in HNSW?
M is the number of links a new element makes on each layer it joins, so it sets most of the index's memory and how well connected the graph is; the HNSW paper suggests 5 to 48, with larger values for high-dimensional data or high recall. The layer-0 cap, Mmax0, is recommended at 2M, and upper layers cap at M. efConstruction is the size of the candidate list used while inserting: larger values find better neighbours and build a better graph, at the cost of slower construction. ef is the candidate list size on the bottom layer at query time and must be at least k; raising it increases recall and latency smoothly, and it is the one knob you can change without rebuilding the index. The level multiplier mL is normally left at 1/ln M.
How does the HNSW neighbor selection heuristic work?
When a new element q is inserted, the search on each layer returns candidate neighbours. The simple rule links the M closest. The heuristic in the HNSW paper instead takes the candidates in order of distance and keeps one only if it is closer to q than to every neighbour already kept; a candidate nearer an existing neighbour is skipped, and the skipped ones can optionally fill any slots left over. The effect is that links spread in different directions instead of piling into the nearest dense cluster, which preserves the bridges between clusters that greedy search depends on. The paper reports the biggest gains on clustered and low-dimensional data. A relaxed form of the same rule, with a slack factor, is the pruning step of the later DiskANN graph index.
Should I use HNSW or an IVF index?
They solve different halves of the problem and are often combined. HNSW gives an excellent recall-versus-latency trade-off for collections that fit in RAM with their full vectors, supports incremental inserts, and needs no training step, but it adds link storage to every vector and handles deletions awkwardly. IVF, an inverted file over k-means cells, scans only the probed cells; it needs a training pass to learn the cells and pairs naturally with product quantization, so IVF-PQ can hold a billion vectors in compressed form that would not fit as raw vectors in an HNSW graph. The HNSW journal paper compared against product-quantization indexes on 200 million SIFT vectors and found the graph faster at high recall but far hungrier for memory. Many systems run HNSW over the IVF centroids, or over compressed vectors.
How much memory does an HNSW index need?
Most of it is the vectors themselves plus the layer-0 links. With the recommended level multiplier mL = 1/ln M, an element appears on an upper layer only about 1/(M − 1) times on average, so upper layers add little. Layer 0 allows up to Mmax0 = 2M links per element. With M = 16 and 4-byte neighbour ids, that is up to 32 × 4 = 128 bytes of links per element, against 512 bytes for a 128-dimensional float32 vector or 3,072 bytes for a 768-dimensional one. So the graph is a modest overhead for large embeddings and a substantial one for small vectors or large M, while the full-precision vectors still dominate. That is why HNSW is often paired with quantized vectors once a collection outgrows RAM.
What is the difference between HNSW and NSW?
NSW, the navigable small world graph from the authors' earlier work, is a single flat graph built by inserting elements in random order and linking each to the nearest neighbours found, so early links become long-range shortcuts. Its greedy search scales polylogarithmically, which hurts at large N and especially in low dimensions. HNSW separates the links by length into layers: each element gets a random top level, the upper layers hold a geometrically shrinking subset, and search starts at the top and descends, so the hops per layer stay bounded and total work grows about logarithmically. It also adds the diversity heuristic for choosing neighbours and caps the number of links per element. Setting the level multiplier to zero turns HNSW back into a flat NSW-style graph.
4 questions to test what you just read
Work each one out before you open it — a number, a prediction or a reason, not a definition. Producing the answer is what makes it stick. Your progress is kept on this device.
With M = 16 and mL = 1/ln 16, what fraction of elements reach layer 2 or higher, and roughly how many layers does a 1,000,000-element index have?
Show answer
P(l ≥ 2) = 16^−2 = 1/256 ≈ 0.39%, about 3,900 elements. The top layer is about log16(10^6) = 6 / 1.204 ≈ 5, so roughly six layers counting layer 0: about 244 elements at layer 3 or above, 15 at layer 4, one at layer 5.
Candidates for a new element q are a (distance 1.0), b (1.2) and c (2.0), with M = 2. b is 0.5 from a, and c is 2.5 from a. Which two does the heuristic keep, and which would closest-M keep?
Show answer
The heuristic keeps a first. b is closer to a (0.5) than to q (1.2), so it is skipped. c is closer to q (2.0) than to a (2.5), so it is kept, giving {a, c}. Closest-M would keep {a, b}: two links into the same neighbourhood.
With M = 16 and 4-byte ids, how much link memory does layer 0 add per element at most, and what fraction is that of a 768-dimensional float32 vector?
Show answer
Mmax0 = 2M = 32 links × 4 bytes = 128 bytes. The vector is 768 × 4 = 3,072 bytes, so the links add about 4%. For a 128-dimensional SIFT vector (512 bytes) the same links add 25%, which is why graph overhead matters most for small vectors.
Why must ef be at least k, and what happens to recall and latency when you double ef?
Show answer
The bottom-layer search keeps the ef best candidates found and returns the top k of them, so with ef below k there are not enough results to return. Doubling ef widens the beam: more nodes are expanded and more distances computed, so latency rises roughly in proportion while recall rises with diminishing returns as it approaches 1.
From a word vector to RAG
The longest ladder here, and the most linear: nine papers that carry one idea — text as geometry — from a 2013 word embedding to a graph-structured retrieval system.
This idea in other formats
Explore the topic
See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.
More Paper Breakdowns
- Retrieval-Augmented GenerationThe paper behind every "chat with your docs" product. Pair a generator with a neural retriever so the model looks knowledge up instead of memorizing it — dense retrieval, top-k documents, RAG-Sequence vs RAG-Token, and why retrieval cuts hallucination.Read →
- ColBERTKeep one vector per token, not one per document, and score by late interaction: each query token takes its best match anywhere in the document (MaxSim), summed. It recovers the term-level precision single-vector retrieval blurs away, at index-friendly speed. The math, the case where it clearly wins, and how it sits between dense and cross-encoder retrieval — with runnable code.Read →
- Sentence-BERTThe model that turned BERT into fast, comparable sentence embeddings — the ancestor of every embedding model behind vector search and RAG. Why plain BERT can’t be compared without a pass per pair, the siamese fix with mean pooling, and the O(n²)→O(n) arithmetic that took a task from 65 hours to 5 seconds. Worked math plus runnable code.Read →
- Product QuantizationThe compression that makes billion-scale vector search fit in memory. Split a vector into subvectors, quantize each with a 256-entry codebook, and store a 512-byte vector in 8 — while m small codebooks span k^m codes. The compression math, asymmetric distance lookups, and IVFPQ — worked math plus runnable code.Read →
- GraphRAGRAG for the global questions vector retrieval can't answer. GraphRAG builds a knowledge graph from the corpus, detects communities of related entities, summarizes each, and map-reduces those summaries — so "what are the main themes across everything?" gets a comprehensive answer. Why top-k retrieval under-covers global queries, and the graph pipeline — worked math plus runnable code.Read →
- Dense Passage RetrievalThe dual-encoder method that made dense retrieval beat BM25 for open-domain QA. DPR encodes questions and passages into a shared vector space and matches by dot product; its efficiency trick is in-batch negatives — a batch of B pairs yields a B×B similarity matrix whose diagonal is the positive and whose off-diagonal gives B×(B−1) negatives for free. Why matching on meaning beats keywords, and how the free-negatives trick trains it — worked math plus runnable code.Read →