Vector databases and ANN indexes: HNSW vs IVF explained

Two components are being named here and they are routinely conflated. Keep them separate:

The distinction matters because exam distractors are built on it, and because the engineering decision is genuinely three-way rather than two-way. You can have (a) no index at all — brute force; (b) an index without a database — FAISS in your process; or (c) a full database. Each is right for a different scale and set of operational needs.

What the ANN index is solving. Exact nearest-neighbour search over N vectors of dimension d means computing N similarities and taking the top k. That is O(N·d) per query — a matrix-vector product, which modern hardware executes extremely well. At N = 10,000 and d = 768 that is 7.7 million multiply-adds, which a CPU does in a few milliseconds and a GPU in microseconds. At N = 100,000,000 it is 77 billion multiply-adds per query, which is not viable at interactive latency.

ANN indexes get around this by not looking at most of the vectors. The price is that they occasionally miss a true nearest neighbour. That price has a name and a number.

Recall@k for an ANN index is the fraction of the true top-k that the approximate search actually returned. If the exact top-10 for a query are the chunks you would get from brute force, and HNSW returns 9 of them plus one interloper, that is recall@10 = 0.9. This is a different quantity from retrieval recall on your evaluation set and confusing the two is a real and consequential error — one measures the index against brute force, the other measures the whole retriever against human judgement. An index at recall 0.99 sitting on top of a bad embedding model still gives you a bad retriever.

L1 — The intuition you can carry into an exam

HNSW is a skip-list of neighbourhoods. Build a graph where each vector is connected to its close neighbours. Add sparse upper layers that let you take long jumps across the space. To search, start at the top layer, greedily walk toward the query, drop a layer, walk again, and finish with a careful local search at the bottom. You touch a few hundred vectors instead of a hundred million.

IVF is a filing cabinet. Cluster the vectors into nlist buckets by k-means. Each bucket has a centroid. To search, compare the query to the nlist centroids, pick the nprobe nearest buckets, and brute-force only those. If you have 4,096 buckets and probe 16, you searched roughly 0.4% of the corpus.

The two knobs to remember, one per index:

• HNSW: ef_search — how wide the search frontier is at query time. Higher = better recall, slower. Tunable per query without rebuilding.
• IVF: nprobe — how many buckets to search. Higher = better recall, slower. Also tunable per query without rebuilding.

That symmetry is the useful mnemonic: both indexes expose one query-time knob that buys recall with latency, and neither requires a rebuild to turn it.

L2 — The mechanism, index by index

HNSW — Hierarchical Navigable Small World.

Construction inserts vectors one at a time. Each vector is assigned a maximum layer by an exponentially decaying random draw, so most vectors live only in layer 0 and a few reach the sparse top layers. When inserting, the algorithm finds the vector's nearest neighbours in each layer it occupies and links to M of them, pruning links to keep the graph navigable rather than clumped.

layer 2      ●───────────────────────●              (very sparse: long jumps)
              \                     /
layer 1      ●──●──────●───────●──●──●              (medium density)
              \  \    /  \    /  /
layer 0    ●─●─●─●─●─●─●─●─●─●─●─●─●─●─●─●          (every vector, local links)
                        ▲
                      query lands here after descending

Search: enter at the top layer's entry point, greedily move to whichever neighbour is closer to the query until no neighbour improves, then descend and repeat. At layer 0, instead of pure greedy, maintain a candidate list of size ef_search so the search can escape local minima. Return the best k.

The parameters:

HNSW's characteristic properties: excellent recall/latency at high recall targets, high memory footprint (the graph links are stored on top of the vectors, and it wants to be resident in RAM), incremental insertion is natural (you add a vector and link it), and deletion is awkward — most implementations tombstone rather than truly remove, so a high-churn corpus degrades until rebuilt.

IVF — inverted file index.

Construction requires a training step: run k-means over a sample of the vectors to find nlist centroids. Then assign every vector to its nearest centroid's posting list.

centroid c1 → [v17, v204, v991, ...]
centroid c2 → [v3,  v88,  v412, ...]
...
centroid c4096 → [...]

query q:  compare q to all 4096 centroids → nearest 16 → brute-force those 16 lists

The parameters:

IVF's characteristic properties: lower memory than HNSW (no graph links), fast build, requires training (which means it must see representative data before it is useful, and a corpus whose distribution shifts wants retraining), and a specific failure mode: a true nearest neighbour sitting just across a cluster boundary is missed unless nprobe is large enough to include the neighbouring bucket. Recall degrades in a spatially structured way rather than randomly.

