Hitcher: Efficient GPU-based Vector Search via Cluster-Centric Kernel and Hitch-Ride Ordering
Open Access
- 20 April 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 2066-2075
Abstract
Similarity-based vector search, which retrieves the most similar vectors to a given query vector from a large vector dataset, underlies many applications such as search, recommendation, and Large Language Models (LLMs). Some systems run vector search on GPUs to enjoy GPU's high parallelism, but we observe that they are limited in query throughput and latency. In particular, their query-centric GPU kernel conducts computation independently for each query, failing to reuse data loaded to the GPU shared memory across queries and leading to a low GPU compute utilization. While their batch-based task reordering rearranges computation for queries in a batch to reduce CPU-GPU data transfer, but latency is prolonged since each query needs to wait for its slowest task. To tackle these problems, we propose Hitcher. Specifically, to reuse data across queries and improve GPU utilization, Hitcher implements a cluster-centric GPU kernel to batch computation on the same data for multiple queries. To reduce query latency, Hitcher adopts the hitch-ride ordering, which preserves the arrival order for query processing while batching computation across queries to improve efficiency. Hitcher can also offload computation tasks to the CPU to reduce CPU-GPU data transfer and utilize multiple GPUs. Experimental results show that Hitcher achieves up to 22× lower P99 query latency and 9× higher query throughput when compared with the state-of-the-art GPU-based vector query processing systems.Keywords
This publication has 34 references indexed in Scilit:
- CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs2024
- Learning Customized Visual Models with Retrieval-Augmented Knowledge2023
- SONG: Approximate Nearest Neighbor Search on GPU2020
- ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithmsInformation Systems, 2020
- A quantitative evaluation of unified memory in GPUsThe Journal of Supercomputing, 2019
- Video Representation Learning by Dense Predictive Coding2019
- FaceNet: A unified embedding for face recognition and clustering2015
- Understanding deep image representations by inverting them2015
- Optimized Product Quantization for Approximate Nearest Neighbor Search2013
- The inverted multi-index2012