Exact Nearest-Neighbor Search on Energy-Efficient FPGA Devices

Patrizio Dazzi, William Guglielmo, Franco M. Nardini, Raffaele Perego, Salvatore Trani · 2025

Read Exact Nearest-Neighbor Search on Energy-Efficient FPGA Devices by Patrizio Dazzi, William Guglielmo, Franco M. Nardini, Raffaele Perego, Salvatore Trani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16736.txt.

Introduction

Patrizio Dazzi and four co-authors run exact nearest-neighbor search on FPGA chips to save energy. Nearest-neighbor search finds the closest stored vectors to a query, a core task behind systems that use learned image and text embeddings. FPGAs are reconfigurable chips that can be tuned for one job.

The team offers two designs on one low-level setup. One streams data that cannot fit in chip memory and favors throughput. The other keeps data in memory and favors low delay per query. On public image and text data sets, both beat leading CPU systems on speed and energy use. Reported gains reach a scale-up factor above sixteen for throughput.

Catalog record

CREATORPatrizio Dazzi, William Guglielmo, Franco M. Nardini, Raffaele Perego, Salvatore Trani
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16736

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exact Nearest-Neighbor Search on Energy-Efficient FPGA Devices Patrizio Dazzi, William Guglielmo, Franco M. Nardini, Raffaele Perego, Salvatore Trani Abstract . This paper investigates the usage of FPGA devices for energy-efficient exact k k NN search in high-dimension latent spaces. This work intercepts a relevant trend that tries to support the increasing popularity of learned representations based on neural encoder models by making their large-scale adoption greener and more inclusive. The paper proposes two different energy-efficient solutions adopting the same FPGA low-level configuration. The first solution maximizes system throughput by processing the queries of a batch in parallel over a streamed dataset not fitting into the FPGA memory. The second minimizes latency by processing each k k NN incoming query in parallel over an in-memory dataset. Reproducible experiments on publicly available image and text datasets show that our solution outperforms state-of-the-art CPU-based competitors regarding throughput, latency, and energy consumption. Specifically, experiments show that the proposed FPGA solutions achieve the best throughput in terms of queries per second and the best-observed latency with scale-up factors of up to 16.6 × \times . Similar considerations can be made regarding energy efficiency, where results show that our solutions can achieve up to 11.9 × \times energy saving w.r.t. strong CPU-based competitors. 1. Introduction Top- k Nearest Neighbor ( k NN) search in multi-dimension spaces is a well-known problem, extensively studied in the literature. Given a query object q\in\mathbb{R}^{d} , a collection of objects of the same dimensionality and a distance function, it asks for finding the k objects in the collection having the smallest distance to the query. k NN search is a fundamental primitive in several areas, such as databases, information retrieval, recommender systems, pattern recognition, machine learning, and statistical data analysis. Despite the vast amount of studies discussing optimized algorithms and indexing data structures for k NN search, the problem of efficiently finding the data points closest to a given query is still a hot research topic. Its importance is due to the large number of applications and the growing importance and availability of complex data represented in high-dimension spaces. Most of the efforts to make k NN search efficient and scalable address the problem by relaxing it and searching for data points that are likely to be the nearest neighbor ones, i.e., by accepting some loss in accuracy with Approximate NN (ANN) search methods ( Li et al. 2020b ) . Indexing data structures for fast ANN search rely on quantization or hashing/binning techniques ( Pan et al. 2020 ; Andoni and Indyk 2008 ) . Such techniques typically cluster the data points in the collection based on the distance function and perform a search in two steps: first, the centroids of the clusters closest to the query are identified; second, a subset of clusters associated with the nearest centroids is visited exhaustively to determine the closest data points. Due to the curse of dimensionality, visiting all neighboring clusters is impractical, but any heuristics limiting the number of neighboring clusters visited may even severely impact the recall of these approaches ( Li et al. 2020b ) . Some recently proposed graph-based methods achieve competitive recall rates for ANN search ( Groh et al. 2022 ; Ren et al. 2020 ) . They work by building a partial representation of the k NN graph linking the points in the search space to their nearby points. Retrieval starts from a random node in the graph and proceeds iteratively by following at each step the edge connecting the node closest to the query, if any. All ANN search methods have to trade-off between accuracy and computational efficiency. On the other hand, exact k NN search over billions of high-dimension data points is challenging even when leveraging massive GPU parallelism ( Li et al. 2020b ) and sophisticated metric indexes ( Chen et al. 2022 ) . However, many applications require exact k NN search on collections of manageable size. These include, for example, public safety applications ( Chen et al. 2022 ) , data cleaning ( Arasu et al. 2006 ) , near-duplicate detection ( Kim and Lee 2012 ) , and bioinformatics ( Qin et al. 2011 ) . Given the high construction costs and the limited efficiency gain of metric indexes on small/medium datasets, a competitive method for retrieving k NN results is to perform an exhaustive search, i.e., comparing the query object with all the points in the collection with a brute force approach. Moreover, even when datasets are huge, either k NN or ANN search methods based on hashing/binning techniques rely on an exhaustive search to visit selected partitions of the search space. In this paper, we investigate using FPGA devices for energy-efficient k NN search. We propose two flexible solutions based on the same FPGA configuration, and we showcase their efficiency on high-dimension real-world datasets for image and text retrieval. Our work intercepts a relevant trend in the scientific community aimed at making query processing greener ( Scells et al. 2022 ) and AI models more efficient, sustainable and inclusive ( Schwartz et al. 2020 ; Bender et al. 2021 ) . In summary, we focus on sustainable AI inference using resource-constrained, energy-efficient devices and we contribute with: • two different FPGA solutions for energy-efficient AI inference based on exact k NN search in high-dimensional spaces. The first solution maximizes system throughput by processing in parallel a batch of k NN queries over a streamed dataset not fitting into the FPGA memory. The second one minimizes latency by processing a stream of incoming k NN queries over an in-memory dataset. • a rigorous methodology for assessing the proposed solutions with reproducible experiments conducted on publicly available image and text retrieval datasets with vectors varying from 769 to 4,960 dimensions. Our proposal’s throughput, latency, and energy consumption are compared with those of the optimized multi-threaded implementation available in the FAISS k NN library ( Johnson et al. 2019 ) . Results show that our FPGA solutions achieve the best throughput and latency, while enabling up to 11.9\times energy saving compared to a high-end multi-core CPU. Moreover, we show that the FPGA solution remarkably outperforms even a high-end GPU in application scenarios where it is not possible to batch the queries in large sets to fully exploit the GPU cores. The rest of the paper is organized as follows. Section 2 discusses the related work while Section 3 introduces our FPGA solution and details the logic organizations of its components. Section 4 details the experimental settings and discusses the results of the experiments conducted. Finally, Section 5 concludes the work and draws some future lines of investigation. 2. Related Work We restrict the survey of related work to the areas that are more relevant to our work, specifically the approaches for accelerating exhaustive NN search using parallel computational platforms, e.g., multi-threaded CPU ( Al-Hamoudi and Ahmed Biyabani 2014 ) , GPUs ( Garcia et al. 2008 ; Johnson et al. 2019 ) , and FPGA devices. Lu et al. design and implement CHIP-KNN, a high-performance k NN accelerator, which optimizes the off-chip memory access on cloud FPGAs with multiple High-Bandwidth Memory (HBM) banks ( Lu et al. 2020 ) . Given

Read the complete text