Vector Database System Design: HNSW, IVF, and Product Quantization

What This Blog Covers

• Why vector indexes matter
• Exact vs ANN search
• HNSW explained simply
• IVF indexing explained
• Product Quantization basics
• Choosing the right index
• AI system design considerations

Large language models have changed how applications search for information.

Traditional databases were designed to retrieve exact matches. If an application needs the user with ID 105, an order created yesterday, or every product in a specific category, relational databases perform exceptionally well. AI applications, however, often ask a very different question.

Instead of searching for an exact record, they search for meaning.

A user might ask, “Explain cache invalidation in distributed systems,” while the stored document is titled “Maintaining Cache Consistency Across Multiple Services.” Although the wording is different, both pieces of text describe nearly the same concept.

A traditional keyword search may struggle to connect them, but a vector database can.

This shift from exact search to semantic search has introduced an entirely new category of system design problems.

Modern AI systems must retrieve relevant information from millions or even billions of vector embeddings while keeping latency low enough for interactive applications. Achieving that balance requires specialized indexing techniques that are very different from the B-tree indexes commonly used in relational databases.

This is where concepts such as Approximate Nearest Neighbor (ANN) search, Hierarchical Navigable Small Worlds (HNSW), Inverted File Indexes (IVF), and Product Quantization (PQ) become essential.

Understanding these techniques is increasingly valuable for engineers building AI products and for candidates preparing for modern system design interviews.

Why Traditional Database Indexes Are Not Enough

Relational databases rely on indexes such as B-trees to speed up lookups.

These indexes work extremely well because they organize structured values in sorted order. Searching for customer IDs, timestamps, usernames, or order numbers becomes efficient because those values can be compared directly.

Vector embeddings behave differently.

Instead of storing a single number or string, an embedding may contain hundreds or even thousands of floating-point values representing semantic meaning.

For example, an embedding generated by a modern language model may contain 768, 1,024, or even more dimensions.

Searching these vectors requires calculating similarity rather than exact equality.

The database must answer questions such as:

“Which stored vectors are most similar to this new query vector?”

Traditional indexing strategies were never designed for this problem.

Understanding Vector Similarity Search

Before discussing indexing techniques, it helps to understand the underlying problem.

Suppose an application stores ten million document embeddings.

A user asks a question.

The question is converted into a vector using an embedding model.

The database now needs to compare that query vector against every stored vector and return the closest matches.

Similarity is usually measured using one of three metrics:

• Cosine Similarity
• Euclidean Distance
• Dot Product

Although the mathematical details differ, the goal remains the same.

Find vectors that are closest in semantic space.

If the database compared the query against every stored vector, the answer would be perfectly accurate.

Unfortunately, it would also be far too slow for large production systems.

Brute Force Search: The Baseline

The simplest vector search algorithm is brute force.

Every query vector is compared against every stored vector.

The closest vectors are returned as the search results.

This approach has one major advantage.

It produces exact results.

Every nearest neighbor is guaranteed to be correct because every vector has been examined.

However, the computational cost grows linearly with the size of the dataset.

Imagine storing one billion embeddings.

Every search request would require one billion similarity calculations.

Even highly optimized hardware would struggle to provide interactive response times.

Brute-force search quickly becomes impractical for production AI systems.

This creates an important system design trade-off.

Would users rather receive results that are perfectly accurate but several seconds slower?

Or results that are almost identical but arrive within a few milliseconds?

Most production systems choose the second option.

That decision leads directly to Approximate Nearest Neighbor search.

Approximate Nearest Neighbor (ANN)

Approximate Nearest Neighbor search solves a simple problem.

Instead of examining every vector, intelligently search only the parts of the dataset that are most likely to contain similar vectors.

This dramatically reduces computation.

The trade-off is that the search becomes approximate rather than exact.

The algorithm may occasionally miss the mathematically perfect nearest neighbor, but the returned results are usually extremely close.

For semantic search, recommendation systems, and retrieval-augmented generation (RAG), this trade-off is almost always worthwhile.

Users rarely notice the tiny difference in accuracy.

They immediately notice the difference between a response arriving in twenty milliseconds versus two seconds.

Nearly every modern vector database relies on some form of Approximate Nearest Neighbor indexing.

The remaining sections of this article explain the three most common approaches.

Why Multiple ANN Algorithms Exist

There is no single indexing strategy that performs best in every situation.

Different applications prioritize different goals.

Some prioritize search speed.

Others prioritize memory efficiency.

Some need extremely high recall.

Others must fit billions of vectors into limited hardware.

This is why multiple ANN algorithms exist.

Among the most widely used are:

• HNSW
• IVF
• Product Quantization
• IVF with Product Quantization

Each solves the same problem using a different strategy.

Understanding those strategies helps engineers choose the right index for a particular workload rather than treating every vector database as identical.

HNSW: Hierarchical Navigable Small Worlds

