Long Context and Efficient Attention

See why long inputs are expensive and how FlashAttention, sliding-window and sparse attention, GQA, ring attention and linear-time architectures make long context practical, with online softmax built from scratch.

30 minAdvancedCode Examples

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.

  1. Beginner: Why Long Inputs Are Hard

In the attention lesson you saw that every token compares itself with every earlier token. For nn tokens that is about n2n^2 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 lengthComparisons per head, per layer (n × n)Growth
4,000 tokens16,000,0001×
32,000 tokens1,024,000,00064×
128,000 tokens16,384,000,0001,024×

Two separate problems: Compute (too many comparisons) and memory (a huge score table and a huge KV cache). Different tricks attack different problems.

  1. Beginner: The Main Families of Tricks

IdeaWhat it changesExact or approximate?
FlashAttentionHow the math is scheduled on the GPU, so the big table is never storedExact (same answer, faster)
Sliding-window attentionEach token looks only at the last few thousand tokensApproximate (less context)
Sparse / local + globalOnly some token pairs are compared, plus a few special tokens that see everythingApproximate
GQA / MQAShare keys and values to shrink the KV cacheSlightly approximate by design
Ring attentionSplit a very long sequence across many GPUs that pass keys and values around a ringExact
Linear attention / state-space modelsReplace attention with a fixed-size running memoryDifferent architecture

Rule of thumb: Exact methods keep the answer identical and only save time or memory. Approximate methods trade some context for speed.

  1. 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 n×nn \times n 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.

1
Load a tile of K and V: Small enough for fast memory.
2
Compute scores for that tile: Only a small block of the table exists.
3
Update the running max and sum: Rescale the earlier partial results.
4
Add the tile's contribution to the output: Then discard the tile and move to the next.

Result: Exactly the same output as standard attention, but memory for the score table drops from n2n^2 to a small tile, and speed improves a lot because far less data is moved.

  1. Medium: Sliding Windows and Sparse Patterns

Sliding-window attention limits each token to the previous ww tokens (for example 4,096). The cost becomes about n×wn \times w instead of n2n^2, 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.

MethodCost for n tokensKeeps
Full attentionabout n²Everything
Sliding window (w)about n × wThe most recent w tokens, plus indirect memory through layers
Local + globalabout n × w + fewRecent 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.

  1. 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.

Architectures beyond attention
State-space models and other linear-time designs keep a fixed-size memory that is updated token by token, so cost grows only linearly with length. They are efficient but can be weaker at exact recall, so some recent models mix them with a few attention layers.

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.

  1. Visual Explanation: Seeing Less, Moving Less

The figure first compares three attention patterns, then contrasts standard attention with the tiled FlashAttention approach.

Part 1 · Which Tokens Can I See?Three attention patterns
Full causalCost: n²
Token 10 looks at tokens 1 to 10
↓
Every earlier token is compared
↓
Complete memory, highest cost
Sliding windowCost: n × w
Token 10 looks at the last w tokens only
↓
Older tokens are skipped
↓
Linear cost, limited direct view
Local + globalCost: n × w + few
Recent tokens plus a few global tokens
↓
Global tokens see everything
↓
Cheap and keeps key anchors
Part 2 · FlashAttention in TilesSame answer, far less memory traffic
Standard attentionSlow memory heavy
Build the full n × n score table
↓
Write it to main GPU memory
↓
Read it back for softmax
↓
Big memory use, lots of data movement
FlashAttentionTiled, exact
Load one small tile of K and V
↓
Update running max and sum (online softmax)
↓
Add to the output, then next tile
↓
Identical output, small memory
Click to see the online-softmax ideaCompare ▼
Keep a running maximum m and running sum l. When a new tile has a larger maximum, multiply the old sum and old output by exp(old m - new m) to rescale them. After the last tile, divide the output by the sum. The code below proves it matches normal attention.

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.

  1. 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.

efficient_attention.pyPython 3.10+ · NumPy only
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")
EXPECTED OUTPUT (your numbers may differ slightly)
n = 4,096 | full: 8,390,656 | window 4096: 8,390,656 | saving: 1.0 x
n = 32,768 | full: 536,887,296 | window 4096: 125,831,168 | saving: 4.3 x
n = 131,072 | full: 8,590,000,128 | window 4096: 528,484,352 | saving: 16.3 x
Tiled (FlashAttention-style) result equals standard attention: True
Largest score table held at once: standard 4096 numbers | tiled 1024 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

Question 1: What is special about FlashAttention?
Question 2: What is the main weakness of a pure sliding window?

Key Points

✓Full attention costs about n² comparisons, and the KV cache grows with n too.
✓FlashAttention is exact: it tiles the work and uses an online softmax to avoid storing the full score table.
✓Sliding-window attention costs about n × w and trades some direct context for speed.
✓Sparse patterns add a few global tokens so key information stays visible.
✓Ring attention splits a sequence over many GPUs and passes keys and values around a ring.
✓Use the shortest context that solves the task, and retrieval when only parts of a document matter.

The Big Picture

Efficient Attention in One Line

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.