Key-Value (KV) cache plays a crucial role in accelerating inference in large language models (LLMs) by storing intermediate attention states and avoiding redundant computation during autoregressive generation. However, its memory footprint scales linearly with sequence length, often leading to severe memory bottlenecks on resource-constrained hardware. Prior work has explored offloading KV cache to the CPU while retaining only a subset on the GPU, but these approaches often rely on imprecise token selection and suffer performance degradation in long-generation tasks such as chain-of-thought reasoning. In this paper, we propose a novel KV cache management strategy, IceCache, which integrates semantic token clustering with PagedAttention. By organizing semantically related tokens into contiguous memory regions managed by a hierarchical, dynamically updatable data structure, our method enables more efficient token selection and better utilization of memory bandwidth during CPU-GPU transfers. Experimental results on LongBench show that, with a 256-token budget, IceCache maintains 99% of the original accuracy achieved by the full KV cache model. Moreover, compared to other offloading-based methods, IceCache attains competitive or even superior latency and accuracy while using only 25% of the KV cache token budget, demonstrating its effectiveness in long-sequence scenarios. The code is available on our project website at https://yuzhenmao.github.io/IceCache/.
Figures & tables
Figure 1: IceCache has the best trade-off between CUDA memory footprint and time-per-output-token (TPOT) on A100 at a 36k sequence length. Baselines are chosen to represent high-accuracy (Left) and memory-efficient (Right) methods.
Figure 2: Illustration of IceCache. (1) During the prefill stage, tokens are indexed into a hierarchical data structure (the DCI-tree) according to their semantic similarity in the transformed key-embedding space. Each leaf node of the DCI-tree corresponds to a physical memory page. (2) During the decoding stage, given a query q , IceCache performs a tree search to identify the top- k tokens most relevant to q . The zoomed-in section at the bottom illustrates that these relevant tokens (highlighted in yellow) tend to be clustered within the same leaf nodes and are stored together in corresponding memory pages. (3) After the query-aware retrieval, the pages containing the relevant tokens are selected, and all tokens within these pages are used in the subsequent sparse attention with q .
Figure 3: Illustration of DCI-tree and IceCache: The hierarchical data structure on the left visualizes the result of indexing key embeddings, DCI-tree, where each tree node stores metadata for the tokens, such as the key ID and node index. The tables on the right depict the mapping between nodes in the DCI-tree and the corresponding pages in physical memory. For each selected node, a mapping table is used to locate the memory region containing the associated key-value embeddings.
Figure 4
Figure 6: Passkey retrieval accuracy of IceCache on Llama3.1-8B-Instruct. The horizontal axis indicates the relative insertion position (%) of the passkey, while the vertical axis represents the context length in words. Results are presented for cache budgets of 256, 128, and 64. Notably, IceCache achieves 100% retrieval accuracy across all tested budget sizes.
Budget
Method
Single-Document QA
Multi-Document QA
Summarization
Few-shot Learning
Synthetic
Code
Avg.
NrtvQA
Qasper
MF-en
HotpotQA
2WikiMQA
Musique
GovReport
QMSum
MultiNews
TREC
TriviaQA
SAMSum
PCount
PRe
Lcc
RB-P
18409
3619
4559
9151
4887
11214
8734
10614
2113
5177
8209
6258
11141
9289
1235
4206
Llama-3.1-8B-Instruct
N/A
FULL
30.2
45.5
54.9
55.5
46.7
31.3
35.2
25.2
27.2
72.5
91.7
43.8
8.4
99.5
65.1
58.8
49.5
256
TOP- k
30.7
44.7
55.4
55.0
46.5
31.7
34.8
25.1
26.8
71.5
92.2
44.8
7.8
100.0
67.1
63.6
49.8
256
SKV
23.7
27.3
46.3
52.3
40.8
24.2
19.2
22.6
19.2
29.0
84.1
39.0
8.6
97.5
57.3
56.2
40.8
Table 1: Accuracy comparison of our method (ICE) with SnapKV (SKV), SteamingLLM (SLM), OmniKV (OKV), MagicPig (MPG), PQCache (PQC), ArkVale (AKV), Full KV (FULL) and ground-truth top- k (TOP- k ) on LongBench for Llama-3.1-8B-Instruct and Mistral-7B-Instruct. IceCache generally outperforms other methods across various KV-cache budgets and LLMs.
Budget
Method
Single-Document QA
Multi-Document QA
Summarization
Few-shot Learning
Synthetic
Code
Avg.
NrtvQA
Qasper
MF-en
HotpotQA
2WikiMQA
Musique
GovReport
QMSum
MultiNews
TREC
TriviaQA
SAMSum
PCount
PRe
Lcc
RB-P
18409
3619
4559
9151
4887
11214
8734
10614
2113
5177
8209
6258
11141
9289
1235
4206
Qwen3-32B
N/A
FULL
32.6
45.5
50.4
59.6
56.0
40.1
33.2
23.9
25.2
72.0
70.8
37.1
18.0
100.0
12.4
18.4
43.4
64
ICE
29.5
43.9
50.9
61.4
55.8
38.8
30.8
23.8
24.3
71.0
70.0
35.7
15.0
97.0
10.5
17.3
42.2
128
ICE
32.1
44.8
53.3
61.6
54.6
38.5
31.0
23.6
24.8
72.0
70.3
36.2
15.5
100.0
10.7
17.3
42.6
Table 2: Accuracy comparison of our method (ICE) with Full KV (FULL) on LongBench for Qwen3-32B and LongChat-7B-v1.5.
Figure 7: Latency comparison of IceCache and baseline methods on a 36k-token sequence.
Method
Budget
Accuracy
FULL
N/A
48.2
SKV
10%
44.7
SLM
10%
44.4
OKV
10%
42.7
MPG
10%
43.1
PQC
10%
46.2
Table 3: GSM8K CoT.
Figure 10
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Budget
Method
Single-Document QA
Multi-Document QA
Summarization
Few-shot Learning
Synthetic
Code
Avg.
NrtvQA
Qasper
MF-en
HotpotQA
2WikiMQA
Musique
GovReport
QMSum
MultiNews
TREC
TriviaQA
SAMSum
PCount
PRe
Lcc
RB-P
18409
3619
4559
9151
4887
11214
8734
10614
2113
5177
8209
6258
11141
9289
1235
4206
Llama-3.1-8B-Instruct
256
ICE(r)
29.1
43.6
53.4
55.1
44.3
29.0
31.8
24.3
26.2
72.0
91.1
41.0
7.2
100.0
60.7
53.1
47.7
Appendix
Table 5: Accuracy of IceCache (reuse) on LongBench.
Method
Completion Rate
Accuracy Once
Accuracy Range
Accuracy Periodic
Avg. Accuracy
Full KV
97.627
0.349
0.488
0.135
0.324
IceCache
95.322
0.377
0.454
0.164
0.331
PQCache
88.691
0.318
0.395
0.105
0.273
Appendix
Table 6: Accuracy comparison on LongGenBench for Llama-3.1-8B-Instruct.