What Is HNSW and Why Is It So Fast?

A deep technical guide to the algorithm powering modern vector search

Introduction

Every AI system that works with embeddings eventually hits the same wall: finding similar vectors in a large dataset, fast enough to serve real-time requests.

When you build a semantic search engine, a recommendation system, or a retrieval-augmented generation (RAG) pipeline, you are converting your data (text, images, audio, user behavior) into high-dimensional vectors using an embedding model. A 768-dimensional vector from a model like OpenAI's text-embedding-3-small is just a list of 768 floating-point numbers that encode the meaning of the original input. Two vectors that are close together in this 768-dimensional space represent inputs that are semantically similar.

The core operation is straightforward: given a query vector, find the k vectors in your database that are closest to it. This is the nearest neighbor problem, and it sits at the heart of similarity search at scale.

At small data sizes, this is trivial. Compare your query to every stored vector, rank by distance, return the top k. But what happens when your dataset grows to 10 million vectors? Or 100 million? Or a billion? That brute force approach collapses under its own weight. The compute cost grows linearly with the dataset, and latency shoots past any reasonable threshold for user-facing applications.

This is the problem that approximate nearest neighbor (ANN) algorithms solve. And among all ANN algorithms in production use today, HNSW has emerged as the clear winner for most workloads. It is the reason engineers frequently search for "hnsw index explained" and "hnsw vs brute force" when choosing vector database indexing strategies.

This article will explain what HNSW is, walk through exactly how it works at every step, explain why it is so fast, and cover the tradeoffs you should understand before using it in production.

What Is HNSW?

HNSW stands for Hierarchical Navigable Small World. It was introduced by Yuri Malkov and Dmitry Yashunin in their 2016 paper "Efficient and Robust Approximate Nearest Neighbor using Hierarchical Navigable Small World Graphs." It is a graph-based index structure designed for approximate nearest neighbor search in high-dimensional spaces.

Let us unpack the name, because each word tells you something important about how it works.

Hierarchical: The data structure is organized into multiple layers stacked on top of each other, like floors in a building. The top floor has very few nodes. Each floor below it has progressively more. The ground floor has every single vector in the dataset.

Navigable: The graph is constructed so that you can efficiently travel from any starting point to any target point using a simple greedy strategy (always move to the neighbor closest to your destination). Not all graphs have this property. HNSW is specifically built to guarantee it.

Small World: This refers to a well-studied phenomenon in network science. In a small world network, most nodes can be reached from any other node in a surprisingly small number of hops, even if the network is very large. Think of human social networks: despite billions of people on the planet, any two individuals are typically connected through about six intermediate acquaintances. HNSW graphs are engineered to have this same property.

What Is Approximate Nearest Neighbor Search?

Before going deeper into HNSW, it helps to understand what "approximate" means in this context and why we accept it.

Exact nearest neighbor search means finding the mathematically closest vectors to your query. You are guaranteed to get the true top-k results. The only way to do this with certainty is to check every vector in the dataset, which has O(n × d) time complexity, where n is the number of vectors and d is their dimensionality.

Approximate nearest neighbor search relaxes this guarantee. Instead of promising the true closest vectors, ANN algorithms promise vectors that are very close to the true closest, with high probability. In exchange for this slight reduction in accuracy, you get dramatically faster search times.

The accuracy of an ANN algorithm is measured by recall. Recall is the fraction of true nearest neighbors that the algorithm actually finds. A recall of 0.99 means that for every 100 true nearest neighbors, the algorithm returns 99 of them. In practice, for most applications (semantic search, recommendations, RAG), a recall of 95% to 99% is indistinguishable from exact search in terms of user experience.

Why Brute Force Breaks at Scale

Let us make the brute force problem concrete with real numbers.

Suppose you have 10 million vectors, each with 768 dimensions, stored as 32-bit floats. To answer a single query:

• You must compute the distance between your query and all 10 million vectors.
• Each distance computation involves 768 multiplications and 768 additions (for cosine similarity or dot product).
• That is roughly 15.36 billion floating-point operations per query.

