Decoupling Vector Data and Index Storage for Space Efficiency Yuanming Ren1 , Juncheng Zhang1 , Yanjing Ren1 , Rui Yang2 , Di Wu2 , and Patrick P. C. Lee1 1 The Chinese University of Hong Kong 2 Bytedance
arXiv:2604.09173v1 [cs.DB] 10 Apr 2026
Abstract Managing large-scale vector datasets with disk-based approximate nearest neighbor search (ANNS) systems faces critical efficiency challenges stemming from the co-location of vector data and auxiliary index metadata. Our analysis of state-of-the-art ANNS systems reveals that such co-location incurs substantial storage overhead, generates excessive reads during search queries, and causes severe write amplification during updates. We present DecoupleVS, a decoupled vector storage management framework that enables specialized optimizations for vector data and auxiliary index metadata. DecoupleVS incorporates various design techniques for effective compression, data layouts, search queries, and updates, so as to significantly reduce storage space, while maintaining high search and update performance and high search accuracy. Evaluation on real-world public and proprietary billion-scale datasets shows that DecoupleVS reduces storage space by up to 58.7%, while delivering competitive or improved search query and update performance, compared to state-of-the-art monolithic disk-based ANNS systems.
1
Introduction
The rapid growth of artificial intelligence (AI) across various domains (e.g., web search [17], recommendation systems [8], and retrieval-augmented generation in large language models [36]) has spurred demands for managing multimodal data (e.g., texts, images, and audio/video files) [22], represented in the form of high-dimensional vectors, with scalable vector storage. To enable efficient similarity search in highdimensional spaces, approximate nearest neighbor search (ANNS) is often used in practice by returning an approximate top-K result set, rather than exact neighbors, over a vector dataset, with a favorable performance-accuracy trade-off. A vector dataset typically comprises two main components: (i) high-dimensional vectors (the data component) and (ii) an auxiliary index (the metadata component) that keeps metadata for vectors to allow efficient search. As vector datasets scale to hundreds of trillions of high-dimensional vectors [20], traditional in-memory ANNS solutions (e.g., HNSW [31], IVFADC [25]) become impractical due to prohibitive memory requirements [55]. Several studies have explored disk-based ANNS approaches (e.g., [6, 24, 44, 52]) by storing vector datasets on solid-state drives (SSDs) or other persistent storage media. For example, DiskANN [24] organizes vectors using a graph-based auxiliary index and employs best-first similarity search; SPANN [6] partitions a vector dataset into
clusters and maintains an inverted file index that maps cluster centroids to member vectors, so as to enable efficient search through selective cluster access. Such disk-based ANNS systems support billion-scale deployment, making them appealing for modern AI applications. A common design principle in existing disk-based ANNS systems is co-locating vector data and auxiliary index metadata in storage. This simplifies implementation and amortizes I/O costs in accessing vectors and relevant metadata. However, this design choice imposes three critical limitations from a storage perspective (see §2.2 for details): • Space overhead: Vector datasets require substantial auxiliary metadata (e.g., neighbor lists in a graph-based index) to support efficient search. The metadata storage overhead often exceeds the size of vector data (i.e., full-precision vectors). As NVMe SSD prices keep escalating due to surging AI-driven demands [23], space efficiency has become a primary requirement for cost-effective deployment. • Read amplification. A single similarity search query requires retrieving tens to hundreds of candidate vectors from disk for distance computation and ranking. This read amplification can easily saturate the I/O queue, leading to high I/O wait times and reduced query throughput. • Write amplification. While updates can be buffered in memory and flushed to disk in batches to consolidate I/O operations [19, 42], this approach typically requires rewriting large portions of the auxiliary index on disk, leading to substantial disk bandwidth and high write amplification. Our key insight is that vector data and auxiliary index metadata exhibit fundamentally distinct characteristics in data semantics and access patterns (§2.3), implying that they can be decoupled and optimized with specialized strategies to improve the overall space efficiency and I/O performance for disk-based ANNS systems. However, designing an efficient decoupled storage framework for disk-based ANNS systems introduces non-trivial challenges. First, space reduction at the persistent layer should not compromise data integrity. General-purpose lossless compression techniques (e.g., LZ4 [7], Huffman [28]) are straightforward approaches to improve space efficiency without information loss, yet they do not capture the semantic structures of vector data and auxiliary index metadata to optimize compression savings. Second, compression and decompression not only incur computational overhead, but also involve variable-size compressed data that requires additional metadata management.
a common vector space, and constructs an auxiliary index over these vectors for efficient similarity search. Given a search query, the ANNS system generates a query vector and uses the auxiliary index to locate the most similar vectors according to a distance metric (e.g., Euclidean distance, inner product, or cosine similarity). It finally returns the top-K items corresponding to the nearest vectors. Each vector typically comprises hundreds of dimensions represented by numerical data types, such as UINT8, INT8, or FP32 [34]. The embedding model is trained to capture the semantic features of the input data, with each dimension encoding a specific feature [39]. To maintain search accuracy, vectors are often normalized to prevent large-value dimensions from dominating distance calculations. Vector dimensionality can reach tens of thousands for rich representation of textual data (e.g., in large language models) [2]. The auxiliary index allows efficient search queries without scanning the entire dataset. It can be structured as graph-based [24,31], cluster-based [6,25], or tree-based [33]. For example, a graph-based index represents each vector as a vertex and connects similar vertices by edges. Given a search query, the ANNS system begins at a designated entry point, traverses the graph by following edges, and computes distances between the query vector and the vectors at visited nodes to identify the nearest neighbors as candidates. If the search cannot find closer vectors than the current candidate set, it returns the top-K candidate vectors as the result set. In-memory ANNS systems (e.g., HNSW [31], IVFADC [25], and RUMMY [55]) store both vectors and auxiliary indexes in DRAM for fast access, but incur substantial memory overhead. For example, RUMMY [55] requires terabytes of memory to manage billion-scale datasets. Such high memory requirements hinder scalability, thereby motivating the use of disk-based ANNS systems.
[0.12, 0.34, 0.75, .. ] [0.16, 0.28, 0.67, ..] Unstructured datasets
Embedding model
High-dimensional vectors Indexing
Page 0
Embedding
Page 1 Doc
Vertex 0 Vector data
Vertex 1 Neighbor list
Disk data layout
1
Query 5
Store everything on SSDs
2 0
4
3 Graph-based auxiliary index
Figure 1: Basic workflow of disk-based ANNS system, using a graph-based auxiliary index as an example.
Third, decoupling destroys the sequential I/O locality from the co-location strategy, so retrieving vector data and auxiliary index metadata requires separate I/O operations and increases access overhead. Finally, decoupling complicates consistency maintenance between vector data and auxiliary index metadata during updates. We propose DecoupleVS, a decoupled vector data and auxiliary index storage management framework designed for disk-based ANNS systems. DecoupleVS aims to achieve high space savings, while maintaining high search and update performance as well as high search accuracy. Our contributions are summarized as follows: • We characterize the storage and I/O inefficiencies inherent to the co-located storage design of existing disk-based ANNS systems, motivating the need for decoupled vector storage management. • We design DecoupleVS, which incorporates four key techniques for effective decoupled vector storage management: (i) tailored lossless compression algorithms that exploit the distinct characteristics of both vector and index components, (ii) hierarchical storage layouts that minimize access overhead for variable-sized compressed data, (iii) latency-aware search mechanisms that mitigate I/O locality loss, and (iv) batched update mechanisms that reduce write amplification while preserving consistency. • We conduct extensive experiments on real-world public and proprietary datasets. Compared to state-of-the-art diskbased ANNS solutions (DiskANN [24] and PipeANN [18]), DecoupleVS saves up to 58.7% of storage space, achieves up to 2.18× search throughput gain, and preserves high update efficiency. We will release the source code of DecoupleVS in the final version of the paper.
2
Background
2.1
Basics of ANNS
2.2
Disk-based ANNS and its Limitations
To reduce memory footprints, disk-based ANNS systems (e.g., [6, 24, 44, 52]) adopt a hybrid storage architecture by keeping small representative data in memory and persisting full-precision vectors and auxiliary index metadata on disk. For example, DiskANN [24] keeps lossy-compressed vectors (compressed by product quantization (PQ) [25]) in memory, while storing a complete graph-based auxiliary index and fullprecision vectors on disk. SPANN [6] keeps an in-memory graph of cluster centroids, each being attached to an on-disk posting list with full-precision vectors. However, SPANN replicates each vector up to eight times across different posting lists to maintain high search accuracy, leading to substantial storage overhead (§5.2). Thus, in this work, we focus on DiskANN for problem motivation. Figure 1 depicts DiskANN’s disk storage layout, with graph index vertices sorted by ID and stored sequentially. Each vertex bundles a full-precision vector with its neighbor list, enabling both to be fetched in a single disk I/O during
ANNS aims to find the most similar items in a large vector dataset given a search query. As shown in Figure 1, an ANNS system employs deep-learning-based embedding models to map unstructured data into high-dimensional vectors within 2
Normalized latency
DiskANN-IOWait 1.0
1940
DiskANN-CPU
3320 1248
4744
2072
PipeANN-IOWait 6099
2918
7485
3770
neck remains. To justify, we profile DiskANN [24] and PipeANN [18] using the SIFT1M dataset1 [29], and measure the I/O wait time (i.e., the duration that CPU threads are idle while waiting for disk I/Os to complete). We set the beam width W = 4 to mitigate I/O overhead, as suggested by the DiskANN paper [24], and vary the candidate list size L from 50 to 300 to address various search accuracy levels. Figure 2 shows that even with pipelining, the I/O wait time of PipeANN still accounts for 52.9-72.2% of the overall search latency. This shows that the high I/O demands of graph traversal cannot be fully alleviated by pipelining alone. Updates are also costly and incur significant I/O bandwidth, as each vector update modifies not only vector data but also all relevant auxiliary index metadata. For example, for a graphbased auxiliary index, updating a vector often also revises the adjacency lists of all its neighbors. Even with buffered updates [42], the auxiliary index still needs to be periodically rewritten to disk to incorporate accumulated changes.
PipeANN-CPU 8830
4629
5494
0.5
0.0
50
100
150
200
250
300
Candidate list size (L)
Figure 2: Search latency breakdowns of DiskANN and PipeANN, including CPU time and I/O wait time, normalized to the search latency of DiskANN. The number above each bar represents the search latency in microseconds (µs). We use single-threaded execution to eliminate interference from multi-threading and limit variance.
graph traversal. Since vertices are fixed-size and page-aligned, DiskANN can directly compute any vertex’s disk offset from its ID without metadata lookup overhead. For a search query, DiskANN maintains a candidate list of size L. It first initializes candidates with the neighbors of a designated entry point, ranked by the distance between their in-memory PQ codes and the query vector. It then expands the search frontier iteratively. In each iteration, it issues batch I/O requests to fetch the top-W unvisited candidates (W is called the beam width) from disk and evaluates their neighbors using in-memory PQ codes, so as to select the most promising candidates without reading the full-precision vectors of neighbors from disk. Finally, DiskANN re-ranks the visited vertices using their full-precision vectors to return the top-K result set. Despite various I/O optimizations, existing disk-based ANNS systems still face two critical limitations at the persistent storage layer. Limitation #1: High storage costs. Disk-based ANNS systems have high storage overhead due to the need for storing both high-dimensional vector data and auxiliary index metadata. For instance, a 128-dimensional vector [29], with each dimension as a 4-byte floating-point number, consumes 512 bytes. To achieve high recall accuracy, a graph-based index should connect each vector to 128 neighbors [18]. If each neighbor ID is a 4-byte integer, this adds another 512 bytes of metadata, making the total storage per vector entry 1 KiB. This overhead is significant when compared to the average data size in modern NoSQL data stores [1, 4, 38], which is often only a few hundred bytes [3]. Furthermore, a vector dataset can scale up to hundreds of trillions of parameters in production applications [20], and the space overhead is further aggravated by keeping multiple replicas for fault tolerance and load balancing [50]. Limitation #2: High I/O demands. Disk-based ANNS systems suffer from significant I/O amplification in search and update operations. Search queries inevitably traverse large portions of the auxiliary index on disk to identify the result set. Such disk-bound traversal can account for over 70% of the total query time [30]. Even though search optimization techniques, such as pipelined I/Os and computations [18], can improve search performance, the inherent I/O bottle-
2.3
Motivation and Challenges
Vector data and auxiliary index metadata have fundamentally distinct characteristics. We identify their two key differences that lead to storage and I/O inefficiencies. (i) Different data semantics. From a storage perspective, vector data and auxiliary index metadata differ substantially in representation and structure. Vector data generated by embedding models typically encodes high-dimensional numerical features, each with specific characteristics. In contrast, auxiliary index metadata primarily contains neighbor IDs as fixed-length integers (e.g., adjacency lists in a graph-based index [24] or posting lists in a cluster-based index [6]). Colocating them in storage overlooks opportunities for dataspecific optimizations for improved space efficiency. (ii) Different access patterns. From an I/O perspective, both vector data and auxiliary index metadata are accessed in distinct ways during both search queries and updates. Each search query in disk-based ANNS systems frequently traverses the auxiliary index to identify candidate vectors, but only sporadically accesses candidate full-precision vectors for final re-ranking [24]. Auxiliary index metadata must be kept up-to-date to maintain search accuracy [51, 52], while vector data can be updated asynchronously without compromising correctness. Such distinctions motivate data-specific optimizations for improved I/O performance. Design considerations. To address storage and I/O inefficiencies in disk-based ANNS systems, we explore decoupled storage management for vector data and auxiliary index metadata. We pose four design questions to address. Q1: How to maximize vector storage savings? Storage compression is a common approach to reduce content redundancy, but it should maintain data integrity without compromising 1 The dataset contains 1 million vectors with 128 dimensions. We choose this small-scale dataset for ease of analysis and visualization, yet our findings hold consistently for billion-scale datasets (§5).
3
Hot neighbors
Compression metadata
Disk [0.12, 0.34, 0.75, .. ] [0.16, 0.28, 0.67, ..]
1
Vector file
5
0 3
2 4
32.8
DimensionalStd 12.2
0.09 9.69
0.06
SIFT1M
SPACEV1MDecoupleVS1M
(a) Value dispersion
GlobalEntropy 1.0
ColumnarEntropy
2.63
5.59 5.46 1.73
4.39 2.86
0.5
0.0
SIFT1M
SPACEV1MDecoupleVS1M
(b) Information entropy
Figure 4: Normalized value dispersion and information entropy of different datasets.
eral novel techniques to address the storage and I/O inefficiencies described in §2.3.
Vector 1 Neighbor list
DiskANN’s index file
3.1
Figure 3: Architecture of DecoupleVS.
Design Overview
Figure 3 shows DecoupleVS’s architecture. It separately stores the auxiliary index (containing each vertex’s neighbor count and neighbor list) and full-precision vector data (ordered identically to the vertices in the auxiliary index) in distinct on-disk files (in contrast, DiskANN [24] stores them together in the same on-disk file). Similar to DiskANN, DecoupleVS caches PQ-compressed vectors in memory, but additionally maintains compression metadata and hot neighbor lists in memory to support efficient storage access (§3.4). Based on the decoupled architecture, DecoupleVS further introduces various techniques to optimize space efficiency, search, and updates.
search accuracy, especially when full-precision vectors are essential for final re-ranking [24] and the auxiliary index should maintain the search algorithm correctness. Thus, we focus on lossless compression techniques to allow perfect reconstruction after decompression. However, while generalpurpose lossless compression techniques like entropy coders (e.g., Huffman [28], ANS [9]) and dictionary coders (e.g., LZ77 [40], LZ4 [7]) are widely adopted, they do not address semantic characteristics of high-dimensional vectors and auxiliary index metadata, leading to sub-optimal storage savings. Q2: How to mitigate the operational overhead on compressed data? Operations on compressed data should maintain high search query and update performance, so the computational overhead from compression and decompression should be mitigated. Additionally, conventional uncompressed ANNS systems store fixed-size vectors and allow direct disk addressing via vector IDs, yet compression introduces variable-size vector data and auxiliary index metadata, making direct disk addressing infeasible. Variable-size compressed data necessitates additional metadata management and indirections, leading to extra latency and complexity. Optimizing access to variable-size compressed data is critical. Q3: How to achieve high performance and accuracy in search queries? Separating vector data and auxiliary index metadata in decoupled storage destroys the I/O locality and triggers multiple I/Os to distinct storage locations. Such extra I/O overhead can significantly degrade search performance. Also, any I/O optimization strategies should maintain high search accuracy, as in traditional disk-based ANNS systems. Q4: How to achieve high performance in updates? Ensuring consistent updates requires rewriting both vector data and auxiliary index metadata to disk [19, 42]. This process can cause high write amplification, consuming significant I/O bandwidth and degrading foreground search performance.
3
36.2
0.5
0.0
Auxiliary index file
DecoupleVS: Index decoupling Vector 0 Neighbor list
1.0
Norm. entropy
PQ codes
Norm. dispersion
GlobalStd
Memory
• Tailored lossless compression (§3.2). DecoupleVS analyzes the distinct compressibility characteristics of vector data and auxiliary index metadata. It applies tailored lossless compression schemes to each. • Hierarchical storage layouts (§3.3). DecoupleVS introduces hierarchical storage layouts for vector data and auxiliary index metadata to facilitate compression, search, and updates. It carefully manages the memory footprint of compression metadata to ensure minimal overhead. • Latency-aware vector search (§3.4). DecoupleVS differentiates the search I/O paths for vector data and auxiliary index metadata based on their distinct access patterns to prioritize latency-critical operations. It also adaptively prefetches candidate vectors to further mitigate I/O overhead. • Batched vector updates (§3.5). DecoupleVS supports efficient batched updates by separating the update paths for vector data and auxiliary index metadata. It promptly merges batched insertions and deletions into the auxiliary index as in DiskANN [42] to preserve freshness, while updating asynchronously vector data in an append-only manner and performing garbage collection selectively in the background with low write amplification.
3.2
Tailored Lossless Compression
Vector data characterization. We first characterize the compressibility of vector data and auxiliary index metadata. We consider three real-world datasets, each containing 1 million vectors, for motivation: (i) SIFT1M [29] with 128 dimensions (also used in §2.2), (ii) SPACEV1M with 100 dimensions,
DecoupleVS Design
DecoupleVS is a decoupled vector data and auxiliary index storage management framework. It currently builds on graphbased indexing based on DiskANN [24], and introduces sev4
The most frequent symbol of each byte column
extracted from the Big ANN Benchmarks suite [34], and (iii) DecoupleVS1M with 128 dimensions, a proprietary dataset extracted from a commercial application. In §5, we validate our design using billion-scale datasets. Since vectors are normalized to reduce intra-dimensional variability (§2.1), we hypothesize that values within the same dimension exhibit lower variation than the global distribution. We define two metrics: (i) global dispersion, the standard deviation across all values in the dataset, and (ii) dimensional dispersion, the average standard deviation calculated independently for each dimension. Figure 4(a) shows that dimensional dispersion is consistently lower than global dispersion across all datasets, validating our hypothesis. The lower-dimensional dispersion indicates that values within the same dimension are more concentrated and allow more effective compression. We further analyze the compressibility of vector data using information entropy [41]. We define two metrics: (i) global entropy, computed across all bytes in the dataset to measure overall randomness, and (ii) columnar entropy, the average entropy of each byte column across all vectors. Figure 4(b) shows that columnar entropy is consistently lower than global entropy across all datasets, with reductions of 34.3% and 34.8% for SIFT1M and DecoupleVS1M, respectively. This indicates strong byte-positional locality, confirming that symbol distributions at specific byte positions are highly concentrated and exploitable for compression. Delta compression for multi-dimensional vectors. Our entropy analysis shows that compressing data at the same byte position across vectors could yield high compression savings. However, this would require separate compression streams for each byte position, which severely degrades retrieval performance due to numerous decompression operations. To address this, DecoupleVS constructs a base vector by choosing the most frequent byte value at each byte position from all vectors being considered. It then employs XOR-based delta compression [21, 49], as shown in Figure 5, by applying bitwise-XOR operations to each vector with the base vector to produce an XOR-delta (with low entropy). The XORdeltas are further compressed with lossless compression based on Huffman coding [28], which offers fast decoding and a nearly optimal compression ratio [53]. This maintains bytepositional locality and enables effective vector-level compression, rather than separate byte-level compressions. Note that prior studies related to delta compression [21, 35, 49] do not consider multi-dimensional vectors, while we address this by carefully constructing base vectors. Auxiliary index compression. In a graph-based index, the auxiliary data for each vector comprises a neighbor count and an adjacency list of integer identifiers. Since all neighbors are compared in each search anyway, the order of neighbors in the adjacency list does not affect search accuracy. Thus, DecoupleVS sorts neighbor IDs in ascending order and transforms the list into a monotonically increasing sequence that becomes highly compressible. It applies the Elias-Fano al-
Base vector 00101100 11101100 10101100
Entropy compressor
V0 00101100 00111000 10101100
00000000 11010100 00000000
V1 00101100 11101100 00001100
00000000 00000000 10100000
V2 00101100 11101100 10111100
00000000 00000000 00000000 XOR deltas
Figure 5: Delta compression for multi-dimensional vectors. Become immutable when filled
Segment file Mutable space Segment file Chunk
Chunk
Metadata file for a single segment Symbol frequency table
Block Block-level metadata
Block
Block
Full-precision vectors
Segment files
Chunk-level metadata
Chunk-level metadata
Chunk-level metadata cached in memory
First-block offset
# blocks
Boundary Base vector vector IDs
Figure 6: Hierarchical storage layout for vector data.
gorithm [10, 11] to compactly store the sorted neighbor IDs using a two-level representation: each ID is split into lower and higher bits, where the lower bits have the same width across all IDs and record the exact representation, while the higher bits of all IDs are stored in a single bitmap for compact representation.
3.3
Hierarchical Storage Layouts
To support efficient search on variable-sized compressed vector data, DecoupleVS proposes hierarchical storage layouts for vector data and auxiliary index metadata, so as to enable efficient searches and updates. Segment-level vector data organization. As shown in Figure 6, DecoupleVS organizes vector data into segments, each represented as a file with a fixed capacity for the maximum number of vectors. A segment is initially mutable and uncompressed, accepting new vectors via append-only writes in a log-structured manner. Once a segment reaches its capacity, it is sealed and becomes immutable, and a background thread compresses the immutable segment to a smaller size. Each segment file has an ID starting from 0, and vector IDs are mapped to a specific segment file by dividing the vector ID by the capacity. During updates, DecoupleVS triggers asynchronous threads to free the invalid vectors when the stale data volume in a segment exceeds a predefined threshold (see §3.5 for details). This enables DecoupleVS to reclaim free space from segments and reduce write amplification, instead of rewriting the entire index during updates as in DiskANN [42]. Each compressed segment is further divided into chunks, each with a fixed capacity for holding the maximum number of vectors. Within each chunk, vectors are organized into multiple physical disk blocks (4 KiB each), representing the 5
minimum I/O units, and are sorted by IDs. To identify a target block for a given vector ID, DecoupleVS maintains chunk-level metadata, including the offset of the first block in the chunk (4 bytes), number of blocks (4 bytes), boundary vector IDs for all blocks (4 bytes each), and a base vector (equal in size to a full-precision vector) for delta compression (§3.2). DecoupleVS also stores all chunk-level metadata for each segment in a separate disk file, so that it can load all chunk metadata into memory during system startup without scanning the entire segment and allow fast lookups. DecoupleVS stores block-level metadata on disk within each block’s header, specifying the number of vectors and their cumulative compressed sizes, and compressed vector data in the block’s tail. To retrieve a vector, DecoupleVS queries the in-memory chunk-level metadata to locate the physical disk block and find the compressed data for decompression. This hierarchical design mitigates memory footprints while preserving efficient random access. Segment-level vector compression. DecoupleVS applies Huffman-based lossless compression (§3.2), which requires a symbol frequency table for code construction. We note that a global table for the entire vector dataset ignores data locality and leads to suboptimal compression, while creating individual tables for fine-grained units (e.g., chunks) would incur substantial metadata overhead. Thus, DecoupleVS performs compression at the segment level, balancing compression efficiency and metadata overhead. To compress vectors within a segment, DecoupleVS employs a two-stage process. In the first stage, it determines whether to apply XOR-based delta compression (§3.2) to each chunk. It samples a portion of the vectors (e.g., the first 10%) and computes the information entropy of both the original uncompressed vectors and their XOR-deltas against a candidate base vector, which is constructed by selecting the most frequent byte value at each byte position within the chunk. If the delta-transformed data exhibits lower entropy, DecoupleVS applies delta compression to all vectors in the chunk; otherwise, it retains the original vectors. This ensures that delta compression is applied only when it achieves storage savings. DecoupleVS stores the outputs, along with the base vector (if used), in the chunk-level metadata. In the second stage, after processing all chunks, DecoupleVS generates a single symbol frequency table for the entire segment based on the resulting vector data. It then encodes all vectors in the segment using the unified Huffman table. It also caches the Huffman table of each segment in memory to enable efficient decompression during search. As shown in Figure 6, DecoupleVS persists only the symbol frequency table (co-located with the chunk-level metadata) to minimize storage footprints, and reconstructs the Huffman table in memory when loading a segment’s metadata. Block-based auxiliary index organization. To handle variable-sized compressed adjacency lists, DecoupleVS employs a block-based storage layout, similar to that used for
vector data. Each disk block contains multiple adjacency lists, with block-level metadata in the header. To enable fast random access, DecoupleVS maintains a sparse in-memory index that stores boundary vector IDs for all blocks, so as to quickly locate the disk block that contains a target vector’s adjacency list, while incurring limited memory overhead. The sparse index is also persisted into a single disk file, so that DecoupleVS can load it into memory during system startup without scanning the entire compressed auxiliary index. Compression metadata memory usage management. Based on the above discussion, DecoupleVS keeps three types of compression metadata in memory: (i) chunk-level metadata, (ii) the Huffman table for each segment, and (iii) the sparse index for compressed auxiliary index. The memory requirement of chunk-level metadata depends on the chunk size, which creates a trade-off between memory usage and access efficiency. DecoupleVS introduces a configurable parameter, chunk-metadata overhead β , representing the ratio of the chunk metadata size to the total vector data size. Let C be the uncompressed chunk size, α ∈ (0, 1] be the ratio of the compressed size to the uncompressed size based on workload characteristics (a smaller α means higher compression savings), and V be the size of a full-precision vector. With a physical block size of 4,096 bytes, the expected number of blocks in a compressed chunk is α×C 4096 . The per chunk metadata size is 4 × α×C + 3 + V bytes. Thus, the 4096 α V +12 chunk-metadata overhead is β = C + 1024 . By adjusting C based on the user-configured β and the known α and V , DecoupleVS effectively controls memory usage; note that if the compression savings are unknown, we can simply set α = 1 for the worst case (i.e., no compression savings). The memory footprints of the per-segment Huffman tables and the sparse index are not configurable, but they are limited and acceptable based on our trace analysis (§5).
3.4
Latency-aware Vector Search
Since the decoupled architecture incurs multiple I/Os separately to vector data and auxiliary index metadata, DecoupleVS employs two complementary strategies to maintain low-latency search performance: (i) differentiated I/O paths that prioritize latency-critical operations, and (ii) adaptive vector fetching that eliminates unnecessary I/O overhead. Differentiated I/O paths. To mitigate I/O overhead, DecoupleVS pipelines I/Os and computations (including decompression and distance calculations), similar to PipeANN [18], to maximize both CPU and I/O utilizations. However, even with pipelining, the disk I/O latency still dominates in the overall query latency (§2.2). In particular, the graph exploration performance is dictated by the access to neighbor lists from the auxiliary index, whereas vector data access primarily influences the recall accuracy during final re-ranking. Based on these insights and the decoupled architecture, DecoupleVS applies differentiated I/O paths to vector data and auxiliary index metadata, and removes vector data I/Os from 6
the critical search path. During graph traversal, DecoupleVS accesses only the compressed auxiliary index to identify candidate vector IDs. To accelerate this process, DecoupleVS dynamically caches hot compressed neighbor lists in memory using the least-recently-used policy. DecoupleVS then prefetches only the necessary full-precision vectors for final re-ranking. To simplify cache management and alleviate memory fragmentation from variable-sized compressed lists, DecoupleVS allocates fixed-size cache entries based on the theoretical worst-case size of Elias-Fano encoded neighbor lists. Recall that Elias-Fano encoding splits each ID into lower and higher bits (§3.2). For a neighbor list of size R with a maximum vector ID N, the theoretical worst-case space requirement is at most 2R + R · ⌈log2 NR ⌉ bits [37]. In contrast, each uncompressed neighbor list requires 32(R + 1) bits (including each vertex and all its R neighbors). For example, with R = 128 in a billion-scale dataset where N = 109 (§5.1), the worst-case compressed size is 2,430 bits, compared to 3,072 bits for uncompressed lists, achieving at least 20.9% space reduction. By using fixed-size entries based on the theoretical bound of the Elias-Fano algorithm, DecoupleVS reserves sufficient space for any compressed neighbor list, while maintaining predictable memory allocation and improved cache efficiency. Adaptive vector prefetching. DecoupleVS proposes an adaptive strategy by prefetching the most promising vectors in parallel and terminating re-ranking early once the result set stabilizes:
didates. This ensures that I/Os are performed only when necessary, so as to mitigate I/Os while preserving search accuracy.
3.5
Batched Vector Updates
Existing disk-based ANNS systems typically require rewriting large portions of the index file during updates. For example, graph-based indexes buffer insertions [42] and deletions [19, 42] in memory, and periodically merge these updates to disk once a threshold is reached. Since vector data and auxiliary index metadata are co-located, even incremental changes require rewriting the entire index to preserve consistency. This leads to high write amplification and substantial I/O and temporary storage overhead during merges. DecoupleVS’s decoupled architecture enables independent update paths for vector data and auxiliary index metadata. Our key insight is that the two components have different update requirements. Auxiliary index metadata contains highly interconnected graph structures and requires periodic global repairs to maintain graph integrity for accurate search. In contrast, vector data exhibits no inter-dependencies: each vector can be written independently and accessed by ID, making it well-suited for log-structured, append-only writes. Leveraging this distinction, DecoupleVS performs batch merges for the auxiliary index to preserve graph integrity, while using segment-level append-only writes for vector data (§3.3). Space reclamation for vector data is deferred to background garbage collection (GC), avoiding full index rewrites in each merge cycle. DecoupleVS handles two key update operations, namely insertions and deletions, as described below. Vector insertions. DecoupleVS follows the insertion workflow of FreshDiskANN [42] to consolidate random writes and reduce write amplification. It inserts new vectors into the in-memory Vamana index [24]. When the in-memory index reaches a predefined threshold, DecoupleVS computes neighbor deltas for all valid vectors and applies them to the on-disk auxiliary index on a per-batch basis. For vector data, DecoupleVS appends new vectors to the mutable segment’s tail and maintains an ID-to-location mapping within each segment group for subsequent lookups and GC. Vector deletions. For the auxiliary index, DecoupleVS buffers deletions and applies them in batches, removing references to deleted vectors from their neighbors’ adjacency lists to preserve graph connectivity. For vector data, DecoupleVS marks deleted vectors as stale and reclaims their space via GC. GC runs asynchronously at the segment level when buffered updates are merged to disk, and is triggered in the background to limit interference with foreground operations. It selects candidate segments based on their garbage ratio (i.e., the fraction of invalid vectors), greedily prioritizing segments with the highest ratios. For the selected segments, DecoupleVS compacts all valid vectors into new segments, updates in-memory metadata to point to the new locations, and frees the disk space of the old segments. During compaction, DecoupleVS
• Phase 1 (Vector prefetching): During graph traversal, DecoupleVS maintains a max-heap of size K + B, where K is the expected number of final results and B is the batch size, to track top candidates based on their in-memory PQencoded distances. Once the heap is full, if B consecutive candidates are explored without updating the heap, the search is considered to be stable. DecoupleVS then issues I/O requests to prefetch full-precision vectors for the top candidates. To prevent contention with graph traversal, these requests utilize only the available I/O bandwidth, which can be obtained by the configurable beam width W [24] minus the number of in-flight I/Os from graph traversal. This prepares vector data for re-ranking without I/O contention. • Phase 2 (Adaptive re-ranking termination): After graph traversal, DecoupleVS processes prefetched vectors in batches. It re-ranks candidates using the final top-K maxheap based on their full-precision vectors. Upon entering the re-ranking phase, it immediately begins processing the vectors prefetched during graph traversal while asynchronously issuing I/O requests for the next batch of promising candidates. For each batch, it calculates a benefit ratio, defined as the fraction of candidates that update the final max-heap. If this ratio falls below a predefined threshold (e.g., 0.01), DecoupleVS terminates re-ranking; otherwise, it issues I/O requests for the next batch of promising can7
Table 1: Datasets used in evaluation. Source
#Vectors Type #Dims
Size
#Queries
DecoupleVS100M
109 M
FP32
128
53 GiB
10 K
SIFT100M
100 M
uint8
128
12 GiB
10 K
SPACEV100M
100 M
int8
100
9.4 GiB
29.3 K
SIFT1B [26]
1B
uint8
128
120 GiB
10 K
SPACEV1B [6]
1.4 B
int8
100
131 GiB
29.3 K
Baselines. We compare DecoupleVS with three disk-based ANNS systems based on their open-source implementations.
• DiskANN [24]: It is a popular on-disk graph-based ANNS system that employs a best-first search algorithm and stores PQ-compressed vectors in memory to achieve high search performance. Its official implementation [46] supports batched updates to mitigate write amplification [42]. • PipeANN [18]: It is an extension of DiskANN that overlaps disk I/Os and distance computations during graph traversal to reduce search latency. • SPANN [5, 6]: It is an on-disk, cluster-based ANNS system. It partitions data into clusters, organized with a tree structure for load balancing. It connects the cluster centroids using an in-memory relative-neighborhood graph [45]. To reduce disk I/Os during search, it stores the posting lists of each centroid and co-locates vectors with their IDs on disk.
also compresses and seals filled segments (§3.3).
4
DecoupleVS Implementation
We implement DecoupleVS in C++ based on the PipeANN codebase [18]. PipeANN extends the vanilla DiskANN [24] by employing io uring as the I/O engine and leveraging asynchronous I/O requests to reduce I/O wait time, and its codebase has 73.8 K LoC. We integrate our proposed techniques into the PipeANN codebase by adding 19.1 K LoC to support vector storage decoupling, lossless compression, and efficient operations on the compressed auxiliary index. For Huffman coding, we adopt a high-performance implementation [53] that exploits CPU out-of-order execution to accelerate compression and decompression. For Elias-Fano encoding, we build upon the Succinct library [16]. We also implement parallel compression and decompression for the auxiliary index to maximize throughput.
5
We exclude in-memory ANNS systems (e.g., HNSW [31] and NSG [12]), as we focus on disk-based baselines due to their superior cost efficiency and scalability. We also omit a few recent disk-based ANNS systems, which focus on enhancing search and update performance but do not address space efficiency. For example, we exclude Starling [48], which improves DiskANN’s search performance but is outperformed by the later proposed PipeANN [18]. We also exclude OdinANN [19] and SPFresh [52], which extend DiskANN and SPANN with in-place updates, respectively, since our focus is on demonstrating that DecoupleVS achieves space efficiency, while supporting efficient batched updates comparable to the baselines. Note that DecoupleVS is orthogonal to existing in-place update extensions and could potentially benefit from their techniques for improved update performance.
Evaluation
We conduct evaluation and address the following questions: • How does DecoupleVS perform in terms of space efficiency, search performance, and update performance compared to other disk-based ANNS systems? Can it scale effectively to billion-scale datasets? (§5.2) • What are the performance contributions of individual components within DecoupleVS’s design? (§5.3)
5.1
Default settings. For DecoupleVS100M, SIFT100M, and SPACEV100M, the graph-based index uses R = 96 outgoing edges per node and a candidate list size of Lb = 100. For SIFT1B and SPACEV1B, we increase the parameters to R = 128 edges and a candidate list size of Lb = 200 to maintain high search accuracy. For SPANN, we follow its default configurations. We set the beam width (i.e., the breadth of the graph search) to W = 4 for DiskANN, PipeANN, and DecoupleVS, the default in DiskANN [24]. For fair comparisons, we apply the same dynamic cache management (§3.4) to all systems, with the cache capacity set to 1 M entries (corresponding to the size ratios of 1% and 0.1% for 100 M and 1 B datasets, respectively). For DecoupleVS, we set the uncompressed chunk size to C = 4 MiB, the uncompressed segment size to 512 MiB, and the re-ranking batch size to B = 10. We measure search accuracy by recall@10, defined as the fraction of queries whose true nearest neighbors appear in the top-10 search results (i.e., the result set size K = 10).
Methodology
Testbed. We conduct experiments on a physical server equipped with two 32-core 2.30 GHz Intel Xeon Platinum 8336C CPUs, 512 GB DDR4 memory, and a Samsung PM9A3 3.84 TB NVMe SSD. The server runs Debian 9.13 with Linux kernel 5.4.56. Datasets. Table 1 shows the five datasets used to evaluate DecoupleVS. DecoupleVS100M is a proprietary dataset with 109 M vectors, sampled from a production-scale partition of a commercial search engine that indexes hundreds of billions of vectors. SIFT100M, SPACEV100M, SIFT1B, and SPACEV1B are public datasets [34], where SIFT100M and SPACEV100M are the first 100 M vectors of SIFT1B and SPACEV1B, respectively. Both SIFT100M and SIFT1B datasets are derived from image descriptors, and both SPACEV100M and SPACEV1B datasets are derived from web-search embeddings released by Microsoft Bing. 8
Norm. storage size
SPANN-Index
DiskANN-Index
DecoupleVS-Index
SPANN-Vector
DiskANN-Vector
DecoupleVS-Vector
182.2
1.0
82.2
47.7 104.3
0.5 43.1 0.0
59.1 1.0
54.5
421.5
27.7
28.7
DecoupleVS100M SIFT100M
635.8
SPACEV100M
(a) 100M-scale
By decoupling auxiliary index metadata from vector data, DecoupleVS mitigates internal fragmentation, reclaiming 10.3 GiB and 4.4 GiB of wasted space on DecoupleVS100M and SIFT100M, respectively. Note that SPACEV100M has less severe internal fragmentation due to its smaller per-entry size, which occasionally aligns with the page size. Second, DecoupleVS compresses auxiliary index metadata using EliasFano encoding, further reducing its storage size by 63.8%, 61.3%, and 45.8% on DecoupleVS100M, SIFT100M, and SPACEV100M, respectively, compared to DiskANN. Figure 7(b) presents storage size comparisons for the billion-scale datasets. DecoupleVS consistently improves space efficiency compared to other baselines, achieving significant reductions in both vector data and auxiliary index metadata sizes. Specifically, DecoupleVS reduces the overall storage size by 33.7% and 42.6% compared to DiskANN on SIFT1B and SPACEV1B, respectively. Thus, DecoupleVS’s tailored compression remains effective for billionscale datasets.
891.4 511.5
0.5
0.0
SIFT1B
SPACEV1B
(b) Billion-scale
Figure 7: Exp#1 (Space efficiency). For 100M-scale datasets, sizes are normalized to SPANN. For billion-scale datasets, sizes are normalized to DiskANN. The numbers above the bars indicate the absolute storage sizes in GiB.
5.2
Macrobenchmarks
5.2.1
Space Efficiency
We compare the storage sizes of DecoupleVS against DiskANN and SPANN. We omit the results for PipeANN since it shares the identical storage layout and has the same storage size as DiskANN. We also exclude SPANN from the billion-scale datasets due to its excessive memory usage in auxiliary index construction [18, 32]. Exp#1 (Space efficiency). Figure 7(a) shows that DecoupleVS achieves significant storage savings over the baselines. On 100 M-scale datasets, DecoupleVS reduces the overall storage size by 76.4%, 65.1%, and 53.1% compared to SPANN, and by 58.7%, 47.4%, and 41.9% compared to DiskANN, on DecoupleVS100M, SIFT100M, and SPACEV100M, respectively. SPANN has the largest storage size since it replicates each vector by up to 8× across different clusters to maintain high search accuracy [6]. We further analyze the storage size breakdown for both vector data and auxiliary index metadata components in DiskANN and DecoupleVS. DecoupleVS’s tailored compression (§3.2) effectively reduces the sizes of both components. For vector data, DecoupleVS reduces its storage size by 46.4%, 23.8%, and 25.2% relative to raw vector sizes on DecoupleVS100M, SIFT100M, and SPACEV100M, respectively. Notably, applying Huffman coding [28] alone to vectors achieves only 38.5% compression on DecoupleVS100M, showing that combining delta encoding with lossless compression can achieve further space savings (§3.2). However, delta encoding has no improvements on SIFT100M and SPACEV100M, as they have already used 8-bit quantization, which increases information entropy to reduce accuracy loss. Thus, applying further lossless compression yields limited benefits under entropy coding principles. Nevertheless, DecoupleVS still achieves notable storage reductions on these two datasets. The storage reduction in auxiliary index metadata comprises two aspects. First, DiskANN uses page-aligned fixedsize entries to co-locate vector data and auxiliary index metadata. This incurs large internal fragmentation when the combined size does not align well with the 4 KiB page size.
5.2.2
Search Performance
We evaluate search performance by comparing the overall throughput (in number of queries per second (QPS)) and P99 latency of DecoupleVS against SPANN, DiskANN, and PipeANN. We vary the search candidate list size Ls from 50 to 500 for DiskANN, PipeANN, and DecoupleVS to obtain 10 accuracy levels, and adjust the number of internal search results in SPANN accordingly within the same range. We run 64 concurrent search threads to demonstrate the maximum throughput achievable by each system. Exp#2 (Search throughput). Figures 8(a)-8(c) present the search throughput on the three 100 M-scale datasets. In most settings, DecoupleVS achieves the highest throughput. For example, on DecoupleVS100M at 80% recall@10, DecoupleVS achieves 2.58× and 2.18× throughput gains compared to DiskANN and PipeANN, respectively. These improvements stem from more efficient cache space utilization and specialized I/O strategies that separate vector data from auxiliary index metadata (§3.4). An exception occurs at the lowest accuracy setting Ls = 50, where PipeANN’s throughput is slightly higher. This occurs because with a smaller search space under Ls = 50, both PipeANN and DecoupleVS benefit from dynamic caching. However, DecoupleVS incurs additional disk I/Os to fetch full-precision vectors. As Ls increases, DecoupleVS’s faster graph exploration and efficient caching allow it to consistently outperform PipeANN at higher accuracy levels. Graph-based indexes (i.e., DiskANN, PipeANN, and DecoupleVS) generally deliver higher throughput than SPANN, with the exception of DiskANN on SPACEV100M, where SPANN has slightly better performance at high accuracy levels. Nevertheless, both PipeANN and DecoupleVS not only surpass SPANN’s throughput but also achieve higher accuracy. Their advantage comes from a modified DiskANN’s 9
Throughput (QPS)
SPANN
DiskANN
30k
30k
30k
20k
20k
20k
10k
10k
10k
0 66
76
87
0 95
97
100
0 45
PipeANN
72
100
DecoupleVS
20k
20k
10k
10k
0 95
97
100
0 67
80
92
80
92
Recall@10 Recall@10 Recall@10 Recall@10 Recall@10 (a) (b) SIFT100M (c) SPACEV100M (d) SIFT1B (e) SPACEV1B DecoupleVS100M Figure 8: Exp#2 (Search throughput). We show the throughput (queries per second) against Recall@10 (%); higher is better. The points from left to right in each curve correspond to increasing candidate list sizes, which generally lead to higher recall.
P99 Latency (ms)
SPANN
10 10 10
3
10
2
10
1
10 76 Recall@10
2
10
1
87 10 45
DiskANN
10
10
0
0
10 66
3
PipeANN
3
10
10
2
2
10
1
100 10 45
1
10
0
0
72 Recall@10
DecoupleVS 2
72 Recall@10
100
10 95
1
0
97
Recall@10 (d) SIFT1B
100 10 67
Recall@10 (e) SPACEV1B
(a) (b) SIFT100M (c) SPACEV100M DecoupleVS100M Figure 9: Exp#3 (Search latency). We show the P99 latency (ms) against Recall@10 (%); lower is better.
best-first search algorithm, which overlaps disk I/Os with distance computations to enhance search performance. Figures 8(d)-8(e) show the search throughput on billionscale datasets. Consistent with the 100 M-scale results, DecoupleVS achieves higher throughput than DiskANN on both SIFT1B and SPACEV1B. However, DecoupleVS’s throughput is slightly lower than or comparable to PipeANN’s; for example, DecoupleVS has up to 11.9% lower throughput than PipeANN when recall@10 is below 99%. The reason is that billion-scale datasets have a larger search space, leading to more disk I/Os. Nevertheless, DecoupleVS achieves similar or higher throughput for recall@10 at least 99% on SIFT1B, consistent with prior findings that DecoupleVS excels at higher accuracy levels. Exp#3 (Search latency). Figure 9 shows the P99 latency results. Similar to throughput results, DecoupleVS consistently achieves lower P99 latency compared to SPANN and DiskANN, and comparable latency to PipeANN. For example, DecoupleVS reduces the P99 latency by 49.0% and 50.0% compared to DiskANN and PipeANN, respectively, on DecoupleVS100M at 80% recall@10. While DecoupleVS exhibits 57.2% higher latency at the lowest recall levels on SIFT1B, it maintains comparable P99 latency at higher recall levels, consistent with previous findings. 5.2.3
search optimization and shares the same update path and disk index layout as DiskANN, and we expect it to have similar update performance to DiskANN. For each system, we construct the auxiliary index using SIFT100M. As in prior work [19, 42], we simulate a streaming update workload by replacing 50% of vectors with 10 update iterations, each of which merges 5% deletions and 5% insertions of the total dataset size. Our analysis (Exp#6) shows that 10 update iterations suffice to show the performance differences between DecoupleVS and DiskANN. To evaluate concurrent search and update performance, we launch 32 search threads and 32 update threads. We measure search throughput, P50 and P99 latencies, search accuracy, memory usage, and storage size during concurrent search and update operations. Exp#4 (Concurrent search and update performance). DecoupleVS achieves an average throughput gain of 1.88× over DiskANN, while reducing P50 and P99 latencies by up to 51.0% and 49.4%, respectively. These improvements stem from DecoupleVS’s latency-aware search strategy, which mitigates I/O interference during concurrent updates (§3.4). DecoupleVS also maintains search accuracy comparable to DiskANN, with only a 0.13% average loss. Note that index loading at the beginning of each merge phase can cause latency spikes and throughput drops, as it consumes significant background I/O bandwidth.
Update Performance
Figures 10(e)-10(f) show the space efficiency during concurrent updates. DecoupleVS keeps memory usage comparable to DiskANN, with only 1.1% higher usage on average.
We compare the update performance of DecoupleVS against DiskANN. We do not consider PipeANN, which focuses on 10
20k
DecoupleVS
30
15k 10k 5k 0 0
4 Elapsed Time (×104s)
20 10 0 0
9
150 Latency (ms)
Latency (ms)
Throughput (QPS)
DiskANN
(a) Search throughput
4 Elapsed Time (×104s)
0 0
9
98 9
30 20 10 0 0
9
200
40
Storage (GB)
Memory (GB)
Recall@10 (%)
99
4 Elapsed Time (×104s)
(c) P99 latency
50
4 Elapsed Time (×104s)
50
(b) P50 latency
100
0
100
4 Elapsed Time (×104s)
9
150 100 50 0 0
4 Elapsed Time (×104s)
9
(d) Search accuracy (e) Memory usage (f) Storage size Figure 10: Exp#4 (Concurrent search and updates). We show the overall update performance on SIFT100M.
This modest increase results from three factors. First, DecoupleVS caches compression metadata, with minimal overhead (28 MiB on SIFT100M). Second, DecoupleVS requires additional memory buffers for compression and decompression during updates. Third, since DecoupleVS processes the auxiliary index in batches with identical batch sizes based on the physical storage size, it stores more entries per batch due to its compressed storage layout, leading to slightly higher memory usage during updates. At the persistent storage layer, DecoupleVS reduces the peak storage size by 33.6% compared to DiskANN during updates, so it effectively mitigates write amplification in streaming updates. The stable storage size across different merge iterations indicates that the garbage collection process effectively reclaims space occupied by stale vectors. In summary, DecoupleVS demonstrates superior search performance during concurrent updates, while maintaining comparable memory usage and substantially reducing storage size. This validates the effectiveness of DecoupleVS’s design in handling dynamic workloads. However, we note that DecoupleVS shows slightly longer merge time than DiskANN due to the interference between search and updates (Exp#6).
5.3
vector disk I/O count, and (iv) total disk I/O time. The CPU usage includes (i) graph decompression time, (ii) PQ distance calculation time, (iii) vector decompression time, and (iv) reranking distance calculation time. We measure each metric for a single search query and report the average results across all queries. Since we launch 64 search threads in parallel, the actual time spent on each search query is larger than the sum of all steps under thread interference. Table 2 shows the breakdown. For disk I/O usage, DecoupleVS significantly improves cache efficiency. It increases the graph cache hit count by 55.4% and 91.9% compared to DiskANN and PipeANN, respectively. PipeANN shows the lowest cache hit count because its search strategy enlarges the search space. Thus, PipeANN has the highest total physical disk I/Os (58 compared to DiskANN’s 54.8 and DecoupleVS’s 42.8), resulting in the highest total disk I/O time. However, PipeANN overlaps disk I/O time with CPU computations, leading to lower overall search latency than DiskANN. For CPU usage, DecoupleVS shows minimal decompression overhead for full-precision vector data and neighbor lists, which account for 2.4% of the average search query latency. DiskANN exhibits the highest computation time since its blocking I/O model leads to frequent context-switching overhead among threads. DecoupleVS shows higher PQ calculation time than PipeANN since it has higher CPU utilization due to reduced I/O wait time.
Microbenchmarks
We focus on SIFT100M to show the performance breakdown on both search and update paths. Exp#5 (Search performance breakdown). We study how individual components of DecoupleVS contribute to the search performance gain over the baselines. Specifically, we analyze the performance breakdown from the perspective of resource usage at Ls = 100, including disk I/O usage and CPU usage. The I/O usage components include: (i) cache hit count during graph traversal, (ii) disk I/O count during graph traversal, (iii)
Exp#6 (Update performance breakdown). We analyze the update performance in Exp#4 by examining two most time-consuming components: (i) Merge-Delete, the time taken to merge deletion markers into the on-disk index; and (ii) Merge-Insert, the time taken to merge newly inserted 11
Table 2: Exp#5 (Search performance breakdown). The average latencies of DiskANN, PipeANN, and DecoupleVS are 7.15 ms, 4.19 ms, and 3.07 ms, respectively. Steps
DiskANN
PipeANN
DecoupleVS 99.0
(§5.1) are guided by production experience and principled design choices. Specifically, we set the chunk size C = 4 MiB to minimize chunk-level metadata overhead across our evaluated datasets. We adopt a segment size of 512 MiB following conventions in popular vector databases [27]. We set the cache ratio to at most 1% of the dataset size, which represents a practical memory footprint. We set the re-ranking batch size B = 10 to match the result size K = 10, ensuring high search accuracy. Finally, we set the benefit ratio to 0.01 to achieve high search accuracy. These parameter choices deliver robust performance without requiring extensive tuning for typical deployment scenarios.
I/O usage Graph cache hits
63.7
51.6
Graph I/Os
54.8
58.0
9.9
Vector I/Os
-
-
32.9
Total I/O time
2.52 ms
3.23 ms
1.78 ms
CPU usage Graph decompression
-
-
0.039 ms
PQ calculation
0.94 ms
0.60 ms
0.73 ms
Vector decompression
-
-
0.034 ms
Rerank calculation
0.020 ms
0.0062 ms
0.0027 ms
4970.4 5003.6
1278.7
1367.6
1.0 0.5 0.0
Merge-Delete
Merge-Insert
(a) Computation time
1.0
42.4
40.9 35.6
39.0
0.5
0.0
Merge-Delete
Merge-Insert
(b) Disk I/O time
Figure 11: Exp#6 (Update performance breakdown). We show the average computation and disk I/O times per update operation, normalized to DiskANN. The numbers atop bars indicate the absolute time (in seconds).
points into the on-disk index. We decompose each component into computation and disk I/O times. We present average results over 10 iterations, with error bars showing 95% confidence intervals based on the Student’s t-distribution. Figure 11 shows the average computation and disk I/O times per component, normalized to DiskANN. We observe higher computation time for DecoupleVS compared to DiskANN, with 0.67% and 7.0% increases for Merge-Delete and Merge-Insert, respectively. This stems from two factors. First, DecoupleVS performs additional compression and decompression operations during updates, which introduces extra CPU overhead. Second, DecoupleVS reduces I/O wait time during search (see Exp#5), leading to higher CPU utilization and increased CPU contention during updates. Nevertheless, DecoupleVS reduces the disk I/O time by 13.0% and 8.0% for Merge-Delete and Merge-Insert, respectively. The reason is that DecoupleVS only rewrites the auxiliary index during updates, while DiskANN rewrites the entire index.
5.4
Related Work
Disk-based ANNS systems. Disk-based ANNS systems can be broadly categorized by index structures into graph-based and cluster-based indexes. Graph-based indexes are pioneered by DiskANN [24], which constructs a disk-based index graph for efficient search and further supports efficient buffered updates [42]. Follow-up work optimizes DiskANN’s performance. Starling [48] co-locates neighboring graph vertices on the same disk pages to reduce random I/Os. PipeANN [18] adopts pipelined execution to overlap I/Os and computations during graph traversal. OdinANN [19] improves update performance using write-back caching and delta neighbor pruning to reduce I/O and computation overheads. Cluster-based indexes are pioneered by SPANN [6], which partitions vectors into clusters and attaches on-disk posting lists to each cluster centroid for efficient search, and further supports efficient in-place streaming updates [52]. Recent extensions to SPANN, such as SmartANNS [43] and FusionANN [44], accelerate search by offloading distance computations to SmartSSDs or GPUs. In contrast, DecoupleVS focuses on improving space efficiency, while maintaining high search and update performance. Lossy compression for ANNS. Disk-based ANNS systems (e.g., [24, 44]) often cache lossy-compressed vectors in memory. Product quantization (PQ) [25] is the predominant lossy vector compression technique; it represents highdimensional vectors with compact codes by quantizing subdimensions into codebooks. Optimized-PQ [15] reduces interdimensional correlation via orthogonal rotation preprocessing on the original vectors, thereby improving quantization accuracy over PQ. RaBitQ [13] further improves quantization accuracy by adaptively allocating bits to sub-dimensions based on their variance. While these methods reduce memory usage, they inevitably incur quantization errors in search. To meet high recall requirements [14], existing disk-based ANNS systems still store full-precision vectors on disk for a final re-ranking step. In contrast, DecoupleVS focuses on reducing disk storage costs of full-precision vectors without sacrificing accuracy. General-purpose lossless compression. Lossless compression reduces data volume while ensuring perfect reconstruc-
DecoupleVS
Norm. I/O time
Norm. CPU time
DiskANN
6
Discussion on Parameter Settings
DecoupleVS introduces several configurable parameters: (i) chunk size C, (ii) segment size, (iii) cache size, (iv) re-ranking batch size B, and (v) benefit ratio. Our default configurations 12
tion. General-purpose lossless compression methods, such as entropy coders (e.g., Huffman [28], ANS [9]) and dictionary coders (e.g., LZ77 [40] and LZ4 [7]) are widely adopted, but overlook data-specific characteristics. Domain-specific techniques achieve higher compression savings by exploiting inherent data properties, such as delta compression for time-series data [21, 49, 54] and gap encoding for sorted inverted lists [37, 47]. Following this principle, DecoupleVS designs tailored lossless compression for both vector data and auxiliary index metadata, leveraging their distinct data locality patterns to maximize storage savings without degrading performance.
7
[7] Yann Collet. LZ4. https://github.com/lz4/lz4, 2011. [8] Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for YouTube recommendations. In Proc. of ACM RecSys, 2016. [9] Jarek Duda. Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv:1311.2540, 2013. [10] Peter Elias. Efficient storage and retrieval by content and address of static files. Journal of the ACM (JACM), 21(2):246--260, 1974.
Conclusion
[11] Robert Mario Fano. On the number of bits required to implement an associative memory. Massachusetts Institute of Technology, Project MAC, 1971.
DecoupleVS is a decoupled storage framework designed to optimize the storage efficiency and performance of disk-based ANNS systems. By decoupling vector data from auxiliary index metadata, DecoupleVS enables component-specific optimizations that effectively address the critical bottlenecks of existing monolithic storage solutions. Extensive evaluations on real-world datasets demonstrate that DecoupleVS significantly reduces storage footprints while delivering competitive query latency and update throughput compared to state-of-the-art disk-based ANNS systems.
[12] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment, 12(5):461--474, 2019. [13] Jianyang Gao and Cheng Long. RabitQ: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proc. of ACM SIGMOD, 2(3):1--27, 2024.
References
[14] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Meng Wang, and Haofen Wang. Retrieval-augmented generation for large language models: A survey. arXiv preprint arXiv:2312.10997, 2023.
[1] Apache. Cassandra. https://cassandra.apache. org/, 2025. [2] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Proc. of NeurIPS, 2020.
[15] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization. IEEE Trans. on Pattern Analysis and Machine Intelligence, 36(4):744--755, 2013.
[3] Zhichao Cao, Siying Dong, Sagar Vemuri, and David H. C. Du. Characterizing, modeling, and benchmarking RocksDB key-value workloads at Facebook. In Proc. of USENIX FAST, 2020.
[16] Giuseppe Ottaviano. Succinct. com/ot/succinct, 2017.
https://github.
[17] Mihajlo Grbovic and Haibin Cheng. Real-time personalization using embeddings for search ranking at airbnb. In Proc. of the 24th ACM SIGKDD, 2018.
[4] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E Gruber. Bigtable: A distributed storage system for structured data. In Proc. of USENIX OSDI, 2006.
[18] Hao Guo and Youyou Lu. Achieving low-latency graphbased vector search via aligning best-first search algorithm with SSD. In Proc. of USENIX OSDI, 2025.
[5] Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. Sptag: A library for fast approximate nearest neighbor search. https://github.com/Microsoft/SPTAG, 2018.
[19] Hao Guo and Youyou Lu. OdinANN: Direct insert for consistently stable performance in billion-scale graphbased vector search. In Proc. of USENIX FAST, 2026. [20] Harsha Simhadri. Research talk: Approximate nearest neighbor search systems at scale. https://youtu.be/ BnYNdSIKibQ?t=179, 2022.
[6] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. SPANN: Highly-efficient billion-scale approximate nearest neighborhood search. Proc. of NeurIPS, 2021.
[21] Moshik Hershcovitch, Andrew Wood, Leshem Choshen, Guy Girmonsky, Roy Leibovitz, Or Ozeri, Ilias Ennmouri, Michal Malka, Peter Chin, Swaminathan Sun13
dararaman, et al. ZipNN: Lossless compression for AI models. In Proc. of IEEE CLOUD, 2025.
Science Department, University of British Columbia, Vancouver, BC, Canada, 5(6), 2009.
[22] IBM. AI and the future of unstructured data. https: //www.ibm.com/think/insights/unstructureddata-trends, 2025.
[34] NeurIPS. BIG ANN-Benchmarks. https://big-annbenchmarks.com/neurips21.html, 2021. [35] Wanyi Ning, Jingyu Wang, Qi Qi, Mengde Zhu, Haifeng Sun, Daixuan Cheng, Jianxin Liao, and Ce Zhang. Fmdelta: Lossless compression for storing massive finetuned foundation models. Proc. of NeurIPS, 2024.
[23] Luke James. AI data centers are swallowing the world’s memory and storage supply, setting the stage for a pricing apocalypse that could last a decade. https://www.tomshardware.com/pccomponents/storage/perfect-storm-ofdemand-and-supply-driving-up-storagecosts?ref=aisecret.us, 2025.
[36] OpenAI. The ChatGPT Retrieval Plugin lets you easily search and find personal or work documents by asking questions in everyday language. https://github. com/openai/chatgpt-retrieval-plugin, 2023.
[24] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. Proc. of NeurIPS, 2019.
[37] Giuseppe Ottaviano and Rossano Venturini. Partitioned elias-fano indexes. In Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval, 2014.
[25] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. on Pattern Analysis and Machine Intelligence, 33(1):117--128, 2010.
[39] Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. In Proc. of the EMNLP, 2019.
[26] Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. Searching in one billion vectors: rerank with source coding. In Proc. of IEEE ICASSP, 2011.
[40] Suzanne Rigler, William Bishop, and Andrew Kennings. FPGA-based lossless data compression using Huffman and LZ77 algorithms. In 2007 Canadian conference on electrical and computer engineering, pages 1235--1238. IEEE, 2007.
[38] PinCap. TiKV. https://tikv.org, 2025.
[27] Ken Zhang, Fendy Feng. Introducing the Milvus Sizing Tool: Calculating and Optimizing Your Milvus Deployment Resources . https: //milvus.io/blog/introducing-the-milvussizing-tool-calculating-and-optimizingyour-milvus-deployment-resources.md, 2025.
[41] Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-423, 1948. [42] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. FreshDiskANN: A fast and accurate graph-based ann index for streaming similarity search. arXiv preprint arXiv:2105.09613, 2021.
[28] Donald E Knuth. Dynamic Huffman coding. Journal of Algorithms, 6(2):163--180, 1985. [29] Laurent Amsaleg and Hervé Jégou. Datasets for approximate nearest neighbor search. http://corpustexmex.irisa.fr/, 2010.
[43] Bing Tian, Haikun Liu, Zhuohui Duan, Xiaofei Liao, Hai Jin, and Yu Zhang. Scalable billion-point approximate nearest neighbor search using SmartSSDs. In Proc. of USENIX ATC, 2024.
[30] Shengwen Liang, Ying Wang, Ziming Yuan, Cheng Liu, Huawei Li, and Xiaowei Li. VStore: in-storage graph based vector search accelerator. In Proc. of ACM/IEEE DAC, 2022.
[44] Bing Tian, Haikun Liu, Yuhang Tang, Shihai Xiao, Zhuohui Duan, Xiaofei Liao, Hai Jin, Xuecang Zhang, Junhua Zhu, and Yu Zhang. Towards highthroughput and low-latency billion-scale vector search via CPU/GPU collaborative filtering and re-ranking. In Proc. of USENIX FAST, 2025.
[31] Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. on Pattern Analysis and Machine Intelligence, 42(4):824-836, 2018.
[45] Godfried T Toussaint. The relative neighbourhood graph of a finite planar set. Pattern recognition, 12(4):261--268, 1980.
[32] Microsoft. SPTAG issue #416: Segmentation fault when building SIFT1B. https://github.com/ microsoft/SPTAG/issues/416, 2024.
[46] Simhadri Harsha Vardhan, Krishnaswamy Ravishankar, Srinivasa Gopal, Subramanya Suhas Jayaram, Antonijevic Andrija, Pryce Dax, Kaczynski David, Williams Shane, Gollapudi Siddarth, Sivashankar Varun, Karia
[33] Marius Muja and David Lowe. Flann-fast library for approximate nearest neighbors user manual. Computer 14
Neel, Singh Aditi, Jaiswal Shikhar, Mahapatro Neelam, Adams Philip, Tower Bryan, and Patel Yash. DiskANN: Graph-structured Indices for Scalable, Fast, Fresh and Filtered Approximate Nearest Neighbor Search. https://github.com/Microsoft/DiskANN, 2023. [47] Jianguo Wang, Chunbin Lin, Ruining He, Moojin Chae, Yannis Papakonstantinou, and Steven Swanson. MILC: Inverted list compression in memory. Proceedings of the VLDB Endowment, 10(8):853--864, 2017. [48] Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. Starling: An I/O-efficient disk-resident graph index framework for high-dimensional vector similarity search on data segment. Proc. of ACM SIGMOD, 2024. [49] Zirui Wang, Tingfeng Lan, Zhaoyuan Su, Juncheng Yang, and Yue Cheng. ZipLLM:towards efficient LLM storage reduction via tensor deduplication and delta compression. In Proc. of USENIX NSDI, 2026. [50] Weaviate. Configure replication in Weaviate ANN service. https://docs.weaviate.io/deploy/ configuration/replication, 2025. [51] Haike Xu, Magdalen Dobson Manohar, Philip A Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri. In-place updates of a graph index for streaming approximate nearest neighbor search. arXiv preprint arXiv:2502.13826, 2025. [52] Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, et al. SPFresh: Incremental inplace update for billion-scale vector search. In Proc. of ACM SOSP, 2023. [53] Yann Collet. New Generation Entropy coders. https: //github.com/Cyan4973/FiniteStateEntropy, 2019. [54] Yucheng Zhang, Wen Xia, Dan Feng, Hong Jiang, Yu Hua, and Qiang Wang. Finesse: Fine-grained feature locality based fast resemblance detection for postdeduplication delta compression. In Proc. of USENIX FAST, 2019. [55] Zili Zhang, Fangyue Liu, Gang Huang, Xuanzhe Liu, and Xin Jin. Fast vector query processing for large datasets beyond GPU memory with reordered pipelining. In Proc. of USENIX NSDI, 2024.
15