← 研踪 PaperTrailarXiv:2609.06327 · v3
Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions
首次提交 2026-09-06 09:23
版本更新 2026-11-04 17:20
雷达观测 2026-11-05 11:10
摘要
A query-oblivious coreset for a softmax-attention head is a subset of the key--value pairs whose attention output is within $\varepsilon$ of the full one for every query in a ball. With $ρ$ the query radius times the centred key radius, we build such coresets of size $O(e^ρ(\sqrt{d_v}+\sqrt{d_k\log(1+ρ)})/\varepsilon)$ in randomised polynomial time, improving the existential $O(\sqrt d\,e^{ρ+\frac12\logρ+o(\log\logρ)}/\varepsilon)$ of Liberty, Andoni and Kleiner to within $\sqrt{\log(1+ρ)}$ of their $Ω(\sqrt d\,e^ρ/\varepsilon)$ lower bound: a spherical lift of both balls into one exponential-kernel instance admits the Bozzai--Rothvoss chaining bound, and Chevet's inequality splits key from value dimension. A sampling cap $O(e^{2ρ}/\varepsilon^{2})$ completes the envelope, and in fixed dimension Tai's diameter-free bound removes the logarithm. A census of every head of Qwen2.5-7B-Instruct and Llama-3.1-8B-Instruct finds $ρ\ge24.100$, so every whole-ball bound with a factor $e^ρ/\varepsilon$ prescribes a coreset larger than the cache: the algorithmic contribution is asymptotic on these models.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-04 17:20 · 最新观测版本
Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions
A query-oblivious coreset for a softmax-attention head is a subset of the key--value pairs whose attention output is within $\varepsilon$ of the full one for every query in a ball. With $ρ$ the query radius times the centred key radius, we build such coresets of size $O(e^ρ(\sqrt{d_v}+\sqrt{d_k\log(1+ρ)})/\varepsilon)$ in randomised polynomial time, improving the existential $O(\sqrt d\,e^{ρ+\frac12\logρ+o(\log\logρ)}/\varepsilon)$ of Liberty, Andoni and Kleiner to within $\sqrt{\log(1+ρ)}$ of their $Ω(\sqrt d\,e^ρ/\varepsilon)$ lower bound: a spherical lift of both balls into one exponential-kernel instance admits the Bozzai--Rothvoss chaining bound, and Chevet's inequality splits key from value dimension. A sampling cap $O(e^{2ρ}/\varepsilon^{2})$ completes the envelope, and in fixed dimension Tai's diameter-free bound removes the logarithm. A census of every head of Qwen2.5-7B-Instruct and Llama-3.1-8B-Instruct finds $ρ\ge24.100$, so every whole-ball bound with a factor $e^ρ/\varepsilon$ prescribes a coreset larger than the cache: the algorithmic contribution is asymptotic on these models.
查看此版本解读 →查看此版本原文 ↗