EcoFormer: Energy-Saving Attention with Linear Complexity
Authors: Jing Liu
Zizheng Pan
Haoyu He
Jianfei Cai
Bohan Zhuang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Energy-efficient Attention
Linear Complexity
Transformer
Binarization
Hashing

Abstract: Transformer is a transformative framework for deep learning which models sequential data and has achieved remarkable performance on a wide range of tasks, but with high computational and energy cost. To improve its efficiency, a popular choice is to compress the models via binarization which constrains the floating-point values into binary ones to save resource consumption owing to cheap bitwise operations significantly. However, existing binarization methods only aim at minimizing the information loss for the input distribution statistically, while ignoring the pairwise similarity modeling at the core of the attention mechanism. To this end, we propose a new binarization paradigm customized to high-dimensional softmax attention via kernelized hashing, called EcoFormer, to map the original queries and keys into low-dimensional binary codes in Hamming space. The kernelized hash functions are learned to match the ground-truth similarity relations extracted from the attention map in a self-supervised way. Based on the equivalence between the inner product of binary codes and the Hamming distance as well as the associative property of matrix multiplication, we can approximate the attention in linear complexity by expressing it as a dot-product of binary codes. Moreover, the compact binary representations of queries and keys in EcoFormer enable us to replace most of the expensive multiply-accumulate operations in attention with simple accumulations to save considerable on-chip energy footprint on edge devices. Extensive experiments on both vision and language tasks show that EcoFormer consistently achieves comparable performance with standard attentions while consuming much fewer resources. For example, based on PVTv2-B0 and ImageNet-1K, EcoFormer achieves a 73% reduction in on-chip energy footprint with only a slight performance drop of 0.33% compared to the standard attention. Code is available at https://github.com/ziplab/EcoFormer.

