Cluster-Former: Clustering-based Sparse Transformer for Question Answering
Authors: Shuohang Wang
Luowei Zhou
Zhe Gan
Yen-Chun Chen
Yuwei Fang
Siqi Sun
Yu Cheng
Jingjing Liu
Venue:  (2021)
Keywords: Transformer
Question Answering

Abstract: Transformer has become ubiquitous in the deep learning field. One of the key ingredients that destined its success is the self-attention mechanism, which allows fully-connected contextual encoding over input tokens. 
However, despite its effectiveness in modeling short sequences, self-attention suffers when handling inputs with extreme long-range dependencies, as its complexity grows quadratically with respect to the sequence length.
Therefore, long sequences are often encoded by Transformer in chunks using a sliding window.
In this paper, we propose Cluster-Former, a novel clustering-based sparse Transformer to perform attention across chunked sequences. The proposed framework is pivoted on two unique types of Transformer layer: Sliding-Window Layer and Cluster-Former Layer, which encode local sequence information and global context jointly and iteratively.
This new design allows information integration beyond local windows, which is especially beneficial for question answering (QA) tasks that rely on long-range dependencies. Experiments show that Cluster-Former achieves state-of-the-art performance on several major QA benchmarks.

Under review as a conference paper at ICLR 2021
CLUSTER-FORMER: CLUSTERING-BASED SPARSE TRANSFORMER FOR QUESTION ANSWERING
Anonymous authors Paper under double-blind review
ABSTRACT
Transformer has become ubiquitous in the deep learning field. One of the key ingredients that destined its success is the self-attention mechanism, which allows fully-connected contextual encoding over input tokens. However, despite its effee- tiveness in modeling short sequences, self-attention suffers when handling inputs with extreme long-range dependencies, as its complexity grows quadratically w.E.t often encoded by Transformer
the sequence length. Therefore, long sequences in chunks using a sliding window. In this paper, we propose Cluster-Formet a novel clustering- sparse Transformer to perform attention across chunked se- quences. The proposed framework is pivoted on two unique types of Transformer layer: Bldding-Windon Layer and Cluster-Former Layer, which encode local se- quence information and global context jointly and iteratively. This new design allows information integration beyond local windows, which is especially ben- eficial for question answering (QA) tasks that rely on long-range dependencies. Experiments show that Cluster-Former achieves state-of-the-e performance on several major QA benchmarks.
INTRODUCTION
Long-range contextual understanding has proven critical in many natural language processing (NLP) tasks. For example, the relevant context for correctly answering open-domain question can arch over thousands of words. Encoding long sequences via deep neural networks, however, has re- mained an expensive and challenging task due to high demand on training time and GPU memory. Traditional sequence modeling methods (Hochreiter Schmidhuber 1997) encode long sequences in chronological order, which suffers high latency. In the place of sequential encoding, recent mod- els such as Transformer (Vaswani et al. 2017) use simultaneous self-attention over the entire input instead, which has been successtully adopted many NLP tasks such textual entailment (Devlin) et al. 2019). dependency parsing (Zhou & Zhao 2019), and summarization (Lewis et al. (2019). A caveat with Transformer though is that building full connections over long sequences translates to quadratic growth on memory demand and computational complexity w.r.f. sequence length.
One way efficiently encode long sequences is to first chunk sequence into much shorter ones with a sliding window, then build connections between the shorter sequences (Figure [aa). For example, Child al. (2019), Beltagy et al./ (2020) and Zaheer al. (2020) apply sparse attention chunked sequences in hand-designed patterns in order to gather information from the chunks (Figure [b)). Choi al. (017) and Wang et al. (019)) first use simpler model filter chunked sequences, then process selected sequences with fully-connected self-attention. Rae et al. (2019) makes use of the shared memory of chunked sequences build connections between them. However, these methods cannot encode long-range dependencies with as much flexibility or accuracy as fully-connected self- attention, due to their dependency on hand-designed patterns.
Recently, several studies (Kitaev et al. [2200] Tay et al. (020b) propose to further improve the sparse attention mechanism by hashing or sorting the hidden states into different buckets (Figure [(c).. These works mainly explore tasks with relatively short sequences, such sentence-level Machine Translation (MT), where the number of hashing vectors relatively small (less than 16 in Kitaev et al. 2020)), allowing randomly initialized hashing vectors hash hidden states into correct buck- cts. However, how to use hashing- based attention in the context of long sequences (e.g.,, up to thousands of words) is still unexplored territory.

---

Under review as a conference paper at ICLR 2021
Sliding Window to short sequences
Attention preselected positions
Random Hashing Vectors
Clustering
Cenoroids
(a) Sliding window
(b) Sparse Attention
(c) Locality-Sensitvee Hashing (d) K-Means Clustering
Figure 1:
Illustration of different methods for processing long sequences. Each square represents
hidden state. The black-dotted boxes are Transformer layers. (a) is the
method to chunk a long sequence into short ones with window size 3 and stride 2. (b) builds cross- sequence attention based on sliding window over pre-selected positions (red-dotted boxes). (c) hashes the hidden states into different buckets by randomly-nnitializz vectors. (d) is our proposed approach cluster the hidden states. Our final model is a combination of (a) and (d) that processes both local and global context.
Our proposed framework for efficient long sequence encoding, Cluster-Former. marries both sliding-window and hashing-based methods to achieve effective local and long-range dependency encoding. Cluster-Former consists of two types of encoding layer. The first one (noted as Sliding- Window Layer) focuses extracting local information within sliding window. It applies Trans- former to the hidden states each chunked sequence independently, as shown Figure [a). The other (noted chunked sequences. Specifically, we first apply clustering to the input hidden states so that similar hidden states assigned to the same cluster, shown in Figure [d). The clustered and sorted input is then divided uniformly into chunks, each encoded by a Transformer layer. Note that to make model training more efficient, the cluster centroids not computed online but updated peri- odically (every epoch or few epochs). We accumulate the hidden states from the layer prior to the Huster-Former layer in a memory bank, and apply the K-Means algorithm to form cluster centroids during each update cycle. Compared to previously discussed sparse attention based on pre-selected positions (Figure [b)) or mandomly-initializne hashing vectors (Figure [c)), experimental results show that our method can encode dependency across chunked sequences more effectively.
Cluster-Former Layer) learns encode global information beyond the initial
Our contributions can be summarized as follows. (i) We propose Cluster-Former, a novel approach to capturing long-range dependencies more effectively than locality-sensitive hashing method. (it) We propose new Transformer-basee framework to process long sequences by combining Sliding- Window and Cluster-Former layers to extract both local and global contextual information. (iii) Our model achieves the best performance on question answering datasets of Natural Questions (long answer), SearchQA, and Quasar-T.
RELATED WORK
Efficient Transformers With Transformer models growing larger and larger, how to handle longer
sequences arises as a critical challenge. Many works have been proposed to improve the computa- tional and memory efficiency of Transformers, including Sparse Transformer (Child et al.) 2019).
Routing Transformer (Roy et al. 2200)), Reformer (Kitaev et al. 2020), Sinkhorn Transformer (Tay
2020b). Longformer (Beltagy et al. 2020). ETC (Ainslie et al. 2020). Synthesizer Tay et al. 2020a). Performer (Choromanski et al. (020)) Linformer (Wang et al. (020).. Linear Trans- former (Katharopoulos et al.) al.]|2200) 2020), and BigBird (Zaheer et al., 2020). TTy et al. (2020c) provided an excellent literature survey on this emerging topic. Our method falls into the setting of learnable sparse-attention patterns including Routing Transformer, Reformer and Sinkhorn Transformer. Our method is closer to Routing Transformer (Roy et al.] 2020) which also uses cluster centroids to learn patterns, while we are targeting on quite different tasks (language modeling VS question answering) which leads to the significant difference frameworks. Moreover, cluster centroids are up- dated very different ways (online exponentially moving centroids VS periodical centroids update by KMeans).
2

