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

1.1 Results

• The upper envelope combines a chaining-based branch, a sampling branch capped at O(e^(2ρ)/ε^2), and a fixed-dimension branch.The first branch uses a two-slack spherical lift, Chevet’s inequality to split key and value dimensions, and a denominator constraint propagated through recursion.Source: §1.1 · pp. 2–3
• Theorem 1.2 gives the first polynomial-time construction with one signing uniform over the query ball, at the existential size up to a log(1 + ρ) factor.Earlier per-query walks become uniform through a net at polylogarithmic cost and with e^(2ρ) in place of e^ρ.Source: §1 · p. 2, §1.1 · p. 3
• For fixed dk, Theorem 1.3 gives a finite-dimensional bound and rules out a matching large-ρ obstruction, but its constant may be exponential in dk.The theorem says nothing about dimension growing with ρ.Source: §1.1 · p. 3
• The transferred lower bounds include Ω(e^ρ√dv/ε) under stated parameter conditions, with the construction centered to fit the normalized setting.The transfer of Chen et al.’s streaming bounds uses the fact that a coreset is a data structure whose bit length can answer the query.Source: §1.1 · p. 3
• At ρ = 1, one signing for the whole ball costs Ω(√dk), whereas a fixed scalar-valued query has a coreset of size at most 24e^ρ/ε + 3.The paper frames this as the dimension price of query-obliviousness.Source: §1.1 · p. 4
• At 4k–32k tokens, median ρ is 54.015 for Qwen and 49.442 for Llama, making every whole-ball bound carrying e^ρ/ε larger than the cache.On measured real heads, the construction matches uniform sampling rather than beating it.Source: §1.1 · p. 4

1.2 What is inherited and what is new

• The fixed-dimension upper bound loses the logarithm, but the value-direction lower-bound floor requires dk ≳ ρ^3, and no lower bound of order e^ρ/ε is proved there.For scalar values, the dimensional-factor gap remains unmatched from below.Source: §1.2 · p. 4

1.3 Related work

• BalanceKV [22] and Chen et al. [11] give per-query guarantees, Haverbeck et al. [20] analyze averaged risk, and Liberty–Andoni–Kleiner [25] give existential uniform-ball bounds.The paper distinguishes these from guarantees for queries observed in advance and notes that a separate combinatorial cache separation is not comparable.Source: §1.3 · p. 6

2 Why one signing for the whole ball

• A fixed-in-advance query guarantee does not control successive decoding queries that depend on attention outputs produced from the compressed cache.The paper presents this as a modelling argument, not a theorem.Source: §2 · p. 6
• For one fixed query, a deterministic polynomial-time coreset has size at most 24e^rho/ε + 3 for scalar values.The guarantee is for that query, not uniformly over the query ball.Source: §2 · p. 7
• Whether query-oblivious coresets for scalar values require any key-dimension factor remains open.The local INDEX architecture cannot settle the question; its bound is at most e^rho√dv/ε.Source: §2 · p. 7

3.1 Two reductions

• The two-slack lift maps keys and queries from their balls to a sphere while preserving their inner-product relation exactly.The section uses kernel-discrepancy bounds on the lifted points and separates key- and value-dimension contributions through Chevet’s inequality.Source: §3.1 · pp. 7–8

3.2 The reduction to a coreset

• A balanced signing halves the set while controlling numerator, denominator, and cardinality; propagating the denominator bound through recursion yields an ε-coreset.The recursive error bound sums across levels, avoiding the prior side conditions and accumulating key-mean constraint.Source: §3.2 · p. 8

3.3 The sampling branch

• Sampling gives a coreset size cap of min{n, ⌈32e^(2rho)/ε^2⌉}, with a random subset of size min{n, ⌈128e^(2rho)/ε^2⌉} succeeding with probability at least 3/4.The ε^-2 dependence is a phase transition, as the mean at q = 0 demonstrates.Source: §3.3 · p. 9

