Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes an efficient attention mechanism with a linear complexity with respect to the context length and only requires bitwise operations. The resulting model is called EcoFormer. Compared to existing kernel-based linear attention approaches, EcoFormer applies the kernelized hash functions to directly map queries and keys into binary codes to further reduce the computational complexity using floating-point values.
strengths_and_weaknesses: Strengths: This idea of applying kernelized hash functions to existing multi-headed self-attention (MHSA) to achieve linear complexity and eliminate the requirement for floating-point arithmetic operations is very interesting. I believe this proposal helps to further minimize the computational cost of MHSA and is considered as a new contribution to the field. The paper is well written and provides a good discussion of the background and related work. The results are also encouraging, as shown in Table 2, where EcoFormer is able to achieve similar quality (i.e., accuracy) to the ordinary MHSA with significantly fewer multiplication and addition operations. Overall, I like the proposed idea and enjoy reading the paper, but cannot recommend accepting the paper because of the following weaknesses.

Weaknesses: My main concern with this paper is whether the savings claimed in the paper can be achieved with existing hardware backends. The savings in terms of computational cost, energy consumption, and area are purely theoretical and are not supported by any actual demonstration.
1) Performance: The actual performance of the proposed kernelized hashing attention is not reported in wall clock time and is not compared with the ordinary MHSA as well as the kernel-based linear attention methods. Many previous works on efficient attention have demonstrated a significant performance improvement compared the ordinary MHSA when the context length is long. For EcoFormer, I hope to understand more about the actual implementation of the proposed attention mechanism. Specifically, I would like to know if the proposed kernelized hashing attention runs faster, slower, or comparable to kernel-based linear attention methods on GPUs or TPUs.
2) Energy: I am not entirely clear about how the energy consumption is calculated. But I think the authors only calculated the energy consumption of arthemitch operations and ignored the energy consumption of DRAM accesses. However, as pointed out by the TPU-v4 paper [1], the energy consumption of DRAM access dominates the energy consumption of the TPU accelerator chip because DRAM access is over 1000 times more expensive than half-precision multiplication. (Please see Table 2 of the paper). Therefore, I think the authors should claim savings in energy consumption by taking the DRAM access energy into account.
3) Area: I am not convinced by the area saving reported in the paper as you cannot simply calculate the area of the accelerator design by multiplying the area of the circuits with the number of operations. The size of the processing element array/compute engine is determined by the memory bandwidth and the data flow of the accelerator to ensure that the accelerator is not constrained by memory or computation in most cases. I think it makes much more sense to claim better performance on a specific hardware backend rather than area savings.

[1] Ten Lessons From Three Generations Shaped Google’s TPUv4i, ISCA'21

questions: I would like the authors to respond to the main weaknesses mentioned above. In addition, I have a question about how the proposed EcoFormer compares to other non-kernel-based efficient attention schemes (e.g., [2]).

[2] Combiner: Full Attention Transformer with Sparse Computation Cost, NeurIPS'21
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a learnable kernelized hashing to binarize the queries and keys such that the hamming distance between binary codes matches the dot-product similarity relations in the original attention maps. The hashing functions use self-supervised learning using the targets from the most similar and dissimilar pair of queries and keys.  The paper then exploits the equivalence between the hamming distance and dot product of binary codes to approximate the attention in linear complexity with respect to the sequence length.  More importantly, the binarized codes allow replacing the power-hungry floating-point multiplications with simple additions and subtractions. Experiments on vision tasks show that the proposed method results in 50-80% energy and chip area savings for a minor accuracy loss.

strengths_and_weaknesses: **Strengths**
  - The paper is well written. The language is clear and the flow of logic makes the paper easy to understand.
  - The idea of using learnable kernelized hashing to preserve similarity relations of binary codes is novel. The results are encouraging and demonstrate the effectiveness of the proposed methods on the vision tasks.