Even on a modern CPU with SIMD instructions (such as AVX-512), which can achieve 50 to 100+ billion FLOPS for vectorized arithmetic, the practical throughput is significantly lower once you account for memory bandwidth bottlenecks. Loading 10 million 768-dimensional vectors (approximately 30 GB of raw data at 32-bit precision) from memory becomes the true bottleneck, not raw compute. Real-world brute force latency at this scale typically lands in the range of 500 ms to 2 seconds per query, depending on hardware and memory layout.

Now imagine you need sub-10-millisecond latency and 1,000 queries per second. Brute force does not even come close. You would need a massive cluster of machines just to serve a modest query load.

This is not a theoretical concern. It is the reason vector database indexing exists. The HNSW algorithm reduces that 10-million-vector search from seconds to single-digit milliseconds.

The Core Idea: A Layered Express Lane System

Before we get into the formal mechanics, here is an analogy that captures the essential idea.

Imagine you are trying to find a specific house in a country with millions of streets. You could drive down every single street and check every address (brute force). Or you could use a system of express lanes:

1. Interstate highway (top layer): You have a network of highways connecting major cities. From any highway, you can quickly get to the region of the country where your destination is. There are few highways, but they cover long distances.

2. Regional roads (middle layers): Once you exit the highway near the right city, you switch to regional roads. These are denser than highways but still skip over many small streets. They get you to the right neighborhood.

3. Local streets (bottom layer): Finally, you drive down the local streets to find the exact house. Every address is on a local street. This layer has full coverage.

HNSW works exactly like this. The top layers have few nodes connected by long-range links. The bottom layer has every node connected by short-range links. Searching starts at the top and works down, narrowing the search space at each level.

How the HNSW Algorithm Works

The HNSW algorithm has two fundamental operations: inserting a node (building the index) and searching for nearest neighbors (querying the index). Both use the same layered graph structure, and understanding insertion is the key to understanding why search works so well.

The Layer Structure in Detail

The graph has multiple layers, numbered from layer 0 (the bottom, densest layer) up to some maximum layer L (the top, sparsest layer).

Every vector in the dataset exists in layer 0. This is the ground truth layer. It contains all the data.

A subset of vectors also exists in layer 1. A smaller subset exists in layer 2. An even smaller subset exists in layer 3. And so on, all the way up.

How is it decided which vectors appear in which layers? When a new vector is inserted, the algorithm randomly assigns it a maximum layer using this formula:

max_layer = floor(-ln(uniform(0, 1)) × mL)

where uniform(0, 1) draws a random number from the open interval (0, 1) - excluding 0 to avoid an undefined ln(0) - and mL is the level multiplier, a separate parameter that controls how quickly layers thin out. A common default used in most implementations is mL = 1 / ln(M), where M is the maximum number of connections per node. With this default, the formula becomes:

max_layer = floor(-ln(uniform(0, 1)) × (1 / ln(M)))

This formula produces an exponential distribution. Let us see what that means in practice with a dataset of 1 million vectors and M = 16:

• Layer 0: ~1,000,000 vectors (100% of the data)
• Layer 1: ~62,500 vectors (about 1/16th)
• Layer 2: ~3,906 vectors (about 1/256th)
• Layer 3: ~244 vectors
• Layer 4: ~15 vectors
• Layer 5: ~1 vector (the entry point)

The numbers drop off fast. This exponential thinning is what creates the hierarchical structure. The top layers are extremely sparse and provide a bird's-eye view of the data. The bottom layer is fully dense and provides exact local detail.

How Edges Are Formed: Building the Small World

Within each layer, nodes are connected to their nearest neighbors by edges. But HNSW does not just connect each node to its absolute closest neighbors. It uses a heuristic that balances two goals:

1. Short-range edges connect nodes that are very close together. These provide precise local navigation.

2. Long-range edges connect nodes that are farther apart but in different clusters or regions. These provide the "small world" property and allow fast traversal across large distances.

The selection heuristic prefers neighbors that are close to the new node but also in different directions from each other. This is what prevents the graph from becoming a tightly clustered local mess and instead creates a navigable network where you can reach any region quickly.

