Optimizing HNSW Index Parameters for Vector Search

Optimizing HNSW Index Parameters for Vector Search

Approximate Nearest Neighbor (ANN) search has become a cornerstone of modern AI applications, from semantic search to recommendation systems and Retrieval-Augmented Generation (RAG). Among the many ANN algorithms available today, Hierarchical Navigable Small World (HNSW) graphs have emerged as one of the most popular and performant choices. However, HNSW is not a plug-and-play solution — its performance depends heavily on how you tune its parameters. This tutorial walks you through what HNSW is, why parameter tuning matters, and how to optimize it for your specific use case.

What is HNSW?

HNSW is a graph-based algorithm for approximate nearest neighbor search. It builds a multi-layer graph where each node represents a vector in your dataset. The top layers contain fewer nodes and serve as "highways" for fast traversal, while the bottom layer contains all nodes and provides fine-grained search. When you query the index, the algorithm starts at the top layer and greedily navigates toward the query, progressively descending through layers until it reaches the bottom, where it performs a more thorough local search.

This hierarchical structure is what gives HNSW its name and its speed. By combining long-range jumps at the top with detailed exploration at the bottom, HNSW achieves sub-linear search times while maintaining high recall. The algorithm was introduced by Malkov and Yashunin in 2016 and has since been implemented in libraries like FAISS, hnswlib, Milvus, Weaviate, pgvector, and Qdrant.

Why Parameter Optimization Matters

HNSW exposes three primary parameters that control the trade-off between search speed, recall, memory usage, and index build time. Getting these wrong can lead to several problems:

• Low recall: Your search results miss relevant vectors, degrading application quality.
• Slow queries: Users experience latency that makes real-time applications impractical.
• Excessive memory: The index grows too large to fit in RAM, forcing costly infrastructure decisions.
• Long build times: Indexing takes hours or days, slowing iteration and deployment.

Every dataset and workload is different. A configuration that works perfectly for 1 million 128-dimensional vectors may perform poorly on 100 million 768-dimensional vectors. The key is understanding what each parameter does and systematically finding the right balance.

The Three Core HNSW Parameters

M: Maximum Connections Per Node

The M parameter controls how many bi-directional links each node maintains at the lower layers of the graph (layers below the top). A higher M means each node has more neighbors, creating a denser graph. This generally improves recall because the search has more paths to explore, but it also increases memory usage and build time.

Typical values range from 8 to 48. The default in most libraries is 16. For most use cases, M values between 12 and 32 provide a good starting point. If your vectors are high-dimensional (e.g., 768 or 1024 dimensions from transformer models), you may benefit from slightly higher M values because the "curse of dimensionality" makes navigation harder in high-dimensional spaces.

Memory-wise, each connection requires storing an integer identifier. With M=16, each node stores roughly 32 links (incoming plus outgoing), which at 4 bytes per integer adds about 128 bytes per node. For 10 million vectors, that is approximately 1.2 GB just for the graph structure — before even storing the vectors themselves.

ef_construction: Build-Time Candidate List Size

The ef_construction parameter controls the size of the dynamic candidate list used during index construction. When a new vector is inserted, the algorithm explores the graph to find its neighbors. ef_construction determines how many candidates the algorithm considers before selecting the final M neighbors.

A higher ef_construction leads to a better-quality graph with more optimal connections, which translates to higher recall at search time. However, it also significantly increases build time. Typical values range from 100 to 500, with 200 being a common default.

Because ef_construction only affects build time and not query latency or memory (beyond minor graph quality differences), it is often worth setting it relatively high if you can afford the build time. A well-constructed graph pays dividends every time you query it.

ef_search: Query-Time Candidate List Size

The ef_search parameter controls the size of the dynamic candidate list during search. It determines how many nodes the algorithm explores at the bottom layer before returning the top-k results. This is the most important parameter for the speed-recall trade-off at query time.

Higher ef_search means better recall but slower queries. Lower values mean faster queries but potentially missing relevant results. Crucially, ef_search must always be greater than or equal to k (the number of results you want to return). Typical values range from 50 to 500 depending on your recall requirements.

One of the advantages of ef_search is that it can be adjusted at query time without rebuilding the index. This makes it ideal for A/B testing and for adapting to different workloads — you might use a high ef_search for batch processing and a lower one for real-time user-facing queries.

