Corpus size, update rate and memory budget narrow the index choice

Here is a real specification, of the kind that arrives as four lines in a planning document: 3.2 million chunks, 1024-dimension embeddings, 40 queries per second at peak, roughly 8% of documents edited or added every day, running on the same 32 GB instance as the application that serves the queries. Every one of those numbers constrains the index, and together they eliminate most of the options before anyone runs the harness from chapter 6, which sweeps each index across its query-time knob and records recall, p95 latency and peak memory at every setting. Doing that elimination first is the same discipline as sizing a database before choosing its indexes: capacity planning narrows the field, measurement picks the winner from what is left.

Four candidates are in scope, and they differ in what they build rather than in what they compute. Flat, or exact search, stores the vectors and compares the query against all of them; it builds nothing. IVFFlat — inverted file, flat storage — runs a clustering pass over the vectors to find a set of centroids, assigns each vector to the nearest one, and answers a query by scanning only the nprobe cells whose centroids are closest to it; nlist is how many cells there are. IVFPQ is the same cell structure with each stored vector replaced by a compressed code of a few dozen bytes, using product quantisation. HNSW builds a layered proximity graph in which every vector is a node linked to M of its neighbours, and answers a query by walking that graph greedily with a beam of width ef_search; efConstruction is the width of the same walk during the build. Two words recur below and are worth fixing now. Churn is the fraction of stored items that change in a period, and a tombstone is a flag that marks an entry dead while leaving it in place, so that the structure built around it stays intact.

Working the four constraints#

Memory first, because it is the constraint that fails hardest — a scan that is too slow returns a late answer, while an index that does not fit returns nothing and takes the application down with it. The vectors alone are 3.2M × 1024 × 4 = 13.1 GB. That arithmetic has no discretion in it: a float32 number is four bytes wide by definition, a vector is one such number per dimension, so a 1024-dimension vector occupies a little over four kilobytes and the corpus is that repeated once per chunk.

The graph on top of it is where a design decision enters. Each link an HNSW node holds is an integer identifying another node, four bytes wide, and each node holds a bounded number of them. An HNSW graph at M = 32 adds 64 layer-0 links per node at 4 bytes each, which is a quarter of a kilobyte, plus about 10% for the upper layers, so roughly 282 bytes per vector, or 0.90 GB. The upper layers cost so little because HNSW puts a geometrically thinning sample of the nodes into each successive layer, so layer one holds a small fraction of the population, layer two a small fraction of that, and the whole tower above layer zero adds a tenth rather than a second copy.

The number of links kept at layer zero is itself a parameter rather than a consequence of M. Implementations commonly cap it at twice M, which is where 64 comes from here, and a build that caps it at M instead pays half as much per node. That matters for a reader recomputing these figures on their own build: the per-node byte cost has to be read off the index that was actually constructed, since two indexes described as M = 32 can differ by a factor of two in graph memory.

Reading the two figures side by side gives a rule that is easy to state wrongly. Graph bytes per node depend only on how many links each node keeps; vector bytes per node depend only on the dimension. The vector count multiplies both terms equally, so it cancels out of the ratio between them — a corpus ten times larger has ten times the vectors and ten times the graph, in the same proportion. What changes the proportion is dimension. At 1024 dimensions the 0.90 GB graph is under a tenth of the 13.1 GB of vectors; at the 384 dimensions of the second specification below, a 5.9 GB graph against 64.5 GB of vectors is a visibly larger share, because the vector shrank and the links did not.

That ratio is what turns a memory budget into a recall budget, which is the step most capacity plans skip. The bytes available for the graph are whatever is left after the vectors, the application and the rebuild headroom have been subtracted. Graph bytes are the node count times four times the links per node, and the links per node are set by M. So the budget puts a ceiling on M — and M is the parameter that sets HNSW's recall ceiling, since a walk cannot follow an edge the build never created. A box that can only afford a small M has, by that fact alone, capped the recall the index can ever reach, and no query-time tuning recovers it.