EcoFormer: Energy-Saving Attention with Linear Complexity
Jing Liu"
Zizheng Pan"
Haoyu He
Jianfei Cai
Bohan Zhuang
Department of Data Science & Al, Monash University, Australia
Abstract
Transformer is a transformative framework for deep learning which models se- quential data and has achieved remarkable performance on wide range of tasks, but with high computational and energy cost. To improve its efficiency, popular choice is to compress the models via binarization which constrains the floating- point values into binary ones to save resource consumption owing to cheap bitwise operations significantly. However, existing binarization methods only aim mini- mizing the information loss for the input distribution statistically, while ignoring the pairwise similarity modeling at the core of the attention mechanism. To this end, we propose a new binarization paradigm customized to high-dimensional softmax attention via kernelized hashing, called EcoFormer, to map the original queries and keys into low-dimensional binary codes Hamming space. The ker- nelized hash functions are learned to match the ground truth similarity relations extracted from the attention map in a self-supervised way. Based on the equiv- alence between the inner product of binary codes and the Hamming distance well as the associative property of matrix multiplication, we can approximate the attention in linear complexity by expressing it dot-product of binary codes. Moreover, the compact binary representations of queries and keys in EcoFormer enable to replace most of the expensive multipy--ccummulate operations in atten- tion with simple accumulations to save considerable on-chip energy footprint on edge devices. Extensive experiments EcoFormer consistently achieves comparable performance with standard attentions while consuming much fewer resources. For example, based on PVTv2-BB and ImageNet-Ik K, EcoFormer achieves a 73% reduction in on-chip energy footprint with only a slight performance drop of 0.33% compared the standard attention. Code is available at https: / /github....... com/zi com/z/plaabBcooormees Ecooo/rrr.r.rr
both vision and language tasks show that
Introduction
Recently, Transformers [57] have shown rapid and exciting progress in natural language processing (NLP) [15, 14] and computer vision (CV) [17, 56] due to its extraordinary representational power. Compared with convolutional neural networks (CNNs) [30], Transformer models are generally more scalable to massive amounts of data and better at capturing long-dependency global information with less inductive bias, thus achieving better performance in many tasks [26, 38]. However, the efficiency bottlenecks, especially the high energy consumption, greatly hamper the massive deployment of Transformer models to resource-constraii
edge devices, such as mobile phones and unmanned acrial vehicles, for solving a variety of real-world applications.
Authors contributed equally.
Corresponding author. Email: bohan. Chaan.zhuann(innassheeei
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Multiply-accumuliee
Addition only
[g
(q:h=1
(()
[q
H(-)
sofimax
[k3
OC0")
{k/
(kg)
hovrry codes
OEN)
((M)
[vi]==
O(N')
(v)
(IN)
D(N)
(a) Attention
(b) Kernel-based Lincar Attention
(c) EcoFormer
Figure I: Computational graphs for standard attention (left), kernel-based linear attention (middle) and the proposed EcoFormer based on kernelized hashing (right).
Table I: Energy cost for different operations (on 45mm CMOS technology) [21, 22, 32].
Operation
16-bit FP Add 16-bit FP Mult
32-bit FP Add
32-bit FP Mult
Energy (pJ)
0.4
1.1
0.9
3.7
Area (jm²))
1,360
1,640
4,184
7,700
To reduce the energy consumption, quantization has been actively studied to lower the bit-width representation of network weights [11, 52, 66] and/or activations [25, 68, 67]. With the most aggressive bit-width, binary quantization [49, 46] has attracted much attention since it enables efficient bit-wise operations by representing values with a single bit (e.g.. +1 or -1). When we only binarize weights in analogous to BinaryConnect [11]. as shown in Table 1, brings great benefits to dedicated hardware by replacing large number of energy-hunge operations with simple energy-efficient accumulations, which saves significant on-chip area and energy required to run inference with Transformers, making them feasible to be deployed on mobile platforms with limited resources. However, the conventional binarization process typically targets at minimizing quantization errors between the original full- cell-precision data distribution and the quantized Berouuli distribution statistically. other words, each token is binarized separately, where the binary representations may not well preserve the original similarity relations among tokens. This motivates us to customize the binarization process to softmax attention, the core mechanism in Transformer that encodes the pairwise similarity between tokens. To this end, we can adapt the well-established hashing methods, to map the high- high-dimensional queries and keys into compact binary codes (e.g., 16-bits) that are able to preserve the similarity relations in Hamming space. A simple solution is to use the locality-sensitii sensitive hashing (LSH) [1] to substitute the binary quantization counterparts.
multiply-accumulat
Nevertheless, another energy bottleneck exists in Transformers. Specially, given sequence of tokens, the softmax attention obtains the attention weights by computing the inner product between a query p token and all key tokens, leading to the quadratic time complexity O (N²) regarding the number of tokens N. as shown Figure (a). This problem even worse for a long sequence length N, especially for high resolution images in dense prediction tasks. To reduce the complexity of the softmax attention, some prior works propose to express the attention as a linear dot product of kernelized feature embeddings [45, 9]. With the associative property of matrix multiplication, the attention operation can be approximated in linear complexity ((N), as illustrated by Figure (b).
Based on the hashing mechanism and kernel-based formulation of attention, we devise simple yet effective onergy-saving attention, called EcoFormer, which is shown in Figure 1 (c). In particular, we propose to use kernelized hashing with RBF kernel to map the queries and keys to compact binary codes. The resulting codes are valid for similarity preserving based on the good property that the codes' inner product (ie.. Hamming affinity) and Hamming distance have one-to-one correspondence [36]. Thanks to the associative property the linear dot-product between the binary codes, the kernelized hashing attention is in linear complexity with significant energy saving. Moreover, the pairwise similarity matrix in attention can be directly used to obtain the supervision labels for hash function learning, delivering novel self-supe hashing paradigm. By maximizing the Hamming affinity on the similar pairs of tokens and simultaneously minimizing on the dissimilar pairs of tokens, the pairwise similarity relations between tokens can be preserved. With low-dimensional binary queries and keys, we can replace most of the energy-hungr floating-pon multiplications in attention with simple additions, which greatly saves the on-chip energy footprint.
To sum up, we make three main contributions: 1) We propose a new binarization paradigm to better preserve the pairwise similarity in softmax attention. In particular, we present EcoFormer, an energy-saving attention with linear complexity powered by kernelized hashing to map the queries and keys into compact binary codes. 2) We learn the kernelized hash functions based on the ground-

---

truth Hamming affinity extracted from the attention scores in self-supervised way. 3) Extensive experiments on CIFAR-100, ImageNet- IK and Long Range Arena show that EcoFormer is able to significantly reduce the on-chip energy cost while preserving the accuracy. For example, based on PVTv2-BO and ImageNet-1K EcoFormer achieves a 73% reduction in on-chip energy footprint with only a marginal performance drop of 0.33% compared to the standard attention.
2 Related Work
Efficient attention mechanisms. To alleviate the quadratic computational cost for vanilla attention with respect to the number of tokens, much work has endeavored developing efficient attentions.
One line of research performs attention only on the part of the tokens [38, 61, 4, 29, 60, 12, 58, 54]. For instance, Reformer [29], SMYRF [12], Fast Transformers [58] and LHA [54] restrict the attention to the most similar token pairs via hashing and reduces the computational complexity to ON N). Linformer [60] approximates the attention with low-rank factorization that reduces the length of the key and value. However, the computational complexity is dependent on the design for reducing tokens. Another line of research speeds up the vanilla attention with kernel-based methods [9, 64, 41, 28, 47J. For example, Performer [9] approximates the softmax operation with orthogonal random features. Nyströmformer [64] and SOFT [41] approximate the full self-attention matrix via matrix decomposition. Although impressive achievements have been achieved, how to develop attention that is highly energy-efficient remains under-explored, as multiplications dominate the on-chip energy consumption. AdderNet variants [8, 53] replace the energy- -unggy multiplication- based similarity mcasurement with the energy-effictee efffcientt addition-basee L1 distance and argue that additions also provide powerful feature representations. Nevertheless, this heuristic approach brings a drastic performance drop. In contrast, we are from the perspective of binarization and propose to learn kernel-based hash functions using attention scores map the original features into compact sumilarity-preservve linear complexity (NN). With the low-dimensional binary queries and keys, our EcoFormer is able to replace most of the multiplications with simple accumulations.
binary codes in Hamming distance, which is energy-efficient and in
Hashing. Hashing is an efficient nearest neighbor search method by embedding the high-dimensional data into a similarity preserving low-dimensional binary codes, based on the intuition that highly similar data should be assigned the same hash key. Hashing methods can be roughly categorized into data-inde mattainddeendentt and data-dependent schemes. The former focuses on building random hash functions and locally sensitive hashing (LSH) [19, 7] is arguably the most representative one, which guarantees the sub-linear time similarity search and is followed by non- non-linear extensions such as hashing with kernels [31]
manifolds [63]. The latter be further divided into unsupervised [37, 20, 35], semi-supervised [44, 59] and supervised hashing [36, 71, 65J. When it comes to Transformers, as self-attention encodes the pairwise similarity among tokens, hashing is thus a natural choice to efficiently retrieve similar keys given a query. Reformer is such a pioneering work, which proposes group similar tokens in a single hash bucket to form sparse self-attention. Our EcoFormer is fundamentally different from Reformer in three aspects: 1) Reformer relies on local attention lookups to reduce the complexity while our EcoFormer is designed from numerical perspective, where the low-dimensional binary codes are used to save the multiplications: 2) Reformer is built upon LSH with linear mapping, which cannot deal with the kernel-based formulation of attention to scale linearly with the sequence length; 3) Our hash functions are self- eeffssupee by the pairwise affinity labels in attention, which are optimized in conjunction with network parameters and more accurate than unsupervised random projections.
Binary quantization. Binarization, an extreme quantization scheme, seeks represent the vectors by binary codes. As a result, the computationally heavy matrix multiplications become light- bitwise operations (i.e., xnor and popcount). yielding promising memory saving and acceleration. In general, to make binary neural networks [24] reliable in accuracy, current research targets at tackling two main challenges. The first challenge is to minimize the quantization error, basically based on learning the scaling factors [49, 6]. parameterizing the quantization range and/or intervals [27, 18], and ensembling multiple binary bases [34, 72], etc. Another category of studies focus on solving the non-diff non-differentiable optimization problem due to the discretization process via training with regularization [16], knowledge distillation [43, 46), relaxed optimization [23, 3], appending full-precision branches [39, 42] and so on. Apart from CNNs, there are some recent pioneering attempts targeting on binarizing Transformers. For example, BinaryBERT [2] proposes to push
Transformer quantization to the limit by weight binarization. BiBERT [46] quantizes both weights,
3

---

embeddings and activations of BERT [15] to 1-bit and achieves considerable savings on FLOPs and model size, but still has obvious performance drop. In contrast. we propose to customize the binarization paradigm to softmax attention from the hashing perspective, preserving high-fidelity pairwise similarity information in compact binary codes which are used to deliver iinear-complexity, energy-efficient self-attention.
3 Preliminaries
3.1 Attention Mechanism
Let X N be the imput sequence into standard multi-head self-attention (MSA) layer, where N is the length of the input sequence and D is the number of hidden dimensions. A standard MSA layer calculates a sequence of query, key and value vectors with three learnable projection matrices Wg. W.. W. E DxDy, which can be formulated as
{qi)) XW (k. XW&, (velem XWe.
(1)
where Dp refers to the number of dimensions for each head. For each query vector, the attention output weighted-sum all value vectors
exp(q: k,/T) ΣE, exp(q: k2/T)
Attention(q,, (ke), (v.)) (v:))= E,
Vi.
(2)
where F is the temperature for controlling the flatness of softmax and exp( ,)) is an exponential function. With N token, the computation of attention has a quadratic complexity of O(N²) ) in both space and time, which results in huge computational cost when dealing with long sequences.
3.2 Kernel-based Linear Attention
The idea behind kernel-based linear attention is to express the similarity measure in Eq. (2) as a linear dot-product of kernel embeddings, such as polynomial kerne,, exponential or RBF kernel. particular choice is to employ the finite random mapping [48] Φ(.) to approximate the infinite dimensional RBF kernel. Then, according the theorem from Rahimi [48], the inner product between pair of transformed vectors x and with ((-) can approximate a Guassian RBF kernel. This gives rise to an unbiased estimation exp((+; in Eq. (2), which can be expressed
exp v//0)
exp [|x| /202 + 11y1? 2202
exp (- ||x 1xx-yl* y11 /20
(3)
= exp
[|x
220 2 + ||yl| /20
$ (x)
(ly).
Assume that the queries and keys unit vectors, then the attention computation in Eq. (2) can be approximated by
Φ (qi)
Φ (k,)
Attention(q, (ki), (v:)) ~0
(4a)
Σ, ① (qi) $ (kg))
+ (q.) Σ, Φ (k. @v:
(4b)
+ (q:) Σ, (k,)
where refers the outer product. Recent works have shown that kernel-based linear attentions perform favorably against the original softmax attention on machine translation [45] and protein sequence modeling [9]. However, although the complexity is reduced into linear, the intensive floating-pon multiplications in Eq. (4b) still consume a large amount of energy, which can quickly drain the batteries on mobile/edge platforms.
3.3 Binary Quantization
Following [49], binary quantization typically estimates the full-precision u E R² using a binary ú e {+1, -1}" and scaling factor E R+ such that aú holds. To find accurate estimation, existing methods [49, 42, 34, 2, 46] minimize the quantization enror as
û arg min ||u aull-
(5)

---

By solving Problem (5), we have ú = sign (u) and = ||uller. where sign(u) returns 1 if u 2 0 and -1 u < O. Since the sign function is non-differentiabl, the straight- straight-through estimator (STE) [5] is applied to approximate the gradient such as using the gradient of hard tanh [25] or piecewise polynomial function [39].
Proposed Method
To reduce the energy consumption of self-attention, one may perform binary quantization [46, 2] on the queries {qe J and keys (ke (k.)/= J/V In this case, we can replace most of the energy-expensive multiplications with the energy-efficient bit-wise operations. However, existing binary quantization methods only focus on minimizing the quantization enror between the original full foll-precision values and the binary ones as in Eq. (5), which fails to preserve the pairwise semantic similarity between different tokens in attention, leading to performance degradation.
Note that the attention can be seen as applying kernel smoother over pairwise tokens where the kernel scores denote the similarity of the token pairs, as mentioned in Section 3.2. Motivated by this, propose a new binarization method that applies kemnliized hashing with Gaussian RBF to map the original high-dimensional queries/keys low-dimensional similarity-preeerving binary codes in Hamming space. The proposed framework, which we dub EcoFormer, is depicted in Figure 1 (c). To maintain the semantic similarity attention, we learn the hash functions in a self-supervised manner. By exploiting the associative property of the linear dot- dot-product between binary codes and the equivalence between the code inner products (i.e., Hamming affinity) and the Hamming distances, we are able to approximate the self-attention in linear time with low energy cost. In the following, we first introduce the kernelized hashing attention in Section 4.1 and then show how to learn the hash functions in self-supervised way in Section 4.2.
4.1 Kernelized Hashing Attention
Before applying hash functions, we let the queries {g:)<= and keys ] to be identical follow- ing [29, 41]. In this way, we can then apply kernelized hash functions H : IR + {1,- -1,6 without explicitly applying transformation (6-) mentioned in Section 3.2 to map qi and k, into b-bit binary
codes H (q:) and (k,), respectively (see Section 4.2). In this case, the Hamming distance between them can defined as
D (H(q), H(k))) = - (gH) * (k))),
(6)
where (.) the r-th bit of the binary codes; 1 {A} is an indicator function that returns if A satisfied and otherwise returns O. With D (H()), H(k,)), )), the codes inner product between (q.))
and H (k,) can be formulated as
H(q)) H(k,)
Σ (HH((q)) H,(ks)) Σ ((H((q)) # H.(k;))
= b- 2 > ((H((q)) + H,(k))) = = 5-20 2D
Importantly, Eq. (7) shows the equivalence between the Hamming distance and the codes inner product since there is a one-to-one correspondence. By substituting with the hashed queries and keys in Eq. (4a), we can approximate the self-attention
Attention(q... (ki), {v.)) ~ Σ H(q)) H(k)). (()) H(,,)
(8)
Note that H())) TH(Kk E [-b, b). To avoid zero in denominator, we introduce a bias term 2 to each inner product so that H (qq)) (k,) + 2 > 0, having no effect on the similarity measure. Here, we can simply set to [log2(b + 1)7 where [u] returns the least integer greater than or equal to u. Using the associative property of matrix multiplication, we approximate the self-attention as
Attention(qu (k)) (v.)) =3 Σ (H)))) H (k:) + +2
E, (H H ((,)) + +
(9)
H(q)) E, H(k)) @ v; + >, 2 H(q)) Σ, H(k,) + N
5

