提出一种常数时间注意力机制,让大模型长文本推理更快更省算力。
Attention in Constant Time: Vashista Sparse Attention for Long-Context Decoding with Exponential Guarantees
- 基于关键向量凸包投影建模注意力,发现仅少量词对查询有贡献
- 在支持间隙达标时,无效词权重指数衰减,有效词集大小恒定
- 可插拔部署,适合隐私敏感或离线环境,速度提升显著且精度损失小
大型语言模型在长上下文推理中,注意力机制消耗了大部分计算成本。然而实证表明,每个查询仅有少数词真正起作用。本文将注意力建模为键向量凸包的投影,并分析其熵松弛(类似softmax)行为。理论核心是面稳定性定理:当满足严格互补性边界(由KKT乘子验证的支持间隙Δ)时,熵注意力会集中于一个大小恒定的活跃面——无效词的总权重按exp(−Ω(Δ/ε))指数衰减,而活跃面误差随温度参数ε线性增长。该结果给出了稀疏解码的安全条件,并提供了一个在精度与算力间权衡的可控参数。基于此,我们提出Vashista稀疏注意力,通过类分页的上下文选择策略,为每查询维护一个小候选集,兼容现代推理架构。在长文本评估中,我们观察到稳定常数级有效支持、显著的时钟周期加速,且在支持间隙诊断预测的范围内质量下降极小。最后讨论了在隐私敏感和离线环境中部署的潜力,可互换的注意力模块能实现确定性延迟与成本,无需外部检索依赖。
原文摘要 · Abstract (English)
Large language models spend most of their inference cost on attention over long contexts, yet empirical behavior suggests that only a small subset of tokens meaningfully contributes to each query. We formalize this phenomenon by modeling attention as a projection onto the convex hull of key vectors and analyzing its entropic (softmax-like) relaxation. Our main theoretical contribution is a face-stability theorem showing that, under a strict complementarity margin (a support gap (Δ) certified by KKT multipliers), entropic attention concentrates on a constant-size active face: the total mass assigned to inactive tokens decays exponentially as (\exp(-Ω(Δ/\varepsilon))), while the error on the active face scales linearly in the temperature/regularization parameter (\varepsilon). This yields a practical criterion for when sparse long-context decoding is safe and provides a principled knob to trade accuracy for compute. Building on these guarantees, we introduce Vashista Sparse Attention, a drop-in mechanism that maintains a small candidate set per query through a paging-style context selection strategy compatible with modern inference stacks. Across long-context evaluations, we observe stable constant-size effective support, strong wall-clock speedups, and minimal quality degradation in the regimes predicted by the support-gap diagnostics. Finally, we discuss deployment implications for privacy-sensitive and air-gapped settings, where interchangeable attention modules enable predictable latency and cost without external retrieval dependencies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。