Approximate nearest-neighbor systems often start with an in-memory graph such as HNSW or DiskANN’s Vamana graph. Those structures work well when the vector corpus and navigation metadata fit comfortably in RAM. At billion scale, however, raw vector payloads dominate the cost model. A billion 768-dimensional float vectors require multiple tebibytes before adding graph edges, metadata, or replication. Keeping every vector in memory can become more expensive than the compute doing the search.
SPANN, introduced by Microsoft Research at NeurIPS 2021, is a memory-disk hybrid ANN design. It follows the inverted-index pattern: keep a compact centroid index in memory, store large posting lists on SSD, and read only the few lists that are likely to contain the nearest neighbors for a query. The paper reports that SPANN reached 90% recall@1 and recall@10 at around one millisecond using 32 GB of memory on billion-scale datasets, and was twice as fast as DiskANN at the same 90% recall point under the same memory budget.
The important mechanism is not simply “put vectors on disk.” SPANN makes disk access viable by combining balanced hierarchical clustering, boundary replication through cluster closure, and query-aware pruning of posting-list reads. The design gives engineers a reusable template for ANN systems where DRAM is reserved for routing and SSDs hold the full-resolution vector population.
SPANN partitions the vector corpus into many posting lists. Each posting list has a centroid, and only those centroids plus routing metadata need to stay in memory. A query first searches this coarse layer to find nearby centroids, then loads the corresponding disk-resident lists for exact or high-fidelity scoring against the original vectors.
A posting list contains the vectors assigned to one partition. This mirrors lexical search: an inverted index maps a term to documents, while SPANN maps a vector-space region to vectors. The practical constraint is that each list must be small and balanced enough to load with a bounded number of SSD reads. Large or skewed lists create high tail latency because one query can suddenly fetch far more data than another.
Hard clustering is dangerous for nearest-neighbor search because true neighbors often lie near partition boundaries. If a query reads only the closest centroid’s list, it can miss vectors that are geometrically close but assigned to an adjacent partition. SPANN addresses this by augmenting posting lists with vectors from each cluster’s closure, effectively replicating boundary vectors into nearby lists so recall does not depend on perfect one-list assignment.
SPANN’s central tradeoff is to keep only a small, navigable summary of the vector space in memory. The full vector payload remains on SSD, but the system structures partitions so a high-recall query touches only a small number of predictable disk pages.
SPANN starts by selecting and organizing head vectors through hierarchical balanced clustering. The goal is not only to minimize clustering error, but also to keep posting-list lengths close to a target size. This differs from ordinary k-means, which can produce dense clusters with very long lists and sparse clusters with short lists. Balanced clustering makes the disk cost predictable.
After the centroids are chosen, the builder assigns vectors to posting lists and adds closure replicas for vectors near cluster boundaries. The resulting index has two tiers: an in-memory head index over centroids and an SSD index containing the posting lists.
def build_spann(vectors, target_list_size, replica_count):
centroids = balanced_hierarchical_clustering(
vectors,
target_cluster_size=target_list_size,
)
posting_lists = {centroid.id: [] for centroid in centroids}
for vector_id, vector in vectors:
primary = nearest_centroid(vector, centroids)
posting_lists[primary.id].append((vector_id, vector))
# Replicate boundary vectors into nearby lists to improve recall.
closure = nearest_centroids(vector, centroids, top_k=replica_count + 1)
for centroid in closure:
if centroid.id != primary.id and is_boundary_candidate(vector, centroid):
posting_lists[centroid.id].append((vector_id, vector))
head_index = build_memory_index([c.vector for c in centroids])
ssd_layout = write_bounded_posting_lists(posting_lists)
return head_index, ssd_layoutAt query time, SPANN searches the in-memory centroid index and obtains a ranked list of candidate posting lists. Rather than blindly reading a fixed number of lists, it applies a query-aware pruning rule so lists that are unlikely to improve the result set can be skipped. The remaining lists are loaded from SSD and scanned to produce final nearest-neighbor results.
def search_spann(query, head_index, ssd_layout, top_k, max_lists):
centroid_hits = head_index.search(query, top_k=max_lists)
selected_lists = []
best_centroid_distance = centroid_hits[0].distance
for hit in centroid_hits:
if should_read_posting_list(
centroid_distance=hit.distance,
best_distance=best_centroid_distance,
query=query,
):
selected_lists.append(hit.centroid_id)
candidates = []
for list_id in selected_lists:
for vector_id, vector in ssd_layout.read_posting_list(list_id):
candidates.append((distance(query, vector), vector_id))
return sorted(candidates)[:top_k]The serving path is built around the fact that SSD reads are slower and less predictable than memory lookups. Good implementations issue reads asynchronously, cap the number of posting pages per list, keep warm routing structures in memory, and track how many bytes each query reads. The ANN algorithm and the storage layout are inseparable: recall is controlled by which partitions are read, while latency is controlled by how many pages those reads require.
Search engines, recommendation systems, and large RAG corpora often need high recall over vectors that are too large for a fully in-memory index. SPANN fits workloads where SSD latency is acceptable if the system can keep memory usage bounded and predictable.
A managed vector database may serve many tenants with uneven corpus sizes. Keeping only centroids in memory allows a service to host larger corpora per machine, while posting-list controls limit the worst-case query cost. This can be more economical than provisioning enough memory for every tenant’s full vectors and graph edges.
SPANN-style retrieval is useful as a first-stage candidate generator. The system can retrieve hundreds or thousands of candidate IDs cheaply from disk, then pass them to a reranker, lexical filter, metadata policy layer, or neural cross-encoder. The separation between coarse routing and fine ranking makes it easy to compose with larger search pipelines.
Treat head selection as a capacity-planning problem. More centroids reduce posting-list length and improve routing precision, but increase memory usage. Fewer centroids reduce memory, but inflate each disk read. Pick the centroid ratio using measured recall, tail latency, and memory constraints rather than copying a default.
A disk-resident ANN index should have an explicit page budget. The SPTAG implementation exposes controls such as posting page limits, replica counts, and internal result counts because these are the knobs that translate algorithmic choices into actual I/O. Without a page budget, balanced clustering errors become production latency spikes.
Replication improves recall but increases index size and write amplification. Measure how many true neighbors are recovered by closure replicas and how much additional data is read per query. The right replica count is dataset-dependent: highly clustered embeddings need less overlap, while noisy or high-dimensional corpora may need more.
class SpannTuning:
def __init__(self, centroid_ratio, replica_count, posting_page_limit, search_list_limit):
self.centroid_ratio = centroid_ratio
self.replica_count = replica_count
self.posting_page_limit = posting_page_limit
self.search_list_limit = search_list_limit
def estimate_query_io(self, avg_page_size_bytes):
return self.search_list_limit * self.posting_page_limit * avg_page_size_bytes
def explain(self):
return {
"memory_pressure": "increases with centroid_ratio",
"index_size": "increases with replica_count",
"tail_latency": "bounded by posting_page_limit and search_list_limit",
"recall": "usually improves with replica_count and search_list_limit",
}