Track B · Document 10 · Embeddings and index
What to do when the index no longer fits in memory, the compression trick that puts the error where the score cannot see it, and how to choose among all five.
Everything in document 09 assumed the index fits in memory. At a hundred million vectors it does not, and the way it fails is instructive.
333 GB of RAM is a machine that exists and a bill that stings. Double the corpus and it is 665 GB, which is a machine that exists and a bill nobody signs. That is the wall, and everything in this document is a response to it.
Document 09 established that a graph walk defeats the prefetcher, and that no memory ordering fixes it — a node belongs to many neighbourhoods at once, so it cannot be contiguous with all of them. Most treatments present that as bad news. DiskANN treats it as an opportunity.
Six milliseconds of dead time destroys most latency budgets. So DiskANN cannot simply relocate HNSW to disk — it has to attack the cost per hop and the number of hops separately. Two ideas, one for each.
Worth doing the arithmetic explicitly, because it is a favourite interview question and the numbers settle it.
The numbers are damning, and that is why the question gets asked. A candidate who says “you would just put the index on SSD” has not done this arithmetic; a candidate who splits it into these two problems has.
A hop has two distinct needs, and separating them is the key to the whole design. To pick a direction you need the neighbours’ vectors. To continue you need the chosen node’s neighbour list. Those two needs can be served from two different places.
The principle, worth memorising as a sentence: errors during navigation are self-correcting; errors in the final ranking are not. Pick the second-best neighbour and you still moved toward the answer, and the next hop corrects. Get the final ordering wrong and a user sees the wrong document.
The compressed vectors are lossy, which would be alarming if they decided the answer. They do not — they decide the direction.
During the walk the question is “which of these thirty-two is closer?”, and an approximate answer is fine: pick the second-best neighbour and you have still moved toward the answer, and the next hop corrects. At the end the question is “which are my top ten, in order?”, that goes to the user, and an error there is a wrong document that nothing downstream fixes.
After idea one, a query is sixty hops × one disk read × 100 µs = six milliseconds of pure waiting. Still too slow. So reduce the hops — which means throwing away the layer hierarchy, because each layer is more disk reads.
HNSW gets its long jumps from sparse upper layers. Vamana gets them from a pruning rule that puts long and short edges in the same neighbour list.
Same goal as HNSW — coarse first, fine last — reached differently. HNSW separates the two scales by layer; Vamana mixes both scales into one neighbour list. The parameter controlling how aggressively it prunes is alpha: above 1 it deliberately keeps some edges that would otherwise go, producing longer-range links and shorter paths, at the cost of a denser graph and slower builds. Typical values sit around 1.2.
| Parameter | What it is | Typical |
|---|---|---|
| R | The maximum neighbour-list length — DiskANN’s M | Usually larger than HNSW’s M, because the list is read from disk in one page anyway — you are paying for the read regardless, so you may as well fill the page |
| L | The search candidate list — DiskANN’s efSearch | A query-time knob, same tradeoff as efSearch |
| alpha | How aggressively the pruning rule discards same-direction candidates | ~1.2. Above 1 keeps edges that would otherwise go, giving longer-range links and shorter paths, at the cost of a denser graph and slower builds |
Worth stating cleanly, because interviewers use the names loosely. Vamana is the graph construction algorithm — the edge selection and pruning rule. DiskANN is the whole system: a Vamana graph, plus compressed vectors in RAM, plus full vectors and the graph laid out on SSD, plus a full-precision re-rank at the end.
You could run Vamana entirely in RAM with no disk at all and it would work fine — a flat graph competing with HNSW on roughly equal terms. But the pairing is not accidental: the flat graph is what makes disk viable, because ten hops of disk reads is affordable and sixty is not.
An SSD does not read a byte, it reads a block — typically 4 KB. So reading one integer and reading 4 KB cost the same. DiskANN exploits that by storing each node’s neighbour list and its full-precision vector together in the same page: when the walk commits to a node it needs the neighbour list, and if that node ends up in the top candidates it also needs the full vector for the re-rank. Co-locating them means the re-rank data is often already fetched.
Beyond the page, nodes are ordered on disk so that graph-adjacent nodes tend to land near each other. That does not eliminate random access — nothing can — but it increases the chance that a fetch pulls in something useful nearby. This layout is computed during the build, over the whole dataset, which is exactly why incremental inserts degrade it.
The trade in one line: roughly an order of magnitude less RAM, for a few times the latency. Whether that is a good deal is a business question, not a technical one.
Move the corpus slider to 200M and watch the left-hand number go from “a machine that exists” to “a machine nobody signs off”. That crossing is where this document stops being theory.
The disk ordering and the pruning were computed over the whole dataset at build time.
New vectors are appended wherever there is room, so locality decays and hop counts rise. Performance degrades gradually and nothing errors.
DiskANN is at its best on corpora that are rebuilt in bulk rather than edited continuously.
Which is a genuine architectural constraint and belongs in the decision, not a footnote.
Local NVMe, not network-attached storage.
On network storage the per-hop read goes from ~100 µs to milliseconds and the whole design collapses.
Vamana is a graph build, so it inherits the problem: constructing edges requires searching the graph.
It parallelises somewhat better than HNSW, but it is hours at a hundred million, not minutes.
Postgres users sometimes ask whether they can have this. The honest answer is that pgvector’s HNSW implementation assumes the index is in shared buffers or the OS page cache, and its performance falls off in the same way any RAM-resident graph does once it does not fit. There are DiskANN-style extensions in the ecosystem, and the general point holds: if your corpus has outgrown memory, the question is whether your engine has a disk-native index at all, and for most general-purpose databases the answer today is no.
DiskANN asked “where should the vectors live?”. ScaNN asks a different question: given that we are going to compress, can we compress more cleverly?
The starting point is ordinary product quantisation, which is covered fully in document 12. In one paragraph: cut each vector into chunks, match each chunk against a learned 256-entry catalogue, and store the winning entry number. A 768-dimension float32 vector becomes 96 bytes of pointers — not values, pointers — and all of it happens at build time.
Anisotropic means “not the same in all directions”. Standard quantisation is isotropic: error in any direction counts equally. ScaNN’s weights the parallel component more heavily — formally loss = η·(parallel error)² + (perpendicular error)², where η = 1 is ordinary quantisation. Being able to unpack that one word plainly is worth a lot.
This is the entire justification for the technique in one picture. Standard quantisation treats those two placements as equally good, because it minimises plain squared distance. ScaNN does not, because it is optimising for what the score will actually do.
| Ordinary product quantisation | ScaNN’s anisotropic version | |
|---|---|---|
| What it minimises | Plain squared distance — error in every direction counts the same | A weighted loss that penalises error along the vector’s own direction more heavily |
| Code size | 96 bytes | 96 bytes — identical |
| Query path | Unchanged | Unchanged |
| Build cost | A k-means over chunks | The same, with a different objective |
| Recall at the same code size | The baseline | Better — the error was placed where the score cannot see it |
That is the whole contribution, and it is worth appreciating how narrow it is: same catalogue size, same bytes, same query path, different selection rule. ScaNN is better framed as an optimisation of quantisation than as a fifth index type — which is also the honest answer when someone asks “should we use ScaNN?”
Each one is a response to the previous one’s limitation. Reading them in that order is how the field actually developed, and it is how to present them.
Nothing here is a strict upgrade of the thing before it. Each fixes a specific limitation and introduces a new one, which is why all five are still in production somewhere.
| Flat | IVF | HNSW | DiskANN | ScaNN | |
|---|---|---|---|---|---|
| Family | none | partition | graph | graph | partition |
| Recall | exact, 1.00 | tunable, ~0.94 at nprobe 16 | tunable, ~0.95+ | ~0.95+ | ~0.95+ at a given code size |
| Latency, 1M | ~61 ms | a few ms | ~1 ms | 3–5 ms | a few ms |
| Index overhead | none | ~0.1% | ~8.5%, and ~34% once quantised | ~10 GB per 100M in RAM | low |
| Must fit in RAM? | the vectors, yes | the vectors, yes | vectors and graph, yes | only the codes | the codes |
| Build | none | fast — one k-means pass | slow | slow | a k-means with a different objective |
| Inserts | trivial | drift | graceful | degrade the layout | drift |
| Deletes | trivial | rebuild the list | tombstone only | tombstone only | rebuild the list |
| Filtering | perfect — filter first, scan the rest | poor | better | better | poor |
| Knobs | none | nlist, nprobe | M, efConstruction, efSearch | R, L, alpha | leaves, chunk size, reorder depth |
The decision is never made in the abstract. Four briefs, and the reasoning that settles each.
| The brief | The answer | Why |
|---|---|---|
| 80,000 chunks, internal wiki, 20 users | Flat | A few milliseconds, exact, zero parameters, nothing to rebuild and nothing to tune. Any index here is complexity you will maintain and never benefit from |
| 10M chunks, p95 under 50 ms, filters on four fields, continuous edits | HNSW | It fits in RAM comfortably, filtering interacts far better than with IVF, and inserts are graceful. The graph overhead is a few gigabytes, which is affordable |
| 500M chunks, rebuilt nightly from a warehouse, 200 ms budget | IVF, probably quantised | Bulk rebuild suits it, the index overhead is a rounding error at this scale, the budget is generous, and quantisation helps sequential scanning more than it helps random access |
| 200M chunks, p95 under 50 ms, RAM budget of one machine | DiskANN | HNSW would need ~665 GB of RAM. DiskANN needs ~20 GB plus an NVMe drive and delivers 3 to 5 ms against a 50 ms budget. There is no contest — you were not short of time, you were short of money |
Worth knowing so you are not surprised by a follow-up. HNSW is the overwhelming default — it is what pgvector, Qdrant, Weaviate, Elasticsearch and most managed services reach for, because it wins the common case. IVF variants dominate at very large scale, particularly in FAISS-based systems where the corpus is rebuilt in bulk. DiskANN appears where RAM economics force it, most visibly in Microsoft’s own products and increasingly as an option in managed services. ScaNN shows up inside Google infrastructure and as a library, and its ideas propagate into other engines’ quantisation rather than as a product you pick.
| Symptom | Most likely cause | What to check first |
|---|---|---|
| Latency collapsed when the corpus crossed a size threshold | The index no longer fits in memory, so a graph walk is now doing disk seeks per hop | Resident memory against index size. This is a cliff, not a slope |
| DiskANN latency degraded gradually over months | Inserts have eroded the disk layout, so hop counts and page locality are both worse | When the index was last rebuilt. This is expected behaviour, not a fault |
| DiskANN is far slower than the benchmark suggested | Network-attached storage rather than local NVMe | The per-read latency. At milliseconds rather than ~100 µs the whole design stops working |
| Quantisation saved less memory than expected on a graph index | Compression shrinks the vectors and not the edges | The graph size separately. Its share of the total rises after quantisation |
| Recall dropped after switching to a quantised index and rescoring is enabled | Too few candidates re-ranked, or the codes are too short | The rescore depth first — it is a query-time knob and the cheapest thing to move |
| ScaNN gave no improvement over ordinary product quantisation | The corpus or metric does not suit it — the benefit assumes inner-product-style scoring where the along-query error is what matters | Whether vectors are normalised and what the metric is. And whether the comparison held code size constant |
| The build takes a whole day | Any graph index at scale — each insertion is a search | Whether the build is parallelised, and whether a partition-based index would suit the write pattern better |
ArchitectWhy can you not just put an HNSW index on an SSD?
Because of the read count. Standing at a node you need one read for its neighbour list and thirty-two more for the neighbours’ vectors, just to decide which way to step. That is thirty-three reads per hop, sixty hops per query, so about two thousand disk reads at roughly a hundred microseconds each — two hundred milliseconds. Unusable.
And it splits into two separate problems. Thirty-two of the thirty-three reads are for scoring, and even if you solved that perfectly, sixty structure reads is still six milliseconds. DiskANN’s two ideas map exactly onto those: compressed copies in RAM kill the scoring reads, and a flat graph reduces the hops.
ArchitectExplain DiskANN.
Two ideas on top of a graph. First, keep a product-quantised copy of every vector in RAM — about 96 bytes each, so ten gigabytes at a hundred million — and serve all the scoring from those. That takes a hop from thirty-three disk reads to one, because the only thing you still need from disk is the chosen node’s neighbour list.
Second, throw away the layer hierarchy and build one flat graph whose neighbour lists deliberately contain both long and short edges, so there are ten hops instead of sixty. The pruning rule that produces that is Vamana. Then the final step fetches about a hundred full-precision vectors from SSD and re-scores exactly — so the compression guides the route and never decides the answer, which is why recall matches HNSW.
ArchitectIs it safe to navigate on lossy vectors?
Yes, and the reason is worth stating as a principle: errors during navigation are self-correcting; errors in the final ranking are not. During the walk the question is “which of these neighbours is closer”, and picking the second-best still moves you toward the answer — the next hop corrects. At the end the question is “what are the top ten, in order”, that goes to a user, and nothing downstream fixes it.
So the design puts the approximation entirely in the first job and full precision entirely in the second. That separation is the interesting part of DiskANN, more than the disk itself.
ArchitectWhat is ScaNN doing that ordinary quantisation is not?
Choosing where to put the error. Quantisation replaces your vector with a catalogue entry, so there is always a gap — it can be placed but not removed. Ordinary quantisation minimises plain squared distance, so it treats every direction as equally bad.
But a dot product measures alignment with the query, so only the component of the gap pointing along the query changes the score; a sideways component is nearly invisible. ScaNN weights the training objective to be very accurate along the vector’s own direction and sloppy sideways. Same code size, same query path, better recall.
The objection to have ready is that you do not know the query at build time — and the answer is that a document’s own direction is the best available proxy, because the queries that will retrieve it point roughly toward it.
ArchitectTwo hundred million vectors, fifty-millisecond budget. What do you build?
DiskANN, and I would show the arithmetic. Two hundred million 768-dimension float32 vectors is about 614 GB, plus roughly 51 GB of graph, so HNSW wants 665 GB of RAM. DiskANN wants about 20 GB of RAM plus local NVMe, and delivers three to five milliseconds.
Against a fifty-millisecond budget there is no contest: the speed HNSW would buy me is worth nothing, because I was not short of time, I was short of money. The two things I would confirm are that the storage is local NVMe rather than network-attached, and that the corpus is rebuilt in bulk rather than edited continuously — because incremental inserts erode the disk layout.
ArchitectWalk me through all five and when you would use each.
Flat is the absence of an index: exact, no parameters, linear cost. Right under about a hundred thousand vectors, for small entitled sets, and always as the ground truth that every recall figure is measured against.
IVF prunes by region — partition once, open the nearest few buckets. Cheap index overhead, fast bulk builds, poor with filters. HNSW prunes by path — walk a graph, scoring far fewer vectors for the same recall. The default for interactive search, at the cost of about 8 percent index overhead and no real delete story.
DiskANN is HNSW’s answer to running out of RAM: compressed copies in memory, everything else on SSD, a flat graph so there are fewer reads. And ScaNN is not really a fifth structure — it is a better quantisation objective, and its ideas turn up inside other engines rather than as a thing you deploy.
Eng managerThe team wants to move from HNSW to DiskANN to cut the RAM bill. What do you ask?
Three things, and the first two can kill it. What is the actual latency budget, and how much of it are we using now — because DiskANN is a few times slower and if we are already close to the limit this trades a cost problem for an SLO problem. Is the storage local NVMe, because on network storage the design collapses and the benchmark will not tell you that.
And what is the write pattern? DiskANN’s disk layout is computed over the whole dataset at build time, so continuous inserts erode it and performance decays gradually. If we edit constantly, we are signing up for a rebuild cadence, and that belongs in the plan rather than being discovered in month four.
Eng managerHow would you run this decision as a bake-off rather than an argument?
Fix the recall target first, because otherwise the comparison is meaningless — anything can be fast if it is allowed to be wrong. Then measure latency and memory at that recall on our corpus and our query mix, including the filters, because filtering is where the families differ most and it is usually left out of vendor benchmarks.
I would also measure build time and rebuild time explicitly, because those decide the operational cost for the next three years and they never appear in the headline number. And I would insist on a flat baseline over a sample, because without it we have no recall figure at all — only a comparison of two approximations to each other.
Is DiskANN just HNSW on a disk?
No, and the arithmetic in section 3 is why: HNSW moved verbatim to disk is about two hundred milliseconds a query. DiskANN changes two things — scoring is served from compressed copies in RAM so a hop costs one read instead of thirty-three, and the graph is flat with mixed-length edges so there are roughly ten hops instead of sixty. Without both changes it does not work.
Can I run Vamana in memory, without the disk part?
Yes, and it works fine — a flat graph competing with HNSW on roughly equal terms. Some engines offer exactly that. The pairing with disk is not accidental though: the flat graph exists because sixty disk reads is unaffordable and ten is not, so in RAM the motivation largely disappears and the comparison with HNSW becomes an empirical question.
Why is R usually larger than HNSW’s M?
Because the neighbour list is read from disk in one 4 KB page regardless of how full it is. You are paying for the page, so you may as well use it. In RAM there is no such quantum — a bigger M costs proportionally more memory — which is why the two systems land on different values for what is nominally the same parameter.
Does DiskANN need an NVMe drive specifically?
It needs something with a per-read latency near a hundred microseconds and enough IOPS for your concurrency. Local NVMe delivers that; a spinning disk does not come close; and network-attached storage typically lands in the milliseconds, which multiplies the ten-hop walk into something worse than the RAM index it replaced. Check the storage before believing any DiskANN benchmark.
Is ScaNN a competitor to HNSW?
Not really, and it is worth saying so rather than treating all five as alternatives. ScaNN is a partition-based system whose distinctive contribution is a better quantisation objective. Its ideas compose with other structures rather than replacing them — you can quantise a graph index anisotropically too. The honest framing is: ScaNN is a better way to compress, packaged with an index around it.
Can I combine quantisation with any of these?
Yes, everything except flat, and that is why vendor names run together — IVF-PQ, HNSW-SQ and so on. Quantisation is not an index type; it is orthogonal to the structure. The interaction worth remembering is that it helps partition-based indexes more than graph ones, because sequential scanning is bandwidth-bound and benefits fully from smaller vectors, while random access is latency-bound and benefits far less.
What if my corpus is 30 million vectors — right in the gap?
Then do the RAM arithmetic before anything else, because it usually decides for you. Thirty million at 768 dimensions is about 92 GB of vectors plus 8 GB of graph, which fits on a large machine and is uncomfortable on three medium ones. If it fits, use HNSW. If it nearly fits, reduce the dimension or the precision first — that is a cheaper lever than changing index type, and document 06 shows how much it buys.
How do I benchmark these fairly?
Fix the recall target, then measure everything else at that recall. A latency comparison at unspecified recall is meaningless, and it is the single most common flaw in published benchmarks. Beyond that: use your own corpus and query mix, include the filters, measure build and rebuild time as well as query time, and produce a flat baseline over a sample so the recall figures mean something.
“At a hundred million vectors HNSW wants about 333 gigabytes of RAM, and quantisation does not rescue it because the graph does not shrink. DiskANN’s move is to notice that a graph walk is random access anyway, and random access is what an SSD does natively — so relocate the penalty to cheaper hardware.
You cannot do that naively: HNSW on disk is thirty-three reads a hop, sixty hops, about two hundred milliseconds. So two changes. Compressed copies of every vector in RAM — ten gigabytes at a hundred million — so all the scoring is served from memory and a hop costs one read. And a flat Vamana graph whose pruning rule mixes long and short edges into one neighbour list, so it is ten hops rather than sixty. Then a full-precision re-rank of the top hundred at the end, which is why recall matches HNSW: the approximation guides the route and never decides the answer.
ScaNN attacks the same memory problem from the other side. Quantisation always leaves a gap between the real vector and the stored code, and you cannot remove it — but you can place it. Only the component pointing along the query changes a dot-product score, so train the catalogue to be accurate along the vector’s own direction and sloppy sideways. Same bytes, same query path, better recall.”
| Thread from this document | Resolved in |
|---|---|
| Flat, IVF and HNSW in full, and why the graph is random access | 09 · Flat, IVF and HNSW |
| R, L, alpha, leaves and reorder depth, derived from a budget | 11 · Parameters and the tuning runbook |
| Product quantisation, catalogues, and rescoring in full | 12 · Quantisation and capacity |
| Sharding a graph index, and why it is awkward | 13 · Sharding and replication |
| Why filtering separates the two families | 14 · Filtered search and multi-tenancy |
| Fixing the recall target before any benchmark | 16 · Evaluation and observability |