arXiv cs.CL· Ofek I. Cohen·· 11 小时前AI 评分18
面向 Softmax 注意力的查询无关 coreset：更优界与高效构造
Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions
AI 导读
研究者为 softmax 注意力头构造出查询无关 coreset，规模为 O(e^ρ(√d_v+√(d_k log(1+ρ)))/ε)，在随机多项式时间内完成，将 Liberty、Andoni 与 Kleiner 的存在性上界改进到距其下界仅差 √log(1+ρ)。
正文 · AI 翻译
摘要：针对 softmax 注意力头的查询无关 coreset 是键值对的一个子集，对于球内每个查询，其注意力输出与完整输出的差距在 $\varepsilon$ 以内。设 $\rho$ 为查询半径乘以中心化键半径，我们在随机多项式时间内构造出大小为 $O(e^{\rho}(\sqrt{d_v}+\sqrt{d_k\log(1+\rho)})/\varepsilon)$ 的此类 coreset，将 Liberty、Andoni 和 Kleiner 的存在性界 $O(\sqrt d\,e^{\rho+\frac12\log\rho+o(\log\log\rho)}/\varepsilon)$ 改进到与其下界 $\Omega(\sqrt d\,e^{\rho}/\varepsilon)$ 相差 $\sqrt{\log(1+\rho)}$ 以内：将两个球球面提升为同一个指数核实例后满足 Bozzai--Rothvoss 链式界，而 Chevet 不等式将键维度与值维度分离。采样上界 $O(e^{2\rho}/\varepsilon^{2})$ 补全了整个包络，在固定维度下 Tai 的无直径界去掉了对数项。对 Qwen2.5-7B-Instruct 和 Llama-3.1-8B-Instruct 每个头的普查发现 $\rho\ge24.100$，因此任何带有因子 $e^{\rho}/\varepsilon$ 的整球界所规定的 coreset 都大于缓存：在这些模型上，该算法贡献是渐近的。
| 主题： | 数据结构与算法（cs.DS）；计算与语言（cs.CL） |
| 引用为： | arXiv:2609.06327 [cs.DS] |
| （或 arXiv:2609.06327v3 [cs.DS] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2609.06327 由 DataCite 颁发 arXiv DOI |
提交历史
来自：Ofek I. Cohen [查看电子邮件]
[v1]
2026年9月6日周日 01:23:58 UTC（28 KB）
[v2]
2026年9月13日周日 14:47:32 UTC（291 KB）
[v3]
2026年11月4日周三 09:20:34 UTC（286 KB）
来源：arXiv cs.CL · arxiv.org