HNSW + PQ: The Secret Sauce Behind Billion-Scale Vector Search (And Why Your FAISS Index Is Lying to You)

The Hook: You’ve Built a Ferrari with Square Tires

You’ve done it. You’ve fine-tuned your BERT model, you’ve dumped your embeddings into a vector database, and you’ve got a slick demo that returns semantic search results in 50 milliseconds. You’re feeling pretty good.

Then, you scale.

You go from 1 million vectors to 100 million. Your query latency balloons from 50ms to seconds. Your RAM usage looks like a Bitcoin mining rig’s power bill. And your recall? It’s hovering around 70%, which means your users are getting irrelevant results and they don’t know why. You’ve just hit the wall that every ML engineer eventually slams into: Naive Approximate Nearest Neighbor (ANN) search doesn’t scale. Period.

But wait. There’s a magic acronym combo you’ve seen in the GitHub repos of every vector database vendor (Pinecone, Weaviate, Milvus, Qdrant) that promises to fix this: HNSW+PQ. It sounds like a fancy cocktail order, but it’s actually the most brutal, elegant, and effective engineering hack in the machine learning infrastructure space.

If you want to serve billions of embeddings on a single (or modest cluster) of commodity hardware, you need to stop treating your vectors like they exist in a normal spatial dimension. You need to slice them, dice them, and build a graph that looks like a neurosurgeon’s map of the brain.

Buckle up. We’re going under the hood of the most important scaling technology you’ve never fully understood.

The Hype vs. The Reality: Why Everyone is Talking About “Hybrid Search”

Before we dive into the math, let’s address the elephant in the room. Why did 2023 and 2024 turn into the “Year of the Vector Database”? It’s not just because RAG (Retrieval-Augmented Generation) got hot. It’s because Latency is the new Currency.

LLMs are slow. They generate tokens at a snail’s pace compared to disk I/O. So, engineers realized they needed to pre-filter context. They turned to vector search to find the “needles” in the haystack of documents to stuff into the prompt. This created a massive hype cycle.

Everyone started screaming about HNSW (Hierarchical Navigable Small Worlds) as if it were a new invention. Here’s the secret: HNSW is old. It was published in 2016 by Yury Malkov. But it’s only now hitting its stride because the data volume has finally caught up to the algorithm’s complexity.

The reality is that pure HNSW is a memory hog. It stores the graph connections (neighbors) alongside the vectors. For a million vectors, that’s fine. For a billion, you’re looking at several hundred gigabytes of RAM just for the graph structure. That’s not scalable. That’s a supercomputer budget.

So, the industry shifted to a two-pronged attack:

1. HNSW for the graph traversal (the “navigational” smarts).
2. PQ (Product Quantization) for the vector compression (the “storage” muscle).

Together, they form a dual-stage filtering mechanism that makes billion-scale search possible without a supercomputer. Let’s dissect each one.

Part 1: HNSW – Building the “Small World” Highway System

The Multi-Layer Graph Theory

Imagine you’re in a massive city— let’s call it “Vectorville.” There are a billion houses (your embeddings). You need to find the closest house to a specific GPS coordinate (your query). If you try to walk to every house, you’ll die of old age.

HNSW solves this by creating multiple layers of maps.

• Layer 0 (The Ground Floor): Contains all billion data points. Edges connect actually close neighbors. This layer is highly granular but slow to navigate if you start here.
• Layer 1: Contains a random subset of the points (maybe 1 in 10).
• Layer 2: Contains 1 in 100.
• Layer 3 (The Penthouse): Contains the “hubs”— only a handful of points that are extremely well-connected.

The Search Algorithm: “Zoom In, Then Micro-Accurate”

When you query, you don’t start on Layer 0. You always start at Layer 3 (the top).

1. Greedy Descent: You look at the penthouse points. Which one is closest to your query? You move to that one. Then you check its neighbors on that layer. Are they closer? If yes, go there. Repeat until you can’t find a closer point on that layer.
2. The Drop: You take that local minimum and drop it down to the next layer (Layer 2). You repeat the greedy search there, using the previous point as your starting seed.
3. The Final Sweep: You descend all the way to Layer 0, where you now have a very good approximation of where your query sits. Here, you perform a more exhaustive scan of the local neighbors.

