IVF Index: Clustering-Based Vector Search & Partitioning › IVF vs HNSW

Both IVF and HNSW (covered in the previous chapter) are workhorses of approximate nearest neighbor search, but they make fundamentally different tradeoffs. Understanding when to use each one is necessary for building effective RAG systems.

HNSW builds a multi-layer proximity graph where each vector is a node connected to its approximate nearest neighbors. Search proceeds by greedy traversal from the top layer down. The graph structure must be stored alongside the vectors, adding memory overhead.

IVF partitions the space using clustering and stores vectors in inverted lists. Search identifies relevant clusters and scans their contents exhaustively. The overhead is just the centroids, which is minimal.

HNSW requires storing the graph edges. With a typical parameter $M = 16$ connections per node, each vector requires additional memory for graph storage. We calculate this overhead to understand the concrete cost.

Graph storage per vector:

Each node in the HNSW graph stores $M$ bidirectional connections, where each connection is represented by a 4-byte integer (the node ID). The bidirectionality means that if node A has an edge to node B, then node B also stores an edge back to node A. Both endpoints must record the connection so that the graph can be traversed efficiently in either direction during search:

$$\begin{aligned} \text{Bytes per vector} &= M \times 2 \times 4 && \text{(bidirectional links as 4-byte integers)} \\ &= 16 \times 2 \times 4 && \text{(substitute } M = 16\text{)} \\ &= 128 \text{ bytes} && \text{(total graph overhead per vector)} \end{aligned}$$

The factor of 2 accounts for bidirectionality because in HNSW's implementation, each edge is stored at both endpoints to let fast traversal in either direction. The factor of 4 comes from using 32-bit integers to store node IDs, which supports datasets of up to approximately 2 billion vectors.

where:

• $M = 16$: the maximum number of connections per node in the HNSW graph
• Factor of 2: accounts for bidirectional links, each edge stored twice (once at each endpoint)
• Factor of 4: bytes per integer, storing node IDs as 32-bit integers

This overhead is independent of vector dimensionality. Whether vectors are 64-D or 768-D, the graph structure costs the same per node. This is an important observation because it means the relative overhead of the graph decreases as vector dimensionality increases.

Overhead percentage for typical embeddings:

To understand whether 128 bytes per vector is significant, we need to compare it against the size of the vectors themselves. For 768-dimensional vectors (common in models like BERT) using 32-bit floats:

$$\begin{aligned} \text{Vector size} &= 768 \times 4 && \text{(dimensions times bytes per float32)} \\ &= 3{,}072 \text{ bytes} && \text{(total size per vector)} \\ \text{Overhead} &= \frac{128}{3{,}072} && \text{(graph bytes divided by vector bytes)} \\ &\approx 4\% && \text{(percentage overhead)} \end{aligned}$$

where:

• $768$: the dimensionality of the embedding vectors
• $4$: bytes per float32 value
• $128$: the graph storage overhead per vector, calculated above
• $3{,}072$: the total size of each 768-dimensional float32 vector in bytes

For higher-dimensional vectors, this percentage overhead decreases (graph cost stays constant while vector cost grows), making HNSW more attractive for very high-dimensional spaces. Conversely, for lower-dimensional vectors (say, 64 dimensions requiring only 256 bytes), the graph overhead of 128 bytes is a 50% increase in memory, which is much more significant.

This overhead is modest, but the key constraint is that the entire graph structure must reside in memory for efficient traversal.

IVF stores centroids ($k \times d$ floats) and vector assignments, which is negligible overhead. More importantly, IVF naturally supports on-disk storage. The inverted lists can be memory-mapped, and only the lists being probed need to be loaded into memory. This makes IVF far more suitable for datasets that don't fit in RAM.

HNSW typically offers better query latency for the same recall level, especially at high recall targets (>95%). The graph traversal naturally focuses on the relevant region of the space and adapts to the local density of the data. HNSW query time is also more predictable, as it doesn't depend on cell sizes.

IVF query time depends heavily on the uniformity of the clustering. If some cells are much larger than others (due to uneven data distributions), probing those cells is disproportionately expensive. However, IVF's simple structure makes it easier to parallelize. You can scan multiple inverted lists concurrently.

IVF requires a training phase (running k-means) before vectors can be added, but this training is relatively fast and adding new vectors is trivial (just assign them to the nearest centroid). Removing vectors is also straightforward.

HNSW builds incrementally. Each vector is inserted by finding its neighbors and adding edges. This can be slow for large datasets and the insertion order can affect quality. Deletion is also more complex because removing a node requires reconnecting its neighbors.

The following table summarizes the key tradeoffs:

Choose IVF when:

• Your dataset is too large to fit entirely in RAM
• You need to combine with Product Quantization for compression
• You need easy updates (adding/removing vectors frequently)
• You're operating at billion-scale

Choose HNSW when:

• Your dataset fits in memory
• You need the highest possible recall at low latency
• You can tolerate the memory overhead of the graph
• You have fewer than ~10 million vectors

In many production systems, the two approaches are combined. FAISS supports an IndexHNSW as the coarse quantizer in an IVF index, replacing the flat centroid comparison with an HNSW graph over the centroids. This gives fast centroid lookup when $k$ is very large.