---

In practice, the multiplications between the binary codes and the full full-precision values in Eq. (9) can be replaced by simple additions and subtractions, which greatly reduce the computational overhead in terms of on-chip energy footprint. Moreover, the multiplications with powers-of-twe 2 can also be implemented by efficient bit-shift operations. As a result, the only multiplications come from the element-wise divisions between the numerator and denominator.
4.2 Self-supervised Hash Function Learning
Given queries Q (qi (....... qN) C Pr, we seek learn a group of hash functions h RD, {1, -13. Instead of explicitly applying the transformation function ((.) mentioned in Section 3.2. we compute the hash functions with a kernel function x(q,, q,) R x R. R. Given Q qq.... ... qN]" E RDxx,, we randomly sample m queries 4(1),.... 4(m) from Q as support samples following the kernel-based supervised hashing (KSH) [36] and define hash function h as
h Q) sign E==1 (N (90)) Q) 14) a.) = sign (g(Q)a),
(10)
where a la..... am]
IT is the weight of h, (4 E (96) q:) is normalize the kernel function to zero-mean, and g : RDD + R. is mapping defined by g(Q)
[K (9 Q) Pl...., (((())) Q) pm Nxm. Then, we define the kernelized hash func-
tion H())
((Q) (h) (Q) h1 ... ho(q1)
sign (g(Q)A),
(11)
(qw),, (.. ,,s(qN)
where A = (a1, ... au] E Rm and h, (Q) = sign (g(Q)aa) the hash function for the r-th bit.
To guide the learning of the binary codes, hope that similar token pairs will have the mini- mal Hamming distance while dissimilar token pairs will have the maximal distance. Nevertheless, directly optimizing the Hamming distance is difficult due to the non-convex and non-smooth for-
mulation in Eq. (6). Utilizing the equivalence between the code inner products and the Hamming distances in Eq. (7), instead conduct optimization based on the Hamming affinity to minimize the reconstruction error as
minA || QQQ BY minA (Q),,, - bY
(12)
where |-I1 is the Frobenius norm and E NxN the target Hamming affinity matrix. To preserve the similarity relations between queries and keys, we use the attention scores as the self-supervised information to construct Y. Let and 2/ be the similar and dissimilar pairs of tokens. We obtain S and l by selecting the token pairs with the Top-/ largest and smallest attention scores. We then construct pairwise labels as
1,
(q., q1) (q: qi) Eu
Yo, =
1,
(13)
0, otherwise.
However, Problem (12) is NP-hard. To solve it efficiently, we adapt discrete cyclic coordinate descent to learn binary codes sequentially. Specifically, we only solve once the previous " a have
been optimized. Let Y bY Σx= hr (Q),,, (Q) be the residual matrix, where Yo bY. Then, we can minimize the following objective to obtain a,
= mina, - (Q) (1) (Q)) -Y_ - -
mina,-
(14)
where C' = (Q) +t (Y,-)) is constant. Note that Ý, is a symmetric matrix.
Therefore, Problem (14) is a standard binary quadratic programming problem, which can be efficiently solved by many existing methods, such as the LBFGS-B solver [69] and block graph cuts [33]. To learn a, in conjunction with network parameters, we propose to solve Problem (14) using the gradient- STE [5] approximate the gradient
based methods. For the con-differentiable sign function, using hard tanh as mentioned in Section 3.3. Note that learning the hash functions for each epoch is computationally expensive yet unnecessary. We only learn the hash functions per epoch.

---

Table Main results on ImageNet-IK: I. The number of multiplications, additions, as well on-chip energy consumption are calculated based on an image of resolution 224 x 224. The throughput is
measured with a mini-batch size of 32 on a single NVIDIA RTX 3090 GPU.
Model
Method
#Mul. (B)
#Add. (B)
Energy (B pJ)
Throughput (images/s)
Top-1 Acc. (%)
MSA
2.02
1.99
9.25
850
70.77
PVTv2-B0 [62]
Ours
0.54
0.56
2.49
1379
70.44
MSA
5.02
5.00
23.07
621
78.83
PVTv2-BI
Ours
2.03
2.09
9.39
874
78.38
MSA
8.64
8.60
39.71
404
81.82
PVTv2-B2
Ours
3,85
3.97
17.82
483
81.28
MSA
11.86
11.82
54.56
310
82.26
PVTv2-B3
Ours
6.54
6.72
30.25
325
81.96
MSA
15.97
15.93
73.43
247
82.42
PVTv2-B4
Ours
9.57
9.82
44.25
249
81.90
MSA
5.96
5.91
27.36
426
81.66
Twins-SVT-S [10]
Ours
2.72
12.59
576
80.22
5
Experiments
5.1 Comparisons ImageNet-1K
To investigate the effectiveness the proposed method, we conduct experiments on ImageNet- IK [30], a large-scale image classification dataset that contains 1.22 training images from IK categories and 50K validation images. We compare our kernelized hashing attention with standard MSA by adapting the attention approaches into two popular vision Transformer frameworks PVTv2 [62] and Twins [10]. We measure model performance by the Top-1 accuracy. Furthermore, FLOPs cannot accurately reflect the computational cost in our proposed method, measure the model complexity by the number of multiplications and additions, separately, as done in [53]. Specifically, calculate FLOPs following [61], where count the multiply-accumull operations for all layers. In this case, each cation. We also count the multiplications in the scaling operations. Moreover, we report the on-chip energy consumption according to Table I and the throughput with mini-batch size of 32 on single NVIDIA RTX 3090 GPU.
accumulate operation consists of an addition and multipli-
Implementation details. All training images are resized to 256 256, and 224 x 224 patches are randomly cropped from image its horizontal flip, with the per-pixel mean subtracted. To obtain the MSA baselines, we first replace the original attention layers in PVTv2 [62] and Twins [10] with standard MSAs and initialize the models with the pretrained weights on ImageNet- Next, finetune each model on ImageNet- K with 100 epochs. Based the pretrained MSA weights, we then apply our approach each model and finetune on ImageNet- 1K with 30 epochs. All models this experiment are trained on 8 V100 GPUs with a total batch size of 256. We set the initial learning rate 2.5 x 10 for PVTv2 and 1.25 10 for Twins. We use AdamW optimizer [40] with cosine decay learning rate scheduler. All other byperparameters are the same as in PVTv2. Also note that recent hierarchical ViTs [62, 38, 10] have multiple stages to incorporate pyramid feature maps. At the last stage, they usually apply standard MSAs due to the comparably low-resolution feature maps. This design is also adopted in PVTv2 and Twins. Therefore, we follow the common practice and do not modify the attention layers at the last stage. For the hash functions learning, we set the number support samples m and update interval I in constructing pairwise labels Y is set to 10. We set the hash bit to 16.
25 and 30, respectively. The hyper-parameter
Results analysis. We report the results Table In general, our baseline MSA has more multiplica- tions than additions. In contrast, our EcoFormer replaces most of the floating -oint multiplications in attention with simple additions. Therefore, there are more additions than multiplications in our EcoFormer. Compared to MSA, our method achieves lower computational complexity. less energy consumption and higher throughput with comparable performance. For example, based on PVTv2-BB BO, our method saves around 73% multiplications and 72% additions, well as reducing 73% on-chip energy consumption, which demonstrates the energy-efficiene of our approach. With more efficient accumulation implementation, the throughput of our EcoFormer can be further improved. Besides, larger model comes with larger proportion of computational and on-chip energy cost dominated by FFNs, shown in Figure 2. In this case, our approach focuses on the attention layers, the energy-
7

---

100
100
Attn
FLOPs Percentage (%)
Energy Percentage (9)
2005
FFN
80
80
40
40
DRSH
S4E4
20
20
83
84
80
81
82
83
Model
Model
Figure 2: FLOPs and on-chip energy footprint percentage of attention layers (Attn) and feed forwar layers (FFN) in different variants of PVTv2 with standard MSAs. For bigger model, FFN takes larger proportion the computational cost and on-chip energy footprint.
saving from larger models is comparably less than smaller models (e.g.. PVTv2-BO vs. PVTv2-B4). Nonetheless, we still reduce significant computational cost and on-chip energy consumption. For example, PVTv2-B4, the performance drop of our method is slightly larger on Twins. One possible reason is that our method may be sensitive the conditional positional encodings in Twins.
around 40% on-chip energy consumption. Compared with PVTv2,
5.2 Comparisons Long Range Arena
To evaluate the performance different efficient attentions under long-context scenarios, we train our EcoFormer on two tasks, Text and Retrieval from the Long Range Arena (LRA) benchmark [55] following the settings of [70]. Our implementations are based on the released code of [64]. We m, and in ImageNet- IK experiments. We show the results in
the same Table 3. From the table, our EcoFormer achieves comparable performance with much lower on-chip energy consumption. For example, on Text, compared with MSA, method saves around 94.6% 6% multiplications and 93.7% additions as well as 94.5% on-chip energy consumption, which is more efficient than existing attention mechanisms.
Table 3: Comparisons of different methods on Long Range Arena (LRA). We report the classification accuracy (%) for Text well Retrieval and average accuracy across two tasks. denotes that obtain the results from the original paper.
Method
#Mul. (B)
#Add. (B)
Energy pJ)
Text (4K)
Retrieval (4K)
Average
Transformer
4.63
4.57
21.25
64,87
79.62
72.25
Performer [9]
0.83
0.84
3.83
64,82
79.08
71,95
Linformer [60]
0.81
0.81
3,74
$7.03
78.11
67.57
Reformer [29]
0.54
0.54
2.49
65.19
79.46
72.33
Combiner" [50]
0.51
0.51
2.34
64.36
56.10
60.23
EcoFormer
0.25
0.29
1.17
64.79
78.67
71.73
5.3 Ablation Study
In this section, we evaluate the effectiveness our EcoFormer by comparing it with different binarization approaches and efficient attention mechanisms. By default, train each model from scratch on CIFAR- 100 with 2 GPUs for 300 epochs. The total batch size 64. The initial learning rate is 6.25 10 For the hash functions learning, set update interval 7 to 300. All the other hyperparameters are the same as in ImageNet- I experiments.
Table 4: Performance comparisons with different binarization methods on CIFAR-100. #Add. (B)
Model
Method
#Mul. (B)
Energy (B pJ)
Top-1 Ace. (%)
EcoFormer
0.94
4.33
70.78
PVTv2-B0
Bi-Foorrrerr
0.63
0.83
3.09
70.06
EcoFormer
0.56
2.49
71.23
FP-EcoFormer
5.96
5.91
27.36
80.04
Wvins-SVT-S
Bi-EcoFormer
3.59
14.38
80.04
EcoFormer 2.72
2.81
12.58
80.31
Quantization vs. hashing. investigate the effect of different binarization methods, we compare EcoFormer with the following methods: FP-EcoFormer: Based EcoFormer, we do not

