IceCache: Memory-Efficient KV-cache Management for Long-Sequence LLMs
Authors: Yuzhen Mao
Qitong Wang
Martin Ester
Ke Li
Venue: ICLR 2026 Poster (2026)
Keywords: LLM Inference; KV-cahce Optimization; Sparse Attention
Primary area: generative models

Abstract: 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/.

Published as a conference paper at ICLR 2026
ICECACHE: MEMORY-EFFICIENT KV-CACHE MANAGE- MENT FOR LONG-SEQUENT LLMS
Yuzhen Mao
Qitong Wang
Simon Fraser University, BC, Canada yuzhenm@sfu.co
Harvard University, Cambridge, USA qitonge seas harvard.edi
Martin Ester Simon Fraser University, BC, Canada ester@sfu.
Ke Li
Simon Fraser University, BC, Canada
ABSTRACT
Key-Value (KV) cache plays a crucial role accelerating inference in large lan- guage models (LLMs) by storing intermediate attention states and avoiding redun- dant computation during autoregressive generation. However, its memory footprint scales linearly with sequence length, often leading on resource-constrained hardware. Prior work has explored offloading K KV-cache 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
memory bottlenecks
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 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 Long- Bench show that, with a 256-token budget, IceCache maintains 99% of the original accuracy achieved by the full KV-cache model. Moreover, compared other offloading-bar 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 dittps://yuzherrre htt.yyywwwemaa..iigtt.ooeeee taiituu..ii wtt.uu......eaaaeee..
INTRODUCTION
Key-Value (KV) cache is critical component in modern large language models (LLMs), which stores the intermediate attention outputs for each token, allowing the model to reuse these computations in subsequent forward passes. This mechanism is particularly important for autoregressive generation, where tokens produced sequentially. However, fundamental challenge of K VV-ccche lies in its memory consumption: as the generated sequence length increases, the cache size grows linearly, often leading severe memory pressure out-of-memory errors on devices with limited resources.
Recent studies (Zhang et al. 2024b Tang et al.) 2024 Xiao al. 2023) have shown that, de- spite the growing size of the KV-cache, only
CUDA Memory (GB)
(PO)( L:0
small subset of tokens contributes disproportion- ately to generation accuracy. Building on this
insight, subsequent work (Chen et al. 2024a]
Lee et al., 2024 Chen et al. (224bb offloads the KV-cache to the CPU while dynamically retain- ing only the most important entries the GPU, However, many existing approaches lack pre- cise mechanisms for identifying truly relevant tokens, resulting in low hit rates for the most relevant cache entries. In addition, they often
IeeCache
Omalky y
Full Attention Oflaaiingg
leeCache
PoCache
Full Arteation w
Offeaaing
Figure I: IceCache has the best trade-off between CUDA memory footprint and time-per-outpur token (TPOT) on 1 at a 36k sequence length. Baselines are chosen represent aechacccrrccy (Left) and memory-efficient (Right) methods.

---

Published as a conference paper at ICLR 2026
lack effective update mechanisms to manage the KV-cache pool tokens generated during decoding. Therefore, scenarios involving cong-generationn tasks, such as long-context summariza- tion, multi-step reasoning, and chain-of-thought (CoT) generation, previous methods experience significant performance degradation (Li al. 2024a).
To improve the identification of relevant KV-cache entries, propose innovative approach, IceCache, which integrates semantic token clustering with PagedAttention (Kwon et al. 2023). a widely adopted memory management technique that stores K VV-cache entries in non-contiguous pages. As illustrated in Figure 2 by grouping semantically related tokens into the same memory pages, our method increases the likelihood that relevant tokens are co-located, thereby improving page selection hit rates and enhancing memory bandwidth utilization during CPU-GPU transfers. Furthermore, IceCache employs hierarchical data structure that can efficiently updated during decoding, mitigating the performance degradation commonly observed in long- uin-ggneration tasks. As result, IceCache enables more effective and adaptive K KV-cache management it achieves superior latency and accuracy compared to state-of-the-art baselines under the same KV-cache budget, and still attains comparable accuracy while using substantially smaller budgets.
2
Prompt
DCI-tree
Current Query (4)
LLM
Page
Transformed Key Emb.
Sparse
Atten
Selected (KV) Pages
Clustered Tokens
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. Fach leaf node of the DCI-tree corresponds to physical memory page. (2) During the decoding stage, given query q. IceCache performs tree search to identify the top-k tokens most relevant to q. The zoomed-in section 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-awan retrieval, the pages containing the relevant tokens are selected, and all tokens within these pages used in the subsequent sparse attention with q.
In summary, IceCache makes the following contributions:
We propose KV-cache offloading strategy that substantially improves retrieval hit rates by grouping semantically similar tokens into the same memory pages.
We develop multi-level DCI algorithm that supports efficient indexing, fast retrieval, and dynamic updates, enabling effective maintenance of the KV-cache data structure.
We design pipelining scheme that overlaps CPU and GPU computations, effectively hiding the latency associated with indexing and retrieval.
We evaluated IceCache under constrained GPU memory budgets on the Passkey Retrieval (Mo- htashami & Jaggi 2023), LongBench (Bai et al. 2023). and GSM8K Chain-of-Thought (CoT) reasoning (Wei et al. 2022) using four popular ooen-source LLMs: Llama3. --8B--Inttrut, Mistral- IB-Instructt-0.2 v0.2, LongChat- 7B-v and Qwen3-32B. 32B. Across diverse tasks, including open-domain QA, multi-ho hopp reasoning, academic reading comprehension, long-context summarization and long- context generation, IceCache consistently outperformed six state-of-the-art K KV-ccche baselines.
2

---

Published as a conference paper at ICLR 2026
Notably, IceCache sustained near-oracle performance most tasks using only small fraction (as small as 64 tokens) of the original KV-cache size. Furthermore, by leveraging its hierarchical and dynamically updatable data structure, IceCache effectively mitigates performance degradation in long-genenn rengggenerttion tasks. As shown in Figure | the empirical results demonstrate that IceCache establishes state-of-the-art in accuracy-eto -etrraccffficinncy trade-offs, achieving superior accuracy while significantly reducing CUDA memory usage and decoding latency compared to all existing baselines.
2
RELATED WORK
2.1 KV-CACHE MANAGEMENT VIA EVICTION AND OFFLOADING
Existing approaches to KV-cache management generally fall into two categories: eviction- -bssed methods and offloading- basen methods. Eviction- based methods are typically faster, as they avoid data transfer between the GPU and the CPU. However, they often rely on static selection strategies and fail to adapt to changing contexts. In contrast, offloading- -baied methods aim to preserve important VV-cache entries more accurately by dynamically transferring data between GPU and CPU, but introduce additional latency.
Evietion-based approaches include H2O (Zhang et al.! 2024b), which retains only subset of tokens selected based on attention scores; Streaming LLM (Xiao et al. (022), which preserves sink tokens and recent tokens to approximate attention; and SnapKV V (Li et al. 2024b), which selects key embeddings from the tail of the prompt to guide subsequent decoding. While efficient, these methods may struggle to maintain accuracy in cong-generation scenarios due to their limited flexibility in adapting to evolving contexts. Offloading based methods dynamically manage KV-cache storage across devices. MagicPiG (Chen et al. 2024b) uses sampling techniques based on Locality Sensitive Hashing (LSH) to approximate attention. OmniKV (Hao et al., (025) improves efficiency by reusing important tokens across consecutive layers. PQCache (Zhang et al.] (024a) applics product quantization to compress the K KV-cache and approximate attention computation. Although these approaches better preserve critical information, they incur additional communication costs from GPU-CPU transfers.
2.2 PAGED KV-CACHE MANAGEMENT
PagedAttention (Kwon et al. 2023 an innovative memory management technique designed to optimize the KV-cache of LLMs. addresses the challenges by introducing a paging mechanism similar to virtual memory systems in operating systems. This approach divides the KV-cache into fixed-size pages, allowing for more efficient memory allocation and management. By doing so, PagedAttention improves GPU memory utilization by reducing fragmentation and enabling longer context windows without sacrificing performance. However, unlike the methods discussed in the previous subsection, PagedAttentiin does not address the fundamental issue that the K V--cchee continuously grows during decoding.
Quest (Tang et al. 2024) and Vrk (Chen et al. 2024a) are two query- criticality estimation algorithms built on PagedAttentiio.. They effectively identify relevant KV-ccche tokens and perform self-attention selectively on the chosen tokens. For each page, Quest and Ark Vale calculate an upper bound using the feature values of the Key vector for each page's 's criticality estimation. Given all criticality scores of the pages, Top-k pages chosen to perform approximate self-attention, where is a preset constant (e.g. 128, 256). Additionally, VrkVale integrates the GPU-CPU offloading into the system further save GPU memory. However, key limitation of both Quest and Ark Vale is that they construct memory pages according to the original token order. As a result, tokens that are semantically relevant given query may be scattered across multiple pages. In contrast, IceCache performs semantic clustering during indexing, grouping similar tokens into the same pages. This organization increases the likelihood that relevant tokens are co-located, improving retrieval hit rates and reducing unnecessary memory transfers.
BACKGROUND
3.1 ATTENTION MECHANISM AND SPARSE ATTENTION
Mathematically, the attention operation takes three matrices as input, K E gmxd Q E Rudd V e mmxd', which denote keys, queries and values, respectively. Optionally, it may also take in mask as input, S E aaxm whose entries are either 0 or 1. The ith rows of K, Q and V, denoted as k, qi and v,, represent the ith key, query, and value, respectively. The entry of S in the ith row and jth
3

---

Published as a conference paper at ICLR 2026
column, denoted $i,,, represents whether the ith query is allowed to attend to the jth key - if is 1, it would be allowed; where $2 is 1 if i 2 and otherwise. Keys and queries have the same dimension d, and each key is associated with a value, and so the number of keys and values is the same and denoted as m. The attention operation computes the attention weight matrix A Raxm Its entry in the ith row and jth column, denoted as ai.j. is computed with the following formula:
is O, it would not be. A common masking scheme is the causal mask,
9. kg
$1,5 exp
Vd
0i.j
m E $ exp
9: k
The attention matrix A typically sparse (Niiiaa et al. 2020 Gupta et al. 2021 i.e., in each row of A, only a few attention weights have significant (large) values, while the majority of the remaining values are close to zero. If we can somehow identify the & unmasked keys that receive the highest attention weights for each query qi without computing the attention weights for all keys, the original attention matrix A can be approximated by only computing the inner product for the identified keys, which can save significant amount of computational resources.
3.2 LLM INFERENCE
The inference process of LLMs primarily comprises two key stages: the prefill (or prompt) stage and the decoding (or generation) stage. In the prefill stage, the model takes an input prompt sequence of length Sin and processes it through all layers of the LLM. During this process, the keys and values for each token in the sequence are computed and stored as part of the KV-cache. The decoding stage begins once the prompt has been processed. Here, the model generates output tokens one step at a time, using and updating the KV-cache iteratively. For each decoding step, the current token's 's computation depends on the stored keys and values from previous tokens, allowing the model to maintain context over the sequence. The KV-cache thus plays crucial role in enabling efficient autoregressive generation by reducing redundant computations and maintaining information about past tokens.
3.3 MULTI-LEVEL DCI
Prioritized Dynamic Continuous Indexing (P-DCI). Li & Malik 2016) proposed an exact, random- ized algorithm designed perform efficient k-nearest neighbour (k- (k-NN) searches in high-dimensional spaces. Unlike traditional methods, DCI avoids space partitioning, which scales poorly to high dimen- sions. It does so by constructing multiple indices, each of which allows for points to be efficiently ranked by a lower bound on the distances between them and the query. The lower bound is formed by projecting the distances along a random vector associated with each index. P-DCI (Li & Malik 2017) aggregates over the lower bounds given by each index to produce tighter lower bound and uses a priority queue to order points so that points with smaller lower bounds are processed earlier than points with larger lower bounds. This approach significantly reduces the number of distance evaluations and memory usage compared to methods like Locality-Sensitive Hashing (LSH). Mao first introduced P-DCI into sparse attention mechanisms accelerate LLM inference.
al. 2022)
Multi-level Dynamic Continuous Indexing (M-DCT). In this work, we extend P-DCI by introducing hierarchical data structure further enhance search efficiency. The index is organized into multiple levels, each containing a subset of data points. Points are randomly promoted to higher levels, forming a hierarchical data structure. Each point at a lower level assigned parent in the next higher level, typically the nearest neighbour among the promoted points. This creates "nodes" or clusters of points sharing the same parent. When querying, the algorithm starts at the top level, using P-DCI to find the k-closest points to the query. It then recursively searches within the nodes associated with these points at the next lower level, continuing this process down the hierarchy. This multi-level approach allows M-DCI to focus computational resources on the most promising regions of the index, effectively narrowing down the search space and improving query times, especially in datasets with high intrinsic dimensionality.
4 ICECACHE
We propose innovative approach, named IceCache, that integrates token clustering with KV-cache storage. Our method consists of three steps: (1) indexing; (2) page selection; and (3) bulk loading. The indexing step occurs either during the prompt processing phase- IceCache constructs
4

---

Published as a conference paper at ICLR 2026
hierarchical data structure, referred to the DCI-tree, for the prompt key embeddings: when new window pages are offloaded to the CPU. In this step, similar tokens are grouped into units called nodes, rather than being stored sequentially in virtual memory pages in PagedAttention. Here, node denotes a group of data points that share the same parent in the tree hierarchy. The next two steps take place during the token generation (decoding) phase. In the page selection step, IceCache employs a fast Approximate Nearest Neighbor (ANN) search algorithm, M-DCI, to independently select the top-k most relevant pages for each attention head. Finally, in the bulk loading step, the selected pages are efficiently transferred from the CPU back to the GPU. IceCache also overlaps the indexing (a CPU-intensive operation) with ongoing GPU computations further reduce the latency.
We provide further details on each of these three steps in the following subsections and illustrate the method in Fig
Roo Nade
Fillll
Plyscl Paga
Node
Page
2
13
Node
2
Page
Node
7
KV2
KYB
Page
12
Node 3
0
Page
10
Node
Page
Node
Page
5
Node
5
Page
8
Node
3
RV-11
Page 7
The hicrarchical data structure the left visualizes the result of indexing key embeddings, DCI-tree, where each tree node stores metadata for the tokens, such the key ID and node index. The tables the right depict the mapping between nodes in the DCI-tree and the corresponding pages in physical memory. For each selected node, mapping table used locate the memory region containing the associated key-value embeddings.
Figure 3: Illustration of DCI-tree and IceCache:
4.1 INDEXING: CLUSTERING KEY EMBEDDINGS INTO A HIERARCHICAL TREE
During decoding, the dominant bottleneck is often not the computation but memory bandwidth. As the KV-cache grows with sequence length, each decoding step requires repeatedly loading large amounts of KV embeddings from GPU memory. This leads to memory-bane banooy--bbnwidthhh saturation, significantly degrading latency scalability. PagedAtttention (Kwon et al., 2023) mitigates this issue by introducing virtual memory abstraction for the KV-cache. Instead of storing the KV-cache as single contiguous tensor, organizes KVs into fixed-size memory pages and maintains a page table to map logical token positions to physical memory locations. Within each page, consecutive tokens are stored contiguously, reducing fragmentation. This paging mechanism enables more flexible memory allocation and more efficient KV-cache management during decoding.
Building on this design, subsequent KV-cache optimization methods such as Quest (Tagg et al. 2024) and Vrle (Chen al., 2024a) leverage PagedArttenton's 's paging abstraction while incorporating query-aware page selection. These approaches estimate the importance of each page during decoding and utilize only the top-k pages to approximate attention more efficiently.
However, since pages are constructed based on the original token order, tokens relevant to a given query are often distributed across multiple pages. Therefore, retrieving them requires loading entire pages that may contain many irrelevant tokens, leading to unnecessary memory overhead and reduced selection precision. In contrast, IceCache organizes K KVcccche entries based on semantic similarity. concentrating relevant tokens within fewer pages. This design improves retrieval efficiency and achieves superior performance while reducing the number of pages accessed.
Specifically, IceCache organizes key-value embeddings into memory pages through fundamentally different indexing strategy: instead of relying on the token's original order, IceCache constructs a separate hierarchical tree data structure for each attention head, called DCI-tree, which clusters tokens based on the semantic similarity of their key embeddings. Each node in the DCI-tree represents small group of semantically related tokens that share common parent, effectively forming a localized cluster. From a memory system perspective, IceCache maps each node directly to memory page, thereby preserving semantic locality in storage and enabling efficient access during
5

---

Published as a conference paper at ICLR 2026
decoding. By clustering semantically similar tokens into the same nodes/pages, IceCache enables more targeted and efficient retrieval during decoding.
Moreover, the DCI-tree data structure used by IceCache is designed for efficient incremental updates. As new windows of tokens (c.g., from a sliding window in long-context scenarios) are offloaded to the CPU, each token is inserted into the appropriate node in the DCI-tree based on its key embedding. When a node exceeds the maximum page size, new pages are dynamically allocated to maintain balance. This adaptive tree maintenance ensures that the index remains both semantically meaningful and efficient, making IceCache particularly effective for long-sequence generation.
In summary, while prior methods treat KV-cache page layout static memory allocation problem, IceCache introduces dynamic, semantically-aweer data structure that preserves key similarity across time. This enables more focused page retrieval, reduces memory fragmentation, and supports more efficient decoding. Furthermore, by performing indexing during the prompt or CPU offloading phase, IceCache amortizes the tree construction cost and avoids incurring additional latency during inference.
4.2 PAGE SELECTION: HEAD-SPECIFIC ANN SEARCH WITH FINE-GRAINTR RETRIEVAL
During the decoding phase, given a query embedding, IceCache performs head-specific page selection to identify the most relevant pages for each attention head. Leveraging the hierarchical DCI-tree constructed during indexing. we apply the fast approximate nearest neighbor (ANN) search algorithm described in Section 3.3 M-DCI, retrieve the top-k pages that are important the current query for each head independently. For group-query attention (GQA), where multiple query heads share the same set of key embeddings, we compute the union of the selected pages across queries within the same group and share the resulting pages among them, following Yuan al. (2025).
The detailed pseudo-code of this procedure is provided in Appendix B.2
4.3 BULK LOADING AND PIPELINING
In this section, we present how optimize the efficiency of the IceCache workflow, using bulk loading and pipelining. Our key observation that the selected pages are not contiguous in either main memory or GPU memory. As result, individual transfer of these pages between main memory and GPU memory is highly inefficient. To overcome this issue, we designed bulk loading algorithms to efficiently offload and backload the selected pages, using two CPU and GPU backload buffers. In addition, we carefully designed an efficient pipeline prefilling calculations, KV-cache offloading. and DCI indexing, for efficient prefilling. We illustrate bulk back-loading workflow in Figure
DCtaree Kishel!!
C'FCaade Tible
Parffl
Irde..
Portil
CL
Iodrs L.p-11
L Jert
A
Cupy memury
CLL. (iers
Copy to GPU
cachhe blockss
Balk backlead
CPI
Iallss
felix
Gechbackooo Bufferr
KeCaaaa speliiing
Figure 4: After IceCache selects important KV- pages, it aggregates all selected pages into a con- tiguous CPU preloading buffer. This buffer then transferred via high-throughput PCIe trans- action to pre-allocated GPU buffer. Finally, the transferred blocks are scattered into their exact locations in the KV-Cache table. This bulk trans- fer avoids many small copying operations over PCIe and significantly improves utilization.
Figure 5: (a) Baseline serial workflow, where prefilling, offloading (OL), and indexing are exe- cuted strictly in sequence. (b) IceCache pipelin- ing, where GPU prefilling overlaps with KV- offloading via PCIe and CPU-side DCI indexing. Once KVs of layer i (L;) arrive in CPU mem- ory, Li-DCI-tree indexing progresses in parallel with GPU prefilling and offloading of the subse- quent layer (Li+1). This results in significantly reduced end-to-end prefilling latency.
Offloading follows similar procedure, except that the steps executed in reverse. After identifying the most relevant pages (indicated by color), we filter out those already resident in GPU memory from previous token generations. The remaining pages then aggregated into pre-allocated CPU-

---

Published as a conference paper at ICLR 2026
memory buffer, enabling single high-throughput PCIe transfer into a pre-allocated GPU GPU-memory buffer. Once the pages arrive in the GPU, we perform a scatter operation to load them into the appropriate slots of the KV-Cache table.
Figure (b)) illustrates the pipelining of IceCache prefilling (other minor stages are omitted for clarity). After the KV embeddings are generated on the GPU, simultaneously launch the prefilling calculation and the offloading transfer. The DCI index construction starts building the index along with the prefilling calculation, right after the KV states fully arrive in the main memory. This approach allows the offloading and indexing latencies to be largely hidden by the main prefilling computation. Furthermore, IceCache can be easily extended with page reuse techniques (Liu et al. 2023 Hao et al., 2025 to further accelerate prefilling.
5
EXPERIMENTS
5.1 SETTINGS
To comprehensively evaluate IceCache, we conduct experiments across models of varying scales and attention architectures. We first apply IceCache
---mna--.-BB-IIsttttt and Dustral-B-IInsruuee v0.2, two widely adopted open-source LLMs employing group-query attention (GQA) (Ainslie) al., 2023). To further assess scalability and architectural generality, we extend our evaluation to Qwen3-32B, a larger-scale model, and LongChat-7B-v1.5 which employs standard multi-head attention Vaswani et al. (017) rather than group-query attention. Our evaluation proceeds in four stages. We first measure recall in retrieving important tokens (Mohtashami & Jaggi 2023). To evaluate the performance of IceCache on long generation tasks, we further conduct experiments on LongBench (Bai al., 2023), which contains long generation tasks such as summarization and code generation, and GSM8K (Cobbe et al., 2021). which requires chain-of-thought reasoning. Finally, we examine its scalability on RULER Hsiih et al. 2024) under extremely long-context settings.
Our experimental platform comprises an NVIDIA A100 40GB PCIe GPU (for small models) or an NVIDIA H100 80GB PCIe GPU (for large models). For all experiments, we fix the number of CPU threads to 64. The software stack includes CUDA version 12.2, PyTorch version 2.4.1, and HuggingFace Transformers version 4.57.1. We implement IceCache on top of HuggingFace Transformers, utilizing FlashInfer Ye et al. 2025) for the attention kernel operation. As prior research indicates (Tang et al. 2024)), the initial layers of the model exhibit relatively low sparsity. Therefore, neither IceCache nor baseline methods are applied to the first two layers of the models.
5.2 PASSKEY RETRIEVAL ACCURACY
We first evaluate IceCache's effectiveness in handling long-range dependencies using the passkey retrieval task. We consider context lengths from 10k words to 100k words, and test with the size of cache budget- = [256,] 128, 64). For each length, 100 test cases are generated with passkeys inserted at various positions from 0% to 95% of the total context length in increments of 5%. The results are illustrated in Fig. 6 As shown in the figure, IceCache dynamically assesses the importance of evicted pages and recall crucial ones on demand, consistently maintaining 100% retrieval accuracy across all tested budget sizes.
5.3 LONGBENCH EVALUATION
To assess the performance of our method in long- long-context scenarios, conduct a comprehensive evaluation on the LongBench benchmark (Bai et al. 2023). LongBench is designed to evaluate how well LLMs understand and reason over long-context inputs across diverse real-world tasks. We compare IceCache (ICF) against six state-of-the-art KV cache optimization methods, including MagicPig (MPG) (Chen et al. 2024b). ArkVale (AKV) Chen al. (2024a). SnapKV (SKV) Li et al. (0024)), EtreamingLLM (SLM) et al. (2024), OmniKV (OKY Hao et al. (2025) and PQCache Zhan) et al. (2024a) as baselines. We also include the results of full K Cacche (FULL) and ground-truth top-l KV-cache (TOP-k) as baselines. Notably. OmniKy V offloads only a subset of layers while keeping all remaining layers fully resident on the GPU, resulting in substantially higher memory usage than other methods. The detailed results are presented in Table [
5.3.1 ACCURACY ANALYSIS
Accuracy on 1.1-aa--.-------siii ularly pronounced. Most impressively, with a highly constrained KV-Cache budget of just 64, our method achieves an average accuracy of 47.8. This result alone surpasses the strongest baseline,
On Llama-3.1-8B. the effectiveness of IceCache is partic-
7

---

Published as a conference paper at ICLR 2026
100
100
100
15
15
15
90
Position
30
30
45
45
55
55
20
75
20
75
20
05
05
10k
20r
90%
100k
20k 100k
Word Count
Word Count
Word Count
(a) Cache Budget 256
(b) Cache Budget 128
(c) Cache Budget = 64
Figure 6: Passkey retrieval accuracy of IceCache on Llama3. I-StuInstruct. 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.
Table I: Accuracy comparison of our method (ICE) with SnapKV (SKV), SteamingLLM (SLM), OmniKV (OKV), MagicPig (MPG), PQCache (PQC), Vak (AKV), Full KV (FULLL) and ground- truth top-k (TOP-k) on LongBench for Llama-3, 3.1.a-..11811 -S--nnstruct and Mistral-7B Destral-BBIInstruee Instruct. IceCache generally outperforms other methods across various KV-cache budgets and LLMs.
Single-Dueumen QA
Multi-Dorumrnt QA
Summarization
Feu-shut Learning
Synthelic
Cude
Budget Methou
NivQA 15409
Qusperi MF HaparQA
2WIL38QA 4857
Misique Gon Reponn
QMSuu MMlliNews 10624
TREC 5177
TriviaQA $299
SAMSum PCount 6258
PRc 9239
Lce RB 1235
3619
4559
9151
11214
8734
2113
1114:
4206
Liuma-3.1-5B
27.2
91.7
49.5
20.7
$3.5
256
MPG
25.0
$4.0
44.6
47.3
AKV
42.8
64
03.2
25.7
26.2
72.5
90.3
99.5
61.8
ICB
44.7
30.0
26.3
26.5
73.0
91.3
51.5
48.0
256
IC6
30.6
44.7
55.3
55.2
45.9
30.6
34.6
24.4
26.7
73.0
92.0
43.5
6.7
108.0
62.5
49,0
Mistroll 7I-- Emndrnet-111222
NIA
27.1
56.2
56.9
256
TOP-A
27.1
56.6
59.00
MPG
99.1
57.4
AKV
53.0
55.9
53.2
39.0
26.1
70.5
55.7
53.6
60.5
256
31.0
25.1 26.9
71.0
86.3
85.1 54.7
41.7
PQCache, which scores 47.3 while operating with 4x larger budget of 256. This highlights the exceptional efficiency of our approach in low-resource environments. As we increase the budget for IceCache to 256, its performance climbs an average score of 49.0. This only represents substantial 1.7 point improvement over PQCache but also closes the performance gap to the uncon- strained Full KV-Cache (49.5) to a mere 0.5 points. Notably, our performance remarkably close to the ground-truth truth Top-k, demonstrating a near-optimal cache management strategy across diverse set of tasks.
Accuracy on Mistral-7B-Instrudd This strong performance trend is consistent on the Mistral-7B model, confirming the robustness of our method. With budget of 256, IceCache achieves an average accuracy of 41.7, establishing a significant 2.6 point lead over the best-perg baseline, MagicPig (39.1). Again, the low-budget capability of IceCache stands out; with a budget of 64, IceCache scores 39.0, remaining highly competitive with the top baseline (MagicPig, scores 39. 1) that uses four times the cache size (256).
Accuracy two additional LLMs. To further validate IceCache larger-scab models and standard multi-heate attention architectures, we evaluate it on LongBench using two additional models: Qwen3-328 and LongChat-7B-vll As shown in Tables 2 for Qwen3-321B, IceCache with
8

---

Published as a conference paper at ICLR 2026
Table 2: Accuracy comparison of our method (ICE) with Full KV (FULL) on LongBench for Qwen3- 32B and LongChat-7B-v1.5.
Single Ducument QA
Multi Document QA
Semmortzatton
Few Learning
Synthetic
Code
Budget
Method
NivQA 1840
Qoeper 3619
MF-ea HappeQA
2WikiMlQA 4867
Masigna CowBepoo 11214
(MMSum MainiNows 10614
TRFE 5177
TTriiQA $200
SAMSum 6258
PConnt 11141
PRr
Loe RRR-P
4559
9151
8734
2113
9289
1235
4206
Qwend-328
NAA
4434
64
ICB
29.5
43.9
$0.9
55.8
16.8
90.8
23.8
24.3
71.0
70.0
15.7
15.0
93.0
10.5
42.2
198
10.1
44.8
53.3
54.6
16.5
31.0
25.6
24.8
12.0
70.3
16.2
15.5
100.0
10.7
17.5
42.6
256
ICE
30.2
51.9
60.2
55.1
16.9
32.4
34.3
24.7
71.5
70.7
57.4
16.5
100.0
11.8
18.0
43.1
LangChat--775 11.
FULL
$4.0
330.5
54.77
335.2
52.5
52.6
26,1
53.6
small budget of 64 achieves an average accuracy of 42.2 on LongBench, retaining 97.2% of the full KV-cache performance (43.4). This score rises to 99.3% with budget of 256, nearly matching the vanilla model. Similarly, on NongChat-7B-v1.55 our method preserves 96.3% of the full K KV-cache performance with a budget 64, and achieves up to 99.4% at budget of 256. These results provide strong evidence that IceCache is effective across different model scales and attention mechanisms.
5.3.2 LATENCY ANALYSIS
Since most baselines, including IceCache, use the entire K V-cachee generate the first token, follow PQCache (Zhang et al. 2024a) and report the Time to the second token (TT2T) in Fig. 7a for 36k sequence length with Llama-3, 3., 1..1-88-IInttee and all the methods compared in Table except MagicPig, which is restricted to costly AVX-512 CPUs. Additionally, we present results for IceCache incorporating the critical paaellpae-eessse technique (reusing the same selected K VV-page indices across layers), method also used in OmniKV, which serves as an approximate version that trades accuracy for increased speed.
100
@iceCachetreea@ IeeCohe
POCache
Decoding
90
Accnscy
Arkvaale
Query
SnapitV
73
Loading
@ttaming
5KV
SLM
AKV
POC
OKV
ICE
(CEIP)
0.04
0.06
0.05 0.30
0.32
0.04
Latency
(a) Time to the second token.
(b) Time per output token.
(c) TPOT Lateney breakdown.
Figure 7: Latency comparison of IceCache and baseline methods 36k-token sequence.
As illustrated in the figure, our method, IceCache, achieves competitive latency among retrieval-based algorithms, recording 7.7 seconds. IceCache (reuse) further reduces this to 5.9 seconds, matching OmniKV (5.8 s) and outperforming other retrieval-based baselines such as Arkvale (7.4 s) and PQCache (13.3 s). Although eviction-based methods like SnapKV (0.55 s) and StreamingLLM (0.13 s) are much faster, their speed often comes at the cost of accuracy. Overall, IceCache and IceCache(reuse) offer a strong balance between efficiency and accuracy. with the reuse variant showing how our approach can further optimize latency without significantly sacrificing performance. We include more details of IceCache(reuse) the appendix C
Similarly, for decoding latency, Fig. 7b shows the average time per generated token, along with the corresponding accuracy percentage relative to the full KV-cache model, for an input sequence length of 36k. Eviction-based methods, StreamingLLM and SnapKV (both at 0.03 seconds per token), continue to show the fastest speeds due to their minimal overhead. Among the more accurate retrieval- based methods, IceCache(reuse) achieves highly competitive decoding time of 0.06 seconds per token substantially faster than PQCache (0.13) s) and nearly matching the speed of OmniKV (0.05 s). Vanilla IceCache maintains strong balance, combining superior accuracy with efficient decoding.

---

Published as a conference paper at ICLR 2026
It achieves the highest accuracy percentage (99.0%) while still outperforming PQCache in speed. These results further demonstrate that IceCache effectively balances accuracy and decoding latency.
Figure 7c presents detailed breakdown of TPOT latency for IceCache at sequence length of 36k, with a total latency 0. seconds. In this figure. "Loading". "Query", and "Decoding" correspond to the overhead from CPU-GPU communication, DCI-query operations, and the overall LLM decoding process, respectively. The largest contributors to latency are the DCI-query module (0.05 s) and decoding (0.04 s), while GPU-CPU offloading and other miscellaneous operations add only 0.015 seconds and 0.005 seconds, respectively.
5.4 GSM8K COT REASONING
Table GSM8K COT.
We also evaluate IceCache on the GSM8K benchmark using Chain- of of-Thought prompting. applying 10% budget for all compared methods using Mistral-7B-IInsruut--0.. As shown in Table Ice- Cache demonstrates superior performance, achieving an accuracy of 47.4%, significantly higher than all other methods under the same budget constraint. particular, it improves upon the strongest base- line, PQCache (46%), by 1.2% absolute points, reaching 47.4%. Moreover, our approach nearly matches the full KV-cache (48.2%), highlighting the effectiveness of IceCache.
Method
Budget
Accuracy
NIA
SKV
10%
44.7
SLM
10%
44.4
OKV
10%
42.7
MPG
109
43.1
AKV
1055
10%
47.4
5.5 SCALABILITY TO EXTREMELY LONG CONTEXT
To further evaluate the performance of IceCache under extremely long-context settings, we conduct experiments on the RULER benchmark and report accuracy on Single-Needle-innat -a-aa-aaa- (Single- NIAH), Multi-keys NIAH, and QA tasks with context lengths of 150k, 200k, and 250k tokens, using token budget of 256. The experiments are conducted using -wen3-4B-Instruct-22 GPU with 64 CPU threads enabled. As shown in Table 4 IceCache and IceCache(r) consistently maintain accuracy comparable to Full-KV across all tasks and context lengths. Figure S further demonstrates that, as the input context grows, both IceCache and IceCache(r) exhibit substantially slower increase in per-token decoding latency than Full-KV, whose decoding cost scales sharply with sequence length. These results indicate that IceCache achieves a better accuracy-latent trade-off for extremely long-contex inference, enabling scalable decoding without sacrificing accuracy on the RULER benchmark.
on a single H100
Table Accuracy comparison on Qwen3- 4B-Instruct under different context lengths (150k, 200k, 250k) on RULER bench- mark.
Full
IceCache IceCacheirl
Decatt Latescyyfolem (mns)
Method
Single-NTAH
Multi-kyy NIAH
QA
158k Tokens
Full KV
100,0
97.0
93.0
IceCache
98.0
TeeCache
98.0
KV
92.0
IeeCache
91.3
95.0
IeeCeche (1)
100.0
91.0
94.3
250%: Tokens
Figure 8: Latency scaling across context
Pull KV
100.0
91.0
91.3
leoCache
100.0
93.0
91.7
lengths (150k, 200k, 250k and 300k).
IeeCache
100.0
92.0
92.0
CONCLUSION
This paper addresses the fundamental challenge of long-context inference in L.MMs, where the rapidly growing KV-cache consumes substantial GPU memory and degrades computational efficiency. We first introduce the DCI-tree, hierarchical indexing structure that integrates naturally with PtgedAtten-- tion and supports dynamic updates for efficient KV-cache organization. Building this foundation, we propose IceCache, a page-based KV-cache management framework that combines semantic token clustering with efficient GPU-CPU offloading. Across diverse long-cou long-context benchmarks, IceCache consistently achieves superior sccuracy-latents trade-offs. These results establish IceCache as a scalable and practical solution for memory-efficient long-context L.M inference.
10

---

Published as a conference paper at ICLR 2026
7 ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their insightful feedback and constructive suggestions. This research was enabled in part by support provided by NSERC, the BC DRI Group and the Digital Research Alliance of Canada.
REFERENCES
Joshua Ainslie, James Lee- Thorp. Michiel De Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints. arXiv preprinl arXiv: 33245, 2023.
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308. 14508, 2023.
Renze Chen, Zhuofeng Wang. Beiquan Cao, Tong Wu, Size Zheng, Xiuhong Li, Xuechao Wei, Shengen Yan, Meng Li, and Yun Liang. Arkvale: Efficient generative I1m inference with recallable key-value eviction. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a.
Zhuoming Chen, Ranajoy Sadhukhan, Zihao Ye, Yang Zhou, Jianyu Zhang, Niklas Nolte, Yuandong Tian, Matthijs Douze, Leon Bottou, Zhihao Jia, et al. Magicpig: Lsh sampling for efficient llm generation. arXiv preprint arXiv:2410. 16179, 2024b.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jenry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110. 14168, 2021.
Ankit Gupta, Guy Dar, Shaya Goodman, David Ciprut, and Jonathan Berant. Memory-efficient transformers via top-k attention. arXiv preprint 10X::22066.0689, 2021.
Jitai Hao, Yuke Zhu, Tian Wang, Jun Yu, Xin Xin, Bo Zheng, Zhaochun Ren, and Sheng Guo. Omnikv: Dynamic context selection for efficient long-context llms. In The Thirteenth International Conference on Learning Representations, 2025.
Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, Yang Zhang, and Boris Ginsburg. Ruler: What's the real context size of your long-context language models? arXiv preprint arXiv:2404.06654 2024.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pp. 611-626, 2023.
Wonbeom Lee, Jungi Lee, Junghwan Sco, and Jaewoong Sim. {InfiniGen]: Efficient generative inference of large language models with dynamic (KV) cache management. In 18th USENIX Symposium Operating Systems Design and Implementation (OSDI 24), pp. 155-172, 2024.
Ke Li and Jitendra Malik. Fast k-nearest neighbour search via dynamic continuous indexing, In International conference on machine learning, pp. 671 171.679. PMLR, 2016.
Ke Li and Jitendra Malik. Fast k-nearest neighbour search via prioritized dei. In International conference on machine learning, pp. 2081 2081-2090. PMLR, 2017.
Yucheng Li, Huiqiang Jiang, Qianhui Wu, Xufang Luo, Surin Ahn, Chengruidong Zhang, Amir H Abdi, Dongsheng Li, Jianfeng Gao, Yuqing Yang, et al. Scbench: A kv cache-centric analysis of long-context methods. arXiv preprint arXiv:2412 10..1119911199 2024a.
Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Lim knows what you are looking for before generation. arXiv preprint 2404. 2e.e2244444444 /4469, 2024b.
11

---

Published as a conference paper at ICLR 2026
Zichang Liu, Jue Wang, Tri Dao, Tianyi Zhou, Binhang Yuan, Zhao Song, Anshumali Shrivastava, Zhang, Yuandong Tian, Christopher Re, et al. Deja vu: Contextual sparsity for efficient Ilms at inference time. In International Conference Machine Learning, pp. 22137-22176. PMLR, 2023.
Yuzhen Mao, Martin Ester, and Ke Li. Iceformer: Accelerated inference with long-sequence transformers on CPUs. In The Twelfth Interationall Conference on Learning Representations. 2024.
Amirkeivan Mohtashami and Martin Jaggi. Landmark attention: Random-access infinite context length for transformers. arXiv preprint arXiv:2305. 16300, 2023.
Kitaev Nikita, Kaiser Lukasz, Levskaya Anselm, et al. Reformer: The efficient transformer. In Proceedings of International Conference Learning Representations (ICLR), 2020.
Jiaming Tang. Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-aware sparsity for efficient long-context Ilm inference. arXiv preprint Mxxv:2406.11074 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837 2022.
Yuhao Wu, Ming Shan Hee, Zhiqing Hu, and Roy Ka-Wei Lee. Longgenbench: Benchmarking long-form generation in long context llms. arXiv preprint arXiv:2409.020776 2024.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint mxXi::2309.17455 2023.
Zihao Ye, Lequn Chen, Ruihang Lai, Wuwei Lin, Yineng Zhang, Stephanie Wang. Tianqi Chen, Baris Kasikci, Vinod Grover, Arvind Krishnamurthy, et al. Flashinfer: Efficient and customizable attention engine for I1m inference serving. Proceedings of Machine Learning and Systems, 7, 2025.
Jingyang Yuan, Huazuo Gao, Damai Dai, Junyu Luo, Liang Zhao, Zhengyan Zhang, Zhenda Xie, Yuxing Wei, Lean Wang, Zhiping Xiao, et al. Native sparse attention: Hardware- and natively trainable sparse attention. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp. 23078-23099 2025.
Hailin Zhang, Xiaodong Ji, Yilin Chen, Fangcheng Fu, Xupeng Miao, Xiaonan Nie, Weipeng Chen, and Bin Cui. Pqcache: Product quantization- based kvcache for long context Ilm inference. arXiv preprint arXiv:2407. 12820, 2024a.
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances Neural Information Processing Systems, 36, 2024b.
12

---

Published as a conference paper at ICLR 2026
A METHOD OVERVIEW
We separate all tokens into three groups: sink tokens, which are the tokens at the very beginning of the input sequence; window tokens, which are the most recent tokens; and all the remaining tokens in between. The pages that store sink tokens are referred to as sink pages, and those that store window tokens are referred as window pages. We always keep all the sink and window pages GPU.
We provide the pseudocode below for IceCache. It operates in two main phases: (1) Prefill Phase: During the initial processing of prompt tokens, IceCache allocates paged KV memory per layer and performs self-attention computations. From the third layer onward, it copies KV embeddings to CPU and builds a dynamic index - DCI-tree. This tree enables efficient future lookup of important tokens based on query embeddings. (2) Decode Phase: During autoregressive decoding, each new token's s query embedding is used to retrieve the most relevant KV pages via DCI-based query. Selected pages are back-loaded to GPU demand, while unimportant pages are offloaded CPU storage. When new window page is offloaded, the DCI-tree is incrementally updated to store tokens in this page. We will explain the mechanisms behind indexing and
The detailed steps are outlined in Algorithm [ page selection in the following sections.
B
METHOD DETAILS
B.1 INDEXING
For each attention head, given a set of pre-computed key embeddings, IceCache first indexes them using hierarchical tree structure which is obtained by novel approach called Multi-level DCI (M-DCT). It works by constructing a dynamic index called DCI-tree and applies Prioritized DCI (P-DCI) (Li & Malik (017) to each level of the tree recursively (more details in Section (.3). The data points processed in M-DCI are transformed key embeddings and query embeddings using the following transformation formulas, which we denote as Tk- Rd Rd+1 and TQ R Rd+1,
Tk = [ky/c
V1
k
To = lq:/// 0]
where 2 maxy ||ky |l2 is at least the maximum norm across all keys. We use the Euclidean distance as the distance function.
At the very beginning of the indexing, all data points are initially placed at the bottom level of the DCI-tree. Subsequently, some points are randomly selected to be promoted to the next higher level based on a promotion ratio fixed throughout the process. After the indexing, we can get the total number of levels in the DCI-tree, denoted as The details are presented in Algorithm 2
1. The ratio r predefined during DCI-tree initialization and remains
Specifically, let ny denote the number of data points at level E, with level indices starting from the bottom (i.e., the lowest level is = 1). Ideally, the number of points satisfies the recurrence relation N4 r 1- In other words, the distribution over level indices follows geometric distribution. The probability that a point is assigned to the highest level (f = L) is pl- while the probability of being assigned to level e (for 1 < l = L 1) is ff-1 - r
After level assignment, each data point at level is linked to a parent at level + 1, defined as the closest point in terms of key embedding distance. This parent assignment is formulated 1-nearest query.
neighbor search and is efficiently solved using M-DCI
In the decoding stage, when new token is generated, its key embedding is inserted into the appropriate position in the DCI-tree. A level & is first assigned to the new key according to the same random promotion process. Then, its parent level é + is determined, and the key is added the physical memory page corresponding to the node into which it is inserted.
B.2 PAGE SELECTION
As aforemennioned, IceCache aims to accelerate self-attention by loading only a limited number of pages into GPU memory for computation. Therefore, the objective of page selection is to maximize
13

---

Published as a conference paper at ICLR 2026
the recall (or hit rate) of significant keys for given query. By clustering semantically similar tokens into the same nodes/pages, IceCache enables more targeted and efficient retrieval during decoding. In contrast, methods like Quest (Tang et al., 2024), Arkvale (Chen et al. 2024a). PQCache (Zhang let al.; 2024a) construct pages based on the original token order, which often causes tokens relevant to given query be scattered across multiple pages. Retrieving them requires loading entire pages filled with many irrelevant tokens, resulting in unnecessary memory overhead. IceCache mitigates this inefficiency by grouping similar tokens, so relevant tokens tend to be concentrated within fewer pages. As result, the hit rate of significant keys during decoding increases. The detailed procedure shown in Algorithms [ and 4
Specifically, when computing the attention matrix, given a query vector qs. we follow the query process described in 3..3ionn3.3Jta identify the top-k keys that are most likely to yield the highest dot-product values with qt. Once these top-k keys are identified, we load only the pages that contain them. Suppose p pages are loaded, and each page contains d entries, since not all the pages are fully filled, the number of loaded keys N is bounded as: N S pd.
The approximate attention scores between the query q and these N selected keys are then computed using Equation [ The masks 8i, are set to 1 for the selected keys and 0 for all others. Note that, IceCache constructs a separate DCI-tree for each attention head, allowing it to retrieve different sets of significant pages per head. This head-specific, fine- fine-grained selection mechanism distinguishes IceCache from baselines such as Quest and Ark Vale, which retrieve the same set of pages for all heads, potentially limiting their retrieval accuracy.
C DETAILS OF ICECACHE (REUSE) ON LONGBENCH
We present the LongBench scores for IceCache (reuse) in Table 5 Starting from the third layer, build the DCI-tree and perform DCI-queries every three layers; we refer to these as "anchor layers". For the layers in between, reuse the KV-cache indices selected at the most recent anchor layer.
Table 5: Accuracy of IceCache (reuse) on LongBench.
Single Document QA
Multi-Dacument QA
Summarization
Feu Learning
Svathetic
Cide
Budget Methood
NavQA 1848
Qosperi MT es HorporQA
2WHKMMQN 4867
Missique Rooooo
QM55m 10614
MainiNww 2113
TREU 3177
TrmiaQA $208
SAMSum 0258
PConni 11141
PRe
Loc 1230
RB P Avg. 4206
3619
4559
9151
11216
8734
9289
Limma-3 Instruct
100.0] (477
D PERFORMANCE ON LONG GENERATION BENCHMARK
To evaluate the effectiveness of IceCache on long-context generation tasks, we conduct experiments on LongGenBench [Wu et al., 2024) using Llama-3.1-88 -88---nrnttt with 256-token budget. As shown in Table 66, IceCache substantially outperforms PQCache while maintaining accuracies on par with the Full-KV baseline.
Table 6: Accuracy comparison on LongCeeBennh for Llama-3. 3.1--....--BBmm Instrrctt
Method
Completion
Accuracy Cluce
Accanscy Range
Accuracy Periodic
Avg. Accunay
KV
97.627
IceC lcce
95.322
0.377 0,318
0.454 0.395
0.164 0.105
0.331
PQCache
$3.691
0,273
E LLM USAGE
This work focuses on optimizing KV-cache management for large language models (LLMs). All the base models used in this paper can be viewed as LLMs, including 1.1-a--..-B-----S-- Mistral-7B- Instruct-v0.2, Qwen3-32B, LongChat-7BBs 7B- and Qwen3-4B 4B-IInttruct-22 We also leveraged an L.LM to help refine the manuscript's language and improve its overall readability.
14

---

Published as a conference paper at ICLR 2026
Algorithm IceCache
1: Input: Sequence of tokens F1.1, Transformer with L attention layers, Page size
2: Phase I: Prefill
3: for L t= 0 to L --1 do
4: Allocate pages and arrange KVs the pages for layer l
5: if' & 2 2 then
6:
Copy KVs of tokens between sink tokens and window tokens from GPU CPU (denoted Sk and S.,) end
7:
8:
Compute the output from the current self-attention layer
9:
i 2 2 then
Ti +- D.-DDI-NDEXINN
11: end if
end for
13:
Phase 2: Decode (repeated over time steps i >> T)
while receive new token v; with qu as its query embedding do
15: for f= 0 to L 1 do
16:
Number of tokens the last page 2 s --1 then Offload the oldest window page Pw from GPU to CPU
17:
18:
Set Flag to True
19:
end if
20:
Append KVs of x; to the end of the newest window page if f 2 then
21:
22:
S + PAGE-SELECTIQ. Ti k) k)
Recall selected pages S, from CPU to GPU
24:
end if
Compute the output from the current self-attention layer
26:
if f 2 2 & Flag is True then
27:
// Insert the tokens in offloaded Pa, Ti
28:
for i in Pw. do
29:
// Random Promotion
30:
4 1-11 1
Start at bottom level
31:
while Random (0, 1) < r do
32:
1, 4 +
Promote to the next higher level
33:
end while
34:
{p:} QUERY(K, Ti,4,
Get the parent index using QUERY (Alg.4)
35:
Insert k; to Ti with p; its parent node index
end for end if end for
37:
38:
39:
if x, =
EOS then
40:
Break end if
41:
42:
-=it +++1
43:
end while
15

---

Published as a conference paper at ICLR 2026
Algorithm 2 Indexing
Require:
list S& of keys ki,..., kn R", Promotion ratio
function DCI-INDEXING(SS, r)
for: = 1 to n. do
// Random Promotion
4
Start bottom level
while Random(O, 1) do
4 + 4++1
Promote to the next higher level
end while
end for
Remove the empty levels
Initialize with an empty root node
for = 1 to n. do
{p:} <- QUERY(K;, T, 1) 1)
Get the parent index using QUERY (Alg.4)
Insert k; to T with pı its parent node index
end for return
end function
Algorithm 3 Page Selection
Require:
Query vector q, E R DCI-tree T', Number of critical keys function SEEEESSEEETTQ;;111 Initialize S₁ +- 0 QUERY T, k) S < FIND-PAGF-INDEX(SS)
return St end function
Algorithm k--Narest Neighbour Querying
Require: Query vector q; E Rd, DCI-tree T with L levels, Target level Number critical keys k function QUERY(q;, (,1,
if 1 then
1+1 Set Flag to True
else
Set Flag False
end if
+-0 0
P + empty priority queue with size
for = to do
5" 8
if then
+ (root node)
end if
for in S do
S" Prioriizee-DDCL--eerygg... S' S' S
end for
if Flag is True or i- then
for in 5 do P Aad-to-Priority-Queee (P,
end
end if S < S' end for
return nodes have the keys with maximum inner-product with q: end function
16


Reviews:
[{"review_id": "dfOJQiNstJ", "reviewer": "Reviewer_SWPZ", "summary": "This paper proposes a KV-cache management method called IceCache, combining semantic token clustering (using a hierarchical DCI-tree) with the PagedAttention mechanism to optimize long-sequence LLM inference. The core idea is to group semantically related tokens into the same memory pages, enabling more accurate and efficient query-aware page selection during decoding, compared to methods that rely on the original token order. The paper demonstrates better results compared with baselines, maintaining over 99% of full-model accuracy with a significantly reduced KV-cache budget (e.g., 256 tokens) across a wide range of long-context benchmarks.", "questions": "The same as the weakness.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Grouping tokens by semantic similarity in key-embedding space improves cache hit rates, which is powerful and clearly explained.\n2. Comprehensive evaluation with diverse benchmarks and multiple models with impressive results.\n3. Superior accuracy-latency trade-off compared to other high-accuracy, retrieval-based methods.", "weaknesses": "1. Lack quantitative analysis of the computational cost of building and maintaining the DCI-tree on the CPU. How significant is the CPU utilization? Could this become a bottleneck on a system with a less powerful CPU or when running multiple instances?\n2. The storage cost of the DCI-tree indices themselves is not discussed. For a context length of 100k tokens per layer and per head, what is the memory footprint of the index on the CPU? \n3. Compared to OmniKV, the overhead is primarily from the DCI-query, the more complex data movement, or both? A direct comparison of these components with a leading baseline like OmniKV would be more informative.\n4. The description of M-DCI with P-DCI, but the algorithm in Page 4's pseudocode and Appendix B.1 uses a simpler promotion and parent-assignment scheme, the consistency should be improved.\n5. The entire method hinges on the quality of the key embeddings for clustering. How about the assumption of the clustering not hold?\n6. The promotion ratio r for the DCI-tree and the number of levels L are crucial hyperparameters. How were they chosen? How sensitive are the results to their values?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9pMBzEoAgT", "reviewer": "Reviewer_Egcx", "summary": "IceCache introduces a new approach to memory-efficient KV-cache management for long-sequence LLMs. It uses a hierarchical DCI-tree that clusters key embeddings based on semantic similarity, grouping related tokens into memory pages. IceCache further employs bulk data loading and CPU-GPU pipelining to minimize latency. Tested on models like LLama-3.1-8B, Mistral-7B, Qwen3-32B, LongChat-7B on various tasks. It maintains over 99% accuracy with a 256 token budget.", "questions": "1. What is the latency for prefill stage, since you introduce additional clustering and indexing \n2. Did you try on multi-turn conversation where context may change, since I assume the serial workflow in Figure 4 means multi-turn. What is the latency and accuracy.\n3. Figure 4 is lack of explanation and notations, hard to understand. \n4. Did IceCache select page for each decoding step or only once for the whole decoding phase.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. High efficiency and accuracy: while cutting KV memory usage, achieve high accuracy\n2. Fine-grained retrieval: per-head-query-aware selection, improve attention focus\n3. Efficient pipelining: CPU-GPU overlap computation with data movement to reduce latency", "weaknesses": "1. Limited analysis: missing ablations on index depth, page size and computational cost of clustering and updates\n2. Scalability uncertainty: effectiveness and efficiency on extremely long contexts or distributed multi-GPU settings\n3. Figure clarity and presentation issues: figure 1 & 4 are not well-explained or visually clear. lack of consistent notation and labeling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lT7jYsZdiw", "reviewer": "Reviewer_815Q", "summary": "This paper introduces IceCache, a novel KV-cache management strategy designed to mitigate memory bottlenecks for LLMs processing long sequences. The core idea is to move beyond storing the KV-cache in its original token order. Instead, IceCache clusters tokens based on the semantic similarity of their key embeddings into a hierarchical structure called a DCI-tree. During inference, it employs a fast Approximate Nearest Neighbor (ANN) search algorithm (M-DCI) on the CPU to perform a query-aware, head-specific selection of the most relevant memory pages. These selected pages are then transferred from CPU to GPU for attention computation. The system is optimized with a pipelined workflow that overlaps the CPU-based page selection with GPU computations to hide latency. Experimental results across several benchmarks and models show that IceCache can maintain high accuracy (over 99% in some cases) with a significantly reduced token budget compared to the full KV-cache and outperforms other baseline methods.", "questions": "1.  Could you provide performance curves showing how the inference speed (e.g., tokens per second) scales with increasing context length?\n\n2.  The ANN search is currently performed on the CPU to overlap with GPU computations. Have you considered the feasibility of further accelerating the M-DCI query step by implementing it on the GPU?\n\n3.  The proposed method seems to be tightly integrated with a CPU offloading strategy. Is it possible to adapt IceCache for a non-offload scenario (i.e., where the full KV-cache fits in GPU memory, but sparsity is desired to accelerate computation)? Or does the method fundamentally rely on the CPU having access to the cache for the DCI-tree query to work?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The authors compare IceCache against a strong and sufficient set of six recent state-of-the-art KV-cache optimization methods.\n\n- The paper is well-organized and clearly written. The motivation is well-established, the proposed method is described logically with helpful diagrams (e.g., Figure 1 and 2).\n\n- The application of a hierarchical ANN algorithm (M-DCI) to cluster and retrieve from the high-dimensional key-embedding space of the KV-cache is a novel and interesting approach.", "weaknesses": "- The paper does not provide an analysis of how different parameter choices of M-DCI affect the final model accuracy and inference latency. Furthermore, the specific parameter values used in the experiments are not clearly described, which could hinder reproducibility.\n\n- The latency analysis in Section 5.5 focuses on \"Time to the second token\" (TT2T) and \"Time per output token\" (TPOT). While informative, it lacks a direct end-to-end runtime comparison against full attention.\n\n- A central claim is that grouping semantically similar tokens into the same memory pages improves efficiency. However, there is no ablation study to isolate and quantify this specific contribution. Since the index selection happens on the CPU, a key question arises: does this memory layout truly enhance efficiency, or is the performance bottleneck dominated by the CPU search and the CPU-GPU data transfer overhead?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)