PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yuhe Sui, Jianing Zhang

arXiv:2608.28150v1cs.LGcs.AI

TL;DR

The paper asks which geometry controls the rank complexity of normalized softmax attention. It analyzes maximum-row-ℓ1 approximation rank through support geometry and the softmax-visible interaction quotient, then extends the analysis to approximate subspaces and calibrates it on BERT-base. The main result separates worst-case temperature scaling from per-head approximation complexity, with synthetic checks supporting the predicted geometric exponents.

  • Problem

    The paper asks which geometric dimension governs the unrestricted rank needed to preserve normalized softmax attention on every bounded vector-valued output.

    Source: §1 · p. 1

  • Method

    The paper studies maximum-row-ℓ1 approximation rank, derives support-geometry laws and a row-softmax-visible interaction quotient, and extends the quotient using residual bounds and SVD-selected subspaces.

    Source: §1 · p. 1, §3.2 · p. 4, §3.3 · p. 4

  • Results

    Support shape determines worst-case temperature scaling, while the visible interaction geometry controls per-head approximation complexity; synthetic checks support the predicted exponents.

    Source: §5 · p. 5, §4.1 · p. 5

  • Takeaways & Limitations

    The results separate worst-case state-capacity laws from a per-instance interaction-geometry notion that can be relaxed through a projective residual.

    Source: §5 · p. 5

    The BERT study calibrates one model rather than establishing a universal learned-head law, and approximation rank alone implies neither sparsity nor arithmetic speedup.

    Source: §5 · p. 5

Abstract

from arXiv · show