---

binarize queries and keys in attentions. Bi-EcoFormer: Relying on EcoFormer, we use the same binary quantization [25] as BinaryBERT [2] and BiBERT [46] obtain binarized queries and keys instead of our proposed hash functions. For fair comparisons, the attention operations in the compared method are in linear complexity. We apply different methods to PVTv2-BO and Twins-SVT--S and report the results in Table 4. We observe that our EcoFormer consistently outperforms Bi-merrormer on different frameworks. For example, based on PVTv2-BO, our EcoFormer surpasses Bi-EcoFormer by 1.17% in terms of the Top-1 accuracy. Compared with binary quantization, our proposed self- supervised hash functions preserve the pairwise similarity of attention, leading to better performance. Moreover, our EcoFormer does not need to explicitly compute transformation x6-) in Eq. (4b). Therefore, the energy cost of our EcoFormer is lower than Bi-EcoFormer.
Table 5: Performance comparisons with different hash functions regarding PVTv2-BO on CIFAR-100.
Method
IMuul (B) #Add. (B) Energy (B pJ)
Top-1 Acc. (%)
U.S--EcoFormce
0.68
0.69
3.12
70.18
KL.SH-EoFoorerr
0.54
0.56
2.49
70.66
EcoFormer
0.54
0.56
2.49
71.23
Effeet of different hash functions. To investigate the effect of different hash functions, we include the following methods for comparisons: LSo-eeooormmr: Relying EcoFormer, Sensitive Hashing (LSH) [13] rather than our proposed kernelized hash function. KLSH-Eco Based on EcoFormer, we replace the proposed hash function with Kernelized Locality-Sensitive Hashing (KLSH) [31]. We report the results in Table 5. We can observe that KLSHH-EcoFormer outperforms
Locality-
by 0.48% in terms of the Top-1 accuracy with less on-chip energy consumption. The reason can be attributed to that LSH is based on random linear projection, which can not deal with the non-linear softmax attention well. Critically, our EcoFormer further improves the performance by 0.57% on the Top-1 accuracy. Compared with random hashing in KLSH, our EcoFormer learns the hash functions with additional self self-supervised information. Therefore, our learned binary codes are better at preserving the token similarity.
Table 6: Comparison with other efficient attention methods regarding PVTv2-BO [62] on CIFAR-100. nAdd. (B)
Method
#Mul. (B)
Energy (B pl)
Top-1 Acc. (%)
Transformer
2.02
1.99
9.25
71.44
Performer [9]
0.94
0.94
4.33
70.78
Linformer [60]
0.69
0.69
3.18
71.17
Reformer [29]
1.62
1.63
7.44
70.56
EcoFormer
0.54
0.56
2.49
71.23
Comparing with other efficient attention mechanisms. To compare EcoFormer with different attention mechanisms, we conduct ex- periments on CIFAR- 100 based on PVTv2-BO in Table 6. In our experiments, we directly re- place the attention layers with each compared method in PVTv2-BO [62]. In general, com- pared to other efficient attention mechanisms, EcoFormer saves more computations and re- duces more on-chip energy consumption while achieving better performance. Particularly, ben- efiting from the multiplication-saving operations and diw-dimnniionl binary queries and keys, EcoFormer saves more on-chip energy than Performer. Also note that since the proposed kernelized hash function H-) does not need to explicitly apply transformation <f.)) to the queries and keys as in Eq. (4b), EcoFormer simultancously reduces more multiplications and additions than Performer. Besides, Linformer achieves competitive results. How- ever, as the size of the learnable low-rank projection parameters depends on the length of the input sequence. Linformer not scalable to different image resolutions, whereas EcoFormer with sufficient bits is agnostic to the sequence length.
Table 7: Latency and energy comparisons with dif- ferent attention methods. We measure the latency and energy of an attention layer with batch size of 16, a sequence length of 3, 136 and an embedding dimension of 32 on a BitFusion [51] simulator.
Method
Latency (ms)
Energy (p))
Transformer
0.0036
85,692.18
Performer [9]
0.0019
41.113.64
Linformer [60]
0.0018
45,770.61
Reformer [29]
0.0024
57,305.47
EcoFormer
0.0010
24,990.75
Latency and energy on BitFusion [51]. To show the actual energy consumption and latency, we test different methods on a simulator of BitFusion, bit-flexible microarchitecture synthesized in 45 nm technology. From Table 7, EcoFormer shows much lower latency and on-chip energy than the other efficient attention methods, which further verifies the advantage of EcoFormer.
9

