cs.LGNov 2, 2026

Exact Fusion of Softmax Attention Heads Can Require Exponentially Many Atoms

Authors: Hiroyasu Usami, Keisuke Hara, Ayato Tsuboi, Naohiko Matsuda

Organizations: Department of Computer Science, Graduate School of Engineering, Chubu University, Kasugai, Aichi 487-8501, Japan · Heat Transfer Research Department, Research & Innovation Center, Mitsubishi Heavy Industries, Ltd., Takasago, Hyogo 676-8686, Japan

Abstract

Fusing independently normalized attention heads can increase the number of explicit key-value entries, or atoms, needed to preserve their output. We prove a sharp separation for Wd(q)=∑j=1dσ(qj)W_d(q)=\sum_{j=1}^dσ(q_j): its dd two-atom heads use 2d2d head-atom terms, whereas its minimum single-head representation has exactly 2d2^d atoms, even with arbitrary fixed replacement keys, scalar values, and positive masses. The same lower bound holds for every fixed uniform error below 1/21/2 on Rd\mathbb R^d, and the threshold is sharp. The proof uses exposed-key normal cones; exact equality on any nonempty open query domain inherits the bound. The resulting atom bound for a fixed head count is tight when that count divides dd. A normalized family retains its exponential exact minimum while approaching a constant on fixed-radius query balls. For pretrained-model caches, a classical affine-rank bound and a certified instance exclude exact vector preservation at a specified atom count. Learned-cache comparisons on two disjoint banks of 64 contexts show budget-dependent reversals and calibration effects.

Figures & tables

Explore similar work

Oct 12, 2026

Counting with Attention and LayerNorm: Norm Scaling and Representation Geometry

Counting is a simple task on which transformers can nevertheless fail at long sequence lengths. We study the cost of counting in a single attention layer, up to a maximum length LL, focusing on how softmax attention and layer normalization shape the representation from which the count is recovered. We mainly focus on regression read-out but also consider classification read-out. For regression, we show unnormalized linear attention counts exactly at parameter norms independent of LL. For softmax attention, regression cannot count exactly with finite parameters; it recovers the count after rounding, but only when the vector parameter norms grow with LL. We measure this cost by Bmin⁡B_{\min}, the smallest bound that can be placed on every trainable vector to ensure exact counting after rounding, and derive tight rates. At fixed model dimension, Bmin⁡B_{\min} grows as LL without normalization, as L3/2L^{3/2} under bare post-normalization, and as L3/4L^{3/4} with learned post-normalization. The last rate is unexpected: post-normalization discards the magnitude that carries the count and might be expected to make counting harder, yet with a learnable gain it counts at a smaller norm than softmax without normalization. Bare pre-normalization is different: it bounds the attention scores, so beyond a finite length no parameter norm suffices. A classification read-out keeps every norm bounded under every placement, but a dense head stores one output vector per count and costs more in storage. Experiments on the post-normalized model reproduce this split between the two read-outs. Together, our theoretical and empirical findings characterize how self-attention, layer-normalization placement, and read-out choice shape the representation geometry and parameter cost of counting in the minimal single-head architecture studied here.
Aug 11, 2026

Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention

How much feature rank does comparison require in kernel attention? On Min-IP over mm-bit tokens, rank one solves every sequence of length at most two exactly. At length three, the minimum feature rank of one normalized nonnegative kernel-attention head is 2Θ(m)2^{Θ(m)} for error strictly below 1/21/2 on every input, even with arbitrary finite-dimensional tokenwise values and query-dependent affine readouts. Dense softmax solves this three-token task with mm-dimensional scores and temperature constant in mm. For every fixed number of heads HH, the minimum total feature rank is 2ΘH(m)2^{Θ_H(m)} for the same error guarantee at exact length H+2H+2 in one attention layer with affine mixing. These bounds also hold with position-dependent maps and a final causal query. For one head with polynomial readout of fixed degree at most DD, rank one suffices at exact length D+1D+1, while exact length D+2D+2 requires exponential feature rank. With unrestricted exact-real decoding, a scalar rank-one construction solves the task at every finite length. This motivates a separate bound on total communication for deterministic models with finite-alphabet cross-token channels and any number of heads and layers. In this setting, correctness up to length nn requires Ω(nlog⁡m)Ω(n\log m) bits over a range of lengths that grows exponentially with mm.
Nov 4, 2026

Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds

Attention is central to modern AI models for language, vision, and scientific modeling. However, direct evaluation compares every query with every key, requiring quadratic time in the context length, which limits its scalability to long contexts. Consequently, characterizing the complexity bounds of attention is of fundamental importance. For every fixed dimension dd, we give an algorithm for mm queries, nn key-value pairs, and additive error ε\varepsilon, with expected time O~((mn)k/(k+1)+m+n),k=⌊d/2⌋.\widetilde{\mathrm{O}}\bigl((mn)^{k/(k+1)}+m+n\bigr),\qquad k=\lfloor d/2\rfloor. For fixed dimension and a fixed number of value channels, soft-O hides factors of the form poly⁡d(b,log⁡(m+n),log⁡B,log⁡(1/ε)),\operatorname{poly}_d\bigl(b,\log(m+n),\log B,\log(1/\varepsilon)\bigr), where bb bounds input encoding lengths and BB bounds coordinate and value magnitudes. In particular, the dependence on BB and 1/ε1/\varepsilon is polylogarithmic, which allows arbitrary positive temperature. When m=nm=n and d≥2d\ge2, the bound is O~(n2−2/(⌊d/2⌋+1))\widetilde{\mathrm{O}}(n^{2-2/(\lfloor d/2\rfloor+1)}): near-linear in dimensions two and three, with exponent 4/34/3 in dimensions four and five and 3/23/2 in dimensions six and seven. It improves the previous O~(n2−1/d)\widetilde{\mathrm{O}}(n^{2-1/d}) upper bound and matches the best known batch maximum-inner-product bound in each fixed dimension. Additionally, we reduce integer batch maximum inner product computation to one attention call with the same dimension and input sizes m,nm,n.