Menu
HNSWBuilding with AI

Hierarchical Navigable Small World

4 min readintermediateUpdated 28 Sept 2026
1 · In one line

HNSW finds the stored vectors closest to a query quickly by searching a stack of linked graphs, from a sparse top layer down to a dense bottom one.

1 · What it is

HNSW, short for Hierarchical Navigable Small World, is a way to find stored vectors that sit closest to a query vector. A vector is just a list of numbers, such as [1,2,3]. Tools like pgvector store embeddings this way. “Closest” means the smallest distance from the query. The search is approximate. It may miss a few true neighbours, but it is faster. Malkov and Yashunin introduced the idea.

Think of it as a pile of maps stacked in layers. Each map is a graph: points joined by links. The bottom map, layer 0, holds every vector. Each higher map holds a smaller group taken from the one below.

How many links each point gets is called M in the paper. pgvector, a database add-on, calls it m and uses 16 links per layer by default. The paper suggests picking layers like a skip list: each vector moves up to the next layer with a chance of 1 in M. With M = 16, about 1 in 16 vectors also sit on layer 1, and about 1 in 256 on layer 2.

On the upper layers, the search keeps just one best guess. It hops to whichever neighbour is closer, again and again. When no neighbour is closer, it drops one layer and carries on from the same spot. On layer 0 it keeps a longer list of candidates, called ef_search. pgvector sets ef_search to 40 unless you change it.

Tuning is mostly about M. The paper suggests values from 5 to 48. The links alone take about 60 to 450 bytes per vector, on top of the vectors themselves. A larger M helps with data that is truly complex (high intrinsic dimensionality, meaning it cannot be squeezed into a few numbers). It also helps when you need high recall, meaning you find more of the true neighbours. The price is more memory.

You rarely write HNSW yourself. hnswlib is a C++ library you can also use from Python. It can add items to an index that already exists. It can also mark an item so later searches skip it. Faiss offers HNSW as IndexHNSWFlat. pgvector offers HNSW as an index type inside Postgres. Qdrant uses HNSW as its only index for dense vectors.

2 · Why it exists

Finding the nearest vectors among millions is slow if you check every one.

Checking everythingThe simple method compares the query with every stored vector, so its cost grows in direct proportion to the size of the collection.
Exact shortcuts fadeExact speed-up methods give a big boost only when each vector has few numbers.
Flat graphs stallEarlier single-layer graph searches slowed down badly on clustered data or data with few dimensions.
3 · How it works

Follow one query from the top layer to the answer.

Drawn on one line for clarity. In one dimension, HNSW turns into a skip list, a classic layered linked list.
  1. 1 · assignEach new vector gets a random top layer, and each higher layer is exponentially less likely than the one below.
  2. 2 · linkOn each of its layers the vector is linked to nearby vectors, picked so that the links point in varied directions.
  3. 3 · descendA search starts on the top layer, keeps hopping to a closer neighbour until none is closer, then drops to the layer below.
  4. 4 · widenOn layer 0 it keeps a list of the best ef candidates found so far and returns the nearest of them.

Upper layers make the long jumps; layer 0 does the careful local search.

4 · Where it's used
WhoWhat they askWhat it works with
App developer on Postgres“Can nearest-neighbour queries on my embeddings table get faster?”An hnsw index on the embedding column
Search engineer“How high must ef_search go before recall stops improving?”Recall measured against an exact search
Python developer“Can I add and hide items without rebuilding the index?”An hnswlib index with mark_deleted
5 · What it solves, and what it doesn't
solves
  • Starting from the sparse top layer lets search cost grow with the logarithm of the collection size.
  • At query time one number, ef, sets the balance. Raise it and answers get more accurate, but each search takes longer.
  • There is no training step, so a pgvector HNSW index can be created before the table holds any data.
  • It works with several distance measures, such as straight-line (squared L2) distance, inner product and cosine in hnswlib.
doesn't solve
  • Answers are approximate. Once pgvector uses an HNSW index, a query can miss neighbours that an exact scan would have found.
  • pgvector says HNSW builds more slowly and uses more memory than its IVFFlat index.
  • Filters can starve results. With pgvector's default ef_search of 40, a filter matching 10% of rows leaves about 4 matches on average.
  • Faiss's HNSW index has no way to take a vector out, since pulling one would break the links the search depends on.
6 · Go deeper
Approximate nearest neighbor searchVector databasesEmbeddingsFAISSpgvector

Sources used

This explainer is written in original language. The links below support its factual claims.

  1. paperEfficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, Malkov and Yashunin, arXiv · read 28 Sept 2026
  2. repohnswlib: header-only C++/python library for fast approximate nearest neighbors, nmslib · read 28 Sept 2026
  3. docsHNSW algorithm parameters (ALGO_PARAMS.md), nmslib · read 28 Sept 2026
  4. repopgvector: open-source vector similarity search for Postgres, pgvector · read 28 Sept 2026
  5. docsFaiss indexes, Meta AI Research (Faiss wiki) · read 28 Sept 2026
  6. docsIndexing, Qdrant · read 28 Sept 2026
Suggest a correction