Linear Log-Normal Attention with Unbiased Concentration
Authors: Yury Nahshan
Joseph Kampeas
Emir Haleva
Venue: ICLR 2024 poster (2024)
Keywords: Neural Networks
Transformers
Self-Attention
Linear Attention
Scalable Transformers
Efficient Attention
Attention with Linear Complexity
Linearized Attention
Self-Attention Analysis
Primary area: general machine learning (i.e., none of the above)
TL;DR: The quadratic complexity of the attention limits the scalability of the transformer models. We propose Linear Log-Normal Attention that offers linear complexity while maintaining key features of the original attention mechanism.

Abstract: Transformer models have achieved remarkable results in a wide range of applications. However, their scalability is hampered by the quadratic time and memory complexity of the self-attention mechanism concerning the sequence length. This limitation poses a substantial obstacle when dealing with long documents or high-resolution images. In this work, we study the self-attention mechanism by analyzing the distribution of the attention matrix and its concentration ability. Furthermore, we propose instruments to measure these quantities and introduce a novel self-attention mechanism, Linear Log-Normal Attention, designed to emulate the distribution and concentration behavior of the original self-attention. Our experimental results on popular natural language benchmarks reveal that our proposed Linear Log-Normal Attention outperforms other linearized attention alternatives, offering a promising avenue for enhancing the scalability of transformer models.

Published as a conference paper at ICLR 2024
LINEAR LOG-NORMAL ATTENTION WITH UNBIASED CONCENTRATION
Yury Nahshan, Joseph Kampeas and Emir Haleva
Distributed and Parallel Software Lab, Huawei Technologies Email: {first. 1 last] hhuawei...... com
@
ABSTRACT
Transformer models have achieved remarkable results wide range of applica- tions. However, their scalability is hampered by the quadratic time and memory complexity of the self-attention mechanism concerning the sequence length. This limitation poses substantial obstacle when dealing with long documents or high- resolution images. In this work, we study the sell-attention mechanism by analyz- ing the distribution of the attention matrix and its concentration ability. Further- more, we propose instruments to measure these quantities and introduce a novel self-attention mechanism, Linear Log-Noon -ormal Attention, designed to emulate the distribution and concentration behavior of the original self-attention. Our exper- imental results popular natural language benchmarks reveal that our proposed Linear Log-Normal Attention outperforms other lincarized attention alternatives, offering a promising avenue for enhancing the scalability of transformer models.
INTRODUCTION
Transformer models, proposed by (Vaswani et al.] 2017). have become widely used deep learn- ing architectures that have achieved state-of-the-art performance in various fields, including Natural Language Processing (NLP) (Brown et al.) 20200] Devlin et al. 2018), Computer Vision (CV) (Doso-) vitskly et al. (020)). Neural Machine Translation (NMT) (Chen et al. 2018). Document Summa- rization (Zhang al.] 2019 Pilault et al. 2020), and Protein Structure Prediction (Bahdanau al.] 2015). The main component of the Transformer model is an attention mechanism that identifies complex dependencies between tokens and efficiently captures tokens' correlation. However, stan- dard self-attention suffers from quadratic memory and computation complexity, which arises from the attention matrix, where N is the sequence length. This problem is particularly significant during training, as it requires storing the attention matrix for gradient computation. Consequently, this significantly hinders the training of Transformer models with long sequences.
Recently, have observed increasing interest in training Transformer models with long quences, especially when considering large language models (Scao et al.) 2022) Zhang et al.) [022]] Chowdhery al. 2022). Various approaches address the quadratic memory issue in self-attention. One class of the methods sparse-attention, which aims to perform only a subset of the attention computations while preserving the softmax function (Child al. 2019
[ Zaheer al. (2020). Another approach is Linearized Attention (LA), which replaces the softmax with a product of two functions (Choromanski et al., 2020) Katharopoulos
al. 2020). These methods reduce the computational and memory complexity of the attention mechamim while striving to maintain performance. One of LA's benefits is that it performs dense operations and does not require special HW or low-level implementation. However, despite their efficiency. LA methods often underperform compared to standard self-attention. Thus, understanding the reasons behind the superior performance of self- attention is crucial for designing effective LA method.
In this paper, we propose a systematic way to develop an LA method with comparable performance to the Softmax Attention (SA). First, we define holistic model of the SA and examine its char- acteristics. Then, we analyze the SA from three different perspectives, focusing on its statistical, informational, and algebraic properties. In particular, characterize the probability distribution of the attention matrix and prove its tor-normal nature. Moreover, we study the concentration behav- ior of the SA by analyzing its entropy and the spectral gap (Coste) 2017). Based on the proposed

---

