Training Free Exponential Context Extension via Cascading KV Cache
Authors: Jeffrey Willette
Heejun Lee
Youngwan Lee
Myeongjae Jeon
Sung Ju Hwang
Venue: ICLR 2025 Poster (2025)
Keywords: transformer
efficiency
linear attention
Primary area: generative models
TL;DR: We propose a novel linear prefill strategy for pretrained transformers with linear scaling KV caches which delivers practical and efficient linear scaling during inference.

Abstract: The transformer's context window is vital for tasks such as few-shot learning and conditional generation as it preserves previous tokens for active memory. However, as the context lengths increase, the computational costs grow quadratically, hindering the deployment of large language models (LLMs) in real-world, long sequence scenarios. Although some recent key-value caching (KV Cache) methods offer linear inference complexity, they naively manage the stored context, prematurely evicting tokens and losing valuable information. Moreover, they lack an optimized prefill/prompt stage strategy, resulting in higher latency than even quadratic attention for realistic context sizes. In response, we introduce a novel mechanism that leverages cascading sub-cache buffers to selectively retain the most relevant tokens, enabling the model to maintain longer context histories without increasing the cache size. Our approach outperforms linear caching baselines across key benchmarks, including streaming perplexity, question answering, book summarization, and passkey retrieval, where it retains better retrieval accuracy at 1M tokens after four doublings of the cache size of 65K. Additionally, our method reduces prefill stage latency by a factor of 6.8 when compared to flash attention on 1M tokens. These innovations not only enhance the computational efficiency of LLMs but also pave the way for their effective deployment in resource-constrained environments, enabling large-scale, real-time applications with significantly reduced latency.

