Flash Attention

Flash Attention fundamentally restructures the attention computation to be IO-aware, meaning it accounts for the speed disparity between GPU High Bandwidth Memory (HBM) and on-chip Static Random-Access Memory (SRAM). Standard attention materializes the full N×N attention matrix in slow HBM, creating a quadratic memory bottleneck. Flash Attention instead tiles the computation into blocks that fit entirely in fast SRAM, performing the softmax reduction incrementally without ever writing the full intermediate matrix to HBM. This minimizes data movement, the primary bottleneck in transformer inference and training.

The algorithm employs a tiling strategy that decomposes the query, key, and value matrices into blocks. For each query block, it iterates over key-value blocks, accumulating softmax statistics in SRAM. Crucially, Flash Attention uses recomputation in the backward pass: rather than storing the massive attention matrix from the forward pass, it recalculates it on-the-fly using the stored softmax normalization statistics. This trades a small amount of extra computation for a dramatic reduction in memory footprint, enabling training with longer sequences on existing hardware.

A core mathematical innovation is the online softmax algorithm, also known as tiled softmax. Standard softmax requires two passes over the data: one to find the maximum value for numerical stability and another to compute the exponential sum. Flash Attention fuses these into a single pass per tile by maintaining running statistics. It uses the standard log-sum-exp trick to ensure numerical stability across blocks, rescaling partial sums as new maxima are encountered. This guarantees the output is bitwise identical to the standard attention computation, making it an exact algorithm, not an approximation.

Flash Attention is implemented as a single, highly optimized CUDA kernel that fuses multiple operations into one GPU program. Instead of launching separate kernels for matrix multiplication, masking, softmax, and dropout, the entire attention operation is compiled into a monolithic kernel. This eliminates the overhead of launching multiple kernels and, more importantly, avoids the redundant round-trips to HBM that occur between kernel boundaries. The fused kernel carefully manages shared memory allocation and thread block scheduling to maximize occupancy and hide memory latency.

By reducing the memory footprint of attention from quadratic to linear in sequence length, Flash Attention directly enables training on significantly longer contexts. Models like GPT-4 and Llama 3 rely on this algorithm to scale to context windows of 128k tokens and beyond. Without it, the attention matrix for a 128k sequence would require over 64 GB of memory per attention head, making training infeasible on current hardware. Flash Attention makes long-context training practical on standard GPU clusters, unlocking applications in long-document summarization, codebase analysis, and extended multi-turn conversation.

A memory management technique that partitions the KV cache into non-contiguous, fixed-size blocks, analogous to virtual memory paging in operating systems. This eliminates fragmentation and enables near-optimal memory utilization during serving.

• Handles variable-length sequences without pre-allocation
• Enables memory sharing across sequences for techniques like parallel sampling
• Core innovation behind the vLLM inference engine
• Works synergistically with Flash Attention's tiled computation

A memory buffer that stores the computed Key and Value tensors from all previous tokens during autoregressive generation. Without it, each new token would require recomputing attention over the entire sequence.

• Memory grows linearly with batch size × sequence length × hidden dimensions
• Flash Attention reduces the HBM reads/writes of KV cache operations
• Multi-Query Attention (MQA) and Grouped-Query Attention (GQA) shrink KV cache size by sharing key-value heads
• Primary bottleneck for long-context serving

An attention mechanism that divides query heads into groups, with each group sharing a single set of Key and Value heads. This interpolates between the quality of Multi-Head Attention (MHA) and the speed of Multi-Query Attention (MQA).

• Used in Llama 2 70B, Llama 3, and Mistral models
• Reduces KV cache size by a factor equal to the number of query heads per group
• Pairs naturally with Flash Attention's memory-efficient tiling
• Maintains near-MHA quality while approaching MQA throughput

A family of techniques that extend the effective context window of models using Rotary Position Embeddings (RoPE) beyond their pre-trained length without full retraining.

• Linear scaling: Divides position indices by a scaling factor
• NTK-aware scaling: Non-linear interpolation preserving high-frequency information
• YaRN: Combines NTK scaling with temperature adjustment for extreme length extension
• Enables Flash Attention to operate on sequences far exceeding original training length

An optimization that stores and reuses the computed KV cache for a shared prompt prefix across multiple generation requests. When multiple queries share a common system prompt or few-shot examples, the attention computation for that prefix is performed only once.

• Dramatically reduces Time To First Token (TTFT) for cached prefixes
• Complements Flash Attention by avoiding redundant IO-aware computation
• Critical for chatbot serving with long system prompts
• Implemented in serving engines like vLLM and SGLang