4 Polynomial time

• Each algorithm level forms a Gram matrix, factors it by pivoted Cholesky, and runs the Gram–Schmidt walk on its rows.A signing is accepted when the checkable constraints pass; each trial is accepted with probability at least one half.Source: §4 · p. 9
• The recursive construction’s coreset size is less than 8D̄/ε + 4σGS.The level errors are bounded in expectation and summed across the recursion; a union bound controls the level suprema with logarithmic dependence on log n.Source: §4 · p. 10
• The sampling-and-balance variant draws a random subset, recentres and rescales it, then runs the recursive algorithm; its stated expected runtime includes O(ndk) preprocessing.The sampling check enforces a bound on the sampled key mean; the construction’s result is probabilistic.Source: §4 · p. 10
• The sampling stage improves the recursive bound only when 2048e^(2rho)/ε^2 < n; at ε = 0.1, the stated threshold is n > 2·10^5e^(2rho).The paper reports that this stage draws its whole input on every instance in Section 7.Source: §4 · p. 10

5 Fixed dimension: the logarithm disappears

• Completing the key ball to a sphere makes the exponential-kernel identity applicable uniformly over the query ball.The identity itself is known; the contribution is completing the ball so the key points lie on one sphere and the weighted factors become uniform.Source: §5 · p. 11
• Tai’s diameter-free Gaussian-kernel discrepancy bound yields an expected-polynomial-time fixed-dimension coreset of size min{n, 8Fe^rho/ε + 1}.Here F = 7√dv e^(dv/4)(fT(dk + 1 + 2dv) + 1), with fT the diameter-free discrepancy constant.Source: §5 · p. 11
• The construction settles the Gaussian-restriction case of the Bozzai–Rothvoss question, but does not resolve it for Laplacian or Jensen–Shannon kernels or determine fT’s growth.The paper states that F is exponential in dv and, as far as is known, in dk.Source: §5 · pp. 11–12

• At q = 0, the spherical-code construction gives a small-radius floor min{d_v, ε^-2}, and weighted subsets face the same floor.The paper contrasts this with a lookup instance where two weighted atoms reproduce attention at q = 0 and one further query [20].Source: §6 · p. 12
• S ≥~Ω(min{n, (1/ε)^{1−1/a−o(1)}}) when d = Θ(log^a n), a > 2, and n^-100 < ε < n^-c.Source: §6 · p. 12
• S ≥~Ω(min{n, e^{r²(1−o(1))}/ε}) when Ω(log n) ≤ r² < 1 and d = (log n)^{1+Ω(1)}, for keys on the radius-r sphere and queries equal to keys.Source: §6 · p. 13
• Rescaling keys and queries, translating keys by their mean, and normalizing by the centred radius preserve attention and yield ρ = Θ(r²) in regime (a) and ρ = r²(1+o(1)) in regime (b).Source: §6 · p. 13
• The [11] reduction encodes INDEX bits as values and sends coreset indices and bits in O(s log m) bits, yielding s ≥ Ω(m/log m).The keys are public random points and Bob evaluates the coreset at a public-key query.Source: §6 · pp. 12–13
• The transferred regime-(b) bound has the e^ρ/ε shape at d_v = 1, while extending the lower-bound floors across value coordinates or obtaining a d_k factor remains open.Regime (a)'s transferred bound is polynomial in 1/ε; its comparison to the upper bound is limited by losses and parameter conditions.Source: §6 · p. 13

7.1 Setup

• The experiments measured Qwen2.5-7B-Instruct and Llama-3-8B-Instruct on natural and random-token prompts, using worst-case relative attention error over decoding queries or 104 sampled sphere queries.E2 excluded near-hard-max instances; it retained 28 Qwen and 25 Llama instances, and capped walk inputs at 8,192 pairs.Source: §7.1 · pp. 14–15, §7.3 · p. 17

7.2 E1: the census of centred ρ

