ArkVale: Efficient Generative LLM Inference with Recallable Key-Value Eviction

Renze Chen, Zhuofeng Wang, Beiquan Cao, Tong Wu, Size Zheng, Xiuhong Li, Xuechao Wei, Shengen Yan, Meng Li, Yun Liang

TL;DR

ARKVALE is a novel Key-Value (KV) cache management system that addresses the "permanent eviction" problem in long-context LLM inference. By backing up evicted tokens to CPU memory and using clever geometric "digests" to predict when they might become relevant again, it achieves up to a 2.2× speedup in decoding and a 4.6× boost in throughput with negligible accuracy loss.

What Problem Does This Paper Address?

As Large Language Models (LLMs) scale to handle massive context windows (32k to 1M+ tokens), they hit a severe physical bottleneck: the Key-Value (KV) cache. To generate each new token, the model must attend to the keys and values of every previous token. This cache grows linearly with sequence length, quickly devouring GPU memory and slowing down inference due to massive memory access overhead.

Attention latency dominates as sequence length grows.

Existing solutions attempt to "evict" (delete) unimportant tokens to save space. However, these methods usually assume that if a token isn't important now, it never will be. The authors of ARKVALE discovered a "dynamic shift" in token importance: a token that seems useless at step 100 might suddenly become the most critical piece of information at step 5,000. If the system has already permanently deleted it, the model’s accuracy plummets.

Methods: Page-Based Recallable Eviction

ARKVALE introduces a "Page-based Recallable Eviction" strategy. Instead of permanently deleting tokens, it manages them similarly to virtual memory in an operating system.

Comparison of KV cache management strategies, highlighting ArkVale's Keep & Recall approach.

The system operates through four main mechanisms:

  1. Paged Organization: Inspired by systems like vLLM, tokens are grouped into "pages" (e.g., 32 tokens per page) for streamlined memory management.
  2. Asynchronous Backup: When a KV page is filled on the GPU, it is copied to the CPU memory (RAM) as a backup. This happens asynchronously in the background to avoid blocking GPU computation.
  3. Page Digests (The "Secret Sauce"): To avoid moving massive amounts of data back and forth just to check importance, the GPU keeps a tiny "digest" of each page. ARKVALE uses Bounding Volumes—a technique borrowed from computer graphics—to summarize the high-dimensional keys in a page. They tested two shapes:
  4. Bounding-spheres: Storing a center point and a radius.
  5. Bounding-cuboids: Storing the minimum and maximum values across all dimensions (Axis-Aligned Bounding Boxes).
  6. Dynamic Recall: Before each attention step, the model uses the current query and these tiny digests to estimate which pages (even those currently offloaded to the CPU) are most important. It then "recalls" the top-ranked pages back to the GPU and evicts the least important ones.

Key Insights and Results

The authors evaluated ARKVALE using comprehensive benchmarks like LongBench (multi-document QA, summarization, few-shot learning) and Passkey Retrieval (a synthetic "needle in a haystack" test up to 30k tokens).

  • Token Importance is Not Static: The most striking insight is that pages can start with zero importance but "spike" to become crucial thousands of tokens later.
  • Geometric Summarization Works: Using Bounding Cuboids (specifically the "cuboid-mean" variant) allows the system to estimate the maximum possible dot product between a query and a page of keys with surprising accuracy, achieving 95% recall for the top-1 page.
  • Communication is Cheaper than Computation: The overhead of moving a few pages from CPU to GPU takes mere hundreds of microseconds, while the time saved by skipping attention on thousands of "junk" tokens is measured in milliseconds.

Performance Highlights: * Accuracy: On the Passkey Retrieval task, standard eviction methods (like H2O or StreamingLLM) dropped to <50% accuracy as context grew. ARKVALE maintained >95% accuracy across all tested lengths. * Speed: ARKVALE achieved up to 2.2× speedup (1.7× average) in decoding latency compared to full-cache baselines. * Throughput: By drastically reducing the GPU memory footprint per request, ARKVALE allowed for much larger batch sizes, resulting in up to 4.6× higher throughput (3.5× average). * Efficiency: The system performs exceptionally well with a strict cache budget of only 2k–4k tokens, even when the total context is significantly longer.

Limitations and Future Work

While highly effective, ARKVALE does have limitations:

  • CPU Memory Pressure: By saving GPU memory, ARKVALE shifts the storage burden to CPU memory. For extremely long sequences or high-concurrency environments, CPU RAM could become a bottleneck, potentially requiring offloading to slower NVMe storage.
  • Prefill Overhead: The asynchronous backup works perfectly during the "decoding" phase, but the initial "prefill" (reading the prompt) phase is harder to hide, as the backup latency cannot be fully overlapped with computation.
  • Hardware Dependency: Performance gains rely heavily on the bandwidth of the CPU-GPU interconnect (e.g., PCIe). Slower links might diminish the benefits of the dynamic recall mechanism.

Future work may explore even more compressed digests or investigate how this "recall" logic could be natively integrated into an LLM's training process.

Summary updated

Abstract

Large Language Models (LLMs) are widely used in today's tasks of natural language processing. To support applications like multi-turn chats, document understanding, and content generation, models with long context lengths are growing in importance. However, managing long contexts brings substantial challenges due to the expansion of key-value cache (KV cache). Longer KV cache requires larger memory, limiting the batch-size thus decreasing throughput. Also, computing attention over long KV cache incurs more memory access, hurting the end-to-end latency. Prior works find that it is sufficient to use only the recent and high-impact tokens for attention computation, allowing the eviction of less vital tokens to shrink cache size. Nonetheless, we observe a dynamic shift in token importance across different decoding steps. Tokens initially evicted might regain importance after certain decoding steps. To address this, we propose ArkVale, a page-based KV cache manager that can recognize and recall currently important tokens evicted before. We asynchronously copy the filled page into external memory (e.g., CPU memory) as backup and summarize it into a much smaller digest by constructing the bounding-volume of its keys. Before attention computation, we measure all pages' importance based on their digests, recall the important ones, evict the unimportant ones, and select the top-ranked pages for attention computation. Experiment results show that ArkVale performs well on various long context tasks with negligible accuracy loss under 2k$\sim$4k cache budget and can improve decoding latency to $2.2\times$ and batching throughput to $4.6\times$ because it applies attention on only a small subset of pages and reduce per-sample memory usage of KV cache.
BibTeX
@inproceedings{chen2024arkvale,
  author = {Renze Chen and Zhuofeng Wang and Beiquan Cao and Tong Wu and Size Zheng and Xiuhong Li and Xuechao Wei and Shengen Yan and Meng Li and Yun Liang},
  title = {{ArkVale: Efficient Generative LLM Inference with Recallable Key-Value Eviction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=4oAt5L4lYe},
}
Figure