通过实时发现模式与动态阈值，实现超快长文本预填充。
FlashPrefill: Instantaneous Pattern Discovery and Thresholding for Ultra-Fast Long-Context Prefilling
- 实时搜索垂直、斜向、块状稀疏模式，快速定位注意力结构。
- 动态阈值避免排序开销，在256K序列上提速27.78倍。
- 适用于不同长度序列，4K上下文仍保持1.71倍加速，实用性强。
长上下文建模是大语言模型的关键能力，但注意力机制的二次复杂度仍是计算瓶颈，尤其在高耗时的预填充阶段。现有稀疏注意力方法通常存在搜索延迟高或稀疏度不足的问题。本文提出FlashPrefill框架，通过即时模式发现与阈值化实现超快预填充。该方法采用快速块搜索技术，同时识别动态的垂直、斜向和块状稀疏注意力模式；关键创新在于动态阈值机制，无需排序或累加注意力分数即可有效消除长尾分布，提升稀疏度。大量实验表明，FlashPrefill在256K序列上实现27.78倍速度提升。值得注意的是，相比其他方法在短序列中效率下降，FlashPrefill在4K上下文仍保持1.71倍加速，展现出跨序列尺度的鲁棒性与实用性。
原文摘要 · Abstract (English)
Long-context modeling is a pivotal capability for Large Language Models, yet the quadratic complexity of attention remains a critical bottleneck, particularly during the compute-intensive prefilling phase. While various sparse attention mechanisms have been explored, they typically suffer from either significant search latency or insufficient sparsity. In this paper, we propose FlashPrefill, a framework enabling ultra-fast prefilling via instantaneous pattern discovery and thresholding. FlashPrefill leverages a fast block-searching technique to simultaneously locate dynamic vertical, slash, and block-sparse attention patterns. Crucially, it introduces a dynamic thresholding mechanism that bypasses the prohibitive overhead of sorting or accumulating attention scores while effectively eliminating the long-tail distribution to enhance sparsity. Extensive evaluations demonstrate that FlashPrefill achieves a substantial leap in efficiency, delivering an unprecedented 27.78x speedup on 256K sequences. Notably, unlike existing methods that incur efficiency degradation on shorter contexts, FlashPrefill maintains a 1.71x speedup even at a 4K context length, demonstrating its robustness and practical utility across varying sequence scales.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。