Attention Mechanisms in Transformers: A Comparative Survey and Structural Enhancements to Linear Attention
Abstract
This master’s thesis explores the trade-off between computational efficiency and modeling performance in Transformer architectures by studying and improving attention mechanisms. The work consists of two parts: (1) a comparative empirical study evaluating five attention variants—standard Multi-Head Attention, FlashAttention, Sparse Attention, Sliding-Window Attention, and Linear Attention—across multiple Transformer model families, including encoder-only (BERT-style), decoder-only (GPT-style), and full encoder–decoder architectures. This broader evaluation highlights how each mechanism behaves under different structural constraints and reveals the consistent underperformance of linear attention in decoder-only setups due to weaker long-range modeling. (2) A technical contribution proposing two new hybrid mechanisms, Linear SparseAttention and Linear Sliding-Window Attention, which enhance the expressiveness of linear attention while preserving its linear-time complexity. Experiments show that both hybrids significantly outperform standard linear attention and narrow the performance gap with full attention, offering a promising path toward efficient and scalable Transformer models deployable in resource-constrained settings.
Full text
Universit´e Sultan Moulay Slimane ´ Ecole Nationale des Sciences Appliqu´ees -KhouribgaFinal Year Project Report In view of obtaining the degree MASTER Program: Big Data et Aide `a la D´ecision Attention Mechanisms in Transformers: A Comparative Survey and Structural Enhancements to Linear Attention Prepared by: Mr. BENNANI Nizar Under the supervision of: Pr. Abdelghani GHAZDALI Defended on June 17, 2025, in front of the jury: Pr. Abdelghani GHAZDALI ENSA Khouribga – Supervisor Pr. Aziz IFZARNE ENSA Khouribga – President Pr. Moad HAKIM ENSA Khouribga – Examiner Academic Year: 2024-2025
Acknowledgements First and foremost, I would like to express my deepest gratitude to God for granting me the strength, patience, and perseverance throughout this journey. Without divine guidance and blessings, none of this would have been possible. I am profoundly thankful to my family, whose unwavering love, encouragement, and support have been a constant source of strength. Their faith in me has helped me overcome countless challenges and kept me grounded through every stage of my academic journey. My heartfelt thanks also go to my friends, who stood by me with kindness and motivation. Their presence brought lightness and laughter during moments of stress and fatigue, and I am truly grateful for their companionship. I extend my sincere appreciation to my school and all the professors who have guided me, challenged me, and contributed to my learning over the years. Their dedication and passion for teaching have played a vital role in shaping the person and professional I am becoming. Finally, I wish to thank my project supervisor, Professor Abdelghani GHAZDALI, for their valuable guidance, thoughtful feedback, and continuous support throughout the course of this project. Their mentorship has been instrumental to both the development of this work and my growth as a student. To all those who have accompanied me along this path thank you from the bottom of my heart. 2
Abstract Transformer models have transformed natural language processing by employing self-attention mechanisms to model long-range dependencies. However, the quadratic complexity of full selfattention poses significant challenges for scaling to long sequences and deploying models in resource-constrained environments. In this work, we present a comprehensive study of alternative attention mechanisms including standard multi-head attention, linear attention, sparse attention, sliding-window attention, and FlashAttention. Our analysis spans both theoretical foundations and empirical performance, considering not only a variety of NLP tasks but also a range of Transformer architectures: encoder-only (e.g., BERT), decoder-only (e.g., GPT), and encoder–decoder models (e.g., full Transformer). Motivated by the limitations observed in linear attention particularly its reduced expressiveness despite its computational efficiency we propose two novel hybrid attention mechanisms designed to improve its performance in decoder-only models. The first mechanism integrates the local context sensitivity of sliding-window attention into the linear framework, while the second incorporates global sparsity patterns inspired by sparse attention. These hybrids aim to maintain the linear time and space complexity of linear attention while enhancing its ability to model contextual dependencies more effectively. Experimental results on the Tiny Shakespeare next-character prediction task demonstrate that our proposed hybrid mechanisms significantly outperform standard linear attention in terms of loss and perplexity. Unlike prior work that primarily focuses on designing faster or approximate attention variants, our contribution explicitly targets the recovery of performance lost in linear attention mechanisms. This focus on restoring predictive quality while retaining linear complexity is the core innovation of this work. Although our evaluation is limited to a small-scale setting, the findings suggest that these enhancements could be beneficial when scaled to more complex models and larger datasets. This work highlights the importance of tailoring attention mechanisms not only to specific tasks but also to the structural design of Transformer architectures. Keywords: Transformer models, self-attention, linear attention, sparse attention, hybrid attention mechanisms, decoder-only models, contextual dependencies, NLP tasks, performance recovery, Tiny Shakespeare dataset 3
R´esum´e Les mod`eles Transformer ont r´evolutionn´e le traitement automatique du langage naturel grˆace `a l’utilisation de m´ecanismes d’auto-attention permettant de mod´eliser les d´ependances `a longue port´ee. Cependant, la complexit´e quadratique de l’auto-attention compl`ete constitue un obstacle majeur `a l’extension vers de longues s´equences et `a la mise en œuvre dans des environnements `a ressources limit´ees. Dans ce travail, nous pr´esentons une ´etude approfondie de m´ecanismes d’attention alternatifs, incluant l’attention multi-tˆete standard, l’attention lin´eaire, l’attention clairsem´ee, l’attention `a fenˆetre glissante et FlashAttention. Notre analyse couvre `a la fois les fondements th´eoriques et les performances empiriques, en consid´erant non seulement une vari´et´e de tˆaches de NLP, mais aussi diff´erents types d’architectures Transformer : encodeur seul (par exemple BERT), d´ecodeur seul (par exemple GPT) et mod`eles encodeur-d´ecodeur (par exemple Transformer complet). Motiv´es par les limites observ´ees dans l’attention lin´eaire notamment sa capacit´e d’expression r´eduite malgr´e son efficacit´e computationnelle nous proposons deux nouveaux m´ecanismes hybrides con¸cus pour am´eliorer ses performances dans les mod`eles `a d´ecodeur seul. Le premier int`egre la sensibilit´e au contexte local de l’attention `a fenˆetre glissante dans le cadre lin´eaire, tandis que le second incorpore des sch´emas de raret´e globale inspir´es de l’attention clairsem´ee. Ces m´ecanismes hybrides visent `a conserver la complexit´e lin´eaire en temps et en m´emoire de l’attention lin´eaire, tout en am´eliorant sa capacit´e `a mod´eliser les d´ependances contextuelles de mani`ere plus efficace. Les r´esultats exp´erimentaux sur la tˆache de pr´ediction du caract`ere suivant dans le corpus Tiny Shakespeare montrent que nos m´ecanismes hybrides surpassent significativement l’attention lin´eaire standard en termes de perte et de perplexit´e. Contrairement aux travaux ant´erieurs qui se concentrent principalement sur la conception de variantes d’attention plus rapides ou approximatives, notre contribution vise explicitement `a restaurer la performance perdue dans les m´ecanismes d’attention lin´eaire. Cette volont´e de r´etablir la qualit´e pr´edictive tout en conservant une complexit´e lin´eaire constitue l’innovation principale de ce travail. Bien que notre ´evaluation soit limit´ee `a un cadre de petite ´echelle, nos r´esultats sugg`erent que ces am´eliorations pourraient ˆetre b´en´efiques lorsqu’elles sont appliqu´ees `a des mod`eles plus complexes et `a des ensembles de donn´ees plus volumineux. Ce travail souligne l’importance d’adapter les m´ecanismes d’attention non seulement aux tˆaches sp´ecifiques, mais aussi `a la structure des architectures Transformer. Mots-cl´es : mod`eles Transformer, auto-attention, attention lin´eaire, attention clairsem´ee, m´ecanismes hybrides, mod`eles `a d´ecodeur seul, d´ependances contextuelles, tˆaches de NLP, restauration des performances, corpus Tiny Shakespeare 4
Plm Amt ® Ty`ybW Tl TA` A ¨ A¾ryb ¾ry ¯wm ÐAm d dq ¨`yrt dyq`t ,Ð ¤ .Amlk y dy`b A®` T@mn ¨@ £Abt¯ Ty ¨ ÐAmn @yfn dn ¤ Tl§wV ®sls A`t dn A¾ryb A¾A§d ÌkK§ Ak £Abt® Ð ¨ Am ,Tl§db £Abt¯ Ayµ TlAJ TFC dq ,m` @¡ ¨ . Cwm ¤d A·y @wn Yl ¶Aq £Abt¯¤ ,rAntm £Abt¯¤ ,¨W £Abt¯¤ ,x¤¦r d`t ©dylqt £Abt¯ .§rs £Abt¯¤ ,Tqznm Ah Twnt Twm rb Ф ,¨b§rt º ±¤ T§r\n w Anlyl mK§ Yl Xq dmt` ¨t ÐAmn ,¯wm ÐAm Tflt Ynu¤ Ty`ybW Tl TA` .ryfKt ¤ ryfKt y m ¨t l ¤ ,ryfKt Yl Xq ¤ ,ryfKt Yl ¢Cd `R y A¾A}wO ,¨W £Abt¯ ¨ A¡An\¯ ¨t wyq A¾A®W¤ ¨ ¢¶ ys Y Adh yd§d ytn¡ yty rtq ,TyA` ¢ºAf C Ays ym dmtsm ¨lm Aysl TyFAs d Y¤± Tyµ .Xq ryfKt Yl dmt`m ÐAmn r`b ªAm Yl TyA Tyµ dmt` Amny ,¨W CAV³ mR @wn Yl ¶Aq £Abt¯ ¨Ak¤ ¨nE dyq` Yl _Af Y Atyµ AA¡ dh .rAntm £Abt¯ Awts TymA .S kK Ays ªAqt Yl Ðwmn Cd z§z` ¨W ytyµ ry} QwO ¨ ¨At r Ìw Tmh Yl Tyb§rt ¶Atn rh\u CAs |Af y ©dylqt ¨W £Abt¯ Yl _wl kK Awft ytrtqm §rq ¤ £Abt¯ §rs Yl zC ¨t TqAs Am± Hk Yl¤ .¥bnt w Ìs¤ Xysbt bs wqfm º ± w A`tF Yl R¤ kK zr Antm¡As ,¢¶At .m` @¡ ¨ CAkt¯ r¡w dh @¡ d`u§¤ .¨As wk d Anyst £@¡ Y ¶Atn ryK , ¤d AW Yl rOt yyqt C¤ Tym¡ Yl ºwS m` @¡ XÌls§ .A¾Am rb Ah¤ A¾dyq` r ÐAm mKt yFwtl TlA .Ðwmnl T§CAm`m Tynb s A¾AS§ ,Tmhm w s Xq Hy £Abt¯ Ay Tºw Ayµ ,rAntm £Abt¯ ,¨W £Abt¯ ,¨@ £Abt¯ ,¯wm ÐAm :TyAtfm Amlk ,º ± A`tF ,Ty`ybW Tl TA` Ah ,¨Ays Amt¯ ,ryfKt ÐAm ,Tnyh raFkahR ¨Ã AAy Twm 5
Motivation As Transformer models continue to dominate the landscape of natural language processing, the demand for scaling them efficiently both in terms of memory and compute has become increasingly urgent. Full self-attention, despite its effectiveness, imposes a quadratic cost with respect to sequence length, making it a bottleneck in long context applications or when deployed under resource constraints. Various solutions have been proposed to address this, yet many introduce new limitations, such as reduced expressivity or increased architectural complexity. Motivated by this tension between efficiency and performance, our work investigates how different attention mechanisms behave across Transformer architectures and NLP tasks. We conduct an extensive comparative study of standard attention, linear attention, sparse attention, sliding-window attention, and FlashAttention, evaluating them not only across tasks such as masked language modeling, next-character prediction, and translation, but also across architectural types: encoder-only, decoder-only, and encoder–decoder models. This broader perspective reveals that linear attention, while attractive for its low memory footprint, struggles particularly in decoder-only setups like GPT, leading to higher loss and perplexity. To address this limitation, we introduce two hybrid attention mechanisms that enhance linear attention using structural ideas drawn from sparse and sliding-window attention. One emphasizes localized token interactions; the other incorporates sparse global patterns. The goal is to increase the representational power of linear attention without negating its efficiency gains. Using a lightweight GPT model trained on the Tiny Shakespeare dataset, we show that both hybrid variants achieve loss and perplexity close to those of full attention, while maintaining significantly lower memory usage. Although these hybrids do not outperform standard attention, their ability to narrow the performance gap while remaining efficient suggests a promising path toward scalable Transformer architectures suitable for deployment in constrained environments. 6
List of Abbreviations Abbreviation Meaning attn attention bwd backward ctx context dim dimension doc document enc encoder FFN Feed Forward Network GPU Graphics Processing Unit GPT Generative Pretrained Transformer grad gradient IO Input/Output k/v key/value (in attention) mem memory MHA Multi-Head Attention nctx number of context tokens n embd embedding size n head number of attention heads n layer number of layers n vocab vocabulary size NLL Negative Log Likelihood param parameter pos enc positional encoding QKV Query/Key/Value rel pos enc relative positional encoding res residual RMSNorm Root Mean Square Normalization seq len sequence length softmax softmax function std standard deviation sw sliding window TFM Transformer vocab vocabulary win size window size 7
Contents Acknowledgements...................................... 2 Abstract............................................ 3 Motivation .......................................... 6 Abbreviations......................................... 7 1 Background and Related Work 15 1.1 Transformer Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.1.1 From Sequential Constraints to Parallelized Context: How Transformers Overcome RNN Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.1.2 Overview of the Transformer Architecture . . . . . . . . . . . . . . . . . . 18 1.1.3 Self-Attention.................................. 20 1.1.4 Multi-headAttention ............................. 24 1.1.5 The Feed-Forward Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.1.6 PositionalEncoding .............................. 26 1.1.7 Add & Normalize Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.1.8 The Final Linear and Softmax Layers (Decoder) . . . . . . . . . . . . . . 30 1.1.9 Encoder-Decoder Architecture and Information Flow in Transformers . . 31 1.2 The Transformer Tree of Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.2.1 TheEncoderBranch.............................. 33 1.2.2 TheDecoderBranch.............................. 34 1.2.3 The Encoder-Decoder Branch . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.3 Conclusion ....................................... 35 2 State of the Art in Attention Mechanisms 36 2.1 Linear Attention: A Kernel-Based Approach to Efficient Sequence Modeling . . . 36 2.1.1 Standard Attention: The Quadratic Bottleneck . . . . . . . . . . . . . . . 36 2.1.2 Kernel-Based Reformulation . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.3 Feature Map Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.4 Linear Complexity Derivation . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.5 Feature Map Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.1.6 Mathematical Analysis of Algorithmic Steps . . . . . . . . . . . . . . . . . 38 2.2 Sparse Attention Mechanisms: A Theoretical Analysis . . . . . . . . . . . . . . . 39 2.2.1 FormalDefinition................................ 39 2.2.2 Sparse Attention Patterns: Design and Theoretical Foundations . . . . . . 39 2.2.3 Theoretical Analysis of Complexity and Expressivity . . . . . . . . . . . . 41 2.3 Sliding Window Attention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.3.1 Theoretical Foundation: Locality in Sequence Modeling . . . . . . . . . . 41 2.3.2 Mechanism: Fixed-Length Contextual Windows . . . . . . . . . . . . . . . 42 2.3.3 Receptive Field Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.3.4 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3.5 ComplexityAnalysis.............................. 43 2.4 Understanding Flash Attention: Efficient Transformer Attention Mechanisms . . 44 8
Chapter 1 Background and Related Work This chapter delves into the foundational components of Transformer models, examining the core mechanisms that enable their effectiveness. We begin by exploring the attention mechanism, which serves as the cornerstone of the Transformer architecture. The attention mechanism, introduced in [1], revolutionized sequence modeling by enabling parallelized computation and direct access to global context. Subsequently, we introduce the additional components necessary to construct a functional Transformer encoder. Furthermore, we highlight the architectural distinctions between the encoder and decoder modules. By the end of this chapter, the reader will have a comprehensive understanding of Transformer model architecture. Additionally, we present a taxonomy of Transformer variants to provide insight into the vast landscape of models that have emerged in recent years. Notable variants include BERT [2], RoBERTa [11], ALBERT [9], and DistilBERT [14], each addressing specific challenges in model efficiency and performance. Before dissecting the architecture that sparked the Transformer revolution, it is essential to understand the motivations and challenges that led to its development. 1.1 Transformer Architecture This section provides an in-depth exploration of the Transformer architecture, which has revolutionized the field of natural language processing (NLP) and machine learning. We begin by discussing the limitations of traditional sequential models, such as Recurrent Neural Networks (RNNs), and how the Transformer model overcomes these constraints through parallelization and attention mechanisms. A comprehensive overview of the Transformer architecture is then presented, delving into key components such as self-attention, multi-head attention, the feedforward layer, and positional encoding. 1.1.1 From Sequential Constraints to Parallelized Context: How Transformers Overcome RNN Limitations Fundamental Limitations of RNNs Recurrent Neural Networks (RNNs) process sequential data iteratively, updating a hidden state at each timestep based on the current input and prior hidden state. While this mimics human text consumption, it introduces critical bottlenecks: •Sequential Processing and Lack of Parallelization: RNNs cannot parallelize computation, as each timestep depends on the output of the previous step. This sequential 15
dependency creates inefficiencies in training, particularly for long sequences, where hardware acceleration (e.g., GPUs/TPUs) cannot exploit parallelism. Figure 1.1: Sequential processing in RNNs. •Degradation of Long-Range Dependencies: RNNs propagate contextual information through a chain of hidden states. Over long sequences, repeated nonlinear transformations cause vanishing or exploding gradients, impairing the model’s ability to retain distant dependencies. Transformers address this issue through self-attention, as demonstrated in [1], and further improvements in long-range dependency modeling have been achieved in models like Longformer [17]. Even advanced variants like LSTMs and GRUs, which regulate information flow via gating mechanisms, rely on sequential propagation, forcing distant tokens to traverse intermediate states. This ”daisy-chain” processing risks information loss or distortion. •Indirect Contextual Access: Bidirectional RNNs partially mitigate positional bias by aggregating forward and backward hidden states. However, they still process sequences sequentially within each direction and combine outputs only after full traversal, limiting direct access to global context. Transformers: Architectural Innovations Transformers address RNN limitations through three interconnected innovations: •Self-Attention Mechanism and Parallelization: The core innovation of transformers is self-attention, which computes pairwise relevance scores between all tokens in a sequence. This mechanism, first proposed in [1], allows transformers to model longrange dependencies efficiently by attending to all tokens simultaneously. For each token, the output is a weighted sum of embeddings from all other tokens, with weights reflecting contextual relevance. This allows direct access to distant positions without traversing intermediate steps, preserving long-range dependencies. Multi-head attention extends this by capturing diverse contextual relationships across multiple representation subspaces. The effectiveness of multi-head attention has been further analyzed in [15], which demonstrates that specialized heads often handle specific linguistic phenomena. Crucially, self-attention operates on all tokens simultaneously, enabling full parallelization during training and eliminating sequential bottlenecks. 16
Figure 1.2: Self-attention mechanism in Transformers. •Positional Encoding and Inherent Bidirectionality: Unlike RNNs, which implicitly encode positional information through processing order, transformers explicitly inject positional data via positional embeddings. The use of positional embeddings, as described in [1], ensures that transformers retain sequence information without sacrificing parallelization. These learned or fixed vectors are added to token embeddings, preserving sequence order while maintaining parallelization. Furthermore, self-attention inherently incorporates bidirectional context by attending to all positions in a single pass. Unlike bidirectional RNNs, which require separate forward and backward processing, transformers holistically model relationships between tokens in all directions, enhancing contextual awareness without computational redundancy. This bidirectionality is a key feature of models like BERT [2], which leverages transformers to capture context from both directions simultaneously. •Training Parallelism: The transformer’s architecture enables simultaneous computation across the entire sequence during training. Unlike RNNs, which process tokens stepwise, transformers leverage parallel hardware (e.g., GPUs) to compute representations for all tokens at once. This maximizes computational efficiency, accelerates convergence, and scales effectively to large datasets. The parallelizable nature of transformers, as highlighted in [1], has made them the architecture of choice for large-scale language models like BERT [2] and RoBERTa [11]. 17
Figure 1.3: Training parallelism in Transformers. Conclusion Transformers surpass RNNs by replacing sequential processing with parallelizable self-attention, enabling efficient training and robust modeling of global dependencies. This architectural shift, introduced in [1], has been further refined in models like BERT [2] and RoBERTa [11], which leverage transformers for tasks requiring deep contextual understanding. These innovations direct contextual access through attention, explicit positional encoding, and inherent bidirectionality have rendered transformers the dominant architecture for tasks such as machine translation, text generation, and document summarization. 1.1.2 Overview of the Transformer Architecture The original Transformer model is built upon an encoder-decoder architecture, which has been extensively used in sequence-to-sequence tasks such as machine translation. This architecture, introduced in [1], consists of two key components: •Encoder: Transforms an input sequence of tokens into a sequence of embedding vectors, commonly referred to as the hidden state or contextual representation. •Decoder: Utilizes the encoder’s hidden state to iteratively generate an output sequence of tokens, one token at a time. As illustrated in Figure 1.4, the encoder and decoder are composed of multiple building blocks: •Tokenization and Embedding: The input text is tokenized and mapped to token embeddings. Since self-attention lacks inherent positional awareness, positional embeddings are incorporated to preserve the sequential nature of text. This approach, first proposed in [1], ensures that transformers retain sequence information without sacrificing parallelization. •Stacked Layers: The encoder consists of multiple layers, akin to convolutional layers in computer vision, each responsible for progressively refining representations. The decoder follows a similar layered structure with additional mechanisms for attending to encoder outputs. 18
•Autoregressive Decoding: The decoder receives the previously generated tokens as input, alongside the encoder’s outputs, to predict the next token in the sequence. This iterative process continues until a special end-of-sequence (EOS) token is encountered or a maximum sequence length is reached. While initially designed for sequence-to-sequence tasks, the Transformer architecture has since evolved, giving rise to three major model categories: •Encoder-only models: These generate rich numerical representations of text, making them well suited for tasks like text classification and named entity recognition. Examples include BERT [2], RoBERTa [11], and DistilBERT [14], which leverage bidirectional attention. •Decoder-only models: Designed for autoregressive generation, these models predict the most probable next word based on left-context inputs. The GPT family, as described in [3], falls under this category, utilizing causal attention mechanisms. •Encoder-decoder models: Tailored for complex sequence mappings, these models excel in translation and summarization tasks. Examples include BART and T5, which integrate encoder and decoder components for robust text generation. Although these classifications provide a general framework, the boundaries between model applications are often fluid. For instance, decoder-only models like GPT can be adapted for translation, while encoder-only models like BERT can be used for summarization. Having established a high-level understanding of Transformer architecture, we now proceed to a detailed examination of the encoder’s inner workings. 19
Figure 1.4: Overview of the Transformer architecture, highlighting the encoder-decoder structure and key components. 1.1.3 Self-Attention Building an Intuitive Understanding of the Self-Attention Mechanism Self-attention is a fundamental mechanism that allows neural networks to dynamically assign varying levels of importance, or ”attention,” to different elements within a sequence. In the context of textual data, these elements correspond to token embeddings vector representations of individual tokens within a given sequence. For instance, in BERT [2], each token is encoded as a 768-dimensional vector. The term ”self” in self-attention highlights that attention weights are computed across all hidden states within the same sequence, such as all hidden states within the encoder. This is distinct from traditional attention mechanisms in recurrent models, where attention is computed between encoder hidden states and the decoder’s hidden state at each decoding step. The central idea of self-attention, as introduced in [1], is to leverage the entire sequence to compute a weighted sum of each token embedding. Instead of using static embeddings, the self-attention mechanism refines token representations by incorporating contextual information. Mathematically, given a sequence of token embeddings x1, . . . , xn, self-attention generates a new sequence of embeddings x′ 1, . . . , x′ n, where each transformed embedding x′ iis computed as a weighted sum of all token embeddings in the sequence: 20
x′ i= n X j=1 wjixj To understand the intuition behind self-attention, consider the word ”flies” in isolation it could refer to insects or be the present tense of the verb ”fly.” However, when placed in a sentence like ”Time flies like an arrow,” the surrounding words provide crucial context, clarifying that ”flies” is a verb. The self-attention mechanism captures such contextual dependencies by assigning greater weight wji to the most relevant tokens, such as ”time” and ”arrow,” while diminishing the influence of less relevant ones. A visual representation of this process illustrates how self-attention allows different interpretations of the same token depending on the context in which it appears. Figure 1.5: Visualization of self-attention weights for the word ”flies” in different contexts. Detailed Computation of Self-Attention The self-attention mechanism consists of several sequential steps that transform input embeddings into context-aware representations. These steps, as introduced in [1], can be understood as follows: •Generating Query, Key, and Value Vectors: Each word in the input sequence is first mapped to three distinct vectors Query (Q), Key (K), and Value (V) which are derived by multiplying the input word embeddings with learnable weight matrices. Given an input word embedding vector xi, the transformation can be expressed as: qi=WQxi, ki=WKxi, vi=WVxi where WQ,WK, and WVare learnable weight matrices, and qi,ki, and viare the corresponding query, key, and value vectors. 21
Figure 1.6: Generation of Query, Key, and Value vectors. •Computing Attention Scores: The attention score for each word is determined by computing the dot product between its query vector and the key vectors of all words in the sequence. This measures the relevance of each word to the current word: scoreij =qi·kj where scoreij represents the attention score between the ith and jth words. •Scaling the Scores: To stabilize gradients and improve learning, the scores are scaled by the square root of the dimension of the key vectors, denoted as dk: score′ ij =scoreij √dk where dkis typically set to 64, as per the original Transformer implementation [1]. •Applying Softmax: The scaled scores are then passed through a softmax function to normalize them into probability distributions: αij =escore′ ij Pjescore′ ij These normalized attention scores determine the influence of each word on the final representation of the current word. •Computing Weighted Sum of Value Vectors: The output representation for each word is obtained by multiplying the value vectors with the attention weights and summing them: zi=X j αijvj This ensures that the model aggregates information from all relevant words, effectively encoding context-dependent representations. 22
Figure 1.7: Computation of Self-Attention. Matrix-Based Implementation of Self-Attention To enhance computational efficiency, self-attention is implemented in matrix form, allowing parallelized computation. The steps are as follows: •Constructing Query, Key, and Value Matrices: Instead of processing each word individually, we represent all input embeddings as a matrix X, and compute the Q,K, and Vmatrices as follows: Q=XWQ, K =XWK, V =XWV where Xis the matrix containing word embeddings, and WQ,WK, and WVare learnable weight matrices. Figure 1.8: Matrix-based computation of Query, Key, and Value matrices. •Computing Scaled Attention Scores and Applying Softmax and Weighting 23
Values: Using matrix multiplication, we compute all pairwise attention scores simultaneously: S=QKT √dk where Sis the attention score matrix. The softmax function is then applied row-wise to obtain the attention weight matrix A: A= softmax(S) Finally, the output of the self-attention mechanism is computed as: Z=AV This results in a refined representation Z, which integrates contextually relevant information from the entire sequence. Figure 1.9: Matrix-based computation of self-attention output. This matrix formulation significantly accelerates computation, making the Transformer architecture highly efficient and scalable for various NLP tasks [1]. 1.1.4 Multi-head Attention In a basic self-attention mechanism, attention scores and weights are computed directly from token embeddings. However, the self-attention layer introduces additional complexity by applying three independent linear transformations to each embedding, generating the Query (Q),Key (K), and Value (V) vectors. These learned projections allow the model to capture different relationships within the input sequence, with each projection parameterized by distinct weight matrices. To further enhance the model’s ability to capture diverse patterns, multi-head attention is introduced. Instead of relying on a single attention mechanism, multiple independent sets of Q, K, and V matrices each representing a separate attention head are used. Each head learns different aspects of token relationships, enabling the model to focus on multiple linguistic structures simultaneously. The multi-head attention mechanism, as described in [1], is formally expressed as: MultiHead(Q, K, V ) = Concat(head1,head2,...,headh)WO where each head is computed as: headi= Attention(QW Q i, KWK i, V WV i) 24
•Vis the vocabulary size. •The softmax function ensures that all probabilities are positive and sum to 1, making the output interpretable as a probability distribution over possible words. Once the probability distribution is computed, the model selects the word with the highest probability as the predicted token for that time step. Figure 1.14: The Final Linear and Softmax Layers. 1.1.9 Encoder-Decoder Architecture and Information Flow in Transformers Encoder: Contextual Representation Generation The encoder transforms an input sequence of tokens into a high-dimensional, contextually enriched representation. It consists of a stack of identical layers, each containing two main components: the multi-head self-attention mechanism and the position-wise feed-forward network (FFN). The self-attention mechanism computes relationships between all tokens in the sequence, allowing the model to capture long-range dependencies and contextual information. The FFN applies non-linear transformations to refine these representations. Residual connections and layer normalization are used to stabilize training and improve gradient flow. As the input sequence passes through each layer, the encoder progressively refines the token representations, ultimately producing a final output zthat encapsulates the global context of the input sequence. Decoder: Auto-Regressive Generation with Contextual Guidance The decoder generates the output sequence token by token, conditioned on both the encoder’s output zand the previously generated tokens. It also consists of a stack of identical layers, but with three key components: masked multi-head self-attention,encoder-decoder multihead attention, and the position-wise FFN. The masked self-attention ensures that each token is generated based only on the preceding tokens, preserving the auto-regressive property. The encoder-decoder attention allows the decoder to focus on relevant parts of the encoder’s output z, enabling it to align input and output sequences effectively. The FFN further refines the representations. Like the encoder, the decoder uses residual connections and layer normalization to stabilize training. During inference, the decoder iteratively predicts tokens, appending each new token to the output sequence until completion. 31
Encoder-Decoder Synergy: Cross-Attention and Information Flow The encoder and decoder work together through the encoder-decoder attention mechanism, which is the core of their interaction. The encoder processes the input sequence in parallel, producing a contextualized representation z. The decoder, during its auto-regressive generation, uses this representation to guide its predictions. At each decoding step, the encoderdecoder attention sub-layer computes attention weights between the decoder’s current state (queries) and the encoder’s output z(keys and values). This allows the decoder to dynamically retrieve relevant information from the input sequence, ensuring that the generated output is contextually aligned with the input. For example, in translation tasks, the decoder can focus on specific input tokens (e.g., a subject or verb) when generating the corresponding output tokens. This interplay between the encoder and decoder enables the Transformer to handle complex sequence-to-sequence tasks efficiently and effectively. 1.2 The Transformer Tree of Life Over time, each of the three main transformer architectures has undergone an evolution of its own. This is illustrated in the Figure below , which shows a few of the most prominent models and their descendants. Figure 1.15: An overview of some of the most prominent transformer architectures This family tree by no means provides a complete overview of all existing transformer architectures; it simply highlights a few of the architectural milestones. Having covered the original 32
Transformer architecture in depth in previous sections, we now examine some of the key descendants, starting with the encoder branch. 1.2.1 The Encoder Branch The first encoder-only model based on the Transformer architecture was BERT. At the time it was published, it outperformed all state-of-the-art models on the popular GLUE benchmark [4], which measures natural language understanding (NLU) across several tasks of varying difficulty. Subsequently, the pretraining objective and the architecture of BERT have been adapted to further improve performance. Encoder-only models still dominate research and industry for NLU tasks such as text classification, named entity recognition, and question answering. Let’s examine the BERT model and its variants: BERT BERT is pretrained with the dual objectives of predicting masked tokens in texts and determining if one text passage is likely to follow another [2]. The former task is called masked language modeling (MLM) and the latter next sentence prediction (NSP). DistilBERT Although BERT delivers strong results, its size can make it challenging to deploy in environments requiring low latencies. By using knowledge distillation during pretraining, DistilBERT achieves 97% of BERT’s performance while using 40% less memory and being 60% faster [14]. RoBERTa A study following BERT’s release revealed that its performance can be further improved by modifying the pretraining scheme. RoBERTa is trained longer, on larger batches with more training data, and drops the NSP task [11]. Together, these changes significantly improve its performance compared to the original BERT model. XLM Several pretraining objectives for building multilingual models were explored in the cross-lingual language model (XLM) [8], including autoregressive language modeling from GPT-like models and MLM from BERT. Additionally, the authors introduced translation language modeling (TLM), an extension of MLM to multiple language inputs. These pretraining tasks achieved state-of-the-art results on several multilingual NLU benchmarks and translation tasks. XLM-RoBERTa Following XLM and RoBERTa, the XLM-RoBERTa (XLM-R) model advances multilingual pretraining by massively upscaling the training data [6]. Using the Common Crawl corpus, the researchers created a dataset with 2.5 terabytes of text and trained an encoder with MLM on this dataset. This approach significantly outperforms XLM and multilingual BERT variants, especially on low-resource languages. ALBERT ALBERT introduced three changes to enhance encoder architecture efficiency [9]. First, it decouples token embedding dimension from hidden dimension, allowing smaller embedding dimensions and saving parameters. Second, all layers share parameters, decreasing effective parameter 33
count further. Finally, NSP is replaced with sentence-ordering prediction. These changes enable training of larger models with fewer parameters while achieving superior NLU task performance. ELECTRA Addressing a limitation of standard MLM pretraining where only masked token representations are updated, ELECTRA employs a two-model approach [19]: a small model works as a standard masked language model predicting masked tokens, while a second model (the discriminator) predicts which tokens were originally masked. This makes training 30 times more efficient, as the discriminator performs binary classification for every token. DeBERTa DeBERTa introduces two architectural innovations [21]. First, each token is represented by two vectors one for content, another for relative position disentangling content from position and enabling better modeling of token pair dependencies. Second, absolute position embeddings are added before the softmax layer of the token decoding head. DeBERTa was the first model (as an ensemble) to exceed human baseline performance on the SuperGLUE benchmark [16]. 1.2.2 The Decoder Branch Progress on transformer decoder models has been largely driven by OpenAI. These models excel at predicting the next word in a sequence and are primarily used for text generation tasks. Their advancement has been fueled by larger datasets and scaling to increasingly larger model sizes: GPT GPT combined two key NLP innovations [3]: the efficient transformer decoder architecture and transfer learning. The model was pretrained by predicting the next word based on previous ones, trained on the BookCorpus, achieving impressive results on downstream classification tasks. GPT-2 Building on GPT’s success, the original model and training set were upscaled to produce GPT-2 [12], capable of generating long sequences of coherent text. Due to potential misuse concerns, the model was released gradually, with smaller models published before the full version. CTRL While models like GPT-2 can continue input sequences (prompts), users have limited control over generation style. The Conditional Transformer Language (CTRL) model addresses this by incorporating ”control tokens” at sequence beginnings [7], enabling style control and diverse text generation. GPT-3 Following scaling from GPT to GPT-2, analysis revealed power laws governing relationships between compute, dataset size, model size, and language model performance [22]. GPT-2 was subsequently upscaled by a factor of 100 to create GPT-3 [18] with 175 billion parameters. Beyond generating realistic text, the model demonstrates few-shot learning capabilities across novel tasks. 34
1.2.3 The Encoder-Decoder Branch While single encoder or decoder stacks have become common, several encoder-decoder Transformer variants offer novel applications across both NLU and NLG domains: T5 The T5 model unifies NLU and NLG tasks by converting them to text-to-text tasks [13]. All tasks are framed as sequence-to-sequence problems, naturally suited to encoder-decoder architectures. For classification, the text serves as encoder input while the decoder generates the label as text rather than a class. Using the large C4 dataset, T5 is pretrained with masked language modeling and SuperGLUE tasks translated to text-to-text format. The largest 11 billion parameter model achieved state-of-the-art results across multiple benchmarks. BART BART combines BERT and GPT pretraining procedures within the encoder-decoder architecture [10]. Input sequences undergo various transformations (masking, sentence permutation, token deletion, document rotation) before being passed through the encoder, with the decoder reconstructing original texts. This versatility enables both NLU and NLG tasks with state-ofthe-art performance. M2M-100 Conventional translation models are built for single language pairs and directions, limiting scalability. M2M-100 is the first model capable of translating between any of 100 languages [20], providing high-quality translations between rare and underrepresented languages. The model uses prefix tokens to indicate source and target languages. BigBird A primary limitation of transformer models is maximum context size due to attention mechanism’s quadratic memory requirements. BigBird addresses this through sparse attention that scales linearly [23], expanding context from typical 512 tokens in BERT models to 4,096 tokens. This particularly benefits tasks requiring long dependencies, such as text summarization. 1.3 Conclusion In conclusion, the Transformer architecture has significantly advanced NLP by addressing the inherent limitations of previous models, offering parallelization and efficient handling of longrange dependencies. The components discussed in this chapter form the foundation for many state-of-the-art models today, highlighting the importance of self-attention, multi-head attention, and positional encoding in improving performance. Understanding the Transformer’s architecture is crucial for exploring its applications and innovations in modern machine learning research, including the modifications and advancements in attention mechanisms that will be examined in subsequent chapters. 35
Chapter 2 State of the Art in Attention Mechanisms The Transformer architecture, driven by the power of the self-attention mechanism, has revolutionized the field of deep learning, particularly in natural language processing and computer vision. However, the original attention mechanism introduced in ”Attention is All You Need” scales quadratically with sequence length, posing challenges for long sequences and large-scale models. As the demand for more efficient and scalable models has grown, numerous innovations have emerged to improve attention’s computational and memory efficiency without sacrificing model quality. In this chapter, we explore several state-of-the-art advances in attention mechanisms that aim to address these challenges. We present and analyze Linear Attention, Sparse Attention, Flash Attention, and Sliding Window Attention each offering unique solutions to the bottlenecks of standard attention. By understanding the core ideas, motivations, and trade-offs behind these methods, we gain deeper insight into how attention mechanisms continue to evolve to meet the demands of modern deep learning tasks. 2.1 Linear Attention: A Kernel-Based Approach to Efficient Sequence Modeling Linear attention represents a fundamental advancement in transformer architecture, addressing the quadratic complexity bottleneck that limits the scalability of standard attention mechanisms [1]. By reformulating attention through kernel methods, linear attention achieves O(T) complexity while preserving the essential modeling capabilities of the attention mechanism. This exposition presents a rigorous mathematical treatment of linear attention, emphasizing its theoretical foundations and computational advantages. 2.1.1 Standard Attention: The Quadratic Bottleneck In the standard transformer, self-attention computes pairwise interactions between all tokens in a sequence [1]. For a sequence of length Twith embedding dimension d, the attention output for token iis given by: Attention(Q, K, V )i=PT j=1 eq⊤ ikjvj PT n=1 eq⊤ ikn(2.1) where qi∈Rdis the query vector for token i,kj∈Rdis the key vector for token j, and vj∈Rdvis the corresponding value vector. 36
Computing this operation requires O(T2d) time complexity and O(T2) memory for storing the attention matrix. This quadratic scaling renders standard attention prohibitively expensive for long sequences, motivating the development of more efficient alternatives [17]. 2.1.2 Kernel-Based Reformulation The core insight behind linear attention is that the softmax attention mechanism can be reinterpreted as a normalized kernel function [15]. Specifically, the softmax weight between query iand key jcan be expressed as: αij =eq⊤ ikj PT n=1 eq⊤ ikn(2.2) This expression can be generalized as a kernel similarity: αij =K(qi, kj) PT n=1 K(qi, kn)(2.3) where K(·,·) is a kernel function measuring similarity between vectors. 2.1.3 Feature Map Decomposition The critical mathematical insight enabling linear complexity is the approximation of the kernel function using decomposable feature maps [17]. For certain kernels, there exist transformations ϕ:Rd→Rd′such that: K(qi, kj)≈ϕ(qi)⊤ϕ(kj) (2.4) This decomposition allows us to rewrite the attention mechanism as: Attention(Q, K, V )i=PT j=1 ϕ(qi)⊤ϕ(kj)vj PT n=1 ϕ(qi)⊤ϕ(kn)(2.5) By applying the distributive property, we can factor out query-dependent terms: Attention(Q, K, V )i= ϕ(qi)⊤PT j=1 ϕ(kj)v⊤ j ϕ(qi)⊤PT n=1 ϕ(kn)(2.6) 2.1.4 Linear Complexity Derivation Let us define two key terms that can be precomputed: •M=PT j=1 ϕ(kj)v⊤ j∈Rd′dv(value aggregation matrix) •u=PT n=1 ϕ(kn)∈Rd′(normalization vector) The attention output then simplifies to: Attention(Q, K, V )i=ϕ(qi)⊤M ϕ(qi)⊤u(2.7) This reformulation yields a critical computational advantage: both Mand uare computed once for the entire sequence, requiring O(Td′dv) and O(Td′) operations respectively. The perquery computation then requires only O(d′dv) operations, leading to an overall time complexity of O(Td′dv) linear in sequence length T. 37
2.1.5 Feature Map Selection The choice of feature map ϕdetermines both the expressivity and computational efficiency of linear attention [17]. The feature map must satisfy several properties: 1. Kernel approximation quality:ϕ(qi)⊤ϕ(kj) should closely approximate eq⊤ ikj 2. Computational efficiency:ϕshould be fast to compute 3. Non-negativity: To preserve the probabilistic interpretation of attention Common choices include: ELU+1 Feature Map ϕ(x) = ELU(x) + 1 (2.8) where ELU is the Exponential Linear Unit activation function. This transformation ensures non-negativity while maintaining differentiability, approximating the exponential kernel reasonably well for practical purposes. Positive Random Features For more precise approximation of the exponential kernel, random Fourier features can be employed: ϕRFF(x) = eW x √m(2.9) where W∈Rmd is a random projection matrix with entries drawn from a Gaussian distribution. This approach offers unbiased estimation of the true softmax attention, with approximation error decreasing as the projection dimension mincreases. 2.1.6 Mathematical Analysis of Algorithmic Steps The linear attention algorithm can be decomposed into three phases: 1. Feature Mapping: Transform queries and keys: ΦQ=ϕ(Q), ΦK=ϕ(K) Complexity: O(Td′) 2. Aggregation: Compute M=PT j=1 ϕ(kj)v⊤ j Implementable as matrix multiplication: M= Φ⊤ KV Complexity: O(Td′dv) Compute u=PT j=1 ϕ(kj) Implementable as vector summation: u= Φ⊤ K1 Complexity: O(Td′) 3. Output Computation: For each query i: outputi=ϕ(qi)⊤M ϕ(qi)⊤u+ϵ Complexity: O(Td′dv) The total complexity is dominated by the aggregation and output computation phases, yielding O(Td′dv) linear in sequence length T. 38
Linear attention represents a mathematically elegant solution to the quadratic scaling problem in transformer architectures [1]. By reformulating attention through kernel methods and feature map decomposition, it achieves linear computational complexity while preserving the essential modeling capabilities of the attention mechanism. The performance-efficiency trade-off is controlled primarily through the choice of feature map, offering a flexible framework for efficient sequence modeling across diverse applications. This kernel-based approach not only provides computational efficiency but also establishes theoretical connections between transformers and other sequence modeling paradigms, opening avenues for further theoretical analysis and architectural innovation in efficient sequence processing. 2.2 Sparse Attention Mechanisms: A Theoretical Analysis The standard attention mechanism in transformer models [1] computes pairwise interactions across all tokens in a sequence, leading to a computational complexity of O(n2) for sequence length n. While effective for modeling relationships in shorter sequences, this quadratic scaling becomes computationally prohibitive for tasks requiring long-context processing, such as genome analysis or book summarization. Sparse attention addresses this fundamental bottleneck by restricting the attention matrix to a strategically selected subset of token pairs, thereby reducing computational complexity to O(n) or O(nlog n) while preserving the model’s ability to capture both local and global dependencies. 2.2.1 Formal Definition Given an input sequence X∈Rnd where nis the sequence length and dis the embedding dimension, sparse attention computes an output Z∈Rnd as: Zi=X j∈S(i) Softmax QiK⊤ j √d!Vj(2.10) where S(i)⊂ {1,2, . . . , n}defines a sparsity pattern determining which tokens the i-th token attends to, with |S(i)| ≪ n. The key innovation lies in the design of these sparsity patterns, which must balance computational efficiency with the preservation of essential information flow between tokens. 2.2.2 Sparse Attention Patterns: Design and Theoretical Foundations Local (Sliding Window) Attention Local attention restricts each token to attend only to nearby tokens within a fixed radius w/2: Slocal(i) = {j:|i−j| ≤ w/2}(2.11) The theoretical basis for this pattern stems from the locality bias inherent in natural sequences like text and images, where syntactic and semantic relationships are often strongest between nearby tokens [5]. With a window size w, the computational complexity reduces to O(n·w), which becomes linear when wis a constant independent of n. Global Attention To enable long-range dependencies, global attention designates a small set of gspecial tokens (e.g., [CLS] tokens or positional markers) that can attend to and be attended by all tokens in the sequence: 39
Sglobal(i) = ({1,2, . . . , n}if i∈ G Gif i /∈ G (2.12) where Grepresents the set of global token indices. These tokens function as information aggregation and distribution centers, ensuring that all tokens in the sequence can influence and be influenced by these summary tokens, which is crucial for tasks requiring sequence-level understanding. Randomized Attention To prevent over-localization and ensure connectivity across the entire sequence, randomized attention patterns incorporate stochastically sampled connections: Srand(i) = {j1, j2, . . . , jr}where jk∼Uniform(1, n) (2.13) From a theoretical perspective, random patterns transform the attention graph into a smallworld network, guaranteeing a maximum path length of O(log n) between any two tokens [23]. This property ensures that information can flow between arbitrary token pairs through a logarithmic number of attention hops, allowing sparse attention to approximate full attention in expectation. Dynamic Sparse Attention Rather than using fixed patterns, dynamic sparse attention learns to identify important token interactions based on content: Sdynamic(i) = Top-k(f(Qi, K)) (2.14) where f:RdRnd →Rnrepresents a lightweight scoring function that produces importance scores for potential connections. This approach enables the model to adapt its attention structure to the specific content being processed for instance, focusing on semantically significant tokens while ignoring common stopwords. Figure 2.1: Sparse attention patterns visualization 40
2. Rescale the normalization factor: lnew =lold ·ecurrent max−new max 3. Add the contribution of the new element: lnew =lnew +exi−new max This online approach ensures that the normalization factor is continuously updated to reflect the current maximum value, maintaining numerical stability throughout the computation process while reducing the number of required passes through the data. Figure 2.6: Online softmax computation process Illustrated Example For vector X= [3,2,5,1], the online softmax computation proceeds as follows: 1. When processing the first element (3), we initialize the maximum to 3 and the normalization factor to e3−3= 1, representing the contribution of this element to the normalization sum. 2. When processing the second element (2), the maximum remains unchanged at 3, and we update the normalization factor to 1 + e2−3= 1 + e−1≈1.368, adding the contribution of the second element. 3. When processing the third element (5), we encounter a new maximum. We update the maximum from 3 to 5, and we must rescale the current normalization factor accordingly: 1.368 ·e3−5= 1.368 ·e−2≈0.185. We then add the contribution of the new element: 0.185 + e5−5= 0.185 + 1 = 1.185. 4. Finally, when processing the fourth element (1), the maximum remains at 5, and we update the normalization factor to 1.185 + e1−5= 1.185 + e−4≈1.187. This example demonstrates how the online softmax algorithm dynamically updates the maximum and normalization factor as it processes each element, reducing the need for multiple passes through the data. 47
Optimized Pseudocode Algorithm 2 Online Softmax 1: m0← −∞ 2: l0←0 3: for i= 1 to Ndo 4: mi←max(mi−1, xi) 5: li←li−1·emi−1−mi+exi−mi 6: end for 7: for u= 1 to Ndo 8: xu←exu−mN/lN 9: end for This approach reduces the required memory accesses to just one full pass through the vector for computing the max and normalization factor, followed by one pass for applying the normalization. The reduction in memory access operations significantly improves performance, especially for large vectors or matrices. 2.4.5 Block Matrix Multiplication in Flash Attention Block matrix multiplication forms a critical component of Flash Attention’s optimization strategy [25]. By decomposing the large attention matrix computation into smaller, manageable blocks, Flash Attention effectively utilizes the memory hierarchy of modern hardware accelerators such as GPUs and TPUs. Mathematical Formulation of Block Matrix Multiplication Consider the standard attention computation: O= softmax QKTV(2.19) where Q∈RNd,K∈RNd, and V∈RNd are the query, key, and value matrices, respectively, with Nbeing the sequence length and dthe feature dimension. In Flash Attention, these matrices are partitioned into Bblocks along the sequence dimension: Q= Q1 Q2 . . . QB ,K= K1 K2 . . . KB ,V= V1 V2 . . . VB (2.20) where each block Qi,Ki,Vi∈R(N/B)d. The attention matrix S=QKTis computed block-wise as: S= S11 S12 ··· S1B S21 S22 ··· S2B . . .. . ..... . . SB1SB2··· SBB (2.21) where each submatrix Sij =QiKT j∈R(N/B)(N/B)represents the attention scores between the i-th query block and j-th key block. 48
Block-wise Softmax Computation The softmax operation cannot be directly decomposed into blocks due to its global normalization. However, Flash Attention applies the online softmax algorithm at the block level by maintaining running statistics (maximum values and normalization factors) for each row of blocks. For each row iof the attention matrix, we process the blocks Si1, Si2, . . . , SiB sequentially, updating the maximum values and normalization factors as we go. This allows us to compute the softmax operation without materializing the entire attention matrix in memory. The output for each block Oican be computed as: Oi= B X j=1 softmax(Sij)Vj Where the softmax is computed using the online algorithm with properly maintained running statistics across blocks. Memory Efficiency Through Block Processing By processing the attention mechanism in blocks that fit in fast memory (SRAM or cache), Flash Attention reduces the need for frequent accesses to high-latency memory (HBM or DRAM). This is particularly important because memory bandwidth is often the bottleneck in attention computation rather than computational throughput. Each block is loaded into fast memory only once for processing, after which the intermediate results are updated without requiring additional high-latency memory accesses. This significantly reduces the memory bandwidth requirements compared to standard attention implementations. Furthermore, the block-wise approach allows for better utilization of memory hierarchy. The block sizes can be optimized based on the specific hardware architecture to maximize cache utilization and minimize cache misses. Optimal Block Size Determination The optimal block size for Flash Attention depends on several factors: 1. The size of available fast memory (SRAM or cache) 2. The dimensionality of the attention mechanism (head size and number of heads) 3. The characteristics of the underlying hardware architecture Flash Attention dynamically determines the optimal block size based on these factors, ensuring maximum computational efficiency while maintaining memory constraints. This adaptive approach allows Flash Attention to perform well across different hardware configurations and model architectures. 2.4.6 Flash Attention: Tiling and IO-Aware Algorithms Flash Attention extends the online softmax algorithm by incorporating tiling techniques and IOaware algorithmic design to further optimize attention computation [25, 24]. These techniques consider the hierarchical nature of modern memory systems and optimize operations accordingly. 49
IO-Aware Algorithmic Tiling Flash Attention partitions the attention matrix into smaller blocks or ”tiles” that can fit in fast memory (SRAM). This tiling approach is specifically designed to minimize data movement between different levels of the memory hierarchy, which is often the most significant performance bottleneck in matrix computations. Figure 2.7: IO-aware tiling in Flash Attention The tiling strategy incorporates several important considerations: First, it reduces the number of accesses to high-bandwidth memory (HBM) by ensuring that each tile is loaded into fast memory only once and processed completely before moving to the next tile. This minimizes the data transfer overhead, which can be substantial for large matrices. Second, it maximizes the utilization of on-chip memory (SRAM) by carefully selecting tile sizes that fit optimally in the available fast memory while providing sufficient computational work to amortize the memory transfer costs. Third, it allows for parallel processing of attention computations within each tile, taking advantage of the parallel processing capabilities of modern hardware accelerators. This parallelism is essential for achieving high computational throughput. Mathematical Formulation of Tiled Attention For a sequence partitioned into Bblocks, the attention computation can be rewritten as: Oi= B X j=1 softmax(Sij)Vj Where Sij represents the attention scores between blocks iand j, and Vjis the values matrix for block j. The key insight is that we can compute partial softmax results for each block and combine them using the online softmax algorithm, adjusting the normalization factors appropriately as we process each block. This approach allows us to process the attention mechanism in a memory-efficient manner without sacrificing mathematical correctness. For each row of blocks in the attention matrix, Flash Attention maintains running statistics (maximum values and normalization factors) that are updated as each block is processed. This 50
enables the computation of the softmax operation without materializing the entire attention matrix, significantly reducing memory requirements. Figure 2.8: Block-wise processing in Flash Attention Flash Attention Algorithm The Flash Attention algorithm combines tiling with the online softmax approach in a carefully orchestrated manner: First, it partitions the input matrices Q,K, and Vinto blocks that fit in SRAM, based on the available fast memory and the dimensions of the matrices. These blocks are sized to optimize memory utilization while providing sufficient computational work. Second, for each query block, it loads the query block into SRAM and processes all key-value blocks sequentially. For each key-value block, it loads the block into SRAM, computes partial attention scores, and updates the running maximum and normalization factors using the online softmax algorithm. This step is performed without materializing the entire attention matrix in memory. Third, it applies the final normalization to compute the output for each query block, using the accumulated statistics from processing all key-value blocks. This ensures that the softmax operation is computed correctly across the entire row of blocks. Finally, it combines all output blocks to form the complete output matrix, which represents the result of the attention mechanism. This approach significantly reduces memory bandwidth requirements and improves computational efficiency, allowing for processing of much longer sequences than traditional attention implementations. The careful orchestration of memory accesses and computational operations enables Flash Attention to achieve substantial performance improvements while maintaining mathematical correctness. Flash Attention significantly optimizes transformer models by combining safe softmax computation with block matrix multiplication and tiling techniques [25]. This approach enhances performance and memory efficiency, enabling the processing of longer sequences without sacrificing accuracy. The integration of online softmax computation and block-wise processing addresses computational and memory challenges, broadening the practical applications of transformers in 51
NLP, computer vision, and beyond. Flash Attention exemplifies the growing trend of hardwareaware algorithm design, offering a path for more energy efficient and scalable machine learning models. 2.5 Conclusion Attention mechanisms lie at the heart of many of today’s most powerful models, and optimizing their efficiency is crucial for scaling to longer contexts and larger datasets. Through our exploration of linear, sparse, flash, and sliding window attention, we have seen a range of strategies to reduce computational complexity, manage memory usage, and maintain or even improve performance. Each method embodies a distinct design philosophy from rethinking the mathematical structure of attention, to intelligently limiting the receptive field, to reorganizing memory access patterns for greater speed. While no single approach universally dominates, together they represent critical steps toward building faster, more capable models. This evolution of attention mechanisms not only enhances current architectures but also opens new avenues for future research in efficient and scalable deep learning. 52
Chapter 3 Experimental Results and Comparative Analysis Building on the previous chapter’s review of state-of-the-art attention mechanisms, this chapter presents a focused empirical comparison of five variants Standard, Sliding-Window, Sparse, Linear, and Flash Attention. We evaluate their performance across three tasks: next-character prediction with GPT on the Tiny Shakespeare corpus, masked-character prediction with BERTstyle models, and English-to-French translation using an encoder–decoder Transformer on a subset of the Tatoeba corpus. Our goal is to assess how each mechanism balances predictive quality, efficiency, and memory usage. By isolating the attention module and keeping all other settings constant, we aim to reveal the practical strengths and limitations of each approach, providing guidance on when and why to use them. 3.1 Experimental Setup and Implementation Details 3.1.1 Overview of Attention Mechanisms This work explores five distinct attention mechanisms, each designed to balance computational efficiency with the ability to model complex dependencies. The following provides a theoretical explanation of the underlying principles behind each implementation, abstracted from the codelevel details used in our experiments. •Scaled Dot-Product Attention This is the standard mechanism used in Transformer models, where each token attends to all previous tokens using dot products of their query and key vectors, scaled by the dimensionality of the embeddings. A softmax function converts these scores into attention weights, which are then used to compute a weighted sum of the value vectors. A causal mask ensures autoregressive behavior, preventing a token from attending to future positions. •Enhanced Sparse Attention Inspired by sparse attention frameworks like BigBird, this mechanism restricts attention to a structured set of tokens, including local neighbors, a few global tokens, and a learned selection of important positions. The sparsity pattern improves computational efficiency while retaining access to key contextual information. A small neural network predicts the importance of keys, enabling adaptive sparsity. 53
•Enhanced Linear Attention This mechanism approximates the softmax attention using kernel feature maps specifically the ELU + 1 transformation on queries and keys. The attention computation becomes linear in sequence length by reordering operations and removing the softmax. To maintain autoregressive behavior, a causal decay mask is applied. This approach significantly reduces memory and computational complexity. •Flash Attention Flash Attention leverages optimized GPU memory usage to compute exact attention with reduced overhead. It processes attention in small, register resident tiles to minimize reads and writes to high-bandwidth memory. This tiled approach, along with numerically stable softmax computation, enables faster and more efficient execution without approximation. •Sliding-Window Attention This variant restricts each token’s attention to a fixed-size local window around it. To capture longer dependencies, it optionally includes dilated attention hops and a small set of global tokens. Such a pattern is especially useful for long sequences, offering a trade-off between full attention expressivity and computation speed. 3.1.2 Evaluation Metrics We measure each attention variant on: Metric Description Training Time (minutes) Total time needed to train the model Peak GPU Memory (MB) Maximum memory used during training Average Inference Latency (ms) Time needed to process one input Next-character prediction: Perplexity How well the model predicts next characters (lower values are better) Masked-character prediction: Accuracy Percentage of correctly filled-in masked characters Translation: BLEU score Translation quality score (0-100, higher is better) Table 3.1: Evaluation metrics used in our comparative analysis 3.1.3 Experimental Setup •Compute: Google Colab (free tier) with an NVIDIA T4 GPU •PyTorch version: ≥2.0 (for Flash Attention fallback to native if available) 3.1.4 Experimental Philosophy and Fairness •Single-codebase: All models share identical code except for the attention module swap. •Architecture consistency: –GPT experiments use causal self-attention. –BERT experiments use bidirectional masked self-attention. 54
–Translation uses the same attention type for encoder self-attention, decoder masked self-attention, and cross-attention. •Controlled variables: same sequence length, embedding dims, optimizer, and training budget per task. •Limitations: constrained by Colab session limits and T4 memory models are kept small (block size ≤1024). 3.2 Comparison Using GPT Models 3.2.1 Task Definition Next-character prediction on Tiny Shakespeare: given a sequence of up to 128 characters, the model must predict the next character. This simple autoregressive task exposes how each attention mechanism handles causal dependency and sequential token mixing. 3.2.2 Model Configuration All GPT variants share the same core hyperparameters (from ModelConfig): vocab_size = 65 # Tiny Shakespeare’s 65-character alphabet n_embd = 64 # Embedding dimension n_head = 4 # Number of attention heads n_layer = 4 # Transformer blocks block_size = 128 # Context length batch_size = 32 max_iters = 4_200 dropout = config.dropout Only the attn type (sliding window, flash, standard, sparse, linear) differs between runs; everything else remains constant to ensure a fair comparison. 3.2.3 Dataset Tiny Shakespeare is a ∼1 MB corpus of Shakespeare’s complete works, containing roughly 111K characters and a 65-token vocabulary (letters, punctuation, whitespace). We split it into 90% train and 10% validation characters, with no further preprocessing. 3.2.4 Training Setup •Hardware: Google Colab free tier on a Tesla T4 GPU (≈16 GB RAM) •Optimization: AdamW with OneCycleLR scheduler (details per run) •Metrics logged: – Perplexity (train & validation) – Wall-clock training time (minutes until 4,200 iterations) – Peak GPU memory (MB) – Average inference latency (ms per forward pass, sequence length = 128) 55
3.2.5 Performance Results Training and Validation Loss Figure 3.1: Training and validation loss curves for five attention variants Training Loss: All five attention variants exhibit a rapid initial decrease in training loss, dropping from ∼4.4 to ∼2.7 within the first 200 steps as the models learn basic character dependencies. Thereafter, Flash Attention (green) continues to improve most aggressively, reaching a final loss of ≈1.43 by step 4,000. In contrast, Linear Attention (cyan) plateaus early settling around 2.27 suggesting its kernel approximation struggles to model fine-grained autoregressive structure. Standard (brown), Sliding-Window (blue), and Sparse (gray) attentions fall between these extremes, converging to ≈1.65–1.70. This ordering highlights Flash’s numerical stability and efficiency in gradient propagation versus the weaker representational power of Linear attention under identical configurations. Validation Loss: The validation curves mirror the training trends, underscoring generalization behavior. Flash Attention again achieves the lowest held-out loss (∼1.43), with very little overfitting gap. Sliding-Window, Standard, and Sparse attentions converge closely around 1.85–1.90, indicating similar capacity to model the validation set once properly trained. Linear attention’s validation loss stalls at ≈2.35, reflecting its higher bias. Notably, Sparse attention generalizes almost as well as plain self-attention despite its irregular sparse connectivity, while Flash’s memoryefficient kernel yields both fastest convergence and best generalization. 56
class ModelConfig: def __init__(self, attn_type, src_vocab_size, tgt_vocab_size): self.src_vocab_size = src_vocab_size self.tgt_vocab_size = tgt_vocab_size self.n_embd = 256 self.n_head = 2 self.n_layer = 2 self.block_size = 128 self.batch_size = 64 self.max_iters = 1200 self.dropout = config.dropout We apply Byte-Pair Encoding (BPE) tokenization separately to source and target. 3.4.3 Dataset We use a subset of the Tatoeba English-French parallel corpus, a volunteer-contributed collection of sentence translations. ManyThings.org reports 232,736 English-French pairs in the full Tatoeba release; for this study we loaded 30,000 randomly selected pairs for training and validation. The Tatoeba project maintains over 12.6 million sentences in 426 languages under CC BY, with 276 language pairs exceeding 10,000 translations [tatoeba]. 3.4.4 Training Setup •Hardware: Google Colab (free tier) with NVIDIA Tesla T4 (16 GB GDDR6) •GPU microarchitecture: T4 is built on NVIDIA’s Turing design •Available VRAM: Colab reports ∼15.8 GB available (≈1 GB reserved for ECC) •Optimizer: AdamW with cosine annealing and OneCycleLR schedules •Metrics: Wall-clock train time, peak GPU memory, avg. inference latency, and BLEU on validation 3.4.5 Performance Results Training and Validation Loss Figure 3.7: Training and validation loss for translation models with different attention mechanisms 63
Both the training and validation loss plots exhibit a consistent downward trend across steps for all attention types, which is a good indicator of successful learning. In terms of training loss, ”sparse” and ”flash” attentions achieve slightly lower losses than the others towards the end, suggesting more efficient training. Validation loss mirrors this, with ”sparse” achieving the lowest final validation loss, closely followed by ”flash” and ”sliding window.” ”Standard” attention consistently maintains a slightly higher loss. This indicates that while all models are learning, ”sparse” and ”flash” attention mechanisms generalize slightly better to unseen data in this setup. BLEU Score Figure 3.8: BLEU scores for translation models with different attention mechanisms The BLEU score plot shows the translation quality of the different attention mechanisms across training steps. Overall, the ”sliding window” and ”linear” attention mechanisms achieve the highest BLEU scores by the end of training, with ”sliding window” reaching a peak score above 60. However, the performance is quite volatile across all methods, indicating some instability in BLEU during training. This instability is likely due to the small dataset size and limited training time, as the models were trained on a constrained setup using Google Colab’s free version, which can prevent transformers from fully stabilizing. Despite this volatility, the trends remain clear enough to extract meaningful comparative insights across the different attention mechanisms. ”Flash” and ”standard” methods show moderate BLEU improvements, while ”sparse” lags behind slightly but still shows competitive peaks. These results suggest that while all attention variants are capable, ”sliding window” and ”linear” have the most potential for achieving higher translation quality in this setup. Efficiency Measures (Training Time, Peak GPU Memory, and Inference Latency) The bar plots provide a clear view of the computational trade-offs. In terms of training time, ”flash” attention is the fastest, closely followed by ”standard” and ”sliding window,” whereas ”sparse” takes the longest by a wide margin. Peak GPU memory usage is fairly similar across 64
Figure 3.9: Efficiency metrics for translation models with different attention mechanisms models, but ”flash” uses slightly less memory compared to the others, highlighting its efficiency. When it comes to inference latency, ”standard” has the lowest average latency, making it the fastest for deployment, while ”linear” is the slowest by a significant margin. ”Flash” again stands out by offering a good balance between speed and memory usage, while ”sliding window” offers a strong BLEU performance but at the cost of slightly higher inference latency. Summary of the Results Attention Type Train Time (min) Peak GPU Mem (MB) Inf. Latency (ms) BLEU Score standard 2.71 292.26 58.73 35.36 sparse 8.54 277.29 82.90 32.07 linear 4.97 292.42 222.76 57.74 flash 3.28 280.87 102.79 37.99 sliding window 4.33 292.67 108.69 63.89 Table 3.6: Summary of performance metrics for translation models Overall Findings From the results across BLEU score, loss curves, and efficiency metrics, it’s clear that different attention mechanisms offer different trade-offs. The sliding window attention achieved the highest BLEU score, suggesting it delivers the best translation quality, though at the cost of slightly higher inference latency. Flash attention consistently stood out for its excellent balance between training speed, memory efficiency, and low inference latency, making it a very practical choice for deployment scenarios where both performance and speed matter. Sparse attention, while achieving strong validation loss and competitive BLEU scores, suffered from significantly longer training times, which could be a limitation in resource constrained settings. Linear attention, despite achieving high BLEU scores at some points, showed the highest inference latency, making it less attractive for real-time applications. Finally, the standard attention model performed decently across the board but was generally outpaced by the more specialized variants. In conclusion, the best attention mechanism depends on the application needs: for highest quality, sliding window is preferable; for efficiency, flash stands out as the optimal choice. 3.4.6 Ranking of Attention Mechanisms Higher BLEU and lower resources are better: 65
Metric 1st place 2nd place 3rd place 4th place 5th place BLEU Score sliding window linear flash standard sparse Train Time standard flash sliding window linear sparse GPU Memory sparse flash standard sliding window linear Inference Latency standard sliding window flash sparse linear Table 3.7: Ranking of attention mechanisms for translation models 3.4.7 Discussion •Sliding-window attention clearly excels in translation quality (63.89 BLEU) while using moderate resources its locality bias plus a few global tokens captures both short and longrange dependencies effectively. •Linear attention offers surprisingly strong BLEU (57.74) but suffers from extremely high latency (222 ms), making it impractical for real time use despite its sub-quadratic complexity. •Flash attention provides a modest BLEU gain over standard (37.99 vs. 35.36) but at the cost of additional implementation complexity and slightly longer training than standard. •Standard attention remains a solid baseline: fast to train and infer, but yields lower translation quality. •Sparse attention incurred the largest training time and highest latency for the lowest BLEU, reflecting the overhead of dynamic sparsity masks outweighing its potential memory savings. 3.5 Conclusion At a glance, our systematic experiments reveal that no single attention mechanism universally dominates across all tasks. Instead, each variant offers a unique balance of predictive quality,compute efficiency, and memory footprint: •Next-character prediction (GPT): Flash Attention delivers the lowest perplexity (≈4.2) thanks to its memory-efficient kernel, while Sliding-Window Attention trains fastest (≈6 min) with minimal GPU usage and the lowest inference latency (≈9 ms). •Masked-character prediction (BERT): Sparse Attention achieves the highest accuracy (≈48%), dynamically focusing on key tokens at the cost of long runtimes (≈23 min) and high latency (≈72 ms). Sliding-Window Attention again strikes the best balance, with solid accuracy (≈43%), moderate training time (≈10 min), and low memory use. •English→French translation (Transformer): Sliding-Window Attention leads in BLEU score (≈63.9) by combining local windows with a few global tokens, while Linear Attention closely follows in quality (≈57.7) but suffers extreme latency (≈223 ms). Standard and Flash attentions offer respectable BLEU (≈35–38) with the fastest runtimes, whereas Sparse incurs overheads that outweigh its modest gains (≈32.1 BLEU). Throughout, Standard Attention remains a robust baseline simple, fast, and memorylean yet it often cedes ground to specialized methods on quality. Conversely, Linear and Sparse 66
variants demonstrate that sub-quadratic complexity or content-based sparsity can boost task performance, but only when their added computational costs are acceptable. These findings underscore the importance of matching attention design to task requirements. For scenarios demanding maximal accuracy and where resources permit, Flash (for autoregression) or Sparse (for bidirectional contexts) are compelling choices. When throughput, latency, or limited memory are paramount, Sliding-Window or Standard attention offer the best efficiency–quality trade-off. 67
Chapter 4 Enhancing Linear Attention with Structural Biases: Design and Evaluation of Hybrid Mechanisms While the prior chapters provided a thorough analysis of existing attention mechanisms and evaluated their performance in GPT models, this chapter presents the central contribution of this research: two novel hybrid attention mechanisms that combine the efficiency of linear attention with the structural benefits of sparse and sliding window patterns. These mechanisms were designed to overcome the limitations observed in pure linear attention, particularly its underperformance on tasks that require stronger contextual modeling and long-range dependency handling. Our comparative experiments showed that although linear attention is efficient, it often lacks the expressive power necessary for certain language modeling tasks. Unlike prior work that primarily aims to speed up attention or reduce memory usage, our approach focuses on restoring the performance especially in terms of loss and perplexity typically sacrificed by linear approximations. Through evaluations on next-character prediction tasks, we aim to reduce the performance gap between linear and standard attention. This goal of recovering performance while maintaining efficiency defines the core innovation of our work. 4.1 Motivation Although linear attention is appealing for its O(n) time and memory complexity, enabling efficient handling of long sequences, our experiments on the next-character prediction task (Tiny Shakespeare dataset, context length 128) revealed a notable expressivity gap when compared to more structured mechanisms like sparse or sliding window attention. This gap is reflected in higher validation loss and reduced accuracy, indicating that linear attention struggles to model rich contextual dependencies. These observations motivated the development of hybrid mechanisms that preserve linear attention’s efficiency while recovering much of the performance benefits of structured attention. Bridging this trade-off became a key driver of our research. 68
Figure 4.1: Addressing the problem with linear attention •Early plateau in loss/perplexity As shown in the validation curves, Linear Attention (cyan) quickly stalls around a validation loss of ≈2.35 well above the ≈1.85–1.90 achieved by Standard, Sliding-Window, and Sparse attentions and maintains a perplexity of ≈10.4 versus ≈6.2–6.5 for the others. •Trade-off versus structure Although Flash Attention (green) clearly outperforms all methods (final val PPL ≈5.35) thanks to its numerically stable kernel, it incurs moderate runtime and latency costs. Sliding-Window and Sparse attentions strike different balances of locality bias and complexity but still outperform plain linear in quality. These results underscore that efficiency alone is not enough without some form of structural bias, linear attention is too ”bland” to model the rich, long-range patterns present even in a simple autoregressive text task. Hypothesis: Embedding structural priors either a sparse connectivity pattern or a fixed local window into the kernelized linear formula could bridge the expressivity gap while preserving subquadratic scaling. In the next sections, we thus introduce two new hybrid mechanisms LinearSparseAttention and LinearSlidingWindowAttention designed to inject exactly these biases into the linear framework, and we show that they recover much of the performance lost by pure linear attention without reverting to quadratic complexity. 4.2 Proposed Hybrid Mechanisms To address the expressivity gap of pure linear attention while retaining its O(N) complexity, we propose two hybrid mechanisms that inject structural biases into the kernel-based framework. Both approaches build on the ELU+1 feature map formulation but differ in how they constrain the attention scope: •LinearSparseAttention adds a predefined sparse connectivity pattern that balances global, local, and random token interactions. •LinearSlidingWindowAttention restricts each token’s receptive field to a fixed-size local window, ensuring strong locality inductive bias. By combining linear attention’s efficiency with structured attention patterns, these hybrids aim to: 1. Enhance representational power by reintroducing selective token dependencies missing in pure linear formulations. 69
2. Preserve subquadratic scaling, ensuring that both time and memory complexity remain linear in sequence length. 3. Bridge the performance gap in loss and perplexity metrics observed in prior experiments (see Section 4.3.5). 4.2.1 LinearSparseAttention LinearSparseAttention integrates the ELU+1 kernel trick with a BigBird-inspired sparse pattern comprising: •Global tokens: A small set of positions attend to and are attended by every other token, enabling long-range signaling. •Local window: Each non-global token connects to its immediate neighbors within a fixed window, preserving locality. •Random links: Sparse random edges ensure additional paths between distant tokens, promoting mixing without dense computation. Theoretical rationale: By overlaying these sparse structures onto the linear attention kernel, we reintroduce targeted cross-token dependencies that pure linear attention omits. The sparse pattern compensates for ELU+1’s tendency to distribute attention uniformly, thereby reducing bias and lowering both training and validation perplexity while maintaining O(N) operations in most layers. 4.2.2 LinearSlidingWindowAttention LinearSlidingWindowAttention fuses the ELU+1 kernel method with a fixed sliding window constraint: •Each token attends only to itself and a set number of preceding tokens (window size W), enforcing causal locality. •The kernelized attention computation remains unchanged, but is applied over this local context rather than the full sequence. Theoretical rationale: Language exhibits strong local correlations, especially in character-level prediction tasks. By focusing linear attention on a localized context, we amplify useful dependencies and improve gradient signal for nearby tokens. This localized bias yields lower loss and perplexity early in training and stabilizes convergence yet still leverages the ELU+1 kernel trick to avoid quadratic scaling. Together, these two mechanisms represent complementary ways to enrich linear attention with inductive biases: one through structured sparsity and the other through locality constraints. In the following section (5.4), we detail their implementation and training configurations before presenting comparative results. 4.3 Implementation Details Both hybrids were implemented in PyTorch by extending a standard Transformer block: we simply replace softmax with the ELU+1 kernel trick and inject either a sparse or sliding-window mask (and a lightweight fusion step) into the attention computation. All other components Q/K/V projections, output projection, normalizations, and dropout remain unchanged. Hyperparameters for window size, global/random links, and dropout are managed via a shared configuration object, allowing seamless swapping between attention variants. 70
4.4 Experimental Results and Analysis 4.4.1 Training and Validation Loss Figure 4.2: Training and validation loss curves Over the first 500 steps, all attention variants on the Tiny Shakespeare task exhibit a steep decline in training loss from approximately 4.1 to 2.1, as the models capture basic character transitions. In the subsequent 3 700 steps, losses diverge: Standard Attention attains the lowest convergence (≈1.42 train, 1.70 validation), demonstrating its expressive power. LinearSlidingWindowAttention closely follows, reaching ≈1.43 train and ≈1.70 validation effectively matching the baseline. LinearSparseAttention settles at higher values (≈1.55 train, 1.83 validation), while pure LinearAttention plateaus around 1.95 train and 2.07 validation, confirming that structural bias is essential to recover expressivity. 4.4.2 Training and Validation Perplexity Figure 4.3: Training and validation perplexity curves Perplexity trends mirror the loss curves: all models reduce perplexity from the mid-70s to single digits by step 500. By the final iteration, Standard Attention achieves a validation perplexity of ≈5.50, LinearSlidingWindowAttention ≈5.46, and LinearSparseAttention ≈6.19. Pure LinearAttention remains higher at ≈7.85. These results indicate that both hybrid mechanisms recover the majority of performance lost by the linear kernel approximation, with sliding-window slightly outperforming sparse on this task. 71
4.4.3 Training Time Figure 4.4: Training time comparison Measured wall-clock times for 4 200 iterations reveal that Standard Attention completes training in 187 s, and LinearAttention in 205 s. The hybrid variants require 376 s (slidingwindow) and 409 s (sparse), remaining under seven minutes. Thus, the hybrids incur a moderate computational overhead about 80–100 4.4.4 Inference Latency Figure 4.5: Inference latency comparison Average per-token inference times are 0.064 ms for Standard Attention, 0.108 ms for pure LinearAttention, 0.184 ms for LinearSlidingWindowAttention, and 0.216 ms for LinearSparseAttention. Although the hybrid methods double to triple the cost of pure linear inference, they maintain sub 0.25 ms latency, making them viable for real-time or streaming applications. 72