PaperlayerView exact revision on arXiv

Source-linked AI summary

IceCache: Memory-efficient KV-cache Management for Long-Sequence LLMs

Yuzhen Mao, Qitong Wang, Martin Ester, Ke Li

arXiv:2604.10539v1cs.LGcs.AI

TL;DR

Long-context LLM inference is constrained by KV-cache growth and by imperfect token selection during CPU offloading. IceCache combines semantic clustering, hierarchical dynamic indexing, and PagedAttention to manage pages selectively, retaining near-full-cache accuracy with much smaller budgets and competitive latency.

  • Problem

    KV-cache memory grows linearly with sequence length, while prior CPU-offloading methods may select relevant tokens imprecisely and degrade on long-generation tasks.

  • Method

    IceCache combines semantic token clustering with PagedAttention and a dynamically updatable hierarchical DCI-tree for query-aware page selection and CPU–GPU offloading.

  • Results

    Across diverse long-context benchmarks, IceCache achieves superior accuracy–latency trade-offs, retaining near-oracle performance with budgets as small as 64 tokens.

  • Takeaways & Limitations

    IceCache provides a scalable, practical approach to memory-efficient long-context LLM inference under constrained GPU memory.

  • Takeaways & Limitations

    The indexing method assumes c ≥ max_j′ ∥k_j′∥_2 and uses Euclidean distance.

Abstract

from arXiv · show

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

1 INTRODUCTION

IceCache addresses KV-cache memory pressure and long-generation degradation by combining semantic token clustering, hierarchical indexing, and PagedAttention-based offloading. Across diverse tasks, it improves accuracy–efficiency trade-offs under constrained GPU memory.

  • KV-cache memory grows linearly with sequence length, creating severe memory pressure and potential out-of-memory errors on resource-constrained devices.
  • Existing offloading methods often identify relevant tokens imprecisely and lack effective updates, causing degradation in long-generation tasks.
  • IceCache groups semantically related tokens into shared memory pages through semantic clustering integrated with PagedAttention.This organization aims to improve page-selection hit rates and CPU–GPU memory-bandwidth utilization.
  • The DCI-tree provides hierarchical indexing and dynamic updates, while a pipelining scheme overlaps CPU and GPU computation to hide indexing and retrieval latency.
  • IceCache was evaluated on Passkey Retrieval, LongBench, and GSM8K CoT across four open-source LLMs and diverse long-context tasks.It consistently outperformed six state-of-the-art KV-cache baselines.
  • IceCache sustained near-oracle performance with budgets as small as 64 tokens while reducing CUDA memory usage and decoding latency relative to existing baselines.

2 RELATED WORK

Prior KV-cache management methods trade speed, adaptability, and memory efficiency in different ways. IceCache addresses these limitations by combining semantic page organization with query-aware retrieval and CPU–GPU offloading.

  • Eviction-based methods avoid transfer overhead but often use static selection strategies that adapt poorly to changing contexts.
  • Offloading-based methods dynamically preserve important entries but introduce CPU–GPU transfer overhead.
  • H2O, StreamingLLM, and SnapKV use selective token-retention strategies that may struggle in long-generation scenarios because of limited adaptability.
  • PagedAttention improves memory allocation by dividing KV-cache storage into fixed-size pages, reducing fragmentation and supporting longer contexts.However, it does not prevent the KV-cache from continuously growing during decoding.
  • Quest and ArkVale perform query-aware top-k page selection, but their original-token-order pages can scatter semantically relevant tokens across multiple pages.
  • IceCache instead clusters similar tokens into shared pages, increasing relevant-token co-location while reducing unnecessary memory transfers.

3 BACKGROUND

The background describes autoregressive inference, sparse attention, and approximate nearest-neighbor indexing as foundations for selective KV-cache retrieval. These components motivate identifying only the most relevant keys during decoding.

  • Attention takes keys K, queries Q, and values V, optionally together with a binary mask S controlling which query–key pairs may interact.
  • The attention matrix is typically sparse, with only a few large weights in each row and most remaining weights near zero.
  • Exploiting sparsity allows approximate attention to compute inner products only for the k unmasked keys expected to receive the highest weights.This can reduce computational resource use without evaluating all keys.
  • LLM inference consists primarily of prefill, which computes and stores prompt keys and values, followed by decoding, which generates tokens while iteratively using and updating the KV-cache.
  • P-DCI performs efficient high-dimensional k-nearest-neighbor search using multiple indices that rank points by projected distance lower bounds.
  • M-DCI extends P-DCI with multiple hierarchical levels in which points are promoted and assigned parents, forming a tree structure for more efficient search.

4 ICECACHE

IceCache manages KV-cache storage through semantic clustering, hierarchical indexing, query-driven page selection, and efficient CPU–GPU transfers. Its dynamic DCI-tree preserves semantic locality while supporting updates during decoding and overlapping indexing with computation.

  • Overview: IceCache uses indexing, page selection, and bulk loading to manage clustered KV-cache entries during prompt processing and decoding.Similar tokens are grouped into DCI-tree nodes; M-DCI selects relevant pages, which are transferred from CPU to GPU.
  • Semantic organization: The DCI-tree maps each hierarchical node to a physical memory page, with metadata and mapping tables locating associated key-value embeddings.The structure is maintained separately for each attention head to preserve semantic locality in storage.
  • Semantic organization: Semantic clustering concentrates query-relevant tokens into fewer pages than original-order layouts, improving retrieval efficiency and selection precision.PagedAttention-based methods may scatter relevant tokens across pages, requiring retrieval of irrelevant entries.
  • Latency optimization: IceCache constructs its index during prompt processing or CPU offloading, amortizing tree-construction cost and avoiding additional inference latency.Its pipeline overlaps CPU indexing with GPU computation and data transfers.
  • Dynamic updates: New token embeddings receive tree levels and parent links during decoding, while oversized nodes trigger dynamic page allocation to maintain balance.Incremental updates allow the index to accommodate new token windows without treating page layout as static.
  • Page selection: M-DCI performs head-specific approximate nearest-neighbor search to select the top-k pages most relevant to each decoding query.This page-selection objective is to maximize recall of significant keys while loading only limited pages into GPU memory.

