How much memory overhead is typically introduced by indexes like HNSW or IVF for a given number of vectors, and how can this overhead be managed or configured?

Indexes like HNSW (Hierarchical Navigable Small World) and IVF (Inverted File) introduce memory overhead by storing additional structures to accelerate similarity searches. For HNSW, the overhead primarily comes from maintaining layered graphs where each vector has multiple connections (edges) to neighbors. For example, if each vector in a dataset of 1 million entries has 32 connections (a common default), and each connection is stored as a 4-byte integer, the graph structure alone adds approximately 128 MB of memory. Combined with the vectors themselves (e.g., 1M vectors of 768 dimensions as 32-bit floats = 3 GB), the index adds ~4-5% overhead. IVF, on the other hand, clusters vectors into groups and stores centroids and inverted lists. With 1,024 clusters, IVF might require ~3 MB for centroids (1,024 clusters × 768 dimensions × 4 bytes) plus ~4 MB for inverted lists (1M vector IDs as 4-byte integers), totaling ~7 MB, or <1% overhead for the same dataset. However, scaling IVF to 65,536 clusters increases centroid storage to ~195 MB, pushing overhead to ~7%.

The overhead of HNSW can be managed by adjusting its parameters. For instance, reducing the number of connections per node (M) from 32 to 16 cuts edge storage by half (64 MB instead of 128 MB), though this may lower search accuracy. Similarly, using smaller data types for edges (e.g., 2-byte integers instead of 4-byte) reduces memory but limits the maximum vector count. For IVF, reducing the number of clusters lowers centroid storage but may require scanning more clusters during search, increasing latency. Alternatively, using product quantization (PQ) to compress vectors within IVF clusters can drastically reduce memory. For example, PQ with 8-bit codes cuts vector storage from 3 GB to 0.75 GB while adding minimal overhead for codebooks (~1-2 MB). Both indexes benefit from quantizing the original vectors (e.g., 8-bit integers instead of 32-bit floats) to reduce baseline memory before indexing.

Libraries like FAISS provide configuration options to balance memory and performance. For HNSW, efConstruction and M directly control graph density and memory use. For IVF, nlist (number of clusters) and PQ parameters (m and nbits) allow tuning. Storing parts of the index on disk with caching (e.g., only loading frequently accessed clusters) can also help, though this adds complexity. Developers should profile their datasets: smaller datasets might prioritize HNSW’s accuracy with manageable overhead, while larger datasets could use IVF with PQ for memory efficiency. For example, a 10M vector dataset with IVF-4096 and PQ might use ~3.5 GB (vectors + index) instead of ~38 GB for raw vectors, with minimal accuracy loss.