Curse of High Dimensionality Issue in Transformer for Long Context Modeling
Authors: Shuhai Zhang
Zeng You
Yaofo Chen
Zhiquan Wen
Qianyue Wang
Zhijie Qiu
Yuanqing Li
Mingkui Tan
Venue: ICML 2025 poster (2025)
Keywords: Large language models
Transformer
Primary area: theory->deep_learning

Abstract: Transformer-based large language models (LLMs) excel in natural language processing tasks by capturing long-range dependencies through self-attention mechanisms. However, long-context modeling faces significant computational inefficiencies due to redundant attention computations: while attention weights are often sparse, all tokens consume equal computational resources. In this paper, we reformulate traditional probabilistic sequence modeling as a supervised learning task, enabling the separation of relevant and irrelevant tokens and providing a clearer understanding of redundancy. Based on this reformulation, we theoretically analyze attention sparsity, revealing that only a few tokens significantly contribute to predictions. Building on this, we formulate attention optimization as a linear coding problem and propose a group coding strategy, theoretically showing its ability to improve robustness against random noise and enhance learning efficiency. Motivated by this, we propose Dynamic Group Attention (DGA), which leverages the group coding to explicitly reduce redundancy by aggregating less important tokens during attention computation. Empirical results show that our DGA significantly reduces computational costs while maintaining competitive performance.

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Shuhai Zhang + 12 Zeng You 13 Yaofo Chen
Zhiquan Wen
Qianyue Wang' Zhijie Qiu'
Yuanqing Li
Mingkui Tan 14
Abstract
hibiting emergent abilities like few-shot learning and com- plex reasoning (Schaeffer et al., 2023). These capabilities stem primarily from their ability to model long-range depen- dencies through self-attention (Vaswani, 2017; Schaeffer et al., 2023). However, a key challenge in long-context modeling the redundancy in attention computation: while attention weights are often sparse, meaning many tokens contribute minimally predictions, all tokens still consume equal computational resources. This substantial inefficiency raises the question: how can we reduce redundant computa- tions without sacrificing model performance?
Transformer- large language models (LLMs) excel in natural language processing tasks by capturing long-range dependencies through self- attention mechanisms. However, long-context modeling faces significant computational ineffi- ciencies due to redundant attention computations: while attention weights are often sparse, all to- kens consume equal computational resources. In this paper, we reformulate traditional probabilis- tic sequence modeling as a supervised learning task, enabling the separation of relevant and irrele- vant tokens and providing a clearer understanding of redundancy. Based on this reformulation, we theoretically analyze attention sparsity, revealing that only a few tokens significantly contribute to predictions. Building on this, we formulate attention optimization as linear coding prob- lem and propose a group coding strategy, theo- retically showing its ability to improve robust- ness against random noise and enhance Iearn- ing efficiency. Motivated by this, we propose Dynamic Group Attention (DGA), which lever- ages the group coding explicitly reduce redun- dancy by aggregating less important tokens dur- ing attention computation. Empirical results show that our DGA significantly reduces computational costs while maintaining competitive performance. Code is available at https: /github. com/ boli boL.xx..ww//Dyyaaacccroottttttt
Existing approaches (Xiao et al., 2024; Han et al., 2023; Chen al., 2024) often tackle this issue by discarding some tokens to simplify attention computations and reduce costs. However, while effective in specific scenarios, such methods risk disrupting token interactions, especially in tasks requir- ing comprehensive context understanding, e.g., question answering (Lu et al., 2022: Singhal et al., 2025) and docu- ment summarization (Cao et al., 2017; Pasunuru et al., 2021). Token removal may lead to incomplete or inaccurate con- text comprehension, impairing model performance. Thus, the key challenge is how minimize redundant attention computations while maintaining critical token interactions.
Traditional probabilistic sequence modeling, such as au- toregressive models (Vaswani, 2017; Huang et al., 2018; OpenAL, 2023), treats long-context redundancy implicitly by processing the entire context as a block during text-token prediction, making it difficult analyze the above issue. To better understand and analyze redundancy, we reformu- late the probabilistic sequence modeling supervised learning task in Section 3. This reformulation enables us to separate relevant and irrelevant tokens and provides a clearer view of redundancy, inspiring us to develop more efficient methods for long-context modeling.
1. Introduction
Transformer-based large language models (LLMs) (Touvron et al., 2023a;b) have advanced in various natural language processing tasks (Brown et al., 2020; Wei et al., 2022), ex-
To gain a deeper understanding of the redundancy in long context, we provide theoretical analysis of the sparsity of attention weights in transformers in Section 4. Our analy- sis shows that only a small subset of tokens significantly contributes to the target representation, while many tokens offer little value to overall model performance, leading to inefficient use of computational resources. To better un- derstand this issue and inspire new attention, we formulate
"Equal contribution 'South China University of Technology "Pazhou Laboratory *eng Cheng Laboratory Keyy Laboratory of Big Data and Intelligent Robot, Ministry of Education. Correspon- dence to: Mingkui Tan <mingkuitan scut.edu.cn>.
Proceedings of the 4 International Conference on Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
attention optimization as linear coding problem (Ryan & Lin, 2009). In long-context modeling, the sparsity of attention weights often causes learning unstable and inef- ficient (Lounici et al., 2011; I; Huang & Zhang. 2010). To address this, we propose a group coding strategy, which aggregates tokens into meaningful groups. Our theoretical analysis demonstrates that the group coding is more robust to random noise and offers a more stable and efficient learn- ing process. This suggests that grouping mechanisms can effectively reduce redundancy in long-context modeling, offering new perspective on transformer optimization.
and offers a more stable and efficient learning process.
Dynamic group attention for long-context modeling: We propose Dynamic Group Attention (DGA) to address re- dundancy in attention computation for long-context mod- eling. DGA dynamically aggregates less important tokens into meaningful groups, significantly reducing computa- tional costs while preserving critical token interactions. Empirical results on diverse long-context tasks demon- strate that our DGA significantly reduces computation while maintaining competitive performance.
To further exploit the group mechanism to reduce com- putational redundancy in LLMs, we propose a Dynamic Group Attention (DGA) mechanism, which explicitly re- duces redundancy in attention computation without sacrific- ing critical token interactions, as detailed in Section 5. The core idea of DGA lies in dynamically grouping and aggre- gating less important tokens during attention computation, as illustrated in Figure and Algorithm 1. Specifically, 1) DGA identifies tokens that contribute minimally to the atten- tion process, grouping them together and aggregating their representations before performing the attention operation. This reduces the number of individual tokens involved in attention calculations, thereby significantly reducing com- putational complexity. 2) Crucially, the more important tokens, which are vital for maintaining the model's 's perfor- mance, are handled individually, ensuring their interactions remain preserved and accurately represented. 3) Further- more, DGA introduces complementary keys and values for tokens restricted from accessing group information due to the autoregressive nature of LLMs. By focusing the atten- tion mechanism on the most relevant tokens and reducing the redundancy of less informative ones, DGA not only reduces redundancy computation but also maintains essen- tial token interactions. Empirical results demonstrate the superiority of our DGA for long-context modeling.
2. Related Work
Efficient transformer. Early efforts focus on introducing sparsity into attention mechanisms. For instance, Reformer (Kitaev et al., 2020) uses Locality Sensitive Hashing (LSH) to group similar tokens into buckets, reducing computational demands. Similarly, Longformer (Beltagy et al., 2020) com- bines global attention for key tokens with local sliding win- dow attention to handle longer texts. Big Bird (Zaheer et al., 2020) further integrates global, local, and random attention strategies to capture both long-range and local contexts.
Another line of research approximates attention mechanisms to achieve linear complexity. Performer (Choromanski et al., 2021) introduces a kernel-based approximation of softmax attention, reducing memory and computational costs. Simi- larly, Linear Transformer (Katharopoulos et al., 2020) and RetNet (Sun et al., 2023) reformulate self-attention as a linear dot-product of kernel feature maps. Additionally, Sun et al. (2021) Iearn parameterized hash functions for queries and keys to enhance efficiency. HyperAttention (Han et al., 2024) refines attention approximation by measuring prob- lem hardness with fine-grained parameters.
Recent works further advance long-context modeling. Lon- gLoRA (Chen et al., 2024) partitions tokens into groups and shifts group partitions to facilitate inter-group com- munication for modeling efficiency. StreamingLLM (Xiao et al., 2024) and LM-Infinite (Han et al., 2023) prioritize attention the initial and final tokens, ignoring intermedi- ate tokens optimize attention. KVMerger (Wang et al., 2024b) focuses on KV cache compression via Gaussian- kernel-based Key clustering but ignores attention compu- tation redundancy. Some methods focus on dynamically adapting sparsity patterns. For instance, MInference (Jiang et al., 2024) identifies three unique sparse attention patterns and dynamically applies them during inference.
We summarize our main contributions follows:
A supervised reformulation of sequence modeling for redundancy analysis: We reformulate the sequence model- ing as supervised learning task, enabling the separation of relevant and irrelevant tokens in long- bong-context modeling. It provides clearer understanding of redundancy and in- spires more efficient methods for long-context modeling.
Theoretical analyses of attention sparsity and group cod- ing strategy: We theoretically analyze the sparsity of at- tention weights in transformers, showing that only small subset of tokens significantly contributes to the target representation. To inspire new attention, we formulate at- tention optimization as linear coding problem. Based on this, we propose a group coding strategy and thcoretically show that the group coding is more robust to random noise
Despite these advancements, such methods often rely on fixed sparsity patterns, which may sacrifice important token interactions. This can degrade performance in tasks re- quiring fine-grained interactions. Recently, CCA-Attention (Chen et al., 2025) leverages grouped aggregation of intra- token interactions combined with local sliding windows for
2

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
efficient attention. In contrast, our method dynamically iden- tifies critical tokens and selectively aggregates only unim- portant tokens while preserving essential interactions via complementary tokens. This ensures adaptive redundancy reduction without sacrificing key contextual dependencies.
ters more irrelevant information, leading to inefficiencies in both computation and optimization. Traditional sequence modeling treats the entire context as a monolithic block due to its conditional modeling paradigm, making it diffi- cult to identify or eliminate redundant tokens. Moreover, the implicit handling of redundancy in traditional sequence modeling (e.g., self-attention (Vaswani, 2017)) limits the ability to optimize computational resources effectively.
Long-context modeling. Extending the context window of LLMs to handle long sequences critical for tasks re- quiring deep understanding. Recently, A plethora of work has attempted to extend the context length of LLMs (Chen et al., 2023; Yen et al., 2024; Mohtashami & Jaggi, 2023; An et al., 2024; Tworkowski et al., 2023). For instance, Position Interpolation (Chen et al., 2023) linearly down- scales input position indices to fit within the original context window size, enabling RoPE-based L.MSs to handle longer sequences. Yen et al. (2024) introduce a small encoder to process long inputs in chunks, allowing frozen decoder to cross-attend to additional contexts, thus extending the context length without modifying the core architecture. In contrast, An et al. (2024) propose Dual Chunk Attention, en- abling models like Llama2-700 to support context windows exceeding 1 10,000 tokens without extra training. by decom- posing long-sequence attention into chunk-based modules that capture both intra-chunk and inter-chunk dependencies.
3.2. Supervised Reformulation for Sequence Modeling
Recall that next-token prediction (Zhang et al., 2024) in traditional sequence modeling is x;=arg maxy P(x(x<s). We can reformulate it y= arg maxy P(y[C(y)) with C(y) {x1, X2,......... X;- } representing the context pre- ceding the target token y. This can be interpreted as pre- dicting label based on the input C(y)). resembling the supervised learning mechanism (Hastie et al., 2009).
Building on this insight, we formalize probabilistic sequence modeling as a supervised learning task. Given a training corpus (CC(y:). (((y)).)))))))) y=)) where y;Ev is token from the vocabulary V and C(y:) is its context, the task is to maxi- mize the likelihood of predicting conditioned on all C(ys):
Other approaches focus on modifying position embeddings to extend context length, such as positional skipping (Zhu et al., 2024), Yarn (Peng et al., 2024), and RoPE extrapo- lation (Liu et al., 2024b). While these methods primarily address position embedding limitations, our approach is or- thogonal, focusing on reducing computational redundancy through dynamic token grouping and aggregation.
max 8
II yEV,C(y)
Poly
Denoting f as the feature extractor in the last layer of the LLM, the probability Po(y)C(y)) can be reformulated as
exp(z*)
Poly)C(y)) = E exp(z,)
(3)
3. Sequence Modeling to Supervised Learning
where k is the index of the token in the vocabulary, and z = w T (f(((y)) E R represents the logits of y. Here, w E Ædxk is the weight matrix of the final fully connected layer, and K = | is the vocabulary size. This is a standard supervised learning paradigm (Hastie et al., 2009; Nasteski, 2017). Further discussion on the relations between sequence modeling and supervised learning is in Appendix B.
3.1. Traditional Probabilistic Sequence Modeling
Traditional probabilistic sequence modeling (Vaswani, 2017; Wang et al., 2024a) in language models typically involves generating a token sequence by predicting each next token based on previously generated ones. Given token sequence {x1, X2,.... . X1) } the training objective for model 0 is to maximize the likelihood of the entire sequence:
Remark 1. 1) Ideally. for each target token y, it is crucial to collect all relevant contexts C(y) for accurate prediction. 2) To train promising model, it is essential to gather the comprehensive context associated with each y. This can be achieved by collecting longer corpora (Fu et al., 2024). However, longer contexts inevitably introduce redundant tokens, leading to unnecessary computational overhead and optimization challenges (Altman & Kraywinski, 2018).
max
Pxx X2, XX.., x;-)). #
During the generation, the model selects the most likely token at each step via x;= arg maxx P(x This au- toregressive process iteratively applies the same mechanism until the desired sequence length is reached.
A Advantages of supervised sequence modeling. The su- pervised sequence modeling provides more structured ap- proach to understanding long-context redundancy, although they are theoretically equivalent. It allows us to separate the context C'y) into relevant and irrelevant parts, allowing a more focused examination of the redundancy issue. By
Limitations of probabilistic sequence modeling for anal- ysis. While this approach ensures coherent and contextually relevant token generation, it struggles with long sequences. As the sequence length increases, the model often encoun-
3

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
casting the problem as supervised learning, we can precisely determine which tokens in C(y) are vital for predicting y, and which tokens may be discarded or aggregated.
where A, softtmaax /V/). This implies that the at- tention of token is computed as linear combination of the values of other tokens, weighted by the importance obtained from the dot product of its query and the keys of other tokens. This mechanism enables the model to consider long-range dependencies for long-context modeling.
Redundancy in long contexts. From the above view, the context C(y) with redundancy can be formalized as
IR C(y) = (x} X2
X3
X X5
XL
x J. (4)
Redundancy in attention weights. To analyze the inher- ent redundancy in long-context modeling within LLMs, we focus the representation of the context C(y) in sim- plified model: a single-layer transformer with single-head attention. Given a sequence C(y) E Rixdd denoted as x- xx.] for simplicity, the representation of the last token f(X) can be formulated as:
where xR denotes relevant tokens that contribute to predict- ing the target token x, and xII denotes irrelevant tokens that introduce unnecessary noise computation.
Challenges. The redundancy becomes particularly pro- nounced in transformers, which process all tokens with equal computational cost. However, not all tokens con- tribute equally to predicting y: many tokens in C'y) offer negligible or redundant information, inflatiig computational requirements and impairing optimization efficiency. This motivates to analyze the redundancy within C(y) and find more effective methods for long-context modeling.
f(x) = 01 V1 + 02 V2 + ................................ +a V, + +ay (7)
where aj = E exp(Q. K.) represent the j-th weight.
exp(Q K2)
The attention weights aj determine the contribution of each token's value vector V, to the target representation f f(X). However, in long sequences, significant portion of the to- kens in the context are irrelevant to the target representation as in Eqn. (4), resulting in sparse and concentrated attention distributions, i.e., a few weights a, are significantly greater than most weights. To facilitate understanding, we analyze the sparsity of attention weights in the following:
4. Redundancy in Self-attention: From Mechanism to Coding Perspective
Section 3 reformulates long-contexs modeling as a super- vised learning task (Eqn. (2)), which explicitly separates relevant (critical for predictions) and irrelevant (redundant for context) tokens. This formulation provides a structured foundation to investigate how redundancy manifests in atten- tion computations and motivates our theoretical exploration from both the mechanism and coding perspectives.
Theorem 1. (Sparsity on attention weights) Consider p E (1/L, 1] as a sparse rate, we say that the weight a is p sparse when there exists at least one probability greater than 1/(L)). Let = KQ, E R then the probability of being p-sparse Poparse (L,, p) is given by
4.1. Redundancy in Self-attention Mechanism
P Paparse Peparse(L, 2 mmx 1 [Phead Peasi' a>0
(8)
Self-attention in LLMs. Self-attention (Vaswani, 2017) is key mechanism in LLMs that allows the model to assign the importance of different tokens for long-context modeling. Formally, given input XxR self-attention is defined as:
where Phead = Pfcxp((s) S x) with j being some index of a and Prait P((Lp 1)x S. Ehj exp(Ex))-
Remark Given and p. the probability Pspprse (L, p) is influenced by the interplay between Phead and Proit that are functions of x. A larggr x increases Phond but decreases Ptait. leading to a balance where PheadPPast 1.1. For suf- ficiently large L, the exponential amplification of L sup- presses Peatt Puastfurthrr ensuring a large P Paporee (L, p).
QK
Att = softmax
V,
(5)
Vd
where Q-XWQ, K-XW*, and V-XWV repre- sent the query. key, and value matrices, respectively. Here, WQ, WK W E gaxd are learnable projection weights and is the dimensionality of the token embed- dings. For simplicity, we denote the attention weight as A-softmax QK /Vd), which captures the pairwise rel- evance between tokens, determining how much influence of each token on the representation of the other tokens. To facilitate the understanding of the attention mechanism, we rewrite the attention of i-th token separately:
Peporee (L, p) rigorously quantifies how spar- sity intensifies with increasing context length L. It reflects a model's inherent ability to prioritize critical tokens across diverse contexts, e.g., Peparee (L. p) evaluated on xXx model rises sharply for p=0.01 as L grows (see Figure 2(b)). Cru- cially, p-sparsity can be aggregated over multiple sequences to compute the average sparsity level (see Section 6.2), pro- viding model-level characterization of sparsity that gener- alizes beyond individual instances. This metric serves as a unified approach to evaluate and compare the efficiency of attention mechanisms in long-context modeling.
Remark 3.
1. Att: Σ j=1
V Rxd i= I,...,L
(6)
4

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
The sparsity of implies that only few tokens in the con- text contribute meaningfully to the target representation. While this sparsity aligns with the nature of self-attention, the redundancy in the imput context still increases the compu- tational burden during training, as all tokens are processed equally regardless of their relevance. This not only increases training time but also impairs optimization efficiency.
Problem 2. (Group coding problem for self-attention)
min
9
y
5
S.L.
g
Ggl=1,
2y>0.
9=1
9
JEGg
9=1
(10)
This group mechanism not only reduces the dimensionality of optimization but also reduces the redundancy observed in the attention. Aggregating tokens into meaningful groups can effectively compress redundant information and exploit the shared structure within the context. We summarize the advantages of this approach as follows:
4.2. Redundancy Analysis from Coding Perspective
In this work, we aim to seek an effective mechanism to alleviate the issue of attention redundancy for long-context modeling. Inspired by the form in Eqn. (7), we simplify the optimization process of a transformer into linear coding problem (Ryan& & Lin, 2009). This enables us to investigate the sparsity and redundancy of attention weights and in- spires us to develop more efficient optimization approaches. Specifically, we will show how grouping mechanisms can reduce redundancy while improving optimization efficiency. Problem 1. (Linear coding problem for self-attention)
1) Improved Robustness to Noise: nism smooths out the impact of random noise by averaging over multiple tokens in the same group. Mathematically. as shown in Theorem 2, the variance of weight changes is reduced by a factor of 1 1/m², where m is the group size.
The grouping mecha-
Theorem 2. Assume the weights before normalization are à obtained by the product of the query and key matrix, and explxs)
aj = Σt "1=,xxx(a;)) Consider a Gaussian noise Aā ~ ((, o 02I being added into à and each group size being Ggl = m, the variance of the weight changes obtained via group coding in Eqn. (2) can be reduced by 1/m².
min Σ agv, V
1, a3 0.
(9)
wherey y is the embedding of the target token.
2) Accelerated Optimization: Most weights in long- context modeling are relatively small (see Theorem 1), mak- ing most gradient contributions also small; The group opti- mization reduces both the optimization dimension and gradi- ent sparsity while enhancing stability. Theorem 3 shows that the group coding reduces the condition number (Edelman, 1988) of the objective function, enhancing convergence of the optimization, as verified in Section 6.3.
In this formulation, oj represents the contribution of the j-th token's 's value vector V, to the target representation, and its constraints are attributed to the softmax in the attention. Here, we consider each embedding y of the target token in the vocabulary and the parameters of V, as fixed, simpli- fying the analysis of transformer optimization using linear coding techniques (MacKay, 2003; Ryan & Lin, 2009).
Due to the sparsity property established in Theorem 1, the attention weights a focus on a few key tokens, rendering most of the context redundant. However, this redundancy challenges optimization: while sparse weights are beneficial, achieving stable and efficient learning is often hindered by noise sensitivity and overfitling to irrelevant tokens (Lounici et al., 2011; Huang& & Zhang, 2010).
Theorem 3. Denote H and H as the Hessian matrix of the optimizations in (1) and (2), respectively. Let ro(H) = Amax (H) /min (H) be the condition number (Edelman, 1988) of H, where Amux and Amin are the maximum and
minimum eigenvalues of H, respectively. Consider each group size |G (Gyl=m, Amin (an (H)>0 and Xaiin Ami (H)>0, we have
x(H)) S k(H)).
(11)
One naive approach is to add some penalties during opti- mization. Unfortunately, each context C(x) has its optimal weight within the whole tokens of the context. To address this, benefiting from the group sparsity (Huang & Zhang, propose group coding
Through the lens of the group linear coding, we highlight the redundancy in the long context can be mitigated by structured grouping. This approach not only reduces the computational overhead but also enhances model robustness and optimization efficiency, offering a feasible way to man- age sparsity and redundancy in transformer optimization.
2010; Lounici al., 2011), strategy, reducing the inherent redundancy by partitioning the attention weights a into & groups, i.e., ā E R* Each group shares a common weight, effectively pooling the con- tributions of grouped tokens. Let GI.....C Gb denote the index sets from the token indices I = {1...., L)) where = د Gg and G.NG, = for Vi + j. Formally, define the group weight as a, = 1 Eiea, a; The optimization problem is then reformulated as:
5. Dynamic Group Attention Mechanism for Long-context Modeling
iG,
Theorems 2 and 3 show the robustness and optimization ef- ficiency of group coding in reducing redundancy, inspiring
5

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Focal tokens
Non-focal tokens
Aggrogated keys
Complemertted kays
K/
kf
K"
KC"
K: Kg
Kg K, Kg K2 Kg Kg Kg
Kg
K,
K,
Kg
Kg
Kg
K,
Kg
Kg
K, Kg [K]
Kg
Kg
K,
K,, [KT
KK] KKG
KG KS
42
11
01
K2
Q:
0:
K,
0
9a
Q
0,
Rearrange
Groupe & Aggrogate
Q4
Complement Q+
0.
0.
Q:
Ks.
0:
Q
Q6
0-
0-
0-
Q-
Kg
0g
Qn
0.
0+
Qu
1/2
1.
V/6
112
V/5
Ve
V/g
V/6 V, V/g VV V.2
V/2
V2 VS vg
A Aguregated values
Complommeted values
Figure 1. Overview of the proposed DGA attention. The DGA attention dynamically adjusts the computation based on token importance. First, DGA moves the key-value (KV) pairs of important tokens to the front (denoted as K/ and V²). For less important tokens, DGA groups and aggregates their KV pairs with group size m (denoted as K" and V*). Finally, DGA introduces complementary KV pairs (denoted K" and V*) to enable access to group information for tokens restricted by the autoregressive nature.
Algorithm 1 The pipeline of dynamic group attention.
rather than individual tokens. The overview of our DGA is shown in Figure and the algorithm in Algorithm 1.
input Matrices Q, K, V Rxd group size m, impor-
tance rate 7. output Att E R.Lxd.
Formally, we give the grouped Kgroup and Vgroup as:
1: Compute the importance score via Eqn. (16) and (17).
Krouup KK V V/ (12)
2: Divide the tokens into focal tokens loc and non-focal tokens T based on and 7.
where K' and V are the key and value of the focal tokens, K" and V are the key and value of the non-focal tokens that are grouped and aggregated, K" and V are the key and value complementing tokens that cannot access the group information due to the autoregressive nature. The detailed formulations are given in Eqn. (14) and Eqn. (15). Recall the definition of attention in Eqn. (6), we compute the attention with causing mask as:
3: Construct K' and V E Xx_ by moving the items of
K and V corresponding to 7 the front positions.
4: Construct Kgroup and Vgroup via Eqn. (12), (14), (15).
5: Construct the causing mask M via Algorithm 2.
6: for j = I,...,I L..,,Lo do
7: // Compute the attention for the query Q
flash 8: Att, = Attention flash (Q,, K grouup Vgroup, M.).
9: end for
Att. = Σ(A group c M, ) Vrroup 1.
E R
1xd
(13)
us to explore novel approach to address the computational inefficiencies in long-context modeling. Typical methods often use sparse mechanisms (Xiao et al., 2024; Han et al., 2023; Chen et al., 2024), discarding some tokens to simplify attention computation and reduce costs. However, such ap- proaches risk disrupting the flow of information, particularly in tasks requiring comprehensive context understanding, such as question answering or document summarization.
where A = (Q T /Va) M is the caus- ing mask and @ is the element-produce We can implement this by the flash attention (Dao et al., 2022), simply formu- lated as Attention flash: (Q;, Kgroup Virrou,, M,))
5.1. Grouping for Self-attention
Overview of dynamic group attention. To address the above issues, we leverage the advantages of the group mech- anism and propose Dynamic Group Attention (DGA), which explicitly reduces redundancy in attention computa- tion without sacrificing essential token interactions. Specifi- cally, we divide tokens into two parts based on the impor- tance score: small subset of significant tokens as focal tokens, while the less critical tokens are treated as non-focal tokens. Non-focal tokens are then grouped and aggregated, allowing the model foeus on aggregated representations
Given a sequence with L tokens, we first employ an impor- tance statistic to derive the importance score 8 E R& (see Eqn. (16) in Section 5.2) and divide all tokens into focal tokens (top-y important ones) and non-focal tokens, denoted as Thee and T respectively. For convenience in compu- tation, we move the items of K and V associated with the focal tokens in foc to the front positions. We denote these rearranged items as K' and V', respectively. Subsequently, we group and aggregate the K' and V' matrices related to the non-focal tokens in Toon with a group size m based on
6

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
their importance in each group, which are formulated as:
where ||A., is the number of non-zero elements in the i- th column of A, which will be I- for the decoder-only based transformer. Similar techniques have been used for the inference of LLMs (Zhang et al., 2023; He et al., 2024).
K/= = K
K
V [
V+]
E Rxxd
K"
PI Pi..
K
Σ
K2
For fast to obtain an importance score 8, we sample a small portion of recent tokens and some other random tokens to obtain Q approximate the attention weight A:
jEG1
JEG₂
(14)
V
Σ jEG1
PLSV Σ V jEGb
Ä softmax (ÔK \Va)
(17)
where Po.=softmax QmaxC, K (ninG.maxx.. ) ER weight vector of i-th group, G2 is the index set of i-th group, min G, and max G; are the first and last token index in the
T is the
For fast implementation, we perform the matrix partitioning technique (Dao al., 2022) when computing the softmax.
i-th group, r=|7foq| and k=(L- -0) /mmm are the number of focal tokens and groups Here, we compute the weights P using only the query of the last token in each group. If non-focal tokens are not divisible by m, will include more tokens in Tloc, ensuring all tokens are processed.
6. Experiments
6.1. Experimental setup
Benchmark and evaluation metrics. We compare our methods on LongBench-E (Bai et al., 2024) to evaluate the long-context understanding capabilities of L.LMs, and use EM score (Liu et al., 2024a) to measure the ability to find the key information within long multi-document context. Ad- ditionally, use inter-token latency (ITL (Chitty-Venkata Venkata et al., 2024)) to measure the time delay between generating consecutive tokens. More details are in Appendix C.I.
Note that some tokens may not access preceding tokens after grouping aggregation. For instance, in the rightmost of Figure 1, the query Q2 cannot attend to the keys K1 and K₂ (i.e, their masks are zeros at the 4-th and 5-th columns) even if the 2-th token should access the 1-th and 2-th tokens. To address this, we introduce complementary keys K and values V to restore the missing information for the query Qi (e.g., adding the keys "K, and K₂" K2" and the values "V1 and V2" to the query Q2 at the 6-th and 7-th columns):
Models. We integrate our DGA attention into LLaMA2-7B (Touvron et al., 2023b) and GPT2-S (Radford et al., 2019) and OPT-125M (Zhang et al., 2022). We train the models SlimPajama (Cerebras, 2024). All training uses 8 A800 GPUs with a micro-batch size of 1, gradient accumulation of 8, and 1000 steps, consistent across all context lengths.
K"= [2,) V [V,] [V,], .jEG, if vElmin Gz, max Gz), (15)
where z denotes the index of the i-th token's nearest neigh- bor group. We then mask inaccessible keys and values due to the autoregressive nature (more details in Appendix D).
Baselines. We compare our DGA attention with follow- ing baselines: StreamingLLM (Xiao et al., 2024), LM- Infinite (Han al., 2023), and MInference (Jiang al., 2024). We defer more implementation details for these baseline methods in Appendix C.3.
Group inference. In the prefilling phase, we can calculate attention in the same way as in the training phase. In the decoding phase, the model generates new tokens, which re- quires us to dynamically group and aggregate tokens. When the model generates less than m²' 1.1m tokens (with use standard attention for
6.2. Empirical Studies of Redundancy in Sell-attention
10% slots for focal tokens), calculation; Once m tokens are generated, we can use the attention of the last query to re-calculate the weight P and update the group keys Kgroup and values Vgroup for the subsequent generation. However, we only add a new group key and value to the original ones for reduced memory usage once generating m' tokens.
We investigate the redundancy in transformer-based L.MSs. for long-context modeling by analyzing the sparsity of vanilla attention weights. Figure 2(a) shows the distribu- tion of the vanilla attention weights for a sequence randomly sampled from SlimPajama on L.LMMA-B,, which shows that only a few tokens contribute significantly to the predictions.
To further quantify the sparsity across more examples on long contexts, we examine Peeporse (h,erseL,,)) p) of the attention weights across 100 contexts of length 1k over SlimPa- jama on ILaMA-7B at layers 24 and 30 under different sparse rates p. Note that lower p means sparser atten- tion weights. Figure 2(b) shows that, as p decreases, i.e., p : 0.03-~0.02-0..00 the probability Paparse (L, p) in- creases with context length L,, indicating that attention
5.2. Fast Focal Token Identification for Grouping
Evaluating the importance of the token is crucial for our group-oriented attention. To this end, we employ an impor- tance score by computing accumulated attention weights:
ΣJ=1 A Aj 8,
(16)
AA A/lo
7

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Table Comparisons of different methods LongRench-F. (Bai al., 2024), where the 95% text length quantile is 31K. "ITI." denotes
inter-token latency (Chitty- Venkata et al., 2024), which measures the time delay between generating consecutive tokens.
Methods
Single-Doc. QA
Molti-Doc. QA
Summary
FS. Learning
Synthetic
Code
Avg. 1
ITL/
LLaMA2-7B (Vanilla Self-Aitettion)
6.43
2.37
13.65
56,65
3.04
48.0
21.69
69.70
Minference (Jiang et al.. 2024)
5.86
2.65
14.33
55.99
2.63
48.41
21.64
94.34
StreamingLLM (Xiao et al., 2024)
4.99
4.13
11.51
45.43
2.16
30.38
16.43
78.28
LM-Infinite (Han et al., 2023)
3.54
2.61
3.31
48.97
1.33
35.26
15.84
102.22
DGA-LLM (Ours)
3.61
3,58
6.81
57.90
1.47
53.45
21.14
28.80
the efficiency of our group coding strategy in reducing com- putational redundancy while maintaining performance, mak- ing it particularly suitable for time-sensitive applications.
Table Comparisons of different methods on EM score (Liu et al.,
2024a) evaluated at lengths from 4K to 32K.
Methods
4K
8K
16K
32K
Avg.
T. (Vanilla Self-Attetion)
37.2
36.4
33.8
26.8
33.6
More results on ITL are in Section 6.4.
StreamingLLMM
30.2
25.8
22.2
20.8
24.8
Results on EM score. We further validate the effective- ness of our DGA-LLM on long-document EM scores at context lengths of 4K, 8K, 16K and 32K for LLaMA2-7B trained with a context length of 8K. As shown in Table 2, our DGA-LLM achieves the highest performance at 4K, 16K, and 32K context lengths, and the second highest at 8K compared to other baselines, with average scores of 27.7. In contrast, methods like StreamingI and LM- IM-Infinite ex- hibit significant performance degradation as context length increases, particularly at 16K, where their scores drop to
LM-Infinit
29.4
28.6
23,8
22.4
26.1
MInference
29.2
24.8
23.6
17.0
23.7
DGA-LLM (Ours)
35.0
27.4
25.6
22.6
27.7
Table 3. Comparisons of different methods computational effi-
ciency in terms of inter-token latency (ITL (Chitty- Venkata et al.,
2024)) evaluated lengths from 4K to 16K. Methods
4K
8K
16K
LLMMA27BB (Vanilla Self-Artention)
36.87
42.32
69.70
MInference
93.13
93.93
94.34
StreamingLLM
40.00
46.67
78.28
22.2 and 23.8, respectively. These results highlight that our
LM-Infinite
49.70
64.34
102.22
DGA-LLM not only reduces computational redundancy but also maintains competitive performance, making highly suitable for diverse long-context scenarios.
DGA-LILM (Ours)
26.26
26.87
28.79
weights become increasingly sparse with longer contexts, and only a few tokens contribute significantly to predictions.
Results on optimization efficiency. To validate the opti- mization efficiency of the group coding strategy in DGA, we pre-train GPT2-S and OPT-125M with a 1K and 2K context length on SlimPajama, respectively, as fine-tuning LLMs from scratch is infeasible. As shown in Figures ((a) and 4, the validation loss for DGA converges faster than vanilla self-attention, indicating that our group coding strat- egy accelerates convergence. These results align with the conclusion in Theorem 3, demonstrating the efficiency of our approach in optimizing long-context modeling tasks.
Note that P P'spars (L, p) is dataset-independent and adapts to L. Figure 2(c) shows Psparse has nearly identical trends across SlimPajama and WikiText2 over 1lama2-7B or Qwen2.5-7B model, confirming P generalizes across datasets. As p = 0.02, P Paparse increases sharply with L. where P Paparse + at L = 400 over Ilama2-7B and = 300 over Qwen2.5-7B, respectively, proving sparsity strengthens with context length universally and model-level characterized. These results align with our analysis in Theo- rem 1, highlighting the inherent redundancy in long-context attention computations. More results are in Appendix H.
Results on robustness random noise. To evaluate the robustness of the group coding strategy in DGA to ran- dom noise, conduct experiments on question answering task for LLaMA2-7B trained with context-length 8K and compare the average KL-divergence of the output probabil- ity before and after adding the noises on random sampled 100 sequences on SlimPajama. From Figure 3(b), vanilla self-attention exhibits a significant deviation under noisy conditions, while our DGA maintains a more robust KL- divergence. This coincides with Theorem 2, demonstrating that group coding enhances robustness to random noise.
6.3. Comparisons on Long-Context Modeling
Results on Longbench-E. We conduct experiments on LongBench-E (Bai et al., 2024), which includes tasks with text lengths up to K1 Table shows that our DGA-LLM achieves competitive performance across tasks, with an av- erage score of 21.14 for LLaMA2-7B trained on 8K context- length texts. While method does not significantly out- perform others in average scores, it demonstrates notable advantages in Inter-token Latency (ITL) at 16K context length. Specifically, DGA-LLM achieves an ITL of 28.80 ms, 2.42X faster tham vanilla LLaMA2-7B (69.70 ms) and 3.55x faster than LM-Infinit (102.22 ms). This highlights
6.4. Comparisons on Computational Efficiency
To evaluate the inference efficiency of our DGA, measure the Inter-token Latency (ITL) of the LLaMA2-7B model
8

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Layer 30
0.10
0.15
10.4
-9-
GPT-125M (DGA)
OPT-125M (Vanilia)
KL divergence
0.16-
Vanilla Sel-Attention (Ours)
Val loss
0.03
10.0
0.12
0.00
400
600
800
1000
0.08
Token Index
(a) Distribution of attention weights for a random context.
9.6
0.04
9.4
Layer 24, p-0.05
Layer 24, p-0.02
Layer 24, p-0.01
1.00
1.00
Iterations
Noise variance
0.75
0.75
0.75
(a) Optimization Efficiency
(b) Robustness
0.50
0.50
0.50
Figure 3. Comparisons on optimization efficiency and robustness to random noise between Vanilla Seff-Attention and DGA-LLM (ours). Subfigure (a) shows validation losses of our DGA-LLM and vanilla ones OPT-125M where the models trained with 2K context length on SlimPajama, Subfigure (b) demonstrates average KL-divergence between the output probability distributions before and after adding Gaussian noise for Vanilla Self-Attention and our DGA-LLM under different levels noise variance (o²).
0.00
200
600
1000
0.00
200
600
1000
0.00
200
600
1000
Layer 30, pm0.05
Layer 30, pro.02
Layer 30, pm0.01
0.75
0.75
0.75
0.50
0.50
0.50
0.00
200
600
1000
0.00
200
600
1000
0.00
200
600
1000
(b) Distribution of p-sparse across different context lengths.
Llama2-7B
Qwen2.5-78
7. Conclusion
1.00
1.00
In this paper, we address computational redundancy in long- context modeling by first reformulating the sequence mod- eling as supervised learning task, enabling a clear under- standing of token relevance. Based on this reformulation, we theoretically analyze attention sparsity, showing that only few tokens significantly contribute to predictions, and propose a group coding strategy. Last, we propose Dy- namic Group Attention (DGA), which uses this strategy to adaptively reduce redundancy while retaining critical to- ken interactions. We validate the effectiveness of DGA on long-context tasks, showing significant reductions compu- tational costs while maintaining competitive performance.
Psparse
0.75
0.75
0.50
0.25
SlimPajama
0.25
SlimPajama WikiText2
WikiText2
0.00
200 400 600 800 1000
0.00
0
200
400
600 80o 1000
(c) Distribution of p-sparse across different datasets and models.
Figure Sparsity on the attention weights on long-context modeling. (a) shows the attention weight distribution for a random example on SlimPajama. (b) demonstrates the distribution of p- sparse across context lengths, i.e. Peparse (L, p). over 100 random
examples on SlimPajama. (c) exhibits the distribution p-sparse over 100 random examples WikiText2 and SlimPajama, across Ilama2-7B (left) and Qwen2.5-7B models (right) as = 0.02.
A Acknowledgments
This work was partially supported by the Joint Funds of the National Natural Science Foundation of China (Grant No. No.U2442,,27) Key-Area Research and Development Pro- gram Guangdong Province 201 0010000110001, Postdoctoral Fellowship Program of CPSF (GZC20251043) and TCL Science and Technology Innovation Fund, China.
during the decoding phase across 4K, 8K, and 16K contexts on LongBench-E using a single A800 GPU. Table shows that DGA significantly reduces inference latency compared other methods. For instance, 16K context length, DGA- LLM achieves ITL of 28.79 ms, 3.28x faster than MIn- ference (94.34 ms) and 2.72x faster than StreamingLL.M (78.28 ms). Notably, other methods are slower than vanilla self-attention, as they lack optimizations for the generation process. As the context length increases from 4K to 16K, other baseline methods show sharp ITL rise, indicating slower generation. In contrast, our DGA-LLM maintains stable and low ITL, demonstrating its efficiency for longer texts (see more detailed complexity analysis in Appendix E). Notably, LongLoRA (Chen et al., 2024) uses S²-Attention only during training, reverting to vanilla self-attention in in- ference, resulting in the same speed. These results highlight the efficiency of DGA-LLMM handling long-conter oong-context tasks.
Impact Statement
Our work addresses the computational inefficiency of long- context modeling in LLMs by introducing a dynamic token grouping strategy. By reducing redundant attention com- putations while preserving critical interactions, our method lowers training and inference costs, making long-context applications (e.g., legal document analysis, multi-hop QA) more accessible for resource-constraingg settings. Our ap- proach contributes to sustainable Al development by balanc- ing performance and efficiency, paving the way for scalable and practical deployment of L.LMs in real-world scenarios.

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
References
Chen, S., Wong, S., Chen, L.,, and Tian, Y. Extending context window of large language models via positional interpolation. arXiv: 15595, 2023.
Alayrac, J.-B., Donahue, J., Luc, P., Miech, A., Barr, I,, Hasson, Y., Lene, K., Mensch, A., Millican, K., Reynolds, M.. et al. Flamingo: visual language model for few- shot learning. Advances in neural information processing systems, 35:23716-2372 2022.
Chen, Y., Qian, S., Tang, H., Lai, X., Liu, Z., Han, S., and Jia, J. Longlora: Efficient fine-tuning of long-context large language models. In International Conference on Learning Representations, 2024.
Altman, N. and Krzywinski, M. The curse (s) of dimension- ality, Nat Methods, 15(6):399-40k 2018.
Chen, Y., You, Z., Zhang, S., Li, H., Li, Y. Wang, Y., and Tan, M. Core context aware transformers for long context language modeling. In International Conference on Machine Learning. PMLR, 2025.
An, C., Huang, F., Zhang. J., Gong, S., Qiu, X., Zhou, C., and Kong, L. Training-free long-context scaling of large language models. In International Conference on Machine Learning, 2024.
Chitty-Venkane
T., Raskar, S., Kale, B., Ferdaus, E, Tanikanti, A., Raffenetti, K., Taylor, V., Emani, M., and Vishwanath, V. LIm-inference-benece Inference bench- marking of large language models ai accelerators. In CC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1362-1379. IEEE, 2024.
Artetxe, M., Bhosale, S., Goyal, N., Mihaylov, T., Ott, M., Shleifer, S., Lin, X. V., Du, J., Iyer, S., Pasunuru, R., et al. Efficient large scale language modeling with mixtures of experts. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp- 11699-11732, 2022.
Azerbayev, Z., Ayers, E., and Piotrowski, B. Proof- pile. In Available online: https//githubb.co///aggggg azerbayev/proof-piee 2022.
Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J. Q., Mo- hiuddin, A., Kaiser, L.,, et al. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
Bai, Y., Lv, X., Zhang, J., Lyu, H., Tang, J., Huang, Z., Du, Z., Liu, X., Zeng, A., Hou. L., Dong. Y., Tang, J., and J. Longbench: A bilingual, multitask benehmark for long context understanding. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, pp. 3119-3137, 2024.
Dao, T., Fu, D., Ermon, S., Rudra, A., and Ré, C. Flashat- tention: Fast and memory-efficien exact attention with io-awareness. Advances in Neural Information Process- ing Systems, 35:16344-16339, 2022.
Beltagy, I., Peters, M. E., and Cohan, A. Long- former: The long-document transformer. arXiv preprint arXiv:2004.055 15000, 2020.
Edelman, A. Eigenvalues and condition numbers of random matrices. SIAM journal on matrix analysis and applica- tions, 9(4)5443-560, 1988.
Browder, A.
Mathematical analysis: an introduction. Springer Science & Business Media, 2012.
Frantar, E., Ashkboos, S., Hoefler, T., and Alistarh, D. Gptq: Accurate post-training quantization for generative pre- trained transformers. arXiv preprint arXiv:2210.17323, 2022.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33: 1877-1901, 2020.
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 101111 2024.
Cao, Z., Li, W., Li, S., and Wei, Improving multi- document summarization via text classification. Pro- ceedings of the AAAI conference on artificial intelligence, 2017.
Gu, Y., Dong, I.., Wei, F., and Huang, M. Minillm: Knowl- edge distillation of large language models. In The Twelfth International Conference on Learning Representations, 2024.
Cerebras. Slimpajama:
A 627b token cleaned and deduplicated version of redpajama. www..errerraeeeebbb///i/iaaaaaae seetaand-aandddddullii oorprdeooiioooo---rrppaaaaaa.a 2024. Accessed: 2024-04-23.
Han, C., Wang, Q., Xiong, W., Chen, Y., H., and Wang, S. LM-infinite: Simple -n-the-fly length generalization for large language models. arXiv preprint arXiv:2308.1611 2023.
10

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Han, I., Jayaram, R., Karbasi, A., Mirrokni, V., Woodruff, D., and Zandieh, A. Hyperattention: Long-context at- tention in near-linear time. In The Twelfth International Conference on Learning Representations, 2024.
International Conference on Learning Representations, 2024b.
Lounici, K., Pontil, M., Van De Geer, S., and Tsybakov, A. Oracle inequalities and optimal inference under group sparsity. 2011.
Hastie, T., Tibshirani, R., Friedman, J., Hastie, T., Tibshi- rani, R., and Friedman, Overview of supervised learn- ing. The elements of statistical learning: Data mining, inference, and prediction, pp. 9-41, 2009.
Lu, P., Mishra, S., Xia, T., Qiu, L., Chang, K.-W., Zhu, S.-C., Tafjord, O., Clark, P., and Kalyan, A. Learn to explain: Multimodal reasoning via thought chains for science question answering. Advances in Neural Infor- mation Processing Systems, 35:2507-2521, 2022.
He, Y., Zhang, L., Wu, W., Liu, J., Zhou, H., and Zhuang, B. Zipeache: Accurate and efficient kv cache quanti- zation with salient token identification. arXiv preprint arXiv:2405. 14256, 2024.
MacKay, D. Information theory, inference and learning algorithms. Cambridge university press, 2003.
Hom, R. A. and Johnson, C. R. Matrix analysis. Cambridge university press, 2012.
Mathias, R. The spectral norm of a nonnegative matrix. Linear algebra and its applications, 139:269-284, 1990.
Huang, C.-W., Krueger, D., Lacoste, A., and Courville, A. Neural autoregressive flows. In International Conference on Machine Learning, pp. 2078-2087. PMLR, 2018.
Mohtashami, A. and Jaggi, M. Landmark attention: Random-access infinite context length for transformers. arXiv preprint arXiv:2305. 16300, 2023.
Huang, and Zhang, T. The benefit of group sparsity. 2010.
Nasteski, V. An overview of the supervised machine learn- ing methods. Horizons. 4(51-62):56, 2017.
Jiang, H., LII Y., Zhang, C.,, Wu, Q., Luo, X., Ahn, S., Han, Z., Abdi, A. H., Li, D., Lin, C.-Y., Yang. Y., and Qiu, L. Minference 1.0: Accelerating pre-filling for long-context LLMs via dynamic sparse attention. In The Thirty-eigtth Annual Conference on Neural Information Processing Systems, 2024.
OpenAL. GPT-4 technical report. arXiv:2303.08774 2023,
Pasunuru, R., Celikyilmaz, A., Galley, M., Xiong, C., Zhang, Y.. Bansal, M., and Gao, J. Data augmentation for ab- stractive query-focused multi-document summarization. In Proceedings of the AAAI Conference on Artificial In- telligence, volume 35, pp. 13666 13674, 2021.
Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. Transformers are rnns: Fast autoregressive transformers with linear attention. International Conference on Machine Learning, pp. 5156-5156101 5165. PMLR, 2020.
Peng, B., Quesnelle, J., Fan, H.,, and Shippole, E. Yarn: Effi- cient context window extension of large language models. In The Tweifth International Conference on Learning Representations, 2024.
Ke, Z.,, Shao, Y., Lin, H., Konishi, T., Kim, G., and Liu, B. Continual pre-training of language models. In The Twelfth International Conference on Learning Representations, 2023.
Radford, A.,
Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Kenton, J. D. M.-W. C. and Toutanova, L. K. Bert: Pre- training of deep bidirectional transformers for language understanding. In Proceedings of naacL-HLT, volume 1. Minneapolis, Minnesota, 2019.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 8748-8763. PMIR, 2021.
Kitaev, N.. Kaiser, L., and Levskaya, A. Reformer: The efficient transformer. In International Conference Learning Representations, 2020.
Ryan, W. and Lin, S. Channel codes: classical and modern. Cambridge university press, 2009.
Liu, N. F., Lin, K., Hewitt, J., Paranjape, A., Bevilacqua, M., Petroni, F., and I. Liang, P. Lost the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157-173, 2024a.
Schaeffer, R., Miranda, B., and Koyejo, S. Are emergent abilities of large language models a mirage? Advances in Neural Information Processing Systems, 36, 2023.
Singhal, K., Tu, T., Gottweis, J., Sayres, R., Wulezyn, E., Amin, M., Hou, L., Clark, K., Pfohl, S. R., Cole-Lewis, H., et al. Toward expert-level medical question answering
Liu, X., Yan, H., Zhang, S., An, C., Qiu, X., and Lin, D. Scaling laws of rope-based extrapolation, In The Twelfth

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
with large language models. Nature Medicine, pp. 1-8, 2025.
Conference of the North American Chapter of the Associ- ation for Computational Linguisties: Human Language Technologies, pp. 4643-4663, 2024.
Sun, Y. Dong, L., Huang, S., Ma, S., Xia, Y., Xue, J., Wang, J., and Wei, Retentive network: successor to transformer for large language models. arXiv preprint arXiv:2307.0862), 2023.
Yen, H., Gao, T., and Chen, D. Long-context language modeling with parallel context encoding. In Proceed- ings of the 62nd Annual Meeting the Association for Computational Linguistics, pp. 2588-2610, 2024.
Sun, Z., Yang, Y., and Yoo, S. Sparse attention with learn- ing to hash. In International Conference on Learning Representations, 2021.
Zaheer, M., Guruganesh, G., Dubey, A., Ainslie, J., Al- berti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q.. Yang, L., al. Big bird: Transformers for longer se- quences. Advances in Neural Information Processing Systems, 33:17283-17299 2020.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F,, et al. Llama: Open and efficient foundation lan- guage models. arXiv preprint arXiv:2302. 13971, 2023a.
Zhang, L.. Hosseini, A., Bansal, H., Kazemi, M., Ku- mar, A., and Agarwal, R. Generative verifiers: Re- ward modeling next-token prediction. arXiv preprint arXiv:2408. /5240, 2024.
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine- tuned chat models. arXiv preprint 230::2377.09288 2023b.
Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M.. Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., et Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205. 01068, 2022.
Tworkowski, S., Staniszewski, K., Pacek, M., Wu, Y., Michalewski, H., and Mitoš, P. Focused transformer: Contrastive training for context scaling. Advances in Neural Information Processing Systems, 36, 2023.
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-34711 2023.
Vaswani, A. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Wang, X., Zhang, X., Luo, Z., Sun, Q. Cui, Y.. Wang, J., Zhang, F. Wang. Y., Li, Z., Yu, Q., et al. Emu3: Next-token prediction is all you need. arXiv preprint arXiv:2409. 18869, 2024a.
Zhu, D.,, Yang. N., Wang, L., Song, Y., Wu, W., Wei, F., and Li, S. Pose: Efficient context window extension of Ilms via positional skip-wise training. In The Twelfth International Conference on Learning Representations, 2024.
Wang, Z., Jin, B., Yu, Z., and Zhang. M. Model tells you where to merge: Adaptive kv cache merging for lims on long-conter tasks. arXiv preprint arXiv:2407.08454 2024b.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F,, Chi, E., Le, Q. V., Zhou, D., al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35: 24824-24837, 2022.
Xiao, G.. Tian, Y., Chen. B., Han, S., and Lewis, M. Effi- cient streaming language models with attention sinks. In International Conference on Learning Representations, 2024.
Xiong, W., Liu, J., Molybog, I,, Zhang, H., Bhargava, P., Hou, R., Martin, I.., Rungta, R., Sankararaman, K. A., Oguz, B., Khabsa, M., Fang, H., Mehdad, Y., Narang, S., Malik, K., Fan, A., Bhosale, S., Edunov, S., Lewis, M.. Wang, S., and Ma, H. Effective long-context scal- ing of foundation models. In Proceedings of the 2024
12

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
APPENDIX
Contents
Theoretical analysis
14
A.I Proof of Theorem
14
A.2 Proof of Theorem
A.3 Proof of Theorem
16
More Discussions on Sequence Modeling and Supervised Learning
18
More Details for Experiment Settings
19
C.1 More Details on Benchmark and Evaluation Metrics
19
C.2 Implementation Details on Our Method
19
C.3 Implementation Details Baselines
19
C.4 Implementation Details on Sparsity Figure
20
C.S Implementation Details on Optimization Efficiency Figure 3(a)
20
Details on Causing Mask Group-Oriente Attention
20
Analysis on Reduced Complexity and Key-value Cache
21
Ablation Studies
22
Discussions on DGA-LLM
23
More Experimental Results
23
H.l More Results on Redundancy in Self-attention
23
I Future Directions
23
13

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
A. Theoretical analysis
A.1. Proof of Theorem
Theorem (Sparsity on attention weights) Consider p E (1/L, 1] as a sparse rate, we say that the weight a is p-sparse when there exists at least one probability greater than 1/pp.. Let = KQ; RR, then the probability of a being p-sparse P Paperse (L, p) is given by
Peparse ( (L.
max 1 CheeadPtail""" x>0
(18)
where Phead= P(exp(E)) S x) with j being some index of a and Pias = Pi(Lp- 1)x S Ehet exp(Ex)).
Proof. According to the definition of p-sparse, the probability of having at least one probability greater than 1/(L.) is given
P separse p) = - P(a; 1/((p)) vj E [4]}
21- (at S 1/(p))
(19)
Here, the inequation due to the dependence of each o.. next focus on the upper bound of P(a3 S 1/L)))
P(a3 & 1/(Lp)} =
& 1/(p))
P(exp(E)) 5 </((p) 1,))
P(exp(E)) S x S ((L))
P(exp(()) S 2, = (/Lp)((xx((()
P(cxp(Ej) s x) Pfz (sLp)) cx)((,(()))))) S x}
P(exp(Ej) s x) P(Lpr - (exp(E), (n) exp(E)) S <
s P(exp(E)) s < P((Lp - 1)x - Σ exp((x))
(20)
kjj
Combining the inequations (19) and (20), and denoting Phead Plexp(E)) x} and Preut P((LD 1)x
Eke, exp(Ex)), we finish the proof.
Note that the distribution of the attention weights a is often complex, and more importantly, these weights are not independent and may be highly correlated, which makes the analysis of sparsity extremely challenging. In this theorem, we provide general bound for sparsity without imposing specific assumptions on the weights. In the inequation (18), a larger x increases Phead but decreases Ptant ensuring that their product remains bounded by a value less than 1. When the sequence length large, this value raised the power of L will be much less than 1, resulting in large P Peparse (L, p). We hope this theorem offers researchers deeper insights and serves as a source of inspiration for further exploration into sparsity.
A.2. Proof of Theorem
Theorem 2 Assume the weights before normalization are obtained by the product of the query and key matrix, and explá,)
0j Σt_ exp(ār) Consider a Gaussian noise λā ~ ol,, being added into â and each group size being (Gyl = m, the variance of the weight changes obtained via group optimization in Eqn. (2) can be reduced by 1/m?
Proof. Recall that the optimization in Problem (2) when |Ggl is:
min
y
s.t. may= =1, ag ag>0.
(21)
g
ag is equivalent to adding the noise & on each weight in g-th group. Consequently, we focus only on the effect of the input noise &g m on the normalized output. Since the factor 1 can be shifted m on the variance a of the noise, we next direct analyze the effect of the input noise â on the normalized a, for simplicity.
Note that adding the noise Ad, ~ .N(0 o²)
14

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Denote the normalized noised weight
exp(aς)
af E exp(a.)
(22)
where ag aā + Ddj and Dāj ~ ~N(0, 02). Then, according to Lemma and Lemma 2, we have
Var(Aa;) = Varla] -az)
(23)
Var a5(Aāz -
Σ
azA + d(az)))
==1
L
=0 Var
Ddj- -
Σ
(k ما, + {(ar))
/=1
= =
(24)
where o(ā represents the higher-order infinitesimal of Αā, and O denotes the same-order infinitesimal of a² (Browder, 2012). Thus, when adding the noise áz to each weight the g-th group, the variance of the weight changes O /m²). Therefore, by group optimization in Eqn. (2), the variance of the weight changes can be reduced by 1/m². O
exp(ā,) and a = Et. exp(ā:+AA.)' where dā, ~ (N(000), let Das = aς ag. we have Lemma 1. Given aj = Et, Explap exp(ar)
expla,+
Aaj aj Aāj Σ C, + o(Aāz) +
(25)
where o(Sās) represents the higher-order infinitesimal of Aā₃ (Browder, 2012).
Proof. According the definition of Aāj, have
exp(â; + Aāz)
Σ exp(pi Aā:)
exp(á;)](1 + Aā, + o()ā))]
E (xp((::)1 + Ad; + of ((ā))
exp(ā,)](1 Aā, + o(Aā,))
_ exp(ax) + Ei_ exp(āx) + of (a:)]
exp(o;) Ad; + ol (Ax expla.)
exp(áx)) 1 + ΣLe 5z exp(dmm
Ad; + of A()))
exp(ā;) + Aāj + o(Aū)))
El_ exp( {1 E/= as Aas + o(Aā))]
a3 + Aā, + o(A
1+ Σle 0; Aā; + of ((aā))
E as Dā; La + o(Ar)))
a, [11 + Aāj + A(o)))]
1- I- aalAa + o(Ao))] +0 +o
i=1
1=1
=a 1+ Aa.
Σ Aa o(Aā))
(26)
where the second line follows Taylor's expansion of exp(Aāz) = 1+ Aā, + o(Aā)); the penultimate line follows Taylor's expansion of I+ a. Ad. [o = -te as Aā; o(Aā.)) + Et as m[Aa; + +((a)))
15

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Therefore, have
Daz a} a, aj Ad, Σ a, + d(aā))
(27)
Lemma 2. Given A N((, we have
L = Var(Sá; Σ = O(oo),
(28)
where 2 denotes the same-order irfinitesimal of x² (Browder, 2012).
Proof. Expanding the variance of Aay- Ei= 0; as
Var(Day- Σ aaaa) = Var(Aāj) + Var
Σ a, - -2-Co. Cov
Aag,
Σ a,
i=1
i=1
L
0² + 0
2
2
a Cov(oaj,
i=1
i=1
x²
2
0 2az0²
i=1
=1+ Σ a - 20,)
= -(
(29)
where the third line holds since Cov(Ad;, Aāz) = 0 when i + and Cov(Aā, Aā₂) = o² when i + j.
A.3. Proof of Theorem 3
Theorem 3 Denote H and H the Hessian matrix of the optimizations in (1) and (2), respectively. Let k(H) Amaxx (H)) (min(()) be the condition number (Edelman, 1988) of H, where Amax and Xuin are the maximum and minimum eigenvalues of H, respectively. Consider each group size |G gl m and Amiu (H) > 0, we have
H x(H).
(30)
Proof. Recall that the objective in Problem (2) when G = m is:
min &
Σ
Cg V
y
s.t.
= ay>0.
(31)
m
g=1jEG
g=1
Let V, 1 Ejec, V, and V [V: V2; m
Vel E Rexd
then the Hessian matrix of the grouped objective is
H TVVVVV
(32)
We introduce a grouping matrix M E 1 where M is defined as
i E
M g.
(33)
0,
$ g.
16

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Then, have
V MV.
(34)
The Hessian matrix in (32) can be reformulated
A
MV.
(35)
According to Lemma and 4, we have
Xmax (H)
mmax H
(36)
Amin H))
Amin (H)
Thus, based on the definition of the condition number (Edelman, 1988), have
x(H) x(H).
(37)
Lemma 3. Given H -V M TTM MV and H = 2V V, where M is defined in Eqn. (33), we have
Amax
Xmax (1f)
(38)
Proof. Note that the matrix M M is a block diagona matrix:
m2 J
0
Jm
0
M T M
m
(39)
0
Jm_
m2
where Jm E Rm is an all-one matrix.
Note that the rank of Jm is rank(Jm) 1 since each row of the matrix is 1. Due to Jn mv, where
v 11 1.. 1]T, one of the (non-zero) eigenvalues m²
1
Jm is
1 Jm)
Amax
(40)
m2
m m
Thus, have
1
Amax (M M)
(41)
mn
Based the property of the spectral norm of the matrix (Mathias, 1990), we have
S(VT M MV) S S(VTV) S(M M),
(42)
where 5(4) the spectral norm of the matrix A. Since the spectral norm of the symmetric matrix is its maximum cigenvalue, we have
Amax (V (VT VTM M MV) & Amax (V T V). Amax (M [MMM) M).
(43)
Combing Eqn. (41) and the definitions H and H, we get
Amax (H)
Amax (
(44)
m
Lemma 4. Given H = 2VT M MV and H = 2V V, where M is defined in Eqn. (33), we have
Amin (H)
Amin (
(45)
17

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Proof. According the Rayleigh theorem (Horn & Johnson, 2012), for M M, for any nonzero vector E IR,, have
Mz M
Amiu Ami M).
(46)
z
Let Vx, where E I& and |xx12 = 1, we have
x M MVx Amin (M M) x VV..
(47)
Taking the minimum of all the vectors get
min x
x V
MVTMV 2 (Min(MMMM M). min x <V Vx. |x|]==1
Vx.
(48)
According to the definition of the minimum eigenvalues, we have
min (VTM M MVV 2 Amin (M M) Amiu (V V).
(49)
Here, we focus on the non-zero eigenvalues of V MTMV since the zero eigenvalues may not actually mean much. Based on the analyses in the eigenvalues of M M in Lemma 3, we have Amin (M M) 1. Thus, we obtain
Amin (H)
Amin ( (
(50)
17
B. More Discussions on Sequence Modeling and Supervised Learning
We demonstrate that traditional pre-training is fundamentally form of supervised learning. For token sequence X1,X0 X2,..... Xz, traditional pre-training, based on the principle of maximum likelihood, optimizes the model 0 as
max
= II
Xk-1)), E X
(51)
Given large collection of sequences, this objective aligns with Eqn. 2, with the conditions represented as C(y). In practical applications, this can be reformulated as minimizing the cross-entropy loss:
min log logp(xx|<1, X x)-
(52)
Thus, the traditional pre-training paradigm for LLMs essentially equivalent to supervised learning.
18

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
C. More Details for Experiment Settings
C.1. More Details on Benchmark and Evaluation Metries
SlimPajama (Cerebras, 2024) dataset is an open-source reproduction of the data mixture used to pretrain the LLaMA models. includes 82% web data, 4.5% code from GitHub, 4.5% Wikipedia, 4.5% books, 2.5% Arxiv, and 2.0% StackExchange. The dataset is designed to extend the context lengths of large language models (LLMs) 128K tokens through data engineering techniques such as per-source length upsampling.
LongBench (Bai et al., 2024) is pioneering benchmark designed to evaluate the long-context understanding capabilities of large language models (LLMs) in a bilingual (Chinese and English) and multitask setting. It includes 21 tasks across 6 major categories, such as single-document QA, multi-document QA, summarization, few-shot learning, synthetic tasks, and code completion, covering key long-text application areas, The benchmark comprises 14 English tasks, Chinese tasks, and 2 code tasks, with most tasks averaging between 5k 15k in length and totaling 4,750 test data points. LongBench contains test set with more evenly distributed lengths, named LongBench-EE which includes comparable data quantities across 0-4K, 4K-8K, and 8K+ length intervals, enabling thorough analysis of model performance across different input lengths.
EM score (Liu et al., 2024a) measures the ability to find the key information within long multi-document context. It measures whether the model's predicted output exactly matches one or more ground-truth answers, ensuring precision in information retrieval. Therefore, the EM score is calculated by checking if any correct answers appear in the model's predictions, providing a strict assessment of the model's ability to extract precise information from complex contexts. This metric is particularly stringent, as it requires the model identify the correct answer without partial or approximate matches.
Inter-token latency (ITL (Chitty- Venkata al., 2024)) is a metrie for evaluating the average time between generating consecutive tokens in response. It refers to the time delay between the generation of consecutive tokens (e.g., words or subwords) in sequence produced by a language model. This metric is influenced by factors like model architecture, computational resources, and optimization techniques. Reducing inter-token latency is essential for enhancing the usability and performance of language models in senesseniiive scenarios.
Perplexity (PPL) serves as a metric to evaluate a model's predictive accuracy within given context. derived by exponentiating the average negative log-likelihood of a sequence, providing a statistical assessment of language modeling efficacy. Proof-pile (Azerbayev et al., 2022) is high-quality dataset encompassing mathematical text and code, totaling 13GB and consisting of 8.3 billion tokens (tokenized using the gpt-neox tokenizer). This dataset aggregates variety of sources, including both informal and formal mathematical content, with raw data collected from the web. The PPL is reported based on the test dataset. We use the test dataset of Proof proof-pile to verify the modeling ability of models.
C.2. Implementation Details on Our Method
For continuous pretraining, we utilize the SlimPajama dataset, an open-source replication of the LLaMA pretraining data mixture. In our approach, we replace the standard self-attentoon mechanism in LLaMA-2 with our focal attention. Notably, the group size m = 16 and importance rate y = 0.1, the number of the focal tokens is max(> 1k), remain consistent across different experiments, ensuring architectural uniformity. All models are trained on 8 x A800 GPUs, employing a micro-batch size of with gradient accumulation over 8 steps, totaling 1000 training steps. To facilitate effective scaling to longer contexts, we modified the RoPE (Rotary Position Embedding) base frequency from 10,000 500,000, following Cerebras (2024) and Xiong al. (2024).
C.3. Implementation Details Baselines
We implement StreamingLLM (Xiao et al., 2024) following the codebase', LM-Iniiitt (Han et al., 2023) following the codebase?, MInference (Jiang et al., 2024) following the codebase?.
For StreamingLLMM, we configure the attention sink parameter to 4 and the attention context window size to 2000 tokens. For LM-Infinite, the local branch size is set to 4096 tokens, while the global branch size is configured to 10. For MInference, we utilize their official implementations with default parameter settings.
19

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
C.4. Implementation Details on Sparsity in Figure
In Section 6.2, we conduct experiments on the sparsity of the vanilla attention weights on the samples from the train split of the SlimPajama (Cerebras, 2024) dataset, truncating each sample to retain only the first 1,000 tokens. Each sample undergoes single forward pass through the LLaMA2-7B model (Touvron al., 2023b), during which we capture the attention maps from the 9-th attention head of the 24-th and 30-th layers. In Figure 2(a), we randomly select a example and display the distribution of attention weights corresponding to the last token in the 30-th layer. Additional results are provided in Figure 6. In Figure 2(b), we randomly select 100 examples and present the statistical analysis of attention distributions across rows L E [100, 1000] in different attention maps, quantified using the p-sparse metric P P'spare(LL p) with different p E {0.05, 0.02, 0.01), as defined in Theorem 1. We estimate P Pspase (L, p) using the observed sparsity frequency in the 100 examples. Additional results are provided in Figure 7.
C.5. Implementation Details on Optimization Efficiency in Figure 3(a)
We train the GPT2-S and OPT-125M models on the SlimPajama dataset using distributed setup consisting of 8 A800 GPUs. The training configuration includes micro-batch size of I, gradient accumulation over 8 steps, and a total of 1000 training steps. Integrating our proposed DGA into the model, we set the group size m to 16 and the importance rate to 0.1. For GPT2-S, the learning rate is set to X 10-4, with a warmup period of 20 steps. For OPT-125M, the learning rate set to 8 x 10-5, with warmup period of 50 steps and weight decay coefficient of 0.1. Additionally, the AdamW optimizer is employed with the hyperparameters 31 = 0.9 and $2 = 0.95.
9.4
GPT2-5 (Vanilla)
GPT2-S (DGA)
9.3
9.0
8.9
250
500
750
1000
Iterations
Figure 4. Validation losses of our DGA-LLM and vanilla ones on GPT2-S. where the models are trained with IK context length SlimPujama.
D. Details on Causing Mask in Group-Oriented Attention
Algorithm 2 Constructing causing mask M for attention.
input Matrices Q, K, V E BLxd, group size focal tokens Tie and non-focal tokens Taon.
output Causing mask M R=x(++++m)
1: Initialize a lower triangular matrix M E RL with ones.
2: Partition 7 into k groups (G each of size m. // Note that non-divisible tokens are classified as focal tokens.
3: Construct 0-1 mask M for aggregated tokens by setting - if M 1o:>0.
4: Construct 0-1 mask - Lxm for complemented tokens:
M t 11mmma)) IRm if ig Gz, max Gz].
where & = M nou
6th (M"), 2th (M") repeats each column of the matrix M m times.
5: Final mask is M [M
M M E (r++kmm))
Tice foc
20

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
E. Analysis on Reduced Complexity and Key-value Cache
(a) Self-Attention (())
Focal tokens
Non-Foral tokens
(b) Ours 0 (r
m
Figure 5. Comparison the computational complexity during inference between our DGA-LI -LLM and vanilla self-attention.
Our DGA-LLM enhances efficiency by adaptively grouping and aggregating redundant non-focal tokens, thereby reducing computational complexity and key-value cache memory storage compared to vanilla self-attention. Based these benefits, our DGA-LLM achieves substantial improvements in terms of running speed and memory usage efficiency.
Computational Complexity Optimization. Our DGA-LLM exhibits varying computational complexities across training and inference phases. For the training phases, DGA-LLM achieves a computational complexity of O(Lr + L + Lm), representing substantial improvement the vanilla full self-attention mechanism, which has a complexity of (LP).. Specifically, the computation primarily involves three types of tokens: (1) focal tokens, contributing complexity of (Lr); (2) aggregated non-focal tokens, contributing (L "==");; ); (3) complement tokens, contributing (Lm). Considering the group size m and the number of focal tokens as constant, the final computational complexity can degenerate as O(L2/m)
m
As shown in Figure 5, during the inference phase, where the generation process involves next-token prediction, the computational complexity of generating a token is reduced to O(r L-r mm). This is significantly lower with large m compared to the full self-attention mechanism, which has complexity of OL)).
Key- Value (KV) Cache Reduction. The KV cache is widely used mechanism in ceff-attention-batt based Transformers to enhance the efficiency of attention computations by leveraging the model's auto-regressive nature store and reuse key-value pairs (i.e., K and V). However, its memory consumption scales linearly with sequence length, making it a primary contributor to the overall memory footprint during inference. The increasing memory demand not only imposes substantial resource requirements but also potentially degrades inference speed due to the heightened frequency of I/O operations.
The full self-attention mechanism has storage complexity of O(L), whereas our proposed DGA-LLM significantly reduces O(r + L-r + m). Specifically, instead of storing all original tokens O(L) complexity, we retain key and value m matrices for three distinct token types: focal tokens with a complexity of (r),, aggregated non-focal tokens O [--r and complement tokens O(m).
m
21

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
F. Ablation Studies
Effect of group Size m. In this experiment, we investigate the impact of group size m on model performance and latency, As shown in Table 4, when varying m from 64, we observe only a slight degradation in model performance, with perplexity (PPL) increasing from 3.20 to 3.87 and accuracy decreasing from 70.17% to 55.00%. However, computational efficiency shows notable improvement, with latency significantly decreasing from 189.80 ms to 162.02 ms. Thus, set m 16 to strike balance between computational efficiency and model performance the default training setting.
Table 4. Effect of group size
4
16
32
64
PPL L
3.20
3.42
3.59
3.77
3,87
Accuracy t (%)
70.17
68.33
67.00
65.61
65.00
Latency (ms)
189.80
189.10
172.12
169.40
162.02
Effect of focal token identification. this experiment, we investigate the effect of different focal token identification strategies on model performance. From Table 5, compared the randomly selected strategy, our Top-K approach achieves an improvement in aceuracy from 66.91% % 67.00%. At the same time, perplexity (PPL) shows decrease from 3.60 to 3.59. These results suggest the effectiveness of focal token identification in DGA over the randomly selected strategy.
Table S. Effect of focal token identification strategy.
Strategy
Randomly Selected Top-K (Ours)
PPL 4
3.60
3.59
Accuracy 1 (%)
66.91
67.00
Effect of importance rate y. In this experiment, investigate the effect of the importance rate "y in our DGA. Table 6 demonstrates a significant positive correlation between "y values and model performance. Specifically, from 0.1 to 0.9, the model accuracy improves substantially from 67 .00% to 70.58%, while perplexity (PPL) consistently decreases from 3.59 to 3.20. However, the latency shows an increase as 7 increases, growing from 172.12 ms to 555.25 ms. larger indicates that more tokens are identified as focal tokens, thereby preserving a greater portion the original input information in the self-attention computations. This preservation of information, while beneficial for accuracy, inevitably increases the computational overhead. Conversely, smaller y leads more tokens being grouped and aggregated, which enhances computational efficiency but at the expense of model performance. Striking balance between computational efficiency and model effectiveness, we select y = 0.1 the default training setting.
increases
Table 6. Effect of importance rate 7.
0.1
0.3
0.5
0.7
0.9
P Accuracy 1 (%)
3.59
3.43
3.27
3.22
3.20
67.00
68.25
69.67
70.29
70.58
Latency (ms)
172.12
224.85
386.36
465.35
555.25
Effect of complementary tokens. Table 7 shows that removing complementary tokens significantly degrades performance
on tasks like Multi-Doc QA from 3.58 to 2.37 and Code from 53.45 to 48.00, indicating complementary tokens are critical for context modeling. They slightly increase latency from 24.9 ms to 28.8 ms. but still 2.4 ~ 3.5x faster than vanilla self-attention (Table 2: 69.70 ~ 102.22 ms).
22

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Table Effect of complementary tokens on LongRench--F (Bai et al., 2024), where the 95% text length quantile is 31K. "ITI." denotes
inter-token latency (Chitty Venkata et al., 2024), which measures the time delay between generating consecutive tokens.
Methods
Single Doc. QA Multi Doc. QA
Summar.
FS Learning
Synthetic
Code
Avg. t
ITL (ms) L
w/o comple. tokens
6.43
2.37
8.47
53.69
3.04
48.00
20.33
24.9
DGA-LLM (Ours)
3.61
3.58
6.81
57.90
1.47
53.45
21.14
28.8
G. Discussions on DGA-LLM
Hyperparameters selection. Experimental analysis in Tables 4 and 7 reveals that smaller group sizes (m) and higher importance rates (y) improve performance at the cost of increased latency. Based on these, we recommend the following practical guidelines for parameter selection: For resource-constrriiee scenarios, larger m and lower y balance acceptable applications (e.g., medical diagnosis) benefit from minimal
performance with reduced complexity. Performance- m and maximal 7 to preserve accuracy, whereas latency-sensitiee tasks (e.g., real-time systems) require moderate m and lower 7 for responsiveness. An adaptive framework automatically optimize (m, 7) based on application-speeific accuracy-latency trade-offs remains a promising direction for future work.
Potential application. While our current work focuses on long-text modeling, the proposed DGA mechanism is inherently lask-agnostic and could generalize to other long-sequence domains (e.g., video/audio) where redundancy exists in sequential tokens and adaptive token importance assessment is critical. For instance, 1) Video processing: Temporal sequences in videos often exhibit localized redundancy (e.g., static backgrounds or repetitive motions). DGA could dynamically group less informative frames while preserving critical temporal segments. 2) Audio processing: Long audio signals contain silent or redundant segments. DGA's importance scoring could prioritize phonetically rich regions, enabling efficient compression.
H. More Experimental Results
H.1. More Results on Redundancy in Self-attention
In this section, we present additional visualizations of the sparsity in vanilla attention weights. Figure 6 illustrates the distributions of attention weights across four randomly sampled long contexts from SlimPajama. Figure 7 depicts the distributions of P PsparseLL, p) for p E {0.05, 0.02, 0.013. The results reveal that attention weights grow increasingly sparse with longer contexts, with only a small subset of tokens playing a significant role predictions, aligning with the findings in Theorem and the results in Section 6.2.
I. Future Directions
While our proposed Dynamic Group Attention (DGA) demonstrates significant improvements in computational efficiency and robustness for long-com oongccontxtt modeling, several avenues remain for further exploration. First, extending DGA to multi- modal settings, such as vision-language models or audio-text models, could unlock new possibilities for efficient cross-modal reasoning. For instance, integrating DGA with architectures like CLIP (Radford al., 2021) or Flamingo (Alayrac et al., 2022) could enable more efficient processing of long video or audio sequences while maintaining high performance. Additionally, exploring the application of DGA in low-resource environments, such edge devices mobile platforms, could further enhance its practicality. Techniques like quantization (Frantar et al., 2022), distillation (Gu et al., 2024), or hardware-aware optimization (Artetxe et al., 2022) could be combined with DGA to reduce memory and computational requirements, making it suitable for real-time applications in resource-constrained settings.
Second, the theoretical foundations of DGA could be further refined to better understand its limitations and potential improvements. For example, a deeper analysis of the trade-off's between group size m and model performance could provide insights into optimal hyperparameter settings for different tasks and datasets. Moreover, investigating the impact of DGA on downstream tasks, such as few-shot learning (Brown et al., 2020), transfer learning (Kenton & Toutanova, 2019), or continual learning (Ke et al., 2023), could reveal its broader applicability. Finally, exploring adaptive mechanisms for dynamically adjusting the group size m or the importance threshold ? during training and inference could further enhance the flexibility and efficiency of DGA. These directions not only address the limitations of the current approach but also open up new opportunities for advancing long- long-context modeling in both research and practical applications.
23

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Layer
Layer 18
0.80
0.60
0.40
0.40
0.20
0.20
0.00
0.00
Layer
30
0.80
0.15
0.10
UEt
0.40
0.05
200
400
500
800
1000
200
400
600
800
1000
Token Index
Token Index
Layer
Layer
0.40
0.20
0.10
0.00
1000
0.00
800
1000
Layer
30
0.80
0.40
0.30
0.40
0.20
200
400
600
800
1000
0
200
400
600
800
1000
Token Index
Token Index
(b)
Layer
Layer
0.40
0.30
0.30
0.20
0.10
0.00
400
1000
0.00
200
800
1000
Layer 24
Layer 30
0.60
0.50
0.15
0.40
0.30
0.10
0.05
0.10
0.00
11
200
400
600
800
1000
0
200
400
600
800
1000
Token Index
Token Index
(c)
Layer
Layer
0.60
0.50
0.40
0.40
0.30
0.20
0.20
0.10
0.00
200
400
1000
0.00
200
800
1000
Layer 24
Layer 30
0.50
0.40
0.30
0.20
0.20
0.10
0.10
0.00
200
400
500
800
1000
200
400
600
800
1000
Token Index
Token Index
(d)
Figure 6. More visualizations on distribution of attention weights over Llama2-7B on 4 random examples from SlimPajama.
24

---

Curse of High Dimensionality Issue in Transformer for Long-context Modeling
Layer 6, p=0.04
Layer 6, p=0.03
Layer 6, p=0.02
Layer 6, p=0.01
1.00
1.00
1.00
1.00
Psparse
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
200
600
1000
200
600
1000
200
600
1000
200
600
1000
Layer 18, p=0.04
Layer 18, p=0.03
Layer 18, p=0.02
Layer 18, p=0.01
1.00
1.00
1.00
1.00
Paparse
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
200
600
1000
200
600
1000
200
600
1000
200
600
1000
Layer 24, p=0.04
Layer 24, p=0.03
Layer 24, p=0.02
Layer 24, p=0.01
1.00
1.00
1.00
1.00
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
200
600
1000
200
600
1000
200
600
1000
200
600
1000
Layer 30, p=0.04
Layer 30, p=0.03
Layer 30, p=0.02
Layer 30, p=0.01
1.00
1.00
1.00
1.00
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.00
0.00
0.00
0.00
200
600
1000
200
600
1000
200
600
1000
200
600
1000
L
Figure 7. More visualizations on the sparsity attention weights.
25


Reviews:
[{"review_id": "6F9Tqd39aT", "reviewer": "Reviewer_ta8R", "summary": "In this paper, the author proposes a new method for long context LLMs. It uses dynamic grouping to divide tokens into several groups,  the attention over coarse granularity of token groups achieves faster inference.", "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 thank the reviewer for the detailed comments. Responses are below:\n\n>Q1. The LLM sparsity discovered in Sec 4 has already been revealed in several previous works (e.g., StreamingLLM).\n\n**A1.**  We thank the reviewer for noting prior sparsity on self-attention weight like in StreamingLLM [r1]. Unlike empirical studies, we theoretically show why attention sparsity should happen and would be strengthened with context length (Theorem 1). Based on this, we developed Dynamic Group Attention (DGA), which adaptively aggregates tokens while preserving critical interactions. Theorems 2–3 further establish group coding's advantages in noise robustness and optimization efficiency. We highlight **two additional distinctions**:\n* **Static Sparsity vs. Dynamic Group Mechanism**. Methods like StreamingLLM often use static sparsity that prioritizes attention on initial/ final tokens, which may discard critical tokens; DGA dynamically groups tokens based on context-dependent importance, ensuring adaptation in dynamic scenarios.\n* **Perfomance Comparisons**. DGA outperforms StreamingLLM by 11.69% EM score (Table 2) with 1.28× speedup (Table I), highlighting both accuracy and efficiency gains.\n\n[r1] Efficient streaming language models with attention sinks. ICLR2024.\n\n>Q2.  The token grouping in Sec 4 has been proposed by KVMerger [r2]. Its clustering-based method seems simpler and more reasonable.\n\n**A2.** Our method differs from KVMerger [r2] in **objective**, **methodology** and **experiments**: \n* **Distinct Objectives**: KVMerger focuses on KV cache compression via Gaussian-kernel-based Key clustering but ignores attention computation redundancy; DGA targets self-attention acceleration in long-context tasks by dynamic grouping, thus **reducing both computation and memory consumption**.\n* **Methodological Differences**: KVMerger uses static Key clustering; DGA groups tokens by context-aware importance, adapting to input variations.\n* **Empirical Validation**: KVMerger lacks self-attention acceleration results; Our Table 3 shows **2.4× speedup** at 16K length with minimal accuracy loss.\n\nWe will include this in our revised paper.\n\n[r2] Model Tells You Where to Merge: Adaptive KV Cache Merging for LLMs on Long-Context Tasks. Arxiv 2024.\n\n>Q3. It seems the author does not mention the supervised learning method in their method section (Sec 5).\n\n**A3.** Sec. 3 reformulates long-context modeling as a supervised learning task (Eq. 2), separating **relevant** (critical for predictions) and **irrelevant** (redundant for context) tokens, motivating **theoretical analysis of sparsity** (Theorem 1–3 in Sec. 4). This **inspires the design of DGA** in Sec. 5, where token relevance (Eq. 4) derived from supervised learning guides dynamic grouping in DGA ($s_i$ in Eq. 16), aggregating redundant tokens while preserving critical interactions. These three sections form a pipeline: **supervised learning identifies redundancy**→**theoretical analysis quantifies sparsity**→**DGA operationalizes efficient computation**. We will clarify this in our paper.\n\n>Q4. The Fig. 2 analysis and ρ-sparse definition seem less reasonable and clear than StreamingLLM's attention sink analysis (see Fig. 2 of StreamingLLM).\n\n**A4.** The ρ-sparse, i.e., $P_{sparse}(L,ρ)$ quantifies the probability of at least one attention weight exceeding $1/(Lρ)$, rigorously measuring how sparsity strengthens with context length $L$. It evaluates a model’s **inherent ability to prioritize critical tokens** in varying contexts, e.g., $P_{sparse}$ rises sharply for $ρ=0.01$ as $L$ grows (Fig. 2b).\n\nCrucially, we note the **different functionality**: StreamingLLM analyzes sparsity for **individual sequences** (e.g., attention maps), while our ρ-sparsity aggregates across **multiple sequences** (Sec. 6.2), offering a **model-level sparsity characterization**.\n\n>Q5. Issues in Tables 1 & 3: (1) Unclear context window lengths. (2) StreamingLLM is slower than vanilla despite pruning.\n\n**A5.** We address concerns:\n* **Context Window**: Models were trained on **8K context** and evaluated on **32K context** (covering 95% of LongBench-E sequences). ITL was at **16K context**.\n* **StreamingLLM Efficiency**: \n    * All methods in Tables 1 and 3 used MInference for consistent evaluation (with full KV caching overhead). \n    * With StreamingLLM’s official code (Table I), ITL stabilizes (36ms) but is higher than DGA-LLM (28ms) as it retains a fixed 4K-token cache, while **DGA dynamically reduces cache size** (e.g., 2576 tokens for 16K).\n\nTable I: ITL (ms) comparisons with official StreamingLLM. \n|Methods|4K|8K|16K|\n|-|-|-|-|\n|StreamingLLM|36.16|36.97|36.87|\n|**DGA (Ours)**|**26.26**|**26.87**|**28.79**|\n\n>Q6. Many related works are missing and the citation (Hastie et al., 2009) is clearly inappropriate.\n\n**A6.** We will carefully discuss these works according to the reviewer's suggestions.", "claims_and_evidence": "1. The LLM sparsity discovered in Sec 4 has actually already been revealed in several previous works (such as StreamingLLM).\n2. The approach proposed in Sec 4 of performing grouping for tokens has already been proposed (see KVMerger \"MODEL TELLS YOU WHERE TO MERGE: ADAPTIVE KV CACHE MERGING FOR LLMS ON LONG-CONTEXT TASKS\"). Moreover, I believe the clustering-based approach used by KVMerger is simpler and more reasonable than the grouping method in this paper.\n3. In Section 3, the author proposes using supervised learning to achieve long context feature extraction. However, it seems the author does not mention the supervised learning method in their method section (Sec 5).", "methods_and_evaluation_criteria": "1. The analysis in Figure 2, as well as the definition of ρ-sparse, is not as reasonable and clear as the analysis of attention sink in StreamingLLM (see Figure 2 of StreamingLLM).\n2. Table 1 in the paper has issues: (1) The context window length setting is not specified by the author. (2) Since StreamingLLM performs token pruning, its inference efficiency should be much higher than the original model (LLaMA2-7B). However, in this table, StreamingLLM's speed (ITL) has decreased. \n3. Similar issues appear in Table 3. StreamingLLM's inference efficiency should be almost unaffected by text length because it directly truncates text using a sliding window.", "theoretical_claims": "No", "experimental_designs_or_analyses": "Please see Methods And Evaluation Criteria", "relation_to_broader_scientific_literature": "See Claims And Evidence.", "essential_references_not_discussed": "Many related work are about grouping/clustering tokens in long-context LLM, such as KVMerger, PQCache: Product Quantization-based KVCache for Long Context LLM Inference, ClusterKV: Manipulating LLM KV Cache in Semantic Space for Recallable Compression", "other_strengths_and_weaknesses": "The author has a very strange citation: they even included a citation for supervised learning (Hastie et al., 2009). This citation is clearly inappropriate.", "other_comments_or_suggestions": "No", "questions_for_authors": "See Claims And Evidence and Methods And Evaluation Criteria", "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": "sX9AEwOxiM", "reviewer": "Reviewer_HvaA", "summary": "This paper addresses the computational inefficiency in Transformer-based models for long-context modeling caused by redundant attention computations. The authors reformulate probabilistic sequence modeling as a supervised learning task, providing a theoretical foundation for analyzing redundancy. Building on this, they propose a group coding strategy to aggregate less important tokens and introduce Dynamic Group Attention (DGA), which dynamically groups non-focal tokens while preserving critical interactions. Experimental results show that DGA reduces computational costs while maintaining competitive performance on long-context benchmarks.", "questions": "", "limitations": "", "rating": 4, "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 thank the reviewer for the encouraging comments and suggestions. Responses are below:\n\n>Q1. \"...**clear theoretical insights**...**deepen the understanding** of the redundancy in the attention, providing a **foundation** for the proposed method...\", \"...**comprehensive empirical results**...The comparative evaluation provides **sufficient evidence** to support the authors' claims\", \"...**different from the existing method** like MInference and StreamLLM that directly discard some tokens\".\n\n**A1.** We sincerely appreciate your thoughtful and encouraging feedback on our work. Your acknowledgment of the theoretical insights into attention redundancy, along with the robust empirical validation, is greatly appreciated. We are also grateful for highlighting how our method innovatively diverges from approaches like MInference and StreamLLM by avoiding token discarding. These comments underscore the significance of our contributions, motivating us to further advance research in this domain.\n\n>Q2. Some statements in Section 5 are confusing. The authors first mention that they divide the tokens into two parts. However, in Eqn. 12, I found the tokens are segmented into three parts.\n\n**A2.** We appreciate the reviewer’s careful observation and clarify the token partitioning strategy:\n* **Two-Part Token Partitioning**: Tokens are divided into **focal** and **non-focal** (redundant) groups based on their importance scores.\n* **Complementary Tokens for Autoregressive Integrity**: To address potential information loss caused by grouping (e.g., some tokens cannot access the group information due to the autoregressive nature), we introduce **complementary KV pairs** (third part in Eq. 12) to restore missing dependencies. \n\n>Q3. Some notations are hard to understand, such as $min G_i$ in line 315. I guess it denotes the minimum index in the group index $G_i$, right?\n\n**A3.** Yes. $min G_i$ is used to identify the earliest token position in the group. We will clarify these notations in the revised manuscript to improve readability.\n\n>Q4. In Eqn 17, the authors use a small set of queries to estimate the attention weights. However, what if we only have one query token in the decoding stage?\n\n**A4.** In the decoding stage with only one query token, our method adapts as follows:\n* **Initial Generation Phase (Token Count < m)**: When fewer than $m$ tokens (group size) are generated, we directly compute attention using standard full self-attention (without grouping) to ensure accurate context capture. This avoids instability in weight estimation with limited tokens.\n* **Subsequent Generation (Token Count ≥ m)**: Once $m$ tokens are generated, we leverage the **query of the last token** in the current group to compute weights *P* (Eqn. 14). This query implicitly encodes dependencies on prior tokens through its positional encoding, enabling reliable importance estimation.\n\n>Q5. In Table 3, are all the methods tested with Flash Attention?\n\n**A5.** No. To ensure fair comparisons, none of the methods in Table 3 use Flash Attention because StreamingLLM's official implementation lacks support for it. However, our approach is compatible with Flash Attention optimizations (e.g., block matrix operations), which could further enhance performance in future implementations.\n\n>Q6. The method introduces complementary tokens to recover masked information during autoregressive generation. However, I would like to understand the impact of these complementary tokens on the model's inference performance, such as latency and overall accuracy.\n\n**A6.** Our ablation study (Table I below) shows complementary tokens are critical: removing them significantly degrades performance (21.14→20.33) on Longbench-E by **3.8%↓**. While they incur a slight latency increase (24.9ms→28.8ms), this remains **2.4–3.5× faster** than vanilla self-attention (Table 2: 69.70–102.22 ms).\n\nTable I: Effect of complementary tokens, where we train LLaMA2-7B on 8K context-length texts over SlimPajama and test on Longbench-E.\n|Methods|Single Doc. QA|Multi Doc. QA|Summar.|FS learning|Synthetic|Code|Avg.|ITL (ms)|\n|-|-|-|-|-|-|-|-|-|\n|w/o comple. tokens|6.43|2.37|8.47|53.69|3.04|48.00|20.33|24.9|\n|DGA-LLM (Ours)|3.61|3.58|6.81|57.90|1.47|53.45|21.14|28.8|\n\n>Q7. In Algorithm 1, can the proposed method conduct attention parallelly? I found that the proposed method seems to calculate attention for different query Q_i separately in line 8 of the algorithm.\n\n**A7.** Yes. While Algorithm 1 describes sequentially for clarity (e.g., line 8), our implementation uses batched matrix operations and GPU parallelism to process all queries in parallel.\n\n>Q8. Some titles appear odd and awkward, such as “C.4. Implementation Details on Sparsity” and “C.5. Implementation Details on Optimization Efficiency.” 10. What is the meaning of the subfigures a b c and d in Figure 5?\n\n**A8.** We will revise the appendix titles for clarity and add clear captions for the subfigures in Figure 5.", "claims_and_evidence": "The claims in the paper are supported by clear evidence.", "methods_and_evaluation_criteria": "The methods presented in the paper are well-motivated, but I still have some question:\n1. Some statement in Section 5 is confusing. The authors first mention that they divide the tokens into two parts. However, in Eqn. 12, I found the tokens are segmented into three parts.\n2. Some notations are hard to understand, such as $min G_i$ in line 315. I guess it denote the minimum index in the group index $G_i$, right?\n3. In Eqn 17, the authors use a small set of query to estimate the attention weights. However, what if we only have one query token in the decoding stage?", "theoretical_claims": "I have thoroughly reviewed the theoretical claims presented in the manuscript, including the proposed theorems and their corresponding proofs. The authors offer clear theoretical insights. They rigorously establish the sparsity of attention weights (e.g., Theorem 1 on sparsity bounds), showing that only a small subset of tokens significantly contributes to predictions. Subsequently, they link the optimization in attention with group coding and show its improved robustness (Theorem 2) and optimization efficiency (Theorem 3). These thorough analyses deepen the understanding of the redundancy in the attention, providing a foundation for the proposed method to address the computational inefficiency in transformers.", "experimental_designs_or_analyses": "The authors conducts comprehensive empirical results that validate the effectiveness of DGA. The experiments on LongBench-E and EM score show significant reductions in computational costs and inter-token latency while maintaining competitive performance on various long-context tasks. The significant latency reduction underscores its practical utility for real-world applications requiring efficient long-context processing. Besides, the authors compare the proposed method with a wide range of baseline methods, including MInference and StreamLLM. The comparative evaluation provides sufficient evidence to support the authors' claims. I still have some questions:\n1. In Table 3, are all the methods tested with Flash Attention?\n2. The method introduces complementary tokens to recover masked information during autoregressive generation. However, I would like to understand the impact of these complementary tokens on the model's inference performance，such as latency, and overall accuracy.", "relation_to_broader_scientific_literature": "The proposed method seems to reduce the redundancy of the attention, different from the existing method like MInference and StreamLLM that directly discard some tokens.", "essential_references_not_discussed": "The authors clearly discussed key methodologies in the field of efficient attention.", "other_strengths_and_weaknesses": "1.\tIn Algorithm 1, can the proposed method conduct attention parallelly? I found the proposed method seems to calculate attention for different query Q_i separately in line 8 of the algorithm.", "other_comments_or_suggestions": "1.\tSome titles appear odd and awkward, such as “C.4. Implementation Details on Sparsity” and “C.5. Implementation Details on Optimization Efficiency.”\n2.\tWhat is the meaning of the subfigures a b c and d in Figure 5?", "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": "fEFv5x2bah", "reviewer": "Reviewer_Q8qd", "summary": "In this paper, the authors propose a novel approach called Dynamic Group Attention (DGA) to address the computational inefficiencies in long-context modeling for transformer-based large language models. DGA leverages a group coding strategy to dynamically aggregate less important tokens while preserving critical token interactions. The approach aims to reduce redundancy in attention computations without sacrificing model performance. Through theoretical analysis, the authors demonstrate the robustness of the group coding mechanism and its ability to improve learning efficiency. Extensive experiments on the LongBench-E benchmark validate the effectiveness of DGA, showing significant reductions in computational costs while maintaining competitive performance across various long-context tasks.", "questions": "", "limitations": "", "rating": 4, "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 thank the reviewer for the encouraging comments and detailed suggestions. Responses are below:\n\n>Q1. \"...**solid evidence** from **theoretical analysis** and **extensive experiments**\", \"...**theoretical analysis clearly demonstrates** how DGA reduces computational redundancy...**well-justified and aligns perfectly with** the experimental results\", \"...comparison...**comprehensive evaluation**...\", \"...incorporate **a variety of experiments**...\", \"...addressing **significant gaps** in long-context modeling...\"\n\n**A1.** We are deeply appreciative of your thoughtful comments. The recognition that DGA’s redundancy reduction theory aligns with experimental results shows our approach's rigor. We appreciate your focus on comprehensive evaluation, including baseline comparisons and ablation studies, inspiring us to further develop solutions in this domain.\n\n>Q2.  From Fig. 1, grouping seems to reorder tokens. Could this introduce significant overhead for longer sequences?\n\n**A2.** No. The reordering operation introduces **minimal overhead** even for long sequences. From Table I, the repositioning time ratio increases only marginally (12.5%→15.8%) as context length grows from 4K to 16K, demonstrating scalability. Thus, the benefits of dynamic grouping (e.g., 2.4–3.5× latency reduction) far outweigh this minor cost.\n\nTable I: Percentage of total attention computation time for reordering operation across different sequence lengths (Table 3 settings).\n|Context Length|4K|8K|16K|\n|-|-|-|-|\n|Ratio|12.5%|15.6%|15.8%|\n\n>Q3. The paper needs clarity on method details, e.g., group window size consistency prefill-decoding, and token importance determination in decoding.\n\n**A3.** In decoding, we use a slightly larger group size ($m' = 1.1m$, e.g., 16→18) with 10% slots for focal tokens. Focal tokens are selected via top-10% attention weights from the group’s last token when a group reaches $m'$, ensuring adaptive prioritization and aligning with training principles. We'll clarify in revisions.\n\n>Q4. How are threshold values (e.g., ρ) chosen? Are they dataset-specific and generalizable?\n\n**A4.** The threshold $ρ$ is chosen based on sequence length $L$ ($ρ \\in (1/L,1]$), with smaller $ρ$ enforcing stronger sparsity. Table II shows $P_{sparse}$ has **nearly identical trends** across SlimPajama and WikiText2, confirming ρ generalizes across datasets. As $ρ=0.01$, $P_{sparse}$ increases sharply with $L$, proving sparsity strengthens with context length universally. So, **ρ is dataset-independent and adapts to $L$**.\n\nTable II: Estimations of $P_{sparse}(L,ρ=0.01)$ across lengths (Fig. 2 settings).\n|L|100|200|300|400|500|600|700|800|900|1000|\n|-|-|-|-|-|-|-|-|-|-|-|\n|WikiText2|0.14|0.68|0.86|0.93|0.94|0.99|1.00|1.00|0.99|1.00|\n|SlimPajama|0.09|0.65|0.86|0.95|0.97|0.97|0.99|1.00|1.00|0.99|\n\n>Q5. Ablation study on complementary tokens, assessing impact on model performance (efficiency & accuracy).\n\n**A5.** Our ablation study (Table III) shows complementary tokens are critical: removing them significantly degrades performance on tasks like Multi-Doc QA (3.58→2.37) and Code (53.45→48.00). They slightly increase latency (24.9ms→28.8ms), but are still **2.4–3.5× faster** than vanilla self-attention (Table 2: 69.70–102.22ms).\n\nTable III: Effect of complementary tokens (Table 1 settings).\n|Methods|Single Doc. QA|Multi Doc. QA|Summar.|FS learning|Synthetic|Code|Avg.|ITL (ms)|\n|-|-|-|-|-|-|-|-|-|\n|w/o comple. tokens|6.43|2.37|8.47|53.69|3.04|48.00|20.33|24.9|\n|DGA-LLM (Ours)|3.61|3.58|6.81|57.90|1.47|53.45|21.14|28.8|\n\n>Q6. The proposed method relies on long-context token importance sparsity. In lower-sparsity tasks like summarization, its performance seems less effective. Any potential solutions for such scenarios?\n\n**A6.** For lower-sparsity tasks (e.g., summarization), our method can adjust group size m for balance performance and efficiency. Reducing m from 16 to smaller values (e.g., m = 2) improves summarization performance (9.53→6.81) but increases ITL (53.0ms→28.8ms). We will explore dynamic m-adjustment in future work.\n\nTable IV: Comparisons of inference performance for different group sizes (m=2→m=16) on LongBench-E.\n|**Task**|**vanilla self-attention**|**2**|**4**|**8**|**16 (default)**|\n|:-:|:-:|:-:|:-:|:-:|:-:|\n|Single Doc. QA|6.43|5.68|4.93|3.04|3.61|\n|Multi. Doc. QA|2.37|5.40|4.43|4.74|3.58|\n|Summar.|13.65|9.53|8.36|7.30|6.81|\n|ITL(ms)|69.7|53.0|38.3|33.5|28.8|\n\n>Q7. Provide detailed computational complexity analysis of sparse attention mechanism for prefill and decoding stages.\n\n**A7.**  Thanks for the suggestion. Let $L$, $r$, and $m$ denote the context length, the number of focal tokens, and the group size. \n* **Prefilling stage**: Complexity is $O(Lr+L\\frac{L-r}{m}+Lm)$, simplifying to $O(\\frac{L^2}{m})$ for constants $m$ and $r$, significantly lower than vanilla self-attention’s $O(L^2)$.\n* **Decoding stage**:, Per-token complexity is $O(r+\\frac{L-r}{m} + m)$, significantly lower than vanilla’s $O(L)$ for large $m$.", "claims_and_evidence": "This work successfully demonstrates the potential of Dynamic Group Attention (DGA) in addressing computational inefficiencies in long-context modeling for transformer-based large language models. The paper's claims are supported by solid evidence from theoretical analysis and extensive experiments.", "methods_and_evaluation_criteria": "The methods presented in the paper are well-suited for the challenges of long-context modeling in transformer-based large language models.\nMy questions are:\n1.\tFrom Figure 1, it appears that the grouping operation involves reordering the tokens. When handling longer sequences, could this reordering introduce significant additional overhead?\n2.\tThe paper would benefit from further clarification of certain method details. Specifically, it is unclear whether the group window size is consistent between the prefill and decoding stages. Additionally, more information is needed on how token importance is determined during the decoding stage.", "theoretical_claims": "The theoretical claims in this paper are highly solid and well-supported. The introduction of Dynamic Group Attention (DGA) and its group coding strategy represents a significant innovation in addressing the challenges of long-context modeling. The theoretical analysis clearly demonstrates how DGA reduces computational redundancy and improves efficiency by dynamically aggregating less important tokens. This is well-justified and aligns perfectly with the experimental results, further validating the effectiveness of the method. The paper's theoretical background provides a strong foundation for understanding the improvements in attention mechanisms and model performance. Overall, the theoretical contributions contribute greatly to the novelty and impact of the work.", "experimental_designs_or_analyses": "The experimental designs and analyses presented in the paper are sound and robust.\n1.The paper compares the proposed Dynamic Group Attention (DGA) with several baseline methods, including standard self-attention and other attention optimization techniques, providing a comprehensive evaluation of the method's performance.\n2.The authors incorporate a variety of experiments, including comparisons on the LongBench-E benchmark, performance testing across multiple tasks, and inference efficiency evaluations, offering a solid foundation for validating the effectiveness of DGA.\n3.Ablation studies are conducted to assess the contribution of key components, such as the group coding strategy and dynamic token aggregation, further supporting the claims of the method's benefits.\nMy questions are:\n    How are the values of the thresholds (e.g., $\\rho$) chosen? Are these values specific to certain datasets, and can they generalize across different datasets?\n    It would be beneficial to include an ablation study on the complementary tokens, specifically evaluating their impact on the model's performance, particularly in terms of efficiency and accuracy.", "relation_to_broader_scientific_literature": "The key contributions of this paper are strongly rooted in the existing literature, addressing significant gaps in long-context modeling for transformer-based large language models.", "essential_references_not_discussed": "The paper addresses key references relevant to its contributions. However, there is an existing method that uses dynamic grouping to accelerate attention[A]. It would be better to provide a more detailed discussion on how the proposed method differs from this.\n[A] Dynamic Group Transformer: A General Vision Transformer Backbone with Dynamic Group Attention. (IJCAI 2022)", "other_strengths_and_weaknesses": "The proposed method relies heavily on the sparsity of the long-context tokens' importance. However, in tasks with relatively lower sparsity, such as summarization, the method's performance seems to be less effective. Are there any potential solutions or adjustments that could improve its performance in such scenarios?", "other_comments_or_suggestions": "NA", "questions_for_authors": "1.\tCan you provide a detailed computational complexity analysis of the proposed sparse attention mechanism, specifically for both the prefill and decoding stages?", "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": "iYSgQYZrMt", "reviewer": "Reviewer_VyKb", "summary": "This paper explores the challenge of the curse of dimensionality in Transformer architectures for long-context modeling, with a particular focus on redundant attention computations. To address this issue, the authors introduce a novel approach called Dynamic Group Attention (DGA), which minimizes redundant computations by dynamically grouping and aggregating less critical tokens while preserving essential token interactions. They redefine traditional probabilistic sequence modeling as a supervised learning task and conduct a theoretical analysis of attention sparsity in Transformers, showing that only a small subset of tokens has a significant impact on predictions. Furthermore, they frame attention optimization as a linear coding problem and develop the DGA mechanism to dynamically manage token grouping and aggregation. Experimental results indicate that DGA effectively lowers computational costs while maintaining strong performance.", "questions": "", "limitations": "", "rating": 4, "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 really appreciate the reviewer's kind words and detailed suggestions. Here are our responses:\n\n>Q1. \"...**well-structured and insightful theoretical analyses**... **strong foundation**...\", \"The experimental designs...are **well-structured and robust**...\", \"...theoretical exploration offers a **fresh perspective** on understanding redundancy\", \"...**flexibility and efficiency**... **potential applicability to other tasks**...\", \"...successfully lowers computational costs **without compromising model performance**, demonstrating strong **practical value**\".\n\n**A1.** We sincerely thank the reviewer for their insightful feedback. We appreciate the recognition of our theoretical rigor in analyzing Transformer redundancy and the robust experimental validation demonstrating DGA’s efficiency-performance balance. The highlighted flexibility and practical value of our approach motivate us to explore broader applications in future work.\n\n\n>Q2. DGA mitigates redundancy well, but its implementation and understanding are complex. The dynamic grouping and aggregation strategy needs precise control, increasing implementation difficulty and debugging costs.\n\n**A2**. Thanks for your insightful comments. To address this concern, we will add a PyTorch-style pseudocode in the revised manuscript. Our approach leverages standard PyTorch operations, including matrix multiplication, `topk` selection, and tensor slicing, all of which are widely used and well-optimized within modern deep learning frameworks. We believe that this additional clarification will help elucidate the implementation. \n\n>Q3. >Q3. DGA depends on hyperparameters like $m$, $\\gamma$, affecting performance. The paper examines their impact, but finding optimal values in practice is hard. Deeper discussion on selection would help.\n\n**A3**. Experimental analysis in Tables 4 and 6 reveals that smaller group sizes ($m$) and higher importance rates ($\\gamma$) improve performance at the cost of increased latency. Based on these, we recommend the following practical guidelines for parameter selection: For resource-constrained scenarios, larger $m$ and lower $\\gamma$ balance acceptable performance with reduced complexity. Performance-critical applications (e.g., medical diagnosis) benefit from minimal $m$ and maximal $\\gamma$ to preserve accuracy, whereas latency-sensitive tasks (e.g., real-time systems) require moderate $m$ and lower $\\gamma$ for responsiveness. \n\nAn adaptive framework to automatically optimize ($m$, $\\gamma$) based on application-specific accuracy-latency trade-offs remains a promising direction for future work.\n\n>Q4. Can the proposed method be integrated with FlashAttention optimization strategies to achieve further acceleration? Additionally, does it support KV-Cache techniques?\n\n**A4**. Yes, the proposed DGA method is compatible with FlashAttention and KV-Cache optimizations. For KV-Cache, DGA retains only 0.32–2.51GB of KV states on context-length 4K-32K (Table I), a 78–98% reduction compared to vanilla self-attention.\n\nTable I: Comparison of KV-Cache (GB) with Vanilla self-attention.\n| Methods | 4K | 8K | 16K | 32K |\n|---|---|---|---|---|\n| Vanilla self-attention | 2 | 4 | 8 | 16 |\n| DGA (Ours) | 0.32 | 0.63 | 1.26 | 2.51 |\n\n>Q5. Do the baseline methods used for comparison incorporate FlashAttention or KV-Cache when evaluating latency?\n\n**A5**. No. FlashAttention is not used in any method (including ours) to ensure fair comparison, as StreamingLLM's official implementation lacks support. All compared methods (including baselines and our DAG) employed standard KV-Cache techniques.\n\n>Q6. Some formulas in the appendix are missing periods or commas, such as Equation 36, 42.\n\n**A6**. We will fix it.\n\n>Q7. The method works for long text modeling. But it's unclear if DGA can be applied to other long sequence tasks (e.g., video, audio processing). Without extra experiments, could the authors discuss this potential application?\n\n**A7**. We appreciate the reviewer’s insightful question regarding the broader applicability of DGA. While our current work focuses on long-text modeling, the proposed Dynamic Grouping Attention (DGA) mechanism is inherently task-agnostic and could generalize to other long-sequence domains (e.g., video/audio) where redundancy exists in sequential tokens and adaptive token importance assessment is critical. For instance:\n* **Video Processing**: Temporal sequences in videos often exhibit localized redundancy (e.g., static backgrounds or repetitive motions). DGA could dynamically group less informative frames while preserving critical temporal segments.\n* **Audio Processing**: Long audio signals contain silent or redundant segments. DGA’s importance scoring could prioritize phonetically rich regions, enabling efficient compression.\n\nWe will include the above discussions in our revised paper.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are well-suited to the problem, but I still have some concerns:\n\n* While the DGA mechanism effectively mitigates redundant computations, its implementation and understanding are relatively complex. The dynamic grouping and aggregation strategy requires precise control, which may increase implementation difficulty and debugging costs.\n\n* The DGA mechanism depends on several hyperparameters, such as the group size $m$ and the importance rate $\\gamma$, which significantly influence both model performance and computational efficiency. Although the paper examines their impact experimentally, determining the optimal values in real-world applications remains challenging. A more in-depth discussion on hyperparameter selection would be beneficial.", "theoretical_claims": "I have thoroughly reviewed the theoretical claims presented in the manuscript, including the proposed theorems and their corresponding proofs. The authors provide well-structured and insightful theoretical analyses that contribute valuable perspectives on the problem. This paper offers a rigorous and comprehensive understanding of redundancy in transformer-based long-context modeling, effectively identifying redundant tokens, providing probabilistic insights into attention sparsity, and introducing a robust optimization strategy through group coding. These theoretical contributions serve as a strong foundation for developing more efficient and effective attention mechanisms, as exemplified by the proposed Dynamic Group Attention mechanism.", "experimental_designs_or_analyses": "The experimental designs and analyses in the paper are well-structured and robust.\n\n* The authors compare the proposed method against a diverse set of baseline approaches, including MInference and StreamLLM, using LongBench-E and EM scores. The results demonstrate significant reductions in computational costs and inter-token latency while maintaining competitive performance across various long-context tasks.\n\nMy questions are:\n\n* Can the proposed method be integrated with FlashAttention optimization strategies to achieve further acceleration? Additionally, does it support KV-Cache techniques?\n\n* Do the baseline methods used for comparison incorporate FlashAttention or KV-Cache when evaluating latency?", "relation_to_broader_scientific_literature": "The authors clearly identify the issue of computational redundancy in Transformer-based long-context modeling and substantiate its presence through both theoretical analysis and empirical validation, establishing a strong foundation for further optimization.\n\nBeyond introducing a novel method, the authors conduct an in-depth theoretical analysis of attention weight sparsity, reformulate the attention optimization problem as a linear coding issue, and propose a group coding strategy within this framework. This theoretical exploration offers a fresh perspective on understanding redundancy in Transformers.\n\nWhile the paper primarily focuses on long-context modeling, the flexibility and efficiency of the Dynamic Group Attention (DGA) mechanism suggest its potential applicability to other tasks involving long-sequence processing, such as video and audio analysis. This highlights the broad applicability of the proposed method.", "essential_references_not_discussed": "The authors clearly discussed key methodologies in the field of efficient attention.", "other_strengths_and_weaknesses": "* The proposed Dynamic Group Attention (DGA) mechanism introduces a novel strategy for optimizing attention mechanisms. By dynamically grouping and aggregating less important tokens, it effectively reduces redundant computations while preserving essential token interactions. This approach successfully lowers computational costs without compromising model performance, demonstrating strong practical value.\n\n* The authors conduct extensive experiments across multiple long-context modeling tasks, including the LongBench-E benchmark. The results show that DGA not only reduces computational costs but also maintains or even outperforms existing methods in terms of performance. Notably, in long-text generation tasks involving extensive context lengths (e.g., 16K), DGA significantly reduces generation latency, underscoring its efficiency and suitability for long-context applications.", "other_comments_or_suggestions": "Some formulas in the appendix are missing periods or commas, such as Equation 36, 42.", "questions_for_authors": "The method in this paper is effective for long sequence text modeling. However, it remains unclear whether the proposed DGA mechanism can be applied to other long sequence processing tasks or architectures like video and audio processing. Without extra experiments, it would be great if the authors could discuss this potential application.", "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 presents a theoretically grounded and empirically validated method—Dynamic Group Attention (DGA)—to reduce redundant attention computation in long-context Transformers. The authors introduce a supervised learning-based formulation of attention sparsity and reformulate attention optimization as a group coding problem, supporting their claims with rigorous theorems and competitive performance on LongBench-E. While DGA shows clear improvements in latency and efficiency over baselines, some concerns remain regarding novelty relative to prior work (e.g., StreamingLLM, KVMerger) and clarity in method description. The authors provide detailed rebuttals addressing these issues, and while not all comparisons are compelling, the theoretical contributions and strong empirical results are valuable.
Decision: Accept (poster)