How Vector Databases Actually Work | ANN, HNSW, IVF & Product Quantization

Vector databases are specialized storage and retrieval engines designed to handle high-dimensional vector embeddings generated by machine learning models. This chapter explores the foundational mechanics, scaling bottlenecks, and indexing algorithms that allow modern systems to query millions of embeddings in milliseconds without performing exhaustive linear scans.

1. Why Do We Need Specialized Indexing? (The Scaling Problem)

In standard applications, finding similar data points often relies on relational databases using B-Trees, exact matching, or text-based search engines using inverted indexes (like BM25). However, Generative AI applications represent text, images, audio, and video as high-dimensional continuous vectors (e.g., 1536-dimensional float vectors from OpenAI models).

When a user submits a query, the system converts it into a query vector and measures semantic similarity (typically via Cosine Similarity, Dot Product, or Euclidean Distance) against stored database vectors.

Exact Nearest Neighbor (KNN) vs. The Computational Wall

The naive approach to vector search is K-Nearest Neighbors (KNN), also known as an Exact Nearest Neighbor search.

Mathematically, if we have $N$ vectors in our database, and each vector has dimensionality $D$, computing the distance for a single query requires:

• $N \times D$ floating-point operations (FLOPs).
• For $N = 1,000,000$ vectors and $D = 1536$ dimensions, a single query requires over 1.5 billion mathematical operations.

In production systems handling hundreds of concurrent queries with latency budgets under 50 milliseconds, an exhaustive linear scan ($O(N)$ time complexity per query) becomes computationally impossible. This scaling wall forces engineers to adopt Approximate Nearest Neighbor (ANN) search.

2. Approximate Nearest Neighbor (ANN) and the Speed vs. Recall Trade-Off

To bypass the $O(N)$ bottleneck, vector databases sacrifice absolute precision for drastic speed improvements using Approximate Nearest Neighbor (ANN) search algorithms.

Real-Life Analogy: Finding a Book in a Massive Library

Imagine walking into a massive library with millions of books.

• Exact Search (KNN): You pick up every single book in the library, read its first page, and compare it word-for-word against your topic. You are 100% guaranteed to find the absolute best book, but it takes days.
• Approximate Search (ANN): You walk to the correct floor, check the section shelf labeled "Computer Science", and look at the top 5 most relevant books. You find an amazing book in 30 seconds. While you might miss a slightly better book hidden in the history section, the time saved is astronomical.

Understanding Recall@K

Because ANN algorithms do not scan every vector, they may occasionally miss the true nearest neighbor. We measure the quality of an ANN index using Recall@K:

• If Recall@1 = 0.95, it means 95% of the time, the index successfully retrieves the absolute closest vector to the query.
• Modern indexing balances this metric, trading a minor drop in accuracy (e.g., 98% recall) for a 100x to 1000x boost in query throughput.

3. IVF (Inverted File Index) from First Principles

The Inverted File Index (IVF) is a space-partitioning approach borrowed from traditional information retrieval and adapted for vector spaces. Instead of searching the entire vector space, IVF divides the space into distinct geometric regions using clustering.

Step-by-Step IVF Architecture

1. Offline Training (Clustering): Before storing vectors efficiently, the database runs an unsupervised clustering algorithm—typically K-Means—across the dataset.
   • If $N = 1,000,000$, K-Means groups the vectors into $C$ clusters (e.g., $C = 1024$).
   • Each cluster is defined by its center point, known as a Centroid.
2. Assignment: Every vector in the database is assigned to its nearest centroid and stored in an inverted list pointing to that centroid.
3. Online Querying: When a query vector arrives:
   • The database compares the query vector only against the $C$ centroids (which is extremely fast because $C \ll N$).
   • It identifies the closest centroid (or top $nprobe$ centroids).
   • It restricts the exhaustive distance calculation solely to the vectors residing inside those targeted cluster lists.

The Role of nprobe

• nprobe = 1: Extremely fast, but risks low recall if the true nearest neighbor happens to sit just across the boundary in a neighboring cluster.
• nprobe = C: Degrades back into a full linear scan (KNN) with maximum recall.
• Tuning nprobe allows engineers to dial in the exact latency vs. accuracy profile required by their application.

4. HNSW (Hierarchical Navigable Small World) Graphs

While IVF partitions space into clusters, Hierarchical Navigable Small World (HNSW) uses graph theory, taking inspiration from the "small-world phenomenon" (six degrees of separation).

Core Mental Model

Think of HNSW as a multi-layered highway system:

• Top Layer (Layer 2 / Expressways): Sparse nodes with long-range connections. You can cross the entire dataset in a few hops.
• Middle Layer (Layer 1 / Regional Roads): Denser nodes with medium-range connections.
• Bottom Layer (Layer 0 / Local Streets): Contains every single vector in the database, connected to their immediate local neighbors.

How HNSW Querying Works

1. Entry Point: The search starts at a designated entry point on the top sparse layer.
2. Greedy Routing: The algorithm evaluates neighboring nodes on the current layer, greedily stepping closer to the query vector.
3. Layer Descent: When no further progress can be made on the current layer (i.e., you are closer to the target than any neighbor), the algorithm drops down to the same node on the layer below.
4. Local Fine-Tuning: The process repeats until the algorithm reaches Layer 0, where it performs a localized greedy search to find the exact nearest neighbors.

