Computational complexity of attention — Hinglish notes

4.1.13 · AI-ML › Transformer Architecture

The fundamental cost breakdown

Memory and operations in standard self-attention

Self-attention mechanism har token ke liye teen matrices compute karta hai: queries (Q), keys (K), aur values (V). Complexity sabhi pairs of tokens ke beech attention scores compute karne se aati hai.

Chaliye scratch se complexity derive karte hain.

Deriving the time complexity

Step 1: Linear projections

Input $X \in R^{n \times d}$ aur weight matrices $W_{Q}, W_{K}, W_{V} \in R^{d \times d_{k}}$ ke liye:

$Q = X W_{Q}$

Yeh ek matrix multiplication hai: $(n \times d) \times (d \times d_{k}) = n \times d_{k}$ output.

Cost: Har output element ke liye $d$ multiplications chahiye, total: $n \cdot d_{k} \cdot d$ operations.

Teeno projections (Q, K, V) ke liye: $3 n d \cdot d_{k}$ operations.

Yeh step kyun? Hum har token ki embedding ko query/key/value space mein transform kar rahe hain. Yeh sequence length mein linear hai—problem yeh nahi hai.

Step 2: Attention scores compute karna $S = Q K^{T}$

$S = Q K^{T} \in R^{n \times n}$

Matrix dimensions: $(n \times d_{k}) \times (d_{k} \times n) = n \times n$

Cost: $n^{2}$ output elements mein se har ek ke liye $d_{k}$ multiplications chahiye.

Total: $n^{2} \cdot d_{k}$ operations.

Yeh step kyun? Yahi woh jagah hai jahan har token khud ko har doosre token se compare karta hai. $n \times n$ output inherently quadratic hai—yahi bottleneck hai.

Step 3: Softmax

$S$ ki har row ke liye (ek query), compute karo:

$A_{ij} = \frac{e x p ( S _{ij} / d _{k} )}{\sum _{j = 1}^{n} e x p ( S _{ij} / d _{k} )}$

Cost: $O (n)$ per row, $n$ rows total: $O (n^{2})$ operations.

Yeh step kyun? Attention weights ko normalize karna. Scores ki sankhya mein abhi bhi quadratic hai.

Step 4: Weighted sum $Output = A V$

$(n \times n) \times (n \times d_{k}) = n \times d_{k}$

Cost: $n^{2} \cdot d_{k}$ operations.

Yeh step kyun? Har output token sabhi value vectors ka weighted combination hota hai.

Step 5: Output projection $Out = Z W_{O}$

Heads ko $d$ -dimensional vector mein concatenate karne ke baad, hum output projection $W_{O} \in R^{d \times d}$ apply karte hain:

$(n \times d) \times (d \times d) = n \times d$

Cost: $n \cdot d \cdot d = n d^{2}$ operations.

Yeh step kyun? Output projection heads ke beech information mix karta hai aur model dimension par wapas map karta hai. Yeh ek aur $O (n d^{2})$ term contribute karta hai—linear-projection cost count karte waqt ise bhoolna mat.

Memory complexity

Figure — Computational complexity of attention

Why each component matters

Linear projections: $O (n d^{2})$

Yeh sequence length ke saath linearly scale karta hai. $n$ double karo toh kaam double ho jaata hai. Lambi sequences ke liye bottleneck nahi hai lekin bahut choti sequences ke liye dominate karta hai jahan $n ≪ d$ . Yeh term Q, K, V projections aur output projection $W_{O}$ ko cover karta hai—milake roughly $4 n d^{2}$ operations, lekin asymptotically $O (n d^{2})$ .

Attention matrix: $O (n^{2} d_{k})$

Yahi core problem hai. $n^{2}$ term ka matlab hai:

2× sequence length → 4× compute
10× sequence length → 100× compute

Standard attention mein yeh kyun unavoidable hai: Har token ko decide karne ke liye ki "kise dhyan dena hai", har doosre token ke saath score chahiye.

Worked example Concrete numbers

Setup: GPT-2 Medium jisme $d = 1024$ , $d_{k} = 64$ , 12 heads (toh $h \cdot d_{k} = d$ ). Projection cost $\approx 4 n d^{2}$ hai (Q, K, V, output) — $h$ se nahi multiply hota, kyunki heads $d$ dimension ko split karte hain.

Sequence length $n$	Attention FLOPs ( $h n^{2} d_{k}$ )	Linear projection FLOPs ( $4 n d^{2}$ )	Ratio attention/projection
128	12 × 128² × 64 = 12.6M	4 × 128 × 1024² = 537M	0.02×
512	12 × 512² × 64 = 201M	4 × 512 × 1024² = 2.1B	0.10×
2048	12 × 2048² × 64 = 3.2B	4 × 2048 × 1024² = 8.6B	0.37×
8192	12 × 8192² × 64 = 51.5B	4 × 8192 × 1024² = 34.4B	1.5×
Yeh kyun important hai: 8K tokens par attention projections se aage nikal jaata hai. Isi liye long-context models ko efficient attention chahiye.

Multi-head attention scaling

$h$ attention heads ke saath, har dimension $d_{k} = d / h$ ka:

Attention cost: $h$ heads mein se har ek ka cost $n^{2} d_{k}$ hai, toh total $h \cdot n^{2} d_{k} = n^{2} d$ (kyunki $h d_{k} = d$ ).
Projection cost: Q, K, V projections aur output projection sabhi full $d$ -dimensional space par ek baar operate karte hain, har head ke liye ek baar nahi. Toh projection cost $O (n d^{2})$ rehta hai — yeh $h$ se multiply nahi hota.

$Total = O (h n^{2} d_{k} + n d^{2}) = O (n^{2} d + n d^{2})$

Key insight: Zyada heads use karne se asymptotic complexity nahi badalti (abhi bhi $O (n^{2} d + n d^{2})$ ), aur projection term mein $h$ ka factor nahi lagta. Heads mein split karna sirf same $d$ -dimensional projections ko reshape karta hai.

Comparison with other architectures

| Architecture | Time complexity | Memory | Receptive field | |------------|-----------------|-----------------| | Self-attention | $O (n^{2} d)$ | $O (n^{2})$ | Global (sabhi tokens) | | RNN (LSTM/GRU) | $O (n d^{2})$ | $O (d)$ | Sequential (limited) | | CNN (kernel $k$ ) | $O (nk d^{2})$ | $O (n d)$ | Local ( $k$ tokens) | | Sparse attention | $O (n n d)$ | $O (n n)$ | Structured patterns | | Linear attention | $O (n d^{2})$ | $O (n d)$ | Global (approximation) |

Trade-off: Self-attention global context turant deta hai (kisi bhi do tokens ke beech depth-1 path) lekin quadratic cost chukani padti hai. RNNs linear hain lekin door ke tokens ko connect karne ke liye $n$ sequential steps chahiye.

Efficient attention variants

$O (n^{2})$ bottleneck ne ek research area ko janam diya hai:

Sparse attention (Sparse Transformer, Longformer): Sirf token pairs ke subset ke liye attention compute karo (jaise local windows + global tokens). $O (n lo g n)$ ya $O (n n)$ tak reduce ho jaata hai.
Linear attention (Performers, Linear Transformers): Kernel methods se attention approximate karo, $O (n d^{2})$ achieve karte hue $n \times n$ matrix ko kabhi materialize kiye bina.
Flash Attention: $O (n^{2} d)$ complexity rakhta hai lekin tiling use karke memory access patterns optimize karta hai, memory ko $O (n^{2})$ se $O (n)$ tak reduce karta hai full attention matrix store kiye bina.

Practical implications

Training vs. inference

Training: $S$ ko backpropagation ke liye store karna padta hai. Memory aksar limiting factor hoti hai, compute nahi.

Inference: Full matrices store kiye bina on-the-fly attention kar sakta hai. KV-caching help karta hai: past keys/values store karo taaki har naye token ke liye unhe recompute na karna pade.

Why context length is expensive

Quadratic scaling ka matlab hai:

GPT-3 (2K context): manageable
GPT-4 (32K context): attention term mein 8K ke comparison mein 16× memory aur compute
100K context: 4K ke comparison mein 625× cost

Isi liye long-context models ya toh sparse attention use karte hain ya run karne ke liye bahut expensive hain.

