CS Paper Radar

Recast: Refinement-Centered Approximate Nearest Neighbor Search Optimized for Storage

Zehai Yang, Fengyi Tao, Wenzhuo Dong, Shimin Chen

cs.DB ·submitted 2026-11-02 08:46 UTC · v1

Abstract

Large-scale ANNS systems often exploit storage in addition to DRAM for supporting vector search. The central question is how to divide the work between memory and storage for achieving both high query throughput-recall and good index maintenance performance. Existing storage-optimized ANNS paradigms fall short of providing a complete answer: disk-resident graph indexes have difficulty in supporting efficient vector deletions, while posting-list systems often incur more disk I/Os for queries. In this paper, we introduce a refinement-centered paradigm for storage-optimized ANNS systems. We propose Recast as a concrete design of this paradigm. Recast stores raw vectors on disk and keeps an IVF index with our RecastQ quantization encoding in memory. For an ANNS query, Recast selects nprobe inverted lists and performs SIMD-based FastScan on their RecastQ codes to identify refinement candidates in memory. It then retrieves candidate vectors from disk, computes exact distances, and refines the top-K result. To reduce disk I/Os, RecastQ computes uncertainty intervals containing true distances with high probability. Our QUIC policy selects a minimal refinement set based on these intervals, minimizing candidate-retrieval I/Os. Both the on-disk raw vectors and the in-memory IVF structure support insertions and deletions. Experiments on real-world data sets show that Recast processes batched insertions and deletions 3.10-37.27x faster than SPFresh and OdinANN, while its QPS at 0.99 recall changes by at most 6.9% after updating 50% of the corpus. For static queries at 0.99 recall, Recast achieves 1.56-2.01x the QPS of the strongest baseline with the matched memory budget on each data set, while requiring 1.22-6.75x less external storage than the evaluated systems. At matched in-memory space, RecastQ also provides a better Recall-refinement frontier than RaBitQ.

Closest papers

Nearest neighbours by meaning across the whole index.

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.80
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

RaBitQ-SSD: Split Codes and Pipelined I/O for SSD-Resident Vector Search

cs.DB ·2026-10-02 ·Yuexuan Xu, Jianyang Gao, Michael Norris, Alibek Zhakubayev, Pankaj Singh +3 more
similarity 0.77
Abstract

SSD-resident approximate nearest-neighbor search is essential when vector collections exceed DRAM capacity. The challenge is to reduce SSD reads and hide I/O latency through concurrent reads and overlap with computation. However, for graph-based search, progressive candidate discovery limits advance I/O planning while IVF search reads inverted lists in full, incurring unnecessary SSD reads. In this paper, we present RaBitQ-SSD, an extension of IVF-RaBitQ for SSD-resident vector search. Specifically, we propose Split-RaBitQ, which retains a configurable prefix of each binary code in DRAM, allowing in-memory code storage below one bit per dimension. Using this partial representation, it provides an unbiased distance estimator with a probabilistic error bound. Once the in-memory coarse quantizer identifies candidate lists, this bound supports pruning individual candidates within them, enabling finer-grained SSD access. We also design an asynchronous search pipeline that coordinates candidate pruning with SSD read scheduling to reduce unnecessary reads while overlapping I/O with computation. On datasets ranging from $5$ million to $1$ billion vectors, RaBitQ-SSD delivers up to $1.74\times$ the throughput of graph-based baselines at $90\%$ recall, while reducing SSD page reads by up to $3.8\times$. Its on-SSD indexes are up to $7.0\times$ smaller and $10.0\times$ faster to build than DiskANN. We also build and search an index of $10$ billion vectors on a single machine with one SSD, achieving over $3{,}000$ queries per second at $90\%$ recall.

0.22

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.74
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

KatoANN: Enabling Near-Exact Vector Search at the Speed of Lossy Scans with CPU Matrix Engines

cs.DB cs.AR ·2026-10-20 ·Soobin Cho, Gyuyeong Kim
similarity 0.73
Abstract

Distance scans in partition-family approximate nearest-neighbor (ANN) search are typically limited by memory bandwidth. Existing systems therefore improve throughput by reading fewer bytes per candidate, often at the cost of recall. We present KatoANN, a CPU ANN search system that removes this tradeoff by batching distance scans on Intel AMX, a CPU matrix engine. Batching allows multiple queries to reuse each fetched vector code, shifting the scan from memory-bound to compute-bound and enabling near-exact distances at the speed of a lossy scan. KatoANN stores each vector once as a 16-bit SQ16 code split into high- and low-byte planes. Its adaptive rank-then-refine scan first ranks all candidates using only the high byte, then refines a small survivor set using the full-byte code. Both stages use the same representation, avoiding a second copy of the raw vectors. Experiments across diverse high-dimensional workloads show that KatoANN is the fastest partition-family ANN search system in our evaluation throughout the high-recall range.

0.24

UBASE: An AI Search Engine for Trillion-Scale Vector Data Management at ByteDance

cs.DB ·2026-08-31 ·Yao Tian, Yuncheng Lu, Liyao Xiong, Yuming Xu, Hao Zhang +7 more
similarity 0.72
Abstract · ATC26 UBASE with Appendix

