HNSW (Hierarchical Navigable Small Worlds)

Every semantic search system, RAG pipeline, and recommendation engine eventually faces the same wall: once you have millions or billions of embeddings, comparing a query vector against every single one of them — brute-force, exact nearest neighbour search — becomes too slow to serve in real time. HNSW (Hierarchical Navigable Small Worlds) is the algorithm that broke through that wall, and by 2025–2026 it has become the default index type in essentially every vector database on the market: Pinecone, Weaviate, Qdrant, Milvus, Chroma, Redis, pgvector, Elasticsearch, and OpenSearch all ship HNSW as their primary or recommended index.

HNSW was introduced in a 2016 paper by Yury Malkov and Dmitry Yashunin, building on decades of research into “small-world” network theory — the same mathematical structure behind the “six degrees of separation” phenomenon in social networks. The insight: if you organize data points into a graph where each point has a handful of well-chosen neighbours, you can hop from any point to any other point in only a few steps, even in graphs with billions of nodes. HNSW applies this idea to vector search, replacing an O(n) linear scan with an O(log n) graph traversal.

The Problem HNSW Solves

Exact nearest neighbour (NN) search — checking a query vector against every stored vector and returning the truly closest ones — is simple and perfectly accurate, but it scales linearly with the size of the collection. At 10,000 vectors this is instant. At 100 million vectors with 1,024 dimensions each, a single query can take seconds, which is unusable for interactive applications like chat-based RAG or real-time recommendations.

Approximate Nearest Neighbour (ANN) search accepts a small, controlled amount of inaccuracy — occasionally missing the single closest vector, in exchange for enormous speedups. HNSW is the most widely deployed ANN algorithm because it achieves near-perfect recall (often 95–99.9%) while running in logarithmic time, and — unlike many competing ANN methods — it supports incremental inserts and deletes without a full index rebuild.

How HNSW Works

HNSW’s core idea is to build a multi-layer graph, where each layer is a “navigable small world” graph of decreasing density:

• The top layer contains very few nodes with long-range links — it exists purely for fast, coarse navigation across the entire dataset.
• Each layer below adds more nodes and shorter, denser links.
• The bottom layer (layer 0) contains every single vector in the collection, densely interconnected with its nearest neighbours.

A search starts at an entry point in the sparse top layer, greedily moves toward the region closest to the query vector, then drops down a layer once no further progress can be made — repeating this “zoom in” process until it reaches layer 0, where it performs a fine-grained local search to find the true nearest neighbours.

graph TB
    classDef default fill:#ffffff,stroke:#4338CA,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef layer2 fill:#4338CA,stroke:#4338CA,stroke-width:2px,color:#ffffff,rx:8px,ry:8px;
    classDef layer1 fill:#6366F1,stroke:#4338CA,stroke-width:2px,color:#ffffff,rx:8px,ry:8px;
    classDef layer0 fill:#EEF0F7,stroke:#0D9488,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef query fill:#0D9488,stroke:#0D9488,stroke-width:2px,color:#ffffff,rx:8px,ry:8px;

    Q([Query Vector]):::query --> L2

    subgraph L2["Layer 2 — sparse, long-range links"]
        A2((A)):::layer2 --- B2((B)):::layer2
    end

    subgraph L1["Layer 1 — medium density"]
        A1((A)):::layer1 --- B1((B)):::layer1
        B1 --- C1((C)):::layer1
        A1 --- D1((D)):::layer1
    end

    subgraph L0["Layer 0 — every vector, densely linked"]
        A0((A)):::layer0 --- B0((B)):::layer0
        B0 --- C0((C)):::layer0
        C0 --- E0((E)):::layer0
        A0 --- D0((D)):::layer0
        D0 --- F0((F)):::layer0
        E0 --- F0((F)):::layer0
    end

    L2 -.drop down.-> L1
    L1 -.drop down.-> L0
    L0 --> R([Top-k Nearest Neighbours]):::query

Graph Construction

