Why does attention cost grow quickly as the input gets longer?
Every token is compared with every other token, so the number of comparisons grows with the square of the sequence length. Doubling the input roughly quadruples the attention work and memory, which makes very long contexts expensive.
Explain it simply
At a college fest with 50 people, if everyone shakes hands with everyone, that is 1,225 handshakes. With 100 people it is 4,950. Double the crowd and the handshakes go up about four times.
Attention is the handshake. For a sequence of n tokens it builds an n by n table of scores. A prompt of 1,000 tokens needs about a million entries per head per layer, and 4,000 tokens needs about sixteen million.
This is why long contexts raise latency and cost, and why researchers work on sparse attention, sliding windows and memory-efficient kernels. Other parts of the model grow only linearly with length, so attention dominates mainly at long lengths.
Example
n = 1,000 tokens -> 1,000 x 1,000 = 1,000,000 scores
n = 2,000 tokens -> 2,000 x 2,000 = 4,000,000 scores (4x)
n = 4,000 tokens -> 4,000 x 4,000 = 16,000,000 scores (16x)What to say in the interview
"Standard self-attention is O(n squared) in time and memory with sequence length, since every pair of tokens is scored. That is why long prompts are costly, and why I trim irrelevant context and consider retrieval instead of stuffing everything in."