ParallelComp: Parallel Long-Context Compressor for Length Extrapolation
Authors: Jing Xiong
Jianghan Shen
Chuanyang Zheng
Zhongwei Wan
Chenyang Zhao
Chiwun Yang
Fanghua Ye
Hongxia Yang
Lingpeng Kong
Ngai Wong
Venue: ICML 2025 poster (2025)
Keywords: Large Language Models
Parallel Attention
KV Cache Eviction
Attention Calibration
Attention Sink
Primary area: deep_learning->attention_mechanisms

Abstract: Extrapolating ultra-long contexts (text length >128K) remains a major challenge for large language models (LLMs), as most training-free extrapolation methods are not only severely limited by memory bottlenecks, but also suffer from the attention sink, which restricts their scalability and effectiveness in practice. In this work, we propose ParallelComp, a parallel long-context compression method that effectively overcomes the memory bottleneck, enabling 8B-parameter LLMs to extrapolate from 8K to 128K tokens on a single A100 80GB GPU in a training-free setting. ParallelComp splits the input into chunks, dynamically evicting redundant chunks and irrelevant tokens, supported by a parallel KV cache eviction mechanism. Importantly, we present a systematic theoretical and empirical analysis of attention biases in parallel attention—including the attention sink, recency bias, and middle bias—and reveal that these biases exhibit distinctive patterns under ultra-long context settings. We further design a KV cache eviction technique to mitigate this phenomenon. Experimental results show that ParallelComp enables an 8B model (trained on 8K context) to achieve 91.17% of GPT-4's performance under ultra-long contexts, outperforming closed-source models such as Claude-2 and Kimi-Chat. We achieve a 1.76x improvement in chunk throughput, thereby achieving a 23.50x acceleration in the prefill stage with negligible performance loss and pave the way for scalable and robust ultra-long contexts extrapolation in LLMs. We release the code at https://github.com/menik1126/ParallelComp.

ParallelComp:
Parallel Cong-Context Compressor for Length Extrapolation
Jing Xiong"
Jianghan Shen Chuanyang Zheng?
Zhongwei Wan Chenyang Zhao Chiwun Yang Ngai Wong'
Fanghua Ye' Hongxia Yang*
Lingpeng Kong'
Abstract
Extrapolating ultra-long contexts (text length 128K) remains major challenge for large lan- guage models (LLMs), as most training-free ex- trapolation methods are not only severely limited by memory bottlenecks, but also suffer from the attention sink, which restricts their scalability and effectiveness in practice. In this work, we pro- pose PARM parallel long-context compression method that effectivvly overcomes the memory bottleneck, enabling 8B 1B-parameter LLMs to extrapolate from 8K to 128K tokens on a single A 100 80GB GPU training-free setting. PARALLELCOME splits the input into chunks, dynamically evicting redundant chunks and irrelevant tokens, supported by parallel KV cache eviction mechanism. Importantly, we present a systematic theoretical and empiri- cal analysis of attention biases in parallel atten- tion-including the attention sink, recency bias, and middle bias-and reveal that these biases ex- hibit distinctive patterns under ultra-long context settings. We further design KV cache eviction technique to mitigate this phenomenon. Exper- imental results show that PARALLELCOMP en- ables an 8B model (trained on 8K context) to achieve 91.17% of GPT-4's performance under ultra-long contexts, outperforming closed-source models such as Claude-2 and Kimi-Chat. We achieve 1.76x improvement in chunk through- put, thereby achieving 23.50x acceleration in the prefill stage with negligible performance loss and pave the way for scalable and robust ultra-long contexts extrapolation in LLMs. We release the code at httpp::://gttttaa menik kelkk11666556 Parra 1ell
1.3
Atroite 2000
Token ID
Toaen ID
(a) Normal Attention Distribution
(b) Parallel Attention Distribution
04
0.
02
02
(c) Nornal Atlention
(d) Parallel Atlention
Figure 1: Upper:
Distribution of two types of attention. Lower: Heatmaps of the two types of attention. The at- tention head shown here represents the distribution change between normal attention and parallel attention for the s head in layer 1, using the Llama-2 2-7b-chat-h model.
1. Introduction
Extrapolating long-contexts is core capability of large lan- guage models (LLMs) (Achiam al. 2023) Touvron et al.) 2023 Dubey et al.) (024). Achieving this requires effective mechanisms for modeling positional relationships over ex- tended sequences. Rotary position embedding (RoPE) (Su 2023) are commonly employed LLMs due to their ability to efficiently encode relative positional information. How- ever, extrapolating lengths beyond the training range dur- ing inference remains significant challenge. While retrain- ing or fine-tuning the entire model is one possible solution, it is not always feasible, particularly in resource- conouurce-cottrrineed environments (Press et al. 2022 Chi et al. 2022 Peng et al., 2023 Fu et al. 2024). This limitation prevents RoPE-based
com/
models from generalizing to longer sequences without ad- ditional training, making them less adaptable to scenarios requiring inference inputs of unforeseen lengths.
Equual contribution 'The University of Hong Kong, "Nanjing University, "The Chinese University of Hong Kong, "The Ohio State University, 'The University of California, Los Angeles, "Sun Yat-Sen University, 'Tencent, "Hong Kong Polytechnic University. Correspondence to: Jing Xiong < junexiong connect.hku.hik.
To address this, many researchers explore training-fres ap- proaches for context length extrapolation. One prominent direction involves incorporating -TK-based methods (Lo calLLaMA] 2023b a bloc97 2023), which distinguish di- mensions of different frequencies by their wavelengths and
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

ParallelComp: Parallel Long-Context Compressor for Length Extrapolation
apply tailored interpolation strategies address the extrap-
LLMs scaling from 8K to up 128K tokens a single A A100 80GB GPU by addressing attention bi- ases through an effective attention calibration strategy.
olation challenge of position encoding. Another promising
strategy leverages text chunking techniques (An et al.) 2024
Xiao et al. [224] Rainer et al., [2022] Zhuu et al. 2024),
which typically reuse position encodings across chunks to enable chunk-wise length extrapolation without retraining, thereby improving the model's ability to generalize to longer contexts. However, both approaches suffer from the atten- tion sink phenomenon (Liu et al.. 2024 Xiao et al.] 2023 Han et al. 2024] Gu et al.) 2024), where high attention scores tend to be assigned to the first few tokens or the last few tokens in the input sequence. Figure | iillustrate this phenomenon and compares the attention distributions between standard and parallel attention mechanisms. In the upper part of Figure I we observe the distribution of attention scores across tokens. In the standard attention distribution (left), corresponding to the heatmaps (c) below the image, attention is disproportionately focused on the first and last few tokens. In contrast, the parallel attention distribution (right), shown in the heatmaps (d) below the im- age, attempts to distribute attention more evenly. However, it still shows noticeable concentrations in certain regions and exhibits multi-peak distribution, indicating that the nature of the attention sink differs fundamentally between the two mechanisms. The phenomenon within the length ex- trapolation mechanism in the parallel attention mechanism remains unexplored. This paper focuses on addressing the memory limitations encountered during length extrapolation and provides a detailed analysis of the unique attention sink that emerges in parallel attention. Specifically, we extrapo- late the length by chunking the input and reusing position encodings, applying parallel compression of the KV cache of the chunks and tokens to resolve memory bounds, and exploring the unique phenomenon of the attention sink in parallel attention while attempting to adopt a token eviction strategy to mitigate this bias. To promote the understanding of the effects of special attention sink on parallel attention, we propose the following questions in this paper: Q1: What types of attention patterns can be summarized? Q2: Is there any difference between the atlention bias in parallel alten- tion and the attention bias in classical attention? Q3: Can the calibration strategy alleviate attention bias? Q4: Does our parallel compression strategy effectively support length extrapolation?
To overcome limitations in parallel attention, we in- troduce a chunk eviction mechanism and parallel KV cache eviction, allowing processing of contexts be- yond 128K tokens and achieving a 1.76x throughput improvement and 23.50x speedup in the prefilling stage, with negligible performance loss.
Experiments demonstrate that PARALLELCOMP achieves 91.17% of GPT-4's performance on ultra- long context tasks using an SB model trained on only 8K-length context, outperforming strong proprietary models such Claude-2 and Kimi-Chat.
2. Related Work
Position encoding. Existing absolute position encoding (APE) (Vaswani] 2017; Devlin] (018)) incorporates either fixed or learnable position encodings into input represen- tations through vector addition. However, APE faces chal- lenges when dealing with long-contexts. To overcome these limitations, relative position encoding (RPE) meth- ods- as rotary and additive position encodings (Su 2023 Su et al. 2024 Press et al., 202T) are developed to offer improved generalization in longer contexts. In addition, some data-dependent position encoding meth- ods (Golovneva et al. 2024 Zheng al., (024) are gaining widespread attention. These position encodings are gener- ated based on the input data.
Some works (Press et al., 2022 Chi et al. 2022 Li et al.; 2023a) also focus on designing better position encodings to enhance the pre-trained model's capability for length extrapolation. Another line of works (Peng et al., 2023] bloc97| 2023; Chen et al., 2023a) focus enhancing the L.M's length extrapolation capability by fine-tuning.
Furthermore, there are two categories of training-free extrap- olation methods. The first category. such as Local LaMA (202b)): Chen et al. (202bb); LocalLLaMA] (023a): Chen et al.] (0224) directly modifies position encodings to en- able extrapolation or interpolation, aiming to enhance the model's length extrapolation capability. The second cate- gory (An et al. 2024 Xiao et al., 2024 Ratner et 2022] Zhu et al. 2024) achieves extrapolation solely by reusing position encodings. In this work, we focus primarily on the training-free free setting.
To address the above questions, we propose PARALLEL-
COMP, parallel long-context compression method to ex- trapolate length. While maintaining high throughput, we extrapolate the length from 8K to 128K on a single GPU, with almost no performance loss. Overall, our contributions are as follows:
Attention sink. A series of studies (Gu et al. 2024 Xiao ct al. 2023 Liu et al.] (022)) reveal the phenomenon of attention sink, where certain tokens in the sequence (re- ferred to as sink tokens) consistently receive abnormally high attention scores.
We propose PARALLELCOMP, a novel training- free method that enables efficient length extrapolation for
2

---

