VCC: Scaling Transformers to 128K Tokens or More by Prioritizing Important Tokens
Authors: Zhanpeng Zeng
Cole Hawkins
Mingyi Hong
Aston Zhang
Nikolaos Pappas
Vikas Singh
Shuai Zheng
Venue: NeurIPS 2023 poster (2023)
Keywords: efficient
transformer
roberta
T5
language modeling
question answering
summarization

Abstract: Transformers are central in modern natural language processing and computer vision applications. Despite recent works devoted to reducing the quadratic cost of such models with respect to sequence length, dealing with ultra long sequences (e.g., $>$16K tokens) remains challenging. Applications such as answering questions based on a book or summarizing a scientific article are inefficient or infeasible. Here, we propose to significantly improve the efficiency of Transformers for ultra long sequences, by compressing the sequence into a much smaller representation at each layer. Specifically, by exploiting the fact that in many tasks, only a small subset of special tokens, which we call VIP-tokens, are most relevant to the final prediction, we propose a VIP-token centric compression (VCC) scheme which selectively compresses the sequence based on their impact on approximating the representation of the VIP-tokens. Compared with competitive baselines, our algorithm is not only efficient (achieving more than $3\times$ compute efficiency gain compared to baselines on 4K and 16K lengths), but also offers competitive/better performance on a large number of tasks. Further, we show that our algorithm scales to 128K tokens (or more) while consistently offering accuracy improvement. Code is available at https://github.com/mlpen/VCC.

VCC: Scaling Transformers to 128K Tokens or More by Prioritizing Important Tokens
Zhanpeng Zeng University of Wisconsin, Madison zzeng380visc.edi
Cole Hawkins AWS AI
colehawk@amazon. com
Mingyi Hong
Aston Zhang AWS Al
University of Minnesota, Minneapolis & AWS Al mhongSumn.Co edu
astonz@amazon.co com
Nikolaos Pappas AWS Al
Vikas Singh
Shuai Zheng
University of Wisconsin, Madison vsingh@biostat. wisc.
AWS AI
appappa@amazon.cmm com
shzhengGamazon.c com
Abstract
Transformers are central in modern natural language processing and computer vision applications. Despite recent works devoted to reducing the quadratic cost of such models with respect to sequence length, dealing with ultra long sequences (e.g..> >16K tokens) remains challenging. Applications such as answering questions based on book or summarizing a scientific article are inefficient or infeasible. Here, we propose to significantly improve the efficiency of Transformers for ultra long sequences, by compressing the sequence into a much smaller representation at each layer. Specifically, by exploiting the fact that in many tasks, only small subset of special tokens, which we call VIP-tokens, are most relevant to the final prediction, we propose VIP-token centric compression (VCC) scheme which selectively compresses the sequence based on their impact on approximating the representation of the VIP-tokens. Compared with competitive baselines, algorithm is not only efficient (achieving more than 3x compute efficiency gain compared to baselines performance on a large number of tasks. Further, we show that our algorithm scales to 128K tokens (or more) while consistently offering accuracy improvement. Code is available at httph:t///// htt:://gtttttt thub. com/ con/mlpen//CC
4K and 16K lengths), but also offers competitive/better
Introduction
The Transformer 32] is a fundameenal/Founndatonn architecture for natural language processing (NLP) and computer vision. It has shown remarkable performance across NLP applications including machine translation [32]. language inference [10]. and summarization [14]. Transformers have also been successfully applied to various visual recognition tasks and achieve impressive results [T]] 41).
Unfortunately, the runtime/memory needs Transformers involve an unfavorable dependence on the input sequence length, making the of Transformers for ultra-long sequence applications difficult. Therefore, many studies on Transformers make use of strategies such as truncation to ensure that the input sentence length is most 512, e.g., BERT, T5, and other Transformer-basse language models [36 [2 22]. Unfortunately, such truncation, and other related strategies, inevitably results in loss of accuracy, the extent of which can vary from one task/dataset another. Consequently, improving the efficiency for longer input sequence length is key focus of many proposals. These developments are
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

important milestones, and they have reduced the quadratic dependency on sequence lengths to linear 6
40 39]. Currently, many Transformer models can process samples with sequence lengths of up to 4K (and even 16K). Very recently, results of newer models being able to handle much longer sequences have appeared [3]
25
35
2
38
Rationale. It natural to ask whether the ability to process longer sequences is worth the trou-
Tranuformet
Longfomerr
1500
ble. The short answer is yes. Improved accu-
Rurniee (ms)
Memory (GB)
30
racy has been reported on long sequence tasks 22 [4]. So, what is stopping us from harvest- ing even stronger gains in accuracy by feeding even longer sequences to such models? Models such as Longformer [2] and Big Bird [8 be- come slow and consume an excessive amount of memory as the sequence length keeps increasing. See Fig. for illustration. Why? The represen- tation update of every token involves computing efficient attention and feed-forward network at each layer. This incurs linear cost relative to the sequence length and is expensive for sequences much longer than 4K (or 16K) tokens. To endow the need to lower this cost. What we describe
1000
29
500
10a
10'
10
107
10f
10a
Sequencei Length
Sequancal Longhh
Figure I: Model efficiency of processing one se- quence on a NVIDIA A100 as sequence length increases (note logarithm x axis).
models the ability to learn ultra-long range dependency, in this paper is a concrete step forward based on certain sask-specific assumptions which appear to generally hold, outline formulation that works and delivers the expected improvements.
(1) Focus on what we need for a task: VTP-token centric compression (VCC). We hypothesize/fnd that in many tasks where Transformers are effective, only a small subset of tokens, which we refer to as VIP-tokens, are relevant to the final output (and accuracy) of a Transformer. If these tokens had been identified somehow, we could preserve this information in its entirety and only incur moderate loss in performance. Now, conditioned on these specific VIP-tokens, an aggressive compression on the other non- VIP-tokens, can serve to reduce (and often, fully recover) the loss in performance while dramatically decreasing the sequence length. This compression must leverage information regarding the VIP-tokens, with the goal of improving the upproximation of the representation of the VIP-tokent In other words, a high-fidelity approximation of the entire sequence is unnecessary. Once this "selectively compressed" input passes through Transformer layer, the output sequence is decompressed to the original full sequence allowing the subsequent layers to access the full sequence.
(2) Specialized data structure for compresion//decoppres// tical issue, is reducing the overhead when conpressing/dccomprssinn the input/output sequences internally in the network. Ignoring this problem will impact efficiency. We give simple but special- ized data structure to maintain the hidden states of the intermediate layers, where the compression can be easily accessed from the data structure, and explicit decompression the data structure: the sequence is never fully materialized in intermediate layers.
A secondary, but important prac-
be avoid by updating
Practical contributions. Apart from the algorithmic modules above, we show that despite an aggressive compression of the input sequences, we achieve better/competitive performance on a broad basket of long sequence experiments. Compared to baselines, we get much better runtime/memory efficiency. We show that is now practical to run standard Transformer models on sequences of 128K token lengths, with consistent performance benefits (and no complicated architecture changes).
2 Preliminaries
We review the Transformer layer, related work on efficient Transformers and define nota- tions/simplifications. BOLD uppercase letters denote matrices, bold lower case letters denote vectors, and regular lower case letters denote scalars or functions.
Brief review of the Transformer Model. Fix n to be the sequence length and let d be the embedding dimension. Define an embedding matrix X Raxd which gives the feature vector inputs for a Transformer layer. The output of this Transformer layer, Xnew, is defined as
X = (X) + X) + (X)) + X
using (X) as shorthand for al. which multi-head attention (MHA) with X as input for queries, keys, and values, described shortly. Here, 3(-) is a feed-forward network (FFN). Layer
2

---

