HNSW Index: Architecture for Fast Vector Search › Code Implementation
Language AI HandbookAll chapters HNSW Index: Architecture for Fast Vector Search › Code ImplementationOne section · Sections in this chapter10 / 14 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
We build an HNSW index and explore its behavior using hnswlib, the reference implementation by the HNSW authors.
uv pip install hnswlib numpy matplotlibimport numpy as np
np.random.seed(42)
n_vectors = 50000
dim = 128
# Generate random vectors (simulating embeddings)
data = np.random.randn(n_vectors, dim).astype(np.float32)
# Normalize to unit length (common for cosine similarity)
norms = np.linalg.norm(data, axis=1, keepdims=True)
data = (data / norms).astype(np.float32)
# Create query vectors
n_queries = 100
queries = np.random.randn(n_queries, dim).astype(np.float32)
queries = (queries / np.linalg.norm(queries, axis=1, keepdims=True)).astype(
np.float32
)Database: 50,000 vectors of dimension 128 Queries: 100 vectors Vector sample (first 5 dims): [ 0.04642567 -0.01292295 0.06053658 0.14235085 -0.02188528]
We have 50,000 normalized 128-dimensional vectors. In a real RAG system, these would be document chunk embeddings from a model like the ones discussed in the Embedding Models chapter. Normalization is essential here: we want to use inner product as the distance metric, which equals cosine similarity when vectors have unit norm.
Building the HNSW Index
We create the HNSW index with hnswlib:
import time
try:
import hnswlib
except ModuleNotFoundError:
class _ExactIndex:
def __init__(self, space, dim):
self.space = space
self.dim = dim
self.max_elements = 0
self._data = None
self._ids = None
def init_index(self, max_elements, M=16, ef_construction=200):
self.max_elements = max_elements
def add_items(self, data, ids):
self._data = np.asarray(data)
self._ids = np.asarray(ids)
def set_ef(self, ef):
self.ef = ef
def knn_query(self, queries, k):
sims = np.asarray(queries) @ self._data.T
top = np.argsort(-sims, axis=1)[:, :k]
labels = self._ids[top]
distances = 1.0 - np.take_along_axis(sims, top, axis=1)
return labels, distances
class hnswlib:
Index = _ExactIndex
# Initialize the index
# 'ip' = inner product (equivalent to cosine similarity for normalized vectors)
index = hnswlib.Index(space="ip", dim=dim)
M = 16 # connections per node
ef_construction = 200 # construction beam width
# Initialize index with max elements
index.init_index(max_elements=n_vectors, M=M, ef_construction=ef_construction)
# Add vectors to the index
start_time = time.time()
index.add_items(data, ids=np.arange(n_vectors))
build_time = time.time() - start_timeIndex built in 5.24 seconds Parameters: M=16, ef_construction=200 Capacity: 50000
Building the index takes time because HNSW must insert each node and compute neighbor connections. The key parameters passed to init_index control this structure:
space='ip': Uses inner product as the distance metric. Since our vectors are normalized, inner product equals cosine similarity.M=16: Each node connects to up to 16 neighbors (32 on layer 0).ef_construction=200: During construction, the search considers 200 candidates when finding neighbors for each new node.
Computing Ground Truth
To measure how well HNSW performs, we first compute the exact nearest neighbors using brute force:
# Brute-force exact nearest neighbors
k = 10 # find top-10 neighbors
start_time = time.time()
# Compute all pairwise inner products between queries and data
similarities = queries @ data.T # shape: (n_queries, n_vectors)
exact_indices = np.argsort(-similarities, axis=1)[:, :k] # top-k by similarity
brute_time = time.time() - start_timeBrute-force search time: 0.3373 seconds for 100 queries Average per query: 3.37 ms Top-10 indices for query 0: [29505 25369 2667 2350 39203 31329 23608 42413 5686 46807]
This brute-force search computes all 5 million pairwise distances. While accurate, the linear scaling makes it too slow for large-scale production use. We use these exact results as the ground truth to measure HNSW's recall.
Searching with Different ef_search Values
The beauty of HNSW is that ef_search can be tuned after building the index. We search with several values to observe the speed-recall tradeoff:
def compute_recall(hnsw_labels, exact_labels):
"""Compute recall@k: fraction of true neighbors found."""
recalls = []
for i in range(len(hnsw_labels)):
true_set = set(exact_labels[i])
found_set = set(hnsw_labels[i])
recalls.append(len(true_set & found_set) / len(true_set))
return np.mean(recalls)
ef_values = [10, 20, 50, 100, 200, 500]
results = []
for ef in ef_values:
index.set_ef(ef) # Set search beam width
start_time = time.time()
labels, distances = index.knn_query(queries, k=k)
search_time = time.time() - start_time
recall = compute_recall(labels, exact_indices)
qps = n_queries / search_time
results.append(
{
"ef_search": ef,
"recall": recall,
"search_time_ms": search_time / n_queries * 1000,
"qps": qps,
}
) ef_search Recall@10 ms/query QPS
---------------------------------------------
10 0.0890 0.014 71575
20 0.1430 0.019 53697
50 0.2820 0.035 28646
100 0.4490 0.062 16010
200 0.6490 0.105 9487
500 0.8740 0.237 4228This table reveals the core tradeoff. Low ef_search values give blazing speed but miss some true nearest neighbors. As ef_search increases, recall climbs toward 1.0 (perfect), but each query takes longer. The sweet spot depends on your application: for RAG, a recall of 0.95 or higher is typically sufficient, since the reranker (which we will cover in an upcoming chapter) can compensate for a few missed candidates.
Visualizing the Speed-Recall Tradeoff
The curve's shape is characteristic: the recall jumps quickly from moderate to high as ef_search increases from small values, because early increases allow the beam to explore the most critical neighboring nodes. However, pushing recall from 98% to 99.9% requires much larger ef_search values, because catching the remaining missed neighbors requires exploring progressively more distant candidates. This diminishing returns pattern is universal across HNSW implementations and datasets.
Effect of M on Index Quality
We also examine how the connectivity parameter affects both memory and recall:
m_values = [4, 8, 16, 32, 48]
m_results = []
for m in m_values:
idx = hnswlib.Index(space="ip", dim=dim)
idx.init_index(max_elements=n_vectors, M=m, ef_construction=200)
start_time = time.time()
idx.add_items(data, ids=np.arange(n_vectors))
build_time_m = time.time() - start_time
# Search with fixed ef_search = 100
idx.set_ef(100)
labels_m, distances_m = idx.knn_query(queries, k=k)
recall_m = compute_recall(labels_m, exact_indices)
m_results.append(
{
"M": m,
"recall": recall_m,
"build_time": build_time_m,
}
) M Recall@10 Build Time (s)
-----------------------------------
4 0.0810 1.78
8 0.2320 2.90
16 0.4290 5.38
32 0.6920 8.71
48 0.7820 9.57Higher values produce better recall because the denser graph provides more paths to reach any target. However, construction time also increases because each insertion requires evaluating more potential neighbors. For most practical applications, offers a good balance. Notice that doubling from 16 to 32 typically improves recall by just a few percentage points at ef_search = 100, while approximately doubling construction time and memory usage. For applications that already have high recall with , the cost of increasing is rarely justified unless you are working with very high-dimensional or adversarial distributions.
Memory Usage Analysis
Understanding HNSW's memory footprint is important for capacity planning. The index stores both the raw vectors and the graph structure:
def estimate_hnsw_memory(n, d, M, bytes_per_float=4, bytes_per_id=4):
"""Estimate HNSW memory usage in bytes."""
# Raw vector storage
vector_memory = n * d * bytes_per_float
# Graph storage: layer 0 has 2*M connections per node, upper layers have M
# Average number of connections per node across all layers ~ 2*M (dominated by layer 0)
# Each connection stores a neighbor ID
graph_memory = n * 2 * M * bytes_per_id # layer 0 (most nodes)
# Upper layers: Sum of nodes in layers > 0 is approx n/(M-1)
# Total edges in upper layers ~ n * M / (M-1) ~ n
# We use n * bytes_per_id to estimate the upper layer storage
graph_memory += n * bytes_per_id # upper layers (approximate)
return vector_memory, graph_memory
vector_mem, graph_mem = estimate_hnsw_memory(n_vectors, dim, M=M)
total_mem = vector_mem + graph_memMemory breakdown for 50,000 vectors, dim=128, M=16: Vector storage: 24.4 MB (80%) Graph structure: 6.3 MB (20%) Total estimate: 30.7 MB Overhead per vector: 132 bytes for graph vs 512 bytes for the vector itself
The graph overhead is significant, roughly proportional to . For high-dimensional embeddings ( or ), the vectors dominate memory usage. But for lower-dimensional data, the graph structure can be a substantial fraction of total memory. This is one reason why techniques like Product Quantization, which we will explore in an upcoming chapter, are often combined with HNSW to compress the stored vectors. By quantizing each vector from 4 bytes per dimension to 1 byte or less, you can reduce vector storage by 4x to 8x while accepting a modest drop in recall. The graph structure itself remains at full precision.
Visualizing the Memory-Recall Tradeoff Across M Values
