Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: 
Cluster-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). 

This 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.

Pros
- Solid proof of concept and reference to successfully implementing clustering in sparse attention. 
- Strong empirical results, particularly the Natural Questions’ leaderboard for long answers.
- Impressive amount of technical work, also with respect to reproducing results with other systems.
- Notwithstanding the amount of work in this area, literature review and comparison seems adequate but I might have missed something.
- 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.

Cons
- 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.
- 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.

Detailed feedback
- Pleas define x, from x\times d, right below Eq(1). Num tokens in context?
- Scaler value/scalar value?
- It would be great to explain Eq(2) step by step for clarity.
- 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?
- Why using cluster layers at only 2 fixed depths? How does this parameter affect results?
- The max length is constrained to 5k (10k test) due to memory constraints, can this be improved, how?
- How long did it take to train the leaderboard (NQ) entry system?
- Unclear what table 2 evaluates on, e.g., for NQ, is this on the dev set? Or a fraction of it?


review_title: Effective attention for long sequences via chunking and clustering. 

final_score: rating: 2: Strong rejection
review_content: 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.


References:

[1] https://openreview.net/forum?id=B1gjs6EtDr

[2] https://arxiv.org/abs/2003.05997

review_title: Good results, but not a new work

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

I 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. 

The paper evaluates on three QA datasets, as long as experiments on perplexity for language modeling and shows promising performances. 

Some clarifying questions:
1) 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"?
2) 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. 
3) would this work on a really lengthy QA dataset such as narrativeQA?
4) 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? 



review_title: Official Review #3

final_score: rating: 6: Marginally above acceptance threshold
review_content: **Summary:**

This 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. 

Summary 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. 

**Strengths:**

The 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. 

The paper is well written and the presentation is very clear. 


**Weaknesses:**

**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). 

**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). 

**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. 


Aurko 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

Juho 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. 
http://proceedings.mlr.press/v97/lee19d/lee19d.pdf

**Questions for the authors:**

• Please see questions in the details of k-means section.
review_title: Strong empirical results for efficient transformer model, questions about related work & analysis. 

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