自注意力O(n²)复杂度的优化方法
哪些公司问过
答案要点
- 标准自注意力时间复杂度 O(n²d),显存瓶颈是 n×n 的注意力分数矩阵,n 为序列长度
- 稀疏/局部注意力:滑动窗口降到 O(nw),Longformer、BigBird 加全局 token 和随机连接保留长程依赖
- 低秩与核方法:Linformer 把 K、V 沿序列维投影到 k 维;Performer 用随机特征近似 softmax,借矩阵乘法结合律实现线性复杂度
- FlashAttention 是精确注意力,靠分块与在线 softmax 减少显存读写,FLOPs 不变但显存线性、实际更快
- 推理侧配合 KV Cache、MQA/GQA 降低缓存显存;另有 Mamba 等线性复杂度的替代架构
易错点
- 误以为 FlashAttention 是近似算法或降低了 O(n²) 计算量,它是精确计算,只降低显存和 IO
- 只说 O(n²) 而不区分计算和显存,长序列下显存往往先成为瓶颈
- 把 KV Cache 当成降复杂度的方法,它只是避免自回归推理时重复计算历史 K、V
面试官常见追问
- FlashAttention 为什么能加速,计算量不是没变吗?
- 线性注意力为什么效果通常不如标准注意力?
- GQA 能降低注意力的复杂度吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。