Efficient Attention

Efficient attention is the set of tricks that keep self-attention affordable as the context grows. Plain attention costs O(n²) — double the sequence, quadruple the work and the memory. The cards show the fixes; here's the shape of the problem and where each fix actually wins.

Where you meet it

Long-context models — 100k-token prompts, whole codebases, books.
Fast inference — every chat reply runs the decode loop token by token.
Anywhere a model lists "FlashAttention", "sliding window", or "GQA" in its config.

What it does

It attacks the same O(n²) bottleneck from different angles — some make the exact computation cheaper to run, others approximate it so the cost grows linearly. The two are not the same trade, and mixing them up is the usual mistake.

FlashAttention gives you the same numbers, only faster; sparse and linear change what the model sees — measure that trade, don't assume it.

How it works

Standard attention builds an n×n score matrix — quadratic in both time and memory. Four families chip away at it:

n = sequence length

Standard      time O(n²)  mem O(n²)   exact
FlashAttention time O(n²) mem O(n)    exact, IO-aware
Sparse/window time O(n·w) mem O(n·w)  approximate (w = window)
Linear        time O(n)   mem O(n)    approximate (low-rank)

FlashAttention doesn't cut the FLOPs — it cuts the memory traffic. It tiles the matrix into fast on-chip SRAM and streams the softmax, never writing the full n×n to slow HBM. Exact result, linear memory.
Sparse / sliding-window lets each token attend only to its neighbours (a window w), plus a few global tokens. Cost scales with n·w, not n².
Linear attention approximates the full matrix with a low-rank factorisation, dropping both time and memory to O(n).
KV-cache is orthogonal: during decoding it stores the keys/values of past tokens so each new token isn't recomputed from scratch. It buys speed by spending memory.

Watch out

Exact vs approximate. FlashAttention changes nothing about the output — same numbers, faster. Sparse and linear methods change what the model can see; that's a quality trade-off you must measure, not assume.
The KV-cache grows with sequence length. On long context it becomes the memory bottleneck — which is exactly why GQA/MQA and cache quantization exist.
It's hardware- and implementation-bound. FlashAttention's win comes from the GPU memory hierarchy; the speedup depends on the kernel, the GPU, and the dtype.
"Linear" isn't automatically better. Linear and sparse attention often lag full attention on quality, which is why most production models still run exact attention via FlashAttention rather than approximating.

Go deeper

Efficient Attention ist die Sammlung von Tricks, die Self-Attention bezahlbar halten, wenn der Kontext wächst. Standard-Attention kostet O(n²) — doppelte Sequenz, vierfacher Aufwand und Speicher. Die Karten zeigen die Fixes; hier kommt die Form des Problems und wo jeder Fix wirklich gewinnt.

Wo es vorkommt

Long-Context-Modelle — 100k-Token-Prompts, ganze Codebasen, Bücher.
Schnelle Inferenz — jede Chat-Antwort läuft Token für Token durch die Decode-Schleife.
Überall, wo ein Modell "FlashAttention", "Sliding Window" oder "GQA" in der Config nennt.

Was es tut

Es greift denselben O(n²)-Engpass aus verschiedenen Richtungen an — manche machen die exakte Rechnung billiger ausführbar, andere approximieren sie, sodass die Kosten linear wachsen. Das ist nicht derselbe Handel, und beides zu verwechseln ist der übliche Fehler.

FlashAttention liefert dieselben Zahlen, nur schneller; Sparse und Linear ändern, was das Modell sieht — diesen Trade-off messen, nicht annehmen.

Wie es funktioniert

Standard-Attention baut eine n×n-Score-Matrix — quadratisch in Zeit und Speicher. Vier Familien knabbern daran:

n = Sequenzlänge

Standard       Zeit O(n²)  Speicher O(n²)   exakt
FlashAttention Zeit O(n²)  Speicher O(n)    exakt, IO-bewusst
Sparse/Fenster Zeit O(n·w) Speicher O(n·w)  approximativ (w = Fenster)
Linear         Zeit O(n)   Speicher O(n)    approximativ (Low-Rank)

FlashAttention kürzt nicht die FLOPs — es kürzt den Speicherverkehr. Es kachelt die Matrix in schnellen On-Chip-SRAM und streamt den Softmax, schreibt nie die volle n×n in den langsamen HBM. Exaktes Ergebnis, linearer Speicher.
Sparse / Sliding-Window lässt jedes Token nur seine Nachbarn beachten (ein Fenster w), plus ein paar globale Tokens. Kosten skalieren mit n·w, nicht n².
Linear Attention approximiert die volle Matrix über eine Low-Rank-Faktorisierung und drückt Zeit und Speicher auf O(n).
KV-Cache ist orthogonal: beim Decoding speichert er die Keys/Values vergangener Tokens, damit jedes neue Token nicht von Grund auf neu berechnet wird. Er kauft Tempo, indem er Speicher ausgibt.

Worauf achten

Exakt vs. approximativ. FlashAttention ändert nichts am Output — gleiche Zahlen, nur schneller. Sparse- und Linear-Methoden ändern, was das Modell sehen kann; das ist ein Qualitäts-Trade-off, den du messen musst, nicht annehmen.
Der KV-Cache wächst mit der Sequenzlänge. Bei langem Kontext wird er zum Speicher-Engpass — genau deshalb gibt es GQA/MQA und Cache-Quantisierung.
Es ist hardware- und implementierungsabhängig. FlashAttentions Gewinn kommt aus der GPU-Speicherhierarchie; das Speedup hängt am Kernel, an der GPU und am Dtype.
"Linear" ist nicht automatisch besser. Linear- und Sparse-Attention liegen bei der Qualität oft hinter voller Attention — weshalb die meisten Produktionsmodelle weiter exakt via FlashAttention rechnen statt zu approximieren.