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

Ofek I. Cohen

cs.DSSep 6, 2026

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

Authors: Ofek I. Cohen

Organizations: Tel Aviv University.

Abstract

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, and Chevet's inequality splits key from value dimension, giving coresets of size $O(e^ρ(\sqrt{d_v}+\sqrt{d_k\log(1+ρ)})/\varepsilon)$ in randomised polynomial time, the first constructive whole-ball guarantee within $\sqrt{\log(1+ρ)}$ of the lower bound. A sampling cap $O(e^{2ρ}/\varepsilon^{2})$ completes the envelope; in fixed dimension Tai's diameter-free bound removes the logarithm, settling the Gaussian-restriction case of a Bozzai-Rothvoss question for the kernels. We give theLiberty-Andoni-Kleiner lower boud transfer the one-waycommunication bounds of Chen et r is the price of one signing forall queries. A census of every head of Qwen2.5-7B-Instruct and Llama-3-8B-Instruct finds $ρ$ at least 23.877, so everyactor $e^ρ/\varepsilon$ prescribes a coreset larger than the cache: the algorithmic contribution is asymptotic on these models.

Figures & tables

Device	Source
Tensor lift $\psi(k)\otimes v$ , centring invariance, balanced rescaling	[ 21 , Lem. 16] ; [ 22 , App. B.5] ; [ 11 , §6.1.2] ; [ 30 ]
Halving; ratio split into numerator/denominator discrepancies	[ 13 , 28 ] ; [ 25 , Thm. 4] ; [ 22 , §2.2] ; [ 20 , Lem. B.1]
Scalar spherical exponential-kernel discrepancy	[ 9 , Thm. 1.11] ; earlier [ 21 , Lem. 17] , [ 28 , Cor. 4.3]
Key/value split of the Gaussian width	Chevet [ 14 , 34 ] ; sphere case [ 33 , Thm. 1]
Gram–Schmidt walk in halving; Las Vegas rejection	[ 6 ] ; [ 28 , §2] ; [ 9 ] ; [ 32 , Alg. 1]
RKHS $1/\varepsilon^{2}$ bounds (sampling and greedy); two-block form	[ 26 ] ; [ 21 , Thm. 24] ; [ 20 , Thm. 4.5] ; [ 36 ]

Table 1: Inherited devices. New here: the assembly in Theorem 1.1 , the uniform-guarantee construction, the sphere completion and balance repair and value encoding of Section 5 , the centred instance and full proof in Theorem 1.4 (a), the transfer in (c), and Proposition 1.5 .

Regime	Best upper bound	Best lower bound	Gap
$d_{k}=d_{v}=d$ , $\varepsilon\sqrt{d}\gtrsim e^{-\rho}$ , $d_{k}\gtrsim\rho^{3}$	$e^{\rho}\sqrt{d\log(1+\rho)}/\varepsilon$	$e^{\rho}\sqrt{d}/\varepsilon$ ( 1.4 a, [ 25 ] )	$\sqrt{\log(1+\rho)}$
$d_{k}=d_{v}=d$ fixed, $\rho\to\infty$	$F(d,d)e^{\rho}/\varepsilon$	$\Omega(d)$ only ( 1.4 a; its $e^{\rho}$ branch needs $d_{k}\gtrsim\rho^{3}$ )	$e^{\rho}/\varepsilon$ unmatched from below
scalar values; $d_{k}\gtrsim\rho^{3}$ or $d_{k}=\mathrm{polylog}\,n$	$e^{\rho}\min\{\sqrt{d_{k}\log(1+\rho)},\allowbreak F(d_{k},1)\}/\varepsilon$	$e^{\rho}/\varepsilon$ ( 1.4 a at $d_{v}=1$ ; 1.4 c)	whole $d_{k}$ factor
$\varepsilon\ll e^{-\rho}$ , $d_{k}=\Theta(\log^{a}n)$ , scalar	$\min\{n,\,e^{\rho}(1+\sqrt{d_{k}\log(1+\rho)})/\varepsilon\}$ , i.e. $n^{o(1)}/\varepsilon$	$(1/\varepsilon)^{1-1/a-o(1)}$ ( 1.4 c)	$(1/\varepsilon)^{1/a+o(1)}n^{o(1)}$
$\rho\to 0$	$\min\{n,\varepsilon^{-2},\ldots\}$	$\min\{d_{v},\varepsilon^{-2}\}$ ( 1.4 b)	none for $d_{v}\geq\varepsilon^{-2}$

Table 2: Lower-bound status under ( 4 ). The sampling branch

e^{2\rho}/\varepsilon^{2}

is unmatched from below except through the mean floor.

	median $\rho$		median $e^{\rho}$		fraction of heads		uncentred
Model	max	p99	max	p99	$e^{\rho}\leq 10^{3}$	$e^{\rho}\geq 10^{6}$	median $\rho$
Qwen2.5-7B-Instruct	54.015	50.575	$2.88\!\times\!10^{23}$	$9.22\!\times\!10^{21}$	0%	100%	69.719
Llama-3-8B-Instruct	49.442	48.733	$3.02\!\times\!10^{21}$	$1.46\!\times\!10^{21}$	0%	100%	54.960
	median $\rho$ by layer quintile, shallowest to deepest
Model	first	second	third	fourth	fifth
Qwen2.5-7B-Instruct	44.716	53.935	60.708	57.344	53.062

Table 3: E1. Centred

\rho

over all layers and key–value heads at 4k–32k tokens: 112 heads in 28 layers on Qwen (24,976 measurements) and 256 heads in 32 layers on Llama (54,272). The maximum and the 99th percentile are the two conventions for

\varrho

; the last column is the uncentred control

\max_{t}\lVert q_{t}\rVert\max_{i}\lVert k_{i}\rVert

in the maximum convention. Lower block: medians over the heads of each layer quintile, the quintiles being layers 0–4, 5–10, 11–15, 16–21, 22–27 on Qwen and 0–5, 6–11, 12–18, 19–24, 25–31 on Llama.

Figure 1: E1. (a) Centred

\rho

of every key–value head against its layer, one point per head (the median over prompts), with the median over the heads of each layer joined and the overall median dashed. (b) Empirical distribution of the per-head

\rho

on both models; the dashed lines mark

e^{\rho}=10^{3}

and

e^{\rho}=10^{6}

. (c) Median

\rho

against context length from 512 to 32768 tokens, with the band from the 10th to the 90th percentile over heads in each model’s colour; the corpus at each length is the set of documents that fill it.

Qwen2.5-7B-Instruct
	real decoding queries			sphere of radius $\varrho$
Method	$n/64$	$n/16$	$n/4$	$n/64$	$n/16$	$n/4$
Uniform sampling	0.550	0.490	0.291	1.038	0.981	0.919
BalanceKV	0.575	0.453	0.300	1.050	0.989	0.902
Kernel halving	0.578	0.454	0.291	1.049	0.991	0.889
Halving	0.573	0.449	0.311	1.053	0.996	0.897

Table 4: E2. Worst-case relative error at matched coreset size, lower is better. A cell is the median over the 28 (Qwen) or 25 (Llama) instances that are not near hard max and over 10 seeds, pooled; the last two rows of each panel, set off by a gap, are the query-aware references and are deterministic. The real column is the worst case over the model’s decoding queries and the sphere column over

10^{4}

queries of norm

\varrho

. Bold marks the two variants of the construction of this paper.

Figure 2: E2. Worst-case error on the real decoding queries relative to uniform sampling: for each kept instance, method and size, the method’s median over seeds divided by uniform sampling’s median over seeds, one point per instance, the whisker spanning the method’s range over seeds, and the bar the median over instances; uniform sampling’s own strip shows its range over seeds around one. Hollow markers are the two query-aware references, set off from the query-oblivious methods by a rule. Instances near hard max are excluded as in Table 4 .

Method	size	open	closed	closed/open	diverged	tracked	agreement
Qwen2.5-7B-Instruct
Uniform sampling	$n/16$	0.582	0.567	0.984	54 of 54	4	0.09
BalanceKV	$n/16$	0.645	0.634	1.006	54 of 54	4	0.08
Halving, re-centred subsample	$n/16$	0.651	0.680	0.993	54 of 54	4	0.07
Heavy hitters (oracle)	$n/16$	0.212	0.254	1.110	36 of 54	98	0.44
Uniform sampling	$n/4$	0.506	0.494	1.000	45 of 54	38	0.20

Table 5: E3. Worst-case relative error over the queries each loop issued, median over the 54 rows (prompt, head) of each size; the closed/open ratio is the median over the rows in which the closed loop diverged from the uncompressed model, counted in the “diverged” column. “Tracked” is the median number of decode steps before the closed loop first diverged and “agreement” the median fraction of the 256 generated tokens that agree with the uncompressed model. Above one the closed loop is worse.

		fitted slope of $\log(\text{size})$ against $\rho$ , and its range over seeds
Keys	Method	$d_{k}=2$	$d_{k}=8$	$d_{k}=64$
Sphere, $d_{v}=1$	Uniform sampling	0.54 [0.40, 0.60]	0.81 [0.76, 0.93]	0.57 [0.40, 0.72]
Sphere, $d_{v}=1$	Halving	0.58 [0.32, 0.86]	1.10 [0.98, 1.26]	1.03 [0.82, 1.22]
Sphere, $d_{v}=8$	Uniform sampling	0.34 [0.31, 0.38]	0.58 [0.54, 0.63]	0.27 [0.25, 0.27]
Sphere, $d_{v}=8$	Halving	0.41 [0.35, 0.45]	0.90 [0.86, 0.96]	0.66 [0.57, 0.75]
Clustered, $d_{v}=1$	Uniform sampling	0.42 [0.31, 0.59]	0.57 [0.45, 0.72]	0.44 [0.32, 0.73]

Table 6: E4. Scaling of the size needed to reach

\varepsilon=0.1

\rho

, fit over

\rho\in\{1,2,4\}

, median over 10 seeds with the range over seeds in brackets, for uniform sampling and Halving; all 60 fits are in Table 19 . Bold marks a slope within the pre-registered

1\pm 0.1

;

\dagger

as in Appendix E.5 .

Figure 3: E4. (a) Worst-case error against the requested coreset size at each

\rho

on the sphere with

d_{k}=64

d_{v}=8

, median over seeds, with the tolerance

\varepsilon=0.1

dashed and the 8192-pair cap dotted; the curves of the three capped methods end at

n/16

, the largest size below the cap. (b) Fitted size to reach

\varepsilon

against

\rho

for Halving and uniform sampling over the twelve (keys,

d_{k}

d_{v}

) configurations, with the range over seeds shaded; the dotted lines are the smallest and largest swept sizes and the largest size below the cap, which bounds the Halving fit. (c) The ratio of the two, by configuration, as in Table 7 ; the count below each

\rho

is the number of configurations whose ratio is defined.

	size to reach $\varepsilon$ : construction over uniform sampling
Configuration	$\rho=1$	$\rho=2$	$\rho=4$
Sphere, $d_{k}=2$ , $d_{v}=1$	0.11	0.13	0.15
Sphere, $d_{k}=2$ , $d_{v}=8$	0.19	0.21	0.24
Sphere, $d_{k}=8$ , $d_{v}=1$	0.14	0.21	0.33
Sphere, $d_{k}=8$ , $d_{v}=8$	0.25	0.43	0.73
Sphere, $d_{k}=64$ , $d_{v}=1$	0.26	0.43	1.02

Table 7: E4. Ratio of the fitted size at which Halving (Theorem 1.2 (a)) reaches

\varepsilon=0.1

to the size at which uniform sampling does, median over the seeds in which both crossings lie inside the sizes their fits used; a cell prints a dash when fewer than half the seeds qualify. Below one the construction needs the smaller coreset.

	query-oblivious signing at $q_{z}$			per-query greedy at $q_{z}$
$d_{k}$	bound $\rho\sqrt{r}/e$	$r\sinh(\rho/\sqrt{r})$	walk, best of 8 seeds	worst of 8 seeds
$256$	5.886	16.010	16.010	0.878
$1024$	11.772	32.005	32.005	0.813
$4096$	23.544	64.003	64.003	1.000

Table 8: The two inequalities of Proposition 1.5 on its instance at

\rho=1

. The walk’s signing must sit above the bound and the greedy below

e^{\rho}=2.718

. The third column is the value of the witness query for any balanced signing; the fourth reproduces it because the best seed’s signing is balanced.

	Rule, fixed in advance	Outcome
E1	If the median head satisfies $e^{\rho}(\sqrt{d_{v}}+\sqrt{d_{k}\log(1+\rho)})/\varepsilon\leq n$ at $\varepsilon=0.1$ , the discrepancy branch is meaningful and E2 proceeds on the median heads. If most heads have $e^{\rho}\geq 10^{6}$ , the results are reported as asymptotic, the abstract says so, and E2 runs on the low- $\rho$ tail.	Not meaningful at the median head on either model (yes/no: Qwen no, Llama no); $e^{\rho}\geq 10^{6}$ on 100% and 100% of heads. Reported as asymptotic, in the abstract. E2 was run on all terciles (Section 7.3 ).
E2	The construction should have lower worst-case error than uniform sampling at every size on every head, and the gap should widen with $\rho$ ; if it does not beat uniform sampling on the median heads, the constants of Section 4 dominate at these $n$ and the paper says so.	Not met: over all instances the construction beats uniform sampling in 273 of 540 cells on Qwen and 303 of 540 on Llama (both variants), and its halving variant in 64 of 140 and 76 of 125 after the near-hard-max exclusion; the ratio is flat across terciles. The constants dominate at these $n$ , and $e^{\rho}$ puts every bound above the cache.
E3	Per-query methods degrade faster in the closed loop than in the open loop, and the uniform-guarantee construction degrades equally in both; the modelling argument of Section 2 loses its support if the two are indistinguishable.	The two differ in the median closed/open ratio on both models over the rows in which the closed loop diverged, a cut chosen after the results, with the oracle as the only query-aware method run: its ratio there is 1.121 (Qwen) and 1.086 (Llama), and 1.000 and 1.047 over all rows; the re-centred variant’s is 1.000 and 1.000. Consistent with the argument, with the ceiling caveat of Section 7.4 .
E4	The size needed to reach $\varepsilon=0.1$ should scale as $e^{\rho}$ : a log-linear fit of slope $1\pm 0.1$ over $\rho\leq 4$ for every method.	Met in 5 of 60 fits, and by the construction in 2 of 12; the largest fitted slope is 1.10. Not met as stated.

Table 9: The decision rules of the plan and what the runs returned.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Run	GPU	hours
E1, Qwen	RTX 5090	0.4
E1, Llama	RTX 5090	0.6
E2, Qwen	RTX 3090	5.2
E2, Llama	RTX 3090	6.2
E3, Qwen	RTX 5090	0.4
E3, Llama	RTX 5090	0.4

Appendix

Table 10: Wall-clock time of the runs behind the tables.

	Change	Stage	Reason	Effect
1	E2 reports the two query populations as separate columns rather than one worst case over their union.	before run, after pilots not reported here	The sphere’s radius exceeds the real queries’ norms, so the union’s worst case was the sphere’s.	Rule read on the real column; sphere reported beside it.
2	E1 decomposes $\varrho$ over the query heads of a group.	before run	One query head could set $\rho$ for its group.	Table 12 ; no rule affected.
3	E1 reports $\kappa$ after trimming the furthest keys.	before run	The attention-sink explanation needed a test.	Table 12 ; negative.
4	The uncentred control is reported with the key-projection bias norms recorded per head.	before run	The uncentred radius tracks the bias where a bias exists.	One column of Table 3 .
5	The 8192-pair cap applies to every Gram–Schmidt or self-balancing walk, and the pairs seen are recorded per row.	before run	Otherwise matched output size at mismatched input size.	Kernel halving remains uncapped, in its favour; stated in Section 7.1 .
6	$\varrho$ is computed over decoding queries only, and the 99th percentile is undefined below 100 queries.	before run, after pilots not reported here	Two call sites disagreed on the population; a percentile of few queries copies the maximum.	Definitions of Appendix E.2 .

Appendix

Table 11: Every departure from the pre-registered plan.

	$\varrho$ within one query-head group			$\kappa$ after trimming
Model	largest head	smallest head	ratio	drop $4$	drop $32$
Qwen2.5-7B-Instruct	2.415	1.722	1.39	0.970	0.929
Llama-3-8B-Instruct	1.674	1.352	1.22	0.977	0.945

Appendix

Table 12: E1. Left:

\varrho

decomposed over the query heads that share one key–value head; each column is a median over heads, so the ratio is the median of per-head ratios. Right:

\kappa

after removing the four and the thirty-two keys furthest from the centroid, as a fraction of the untrimmed value, median over heads.

Model	context $n$	heads	prompts	median $\kappa$	median $\varrho$	median $\rho$
Qwen2.5-7B-Instruct	512	112	250	18.287	2.288	41.954
	1024	112	250	19.143	2.319	44.721
	2048	112	250	20.047	2.339	47.942
	4096	112	36	20.502	2.398	49.685
	8192	112	63	21.474	2.420	52.368
	16384	112	62	22.517	2.445	56.454

Appendix

Table 13: E1. Centred

\rho

and its two factors against context length. Each row is a separate census; rows are bucketed by the requested length, and the realised token count falls short of it by at most 8% on Qwen and 10% on Llama: the corpus admits a document that fills nine tenths of its bucket, and the Llama tokeniser counts fewer tokens than the Qwen tokeniser the corpus was bucketed with. The documents differ between lengths, since only long documents fill the long buckets; the fitted exponents are in Section 7.2 .

Qwen2.5-7B-Instruct
Head	$\rho$	participation ratio	$n$	top-1 mass	near hard max
L00H00	193.8	292.6	4096–32768	0.07	0 of 6
L00H03	37.9	586.4	4096–32768	0.02	0 of 6
L03H01	52.7	298.9	4096–32768	0.07	0 of 6
L07H01	48.9	3.9	4096–32768	0.70	6 of 6
L15H00	66.9	12.1	4096–32768	0.50	5 of 6

Appendix

Table 14: E2. Softmax concentration of each selected head at its decoding queries, one row per head with the median over its instances;

\rho

is the E2 value of the head,

n

the range of cache lengths, and the last column counts the instances that are near hard max (Appendix E.2 ) out of its six.

Qwen2.5-7B-Instruct
	real decoding queries			sphere of radius $\varrho$
Method	$n/64$	$n/16$	$n/4$	$n/64$	$n/16$	$n/4$
Uniform sampling	0.676	0.565	0.415	1.078	1.046	1.007
BalanceKV	0.707	0.624	0.401	1.079	1.053	0.984
Kernel halving	0.671	0.506	0.413	1.091	1.047	0.986
Halving	0.706	0.582	0.403	1.088	1.048	0.975

Appendix

Table 15: E2, worst seed. As Table 4 , but each instance contributes the largest error over its 10 seeds before the median over instances is taken.

	Qwen2.5-7B-Instruct		Llama-3-8B-Instruct
Method	size ratio	fewer keys	size ratio	fewer keys
BalanceKV	1.000	19%	1.000	15%
Kernel halving	1.000	21%	1.000	6%
Halving	1.000	25%	1.000	15%
Halving, re-centred subsample	1.000	24%	1.000	4%
Heavy hitters (oracle)	0.250	93%	0.250	96%

Appendix

Table 16: E2 read at matched error. For each instance and each swept size

T

, the smallest swept size at which the method reaches uniform sampling’s error at

T

on the real decoding queries, divided by

T

: “size ratio” is the median over (instance,

T

) and “fewer keys” the fraction of those cells in which the method needs strictly fewer keys. Cells at an instance’s smallest swept size are excluded, since no smaller size exists, and cells in which the method never reaches uniform sampling’s error are dropped. The size grid is geometric, so the ratio is quantised to powers of two and a median of exactly one means the same grid point. Population: 28 instances of 6 heads on Qwen and 25 of 9 on Llama, the near-hard-max instances excluded as in Table 4 .

Model	$\rho$ band	inst.	heads	rank	saturated	full	$A,B$	degen.
				pivoted Cholesky		off-diag. correlation
Qwen2.5-7B-Instruct	$[0,50)$	14	4	256.0	14/14	0.972	0.179	0
	$[50,100)$	28	7	256.0	28/28	0.962	0.039	0
	$[100,200)$	4	1	158.0	0/4	0.951	$3.20\!\times\!10^{-6}$	1
	$\geq 200$	8	2	133.5	0/8	0.967	$3.31\!\times\!10^{-11}$	5
Llama-3-8B-Instruct	$[0,50)$	28	7	256.0	28/28	0.962	0.094	0

Appendix

Table 17: The Gram matrix of Definition 4.1 on the E2 instances, by band of the instance’s

\rho

. “Rank” is the rank at which the matrix-free pivoted Cholesky met its relative stopping rule, capped at 256; “saturated” counts the instances that reached the cap, for which the recorded rank is only a lower bound on the true rank. The correlation columns give the largest off-diagonal entry of the correlation matrix over a sample of pairs, for the whole Gram matrix and for the numerator and denominator blocks alone; the cardinality block adds a constant to every entry of the former, so only the latter moves with

\rho

. “Degenerate” counts instances whose

A,B

blocks have no off-diagonal correlation above

10^{-8}

. Each band lists instances and distinct heads, since one head contributes up to six instances.

	Qwen2.5-7B-Instruct		Llama-3-8B-Instruct
Method	worst case	after divergence	worst case	after divergence
Uniform sampling	1.000	1.004	1.000	1.008
BalanceKV	1.000	1.005	1.000	1.005
Halving, re-centred subsample	1.000	1.010	1.000	1.001
Heavy hitters (oracle)	1.121	1.071	1.086	1.035

Appendix

Table 18: E3, pooled over both sizes and over the diverged rows. The first column of each pair is the ratio of worst-case errors of Table 5 ; the second is the ratio of the mean error over the steps from the first divergent token on; the step that produced that token still issues the same query in both loops, so one shared step is included.

Figure 4: E3. Median over the diverged rows of the attention error at each decode step, the error at a step being the largest over the query heads of the group; the open loop is the wide pale trace and the closed loop the thin dark one, for the heavy-hitter oracle and the re-centred variant of the construction, on both models at

n/16

and

n/4

, each panel on its own logarithmic scale. The legend of each panel gives the number of diverged rows behind each method’s pair of traces.

		fitted slope of $\log(\text{size})$ against $\rho$ , and its range over seeds
Keys	Method	$d_{k}=2$	$d_{k}=8$	$d_{k}=64$
Sphere, $d_{v}=1$	Uniform sampling	0.54 [0.40, 0.60]	0.81 [0.76, 0.93]	0.57 [0.40, 0.72]
	BalanceKV	0.48 [0.37, 0.59]	0.97 † [0.79, 1.19]	0.68 [0.44, 1.00]
	Kernel halving	0.42 [0.33, 0.53]	0.90 [0.83, 1.07]	0.58 [0.48, 0.81]
	Halving, re-centred subsample	0.64 [0.44, 0.84]	1.08 [0.91, 1.14]	0.98 [0.72, 1.15]
	Halving	0.58 [0.32, 0.86]	1.10 [0.98, 1.26]	1.03 [0.82, 1.22]

Appendix

Table 19: E4, all 60 fits. Bold marks a slope within the pre-registered

1\pm 0.1

(5 of 60);

\dagger

marks a fit resting on at least one crossing outside the sizes it was fitted over (8 fits, Appendix E.5 ); an excluded fit prints a dash.

	worst-case error at a coreset of 1024 of 65536 pairs
Method	$\rho=1$	$\rho=2$	$\rho=4$	$\rho=6$
Uniform sampling	0.031	0.040	0.058	0.074
BalanceKV	0.025	0.034	0.051	0.069
Kernel halving	0.024	0.035	0.053	0.068
Halving	0.011	0.018	0.026	0.038
Halving, re-centred subsample	0.011	0.016	0.024	0.038

Appendix

Table 20: E4 read at a fixed requested coreset size: median over the 10 seeds, both key families, all three

d_{k}

and both

d_{v}

. Lower is better.

Coreset Selection

Coreset selection chooses compact subsets that preserve a dataset’s learning, evaluation, or optimization value while reducing cost.

See all 59 papers

May 7, 2026

Nearly Optimal Attention Coresets

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)

\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^ρ/ε})

Edo Liberty, Alexandr Andoni, Eldar Kleiner

Softmax Attention Efficient Attention Coreset Selection Attention Approximation Memory-Efficient Attention

Ask PDF

Sep 29, 2026

Efficiently Approximating Attention Is Hard

Softmax attention is ubiquitous in modern machine learning, but its quadratic scaling with sequence length makes it costly. To reduce this cost, attention is often approximated with fast algorithms, which incur error but can still perform well in practice and on some inputs. At the same time, the growing diversity of attention applications makes approximation guarantees that do not depend on particular input structure a compelling target. For such uniform guarantees over all inputs, known runtime lower bounds rule out fast algorithms for near-exact attention, but leave open the practically important regime: is there an efficient algorithm with even a modest uniform approximation guarantee? We answer this question negatively. Under standard complexity-theoretic assumptions, no truly subquadratic algorithm can approximate attention with any nontrivial additive or relative guarantee uniformly over all inputs. This impossibility holds in the mildest parameter regime for which known algorithms do not already achieve strong approximation guarantees in near-linear time, and extends to practically relevant relaxations: even after polynomial preprocessing of the KV cache, no efficient algorithm can obtain a nontrivial uniform approximation guarantee, or identify a small set of keys receiving substantial attention under sparsity. Overall, our results settle the computational limits of uniform attention approximation.

Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno +2

Institute for Data Science in Mechanical Engineering, RWTH Aachen University · Autonomous Systems Lab, Stanford University

Attention Approximation Efficient Attention Softmax Attention Sparse Attention

Ask PDF

Oct 7, 2026

Attention via Black-Box Vector Search

Sparse attention mechanisms estimate attention over

n

tokens using a small subset of keys. Many existing approaches use maximum inner product search (MIPS) to retrieve the heaviest keys, which motivates the following question: given black-box access to a MIPS oracle, how many keys must be retrieved to output an

\varepsilon

-accurate attention estimate? We answer this question by unifying prior approaches through the framework of priority sampling. With a single MIPS index, we show that

Θ(\sqrt{n}/\varepsilon)

retrieved keys are both sufficient and necessary. With

Θ(\log n)

indices, we give an algorithm that retrieves only

O(\log n+1/\varepsilon^2)

keys and prove that this is near-optimal. More generally, we design algorithms that establish a smooth tradeoff between the number of MIPS indices and number of retrieved keys. We then show that if we allow augmentation of keys and queries, we can bypass the above lower bounds: there exists a simple priority-sampling estimator using a single MIPS index and

O(1/\varepsilon^2)

retrieved keys. When integrated into LLM inference, our algorithms outperform top-

k

and sampling approaches used in prior work and yield attention approximation that scales favorably to long contexts.

Stepan Zharkov, Krish Singal, Ashwin Padaki +1

University of Pennsylvania

Attention Approximation Efficient Attention Sparse Attention LLM Inference Efficiency

Ask PDF

Abstract

Coreset Selection

Explore similar work

Nearly Optimal Attention Coresets

Efficiently Approximating Attention Is Hard

Attention via Black-Box Vector Search