Example: Suppose you are adding a node representing the sentence "How to train a neural network" to the graph. Its nearest neighbors might include vectors for "deep learning tutorial," "backpropagation explained," and "machine learning basics." But the heuristic might also keep an edge to a slightly more distant node like "GPU computing for data science," because that node provides access to a different region of the vector space that would otherwise require many hops to reach.

Node Insertion: Step by Step

Here is exactly what happens when a new vector v is inserted into an HNSW index:

Step 1: Determine the maximum layer. The algorithm uses the randomized formula above to assign a maximum layer l to the new node. Most of the time, l = 0, meaning the node only appears in the bottom layer. Occasionally, l = 1 or higher.

Step 2: Find the entry point. The index maintains a single global entry point, which is the node with the highest assigned layer. Insertion starts here.

Step 3: Traverse layers above l. Starting from the entry point at the topmost layer, the algorithm greedily descends through layers that are above the new node's assigned layer. At each of these layers, it simply finds the node closest to v and uses it as the starting point for the next layer down. No new edges are created at these layers because the new node does not exist here.

Step 4: Insert and connect at layers l down to 0. At each layer from l down to 0, the algorithm:

• Searches the current layer to find the M closest existing nodes to v (using a beam search with a candidate list of size efConstruction).
• Creates bidirectional edges between v and these M neighbors.
• For each neighbor that now has too many connections (more than a maximum threshold, typically 2*M for layer 0 and M for higher layers), it prunes the neighbor's edge list by removing the least useful connection using the diversity heuristic described in the original paper.

Step 5: Update entry point if needed. If the new node's assigned layer is higher than the current entry point's layer, the new node becomes the entry point.

The key insight is that the insertion process itself performs a search. Every time you add a node, you are navigating the existing graph to find the right place to put it. This means the graph is built incrementally, and each new insertion benefits from (and improves) the existing structure.

Search Process: Step by Step

Searching for the k nearest neighbors to a query vector q follows a similar top-down path:

Step 1: Start at the entry point on the highest layer.

Step 2: Greedy search on upper layers. At each layer above layer 0, the algorithm performs a simple greedy walk: from the current node, it checks all neighbors, moves to the neighbor closest to q, and repeats until no neighbor is closer than the current node. When the greedy search stalls (no improvement possible), it drops down to the next layer, carrying the current best node as the starting point.

At these upper layers, the algorithm only keeps track of a single closest node. This is fast because the upper layers are sparse and the greedy walk converges quickly.

Step 3: Beam search on layer 0. The bottom layer is where the real work happens. Here, instead of tracking just one candidate, the algorithm maintains a priority queue of efSearch candidates. It explores the neighbors of the best unexplored candidate, adds any that are closer than the worst candidate in the queue, and continues until no more improvements can be found. This wider search produces more accurate results than a single greedy walk.

Step 4: Return the top k results. From the efSearch candidates explored at layer 0, the algorithm returns the k closest to the query.

Example walkthrough: Suppose you have 10 million vectors in 5 layers, and you search for the query "best Italian restaurants in Brooklyn":

1. Layer 4 (1 node): Start at the single entry point. It is the only option, so drop down.

2. Layer 3 (~15 nodes): Greedy walk finds the node closest to the query among the connected nodes. This might be a vector for "food and dining recommendations." Drop down.

3. Layer 2 (~3,900 nodes): Greedy walk navigates to a region related to "restaurant reviews in New York." Drop down.

4. Layer 1 (~62,500 nodes): Greedy walk refines to "Italian dining in NYC neighborhoods." Drop down.

5. Layer 0 (10M nodes): Beam search with efSearch=128 explores 128 candidates in the local neighborhood, comparing vectors for specific Italian restaurants in Brooklyn. Returns the top k.

The total number of distance computations across all layers might be 500 to 2,000, compared to 10 million for brute force.

Why Greedy Search Works Here

Greedy algorithms are generally unreliable. They can get stuck in local optima and miss the global best answer. So why does greedy search work so well in HNSW?

