CS Paper Radar

WaRP: Workload-Aware Request Planning for Vector Retrieval on Object Storage

Ruipeng Wan, Xinyu Zeng, Yiming Qiao, Huanchen Zhang

cs.DB ·submitted 2026-10-21 13:01 UTC · v1

Abstract

Modern vector search systems keep payload vectors in cloud object storage and only a compact routing index on fast local storage, typically using cluster-based ANN indexes. This design inherits a problem existing systems do not address. On object storage, small Range-GETs have latency dominated by fixed per-request overhead and are billed per request. Existing readers either issue one request per probed cluster, or coalesce adjacent ranges with hand-tuned gap or span thresholds that do not transfer across datasets or query workloads. We formulate the grouping of probed-cluster byte intervals into object-store requests as a global per-query optimization problem and present WaRP, a workload-aware request planner that solves it efficiently. Given the sorted byte intervals, a limit on the number of requests per query, and an estimate of how many object-store requests from one query can proceed concurrently under the target serving configuration, WaRP searches for a merge plan that minimizes a concurrency-aware latency surrogate while satisfying the request limit. Using an optimized dynamic program and adaptive frontier search, WaRP returns a plan within $(1{+}ε)$ of the optimum, with per-query planning overhead under $10$ms even in the most demanding tested settings. A lightweight offline reordering pass further improves request mergeability without changing the semantics of ANN search. We implement WaRP inside Lance's I/O scheduler and evaluate it on AWS S3. We build IVFPQ indexes on seven datasets, including SIFT100M and DEEP100M at the 100M-vector scale. WaRP + Reorder improves QPS by $1.09--3.48\times$ and reduces GETs by $2.12--5.19\times$ relative to Lance, while preserving Lance's recall.

Comment
14 pages, 14 figures

Closest papers

Nearest neighbours by meaning across the whole index.

RemoteANN: A Native Vector Search Engine for Cloud Object Storage

cs.DB cs.IR ·2026-10-18 ·Yutong Gou, Silu Huang, Yue Wang, Jianjun Chen, Cheng Long
hot direction similarity 0.75
Abstract

Vector search engines built on cloud object storage have drawn growing attention from both academia and industry. These systems typically adopt a disaggregated storage-compute architecture, persisting the primary vector payload in object stores (e.g., Amazon S3) while retaining compact index metadata on compute nodes. However, conventional vector indexing structures are not natively tailored to the pronounced network latency and per-request access costs of cloud object stores, resulting in network I/O amplification, degraded query throughput, and higher API expenses. To resolve these challenges, we present RemoteANN, a vector search engine explicitly co-designed for cloud object storage across indexing and querying. To mitigate the dominant network I/O bottleneck, RemoteANN couples an Inverted File (IVF) index with RaBitQ quantization, further optimized by inter-cluster and intra-cluster data reordering for improved data locality. Building on this tailored data layout, RemoteANN's query engine combines cluster pruning, fine-grained Range-GET requests, request merging, and local NVMe SSD caching, dramatically reducing discrete storage requests and network transfer volume without sacrificing accuracy. To address the index construction bottleneck, we further develop QGKMeans, which substantially reduces construction latency without compromising clustering quality. Extensive evaluations on real-world datasets demonstrate that, compared with representative baselines, RemoteANN achieves up to a $5.9\times$ throughput speedup while issuing up to $16.1\times$ fewer object storage requests at 97% target recall.

0.25

ConStore: Search-Overlapped Prefetch and Co-Retrieval-Aware Content Storage for Disk-Based ANNS

cs.DB ·2026-10-15 ·Zhutao Zhuang, Nong Xiao, Zhiguang Chen, Yue Yu
similarity 0.72
Abstract

Disk-based approximate nearest-neighbor search (ANNS) supports retrieval-augmented generation (RAG), search, recommendation, and advertising over corpora that exceed memory capacity. Existing ANNS research often focuses on vector search at small top-K, whereas industrial-scale applications require larger retrieval sets. Fetching the corresponding content from storage remains comparatively underexplored. Our profiling across million- to billion-vector corpora shows that, at large K, content fetch latency can match or exceed vector-search latency and cannot be ignored in end-to-end retrieval. We present ConStore, a content storage engine combining two complementary techniques to reduce end-to-end retrieval latency. Speculative Inline Content Prefetch (SICP) commonly abstracts graph-based and cluster-based ANNS as progressive SSD I/O that refines an in-flight candidate queue. It prefetches content for stable leading candidates under a bounded I/O budget, overlapping content reads with search without changing the final top-K results. Co-Retrieval-Pattern-Aware Grouping (RPAG) uses query logs to place frequently co-retrieved documents in contiguous segments. Workload-Adaptive Segment Reorganization (WASR) adapts this layout to workload shifts by selectively regrouping segments under a bounded rewrite budget. Group Content Fetch (GCF) exploits this layout to coalesce per-document random reads into batched, page-aware I/O requests. SICP works independently of the content layout, while RPAG and GCF reduce fetch cost even without prefetching. Across three multi-hop QA workloads with K from 10 to 1600, ConStore reduces end-to-end retrieval latency over the best per-document-read baseline by up to 48% on DiskANN and 25% on SPANN. Separate experiments on 100M- and billion-vector indexes demonstrate SICP's applicability at larger scales.

