LSH-KV: Efficient KV Cache Retrieval for Long-Context LLM Inference via Locality-Sensitive Hashing

Abstract

As large language models increasingly support long-context inference, the computation and memory access overhead of attention and KV caches have become critical bottlenecks for inference latency and system scalability. Existing approaches mitigate these costs through KV cache dropping, approximate attention, or system-level optimizations, but often incur non-trivial trade-offs between efficiency, accuracy, and implementation complexity. In this work, we propose LSH-KV, a coarse-to-fine KV retrieval framework for efficient long-context LLM inference. LSH-KV uses locality-sensitive hashing (LSH) as a lightweight, training-free coarse partitioning layer for similarity-preserving organization of global KV entries. Within each hash bucket, LSH-KV further uses product quantization with offline-precomputed codebooks for efficient approximate similarity estimation, followed by exact re-ranking to preserve attention accuracy. To further improve system efficiency, LSH-KV introduces a score-aware block-level cache management strategy that aligns KV movement between CPU and GPU with retrieval relevance. Experimental results on long-context benchmarks demonstrate that LSH-KV significantly reduces end-to-end inference latency while preserving generation quality, even when selective attention is performed using only a fraction of the input tokens. These results show that LSH-KV enables scalable, robust, and accurate inference under long-context settings. The code is available at https://github.com/HarryFunn/lsh-kv.