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.
Abstract
The annual SISAP Indexing Challenge benchmarks Approximate Nearest Neighbor Search (ANNS) algorithms under rigorous constraints. This paper presents our submissions for the 2026 edition, addressing both $k$-Nearest Neighbor Graph (kNNG) construction on 1024-dimensional BGE-M3 embeddings (Task 1) and Maximum Inner Product Search (MIPS) on unnormalized Llama-3.2-8B features (Task 2). To optimize construction speed, we utilize Equi-Voronoi Polytopes (EVP) for efficient quantization, supplemented by targeted reranking strategies to maintain high recall. For MIPS, we transform the asymmetric inner product problem into a Euclidean search space via dimensionality augmentation. To reduce query latency and optimize memory access, we introduce a 1D presorting mechanism via Fast Linear Assignment Sorting (FLAS) prior to graph construction. This significantly improves spatial locality and cache hit rates during subsequent graph traversal. Source Code: https://github.com/Visual-Computing/sisap26-deglib
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 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.
Zhiwei Zhang, Weiguo Zheng· Proceedings of the 32nd ACM...· 0 citations
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.
Zekai Wu, Jiabao Jin, Peng Cheng et al.· 0 citations
Approximate nearest neighbor search (ANNS) is a fundamental operation in large-scale vector retrieval systems, where achieving high recall under strict latency constraints is essential. Existing ANNS approaches typically control recall using fixed search parameters, such as a predefined candidate neighbor set (CNS) size, which require significant effort to fine-tune for each use case. Even worse, due to substantial heterogeneity in query difficulty and data distribution, static parameterization often results in over-searching for easy queries and under-searching for hard ones. In this paper, we propose an adaptive framework for ANNS that explicitly incorporates user-specified recall requirements into the search process by employing an early termination strategy. We introduce two learning-based mechanisms, one for dynamically predicting the achieved recall during the search and triggers early termination once the predicted recall satisfies the target threshold, and another for estimating the minimal CNS size required to satisfy user needs during the search, enabling dynamic scaling of the CNS. Our framework is index-agnostic and can be seamlessly integrated into widely used graph-based ANN indexes, including HNSW, with negligible overhead. Extensive experiments on benchmark datasets and various graph indexes demonstrate that our methods significantly reduce query latency compared to state-of-the-art baselines. Our code is available at https://github.com/lxxabb/Recall-Aware-Early-Termination-in-Approximate-Nearest-Neighbor-Search.
Shuang Hao, Xinxin Li, Wei Zhang· Proceedings of the 32nd ACM...· 0 citations
Approximate nearest neighbor search (ANNS) on CPUs is increasingly constrained by candidate-vector movement and decoding rather than peak arithmetic throughput. Although the RISC-V Vector Extension (RVV) provides vector-length-agnostic execution and LMUL-based register grouping, generic low-precision decoding still incurs conversion overhead, while irregular graph traversal generates scattered accesses that degrade cache locality and memory-level parallelism. We present RVANNS, an RVV-oriented ANNS engine that jointly optimizes vector representation and graph locality. Its Mixed-Precision Multi-Layer Index (MPMI) represents each vector with a dense 8-bit affine base and sparse FP16/FP32 residuals, fusing reconstruction with distance accumulation and aligning widening with LMUL-sized register groups. ROrder co-locates likely co-visited graph nodes and sorts remapped adjacency lists, transforming scattered payload probes into denser, predominantly forward-moving address streams. Integrated into Milvus, RVANNS achieves 3.39x and 4.94x speedups over scalar execution on real 128-bit and 256-bit RVV processors, respectively. Under controlled HNSW configurations, it improves throughput by 2.27--2.76x over RVV SIMD+FP32 and by 1.18--1.59x over the corresponding AVX-512 and SVE baselines. On Cohere10M, it further delivers 1.82--2.27x higher QPS/W than the evaluated GPU baselines.
Chengying Huan, Yudong Liu, Jianguo Wang et al.· 0 citations
It has been common to represent many objects as high-dimensional vectors due to the proliferation of machine learning-based embedding techniques. One of the most important functions for analyzing high-dimensional vectors is approximate nearest neighbor search, which, given a query vector, retrieves the vector that is approximately the most similar to the query vector. In many real-world applications, such as e-commerce, objects have not only vectors but also attributes, e.g., category, color, and brand, and they require a scenario where users can specify a query vector and a value for each attribute of interest. This problem, called filtered approximate nearest neighbor search, retrieves approximate nearest neighbors from a set of objects that have the specified attribute values. Efficiently solving this problem is challenging because it has to accept arbitrary query vectors and attribute values, which are not known in advance. Existing techniques suffer from slow search performance and difficulty in dealing with arbitrary combinations of attributes. This work overcomes these challenges and proposes a new algorithm for this problem. We conduct extensive experiments, and the results demonstrate the efficiency of our algorithm.
