acceptodds
Under review as a conference paper at ICLR 2027

RDKV: Rate-Distortion Bit Allocation for Joint Eviction and Quantization of the KV Cache

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 (Rate-Distortion 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 via Lagrangian relaxation. 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 decode speedup and peak memory reduction with 128K context length, while maintaining comparable performance.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, KV cache compression, efficient inference, quantization, long-context inference

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_3uQuOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes RDKV, a rate-distortion framework for jointly optimizing token/channel eviction and quantization of the KV cache. The paper argues that eviction and quantization should not be treated as two independent compression operations. Instead, they can be viewed as different points on a single bit-allocation curve, where zero bits correspond to eviction and positive bit-widths correspond to quantized retention.

For the V cache, RDKV derives token importance from the cumulative attention received by each token. For the K cache, it derives channel importance from the perturbation of the attention logits caused by removing a channel. These importance weights are combined with empirical quantization-distortion estimates to formulate a discrete rate-distortion allocation problem over the bit-width set {0, 2, 4, 8, 16}. The resulting multiple-choice allocation problem is approximately solved using Lagrangian relaxation and one-dimensional bisection. The paper also introduces a TriZone packed layout to execute mixed-bit decoding without first expanding the compressed cache back to FP16.

The method is evaluated on LongBench, Needle-in-a-Haystack, RULER, and InfiniteBench using LLaMA-3.1-8B-Instruct as the primary model, with additional experiments on Mistral-7B, Qwen3-4B, LLaMA-2-13B, and Qwen2.5-72B. On LLaMA-3.1-8B-Instruct, RDKV achieves the highest LongBench average among the evaluated compression baselines at all reported budgets. At a budget of 1024L, it obtains 49.47 compared with 49.82 for FullKV, while at a more aggressive budget of 64L it obtains 45.97 compared with 43.23 for SnapKV plus ZipCache. At 128K context length, the paper reports approximately 4.5x lower decoding latency and a reduction from 58.1 GB to 30.5 GB peak memory relative to FullKV FlashAttention-2 decoding.

Critical strengths
  1. The paper provides a clean and meaningful unification of KV-cache eviction and quantization. The rate-distortion formulation explains why binary eviction can be too coarse and why quantizing every token can waste bits on low-impact cache units. The action-space ablation supports this motivation: at the 128L budget, the reported LongBench averages are 39.06 for quantization-only, 42.53 for eviction-only, 46.91 for the tri-state configuration, and 47.75 for the full RDKV action space.

  2. The paper connects the algorithmic formulation to an executable inference system. The TriZone layout is not merely a theoretical storage scheme: the paper reports approximately 18 ms/token with TriZone versus approximately 36 ms/token without it, and compares RDKV against FullKV and AdaKV on actual A100 hardware. This makes the work more practically relevant than a method evaluated only through reconstructed-cache accuracy.

Critical weaknesses
  1. The effective compression budget is not fully comparable to physical memory usage. In the implementation details, the matched budgets are computed from nominal bit-widths while quantization metadata such as scales and zero-points are explicitly excluded for all methods. At the very low budgets emphasized by the paper, these metadata and layout costs may be non-negligible. The paper should report the actual bytes transferred and stored, including all scales, zero-points, masks, padding, indices, and other TriZone metadata.

  2. The paper’s default allocation is static over the prefetched context, while the KV cache continues to grow during generation. The dynamic variant is evaluated only as an additional experiment and increases decoding latency from 18.70 to 24.73 ms/token while reducing peak memory only from 30.36 to 30.32 GB. Therefore, the strongest system claims primarily concern long-prefix decoding rather than long-input-and-long-output serving. The limitations of static allocation for long generated sequences should be made more explicit, and end-to-end results with realistic output lengths would strengthen the paper.

Questions for authors
  1. In Appendix B, the paper states that scales and zero-points are excluded from the matched-budget accounting. What are the effective physical compression ratios after including all quantization metadata, per-token/per-channel information, padding, masks, and TriZone packing overhead?

  2. The additive objective in Eq. (6) treats the distortion caused by each cache unit as separable. The validation in Appendix I uses six held-out 8K prefixes and 41 matched-budget allocations, obtaining Spearman correlations of 0.762 and 0.769 with end-to-end vocabulary KL. Can the authors provide a larger validation across models, context lengths, and task distributions, and report whether the surrogate also predicts downstream task accuracy?

  3. How are the 32 calibration sequences drawn from LongBench prefixes separated from the LongBench evaluation examples? Please clarify whether the calibration data are disjoint at the document, task, and test-example levels.

  4. The paper uses an equal K/V budget split by default and reports a small sweep over ratios 0.4, 0.5, and 0.6. How sensitive is the allocation to this choice on the other model families, especially LLaMA-2-13B and Qwen2.5-72B?

  5. The paper reports that RDKV outperforms the best evaluated baseline by 9.1% on average. Please provide the exact aggregation procedure for this number, including the benchmarks, budgets, models, and whether the improvement is absolute or relative.

  6. How much additional computation is required to calculate the probe attention weights, empirical distortion tables, per-head allocation, and TriZone packing during prefill? The paper reports a 6% prefill overhead at 128K, but a breakdown for shorter contexts and different batch sizes would clarify the deployment trade-off.

  7. Why is HqeKV included only in an additional RULER comparison rather than in the main LongBench and system comparisons? Please discuss whether the baseline implementation or budget definition prevents a direct comparison.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 3uQu [Part 1]

We would like to sincerely thank Reviewer 3uQu for providing a detailed review and insightful suggestions.

W1 & Q1 — Physical Memory Accounting and Budget Fairness

Following your suggestion, we measured the effective compression ratios with overhead counted. Including scales, zero-points, indices, padding and allocation rounding, the effective compression ratio at 128K context and 1024L1024L budget is 89.0×89.0\times for the submitted implementation with mask removal. Our further compaction raises it to 119.1×119.1\times, compared with 128×128\times when metadata is ignored. The storage breakdown at 1024L1024L (MiB, averaged over 100 RULER inputs, 50 each at 16K and 64K) is:

ComponentOriginal RDKV (mask-removed)Compacted RDKV
KV payload127.99127.99
Scales + zero-points6.094.22
Indices / metadata3.330.88
Alignment padding39.774.82
Allocation rounding0.160.18
Total177.34 (+38.6%)138.08 (+7.9%)

The original FP32 padding mask is redundant and has been removed without changing the output, so masks contribute no storage after the revision.

More details, including the benchmark comparison under matched KV-cache storage and the impact on decoding latency, are provided in the Details of Revision 1 under the Summary of Revisions and Global Response. The results of each task and the nominal-budget mapping are added in Appendix N of the revised PDF. The updated implementation of both versions is included in the revised supplementary material.

W2 — Static Allocation and Long-Output Serving

Following your suggestion, we extend our evaluation to long-output serving to assess the end-to-end efficiency and overhead of periodic re-budgeting. We evaluate Blockwise RDKV with a re-budgeting interval of M=256 against FullKV (FA2) on LLaMA-3.1-8B-Instruct, using a 120K-token input and generating 1K, 2K, and 4K tokens under Btotal=1024LB_{\mathrm{total}}=1024L.

Output lengthMethodE2E latency (s)TPOT (ms)Peak memory (GB)
1KFullKV106.678.6648.67
Blockwise RDKV51.023.1129.42
2KFullKV187.678.9448.81
Blockwise RDKV80.426.1529.42
4KFullKV352.779.8349.08
Blockwise RDKV162.333.0229.42

Across all output lengths, Blockwise RDKV achieves 2.09–2.33× end-to-end speedup and 1.65–1.67× peak-memory reduction over FullKV. Periodic compression accounts for only 8–9% of total execution time, including all re-budgeting and packing operations.

As output length increases, TPOT rises from 23.11 to 33.02 ms due to periodic compression and the growing number of compressed blocks processed during decoding. However, RDKV maintains clear end-to-end gains at all tested length of output.

We will incorporate these results into the revised manuscript and clarify the limitations of long-output serving.

AuthorsOpenReview ↗

Response to Reviewer 3uQu [Part 2]

Q2 — Additive Surrogate Validation

Following your suggestion, we extend the additive surrogate validation across additional models, context lengths, and task distributions. We also examine its relationship with downstream task accuracy.

Extended Validation. We extend the evaluation in Appendix I to LLaMA-3.1-8B and Qwen3-4B across 8K–32K contexts, two cache budgets (128L and 512L), and five task categories from LongBench and RULER. Following the same 41-allocation validation protocol, the surrogate maintains Spearman correlations of approximately 0.75 with end-to-end KL, consistent with the original results (0.762/0.769).

ModelPrefixesρ (128L)CV R² (128L)ρ (512L)CV R² (512L)
LLaMA-3.1-8B720.7470.9670.7470.917
Qwen3-4B720.7550.9460.7540.901
Combined1440.7510.9530.7530.909

Surrogate–downstream accuracy validation. We further evaluate LLaMA-3.1-8B on all 11 RULER tasks at 8K, 16K, and 32K under two cache budgets, using 100 samples per task. We compare ten allocation variants and measure the Spearman correlation between surrogate distortion and downstream accuracy. The experimental results are shown below.

Method8K / 128L8K / 512L16K / 128L16K / 512L32K / 128L32K / 512L
RDKV (Heuristic)71.790.569.785.266.479.5
RDKV (MCKP)73.994.772.690.067.683.2

We report correlations across all ten allocations, eight allocations sharing the same K/V budget split, and six progressively perturbed allocations.

Allocation Set8K / 128L8K / 512L16K / 128L16K / 512L32K / 128L32K / 512LMean
All 10 allocations−0.81−0.70−0.79−0.76−0.84−0.79−0.78
Same K/V split (8)−0.90−0.83−0.90−0.83−0.90−0.90−0.88
Graded perturbations (6)−0.94−0.94−0.94−0.94−0.94−0.94−0.94

The consistently negative correlations indicate that lower surrogate distortion is associated with higher downstream accuracy across all six settings.

Q3 — Calibration Data Separation

Thank you for raising this question. We audited the calibration protocol and conducted additional experiments to verify the impact of calibration data separation.

The original LongBench calibration pipeline did not explicitly enforce disjointness from evaluation data. To address this, we constructed a new calibration set using 32 sequences of 16K tokens from WikiText-2 train. We verified that these sequences have no exact or near-duplicate matches with the 14,750 evaluation inputs under our overlap criteria. Calibration uses only KV reconstruction errors, without evaluation labels or scores.

We then repeated downstream evaluations, changing only the calibration table.

BenchmarkOriginalIndependentΔ (pp)
LongBench 128L47.8247.71-0.12
LongBench 512L49.2149.26+0.05
RULER 16K95.6695.30-0.36
RULER 64K80.0679.76-0.30

The performance differences are within 0.36 percentage points across all four settings. These findings are consistent with the calibration robustness results in Appendix J, which further evaluates cross-corpus, cross-model, and calibration-free variants. We will clarify the calibration protocol and include the new data-isolation results in the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer 3uQu [Part 3]

Q4 — Cross-Model K/V Budget Split Sensitivity

Following your suggestion, we extend the K/V budget split ablation to LLaMA-2-13B-Chat and Qwen2.5-32B-Instruct across three cache budgets.

ModelBudgetrK=0.4r_K=0.4rK=0.5r_K=0.5rK=0.6r_K=0.6
LLaMA-2-13B128L29.4229.4629.11
LLaMA-2-13B256L29.8129.7129.71
LLaMA-2-13B512L30.1029.9629.78
Qwen2.5-32B128L45.8746.3746.02
Qwen2.5-32B256L47.1447.7247.12
Qwen2.5-32B512L48.0348.4548.18

The optimal split varies slightly across models. LLaMA-2-13B favors rK=0.4r_K=0.4 at larger budgets, while Qwen2.5-32B consistently favors rK=0.5r_K=0.5. Overall, the equal split performs best in four of six settings and remains within 0.14 accuracy points (less than 0.5% relative) of the best tested ratio in the remaining two. We therefore recommend rK=0.5r_K=0.5 as a robust default without model-specific tuning.

Since the original GH200 environment is no longer accessible, all configurations, including rK=0.5r_K=0.5, were rerun under identical settings on A100 GPUs to ensure consistent comparisons. Due to computational and rebuttal time constraints, we evaluate Qwen2.5-32B instead of Qwen2.5-72B and will include the 72B results in the revised manuscript.

Q5 — Aggregation of the 9.1% Improvement

The 9.1% is a relative improvement, averaged over 12 settings on LLaMA-3.1-8B-Instruct (LongBench at five budgets, RULER at six lengths, and InfiniteBench). The reference is ThinK, the baseline with the highest average score across these settings (61.31, vs. 60.73 AdaKV, 60.60 SnapKV, 59.34 SnapKV+ZipCache). We compute the relative gain over ThinK in each setting and take the mean. We will state this clarification in the revision.

Q6 — Prefill Computation and Overhead

Following your question, we extend the prefill overhead evaluation across context lengths, batch sizes, and storage-optimized implementations on LLaMA-3.1-8B-Instruct (A100-64GB, 1024L budget).

Context-length sensitivity. With repeated measurements (median of 3 runs, HF generate FullKV baseline as in Appendix H.1), RDKV adds 4.8% to TTFT at 128K and batch size 1, or 7.4% against the faster 8K-chunked FullKV prefill. The overhead increases to 12% at 64K and 31% at 32K. Table 12 reports 6.0% at 128K from an earlier single measurement.

Batch-size sensitivity. Measured against the FullKV forward pass in a separate sweep at 128K, the overhead decreases slightly from 5.2% to 4.5% as the batch size grows from 1 to 4. FullKV cannot accommodate batch size 4 on the same GPU.

We will update Table 12 with the repeated measurements and add the context-length and batch-size sweeps in the revision.

Storage optimization. We additionally evaluate Compacted RDKV against the submitted implementation under identical conditions. The compacted implementation reduces KV-cache storage from 208.4 MiB to 137.6 MiB (−33.97%), with only 0.5% additional TTFT and 1.02% additional decode latency. Both implementations produce identical generated outputs. The compacted RDKV implementation is included in the updated supplementary code submitted with this rebuttal.

Q7 — HqeKV Baseline Coverage

We previously compared RDKV with HqeKV only on RULER because its fixed context lengths allow budget matching. On LongBench, varying input lengths and discrete allocation granularity prevent HqeKV's fixed compression ratios from exactly matching RDKV's fixed bit budget across examples. Following your suggestion, we extend the comparison with HqeKV to system performance.

We evaluate both methods on the same A100-64GB using LLaMA-3.1-8B-Instruct, batch size 1, context lengths from 16K to 128K, and 1,024 generated tokens. Both methods use their optimized decoding implementations, with inference-time compression overhead included.

MetricRDKVHqeKV
Decode latency18–20 ms/token49–62 ms/token
End-to-end latency21–49 s52–92 s
KV-cache storage137–138 MiB220–257 MiB

Under nominally matched bit budgets, RDKV achieves 2.7–3.3× faster decoding and 1.9–2.7× end-to-end speedup, with comparable TTFT. HqeKV also uses 1.6–1.9× more physical prompt KV storage, mostly quantization metadata. Even when HqeKV's physical storage is reduced to match RDKV's at 16K–64K, its decoding latency remains 50–56 ms/token.

With these responses, we hope we have addressed your concerns. If so, we would be grateful if you would consider raising your score, and we are glad to clarify anything further. We will add the relevant clarifications and additional results to the revised manuscript, following your helpful comments. Thank you again for your time and thoughtful consideration.

Reviewer_9rTqOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

RDKV casts KV cache compression as a rate-distortion problem where eviction and quantization are optimized jointly as end-points of a bit allocation scheme. It assigns each token or channel a bit-width based on the distortion compression on that token or channel would induce on the attention computation. Experiments on multiple benchmarks show it outperforming baselines and achieving speedup compared to full-cache FlashAttention-2.

Critical strengths
  1. The experiments across models, benchmarks, and protocols clearly show that RDKV outperforms other bit allocation methods in several scenarios.
  2. The rate-distortion formulation provides a consistent rule for choosing between eviction and quantization for different tokens and channels.
Critical weaknesses
  1. The importance of the specific proposed allocator remains unclear. A comparison with a simpler importance-ranked mixed-precision heuristic on downstream benchmarks would help isolate this contribution.
Questions for authors
  1. How do the accuracy comparisons change when the budget are matched for the different methods when quantization metadata such as scales and zero-points are included?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 9rTq

We would like to sincerely thank Reviewer 9rTq for providing a detailed review and insightful suggestions.

W1 — Importance-Ranked Mixed-Precision Heuristic

Following your suggestion, we implement a simple importance-ranked mixed-precision heuristic to isolate the contribution of the MCKP allocator. Instead of solving the rate-distortion optimization, the heuristic ranks units by importance and assigns 16/8/4/2-bit precision in a fixed 1:2:4:8 ratio, under the same cache budget. The remaining units are evicted. All other parts of the pipeline remain unchanged.

We evaluate both methods on LongBench across five cache budgets and RULER across six context lengths. The results are shown below.

LongBench (16-task average)

Method64L128L256L512L1024L
Best Baseline43.2346.2447.3047.9648.84
RDKV (Heuristic)45.2247.3648.2248.9049.40
RDKV (MCKP)45.9747.7548.7349.2249.47

RULER (11-task average, 1024L budget)

Method4K8K16K32K64K128K
Best Baseline92.0386.4481.4575.9474.5962.85
RDKV (Heuristic)98.4297.6193.6285.8978.4465.18
RDKV (MCKP)98.6298.6195.6588.2880.0766.95

These results show that MCKP consistently outperforms the importance-ranked heuristic. Moreover, the heuristic itself outperforms the evaluated baselines. It further shows the benefit of joint eviction and quantization even without optimal allocation.

Q1 — Actual-Memory-Matched Accuracy Comparison

Following your suggestion, we compare accuracy under matched KV-cache storage. For each target, we reduce RDKV's nominal budget until its KV-cache storage, including all compression overhead (scales, zero-points, indices and padding), matches the FP16 size of the target. Baselines are evaluated with their compression overhead ignored, which makes the comparison conservative for RDKV. Below shows the result.

LongBench (16-task average) under matched KV-cache storage:

KV-cache storage64L128L256L512L1024L
Best baseline, overhead not counted43.2346.2447.3047.9648.84
Original RDKV (mask-removed), overhead counted42.7946.8448.0548.6449.48
Compacted RDKV, overhead counted45.5147.6148.6149.0149.64

RULER (11-task average) under 1024L KV-cache storage:

Method4K8K16K32K64K128KAvg.
Best baseline, overhead not counted92.0386.4481.4575.9474.5962.8578.48
Original RDKV (mask-removed), overhead counted98.4497.5693.7086.3578.9165.6886.77
Compacted RDKV, overhead counted98.5998.3495.1987.9479.8166.6287.75

Across the 11 comparisons (5 LongBench budgets and 6 RULER context lengths), Original RDKV (mask-removed) outperforms the best baseline in 10, and Compacted RDKV outperforms it in all 11.

The selected nominal budgets, impact on decoding latency and the KV-cache storage breakdown are provided in the Details of Revision 1 under the Summary of Revisions and Global Response. The results of each task and the nominal-budget mapping are added in Appendix N of the revised PDF. The updated implementation of both versions is included in the revised supplementary material.

With these responses, we hope we have addressed your concerns. If so, we would be grateful if you would consider raising your score, and we are glad to clarify anything further. We will add the relevant clarifications and additional results to the revised manuscript, following your helpful comments. Thank you again for your time and thoughtful consideration.

Thank you for your detailed response. I will maintain my score of acceptance and raise my soundness score.

Thank you for your positive feedback and for taking the time to review our additional results. We appreciate your decision to raise the soundness score.

Reviewer_PZ7XOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes RDKV, a KV-cache compression method that treats eviction and quantization as choices in a rate-distortion allocation problem. The method derives importance weights for V-cache tokens and K-cache channels from attention statistics, and combines them with calibrated distortion tables to assign bit-widths from 0 to 16 under a cache budget. Allocation is performed after prefill using Lagrangian relaxation, while newly generated KV states remain in FP16 by default. The paper also proposes TriZone, a packed cache layout that fuses dequantization into attention. Experiments on LongBench, RULER, and InfiniteBench across five LLMs report improved accuracy at nominally matched cache budgets. The paper reports up to 4.5x decode speedup and 1.9x peak-memory reduction against FullKV at 128K context, with additional measurements of TTFT and end-to-end generation time.

Critical strengths
  1. The motivation behind the proposed method is clean. Treating eviction as a zero-bit choice gives a common framework for deciding which cache entries to remove and which to quantize.
  2. The reported gains are consistent across several model families and long context benchmarks. Also, the paper provides packed kernels and reports TTFT and e2e latency, including the compression overhead.
Critical weaknesses
  1. The main comparisons match nominal bitwidths but seem to exclude scales and zero points. Since these costs depend on quantization granularity, comparisons at matched actual KV-cache memory are needed to establish the memory-quality advantage.
Questions for authors
  1. How often is KV compression triggered under chunked prefill, and how does the overhead accumulate across chunks? Is it possible to observe the impact on TTFT and e2e latency, including any repeated allocation and repacking costs?
1 comment
AuthorsOpenReview ↗

Response to Reviewer PZ7X

We would like to sincerely thank Reviewer PZ7X for providing a detailed review and insightful suggestions.

W1 — Actual-Memory-Matched Accuracy Comparison

Following your suggestion, we compare accuracy under matched KV-cache storage. For each target, we reduce RDKV's nominal budget until its KV-cache storage, including all compression overhead (scales, zero-points, indices and padding), matches the FP16 size of the target. Baselines are evaluated with their compression overhead ignored, which makes the comparison conservative for RDKV.

LongBench (16-task average) under matched KV-cache storage:

KV-cache storage64L128L256L512L1024L
Best baseline, overhead not counted43.2346.2447.3047.9648.84
Original RDKV (mask-removed), overhead counted42.7946.8448.0548.6449.48
Compacted RDKV, overhead counted45.5147.6148.6149.0149.64

RULER (11-task average) under 1024L KV-cache storage:

Method4K8K16K32K64K128KAvg.
Best baseline, overhead not counted92.0386.4481.4575.9474.5962.8578.48
Original RDKV (mask-removed), overhead counted98.4497.5693.7086.3578.9165.6886.77
Compacted RDKV, overhead counted98.5998.3495.1987.9479.8166.6287.75

Across the 11 comparisons (5 LongBench budgets and 6 RULER context lengths), Original RDKV (mask-removed) outperforms the best baseline in 10, and Compacted RDKV outperforms it in all 11.

The selected nominal budgets, impact on decoding latency and the KV-cache storage breakdown are provided in Details of Revision 1 under the Summary of Revisions and Global Response. The results of each task and the nominal-budget mapping are added in Appendix N of the revised PDF. The updated implementation of both versions is included in the revised supplementary material.

Q1 — Chunked Prefill Overhead and End-to-End Latency

Following your suggestion, we evaluated RDKV with chunked prefill. Each chunk appends its KV states to the full-precision cache. After the final chunk, RDKV runs one round of scoring, per-head allocation, and packing over the complete prompt before emitting the first token. Each layer is packed once per request.

At 128K input tokens, we tested 1, 4, 8, 16, and 32 chunks. In every setting, compression ran exactly once per request, and its cost varied by less than 0.03 s across chunk counts, so it does not accumulate with the number of chunks.

MethodPrefill chunksTTFT (s)TPOT (ms)End-to-end latency (s)
FullKV128.8481.9112.73
FullKV1628.2582.7112.80
RDKV130.5818.049.00
RDKV1629.2518.948.60

We measured these results on one A100 64 GB with LLaMA-3.1-8B-Instruct, a 128K-token input, and 1,024 generated tokens. With 8K chunks, RDKV increases TTFT by 1.00 s (3.5%) and achieves a 2.32× end-to-end speedup over the FullKV baseline. Chunked prefill does not increase the TTFT of RDKV, since compression is performed only once per request.

With these responses, we hope we have addressed your concerns. If so, we would be grateful if you would consider raising your score, and we are glad to clarify anything further. We will add the relevant clarifications and additional results to the revised manuscript, following your helpful comments. Thank you again for your time and thoughtful consideration.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Revisions and Global Response

We sincerely thank all the reviewers for their insightful reviews and valuable comments, which are instructive for us to improve our paper further.

In this paper, we formulate KV-cache compression as a rate-distortion problem and show why eviction and quantization should be jointly optimized rather than treated separately. Building on this perspective, we propose RDKV, which jointly determines eviction and quantization through rate-distortion optimization. Experimentally, RDKV outperforms the strongest evaluated baseline by 9.1% on average across diverse benchmarks, and recovers 97.81% of FullKV accuracy with only 2.48% cache retention on LongBench. At 128K context length, RDKV further achieves up to 4.5× decoding speedup and 1.9× peak-memory reduction compared with full-cache FlashAttention-2 decoding.

The reviewers generally held positive opinions of our paper. We are encouraged that they find our method:

  • "clean and meaningful unification of KV-cache eviction and quantization" (Reviewer 3uQu)
  • "motivation behind the proposed method is clean" (Reviewer PZ7X)
  • "consistent rule for choosing between eviction and quantization" (Reviewer 9rTq)
  • "gains are consistent across several model families and long context benchmarks" (Reviewer PZ7X)
  • "outperforms other bit allocation methods in several scenarios" (Reviewer 9rTq)
  • "connects the algorithmic formulation to an executable inference system" (Reviewer 3uQu)

The reviewers also raised insightful and constructive concerns. We made every effort to address all the concerns by providing detailed descriptions and requested results. Here is the summary of the major revisions:

  1. Physical-memory accounting and matched-storage evaluation (Reviewer 3uQu, Reviewer PZ7X, Reviewer 9rTq): We provide a complete breakdown of physical KV-cache storage after removing the redundant mask. We also introduce layout compaction to reduce storage overhead and report the corresponding storage breakdown. We further evaluate accuracy under matched KV-cache storage. For the KV-cache storage mapping, latency impact, and more details, please see "Details of Revision 1" in the following comment.

  2. Comparison with an importance-ranked mixed-precision heuristic (Reviewer 9rTq): Following the reviewer’s suggestion, we implement an importance-ranked mixed-precision heuristic. Then we compare it with RDKV to isolate the contribution of the proposed MCKP allocator.

  3. Expanded surrogate validation (Reviewer 3uQu): Following the reviewer’s suggestion, we extend the additive surrogate validation across additional models, context lengths, and task distributions. We also examine the relationship between surrogate distortion and downstream task accuracy.

  4. Calibration data separation (Reviewer 3uQu): Following the reviewer’s question, we audit the original calibration protocol and construct an independent calibration set from WikiText-2. We verify its separation from evaluation data and repeat downstream evaluations using the new calibration set.

  5. Cross-model K/V budget split sensitivity (Reviewer 3uQu): Following the reviewer’s suggestion, we extend the K/V budget split ablation to more models. We evaluate different K/V budget ratios across multiple cache budgets to assess the robustness of the default equal split.

  6. Long-output serving evaluation (Reviewer 3uQu): Following the reviewer’s suggestion, we extend the end-to-end efficiency evaluation to longer generated sequences. We evaluate blockwise RDKV with periodic re-budgeting and analyze its latency and memory overhead.

  7. Chunked prefill overhead (Reviewer PZ7X): Following the reviewer’s question, we evaluate RDKV under different prefill chunk sizes. We examine the compression frequency and measure its impact on TTFT and end-to-end latency.

  8. Prefill overhead and batch-size sensitivity (Reviewer 3uQu): Following the reviewer’s question, we extend the prefill overhead analysis across different context lengths and batch sizes. We also evaluate the latency overhead of the compacted RDKV implementation.

  9. Additional HqeKV system comparison (Reviewer 3uQu): Following the reviewer’s suggestion, we extend the comparison with HqeKV to system-level efficiency. We evaluate decoding latency, end-to-end latency, and physical KV-cache storage under nominally matched cache budgets.

  10. Clarification of the reported 9.1% improvement (Reviewer 3uQu): Following the reviewer’s question, we clarify the aggregation procedure, including the evaluated benchmarks, cache budgets, and reference baseline.

The valuable suggestions from reviewers are very helpful for us to revise the paper to a better shape. We'd be very happy to answer any further questions.

Looking forward to the reviewer's feedback :D

AuthorsOpenReview ↗

Details of Revision 1

As all three reviewers raised concerns regarding physical-memory accounting and budget fairness, we provide a detailed response below.

Original RDKV (mask-removed). The submitted implementation stored an FP32 mask that marks which cache positions are padding. For example, it takes 23.82 MiB at 1024L1024L. However this mask is purely redundant, because the padding positions can be computed in the kernel from the per-head lengths we already store. So, we remove it in the submitted implementation without changing the output.

Compacted RDKV. Compacted RDKV additionally reduces the cross-head padding of the TriZone layout. It only changes how the cache is stored. The quantization decisions, packed codes and the attention computation remain the same. So the outputs are identical to the submitted implementation.

Overhead analysis. KV-cache storage breakdown of LLaMA-3.1-8B-Instruct at 1024L1024L (MiB), averaged over 100 RULER inputs (50 each at 16K and 64K):

ComponentOriginal RDKV (mask-removed)Compacted RDKV
KV payload127.99127.99
Scales + zero-points6.094.22
Indices / metadata3.330.88
Alignment padding39.774.82
Allocation rounding0.160.18
Total177.34 (+38.6%)138.08 (+7.9%)

In the mask-removed version, cross-head alignment padding accounts for 80.6% of the overhead. After compaction, scales, zero-points and indices account for only 4.0% of the payload. At 128K context and 1024L1024L budget, the effective compression ratio is 89.0×89.0\times for Original RDKV (mask-removed) and 119.1×119.1\times for Compacted RDKV, compared with 128×128\times when the overhead is ignored.

Latency. At 128K context, TPOT is 18.70 ms for the submitted implementation, 18.63 ms for Original RDKV (mask-removed) and 18.89 ms for Compacted RDKV (+1.0%).

Comparison with the same KV-cache storage. For each target, we reduce RDKV's nominal budget until its KV-cache storage matches the FP16 size of the target. The selected nominal budgets are listed below, where matching uses the mean over a fixed set of RULER inputs.

Target (MiB)64L (8)128L (16)256L (32)512L (64)1024L (128)
Original RDKV (mask-removed)23L (8.07)71L (15.98)169L (31.93)359L (64.01)731L (127.99)
Compacted RDKV51L (7.95)111L (15.97)230L (31.96)469L (63.97)947L (127.99)

Baselines are evaluated with their compression overhead ignored, which makes the comparison conservative for RDKV. The results on LongBench and RULER are listed below:

LongBench (16-task average) over different KV-cache storage:

KV-cache storage64L128L256L512L1024L
Best baseline, overhead not counted43.2346.2447.3047.9648.84
Original RDKV (mask-removed), overhead counted42.7946.8448.0548.6449.48
Compacted RDKV, overhead counted45.5147.6148.6149.0149.64

RULER (11-task average, 1024L KV-cache storage):

Method4K8K16K32K64K128KAvg.
Best baseline, overhead not counted92.0386.4481.4575.9474.5962.8578.48
Original RDKV (mask-removed), overhead counted98.4497.5693.7086.3578.9165.6886.77
Compacted RDKV, overhead counted98.5998.3495.1987.9479.8166.6287.75

With the compacted layout, RDKV leads the strongest baseline at every budget and every context length. The mask-removed version trails only at 64L (by 0.44), where its fixed per-head overhead is largest relative to the payload. The result shows that RDKV consistently outperforms the baselines, even when its overhead is counted while others are not.

The results of each task and the nominal-budget mapping are added in Appendix N of the revised PDF. The updated implementation of both versions is included in the revised supplementary material.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.