CS Paper Radar

AiSAQ-in-Filtering for DRAM-free Filtered Information Retrieval

Kento Tatsuno, Daisuke Miyashita, Kazunari Sumiyoshi, Hiroaki Yamanaka, Kosuke Nakata, Jun Deguchi

cs.IR ·submitted 2026-10-13 02:50 UTC · v1

Abstract

Filtering search is one of the crucial applications of approximate nearest neighbor search (ANNS). In filtering search, label information is used in conjunction with unstructured vector data. ANNS provides efficient similarity search in large-scale datasets, however, the memory footprint of storing both vector data and their associated label becomes a significant cost factor as dataset sizes grow. To address this problem of increasing DRAM usage, we propose AiSAQ-in-Filtering, with a novel quantization method called LiPQ (Label-inclusive Product Quantization). LiPQ combines unstructured data and structured labels into a single representation, leading no growth of encoded data. Our proposal increased recall@1 of single-label searches by up to 55% and fewer disk I/Os compared with existing methods. This also retains the main advantages of AiSAQ, which can reduce DRAM footprint by up to 1/78 and index switching time comparing with existing methods. This proposal can also be applied to sparse-dense hybrid search beyond label filtering such as semantic and keyword search of documents.

Comment
5 pages, 7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

CapCover Filter: Semantic Approximate Membership Queries over Embeddings

cs.DB cs.AI ·2026-11-15 ·Dvir David Biton, Shay Hahiashvili, Nadav Keren, Gil Einziger, Roy Friedman
similarity 0.67
Abstract

Determining whether an embedding is sufficiently similar to any vector in a vector store without performing a nearest-neighbor search can substantially improve query throughput in vector-store systems. We study Semantic Approximate Membership Queries (SAMQs), which allow queries to be rejected when no indexed vector meets the requested similarity threshold, while guaranteeing no false negatives. We introduce CapCover Filter, a geometric data structure that summarizes a set of embeddings using spherical caps. Its representation is independent of the query threshold, allowing a single filter to support arbitrary thresholds without reconstruction. We evaluate alternative construction and quantization methods, compare CapCover Filter with competing filters, and measure its impact on query throughput. Across five real-world datasets, at a cosine similarity threshold of 0.95, CapCover Filter eliminates approximately 20--100\% of index accesses while using only 2\% of the raw (FP32) embedding memory. When placed before a FAISS flat index, it improves query throughput by up to 382\% and by approximately 116\% on average across the five datasets, while returning the same range-search result. We also evaluate lower similarity thresholds. Our results show that CapCover Filter can substantially improve vector-store throughput when similarity thresholds are tight, retrieval is expensive, and indexed embeddings are highly clustered. We release an optimized implementation of CapCover Filter and its evaluation framework.

0.14

RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search

cs.LG cs.IR ·2026-08-31 ·Rastislav Lenhardt, Teodora Dobos, Thomas Vecchiato, Jiri Isa, Igor Ginzburg
benchmark similarity 0.64
Abstract · 14 Pages, 3 Figures, Preprint

By introducing RSLM (Rotated Scaled Lloyd-Max), a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension, we reduce memory cost and memory bandwidth of a typical large-scale Approximate Nearest Neighbor (ANN) search system, while reducing its complexity and keeping or improving recall across multiple benchmark datasets. State-of-the-art systems filter candidates using coarse partitions, approximately score them to narrow the set, and then rescore the best with higher precision representations (often >=8 bits per dimension). Our relativized codecs can bring this down to 2--4 bits per dimension. We use the properties of the ANN system to encode residual vectors instead of full vectors, both for the approximate scoring phase and the rescoring phase. Since Maximum Inner Product Search (MIPS) is very sensitive to vector norms, we correct the $L_2$ norms of quantized vectors. Our major innovation is that we correct the $L_2$ norm of the final reconstructed vector rather than just the residual. Our rescaling replaces more complicated schemes, such as Anisotropic loss. The residualization scheme gives us a more favorable quality vs size trade-off than generic quantization methods. Our high-performance implementation leverages a block-wise cascaded Fast Walsh-Hadamard Transform (FWHT) with linear-like complexity, AVX SIMD-optimized codebooks, and a steganographic encoding of scaling factors for perfect cache-line alignment.

0.36

VADER: Filtered Vector Search with Declarative Recall

