Attention Score Matrix

The attention score matrix has dimensions N × N, where N is the sequence length. Computing and storing this matrix requires O(N²) memory and time complexity. For a 32k token context window, this results in over 1 billion pairwise scores. This quadratic scaling is the primary computational bottleneck that techniques like FlashAttention, sparse attention, and KV caching aim to mitigate.

Each entry S_{ij} represents the dot product between the Query vector of token i and the Key vector of token j. Because Queries and Keys use separate learned projection matrices (W_Q and W_K), the matrix is not necessarily symmetric. Token A attending to Token B can yield a different raw score than Token B attending to Token A, reflecting directional semantic relationships.

In decoder-only architectures, a lower triangular mask is applied to the score matrix before softmax. This sets all entries where j > i to negative infinity, preventing token i from attending to future tokens. The resulting matrix is upper-triangular with -∞ values, enforcing the autoregressive property essential for text generation in models like GPT.

Raw dot-product scores grow in magnitude as the dimensionality d_k of Query/Key vectors increases. Large score values push the softmax into regions of extremely small gradients. Dividing all scores by √d_k keeps the variance of the dot products stable at approximately 1, ensuring healthy gradient flow during backpropagation. Without this scaling, training deep Transformers becomes unstable.

Not all N² entries are equally important. Sliding window attention computes only a banded diagonal of the matrix, where each token attends to a fixed neighborhood of ±W tokens. Dilated attention uses strided patterns. These sparsity masks transform the O(N²) complexity to O(N·W), enabling processing of sequences with hundreds of thousands of tokens without quadratic memory growth.

In multi-head attention, each head maintains its own independent score matrix. Empirical analysis reveals that different heads specialize in distinct linguistic patterns: some heads focus on syntactic dependencies, others on coreference resolution, and some become no-op heads that contribute minimally. Head pruning techniques exploit this redundancy by removing heads whose score matrices show consistently uniform or low-variance patterns.

The exact mathematical operation that generates the raw attention score matrix. It computes the dot product of the Query matrix with the transposed Key matrix, then scales the result by 1/√dₖ (where dₖ is the key dimension) to prevent the softmax from entering regions with extremely small gradients. The formula is: Attention(Q,K,V) = softmax(QKᵀ/√dₖ)V. Without this scaling factor, high-dimensional dot products grow large in magnitude, pushing the softmax function into saturation and halting learning.

A constraint applied to the attention score matrix in decoder-only and autoregressive models. Before the softmax step, a mask sets all scores corresponding to future tokens to -∞, ensuring that after softmax, those positions receive a weight of zero. This enforces the autoregressive property: a token at position i can only attend to positions ≤ i. The mask is typically an upper-triangular matrix of negative infinity values, preserving the causal ordering of sequence generation.

The fundamental computational limitation of the attention score matrix. Since the matrix dimensions are N × N (where N is sequence length), both memory and compute scale as O(N²). For a 32k-token context, this yields over one billion pairwise scores to compute and store. This bottleneck drives research into sparse attention, linear attention, and FlashAttention to make long-context processing tractable without exhausting GPU high-bandwidth memory.

A hyperparameter that modulates the sharpness of the attention distribution. Applied as a divisor to the logits before softmax: softmax(scores / τ). A low temperature (τ < 1) sharpens the distribution, making the model focus heavily on the single most relevant token. A high temperature (τ > 1) flattens the distribution, giving more weight to secondary tokens. This is distinct from the scaling factor √dₖ, which is fixed by dimensionality; temperature is a tunable control for exploration vs. exploitation.

An IO-aware exact attention algorithm that computes the attention score matrix in tiled blocks without ever materializing the full N × N matrix in GPU high-bandwidth memory (HBM). By fusing the softmax reduction across tiles in SRAM, it achieves significant speedups and memory savings while remaining mathematically identical to standard attention. This makes it possible to train models with long context windows without resorting to sparse approximations.

A family of techniques that reduce the O(N²) cost by computing only a subset of the attention score matrix. Common patterns include:

• Sliding Window: Each token attends only to a fixed window of ±W neighboring tokens
• Dilated Sliding Window: Gaps are introduced in the window to increase receptive field
• Global Attention: A few pre-selected tokens attend to the entire sequence
• Block-Sparse: The matrix is divided into blocks, with only certain blocks computed These patterns reduce complexity to O(N·W) or O(N·k) where k ≪ N.