IVF-PQ adds product quantization: each vector is split into sub-vectors, each sub-vector is replaced by the id of its nearest entry in a small learned codebook, and distances are computed on the compressed codes. This is a compression technique layered on IVF, and it is how billion-scale indexes fit in memory. It costs additional recall on top of IVF's own approximation. Know that PQ means "compressed vectors, more speed and less memory, less recall" — the depth beyond that is well past what the exam calibration suggests you need [FIELD].

L3 — Filtered ANN search, and why it is the hard part

07-03 and 07-05 both require filtering retrieval by metadata — status, date, trust tier, and above all permissions. Naïvely you would think this is easy: search, then drop the ineligible results. It is not easy, and the reason is structural.

Three strategies exist, and they have genuinely different properties:

The critical insight, and the one to carry into a design review: post-filtering silently changes your result-set size, and it does so exactly when the filter matters most. Consider a corpus where 1% of chunks belong to a given team. Retrieve top-20 by similarity across the whole corpus and post-filter to that team; the expected number of survivors is 0.2. You asked for 20 results and got zero or one, with no error. The system reports "no relevant documents found" for a question whose answer is sitting in the index.

Overfetching — retrieve top-500, then filter — reduces but does not eliminate this, and it makes latency unpredictable in the cases where the filter is most selective. The general fix is that selective filters want pre-filtering, and unselective filters want post-filtering, and a mature vector database estimates selectivity and picks. What you should know for the exam is that the interaction exists, that it is a real reason filtered vector search is harder than unfiltered, and that for authorisation the answer is never post-filtering regardless of performance, because it is a security property rather than a latency property.

One more L3 note worth having: HNSW and IVF are both in-memory-oriented structures. Disk-resident variants exist (DiskANN and similar) and they matter enormously at very large scale, because RAM for a billion 768-dimension float32 vectors is roughly 3 TB before index overhead. If a scenario question mentions a corpus size that clearly exceeds plausible memory, the intended reasoning is usually about quantization, sharding, or disk-based indexing rather than about tuning ef_search.

And the layer confusion this table is built to prevent — three different things that all get called "the index":

That first row is a genuine trap. BM25's inverted index maps terms to documents. IVF's inverted file maps centroids to vectors. They share a name and a general shape — a dictionary of posting lists — and nothing else. A question that asks "which structure supports BM25 keyword search?" wants "inverted index"; one that asks "which ANN index partitions vectors by k-means centroids?" wants IVF.

The numbers below are constructed arithmetic from stated assumptions, not measurements. They exist to make the scale argument computable; treat the assumptions as illustrative and re-derive with your own if you need a real answer.

Assumptions, all stated: 768-dimension float32 vectors (3,072 bytes each, per M0.4 on units); the exact-search cost model is one multiply-add per dimension per vector.

Case A — 10,000 chunks

storage:  10,000 × 3,072 B          = 30.7 MB      → fits in a laptop's RAM trivially
one query: 10,000 × 768 multiply-adds = 7.68 M FLOPs (×2 for mul+add)

A 7.7-million-operation matrix-vector product is not a performance problem on any hardware built this decade. A single numpy.dot call over a (10000, 768) matrix returns exact similarities, and you sort them and take the top k. Recall is 1.0 by construction. There is no index, no server, no training step, no nprobe, no tombstones, and filtering is a boolean mask applied before the dot product, which is exactly the pre-filter semantics 07-05 requires and which a vector database makes you work for.

What you would gain from a vector database at this scale: persistence you could get from a .npy file, and an API you could write in twenty lines. What you would pay: a service to deploy and monitor, a client library, a schema, a consistency model, an approximation you did not need, and a filtering pathology you did not have before.

Case B — 1,000,000 chunks

storage:  1,000,000 × 3,072 B       = 3.07 GB      → still fits in RAM on a normal server
one query: 1M × 768 multiply-adds    = 768 M FLOPs

Now it depends on your latency budget and your concurrency. A single exact query is still tractable — on a GPU this is a small matrix multiply and genuinely fast; on a CPU it is tens of milliseconds. But multiply by concurrent requests and the arithmetic stops being free. This is the region where an ANN index starts to pay, and where "which index" becomes a real question rather than a preference. It is also the region where the operational features of a database — durability, incremental updates, metadata filtering, replication — start to matter as much as the search algorithm.

Case C — 100,000,000 chunks

storage:  100M × 3,072 B            = 307 GB       → exceeds single-machine RAM for most deployments
one query: 100M × 768 multiply-adds  = 76.8 G FLOPs

Exact search is now clearly off the table at interactive latency, and raw float32 storage is a capacity problem before it is a speed problem. This is where quantization (12-01, 12-02 for the general precision concepts) and sharding are not optimisations but requirements, and where IVF-PQ or a disk-based index is the shape of the answer.

Reading the three cases together