---

Effect of training from scratch on ImageNet-1K. To explore the effect of training from scratch, we apply EcoFormer to PVTv2-BO and PVTv2-B1. We follow the experimental settings mentioned in Section 5.1 except that we train the model from scratch with 300 epochs. The initial learning rate set to 2.5 x 10-1 From Table 8, EcoFormer achieves comparable performance while significantly reducing the computational complexity and on-chip energy consumption. The accuracy drop from discretization comes from the gradient approximation for the non-differentiable sign function, which can be mitigated by more advanced optimization methods, such as regularization [16], knowledge distillation [43, 46], relaxed optimization [23, 3], appending full-precision branches [39, 42], etc.
Table 8: Performance comparisons of different methods on ImageNet- All the models are trained from scratch. The number of multiplications, additions, and on-chip energy consumption are calculated based on an image of resolution 224 x 224.
Model
Method
#Mul. (B)
#Add. (B)
Energy (B pJ)
Top-1 Acc. (%)
MSA
2.02
1.99
9.25
69.72
PVTv2-BO
Ours
0.54
0.56
2.49
68.70
MSA
5.02
5,00
23.07
78.34
PVTv2-B1
Ours
2.03
2.09
9.39
77.49
Effect of different m. To investigate the effect of different numbers of support samples m, we train EcoFormer with different m based on PVTv2-BO. We report the results on CIFAR-100 in Table 9. As we increase m, the performance becomes better along with the increase in on-chip energy consumption. For example, the model obtained with m = 15 outperforms that of m = 10 by 0. 091% on the Top- accuracy with little additional energy cost. We speculate that, with more support samples, we can capture more accurate statistics in Eq. (10) and hence lead to better performance. Since our EcoFormer achieves the best performance with m = 25, we use it by default in our experiments.
Table 9: Performance comparisons with different #support samples m. We report the results of PVTv2-BO on CIFAR-104
#Mul. (B)
#Add. (B)
Energy (B pJ)
Top-1 Acc. (%)
10
0.53
0.55
2.46
70.73
0.53
0.56
2.47
70.92
20
0.53
0.56
2.48
70.81
25
0.54
0.56
2.49
71.23
Conclusion and Future Work
In this paper, we have presented a novel energy-saving attention mechanism with linear complexity to save the vast majority of multiplications from new binarization perspective, making the deployment of Transformer models at scale feasible on edge devices. We are inspired by the fact that conventional binarization methods are built upon statistical quantization error minimization without considering to preserve the pairwise similarity relations between tokens. To this end, we customize binarization to softmax attention by mapping the original token features into compact binary codes in Hamming space using set of kernel-based hash functions, where the similarity can be measured by codes dot product. The hash functions for queries/keys are learned to encourage the Hamming affinity of a token pair to be close to the target obtained from the attention scores, in self- relf-supervised way. Extensive experiments have demonstrated that EcoFormer saves significant on-chip energy footprint while achieving comparable performance with standard attentions on ImageNet- 1K, Long Range Arena and CIFAR-100. In terms of the future work, we can further binarize the value vectors in attention, multi-layer perceptrons and non-linearities in Transformer to make it fully binarized for more significant on-chip energy-saving. We may also extend EcoFormer to other NLP tasks such as machine translation and speech analysis tasks to make it more impactful wider communities.
Limitations and societal impact. We have shown that EcoFormer is more energy- compared to the standard attention. However, in practice, the addition operations between binary codes and floating-pott numbers will require specialized GPU kernels (e.g., customized CUDA operators) for further acceleration. Moreover, for the short sequence scenario, our EcoFormer suffers from severe performance drop due to the limited representational capability. Our work potentially brings some negative societal impacts that training large Transformer models requires extensive computations, resulting in financial and environmental costs. A promising solution to jointly optimize training and inference efficiency.
10

