Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This article presents YOSO, an locality sensitive sampling based attention mechanism for large scale language modeling. 



Strength:
A new idea of applying  locality sensitive sampling to approximate attention matrix in the transformer


Weakness:
1. Comparison of Complexity: [1] presents the complexity of different efficient transformers. For linformer[2], the time and memory complexity is O(nk). Is there any justification of LSH sampling equipped YOSO with complexity more than O(nm\tau log(d)+nmd)?
2.Experiments: YOSO takes linformer as baselines. However, the pre-training experiment part does not provide steps vs ppl of linformer with YOSO in Figure 4. What is the comparison result of YOSO with linformer on iteration wise convergence? Also, linformer demonstrates better accuracy in downstream tasks such as SST-2. Is there any comparison to an explanation that can analyze this difference in performance?
3.Efficiency: YOSO demonstrates an advantage over linformer and longformer in memory and runtime. However, is there any analysis on why YOSO achieves this superiority with higher complexities? Are there any system-level advantages that YOSO can show?

Some discussions: 
Reformer[3] design an attention mechanism that computations are held in the neighbor tokens inside the hash buckets. YOSO also uses hash based sampling to compute attention via neighbor tokens that have high collision probability. On the other hand, linformer introduces a more global view for attention by the low rank projection. Is there any analysis of the local vs global intuition?

[1]Efficient Transformers: A Survey https://arxiv.org/pdf/2009.06732.pdf

[2]Linformer: Self-Attention with Linear Complexity https://arxiv.org/abs/2006.04768

[3] Reformer: The Efficient Transformer https://arxiv.org/abs/2001.04451
review_title: Attention by LSH sampling

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper tries to improve the efficiency of (multi-head) self-attention by reducing the computational complexity from a quadratic one to a linear one. The authors propose to use Bernoulli sampling to approximate the self-attention's softmax distribution through importance sampling via LSH, which makes a linear cost self-attention possible. 

Pros:
1. This paper provides a thorough solution of how to accelerate self-attention via an approximation by Bernoulli sampling and LSH. 
2. The experiments show that the proposed approach could achieve considerable speedup while preserving model performance. 

Cons:
1. The authors should give a more direct comparison with an important related work the reformer, which also uses LSH to speedup the computation of attention. 
2. The experiments were mainly conducted on MLM on GLUE, which lacks generalization among tasks. Adding more tasks such as MT or autoregressive/causal LM would make the experimental part more solid and convincing. 



---------
Minors:
- Fig 2, 3 and Tab 1 are not cross-refed in the main body
- Format of citation: seems all of the citations are of this format - authors (year), which is not correct when citations do not act as subjective of objective in the sentence. Please check the format guideline.

review_title: Review

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

The paper proposes to replace the weighted average of the values in standard self-attention with the average of values sampled in a way that the expectation is close to the result of self-attention. In particular, the authors associate with each query-key pair, a Bernoulli random variable with expected value close to the exponential of the dot-product. Sampling these variables and averaging the values per query is formulated in an efficient way using locality-sensitive hashing.

### Strengths

- Using sampling to approximate self-attention is novel and promising.
- The LSH formulation where the values are averaged in the bucket is a clever way to avoid the pairwise interactions between queries and keys.
- Training with hashing and evaluating using the expectation is interesting and provides evidence for the approximation quality of YOSO.

### Weaknesses

1. In the evaluation there is never an explicit comparison with respect to both time and performance. I appreciate that given a large enough sequence length YOSO will always be faster but will it be good enough?

2. One of the most important parts of the methodology, the gradient computation, is the least clearly written. For instance, equation 11 contains $\nabla_{Attn}$ which is never defined and subsequent equations contain $\nabla_{YOSO}$ which seems to contradict equation 11. Moreover, how is equation 11 derived? Is it the gradient of the expectation?

3. In table 3, the performance is only measured with respect to inference. Given that the most computationally intensive part of the method is the backward pass, a comparison with respect to wall-clock time per epoch, as well as total training time would be very informative.

### Reasons for recommendation

I find the idea very elegant and interesting however, the experimental section is somewhat lacking. There is no clear evaluation of the trade-off between speed and performance. The MLM task, although significant and demanding, contains sequences of small length, otherwise why not show a graph of performance vs inference-time.
review_title: Elegant idea and formulation but somewhat lacking evaluation

final_score: rating: 2: Strong rejection
review_content: This paper presents a linear-time attention model based on importance sampling and locality sensitive hashing. The idea is to use Bernoulli sampling to approximate the self-attention - which is quadratic in complexity. 

Honestly, this is a very crowded space and already many models exist (https://arxiv.org/abs/2009.06732). The authors are aware of these works, cite them and yet there is no comparison. 

This method seems to be rooted in LSH and a very natural question is how does compare to Reformers. There is not even a sparse transformer or local attention baseline in the experiments. This raises questions about whether this paper will even make any impact at all. (comparisons with longformer is done only on speed/memory but not qualitatively). why? 

I also find other flaws with the model. If sampling is used, this essentially makes the model stochastic (correct me if Im wrong here). but there are undesirable properties of this such as having non-deterministic inference.

Another flaw is that method potentially introduces a lot of instability in training. I think the authors could comment a little on this. Transformers are already notoriously difficult to train and I figure that this method would probably make it way harder for practitioners to get the hyperparameters correct. I think playing with the scaling and normalization of the self-attention weights is something non-ideal, and unless the authors can show this is reasonable stable i am not convinced. 

I also find it difficult to understand the choices of tasks. It seems like GLUE benchmark is used, yet most of the tasks (like SST) are relatively shorter sequences. I think the authors need to explore datasets that showcase the model's ability on longer sequences. Artificially raising sequence len during pretraining is not really sufficient to be convincing that the model is doing something useful for longer sequences (since the masked out tokens really depend on local context). 

My constructive feedback to the authors to improve the paper is to have reasonable baselines for comparison. The datasets are also not appropriate. I would suggest some actually long-range tasks in order to showcase the model's capabilities. 

At the rate of the number of new models that tackle this problem, I suspect it would be wise to wrap up your sleeves and add actual efficient transformer baselines.

review_title: Lacking impact and convincing experiments, unnecessary model 

Meta-review: The paper presents an interesting idea for making self-attention efficient. Several reviewers were not satisfied with the experiments because it did not include runtime and sought after benchmarks.  Rebuttal did a good job of clarifying a few of those with newly added experiments that make the paper stronger. However, the new experiments are in limited settings as well as the real advantage over LSH baselines require more investigation.   This could make a good paper in the future if the experiments are made more rigorous with standard tasks and benchmarks. 
Decision: Reject