Source-linked AI summary
Cracking Vector Search Indexes
Vasilis Mageirakos, Bowen Wu, Gustavo Alonso
TL;DR
Brute-force search and smaller IVFlat indexes enable fast discovery but struggle at scale with higher query response times, while much private unstructured data in data lakes remains untapped. CrackIVF starts as a small partition-based ANN index and incrementally adds or refines partitions in response to incoming queries. CrackIVF can process over 1 million queries before conventional methods finish building an index, achieving 10-1000x faster initialization times.
Problem
Brute-force search and smaller IVFlat indexes enable fast discovery but struggle at scale with higher query response times, while much private unstructured data in data lakes remains untapped.
Source: §1 · pp. 1–2Method
CrackIVF starts as a small partition-based ANN index and incrementally adds or refines partitions in response to incoming queries.
Source: §1 · p. 2Results
CrackIVF can process over 1 million queries before conventional methods finish building an index, achieving 10-1000x faster initialization times.
Source: §7 · p. 12Takeaways & Limitations
The approach is particularly effective for cold data, infrequently accessed datasets, and rapid access to unseen data.
Source: §7 · p. 12The cost model treats execution time as linear and overlooks system-level nonlinearities such as caching, NUMA constraints, and SIMD optimizations.
Source: §4.3 · p. 7
Abstract
from arXiv · showhide
Retrieval Augmented Generation (RAG) uses vector databases to expand the expertise of an LLM model without having to retrain it. The idea can be applied over data lakes, leading to the notion of embedding data lakes, i.e., a pool of vector databases ready to be used by RAGs. The key component in these systems is the indexes enabling Approximated Nearest Neighbor Search (ANNS). However, in data lakes, one cannot realistically expect to build indexes for every dataset. Thus, we propose an adaptive, partition-based index, CrackIVF, that performs much better than up-front index building. CrackIVF starts answering as a small index, and only expands to improve performance as it sees enough queries. It does so by progressively adapting the index to the query workload. That way, queries can be answered right away without having to build a full index first. After seeing enough queries, CrackIVF will produce an index comparable to those built with conventional techniques. CrackIVF can often answer more than 1 million queries before other approaches have even built the index, achieving 10-1000x faster initialization times. This makes it ideal for cold or infrequently used data and as a way to bootstrap access to unseen datasets.
1 INTRODUCTION
Embedding data lakes could make underlying datasets searchable for RAG, but building indexes across diverse datasets and unknown workloads is costly. CrackIVF adapts an index as queries arrive, aiming to answer immediately while improving with workload growth.
1 INTRODUCTION
- Embedding data lakes store unstructured data with vector representations and expose it through a pool of vector databases for retrieval and question answering.RAG relies on ANN indexes to retrieve information absent from an LLM’s training data.Source: §1 · p. 1
- Index selection must balance costly upfront construction against brute-force search that does not scale, while future query volume and workload are unknown.The best index varies with query volume: large IVFlat configurations take longer to build, while brute force and smaller IVFlat indexes have higher response times at scale.Source: §1 · pp. 1–2
- Earlier adaptive approaches do not scale to embedding dimensionalities or support typical RAG k-NN queries, while AV-Tree targets short-lived workloads of up to one thousand queries.AV-Tree is an exact, tree-based index, whereas RAG-scale workloads rely on approximate search for lower response time and greater scalability.Source: §1 · p. 2
- CrackIVF incrementally adapts a partition-based ANN index to growing workloads, answering queries along the way and asymptotically matching or surpassing pre-built indexes.Queries and their locally visited regions guide new partitions and refinements; the paper evaluates the static setting without data or query distribution shifts.Source: §1 · p. 2
- Across benchmarks, CrackIVF consistently outperforms pre-built partition-based indexes, and in some cases processes 1 million queries before baseline indexes finish building, while achieving several orders of magnitude lower startup time.It converges to near-optimal query response time and consistently remains near the Pareto frontier of minimum cumulative time across the number of queries posed.Source: §1 · p. 2
2 BACKGROUND
Nearest-neighbor search seeks the closest vectors to a query, but exact methods can become impractical in high dimensions. IVF indexes trade exactness for speed by scanning selected partitions rather than the full dataset.
2 BACKGROUND
- Approximate nearest-neighbor search trades a small retrieval error for runtime or memory gains when exact search becomes impractical for high-dimensional or large datasets.Brute-force exact search scans every point with O(|P| · d) complexity; approximation quality can be measured by the fraction of exact top-k vectors recovered.Source: §2 · p. 2
- Partition-based IVF divides vectors into disjoint groups, probes the nearest partitions, and exhaustively scans only their points, so neighbors in skipped partitions may be missed.The index typically uses k-means representatives trained on a subset, assigns each point to its nearest representative, and stores assignments in an inverted file.Source: §2 · p. 2
- FAISS is a widely adopted IVF implementation and serves as the basis for CrackIVF and the paper’s baseline.The passage identifies FAISS as Meta’s library implementation.Source: §2 · p. 2
3 SOLUTION OVERVIEW
CrackIVF extends IVF with incremental construction that follows query activity rather than building uniformly across the vector space. It starts small, answers queries immediately, and selectively grows and refines the index as workload demands increase.
3 SOLUTION OVERVIEW
- Embedding-lake deployments need indexes that balance construction and memory overhead with query throughput, but even efficient IVF construction is paid upfront before workload volume is known.The passage contrasts IVF’s smaller footprint with HNSW’s higher QPS and much higher memory, then motivates incremental IVF construction.Source: §3 · p. 2
3.1 Cracking in high dimensions
- In high dimensions, cracking after every query is costly because moving vectors between IVF lists incurs random access, data movement, and possible linear-time compaction without eventual locality benefits.This makes it difficult to minimize query latency while continuously improving the index and cumulative time.Source: §3.1 · p. 3
3.2 Outline of the approach
- Index construction separates into adding partitions and refining their locations with k-means; query access is skewed, so uniform partitioning and global refinement can waste effort in rarely accessed regions.The approach can first increase partition count up to a limit, then refine locations; on open datasets, 80% of queries access 60% of partitions, with the most- and least-accessed partitions differing by over 50 times.Source: §3.2 · p. 3
- CrackIVF reuses search computations by treating queries as candidate centroids and refining locally visited regions, directing build operations toward accessed regions.More frequently queried partitions are proportionally more likely to be cracked or refined.Source: §3.2 · p. 3
3.3 Outline of the solution
- CrackIVF begins as a small, coarse IVF index and adds partitions in accessed regions through independent CRACK and REFINE operations.CRACK operations are buffered until beneficial, while REFINE operations run eagerly but infrequently; heuristic rules choose where to build, and a cost-based budget governs when, growing with cumulative runtime.Source: §3.3 · p. 4
4 CRACK-IVF
CrackIVF answers queries while incrementally reorganizing its partition-based index through query-driven CRACK and REFINE operations. Heuristics choose where to reorganize, while a cost-based budget controls when build operations run.
4.1 Algorithm and Operations
- CRACK buffers good query-centered partition candidates for later commitment, while REFINE eagerly applies local K-means to improve the region visited during search.SEARCH returns nearest-neighbor results and the visited region; CRACK commits new partitions and reassigns points, whereas REFINE updates assignments and storage locally.Source: §4.1 · pp. 4–5
- A dynamic state tracks buffered changes separately from the committed index, allowing buffered cracks to be re-evaluated after REFINE changes assignments.The rollback procedure retains only cracks that remain good before committing them.Source: §4.1 · pp. 5–6
4.2 Where to apply build operations?
- CrackIVF classifies incoming queries as crack candidates and visited regions as refine candidates, using heuristics to favor frequently accessed regions needing more partitions or better clustering.Crack candidates are accepted by default but can be rejected; refinement considers local imbalance and global partition-size patterns, and the rules are not claimed to be exhaustive.Source: §4.2 · p. 6
4.3 When to apply build operations?
- Build operations run only when their estimated costs fit the indexing-time budget; with α = 0.5, at most 50% of total runtime is allocated to building.CRACK also waits until buffered candidates exceed 20% of the current index size.Source: §4.3 · p. 7
- A first-order linear cost model predicts build time from kernel computation and data movement, but assumes linear execution costs and must be refitted when hardware changes.The reported model explains 40–95% of variance across tests; measured build and search times are used in the budget constraint.Source: §4.3 · p. 7
5 EXPERIMENTS
Across the experiments, CrackIVF reaches near-minimum cumulative time across query scales while converging to near-optimal query response time. Its adaptive build and search costs depend on workload and control settings, with dataset-dependent effects in the ablations.
5.1 Comparison with AV-Tree:
- 3.7x faster than AV-Tree at the end of the 1M-query SIFT1M trace, CrackIVF trails AV-Tree for the first 10 queries, while AV-Tree continues to outperform up to 1000 queries.Both cracking-based indexes vastly outperform IVF indexes at low query scales; CrackIVF continues to benefit through 1 million queries.Source: §5.1 · pp. 8–9, Table 3 · p. 8
5.2 Does CrackIVF improve over time?
- CrackIVF-END is consistently at or near the Pareto frontier across tested datasets, and on Last.fm it achieves ≈50% higher QPS at Recall@10 = 0.9 than any other index.Last.fm’s high query skew lets CrackIVF partition the accessed space with relatively few cracks; search improves over time, while CRACK and REFINE operations account for less than 0.03% and 0.6% of the trace, respectively.Source: Figure 3 · p. 8, §5.2 · p. 9
5.3 Does CrackIVF Minimize Cumulative Time?
- ≈1000x lower initialization time than larger indexes, while CrackIVF answers 100K to 1M queries before comparable indexes finish building.On SIFT10M, initialization is ≈100x lower than IndexFlat(5000) and almost 1000x lower than IndexFlat(16000), yet CrackIVF answers 100k and 1M queries respectively before those indexes finish building.Source: §5.3 · p. 9, Figure 4 · p. 9
5.4 Does CrackIVF Reduce Total Distance Computations for Build Operations?
- After convergence, CrackIVF’s final build distance computations can be orders of magnitude lower than larger IVF indexes, with similar final QPS-Recall performance.On Glove, computations increase faster because REFINE regions contain more points and cracks; total cost is still almost an order of magnitude below the largest IVF index.Source: §5.4 · p. 9, Figure 5 · p. 10
5.5 Control Mechanisms Ablation Study
- Without the “where” heuristics, random crack additions yield only slightly better performance than the initial index; with heuristics, CrackIVF converges to the Pareto-optimal QPS-Recall trade-off.The compared runs use the same number and order of queries.Source: §5.5 · p. 10, Figure 6 · p. 10
- With the “when” budget disabled, building dominates total time; enabling it balances search and build costs on the same 100k-query trace.Without budgeting, CrackIVF cracks and refines after almost every query until reaching 16,000 partitions; the default α = 0.5 caps build operations at 50% of total time.Source: §5.5 · p. 10, Figure 7 · p. 10
- Across 48 single-parameter edge cases, 15 noticeably affected the final index; the two-rule heuristics make the model robust to changing one parameter, but effects remain dataset-dependent.Setting min_pts to 32 negatively affected all six datasets; disabling the size_prctl decision rule greatly affects the final index and prevents convergence to the optimal state.Source: §5.5 · p. 11
- The experiments recommend BruteForce until a dataset surpasses 10–100 queries, then CrackIVF when it is likely to receive more, despite CrackIVF’s slight memory and runtime overhead.The default parameter values provide robust performance, though the authors did not pursue dataset-specific tuning.Source: §5.5 · p. 12
6 RELATED WORK
The related work spans vector database systems and ANN index families, then distinguishes CrackIVF’s query-triggered construction setting from adaptive indexes for specialized data and index maintenance under updates or distribution shifts.
Vector Databases
- Vector database systems support efficient ANN search for RAG, semantic search, recommendation, and product search, with extensions for filtered, sparse, and hybrid search.Many relational engines are also incorporating vector search.Source: §6 · p. 12
Vector Search Indexes
- IVF offers a trade-off among index build time, search performance, and memory overhead, while graph-based indexes achieve state-of-the-art QPS–Recall performance at higher construction and memory cost.The paper focuses on IVF and notes that cracking could be generalized to other ANN indexes, though each requires solving unique challenges.Source: §6 · p. 12
Adaptive indexes for specialized data types
- Adaptive indexes for time-series similarity search are specialized to sequential data, whereas the paper focuses on ANN methods broadly applicable across modalities lacking sequential relationships.The passage identifies specialized adaptive indexes as relevant for embedding lakes when datasets have inherent sequential dependencies, including energy, weather, financial data, audio, and video.Source: §6 · p. 12
ANN index maintenance
- ANN maintenance methods address updates or distribution shifts, but the paper distinguishes CrackIVF’s static setting, where index operations are triggered solely by queries to incrementally construct the index.Prior methods use incoming updates or shifts to trigger maintenance; CrackIVF follows the principle that maintenance is a byproduct of query processing, not updates.Source: §6 · p. 12
7 CONCLUSION
CrackIVF is a cracking-based IVF index for ANNS over embedding lakes that adapts as query workloads grow. It can process over 1 million queries before conventional methods finish building an index, with 10–1000x faster initialization times.
7 CONCLUSION
- Over 1 million queries can be processed before conventional methods finish building an index, with 10–1000x faster initialization times.The conclusion identifies cold data, infrequently accessed datasets, and rapid access to unseen data as particularly effective settings.Source: §7 · p. 12