When a new vector is inserted, HNSW probabilistically assigns it a maximum layer — most vectors only appear in layer 0, while progressively fewer appear in higher layers (following an exponentially decaying probability distribution). This mirrors how skip lists work in classical computer science: a small number of “express lane” nodes let searches skip over large portions of the graph.

At insertion time, the algorithm searches the existing graph for the new vector’s approximate nearest neighbours at each layer it belongs to, and links it to them — bounded by a maximum number of connections per node.

The Key Tuning Parameters

ef is the parameter operators tune most often in production — it can be adjusted per query, letting a single index serve both “fast but slightly less accurate” and “slow but near-exact” requests without rebuilding anything.

HNSW vs. Other ANN Methods

HNSW’s biggest structural advantage over IVF-PQ and classic LSH is that it doesn’t need the data distribution known in advance and it supports live inserts and deletes gracefully — a critical property for RAG systems where documents are added and removed continuously. Its main weakness is memory: because the graph stores explicit edges for every vector, HNSW indexes typically consume more RAM than IVF-PQ for the same collection size, since IVF-PQ compresses vectors via product quantization.

What’s New in HNSW (2025–2026)

The algorithm itself (the graph structure) hasn’t fundamentally changed since 2016, but the engineering around HNSW has matured dramatically in the last two years, closing most of its historical weaknesses:

• Filtered HNSW (metadata-aware search) — Modern vector databases (Qdrant, Weaviate, Milvus) now support combining HNSW graph traversal with metadata filters (e.g., “find similar documents where tenant_id = 42”) without falling back to brute-force post-filtering. Qdrant’s 2025 releases introduced adaptive filtering that dynamically switches between graph-traversal-with-filter-pruning and payload-index pre-filtering depending on filter selectivity.
• Quantization-aware HNSW — To address HNSW’s memory footprint, most databases now combine the graph with scalar or binary quantization of the underlying vectors (e.g., Qdrant’s binary quantization, Milvus’s SQ8/PQ hybrid, pgvector’s halfvec and binary quantization added in pgvector 0.7–0.8). This can reduce memory usage by 4–32× with a small recall cost, while keeping the HNSW graph structure intact for navigation.
• DiskANN-style disk-resident HNSW variants — For collections too large to fit in RAM, 2025-era systems (Milvus’s DiskANN integration, Azure Cosmos DB’s DiskANN-backed vector index, LanceDB) blend HNSW-like graph navigation with SSD-resident storage, trading some latency for the ability to index tens of billions of vectors on commodity hardware.
• GPU-accelerated HNSW construction — NVIDIA’s cuVS (part of RAPIDS, integrated into Milvus 2.5+ and FAISS) accelerates HNSW graph construction on GPUs, cutting index build times for hundred-million-scale collections from hours to minutes.
• Native HNSW in relational databases — pgvector’s HNSW support (stable since pgvector 0.5, further optimized through 0.7/0.8 in 2024–2025) and MySQL HeatWave’s vector HNSW index (2025) mean HNSW is no longer confined to specialized vector databases — it now runs directly inside general-purpose OLTP databases, simplifying architecture for teams that don’t want a separate vector store.
• Multi-vector and ColBERT-style HNSW — With late-interaction retrieval models (ColBERT v2, and 2025’s Jina-ColBERT-v2) becoming more popular, databases such as Qdrant and Vespa have extended HNSW to index multi-vector representations (one HNSW-searchable vector per token) rather than a single dense vector per document, enabling finer-grained semantic matching while retaining HNSW’s speed.

HNSW in a RAG Pipeline

flowchart LR
    classDef default fill:#ffffff,stroke:#4338CA,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef store fill:#F7F8FC,stroke:#6366F1,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef ai fill:#4338CA,stroke:#4338CA,stroke-width:2px,color:#ffffff,rx:8px,ry:8px;
    classDef result fill:#0D9488,stroke:#0D9488,stroke-width:2px,color:#ffffff,rx:8px,ry:8px;

    Docs([Document Corpus]) --> Embed(Embedding Model):::ai
    Embed --> Build[Build HNSW Graph]:::store
    Query([User Query]) --> QEmbed(Embedding Model):::ai
    QEmbed --> Search{HNSW Graph Traversal}:::store
    Build --> Search
    Search --> TopK[Top-k Candidate Chunks]:::result
    TopK --> Rerank(Reranker Model):::ai
    Rerank --> LLM(LLM Generation):::ai
    LLM --> Answer([Final Answer]):::result