Two reasons:

First, the upper layers prevent local optima. Because the upper layers are sparse and have long-range connections, the greedy walk at the top quickly jumps to the correct region of the space. By the time the algorithm reaches the dense bottom layer, it is already in the right neighborhood. The risk of a local optimum at layer 0 is much lower because the starting point is already good.

Second, the small world structure guarantees short paths. The careful construction of edges during insertion ensures that every region of the space is reachable in O(log n) hops from any starting point. Even if the greedy walk is not perfect, it converges quickly because the graph topology supports it.

Why O(log n) Complexity Emerges

The logarithmic query time is a direct consequence of the hierarchical structure:

• The number of layers is O(log n), because layer assignment follows an exponential distribution.
• At each layer, the greedy search visits a constant number of nodes (bounded by the degree of the graph, which is M).
• Therefore, the total number of nodes visited is O(M × log n), which simplifies to O(log n) since M is a fixed constant.

A note on rigor: The O(log n) complexity is an empirically observed average-case behavior, consistently confirmed in benchmarks and the original paper's experiments, rather than a formally proven worst-case bound. The actual number of distance computations per query depends on graph quality, data distribution, dimensionality, and the efSearch setting. In practice, doubling your dataset from 10 million to 20 million vectors adds roughly one more layer and a small constant to query time. It does not double the work.

HNSW vs Brute Force

The table below provides a concrete comparison that engineers can use when deciding between HNSW and brute force for their workload.

A few things stand out from this comparison.

The latency gap grows with scale. At 1 million vectors, brute force is slow but survivable for some use cases. At 100 million vectors, it is unusable for anything interactive. HNSW barely notices the difference.

Brute force has zero overhead. There is no index to build, no extra memory to provision, no parameters to tune. If your dataset is small enough (say, under 50,000 vectors), brute force is simpler, exact, and fast enough. Do not over-engineer a small problem.

HNSW trades perfect recall for speed. You will not get 100% recall with HNSW, ever. But you can get 99%+ with proper tuning, and for most applications, the 1% of missed results has no measurable impact on user experience or downstream model performance.

Why Is HNSW So Fast?

Understanding HNSW's speed requires looking beyond the big-O notation. Several architectural properties contribute to its real-world performance.

Navigable Small World Properties

The core mathematical insight is that HNSW graphs are "navigable." In a navigable graph, greedy routing (always move to the neighbor closest to the destination) succeeds with high probability. This is not true of random graphs or most real-world networks. It is a property that must be engineered during construction.

HNSW achieves navigability by ensuring that each node has a mix of short-range and long-range connections. The long-range connections are what make greedy routing work across large distances. Without them, the greedy algorithm would get stuck in clusters and fail to find distant targets.

Layered Pruning of the Search Space

This is perhaps the most important practical speedup. The hierarchical layers mean that the algorithm starts its search in a space with very few nodes and progressively increases resolution.

Consider a dataset of 100 million vectors:

• Layer 5 might have 10 nodes. The algorithm checks a handful.
• Layer 4 might have 160 nodes. The algorithm checks a few dozen.
• Layer 3 might have 2,500 nodes. The algorithm checks maybe 50.
• Layer 2 might have 40,000 nodes. The algorithm checks maybe 100.
• Layer 1 might have 625,000 nodes. The algorithm checks maybe 150.
• Layer 0 has 100,000,000 nodes. The algorithm checks maybe 200 (bounded by efSearch).

Total nodes visited: roughly 500 to 600, out of 100 million. That is a reduction of five orders of magnitude.

Reduced Candidate Set Exploration

At the bottom layer, the beam search is bounded by efSearch. This parameter (typically 64 to 256) caps the number of candidates the algorithm evaluates. Instead of comparing the query against millions of vectors, it compares against a few hundred that are already known to be in the right neighborhood.

This is possible because the upper layers have already done the work of navigating to the correct region. The bottom layer search is a local refinement, not a global scan.

Cache Locality and Memory Access Patterns

