Vector Database Indexing Guide: HNSW vs IVF-PQ vs ScaNN for Vector Search

1. Introduction: The High-Dimensional Vector Search Challenge

Modern artificial intelligence pipelines transform unstructured data (natural language, source code, genomic sequences, molecular structures) into dense high-dimensional vectors.

Searching across N = 10,000,000 documents with dimension D = 1,536 (e.g. OpenAI text-embedding-3-large) requires computing 10 million vector dot products per query:

Total Operations per Query = N * D = 10,000,000 * 1,536 = 15.36 Billion FLOPs

Executing exact exhaustive flat k-NN search across 15.36 billion floating-point operations introduces 150 ms to 500 ms of CPU latency per query, making real-time interactive search impossible.

Approximate Nearest Neighbor (ANN) indexing algorithms solve this by trading a negligible fraction of theoretical recall (e.g. 97% Recall@10 instead of 100%) to reduce query time complexity from linear O(N) down to logarithmic O(/log N) or clustered sub-linear O(sqrt(N)).

VECTOR DATABASE INDEXING ARCHITECTURES

• [ Algorithm 1: Hierarchical Navigable Small World (HNSW) ]
• Layer 2 (Sparse Highway) -------------------------------------------------------- [ Node A ] -------------------------------------------------------- [ Node F ]
• Layer 1 (Medium Granularity) ? [ Node A ] -------------------------------------------------------- [ Node C ] -------------------------------------------------------- [ Node F ]
• Layer 0 (Dense Base Graph) -------------------------------------------------------- [ Node A ]?[B]?[ Node C ]?[D]?[ Node F ]
• [ Algorithm 2: Inverted File with Product Quantization (IVF-PQ) ]
• Vector (1536d Float32: 6,144 Bytes)
• [ Product Quantization Compression: Split into M = 64 Sub-Vectors ]
• Compressed Vector (64 Bytes Codebook Indices: 96x Compression)
• [ Routed into K = 4,096 Voronoi Centroid Clusters ] -------------------------------------------------------- Query probes top-nlist = 16 cells

2. Head-to-Head Index Algorithm Comparison

3. Deep-Dive: HNSW Graph Theory & Parameter Tuning

The HNSW algorithm builds upon probabilistic skip-lists applied to spatial graph networks:

1. Layer Hierarchy:
   • Nodes are assigned to layers with exponentially decaying probability (P(l) /propto /exp(-l / m_L)).
   • Upper layers contain sparse long-range connections for fast geometric traversal.
   • Base layer l_0 contains all data points with dense local Delaunay-like clustering.
2. Key Hyperparameters:
   • M (Max bidirectional connections per node, typically 16 to 64): Higher M improves recall on high-dimensional vectors but increases memory usage and index build time.
   • efConstruction (Size of dynamic candidate list during graph construction, typically 100 to 200): Controls index quality and build duration.
   • efSearch (Candidate list size at query time, typically 32 to 128): Dynamically tunes the runtime trade-off between QPS and Recall@K without rebuilding the index.

======================================================================================
HNSW PARAMETER TUNING BENCHMARK (1M VECTORS, 1536 DIMENSIONS)
======================================================================================

Configuration (M / efSearch)| Recall@10 Accuracy | Query Latency (p99) | QPS Throughput
----------------------------+--------------------+---------------------+----------------
Fast (M=16, efSearch=32)    | 93.4%              | 1.1 ms              | 3,850 QPS
Balanced (M=32, efSearch=64)| 97.8%              | 2.2 ms              | 2,100 QPS
High-Precision (M=64, ef=128| 99.4%              | 4.6 ms              | 1,050 QPS

4. Product Quantization (PQ) & Asymmetric Distance Computation

Product Quantization compresses high-dimensional vector space through sub-space decomposition:

1. A D = 1,536 dimensional vector is divided into M = 64 sub-vectors of dimension D^* = D / M = 24.
2. For each sub-space, K-Means clustering identifies K^* = 256 centroids.
3. Each sub-vector is replaced by an 8-bit integer index (1 byte) representing its closest centroid.
4. Total vector size is compressed from 1536 imes 4 ext{ bytes} = 6,144 ext{ bytes} down to 64 bytes (98.9% memory reduction).

Asymmetric Distance Computation (ADC)

During a search query Q:

• The query Q is not quantized.
• The system precomputes the distance between Q's sub-vectors and the 256 centroids across all 64 sub-spaces, storing results in a small 64 imes 256 lookup table.
• Approximating the distance to any of the 10 million stored vectors requires only 64 array table lookups and additions, utilizing SIMD registers without floating-point multiplications.

5. Google ScaNN: Anisotropic Vector Quantization

In standard Product Quantization, quantization error is minimized uniformly in all directions (spherical loss):

Loss_Standard = || x - x_quantized ||^2

In Maximum Inner Product Search (MIPS), the dot product $/langle q, x angledepends heavily on the component ofxparallel to the queryq$.

ScaNN (Scalable Nearest Neighbors) reformulates the quantization loss function to be anisotropic:

Loss_ScaNN = || x_parallel - x_quantized_parallel ||^2 + (1 - w) * || x_orthogonal - x_quantized_orthogonal ||^2

By prioritizing precision along the parallel projection vector (w o 1), ScaNN reduces angular error where it matters most for ranking, achieving up to 2x higher QPS at 95% Recall@10 compared to standard FAISS IVF-PQ implementations.

Frequently Asked Questions (FAQ)

When should I choose HNSW over IVF-PQ?

Choose HNSW when your dataset fits in RAM, query latency must be < 3 ms, and Recall@10 must exceed 98%. Choose IVF-PQ when storing tens of millions of vectors on limited RAM budgets where 95% memory compression is essential.

Can HNSW handle real-time vector insertions?

Yes. HNSW natively supports dynamic, real-time node insertion without rebuilding the entire graph index. In contrast, IVF-PQ requires periodic offline retraining of Voronoi centroid clusters when data distributions drift.

Where can I test regular expression state machines and token parsers?

You can build and step through deterministic finite state machines using our Regex State Machine Visualizer and model API infrastructure costs on the LLM Pricing Calculator.