cs.DB ·2026-09-29 ·Manos Chatzakis, Duo Lu, Helena Caminal, Yannis Chronis, Fatma Özcan +5 more
top venue similarity 0.63
Abstract · This paper appeared in VLDB 2027

Approximate filtered vector search (FVS), a core operation in many data management tasks that combine structured data with vector embeddings, exhibits increased complexity due to the characteristics of filtering predicates. Each predicate is defined by selectivity (i.e., the fraction of vectors that satisfy the predicate) and correlation (i.e., the relationship between the filter and the vector space), which can significantly affect search difficulty even for the same query vector. This poses a key challenge for users aiming to integrate vector search with structured data, as efficient execution often requires extensive manual tuning of algorithm parameters. In this paper, we present VADER, the first approach that eliminates hyperparameter tuning by introducing declarative recall for approximate filtered vector search. With declarative recall, users specify a desired recall target, and VADER executes FVS queries to meet this target without requiring manual configuration. VADER achieves this by employing a filter-aware recall predictor that generalizes across varying selectivities and correlations without explicit tuning, and by performing early termination once the predicted recall reaches the user-defined target. Through extensive experimental evaluation, we show that VADER achieves near-optimal early termination, while providing significant speedups of up to 53% faster and improved result quality of 28% compared to the best-performing baseline.

0.29

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

BOA: Beamwidth Online Adaptation for Filtered-ANNS on a GPU

cs.DC ·2026-09-14 ·Farhana Akter Tumpa, Rajiv Gupta
similarity 0.63
Abstract

Filtered approximate nearest neighbor search, i.e. returning the top-k vectors nearest to a query vector among those satisfying one or more attribute predicates, has become a fundamental operation in modern vector search systems. Graph-based solutions employ beam search to solve a batch of queries in parallel for high throughput and employ high fixed beamwidth of 100 or greater for ensuring high recall. We observe that, given a batch of queries, more than half of the queries across multiple data sets can be solved precisely with a beamwidth of just 50 or less. Therefore, existing systems based on fixed high beamwidth sacrifice throughput to achieve high recall by forcing every query to search as thoroughly as the hardest query in the batch even though majority of queries can be resolved by a shallow search. In this paper we present a filtered ANNS engine for a single GPU named BOA that uses online beamwidth adaptation to customize the search effort across queries within a batch under multi-attribute range filters. We address the recall throughput tradeoff with a multi-phase search: all queries are first evaluated under a narrow beam, and only those with uncertain results are progressively refined with wider beamwidths. This renders recall largely insensitive to the starting beamwidth, whereas prior methods must use a fixed high beamwidth for high recall. BOA+ overlaps execution of phases to further enhance throughput. Our experiments show that, for 10,000 queries, online adaptation achieves 94.05% to 99.96% recall with average beamwidth ranging from 22 to 77, while a non-adaptive approach requires a fixed beamwidth of 500 to achieve similar or lower recall. Consequently, adaptivity increases throughput by 7x to 12.5x

0.07

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

cs.DB ·2026-11-02 ·Zehai Yang, Fengyi Tao, Wenzhuo Dong, Shimin Chen
similarity 0.63
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.

0.13

Analyzing and Reducing Search Quality Differences in Vector Similarity Search

cs.DB cs.OS ·2026-08-25 ·Sara Mahdizadeh Shahri, Martin Prammer, Jignesh M. Patel, Akshitha Sriraman
similarity 0.62
Abstract

Modern database services scalably search over large data collections via Approximate Nearest Neighbor Search, which improves search performance at the cost of search quality, measured by recall. In practice, a database operator seeks to achieve a target mean recall while maximizing throughput across search queries. We show that optimizing for mean recall masks significant differences in recall across queries even when target recall is met. As a result, numerous queries face (1) below-target recall, hurting user experience and revenue and (2) above-target recall, wasting computation to deliver unnecessarily high search quality. Thus, it is critical to detect and reduce recall differences across queries. We design RCheck, a light-weight run-time system that identifies low-recall queries and reduces recall differences while achieving high throughput. RCheck's key design principle is to dynamically, efficiently adapt search effort by increasing effort for queries below target recall and decreasing effort for those above it. RCheck tunes available search effort parameters, making it readily deployable. We evaluate RCheck using the widely-used production-style pgvector database. At the same throughput, RCheck improves mean recall by 11-93% and enables 8-47% more queries to meet target recall compared to the state-of-the-art globally-tuned configuration.

0.23