An HNSW index is an algorithm for finding the most similar items in a large collection of data represented as vectors. It powers applications like semantic search, recommendation engines, and modern AI systems by trading a small amount of accuracy for a massive gain in speed. This HNSW index explained guide will show you how it works.
Key takeaways
- HNSW is an approximate nearest neighbor (ANN) search algorithm. It uses a multi-layered graph to find similar vectors quickly.
- It works like a road network. Searches start on a sparse "highway" layer for long jumps and descend to dense "local road" layers for precise exploration.
- Performance is controlled by three key parameters.
Maffects graph connectivity and memory,efConstructionaffects build-time quality, andefSearchaffects the query-time balance of speed vs. accuracy. - Tuning HNSW is an empirical process. You must measure recall against an exact search baseline while monitoring latency, memory, and build time to find the right balance for your application.
What Is an HNSW Index?
An HNSW index is a data structure for efficient approximate nearest neighbor (ANN) search. HNSW stands for Hierarchical Navigable Small World. It organizes high-dimensional vectors into a layered graph that allows for fast and scalable similarity searches. This is essential for AI applications like retrieval-augmented generation, which must find relevant information from millions of documents in milliseconds.
The core idea is to create a multi-level graph. Think of it like a national road system.
- The top layers are like interstate highways. They are sparse and have long-range connections, letting you quickly travel across the entire dataset.
- The bottom layer is like local city streets. It is dense and connects every single data point to its close neighbors, allowing for fine-grained, precise searching.
A search starts on the "highway" to find the right general area and then descends to the "local streets" to find the final destination. This hierarchical approach avoids the need to compare a query vector with every other vector in the database, which would be prohibitively slow. Because the search explores a limited path, it is approximate, meaning it finds results that are very likely the closest but without a 100% guarantee (Milvus.io).
How Does an HNSW Index Work, Step by Step?
The HNSW algorithm has two distinct phases: building the index and searching the index. Understanding both is key to using it effectively.
Index Construction (Building the Graph)
This one-time process creates the layered graph structure. For each vector added to the index, the following steps occur:
- Assign a Maximum Layer: Each new vector is randomly assigned a maximum layer to exist in. The probability of being assigned to a higher layer decreases exponentially. This ensures that upper layers remain sparse, acting as expressways, while the bottom layer contains every vector (Milvus.io).
- Find the Entry Point: The process starts at a designated entry point in the highest layer of the graph.
- Search for Neighbors in Upper Layers: From the entry point, the algorithm traverses the graph greedily. At each step, it moves to the neighbor that is closest to the new vector being inserted. This happens on each layer, from top to bottom.
- Connect to Neighbors: Once the algorithm descends to the vector's randomly assigned maximum layer, it begins creating connections. It identifies the nearest neighbors to the new vector at that layer. The search for these neighbors is guided by a parameter called
efConstruction, which defines the size of the candidate pool considered (Microsoft Azure Docs). - Build Bidirectional Links: The new vector is connected to its closest neighbors found in the previous step. The maximum number of connections per node is limited by a parameter
M(Microsoft Azure Docs). This process repeats for each layer, moving downwards until layer 0 is reached.
Search Process (Finding Neighbors)
Once the index is built, it can serve queries very quickly.
- Start at the Top: A query starts at the entry point of the highest layer in the graph.
- Navigate the Highways: The algorithm greedily moves through the graph, always jumping to the neighbor closest to the query vector. This allows it to quickly cross large distances in the vector space.
- Descend and Refine: When it finds a "local minimum" (a point where no neighbor is closer to the query), it descends to the layer below. The node it just found becomes the new entry point for searching this denser layer.
- Explore the Local Roads: This process repeats until the search reaches the bottom layer (layer 0). Here, a more thorough local search is performed. Instead of just following one greedy path, it maintains a dynamic list of candidate nearest neighbors. The size of this list is controlled by the
efSearchparameter (Microsoft Azure Docs). - Return the Best Results: After exploring the neighborhood on the bottom layer, the algorithm returns the k closest vectors from its candidate list as the final result.
A Worked Example: Navigating an HNSW Graph
To make this concrete, imagine a small set of 2D points representing vectors. We have built a two-layer HNSW graph. Layer 1 is the sparse "highway" and Layer 0 is the dense "local" layer.
The Setup:
- Layer 1 (Highway): Contains only points
AandD. There is a connection betweenAandD. The entry point for the whole graph isA. - Layer 0 (Local): Contains all points:
A,B,C,D,E, andF. All points are connected to their immediate neighbors. - Query: A new query point,
Q, arrives. Its true nearest neighbor isE.
The Search Path:
- Start at Layer 1: The search begins at the entry point
Ain Layer 1. - Navigate Layer 1: The algorithm calculates the distance from
QtoAand toA's neighbors in this layer. The only neighbor isD. It finds thatDis closer toQthanAis. So, it jumps fromAtoD. - Find Local Minimum and Descend: At
D, it checksD's neighbors in Layer 1. There are none closer toQ.Dis the local minimum in Layer 1. The algorithm now descends to Layer 0, usingDas the entry point. - Explore Layer 0: The search now begins at
Din the dense bottom layer. It addsDto a candidate list. It then exploresD's neighbors:C,E, andF.- It measures the distance from
QtoC,E, andF. - It finds that
Eis the closest of this group. - Even if the simple greedy path from
Dmight have suggestedCfirst, the expanded search (controlled byefSearch) considers multiple candidates. This allows it to "look around the corner" and discoverE.
- It measures the distance from
- Find the True Neighbor: The candidate list is maintained and pruned. By exploring the neighborhood around
D, the algorithm correctly identifiesEas the closest point toQ. The search terminates and returnsE.
Without the hierarchical structure, the search would have had to calculate the distance from Q to all six points. With it, the search made one long jump on the highway (A to D) and then a small, local exploration to find the answer.
What Do M, efConstruction, and efSearch Mean in HNSW?
The performance of an HNSW index is governed by three critical parameters. They control separate aspects of the build and query processes (OpenSearch Blog).
| Parameter | What It Is | When It's Used | Primary Impact | Main Cost |
|---|---|---|---|---|
M |
The maximum number of bidirectional connections a node can have within a single layer. | Index Construction | Graph Connectivity & Memory. Higher M creates a denser, more navigable graph, which can improve recall. |
Memory & Build Time. Memory usage grows significantly with M. Changing it requires a full index rebuild. |
efConstruction |
The size of the dynamic list of candidate neighbors considered when adding a new vector to the graph. | Index Construction | Graph Quality. A higher value leads to a better-connected graph, increasing the maximum possible recall. | Build Time. Indexing becomes much slower as this value increases, with diminishing returns. |
efSearch |
The size of the dynamic list of candidate neighbors explored during a query. | Query Time | Recall vs. Latency. This is the main runtime knob for tuning the accuracy/speed tradeoff. Higher values improve recall. | Query Latency. The search becomes slower as the algorithm explores more potential neighbors. |
How Do You Tune HNSW for Recall vs. Latency?
Tuning an HNSW index is an empirical process of balancing four competing goals: high recall, low latency, low memory usage, and fast index build time. The central tradeoff you manage at query time is between recall vs latency.
The key tuning parameter for this is efSearch. This value can often be adjusted at query time without rebuilding the index (OpenSearch Blog). The general process is:
- Establish Ground Truth: First, run your queries using a brute-force (exact) search to find the true nearest neighbors. This is your "ground truth" benchmark.
- Define Recall: Recall is the percentage of true nearest neighbors your HNSW search finds. For example, if you want the top 10 neighbors (
k=10) and HNSW finds 9 of the 10 true neighbors, your recall is 90%. - Measure and Iterate: Start with a low
efSearchvalue (e.g., slightly larger than your desiredk). Run your queries, measure recall and query latency (specifically p95 or p99 latency, not just the average). - Increase
efSearch: Incrementally increaseefSearchand repeat the measurements. You will see recall improve as latency increases. Continue this process until you meet your application's recall target or the latency becomes unacceptably high.
When Increasing efSearch Is Not Enough
Sometimes, you'll find that increasing efSearch stops improving recall, or the recall hits a ceiling below your target. This indicates the underlying graph itself is not well-connected enough to navigate to the true neighbors. A wider search at query time cannot fix a poorly built road network (OpenSearch Blog).
In this scenario, you must rebuild the index with higher build-time parameters:
- Increase
efConstruction: This makes the index build slower but results in a higher-quality graph, which can raise the maximum achievable recall. - Increase
M: This creates a denser graph with more connections, improving navigability at the cost of significantly more memory (Microsoft Azure Docs).
When Should You Use HNSW?
HNSW is a powerful tool, but it's not always the best choice. Here is a comparison to help you decide.
| Index Type | Best For | Strengths | Weaknesses |
|---|---|---|---|
| Brute-Force (Flat) | Smaller datasets; applications requiring 100% accuracy. | Perfect recall, simple to implement, no tuning required. | Latency scales linearly with dataset size; becomes too slow for large collections. |
| HNSW | Datasets of all sizes (from thousands to millions) needing a flexible balance of high recall and low latency. | Excellent recall-latency tradeoff. | Memory usage and index build times are significant costs to be managed. Requires careful tuning of its three main parameters. |
Choose brute-force for small projects or when accuracy is paramount. Consider HNSW as the default for most interactive applications needing a good balance of speed and accuracy. You can learn more about how these fit into a larger system in our guide to Vector Database Explained: How Similarity Search Works.
What to learn next
- Hybrid Search BM25 Vector: A Guide to Combining Keyword and Semantic Search: Learn how to combine traditional keyword search with HNSW-powered vector search for more robust results.
- RAG Reranking: How It Improves LLM Answer Precision: Discover how to use a more precise, secondary model to reorder the candidate documents retrieved by a fast initial search like HNSW.
- RAG Evaluation Metrics: A Practical Guide: Understand how to measure the quality of the documents retrieved by your search system and its impact on the final AI-generated answer.
