Fast and Efficient Approximate Nearest Neighbor Search for High-Dimensional LLM Embeddings

• URL: http://arxiv.org/abs/2607.20957v1
• Date: Thu, 23 Jul 2026 06:35:12 GMT
• Title: Fast and Efficient Approximate Nearest Neighbor Search for High-Dimensional LLM Embeddings
• Abstract summary: SISAP Indexing Challenge benchmarks Approximate Nearest Neighbor Search (ANNS) algorithms under rigorous constraints.<n>This paper presents our submissions for the 2026 edition, addressing 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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

Related papers

• GONDOR to the Rescue: Satisficing Planning with Low Memory [80.8869960059932]
  GONDOR is a memory-efficient extension of Greedy Best-First Search (GBFS)<n>GONDOR periodically compresses the search tree while retaining a sparse set of anchor states, then upon reaching the goal reconstructs the path by re-searching between the sparse states.<n> Experiments show that GONDOR consistently improves coverage under low memory budgets compared to standard GBFS.
  arXiv  Detail & Related papers  (2026-05-27T13:20:58Z)
• optimize_anything: A Universal API for Optimizing any Text Parameter [98.42497715725356]
  We show a single AI-based optimization system-supporting single-task search, multi-task search with cross-problem transfer, and generalization to unseen inputs.<n>We show for the first time that text optimization with LLM-based search is a general-purpose problem-solving paradigm.
  arXiv  Detail & Related papers  (2026-05-19T10:18:12Z)
• Panorama: Fast-Track Nearest Neighbors [22.201421121801218]
  We present PANORAMA, a machine learning-driven approach that tackles the Approximate Nearest-Neighbor Search bottleneck.<n>We show that PANORAMA affords a 2--30$times$ end-to-end speedup with no recall loss.
  arXiv  Detail & Related papers  (2025-10-01T06:38:45Z)
• Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets [16.768212375976546]
  We introduce a set of novel data structures and algorithmic methods for sparse ANNS.<n>Our contributions range from a theoretically-grounded sketching algorithm for sparse vectors to reduce their effective dimensionality.<n>Our final algorithm, dubbed Seismic, reaches sub-millisecond latency with high accuracy on a large-scale benchmark dataset.
  arXiv  Detail & Related papers  (2025-09-29T14:02:45Z)
• CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search [9.557937699715124]
  Approximate nearest neighbor search (ANNS) is a crucial problem in information retrieval and AI applications.<n>We propose a novel routing strategy named CRouting, which bypasses unnecessary distance computations.<n>Our experiments show that CRouting reduces the number of distance computations by up to 41.5% and boosts queries per second by up to 1.48$times$ on two predominant graph indexes.
  arXiv  Detail & Related papers  (2025-08-30T05:27:09Z)
• FFT-based Dynamic Subspace Selection for Low-Rank Adaptive Optimization of Large Language Models [49.397861654088636]
  We propose a two-step procedure to approximate SVD/QR-based gradient projections into lower-dimensional spaces.<n>We show that our strategy achieves faster runtime and reduced memory usage by up to $25%$ across different model sizes.
  arXiv  Detail & Related papers  (2025-05-23T14:37:00Z)
• Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization [0.8786066051474574]
  The Hierarchical Navigable Small World (HNSW) algorithm is widely used for approximate nearest neighbor search.<n>We propose a novel algorithm that mitigates local optima and cluster disconnections while enhancing the construction speed, maintaining inference speed.<n> Experiments on various benchmarks and datasets showed that our algorithm outperforms the original HNSW in both accuracy and speed.
  arXiv  Detail & Related papers  (2025-01-23T10:20:12Z)
• Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining [61.09807522366773]
  We introduce an algorithm that approximates the softmax with provable bounds and that dynamically maintains the tree. In our study on datasets with over twenty million targets, our approach cuts error by half in relation to oracle brute-force negative mining.
  arXiv  Detail & Related papers  (2023-03-27T15:18:32Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Mind Mappings: Enabling Efficient Algorithm-Accelerator Mapping Space Search [7.596028906226877]
  This paper presents a novel Mind-based search foraccel-based search space. We derive differentiable approximations to the otherwise nonsmooth$optimal mapping space. With a differentiable approximation, we can compare high-bound efficient algorithms to find Mind-based search schemes.
  arXiv  Detail & Related papers  (2021-03-02T06:11:58Z)
• ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding [86.40042104698792]
  We formulate neural architecture search as a sparse coding problem. In experiments, our two-stage method on CIFAR-10 requires only 0.05 GPU-day for search. Our one-stage method produces state-of-the-art performances on both CIFAR-10 and ImageNet at the cost of only evaluation time.
  arXiv  Detail & Related papers  (2020-10-13T04:34:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.