Document 10 · Quick learn One read, not thirty-three · Ten hops, not sixty · Place the error sideways

When RAMruns out

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.

“Errors during navigation are self-correcting. Errors in the final ranking are not.”

665 → 20 GB

of RAM, at 200 million vectors

33 → 1 reads

per hop, once scoring comes from RAM

60 → 10 hops

once the graph goes flat

96 bytes

same code size, better recall

Where HNSW hits a walland why you cannot just move it to an SSD

Worked100M × 768-d fp32 = 307 GB of vectors + 26 GB of graph = 333 GB of RAM · 200M = ~665 GBthe arithmetic that starts the conversation

One hop, standing at a node

You need one read for its neighbour list — and 32 more for the neighbours’ vectors, just to decide which way to step.

33 reads per hop

Sixty hops per query

~2,000 disk reads at roughly 100 µs each.

~200 ms. Unusable

And it splits in two

32 of the 33 reads are for scoring. Even solved perfectly, 60 structure reads is still 6 ms.

DiskANN’s two ideas map exactly onto those

Compressed copies in RAM kill the scoring reads. A flat graph reduces the hops.

The reframe

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.

Idea onecompressed vectors in RAM, everything else on SSD

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 can be served from two different places.

Two tiers

Compressed copies of every vector in RAM — ~10 GB at a hundred million. Full vectors and the graph on SSD.

Scoring from RAM

The 32 neighbours’ vectors, answered with zero disk reads.

Traversal from disk

One read of one 4 KB page for the chosen node’s neighbour list.

So a hop costs one disk read instead of thirty-three

The final step

Fetch ~100 full-precision vectors and re-score them exactly.

Why approximate scoring is safe during the walk

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. Errors during navigation are self-correcting; errors in the final ranking are not

Idea twoa flatter graph, because each layer is more disk reads

After idea one, a query is sixty hops × one disk read × 100 µs = six milliseconds of pure waiting. Still too slow. 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.

1 · Gather

A large pool of candidates for C’s neighbour list, by searching the graph.

2 · Keep the closest

Then repeat until the list is full or the candidates run out.

3 · Prune by direction

Discard any candidate lying in roughly the same direction as something already kept.

Formally: X goes if X is closer to a kept Y than it is to C

What survives

Spread across directions — some near, some far. Ten hops instead of sixty.

The maximum neighbour-list length — DiskANN’s M.

Usually larger than HNSW’s M, because the list is read from disk in one 4 KB page anyway — you are paying for the page, so use it

The search candidate list — DiskANN’s efSearch.

A query-time knob, same tradeoff

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

Vamana is the algorithm; DiskANN is the system

Worth stating cleanly, because interviewers use the names loosely. Vamana is the graph construction — edge selection and the pruning rule. DiskANN is the whole system: a Vamana graph, plus compressed vectors in RAM, plus full vectors and the graph on SSD, plus a full-precision re-rank.

You could run Vamana entirely in RAM and it would work fine. 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

ScaNNthe same problem, attacked differently

DiskANN asked where should the vectors live? ScaNN asks: given that we are going to compress, can we compress more cleverly?

The gap is unavoidable

You replace the real vector with a catalogue entry, and it is not the same vector.

The gap can only be placed, not removed

The grocery-bill version

Being wrong about the number of apples changes the bill. Being wrong about the bag colour does not.

The geometry

The part of the gap pointing along the query changes the score. The part pointing sideways barely does.

Because a dot product measures alignment

So train the catalogue accordingly

Accurate along the vector’s own direction, sloppy sideways.

Same code size, same query path, different selection rule

Ordinary product quantisation

Minimises plain squared distance.

Error in every direction counts the same
Code size: 96 bytes
Query path: unchanged
Build: a k-means over chunks

Same size.
Same query path.
Different objective.

ScaNN’s anisotropic version

A weighted loss that penalises error along the vector’s own direction more heavily.

Code size: 96 bytes — identical
Query path: unchanged
Build: the same, with a different objective
Better recall at the same code size — the error was placed where the score cannot see it

The objection to have ready

“You do not know the query at build time.” And the answer: a document’s own direction is the best available proxy, because the queries that will retrieve it point roughly toward it.

