analiza aiqbench
This is a theoretical paper on the memory cost of approximating transformer attention, which is relevant to KV-cache compression for long-context inference. It shows that assuming realistic key/query geometry (cosine similarities bounded near zero) allows near-optimal space bounds, and that simple uniform sampling is nearly optimal in a typical parameter range. Readers should treat it as a formal result under a stated assumption, not an immediate practical method, though it offers some theoretical support for why simple sampling works on real models.
Attention under Bounded Key-Query Similarity: Space Complexity and Transformer Anisotropy
arXiv:2610.35020v1 Announce Type: new Abstract: A growing body of work on KV-cache compression aims to reduce the memory requirements of autoregressive generation. These methods compress the stored context while approximately preserving attention computation, enabling generation with reduced memory consumption. Almost tight theoretical results on the worst case space complexity of attention have recently been obtained, but they are achieved by instances where queries can be perfectly aligned with keys. This directly contradicts the observed anisotropy of the key/query geometry in real transformers. In particular, it has been shown empirically that key/query cosine similarities are small even for most correlated pairs, i.e., near-perfect alignment of queries with keys does not happen in practice. In this paper, we study the space complexity of attention approximation under the assumption that key/query cosine similarities belong to a small interval around zero, i.e., a query cannot align too much with any key. We give a nearly space optimal algorithm and a corresponding space lower bound. Surprisingly, the distribution of key/query cosine similarities in our lower bound exhibits the anisotropy property empirically established and studied in the literature. Additionally, we show that the simple uniform sampling algorithm is nearly optimal for a typical range of parameters, supporting its surprising effectiveness on real datasets.
Abstract:A growing body of work on KV-cache compression aims to reduce the memory requirements of autoregressive generation. These methods compress the stored context while approximately preserving attention computation, enabling generation with reduced memory consumption. Almost tight theoretical results on the worst case space complexity of attention have recently been obtained, but they are achieved by instances where queries can be perfectly aligned with keys. This directly contradicts the observed anisotropy of the key/query geometry in real transformers. In particular, it has been shown empirically that key/query cosine similarities are small even for most correlated pairs, i.e., near-perfect alignment of queries with keys does not happen in practice. In this paper, we study the space complexity of attention approximation under the assumption that key/query cosine similarities belong to a small interval around zero, i.e., a query cannot align too much with any key. We give a nearly space optimal algorithm and a corresponding space lower bound. Surprisingly, the distribution of key/query cosine similarities in our lower bound exhibits the anisotropy property empirically established and studied in the literature. Additionally, we show that the simple uniform sampling algorithm is nearly optimal for a typical range of parameters, supporting its surprising effectiveness on real datasets.
Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS)
arXiv:2610.35020 [cs.LG]
(or arXiv:2610.35020v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.35020 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 301 cuvinte
Subiecte conexe
Effective quasiparticle conserving Lindbladians in the thermodynamic limit
arXiv · 3 sept. 2026
Coupled cluster theory for multireference and open-shell molecules
arXiv · 7 oct. 2026
Toward Learning POMDPs Beyond Full-Rank Actions and State Observability
arXiv · 23 iul. 2026
$T$-efficient unitary synthesis via block-sparse Hamiltonian simulation
arXiv · 14 oct. 2026