提升大模型嵌入向量的近邻搜索速度与效率，兼顾高召回率和低延迟。
Fast and Efficient Approximate Nearest Neighbor Search for High-Dimensional LLM Embeddings
- 用等距胞腔多面体实现高效量化，结合重排序保持高召回率。
- 通过维度扩展将内积搜索转为欧氏距离搜索，降低查询延迟。
- 引入一维预排序机制，显著提升缓存命中率和内存访问效率。
每年的 SISAP 索引挑战赛对近似最近邻搜索（ANNS）算法在严格约束下进行基准测试。本文提交了2026年版本的解决方案，涵盖两个任务：在1024维BGE-M3嵌入上构建k近邻图（Task 1），以及在未归一化的Llama-3.2-8B特征上执行最大内积搜索（MIPS，Task 2）。为优化构建速度，我们采用等距胞腔多面体（EVP）进行高效量化，并辅以针对性重排序策略以维持高召回率。针对MIPS，我们通过维度增强将非对称内积问题转换为欧氏空间搜索。为降低查询延迟并优化内存访问，我们在图构建前引入基于快速线性分配排序（FLAS）的一维预排序机制，显著提升了后续图遍历时的空间局部性和缓存命中率。源代码：https://github.com/Visual-Computing/sisap26-deglib
原文摘要 · Abstract (English)
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
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。