Add the ID mapping and payload pointers and the index is around 14.3 GB resident, against a 32 GB box that also has to hold the application, its heap, the page cache and enough headroom that a traffic spike does not push the machine into swap. That fits, with something like 12 GB of margin — but it fits with the entire budget consumed by one index and no room for a second copy during a rebuild, which matters more than the steady-state figure. The margin is the figure to read rather than the total, because the index is larger than it: a rebuild produces a second copy while the first is still serving, and a second copy at 14.3 GB does not fit in 12 GB. On this box the question about rebuilds is where they happen rather than how long they take.

Query load next. Forty QPS with an exact scan over 13.1 GB is not close: a single scan reads 13.1 GB, so even at 80 GB/s of memory bandwidth using every core it takes about 165 ms, and 40 concurrent scans want 524 GB/s. That is more than six times the bandwidth the machine has, and there is no arrangement of threads that changes it, because the quantity being exceeded is the memory bus rather than the CPU. Exact search is out on this spec, which is the first hard elimination and it took one multiplication. The same figure read the other way gives the throughput ceiling directly: one scan every 165 ms is about six scans a second, which is the ~5 QPS the recommendation table below records as flat's limit, rounded down.

Update rate is where the choice between the two approximate families actually gets decided. Eight per cent of 3.2M is 256,000 chunks a day, which is about 3 per second averaged over 24 hours, and most of them are edits rather than new documents — an edit being a delete plus an insert as far as any vector index is concerned. That last equivalence is worth pausing on, because it is the reason churn costs anything at all. A vector is a function of the text it was computed from, so edited text produces a different point in the space; there is no operation that moves a stored point without removing it and adding it back. The step from 8% of documents to 8% of chunks assumes edited documents carry an average number of chunks, which holds unless the churn is concentrated on the longest documents in the collection.

HNSW handles the insert side comfortably; adding a vector costs roughly the same as a search at ef_search = efConstruction, so 1 to 3 ms. The two costs coincide because an insertion is a search: the algorithm finds the new node's neighbours by running the same greedy walk it would run for a query, at the wider beam efConstruction, and then links the new node to a selection of what that walk found. At the bottom of that one-to-three-millisecond band a day's 256,000 inserts come to about four minutes of CPU and at the top to a little over twelve, so 256,000 of them is around 10 minutes of single-threaded work spread over a day.

The delete side is the problem, because most implementations tombstone rather than remove. Removing a node properly would mean finding every edge that points into it and repairing each one, and a graph node stores its out-edges while nothing indexes its in-edges — so an exact removal costs a traversal of the graph to discover what pointed at the dead node. Marking is cheap and correct-looking, so implementations mark, and the graph's connectivity goes on depending on the dead nodes as routing elements. So after 90 days without a rebuild at this churn rate the graph is carrying a large population of nodes that are traversed, occupy memory, and are filtered out of results at the end.

IVF's inserts are cheaper still — one comparison against nlist centroids, then an append to a list — because filing a vector means picking one of a small set of cells rather than walking a structure. Its deletes can genuinely remove entries from a list, for the complementary reason: a posting list has no structural dependency on its members, so nothing routes through the entry you are deleting. What IVF pays instead is decay. Its centroids were fitted to the corpus as it stood at training time, and every later vector is filed under the nearest existing centroid whether or not that centroid describes it. When new material occupies a region the training snapshot did not cover, it lands in a cell chosen by default rather than by fit, and that cell is not the one a query about the same material will probe — so recall on new material falls with no error anywhere. Eight per cent daily churn means the corpus is substantially different within a month, though the quantity that actually moves the centroids is drift in what the corpus is about: 8% a day of edits to the same subjects disturbs them far less than 8% a day of genuinely new subject matter.

