Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes Skyformer a new xformer variant that uses Gaussian kernels and the Nystorm method. 
main_review: The idea does sound interesting and novel, the experiments on long range arena look satisfactory. 

Results look borderline but overall better than some of the existing baselines while being faster/less memory hungry.

The improvements of Nystromformer is that: "Nyströmformer blindly applies the Nyström method to a non102 PSD matrix, and thus fails to ultize the full potential of Nyström method." the authors solve this by "instead lifting the kernelized attention score matrix into a large PSD
matrix which contains the target non-PSD matrix as its off-diagonal block."

I have some minor concerns.

1) I find that the intro is an over nag. The paper starts off by telling us how expensive GPT-3 training is (or how long it takes). I don't think the proposed method solves this problem. I would advise the authors to keep the exposition short. Most reviewers in the space know the problems with Transformers and the quadratic complexity problem.
2) What happened to the image CIFAR task on LRA? Why was that omitted? 
3) A nit but why is the model called Skyformer? What does SKY mean here?

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a method (Skyformer) to apply Nystrom approximation to the attention matrix. It embeds the attention matrix inside a larger PSD matrix (unlike Nystromformer), allowing Nystrom method to work well. Theoretical and empirical validation shows that the method is competitive with other forms of efficient attention (e.g. BigBird, Performer, Reformer).
main_review: Strengths:
1. The paper is well-written and easy to understand. Section 4 provides valuable intuition, and I enjoyed reading it.
2. The method can significantly speed up attention computation, which is necessary for scaling to longer sequences.
3. The method is novel to the best of my knowledge.

Weaknesses:
1. Limitation of application: it's not clear to me how widely the proposed method can be apply, as there's no discussion of its limitations. I'm not sure which conditions will allow it to work well. 
2. The empirical validation is not sufficient. As the paper proposes a new variant of attention (based on Gaussian kernel), one has to demonstrate this works on different tasks (e.g. language modeling, translation, etc.), not just classification as in the long-range arena benchmark.

Questions:
1. Section 4.2, instead of the block matrix [[phi(Q, Q), phi(Q, K)], [phi(K, Q), phi(K, K)]], would it also work to embed phi(Q, K) in the block matrix [[0, phi(Q, K)], [phi(K, Q), 0]]? I think this matrix is also PSD, and it has a lot of zeros so it might save some computation.
2. Figure 2: (a) Isn't Skyformer approximating a different matrix (the matrix C instead of the attention matrix)? Why would Skyformer have low approximation error wrt the attention matrix here?
(b) Maybe Performer is having problem because it also tries to approximate the normalization constant D^{-1}, which Skyformer does not do. Would that make this an unfair comparison, because Skyformer is approximating a different matrix and Performer is doing more work to approximate the denominator?

Comments:
- Line 129, (D_Q)_ii = ||q_i||^2 / sqrt(p) should be (D_Q)_ii = exp(-||q_i||^2 / sqrt(p)).
- Equation after line 177 equation, this definition is for the matrix C, not for Kernelized-Attention(Q, K, V). I assume kernelized-attention is the product of C and V.
- Line 178, (D_Q)_ii = ||q_i||^2 / sqrt(p) should be (D_Q)_ii = exp(-||q_i||^2 / sqrt(p)).

============== Post-rebuttal

Thank you for the response to my questions. That has helped clarified some of my misunderstanding of the method. 

I would still encourage the authors to validate the method on a wider variety of applications to make a stronger case.

I've increased my rating.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The paper presents an alternative approach to attention in the Transformer. There are two modeling contributions:

1. Kernelized attention that omits the typical normalization term used for softmax attention.
2. A Nystrom method approach that allows efficiently approximating the output of the attention mechanism

The contributions also include theoretical results regarding the accuracy of the Nystrom approximation, and experimental results showing better convergence, higher accuracy, and medium efficiency gains from the approach.

