ParisKV: Fast and Drift-Robust KV-Cache Retrieval for Long-Context LLMs

KV-cache retrieval is essential for long-context LLM inference, yet existing methods struggle with distribution drift and high latency at scale. We introduce **ParisKV**, a drift-robust, GPU-native KV-cache retrieval framework based on collision-based candidate selection, followed by a quantized inner-product reranking estimator. For million-token contexts, ParisKV supports CPU-offloaded KV caches via Unified Virtual Addressing (UVA), enabling on-demand top-$k$ fetching with minimal overhead. ParisKV matches or outperforms full attention quality on both **long-input** and **long-generation** benchmarks. It achieves state-of-the-art long-context decoding efficiency: it matches or exceeds full-attention speed even at batch size 1 for long contexts, delivers up to **2.8$\times$** higher throughput within full attention’s runnable range, and scales to **million-token** contexts where full attention runs out of memory. At million-token scale, ParisKV reduces decode latency by **17$\times$** and **44$\times$** compared to MagicPIG and PQCache, respectively—two state-of-the-art KV-cache top-$k$ retrieval baselines; code is available at https://github.com/amy-77/ParisKV/tree/main.

Large language models can read and generate very long texts, but doing so requires storing and searching through a large amount of past information, which makes inference slow and memory-intensive. ParisKV is a new system that helps language models efficiently find the most useful parts of this stored information when processing long contexts. Instead of checking everything, ParisKV quickly narrows down the important candidates and retrieves only the most relevant information. This makes long-context inference faster and more memory-efficient, while maintaining the model’s answer quality. Our results show that ParisKV can support much longer inputs and generations than standard approaches, and can be especially useful when full attention becomes too expensive or runs out of memory.