What problem does DiskANN solve that HNSW does not, and when do you reach for it?

MCQ·Hard·4.0 · 0·~1 min·Asked atPinecone Zilliz·Relevant atMicrosoft

Attempt it

**HNSW** is fast because the entire graph and all the vectors live in RAM. That speed is the constraint: at a billion vectors, the RAM footprint hits hundreds of gigabytes or terabytes, which is no longer feasible on a single machine. **DiskANN** (Microsoft Research) was designed to break the RAM ceiling. The graph index lives on solid state storage instead of RAM. Only a small in memory summary (a Product Quantized version of each vector) stays in RAM for cheap distance estimation. Query time traversal walks the on disk graph, fetching nodes in sequential chunks that align with SSD page sizes. The tradeoff is straightforward. SSD bytes are about 100x cheaper than RAM bytes, but each random access is ~100x slower. DiskANN amortizes this by making queries touch a small constant number of SSD pages (~10-50 per query) and by using PQ in RAM to filter candidates before the SSD reads. **Reach for DiskANN when:** - The corpus times dimension exceeds your RAM budget. - The workload can tolerate 5-15ms per query latency (rather than HNSW's sub millisecond). - Examples: internal enterprise search, batch ingestion pipelines, backend recommendation surfaces. The other answer options describe completely different systems (GPU ANN, learned distance metrics) and are wrong.

**DiskANN solves the RAM-budget problem at billion-vector scale.** HNSW requires the index to be RAM resident; DiskANN keeps the graph on SSD with a small in RAM PQ summary. Mechanically, DiskANN is the Vamana graph algorithm from Microsoft Research. The graph is laid out so that traversal touches sequentially-accessible SSD pages rather than random pages; sequential SSD reads are an order of magnitude faster than random ones. Each query walks the graph, fetches a small number of pages (~10-50), computes exact distances on the fetched candidates, and returns top-K. PQ compressed vectors stay in RAM as a coarse filter to avoid spurious SSD reads. **The cost versus latency tradeoff.** A billion 1024-dim vectors at float32 is 4TB raw. As HNSW that is 4TB of RAM (infeasible on a single machine, very expensive at any scale). As DiskANN it is 4TB of SSD plus ~32GB of RAM for PQ summaries, feasible on a single workstation. The cost: per query latency rises from sub millisecond to 5-15ms because of the SSD page reads. **The right workloads:** - Batch retrieval or backfill pipelines where 10ms per query is invisible. - Internal enterprise search where the SLA is 100-500ms end to end. - Recommendation backends where a recall pass over a billion items happens once per session. - Embedding-store backups or long-tail content where the active subset is small. **The wrong workloads:** - Latency-critical RAG where p99 must stay under 50ms end to end. - High-QPS public facing search where every millisecond compounds. - Workloads that fit comfortably in RAM (under ~100M-vectors-at-1024-dim): use HNSW. The distractor options (GPU ANN, learned metric, BQ-on-HNSW) describe unrelated systems and are wrong on the vendor-pitch level.

Quick reference

TL;DR

DiskANN stores the graph on SSD with a small in RAM PQ summary. Use it when corpus × dim outgrows RAM and the workload tolerates 5-15ms per query.

Memory aid

Easy to grasp

Think of DiskANN like a library that lives in a warehouse instead of on your desk. HNSW is fast because the whole map and every book sit on your desk (RAM), but desks are tiny and expensive, and a billion books will never fit. DiskANN is a clever redesign that lays the map out on a fast warehouse shelf (the SSD) so that grabbing a book pulls a whole nearby section at once (SSDs love sequential reads). A tiny index card on your desk tells the search which warehouse aisle to walk to, so each lookup only fetches a few shelves. The result: you can hold a billion items on one fancy laptop's SSD instead of renting a rack of RAM-stuffed servers, at the cost of each lookup taking 5-15 milliseconds instead of being instant.

Key concepts

DiskANN

Detailed answer & concept explanation

~5 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.

Quick scan · 2–4 min

Everything important, quickly.

6 min: the Vamana graph and SSD layout, the PQ-in RAM filter, the cost versus latency tradeoff, and the right and wrong workloads for billion-scale DiskANN.

Side-by-side

Property	HNSW	DiskANN
Primary storage tier	RAM	SSD
In-RAM footprint per vector	4 × d + graph edges	PQ code (~64-128 bytes)
Typical query latency	Sub-millisecond	5-15 ms
Sweet-spot scale	1M-100M vectors	100M-10B vectors
Write cost	Cheap incremental	Expensive (rebuild flavored)
Cost per billion vectors	Very high (RAM)	Moderate (SSD + small RAM)

Real-world examples

Real products, models, and research that use this idea.

Microsoft Bing uses DiskANN internally for enterprise document search at hundreds of millions of documents.
Milvus ships DiskANN as an opt in index type for billion-scale workloads where RAM is not feasible.
Vespa exposes a disk resident ANN mode for large scale ranking workloads with relaxed latency SLOs.
Turbopuffer's object storage-backed architecture extends the DiskANN insight further, with S3 as the cold tier and per query latency in the 50-200ms range.
Azure AI Search ships an exhaustive or approximate hybrid that uses DiskANN style on disk graphs for large indexes.

Interviewer follow-ups

What an interviewer would ask next. Try answering before peeking at the approach.

QHow does the PQ summary in DiskANN avoid spurious SSD reads during graph traversal?

QWhy does Turbopuffer's S3-backed design accept much higher latency than DiskANN's SSD-backed design?

QHow would you migrate a 500M-vector HNSW index to DiskANN without downtime?

Don't say this

Red flags and common mistakes that signal junior thinking. Click to expand.

Most common mistake

Treating DiskANN as a GPU variant or a recall improvement over HNSW. It is neither; it trades latency for storage cost by moving the index to SSD.

60-second cheat sheet

The night-before-the-interview bullets. Scan these on the way to the call.

References

Primary sources. Skim if you want the original framing.