a high-level overview of ParallclComp: Parallel Long-Contess Compressor for Length Extrapolation
teep 1: Parallel A Attention
Stap 2: Parallel KV Cache E Eviction
Step 3: Global Attention
Query
Dvit Dus Iahon 8. DochormulToar &
X lvies Churk Sef4rbrriiin
Dunnk
Cheen'
Phene
sreee
Lingh
Salarformtto
Chank
Caraa
Bonkk
oue
Chabk
Figure 2: Overview of PARALLEI.COME Parallel Attention -hhe input sequence is split into multiple chunks based the model's maximum context length. Each chunk undergoes local attention computation independently, and the self-informatic score of the query is calculated. Parallel KV Cache Eviction Based on the self-information score, low-score tokens (marked in yellow, H(t)) and attention bias tokens (marked in red, Rtt,) are selectively evicted to optimize memory usage and attention bias. Global Attention The remaining KV caches are ranked by self-information, and less relevant chunks are discarded. The selected chunks are then concatenated, and a global attention operation applied to ensure comprehensive information aggregation before the final autoregressive decoding stage.
When the sequence length increases, the attention scores in the middle of the sequence are significantly lower com- pared to the beginning and the end. Some work (Xiao et al. 2023 Zhang et al., 2023; Wan et al., 2024; Xiong et al. 2024) find that the tokens of attention sink can effectively aggregate information and use it to efficiently compress the KV cache. But in ultra-long contexts, this may prevent the model from focusing the correct parts of long sequences. Xiao et al. (202)) attributes this phenomenon to the soft- max function, which forces the query to assign attention scores to all preceding tokens, even when the preceding tokens lack essential information, resulting in high scores being assigned to initial tokens. Gu al. (2024) proposes simple solution by replacing the softmax attention with al- ternative attention mechanisms (e.g., unnormalized sigmoid attention) to alleviate this dependency. Chen et al.] (2024) alleviates this phenomenon by simply removing certain low- frequency components from RoPE. Yu et al. (2024) deals with this issue by calibrating the attention distribution. In our work, we focus primarily on three phenomena of atten- tion bias within parallel attention: the attention sink at the beginning of the input, the attention sink at the end of the input (i.e. recency bias Peysakhovich & Lerer 2023), and the scattered attention in the middle of the input (Yu et al. 2024). These biases provide insights into how LLMs utilize parallel contextual information.
bias phenomenon. Figure Ooffers PARALLELCOMP.
3.1. ParallelComp
Parallel attention. Inspired by previous studies (An et al., 2024), we divide the text into chunks based on the model's maximum context size and concatenate them with the in- put query for parallel encoding. This step is typically car- ried out using local attention. For a given input sequence X E Nxd, the sequence is split into C [N/w]] chunks, each containing at most tokens (the maximum context length per chunk). Let fQ(-). Jx(-). and fv(-) denote the linear transformation functions for the query, key, and value projections, respectively. Attention computation is then performed within each chunk:
Af = =Sotmaax (Jo(X9) Sx((X)
(e(X)))x(XX)))
(1)
vd
where X E Rexd represents the e-th chunk of the input sequence and A& E Rex is the corresponding attention matrix. The feature update is performed for each chunk:
= AC Jv("),
where F E R is the updated feature for the c-th chunk.
Below, we discuss how to design chunk eviction strategies and parallel KV cache eviction strategies to maintain high throughput while minimizing redundant computations.
3. Method
In this section, we introduce PARALLEI.COMP, our pro- posed approach for achieving efficient long-context com- pression during extrapolation. We then discuss its unique
Chunk eviction. To ensure that the computation of par- allel attention can be performed on single 80GB A100
3

---

ParallelComp: Parallel Long-Context Compressor for Length Extrapolation
GPU, we design a chunk eviction strategy to control mem- ory overhead as shown in Figure step 3. Inspired by Li et al. (2023b); Jiang et al. 2023), we introduce chunk eviction mechanism that leverages the self-information of the query tokens X to further enhance parallel process- ing efficiency. This mechanism employs an online priority queue to manage memory, retaining only the most relevant chunks with the lowest perplexity, thereby improving lan- guage modeling. For a given chunk e, the self- ceff-information score for the query tokens X is calculated as follows:
each token in the chunk to the query X9, Tokens with low cumulative attention scores within the chunk are evicted, and the retained tokens are used to form the compressed KV cache:
(7) where K and V represent the KV cache of the h-th head of the input chunk, and R2, denotes the set of indices cor- responding to the evicted tokens in the /-th head with low attention scores. The notation [-] indicates indexing into K and V to evict only the tokens corresponding to the indices in R2 K and V denote the retained KV cache. The com- pression strategy of the KV cache typically helps reduce memory overhead while increasing chunk throughput, but it often exacerbates attention bias. Next, we introduce a sim- ple and effective strategy to calibrate attention distribution.
K = = k2]
= -
L = log P(X X"),
(3)
where X represents the context of chunk and X cor- responds to the chunk of the query. Chunks with lower self-information scores are considered more relevant and are retained. The set of indices e corresponding to the se- lected chunks is denoted by:
Attention calibration. To mitigate the attention bias ex- acerbated by parallel KV cache eviction, we propose an alternative token eviction strategy based on Eq. [ Specifi- cally, we evict tokens with excessively high attention scores. Let R1 represent the tokens with attention scores of h-th head exceeding a manually-set threshold X. Thus, we have:
s= c
(4)
where is a threshold that determines whether a chunk will be selected or not. The selected chunks are sorted based on T,, and only a fixed number of top-ranked chunks are retained. These selected chunks are stored in a fixed-size priority queue to ensure that the prefilling stage remains within the memory limit.
k = Kb (R))) V = [
(8)
Evicting tokens with exceptionally high scores guarantees that the attention mechnism can produce calibrated attention distributions. We will thoroughly investigate the impact of this calibration method on the attention bias in Section
Parallel KV cache eviction. To further improve chunk throughput, we propose KV cache eviction strategy, We leverage Flash Atten- tion (Dao 2023) for efficient attention computation. Prior to performing local attention, we use the cumulative scores of X to quickly identify tokens with relatively low attention importance and evict them. Specifically, the local attention score Af between the i-th token of the query X² and the j-th token of the chunk Xy is calculated as:
illustrated in Step 2 of Figure 2
Global attention. After obtaining the attention outputs for each chunk, we concatenate the KV caches from all chunks into unified representation. Specifically, the concatenated KV cache is given by:
K = [K x1
K x2
x
.K*',
(9)
V - [vxt vxa
uxe VXJ
where KX and V are the KV caches of the c-th chunk.
AGU = [(2 Xj),
(5)
Next, we perform a global attention operation. This global attention enables the model to aggregate information across all chunks, ensuring that global dependencies are captured. The global attention computation for X is given by:
where f represents the matrix multiplication used to com- pute the attention score between X² and Xý. Then, the cumulative attention score for the j-th token in the e-th chunk is computed by summing the local attention scores over all tokens in the query chunk:
[x x) KT
Ag Softmax
(10)
Vd
where Ag E I ((= is the global attention score matrix for the query chunk. The corresponding output of the global attention computed as:
Sc,j = Σ Aiu)): 1=1
j= 1,,,2...,
(6)
where Se.j E R denotes the cumulative attention score for the j-th token in the e-th chunk, and w. is the length of the query chunk X². The cumulative attention score aggregates the attention distributions from each token in the query to each token in the chunk, thereby measuring the relevance of
Fg = Ag V,,
(11)
where Fg E IR, xd represents the globally updated features for the query chunk. Finally, the updated global represen- tation is passed through the decoding stages, enabling the
4

---

ParallelComp: Parallel Long-Context Compressor for Length Extrapolation
model to generate outputs while effectively leveraging in- formation from all chunks.
Sink Blas
Recency Blas
Atteation Score
Tawe Hend
Attertinn Soore
Lyw Weal
3.2. Parallel Attention Bias
301 200
00
Theoretical insights into parallel attention bias. In this section, we develop theoretical framework to understand Parallel Attention Bias, extending the concept of attention collapse (Dong et al. ) to parallel attention as described in Section 3.1 We focus on the sparsity behavior of the local attention matrices computed over parallel chunks and examine its impact on both efficiency and accuracy.
Midddle Biss
Coltpe
Altentonn Saare
Lager Real
Layo Red
Afterton
Mountain
Unifiern
Attention Scate
Atteodoo Store
Theorem 3.1. Consider the following setup:
Part For any > O, the sparsity threshold of ef- fective entries A7 decreases as w increases. e rep- resents a user-defined threshold controlling sparsity in the attention matrix. As the number of chunks (C) increases, governs the trade-off between preserving information within each chunk and computational effi- ciency.
Telern ID
Tokom II
Figure 3: Several types of attention distribution. The Token ID represents the token position in the input text.
Local Attenion
Global Altonion
Part 2: The number of effective entries k in each row of Aç is
Acteution Scote
by:
0.000
0.008
0.006-
log w) S w - exp (0 (o(
5
wd' where R is the rank of the sparse attention matrix, inftuencing the effective dimensionality of retained at- tention entries, and is a probability bound controlling the confidence level of the sparsity constraint.
R
0.002
2000
4000
6000
8000 10000
Taken ID
Figure 4: Comparison of local and parallel attention patterns. The blue lines show the local attention distribution within a chunk, while the yellow lines represent the parallel attention patterns in global attention.
Part 3: With high probability (1 - 8), the number of
ineffective entries each row satisfies:
lim ( [A) = k. 100000
Proof Sketch of Theorem 3.7 Proof sketch of Part I: By utilizing the exponential decay property of local attention weights (as derived in Theorem[A.] [. the sparsity threshold for effective entries in Af can be bounded by:
Proof sketch of Part 3: Substituting the bound on into the definition of ( J, the number of ineffective entries, we obtain:
lim (A 2 w k.
6 exp (O(R). Vog(w- (w- (w k))8))
Finally, observing that R 0( ((Vloo(()) ensures that the sparsity growth bounded as - co. A more detailed proof is available in Appendix A
This inequality indicates that increases, the threshold for retaining effective entries becomes stricter, thus limiting the number of such entries.
Discussion. Theorem 3.1 emphasizes the inevitability of attention collapse in parallel attention. If we fix the sparsity threshold and keep the number of chunks C' constant, as the input sequence length increases, the effective number of attention entries within each chunk decreases as the chunk size w increases, despite partitioning the input sequence into C chunks. The key insights include: i) Each local attention matrix Ai exhibits sparsity behavior akin to the global at- tention matrix, with most entries becoming negligible for
Proof sketch of Part 2: Rearranging the above inequality, we derive an upper bound on k; the number of effective entries:
(o(loRte (ogg"(e))) w)
(E R2
))
8
5 w w exp
wdd'
Thus, the number of effective entries in each row of the attention matrix is w k.
5

---

ParallclComp: Parallel Long-Context Compressor for Length Extrapolation
eviction
After eviction
Parallel KV Cache Eviction
KV Cache Eviction
Evict sink bias tokens
Eviet recent bias tokens
Evict all bias tokens
Layer
Layer
Layer
Layer 18 Head
Layer Head
Head
Laver Head
Layer Head
Laver
Figure 5: Several types of attention bias and patterns. In the figure, Parallel KV Cache Eviction performs independent KV cache eviction within each chunk, while KV Cache Eviction unifies this process during global attention. Parallel KV Cache Eviction significantly reduces the computational load of global attention.
large w. ii) When long sequence is processed in paral- lel, aftention bias becomes unavoidable, with the attention mechanism consistently focusing on a small subset of tokens due to its inherent limitations, even when more information is available. Choosing an appropriate sparsity parameter mitigate this issue. iii) Dividing the input into chunks reduces computational overhead while preserving sparsity within each chunk, leading to an efficient approximation of global attention.
Threshal
4. Empirical Study of Parallel Attention Bias
Threshold n.3
In this section, we investigate the attention sink phenomenon in parallel attention and compare its similarities and differ- ences with the regular attention sink phenomenon. Specifi- cally, we explore the following question:
Q1: What types of attention patterns can be summa- rized? summary, three main types of attention patterns emerge, as illustrated in Figure U-shape, Mountain-shape, and Uniform-shape.
Culibration
Head ID
After Callbration
Figure 6: The distribution of tokens with abnormally high attention scores. Blue represents outliers.
Observations. These attention distributions give rise three corresponding biases: i) Attention sink, where focus is concentrated the initial few tokens. ii) Recency bias, where attention is more strongly concentrated at the tail. iii) Middle bias, where attention is disproportionately focused on a few tokens in the middle of a sequence. iv) These biases manifest in a wavelike pattern, with Rs containing three token types (R,, Rm, R,,) corresponding to these biases.
Observations. Similar the blue local attention, the yellow curve shows the U-shaped attention sink repeatedly appearing in global attention. ii) Parallel attention and local attention both exhibit severe recency bias, but the bias is significantly mitigated in parallel attention compared to local attention. iii When computing global attention Ag. the model suffers from a more severe recency bias compared to the attention sink, though it still less pronounced than within Ai (blue line). iv) Compared to the classical attention distribution, i.e., the local attention, the peaks of Ag within the chunk are significantly weakened, indicating that global attention can significantly mitigate recency bias. In other words, the parallel attention itself can mitigate attention bias.
Q2: Is there any difference between the attention bias in parallel attention and the attention bias in classical attention? In this part, we provide detailed analysis of bias in parallel attention. We observe in Figure Q that there are relatively more peaks within the contexts compared to the classic attention mechanism.
6

---

ParallelComp: Parallel Long-Context Compressor for Length Extrapolation
Singk-DDecumnt Q4
Multi-Document Q4
Summarization
Few-shol Learning
Synthetic
Cude
Methods
NHTYA
Qusper
MF-en
HotpatQA
ZWikMMAA
Masiqee
Gov
QMSaam
MullNwwss
TREC
SAMSum TrivieQA
PCamu
RB-F
AYG
Max Length
84123
24204
19727
20325
19001
20520
00515
34477
16271
13049
26756
21884
32199
17158
37628
58822
20657
Llama2- Baeann2-B-chut--aee -kk
F
18.62
19.53
35.49
31,07
26.15
9.91
25.52
30.87
26.28
62.00
82.68
40.36
5.50
10.50
61.04
55.30
39.21
Dysamic-Pi
9.69
20:05
33.10
16.40
3.62
27.83
18.75
16.53
1.58
5.14
28.54
AWuee
13:02
14.25
31.51
29.55
28.75
16.96
26.30
4.08
4,30
49.39
30.46
ChunkLlama
22.97
20.52
33.71
28.91
26.14
13.84
14.84
21.62
18.13
62.50
77.15
40.83
2,03
4.00
59.81
54.33
31.33
InfLLM
16.14
22.11
29.86
30.99
30.74
9.41
26.33
20.63
26.18
62.50
$4.24
39 92
3.36
6.00
60.15
55.99
32.91
AllenCalleationNNKK
14.05
12.49
32.52
30.61
31.22
12.84
29.72
18.24
24.40
61.90
72.88
30 14
2.33
3.00
48.86
50.36
30.29
Ours
23.20
17:50
64,00
4.00
36.60
Curs-calllvatton
24.95
19.07
38.16
32.62
22.64
25.42
22.82
26.01
5.00
32.50
58.84
37.21
Ours compression
25.33
16.97
35.25
39.49
32.47
20.17
24.35
21.97
25.08
63.50
34.46
40.81
4.00
31.50
59.43
58.54
36.37
Ours calibration compresssoo
24.04
18.39
38.03
39.89
35.38
22.15
24.26
22.46
24.51
63.50
$4.83
40.73
4,00
31.50
57.67
58.48
26,86
(S))
24.31
38.13
39.69
44.16
35.66
21.00
28.35
23.06
26.96
73.00
90.13
42.46
4.61
68.50
661.46
56.11
42.29
Dynamic-PI
21.71
36.66
35.48
14.28
29.43
22.00
2.33
47.36
40.63
NIK Aware
25.92
32.54
23.5L
33.74
24.13
26.35
7.24
95.61
34,84
41.33
Chun&Llama
25.01
37.39
43.52
49.37
37.56
30.95
17.57
23.51
19.72
76.00
90.38
42.14
4.71
67.95
61.10
52.57
42.47
InfLLM
19:90
43.52
40.58
48.31
35.99
23 25
30.49
21.60
26.53
76.00
50,93
42. 30
8.00
74.00
$8.98
$2.46
43.18
AllnCalleetion-NTK
26.55 54
37.52
41:17
47.5 56
18.90 18.98
26.
34.21
23.35
25.64
45.50
89.23
42.21
4.81
93.51
36,86
42.87
41,02
Curs
26.67
39.05
42.66
40.02
26.23
29.10
24.18
42.07
7.81
44.95
Curs-calllvatton
26.89
39.46
42.01
49.88
26.68
29.17
24.55
26.77
72.50
42.13
8.02
92.75
58.05
53.97
45.21
Ours compression
26.18
36.56
39.72
47.10
34.89
24.96
27.03
23.86
24.52
67.00
89.55
41 1.20
7.57
92.29
58.51
52.15
43.31
Ours calibration compression
26.46
37.49
41.28
48.25
36.29
26.68
26.79
24.98
25.18
69.00
90.37
40.72
7.34
91.29
57.30
53,97
44,31
Table I: Length Extrapolation Performance Comparison across Different Tasks. Ours-calibration and Curs-compressoon both represent parallel KV Cache Eviction, where the former evicts tokens of Rs, and the latter evicts tokens of Rg Ours- iilbrratio-compressi represents the simultancous adoption of both eviction strategies. FullKV refers to truncating the context to 4k or 8k lengths (without extrapolation) for generation.
Q3: Can the eviction strategy alleviate attention bias?
InfLLM Xiao et al.) 2024), on LongBench (Bai et al.)
By evicting different types of RØ at different layers, we have the following observations:
2023 and InfiniteBench (Zhang et al. 2024). evaluat-
ing them on Llama2-7B-chen chhhhth (Touvron al.
2023
Observations. i): From Figure 5 we can find that KV
LLaMA3.1 (Grattafioni et al., (024)) Qwen2.5
YYng
cache eviction exacerbates the bias. However, parallel cache eviction can achieve more stable distribution. ii):
paraaleel KV
et al. (022a) and Miima-3-8B-Instruee
(AI
2024).
We also compare our method with the following open-
Evieting sink bias tokens in the early layers may exacerbate attention bias, but evicting them in the deeper layers can mitigate this attention bias. iii): Evicting recency bias to- kens in the intermediate layers can mitigate attention bias, while evicting recency bias tokens in the deeper layers re- distributes the attention scores obtained by the recency bias tokens to the intermediate tokens. iv): Simultaneously evict- ing sink bias and recency bias tokens can alleviate attention bias in the intermediate layers (Layer 16). v): As shown in Figure 6 evicting tokens with abnormally high attention scores appears to effectively mitigate attention bias within the model. However, the impact of this strategy on task- specific performance remains uncertain. We will investigate this further in our experiments.
source and closed-source models trained on long-context data: ChatGL.M-3-611 1-MM---6--18888 (GLM et al. 2024). Kimi-
Chat (Al 2023). Yi-6B-200K (01AAl 2023a), Yi-34B- 200K (OL.AI) 2023b), C (Anthropic) 2023), Yarn-
Mistral 1 12kk (Peng et al.) 2023). and GPT-4 (Achiam) et al. 2023). Since AttenCalibration only calibrates the attention distribution and lacks the capability for length extrapolation, we incorporate NTK-aware techniques to en- able this functionality, resulting in AttenCalibration-NTT Details of our hyperparameters are provided in Appendix C
5.2. Length Extrapolation Settings
Main results. We present our method in Table showing the performance of several strong baselines on LongBench. We have the following main findings: i): Our method is the only one that surpasses FullKV (i.c., the bascline without any length extrapolation) across different backbones. ii): Section reveals that parallel KV cache compression exac- erbates attention bias. However, combining it with the evic- tion RH method to calibrate the attention distribution, i.c.. Ours-calibration- www.ccllibaaiiooocopeessioo can restore the performance to that of the original KV cache size. iíi): Chunk-based length extrapolation methods, such as InfLLM and ChunkL-
5. Experiment
5.1. Experimental Settings
Models, Baselines, and Tasks. We compare method with existing length extrapolation approaches, including Position Interpolation (PI) (Chen et al.) 2023b). NTK- Aware [Loca|LLaMA] 2023b), ChunkLlama (An et al. 2024). AttenCalibration (Yu et al.) (024), APE (Yang et al. 2025b), StarAttention (Acharya et al., 2024), and
7