0.40

Revisiting Index Performance under High Cache-Miss Penalties

cs.DB ·2026-11-16 ·Mathew M. Kim, Beomseok Nam
similarity 0.70
Abstract

Modern data-intensive applications often query very large datasets, making index performance critical. Recent index structures exploit the fine-grained access capabilities of emerging storage devices such as DCPMM and CXL. However, existing benchmarks typically evaluate indexes in isolation using saturated, closed-loop workloads that emphasize maximum throughput. Such workloads favor highly concurrent designs while overlooking the application work that follows an index lookup and competes for cache, memory bandwidth, and CPU resources. We present AuxBench - a microbenchmark that evaluates indexes as auxiliary access paths within larger application workloads. Using AuxBench, we evaluate four byte-addressable indexes under controlled post-lookup memory activity, concurrency, and request arrival patterns. Our experiments show that post-lookup memory activity can change the relative performance of competing indexes, that concurrency-oriented designs may lose their advantages when substantial application work is introduced, and that time-varying request arrivals can produce severe tail latency near saturation. These findings demonstrate why index-only benchmarks may not adequately predict performance in larger application workloads

0.20

Aker: Density-Aware Approximate Caching for Vector Search (Extended Version)

cs.DB ·2026-09-03 ·Sukjoon Oh, Minki Kang, Dohyun Kim, Baotong Lu, Jing Liu +3 more
top venue similarity 0.70
Abstract · Extended version of the paper published in Proceedings of the VLDB Endowment (PVLDB), Vol. 19, No. 10, pp. 2727-2740, 2026

Disk-based approximate nearest neighbor search (ANNS) incurs high I/O overhead due to frequent disk accesses during index traversal. Approximate caching, which reuses the results of past queries to serve future similar queries, offers a promising approach to bypass expensive disk searches. However, existing approaches suffer from two key limitations. First, their approximate hit predicates fail to simultaneously achieve high throughput and high accuracy, as they do not adapt to the varying local neighbor density in high-dimensional spaces. Second, they lack an effective refresh mechanism to maintain cache correctness under vector updates. We present Aker, an approximate cache for disk-based ANNS. Aker addresses these limitations through two core design choices. First, we introduce a per-query similarity threshold, where each cache entry maintains its own threshold that is dynamically adjusted based on observed cache hit patterns. This design enables Aker to adapt to neighborhood densities to preserve both efficiency and accuracy. Second, we propose del-consistency, a consistency model for ANNS caches that applies deletions eagerly and insertions lazily. Under this model, Aker implements a low-overhead refresh mechanism that bounds cache staleness and preserves high search accuracy. We integrate Aker into pgvector and evaluate it on representative workloads. Aker improves recall by up to 64 percentage points over prior solutions and increases QPS by up to 3.2x, while using 0.6x the memory of pgvector's shared buffers.

0.68

Cross-Modal Data Co-Locality for Heterogeneous Storage Systems

cs.DC ·2026-10-25 ·Abdullah Al-Mamun
similarity 0.69
Abstract

Distributed vector stores increasingly serve multimodal workloads whose representations are jointly accessed but independently partitioned and placed. As a result, cross-modal physical locality remains largely unoptimized. Multimodal queries can incur remote accesses and cross-tier data movement even when each modality's ANN search remains efficient. We present Coloc, a storage-management layer that makes cross-modal access locality a first-class data-layout signal. A Cross-Modal Access Graph combines semantic affinity, co-access, and temporal behavior. A movement-aware optimizer places frequently co-accessed vectors under capacity and topology constraints. A migration manager adapts placement as workloads shift by weighing locality gains against migration cost. A confidence-gated prefetcher hides remaining slow-tier latency. Coloc operates above existing ANN indexes without modifying embeddings, search, or retrieval semantics. We deploy Coloc on a multi-tier AWS testbed spanning GPU, NUMA-DRAM, NVMe, and S3. Coloc substantially reduces data movement and query latency while leaving ANN retrieval unchanged. Under a scheduled workload shift, its migration manager matches the locality of periodic global reorganization while moving 5.9x less data and completing 3.9x faster.

0.50

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

