## 3 Materials and Methods
### Model Construction
#### 3.2.3 ProbSparse Self Attention  
Self-Attention [17,36], a fundamental operation in Transformer models, computes relationships among query, key, and value pairs. However, its computational complexity scales quadratically as \(O(L_{Q}L_{K})\), where \(L_{Q}\) and \(L_{K}\) denote the lengths of the query and key sequences, respectively. This quadratic scaling poses a significant challenge for processing long sequences. ProbSparse Self-Attention addresses this issue by introducing sparsity into the attention mechanism, drastically reducing computational and memory requirements. The standard Self-Attention mechanism computes the output as:  
\[A(Q,K,V)=\text{softmax}\left(\frac{QK^{\top}}{\sqrt{d}}\right)V \tag{12}\]  
where \(Q\in\mathbb{R}^{L_{Q}\times d},K\in\mathbb{R}^{L_{K}\times d}\), \(V\in\mathbb{R}^{L_{V}\times d}\), \(d\) is the feature dimension, and \(q_{i},k_{i},v_{i}\) represent the \(i\)-th rows of \(Q,K,V\) respectively.  
As shown in Figure 4, the Self-Attention mechanism computes the attention scores (\(a^{\prime}_{1,i}\)) for each query by comparing it with all keys in the sequence. These scores are then normalized using the _Softmax_ function and used to compute a weighted sum of the value vectors (\(v^{i}\)). The resulting output vector (\(b^{1}\)) is given by:  
\[b^{1}=\sum_{i}a^{\prime}_{1,i}v^{i} \tag{13}\]  
This equation illustrates how the attention mechanism aggregates information from all value vectors, weighted by their respective attention scores.  
ProbSparse Self-Attention modifies this formulation by recognizing that attention scores are inherently sparse: not all queries strongly relate to all keys. By focusing only on the most relevant key-value pairs for each query, the mechanism reduces complexity  
Figure 4: An illustration of the Self-Attention mechanism.  
while maintaining performance. The attention for the \(i\)-th query is reformulated as a kernel-smoothing operation:  
\[A(q_{i},K,V)=\sum_{j}\frac{k(q_{i},k_{j})}{\sum_{j}k(q_{i},k_{j})}v_{j}=\mathbb{ E}_{p(k_{j}|q_{i})}[v_{j}] \tag{14}\]  
Here, the kernel function \(k(q_{i},k_{j})\) is defined as an asymmetric exponential kernel:  
\[k(q_{i},k_{j})=\exp\left(\frac{q_{i}^{\top}k_{j}}{\sqrt{d}}\right) \tag{15}\]  
and \(p(k_{j}|q_{i})\) is the normalized probability distribution. By focusing on these probabilistically significant pairs, ProbSparse reduces the computational complexity. To identify the sparsity in attention weights, ProbSparse uses the Kullback-Leibler (KL) divergence to measure the deviation between the distribution \(p(k_{j}|q_{i})\) and a uniform distribution. The KL divergence is defined as:  
\[KL(q||p)=\ln L_{K}+\sum_{l=1}^{L_{K}}\exp\left(\frac{q_{i}^{\top}k_{l}}{\sqrt{ d}}\right)-1-\frac{1}{L_{K}}\sum_{j=1}^{L_{K}}\frac{q_{i}^{\top}k_{j}}{\sqrt{d}} \tag{16}\]  
Removing the constant terms, the sparsity measure for the \(i\)-th query is defined as:  
\[M(q_{i},K)=\ln\sum_{l=1}^{L_{K}}\exp\left(\frac{q_{i}^{\top}k_{l}}{\sqrt{d}} \right)-\frac{1}{L_{K}}\sum_{j=1}^{L_{K}}\frac{q_{i}^{\top}k_{j}}{\sqrt{d}} \tag{17}\]  
The first term is the Log-Sum-Exp (LSE) operation, highlighting the strongest key-query relationships, while the second term reflects the average similarity across all keys. A larger \(M(q_{i},K)\) value indicates greater sparsity in attention weights. Using the sparsity measure \(M(q_{i},K)\), ProbSparse Self-Attention selects the top \(u=c\ln L_{Q}\) queries, where \(c\) is a constant factor. These queries form the subset \(\hat{Q}\), which is used to compute the attention with reduced complexity:  
\[A(Q,K,V)=\text{softmax}\left(\frac{\hat{Q}K^{\top}}{\sqrt{d}}\right)V \tag{18}\]  
This formulation ensures that only the most important query-key interactions are retained. As a result, ProbSparse Self-Attention achieves a computational complexity of \(O(L_{Q}\ln L_{Q})\) and a memory usage of \(O(L_{K}\ln L_{Q})\), making it suitable for long-sequence modeling.