By Payman Behnam, Yaosheng Fu, Ritchie Zhao, Po-An Tsai, Zhiding Yu, Alexey TumanovSourcearXiv
Fork
Clone
git clone https://openversions.com/git/index/arxiv-2502-14051.git
Cite
Version link
https://openversions.com/index/arxiv-2502-14051/commit/5075a88384b5985fbeb45d4ccd35fa53b25fc0d5
Version identifier (commit hash)
5075a88384b5985fbeb45d4ccd35fa53b25fc0d5

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

Claims

Findings

Headline finding

RocketKV provides a compression ratio of up to 400x, end-to-end speedup of up to 3.7x, and peak memory reduction of up to 32.6% in the decode phase on an NVIDIA A100 GPU compared to the full KV cache baseline, while achieving negligible accuracy loss on a variety of long-context tasks.

On LongBench, RocketKV consistently outperforms DuoAttention, SnapKV, Quest, and SparQ across Llama3.1-8B-Ins, Mistral-7B-Ins-v0.2, and LongChat-7B-v1.5, especially under lower token budgets, achieving almost no accuracy loss on Llama3.1-8B-Ins at token budgets of 512 and above and only a 1.1% average accuracy drop at a token budget of 256.

On Needle-in-a-Haystack (NIAH), RocketKV achieves near Full-KV accuracy across Llama3.1-8B-Ins, Mistral-7B-Ins-v0.2, and LongChat-7B-v1.5 even with a token budget of 256, reaching 100% accuracy on Llama3.1-8B-Ins under a 256 token budget (over 400x compression at 109K max sequence length), whereas other methods suffer substantial accuracy drops.

On the RULER benchmark across Llama3.1-8B-Ins, Mistral-7B-Ins-v0.2, and LongChat-7B-v1.5 with varying sequence lengths, RocketKV outperforms all other compared methods across token budgets and sequence lengths, with negligible accuracy loss at short sequence lengths and widening accuracy gaps over other methods at longer sequence lengths.

RocketKV-MT, a variant of RocketKV for multi-turn scenarios, consistently outperforms existing methods on multi-turn SCBench and achieves accuracy nearly on par with an oracle top-k attention scheme (Exact-TopK) across all token budgets.

On Llama3.1-8B-Ins (FP16, batch size 1), RocketKV achieves up to 3.7x end-to-end speedup on an NVIDIA A100 GPU, up to 3.3x end-to-end speedup on an NVIDIA H100 GPU, and up to 32.6% peak memory saving at the decode phase compared to Full-KV.

Standalone Hybrid Sparse Attention (HSA) consistently outperforms single-dimension dynamic selection methods (Quest and SparQ) on Llama3.1-8B-Ins across LongBench, NIAH, and RULER, especially at low token budgets.

The adaptive compression decomposition mechanism (r=min⁡(0.2+0.06⋅log⁡2(c),0.8)r = \min(0.2 + 0.06 \cdot \log_2(c), 0.8)) provides comparable accuracy to the best static split factor r∈[0.3,0.7]r \in [0.3, 0.7] across different sequence lengths and token budgets on Llama3.1-8B-Ins.

Methods

RocketKV is a training-free two-stage KV cache compression framework that performs coarse-grain permanent KV cache eviction on input sequence tokens in the first stage using SnapKV (adapted for GQA via per-group token selection and using a pooling kernel size of 63), followed by fine-grain dynamic KV token selection in the second stage using Hybrid Sparse Attention (HSA).

Source excerpts

“As shown in Figure 3, RocketKV performs coarse-grain KV cache eviction in the first stage. The purpose of this stage is to remove KV tokens with low importance while keeping the majority of important tokens. In the second stage, it conducts fine-grain dynamic KV token selection on the remaining KV tokens, followed by top-k sparse attention.” · Show in paper

“To reduce KV token storage with GQA, we follow the Ada-KV work to perform token selection on a per-group basis according to aggregated per-group attention scores so that the selected KV tokens are shared across the entire attention group.” · Show in paper

“Since in our case, SnapKV is only used for coarse-grain KV token eviction at the first stage, we discovered that the optimal kernel sizes for pooling are much larger. We empirically set the kernel size to 63 in all our experiments.” · Show in paper

Hybrid Sparse Attention (HSA) performs dynamic KV token selection via two-dimensional reduction in three steps: (1) grouping keys into consecutive pages along the sequence dimension and storing element-wise maximum (K_max) and minimum (K_min) aligned along the head dimension; (2) finding k_1 largest absolute values of query q along the head dimension, fetching corresponding K_max or K_min entries based on the sign of q, computing element-wise max(q * K_max, q * K_min) on those k_1 dimensions, and selecting top-k_2 indices along the sequence dimension; (3) performing sparse attention on the predicted k_2 indices, with GQA compatibility achieved by summing q or |q| across the attention group.

Source excerpts

“In contrast, we propose hybrid sparse attention (HSA), which takes advantage of two-dimensional reduction, in both sequence and head dimensions together to achieve better estimation accuracy on KV token indices with top-k attention scores.” · Show in paper

“Our HSA algorithm can be decomposed into three steps: Step 1: Group tokens in key tensor into consecutive pages along the sequence dimension and store element-wise maximum (Kmax) and minimum (Kmin) values of each page as auxiliary storage similar to Quest.” · Show in paper

“Our HSA algorithm is fully compatible with GQA. To achieve this, we perform all key tensor selections on a per attention group basis. More details are shown in Algorithm 1 where we perform the sum of q or |q| in the group dimension as needed to guarantee that all attention heads within a group are making the same selection at each step.” · Show in paper

RocketKV-MT is a multi-turn variant of RocketKV that retains all KV tokens in memory across conversation turns without permanent eviction in the first stage, re-applying SnapKV filtering on the full accumulated KV history at each turn and restricting second-stage HSA dynamic selection to the filtered subset.

Source excerpts

“The core idea in RocketKV-MT is to avoid permanently evicting any KV tokens during the first stage; instead, all KV tokens are retained in memory across turns, ensuring that no potentially useful context is lost. Meanwhile, to preserve computational efficiency, the second stage still performs dynamic selection over the subset of KV tokens filtered by the first stage, similar to the original RocketKV.” · Show in paper

Adaptive compression decomposition splits an overall compression ratio c=S/tc = S/t into crc^r for the first stage and c(1−r)c^{(1-r)} for the second stage using r=min⁡(0.2+0.06⋅log⁡2(c),0.8)r = \min(0.2 + 0.06 \cdot \log_2(c), 0.8), and further splits c(1−r)c^{(1-r)} within HSA into ⌈c(1−r)/2⌉\lceil c^{(1-r)/2} \rceil along the sequence dimension and c(1−r)/⌈c(1−r)/2⌉c^{(1-r)} / \lceil c^{(1-r)/2} \rceil along the head dimension, where token budget tt accounts for both top-k estimation and top-k attention memory traffic.

Source excerpts

“For an overall compression ratio of c, we define a split factor r so that c is split into c^r for the first stage and c^(1-r) for the second stage, where 0 <= r <= 1. We use the following formula to adaptively determine r: r = min(0.2 + 0.06 * log2(c), 0.8)” · Show in paper

“For compression decomposition within HSA, we simply split the compression ratio c^(1-r) evenly between the sequence and head dimensions so that each dimension gets a compression ratio of c^(1-r)/2.” · Show in paper