• At median heads, ρ was 54.015 on Qwen and 49.442 on Llama, with e^ρ = 2.88×10^23 and 3.02×10^21; all heads had e^ρ ≥ 10^6.At ε = 0.1, the sampling branch was below cache size on 0% of heads in either model.Source: §7.2 · pp. 15–16, Table 3 · p. 15
• At 512 tokens, the smallest observed ρ across heads was 24.100 on Qwen and 23.877 on Llama; fitted context-length exponents were 0.073 ± 0.006 and 0.130 ± 0.025.The fit spans seven lengths, but the corpus changes with length, so the authors do not extrapolate the trend.Source: §7.2 · p. 17

7.3 E2: constructions at matched size

• Construction-to-uniform median error ratios were 1.002 on Qwen and 0.990 on Llama, with 80% of cells within 0.917–1.081 and 0.871–1.086, respectively.The five query-oblivious methods were within 0.05 of one another at every size; no query-oblivious method needed fewer keys than uniform sampling in more than 25% of Qwen cells or 15% of Llama cells at matched error.Source: §7.3 · pp. 17, 19, Table 4 · p. 18, Figure 2 · p. 18
• On sphere queries at n/64, uniform sampling’s worst-case error was 1.038 on Qwen and 0.794 on Llama; at n/4 it was 0.919 and 0.667.Every query-oblivious method was within 0.03 of uniform sampling at every size, and the oracle was above it at all three reported sizes; the 104 sampled directions give only a lower bound on the ball supremum.Source: Table 4 · p. 18, §7.3 · p. 19

7.4 E3: closed-loop decoding

• On diverged decoding rows, the oracle’s closed/open error ratio was 1.121 on Qwen and 1.086 on Llama, while each query-oblivious method’s ratio was 1.000 on both models.The oracle degraded while the query-oblivious methods did not, but the result is not a strong test of the modelling argument because query-oblivious rows had a ceiling effect and the experiment does not isolate query fitting from guarantee type.Source: §7.4 · pp. 20–21, Table 5 · p. 21

7.5 E4: scaling on synthetic instances

• The pre-registered slope check of 1 ± 0.1 was met in only 5 of 60 synthetic fits, including 2 of 12 construction configurations.Both construction variants had higher slopes than every baseline in 12/12 configurations, but the sweep neither contradicts nor establishes the bound’s rate in ρ.Source: §7.5 · p. 22, Table 6 · p. 22
• At ρ = 1, 2, and 4, the construction used smaller fitted coresets than uniform sampling in 11/11, 12/12, and 11/12 configurations, with median size ratios 0.19, 0.21, and 0.31.These crossings are based on worst error over 2,000 queries, a lower bound on the ball supremum, so they do not establish the whole-ball guarantee or its rate in ρ.Source: §7.5 · p. 22, Figure 3 · p. 23, Table 7 · p. 24
• At ρ=1, the witness-query tests satisfy the walk and greedy inequalities at dk ∈{256, 1024, 4096}.For balanced walk signings, the witness value is r sinh(ρ/√r); the factor e in the bound is slack, and the witness value is only a lower bound on the supremum over the ball.Source: §7.5 · p. 25

7.6 The pre-registered rules and their outcomes

• The plan’s first two rules’ consequences were applied, but its third-rule consequence about uniform guarantees in a decoding loop does not apply.The abstract states that the algorithmic contribution is asymptotic on the measured models, Section 7.3 states constants dominate at these n, and analyses outside the plan are listed in Appendix F.Source: §7.6 · pp. 25–26, Table 9 · p. 25

7.7 What the experiments establish

