# Quake: Adaptive Indexing for Vector Search

arXiv: https://arxiv.org/abs/2506.03437 · HTML: https://mlsanity.com/paper/2506.03437/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Vector search and ANN indexes, one of 15 directions in Retrieval-augmented generation.
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 3 Jun 2025.

## Placed in

- Retrieval-augmented generation / [Vector search and ANN indexes](https://mlsanity.com/rag/vector-search-and-ann-indexes/)

## Builds on (most cited first, 21 of 21)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba](https://mlsanity.com/paper/1803.02349/) (2018)
- [PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest](https://mlsanity.com/paper/2007.03634/) (2020)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [Monolith: Real Time Recommendation System With Collisionless Embedding Table](https://mlsanity.com/paper/2209.07663/) (2022)
- [Marius: Learning Massive Graph Embeddings on a Single Machine](https://mlsanity.com/paper/2101.08358/) (2021)
- [SPFresh: Incremental In-Place Update for Billion-Scale Vector Search](https://mlsanity.com/paper/2410.14452/) (2024)
- [Related Pins at Pinterest: The Evolution of a Real-World Recommender System](https://mlsanity.com/paper/1702.07969/) (2017)
- [Applying Deep Learning To Airbnb Search](https://mlsanity.com/paper/1810.09591/) (2018)
- [MariusGNN: Resource-Efficient Out-of-Core Training of Graph Neural Networks](https://mlsanity.com/paper/2202.02365/) (2022)
- [High-Throughput Vector Similarity Search in Knowledge Graphs](https://mlsanity.com/paper/2304.01926/) (2023)
- [SOAR: Improved Indexing for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2404.00774/) (2024)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [Locally-Adaptive Quantization for Streaming Vector Search](https://mlsanity.com/paper/2402.02044/) (2024)
- [DiskANN++: Efficient Page-based Search over Isomorphic Mapped Graph Index using Query-sensitivity Entry Vertex](https://mlsanity.com/paper/2310.00402/) (2023)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [MicroNN: An On-device Disk-resident Updatable Vector Database](https://mlsanity.com/paper/2504.05573/) (2025)
- [Cracking Vector Search Indexes](https://mlsanity.com/paper/2503.01823/) (2025)

## Built on by (most cited first, 8 of 8)

- [Pancake: Hierarchical Memory System for Multi-Agent LLM Serving](https://mlsanity.com/paper/2602.21477/) (2026)
- [Opal: Private Memory for Personal AI](https://mlsanity.com/paper/2604.02522/) (2026)
- [DiLaServe: High SLO Attainment Serving for Diffusion Language Models](https://mlsanity.com/paper/2606.29094/) (2026)
- [Efficient K-generalizable Learned Search](https://mlsanity.com/paper/2603.06159/) (2026)
- [HNSW with Accuracy Guarantees Using Graph Spanners](https://mlsanity.com/paper/2607.02338/) (2026)
- [QASP: Query-Adaptive Robust Vector Search Policy](https://mlsanity.com/paper/2607.29606/) (2026)
- [Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings](https://mlsanity.com/paper/2608.14648/) (2026)
- [A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval](https://mlsanity.com/paper/2609.19855/) (2026)

## Abstract (arXiv)

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.