HNSW delivers exceptional query latency and high recall, making it the default indexing strategy for many real-time applications, though it requires significantly more RAM because the graph edges must be stored in memory.

5. IVF vs. HNSW: Comparative Synthesis

Choosing between IVF and HNSW depends on hardware constraints, memory limits, and ingest-versus-query trade-offs.

6. Vector Quantization and Compression

Storing millions of high-dimensional floating-point embeddings consumes massive amounts of RAM.

The Math of Raw Embeddings

Consider a standard embedding model like OpenAI's text-embedding-3-small, which outputs a dimensionality of $D = 1536$.

• Each dimension is stored as a 32-bit floating-point number (float32), which equals 4 bytes per dimension.
• Size per vector: $1536 \times 4 \text{ bytes} = 6144 \text{ bytes}$ ($\approx 6 \text{ KB}$).
• For 10 million vectors: $10,000,000 \times 6144 \text{ bytes} \approx 61.44 \text{ GB}$ of raw vector data alone, before accounting for graph overhead or metadata.

7. Product Quantization (PQ) in Detail

Product Quantization (PQ) solves the memory explosion problem by compressing vectors through vector quantization. Instead of storing full 32-bit floats, PQ breaks vectors into sub-vectors and compresses them into compact codebook indices.

Step-by-Step Product Quantization Workflow

1. Sub-vector Decomposition: Take a 1536-dimensional vector and split it into $M$ smaller sub-vectors. For example, let $M = 96$. Each sub-vector will have dimensionality:

2. Sub-space Clustering (Codebooks): For each of the 96 sub-space positions across the entire training dataset, the database runs K-Means clustering to create a "codebook" of centroids. If we use 8 bits per codebook, each codebook contains $2^8 = 256$ centroids.
3. Quantization / Encoding: Every 16-dimensional sub-vector is replaced by the ID (1 byte, ranging from 0 to 255) of its nearest centroid in that sub-space's codebook.
4. Extreme Compression Result:
   • Instead of storing 96 sub-vectors as 16-dimensional float32 arrays ($96 \times 16 \times 4 = 6144$ bytes), we store 96 single-byte IDs.
   • Compressed vector size: $96 \times 1 \text{ byte} = 96 \text{ bytes}$.
   • This achieves a 64x compression ratio, turning gigabytes of RAM requirements into manageable megabytes.

8. Metadata Filtering in Vector Databases

Production applications rarely perform pure vector similarity searches in isolation. Users expect semantic search combined with relational filters (e.g., "Find the 5 documents most similar to my query vector, but restrict results to documents where author = 'alice' and date >= 2024-01-01").

Pre-filtering vs. Post-filtering Architectures

• Pre-filtering:
  • Mechanism: The database applies the metadata filter first, reducing the dataset to only matching rows, and then runs the vector search on that subset.
  • Drawback: If the metadata filter is overly restrictive (e.g., leaving only 10 vectors out of 10 million), vector indexes like HNSW or IVF break down because graph traversal algorithms require a dense, continuous topological space.
• Post-filtering:
  • Mechanism: The database performs the vector search first to retrieve the top $K$ results (e.g., Top 100), and then strips out any results that fail the metadata criteria.
  • Drawback: If your metadata filter eliminates 95% of those top results, you are left with only 5 items instead of your requested $K$.
• Fused / Indexed Filtering:
  • Modern vector databases (such as Pinecone, Qdrant, Weaviate, and pgvector) use integrated inverted indices for metadata alongside vector indices, evaluating both simultaneously during graph traversal or cluster probing to guarantee accurate, performant results.

Summary and Key Takeaways

• The Scalability Bottleneck: Exact Nearest Neighbor (KNN) search requires linear $O(N)$ scans, becoming computationally infeasible as datasets scale into millions of high-dimensional embeddings.
• Approximate Nearest Neighbor (ANN): Trades absolute precision for massive speed gains, evaluated via the Recall@K metric.
• IVF (Inverted File Index): Partitions vector space using K-Means centroids, restricting distance calculations only to vectors residing in the closest matching clusters (nprobe).
• HNSW (Navigable Small World Graphs): Utilizes multi-layered graph hierarchies to achieve ultra-fast logarithmic search times through greedy routing.
• The Memory Challenge: Raw high-dimensional embeddings (e.g., 1536 dimensions at float32) require massive RAM; vector quantization is essential for enterprise scale.
• Product Quantization (PQ): Decomposes vectors into sub-vectors and maps them to codebook centroids, compressing vector footprints by up to 64x without catastrophic loss in recall.
• Metadata Filtering: Combines semantic similarity with structured relational constraints using advanced pre-filtering, post-filtering, or fused indexing strategies.
• Ecosystem Maturity: Modern infrastructure tools (Pinecone, Qdrant, Weaviate, pgvector) abstract these complex algorithms behind clean APIs for production-grade GenAI applications.