Vector Database Architecture: HNSW, IVF and Quantization

Vector databases store and search high-dimensional embeddings — the numerical representations that power semantic search, recommendation systems, and RAG pipelines. But behind every fast similarity query is an indexing algorithm making tradeoffs between accuracy, speed, and memory. Understanding these algorithms lets you configure your vector database for your specific workload instead of trusting defaults that may waste resources or return poor results. After running benchmarks across three production search systems at scales from 100K to 500M vectors, here's how the core indexing algorithms work and when each one shines.

The Problem: Exact Search Doesn't Scale

Finding the k nearest neighbors to a query vector by brute force requires computing the distance between the query and every vector in the index. For a dataset of N vectors with D dimensions, that's N × D floating-point operations per query. At 1 million vectors with 1024 dimensions, that's ~1 billion operations — roughly 2ms on a modern CPU. At 100 million vectors, it's 200ms. At 1 billion, 2 seconds. For real-time applications needing sub-10ms latency, exact search stops working somewhere between 100K and 1M vectors depending on hardware.

Approximate Nearest Neighbor (ANN) algorithms solve this by trading a small amount of accuracy for orders-of-magnitude speedup. Instead of checking every vector, they build data structures that guide the search toward likely nearest neighbors, checking only a fraction of the dataset. The "approximate" part means they might miss the true nearest neighbor, but good algorithms achieve 95-99% recall — meaning they find 95-99% of the true top-k results. For understanding how the embedding models that generate these vectors are chosen, see our embedding models comparison.

HNSW: The Graph-Based King

Hierarchical Navigable Small World (HNSW) is the most widely used ANN algorithm. It builds a multi-layer graph where each vector is a node, and edges connect nearby vectors. The hierarchy enables efficient navigation from coarse to fine resolution.

How HNSW Works

During index construction, each new vector is assigned a random maximum layer based on an exponential distribution — most vectors appear only in the bottom layer (layer 0), and progressively fewer vectors exist in higher layers. The algorithm then connects each vector to its M nearest neighbors at each layer it appears in.

During search, the algorithm starts at the top layer's entry point and greedily navigates to the nearest node. It then drops to the next layer and continues searching from there, repeating until it reaches layer 0. At layer 0, it performs a beam search with width ef_search to find the final k nearest neighbors. The upper layers act as a "highway system" — sparse connections that let the search quickly navigate to the right region before doing detailed local search.

# HNSW configuration in Qdrant
from qdrant_client import QdrantClient
from qdrant_client.models import VectorParams, Distance, HnswConfigDiff

client = QdrantClient("localhost", port=6333)

client.create_collection(
    collection_name="articles",
    vectors_config=VectorParams(
        size=1024,
        distance=Distance.COSINE,
    ),
    hnsw_config=HnswConfigDiff(
        m=16,              # Edges per node (memory vs recall)
        ef_construct=200,  # Build-time search width (quality vs speed)
        full_scan_threshold=10000,  # Below this count, use brute force
    ),
)

HNSW Parameters

Parameter	Range	Effect	Default
M	4-64	Higher = better recall, more memory	16
ef_construction	100-500	Higher = better graph quality, slower build	200
ef_search	16-512	Higher = better recall, slower query	64

M=16 is the sweet spot for most workloads. Below 8, recall drops significantly because the graph becomes too sparse for efficient navigation. Above 32, memory consumption increases substantially (each edge stores a 4-byte neighbor ID) with diminishing recall improvements. The memory formula is approximately: N × (D × 4 + M × 2 × 4) bytes, where the first term is vector storage and the second is edge storage.

IVF: Partition-Based Search

Inverted File Index (IVF) takes a fundamentally different approach: partition the vector space into clusters using k-means, then search only the clusters closest to the query. It's the classic partition-and-search pattern applied to high-dimensional space.

1. Training: Run k-means on a representative sample to find nlist centroids.
2. Indexing: Assign each vector to its nearest centroid.
3. Searching: Find the nprobe centroids closest to the query, then brute-force search only the vectors in those clusters.

# IVF index with FAISS
import faiss
import numpy as np

d = 1024          # Dimension
nlist = 4096      # Number of clusters
nprobe = 64       # Clusters to search

# Train the index
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist)

training_data = np.random.rand(100000, d).astype('float32')
index.train(training_data)

# Add vectors
vectors = np.random.rand(1000000, d).astype('float32')
index.add(vectors)

# Search
index.nprobe = nprobe
query = np.random.rand(1, d).astype('float32')
distances, indices = index.search(query, k=10)