---

ParallelComp: Parallel Long-Context Compressor for Length Extrapolation
tionally well on needle-in-a-haystack retrieval tasks (R.PK, R.Num, R.KV), being the only model capable of achiev- ing over 90% accuracy across all tasks, surpassing even the strongest closed-soure model, GPT-4, ii): Position ancoding-based length extrapolation methods, such as NTK- Aware, Dynamic-PI, generally struggle to achieve good performance on tasks with ultra-long contexts compared to chunk-based extrapolation approaches. iii): Our training- free extrapolation method, using an 8K window, is the only approach that surpasses the powerful closed-source mod- els Kimi-Chat and Claude-2, achieving 91. 17% of GPT-4's performance on ultra-long contexts with an 8B model.
Date-Debug
Aveeage
Length
125k
PMIKY
1:36
1:30
044
1144
17.43
21.37
7:36
DyansicP
0.17
5.0
0.00
7.42
2.00
31.33
5:15
2.54
600
0.00
306
7.11
18.78
535
11:07
biLLM
19000
N651
2440
29.90
22.34
0.00
5,9
0.00
1.66
5.1
19.34
4.%
Oal
19000
57.63
20.99
33.02
19.71
25.13
19:45
Exitration
19000
18.44
32.89
36.34
19:71
36.38
$1.21
Gurs hawecclleettt---ee compeessic
9130
14.14
10.90
15.40
13.30
28.23
46.41
Metlenla
R.P%
R.Num
R.KY
EnAMC
MaliFF
Codc-
Arcrass 10111
THIKK
6.10
5.27
4.30
43.29
15:57
23:11
Draanic-Ff
23.71
13:45
3,30
1,7
Chaskllass
3.5
9.15
3.50
13.54
34,29
11.42
12:51
MrsCCalminnnNTI
4.5
5.47
12:49
34.25
36.57
22.58
10.83
LX
41.70
19000
90.3
12.34
Ouz- caliiiiiiii
100.00
00.40
93.89
$6.77
48.00
25.24
68.35
19000
91.3
89.20
55.45
48,00
21.31
67.6
Language modeling. To further compare the performance of our method in language modeling, we present the results of perplexity (PPL) calculations on the NarrativeQA test set in Table 3 which reflect the model's performance in long-context language modeling. For fair comparison, we typically calculate the PPL for the query chunk, as it cor- responds to the model's decoding phase. i): Chunk- position extrapolation methods (ChunkL InfLLM,, and Ours) achieve significantly lower PPL compared to position encoding-basse based methods (Dynamic-Pl and NTK-Aware), ii): Position meoding-based methods start to collapse in per- formance for language modeling when the length exceeds 32k. ii): As the number of chunks increases (from 2K to 128K), our method still demonstrates consistent perplexity stability across different lengths. Surprisingly. ChunkL- lama maintains high performance on Mauma3-8-iinstruce outperforming other methods.
10000
$1.00
56.77
propetetary
Midels
R.PK
R.Nun
R.KV
EnMC
MathFP
Coll-Dbbeg
Average 7K.55
(PPT.
19L10
1861
$9.10
67.25
60,01
37.66
Kini-Char
56.14
95.33
11.00
72,09
17:57
17:14
16:11
(lodbo7
97%
11
15:40
67:05
17.29
17:37
open searce
Y&R 1B-125
92.71
$6.61
27.95
42:92
Y1-8B 300K
1m
<5
36.03
30:15
Y:348-2000 200
Jm
888
<55
38.43
25.11
46.56
Table 2: The model's performance on the InfiniteBench
dataset across different datasets.
Llama2-7B-chhe 4k)
Methods
2k
4k
8k
16k
32k
64k
128k
Llama2.7b
7.03
6.21
100
10
100
> 100
>> 10
Dymamic-PI
7,05
6.71
11.62
10
10a
NTK-Aware
8.61
8.41
8.29
7.19
40.71
> 10
> 10
ChunkLlama
7,03
6.71
6.42
5.01
4.82
12.36
43.57
InfT L.
23.24
23.46
19.84
18:26
18.97
8.01
9.71
11.97
10.46
11.34
11.58
12.56
Llama3-8BB-ne (nstruicikk
Methods
2k
4k
8k
16k
32k
64k
128k
5.3. Evaluation in Long-context Models
Llama3-88
9.90
9.15
10?
10
> 10
Dymmic-PI
9.90
9.15
17:25
10a
10
10
To demonstrate the effectiveness of our method for long- context models, we evaluate it on two models trained with contexts up 128K, which therefore do not require any extrapolation capabilities: LLaMA3.1 (Grattafiori et al., 2024) and Qwen2.5 (Yang et al., 2025a). used as base mod- els. All evaluations are conducted under a consistent 24K KV cache size. While standard baselines directly utilize the full 24K position encodings, our method applies ex- trapolation techniques to reuse 6K position encoding, thereby supporting longer input lengths without modify- ing the model architecture. To ensure faimesss we stan- dardize the use of special prompt tokens across models (e.g., < beg n_of__extt >> for LLaMA3.1), 1), which we observe to have a significant impact on performance. All reported results correspond to configurations that include these prompt tokens.
NTK-Aware
10.71
9.66
8.16
6.74
8.66
77.63
> 10
ChunkL.nama
9.88
9.14
7.92
6.57
6.13
5.33
5.40
IntLLM
8.50
9.30
8.72
9.47
8.98
9.66
9.10
Ours
5.85
6.75
6.30
5.61
5.13
5.72
Table We test the perplexity on the NarrativeQA Kočöský et al.
2018) test set.
lama, generally perform better than position encoding-based methods such as Dynamic-Pl and NTK-Aware. iv): Directly calibrating the attention distribution in NTK-aware length extrapolation methods, such as AttenCalibrationNNKK leads to strong performance primarily on the longest datasets, in- cluding NurvQA, GovReport, and RB-P. This suggests that the effect of attention distribution calibration becomes in- creasingly significant as input length grows.
Extrapolating beyond 128K context lengths. We eval- uate the performance under extremely long contexts in Ta- ble comparing it with several powerful open-source and closed-source models. These models are trained on context lengths exceeding 1 128K, and thus do not require additional extrapolation capabilities to handle ultra-long contexts. We have the following findings: i): Our method performs excep-
As shown in Table 4 and Table 5 our PARALLEL COMP method consistently improves performance across broad range of tasks. On LongBench, we observe modest but consistent gains compared to baselines. On InfiniteBench, which emphasizes ultral-long context understanding, our method demonstrates significant improvements, particularly
8

---

