CS Paper Radar

REWEAVE: Online Learning for Workload-Adaptive HNSW Indexes

Minghao Li, Nick Koudas, Raghav Mittal

cs.DB cs.IRcs.LG ·submitted 2026-11-11 22:18 UTC · v1
theory

Abstract

Vector databases rely on Hierarchical Navigable Small World (HNSW) indexes for similarity search, but a graph built from data alone can be poorly matched to a skewed or changing query workload. We present REWEAVE (Reward-Guided Rewiring of Vector Graphs), an online index-maintenance method that learns edge utility from query feedback and periodically rewires the bottom layer within the original per-node degree cap. The method supports sparse exact-neighbor feedback combined with self-labels, and standard HNSW serving without learning overhead once adaptation is disabled. Under explicit assumptions we prove value-estimation and graph-stabilization guarantees. Under stationary skew, REWEAVE improves held-out recall by up to 23.3 percentage points over HNSW. In comparisons with query-aware baselines on up to 100M vectors, it achieves up to 3.3x NGFix's query throughput at recall@100 of 0.80. On Amazon-ESCI with query drift, it increases stream recall@100 from 0.745 to 0.979 with 34% fewer search distance computations than frozen HNSW. These results illustrate the potential to improve retrieval quality and reduce search effort within an existing graph-degree budget, while incurring additional work during adaptation.

Comment
20 pages, 9 figures, 5 tables. Full version with appendix

Closest papers

Nearest neighbours by meaning across the whole index.

Index-Free Dynamic Edge Retrieval with Energy-Tail-Aware Partial Scans

cs.IR ·2026-09-01 ·Mohammad Arif Rasyidi, Omar Alhussein
publishedcode/data similarity 0.69
Abstract · Accepted for presentation at the 2026 IEEE 12th World Forum on Internet of Things (WF-IoT)

Dynamic maximum inner-product search (MIPS) returns the $K$ stored vectors with the largest dot products with a query while allowing the dataset to change through insertions, replacements, and deletions. For edge retrieval, the challenge is to achieve high recall and fast queries without making updates expensive. Full-vector scanning keeps updates simple but compares each query with every stored vector, while indexed methods reduce query cost at the expense of maintaining additional structures during updates. We propose ETAR, an index-free method that reduces query work while preserving simple updates. ETAR keeps the query coordinates with the largest squared values until they cover most of its total squared magnitude and treats the rest as a low-magnitude tail. It estimates similarity from the retained coordinates using a compact lower-precision representation, corrects for skipped coordinates, and reranks a fixed number of candidates using full-precision vectors. Across five runs on nine static datasets, ETAR averages 99.2% Recall@10, the fraction of exact top-10 results recovered, while running over 4$\times$ faster than exact scanning at a representative setting. This speedup also extends to an ARM-based mobile device, where ETAR is up to 6.9$\times$ faster across four synthetic distributions. Under five streaming workloads, it maintains 100% Recall@10 at every measured point without index rebuilds. Overall, ETAR offers a practical middle ground for dynamic MIPS by reducing query cost while retaining simple, index-free updates. Code is available at https://github.com/arasyi/etar-mips.

0.47

Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search

cs.IR ·2026-10-27 ·Francesco Benocci, Leonard Dahlmann, Francesco Gargiulo, Tobias Heuer, Silvio Martinico +3 more
top venuecode/data similarity 0.67
Abstract · 7 pages, 5 figures, Accepted at CIKM 2026. Code: https://github.com/TusKANNy/kannolo. Reproducibility: https://github.com/tusKANNy/papers_re…

Graph-based Approximate Nearest Neighbor (ANN) indexes, such as HNSW, are the backbone of modern vector search. However, their massive memory footprint creates a severe infrastructure bottleneck. While vector quantization is widely adopted to reduce the memory required to store data vectors, the graph's edge structure increasingly dominates total memory usage. Compressing these adjacency lists for online search presents a critical system challenge: because decompression occurs during query processing, i.e., while navigating the graph, memory savings cannot come at the expense of query latency. In this paper, we present a compression technique explicitly tailored for live HNSW routing. By applying offline graph permutations to artificially induce structural locality, we enable the use of SIMD-accelerated integer compressors, such as Stream VByte, for rapid on-the-fly decompression. Evaluated across diverse real-world workloads, we significantly outperform the current state of the art in both compression ratio and query latency. Our experimental results show that we achieve compression ratios up to 52.7% with negligible penalties in latency compared to the uncompressed baseline. Furthermore, our technique has been effectively deployed in production at eBay, achieving up to 44.3% reduction in edge storage with no degradation in query latency.

0.73

Budgeted Task-Aware Acquisition of Dynamic Networks

cs.LG ·2026-09-05 ·Zihe Zhou
benchmarkcode/data similarity 0.66
Abstract · 4 pages, 2 figures, 1 table. Revised version with updated experimental results and analysis. Code and experimental details: https://github.c…

Learning on dynamic graphs is difficult when changes in the underlying network are only partially observed. Acquiring current graph information incurs observation and computational costs, making complete updates impractical under limited resources. This paper focuses on budgeted task-aware acquisition on dynamic networks, where a model needs to decide which stale graph information to refresh for a downstream task. We propose Scout, a lightweight framework that learns the task value of querying each node from the maintained graph and observation history. Our evaluation covers one synthetic and 4 real-world dynamic networks, 2 downstream tasks, 9 acquisition baselines, and several query budgets. Scout achieves the highest mean downstream performance in 15 of the 21 benchmark-budget settings and ranks within the top two in 19 of them. Its average rank is 1.4, compared with 3.2 for the strongest baseline. On the same dynamic network, task-matched acquisition improves link-prediction AUC by 0.005-0.007 and node-classification accuracy by 0.007-0.017 over task-mismatched acquisition. These results show that useful graph observations depend on the downstream task and that limited observation budgets can be allocated effectively by learning directly from downstream utility.