IVF's advantage is simplicity and low memory overhead — the index structure adds only the centroid storage (nlist × D × 4 bytes). The tradeoff: recall depends heavily on the cluster boundaries aligning with the nearest neighbor structure. Vectors near cluster boundaries are often missed because the search doesn't check neighboring clusters. Increasing nprobe fixes this but reduces the speedup.

Product Quantization: Compression for Scale

Product Quantization (PQ) compresses vectors by approximating them with compact codes, enabling billion-scale search on commodity hardware. The algorithm splits each D-dimensional vector into M subvectors, then quantizes each subvector independently using a learned codebook of 256 centroids (stored as 1-byte codes).

A 1024-dimensional float32 vector occupies 4096 bytes. With PQ using M=128 subvectors (8 dimensions each), the compressed representation is just 128 bytes — a 32× compression ratio. Distance computation uses lookup tables precomputed from the query against all centroids, making distance computation between a query and a compressed vector require only 128 table lookups and additions instead of 1024 floating-point multiplications.

Method	Memory per 1M vectors (1024d)	Query Latency	Recall@10
Flat (brute force)	4.0 GB	2.1 ms	100%
HNSW (M=16)	5.2 GB	0.3 ms	97.5%
IVF-Flat (nlist=4096)	4.1 GB	0.8 ms	95.2%
IVF-PQ (M=128)	0.18 GB	0.5 ms	88.4%
HNSW + SQ (int8)	1.5 GB	0.4 ms	96.1%
IVF-PQ + Refine	0.18 GB + flat	1.2 ms	94.8%

IVF-PQ is the combination used for billion-scale deployments. Meta's FAISS library is the reference implementation, and it's the engine behind many production vector databases. For understanding how these compressed representations interact with the embedding layer, our guide on embedding model selection covers the upstream tradeoffs.

Scalar Quantization: The Simple Win

Scalar quantization (SQ) maps each floating-point dimension to an 8-bit integer, reducing memory by 4× with minimal accuracy loss. Unlike PQ, which requires training codebooks, SQ simply tracks the min and max value per dimension and linearly maps the range to 0-255.

# Scalar quantization in Qdrant
from qdrant_client.models import (
    VectorParams, Distance,
    ScalarQuantization, ScalarQuantizationConfig,
    ScalarType, QuantizationSearchParams
)

client.create_collection(
    collection_name="articles_quantized",
    vectors_config=VectorParams(
        size=1024,
        distance=Distance.COSINE,
    ),
    quantization_config=ScalarQuantization(
        scalar=ScalarQuantizationConfig(
            type=ScalarType.INT8,
            quantile=0.99,  # Clip outliers
            always_ram=True,
        ),
    ),
)

# Search with quantization
results = client.search(
    collection_name="articles_quantized",
    query_vector=query_embedding,
    limit=10,
    search_params=QuantizationSearchParams(
        quantization={"rescore": True, "oversampling": 2.0},
    ),
)

The rescore parameter is critical: the initial search uses quantized vectors for speed, then re-ranks the top candidates using original float32 vectors. With oversampling=2.0, the initial search retrieves 2× the requested results and re-ranks them, recovering most of the accuracy lost to quantization. This pattern — fast approximate search followed by precise re-ranking — appears throughout production vector search systems. For building the retrieval pipelines that use these quantized indexes, see our RAG architecture guide.

Choosing an Index for Your Scale

• Under 1M vectors: Use HNSW with float32 vectors. Memory is cheap at this scale, and you get the best recall-latency tradeoff. Most vector databases make this the default.
• 1M - 10M vectors: HNSW with scalar quantization (int8). This cuts memory by 4× while keeping recall above 96% with rescoring. The sweet spot for most production RAG applications.
• 10M - 100M vectors: IVF-PQ or HNSW with more aggressive quantization. At this scale, memory dominates cost. IVF-PQ's 32× compression enables serving from a single machine. Add a flat re-ranking step if you need recall above 93%.
• 100M+ vectors: IVF-PQ with sharding across multiple machines. Each shard runs its own index and results are merged. This is how Spotify, Pinterest, and Meta run billion-scale similarity search.

On-Disk Indexes: Beyond Memory

When your dataset exceeds available RAM, disk-based vector search becomes necessary. Two approaches dominate:

DiskANN

DiskANN (Microsoft) builds a graph index on disk using Vamana graphs — similar to HNSW but optimized for sequential disk reads. It stores compressed (PQ) vectors in memory for distance computation and accesses original vectors on SSD only for the final re-ranking step. At 1 billion vectors, DiskANN achieves 95% recall with ~5ms latency using just 64GB of RAM for the compressed index, compared to ~1TB for an in-memory HNSW index.

