PaperlayerView exact revision on arXiv

Source-linked AI summary

Quake: Adaptive Indexing for Vector Search

Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F. Ilyas, Theodoros Rekatsinas, Shivaram Venkataraman

arXiv:2506.03437v2cs.IR

TL;DR

Dynamic, skewed workloads make it challenging for existing indexes to maintain low-latency, high-recall vector search as data and access patterns evolve. Quake adapts a multi-level partitioned index and per-query scanning, and uses NUMA-aware parallelism. Across dynamic workloads, it reports lower search and update latency than state-of-the-art graph indexes.

  • Problem

    Existing indexes struggle to maintain low-latency, high-recall search as data and query patterns change under dynamic, skewed workloads.

    Source: §1 · p. 1, §2.1 · p. 2

  • Method

    Quake adapts hierarchical partitions using a query-cost model, adjusts per-query scanning from recall estimates, and uses NUMA-aware parallelism.

    Source: §1 · p. 2

  • Results

    Quake achieves 1.5-13× lower search latency than HNSW, DiskANN, and SVS, with 18-126× lower update latency across dynamic workloads.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The study finds Quake can minimize query latency while meeting a fixed recall target as queries and base vectors change over time.

    Source: §1 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

Dynamic, skewed vector workloads make it difficult to sustain low-latency, high-recall search as queries and data change. Quake adapts partitioning and per-query scanning, and reports lower search and update latency than state-of-the-art graph indexes on dynamic workloads.

1 Introduction

  • Quake’s central objective is minimizing query latency while meeting a fixed recall target as queries and base vectors change over time.Source: §1 · p. 2
  • Quake adapts hierarchical partitions by minimizing a query-latency cost model that tracks partition sizes and access frequencies.Maintenance identifies costly partitions for splitting or merging, and is reported stable and convergent to a local minimum of the cost model.Source: §1 · p. 2
  • Quake adjusts the number of partitions scanned per query using recall estimates from partition geometry and intermediate results, stopping when the target is met.This is intended to maintain recall targets while index structure and data change.Source: §1 · p. 2
  • Quake achieves 1.5-13× lower search latency than HNSW, DiskANN, and SVS, with 18-126× lower update latency across dynamic workloads.The evaluation also prepared a Wikipedia workload and a generator for configurable query and update patterns.Source: §1 · p. 2
  • APS matches an oracle’s nprobe across recall targets on SIFT1M with a 17-29% latency increase, and performs on par with or better than existing early-termination methods without offline tuning.Source: §1 · p. 2
  • Quake’s NUMA-aware processing shows linear scalability and high memory-bandwidth utilization on MSTURING100M, with 20× and 4× lower query latency than single-threaded and non-NUMA-aware configurations, respectively.Source: §1 · p. 2

2 Motivation and Challenges

Dynamic vector search combines approximate nearest-neighbor queries with evolving data, while skewed reads and writes challenge existing indexes. The section motivates Quake through the limitations of current approaches and identifies adaptation, online nprobe adjustment, and the partition-index performance gap as open challenges.

2 Motivation and Challenges

  • Vector databases use specialized ANN indexes for fast approximate queries, but shifting data and query patterns make it challenging to maintain performance and accuracy.Source: §2 · p. 2

2.1 Vector Search Workload

  • A vector-search workload combines top-k approximate queries with evolving data; maintaining a recall target and low latency as both change is difficult.Recall@k is defined using the intersection of returned and ground-truth vectors divided by k.Source: §2.1 · p. 2

2.2 Why Real-World Workloads are Hard

  • Wikipedia-12M exhibits skewed reads and writes, with activity concentrated on a small portion of the index and query traffic focused on popular entities.The workload is based on monthly pageview statistics and spans 103 months as the dataset grows from millions to tens of millions of vectors.Source: §2.2 · pp. 2–3, Figure 1 · p. 3

2.3 Shortcomings of Existing Approaches

  • Graph indexes incur costly update maintenance, while partitioned indexes can develop imbalanced partitions and rely on fixed nprobe, risking degraded latency or insufficient recall.Source: §2.3 · p. 3

2.4 Technical Challenges for Partitioned Indexes

  • Partitioned indexes need query-aware structural adaptation, online nprobe adjustment, and a way to address their query-latency gap with graph indexes; Quake targets these challenges with cost-based maintenance, recall estimation, and NUMA-aware parallelism.Source: §2.4 · pp. 3–4