The Technical Magic: This works because of the “Small World” property. In a random graph, the diameter (the average shortest path between nodes) is small. But in HNSW, the probability of a long-edge shortcut is high. The top layers are essentially “highways” that teleport you across the vector space in a few hops. You bypass the “local minima” problem of brute-force KNN by starting broad and narrowing down.

The Engineering Catch: The M and efConstruction Hyperparameters

• M (Max Neighbors): Controls how many bidirectional links each node keeps. Higher M = higher recall, higher memory, slower insertion. Lower M = faster, but your graph becomes fragmented.
• efConstruction: Controls the size of the dynamic candidate list during insertion. If you set this too low, you create a “greedy” graph that builds suboptimal links.

The Pro Tip: Most engineers set M=16 and forget it. But for datasets with high intrinsic dimensionality (like text embeddings from LLMs), you need to crank M to 32 or 48. The “curse of dimensionality” makes distances converge, so you need more edges to disambiguate.

Part 2: Product Quantization – The Art of Turning a Vector into a Skeleton

Here’s where the “Cloudflare-style” engineering logic kicks in. You can’t afford to store 1 billion * floats in RAM. That’s 4 gigabytes per billion dimensions. If your model produces 768-dim embeddings, that’s ~3 TB. No single server has that.

HNSW alone will tank your memory. We need lossy compression.

Enter Product Quantization (PQ). This isn’t your average dimensionality reduction like PCA. This is a codebook-based compression that allows SIMD (Single Instruction, Multiple Data) ops to fly.

The Subspace Splitting Trick

The core idea is to break a high-dimensional vector into M distinct sub-vectors.

Let’s say we have a 96-dim vector. We split it into M=8 sub-vectors, each of dimension D=12.

• Step 1: Training. You take a random sample of your entire dataset (e.g., 1 million vectors). You split them all into sub-vectors. For each of the 8 subspaces, you run a K-Means clustering algorithm (usually with K=256 clusters, or 8 bits).
• Step 2: The Codebooks. You now have 8 codebooks. Each codebook has 256 “centroids” (representative vectors). These centroids represent the “typical” patterns found in that subspace.
• Step 3: Encoding. For every single vector in your billion-scale dataset, you look at its sub-vector 1. You find the nearest centroid in codebook 1. You store just the ID of that centroid (0–255). You do this for all 8 sub-vectors.

The Result? You’ve replaced a 96-dim vector (768 bytes) with an 8-byte code (8 integers). That’s a 96x compression ratio.

Query Time: The Asymmetric Distance Computation (ADC)

Here is the killer feature that makes PQ scale. You don’t decompress the database to query it. You use Asymmetric Distance Computation (ADC).

• You keep the query vector full resolution (float32).
• You split the query into the same 8 sub-vectors.
• For each subspace, you use the Lookup Table (LUT). You calculate the distance between the query’s sub-vector and all 256 centroids in that subspace. You store these distances in a table.

Now, when you want to calculate the distance to a compressed database vector, you just look up the pre-computed distances for each of its 8 centroids and add them up.

Why this is fast: The distance calculation becomes a add-to-accumulator operation on integers, not a multi-dimensional floating-point dot product. Modern CPUs can do this with AVX-512 vector extensions incredibly fast.

The Catch: PQ is lossy. You’re comparing your query to the centroids. If two different vectors map to the same centroid, you’ve lost the fine-grained distinction between them. This is why you cannot use PQ as your sole metric.

The Grand Fusion: HNSW + PQ = The Hybrid Beast

Here’s where the engineering brilliance “clicks.” You don’t use HNSW for distances. You use HNSW to find candidates.

The Two-Stage Retrieval Pipeline