Practical Implementation with hnswlib

Let us look at how to build and query an HNSW index using the popular hnswlib Python library. First, install the package:

pip install hnswlib numpy

Here is a complete example that builds an index, queries it, and measures recall:

import hnswlib
import numpy as np
import time

# Generate synthetic data: 100,000 vectors of dimension 128
np.random.seed(42)
num_elements = 100_000
dim = 128
data = np.random.rand(num_elements, dim).astype(np.float32)

# Split into database and query sets
num_queries = 1_000
db_data = data[num_queries:]
query_data = data[:num_queries]

# Build the HNSW index
index = hnswlib.Index(space='cosine', dim=dim)

index.init_index(
    max_elements=num_elements - num_queries,
    ef_construction=200,
    M=16
)

start_time = time.time()
index.add_items(db_data, np.arange(len(db_data)))
build_time = time.time() - start_time
print(f"Index build time: {build_time:.2f}s")

# Set ef_search for querying
index.set_ef(100)

# Query the index
k = 10
start_time = time.time()
labels, distances = index.knn_query(query_data, k=k)
query_time = time.time() - start_time
print(f"Query time for {num_queries} queries: {query_time:.4f}s")
print(f"Per-query time: {(query_time / num_queries) * 1000:.2f}ms")

Measuring Recall Against Ground Truth

To know whether your parameters are well-tuned, you need to measure recall — the fraction of true nearest neighbors that your HNSW search actually finds. Here is how to compute it:

from sklearn.neighbors import NearestNeighbors

# Compute ground truth using brute-force search
print("Computing ground truth...")
brute = NearestNeighbors(n_neighbors=k, metric='cosine', algorithm='brute')
brute.fit(db_data)
true_labels = brute.kneighbors(query_data, return_distance=False)

# Compute recall@k
correct = 0
total = 0
for i in range(num_queries):
    true_set = set(true_labels[i])
    found_set = set(labels[i])
    correct += len(true_set & found_set)
    total += k

recall = correct / total
print(f"Recall@{k}: {recall:.4f}")

Systematic Parameter Tuning

Rather than guessing parameter values, you should run a systematic sweep. The following script tests different combinations of M and ef_search to find the best speed-recall trade-off:

import hnswlib
import numpy as np
import time
from sklearn.neighbors import NearestNeighbors

# Prepare data
np.random.seed(42)
num_elements = 50_000
dim = 128
data = np.random.rand(num_elements, dim).astype(np.float32)
num_queries = 500
query_data = data[:num_queries]
db_data = data[num_queries:]

# Ground truth
brute = NearestNeighbors(n_neighbors=10, metric='cosine', algorithm='brute')
brute.fit(db_data)
true_labels = brute.kneighbors(query_data, return_distance=False)

# Parameter sweep
M_values = [8, 16, 24, 32]
ef_search_values = [50, 100, 200, 400]
k = 10

print(f"{'M':>4} | {'ef_search':>10} | {'Recall@10':>10} | {'Latency(ms)':>12} | {'Index Size(MB)':>15}")
print("-" * 65)

for M in M_values:
    index = hnswlib.Index(space='cosine', dim=dim)
    index.init_index(max_elements=len(db_data), ef_construction=200, M=M)
    index.add_items(db_data, np.arange(len(db_data)))

    for ef_search in ef_search_values:
        index.set_ef(ef_search)

        start = time.time()
        labels, _ = index.knn_query(query_data, k=k)
        latency = (time.time() - start) / num_queries * 1000

        correct = sum(len(set(true_labels[i]) & set(labels[i])) for i in range(num_queries))
        recall = correct / (num_queries * k)

        # Estimate index size
        index_size = index.index_size() / (1024 * 1024)

        print(f"{M:>4} | {ef_search:>10} | {recall:>10.4f} | {latency:>12.2f} | {index_size:>15.2f}")

    del index

This will produce a table showing how each parameter combination affects recall, latency, and memory. You can then pick the configuration that meets your recall threshold at acceptable latency.

Using HNSW in pgvector

If you are using PostgreSQL with the pgvector extension, HNSW is also available. Here is how to create and tune an HNSW index in SQL:

-- Enable the extension
CREATE EXTENSION IF NOT EXISTS vector;

