Technical Summary: ParisKV

Problem Statement

Large Language Models (LLMs) are rapidly extending their context windows to millions of tokens, creating unprecedented pressure on inference efficiency. The KV-cache, which stores keys and values for autoregressive decoding, quickly dominates memory footprint and latency as context grows. Long-context decoding is inherently memory-bound, as each step requires reading a large volume of KV vectors, with bandwidth costs scaling linearly with context length.

While sparse/selective attention methods attempt to mitigate this by attending only to a Top-k subset of relevant past tokens, existing KV-cache retrieval approaches face three critical challenges in latency-sensitive, long-generation scenarios:

1. Speed–Quality Tradeoff: Lightweight approximate retrieval (e.g., coarse clustering, low-bit quantization) often sacrifices recall for speed. Recovering accuracy typically requires increasing the retrieval budget, which erodes the benefits of sparsity.
2. Decoding Drift: Centroids learned from clustering prefill keys become stale as generation continues. As decoding keys accumulate, the distribution shifts, causing a mismatch between prefill-only centroids and the true key distribution. This leads to severe recall collapse during long decoding steps in prior methods.
3. CPU-Bound Retrieval: When full KV caches are offloaded to CPU memory to save GPU space, retrieval often involves CPU-side search and CPU-to-GPU data transfer. This introduces approximation errors and makes CPU orchestration the dominant factor in end-to-end latency.

Methodology: The ParisKV Framework

ParisKV is a hardware-aware algorithm–system co-design for KV-cache retrieval that achieves fast decoding and stable recall under long input and/or long-generation (up to million-token scale), even in the presence of distribution drift.

Core Algorithmic Innovations

1. Drift-Robust Analytic Centroids:
Unlike prior methods that learn centroids from prefill keys, ParisKV transforms queries and keys into a stable, data-independent space.

• Normalization and Rotation: Keys and queries are $\ell_2$-normalized and subjected to a shared random orthogonal rotation (implemented via SRHT). This maps them onto a unit hypersphere.
• Analytic Centroids: Instead of learning centroids, ParisKV defines a set of uniformly distributed centroids on the unit hypersphere based on sign patterns (e.g., $\pm 1/\sqrt{m}$). Because these centroids are data-independent and uniformly distributed, any newly generated key during decoding will always be close to at least one centroid, preventing the "stale centroid" problem.

2. Two-Stage GPU-Native Retrieval Pipeline:
ParisKV implements a coarse-to-fine retrieval pipeline entirely on the GPU to avoid CPU bottlenecks.

• Coarse Candidate Generation (Collision-Based): The rotated keys are split into $B$ subspaces. Each subspace direction is assigned to the nearest analytic centroid. For a query, the system selects the top-$\rho$ most similar centroids in each subspace. Keys in these selected buckets receive votes (with tiered weights). The system sums votes across subspaces to generate a coarse integer score, pruning the search space to a small candidate set (e.g., top 5–10%).
• Candidate Reranking (RSQ-IP): The candidates are reranked using a calibrated inner-product estimator without accessing full-precision keys.
  • Quantization: Each subspace direction is encoded using a 4-bit code (1-bit sign + 3-bit magnitude) derived from rotation-induced Beta priors.
  • Calibration: A lightweight scaling factor ($w_{i,b}$) is precomputed during the prefill phase to correct for quantization alignment errors.
  • Estimation: The system estimates the raw attention score $\langle k, q \rangle$ using the formula: $\|q\|_2 \sum_{b=1}^B w_{i,b} \langle v_{i,b}, \tilde{q}_b \rangle$, where $v_{i,b}$ is the dequantized direction and $\tilde{q}_b$ is the rotated query. This allows high-fidelity reranking using only compact metadata.

System-Level Innovations

1. Unified Virtual Addressing (UVA) Offloading:
ParisKV offloads the full-precision KV cache to CPU memory but leverages UVA to allow GPU kernels to directly fetch only the selected Top-k KV pairs on demand. This bypasses explicit memcpy operations and CPU-side scheduling overhead, enabling the GPU to access CPU memory as if it were local.

2. Sliding-Window Update Mechanism:
To support unbounded generation, the KV cache is managed in four regions: Sink (early tokens on GPU), Local (recent tokens on GPU), Retrieval (offloaded historical tokens), and an Update Buffer. When the buffer fills, the oldest local tokens are evicted to the Retrieval zone (offloaded to CPU), and the buffer tokens are promoted to Local. This ensures retrieval metadata remains fresh while preserving fast access to both recent context and long-range history.

Key Contributions

1. Drift-Robust Analytic Centroids: A data-independent transformation (normalization + rotation) that maintains stable retrieval recall even under significant distribution shifts at the million-token scale, eliminating the need for learned centroids that degrade over time.
2. GPU-Native Coarse-to-Fine Pipeline: A retrieval system combining collision-based pruning and calibrated reranking (RSQ-IP) that achieves high-fidelity Top-k selection directly on compressed codes without CPU-side search.
3. Scalable UVA-Based Offloading: An implementation enabling on-demand KV fetching with minimal CPU intervention, allowing the system to scale to million-token contexts where full attention runs out of memory.
4. Extensive Evaluation: Demonstrated performance across long-generation reasoning and long-context understanding tasks.

Experimental Results

The authors evaluated ParisKV on long-generation reasoning benchmarks (GPQA-Diamond, MATH500, AIME25) and long-context understanding (LongBench-V2, RULER) across multiple model families (Qwen-3-8B, DeepSeek-R1-Llama-8B, etc.).

Accuracy:

• ParisKV matches or outperforms full attention quality on long-input and long-generation benchmarks.
• On AIME25, it improves pass@8 accuracy by +40 to +77 points over state-of-the-art baselines MagicPIG and PQCache.
• In 7 out of 9 settings, ParisKV matches or exceeds full attention accuracy, significantly outperforming prior retrieval baselines.

Efficiency:

• Throughput: ParisKV achieves up to 2.8× higher throughput than full attention within its runnable range.
• Latency at Scale: At the million-token scale (1M tokens), ParisKV reduces decode latency by 17× compared to MagicPIG and 44× compared to PQCache.
• Scalability: While full attention runs out of memory (OOM) at batch sizes $\ge 4$ for 128K contexts and $\ge 2$ for 256K contexts, ParisKV scales to batch sizes of 8 and 5, respectively. It remains runnable at 384K and 1024K contexts where full attention fails completely.

Significance and Claims

The paper claims that ParisKV addresses the fundamental challenges of distribution drift and retrieval latency in long-context LLM inference. By transforming keys onto a unit hypersphere and employing data-independent analytic centroids, the system eliminates the centroid staleness that plagues existing methods.

The authors assert that carefully designed KV-cache retrieval can simultaneously improve both efficiency and accuracy for long-context inference, even in the presence of drift. This opens new possibilities for deploying LLMs in latency-sensitive, long-generation applications (such as complex reasoning tasks) where previous methods either failed to scale or suffered from severe accuracy degradation. The work demonstrates that it is possible to achieve near-lossless quality while maintaining the speed benefits of sparse attention, even when the KV cache is offloaded to CPU memory.