---

Under review as a conference paper at ICLR 2021
leyer
lyyer
Slidig
Transformer
Transformer
Transformer
Cluster1
Cluster2
ClusterN
Cantroids
Hidden sistes re-orderingg
T
K-Means
Every/ spocch
Transformer
Transformer
Transformer
Transtormer aliding
Memory bank
(b) Cluster-Formar
An overview proposed Transformer layer. (a) Sliding- Window layer over a sequence. (b) Cluster-Formn layer over clustered hidden states from the output of (a). Cluster centroids periodically updated based on the memory bank the hidden states the corresponding layer. Note that the sequence inputs in (a) and (b) usually come from two different samples.
Figure 2:
Long Sequence in Question Answering For tasks such as open-domain question answer- ing (Chen al. 2017). large volume of documents paragraphs is usually retrieved infer the answer, yielding extremely long context content. Despite the fact that state-of-the-arr NLP models capable of extracting answers amid complex context, they still struggle with extremely long put sequences. Recent advances that advocate the use of large-scale pre-trained models (Lewis et al., 2019 Liu et al., [219 Lan et al. 2020) for question answering make this problem more prominent, due to tremendous memory consumption. To process long sequences, the most widely-used method to first use lightweight model filter out redundant text, then use sliding-window-ber
ap-
proaches to encode the remaining sequences with a more sophisticated model. [hen al. (2017) integrated bi-gram features into Information Retrieval (IR) methods to retrieve related documents more accurately. Wang et al. 2018) trained paragraph selector using as the reward whether the entire system can obtain the correct answer or not [in et al. (2018) proposed to use a paragraph ranking model to curate data that are required for training reading comprehension models. Wang et al. (2019) trained a ranker to merge paragraphs for multi-passage reasoning. Asai et al.] (2020) trained recurrent retriever to select paragraphs for multi-hop question answering. Besides the above methods, directly applying Efficient Transformers to process long sequences in question answering another option. In this paper, we focus on this direction by directly training our Cluster-Former on the long context without using lightweight model for context filtering.
3 PROPOSED APPROACH
The proposed framework to handle long sequences is pivoted on two types of Transformer layer: (i) Sliding- Windoow Layer; and (it) Staster-Former Layer. The former focuses on encoding local sequence information, while the latter is encoding global context and always built top of the former layer. An overview of the two layers is illustrated in Figure
3.1 SLIDING- WINDOW LAYER
Despite that our focus is on capturing long-range dependencies for global context, local information also plays critical role for knowledge propagation. Therefore, in the lower section of our network, we adopt the traditional sliding-window encoding mechanism. A sliding window segments a long with window size 1 and stride m, illustrated in Fig- ure a Note that in this paper, we focus on question answering tasks, for which we concatenate the question Q with each sequence chunked from the document:
sequence X into short, overlapping
H [Q: X [m x k (m k 1)]]

---

Under review as a conference paper at ICLR 2021
where Q Raxd denotes question embeddings given QA task, is the number of tokens in the question, and X IR= is the embeddings for all context, x the number tokens in context. the ID of the chunked sequence, I is the window size, and m is the stride of the sliding window. [idx] idra] indicates selecting rows between the index of idæ and idæ; of the matrix. [++]] means concatenating the matrices along the row. We first Transformer encode each sequence in sliding window as follows:
H Transformer(H]])
where H E R(++0xx is the output of Transformer on the k-th sequence in the n-th layer. While it is not the final output of the n-th layer. As expect the neighbouring sequences to share useful information in hidden states as well, we always set m < to allow overlapping between sequences. We the values of the Transformer hidden states at the overlapped tokens between windows as final outputs. To merge the representations from (k 1)-th sequence:
H lg : 1 I -m]
m++1
+
H H lg + m end],
H [g : +l m]
/
2,
and merge representations from (k + 1)-th sequence:
H me++ lg + m end] + = : m],
[g m end] / 2,
where + + is to add matrices in-place and / is to divide a matrix by scalar value in-place. The merged hidden states H E ((++()x are the final outputs of the w-th layer. If the next layer is Cluster-Former, the output hidden states in this layer Ho+ will be saved into memory bank for computing the cluster centroids.
3.2 CLUSTER-FORMET LAYER
We introduce Cluster-Former layer to add global representational power to Transformer beyond sliding windows. An in-depth visualization of the layer is illus- trated in Figure
Algorithm 1 Cluster Centroids Update
Initialize Memory Queue()
Centroi GRTCHANTOOnS(RRaddmmWoe Vector)
3:
4: function TrAutt)))
The input of the Cluster-Former layer comes from the hidden states of the prior layer (in our case a Sliding-Window layer). After merging the overlaps be- tween sequence chunks, the input of this layer is defined as:
5: for i 2, IterationNum do
States Sliding- Transfomer((nguutt]]]
7: Memozy St
8:
while len(Memo ry) >> M do Memory-pop()
9:
10:
end while
11:
if Cussterrppaaterrrquuenyyy == then Centroids = GETCENTROIDS(Memoos)) end if
Hº [0 q + m|::..: H: ml]
12:
(4)
13:
where H +a) is the hidden
14: Clusters cluster States Centroids
states to cluster, x the number of tokens
15:
States Foster
in the context.
16: end for
17: end function
As the hidden states with larger cosine
18:
similarity are more likely to have higher attention weights, we build sparse self-
19:
function GurVCaanrooD(HHlddeenttttee))
20:
Centroids = K-Meen((iiddenstatess))
attention only on the hidden states in the
21:
Outputs = List()
same cluster. In this work, we use K- Means as the chosen clustering method for simplicity. More advanced cluster- ing algorithms have the potential of yield- ing better performance. Since running K- Means on the fly in each training iteration
22:
Outputs[I] = Centroids([]
23:
for - 2, 3 ClusterNum do
Outputa(i] centroid from Centroide da
24:
that closest to Outputs(i not Outputs
25: end for
computationally expensive, decide re-compute the cluster centroids with low frequency (every epoch few epochs).
26: return Outputs
27: end function
4

---

Under review as a conference paper at ICLR 2021
In addition, to avoid dramatic changes in the cluster centroids due to limited hidden state inputs, we maintain a memory bank for the most recent hidden states. The entire procedure is depicted directly use them for hidden state
in Algorithm|l []] Once compute the cluster centroids, clustering as follows:
(C H C*
V argmax
(5)
where C E _xxd are the cluster centroids for layer n, and p is the pre-defined number of clusters. The function argmax(() performs the last dimension and assigns all the input hidden states into different clusters based on the max value of cosine similarity between the hidden states and cluster centroids. v E [R([[//m]+3) +x) is the assigned cluster IDs of all the input hidden states.
Since the number of hidden states in different clusters can vary substantially, padding them to the maximum length for Transformer training will significantly increase the computational time. To make the extraction of global context more efficient, greedily pick the cluster centroids based on the nearest neighbour (measured by cosine similarity) as shown in the function GETCENTROIDS in Algorithm|| [ Thus, the hidden states with similar cluster IDs are also close each other. Then, we can directly sort the cluster IDs of hidden states and uniformly chunk the hidden states (same window size and stride m):
u" argsort(v"), a = =" [mk: m(k + 1)],
- [a]
(6)
where the function argsort(-) is obtain the indexes of input values sorted in order (same values sorted by the corresponding position of hidden states). a E I2mh is the chunked indexes of the hidden states, Eg E Ixd is the k-th clustered hidden states, and we will run Transformer on top of it to build the connection beyond the words in the initial sliding window follows:
E Transformer(E
After updating the hidden states, we map them back the order before clustering:
H=+1 [E ET 3.... Ex+1 ],
a" = [a]: aj axl
(8)
a") = clone(H
where H is the final output hidden state of this layer and has the same word order as the input H In experiments, stack these types of layer interchangeably capture both global and local context efficiently.
4 EXPERIMENTS
#train
#test
med
max
4.1 DATASETS
Quasar-T SearchQA
29k
3k
2.8k
8.2k
100k
27k
2.5k
4.9k
We evaluate our proposed approach on multiple question answering benchmarks. The statistics of all the datasets are summarized in T
NQ
292k
8k
6.3k
128k
Table Statistics of Question Answering datasets. #train: number of questions in the train- ing set. #test: number of questions in the test set. med: median length of the context. max: max length the context.
Quasar-T (Dhingra al. 2017): The goal of this task is to answer open-domain ques- tions from Trivia Challenge. All the passages harvested through information retrieval can be used to answer questions. The task requires the model to generate answers in phrases. The evaluation metric on this dataset is based on Exact Match and F1 score of the bag-of of- words matching. Our evaluation too fooe from the SQuAD dataset.
SearchQA Dunnn et al. 2017;: The setting of this dataset is the same as Quasar-Tr T, except that the questions are sourced from Jeopardy! instead.
htttss//gihuubcoom////ingggguuuu httpp://aajpukaaagiiinnnsSSSSDpp htaps://giiiahccommmn//ldddlrrrr
5

---

Under review as a conference paper at ICLR 2021
Natural Questions Kwwiakowssii et al., 2019): This task aims to answer questions based on given Wikipedia document, and has two settings. (i) Long answer: select a paragraph that can answer the question based on the Wikipedia document if any. (ti) Short answer: extract an answer phrase from the document if the document contains the answer. As the given document may not contain answer, we can either predict answer or predict answer. The evaluation metric this dataset is the Fl score, where true positives are exactly correct answers, false positives are incorrect answer predictions, and false negatives are incorrect "no answer" predictions. As the test set is hidden, we split 5% of the training set for validation, and use the original validation set for testing. We use the official tool from the dataset to evaluate our models. We also submit our best model to the leaderboard.
4.2 IMPLEMENTATION DETAILS
All the models are trained on Nvidia V100 GPUs. For clustering, we adopt "Yinyang kmeans "(Ding et al. 2015 which takes less than 5 seconds for clustering in all of our experi- ment settings. We set the memory size for clustering M = 100, 000 in Algorithm [] We use cluster centroids that perform the best on the validation set for test set experiments. We initialize our mod- els with RoBERTa-large (Liu et al. (019). As the number of position embeddings of RoBERTa is limited to 512, we cannot assign different position embeddings the same position embeddings to each chunked sequence. The majority of our model is made up of Sliding-Window posed Cluster-Former Layer in layers 15 and 20 to further capture long-range information. We set the sliding window size 1 to 256, stride m to 224, and change the number of clusters in (64, 256, 512} to analyze its impact the final performance. We prepend special token to the beginning of all the given/retrieved paragraphs and directly concatenate all the paragraphs as the final context sequence. Due to memory constraints, we set the max length to be 5000 during training and 10000 during inference. During dataset finetuning, we use Adam (Kingma & Ba, 2015)) to optimize the model. We set warm-up updates 2,220, maximal updates to 22,200, learning rate x 10-5 and batch size to 160. We tune dropout rate from {0.1, 0. 15, 0.2) for all methonds including baselines and report the best results. The model converges in one day for all the QA datasets.
all tokens. Instead, we assign
Window Layers, as the local information essential for QA tasks. We adopt the pro-
For Q and SearchQA, we predict the start and end positions of the answer. For Natural Question, we first identify whether the question has short/long answers or not based on the mean values of the first hidden state of all the chunked sequences, K number of chunks and N is the number of layers. If answerable, we rank all the candidates for long answer selection, and predict the start and end positions of short answers. Our model submitted to Natural Question Leaderboard ensembled 3 models with 512 clusters, and only these models are firstly trained on SQuAD2.0 and then finetuned on Natural Question dataset.
1 Σx= H [0] where K is the
4.3 BASELINE
We compare our models with several strong baselines, including:
R3 (Wang et al. 2018) proposes to use reinforcement learning to jointly train passage ranker and reader. DS-QA (in et al. 2018) proposes to first use paragraph selection filter the noisy data and then trained model on denoised data. Multi-passage BERT (Wang et al.) 2019) proposes to filter the passages and then merge multiple useful passages into one sequence, which can be encoded by BERT. DrQA (Chen et al. 2017) makes use of attention mechanism across the question and the document for answer phrase extraction. DecAtt and DocReader (Kwiatkowski et al.) 2019) is based on a pipeline approach that first uses a simpler model to select long answers and then reading comprehension model to extract short answers from the long answers. BERT joint (Alberti et al., 2019) jointly trains short and long answer extraction in single model rather than using pipeline approach. BERT ww +SQuAD2 (Pan et al. 2019) makes use of multi-task learning to further boost performance. RikiNet- reader and multi-level cascaded answer predictor. BigBird-ETC (Zaheer et al., (020) makes use of sparse attention mechanism to encode long sequences.
(Liu et al. 2020) proposes dynamic paragraph dual-attention

---

Under review as a conference paper at ICLR 2021
Quasar-T EM/F1
SearchQA
NQ(long) F1
NQ(short) F1
EM/FI
R3 (Wang et al. 2018
35.3/41.7
49.0/55.3
DECAPROP Tay et al.
2018
38.6/46.9
62.2/70.8
DS-QA (Lin
2018
42.2/49.3
58.8/64.5
Multi-passage BERT Wang et al.
2019
51.1/59.1
65.1/70.7
DIQA (Chen et al. 2017)
37.7/44.5
41.9/48.7
46.1
35.7
DecAtt DocKeader Kwiatkowski et al. 2019
54.8
31.4
BERT Joint Allbrtt et al. 2019)
64.7
52.7
BERT wmm +SQAAD2 an al. 2019
68.2
57.2
(Liu et al.
2020
75.3
59.3
Sliding Window
52.9/62.8
65.8/73.2
75.3
56.4
Sparse Atlention CChidd cl al. 2019
52.1/62.0
64.7/71.7
74.5
56.1
Locality -Senstt-Sensitive Hashing Kitaay et al.
2020
53.2/62.9
66.0/73.5
75.5
56.4
Cluster-Formes (#C=64)
53.3/63.3
67.0/74.2
76.3
56.7
Muster-Former (#C=256)
53.6/63.5
67.5/74.5
76.3
Cluster-Formee (#C=512)
54.0/63.9
68.0/75.1
76.5
57.1
Table 2: Results on Quasar-T, SearchQA test sets and NQ dev set.
#C: number of clusters.
Long Answer Precision
Short Answer Precision
Recall
F1
Recall
BigBird-ETTC-arre (Zaheer et al.
2020
77.8
77.5
78.1
57.9
63.7
53.0
RikiNet (Liu et al. 2020)
76.1
78.1
74.2
61.3
67.6
56.1
Cluster-Former (Ours)
78.0
78.5
77.5
60.9
62.1
59.8
Table 3: Results Natural Questions (NQ) leaderboard (test set). We show two published results here from over 40 submissions. And our model achieves No.1 for long answer and No.4 for short answer.
We also c--implement several strong baselines which have been applied to process long context in question answering tasks:
Sliding Window:
The original method is fully made up of Sliding-Window Window Layers and can only attend to local information.
To make a fair comparison among different methods on long-range information collection, we replace several layers of this sliding window bascline with Sparse Attention, Locality-Sensitive Hashing, and Cluster-Former.
Sparse Attention (Child et al. 2019): This method replaces several layers in the previous baseline by training Transformer layer across sequences on pre-selected positions. We run this sparse Transformer on all the hidden states in the same position across sequences, so that the output of sparse Transformer can merge the information from different sequences.
Locality-Sensitie Hashing (Kitaev al.) 2020): This method hashes hidden states into different buckets determined by randomly-initialin hashing vectors. A Transformer layer is then applied across buckets to build Sparse Attention across the whole sequence. Note that this method cannot be directly used for question answering without adding Sliding- Window layer, our QA model is initialized by RoBERTa that only has 512 position embeddings.
Blding-Winndw
4.4 EXPERIMENTAL RESULTS
Slate-of-the-Ane Results QA Table and show that proposed method outperforms several strong baselines, thanks to its ability to encode both local and global information. Cluster-Former with 512 clusters achieves new state-of-the-ar results Quasar-T, SearchQA and Natural Question (long answer).
Effect of Cluster-Former We also test the ability of Cluster-Former modeling long- rangerage dependencies. Note that Sparse Attention (Child et al.] 2019) and Locality-Sensite Hash- ing (Kitaev al. 2020) have never been tested question answering tasks with long

---

Under review as a conference paper at ICLR 2021
Question
Where did the underground railroad start and finish The Underground Railroad by artist Charles T. Webber 1893 Date Late 1700s 1865 Location Northern United States with routes to Canada, Mcxico
Context
Special token
<>>
<< Island island in the colonics city <>>><>><<>><>>>>>> With in the in did start and finish 1893 Date 1700 1865 Location Participants Outcome Deaths 19 1763 the the the .... to .... the American runaway slaves of free stales the ... it to the the Canada Mexico Canada is applied Florida Spanish Railroad Railroad Railroad
Time
Stopwords
Entity
Positions
49, 50, 51, 52, 53, 54, 55, 115, 116, 168, 273, 394, .... 6022, 6040, 6042, 6060, 6094, 6095
Table 6: An example from Natural Question dataset. The rows in the middle section show the corresponding words of the clustered hidden states, and the bottom row shows the positions of the clustered hidden states. "
" refers start token of long answer candidate.
text. For fair comparison,
the layers 15 and 20 either Sparse Attention, Locality- Sensitive Hashing or our Cluster-Former, and the left layers are Sliding Window layers.
As shown, Sparse Attention performs worse than our Cluster-Former. The loss may come
8
55.7/65.0
55.6/64.4
54.7/64.3
55,4/64.6
from the noise introduced by pre-selected po-
12
55.1/64.9
55.8/65.0
56.1/65,4
55.4/64.6
sitions, the corresponding words of which may not be related. We set the number of hashing vectors Locality-Sensithe to 64, the same as the number of clusters in Former.Formmrr LSH outperforms the base- line slightly QA and consistently underper- forms our Cluster-Former (#C=64). Overall, Cluster-Former performs the best.
16
55.6/65.0
55.2/64.7
1/.4/
54.8/64.1
20
54.8/64.2
55.4/64.8
15.1/64.6
Hashing (LSSH)
Table 4: Experiments on Quasar-T dev dataset.
a E (3,4,5,6) and b E {8. 12, 16, 20]. if the layer number % = 0 and >= b, we set it as
Cluster-Former Layer, otherwise Sliding Window Layer.
Effect of Number of Cluster Centroids We also test the effect of different numbers of clus- ter centroids (C) on model performance. We observe that the model with 512 clusters works significantly better than the model with 64 clus- ters on most of the tasks. However, for Natural Questions Long Answer setting, the improve- ment is marginal. As we mainly rely on the hidden state of special tokens "
" for long answer selection, and the same tokens can assigned into same chunk more easily even with a smaller number of clusters.
Wikitext ppl
Enwik8
bpc
Sliding window Sparse Attention Locality-Sensitiv Hashing
20.8
1.34
20.5
1.29
20.8
1.33
Cluster- (#C==4)
20.5
1.28
Cluster-Former (#C=256)
20.3
1.24
Cluster-Former (#C=512)
20.2
1.22
Table 5: Results on Language Modeling. number of clusters; Wikitext: Wikitext-103.
#C:
Selection of Cluster-Former Layers We also have analysis which layers are better used for Cluster-Former layer. As shown in Table 4 we conduct hyper-parameter search. And find that get better performance with at least one worst results come from only one Cluster-Formet layer in the layer of 22 or 23.
layers in the middle layer (8- 16). The
Language Modeling Although we focus QA tasks in this paper, demonstrate the versatil- ity of Cluster-Former, we further conduct additional experiments on language modeling using the Wikitext- 103 (Merity et al. (017) and Enwik8 (Mahoney 2011) benchmarks. Implementation de- tails are provided in Appendix. As shown in Table Cluster-Former outperforms strong state-of- the-art baselines.
4.5 QUALITATIVE ANALYSIS
We perform qualitative analysis on how the hidden states are clustered, by visualizing the corre- sponding words and positions of the hidden states in Table X From the first row, we can see that the special tokens "
> tend to belong the same cluster. Note that "
" is the start token of each long answer candidate, and its hidden state is used for final long answer selection. Therefore, Transformer this cluster compare across the candidates make the final prediction.
8

---

Under review as a conference paper at ICLR 2021
We further observe that the same types of token more likely to appear in the same cluster. For example, words from the second row to the forth row cover the topics of time, stopwords, and organization & geopolitical entities.
Finally, we randomly sample a cluster and list the positions clustered hidden states the last row of the table. We find that states in long distance, such the 50-th and 6060-th states (over 6000 tokens apart), can be in one cluster, which demonstrates the ability of Cluster-Formet long-range dependencies. Further, observe that states tend to cluster in phrases. For example, we see consecutive positions such as "49, 50, 51, 52, 53, 54, 55", which likely results from the sliding-windee encoding.
detecting
CONCLUSION
In this paper, we present Cluster-Former, new method encode global information for long se- quences. We achieve new state of the art on three question answering datasets: Quasar-Ta T, SearchQA, and Natural Questions. Further, we observe that larger number of clusters in Cluster-Former can lead to better performance on question answering tasks. Cluster-Formed is generic approach, and believe that can benefit other NLP tasks that rely on long-range dependencies as well.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Joshua Ainslie, Santiago Ontanon, Chris Alberti, Philip Pham, Anirudh Ravula, and Sumit Sang- hai. Etc: Encoding long and structured data in transformers. In Empirical Methods in Natural Language Processing (EMNLP), 2020.
Chris Alberti, Kenton Lee, and Michael Collins. A bert baseline for the natural questions. arXiv preprint arXiv:1901.08634, 2019.
Akari Asai, Kazuma Hashimoto, Hannaneh Hajishirzi, Richard Socher, and Caiming Xiong. Learn- ing to retrieve reasoning paths over wikipedia graph for question answering. In International Conference on Learning Representations (ICLR), 2020.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05/55 2020.
Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. Reading Wikipedia to answer open- domain questions. Association for Computational Linguistics (ACL), 2017.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint
2019.
Eunsol Choi, Daniel Hewlett, Jakob Uszkoreit, Illia Polosukhin, Alexandre Lacoste, and Jonathan Berant. Coarse-to- corrse-to-fine question answering for long documents. In Association for Computational Linguistics (ACL), 2017.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Jared Davis, Tamas Sarlos, David Belanger, Lucy Colwell, and Adrian Weller. Masked language modeling for pro- teins via linearly scalable long-context transformers. arXiv preprint vrXiv:2006.03555 2020.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the Associ- ation for Computational Linguistics (NAACL), 2019.
Bhuwan Dhingra, Kathryn Mazaitis, and William W Cohen. Quasar: Datasets for question answer- ing by search and reading. arXiv preprint 170.xv:70.0039// 2017.
Yufei Ding, Yue Zhao, Xipeng Shen, Madanlal Musuvathi, and Todd Mytkowicz. Yinyang k-means: A drop-in replacement of the classic k-means with consistent speedup. In International conference on machine learning (ICML), 2015.
Matthew Dunn, Levent Sagun, Mike Higgins, V Ugur Guney, Volkan Cirik, and Kyunghyun Cho. Searchqa: A new q&a dataset augmented with context from search engine. arXiv preprint 17Xiv:1704.05579, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 1997.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. arXiv preprini arXiv:2006. 16236. 2020.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations (ICLR), 2020.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. Natural questions: benchmark for question answering research. Transactions of the Association for Computational Linguistics (TACL)) 2019.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Sori- cut. Albert: A lite bert for self- self-supervised learning of language representations. In International Conference Learning Representations (ICLR), 2020.
10

---

Under review as a conference paper at ICLR 2021
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. Bart: Denoising sequence-to -eeenceet--eeuence pre-training for natural language generation, translation, and comprchension. In Association for Computa- tional Linguistics (ACI.), 2019.
Yankai Lin, Haozhe Ji, Zhiyuan Liu, and Maosong Sun. Denoising distantly supervised open- domain question answering. In Association for Computational Linguistics (ACL), 2018.
Dayiheng Liu, Yeyun Gong, Jie Fu, Yu Yan, Jiusheng Chen, Daxin Jiang, Jiancheng Lv, and Nan Duan. Rikinet: Reading wikipedia pages for natural question answering. In Association for Computational Linguistics (ACI.), 2020.
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 1907.1190.1110 2019.
Matt Mahoney. Large text compression benchmark. URL: http://www. mattmahoney, net/text/text.
html, 2011.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference on Learning Representations (ICLR), 2017.
Lin Pan, Rishav Chakravarti, Anthony Ferritto, Michael Glass, Alfio Gliozzo, Salim Roukos, Radu Florian, and Avirup Sil. Frustratingly easy natural question answering. arXiv preprint arXiv:1909.05286. 2019.
Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, and Timothy P Lillicrap. Compressive transformers for long-range sequence modelling. In International Conference on Learning Rep- resentations (ICLR), 2019.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-bass sparse attention with routing transformers. Transactions of the Association for Computational Linguis- tics (TACL), 2020.
Yi Tay, Anh Tuan Luu, Siu Cheung Hui, and Jian Su. Densely connected attention propagation for reading comprehension. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng. Synthesizer: Rethinking self-attention in transformer models. arXiv preprint arXiv:2005. 00743, 2020a.
Yi Tay, Dara Bahri, Liu Yang. Donald Metzler, and Da-Cheng Juan. Sparse sinkhorn attention. arXiv preprint arXiv:2002. 1296, 2020b.
Yi Tay, Mostafa Dehghani. Dara Bahri, and Donald Metzler. Efficient transformers: A survey, arXiv preprint arXiv:2009. 06732, 2020c.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems (NeurIPS), 2017.
Shuohang Wang, Mo Yu, Xiaoxiao Guo, Zhiguo Wang. Tim Klinger, Wei Zhang, Shiyu Chang, Gerry Tesauro, Bowen Zhou, and Jing Jiang. R3: Reinforced ranker-reader for open-domain question answering. In AAAI Conference on Artificial Intelligence (AAAI), 2018.
Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.0477 2020.
Zhiguo Wang, Patrick Ng, Xiaofei Ma, Ramesh Nallapati, and Bing Xiang. Multi-passage bert: A globally normalized bert model for open-domain question answering. In Empirical Methods in Natural Language Processing (EMNLP). 2019.
Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. arXiv preprint MwXiv:2007.14066 2020.
Junru Zhou and Hai Zhao. Head-driven phrase structure grammar parsing on penn treebank. In Association for Computational Linguistics (ACI.), 2019.


Reviews:
[{"review_id": "vewx7DKARNR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary:**\n\nThis paper introduces the ClusterFormer, a transformer architecture that scales gracefully to long sequences by restricting pairwise attention by the cluster assignments of the hidden states of input tokens. The paper presents strong empirical results on question answering benchmark datasets outperform state-of-the-art approaches as well as strong baselines introduced by the authors. \n\nSummary of review: Strong empirical results on question answering datasets; interesting data-driven efficient transformer model; further clarification on relationship to related work needed; experimental results would be stronger with more analysis of the proposed method. \n\n**Strengths:**\n\nThe all pairs self attention component of transformers limits their scalability to long sequences. This paper presents a model that is reduces the complexity by grouping related tokens into clusters, such that self-attention is applied only within each cluster. In particular, a long sequence is first encoded using a sliding window style approach, then these sliding window representations are clustered and the resulting cluster memberships determine the sparsity for the remaining layers of the transformer. The approach appears to work quite well on question answering datasets for which the approach achieves state-of-the-art results on three datasets. \n\nThe paper is well written and the presentation is very clear. \n\n\n**Weaknesses:**\n\n**Relationship to related work:** The proposed approach appears to share many similarities to the Routing Transformer (Roy et al, 2020). While both approaches from this year, I think that it would be important to present the similarities and differences of the two approaches (i.e. sliding windows, way k-means centers are updated, etc) clearly in this paper. Other related, though more distinct, ideas are used in the inducing point based variant of Set Transformers (Lee et al, 2019). \n\n**Empirical Analysis of Scaling to Long Sequences:** I think the presentation of the paper would be improved if the authors demonstrated just how much computation is saved by using these sparse, cluster-based attention layers. It would also improve the presentation to compare the efficiency of the proposed approach to other methods at varying input length sizes. Similarly, it would be interesting to show the performance of the proposed approach compared to baselines for varying maximum sequence lengths. It would further be interesting to investigate the cluster centers discovered by the method, what they represent, and how they change over time. This would be particularly important to analyze how the model picks up information across long sequences (i.e., showing that clusters are not made up of tokens from the same sliding window). \n\n**Details of k-means**: Apologies if I've missed this, but is anything done to ensure that the cluster sizes produced by k-means are relatively balanced? The skew of these sizes will directly impact the scalability of the method? Further, while it is implied by the method/text, it would be nice to describe how the gradient is calculated for this hard cluster assignment. \n\n\nAurko Roy, Mohammad Saffar, Ashish Vaswani, David Grangier. Efficient Content-Based Sparse Attention with Routing Transformers. First posted March 2020. https://arxiv.org/abs/2003.05997\n\nJuho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek, Seungjin Choi, Yee Whye The. Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks. ICML 2019. \nhttp://proceedings.mlr.press/v97/lee19d/lee19d.pdf\n\n**Questions for the authors:**\n\n• Please see questions in the details of k-means section.", "extra_scores": {}, "extra_text": {}}, {"review_id": "cc1VP6NTky", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes ClusterFormer to address the problem of quadratic compute requirements of the attention mechanism in a Transformer model. To this end this paper proposes to combine local attention to promote local consistency and proposes KMeans clustering to gather global information for every token. The paper establishes strong results on the long form question answering task of Natural Questions in an extractive setup, with it getting the leaderboard position ahead of ETC-large. While the idea in the paper is natural and the results on NQ are strong, unfortunately the idea in the paper is not new and has already been introduced in the work \"Efficient Content-based Sparse Attention with Routing Transformers\" [1, 2] which the authors fail to cite or credit. Therefore, I recommend rejection.\n\n\nReferences:\n\n[1] https://openreview.net/forum?id=B1gjs6EtDr\n\n[2] https://arxiv.org/abs/2003.05997\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "a4vin18Te1l", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper describes a method to handle long documents for question answering. Most existing approaches use a sliding window approach, without communication between different sliding windows. Instead, they propose an approach that clusters individual vectors, and allows communication (attention) among the locations in the same cluster. I am not sure about the intuition behind this -- why would communicate between similar vectors more efficient than dissimilar or randomly chosen vectors? Would the performance improve if you use a better clustering algorithm? The authors do not provide much intuition on this either. \n\nI have a concern about comparison with locality sensitive hashing. The number of buckets used in locality sensitive hashing was 64. And it's clear that having more clusters help. And the comparison between #C=64 Cluster Former and Locality Sensitive Hashing is marginal -- less than one point on all measures. I am not sure the results are strong enough to support that clustering is better than random assignments. For a valid comparison, they should report the results with locality-sensitive hashing and 512 buckets. \n\nThe paper evaluates on three QA datasets, as long as experiments on perplexity for language modeling and shows promising performances. \n\nSome clarifying questions:\n1) could you specify a bit more on how do \"classify the mean values of the first hidden state of all the chunked sequences to identify whether the question has short / long answers or not\"?\n2) I'm a bit confused with the experimental set up. For NQ, what's the numbers in Table 2? Is it on the dev set, and the numbers on Table 3 are on the test set? Please make it clear. \n3) would this work on a really lengthy QA dataset such as narrativeQA?\n4) From Table 2, it seems the more the number of clusters, the better the performance.  Why do you stop at 512? Is this have something to do with computational efficiency? \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7T_ERn5G-Hx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nCluster-former is the latest proposal for enabling transformers to deal with long input sequences. Such sequences are particularly problematic for problems like question answering, QA, (or summarization), where the context can be arbitrarily long, and effectively open-ended when the setup includes a context retrieval component (e.g., as in OpenQA). Cluster-Former combines local information by encoding sequence chunks separately with a sliding window, then injects clustering layers, that use k-means to compute centroids to cluster hidden states and capture global information. The approach yields state-of-the-art, and top-of-leaderboard, results on Natural Questions (long answers). \n\nThis is great solid work, showing how clustering can be designed, implemented and  used successfully, to capture long distance dependencies in sparsified self-attention models. This is a concrete and useful contribution in itself for the large community working on this type of architecture and related problems. At the same time the approach involves quite a bit of complexity which makes one wonder if the baselines could be more competitive given a comparable amount of fine tuning. At the same time, competitive solutions of different nature (generative) are being proposed that pose a concrete challenge to this type of architecture, which are not evaluated, but should be at least discussed.\n\nPros\n- Solid proof of concept and reference to successfully implementing clustering in sparse attention. \n- Strong empirical results, particularly the Natural Questions’ leaderboard for long answers.\n- Impressive amount of technical work, also with respect to reproducing results with other systems.\n- Notwithstanding the amount of work in this area, literature review and comparison seems adequate but I might have missed something.\n- Some qualitative analysis: which could be extended and articulated, in particular it would be interesting to understand where the long distance information helps; e.g., vs the sliding window approach and particularly vs LSH.\n\nCons\n- One of the arguments for the paper is that it is not clear if related methods, like Reformer, can generalize to long sequences. However, in the evaluated implementation (Table 2) LSH is not that much worse than k-means. In fact, even just the sliding window alone seems surprisingly competitive on all QA tasks. While being much simpler. I find the authors’ effort to compare with all these related methods truly commendable. It seems natural to wonder how much more fine-tuning has gone into Cluster-Former compared to the simpler baselines, given its additional complexity. It would be important to discuss this aspect in more detail.\n- Given the recent work of generative readers: https://arxiv.org/abs/2005.11401, and particularly Izacard & Grave, (FID, https://arxiv.org/pdf/2007.01282.pdf) it seems unclear that direct encoding is the only, or the best, option for dealing with long sequences, at least for QA. In particular, FID seems attractive due to its simplicity and capacity (about twice as much as Cluster-Former it seems). The authors should discuss this work. It would be ideal, at some point, to compare directly by evaluating on OpenQA-NQ or by other means.\n\nDetailed feedback\n- Pleas define x, from x\\times d, right below Eq(1). Num tokens in context?\n- Scaler value/scalar value?\n- It would be great to explain Eq(2) step by step for clarity.\n- What is the effect of the overlapping content size m-l? And in general of parameters l and m. In particular, could this affect positively the performance of the simpler sliding window model?\n- Why using cluster layers at only 2 fixed depths? How does this parameter affect results?\n- The max length is constrained to 5k (10k test) due to memory constraints, can this be improved, how?\n- How long did it take to train the leaderboard (NQ) entry system?\n- Unclear what table 2 evaluates on, e.g., for NQ, is this on the dev set? Or a fraction of it?\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper attempts to make transformers more scalable for longer sequences. In this regards, authors propose a clustering-based attention mechanism, where only tokens attends to other tokens in the same cluster. This design reduces memory requirements and allows more information mixing than simple local windows. Using the proposed approach, new state-of-the-art performance is obtained on Natural Questions long answer, although marginal. However, reviewers raised numerous concerns. First, the novelty of the paper compared to prior work like reformer or routing transformer which also conceptually does clustering is not resolved. Second, the claim that k-means yields a more balanced/stable clustering than LSH is not well established. Finally, why clustering, i.e. attention between similar vectors is better than dissimilar or randomly chosen vectors or does is it even as expressive is not clear. Thus, unfortunately I cannot recommend an acceptance of the paper in its current form to ICLR.
Decision: Reject