linear attention vs flash attention

Topics

• attention mechanism
• optimization

Goal of linear attention (algorithm optimization) is different from implementation optimizations like flash attention.

FlashAttention

• Hardware-aware algorithm optimizes standard attention mechanism
• Avoids explicit $N\times N$ attention matrix materialization in High Bandwidth Memory (HBM)
• Uses techniques like tiling, recomputation within faster on-chip Static Random-Access Memory (SRAM)
• Effectively reduces memory footprint to $O(N)$ during execution
• Does not change underlying computational complexity; still performs $O(N^2)$ computations

Linear Attention

• Aims to reduce both computational complexity and memory complexity to $O(N)$
• Achieved by reformulating attention calculation itself
• Relevant where even $O(N^2)$ compute becomes prohibitive