One billion vectors must live mostly on cheap storage with a 200 ms budget. Decide between SPANN style and DiskANN style designs.
SPANN wins on object storage: centroids in RAM, then a few large parallel posting-list fetches. DiskANN's chained pointer hops die on tens of milliseconds per round trip.
Imagine your library is mostly in a warehouse three towns over, and a single trip to the warehouse takes thirty minutes regardless of how many books you grab. If a book sends you to fetch the next one in the warehouse, then the next, then the next, you spend the whole afternoon driving. That is what DiskANN does on object storage. SPANN keeps a single map of which shelf to visit and, on each query, drives to a couple of shelves and brings back whole boxes at once. Fewer trips, more parallel, far less wall-clock time. The medium being slow per request is what makes the difference, not the total weight of books.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
At a billion vectors, the design space splits cleanly along a single axis: where the data lives and how much it costs per request. RAM is fastest but expensive enough that a billion 768-d float32 vectors at roughly 3 KB each costs many machines just to hold. Local NVMe is two orders of magnitude cheaper per byte and only marginally slower per request. Object storage is another order of magnitude cheaper but pays tens of milliseconds per GET regardless of object size.
SPANN and DiskANN are both designed for the lower-RAM tiers. They take radically different bets on what kind of I/O the storage layer can sustain, and those bets do not transfer between NVMe and object storage. Picking the wrong one for the medium is the kind of architectural mistake that does not show up in benchmarks until production load hits.
This deep dive lays out the I/O model of each design, does the per-query cost math against both storage tiers, and walks through which 2026 production engines use which approach and why.
What each design actually does at query time
DiskANN builds a Vamana graph, a navigable small-world structure with carefully chosen long-range edges. A query starts at an entry point, looks at the entry point's neighbors, picks the closest to the query, hops there, and repeats. Each hop reads a node's neighbor list (a few hundred ids plus the node's compressed vector) from storage. After 50 to 100 hops, the candidate set has converged on the true nearest neighbors.
The key property of this traversal is that it is dependent and serial. Hop k+1's id is determined by what hop k returned, so the I/O cannot be batched ahead of time. Each hop is one storage round trip.
SPANN partitions all vectors into clusters via k-means and stores each cluster as a posting list. The centroids (a few hundred thousand vectors for a billion-vector corpus) live in RAM. A query computes distances to all centroids, picks the nearest r (typically 3-10), then fetches the posting lists for those r clusters and rescans the candidates in them.
The key property of this traversal is that it is shallow and parallel. The r fetches are independent and can run concurrently; each fetch is large (a few MB per posting list) and amortizes its round-trip cost across many vectors.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
Real products, models, and research that use this idea.
- Turbopuffer's object-storage-native vector engine implements a SPANN-style posting-list layout because per-request S3 latency makes graph traversal nonviable
- Pinecone serverless keeps centroids and metadata in a hot tier while posting lists live on S3, the same separation SPANN proposed
What an interviewer would ask next. Try answering before peeking at the approach.
QHow would you adapt DiskANN to object storage without rewriting the algorithm?
Walk through a hot-subgraph cache (RAM holds the entry points and dense neighborhoods), batching across queries, and locality-aware node packing so neighbor lists arrive in one S3 GET. Be explicit about the recall-vs-cost tradeoff when the cache misses on cold queries.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Choosing DiskANN because it reads fewer total bytes. On object storage, latency per request dominates throughput, so a chain of small dependent reads is much slower than a few large parallel fetches.
60 second bullets to scan on the way to the call.
How SPANN partitions vectors into posting lists routed by RAM centroids
How DiskANN's Vamana graph walk creates a chain of dependent reads
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.