Choosing a Vector Index: HNSW, IVF, and the Trade-Offs

The situation

A knowledge-base assistant on Amazon Bedrock retrieves passages to ground its answers. The embeddings live in a vector store, and at launch the corpus was 40,000 chunksChunkingSplitting documents into retrievable pieces before embedding them – small enough to match precisely, big enough to still make sense. . Queries came back in a few milliseconds and recall was effectively perfect, because the store was doing an exact scan over every vector on every query. Nobody thought about the index because there wasn’t one worth naming.

Eighteen months later the corpus is 12 million chunks and growing, the embeddings are 1,024 dimensionsEmbedding dimensionHow many numbers each embedding vector holds – fewer means a smaller, cheaper, faster index and slightly blurrier matching. , and the same exact scan now takes over a second per query. Retrieval has become the slowest part of the request. The obvious lever, a larger instance, buys a little headroom and then the curve catches up again, because exact search cost grows with the corpus and no amount of hardware changes that shape.

The store on offer, whether that’s Amazon OpenSearch Service with its k-NN plug-in or Aurora PostgreSQL with pgvector, supports approximate-nearest-neighbourANNIndex structures (HNSW graphs, IVF partitions) that answer the k-nearest-neighbours question fast by giving up guaranteed exactness – recall becomes a tunable knob rather than a certainty. indexes. Switching to one will make queries fast again. The question underneath is which index, and what it quietly costs: a percent or two of recall, a chunk of memory, a longer build, or all three. Get it wrong and the assistant either answers slowly, answers from the wrong passages, or runs a bill nobody signed off.

What actually matters

Vector search is a three-way tension, and every index choice is a point inside it. The three corners are recall (how often the approximate search returns the same neighbours an exact search would), latency (how fast a query comes back), and memory or cost (how much RAM and storage the index needs to hold). You cannot max all three at once. Exact search sits at the perfect-recall corner and pays for it in latency at scale; the approximate indexes buy latency back by giving up a controllable slice of recall, and they differ mainly in how much memory they demand to do it.

The first thing worth naming is that corpus size decides whether you even have a problem. At tens of thousands of vectors, an exact scan is fine and an index is premature; the scan is fast and its recall is a guaranteed 100%. The exact scan’s cost grows with the number of vectors, so somewhere between hundreds of thousands and a few million, depending on dimension and latency budget, the scan crosses from “instant” to “the bottleneck”. Approximate indexes exist to break that link, so their query cost grows far more slowly than the corpus does. The decision to index is really a decision about where you are on that curve.

The second is that recall is a dial, not a fixed property of the index. Every approximate index has parameters that trade recall against speed and memory, and the same index can be tuned to 99% recall or 90% recall on the same data. That means “which index” and “how is it tuned” are one question, not two. An HNSW index with a stingy search parameter can return worse results than a well-tuned IVF index, and vice versa. Quoting an index’s recall without quoting its parameters is meaningless.

The third is that build cost and update cost are separate from query cost, and easy to forget until they bite. A graph index that answers queries beautifully can take hours to build and rebuild, and some index types need a training pass over a sample of the data before they can be populated at all. If the corpus changes constantly, the cost of keeping the index current can dominate the cost of querying it. A store that indexes 12 million vectors nightly has a very different profile from one that ingests a steady trickle.

The fourth is that memory is often the real budget. The high-recall graph indexes generally keep the graph and the full-precision vectors resident in RAM to hit their latency, and at 12 million vectors of 1,024 dimensions that is tens of gigabytes before you count overhead. Memory is what turns a good index into an expensive one, which is why the compression techniques exist: they trade a further slice of recall for a much smaller footprint, and at large scale that trade is often what makes the whole thing affordable.

The last is that none of this is answerable from a spec sheet. Recall depends on your embedding distribution, your query distribution, and your parameters, all of which are specific to your data. The only trustworthy numbers come from building a small ground-truth set (exact-search results for a sample of real queries) and measuring approximate recall and latency against it. Every recommendation below is a starting point to measure from, not a setting to trust blind.

What we’ll filter on

1. Corpus scale, are we at tens of thousands of vectors where exact search is fine, or millions where an approximate index is the point?
2. Recall target, how close to exact-search results does retrieval need to be, and how much drop is tolerable?
3. Query latency budget, what per-query time does the request path allow for the search step?
4. Memory and cost ceiling, how much RAM is the index allowed to consume, and does that force compression?
5. Build and update profile, is the corpus static, batch-rebuilt, or continuously changing, and what index-maintenance cost does that imply?

The index landscape

Exact / brute-force (flat). No approximation: the query is compared against every vector and the true nearest neighbours come back. Recall is 100% by definition, there are no parameters to tune, and there’s nothing to build beyond storing the vectors. In pgvector this is simply a query with no ANN index present; in OpenSearch it’s exact k-NNk-NNThe retrieval question itself: given a query vector, return the k closest vectors under the index’s distance metric – answered exactly by comparing against everything, or quickly by an ANN index. scoring. The cost is linear in the corpus, so query time grows with the number of vectors. Perfect for small or slowly-searched corpora, and the ground truth you measure every other index against, but it stops scaling exactly when you need it to.

