Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.05602 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913097362440192 |
|---|---|
| author | Liberty, Edo Andoni, Alexandr Kleiner, Eldar |
| author_facet | Liberty, Edo Andoni, Alexandr Kleiner, Eldar |
| contents | We consider the problem of estimating the Attention mechanism in small space, and prove the existence of coresets for it of nearly optimal size. Specifically, we show that for any set of unit-norm keys and values $(K,V)$ in $\mathbb{R}^d$, there exists a subset $(K',V')$ of size at most $O({\sqrt{d} e^{ρ+o(ρ)}/\varepsilon})$ such that \[ \left\| \operatorname{Attn}(q,K,V)- \operatorname{Attn}(q,K',V') \right\| \le \varepsilon \] simultaneously for all queries whose norm is bounded by $ρ$. This outperforms the best known results for this problem. We also offer an improved lower bound showing that $\varepsilon$-coresets must have size $Ω({\sqrt{d} e^ρ/ε})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05602 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Nearly Optimal Attention Coresets Liberty, Edo Andoni, Alexandr Kleiner, Eldar Data Structures and Algorithms Artificial Intelligence We consider the problem of estimating the Attention mechanism in small space, and prove the existence of coresets for it of nearly optimal size. Specifically, we show that for any set of unit-norm keys and values $(K,V)$ in $\mathbb{R}^d$, there exists a subset $(K',V')$ of size at most $O({\sqrt{d} e^{ρ+o(ρ)}/\varepsilon})$ such that \[ \left\| \operatorname{Attn}(q,K,V)- \operatorname{Attn}(q,K',V') \right\| \le \varepsilon \] simultaneously for all queries whose norm is bounded by $ρ$. This outperforms the best known results for this problem. We also offer an improved lower bound showing that $\varepsilon$-coresets must have size $Ω({\sqrt{d} e^ρ/ε})$. |
| title | Nearly Optimal Attention Coresets |
| topic | Data Structures and Algorithms Artificial Intelligence |
| url | https://arxiv.org/abs/2605.05602 |