SOURCE-LINKED INTELLIGENCE

Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions

arXiv · AI, language, vision and robotics · article · Sep 6, 2026 · UTC

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. Liberty, Andoni and Kleiner proved that unweighted coresets of size $O(\sqrt d e^{ρ+\frac12\logρ+o(\log\logρ)}/\varepsilon)$ exist, $ρ$ the query radius times the centred key radius, against a lower bound $Ω(\sqrt d e^ρ/\varepsilon)$, and conjectured that closing the gap needs new techniques. It does not: a spherical lift of both balls into one exponential-kernel instance lets the Bozzai-Rothvoss chaining bound apply

Read original source ↗ Open in workspace

recordType

paper

region

Global