In production RAG systems, HNSW rarely operates alone. It handles the first-stage retrieval: pulling a candidate set (say, top 50–100) of semantically similar chunks from millions of embeddings in milliseconds. Because ANN search trades some recall for speed, that candidate set is then commonly passed through a reranker — a more expensive but more precise model — to reorder the top candidates before they’re sent to the LLM. This two-stage “retrieve-then-rerank” pattern is now the standard architecture for production-grade RAG.

Recall, Latency, and Memory: The Central Trade-off

Every HNSW deployment decision comes down to balancing three variables:

1. Recall — What fraction of the true top-k nearest neighbours does the approximate search actually find? Increasing M and ef improves recall but costs memory and latency.
2. Latency — How fast is each query? Lower ef at query time means faster but less accurate results.
3. Memory — Explicit graph edges plus full-precision vectors can be expensive at scale; quantization mitigates this at a small recall cost.

A common production pattern is to benchmark recall against ground-truth brute-force results on a validation set, then tune ef_search to hit a target (e.g., 98% recall@10) at the lowest possible latency.

# Measuring recall of an HNSW index against exact brute-force search
import numpy as np

def recall_at_k(hnsw_labels: np.ndarray, exact_labels: np.ndarray, k: int = 10) -> float:
    hits = 0
    for approx, exact in zip(hnsw_labels, exact_labels):
        hits += len(set(approx[:k]) & set(exact[:k]))
    return hits / (len(hnsw_labels) * k)

# recall_at_k(hnsw_results, brute_force_results, k=10)
# -> e.g. 0.987, meaning 98.7% of true top-10 neighbours were retrieved

Choosing HNSW Parameters by Scale

Where HNSW Came From: Skip Lists and Small-World Networks

HNSW didn’t emerge in a vacuum — it’s the convergence of two older ideas. The first is the skip list, a classical probabilistic data structure (Pugh, 1990) that speeds up ordered search by maintaining multiple “express lane” layers over a sorted linked list, each layer skipping over more elements than the one below it. HNSW borrows this exact layering idea, but generalizes it from a 1-dimensional sorted list to an arbitrary-dimensional vector space, where “ordering” is replaced by graph proximity.

The second is Navigable Small World (NSW) graphs, an earlier algorithm by the same research group (Malkov et al., 2014) that built a single-layer graph with the small-world property — most nodes reachable from any other node in only a handful of hops, thanks to a mix of short-range and long-range links (mirroring the famous “six degrees of separation” result from social network theory, and Kleinberg’s decentralized-search models). NSW alone worked reasonably well at small scale but suffered from expensive, unpredictable search paths as datasets grew — searches could get stuck in locally dense regions before finding a long-range link out. HNSW’s key contribution was to stack multiple NSW-like graphs in layers of decreasing density, so that a search reliably starts wide (top layer) and narrows down (lower layers), fixing the traversal-cost blowup that plagued flat NSW graphs at scale. This layered structure is what gives HNSW its logarithmic — rather than roughly linear — query complexity as collections grow into the billions.

Handling Deletions and Index Maintenance

A detail that trips up many first-time HNSW users: the algorithm was designed around insertion, not deletion. Removing a node from a multi-layer graph safely — without leaving dangling edges or disconnecting parts of the graph — is nontrivial, so most HNSW implementations (hnswlib, FAISS’s HNSW index, and the earliest versions of several vector databases) historically supported only soft deletes: the vector is marked as deleted and excluded from search results, but its graph edges remain in place so that other nodes can still route through it during traversal.

This has real operational consequences. A collection with a high churn rate (frequent inserts and deletes — common in RAG systems tracking a live document set) can accumulate a large fraction of “tombstoned” vectors over time, bloating memory and gradually degrading search quality as the graph becomes cluttered with dead ends. Production vector databases address this in one of two ways:

