The Approximation Rank of Softmax Attention: Sharp Geometric Laws and Robust Interaction Dimension

arXiv:2608.28150v1 [cs.LG] 28 Aug 2026

The Approximation Rank of Softmax Attention: Sharp Geometric Laws and Robust Interaction Dimension Yuhe Sui

Jianing Zhang

Nanyang Technological University, Singapore ORCID: 0009-0002-7456-0804

Carnegie Mellon University ORCID: 0009-0004-3810-9316

Abstract Which geometry controls the rank complexity of normalized softmax attention? We study maximum-row-ℓ1 approximation rank, exactly the least unrestricted rank preserving every bounded vector-valued output. Two sharp worst-case laws isolate support geometry: for fixed d and error ε, spherical self-attention has rank Θd,ε (min{n, (1+β)(d−1)/2 }), while full-ball geometry adds one radial degree and, for β ≥ β0 (d, ε) and n ≥ Cd eβ/8 , gives Θd,ε (β d/2 ). For a fixed head, row-softmax quotients out row-scalar logit directions: the remaining visible query–key interaction dimension r yields an r/2 per-instance upper law, and bounded constructions show this exponent is minimax sharp. Approximate interaction subspaces incur an explicit residual output error and yield a tolerance-indexed SVD dimension. On an 84-head BERT-base calibration set, we observe modest effective-dimension reductions across many head–temperature settings, together with positive associations with finite constructive rank upper certificates. Together, these results separate support geometry, which sets worst-case temperature scaling, from softmax-visible interaction geometry, which controls per-head approximation complexity.

Keywords. softmax attention, approximation rank, representation geometry, effective dimension, convex geometry

1

Introduction

Softmax attention is usually described through ambient head dimension, the query–key map, or spectra of the resulting attention matrix. Row normalization, however, removes entire logit directions, while the geometry on which queries and keys vary controls how sharply the associated Gibbs family can localize. This raises an intrinsic approximation question: how much real matrix rank is required to preserve the action of normalized attention on every bounded value vector, and which geometric dimension should govern that rank? We study maximum-row-ℓ1 approximation rank, whose norm has an exact operator interpretation for arbitrary normed value spaces. The theory reveals two complementary geometric roles. First, support geometry controls worst-case temperature complexity: spherical self-attention has exponent (d − 1)/2, whereas allowing one radial degree in the full ball gives d/2 in the stated large-token regime. Second, for a fixed head, row-softmax quotients away row-scalar logit directions. The remaining visible query–key interaction dimension r yields an r/2 upper law, and a bounded construction shows that this exponent is minimax sharp. A projective softmax perturbation bound then extends the result to approximate interaction subspaces and leads to a reproducible SVD-based effective dimension. Our main contributions are therefore: 1

• sharp sphere and full-ball temperature laws for output-preserving approximation rank; • an exact softmax-visible interaction quotient with a minimax-sharp r/2 exponent, together with a robust approximate-subspace extension; and • synthetic checks of the lower constructions and a fixed 84-head BERT-base calibration connecting the effective dimension to finite constructive rank upper certificates. The broad principle that intrinsic geometry can reduce kernel rank is known (Altschuler and Parrilo, 2023; Budzinskiy, 2025), and rigorous attention thinning, coreset, and related approximations study more restricted or algorithmic representation classes (Carrell et al., 2025; Schröder and Mackey, 2026; Liberty et al., 2026). Query–key SVD and row-centred softmax spectra provide neighboring notions of interaction structure (Pan et al., 2024; Lee, 2026a,b). The narrower object here is the unrestricted rank of the normalized attention operator under uniform bounded-value output error, together with sharp temperature laws and the row-softmax-visible quotient. Appendix G gives a more detailed comparison.

2

Sharp geometric laws for output-preserving attention rank

2.1

Approximation rank and operator interpretation

For bounded queries and keys, let ⊤

eβqi kj Aij = P , βqi⊤ kℓ ℓe

rε (A) = min{rank(B) : max ∥Ai· − Bi· ∥1 ≤ ε}. i

For every nonzero normed value space E, max ∥Ai· − Bi· ∥1 = i

sup

max

maxj ∥vj ∥E ≤1

i

X

(Aij − Bij )vj

j

. E

Thus rε (A) is exactly the least unrestricted real rank that preserves every bounded vector-valued output to error ε.

2.2

Sphere and full-ball laws

First consider spherical self-attention Aβ (X)ij ∝ eβ⟨xi ,xj ⟩ for X = (x1 , . . . , xn ) ∈ (Sd−1 )n , and define Rsph ε (n, d, β) =

sup

rε (Aβ (X)).

X∈(Sd−1 )n