This is an underappreciated factor. On modern CPUs, the time to compute a distance between two vectors is often dominated by memory access latency, not arithmetic. If the data the CPU needs is already in the L1 or L2 cache, the computation is fast. If it has to be fetched from main memory, it is 50 to 100x slower.

HNSW has good cache behavior for two reasons:

1. Sequential neighbor access: When the algorithm visits a node, it reads that node's neighbor list and then visits those neighbors. The neighbor list is a contiguous array of node IDs, which is cache-friendly.

2. Locality in the graph corresponds to locality in memory: Nodes that are connected by edges tend to be close in the vector space, and implementations often store nearby vectors close together in memory. This means visiting a node's neighbors often hits the cache.

Tree-based ANN methods (like KD-trees or ball trees) tend to have worse cache behavior because tree traversal jumps around in memory more unpredictably.

Recall vs Speed: A Continuous Tradeoff

Unlike some ANN methods that offer a fixed accuracy level, HNSW gives you a continuous knob. By adjusting efSearch:

• efSearch = 10: Very fast queries (sub-millisecond), but recall might be 80 to 90%.
• efSearch = 64: Fast queries (1 to 3 ms), recall around 95%.
• efSearch = 128: Moderate speed (3 to 8 ms), recall around 98%.
• efSearch = 256: Slightly slower (5 to 15 ms), recall above 99%.
• efSearch = 500+: Approaching brute force speed on the local neighborhood, recall at 99.5%+.

You can choose the exact point on this curve that matches your application's requirements. A chatbot that needs fast responses might use efSearch=64. A medical image retrieval system that cannot afford to miss relevant results might use efSearch=256.

Key Parameters and Tuning

HNSW has three primary parameters, plus the level multiplier. Each one affects different aspects of the index, and understanding their interactions is critical for production deployments.

M (Maximum Connections per Node)

What it controls: M sets the maximum number of bidirectional edges each node maintains at each layer. At layer 0, the limit is typically 2*M; at higher layers, it is M.

How it affects performance:

• Higher M (e.g., 32 to 64): Each node has more connections, meaning the graph is more densely linked. This improves recall because there are more paths to any given target, reducing the chance that the greedy search misses the best route. But it also increases memory usage (each edge stores a node ID) and slows down index construction (more neighbors to evaluate during insertion).

• Lower M (e.g., 8 to 12): Saves memory and speeds up construction, but the graph is sparser and search quality may suffer, especially for high-dimensional data where the local neighborhood structure is more complex.

Recommended range: 12 to 48. A value of 16 is the most common default. For high-dimensional data (1000+ dimensions), values of 32 or higher can improve recall.

Memory impact example: For M=16, each node stores about 16 neighbor IDs (4 bytes each) per layer it appears in. A node at layer 0 can have up to 2*M = 32 neighbors, costing 128 bytes for just the neighbor list. For 10 million nodes, the graph overhead from neighbor lists alone is roughly 1.2 to 1.5 GB, on top of the raw vector storage.

efConstruction

What it controls: efConstruction sets the size of the candidate list used during index building. When a new node is inserted, the algorithm uses a beam search with this many candidates to find the best neighbors for the new node.

How it affects performance:

• Higher efConstruction (e.g., 200 to 400): The insertion algorithm explores more candidates when choosing neighbors for each new node. This produces higher-quality edges, which means better recall at query time. But it increases index build time substantially because every insertion does more work.

• Lower efConstruction (e.g., 50 to 100): Faster index builds, but the graph may have suboptimal edges. Poor edges cannot be fully compensated by increasing efSearch later.

Critical point: efConstruction only affects build time, never query time. But the quality of the graph it produces directly impacts how well queries perform. Think of it as the "construction quality" of a road network. Cheap construction (low efConstruction) gives you roads that are not optimally placed. No matter how carefully you drive on them later (high efSearch), you cannot fully make up for poor road layout.

Recommended range: 100 to 400. A value of 200 is a solid default.

efSearch

What it controls: efSearch sets the size of the candidate list used during querying at layer 0. It determines how thoroughly the algorithm explores the local neighborhood around the query.

