HNSW Index: Architecture for Fast Vector Search › Limitations and Impact

HNSW has become the de facto standard for approximate nearest neighbor search in production vector databases because it delivers consistently high recall with low latency across a wide range of data distributions and dimensionalities. Like every algorithm, it has tradeoffs that affect design decisions.

The most significant limitation is memory consumption. HNSW requires storing the entire graph structure in RAM, including all vectors and their neighbor lists. For a billion-vector index with 768-dimensional embeddings, the vectors alone require about 3 TB of storage (at 4 bytes per float), and the graph adds substantial overhead on top of that. This makes pure HNSW impractical for very large-scale deployments without compression techniques like Product Quantization or dimensionality reduction.

In contrast, disk-based approaches like IVF indices can handle much larger collections because they only need to load a small subset of vectors into memory for each query. For truly massive collections (billions of vectors), the practical solution is to combine HNSW with quantization: use Product Quantization to compress each vector from full float32 precision to a fraction of its original size, then build the HNSW graph on the compressed representations. This reduces memory by 4x to 32x at the cost of a modest recall penalty. Modern vector databases like Faiss and Milvus support this combination natively.

Another limitation is the construction cost. Building an HNSW index is relatively slow compared to partition-based methods like IVF, because each insertion requires searching the existing graph to find neighbor candidates. The index also cannot be easily split across machines for distributed construction. HNSW indices are append-only in practice: while it is possible to add new vectors incrementally (a significant advantage over methods that require full rebuilds), deleting vectors is not natively supported in most implementations. Deleted nodes leave "holes" in the graph that degrade connectivity over time. This makes HNSW less suitable for collections that change frequently, unless you periodically rebuild the index.

Vector databases handle this in different ways. Qdrant marks deleted vectors as tombstones and periodically re-indexes to remove them. Weaviate rebuilds segments when deletions exceed a threshold. Pinecone's serverless tier handles it transparently in the background. Understanding your update patterns is important when choosing whether HNSW is right for your use case: if you have a mostly-static collection (like a corpus of product descriptions that changes monthly), HNSW is ideal. If your collection changes rapidly (like a news feed where articles expire and new ones are added hourly), a hybrid approach with more frequent rebuilds may be necessary.

For very high-dimensional embeddings (above 1024 dimensions), HNSW's performance can degrade. In these spaces, all vectors are roughly equidistant from any query (the curse of dimensionality), making it hard for the greedy search to make directional progress. Increasing $M$ helps, but at the cost of proportionally higher memory and construction time. Dimensionality reduction via PCA before indexing can mitigate this, though it introduces a small additional approximation. In practice, most sentence embedding models produce vectors in the 384 to 1536 dimensional range, where HNSW performs well without special treatment.

The tuning complexity is another practical concern. While HNSW has only three main parameters ($M$, ef_construction, ef_search), finding the right settings for a given dataset and latency budget requires experimentation. The optimal parameters depend on the data dimensionality, distribution, and the required recall level, and these interactions are not always intuitive. Many organizations run automated parameter sweeps (measuring recall vs. latency across a grid of configurations) to identify the Pareto-optimal point for their use case. The good news is that reasonable defaults ($M = 16$, ef_construction = 200, ef_search = 100) work well for most NLP applications without further tuning.

Despite these limitations, HNSW's impact on the field of vector search has been enormous. Before HNSW, practitioners had to choose between methods with known weaknesses: tree methods that fail in high dimensions, hash methods with difficult precision-recall tradeoffs, and quantization methods that require careful cluster count tuning. HNSW provided a single algorithm that works well across the board, with a clean interface and predictable tuning behavior.

The timing was also perfect. HNSW was introduced in 2016, just as dense retrieval and embedding-based search were beginning to gain traction in NLP. As BERT and its successors demonstrated the power of semantic embeddings, the demand for efficient vector search exploded. HNSW was ready: Hnswlib (the authors' reference C++ implementation) offered production-quality performance, FAISS quickly added HNSW support, and vector databases built on top of both. Today, virtually every major vector database, including Pinecone, Weaviate, Qdrant, Milvus, and Chroma, uses HNSW as either its primary or default index type. The algorithm that powers semantic search in RAG systems is a graph structure inspired by Milgram's letters and skip list pointers.