The Core Idea: Attention cost and KV-cache memory both explode with length. FlashAttention keeps the answer exact but moves less data, sliding windows and sparse patterns compare fewer pairs, and ring attention spreads one huge sequence across many GPUs.
- Beginner: Why Long Inputs Are Hard
In the attention lesson you saw that every token compares itself with every earlier token. For tokens that is about comparisons. This cost, together with the memory of the KV cache, is what makes very long inputs such as books, codebases or hours of chat difficult.
| Text length | Comparisons per head, per layer (n × n) | Growth |
|---|---|---|
| 4,000 tokens | 16,000,000 | 1× |
| 32,000 tokens | 1,024,000,000 | 64× |
| 128,000 tokens | 16,384,000,000 | 1,024× |
Two separate problems: Compute (too many comparisons) and memory (a huge score table and a huge KV cache). Different tricks attack different problems.
- Beginner: The Main Families of Tricks
| Idea | What it changes | Exact or approximate? |
|---|---|---|
| FlashAttention | How the math is scheduled on the GPU, so the big table is never stored | Exact (same answer, faster) |
| Sliding-window attention | Each token looks only at the last few thousand tokens | Approximate (less context) |
| Sparse / local + global | Only some token pairs are compared, plus a few special tokens that see everything | Approximate |
| GQA / MQA | Share keys and values to shrink the KV cache | Slightly approximate by design |
| Ring attention | Split a very long sequence across many GPUs that pass keys and values around a ring | Exact |
| Linear attention / state-space models | Replace attention with a fixed-size running memory | Different architecture |
Rule of thumb: Exact methods keep the answer identical and only save time or memory. Approximate methods trade some context for speed.
- Medium: FlashAttention, the Same Answer With Less Memory
A GPU has a small, very fast on-chip memory and a large, slower main memory. Standard attention writes the whole score table to the slow memory and reads it back. Most of the time is spent moving data, not calculating.
FlashAttention processes the keys and values in small tiles that fit in the fast memory and never writes the full table. The difficulty is the softmax, which seems to need all scores at once. The trick is the online softmax: keep a running maximum and a running sum, and rescale what was accumulated whenever a new tile arrives.
Result: Exactly the same output as standard attention, but memory for the score table drops from to a small tile, and speed improves a lot because far less data is moved.
- Medium: Sliding Windows and Sparse Patterns
Sliding-window attention limits each token to the previous tokens (for example 4,096). The cost becomes about instead of , which is linear in length. Information can still travel far, because each layer passes information a window further, so stacked layers see much beyond one window.
Sparse patterns add a few global tokens (like the start of the text or special markers) that every token can see, so important information is never fully cut off.
| Method | Cost for n tokens | Keeps |
|---|---|---|
| Full attention | about n² | Everything |
| Sliding window (w) | about n × w | The most recent w tokens, plus indirect memory through layers |
| Local + global | about n × w + few | Recent tokens and a few special tokens |
Trade-off: A pure window can forget a detail from early in the document. Models that need exact recall of far-away facts often keep some full-attention layers.
- Advanced: Ring Attention, Position Scaling and Beyond
When one GPU cannot even hold the KV cache of a very long input, the sequence itself is split. Ring attention gives each GPU a piece of the sequence. The GPUs pass blocks of keys and values around a ring while each computes its share, so the result is exact and memory per GPU stays small.
To make a model handle lengths beyond its training length, it also needs its positions rescaled (see the RoPE lesson) and usually some extra training on long documents.
Practical advice: Choose the shortest context that solves your task. Use retrieval (RAG) to bring in only relevant pieces, and use long-context models when you really need the whole document at once.
- Visual Explanation: Seeing Less, Moving Less
The figure first compares three attention patterns, then contrasts standard attention with the tiled FlashAttention approach.
Click to see the online-softmax ideaCompare ▼
In Part 1, the cost line under each title shows how work grows with length. Part 2 shows that FlashAttention changes how the data moves, not the answer. Open the bar for the online-softmax rule.
- Python Implementation: Window Savings and Online Softmax
This script counts how many token pairs full attention and a 4,096-token sliding window need at three lengths, then implements a tiled, FlashAttention-style attention with online softmax and checks that it matches standard attention exactly.
import numpy as np # 1. Sliding-window attention: each token looks only at the last `window` tokensdef pairs_full(n): return n * (n + 1) // 2 # causal: every token sees all earlier tokens def pairs_window(n, window): return sum(min(i + 1, window) for i in range(n)) for n in [4096, 32768, 131072]: full, win = pairs_full(n), pairs_window(n, 4096) print("n =", format(n, ","), "| full:", format(full, ","), "| window 4096:", format(win, ","), "| saving:", round(full / win, 1), "x") # 2. Online softmax: the trick inside FlashAttention (process scores in small tiles)rng = np.random.default_rng(0)n, d, tile = 64, 16, 16Q, K, V = rng.normal(size=(3, n, d)) def standard_attention(Q, K, V): S = Q @ K.T / np.sqrt(d) P = np.exp(S - S.max(axis=1, keepdims=True)) return (P / P.sum(axis=1, keepdims=True)) @ V def tiled_attention(Q, K, V): m = np.full(n, -np.inf) # running max of scores l = np.zeros(n) # running sum of exponentials out = np.zeros((n, d)) for start in range(0, n, tile): # one tile of keys and values at a time S = Q @ K[start:start + tile].T / np.sqrt(d) m_new = np.maximum(m, S.max(axis=1)) fix = np.exp(m - m_new) # rescale what we accumulated before P = np.exp(S - m_new[:, None]) l = l * fix + P.sum(axis=1) out = out * fix[:, None] + P @ V[start:start + tile] m = m_new return out / l[:, None] same = np.allclose(standard_attention(Q, K, V), tiled_attention(Q, K, V))print("Tiled (FlashAttention-style) result equals standard attention:", same)print("Largest score table held at once: standard", n * n, "numbers | tiled", n * tile, "numbers")At 4,096 tokens the window changes nothing (the whole text already fits). At 131,072 tokens it needs about 16 times fewer pairs. The tiled version matches standard attention (True) while holding a score block four times smaller in this small example.
Interactive Knowledge Check
Key Points
The Big Picture
Exact tricks move less data; approximate tricks compare fewer pairs; distributed tricks share the load
These methods are why modern models can accept book-length inputs at a reasonable price, and knowing them helps you pick a model for long-document work.
Up Next: Another way to make big models cheap is to use only part of them for each token. In Mixture of Experts you will see how a router sends each token to a few specialist sub-networks.