Learning Advanced Self-Attention for Linear Transformers in the Singular Value Domain
Hyowon Wi, Jeongwhan Choi, Noseong Park · 2025
Read Learning Advanced Self-Attention for Linear Transformers in the Singular Value Domain by Hyowon Wi, Jeongwhan Choi, Noseong Park (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08516.txt.
Introduction
Hyowon Wi, Jeongwhan Choi, and Noseong Park rethink the core step that lets transformer models weigh links between words. Their 2025 paper views that step as a filter on a graph, where word values act as the signal. In that view, the standard step uses just the first, simplest part of the filter. It acts like a low-pass filter and drops much of the fine detail in the signal.
Their new method learns the full filter in a space set by singular values, even for directed graphs. It keeps cost in line with input length. On long-range tests and on time series tasks, their method reached top scores among the methods tried.
Catalog record
| CREATOR | Hyowon Wi, Jeongwhan Choi, Noseong Park |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-08516
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning Advanced Self-Attention for Linear Transformers in the Singular Value Domain Hyowon Wi, Jeongwhan Choi, Noseong Park Abstract Transformers have demonstrated remarkable performance across diverse domains. The key component of Transformers is self-attention, which learns the relationship between any two tokens in the input sequence. Recent studies have revealed that the self-attention can be understood as a normalized adjacency matrix of a graph. Notably, from the perspective of graph signal processing (GSP), the self-attention can be equivalently defined as a simple graph filter, applying GSP using the value vector as the signal. However, the self-attention is a graph filter defined with only the first order of the polynomial matrix, and acts as a low-pass filter preventing the effective leverage of various frequency information. Consequently, existing self-attention mechanisms are designed in a rather simplified manner. Therefore, we propose a novel method, called A ttentive G raph F ilter (AGF), interpreting the self-attention as learning the graph filter in the singular value domain from the perspective of graph signal processing for directed graphs with the linear complexity w.r.t. the input length n n , i.e., 𝒪 ( n d 2 ) \mathcal{O}(nd^{2}) . In our experiments, we demonstrate that AGF achieves state-of-the-art performance on various tasks, including Long Range Arena benchmark and time series classification. 1 Introduction Transformers Vaswani et al. (2017) have achieved great success in many fields, including computer vision Touvron et al. (2021a) ; Liu et al. (2021) , time series analysis Li et al. (2019) ; Wu et al. (2021) ; Zhou et al. (2021) , natural language processing Nangia and Bowman (2018) ; Maas et al. (2011) ; Radford et al. (2019) ; Devlin et al. (2019) , and many other works Xiong et al. (2021) ; Wang et al. (2020) ; Yu et al. (2024) ; Kim et al. (2024) . Many researchers agree that the self-attention mechanism plays a major role in the powerful performance of Transformers. The self-attention mechanism employs a dot-product operation to calculate the similarity between any two tokens of the input sequence, allowing all other tokens to be attended when updating one token. (a) Vanilla self-attention in Transformers (b) Graph signal processing on undirected graph (c) Graph signal processing on directed graph Figure 1: Illustration of the vanilla self-attention in Transformers and graph signal processing: (a) shows the softmax operation after the dot-product of query and key vectors, followed by the multiplication with the value vector; (b) and (c) show graph signal processing in undirected and directed graphs, respectively. For undirected graphs, the signal is filtered in the eigenvalue domain, while for directed graphs, the signal is filtered in the singular value domain . Linear Transformers approximate the self-attention. However, the self-attention requires quadratic complexity over the input length to calculate the cosine similarity between any two tokens. This makes the self-attention difficult to apply to inputs with long lengths. In order to process long sequences, therefore, reducing the complexity of self-attention has become a top-priority goal, leading to the proposal of approximating the self-attention with linear complexity Child et al. (2019) ; Ravula et al. (2020) ; Zaheer et al. (2020) ; Beltagy et al. (2020) ; Wang et al. (2020) ; Katharopoulos et al. (2020) ; Choromanski et al. (2020) ; Shen et al. (2021) ; Xiong et al. (2021) ; Qin et al. (2022) ; Chen et al. (2023) . However, existing self-attention with linear complexity aims to create a matrix that is close to the original self-attention map \bar{\mathbf{A}} . The self-attention is a low-pass filter (see Thm. 1 ). The self-attention map is a matrix that represents the relationship between every pair of tokens as scores normalized to probability by softmax. Considering each token as a node and the attention score as an edge weight, self-attention is considered as a normalized adjacency matrix from the perspective of the graph Shi et al. (2022) ; Wang et al. (2022) ; Choi et al. (2024) . Therefore, the self-attention plays an important role in the message passing scheme by determining which nodes to exchange information with. Given that the self-attention operates as a normalized adjacency matrix, it is intuitively aligned with graph signal processing (GSP) Ortega et al. (2018) ; Marques et al. (2020) ; Chien et al. (2021) ; Defferrard et al. (2016) , which employs graph structures to analyze and process signals. Fig. 1 illustrates the self-attention in Transformers and signal filtering in GSP. As depicted in Fig. 1 (a), the original self-attention takes the softmax of the output from the dot product of the query vector and the key vector, and then multiplies it by the value vector. Fig. 1 (b) illustrates a general GSP method that applies the graph Fourier transform to the signal, conducts filtering in the spectral domain, and subsequently restores it to the original signal domain. In GSP, a signals are filtered through the graph filters, which are generally approximated by a matrix polynomial expansion. The self-attention mechanism in Transformers can be viewed as a graph filter \mathbf{H} defined with only the first order of the polynomial matrix, i.e., \mathbf{H}=\mathbf{\bar{A}} . Furthermore, since the self-attention is normalized by softmax and functions as a low-pass filter (see Theorem. 1 ), the high-frequency information in the value vector is attenuated, preventing the effective leverage of various frequency information. Consequently, existing self-attention mechanisms are designed in a rather simplified manner. Our proposed linear Transformer learns an advanced self-attention (see Thm. 2 ). Although the approximation of linear Transformers is successful, what they are doing is simply a low-pass filtering. Therefore, to increase the expressive power of linear Transformers, we propose a more generalized GSP-based self-attention, called A ttentive G raph F ilter (AGF). We interpret the value vector of Transformers as a signal and redesign the self-attention as a graph filter. However, the existing self-attention mechanism possesses two problems: i) since the self-attention is based on directed graphs, the graph Fourier transform through eigendecomposition is not always guaranteed, and ii) the attention map change for every batch, making it too costly to perform the graph Fourier transform every batch. In order to address the first problem, therefore, we design a self-attention layer based on the GSP process in the singular value domain (see Fig. 1 (c)). The singular value decomposition (SVD) has been used recently for the GSP in directed graphs and can substitute the eigendecomposition Maskey et al. (2023) . In order to address the second problem, we directly learn the singular values and vectors instead of explicitly decomposing the self-attention map or any matrix. Since our proposed self-attention layer directly learns in the singular value domain by generating singular vectors and values using a neural network, our proposed method has a linear complexity of O(nd^{2}) . Therefore, our method efficiently handles inputs with long sequences. Our contributions can be summarized as follows: 1. We propose an advanced self-attention mechanism based on the perspective of signal processing on directed graphs, called A ttentive G raph F ilter (AGF), motivated that the self-attention is a simple graph filter and acts as a low pass filter in the singular value domain. 2. AGF learns a sophisticated graph filter directly in the singular value