As asked
Standard self-attention has O(n^2) time and memory complexity in sequence length. Walk me through exactly where that quadratic term comes from, and describe at least two concrete algorithmic approaches that reduce it.
Sample answer outline
The quadratic cost comes from computing all n^2 query-key dot products to form the attention matrix, then multiplying by values. FlashAttention avoids materializing the full n x n matrix by tiling the computation in SRAM and fusing the softmax, achieving O(n) memory while keeping exact attention. Sparse attention methods (Longformer sliding window, BigBird random plus global patterns) reduce compute by restricting which token pairs attend to each other, trading exact for approximate attention.
Expect these follow-ups
- How does FlashAttention 2 differ from the original FlashAttention in terms of the tiling strategy?
- What is the causal masking change required in FlashAttention for decoder-only models?