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.

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

  • Results

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

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

  • Takeaways & Limitations

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

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

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.
  • 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ε.
  • Sphere and full-ball laws: 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.

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.
  • Exact quotient: 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.
  • 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).
  • 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.
  • Approximate subspaces: 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.

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.
  • 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.
  • Learned-head calibration: 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ε.

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.
  • 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.
  • Limitations: 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.

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.
  • 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.
  • 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.
  • Convex-geometric proof: 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 π.
  • 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}.
  • Full-ball lift: A weighted full-ball lift embeds the problem into one higher spherical dimension, while zero-radius cases reduce to exact rank one.The lift preserves inner products exactly.

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.
  • Exact quotient: 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.
  • 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.
  • Exact quotient: Choosing W = V eliminates residual key components, so the robust theorem reduces to the exact interaction-quotient theorem.In this case τV = 0.
  • 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.

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).
  • SVD bridge: 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.
  • 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.
  • Tolerance-indexed dimension: 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.
  • Limitations: Top-r SVD is optimal for usual key-matrix spectral or Frobenius objectives but need not minimize the robust product δQ,WωK,W or its full bound.The tolerance is an output-error tolerance, not explained variance.

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⟩.
  • 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.
  • Proof mechanism: 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⟩.
  • 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.

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.
  • Full-ball law: For fixed d and ε, full-ball approximation rank is Θd,ε(βd/2) when β ≥ β0(d,ε) and n ≥ Cd eβ/8.The finite lower certificate uses bounded tokens and a discrete-Gaussian message construction.
  • 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.
  • 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 β.
  • Interaction sharpness: 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.

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.
  • Certificate chain: 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.
  • 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.
  • 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.
  • Scope and positioning: 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.
Loading 2608.28150v1…