Title: Lecture 4 — Inside the Index: HNSW, IVF, and the Filtering Problem
Course: AIINFRA 301: Production RAG & LLMOps — Observability and Evaluation > Section: Week 04 — Indexing Deep Dive: HNSW vs IVF and Metadata Filtering

📖 Lecture — Inside the Index: HNSW, IVF, and the Filtering Problem

By now you've stored embeddings and run similarity search against them. This week we open the hood on how that search actually works at scale, and why the index you choose has real consequences for recall, latency, memory, and — critically — how well your search behaves once you start filtering by metadata.

Why we need approximate search at all

A brute-force nearest-neighbor search compares your query vector against every vector in the collection. That's exact, and it's fine at a few thousand rows. But production RAG corpora run into the millions, and comparing against every vector for every query does not scale. Approximate Nearest Neighbor (ANN) indexes trade a small amount of recall (the percentage of true nearest neighbors actually returned) for large gains in speed. The two dominant ANN strategies you'll meet in nearly every vector database — pgvector, Qdrant, Pinecone, Milvus — are HNSW and IVF. Understanding how each works internally is what lets you tune them instead of just guessing.

HNSW: navigating a graph from the top down

Hierarchical Navigable Small World (HNSW) builds a multi-layer graph over your vectors. The top layer has very few nodes with long-range connections; each layer below has progressively more nodes and shorter, denser connections, until the bottom layer contains every vector. A query starts at an entry point in the sparse top layer, greedily walks toward the closest neighbor it can find, then drops down a layer and repeats, narrowing in on the true nearest neighbors as it descends. This gives roughly O(log n) query complexity — search time grows very slowly as your collection grows — with strong recall at low latency. The cost is memory: HNSW keeps an explicit graph of edges in memory for every vector, so its footprint is larger than a compressed IVF index over the same data. The tunables that matter, using pgvector syntax:

Parameter | When set | What it controls | Typical values
m | Build time | Graph connectivity — how many edges each node keeps per layer | 16 (default)
ef_construction | Build time | Size of the candidate list explored while inserting each node | 64–500
ef_search (hnsw.ef_search) | Query time | Size of the candidate list explored while searching | 20–40 for speed, 100–200 for accuracy

In pgvector, you build the index like this:

CREATE INDEX ON items USING hnsw (embedding vector_l2_ops) WITH (m = 16, ef_construction = 64);

Then, at query time, you tune recall vs. speed without rebuilding anything:

SET hnsw.ef_search = 40;

A notable HNSW property: it can be created with no data present at all. There's no training step — the graph is built incrementally as rows are inserted or as the index is populated. Compare that to IVF below, which needs data up front.

IVF: partition first, then search only the relevant partitions

Inverted File (IVF) indexing takes a different approach. At build time, it runs k-means clustering over your vectors to produce nlist (pgvector calls this lists) partitions, each represented by a centroid. A common sizing guideline is nlist ≈ sqrt(n) for a collection of n vectors — enough partitions to meaningfully narrow the search, but not so many that each partition holds too few points to be useful. At query time, IVF compares your query vector against the centroids, identifies the nprobe (pgvector: probes) closest partitions, and only searches vectors inside those partitions.

CREATE INDEX ON items USING ivfflat (embedding vector_l2_ops) WITH (lists = 100);

The crucial difference from HNSW: IVF requires data to already exist in the table before you build the index, because k-means needs real vectors to compute centroids from. Build an IVF index on an empty table and you'll get poorly-placed (or default) centroids and bad recall until you rebuild. nprobe is a query-time knob, just like ef_search — you can raise or lower it without rebuilding the index, trading latency for recall.

The trade-off table

 | HNSW | IVF (IVFFlat)
Build-time data required | No — can build on empty table | Yes — needs data to train centroids
Query complexity | \~O(log n), graph traversal | Scans nprobe of nlist partitions
Memory footprint | Larger (explicit graph) | Smaller (centroids + flat lists)
Recall/latency control | ef_search (query time) | nprobe (query time)
Behavior under heavy metadata filtering | Degrades — see below | Degrades more gracefully

The non-obvious part: filtering changes the answer

Here's the point that catches teams off guard in production: metadata filtering is not free, and it does not behave the same way across index types. When you filter (e.g., "only search documents where doc_type = 'invoice'") before or during the ANN search, you are asking the index to find nearest neighbors within a restricted subset of the data — and the two index structures cope with that very differently. IVF can filter at the centroid/partition level relatively cleanly: it identifies the closest partitions and then scans within them, checking the filter as it goes. If a partition has very few matching rows, IVF simply returns fewer candidates from that partition — a graceful degradation. HNSW, by contrast, relies on graph connectivity to navigate efficiently. If the filter excludes a large fraction of the vectors near your query's natural path through the graph — say, more than 90% of candidates are excluded — the graph can fragment: the algorithm may need to traverse far more nodes than usual to find enough valid neighbors, and in the worst case its behavior degrades toward something close to a brute-force scan, with much higher latency variance than an unfiltered query. This is exactly the finding highlighted in recent filtered-ANN research (arXiv:2602.11443): filter strategy has to be co-designed with index choice, not bolted on afterward. Practical rule of thumb: if your workload applies highly selective metadata filters routinely, lean toward IVF or a filter-aware index design (e.g., Qdrant's payload indexes, which pre-index metadata fields alongside the HNSW graph specifically to mitigate this problem). If your workload is mostly unfiltered or lightly filtered similarity search, HNSW's superior unfiltered recall/latency usually wins.

Correcting three common misconceptions

"Creating a vector index automatically gives good recall, just faster." Not true. IVFFlat's default probes = 1 yields poor recall out of the box — you must raise nprobe (a common heuristic is ~sqrt(nlist)) to trade latency for recall. And here's the twist: an unindexed pgvector column doing a sequential scan gives you 100% recall (it's exact search) — it's just slow. Recall is never "free" with an ANN index; it's always a dial you have to set deliberately. "Cranking m and ef_construction as high as possible always improves recall." Beyond a fairly modest point, denser graphs give negligible additional recall while sharply increasing memory use, build time, and sometimes even query latency (bigger neighbor lists to traverse). The failure mode to actually watch for is graphs that are too sparse — too-low m or ef_construction leaves the graph poorly connected and recall suffers badly. Aim for "adequately connected," not "maximally dense." "Metadata filtering is free and behaves the same across index types." As covered above, filtering interacts directly with the ANN index's internal structure. HNSW in particular can show much higher latency variance under selective filters than IVF does. This is why filter strategy must be part of your index selection decision from day one, not an afterthought you bolt on once the app is already in production.