Radar: Fast Long-Context Decoding for Any Transformer
Authors: Yongchang Hao
Mengyao Zhai
Hossein Hajimirsadeghi
Sepidehsadat Hosseini
Frederick Tung
Venue: ICLR 2025 Poster (2025)
Keywords: Long-context decoding
Large language models
Inference acceleration
Random features
Primary area: foundation or frontier models, including LLMs

Abstract: Transformer models have demonstrated exceptional performance across a wide range of applications. Though forming the foundation of Transformer models, the dot-product attention does not scale well to long-context data since its time requirement grows quadratically with context length. In this work, we propose Radar, a training-free approach that accelerates inference by dynamically searching for the most important context tokens. For any pre-trained Transformer, Radar can reduce the decoding time complexity without training or heuristically evicting tokens. Moreover, we provide theoretical justification for our approach, demonstrating that Radar can reliably identify the most important tokens with high probability. We conduct extensive comparisons with the previous methods on a wide range of tasks. The results demonstrate that Radar achieves the state-of-the-art performance across different architectures with reduced time complexity, offering a practical solution for efficient long-context processing of Transformers. The code is publicly available at https://github.com/BorealisAI/radar-decoding.

Published as a conference paper at ICLR 2025
RADAR: FAST LONG-CONTEXT DECODING FOR ANY TRANSFORMER
Yongchang Hao"
Mengyao Zhai
University of Alberta & RBC Borealis
RBC Borealis
yongchal (Qualeertt wwerteera...
rengyao. @boreal isai i. coom
Hossein Hajimirsadeghi
Sepidehsadat Hosseini
RBC Borealis
RBC Borealis
hossein ha wng.g//aiirsddggntorrreeesse....
sepid. www.sossseeiiicmmmm wtwasseeiiitooralisaa....o
Frederick Tung
RBC Borealis
frederick cung@borcallssa..com
ABSTRACT
Transformer models have demonstrated exceptional performance across a wide range of applications. Though forming the foundation of Transformer models, the dot-product attention does not scale well to long-context data since its time requirement grows quadratically with context length. In this work, propose Radar, a training-free approach that accelerates inference by dynamically search- ing for the most important context tokens. For any pre-trained Transformer, Radar can reduce the decoding time complexity without training or heuristically evicting tokens. Moreover, we provide theoretical justification for our approach, demon- strating that Radar can reliably identify the most important tokens with high probability. We conduct extensive comparisons with the previous methods on a wide range of tasks. The results demonstrate that Radar achieves the state-of- the-art performance across different architectures with reduced time complexity, offering practical solution for efficient long-context processing of Transform- ers. The code is publicly available at atthtps::/ /ttp:://ittttubuuu cwt/:occc/oooeooo com.//eaa///////./// radar-decoding
INTRODUCTION
Transformer models demonstrate an extraordinary ability on different sequential processing tasks, including language modeling Vaasaani et al. 2017]] Devlin et al.) 2019 Raffel et al. 2020 Touvron ctt al., 2023b)), image classification (Dosovitskiy et al. [202] Liu et al. 2021 Hassani et al. 2022
Zhu et al. 2023). translation (Tang et al. 2020 Yao & Wan 2020), and many more (Carion al.
2020 Ding et al. 2022 Chang et al. 2023; Xu et al.] [022 Fang et al. 2023 In particular, Trans- former models take each input as sequence of tokens and compute the embedding of each token for downstream tasks. Among all components, the dot-product attention has been shown to be critical the success of Transformer models (Choromanski
2021). It not only enables parallel com- putation of sequences during training (Vyas et al. 2020), but also provides a high-quality method sequence modeling (Sanford et al. (2023).
Despite being at the core of Transformer models, the dot- attention is not ideal for long- context data: the time to process each token increases with context lengths, significantly slowing down the throughput on long mong-contxtt data. Moreover, the maximum context length is limited during training, resulting in an inability to perform inference on long-context tasks. Yet, many real-world applications are naturally long-context (Tay et al., 2021 Beltagy et al. 2020: Wu et al. 2024). For example, code file could have more than 10K tokens (Lozhkov et al.
2024 Kocetkov al. 2022)
Work done during intersship RBC Borealis.

---

Published as a conference paper at ICLR 2025
However, Llama-2 Touvron et al. 2023b), widely used Transformer- bassed model, is incapable of processing the full source code because it has a maximum context length of 4K tokens.
To improve Transformer's long-con context performance. line of research proposes replace the orig- inal attention with some faster variants (Xiao et al. 2024| Peng et al. 2021; Bertsch et al 2023
Beltagy al., 2020 Choromanski et al. Mohtashami & Jaggi 2023 Peng et al. 2023 One notable example is attention kernelization, which reformulate the not-product attention as a kernel and approximate the kernel with linear operations (Peng al. (021). By reordering the matrix chain multiplication, kernelization methods reduce the time complexity to O(t) for the context of length However, such methods require training process fit the approximations, which becomes more and more infeasible given the fast parameter scaling of the current Transformer models.
Without the need for training, another line of work accelcrates inference by evicting previous tokens used in each decoding step (Xiao et al.) 2024 Zhang et al. 2023 Li et al. 2024). For instance, StreamingL.LM (Xiao et al. 2024) proposes to only use the constant-lengthn recent tokens and discard all other but the first tokens. Although they are faster in inference on long-context data, these methods lose previous information in the context that is potentially critical for future use. Using the code file an example, StreaningLLM could fail to invoke a function if the function declaration is not in the recent tokens.
In this paper, propose Radar (range search accelerated by random features), training-frre ap- proach that dynamically selects the important context ranges to accelerate inference. Specifically, Radar groups the context into segments and maintains "summarization representation" for each group by random projections. To generate a new token, Radar calculates the importance of each group and selects only the tokens in the most important segments. We theoretically justify our approach by showing that Radar is guaranteed to pick the most dominant tokens with high proba- bilities. For any pre-trained Transformers, our approach can instantly extend the maximum context length while reducing the overall complexity to O(t)-5).
We conduct extensive experiments verify the effectiveness of our approach. Specifically, compared our method with StreamingLLM (Xiao et al. 2024). Landmark attention (Mohtashami & Jaggi 2023). H₂O (Zhang et al., 2023), and SnapKV (Li al. 2024p. The results across dif- ferent models and tasks show that Radar generally achieves state-of-the-ee performance with a low time complexity. Additionally, our in-depth analyses, while providing detailed information, highly corroborate our main results.
2 METHODOLOGY
In this section, we present Radar, a principled approach that is guaranteed to select the most impor- tant tokens with high probability. We first introduce the notations and the problem formulation in Section 2.1 The algorithm of Radar is formally presented in Section 2.2 with a major focus on showing the time complexity. The correctness of our algorithm rigorously shown in Section 2.3
2.1 BACKGROUND
Dot-product attention. Without loss of generality, we focus on the single-head self-attention for simplicity. Specifically, it operates on the level of sequence. Each sequence contains several token embeddings 1æ...... 2x), where every embedding is vector in the high dimensional space Rdd The attention first maps each embedding to query, key, and values by linear projections (g: WGR, k; WAD; and v; W..:). The attention score is defined as
1 I(j < exp lt/VVd] zz
oi
for 1 S i,j < t. Here, is normalization factor such that Σj=1 Cijj = 1. The dot-product attention then produces a sequence by
O
Us Vi
j=1
indicating that o; is fusion of (vi,..., v;) weighted by the attention scores (ai,1y...,, (i.i)-
2

---

Published as a conference paper at ICLR 2025
dalkss)
0..
@etle))..
01
Aodhual dalkss) Bust
(isla)
Nm
(a) Construction process a single segment consists of three tokens k4.6- Radar first maps cach token embed- ding the random feature dn (k.). The segment embedding Φr (k=:6) average of random features.
(b) Query process for single query q. The query token is first mapped to the random feature Φn (q). The segment importance is obtained by inner products between random features Φn (g))) (k.ce2) In this example, the second segment has the highest (unnormalized) segment attention of 2.2.
Figure 1: Overview of the approach.
The equations above show that the dot-product attention requires O(t) generate token, resulting in an overall ((22) time for the whole sequence. To reduce the complexity of the dot- product attention, both operations should not be quadratic in t.
Context reduction. Without the need for training, one popular strategy for accelerating inference reduce the number tokens used in attention calculation. LongFormer (Beltagy et 2020) proposes to use local sliding window attention, which only needs to look into the tailing tokens, to accelerate decoding. More recently, StreamingLLM (Xiao et al., (024) improves this by prepending sink tokens to stabilize the decoding for contexts beyond the pre-training length. However, these methods suffer from the issue of information loss, where the vast amount of middle tokens poten- tially containing important information are permanently lost. Other remedies such as the heavy- hitter oracle (HzO) use heuristics to partially retain some middle tokens. Despite this, they depend on heuristic rules and sometimes fail to completely prevent information loss.
Problem formulation. Given Equation 2 the attention score a,, represents the importance of the jth token to the current step To ensure the selected tokens are important, we would like to select an index set that
j E arg topk di,7 IsISi
for all j E S. This gives approximation of the original attention and reduces the compute O(S)). However, generating such an index set takes O(t) time, failing to improve the overall time complexity. We aim approximately solve this problem sublinear time complexity.
2.2 THE PROPOSED ALGORITHM: RADAR
This section shows the algorithm of Radar with a focus on analyzing the time complexity. The correctness of the algorithm is deferred to Section 2.3
Hierarchical structure. We manage the key embeddings (kI,..., kj) with a hierarchical data structure consisting two layers of nodes. The bottom- layommllyynnodeee are the original key embeddings, whereas each top-layer node is a segmení consisting of the bottom keys. The hierarchical structure enables a two-step attention calculation procedure: for the first step, we search for the important segments with the highest summed attention score; after that, use the tokens in the selected segments to approximate the attention for attention calculation.
The benefit of applying the hierarchical paradigm is reducing the time complexity. Assume there are tokens and each segment contains tokens on average, then the overall query complexity O(r(c) . t/c c). where ((T(c)) is the time complexity to obtain the importance score for segment. The term O(t/c) comes from calculating the importance [t/c] segments and selecting the top ones; and the second term O(c) is for the actual attention by Equations (T) and (2).
3

---

Published as a conference paper at ICLR 2025
Accelerated segment search. To accelerate the segment search, propose to assign each seg- ment node representation that "summarizes" the bottom-layer key embeddings. We resort to the attention kemelizatiin technique to accomplish this. Specifically, first apply mapping Φn Rd - IR" in (Choromanski et al. 2021) for all keys
(k)k) = Vn exp(ww] k' _I. -1111/1)
Here, every element Q Rnxd is sampled from No,1 and the vector wi E Rd the ith column of S2. We let k' := k/ Vd for the scaling in attention. After projection, we average the projected
features as the segment embedding. The embedding for segment ranging from cis
(a(kitt)) == Σ da (ks-.)).
(5)
1=0
The segment embeddings can be pre-computed and stored. This construction process illustrated in Figure Ta
To search for the most important segments, we can search for
arg topk (auite ==
(6)
for I E c...,, [[4/c] - l)c]. By using this acceleration, the time for calculating the importance of single segment (i.e., r(c)) becomes constant, and consequently ((T(c) (()). Therefore, the total time is O(t/c) given there are [t/c] segments. Based on our theoretical
guarantees in Section 2.3] the obtained segments will likely contain the most important tokens that summed to the highest attention scores. This process is demonstrated in Figure Tb
Dynamic restructuring. With the accelerated searching, we have O(t/c+/ c) time for each query. The optimal asymptotic time complexity O(vi) obtained when O(vt), indicating that the segment range should change with the length of the context. However, changing the segment range requires a reconstruction of the segment embeddings that takes Ott) time. To address this, we propose a dynamic restructuring schedule, which only performs reconstruction when vi E N. This schedule indicates that there will be maximum vt times of restructuring happening for tokens, amortized an ((v)) time for each query step.
For all other steps that vt & we store the token buffer W, which serves as a sliding window with maximum size of 2/t- The sliding window is always used in querying steps. Although this adds more tokens in the attention calculation, the asymptotic complexity remains O(vi) for each step.
The overall algorithm. Putting all together, see that Radar demonstrates an overall time com- plexity of Ott to generate t tokens. We provide the procedure of Radar with detailed time complexity analysis in Appendix
2.3 THEORETICAL JUSTIFICATIONS
In this section, rigorously show that our algorithm described in Section 2.2 is guaranteed to solve the problem in Equation 3) with high probability.
We first show that the projection 4 sound with the following lemma.
Lemma 1. Let Φn follow the definition where Ω = (wi...., w,) is sampled No. Given any Rd, we have (u)
exp ( T./oo/V)..
Proof. This is first shown in (Choromanski et al. 2021 We include as a part of our Lemma 6 in Appendix B for completeness.
Based this, build the following theorem to show the correctness of our algorithm.
4

---

Published as a conference paper at ICLR 2025
Theorem 2. Let Radar be at a state of e segments where each segment contains tokens. Without loss of generality, assume the first segment k1.1+e has the highest attention score 01:1+e W.T.t the current query q. With confidence at least 1 6. we have
(5 max Φ (g)(g) (12)))))(kkkt))
the minimum gap 01:1+c max, aliic 2 c (xp(<2/va) V
Blog(2(e-1//0) Here, Ç is the maxi-
a
2c, ..... ...., (c 1)c] is the starting index of norm among k; and q. whereas E [1,1+ each segment.
Proof. We first build a series of essential lemmas in Appendix B The proof of this theorem is then shown in Appendix C
Our theorem asserts that as long as the projection dimension large enough, we can correctly retrieve the segment with the highest attention up to any precision. In fact, with the growth of sequence length, the difficulty of meeting this condition not growing linearly because the attention gap needed is Ollog(c)/c) for an average segment attention score of O(1/c), suggesting our approach is particularly favorable for long-context decoding.
3 EXPERIMENTS
In this section, we conduct extensive experiments to verify the effectiveness of Radar in comparison with other methods on diverse tasks and models. We additionally carry out in-depth analyses and ablation studies to demonstrate the effects of the length of prompts, the projection dimension, and the number of selected segments.
3.1 EVALUATING LONG-CONTREN PERPLEXITY
Datasets. Following previous work (iiao et al. 2024 Zhang al. 2023).
the perplexity
on the first sample in the PG-19 dataset as the main test bed. Specifically, we evaluate the over- all perplexity by feeding the ground-truth tokens one by one. Since PG-19 only contains natural language, we additionally use a code sample from The Stack (Lozhkov et al. 2024) for a broader comparison. The selected sample an implementation NASA's CDF CDF Project in single Python file. To simulate the real-world use cases, we prefill the first 16,384 tokens into the model as prompt. The experiments without prompts are conducted in Section 3.3
Competing methods. We consider the vanilla dot-product attention (Vaswani et al. 2017) and StreamingLLM (Xiao et al. 2024) as the baselines in this experiment. Following the default setting in previous work (Xiao et al. 2024 Zhang et al. 2023) the sliding window length is set to 1024 for all runs. For Radar, dimension set to 2048. The effect of these two parameters is studied in Section 3.3 conducted on single A000 GPU with 40GB of memory.
choose the top 64 segments for each query with the random projection
Each experiment
Models. Following previous work (iiao this experiment: Llama (Dubey et al. 2024) and Mistral (Jiang et al. 2023). Specifically, we use Llama-Meta- 1- and Mistral- 1-11--7--0 for each architecture, respectively.
2024). we choose two popular architectures in
Results. We show the results in Figure 2 The naive attention method achieves the best perplexity in all runs. However, its elapsed time grows quadratically regardless of the architecture. In prac- tice, the generation throughput drops to 10 tokens/s or even lower at the end. On the other hand, StreamingL_LM achieves constantly high throughput cost of poor generation quality (measured in perplexity), , as it evicts most of the context during generation. Our method Radar, in contrast, is able to effectively control the elapsed time while maintaining similar perplexity by maximum
https://cdf. gafc. nasa.gov/
5

---

Published as a conference paper at ICLR 2025
Vanilla
StreamingLLM
Radar
PG19
Code
6.1
3.0
2,55
6.8
2.5
2.8
Perplexity
5.9
5.8
2.6
2.4
230
6.4
6.40
2.4
2.0
5.6
7.07
Elppadd time (5)
3000
10:14:5
2000
12.15
20:02
1000
4295
22.00
16 021
33.00
2
x10
Steps
Steps x10*
Steps
x10
The performance comparison in perplexity (first row) and elapsed time (second row). The lower the better for both metrics. For the Llama model, we annotate the perplexity value at the last token; for the Mistral model, we annotate the perplexity at the maximum pre-training context length (shown by the vertical dashed lines) because the full context exceeds its modeling ability. We additionally show the generation throughput for all runs.
Figure 2:
difference of around 0.2 compared with the vanilla attention. Notably, the performance degener- ation of Radar at most 10% while the speed up is more than 2 times. The results confirm the effectiveness of method in effectively utilizing the context while accelerating inference.
We present additional results with H2O (Zhang et al. 2023) and SnapKV (Li et al. 2024), two state- of-the-art methods that employ different heuristics to reduce context length during inference, in separate figure in Appendix D as both methods produce out-of-scale perplexities in this setting,
3.2 LONG-CONTEXT BENCHMARKS
In Section above, we only evaluated the perplexity without inspecting the down-stream perfor- mance. For a more comprehensive comparison, we additionally conduct the end-to-end evaluation on numerous long-context tasks.
Datasets. Following previous work (Li et al. 2024). we use the LongBench dataset (Bai et al. 2024) as the main benchmark. Specifically, we use all 16 subtasks in English and code languages. These tasks belong to 6 categories in total: single-doc QA, multi-doc QA, summarization, few-shot learning, synthetic, and code. Following the standard LongBench pipeline (Bai et al.) (024), we truncate the context from the middle of the prompt length exceeds the pre-training length. Each subtask is evaluated with a specific metric (e.g., ROUGE scores (Lin (004) for summarization tasks and accuracies for synthetic tasks). After evaluating all subtasks, we report the average scores as a summary on LongBench. It is worth noting that the metrics used by different subtasks can have very different scales, indicating the arithmetic average over all subtasks may not reflect the overall performance (e.g., the final average may be inaccurately dominated by the accuracy of the synthetic tasks as pointed by the original paper (Bai et al., (024)). To this end, we additionally include the average percentile over all 16 tasks ranked within the same base model. For instance, percentile of 80% means that the method is expected be strictly better than 80% of other methods.
Competing methods. We use all methods mentioned in Section 3.1 including H₂O (Zhang al. 2023) and SnapKV (Li et al. 2024). Following the previous work (Li et al. 2024). all competing baselines
maximum of 32 ne tokens, where 32 is the length of the sliding window and n, is the number middle tokens varied from 1024 to 4096. For StreamingLLMM, we simply extend the sliding window by ne- In addition baselines used in previous work, we also evaluate

---

Published as a conference paper at ICLR 2025
Table 1: Performance comparisons of different methods on LongBench. On each model, the best- performing method is highlighted in bold and the second-best method is underlined (excluding the vanilla method). Each table contains the results for one particular model.
(a) The LongBench benchmark results of different methods applied Llama- 7b. Each prompt contains
maximum 1.5K tokens as the model can handle maximum 2K tokens.
Single QA
Muli QA
Summarization
Few-show
Synthtiic
Code
Context
Mothod
NrvQA
Qusper
MRQA
HtPQQA
2W1QA
Musique
GovRep
QA35um
MulNows
TREC
TriQAA
SumSum
PygCmt
PsgRet
Avg. Seore
Avg. Pere.
LCC
RB-P
Full
Vanilla
3.12
8.01
17.52
8.16
10.02
4.75
26.28
14.33
27.18
52.50
80.88 35.16
2,00
6.17
61.88
54,81
25.80 56,25
Landmark
8.53 10.51
16.05
10.97
12.61
4.54
11.93
11.88 7.16 34.00
58.83
28.93
2.50
5.83 45.24
39.39
19.31 30.21
LtreamingI.LM
2.76
7,86
16.37
8.57
11.14
4.54 15.86
14.17
19.96
53,00
80.79
35.44
1.83 6.50
61.81 53,97
24.66 37.50
H₂O
2.87
8.11
16.59
8.05
9.85
26.25
14.85
25.92
51.50
80.67
34.41
5:75
52.96
25.22 25.00
1024
SnapKV
2,97
7,88
17.38
8.39
10.07
4.65
25.74
14.51
26.55
52.50 80.88
35.24
2.00
6.17 62.71 54,47 25,76 52,08
Radar
2.94
8.01
17.61
8.49
10.51
4.15 26.11 14.61 27.52 52.00 80.92 35.48
1.75 6.50 62.36 54.41 25.84 54.17
(b) The LongBench benchmark results of different methods applied on Liama 2- aaa--cat--ee -hf. Each
prompt contains maximum 3.5K tokens as the model can handle maximum 4K tokens.
Single QA
Multi QA
Summarization
Few-shor
Synthetic
Code
Context
Method
Nrn-A
Qusper
MPQA
HipQA
2WKQA
Musique
GovRep
QMSum
NeWssss
TRBC
TAQQA
SamSum
PsgCnt
Pagite
LeC
RB-P
Ang. Score
Avg. Perc.
Full
Vanilla
16.87
17.78
36.13
34.06
27.53
9.10
26.09
21.01
25.99
64.00
83.84
41.24
4,50
12.00
58.36
52.31
33.18
74.38
SubGien
26.27
21.49
7.38
22
20.68
23.90
39.00
65.31
25.95
4.92
24.98
13.75
Streamingl.IAM
15.38
15.13 21.95
28.67
24.56
5.66
21.15
19.70
24.57
61.00
80.69
40.62
4.58
4.50
56.59
49.28
29.63
14.37
1024
H₂O
16.54
16.04
35.1
32.53
26.60
8.1
27.91
20:42
26.84
63.00
15
38.38
4.00
10.50
52
44.53
31.61
36,25
SnapKV
15.69
18.30
35.59
33.23
26.27
8.62
21
20.47
25
64.50
82.57
40.43
4.50
11.00
58.27
52.06
32.41 45.00
Radar
16.95
19.32 37.20
33.70
27.60
8.83
25
30
21.21
25.66
63.50
83.44
40.78
4.50
10.00
57.70
51.17
32,93
64.38
StrcamingLLM
16,77
16.03
25.45
30.14
25
36
7:42
23.
39.59
19.71
25 58
64.00
52.57
41.65
4.50
6.50
56.94
51.15
31.08 35.00
H₂O
16.39
17.93 36.09
32
26
7.61
27
73
20.58
26
45
63.50
39.
26
10.00
57.32
51.63
32.63
2048
SnapKV
17.05
18.43
36.03
33 78
27.06
7,90
24.56
21.01
25
76
64.00
82.88
40.60
4.50
11.50
58.51
51.74
32,83 64.38
Radar
16.90 17.76 36.02 33.90 26.81 8.79
26.32 21.11
26.15
64.00
83.92 41.01
4.50
11.50
58.37 52.06
33.07 71.25
(c) The LongBench benchmark results of different methods applied on Mistral- 7B- -aatrral-----ttttee custrruct-to .2..
Each prompt contains maximum 31.5K tokens as the model can handle maximum 32K tokens.
Single QA
Mulii QA
Summarizatiio
Few-shot
Synthetic
Code
Context
Method
Nrn-Q
Qusper
MRQA
HiPIQA
2WXQA
Musique
GovRep
QMSam
MulNews
TRRC
TriQAA
SumSum
PsgCnt
PsoRet
1.C
RB-P
Avg. Score
Avg. Perc.
Full
Vanilla
27.06 32.22 49.61 43.49 27.96
18.85 33.35 24.30 27.13 71.00
86.07
43.50 2.80
86.98
56.17
53.63
42.76
75.63
Streamingg
32.03
21.69
23.55
20.28
25.41
64.00
13
22.33
54.79
94
33.09
8.75
1024
SnipKV
24.97
30.03
49.51
41.35
25.82
18.92
25.85
24.09
26.24
70.00
86.53
42.04
2,83
89.06
54.33
50.96
41.41
43.75
Radar
23.81
28.26
47.91
38.96
27
16.08
27.99
22.52
26.95
70.50
41.70
3.13
53.33
54.17
50.03
38.59
28.75
Streamingt J.M 22.54
22.46 35.35
33.36
21
13.30
26.60
20.67
26.47
66.00
85, 92
42.
02.00/1
2.81
26.58
55.92
51 58
34.67
18.75
2048
SnapKy
26.10 32.14 49.31
41.71
27.60
28.90
24.53
26.65
70.50
86.28
42.97
86.27
54,50
50.87
41.87
51.87
Radar
26.31 31,89
49.55
43.18
26.83
17.47
30.38
23.30
27.18
71.50
86.15
42.49
3.39
72.25
55.76
51.87
41.22
60.00
StreamingL.LM
24.48 29 86 41 41.04
37.19
24.47
14.94
30.38
21, 62 26.96
69, 50
86
15
42.70
2,58
39.53
56,49
52.64
37.53 34.38
4096
SnapKV
26.31 33.61
50.35
42.67
27.89
18.74
30.73
24.24
27.00
71.00
86
43.14
2.60
86.10
54.19
51.22
42.25
61.25
Radar
26.31 33.77
49.17
42.85
28.68
17.91
32.15
24.17
27.11
71.00
86.23
43,41
2.87
81.75
56.42
52.92
42.30
69.38
the Landmark attention (Mohtashami & Jaggi 2023) and SubGen (Zandich et al. 2024). Each experiment is conducted on one A100 GPU.
Models. We test wide range of models in this experiment. We first choose the Llama-77 7b model (Touvron et al. 2023a) because Landmark attention is fine-tuned based on it. We also have .lama-2-7b-aa -ff, which is included in the original LongBench paper (Bai et al.) 2024 Finally, we also test with Mistral- - 7B- Instrrct---uut v0. 2 following the previous work (Li et al. 2024].
7

---

Published as a conference paper at ICLR 2025
Results. The results shown in Table 11 In all three subtables, see that the vanilla attention mechanism generally achieves the highest scores on all tasks, given that it has all the information presented in the context. StreamingLLM is oftentimes the worst method because it only uses the recent 32+n, tokens.
For the Llama-7b model (in Table la we that the Landmark attention method performs better than the vanilla method on QA tasks. This is likely due to the additional data in fine-tuning. However, the performance on other tasks is significantly deteriorated. For H2O and SnapKV, observe similar results as in Li et al. 2024), where SnapK is better than H2O in both average score and percentile. Among all the baselines, Radar achieves the highest average score and percentile ranking.
The results on Llama 2-7b-chat- are shown in Table Tb Aligned with the observation in previous work (Li et al. 2024), SnapKV generally outperforms HzO in this setting. SubGen, albeit additionally saving memory, underperforms other methods on nearly all tasks. This indicates that its emphasis memory saving and acceleration might be at the expense of generation quality. Our Radar achieves the highest average scores and average percentiles across all n,, settings. Notably, Radar with 1024 middle tokens outperforms SnapKV with 2048 middle tokens in terms of average score. The results strongly suggest the effectiveness our method in utilizing the context.
Table 1c shows the results for Mistral- - Ies-Instuuct--. v0. Our method is consistently better than SnapKV when the ground-truth answers require long generation (e.g., the government report task). This not only suggests the effectiveness of Radar but also shows that Radar is utilizing different tokens at different steps of token generation. Remarkably, Radar achieves an average score close to the vanilla method with only 13% of the tokens used (n. 4096).
3.3 IN-DEPTH ANALYSES
Generating without prompts. In Section 3.1 we prefill 16,384 tokens for all runs to simulate the usage of prompts in real-world applications. However, some previous work are focused on non- conditional generation, where no prompt is provided. To compare the performance in this setting, we conduct experiments similar to Section 3.1 without the prompts. The results are shown Figure Note that we cannot compare with SnapKV V because it is only applied to prompts.
StreamingLLM
H2O
(PPL)
(PPL)
PG19 (Time)
6.50
7.00
6.66
6.25
4000
66000
6.00
3000
0:01
4000
50
6.50
5.75
3000
2000
5.50
3.59
2000
6.00
5.25
1000
1000
3534
5.75
5.00
2
2
6
Steps
x10
Skeos
Steps
Steps
x10
Figure 3: Generation without prompts.
As observed, H2O demonstrates a promising result on the Llama model the overall perplexity is only worse than Radar by 0.05. However, the perplexity of the Mistral model starts to drastically deteriorate after hundreds of tokens. On the contrary, Radar continues to perform steadily. This experiment suggests the versatility of Radar, offering acceleration with without prompts wide range of model architectures.
The effect of and k. Our method introduces hyper-paramenn (the projection dimension for the random matrix) and & (the number of top segments selected). We show the effect of these two hyper-parameters with the Figure 4a and Figure 4b respectively.
Aligned with our theoretical prediction with Theorem 2 increasing n improves the performance by providing better attention approximation. Similarly, increasing k also improves the generation
We skip the H2O method in this setting because runs of 40GB memory with prompts of 31.5 tokens.
8

---

Published as a conference paper at ICLR 2025
Venilla
Redar n|128]
Vanilla
Reder k(4)
StreamingLLM Radar n(2048)
n(8)
StreamingLLM Radar k(64)
8(256)
Liama PG19 (PPL)
Liama PG19 (Time)
Liama PG19 (PPL) 4M4
Liama PG19 (Time)
6.8
3000
3000
651
:3.44.5
6.6
2000
22.5
6.6
2000
20
75:1
6.4
64
1000
6.4
1000
25.3
4..2
Steps
x10
x10
Steps
x10
Steps
x10*
(a) The effect of the hyper-parameten rt.
(b) The effect of the ayper-parameterr l.
Figure 4: The effect of the hyper-parameters n (the projection dimension for the random matrix) and & (the number of top segments selected) introduced by Radar.
quality by using more tokens. However, high n or k imposes the need for more memory and increases the computational overhead. Given these considerations, we use n 2048 and & 64 by default to balance the generation quality and hardware efficiency.
Ablation study. Our algorithm involves an approximated top-k selection. To verify that such an approximation is functioning as intended, we conduct three ablation studies in Figure S by replacing with three other strategies. The experiments are conduced with the Llama model on the PG-19 sample.
Vanilla
StreamingLLM
Radar
Radar(Ablation)
Bottom
Random
Exact
605
1.5
535
6.8
6.8
6.8
Perpleaby
6.6
6.6
6.6
6-0
4
6
6.4
6.4
Steps
x10
Steps
x10*
Steps
x10*
Figure 5: Ablation studies. Here, we compare with three different segment selection strategies.
As shown, when we select segments with the lowest approximated segment attention scores (left), the performance becomes similar to StreamingLLMM, suggesting that the selected tokens with low segment attention scores are indeed not informative. addition, our approximation better than the random selection strategy (middle), showing that such an approximation is choosing more infor- mative tokens than the "uneducated guess". Lastly, we see that our approximation has the closest performance compared with the exact segment search (right), indicating our method, albeit poten- tially missing some tokens, is a reasonable approximation given its low time complexity.
RELATED WORK
Context reduction. Previous literature shows that Transformers with sparse attention patterns can generate with fewer context tokens while not sacrificing the generation quality (Child et al., 2019 Beltagy et al., 2020 Zaheer et al., 2020 Roy et al. 2020 Chen et al. 2021). In addition to the success of sparse attention architectures, researchers also empirically demonstrate that the vanilla Transformers do not need all tokens in the context to correctly generate the current token (O'Connor
& Andreas 2021 Sun et al.] 2021 Liu al. 2024 Our work entails this discovery.
Based on the discovery, there are some closely related methods proposed Han et al. 2023). For instance, StreamingL.LM (Xiao al. 2024) uses only the local sliding window along with few

---

Published as a conference paper at ICLR 2025
beginning tokens to generate the current token. H₂O Zhang al. 2023) proposes to additionally retain middle tokens based on a scoring function to maximize hit rate. SnapKV (Li et al.) 2024) proposes to retain middle tokens based on the attention pooling in parallel manner. All these meth- ods, albeit reducing the context length, cannot recover the lost information once the context token is evicted. Moreover, they still suffer from the quadratic time complexity. By contrast, is able to dynamically retrieve any tokens in the context with low time complexity. Recently, Zandich et al. (2024) propose compress the KV cache for memory and time efficiency, posing an opportunity for better algorithm designs.
method
Efficient attention. The quadratic computing time of the dot-product attention becomes bottle- neck in long-context generation. Searching for an efficient design of the attention mechanisms is a long-standing topic for Transformers (Wang et al., 2020 Kitaev al. (020)). Recently, Landmark Attention (Mohtashami & Jaggi 2023) proposes to use grouped softmax with a special token to reduce computation. Another line of work reduces the time complexity is through attention ker- nelization, which reformulates the dot-product attention mechanism as kernel (Tsai et al.) 2019) Katharopoulos al. 20200) Peng al. ear complexity in both training and inference by recurrence. However, the parameters are required fit the new architectures. On the contrary, our method is training- and can be applied to any pre- pre-trained Transformers.
202T Zandieh et al., 2023). These methods can achieve lin-
be trained/fine-tune
Instead of modifying the vanilla attention, recent literature also focuses on improving the efficiency
in implementation. For example, Flash Attention series (Dao et al. 2022 Dao 2023) leverage the tiling technique to avoid memory-bound attention operations.
semory-efficiiee attention (Rabe & Staats, (021)) reorders the attention calculation to allocate only the constant space for any context length. Our work orthogonal these methods and can be combined together.
Long-context ability via retrieval. In certain cases, Transformers can gain the long-context abil- ity by retrieving related documents like retrieval-augmented generation (Lewis al.) (2200) based on ANN search. For instance, Memorizing Transformer (Wu et al.) 2022) recurrently caches previ- ous tokens in kNN index. Unlimiformer (Bertsch al. [0223 uses a ANN index retrieve the encoded chunks in the encoder attention. However, these methods can only be used with the specialized architectures after training. They may also suffer from the exponential search quality degradation when the dimension increases (Beyer et al., 1999). Unlike these methods, Radar is training-foe free method with a rigorous performance guarantee independent of the dimension.
5 CONCLUSION
In this work, we present Radar, a general and effective approach to accelerate inference for Trans- formers. Unlike previous methods that train other variants of the attention mechanism for replace- ment, Radar can accelerate any pre-trained Transformers without the need for training. In addition, we provide theoretical justifications that show Radar can reliably identify the most important tokens with high probability. More importantly, models confirm the effectiveness of our method. Compared with prior training- free methods that evict tokens based on heuristics, Radar utilizes context tokens dynamically in principled manner, resulting in significantly higher generation quality while achieving a lower time complexity.
empirical results across wide range of tasks and
We hope that Radar opens up opportunities for pre-trained Transformers to be applied out-of-the- box, without requiring expensive re- re-training, to long context settings (c.g. legal documents or finan- cial transactions). We also hope method further inspires advancements in high-quality generation with low time complexities for LLMs.
ETHICS STATEMENT
Our research focuses on accelerating pre-trained Transformers to reduce power and time consump- tion in inference. As far as we are aware, does not pose any new ethical or societal risks that require specific attention.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
In our paper, all of our models and datasets are publicly accessible. For the models, we download them from HuggingFace's hub using the following identifiers:
meta mata==lDammm/etete-111mo-------1
huggy/llama/bllmm->bb
m
mbstralli/Misttral---Tnttttttt
For the datasets, we follow the previous work and similarly obtain them from HuggingFace:
THUDx/LongBench
emczilla/pgi19-test
bigcodee/th--stack
We run all of our experiments on A100 GPUs.
The procedure of Radar is explained in Algorithm with the theoretical justification in Theorem
REFERENCES
Joshua Ainslie, James Lee-Thorp Michiel de Jong, Yury Zemlyanskiy, Federico Lebron, and Sumit Sanghai. GQA: Training generalized multi-query transformer models from multi- head check- points. In EMNLP, 2023. URL BtKLhtttss///ppereeeee wwwp://wwwwwwww.eeeeeeeereom
net/forum? d=hmOw0ZWZYF
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang. Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. LongBench: A bilin- gual, multitask benchmark for long context understanding. ACL, pp. 3119-3137, 2024. URL ht http:///.....aaoooo.ooo//////aaa
org
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long- transformer. 055000 2020. / wtw..//.///./.oooo.///// 05150
Amanda Bertsch, Uri Alon, Graham Neubig, and Matthew R. Gormley. Unlimiformer: Long-range transformers with unlimited length input. In Thirty-seventh Conference Neural Information Processing Systems, 2023. URL https: htttpp::///peereveeww net
Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. When Is "Nearest Neighbor" Meaningful?? pp. 217-235. Springer Berlin Heidelberg, 1999. doi: 10.1007/
3-540-49257-7.15. URL /htt::///iiii www.....i.................... com/ http://ccc/cccoet///t/////////// 3-540-49257-7_15
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In ECCV, pp. 213-229, 2020.
URL https:://ttxi...ttts//
Barrgg/bb////0 babs/2005. 12872
Huiwen Chang, Han Zhang, Jarred Barber, Aaron Maschinot, Jose Lezama, Lu Jiang, Mlngg-Hsua Yang, Kevin Patrick Murphy, William T. Freeman, Michael Rubinstein, Yuanzhen Li, and Dilip Krishnan. Muse: Text-to-image generation via masked generative transformers. ICML, 2023.
URL htt.tttss///iiii / abt.lss......a..ope.p 00704
Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, A. Rudra, and C. Ré. Scatterbrain: Unifying sparse and low-rank attention approximation. 2021. URL http:://axxiv..rg//a/////2
15343
Rewon Child, Scott Gray, Alee Radford, and llya Sutskever. Generating long sequences with sparse transformers arXiv preprint 1rX1:1994410009 2019. URL https: / //taxxa..oorro//e....o. abs/
1904. 10509

---

Published as a conference paper at ICLR 2025
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger. Lucy J Colwell, and Adrian Weller. Rethinking attention with per- formers. In ICLR, 2021. URL BtRLbttss:///peneeee
ntt/forumm 6zuk
Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.0866 2023, URL httttttss////xxiii http://awwii..oooaa///////3// 08691
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. FlashAttention: Fast and memory- efficient exact attention with IO-awareness. NeurIPS, 35:1 35:16344-16359, 2022. URL https:
7/ //axiv.crg/abs//222..... 2211b.
Jacob Devlin, Ming-Way Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In NAACI, 2019. URL https:
//
Ming Ding, Wendi Zheng, Wenyi Hong, and Jie Tang. Cogview2: Faster and better text-to-image
generation via hierarchical transformers. In NeurlPS, 2022. URL httpps://ppenrevieew
net/forummi (it.oorommmiid-GG000ggbouuu.__
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenbor,, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x 16 words: Transformers for image recognition at scale. In ICLR, 2021. URL
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, and et al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024. URL httph:t////// http///axvvv/.e////a//////aaae org/ abs/2477. 21783
Xiequan Fan, Ion Grama, and Quansheng Liu. Exponential inequalities for martingales with appli- cations. Electronic Journal of Probability, 20:1 - 22, 2015. httpt://doooo org/
1214/EJP. v220-3496
Qingkai Fang, Yan Zhou, and Yang Feng. DASpeech: Directed acyclic transformer for fast and high-quality speech-to-speech translation. In NeurlPS, 2023. URL httppp:p:///oerreiiien.
Insu Han, Rajesh Jayaram, Amin Karbasi, V. Mirrokni, David P. Woodruff, and A. Zandich. Hy- perattention: Long-context attention in near-linear time. ICML, 2023, URL https://arxxi
2ttpo//2311.om 05869
Ali Hassani, Steven Walton, Jiachen Li, Abulikemu Abuduweili, Humphrey Shi, and Dacheng Tao. Regionvit: Regional-to-local attention for vision transformers. In ICLR, 2022. URL https:
02689
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chap- lot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint 1rXiv:2310.06825, 2023. URL https:://axxv..rrg//
2310.06823
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers mns: Fast autoregressive transformers with linear attention. In ICML, pp. 5156-5165, 2020.
URL https:
16236
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In ICLR,
2020. URL URL http://ppa..ppppeeeeee.eeeeeeees
Denis Kocetkov, Raymond Li, Loubna Ben Allal, Jia Li, Chenghao Mou, Carlos Muñoz Ferrandis, Yacine Jemnite, Margaret Mitchell, Sean Hughes, Thomas Wolf, Dzmitry Bahdanau. Leandro von Werra, and Harm de Vries. The stack: of permissively licensed source code. Preprint, 2022. URL httth:/ts::/eet wrgg/ooaoo abs/ /211 15533
12

---

Published as a conference paper at ICLR 2025
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. Retrieval- -augeeted gen- eration for inowledge-imtensive ulp tasks. NeurIPS, 33:9459-9474 9474, 2020. URL https:
11401
Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Lim knows what you are looking for before generation. Neru/PS, 2024. URL
14469
Chin-Yew Lin, ROUGE: A package for automatic evaluation of summaries. In Texr Summarization Branches Out, pp. 74-81. Association for Computational Linguistics, July 2004, URL https
//aclanthologg oog org/w04 1013
Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. TACL, 12:157-173, 2024. //ttttsss/aaattt http://aaaxx....aabb..ass wwwp:/orggaaaaaaaeeeee /2007 03172
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. ICCV, pp. 10012- 10022, 2021. https: //arx/aaavvvv//aa//aa/ org/ abs/2103. 14030
Anton Lozhkov, Raymond Li. Loubna Ben Allal, Federico Cassano, Joel Lamy-Poirier, Noua- mane Tazi, Ao Tang, Dmytro Pykhtar, Jiawei Liu, Yuxiang Wei, Tianyang Liu, Max Tian, De- nis Kocetkov, Arthur Zucker, Younes Belkada, Zijian Wang, Qian Liu, Dmitry Abulkhanov, Indraneil Paul, Zhuang Li, Wen-Ding Li, Megan Risdal, Jia Li, Jian Zhu, Terry Yue Zhuo, Evgenïi Zheltonozhski,, Nii Osae Osac Dade, Wenhao Yu, Lucas Krauß, Naman Jain, Yix- uan Su, Xuanli He, Manan Dey, Edoardo Abati, Yekun Chai, Niklas Muennighoff, Xian- gru Tang, Muhtasham Oblokulov, Christopher Akiki, Mare Marone, Chenghao Mou, Mayank Mishra, Alex Gu, Binyuan Hui, Tri Dao, Armel Zebaze, Olivier Dehaene, Nicolas Patry, Can- wen Xu, Julian McAuley, Han Hu, Torsten Scholak, Sebastien Paquet, Jennifer Robinson, Car- olyn Jane Anderson, Nicolas Chapados, Mostofa Patwary, Nima Tajbakhsh, Yacine Jernite, Car- los Muñoz Ferrandis, Lingming Zhang, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. Starcoder 2 and the stack v2: The next generation, 2024. URL attts::/aaxxe org/ abs
Amirkeivan Mohtashami and Martin Jaggi. Random-acces: infinite context length for transformers. In NeurlPS, 2023. URL https::: htt.://eww........e.....ouuooooa
Joe O'Connor and Jacob Andreas. What context features can transformer language models use? In ACL, pp. 851-864, August 2021. URL
acl oog.nnn... 70
Bo Peng, Eric Alcaide, Quentin Gregory Anthony, Alon Albalak, Samuel Arcadinho, Stella Bider- man, Huanqi Cao, Xin Cheng, Michael Nguyen Chung, Leon Derezynski, Xingjian Du, Matteo Grella, Kranthi Kiran GV, Xuzheng He, Haowen Hou, Przemyslaw Kazienko, Jan Kocon, Jiaming Kong, Bartlomiej Koptyra, Hayden Lau, Jiaju Lin, Krishna Sri Ipsit Mantri, Ferdinand Mom, At- sushi Saito, Guangyu Song, Xiangru Tang, Johan S. Wind, Stanislaw Wożniak, Zhenyuan Zhang, Qinghua Zhou, Jian Zhu, and Rui-Jie Zhu. RWKV: Reinventing RNNs for the transformer era. In EMNLP, 2023. B https: httppp:://peeeeee http///pppeeeiiieeeeee//eeeeeeet hwt.:/iwww....ee.e...ee nwt/
www.:/ernttttteee. Forum 2 d SaxczzappG
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. International Conference on Learning Representations, 2021. URL
/
net htte:/oorommmm-tttttataa--a
Markus N. Rabe and Charles Staats. Self-attention does not need onn²) memory. arXiv preprint 2112. 05682
arXiv: /2 2021. URL
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. JMLR, 21 21(14)): 2020.
wwwpr///abb///gga 10683
Aurko Roy, M. Saffar, Ashish Vaswani, and David Grangier. Efficient content- based sparse attention with routing transformers. TACL, 2020. doi: 10.1 1662tacl 00353.
13

---

Published as a conference paper at ICLR 2025
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. Thirty-sevents Conference on Neural Information Processing Systems, 2023.
Simeng Sun, Kalpesh Krishna, Andrew Mattarella-Micke and Mohit Iyyer. Do long-range language languaae models actually use long-range context? In EMNLP, pp. 807-822, 2021. URL https://
acl aclanthology.oo org/ 2021. emn wwwll-manalneeeeeee
Yuqing Tang, Chau Tran, Xian Li, Peng-Jen Chen, Naman Goyal, Vishrav Chaudhary, Jiatao Gu, and Angela Fan. Multilingual translation with extensible multilingual pretraining and finetuning. arXiv preprint arXiv:2008.0044000 2020.
ptq/abs///eeeoo........ee/... org abs / 2008 00401
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang. Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient trans- formers. In ICLR, 2021. URL httpt: http::://ppnneevieeeeee////////e
net iie..eeeeee...iiiiiiiieeeeeleee
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971 2023a.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et Llama 2: Open foun- dation and fine-tuned chat models. arXiv preprini arXiv:2307.09220 092888 2023b. URL https:
//aaxii..rrgab////3333 09288
Yao-Hung Hubert Tsai, Shaojic Bai, Makoto Yamada. Louis-Philippe Morency, and Ruslan Salakhutdinov. Transformer dissection: An unified understanding for transformer's attention via the lens of kernel. EMNIP-IJCCIPP pp. 4344 4353. Association for Computational Linguis- org.p19 1444333391443
tics, 2019,
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention all you need. In NIPS, volume 30, 2017. URL htttps://proceediing www.eeiddi.nnnnnnen............e www.iee..rcoooo wwwppippppcppppppprpppppepppppee fi ftles/pappe/201177 file/ File:/5foee2333/feeee11111133113
Apoorv Vyas, Angelos Katharopoulos, and François Fleuret. Fast transformers with clustered atten- tion. NeurlSP. 33:21665- 2020. Utl.https.//axxivvorr////.. 00020000
Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.07668 2020. URL httttttss/////xit/
abs/2006 04768
Yuhuai Wu, Markus Norman Rabe, DeLesley Hutchins, and Christian Szegedy, Memorizing trans- formers. In ICLR, 2022.
jbx fbxzRenf-
Zijun Wu, Bingyuan Liu, Ran Yan, Lei Chen, and Thomas Delteil. Reducing distraction in long- context language models by focused learning. arXiv preprint arXiv: 2411.05928, 2024. URL
https:/ attp://////xxxooooaaaaaao. www.orgg..bb...oooooo.. 2411.05928
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming net.
language models with attention sinks. In ICLR, 2024. URL
FoorumiddNG775511i
Tongkun Xu, Weihua Chen, Pichao WANG, Fan Wang, Hao Li, and Rong Jin. CDTrans: Cross-
domain transformer for unsupervised domain adaptation. In ICLR, 2022. URL https:
Shaowei Yao and Xiaojun Wan. Multimodal transformer for multimodal machine translation. In ACL, pp. 1346-4350 2020. doi: 088653/v12222000 20l00aalllmmm40000 moin.400. acl antho / acl 1ell-mainn 4000
URL https:
14

---

Published as a conference paper at ICLR 2025
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. NeurlPS, 33:17283-17297, 2020. URL https::/taaat http//axxvvv./////e www.vorggaaa abs/
2007 14062
Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi. KDEformer: Accelerating Trans- formers via kemel density estimation. In ICML, pp. 40605-40622 2023,
URL https:
//proceedings press httpe/////v2//aannee2....aa... htmml
Amir Zandieh, Insu Han, Vahab Mirrokni, and Amin Karbasi. Subgen: Token generation in sublin- ear time and memory. arXiv preprint arXiv: 2402.06082, 2024. URL htlpttss///xxi..rrgg
abs/2402. 06082
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H20: Heavy-hitter oracle for efficient gen- erative inference of large language models. Neru/PS, 36, 2023. URL httpss:s//axiii.rr.t
Lei Zhu, Xinjiang Wang, Zhanghan Ke, Wayne Zhang, and Rynson WH Lau. Biformer: Vision transformer with bi-level routing attention. In CVPR, pp. 10323-10333, 2023, URL https:
//arxiv.om www.vv..rrrroooo abs/ / 220///233.000 08810
15

---

Published as a conference paper at ICLR 2025
A COMPLETE ALGORITHM
We provide the complete algorithm as follows.
Algorithm The overall algorithm of Radar
Require:
head dimension d E N, projection dimension N, number of segment selection lt E N
> Initialize the Radar state
1: Current context length
2: Current segment range +-40 0 Unregistered buffer V 4
4: Sample 5 = (Wi,... w.) from No.1
5: Obtain the projection function Φn according to Equation
>> Decoding procedure
6: while taking a new token with q, k and v do
7:
< [++
8:
V E N then
9:
Restructuring process descried in Section 2.2
10:
- vt
11:
Pre-calculate ((kus4o) for E [1, 1 + 2c, ......, (c 1)c]
D O(t)
12:
W- +
13:
else
14:
W WUL
Append the buffer otherwise
15:
end if
Querying procedure in O(Vl) for E [1, c. 1 .c.... 1 + (c 1)c] do
16:
ati+e (9) (kute))
Calculate segment attentions according to Equation O
18:
end for
Pick indices in the k segments with the highest au++
O(vi)
20:
S + S+SUW SUW
D Use the buffer as the sliding window
21:
yield softmax(q
Tke/ ks/ se/vd)os
O(k(t)
22:
end while
In the reconstruction step (lines 9-12), the time complexity is Ott) because we have segments with each containing e tokens. Since each segment representation & takes O(c) to construct, line 11 takes at most Σi= Occ) O(c²) time. This is equivalent to Ott) because c = v in line 10. As we will restructure the hierarchical approximation by at most O(Vt) times (given by the condition in line 8), the overall time complexity of all restructuring steps (considering the outer loop containing lines 8-11) is 0(13/2). When amortized all steps, each step will take O(Vl) average.
For the query step (lines 16-18), it is straightforward to the per-step time complexity is O(vi) because each time step computes O(vi) segment attention scores.
The final attention step (line 21) takes O(kvt) time because there are k segments selected, each with ((vE) tokens.
Overall, see the per-step time complexity of Radar grows in O(vi).
B ESSENTIAL LEMMAS
Lemma 3 (adapted from Fan et al. 2015)). Let XI,..., X, be i.i.d. random variables such that
B[X]] X; b. For every 0. have
ns²
Pr
X; x,28 2
Seep
(8)
2c
1=1
nE²
and Pr
X; 26
cxp
(9)
2c
i=
16

