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
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): its d two-atom heads use 2d head-atom terms, whereas its minimum single-head representation has exactly 2d atoms, even with arbitrary fixed replacement keys, scalar values, and positive masses. The same lower bound holds for every fixed uniform error below 1/2 on Rd, 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 d. 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
Study
Target and interface
Guarantee or counted resource
Jordan–Jacobs [ 1 ]
Hierarchical conditional expert mixtures
Logistic gates and hierarchical products; construction background.
Haverbeck et al. [ 2 ]
Joint KV replacement, including new atoms and positive masses
Query-distribution approximation risk; broader than support-subset eviction.
Haris–Onak [ 5 ]
Worst-case autoregressive streaming
Memory bits with probabilistic guarantees.
Hsu–Xu [ 6 ]
Multi-task attention computation
Head count, dimension, precision, and threshold-degree tradeoffs.
Yu et al. [ 7 ]
Varying sequences, trainable encoders and post-attention networks
Transformer parameter approximation rates.
Amsel et al. [ 8 ]
Retrieval with varying contexts and queries
Rank, head-count, and weight-norm barriers.
TABLE I: Closest results grouped by target, interface, and counted resource.
Fig. 1: Attainment, convexity obstruction, and fixed-head atom budgets. (a) Eight unit-mass cube atoms realize W3 ; three two-atom heads use six head–atom terms. Vertex labels are scalar values, taking four distinct values. (b) The strict-winner cone for k0=0 against keys (−3,−2),(−2,−3) contains u=(−1,2) and v=(2,−1) with r=1 , and their midpoint w=(1/2,1/2) with r=2 . One winning key gives one constant ray limit throughout its cone, requiring ε≥1/2 . Shading shows the clipped closure; dashed boundaries and the origin are excluded. (c) The curve is H212/H ; filled markers attain it for H∣12 . Counts are head–atom terms.
d
Mexact
Head terms
E1
1
2
2
0.231059
2
4
4
0.122459
4
16
8
0.062177
8
256
16
0.031209
16
65536
32
0.015620
TABLE II: Closed-form theoretical comparison for Fd,1/d on ∥q∥2≤1 . All cube keys have norm at most one and values lie in [0,1] . Mexact is the minimum single-head atom count; head terms count the coordinate construction. E1 is the optimal one-atom uniform error. Values follow the closed forms of Proposition 7.
Fig. 2: Controlled readouts. Top: observed normalized maximum error for the fixed two-atom mean baseline, evaluated on paired finite query banks in boxes. Bottom: FP64 storage used by each method’s K/V arrays. Exact-method errors across all banks are at most 7.04×10−13 .
Method
Terms
KV (KiB)
Cube head
4096
416.000
Block size 2
24
0.562
Coordinate
24
0.375
Fixed mean
2
0.203
TABLE III: Controlled FP64 evaluation at d=12 , R=1 , with 4,608 queries. KV counts explicit array storage. The first three methods attain the fixed-head atom bound with H=1,6,12 , respectively. The fixed mean is a prespecified two-atom approximation.
Resource
Separate heads
Single head
Softmax normalizers
H
1
Atoms; log masses
Hn ; Hn
n ; n
Key and value width per atom
64 each
64H each
Query and output coordinates
Fixed 64D block per head
All 64H coordinates per atom
Mixture-weight sharing
Within each 64D output block
Across all 64H output coordinates
Key coefficients; value coefficients
64Hn ; 64Hn
64Hn ; 64Hn
TABLE IV: Resource allocation in the equal-byte learned comparison. Both architectures retain the same number of key/value coefficients and receive the same FP32 storage budget. Normalizer count, atom count, coordinate access, and weight sharing vary together, allowing different training arithmetic at the same memory budget.
H
n per head
KiB each
Cal. S
Cal. F
Held S
Held F
S lower
2
4
4.031
0.1901
0.2355
0.4948
0.4467
32/64
2
8
8.062
0.0573
0.1179
0.3363
0.5269
62/64
4
4
8.062
0.1550
0.2845
0.4855
0.5135
42/64
4
8
16.125
0.0463
0.2071
0.3657
0.4896
60/64
TABLE V: Learned compression with equal FP32 storage budgets. Each result uses all 64 prompts. Cal.: macro calibration NRMSE from FP32 exports; held: macro held-out NRMSE from FP32 records selected by calibration error. Lower is better. S/F denote separate/single-head fits. Separate/single allocations retain Hn / n total atoms. Fits use 512 updates and four starts; Table IV details the resource allocation.
Early
Distributed
n
KiB
S
F
S
F
4
4.031
0.4967
0.4809
0.4717
0.4711
8
8.062
0.3644
0.5734
0.3515
0.4817
TABLE VI: Calibration-policy follow-up on 64 unused contexts. Held-out NRMSE is averaged equally across prompts on the common bank of final-16 queries. S/F: separate/single-head fits.
Fig. 3: Native capacity and calibration on the second, disjoint 64-context bank. (a) The original two-head cache realizes its target with a 16 KiB KV payload. Gray points are classical affine-rank error floors for arbitrary 16-atom single heads with the same KV payload and free masses, evaluated on 32 early queries per context; the red bar is their mean. (b,c) Macro error on the common final-16-query bank when the 32 calibration queries are early or distributed. Both architectures improve at both fitted-cache budgets.
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 L, 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 L. 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 L. We measure this cost by Bmin, 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 grows as L without normalization, as L3/2 under bare post-normalization, and as L3/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.
How much feature rank does comparison require in kernel attention? On Min-IP over m-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) for error strictly below 1/2 on every input, even with arbitrary finite-dimensional tokenwise values and query-dependent affine readouts. Dense softmax solves this three-token task with m-dimensional scores and temperature constant in m. For every fixed number of heads H, the minimum total feature rank is 2ΘH(m) for the same error guarantee at exact length H+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 D, rank one suffices at exact length D+1, while exact length D+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 n requires Ω(nlogm) bits over a range of lengths that grows exponentially with m.
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 d, we give an algorithm for m queries, n key-value pairs, and additive error ε, with expected time O((mn)k/(k+1)+m+n),k=⌊d/2⌋. For fixed dimension and a fixed number of value channels, soft-O hides factors of the form polyd(b,log(m+n),logB,log(1/ε)), where b bounds input encoding lengths and B bounds coordinate and value magnitudes. In particular, the dependence on B and 1/ε is polylogarithmic, which allows arbitrary positive temperature. When m=n and d≥2, the bound is O(n2−2/(⌊d/2⌋+1)): near-linear in dimensions two and three, with exponent 4/3 in dimensions four and five and 3/2 in dimensions six and seven. It improves the previous O(n2−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,n.
Zixuan Huang, Guozhang Chen
State Key Laboratory of Multimedia Information Processing, School of Computer Science, Peking University, Beijing, China · School of Physics, Peking University, Beijing, China · National Engineering Research Center of Visual Technology, School of Computer Science, Peking University, Beijing, China