---

References
A. Andoni, P. Indyk, T. Laarhoven, I. Razenshteyn, and L. Schmidt. Practical and optimal Ish for angular distance. NewrIPS, volume 28, pages 1225-1233, 2015.
H. Bai, W. Zhang, L. Hou, L.. Shang, Jin, X. Jiang. Q. Liu, M. Lyu, and I. King. Binarybert: Pushing the limit hert quantization. ACI, pages 4334-4348, 2021.
[] Y. Bai, Y.-.. Wang, and Liberty. Proxquant: Quantized neural networks via proximal operators. In ICLR, pages 1-19, 2019.
[4] Beltagy, M. Peters, and A. Cohan. Longformer: The long-document transformer. arXiv preprint arXiv2200.005 2020.
[5] Y. Bengio. Estimating or propagating gradients through stochastic neurons. arXiv preprint Ii:: 2013.
[6] A. Bulat and G. Tzimiropoulos. Xnor-net++: Improved binary neural networks. In BMVC, page 62, 2019.
[7] M. S. Charikar, Similarity estimation techniques from rounding algorithms. STOC, pages 388,88 2002.
[8] H. Chen, Y. Wang. C. Xu, B. Shi, C. Xu, Q. Tian, and C. Xu. Addernet: Do we really need multiplications in deep learning? In CVPR, pages 1468-1477 2020.
[9] K. M. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos, P. Hawkins, J. Q. Davis, A. Mohiuddin, L. Kaiser, D. B. Belanger, L. Colwell, and A. Weller. Rethinking attention with performers. In ICLR, pages 1-38, 2021.
[10] X. Chu. Z. Tian, Y. Wang, Zhang, H. Ren, X. Wei, H. Xia, and C. Shen. Twins: Revisiting the design of spatial attention in vision transformers. NeurlPS, pages 9355-9366, 2021.
[11] M. Courbariaux, Y. Bengio, and J.-P. David. Binaryconnect: Training deep neural networks with binary weights during propagations. NewrIPS, volume 28, pages 3123-3131, 2015.
[12] G. Daras, N. Kitaev, A. Odena, and G. Dimakis. Smyrf-efficient attention using asymmetric clustering. In NeurlPS, volume 33, pages 6476 6489,, 2020.
[13] Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In SoCG, pages 353-262,00 2004.
[14] M. Dehghani, S. Gouws, O. Vinyals, J. Uszkorcit, and Kaiser. Universal transformers. In ICLR, pages 1-23, 2019.
[15] J. Devlin, M. Chang. K. Lee, and K. Toutanova. BERT:
pre-training of deep bidirectional transformers for language understanding. In J. Burstein, C. Doran, and T. Solorio, editors, NAACL-HLT, pages 4171-4186. 2019.
[16] R. Ding, T.W.. Chin, Z. Liu, and D. Marculescu. Regularizing activation distribution for training binarized deep networks. In CVPR, pages 11408-1144 1141,, 2019.
[17] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenbom. X. Zhai, T. Unterthiner, M. Dehghani, M. Min- derer, G. Heigold, Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x 16 words: Transformers for image recognition at scale. ICLR, pages 1 1-21, 2021.
[18] S. K. Esser, McKinstry, Bablani, R. Appuswamy, and D. S. Modha. Learndd step size quantization. In ICLR, pages 1 12, 2020.
[19] A. Gionis, P. Indyk, and R. Motwani, Similarity search high dimensions via hashing. Vldb, page 518-529, 1999.
[20] Y. Gong, Lazebnik, A. Gordo, and Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. TPAMI, 35(12)22916 2929629999222222 2012.
[21] S. Han, X. Liu, H. Mao, J. Pu, A. Pedram, M. A. Horowitz, and W. J. Dally. Eie: Efficient inference engine compressed deep neural network. ACM SIGARCH Computer Architecture News, 44(3):243-24, 2016.
[22] M. Horowitz. 1.1 computing's 's energy problem (and what we can do about it). In ASSCC, pages 10 14, 2014.