All five, on one pageeach a response to the previous one’s limitation

Flat

The absence of an index.

Recall: exact, 1.00 · 1M latency: ~61 ms · overhead: none
Filtering: perfect — filter first, scan the rest
Knobs: none

IVF

Prune by region.

Recall: ~0.94 at nprobe 16 · latency: a few ms · overhead: ~0.1%
Inserts: drift · deletes: rebuild the list
Filtering: poor · knobs: nlist, nprobe

HNSW

Prune by path.

Recall: ~0.95+ · latency: ~1 ms · overhead: ~8.5%, ~34% once quantised
Inserts: graceful · deletes: tombstone only
Knobs: M, efConstruction, efSearch

DiskANN

HNSW’s answer to running out of RAM.

Recall: ~0.95+ · latency: 3–5 ms · RAM: ~10 GB per 100M — only the codes
Inserts: degrade the layout
Knobs: R, L, alpha

ScaNN

A better quantisation objective, packaged with an index.

Recall: ~0.95+ at a given code size · latency: a few ms
Filtering: poor · knobs: leaves, chunk size, reorder depth

The four questions that settle it every time

How many vectors, and how big? This gives the RAM number, and the RAM number usually eliminates two options immediately.
What is the latency budget? Not “as fast as possible” — a number. If you are spending 5 ms of a 50 ms budget, speed is worth nothing to you.
What is the write pattern? Continuous edits favour a graph; bulk rebuilds favour a partition.
Is there a filter on every query? If yes, partition-based indexes are structurally disadvantaged.

Four briefs, four answersthe decision is never made in the abstract

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 without benefit

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

500M chunks

Rebuilt nightly from a warehouse, 200 ms budget.

IVF, probably quantised. Bulk rebuild suits it, the overhead is a rounding error at this scale, the budget is generous

200M chunks

p95 under 50 ms, RAM budget of one machine.

DiskANN. HNSW would need ~665 GB. DiskANN needs ~20 GB plus NVMe and delivers 3–5 ms against a 50 ms budget

The characteristic DiskANN failure, and how to avoid buying it

The disk layout is computed over the whole dataset at build time, so continuous inserts erode it and performance decays gradually rather than breaking. And on network-attached storage the design collapses — per-read latency lands in the milliseconds and multiplies the ten-hop walk into something worse than the RAM index it replaced.

Check the storage before believing any DiskANN benchmark, and put the rebuild cadence in the plan rather than discovering it in month four

Answer it out loudthe ninety-second version, then six questions

“Everything in document 09 assumed the index fits in memory. At two hundred million vectors HNSW wants about 665 GB of RAM, and you cannot just move it to an SSD: a hop needs one read for the neighbour list and thirty-two more for the neighbours’ vectors, sixty hops a query, which is two thousand reads and about two hundred milliseconds. DiskANN fixes both halves. Product-quantised copies of every vector live in RAM — ten gigabytes at a hundred million — so scoring costs no disk reads and a hop is one read. And the graph is flat with mixed-length edges, so there are ten hops rather than sixty. Then a final full-precision re-rank of about a hundred candidates, which is why the compression guides the route and never decides the answer.”

Six questions, and the spine of each answer

Architect

Why can you not just put HNSW on an SSD?

Because of the read count. One read for the neighbour list, thirty-two for the neighbours’ vectors
33 reads per hop × 60 hops × ~100 µs = ~200 ms. Unusable
And it splits into two problems: 32 of the 33 are scoring, and even solved perfectly, 60 structure reads is still 6 ms

DiskANN’s two ideas map exactly onto those: compressed copies in RAM kill the scoring reads, and a flat graph reduces the hops.

Architect

Explain DiskANN.

Two ideas on top of a graph. Keep a PQ copy of every vector in RAM — ~96 bytes each, ten gigabytes at 100M
Serve all the scoring from those: a hop goes from 33 disk reads to one
Throw away the layer hierarchy; build one flat graph with both long and short edges — ten hops instead of sixty
That pruning rule is Vamana

Then fetch ~100 full-precision vectors from SSD and re-score exactly — so compression guides the route and never decides the answer, which is why recall matches HNSW.

Architect

