HNSW: The Algorithm Behind Instant Vector Search

⏱️ Lectura: 14 min

Comparing an embedding vector against a billion vectors, one by one, can take minutes even on a powerful server. HNSW (Hierarchical Navigable Small World) solves that bottleneck with a graph organized in layers that answers the same query in milliseconds, at the cost of sacrificing a bit of precision.

📑 En este artículo

1. TL;DR
2. What approximate vector search is and why it matters
3. How HNSW works internally
4. Practical examples with hnswlib
   1. A minimal index
   2. An index with real embeddings
5. Getting started: step-by-step installation and setup
6. Real-world use cases
7. Common mistakes and best practices
8. HNSW versus other vector search strategies
9. Going deeper: the design behind the layers
10. Frequently Asked Questions
    1. Does HNSW give exact results?
    2. How much memory does an HNSW index need?
    3. Can I delete vectors from an already-built HNSW index?
    4. Which distance should I use, cosine or L2?
    5. Does HNSW work with billions of vectors?
    6. Where is HNSW used in production today?
11. References

This algorithm powers vector search behind recommendation systems, semantic search engines, and context retrieval in RAG. Faiss, hnswlib, pgvector, Qdrant, Weaviate, and Elasticsearch use it as their default indexing engine.

TL;DR

• You’ll understand why exact nearest-neighbor search collapses once you reach millions of vectors.
• You’ll be able to describe HNSW’s layered graph structure and its resemblance to a skip list.
• You’ll know how to tune M, ef_construction, and ef_search to shift the balance between speed and accuracy.
• You’ll be able to build an HNSW index in Python with hnswlib in under 15 lines.
• You’ll know how to measure your index’s recall@10 by comparing it against a brute-force search.
• You’ll be able to decide when HNSW is the better choice over IVF, LSH, or a flat index.
• You’ll learn why deleting vectors from an HNSW index isn’t a cheap operation.

What approximate vector search is and why it matters

Vector search converts text, images, or audio into lists of numbers (embeddings) and looks for the most similar vectors according to a mathematical distance, almost always cosine or Euclidean distance. The problem shows up as that collection grows: comparing a query against every vector, known as brute-force search or flat search, has a cost that scales linearly with the size of the collection.

With a thousand vectors, brute force is instant. With a hundred million, each query means a hundred million dot products, before even adding network or disk latency. HNSW attacks that cost with a structure that discards most of the search space without comparing against every vector.

The underlying problem is known as the curse of dimensionality: as the number of dimensions in each vector rises (768, 1536, up to 4096 in some models), distances between points become increasingly similar to one another. Classic structures like k-d trees, efficient in 2 or 3 dimensions, stop offering any advantage over brute force in high-dimensional spaces.

HNSW’s core idea isn’t new: it comes from skip lists, a linked-list structure with shortcut levels. HNSW applies that same principle to a neighbor graph in a high-dimensional space, published in 2016 by Malkov and Yashunin in an arXiv paper that today is the field’s standard reference.

How HNSW works internally

HNSW builds several layers of the same graph. The top layer has few nodes and long connections, designed to jump quickly between distant regions of the space. Each lower layer adds more nodes and shorter connections, down to the base layer, which contains every vector in the index.

Each new vector is assigned, upon insertion, a maximum level chosen at random with a probability that decays exponentially: most nodes only live in the base layer, and very few reach the upper layers. That imbalance gives the graph its small world shape: a few long jumps are enough to traverse the entire space.

Searching for a close neighbor starts at a fixed entry point in the top layer. The algorithm moves greedily toward the neighbor closest to the query within that layer, and once it can’t improve any further, it drops down a layer and repeats the process, each time with a denser neighborhood.

The greedy descent stops at each layer when no candidate neighbor improves the distance to the query compared to the current best candidate. At that point, the algorithm passes that best candidate as the entry point to the layer below, and repeats the search with a set of candidates maintained in a priority queue.

Two parameters control the graph’s shape: M sets how many connections each node keeps (a higher M means more memory and better recall, with diminishing returns past a certain point), and ef_construction sets how many candidates are evaluated when inserting each new node, which affects the final graph’s quality.

flowchart TD
subgraph "Layer 2 (sparse)"
A2["node A"] --- B2["node B"]
end
subgraph "Layer 1"
A1["node A"] --- B1["node B"]
B1 --- C1["node C"]
end
subgraph "Layer 0 (base, all nodes)"
A0["node A"] --- B0["node B"]
B0 --- C0["node C"]
C0 --- D0["node D"]
D0 --- E0["node E"]
end
A2 -.-> A1
B2 -.-> B1
A1 -.-> A0
B1 -.-> B0
C1 -.-> C0

At query time a third parameter comes into play, ef_search (sometimes just ef), which controls how many candidates the algorithm keeps open while searching the base layer. Raising ef_search improves recall at the cost of latency; lowering it makes the query faster but risks missing the true neighbor.

Practical examples with hnswlib

A minimal index

hnswlib is the reference implementation in C++ with Python bindings, and it underlies many vector search engines. This first example creates a tiny index of 5 vectors with 4 dimensions and searches for the 2 most similar to the first one:

import hnswlib
import numpy as np

dim = 4
num_elements = 5

data = np.array([
    [0.1, 0.2, 0.3, 0.4],
    [0.9, 0.8, 0.7, 0.6],
    [0.15, 0.25, 0.35, 0.45],
    [0.5, 0.5, 0.5, 0.5],
    [0.05, 0.1, 0.2, 0.3],
], dtype=np.float32)

index = hnswlib.Index(space='cosine', dim=dim)
index.init_index(max_elements=num_elements, ef_construction=100, M=16)
index.add_items(data, ids=np.arange(num_elements))
index.set_ef(50)

labels, distances = index.knn_query(data[0], k=2)
print(labels, distances)

init_index reserves space for 5 elements with M=16 and ef_construction=100 (generous values for such a small index). knn_query returns the labels (ids) and distances of the 2 nearest neighbors to vector 0; the expected result includes vector 0 itself (distance 0) and vector 2, the most similar one in cosine space.

An index with real embeddings

The realistic case shifts scale: 200,000 embeddings with 384 dimensions, the typical size for a sentence-transformers-style model. This example builds the index, saves it to disk, and computes recall@10 by comparing against an exact search:

import hnswlib
import numpy as np

dim = 384
num_embeddings = 200_000

embeddings = np.random.default_rng(42).random((num_embeddings, dim)).astype(np.float32)
query_vectors = embeddings[:100]

index = hnswlib.Index(space='cosine', dim=dim)
index.init_index(max_elements=num_embeddings, ef_construction=200, M=32)
index.add_items(embeddings, ids=np.arange(num_embeddings))
index.save_index("catalogo_productos.hnsw")

index.set_ef(100)
approx_labels, _ = index.knn_query(query_vectors, k=10)

exact_labels = np.argsort(1 - (query_vectors @ embeddings.T), axis=1)[:, :10]

recall = np.mean([
    len(set(approx_labels[i]) & set(exact_labels[i])) / 10
    for i in range(len(query_vectors))
])
print(f"recall@10: {recall:.3f}")

This block computes the approximate top-10 with knn_query and the exact top-10 by sorting the full similarity matrix with np.argsort. recall@10 measures what fraction of the 10 exact neighbors also appears in the approximate result: a score of 0.95 means the index gets 95% of the real neighbors right; if it drops below 0.8, it’s worth raising ef_search or M.

💡 Tip: normalize your vectors before indexing them if your model was trained for cosine similarity. With space='cosine', hnswlib already normalizes internally, but with 'ip' (inner product) it doesn’t do that for you.

Getting started: step-by-step installation and setup

To bring HNSW into a real project, here are the concrete steps, no shortcuts:

1. Install the library: pip install hnswlib (or faiss-cpu if you prefer Faiss with built-in HNSW support).
2. Choose the space metric based on your embedding model: cosine, l2, or ip.
3. Set M (16 to 48 is a typical range) and ef_construction (100 to 200) when calling init_index.
4. Add the vectors with add_items(vectors, ids), in batches if the collection is large.
5. Save the index with index.save_index("path.hnsw") and load it later with load_index.
6. On each query, set ef_search above k (for example, ef_search=100 for k=10).
7. Measure recall@10 against brute force on a sample before going to production.

If your stack already uses PostgreSQL, pgvector adds a native HNSW index without leaving SQL:

CREATE INDEX ON productos
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);

SET hnsw.ef_search = 100;

EXPLAIN ANALYZE
SELECT id FROM productos
ORDER BY embedding <=> '[0.12, 0.04, 0.31]'
LIMIT 10;

EXPLAIN ANALYZE confirms that Postgres is using the index: if the plan shows Index Scan using on the HNSW index instead of a Seq Scan, the query is taking advantage of the graph instead of comparing against the entire table.

Real-world use cases

The most common use today is RAG (retrieval-augmented generation): an LLM-based assistant needs to retrieve the most relevant documentation fragments for a question, and it runs that search against an HNSW index instead of reading the entire corpus.

A concrete case: an e-commerce catalog with millions of products generates an image-and-description embedding for each one. When a user searches by photo, the system converts the image into a vector and queries the HNSW index to bring back the most visually similar products, within the response time of a normal HTTP request.

Semantic search engines and recommendation systems use the same technique to find similar products, songs, or articles based on their vector representation. Faiss, Meta’s library, has exposed HNSW as one of its index types for years.

Databases like Qdrant, Weaviate, and Milvus, and search engines like Elasticsearch and OpenSearch (through the dense_vector type), integrate HNSW as their default or primary vector index.

Common mistakes and best practices

⚠️ Watch out: HNSW doesn’t support deleting a vector cheaply. hnswlib lets you mark it with mark_deleted to exclude it from future searches, but the node keeps taking up space in the graph until you rebuild the index.

index.mark_deleted(id_producto_descontinuado)

# the vector still takes up space in the graph
# until you rebuild the index with save_index() and load_index()

