mlsanityData to 7 Oct 2026

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

arXiv 2608.28150 ↗First posted 28 Aug 2026cs.LG cs.AIcited by 1

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

  1. 2020Rethinking Attention with Performerscited by 1,584
  2. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  3. 2021Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attentioncited by 468
  4. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 128
  5. 2014Factorization Norms and Hereditary Discrepancycited by 14
  6. 2024Dissecting Query-Key Interaction in Vision Transformerscited by 12
  7. 2025Low-Rank Thinningcited by 7
  8. 2021Kernel approximation on algebraic varietiescited by 4
  9. 2026Nearly Optimal Attention Coresetscited by 4
  10. 2024When big data actually are low-rank, or entrywise approximation of certain function-generated matricescited by 3
  11. 2026On the Invariants of Softmax Attentioncited by 3
  12. 2025Degrees of Freedom for Linear Attention: Distilling Softmax Attention with Optimal Feature Efficiencycited by 2
1 more
  1. 2026Compressible Softmax-Attended Language under Incompressible Attentioncited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.