Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· pp. 6700-6711· 0 citations· 17 references
Abstract
Graph-based approximate nearest neighbor search (ANNS) is widely used in vector databases and retrieval systems. Most existing methods typically rely on structure-driven index construction and tuning, building graph topologies that approximate idealized geometric archetypes to promote navigability. However, geometric proximity is often an indirect proxy for search efficiency: static graph structures may fail to reflect actual traversal dynamics, leading to redundant distance evaluations such as low-yield node expansions and unnecessary local detours. These inefficiencies can significantly hinder high-recall performance. To address this limitation, we introduce PIGR (Post-hoc Iterative Graph Refinement), a trace-driven framework that explicitly aligns efficiency with observed search behavior. Instead of relying on coarse-grained construction parameter tuning, PIGR leverages self-queries to analyze search traces and identify inefficient traversal behaviors. It further performs iterative index optimization via trace-guided, budgeted prune-and-add edge edits without modifying the deployed search procedure. As a post-construction plug-in, PIGR delivers 1.3x-2.5x speedups at near-exact recall across diverse datasets and index families, consistently outperforming the best build-time tuned baselines.
Graph-based indexes have become the dominant approach to approximate nearest neighbor search (ANNS) over high-dimensional data and play a crucial role in real-world applications such as retrieval-augmented generation, recommendation systems, and vector databases. Despite extensive progress in static graph construction and search, efficient in-place deletion remains challenging because obsolete vectors must be removed without allowing stale incoming edges to consume search capacity or expensive graph-wide maintenance to interrupt online services, e.g., retrieval-augmented generation (RAG) and recommendation platforms. To address this problem, we propose MERIT (MST-based Efficient Repair with In-place updaTes), an in-place update framework with three core techniques: (1) bounded search-based recovery that combines a deleted vertex's outgoing neighbors with its readily searchable in-neighbors, (2) $k_r$-Minimum Spanning Tree (MST) local repair that promotes local connectivity while retaining multiple routing choices for graph search, and (3) versioned-edge invalidation that immediately filters all stale incoming edges to the deleted vertex and progressively removes them as adjacency lists are rewritten. Its integration with the hierarchical HNSW index and the single-layer Vamana index demonstrates applicability across distinct graph structures. Extensive experiments on multiple real-world datasets show that MERIT processes deletion at nearly the cost of inserting one vector, achieves up to $3.02\times$--$18.87\times$ faster deletion than state-of-the-art (SOTA) methods, and keeps search recall stable or even improves it as deletions accumulate.
Approximate Nearest Neighbor (ANN) search is a core operation in large-scale vector databases that support recommendation, semantic search, and retrieval-augmented generation. Graph-based indexes are widely used for their superior search performance at million scale, but scaling them to billion-scale datasets exposes a fundamental trade-off between construction efficiency and search performance. CPU-based methods produce high-quality graphs enabling fast search but require multiple days to construct, while GPU-based methods accelerate construction at the cost of degraded search performance. This trade-off stems from the traditional requirement of enforcing global connectivity during graph construction. We observe that graph-based search primarily depends on local connectivity between entry points and a query's nearest neighbors, making global connectivity unnecessary for high search performance. In this paper, we introduce HEXA, a disjoint-subgraph-based indexing framework that partitions the dataset into disjoint clusters and constructs refined proximity subgraphs independently on GPUs. At query time, HEXA employs a two-level routing structure to select relevant subgraphs and query-close entry points, then applies a budget-adaptive search algorithm that allocates exploration effort based on each subgraph's likelihood of containing nearest neighbors. Experiments on billion-scale datasets demonstrate that HEXA achieves up to 14.7 times higher query throughput at the same recall levels compared with various indexing methods, and reduces construction time to approximately one hour.
Yi-Fei Xu, Yan-Yan Shen, Youmin Chen et al.· Proceedings of the VLDB Endo...· 0 citations
This paper addresses both $k-Nearest Neighbor Graph (kNNG) construction on 1024-dimensional BGE-M3 embeddings and Maximum Inner Product Search (MIPS) on unnormalized Llama-3.2-8B features, and introduces a 1D presorting mechanism via Fast Linear Assignment Sorting (FLAS) prior to graph construction.
Nico Hezel, Kai Barthel, Bruno Schilling et al.· arXiv.org· 0 citations
Approximate Nearest Neighbor (ANN) search at scale exposes a structural trade-off between routing accuracy, memory footprint, and query latency. Graph-based indices such as HNSW provide high recall but incur significant memory overhead due to full-dataset connectivity, while centroid-based IVF variants remain memory-efficient yet degrade under highdimensional, non-convex cluster manifolds. This trade-off forces system designers to choose between recall and storage cost, and no existing single-index design resolves both simultaneously at scale. The need for an index that delivers graph-level recall at IVF-level memory cost therefore motivates this work. We present a density-aware hybrid indexing architecture that explicitly decouples routing from storage. The system extracts manifold representatives via a robust Lloyd refinement and constructs a lightweight HNSW graph over this reduced set, preserving topological routing precision while avoiding fullgraph memory costs. Candidate selection is performed through a dual-path routing mechanism combining geometric centroids and density-aware graph traversal. The search pipeline then diverges into two execution regimes: (1) an uncompressed, SIMD-optimized L2 path achieving hardware-bound latency, and (2) a compressed OPQ-based residual reconstruction path for memory-constrained deployment. On SIFT1M, the uncompressed configuration achieves 0.09 ms/query with 0.974 Recall@10, while the 32-byte/vector OPQ configuration attains 0.341 ms/query with 0.997 Recall@10. Integrated into a gRPC scatter-gather framework, the distributed system sustains 0.9975 Recall@10 across sharded partitions. These results demonstrate that density-aware routing enables graph-level recall with IVF-level storage cost, providing a scalable foundation for high-dimensional vector retrieval.
Aditya Parthiban, Arindam Kalita, Rishab K Das et al.· 2026 International Conferenc...· 0 citations
Graph-based retrieval can improve multi-hop question answering, but existing approaches often incur high query-time costs and produce diffuse, oversized contexts that reduce generation efficiency. We present LiteRAG, a graph-based retrieval method that replaces expensive retrieval-time LLM control with query-conditioned algorithmic exploration and reasoning-chain context construction. On DistComp, a benchmark for multi-hop retrieval over distributed-systems papers, LiteRAG attains the highest overall quality among the evaluated methods (0.798) while reducing per-query latency by over 100$\times$ and cost by over 99% relative to GraphRAG Global and DRIFT. On UltraDomain, it matches LinearRAG on overall quality while using about 14$\times$ fewer tokens. An ablation study indicates that LiteRAG's query-adaptive thresholding and community-aware hub penalization are the main drivers of its token-efficiency gains.
Daniel Alejandro Coll Tejeda, Pedro García López, Daniel Barcelona-Pons· 0 citations
Graph-based Approximate Nearest Neighbor Search (ANNS) has become fundamental to modern data-intensive applications, yet supporting efficient vector updates while maintaining index quality remains a critical challenge. Existing approaches face a tough dilemma: extensive reconstruction ensures connectivity but incurs unpredictable overhead, while restricting update scope improves efficiency but degrades search accuracy. In this paper, we reveal that graph-based ANNS indexes inherently comprise backbone nodes that dictate global navigation capability and expansion nodes that provide local refinement. This insight motivates Hope, a Host-CSD (Computational Storage Device) cooptimized update framework that optimizes both index quality and update efficiency with a differentiated update design. For efficient vector categorization, we propose an in-storage sketcher that leverages per-dimension correlation with the bitmap-based flip mechanism to dynamically identify backbone and expansion vectors with minimal overhead. For asymmetric update handling, Hope employs the host-CPU for computation-intensive backbone updates with multi-hop neighbor gathering to preserve connectivity, while delegating I/O-intensive expansion updates to in-storage computing for immediate local manipulations. Our evaluation demonstrates that Hope achieves superior update efficiency and index quality compared to state-of-the-art baselines, providing stable performance for both vector updates and ANNS queries in dynamic environments.
Kecheng Huang, Jiaxian Chen, Chenlin Ma et al.· IEEE Non-Volatile Memory Sys...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