**Weakness** 
  - The paper demonstrates the efficacy of the proposed methods on vision tasks. I am concerned about the accuracy on natural language processing and other tasks involving sparse attention patterns where the sensitivity of the binarized attention codes could be affected. Long-range arena [1] could be a good benchmark to test the accuracy for various tasks.
  - The paper currently reports the number of additions and multiplications. However, a discussion on how these numbers were derived is missing. It would be good to include this (possibly in the supplementary). 
  - The paper mentions that the Adder Attention [2] results in a drastic performance drop. However, the paper doesn't offer any evidence of this in a comparable setting. From the Adder Attention paper, the DeiT-B model with additions can drop the top-1 accuracy from 81.8%  to 80.4%, similar to the accuracy drop for the proposed method with the Twins-SVT-S model. Thus, a fair comparison would be to use identical networks to compare the accuracy and performance benefits.

[1] Long Range Arena: A Benchmark for Efficient Transformers

[2] Adder Attention for Vision Transformer
questions: **Questions and Suggestions**
  - In lines 254-257, the paper describes the setup for the ImageNet experiments. The proposed method starts from the weights of the pre-trained MSA model and fine-tunes it for 30 epochs. In contrast,  for CIFAR experiments, the models were trained from scratch. Why was the ImageNet model not trained from scratch?
  - Besides Reformer, other works have looked at LSH-based schemes to identify similar pairs of queries and keys. A discussion contrasting the current work from these could be included in the related works:
    - SMYRF: Efficient Attention using Asymmetric Clustering (NeurIPS 2020)
    - Fast Transformers with Clustered Attention (NeurIPS 2020) 
    - Sparse Attention with Learning to Hash (ICLR 2022) 
limitations: These are discussed.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes a new binarization framework to customize high-dimensional softmax attention and reduce computation complexity in Transformers. Specifically, it utilizes the kernelized hashing to map the original queries and keys into low-dimensional binary codes in Hamming space. The kernelized hashing function is learned to maximize the similarities between the binarized codes and ground-truth relations in the original attention maps. Experiments on classification tasks show it achieves comparable performance with much fewer multiplications and additions.
strengths_and_weaknesses: Strengths:
1. The motivation of this work is promising and binarizing the Transformers through kernelized hashing functions in a self-supervised way is novel.
2. In this paper, authors explicit the idea and methods clearly and easy to follow how they solve the whole optimization problem.
3. Experimental results on ImageNet show high efficiency compared with the baselines.

Weaknesses:
1. Sec. 4.2 seems to have some inconsistent size of matrices or vectors, which makes this key part hard to follow and misunderstanding.
2. There are some related works using binarization strategy in Transformers, too, including the latest BiT [1]. etc. However, there is no comparison with these methods.
3. In the section of experiments, tables show the number of additions and multiplications but the details of how to calculate them are missed.

[1] Liu, Zechun, et al. "BiT: Robustly Binarized Multi-distilled Transformer." arXiv preprint arXiv:2205.13016 (2022).
questions: 1. In the line 202, $c$ is set to $\lceil \log_2 b \rceil$, then the inequation in line 201 could be 0, right? 
2. The notations in Sec. 4.2 are confusing and difficult to understand, for example, in Eq. (11), the LHS $H(q)$ should be a bx1 vector as you defined at the beginning of this subsection, but RHS is Nxb after the matrix multiplication. How come this happens?

limitations: The additional parameters of weights $a$ are optimized iteratively in the training process, the computation cost and time cost might still be a problem.
review_title: null

Meta-review: metareview: The paper after rebuttal addresses several of the limitations (mainly lacking positioning in the rich existing litterature) of the first submission. The strength of the paper resides in a holistic approach to the ("yet another") efficient attention mechanism, evaluating and discussing trade-offs between accuracy, compute, energy, and silicon area use. 
The main limitations are the limited novelty, and the rather thin experimental validation: no SOTA baselines on ImageNet, LRA not being very correlated to real tasks accuracy. 
Overall, I recommend for the paper to be accepted based on its technical merit.
confidence: Less certain
Decision: Accept