ParallelComp: Parallel Long-Contex Compressor for Length Extrapolation
Method
NARR
QAS
MULT
HOPT
2WK1
MUS
GOV
QMS
NEWS
TREC
TRIV
SSM
PCNNT
PREN
LCC
REP
AYG
Lluma3.1
49,46
47.86
40.54
22.90
38.00
25.64
2.02
92,00
10.35
18.64
36.94
PuralleCoop--Lamaaal 1.mm--a
29.45
45,98
50.67
48.36
46.56
23.12
32.60
24,29
27.34
38,50
86.72
25.93
0.05
95.00
14.15
21.42
38.15
Qwen2.5
41.31
50.41
53.52
44.68
24.01
25.40
71.00
86.10
39.91
7.25
100.00
40.60
28.42
42.24
50.54
56.26
42.02
28.25
33.43
23.20
25.20
71.50
89.21
41.84
5.00
93.50
20.73
13.34
41.54
Table 4: Performance on LongBench benchmark. Models are evaluated under a 24K KV cache budget.
Method
PS
NUM
KV
EN.MC
MATH
CODE
AVG
phenomenon, please refer to Appendix B
Lhama311
5.39
26.25
18.60
32.86
31.52
22.56
26.36
ParallelComp-Laamae Llama3.1
100000
83.56
$8.60
66.38
37.14
22.08
59.55
Quen2.5
59.32
58.31
33.80
85.71
ParalletComp- Conns2
100.00
76.27
63.40
66.86
92.57
24.75
70.64
1051
4977974
1.11
18000
Table 5: Performance on InfiniteBench with different mod-
6871-1874
11%00
els. Models are evaluated under 24K KV cache budget.
505
Table 7: Throughput analysis. We evaluate on Llama2-7B- chat-hf and compare the improvement in chunk throughput with the use of parallel KV cache compression. Time tests were performed on the NarrativeQA dataset. Experiments are conducted on an AMD Instinct MI210 64GB GPU.
for tasks such as PS, NUM, and KV. These results indi- cate that extrapolated position encodings can be effectively reused in parts of the model's ''s position encodings to ex- tend context length, achieving comparable or even improved performance relative to using full position encodings in long- long-context models.
5.5. Throughput Analysis
We mainly focus on the throughput of chunks during context parallelism. Therefore, we compare the maximum number of parallel chunks and the memory usage before and after parallel KV cache compression. Table presents the mem- ory usage of the model using the parallel KV cache eviction strategy. On single GPU, by compressing the KV cache size of each chunk to half of its original size, we achieve a 1.76x improvement in chunk throughput, thereby achieving a 23.50x acceleration in the prefill stage with negligible performance loss.
Mas Length
123k
122k
175k
-5542
238k
Oam-
100.00
07.63
20,59
33.02
19.71
25.13
29.45
Das-cailention
10000
08.64
33.88
35.24
19.71
30.30
51.37
Siak
Sulo
100.00
91
11.00
37.12
34.37
Sick eieeioeeeeeee (7:33
100
07.50
20.00
33.19
19.14
30.56
90.33
Stck coteeoonlnlleeeeee 24.3)-243 3)
100000
97.63
20.20
31.88
18.00
39.9
25
bocresy-ntetre--aameii is
19.44
2.50
11:19
15.18
Keceacy-nn ceceacy--ittteeeee 12----1----12 13:23
192200
12.97
20.40
21.85
15.38
32.34
48.45
Receacr- eatterrreiiteeee---ee- 24:31
100100
99.63
20.0
35.01
15.57
25.99
2135
Miali ericions lipen--4
10.100
97.39
2069
34.00
13.29
Makie- cvatte ayen- 17-25
95.81
97.46
2000
34.06
19.14
30.20
49.55
cralec-rraties 24-33
100.00
97.46
19.30
30.13
19.43
28.33
20.30
Table 6: Ablation of Llama2-7B-chat-h on InfiniteBench. Ours-calibration refers the approach where layers 9-16 adopt the recency bias token eviction method, while layers 25-32 evict sink bias tokens, and layers 1-8 evict middle bias tokens. Other methods follow the naming format [Evicted Token Typel-eviction-layy layrrrovned [Evicted Layer Range].
6. Conclusion
In this paper, we propose PARALLEEICOMP. a training-free and parallel long-context compression framework that sig- nificantly enhances the extrapolation capability of large language models (LLMs) for ultra-long contexts. PAR- ALLELCOMP overcomes the critical memory bottlenecks in length extrapolation and systematically analyzes the at- tention bias that arises in such settings. Specifically, our method allows 8B LLMs to extend inference length from 4K to 128K tokens on single A100 80GB GPU with- out retraining or significant degradation in performance. By leveraging chunk-basee parallel attention, dynamic KV cache eviction, and an attention calibration strategy, our approach alleviates both excessive memory usage and the attention sink phenomenon. Extensive theoretical and em- pirical results demonstrate that PARALLEL COMP effectively mitigates attention bias and enables robust, end-to-end in- ference. Notably, our method achieves 91. 177% of GPT-4''s performance on ultra-long context tasks using an 8B model, outperforming various state-of-the-an closed-source models. These findings pave the way for more scalable and efficient long-context inference.
5.4. Ablation of Attention Bias
We present in Ta the impact of evicting different bias tokens various layers on different tasks. We have the following observations: i): The R, in the shallow layers (1-8) is crucial for retrieval tasks. Without these tokens, the model's performance will be significantly impaired. ii): The R, in the deeper layers (layers 9-16) plays a crucial role in the model's reasoning abilities. Evicting these tokens results in a decline in performance on coding and math tasks. iii): Shallow Rm, (layers 1-8) damages the model's under- standing ability, and evicting them can improve the model's performance. Deep Rm, (layers 24-31) contributes to the model's 's ability in reading comprehension tasks (En.MC), and evicting them harms the model's 's performance. iv): R, in the early layers (layers 1-8) is important for the model's in-context learning ability. For a detailed analysis of this

---

ParallclComp: Parallel Long-Context Compressor for Length Extrapolation
Impact Statement
Anthropic. Model card and evaluations for claude models, 2023. URL https:://wwwt www.wwww..tttr....ooooo cessed: 2025-01-25.
Ac-
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Bai, Y., Lv, X., Zhang, J., Lyu, H., Tang, J., Huang, Z., Du, Z., Liu, X., Zeng, A., Hou, L.,, et al. Longbench: A bilingual, multitask benchmark for long context under- standing. arXiv preprint arXiv:2308. 14508, 2023.
Acknowledgements
bloc97. Add ntk-aware interpolation "by parts" rection. https::/githuu htt. lle/ -caled-rope/pul rope/pul1/1 2023. Accessed: 2025-01- 12.
This work supported in part by the Theme-based Re- search Scheme (TRS) project 745-201/22-RR of the Research Grants Council (RGC), Hong Kong SAR, and in part by the AVNET-HKU Emerging Microelectronies & Ubiquitous Systems (EMUS) Lab.
Chen, G., X., Meng, Z., Liang, S., and Bing, L. Clex: Continuous length extrapolation for large language mod- cls. arXiv preprint arXiv:2310.16450, 2023a.
Future Work
While PARALLELCOME enables efficient length extrapo- lation up 128K tokens, future work can explore its ap- plication to long-chain reasoning and ultra-long in-context learning (Xiong al., 2023). This includes designing meth- ods for reasoning over 100K+ tokens, developing test-time scaling. Further exploration into in-context learning will also be critical for reliable deployment in real-world long- context reasoning.
Chen, S., Wong, S., Chen, L.. and Tian, Y. Extending context window of large language models via positional interpolation. arXiv preprint arXiv:2306. 15595, 2023b.
Chen, Y., Lv, A., Luan, J., Wang, B., and Liu, W. Hope: A novel positional encoding without long-term decay for enhanced context awareness and extrapolation. arXiv preprint arXiv:2410.21216. 2024.
Chi, T.-C., Fan, T.-H., Ramadge, P.J., and Rudnicky, A. Ker- ple: Kernelized relative positional embedding for length extrapolation. Advances in Neural Information Process- ing Systems, 35:8386-8399 2022.
References
0L.AI. Yi-34b-200k.
2023a.
URL https:
// Ac-
wuggingfacc.cco
cessed: 2025-01-25.
Dao, T. Flashattention-22 Faster attention with bet- ter parallelism and work partitioning. arXiv preprint arXiv:2377.0869/ 2023.
01.AI.
Yi-6b-200k, 2023b. URL
https://
huggingface wwtp////a//11-3-200000000
Ac-
Devlin, J. Bert:
Pre-training of deep bidirectional trans- formers for language understanding. arXiv preprint DrXiv:1810.0400 2018.
cessed: 2025-01-25.
Acharya, S., Jia, F., and Ginsburg, B. Star attention: Effi- cient Ilm inference over long sequences. arXiv preprint arXiv:2411.17116, 2024.
Dong, Y., Cordonnier, J.-B., and Loukas, A. Attention is not all you need: Pure attention loses rank doubly exponentially with depth. In International Conference on Machine Learning, pp. 2793-2803. PMLR, 2021.
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.0877 2023.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle,
A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama 3 herd of models. arXiv preprint arXi::2407.21780 2024.
AI M. Kimi chat, 2023. URL https://king
moonshot. /n/l Accessed: 2025-01-25.
Fu, Y., Panda, R., Niu, X., Yue, X., Hajishirzi, H., Kim, Y., and Peng. H. Data engineering for scaling language models to 128k context. arXiv preprint arXiv:2402. 10171, 2024.
AI, M. Llama 3: A family of large language models. httpps///laame /malama..a..mmmmmm..aa .meta.com 2024. URL https; Instruction-tuned version.
//llama. "ilama.meta.
An, C., Huang, F., Zhang, J., Gong, S., Qiu, X., Zhou, C., and Kong, L. Training-fres long-contexs scaling of large language models. arXiv preprint arXiv:2402.1746. 2024.
GLM, T., Zeng, A., Xu, B., Wang, B., Zhang, C., Yin, D., Zhang, D., Rojas, D., Feng, G., Zhao H., et al. Chatglm: A family of large language models from glm-130b to glm-4 all tools. arXiv preprint arXiv:2406. /2793, 2024.
10

---

ParallciComp: Parallel Long-Context Compressor for Length Extrapolation
Golovneva, O., Wang. T., Weston, J., and Sukhbaatar, S. Contextual position encoding: Learning count what's important. arXiv preprint arXiv:2405.18719, 2024.
perplexity
degradation..
June 2023b.
URL
https: /ttw//wwwwww. weddit......... w.w.edddi.coo..mmm wtt.tttcoooooooom www.r/oooaaaoooee///oo ILLMA/
commentss/411211 wtttttaaaaaeeeeaaaaaaaaaeaeee scaled
rope_ _lpe_allows 11ama models_ta to have/
Grattafiori, A., Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Vaughan, A., et al. The llama 3 herd of models. arXiv preprint arXiv:2407.22 2000:22077.788, 2024.
Peng. B., Quesnelle, J., Fan, H., and Shippole, E. Yarn: Efficient context window extension of large language models. arXiv preprini urXiv:2309.00077 2023.
Gu, X., Pang, T., Du, C., Liu, Q. Zhang, F,, Du, C.,, Wang, Y., and Lin, M. When attention sink emerges in language models: An empirical view. arXiv preprint arXiv:2410.10781, 2024.
Peysakhovich, A. and Lerer, A. Attention sorting combats recency bias in long context language models. arXiv preprint arXiv:2310.014277 2023.
Press, O., Smith, N. A., and Lewis, M. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108. 12409, 2021.
Han, C.. Wang, Q.. Peng, H., Xiong, W., Chen, Y., Ji, H., and Wang, S. Lm-infinite: Zero-shot extreme length generalization for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume Long Pupers), pp- 3991-4008, 2024.
Press, O., Smith, N. A., and Lewis, M. Train short, test long: Attention with linear biases enables input length extrapolation, 2022.
Jiang, H., Wu, Q. Luo, X., Li, D., Lin, C.-Y,, Yang, Y., and Qiu, L. Longllmlingua: Accelerating and enhancing Ilms in long context scenarios via prompt compression. arXiv preprint arXiv:2310.006 06839, 2023.
Ratner, N., Levine, Y., Belinkov, Y., Ram, O., Magar, I., Abend, O., Karpas, E., Shashua, A., Leyton-Brown, K., and Shoham, Parallel context windows for large lan- guage models. arXiv preprint arXiv:2212.1094/ 2022.
Kočiský, T., Schwarz, J., Blunsom, P., Dyer, C., Hermann, K. M., Melis, G., and Grefenstette, E. The narrativeqa reading comprehension challenge. Transactions of the Association for Computational Linguistics, 6:317-328, 2018.
Su, J. Rectified rotary position embeddings. https:// g github cachub..co//bbo www.e/o//ooooerrerooooee 2023.
Su, J., Ahmed, M., Lu, Y., Pan, S., Bo, W., and Liu, Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568:127063, 2024.
Li S., You, C., Guruganesh, G., Ainslie, J., Ontanon, S., Zaheer, M., Sanghai, S., Yang, Y., Kumar, S., and Bho- janapalli, S. Functional interpolation for relative positions improves long context transformers, 2023a.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, et al. Llama: Open and efficient foundation lan- guage models. arXiv preprint 2rx. 2023.
Li, Y., Dong, B., Lin, C., and Guerin, F. Compressing context to enhance inference efficiency of large language models. arXiv preprint arXiv:2310.0620. 2023b.
Vaswani, A. Attention all you need, Advances Neural Information Processing Systems, 2017.
Liu, N. F., Lin, K., Hewitt, J., Paranjape, A., Bevilacqua, M., Petroni, F., and Liang, P. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157-173, 2024.
Wan, Z., Wu, X., Zhang, Y., Xin, Y., Tao, C., Zhu, Z., Wang. X., Luo, S., Xiong, J., and Zhang, M. D2o: Dynamic dis- criminative operations for efficient generative inference of large language models. arXiv preprint vrXiv:2406.1303. 2024.
Laca
Dynamically scaled rope fur- ther increases performance of long context Ilama with zero fine-tuning, July 2023a. URL
Xiao, C.,, Zhang, P., Han, X., Xiao, G., Lin, Y., Zhang, Z., Liu, Z., and Sun, M. Inflim: Training-fre free long- context extrapolation for llms with an efficient context memory. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
httpp::/www..eeddt..coo///////c comments/14mrgee commeetts///aaggp///oyyaaaallal/
htttps://ww..rr
rope_furee further ftteefuuhhe__nceeeees//
LaMA Ntk-aware scaled rope allows llama models to have extended (8k+) con- text size without any fine-tuning and minimal
Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M. Ef- ficient streaming language models with attention sinks, 2023.

