keyword
linear self-attention
Linear self-attention is a variant of the self-attention mechanism in neural network architectures designed to scale computational time and memory usage linearly rather than quadratically with the length of the input sequence. In standard self-attention, the model computes pairwise relationships between every token in a sequence, leading to computational and memory requirements that grow with the square of the sequence length and become prohibitively expensive for long inputs. Linear self-attention overcomes this bottleneck by approximating or reformulating the attention computation, commonly through kernel feature mappings, low-rank matrix projections, or by leveraging the associative property of matrix multiplication to reorder operations. By reducing this computational overhead, linear self-attention enables transformers to process significantly longer contexts and large-scale inputs efficiently during both training and inference while continuing to model dependencies across the entire sequence.
2 items
In-context Convergence of Transformers
Yu Huang, Yuan Cheng, Yingbin Liang
Why you should read this
Establishes the first finite-time convergence guarantees and characterizes the stage-wise gradient descent dynamics of single-layer softmax transformers performing in-context learning on linear tasks across balanced and imbalanced feature distributions.
Transformers have recently revolutionized many domains in modern machine learning and one salient discovery is their remarkable in-context learning capability, where models can solve an unseen task by utilizing task-specific prompts without further parameters fine-tuning. This also inspired recent theoretical studies aiming to understand the in-context learning mechanism of transformers, which however focused only on linear transformers. In this work, we take the first step toward studying the learning dynamics of a one-layer transformer with softmax attention trained via gradient descent in order to in-context learn linear function classes. We consider a structured data model, where each token is randomly sampled from a set of feature vectors in either balanced or imbalanced fashion. For data with balanced features, we establish the finite-time convergence guarantee with near-zero prediction error by navigating our analysis over two phases of the training dynamics of the attention map. More notably, for data with imbalanced features, we show that the learning dynamics take a stage-wise convergence process, where the transformer first converges to a near-zero prediction error for the query tokens of dominant features, and then converges later to a near-zero error for query tokens of under-represented features, via one and four training phases. Our proof features new techniques for analyzing the competing strengths of two types of attention weights, the change of which determines different training phases.
Added
2026-09-26
Linformer: Self-Attention with Linear Complexity
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, Hao Ma
Why you should read this
Proposes Linformer, an attention architecture that reduces Transformer computational and memory complexity from quadratic to linear via low-rank matrix approximation without sacrificing accuracy.
Large transformer models have shown extraordinary success in achieving state-of-the-art results in many natural language processing applications. However, training and deploying these models can be prohibitively costly for long sequences, as the standard self-attention mechanism of the Transformer uses time and space with respect to sequence length. In this paper, we demonstrate that the self-attention mechanism can be approximated by a low-rank matrix. We further exploit this finding to propose a new self-attention mechanism, which reduces the overall self-attention complexity from to in both time and space. The resulting linear transformer, the \textit{Linformer}, performs on par with standard Transformer models, while being much more memory- and time-efficient.
Added
2026-09-14