---

Published as a conference paper at ICLR 2025
Here,
[[X?), b+
[E 2 bb,
c²
(10)
Bixf b
otherwise.
Proof.
Please refer to Corollary 2.7 in (Fan et al. 2015
Lemma 4. Let YI....,y, Y, be ii.d random variables such that Y, 2 0, Var[Y:] o². We have
E|Y,] = p > 0, and
n
Pr (1 11
26)
exp
(11)
max (p²,0²)
and Pr ( 2
( Y
n
exp
(12)
max (n², 02)
for every 2 O.
Proof. Let Xi = p Y, It is easy to verify that
1. [X = Elj - Yi = μ E = 0, and
2. X; = μ - Y; S and
3. [[X?] E[Y?] 11²² Var[Y:] = o².
We can then apply Lemma
3 on xI,...,X, Xn with b= 1t > O, which gives us
|B| [[?] 0²
if o 2 1 0 otherwise,
1 -++ =|x+1|
(13)
S u²:
summarized as 0 < e < max n²)) exp(-(ne2)/c3 is monotonically increasing with c² > O.
We can then obtain the proof by noticing that
Definition 5. For any u E Rdd we define a transformation function fu Rd + R as fu(w) == exp(w T aa-11u 1||
Lemma 6. Given any u, E Rd and w a random variable following No.1 E Rd, we have the following properties for f:
1. fu(w) 0, and
2. [[]] 1, and
3. (lfu(w)f. exp(u" ()), and
4. (arifu(W)f[ = expp2 v)
-
5. Cov
= (xp(")))))xxx(xxx()00 T)T=) (exp((u+2)) 2) (v+ + 2)) - 1).
Proof. We prove each property as follows:
1. It is obvious that exp(x) for all R.
2.
[B (w)) E [exp(wT ||22|1/22]]
(14)
/ Pr(w) exp(w> / /2)dw
(15)
17

---

Published as a conference paper at ICLR 2025
=(27)- d/2
exp(-1ww11/2) exp(w a -leell/// /2)
(16)
=(2m) d/2
cxp( w T - || /2 - ||0|1 12) dw
(17)
=(2T) -d/
exp(-Ilu 1|0 2 /2w
(18)
Pr(RR))
(19)
=1.
(20)
3. This is first shown in Choromanski et al. 2022 We present it here for completeness.
B[fu(w][((W]] E eexp(w" u |//l2/22 exp(w v ||0|| /2)
(21)
E [exp(w> T (u v) |/u + o012/22 exp(2i e J v)
(22)
= -E(futo(w) exp(x") Tv)
(23)
-xp(uu (T).
(24)
where the last line is from the second property. Notice that Φn in the main text scales both u and by 1/ vd before projection, resulting in En (()) [Ta(v)] = exp u T v vd
4. We first show that
[[(f(()ff(())
(25)
= eep (2 (u + v) - |uu + =113) exp e2p(2u w)]
(26)
=E (exp(22x) (2w (u + v) 12u + 20/1 /2) exp exp(2u' T + u + =]]3]]
(27)
= El [w)) exp (2u To + l/ + x1??
(28)
eep((2u T v + l| + 21)
(29)
where the last line is from the second property. It is then clear that
Varlfu(w)fo(w)) [[(fu(w)fe(
(Blfu(w)fo()))) = =exp 22 T v 1|u =1(²) - exp(2u' v)
(30)
(31)
= exxp(2uTu To) (exp(Ilu m11²) - 1).
(32)
5. More generally,
Cov (o)
(33)
(34)
The first term is
(35)
= E ( 1lu -0 =x12/2) exp(u" z)
(36)
exp(ww (w+)) 1 2 222 ex)(
(37)
= (ll t 2)
(38)
exp((u (v exp(u' x utv Tz)..
(39)
The second term is
([) =xpp=) =T zz).
(40)
Overall,
Cov (fu(w) (f)) = (u+ + x)) 1) exp((u + t) x).
(41)
18

---

Published as a conference paper at ICLR 2025
We can thus conclude proofs.
Definition 7 (Random feature approximation). Since Lemma shows that Ew~No. Lf (w) fw) [w(w]
=exp(u' v), can approximate exp(2 (u" v) by sampling random variable S defined as
S 1
fu(ws)fo(wo,)
(42)
for w, No.- This random variable corresponds the dot-product between two features using Equation
Lemma Given any un Va 2 E Ed for E [1.c]. Without loss of generality, we assume
Ei exp(u) 2) S Ei-i exp(u, 2). Let = - (cxp(e) z) exp(u]zz) and Ç
max [u ||: ||]]]] We have Ei=1 sin. S Dis Stn. with high confidence.
Proof. If there is a constant a E [0, 1] such that we have 0 S _ Ei= exp(11 2) - Ei= Sia S
as and 0 S Ei= g(n)
- 1 - exp(ux 2) (1 11-a)) are at the same time, can show
S(n) 02
exp((T 2) ((n) 0, + Stmt - exp(u =0) S CE.
(43)
U
Conversely, if
2i=1 Ui
> 1 Li=1 s(n)
we have either Ei exp uu 2) >) Son > acE
or
Di=1 Du.
(n)
Di=1 exp(1i, [1, 2) > (1 a)es for the a. For the first case, we have
Pr
exp U 2)
Σ
s(n) 012
2
acE
(44)
1=1
i=1
na E22
< exp
(45)
max (EE -ii m
2i=1.==1 Cov (n)
2a2E202
cxp
(46)
Σ i=cj=c
i=1.j=1 Cov(S!!)) s(r)2) + phllis
na?E20²
exp
2 > i=aj=c i=1y=1 exp((e: + T (u, 2)) exp (1, 22,20022)
(47)
<xp
(48)
2 2( : (xp(x:2))<cxp(223)
na 222
=:exp
(49)
2,33 exp(2(2)
Here, we define Bu := 1ل= exp(v:2) for simplicity. Similarly, we have for the second case:
Pr
S(n)
exp(u 2) 2 (1-a)cs)
(50)
n1( 222
I exp
(51)
(>i= 11)2 > vi=o,j= Cov(s!m) s6zr12)
2 max
n11 222
< exp
(52)
2 DE >=ay= exp((u; + 2) (u, + 2)) exp un. 2 + u. =)
n11 - ((1-))2223 2222
<exp
(53)
2( 2(
exp(2
19

---

Published as a conference paper at ICLR 2025
n(1 - 2222222 2 exp(2(3)
=:e
(54)
We choose = Bo/(9u + Bu), which means
=2
nC²
exp
2exp(2(2))82 = =exp
(55)
2exx(2(2) + Bun2
and
n(1 - o²2
nc²E²
exp
2 2exp 22xp(2
= exp
2exp(2(2) + B,,
(56)
Putting all together, we have
Pr
S(a)
S(n)
(57)
x=1
Pr
Σ i=1
exp(1; U2 2) - -S(1!
acs
+r
Σ
((a)= =pp(u.z)) (1 a)ee
i=1
(58)
E²
<2exp
(59)
2 (exp(2(2)(A) Bu)
( - -duu)
=:2 exp
(60)
V2 e2exxp(22)
where we use d' == B/ + Bu) and a', == Bu/(Bo BB)) for simplicity.
Lemma 9. Given any us Us
E Rd for i E [1, Without loss of gen-
erality,
we assume Σi=1 expl u ((T2/Vd) S Ei exp i. 1. 2/vd).
Let E have
Di exp 0, 22/vd) - exp(u u z/va) and Ç = max |u: |/10/1. ||=]].
(n) E Su.z
5 Ei= S with confidence least
Vn(a', d',) exp exp (2/Vd)
1 - 2exp
(61)
Proof. This is a direct application of Lemma 8 by scaling vi u. and z in Lemma by 1/ Vd.
C THE PROOF OF THEOREM 2
Now we provide the proof for Theorem in the main text.
Theorem 2. Let Radar be at a state of e segments where each segment contains tokens. Withous loss of generality, assume the first segment kiste has the highest attention score 01:1+e W.E.t. the current query q. With confidence at least we have
max (1
if the minimum gap 01:1+e - max atite 2 1 exp / $log(2(e-1)/6) Here, Ç is the maxi- mum norm among k; and q. whereas E [1, 11,1+a0 c, 2c, ..., 1 (c- 1)cl is the starting index of each segment.
20

---

Published as a conference paper at ICLR 2025
Proof. Let Bg denote the summation of the unormalized attention weights in ith segment
Σj exp q keit/vvd) We know that B1 2 3 for all 1 by our assumption. Let
& := (31 - 3.)/c be the difference between the first and the ith segment. According to Lemma the probability of confusion between segment 1 and has
8, S2exp (-( Vilai -())
(-(X
(62)
/2exp( (osp((//V))
where == 3:/(31 + B.). The real attention score for ith segment is a, Ba/ Ej/ Bj. meaning
8, <2exp/ 1 (-(Veexp
2
2 exp (-
(-(22 12 (2/vd) (c//V))(2a)) (2a1)
VTe
-
VNe
(3/ed)((///de)) aa))
(63)
where: == min; E; is the minimum gap.
The probability of making at least one confusion is
(-(
Tne
8, 2(c exp
(64)
V2 expe (2/v (d) (2a1)
This is equivalent
log 1log(2(c 11)6))
8 8 an exp exp expp(e//V) (2/va)
(65)
which concludes the proof by taking the contraposition and noticing that 01 2 1/c.
D ADDITIONAL EXPERIMENTS
In Section 3.1
we mainly test our methods against StreamingI.LMM Xiao et al. 2024 and the vanilla
attention Vaswani et al. 2017). In fact, we also consider H₂O (Zhang et al. 2023) and SnapK (Li
al., (0024) as our baselines. Following the same settings as in Section 3. we show their perfor- mance in Figure
Vanilla
StreamingLIM
Radar
H₂O
SnapKV
Mistral PG19 (PPL)
Mistral PG19 (Time)
5000
7.09
10
4000
16.71
10a
3000
10a
2000
:0.00
15 34 is
1000
38.53
10
5.64
38.53
Steps
x10*
Steps
x10*
Figure 6: Failures of H₂O and SnapKV on Mistral.
As observed, both methods suffer from the considerable degeneration under this setting The per- formance of H2O, similar to its non-conditional generation with Mistral models (in Section 3.3 has
It should be pointed out that we do not consider their failures are due to replication, because
successfully reproduce their results under the settings in their papers (c.g., Scction 3.2 and Section 3.3
21

---

Published as a conference paper at ICLR 2025
extremely high perplexity, indicating its unsuitability beyond a limited model architectures like Llama. SnapKV, albeit having a low complexity at the beginning. shows a considerable loss degra- dation during generation. This aligns with observations in Section 3.2 where SnapKV generally underperforms Radar when the ground-truth generation is long. The results also suggest that Radar generalizes better than other baselines. We hypothesize that this is because methods like H2O and SnapKV heuristically use the accumulated attention scores as the indicator of the importance. The heuristics may lead to evicting the current unimportant tokens which will be very useful later for new tokens, especially when each head is responsible for multiple query spaces (e.g., grouped-ques -uurry at- tention (Ainslie al., 2023) used in Llama 3 and Mistral models). Evidently, we observed that both methods tend to perform worse these models. By contrast, Radar is based on a proven approxi- mation of the vanilla attention. The error bound well-established our Theorem 2 regardless of the model architectures and weights, making it more versatile in applications.
E VISUALIZING THE APPROXIMATION
In Theorem theoretically show the correctness of our method. To provide intuition for the approximation, we visualized the Radar approximation using Llama 3 on the 100 tokens (after sink token) of PG-19 partitioned in 10 segments. The results are displayed in Figure
(Tokas)
Allatton TTkee)
20
60
20
40
80
20
40
6G
Vasilla Attention (Seamenn))
Vanilla Aftention (Segmeen)
Vanill Aftorrion
Rodar Attenios (Sggmett)
Rodar Alterion (Sogmant)
Radar Attention (Segment)
(a) Head 1.
(b) Head 20.
(c) Head 30.
Figure Visualization of the vanilla token-level attention (top), the corresponding segment attention (middle), and the approximated segment attention by Radar (bottom). Here we use three heads in the first layer as an example. The dark blue and red represent low and high attention scores, respectively.
It is straightforward to see that Radar (the bottom row) provides a reasonable approximation of the real segment attention (the middle row). Notably, Radar not only captures the top segments but also correctly flags the runner-up segments, suggesting its ability in identifying multiple important segments simultaneously. Empirically, we found that 34.38% of Radar's 's approximation success- fully flags the top segment among the 10 segments with k = 1. When we increase k = 3, the successful rate is 62.5%. These are considerable higher than other segmental selection strategies based on heuristics. For example, by selecting the most recent segments (i.e., extending the sliding window for StreamingLLM (Xiao et al. 2024)), the corresponding rates are 18.75 18.75% and 46.88% The random selection strategy is expected to achieve 10% and 30%. Both methods underperform Radar significantly.
F DISCUSSION ON FUTURE WORK
Non-contiguous segmenting strategies. this work, we propose to use contiguous tokens to construct a segment. This is generally a safe practice because the important tokens are sparse in a sequence (as visualized in Figure and previous work like StreamingLLM Xiao et al.] (2024)) ). In addition, by selecting the surrounding tokens around the important ones, could provide the context for the model to correctly identify the semantics for these tokens. Our design could natu- rally achieve this goal, while other methods like SnapKV (Li et al. 2024 need to explicitly apply
22

---

Published as a conference paper at ICLR 2025
smoothing techniques to encourage the surrounding selection. Nevertheless, consider that there could exist better segmenting mechanisms for Radar by developing an adaptive method. We hope this paper serves as the foundation for the future exploration of this direction.
Memory-efficient Radar. Our method mainly focuses on accelerating the decoding efficiency of modern Transformer models. However, Radar does not save runtime memory. In fact, it uses marginally more memory (scaled at a O(vi) rate) to maintain the segment representations. There- fore, consider the memory-efficient version of Radar as a promising future direction. For ex- ample, one could exploit the hierarchical structure of Radar to align with the memory hierarchy by off-loading. By doing this, we hope Radar could match the effective memory saving with previous memory-efficient decoding algorithms (Zhang et al. 2023 Li et al. 2024
Zandich et al. 2024).
Training with Radar. Our method is designed as training-free acceleration algorithm to duce the training cost for broader users. However, we expect training with this kind of hierarchical approximation could yield better results. We leave this to future exploration.
23


Reviews:
[{"review_id": "v1pOCb4ffY", "reviewer": "Reviewer_RGXx", "summary": "The paper describes a training-free approach to speed up attention computation over a long context, by essentially performing a hierarchical search for the 'closest' tokens in the attention dot-product. Tokens are grouped into segments, and attention is restricted to the closest segments --- which itself is found through dot product attention to a 'segment'-level averaged projected feature.\n\nThe paper provides theoretical analysis of this approximation, and experiments show speedups over vanilla attention without significant drop in quality.", "questions": "In addition to speaking to the weaknesses listed above, it would be good if the authors could discuss whether they think this kind of hierarchical approximation to attention might work even better if it were included during training, not just as a post-training step.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is very well written and motivated.\n- The hierarchical search approach is novel, as is the use of averaged random projection features to allow identifying segments without retraining.\n- The theoretical analysis is a nice addition to the paper and is insightful in understanding why we expect the approach to work.\n- The experimental results are solid, and the approach appears to achieve real speedups when run on GPUs (not just in theoretical flops).", "weaknesses": "- There seems to be an assumption that segments should be made of contiguous tokens. This might be a safe assumption, but should be discussed. I can imagine an 'adversarial' setting where the ideal attention matrix would have been centered on a subset of tokens spaced far apart (i.e., each in a different segment). The theoretical analysis could perhaps have focused on this as well (how likely it is for the top-k segments to include the top-k tokens).\n\n- It would have been nice to include some examples of the true and approximated attention maps (as heatmap figures, and perhaps also as text examples). We only see performance numbers at the final task, but not directly how well attention is being approximated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gwumvpmxaI", "reviewer": "Reviewer_v6nX", "summary": "Transformer are the core of LLMs. This paper introduces a novel approach coined \"Radar\", which accelerates inference and is even training-free. Theoretical results are provided and the effectiveness is shown by numerical experiments.", "questions": "no questions", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The new approach selects the most important tokens with high probability.\n* It accelerates inferences for transformers.\n* The method does not need to be trained.\n* Theoretical results are provided.\n* Also the numerical results are convincing.", "weaknesses": "no weaknesses", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n6QarZNYLs", "reviewer": "Reviewer_Un5J", "summary": "This work introduces a novel training-free approach that accelerates inference by dynamically identifying the most important context tokens. The paper also provides proofs of algorithmic correctness and includes a time complexity analysis. The experimental results indicate competitive performance.", "questions": "See weakness. If I made mistakes, please tell me and I am glad to give a high score.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The problem addressed is significant and appealing, focusing on a crucial aspect of LLM performance.\n2. The paper presents a novel approach for accelerating LLM inference by selecting the most important context tokens.\n3. The authors provide detailed proofs of algorithmic correctness and analyze the time complexity.\n4. The experimental results are competitive, highlighting the effectiveness of the proposed method.", "weaknesses": "1. The analysis of time complexity needs more detail, particularly regarding lines 8 to 11 of Algorithm 1. This dynamic restructuring step may take more time than $O(t)$. Based on my understanding, this section could have a total time complexity of $\\sum_{c=1}^{\\sqrt{t}} c^2 = O(t^{3/2})$. Thus, the time required for calculating the importance score of a single segment is not constant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6B5qzUiuL4", "reviewer": "Reviewer_VET1", "summary": "The paper proposes a new method to approximate the softmax attention mechanism in transfomer architecture. The method works by segmenting the key embeddings and then for each query picking a few segments which have highest attention scores on average and computing the attention scores for the keys in those segments exactly. The mehtod uses random features proposed in the Performer paper  to estimate the average attention score of each segment.", "questions": "- How does your method compare against the aforementioned works in experimental evaluations?\n\n- The paper does not clarify how tokens are segmented. Do you segment the stream of tokens into contiguous chunks, or do you employ a different ordering method?\n\nAdditionally, I would like to note: please try to address my concerns, and rest assured that I will consider raising my score if you provide sufficient experimental results during the rebuttal.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper proposes a practical and easily implementable algorithm that demonstrates strong performance compared to existing streaming attention and sliding window attention methods.", "weaknesses": "The paper lacks a comparison with several relevant works focused on attention acceleration. Notably, the following papers explore sparse, low-rank, and combinations of these approaches with near-linear runtimes for long context, and it remains unclear how the proposed method measures up against them:\n\n- `Chen, Beidi, et al. \"Scatterbrain: Unifying sparse and low-rank attention.\" Advances in Neural Information Processing Systems 34 (2021): 17413-17426.`\n- `Zandieh, Amir, et al. \"Kdeformer: Accelerating transformers via kernel density estimation.\" International Conference on Machine Learning. PMLR, 2023.`\n- Han, Insu, et al. \"Hyperattention: Long-context attention in near-linear time.\" arXiv preprint arXiv:2310.05869 (2023).\n- `Zandieh, Amir, et al. \"SubGen: Token Generation in Sublinear Time and Memory.\" arXiv preprint arXiv:2402.06082 (2024).`\n- `Roy, Aurko, et al. \"Efficient content-based sparse attention with routing transformers.\" Transactions of the Association for Computational Linguistics 9 (2021): 53-68.`\n\nAdditionally, this method does not tackle the memory concerns regarding storing key-value embeddings in the KV cache; it requires retaining all key and value embeddings in the cache during the generation phase.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0brXsKt03B", "reviewer": "Reviewer_LfUC", "summary": "This paper proposes an algorithm for accelerating LLM inference by efficiently selecting of important tokens. Its headline claim is a reduction from $\\mathcal{O}(t^2)$ sequence length complexity to $\\mathcal{O}(t^{3/2})$.", "questions": "- Do you have any intuition for why the H20 and SnapKV methods perform so poorly when applied to the Mistral PG19 model (Appendix C)? The difference is quite striking, so it would be useful to have at least a hypothesis for why these methods do not generalize across architectures. This could also provide useful context for why the proposed method successfully generalizes. \n\n- There appears to be a typo on Line 837, as the square brackets enclose the equality. \n\n- It might be useful to state Lemma 1 in terms of concentration to the expectation at large $n$, as that could give a bound on error in a practical setting. \n\n- Given that the claimed time-complexity improvement is in the exponent of a power law, it would be useful to use logarithmic scales for time in the figures, so that one can see how tight the bound is. \n\n- It could be semantically useful to use a different color scheme for Figure 4, to distinguish the fact that here different dimensions are being used rather than different algorithms.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I am not an expert in efficient approximations to softmax attention, so I cannot confidently speak to the novelty of this algorithm relative to other methods. I will confine my comments to the results as presented. The proposed algorithm is simple, and the experiments demonstrate that it achieves a seemingly reasonable balance of accuracy and efficiency. Moreover, I found the paper to be reasonably clearly written.", "weaknesses": "In my mind, the paper would be stronger if there was a clearer link between Theorem 2 and the experiments. Namely, unless I've missed something, the authors don't actually measure whether their algorithm retrieves the correct top-k index set in their experiments. It would be useful to do so, and to comment on whether by those results the bound in Theorem 2 is practically useful or not. It would also be useful to know something about the distribution of attention scores, which would affect what value of $k$ is reasonable. More precise (and in some sense more mechanistic) quantifications could help the reader get a better sense of why your method works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)