# Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 17 references that are in the map.
- First posted on arXiv 28 Aug 2026.

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

- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Factorization Norms and Hereditary Discrepancy](https://mlsanity.com/paper/1408.1376/) (2014)
- [Dissecting Query-Key Interaction in Vision Transformers](https://mlsanity.com/paper/2405.14880/) (2024)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)
- [Kernel approximation on algebraic varieties](https://mlsanity.com/paper/2106.02755/) (2021)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [When big data actually are low-rank, or entrywise approximation of certain function-generated matrices](https://mlsanity.com/paper/2407.03250/) (2024)
- [On the Invariants of Softmax Attention](https://mlsanity.com/paper/2605.02907/) (2026)
- [Degrees of Freedom for Linear Attention: Distilling Softmax Attention with Optimal Feature Efficiency](https://mlsanity.com/paper/2507.03340/) (2025)
- [Compressible Softmax-Attended Language under Incompressible Attention](https://mlsanity.com/paper/2604.04384/) (2026)

## Built on by (most cited first, 1 of 1)

- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)

## 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.