EVP+FLAS: New ANNS method speeds LLM embedding search

Approximate Nearest Neighbor Search (ANNS) is a critical bottleneck in retrieval-augmented generation (RAG) and large-scale LLM inference. In a new arXiv preprint, researchers Nico Hezel and colleagues tackle two challenging tasks from the 2026 SISAP Indexing Challenge: k-Nearest Neighbor Graph construction on 1024-dimensional BGE-M3 embeddings (Task 1) and Maximum Inner Product Search (MIPS) on unnormalized Llama-3.2-8B features (Task 2). The goal is to balance construction speed with high recall under rigorous constraints, a key hurdle for production systems.

To optimize both tasks, the team introduced two key innovations. For quantization, they employ Equi-Voronoi Polytopes (EVP), which efficiently partition the high-dimensional space and reduce computational overhead while maintaining accuracy through targeted reranking. For MIPS, they transform the asymmetric inner product into a Euclidean search space via dimensionality augmentation, enabling the use of standard ANNS algorithms. The standout contribution is Fast Linear Assignment Sorting (FLAS), a 1D presorting mechanism applied before graph construction. FLAS dramatically improves spatial locality and cache hit rates during graph traversal, reducing query latency. The full source code is available on GitHub, making these techniques immediately accessible for practitioners building high-dimensional vector search systems.