---

ParallelComp: Parallel Long-Context Compressor for Length Extrapolation
Xiong, J., Li, Z.,, Zheng, C., Guo, Z., Yin, Y., Xie, E., Yang.
Z., Cao, Q Wang, H., Han, X., al. Dq-lore: Dual
queries with low rank approximation re-ranking for in-
context learning. arXiv preprint arXiv:2310.02994. 2023.
Xiong, J., Shen, J., Ye, F., Tao, C., Wan, Z., Lu, J., Wu, X., Zheng, C., Guo, Z.., Kong, L.,, et.. Uncomp: Uncertainty- aware long-context compressor for efficient large lan- guage model inference. arXiv preprint arXiv:2410.0300 2024.
Xu, P., Ping, W., Wu, X., Xu, C., Liu, Z.., Shoeybi, M., and Catanzaro, B. Chatqa 2: Bridging the gap to proprictary Iims in long context and rag capabilities. arXiv preprint arXiv:2407. 14482, 2024.
Yang, A., Yu, B., Li, C., Liu, D., Huang, F, Huang, H., Jiang, J., Tu, J., Zhang, J., Zhou, J., et al. Qwen2. 5- Im technical report. arXiv preprint arXiv:2501. 2025a.
Yang. X., Chen, T., and Chen, B. Ape: Faster and longer auggett- generation via adaptive parallel coding. arXiv preprini arXiv:2502.05441, 2025b.
Yu, Z., Wang. Z., Fu, Y., Shi, H., Shaikh, K., and Lin, C. Unveiling and harnessing hidden attention sinks: En- hancing large language models without training through attention calibration. arXiv preprint arXiv:2406.155 15765, 2024.
Zhang, X., Chen, Y., Hu, S., Xu, Z., Chen, J., Hao, M., Han, X., Thai, 7.,, Wang, S., Liu, Z.,, et al. infinite bench: Extending long context evaluation beyond 100k tokens. In Proceedings of the 62nd Annual Meeting of the Asso- ciation for Computational Linguistics (Volume I: Long Papers), pp. 15262-15277, 2024.
Zhang, Z., Sheng. Y., Zhou, T., Chen, T., Zheng, L., Cai, R., Song, Z., Tian, Y., Ré, C., Barrett, C., et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36:34661-34710 2023.
Zheng, C., Gao, Y., Shi, H., Huang. M., Li, J., Xiong, J., Ren, X., Ng, M., Jiang, X., Li, Z., et al. Dape: Data- adaptive positional encoding for length extrapolation. In The Thirty-eighth Annual Conference on Neural Informa- tion Processing Systems, 2024.
Zhu, Y., Gu, J.-C., Sikora, C., Ko, H., Liu, Y., Lin, C.-C., Shu, L., Luo, L., Meng. L., Liu, B., et al. Accelerating in- ference of aetrivval-augmeent generation via sparse con- text selection. arXiv preprint arXiv:2405.16// 2024.
12

---