• ρ is at least 23.877 on every measured head, making every e^ρ whole-ball bound larger than the cache it compresses.The measurement covers every key–value head of two instruction-tuned models at context lengths from 512 to 32768 tokens; ρ reaches 562.5 at the largest head at 4k–32k tokens, with medians of 54 and 49 there. It grows as n^0.073 and n^0.130 over a corpus that changes with context length, and is a bulk property of the key cloud; all bounds use the centred convention.Source: §7.7 · p. 26
• At matched size, the five query-oblivious rows of Table 4 lie within five hundredths of one another at every size.At matched error, none needs fewer keys in more than 25% of cells on Qwen and 15% on Llama; the heavy-hitter oracle has lower error in every real-query cell, from 0.362 against 0.550 at n/64 on Qwen to 0.011 against 0.237 at n/4 on Llama.Source: §7.7 · p. 26
• At ρ ≤4, the construction needs 3.2 to 5.3 times fewer pairs than uniform sampling at the median synthetic configuration.The sweep neither contradicts nor establishes the rate of Theorem 1.2(a); the closed-loop experiment is consistent with Section 2’s modelling argument but is weak for the reason stated there.Source: §7.7 · p. 26

8 Conclusion

• The Liberty–Andoni–Kleiner gap is attributed to its width input; two reductions narrow it to log(1 + ρ) against the value-direction floor.Tai’s theorem removes the logarithm in fixed dimension.Source: §8 · p. 26
• The fixed-dimension branch depends on Tai’s dimension-dependent constant, exponential in d_v and, as far as known, d_k; the construction succeeds with constant probability.The paper proves no general lower bound of order e^ρ/ε against that branch.Source: §8 · p. 26
• At 4k–32k tokens, median ρ is near 54 and 49, and every whole-ball bound carrying e^ρ/ε exceeds the cache size on the measured models.The smallest ρ at 512 tokens is 23.877; the construction matches uniform sampling on real heads.Source: §8 · p. 26
• Two unpursued routes are guarantees over realised queries, which forfeit ball-uniformity, and tighter-key-geometry architectures, none measured.Source: §8 · p. 27

A Tools

• The Gram–Schmidt walk produces a randomized signing whose signed sum has zero mean and controlled second and subgaussian moments.Source: A Tools · p. 27
• Dudley’s inequality applies to processes with subgaussian increments; centered Gaussian processes have such increments in the Euclidean metric.Source: A Tools · p. 27
• Borell–TIS bounds the upper tail of the supremum of a centered, almost surely bounded Gaussian process.Source: A Tools · p. 27
• For 0 < η ≤ 1, sphere and ball covering numbers are at most (3/η)^d, while spherical-cap tails are bounded by 2e^(−dt²/2).Source: A Tools · p. 27
• In one-way INDEX with public randomness and error δ ≤ 1/2, communicating the N-bit input requires at least (1 − h(δ))N bits.The proof uses Fano’s inequality and concavity of binary entropy.Source: A Tools · p. 27

B Proof of the first branch of Theorem 1.1

• The test-set entropy bounds separate value and key dimensions: Dudley complexity is controlled by e^ρ(√d_v + √(d_k log(1 + ρ))).The value sphere contributes the √d_v term, while the key feature set contributes the √(d_k log(1 + ρ)) term.Source: B Proof of the first branch of Theorem… · pp. 28–29
• Three independent Gaussian blocks enforce the attention numerator, denominator, and signing-count constraints simultaneously with positive probability.The product body has Gaussian measure at least 0.512 before intersection with a finite-radius ball.Source: B Proof of the first branch of Theorem… · p. 29
• Truncating the exponential feature map at M = ⌈max{2eρ, log2(2n)}⌉ limits the kernel-sum error while keeping the feature representation finite-dimensional.The truncation error is bounded by m·2^-M, and the proof absorbs the resulting error into its thresholds.Source: B Proof of the first branch of Theorem… · pp. 27–29
• A sign vector satisfying the test-set bounds controls all query and value-direction read-offs, which the iterative construction uses to preserve denominators and accumulate at most ε error.The denominator lower bound is maintained at each level, yielding the uniform error bound over the query ball.Source: B Proof of the first branch of Theorem… · p. 29
• The final subset has uniform query error at most ε and size below 4D/ε + DN, with D bounded by a constant times e^ρ(√d_v + √(d_k log(1 + ρ))).The construction stops at the largest level ℓ with 2^(ℓ+1)D ≤ εn; its size bound follows from maximality.Source: B Proof of the first branch of Theorem… · p. 29