-- Create a table with vector column
CREATE TABLE documents (
    id SERIAL PRIMARY KEY,
    content TEXT,
    embedding VECTOR(768)
);

-- Build an HNSW index with tuned parameters
CREATE INDEX ON documents USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 200);

-- Query with a specific ef_search
SET hnsw.ef_search = 100;

-- Perform a similarity search
SELECT id, content, embedding <=> '[0.1, 0.2, ...]'::vector AS distance
FROM documents
ORDER BY embedding <=> '[0.1, 0.2, ...]'::vector
LIMIT 10;

Note that in pgvector, ef_search is set at the session level using SET, which means you can adjust it per query or per connection without rebuilding the index.

Using HNSW in FAISS

FAISS also supports HNSW through its IndexHNSWFlat class. Here is an example:

import faiss
import numpy as np

dim = 128
num_elements = 100_000

data = np.random.rand(num_elements, dim).astype(np.float32)

# Create HNSW index
index = faiss.IndexHNSWFlat(dim, 16)  # M = 16
index.hnsw.efConstruction = 200
index.hnsw.efSearch = 100

# Build the index
index.add(data)

# Query
query = data[:5]
distances, labels = index.search(query, k=10)
print("Nearest neighbors:", labels)

Best Practices for HNSW Optimization

Start with Sensible Defaults

If you are unsure where to begin, use M=16, ef_construction=200, and ef_search=100 as your starting point. These values work well for many datasets and give you a baseline to improve from. From there, adjust based on your measurements.

Prioritize ef_construction During Build

Since ef_construction only affects build time and not query performance, set it as high as your build-time budget allows. A value of 200 is good; 400 or 500 is better if you can afford it. The quality of the graph you build determines the ceiling of your recall at any given ef_search level.

Tune ef_search Based on Your Latency Budget

Start with ef_search equal to ef_construction and then reduce it until recall drops below your acceptable threshold. For many applications, a recall@10 of 0.95 or higher is sufficient. If you need 0.99+ recall, you may need significantly higher ef_search values, and in some cases, brute-force search might actually be competitive.

Normalize Your Vectors

If you are using cosine similarity, normalize your vectors before indexing. This allows you to use the inner product (or L2) space, which is computationally cheaper than cosine space. In hnswlib, you can use space='cosine' which handles normalization internally, but in FAISS, you should normalize manually:

import faiss
import numpy as np

data = np.random.rand(10000, 128).astype(np.float32)

# Normalize vectors for cosine similarity
faiss.normalize_L2(data)

# Use inner product space
index = faiss.IndexHNSWFlat(128, 16, faiss.METRIC_INNER_PRODUCT)
index.hnsw.efConstruction = 200
index.add(data)

Consider Dimensionality Reduction

If your vectors are very high-dimensional (e.g., 768 or 1024 dimensions), consider applying PCA or quantization before indexing. Reducing dimensions from 768 to 256 can dramatically reduce memory usage and improve search speed with minimal recall loss, especially if your vectors have redundant dimensions.

Benchmark on Real Data

Never tune parameters on synthetic random data alone. Random vectors behave differently from real embeddings — real embeddings often have cluster structure that HNSW can exploit. Always validate your parameter choices on a representative sample of your actual production data.

Account for Updates

HNSW supports incremental insertions, but frequent deletions can degrade graph quality over time. If your dataset changes frequently, consider periodically rebuilding the index from scratch with a high ef_construction to maintain optimal graph structure.

Monitor Recall in Production

Recall can drift over time as your dataset grows. Set up a monitoring pipeline that periodically runs a set of known queries against both the HNSW index and a brute-force search on a sample of your data. If recall drops below your threshold, it may be time to rebuild the index or increase ef_search.

Conclusion

Optimizing HNSW index parameters is a balancing act between recall, latency, memory, and build time. The three core parameters — M, ef_construction, and ef_search — each control a different aspect of this trade-off, and finding the right combination requires systematic experimentation on your actual data. Start with sensible defaults, measure recall against ground truth, and iterate. Remember that ef_construction is a build-time investment that pays off in query quality, while ef_search is your runtime dial for adjusting the speed-recall trade-off on the fly. By following the practices and code patterns in this tutorial, you can build vector search systems that are both fast and accurate, scaling from thousands to millions of vectors while keeping latency low and recall high.