• ef_search equal to k: if you ask for the 10 nearest neighbors with ef_search=10, recall tends to be poor. Leave margin: ef_search from 50 to 200 depending on how much latency you can tolerate.
• Mixing metrics: indexing unnormalized vectors with ‘ip’ breaks the relationship between distance and real similarity. If your model assumes cosine, normalize before inserting or use space=’cosine’ directly.
• Excessive M: raising M from 16 to 64 doesn’t double the recall; it doubles the memory and build time. Measure actual recall before blindly raising M.
• Everything in RAM: HNSW keeps the entire graph in memory. For catalogs of tens of millions of high-dimensional vectors, RAM tends to be the bottleneck before the CPU is.
• Underestimating build time: indexing millions of vectors with high M and ef_construction can take minutes or hours; test first with a subset before launching the full build in production.

HNSW versus other vector search strategies

None of these options is universally better: the choice depends on the size of the collection, the available memory, and how much recall loss you’re willing to accept.

Option	When to use it	Advantage	Limitation
HNSW	Low latency and good recall without retraining the index	Best speed/accuracy balance among the approximate options	The entire graph lives in RAM; deleting vectors is costly
IVF (Faiss)	Huge collections with a tight memory budget	Divides the space into clusters and only searches the closest ones	Needs to retrain the clusters if the data distribution changes significantly
Flat / brute force	Small collections or when recall must be 100%	Exact result, no approximation	Linear cost: becomes slow past a few million vectors
LSH	Very limited memory and acceptable approximate recall	Simple structure based on hash functions	Recall generally worse than HNSW in practice

Going deeper: the design behind the layers

Each node’s layer assignment follows the formula level = floor(-ln(uniform(0,1)) * mL), where mL is a normalization factor related to M. That exponential distribution is the same idea skip lists use to decide how many shortcut levels each inserted element gets.

In the base layer, each node typically keeps up to 2×M connections (double what upper layers have), because that’s where most of the search’s real work happens. That asymmetry explains why an HNSW index’s memory footprint grows faster than just dim × num_vectors × 4 bytes: you have to add the cost of the adjacency lists.

sequenceDiagram
participant Q as Query
participant L2 as Upper layer
participant L1 as Middle layer
participant L0 as Base layer
Q->>L2: enters through the entry point
L2-->>Q: best candidate in this layer
Q->>L1: descends with that candidate
L1-->>Q: refined candidate
Q->>L0: descends to the base layer
L0-->>Q: final top-k neighbors

Building an HNSW index is more time-costly than building an IVF index, because each insertion runs several greedy searches to find who to connect to. In exchange, it doesn’t require a prior training phase over a data sample, something IVF does need to define its centroids.

To reduce memory footprint, Faiss combines HNSW with product quantization (PQ): it uses the HNSW graph as a coarse navigation layer and compresses the actual vectors into quantized codes of a few bytes instead of storing the full float32, the same pattern used by indexes like IVF-PQ, but with HNSW organizing the graph instead of clusters.

💭 Key point: pgvector didn’t support HNSW from the start: it added that index type as an alternative to IVFFlat in a later version of its repository, precisely because HNSW doesn’t require a prior training step the way IVFFlat does.

📖 Summary on Telegram: View summary

Your next step: install hnswlib with pip install hnswlib, generate 10,000 random 128-dimensional vectors with NumPy, build an index, and compare its recall@10 against brute force by changing only ef_search between 10, 50, and 200.

Frequently Asked Questions

Does HNSW give exact results?

No. It’s an approximate search algorithm: it prioritizes speed over perfect accuracy. Recall, how often it finds the true neighbor, is controlled by adjusting ef_search at query time.

How much memory does an HNSW index need?

As a floor, dim × number of vectors × 4 bytes if you use float32, plus the cost of each node’s adjacency lists, proportional to M. An index of 10 million 768-dimensional vectors runs into tens of gigabytes just in the vectors, not counting the graph.

Can I delete vectors from an already-built HNSW index?

hnswlib lets you mark them with mark_deleted to exclude them from future searches, but the node keeps taking up space in the graph. To actually free memory, you need to rebuild the index from scratch.

Which distance should I use, cosine or L2?

It depends on how the model that generated the embeddings was trained. If the model optimizes for cosine similarity, normalize the vectors before indexing them or use space='cosine' directly in hnswlib.

Does HNSW work with billions of vectors?

Yes, but since it lives entirely in RAM, it’s better to combine it with quantization, as Faiss does with product quantization, or distribute it across several nodes, instead of trying to fit everything on a single machine.

Where is HNSW used in production today?

In Faiss, hnswlib, pgvector, Qdrant, Weaviate, Milvus, and in the dense_vector type of Elasticsearch and OpenSearch. It’s the most widely used approximate index in the vector database ecosystem.

References

• Malkov and Yashunin, arXiv 1603.09320: the original paper describing HNSW and its relationship to skip lists.
• nmslib/hnswlib on GitHub: the reference implementation in C++ with Python bindings used in this article’s examples.
• facebookresearch/faiss on GitHub: Meta’s library that combines HNSW with product quantization for more compact indexes.
• pgvector/pgvector on GitHub: the PostgreSQL extension that adds native HNSW indexes on the vector column.

📱 Enjoying this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.

Imagen destacada: Foto de A Chosen Soul en Unsplash