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

arXiv: https://arxiv.org/abs/2609.06327 · HTML: https://mlsanity.com/paper/2609.06327/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 39 references that are in the map.
- First posted on arXiv 6 Sep 2026.

## Builds on (most cited first, 24 of 24)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [A Dataset of Information-Seeking Questions and Answers Anchored in Research Papers](https://mlsanity.com/paper/2105.03011/) (2021)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Discrepancy Minimization via a Self-Balancing Walk](https://mlsanity.com/paper/2006.14009/) (2020)
- [SubGen: Token Generation in Sublinear Time and Memory](https://mlsanity.com/paper/2402.06082/) (2024)
- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues](https://mlsanity.com/paper/1708.01079/) (2017)
- [Spectral norm of random tensors](https://mlsanity.com/paper/1407.1870/) (2014)
- [Optimal Coreset for Gaussian Kernel Density Estimation](https://mlsanity.com/paper/2007.08031/) (2020)
- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations](https://mlsanity.com/paper/2401.02562/) (2024)
- [Compression Barriers for Autoregressive Transformers](https://mlsanity.com/paper/2502.15955/) (2025)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [The risk of KV cache compression](https://mlsanity.com/paper/2607.01520/) (2026)
- [Token Sample Complexity of Attention](https://mlsanity.com/paper/2512.10656/) (2025)
- [How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers](https://mlsanity.com/paper/2604.17935/) (2026)
- [Towards Tight Bounds for Streaming Attention](https://mlsanity.com/paper/2606.07205/) (2026)
- [Stronger Coreset Bounds for Kernel Density Estimators via Chaining](https://mlsanity.com/paper/2310.08548/) (2023)
- [Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention](https://mlsanity.com/paper/2608.28150/) (2026)

## Abstract (arXiv)

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(√ d eρ+frac12logρ+o(loglogρ)/varepsilon) exist, ρ the query radius times the centred key radius, against a lower bound Omega(√ 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ρ(√dv+√dklog(1+ρ))/varepsilon) in randomised polynomial time, the first constructive whole-ball guarantee within √log(1+ρ) of the lower bound. A sampling cap O(e2ρ/varepsilon2) 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ρ/varepsilonprescribes a coreset larger than the cache: the algorithmic contribution is asymptotic on these models.