Why HNSW is Not the Answer to Vector Databases

HNSW (Hierarchical Navigable Small World) has become the algorithm of choice for many vector databases. Its multi-layer graph structure and ability to efficiently navigate vector embedding make it particularly attractive. However, despite its obvious advantages, HNSW may not be the best solution for large-scale dynamic vector similarity searching. In this article, we challenge the dominance of HNSW and explore why disk-based alternatives such as IVF (Inverted File Indexing) may be more practical for large data sets.

The appeal of HNSW

HNSW offers several advantages:

• Efficient search: Its graph-based structure enables fast nearest neighbor searches, especially for smaller datasets.

• incremental update: The ability to incrementally add new vectors without rebuilding the index is a major advantage of dynamic environments.

• High recall rate: HNSW provides high recall with relatively low latency, making it ideal for real-time applications.

However, these benefits come with trade-offs that become more apparent as the dataset size increases.

High Tech South Wales Problems

One of the major challenges of HNSW is its heavy reliance on memory for indexing and search operations. Here are the main issues that arise:

• memory overhead: Traversing the graph structure of HNSW involves highly random access patterns. The entire data set must be stored in memory for reasonable performance. This becomes infeasible for large-scale data sets with billions of high-dimensional vectors due to excessive memory requirements.

• Performance sensitivity to memory size: If the memory is even slightly insufficient to hold all the vectors, HNSW’s performance drops dramatically. In this case, swapping the data to disk would significantly affect the seek speed, making it impractical for systems with limited memory.

• Not suitable for disk-based environments: HNSW is essentially designed for in-memory operations and does not perform well in disk-oriented scenarios (such as PostgreSQL). Its reliance on frequent random access patterns makes it incompatible with the sequential access nature of disk storage.

• Insertion and deletion costs:Updating indexes in HNSW involves cascading modifications throughout the graph, resulting in significant computation and write amplification. This makes insert and delete operations slow and resource intensive.

In comparison, disk-based solutions such as IVF excel in scenarios that require scalability and efficiency at the expense of minimal complexity.

Why IVF is faster than HNSW

A key observation of all vector search algorithms is that their performance strongly depends on the number of distance calculations they perform. Minimizing these calculations is critical to increasing search speed. Although the original IVF index required scanning 1% to 5% of the total vectors, modern advances in quantization and optimization have significantly improved its efficiency, making IVF a strong competitor to HNSW.

Quantification: The Game Changer

Quantization compresses high-dimensional vectors into compact representations. For example:

• Rabbit Q: Utilizes the centralization of measurement phenomena to enhance binary and scalar quantization accuracy, quantizing each dimension to 1 bit to obtain a 32x compression ratio.

• Product Quantization (PQ): Operates by dividing a vector space into subspaces and quantizing each subspace independently to minimize the approximation error. This method provides flexible compression ratios from 4x to 64x in FAISS, allowing for finer compression and faster approximate searches.

• Scalar Quantization (SQ): Quantize each vector dimension independently by dividing the range of each vector dimension into discrete levels, typically achieving a 4x compression ratio by converting from float to int8.

• Scanning Neural Networks: Uses anisotropic vector quantization to optimize inner product accuracy by penalizing errors in directions that affect high inner products, resulting in superior recall and speed.

Quantization can significantly reduce memory and disk space usage (typically 32x reduction when converting floating point numbers to bits), while also significantly reducing computational overhead. Despite the loss of accuracy, quantization makes vector comparisons more efficient. For example, a typical distance calculation between two D-dimensional vectors is O(D^2), but compressing floating point to bits reduces this by a factor of 1024 (32×32). Through fast scan optimization, these calculations can be further accelerated through efficient CPU register lookups. Combined with IVF, many quantitative methods consistently outperform HNSW in terms of speed and scalability. Typical workflow includes:

1. preliminary search: Use compressed representation to quickly identify candidate vectors.

2. rerank: Use full-precision distance calculations on a smaller subset of candidates to refine the results.

Compare RaBitQ+IVF and HNSW

IVF with quantification provides an efficient method of storing all quantization vectors in memory. By leveraging RaBitQ, memory usage is reduced by a factor of 32 compared to full-size vectors, allowing the entire quantized data set to fit in memory. This design enables the index to quickly retrieve approximate nearest neighbors using bit vectors and reorder them using full precision vectors obtained from disk. For a typical Top-10 query, IVF only fetches 100-200 vectors from disk, while HNSW may require 800-1000 vectors. This efficient approach achieves the best balance between memory usage and disk access, providing excellent price/performance advantages.

While similar quantification techniques can theoretically be applied to HNSW, practical limitations reduce its effectiveness:

• Vector packaging: The fast scan optimization relies on packing 32 compressed vectors together, which is incompatible with the graph structure of HNSW.

• random access cost: HNSW involves frequent random access across graph nodes and edges, making traversal inefficient. In contrast, IVF organizes vectors sequentially in the release manifest, allowing for faster prefetching and efficient sequential scans.

• reranking cost: Since both IVF and HNSW rely on quantitative representation in the first stage, their reranking computational costs are similar.

Ultimately, the quantitative performance difference between IVF and HNSW may be small, but IVF stands out for its simplicity and efficiency.

IVF is easy to operate

The simplicity of IVF makes it a more practical option in real-world applications:

• Insertion and deletion: In HNSW, these operations trigger cascading modifications throughout the graph, resulting in significant computation and write amplification. In contrast, IVF only requires updates to the relevant release lists.

• disk-based storage: IVF’s reliance on disk-based indexing allows it to scale efficiently without incurring the prohibitive memory costs associated with HNSW.

• Adaptability: IVF can be easily combined with advanced quantitative techniques, allowing for further optimization.

in conclusion

Although HNSW has cemented its reputation as a fast and accurate algorithm for vector similarity searches, it is not without limitations. Its memory-intensive nature and operational complexity make it less suitable for large-scale applications. In contrast, in vitro fertilization offers a scalable and cost-effective alternative, especially when combined with modern quantitative techniques.

As the need for vector hunting continues to grow, practitioners must carefully evaluate the trade-offs between memory-based and disk-based solutions. HNSW may dominate small to medium-sized applications, but for large data sets it is time to move beyond HNSW and adopt simpler, scalable methods (such as IVF).