D. Modify Index

Quake uses a multi-level partitioned index and adapts its structure to workload access patterns. Its architecture connects search statistics, cost-guided maintenance, and NUMA-aware query processing.

D. Modify Index

  • Search scans selected partitions, updates access-pattern metadata, and informs maintenance decisions in a continuous online process alongside inserts and deletes.The architecture depicts this loop as APS selection, metadata tracking, cost-based action selection, and index modification.Source: Figure 2
  • The multi-level index partitions vectors at the lowest level and recursively partitions centroids above, enabling top-down search while limiting centroid-scanning overhead.Inserts and deletes modify the lowest-level partitions; maintenance can then reshape the index.Source: D. Modify Index · p. 4
  • A cost model uses partition sizes and access patterns to choose partitions for splitting or merging, with maintenance frequency configurable.Frequently accessed or large partitions are candidates for splitting; infrequently accessed or small ones may be merged.Source: D. Modify Index · p. 4
  • Quake distributes partitions across NUMA nodes and uses affinity-based scheduling and within-node work stealing to reduce remote memory access.The stated aim is to improve memory-bandwidth use and lower query latency.Source: D. Modify Index · p. 5

4 Adaptive Incremental Maintenance

Quake estimates the query-latency cost of partitions and uses that estimate to select and verify index-maintenance actions. The workflow applies beneficial changes bottom-up while guarding against cost increases.

4 Adaptive Incremental Maintenance

  • Quake’s adaptive incremental maintenance uses a cost model to estimate partition contributions to query latency and guide maintenance decisions.The maintenance methodology covers available actions, their estimated cost deltas, and a decision workflow.Source: §4 · p. 5

4.1 Cost Model

  • The cost model sums partition latency contributions driven by partition size and access frequency, balancing vector-scan cost against centroid-scanning overhead.Frequently accessed partitions contribute more to total cost; finer partitions can reduce vector scans but increase centroid overhead.Source: §4.1 · p. 5

4.2 Conducting Maintenance

  • Maintenance proceeds through estimate, verify, and commit or reject phases, using predicted cost changes to decide whether to retain an action.Actions are applied only when the cost change is below −τ, a non-negative tunable threshold.Source: §4.2 · p. 5, §4.1 · p. 5

4.2.1 Maintenance Actions

  • Splits divide hot or oversized partitions with k-means and refine nearby assignments; merges can delete cold, small partitions but may increase receiver sizes.The hierarchy can also add or remove top levels when centroid counts cross configured thresholds.Source: §4.2.1 · pp. 5–6

4.2.2 Cost Deltas

  • Split and merge actions are scored by predicted cost deltas, with lightweight estimates relying on balanced splits and proportional access scaling.After a tentative action, actual sizes and merge receivers are measured and the cost change is reevaluated before commitment.Source: §4.2.2 · p. 6

4.2.3 Decision Workflow

  • The bottom-up workflow tracks partition sizes and sliding-window access counts, estimates actions, verifies their actual size effects, then commits or rejects them.Each level uses the same cost-decrease guard before the workflow propagates upward.Source: §4.2.3 · p. 6

4.2.4 Example Maintenance Workflow

  • In the example, equally sized and accessed partitions are tentatively split using balanced-child and equal-traffic estimates, while the observed split outcomes can differ.P1 splits 250/250, whereas P2 splits 450/50, prompting verification of the estimates.Source: §4.2.4 · pp. 6–7

3. Decide

The verification step blocks an imbalanced split that would otherwise increase query latency.

3. Decide

  • Verification blocks an imbalanced split that would otherwise increase query latency.Source: §3 · p. 7

5 Adaptive Partition Scanning (APS)

Adaptive Partition Scanning (APS) estimates where a query’s nearest neighbors are likely to lie and scans partitions until its recall target is met. Its probability estimates use partition geometry and are updated as search results change.

5 Adaptive Partition Scanning (APS)

  • APS estimates partition probabilities from the fraction of the query-centered hypersphere intersecting each partition, under a uniform-density assumption.The hypersphere radius is updated from the current observed k-th neighbor, and candidate partitions are approximated as half-spaces.Source: §5 · p. 7, Figure 3 · p. 7