Published as a conference paper at ICLR 2024
model, develop LA method that emulates the distribution and concentration behavior of the SA, achieving comparable performance. Finally, we evaluate the effectiveness of our method on popular NLP benchmarks and compare with other state-of-the-an methods. In summary, tribution is as follows:
We conduct an in-depth analysis of self-attention, characterizing its statistical, informa- tional, and algebraic properties.
Develop tools suitable for studying the concentration ability of the attention based the entropy and the spectral gap metrics.
Using the developed model and tools, we design Linear Log-Normal Attention (LLN At- tention) with comparable performance SA while requiring linear memory and computa- tional complexity in the sequence length.
We have made the code of our method available for MindSpord and PyTorch frameworks.
2 BACKGROUND AND RELATED WORK
In this section, we present a brief overview of the attention mechanism and various methods for efficient and linearized attention. We review the most relevant works in the field, classifying them into different types of attention methods such as sparse attention, low-rank projection, memory- based, kernel-based approximations, and clustering-based methods.
2.1 BACKGROUND ON SELF-ATTENTION
In the seminal study of (Bahdanau et al. 2015), the authors proposed the attention mechanism, which was subsequently incorporated into the Transformer model (Vaswani et al. 2017). Since then, attention has become a fundamental building block for many Transformer-basee models.
Consider sequence of N tokens, where each token represented by d-dimensional query, key, and value vectors, denoted as 1g [ and {v, J. respectively. The SA defined as:
Σ Mexp (q kj
Attn(g;: (k)..... kNJ. fu.....,,.. uN
(1)
Et Noxp (q:: ki)
where Keep is an exponential kernel used in the softmax function:
Keep (q:: k,)
Va
The recent study by (Wright & Gonzalez 202 has examined SA from the perspective of the kernel method. Notably, the formulation of SA in eq. (I) can be seen Nadaraya- Watson kernel regres- sion [Nadaraya] 1964), where estimating some unknown function with with distribution p(k: v) and density p(k) with kernel (Han al. 2022). Moreover, as shown by Tsai al. 2001)) other popular kernels, such as polynomial or Radial Basis Function (RBF), can be used instead of the exponential kernel. However, the performance may vary depending on the type of kernel. A kernel method perspective of the attention allows us to address the problem of attention lineariza- tion by using the connection between any kernel and its feature embedding function Q described by Mercer's 's theorem (Mercer 1909):
x(g, ky) (Q.)), ((k,)
gitee. gittc..com/yaahshanioo... huttrc//mmmmaaiiiiiaaaaoooaaaaao outth..ccmyyyaaaaaaallrreeeooooe
2

---

Published as a conference paper at ICLR 2024
2.2 LINEARIZED ATTENTION
In recent years, several techniques have been proposed to address the quadratic cost associated with SA. Based on the taxonomy by (Zhu et (00T), these techniques can be categorized into five types: i) sparse attention mechanisms with predefined patterns, including sliding window approaches such as Sparse Transformer (Child et al. (2119) Axial Transformer (Ho al. 2019). Blockwise Attention (Qiu et al.] 2019), Longformer (Beltagy et al. 2020), and BigBird (Zaheer et al., 2020), where some of these works (Wang et al. (021) manage to improve model convergence due noise reduction; ii) low-rank projection methods, including Linformer (Wang et al., (020), Synthesizer (Tay et al., 2020a), NystromFormer (Xiong et al. 2021). SkyFormer (Chen et al. 2021), and Cosformer (Qin et al. 2022b); iii) memory-based methods, such as Set Transformer (Lee et al.) 2018b) and Com- presssvve Transformers (Rae et al. 2019); iv) kernel-based approximation of the attention matrix, including Performer (Choromanski et al. 2020). Linear Transformers (Katharopoulos et al., 2020).
and RFA (Peng al.][2021), and v) similarity and clustering methods, including Reformer (Kitav et al. 2020). Routing Transformer (Roy et al. 2020), Sinkhorn Attention (Tay et al. (0200b) and Clustered Attention (Vyas et al., 2020).
Some of these methods combine multiple types of efficient attention mechanisms. For instance, (Zhu al. (22T) suggested a combination of low-rank projection and local window attention. Sim- ilarly, (Qin et al. 2022a) incorporate both kernel-based and block-wise attention in their approach. Our method also integrates kernel and block-wise techniques while suggesting a novel kernel ap- proach that differs from that of (Qin et al. (022a). By leveraging the benefits of multiple attention mechanisms, these techniques offer more efficient and accurate models for various NLP tasks.
Kernel-based attention requires selecting feature embedding function & to compute the LA kernel eq. (3 Linearized attention can then be defined as:
Σn (o(9.) (kjkk Σ 1 e (Q:)TT Tx vj D Σ xx (k))
D EE 4x (kj)u
Attmangg; (k))) (ug}
(4)
The choice of feature embedding function is crucial, as we demonstrate later in section 4 Differ- ent works suggest different types of embedding functions for this purpose. For example, Performer (Choromanski et al. 2020) uses an exponential function, Linear Transformers (Katharopoulos et al.) 2020) uses the ELU function, and RFA (Peng et al., (02T) uses trigonometric functions to approx- imate the Gaussian kernel with Fourier features. However, none of these works have analyzed the properties of the attention mechanism induced by these functions.
3 DISSECTING SOFTMAX ATTENTION
In the previous section, discussed the LA concept. Although this concept may seem straight- forward, creating an LA mechanism that effectively handles complex tasks presents a challenging problem. Typically, the LA of the form in eq. (4) performs worse than the SA. To gain insight into the superiority of the SA, we conduct a thorough analysis of its properties. We start by character- izing the distribution of the attention matrix since it is a core element of the attention mechanism. Then, we study the connection between its entropy, spectral gap, and concentration ability of the self-attention.
Our model assumes that queries and keys approximately follow a Gaussian distribution. This assumption reasonable due to the Central Limit Theorem (CLT) (Lee et al.) 2018a) and accepted in literature for tractability purposes (Toffe & Szegedy 2015) Banner et al. 2018). Moreover, let us assume the mean of queries and keys is approximately zero, which is a valid assumption due to the layer normalization presence in the Transformer models.
We begin our analysis by formalizing model based on the SA from Equation I
Rdd be a Gaussian vectors, where elements qie NN(0, of) and Kje ~ (0, of), VI. Let aij = -T vd the attention score of pair i,j, whose variance can be expressed as o = oZ + Cerosso where Caross is the pross-covariance of the squared queries and keys (Goodman 1960). We define temperature of the SA
Model Definition. Let q.,
3

---

Published as a conference paper at ICLR 2024
1
Tsm
(5)
Osm
V
0 + Ceross
Denote āig aij / amm and let piSM) E NxN the SA matrix, where N sequence length such that:
G Tem
P(SM)
21=1 eda/TTm
The form in Equation (6) is significant as it demonstrates the connection between SA and implicit temperature parameter imposed by the variance attention inputs. We can draw an analogy be- tween the SA training and stochastic processes, where controlling the temperature allows balancing between exploration and exploitation. High temperature results in equal probabilities for all tokens (exploration), whereas low-temperature results in a high probability for one or few tokens, empha- sizing it (exploitation of this particular token).
3.1 CHARACTERIZING DISTRIBUTION OF SOFTMAX ATTENTION
Let us now characterize the probability distribution of the SA. By analyzing its probability distribu- tion, we can gain valuable insights into the behavior of the SA and reveal its statistical properties. In particular, the distribution of P(MM) plays a crucial role quantifying the variability of its entries. This variability is closely related to the concentration ability of the SA, topic that we will explore in more detail in subsequent sections.
Proposition 3.1. Let q and & be Gaussian vectors, where qs o() and k, N(0, V. Then, for moderate values of og. and large enough N the distribution of p(SM) can be approximated by log-normal distribution with parameters pmm In o and o of Ceross.
The key behind the proof is approximate the denominator in eq. 6 with log-normal distribution by (Fenton) 1960) theorem. Then, since the numerator is also log-normal by the CLT, the resulting ratio can be approximated by log-normal distribution. leads the log-normal distribution of the p(SM) The detailed proof is given in Appendix A.5
The log-normal probability distribution of the SA matrix helps understand the attention mecha- nism. The skewness log-normal distribution emphasizes certain positions and enables concentra- tion. The temperature parameter controls uncertainty, influencing the balance between exploration and exploitation during training.
3.2 ANALYZING SELF-ATTENTIN THROUGH MARKOV CHAIN PERSPECTIVE
To delve deeper into the self-attention mechanism, we draw inspiration from the principles of Markov chains (Levin et al. 2006). Each row of the self-attention matrix represents the correlation between a specific token and all other tokens. These correlations closely resemble transition prob- abilities in classical Markov chains. The self-attention matrix continuously evolves during training. eventually converging to final model.
3.2.1 ENTROPY AND ATTENTION CONCENTRATION
A crucial parameter in understanding such stochastic system is its entropy, metric commonly used to measure the uncertainty or randomness associated with the state transitions of Markov chain. In the context of self-attention, entropy serves as valuable tool to evaluate the concentration ability of the self-attention. We refer to this as Attention Concentration (AC), which essentially measures the model's 's ability to direct its focus toward specific tokens, thereby extracting relevant information from the input sequence. Previous studies (Ghader & Monz 2017; Vig Belinkov] 2019) have proposed using entropy measure the AC. Lower entropy indicates greater focus
4

---

Published as a conference paper at ICLR 2024
Layer
0.8
10
0.4-
0.4
0.
Stop
S0cp
Stop
(a)
(b)
Figure 1: Temperature (left), entropy (center), and spectral gap (right) during training of the small RoBERTa model with single head per layer in every training step (X-axis).
few tokens, while higher entropy indicates more uniformly distributed attention. To formally define the entropy of the attention matrix ((SM) we average the entropy of individual rows as following:
N
N
H(P(SM)
1 N
(SM) kj
log, (P(S))
Note that by eq. (6). the attention matrix can be represented in terms of its temperature. To further explore the connection between the AC and temperature, present the following theorem, which characterizes the relationship between the entropy of the SA and its temperature:
Theorem 3.2. The entropy in eq. is monotonically increasing with temperature Tsm-
To prove the theorem, we consider the derivative of the entropy with respect to the temperature and show it always positive. For detailed proof, refer to Appendix A.441
According to Theorem 3.2 the entropy of the SA increases with the temperature, which controls the concentration of the SA. Essentially, a higher temperature results more dispersed distribution of attention. Conversely, a lower temperature makes it easier to focus specific tokens. Moreover, the temperature controls the exploration (higher entropy) and exploitation (lower entropy) of the states within the chain. Figure la shows how temperature decreases during training, resulting in a more confident state (lower entropy) Figure [b] Notably, while the first layers of the model retain high en- tropy, allowing exploration, the entropy of the middle layers decreases and becomes approximately zero, leading to exploitation those layers.
3.2.2 SPECTRAL GAP AND ATTENTION CONCENTRATION
In the analysis of Markov chains, the spectral gap is a valuable metric to consider because it pro- vides insights into the speed which the chain reaches its stationary state (Coste) 2017). In other words, it quantifies the rate of convergence, where the larger values of the spectral gap indicate a faster convergence process, while smaller suggests slower one. When applied to attention mechanisms, the spectral gap can provide insights into the rate at which the attention mechanism focuses specific elements within the input sequence. Including the spectral gap in our analysis allows us a more comprehensive understanding of the SA mechanism from an algebraic perspective.
The spectral gap measures the difference between the first and the second largest eigenvalues. Since the attention matrix is a stochastic matrix (Meyer) 2000), it follows from the Frrron-Frooeniuss Therefore, the spectral gap is A21, where X is the second largest eigenvalue. In Theorem 3.3 we establish a relationship between the variance of the attention matrix and the spectral gap.
theorem (Samelson) 1957) that its largest eigenvalue is X
Theorem 3.3. Let P E N right stochastic matrix with eigenvalues Ai....,Ay AN ordered by their AA Let dmaz be the major principal component of the centered version of P. Then, X2 D where o represents the amount of variance in the direction specified by the major principal component Umar-
absolute values, where A1 = A2/2....
5

---

