Long-context architectures — Hinglish notes

6.1.10 · AI-ML › Scaling & Efficient Architectures

Modern AI systems ko increasingly long sequences process karni padti hain—poore documents, code repositories, ya conversation histories. Traditional Transformers ko sequence length mein quadratic complexity $O (n^{2})$ face karni padti hai, jo unhe ~2k-8k tokens se aage ke contexts ke liye impractical bana deti hai. Long-context architectures is problem ko attention mechanisms aur memory structures ko redesign karke solve karti hain, taaki 100k+ token contexts efficiently handle ho sakein.

Why Long Context Matters

Standard Transformer attention har token pair ke beech similarity compute karta hai: $Attention (Q, K, V) = softmax (\frac{Q K ^{T}}{d _{k}}) V$

$n$ tokens ke liye, is mein $O (n^{2})$ memory aur compute lagti hai. 100k tokens par, yeh 10 billion comparisons per layer ho jaate hain.

Architectural Approaches

1. Sparse Attention Patterns

Longformer ka Sliding Window Derive Karna:

Token $i$ ke liye full attention cost se shuru karo: $C_{i} = n comparisons$

Size $w$ ki local window tak restrict karo: $C_{i}^{local} = w comparisons$

$n$ tokens ke liye: $C_{total} = n \cdot w$

Agar $w$ constant hai (jaise, 512), complexity ban jaati hai: $O (n \cdot w) = O (n) when w ≪ n$

Lekin local-only attention global context kho deta hai. Longformer ka solution: global attention tokens add karo jo sab kuch attend karte hain:

Zyaadatar tokens: local window ( $w$ comparisons)
$g$ special tokens: full attention ( $n$ comparisons each)
Total: $O (n w + g n)$

Agar $g ≪ n$ hai, toh yeh $O (n)$ hai with global information preserved.

Worked example Sliding Window with Global Tokens

Sequence (11 tokens): [CLS] The cat sat on the mat and fell asleep .
Window w=3:

Token "sat" attends to: ["cat", "sat", "on"]  ← local
Token [CLS] attends to: ALL tokens              ← global

Cost per token:
- Regular token: 3 comparisons (local window)
- Global token [CLS]: 11 comparisons (whole sequence)

There are 10 regular tokens + 1 global token:
Total: 10×3 + 1×11 = 41 vs. 11×11 = 121 full attention

Yeh step kyun? Global tokens (jaise [CLS]) document-level information aggregate karte hain, jabki local windows nearby dependencies capture karti hain. Yeh thodi si full attention ko mostly-local attention ke saath trade karta hai.

2. Linear Attention Mechanisms

Softmax expand karo: $softmax (Q K^{T})_{ij} = \frac{e ^{q_{i} \cdot k_{j}}}{\sum _{j^{'}} e ^{q_{i} \cdot k_{j^{'}}}}$

Iske liye saare $q_{i} \cdot k_{j}$ dot products compute karne padte hain → $O (n^{2})$ .

Linear attention $e^{q \cdot k}$ ko explicit feature maps $ϕ$ se approximate karta hai: $e^{q \cdot k} \approx ϕ (q)^{T} ϕ (k)$

Tab: $Attention (Q, K, V)_{i} = \frac{\sum _{j} ϕ ( q _{i} ) ^{T} ϕ ( k _{j} ) v _{j}}{\sum _{j} ϕ ( q _{i} ) ^{T} ϕ ( k _{j} )}$

Key insight: Sum ko associativity se rearrange karo: $= \frac{ϕ ( q _{i} ) ^{T} ( \sum _{j} ϕ ( k _{j} ) v _{j}^{T} )}{ϕ ( q _{i} ) ^{T} ( \sum _{j} ϕ ( k _{j} ) )}$

Ab hum compute karte hain (maano $d_{ϕ}$ = feature map dimension, $d_{v}$ = value dimension):

$S = \sum_{j} ϕ (k_{j}) v_{j}^{T}$ ek baar saare tokens ke liye → $O (n d_{ϕ} d_{v})$
$Z = \sum_{j} ϕ (k_{j})$ ek baar → $O (n d_{ϕ})$
Har query ke liye: numerator $ϕ (q_{i})^{T} S$ aur denominator $ϕ (q_{i})^{T} Z$ → $O (d_{ϕ} d_{v})$ per query, yaani $n$ se independent

$n$ queries mein total: $O (n d_{ϕ} d_{v})$ — sequence length mein linear!

Yeh step kyun? Key-value aggregation $S$ aur normalizer $Z$ precompute karke, har query sirf in fixed-size summaries ko touch karta hai. Per-query cost $d_{ϕ}, d_{v}$ par depend karti hai, $n$ par nahi. Feature map $ϕ$ ko quality maintain karne ke liye softmax kernel ko itna achha approximate karna chahiye.

Worked example Linear Attention Calculation

Given 4 tokens, d=2 dimensions, feature map ϕ(x) = [1, x₁, x₂] (so d_ϕ = 3):

Q = [[1, 0], [0, 1]]              # 2 queries
K = [[1, 0], [0, 1], [1, 1], [0, 0]]  # 4 keys  
V = [[1], [2], [3], [4]]         # 4 scalar values (d_v = 1)

Feature maps of keys (each is 3-dim):
ϕ(k₁) = [1, 1, 0]
ϕ(k₂) = [1, 0, 1]
ϕ(k₃) = [1, 1, 1]
ϕ(k₄) = [1, 0, 0]

Step 1: Precompute S = Σⱼ ϕ(kⱼ) vⱼ   (3-dim vector since d_v=1)
S = [1,1,0]·1 + [1,0,1]·2 + [1,1,1]·3 + [1,0,0]·4
  = [1,1,0] + [2,0,2] + [3,3,3] + [4,0,0]
  = [10, 4, 5]

Step 2: Precompute normalizer Z = Σⱼ ϕ(kⱼ)   (3-dim vector)
Z = [1,1,0] + [1,0,1] + [1,1,1] + [1,0,0]
  = [4, 2, 2]

Step 3: For q₁ = [1,0], ϕ(q₁) = [1, 1, 0]
numerator   = ϕ(q₁)·S = [1,1,0]·[10,4,5] = 10 + 4 + 0 = 14
denominator = ϕ(q₁)·Z = [1,1,0]·[4,2,2]  = 4 + 2 + 0 = 6
Attention₁  = 14 / 6 ≈ 2.33   ← normalization matters!

Compare to full attention: would need 4 separate q·k dot products per query.

Yeh step kyun? Keys par linear scan globally ek baar hota hai ( $S$ aur $Z$ build karte waqt), har query ke liye baar baar nahi. Phir har query un summaries ko constant time mein reuse karta hai w.r.t. $n$ , aur $ϕ (q)^{T} Z$ se division softmax-style normalization enforce karta hai.

3. State Space Models (SSMs)

Tokens ke liye Discretization: Continuous time ko discrete steps (tokens) se replace karo: $h_{k} = \overset{ˉ}{A} h_{k - 1} + \overset{ˉ}{B} x_{k}$ $y_{k} = C h_{k}$

jahan $\overset{ˉ}{A} = e^{Δ A}$ aur $\overset{ˉ}{B} = (e^{Δ A} - I) A^{- 1} B$ step size $Δ$ ke liye.

SSMs long context ke liye kyun?

State $h_{k}$ ki dimension fixed hai (jaise, 256), sequence length ke saath nahi badhti
Update $O (d^{2})$ per token hai jahan $d$ state dimension hai
Total: $O (n d^{2})$ with $d ≪ n$ → effectively $O (n)$

$A$ ko diagonal plus low-rank choose karo: $A = Λ - p q^{T}$

Yeh fast matrix exponential allow karta hai: $e^{Δ A} \approx I + Δ A + \frac{( Δ A ) ^{2}}{2} + \dots$

Diagonal $Λ$ ke saath, exponential hai: $e^{ΔΛ} = diag (e^{Δ λ_{1}}, \dots, e^{Δ λ_{d}})$

Low-rank correction Woodbury identity ke zariye efficient updates allow karta hai.

Recurrent form: $h_{k} = \overset{ˉ}{A} h_{k - 1} + \overset{ˉ}{B} x_{k}$

Convolutional form (training parallelization ke liye): $y = \overset{ˉ}{K} * x$

jahan $\overset{ˉ}{K}_{k} = C \overset{ˉ}{A}^{k} \overset{ˉ}{B}$ ek learnable convolution kernel hai.

Worked example SSM vs Attention on Long Sequence

Sequence: 100k tokens, embedding dim d=512, state dim s=256

Transformer attention:
- Memory: 100k × 100k = 10B attention scores
- Compute: O(100k²) per layer

S4 SSM:
- Memory: state vector 256-dim + convolution kernel ~16k
- Compute: O(100k × 256²) = O(100k) effective per layer

At 100k length, SSM is ~1000× more memory efficient.
But: SSM state is fixed-size, may lose information that attention retains.

Yeh step kyun? State space formulation poori history ko ek fixed vector mein compress karta hai, RNN hidden states ki tarah lekin better training stability ke saath. Structured matrices ise computationally feasible banate hain.

4. Memory-Augmented Architectures

Memorizing Transformers architecture:

Local attention: Recent $w$ tokens ko attend karo (sliding window)
Memory attention: External memory se $k$ nearest neighbors ko attend karo
Memory update: Current layer ke key-value pairs memory bank mein store karo

Memory lookup approximate nearest neighbor (ANN) search use karta hai: $Retrieve (q) = TopK_{m \in Memory} (similarity (q, m_{k}))$

FAISS ya similar use karke, yeh $O (lo g M)$ hai jahan $M$ memory size hai.

Total complexity: $O (n w) + O (n lo g M)$ ≈ $O (n)$ jab $w, lo g M ≪ n$

Worked example Memory-Augmented Lookup

Processing token 50,000 in a document:

Local window (w=512):
- Attend to tokens 49,488-50,000

Memory bank (M=10k compressed key-values from earlier tokens):
- Query current token embedding q₅₀ₖ
- FAISS finds top-k=64 most similar keys from memory
- Attend to those 64 retrieved values

Total attention: 512 + 64 = 576 tokens
vs. 50,000 for full attention

Memory stores: representative moments, chapter boundaries, 
key facts from earlier sections

Yeh step kyun? Saare past tokens equally relevant nahi hote. Retrieval computation ko wahan focus karti hai jahan current token ke liye matter karta hai, human selective attention ko mimic karte hue.

Comparison Table

Architecture	Complexity	Context Length	Training	Key Tradeoff
Sparse Attention (Longformer)	$O (n)$	16k-32k	Moderate	Local bias, global tokens zaroori
Linear Attention (Performer)	$O (n)$	100k+	Fast	Approximation quality
State Space (S4)	$O (n)$	1M+	Fast (convolution)	Fixed state capacity
Memory-Augmented	$O (n lo g M)$	Unlimited	Slow (retrieval)	Memory management overhead

Kyun galat hai: Feature map $ϕ$ softmax kernel ko approximate karta hai. Tasks ke liye jinhein precise token interactions chahiye (jaise, exact words copy karna, arithmetic), approximation quality degrade kar deti hai. Empirically, linear attention often standard attention se underperform karta hai un tasks par jo exact attention patterns maangti hain.

Fix: Linear attention encoder layers ke liye use karo jo long context process karti hain, lekin decoder layers ke liye standard attention rakho jahan output generate karte waqt precision matter karti hai. Ya hybrid approaches use karo (local + linear).

Kyun galat hai: Transformers mein multiple layers hoti hain. Information network ke through propagate hoti hai. $w$ size ki sliding window ke saath, receptive field har layer mein ~ $w$ tokens badhta hai, toh ek token roughly $n / w$ layers ke baad distant context tak pahunch sakta hai—full attention se kaafi sasta.

Example: Position 1000 par token, window $w = 100$ ke saath (har taraf ±50 attend karta hai)

Layer 1: receptive field ≈ 100 tokens (950–1050)
Layer 2: un mein se har ek ne ±50 dekhe → field ≈ 200 tokens (900–1100)
Layer $L$ : receptive field ≈ $L \cdot w$ tokens
Pure 1000-token span cover karne ke liye tumhe $\approx n / w \approx 10$ layers chahiye, nahi 4–5.

Fix: Itni depth do ( $\sim n / w$ layers) ki information propagate ho sake, ya global tokens / dilated windows add karo taaki kam layers mein long-range access shortcut ho.

Key Formulas Summary

Recall Baarah Saal ke Bachche ko Samjhao

Socho tum ek bahut badi kitaab padh rahe ho jisme 100,000 words hain. Tumhara dimaag har ek word yaad nahi rakh sakta jo tumne padha, hai na?

Full attention matlab hai ki har naye word ke liye tum poori kitaab mein waapas jaake check karte ho ki yeh word har pichle word se kaise related hai. Yeh bahut thaka dene wala hai! Agar kitaab 1,000 pages ki hai, toh tum ek million page flips karoge.

Sparse attention kehta hai: "Sirf pichle kuch pages dekho (local), plus table of contents aur chapter summaries (global tokens)." Bahut faster! Tum gist phir bhi samajh jaate ho bina sab kuch dobara padhe. (Ek catch: bahut door ke pages ko sirf local jhaankon se connect karne ke liye, tumhe kitaab ke kaafi "passes" chahiye.)

Linear attention matlab hai ki padhte waqt ek cheat sheet banana—tum key points likhte ho jo automatically update hoti hain. Jab tum naya word dekhte ho, poori kitaab ki jagah sirf apna ek-page cheat sheet check karte ho. Cheat sheet check karna utna hi chhota time leta hai chahe kitaab kitni bhi lambi ho.

Memory banks matlab hai 100 sabse important sentences highlight karna, phir jab kuch yaad karna ho sirf un highlights ko dekhna.

Har method sab kuch dobara padhne se bachne ka ek smart shortcut dhundhta hai, taaki tum bahut, bahut lambi kitaabein (ya AI mein, bahut lambi conversations aur documents) handle kar sako.

Connections

Transformer Architecture - woh foundation jo optimize ho rahi hai
Attention Mechanisms - core operation jo re-engineer ho rahi hai
Computational Complexity - $O (n^{2})$ bottleneck samajhna
Retrieval-Augmented Generation - related memory approach
Recurrent Neural Networks - SSMs recurrent ideas ko better scaling ke saath revive karte hain
Kernel Methods - linear attention kernel approximation use karta hai
Information Bottleneck - state space models fixed capacity se compress karte hain

#flashcards/ai-ml

Standard Transformer attention mein O(n²) complexity kyun hoti hai? :: Kyunki yeh har token pair ke beech similarity (QKᵀ) compute karta hai — n queries mein se har ek n keys se compare hoti hai.

Longformer jaise sparse attention patterns ka key idea kya hai?

Har token ek local window (constant size w) plus kuch global tokens ko attend karta hai, complexity O(n²) se O(n) tak reduce hoti hai jabki long-range dependencies preserve rehti hain.

Linear attention O(n) complexity kaise achieve karta hai?

Softmax kernel ko explicit feature maps ϕ se approximate karke, taaki key-value aggregation S=Σϕ(k)vᵀ aur normalizer Z=Σϕ(k) ek baar precompute ho sakein aur har query ka cost sirf O(d_ϕ d_v) ho, n se independent.

Sparse local attention mein full sequence cover karne ke liye kitni layers chahiye?

Lagbhag n/w layers, kyunki har layer receptive field sirf ~w tokens expand karti hai (jab tak global/dilated tokens shortcut na karein).

Attention aur state space models mein fundamental difference kya hai?

Attention pairwise comparisons ke saath poori token history maintain karta hai; SSMs poori history ko ek fixed-dimension state vector mein compress karte hain jo recurrently update hota hai.

Memory-augmented architectures ka tradeoff kya hai? :: Yeh external memory se retrieve karke unlimited context achieve karte hain, lekin retrieval overhead (O(log M) per query) add hoti hai aur kya store karna hai yeh manage karna padta hai.

Exact-matching tasks par linear attention kyun underperform kar sakta hai?

Softmax ka feature map approximation precise attention patterns capture nahi kar pata jo copying ya arithmetic ke liye zaroori hain, exact attention ki tulna mein quality degrade kar deta hai.

Sparse attention mein distant tokens tak information kaise pahunchti hai?

Multi-layer propagation ke zariye — receptive field ~w per layer badhta hai, toh full coverage ke liye ~n/w layers chahiye; global/dilated tokens ise fast karte hain.

State space models ka convolutional view kya hai?

SSMs ko convolution y = K̄ * x ki tarah formulate kiya ja sakta hai jahan kernel K̄ₖ = CA^kB hai, jo parallel training enable karta hai jabki recurrent inference maintain rehti hai.