Below I summarize my understanding/takeaways from the two key methods; please correct me in the author response if these are inaccurate:
1. As I understand it, "kernelized attention" mean that target keys don't compete with each other, the only thing that matters is their distance to the query. In standard softmax attention, suppose that all key vectors are orthogonal to a query vector -- in that case, attention would weigh all values uniformly. In kernelized attention, on the other hand, if key vectors are all far away from the query vector, then all value vectors would be attended to with near-zero weight.
2. The Nystrom approximation involves sampling some queries and keys, and then computing kernels between all pairs. But whereas Nystromformer computes similarity for query+key pairs only, the proposed approach also computes kernels for query+query and key+key pairs as well.
main_review: Overall this is a very solid paper. The methods presented are novel in the context of efficient attention, and they are justified from both a theoretical and experimental standpoint. I particularly appreciate that the error caused by the Nystrom approximation rapidly shrinks as the number of features increases (as shown in Figure 2), and I believe that it should approach zero as the number of features grows to match the length of the sequence. The paper is clear and well-structured, with some minor exceptions noted below. The overall research program of constructing efficient attention variants has gained a lot of interest in the community, and this paper appears to represent significant progress on this research direction.

The paper offers two contributions that are in principle orthogonal: kernelized attention, and the Nystrom approximation. Indeed, kernelized attention (without any approximations) is presented as a standalone ablation. Why about evaluating the Nystrom approximation in isolation? I believe this would just involve taking the proposed Skyformer and re-introducing a $D^{-1}$ normalization term. Does this make sense conceptually, and have the authors tried it in practice?

In terms of writing, the only point where I was confused was Theorem 2, which I still don't understand. Line 222 simultaneously introduces a new scalar lambda, uses a matrix C never previously mentioned in the theorem, and *also* introduces a new concept C-bar. There is just too much happening all at once. It would help to introduce all terms one by one, specify in words what lambda is, and otherwise clarify.

I have some questions regarding the LRA evaluations. First, is there a reason the Image task is omitted? Without an explanation in the text it's possible to interpret this as cherry-picking. Next, Retrieval scores are a full 20 points higher than the LRA paper. Nystromformer has similar results, so I trust that the results presented are correct, but it would be helpful to have a comment in the paper regarding this situation. Finally, Pathfinder scores are actually *lower* than both Tay et al (LRA) and Xiong et al. (Nystromformer). Do you know why this might be?

Overall LRA benchmarking is becoming a bit of a mess, because results from two different papers can't be compared against each other. This situation is not limited to only the present paper, but it's still disappointing because it makes it possible for individual papers to use cherry-picked baselines or poor hyperparameter choices for competing methods, without no easy way to flag it using cross-paper comparisons. I understand that it's hard for any one paper to address systemic benchmarking issues, but the results would certainly be stronger if the authors had a way to mitigate these concerns. If anything a little more discussion to justify the evaluation would help.

Minor
- Why the name Skyformer? I'm just curious, because the naming choice is never discussed in the paper.
- line 27: I would not characterize Reformer as a low-rank approximation, since it can learn full-rank sparsity patterns
- line 77: "By reduce" is ungrammatical
- Equation on line 177: there is no V term on the right side of the equality, so I think this equation isn't quite right
- Figure 1: $K_S^T$ should have shape $d_S$ x $n$
limitations_and_societal_impact: Limitations and impact are adequately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The author proposes a modified Nyström method named Skyformer to approximate the Kernelized Attention. They also provide a theoretical guarantee that the approximation error is small in terms of the spectral norm. Extensive experiments are also conducted to show that Skyformer achieves comparable performance to vanilla self-attention with fewer computational costs.
main_review: The paper is well written and easy to follow. In this paper, A new variant of the Nyström method, Skyformer, is proposed to estimate the Kernelized Attention. Specifically, they expand the original Kernelized Attention to a larger PSD Kernelized Attention and then use the Nyström method to approximate the larger PSD matrix. The theoretical result shows that the complexity of Skyformer is comparable to the complexity of most other efficient transformers. Experiment results also facilitate the author's claim. Although I admire the theoretical contribution of this work, I am worried about the practice of this method since it enlarges the original dimension n to 2n and needs to calculate the inverse of a matrix.
limitations_and_societal_impact: - In Theorem 2, it seems that the sampling size d is independent of the approximate accuracy \epsilon, which is unreasonable.

- For Figure 3, it is not evident that Skyformer is more stable than the other competitors. Does the author have more solid evidence to show that Skyformer is more stable than softmax?

