Tutorial: Algebraic Foundations Powering FlashAttention
8 hours ago
- #FlashAttention
- #Associative Algebra
- #Numerical Stability
- FlashAttention的高效性源于结合律的代数特性，使得注意力计算能够进行并行规约。
- 在线softmax算法是FlashAttention的关键组件，它通过携带状态（m, d）表示运行最大值和分母，并结合一种保持数值稳定的合并操作，从而被证明具有结合性。
- Welford方差算法是结合运算的另一个例子，其中携带状态（计数、均值、平方偏差和）允许稳定地流式计算方差。
- FlashAttention的状态包括用于最大值、分母和未归一化输出的（m, d, o），其合并操作基于最大差值进行重新缩放，并通过结构传递证明了结合性。
- 结构传递表明，任何应用于幺半群的双射都会保留结合性，这使得机器学习中的结合规约得以泛化，例如使用以2为底的指数运算以提高效率。
- 数值稳定性分析确保FlashAttention中没有溢出且精度损失最小，误差界随加法次数增加而扩展，不受分块影响。
- 第三同态定理提供了一种方法来检查顺序循环是否实际上是结合的，即通过验证前向和后向折叠的存在性，从而实现并行化。