1. Stage 1: Graph Traversal with Compressed Vectors.

   • When you traverse the HNSW graph, the distance between the query and a neighbor is not the true distance.
   • It’s the PQ distance (the distance to the reconstructed centroids).
   • This is fine because we don’t need perfect distances to navigate. We just need to know relative distances. Is Node A closer than Node B? As long as the compression is decent, the ranking order holds up roughly.
   • Note: Some advanced implementations (like FAISS’s IVFPQ) use SQ (Scalar Quantization) for the graph navigation and PQ for the refinement, but the principle holds.

2. Stage 2: Re-ranking with Exact Vectors.

   • You collect the top N candidates (e.g., top 100) from the graph traversal.
   • You now load the original, uncompressed vectors for those 100 candidates from disk (or a separate memory pool).
   • You compute the exact Euclidean cosine or dot product between your full-resolution query and these 100 true vectors.
   • You sort, and return the top 10.

This is the “secret sauce.” You’re sacrificing accuracy in the search phase but gaining absurd speed and memory efficiency, then recouping the accuracy in the refinement phase.

Why This Scales to Billions

• Memory Efficiency: You store the HNSW graph links (which are just 32-bit integers pointing to memory addresses) and the PQ codes (8 bytes each). The actual float32 vectors go on disk or in a separate cold storage bucket.
• Cache Locality: The PQ codes are stored contiguously. When you load a node from memory, you load its 8-byte code and its 64 links. That fits nicely into L1/L2 cache lines. With HNSW alone, you’d be jumping around memory, causing cache misses.

The Architecture Deep-Dive: A Realistic Deployment Scenario

Let’s talk about the actual infra guts. You can’t just install a library and hope for the best. Here’s what a realistic system looks like for 1 Billion vectors (768 dims, float32).

The Hardware Config

• The Index Node (Query Node):
  • CPU: 32-core (needs high frequency, not necessarily high core count).
  • RAM: 128GB.
  • Storage: NVMe SSD.
• The Vector Store (Object Storage/S3):
  • Holds the raw float32 vectors. This is your source of truth for re-ranking.

The Index Build Phase (Batch Processing)

You don’t stream these. You build in a MapReduce fashion.

1. Sampling: Take 1M vectors, run PCA to reduce from 768 to say 96 dims (just for the graph). We call this the OPQ matrix.
2. Training: Run K-Means on the 96-dim data to learn the PQ codebooks.
3. Encoding: Run a massive Spark/Beam job that loads the full vectors, projects them, and gates them through the codebooks. Output is a binary file of just the compressed codes.
4. Graphical Build: Insert the 1 billion compressed vectors into the HNSW graph on the index node. This takes days. You have to do this in batches to avoid memory overflow.

A note on memory during the build: If you follow naive HNSW, you’ll OOM. The trick is to use a “Distributed” index build. You build 100 smaller HNSW graphs (each with 10M nodes), then merge them by connecting the “entry points” (the top-layer hubs) at the end. This induces a tiny amount of recall loss if done wrong, but it’s the only way to build a billion-scale graph in real time.

The Query Path (Data Flow)

1. Ingest: Query comes in (768 dims).
2. OPQ Transform: The query is reduced to 96 dims using the cached OPQ matrix.
3. PQ Encoding: The query is not PQ encoded! It stays in high precision.
4. Graph Search: The query traverses the HNSW graph using the PQ ADC distances. efSearch is set to 1000 (this is the dynamic candidate list size).
5. Candidate Fetch: We get 1,000 candidate IDs from the graph.
6. The “Fetch & Re-rank”: The system goes to S3 and grabs these 1,000 full-resolution vectors (they are likely cached in memory on a hot node).
7. Exact Score: We compute exact distances and sort.

Latency: If done correctly, the graph search takes ~10ms, the S3 fetch takes ~20ms (if cached, 1ms), and the re-rank takes ~5ms. Total: ~30ms p99. That’s how you serve billions of vectors.

The “Gotchas” Nobody Talks About

Let’s get into the technical weeds. Why do engineers pull their hair out with this?

The efSearch vs. M Trade-off

The Secret to Recall: Your recall is determined by how many nodes you visit. efSearch controls this. If you set efSearch too high, you’re basically doing a BFS (Breadth-First Search), which is slow. If too low, you miss all the good neighbors. The trick is to dynamically adjust efSearch based on query load and the distribution of your data.