C Proofs for Section 4

• A Gram-matrix factorization gives an isometry that preserves all signing read-offs while projecting test vectors onto the span of the data vectors.The projection does not increase the test-vector norm.Source: C Proofs for Section 4 · p. 29
• The signing process is subgaussian on the test sets, so Dudley bounds its expected supremum and a tail bound controls the levelwise deviations.The process has mean zero and increment scale K* times the test-set distance.Source: C Proofs for Section 4 · p. 30
• The expected-time analysis runs each level using costs O(m²(d_k + d_v)) + O(m³) plus an expected two walks costing O(m(2m)^ω).The level size is bounded in terms of n/2^j and D′.Source: C Proofs for Section 4 · p. 30
• The high-probability construction chooses a computable stopping threshold D* and achieves error at most ε with size below 4D*/ε + D′.The per-level tail bounds hold jointly with probability at least 1 − δ/2.Source: C Proofs for Section 4 · p. 30

D Proof of Theorem 1.4(a)

• The reduction encodes a binary matrix in paired keys and values, then uses an ε-coreset to let Bob decode a selected matrix bit from an attention query.The construction uses N′ = 2md_v pairs and has zero key centroid, unit-norm keys, and values of norm at most one.Source: D Proof of Theorem 1.4(a) · p. 31
• The communication count contradicts the INDEX lower bound when the coreset is too small, establishing the claimed size lower bound.The proof compares at most 0.256N + O(log N) transmitted bits with a requirement exceeding 0.278N bits.Source: D Proof of Theorem 1.4(a) · p. 31
• Every ε-coreset can require Ω(d_v min{e^ρ/(ε√d_v), e^(2ρ), e d_k/(4ρ²)}) pairs.The argument first obtains a linear lower bound in d_v times the minimum of these three terms.Source: D Proof of Theorem 1.4(a) · pp. 30–31
• The √d_v factor comes from multiplexing independent bits over output coordinates; the one-bit-per-token architecture does not yield a key-dimension factor.At a single query, the signal from one token is capped at e^ρ√d_v/ε; breaking that cap requires side information, as in [11].Source: D Proof of Theorem 1.4(a) · pp. 31–32

E.1 Corpus and capture

• The corpus combines 250 natural documents across four token-length buckets with 50 random-token controls, interleaved so prefixes preserve their proportions.Documents are drawn from nine LongBench subsets and QASPER; models skip prompts that fail their tokenizer-based length criteria.Source: §E.1 · p. 32
• Forward hooks capture projected keys, values, and queries after prefill; rotary embeddings and query scaling are applied so captured q⊤k matches the model’s attention logit.Nine heads per model are sampled across 6 leading prompts, with 128 decoding queries per prompt for the stated dumps.Source: §E.1 · p. 32

E.2 Definitions

• The reported ρ is the product of centered key radius κ and query radius ϱ, with ϱ computed under maximum or 99th-percentile conventions over specified decoding queries.The maximum convention depends on the query set, so the same head can have different ρ values across E1 and E2.Source: §E.2 · p. 32
• Attention error is the output-vector difference divided by the maximum value-vector norm; participation ratio measures the effective number of attended keys.An instance is designated near hard max when its mean decoding-query participation ratio is at most 16.Source: §E.2 · p. 32

E.3 Methods and provenance

• The construction normalises instances, builds four-block Gram features, signs pivoted-Cholesky factors with the Gram–Schmidt walk, and recursively keeps the larger sign class.The factorisation rank is capped at 256; BalanceKV and kernel halving are reimplementations with different blocks and procedures, while heavy hitters and per-query are reference methods.Source: §E.3 · p. 33

E.4 Closed-loop protocol

