Quadratic Complexity Bottleneck

The core computational cost arises from the attention score matrix calculation. For a sequence of length n, every token must compute a compatibility score with every other token, resulting in n × n operations.

• Matrix Multiplication: Computing QK^T requires O(n² · d) operations where d is the head dimension
• Real-world impact: Doubling sequence length quadruples computation time
• Example: Processing a 32k token document requires 1,024× more attention operations than a 1k token document
• GPU implications: The attention matrix of size n×n must fit in high-bandwidth memory, creating a hard ceiling on sequence length

Storing the full attention score matrix and intermediate activations during training creates a memory bottleneck that scales quadratically with sequence length.

• Attention matrix storage: Requires storing n² floating-point values per attention head per layer
• Training memory: Backpropagation requires storing the full attention matrix for gradient computation
• Example: A single attention head on a 64k sequence requires ~16GB just for the attention matrix in FP32
• Multi-head amplification: Memory scales linearly with the number of attention heads, multiplying the bottleneck

The quadratic bottleneck directly constrains the maximum context window size that can be practically deployed in production systems.

• Historical constraints: Early Transformer models were limited to 512-1024 tokens due to quadratic scaling
• Hardware ceiling: Even with modern GPUs, the quadratic curve eventually exceeds available VRAM
• Trade-off: Increasing context window requires either more hardware or algorithmic approximations
• Production reality: Models with 128k+ context windows rely on sparse or linear attention variants, not standard self-attention

Sparse attention patterns reduce complexity by computing only a subset of the full attention matrix, trading complete context for computational feasibility.

• Sliding window attention: Each token attends only to w neighboring tokens, achieving O(n · w) complexity
• Dilated sliding windows: Expands receptive field without quadratic cost by using gaps between attended tokens
• Global tokens: Designating a few tokens to attend to the entire sequence creates information highways
• Block-sparse patterns: Dividing the sequence into blocks and computing attention within and between selected blocks

Linear attention mechanisms reformulate the attention operation to achieve O(n) complexity by changing the order of matrix operations.

• Kernel trick: Approximating softmax with a kernel function allows computing K^T V first, then multiplying by Q
• Performer architecture: Uses random feature maps to approximate softmax attention in linear time
• Linear Transformer: Removes softmax entirely, using simple feature maps for O(n) complexity
• Trade-off: Linear approximations may lose the sharp selectivity of softmax attention on long-range dependencies

FlashAttention addresses the memory bottleneck rather than the computational complexity, achieving significant speedups while computing exact attention.

• Tiling strategy: Breaks the attention matrix into tiles that fit in GPU SRAM, avoiding HBM reads/writes
• Online softmax: Computes softmax incrementally across tiles without storing the full attention matrix
• Memory reduction: Reduces memory footprint from O(n²) to O(n) by recomputing attention during backward pass
• Practical impact: Enables 2-4× faster training and supports longer sequences without approximation

A class of techniques that reduces the O(n²) complexity by computing only a subset of the full attention score matrix. Instead of allowing every token to attend to every other token, sparse attention enforces predefined or learned patterns.

• Local/Sliding Window: Tokens attend only to a fixed neighborhood.
• Dilated Sliding Window: Increases receptive field without increasing compute.
• Global + Local: Combines task-specific global tokens with local attention.
• Learnable Patterns: The model learns which token pairs to attend to.

This reduces memory and time complexity to O(n log n) or O(n) , enabling processing of long documents.

An IO-aware exact attention algorithm that avoids materializing the full N x N attention matrix in high-bandwidth memory (HBM). It operates by tiling the computation and fusing operations in fast on-chip SRAM.

• Tiling: Breaks the Q, K, V matrices into blocks that fit in SRAM.
• Recomputation: Recomputes attention statistics in the backward pass rather than storing the full matrix.
• Kernel Fusion: Combines multiple operations into a single CUDA kernel.

FlashAttention achieves 2-4x speedups over standard attention with no approximation, making it a default in modern training stacks.

A variant of multi-head attention where all attention heads share a single set of Key and Value projection weights, while retaining separate Query projections.

• KV Cache Reduction: Reduces the size of the KV cache by a factor equal to the number of heads.
• Memory Bandwidth: Significantly lowers memory reads during autoregressive decoding.
• Trade-off: Slight degradation in model quality compared to standard multi-head attention.

MQA directly addresses the memory bottleneck of the KV cache, which grows linearly with sequence length and batch size during inference.

An interpolation between multi-head attention and multi-query attention. Query heads are partitioned into groups, with each group sharing a single set of Key and Value heads.

• Balanced Trade-off: Achieves inference speed close to MQA while preserving quality close to standard multi-head attention.
• Configurable Groups: The number of groups controls the speed-quality trade-off.
• Adoption: Used in models like Llama 2 and Llama 3.

GQA provides a practical middle ground for production deployments where both latency and accuracy are critical.

A sparse attention pattern where each token attends only to a fixed-size window of neighboring tokens, typically extending W tokens to the left and right.

• Linear Complexity: Complexity scales as O(n × W) , where W is the window size and is constant.
• Stacked Layers: Receptive field grows with layer depth, allowing distant tokens to interact indirectly.
• Implementation: Used in architectures like Longformer and Mistral.

This approach is particularly effective for tasks with strong local structure, such as text processing where nearby words carry the most contextual relevance.

An inference optimization that stores the previously computed Key and Value vectors for all generated tokens to prevent redundant re-computation during autoregressive decoding.

• Mechanism: During each generation step, only the new token's Q, K, V are computed; past K and V are read from cache.
• Memory Growth: Cache size grows linearly with sequence length and batch size.
• Bottleneck: The KV cache becomes the primary memory constraint for long-context inference.

Efficient KV cache management is the driving motivation behind MQA, GQA, and quantization techniques for serving large language models.