How it affects performance:

• Higher efSearch: More candidates are evaluated, improving recall but increasing latency.
• Lower efSearch: Fewer candidates, faster queries, lower recall.

Important constraint: efSearch must be at least k, where k is the number of results you want. If you want the top 10 results, efSearch must be at least 10. In practice, you always set efSearch much higher than k.

Recommended range: 64 to 256 for most workloads. Start at 128 and measure recall against a ground truth set. Adjust up or down based on your accuracy and latency requirements.

mL (Level Multiplier)

What it controls: mL controls the probability distribution of layer assignments - how quickly the layers thin out. It appears in the layer assignment formula as the scaling factor applied to -ln(uniform(0, 1)).

Default: 1 / ln(M). This default is used in most implementations and produces a layer structure where each successive layer contains roughly 1/M of the nodes from the layer below. Tuning this parameter is rarely necessary; the default works well for the vast majority of workloads.

Parameter Interaction Summary

When to Use HNSW and When Not To

HNSW Is the Right Choice For:

RAG (Retrieval-Augmented Generation) systems. RAG pipelines retrieve relevant document chunks to provide context for LLM responses. Latency matters because the retrieval step runs on every user query. HNSW gives you sub-10ms retrieval even at millions of documents.

Semantic search. Whether you are building search over a product catalog, a knowledge base, or a document repository, HNSW handles the combination of large scale and low latency that semantic search demands.

Recommendation engines. User and item embeddings often number in the tens of millions. Real-time recommendations require finding the most similar items to a user's embedding in milliseconds. HNSW is built for this.

AI agents with memory retrieval. Agents that retrieve past conversations or relevant knowledge from vector stores need fast, reliable recall. HNSW makes this possible even as the agent's memory grows to millions of entries.

Large embedding collections. Any application storing more than 100,000 vectors and requiring sub-second retrieval benefits from HNSW indexing.

Most modern vector databases, including systems like Endee, implement or optimize HNSW for production-scale workloads. It has become the de facto standard because the combination of tunable recall, logarithmic scaling, and practical performance at billion-vector scale is hard to beat.

When Brute Force Is Still Acceptable:

Small datasets (under 50,000 vectors). At this scale, brute force is fast enough for most latency requirements, and you avoid the complexity of building and maintaining an index.

Exact recall is non-negotiable. If your application truly cannot tolerate missing any nearest neighbor (rare, but possible in some scientific or compliance contexts), brute force is the only guarantee.

Highly dynamic data with constant insertions and deletions. If your dataset changes so rapidly that the index cannot keep up, and the dataset is small enough, brute force avoids the index maintenance problem entirely.

When Other ANN Algorithms Might Make Sense:

IVF (Inverted File Index): IVF-based methods partition the vector space into clusters using k-means and only search the most relevant clusters. They use less memory than HNSW because they do not store a graph. They work well for very large, relatively static datasets where memory is the primary constraint. However, they generally offer lower recall than HNSW at the same query speed.

Product Quantization (PQ): PQ compresses vectors into much smaller representations (e.g., from 768 floats to 96 bytes), dramatically reducing memory. It is often combined with IVF (IVF-PQ) for large-scale deployments. The tradeoff is reduced accuracy due to the lossy compression.

DiskANN: For datasets that do not fit in RAM, DiskANN stores the graph on SSD and uses a carefully designed access pattern to minimize disk reads. It trades some latency for the ability to handle billion-scale datasets on a single machine without massive RAM.

Limitations and Tradeoffs

HNSW is not a silver bullet. Understanding its limitations is just as important as understanding its strengths.

Memory Amplification

The graph structure requires storing neighbor lists for every node at every layer. For a typical configuration (M=16), the graph overhead is roughly 0.5x to 1x the size of the raw vector data. For a dataset of 10 million 768-dimensional vectors stored as float32:

• Raw vectors: 10M × 768 × 4 bytes = ~28.7 GB
• HNSW graph overhead: ~14 to 28 GB additional
• Total: ~43 to 57 GB

