Fast Vector Search via Two-Step Binary Prefiltering and SIMD-Accelerated Rescoring

ACM Transactions on Embedded Computing Systems

Abstract

Vector similarity search is a critical but resource-intensive component of Retrieval-Augmented Generation (RAG) pipelines, especially on edge devices. We address this challenge with a highly optimized two-step flat scan primitive using Single Instruction, Multiple Data (SIMD) instructions (AVX2 on x86, NEON on ARM). The first step uses a bandwidth-efficient binary sketch to prefilter candidates, and the second step applies a precise, SIMD-accelerated rescoring to refine the final ranking. We evaluate this primitive against multiple quantization and dimensionality reduction techniques, analyzing trade-offs in latency, accuracy, memory, and energy. On a PC with a 1.2 million vector dataset, our method achieves more than 120 × speedup over a non-SIMD float32 baseline while maintaining an NDCG@100 score of 0.99. On a Raspberry Pi 3 with a 60,000-vector subset, the same method reduces query latency by 39 × ∼ 59 × and energy consumption by 41 × against the same baseline, while achieving an NDCG@100 of 0.98. Our results demonstrate that effective flat scan optimization can deliver substantial performance and energy efficiency gains despite constrained memory bandwidth and limited compute resources.

Authors 3

1. Thorben Simon

   TU Dortmund University

   Affiliation as printed

   TU Dortmund

2. Yun-Chih Chen

   National Tsing Hua University

   Affiliation as printed

   Computer Science, National Tsing Hua University

3. Jian-Jia Chen Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University