Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention
Not on the map. Why?
Abstract (arXiv)
How much matrix rank is required to preserve every bounded value output of normalized softmax attention? We study the unrestricted maximum-row-(ℓ1) approximation rank (r_varepsilon(A)), exactly the least rank achieving uniform error over all bounded vector-valued values. Row softmax exposes the intrinsic interaction (C=Pm(log A)PN), whereas invertible (Q/K) gauges leave (A) fixed while changing the Euclidean geometry of a chosen query/key factorization. We replace that coordinate-dependent description by a projective residual (q(C-T)) and an attained factor-radius size (kappa(T)). For every rank-(r) retained interaction with (τ(T)<varepsilon), we prove r_varepsilon(A)≤ minleft N,; Crleft( 1+frackappa(T) (varepsilon-τ(T))2 right)r/2 right, with the same unknown dimension constant as the underlying weighted Gibbs-row cover. The profile is gauge invariant, termwise no worse than native retained-subspace bounds at the same declared dimension, and has a worst-case sharp (r/2) size exponent at fixed (r) and (varepsilon). We then measure (r_varepsilon(A)) directly on learned attention using 9,978 certified brackets across BERT, GPT-2, Qwen2.5, and two ViT checkpoints; where certificates do not close, the optimum remains interval-valued. A pre-specified 2,302-cell held-out study further shows that the historical native-coordinate geometry block contains coarse, mostly head-level information but no detectable incremental information beyond a strong calibrated baseline. The new intrinsic descriptor is not evaluated in that study. Together, the theory and measurements distinguish an operator-intrinsic complexity control from a stronger empirical explanation that the learned-head evidence does not support.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 13 of its 17 references that are in the map. First posted on arXiv 28 Aug 2026.
Builds on
13 of 17 references.
References · 13
- 2020Rethinking Attention with Performerscited by 1,584
- 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
- 2021Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attentioncited by 468
- 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 128
- 2014Factorization Norms and Hereditary Discrepancycited by 14
- 2024Dissecting Query-Key Interaction in Vision Transformerscited by 12
- 2025Low-Rank Thinningcited by 7
- 2021Kernel approximation on algebraic varietiescited by 4
- 2026Nearly Optimal Attention Coresetscited by 4
- 2024When big data actually are low-rank, or entrywise approximation of certain function-generated matricescited by 3
- 2026On the Invariants of Softmax Attentioncited by 3
- 2025Degrees of Freedom for Linear Attention: Distilling Softmax Attention with Optimal Feature Efficiencycited by 2
1 more
Built on by
Citing papers per year: 2026: 1.
1 paper.