Since 2016, UBASE has been the foundation of ByteDance's search infrastructure, scaling to more than 7,000 clusters and 300 PB of indexed data. Driven by the demands of AI workloads, UBASE has evolved from a text search engine into a unified AI search system supporting vector retrieval, lexical matching, and predicate filtering. Its largest deployment indexes nearly one trillion high-dimensional vectors. This scale exposes two central bottlenecks in AI-era retrieval: memory-intensive graph-index construction under sustained ingestion, and the prohibitive cost of keeping vector indexes entirely in memory. UBASE addresses these bottlenecks with two techniques. First, it introduces a quantization-aware vector kernel based on SymRaBitQ, a new symmetric quantization scheme with tight theoretical guarantees that allows index construction to run directly in the quantized space accurately and efficiently without retaining a copy of full-precision vectors. Second, it provides a hybrid storage engine that supports memory-resident, hybrid, and SSD-resident deployments, with fine-grained record-level caching to trade memory for latency under operational control. On large-scale benchmarks, UBASE improves throughput by up to 3x, reduces indexing memory by 80%, and lowers serving cost by up to 99.4% compared with prior systems, while supporting trillion-vector scale, write-heavy or latency-sensitive workloads in production.

0.24

GINGER: Spicing Up Graph-Based Vector Search

cs.IR cs.DC ·2026-11-05 ·Daniel Salwasser, Lars Gottesbüren, Laxman Dhulipala, Jakub Łącki, Guy Blelloch +5 more
code/data similarity 0.71
Abstract

We present \textsc{Ginger}, a state-of-the-art open-source C++ library for graph-based approximate nearest neighbor search (ANNS). We developed \textsc{Ginger} at Google to push the speed and memory efficiency of graph search on large and high-dimensional embedding datasets. \textsc{Ginger} surpasses existing ANNS libraries with regards to query throughput and indexing time while matching the memory footprint of the most space-efficient competitors. \textsc{Ginger} builds upon recent advances in proximity graph construction (PiPNN) and vector quantization (TurboQuant). We introduce Nested TurboQuant (NTQ), a two-level quantizer which supports low precision graph navigation and high precision reranking in a single code. This representation achieves near floating point precision with $2.6\times$ less memory. We also compress the size of our proximity graphs by up to $2.5\times$ without impacting query throughput. We combine graph reordering with a new lossless compression codec called AdaptiveGap, which builds upon StreamVByte. At $95\%$ recall, \textsc{Ginger} speeds up query throughput by an average of $1.8\times$ over each dataset's fastest competitor and by at least $2.3\times$ over any single library. This lead grows to $2.9\times$ over compact libraries on high-dimensional embeddings.

0.26

Towards Enabling Distance-Based Memory Addressing

cs.AR cs.ET ·2026-09-05 ·Ananth Krishna Prasad, Sharad Bhat, Rajeev Balasubramonian, Mahdi Nazm Bojnordi
similarity 0.70
Abstract · 14 pages, 10 figures, 3 Tables

Approximate Nearest-Neighbor Search (ANNS) in high dimensional vector datasets is an application of significant prevalence across different AI applications. However, such an operation is significantly bandwidth limited at large workingset sizes owing to the curse of dimensionality. Traditional indices used to accelerate ANNS rely on search-space pruning as a preprocessing step to alleviate such bandwidth requirement, but such optimization occurs either at the cost of increased bandwidth-inefficiency and/or degradation of search quality. This paper proposes a data-parallel hardware/software mechanism for performing large-scale similarity search in-memory. We propose a novel algorithm to simplify the computation requirement for similarity search across various distance metrics through lightweight primitives to perform a fast and approximate data-parallel brute-force search on the entire vector space. We further build a memory system capable of executing the required operations to generate a distance metric per datapoints, which is then used to enable pruning as a post-processing step. We offer adequate software support for user control over the proposed system. By enabling such search-space pruning as a post-processing step, we achieve near-perfect recall across representative workloads while achieving orders of magnitude performance and energy improvement over state-of-the-art algorithmic approaches on million and billion-scale workloads.

0.25

RiftANN: Efficient Graph Traversal for Vector Search with RDMA-Based Memory Disaggregation

cs.DB ·2026-10-06 ·Qi Lin, Zhenyu Zhang, Jun Kong, Zhichao Cao
similarity 0.70
Abstract

Graph indexes for billion-scale vector collections can exceed a single server's DRAM capacity. Passive RDMA-based disaggregated memory provides scalable capacity without memory-node computation, but conventional best-first search performs poorly in this setting. Fine-grained and unnecessary remote reads increase communication cost, while dependencies between candidate evaluation and subsequent expansion serialize traversal and leave CPUs idle. We present RiftANN, a graph-based approximate nearest neighbor search (ANNS) system for passive RDMA-based disaggregated memory. RiftANN navigates using compact vectors at compute nodes and selectively verifies exact vectors using a threshold calibrated from observed approximation errors. A bounded one-sided RDMA pipeline batches and overlaps the remaining remote accesses with local processing. RiftANN evaluates returned neighbors in parallel and incrementally incorporates completed results. An impact gate estimates whether unfinished evaluations may change the candidate set, allowing traversal to continue when their expected influence is small while preventing unsafe advancement from incomplete search state. A lightweight feedback controller coordinates RDMA concurrency with background evaluation capacity as search configurations and query loads change. We evaluate RiftANN on SIFT, DEEP, and SPACEV at 100M scale and SIFT1B. At matched recall, RiftANN achieves 1.6x to 4.3x latency speedups and 1.1x to 2.2x higher throughput than DistVS, and 1.6x to 5.6x latency speedups over SSD-based DiskANN and PipeANN. These results show that passive disaggregated memory can support low-latency graph-based vector retrieval without query-time computation at memory nodes.

0.21