The PQ “Clustering Bias”

If your data is inherently clustered (e.g., all images of cats, then all images of dogs), K-Means will do great. But if your data is a uniform blob (which happens with L2-normalized embeddings from OpenAI), PQ codebooks become inefficient. The centroids don’t represent the “empty” space well. You end up with high quantization error.

Solution: Use OPQ (Optimized Product Quantization). It learns a rotation matrix that aligns the dimensions so that the data is more amenable to splitting into subspaces. Always, always use OPQ matrices over raw PQ.

The “Re-ranking” Bottleneck

If you fetch 1,000 vectors to re-rank, you might be pulling 1,000 _ 768 dims _ 4 bytes = ~3 MB of data per query. If you get 100 QPS, that’s 300 MB/s transfer from your object store. That will saturate a single 10GB NIC.

The Fix: You don’t store the raw vector on S3. You store the raw vector in a memory-mapped file on the index node’s SSD, and use mmap with MADV_RANDOM to read only the needed pages. Or, you cache the “hot” clusters in RAM.

The Code: A Skim Through the FAISS Implementation

If you want to see this in action, the FAISS library is basically the reference implementation. Here’s a snippet that shows how to set this up (conceptually):

import faiss

# Dimension of your embeddings
d = 768
# Number of subspaces for PQ
m = 96 # each subvector is 8 dims
# Codebook size (we use 8 bits = 256 centroids)
nbits = 8

# Build the OPQ Matrix + PQ Index
# This creates a "Pre-transform" that rotates the data
opq_matrix = faiss.OPQMatrix(d, m)
index_pq = faiss.IndexPQ(d, m, nbits)

# Combine into a 2-level structure: OPQ rotates, then PQ quantizes.
index = faiss.IndexPreTransform(opq_matrix, index_pq)

# Now, the HNSW part - This is where it gets tricky.
# faiss doesn't directly support HNSW with PQ* re-ranking in one class.
# You typically build a "HNSW graph" for navigation,
# and make the *storage* the PQ code.

# Here is the full hybrid:
quantizer = faiss.IndexHNSWFlat(d, 32) # 32 is M, storage is raw float (for nav)
# We wrap the quantizer with the PQ indexing
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, nbits)
index.nprobe = 200 # number of cells (clusters) to search

# Train and Add
index.train(training_vectors)
index.add(all_vectors)

# Search with re-ranking?
# Actually, FAISS does the re-ranking internally via a "look-up table"
# that computes exact distances to the reconstructed vectors of the candidates.

The Crucial Detail: Notice that IndexIVFPQ uses an Inverted File (IVF) as the quantizer, not HNSW. But the principle is identical: Use the graph to find candidate cells, use PQ to compute rough distances within those cells, and then use the exact storage for the final score.

The Final Verdict: Is This the Silver Bullet?

HNSW+PQ is the reason vector databases can exist in the cloud today. Without PQ, the memory cost per vector would make “serverless vector databases” economically impossible.

But here is the hard truth: You cannot just slap this together and expect good results. You need to tune:

1. The OPQ rotation: Is your data balanced across the subspaces?
2. The m parameter: How much compression vs. recall accuracy are you willing to sacrifice? Going from m=64 to m=96 is a massive recall boost.
3. The Re-ranking strategy: Are you able to shrink your candidate set to <500?

The Curious Case of the Billion-Vector Query: If you’ve done it right, you’ll find that a query against 1 billion vectors takes longer than a query against 10 million only by a factor of 2-3x. Why? Because the HNSW graph fundamentally reduces the “search space” logarithmically. You are not scanning; you are traversing.

This isn’t just a database optimization; it’s a fundamental law of physics for ML infrastructure. The era of loading everything into RAM is over. The era of compressing intelligence into the tightest possible mathematical representation is here.

Go build your graph. Go quantize your vectors. Stop waiting for brute force to save you.

Found this deep dive useful? If you’re wrestling with GPU OOM errors or insane recall issues on your current index, drop a comment below—I’d love to hear how your graph traversal is going.