The decision boundary is not a single number, and anyone who gives you one is guessing. It is a function of corpus size, latency budget, query concurrency, update rate, filtering selectivity, and how much recall loss your evaluation set says you can absorb. But the shape is clear and it is the exam-relevant part:

And the honest counterpoint, because "you don't need a vector database" is itself an over-claim: scale is not the only reason to adopt one. Durable storage with crash recovery, concurrent writes while serving reads, metadata filtering with sane semantics, per-tenant isolation, snapshots, and access control are real features, and building them yourself around a NumPy array is how you end up writing a bad database. If you need those properties at 10,000 chunks, take the database — just take it for those reasons, and know that you are not taking it for speed.

That last row is the operational thesis of the lesson. Index choice is a latency decision made after retrieval quality is established. Teams routinely invert this: they choose an index in week one, then spend week six wondering why answers are wrong, when the answer is in chunking (06-02), parsing (06-01), boilerplate (06-04), or encoder mismatch (07-02) — none of which any index can fix.

The official objective text names vector databases explicitly. Objective 1.6 (and its Software Development twin 4.3) reads: familiarity with the capabilities of Python natural language packages (spaCy, NumPy, vector databases, etc.) [OFFICIAL]. That is one of the few places the blueprint names a category of infrastructure directly, and "familiarity with the capabilities" is precisely the depth this lesson targets: what they do, when they are needed, and what they cost.

Also served: 1.4 (curate and embed content datasets for RAGs — the index is where embedded content lands), 1.3 and 4.2 (build RAG use cases), and 4.4 (identify system data, hardware, or software components required to meet user needs), which is almost a restatement of §5's decision table. The course index places dense-versus-sparse retrieval, ANN indexing with HNSW and IVF, the recall/latency trade-off, metadata filtering, hybrid search, and when a vector DB is unnecessary in one coherent block — and that last item is the distinctive claim of this lesson.

Exam depth is general-level; candidate reports agree that deep technical dives, config detail, and hardware spec sheets were overkill and did not appear [FIELD]. Practically: be able to name HNSW as a graph index and IVF as a cluster/partition index, state that ANN trades recall for latency, and identify when exact search suffices. Do not memorise ef_construction defaults.

Question phrasings you should recognise:

Distractor families:

• "A vector database is required for RAG." It is not. RAG requires retrieval; retrieval does not require a database.
• BM25's inverted index conflated with IVF. Different layers, coincidental name overlap.
• HNSW described as exact. It is approximate by construction. Only brute force is exact.
• "ANN indexes improve retrieval accuracy." They reduce it relative to exact search. They improve latency. A question that offers "use HNSW to improve retrieval quality" is inverting the trade-off.
• The vector database credited with the embedding. The embedding model produces vectors (07-02); the database stores and searches them.
• "Post-filter for permissions." Performance-plausible, security-wrong (07-05).
• Recall@k against brute force conflated with retrieval recall against human labels. Two different measurements answering two different questions.
• "Increase nprobe to fix irrelevant results." If the embedding put the wrong chunk nearest, searching harder finds it faster. nprobe fixes misses, never wrong-but-near results — which is the 07-03 blind-spot family.

Mistakes 7 and 9 are two faces of one misconception: that the index is where retrieval quality comes from. It is not. The index determines whether you found the nearest vectors; the embedding model, the chunking, and the corpus determine whether the nearest vectors are the right passages. Almost every disappointing RAG system is failing at the second, and almost every team's first instinct is to tune the first.

Whenever exact in-memory search meets your latency budget and you do not need the database's operational features. Concretely, that covers a large fraction of real projects:

Internal documentation search. A company handbook, a product manual set, a runbook collection — these are thousands of chunks, not millions. Storage is measured in tens of megabytes.

Single-product support knowledge bases. Hundreds to low thousands of articles.

Anything you are still prototyping. During development, exact search is strictly better: it removes the approximation variable, so when retrieval is wrong you know the index is not the reason. That elimination is worth more than the latency you saved.

Anything you are evaluating. When you measure recall@k on your eval set (03-04), you want to know what the retrieval method achieves, not what the method-plus-approximation achieves. Measure with exact search, then measure how much the index costs you, separately.

The implementation is genuinely small:

# scores for one query against the whole corpus — exact, no index
import numpy as np
V = np.load("vectors.npy")          # (n_chunks, dim), L2-normalised
q = embed(query)                    # (dim,), L2-normalised
scores = V @ q                      # cosine similarity, since both are unit-length
top = np.argsort(-scores)[:k]

# metadata pre-filter is a boolean mask applied BEFORE the dot product
eligible = mask_for_user(user)       # (n_chunks,) bool
scores = np.where(eligible, V @ q, -np.inf)