Is 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: “which of these is closer?” — picking second-best still moves you toward the answer, and the next hop corrects
At the end: “what are the top ten, in order?” — that goes to a user

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.

Architect

What is ScaNN doing that ordinary quantisation is not?

Choosing where to put the error. Quantisation always leaves a gap — it can be placed but not removed
Ordinary PQ minimises plain squared distance, treating every direction as equally bad
But a dot product measures alignment: only the component pointing along the query changes the score
ScaNN weights the objective to be accurate along the vector’s own direction and sloppy sideways

Same code size, same query path, better recall. And the objection to have ready: you do not know the query at build time — but the document’s own direction is the best available proxy.

Architect

200 million vectors, 50 ms budget. What do you build?

DiskANN — and I would show the arithmetic
200M × 768-d fp32 is ~614 GB, plus ~51 GB of graph: HNSW wants 665 GB of RAM
DiskANN wants ~20 GB plus local NVMe, and delivers 3–5 ms

Against a 50 ms budget there is no contest: the speed HNSW would buy is worth nothing, because I was not short of time, I was short of money. Confirm two things: local NVMe, not network storage; and bulk rebuilds, not continuous edits.

Eng manager

How would you run this as a bake-off rather than an argument?

Fix the recall target first, or the comparison is meaningless — anything can be fast if allowed to be wrong
Then measure latency and memory at that recall, on our corpus and query mix — including the filters
Measure build and rebuild time explicitly, because those decide operational cost for three years and never appear in the headline

And 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.

Fast answersthe eight that come up most

QIs DiskANN just HNSW on a disk?

No. HNSW moved verbatim to disk is about two hundred milliseconds a query. DiskANN changes two things — scoring served from compressed copies in RAM so a hop costs one read instead of thirty-three, and a flat graph with mixed-length edges so there are ~10 hops instead of 60. Without both changes it does not work.

QCan I run Vamana in memory, without the disk part?

Yes, and it works fine — a flat graph competing with HNSW on roughly equal terms. But the pairing is not accidental: the flat graph exists because sixty disk reads is unaffordable and ten is not. In RAM the motivation largely disappears.

QWhy 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.

QDoes DiskANN need an NVMe drive specifically?

It needs 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 milliseconds, which multiplies the ten-hop walk into something worse than the RAM index it replaced.

QIs 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, and its ideas compose with other structures rather than replacing them.

QCan I combine quantisation with any of these?

Yes, everything except flat — which is why vendor names run together (IVF-PQ, HNSW-SQ). Quantisation is not an index type; it is orthogonal to the structure. It helps partition-based indexes more than graph ones, because sequential scanning is bandwidth-bound and random access is latency-bound.

QWhat if my corpus is 30 million vectors — right in the gap?

Do the RAM arithmetic first, because it usually decides for you. 30M at 768-d is ~92 GB of vectors plus ~8 GB of graph — fits on a large machine, uncomfortable on three medium ones. If it nearly fits, reduce the dimension or the precision first: a cheaper lever than changing index type.

QHow 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 most common flaw in published benchmarks. Use your own corpus and query mix, include the filters, and measure build and rebuild time as well as query time.

The interesting part of DiskANN is not the disk — it is where the approximation is allowed to live. Errors during navigation are self-correcting: pick the second-best neighbour and the next hop fixes it. Errors in the final ranking are not: that goes to a user and nothing downstream catches it. So the design puts lossy compressed vectors entirely in the first job and full precision entirely in the second — and ScaNN is the same instinct applied to the compression itself, placing the error sideways where a dot product cannot see it.

HNSW · 665 GB of RAM at 200M

DiskANN · ~20 GB

Where this goes next

The graph walk this is trying to survive 09 · Index IR, L and alpha derived from a budget 11 · TuningProduct quantisation properly, and rescoring 12 · CapacityWhether to shard instead of going to disk 13 · ShardingWhy partition indexes struggle with filters 14 · FilteringFixing the recall target before any comparison 16 · Proof

Questions to ask them

How many vectors, at what dimension — what is the RAM number?

What is the latency budget, as a number, and how much are you using now?

Is the storage local NVMe, or network-attached?

Is the corpus rebuilt in bulk or edited continuously?

Is there a filter on every query?

Was the last benchmark run at a fixed recall target?