RDKV: Rate-Distortion Bit Allocation for Joint Eviction and Quantization of the KV Cache
Junkai Zhang, Hang Guo, Luca Benini, Yawei Li, [0.5em] ETH Zurich · 2026
Read RDKV: Rate-Distortion Bit Allocation for Joint Eviction and Quantization of the KV Cache by Junkai Zhang, Hang Guo, Luca Benini, Yawei Li, [0.5em] ETH Zurich (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-08317.txt.
Introduction
Junkai Zhang, Hang Guo, Luca Benini, and Yawei Li unify two ways of shrinking the key-value cache that slows long-context language model inference. The cache grows with every token and is re-read at each decoding step, so serving long inputs is bound by memory, not arithmetic. Prior work either evicts tokens or quantizes them, rarely both.
Casting compression as a rate-distortion problem shows eviction and quantization are two ends of one bit-allocation scheme. Their RDKV method scores each token and channel by the distortion its compression would cause in attention, then hands out bits accordingly. Joint allocation squeezes the cache harder for the same quality loss.
Catalog record
| CREATOR | Junkai Zhang, Hang Guo, Luca Benini, Yawei Li, [0.5em] ETH Zurich |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.08317
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
RDKV: Rate-Distortion Bit Allocation for Joint Eviction and Quantization of the KV Cache Junkai Zhang, Hang Guo, Luca Benini, Yawei Li, [0.5em] ETH Zurich Abstract Large language models (LLMs) have shown strong performance across diverse tasks, but their inference with long input contexts is bottlenecked by memory size and bandwidth. The Key-Value (KV) cache size grows linearly with sequence length and needs to be re-read from off-chip high-bandwidth memory (HBM) to on-chip memory at every decoding step, resulting in memory-bound inference. Existing methods reduce the cache by either eviction or quantization, but typically treat the two in isolation. In this paper, we cast KV cache compression as a rate-distortion problem, under which eviction and quantization are two end-points of the same bit allocation scheme. This exposes the need to optimize them jointly, motivating our method, RDKV ( R ate- D istortion KV cache compression). RDKV derives the weight of each token or channel from the distortion that compression induces on the attention computation. Based on these weights, it assigns each token or channel a bit-width ranging from full precision down to zero bits guided by reverse water-filling, applied once after the prefilling stage. Experiments on LongBench, RULER, and InfiniteBench show that RDKV outperforms the best evaluated baseline by 9.1% on average. On LongBench it recovers 97.81% of full-cache accuracy with only 2.48% cache retention. Compared with full-cache FlashAttention-2 decoding, it achieves 4.5 × \times decode speedup and 1.9 × \times peak memory reduction with 128K context length, while maintaining comparable performance. 1 Introduction Large language models (LLMs) [ 1 , 2 , 3 ] have demonstrated strong performance from open-ended generation to complex multi-step reasoning. As these capabilities move into production, the input contexts they require have grown from thousands to hundreds of thousands of tokens. Retrieval-augmented generation [ 4 ] , multi-document reasoning, and agentic workflows all routinely operate at this scale. At these lengths, inference becomes memory-bound. Transformer decoding stores a Key-Value (KV) pair for every token in every layer. The cache therefore grows linearly with sequence length and reaches tens of gigabytes per request [ 5 ] . Because every generated token re-reads this entire cache through the attention computation [ 6 ] , memory traffic rather than arithmetic sets the per-token decode latency [ 7 ] . Reducing the cache footprint without retraining, while preserving generation quality, has thus become a central problem for efficient long-context inference [ 8 , 9 ] . A growing number of works address this bottleneck by compressing the KV cache after prefill. These methods fall along two axes: eviction and quantization. Eviction methods score each token or channel and keep the top-ranked units at full precision, dropping the rest [ 10 , 11 , 12 ] . Quantization methods retain every token and instead reduce the bit-width [ 13 , 14 ] . Yet cache units differ widely in importance: a few are critical, most are not. A binary keep-or-evict action leaves no precision tier for the broad middle, while mixed-precision quantization retains every token, including the many that contribute negligibly to the output. Recent analysis shows that combining eviction with quantization outperforms either action alone [ 15 ] . Several hybrids route each token among full-precision, low-bit, and evicted states [ 16 , 17 ] . But their routing scores remain heuristic and the budget ratios are preset or searched before the final assignment. A natural question is whether both the score and the allocation can be derived from a single objective function. Figure 1 : Left: Per-sequence weighted distortion \Delta\mathcal{D}=\sum_{u}w_{u}\,\varepsilon_{u}(b_{u}) ( equation 6 ) versus average bit-width \bar{b} . Lines: median across sequences; shaded: IQR. Lower bound : continuous relaxation (Prop. A.3 ). Right: LongBench score by task category at a per-layer cache budget of 128 FP16-equivalent tokens ( B_{\text{total}}=128L ), normalized by FullKV; per-task scores in table 1 . Eviction refers to Ada-SnapKV [ 26 ] in the right panel. Model: LLaMA-3.1-8B-Instruct [ 42 ] . In this paper, we present RDKV, a rate–distortion framework for KV cache compression. RDKV poses a bit-allocation problem: given a fixed bit budget, assign each token in the V cache and each channel in the K cache a bit-width to minimize a weighted distortion. The weight of each token or channel is defined as the deviation in the attention distribution or the attention logit when it is evicted. Reverse water-filling converts these weights into bit-widths, from full precision for critical units down to zero bits (eviction) for negligible ones. Eviction and quantization are thus at the two ends of one allocation curve, and are explored jointly rather than in a staged fashion. We make three contributions . (1) We formulate KV cache compression as a rate–distortion problem. The continuous optimum inherently mixes zero-rate (eviction) and finite-rate (quantization) units. Therefore, approximating this bound requires both actions in the same solver, while restricting to either alone leaves a clear gap, as figure 1 (left) shows on calibration data. (2) We instantiate the allocation as a discrete knapsack over hardware-supported bit-widths and solve it via reverse water-filling with Lagrangian relaxation. (3) We realize the resulting mixed-bit cache with TriZone, a packed-decode layout that fuses dequantization into the attention kernel, turning the mixed-bit allocation into actual memory savings. Taken together, figure 1 (right) shows the empirical picture: RDKV approaches FullKV’s performance across all six categories while the strong baseline lags consistently. 2 Related Work Existing KV cache compression methods can be organized by the action they apply: eviction, quantization, or both. Meanwhile, they can also be organized by how the compression target is specified. We adopt the latter axis, distinguishing methods that target a prescribed compression ratio or tier schedule from methods that allocate a given active-cache budget. Compression-Ratio-Driven Methods. These methods reduce the stored representation of cache entries to reach a target compression ratio. Quantization methods such as KIVI [ 13 ] , KVQuant [ 18 ] , ZipCache [ 14 ] , and KVTuner [ 19 ] exploit asymmetric K/V quantization, outlier handling, salient-token preservation, or searched precision configurations to lower the bit-width of stored keys and values. QAQ [ 20 ] and MiKV [ 21 ] adapt precision by token or KV-pair importance, while AQUA-KV [ 22 ] exploits K/V dependencies and quantizes prediction residuals. Several recent hybrids add eviction as the lowest precision tier. HqeKV [ 17 ] uses a Tree-structured parzen estimator search (200 trials per setting) to determine the fraction of tokens at each bit-width; ARKV [ 16 ] estimates per-layer Original–Quantization ratios from prefill-time attention statistics, with scoring thresholds searched offline. Both methods rely on offline optimization before deployment, with HqeKV searching tier ratios and ARKV searching scoring thresholds. Budget-Driven Methods. These methods take an active-cache budget as input and decide which units remain available during decoding. KV cache eviction methods score each cache unit and retain the top-ranked subset under a fixed token count. StreamingLLM [ 23 ] keeps sink tokens and a recent window. H2O [ 10 ] , SnapKV [ 11 ] , Scissorhands [ 24 ] , and NaCl [ 25 ] use attention-derived token scores. AdaKV [ 26 ] , PyramidKV [ 27 ] , and CAKE [ 28 ] further distribute the