ParallclComp: Parallel Long-Context Compressor for Length Extrapolation
A. Proofs for Parallel Attention Bias
A.1. Exponential Decay of Local Attention
We formalize the exponential decay of attention values as a function of relative distance when using relative position encodings (Su al. 2024). This behavior modulated by sparsity control parameter R, which regulates the rate at which attention diminishes increasing distance.
Theorem A.I (Exponential Decay of Attention). Let Af(i.j] denote the local attention weight from token token j within chunk c, computed using scaled dot dot-product attention with relative position encoding. Suppose the dot product between query qi and key kj depends linearly on their relative distance, i.e.,
q k- R aa- d(i,j);
where j( is the positional distance and a: >> O is a constant. Then the attention value exhibits exponential decay:
Aii ~ exp (-O(R) d(i.)))
where R is a sparsity parameter controlling the effective attention range.
Proof. The local attention matrix is given by
9:-k;
exp
vil
Alli,
-1 exp
10
k::kg
vdd
Assuming 9: ky = -a -a-a-dep d(i. we obtain:
4i kg vd
(-va d(i.j)
exp
= exp
Letting O(R) == a/VVd leads to:
Ai x exp (-O(R) d(i.)),
establishing the exponential decay behavior.
Discussion. This exponential decay arises from the softmax mechanism and relative position encoding: the relative distance increases, the inner product diminishes, leading to exponentially suppressed attention values. The parameter R determines how rapidly this suppression occurs. A higher R yields slower decay (broader attention), while a lower R enforces sharper loculity-crucial for analyzing sparsity and receptive fields in attention models.
Theorem A.2 (Tail Bound on Effective Attention Mass). Suppose A9 ~ exp(-O(R) (R)) d(i,j) with R = O (log w) Let e threshold and k be the number of ineffective entries row of the local attention matrix, Le., those satisfying Affi, S e. Then for any 1,
w(w Ac)
2 exp (O(R)-
log
8
Proof. Let consider the attention weight between query gi and key ky (within chunk given by
kg Vd
exp
Aflisj]
gicker
y exp
vid
Assume the dot product gi k, (after position encoding) satisfies
9i ky -a d(iij) Zi.s
where dii,j) is the relative distance, according to Theorem A.1
a > 0 is a scaling constant, and Zz,j is mean-zero,
Lub-Gaussian noise term arising from randomness in qi and ky.
13

---

ParalleiComp: Parallel Long-Context Compressor for Length Extrapolation
Sub-Gaussian concentration. Suppose Zr, is sub-Gaussian with parameter o² (variance proxy). Since qo ki E Rd assumed be independent and isotropic (or sufficiently well-behaved), the inner product Zz.j scales (0, d), after normalization by vd, we have:
Zud ~ 10)
and more generally, sub-Gaussian()) for all entries.
Tail probability for an entry exceeding c. We are interested in the probability a particular attention entry Af[i, exceeds a fixed threshold >
P [ c).
The numerator is exp Z; is the sum over all to such terms.
gorkg vd
which, via the deterministic and random parts, is exp (- (- (i,,d +
Zu
The denominator
Vd
By the softmax property, after normalization, it holds that for entries with large d(i,j) (i.e., far from the diagonal), probability concentrates low values, and for an entry to exceed the exponent must be large:
exp (- d(d
Zig Val
d(i,))
+
> cZi
Vd
or
Zis
d(i,s)
log(
vd
Vd
Union bound over all entries. We need to ensure with high probability (at least - 8) that at most & entries per row (out of w) exceed e. That is, we want (by union bound)
w(w - PP c) 5.
Then,
5
[(AT).)) w(w k)
which, after inverting the softmax and using sub-Gaussian tail estimates for Zz gives
Z
log(tZi) + Va Add(i.))
IP
w(w
The sub-Gaussian tail bound reads for 0:
P(X > 1) exp(-111))
Setting t²/2 log [m((w=k) k) leads to
www - k))
2 log
and relating back normalization and decay constants, finally yields
(00(8)) / w(w - k)
2 exp
where a/ Vd (showing dependence on d).
14

---

ParallciComp: Parallel Long-Context Compressor for Length Extrapolation
The role of d in the bound. The normalization by vd plays a key role: as d increases, the effective noise in the dot product becomes less significant relative to the deterministic decay -ad(i, pulling most attention values closer to except for small set (nearby positions). This effect concentrates the attention and tightens the tail, making large attention far from the diagonal even less probable.
Note that, in total union bound, we consider w. possible entries and sometimes further divide by d, reflecting the increased concentration with high dimension or the independence among channels (as found in certain information-theomm arguments for high-dimensional softmax). This dependence enters the denominator for the upper bound k:
S w expp exp (o
(ew) Re2
wd
Summary. The dependence on d in the denominator comes from sub- Gaussian concentration for scalar products in dimension d. As d grows, the likelihood of far-off entries (large distance) carrying significant attention decays rapidly due to stronger concentration of measure, resulting in increased sparsity of the attention matrix for fixed threshold c. Therefore, for sufficiently large w and d, with fixed
k < w,
implying
lim 15 (AfTi, k. 100000
where & = o(w).
The appearance of the term d in the denominator reflects how higher model dimensionality increases the concentration of dot products, making rare large excursions (that could create significant attention values far from the main focus) even less probable. Thus, the sparsity bound becomes stricter as increases. This probabilistic tail behavior essential for understanding how the structure and dimension of the attention model affect the sparsity and locality of its learned representations.
Remark.
A.2. Sparsity in Local Attention
Theorem A.3 (Sparsity of Local Attention). Let X Nxd be partitioned into C chunks of width w. For each chunk e, let local attention matrix Af E TR be computed via
Q
A Softmax
Vd
Let S. (A(((.)) [j E [w] A40, > for fixed c > O, and set R = O(Vlo(Vovg w)
Then for any < 5 < 1, as w + co, with high probability 1 ō,
((c) (A) = w - k,
where & k= olw) depends on and R.
Proof. We begin with Theorem A.2 which provides tail bound for the effective attention mass:
2 exp (-O(8)) / log
w(w k:)
8
Taking logarithms both sides gives
w(w k))
loge 2 -0(R)
/ log
15

---

ParallciComp: Parallel Long-Context Compressor for Length Extrapolation
Rearranging, we have
ww
k)
log cl ((R)
log
8
80
w(w k)
log" 2 O (1e))
log
8
Exponentiating both sides, have
w(w
k)
log Ri2
I exp
0
8
which implies
(0
log² R²
w(w k) S 8 exp
Solving for k gives
log²
k 2 8exp
0
R²
Now, if refine the union bound to account for all entries in probability of an entry exceeding is further divided by d due to the independence in d dimensions (assuming the dot products across dimensions act as independent sub-Gaussian random variables). That is, the standard deviation of the normalized dot product reduced by a factor /d, affecting the spread of attention weights. Thus, the probability becomes
attention matrix for d-dimensional vectors, the
P( > e) S w(w k)d
leading to the sparsity bound
(
(0( log (ew)
5
k S -exp exp
R²
wd
The presence of d in the denominator reflects how higher model dimensionality increases concentration, making the tail events (large attention weights far from the focus) less probable.
Therefore, for sufficiently large w and fixed e, we indeed have kt < w, and thus
lim
(A(() w k.
with A o(w).
Remark. The inclusion of the d term in the denominator arises from the probabilistic tail bound under the assumption that the dot products are sub-Gaussian in d dimensions. As d increases, the attention weights become more concentrated (due to the central limit effect over the d independent dimensions), reducing the portion of entries that exceed a fixed threshold e, This effect is captured in the sparsity upper bound through the explicit dependence on d.
A.3. Exponential Decay in Global Attention
We extend the above result to global attention, which spans the entire sequence.
Theorem A.4 (Exponential Decay of Global Attention). Let Agli.j] be the global attention from query i to key j. where
di k. d(i.j).
Then,
1 Agli, ~ exp (-O(R) d(i.j)),
with a
16

---

ParallciComp: Parallel Long-Context Compressor for Length Extrapolation
Proof. Analogously the local case, the attention value is
exp (- a d((,))
Agli, 2
vi
& exp exp((O((R)d((,))
7,
where Zi is the row normalization.
A.4. Tail Bound for Global Attention
Theorem A.5 (Tail Bound for Global Attention Mass), Suppose Agli, exp(-O(R)- Let lig denote the number of global attention entries below in each row. Then
(Cw + woy kig)
2 exp -0(R) v
flog
5
Proof. Applying the union bound and exponential decay form as in the local case,
P(Ag >)) (Cw wy)(er kg)
which yields the stated bound for e.
A.5. Sparsity of Global Attention
Theorem A.6. For any fixed e > 0 and R - OoooooooCCoa + Wgl), as wi + 0c.
(Ag( (Cw + myy) kg. mig
lim
kig = oCCw wg))
Proof. Since the global attention decays exponentially in distance, as in the local case the number of entries above is kg = oCCw + w.y) for R = 0( ((o/oo((ww + w.g)), ensuring overall sparsity sequence length grows.
Discussion. While global attention has a larger support span, attention values still decay exponentially with distance; only a vanishingly small fraction of entries exceed a fixed threshold for sufficiently large R. This structure ensures the computational tractability and sparsity of the attention matrices, where R modulates the effective receptive field between local and global modeling.
B. Ablation Study
In this section, we analyze the impact of different attention biases on the LongBench dataset. shown in Table g the exceptionally low performance of cennncy-vvictionllyeeeee on both in-context learning tasks, TREC and TriviaQA, as well as SAMSum, indicates that the recency bias tokens in the model's early layers crucial for developing in-context learning abilities.
C. Hyperparameter
The Dynamic-PI method interpolates dynamically according to the length of the input token. NTK-Aware refer to (Locall LaMA, 2023b) and the maximum length set to 128. ChunkLlama, InfLLM and AttenCalirrationNNTKK use hyperparameters from open source repositories. About our method, when performing parallel KV Cache compression, we use last token's cumulative attention scores compress the KV cache size within each chunk 2000/4000 for llama2/laama,, For the hyperparameter т, on Longbench, we retain 3 chunks from the priority queue except for PRe, in which dataset we retain only 1 chunk. On InfiniteBench, we retain chunk for retrieval tasks and chunks for other tasks from the priority queue. In all datasets, the context length of each chunk, including the query, is the maximum pre- pre-training length of the model. R. obtained from the first 100 tokens of the chunk, R, is obtained from the last 100 tokens of the chunk, and the remaining part of the chunk obtains Ry, All experiments are performed on 8 64G AMD Instinct MI210.
17

---

ParallclComp: Parallel Long-Context Compressor for Length Extrapolation
Singke-Demmmnt QA
Multi Doeeii-D Q4
Summarization
Few-shot Learning
Syuthetle
Code
Methods
NIYYAA
Qusper
MF-en
HolpotQA
ZWIMMQAA
Musque
GovReport
QMSam
MatuNews
TREC
SAMSim TrittQAA
PCaunt
PRc
RB-F
AVG
Mix Length
84123
24204
19727
20525
19001
20520
60515
34477
16271
13049
26756
21884
32699
17158
57628
58822
30657
1.ama2-BB-Ba 2B--2-Buttt--hf-
Ne-eviction
25.20
17.50
57.07
38.07
32.08
20.22
25.00
22.79
25.34
64,00
34.63
40.67
4.90
31.50
59.37
58.55
36.60
Sink eviction layer- 8
23.75
18.69
38.41
39.86
32.91
20.75
24.96
22.10
25.56
63.00
$4.42
60.78
4.50
30.00
54.67
59.30
36.47
Sink loyer-
23.34
19.10
25.31
36.22
Sink-evistion-ban layer- 17-24
17.75
38.79
19.67
62.00
85.35
24
4.00
28. 50
58.41
36,
Sink--vicioo-liyen255--4
23.87
18:40
35.91
38.96
31.02
20.21
25. 32.32
22. 00
25.81
64.00
84.19
50.77
3.50
30.00
58.58
58.21
36.23
Recomyy-viiztio-tteerr 1-8
22.71
16.95
35.24
36.14
30.60
17.19
25.21
22.11
26.22
59,00
68.00
40.03
2.50
31,00
58.07
51.47
33.90
Kecency-eviction 1-11199-66
24.95
13.54
5.00
34.45
Recency eviction layer
21.68
15.17
34.97
25.
34,00
24.75
Recency eeicci--iiiiin---e layer 25-32
24.15
17.32
37.82
36.76
29 29.85
18.48
25.21
06
25.6
68.00
83.20
36.67
5.00
30.50
56.13
56.52
35.58
Miskle--victtio-- wwwctiio--leee---1- 1-yer-1-8
22:41
16.84
37.94
39.99
33.24
19.62
24.74
22.02
25.80
63.50
83.67
40.00
5.00
32.50
$9.22
56.71
36.45
Thabll-evviriienlleeee 1196199--9
22.96
17.63
37.50 19
40.51
30.68
21.00 09
25.
21.00 94
25. 66
62.00
85.02
40:57
4.00
35.50
59.35 20.38
57.88
36,
Middle-eviciion layer- 17:24
21.72
17.06
35.88
39.99
31,76
19.06
25.00
22.20
25.77
58,00
83.62
40.02
0.50
38,00
59.38
57,98
36.25
Middll-ovictiom prriecion-lyee--5-.. layer-25-32
21.64
17.04
19.14
25.07
Alleevition-llyem--88
0.33
0.05
1.24
0.32
0.68
0.38
1.76
3.25
1.59
1.50
5.40
1.75
0.41
0.50
23.61
12.17
3.43
Alleevkrtice-leees---1
1.60
1.97
5.06
0.65
1.44
0.81
21.75
36.22
1.81
35.00
30.77
10:54
3.00
0.50
33.25
22.89
12.95
All-evicraa-Bee loyer---llye---T 17-24
17-24
12.20
10.26
16.30
20.30
18.10
8.54
13,33
20.45
17.61
49.00
11.95
29.74
5.50
26,00
41.92
23.07
20.32
All-evizton layer
7.62
12.87
3.50
13.39
calibration
24.95
19.07
22.82
5.00
32.50
37,21
Table Bias Token Eviction Ablation. Sink-evictoon-laye---- typically means evicting sink bias tokens in layers 8, and other naming conventions follow the same pattern. Ours-calibration refers the approach where layers 9-16 adopt the recency bias token eviction method, while layers 1-8 evict middle bias tokens, and layers 25-32 evict sink bias tokens.
D. Comprehensive Evaluation
This section presents additional experiments and implementation details to further contextualize and substantiate the claims in the main text. Specifically, we investigate comparisons with Sarrivva--Aumentte Generation baselines, provide extended benchmarks with APE (Yang et al. 2025b) and StarAttentio (Acharya al. 2024), report hyperparameter sensitivity, discuss latency and memory efficiency, and elaborate on our design choices for attention bias sparsification.
D.1. Comparison with Retrieval-Augmente Generation Method
Model
QM
QASP
MSQ)
HQA
MFQA
AVG
ChatQA-2
11.64
28.85
27.81
53.81
$1.02
34.63
CharQA-2 RAG
13:20
28.85
29.77
57.81
51.15
Ours
24.18
39.05
33.25
49.58
42.66
37.74
Table 9: Performance comparison with RAG and non-RAG baselines LongBench.
Model
KV Retrieval
Numbe String
Passkey
En.MC
AVG
CharQA-2
100.00
100.00
64.19
CharQA-2 RAG
N/A 92.80
N/A
N/A
N/A
N/A
Ours
99.83
100.00
54.59
86.81
Table 10: Performance comparison on InfiniteBench. RAG methods completely fail on InfiniteBench, so we do not provide further results.
To clarify the role of length extrapolation versus to leading RAG-enhanced models such as CharQA-2 (Xu et al. (024)) representative benchmarks. T Table T0 summarize results on LongBench and InfiniteBench, respectively. The proposed method demonstrates strong robustness and competitive or superior performance in challenging long-context retrieval scenarios such as InfiniteBench, where RAG-based methods may encounter instability or diminished effectiveness.
generation (RAG), compare the proposed method
D.2. Comparison with APE and StarAttention
To comprehensively evaluate our approach in the context of existing chunked long-context processing methods, we conduct extensive experiments comparing PARALLELCOME with both APE (Yang et al., (0256) and StarAttention (Acharya et al.) 2024). APE leverages shared prefix minimize distributional disparities, incorporates a low-temperature mechanism to
18

---

ParallclComp: Parallel Long-Context Compressor for Length Extrapolation
Method
NARR
QAS
MUL
HOPT
2WK1
MCS
GOV
QMS
NEWS
TREC
TRIV
SSM
PCNNT
PREN
LCC
REP
AVG
APE
23.63
39.11
50.06
49.47
43.70
25.99
27.78
22.79
11.22
43.50
90.17
9.79
0.50
59.00
23.93
24.28
34,06
StarAtin
11.90
14.37
8.19
43.71
3,80
12.72
ParalleComp
29.45
45,98
50.67
48.36
46.56
23.32
32.60
24.29
27.34
38.50
86.72
25.93
0.05
95,00
14.15
21.42
38.15
Table 11: Comparison with APE and StarAttention denoted as StarAttn LongBench. Temperature and scaling factors for APE are indicated as APE T + S. In our experiments, we set APE's temperature to 0.5 and scaling factor to 0.8; for StarAttention, the chunk size is set to 2K. In ParallelComp, we reuse 6K position encodings to facilitate length extrapolation. All evaluations are conducted on the Llama-3. 1-8Bt-Inttruct base model with KV cache size of 24K.
sharpen attention, and utilizes a scaling factor to compensate for temperature changes, Its objective to better align the attention patterns between parallel and sequential encoding. StarAttention is designed for thunk-basee training of models with long contexts. At each generation step, it recalculates attention for every chunk, whereas PARALLELCCMM computes attention once during the prefill phase and then efficiently reuses the compressed KV cache for subsequent generation. This distinction leads to substantial improvements in computational efficiency.
We first compared the performance of different methods under the same KV cache budget. Hyperparameters are selected according to those reported in the original publications or official releases. Table I1 summarizes the representative results, where all models are assessed using standardized evaluation infrastructure. Our analysis emphasizes the memory bottleneck encountered during length extrapolation. This experiment emphasizes the memory bottleneck encountered during length extrapolation. The other methods forced truncate the input during extrapolation, resulting in significantly lower performance certain tasks compared to our approach.
QAS
MUS
QMS
APE0.8+0.8
25.92
41.99
53.79
53.64
50.54
26.46
30.15
25.42
20.68
50.50
88,70
9.72
6.50
89.00
16.71
25.78
38.47
APE0.5+0.8
23.63
39.11
50.06
49.47
43.70
25.99
27.78
22.79
11.22
43.50
90.17
9.79
0.50
59.00
23.93
24.28
34,06
APE0.2+0.8
18.83
26.53
41.70
44.63
35.91
17.71
24.31
20.14
7.96
35.75
$8.54
9.72
1.50
34.50
23.86
23.22
APE0.8+0.4
9.04
11.48
19.59
31.41
24.68
10.16
5.32
13.80
8.20
0.50
87.06
9.71
0.00
7.00
13.72
16.51
16.76
APE0.5+0.4
7.59
9.74
16.13
31.89
25.72
9.62
5.20
9.56
8.19
0.00
87.60
9.69
0.00
5.00
14.26
15.58
15.99
APE0.2+0.4
8.97
29.71
26.66
87.57
9.71
16.24
StarAtto4K
3,74
11.90
24.81
14.17
14.37
8.19
34,90
22.54
27.11
65.33
87.84
43.71
3,80
65.17
S0,54
45.40
32,72
StarAtto6K
4.65
13.63
21 11.05
14.47
15.57
6.38
34.80
22.67
26.27
66.00
65.5 54
47.91
8.00
70.00
56.48
45.42
32.43
ParalleCComp
46.56
23.32
86.72
25.93
21.42
Table Performance comparison across different methods. APE X+Y indicates temperature = X and scaling factor StarAttn4K and StarAttn6K represent StarAttention using chunk sizes of 4K and 6K, respectively.
In order to further compare with the full-size context models Sttentttntion and APE, we conducted ablation experiments as shown in Table [2] We find that even after carefully tuning the hyperparameters of both models, their average performance only surpasses that of our PARALLELCOMM by 0.32%, which further demonstrates the effectiveness of our method.
19


Reviews:
[{"review_id": "cEgmGAPj22", "reviewer": "Reviewer_JBTb", "summary": "Motivation is also for better generalization on long seqs. And to use existing LLMs and extend their attention context size. And for more efficient attention on long seqs.\n\nThe proposed method does not need any finetuning. Any existing LLM can be used, with the attention mechanism and caching adapted.\n\nThe proposed method is called ParallelComp. It uses chunk-based attention for fast parallel calculation to be able to filter out (evict) non-relevant parts of the cache/history in an efficient parallel way, and only then computes global attention on the remaining cache.\n\nMany experiments are performed to show how well it performs on length extrapolation, and results look good for ParallelComp.\n\n## Update after rebuttal\n\nWhile it is clarified that the code is being released, which is am important point, overall I keep my current score, as I'm not sure about the importance/impactfulness of the presented approach, as also pointed out by other reviewers, and the experiments could also be extended to some more recent LLMs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank for your suggestions!\n\nQ1:**For general inquiries such as typos and others.**\n\n- We promise to release our github and will correct typo error in future paper version.  \n- Regarding citation issues, the NTK-by-parts position interpolation method was not proposed in a formal paper. It was also cited from a GitHub repository in other papers, with reference [7] in the reference paper [1].  \n\nQ2:**Fig 1, is that one selected attention head in one layer, or the average over attention heads and all layers, or what else is it exactly? And for what model? Eq 3, how is this self-information log prob defined? Is this the attention score A? Why do you write P? Sec 3.1 \"concatenate them with the input query for parallel encoding\" - what exactly does this mean? What is the input query for parallel encoding? Where do I see the input query in the formula?**  \n- The attention head we show here is the distribution change of the 21st head of layer 1, and the model is meta-llama/Llama-2-7b-chat-hf.  \n- Self-information is not attention score; essentially, it is the negative log-likelihood of the question predicted based on the chunk input to the LLM. It reflects the model's confidence in predicting the query based on the context.  \n- We concatenate the input question(X^q in the formula) with each chunk and encode them in parallel. The query serves two purposes: first, to assess the importance of each chunk and decide if its KV should be stored in the GPU’s priority queue to manage memory; second, to evict tokens from the chunk’s KV cache, optimizing memory usage and throughput. In short, the query is primarily used for compression.\n\nQ3:**Sec 3.1 Chunk Eviction: What is this about? \"retaining only the most relevant chunks\" - what does this mean? how is this different to the KV Cache Eviction? What exactly is parallel about it? The previous chunk eviction is not parallel**\n- Chunk eviction means removing the entire KV cache of a chunk from a priority queue based on self-information scores, while KV Cache Eviction refers to removing tokens from a specific layer and head within a chunk.  \n- The token-level KV cache eviction process is parallel across chunks, as it depends on the cumulative attention distribution of the query across layers and heads without dependencies between chunks. In contrast, traditional KV cache eviction methods such as H2O [2] have no extrapolation capability and can only handle KV caches with a fixed context length.  \n- The eviction of chunks depends on whether the priority queue has reached its maximum size, usually determined by the GPU memory. When the size is reached, chunks completing self-information calculation and KV cache eviction compare their self-information size with those in the queue to decide retention or eviction. This comparison is typically done sequentially.\n\nQ4:**Why is Flash Attention relevant here? Flash attention is just a specific implementation.**  \n- We want to emphasize that flash attention provides faster computation and memory utilization. FlashAttention does not return the complete attention distribution matrix for each layer of the model[3], thus making it unable to perform KV cache eviction. To address this issue, we calculate the inter-chunk attention matrix for each chunk and its corresponding query block at each layer separately, based on formula (5).  \n\nQ5:**Since it is hard to obtain the complete attention distribution from Flash Attention\" - what do you mean? Sec 3.1 Attention Calibration: \"we evict tokens with excessively high attention scores\": Evict means, you only use those values with high att scores, or you exclude those and only use the others? What exactly is \"Ours\" (without the calibration R_h and compression R_l)?**  \n \n- According to [3], FlashAttention doesn't return the attention distribution, preventing us from evicting the KV cache based on attention scores. To solve this, we use the last 8 tokens from the query chunk and multiply it with the chunk's value matrix to quickly estimate a cumulative attention distribution for evicting tokens using Pytorch.   \n- Equation 7 represents that we evict tokens with abnormally high scores. At the same time, we also evict tokens with low attention scores according to Equation 6. In summary, the eviction strategy removes tokens with either abnormally high or the lowest attention scores.  \n- We calculate the full attention distribution for each head using flash-attention. To prevent abnormal patterns, we first approximate the attention distribution with Equation 5, allowing us to evict tokens that would gather excessive attention.  \n- 'Ours' represents the case without any KV cache compression or attention calibration, only with the chunk eviction mechanism.  \n\n**Reference**:  \n[1] YaRN: Efficient Context Window Extension of Large Language Models.  \n[2] H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models.  \n[3] https://github.com/Dao-AILab/flash-attention/issues/1357", "claims_and_evidence": "Better length extrapolation is claimed by the new proposed method. This is tested and verified in the experiments.", "methods_and_evaluation_criteria": "Tested on benchmarks which test for length extrapolation, so they make sense.", "theoretical_claims": "I did not check in detail.", "experimental_designs_or_analyses": "Tested on benchmarks which test for length extrapolation, so they make sense.", "relation_to_broader_scientific_literature": "The presented method is relevant for length extrapolation.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "Strengths:\n\n- Presented approach should be simple to do. Does not need any finetuning.\n- Presented approach gives good results.\n- Many experiments are performed.\n\nWeaknesses:\n\n- No code released to reproduce the experiments?\n- Some parts are a bit unclear to me. See questions below.", "other_comments_or_suggestions": "Sec 2 \"reecent\" typo.\n\nYou have a \"bloc97\" reference. That is the GitHub username of Bowen Peng (see for example: https://arxiv.org/pdf/2411.19870).\n\nThe appendix has the title \"Submission and Formatting Instructions for ICML 2025\".", "questions_for_authors": "Where is the code of the experiments? Will this be published?\n\n\nFig 1, is that one selected attention head in one layer, or the average over attention heads and all layers, or what else is it exactly? And for what model?\n\n\n\nEq 3, how is this self-information log prob defined? Is this the attention score A? Why do you write P? Shouldn't this be A?\n\nSec 3.1 \"concatenate them with the input query for parallel encoding\" - what exactly does this mean? What is the input query for parallel encoding? Where do I see the input query in the formula?\n\n\nSec 3.1 Chunk Eviction: What is this about? \"retaining only the most relevant chunks\" - what does this mean? What exactly is kept? The KV? But then, how is this different to the KV Cache Eviction?\n\nSec 3.1 KV Cache Eviction: How is this different now to the previously described chunk eviction?\n\nSec 3.1 KV Cache Eviction: What exactly is parallel about it? The previous chunk eviction is not parallel or also parallel?\n\nSec 3.1 KV Cache Eviction: Why is Flash Attention relevant here? Flash attention is just a specific implementation.\n\nSec 3.1 KV Cache Eviction: \"Since it is hard to obtain the complete attention distribution from Flash Attention\" - what do you mean? You don't get the attention weights out of flash attention? Why is this relevant? Then just don't use flash attention but something else? Or implement this yourself? Or modify flash attention?\n\nSec 3.1 Attention Calibration: \"we evict tokens with excessively high attention scores\": Evict means, you only use those values with high att scores, or you exclude those and only use the others? From eq 7, it looks like you only use those values with high att scores. But why is this helpful? How does this calibrare the attention distribution?\n\nTable 1, 2: What exactly is \"Ours\" (without the calibration R_h and compression R_l)?", "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": "VltoraELPi", "reviewer": "Reviewer_KipP", "summary": "This paper proposes a method for training-free length extrapolation of LLM i.e. extending an LLM to process sequence longer than the sequence length it is pretrained on. The key idea is to split the input into chunks that fit in the LLM's context window and perform global attention over the chunks. While previous work (e.g. InfLLM) has also explored similar idea, this paper further proposes to mitigate \"attention bias\" by removing tokens within the chunk that receive (1) high attention scores (sink tokens) and (2) low self-information scores.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude for your fruitful suggestions, and for all your questions below!  \n\nQ1: **Minimal Performance Difference Between \"Ours\" and Other Methods in Token Eviction Settings.**\n- \"Ours\" implements the eviction scheme for the entire chunk's KV cache.\n- \"Ours-compression\" refers to further compressing the KV cache within the chunk. \n- \"Ours-calibration-compression\" attempts to recover performance further through calibration.\n\n\"Ours\" and \"Ours-compression\" refer to the methods of adding chunk eviction and parallel KV cache eviction, respectively. Generally, parallel KV cache eviction tends to degrade the performance of many models, so we hope to recover the performance lost during compression by using an attention distribution calibration mechanism, namely \"Ours-calibration-compression.\"\n\n\n\n\nQ2: **Difference Between \"Ours\" and InfLLM: Global Attention with Full vs. Subset of Chunks.**  \nWe need to clarify your misunderstanding of our method.\n\n- \"Ours\" only **applies attention to chunks in the priority queue**, unlike InfLLM, which retains all chunks in the CPU and causes high I/O overhead and slow prefill speeds by swapping the KV cache between the CPU and GPU. In fact, it can attend to all global chunks simultaneously.\n\n\n- InfLLM addresses the memory-bound issue during inference by retaining only the chunk representations, while \"Ours\" uses a chunk eviction strategy and parallel compresses the KV cache to increase chunk process throughput. **We mainly focus on the KV cache compression strategy in parallel chunk processing**\n\n\n\n\n\nQ3: **Analyzing the Benefits of Calibration and Compression vs. \"Ours\".**\n\nWe will start our analysis from a core motivation, which is the memory-bound issue in the parallel encoding and the attention bias issue aggravated by compression.. \n- “Ours“  \nDue to GPU memory limits, it's not feasible to store KV caches for many chunks at once. Offloading chunks to the CPU during parallel processing also introduces high I/O latency, making it impractical.  We propose a more general approach based on two principles:\n**Simplicity:** We use negative log-likelihood (NLL) to model the relevance between queries and chunks without designing extra representations. This reduces communication overhead—especially important in multi-GPU setups where I/O is the main bottleneck.\n**Efficiency:** Sorting in the priority queue only involves scalar comparisons with O(log n) time complexity, unlike heavier methods like InfLLM that use O(n²) retrieval operations.\n\n- “Ours-compression“  \nParallel KV cache eviction helps address memory limitations in parallel computation, but our analysis shows it worsens attention bias. To mitigate this, we introduced a simple attention calibration mechanism “**ours-compression-calibration**” for near-lossless compression, making our design effective.\n\n\n\nQ4: **Typo of equation 6.**\n\n- In Eq. 6, [·] represents the eviction operation, which means removing the indices in [·] from K_x.\n\n\nQ5: **Clarifying the Link Between Figure 3 Patterns and the proposed method.**\n\n- Observation1: Based on our observations, due to using almost the entire window length for parallel encoding, the model always exhibits a strong recency bias in the query chunk region.\n\n- Design1 : It indicates that the model relies on the tokens in the query chunk to make next token predictions, which inspired us to use the negative log-likelihood of the tokens in this region to measure the importance of the chunk.\n\n\n- Observation2: Another phenomenon is that the KV cache compression operation **exacerbates attention bias as shown in Figure 3**, as shown in the first image of Figure 5. \n\n- Design2 : Therefore, designing a calibration mechanism is necessary to mitigate the performance loss caused by exacerbated attention bias.\n\n\n\nQ6: **The performance discrepancy for Llama-3-8B-Instruct (8k) on LongBench may be due to different settings, while results for InfiniteBench align with InfLLM's Table 1.**\n\n- LongBench: For LongBench, we do not use the original hyperparameters reported in the InfLLM paper. Instead, we re-evaluated all baselines under a unified testing framework to ensure fair comparison. Specifically, we adopted the evaluation setup from the open-source repo[1], and ported that framework to the InfLLM codebase for consistency. This was done to eliminate inconsistencies in evaluation scripts, precision settings, and other hyperparameters.\nThe inference details\ntemperature=0, and num_beams=1, float16 precision.  \n- For InfLLM, we use the default hyperparameters as provided in their official code repository to evaluate on longbench.\n\n\n\n\n**Reference**:  \n[1] https://github.com/Zefan-Cai/KVCache-Factory.", "claims_and_evidence": "Experiments are conducted on multiple long-context datasets (LongBench, Infinite-bench and perplexity of NarrativeQA, showing that the proposed method outperform previously proposed methods (including methods that manipulate position encodings and similar chunk encoding methods like InfLLM).\n\nHowever, I find the evidence that the proposed calibration and compression methods is helpful to be relatively weak. For all the experiments (table 1, table 2). If I understand correctly, \"ours\" is the setting where all tokens are encoded in the parallel fashion, and \"ours-compression\" and \"ours-calibration\" correspond to setting where tokens are evicted. And in both tables the difference between \"ours\" and the other two methods are minimal (except for Llama-2-7B-chat-hf(4k) on Infinite-bench). \n\nFurther, the difference between \"ours\" and InfLLM since to be whether all the chunks are included in the global attention, or only some of the chunks are considered (InfLLM only uses subset of chunks to do global attention), which is not surprising as leveraging more information is more accurate.", "methods_and_evaluation_criteria": "The proposed benchmark datasets and baselines are suitable for the method.", "theoretical_claims": "I checked the theoretical claims on attention bias for parallel attention computation.", "experimental_designs_or_analyses": "The experiment settings make sense.", "relation_to_broader_scientific_literature": "This work contributes to the line of work which aims to enable language models to process text longer than their pre-training context window. While there are more language models nowadays that is trained to process very long context already, I think the direction is still an important.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "* I think it will be helpful to analyze the setting where the proposed calibration and compression method helps compared to \"Ours\". For instance, it seems like for `En.MC` and `R.KV`, \"ours-calibration\" improve upon \"ours\" more compared to the other tasks.\n\nTypo: \n* line 71 in Related work section \"reecent\" ==> \"recent\"\n* equation 6 -- if $R_{l}$ represents the indices corresponding to tokens to evict, doesn't $K_{x}[R_{l}]$ represent the key states to be evicted?\n\n* The text in Table 5 is too small and uneasy to read.", "questions_for_authors": "* While the attention analysis in Section 4 is nice, it is unclear to me what's the connection of the patterns observed in figure 3 to the proposed methods aside from the idea that tokens with high attention scores are removed?\n* For Llama-3-8B-Instruct (8k) performance on LongBench, it seems like some of the numbers for InfLLM and FullKV are different for the numbers reported in the [InfLLM paper](https://arxiv.org/pdf/2402.04617) Table 5 (e.g. NarrativeQA and MF-en), is the setting different causing the discrepancy? The results for InfiniteBench seems to align with that in InfLLM's Table 1.", "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": "8rh8QZRTVq", "reviewer": "Reviewer_GVLE", "summary": "This paper introduces ParallelComp, which the authors claim to be able to extend the context window of off-the-shelf LLMs from 4K to 128K tokens while maintaining computational efficiency. The authors address the critical challenge of attention sink phenomena in parallel attention mechanisms, where models disproportionately focus on initial/recent tokens, impairing long-context understanding.\n\n\n## Update After Rebuttal\n\nI have read the authors' rebuttal and decided to keep the current positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude for your fruitful suggestions, and for all your questions below!  \n\nQ1: **The authors conduct a thorough comparison against existing length extrapolation methods for tasks such as single/multi-document QA. However, these tasks could potentially benefit from RAG without requiring long-context extrapolation in LLMs. Would it be possible to compare the proposed approach with leading RAG methods such as [1,2]?**\n\n\n| Model|QM|QASP|MSQ|HQA|MFQA|Average|\n|-----|------|------|------|------|------|---------|\n| Llama3-ChatQA-2-8B | 11.64| 28.85| 27.81| 53.81| 51.02| 34.63   |\n| w/ RAG|13.20|28.85|29.77|57.81|51.15|36.16|\n| ours-llama3|24.18| 39.05|33.25|49.58|42.66|37.74|\n**Table 1: Experiments on Longbench** \n\n\n| Model| kv_retrieval | numbe_string | passkey | En.MC | Average |\n|-----|--------------|---------------|---------|-------|---------|\n| ours-llama3|92.80| 99.83|100.00|54.59|86.81|\n| Llama3-ChatQA-2-8B|72.00|100.00|100.00| 64.19|84.05|  \n**Table 2 Experiments on InfiniteBench.** \n\n- Since Llama3-ChatQA-2-8B produces \"Not Available\" results on InfiniteBench when using RAG (w/ RAG), we only compared the results of Llama3-ChatQA-2-8B in Table 2.  \n- The above shows the comparison results between our method and the representative RAG method, ChatQA 2 [2]. It is clear that our method performs well compared to the strong RAG baseline, especially on the Longbench dataset.\n- The performance collapse of the RAG method on InfiniteBench is an unknown phenomenon, which also demonstrates the robustness of our method.\n\n\n\n\n\n\nQ2: **Does the paper provide a detailed description of the calibration data used? Have they analyzed stability across different context sources (e.g., code vs. narrative text)?**\n- We calibrated the attention scores based on Equation 7, using an online method to evict  anomalous tokens, so there is no need to sample data in advance for calibration. \n- We found that in code tasks, the attention distribution of the intermediate layers are more sensitive to calibration, while in text tasks, such as in-context learning, the attention distribution of the earlier layers are more sensitive to calibration.\n\n\n**Reference**:   \n[1] RAPTOR: recursive abstractive processing for tree-organized retrieval.  \n[2] ChatQA 2: Bridging the Gap to Proprietary LLMs in Long Context and RAG Capabilities.", "claims_and_evidence": "1. Parallel Compression Framework. The authors propose a chunk-based architecture with parallel local attention computations and strategic KV cache eviction. This enables efficient processing of ultra-long contexts on a single A100 GPU.\n\n2. Attention Bias Analysis & Calibration. The authors have conduct a systematic identification of three attention bias patterns in parallel mechanisms.", "methods_and_evaluation_criteria": "Regarding the methods, the proposed methods align well with the core challenge of long-context extrapolation. The parallel attention mechanism and chunk eviction strategies are designed to address the memory/computation bottlenecks of long sequences. In the meanwhile, compatibility with flash attention is well attended to.\n\nThe evalution seems comprehensive and appropriate for me. I am just wondering whether the authors have considered testing their method on more cross-lingual datasets?", "theoretical_claims": "The overall theoretical framework provides useful explanation about parallel attention collapse.", "experimental_designs_or_analyses": "1. (Apologies if this question is somewhat naïve, as I am extremely unfamiliar with this field.) The authors conduct a thorough comparison against existing length extrapolation methods for tasks such as single/multi-document QA. However, these tasks could potentially benefit from RAG without requiring long-context extrapolation in LLMs. Would it be possible to compare the proposed approach with leading RAG methods such as [1,2]?\n\n\n2. Does the paper provide a detailed description of the calibration data used? Have they analyzed stability across different context sources (e.g., code vs. narrative text)?\n\n\n---\n[1] RAPTOR: recursive abstractive processing for tree-organized retrieval.\n\n[2] ChatQA 2: Bridging the Gap to Proprietary LLMs in Long Context and RAG Capabilities", "relation_to_broader_scientific_literature": "This work focuses on LLM length extrapolation, an important research direction with numerous influential studies. Given that the proposed approach is training-free, its contribution appears particularly meaningful.", "essential_references_not_discussed": "As I am not well-versed in this area, I have not identified any critical missing references.", "other_strengths_and_weaknesses": "See above", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "gcs8vfoSQA", "reviewer": "Reviewer_P8gm", "summary": "ParallelComp processes the input sequence chunk by chunk independently. Therefore, they can parallel process the attention matrix, except for the last chunk of attention.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank for your suggestions!\n\nQ1：**Key differences**  \n\n|Method|NARR|QAS|MUlT|HOPT|2WKI|MUS|GOV|QMS|NEWS|TREC|TRIV|SSM|PCNNT|PREN|LCC|REP|AVG|\n|------|----|---|----|----|----|---|---|---|----|----|----|---|-----|----|---|---|----|\n|APE|23.63|39.11|50.06|49.47|43.70|25.99|27.78|22.79|11.22|43.50|90.17|9.79|0.50|59.00|23.93|24.28|34.06|\n|Star|3.74|11.90|24.81|14.17|14.37|8.19|34.90|22.54|27.11|65.33|87.84|43.71|3.80|65.17|50.54|45.40|32.72|\n|ParallelComp|29.45|45.98|50.67|48.36|46.56|23.32|32.60|24.29|27.34|38.50|86.72|25.93|0.05|95.00|14.15|21.42|38.15|\n**Table 1:** Comparison with other methods.  \n\n- We focus on the **memory-bound** encountered during the implementation of length extrapolation.\n- ParallelComp introduces a **two-stage compression strategy**: chunk-level kv cache eviction followed by intra-chunk compression. **Attention calibration** is applied to reduce the performance loss caused by compression. This enables both context window extension and improved inference throughput. \n- **APE** consists of a shared prefix to reduce distributional differences, a low-temperature mechanism to sharpen attention, and a scaling factor to adjust for temperature-induced changes. It aims to align the attention patterns of parallel and sequential encoding.\n- **StarAttention** targets models with native long-context support. It recalculates attention for each chunk at every step, while our method computes attention only once at the prefill stage and reuses the **compressed**  KV cache for generation—greatly improving efficiency.\n\n\n\n- We conducted a comparative experiment, with the code implementation based on [1,2]. However, APE lacks prompt design, Star is missing the Longbench experiment, and hyperparameter configurations are absent in both. For APE, we set the temperature to 0.5 and the scaling factor to 0.8. For Star, the chunk size was set to 2K. In our approach, we reuse these 6K position encodings for length extrapolation. Base model is Llama-3.1-8B-Instruct.\n\n\n\nQ2: **Supplementary baseline**\n\n\n\n|Method|NARR|QAS|MUlT|HOPT|2WKI|MUS|GOV|QMS|NEWS|TREC|TRIV|SSM|PCNNT|PREN|LCC|REP|AVG|\n|------|----|---|----|----|----|---|---|---|----|----|----|---|-----|----|---|---|----|\n|Llama3.1|27.80|44.25|49.46|47.86|40.54|23.64|32.64|22.90|26.90|38.00|88.44|25.64|2.02|92.00|10.35|18.64|36.94|\n|ParallelComp-Llama3.1|29.45|45.98|50.67|48.36|46.56|23.32|32.60|24.29|27.34|38.50|86.72|25.93|0.05|95.00|14.15|21.42|38.15|\n|Qwen2.5|27.83|41.31|50.41|53.52|44.68|30.00|33.38|24.01|25.40|71.00|86.10|39.91|7.25|100.00|6.86|7.88|40.60|\n|ParallelComp-Qwen2.5|28.42|42.24|50.54|56.26|42.02|28.25|33.43|23.20|25.20|71.50|89.21|41.84|5.00|93.50|20.73|13.34|41.54|\n**Table 2:** Longbench.\n\n|Method|PS|NUM|KV|EN.MC|MATH|CODE|AVG|\n|------|---|---|--|-----|-----|-----|----|\n|Llama3.1|5.59|26.25|18.60|32.86|31.52|22.56|26.36|\n|ParallelComp-Llama3.1|100.00|83.56|88.60|66.38|37.14|22.08|59.55|\n|Qwen2.5|59.32|58.31|33.80|61.39|85.71|23.76|53.72|\n|ParallelComp-Qwen2.5|100.00|76.27|63.40|66.86|92.57|24.75|70.64|\n**Table 3:** Infinitebench.\n\n- The KV cache management mechanism of Gemma2 is significantly different from that of LLaMA and Qwen models, so we have not yet fully implemented it. If we have more time, we promise to submit the test results of EXAONE 3.5 and Gemma2. We promise to provide it in a future version of the paper. \n\n\n- We conduct experiments on Llama3.1 and Qwen2.5 using Longbench and InfiniteBench under the same 24K KV cache budget. While other models use 24K position encodings directly, our approach leverages extrapolation techniques to reuse 6K position encoding. Others use the original length.In the experiment, it is found that whether the prompt word(such as “
” for Llama3.1) is used has a great influence on the performance, and we make a comparison in the case of the prompt word.\nIt can be seen that, under the same 24K KV cache size budget, our approach still outperforms other models that **do not implement extrapolation**, especially on the InfiniteBench dataset.\n\n\n\nQ3: **Necessity to sparsify attention mechanisms**\n\nBased on our observations, certain tokens at specific layers do indeed contribute to improving the model's performance:\n\n- In early layers, attention biases are crucial for context understanding—removing them harms performance.\n- For code tasks, biases in middle layers matter most—removal also leads to performance drops. \n- The attention sink boosts retrieval in early layers but hurts performance in later layers.\n\nHowever, in other layers, **these attention biases significantly hinder the model's ability to process long contexts**. Therefore, removing these anomalous tokens can improve the model's performance.\n\nQ4: **Others**\n\n- We will consider your suggestions and incorporate additional supplementary materials into future versions of the paper, especially the release of the open-source code.\n\n\n\n**Reference**:\n\n[1]https://github.com/Infini-AI-Lab/APE  \n\n[2]https://github.com/NVIDIA/Star-Attention", "claims_and_evidence": "No, the supporting evidence is not clear and not well connected to their claims.", "methods_and_evaluation_criteria": "No, I think the evaluation of the calibration and compression variant is not well justified because the performance looks pretty similar between whole variants in Llama 3.", "theoretical_claims": "Yes.\n\nHowever, I am concerned that Parallel Attention Bias is necessary to sparsify attention mechanisms.", "experimental_designs_or_analyses": "Using Llama 2 looks like a bad choice in 2025. At least, I think we should use Gemma 2 or EXAONE 3.5 for short context models.\n\nI wonder how performance is good in long context language models such as llama 3.1. Since the KV cache memory is usually a more significant problem rather than latency in most scenarios (up to 1M token context), we can compare this method to long context LLMs that use the same amount of KV cache memory with ParallelComp. \n\nI wonder how performance is good when we apply ParallelComp to long context LLM such as Llama 3.1 and Qwen 2.5. Llama 2 and 3 are pretty old and short at this point.", "relation_to_broader_scientific_literature": "I am not sure the key contribution of this work (chunkwisly parallel encoding) is scientifically impactful.\n\nI am not sure if Parallel Attention Bias is effective in terms of downstream tasks.", "essential_references_not_discussed": "StarAtteniton (https://arxiv.org/pdf/2411.17116) and APE (https://arxiv.org/pdf/2502.05431) look extremely similar to this work. I strongly suggest that the authors compare ParallelComp with those baselines.", "other_strengths_and_weaknesses": "Please refer to other sections.", "other_comments_or_suggestions": "In the abstract, I think we need to avoid the bold text if it is unnecessary.\n\nTables 1, 2, 3, 4, and 5 are too tiny text. Please revise the overall formatting significantly.\n\nPromoting performance between GPT4 might be overclaiming. The promotion that ParallelComp can make 8B better than GPT4 may lead to misunderstanding that this method improves the long context performance. I feel afraid of such overclaims, so I gently ask you to think about this once more.\n\nIn Tables 1 and  2, I think we should show the average length of the dataset or 99% of the length of the dataset because the maximum length might show only the outliers.\n\nIn Figure 2, the terms `Key` and `Value` should be plural (-s).", "questions_for_authors": "Please refer to the upper sections.", "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:

Meta-review: This paper introduces a training-free approach to generalizing LLMs to longer context lengths. The method computes local attention on chunks of the sequence, and uses this to evict tokens and chunks that have a low score according to their metric. Finally, the remaining chunks undergo global attention.

* Reviewers appreciate that the approach is training-free but still leads to performance improvements on length extrapolation, while improving efficiency and memory usage. 
* One of the reviewers encouraged the authors to include comparisons to more recent models, and the authors have included in their response a comparison of their approach applied to the Llama 3 and Qwen models. We encourage the authors to include these in the final submission with appropriate discussion.
* We additionally encourage the authors to address parts the reviewers found unclear, and to include the comparison to STAR and APE. We recognize these were not published before the submission deadline, but discussing them and comparing to them will make this a stronger paper that is easier to contextualize with the literature.

Based on the reviews and author responses, we recommend this paper for acceptance.
Decision: Accept (poster)