Both therefore need a rebuild cadence, and the two costs differ in kind rather than only in size. IVF retraining on this corpus is a k-means pass over a sample plus a reassignment of 3.2M vectors, which lands around 8 to 12 minutes. An HNSW rebuild at M = 32, efConstruction = 200 on 16 threads is 35 to 45 minutes, and it needs the memory for the new index while the old one is still serving, which on a 32 GB box means it has to happen somewhere else and be shipped in. On wall clock that is roughly a fourfold gap, and two things stop the wall clock from being the whole comparison. Only the HNSW figure is quoted with its thread count, so the two durations are not strictly comparable and the gap in CPU time could be much wider than the gap in minutes. And only the HNSW rebuild needs a machine that is not the serving box. A job that runs in place and a job that requires provisioning are different operational objects however close their durations are.

The candidates against the criteria#

The rows are more useful read as gaps than as levels, because a gap says which decision a row is capable of making. Take the latency row. Flat sits at 100–200 ms and the three indexes sit between 3 and 20 ms, which is more than an order of magnitude — but the three indexes sit almost on top of each other, since 6–20, 4–12 and 3–12 overlap across nearly their whole range. That row decides whether to index and cannot decide which index. The memory row behaves the same way with a different partition: flat, IVFFlat and HNSW are within a quarter of each other, while IVFPQ is twenty to fifty times smaller, so memory only ever answers the question "compressed or not". The build-cost row's largest gap is between "none" and any number at all, because that step introduces a rebuild cadence somebody has to own, and the gap from ~10 min to ~40 min is under fourfold by comparison.

Put those three readings together and the family choice falls out. Latency cannot separate the three indexes, and memory cannot separate three of the four. What is left to separate IVFFlat from HNSW is the training-pass row, the decay row, the delete row and the build-cost row — and every one of those is a question about how often the corpus changes. Churn decides between the approximate families because it is the only constraint whose row still discriminates once the other two have done their work.

There is a second pattern in the table worth naming, because it explains why the exact-search argument keeps recurring in this topic. Flat loses exactly three rows — memory, the p95 and the scale limit — and those three are exactly the rows that quote a measured quantity. In every one of the seven rows it wins or ties, its cell reads as an absence: no build cost, an append rather than a procedure, an exact removal rather than a mark, no training pass, no decay, no query-time knob, and a recall ceiling of 1.000, which is the absence of loss. What that licenses is a conclusion about what indexing costs: flat's advantages are objects it does not have, and an object you do not have cannot be adopted piecemeal. There is no setting on HNSW that yields "no rebuild policy". The decision to index is a decision to acquire a build step, a cadence, a parameter set and an unmeasured recall risk, and the only thing bought with them is the latency row.

Reading down the columns against the spec: flat is eliminated by throughput. IVFPQ is not needed, because 14.3 GB fits and quantisation would cost recall to buy memory that is not scarce. It becomes the right answer when the vectors alone exceed the box, which on this hardware would be somewhere past 7 million chunks at 1024 dimensions — 7 million vectors at a little over four kilobytes each is most of the 32 GB before any graph or application is counted. That leaves IVFFlat and HNSW, and the deciding factors are that HNSW is faster at equal recall on prose-like data, while IVFFlat is dramatically cheaper to rebuild and handles deletes without accumulating garbage. With 8% daily churn and a 32 GB box that cannot hold two copies, IVFFlat with a nightly retrain is the more operable choice even though HNSW wins the chapter 6 table. If the churn were 0.5% a day, HNSW would win outright.

Diagram

The diagram has three decision diamonds and the section above worked three constraints, and the correspondence is exact: throughput decides index or no index, memory decides compressed or uncompressed, churn decides between the two approximate families. No constraint appears twice and none of the three is idle. That is what makes the recommendation reproducible rather than a matter of taste — a family that is not in the table can be placed by asking only which of the three answers it changes, and if it changes none of them it belongs wherever its nearest neighbour in the table already sits.

The diamonds are also in a different order from the prose above, which worked memory first, and both orders are right for their own question. Memory comes first when the question is whether a chosen index fits, because that is the failure that takes the process down. Throughput comes first when the question is which index to choose, because a yes at that diamond ends the exercise — there is nothing further to decide once a scan is fast enough.

