Why Longer Context Costs More: The O(n²) Bill
The attention mechanism makes every token look at every token: drag context length and watch compute and the bill climb with the square—why long chats get slow and expensive
THE QUESTION THIS PAGE ANSWERS
ANSWER FIRSTWhy Longer Context Costs More: The O(n²) Bill?
The attention mechanism makes every token look at every token: drag context length and watch compute and the bill climb with the square—why long chats get slow and expensive
Make the claim earn its place. Use this page as a decision aid, not a definition to memorize. Connect the idea to one real task, one observable result, and one failure that would change your mind.
Write one question you could answer with evidence after trying this idea.
A conclusion that sounds complete but leaves the key assumption untested.
Earlier lessons covered this: when an LLM generates each new token, it has to “look back” at every previous token, assign attention weights, and decide what comes next. One token scanning all tokens—translate that into last lesson's language: n tokens, each looking at n, for n × n “eye contacts” total. That's an n×n table. Drag the slider and see it drawn.
Each row below means “one token looking at every token”; the dark diagonal is it looking at itself. Watch the cell count on the right: the slider moves at a steady pace, but the number jumps harder and harder—that's the feel of “quadratic growth.”
Same ask—“summarize the key points for me.” One person trims history to 10k tokens first; the other dumps a full 100k-token record in. Tokens differ by only 10×—watch how far the bills diverge. Watch the “attention compute” row: it's not ×10, it's ×100.
Trim camp 10k tokens
Stuff-it-all camp 100k tokens
① Why long chats get slower
The longer you chat, the bigger n, and the more “look-backs” each new token needs. Lag isn't a network issue—it's n² snowballing in the background.
② Why context compression exists
Compaction summarizes old turns into a short chunk, then continues. Trade a bit of detail for a much smaller n—halve n, cut compute by three quarters. Worth it.
③ Why KV Cache saves money
Cache attention results already computed for the prefix so the next turn doesn't redo them (sister part ds-6 covered this). Precisely because the raw compute is the expensive O(n²), the cache discount is so valuable.
The algorithmic cost curve in “Quick refresh · What attention is doing”
“Earlier lessons covered this: when an LLM generates each new token, it has to “ look back ” at every previous token, assign attention weights, and decide what comes next.” is not asking you to memorize steps. It trains you to spot repeated work: as the input grows, how many comparisons, moves, or recursive calls does the program perform?
Find repeated work before declaring something fast
Break “Each row below means “one token looking at every token”;” into three questions: how input size changes, what each round does, and whether the next round can shrink its search space. Big-O describes growth, not an exact time on every machine; constants, memory, and data distribution still matter.
- Attention is O(n²) : every token looks back at every token—you can't escape the n×n table
- Context isn't a free warehouse : every token you stuff gets looked at again and again by every later token
- 10× → 100× costlier : compute grows with the square—the root of long chats getting slow and expensive
Theoretical optimum is not always practical optimum
When AI writes an algorithm, trace a small input by hand and benchmark progressively larger inputs. That turns “Cache attention results already computed for the prefix so the next turn doesn't redo them (sister part ds-6 covered this).” from a slogan into a performance claim you can check.
From “Quick refresh · What attention is doing” to “Interactive 1 · Attention matrix: what n² looks like”
“Quick refresh · What attention is doing” grounds the problem in “Earlier lessons covered this: when an LLM generates each new token, it has to “ look back ” at every previous token, assign attention weights, and decide what comes next. One token scanning all tokens—translate…”. “Interactive 1 · Attention matrix: what n² looks like” then moves it toward “Each row below means “one token looking at every token”; the dark diagonal is it looking at itself. Watch the cell count on the right: the slider moves at a steady pace, but the number jumps harder and harder—t…”. Together, they show that the lesson is not just a conclusion to remember, but a claim with conditions.
Carry the judgment into the next situation
For a real task, find the repeated work first, ask how input size changes, and use a small benchmark to verify the theoretical judgment. Complexity should not become a label detached from the situation.
- “Quick refresh · What attention is doing”: Earlier lessons covered this: when an LLM generates each new token, it has to “ look back ” at every previous token, assign attention weights, and decide what comes next. One token scanning all tokens—translate…
- “Interactive 1 · Attention matrix: what n² looks like”: Each row below means “one token looking at every token”; the dark diagonal is it looking at itself. Watch the cell count on the right: the slider moves at a steady pace, but the number jumps harder and harder—t…
- “The closing point”: Trim context = save money and time : compression, summaries, KV Cache—all wrestling this n²
The final “The closing point” brings the discussion to “Trim context = save money and time : compression, summaries, KV Cache—all wrestling this n²”. The useful thing to carry forward is knowing which judgments must be revisited when input, scale, or risk changes.
What this lesson wants to share
- Attention is O(n²): every token looks back at every token—you can't escape the n×n table
- Context isn't a free warehouse: every token you stuff gets looked at again and again by every later token
- 10× → 100× costlier: compute grows with the square—the root of long chats getting slow and expensive
- Trim context = save money and time: compression, summaries, KV Cache—all wrestling this n²
I turned one judgment from this article into a small experiment I could run today. Knowing what to observe next is more useful than simply remembering the conclusion.
After reading this, I first looked for the conditions behind the idea instead of copying the method into a project. That order made the later trade-offs much clearer.
When this judgment reaches real work, which constraint should be added first? I am curious which step matters most between reading and the first practical attempt.
No discussion on this article yet.