Which geometry controls the rank complexity of normalized softmax attention? We study maximum-row-$\ell_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 $\varepsilon$, spherical self-attention has rank $Θ_{d,\varepsilon}(\min\{n,(1+β)^{(d-1)/2}\})$, while full-ball geometry adds one radial degree and, for $β\geβ_0(d,\varepsilon)$ and $n\ge C_d e^{β/8}$, gives $Θ_{d,\varepsilon}(β^{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.

1 Introduction

The paper formulates unrestricted output-preserving approximation rank for normalized attention and identifies support geometry and softmax-visible interaction geometry as distinct controls. It develops sharp geometric laws, a robust subspace extension, and calibration evidence from BERT-base.

Research question

  • Maximum-row-ℓ1 approximation rank is the least unrestricted rank preserving normalized attention on every bounded vector-valued output.The norm has an exact operator interpretation for arbitrary normed value spaces.Source: §1 · p. 1

Sharp geometric laws

  • Support geometry controls worst-case temperature complexity, with sphere and full-ball geometries having exponents (d−1)/2 and d/2, respectively.The full-ball law adds one radial degree of freedom in the stated large-token regime.Source: §1 · pp. 1–2

Visible interaction geometry

  • Row-softmax removes row-scalar logit directions, leaving a visible interaction dimension r with an r/2 upper law and minimax-sharp bounded constructions.A projective perturbation bound extends the result to approximate interaction subspaces.Source: §1 · pp. 1–2

Empirical calibration

  • An 84-head BERT-base calibration connects effective interaction dimension with finite constructive rank upper certificates.The calibration is presented as an empirical connection rather than a universal learned-head law.Source: §1 · p. 2

Relation to prior work

  • The paper distinguishes its unrestricted normalized-output rank from prior geometric, thinning, coreset, and interaction-spectrum approximations.The narrower object is uniform bounded-value output error under unrestricted rank.Source: §1 · p. 2

2 Sharp geometric laws for output-preserving attention rank

The rank laws are established through an exact bounded-output operator interpretation and geometric constructions over spherical and full-ball supports. Allowing radial variation changes the worst-case temperature exponent by 1/2.

Approximation-rank interpretation

  • Maximum-row-ℓ1 error exactly measures error on bounded vector-valued attention outputs, independently of value dimension and norm.This operator interpretation underlies the definition of output-preserving approximation rank.Source: §2.1 · p. 2

Sphere and full-ball laws

  • Sphere and full-ball support geometries produce theorem exponents (d−1)/2 and d/2, respectively.Figure 1 compares synthetic lower certificates with these predicted slopes; the certificates are not estimates of rε.Source: Figure 1 · p. 3, §2.2 · p. 3
  • One radial degree of freedom increases the temperature exponent by exactly 1/2.The full-ball match is a worst-case state-capacity result under the large-token condition.Source: §2.2 · p. 3

3 Softmax-visible interaction geometry

The section identifies the softmax-visible interaction dimension after quotienting out row-scalar logits, then extends the resulting rank law to approximate subspaces.

Exact quotient

  • Ambient directions in U ∩ V⊥ add a common rowwise logit scalar and disappear under softmax.After recentering, key-only terms become common positive base weights.Source: §3.1 · p. 3
  • The remaining visible interaction dimension r gives a weighted Gibbs-family upper law with an r/2 exponent.The construction is uniform in alphabet size and positive base weights.Source: §3.1 · pp. 3–4

Sharpness

  • Bounded instances attain rε(A) ≳r,ε β^(r/2), establishing minimax sharpness of the r/2 exponent.These instances have exact visible dimension r, Γ ≍r β, and n ≍r,ε β^(r/2).Source: §3.1 · p. 4

Approximate subspaces

  • Discarded interaction is converted through a projective softmax inequality into a uniform row error before applying the projected Gibbs cover.This provides the robust extension from exact to approximate interaction subspaces.Source: §3.2 · p. 4
  • Top-r right-singular subspaces of the mean-centred visible-key matrix define a reproducible nested effective-dimension family.The resulting tolerance is an output-error tolerance rather than explained variance, and the SVD choice need not minimize the residual product.Source: §3.3 · p. 4

4 Numerical checks and learned-head calibration

Synthetic experiments reproduce the predicted sphere and full-ball scaling slopes, while BERT-base calibration finds modest effective-dimension reductions and positive associations with finite rank certificates.

Synthetic scaling constructions

  • Full-ball grouped constructions reached 17,850,625 message states with an effective token count about 1088,946.This illustrates a worst-case state-capacity law rather than an ordinary context-length prediction.Source: §4.1 · p. 5

Learned-head calibration

  • At ε = 0.25, 41.9% of head–temperature cells had a strictly smaller rSVDint(ε/3), although reductions were usually modest.The calibration evaluated 84 BERT-base heads across lengths 64, 128, 256, five temperature multipliers, and three errors.Source: §4.2 · p. 5
  • At multiplier one, effective dimension had Spearman associations 0.574 and 0.606 with two finite constructive rank upper certificates.The associations concern finite certificates, not the unknown optimum rε.Source: §4.2 · p. 5

5 Discussion and limitations

The discussion separates support geometry, which determines worst-case temperature scaling, from visible interaction geometry, which governs per-instance approximation complexity.

Discussion

  • Support shape determines normalized-attention temperature scaling, whereas the row-softmax quotient identifies geometry visible to a particular head.The first is a worst-case state-capacity statement; the second is a per-instance notion relaxable through projective residual.Source: §5 · p. 5

Limitations

  • The analytic Cr bound can carry 2^O(r) dependence and is therefore not numerically useful at learned-head dimensions r ≈ 50–64.Finite certificates are instead directly evaluated approximants.Source: §5 · p. 5
  • 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 also implies neither sparsity nor arithmetic speedup.Source: §5 · p. 5

A Weighted Gibbs covers with arbitrary positive base weights

The appendix proves weighted Gibbs covering bounds using convex geometry, establishes their operator interpretation, and converts row covers into rank certificates.

Operator interpretation

  • Maximum-row-ℓ1 error equals induced error on bounded vector-valued attention outputs for any nonzero normed value space.The reverse inequality uses a signed unit vector on a maximizing row.Source: A Weighted Gibbs covers with arbitrary… · p. 6

Spherical Gibbs cover

  • The weighted spherical Gibbs theorem provides an ℓ1 cover uniformly over alphabet size and all positive base weights.Its cardinality depends on fixed dimension, temperature, and error through the stated cover law.Source: A Weighted Gibbs covers with arbitrary… · p. 6

Convex-geometric proof

  • Convexity of a one-homogeneous extension makes the Gibbs function a support function of a compact convex body comparable to the Euclidean ball.The proof uses the Hessian criterion and bounds 1 ≤ h ≤ 3.Source: A Weighted Gibbs covers with arbitrary… · pp. 6–7
  • Support gaps control KL divergence, and fixed-dimensional polytope approximation followed by Pinsker yields the required ℓ1 cover.The construction is independent of N and the positive weight vector π.Source: A Weighted Gibbs covers with arbitrary… · p. 7

Rank construction

  • Representative rows produce a nonnegative row-stochastic approximant whose rank is bounded by the number of covering representatives.For rectangular attention matrices, the trivial cap becomes min{mQ, N}.Source: A Weighted Gibbs covers with arbitrary… · p. 7

Full-ball lift

B Exact quotient and robust residual theorem

Row-softmax removes row-scalar logits, leaving a visible interaction quotient that supports sharp rank bounds. Approximate subspaces add a residual output error before applying the projected Gibbs-cover bound.

Exact quotient

  • The visible interaction space is formed from query differences and projected key differences, with orthogonal key components becoming softmax-invisible.The remaining subspace V is contained in the query-difference span U.Source: B Exact quotient and robust residual… · p. 8
  • The quotient softmax perturbation is controlled by residual-logit oscillation, and its first bound is sharp.The likelihood-ratio argument identifies oscillation as the relevant projective distance.Source: B Exact quotient and robust residual… · p. 8

Robust residual theorem

  • For a dimension-r subspace W with residual error τW < ε, the projected Gibbs family admits a rank bound with shape term (1 + ΓW/(ε −τW)^2)r/2, capped by n.The residual consumes part of the output-error budget before covering the projected family.Source: B Exact quotient and robust residual… · p. 9

Exact quotient

Edge regimes

  • When β = 0, or when the relevant projected radius vanishes, rank one is exact; as τW approaches ε, only the trivial cap n remains guaranteed.The zero-temperature and zero-variation regimes collapse the rows to a common structure.Source: B Exact quotient and robust residual… · p. 9

C SVD bridge and tolerance-indexed effective interaction dimension

The robust interaction dimension can be indexed by an output-error tolerance and estimated reproducibly with nested SVD subspaces. However, SVD optimality for standard spectral objectives does not imply optimality for the robust attention bound.

SVD bridge

  • Mean-centering the visible-key matrix Z and taking its top-r right-singular subspace provides a reproducible nested candidate family.The residual matrix is Er = Z(I −Pr).Source: C SVD bridge and tolerance-indexed… · pp. 9–10
  • The spectral residual is controlled by the next singular value, yielding computable bounds on residual key width and the resulting perturbation.The spectral route uses σr+1(Z), while a directly computed residual-width bound can be tighter.Source: C SVD bridge and tolerance-indexed… · p. 10

Tolerance-indexed dimension

  • The tolerance-indexed interaction dimension is the minimum dimension of a subspace W whose residual error τW is at most τ.This defines the smallest visible interaction subspace meeting the requested output tolerance.Source: C SVD bridge and tolerance-indexed… · p. 10
  • At τ = 0, the tolerance-indexed dimension recovers dim V in exact arithmetic unless query variation is trivial.This connects the approximate dimension to the exact visible interaction space.Source: C SVD bridge and tolerance-indexed… · p. 10

Limitations

D Sharp spherical law

For spherical self-attention, support geometry determines a sharp worst-case approximation-rank law. The exponent comes from spherical covering and is capped by the number of tokens.

Setup

  • The quantity being maximized is the approximation rank of Aβ(X) over all n-token configurations on the sphere.The attention matrix uses logits proportional to β⟨xi,xj⟩.Source: D Sharp spherical law · p. 11

Proof mechanism

  • The upper bound uses a weighted spherical cover with uniform weights and caps the cover size by n.The lower bound constructs separated sphere centres whose attention matrix remains hard to approximate.Source: D Sharp spherical law · p. 11
  • For β ≥ 1, the spherical density near a query determines the reciprocal-density scale driving the lower construction.Rotational invariance reduces the estimate to a one-dimensional Laplace bound in t = 1 −⟨x,y⟩.Source: D Sharp spherical law · p. 11

Edge regimes

  • Rank one is exact at β = 0, while for bounded β the lower bound remains constant-order and matches the upper order.The construction also handles nondivisible token counts through balanced duplication.Source: D Sharp spherical law · pp. 11–12

E Full-ball finite lower theorem and interaction-exponent sharpness

Full-ball support adds a radial degree, producing a βd/2 worst-case law under a large-token condition. Separately, fixed visible interaction dimension r has a sharp βr/2 exponent.

Proof mechanism

  • The lower construction decodes Gaussian-concentrated attention rows into message groups, making the selected channel invertible under any sufficiently accurate approximant.Selection and decoding are contraction operations, so invertibility yields a rank lower bound.Source: E Full-ball finite lower theorem and… · p. 13, §E.1 · p. 14

Full-ball law

Finite certificate

  • The grouped construction realizes M = 17,850,625 messages with an analytically represented effective token count of about 1088,946.Grouping avoids materializing all duplicate tokens while preserving the asymptotic construction.Source: E Full-ball finite lower theorem and… · p. 13

Interaction sharpness

  • For visible interaction dimension r, bounded instances have n ≍r,ε βr/2 and approximation rank ≳r,ε βr/2.Their shape parameter satisfies Γ ≍r β.Source: §E.1 · pp. 13–14
  • Therefore the r/2 exponent in the exact interaction upper bound cannot be uniformly reduced.The construction has exact visible interaction dimension r in Rr+1.Source: §E.1 · pp. 13–14

F Learned-head certificate chain

The learned-head certificate chain combines deterministic robust bounds with finite constructive rank certificates, while distinguishing symbolic shape laws from evaluated approximants and aggregate calibration evidence.

Certificate chain

  • The deterministic chain for a fixed learned head and candidate dimension r organizes the quantities entering the robust upper bound.The chain is reported separately from aggregate BERT calibration because aggregate medians do not determine one representative head's full tuple.Source: F Learned-head certificate chain · pp. 14–15
  • Attention-SVD and representative-row quantities are constructive rank upper certificates at maximum row-ℓ1 error ε, whereas top-k is a sparsity budget.These quantities represent different guarantees and should not be conflated.Source: F Learned-head certificate chain · p. 15

Calibration scope

  • The BERT summary is an aggregate calibration over a fixed 84-head evaluation set, with no intended population-level inference.At multiplier one and ε = 0.25, the reported medians are rSVD int (ε/3) = 64, attention-SVD upper certificate 48, representative-row upper certificate 87.5, and top-k sparsity budget 45.Source: F Learned-head certificate chain · p. 15

Scope and positioning

  • The broad principle that intrinsic geometry can reduce kernel rank is established in related work, so the paper’s contribution is the narrower normalized-attention theorem package.Prior work covers intrinsic variety dimension, function-generated matrices, interaction structure, and attention-native rank under different objectives.Source: G Relation to neighboring theory · p. 15
  • The paper’s theorem package targets unrestricted uniform-output approximation rank, not algorithmic thinning, coresets, or other restricted representation classes.Related methods address algorithmic or subset-based approximations, while this framework uses maximum-row-ℓ1 approximation of normalized attention outputs.Source: G Relation to neighboring theory · p. 15
Loading 2608.28150v1…