The diagram is a filter, not an answer. It gets you to one or two candidates, and the harness from chapter 6 then measures them on your data — which is where a decision guide like HNSW vs IVFFlat: How to Choose the Right Vector Index leaves off as well, and correctly, because the last step is not generalisable.

The small-corpus case, restated as an operational argument#

Chapter 1 made the case for exact search at 200k chunks and 768 dimensions arithmetically: 614 MB, about 8 ms per scan, one query per second against a budget of a thousand milliseconds. The same case looks different through this chapter's criteria and lands in the same place, and it lands there by way of the absence pattern in the table. There is no build step, so there is no rebuild window and no cadence to own. Deletes are exact, so nothing accumulates. There is no training pass, so a corpus that grows into new subject matter needs no retraining. There are no parameters, so there is nothing for a future colleague to set wrong and nothing to sweep after every corpus change. And recall is 1.0, so the index is permanently removed from the suspect list in every retrieval investigation. The strongest response to a proposal for HNSW at that scale is that a 600 MB scan is fast enough with perfect recall and nothing to tune — and the operational reading is that the index would add five parameters, a build step, a rebuild policy and a permanent unmeasured recall risk, to save 7 ms on a request that spends seconds in a language model.

The version of this argument that goes wrong is applying it to a corpus with a trajectory. If the 200k chunks are on their way to 5M within a year, the arithmetic that says "no index" today says "index" in eight months, and the design question becomes when to introduce one rather than whether. That is a legitimate reason to build the abstraction now — a retrieval interface that can swap implementations — and it is not a reason to run HNSW today, because the index you would choose at 5M is the one you would choose after measuring at 5M, not the one that looked reasonable at 200k.

Parameters, sharding and filtered search#

Choosing an index family does not choose its parameters, and the differences within a family are larger than people expect. The chapter 4 table showed the same HNSW build at M = 16 and M = 48 differing by eight points of recall ceiling, which is a bigger gap than the one between IVFFlat and HNSW at their respective best operating points. Getting the family right and the parameters wrong produces an index that looks correct on paper and loses a tenth of every result set. That gap is also the currency the memory ceiling above is spent in: capping M to fit a box is spending recall, and the table in chapter 4 says how many points.

The analysis also assumes a single machine and a single index. Sharding changes the memory constraint entirely, since four boxes holding 800k vectors each can run exact search where one box holding 3.2M cannot, at the cost of a fan-out and a merge on every query. Replicas change the QPS constraint the same way. Filtered search changes everything, because a query restricted to one tenant's 4,000 documents out of 3.2M is a different problem — pre-filtering makes an exact scan over 4,000 vectors trivially fast, while post-filtering an HNSW result set can return nothing at all when the filter is selective, and the interaction between filters and graph traversal is its own subject.

Managed services do not remove the decision either. pgvector asks you to choose between ivfflat and hnsw at CREATE INDEX time with lists, m and ef_construction as build parameters and ivfflat.probes and hnsw.ef_search as session settings, which is exactly the split from chapter 4 wearing SQL syntax. Qdrant, Milvus and Weaviate expose HNSW's m and ef under their own names. A fully managed service that exposes nothing has made the choice for you, at a point on the frontier you did not select and cannot see, which is a reasonable trade only if you have measured what it costs.

Three constraints, three eliminations, and a shortlist of one or two before any benchmark runs. The arithmetic behind each is small enough to do in a planning meeting: multiply count by dimension by four for the vectors, divide that by the machine's bandwidth for the scan time, and multiply the churn rate by the corpus for the daily delete volume. What those numbers rule out, they rule out permanently, and what they leave standing is what the sweep in chapter 6 is for.

Getting the family, the parameters and the operating point right still leaves an index that can go wrong in service. A corpus that churns accumulates tombstones, a growing corpus outgrows the nprobe that was right at half the size, and a pipeline that skips a normalisation step feeds the index vectors it cannot rank correctly. Each of those produces the same user-visible symptom — wrong results, no errors, normal latency — and the next chapter is about telling them apart.