Memory-Mapped Files

Qdrant and Milvus support memory-mapped (mmap) vector storage, where the OS manages paging vectors between disk and RAM. This works well when queries access a hot subset of the data (temporal locality) but degrades under uniform random access patterns. The practical benefit: you can serve a 50GB vector index on a machine with 16GB RAM, as long as your query distribution has locality.

Filtering: The Metadata Challenge

Real-world vector search almost always involves metadata filters: "find similar articles published in the last 7 days" or "find matching products in the Electronics category priced under $50." Combining ANN search with exact filtering is surprisingly difficult because the two operations have conflicting requirements.

Pre-filtering (filter first, then ANN search) is accurate but slow — you might filter down to 1% of vectors, making the ANN index worthless because the filtered subset doesn't have a pre-built graph.

Post-filtering (ANN search first, then filter) is fast but inaccurate — if the top-100 ANN results contain only 3 that match the filter, you return poor results.

In-filter search (the modern approach) integrates filtering into the ANN algorithm itself. Qdrant's approach: traverse the HNSW graph normally, but skip nodes that don't match the filter. This requires checking filter conditions during graph traversal, which adds latency proportional to the filter's selectivity. When the filter is very restrictive (selecting less than 1% of vectors), the algorithm falls back to brute-force scan of matching vectors. Understanding these filtering tradeoffs matters when building feature stores that serve both exact and approximate lookups.

# Filtered search in Qdrant
from qdrant_client.models import Filter, FieldCondition, Range

results = client.search(
    collection_name="articles",
    query_vector=query_embedding,
    query_filter=Filter(
        must=[
            FieldCondition(
                key="published_date",
                range=Range(gte="2026-01-01"),
            ),
            FieldCondition(
                key="category",
                match={"value": "machine-learning"},
            ),
        ]
    ),
    limit=10,
)

Production Tuning Checklist

After deploying vector search systems at multiple scales, here's the tuning checklist we follow:

1. Start with HNSW + float32. Optimize only when you have a measurable problem (memory pressure, latency budget).
2. Measure recall on your data. Build a ground-truth set of 1000 queries with brute-force nearest neighbors. Measure recall@10 for your index configuration. Don't trust benchmark numbers from other datasets.
3. Tune ef_search first. This is the query-time knob with the most direct recall-latency tradeoff. Start at 64, increase until you hit your recall target, check latency.
4. Add scalar quantization if memory is tight. Always enable rescoring with 2× oversampling. Check that recall drops less than 2%.
5. Switch to IVF-PQ only if your dataset genuinely exceeds available memory and you can't add more RAM. The recall cost is real.
6. Profile your filter selectivity. If common queries filter to under 5% of vectors, ensure your database handles this without degraded recall. Test the worst-case filter.
7. Monitor hot vs cold latency. First queries after a restart page data from disk and are 10-100× slower. Pre-warm your index by running sample queries after deployment. For monitoring these metrics, see our monitoring guide.

FAQ

What is HNSW and why is it the most popular vector index?

HNSW is a graph-based ANN algorithm that builds a multi-layer graph for efficient nearest neighbor search. It achieves 95-99% recall with sub-millisecond latency, making it the default choice for Pinecone, Weaviate, Qdrant, and pgvector.

When should I use IVF instead of HNSW?

Use IVF when memory is constrained and your dataset exceeds available RAM. IVF with product quantization can compress vectors by 10-30×, enabling billion-scale search on commodity hardware. The tradeoff is lower recall at equivalent latency.

How much memory does a vector database need?

For HNSW: approximately vector_count × dimensions × 4 bytes × 1.5 overhead factor. One million 1024-dimensional vectors require ~6GB. With scalar quantization this drops to ~1.5GB. IVF-PQ can compress to ~200MB for the same dataset.

What is product quantization and how does it compress vectors?

PQ splits each vector into subvectors and maps each to its nearest centroid in a learned codebook. A 1024-dimensional float32 vector (4KB) can be compressed to 128 bytes — a 32× ratio — trading some accuracy for dramatically reduced memory and faster distance computation.

How do I tune HNSW parameters for my workload?

Start with M=16 and ef_construction=200. For queries, set ef_search=64 and increase until you hit your target recall (typically 95%+). Higher M improves recall but increases memory linearly. Monitor latency as you increase ef_search — the recall-latency curve flattens beyond a certain point.