• Closed-loop decoding compares errors when masked-model queries follow reference tokens versus when the compressed-cache model generates its own tokens.The protocol tracks token agreement and the leading shared prefix over 256 generated tokens; masking a position reproduces attention from a shrunken cache.Source: §E.4 · p. 34

E.5 Synthetic instances

• Synthetic instances vary key and value dimensions, key families, and query radius, measuring worst error across 2,000 queries and fitting the size needed to reach ε = 0.1.The sweep uses ten seeds per instance and excludes certain off-range or low-variation fits under specified rules.Source: §E.5 · p. 34

E.6 Hardware, run times and seeds

• Runs used RTX 5090 and RTX 3090 GPUs, with CPU walks; the stated seeds span ten E2 seeds, ten per E4 instance, and eight separation runs.The paper assigns numerical majorants to three proof constants but does not assign a value to Tai’s constant.Source: §E.6 · pp. 34–35, Table 10 · p. 35

F.1 The archived plan

• The archived plan set experiments and decision rules in advance, including whether observed ρ makes bounds meaningful, whether the construction beats uniform sampling, and how open- and closed-loop degradation compares.The plan specifies reporting an asymptotic contribution if most heads have e^ρ ≥ 10^6 and says a failure to beat uniform sampling would make the algorithmic claim theoretical rather than practical.Source: §F.1 · pp. 35–36

F.2 Departures from the plan

• No thresholds or decision rules changed, but some populations, rows, and estimators changed after results were seen; the pre-registered readings or outcomes are also reported.The table records when each change occurred, from before the affected run through reporting.Source: §F.2 · p. 37, Table 11 · p. 37
• The E3 analysis adds ratios over diverged rows and mean error from the first divergent token, while the pre-registered hypothesis had no margin.A proposed ratio conditioned on the shared prefix was not adopted because it is identically one.Source: §F.2 · p. 38

Appendix E.4.

• The E4 crossing uses a fit over swept sizes rather than the smallest size reaching ε, because the original grid’s floor already met ε in almost every group.The fit excludes capped-method rows at n/8 and n/4; fitting all thirteen sizes instead yields higher construction slopes and larger ratios and is not reported.Source: §F.2 · p. 38, Appendix E.4 · p. 39

F.2 Departures from the plan

• The separation run used only the Gram–Schmidt walk, and its witness value is a lower bound on the supremum, so the two inequalities are reported separately rather than as a ratio.E4 also omits query-aware reference methods, and the E2 mean error is not reported.Source: §F.2 · p. 38
• The E2 sizes n/32 and n/8 are not tabulated.The stated reason is table width.Source: §F.2 · p. 38

G Additional tables and figures

• Tables 12–14 describe query-radius and key-radius profiles, centred ρ and its factors by context length, and softmax concentration for selected heads.Table 13 notes that documents differ across length buckets and gives the fitted exponents in Section 7.2.Source: Table 12 · p. 39, Table 13 · p. 39, Table 14 · p. 40
• Tables 15–17 report worst-seed E2 errors, matched-error size ratios, and Gram-matrix rank, correlation, and degeneracy summaries.Table 17 counts rank saturation and instances whose numerator and denominator blocks lack off-diagonal correlation above 10^-8.Source: Table 15 · p. 40, Table 16 · p. 41, Table 17 · p. 41
• Table 18 summarizes E3 error ratios over diverged rows, while Figure 4 plots median per-step attention error for open and closed loops across methods, models, and sizes.Figure 4 uses a separate logarithmic scale in each panel; its legend gives the diverged-row count behind each method’s traces.Source: Table 18 · p. 41, Figure 4 · p. 42
• Table 19 reports all 60 E4 fits: 5 slopes fall within the pre-registered 1 ± 0.1 band, 8 fits carry an extrapolation marker, and excluded fits show dashes.Table 20 gives E4 error at fixed requested coreset size, with lower values better.Source: Table 19 · p. 43, Table 20 · p. 43