Published as a conference paper at ICLR 2025
TRAINING-FREE EXPONENTIAL CONTEXT EXTENSION VIA CASCADING KV CACHE
'Jeffrey Willette, 'Heejun Lee, Younggan Lee
KAIST AI, 'ETRI, South Korea
(jwillette, sinntteestainneeettsts... yw. re. kr
Myeongjae Jeon
Sung Ju Hwang
POSTECH, South Korea mj. www.jeosstecc..ac... ac.kr
KAIST AI, Deepauto.at ai, South Korea
hawagju wac.sttaa....................... acc. kr
ABSTRACT
The transformer's context window is vital for tasks such as few-shot learning and conditional generation it preserves previous tokens for active memory. How- ever, as the context lengths increase, the computational costs grow quadratically. hindering the deployment of large language models (LLMs) real-world, long sequence scenarios. Although some recent key-value caching (KV Cache) meth- ods offer linear inference complexity, they naively manage the stored context, prematurely evicting tokens and losing valuable information. Moreover, they lack an optimized prefill/prompt stage strategy, resulting in higher latency than even quadratic attention for realistic context sizes. In response, we introduce a novel mechanism that leverages cascading sub-cache buffers to selectively retain the most relevant tokens, enabling the model to maintain longer context histories without increasing the cache size. Our approach outperforms linear caching base- lines across key benchmarks, including streaming perplexity, question answering, book summarization, and passkey retrieval, where it retains better retrieval accu- racy at 1M tokens after four doublings of the cache size of 65K. Additionally, our method reduces prefill stage latency by a factor of 6.8 when compared to flash attention on IM tokens. These innovations not only enhance the computa- tional efficiency of LLMs but also pave the way for their effective deployment in resource-constrained environments, enabling large-scale, real-time applications with significantly reduced latency.
INTRODUCTION
Large language models (LLMs) have become indispensable in a wide range of applications, from natural language pro- cessing to Al-driven content generation. However, their de- ployment is often hindered by the significant computational resources required, particularly during the quadratic attention operation in inference. Despite recent advancements such as Flash Attention 2 (Dao, 2023), which reduce memory over- head, the quadratic growth of latency and compute costs with input size remains a burden, especially when processing long input sequences. This challenge is felt in streaming applica- tions, where high latency directly impacts user experience and operational costs.
sliding
Forgotten Contect
Capcade Bugder''s
Toker Span with Cascading
Exposeutial Token Span
Cascuding KV Cache (Ours)
Figure 1: Attention matrices from
Existing methods, such sliding window approaches (Belt- agy et al., 2020; Jiang et al., 2023), attempt to manage long sequences but impose static limit the model's ability to retain context due to the fixed window size. As a result, valuable tokens are naively discarded once they fall outside the window, leading irreversible loss of context. Although some recent meth-
Streaming LLM (Xiao et al., 2023) and Cascading KV Cache (Ours), both with the same total cache size.

---

Published as a conference paper at ICLR 2025
ods have tried to stabilize this process by preserving a small number of initial tokens (Xiao al., 2023) (Figure 3 top), they still operate within a static framework with a naive eviction policy that does not account for the relative importance of tokens within the sequence. Additionally, the linear inference procedure from Xiao et al. (2023) processes a single token per step, which is impractical to apply during the prompting stage when many tokens need to be processed together in parallel.
Our work addresses these critical limitations by propos- ing novel linear inference approach that extends the effective context length of sliding windows without in- creasing computational complexity or requiring addi- tional training. We introduce a dynamic caching mech- anism that organizes the key-value (KV) cache into cas- cading sub-caches, each designed to selectively retain to- kens based on their importance. As opposed to a fixed sliding window that only evicts tokens at the end, our method offers multiple eviction routes before reaching the end, while intelligently preserving older tokens, which are likely to play a crucial role in future predictions.
100%
Gasade (Ouss,
Steeaming
806
Cache Slze (BSk)
Accunny
40%
2066
20:05
000K
600K Coulacc Stan
900K
IM
Figure 2: Passkey accuracy up to IM to- kens given a cache size of 65K. Our Cascad- ing cache maintains higher accuracy even af- ter four doublings of the context length.
To demonstrate the effectiveness of our method, we present two compelling examples: First, we visualize the attention matrix on the PG19 test set, showing how our cascading KV cache retains context far beyond a static sliding window while maintaining the same total cache size (Figure 1). Second, we provide an example on passkey retrieval up IM tokens given a total cache size of 65K (Figure 2), illustrating that our method consistently outperforms static window attention in terms of retrieval accuracy, maintaining superior performance over prior work even after four doublings of the context size. These results underscore the potential of our approach to transform the efficiency and accuracy of long-context I.LMs in both research and real- world applications. Our contributions are as follows:
We introduce a simple yet powerful training-free linear attention modification to sliding window attention pretrained quadratic transformers that selectively retains important tokens, significantly extending the effective context length.
Given the same total KV cache size, our method delivers substantial improvements of 12.13% average in long context benchmarks (LongBench), 0.4% in streaming perplex- ity (PG19), 4.48% in Book Summarization, and increases passkey retrieval accuracy by 24 percentage points (pp) at IM token after four doublings of the context size and 18pp higher accuracy after 5 doublings of the context size.
We provide linear prefill strategy that avoids the restrictive quadratic prompt complexity of previous works. Our strategy reduces latency on 1M tokens by factor of 6.8 compared to Flash Attention 2.
We provide an efficient implementation' of our KV cache, which achieves more than two order of magnitude speedup over Streaming LLM.
2 RELATED WORK
Previous research has explored sparse attention patterns to reduce computational costs, such as in BigBird (Beltagy et al., 2020), where a sliding window with random sparse context is applied. While effective in reducing time complexity, this approach relies on uninformative random atten- tion patterns that lack adaptability. Linear attention mechanisms, including locality-sensitive hash- ing (Kitaev et al., 2020), kernel-based approximations (Choromanski et al., 2020), attention matrix compression (Lee et al., 2023), and token compression techniques (Munkhdalai et al., 2024; Kim et al.. 2023; Mohtashami & Jaggi, 2023), offer promising alternatives but often require extensive retraining, limiting their broad applicability existing models.
Our work builds on insights from Streaming LLM (Xiao et al., 2023), which identified key phe- nomenon in transformers: as features progress through layers, attention scores often concentrate
httpp:://gt cttp://fc///ff/fa/e cesett//caccainnn sasscadinggky_ceee
2

---

Published as a conference paper at ICLR 2025
Key Value Caches
Sink Tokens
Evicted Tokens
New Token
Sink Attention
Attention Score
Exiet?/Keepp?
Sink Tokeni
(EMA))
New Taken
Cascade (Ours)
Evicted Tokens
1/2
1/2 1/2
1/22
Token Acceplance Ratio
Comparison of Streaming LLM (Xiao al., 2023) and Cascading Cache (Ours). Top: Streaming LLM stores fixed sink tokens (red) along with a sliding window of recent tokens. Bottom: Our method segments the cache into smaller cascading sub- cab-caches, where each successive sub-cache conditionally accepts a fraction of tokens based on the magnitude of past attention scores. This simple technique allows for important tokens to remain in the cache for longer time instead of being naively evicted too early. Conversely, superflu- tokens may be evicted before reaching the end of the cache, allowing for intelligent eviction strategy.
Figure 3:
probability mass on the initial tokens, referred as "sink tokens." This phenomenon presents challenge in traditional fixed sliding windows, as evicting sink tokens from the cache disrupts the attention score distribution, forcing the model to redistribute probability mass onto other unexpected tokens. Xiao et al. (2023) demonstrated that this distribution shift leads to significant performance degradation unless the sink tokens are retained. We extend this insight by introducing an efficient, scalable method that increases the effective context window while maintaining a static cache size, improving throughput during the prompt stage, and enhancing performance on long-sequence tasks.
Subsequent approaches, such as SnapKV (Li et al., 2024) and H2O (Zhang et al., 2024b), have in- troduced score-based KV cache eviction policies, but these rely on quadratic prompts, with cache compression limited only to the decoding phase. These methods lack a linear prefill strategy, which results in the prefill attention operation remaining quadratic. Our method diverges from these previ- ous approaches by offering fast linear prefill strategy that is compatible with a cache that selectively retains important tokens through dynamic sparsity. This makes our approach not only more adap- tive but also significantly more efficient, providing practical path to extend transformer models' context length with linear complexity and without incurring the high costs of retraining.
3 METHOD
Notation. We use the common notation boldface lowercase letter to denote a vector æ and a boldface uppercase letter denote matrix X. A superscript (2) denotes that object belongs to layer 1, where E [1, 21,2.... LJ. To simplify notation for attention, we omit the head dimension, output projections, and multi-layer perceptron (MLP) transformations, please see Vaswani et al. (2017) for an overview regarding those topics. We refer to a generic cache as C, using subscripts Cg and Cy to refer to key and value caches, respectively.
Attention. Let S E N represent a token sequence length, where each token at layer I is represented by vector (0(0) E Rd. The collection of tokens in the sequence be represented as matrix (1) RSd With being the softmax function, and different learnable query, key, and value matrices Q(1, K(), y(l)) E _ddd the standard attention operation is as follows:
x = (22 (xxx"") (xx*
x (1) (1) e RRd
(1)
Key-Value (KV) Caching. During LLM inference, a single token is generated at each time step. Combined with a causality condition such that token æ; cannot influence x, iff j. it becomes more efficient to cache the (()) and (t)) projected tokens in each layer 1 rather than recomputing the full set of key, and value projections at each generation time step. Specifically, with U representing a concatenation operation along the S dimension, and each cache C' E Sxd the calculation of the attention operation for the current token æ; during inference becomes,
of (1+1) = ( Q (q Va
(ox2 (KWA")) (yPuvaaa)) E Rd
(2)
3

---

Published as a conference paper at ICLR 2025
SiA Ticce (hted)
Accepo Tokens
Ancpes n Tekess
Accepea in Tnken Free
Accepa Telics
Next sub-eache
add dldst sub-ccckk..
cache but cecho, token from subl-coche.
eldest
Add sus ieb-add
Case 3; Nect oubstarke is not ancepting saluns. Attention scere of aldeed taken (1L3) is lower than neseed token (ILS) in neet carbu - dhrard okleet biken
Case E Nest uib-carke is not accepling sakuns. Attention seare of oldret raken (8.9)
Ic liigheer than nivrrtt tiken (1.5) nest cache -e dhrard lower scared tokoe.
0.5
0.1
0,9
Tikku
Figure 4: Top: Each successive sub-cache window accepts fraction of tokens evicted from the previous sub-cache. Bottom: At the boundaries between sub-caches, there are four possible cases where our method takes a different conditional action, creating dynamic attention pattern. Circular buffers are not depicted for simplicity of visualization.
After the concatenation operation, x; K (9) and 3 (0) are considered to be added to the respective CR and Cy caches for the next iteration in the sequence.
Sliding window attention, as used by Streaming LLM, treats the KV cache as fixed size buffer which must evict tokens from the cache when the cache reaches its storage limit. Considering cache which is fully populated (denoted by an overbar C and omitting the layer index 1), when new token comes in, the cache must drop the oldest token in order to make space for the new token such that.
U Kay = 11 KK,, K0 K K K [Kx,))\ (Kx.).
The only difference between standard sliding window attention and sink cache of Streaming LLM (Xiao et al., 2023) is that the sink cache perpetually retains the first tokens in the sequence such that if a full cache starts from the first token æ1 K, is not token æ₁ K which is evicted, but N being a fixed hyperparameter. Both sliding window attention and sink
token T1+a K, with cache have the benefit of linear complexity, and a fixed overhead computation and memory cost for the window, as the size of the cache can only grow fixed, predetermined amount. However, this has the downside of constraining the information available in the cache, which may be needed for later predictions in the sequence. To illustrate, imagine streaming generation of an entire book with an LLM. If the cache can only contain tokens representing the average length of one chapter, then important information from previous chapters may be forgotten which could prove to be crucial for later steps of generation.
Linear Prefill. A crucial limitation of Streaming LLM (Xiao et al., 2023), H2O (Zhang et al., 2024b), and SnapKV (Li et al., 2024) lies the handling of the prompt/prefill stage of the LLM. Fach of the afore- mentioned works only considers that either 1) tokens processed one-by-one during the prompt 2) the prompt is processed with full quadratic attention and then proceeds apply the relevant caching strategy during the generation phase. Being limited in this way, even a linear model like Streaming LLM exhibits slower latency than a quadratic prompt utilizing flash attention in the non-asymptotic regime (see Figure 6b). To bridge this gap. our method utilizes an attention kernel which processes fixed- sized chunks (strides) of the prompt in single operation before adding the keys and values to our cascading cache. Specifically, for a sequence length of S. quadratic attention can be seen as having a stride size of S, Streaming LLM can be seen as having stride size of 1, and our prefill method can be seen as having a stride size K E [1, S] that is somewhere in between. Algorithm I contains pseudocode for our strided prefill process, and Figure 5 contains allows for a more than two order of magnitude decrease in latency compared to single token process- ing and reduces latency by a factor of 6.8 over quadratic flash attention when processing 1M tokens. This significant improvement delivers the benefits of linear attention on realistic, non-asymptotic sequence lengths.
Algorithm Strided Prefill
Require: inputs. cache, model, stride size for chunk in stride stride size) do for layer in model do
KV cache. get()
output, scores layer(chunk, KV) cache.update(ccunk, scores)
end for end for
illustration. Our strided prefill
4

---

Published as a conference paper at ICLR 2025
3.1 CASCADING KV CACHE
Our cache is a generalization of sliding window attention which allows for important historical tokens to be kept in the cache history for longer period of time. To accomplish this, we view fixed sized sliding window KV cache C' with cardinality |C| as a collection of sub-caches C, for
i E [I,....N] N., each with cardinality |C|| S |C| such that I C.I. |C|. Assuming a sub- cache is full, each full sub-cache C, evicts tokens when new token is accepted into the sub-cache. However, each sub-cache accepts new tokens at a different rate, which in turn means that tokens may be discarded between the sub-caches and not solely at the end of the total cache window. An example of this process is depicted in Figure 4 (top), where the blue cache accepts all new incoming tokens. The green sub-cache, however, accepts only half of the tokens which are evicted from the blue sub-cache (every 2nd iteration). The yellow sub-cache accepts half of the tokens evicted from the green sub-cache (every 4th iteration) and so on.
As Xiao et al. (2023) discovered, the initial attention sink to- kens are vital for the stability of generation. Therefore, we too keep a fixed sub-cache of the initial tokens as attention sinks. With our method, sink cache is a special case of a cascad- ing cache, where the number of cascades (sub-caches) is set to 1, and accepts all incoming tokens (i.e. using only the blue cache and red cache in Figure 4).
New query attention with new keys (dense)
Strdde Length (New
Cache
Token Selection. The process outlined in the preceding para- graph would result in fixed heuristic pattern of tokens being dropped. However, such a heuristic pattern is not ideal, as it may be the case that the model naively holds onto tokens with limited value, while discarding important tokens. To remedy this, instead of discarding tokens naively, we dynamically lect the most important tokens to retain by tracking the average attention score each token receives throughout time via an ex- ponential moving average (EMA). We then selectively discard the token with the lower attention score EMA where possible. Given hyperparameter y E [0. 1], and vector of attention scores for all keys in the cache 8% at timestep i, we update the stored average attention scores (1 as,
New query attention with cached keys
(sparse)
Figure 5: Our strided prefill. We first compute attention for chunk (stride) of new queries and new cached keys, forming a rectangular slice of the attention matrix at each step.
4e (1++) = yp (t) + (1 -1--10 7)
Consider the two sub-caches depicted in cases 2-4 of Figure 4. The blue sub-cache must accept all incoming tokens, while the green cache only accepts tokens every other iteration. Let the green cache be accepting tokens at the current timestep (case 2). When a new token comes in, it is added to the blue cache, which must then evict a token as the cache is full. The evicted token then goes to the green cache which accepts it unconditionally. The same process repeats the next iteration, however, this time the green cache will not be accepting tokens (cases 3-4). At this step, when the blue cache accepts and subsequently evicts a token, we compare the attention score of the token evicted from the blue cache with the attention score of the newest token in the green cache. The token with the higher attention score is set (or remains) as the newest token in the green cache, while the token with the lower attention score is discarded. For full pseudocode algorithm that covers cases 1-4 in Figure 4, see Algorithm 2 in the appendix.
Positional Encoding. We use the same positional encoding strategy as Streaming LLM, which reapplies positional encodings for each token the cache according to its index within the cache. Assuming that tokens with higher index are more recently added to the cache, the positional encoding function PE(X,, i) applies positional encoding index to token x,. For example, if our cache holds the token indices from the original sequence [0. 3, 5, 7, 8). they would in turn receive positional encodings [0, 1, 2, 4, which corresponds to their index within the cache.
Circular Buffers. Previous approaches have relied on tensor concatenation during cache add op- erations. However, this results in excessive copying operations, as each concatenation requires re- trieving and storing all entries into block of memory. We utilize more efficient circular buffers by tracking the location of the oldest token (()) at timestep (where insertion should occur). We then increment & after each insertion to the buffer such that g((+1) (g(O + +1) mod |C,]. This way,
at timestep we know that the oldest token in the buffer resides at g(t). When it is time to remove
5

---

Published as a conference paper at ICLR 2025
Stonazen LLM (Sttstal)
Atteerien Latengy (S)
Attertionn Lattoury (51
Strantik LLZ (Ogging
Coackee cascadd))
Fick Aitex
SeagKt
Dlapaie (iazk) 2030 sxak)
Comubotive 75
O0M
28 Rasettee
sta strie
srode
3010 arede
s112 andde
Ours
315
131
un 3M
Coatext Length
IM Tokens
(a) Cache Latency
(b) Attention Latency
(c) Strided Prefill Lateney
Figure 6: Latency. a) Our efficient cache implementation offers more than two orders of magnitude speedup over naive concatenation for cache add operations. b) Our strided prefill strategy is the only linear caching method which outperforms flash attention 2 lateney on realistic sequence lengths (IM tokens). We fit a second degree polynomial (dotted lines) predict latencies after quadratic models run out of memory a 49GB GPU, Strided prefill lateney for 1M tokens by different stride sizes.
a token, we simply overwrite the content of the memory address of ((t) rather than performing costly concatenation.
Cache Token Span. Given previously outlined cascading cache, we have lengthened the span of the tokens which currently reside in the cache. The process outlined above effectively extends sliding window context length by allowing older tokens to remain as keys and values for longer time, with gaps between tokens. Assuming that each sub-cache has the same capacity (i.e. |C|
IU CiI NNC D. and each will accept tokens with a different frequency function defined 7(F)* then the approximate context length will be a summation over the cache sizes and the inverse of the frequency functions. For example, if each successive sub-cache accepts half of the tokens evicted from the previous cache, the total span of the cache Š becomes Equation (4). We can then calculate the overall sparsity of the cache as 1 JC|/S and sparsity of the cache window as 1 - IC1/S.
C
5 f0)| = | Σ 2'-1=
2'11
4 EXPERIMENTS
Setup. We conduct experiments on streaming books (PG19) (Rae al., 2019), Long Context Un- derstanding (LongBench) (Bai et al., 2023b), book summarization (Booksum) (Kryšcińskii et al., 2021), and 1M token passkey retrieval. We evaluate our method with pretrained transformers from the Llama3. 1 (Dubey et al., 2024) and Qwen2 (Bai et al., 2023a) families of models. Please see Ta- ble 5 for model paths. In all our experiments, we keep the first 64 initial tokens as attention sinks. When considering the number of tokens in the cache, we always consider the sink tokens to be in addition to the cache size. Therefore a cache size of |C| has a total of |C] + 64 total tokens. We set the EMA parameter y = 0.9999. We use the cascade token acceptance policy depicted in Figure 4 and Equation (4), where each sub-cache accepts half of the tokens from the previous sub-cache. Un- less otherwise indicated, our models use four cascading sub-caches. As Streaming LLM is a special case of our model, and 1 token per step is prohibitively slow, all results involving Streaming LLM results use our strided prefill strategy. Note that the strided prefill improves results over the original Streaming LLM with one token per step as shown in Figure 11. See Appendix B for further details.
4.1 LATENCY
We compare the latency of our cascading cache to the implementation from Xiao et al. (2023) which uses tensor concatenation to add/evict tokens from the cache. Our implementation utilizes circular buffers and the Triton compiler (Tillet et al., 2019) to create an efficient CUDA kernel for the caching operation. To perform this experiment, we initialize a cache with 64 sink tokens and a total window size of |C| 16K with 4 and cascades, which are equivalent to our Cascading KV Cache and Streaming LLM, respectively. We also initialize the original Streaming LLM that uses concatenation. We then process total of 16K tokens into the cache, and report the cumulative time spent on caching operations. Our method with one cascade (equivalent to Streaming LLM) takes just 0.01% 1/10000 of the total caching time of the original Streaming L.M,, and method

---

Published as a conference paper at ICLR 2025
Table 1: PG19 Perplexity. Across all tested cache sizes, our cascading model maintains lower perplexity than baselines. Flash Attention 2 and Bigbird operate by stepping through the entire sequence with stride equivalent to the total cache size. They perform attention each step until reaching the end of the sequence. The Qwen model is excluded from 65K cache size due to having only 32K positional embeddings.
Methods Perplexity
Total
Num. Books
Token Count
Cache Size
Model
Flash Attn, 2 (strided)
Big Bird (strided)
Streaming LLM
Cascading KV Cache (Ours)
Qwen27p
9.50
(+0.36)
10.65
(+1.51)
9.18
(+0.04)
9.14
16384
91
9.78M
LLaMA3.1a
8.08
(+0.36)
12.76
(+5.04)
7.78
(40.06)
7.72
Qwen21a
9.26
(+0.26)
10.38
(+1.35)
9.05
(+0.02)
9.03
32768
77
9.42M
LLaMA3.1
7.86
(+0.26)
11:33
(43.73)
7.65
(+0.05)
7.60
65536
62
8.25M
LLaMA3.1a lan
7.73
(+0.13)
00M
(-) 7.61
(+0.01)
7.60
Streaming LLM
Cascade (Ours)
PCCTO Book
PG10 64
PG19 Book
6.1
5.50
Cache. Size. (6SK))
6. (DOIS..
6.7
6.0
Puplecty
5.85
Peralecitt
Pepllctty
Cache
5.50
6.5
3.75
1001S
200R
300K
60K
80K
100R
120R
100R
BOIK
3IRK
Step
Step
Step
Figure 7: PG19. For Llama with total cache size of 65K, our cascade model stays equivalent to Streaming LLM until the cache size is exceeded and eviction policy and token selection begin. Our intelligent eviction policy leads to better perplexity for the total stream. Additional figures can be seen in Figures 14 and 15.
with 4 cascades takes just 0.038% 3.8/10000 of the total caching time in Figure 6a. In Figure 6b, we show the overall attention latency, including caching, for single attention layer processing 1M tokens. Our model uses a strided prefill of 4K with a total cache size of 16K. Our method is the only method which processes IM tokens faster than flash attention 2, and takes only 14.8% of the time of quadratic flash attention. other words, flash attention is 6.8 times slower than ours for processing IM tokens. We also study the effect of the size of our strided prefill on overall 1M token latency in Figure 6b, finding that a stride of 4K delivers the lowest latency.
4.2 PG19
We measure perplexity on the PG19 test set (full-length books). Each book is streamed indepen- dently from start to finish without concatenation. We compare against a quadratic flash attention model, well as BigBird and Streaming I.M,, which are also training-free inference adaptations. We use three cache sizes of 16K, 32K, and 65K with a strided prefill of IK. Since our cache is equivalent to Streaming LLM sequence lengths that are less than the total cache size, only run each experiment on the subset of books which exceed the given cache size. Flash Attention 2 and Bigbird would exceed the GPU memory capacity, therefore, they are limited processing books in chunk sizes equivalent to the total cache size. Results are displayed in Table 1. Our method delivers a consistently lower perplexity for all tested cache and model sizes. Additionally, we show examples of how our model behaves during the streaming process in Figure 7. After the cache size exceeded, our eviction policy begins to differ from Streaming LLM, and our model tends show lower perplexity due to the increased total token span in our cascading cache. Additional plots for Llama3.1 on all books exceeding 65K length can be seen in Figures 14 and 15.
4.3 BOOK SUMMARIZATION
We also evaluate our models on the booksum (Kryšciñski et al., 2021) book summarization dataset. For this experiment we compare against both linear and quadratic methods Table 2. We find that among linear methods, our models deliver a 4.48% average performance increase over the best linear baseline rouge score (Lin & Hovy, 2003). We find that quadratic methods generally outperform linear cache, although the performance increases come at a tremendous latency cost for longer input sequences shown in Figure 6b.
7

---

Published as a conference paper at ICLR 2025
Table 2: Booksum book summarization. Among linear baseline models, Cascading KV cache offers
consistent improvement. Averaged all models and metrics, ours performs 4.48% better than linear baselines.
Method
Complexity
Llama 3.1
Qwen 27
Rouge-1
Rouge-2
Rouge-T.
Rouge-1
Rouge-2
Rouge-T.
Vanilla Transformer
(
35.37
7.29
21.24
31,70
5,70
17.8
Snap KV
(
36,80
8.11
21.63
H20
(
35.62
7.42
21.16
31.10
5.47
17.58
BigBird Streaming LLM
O(N)
33.36
6.55
18.59
20.83
2.31
12.62
O(N)
33.04
6.04
19.85
29.14
4.51
16.91
Cascade (Ours)
((N)
34,47
6,63
20.52
30.34
5.02
17.54
093
1:01
103
45
6-3
8
11
11
504)
1:0
58
91
29
100
12
12
1:01
2+
100
43
10:4
300
2
10
10
1:00
00.0
100
1:00
100
100
32%
BSIK
2024
WEAK
1M
32%
HIA
200%
021R
Contred Tangth
Contest Lought
(a) Ours 32K Total Cache Size
(b) Streaming LLM 32K Total Cache Size
1001
-00
57
14
130
0'
103
07
100
110
8-
10
17
46.00
100
00
100
100
100
100
100
112
326
65k
B3TK
2028
321X
1xI
63A
BIX
2621
521R
Ouitedt Legth
Codleat Linglt
(c) Ours 65K Total Cache Size
(d) Streaming LLM 65K Total Cache Size
Figure 8: Passkey Retrieval. For total cache size of 65K, our Cascading KV Cache is able to maintain hetter than random (10%) accuracy after doublings of the context length beyond the cache size.
4.4 PASSKEY RETRIEVAL
For passkey retrieval, we evaluate Streaming LLM and our Cascading KV Cache, by generating random 5 digit passkey which is hidden in a random point in the total sequence length. The rest of the text consists of random English words from the dictionary. We perform 20 trials for 5 insertion location ranges and sequence lengths for a total of 600 retrievals. We calculate accuracy for each digit, counting a correct digit prediction if it falls in the proper place in the output sequence. Therefore, a model which outputs random digits would receive an accuracy of 10%. We evaluate total cache sizes of 32K and 65K and sequence lengths with 8 cascades and strided prefill of 4K. Context lengths start from 32K and double until we reach 1M tokens. Results are shown in Figure 8. For both 32K and 65K cache sizes, Streaming LLM begins to show near random accuracy after the first doubling which exceeds the cache size, while our Cascading KV Cache is still better than random after doublings of the context length.
4.5 LONGBENCH
We evaluate method against other linear scaling models the same subset of tasks (Xiao et al., 2023) in the LongBench long context understanding benchmark (Bai et al., 2023b). We limit the total cache size of each model to be approximately 1/4 of the original prompt length L of each h
input using the function L' = 210og, (L/4)] and use strided prefill of 512. Flash attention models truncate text from the middle of the input to achieve the desired cache length. The results are displayed in Figure 9. Averaged over all datasets and tested models, cascading cache improves performance over the next best model by 12.13%. For tabular results, please see Table 9.
4.6 VISUALIZATION
To visualize the effect of our cache on the attention matrices, we reconstruct the full attention ma- trices of both Streaming LLM and our Cascading KV Cache using Llama3.1 8B on the first 8K tokens of the first book of the PG19 test set. We use total cache size of 2048 and 4 cascades with a strided prefil of 256. The attention matrices are displayed in Figure 10. Naive sliding window attention Figure 10 (a.c) forms short static barrier where tokens are evicted regardless of their im- portance. Our cache Figure 10 (b,d) retains tokens in history for a longer time where have influence over future predictions, effectively increasing the available knowledge.
8

---

Published as a conference paper at ICLR 2025
Streammin LLM
Bird
Fassh Altention (trumaaeed)
Cascade (Ows)
Narrtto qj
Namattee
Nambto Q4
Namtoo GA
1.S.A, Bis U.S.
Ropel
Holt
Rownr
200a SADA
(a) Llama 3.1sB
(b) Qwen 27B
(c) Llama 3.170B
(d) Qwen 272B
Figure 9: LongBench. Our cascade model consistently outperforms linear inference baselines, All models are limited context window which is roughly 1/4 of the total original prompt length. Averaged over all models datasets, our Cascading cache results in an average performance gain of 12.3%. Please see Table for a tabular presentation of results.
Layer 15
Layer 23
Quarle
Quarii-
Mell Proused Key-Valer
Lost Past Infermation
Lot Past Informattion
Presoved Strize Attunton Pattern
Taken
expnneniaal
Streaming LLM
(b) Cascade (Ours)
(c) Streaming LLM
(d) Cascade (Ours)
Figure 10:
Attention matrix reconstruction for Streaming I.M.'s sink cache and our Cascading Cache. Both methods result in ((n) inference time complexity with the same total cache size (IC) = 2048).
We demonstrate the cascade boundaries of our proposed KV eviction policy in Figure 10(b), where the sparsity of each cas- cade gradually increases with the size of the cascade. Addi- tionally, our method preserves the attention patterns more thor- oughly than Streaming LLM, such as the annotated preserved key value in Figure 10(d) which falls well outside of the range of the sliding window pattern. For more attention visualiza- tions, please see Figure 17 in the appendix.
Table 3:
The token selection process outlined in Section 3 is crucial for ere- ating dynamic attention patterns.
LLaMA3.
Cache (iC) = 2048)
PPL.
Streaming LLM Ours w/o token selection
8.03
8.03
Ours w/ token selection
7.88
4.7 ABLATION STUDY
PG19 Book
To study the effect of different parts of our model, we provide three ablation studies including the effect of the strided prefill and token selection using the first book of PG19, and the effect of sparsity induced by the number of cascades. The effect of the strided prefill is shown in Figure 11. We find a decrease in perplexity with an increasing stride size. Intuitively, this comes from the fact that a larger stride provides a larger dense window at the leading edge of the attention matrix as shown in Figure 5. We study the token selection process outlined Section Table and find that without the token selec- tion process, our model matches the performance of Stream- ing I.M., which highlights the importance of selecting higher scoring tokens. Lastly, we study the effect of the number of cascades, and thus overall sparsity, in Figure 12. For this ex- periment,
6.8
128
Stride 512
Stude
Perplexity
Steidee
6.7
6.6
30K
40K
50K
60K
Step
Streaming LLM with strided prefill achieved a progres- sively better perplexity and latency (Figure 6c) when increasing the stride due to a larger region of dense atten- tion.
Figure 11:
total cache size of 4K and consider context lengths from 4K which double until 262K. We average the passkey retrieval accuracy over all in- sertion locations. We find that accuracy steadily increases until the number of cascades exceeds (more than 96% window sparsity calculated by C1/S).

---

Published as a conference paper at ICLR 2025
Streeming LLM
2 Cascades
4 Crsoudes
8 Casoades
16 Cascades
32 Croodds
Expected
100%
1005
80%
80%
0.0
Acourey
Accureyy
Diffecarce
-0.2
67%6
6055
00.4
4096
40%
-0.6
2055
20%
12
13
14
15
16
17
18
16 logg( Length)
14
15
17
12
16 Context Length)
18
CongCCo Length
(a) Actual Accuracy
(b) Expected Accuracy
(c) Actual Expected
The effect of more cascades. a) For fixed cache size, increasing the number of cascades leads more sparsity. We find passkey retrieval accuracy increases until total cascades. b) Expected accuracy using total token span (Equation (4)) as a rough predictor. c) measuring the difference between predicted and actual accuracy (Figure 12a- - Figure 12b), we see that token span remains a strong predictor until the number of cascades exceeds four.
Figure 12:
Interestingly, the token span in the cache remains a good predictor of accuracy for a moderate num- ber of cascades. Given token span, we may roughly calculate the expected accuracy in Figure 12b by considering the probability that the passkey falls within the span of the tokens. For example, with a token span of Š = 1024, and context size of 2048, we would expect an accuracy of approximately 50%. We find the token span be reliable predictor of accuracy until 4 cascades (Figure 12c).
LIMITATIONS & FUTURE WORK
As described above Equation (4) and visualized in Figure 12, the overall sparsity of our model in- creases as the number of cascades N increases. This introduces a trade-off, as demonstrated in Figure 12a, where performance improves up point but decreases once the number of cascades exceeds eight. Therefore, while our method enables substantial context length extrapolation, this process is not unbounded. Eventually, tokens must be discarded to maintain linear inference com- plexity, which inherently limits the scope of extrapolation. A promising direction for future work involves removing the need discard any tokens while preserving sub-quadratic complexity. One potential solution could involve developing methods for logarithmic complexity searches for query- key similarity within the KV cache. By efficiently identifying the top-k relevant key-value pairs, such an approach could eliminate the need for token eviction and allow the model to maintain an overall complexity of (N log N). This would open new avenues for expanding the context mem- ory of transformer models without compromising efficiency.
CONCLUSION
In this paper, we introduced a novel, training-free method for extending the context memory of streaming LLMs, offering significant improvements without increasing computational complexity. Our approach treats the fixed-size KV cache as a series of cascading sub-caches, allowing for dy- namic token retention based on their historical importance. By selectively preserving high-impact tokens and evicting less critical ones, our method effectively extends the context window far beyond the limitations of traditional sliding windows. Our results demonstrate clear performance gains: a 133% average improvement in LongBench, a 4.48% boost in book summarization tasks, and supe- rior passkey retrieval accuracy at IM tokens, maintaining significant edge even after four doublings of the context size. Additionally, our linear prefill strategy eliminates the quadratic complexity of previous approaches, achieving latency reduction by a factor of 6.8 compared to flash attention 2. These advancements highlight the potential of our method to significantly improve the efficiency of LLMs, making it a practical and impactful solution for both research and real-world applications that require long-context processing.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
In order aid in reproducibility of our experiments, we provide our code which is available online?. We also provide exact pretrained model URL's which are listed in Table 5. We provide an algorithm for our strided prefill method Algorithm and a complete algorithm for our Cascading KV Cache in Algorithm 2 and modified flash attention kernnel in Algorithm 3. We have explained the param- eters and computation budgets for all experiments in Section As our method is deterministic and does not require stochastic training or generation process, we have omitted error bars in our results.
ACKNOWLEDGMENTS
This work was supported by Institute for Information & communications Technology Planning & Evaluation(IITP) grant funded by the Korea goVernment(MSIT) (No. RS-2019-1119007,, Artificial Intelligence Graduate School Program(KAISST); (No. 1S-2019-11191906, Artificial Intelligence
(No. RS-2024-00459799,, Development of ML compiler framework for on-device Al): (No. RS-2022-1122071 13, Meta-learning Applicable Real-world Problems): and (No. RS-2022-001172288 Development of Large Korean Language Model Technol- ogy for Efficient Pre-training).
Graduate School
This work was supported by the National Research Foundation of Korea( grant funded by the Korea gOVEM (No. RS-2023-00256655); and (No. RS- RS-2024-003549477.
REFERENCES
Joshua Ainslie, James Lee- Sherp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head check- points. arXiv preprint arXiv:2305. 13245, 2023.
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, al. Qwen technical report. arXiv preprint arXiv:2309. 16669, 2023a.
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu. Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308. 14508, 2023b.
Iz Beltagy, Matthe E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arxiv:2004.00 0500 2020.
Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, al. Pyramidkv: Dynamic kv cache compression based on pyramidal information funneling. arXiv preprint arXiv:2406. 24t.02299000 2024.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreca Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009. 14794, 2020.
Tri Dao. Flashattention--:: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08669, 2023.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.2 178.2 2024.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023.
Huiqiang Jiang, Yucheng Li, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin Ahn, Zhenhua Han, Amir Abdi, Dongsheng Li, Chin-Yer Lin, al. Minference 1.0: Accelerating pre-filling for long-context Iims via dynamic sparse attention. arXiv preprint arXiv:2407.024990 2024. 2024.
Pttpps: ptttps://gii fttf://fffttioocoffffff/fftt htt.:////efwiileeee/eeeaaaaaaaee wwweelleeeeteeeeeeeeeeeeeee kaccccch

---

Published as a conference paper at ICLR 2025
Jang-Hyun Kim, Junyoung Yeom, Sangdoo Yun, and Hyun Oh Song. Compressed context memory for online language model interaction. arXiv preprint arXiv:2312.03414, 2023.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint NXXi:20001.0445./ 2020.
Wojeiech Kryšciński, Nazneen Rajani, Divyansh Agarwal, Caiming Xiong, and Dragomir Radev. Booksum: A collection of datasets for long-form narrative summarization. 2021.
Heejun Lee, Jina Kim, Jeffrey Willette, and Sung Ju Hwang. Sea: Sparse linear attention with estimated attention mask. arXiv preprint arXiv:2310.01777, 2023.
Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Llm knows what you are looking for before generation. arXiv preprint MxXii::24441146666 2024.
Chin-Yes Lin and Eduard Hovy. Automatic evaluation of summaries using n-gram co-occurrence statistics. In Proceedings of the 2003 haman language technology conference of the North Amer- ican chapter of the association for computational linguistics, pp. 150-157, 2003.
Amirkeivan Mohtashami and Martin Jaggi. Landmark attention: Random- access infinite context length for transformers. arXiv preprint arXiv:2305. 2023.
Tsendsuren Munkhdalai, Manaal Faruqui, and Siddharth Gopal. Leave no context behind: Efficient infinite context transformers with infini-attention. arXiv preprint 2404:22404.07143, 2024.
Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, Chloe Hillier, and Timothy Lillicrap. Compressive transformers for long-range sequence modelling. arXiv preprint, 2019. URL
https: htt.///axvvvv/..///e//eeee...ava wwt.ooogg////oooooooooooosesss/s https/991..00011
Philippe Tillet, Hsiang- Tsung Kung, and David Cox. Triton: an intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, pp. 10-19, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- tion processing systems, 30, 2017.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint urXiv:2309. /7453, 2023.
Xinrong Zhang, Yingfa Chen, Shengding Hu, Zihang Xu, Junhao Chen, Moo Hao, Xu Han, Zhen Thai, Shuo Wang. Zhiyuan Liu, et al. Infinite bench: Extending long context evaluation beyond 100k tokens. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 15262-15277. 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 gen- erative inference of large language models. Advances Neural Information Processing Systems, 36, 2024b.
12

---

Published as a conference paper at ICLR 2025
A
APPENDIX
Appendix B Extra experimental settings information
Appendix C- Extra ablation study on head policy and head reduction function.
Algorithm 2
The algorithm of our cascading cache method
Table 5 Paths to exact pretrained models used in our experiments.
Table 4 MMLU experiment
Table 9 LLngBench tabular data (displays the same data as Figure
Figures 14 and 15 Extra PG19 plots for the subset of PG19 which exceeds 65K length.
Figure 16 Quadratic Llama3. passkey results.
Figure 17 Additional attention matrix plots in higher resolution.
B EXPERIMENTAL SETTINGS
For experiments utilizing 8B model sizes, we use one NVIDIA A6000 (49GB) GPU, and for exper- iments utilizing 70B model sizes, we utilize NVIDIA A100 GPUs. Quadratic models which use Flash Attention 2 (Dao, 2023) utilize the official cuda kernel, while our method utilizes modified triton (Tillet et al., 2019) Flash Attention kernel.
C HEAD POLICY AND HEAD REDUCTION.
When making a decision for token selection, we may apply the same homogeneous decision across all heads. Likewise, we may allow the heads behave independently as illustrated in Figure 13a. Additionally, as models may make use of Grouped Query Attention (GQA) (Ainslie et al., 2023), the number of attention heads may differ between queries and keys. Therefore, for both cases of homogeneous and independent heads, we need to select a head reduction function which will reduce head dimension in the attention matrix to (homogeneous heads) or K (key-value heads in GQA). We perform an ablation the PG19 dataset to explore different options of head reduction functions and head policies in Figure 13b. find that in all cases, independent heads outperform homogeneous heads. Among the independent heads, find that mean and max reductions resulted in similar performance, while a median reduction resulted slightly worse performance. We utilize independent heads and max pooling attention scores in experiments.
Diveie
RAC
7.23
7:25
7:2
the toletiiiee
7:70
7.1
Heal Backutter Poatoo (Lkee Kigg)
0
PoleT
9.15
0
0.12
Bed Dolaltttio Rlaiioe Kios Jurt
(a) Head Policy Illustration
(b) Llama 3.1 Perplexity (L)
Figure 13: Head Reduction Function and Head Policy Ablation
13

---

Published as a conference paper at ICLR 2025
Model
Huggingface Path
Experiment
LLaMA3, ls (Dubey et al,, 2024)
PG19
LLaMA3. lan Instruct (Duhey al., 2024)
Ilama/Meta Llama 3-88- 388-nntt
Bonokuum.Longencch.oo Ablatti,,n,,,iiinn,.. Paaskey
LLaMA3. Iam Instruct (Dubey al., 2024)
meta-llama//Mtta- Maaaaa----aa---0------- Instruutt
Lengbench
Qwen22g (Bai al., 2023a)
Qwen/Qwen2-77 7B
Qwen2m Instruct (Bai al., 2023a)
Qwen/Qwen2-77 Bren/Qwen2-77-IInstuue
Booksum,Longhenn
Qwen2 Instruct (Bai ul., 2023a)
Qwen/Qwen2-775 (er-Qwee22----BBme Instruct
LongBench
Table 5: Huggingface model paths used in our experiments.
Table 4: MMLU. We find that our Cascading KV Cache outperforms all lincar models overall.
Model
Method
Complexity
Humanities
Soc. Science
Other
STEM
Overall
Flash Atlention 2(Full Contexi) Vanilla (Truncated)
O(N
61.59
76.47
73.09
56.01
67.00
O(N)
61.23
76.08
73.06
55.79
66.80
Ilama 3.1
Streaming LLM
((N)
61.57
76.37
73.19
55.92
66.98
Cascade (Ours)
O(N)
61.45
76.63
73.25
56.23
67.11
Flash Attention (Full Context)
(
63.12
80.40
74.64
64.07
70.99
Vanilla (Truncated)
O(N)
62.61
80.21
74.64
64.12
70.81
Qwen 27
Streaming LLM
O(N)
63.04
80.47
74.61
63.84
70.86
Cascade (Ours)
O(N)
62.93
80.40
74.57
63.88
70.87
Algorithm Cascading Sink Cache Algorithm (repeat for keys and values)
Require:
cascade cache. buf array, sink cache_buf, item to cache if not sincee bwffer.is_ffllll.l then
sink_cache_but buffer J itte_to_cacee return
end for cache buf in cascade cache buf array do cache_ buf. is lussscccpptnn_toot tokens(()))))))) then if not cache_ bache_buf.is isf. full() then cache_ buf item_to tocccche return
add item to cache which is not full
else
b evict an item from the cache and continue
cache buf ( item cache iteh_to_cache +- nache_buf.eevietoolee end if'
> reset variable for next iteration
else
if not cache buf full then cache buf U item cacce
eager add to unfilled cache to avoid naively evicting
return
else
token selection (newest in cache vs. incoming token)
newest_item +-
newest_score wwwche.b...ee.scorreeocoooooooee
item_score f cache_ f got_scorr(iemmttoocaa
if item score newest score then
cache. cache.buf.evic. buf.eviict.ewwstt))
cache_ buf U item_to stoomtt___o tocccccceeeeeee
end if return end if end if
update positional encoding indices() end for
14

---

Published as a conference paper at ICLR 2025
Corbe Sic AOXZ
PC
9.20
Coday Sae (6K)
Buck?
P.....a...
Carbu Sien CONNe?
FGH
6,500
Phophatt
15
8:40
1L.5
7:66
50%
XI
7BK
63K
100
V0A
00K
Step
Shop
Stop
PC Boek 4
PCD5 Book
PC31 Bock
2015 Buck
8.80
0.50
Carbe Sian (888)
Carbe Stee. (BS))
Carbe Site (K0K)
Pay Taykk
8.30
0.0
8.16
7.0
70th
3tp
Step
PCIe B.dd
PC Bock
PC1P Baak
2016 Book
Kaddt Non 103AS
Cacta Size (UK
Cirbee LOCk
Pepahaat
Pappialty
Propisaty
Cacle
8.60
8:70
19310 mlase
PNJ Panie
27216 Tavd 70
FE1 Thoa
Cledee Silee (698)
Codble Sire. (0GK).
N
8.8
(9220 Blecct 2il
(1020 Beck
6.54
Carle Size (BX))
So Ster. (01))
5.80
Siln (unk))
M
Poplinaly
Paydusily
diche Sico.
Haplestoo
Parlesity
So
S.
7:70
0.50
7.65
0.39
Stage
Stap
7011
5,00
Clehu Site (6635)
(
10.6
Rerphody
10.4
10:00
0.2
10.0
Stop
7.00
9.10
(8905
9.00
Papkenkk
5.55
6.68
04%
125k
1000
Step
Step
Streaming L.M
Cascade (Ouns)
Figure 14: Additional plots for all of the books in the subset of PG19 books which exceeds 65K in length. The model used is Llama 3.1 8B. This chart is a complement to Figure 7
15

---

Published as a conference paper at ICLR 2025
2016 Budd
2010
7.000
5.10
Wart LOSN). N...
Codbe Sec. RON)
Carda Sho (033]
6.75
Spdbe Sel JRSK
6.070
Papposte 1
Paopholt
Pappoale
550
6.020
6.60
B0X
620%
66k
MXX
10X
550
10h
1000
199K
3000
Stop
Stop
VCat Book
1.4
PCD Bodk
PCRS Baok
2015 Dook
CCabee sike (053)
Corbe Site. (D0K)
Codbe. Sttee 0600
Stat 1606
0.4
10
6.50
92
6,70
1001
2007
10.05
1000
0.5%
7Mh
3hpp
PCIe Bod.
P0.0
7.2
PGH Bod d0
PO.1 Buck
6.5
C2 Stee (65K)
10.6
Cadue Si 1803)
Cadaa Sox (8535)
Catlee Stoc. (GAA)
Proplaaly
Proploaty
10.0
Papilaat
0.0
300p
PN229 Flvec
"YD10 Badl 73
7V210 Boel
"THE Bock 26
10.24
5.400
Siee (053)
Clect uec USK)
6.515
Paoploals
10:22
5,50%
3M
Shrpp
11218 Book
(9228 Blecc AS
19.20 Blvil
Marion Size (651))
6.75
Siri Stor-ait
Paylesily
16.50
6. 6.677m
Carte
6 5tr
6.522
PS7
Bad
0.7
9.75
Coclee Size (6XXL
Aeplooy
Pergioulyy
M
8:00
0.4
10.5
3lup
Step
Step
0.710
Carie Siew (0530 (05
Cerdle Sieeet (OSK).
6.710
Paykesk
Papkenkk
Re
8.s
a1x
301
3006
Shop
3top
Streaming LLM
Cascade (Ouns)
Figure 15: Additional plots for all of the books in the subset of PG19 books which exceeds 65K in length. The model used is Llama 3.1 8B. This chart is a complement to Figure 7
16

---

Published as a conference paper at ICLR 2025
Algorithm Token Selection EMA Accumulation (in the context of Flash Attention kemnel)
Require:
score_cache, queries, keys, m, EMA beta
for i in chunk(queries) do
Load Q; from HBM to on-chip SRAM from queries for in chunk(keys) do
Load K,. V, from HBM to on-chip SRAM from keys
On Chip, Compute Sij = Q,K7
On Chip, update m. (update rolling
la flash attention 2)
On Chip, update I (update normalization constant la flash attention 2)
On Chip, Compute Sig (max-adjusted exponential before softmax normalization)
On Chip, update O; (update output vector flash attention
On Chip, calculate EMA coeff. CEMA for Qi.
CEmA = 8 3)vk E [len(queries) (q chunk indices 1)] On Chip, calculate inner loop steps completed and remaining
Write, Atomic Sum to acche suLgsum(( + 4 4)) CEMA)
end for end for
0-70
100
OOM
OOM
OOM
0OM
20-10
100
100
OOM
OOM
OOM
OOM
Ioaer Loc
40-G0
100
100
OOM
OOM
OOM
OOM
100
100
OOM
OOM
OOM
OOM
100
100
OOM
OOM
OOM
OOM
32K
65K
131K
262K
524K
1M
Context
Length
Figure 16: Passkey results for vanilla Llama3.1 as measured on an NVIDIA A6000 GPU with 49GM memory and cache size of 65K. According to the llama whitepaper (Dubey et al., 2024), was finetuned for 131K positional embeddings until it achieved 100% accuracy on a passkey retrieval task. Therefore, given big enough cache, achieves perfect accuracy up the cache size (or 131K). Our model however, can extend high accuracy numbers well beyond the cache size (see Figure 8).
Model
16K
32K
65K
131K
262K
524K
IM
Minference
5.11
12.84
28.41
60.47
OOM
OOM
OOM 665.33
Cascading KV Cache
9.58
19.71
40.11
80.84
164.47
334.17
Table 6: Latency (S) as compared to Minference for 1M tokens. This table shows latency throughout all layers, which differs from that shown Figure 6b which shows attention latency for single layer. Minference goes OOM after 131K on 49GB GPU due to requiring all tokens cache for the forward pass. Our model uses cache size of 16K with stride of 4K. which are the same settings used in Figure 6b.
17

---

Published as a conference paper at ICLR 2025
C.I ADDITIONAL LONGBENCH//NIINTTEERRE BASELINES
In Table 9, we show tabular results for the data displayed in Figure 9. We also add three additional models (MInfer- ence (Jiang et al., 2024), PyramidKV (Cai et al., 2024) and Cascade + MInference). The settings between these extra methods contrasts with our setting in various ways (Ta- ble 7), as Minference supports sparse prefill with dense decode and PyramidKV supports dense prefill with a sparse decode. As our method the only one which sup- ports both sparse prefill and decode, we truncate the mid- dle the prompt for MInference and PyramidKV V in the same way we do for flash attention in Fig- ure 9.
Table 7: Prefill and decoding sparsity for additional models.
Method
Sparse Prefill
Spurse Decude
MInference PyramidVV
Cascade (OURS)
In addition to this, we have also provded an example of our cache integrated with the official MInfer- ence kernel. This allows for using our our linear strided prefill and cascading cache in conjunction with MInference. The key difference in Minference+Cascate is that the leading chunk (stride) of the attention matrix uses MInference instead of dense attention. As MInference very sparse, this allows for greatly increasing the size of the stride without adding much computation overhead while computing each row of the attention matrix. For this experiment Minference+Cascade used stride of 100K.
Infinite bench (Zhang al., 2024a). results can be seen in Table using the same truncation strategy for MInference as outlined above.
C.2 ADDITIONAL. LATENCY EXPERIMENT
In Table 8, we evaluate two additional models (MInference and MInference + Cascade) in terms of latency for single self attention layer. MInference shows tendency to scale luper-linearly, each doubling of the context results in a more than doubling of the latency. Because of this, MInference cascade begins outperform the latency of plain MInference after sequence lengths of 131K. This decrease in latency is due to the fact that MInference + Cascade uses MInference as the leading chunk in the attention matrix (with 100K stride) which bounds the total size of the attention matrix of single attention head at each step to be E R 100K x (100K+[CC) where |C| is the total cache size.
Table 8: Additional 1M token latency (S) results. While our cascade model with stride of 4096 maintains the best overall latency, MInference cascade also shows linear scaling in addition to added performance benefits shown in Table 9. MInference + cascade begins to outperform plain MInference terms latency on sequences over 131K in length. For further discussion these results, please see Appendix C.2.
Model
16K
32K
65K
131K
262K
524K
1M
MInference
0.26
0.28
0.78
2.26
6.39
16.84
0OM
MInference + Cascade
0.34
0.68
1.3
3.04
5.77
11.88
24.13
Cascade
0.22
0.46
0.94
1.93
3.81
7.66
15.34
18

---

Published as a conference paper at ICLR 2025
Table 9: Tabular display LongBench radar plot results from Figure Higher scores are better (f). Total cache sizes are based on the length of the original prompt L. For Llama 3.1 8B Instruct we added three additional models (MInference, PyramidKV V and Cascade + MInference). For more details regarding these models, please refer to Appendix C.I.
Repur
Susaming LLM Flahh Alaman 2 (ranesse))
22.57
40.75
23.00
20.69
23.45
16.82
26.37
LL Instrct
Big
21
18.07
36.59
11.33
15.77
22:33
17:24
19.62
20.13
20.46
26.15
21:39
25:18
Ulinn
Panunid
Cacaal (Oung
36.43
47.26
33.12
23,33
32,33
28.32
31.8
Cascade Ouns Mixference (llnng et 2004)
20.54
55.22
36.51
25.34
05.85
25.2
36.96
Qwen2
Fiehh Alorran (rancted)
Big Brd
15:01
17.78
28.08
20.15
1566
12.9
25.35
90.31
17.49
18.64
21.67
30.57
Cascade Oues)
20.55
37.30
28.66
19.57
34.35
36.22
27.78
Sneeming LLM
25.23
42.59
36.5
3005
$1.76
32.67
24.85
LLaMA3.Ipe
Alrmaam (rancate))
Sneaming ITM
30.8
50.06
70.08
17:97
43.85
22.85
20
Qwen2aza
Flah Amtrrn (manvated)
28.5
Table 10: InfiniteBench (Zhang al., 2024a) results.
Total Cache Size
Model
Cache
ea.MC
en.QA
en.Sum
Mean
Streaming LLM
46.72
13.98
30.8
30.5
LLaMA3.1s Instruct
Minference (truncated)
46.72
32.25
Cascade (Ours)
56.77
17.69
31,50
35.32
198
00
50
09
(a) Layer
(b) Layer 11
(c) Layer 14
006
204
60
.012
8.01
130
600
.0.0
6.01
130
900
20.2
6:01
400
(d) Layer
(c) Layer 11
(f) Layer 14
Figure 17: Attention matrix reconstructions for Streaming LLM Figures 17a to 17c and our Cascad- ing KV Cache Figures 17d to 17f on first 8K tokens of the first book of (PG19).
19

---

Published as a conference paper at ICLR 2025
Streaming LLM (single token per step)
Cascading Cache (4 tokens per step)
24 Steps
6 Steps
Illustration contrasting the prefill strategy of Streaming LLM vs our Cascading KV Cache. The original Streaming LLM does complete forward pass for every row of the attention matrix which causes the poor latency of Streaming LLM in Figure 6b. Our method, however, can process chunk of tokens during each forward pass of the prefill leading to reduction in the number of forward passes necessary process the entire prompt.
Figure 18:
20


Reviews:
[{"review_id": "ViIHMA7Nbl", "reviewer": "Reviewer_hjX9", "summary": "The paper proposes an extension to attention sink by (1) blockwise prefilling to optimize the latency of this period, (2) cascading caching management. The resulting framework shows quality and latency improvement over StreamingLLM.", "questions": "1. Related to weakness 1, is this method compatible with continuous batching? How well does the method perform compared to, or compatible with actual serving systems, e.g., vllm/sglang? \n2. Could you benchmark the latency and quality wrt to Minference? \n3. For FlashAttention, which version are you comparing to? FlashAttention-1, FlashAttention-2, or FlashAttention-3? Triton or cuda kernel?\n4. What would be the memory overhead, and IO overhead for computing, storing and access the EMA for each token(and manipulate the resulting memory layout change)? Also, can this operation be fused into online softmax? It would be good to add a pseudo code section to illustrate how this part is done, e.g., based on FlashAttention logic.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Prefilling observation is sound. It's good to bulk processing this stage, which StreamingLLM and H2O failed to do.\n2. It's intuitionally beneficial to keep the middle context in addition to sliding window and attention sink, which the paper proves by passkey performance.", "weaknesses": "1. It's pretty tricky to manage memory in this cascading way. I would say it's challenging to manage small amount of memory, e.g., two bytes, at arbitrary locations. It's very likely to cause memory fragmentation and hurt the throughput as a result, which a practical serving system should avoid.\n2. There are a few earlier and more comprehensive works (compared to StreamingLLM) that tackles the prefilling stage with sparsity, e.g., MInference[1], it would be compare against [1].\n[1] MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention", "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": "MfjbEsvWnj", "reviewer": "Reviewer_2xPR", "summary": "The transformer’s context window is crucial for tasks like few-shot learning, but longer contexts increase computational costs, limiting large language models (LLMs) in long-sequence tasks. Recent key-value caching methods lower complexity but often discard tokens too soon and have inefficient prefill stages, leading to high latency. To solve this, the author propose a cascading sub-cache buffer system that selectively retains relevant tokens, supporting longer context without added cache size. This method improves accuracy and reduces latency across tasks, enhancing LLM efficiency for real-time applications in resource-limited environments.", "questions": "- How's your peformance compared with Minference?\n- How's your performance compared with others on RULER task, which is a benchmark for evaluating context size", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The idea of cascade kv cache is simple and effective\n- The design of this method carefully considered the implementation so as to get the actual speedup", "weaknesses": "The baseline may not be sufficient, most of the experiment are comparing with streamingLLM", "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": "swt74jN17N", "reviewer": "Reviewer_Ckne", "summary": "The paper presents a new training-free approach which significantly extend the effective context length of LLM. The authors first introduce a strided prefill which reduces the prompt computing latency on 1M tokens by a factor of 6.8 compared to flash attention. Then illustrate their cascade KV cache maintaining mechanism. Given the same KV cache size, the cascade mechanism gains impressive improvements compared with the existing methods.", "questions": "I am wondering the perplexity results on more evaluation datasets.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Although the idea is simple, the experiment results are very good.\n2. The idea is well implemented with careful code optimization.", "weaknesses": "The experimental section would be better if the idea is evaluated on more data sets.", "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": "00R8DcMyMS", "reviewer": "Reviewer_4zw7", "summary": "In order to enable LLMs to preserve a long context without increasing the KV cache size, this paper proposes a training-free KV cache eviction policy with a cascading sub-cache algorithm. The algorithm allows one sub-cache window to accept a subset of tokens evicted from the previous sub-cache. This paper also introduces a linear prefill strategy that avoids the restrictive quadratic prompt complexity during the prefill stage by processing fixed-sized chunks (strides) of the prompt.", "questions": "Please refer to the weakness part for questions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The experiments and conclusions are sufficient, including the evaluation of latency and accuracy on different tasks and LLMs. Also, the display of the experimental figures are clear.\n2. This work builds a new paradigm of KV cache with cascading sub-cache and effectively extends the context length without increasing complexity or requiring additional training. This work provides a promising solution for efficient edge-side LLM inference.", "weaknesses": "1. I understand the proposed method is a generalization (more flexible version) of sliding window attention, but the main problem is that this paper does not clearly explain why the proposed cascading sub-cache is effective for KV cache eviction (intuitively). It is better to explain more about the background of cascading structure and the key motivations/observations/insights for introducing cascading KV cache.\n2. Although experiments are sufficient, the baselines are kind of weak. For example, when evaluating on LongBench, there are more recent dynamic KV cache method such as PyramidKV [1], PyramidInfer[2], InfLLM [3], Quest [4], and FastGen [5]. It will be better to compare with one/two more recent dynamic KV cache method to further support your conclusions.\n3. In Section 3.1, it is not clear that why use trunks can achieve linear attention complexity during the prefill stage, and what is the key difference between the proposed method and FlashAttention which also uses tiling to save the memory.\n4. From Section 3.2, each sub-cache relies on the previous sub-cache. The sequential procedure seems to have an impact on the inference efficiency. How to avoid this problem and achieve much higer efficiency compared with StreamingLLM.\n5. Token selection algorithm leverages exponential moving average (EMA) to track the historical attention score. This method seems similar to directly using accumulated attention score proposed by H2O. Can I understand this process as considering the different importance degrees of current and historical attention score based on the method of H2O, which is controlled by the hyper-parameter gamma.\n\nRelated references:\n[1] PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling (arXiv 2024)\n[2] PyramidInfer: Pyramid KV Cache Compression for High-throughput LLM Inference (ACL 2024)\n[3] InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memory (arXiv 2024)\n[4] Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference (ICML 2024)\n[5] Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs (ICLR 2024)", "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)