Look at what those four lines give you that a database makes you configure: exact recall, cosine similarity by construction (because the vectors are normalised — M0.1), and correct pre-filter semantics for free. The mask is applied before ranking, so a selective filter returns k eligible results rather than however many survived a post-filter.

When it is necessary, and this list is short and honest: corpus size beyond comfortable RAM; query concurrency high enough that per-query linear scans saturate your compute; continuous writes while serving reads; durable storage with recovery guarantees; multi-tenancy with hard isolation; or a metadata filtering story more complex than a boolean mask. Those are all legitimate and none of them is "we are doing RAG".

If you must choose one without measuring, the field default is HNSW, because it gives high recall at low latency, supports incremental insertion naturally, and requires no training pass. Most vector databases default to it for exactly those reasons.

Choose IVF when memory is the binding constraint, when build time matters more than query latency, or when your corpus has heavy delete churn that would leave HNSW accumulating tombstones. Choose IVF-PQ when the corpus does not fit in memory as raw vectors and you have measured that the additional recall loss is acceptable on your evaluation set.

Two closing cautions. First, do not choose an index by reading benchmark charts. Published ANN benchmarks are run on public datasets with particular dimensionalities and distributions, and your corpus is not those datasets. The only number that governs is recall against exact search on your vectors at your latency target. Second, index choice is usually not your bottleneck. If you have not yet measured BM25 as a baseline (07-01), verified encoder consistency (07-02), fixed chunking (06-02), and stripped boilerplate (06-04), index selection is the least valuable decision available to you.

It costs exactly what your evaluation set says it costs, and the discipline is to measure it as a separate quantity from everything else in the pipeline. The procedure:

1. Build the exact baseline. For a sample of your eval queries, compute the true top-k by brute force. This is ground truth for the index, and it is cheap on a sample even when it is infeasible in production.
2. Measure index recall@k at several settings of the query-time knob — a few values of ef_search or nprobe — as the fraction of the exact top-k that the index returned.
3. Measure latency at each setting, at realistic concurrency rather than one query at a time.
4. Plot the pair and choose a point. Pick the lowest-latency setting whose index recall does not measurably move your end-to-end retrieval recall on the eval set.

Step 4 is the part that gets skipped, and it contains the real insight: index recall below 1.0 is only a problem if it changes the answer. If the true top-10 contains three passages that answer the question and the index returns eight of the ten including all three, your end-to-end quality is untouched and you banked the latency. Conversely, if the one passage that answers the question is the one the index missed, a recall of 0.9 was catastrophic for that query. Which case you are in depends on redundancy in your corpus, and only measurement tells you.

The second thing measurement protects you from is attributing a quality problem to the index when the index is fine. Run the eval set with exact search and again with the ANN index. If the two scores match, the index is exonerated and every remaining quality problem lives upstream — in the encoder, the chunks, the corpus, or the ranking. That is a two-line experiment that saves days, and it is the same attribution discipline 07-10 applies to the pipeline as a whole.

• A vector database is not an ANN index. The index is the algorithm (HNSW, IVF); the database is the system around it that adds persistence, metadata, filtering, and access control.
• HNSW is a navigable multi-layer graph; IVF is k-means clusters with posting lists. Both expose one query-time knob — ef_search and nprobe respectively — that buys recall with latency and needs no rebuild.
• ANN trades recall for latency. It never improves retrieval accuracy relative to exact search; a question offering it as an accuracy improvement has inverted the trade-off.
• The worked example's headline result: 10,000 chunks at 768 dimensions is 30.7 MB and 7.7 million multiply-adds per query. That is a numpy.dot, exact, with recall 1.0 and correct pre-filter semantics for free.
• A corpus of ten thousand chunks does not need a vector database. Adopting one anyway is the most common over-engineering in applied RAG.
• Post-filtering silently shrinks the result set, worst when the filter is most selective. Selective filters want pre-filtering; permissions want pre-filtering unconditionally (07-05).
• IVF's "inverted file" is not BM25's "inverted index." Same word, different layers of the stack.
• Index recall and retrieval recall are different measurements. Compare the index to brute force; compare the retriever to human labels. Fixing the second by tuning the first does not work.
• Choose the index after retrieval quality is established, not before. The index decides whether you found the nearest vectors; the encoder, chunking, and corpus decide whether the nearest vectors are the right ones.

The filtering discussion in this lesson deferred one case as too important to fold in: what happens when different users are allowed to see different documents. Similarity has no authorisation model, post-filtering means the system already read data the requester was not entitled to, and a retrieval index that mixes tenants is a data-exfiltration path that a well-crafted question can walk straight down. Next: 07-05 covers access control in RAG retrieval — why the permission predicate must live inside the retrieval query rather than after it, what to do about documents whose permissions change after indexing, and why a prompt instruction telling the model not to reveal restricted content is not a security control.