Vector Indexing Internals: HNSW Graphs, Product Quantization (PQ), and Inverted File (IVF)

Vector indexing is the algorithmic foundation of modern vector databases, semantic search engines, and Retrieval-Augmented Generation (RAG) systems. While exact flat search ( $\text{Flat L2}$ or Cosine) calculates pairwise distances across all $N$ vectors with $O(N \cdot d)$ computational complexity, approximate nearest neighbor (ANN) indexes trade a marginal fraction of recall (typically $95\% - 99\%$ Recall@ $K$ ) for orders-of-magnitude faster queries ( $O(\log N)$ or $O(1)$ ) and reduced RAM footprints.

This article details the mathematical foundations, data structures, and hardware trade-offs of the three primary vector indexing paradigms: Hierarchical Navigable Small World (HNSW), Inverted File (IVF), and Product Quantization (PQ).

1. Quick-Reference: Index Architecture Comparison

+-----------------------------------------------------------------------------------------+
|                               ANN VECTOR INDEX TRADEOFF MATRIX                          |
+-----------------------------------------------------------------------------------------+
| Index Type         | Query Latency (QPS) | Memory Footprint (RAM) | Index Build Time | Recall@10 |
+--------------------+---------------------+------------------------+------------------+-----------+
| Flat (Exhaustive)  | Very Slow (< 50 QPS)| High (100% Float32)    | Instant (0 ms)   | 100%      |
| IVF-Flat           | Fast (~ 1,500 QPS)  | High (100% Float32)    | Fast (K-Means)   | 90 - 95%  |
| HNSW               | Ultra-Fast (>5,000) | Very High (+30% Graph) | Slow (Multi-pass)| 98 - 99.5%|
| IVF-PQ             | Fast (~ 3,000 QPS)  | Ultra-Low (4x-16x comp)| Moderate (Train) | 85 - 93%  |
| HNSW-PQ            | Ultra-Fast (>4,000) | Low (Quantized nodes)  | Slow (Training)  | 92 - 96%  |
+-----------------------------------------------------------------------------------------+

2. Hierarchical Navigable Small World (HNSW)

HNSW is currently the state-of-the-art graph-based ANN algorithm. It structures vector space into a multi-layer graph hierarchy analogous to a Skip List:

HNSW Multi-Layer Search Traversal:
Layer 2 (Sparse Graph):    (Node A) -----------------------------------> (Node D)
                               |                                             |
                               v                                             v
Layer 1 (Medium Density):  (Node A) ------------> (Node B) ------------> (Node D)
                               |                     |                       |
                               v                     v                       v
Layer 0 (Dense Base):      (Node A) -> (Node E) -> (Node B) -> (Node F) -> (Node D)

Navigable Small World (NSW) Properties

Short Path Lengths: Any two nodes can be connected in $O(\log N)$ hops (the "Six Degrees of Separation" principle).
High Clustering Coefficient: Neighboring nodes share common connections, preventing dead-ends during greedy routing.

Traversal and Construction Mechanics

Search ( $efSearch$ ): Starts at the top sparse layer with the lowest degree. It greedily steps to the neighbor closest to query vector $q$ . When reaching a local minimum at Layer $l$ , it descends to Layer $l-1$ at the same node. At Layer 0, it maintains a dynamic candidate priority queue of size $efSearch$ .
Heuristic Edge Selection: Prevents graph clustering by ensuring outgoing edges connect to diverse directional vectors rather than only immediate nearest clusters.

3. Inverted File Indexing (IVF)

IVF partitions high-dimensional vector space into $C$ Voronoi cells using $K$ -Means clustering:

IVF Voronoi Partitioning:
[ High-Dimensional Space ]
         |
         v (K-Means Clustering: C Centroids)
  +-------------+-------------+
  |  Cell C1    |   Cell C2   |
  |  * Centroid |   * Centroid|
  |  [vec1,vec2]|   [vec3,vec4|
  +-------------+-------------+
         |
Query Search: Identify closest `nprobe` centroids -> Scan only vectors in those cells!

The `nprobe` Latency vs. Recall Dial

During query execution, the engine computes distance from query $q$ to all $C$ centroids.
It selects the top $\text{nprobe}$ closest centroids and performs exhaustive distance checks only on vectors within those cells.
If $\text{nprobe} = 1$ , latency is minimal but boundary vectors are missed (lower recall).
If $\text{nprobe} = C$ , IVF degrades to exhaustive Flat search ( $100\%$ recall, high latency).

4. Product Quantization (PQ) Compression Mechanics

High-dimensional float32 vectors consume massive RAM. A 1,536-dimensional vector (OpenAI text-embedding-3-small) requires $1,536 \times 4\,\text{bytes} = 6,144\,\text{bytes}$ per vector. One million vectors require $\approx 6.14\,\text{GB}$ of uncompressed RAM.

Product Quantization (PQ) compresses vectors by splitting high-dimensional spaces into lower-dimensional orthogonal subspaces:

Product Quantization 4x Compression Pipeline:
Original 128-dim Float32 Vector (512 Bytes):
[ v_1, ..., v_32 | v_33, ..., v_64 | v_65, ..., v_96 | v_97, ..., v_128 ]
        |                |                |                 |
        v (Subspace 1)   v (Subspace 2)   v (Subspace 3)    v (Subspace 4)
  [ Codebook 1 ]   [ Codebook 2 ]   [ Codebook 3 ]    [ Codebook 4 ]
  (256 Centroids)  (256 Centroids)  (256 Centroids)   (256 Centroids)
        |                |                |                 |
        v (Byte Index)   v (Byte Index)   v (Byte Index)    v (Byte Index)
Compressed 4-Byte Quantized Code: [ 0x4A, 0x1F, 0x9B, 0x03 ] (4 Bytes total! 128x compression)

Asymmetric Distance Computation (ADC)

In Asymmetric Distance Computation, the query vector $q$ remains uncompressed float32, while stored database vectors are quantized bytes. The engine precomputes a lookup table of distances from $q$ 's sub-vectors to all 256 centroids per codebook:

D_{\text{ADC}}(q, x) = \sum_{m=1}^M \| q^m - c_{k(x^m)}^m \|^2

Evaluating distance requires only $M$ table lookups and additions per vector, completely eliminating expensive floating-point multiplications from inner loops.

5. Modern Hybrid Vector Index Architectures

Production vector engines (Qdrant, Milvus, pgvector, Lucene) combine techniques:

IVF-PQ: Combines IVF coarse partitioning with PQ subspace compression, fitting billions of vectors into commodity RAM.
HNSW-SQ8 (Scalar Quantization): Compresses Float32 components to Int8 (4x reduction) while maintaining HNSW graph connectivity, achieving $>98\%$ recall with $70\%$ less memory.

References

Malkov, Y. A., & Yashunin, D. A. (2018). Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE TPAMI, 42(4), 824–836.
Jégou, H., Douze, M., & Schmid, C. (2011). Product Quantization for Nearest Neighbor Search. IEEE TPAMI, 33(1), 117–128.
Johnson, J., Douze, M., & Jégou, H. (2019). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3), 535–547.