---

[23] L. Hou and J. T. Kwok. Loss-aware weight quantization of deep networks. In ICLR, pages 1-16, 2018.
[24] I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio. Binarized neural networks. In NeurlPS, pages 4107-4115, 2016.
[25] I. Hubara, M. Courbariaux, D. Soudry, R. El-Yas Yaniv, and Y. Bengio, Quantized neural networks: Training neural networks with low precision weights and activations. JMLR, 18(1):6869-6888, 2017.
[26] A. Jaegle, F. Gimeno, A. Brock, O. Vinyals, A. Zisserman, and J. Carreira. Perceiver: General perception with iterative attention. In ICML, pages 4651-4664, 2021.
[27] S. Jung, C. Son, S. Lee, J. Son, J.JJ Han, Y. Kwak, S. J. Hwang, and C. Choi. Learning to quantize deep networks by optimizing quantization intervals with task loss. In CVPR, pages
2019.
[28] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In ICML, pages 5156-5165, 2020.
[29] N. Kitaev, L. Kaiser, and A. Levskaya. Reformer: The efficient transformer. In ICLR, pages 1-12, 2020.
[30] A. Krizhevsky, Sutskever, and E. Hinton. Imagenet classification with deep convolutional neural networks. In NeurlPS, volume 25, pages 1106-1114, 2012.
[31] B. Kulis and Grauman. Kernelized locality-sensitive hashing. TPAMI, 34(6):1092- 2011.
[32] X. Lian, Z. Liu, Z. Song, Dai, W. Zhou, and X. Ji. High-performance fpga-based enn accelerator with flock-floating-piin arithmetic. TVLSI, 27 2019.
[33] G. Lin, C. Shen, Q. Shi, A. Van den Hengel, and D. Suter. Fast supervised hashing with decision trees for high-dimensional data. CVPR, pages 1963-1970, 2014.
[34] X. Lin, C. Zhao, and W. Pan. Towards accurate binary convolutional neural network. In NeurlPS, pages 344-35 114-352,22 2017.
[35] W. Liu, C. Mu, S. Kumar, and S.-F. Chang. Discrete graph hashing. In NeurlPS, volume 27, pages 3419-3427, 2014.
[36] W. Liu, J. Wang, R. Ji, Y-GG, Jiang, and S.-F. Chang, Supervised hashing with kernels. In CVPR, pages 2074-2081, 2012.
[37] W. Liu, J. Wang. S. Kumar, and S.-F. Chang. Hashing with graphs. In /CML, pages 1 1-8, 2011.
[38] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In ICCV, pages 10012-10022, 2021.
[39] Z. Liu, B. Wu, W. Luo. X. Yang. W. Liu, and K.-T. Cheng. Bi-real net: Enhancing the performance of 1-bit cnns with improved representational capability and advanced training algorithm. In ECCV, pages 722-737, 2018.
[40] Loshchilov and F. Hutter. Decoupled weight decay regularization, In ICLR, pages 1- 1-18, 2019.
[41] J. Lu, J. Yao, J. Zhang, X. Zhu, H. Xu. W. Gao, C. Xu, T. Xiang, and L. Zhang. Soft: Softmax-free transformer with linear complexity. In NeurIPS, volume 34, pages 21297-21309, 2021.
[42] B. Martinez, J. Yang. A. Bulat, and G. Tzimiropoulos. Training binary neural networks with real-to- real-to-binary binary convolutions. In ICLR, pages 1-11, 2020.
[43] A. Mishra and D. Marr. Apprentice: Using knowledge distillation techniques to improve low-precision network accuracy. In ICLR, pages 1-17, 2018.
[44] M. Norouzi and D. J. Fleet. Minimal loss hashing for compact binary codes. In ICML, pages 353-360, 2011.
[45] H. Peng, N. Pappas, D. Yogatama, R. Schwartz, N. Smith, and L. Kong. Random feature attention. In ICLR, pages 1-19, 2021.
[46] Н. Qin, Y. Ding, M. Zhang, Q YAN, A. Liu, Q. Dang, Z. Liu, and X. Liu. BiBERT: Accurate fully binarized BERT. In ICLR, pages 1-24, 2022.
[47] Z. Qin, W. Sun, H. Deng. D. Li. Y. Wei, B. Lv. J. Yan, L. Kong, and Y. Zhong, cosformer: Rethinking softmax in attention. In ICLR, pages 1-15, 2022.
12

---

