Training-Free Exponential Extension of Sliding Window Context with Cascading KV Cache

• URL: http://arxiv.org/abs/2406.17808v1
• Date: Mon, 24 Jun 2024 03:59:17 GMT
• Title: Training-Free Exponential Extension of Sliding Window Context with Cascading KV Cache
• Authors: Jeffrey Willette, Heejun Lee, Youngwan Lee, Myeongjae Jeon, Sung Ju Hwang,
• Abstract summary: We propose a novel mechanism for storing longer sliding window contexts with the same total cache size. We show improvements of 5.6% on long context generation (LongBench), 1.2% in streaming perplexity (PG19), and 0.6% in language understanding (MMLU STEM) using LLMs given the same fixed cache size.
• Score: 49.608367376911694
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The context window within a transformer provides a form of active memory for the current task, which can be useful for few-shot learning and conditional generation, both which depend heavily on previous context tokens. However, as the context length grows, the computational cost increases quadratically. Recent works have shown that saving a few initial tokens along with a fixed-sized sliding window leads to stable streaming generation with linear complexity in transformer-based Large Language Models (LLMs). However, they make suboptimal use of the fixed window by naively evicting all tokens unconditionally from the key-value (KV) cache once they reach the end of the window, resulting in tokens being forgotten and no longer able to affect subsequent predictions. To overcome this limitation, we propose a novel mechanism for storing longer sliding window contexts with the same total cache size by keeping separate cascading sub-cache buffers whereby each subsequent buffer conditionally accepts a fraction of the relatively more important tokens evicted from the previous buffer. Our method results in a dynamic KV cache that can store tokens from the more distant past than a fixed, static sliding window approach. Our experiments show improvements of 5.6% on long context generation (LongBench), 1.2% in streaming perplexity (PG19), and 0.6% in language understanding (MMLU STEM) using LLMs given the same fixed cache size. Additionally, we provide an efficient implementation that improves the KV cache latency from 1.33ms per caching operation to 0.54ms, a 59% speedup over previous work.

Related papers

• Sparse-dLLM: Accelerating Diffusion LLMs with Dynamic Cache Eviction [58.044803442346115]
  Diffusion Large Language Models (dLLMs) enable breakthroughs in reasoning and parallel decoding but suffer from prohibitive computational complexity and memory overhead during inference.<n>We propose Sparse-dLLM, the first training-free framework integrating dynamic cache eviction with sparse attention via delayed bidirectional sparse caching.
  arXiv  Detail & Related papers  (2025-08-04T16:14:03Z)
• Compress, Gather, and Recompute: REFORMing Long-Context Processing in Transformers [58.98923344096319]
  REFORM is a novel inference framework that efficiently handles long contexts through a two-phase approach.<n>It achieves over 50% and 27% performance gains on RULER and BABILong respectively at 1M context length.<n>It also outperforms baselines on Infinite-Bench and MM-NIAH, demonstrating flexibility across diverse tasks and domains.
  arXiv  Detail & Related papers  (2025-06-01T23:49:14Z)
• ZSMerge: Zero-Shot KV Cache Compression for Memory-Efficient Long-Context LLMs [7.958429361868486]
  We propose ZSMerge, a dynamic KV cache compression framework for efficient cache management. ZSMerge significantly enhances memory efficiency and inference speed with negligible performance degradation.
  arXiv  Detail & Related papers  (2025-03-13T03:36:03Z)
• CacheFocus: Dynamic Cache Re-Positioning for Efficient Retrieval-Augmented Generation [6.544043376474944]
  Large Language Models (LLMs) excel across a variety of language tasks yet are constrained by limited input lengths and high computational costs. Existing approachestextemdash partially alleviate these issues but often require additional training or suffer from performance degradation with longer inputs. We introduce textbftextitCacheFocus, a method that enhances length normalization and reduces inference latency without any further training.
  arXiv  Detail & Related papers  (2025-02-16T12:33:16Z)
• CSR:Achieving 1 Bit Key-Value Cache via Sparse Representation [63.65323577445951]
  We propose a novel approach called Cache Sparse Representation (CSR) CSR transforms the dense Key-Value cache tensor into sparse indexes and weights, offering a more memory-efficient representation during LLM inference. Our experiments demonstrate CSR achieves performance comparable to state-of-the-art KV cache quantization algorithms.
  arXiv  Detail & Related papers  (2024-12-16T13:01:53Z)
• EPIC: Efficient Position-Independent Context Caching for Serving Large Language Models [19.510078997414606]
  EPIC introduces position-independent context caching for large language models. EPIC delivers up to 8x improvements in TTFT and 7x throughput over existing systems.
  arXiv  Detail & Related papers  (2024-10-20T08:42:29Z)
• ThinK: Thinner Key Cache by Query-Driven Pruning [63.13363917871414]
  Large Language Models (LLMs) have revolutionized the field of natural language processing, achieving unprecedented performance across a variety of applications. This paper focuses on the long-context scenario, addressing the inefficiencies in KV cache memory consumption during inference. We propose ThinK, a novel query-dependent KV cache pruning method designed to minimize attention weight loss while selectively pruning the least significant channels.
  arXiv  Detail & Related papers  (2024-07-30T17:59:08Z)
• Efficient Inference of Vision Instruction-Following Models with Elastic Cache [76.44955111634545]
  We introduce Elastic Cache, a novel strategy for efficient deployment of instruction-following large vision-language models. We propose an importance-driven cache merging strategy to prune redundancy caches. For instruction encoding, we utilize the frequency to evaluate the importance of caches. Results on a range of LVLMs demonstrate that Elastic Cache not only boosts efficiency but also notably outperforms existing pruning methods in language generation.
  arXiv  Detail & Related papers  (2024-07-25T15:29:05Z)
• PQCache: Product Quantization-based KVCache for Long Context LLM Inference [27.523568511043273]
  Key-Value Cache (KVCache) is a crucial component in Large Language Models (LLMs) Current methods selectively determine suitable keys and values for self-attention in LLMs to address the issue. We propose PQCache, which employs Product Quantization (PQ) to manage KVCache, maintaining model quality while ensuring low serving latency.
  arXiv  Detail & Related papers  (2024-07-01T13:05:42Z)
• CORM: Cache Optimization with Recent Message for Large Language Model Inference [57.109354287786154]
  We introduce an innovative method for optimizing the KV cache, which considerably minimizes its memory footprint. CORM, a KV cache eviction policy, dynamically retains essential key-value pairs for inference without the need for model fine-tuning. Our validation shows that CORM reduces the inference memory usage of KV cache by up to 70% with negligible performance degradation across six tasks in LongBench.
  arXiv  Detail & Related papers  (2024-04-24T16:11:54Z)
• Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference [78.65321721142624]
  We focus on a memory bottleneck imposed by the key-value ( KV) cache. Existing KV cache methods approach this problem by pruning or evicting large swaths of relatively less important KV pairs. We propose LESS, a simple integration of a constant sized cache with eviction-based cache methods.
  arXiv  Detail & Related papers  (2024-02-14T18:54:56Z)
• SubGen: Token Generation in Sublinear Time and Memory [48.35076900702408]
  Large language models (LLMs) have extensive memory requirements for token generation. In this work, we focus on developing an efficient compression technique for the KV cache. We have devised a novel caching method with sublinear complexity, employing online clustering on key tokens and online $ell$ sampling on values. Not only does this algorithm ensure a sublinear memory footprint and sublinear time complexity, but we also establish a tight error bound for our approach.
  arXiv  Detail & Related papers  (2024-02-08T22:17:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.