0.31

Getting a GRIP on Graph-Based Search for Learned Sparse Retrieval

cs.IR cs.DB ·2026-10-21 ·Vihan Lakshman, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini
benchmark similarity 0.65
Abstract · 8 pages

Learned sparse retrieval (LSR) has recently gained traction in the information retrieval community for the ability to combine the generalization capabilities of neural representations with the interpretability of keyword-based search. A number of recent works have demonstrated that inverted indexes, when appropriately modified for learned sparse embeddings, achieve state-of-the-art recall-latency tradeoffs for LSR, often outperforming graph-based indexes by substantial margins in latency at a fixed recall target. As a result, the community has generally concluded that graph-based approximate nearest neighbor (ANN) search is inferior to inverted indexes for LSR. This paper challenges this conventional wisdom. Our key insight is that, while applying standard graph-based ANN indexes out-of-the-box to sparse vectors leads to uncompetitive performance, we can overcome these shortcomings by infusing the strengths of inverted indexes into graph-based search. In particular, we introduce three techniques to accelerate graph-based LSR: (i) term-based entry point seeding, (ii) approximate routing via sparse sketching, and (iii) sparse partition-based graph construction. We combine these techniques into a new graph-based ANN system for LSR we call GRIP. On the MS MARCO v2 benchmark (138M passages) with SPLADE embeddings, GRIP achieves a $2.5\times$ latency improvement over Seismic, a state-of-the-art inverted index tailored for LSR, at 95\% recall@10. Ultimately, our results call into question the default choice of inverted indexes for deploying learned sparse retrieval.

0.27

Recall-Bounded Staleness for Filtered Multi-Tenant ANN Graph Indexes under Concurrent Updates

cs.DB cs.DC ·2026-10-10 ·Namrata Das, Kailas Devadkar, Anand Godbole
similarity 0.64
Abstract · 14 pages, 4 figures, 3 Pages supplemental Proof

Production vector search must continuously ingest, delete, and re-tenant vectors while serving low-latency, high-recall, metadata-filtered approximate nearest-neighbor (ANN) queries for many tenants with per-tenant service-level objectives. Existing graph-based ANN systems address these requirements largely in isolation, leaving recall during concurrent re-optimization without an analytical bound. We develop a graph-based index that combines streaming updates, filtered search, and multi-tenancy, with one theoretical result and two system mechanisms. Our theory decomposes per-tenant recall loss into staleness from updates not yet integrated into the graph and filtered navigability determined by the local density of points satisfying a tenant's predicate. The staleness component exhibits anti-amortization on a merge-based graph, integrating a larger batch of inserts increases recall degradation super-linearly, so larger merges do not reduce total staleness loss. Holding the insert horizon fixed while increasing merge size 20x, we observe a monotonic decrease in terminal recall@10 from 99.44% to 99.01%. For filtered search, the theory gives a parameter-free frontier-mass relationship in local predicate density and a query-averaged per-tenant recall bound. We instantiate the bound with a filter and tenant-aware staging cache and a select-not-resize scheduler with per-tenant staleness ceilings. On a FreshDiskANN substrate, the ceiling eliminates tight-tier SLA violations under the evaluated churn workload, while merge reordering changes terminal recall by only 0.02 percentage points. The results show how recall bounds can guide background maintenance without relying on merge resizing as a recall control mechanism.

0.15

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

HorizANN: Elastically Scaling Vector Search with Ghost Edges

cs.DB ·2026-11-14 ·Talika Gupta, Yunqi Li, Aditya Kunte, Claire Lin, Supawit Chockchowwat +3 more
similarity 0.63
Abstract · 14 pages, 11 figures

Approximate nearest neighbor search (ANNS) is fundamental to modern data-intensive AI applications such as retrieval-augmented generation, recommendation systems, and semantic search. Among existing indexing methods, graph-based indexes emerge as the state of the art due to their superior recall-throughput tradeoffs. Scaling these indexes to multiple machines requires partitioning the data and building indexes on each. However, when new machines are added or removed, the data must be repartitioned and the indexes reconstructed from scratch, making horizontal scaling costly at billion scale. In this work, we present HorizANN, a distributed graph-based ANNS system that scales horizontally without requiring full index reconstruction. To achieve this, we introduce ghost edges, a mechanism for preserving cross-partition connectivity as partition boundaries change during repartitioning. By reusing the structural information that would otherwise be discarded during repartitioning, HorizANN avoids costly full index reconstruction. As the index grows from 100M vectors on one worker to 1B vectors on ten workers, HorizANN inserts each 100M vectors within 2.5 hours and sustains 3.4--3.5K queries per second at 0.998 Recall@10.

0.18

SAIL: Self-Adaptive Index Learning with Hybrid Models (Extended Version)

cs.DB ·2026-11-10 ·Kasun Amarasinghe, Farhana Choudhury, Jianzhong Qi
similarity 0.62
Abstract

Learned index structures have demonstrated a significant improvement in query performance over traditional index structures. The majority of learned indexes use a uniform node structure throughout their index structures. A few studies show that combining multiple types of node structures can lead to indexes that better adapt to local key-set distributions, hence yielding query efficiency gains. Following this line of work, we propose a learned index structure named SAIL that supports a wide range of different candidate node structures for both leaf and inner nodes, selected via cost models based on data driven approximations. We design an efficient construction algorithm that recursively partitions the key-set to be fitted by the candidate node types. Experiments demonstrate that SAIL achieves 2x improvement over existing learned indexes in query time, with similar memory consumption and index build times.

0.26