Search papers, labs, and topics across Lattice.
This paper addresses the challenges of Approximate Nearest Neighbor Search (ANNS) by presenting two innovative approaches for the 2026 SISAP Indexing Challenge, focusing on k-Nearest Neighbor Graph (kNNG) construction and Maximum Inner Product Search (MIPS). The authors employ Equi-Voronoi Polytopes (EVP) for efficient quantization and implement targeted reranking strategies to enhance recall in high-dimensional BGE-M3 embeddings. Additionally, they introduce a 1D presorting mechanism using Fast Linear Assignment Sorting (FLAS) to improve query latency and memory access, resulting in significant performance gains during graph traversal.
Transforming the asymmetric inner product problem into a Euclidean search space could redefine efficiency benchmarks in high-dimensional embedding searches.
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
