Vector Index Internals: HNSW, IVF, and Quantization

The exact nearest-neighbor problem at scale

Suppose you have 1 million 768-dimensional embedding vectors in a database. A user asks a question; you embed it to a 768-dim vector. To find the most relevant chunks, you compute the distance (usually cosine similarity or Euclidean distance) between the query vector and all 1 million vectors, then rank by similarity.

This is exact nearest-neighbor search. It's guaranteed to find the true closest neighbors. It's also O(n*d), where n is the number of vectors and d is the dimension. At 1M vectors × 768 dims = ~768M scalar multiplications per query. On a modern CPU, that's roughly 0.5-1 second per query. On a GPU, maybe 0.05 seconds. But at scale—processing 100 concurrent queries—exact search becomes a bottleneck.

The deeper problem: vector search doesn't benefit from traditional indexing tricks (like B-trees or hash tables). In low-dimensional spaces, spatial indexes are effective. But high-dimensional spaces suffer from the "curse of dimensionality": most vectors become roughly equidistant from a random query, making spatial locality almost meaningless. Traditional indexes give little speedup.

Approximate Nearest Neighbor (ANN) search accepts this constraint: instead of finding the true k nearest neighbors, find approximately k neighbors that are close enough. The tradeoff is dramatic: a well-tuned ANN index can return top-10 results in 5-10 milliseconds from 100M vectors, a 50-100x speedup over exact search. The cost is that you might miss some of the true top-10, or retrieve a few false positives.

For RAG, this tradeoff is almost always worth it. Retrieving 8 out of 10 most relevant chunks in 10ms is far more useful than retrieving the exact top-10 in 1 second.

HNSW: Navigable small-world graphs

Hierarchical Navigable Small World (HNSW) graphs are the most popular ANN algorithm in production RAG systems. They're used in Pinecone, Weaviate, Qdrant, and Milvus.

Core idea: Imagine a graph where every node is a vector. Edges connect nearby vectors. A search starts at a random node, then greedily hops to neighbors closer to the query. This is fast—just a few hops to a good neighborhood—but greedy search can get stuck in local optima.

HNSW fixes this by building a layered graph: vectors exist on multiple levels. The top level is sparse (few connections, large hops), the bottom level is dense (many connections, fine-grained). A query enters at the top, makes large jumps, then drops down to lower levels for precise local search.

Level 2 (sparse):     [A]----[B]----[C]       (3 nodes)
                       |      |
Level 1 (denser):    [A]--[D]--[B]--[E]--[C]  (5 nodes)
                      | \ | / |  |  |
Level 0 (full):  [A]-[D]-[F]-[B]-[G]-[E]-[C]-[H] (8 nodes)

Query enters at level 2, jumps from A -> B -> C (2 hops)
Drops to level 1, searches locally: B -> E -> C (2 more hops)
Drops to level 0, final refinement: C -> G -> H (fine grained)

Why this works: A greedy search in the sparse top layer gets close in ~log(n) hops, then a dense local search finds exact neighbors. Total complexity is near-logarithmic instead of linear.

Key tuning parameters:

• M (max connections per node): Higher M makes edges denser, improving search quality but increasing memory and insertion cost. Typical: 5-48 (default 16).
• ef_construction (insertion parameter): How hard to work when inserting a new vector. Higher values mean the new vector is placed more precisely in the graph, improving future searches. Default: 200, range 50-500.
• ef_search (query parameter): How many candidates to consider during search. ef_search=200 means exploring ~200 nodes; higher values improve recall but slow search. Default: 200-1000 for production.

Memory footprint: ~4KB per vector (storing ~16 pointers per node, 8 bytes per pointer). At 1M vectors: ~4GB. Reasonable for most applications.

IVF: Inverted file index with clustering

IVF (Inverted File Index) is an older but still effective approach, widely used in FAISS (Facebook AI Similarity Search).

Core idea: Cluster the vectors into k groups (e.g., 1000 clusters). For each cluster, precompute a centroid. To search:

1. Embed the query.
2. Find the nprobe nearest clusters (not just the single nearest).
3. Search all vectors within those clusters exactly.

Example:

Corpus of 1M vectors -> cluster into k=1000 clusters
Each cluster has ~1000 vectors

Query Q arrives:
1. Compute distance from Q to all 1000 cluster centroids
2. Pick the 5 nearest clusters (nprobe=5)
3. Search all vectors in those 5 clusters exactly (~5000 vectors)
4. Return top-10 from the 5000