5.1 APS algorithm

  • APS scans the nearest partition first, then scans remaining candidates in descending probability order until cumulative estimated recall exceeds the target.It updates the radius and recomputes probabilities when the radius shrinks beyond a relative threshold; higher levels use a fixed 99% target.Source: §5.1 · pp. 7–8
  • 29% lower query latency on SIFT1M resulted from precomputing beta-function values and recomputing partition probabilities only after a sufficient radius change, without sacrificing recall.Table 2 compares APS variants by mean single-threaded query latency and recall at a 90% recall target.Source: §5.1 · p. 8, Table 2 · p. 8

6 Quake Implementation

Quake combines NUMA-aware data placement and query scheduling with Adaptive Partition Selection (APS), coordinating local partition scans and recall-based termination. This design aligns work with memory locality while avoiding scans beyond the requested recall threshold.

NUMA Data Placement and Query Processing

  • Quake distributes partitions across NUMA nodes and schedules scans on the nodes where their data resides, reducing remote memory access.Partitions are assigned round-robin; affinity binds partitions to cores to support cache utilization and load balancing as partitions are added.Source: §6 · p. 8

NUMA-Aware Query Execution with APS

  • APS selects partitions dynamically for the query’s recall target, while NUMA-aware workers scan local partitions and a main thread coordinates execution.The main thread merges partial results and terminates workers once estimated recall reaches the target.Source: §6 · pp. 8–9
  • Query processing periodically merges worker results and estimates recall, stopping the remaining scans when the target is met.Workers compute distances within their local partitions and update local partial results.Source: §6 · pp. 8–9

Implementation Details

  • Quake’s implementation combines Faiss, PyTorch, and SimSIMD primitives with a concurrent queue and a Python workload-generation and evaluation framework.The implementation is 7,500 lines of C++ and provides a Python API.Source: §6 · p. 9

7 Experiments

Quake is evaluated on real-world and synthetic workloads, including dynamic traces with skewed reads and updates. Across dynamic workloads it reduces search and update latency against graph-index baselines, while experiments also examine multi-query performance, NUMA scaling, adaptive recall selection, and maintenance components.

7 Experiments

  • 1.5–13× lower search latency and 18–126× lower update latency: Quake achieves the lowest search time across dynamic workloads compared with state-of-the-art graph indexes.The evaluation includes HNSW, DiskANN, and SVS.Source: §7 · p. 9

7.1 Workloads and 7.2 Experimental Setup

  • The evaluation spans Wikipedia-12M, OpenImages-13M, and MSTuring workloads, with search-only and dynamic traces; its main setup targets 90% recall for k = 100.Wikipedia-12M grows from 1.6 million to 12 million pages over 103 updates, while OpenImages tests inserts and deletes in a sliding window; systems use 16 threads for updates and maintenance.Source: §7.1 · p. 9, §7.2 · pp. 9–10

7.3 End-to-End Evaluation

  • On WIKIPEDIA-12M, Quake-MT takes 1.53 hours for searches versus 12 hours for DiskANN, the strongest graph-based method; on OPENIMAGES-13M, it is 7.3× faster than DiskANN.On MSTURING10M-IH, Quake-MT is 1.5× faster than DiskANN, while single-threaded Quake is 2.6× slower.Source: §7.3 · p. 10
  • On static MSTURING10M-RO, SVS searches in .33 hours versus .63 hours for Quake-MT; on WIKIPEDIA-12M, Quake maintains near-90% recall and stable latency as partitions evolve.Quake and LIRE increase partition counts by 2.5× and 10×, respectively, while DeDrift’s latency increases significantly; disabling NUMA-aware multithreading raises query latency 6×.Source: §7.3 · pp. 10–11, Figure 4 · p. 11, Table 4 · p. 11

7.4 Multi-Query Processing

  • At a batch size of 10,000 queries, Quake achieves a 6.7× speedup over FaissIVF and SCANN and a 1.8× speedup over DiskANN.Quake scans each partition once per batch, unlike FaissIVF and SCANN, which scan partitions individually per query.Source: §7.4 · p. 12, Figure 5 · p. 12