- For Figure 3, It is fairer if the author uses the real-time as X-axis, instead of steps. Also, in Table 2, it seems that Skyformer is not the fastest algorithm.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new form of self-attention for use in transformer models using Gaussian Kernels. They show that the new attention method is comparable in accuracy to traditional softmax self-attention. They then go on to show that kernel based attention can be approximated by taking a Nystrom sketch of the kernel matrix. They give rigorous bounds on the spectral norm of the approximation (assuming that the kernel matrix has a high condition number). 
main_review: Pros
* Proposal of a new attention method (kernel based instead of soft-max)
* Rigorous proof and a proper sketch of the scenarios where one can use Nystrom method. Mathematically founded approximation of the kernel matrix unlike earlier approach (Nystromformer)
* Mostly clear and easy to follow

Cons
* Work seems incremental (Nystromformer is very similar). But the nice thing is the authors do a good job of giving proofs motivating their algorithm

Nit
* Page 1: Introduction: O(n^2) not O(n)
limitations_and_societal_impact: Don't see any potential negative societal impact from reducing resources required for training and inferencing
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors reformulate soft max structure of the self-attention mechanism in Transformers in terms of a Gaussian kernel evaluation. They claim that such a model is empirically stable during training, while allowing the use of various Kernel approximation strategies to improve the quadratic computational complexity. 

In this work, approximation strategy used by the authors is the popular Nyström approximation. However, since the kernel matrix formed between the query and the key matrices is not symmetric (hence not PSD), the Nyström approximation is not directly applicable. The authors propose to form a PSD kernel matrix by first evaluating the Gaussian kernel on the row concatenated  query and key matrices which is PSD, performing the Nyström approximation and then choosing the appropriate block in the resulting matrix.

By adapting an existing theorem [Musco, Musco 17],  the authors claim that such a low-rank approximation of the kernelized attention score is bounded in terms of the relative spectral norm. This is claimed to be due to the observed fast decay of the eigenvalues in an empirical kernel matrix. 

The matrix inversion required for the Nyström approximation, however is a potential issue in terms of numerical stability on a GPU. To circumvent the problem, instead of a standard conjugate gradient method, they use a Schulz type iteration which only uses matrix products, without any floating point divisions.  

Empirical evaluation shows marginal improvement on most tasks on the LRA benchmark, as compared to the naive Nyström approximation [Xiong et al 2021]. However, this is at the cost of relatively larger time and memory usage. 
main_review: Originality: 
The main contribution of this work seems to be the proposed fix to the theoretical issue of Nyström approximation in [Xiong et al 2021]. The rest of the methods used here are priorly known techniques, though presented in a cogent manner. They cite most important of the previous works, however at times their contributions are not clearly delineated from existing methods. For example, the Kernelized attention model (line 54). Reference to [Chormanski et al 2020] for Lemma 1 is also missing. 

Quality: 
The submission is technically sound and correctly applies the Nyström approximation to the kernelized attention mechanism. The claim of good approximation in spectral norm is supported by a stated theorem as well as empirical evaluation. However, the use of Schulz type iteration for inverse may have the unintended consequence of "zero fill in", i.e. the approximate inverse converges to a dense matrix even when the kernel matrix was sparse. 

Clarity: 
The paper is well written and clearly organised. Claims of speed-up though (line 313) might be considered misleading as they direct competitor is the method in [Xiong et al 2021]. The experimental setup is fairly well described with the code being adapted from [Xiong et al 2021]. 

Significance: 
The paper is good contribution towards the development of theoretically sound approximations and reformulations of the self-attention mechanism. 
limitations_and_societal_impact: The authors did not point out or address any potential negative societal impact of their work. Being essentially a theoretical improvement over previous work, there is limited potential for excess social impact as compared to previous work in this field.
review_title: null

Meta-review: The reviewers agree that this is a solid paper re-introducing the Nystrom method for Transformers to address the quadratic space and time complexity of the regular attention module. Thus, it leverages the fruitful area of research on using kernel approaches to improve regular Transformers. The novelty given that Nystrom method was previously used in that context is limited, but the empirical results are strong and furthermore the authors explain in detail approximation guarantees of their method. What is missing is equally detailed analysis of the computational time of the presented method. Nystrom algorithm is in general expensive, but the authors manage to bypass some of its complexities, as showed in the experimental section. More detailed discussion regarding Nystrom method in theory and practice would strengthen the paper.
Decision: Accept (Poster)