← back to the archiveCover illustration for “HNSW: the index behind fast vector search”
TERM6mo ago·Published · Updated ·by Andy Padia

HNSW: the index behind fast vector search

In short: HNSW (Hierarchical Navigable Small World) is a layered graph index that makes approximate nearest-neighbour vector search fast, at a cost in memory.

HNSW (Hierarchical Navigable Small World) is a graph-based index for approximate nearest-neighbour search, described by Malkov and Yashunin in a paper submitted in March 2016. It organises vectors into layered graphs so a search can jump across the space in the sparse upper layers and refine locally at the bottom. Many vector databases and extensions, pgvector among them, offer it as an index type.

HNSW in plain words

Finding a house: first take the motorway to the right city, then main roads to the neighbourhood, then side streets to the door. You never check every house in the country.

How it works

Each vector is a node linked to its near neighbours. Higher layers contain fewer nodes with long-range links; the bottom layer contains all nodes. A query enters at the top, greedily moves to closer nodes, drops a layer and repeats. The paper says this layering is what lets search cost scale logarithmically with the size of the collection.

Two build settings and one query setting control the trade. In the pgvector README, read in November 2026, m is the maximum number of connections per layer (default 16), ef_construction is the candidate list size while building (default 64) and hnsw.ef_search is the candidate list size while searching (default 40).

Example

In pgvector:

CREATE INDEX ON chunks USING hnsw (embedding vector_cosine_ops)
  WITH (m = 16, ef_construction = 64);
SET hnsw.ef_search = 100;  -- higher = better recall, slower queries

Where you'll meet it

  • pgvector, Elasticsearch, OpenSearch, Qdrant, Weaviate, Milvus and FAISS
  • Index configuration screens in managed vector databases
  • Benchmarks comparing approximate nearest-neighbour methods
  • Capacity planning for RAG systems

What it changes for you

For developers, HNSW defaults are usually fine to start; raise the search setting when recall tests show misses. For platform teams, memory is the constraint to plan for: the pgvector README says builds are significantly faster when the graph fits into maintenance_work_mem. It also notes that vacuuming an HNSW index can take a while and suggests reindexing first, so schedule maintenance for tables with heavy deletes.

HNSW vs IVF

An IVFFlat index divides vectors into lists and searches only the lists closest to the query. The pgvector README says IVFFlat builds faster and uses less memory, while HNSW has the better speed-recall tradeoff.

Common mistake

My view: blaming the language model for missing answers when the vector index's recall is low. Measure recall of the index against exact search on a sample before tuning anything downstream.

Vector search · Vector database · Embeddings · Retrieval-augmented generation

From the archive: Why your RAG pipeline returns irrelevant results

Measure the index's recall against exact search before you tune anything downstream.

#field-guide#vector-search#retrieval#algorithms#databases

Sources

  1. arxiv.org/abs/1603.09320
  2. github.com/pgvector/pgvector
← older drop
SWE-bench: the benchmark for AI fixing real GitHub issues
newer drop →
AI-BOM: a bill of materials for AI systems

related drops

explore all 557 drops →
← back to the archiveday 175