cs.DB cs.IR ·2026-10-30 ·Adithya Ramanatha, Sanskar S. Singh, Maya Ramanath
benchmark similarity 0.68
Abstract

Vector search has become a database operator with many physical implementations: different index families, build-time and search-time parameters, and compressed or disk-resident variants. Each trades cost against fidelity, the fraction of a query's exact top-k nearest neighbors that a configuration returns. Deployments nevertheless choose one configuration offline and use it for every query, so they are sized for their hardest queries and overpay for the rest. On a 5.8M-item LAION benchmark with four embedding models, running each query on the cheapest configuration that suffices for it would roughly halve the cost in a typical setting. Exploiting this requires predicting each configuration's fidelity before running it, which is hard because fidelity is defined by the very exact search that approximate indexes avoid. Relational optimizers solve the analogous problem for cardinality with offline synopses; we propose one for vector search. A fidelity synopsis divides the embedding space into cells around a set of landmarks and records, for every cell and configuration, how often that configuration met a fidelity target on a sample of queries. At query time, one nearest-landmark lookup yields a calibrated estimate for every configuration, and an optimizer chooses configurations so that the workload misses the target no more often than its requirement allows. We test the two premises the synopsis relies on, that fidelity varies smoothly across the embedding space and that its loss is specific to each configuration. Held to the same requirement a static deployment is built to meet, synopsis-guided selection lowers cost in all 16 combinations of model and query direction, to a median of 0.72x the static deployment, with a batched lookup of 21-32 microseconds per query. The saving persists against the best static choice among the same indexes, and within a single index at no extra memory.

0.09

PrairieFire: Igniting High-Throughput Updates in Large-Scale Approximate Nearest Neighbor Search

cs.DB ·2026-10-16 ·Yuchen Huang, Baiteng Ma, Yiping Sun, Xiao Chen, Rui Ma +7 more
similarity 0.68
Abstract

Arrays of modern NVMe SSDs are approaching memory in terms of bandwidth while offering much lower cost per gigabyte. Hence, approximate nearest neighbor search (ANNS) for billion-scale vectors in applications such as recommendation, search, and retrieval-augmented generation increasingly runs on SSD-based systems. Unfortunately, due to the limited update throughput of existing SSD-based solutions, the indexed corpus cannot keep pace with continuous modifications to data and embedding models, thus hindering broader deployment across more scenarios and larger scales. The bottleneck lies in CPU-intensive update paths, where foreground insertions incur frequent SSD accesses and background reassignments repeatedly relocate each vector, making high update throughput difficult to achieve even by exhausting available hardware. In this paper, using buffered updates and batched local rebuilds, we develop PrairieFire with cascaded adjustments, concurrency control, and CPU-GPU-SSD cooperation. These co-designs avoid frequent SSD accesses in foreground updates and heavy background reassignments, achieving high update throughput while maintaining excellent search performance. Evaluations show that, compared with state-of-the-art systems, PrairieFire can sustain approximately 3-35x update throughput while maintaining approximately 3-5x search throughput simultaneously. It also achieves approximately 1.5-8.7x cost efficiency. PrairieFire has been deployed in RedNote's production environments for two months, improving business metrics by higher freshness without frequent index rebuilds.

0.22

KVStream: Adaptive Parallel Storage Management for KV Caching in Large-Scale LLM Serving

cs.DC ·2026-10-22 ·Avinash Maurya, Jaiaid Mobin, Jie Ye, M. Mustafa Rafique, Franck Cappello +1 more
similarity 0.67
Abstract

Long-context LLM serving for agentic, coding, and document workloads reuses prefixes whose key-value (KV) cache outgrows GPU and host memory, putting storage I/O on the critical path of the inference step for retrieving prefixes. A single node-local NVMe absorbs all retrievals, while the parallel file system or cloud file store that nodes already mount carries almost no inference traffic. We cast prefix retrieval as aggregate-bandwidth scheduling across these tiers and present KVStream, a KV cache engine that batches a step's reads, defers writes behind the forward pass, replicates each chunk on every tier, and lets each tier adaptively claim the next unread chunks once it is free. Our performance model shows this routing attains the aggregate-bandwidth bound without prediction or tuning, whereas any static split misses it by a margin that grows as per-tier bandwidths drift or fluctuate. It also predicts that the time-to-first-token (TTFT) gain grows with load, as faster retrieval drains the queue, and disappears when host memory or arrival order keeps reuse in cache. Plugged into LMCache and evaluated on four models, six datasets, and up to 128 GPUs, KVStream retrieves within 5% of the bound, delivers up to 1.49$\times$ higher offline throughput than LMCache, and lowers mean TTFT by up to 6.1$\times$ under bursty arrivals.

0.06