Total distance computations: 1M (for cluster centroids) + 5000 (within clusters) ≈ 1M
(The 1M is a one-time precomputation per index rebuild; at query time, only ~5000 exact distance ops)

Why IVF can be faster: If nprobe is small (5-10), IVF searches only 5000-10000 vectors exactly instead of 1M. This is faster than HNSW's graph traversal for very large clusters. IVF is especially efficient on GPUs, where massive exact distance computations are parallelizable.

Key tuning parameters:

• k (number of clusters): More clusters = finer granularity, but increases time to find nearest clusters. Typical: 1000-8000 for a 1M corpus.
• nprobe (clusters to search): Higher nprobe improves recall but increases search cost. At nprobe=5, you search 5x more vectors; at nprobe=100, you search almost the whole corpus.
• Training: IVF requires a training phase (k-means clustering on a sample of vectors) before the index is queryable. This is a one-time cost but adds operational complexity.

When IVF wins:

• GPU deployment (exact distance computation is highly parallelizable)
• Very large corpus (>100M vectors) where clustering overhead is amortized
• When you want tight control over search cost (nprobe directly controls how many vectors are examined)

When HNSW wins:

• Incremental indexing (adding vectors one-at-a-time without retraining)
• CPU deployment
• Smaller corpus (<50M vectors)
• Simpler operational model (no training, no cluster management)

Quantization: Compressing vectors

A 768-dimensional float32 vector uses 768 × 4 bytes = 3072 bytes. Storing 1M vectors requires 3GB just for the raw embeddings. Vector databases must also store indexes (pointers, centroids), metadata, and replication. Quantization reduces vector size without major recall loss.

Scalar quantization: The simplest approach. Instead of storing float32 (4 bytes per dimension), store int8 (1 byte per dimension). The vector is scaled to fit the range [0, 255], then integers are rounded.

import numpy as np

def scalar_quantize(vector, bits=8):
    """Quantize float32 vector to int8."""
    # Scale to [0, 255]
    min_val, max_val = vector.min(), vector.max()
    scaled = ((vector - min_val) / (max_val - min_val)) * (2**bits - 1)
    quantized = np.round(scaled).astype(np.uint8)
    return quantized, min_val, max_val

def quantize_dequantize(vector, bits=8):
    """Round-trip a vector through quantization."""
    quantized, min_val, max_val = scalar_quantize(vector, bits)
    # Dequantize
    dequantized = (quantized.astype(np.float32) / (2**bits - 1)) * (max_val - min_val) + min_val
    return dequantized

# Test
original = np.random.randn(768)
dequantized = quantize_dequantize(original, bits=8)
error = np.linalg.norm(original - dequantized)
print(f"Reconstruction error: {error:.4f}")
# Output: ~0.001-0.01 (very small; int8 is quite good)

Scalar quantization impact:

• Storage: 4x reduction (768 dims × 4 bytes → 768 dims × 1 byte)
• Recall loss: 1-2% (sometimes imperceptible)
• Advantages: Simple, fast
• Disadvantages: Information loss in each dimension independently

Product quantization (PQ): More sophisticated. The 768-dim vector is split into chunks (e.g., 4 chunks of 192 dims each). Each chunk is quantized independently using a codebook (precomputed using k-means on a training set). A 768-dim vector becomes 4 × 8-bit codes = 4 bytes (compared to 4 bytes × 768 = 3072 bytes originally).

PQ is more complex but is used in FAISS for extremely large scale (billions of vectors). It reduces storage by 700x with only ~5-10% recall loss on large corpora.

When to quantize:

• Memory is the bottleneck (vector database storage is expensive).
• You can tolerate 2-5% recall loss for a 4x-8x storage reduction.
• You're building a very large system (>100M vectors).

When not to quantize:

• You need absolute best recall (<1% loss tolerance).
• Your corpus is small (<10M vectors) and storage is cheap.
• You're re-indexing frequently (quantization adds overhead at index time).

Putting it together: A production vector search implementation

Here's a realistic example using FAISS (Facebook AI Similarity Search), a free, open-source library that supports HNSW-like algorithms and quantization:

import faiss
import numpy as np
from sentence_transformers import SentenceTransformer

# Step 1: Prepare vectors
model = SentenceTransformer('all-mpnet-base-v2')  # 768 dims

# Load corpus (example: 1M document chunks)
corpus_texts = load_corpus("documents.txt")  # 1M chunks
corpus_embeddings = model.encode(corpus_texts, batch_size=128, show_progress_bar=True)
corpus_embeddings = np.float32(corpus_embeddings)  # FAISS requires float32

print(f"Corpus shape: {corpus_embeddings.shape}")  # (1000000, 768)

