Scalable Distributed Vector Search via Accuracy Preserving Index Construction
Yuming Xu, Qianxi Zhang, Qi Chen, Baotong Lu, Menghao Li, Philip Adams, Mingqin Li, Zengzhong Li, Jing Liu, Cheng Li, Fan Yang, University of Science, Technology of China, Microsoft Research, Microsoft · 2025
Read Scalable Distributed Vector Search via Accuracy Preserving Index Construction by Yuming Xu, Qianxi Zhang, Qi Chen, Baotong Lu, Menghao Li, Philip Adams, Mingqin Li, Zengzhong Li, Jing Liu, Cheng Li, Fan Yang, University of Science, Technology of China, Microsoft Research, Microsoft (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-17264.txt.
Introduction
Yuming Xu and ten co-authors present SPIRE, an index that can search billions of vectors spread across many machines. Vector search finds the stored items closest to a query, and it powers tools from image search to chatbots. At huge scale, systems must trade off accuracy, delay, and speed, and older designs struggle to hold all three.
SPIRE makes two key choices. It picks a balanced size for splitting data across machines, so reads do not blow up in cost. It then builds the index level by level in a way that guards accuracy as it grows. In tests with up to 8 billion vectors on 46 nodes, SPIRE ran up to 9.64 times faster than leading systems.
Catalog record
| CREATOR | Yuming Xu, Qianxi Zhang, Qi Chen, Baotong Lu, Menghao Li, Philip Adams, Mingqin Li, Zengzhong Li, Jing Liu, Cheng Li, Fan Yang, University of Science, Technology of China, Microsoft Research, Microsoft |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-17264
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scalable Distributed Vector Search via Accuracy Preserving Index Construction Yuming Xu, Qianxi Zhang, Qi Chen, Baotong Lu, Menghao Li, Philip Adams, Mingqin Li, Zengzhong Li, Jing Liu, Cheng Li, Fan Yang, University of Science, Technology of China, Microsoft Research, Microsoft Abstract Scaling Approximate Nearest Neighbor Search (ANNS) to billions of vectors requires distributed indexes that balance accuracy, latency, and throughput. Yet existing index designs struggle with this tradeoff. This paper presents SPire , a scalable vector index based on two design decisions. First, it identifies a balanced partition granularity that avoids read-cost explosion. Second, it introduces an accuracy-preserving recursive construction that builds a multi-level index with predictable search cost and stable accuracy. In experiments with up to 8 billion vectors across 46 nodes, SPire achieves high scalability and up to 9.64× higher throughput than state-of-the-art systems. 1 Introduction Modern systems increasingly rely on high-dimensional vector indexes for Approximate Nearest Neighbor Search (ANNS), an important AI workload [ 15 , 12 , 28 , 6 , 36 , 27 , 55 , 26 , 15 , 42 , 5 , 21 , 47 , 61 ] . A vector index usually connects nearby vectors to form a graph, and queries traverse the graph to locate approximate neighbors. Because ANNS trades exactness for efficiency, maintaining high query accuracy is critical (e.g., recalling >90% of neighbors). Consequently, a high-quality vector index typically preserves sufficiently dense graph connectivity to ensure broad coverage. Scaling ANNS to billions of vectors requires distributing the index across server nodes and utilizing on-disk storage, which requires index sharding. As high accuracy demands dense index graph connectivity, the sharding makes cross-node links unavoidable. Unfortunately, these links introduce substantially higher latency than local traversal [ 1 , 16 ] . To reduce cross-node links, a common approach is to cluster neighboring vectors into partitions, elect partition centroids, and connect nearby centroids. A query then traverses toward relevant centroids before locating approximate neighbors within their associated partitions. Several ANNS systems stack such clustering hierarchically to further control cross-node links, so as to improve scalability with low latency [ 53 , 55 , 37 , 45 , 58 ] . However, vector clustering introduces fidelity loss. A centroid may be a poor representative of its partition, especially for vectors near partition boundaries. To compensate for this fidelity loss, queries often have to probe additional partitions to recover accuracy, which increases vector reads (with extra CPU cycles and disk IOs) and thus reduces overall system throughput. This tension creates a fundamental tradeoff between query latency (dominated by cross-node communication) and system throughput (dominated by vector reads), given an accuracy target. Despite extensive prior work on vector indexes, this tradeoff in scalable hierarchical ANNS indexes remains underexplored and poorly understood. As a result, existing distributed ANNS systems often suffer inflated latency or constrained throughput (§ 2 ). To address these limitations, this paper presents SPire , a hierarchical vector index system designed for high scalability. SPire distinguishes itself through the following two design decisions. First, given a target query accuracy, SPire identifies a balanced partition granularity that avoids significant throughput penalties. We observe that, under a fixed accuracy, the average vector read cost of a query, proportional to throughput penalties, remains largely insensitive to increases in partition granularity when each partition contains only a few vectors. But the read cost grows sharply once the granularity exceeds this range. This is because the read cost is inversely proportional to the partition density, a metric we introduce to quantify the partition granularity (§ 3.2 ). SPire therefore selects the granularity just before this inflection point. Second, because this balanced granularity may still be too fine-grained and induce excessive cross-node communication, SPire employs an accuracy-preserving recursive index construction strategy that builds a multi-level hierarchical index. Cross-node traversal occurs only across levels. Each level in the hierarchy is treated as a single-level vector index, allowing SPire to decompose the end-to-end accuracy preservation into a sequence of level-by-level index construction tasks. The first level is built using a conventional approach while adopting the balanced partition granularity to satisfy the global accuracy target. The second level applies the same procedure to the centroids of level-1 partitions, but adjusts construction to preserve the end-to-end accuracy rather than optimizing for the level-2 accuracy alone. The above process repeats until the top-level index fits within the memory budget of a single server. This recursive, level-by-level construction provides a fixed search cost per level, resulting in stable and highly predictable end-to-end search behavior across scales and significantly simplifying system design and implementation. Guided by these two design decisions, we implemented SPire in 6,000 lines of C++ code. Extensive experiments show that SPire is the first system to achieve high throughput scalability for high-dimensional vector search. It outperforms state-of-the-art systems by up to 9.64× in peak throughput in production-scale deployments (up to 8 billion vectors across 46 nodes), while maintaining lower average and tail latency at all scales. The system saturates SSD (I/O-bound) while using only a fraction of network (<30%) and CPU (<40%) capacity, demonstrating strong headroom for further scaling. Operationally, SPire is simple to deploy. Only the top-level index is kept in memory, while lower-level indexes as well as vectors are offloaded to SSDs. This design keeps the compute tier stateless: the in-memory index is replicated across nodes and can be reconstructed from the SSDs in case of catastrophic failures, enabling elastic scaling and simplified fault recovery. We plan to release the SPire codebase. 2 Background 2.1 Vector Search Systems Vector search, which performs similarity search over high-dimensional spaces, has become a core system component powering latency-sensitive applications such as web search [ 21 ] , recommendation [ 47 , 61 ] , e-commerce [ 27 , 55 , 26 ] , and retrieval-augmented generation (RAG) [ 15 , 42 , 5 , 20 , 39 ] . Due to the curse of dimensionality, exact nearest neighbor search is often expensive [ 7 ] . Modern systems instead rely on vector indexes for Approximate Nearest Neighbor Search (ANNS) [ 13 , 30 , 22 , 46 , 53 , 55 , 52 , 34 , 44 , 56 , 57 ] . These systems trade exact search results for high efficiency: they must deliver high recalls (often above 0.9 [ 15 , 4 , 62 ] ) of an ANNS, respond within millisecond-level SLOs (e.g., 10 ~ 20 ms) [ 27 , 59 , 62 ] , and sustain high query loads that routinely reach thousands of QPS [ 55 , 51 , 1 ] . Among various types of ANNS indexes, graph-based indices, such as HNSW [ 30 ] , dominate single-node deployments due to their efficient search performance and high accuracy. These indices connect nearby vectors to form a densely connected proximity graph where queries use best-first search to locate top- K neighbors approximately. 2.2 Scaling Vector Search Systems Inflated latency due to index sharding. When scaling to billions of vectors [ 12 , 14 ] , index sharding becomes necessary. A naïve approach is to shard the popular graph-based vector index into multiple partitions. However, graph-based indexes like HNSW rely on dense connectivity to ensure query accuracy. Sharding a densely connected