[48] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In NeurlPS, volume 20, pages 1177-1184, 2007.
[49] Rastegari, V. Ordonez. Redmon, and A. Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. In ECCV. pages 525-542, 2016.
[50] H. Ren, H. Dai. Z. Dai, M. Yang. J. Leskovec, D. Schuurmans, and B. Dai. Combiner: Full attention transformer with sparse computation cost. In NeurIPS, volume 34, pages 22470-22482, 2021.
[51] H. Sharma, J. Park, N. Suda, I., Lai, B. Chau, Chandra, and H. Esmacilzadeh. Bit fusion: Bit-level dynamically composable architecture for accelcrating deep neural network. ISCA, pages 764-775, 2018.
[52] S. Shen, 7. Dong, J. Ye, I., Ma, Z. Yao, A. Gholami, M. W. Mahoney, and K. Keutzer, Q-hert: Hcssian based ultra low precision quantization of hert. In AAAI, volume 34, pages 8815-8821, 2020.
[53] H. Shu, J. Wang, H. Chen, I. Li, Yang, and Y. Wang. Adder attention for vision transformer. In NeurlPS, volume 34, pages 19899-99990099 2021.
[54] Z. Sun, Y. Yang. and S. Yoo. Sparse attention with learning to hash. In ICLR, pages 1-20, 2022.
[55] Y. Tay, M. Dehghami. S. Abnar, Y. Shen, D. Bahri, P. Pham, J. Rao, L. Yang. S. Ruder, and D. Metzler. Long range arena: A benchmark for efficient transformers. In ICLR, pages 1-19, 2021.
[56] H. Touvron, M. Cord, M. Douze, F. Massa, Sablayrolles, H. Jégou. Training data-efficient image transformers & distillation through attention. In JCML, pages 10347,1035,, 2021.
[57] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In NeurlPS, volume 30, pages 5998-6008, 2017.
[58] A. Vyas, A. Katharopoulos, and F. Fleuret. Fast transformers with clustered attention. In NeurlPS, volume 33, pages 21665-21674, 2020.
[59] J. Wang, S. Kumar, and S.-F. Chang. Semi-supervised hashing for large-scale search. TPAMI, 34(12):2393- 2406, 2012.
[60] S. Wang, B. Li. M. Khabsa, H. Fang, and H. Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.0 04766, 2020.
[61] W. Wang, E. Xie, X. Li, D.-. Fan, K. Song, D. Liang, T. Lu, P. Luo, and L. Shao, Pyramid vision transformer: A versatile backbone for dense prediction without convolutions. In ICCV, pages 568-578, 2021.
[62] Wang, E. Xic, X. Li, D.-P. Fan, K. Song, D. Liang, T. Lu, P. Luo, and L. Shao. Pvtv2: Improved basclines with pyramid vision transformer. Computational Visual Media, 8(3):455-5 4244, 2022.
[63] Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In NeurlPS, volume 21, pages 1-8, 2008.
[64] Y. Xiong, Z. Zeng, R. Chakraborty, M. Tan, G. Fung, Y. Li, and V. Singh. Nyströmformer: A nystöm-based algorithm for approximating self-attention. In AAAL, volume 35, page 14138, 2021.
[65] C. Yan, Gong, Wei, and Y. Gao. Deep nieti-view enhancement hashing for image retrieval. TPAMI. 43(4):1445-144 1445-1411, 2020.
[66] A. H. Zadeh, 1. Edo, O. M. Awad, and A. Moshovos. Gobo: Quantizing iitention-based nlp models for low latency and energy efficient inference. In MICRO. pages 81 811-824, 2020.
[67] O. Zafrir. Boudoukh, Izsak, and M. Wasserblat. Q8bert: Quantized Sbit bert. In EMC2-NIPS, pages 36-39, 2019.
[68] S. Zhou, Y. Wu, Z. Ni, X. Zhou, H. Wen, and Y. Zou. Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients. arXiv preprint arXiv: 1606.06660, 2016.
[69] C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal. Algorithm 778: L--fgs-h: Fortran subroutines for large-scale bound-constrained optimization. ACM TOMS, 23(4):550-560, 1997.
[70] C. Zhu, W. Ping, C. Xiao, M. Shocybi, T. Goldstein, A. Anandkumar, and B. Catanzaro. Long-short transformer: Efficient transformers for language and vision. In NeurIPS, volume 34, pages 17723-17736. 2021.
[71] B. Zhuang, Lin, Shen, and I. Reid. Fast training of triplet-based deep binary embedding networks. In CVPR, pages 5955- 5964,99442222 2016.
[72] B. Zhuang, C. Shen, M. Tan, L. Liu, and I. Reid. Structured binary neural network for accurate image classification and semantic segmentation. In CVPR, pages 413 413-422, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See abstract and introduction.
(b) Did you describe the limitations of your work? [Yes] See the conclusion Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the conclusion Section 6.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes] We have included the code and instructions needed the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the implementation details in Section 5.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] Error bars are not reported because it would be too computationally expensive. We use the same random seed as recent works for fair comparison.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the implementation details in Section 5.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 5.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [Yes] Code is included in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're
using/curating? [No] We use public datasets.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "mCY_ZVqAaCq", "reviewer": "Reviewer_M9L7", "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.\n", "questions": "**Questions and Suggestions**\n  - 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?\n  - 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:\n    - SMYRF: Efficient Attention using Asymmetric Clustering (NeurIPS 2020)\n    - Fast Transformers with Clustered Attention (NeurIPS 2020) \n    - Sparse Attention with Learning to Hash (ICLR 2022) ", "limitations": "These are discussed.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n  - The paper is well written. The language is clear and the flow of logic makes the paper easy to understand.\n  - 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.\n\n**Weakness** \n  - 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.\n  - 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). \n  - 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.\n\n[1] Long Range Arena: A Benchmark for Efficient Transformers\n\n[2] Adder Attention for Vision Transformer", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FDyN9Q7F9wJ", "reviewer": "Reviewer_THJi", "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.", "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]).\n\n[2] Combiner: Full Attention Transformer with Sparse Computation Cost, NeurIPS'21", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nWeaknesses: 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.\n1) 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.\n2) 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.\n3) 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.\n\n[1] Ten Lessons From Three Generations Shaped Google’s TPUv4i, ISCA'21\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7ODSGDPNTTW", "reviewer": "Reviewer_BP1F", "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.", "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? \n2. 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?\n", "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.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The motivation of this work is promising and binarizing the Transformers through kernelized hashing functions in a self-supervised way is novel.\n2. In this paper, authors explicit the idea and methods clearly and easy to follow how they solve the whole optimization problem.\n3. Experimental results on ImageNet show high efficiency compared with the baselines.\n\nWeaknesses:\n1. Sec. 4.2 seems to have some inconsistent size of matrices or vectors, which makes this key part hard to follow and misunderstanding.\n2. 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.\n3. In the section of experiments, tables show the number of additions and multiplications but the details of how to calculate them are missed.\n\n[1] Liu, Zechun, et al. \"BiT: Robustly Binarized Multi-distilled Transformer.\" arXiv preprint arXiv:2205.13016 (2022).", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept