M4-048M4: Sequences & TransformersEfficient Attention & FlashAttentionEasy
⚡Flashcard Drill➔Mastery:

Online Softmax: Enabling Block-by-Block Incremental Attention Tiling

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M4-049 →
📐 Mathematical Definition
mnew=max⁡(m,max⁡jzj);ℓnew=em−mnewℓ+∑jezj−mnewm^{\text{new}}=\max(m,\max_j z_j);\quad \ell^{\text{new}}=e^{m-m^{\text{new}}}\ell+\sum_j e^{z_j-m^{\text{new}}}
⚡ One-Sentence Core Answer
Online softmax updates running maximums and normalizers dynamically as blocks arrive, eliminating the traditional requirement of scanning the full sequence before computing exponents.

📌 Key Takeaways

  • •
    Standard Softmax 3-pass limitation: Pass 1 finds global max mm; Pass 2 computes sum ℓ=∑exi−m\ell = \sum e^{x_i - m}; Pass 3 divides by ℓ\ell
  • •
    Online Softmax (Milakov & Gimelshein): maintains running state (mk,ℓk)(m_k, \ell_k), updating in 1 pass via exponential rescaling factors
  • •
    Tiled Attention integration: dynamically rescales accumulated partial output matrices in SRAM as new key-value blocks are processed

📐 Mathematical Derivations

Mathematical Formulations (Milakov & Gimelshein, 2018; Dao et al., 2022):
Standard 3-pass softmax over vector x∈RNx \in \mathbb{R}^N:
m=max⁡ixim = \max_i x_i, ℓ=∑i=1Nexi−m\quad \ell = \sum_{i=1}^N e^{x_i - m}, pi=exi−mℓ\quad p_i = \frac{e^{x_i - m}}{\ell}. Requires full vector xx in memory.
Online 2-Pass Softmax Derivation:
Partition vector xx into two blocks x(1)x^{(1)} and x(2)x^{(2)}.
- For block 1: m(1)=max⁡(x(1)),ℓ(1)=∑iexi(1)−m(1)m^{(1)} = \max(x^{(1)}), \quad \ell^{(1)} = \sum_i e^{x_i^{(1)} - m^{(1)}}.
- When block 2 arrives: compute local statistics m(2)=max⁡(x(2)),ℓ(2)=∑iexi(2)−m(2)m^{(2)} = \max(x^{(2)}), \quad \ell^{(2)} = \sum_i e^{x_i^{(2)} - m^{(2)}}.
- Running Combined Updates:
New global maximum: mnew=max⁡(m(1),m(2))m^{\text{new}} = \max(m^{(1)}, m^{(2)}).
New global normalizer: ℓnew=ℓ(1)⋅em(1)−mnew+ℓ(2)⋅em(2)−mnew\ell^{\text{new}} = \ell^{(1)} \cdot e^{m^{(1)} - m^{\text{new}}} + \ell^{(2)} \cdot e^{m^{(2)} - m^{\text{new}}}.
- Output Vector Rescaling in FlashAttention:
Let accumulated output in SRAM from block 1 be O(1)O^{(1)}. When block 2 arrives, update OO dynamically:
Onew=O(1)⋅(ℓ(1)em(1)−mnewℓnew)+(eS(2)−mnewℓnew)V(2)O^{\text{new}} = O^{(1)} \cdot \left( \frac{\ell^{(1)} e^{m^{(1)} - m^{\text{new}}}}{\ell^{\text{new}}} \right) + \left( \frac{e^{S^{(2)} - m^{\text{new}}}}{\ell^{\text{new}}} \right) V^{(2)}.
By induction, blocks of arbitrary size can be streamed through SRAM one by one, producing exact final outputs without ever storing the full attention matrix.

🏭 Production Trade-offs

Register pressure: Online softmax requires maintaining running vectors m,ℓ,Om, \ell, O inside GPU register files. Kernel block sizes (Br,BcB_r, B_c) must be carefully chosen to avoid register spilling into local memory.
⚠️ Common Interview Pitfalls
  • ✕
    Forgetting to rescale previous partial output accumulators O(1)O^{(1)} when updating the running maximum mnewm^{\text{new}}
  • ✕
    Assuming online softmax introduces numerical approximation drift; it is mathematically exact down to floating-point rounding
🎯 Interviewer Follow-up Inquiries
  • ?
    How does the exponential rescaling factor em(1)−mnewe^{m^{(1)} - m^{\text{new}}} guarantee numerical stability in online softmax?
  • ?
    What determines the optimal thread block size (Br,Bc)(B_r, B_c) in FlashAttention CUDA kernels?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM4-047: FlashAttention Core Philosophy: IO-Awareness, SRAM Tiling, and Memory Hierarchy📋 Back to BankNext →M4-049: FlashAttention Backward Pass: Recomputing Softmax in SRAM Without Saving Intermediate Matrices