Recall Ek 12-saal ke bacche ko explain karo

Socho tum $n$ students ki ek class mein ho, aur har kisi ko information share karne ke liye har doosre ko ek chit deni padti hai (yahi attention hai). Agar 10 students hain, toh tumhe $10 \times 10 = 100$ chits chahiye. Class double karke 20 students kar do? Ab tumhe $20 \times 20 = 400$ chits chahiye—chaar guna zyada!

Isi liye transformers lambe texts ke saath slow ho jaate hain: har word ko har doosre word se "baat" karni padti hai, toh length double karne par kaam chaar guna ho jaata hai. Samajhdar researchers aisa tarike dhundh rahe hain jisse words sirf apne neighbors se baat kar sakein ya sab chits dene se bachne ke liye tricks use kar sakein, jisse yeh bahut faster ban jaaye.

Connections

4.1.1-Self-attention-mechanism: Woh mechanism jo yeh complexity cause karta hai
4.1.7-Multi-head-attention: Heads split karne se computational cost kaise affect hoti hai
4.3.2-Sparse-attention-patterns: Quadratic complexity reduce karne ke solutions
4.5.1-Memory-optimization-techniques: Flash Attention aur gradient checkpointing
5.2.3-Positional-encoding-scaling: Kyun lambi sequences ko efficient attention chahiye

#flashcards/ai-ml

Standard self-attention ki time complexity kya hai? :: $O (n^{2} d_{k} + n d^{2})$ , lambi sequences ke liye $O (n^{2} d_{k})$ dominant hota hai jahan $Q K^{T}$ computation ko $n^{2} d_{k}$ operations lagte hain.

Self-attention sequence length mein quadratic kyun hai?

Kyunki attention scores

S = Q K^{T}

compute karne par ek

n \times n

matrix banti hai jahan har token ko har doosre token ke saath score compute karna padta hai, jiske liye

n^{2} d_{k}

operations chahiye.

Self-attention ki memory complexity kya hai?

O (n^{2} + n d)

n^{2}

term backpropagation ke liye attention score matrix store karne se aata hai, jo lambi sequences mein dominate kar sakta hai.

Sequence length double karne par attention compute par kya asar padta hai?

Compute chaar guna ho jaata hai kyunki attention

O (n^{2})

hai.

n

2 n

jaane par cost

n^{2}

(2 n)^{2} = 4 n^{2}

ho jaati hai.

Self-attention aur RNN ki time complexity compare karo :: Self-attention $O (n^{2} d)$ hai lekin parallel hai; RNN $O (n d^{2})$ hai lekin sequential hai. Lambi sequences ke liye ( $n > d$ ), attention slower hai lekin ek hi step mein global receptive field deta hai.

Kya multi-head attention projection cost ko h se multiply karta hai?

Nahi. Q, K, V aur output projections full

d

-dimensional space par ek baar operate karte hain, toh unka cost

O (n d^{2})

hai—

h \cdot n d^{2}

nahi. Sirf attention term heads ke across sum hota hai, jo

h \cdot n^{2} d_{k} = n^{2} d

deta hai.

Self-attention mein computational bottleneck kya hai? :: $Q K^{T}$ matrix multiplication, jo $O (n^{2} d_{k})$ hai. Tokens ke beech yeh all-to-all comparison inherently quadratic hai aur lambi sequences mein dominate karta hai.

O (n d^{2})

term mein kaunse projections contribute karte hain?

Query, key, value projections aur output projection

W_{O}

. Milake yeh roughly

4 n d^{2}

operations hain, lekin asymptotically

O (n d^{2})

n=2048 ke saath ek layer mein attention scores ke liye kitni memory chahiye?

204 8^{2} \approx 4.2

million floats. FP32 (4 bytes each) par, roughly 16 MB per attention head. Multiple heads aur layers ke saath, yeh jaldi badh jaata hai.

Aap ek poori book ko naively GPT mein feed kyun nahi kar sakte?

Quadratic complexity ki wajah se: ek book mein 100K tokens ho sakte hain. Yeh

100 K^{2} = 10

billion attention computations per layer hai, jiske liye massive memory (

10 B

floats ≈ 40 GB sirf attention matrices ke liye) aur compute chahiye.