HNSW (Hierarchical Navigable Small World). A graph index: vectors become nodes connected to their near neighbours across several layers, and a query greedily walks the graph from an entry point toward the closest matches. Queries are very fast and recall is high, which is why HNSW is the default high-quality choice in both OpenSearch and pgvector. The cost is memory and build time. The graph plus the vectors generally live in RAM, and building the graph is slower and heavier than clustering-based alternatives. Three parameters do the tuning: m, the number of neighbour links per node (higher means better recall and more memory); ef_construction, the size of the candidate list while building (higher means a better graph and a slower build); and ef_search, the size of the candidate list at query time (higher means better recall and slower queries). The first two are fixed at build time; ef_search you can turn per query.

IVF / IVFFlat (inverted file). A clustering index: a training pass runs k-means over a sample to partition the space into nlist cells, each vector is assigned to its nearest cell centroid, and a query only scans the vectors in the few cells closest to it. Build is faster and memory lower than HNSW, because there’s no graph to hold, just cell assignments and centroids. Recall is typically a touch lower for the same effort. The tuning dial is nprobe, the number of cells a query scans: nprobe of 1 is fast and low-recall, raising it searches more cells for better recall at more cost, and at nprobe equal to nlist you’re back to an exact scan. The catch is the training step: IVF must see a representative sample before it can be populated, and if the data distribution shifts a long way from the sample the cells stop being balanced and recall drifts.

Product quantisation (PQ), layered on top. Not an index on its own but a compression scheme, usually paired with IVF (as IVFPQ) or with HNSW. It splits each vector into sub-vectors and replaces each with the nearest entry from a small learned codebook, so a 1,024-dimension float vector shrinks to a short code. Memory drops dramatically, which is what makes billion-scale indexes affordable, and the price is recall, because the stored vectors are now approximations of the originals. On OpenSearch the faiss engine exposes PQ; it’s the lever you reach for when memory, not recall, is the binding constraint. A common pattern keeps full-precision vectors for a re-rankingRerankingA second pass that re-scores a wide set of retrieved candidates and keeps only the few most relevant, so the expensive model reads less. pass and uses the compressed index only to shortlist candidates.

Where the stores sit. OpenSearch Service’s k-NN plug-in offers HNSW and IVF through its faiss and (for HNSW) lucene and nmslib engines, with PQ available on faiss for compression. pgvector offers both HNSW and IVFFlat index types on a Postgres column, tuned with the same conceptual dials (m and ef_construction at build, ef_search per session for HNSW; lists at build and probes per session for IVFFlat). The vocabulary and defaults differ, but the trade-offs are the same three corners everywhere.

Side by side

Index	Recall	Query latency	Memory	Build cost	Key tuning dial	Best when
Exact / flat	✓ (100%)	✗ (grows with corpus)	Low-ish	✓ (none)	none	Small corpus, or ground truth
HNSW	✓ (high)	✓ (very fast)	✗ (high, RAM-resident)	✗ (slow, heavy)	ef_search, m	Fast high-recall at scale, memory available
IVF / IVFFlat	Slightly lower	✓ (fast)	✓ (lower than HNSW)	✓ (fast, needs training)	nprobe	Cheaper builds and footprint, tolerant of small recall loss
IVF + PQ	✗ (lowest, compressed)	✓ (fast)	✓ (lowest)	Needs training	nprobe, PQ codes	Memory is the binding constraint; very large corpora

The picks in depth

For the assistant at 12 million vectors, the exact scan has to go; the only question is what replaces it, and the honest answer starts with measurement, not a default. Build a ground-truth set first: take a few hundred real queries, run them through the existing exact search, and record the true top-k for each. That’s the yardstick. Every candidate index gets scored on recall against that set and on p95 query latency, on the real corpus, before anything ships.

HNSW is the strong default when the recall target is high and the memory budget can absorb it. Start with moderate parameters, an m around 16 and an ef_construction in the low hundreds, build the index, then sweep ef_search at query time and watch recall and latency move together: raising it climbs toward exact-search recall and costs milliseconds, and there’s usually a knee where recall is close to flat and further increases only cost latency. Set ef_search at that knee. The thing to check before committing is memory: at 12 million vectors of 1,024 dimensions the graph plus full-precision vectors want tens of gigabytes resident, so size the instance to hold it, because if the index spills out of RAM the latency win evaporates. m and ef_construction are baked in at build time, so if a sweep says you need a denser graph, that’s a rebuild.