norms []] are omitted to reduce clutter. Let the inputs to a(.,'.) be Q K. V E R for queries, keys, and values. MHA defined as:
a Q K. V) == cat |softmax ( (QWa o W K. K v. W
(2)
where g is the number of attention heads, (WQ... K. Wv.3} are trainable projections, and the 'cat' concatenates the outputs of multiple self-attention modules. We omit the biases for notational simplicity. For ease of discussion, let us further simplify the above notation by assuming that g = 1, and suppress W Q,1, W K, v,1, W as well the normalization in softmax: they will still be estimated within the model (i.e., this module remains unchanged) but are tangential to the description of our idea. With these simplifications, the -- can be expressed as:
Q K, V) == exp(QK
Let 7()) be a placeholder for all heavy computations in the Transformer layer above: (X) := 3(a(X) + +X)+ (X)).
(4)
We can verify that the output of a Transformer block (parameters are suppressed to reduce clutter) is,
Xnew - (X) + X
(5)
A Transformer model consists of many such layers: the input of each layer is the output Xnew from the previous layer. Let be the number of layers, then the overall complexity is O + Ind.).
Efficient Transformers. Many efficient self-attention methods are available to reduce the (In2d) cost. We list a few models noting that this list not exhaustive. Performer (6, Random Feature Attention 225. and Nyströmformer 35 propose different low rank approximations of the self- attention matrices. Longformer [2] and Big Bird (38) describe global + local sparse attention. Reformer [17 and YOSO 44) exploit locality sensitive hashing for approximating the self-attention matrix. MRA attention [39] gives a multi-resolution approximation of the self-attention matrices. Memorizing Transformers (3 and RMT 33 follow a recurrent design and store the past context in an external memory module. By sequentially processing one segment of input sequences at one time, they avoid blowing up the memory when processing long sequences.
Efficient Transformers do not scale well to ultra-long sequences. Existing self-attention mecha- nisms often reduce the quadratic cost of MHA to linear. But so far, most experiments report sequence lengths of up to 4K, with some exceptions 2 38 14. Beyond 4K, the linear cost (on n) for both computing efficient attentions and FFN makes the cost prohibitive, especially for large models. For example, although LongT5 [14] can train on sequence lengths of up to 16K tokens with an efficient self-attention and shows promising results for longer sequences, it is slower and needs sizable amount of compute (for example, see Fig. D. Similar to efficient self-attention with linear cost attention, [34] and (3) do not try to reduce the linear cost (on sequence length) for FFN, so the computation might still be expensive for processing ultra long sequences. On the other hand, method seeks reduce the overall cost (both self-attention and FFN) of processing ultra long sequences and processes the entire sequence simultaneously.
Other alternatives for sequence compression? Compressing input sequences for efficiency reasons in Transformers is not new idea. For example, g and [T6) propose pyramid Transformer variants that progressively compress the sequence the layers grow deeper via pooling or core-set selection. (23 proposes adaptively compressing the sequence based on the predicted semantic boundaries within the sequence. [26] proposes compressing the fine- fine-grained past activations to coarser memories. There are three key differences with our approach. First, all methods listed above are task agnostic. They seek compressed/smaller representations to represent the original sequence well. Our formulation places no emphasis on representing the original sequence, as long as information pertinent to the VIP-tokens is preserved as much possible. Second, once these methods compress the sequence, the residual information is lost (for the deeper layers or the later time steps). Our entire approach is predicated on avoiding this loss we maintain access to the full sequence each layer (via residual connection at least). Lastly, some of these ideas often involve an n² dependence on the sequence length in the initial stages of their formulation, making long sequence experiments problematic.
3 VIP-Token Centric Compression (VCC)
Our main goal is to reduce the dependency on n (but not by modifying Transformer internals). To do this, we describe a scheme that compresses the input sequence of Transformer layer and
3

---

decompresses the output sequence, resulting in a model whose complexity is O(Ird + I + Ir (o.(m))d + lrn,d + nd). Here, r is the length of the compressed sequence, "p is the number of VIP-tokens described shortly, and is the size of non- non-ViP/remaining tokens. So, we have Up + ne = n and assume " < r E n. (complexity analysis is provided in the Appendix.)
Let us unpack the term to assess its relevance. The first two terms Olrdd + dr pertain the cost for Transformer, while the remaining terms are the overhead of compression and decompression. The term (Ir log(ne)d + (rn,d) is the overhead of compression and updating our data structure at each layer. The (nd) term corresponds to pre-processing involving converting the hidden states into our data structure and post-processing to recover the hidden states from the data structure. Note that unlike the dependence on n for vanilla Transformers, this O (nd) is incurred only at the input/output stage of the Transformer, but not at any intermediate layers.
Parsing the complexity term:
High level design choices. We use the standard Transformer layers with standard feed-forward network (which results in d² in the first term) and standard quadratic cost self-attention (which gives the ,2 factor in the second term). Why? These choices help isolate the effect of incorporating their efficient counterparts. The proposed algorithm operates on the input/output of each Transformer layer leaving the Transformer module itself unchanged. Therefore, our goals are distinct from the literature investigating efficient self-attentions and efficient feed-forward networks. This is because one can replace these two vanilla modules with any other efficient alternatives to further reduce the r² and d² terms directly. Despite these quadratic terms, our approach is faster than baselines ($4)
We will first describe our general idea, as shown in Fig. 2 which uses VIP-tokens to guide the compression/tecomprssiio of the input/output of a Transformer layer so that it only needs to process the compressed sequence ( (.2)). Then, we will discuss instantiation of the compression process, by adapting a multi-resolution analysis technique ($3.3). Lastly, we will introduce a data structure which allows more efficient compressin/ddeoomrrssiin ($3.4).
3.1 Elevating the Importance of Few Tokens: VIP-Tokens
Let us start with the simplest compression, which identifies linear transformation S R which acts on the input, resulting in a smaller representation SX E Rrxd, Of course, a smaller r implics that more information about X is lost. But we find that in many tasks, only the embedding representations of a few tokens drive the final prediction: we refer to these tokens as VIP-tokens.
Examples of VIP-tokens: Observe that only the embedding outputs of masked tokens in masked lan- guage modeling [0] and the CLS token in sequence classification [ are/is used for prediction. In question answering, only the questions and possible answers associated with the questions are used for prediction. is important to note that the masked tokens, CLS tokens, and question tokens are (1) defined by the tasks and (2) known to the model (although the embedding representation of these tokens are unknown). These VIP-tokens can be viewed as a task or question that is given to the model. The model can process the sequence with specific goal in mind that the model can skip/skim less relevant segments. Our general principle involves choosing a set of tokens as the VIP-tokens that (1) important to the specific task goals and (2) easily pre-identifiable by the user.
Caveats. Not all important tokens can be pre- pre-identified. For example, the tokens in the correct answer span in answer span prediction are also important to the specific goals, but are difficult to pre-identify, so only the question tokens (and not the answer tokens) are used as VIP-tokens. We assume that any other tokens that are relevant for prediction should have high dependency with these VIP-tokens. For example, the answer tokens should have high dependency (in self-attention) to the question tokens.
VIP-tokens occupy the front seats. VIP-tokens can occur anywhere within sequence. But we can re-order the sequence as well as the positional encodings so that VIP-tokens are always the head of sequence to make mmallsis/implementaii
easier. With this layout, let P e I Xd be the VIP-tokens and C E R xd be the non- VIP/remaining tokens, X can be expressed as
P C
X
(6)
This is possible since Transformer is permutation invariant when permuting positional encodings (embeddings or IDs) along with tokens. This re-ordering is performed only once for the input of the Transformer model, then the outputs generated by the model are rearranged to their original positions.

---

Re-ordering makes the analysis. implementation and presentation of our method much clearer and simpler. In fact, placing VIP tokens at the end of the sequence can also serve the same purpose.
From the above discussion, it is clear that one needs to make sure that after compressing the input tokens X, the VIP-tokens must still stay (more less) the same, and the compression matrix S must be VIP-token dependent. We hypothesize that such VIP-token dependent compression matrices require a much smaller dimension 7, compared to VIP-token agnostic compression matrices.
3.2 VIP-Token Centric Compression (VCC): An Initial Proposal
For Transformer layer, let X denote its input matrix. Express the output of this layer follows:
Residual Connection
Decmpression
Residual Connection
X new St (SX) X
(7)
Transformer Layer (7)
where S E -rxx is a compression matrix compressing
S.C
X to smaller representation and St is the pseudo
inverse for decompression. With the layout in 66. we
Token Centric Comppression (8.)
write 7 as
VIP-tokens
Remaining tokens
P Pnew C Cnew
P C
P
S
S
(8)
Figure 2: Diagram that illustrates Trans- former layer with VIP-token centric se- quence compression.
where P new and Cnew are the new embeddings for P and C.
Always reserve seats for VIP-tokens. What is useful structure S? Since Pnew is the embedding output for the VIP-tokens P. we want them to be fully preserved. To achieve this, we impose the following structure on and S
S Inp
Iap 0
st
S.
s
The rearrangement simply says that we will avoid compressing But rewriting it in this way helps us easily unpack (8) to check the desired functionality of S..
Prioritize information in VIP-tokens. Our goal is ensure Pnew generated from the compressed sequence in (8)
will be similar to its counterpart from the uncompressed sequence. Let us check (8) using the compression matrix S defined in (9) first. We see that
IapXR X
01, St
( (s.c)) = SX, SX, SX) + S.C) S Sx) (10)
(
B(a SX. SX) + +P) + a sx. SX)
The orange color identifies terms where P new interacts with other compression-related terms C and/or S.. We primarily care about Pnea R), so the first (orange) row in (10) the main concern. We see that P new only depends on the compressed SX via ((P, SX, SX). We can further unpack,
((P, SX. SX) (Px ST
S SX eXP P + exp PCC PCTTT
(11)
Again, (P,, SX, SX) depends on C and S, via the second (orange) term. Normalization soft- max is omitted for simplicity of discussion. This helps focus on the key term that matters: exp S.SCC. As long as the following approximation using S. is good
ex x Txp(PCT),
(12)
we will obtain a good approximation of new Our remaining task to outline a scheme of finding a compression matrix S. such that this criterion can be assured.
3.3 A Specific Instantiation via Multi- Compression
What should the mechanies of our compression such that 12 holds? general, to get S., we can use any sensible data driven sketching idea which minimizes the error of (12). Doing so efficiently needs bit of work; we describe the high level idea below and the low-level details are provided in Appendix.
5

---

High level idea. Ideally, an efficient scheme for constructing S. should operate as follows. If some regions of the sequence have a negligible impact on (12) (via the orange terms above). the procedure should compress the regions aggressively. If other regions are identified to have higher impact on (12) (again due to the orange terms above), the procedure should scan these regions more carefully for more delicate compression. This suggests that procedurally coarse-to coarse-to-fine fine strategy may work. For example, multi-resolution analysis does help in approximating self-attention matrices in Transformers [39], but the formulation in [39] cannot be easily written in a form similar to (12), making it incompatible with our design. Nonetheless, we derive an analogous form (details in Appendix) that can be represented in similar form as (22 and gives strategy for obtaining S.C.
Specifically, let us define compressed representation (via averaging) of the æ-th s-length segment of sequence C: c E Rd
Σ E2-aciSez
[C];
(13)
where 8 E (k:,, A ,.,.... n assuming nhe is a power of k and x E to the i-th row of the input matrix. We fix the increment ratio k = 2 for simplicity of discussion. The 8 represents the resolution of the approximation: it represents the number of non- VIP token embeddings being averaged into a vector c.. Higher 8 (e.g., s 8 in oi in Fig. 3 means lower resolution and heavier compression of the corresponding segment. The z represents the location of the s-length segment within the sequence C. In our scheme, we compress the sequence C and use set of c for some selected s's and x's as the rows of the compressed S.C as seen in Fig. 3 The sequence C is broken into multiple segments of different lengths, then each segment is compressed into a vector c
[]] refers
Procedurally, as shown in Fig. 3 our scheme starts with the heaviest compression and progressively refines cer- tain segments of C guided by the VIP-tokens P. The scheme starts with the heaviest compression that treats C as a neengghth segment and compresses it to single c.o Then, starting with s = Te (root node), the proce- dure (1) computes the averaged attention scores between VIP-tokens P and c 's for different xz's (averaged over all attention heads and all VIP-tokens; only one c/ at level $ = n2.). We note that the attention scores are obtained by extracting attention matrices from MHA module (2) of the current Transformer layer when using P as queries and of 's as keys. Then, it (2) splits the s-length segments corresponding o% 's with higher averaged attention scores (one segment is split in Fig. 3 but we might split more segments, again only one ci at level s = n2.) into (s/2)- length sub-segments: the corresponding ci/ L3) of each sub-segment is computed for finer representation. Then, at next level for s = ne/2, the same procedure proceeds. This process continues until the sebbeetmmnts have length We note that this procedure is guided by the VIP-tokens and designed maximally reduce the error of approximating (12). No additional learnable parameters are introduced for this scheme. The technical details of this algorithm are less relevant for our overall approach, but for interested readers, the details are discussed in the Appendix.
[
[C
[C
[C
[C|s
[C]
[C
Bricese a hightr scurg
S.C
Ci
C2
Figure 3: Illustration of multi- multi-resolution compression. n4 8. Purple line: com- pute attention scores between P and dif- ferent segments. Green arrow: segment with higher attention score is split into two sub-segments. Accordingly, S.C = [c]
c/ cg]
is constructed.
How good this approximation? The output P Pnew (8) is well approximated since the approach preserves the relevant components of C that have a high impact on the output P new. Further, if the VIP-tokens P have high attention weights for some rows of C, then the corresponding row in C will be approximated with higher frequencies (less compressed). So, the output in Cnew (8) for a subset of non-VIP tokens that have higher dependency with the VIP-tokens will have a better approximation than the others, as desired. This property is useful since some tokens with unknown locations but manifesting high dependency with the VIP-tokens can also relevant
Act AC
Ac act Act
Ac
Aet
ACJ
Act
Aej
Ac!
Act
dck
Figure 4: Proposed data structure T(C)

---

to the final prediction of a Transformer model in some tasks. The answer in span span-based based question answering tasks is one example, and our construction ensures that they will be approximated well too.
3.4 Efficient Data Structure for Compressonn/Decoppesioo
By employing the procedure in $3.3 illustrated in Fig. we can find the compressed S,C with an On + rny4) cost at each layer. The main cost (n. is due to computing c defined in [3] for all resolution s and location 2 by using recursive relation from the bottom up:
2r
2
C -C
(14)
We find that these steps could introduce large overhead. Further, note that if we decompress (apply St to) the output of 7 for compressed sequence as in (8). the cost is O(nd) since the number of nonzero entries in Si is (more details in Appendix). As a solution, we now introduce a data structure (-) for storing C and Crew, as shown in 4 which enables efficient computation of c and eliminates explicit decompression. We note that this data structure is only possible due to the specific structure of S.C constructed in $3.3 Specifically, T(C) stores c/ and Ac; defined as
AC 0/2/21 C
(15)
for every resolution * ne and location I. Similarly, T(C stores (Cnew)) th and A A(Cnew)) where (Cnew); and A (Cnew)) )a are defined similar to (3) and (55 but using Cnew instead of C.
Then, given T(C), any c, can be retrieved efficiently in (log(n )d) cost via recursion:
c = = Act = c////1 Ac Ac
(16)
The only reason we need decompression St is that we need to obtain new representation Cnew (no decompression for Pnew since is uncompressed), Suppose we have T(Cnew), then we have an alternative way of getting Cnew similar to (16) (note (Cnew) ) =Cnnew] without explicit decompression. The key benefit of this data structure is that we can obtain T(Cnew) by changing some nodes in T(C). This only needs updating (rr) nodes, and each update takes ((d) cost.
An example. We show a T(C) for ne in Fig. Let S.C = [cî of Since the segment of is not split into sub-segments of and ch. we have (details in Appendix):
c4
dg] as in Fig.
3
(Cnew))
cj (Cnew)) - c³ (Cnew)) c ct
(17)
By rearranging (17.. we can verify that A A(Cnew)) A(Cnow)) 1 in T(Cnow) stays the same as Act, Ach in TCC and thus do not need to be updated:
A(Cnew) (Cnew) I (Cnow = ca
c =Ac
(18)
A(Cnew)2 (Cnew) (Cnew) cj c = Ach
Further, we can verify that only the green nodes in Fig. will be updated. These nodes correspond to the nodes in Fig. 3 that have been traversed. In summary. for each row cº of S.C' (a leaf node in Fig. B). only the node storing A(c); and its ancestor nodes in TCC) must be updated, so the total number of nodes (including their ancestors) being updated is (r)) Next, we can update the nodes follows: first, we get representations (Cnew) ). (Cnew)) (Cpew t (Cnew) Y/2 by feeding S.C into Transformer layer (details in Appendix). At level 8 = 1, given (Cnew )3 and (Cnew)) we (1) compute (Cnewr) ) via (14), and then (2) compute A(Cnew) 1/2 and ((Cnew)) ) via (15). The last two values are the new values 2, given (Cnew) )2 and (Cnew)2 computed at previous level, we apply similar procedure to obtain (Cnew)i 14 A (CCrew)) 22, A (Cnew) and the last two values are used to update two nodes in T(C). It becomes apparent that each node update takes ((d) cost. Putting it togather: the complexity of modifying TCC) to T(Cnew) is O(dd). The detailed algorithm and complexity analysis are described in Appendix.
for Act and Act in T (C).. At level
By maintaining this data structure, we never need to materialize the entire C or Crew in any intermediate layer, but instead we use (16) to construct the rows of S.C and perform updates to ((C) to obtain Czew (represented as ((Crew) 1) at each intermediate layer. At the output of a Transformer,
Cnew is materialized from T [[Cnew) at a ((n.d)) cost via the recursion (16) from the bottom up.
7

---

4 Experiments
We perform a broad set of experiments to empirically evaluate the performance of our proposed compression. (See hyperparamettrssdattss statistics in Appendix.) We evaluate our method on both encoder-only and encoder-decoder architecture types. We compare our method with baselines on a large list of question answering and summarization tasks, where we found long sequences occur most frequently. Then, we study the model performance of scaling to ultra long sequences enabled by our method. Since efficiency is the focus of the efficient baselines and our work, we include runtime efficiency (of single sequence) in millisecond in each table. (See the procedure for runtime measurement in Appendix.) We also include a discussion on FLOP efficiency in Appendix.
For ease of implementation and hyperparameter selection, we restrict the rows of S,C to have exactly two resolutions for experiments. Specifically, for a pre-defined increment ratio k, we split and refine all segments cr with > k to k-length sub-segments, and select h (pre-defined) k-length segments to further split to 1-length sub-segments. So, the rows of S.C would consist of (n./k h) of c and hk of c for some æ. To simplify the implementation, we only use the proposed compression in the encoder, and use the vanilla computation in the decoder of encoder-decoder models. We note that our method might be applied to the decoder (more details in Appendix).
Further, we found a few layers of standard Transformer layers to pre-process tokens helps the performance. Therefore, in the initial stage of a Transformer, we segment input sequence into multiple 512-length segments. For each segment, we use vanilla computation in the first 4 layers (for base models and layers for larger models) of Transformer. Then, for the remaining layers, segments are concatenated back into one sequence and processed using our proposed compression. There no communication among any segments, so the downstream tasks cannot be solved by these first 4 transformer layers alone, and the initial stage is used just for getting a reasonable representation for the compression to operate on.
Approximation Quality of VIP-Tokens. We empirical measured the approximation quality of our VIP centric strategy compared to random strategy (the tree growth in Fig. is not guided by VIP-tokens,, but is random) and lazy strategy (each k-length segment compressed token). Pneu is the approximated representation of VIP tokens computed with compression and let P new be the ground truth representation of
Table 1: Approx quality.
Compression Finor Consolation
Rundom
0.403
Lazy
0.528
0.869
VIP cenetc
0.137
0.991
VIP tokens computed without compression. We measure the relative error (defined as |P TLE P Phea P./ (h can verify that the proposed procedure indeed improve the approximation quality of VIP-tokens.
E) and correlation coefficient between P new and Phew-- As shown in Tab. 1 we
Enlyder-Only Models. For encoder-only archi- tecture, we compare our method with RoBERTa [22] and three strong baselines: Longformer (2] Big Bird [38]. and MRA Attention 33 We
Table 2: Dev set results for encoder-only models.
Mechod
Size Length
HotpociAA Time
QUALITY Accuncy Time Accuncy
Wikitlop
RoHiKKI
base
512
19.9
35.1
44.9
2122
39.0
19.6
67.6
first pretrain a RoBERTa model using masked language modeling task, then for each method, we perform continuous pretraining from the RoBERTa checkpoint to expand the positional embeddings to 4K length and adjust model pa- rameters to adapt approximations used in effi- cient baselines and our method. We verify that our proposed method can be integrated into a pretrained Transformer with some continuous pretraining. But we note that the amount of reduction in log perplexity for our method (-0.114) during pre-training is much larger than Longformer (-0.017) and Big Bird (-0.025) from 50K steps to 250K steps. The continuous pretraining for these baselines might have saturated since only the self-attention is approximated while our method might require more pretraining to adjust the parameters for more aggressive approximation. So, we run larger scale pretraining for our method; downstream results are in Tab. 2 and Fig. 5 denoted with * We use HotpotQA B77. QuALITY 244, and WikiHop B33 to assess the language models. HotpotQA is an answer span extraction task, while QuALITY and WikiHop are multi-choice question answering tasks. We set questions and multi-choice answers (for QuALITY and WikiHop) as VIP-tokens.
RoBERTs
base
422.3
29.5
75.2
Dig Dird
buse
4K
297.9
59.5
73.2
307.0
38.5
293.3
74.5
Langfommrr
base
4K
371.0
59.9
73.6
36800
27.9
369.7
74.3
MRA Attention
base
4K
203.5
63.4
77.0
200.5
38.7
199.2
76.1
base
4K
114.6
39.6
108.0
75.9
Ous
base
4K
114.6
61.4
75.0
125.7
39.5
108.0
76.1
Ous
largo
4K
285.8 66.7 30.0 3908
41.8
394.3
79.6
As shown in Tab. we verify that our method is consistently better compared to Longformer and Big Bird. Our method obtains better accuracy in QuALITY and WikiHop compared to 4K length
8

---

Table 3: Dev set results for encoder-decoder models. The left / right values of runtime columns are the runtime for the entire model / the encoder.
Method
Size
Param
Length
WikiHlop
HorpatQA
CNNDullymal R-1
MediaSum
Runtime
EM
F1
Runtime
EM
Fi
Runtime
R2
R.L
Runzime
R-1
R-2
R.L
TS
base
223M
512
25,7/20.5
66.7
69.1
26,3/20,5
34,
44,4
40.0/20.5
43.3
20,5
40.
29,9/20.5
30.7
14,5
28.1
223M
59533/558.7
550.3/550.6
77.5
6144/549A
43.8
613.5/552.9
17.
LongT5
base
248M
4K
220.7/233.9
72.7
74.8
273.3/233.7
62.3
75.7
291.6/33499
43.3
20.6
40.5
287.3/
34.9
17.3
32.0
LGD
base
162M
4K
236 232.6/222.9
70.0
72.4
237.4/ 222.9
55.1 67.9
2/9.//21.8
43.3 20.0
40.5
-1-
Ours
base
223M
181.7/148.1
76.7
78.4
157,4
64.5
71.7
1958/1399
43.6
20.7
40.7
196.7/1402
34.8
173
31.9
T5
lage
758M
512
63.5767.0
69.1
71.4
64.1767.0
56.9
47.8
1246/66.0
43.8
20.7
40.9
124.5670
31.9
15.5
29.1
largo
738M
1758:7/1601.0
1598.1
1598.1
16048
-f-
Oars
lirge
738M
561 47460.6
80.6
387.8
81.0
638.17433.8
44.4 21.4
41.5
609774344
18.3
52.8
571441.2
1547.7/1177.1
83.2
19507/13645
448 21.5 1990.7 18.5 33.3
Method
Size
Param
Length
Qusper
QUALITY
Ardiv
SummSarcenFD
Runtime
EM
P1
Kuntime
EM
F1
Runtime
R-1
R-2
R-L
Kunzime
R-1
R-2
R-L
15
base
223M
512
/1.5
10.8
16.4
29.3/20.5
33.6
47.3
59.0/20.5
28.9
3.6
25.6
59.1 20.5
27.0
4.8
23,5
T5
base
223M
4K
608 /551.7
13.2
29.1
596.3/5511
34,7
43.4
645.4/ 615.4/599.1
44.4
18.4
39.9
647.9/551.
31.5
6.8
27.6
T5
base
265M
16K
/6285/1421..
16.2
33,4
1633.1 1449.7
35.8
48.5
1699.7
13700
48.5
21.7
43.7
1763.4/
1427.8
33.1
7,3
28.5
base
162M
1055.8 923.6
47.8
Ours
buse
223M
16K
538.3/391.
16.0 30.8
557.17419.2
36.5
48.7
672.8/3992 48.5
21.4
43.9
670.57 390.9
33.1
7.3
28.6
large
738M
512
101.9/66.4
11.3
17.0
95.1
35.3
49.0
182.2/67.1
30.5
9.1
27.1
180.9/66.5
28.3
4,9
24.9
T5
large
738M
4K
-/-
1760.5 1996-
3788
50.5
1901.5/1900 1/18888
46.0
19.4
4144
-/-
Ours
largo
735M
16K
16796711220.
163
33.7
1753.67 1210.7
40.3
52.5
19591/111110
49.5
22.2
44.7
1957.17
1109
34.3
7.6
29.6
Ours
36
3B
168
6165.47 4637.3 19.0 28.2 63988
4962.7 45.2 5600 20763744422 49.8 22,4 45.0 7641.5 46313
34.7
7.8 30.1
Method
Size
Param
Length
ContraiNLi
NarativeA
Gov-eparr
QMSum
Runtime
EM
P1
Runtime
EM
Fi
Runtime
R-1
R.2 R.L.
Runzime
R-1
R:2
R.L
TS
base
223M
512
24.0/ 20.5
73.5
73.5
26.5.20..5
2.0
11.3
/
40.5
14.8 38.2
43.5/20.5
30.2
8.0
26.5
223M
575.0/551.6
86.8
503.4/547
547.6
13.3
655.1/551.5
54.0
551.2/551.5
27.4
LongT5
base
245M
16K
1564.2 L462.5
85.1
85.1
1541.7/ 1370.2
52
15.6
1726.4
1387.7
55.8
21.9
53.2
1721.4/
1450.7
35.7
11.7
31.4
Ours
base
223M
16K
484.2/393.1
87.0
87.0
518.2 394,4
5.0
15.8
6740//99.
55.2
27.1
52.6
623.17
31,8
8.8
27.9
T5
large
738M
512
76.1
74.3
74.3
-1-
1809766.00
43.3
16.2
41,1
136,4/67.1
31.7
8.1
27.6
T5
large
738M
4K
17024/1601.
87.2
87.2
-7-
-/-
-f-
large
738M
14406/11226
1551/7/1339
18.7
175557
56.3
18164/111346
30/7
36
38502/4665.9
88.5
475594746994
8.2 21.2 7744277
56.9
28.5
54.3
71467/46556
10.9
31.1
RoBERTa model, but it a bit worse than 4k length RoBERTa model on HotporQA. More pretraining helps close the gap. We also use WikiHop to experiment with method specific hyperparameters (such as block size in Big Bird, window size in Longformer, and compression size r in our method). As shown in Fig. takeaway is that our method has a much better runtime efficiency than baselines that have the same sequence length without sacrificing its model performance. Further, we note that our method can be scaled to larger models for accuracy improvement.
our runtime efficiency frontier is consistently better than the baselines. The key
Encoder-Decoder Models. We compare our method with T5 LongT5 [1). and LED (2). We use the public pre- trained checkpoints for baselines. The pretrained models for our method are obtained by doing continuous pretraining from the public T5 checkpoints using T5's pretraining task 22
X
X
RoBERTa
3
X Big
23
X
Longfarmer
Ours
Curs*
27. We note that LED-base has 6 encoder/decoder layers compared to 12 encoder/decoder layers in base models of other methods, its accuracy is usually lower. So, LED evaluated in limited tasks. We use HotpotQA (37). WikiHop
Runtime (ms)
Figure 5: Model runtime vs Wiki-
Hop dev accuracy when using different model specific hyperparameters
33.. CNN/Dailymail (2), MediaSum 443, Arxiv 7 and
GovReport [1S]. SummScreenFDD [5], QMSum 42
Nar-
rativeQA 19), Qasper 19. QuALITY 24). ContractNLI (21 from SCROLLS benchmark [30] to assess the language models. For question answering tasks, set questions and multi-choice answers (for QuALITY and WikiHop) as VIP-tokens in our method. For query-based summarization, such as QMSum, we use the query as VIP-tokens in our method. For general summartization tasks, we prepend a "summarize:" in each instance and use it as VIP-tokens in our method. Our method achieves matching or better performance in most tasks compared to T5, LongTS, and LED with much higher efficiency (see Tab. 3). Further, the performance monotonically increases with the model size, so our method can scale larger models.
Scaling to Longer Sequences. The prior experiments limit the sequence length to at most 4K or 16K since the basclines can only be scaled up these lengths. However, our method can be scaled
9

---

to much longer sequences. We note that Narrative [9] is an ideal testbed as shown in dataset statisties in Appendix. The results are shown Tab. 4 The left middle/ right values of runtime column are for the entire model / the encoder / the last 8 layers (out of 12 layers) that uses our compression. The performance monotonically increases as sequence length increases. We note that for sequence length 64K, the performance of model with k = 64 is lower than the model with A = 16. We suspect that since the results are finetuned from the same model that is pretrained with A = 16, the large gap between the two different k's may have negative impact on finetuning performance. Nevertheless, the performance is still higher than 32K length models.
Why focus on 4K 128K lengths? We believe that the computation required by standard Transformers for pro- cessing shorter sequences is not an efficiency bottleneck. As a result, we do not profile the performance of our method for smaller length sequences, since the standard Transformers are sufficiently fast in this case. Further, while our model can be applied to shorter sequences, we suspect that for shorter sequences, there may be less ir- relevant information for VIP-tokens. So compressing the irrelevant information will not offer a meaningful speed up. This is limitation as the compression works better when there is more compressible information. We have only pushed the sequence lengths to 128K since this length was sufficient to cover a majority of sequence lengths encountered in long sequence tasks (for example, our model is able to process an entire book at once).
Table 4: Dev results of Narrative on base model when scaling sequence length from 16K to 128K.
Langth
Rumtime (ms)
k
h
EM
Fl
16K
518.2 394,4/ 162.4
16
90
59
16.6
32K
(00s8/671.//111 212.6
32
55
6.6
17.5
32K
10279/7510/ 298.0
17.5
64K
/
64K
0244.8/1574.22 609.4
16
90
755
19.3
128K
6267.//125.99 1902.2
90
19.6
5 Limitations
Our method assumes that in many tasks, a subset of tokens are disproportionately responsible for the model prediction, the remaining non- non-VIP ViP---ttt may play a role but are less critical. Our method excels specifically on such tasks by selectively locating relevant information in the sequence for given VIP-tokens. As the experiments show, this choice is effective in many cases but this behavior is not universal. Occasionally, an embedding pre-computed which must then serve multiple tasks concurrently, e.g., both text retrieval and natural language inference. In this case, if we do not know the tasks beforehand, VIP-token selection cannot be meaningfully performed. Further, VIP-token selection requires some understanding of the tasks. However, we believe that a reasonable selection can be made with some generic knowledge for most tasks or use cases. Please see Appendix for VIP-token selection guidelines.
To reduce the complexity of our implementation, the method is currently setup for the encoder module of the Transformer that assumes full access to the entire sequence. The proposed compression might be extended to approximate the computation the decoder, but needs more implementation work, so we leave it future work. Consequently, the current implementation is less useful for decoder-only models (but in the appendix, we discuss some strategies).
6 Conclusions
We propose a VIP-token centric sequence compression method to compress/decompress the in- put/output sequences of Transformer layers thereby reducing the complexity dependency on the sequence length n without sacrificing the model accuracy. Our empirical evaluation shows that our method can be directly incorporated into existing pretrained models with some additional training. Also, it often has much higher efficiency compared to baselines with the same sequence length while offering better or competitive model accuracy. For future work, we believe that extending our method to the decoder of the encoder-decoder and decoder-only models will further boost the efficiency of Transformers while maintaining similar model performance.
Zeng and Singh were supported in part by funding from the Vilas Board of Trustecs and UW-Madison Office of the Vice Chancellor for Research and Graduate Education.
Acknowledgments.
10

---

References
[1] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton, Layer normalization. arXiv preprint arXiv:160..06450, 2016.
[2] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint 55X1v:2004.05/50, 2020.
[3] Aydar Bulatov, Yuri Kuratov, and Mikhail Burtsev. Recurrent memory transformer, 2022.
[4] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European Conference on Computer Vision, pages 13-229. Springer, 2020.
[5] Mingda Chen, Zewei Chu, Sam Wiseman, and Kevin Gimpel. SummScreen: dataset for abstractive screenplay summarization. In Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 8602-8615, Dublin, Ireland, May 2022. Association for Computational Linguistics.
[6] 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 performers. In International Conference on Learning Representations (ICLR), 2021.
[7] Arman Cohan, Franck Demonccurt, Doo Soon Kim, Trung Bui, Seokhwan Kim, Walter Chang. and Nazli Goharian. A discourse- aware attention model for abstractive summarization of long documents. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume 2 (Short Pupers), 2018.
[8] Zihang Dai, Guokun Lai, Yiming Yang, and Quoc Le. traneertransformme: Filtering out sequen- tial redundancy for efficient language processing. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4271 -2822. Curran Associates, Inc., 2020.
[9] Pradeep Dasigi, Kyle Lo, Iz Beltagy, Arman Cohan, Noah A. Smith, and Matt Gardner. A dataset of iiformattion-seeiiin questions and answers anchored in research papers. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4599-4610, Online, June 2021. Association for Computational Linguistics.
[10] Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), 2019.
(11) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations (ICLR), 2021.
[12) Alexander Fabbri, Irene Li, Tianwei She, Suyi Li, and Dragomir Radev. Multi-news: large- scale multi-document summarization dataset and abstractive hierarchical model. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1074-1084, Florence, Italy, July 2019, Association for Computational Linguistics.
[13] Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. The Pile: An 800gb dataset of diverse text for language modeling. arXiv preprint 1-Xiv:2101.0002: 2020.
[14] Mandy Guo, Joshua Ainslie, David Uthus, Santiago Ontanon, Jianmo Ni, Yun-Hsuan Sung, and Yinfei Yang. LongT5: Efficient text-to-text transformer for long sequences. In Findings of the Association for Computational Linguistics: NAACL 2022, pages 724-736, Seattle, United States, July 2022. Association for Computational Linguistics.

---

[15] Luyang Huang, Shuyang Cao, Nikolaus Parulian, Heng Ji, and Lu Wang. Efficient attentions for long document summarization. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1419-1436, Online, June 2021. Association for Computational Linguistics.
[16] Xin Huang, Ashish Khetan, Rene Bidart, and Zohar Karnin. Brramid-BER11 Reducing com- plexity via successive core-set based token selection. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 7798-8817, Dublin, Ireland, May 2022. Association for Computational Linguisties.
[17] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations (ICLR), 2020.
[18] Bryan Klimt and Yiming Yang. The enron corpus: A new dataset for email classification research. In Proceedings of the 15th European Conference on Machine Learning, ECML' '04 page 217-226, Berlin, Heidelberg, 2004. Springer-Verlag.
[19] Tomáš Kočiský, Jonathan Schwarz, Phil Blunsom, Chris Dyer, Karl Moritz Hermann, Gá- bor Melis, and Edward Grefenstette. The NarrativeQA reading comprehension challenge. Transactions of the Association for Computational Linguistics, 6:3 17-32, 2018.
[20] Philipp Koehn. Europarl: A parallel corpus for statistical machine translation. In Proceedings of Machine Translation Summit X: Papers, pages 79-86, Phuket, Thailand, September 13-15
2005.
[21] Yuta Koreeda and Christopher Manning. ContractNLI: A dataset for document-level natural language inference for contracts. In Findings of the Association for Computational Linguis- tics: EMNLP 2021, pages 1907-1919, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
[22] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arxiv: 1692, 2019.
[23] Piotr Nawrot, Jan Chorowski, Adrian Lańcucki, and Edoardo M. Ponti. Efficient transformers with dynamic token pooling, 2022.
[24] Richard Yuanzhe Pang, Alicia Parrish, Nitish Joshi, Nikita Nangia, Jason Phang, Angelica Chen, Vishakh Padmakumar, Johnny Ma, Jana Thompson, He He, and Samuel Bowman. QuALITY: Question answering with long input texts, yes! In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 5336-5358, Seattle, United States, July 2022. Association for Computational Linguistics.
[25] Hao Peng. Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. In International Conference on Learning Representations (ICLR), 2021.
[26] Jack W. Rae, Anna Potapenko, Siddhant M. Jayakumar, Chloe Hillier, and Timothy P. Lillicrap. Compressive transformers for long-range sequence modelling. In International Conference on Learning Representatiins, 2020.
[27] 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 unified text-to-text transformer. Journal of Machine Learning Research, 21(140): 2020.
[28) David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. In International Conference on Learning Representations, 2019.
[29] Abigail See, Peter Liu, and Christopher D. Manning. Get to the point: Summarization with pointer-generator networks. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1073-1083, Vancouver, Canada, July 2017. Association for Computational Linguistics.
12

---

[30] Uri Shaham, Elad Segal, Maor Ivgi, Avia Efrat, Ori Yoran, Adi Haviv, Ankit Gupta, Wenhan Xiong, Mor Geva, Jonathan Berant, and Omer Levy. SCROLLS: Standardized comparison over long language sequences. In EMNLP, 2022.
[31] 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 transformers, In International Conference on Learning Representations (ICLR), 2021.
[32] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[33] Johannes Welbl, Pontus Stenetorp, and Sebastian Riedel. Constructing datasets for multi-hop reading comprehension across documents. Transactions of the Association for Computational Linguistics, 6:287-302, 2018.
[34] Yuhuai Wu, Markus Norman Rabe, DeLesley Hutchins, and Christian Szegedy. Memorizing transformers. In International Conference on Learning Representations, 2022.
[35] Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer. A nyström-based algorithm for approximating self-attention. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[36] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoe V Le. Xlnet: Generalized autoregressive pretraining for language understanding. In H. Wallach, H. Larochelle. A. Beygelzimer, d'Alché-Buce E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[37] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhut- dinov, and Christopher Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Conference Empirical Methods in Natural Language Processing (EMNLP), 2018.
[38] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[39] Zhanpeng Zeng, Sourav Pal, Jeffery Kline, Glenn M Fung, and Vikas Singh. Multi resolution analysis (MRA) for upproximate self attentinn. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari. Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th Inter- national Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 35955-25972. PMLR, 17-23 Jul 2022.
[40] Zhanpeng Zeng, Yunyang Xiong, Sathya Ravi, Shailesh Acharya, Glenn M Fung, and Vikas Singh. You only sample (almost) once: Linear cost self-attention via berouulii sampling. In International Conference on Machine Learning (ICMI.,, 2021.
[41] Sixiao Zheng, Jiachen Lu, Hengshuang Zhao, Xiatian Zhu, Zekun Luo, Yabiao Wang, Yanwei Fu, Jianfeng Feng, Tao Xiang. Philip HS Torr, al. Rethinking semantic segmentation from aequence-to-sequeece perspective with transformers. arXiv preprint arXiv:2012. 15840, 2020.
[42] Ming Zhong, Da Yin. Tao Yu, Ahmad Zaidi, Mutethia Mutuma, Rahul Jha, Ahmed Hassan Awadallah, Asli Celikyilmaz, Yang Liu, Xipeng Qiu, and Dragomir Radev. QMSum: A new benchmark for query-based
multi-domain meeting summarization. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 5905-5921, Online, June 2021. Association for Computational Linguistics.
[43] Chenguang Zhu, Yang Liu, Jie Mei, and Michael Zeng. Mediasum: A large-scale media interview dataset for dialogue summarization. arXiv preprint 103.064100 2021.
13

---

7 Appendix
7.1 Definition of Notations
Table 5: Major notations used
Notation Description
bumber of layers of Transforme model
n
number tokens of an imput sequence
model embedding dimension
number of VIP-tokens
The
number VIP/remaining tokens, so By + ne
length of compressed sequence
multi-head attention taking three inputs query/key'value embeddings two-layer food-forward network
7(-)
function representing heavy computation Transformer layer
embedding matrix representing a input soquence
embedding representing the VIP-tokens embedding matrix represeuting the nee-V VIP/remaaning tokens
updated embedding matrix input sequence, oulput TTransfomer layer
P
updated embeddding matris representing the VIP tokens
Crcc
updated embedding matrix representing non-VIP/reme Vi-remmaiinnn
compression matrix
compression submatrix
VIPhemminiig
ST
decompression matrix
S!
docompression submatrix for the non- ViP/remaiiing tokens
approximation. represents
embeddings being averaged
location of s length segment with the ariginal sequence
increment ratio of resolution, E {1, k, A k ..... m2]
number k-longth segments split number of e-length segments are split into shorter aub-sogments, used in Appendix discussion
I-length sub-segments, used experiments
of components b that is constructed via Alg. I the elements the of S. components used for I.D wavelet transform of scaling s and translation. ir
local avergge 2-th s-length segment sequence C
(Cnew) 1
local average of 2-th e-longth segment of soquence Cnew
T(-)
data structure for storing the input sequence C Cnew state stored in (C)) detined as Ae; == cfs/2] c; state stored in T(C defined as A (c )2 = (cnew ) ///221 (Enew)
Ac
A [
entryfrow input vectoelmatrix
(6.t)-th entry of the input matrix
We provide table 5 of notations that used for more than so that the readers refer to their definition easily.
7.2 Details Multi-Resolution Compression
We describe the omitted technical details of a modified formulation of (39 to construct S&C and corresponding S. satisfying good approximation of
exp(PC s. ~ exp(PC
(19)
Before diving into the technical details of constructing S.. we introduce some notations and tools that will be used later. We use [:] refer the i-th entry/row of the input vector/matrix and [:)k to refer the (i.j))th entry of the input matrix. BOLD uppercase letters denote matrices, bold lower case letters denote vectors, and regular lower case letters denote scalars. Let v; be a vector, when we write a matrix of form
V1
(20)
we treat V, as column of the matrix. When we write a matrix of form
Vi
(21)
V
treat v, row of the matrix.
14

---

7.2.1 Basic Problem Setup
Let by E "h be multi-resolution component de- fined as
5
0.010
if sr -siis otherwise
b
(22)
[b;]]
0.005
SX
S
for [K9, Ah,, k2, ... ) assuming n.e is power of (we assume k = for simiplicity). Here, 8 and x represent the scaling and translation (similar to the concepts in wavelet basis) the component, respectively. Fig. is the visualization of b;
0.000
0
100
200
300
400
500
Figure 6: Visualization of bg for some scaling and translation æ. The axis for different plots are not the same.
Then, any signal R. can represented as linear combination of b
Σ b 9,3
(23)
where og are the coefficients for the linear combination. For a signal with multi-resolution structure (that is, signal has high frequency in some regions and has low frequency in other regions), we can find approximation f that can be expressed as a sparse linear combination where most coefficients are zeros, as shown Fig. 7
p~f- = Σ b
(24)
b2E
We denote I the set of major components by corresponding to the large coefficients, that is, J : (b: le being large]. Since the set all possible by is an over-complete dictionary, there multiple possible linear combinations. To reduce the search space of the best set J, place mild restriction on the set J:
Σ S bIET
#
Vi
(..b Vb by J. by
(25)
The conditions state that each entry of signal is included the support region of exactly one component in J. With these tools, we will first describe the approximation when J is given, then discuss how approximation connects set J to our target S, and S.C. Finally, we will discuss how to construct this J.
0.5
signal
0.0
MM
g
approx
100
200
300
400
500
X
Figure 7: An example of approximating an ID signal using truncated wavelet transform with components defined (22). uses set J of size 79 represent signal in R512
7.2.2 Plugging Our Problem into the Setup
recent result shows that the self-attention matrix exp XX has the multi-resolution structure discussed above [3). Since exp(PC)) is a sub-suuuee mabrix exp(XXX) ). we conjecture that the multi- resolution structure also holds in exp(PCT), As result, we can find a sparse combination of b to represent rows of P
Claim 7.1. Given the set I satisfying restriction 25
we can define an approximation of the i-th row of PPC similar (24) as illustrated in Fig.
eexp(PCT)]
Σ
b
(26)
b EJ
15

---

where Cg is the optimal solution that minimizes
[exp(PC )1, - [exp(PCT) ( ".1.
(27)
Then, the approximation can be written as:
exp((PCT) 1,, ((oxp(PCC)) bg)
(28)
where by E is the component that is supported on j (a.k.a [be], * and there exactly one
by E satisfy this condition due to restriction
Proof. If I is given, let B E
x be matrix whose columns are elements bg J and let E [ be vector whose entries are the corresponding c::
B
b 81 21
b
b
(29)
tg 12
21
then the approximation can be expressed as
(xxp(PCT)]]
Σ
bb;
Bc
(30)
bge
If we solve for
c: = arg min [[xp - BBl
(31)
then
c= (B B B) B
[exp(P (PP())) )]
(32)
Due to the restriction 25
the columns of B orthogonal, B B is diagonal matrix:
1/s1
1/32
B
(33)
1/8
We also write down B (exp(PCT)),
([exp(PC } b [[exp(PC b
B T (exp(PCC)),
(34)
[[exp(PCC))
b
Putting everything together, we have
(exp(PCT) [exp(P
b2)
b
Bc [s
81J |
(35)
([exp(PC bx
We note that sb;, simply re-scale the entry of b such that any us consider j-th entry of Bc. Due to the restriction (25), we have exactly one by E J whose support region contains j, the j-th of the first matrix the right hand side of 35 contains exactly 1 and the remaining entries are 0. Therefore, we have
entry becomes 1. Then, let
[ex ]].,
[Bcl, = ([exp(PPC )], bz)
(36)
where by E I is the component that is supported on j. which concludes our proof.
16

---

7.2.3 Efficient Approximation
We note that computing (8 for all j would require access to the entire [exp(PCT)]; We exploit
the same strategy as described in [39], so the exponential of inner product used as an approximation to inner product of exponential.
exp((CC)) f.
exp(([PCC)
(37)
We note that ([PC"] bg) is the local average of the support region of by which is also the z-th s-length segment of sequence [PC
(PCC li,
Σ
[PC
(38)
is
by b=
#0
By using some arithmetic manipulations, (37) can be efficiently computed
|1 bx)) exp(([PC))
exp(
JPC'li) = =xxpp) Σ (P4.
1b #0
(b;),
(39)
exp(([P);
Σ
(cl,)) exp((
1b
where c is defined the main text:
Σ
[C,, b
(40)
We note that cg is the local average of the æ-th s-length segment of sequence C. The c can be efficiently computed via
C
2
+
2z
C = cC
(41)
Claim 7.2, Given the set I satisfying restriction bj E
25
let S. be be malrix whose rows are elements
b
S81
boz
S.
D
$2
(42)
[
$15
Then,
exp(PC S DS. cxp(PCT)
(43)
where cxp(PCTT) is defined as (37
Proof. Consider i-th row of exp((CC ST).
[exp(P(S.C)])], = (PP[
exp([P), [
))1
(44)
[exp
exp( cr }
Then, we have
s1 s1b2
(exp(P(S.CC) DS.), (exp(([),)))) (())
exp
))
(45)
91 Den
$15
We note that sb simply re-scales the entry of by such that any non-zero entry becomes 1. Then, let us consider j-th entry of [exp(PC s DS.., Due to the restriction 25)) have exactly one
17

---

Dy E J whose support region contains j. so the j-th column of the second matrix in the right hand side of (45) contains exactly and the remaining entries are Therefore, we have
(exp(P(S.C) "DD.) exp(([P), c))) exp(([ Is. b")) = [eep((PC)
(46)
where by I is the component that is supported j. The second equality is based on (39
Claim 7.3. Sc and D are defined Claim 7.2 the pseudo inverse of Se is simply S S D, so each row of St and St contain exactly 1 (so the number of nonzero entries of S and S are n. and n respectively).
Proof. Since each row of Se is some bj E J, due to the restriction
25 for i 1+1 j.
1
[S.S. D 1, (S.)), [DS)) (b 8, (
8;
8:
(47)
[S.S D) ij ([S.). ( (b%) b.)
s,0=0 =0
As result, S.S. I. Further, S. DS, is symmetric matrix. So, all Moore-Penrose conditions are verified. S
From the restriction (25) we have every column of $e contains exactly a non-zero entry. Also,
!
= =S D = b s2b
$15 bل
(48)
Since the non-zero entry of by is simply by definition, sb simply re-scales the entry of by such that any non-zero entry becomes 1. As result, each row of S has exactly 1. Also, by the relation between S and S.:
Inpxng Xxp
0 S.
st = I x 0
S
(49)
s
each row of S has exactly 1.
At the end, the approximation
exp PCC -
DS ~ )
exp(PCT)
(50)
does look exactly as T9). but we can insert a simple diagonal matrix D the formulation (T9 and make the whole thing work.
7.2.4 How to Construct I for Se and S.C?
The derivation far assume access to J, but in practice, we have no knowledge of J and need to construct J that leads to good approximation. With the approximation scheme in place, we can now analyze the approximation error, which will be leveraged later to find reasonable set of components J. The approximation error of i-th row of exp(PC
can be expressed as
& [exp(PCT)) (exp(PCT) -(xxp)(PCT))
(exp((PC)) (exp(PCT)
Σ Σ
- (xp(((CT]] b;)))
beed [b21,
(51)
Σ exp((PCT) ((,bg))
(exp([PCT] (
(PPC by)) 1)2
BEET
(B2)
Σ exp(((P),, c()
Σ (exp(([P), (CI,) - -[P],, 1)²
BEEJ
(B
= Σ
exp (P),(()),,))) c()
Σ
(exp(())), [Cl, - ct)) - 1)2
BIEJ
(B2)
18

---

Algorithm Constructing J
Input: VIP-tokens P and c, for all and
Input: hg number of s-length segments refine for each E {2, ... ,
Initialize empty T
Compute 14 (53) and add be (22) to J (compute root node)
for ne,2,, ......... ,2 do
Pop hts elements by with the largest μم
53
(select nodes with higher attention scores)
for each by do
5/2 Compute 122-11 M2x
53 and add b 8/2
2-
22
8/2
22
J (split selected nodes)
end for Output: J
The second equality and fourth equality are due to (25) and 39
The approximation error is governed by two components multiply together: attention score between [P], and the local average ca of the
r-th s-length segment of sequence C and the inner product of [P], with the amount of deviation of [Cl, from its local average -
When 1, the deviation is simply zero:
[C],-
(52)
It is reasonable to assume that the deviation [Cl, c is smaller if s is smaller. Therefore, this actually suggests a simple heuristic for selecting J: when exp( ([)) is large, we should approximate the r-th s-length segment of C with higher resolution (by splitting the segment to shorter sub-segna se-meeegmets and using finer approximation). This heuristic describes the selection criteria for one row of exp(PC' which corresponds to single VIP-token, for multiple rows of cxp(PCT) (for multiple VIP-tokens), we simply use
expl exp((()),
(53)
as selection criteria since J is shared by all VIP-tokens.
The construction of J is described in Alg. [ This algorithm describes the same procedure as the Figure 3 in the main text. The b J are the rows of S., and the corresponding c (40) are the rows of S.C. The budgets h22 h4. ,,, required by Alg. iis used determine the number of components at each resolution that will added J. Specifically, there are 2h2 h, number of components by for a f 1 based simple calculations. We can choose budgets such that the final size of J r - ny to make the length of compressed sequence to be
7.2.5 How Good is This Approximation?
At high level, the compression S, performs more compression on tokens that are not relevant to the VIP-tokens and less compression to tokens that are important to the VIP-tokens. We will discuss in more details. Since each row of St contain exactly a as stated in Claim 7.3 St can commute with
3, so in summary, we can write the approximation the computation Transformer layer as
(P,S SX) cxP(PP S DD.C
SX, sX C, SX) = +x SP Sx)
DS.C
(54)
Poew Cnew
P C
=
((S CS. SX S(S.C) Sta Sx SX)
+
Note that D is added discussed in 50)
There are four main approximation components (purple) in (54). Taking the fact that DS - (St) T
all of these approximations are row or column space multi-resolution approximations governed by S. matrix. High attention weight implies higher dependency, and the procedure in Alg. D refines regions with large attention weights with higher resolutions. Therefore, the token embedding in C that have higher dependency to are better approximated. The output Paew is well approximated by design since the approximation preserves the higher frequency components of the subset of rows of
19

---

C' that has high impact on the output P Rew- Further, the output in Cnew corresponding to the subset of rows of C that have higher dependency with the VIP-tokens will have better approximation than the remaining rows of C. This property addresses the issue that some tokens with unknown locations are also relevant to the final prediction of Transformer in some tasks. For example, in question answering tasks, candidate answers are usually expected to have large dependency with question tokens (VIP-tokens), so they are approximated well as well. This approximation property is exactly what we need.
7.2.6 Relation to [39] that Inspires Multi Multi-Resolution Compression
Our work and [39 can be viewed as operating at slightly different levels of abstractions. While [39] tries to approximate self-attention computation efficiently, our paper proposes general framework for performing a VIP-token centric compression on the sequence to efficiently handle extremely long sequences (the self-attention module remains completely unchanged). Our VIP-token centric compression involves a number of steps described in the main text. But one of the key steps involves constructing compression matrix S. which has some desirable properties, namely satisfying (19) which we elaborate further below.
Note that for equation (9)) we need a matrix S. such that the approximated attention matrix involving P and is similar to the true attention matrix involving P and C. This is precisely where the general idea of [39] can be used. But the formulation in [39] cannot be applied directly in its original form since it cannot give us S.. Why? One reason is that the formulation in [39] cannot be written as
matrix form similar to equation (19) This may be reason why 33 has to use custom CUDA kernels in their implementation. Nonetheless, the properties of [39] are useful. So we derive the analogous form but for ID instead: this ID case is expressed as applying matrix (this is the S. are looking for) to the signal C.
One bonus of this modification is that it also removes the need for custom CUDA kernels. At a high level, (39 offers multi-resolution view of the self-attention matrices, and our modified version is best thought of as similar multi-resolution view of the sequence itself. But we can also substitute in a different means obtaining S. (which could simply be a sketching matrix). Finally, we note that a naive implementation of the resulting modification still requires ((n,d) cost due to the computation of c for all possible scaling s and translation æ. There a similar cost in [39 (second paragraph in section 4.4 in (39)). The data structure we propose reduces this cost.
7.3 Details of Proposed Data Structure
In section, we describe some omitted technical details of the proposed data structure T(-)
7.3.1 Why (Cnew)) ct (Creew) -c (Cneww) cj irs. le
cj
ct
c2 ?
Claim 7.4. Given the set I satisfying restriction 25 if' E J, then (Cnew) )e cg (Cnew v for all by satisfying the support of by is contained in the support of by (the x'tth s' lengh segment of C is a sub-segment of the x-th s-length segment C).
Proof. To simplify the notations bit, without loss of generality, we assume x = 1. Then, for S 8, consider (::ew)):
(Cnew)) [Cnew]; = (S, S.C) S.
[C], (55)
= [St] (l), + S.C) + [S!], S.,C + +
By Claim 7.3
S S. D and i-th row of S contains exactly a 1. The column that contains in the i-th row of S is exactly sby since i is contained in the support of exactly one components in J due to the restriction (25). Denote this column index as j, then
(Cnew) } = [8(a(S.C, SX, SX) + S,C)), + C,,S SX,, + +
(56)
Note that this holds for all S As result, for i, 8,
(Cnew)) }} cf (8 SX + S,C)), (oss,C,XX = (Cnew)) -ch (57)
20

---

Algorithm 2 Computation of one Transformer layer with T(C)
Input:
VIP-tokens P and data structure T(C)
Use Algo. to construct J but use (63) to retrieve c, from T(C)
Construct Se, S&C associated with J using Claim 7.2
Compute
P Pnew Crew
[la(S.
+
(62)
Set T(Cnew) x-() for + 2-222,,,--nd
for by E E do
Locate row location b,; in Sc, refer the index as
Compute (Cnew) = Crewly
Mark A(Cnew) 3 dirty
end
for dirty ((Cnew) )o do
Compute (Cnew [a/2]] and update (Cnnew)
22
Mark A ((Cnew) [x/2]] dirty
end for
end for
Update (Crew)) )
Output: VIP-tokens P Prew and data structure T(Cnew)
Then,
1
1
(Cnew) c/s/2]
2 (Cnew (ommm))2//2211 2/1/2/-1
+ (Cnom)2 2/1/21 2
- 2
2 ((Cnew 1/13/21-11 - 0211/21-1) + 2 ((Cnew)211/21-1
(Crnew (Cnnew)211/2) -2/122)
(58)
= (Cnew (0ne2))/11/211
C2f1/21-1
The rest follows from induction.
7.3.2
How do get (Cnew)) (Cnew))) (Cnew) (Cnew) ifS.C= [c] ca
ct)
Claim 7.5, We have
S.Cnew BlaaBal,,,,,,S.... + SX + S.C.
(59)
And the updated representation (Cnew) ) of the corresponding c (a row of S.C) is the corresponding
row of S.C. Cnew:
Proof. By definition,
C
(60)
Then.
S. C.Ce = -t8_:///.........5---------58850
S.C
(61)
= B(a(S. - SSC
Since the S, is the same for S.C. Cnew and S. C, the second statement follows.
7.3.3 Algorithm for Making T(C) into T(Cnew)
In this section, describe the exact algorithm update T(C) into T(Cnew)) The pseudo code is described in Alg. 2 where Cº is computed via
(63) We use the term "dirty" in Alg. to indicate the node needs to be handled due to node updates. This term commonly used computer cache implementations indicate that the data of specific location has been updated and needs to be accounted for.
C Ac = c Ac AC
21

---

7.4
Complexity Analysis
In this section, we will discuss the detailed complexity analysis of our proposed method. The overall complexity of our proposed method is Olrdd + Ir + Ir log(n.)d + Irn,d + nd) when using the proposed efficient data structure.
7.4.1 Preparing Input Sequence to T(C): ((nd)
At the first layer, we need to permute the rows of X into C] which takes ((nd) cost. Then, we process C into TCC). This requires (1) computing c defined in (4T). c [Clg, so no compute is needed. With all c given, computing all ci takes O(n.//2). With all c given, computing all c² takes (n)d/44... So, the cost is
(64) Then (2) computing Act for all 8 and x. Computing each Ac² takes ((d) when given c and of The amount of cost is the same the number of nodes in the tree T(C), the cost (nrdd). Note that nee < n. so the overall complexity of the above operations is (nd).
O(n
n.d/+++/++... n.dd//2
d) O(ned).
2
7.4.2 Constructing J,S,, S.C: O(r log(ne)d Irnpd)
We can analyze the complexity of constructing I using Algo. There is only one possible p²* Then for each s, there are 2h, number of μzz being computed since there are components b for each b.. As result, need to compute O + Σ, 2ha) number of u²² When c² is given, the cost of computing a 1t is (Upd), so the overall cost of constructing I is O(11 - Σ. mndd)
Further, at each s, the size of J is increased by h, since h, segments split into 2h, sub segmeesssnts... so the size of I is OiE h.). Since S. E (r("==,)>"" and [T] Orr npp) O hg). We use ((r) for simplicity instead of O(r np). As result, the overall cost of constructing J is (rn..d).
np as discussed in $7.2.4
The above cost assumes c²2 is given. If compute all possible / using 41 the cost will be ((n,d) as analyzed in $7.4.1 However, we employ the proposed data structure, each e/2 can be retrieved in at most OTlog(n.)d by recursively computing (63). Since need retrieve O(1+ Σ, 2h.) (r)) number of cg. the complexity of computing necessary c is Or log(n.)d).
As result, the complexity of constructing J is Orn,d + log(n.)d) at each layer. When summing the cost over all layers, the complexity is OIrnnd + Ir log(n.))),
By Claim 7.2 the rows of Se and S.C are simply the bü E J and the corresponding c which are already computed during the construction of J, so we essentially can get these S. and S.C for free.
7.4.3 Feeding Compressed Sequence into a Transformer Layer: Olrd + (r2d)
At each layer, we need to compute
Preur [ (( (ia(P.SX.R SX + +P Cee
SX. S,C) + a(S.C, + S.C
(65)
for updating T(C). This the part of Transformer layer that requires heavy computation. It can be verified that the complexity of a Transformer layer is O(nd² + n²2d) for a input sequence of length n. Now a compressed sequence of length r fed into a Transformer layer, the cost is simply Olrd² + rdd). We note that there is an additional re-scaling to plug D into exp(PC S. DS. during multi-head attention computation discussed in 50 However, the additional cost of applying D is (rd)) which does not change the complexity. When summing the cost of all layers, the overall complexity is (lrd + I))
7.4.4 Updating T(C) into T(Cnew): (Ird)
is computed, we need to change T(C) into T(Cnew). The cost of change T(C) into T(C is O(d)) as analyzed in the main text. For more specific analysis, us take look the first three iterations:
Once 165
22

---

(1) At the first iteration, there are ((2h2) number of (Cnew)n to be computed at the first inner for loop, and there are (2h2) number of ((Cneo)) ) to be updated in the second inner for loop. Additional ((h2) number of ((Cnew) [a/2]] [a/2] are masked dirty.
(2) At the second iteration, there are ((2ha) number of (Cnew) ) to be computed at the first inner for loop, and there (2hh h22 number of A A(Cnew)
2
l to be updated in the second
inner for loop. The second term due to the dirty A (Cnew)) [a/2] from the first iteration.
Additional (ha + ) number of (Cnew) ( are masked dirty.
(3) At the third iteration, there ((2bg) number of (Cnew)) )a to be computed the first inner for loop, and there O(2hg h4 ha number of A ((Cnew) to be updated in the second inner for loop. The second and third term is due to the dirty (CCnw))( from the second masked dirty.
iteration. Additional Ohhs + h4 A2) number of A (C ( [w/2]
It becomes apparent that if we sum over the number of computes of (Cnew) ) and updates of ( ) the total number OEE, 2h, + 2 مj=1 4.) OiE h2 + E. a h₂) O(r). Since each compute and update takes (dd) cost, the overall complexity of changing T(C) into T(Cnew) is O(rd). When summing the cost of all layers, the overall complexity is (Ird)..
7.4.5 Materializing Cnew from T(Cnew) at the Last Layer: ((dd)
At the output of the last layer, we can (1) compute all (Cnew )2 ne/2 via 663 at a cost of ((2d), (2) compute (Cnew yr//4 )²=/ via 633 at cost of ((d)).. until all (Cnew)) } computed. Then, [Cnewlz = cg is materialized from (CCow)) at total cost of
(d 2d 4d +.....++ ned) O(,d).
(66)
Lastly, undoing the permutation so that [P Pamm; Cnew] are re-ordered to the original positions has complexity of O(nd). As a result, the overall complexity is ((nd).
7.4.6 Overall Complexity
In summary, the overall complexity of our method is
Olrd + dr + Ir Irlog(n.)d + Irn,d + nd)
(67)
7.5 Experiments
Table 6: Length statisties of each dataset. The values are the percentiles of number of tokens for the specific tokenizers. For T5 tokenizer, the left value of for sequence lengths of encoder input, and the right value is for sequence lengths of decoder input.
RoBEKI's QuALITY
T5 Qusper
Percentile
HotpotQA
Wikillop
Wikillop
HospotQA
QuALITY
ContructNLi
75th 95th
1535 1928
7603 8495
2204 3861
2399/6 6 4206/9
1692 /6 2129/
7029 /
7747
2991 /4
10920/71
8603/28
5061 /4
T$ SummScreenFD
Pereentile
NarrativoQA
CNN//ailymail MediaSum
Arxiv
GovReport 13304
QMSum
MultiNews
90482/
/9
13477 364
110
3032 379
95th
260533/ /
1946 / 130
5061 /64
26024 / 759
16722 / 330
23795 983
31749 / 162
6676 468
We run experiments on NVIDIA A100 GPUs. All code implemented using the standard Py PoTchh framework. No custom CUDA kernels are needed. As a result, it can be easily deployed to other platforms or MI. frameworks. We will publish all code and checkpoints necessary for reproducibility concurrently with the paper publication.
23

---

Table 7: Dev results for encoder-only models fintuning HotpotQA, QuALITY, and WikiHop.
Mathod
Length
HotporQA EM
QUALITY
WikiHop
Runtime
F1
Runtime
Accuraty
Runtime
Aucuracy
KodllKia
base
312
19.9
35.1
44.9
21.2
39.0
19.5
67.6
RoRFRTs
hase
4k
422.3
62.2
76.1
403.2
39.5
414.1
75,2
Bar
4k
297.9
307.0
253.3
langforner
hase
371.0
50.9
73.6
27.9
369.7
Ours
hase
4k
114.6
60.
74.6
1264
39.6
105.0
75.9
Ours- 1506
base
4k
114.6
00.7
74.1
1264
39.4
105.0
76.1
7.5.1 Runtime Measurement
The runtimes presented the experiment section are measured runtimes complete training step (including both forward and backward). For each method, into a 80GB A100 and measure the average latency of 10 steps. Then, the average latency is divided by the batch size get the estimated runtime for single instance. Via this procedure, seek to measure the peak efficiency of each method when the GPU is at the highest possible utilization.
the largest batch size that fit.
7.5.2 FLOPs
Some might be interested about the FLOP ef- ficiency of each method, so we provide FLOP profiling results for experiments. The auto- matic tools that we used for calculating FLOPs deepspeed's FlopsProfiler. We note that the FLOP profiling tools do not always work and may throw errors or produce incorrect results when the code contains custom CUDA kernels. The results are summarized in Tab. g and Tab. 2 x in some entries means the profiler throws errors and cannot estimate the FLOPs numbers. Also, the profiler throws errors when we just profile the encoders of encoder-decoder models, so the FLOP numbers in Tab. 9 are for the entire models. As shown the tables, our method has the lowest
Table 8: Dev accuracy and FLOPs for encoder-only models. *: some calculations NOT captured by profiler, so value is underestimated.
Mathod
Size
Langth
WikiHop GELOPs
Runtime
Accuracy
RoBERTa
512
19.6
RobERTa
base
414.1
Big Bird
base
4K
203.1
790
74.5
Longtommr
base
4K
369.7
74.3
MRA Attention
4K
199.2
697
76.1
FLOPs.
Table 9: Dev results and FLOPs for encoder-decoder models.
Methad
Size
Longth
WikiHop
Runtime
Fl
T5
512
25.7/ 30.5
120)
69.1
13
594.3/553.7
76.2
78.1
Longts
base
4K
2
948
72.7
24,8
LED
hase
4K
236.6/ 222.9
70.0
72.4
181.77
76.7
78.4
Method
Longth
ContreeNLi
GFLOPs
512
24.0
112
T5
buse
4K
579.0/ 551.
1437
86.8
86.8
LongTS
hase
16K
1664.2 1462.5
4442
85.1
85.1
Ouns
16K
164.2/393.1
1933
87.0
87.0
However, we note that FLOP numbers do not always reflect practical latency reductions. Memory bandwidth and latency (which are not captured by FLOP numbers) also play an important role in the overall latency. For example, sparse matrix multiplication (with unstructured sparsity) usually has much lower FLOP count than dense matrix multiplication. But, the latency reduction is only possible when sparsity is least 95% or more (depending on the implementation) since sparse matrix multiplication is a memory bandwidth bounded operator.
7.5.3 Pretraining
We use a filtered The Pile dataset [33 tokenizers, we want to enable the distribution of pretraining corpus aligns well with the distribution of corpus used to create the tokenizers. As a result, we use tokens per byte as proxy for alignment of distributions and filter out PubMed Central, ArXiv, Github, StackExchange. DM Mathematics (28).
all pretrainings. Since we are using public pretrained
24

---

Table 10: Dev results for encoder-decoder models on MultiNews.
Method
Size
Param
Length
MultNews
Runtime
T5
hase
223M
50.27
42.5
15.3
T5
base
223M
651.2/551.8
18.2
Lougi5
base
248M
8K
721.7/550.6
46.7
18.3
42.9
LRF
hase
162M
526.5/
46.6
17.8
42.7
377.0/224.6
46.4
18.1
lurge
738M
1808/67700
43.4
15.6
39.8
large
738M
1140.7651.5
4094.5/ 2696.0
19.1
Ubuntu IRC, EuroParl (20), YoutubeSubtitles, and Enron Emails [8] components, which have tokens byte greater than 0.3. Then, the remaining corpus of The Pile dataset is used for pretraining.
For encoder-only models, we pretrain RoBERTa for 750K steps. A batch consists of 8, 192 sequences of 512 length. The masking ratio for masked language modeling (MLM) is 15%. Then, 4K length models are continuously pre- trained from the RoBERTa checkpoints for 300k steps. The positional embeddings are extended by duplicating the pretrained 512 positional embedding multiple times. For 4K length RoBERTa, Longformer, Big Bird and MRA Attention, the batch size is 64, and the masking ratio is 15%. With 15% masking ratio, there are roughly 616 masked tokens scattering the sequences. We find that using 616 scattered masked tokens VIP tokens for 4,096 length sequences might not be indicative for VIP-token centric compression, batch size 128 for our method. The number of masked tokens per sequence is reduced, and the number of total masked token predictions remains the same during pretraining. We note that with larger batch size, the wall clock pretraining runtime for our method is still smaller than baselines. In case that anyone is interested, we also show downstream finetuning same number of tokens but fewer number of masked token predictions in Tab. and Fig. [] denoted Ours-150k. The accuracy consistent with model pretrained 300k steps. For the larger scale pretraining denoted with *, we pretrain our method for 250K steps with batch size 512 and masking ratio 7.5%.
77
Accuracy
75
Big Bird
X
Longformer
Ours
Ours 150k
Runtima (ms)
Figure 8: Model runtime WikiHop dev accuracy when using different model specific hyperparameters
masking ratio 7.5% and
method pretrained on the
For decoder architecture of our method, we do continuous pretraining from the public checkpoints of T5 for 250K steps with batch size 256 using the masked span prediction. Since each masked span (consists of multiple tokens) is replaced by a single special token, when using masking ratio is 15%, the number of special tokens in sequence is not too large, we keep masking ratio % unchanged.
7.5.4 Downstream Finetuning
The statistics of the sequence lengths of instances in each dataset summarized in Tab. 6 The hyperparameters of all experiments are summarized in Tab [] When there are multiple values in an entry, it means we perform hyperparameter search these values. The amount of search is determined by the size of datasets. If dataset is relatively large, we only search the learning rate. If dataset is small, we include batch size and the number of epochs in search. For all tasks, the sequence lengths are longer than the model length m, the sequences will be truncated and only the first tokens will be used. For encoder-decoder models, we use greedy decoding in sequence generations for simplicity. The maximal decoder output length, specified in Tab. TT is set such that the maximal length covers the output lengths of more than 99% of instances. When the length of covering 99% of instances is greater than 512, we just set the maximal decoder output length to 512. Additionally, we show one extra experiment on MultiNews [1 in Tab. which is not in the main text due to space limit.
7.5.5 Non-Language Tasks
While the focus of this work is on language tasks, the overall design does not limit its application to other tasks as long as the assumption ("a subset of tokens are disproportionately responsible for
25

---

Table 11: Hyperparameters for all experiments.
LM
EncodderOOnly QuALITY
Enceder Decoder CNN/Dailymail
Task
HotporQA
WikiHop
WikiHop
HotporQA
MediaSum
Qasper
Optimizer
Adam
Adam
Adam
Adam
Adam
Adam
Adam
Adam
Weight Decay
0,01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
LR Decay
Linear
Linear
Lineur
Lineur
Linear
Linear
Linear
Linear
Precision
FP16
FP16
FP16
BF16
BF16
BF16
BF16
BF16
Batch Size
16
32
32
32
32
32
[16, 32}
I Learning Rate
(3e-5, 5e-5)
(3e-5, 5e-5)
[3e-5, Se-5)
[le44 3e-4]
3e-4)
[le44 Je-4]
( (le.4, 3e-4)
Iee4, 3e-4]
Epochs
[10, 20;
10
10
10
10
[10, 20
Warmup Steps
1000
200
1000
1000
1000
1000
1000
200
Max Ouigut Length
32
40
256
256
128
LM
Encoder Decoder
QuALITY ContracNL.I NaraatvveA
Arxiv
SummScreenFD
GovReport
QMSum
Muliiews
Optimizer
Adam
Adam
Adam
Adam
Adam
Adam
Adam
Adam
Weight Decay
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
LR Decay
Linear
Linear
Linear
Linear
Linear
Linear
Lineur
Linear
Precision
BF16
BF16
BF16
BF16
BF16
BF16
BF16
BF16
Batch Size
(16, 32)
[16. 32)
32
32
[16. 32)
[16,
{16. 32)
32
Learning Rate
(1e-4, 3e-4)
(1e-4,3e 4)
(Ie 3e-4)
[le-4, 3e-4]
(1e-4, 3e-4)
(le-4,ee-4)
(le-4, 3e-4)
[Je-4, 3e-4)
Epochs
[10,
[10, 20)
5
[10, 20)
[10, 20)
[10, 20)
(10, 20)
10
Warmup Steps
200
1000
1000
1000
200
1000
100
1000
Output Length
47
512
512
512
310
512
the model prediction" and VIP-tokens can be reasonably selected) holds or partially holds for the tasks. As result, we also tested our method the Long Range Arena (LRA) benchmark [31] and obtained very promising performance among all baselines compared in [39]. We get slightly better performance than the top performing baselines presented in MRA-attention, but note that we are not trying to show that our method outperforms other baselines but to verify that our method can indeed be applied to other tasks.
Note that there are multiple implementations and hyperparameters used in the LRA benchmark, and comparisons across different implementations and hyperparameters is awkward. We use the same implementation and same hyperparameters as (39] The VIP-token selection of our method in LRA experiments is quite easy. We simply use the prepended CLS token as the only VIP token since it is responsible for the final model classification. The results are shown in Tab. T2 All results except for ours are directly cited from [39]. Since LRA consists of a synthetic task (ListOps), language tasks (Text, Retrieval), and vision tasks (Image, Pathfinder), these results can serve as preliminary evidence indicating the potential applications of our method on other non-language tasks.
Table 12: Test set accuracy of LRA tasks
Methed
Listops
Text
Retreval
Image
Patifinder
Arg
Transfommer
37.1+04
65.2+n6
79.6+117
38.5++03
72.8+L11
58.7+-03
Performer
36.75-02
6522n9
19.5
38.6
71.4207
58.34011
37,4+0.3
570+11
784++01
67.2+0.1
55.6003
SOFT
16.3+-14
6522+0
83.3+10
3533+13
67.7=1.
57.5++05
SOFT + Com
37.1204
2:
829:00
$7.1445
68.1544
58.1109
Nystronformer
24.7++12.5
65.7+a1
802+-33
38.8+29
73.1+6.1
56.5+26
Nystrum Come
30.6+99
65.7+02
789+12
43.2+3
69.1=110
57.5+115
YOSO
37.0200
63.1::2
783:277
40.-1
72.220
58.4-193
YOSO Conv
37.2+00
61.9+12
78.++09
44.6+113
69.5+15
59.0+11
Reformer
1899=24
61.+14
782+16
42.4+04
68.9=1.1
51.7+02
Lougtormer
37.21-033
64.1+a1
7971111
42.6-:011
70.72003
589:001
Big Bird
37,4+03
64.3+111
799+aL1
409+1.1
12,6-07
59.0+03
II TrTanssomerr1 ID
30,4+488
66.0+n2
$0.1
42.14n5
70.7=6.1
57.8+118
Scattrbrain
37.5-00.1
64.4103
7966011
58.01:9
549-114
2RA
37,2+0.3
654+01
79.++06
39.5+0.
73.6+04
59.0+03
MRA-244
37.4200
64.3108
803:01
41.1104
738224
59.4-92
Ours
37.35005
05.3402
809:05
413311
74
59.9-09
7.6 Potential Application to Decoders
The goal of this work is to reduce the cost of attention as well as the feedforward network (FFN) block without changing the internals of the transformer block when dealing with ultra long sequences (which differentiates our work from the few recent ideas that deal with ultra long sequences). Based on the best feasibility of this goal, the scope of application is focused on the encoder and encoder-decoder settings. For standard auto-regressive decoder settings, it might be
26

---

difficult to compress the token that is being generated with neighboring tokens. It is in fact challenging to reduce the cost of FFN since every generated token will most likely need a full calculation of FFN when it is being generated.
Having said that, there are still clear opportunities for decoder-only models, which are left as our future work. We briefly describe three possible options to do so. (1) We can use the input tokens of the decoder as VIP-tokens to compress the representations of context sequence generated by the encoder before Cross Attention computation to reduce the cost of Cross Attention. (2) Auto-regressive decoding operates using Causal Attention at each step. This Causal Attention operation requires memory and computation that is linear in the length of the prefix. We can keep the same Causal Attention VIP-token (the representation of the token currently being generated) and apply our method to compress the representations of the previously generated tokens. This reduces the linear complexity of the Causal Attention operation to sublinear. This is useful for reducing the cost of inference. For training, we can break the sequence into two segments: prefix segment and decoding segment. Then, we can use the proposed compression in prefix segment and vanilla computation in decoding segment. To prevent look ahead to the future tokens, we might only use the first token in the decoding segment as VIP-token. (3) In many cases, the current large language models (LLMs) are not used directly to generate an ultra long text. Rather, the requirements for processing ultra longer context manifests due to the need to incorporate user input and previous LLM responses (like ChatGPT) or to incorporate search results (such as New Bing). In these cases, there is prefix context, and LLMs will generate text based on the user prompt and prefix context. We note that our method can indeed be applied to compress the prefix context, and the user prompt and currently generated tokens will be the VIP-tokens.
7.7 Practical Questions
How is the T5's relative positional encoding handled in our method?
To compute the relative positional bias for self-attention in T5, the position indices of queries and keys are needed (to calculate the position distance between each query and key). After applying our method, the input the T5 block is the compressed sequence (some tokens are compressed while some tokens remain uncompressed). For each uncompressed token, the position index remains unchanged as its true position in the original sequence. For each new token that represents a compressed segment, the position index is the floored average of position indices of tokens in the segment. In this way, we can minimize the amount of modification needed to the internals of the T5 block, and the relative attention bias for the compressed sequence is an approximation of the attention bias for the original sequence.
VIP-token selection is task dependent, how to do this selection?
VIP-token selection requires some understanding of the tasks. However, we believe that reasonable selection can be made with some generic knowledge for most tasks or use cases. For example, for question answering tasks, we just use questions VIP-tokens. For classification tasks (for example, Long Range Arane benchmark shown in Appendix), we simply use CLS token as the VIP-token since only CLS token is used for final prediction. For masked language modeling, we the masked tokens as the VIP-tokens since only these masked tokens are used for final prediction. For question answering, the question tokens (and candidate tokens for multi-choice QA) are used the VIP-tokens since "they (1) are important to the specific task goals and (2) easily pre-identifiable by the user." In the worst case, if there is no obvious token be selected, we can prepend some learnable "latent" tokens or certain user commands (such as "summarize" for summarization tasks as we used in our experiments) and use them as VIP-tokens (in fact, CLS tokens can be thought of as these Iearnable tokens).
Why is the performance of our method is better than standard models?
Our method is an approximation of the standard models, which should be inferior to the standard models, but in some cases, the performance of our method is better than standard models. We believe the reason is that the correct inductive bias improves the performance for tasks with limited amounts of data. Our approach is forced to compress irrelevant information and the attention is carried out on the compressed sequences, but in standard model with standard attention, each token has access to the entire sequence, which enables larger degree of freedom. As result, more training data might be required for the model to learn the correct pattern or bias.
27


Reviews:
[{"review_id": "4xfmB9zGsq", "reviewer": "Reviewer_FRn4", "summary": "The paper presents a new method to reduce the computational cost of transformer models on long input sequences. It proposes to use certain tokens (VIP tokens) that will be responsible for compressing the rest of the sequence into fewer tokens that can then be processed efficiently. In detail, a tree is constructed from the input features to the transformer block such that at each node we have the mean of the children of that node. To construct the feature sequence that will be processed, the averaged attention of the nodes of the tree with the VIP tokens is used to walk the tree until the leaves are reached. The reached nodes form the input sequence to the transformer block. Using the tree and the stored differences between the nodes and their children the new sequence is constructed after the transformer block. Thorough experiments show that the proposed attention achieves results on par with dense attention while being significantly faster to compute.", "questions": "My main questions have to do with the calculation of the runtime of the presented method.\n\nAre the numbers for a single sequence? In that case how does the method scale with the batch size given that different samples will have different paths in the tree which will result in many out of order copies that may make the method slower.\n\nIn addition, is the calculated runtime for a forward pass or for a full training step?", "limitations": "The authors adequately discuss the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Both using a set of tokens to generate the \"clustering\" of the input sequence as well as using the tree of differences to recreate the full sequence are very interesting and original methods.\n- The experimental analysis is thorough and clearly shows that the proposed method works as well as dense attention in the examined benchmarks", "weaknesses": "- The main benefit of the method is the runtime efficiency, however the experiments do not describe adequately what this measured runtime is.\n  1. It is mentioned that it is the time for a single sequence? How does the method scale wrt batch size?\n  2. It is not clear whether it is the forward pass time or the forward/backward. How does this method scale for training?\n- There is a lot of theoretical analysis that seems slightly unnecessary as it doesn't provide much clarity but rather confuses given that the main approximation that allows for the method is taken from [6] and is not analyzed further in this work.\n- The proposed method cannot trivially be used in an autoregressive setting as it is really hard to efficiently compress N tokens while information flows only from the first to the N-th.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please refer to the global response for our response to the questions about decoder models.\n\n1. Clarification about how the runtimes are measured. \n\nThanks for asking this question. The runtimes presented in the experiment section are measured runtimes of a complete training step (including both forward and backward). For each method, we use the largest batch size that can fit into a 80GB A100 and measure the average latency of 10 steps. Then, the average latency is divided by the batch size to get the estimated runtime for a single instance. Via this procedure, we seek to measure the peak efficiency of each method when the GPU is at the highest possible utilization. We will make this clear in the paper. Let us know if this clarification addresses the question.  \n\n2. How does the method scale with the batch size given that different samples will have different paths in the tree which will result in many out of order copies that may make the method slower.\n\nAs noted in the answer above, the batch size is larger than 1. Each individual instance will have its own tree, but this does not make the method any slower (for single instance runtime). \n\nWhile in the main paper, the compression and decompression is represented in a matrix form $S_c$ and the pseudo inverse $S_c^{\\dagger}$, in our algorithm (Figure 3 and Algorithm 1 and 2 in the Appendix), the mathematically equivalent $S_cC$ is obtained by gathering the leaf nodes of constructed tree (Figure 3 visualization) or obtained from the constructed set J (Algorithm 1 and 2 in the Appendix). \n\nSimilarly, in our implementation, we use sorting, tensor sliding, average pooling and others, to obtain a mathematically equivalent $S_cC$ with higher efficiency. All of these operators are parallelized along the batch dimension natively in PyTorch, and will be available within the companion codebase for the paper. \n\n3. There is a lot of theoretical analysis that seems slightly unnecessary as it doesn't provide much clarity but rather confuses given that the main approximation that allows for the method is taken from [6] and is not analyzed further in this work.\n\nAs briefly discussed in Appendix 2.6, the method is inspired from [6], but [6] itself does not directly provide the approximation that we need. Since the readership is broad, we felt that it would be useful for a reader to check that the algorithm is sound (see how our analysis in Appendix is connected to Equation 12 in the main text via Claim 2.2 in Appendix). The remaining analysis, such as the one in Appendix 2.5, discusses the implications of applying this approximation for compressing the sequence. We are happy to use this suggestion to further improve the clarity of the analysis or if suggested, deemphasize it.  \n\n[6] Multi Resolution Analysis (MRA) for Approximate Self-Attention\n\nWe are happy for your appreciation of our work and will be glad to answer any additional questions. \n"}, {"review_id": "hARBLzBF01", "reviewer": "Reviewer_2SnC", "summary": "VIP-token centric compression (VCC) aims to solve the quadratic attention complexity bottleneck in the self-attention component and the transformer encoder block. Roughly, it denotes some tokens as very important (VIP) and compresses the remaining sequence using a low-rank approximation. They benchmark on natural language data and do experiments to verify the time and space complexity from their theoretical analysis.", "questions": "How does this method perform in other large context non-language tasks like images or audio or even synthetic tasks like Long Range Arena where the VIP token selection is less obvious?\n\nIt would be great to see decoder experiments?", "limitations": "Authors should be commended for addressing weaknesses of the method like the selection of VIP tokens and encoder-only aspect.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "They achieve impressive accuracy and performance numbers. Strong results on question-answering tasks that require long context and small runtime. They scale to 128k tokens and are able to tackle NarrativeQA, although the results are not as strong.\n\nThe method is intuitive and the analysis and description of the method is clear.\n\nThey were able to get strong results with pretrained weights from existing transformer encoder models.", "weaknesses": "The idea of VIP tokens is similar to the global memory component of efficient transformers like ETC, BigBird, and Longformer. It suffers a similar problem that it's not clear which tokens are VIP.\n\nExperiments are only done on encoders. They mention in passing that the method can be adapted to decoding, which seems to be more in the vogue these days.\n\nSome aspects of the experiments like doing a different computation in the first 4 transformer layers make me think this method may be finicky and hard to apply in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please refer to the global response for our response to the questions about decoder models.\n\n1. The idea of VIP tokens is similar to the global memory component of efficient transformers like ETC, BigBird, and Longformer. It suffers a similar problem that it's not clear which tokens are VIP.\n\nIt is true that selecting VIP-tokens requires some understanding of the tasks. However, we believe that a reasonable selection can be made with some generic knowledge for most tasks or use cases. For example, for question answering tasks, we just use questions as VIP-tokens. For classification tasks (for example, Long Range Arane benchmark shown below), we simply use CLS token as the VIP-token since only CLS token is used for final prediction. For masked language modeling, we use the masked tokens as the VIP-tokens since only these masked tokens are used for final prediction. For question answering, the question tokens (and candidate tokens for multi-choice QA) are used as the VIP-tokens since “they (1) are important to the specific task goals and (2) easily pre-identifiable by the user.” In the worst case, if there is no obvious token to be selected, we can prepend some learnable “latent” tokens or certain user commands (such as “summarize” for summarization tasks as we used in our experiments) and use them as VIP-tokens (in fact, CLS tokens can be thought of as these learnable tokens). We are happy to further emphasize this point in the paper. \n\n2. Some aspects of the experiments like doing a different computation in the first 4 transformer layers make me think this method may be finicky and hard to apply in general.\n\nIn our experiments, we use the first 4 transformer layers to process each 512-length non-overlapping segment of the input sequence into a reasonably good initial representation for our compression to operate on. Since there is no communication among segments, the downstream tasks cannot be solved by these first 4 transformer layers alone. \n\nWe should clarify that our method also works in the setting where the compression is applied to all transformer layers. In our early evaluations, we also tested the setting with 12 x VCC transformer layers, but it leads to some performance degradation compared to the setting with 4 x short segment transformer layers + 8 x VCC transformer layers (for base models). \n\nAlso, we note that unlike alternative methods that change the size of embedding matrices in the intermediate layers (such as gradually reducing sequence length as the input propagates to deeper layers), our method is easy when used as a drop-in replacement for vanilla transformer layers. This is because regardless of whether our compression is applied, similar to a Transformer block, the output of each layer is the same sized embedding matrix of the input sequence. Further, our implementation also makes it easier to use and experiment with since we only need to specify what type of computation (short segment transformer or VCC transformer) to use at each layer. Finally, our implementation works with arbitrary arrangements of computation as shown below: \n\nFor example, the following is what we used for encoder-decoder model in experiment section: \n\n`encoder_layers = [\"src.t5.models.layers.T5Block\"] * 6 + [\"src.t5.models.vcc_layers.VccT5Block\"] * 18`\n\nWe can also alternatively use these two types of layers in an alternating order: \n\n`encoder_layers = [\"src.t5.models.layers.T5Block\", \"src.t5.models.vcc_layers.VccT5Block\"] * 12`\n\n3. How does this method perform in other large context non-language tasks like images or audio or even synthetic tasks like Long Range Arena where the VIP token selection is less obvious?\n\nWhile the focus of this work is on language tasks, the overall design does not limit its application to other tasks as long as the assumption (“a subset of tokens are disproportionately responsible for the model prediction” discussed in our paper and VIP-tokens can be reasonably selected) holds or partially holds for the tasks. \n\nAfter reading the reviewer’s suggestion, we also tested our method on the Long Range Arena (LRA) benchmark and obtained very promising performance among all baselines compared in MRA-attention [1] (We get slightly better performance than the top performing baselines presented in MRA-attention, but note that we are not trying to show that our method outperforms other baselines but to verify that our method can indeed be applied to other tasks.). \n\nNote that there are multiple implementations and hyperparameters used in the LRA benchmark, and comparisons across different implementations and hyperparameters is awkward. We use the same implementation and same hyperparameters as MRA-attention. Here, we present the LRA results of our method (average and 95% error bar calculated over 3 trials). Please refer to Table 5 in MRA-attention [1] for the LRA results of other baselines. \n\nListOps: $37.3 \\pm 0.5$\n\nText: $65.3 \\pm 0.2$\n\nRetrieval: $80.9 \\pm 0.5$\n\nImage: $41.3 \\pm 1.7$\n\nPathfinder: $74.6 \\pm 1.5$\n\nAvg: $59.9 \\pm 0.9$\n\nThe VIP token selection in LRA experiments is actually quite easy. We simply use the prepended CLS token as the only VIP token since it is responsible for the final model classification. \n\nSince LRA consists of a synthetic task (ListOps), language tasks (Text, Retrieval), and vision tasks (Image, Pathfinder), these results can serve as **preliminary evidence** indicating the potential applications of our method on other non-language tasks. \n\n[1] Multi Resolution Analysis (MRA) for Approximate Self-Attention\n\nThank you for your supports, and we are happy to answer any additional questions. "}, {"review_id": "yfGuo24Czq", "reviewer": "Reviewer_JBnL", "summary": "This work introduces a method to scale up the supported number of tokens for transformer-based models. It prioritize the important/dominant tokens and compress those unimportant tokens during the processing. The conducted experiments demonstrate the effectiveness of the proposed method, and show that the proposed method can be directly incorporated into existing pretrained models with additional finetuning.", "questions": "1. Are the proposed methods, which include but are not limited to the method for evaluating the importance of different tokens, generally applicable (e.g., for other tasks, or for other modalities)? If yes, pls explain more. If not, please analyze the limitations in detail and in-depthly.\n2. The proposed compression and decompression are in fact implemented by matrix multiplication. How can you ensure the tokens of different importances (not referring to splitting as VIP or non-VIP) are compressed or decomposed as expected?\n3. Why can placing VIP tokens in the front seats by re-ordering play the role of prioritizing them? How about repeating the VIP tokens (this is a more commonly used way for highlighting important tokens)? Pls compare these two, if possible.", "limitations": "The biggest problem is that this paper is quite attractive at the beginning, but the main parts, especially for the proposed methods, are somewhat disappointing since they are not that solid and insightful as expected. Pls see the weakness part and my questions for more detailed comments.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "I think this work is trying to target an important problem, i.e., how to break through the limitation on the number of tokens to be processed. The proposed VIP-token centric compression is overall reasonable in terms of its high-level idea. The coducted experiments provide evidences for its efficiency benefits and performance superority when compared to the baselines with the same sequence length.", "weaknesses": "The targeted problem and the main story are quite attractive at the first glance. However, the proposed methods are not that solid and insightful as expected, making I feel some parts somewhat overclaimed. To name a few, for the high-level idea of this work, evaluating the importance of VIP-tokens should be one of major parts. However, the proposed method for evaluating the importance of difference tokens are based on some intuitive assumptions. These assumptions are task-specific or case-specific, affecting the generalization capacity of the proposed method in fact.\n\nBesides the proposed method for evaluating the importance of tokens, other parts of the proposed method only introduces high-level idea deas and illustrates them with examples, without providing a rigorous modeling.\n\nThe experiments are conducted mainly on ultra long sequences. This matches with the major story, but in fact, prioritizing important tokens should be generally benefitial for a wide range of tasks using transformer-based models. The authors have not provides discussion or analysis on these.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Evaluating the importance of different tokens is based on some intuitive assumptions. Assumptions are task-specific or case-specific.\n\nWe are a little unclear about the concern “evaluating the importance of different tokens are based on some intuitive assumptions”. We will be grateful if the reviewer could clarify or suggest any additional experiments. We will answer the question below based on our current interpretation: \n\nYes, this approach is based on intuition from experimental feedback. \n\nOnly a small subset of tokens (VIP-tokens) are important for the final prediction. This is true for many tasks. For example, in classification tasks, only the representation of CLS token is used to make the prediction. The representations of other tokens are only used to aggregate their information into the CLS token in the intermediate layers. **The selection of VIP-tokens is task specific, but this selection can be made with some simple knowledge for most use cases.** (please also see reviewer 2SnC Q1 response) \n\nOnly a small subset of tokens (important non-VIP tokens) in a long sequence will provide relevant information for the final prediction. If the assumption does not hold, we will see performance degradation. But we achieve good performance on a variety of downstream tasks which suggests that the assumption at least partially holds. **The selection of important non-VIP tokens is guided by VIP-tokens using our algorithm and does not require user input.** Based on approximation quality presented in the answer to reviewer xiLt’s Q2, our VIP centric compression does well in preserving important non-VIP tokens in the compressed sequence.\n\n2. Only introduces high-level ideas and illustrates them with examples, without providing rigorous modeling.\n\nIn the main text, we intentionally provide a high-level idea and toy examples (in section 3.3 and 3.4) for presentation purposes because introducing all low-level details will distract from the overall rationale of the approach and its effectiveness. \n\nAlso, including all of these details seemed to make the paper unnecessarily dense and was distracting from the main message. To ensure that the ideas were accessible to a broad cross-section of the readership, we decided to move many of the technical details to the Appendix. \n\nA rigorous step-by-step derivation of our method is discussed in the Appendix section 2. The formal descriptions of the procedures introduced in section 3.3 and 3.4 are described in Algorithm 1 (page 6) and 2 (page 9) in the Appendix. In the main text, we give several pointers (at line 205, line 219, line 245, line 291) to the Appendix for the reader interested in such details. If there are specific sub-sections that will be valuable to include in the main text, we appreciate suggestions and will make every attempt to include in the main text. Thank you!\n\n3. Authors have not provided discussion or analysis on other tasks/modalities that would be benefit from prioritizing important tokens. \n\nYes, it is true that prioritizing important tokens is generally beneficial. As described in lines 379-387, our construction is most useful for ultra-long sequences. For other tasks with shorter sequences (< 4K), vanilla Transformer or efficient variants (Longformer, Big Bird, etc.) may be sufficient. Nonetheless, we can still test our method on other tasks. Please refer to our response to reviewer 2SnC Q3. \n\n4. Why can placing VIP tokens in the front seats by reordering play the role of prioritizing them? How about repeating the VIP tokens? \n\nThanks for this question. The goal of placing VIP tokens in the front seats is not to prioritize them. Instead, re-ordering makes the analysis, implementation and presentation of our method much clearer and simpler (line 167 in main text). In fact, placing VIP tokens at the end of the sequence can also serve the same purpose. \n\nAs shown in the paper, by placing VIP tokens in the front, we can decompose the computation of a Transformer block into (a) computation for VIP tokens, (b) computation for non-VIP tokens, and (c) interaction between VIP tokens and non-VIP tokens for easier analysis. By reordering, our implementation also becomes easier. \n\nWhy not repeat the VIP tokens? Suppose the sequence is [T0, T1, T2, …], and T0 is the VIP-token, then our interpretation is that after repeating (say once), the sequence will become [T0, T0, T1, T2, …]. Here, repeating the VIP-tokens means adjusting the attention weights such that the attention to T0 has higher weights. Our goal is to use VIP-tokens to guide compression of non-VIP tokens rather than let the non-VIP tokens pay higher attention to VIP-tokens. \n\nPlease let us know if we misinterpreted the question. \n\n5. Compression and decompression are implemented by matrix multiplication. How to ensure the tokens of different importances are compressed or decomposed as expected?\n\nWe should clarify that we construct different compression matrices $S_c$ for different sequences. At a high-level, the compression matrix $S_c$ is constructed adaptively based on the different importance scores (VIP tokens’ attention scores to the compressed representation of segments) of non-VIP tokens. So, we ensure proper compression and decompression by properly constructing $S_c$ according to each input sequence. \n\nNote that in our algorithm, we do not need to perform matrix multiplication to obtain $S_cC$, rather we can obtain the rows of $S_cC$ while we are constructing the set J in Appendix Algorithm 1(see Appendix line 218-219). In visualization (Fig 3), the rows of $S_cC$ are the leaf nodes of the tree after growing the tree. \n\nFor implementation, similarly, we use PyTorch operators including sorting (based on “different importances”), tensor sliding, and other operators to obtain the rows of $S_cC$. \n\nThank you for your feedback, and we are happy to answer any additional questions. "}, {"review_id": "LOrCYn5HI5", "reviewer": "Reviewer_z4Ur", "summary": "This paper proposes VIP-token centric compression (VCC) as a method to improve the efficiency of Transformers for ultra long sequences. Based on the impact on approximating the representation of the VIP-tokens, VCC can compress the long sequence into a much smaller representation. Thorough experiments validated the effectiveness of the proposed method.", "questions": "See Weaknesses.", "limitations": "Adequately addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* Long sequences input is a practical problem for current LLM-based applications. And the efficient technology for long sequences that this paper focused on has a high application value, in my opinion.\n* The paper is well-written, the method is generally novel and the effectiveness is validated by thorough experiments.\n* The authors plan to release the code and checkpoints.\n", "weaknesses": "* FLOPs is missing. Runtime is a hardware-dependent metric, and it would be better to see also hardware-independent metrics FLOPs.\n* Why only experiments on encoder-only and encoder-decoder architectures? It would be better to see experiments or discussions on recently more popular decoder-only architectures.\n* KV Cache is a useful technique for accelerating Transformer inference and has been already integrated into widely used packages such as huggingface transformer and timm. It would be better to see the discussion on whether KV Cache and VCC are orthogonal and whether they can be used simultaneously. \n* Missing reference. It would be better to have a discussion on the difference with the previous [1] and concurrent [2] work that scales Transformer to 262k and one million, respectively. \n\n1. Memorizing Transformers. In ICLR 2022.\n2. Scaling Transformer to 1M tokens and beyond with RMT. In arXiv.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please refer to the global response for our response to the questions about decoder models.\n\n1. FLOPs is missing. Runtime is a hardware-dependent metric, and it would be better to see also hardware-independent metrics FLOPs.\n\nThanks for this nice suggestion. We will include FLOPs for as many experiments as possible (we are not able to profile all methods reliably since some implementations contain custom CUDA kernels). In this case, automatic tools for calculating FLOPs (such as deepspeed’s FlopsProfiler) do not always work and may throw errors or produce incorrect results when the code contains custom CUDA kernels. As a preview, here we provide some FLOP profiling results for the WikiHop downstream task using encoder-only models (last column of table 1 where input sequence length is 4K), \n\nRoBERTa: 1317 GFLOPs\n\nBigBird: 790 GFLOPs\n\nLongformer: FlopsProfiler throw errors\n\nMRA Attention: 697 GFLOPs + Unknown FLOPs for approximating attention that involves custom CUDA kernels, which are NOT captured by FlopsProfiler\n\nVCC: 526 GFLOPs\n\nOur method still has the lowest FLOPs. \n\nHowever, we note that FLOP numbers do not always reflect practical latency reductions. Memory bandwidth and latency (which are not captured by FLOP numbers) also play an important role in the overall latency. For example, sparse matrix multiplication (with unstructured sparsity) usually has a much lower FLOP count than dense matrix multiplication. But, the latency reduction is only possible when sparsity is at least 95% or more (depending on the implementation) since sparse matrix multiplication is a memory bandwidth bounded operator. \n\nOn the other hand, yes, even though it is a hardware-dependent metric, a good runtime requires all contributing factors including FLOPs, memory bandwidth, and memory latency to be reasonably good. This is the reason we reported runtime as our efficiency metric. But we appreciate the suggestion and will definitely include FLOPs in the main paper.\n\n2. It would be better to see the discussion on whether KV Cache and VCC are orthogonal and whether they can be used simultaneously. \n\nThe KV cache for inference is used in the autoregressive setting for the Transformer decoder. The current implementation of our method supports encoder in encoder-only and encoder-decoder model, and the decoder remains unchanged, so KV cache in the decoder remains unchanged and can be used simultaneously to complement our method in encoder. \n\n3. Missing reference. It would be better to have a discussion on the difference with the previous [1] and concurrent [2] work that scales Transformer to 262k and one million, respectively. \n\nThanks for the suggestion. In our paper, we discussed differences with some previous works, but yes, we are happy to include more discussion on these related works about Memorizing Transformers [1] and RMT [2]. \n\nBoth Memorizing Transformers and RMT follow a recurrent design and store the past context in an external memory module (memory with kNN lookup for Memorizing Transformers and compressed memory for RMT). They are good for autoregressive decoding settings, but lack the ability of bidirectional encoding. More importantly, similar to efficient Transformers with linear cost attention, both approaches do not try to reduce the linear cost (on sequence length) for FFN, so the computation might still be expensive for processing ultra long sequences. By sequentially processing one segment of input sequences at one time and truncating back-propagated gradients to the external memory, they avoid blowing up the GPU memory when processing ultra long sequences. \n\nOn the other hand, our method seeks to reduce the overall cost (both self-attention and FFN) of processing ultra long sequences and processes the entire sequence simultaneously. We will include more discussions about the comparison to these works in our paper. \n\n[1] Memorizing Transformers. In ICLR 2022. \n\n[2] Scaling Transformer to 1M tokens and beyond with RMT. In arXiv.\n\nThank you for your appreciation and feedback, and we will be glad to answer any additional questions. \n\n"}, {"review_id": "YtPUFf5Cyr", "reviewer": "Reviewer_xiLt", "summary": "This paper aims at designing efficient Transformers for ultra long sequences. The design is motivated from the intuition that only a small subset of special tokens, which are referred to as VIP tokens, are most relevant to the final prediction. Based on the intuition, a multi-resolution compression is proposed to reduce the computational cost. Experiments are conducted to show the efficiency and accuracy of the proposed model.", "questions": "+ Is the proposed approach generalizable to decoder-only models?\n\n+ Is the proposed approach compatible with relative positional encoding? How is the T5's positional encoding handled in the experiments?\n\n+ Can you provide more illustrations on the approximation error of the compression technique?\n", "limitations": "Limitations are discussed in Section 4. However, I recommend the authors to explicitly discuss the applicability to decoder-only models, if the proposed approach only applies to Transformer encoders.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ Nice presentation.\n\n+ The observation that only a small subset of special tokens are most relevant to the final prediction is insightful. The proposed task-driven multi-resolution compression technique is well-motivated and technically sound.\n\n+ The experiments are extensive and show reasonable performance gain.", "weaknesses": "+ The major concern for the proposed approach is that it **only applies to Transformer encoders**. Many important LLMs today are decoder-only, e.g., GPT, PaLM, LLaMA, etc. The authors formulate their method in an encoder layer (Sections 2 & 3), and show their method can lead to decent performance gains on encoder-only models and encoder-decoder models. However it seems non-trivial to generalize the approach to decoder-only models.\n\n+ The compression also seems to **impede the use of relative positional encoding**. Although there are experiments on T5-based models, no details are provided on how the relative positional information is handled.\n\n+ As discussed at the beginning of Section 3.3, the multi-resolution compression technique is proposed to minimize the approximation error of Eq. (12). However, **neither theoretical guarantees nor numerical simulations on the approximation error are provided**. There seems to be some theoretical results in the appendix but I can't find any analysis on the approximation error (defined in Eq. (33)). Since the multi-resolution compression is the main technical contribution of this paper, I encourage the authors to provide some theoretical analysis and/or numerical experiments on the approximation error in the main body of the paper. \n\n+ **Minor issues**.\n   + Line 121: $n_p$ is the size of the VIP-tokens: \"size\" seems ambiguous here and can be misunderstood as \"dimensionality\". I suggest writing _$n_p$ is the number of the VIP-tokens_.\n   + Eq. (9): $\\mathbf I_{n_p\\times n_p}$ can be simplified to $\\mathbf I_{n_p}$.\n   + Line 223, \"$s\\in\\cdots$\" should be \"_where_ $s\\in\\cdots$\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please refer to the global response for our response to the questions about decoder models. \n\n1. How is the T5's relative positional encoding handled in the experiments?\n\nThis detail is not included in the paper, but we will definitely include it in our updated Appendix. \n\nTo compute the relative positional bias for self-attention in T5, the position indices of queries and keys are needed (to calculate the position distance between each query and key). After applying our method, the input to the T5 block is the compressed sequence (some tokens are compressed while some tokens remain uncompressed). For each uncompressed token, the position index remains unchanged as its true position in the original sequence. For each new token that represents a compressed segment, the position index is the floored average of position indices of tokens in the segment. In this way, we can minimize the amount of modification needed to the internals of the T5 block, and the relative attention bias for the compressed sequence is an approximation of the attention bias for the original sequence. \n\n2. Neither theoretical guarantees nor numerical simulations on the approximation error are provided. Can you provide more illustrations on the approximation error of the compression technique?\n\nThanks for the suggestion. The theoretical guarantee of approximation quality will be a special case of Proposition 4.5 in MRA-attention [1]. We assumed this would be less interesting to the reader but are happy to include it in the paper. \n\nBased on the reviewer’s question, we empirical measured the approximation quality of our VIP centric compression compared to random compression (the tree node splittings in Figure 3 are not guided by VIP-tokens, but are randomly selected) and full compression (no further tree node splittings in Figure 3 after the leaf nodes are all representing k-length segments). Let $\\hat{y}$ is the approximated representation of VIP tokens computed with compression and $y$ is the ground truth representation of VIP tokens computed without compression. We measure the relative approximation error (defined as $|| \\hat{y} - y ||_F / || y ||_F$ ) (closer to 0 is better) and correlation coefficient between $\\hat{y}$ and $y$ (closer to 1 is better). Here is the results: \n\nVIP centric compression: error is $0.1371$ and correlation is $0.9906$\n\nRandom compression: error is $0.4025$ and correlation is $0.9187$\n\nFull compression: error is $0.5280$ and correlation is $0.8689$\n\nWe will include this result in the main text. \n\n[1] Multi Resolution Analysis (MRA) for Approximate Self-Attention\n\n3. Minor issues. \n\nThanks for the suggestions, we will update our text accordingly. \n\nWe are grateful for your support and will be glad to answer any additional questions.\n"}]

Author rebuttal:
We are grateful for all reviewers' feedback and support. Please let us know if there are any remaining doubts or questions, and we are happy to answer any additional questions. 

1. Can our method be applied to decoders and decoder-only models?

As we discussed in the paper, although it is possible to apply our method for some decoder-only settings, applying the proposed method in an autoregressive setting is not straightforward, and the implementation is non-trivial. Preventing information leak of future tokens is one of the challenges. 

The goal of the paper is to reduce the cost of attention **as well as the feedforward network (FFN) block without changing the internals of the transformer block** when dealing with ultra long sequences (which differentiates our work from the few recent ideas that deal with ultra long sequences). Based on the best feasibility of this goal, the scope of application is focused on the encoder and encoder-decoder settings. 

For standard autoregressive decoder settings, it might be difficult to compress the token that is being generated with neighboring tokens. It is in fact challenging to reduce **the cost of FFN** since every generated token will most likely need a full calculation of FFN when it is being generated. 

Having said that, there are still clear opportunities for decoder-only models, which are left as our future work. 

- As discussed in Appendix 5, for this setting, we can apply this compression for reducing the cost of causal attention, but the efficiency gain will not be as significant as the encoder and the implementation will be more complicated when we incorporate it with the existing accelerations such as KV cache. 

- In many cases, the current LLMs are not used directly to generate an ultra long text. Rather, the requirements for processing ultra longer context manifests due to the need to incorporate user input and previous LLM responses (like ChatGPT) or to incorporate search results (such as New Bing). In these cases, there is a prefix context, and LLMs will generate text based on the user prompt and prefix context. We note that our method can indeed be applied to compress the prefix context, and the user prompt and currently generated tokens will be the VIP tokens. 

Based on the reviewers’ comments, we will include additional discussion regarding the limitations and these solutions for decoder-only models in the paper. 


Meta-review: This paper presents a new method to reduce the computational cost of transformer models on long input sequences. All reviewers recommended acceptance, based on merits such as a novel method (VIP-token centric compression) to improve efficiency of Transformers for long sequences, achieving good performance on several long-sequence tasks while being faster than compared baselines, and thorough experiments validate effectiveness. There are also some limitation pointed out such as the method currently only applies to encoder, not decoder models. Selection of VIP tokens requires some task-specific knowledge. FLOPs numbers missing. Runtime hardware-dependent. Some concerns on approximation error of compression technique, which warrants more analysis. Compatibility with relative positional encoding unclear. Differences with very related previous work not discussed. The authors are encouraged to take the feedback into account to improve the final revision.
Decision: Accept (poster)