For billion-vector datasets, this memory requirement pushes into the hundreds of gigabytes or even terabytes. This is the primary cost of HNSW and the main reason some teams choose IVF-PQ or DiskANN for very large datasets.

Expensive Index Construction

Building an HNSW index is not cheap. Each of the n vectors must be inserted into the graph, and each insertion involves searching the existing graph (O(log n) cost). The total build cost is O(n log n).

Concrete example: Building an HNSW index over 10 million 768-dimensional vectors with efConstruction=200 and M=16 takes roughly 30 to 90 minutes on a modern multi-core server, depending on hardware and implementation. For 100 million vectors, expect several hours.

This means you cannot rebuild your index on every update. Most production systems use incremental insertion (adding new vectors to the existing graph) and periodic full rebuilds during maintenance windows. In serverless architectures like Endee, this construction cost is managed transparently so you do not need to provision or babysit long-running indexing jobs.

Deletions Are Non-Trivial

Removing a vector from an HNSW graph is harder than it sounds. The deleted node may serve as a critical bridge between two regions of the graph. Simply removing it and its edges can create "dead zones" where nearby vectors become unreachable or require many more hops to reach.

Most implementations handle this with soft deletes: the node is marked as deleted and skipped during search, but its edges remain in the graph. Over time, as more nodes are soft-deleted, the graph quality degrades and a full rebuild becomes necessary.

Some newer implementations support "repair" operations that rewire the neighbors of deleted nodes, but this adds complexity and computational overhead.

No Guarantee of Perfect Recall

HNSW is, by definition, an approximate algorithm. Even with very high efSearch values, there is always a nonzero probability that the algorithm misses a true nearest neighbor. The greedy routing can occasionally take a suboptimal path, and the finite beam width at layer 0 means some candidates are never evaluated.

For most applications, recall above 99% is achievable and sufficient. But if your use case requires mathematical guarantees of exact results (e.g., certain types of scientific computation or regulatory compliance), HNSW cannot provide them.

Data Distribution Sensitivity

HNSW's performance can vary depending on the distribution of your data. It works best when vectors are roughly uniformly distributed in the space or form well-separated clusters. If the data has unusual structure (e.g., many near-duplicate vectors, extreme clustering, or very high intrinsic dimensionality), the graph may not form optimal connections, and recall can suffer.

In practice, embeddings from modern models (BERT, OpenAI, Cohere, etc.) tend to produce well-behaved distributions that work well with HNSW.

Rebalancing Is Not Automatic

Unlike B-trees or other self-balancing data structures, HNSW graphs do not automatically rebalance when the data distribution changes. If you build an index on one distribution of data and then add a large batch of vectors from a very different distribution, the existing graph structure may not serve the new data well. Long-range connections built for the original data might not point toward the new regions.

The practical solution is periodic full rebuilds, which is feasible for most workloads but adds operational complexity.

Conclusion

HNSW became the dominant algorithm in vector database indexing because it solved the right problem at the right time, with the right tradeoffs. As AI systems moved from research prototypes to production deployments, the need for fast, scalable, tunable similarity search became unavoidable. HNSW delivered exactly that.

Its hierarchical layering provides logarithmic search complexity that scales gracefully from thousands to billions of vectors. Its small world graph construction ensures that greedy routing converges quickly and reliably. Its three tunable parameters (M, efConstruction, efSearch) give operators direct, independent control over memory usage, build time, and the recall-latency tradeoff. And its practical performance, single-digit millisecond queries over datasets of hundreds of millions of vectors - makes it the natural backbone for production vector search systems.

But understanding HNSW also means understanding what it costs: significant memory overhead, expensive index construction, challenging deletions, and the fundamental limitation that it cannot guarantee perfect recall. These tradeoffs are acceptable for the vast majority of workloads, but they should be understood clearly before making infrastructure commitments.

If you are evaluating a vector database or building a similarity search pipeline, understanding the HNSW algorithm is one of the most valuable investments you can make. It is not just an implementation detail. It is the foundation that determines whether your system can deliver accurate results, at low latency, at the scale your application demands.