• Periodic index rebuilds — the simplest approach: track the tombstone ratio, and rebuild the HNSW graph from scratch once it crosses a threshold (e.g., 10–20% deleted). Straightforward but causes periodic latency spikes and temporary resource doubling during rebuild.
• True incremental deletion — newer engines (Qdrant, Milvus 2.4+, and updated versions of hnswlib) implement actual edge-repair-on-delete, reconnecting a deleted node’s neighbours to each other so the graph stays fully connected without a rebuild. This is more complex to implement correctly but avoids the rebuild penalty entirely, and has become the expected behavior in most 2025–2026 vector database releases.

Any team running a high-churn RAG corpus (e.g., a support ticket system, a codebase index that changes with every commit) should check which deletion strategy their vector database uses — it’s one of the most common sources of unexpected memory growth and slow recall decay in production.

Common Pitfalls in Production

• Treating ef_search as a fixed constant. Because recall and latency both depend on ef, many teams set it once during initial testing and never revisit it as the collection grows. As a collection scales from 100K to 10M vectors, the same ef value that gave 99% recall at the smaller size may drop to 90% or lower at the larger size, silently degrading retrieval quality. Recall should be re-benchmarked against brute-force ground truth whenever collection size changes materially.
• Ignoring build-time cost at scale. ef_construction and M affect not just query quality but how long it takes to build (or rebuild) the index. Teams that tune purely for query-time recall sometimes discover that reindexing a large, frequently-updated collection now takes hours — a serious problem if the corpus changes daily.
• Assuming HNSW recall is uniform across the vector space. Recall can vary meaningfully across different regions of a high-dimensional space, especially with skewed or clustered data (common in real embeddings, which are rarely uniformly distributed). A global recall@10 average can mask much worse performance in sparsely populated regions of the space — often exactly the “long-tail,” niche queries that matter most in enterprise search.
• Mixing quantization and HNSW without validating end-to-end recall. Quantized HNSW variants (binary or scalar quantization layered on top of the graph) can look fine in isolation but interact with ef in non-obvious ways — a setting that gave 98% recall on full-precision vectors might give meaningfully lower recall once vectors are quantized, requiring ef to be retuned rather than assumed unchanged.

Why HNSW Still Dominates in 2026

Despite a decade of competing ANN research — IVF-PQ, LSH, ScaNN, Annoy, NGT, Vamana/DiskANN — HNSW remains the default choice across the vector database ecosystem because it hits a rare combination: near-exact recall, logarithmic query time, and native support for live updates, all without needing to know the data distribution in advance. The 2025–2026 wave of innovation hasn’t replaced HNSW; it has made it cheaper (via quantization), faster to build (via GPU acceleration), more flexible (via filtering and multi-vector support), and more accessible (via native support in relational databases like Postgres and MySQL). For any team building semantic search, RAG, or recommendation systems today, HNSW is very likely already running underneath, whether they’ve explicitly chosen it or not.

import hnswlib
import numpy as np

dim = 1024
num_elements = 100_000

# 1. Declare an HNSW index (cosine space)
index = hnswlib.Index(space="cosine", dim=dim)

# 2. Initialize: M = graph connectivity, ef_construction = build-time search width
index.init_index(
    max_elements=num_elements,
    ef_construction=200,   # higher = better recall, slower build
    M=16,                  # higher = better recall, more memory
)

# 3. Generate example embeddings and add them to the index
data = np.float32(np.random.random((num_elements, dim)))
ids = np.arange(num_elements)
index.add_items(data, ids)

# 4. Set query-time recall/speed trade-off
index.set_ef(50)  # ef must be >= k (number of neighbours requested)

# 5. Query: find the 10 nearest neighbours of a new vector
query_vector = np.float32(np.random.random((1, dim)))
labels, distances = index.knn_query(query_vector, k=10)

print("Nearest neighbour IDs:", labels)
print("Cosine distances:", distances)

# 6. Save/reload the index (graph structure persists to disk)
index.save_index("hnsw_index.bin")
index.load_index("hnsw_index.bin", max_elements=num_elements)