Loading...
System Design and AI Engineering, by Roni Das. 980 interactive lessons.
Start LearningAI Engineering · Advanced · LLM and GenAI Ops
Hierarchical Navigable Small World, a graph-based nearest neighbor index that gives high recall at low latency by navigating layers of links, at the cost of more memory than IVF.
In short
HNSW (Hierarchical Navigable Small World) is a graph index for approximate nearest neighbour search. It links each vector to near neighbours in stacked layers and walks those links towards the query, giving fast, high-recall search at the cost of extra memory.
In short
HNSW (Hierarchical Navigable Small World) is a graph index for approximate nearest neighbour search. It links each vector to near neighbours in stacked layers and walks those links towards the query, giving fast, high-recall search at the cost of extra memory.
Learn it in the course
This page is the free part.
₹999 in India$49 everywhere elseonce, for the whole course
The AI Engineering course covers HNSW across a run of lessons, not one page. These 4 alone are about 203 minutes of step-by-step reading, every one with code you run in the browser, all with a quiz.
How embeddings become searchable points in space, why exact nearest-neighbor search breaks at scale, and how ANN indexes like HNSW, IVF, and PQ make retrieval fast enough to serve.
Exact search compares a question with every stored piece. Clustered search groups the pieces first and looks only in the nearest groups. Measured on 470 quiz questions and 1,823 pieces with nomic-embed-text and 32 clusters: searching 8 clusters, about a third of the comparisons, found 94 to 95% of the exact top 5 and kept 429 to 430 of 441 right lessons. Searching 1 cluster did 6% of the work and found the right lesson in the top 5 for 338 to 349 of 470.
Should you embed a whole document as one list of numbers, or cut it into small pieces first? Measured on this course's 112 AI lessons with 470 of their own quiz questions and bge-m3 reading up to 8,192 tokens. With one embedding per lesson, the right lesson came first for 286 questions. With 200-word pieces, for 356. Pieces won on short lessons too, not only long ones, and whole lessons still won 31 questions.
Measured on a laptop with qwen2.5:3b over 30 shuffled calls: the first word came back after a median 1.0 s for a 256-token prompt and 36.6 s for about 7,900 tokens. With the laptop's own slowing taken out, writing got about 1.1 tokens a second slower for every 1,000 prompt tokens. A bigger context window made Ollama report more memory: 2.05 GB at 2,048 tokens, 2.79 GB at 32,768.
all part of
AI Engineering
210 lessons · about 219 hours · 10 free to read
₹999in India, by UPI
$49everywhere else, by PayPal
You own this course
Continue with Vector Databases and Approximate Nearest Neighbor Searchpay once,
yours for life
HNSW stands for Hierarchical Navigable Small World. It is an index for approximate nearest neighbour search, which finds the vectors closest to a query without comparing it with every stored vector. It was published by Yury Malkov and Dmitry Yashunin, and it is now one of the most common index types in vector databases.
HNSW builds a graph. Every vector is a node, joined by links to some of its nearest neighbours. The graph has several layers. The bottom layer holds every vector, with short links. Each layer above holds fewer vectors, with longer links. It works like a road map with highways on top, main roads in the middle and side streets at the bottom.
"Small world" describes graphs where any node can reach any other in a few hops, the way two strangers are often linked through a few mutual friends. "Navigable" means a simple greedy walk, always moving to the neighbour closest to the target, gets there. The layers make the first hops long and the last hops short.
A search starts at an entry point in the top layer. It looks at the current node's neighbours, moves to whichever is closest to the query, and repeats until no neighbour is closer. Then it drops one layer and continues from the same node, using the denser links there. At the bottom layer, it keeps a list of the best candidates it has seen and returns the top k.
New vectors are added with the same walk: find the new vector's neighbourhood, then link it to near neighbours. Each new vector is given a random top layer, so most vectors live only in the lower layers and only a few reach the top. Unlike a clustered IVF index, which needs a training pass to learn its cluster centres before it can index anything, HNSW grows as you insert.
Three settings control it. m is how many links each node keeps: higher makes the graph denser, more accurate and bigger in memory, and 16 is a common default. ef_construction is how widely the builder searches for good links while inserting; higher builds a better graph more slowly, and values from 64 to 200 are typical. ef_search is the query-time dial: how many candidates the walk keeps in flight. Raising it finds more true neighbours and takes longer.
The graph lives in memory on top of the vectors. A guideline from the FAISS library puts the size per vector at d x 4 + m x 2 x 4 bytes, where d is the number of dimensions. For 10 million vectors of 1,024 dimensions with m = 16, that is 4,096 bytes of numbers plus 128 bytes of links per vector: about 41 GB of vectors, and about 42 GB with the graph, before any stored text. Because HNSW is usually served from RAM, memory is often the largest cost in a self-hosted vector store.
The recall you tuned at launch does not stay put. With the same ef_search, a bigger graph means the walk visits a smaller share of it, so fewer true neighbours come back. An illustrative curve shows a 98 percent recall target needing ef_search of 64 at one million vectors and 256 at ten million, four times the search work per query. Track recall in your monitoring, sampled against exact search on a subset, and tune again as the index grows.
Filters are the other trap. If a store fetches the nearest results and then applies a WHERE filter, a selective filter can return fewer rows than you asked for. Even when the filter is applied during the walk, the vectors that pass it can form disconnected islands in the graph, and the walk can get stuck on one island while the answer sits on another. Qdrant, for example, documents adding extra links so filtered subsets stay connected, and pgvector 0.8 and later can keep scanning with its iterative scan setting.
pgvector, the PostgreSQL extension, is a common place to start. You store embeddings in a vector column, build an HNSW index on it with a distance type, set ef_search for the connection, and query with ORDER BY distance and LIMIT. The ORDER BY with LIMIT is what lets PostgreSQL use the index instead of scanning every row.
A minimal setup is: CREATE INDEX ON documents USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64); then SET hnsw.ef_search = 40; then SELECT id FROM documents ORDER BY embedding <=> $1 LIMIT 5. Here <=> is cosine distance, <-> is Euclidean distance and <#> is the negative dot product. The operator class in the index must match the operator in the query, or the index is not used.
To tune it, take a sample of real queries and run each one twice: once with exact search and once through the index. Count what share of the exact top results the index also returned. Raise ef_search until that share clears your bar, then stop, because past the bend in the curve each extra point of recall costs much more time.
A common rule of thumb is to reach for HNSW first when speed matters, because it usually gives the best recall for the time spent. Move to IVF, or IVF combined with product quantization (a compression method that shrinks each vector to a short code), when memory rather than speed is the problem, meaning the graph no longer fits in the RAM you are willing to pay for.
Skip it for small collections. For a few thousand vectors, exact search is fast and never misses. For 1,823 pieces of text with 768 numbers each, exact search is about 1.4 million multiplications per question, which a laptop does in a fraction of a second. An index there adds build time, memory and a new way to lose answers.
Be careful with numbers from elsewhere. HNSW's recall depends on your data, your settings and your collection size, so a figure from someone else's benchmark does not carry over. The public ANN-Benchmarks project shows what recall-versus-speed curves look like across libraries, but the curve that matters is the one you measure on your own queries.
hnswlib
An open-source C++ library with Python bindings that implements HNSW, maintained by one of the method's authors.
FAISS
Meta's vector search library, which includes an HNSW index (IndexHNSWFlat) alongside IVF and product quantization indexes.
pgvector
The PostgreSQL extension supports an hnsw index type with m and ef_construction build options and an hnsw.ef_search setting.
Qdrant
An open-source vector database that uses HNSW as its vector index and documents a filterable variant of it.
m is the number of links each node keeps, which sets graph density and memory. ef_construction is how widely the builder searches for links when inserting, which sets build quality and build time. ef_search is how many candidates a query keeps in flight, which trades recall for speed.
HNSW walks a layered graph of neighbour links and grows as you insert, but keeps the graph in memory. IVF groups vectors into clusters with k-means, needs a training pass first, and searches only the nearest clusters. HNSW is a common first choice when speed matters; IVF with compression when memory does.
No. It is an approximate method, so it can miss some true neighbours, and the share it finds depends on ef_search and the size of the graph. Measure recall by comparing its results with exact search on a sample of queries.
It stores the links of the graph on top of the vectors, and it is usually served from RAM. By a FAISS guideline, each vector needs d x 4 bytes for its numbers plus m x 2 x 4 bytes for links, so memory grows with both the number of vectors and m.
Either the store filters after the search, dropping most of the nearest results, or the filtered vectors are not connected in the graph, so the walk cannot reach them. Use a store that filters during the walk and keeps filtered subsets connected, or raise ef_search.
ANN (Approximate Nearest Neighbor)
Search that finds vectors close to a query without scanning every item, trading a small chance of missing a true neighbor for a large gain in speed. HNSW and IVF are the common indexes.
Vector Database
A database that stores embeddings, lists of numbers that capture the meaning of text or images, and finds the ones closest to a question's embedding. It powers semantic search and RAG.
RAG (Retrieval-Augmented Generation)
A pattern that retrieves relevant text from an external index and puts it in the model's prompt so the answer is grounded in current, verifiable facts rather than the model's memory.
Agentic RAG
Agentic RAG is RAG where a language model runs the search in a loop. It decides whether to search, what to search for and where. Then it checks if the text it found answers the question.
Embedding
A list of numbers that represents the meaning of a piece of text, so that similar meanings sit close together in vector space. The same model must embed both the corpus and the query.
Reranking
A second retrieval stage where a cross-encoder scores each candidate chunk against the query directly. Slower than the first-stage retriever but far more precise, so it runs only over the top few dozen results.
This page explains the idea. The "Vector Databases and Approximate Nearest Neighbor Search" lesson builds it up step by step, with diagrams. It is part of the AI Engineering course, which has 210 lessons. 10 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Vector Databases and Approximate Nearest Neighbor Search lessoncourse 2
Take models from notebook to production, with labs on real models.