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

arXiv:2609.06327v2 Announce Type: replace-cross Abstract: A query-oblivious coreset for a softmax-attention head is a subset of the key-value pairs whose attention output is within arepsilon of the full one for every query in a ball. Liberty, Andoni and Kleiner proved that unweighted coresets of size O(sqrt d e^{rho+frac12logrho+o(loglogrho)}/arepsilon) exist, rho the query radius times the centred key radius, against a lower bound Omega(sqrt d e^{rho}/arepsilon), 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^{rho}(sqrt{d_v}+sqrt{d_klog(1+rho)})/arepsilon) in randomised polynomial time, the first constructive whole-ball guarantee within sqrt{log(1+rho)} of the lower bound. A sampling cap O(e^{2rho}/arepsilon^{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 rho at least 23.877, so everyactor e^{rho}/arepsilonprescribes a coreset larger than the cache: the algorithmic contribution is asymptotic on these models.

Related

• Uncertainty-gated selection for block-sparse attention
• MTraining: Distributed Dynamic Sparse Attention for Efficient Ultra-Long Context Training
• Trust the Mass: Forced Weights in KV-Cache Eviction
• LongCat Sparse Attention: Taming the Lightning via Streaming-aware Hierarchical Cross-Layer Indexing

Source: arXiv cs.CL | 2026-09-15