IVF earns its place when the build and memory profile of HNSW is the problem. If the corpus is rebuilt on a schedule and HNSW’s slow graph construction is stretching the window, or the RAM to hold the graph is too expensive, IVFFlat clusters faster and holds less. Choose nlist in proportion to corpus size (a common rule of thumb is on the order of the square root of the vector count as a starting point, then measured), run the training pass on a representative sample, and tune nprobe the way you tuned ef_search: low for speed, higher for recall, measured against the ground truth. Watch for distribution drift; if the corpus grows in a way that diverges from the training sample, recall sags and it’s a retrain, not just a reindex.

PQ enters only when memory is the binding constraint rather than a line item. If holding full-precision vectors for the whole corpus is unaffordable, compress with IVFPQ on the faiss engine and accept that raw recall drops, then win it back with a re-ranking pass: let the compressed index shortlist a few hundred candidates cheaply, and re-score that shortlist against full-precision vectors to restore the top results. That two-stage shape is how large indexes stay both affordable and accurate. Reach for it when the numbers force you to; below that, the compression’s recall cost isn’t worth paying.

Whichever index lands, the store exposes the same conceptual dials whether it’s OpenSearch k-NN or pgvector, and the settings are not portable between corpora. An ef_search or nprobe that hit 98% recall on someone else’s data is a guess on yours until you’ve measured it. This is one component in a larger retrieval system, and the surrounding choices about where the vector store lives shape which of these indexes is even on the table.

A worked example: sizing the switch at 12 million vectors

Take the assistant’s numbers: 12 million chunks, 1,024-dimension embeddings, a per-query latency budget of about 50 ms for the search step, and a recall target of 95% against exact search. Exact scan currently runs over a second, so it’s out.

First, the ground truth. Sample 300 production queries, run exact k-NN for each, store the true top-10. That set never changes and every measurement below scores against it.

HNSW attempt. Build with m = 16, ef_construction = 200. Memory lands in the tens of gigabytes, so the instance is sized to keep the index resident. Sweep ef_search: at 40 the sample shows roughly 93% recall at around 8 ms; at 100, roughly 97% at around 18 ms; at 200, 98% at around 35 ms. The knee is near ef_search = 100, comfortably inside the latency budget and past the 95% target. If memory at this size is affordable, HNSW ships here and there’s no reason to give up the recall.

IVF alternative, run in parallel because the nightly rebuild window is tight. Train on a 1-million-vector sample, nlist = 4,096. Sweep nprobe: at 16, about 91% recall at around 6 ms; at 64, about 96% at around 14 ms; at 128, about 97% at around 24 ms. nprobe = 64 clears the target inside budget, the build is markedly faster than the HNSW graph, and the footprint is smaller. If the rebuild window or the memory bill was the pain, this is the trade worth taking, buying a faster, lighter index for a slightly higher nprobe and a training step to maintain.

Memory-pressed variant. If holding 12 million full-precision vectors is the line that breaks the budget, IVFPQ on faiss shrinks the footprint by an order of magnitude, at a raw recall in the high 80s. Add a re-rank: shortlist 200 candidates from the compressed index, re-score against full-precision vectors, and measured recall on the top-10 climbs back over 95%, with the full-precision vectors needed only for the shortlist rather than the whole corpus. More moving parts, far less memory, target still met. The point of running all three against one ground-truth set is that the pick stops being an opinion and becomes a number you can defend.

What’s worth remembering

1. Vector search is a three-way trade between recall, latency, and memory or cost; every index is a point inside that triangle and none of them wins all three.
2. Corpus scale decides whether you need an approximate index at all; exact search is fine at tens of thousands of vectors and becomes the bottleneck in the millions, because its cost grows with the corpus.
3. Exact / brute-force search gives guaranteed 100% recall and is the ground truth you measure every approximate index against, but its query time grows with the number of vectors.
4. HNSW is the fast, high-recall default, paid for in memory and a slow, heavy build; m and ef_construction are fixed at build time, and ef_search tunes recall against latency per query.
5. IVF / IVFFlat clusters the space and scans only the nearest cells, giving cheaper builds and a smaller footprint for slightly lower recall; nprobe is the dial, and it needs a training pass on a representative sample.
6. Product quantisation compresses the vectors to cut memory sharply at a further recall cost; pair it with IVF and a full-precision re-ranking pass, and reach for it only when memory is the binding constraint.
7. Recall is a tuned dial, not a fixed property, so “which index” and “how is it tuned” are one question; an index’s recall figure is meaningless without its parameters.
8. Build cost and update cost are separate from query cost; a constantly-changing corpus can make index maintenance dominate, and IVF’s training step drifts if the data moves away from its sample.
9. The stores expose the same trade-offs under different names: OpenSearch k-NN offers HNSW and IVF (with PQ on faiss), and pgvector offers HNSW and IVFFlat with the same conceptual dials.
10. No setting is portable; build a small ground-truth set from real queries and measure recall and latency on your own data before committing an index or its parameters.