5 EXPERIMENTS

IceCache is evaluated across long-context retrieval, LongBench accuracy, latency, and Chain-of-Thought reasoning under constrained KV-cache budgets. It generally preserves or improves accuracy while offering competitive latency, with especially strong results at low budgets.

  • Passkey Retrieval: 100% retrieval accuracy is maintained across cache budgets of 256, 128, and 64 tokens in passkey retrieval.The evaluation spans 10k–100k-word contexts and passkey positions from 0% to 95%.
  • LongBench Accuracy: 47.8 average accuracy at budget 64 surpasses PQCache’s 47.3 using budget 256 on Llama-3.1-8B-Instruct.At budget 256, IceCache reaches 49.0 versus 49.5 for Full KV.
  • LongBench Accuracy: 41.7 average accuracy at budget 256 exceeds MagicPig’s 39.1 on Mistral-7B-Instruct.At budget 64, IceCache scores 39.0, close to MagicPig’s 39.1 with a four-times larger budget.
  • Latency Analysis: 5.9 seconds TT2T for IceCache(reuse) matches OmniKV’s 5.8 seconds and outperforms ArkVale’s 7.4 and PQCache’s 13.3 seconds.Vanilla IceCache records 7.7 seconds; eviction-based methods are faster but trade speed for accuracy.
  • GSM8K CoT Reasoning: 47.4% GSM8K CoT accuracy exceeds PQCache’s 46% under the same 10% budget and nearly matches Full KV’s 48.2%.The evaluation uses Mistral-7B-Instruct-v0.2.

6 CONCLUSION

The paper presents IceCache as a memory-efficient framework for long-context LLM inference. Its DCI-tree, semantic clustering, and GPU–CPU offloading target improved accuracy–latency trade-offs under growing KV-cache demands.

  • IceCache addresses long-context inference challenges caused by rapidly growing KV-cache memory use and reduced computational efficiency.
  • IceCache combines a dynamically updated hierarchical DCI-tree with semantic token clustering, PagedAttention, and GPU–CPU offloading.The framework organizes KV-cache pages for long-context processing.
  • IceCache consistently achieves superior accuracy–latency trade-offs across diverse long-context benchmarks.The conclusion characterizes it as a scalable and practical solution for memory-efficient inference.

A METHOD OVERVIEW

IceCache divides KV-cache management into prefill and decode phases, using GPU-resident sink and window pages alongside CPU-hosted indexed cache entries. Its dynamic index supports retrieval of important tokens during autoregressive decoding.

  • Sink and window pages remain on the GPU, while intermediate tokens occupy the remaining KV-cache pages.Sink tokens are at the input beginning, and window tokens are the most recent tokens.
  • Prefill Phase: During prefill, IceCache allocates paged KV memory per layer, computes self-attention, copies later-layer embeddings to CPU, and builds the DCI-tree.The DCI-tree enables future lookup of important tokens using query embeddings.
  • Decode Phase: During decode, each new token’s query embedding is used to retrieve important cached tokens through the dynamic index.

B DETAILS OF ICECACHE (REUSE) ON LONGBENCH

IceCache(reuse) reduces repeated indexing and retrieval by using anchor layers and reusing selected KV-cache indices between them. Its LongBench results are reported in Table 5.

  • Starting from the third layer, IceCache(reuse) performs DCI queries every three layers, which are designated anchor layers.
  • Intermediate layers reuse KV-cache indices selected at the most recent anchor layer.This defines the reuse variant’s reduced-query schedule.
  • Table 5 reports IceCache(reuse) accuracy on LongBench.

C PERFORMANCE ON LONG GENERATION BENCHMARK

On LongGenBench, IceCache substantially outperforms PQCache while maintaining accuracy comparable to the Full-KV baseline under a 256-token budget.

  • 256-token budget: IceCache substantially outperforms PQCache on LongGenBench with Llama-3.1-8B-Instruct.The comparison concerns accuracy on long-context generation tasks.
  • IceCache maintains accuracies on par with the Full-KV baseline on LongGenBench.The result is reported for Llama-3.1-8B-Instruct using a 256-token budget.
  • Table 6 presents the accuracy comparison between IceCache and other methods on LongGenBench.

D LLM USAGE

The paper identifies its models as LLMs and reports using an LLM to refine the manuscript’s language and readability. The supplied implementation passages additionally describe the inference and indexing procedures used by IceCache.

  • All base models used in the paper are treated as large language models, including Llama-3.1, Mistral, Qwen3, and LongChat variants.
  • The authors used an LLM to refine the manuscript’s language and improve its overall readability.
  • The DCI-INDEXING procedure inserts keys into a hierarchical tree using promoted levels and queried parent nodes.Random promotion determines levels before each key is inserted into the tree.
  • IceCache’s implementation includes page-selection and k-nearest-neighbour querying procedures over a DCI-tree.The supplied pseudocode includes PAGE-SELECT, QUERY, and k-nearest-neighbour querying components.
Loading 2604.10539v1…