One of the most popular indexing algorithms today is HNSW.

Rather than organizing vectors into trees or clusters, HNSW represents the dataset as a graph.

Each vector becomes a node.

Every node connects to several nearby neighbors.

These connections allow the algorithm to navigate through the dataset without examining every vector.

The word “hierarchical” comes from the fact that HNSW builds multiple graph layers.

Higher layers contain fewer nodes and allow rapid movement across the graph.

Lower layers become increasingly detailed until the search reaches the most relevant neighborhood.

An intuitive way to think about HNSW is navigating a city.

Instead of walking every street, you first use highways to reach the correct neighborhood.

After leaving the highway, smaller roads guide you toward the final destination.

The algorithm follows a similar strategy.

It moves quickly through higher graph layers before performing a more detailed search near the query vector.

This dramatically reduces the number of comparisons required.

Why HNSW Is Popular

HNSW provides exceptionally high recall while maintaining very low query latency.

For many production workloads, it finds results that are extremely close to exact nearest-neighbor search while remaining fast enough for interactive AI applications.

Because of this balance, HNSW has become the default indexing strategy for many modern vector databases.

IVF: Inverted File Index

HNSW is not the only way to avoid scanning every vector.

Another widely used indexing strategy is the Inverted File Index, commonly known as IVF.

The core idea behind IVF is surprisingly intuitive.

Instead of treating all vectors as one enormous collection, IVF first divides the dataset into multiple clusters. Each cluster is represented by a centroid that summarizes the vectors contained within it.

When a query arrives, the database does not immediately compare the query against every stored vector.

Instead, it first finds the centroids that are closest to the query. Only the vectors inside those clusters are searched in detail.

Imagine looking for a specific house in a country.

Without any organization, every city would need to be searched. IVF first identifies the correct city, then the correct neighborhood, and only then searches individual houses.

The same principle dramatically reduces the number of similarity calculations.

How IVF Is Built

Building an IVF index typically happens offline.

The vectors are first grouped using a clustering algorithm such as k-means.

Each cluster receives a centroid.

The vectors belonging to that centroid are stored together.

During query time, the workflow becomes:

1. Convert the query into an embedding.
2. Compare the query against all centroids.
3. Select the closest clusters.
4. Search only the vectors inside those clusters.
5. Return the nearest matches.

Instead of searching millions of vectors, the search may examine only a few thousand.

Advantages of IVF

IVF offers several practical advantages.

Its memory overhead is relatively low compared to graph-based indexes.

Index construction is generally faster than HNSW.

Large datasets can often be partitioned efficiently, making IVF attractive for very large vector collections.

Many production systems also allow tuning how many clusters should be searched. Searching more clusters improves recall but increases latency. Searching fewer clusters improves speed while sacrificing a small amount of accuracy.

This flexibility makes IVF useful for applications with different performance requirements.

Limitations of IVF

The quality of an IVF index depends heavily on clustering.

Poor clusters lead to poor search quality.

Unlike HNSW, IVF may struggle when relevant vectors happen to be distributed across multiple clusters.

Because of this, HNSW generally achieves higher recall at similar latency, particularly for medium-sized datasets.

However, IVF becomes extremely powerful when combined with Product Quantization.

Product Quantization (PQ)

Searching fewer vectors solves only part of the problem.

Memory usage quickly becomes another major challenge.

Consider storing one billion embeddings.

Suppose each embedding contains 768 floating-point values.

Using 32-bit floating-point numbers, every vector occupies approximately three kilobytes.

A billion vectors would require several terabytes of memory.

Keeping everything in RAM becomes extremely expensive.

Product Quantization addresses this problem.

Rather than storing every floating-point value exactly, PQ compresses vectors into much smaller representations while preserving enough information for approximate similarity search.

The idea is similar to image compression.

A compressed image occupies much less storage while remaining visually similar to the original.

Product Quantization applies the same principle to vectors.

How Product Quantization Works

Instead of compressing an entire vector as one object, PQ divides the vector into multiple smaller sections.

Each section is compressed independently.

For every section, a small codebook is created containing representative values.

Rather than storing original floating-point numbers, the system stores references to entries inside those codebooks.

The result is dramatic memory reduction.

Vectors that originally required thousands of bytes may now occupy only a few dozen bytes.

This makes billion-scale vector databases practical.

Advantages of PQ

The biggest advantage is memory efficiency.

Much larger datasets fit into memory.

Less data must move between memory and CPU caches.

Query performance often improves because compressed representations require less bandwidth.

These savings become increasingly important as datasets reach hundreds of millions or billions of vectors.

Limitations of PQ

Compression introduces approximation.

The reconstructed vector is not identical to the original.

Similarity calculations therefore become slightly less accurate.

This creates another engineering trade-off.

Greater compression reduces memory usage.

Greater compression also reduces recall.

Choosing the right balance depends on application requirements.