Quake: Adaptive Indexing for Vector Search

• URL: http://arxiv.org/abs/2506.03437v2
• Date: Fri, 06 Jun 2025 19:58:25 GMT
• Title: Quake: Adaptive Indexing for Vector Search
• Authors: Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F. Ilyas, Theodoros Rekatsinas, Shivaram Venkataraman,
• Abstract summary: We introduce Quake, an adaptive indexing system that maintains low latency and high recall in dynamic environments.<n>Our evaluation shows that on dynamic workloads, Quake achieves query latency reductions of 1.5-38x and update latency reductions of 4.5-126x compared to state-of-the-art indexes.
• Score: 9.530779665725715
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Vector search, the task of finding the k-nearest neighbors of a query vector against a database of high-dimensional vectors, underpins many machine learning applications, including retrieval-augmented generation, recommendation systems, and information retrieval. However, existing approximate nearest neighbor (ANN) methods perform poorly under dynamic and skewed workloads where data distributions evolve. We introduce Quake, an adaptive indexing system that maintains low latency and high recall in such environments. Quake employs a multi-level partitioning scheme that adjusts to updates and changing access patterns, guided by a cost model that predicts query latency based on partition sizes and access frequencies. Quake also dynamically sets query execution parameters to meet recall targets using a novel recall estimation model. Furthermore, Quake utilizes NUMA-aware intra-query parallelism for improved memory bandwidth utilization during search. To evaluate Quake, we prepare a Wikipedia vector search workload and develop a workload generator to create vector search workloads with configurable access patterns. Our evaluation shows that on dynamic workloads, Quake achieves query latency reductions of 1.5-38x and update latency reductions of 4.5-126x compared to state-of-the-art indexes such as SVS, DiskANN, HNSW, and SCANN.

Related papers

• HAKES: Scalable Vector Database for Embedding Search Service [16.034584281180006]
  We build a vector database that achieves high throughput and high recall under concurrent read-write workloads.<n>Our index outperforms index baselines in the high recall region and under concurrent read-write workloads.<n>namesys is scalable and achieves up to $16times$ higher throughputs than the baselines.
  arXiv  Detail & Related papers  (2025-05-18T19:26:29Z)
• vCache: Verified Semantic Prompt Caching [75.87215136638828]
  This paper proposes vCache, the first verified semantic cache with user-defined error rate guarantees.<n>It employs an online learning algorithm to estimate an optimal threshold for each cached prompt, enabling reliable cache responses without additional training.<n>Our experiments show that vCache consistently meets the specified error bounds while outperforming state-of-the-art static-threshold and fine-tuned embedding baselines.
  arXiv  Detail & Related papers  (2025-02-06T04:16:20Z)
• Accelerating Retrieval-Augmented Generation [15.179354005559338]
  Retrieval-Augmented Generation (RAG) involves augmenting large language models with information retrieved from an external knowledge source, such as the web.<n>IKS is a type-2 CXL device that implements a scale-out near-memory acceleration architecture with a novel cache-coherent interface between the host CPU and near-memory accelerators.
  arXiv  Detail & Related papers  (2024-12-14T06:47:56Z)
• SPFresh: Incremental In-Place Update for Billion-Scale Vector Search [19.245438083030006]
  We introduce SPFresh, a system that supports in-place vector updates. At the heart of SPFresh is LIRE, a lightweight incremental rebalancing protocol. With LIRE, SPFresh provides superior query latency and accuracy to solutions based on global rebuild.
  arXiv  Detail & Related papers  (2024-10-18T13:24:18Z)
• RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval [24.472784635757016]
  RetrievalAttention is a training-free approach to both accelerate attention computation and reduce GPU memory consumption.<n>We show that RetrievalAttention achieves near full attention accuracy while only requiring access to 1--3% of the data.
  arXiv  Detail & Related papers  (2024-09-16T17:59:52Z)
• Locally-Adaptive Quantization for Streaming Vector Search [1.151101202055732]
  Locally-Adaptive Vector Quantization (LVQ), a highly efficient vector compression method, yields state-of-the-art search performance for non-evolving databases. We introduce two improvements of LVQ: Turbo LVQ and multi-means LVQ that boost its search performance by up to 28% and 27%. Our studies show that LVQ and its new variants enable blazing fast vector search, outperforming its closest competitor by up to 9.4x for identically distributed data.
  arXiv  Detail & Related papers  (2024-02-03T05:43:39Z)
• Sparse-DySta: Sparsity-Aware Dynamic and Static Scheduling for Sparse Multi-DNN Workloads [65.47816359465155]
  Running multiple deep neural networks (DNNs) in parallel has become an emerging workload in both edge devices. We propose Dysta, a novel scheduler that utilizes both static sparsity patterns and dynamic sparsity information for the sparse multi-DNN scheduling. Our proposed approach outperforms the state-of-the-art methods with up to 10% decrease in latency constraint violation rate and nearly 4X reduction in average normalized turnaround time.
  arXiv  Detail & Related papers  (2023-10-17T09:25:17Z)
• Similarity search in the blink of an eye with compressed indices [3.39271933237479]
  Graph-based indices are currently the best performing techniques for billion-scale similarity search. We present new techniques and systems for creating faster and smaller graph-based indices.
  arXiv  Detail & Related papers  (2023-04-07T23:10:39Z)
• Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching [72.50506500576746]
  We propose a novel caching paradigm, that we named approximate-key caching. While approximate cache hits alleviate DL inference workload and increase the system throughput, they however introduce an approximation error. We analytically model our caching system performance for classic LRU and ideal caches, we perform a trace-driven evaluation of the expected performance, and we compare the benefits of our proposed approach with the state-of-the-art similarity caching.
  arXiv  Detail & Related papers  (2021-12-13T13:49:11Z)
• When Liebig's Barrel Meets Facial Landmark Detection: A Practical Model [87.25037167380522]
  We propose a model that is accurate, robust, efficient, generalizable, and end-to-end trainable. In order to achieve a better accuracy, we propose two lightweight modules. DQInit dynamically initializes the queries of decoder from the inputs, enabling the model to achieve as good accuracy as the ones with multiple decoder layers. QAMem is designed to enhance the discriminative ability of queries on low-resolution feature maps by assigning separate memory values to each query rather than a shared one.
  arXiv  Detail & Related papers  (2021-05-27T13:51:42Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  Methods have to trade between obtaining high accuracy while maintaining load balance and scalability in distributed settings. We propose a novel approach called IRLI, which iteratively partitions the items by learning the relevant buckets directly from the query-item relevance data. We mathematically show that IRLI retrieves the correct item with high probability under very natural assumptions and provides superior load balancing.
  arXiv  Detail & Related papers  (2021-03-17T23:13:25Z)
• MS-RANAS: Multi-Scale Resource-Aware Neural Architecture Search [94.80212602202518]
  We propose Multi-Scale Resource-Aware Neural Architecture Search (MS-RANAS) We employ a one-shot architecture search approach in order to obtain a reduced search cost. We achieve state-of-the-art results in terms of accuracy-speed trade-off.
  arXiv  Detail & Related papers  (2020-09-29T11:56:01Z)
• Latency-Aware Differentiable Neural Architecture Search [113.35689580508343]
  Differentiable neural architecture search methods became popular in recent years, mainly due to their low search costs and flexibility in designing the search space. However, these methods suffer the difficulty in optimizing network, so that the searched network is often unfriendly to hardware. This paper deals with this problem by adding a differentiable latency loss term into optimization, so that the search process can tradeoff between accuracy and latency with a balancing coefficient.
  arXiv  Detail & Related papers  (2020-01-17T15:55:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.