# Step 2: Build index with PQ quantization + HNSW-like behavior
# FAISS terminology: "Flat" = exact, "PQ" = product quantization, "IVF" = inverted file

# Option A: IVF with Product Quantization (good for very large corpus)
quantizer = faiss.IndexFlatL2(768)  # Quantization uses L2 distance as baseline
index_ivf = faiss.IndexIVFPQ(
    quantizer,
    768,           # Embedding dimension
    1000,          # Number of clusters (k)
    8,             # Bytes per vector after PQ (8 bytes = 768/96 × 8)
    8              # Number of bits per code
)

# Train on a sample (IVF requires training)
print("Training IVF index...")
sample_indices = np.random.choice(len(corpus_embeddings), size=100000, replace=False)
index_ivf.train(corpus_embeddings[sample_indices])

# Add all vectors
print("Adding vectors...")
index_ivf.add(corpus_embeddings)

# Option B: HNSW-like with flat vectors (smaller corpus)
# index = faiss.IndexHNSWFlat(768, 16)  # 16 = M parameter
# index.add(corpus_embeddings)

# Step 3: Set search parameters
index_ivf.nprobe = 10  # Search 10 nearest clusters (default: 1)

# Step 4: Search
query_text = "how do I reset my password?"
query_embedding = model.encode(query_text, convert_to_numpy=True)
query_embedding = np.float32(query_embedding).reshape(1, -1)

# Search for top-10 nearest neighbors
distances, indices = index_ivf.search(query_embedding, k=10)

print(f"\nTop-10 results:")
for i, (distance, idx) in enumerate(zip(distances[0], indices[0]), 1):
    print(f"{i}. Chunk {idx}: distance={distance:.4f}")
    print(f"   Text: {corpus_texts[idx][:100]}...")

# Step 5: Tune for your latency budget
# Latency vs. recall tradeoff:
for nprobe in [1, 5, 10, 50, 100]:
    index_ivf.nprobe = nprobe
    distances, _ = index_ivf.search(query_embedding, k=10)
    # Time this search and measure recall against ground truth
    # Higher nprobe = higher recall, higher latency

Expected performance (illustrative estimates on a 1M-vector corpus):

| Index type | Recall@10 | Latency (p50) | Memory | Setup complexity | |---|---|---|---|---| | Exact (Flat) | 100% | 500ms | 3GB | Very simple | | IVF (no quantization) | 95% | 20ms | 3GB | Medium | | IVF + PQ (8-byte) | 93% | 10ms | 50MB | Medium | | HNSW (flat) | 96% | 15ms | 3GB | Simple | | HNSW + quantization | 94% | 8ms | 200MB | Simple |

In practice, 90-95% recall is sufficient for RAG (losing 5-10% of the true top-10 candidates still leaves plenty of relevant information for the model to generate a good answer).

Tuning for your latency requirements

Different applications have different latency budgets:

• Interactive chat (p50 < 100ms): Use IVF or HNSW with low nprobe/ef_search. Accept 90-92% recall.
• Batch processing (p50 < 1s): Can afford higher recall (94-96%). Use higher nprobe/ef_search or exact search on a filtered subset.
• Research / offline analysis (no latency constraint): Use exact search or high-recall approximation.

For RAG, latency is usually less critical than for e-commerce search. A 200ms retrieval delay is acceptable if answer quality improves. But for a chat interface, users expect sub-100ms latency.

Tuning workflow:

1. Build the index with your chosen method (IVF, HNSW, etc.).
2. Run your golden set of queries, measuring latency and recall.
3. Adjust nprobe/ef_search until you hit your latency target.
4. If you can't hit latency without losing recall, try a different index type or quantization.

Practice: Build and tune a vector index

1. Generate 10K embeddings (or use a publicly available dataset).
2. Build three indexes: IVF, HNSW, and a flat index.
3. Run 100 search queries and measure latency and recall.
4. Tune nprobe/ef_search to hit your latency budget (e.g., <50ms).
5. Measure total memory (embeddings + index) for each.

Common mistake

Assuming a 1% recall loss is acceptable without measuring impact on downstream answer quality. A retrieval failure in the top-10 might be the only chunk that directly answers the user's question. Test end-to-end: measure both retrieval recall and answer quality together. A 1-2% retrieval loss might cause a 10%+ drop in answer correctness.

Also common: Leaving index parameters at defaults. nprobe=1 and ef_search=200 are reasonable baselines, but your specific latency and recall requirements might need different tuning. Run a benchmark on your corpus before going to production.