7.5 Scalability

  • At 64 workers on MSTURING100M, NUMA-aware processing reaches 6ms latency and 200GBps peak scan throughput.The NUMA-disabled configuration performs best at 28ms around eight workers; sorting, memory allocation, and coordination prevent full bandwidth saturation.Source: §7.5 · p. 12, Figure 6 · p. 12

7.6 Comparison with Early Termination Methods

  • APS provides near-optimal performance without offline tuning, matching or exceeding the compared early-termination baselines.On SIFT1M, APS latency is within 30% of the oracle across recall targets; Fixed tuning can take up to 424s.Source: §7.6 · pp. 12–13, Table 5 · p. 12

7.7 Multi-Level Recall Estimation and 7.8 Maintenance Ablation

  • At a 90% base recall target, lowering the upper-level target from 99% to 80% reduces overall recall from 91.0% to 84.1%; two-level indexing cuts latency from 7.86ms to 5.08ms.In the dynamic SIFT1M maintenance ablation, full Quake has the lowest search cost (86s); removing rejection drops recall to 66%.Source: §7.7 · p. 13, §7.8 · p. 13

8 Discussion

Quake fixes most system parameters across workloads, while describing extensions that would require changes to its cost model and APS logic.

8.1 Setting System Parameters

  • The initial candidate fraction fM trades recall risk against initial-scan latency, while worker threads are best set to the physical-core count.Quake uses fM values between 1% and 10%; for large problems, it scales linearly with thread count until memory bandwidth saturates.Source: §8.1 · p. 14
  • Quake’s maintenance threshold τ is set to 250ns; lower values increase maintenance cost and may cause over-splitting, while higher values can allow imbalance to persist.The split access scaling parameter α is fixed at 0.9, and refinement uses one iteration over the 50 nearest partitions.Source: §8.1 · p. 14
  • Quake fixes most parameters across workloads; only the initial candidate fraction fM and maintenance threshold τ are identified as tuning candidates.The defaults are sufficient for the evaluated workloads.Source: §8.1 · pp. 13–14

8.2 Deployment Considerations

  • Quake’s design can extend to other hardware and use cases through changes to the cost model and APS logic, but those extensions are reserved for future work.The discussion identifies heterogeneous devices, distributed environments, compression, filters, and concurrent operations as extension areas.Source: §8.2 · p. 14

9 Conclusion

Quake reduces query latency on dynamic, skewed workloads while meeting recall targets. Its evaluation reports efficient indexing and updates relative to graph indexes, alongside query-latency reductions relative to partitioned indexes.

9 Conclusion

  • Quake minimizes query latency while meeting recall targets on dynamic workloads with skewed access patterns.The conclusion reports lower query latency than partitioned indexes such as Faiss and SCANN, and more efficient indexing and updates than graph indexes such as SVS, HNSW, and DiskANN, while matching or reducing query latency.Source: §9 · p. 14

A Artifact Appendix

The artifact provides setup instructions and experiments for reproducing and validating Quake’s core findings, with some experiments requiring suitable hardware.

Abstract

  • The artifact provides an experimental setup intended to reproduce key Quake results.The README contains full details.Source: Abstract · p. 17

Scope

  • The artifact supports validation of findings on Adaptive Partition Scanning, NUMA-aware searching, and maintenance policies.Specific experiments are listed in the artifact’s README.Source: Scope · p. 17

Hosting

  • The artifact is hosted in the Quake repository’s osdi2025 branch, and the instructions specify using its latest commit.The passage provides the repository location.Source: Hosting · p. 17

Requirements

  • The artifact requires Python 3.9+ and Conda and was tested on Ubuntu 22.04; NUMA evaluations require a NUMA machine for meaningful reproduction.The install script lists system-level dependencies.Source: Requirements · p. 17

A.1 Installation

  • Installation can use either the comprehensive install.sh setup or a Quake-only Conda environment.The artifact README provides detailed installation instructions.Source: §A.1 · p. 17

A.2 Experiment Workflow

  • Experiments run through experiment_runner.py from the repository root and typically download and prepare datasets when they are not local.The passage gives a kick-the-tires command example.Source: §A.2 · p. 17
  • Experiment outputs, including CSV files and plots, are saved to a directory identified in console output.The README documents command parameters, examples, and available experiment configurations.Source: §A.2 · p. 17

Related papers

Loading 2506.03437v2…