Vector Search Internals: HNSW, IVF & Product Quantization
Why exact vector search falls over at scale, and how HNSW, IVF, and Product Quantization trade a little recall for a lot of speed.
Three Seconds Per Query
The refund bot's knowledge base grows past a million chunks, and search latency climbs to 3 seconds per query — long enough that the UI feels broken before the model has even started generating an answer. Nothing about the RAG pipeline from the last phase changed conceptually; the index just got big enough that the way it searches stopped scaling.
The cause is the default, naive way vector search works: flat (exact) search compares the query vector against every single stored vector, one by one, and returns the closest matches. At a few thousand chunks this is instant. At a million, it's a linear scan over a million high-dimensional distance calculations on every single query — the exact bottleneck the refund bot hit.
Approximate Nearest Neighbor: Trading a Little Accuracy for a Lot of Speed
The fix isn't a faster exact search — it's giving up on exact. Approximate Nearest Neighbor (ANN) search accepts that the top-k results might occasionally miss the single mathematically closest vector, in exchange for search times that don't scale linearly with index size. In practice, for RAG-style retrieval, a result that's the 6th-closest vector instead of the exact 1st-closest almost never changes the quality of the final answer — the chunks are all genuinely relevant, just not perfectly ranked — which is why this tradeoff is the default in every production vector database.
HNSW: Search a Graph, Not a List
Hierarchical Navigable Small World (HNSW) graphs, introduced in Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (Malkov & Yashunin), organize vectors into a multi-layered graph instead of a flat list. The top layer has few nodes with long-range connections; each layer below has progressively more nodes with shorter-range connections. A search starts at the sparse top layer, quickly narrows to the right neighborhood, then descends layer by layer, refining within a smaller and smaller region — closer to how you'd navigate a country by first picking the right region on a map, then the city, then the street, rather than checking every address in the country one at a time.
This is exactly what fixed the refund bot's latency: HNSW turns a search that scales linearly with index size into one that scales roughly logarithmically, which is the difference between 3 seconds and under 150 milliseconds at a million chunks.
IVF: Search a Neighborhood, Not the Whole Map
Inverted File Index (IVF) takes a different approach: cluster all vectors into a fixed number of buckets ahead of time (using something like k-means), and at query time, only search the handful of buckets nearest to the query vector instead of the whole index. It's a coarser approximation than HNSW — get the wrong bucket, and you miss everything in it — but it's simpler to build and update incrementally, which matters for the freshness concerns covered in the last phase.
Product Quantization: Shrink Every Vector
Product Quantization (PQ) attacks a different constraint: memory, not speed. It compresses each high-dimensional vector into a much smaller, quantized code by splitting the vector into sub-vectors and representing each sub-vector with a compact learned code instead of the full-precision numbers. The tradeoff is a further, deliberate loss of precision in exchange for a dramatically smaller memory footprint — often combined with IVF (as "IVF+PQ") so the coarse clustering narrows the search and the compressed vectors keep the whole index in memory even at very large scale. FAISS (Johnson et al.), Meta's widely used vector search library, implements this exact combination and is worth knowing by name — it's the reference implementation most other vector databases' internals are compared against.
| Technique | What it optimizes | Tradeoff | Typical use |
|---|---|---|---|
| HNSW | Query speed | More memory (stores graph structure), slower to build/update | Default for most managed vector databases |
| IVF | Query speed | Coarser recall than HNSW; needs periodic re-clustering | Very large, less frequently updated indexes |
| Product Quantization | Memory footprint | Precision loss per vector | Combined with IVF at massive scale |
Zilliz's Vector Index Basics is a solid practical reference for how these three techniques compare and combine in real vector database implementations.
The roadmap's own fix for this scenario paired HNSW with something from two phases back: applying metadata filtering early in the query pipeline — before or during the graph traversal, not as a pass over results afterward — for the same reason covered in the last phase's access-control discussion. Filtering the search space down before searching it is strictly faster than searching everything and discarding the wrong tenant's or wrong audience's results afterward.
Check yourself
A vector index switches from flat (exact) search to HNSW and latency drops from 3 seconds to 150ms at a million vectors. What did this trade away to get that speed?
What's Next
Speed solves the latency problem, but not every retrieval failure is a speed problem. A user searching for an exact error code or product SKU can still get poor results from pure semantic search, no matter how fast the index is — that's a relevance problem, and it needs a different fix.
Frequently asked questions
Do I need to choose between HNSW and IVF, or can a vector database use both?
Most managed vector databases pick one primary indexing strategy per index and expose tuning parameters for it, rather than requiring you to choose the algorithm from scratch — HNSW has become the more common default because it generally offers better recall at comparable speed for typical RAG workloads. IVF (often combined with PQ) tends to show up at larger scale or in memory-constrained deployments.
Does a bigger HNSW graph mean the answer takes longer to retrieve?
Query time grows much more slowly than index size — that's the entire point of the logarithmic-ish scaling — but it isn't free. Index *build* time and memory usage both grow with the number of vectors, which is why re-indexing strategy (covered in the previous phase) matters as much as query-time performance once an index gets large.
Is Product Quantization worth using if memory isn't a constraint?
Generally no — PQ trades precision for memory savings, so if your index comfortably fits in memory without it, skipping PQ keeps full-precision vectors and slightly better recall. It becomes worth the tradeoff specifically once index size threatens to outgrow available memory, not as a default optimization.