  As the field of Large Language Models (LLMs) continues to evolve, the context
length in inference is steadily growing. Key-Value Cache (KVCache), a crucial
component in LLM inference, has now become the primary memory bottleneck due to
limited GPU memory. Current methods selectively determine suitable keys and
values for self-attention computation in LLMs to address the issue. However,
they either fall short in maintaining model quality or result in high serving
latency. Drawing inspiration from advanced embedding retrieval techniques used
in the database community, we consider the storage and searching of KVCache as
a typical embedding retrieval problem. We propose PQCache, which employs
Product Quantization (PQ) to manage KVCache, maintaining model quality while
ensuring low serving latency. During the prefilling phase, we apply PQ to
tokens' keys for each LLM layer and head. During the autoregressive decoding
phase, for each newly generated token, we first identify important tokens
through Maximum Inner-Product Search (MIPS) using PQ codes and centroids, then
fetch the corresponding key-value pairs for self-attention computation. Through
meticulous design of overlapping and caching, we minimize any additional
computation and communication overhead during both phases. Extensive
experiments show that PQCache achieves both effectiveness and efficiency. It
maintains model quality even when only 1/5 of the tokens are involved in
attention, while attaining acceptable system latency.