Published as a conference paper at ICLR 2024
To prove this theorem, deflate the A of the attention matrix and express the variance in the direction of the major principal component. The detailed proof is provided Appendix A.4.2
Theorem 3.4. The variance of the attention matrix P(SM) is monotonically decreasing with temper- ature Tsm-
To prove this theorem, we consider the derivative of the variance with respect to the temperature and show it is always negative. For detailed proof, refer Theorem A.3
According to Theorem 3.3 the magnitude of variability in the direction of the major principal com- ponent mmx is equal A2, consequently, the spectral gap increases as the variability decreases. To- gether with the Theorem 3.4, we can conclude that the spectral gap increases with the temperature, similarly to the entropy. However, biasing the stochastic matrix towards a particular column also af- fects the variability. When P is biased toward a specific column, the variability within the columns decreases, resulting
smaller value of 22 and a higher spectral gap, regardless of the temperature. Therefore, we can conclude that the spectral gap only increases with temperature when the attention matrix is unbiased. This phenomenon led us refer to the spectral gap as a measure of Unbiased Attention Concentration. Figure [ depicts the change in the spectral gap during training. In most layers, the spectral gap decreases during training, indicating improved AC. However, in some lay- ers, the spectral gap increases while the temperature remains constant, suggesting that the attention matrix is biased. This observation justifies that the spectral gap carries additional information to entropy.
4 DESIGN OF LINEARIZED ATTENTION
In the previous section, we presented holistic model of SA and conducted thorough analysis of its properties. Specifically, we identified the log-normal distribution of the SA matrix. Additionally, we analyzed concentration behavior dictated by the temperature parameter. We can measure AC using the entropy (biased) and the spectral gap (unbiased) metrics. In this section, we design the LA method based on the defined model, which resembles similar characteristics and imitates SA behavior. In particular, our LA model should have log-normal distribution with similar moments. Moreover, it should emulate the concentration pattern of the SA by matching its entropy and spectral gap curves. As a result, we expect our LA method to achieve performance comparable to the SA.
4.1 LINEAR LOG-NORMAL ATTENTION
Designing LA according Equation requires selecting feature embedding function T, element of this attention. The choice of this function has a crucial effect on the LA performance. According to our model, we start by satisfying the log-normality requirement, as most functions do not have this property. For example, the Rectified Linear Unit (ReLU) can not produce log-normal distribution as being almost linear. On the other hand, the exponential function induces lor-nolmal distribution for Gaussian inputs, which justifies its selection as a feature embedding function Q. However, to match the concentration behavior of the SA, we must force the LA to produce similar entropy and spectral gap curves with respect to the temperature as in SA. To achieve this goal, we introduce additional parameters, which we tune to perform moment matching between the LA distribution and that of the SA.
Accordingly, let us denote by Φo(() = e0 and (x(k)) = sk the feature embedding functions, where a, B R+ hyper-parameters that must be carefully selected to ensure LA closely approximates the SA. We define the Linear Log-Normal (LLN) Attention as:
ΣN ea ek
Attmain (g (ki....,kN (UI.... UN
c007 ek V.
(8)
ΣN
Where each entry of the LLN attention matrix can be expressed as:
cog Ak;
P(LnN)
(9)
Σ co 9k
Similarly to the analysis of the SA model, we assume zero mean of queries and keys. Then, to show that the LIN Attention matrix follows log-normal distribution, we prove the following:

---

Published as a conference paper at ICLR 2024
1.0
1.0
0.8
142
0.6
Softmax
Softmax
Quadratic
Quadratic
Rell
RellI
Quadratic linear
Quadratic linear
Rell linea
0.2
Relli linear
LLN moment matching
LLN moment matching
LLN ==
LLN
0.0
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
0.25
0.30
0.75
1.00
1.25
1.50
1.75
2,00
Figure 2: Comparison of entropy (left) and spectral gap (right) for various types of attention kernels. The figure shows that the entropy and spectral gap of the LLN Attention with the moment matching is similar to those of the SA.
Proposition 4.1. Let q and k be Gaussian vectors, where qs ~ NN(0,0)) and k; ~ NO Vi Then, for moderate values of og and of. the distribution of P(INN) can be approximated by log-normal distribution with variance Tie a- (a20² + (P + b, where a and b are constants.
The main steps of the proof are approximating the numerator and denominator in eq. (9) using the log-normal distribution, following the theorem by (Fenton) [ 1600). Then, split the analysis into three cases to express the variance, as suggested by (Romeo et al. 2003). The detailed proof is given in Appendix|A.6
Further, we have to ensure the concentration behavior of the LLN Attention is similar to that of the SA. To that end, it is necessary to determine appropriate values for the hyperparameters a and B. In the following, of the SA. Since the log-normal distribution is parameterized only by the first and second moments, align the LLN Attention distribution with the SA by ensuring equivalence of the first two moments.
estimate these parameters by performing moment matching to the distribution
Interestingly, Proposition 4.1 implies linear dependency between the variance of queries and keys and oin This linear connection facilitates the calculation of constants a and It allows the appli- cation of linear interpolation on the randomly generated Gaussian samples and k to perform the moment matching between LLN and SA. We provide a detailed description of the technical aspects of this moment-matching technique in Appendix A.7
Finally, by requiring Onn = Osm and expressing it in terms of a and 8, we can determine and b parameters. We point out that there no closed analytical solution for which both the mean and variance of LLN and SA align. Yet, since the concentration is mostly affected by the variance of the attention matrix, we only match the variances the LLN and SA. Further, to simplify the solution, we also let a²o² 32 _02. Hence, we obtain the following:
6
10 b)
(10)
220
22
A detailed derivation of Equation (10) is given in Appendix A.7 Note that, like in the SA, we can introduce a temperature parameter of the LLN Attention that controls the concentration. Specifically, let us define the temperature of the LLN Attention to be:
(11)
aa (a + (P +b
In Figure 2
we demonstrate that the moment matching essential to align the entropy and the spectral gap of the LLN Attention with those of the SA to achieve the required concentration. More- over, other popular kernels, such as quadratic, ReLU, and their linear counterparts, are indifferent to the temperature, which may result in poor concentration and potentially degraded performance. In conclusion, LLN Attention satisfies the desired normall distribution property and concentration behavior required by the SA model. Therefore, it should achieve comparable results the SA.

---

Published as a conference paper at ICLR 2024
4.2 THE OVERALL ARCHITECTURE
In this section, we present the experimental re- sults of the LLN Attention method on NLP tasks, while more experiments on Image Classi- fication and LRA (Tay al., (2020c) benchmark available in the Appendix A.8
Feed Forward
LLN Transfo Layer
The LLN Attention effectively scales to long sequences while maintaining high concentra- tion, allowing capturing long-range interac- tions. However, for short-range connections, may less effective. Recently, a study by (Qin al. 2022a) emphasized the attention di- lution issue of LA methods. Specifically, LA may overlook neighboring structures, leading to the "dilution" short-range interactions. To
AL Dieg Alseniin
LLN Attention
Disg Attention
Figure 3: LLN Transformer layer architecture.
address this issue, the authors proposed a hy- brid approach that combines LA with block-
diagonal attention, which retains the O(N) memory and computational complexity of LA. This block-diagona attention is regular SA applied on smaller pieces of the input, computing only the diagonal of the original attention matrix. Such block-diagonal attention can scale to longer sequences, but it is useful to improve the performance of the L.A method.
We incorporate this technique into LLN Attention, combining the LLN and block-diagone attention into a unified layer by averaging the outputs of both components Figure 3 While the block-diagonal mechanism effectively captures short-range interactions within its confined block scope, LLN excels in catching broader, long-range connections. This combined approach enhances the performance of LLN Attention and stabilizes training by reducing the magnitude of the gradients (Qin et al. 2022a).
EXPERIMENTS
We first pre-train the bidirectional RoBERTa encoder model (Liu et al. 2019) using LLN Attention on the Vi0 corpus (Merity et al.) 20.8). During pre-training, we monitor the convergence of the model and compare performance to the SA model. In Appendix AA.8.]. we show that the loss of the LLN Attention closely follows the loss of the SA, indicating similar convergence behavior.
Next, to evaluate the performance of LLN Attention downstream tasks, we fine-tune our pre- trained model on several NLP tasks from the General Language Understanding Evaluation (GLUE) dataset (Wang et al. 2018). These tasks include Multi-Genre Natural Language Inference (MNLD, Question-answering Natural Language Inference (QNLI), Quora Question Pairs (QQP), and Stan- ford Sentiment Treebank (SST-2). For all experiments, use the Fairseq framework (Ott al.)
2019 with the default configuration and hyperparameters of the RoBERTa-base model
Table provides detailed comparison of the accuracy achieved by each method each task. The LLN Attention method outperforms the other LA methods with an average accuracy of 86.9%. These results confirm the superior capability of LLN Attention in achieving competitive perfor- mance with SA on a range of NLP tasks.
5.1 SPEED AND MEMORY CONSUMPTION
In this section, we evaluate the training time and memory usage the LLN Attention, comparing to the SA and Nyströmformer, which outperform most of the LA methods available. In the compar- ison, we used the RoBERTa-base model with a batch size of one and performed all measurements on commodity GPU.
The results Table 2 confirm that LLN Attention scales linearly with sequence length, as expected, and can handle at least four times longer sequences than SA. Moreover, the LLN Attention method
8

---

Published as a conference paper at ICLR 2024
Method
MNLI
QNLI
QQP
SST-2
Avg 1
SA baseline [Bahdanau et al.
2015)
80.3
87.2
89.9
90.6
87.0
Reformer (Kitaev et 2020)
35.4
63.2
50.9
49.8
Performer Choromanski et a.
2020
58.8
63.4
79.1
81.4
70.6
ELU Katharopoulos et al. 2020)
74.8
82.5
86.9
87.2
82.8
Longformer (Beltagy et al.
2020
77.2
85.5
88.6
83.7
Transformer LS Zhu et al.
2021)
77.0
84.8
86.8
90.2
84.7
TNN (Qin et al.
2023
76.72
85.06
88.3
90.6
85.17
T2 QQin et al.] 2022a)
77.28
85.39
88.56
90.71
85,48
CosForeer (Qn al.
2022b
76.7
89.2
91
85.6
T1 (Qin et al. 2022a
79.06
87.0
88.61
91.17
86.46
Flash (Hua al.
2022
79.45
87.1
88.83
90.71
86.52
Nyströmformer (Xrong et al. 2021
80.9(-1.5)
88.7(-16)
86.3(-1.)
91.4(+1.4)
86.8(-0.7
LLN Attention (Ours)
77.0
85.1
88.9
90.6
85.4
LLN+Diag Attention (Ours)
80.0
86.5
89.7
91.6
86.9
Table I: Accuracy achieved by various LA methods multiple NLP tasks from the GLUE dataset.
including MNLI, QNLI, QQP, and SST-2. The results Nyströmformer are given in (Xiong al.)
202T]. while the results of the rest are given in (Qin et al. 2022a). Note that for methods marked with which have a different baseline in the original paper, we also provide an accuracy drop in Q).
sequence length
Method
512
1024
2048
4096
8192
16384
Softmax Attention
4.
5.5
12.6
32.1
OOM
0OM
Nyströmlormer
4.
4.5
5.5
7.3
11.6
19.1
Memory [GB]
LLN Attention
4.1
4.4
3.7
7.5
12.
20.1
LLN+ Attention
4.1
4.6
6.1
8.1
13.4
23.
Softmax Attention
0.95
1.05
2.4
6.8
OOM
OOM
Nyströmformer
1.8
1.9
2.6
4.7
8.8
16.7
Time [sec/it]
LLN Attention
1.05
1.6
3.2
11.8
LLN+Diag Attention
1.2
1.3
1.9
3.6
6.9
13.3
Table 2: Memory usage and training time per iteration of SA, Nyströmformer, LLN, and LLN+Diag on RoBERTa model, with varying sequence lengths. "OOM" indicates an "Out Of Memory" error.
requires nearly the same amount of memory as Nyströmformer, with Diag Attention adding only a 10% memory overhead the LLN Attention. Notably, both LLN and LLN+Diag Attention demon- strate superior speed compared to Nyströmformer.
6 CONCLUSION
In this paper, we introduced novel LLN Attention method that incorporates the essential properties of the SA, such as the log-normal distribution of the attention matrix and its concentration behav- ior, while offering linear time and memory complexity. Our approach includes moment-matohe matching technique to match the attention matrix's 's nog-normal distribution with that of the SA, resulting in improved attention concentration and model performance. In addition, we conducted comprehen- sive analysis of the SA, characterizing its distribution and suggesting entropy and the spectral gap metrics for attention concentration analysis. To the best of our knowledge, this is the first work to study self-attention from this perspective. Finally, our experimental results demonstrated that LLN Attention outperforms many existing LA methods several NLP tasks, demonstrating its competi- tiveness and potential to enhance attention performance on long sequences. Overall, our contribution provides a foundation for future research and improvements in attention mechanisms.
ACKNOWLEDGEMENNS
We extend gratitude to Dr. Eliezer Levy, Dror Mizrachi, Dr. Su Teng, Wang ShengNan, and Dror Meirovich for their valuable support and fruitful discussions.

---

Published as a conference paper at ICLR 2024
REFERENCES
Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate, January 2015. 3rd International Conference on Learning Repre- sentations, ICLR 2015; Conference date: 07-05-2015 Through 09-05-2015.
Ron Banner, Yury Nahshan, Hlad Hoffer, and Daniel Soudry. ACIQ: analytical clipping for integer quantization of neural networks. CoRR, abs/1810.05723, 2018. URL pattp://aaaaa org/
abs/1810. 05723
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer, 2020. URL http://///xxvvvvrvoee
05150
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Mia Xu Chen, Orhan Firat, Ankur Bapna, Melvin Johnson, Wolfgang Macherey, George F. Foster, Llion Jones, Niki Parmar, Mike Schuster, Zhifeng Chen, Yonghui Wu, and Macduff Hughes. The best of both worlds: Combining recent advances in neural machine translation, 2018. URL http: /tttp://arxiv. http://wwwwia..aaaa////// hargg/abs/ine www.abb........./
Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang. Skyformer: Remodel self-attention with gaussian hanttsss//ariis..or//aa//////// 00035
kernel and nyström method, 2021.
Rewon Child, Scott Gray, Alec Radford, and llya Sutskever. Generating long sequences with sparse transformers, 2019. URL http: org/ http/bb///1990 100509
10509
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreca Gane, Tamás Sarlós, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, David Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with performers, 2020. URL https://
arxiv.org/abs: httpg/g///////......ggg 2209 1009.147941
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311 2022.
Simon Coste. The spectral gap of sparse random digraphs, 2017. URL https://arxiv.com
0te//1088.0050
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding, 2018. URL http://arxiv.org
025//180.00805
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 16 words: Transformers for image recognition at scale, 2020. /https://arxiv..om
Leslie H. Fenton. The sum of log-normal probability distributions in seatter transmission systems, 1960.
Hamidreza Ghader and Christof Monz. What does attention in neural machine translation pay at- tention to?, 2017. / 03348
Leo A. Goodman. On the exact variance of products. 1960. URL https: htmps://wwwe
Landfonlinee ine..iiie..e.. com atto///bs/1..... htt.a///...111000111111111111111
1960.10483369
Xing Han, Tongzheng Ren, Tan Minh Nguyen, Khai Nguyen, Joydeep Ghosh, and Nhat Ho. Robus- tify transformers with robust kernel density estimation, 2022. URL
abs/2210. 05794
Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans. Axial attention in multidi- mensional transformers, 2019. (tRt::/tt://aatt wwwp:wwwwwrgr../oo/ 1912. 121 12180
10

---

Published as a conference paper at ICLR 2024
Weizhe Hua, Zihang Dai, Hanxiao Liu, and Quoe V. Le. Transformer quality in linear time, 2022.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. CoRR, abs/1502.03167, 2015. URL http:://axxv..orr
abs/1502. 03167
lan Jolliffe. Principal component analysis, 2011. URL https:://ei.orr/10..11
978- 3- 642 04898-2 2 455]
Angelos Katharopoulos,
Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention, 2020. URL httpps///axxiv
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer, 2020.
2201..201..oo 04451
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes, 2018a.
Juho Lee, Yoonho Lee, Jungtack Kim, Adam R. Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer, 2018b. URL htttt::/aaxxv.orze/
00825
David A. Levin, Yuval Peres, and Elizabeth Wilmer. Markoy chains and mixing times, American Mathematical Society, 2006, URL /ttpp///p///eeoooorggogoo.o....
sdt=2000kctrertaaioosscd.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized BERT pretraining approach, 2019. htth:t:::/ http://aaxvvvv.o.e abaaabbss/1/ /190//197.... 11692
J. Mercer. Functions of positive and negative type, and their connection with the theory of integral equations, 1909.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. An amalysis of neural language modeling at multiple scales, 2018. URL htt.apppe//axxx..oo/////////.33
C.D. Meyer. Matrix Analysis and Applied Linear Algebru. Society for Industrial Mathematics, 2000. mat
URL http://wwww..taaaaaaaaaaaoaaocoa
html
Elizbar A Nadaraya. On estimating regression, 1964.
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli, fairseq: A fast, extensible toolkit for sequence modeling. CoRR, Abs/1904.01038.
2019. URLEttte /tttt::/ptaiii// org. 1et./11944.11333 C1038
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A. Smith, and Lingpeng Kong. Random feature attention, 2021. URLhtts:://arxi http///awiv...///aaaaa/aa/o wttp://wwwwww.a////1.2222222
Jonathan Pilault, Raymond Li, Sandeep Subramanian, and Chris Pal. On extractive and abstrac- tive neural document summarization with transformer language models, November 2020. URL
htttps://aclaatheooory.. org.////0ooor..//00//
emnlp- main. 748
Zhen Qin, XiaoDong Han, Weixuan Sun, Dongxu Li, Lingpeng Kong, Nick Barnes, and Yiran Zhong. The devil in linear transformer, 2022a. URL htttps://axxiv.orr//bbb/////
10340
Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjic Yan, Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention, 2022b. URL https:
// //a.xiv.org////aa....a abs/////////// httpo////////......oooo 2202 08791
Zhen Qin, Xiaodong Han, Weixuan Sun, Bowen He, Dong Li, Dongxu Li, Yuchao Dai, Lingpeng Kong, and Yiran Zhong, Toeplitz neural network for sequence modeling. In The Eleventh In- ternational Conference on Learning Representations, 2023. URL
het/foor i xmWsm4 xrrul

---

Published as a conference paper at ICLR 2024
Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self- attention for long document understanding, 2019. URL http: /ttE:://axxi...o arxiv.org/abs/191111
02972
Jack W. Rae, Anna Potapenko, Siddhant M. Jayakumar, and Timothy P. Lillicrap. Compressive transformers for long-range sequence modelling, 2019. URL http://arxiv. abs/
1911. 05507
M. Romeo, Da Costa, and F. Bardou, Broad distribution effects sums of lognormal random variables, apr 2003.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. confictcientcoonttttbbbabbbee sparse attention with routing transformers, 2020.
Hans Samelson. On the perron-frobenius theorem., 1957.
Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. Bloom: 176b- parameter open-access multilingual language model. arXiv preprint arXhv:2211.051000 2022.
Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng. Synthesizer: Rethinking self-attention in transformer models, 2020a. URL
Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da- Da-Cheng Juan. Sparse sinkhorn attention, 2020b. URL
wwwp:iii.orrgaeoooo hbtp:/bbss220..... 11296
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers, 2020c. URL //apss/////vvvv../ org. /bb 20111 04006
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. CoRR, abs/2012.128777 2020. URL //tp://aaavvvvv..v/.aa/eaaaaaiia wwtp:/oggggaaba/ooee
12877
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis- Chiil-Philippe Morency, and Ruslan Salakhutdinov. Transformer dissection: An unified understanding for transformer's attention via the lens of kemnel, 2019. URL http://aaxxvvvv..aaaaa// wwwpg//as/1999... 11775
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2017. URL http://arxxi
org/abs/ /106/ 03763 62
Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention in transformer language model, 2019. URL URU.///cpp.///rvvv..////bbbaa 002.9966044888 04284
Apoorv Vyas, Angelos Katharopoollss, and Francois Fleuret. Fast transformers with clustered atten- tion, 2020. URL Utt.itttees//rrrr...rrrr////////
Alex Wang. Amanpreet Singh. Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding, 2018.
URL http:/ttpp//iiii..ttt org/ abs 07444
Pichao Wang, Xue Wang. Fan Wang. Ming Lin, Shuning Chang, Wen Xie, Hao Li, and Rong Jin. KVT: k-nn attention for boosting vision transformers. CoRR, abs/2106.00515 2021. URL
https://arxxt org wtw./as/////oooooo../..ooo...a.r
Sinong Wang, Belinda Z. Li. Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity, 2020. URL /ttp:::///xxx...ooo/
http://awww...rg////////..00../ 04768
Eric W Weisstein. Normal product distribution, 2003.
Matthew A. Wright and Joseph E. Gonzalez. Transformers are hiw.://mmnnca.cceeeeeiiiiininnna non-mercer binary kernel machines, 2021. URL http:ppp///aai...rrr///////../..
12

---

Published as a conference paper at ICLR 2024
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: A nyström based algorithm for approximating self-attention, 2021.
/tL/pppp////ziiooooo///// 22122. 03902
Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences, 2020. URL httt::tt: / //anvvv www.iiiii.g.i..ooooooooooo abs 20100000...5
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christo- pher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.0106: 2022.
Xingxing Zhang, Furu Wei, and Ming Zhou. HIBERT: document level pre-training of hierarchical bidirectional transformers for document summarization, 2019. URL http://arxiv.ore
abs/1905.065
Chen Zhu, Wei Ping, Chaowei Xiao, Mohammad Shoeybi, Tom Goldstein, Anima Anandkumar, and Bryan Catanzaro. Long-short transformer: Efficient transformers for language and vision, 2021. URL uttpttps::/// www. /ttp///bbbb////2222222
13

---

Published as a conference paper at ICLR 2024
( d)
O x d
SoftMaxi
NO
K
K'
(a) Softmax attention
(b) Linear attention
Figure 4: block diagram of the computational complexity for the Softmax Attention and Lin- earized Attention.
A APPENDIX
A.1 FORMULATION OF THE SELF-ATTENTION (SA)
One of the most widely used variants of the self-attention mechanism is the scaled dot-product attention /aaswani et al. 2017). this formulation, the input vectors "I....,INv] == X E RR Nxd projected into query, key, and value vectors as follows:
9 9Nd = Q XW Rxd
k KN) K XW, E Rxd
(12)
[U....., UN| = V XW
_ Nxd
Here, W. q, WR. W. Raxd learnable parameter matrices. The attention function is then com- puted on the query, key, and value vectors using the following equation:
N
q. k vd
Aut(g: (k....., tui... uN
Σ j=1
softmax
(13)
The dot-product term is scaled by the factor vd
the stability of computations. This scaling
factor accounts for the variance of the dot-product q. ky, which grows with the dimensionality d. In this paper, we refer to this scaled dot prodpct attention as "softmax attention" or "standard attention," which is defined in eq. (1]
A.2 LINEARIZED ATTENTION (LA)
Let Q,K, E N xd denote the queries, keys, and values of the attention mechanism. Computing
noftmax--atennion with Equation equation 13 requires calculating the quadratic matrix QK
lg. kj], N which has a complexity of O O with respect to the sequence length N as illustrated in Figure 4a
Alternatively, if we can decompose softmax (QK into Q'K'T, we can use the associativity
property of matrix multiplication to compute Q' ( from right to left. Such decomposed computation has a linear complexity in the sequence length N, as illustrated in Figure 4b To obtain this decomposition, the un-normalized matrix eQKT is replaced with matrix ( (K)) T, where + is feature map that is applied row-wise, i.e. Q' +(Q) and K' @KK). This form of linear attention can be expressed as follows:
N P(g.) ( (T,kk Σn (T 13 ( i=1 (k:)
p(g.) Σ (kk))u7
Attn (q: (k...... kN), (e uN =
(14)
Due to aggregation over N elements both the numerator and denominator, the memory complexity of this linearized attention mechanism linear with respect to the sequence length N.
14

---

Published as a conference paper at ICLR 2024
A.3 KERNEL VIEW OF THE ATTENTIONN
The SA mechanism can be viewed as Nadaraya-Wannd Watson kernel regression (Nadrray 1964) as shown by Wright Gonzalez (202I). Specifically, the kernel density estimation (KDE) of some unknown function with joint distribution p(k, v) and density p(k) with kernel (Han et al. 2022 Therefore, the kernel function can used to express the self-attention mechanism as tollows:
Ej=1 klg kjju Attn(q (k1,...,,kN .,), ( uNl) = ΣN
N
(15)
Ei= n(q:: ki)
he KDE form of Equation (55) is generalization of softmax attention in Equation use softmax kernel
13 where we
kg) vid
Kam (am k,)
(16)
Interestingly, the kernel view of self-attention reveals that the functionality of the attention mecha- nism remains intact even when the kernel is modified. However, the performance of the attention mechanism can vary depending on the choice of the kernel function, as demonstrated by Tsai et al. (2019). It emphasizes the significance of considering different kernels and their impact on the per- formance of linearized attention. Additionally, the kernel view provides a valuable perspective for tackling the linearization problem within the framework of the kernel method.
According to Mercer's 's theorem (Mereer 1909), any rusitive-definiee kernel (Mercer kernel) can be represented as an inner product of symmetric features. Let X' E R II....,N E X with kernel function & X' > IR, then
2,) = (#x:), (22)))
(17)
where T X - Fx is function mapping the inputs to Hilbert space of feature functions FH. However, the dimensionality of Fx can be large or infinite, making explicit computation of the features infeasible. This is where the kernel trick comes in: the kernel function can be computed without explicitly computing the features. However, storing the attention matrix still requires (NN2) memory complexity. To address this issue, we can design a kernel function such that the dimensionality of Fx is much smaller than N, which allows for ((N) memory complexity. For example, consider @2 Q + Rdd and Φx K. - Rdd for some < N, the attention can be computed using the following linear kernel function:
k(q.: k,) (q,)), kk(k))
(18)
Consequently, using the associativity property described in section A.2 can be used to compute this kernel function with ((V) memory complexity.
A.4 ANALYSIS THE ENTROPY, VARIANCE AND SPECTRAL GAP OF THE SOFTMAX ATTENTION MARIX
We start our analysis by providing additional definitions which extend those in Section SectionBland and proving a couple of lemmas. Denote by N single row of the attention scores matrix A. By denoting a corresponding row of the normalized attention scores matrix À by z. such that ra I, we can write R single row of the softmax attention matrix from eq. (6) as:
p = softmax
(19)
25 e
Σ)=1
Where is the temperature of SA from eq.
5). Similarly to eq.
7), we define the entropy of single
row p as:
H(p) =
Σ Ps logg
(20)
15

---

Published as a conference paper at ICLR 2024
Additionally, we define a variance of the single p of the SA matrix as:
2
N
1
2
p
pi
Σ
Pj
N
(21)
==1
Denote Ex= Pr3:
Lemma A.1. The following holds Ex=1 pi(2;; - p1) =0
Proof.
N
Σ (x (1)
Σ pet;
1
Pi 1
Lemma A.2. Let p in eq. 199.. then the following holds.
Σ
(22)
Proof. By denoting 6; = 24 and substituting it into Equation 22 obtain
together with eq.
19 we
N
N
N
(r.
p))
6
28
8
Emme
e
E
Σ
2
Note that we can replace x; by 5; due to the translation invariance of the softmax. Thus, remains show that:
N
0
By expressing the equation from Lemma
A. terms of 8, we get
N
1
Σ
pi(a;
p))
8
8
N
5 Σ/ 1 e
Thus,
6
(23)
Split the sum in eq. 23 into two parts, first sum over the elements 8, and second over 8, 0. as following:
N
0
8
C
8
+
8.20
4,50
6.20
21
6 <1
Σ
E
0:
8
Σ
(x4 - 11)
1=1
16

---

Published as a conference paper at ICLR 2024
Theorem A.3. The variance og is monotonically decreasing with temperature
Proof. By taking the derivative of the of with respect to the we get.
002
p
2
Σ
N
(p:
1
Sp
-2
Σ
(ps
Dillo
Σ &ppp
N
1 72
05
N
N
N
N
1=1
1=1
N
1 2
1
1
Pi
p2+++ +
N
N 7
2 1 72 N
Σ p 04 11
Pi
1
Pi (2; 1D
N
N
2 1
pf - <)
72 N
Note that 1
(x, 1A) 2 0 as follows from the Lemma A.2
Lemma A.4. The following holds
11
Pe pr 1u)²
Proof.
N
N
Σ
pi(e; 11 u1) - -p²
a
i=1
N
pi(z; -1)2 -1)2+2 +2 Σ
Pi(x; - n) x² -22 -
i=1
Σ pi(z; 11)2 + 2p
p. 1))
pi 22²
A.4.1 PROOF OF THEOREM 3.2
Proof. To show that the entropy in eq. 7 is monotonically increasing with temperature, first show that the entropy of the single row eq. (20) of the SA matrix is monotonically increasing. To that end, we take derivative 2H of the entropy with respect the temperature and show that is always positive.
dr
Denote S = ENN
17

---

Published as a conference paper at ICLR 2024
The derivative of the single entry of p with respect to the temperature is given by:
dp: 0r
(- -
S e Σm=ee (-
g
72
Di
Ps
Pj
2j
72
1=1
N
72 Pi
Σ TyPT))
=
72 Di 11)
The derivative of the entropy from eq.
20
with respect to the temperature:
0H
8p: OT
N
1
0T
lpg)(ps) +
In
logz(p))
+
In
72
P2P(Ti -11)
Piri 1ogg (pt)
ps logg (pi)a +
1n2
Petii
P 2
Σ P:d 1ogg (p:)
Σ ps logg(p))
2
N
Pt
log (p:) -m)
(xt -4) loog 5)
Pi
T
N
plaj
log2 s
Pidy + loog Sp Sp--14
-1 Σ prJs
N
N
Σ
112
Pe(x; - = 33
33
Where, follows from Lemma A.4
Finally, since the entropy in eq. is the average entropy of the rows, the Theorem 3.2 follows.
1 N
H(P(SM)
Σ H(p))
(24)
N
A.4.2 PROOF THEOREM 3.3
The proof based on the Principal Component Analysis (PCA) (Jolliffe 2011 of the stochastic matrix P.
Proof. To start our proof, we first need to center matrix P in eq. 6 by deflating the first eigenvalue. Let = 1 = N EN Pij the vector mean of P. Note that v1 = is the cigenvector of P for which the following holds:
corresponding to the first eigenvalue
N
N
# T vi
1 N
3 Po. =1
(25)
N
18

---

Published as a conference paper at ICLR 2024
Thus, according the Wielandt deflation theorem the eigenvalues of the matrix P = P -1 are 0,
Furthermore, is important to note that the matrix is centered in both rows and columns as follows:
N
Σ
P = P
A11 A 1 NN = P 1
N = PI
1 -
Therefore, the empirical covariance matrix of P can be expressed as:
Ep = (P- (a (P- (1 = =P'P
Denote by 01.... ................................ N the eigenvectors of P, where ú1 corresponds the eigenvalue Å1 0. The variance in along the direction of the principal component 0; can be expressed as:
.......
JpEpū
U.P Pú: Pt. = X² 5. =
5:0;
Therefore, the variance maximized when ū; = 02. and X = of represents the amount of variance in the direction specified by the largest principal component of P.
Thus, X indicates the level variability matrix P along the direction specified by the major principal component P. Moreover, according to Theorem A.3] if the rank of matrix P remains unchanged, the variability should decrease as the temperature increases. However, if the matrix P biased towards a particular column, the variability within the columns decreases, resulting in smaller value of λ2. Consequently,
infer that the spectral gap, defined 7 |A2 < 1, increases with the temperature only when the stochastic matrix is unbiased.
0g
A.5 PROOF OF PROPOSITION
Proof. Generally, the product of two independent Gaussian variables has density in the form of a modified Bessel function of the second kind (Weisstein) 2003). When the vector dimensions sufficiently large, the Central Limit Theorem implies that the distribution of the dot product between and & can be approximated by Gaussian distribution with zero mean and variance o². As mentioned in section 3 the variance of q can be expressed as o² oद h Ceross where Ceross = Cov((", ) Cov(q, k)² is the cross-covariance of the squared queries and keys Gooddman 1960).
Therefore, due to the exponent in (6) the numerator is approximately a log-normal variable with zero mean and variance o²_ address the denominator, we must consider a sum of log-normal variables. Fortunately, Fenton (1960) theorem states that for moderate values of o², the sum of zero-mean i.idd normnlllal variables can be approximated by a log-normal variable with variance o3 and mean lg where:
(#'
1
3f =n
1ss is= = In -05)/2
For large N and moderate values of o², we have of < 0², and we can omit the o term for simplicity. Finally, since the ratio of lormnlrmal variables remains log-normal with mean -/4x and variance o², Proposition] 3.1 follows.
To empirically validate the assumption made in Proposition 3.1 of the SA and compare them to the values predicted by the theory. The results are presented in Figure 5a which shows that the measured statistics closely match the theoretical predictions.
measure the variance and mean
19

---

Published as a conference paper at ICLR 2024
Softmax Attention
Softmax Attention matrix statistics
LLN Attention == ===1
LLN Attention with moment matchin
Actual variance o
oi (Attention
Estimation of
3
-2
Actual mean Pam
Estimation -In o
1
3
4 0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
8
(a)
(b)
Figure 5: (a) The variance and mean of the SA matrix with respect to the input variance. Measure- ments perfectly match theoretical estimation. (b) The variance of the SA and LLN Attention before and after performing the moment matching procedure.
A.6 PROOF OF PROPOSITION 4.1
Proof. To demonstrate that the LLN attention matrix approximately follows a log- log-normal distribu- tion, examine single entry of the attention matrix, which is dot product of two vectors q and The nominator (e"9, e Σd t represents a sum of d log-normal variables with zero mean and variance 2², where
02 aa20 300
(26)
Similarly, the denominator Σj= (009, e of the LLN Attention matrix, which is also a sum of
log-normal variables. According to (Fenton 1960). for moderate values of Ø², the distribution of the sum of log-normal variables can be approximated by another log-normal distribution at the right tail. Since the ratio of the log-normal variables is also log-normal, we can approximate the distribution of the LLN Attention matrix by log-normal distribution.
To determine the relationship between the variance of the LLN Attention matrix oLL and variances of queries and keys o² o² we need to estimate the variance of a sum of log-normal variables. Following the approach of (Romeo et al. 2003), will divide our analysis into three cases: narrow 8² & 1, moderate 8² < and broad o²
Denote variance of the sum in nominator by of and variance of the denominator by dden.
NARROW CASE
0 og of 1 then the values are small such that even close zero, thus we can approximate e ss 1 aq; and @k; xe 1 Sk; thus:
22 nom = dia20² + 5 = =dō2;
2r. ~ N(a20 +800)) No²
(27)
MODERATE CASE
When 8² is relatively small (i.c., S 1), use given by:
(Fenton 1960 method. The approximation is
0 -1
20om z In
+
In
+1
(28)
d
d
20

---

Published as a conference paper at ICLR 2024
Actual d
Estimation d
0,030
Estimation d= 256
10
of the sum
0.025
Estimation d 512
of the sum
0.015
0.010
dm64
0.005
d=256
0.000
boundary of linear region
0.4
0.8 of of the variables
0.6
1.0
1.2
10
20
30
40
50
60
the variables
(a)
(b)
Figure 6: The variance of the sum of d log-normally distributed inputs, each with variance of o² and a zero mean, is effectively estimated by the (Fenton 1960) method. (a) In moderate scenario where o² lies within the range of [0.2, 1.2]. theoretical estimations (depicted dashed lines) aligned with empirical results. (b) In the broad case, for sufficiently large o² the variance of the log-norma sum grows linearly with the variance of the input variables.
Similarly, for the denominator:
c02
den In
+1
(29)
N
In fig. 6a we demonstrate the empirical evaluation of the correctness of Fenton approximation when 0.2, 1.2).
BROAD CASE
In the broad case, when 52 large (i.e., 52 1), it not possible find closed-form approxima- tion for the log-normal sum. However, we can observe that the sum of exponents is dominated by the largest term, which corresponds the maximum value. This maximum value grows linearly with the spread of queries and keys under the Gaussian assumption. Consequently, according to (Romeo) et al. 2003), the resulting variance ÿ² is also linearly proportional ğ² with some constants (1 02 and 61, bz:
0 o RO (a + 8 + b = a1ō² + b1
(30)
aen = f + b azz² b2
(31)
We empirically evaluated the linear dependency assumption of the sum of log-normally distributed inputs and showed its validity in fig. 6bb)
Finally, the variance of the LLN Attention matrix is sum of the nominator and denominator vari- ances, i.e.:
i o nom a aeen
(32)
By denoting a 01 + ag and
+ by for a broad case we get:
o = = + b a(a20 + + +b
(33)
n
21

---

Published as a conference paper at ICLR 2024
= =2= =1
0 = 2.25, of =.44
1.2-
Saftmax Attention
Softmax Attention
1.75
Attention a= ==1
LLN Attention a 8=1
LLN Attention moment matching
1.0
LLN Attention moment matching
1.50
1.25
0.8-
1.00
0.6-
0.75
0.4
0.50
0.2
0.25
0.00
-10
0.0
-17.5
-15.0 -12.5
-10.0
-7.5
-5.0
-2.5
Figure 7: Histogram of the SA and LLN Attention before and after performing the moment match- ing.
A.7 MOMENT MATCHING
As shown in Figure 5b we are interested handling broad range of o² values, particularly those in [1,4]. Using Proposition 4.1 we can find the constants and b that satisfy the requirement oii 2 of the broad case through moment matching. To do this, we perform linear interpolation between the variances of the LLN and Softmax Attention by injecting uncorrelated Gaussian inputs to both attentions and measuring their output variances according to the following equation:
2e = oin = aō² +
(34)
Once we have determined the values for and b, we substitute them into Equation (T)) obtain the optimal values for a and B.
As depicted in Figure 5b the variance of the LLN Attention without moment matching (i.e., = 3 = 1) is much smaller than that of the Softmax Attention and exhibits a nearly linear trend. However, the variance of the LLN Attention with moment matching approximates that of the Soft- max Attention. Additionally, the histogram shown in Figure 7 suggests that the LLN Attention distribution closely follows that of the Softmax Attention. Despite that, the two distributions have slightly different means because we only match their variances.
A.8 EXPERIMENTS
In this section, we present more experimental results and ablation studies of our method.
A.8.1 PRE-TRAINING OF ROBERTA MODEL
We train the bidirectional RoBERTa-baee encoder model (Liu et al. 2019) using LLN Attention the 10k corpus (Merity et al. 2018). During pre-training. we monitor the convergence of the model and compare its performance the SA model. In Figure Sal show the training and validation loss of the RoBERTa-base model during pre-training with LLN Attention, as well as its comparison SA. The loss curve of LLN Attention closely follows the SA, indicating similar convergence behavior. We used the Fairseq framework (Ott et al. 2019) for all experiments with the default configuration and hyperparameters of the RoBERTa-base model
We perform the training with FP16 precision, which can cause instability during training. To test the stability of the training, we also log the inverse loss scale parameter Figure 8bb Spikes in the plot indicate decrease in the loss scale due to large gradients. As can be seen from the figure, the maximum inverse scale of LLN Attention does not exceed that of the SA, which important to ensure similar stability during training as with SA.
22

---

Published as a conference paper at ICLR 2024
14
Softmax Attention train
0.5
Softmax Attention
LLN+Diag Attention train
LLN+Diag Attention
12-
Softmax Attention val
LLN+ Diag Attention val
Inverse scale
0.3
8-
0.2
0.1
0
100
200
300
400
100
200
300
400
Epoch
Epoch
(a)
(b)
Figure 8: (a) Training and validation loss comparison of RoBERTa- base model pre-training using LLN Attention and SA. (b) Inverse of the loss scale during training of RoBERTa-ban model.
A.8.2 IMAGE CLASSIFICATION
To test LLN Attention Vision task, evaluate it the Vision Transformer model using vit- pytorch code base. Our ViT model consists of twelve layers and 128 embedding sizes. We train this model for 100 epochs Dogs Cats dataset with LLN and Softmax Attention. The results in Table 3 show that LLN Attention performs on par with SA while outperforming the Linformer
WWan et 2020 method.
Softmax
LLN++Dag
Linformer
81.37
81.72
79.89
Table 3: Accuracy [%] of the VIT model trained on Dogs vs Cats dataset with Softmax, LLN (ours)
and Linformer (Wang et al. 2020) Attention.
A.8.3 LONG RANGE ARENA
Time[s]
Memory [bb]
method
TC
LO
RE
PF
IC
TC
LO
RE
PF
IC
Softmax
21468
5905
21866
6754
13228
17108
4458
8934
4817
9632
Reformer
4610
2439
4714
4694
8737
3261
1631
3008
3258
6514
Performer
3456
1966
3761
3553
13169
2176
1122
2178
2180
4353
Skyformer
4523
2970
5602
5240
9347
3068
1697
2974
4041
8079
LLN Diag
3043
1774
3135
3042
4053
1641
821
1586
1639
3276
Table 4: Comparison of memory [Mb] and running time [s] of LLN Attention with Reformer(Kitaey ct al. 2020), Performer(Choromanskt al. 2020) and Skyformer (Chnn et al. 2021) linear attention methods and SA baseline.
We use the Long Range Arena (LRA) TTa al. 2020c) benchmark evaluate LLN Attention on longer sequences. LRA benchmark requires sequence length between 1K and 4k, depending on the task. that end, we used code base provided by Skyformer (Chen et al. 2021 We compare the LRA score in addition the memory and computation complexity of LLN Attention with Re- former former(Kitaev et al. 2020),
et al. 2020). and Skyformer(Chen et al.) al.| 2021) linear methods well as regular SA. According the Table LLN Attention requires much less
23

---

Published as a conference paper at ICLR 2024
memory and time compared to other methods while achieving similar average LRA as SA Table
method
Text (4k)
ListOps (2k)
Retrieval (4k)
Pathfinder (Ik)
Image (Ik)
AVG
Softmax
60.41
38. 38.05
79.95
71.3
37.2
57.38
Reformer
61.27
37.05
78.74
67.23
44.04
57.67
Performer
57.85
37.8
80.5
62.58
37.56
55,26
Skyformer 60.88
39.36
81.54
70.23
32.64
56.93
LLN Diag
60.72
38.91
81.21
69.81
38.65
57.86
Table 5: LRA score of LLN Attention with Reformer(Kitann et al.
Performer(Choromanss, 2020) and Skyformer al. 202I) linear attention methods and SA baseline.
2020),
ct al.
A.8.4 LLN ATTENTION CONCENTRATION ABLATION STUDY
In this section, we analyze the impact the LLN Attention temperature of the Vision Transformer (ViT) model trained on the Dogs vs Cats dataset. First, we record the values of and produced by the moment matching procedure during training. According to Figure 9 the values a and obtained during moment matching lay within the range of (2: 2.2). Furthermore, since the tempera- ture of the LLN Attention, as defined in Equation (11), decreases as the hyper-parameters a and / increase. To assess the influence of the temperature, of hyper-parameters a and 3 and record the resulting accuracy. In Figure T0a we see that when a and [3 values are smaller than the moment matching range, i.e., less than 2. the LLN Attention con- centration is insufficient due to the high temperature, leading to accuracy degradation. Conversely, when and values lay within the range of moment matching values or larger (a, 2 2), the concentration is sufficient for the model to achieve the desired accuracy.
train the model with various fixed values
layer0
layers
layrr
ayers
layer]
layer?
2.200
layer
kyye??
2.20
layer3
layerd
layer2o
lagert
2.175
kyyrt
kayer
ayerto
kyyrr
layers
layer11
ayer12
2.18
2.150
2.125
2.16
2.14
2.075
2.050
2.12
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
5000
6000
Iteration
Iteration
(b)
Figure 9: Change the a parameter (a) and /3 (b) during training of ViT model on Dogs vs Cats dataset.
We highlight the risks associated with surpassing the moment matching range by increasing a and 3. particular, larger values of these parameters may risk the stability of the training process due to increased gradients, concern that becomes especially noticeable when training models in Float16 format. The risk of utilizing the F data type stems from the reduced precision, smaller dy- namic range, risks of gradient overflow, and the requirement to maintain the loss scaling. Moreover, the lower precision of F may result in information loss during computations and numerical instability.
Accordingly, exceeding the moment matching values of a and 3 is practically undesirable, particu- larly in the context of training with Float16. In Figure 10b illustrate this phenomenon by pre- senting the loss scale during the training of the deit-tiny model (ouvrro et al. (020) in the F format. We that for large values of B the inverse of the loss scale is significantly larger,
24

---

Published as a conference paper at ICLR 2024
85
Nomeet matching accuracy
0.06
umfm2
Fixed d-p
d-p-4
80
matching range
Comenttatchiine
0.05
invers scale
0.04
Accuracy
0.03
HM Wnitii
65
0.02
60
0.01
0.00
0.5
1.0
1.5
2.0
3.0
4.0
0
50
100
150
200
250
300
epoch
(b)
Figure 10: (a) Accuracy of ViT trained on Dogs vs Cats dataset with LLN Attention and different values of a and B. (b) Inverse of the loss scale during training of deit-tiny model for different fixed values of a and 3 as well as for moment matching.
compared to a == 8= 2, indicating increased gradients and the potential of training instability or failure. Therefore, achieve the desired accuracy and allow stable training, it is erucial to maintain the temperature the "sweet spot" specified by the moment matching values.
25


Reviews:
[{"review_id": "oPK6SSMyYQ", "reviewer": "Reviewer_xXRJ", "summary": "The paper proposes a linear log-normal attention mechanism that has linear time and memory complexity while retaining key properties of the naive softmax attention (SA). The key properties under consideration are the log-normal distribution of the attention matrix and the monotonicity of the entropy as well as the spectral gap with temperature. Several experiments with different NLP tasks are performed to confirm the efficiency of the proposed method.", "questions": "See weaknesses!", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is very well-written with detailed theoretical justification and many useful intuitive explanations.\n\n- The authors have characterized three important and interesting properties of the SA mechanism: (1) the distribution of the SA matrix $\\mathbf{P}^{(SM)}$ can be approximated by a log-normal distribution, (2) the entropy $H(\\mathbf{P}^{(SM)})$ is monotonically increasing with temperature, while (3) the variance of the attention matrix $\\mathbf{P}^{(SM)}$ is decreasing with temperature. I have not checked the proofs line by line, but it seems to me that the proofs are correct.\n\n- Based on these characterizations of the SA mechanism, the authors carefully selected suitable feature embedding functions $\\phi$ in the linearized attention equation in a way that these characterizations still hold.\n\n- Experiments with different NLP tasks confirmed the advantages of the proposed model in comparison with previous linear attention methods.\n\n- In these experiments, the authors also experimentally show that the entropy and the spectral gap of the attention matrix are actually monotonically increasing, as proved in the theoretical parts.\n\nOverall, I think this is a good paper.", "weaknesses": "I do not see any major weaknesses of the paper. There are a few minor weaknesses as follows:\n\n- Some notions are introduced with formulas but without intuitive explanations. For example, why is $\\tau_{sm}$ in Eq. (5) called the \"temperature\" of the SA? and why controls the level of exploration and exploitation?\n\n- In Eq. (6), $P_{ij}^{(SM)}$ is used, while in Eq. (7), it is $\\mathbf{P}_{ij}^{(SM)}.\"\n\n- I am not sure where the proof of Theorem 3.4 is in the Appendix. Is it Theorem A.3?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "FdrLEps1PU", "reviewer": "Reviewer_zqGD", "summary": "The paper proposes a new self-attention mechanism called Linear Log-Normal Attention (LLN Attention) that reduces the quadratic computational complexity of standard softmax attention while aiming to maintain comparable performance.\nThe authors first provide background on transformer models and the standard scaled dot-product softmax attention, as well as prior work on efficient linear attention mechanisms.\nThey then conduct an in-depth analysis of softmax attention, characterizing its statistical, informational, and algebraic properties.\nIn particular, they model the distribution of the attention matrix and prove its log-normal nature.\nFurthermore, they analyze the concentration behavior of softmax attention using entropy and spectral gap metrics.\nBased on this analysis, the authors design the LLN Attention method to emulate the log-normal distribution and concentration properties of standard softmax attention.\nLLN Attention uses exponential feature embeddings of the queries and keys to induce a log-normal distribution.\nThe authors also introduce a temperature parameter and perform moment matching between LLN Attention and softmax attention to align their concentration behavior.\nThis allows LLN Attention to achieve comparable performance to softmax attention.\nThe paper provides proofs that LLN Attention follows a log-normal distribution and that its entropy and spectral gap vary similarly to softmax attention with respect to temperature.\nExperimental results on natural language processing benchmarks demonstrate that LLN Attention outperforms other linear attention methods and achieves competitive accuracy compared to softmax attention.", "questions": "Please see above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- This paper made contributions in 1) in-depth analysis and modeling of distributional and concentration properties of softmax attention; 2) Design of LLN Attention method that emulates softmax attention based on this analysis; 3) Introduction of moment matching technique to align concentration behavior; 4) Linear complexity in sequence length while maintaining softmax attention performance. The proposed LLN Attention offers an interesting and somewhat promising approach to enhance transformer scalability for long sequences.\n\n- The paper provides a novel perspective on analyzing self-attention through statistical and information-theoretic lenses. The design of LLN Attention based on emulating properties of softmax attention is a useful technique for developing efficient linear attention. Matching the log-normal distribution and concentration patterns is a creative way to achieve comparable performance.\n- The analysis provides useful insights into the workings of the widely used softmax attention. Characterizing the distribution and concentration can guide better attention design. LLN Attention demonstrates the viability of achieving softmax performance with linear complexity. This can expand the applicability of transformers to longer sequences.\n- The proposed techniques like moment matching may inspire novel ways to analyze and improve attention mechanisms in future work.", "weaknesses": "- The theoretical analysis relies on several approximations, such as using the Fenton theorem to model log-normal sums. While justified, evaluating the accuracy of these approximations on empirical data could be beneficial.\n- The paper focuses exclusively on natural language tasks. Assessing the effectiveness of LLN Attention on other modalities like computer vision with ViTs could provide more insight into its general applicability.\n- Only accuracy results are reported. Including other metrics like training time, stability, convergence rate, etc. could allow more comprehensive comparison to softmax attention.\n- The moment matching technique matches up to 2nd order statistics of LLN and softmax attention. Have the authors considered or tried extending to higher order statistics?\n- Combining LLN Attention with sliding window or dilated patterns could be an interesting extension to handle local contexts more effectively. What do the authors think?\n- The impact of different feature embedding functions besides the exponential function could be analyzed. Do they provide similar distributions and concentration?\n- More ablation studies on the temperature parameter, block size in diagonal attention, layer depth, etc. could shed light on how to best configure LLN Attention.\n- The quality and diversity of the tasks used for evaluation could be expanded. For instance, adding tasks with longer input sequences could better highlight benefits of LLN Attention.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "TGS9SrKqh8", "reviewer": "Reviewer_m7qC", "summary": "This paper proposed a linear log-normal attention with unbiased concentration to deal with the quadratic time and memory complexity of self-attention. Experiments on several NLP tasks show its effectiveness.", "questions": "See weakness.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The analysis of this this paper is good and the design of linearized attention is interesting. The experiments and the visualized results are easy to follow.", "weaknesses": "1. The main concern of this paper is its results. Compared with Nystromformer, which published two years ago, this paper dose not improve enough, from both results and efficiency, as shown in  Table 1 and Table 2.\n2. Only NLP tasks are adopted, but computer vision based tasks are neglected. \n3. Some related works are missing, such as KVT (ECCV2022). \n4. The experiments are not extensive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "AyYspo3vlK", "reviewer": "Reviewer_aZn4", "summary": "This study scrutinizes the self-attention mechanism, focusing on the distribution and concentration behavior inherent in the original self-attention model, and introduces an innovative linear log-normal attention mechanism. Empirical evidence gathered from widely recognized natural language processing benchmarks demonstrates that the proposed method surpasses other linearized attention alternatives in performance.", "questions": "See weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Linearized Attention has emerged as a crucial subject in contemporary transformer architectures.\n\n2. Empirical evidence demonstrates its efficacy.", "weaknesses": "1. The experimental results across various Natural Language Processing (NLP) tasks do not exhibit significant improvements.\n\n2. The absence of latency comparison is a drawback; providing only theoretical analysis is insufficient without practical, comparative data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)