Then, for fixed d ≥ 2 and 0 < ε < 1, (d−1)/2 Rsph }. ε (n, d, β) ≍d,ε min{n, (1 + β)

(1)

For self-attention configurations in B2d , let Rε (n, d, β) denote the corresponding supremum. The finite lower theorem gives n
d/2 o Rε (n, d, β) ≳d,ε min n, 1 + min{β, log+ (n/Cd )} (2)

2

Figure 1: Support geometry changes temperature complexity. Synthetic decoder counts are lower certificates, not estimates of rε ; dashed lines show the (d − 1)/2 sphere and d/2 full-ball theorem exponents. for β ≥ 1 after fixed small-case constants, while the general upper bound is min{n, Cd′ (1 + β/ε2 )d/2 }. Hence, when (3)

n ≥ Cd eβ/8 ,

β ≥ β0 (d, ε),

(4)

Rε (n, d, β) ≍d,ε β d/2 .

Thus one radial degree of freedom changes the temperature exponent by exactly 1/2. The match in (4) is a worst-case state-capacity result because of the large-token condition (3). Appendices D and E give the proofs.

3

Softmax-visible interaction geometry

3.1

Exact quotient and sharp interaction law

The worst-case laws above still use ambient support dimension. For a fixed head, row-normalized attention can see less. Let U = span{qi − q1 },

sj = PU (kj − k1 ),

ρQ = inf max ∥PV (qi − q1 ) − a∥2 , a∈V

i

V = span{sj },

ρK = inf max ∥sj − c∥2 , c∈V

j

r = dim V, Γ = βρQ ρK .

Directions in U ∩ V ⊥ add the same scalar to every logit in a row and therefore disappear under softmax. After recentering, key-only terms become common positive base weights. The resulting r-dimensional weighted Gibbs family satisfies rε (A) ≤ min{n, Cr (1 + Γ/ε2 )r/2 }. 3

(5)

If r = 0 or ρQ ρK = 0, all rows coincide and rank one is exact. Appendix E.3 constructs bounded instances in Rr+1 with exact visible dimension r, Γ ≍r β, n ≍r,ε β r/2 , and rε (A) ≳r,ε β r/2 ; hence the r/2 exponent is minimax sharp. The upper mechanism is a weighted Gibbs-row cover, uniform in alphabet size and all positive base weights: convex-support gaps control KL divergence and a fixed-dimensional polytope approximation supplies the exponent; hemisphere lifting gives the full-ball law (Appendix A).

3.2

Robust approximate interaction subspaces

Learned heads can have full algebraic interaction rank even when most visible variation is concentrated near a smaller subspace. Let W ⊆ U have dimension r, P = PW , ui = qi − q1 , ξi = (I − P )ui , and ζj = (I − P )sj . Define ρQ,W = inf max ∥P ui − a∥2 , i

a∈W

ηW =

ρK,W = inf max ∥P sj − c∥2 , c∈W

j

β inf max oscj ⟨ξi − a⊥ , ζj ⟩, 2 a⊥ ∈U ∩W ⊥ i

ΓW = βρQ,W ρK,W ,

τW = 2 tanh(ηW /2).

The projective softmax inequality ∥ softmax(x + h) − softmax(x)∥1 ≤ 2 tanh(osc(h)/4) is classical (Cohen and Fausti, 2023). It converts discarded interaction into a uniform row error, after which the weighted Gibbs cover applies to the projected geometry. Theorem 1 (Robust interaction geometry). If τW < ε, then (  r/2 ) ΓW . rε (A) ≤ min n, Cr 1 + (ε − τW )2

(6)

For r = 0 or ΓW = 0, rank one is valid whenever τW ≤ ε.

3.3

SVD bridge and effective interaction dimension

For a reproducible nested family, mean-centre the visible-key matrix Z and let Wr be its top-r right-singular subspace. With Er = Z(I − PWr ), √ 1 max ∥Er,j ∥2 ≤ σr+1 (Z), 2 diam{Er,j } ≤ σr+1 (Z)/ 2. j

Writing ρQ,U = inf a∈U maxi ∥ui − a∥2 gives the spectrum-only bound   βρQ,U σr+1 (Z) spec √ τr = 2 tanh . 2 2

(7)

Directly verifying residual query radius δQ,r and key half-diameter ωK,r gives τrwidth = 2 tanh(βδQ,r ωK,r /2) ≤ τrspec ,

SVD rint (τ ) = min{r : τrwidth ≤ τ }.

(8)

The tolerance in (8) is an output-error tolerance, not explained variance. Top-r SVD supplies a reproducible family but need not minimize δQ,W ωK,W . Weight-space Q–K SVD is used for mechanistic analysis by Pan et al. (2024), while row-centred logit spectra and SVD-to-softmax fidelity are studied by Lee (2026a,b). Here token-level interaction residuals are mapped through the Gibbs cover to approximation rank. 4

4

Numerical checks and learned-head calibration

4.1

Synthetic scaling constructions

Figure 1 checks the lower constructions over their tested regimes: fitted sphere slopes are 0.504, 1.012, 1.381 versus 0.5, 1, 1.5, and full-ball slopes are 0.476, 0.951, 1.427, 1.903 versus d/2. The largest grouped full-ball point represents 17,850,625 message states and an effective token count about 1088,946 , underscoring that (4) is a worst-case state-capacity law rather than an ordinary context-length prediction.

4.2

BERT-base calibration

For a learned-representation calibration, we evaluate 84 BERT-base heads at lengths 64, 128, 256, five temperature multipliers, and errors 0.15, 0.25, 0.35. Reconstructed attention agrees with the model to 1.57 × 10−6 . Exact visible dimensions are 63–64; at ε = 0.25, 41.9% of head–temperature SVD (ε/3), although the reduction is usually modest. At multiplier cells have a strictly smaller rint one, the effective dimension has Spearman association 0.574 with the attention-SVD rank upper certificate and 0.606 with the representative-row upper certificate. We treat these 84 heads as a fixed calibration set, not a population sample; the associations concern finite constructive upper certificates rather than the unknown optimum rε .

5

Discussion and limitations

The results separate two geometric roles. Support shape determines the worst-case temperature scaling of normalized attention, while the row-softmax quotient identifies the interaction geometry that is actually visible in a particular head. The former is a worst-case state-capacity statement; the latter gives a per-instance notion that can be relaxed continuously through the projective residual. The analytic Cr in (5)–(6) can carry 2O(r) dependence (Arya et al., 2024), so it is a symbolic shape law rather than a useful numerical certificate at r ≈ 50–64; finite certificates here are directly evaluated approximants. Equation (4) requires the extreme-token condition (3), and the BERT study calibrates one model rather than establishing a universal learned-head law. Approximation rank alone implies neither sparsity nor arithmetic speedup (Alman and Song, 2023).

5

A

Weighted Gibbs covers with arbitrary positive base weights

We give the weighted-cover proof in full. Its constant is uniform in the alphabet size and in all positive base weights, including arbitrarily small minj πj . Vector-valued operator identity. Let E be any nonzero real normed space and let M ∈ Rm×N . Then N N X X sup max Mij vj = max |Mij |. (A.0) i

maxj ∥vj ∥E ≤1

i

j=1

E

j=1

The triangle inequality gives the upper bound. For the reverse inequality, choose a row i⋆ attaining the maximum, fix e ∈ E with ∥e∥E = 1, and take P vj = sgn(Mi⋆ j )e (with an arbitrary sign when the entry is zero). The i⋆ output then has norm j |Mi⋆ j |. Thus maximum-row-ℓ1 error is exactly the induced error on bounded vector-valued attention outputs, independently of the value dimension and norm. Theorem A.1 (Weighted spherical Gibbs P cover). Fix m ≥ 2, 0 < ε < 1, γ ≥ 0, keys k1 , . . . , kN ∈ B2m , and arbitrary weights πj > 0 with j πj = 1. For x ∈ Sm−1 let πj eγ⟨x,kj ⟩ px (j) = PN . γ⟨x,kℓ ⟩ ℓ=1 πℓ e There is an ℓ1 cover of {px : x ∈ Sm−1 } by members of the same family with cardinality  γ (m−1)/2 M ≤ Cm 1 + 2 , ε where Cm depends only on m, uniformly in N and in the positive weight vector π. Log partition and support body. The case γ = 0 is immediate: every row equals π. Assume γ > 0 and define F (θ) = log

N X

πj e⟨θ,kj ⟩ ,

mx = ∇F (γx),

h(x) = 2 +

j=1

F (γx) . γ

Since ∥kj ∥2 ≤ 1, −γ ≤ F (γx) ≤ γ and hence 1 ≤ h(x) ≤ 3. Moreover KL(px ∥π) = γ⟨x, mx ⟩ − F (γx). The ratio px (j)/πj = eγ⟨x,kj ⟩−F (γx) is at most e2γ , so 0 ≤ KL(px ∥π) ≤ 2γ without any lower bound on minj πj . Put KL(px ∥π) ax = h(x) − ⟨x, mx ⟩ = 2 − ∈ [0, 2]. (A.1) γ On the tangent space Tx Sm−1 , ∇S2 h(x) + h(x)gx = γ Covpx (K)|Tx Sm−1 + ax gx ⪰ 0.

(A.2)

Consider the one-homogeneous extension H(0) = 0 and H(z) = ∥z∥2 h(z/∥z∥2 ) for z = ̸ 0. Its 2 Euclidean Hessian away from the origin has zero radial component and tangent block ∥z∥−1 2 (∇S h + hg) ⪰ 0. Thus H is convex on every segment not passing through the origin. A segment through the 6

origin lies on one line; convexity across the origin follows from H(x) + H(−x) = h(x) + h(−x) > 0. Hence H is globally convex and is the support function of a compact convex body K ⊂ Rm . Since 1 ≤ h ≤ 3, B2m ⊆ K ⊆ 3B2m . (A.3) The support point with outer normal x is cx = ∇H(x) = mx + ax x.

(A.4)

This is also the standard spherical support-function criterion; see Schneider (2014). KL/Bregman identity. For the log partition, the Bregman identity is DF (γx, γy) = F (γx) − F (γy) − γ⟨my , x − y⟩ = KL(py ∥px ).

(A.5)

Using (A.1)–(A.4), a direct rearrangement gives the support-gap identity h(x) − ⟨x, cy ⟩ =

KL(py ∥px ) + ay (1 − ⟨x, y⟩). γ

(A.6)

The second term is nonnegative. Therefore a support point cy whose support gap at x is at most t satisfies KL(py ∥px ) ≤ γt. The KL/Bregman geometry itself is classical for regular exponential families; see, e.g., Banerjee et al. (2005). Projection net and polytope approximation. Classical convex-body approximation gives the following fixed-dimensional fact: if B2m ⊆ K ⊆ 3B2m and 0 < t ≤ 1, there are support points cy1 , . . . , cyM such that the inscribed polytope P = conv{cys }M s=1 obeys 0 ≤ hK (x) − hP (x) ≤ t ∀x ∈ Sm−1 ,

M ≤ Cm t−(m−1)/2 .

(A.7)

The exponent in (A.7) is the Dudley–Bronshteyn–Ivanov rate. Modern quantitative formulations are reviewed by Arya and Mount (2023). Taking t = min{1, ε2 /(2γ)} and, for each x, a vertex attaining hP (x), (A.6) yields KL(pys ∥px ) ≤ ε2 /2. Pinsker’s inequality then gives ∥pys − px ∥1 ≤ ε. Combining the small-γ and t < 1 cases gives the stated Cm (1 + γ/ε2 )(m−1)/2 cardinality. The construction uses only (A.3), so the constant is independent of N and π. Representative rows imply matrix rank. For any finite collection of query points xi , assign each row pxi to a representative pys(i) and let Bi· = pys(i) . Then maxi ∥pxi − Bi· ∥1 ≤ ε, B is row-stochastic and nonnegative, and it has at most M distinct rows. Consequently rank(B) ≤ M . This is the representative-row-to-rank step used in the main theorem. For a rectangular mQ × N attention matrix, the same proof gives the trivial cap min{mQ , N } in place of n; none of the upper or quotient arguments requires equal query and key sets. Edge cases. For m = 1, S0 = {−1, +1}, so two rows cover the family (one row if γ = 0). Repeated keys simply repeat coordinates and do not change any step. A lower-dimensional key span may be projected to that span and only improves the dimension. The theorem assumes πj > 0; a zero-weight coordinate, if present in an application, is identically absent and can be deleted before applying the theorem.

7

Proposition A.2 (Weighted full-ball lift). For weighted Gibbs rows with xi , yj ∈ B2r and inverse temperature γ, the same argument yields    γ r/2 . (A.8) rε ≤ min n, Cr 1 + 2 ε p Proof. Lift x ∈ B2r to x b = (x, 1 − ∥x∥22 ) ∈ Sr and y ∈ B2r to yb = (y, 0) ∈ B2r+1 . Then ⟨b x, yb⟩ = ⟨x, y⟩ exactly. Apply the weighted spherical theorem in dimension r + 1 and use the representative-row construction. If either query or key radius is zero, the family has one row after row/key shifts and rank one is exact.

B

Exact quotient and robust residual theorem

Let ui = qi − q1 ,

U = span{ui },

sj = PU (kj − k1 ),

V = span{sj } ⊆ U.

(B.1)

The original attention rows can be written πj eβ⟨ui ,sj ⟩ , Aij = P β⟨ui ,sℓ ⟩ ℓ πℓ e

πj ∝ eβ⟨q1 ,kj ⟩ > 0.

(B.2)

Indeed, ui ∈ U , so the part of kj − k1 orthogonal to U is invisible, and the remaining k1 term is rowwise scalar. For any W ⊆ U with projector P = PW , define the projected radii ρQ,W = inf max ∥P ui − aW ∥2 , aW ∈W

ρK,W = inf max ∥P sj − cW ∥2 , cW ∈W

i

j

(B.3)

ΓW = βρQ,W ρK,W . Put ξi = (I − P )ui , ζj = (I − P )sj , and define ηW =

β inf max oscj ⟨ξi − a⊥ , ζj ⟩, 2 a⊥ ∈U ∩W ⊥ i

τW = 2 tanh(ηW /2).

(B.4)

Only residual key differences enter the oscillation, so the finite-dimensional infimum is attained after quotienting directions orthogonal to their span. Lemma B.1 (Sharp quotient softmax perturbation). For x, h ∈ RN ,   osc(h) osc(h) ∥ softmax(x + h) − softmax(x)∥1 ≤ 2 tanh ≤ . 4 2

(B.5)

The first inequality is sharp. Proof. The likelihood ratio between the two probability vectors is proportional to ehj , so their Hilbert projective distance is exactly maxj hj − minj hj = osc(h). The sharp total-variation versus Hilbert-distance inequality of Cohen and Fausti (2023) gives TV ≤ tanh(osc(h)/4); multiply by two. The second inequality is 2 tanh(t/4) ≤ t/2. Two-coordinate likelihood ratios attain the sharp envelope.

8

Theorem B.2 (Robust interaction geometry). Let W ⊆ U have dimension r and define (B.3)–(B.4). If τW < ε, then (  r/2 ) ΓW rε (A) ≤ min n, Cr 1 + . (B.6) (ε − τW )2 If r = 0 or ΓW = 0, rank one is valid whenever τW ≤ ε. Proof. Choose projected centres aW , cW ∈ W and a residual query centre a⊥ ∈ U ∩ W ⊥ . Orthogonality gives the exact decomposition ⟨ui , sj ⟩ = ⟨P ui − aW , P sj − cW ⟩ + ⟨ξi − a⊥ , ζj ⟩ (B.7)

+ ⟨aW + a⊥ , sj ⟩ + ⟨P ui − aW , cW ⟩.

Orthogonality eliminates mixed W/W ⊥ terms. The third term depends only on the key and is absorbed into a common positive base weight; the fourth is rowwise scalar and vanishes under softmax. Thus the exact row is a projected weighted Gibbs row perturbed by residual logit vector hij = β⟨ξi − a⊥ , ζj ⟩. By the preceding lemma, optimizing over the common residual centre gives (B.8)

ei· ∥1 ≤ τW . max ∥Ai· − A i

The projected family has query radius ρQ,W , key radius ρK,W , and normalized inverse-temperature product ΓW . The full-ball lift, at remaining error ε − τW > 0, gives a rank Cr (1 + ΓW /(ε − τW )2 )r/2 e The triangle inequality yields (B.6), with the trivial cap n. If r = 0 or one approximant to A. projected radius is zero, the projected Gibbs family has one row; (B.8) then gives the rank-one statement. Exact theorem and edge regimes. Taking W = V makes every residual key ζj zero, hence τV = 0 and the robust theorem becomes the exact interaction-quotient theorem with ρQ = inf max ∥PV ui − a∥2 , a∈V

ρK = inf max ∥sj − c∥2 ,

i

c∈V

j

Γ = βρQ ρK .

(B.9)

If β = 0, all rows are uniform and rank one is exact. If the residual is zero, τW = 0. As β ↓ 0, both ΓW and ηW vanish linearly. If τW ↑ ε, no positive cover-error budget remains and only the trivial cap n is guaranteed by this proof. A simpler residual bound is obtained from δQ,W =

inf

a⊥

∈U ∩W ⊥

max ∥ξi − a⊥ ∥2 , i

ωK,W =

1 max ∥ζj − ζℓ ∥2 . 2 j,ℓ

Cauchy–Schwarz gives ηW ≤ βδQ,W ωK,W and therefore the computable upper bound   βδQ,W ωK,W width τW = 2 tanh . 2

C

(B.10)

(B.11)

SVD bridge and tolerance-indexed effective interaction dimension

Mean-centre the visible keys: s̄ =

1X sj , n

Zj· = (sj − s̄)⊤ .

(C.1)

j

Because s1 = 0, the affine span of the sj equals their linear span, so rank(Z) = dim V . Let Wr be the top-r right-singular subspace of Z, with projector Pr , and Er = Z(I − Pr ). 9

Proposition C.1 (Deterministic spectral residual). For every r, 1 σr+1 (Z) . diam{Er,j· } ≤ √ 2 2

max ∥Er,j· ∥2 ≤ σr+1 (Z), j

(C.2)

Proof. ∥Er ∥2→2 = σr+1 (Z), so each row norm is at most this value. For rows j, ℓ, √ ∥Er,j· − Er,ℓ· ∥2 = ∥(ej − eℓ )⊤ Er ∥2 ≤ 2 ∥Er ∥2→2 . Divide by two. Let the full query-difference Chebyshev radius be (C.3)

ρQ,U = inf max ∥ui − a∥2 . a∈U

i

Orthogonal √ projection of a full-space centre gives δQ,r ≤ ρQ,U , while the proposition gives ωK,r ≤ σr+1 (Z)/ 2. Hence the spectrum-only perturbation bound is   βρQ,U σr+1 (Z) √ τrspec = 2 tanh . (C.4) 2 2 The tighter directly computed residual-width bound is δQ,r =

inf

a⊥ ∈U ∩Wr⊥

max ∥(I − Pr )ui − a⊥ ∥2 ,

ωK,r =

i

τrwidth = 2 tanh



βδQ,r ωK,r 2



1 max ∥(I − Pr )(sj − sℓ )∥2 , 2 j,ℓ

(C.5)

≤ τrspec .

(C.6)

The projected radii and shape parameter are ρQ,r = inf max ∥Pr ui − a∥2 , a∈Wr

i

ρK,r = inf max ∥Pr sj − c∥2 , c∈Wr

Γr = βρQ,r ρK,r .

j

(C.7)

Therefore, whenever τrwidth < ε, (

 rε (A) ≤ min n, Cr 1 +

Γr (ε − τrwidth )2

r/2 ) .

(C.8)

The reproducible SVD effective dimension is SVD rint (τ ) = min{r : τrwidth ≤ τ }.

(C.9)

The subspace oracle optimizes over all candidate subspaces: ⋆ rint (τ ) = min{dim W : W ⊆ U, τW ≤ τ }.

(C.10)

At τ = 0, (C.10) recovers dim V in exact arithmetic (unless all query variation is trivial). Top-r SVD supplies a canonical nested family and is optimal for the usual key-matrix spectral/Frobenius objectives; it need not minimize the product δQ,W ωK,W or the complete right-hand side of (C.8). Percentage explained variance is not the criterion in (C.9)–(C.10).

10

C.1

Dimension dependence of the covering constant

The exponent in (A.7) is sharp for fixed dimension. General-purpose convex coverings with the optimal approximation exponent can carry prefactors of the form 2O(r) in well-centred settings (Arya et al., 2024). Propagating such a construction through (A.3)–(A.8) gives an explicit but very large dimension-dependent prefactor. At learned-head dimensions r = 50–64, this prefactor is not numerically useful. We therefore retain symbolic Cr and separate the prefactor-free shape term   r Γr (C.11) log Sr = log 1 + 2 (ε − τr )2 from the finite constructions. A directly evaluated attention-SVD or representative-row approximant gives a finite constructive rank upper certificate; (C.11) records the prefactor-free shape term.

D

Sharp spherical law

For X = (x1 , . . . , xn ) ∈ (Sd−1 )n let Aβ (X)ij ∝ eβ⟨xi ,xj ⟩ and define Rsph ε (n, d, β) =

sup

rε (Aβ (X)).

X∈(Sd−1 )n

Theorem D.1 (Sharp spherical law). For fixed d ≥ 2 and 0 < ε < 1, (d−1)/2 Rsph } ε (n, d, β) ≍d,ε min{n, (1 + β)

(D.1)

uniformly for n ≥ 1 and β ≥ 0. Proof. The upper bound is the weighted spherical cover with uniform weights and m = d, capped by n. For the lower bound, write Z −β(1−⟨x,y⟩) wβ (x, y) = e , Id (β) = wβ (x, y) dσ(y). Sd−1

Rotational invariance makes Id independent of x. The change of variables t = 1 − ⟨x, y⟩ has density comparable near zero to t(d−3)/2 ; elementary Laplace bounds therefore give, for β ≥ 1, Id (β) ≍d β −(d−1)/2 .

(D.2)

This reciprocal-density estimate is the classical density ingredient in the construction. Take N independent uniform sphere points. The expected total directed cross-energy is N (N − 1)Id (β). Hence some realization has total cross-energy at most twice this expectation. At least half its vertices then have individual cross-energy at most 4(N − 1)Id (β); discard the rest. With N ≍ cε /Id (β) and cε sufficiently small, we obtain M ≍d,ε β (d−1)/2 centres z1 , . . . , zM satisfying max i

X

wβ (zi , zj ) ≤ δε

(D.3)

j̸=i

for a fixed δε > 0 chosen below. If n ≤ M , use any n centres. Their attention matrix is within 2δε /(1 + δε ) in maximum row-ℓ1 of the identity. If n > M , duplicate the M centres into balanced clusters of sizes ⌊n/M ⌋ or ⌈n/M ⌉. The ratio of any two nonzero cluster sizes is at most two, so (D.3) shows that each row places all 11

but O(δε ) of its mass uniformly on its own cluster. Thus the attention matrix is within a chosen δ < 1 − ε of the rank-M block-averaging projection P . Select one row from each cluster with an M × n matrix S, and let the n × M cluster-indicator decoder be D. Then SP D = IM . If B is any maximum-row-ℓ1 ε-approximant to A, multiplication by S and the decoder D is an ℓ1 contraction, so ∥SBD − IM ∥∞→∞ ≤ ε + δ < 1.

(D.4)

Hence SBD is invertible by the Neumann series and rank(B) ≥ M . This proves the lower bound for β ≥ 1, including nondivisible n. For bounded β, the lower bound in (D.1) is a constant and rank one supplies the matching order. At β = 0, rank one is exact.

E

Full-ball finite lower theorem and interaction-exponent sharpness

Let Rε (n, d, β) be the supremum of rε (A) over self-attention configurations with all tokens in B2d . Theorem E.1 (Finite full-ball lower certificate). Fix d ≥ 1 and 0 < ε < 1. There are constants cd,ε , Cd,ε , Cd > 0 such that for β ≥ 1, (   d/2 ) n Rε (n, d, β) ≥ cd,ε min n, 1 + min β, log+ , (E.1) Cd after adjusting the fixed constants for the finitely many below-threshold integer cases, where log+ x = max{0, log x}. The upper bound (  d/2 ) β (E.2) Rε (n, d, β) ≤ min n, Cd′ 1 + 2 ε follows from the full-ball lift. 2

Proof. Choose an even integer L = L(d, ε) so large that a standard discrete Gaussian G ∝ e−∥u∥2 /2 on Zd obeys Pr(∥G∥∞ ≥ L/2) ≤ δ/4, ε + 2δ < 1. (E.3) √ Choose 0 < b ≤ 1/(2 d) and lattice groups p u zu = √ , u ∈ Zd , ∥u∥∞ ≤ b β. (E.4) β All tokens lie in (1/2)B2d . Assign ideal multiplicities   βdb2 − ∥u∥22 wu = exp ≥1 2 and integer multiplicities mu = ⌈wu ⌉, so wu ≤ mu ≤ 2wu . The base token count satisfies X 2 N0 = mu ≤ Cd eβdb /2 .

(E.5)

(E.6)

u

For arbitrary n ≥ N0 , take T = ⌊n/N0 ⌋ whole copies of all groups and distribute the remaining prefix arbitrarily. The resulting multiplicities obey T wu ≤ m′u ≤ 4T wu . 12

(E.7)

√ Use message indices v ∈ Zd whose success cubes remain inside the box: ∥Lv∥ ≤ b β − L/2. For ∞ √ each such v, take the existing token qv = zLv = Lv/ β as the message query. For the ideal weights,   βdb2 L2 ∥v∥22 2 (E.8) wu eβ⟨qv ,zu ⟩ = exp e−∥u−Lv∥2 /2 . + 2 2 Thus, apart from a factor independent of u, the row is a translated discrete standard Gaussian. Equation (E.7) changes all probability ratios by at most a universal factor four, so (E.3) bounds the probability of leaving the nearest-message Voronoi cell by δ. Every selected message centre is at least L/2 from the box boundary. Truncation therefore preserves its entire success cube and can remove only failure points, so it cannot increase the error. Ties are charged to the error event. There are p M ≍d (b β/L)d ≍d,ε (βb2 )d/2 (E.9) message rows. Decode each token group to its nearest message. The selected M × M channel is within row-ℓ1 distance 2δ of IM . For any ε-approximant B, selection and decoding are contractions, so the decoded matrix differs from IM by at most ε + 2δ < 1 in ℓ∞ operator norm. It is invertible and rank(B) ≥ M . Finally choose, above the fixed lattice threshold,   1 2 n 2 b = min , log . (E.10) 4d βd Cd Equations (E.6), (E.9), and integer-floor adjustments give (E.1). The upper bound (E.2) is the full-ball lift. Corollary E.2 (Large-token d/2 law). For fixed d ≥ 1 and 0 < ε < 1, there is β0 (d, ε) such that whenever β ≥ β0 (d, ε), n ≥ Cd eβ/8 , (E.11) one has Rε (n, d, β) ≍d,ε β d/2 .

(E.12)

√

Proof. Under (E.11), take b = 1/(2 d) in (E.10). Then (E.6) requires only Cd eβ/8 tokens and (E.9) gives M ≍d,ε β d/2 . Combine with (E.2). The corollary is a worst-case state-capacity theorem. In the grouped construction, the largest message set is M = 17,850,625 while the analytically represented effective token count is about 1088,946 . Grouping makes this asymptotic scale tractable without materializing the duplicate tokens.

E.1

Sharpness of the interaction-dimension exponent

Theorem E.3 (Sharp interaction exponent). Fix r ≥ 1 and 0 < ε < 1. There are constants cr,ε , Cr,ε , β0 > 0 such that for every β ≥ β0 there are n ≍r,ε β r/2 queries and keys in B2r+1 whose attention matrix A has exact visible interaction dimension r and shape parameter Γ = βρQ ρK ≍r β, while rε (A) ≥ cr,ε β r/2 ≍r,ε Γr/2 . (E.13) Consequently the r/2 exponent in the exact interaction upper bound cannot be replaced by any smaller exponent in a uniform fixed-r theorem.

13

Proof. Choose an even L = L(r, ε) and δ > 0 so that for a standard discrete Gaussian G on Zr , Pr(∥G∥∞ ≥ L/2) ≤ δ,

ε + 2δ < 1.

(E.14)

√

√ Set b = 1/(2 r) and a = ⌊b β⌋. Index the keys by u ∈ Zr with ∥u∥∞ ≤ a and define   u ∥u∥22 ∈ Rr+1 . ku = √ , − β β Index message queries by v ∈ Zr satisfying ∥Lv∥∞ ≤ a − L/2 and set   Lv 1 qv = √ , . β 2

(E.15)

(E.16)

There are N = (2a + 1)r ≍r β r/2 keys and M ≍r,ε β r/2 message queries. Pad the query list to n = N by repeating q0 . Since ∥u∥22 /β ≤ rb2 = 1/4, ∥ku ∥22 ≤ rb2 + r2 b4 = 5/16,

∥qv ∥22 ≤ rb2 + 1/4 = 1/2,

so all vectors lie in B2r+1 . For a message row v, ∥u∥22 2 L2 ∥v∥22 ∥u − Lv∥22 = − . 2 2

β⟨qv , ku ⟩ = Lv · u −

Hence the key distribution in that row is exactly a translated discrete Gaussian conditioned on the lattice box. The cube {u : ∥u − Lv∥∞ < L/2} lies inside the box, so conditioning can only increase its probability; by (E.14) that probability is at least 1 − δ. Decode each key to its nearest selected message centre, assigning keys outside all success cubes arbitrarily. Let D be the resulting N × M one-hot decoder and let S select the M message-query rows. Then ∥SAD − IM ∥∞→∞ ≤ 2δ. (E.17) If B is any maximum-row-ℓ1 ε-approximant to A, right multiplication by D and row selection are ℓ1 contractions, and hence ∥SBD − IM ∥∞→∞ ≤ ε + 2δ < 1. Thus SBD is invertible and rank(B) ≥ M ≍r,ε β r/2 . √ Order q0 and k0 first. The query-difference span is U = Rr × {0}, while PU (ku − k0 ) = (u/ β, 0) spans the same space, so the exact visible interaction dimension is r. Both projected point sets are symmetric lattice boxes. For all sufficiently large β, their Chebyshev radii are bounded above and below by positive constants (for example, 1/8 ≤ ρQ ≤ 1/2 and 1/4 ≤ ρK ≤ 1/2 after increasing β0 ). Therefore Γ = βρQ ρK ≍r β, which converts the lower bound to the final form in (E.13).

F

Learned-head certificate chain

For a fixed learned head and candidate dimension r, the quantities entering the robust upper bound form the deterministic chain (rexact , r, σr+1 , δQ,r , ωK,r ) −→ τrwidth −→ (ρQ,r , ρK,r , Γr ) −→ log Sr −→ finite constructive certificates. 14

(F.1)

Specifically, τrwidth = 2 tanh(βδQ,r ωK,r /2),

Γr = βρQ,r ρK,r ,

  r Γr log Sr = log 1 + . (F.2) 2 (ε − τrwidth )2

The attention-SVD and representative-row quantities are constructive rank upper certificates at maximum row-ℓ1 error ε. The top-k quantity is a sparsity budget. The available BERT summary at multiplier one and ε = 0.25 is an aggregate calibration over a fixed 84-head evaluation set; no population-level inference is intended. Exact visible dimensions are SVD (ε/3) = 64, median attention-SVD upper certificate 48, median representative63–64, median rint row upper certificate 87.5, and median top-k sparsity budget 45. Aggregate medians do not determine a single tuple (σr+1 , δQ,r , ωK,r , Γr , log Sr ) for one representative head, so the deterministic chain (F.1)–(F.2) and the aggregate calibration are reported separately. In particular, symbolic theorem shape ̸= finite constructive rank upper certificate.

G

Relation to neighboring theory

The proof combines several established ingredients. Cohen and Fausti (2023) give the sharp Hilbert/projective total-variation comparison used in the softmax perturbation lemma; exponentialfamily KL/Bregman geometry is classical (Banerjee et al., 2005); and the (m − 1)/2 convex-body approximation exponent has modern quantitative accounts in Arya and Mount (2023); Arya et al. (2024). Broader kernel-rank precedents include Altschuler and Parrilo (2023), where approximation rank can depend on intrinsic variety dimension rather than ambient dimension, and Budzinskiy (2025), which gives entrywise low-rank approximations for several classes of function-generated matrices, including inner-product functions, and discusses transformer attention. Thus the broad principle that geometry or intrinsic dimension can reduce kernel rank is not a novelty claim here. Rigorous attention approximations also use more restricted representation classes. Carrell et al. (2025) convert approximate low rank into a thinning construction with attention guarantees; Schröder and Mackey (2026) obtain a weighted coreset with near-linear runtime under bounded inputs; and Liberty et al. (2026) prove nearly optimal uniform-query attention coresets. These results address algorithmic or subset-based approximations rather than unrestricted rank of the normalized output matrix under maximum-row-ℓ1 error. On interaction structure, Pan et al. (2024) analyze the weight-space WQ⊤ WK by SVD, Lee (2026b) studies row-centred logit/energy-field invariants and their rank and spectral structure, and Lee (2026a) proves per-row softmax fidelity for truncated row-centred-logit SVD under a singular-vector delocalization condition. Nishikawa et al. (2025) chooses linear-attention feature dimension through a statistical degrees-of-freedom criterion, and Yoon (2026) defines a task-intrinsic attention-native rank for a different capacity/realizability problem. The narrow theorem package here controls a different object: unrestricted uniform-output approximation rank of normalized attention. It combines the maximum-row-ℓ1 operator criterion, sharp sphere/full-ball temperature laws, the exact row-softmax-visible query–key quotient with minimax-sharp r/2 exponent, and a robust projective-residual extension. SVD supplies a reproducible corollary for selecting nested candidate subspaces; it is not claimed to optimize the robust bound.

15

References Josh Alman and Zhao Song. Fast attention requires bounded entries. In Advances in Neural Information Processing Systems, 2023. Jason M. Altschuler and Pablo A. Parrilo. Kernel approximation on algebraic varieties. SIAM Journal on Applied Algebra and Geometry, 7(1):1–28, 2023. doi: 10.1137/21M1425050. Sunil Arya and David M. Mount. Optimal volume-sensitive bounds for polytope approximation. In 39th International Symposium on Computational Geometry (SoCG 2023), volume 258 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:16, 2023. doi: 10.4230/LIPIcs. SoCG.2023.9. arXiv:2303.09586. Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Economical convex coverings and applications. SIAM Journal on Computing, 53(4):1002–1038, 2024. doi: 10.1137/23M1568351. arXiv:2303.08349. Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with Bregman divergences. Journal of Machine Learning Research, 6(58):1705–1749, 2005. Stanislav Budzinskiy. When big data actually are low-rank, or entrywise approximation of certain function-generated matrices. SIAM Journal on Mathematics of Data Science, 7(3):1098–1122, 2025. doi: 10.1137/24M1687133. Annabelle Michael Carrell, Albert Gong, Abhishek Shetty, Raaz Dwivedi, and Lester Mackey. Lowrank thinning. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 6811–6848, 2025. Samuel N. Cohen and Eliana Fausti. Hyperbolic contractivity and the Hilbert metric on probability measures. arXiv preprint arXiv:2309.02413, 2023. Wonsuk Lee. Compressible softmax-attended language under incompressible attention. arXiv preprint arXiv:2604.04384, 2026a. Wonsuk Lee. On the invariants of softmax attention. arXiv preprint arXiv:2605.02907, 2026b. Edo Liberty, Alexandr Andoni, and Eldar Kleiner. Nearly optimal attention coresets. arXiv preprint arXiv:2605.05602, 2026. Naoki Nishikawa, Rei Higuchi, and Taiji Suzuki. Degrees of freedom for linear attention: Distilling softmax attention with optimal feature efficiency. In Advances in Neural Information Processing Systems, 2025. arXiv:2507.03340. Xu Pan, Aaron Philip, Ziqian Xie, and Odelia Schwartz. Dissecting query-key interaction in vision transformers. In Advances in Neural Information Processing Systems, 2024. Rolf Schneider. Convex Bodies: The Brunn–Minkowski Theory. Cambridge University Press, second expanded edition, 2014. Tobias Schröder and Lester Mackey. WildCat: Near-linear attention in theory and practice. In Proceedings of the 43rd International Conference on Machine Learning, 2026. Byeong Hoon Yoon. The entropic bound for transformers: Why static rank fails and attention-native rank recovers. arXiv preprint arXiv:2607.23050, 2026. 16

Related documents

• On State Reduction in Linear Attention#1141482
• MiniMax Sparse Attention#275879
• RoPE attention is an exact forward-pass gradient step with softmax intact#974785
• Rank-Aware Spectral Bounds on Attention Logits for Stable Low-Precision Training#1084141
• Visual Attention#91634