Paper deep dive
Kernelized Linear Attention: Breaking the Capacity Wall with Symmetric Cones
Ayoub Ghriss, Sourav Chakraborty
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/21/2026, 5:01:39 AM
Summary
The paper introduces Kernelized Linear Attention Activations (KATA), a framework that addresses the capacity limitations of linear attention by formulating attention recall as a spherical-packing problem. By deriving feature maps from self-dual homogeneous cones (specifically the PSD cone), KATA achieves a favorable capacity-interference tradeoff, enabling exponential key capacity in the projection dimension. The authors provide theoretical bounds on associative recall and demonstrate that KATA variants outperform Gated DeltaNet and approach softmax performance with significantly reduced KV-cache requirements, while offering high-throughput Triton kernel implementations.
Entities (8)
Relation Signals (6)
KATA → uses → PSD Cone
confidence 95% · Building on this observation, we show that rank-one positive semi-definite (PSD) features offer a favorable capacity–interference tradeoff.
KATA → implements → Triton
confidence 92% · We implement KATA as fused Triton kernels
KATA → outperforms → Gated DeltaNet
confidence 90% · On long-range MQAR and repeated-key overwrite, several KATA variants outperform Gated DeltaNet
KATA → achievesthroughput → FlashAttention-2
confidence 88% · up to ~1.6x FlashAttention-2 throughput
PSD Cone → enables → Exponential Capacity
confidence 85% · admits spherical codes with exponentially many keys in the projection dimension
KATA → reduces → KV-cache entries
confidence 80% · approaching the softmax with roughly one quarter of the KV-cache entries
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Linear attention promises constant-time recurrent inference but degrades sharply on associative recall. We formulate attention recall as a spherical-packing problem and introduce Kernelized Linear Attention Activations (KATA), a framework whose feature maps are derived from first principles by certifying nonnegative attention weights through a self-dual homogeneous cone. Building on this observation, we show that rank-one positive semi-definite (PSD) features offer a favorable capacity--interference tradeoff. KATA recovers a parameter-free convex output gate and characterizes associative capacity through the Welch interference floor. For tolerances above this floor, KATA enlarges the state without adding parameters and admits spherical codes with exponentially many keys in the projection dimension. We implement KATA as fused Triton kernels at two operating points: a flash-attention-style forward up to ${\sim}1.6\times$ FlashAttention-2 throughput, and an exact $O(T)$ chunked-state form that reaches ${\sim}11\times$ FlashAttention-2 forward throughput at $131$k tokens. An associative scan of the first-order feature lowers the inter-chunk recurrence depth to $O(\log(T/C))$ for chunk size $C$ and averages ${\sim}2.4\times$ the throughput of a matched sequential linear-attention baseline. On long-range MQAR and repeated-key overwrite, several KATA variants outperform Gated DeltaNet, with parameter counts and state sizes reported alongside accuracy. Induction preserves near-perfect recall, while kernel benchmarks show that the maps can be implemented efficiently. KATA retains $0.985$ MQAR at a $16\times$ out-of-distribution length, approaching the softmax with roughly one quarter of the KV-cache entries. Experiments on 340M-parameter LLMs reveal a feature-dependent fluency trade-off and clarify how positional embeddings, delta rules, and decay gates interact with feature geometry.
Tags
Links
- Source: https://arxiv.org/abs/2607.17419v1
- Canonical: https://arxiv.org/abs/2607.17419v1
Trouble viewing inline? Open PDF directly →
Full Text
144,649 characters extracted from source content.
Expand or collapse full text
Kernelized Linear Attention: Breaking the Capacity Wall with Symmetric Cones Ayoub Ghriss Corresponding author. Sourav Chakraborty Abstract Linear attention promises constant-time recurrent inference but degrades sharply on associative recall. We formulate attention recall as a spherical-packing problem and introduce Kernelized Linear Attention Activations (KATA), a framework whose feature maps are derived from first principles by certifying nonnegative attention weights through a self-dual homogeneous cone. Building on this observation, we show that rank-one positive semi-definite (PSD) features offer a favorable capacity–interference tradeoff. KATA recovers a parameter-free convex output gate and characterizes associative capacity through the Welch interference floor. For tolerances above this floor, KATA enlarges the state without adding parameters and admits spherical codes with exponentially many keys in the projection dimension. We implement KATA as fused Triton kernels111https://github.com/ayghri/kata at two operating points: a flash-attention-style forward up to ∼1.6× 1.6× FlashAttention-2 throughput, and an exact O(T)O(T) chunked-state form that reaches ∼11× 11× FlashAttention-2 forward throughput at 131131k tokens. An associative scan of the first-order feature lowers the inter-chunk recurrence depth to O(log(T/C))O( (T/C)) for chunk size C and averages ∼2.4× 2.4× the throughput of a matched sequential linear-attention baseline. On long-range MQAR and repeated-key overwrite, several KATA variants outperform Gated DeltaNet, with parameter counts and state sizes reported alongside accuracy. Induction preserves near-perfect recall, while kernel benchmarks show that the maps can be implemented efficiently. KATA retains 0.9850.985 MQAR at a 16×16× out-of-distribution length, approaching the softmax with roughly one quarter of the KV-cache entries. Experiments on 340M-parameter LLMs reveal a feature-dependent fluency trade-off and clarify how positional embeddings, delta rules, and decay gates interact with feature geometry. 1 Introduction Transformer architectures (vaswani17attention) owe their dominance to softmax attention, whose exponential kernel supports near-perfect associative recall. The price is the (T2)O(T^2) training cost and the (T)O(T) KV cache at sequence length T, which has motivated a sustained body of linear-time alternatives and fixed-size recurrent states (katharopoulos20transformers; choromanski21performers; peng21rfa; sun23retentive; gu24mamba; dao24mamba2). Linear attention replaces the infinite feature map of exp(⟨,⟩) ( q, k ) with a finite ψ:ℝd→ℝnψ:R^d ^n_ψ and exposes the recurrent update t=t−1+ψ(t)t⊤ S_t= S_t-1+ψ( k_t) v_t . The price of constant state is memory collision: many key–value bindings must share a single fixed state, and retrieval degrades sharply on associative-recall tasks at long contexts (schlag21linear; jelassi24repeat; du25mom). Recent gated linear RNNs, including DeltaNet (yang24deltanet), Mamba2 (dao24mamba2), and Gated DeltaNet (yang25gateddeltanet), close part of the gap with learned forget gates, unnormalized linear writes, and content-addressed erase operations. Yet the geometry driving their feature maps remains opaque: what limits recall capacity at a fixed state size, and which post-Transformer designs operate below that limit? Must feature maps be nonnegative? Which finite maps preserve the isotropy of the softmax? Without principled answers, new linear attention architectures sit one ablation away from the existing menagerie of variants. Central finding. Memory collision is, at heart, the saturation of a spherical-packing problem. Once nonnegative attention weights are certified by a self-dual homogeneous cone and the latent geometry is required to be isometrically invariant, the Koecher–Vinberg classification (koecher57positivitatsbereiche; vinberg63homogeneous; faraut94analysis) organizes the admissible feature geometries into irreducible factors. We study the ordinary real families: the positive orthant, the Lorentz cone, and the symmetric positive semidefinite (PSD) cone. Their feature maps form the basis of our KATA (Kernelized Linear Attention Activations) framework. The denominator of normalized linear attention emerges natively as a parameter-free, token-conditioned convex output gate, so part of the structure typically introduced through explicit gating is already inherent to the normalized formulation. The choice of cone then determines the interference geometry and, through it, the associative capacity. To compare these geometries, we develop a power signal-to-noise ratio (pSNR) analysis based on the optimal interference attainable within each cone. Applying the same analysis to an exponential readout also yields a capacity law for softmax at arbitrary temperature. We support these predictions with efficient Triton implementations across a wide range of context lengths and with pretraining experiments on 340M-parameter language models. Together, the theory and experiments clarify how feature geometry interacts with positional embeddings, gating, the delta rule, and softmax attention. Working on the unit sphere. Throughout, we analyze query and key directions on the unit sphere. Explicit ℓ2 _2 normalization enforces this constraint directly. Under RMSNorm, the per-channel gains can instead be absorbed into a learned diagonal bilinear form and an inverse-temperature scale, leaving normalized directions in a lifted representation (Section˜A.1). This setting covers the query–key normalization used in Qwen3 (yang25qwen3), Gemma 3 (kamath25gemma3), and MiniMax-class (chen26minimax) models, as well as DeltaNet (yang24deltanet) and Gated DeltaNet (yang25gateddeltanet). The capacity bounds therefore describe the normalized address geometry used by these architectures. Contributions. 1. A cone classification for nonnegative linear attention. We characterize the ordinary real symmetric-cone feature geometries considered here under nonnegative attention weights, isometric invariance, and homogeneous latent geometry. 2. A capacity theory for associative recall. Casting recall as discrete spherical packing, we prove the Lorentz Rankin wall (Theorem˜9) and dimension-dependent packing bounds for PSD rank-one rays (Theorem˜4), give explicit finite dictionaries from mutually unbiased bases and DeVore frames, and derive an optimal-packing pSNR ladder whose geometric argument also applies to temperature-scaled softmax attention. 3. Hardware-aligned kernels. We release fused Triton kernels for the gate-free, delta-rule-free KATA-Mgg recurrence at two operating points. Its quadratic (T2)O(T^2) forward reaches up to ∼1.6× 1.6× FlashAttention-2 throughput (dao23fa2) and remains competitive on the training step. In the linear-state (T)O(T) form, KATA-M2 reaches parity with its quadratic counterpart near 1616k tokens, is faster by 3232k, and reaches ∼11× 11× FlashAttention-2’s forward throughput at 131131k; KATA-M1 is faster by 128128k. For the linear feature, an associative scan lowers the inter-chunk depth to (logNC)O( N_C) for NC≔⌈T/C⌉N_C T/C chunks and averages ∼2.4× 2.4× the throughput of a matched sequential linear-attention chunk. 4. Experimental evidence across scales. In the Zoology playground (arora23zoology), we evaluate multi-query associative recall, repeated-key overwrite, and induction under matched training configurations, reporting both parameter counts and state sizes. KATA-M1 retains 0.9850.985 MQAR accuracy at 16×16× the training context with roughly one quarter of softmax’s KV-cache entries at that length. We then pretrain matched 340M-parameter language models for 1515B tokens and evaluate both standard language-model benchmarks and in-context recall. The PSD variants remain broadly comparable on zero-shot accuracy while showing a meaningful perplexity spread, and they retain much more high-entropy needle signal than Gated DeltaNet, whose UUID recall falls to 0.0040.004. 2 Reproducing Kernel Hilbert Spaces for Linear Attention Linear attention (shen21efficient; katharopoulos20transformers) rests on a single algebraic substitution: replacing the exponential kernel of softmax with an inner product of finite features. This substitution allows the quadratic mixing of tokens to collapse into a recurrence on a fixed-size state. We make this substitution explicit and identify the geometric assumptions it imposes on the feature map. Constraining the feature image to a symmetric cone then resolves two design questions typically addressed through ad hoc heuristics: which finite maps are admissible and how normalization produces an output gate. Throughout, sequences have length T, with t,t∈ℝd q_t, k_t ^d and t∈ℝdv v_t ^d_v denoting the query, key, and value at token t. Their stacked tensors are ,∈ℝT×d Q, K ^T× d and ∈ℝT×dv V ^T× d_v. We write ψ:ℝd→ℝnψ:R^d\!→\!R^n_ψ for the feature map and Ψ() ( K) for its row-wise application. Causal softmax attention computes, per head: t=∑i=1texp(⟨t,i⟩)i⊤∑i=1texp(⟨t,i⟩). z_t\;=\; _i=1^t ( q_t, k_i )\, v_i _i=1^t ( q_t, k_i ). (1) Substituting the softmax kernel exp(⟨,⟩) ( q, k ) with a finite inner product ⟨ψ(),ψ()⟩ ψ( q),ψ( k) and using bilinearity yields the linearized form: t=ψ(t)⊤tψ(t)⊤t,t=∑i=1tψ(i)i⊤,t=∑i=1tψ(i), z_t\;=\; ψ( q_t) S_tψ( q_t) Z_t, S_t= _i=1^tψ( k_i) v_i , Z_t= _i=1^tψ( k_i), (2) with state pair (t,t)( S_t, Z_t) of size nψ(dv+1)n_ψ(d_v+1) for all t, and additive recurrence t=t−1+ψ(t)t⊤ S_t= S_t-1+ψ( k_t) v_t , t=t−1+ψ(t) Z_t= Z_t-1+ψ( k_t). The normalized readout is defined whenever its denominator ψ(t)⊤tψ( q_t) Z_t is positive. 2.1 Symmetric cones Let ⊂ℝnψK ^n_ψ be a closed convex cone. Its dual cone is defined as ∗=∈ℝnψ:⟨,⟩≥0∀∈K^*=\ y ^n_ψ: x, y ≥ 0\;∀ x∈K\ under the Euclidean inner product. K is pointed if ∩(−)=0K∩(-K)=\0\, full-dimensional if int()≠∅int(K)≠ , self-dual if =∗K=K^*, and homogeneous if its automorphism group acts transitively on int()int(K). K is a symmetric cone if it is self-dual and homogeneous. Throughout this paper, we work under the following three assumptions: Assumption 1 (Self-dual nonnegative geometry). ψ(ℝd)⊂=∗ψ(R^d)⊂K=K^*. Consequently, ⟨ψ(),ψ()⟩≥0 ψ( x),ψ( y) ≥ 0 for all , x, y. Assumption 2 (Isometric invariance). For every ∈(ℝd) U∈O(R^d) there exists an inner-product-preserving map T_ U on K such that ψ()=ψ()ψ( U x)=T_ Uψ( x). Assumption 3 (Homogeneity). Aut()Aut(K) acts transitively on int()int(K). 2.2 The denominator is a parameter-free convex gate Earlier work on linear attention enforced the nonnegativity in Assumption˜1 through the feature map ψ()=ELU()+1ψ( x)=ELU( x)+1 (katharopoulos20transformers), whereas Efficient Attention (shen21efficient) omitted the denominator ψ(t)⊤tψ( q_t) Z_t. Later recurrent architectures instead introduced explicit recurrence-level gates, including the hardware-friendly vector gate of Gated Linear Attention (GLA) (yang24gla) and the scalar decay of Mamba2 (dao24mamba2). Under Assumption˜1, we show that the discarded denominator already supplies a token-conditioned output gate. Proposition 1 (Output-level gating). Fix t q_t and write: Dt−1=ψ(t)⊤t−1,ct=ψ(t)⊤ψ(t),Dt=Dt−1+ct.D_t-1=ψ( q_t) Z_t-1, c_t=ψ( q_t) ψ( k_t), D_t=D_t-1+c_t. Suppose Dt>0D_t>0. If Dt−1>0D_t-1>0, define ¯t|t−1=ψ(t)⊤t−1/Dt−1 z_t|t-1=ψ( q_t) S_t-1/D_t-1. Then: t z_t =αt(t)¯t|t−1+βt(t)t⊤, = _t( q_t)\, z_t|t-1+ _t( q_t)\, v_t , (3) αt _t =Dt−1Dt,βt=ctDt, = D_t-1D_t, _t= c_tD_t, (4) with αt,βt≥0 _t, _t≥ 0 and αt+βt=1 _t+ _t=1. If Dt−1=0D_t-1=0, including t=1t=1, then t=t⊤ z_t= v_t and the same weights reduce to (αt,βt)=(0,1)( _t, _t)=(0,1). The normalized readout is therefore a convex interpolation between the previous readout and the current value, with query-dependent weights and no additional learned parameters. The gate acts at readout, leaving the state update commutative and additive. Gated DeltaNet controls memory through the rank-one state transition (yang25gateddeltanet): t=gt(−βttt⊤)t−1+βttt⊤, S_t=g_t( I- _t k_t k_t ) S_t-1+ _t k_t v_t , which uses extra projections and produces a noncommutative transition. 2.3 Koecher–Vinberg classification (a) Positive orthant ℝ+3R^3_+. (b) Lorentz cone ℒ+3L^3_+. (c) PSD cone +2S^2_+. Figure 1: Ordinary real symmetric-cone geometries in ℝ3R^3. The PSD cone +2S^2_+ is linearly isomorphic to the Lorentz cone ℒ+3L^3_+. Isometric invariance from Assumption˜2 promotes the softmax identity exp(⟨,⟩)=exp(⟨,⟩) ( U x, U y )= ( x, y ) to the kernel space. On its own, it does not single out K but guarantees that ψ is T_ U-equivariant: the input-space isometry ∈(ℝd) U∈O(R^d) and the cone-space isometry ∈(ℝnψ)|T_ U∈O(R^n_ψ)|_K intertwine through ψ. Homogeneity in Assumption˜3 means that any interior point can be mapped to any other by a cone automorphism. Thus the latent geometry has no privileged interior region or structural bottleneck, a useful symmetry when learning a map into K. Assumptions˜1 and 3 place K within the scope of the classical Koecher–Vinberg theorem, while Assumption˜2 constrains how input rotations act on its factors. The full classification also contains complex Hermitian, quaternionic Hermitian, and exceptional factors. We restrict this work to the ordinary real factors listed below. Theorem 2 (Koecher–Vinberg decomposition (koecher57positivitatsbereiche; vinberg63homogeneous; faraut94analysis)). Let ⊂ℝnψK ^n_ψ be a pointed, full-dimensional closed convex cone. If K is self-dual and homogeneous, then it is a symmetric cone and decomposes uniquely, up to isometry and factor order, as a Cartesian product of irreducible symmetric cones. The irreducible factors studied here are: (O)ℝ+,(L)ℒ+m=(,t)∈ℝm−1×ℝ:∥2≤t,m≥3,(S)+m=∈ℝm×m:⪰0 and =⊤,m≥2. cases (O)&R_+,\\ (L)&L^m_+=\( y,t) ^m-1×R: y _2≤ t\,\ m≥ 3,\\ (S)&S^m_+=\ A ^m× m: A 0 and A= A \,\ m≥ 2. cases Classical feature maps We can map raw projected keys and queries to the positive orthant via ReLU()+ϵReLU( x)+ε for some ϵ>0ε>0, or via ELU()+1ELU( x)+1 as in linear attention (katharopoulos20transformers). For the Lorentz cone, ψL()=(,∥2)ψ^L( y)=( y, y _2) lies on the boundary of ℒ+d+1L^d+1_+ for ≠0 y≠ 0, and Cauchy–Schwarz inequality yields: ⟨ψL(),ψL()⟩=⟨,⟩+∥2∥2≥0. ψ^L( x),ψ^L( y) = x, y + x _2 y _2≥ 0. If ∥2=1 x _2=1, then ∥ψL()∥22=⟨ψL(),ψL()⟩=2∥22=2 ψ^L( x) _2^2= ψ^L( x),ψ^L( x) =2 x _2^2=2. Thus 2−1/2ψL()2^-1/2ψ^L( x) lies on the unit sphere. For the PSD cone +mS^m_+, a classical choice is the LDL parameterization, which represents any ∈+m A∈S^m_+ as =AAA⊤ A= L_A D_A L_A , where A D_A is diagonal and A L_A is unit lower triangular. Then: ⟨,⟩=Tr(AAA⊤BBB⊤)=‖B1/2B⊤AA1/2‖F2. A, B =Tr\! ( L_A D_A L_A L_B D_B L_B )= \| D_B^1/2 L_B L_A D_A^1/2 \|_F^2. These canonical maps establish nonnegative kernels for each real factor considered here. We next turn from admissible feature geometry to the number of key addresses that each cone can separate. 3 Capacity of Symmetric Cones The cone classification identifies admissible nonnegative feature geometries, but not how many key addresses a fixed feature dimension can distinguish. Let ⊂ℝdK ^d be a cone and place T unit-norm feature vectors on ∩d−1K∩S^d-1. We quantify their worst collision by the interference: μ(,T)≔min1,…,T⊂∩d−1maxi≠j|⟨i,j⟩|,μ(K,T) _\ ψ_1,…, ψ_T\⊂K∩S^d-1 _i≠ j | ψ_i, ψ_j |, (5) and define the ϵε-capacity: ϵ()≔supT∈ℕ:μ(,T)≤ϵ. C_ε(K) \T :μ(K,T)≤ε\. (6) This is precisely the mutual coherence of the feature dictionary (donoho03optimally). It isolates the geometry of distinguishable key addresses before specifying values or retrieval dynamics. Theorem 3 (Welch bound (welch74lower)). The d coordinate rays of ℝ+dR_+^d are pairwise orthogonal, so zero interference is attainable for T≤dT≤ d. For any T>dT>d unit vectors in ℝdR^d: μ(ℝd,T)2≥T−d(T−1).μ(R^d,T)^2≥ T-dd(T-1). (7) Consequently, if μ≤ϵ<1/dμ≤ε<1/ d, then T≤d(1−ϵ2)/(1−dϵ2)T≤ d(1-ε^2)/(1-dε^2). For T>dT>d, equality in the Welch inequality holds precisely when the vectors form an equiangular tight frame (ETF): tightness minimizes the average squared off-diagonal Gram entry, and equiangularity makes every off-diagonal modulus attain that average. The bound is therefore generally unattained. Real ETFs exist only for special pairs (d,T)(d,T) and satisfy T≤d(d+1)/2T≤ d(d+1)/2 (fickus16etf). Over ℂdC^d, the corresponding ceiling is d2d^2, although the representation uses 2d2d real scalars. We restrict the present analysis to real cones and leave complex extensions to future work. The orthant inherits the ordinary Welch floor after its d coordinate rays. For the Lorentz cone ℒ+dL_+^d, a normalized extreme ray has the form ψ=2−1/2(,1)ψ=2^-1/2( y,1) with ∈d−2 y∈S^d-2, and its kernel is FLor(z)=(1+z)/2F_Lor(z)=(1+z)/2. For 0≤ϵ<1/20≤ε<1/2, requiring feature interference at most ϵε forces ⟨i,j⟩≤−(1−2ϵ) y_i, y_j ≤-(1-2ε). Rankin’s bound therefore gives: ϵ(ℒ+d)≤mind, 1+11−2ϵ. C_ε(L_+^d)≤ \! \d,\,1+ 11-2ε \. The formal statement and proof appear as Theorem˜9 in Appendix˜C. 3.1 Rank-one packing into the PSD cone The LDL construction in Section˜2 represents an arbitrary matrix in +pS_+^p using: n=p(p+1)2n= p(p+1)2 (8) free coordinates. Directly parameterizing an arbitrary PSD atom would therefore require a learned query/key projection of width n. Packing does not require covering the entire cone: we can project once to ∈p−1 u∈S^p-1 and apply the deterministic rank-one lift: ψS()=⊤⪰0,∥⊤∥F=1,⟨⊤,⊤⟩F=(⊤)2.ψ^S( u)= u u 0, u u _F=1, u u , v v _F=( u v)^2. The learned projection emits only p coordinates, while the lifted feature still occupies the n-dimensional symmetric ambient space. Proposition˜7 shows that, among unit-Frobenius PSD atoms, rank-one matrices uniquely minimize the expected overlap under a Haar-random relative eigenbasis. This average-case optimality motivates the rank-one family; the following theorem gives its worst-case packing guarantee. Theorem 4 (PSD rank-one packing). Let p≥2p≥ 2, n=p(p+1)/2n=p(p+1)/2, and 0≤ϵ<10≤ε<1. Identify +pS_+^p with its n-dimensional Euclidean ambient space under the Frobenius inner product. The unit-Frobenius representatives of its extreme rays are rank-one matrices ⊤ u u with ∈p−1 u∈S^p-1, and their pairwise inner products satisfy: ⟨ii⊤,jj⊤⟩F=⟨i,j⟩2. u_i u_i , u_j u_j _F= u_i, u_j ^2. Hence PSD interference at most ϵε is equivalent to |⟨i,j⟩|≤ϵ| u_i, u_j |≤ ε, and a maximal greedy spherical-cap construction yields: ϵ(+p)≥12(1−ϵ)−(p−1)/2. C_ε(S_+^p)≥ 12(1-ε)^-(p-1)/2. (9) Applying Theorem˜3 to the raw vectors shows that PSD interference ϵ<1/pε<1/p forces T≤p(1−ϵ)/(1−pϵ)T≤ p(1-ε)/(1-pε). Rank-one PSD features therefore do not provide exponential capacity below the Welch floor. For any fixed tolerance ϵ∈(0,1)ε∈(0,1), once p>1/ϵp>1/ε the spherical-cap lower bound in Theorem˜4 is exponential in p. Squaring the raw inner product replaces the mutually obtuse constraint induced by the Lorentz lift with an unsigned near-orthogonal spherical code. The same p-dimensional projection can generate higher even-order features: ψ2r()=⊗2r,⟨ψ2r(),ψ2r()⟩=(⊤)2r≥0, _2r( u)= u 2r, _2r( u), _2r( v) =( u v)^2r≥ 0, whose symmetric ambient dimension is (p+2r−12r) p+2r-12r. We use the first nontrivial order, r=1r=1: as Section˜4 shows, the quadratic expanded state already dominates the hardware budget. 3.2 Constructive packing Table 1: Constructive packing requirements. Ambient dimension required for T=105T=10^5 under two interference targets. Method μ≤0.05μ≤ 0.05 μ≤0.20μ≤ 0.20 Welch d≥399d≥ 399 d≥25d≥ 25 Random d≈18,421d≈ 18,421 d≈1,151d≈ 1,151 MUB d=802d=802 (s=401s=401) d=634d=634 (s=317s=317) DeVore d=2,209d=2,209 (s=47s=47) d=361d=361 (s=19s=19) We give two deterministic finite dictionaries with explicit interference guarantees. The first realifies complete sets of complex mutually unbiased bases (MUBs), producing a dense dictionary whose size is quadratic in its real ambient dimension. restatable [MUB-derived real dictionary]theoremmubconstruct For any prime power s=ℓks= ^k, realification of a complete set of complex MUBs gives T=s(s+1)T=s(s+1) unit vectors in ℝdR^d, where d=2sd=2s, with: μ(ℝd,T)≤1s=2d.μ(R^d,T)≤ 1 s= 2d. This construction is useful when T=Θ(d2)T= (d^2) is sufficient and a uniform deterministic worst-case guarantee matters more than sparsity. The prime-power condition restricts the available dimensions. The full construction is given in Section˜C.5. When higher interference is tolerated, DeVore’s polynomial construction provides a larger and sparser dictionary. restatable [DeVore polynomial construction]theoremdevoreconstruct For any prime power s and integer 0≤r<s0≤ r<s, there is a sparse deterministic construction of T=sr+1T=s^r+1 unit vectors in ℝdR^d, where d=s2d=s^2, with maximum interference μ≤r/sμ≤ r/s. This construction is preferable when sparse storage or fast overlap computation matters more than the tighter interference of the MUB-derived dictionary. The proof is in Section˜C.6. The Johnson–Lindenstrauss (JL) lemma gives a related randomized asymptotic statement: T prescribed points can be embedded into d=(η−2log(T/δ))d=O(η^-2 (T/δ)) dimensions while preserving all pairwise distances within 1±η1±η with failure probability at most δ (johnson84extensions; achlioptas03database). The same concentration argument yields random spherical dictionaries with interference at most μ in d=(μ−2(logT+log(1/δ)))d=O(μ^-2( T+ (1/δ))) dimensions, or equivalently an achievable T=exp(Ω(μ2d))T= ( (μ^2d)) at fixed success probability. These asymptotic random-projection guarantees are often loose at the dimensions of individual attention heads. Deterministic constructions give exact finite dictionaries and worst-case interference guarantees in the regimes where they apply. The bounds and finite-size comparison are collected in Sections˜A.3 and 1. These constructions illustrate the available finite regimes, and better real spherical packings may exist. Determining which packings are best suited to attention heads is left to future work. 3.3 Signal-to-noise analysis Packing controls the score margin between a matched key and its distractors. Whether that margin is sufficient for retrieval depends on the readout. To isolate key interference, hold the attention coefficients fixed and take independent isotropic values j∼(0,dv/dv) v_j N(0, I_d_v/d_v). Then ∥j∥2=1E v_j ^2=1, the cross terms vanish in expectation, and for ()=∑jaj()j o( q)= _ja_j( q) v_j with matched index ⋆ : pSNR()≔∥a⋆⋆∥2∥∑j≠⋆ajj∥2=|a⋆|2∑j≠⋆|aj|2.pSNR( q) E a_ v_ ^2E _j≠ a_j v_j ^2= a_ ^2 _j≠ a_j ^2. (10) We call the readout ideally retrievable when pSNR>1pSNR>1, so the matched value has more power than the aggregate distractors. This criterion gives the expected power ratio under the isotropic-value model. Exact recall also depends on the realized values. Deterministic orthogonal unit values give the same identity when dv≥Td_v≥ T. restatable [Idealized Welch-scale retrieval]theoremoptimalsnr Let p≥2p≥ 2 and T>pT>p. Suppose the T−1T-1 distractors have squared correlations: ϵ⋆=T−p(T−1)ε = T-pp(T-1) with the matched query. Then: pSNRLin _Lin =1(T−1)ϵ⋆=pT−p, = 1(T-1)ε = pT-p, (11) pSNRPSD _PSD =1(T−1)(ϵ⋆)2=p2(T−1)(T−p)2. = 1(T-1)(ε )^2= p^2(T-1)(T-p)^2. (12) The criterion pSNR>1pSNR>1 gives linear retrieval only for T<2pT<2p, hence capacity Θ(p) (p). The PSD map squares distractor interference and extends the idealized threshold to Θ(p2) (p^2), showing how the rank-one lift converts the same address geometry into a larger retrieval regime. This comparison also exposes what changes when the readout is nonlinear: applying softmax to the same Welch-scale margin yields the following proposition. restatable [Softmax sharpening at the Welch scale]propositionsoftmaxsnr Under the setup of Section˜3.3, let μ⋆=ϵ⋆μ = ε and take the harmful distractor sign +μ⋆+μ . Temperature-τ softmax satisfies: pSNRSoft=exp(2(1−μ⋆)/τ)T−1.pSNR_Soft= (2(1-μ )/τ)T-1. (13) It is therefore ideally retrievable precisely when: T−1<exp(2(1−μ⋆)τ).T-1< \! ( 2(1-μ )τ ). (14) For T≫pT p, this gives the approximate capacity: TSoft(p,τ)≈1+exp(2(1−1/p)τ).T_Soft(p,τ)≈ 1+ \! ( 2(1-1/ p)τ ). (15) Equivalently, any finite target length with μ⋆<1μ <1 satisfies the criterion whenever: 1τ>log(T−1)2(1−μ⋆). 1τ> (T-1)2(1-μ ). (16) The softmax partition is common to all coefficients and cancels from pSNR; exponentiation then sharpens the remaining angular margin. Every fixed positive temperature gives a finite idealized capacity; for a fixed positive score margin, this capacity is exponential in 1/τ1/τ. Conversely, writing βT=1/τ _T=1/τ, an unconstrained inverse temperature removes any finite dimension-only ceiling, with βT=Θ(logT) _T= ( T) for a fixed positive margin. This recovers, from a complementary retrieval perspective, the critical logarithmic scale identified for long-context softmax dynamics by chen25longcontext. In our framework the law follows directly from Welch-scale interference and the pSNR criterion: the matched score must be amplified logarithmically to remain above the aggregate power of a growing number of distractors. Proofs are given in Sections˜C.7 and C.8. An alternative perspective on capacity comes from associative-memory theory, which asks how many patterns remain stable and retrievable under a specified update rule, noise model, and success criterion (krotov25mam). Higher-order and exponential interactions can raise these dynamical storage thresholds from polynomial to exponential regimes (krotov16dense; demircigil17model; lucibello24exponential). Our ϵε-capacity measures the quality of the address packing at a fixed interference tolerance. Under the idealized orthogonal-value readout above, that packing directly determines pSNR and hence whether associative recall succeeds. A nonlinear readout can amplify any positive target–distractor margin, while an exact collision remains irreducible. The specified update rule, noise model, and optimization then determine how closely empirical recall realizes this geometric capacity. 4 Hardware-Aligned Implementation The capacity story of Section˜3 is geometric, but its practical reach depends on how cleanly the feature map maps onto modern accelerators. Chunkwise parallel training is the standard scaffold for linear-time recurrent attention: split a length-T sequence into chunks of size C, yielding NC≔⌈T/C⌉N_C T/C chunks with the final chunk padded when necessary, run intra-chunk attention on tensor cores, and propagate the inter-chunk state by a sequential prefix sum (hua22transformerquality). FLA’s chunk-parallel linear attention (yang24fla) and Gated DeltaNet’s non-commutative Householder transition in the compact WY representation (schreiber89compactwy; yang25gateddeltanet) share this decomposition; what differs is the inter-chunk update. GDN requires a C×C\!×\!C triangular solve per chunk, expanding the per-token state into high-bandwidth memory (HBM) and tying chunk size to the solve’s conditioning. Mamba2’s data-dependent transition is likewise sequential at the chunk level. An additive feature-state recurrence avoids both costs and admits a parallel scan that lowers inter-chunk depth from Θ(NC) (N_C) to (logNC)O( N_C). 4.1 From rank-one rays to low-rank PSD packing From this point onward, unqualified references to a KATA mixer or KATA kernel denote PSD-resident features. Orthant and Lorentz variants are named explicitly. The full construction uses the rank-one map ψ()=⊤ψ( u)= u u . A direct outer-product layout has d2d^2 entries for head dimension d, or n=d(d+1)/2n=d(d+1)/2 unique coordinates after symmetry packing. Thus nψ=n_ψ=n for the full PSD map. Linear attention must retain the feature–value state: t=Ψ(1:t)⊤1:t∈ℝn×dv, S_t= ( K_1:t) V_1:t ^n× d_v, so its dominant storage is ndvnd_v; the feature width alone understates the memory cost. At d=64d=64, the direct and packed widths are already 40964096 and 20802080, respectively. Multiplication by dvd_v places the full PSD map at the edge of hardware-friendly state sizes even at this standard head dimension. We therefore test two reduced PSD families. Let g∈ℕg divide d, set m=d/gm=d/g, and partition each projected query or key into g blocks =(1,…,g) u=( u_1,…, u_g) with a∈ℝm u_a ^m. KATA-Σg g sums the block outer products into one PSD feature: ψΣg()=∑a=1gaa⊤∈+m,⟨ψΣg(),ψΣg()⟩F=∑a,b=1g(a⊤b)2. _ g( u)= _a=1^g u_a u_a ∈S_+^m, _ g( q), _ g( k) _F= _a,b=1^g( q_a k_b)^2. Its dominant state size is: m(m+1)2dv=(d/g)(d/g+1)2dv. m(m+1)2d_v= (d/g)(d/g+1)2d_v. Thus KATA-Σg g compresses g outer products into a single low-rank PSD factor. KATA-Mgg instead retains one PSD factor per block. The raw inner product decomposes as ⊤=∑a=1ga⊤a q k= _a=1^g q_a k_a, while the blockwise PSD map is: ψMg()=(11⊤,…,gg⊤)∈(+m)g,⟨ψMg(),ψMg()⟩=∑a=1g(a⊤a)2. _Mg( u)= ( u_1 u_1 ,…, u_g u_g )∈(S_+^m)^g, _Mg( q), _Mg( k) = _a=1^g( q_a k_a)^2. This maps into the Cartesian product of g copies of +d/gS_+^d/g and has dominant state size: gm(m+1)2dv=d(d/g+1)2dv.g m(m+1)2d_v= d(d/g+1)2d_v. Both families recover the full rank-one PSD map at g=1g=1. A Delta prefix adds the delta rule, a Gated prefix adds the learned gate, and GatedDelta combines both without changing the underlying PSD feature geometry. Their recurrences and implementation details are specified in Appendices˜D, D.3 and F.4. Chunkwise forward. Let nψn_ψ denote the active feature dimension. We partition the sequence into chunks of size C and write the per-chunk feature matrices as Ψ([t]),Ψ([t])∈ℝC×nψ ( Q_[t]), ( K_[t]) ^C× n_ψ and [t]∈ℝC×dv V_[t] ^C× d_v. The inter-chunk state update reads: [t+1]=[t]+Ψ([t])⊤[t],[t+1]=[t]+Ψ([t])⊤C. S_[t+1]= S_[t]+ ( K_[t]) V_[t], Z_[t+1]= Z_[t]+ ( K_[t]) 1_C. (17) With ∈0,1C×C M∈\0,1\^C× C the lower-triangular causal mask and =(Ψ([t])Ψ([t])⊤)⊙ P=( ( Q_[t]) ( K_[t]) ) M, the chunk output is: [t] N_[t] =Ψ([t])[t]+[t] = ( Q_[t]) S_[t]+ P\, V_[t] (18) [t] D_[t] =Ψ([t])[t]+ 1C = ( Q_[t]) Z_[t]+ P\, 1_C (19) [t] O_[t] =diag([t])−1[t] = diag( D_[t])^-1 N_[t] (20) Every operation in this pass is a dense general matrix multiplication (GEMM), an element-wise op, or a warp reduction. Relative to Gated DeltaNet’s WY representation, which forms and inverts a C×C\!×\!C unitriangular matrix per chunk, the inter-chunk cost drops from (Cdk2+dk2dv)O(Cd_k^2+d_k^2d_v) to (Cnψdv)O(Cn_ψd_v), and available SRAM sets the chunk-size limit. Triangular-solve conditioning no longer constrains it. The full pass is summarized in Algorithm˜1. 4.2 Tree-scan inter-chunk reduction [0],[0],[0] Q_[0], K_[0], V_[0] [1],[1],[1] Q_[1], K_[1], V_[1] [2],[2],[2] Q_[2], K_[2], V_[2] [3],[3],[3] Q_[3], K_[3], V_[3] Input Sequence Split into NCN_C chunks Length C [0]loc S_[0]^loc [1]loc S_[1]^loc [2]loc S_[2]^loc [3]loc S_[3]^loc Ψ([0])⊤[0] ( K_[0]) V_[0]Ψ([1])⊤[1] ( K_[1]) V_[1]Ψ([2])⊤[2] ( K_[2]) V_[2]Ψ([3])⊤[3] ( K_[3]) V_[3] Intra-Chunk State Computed in parallel Time: (C)O(C) ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ Associative Scan Parallel prefix replaces sequential recurrence. Time: (logNC)O( N_C) [0]pre= S_[0]^pre=0 [1]pre S_[1]^pre [2]pre S_[2]^pre [3]pre S_[3]^pre shiftshiftshift Inter-Chunk Prefix S[t]pre=∑c<tS[c]loc S^pre_[t]= _c<t S^loc_[c] Inter: Ψ([0])[0]pre ( Q_[0]) S_[0]^pre Intra: Ψ([0])Ψ([0])⊤,[0] ( Q_[0]) ( K_[0]) , V_[0] Inter: Ψ([1])[1]pre ( Q_[1]) S_[1]^pre Intra: Ψ([1])Ψ([1])⊤,[1] ( Q_[1]) ( K_[1]) , V_[1] Inter: Ψ([2])[2]pre ( Q_[2]) S_[2]^pre Intra: Ψ([2])Ψ([2])⊤,[2] ( Q_[2]) ( K_[2]) , V_[2] Inter: Ψ([3])[3]pre ( Q_[3]) S_[3]^pre Intra: Ψ([3])Ψ([3])⊤,[3] ( Q_[3]) ( K_[3]) , V_[3] Combine Chunks Time: (C2)O(C^2) [0] O_[0] [1] O_[1] [2] O_[2] [3] O_[3] AddAddAddAdd Final Embeddings Figure 2: Chunkwise associative scan. Each chunk forms its local state in parallel. An exclusive scan produces inter-chunk prefixes in ⌈log2NC⌉ _2N_C rounds, and each output kernel combines its prefix with the local C×C\!×\!C causal term. Only S is shown; Z follows the same scan. A useful observation is that the recurrence Equation˜17 is an associative prefix sum across the NCN_C chunks. Existing chunk-parallel implementations, including the FLA and Gated DeltaNet chunk paths, traverse this prefix sequentially with depth Θ(NC) (N_C). Because (loc,loc)( S_loc, Z_loc) is a vector-space cumulative sum, however, the same prefix admits a parallel scan with depth (log2NC)O( _2N_C). Our forward decomposes into three Triton kernels dispatched in series: a per-chunk state kernel with B⋅H⋅NCB\!·\!H\!·\!N_C programs in parallel, a cumulative pass that performs a associative scan in ⌈log2NC⌉ _2N_C rounds with NCN_C-wide parallelism per round, and a per-chunk output kernel that combines the inter-chunk prefix with the local C×C\!×\!C causal pattern. The resulting wall-clock model is: ttotal t_total =(Cnψdv)⏟state+(log2NC⋅dv)⏟tree-scan+(Cnψdv+C2(nψ+dv))⏟output, = O\! (Cn_ψd_v )\!_state+ O\! ( _2N_C· d_v )\!_tree-scan+ O\! (Cn_ψd_v+C^2(n_ψ+d_v) )\!_output, replacing the linear-scan baseline’s (NCdv)O(N_Cd_v) middle term. The nψn_ψ feature slices are independent and execute in parallel. At T=2048T=2048 and C=32C=32, the scan depth shrinks from NC=64N_C=64 to log2NC=6 _2N_C=6. Its arithmetic cost is negligible relative to the HBM write of loc S_loc at chunk boundaries, which is the actual bottleneck. Occupancy at small batch. The advantage is largest precisely where a sequential scan starves the GPU. At B=1B=1, the B⋅H=16B\!·\!H=16 programs of a sequential chunked scan, as in FLA or Gated DeltaNet, cannot fill the H100’s 132132 SMs, so the forward is occupancy-bound and plateaus near 2525 Mtok/s. The tree scan instead exposes B⋅H⋅NCB\!·\!H\!·\!N_C programs, which scale with the actual work. Figures˜3 and 11 report the full B×TB× T grid and its B=1B=1 slice, respectively. For the linear feature (ψ()=ψ( x)= x, with a matched d×d× d state), the associative scan delivers 1.91.9–2.9×2.9× the throughput of the sequential linear-chunk kernel from 20482048 to 131131k tokens, and up to 7.5×7.5× the throughput of Gated DeltaNet at T=2048T=2048. Figure 3: Forward throughput over B×TB× T. Associative scan, sequential scan, and Gated DeltaNet on H100. Why the PSD feature keeps to (T)O(T) or (T2)O(T^2). The tree scan is viable only for the linear feature. A PSD block of width m=d/gm=d/g has a direct outer-product feature dimension m2m^2, so a chunk’s local state ψ([c])⊤[c]ψ( K_[c]) V_[c] is an m2×dvm^2\!×\!d_v tile. It occupies 128128 KB at g=2g=2 (m2=1024m^2=1024) and already exceeds the H100’s 228228 KB shared-memory budget once the query feature and matrix-multiplication accumulators are resident. At g=1g=1 (m2=4096m^2=4096), it occupies 1.51.5 MB. A scan must moreover materialize every chunk’s state to HBM, requiring (NCm2dv)O(N_Cm^2d_v) storage traffic. We therefore do not tree-scan the PSD recurrence. KATA-Mgg runs either as a quadratic (T2)O(T^2) kernel, which never forms the m2m^2 state, or as a linear-state (T)O(T) kernel, whose m2×dvm^2\!×\!d_v state lives in HBM and is streamed in feature blocks. Realizing the parallel-prefix speedup for PSD features would require this feature blocking within the scan and is left to future work. Full timings and SRAM budgets are reported in Sections˜E.1 and E.3. 4.3 Synthetic induction and hardware microbenchmarks KATA-Σ2 2 solves a V=256V=256 induction-head probe at every distance up to 20482048 tokens within an 88k-step budget, matching or nearly matching softmax with FlashAttention-2 at every scale tested while avoiding the (T2)O(T^2) memory of dense attention (Section˜E.2). The fused rank-two KATA-Σ2 2 forward scales linearly with T at near-peak bandwidth without writing the per-token ψ tensor to HBM; full timings appear in Section˜E.3. Kernel latency and throughput ratios. Figure˜4 sweeps sequence length on an NVIDIA H100 for the two computational forms of the KATA-Mgg kernel. Across the tested lengths, the quadratic KATA-M1 forward delivers 1.31.3–1.6×1.6× the throughput of FlashAttention-2, while KATA-M2 delivers 1.21.2–1.4×1.4× the throughput. Both retain the same (T2)O(T^2) scaling. The exact linear-state PSD kernel instead trades an m2×dvm^2×d_v recurrent state, with m=d/gm=d/g, for (T)O(T) compute. KATA-M2 reaches parity with its quadratic counterpart near 1616K and is faster by 3232K; KATA-M1 is faster by 128128K. At 131131K, linear-state KATA-M2 reaches 11×11× FlashAttention-2’s forward throughput while implementing the exact PSD recurrence. Gated DeltaNet remains faster, but its raw-key feature loses high-entropy needle information (Table˜4). The measured latency scaling approaches 2×2× per doubling for the linear kernels and 4×4× for the quadratic kernels. Figure 4: KATA-Mgg latency versus sequence length on an NVIDIA H100. Forward latency (left) and forward-plus-backward latency (right) at B=8B=8, H=16H=16, dhead=64d_head=64, and bf16 on log–log axes. Solid curves are the (T2)O(T^2) kernels, FlashAttention-2 and quadratic KATA-Mgg; dashed curves are the (T)O(T) recurrences, Gated DeltaNet and linear-state KATA-Mgg. Lower is better; exact timings appear in Tables˜8 and 9. 5 Experiments The theory of Section˜3 predicts that associative-recall behavior separates by cone, and the kernel of Section˜4 makes the corresponding feature maps cheap to run. We test both predictions on three synthetic tasks that isolate distinct failure modes: multi-query associative recall (MQAR) with controlled length extrapolation, a repeated-key overwrite probe, and a long-range induction-head probe. We then scale the recall test to pretrained 340M-parameter language models with a needle-in-a-haystack suite. Only KATA variants instantiated on the PSD cone as described in Section˜4.1 are compared against vanilla linear attention (katharopoulos20transformers), Performer (choromanski21performers), DeltaNet (yang24deltanet), Gated DeltaNet (yang25gateddeltanet), Mamba2 (dao24mamba2), and softmax attention. Concrete KATA configurations are named by feature family, KATA-Σg g or KATA-Mgg. The prefixes Delta, Gated, and GatedDelta add the content erase, multiplicative state gate, or both; for example, GatedDeltaKATA-M2 places PSD features inside the Gated DeltaNet raw-key recurrence. Per-architecture details and reproduction recipes are in Sections˜F.4 and F. Experimental configurations and the early-stopping criterion are matched across methods. 5.1 Multi-query associative recall (MQAR) We use the canonical Zoology MQAR setup (arora23zoology). Training mixes streams up to Ktrain=64K_train=64 at T=256T=256; evaluation grids the OOD slice K∈128,256,512,768,1024K∈\128,256,512,768,1024\ over T∈512,…,4096T∈\512,…,4096\, so the largest evaluation slice is ×16× the longest training sequence and the largest training K. We report the best accuracy across the three-point sweep lr∈10−3,3×10−3,10−2lr∈\10^-3,3\!×\!10^-3,10^-2\. KATA-Orthant and KATA-Lorentz drop into the same backbone as every other row, varying only the feature map. Method dhd_h #params state (#dim) MQAR length extrapolation Repeated-key overwrite OOD Avg. ID OOD Avg. T=512T=512 T=1024T=1024 T=2048T=2048 T=3072T=3072 T=4096T=4096 K=64K=64 K=128K=128 K=256K=256 K=384K=384 Softmax attn. 64 1,132,928 1,048,576⋆ 1.000 1.000 1.000 1.000 1.000 1.000 0.513 0.506 0.499 0.491 0.502 Softmax+RoPE (θ=104θ=10^4) 64 1,132,928 1,048,576⋆ 0.994 0.658 0.134 0.036 0.012 0.367 0.998 0.890 0.403 0.160 0.613 Softmax+RoPE (θ=500θ=500) 64 1,132,928 1,048,576⋆ 0.741 0.046 0.000 0.001 0.001 0.158 0.991 0.670 0.140 0.025 0.457 RWKV7 64 1,162,880 8,192 0.709 0.224 0.051 0.022 0.013 0.204 0.820 0.341 0.084 0.030 0.319 Mamba2 64 1,217,548 16,384 0.845 0.413 0.173 0.094 0.054 0.316 0.930 0.556 0.199 0.127 0.453 GLA 64 1,154,624 8,192 0.900 0.496 0.151 0.067 0.038 0.330 0.768 0.317 0.082 0.030 0.299 DeltaNet 64 1,134,272 8,192 0.992 0.733 0.249 0.101 0.047 0.424 0.984 0.691 0.306 0.171 0.538 Gated DeltaNet 64 1,167,878 8,192 1.000 0.944 0.515 0.279 0.170 0.582 0.998 0.853 0.384 0.217 0.613 RWKV7 128 2,489,600 32,768 0.982 0.670 0.192 0.070 0.032 0.389 0.881 0.376 0.089 0.031 0.344 Mamba2 128 2,629,132 32,768 0.824 0.336 0.066 0.021 0.008 0.251 0.936 0.595 0.224 0.144 0.475 GLA 128 2,505,856 32,768 0.993 0.824 0.369 0.178 0.100 0.493 0.897 0.404 0.105 0.037 0.361 DeltaNet 128 2,432,384 32,768 1.000 0.990 0.526 0.244 0.138 0.580 1.000 0.971 0.585 0.347 0.726 Gated DeltaNet 128 2,565,126 32,768 1.000 0.997 0.670 0.352 0.186 0.641 1.000 0.978 0.595 0.358 0.733 RWKV7 256 2,489,600 65,536 1.000 0.986 0.661 0.332 0.175 0.631 0.938 0.434 0.110 0.038 0.380 GLA 256 5,798,144 65,536 1.000 0.996 0.902 0.689 0.491 0.816 0.927 0.450 0.132 0.050 0.390 DeltaNet 256 5,520,128 65,536 1.000 1.000 0.865 0.535 0.342 0.748 1.000 0.998 0.851 0.569 0.855 Gated DeltaNet 256 6,047,750 65,536 1.000 1.000 0.909 0.618 0.419 0.789 0.999 0.992 0.726 0.419 0.784 KATA-Σ4 4 64 1,134,016 17,408 1.000 0.997 0.865 0.610 0.407 0.776 0.517 0.493 0.364 0.226 0.400 KATA-Σ2 2 64 1,134,016 67,584 1.000 1.000 1.000 0.995 0.958 0.991 0.518 0.505 0.444 0.342 0.452 KATA-M4 64 1,134,016 69,632 1.000 1.000 0.982 0.877 0.707 0.913 0.515 0.484 0.346 0.219 0.391 KATA-M2 64 1,134,016 135,168 1.000 1.000 1.000 0.997 0.970 0.993 0.521 0.509 0.492 0.436 0.489 KATA-M2+RoPE 64 1,134,016 135,168 0.979 0.384 0.040 0.007 0.003 0.283 0.992 0.696 0.087 0.012 0.447 DeltaKATA-M2 64 1,134,272 135,168 1.000 1.000 1.000 0.995 0.955 0.990 1.000 0.999 0.992 0.922 0.978 GatedKATA-M2 64 1,134,276 135,168 1.000 1.000 1.000 0.996 0.965 0.992 0.991 0.662 0.193 0.074 0.480 GatedDeltaKATA-M2 64 1,134,532 135,168 0.979 0.699 0.258 0.119 0.062 0.423 1.000 0.999 0.983 0.859 0.960 KATA-M1 64 1,134,016 266,240 1.000 1.000 1.000 0.998 0.985 0.997 0.521 0.511 0.503 0.483 0.505 DeltaKATA-M1 64 1,134,272 266,240 1.000 1.000 1.000 1.000 0.999 1.000 1.000 1.000 0.999 0.998 0.999 Table 2: MQAR length extrapolation and repeated-key overwrite. Accuracy (higher is better); Avg. is the unweighted mean over the displayed settings. Model size and state dimension use the MQAR configuration. ⋆Softmax reports its KV-cache size at T=4096T=4096. Within each task and block, the best and second-best fixed-state results are shown in bold blue and underlined, respectively. In-distribution accuracy saturates for every fixed-state row, so the differences arise entirely on the out-of-distribution slices. The orthant and Lorentz baselines collapse just past K≈dheadK\!≈\!d_head, where the linear Welch and Rankin ceilings of Theorems˜9 and 3 predict. The PSD variants extend recall into the 16×16×-extrapolation regime. At the largest slice, KATA-M1 retains 0.9850.985 accuracy with a 266,240266,240-entry fixed state, roughly one quarter of softmax’s 1,048,5761,048,576 KV-cache entries; DeltaKATA-M1 reaches 0.9990.999 at the same state size. GatedDeltaKATA-M2 exposes the recurrence trade-off: its average overwrite accuracy rises to 0.9600.960, while its MQAR average falls to 0.4230.423. The convex-gate ablation, which caps ∥t∥F S_t _F inside the convex hull of instantaneous bindings, halves the OOD accuracy of the additive form (full table in Appendix˜F). 5.2 Repeated-key overwrite Each of K unique keys is written twice with two different values, and the model must retrieve the most recent binding. Training mixes K∈4,8,16,32K∈\4,8,16,32\ at sequence lengths up to 256256; evaluation extends to K∈64,128,256,384K∈\64,128,256,384\ with T≤3072T≤ 3072. The backbone is the two-layer Zoology transformer with a width-33 convolutional mixer, parameter-matched across rows. For a repeated key, an additive state writes both values along the same feature direction and therefore contains a term proportional to ψ()(old+new)⊤ψ( k)( v_old+ v_new) . The readout at that address sees their superposition without temporal information. RoPE resolves the ambiguity in-distribution by assigning the two writes different position-dependent features. Because this benchmark always targets the latest write, the model learns to favor the most recent association. In a general retrieval problem, the earlier association may remain correct, and this learned recency preference can select the newer value. The positional shortcut also extrapolates poorly in Table˜2, where both softmax+RoPE and KATA-M2+RoPE deteriorate rapidly beyond the training distribution. The convex output gate of Proposition˜1 acts at readout and leaves the relative contributions stored in t S_t unchanged. GatedKATA places its learned scalar inside the recurrence. Unrolling t=γtt−1+ψ(t)t⊤ S_t= _t S_t-1+ψ( k_t) v_t gives: t=∑s=1t(∏r=s+1tγr)ψ(s)s⊤. S_t= _s=1^t ( _r=s+1^t _r )ψ( k_s) v_s . The recurrent gate assigns every write a multiplicative, token-dependent positional weight. At K=64K=64, this weighting raises overwrite accuracy from 0.5210.521 for KATA-M2 to 0.9910.991 for GatedKATA-M2. The result supports a positional interpretation of the scalar gate, while state magnitude control plays a secondary role. Since the product usually shrinks with age, the gate favors recent writes. The delta rule corrects the value stored at the current content address. For a unit-norm feature, let ^t=t−1⊤ψ(t) v_t= S_t-1 ψ( k_t) be the value currently retrieved at t k_t. The update is: t=t−1+βtψ(t)(t−^t)⊤. S_t= S_t-1+ _tψ( k_t) ( v_t- v_t ) . When βt=1 _t=1, reading the same address after the update returns t v_t exactly. When the earlier association should be preserved, a learned βt _t can suppress the correction. The update strength therefore controls content-dependent replacement at each write. DeltaKATA-M1 is nearly perfect across the overwrite sweep, while GatedDeltaKATA-M2 reaches 0.9600.960 average overwrite accuracy. Full recurrence details are given in Section˜D.3. 5.3 Pretraining 340M-parameter language models To test whether the synthetic results persist under realistic pretraining, we train a family of 340M-parameter models (2424 layers, dmodel=1024d_model=1024, 1616 heads) for 1515B tokens of SlimPajama (soboleva23slimpajama) with the TinyLlama tokenizer (zhang24tinyllama) at a 20482048-token context, holding everything fixed and swapping only the token-mixing layer: softmax attention, Gated DeltaNet, KATA-M1 and KATA-M2 (RoPE positions, RMSNorm on , q, k), DeltaKATA-M1 (KATA-M1 with a DeltaNet content erase), and ℓ2 _2-norm and short-conv ablations. The models remain broadly comparable on zero-shot accuracy, while perplexity reveals a meaningful fluency spread (Table˜3). KATA-M1 trails softmax attention, Gated DeltaNet, and DeltaKATA-M1 on both perplexity datasets; KATA-M2 is higher still. The recall evaluations therefore separate direct association from contextual retrieval: NIAH primarily probes stored bindings, while FDA and SQuAD also require context interpretation and candidate selection. Method Perplexity ↓ Accuracy ↑ LMBD WikiT LMBD ARC-e ARC-c HeSw PIQA Wino BoolQ Softmax attn. 38.6 27.6 0.334 0.412 0.234 0.346 0.645 0.503 0.584 Gated DeltaNet 40.7 28.4 0.316 0.393 0.223 0.349 0.639 0.519 0.562 KATA-M1 43.5 29.1 0.319 0.399 0.222 0.340 0.642 0.519 0.585 DeltaKATA-M1 42.5 28.1 0.309 0.403 0.208 0.343 0.641 0.502 0.597 KATA-M2 51.8 30.0 0.281 0.385 0.230 0.331 0.635 0.512 0.614 ablations: ℓ2 _2-norm (KATA-M2) 57.1 32.2 0.277 0.389 0.230 0.323 0.627 0.499 0.598 short-conv, no RoPE (KATA-M2) 84.6 34.0 0.233 0.363 0.230 0.313 0.625 0.509 0.615 Table 3: Pretraining quality of the 340M models. For word-level perplexity, lower is better; for zero-shot accuracy, higher is better (acc_norm for ARC and HellaSwag, acc otherwise; LMBD is LAMBADA). Bold marks the best sub-quadratic result in the columns discussed in the text. Why the delta rule remains useful with RoPE. RoPE assigns repeated occurrences of the same key different phases, so it can in principle resolve overwrite within the 20482048-token training window. The resulting separation depends on the attention kernel. Consider an aligned unit query and key in one rotary plane with angular rate ω and relative offset Δ=|j−i| =|j-i|. Relative to Δ=0 =0, the KATA and softmax factors are: rKATA(Δ)=cos2(ωΔ),rsoftmax(Δ)=exp(cos(ωΔ)−1τ).r_KATA( )= ^2(ω ), r_softmax( )= \! ( (ω )-1τ ). For dhead=64d_head=64, RMS-normalized query and key vectors have norm approximately dhead d_head before learned per-channel gains. Combined with the standard 1/dhead1/ d_head logit scaling, this gives an effective τ≈1/dhead=1/8τ≈ 1/ d_head=1/8 on normalized directions (Section˜A.1). Taking the nominal slow rotary rate ω=1/θRoPEω=1/ _RoPE, with θRoPE=104 _RoPE=10^4 and Δ=1024 =1024, gives: ωΔ=0.1024,rKATA=0.9896,rsoftmax=0.9590.ω =0.1024, r_KATA=0.9896, r_softmax=0.9590. The KATA score loses about 1.0%1.0\% across this offset, while the exponential softmax weight loses about 4.1%4.1\%. Squaring also removes the sign of the rotated inner product, further weakening phase discrimination. The full RoPE map averages across a spectrum of rates, and this single-plane calculation isolates the effect of the kernel nonlinearity. The delta correction directly updates the content address and can therefore improve recall even inside the training window. The multiplicative state weights of GatedKATA provide another source of learned positional decay and should strengthen this separation. The 340M-model sweep leaves GatedKATA pretraining and its interaction with RoPE for future work. 5.4 Needle-in-a-haystack recall Using the same pretrained models, we evaluate the three RULER single-needle tasks S-NIAH-1/2/3 (hsieh24ruler), which hide a word, a 77-digit number, and a 128128-bit UUID at a random depth in a distractor haystack and query it with a cloze prompt. The tasks form an increasing-entropy ladder: a UUID is a high-entropy exact string, the regime that most stresses a fixed-size recurrent state. We score the full 500500 samples per length with greedy decoding and normalized substring matching at 1K and 2K, both within the 20482048-token training horizon. We restrict the main capacity comparison to these in-window lengths because the RoPE-based softmax and KATA models collapse once evaluation moves beyond the training horizon. This protocol isolates retrieval capacity from positional length extrapolation; OOD lengths are reported in Appendix˜F. Method RULER needle-in-a-haystack Arora’24 (Based) cloze S-NIAH-1 (word) S-NIAH-2 (number) S-NIAH-3 (UUID) SWDE FDA SQuAD TriviaQA NQ 1K 2K 1K 2K 1K 2K Softmax attn. 1.000 0.992 1.000 1.000 0.956 0.930 0.450 0.170 0.160 0.290 0.227 Gated DeltaNet 0.996 0.954 0.384 0.748 0.004 0.004 0.225 0.060 0.293 0.254 0.156 KATA-M1 0.994 0.990 0.986 0.910 0.758 0.458 0.375 0.061 0.041 0.258 0.182 DeltaKATA-M1 0.998 0.950 1.000 0.990 0.908 0.584 0.370 0.148 0.353 0.268 0.179 KATA-M2 1.000 0.974 1.000 0.934 0.910 0.616 0.338 0.118 0.240 0.256 0.160 Ablations: ℓ2 _2-norm (KATA-M2) 1.000 0.836 0.982 0.792 0.658 0.224 0.308 0.086 0.259 0.228 0.142 short-conv, no RoPE (KATA-M2) 0.956 0.960 0.948 0.926 0.760 0.530 0.125 0.074 0.272 0.207 0.088 Table 4: In-context recall of pretrained 340M language models. RULER single-needle accuracy at 1K and 2K (left; 500 samples per length) and Arora’24 cloze accuracy (right), both under normalized substring matching. The best and second-best non-softmax primary methods in each column are shown in bold blue and underlined, respectively; diagnostic ablations are unranked. Table˜4 places softmax attention at the recall ceiling (≥0.93≥ 0.93 on every task), while Gated DeltaNet degrades sharply as needle entropy grows: word, number, and UUID recall fall 0.996→0.384→0.0040.996\!→\!0.384\!→\!0.004 at 1K. The PSD maps retain much more high-entropy signal. KATA-M1 remains strong on word and number recall, but its UUID accuracy falls from 0.7580.758 at 1K to 0.4580.458 at 2K; KATA-M2 reaches 0.9100.910 and 0.6160.616, respectively. At equal head width, the geometric packing argument favors KATA-M1’s full 64-dimensional factor for pure associative recall. Its recurrent state has 266,240266,240 entries, compared with 135,168135,168 for KATA-M2, so KATA-M2 obtains the stronger hard-needle result with approximately half the state. We interpret this reversal as a learnability effect: KATA-M1 learns one 64-dimensional spherical address factor, while KATA-M2 learns a product of two 32-dimensional factors. Realized recall therefore depends on both the available feature geometry and how readily the projections learn to use it. The delta erase provides a complementary gain. DeltaKATA-M1 raises UUID recall from 0.7580.758 to 0.9080.908 at 1K and from 0.4580.458 to 0.5840.584 at 2K without changing the KATA-M1 feature width, approaching KATA-M2’s 0.9100.910 and 0.6160.616. Two ablations on KATA-M2 isolate the remaining design choices: RMSNorm on , q, k improves 2K UUID recall from 0.2240.224 to 0.6160.616, and replacing RoPE with a GDN-style short convolution preserves much of the in-window recall. Length extrapolation exhibits a different ordering. Gated DeltaNet’s multiplicative recurrent gate generalizes more reliably beyond 20482048 tokens and leads the OOD-length evaluations. Its finite address capacity remains visible on the hard needles within the training horizon: UUID recall is 0.0040.004 at both 1K and 2K despite strong word recall. Strong OOD length generalization and hard-needle recall therefore expose complementary properties of the mixer. 5.5 In-context recall on the Based cloze suite Complementing the controlled NIAH probe (Table˜4), we also run the pretrained 340M models on the Based in-context recall suite (arora24based), comprising SWDE, FDA, SQuAD, TriviaQA, and NQ. Each task provides a document in context and a cloze query, scored by normalized substring matching on the full dataset. Table˜4 reports the results. SWDE is closest to a direct key–value association. KATA-M1 reaches 0.3750.375, the best fixed-state result, consistent with the pure-recall advantage of its larger feature space. FDA and SQuAD require contextual interpretation and selection among correlated candidates. In this regime, KATA-M1 falls to 0.0610.061 and 0.0410.041, while KATA-M2 reaches 0.1180.118 and 0.2400.240 and DeltaKATA-M1 reaches 0.1480.148 and 0.3530.353. The reversal supports the same learnability interpretation: the single 64-dimensional spherical address factor is harder to train for contextual routing than the product of two 32-dimensional factors. KATA-M1’s weaker pretraining perplexity relative to softmax attention, Gated DeltaNet, and DeltaKATA-M1 compounds this difficulty. KATA-M2 improves contextual selection despite its higher perplexity, indicating that factorization and general fluency contribute separately. Normalized substring matching also rewards verbose generations, so KATA-M1’s terse answers are under-credited relative to models that surface several candidate spans. We therefore treat NIAH as the primary capacity result and the Based suite as a joint probe of retrieval, contextual routing, and generation style. Method SWDE FDA SQuAD TriviaQA NQ† Softmax attn. 6.5 41.1 54.2 39.5 258 Gated DeltaNet 9.2 27.2 131.8 43.5 258 DeltaKATA-M1 4.5 40.9 202.2 46.3 258 KATA-M1 6.5 35.5 10.9 72.8 258 KATA-M2 7.0 35.5 182.8 30.4 258 Table 5: Average generation length. Tokens averaged over 20 examples per task. †256-token cap on NQ. SQuAD: cloze “…the NFL team that represented the AFC at Super Bowl 50 was the” [gold: Denver Broncos] Softmax New England Patriots. The 2016 NFL season was the 10th season in the NFL… Gated DeltaNet New England Patriots. The Patriots won the Super Bowl 50 with a record of 10–1… DeltaKATA-M1 Denver Broncos. The Broncos were led by quarterback Tom Brady, who was named… KATA-M1 New England Patriots. KATA-M2 San Francisco 49ers, who defeated the New England Patriots 24–10… SWDE (structured copy): cloze “…category: Feature year:” [gold: 1983] all five models 1983 Table 6: Example completions. One prompt each from SQuAD and SWDE. Verbosity and fluency. Because normalized substring matching credits any generation that includes the gold span, it rewards length. Table˜5 reports the average generated length per model: on SQuAD it ranges from ∼11 \!11 tokens (KATA-M1, which commits to a single terse answer) to ∼202 \!202 (DeltaKATA-M1), an 18.6×18.6× spread that mirrors the SQuAD accuracies. Table˜6 shows example completions on a shared prompt: every model is fluent, but the terse KATA-M1 model is penalized whenever its short answer is wrong, whereas more verbose models surface the gold span by volume. On the copy-style SWDE task the effect vanishes because all five emit the same short field value. This indicates that the SQuAD/FDA ordering reflects generation style as much as retrieval, a further reason we take NIAH (short, exact needles) as the primary recall measure. 5.6 Training compute Run GPU k tok/s/GPU GPU-hours Softmax attention H100 188 22.2 Gated DeltaNet H100 144 28.9 KATA-M1 (Flash) H100 190 21.9 KATA-M2 (Flash) H100 190 21.9 DeltaKATA-M1 H100 77 54.1 MQAR + overwrite A100 – ∼4 \!4 Table 7: Training compute. End-to-end throughput and accelerator time for each 15B-token 340M pretraining run; the final row aggregates all MQAR and overwrite experiments. Table˜7 converts the measured end-to-end throughput into accelerator time using 15×109/(r×3600)15× 10^9/(r× 3600) GPU-hours for throughput r in tokens/s/GPU. Under near-linear four-GPU scaling, the H100 totals correspond to approximately 5.55.5 hours for softmax attention, 7.27.2 hours for Gated DeltaNet, 5.55.5 hours for either Flash KATA model, and 13.513.5 hours for DeltaKATA-M1. The softmax run reaches approximately 760760k tokens/s across four H100 GPUs. Kernel-level attention gains are amortized across the full model, whose runtime also includes the MLPs, projections, RMSNorm, and optimizer work. Where applicable, we use FLA’s fused recurrent kernels (yang24fla), including the Gated DeltaNet and delta-rule recurrences, to reduce launch and intermediate-materialization overhead. The complete MQAR and overwrite benchmark suite is much smaller, requiring approximately 44 A100 GPU-hours in total. 6 Related Work We organize prior work along the four axes that Sections˜2, 3 and 4 unify: feature geometry, state recurrence, capacity diagnostics, and hardware mapping. For each, we indicate where existing linear-attention designs fall short. Feature geometry. katharopoulos20transformers replace softmax with ψ()=ELU()+1ψ( x)=ELU( x)+1 and exploit the recurrence t=t−1+ψ(t)t⊤ S_t= S_t-1+ψ( k_t) v_t to recurse in (nψdv)O(n_ψd_v). Performers (choromanski21performers), RFA (peng21rfa), cosFormer (qin22cosformer), and the fast-weight view of schlag21linear use random, trigonometric, or other finite features to approximate exp(⟨,⟩) ( q, k ). When nonnegative attention weights are required, such constructions use orthant-valued maps. The orthant is the simplicial member of the real self-dual cones admitted by the Koecher–Vinberg classification (koecher57positivitatsbereiche; vinberg63homogeneous; faraut94analysis). The Welch bound (Theorem˜3) then gives μ(ℝ+nψ,T)2≥(T−nψ)/(nψ(T−1))μ(R_+^n_ψ,T)^2≥(T-n_ψ)/(n_ψ(T-1)). At nψ=128n_ψ=128, requiring μ≤10−2μ≤ 10^-2 limits the dictionary to T≲130T 130 keys. These works do not analyze the orthant restriction as a capacity bottleneck. State recurrence. S4 (gu22efficiently), RWKV (peng23rwkv), RetNet (sun23retentive), and Mamba (gu24mamba) generalize the recurrence to a data-dependent transition t=tt−1+tt⊤ S_t= A_t S_t-1+ b_t c_t . The State-Space Duality of Mamba2 (dao24mamba2) restricts t=αt A_t= _t I, exposing the algebraic equivalence with causal linear attention but compressing per-token selectivity into a single scalar; the resulting decay is empirically too coarse on retention probes (S-NIAH degrades past 22K tokens (yang25gateddeltanet)). DeltaNet (yang24deltanet) treats t S_t as a fast-weight matrix updated by online ridge regression, and Gated DeltaNet (yang25gateddeltanet) adds an explicit forget gate: t=αt(−βttt⊤)t−1+βttt⊤,αt,βt∈ℝ. S_t= _t( I- _t k_t k_t ) S_t-1+ _t k_t v_t , _t, _t . (21) Proposition˜1 shows that normalized linear attention produces the parameter-free convex coefficient αt=Dt−1/Dt _t=D_t-1/D_t at readout while leaving the stored state unchanged. Recurrent gates act directly on memory and therefore provide a distinct control point. When the raw-key substrate in Equation˜21 is constrained to the nonnegative geometry studied here, its Lorentz lift meets the 1/21/2-interference Rankin wall of Theorem˜9 (rankin55closest), giving an (d)O(d) address regime. Content erase and learned decay can improve overwrite and retention without enlarging the raw feature space. These models tune the recurrence while leaving ψ implicit. Channel-wise refinements (qiu25gated) and test-time-regression variants (behrouz24titans; zuo25localla) operate on the same raw-key substrate; their recurrence mechanisms are complementary to the feature geometry studied here. Capacity diagnostics. Zoology (arora23zoology) and MQAR/needle-in-a-haystack benchmarks expose the recall–memory trade-off (jelassi24repeat; du25mom). Based (arora24based) approximates exp(⟨,⟩) ( q, k ) by a degree-22 Taylor map paired with sliding-window attention; LoLA (mcdermott25lola), the Associative Memory layer (krotov25mam), and the GatedDeltaNet-H1/H2 stacks (yang25gateddeltanet) concede the pure linear path and reintroduce a small KV cache. Modern Hopfield networks (krotov16dense; demircigil17model; ramsauer21hopfield; zhong25transformersdam) establish that exponential energy admits exponentially many stable patterns, and Section˜A.4 places KATA’s rank-one PSD map at degree 22 in this hierarchy with (d2)O(d^2) feature state. The map ψS()=vec(⊤)ψ^S( u)=vec( u u ) squares the inner product: ⟨ψS(i),ψS(j)⟩=⟨i,j⟩2 ψ^S( u_i),ψ^S( u_j) = u_i, u_j ^2. Below the Welch threshold ϵ⋆=1/pε =1/p, Theorem˜3 gives a finite rational ceiling. For any fixed ϵ∈(0,1)ε∈(0,1), once p>1/ϵp>1/ε, the greedy spherical-cap construction packs T≥12(1−ϵ)−(p−1)/2T≥ 12(1-ε)^-(p-1)/2 near-orthogonal keys in p(p+1)/2p(p+1)/2 feature coordinates, which grows exponentially in p (Theorem˜4). Hardware mapping. Chunkwise parallel training is the standard scaffold for linear-time recurrent attention, with the inter-chunk state propagated by a sequential prefix sum in, for example, the FLA kernels (yang24fla). For Gated DeltaNet, the non-commutative Householder transition in Equation˜21 requires a C×C\!×\!C triangular solve per chunk under the WY representation (schreiber89compactwy) and materializes per-token state intermediates in HBM. Mamba2’s data-dependent transition instead requires a multiplicative selective scan rather than a vector-space cumulative sum. An additive feature-state recurrence admits a parallel scan that lowers the inter-chunk depth from Θ(NC) (N_C) to (logNC)O( N_C) (Section˜4.2). KATA combines Koecher–Vinberg geometry with Welch–Rankin packing to certify exponential capacity at a fixed tolerable interference using a finite, hardware-aligned feature map. 7 Discussion and Limitations The results separate three aspects of associative attention that are often grouped under capacity: the geometry available for storing bindings, the ability of training to realize that geometry, and the contextual fluency needed to construct the correct association from language. KATA provides a theory and hardware realization for the first, exposes architectural controls for the second, and tests the third through 340M-parameter pretraining. Geometric capacity. For normalized query and key directions, associative capacity is a packing problem. Within the ordinary real symmetric-cone family, Sections˜2 and 3 identifies the available nonnegative geometries and bounds their attainable interference. The rank-one PSD map squares directional overlap and expands a p-dimensional address into p(p+1)/2p(p+1)/2 features. KATA-M1 realizes the full map, while KATA-Mgg and KATA-Σg g reduce the recurrent state through block factorization. MQAR and NIAH validate the resulting capacity advantage over raw-key recurrences, and the same pSNR framework explains temperature sharpening in softmax. These bounds describe an achievable ceiling under the real, unit-direction, degree-two model. Learnability. Training determines how much of that ceiling is realized, so empirical associative-recall performance reflects the quality of the packing learned by the model. KATA-M1 has the larger geometric packing budget and a 266,240266,240-entry state, yet KATA-M2 obtains stronger hard-needle recall with 135,168135,168 entries. In this regime, the model learns two 32-dimensional factors more effectively than one 64-dimensional factor. Normalization and recurrence design provide additional controls: RMSNorm improves the learned KATA-M2 geometry, the delta rule replaces stale content at repeated addresses, and multiplicative gating supplies learned positional weighting distinct from RoPE. Gated DeltaNet’s length extrapolation shows that such gating can generalize beyond the RoPE training horizon. Contextual fluency. Direct recall begins after the model has formed the relevant query, key, and value. FDA and SQuAD also require context interpretation and selection among correlated candidates. KATA-M1 is strong on NIAH and direct-copy SWDE but degrades on these contextual tasks; KATA-M2 and DeltaKATA-M1 recover part of the gap. Pretraining perplexity contributes separately, since KATA-M2 improves contextual selection despite higher perplexity. The combined synthetic, exact-string, and cloze evaluations therefore distinguish storage capacity from the broader language-modeling behavior of the mixer. Future work. Four directions follow directly. First, packing theory and constructive dictionaries should be extended to complex spaces, where spherical codes and ETFs may offer more capacity at equal dimension. Second, GatedKATA and GatedDeltaKATA should be pretrained systematically, while DeltaKATA should be evaluated beyond M1; all three require dedicated fused GPU kernels. Third, the learnability of the full KATA-M1 geometry should be tested beyond dhead=64d_head=64, together with kernels that make its quadratic feature state practical at wider heads. Finally, tensor-train factorizations (oseledets11t) offer a path to higher even-order outer-product features without materializing the full tensor state. These studies will determine whether the geometric gains persist as feature order, model scale, and contextual demands increase. Acknowledgments We thank the Research Computing staff at the University of Colorado Boulder for providing access to GH200 nodes and for their prompt support in diagnosing and resolving system issues. We also thank Modal for free-tier compute credits that accelerated kernel tuning and development. We are grateful to the GPU MODE community, whose tutorials, competitions, forums, and open technical discussions created a welcoming environment for learning and mastering GPU programming. The answers shared by community members on those forums were crucial to developing the kernels in this work. References Appendix A Reader’s guide to the geometry This appendix provides a short map from the attention equations to the geometric claims in the main text. We reserve d for the raw query/key dimension, dvd_v for the value dimension, and nψn_ψ for a generic feature dimension. For PSD features, p is the matrix side length and n≔p(p+1)/2n p(p+1)/2 is the symmetric ambient dimension, so the full PSD map has nψ=n_ψ=n. The sequence length is T, the chunk size is C, and NC≔⌈T/C⌉N_C T/C is the number of chunks. Packing statements define their dictionary size locally. Why recall becomes a packing problem. Suppose a query q is meant to retrieve the binding at key j k_j from the additive state =∑iψ(i)i⊤ S= _iψ( k_i) v_i . The numerator of the readout is: ψ()⊤=⟨ψ(),ψ(j)⟩j⊤+∑i≠j⟨ψ(),ψ(i)⟩i⊤.ψ( q) S= ψ( q),ψ( k_j) v_j + _i≠ j ψ( q),ψ( k_i) v_i . After normalizing features so the matched coefficient is one, every wrong value is weighted by a feature inner product. A fixed recurrent state therefore stores many bindings well only when the stored feature vectors are nearly orthogonal. This is the interference μ(,T)μ(K,T) in Equation˜5: it asks how many unit feature vectors fit in the allowed cone with all pairwise interference below a target tolerance. Why cones enter. Normalized linear attention needs nonnegative weights in the denominator and numerator. A self-dual cone =∗K=K^* gives a coordinate-free certificate: if ψ(),ψ()∈ψ( x),ψ( y)∈K, then ⟨ψ(),ψ()⟩≥0 ψ( x),ψ( y) ≥ 0. This is weaker than strict coordinatewise positivity. Boundary points are allowed; small ϵε terms are numerical safeguards against a zero denominator, not part of the capacity theorem. Where the denominator gate appears. For a fixed query, write Dt=ψ(t)⊤t=Dt−1+⟨ψ(t),ψ(t)⟩D_t=ψ( q_t) Z_t=D_t-1+ ψ( q_t),ψ( k_t) . If Dt>0D_t>0, the normalized readout is a convex interpolation between the previous normalized readout and the new value, with weights Dt−1/DtD_t-1/D_t and ⟨ψ(t),ψ(t)⟩/Dt ψ( q_t),ψ( k_t) /D_t. This is the parameter-free gate proved formally in Proposition˜1; it comes from normalization, not from an additional state transition. What the three cone factors do. The orthant has d coordinate rays that are exactly orthogonal, but beyond those rays it inherits the ordinary Welch interference floor. The positive orthant has small solid angle, but a worst-case packing can live on sparse boundary faces, so volume alone is not a universal capacity obstruction. The Lorentz lift of a linear key uses ψLor()=2−1/2(,1) _Lor( k)=2^-1/2( k,1) and turns z=⟨,⟩z= q, k into (1+z)/2(1+z)/2; this adds the 1/21/2 offset, so pushing below that offset forces the raw keys to be mutually obtuse and invokes Rankin. The PSD rank-one map ψPSD()=⊤ _PSD( u)= u u turns z into z2z^2, so antipodal and orthogonal-ish raw keys identifies antipodal raw vectors as the same line, while near-orthogonal raw lines become useful packing directions. How softmax fits. The exponential kernel is an infinite direct sum of tensor degrees. Theorem˜8 shows the cone interpretation of those degrees: even monomials are rank-one PSD rays on tensorized features, while signed odd monomials become nonnegative only when paired with enough even mass into Lorentz-gated PSD atoms. KATA keeps the first capacity-changing PSD degree and implements it with a fixed recurrent state. A.1 Kernel methods The exponential dot-product kernel admits the tensor expansion: exp(⟨,⟩)=∑r=0∞⟨,⟩r!=∑r=0∞⟨⊗r!,⊗r!⟩. ( x, y )= _r=0^∞ x, y ^rr!= _r=0^∞ x r r!, y r r! . (22) Thus the canonical RKHS feature map is the infinite direct sum ϕ()=⨁r≥0⊗r/r!φ( x)= _r≥ 0 x r/ r!. Linear attention replaces this infinite feature map by a finite ψ:ℝd→ℝnψ:R^d ^n_ψ. Lemma 5 (Norm of the exponential feature map on the sphere). For τ>0τ>0, let Kτ(,)=exp(⟨,⟩/τ)K_τ( q, k)= ( q, k /τ) have canonical feature map: ϕτ()=⨁r≥0⊗r!τr. _τ( x)= _r≥ 0 x r r!τ^r. Then: ∥ϕτ()∥ℋ2=Kτ(,)=exp(∥2/τ). _τ( x) _H^2=K_τ( x, x)= ( x ^2/τ). In particular, on d−1S^d-1 the squared feature norm is the constant e1/τe^1/τ and the feature norm is e1/(2τ)e^1/(2τ). Proof. The claim follows by evaluating the reproducing kernel on the diagonal: ∥ϕτ()∥ℋ2=⟨ϕτ(),ϕτ()⟩ℋ=Kτ(,) _τ( x) _H^2= _τ( x), _τ( x) _H=K_τ( x, x). ∎ Hence unit-normalizing , q, k in input space maps the sphere into a sphere of radius e1/(2τ)e^1/(2τ) in the exact RKHS, matching the cone-restricted fixed-norm setting used throughout the main text up to a positive scalar. RMSNorm effect RMSNorm normalizes the input direction and then applies a learned per-channel scale. Its output is therefore not unit norm; nevertheless, its query–key inner product can be represented as a scalar multiple of an inner product between unit vectors in one higher dimension. Ignoring the stabilizing ϵε, let cd>0c_d>0 absorb the fixed conversion from RMS normalization to ℓ2 _2 normalization, together with any fixed attention-logit scaling, and define: ^=^∥^∥,^=^∥^∥. q= q q , k= k k . Define the diagonal gain matrix: γ≔cddiag(q⊙k). D_γ c_d\,diag( γ_q γ_k). Then: ℓ(^,^) ( q, k) =^⊤γ = q D_γ k (23) =⟨^,¯⟩,¯≔γ^. = q, k , k D_γ k. (24) Choose any M>0M>0 satisfying M≥∥¯∥2M≥ k ^2 for every key under consideration. For a finite dictionary one may take M=maxj∥¯j∥2M= _j k_j ^2; a context-independent choice for γ≠0 D_γ≠ 0 is: M=∥γ∥op2.M= D_γ _op^2. Define: ~=(^,0),~=1M(¯,M−∥¯∥2). q=( q,0), k= 1 M ( k, M- k ^2 ). Both ~ q and ~ k are unit vectors in ℝd+1R^d+1, and: ℓ(^,^)=M⟨~,~⟩. ( q, k)= M\, q, k . (25) Thus the RMSNorm-scaled logit is exactly a scalar inverse-temperature factor M M multiplying a cosine similarity in the lifted space. The diagonal gain matrix is absorbed into the lifted key geometry. A.2 Symmetric cones and Jordan algebras A subset ⊂ℝnK ^n is a cone if s∈s v∈K for all s>0s>0, ∈ v∈K. It is convex if +∈ u+ v∈K whenever ,∈ u, v∈K. A closed convex cone is pointed if ∩(−)=0K∩(-K)=\0\ and full-dimensional if its interior is non-empty. The dual cone of ⊂ℝnK ^n under the Euclidean inner product is ∗=∈ℝn:⟨,⟩≥0∀∈K^*=\ y ^n: x, y ≥ 0\;∀ x∈K\. The cone is self-dual if =∗K=K^*. Its automorphism group is Aut()=∈GL(n,ℝ):()=Aut(K)=\ A (n,R): A(K)=K\, and K is homogeneous if Aut()Aut(K) acts transitively on the interior int()int(K). The Koecher–Vinberg theorem [koecher57positivitatsbereiche, vinberg63homogeneous, faraut94analysis] identifies real symmetric cones with cones of squares in formally real (Euclidean) Jordan algebras, and classifies the irreducible cases as: ℝ+R_+ (one-dimensional Jordan algebra), ℒ+mL^m_+ for m≥3m≥ 3 (spin factor), +nS^n_+ for n≥2n≥ 2 (real symmetric matrices), ℋ+n(ℂ)H^n_+(C) (complex Hermitian, n≥2n≥ 2), ℋ+n(ℍ)H^n_+(H) (quaternionic Hermitian, n≥2n≥ 2), and ℋ+3()H^3_+(O) (Albert algebra, exceptional). Our analysis restricts to the first three (real-coordinate Jordan algebras); the others remain valid symmetric cones but require complex-, quaternionic-, or octonionic-valued feature maps. A.3 Fundamental geometric bounds We collect the four bounds that govern packing on the cone-restricted sphere. Throughout, T is the number of unit vectors and D is the ambient dimension. Welch bound. For any T unit vectors 1,…,T∈D−1⊂ℝD u_1,…, u_T ^D-1 ^D: maxi≠j⟨i,j⟩2≥T−D(T−1). _i≠ j u_i, u_j ^2\;≥\; T-DD(T-1). Inverting for T at squared interference ϵε gives T≤D(1−ϵ)/(1−Dϵ)T≤ D(1-ε)/(1-Dε) for ϵ<1/Dε<1/D. As T→∞T→∞, the floor approaches 1/D1/D. The Welch bound is achieved with equality by Equiangular Tight Frames (ETFs). Gerzon bound. An ETF on T vectors in ℝDR^D requires T≤D(D+1)/2T≤ D(D+1)/2; above this ceiling, equality in the Welch bound is impossible. Below the ceiling, existence remains parameter-dependent, and real ETFs occur only for special pairs (D,T)(D,T). Over ℂDC^D, the corresponding ceiling is D2D^2, although complex ETF existence is also incomplete [fickus16etf]. Rankin bound. If T unit vectors in ℝDR^D have strictly negative pairwise inner products, then T≤D+1T≤ D+1. At the boundary where the inner products are merely nonpositive, the cross-polytope gives the sharp bound T≤2DT≤ 2D. The Lorentz condition in Theorem˜9 is strict: for interference below 1/21/2, its spatial components lie in ℝd−1R^d-1 and are mutually obtuse, so T≤dT≤ d. Alon’s combinatorial bound. Alon’s rank bound [alon09rank] states that for any T unit vectors with maxi≠j|⟨i,j⟩|≤μ _i≠ j| u_i, u_j |≤μ: D=Ω(minT,logTμ2log(1/μ))D= \! ( \! \T, Tμ^2 (1/μ) \ ) This universal lower bound leaves only a log(1/μ) (1/μ) factor between the best known necessary dimension and the sufficient D=(μ−2logT)D=O(μ^-2 T) scaling of random spherical codes. Finite-size comparison. Alon’s bound hides an unspecified universal constant, so we do not assign it a numerical value. For T=105T=10^5 and μ=0.05μ=0.05, the Welch bound requires D≥399D≥ 399, while the simple all-pairs random-code estimate D≈4logT/μ2D≈ 4 T/μ^2 gives D≈18,421D≈ 18,421. The deterministic MUB-derived and DeVore dictionaries below require D=802D=802 and D=2,209D=2,209, respectively. A.4 Dense associative memory hierarchy The cone feature degrees parallel the Krotov–Hopfield Dense Associative Memory (DAM) hierarchy. DAM capacity is defined through an energy, update rule, and stability criterion, whereas our ϵε-capacity counts address directions at fixed interference. The comparison below concerns the tensor-power degree of F(z)=⟨ψ(),ψ()⟩F(z)= ψ( q),ψ( k) for z=⟨,⟩z= q, k and does not identify the two capacity notions. • Unnormalized linear attention: FLin(z)=zF_Lin(z)=z, degree-1 (classical Hopfield), using the raw signed key kernel. Cone nonnegativity is absent. • Lorentz lift of the linear kernel: FLor(z)=12+12zF_Lor(z)= 12+ 12z. This is the smallest nonnegative cone lift of the degree-1 substrate. Below interference 1/21/2, its geometric address capacity is (p)O(p) by the Rankin wall of Theorem˜9. • Square-diagonal PSD with rank-one rays: FPSD(z)∝z2F_PSD(z) z^2, degree-2 (Krotov–Hopfield dense memory). For fixed interference and p>1/ϵp>1/ε, the spherical-cap construction of Theorem˜4 gives exponentially many address directions. Under the isotropic-value pSNR criterion, aggregate retrieval instead has the Θ(p2) (p^2) threshold of Section˜3.3. • Softmax: Fsoft(z)=ez=∑r≥0zr/r!F_soft(z)=e^z= _r≥ 0z^r/r!, infinite degree. Theorem˜8 shows that its even Taylor degrees are rank-one PSD rays on tensor powers, while its signed odd degrees become positive only after pairing with even mass into Lorentz-gated PSD atoms. The kernel requires the infinite RKHS feature ϕ()=⨁r⊗r/r!φ( x)= _r x r/ r!. KATA’s degree-2 map uses (p2)O(p^2) feature coordinates without adding (p2dv)O(p^2d_v) model parameters. The quadratic kernel rematerializes the p→p2p→ p^2 feature expansion on chip, while the linear-state kernel stores the expanded recurrent state in HBM. Tensor-train factorizations [oseledets11t] are a possible route to higher feature orders without materializing the full tensor; enforcing nonnegativity under such truncations remains open. Appendix B Cone classification and normalization proofs B.1 Proof of Proposition˜1 (output-level gating) Let Dt−1=ψ(t)⊤t−1D_t-1=ψ( q_t) Z_t-1 and ct=ψ(t)⊤ψ(t)c_t=ψ( q_t) ψ( k_t). If Dt−1=0D_t-1=0, then the nonnegative summands in Dt−1D_t-1 are all zero, so ψ(t)⊤t−1=0ψ( q_t) S_t-1=0 as well. Since Dt=Dt−1+ct>0D_t=D_t-1+c_t>0, we have ct>0c_t>0 and the normalized readout is exactly t⊤ v_t . Now suppose Dt−1>0D_t-1>0. Splitting numerator and denominator of t z_t: t=ψ(t)⊤t−1+ψ(t)⊤ψ(t)t⊤ψ(t)⊤t−1+ψ(t)⊤ψ(t). z_t= ψ( q_t) S_t-1+ψ( q_t) ψ( k_t) v_t ψ( q_t) Z_t-1+ψ( q_t) ψ( k_t). Multiplying and dividing the first numerator term by ψ(t)⊤t−1ψ( q_t) Z_t-1 yields: t=ψ(t)⊤t−1ψ(t)⊤t¯t|t−1+ψ(t)⊤ψ(t)ψ(t)⊤tt⊤. z_t= ψ( q_t) Z_t-1ψ( q_t) Z_t\, z_t|t-1+ ψ( q_t) ψ( k_t)ψ( q_t) Z_t\, v_t . The two numerators sum to ψ(t)⊤tψ( q_t) Z_t, so αt(t)+βt(t)=1 _t( q_t)+ _t( q_t)=1. Nonnegativity follows from Assumption˜1, because Dt−1D_t-1 and ctc_t are sums of nonnegative feature inner products. B.2 Canonical-cone classification Let K be the closed, pointed, full-dimensional self-dual homogeneous cone that contains imψimψ. Self-duality gives =∗K=K^*, so for any two features ψ(),ψ()∈ψ( x),ψ( y)∈K: ⟨ψ(),ψ()⟩≥0, ψ( x),ψ( y) ≥ 0, which certifies Assumption˜1. By the Koecher–Vinberg theorem, K is the cone of squares of a Euclidean Jordan algebra and decomposes uniquely as a Cartesian product of irreducible symmetric cones. Restricting to the ordinary real families considered here leaves ℝ+R_+, Lorentz cones, and real PSD cones. Products of one-dimensional ℝ+R_+ factors are orthants. Thus every cone in our scope is represented as a product of orthant, Lorentz, and PSD components. Assumption˜2 constrains how rotations of the input act within this product, but does not introduce additional real irreducible cone factors. Appendix C Packing and SNR proofs C.1 Proof of Theorem˜3 (orthant Welch limit) The d standard basis vectors lie in ℝ+dR^d_+ and are pairwise orthogonal, so zero interference is possible for N=dN=d. For N>dN>d, apply the Welch bound to any N unit vectors 1,…,N∈ℝ+d ψ_1,…, ψ_N ^d_+: maxi≠j⟨i,j⟩2≥N−d(N−1). _i≠ j ψ_i, ψ_j ^2≥ N-dd(N-1). Because orthant inner products are nonnegative, this is also a lower bound on the squared interference μ2μ^2. If μ≤ϵμ≤ε and ϵ<1/dε<1/ d, rearranging ϵ2≥(N−d)/(d(N−1))ε^2≥(N-d)/(d(N-1)) gives N≤d(1−ϵ2)/(1−dϵ2)N≤ d(1-ε^2)/(1-dε^2). C.2 Proof of Theorem˜9 (Lorentz interference wall) Proof. A unit extreme ray of the closure of ℒ+dL^d_+ has the form ψ=2−1/2(,1)ψ=2^-1/2( y,1) with ∈d−2 y ^d-2. Hence: ⟨ψi,ψj⟩=12⟨i,j⟩+12. _i, _j = 12 y_i, y_j + 12. If ⟨ψi,ψj⟩≤ϵ<1/2 _i, _j ≤ε<1/2, then ⟨i,j⟩≤−α y_i, y_j ≤-α with α=1−2ϵ>0α=1-2ε>0. Therefore: 0≤∥∑i=1Ni∥22=N+2∑i<j⟨i,j⟩≤N−αN(N−1),0≤ _i=1^N y_i _2^2=N+2 _i<j y_i, y_j ≤ N-α N(N-1), which gives N≤1+1/αN≤ 1+1/α. Since the pairwise inner products are strictly negative, Rankin’s strict spherical-code bound also gives N≤dN≤ d for vectors in ℝd−1R^d-1 [rankin55closest]. Combining the two bounds proves the claim. ∎ Lemma 6 (One-sided spherical-cap bound). Let p≥2p≥ 2, let ∼Unif(p−1) u (S^p-1), and fix ∈p−1 e ^p-1. For every a∈[0,1]a∈[0,1]: Pr[⟨,⟩≥a]≤(1−a2)(p−1)/2. \! [ u, e ≥ a ]≤(1-a^2)^(p-1)/2. (26) Proof. By rotation invariance, take e to be the north pole and write θ=arccos(a)∈[0,π/2]θ= (a)∈[0,π/2]. With σ denoting normalized surface measure, the cap Ca()=:⟨,⟩≥aC_a( e)=\ u: u, e ≥ a\ has measure: σ(Ca())=∫0θsinp−2ϕdϕ∫0πsinp−2ϕdϕ=12I1−a2(p−12,12),σ(C_a( e))= _0^θ ^p-2φ\,dφ _0^π ^p-2φ\,dφ= 12I_1-a^2\! ( p-12, 12 ), where Ix(α,β)I_x(α,β) is the regularized incomplete beta function. It remains to upper-bound the first ratio. Set n=p−2n=p-2 and s=sinθ=1−a2s= θ= 1-a^2. If s=0s=0, the claim is trivial. Otherwise substitute sinϕ=ssinψ φ=s ψ in the numerator. Then: ∫0θsinnϕdϕ=sn+1∫0π/2sinnψcosψ1−s2sin2ψψ. _0^θ ^nφ\,dφ=s^n+1 _0^π/2 ^nψ ψ 1-s^2 ^2ψ\,dψ. Since 0≤s≤10≤ s≤ 1, we have 1−s2sin2ψ≥1−sin2ψ=cosψ 1-s^2 ^2ψ≥ 1- ^2ψ= ψ for ψ∈[0,π/2]ψ∈[0,π/2]. Hence: ∫0θsinnϕdϕ≤sn+1∫0π/2sinnψdψ≤sn+1∫0πsinnψdψ. _0^θ ^nφ\,dφ≤ s^n+1 _0^π/2 ^nψ\,dψ≤ s^n+1 _0^π ^nψ\,dψ. Dividing by the denominator gives σ(Ca())≤sn+1=(1−a2)(p−1)/2σ(C_a( e))≤ s^n+1=(1-a^2)^(p-1)/2. ∎ C.3 Proof of Theorem˜4 (PSD exponential packing) For p≥2p≥ 2, the extreme rays of the PSD cone +pS^p_+ are rank-one matrices ⊤ u u with ∈p−1 u ^p-1. Their Frobenius inner product is: ⟨ii⊤,jj⊤⟩F=Tr(ii⊤jj⊤)=⟨i,j⟩2. u_i u_i , u_j u_j _F=Tr( u_i u_i u_j u_j )= u_i, u_j ^2. Thus PSD interference at most ϵε is equivalent to |⟨i,j⟩|≤ϵ| u_i, u_j |≤ ε. Let a=ϵa= ε and let σ denote normalized surface measure on p−1S^p-1. Now choose lines greedily on p−1S^p-1: after selecting 1,…,m u_1,…, u_m, add any u outside the antipodal caps Ca(i)∪Ca(−i)C_a( u_i)∪ C_a(- u_i). When the process is maximal, these antipodal caps cover the sphere; otherwise an uncovered point could be added. By Lemma˜6, each selected line covers at most 2(1−ϵ)(p−1)/22(1-ε)^(p-1)/2 surface measure, so maximality implies: 1≤2m(1−ϵ)(p−1)/2⇒m≥12(1−ϵ)−(p−1)/2.1≤ 2m(1-ε)^(p-1)/2 m≥ 12(1-ε)^-(p-1)/2. Because each new line is chosen outside all previous antipodal caps, the selected lines satisfy |⟨i,j⟩|<a| u_i, u_j |<a, hence they meet the stated ϵε interference bound after the rank-one PSD map. Adding ηη I to each rank-one matrix and renormalizing moves the construction into the cone interior if a numerical margin is desired, and the pairwise Frobenius inner products converge to the rank-one values as η↓0η 0. C.4 Rank-one PSD atoms minimize Haar-average interference The ray through ⊤ u u is extreme. Indeed, if ⊤=+ u u = A+ B with ,⪰0 A, B 0, then for every ⟂ w u, 0=⊤+⊤0= w A w+ w B w. Positive semidefiniteness gives ==0 A w= B w=0, so the ranges of A and B are contained in spanspan\ u\. Hence A and B are nonnegative multiples of ⊤ u u . Proposition 7 (Rank-one PSD atoms minimize Haar-average interference). Let ,⪰0 A, B 0 have ∥F=∥F=1 A _F= B _F=1 with eigendecompositions =∑rarrr⊤ A= _ra_r u_r u_r and =∑sbsss⊤ B= _sb_s v_s v_s , ar,bs≥0a_r,b_s≥ 0. Then ⟨,⟩F=∑r,sarbs⟨r,s⟩2≥0 A, B _F= _r,sa_rb_s u_r, v_s ^2≥ 0, and under a Haar-random relative eigenbasis ⟨,⟩F=Tr()Tr()/p≥1/pE A, B _F=Tr( A)Tr( B)/p≥ 1/p, with equality only for rank-one matrices. Let =∑rarrr⊤ A= _ra_r u_r u_r and =∑sbsss⊤ B= _sb_s v_s v_s be spectral decompositions with ar,bs≥0a_r,b_s≥ 0. Then: ⟨,⟩F=Tr(∑r,sarbsrr⊤ss⊤)=∑r,sarbs⟨r,s⟩2. A, B _F=Tr ( _r,sa_rb_s u_r u_r v_s v_s )= _r,sa_rb_s u_r, v_s ^2. All coefficients are nonnegative, so high-rank PSD features average many rank-one interactions without cancellation. If the relative eigenbasis is Haar-random, then ⟨r,s⟩2=1/pE u_r, v_s ^2=1/p for every pair (r,s)(r,s), hence: ⟨,⟩F=1p(∑rar)(∑sbs)=Tr()Tr()p.E A, B _F= 1p ( _ra_r ) ( _sb_s )= Tr( A)Tr( B)p. Since ∥F2=∑rar2=1 A _F^2= _ra_r^2=1, Cauchy–Schwarz gives Tr()=∑rar≥1Tr( A)= _ra_r≥ 1, with equality iff exactly one eigenvalue is nonzero. The same holds for B, so the expected interference is at least 1/p1/p, with equality only when both matrices are rank one. The Cholesky identity used in the main text follows from cyclicity of trace: if =⊤ A= L L and =⊤ B= M M , then: ⟨,⟩F=Tr(⊤⊤)=Tr(⊤⊤)=∥⊤∥F2. A, B _F=Tr( L L M M )=Tr( L M M L)= L M _F^2. Thus dense factors introduce all cross-column products. A single flat-vector inner product omits these interactions. C.5 MUB-derived real dictionary * Proof. We first write the construction explicitly when s=ps=p is an odd prime. Let ω=exp(2πi/p)ω= (2π i/p) and let 0,…,p−1 e_0,…, e_p-1 be the standard basis of ℂpC^p. The first basis is 0,…,p−1\ e_0,…, e_p-1\. For each k∈pk _p and m∈pm _p, define: k,m=1p∑j=0p−1ωkj2+mjj, u_k,m= 1 p _j=0^p-1ω^kj^2+mj e_j, with all exponents evaluated modulo p. This gives p additional bases, one for each k∈pk _p. Within a fixed k, the inner product of two vectors is: ⟨k,m,k,m′⟩ℂ=1p∑j=0p−1ω(m′−m)j, u_k,m, u_k,m _C= 1p _j=0^p-1ω^(m -m)j, which is 11 if m=m′m=m and 0 otherwise. Thus each fixed-k collection is an orthonormal basis. A standard basis vector has inner-product modulus 1/p1/ p with every k,m u_k,m, since every coordinate of k,m u_k,m has modulus 1/p1/ p. Finally, for k≠k′k≠ k : ⟨k,m,k′,m′⟩ℂ=1p∑j=0p−1ω(k′−k)j2+(m′−m)j. u_k,m, u_k ,m _C= 1p _j=0^p-1ω^(k -k)j^2+(m -m)j. The quadratic coefficient is nonzero, so the Gauss-sum identity gives this sum modulus p p; hence the inner-product modulus is 1/p1/ p. The same finite-field construction, with the appropriate trace character, gives complete sets of s+1s+1 mutually unbiased bases in ℂsC^s for every prime power s=ℓks= ^k [wootters89optimal, bandyopadhyay02new]. Write these bases as ℬa=a,1,…,a,sB_a=\ u_a,1,…, u_a,s\ for a=1,…,s+1a=1,…,s+1. They satisfy: |⟨a,i,b,j⟩ℂ|=0,a=b,i≠j,1/s,a≠b, | u_a,i, u_b,j _C |= cases0,&a=b,\ i≠ j,\\ 1/ s,&a≠ b, cases with all vectors unit norm. Thus the complex construction already contains m=s(s+1)m=s(s+1) unit vectors with maximum complex interference 1/s1/ s. To obtain real vectors, apply the realification map R:ℂs→ℝ2sR:C^s ^2s, R(+i)=(,)R( a+i b)=( a, b). This map preserves norms: ∥R()∥22=∥ℜ∥22+∥ℑ∥22=∥22 R( u) _2^2= u _2^2+ u _2^2= u _2^2. Moreover, for any ,∈ℂs u, v ^s: ⟨R(),R()⟩ℝ=ℜ⟨,⟩ℂ. R( u),R( v) _R= u, v _C. Hence |⟨R(),R()⟩ℝ|≤|⟨,⟩ℂ| | R( u),R( v) _R |≤ | u, v _C |. Realifying the s(s+1)s(s+1) MUB vectors therefore gives m=s(s+1)m=s(s+1) unit vectors in ℝ2sR^2s with maximum absolute interference at most 1/s1/ s. Since d=2sd=2s, this is 1/s=2/d1/ s= 2/d. ∎ C.6 DeVore construction * Proof. For a prime p, take p=ℤ/pℤF_p=Z/pZ and index the rows by pairs (x,y)∈p2(x,y) _p^2. The same construction works over the finite field sF_s for any prime power s, so we write it in that notation. Following DeVore’s finite-field construction [devore07deterministic], index the coordinates of ℝs2R^s^2 by (x,y)∈s2(x,y) _s^2 and choose one polynomial for every coefficient vector =(a0,…,ar)∈sr+1 a=(a_0,…,a_r) _s^r+1: P(x)=a0+a1x+⋯+arxr.P_ a(x)=a_0+a_1x+·s+a_rx^r. There are sr+1s^r+1 such coefficient vectors. The condition r<sr<s ensures that distinct coefficient vectors define distinct functions on sF_s: if P=P_ a=P_ b at all s field elements, then P−P_ a-P_ b is a nonzero polynomial of degree at most r with more than r roots, impossible over a field. For each polynomial P, define P∈ℝs2 v_P ^s^2 by: (P)(x,y)=1/s,y=P(x),0,y≠P(x).( v_P)_(x,y)= cases1/ s,&y=P(x),\\ 0,&y≠ P(x). cases The graph (x,P(x)):x∈s\(x,P(x)):x _s\ has exactly s coordinates, so ∥P∥22=s⋅(1/s)=1 v_P _2^2=s·(1/s)=1. For two distinct polynomials P,QP,Q, the supports of P v_P and Q v_Q overlap exactly at the field elements where P(x)=Q(x)P(x)=Q(x). Therefore: ⟨P,Q⟩=1s|x∈s:P(x)=Q(x)|. v_P, v_Q = 1s |\x _s:P(x)=Q(x)\ |. The polynomial P−QP-Q is nonzero and has degree at most r. By the standard root bound for univariate polynomials over a field, it has at most r roots in sF_s. Hence ⟨P,Q⟩≤r/s v_P, v_Q ≤ r/s. This gives m=sr+1m=s^r+1 unit vectors in ℝs2R^s^2 with maximum interference at most r/sr/s. ∎ C.7 Proof of Section˜3.3 (idealized Welch-scale retrieval) Proof. Normalize the matched score to one. For linear features, each distractor has score magnitude ϵ⋆ ε and therefore contributes power ϵ⋆ε . For rank-one PSD features, the score is the squared raw correlation, so each distractor contributes power (ϵ⋆)2(ε )^2. Summing over T−1T-1 distractors gives: pSNRLin=1(T−1)ϵ⋆,pSNRPSD=1(T−1)(ϵ⋆)2.pSNR_Lin= 1(T-1)ε , _PSD= 1(T-1)(ε )^2. Substituting ϵ⋆=(T−p)/(p(T−1))ε =(T-p)/(p(T-1)) yields the two exact expressions in the theorem. Finally, pSNRLin>1pSNR_Lin>1 is equivalent to T<2pT<2p. For PSD features, setting pSNRPSD=1pSNR_PSD=1 gives: T2−(p2+2p)T+2p2=0,T^2-(p^2+2p)T+2p^2=0, whose larger root is p2+2p−2+(p−1)p^2+2p-2+O(p^-1), giving the stated Θ(p2) (p^2) threshold. ∎ C.8 Proof of Section˜3.3 (softmax sharpening) Proof. Write zj=⟨,j⟩z_j= q, k_j . Because q and j k_j have unit norm: zj+1=2⟨ψLor(),ψLor(j)⟩≥0,ψLor()=2−1/2(,1).z_j+1=2 _Lor( q), _Lor( k_j) ≥ 0, _Lor( x)=2^-1/2( x,1). Adding a common bias does not change softmax: e(zj+b)/τ∑ℓe(zℓ+b)/τ=ezj/τ∑ℓezℓ/τ. e^(z_j+b)/τ _ e^(z_ +b)/τ= e^z_j/τ _ e^z_ /τ. At the matched key z⋆=1z_ =1, while the harmful Welch-scale distractors have zj=μ⋆=ϵ⋆z_j=μ = ε . After canceling the common bias factor, their unnormalized scores are: s⋆=e1/τ,sd=eμ⋆/τ.s_ =e^1/τ, s_d=e^μ /τ. The partition is common to every coefficient and cancels from pSNR. Under the independent isotropic-value model of Equation˜10: pSNRSoft=s⋆2(T−1)sd2=e2(1−μ⋆)/τT−1.pSNR_Soft= s_ ^2(T-1)s_d^2= e^2(1-μ )/τT-1. Therefore pSNRSoft>1pSNR_Soft>1 is exactly T−1<exp(2(1−μ⋆)τ).T-1< \! ( 2(1-μ )τ ). (27) When T≫pT p, μ⋆=(T−p)/(p(T−1))→1/pμ = (T-p)/(p(T-1))→ 1/ p, which gives Equation˜15. Solving the same inequality for 1/τ1/τ gives Equation˜16. ∎ C.9 Softmax Taylor cone decomposition Theorem 8 (Softmax Taylor components factor through cone atoms). Let z=⟨,⟩z= q, k for unit vectors ,∈d−1 q, k ^d-1, and define r()=vec(⊗r) t_r( x)=vec( x r). Every even Taylor monomial factors through rank-one PSD atoms: z2r=⟨r()r()⊤,r()r()⊤⟩F.z^2r= t_r( q) t_r( q) , t_r( k) t_r( k) _F. The odd-degree terms become nonnegative after Lorentz gating, and the exponential kernel admits the decomposition: ez=∑r=0∞z2r(1+z)(2r+1)!+∑r=1∞2rz2r(2r+1)!.e^z= _r=0^∞ z^2r(1+z)(2r+1)!+ _r=1^∞ 2r\,z^2r(2r+1)!. Proof. For unit , q, k and r()=vec(⊗r) t_r( x)=vec( x r): ⟨r(),r()⟩=⟨,⟩r=zr. t_r( q), t_r( k) = q, k ^r=z^r. Thus: z2r=⟨r(),r()⟩2=⟨r()r()⊤,r()r()⊤⟩F,z^2r= t_r( q), t_r( k) ^2= t_r( q) t_r( q) , t_r( k) t_r( k) _F, which is the inner product of two rank-one rays in the PSD cone over the r-fold tensor feature space. An odd monomial satisfies z2r+1<0z^2r+1<0 at =− k=- q and therefore violates nonnegativity on the full sphere. Let ℓ()=(,1) ( x)=( x,1). For ∈d−1 x ^d-1, ℓ()∈∂ℒ+d+1 ( x)∈∂L^d+1_+ and: ⟨ℓ(),ℓ()⟩=1+z. ( q), ( k) =1+z. Consequently: z2r(1+z)=⟨r()r()⊤,r()r()⊤⟩F⟨ℓ(),ℓ()⟩,z^2r(1+z)= t_r( q) t_r( q) , t_r( k) t_r( k) _F ( q), ( k) , the product of a rank-one PSD-ray kernel and a Lorentz-ray kernel. Equivalently, define: Φr()=(r()r()⊤)⊗ℓ(). _r( x)= ( t_r( x) t_r( x) ) ( x). Then ⟨Φr(),Φr()⟩=z2r(1+z) _r( q), _r( k) =z^2r(1+z) under the tensor-product inner product, making the “multiplication” a standard feature-map tensoring operation. It remains to check that the Taylor coefficients can be regrouped this way. Absolute convergence on [−1,1][-1,1] permits rearrangement, and: ∑r=0∞z2r(1+z)(2r+1)!+∑r=1∞2rz2r(2r+1)! _r=0^∞ z^2r(1+z)(2r+1)!+ _r=1^∞ 2r\,z^2r(2r+1)! has odd coefficient 1/(2r+1)!1/(2r+1)! on z2r+1z^2r+1 and even coefficient: 1(2r+1)!+2r(2r+1)!=1(2r)! 1(2r+1)!+ 2r(2r+1)!= 1(2r)! on z2rz^2r for r≥1r≥ 1, while the constant term is 11. This is exactly the Taylor series of eze^z. ∎ Theorem 9 (Lorentz Rankin wall). Let 0≤ϵ<1/20≤ε<1/2. Any configuration of N unit vectors on the extreme rays of ℒ+dL^d_+ with pairwise interference at most ϵε satisfies: N≤mind, 1+11−2ϵ.N≤ \! \d,\,1+ 11-2ε \. Appendix D KATA variants and recurrences D.1 Variant taxonomy We use three explicit KATA variants: Plain KATA (additive recurrence, no gate). t=t−1+ψ(t)t⊤ S_t= S_t-1+ψ( k_t) v_t , t=t−1+ψ(t) Z_t= Z_t-1+ψ( k_t), with the convex output gate of Proposition˜1 applied at readout. Best on MQAR (the state is purely accumulative); fails on overwrite (no mechanism to discard a stale binding). GatedKATA (multiplicative scalar state gate). t=γtt−1+ψ(t)t⊤ S_t= _t S_t-1+ψ( k_t) v_t with a learned scalar γt∈[0,1] _t∈[0,1]. The parameter-free convex output gate of Proposition˜1 acts at readout and leaves t S_t unchanged. The learned γt _t enters the recurrence and changes the relative weights stored in the state. Unrolling assigns write s the multiplicative weight ∏r=s+1tγr _r=s+1^t _r, producing token-dependent positional weighting that generally favors recent writes. The overwrite gains identify this positional weighting as the gate’s leading role, with state-norm control as a secondary effect; see Section˜5.2. GatedDeltaKATA (PSD inside the GDN raw-key recurrence). The recurrence is: t=γt[t−1−βtψ(t)ψ(t)⊤t−1]+βtψ(t)t⊤. S_t= _t [ S_t-1- _tψ( k_t)ψ( k_t) S_t-1 ]+ _tψ( k_t) v_t . This is Gated DeltaNet’s recurrence with the rank-one erase term applied to ψ(t)ψ( k_t); GDN applies the same term to the raw t k_t. The construction inherits GDN’s overwrite semantics and uses a Welch-cone PSD feature as its key substrate. Comparison with GDN’s raw-key geometry. Gated DeltaNet’s recurrence treats the unit-normalized key t∈d−1 k_t ^d-1 as the feature itself. Under the nonnegative Lorentz lift, any strict interference tolerance ϵ<1/2ε<1/2 forces negative raw-key inner products and hence permits at most mind+1,1+1/(1−2ϵ) \d+1,1+1/(1-2ε)\ keys by Theorem˜9. At the boundary ϵ=1/2ε=1/2, nonpositive inner products permit up to 2d2d keys; for dhead=128d_head=128, this boundary is 256256 tokens, consistent with the empirical degradation between K=256K=256 and K=512K=512. The rank-one factors used by KATA-Mgg live in +pS^p_+ with p=dhead/gp=d_head/g; KATA-Σg g sums the corresponding block outer products within the same cone. Their packing is governed by Theorem˜3: above the 1/p1/p Welch scale, the spherical-cap construction gives exponential address capacity in p at any fixed interference tolerance. This larger geometric packing budget is consistent with the MQAR trend at comparable fixed-state budgets. D.2 Chunkwise forward pass Algorithm 1 KATA chunkwise forward pass for one head and one layer 1:,∈ℝT×d Q, K ^T× d, ∈ℝT×dv V ^T× d_v, chunk size C, cone map ψ 2:NC←⌈T/C⌉N_C← T/C ; pad the final chunk to length C 3:[0]←nψ×dv S_[0] 0_n_ψ× d_v, [0]←nψ Z_[0] 0_n_ψ 4:for t=0,…,NC−1t=0,…,N_C-1 do 5: load [t],[t],[t] Q_[t], K_[t], V_[t] into SRAM 6: Ψ([t]),Ψ([t])←ψ([t]),ψ([t]) ( Q_[t]), ( K_[t])←ψ( Q_[t]),ψ( K_[t]) ⊳ in-SRAM expansion 7: compute [t] O_[t] via Equation˜20 8: update [t+1],[t+1] S_[t+1], Z_[t+1] via Equation˜17 9:end for 10:return =[[0];…;[NC−1]] O=[ O_[0];…; O_[N_C-1]], truncated to T tokens D.3 Delta-rule chunked forward and backward Recurrence. The delta variant replaces the additive write with a content-based erase applied in feature space. With per-token strength βt∈(0,1) _t∈(0,1), the pseudo-values t∈ℝdv u_t ^d_v are defined by forward substitution on a lower-triangular system, and the readout reads them out through the PSD kernel: t=βt(t−∑s<t⟨ψ(s),ψ(t)⟩s),t=∑s≤t⟨ψ(t),ψ(s)⟩s. u_t= _t ( v_t-\! _s<t\! ψ( k_s),ψ( k_t) \, u_s ), o_t= _s≤ t ψ( q_t),ψ( k_s) \, u_s. (28) The erase kernel is the PSD Gram ⟨ψ(s),ψ(t)⟩=∑ij(s,i⋅t,j)2 ψ( k_s),ψ( k_t) = _ij( k_s,i\!·\! k_t,j)^2 (KATA-Σg g, with i,ji,j over the g groups). GDN uses the raw s⋅t k_s\!·\! k_t kernel. The readout is unnormalized (no denominator), and the online Widrow–Hoff erase keeps =∑sψ(s)s⊤∈ℝnψ×dv S= _sψ( k_s) u_s ^n_ψ× d_v bounded. Chunked forward (WY-free). Let S be the state entering chunk [c][c]. Form the two C×C× C Gram blocks Atskk=∑ij(t,i⋅s,j)2A^k_ts= _ij( k_t,i\!·\! k_s,j)^2 and Atsqk=∑ij(t,i⋅s,j)2A^qk_ts= _ij( q_t,i\!·\! k_s,j)^2 directly from the raw projections; no nψ×nψn_ψ× n_ψ erase matrix is formed. With =diag()tril(Akk,−1) N= diag( β)\,tril(A^k,-1): ′ V =[c]−Ψ([c]), = V_[c]- ( K_[c])\, S, T =(+)−1=∑r≥0(−)r, =( I+ N)^-1= _r≥ 0(- N)^r, (29) U =diag()′, = T\, diag( β)\, V , [c] O_[c] =Ψ([c])+tril(Aqk), = ( Q_[c])\, S+tril(A^qk)\, U, (30) ′ S =+Ψ([c])⊤. = S+ ( K_[c]) U. (31) Since N is strictly lower-triangular (nilpotent, C=0 N^C=0), the inverse T is exact after ⌈log2C⌉ _2C Neumann doublings; only C×C× C, C×dvC× d_v, and the nψ×dvn_ψ× d_v state ever reside in SRAM. Chunked backward. The backward is a reverse scan over chunks carrying the state cotangent d+d S_+ (from later chunks); the forward quantities ,,,′ S, T, U, V are recomputed from the checkpointed S. Per chunk (all += += accumulate into dd S, returned to chunk [c−1][c-1]): dΨ() ( Q) =d[c]⊤, =d O_[c] S , d S =Ψ()⊤d[c]+d+, = ( Q) d O_[c]+d S_+, dAqk ^qk =tril(d[c]⊤), =tril\! (d O_[c] U ), d U =tril(Aqk)⊤d[c]+Ψ()d+, =tril(A^qk) d O_[c]+ ( K)d S_+, d T =d(diag()′)⊤, =d U ( diag( β) V ) , d′ V =diag()⊤d, = diag( β) T d U, d N =−⊤d⊤, =- T d T\, T , dAkk ^k =diag()tril(d,−1), = diag( β)\,tril(d N,-1), d[c] V_[c] =d′, =d V , d S -=Ψ()⊤d′, -= ( K) d V , dΨ() ( K) =d+⊤−d′⊤ = Ud S_+ -d V S +(dAkk+dAkk⊤)Ψ()+dAqk⊤Ψ(), +(dA^k+dA^k ) ( K)+dA^qk ( Q), dΨ() ( Q) +=dAqkΨ(), +=dA^qk ( K), d β =rowsum(′⊙⊤d) =rowsum\! ( V T d U ) +rowsum(tril(Akk,−1)⊙d). +rowsum\! (tril(A^k,-1) N ). (32) The only non-matmul VJP is the matrix-inverse term d=−⊤d⊤d N=- T d T\, T ; the feature-map VJP closes the chain, dg=(dΨ()g+dΨ()g⊤)gd k_g=(d ( K)_g+d ( K)_g ) k_g per group (and likewise for q). The backward therefore has the same (TC+Tnψdv/C)O\! (TC+T\,n_ψ\,d_v/C ) cost profile as the forward, with a single nψ×dvn_ψ× d_v state cotangent streamed across chunks. Appendix E Hardware implementation and benchmarks E.1 Associative-scan kernel The chunked attention forward decomposes into three stages, each launched as a separate Triton kernel that communicates with the next through small HBM buffers at chunk boundaries. Let C denote the chunk size and define the number of chunks as: NC≔⌈TC⌉.N_C TC . The final chunk is padded when C does not divide T. The analysis assumes already-feature-mapped inputs =ψ(^) q=ψ( q) and =ψ(^) k=ψ( k) in ℝnψR^n_ψ, where nψn_ψ denotes the active post-feature dimension. Three-kernel pipeline. (i) Chunk-state computes, for every chunk c: loc(c)=[c]⊤[c]∈ℝnψ×dv,loc(c)=⊤[c]∈ℝnψ. S^(c)_loc= K_[c]^\! V_[c] ^n_ψ× d_v, Z^(c)_loc=1^\! K_[c] ^n_ψ. All (b,h,c)(b,h,c) triples are independent, exposing B⋅H⋅NCB\!·\!H\!·\!N_C programs. (i) Inter-chunk reduction computes the exclusive prefix: (pre(c),pre(c))=∑c′<c(loc(c′),loc(c′))( S^(c)_pre, Z^(c)_pre)= _c <c( S^(c )_loc, Z^(c )_loc) along the chunk axis. This is the only stage with a cross-chunk dependency. (i) Chunk-output combines the inter-chunk prefix with the local C×C\!×\!C causal pattern to produce [c] O_[c]. Associative scan versus sequential scan. The standard chunk-parallel implementation (FLA’s linear-attention kernel [yang24fla]) evaluates the prefix sequentially over NCN_C chunks, giving depth Θ(NC) (N_C). Our associative scan uses ⌈log2NC⌉ _2N_C rounds, each parallel across the NCN_C chunk slots. Its total work is (NClogNC⋅nψdv)O(N_C N_C· n_ψd_v), compared with (NCnψdv)O(N_Cn_ψd_v) for the linear scan, while its parallel depth is (logNC⋅dv)O( N_C· d_v). With one program per batch index b, head index h, and feature index i∈1,…,nψi∈\1,…,n_ψ\, all B⋅H⋅nψB\!·\!H\!·\!n_ψ feature slices scan independently. Wall-clock model. The three stages have wall-clock cost: ttotal=(Cnψdv)⏟chunk-state+(logNC⋅dv)⏟tree-scan+(Cnψdv+C2(nψ+dv))⏟chunk-output.t_total= O(Cn_ψd_v)_chunk-state+ O( N_C· d_v)_tree-scan+ O(Cn_ψd_v+C^2(n_ψ+d_v))_chunk-output. The middle term replaces the linear-scan baseline’s (NCdv)O(N_Cd_v). At T=2048T=2048 and C=32C=32, the scan depth decreases from NC=64N_C=64 to log2NC=6 _2N_C=6. In practice, the scan stage is a small fraction of the wall-clock time. The dominant cost is the HBM write of loc S_loc and the subsequent prefix read. Reducing the per-chunk state through a smaller nψn_ψ, as in orthant, Lorentz, or grouped PSD features, therefore translates directly into higher throughput. Measured throughput (H100 SXM, bf16, B=4B=4, H=12H=12, dv=64d_v=64). Throughput in million tokens/s, C=32C=32, against FLA’s linear-attention kernel on the same materialized inputs: T NCN_C feature map nψn_ψ tree (Mtok/s) linear (Mtok/s) FLA (Mtok/s) 10241024 32 orthant 64 25.6 24.1 10.78 10241024 32 lorentz 64 25.6 24.1 12.05 20482048 64 orthant 64 30.3 27.3 23.41 20482048 64 lorentz 64 30.3 27.3 23.41 40964096 128 orthant 64 33.5 29.8 37.2 At T≤2048T\!≤\!2048, the tree-scan kernel delivers 2.12.1–2.4×2.4× the throughput of FLA at T=1024T=1024 and 1.3×1.3× at T=2048T=2048; tree versus linear within the same dispatch is a consistent 1.061.06–1.12×1.12× throughput gain that grows with NCN_C. At T=4096T=4096, chunk-state becomes HBM-bound, and FLA’s internal nψn_ψ-axis tiling overtakes our single-tile output kernel. The asymptotic logNC N_C advantage is then hidden by the bandwidth ceiling on writes of loc S_loc. For PSD-packed nψ≥1024n_ψ\!≥\!1024, FLA’s pre-materialize path with internal feature-axis tiling currently wins. Adding the same tiling to the tree-scan output kernel is the natural follow-on. E.2 Induction-head benchmark d=128d=128 d=256d=256 d=512d=512 d=1024d=1024 d=2048d=2048 Softmax (FA) acc 1.00 1.00 1.00 1.00 1.00 Softmax (FA) phase step 2k 2k 3k 3k 4k KATA-Σ2 2 acc 1.00 1.00 1.00 1.00 0.99 KATA-Σ2 2 phase step 2k 2k 2k 3k 8k The two model families are aligned on the Zoology [arora23zoology] backbone: two-layer pre-norm transformer, dmodel=128d_model=128, four heads, 4×4× GELU state mixer, LM head weight-tied to the token embedding, Zoology-style Linear/Embedding init with std=0.02=0.02 and GPT-2 residual scaling. Softmax uses F.scaled_dot_product_attention; KATA-Σ2 2 uses the fused rank-2 Triton forward with a matched PyTorch backward. The phase-transition budget scales comparably to softmax at all scales tested, but without softmax’s (T2)O(T^2) memory and compute. E.3 KATA kernel microbenchmark Forward and forward+backward wall-clock time on an NVIDIA H100 for the rank-two KATA-Σ2 2 kernel, using a fused Triton forward and a PyTorch backward over saved chunk-boundary states in fp32: T KATA-Σ2 2 fwd KATA-Σ2 2 fwd+bwd peak mem (bwd) 512 0.67 ms 3.58 ms 0.28 GB 1024 1.13 ms 6.55 ms 0.55 GB 2048 2.34 ms 12.07 ms 1.07 GB 4096 3.98 ms 23.49 ms 2.13 GB 8192 7.81 ms 46.66 ms 4.26 GB The fused kernel scales linearly with T and stays near peak bandwidth; no per-token ψ tensor is written to HBM. The PyTorch backward rematerializes ψ once per chunk, avoiding an (Tnψ)O(Tn_ψ) footprint. A fused backward kernel is left for future work. E.4 Detailed benchmark numbers The tables below give the exact benchmark values. Tables˜8 and 9 tabulate the forward and training-step curves in Figure˜4; Table˜10 reports the B×TB× T forward-throughput grid; and Table˜11 isolates the associative-scan and sequential-scan comparison at B=1B=1. Table 8: Forward latency versus sequence length. Wall-clock milliseconds on one NVIDIA H100 (B=8B=8, H=16H=16, dhead=64d_head=64, bf16); lower is better. Baselines quadratic KATA-Mgg (T2)O(T^2) linear-state KATA-Mgg (T)O(T) T FA-2 GDN M1 M2 M1 M2 11K 0.090.09 0.540.54 0.070.07 0.070.07 2.682.68 0.680.68 22K 0.270.27 0.530.53 0.180.18 0.210.21 5.225.22 1.331.33 44K 0.930.93 0.660.66 0.580.58 0.720.72 10.3410.34 2.702.70 88K 3.503.50 1.301.30 2.202.20 2.822.82 20.5820.58 5.345.34 1616K 13.7813.78 2.592.59 8.928.92 10.6210.62 41.1441.14 10.6810.68 3232K 54.5654.56 5.245.24 34.5634.56 47.0747.07 82.0482.04 21.3421.34 6464K 234.2234.2 10.6710.67 150.8150.8 168.7168.7 164.1164.1 42.7042.70 128128K 943.9943.9 21.3621.36 573.9573.9 702.2702.2 327.9327.9 85.6685.66 Table 9: Training-step latency versus sequence length. Forward-plus-backward milliseconds on one NVIDIA H100 (B=8B=8, H=16H=16, dhead=64d_head=64, bf16); lower is better. Linear-state KATA-Mgg uses the (T)O(T) two-pass backward. Baselines quadratic KATA-Mgg (T2)O(T^2) linear-state KATA-Mgg (T)O(T) T FA-2 GDN M1 M2 M1 M2 11K 0.440.44 2.622.62 0.690.69 0.720.72 10.1410.14 3.373.37 22K 1.151.15 2.372.37 1.311.31 2.242.24 20.0720.07 6.626.62 44K 3.703.70 2.352.35 4.014.01 7.517.51 39.9339.93 13.1113.11 88K 13.2113.21 4.534.53 14.1514.15 27.6627.66 79.5879.58 26.0626.06 1616K 49.9749.97 9.079.07 53.6653.66 106.4106.4 159.1159.1 52.1452.14 3232K 197.1197.1 18.5818.58 217.9217.9 418.8418.8 317.6317.6 103.8103.8 Table 10: Forward throughput across the B×TB× T grid. Mtok/s on one NVIDIA H100 (H=16H=16, dhead=64d_head=64, bf16), sorted by B⋅TB\!·\!T. Tree-scan and linear-chunk use matched d×d×d states with C=128C=128. Speedup is tree-scan over linear-chunk; higher is better. B T B⋅TB\!·\!T GDN Linear-chunk Tree-scan speedup 11 22K 22K 2.52.5 4.94.9 14.214.2 2.9×2.9× 11 88K 88K 10.110.1 21.421.4 44.244.2 2.1×2.1× 44 22K 88K 9.19.1 19.619.6 64.964.9 3.3×3.3× 11 3232K 3232K 30.330.3 24.924.9 49.249.2 2.0×2.0× 44 88K 3232K 38.138.1 37.637.6 80.080.0 2.1×2.1× 1616 22K 3232K 35.935.9 40.840.8 93.393.3 2.3×2.3× 11 6464K 6464K 30.630.6 25.425.4 67.667.6 2.7×2.7× 3232 22K 6464K 49.749.7 42.642.6 99.099.0 2.3×2.3× 44 3232K 128128K 45.945.9 39.239.2 84.784.7 2.2×2.2× 1616 88K 128128K 48.348.3 41.941.9 100.5100.5 2.4×2.4× 44 6464K 256256K 45.345.3 39.639.6 82.882.8 2.1×2.1× 3232 88K 256256K 49.849.8 43.243.2 103.1103.1 2.4×2.4× 1616 3232K 512512K 47.647.6 41.741.7 102.3102.3 2.5×2.5× 1616 6464K 11M 46.746.7 41.141.1 88.388.3 2.2×2.2× 3232 3232K 11M 48.648.6 42.342.3 104.2104.2 2.5×2.5× 3232 6464K 22M 47.647.6 37.437.4 89.489.4 2.4×2.4× Table 11: Small-batch associative-scan throughput. Forward Mtok/s at B=1B=1 on one NVIDIA H100 (H=16H=16, dhead=64d_head=64, bf16). Tree-scan and linear-chunk use ψ()=ψ( x)= x, C=128C=128, and matched d×d×d states; Gated DeltaNet is shown for reference. Speedup is tree-scan over linear-chunk; higher is better. T Gated DeltaNet Linear-chunk Tree-scan speedup (Mtok/s) (Mtok/s) (Mtok/s) vs. chunk 2 0482\,048 2.62.6 6.76.7 19.419.4 2.9×2.9× 4 0964\,096 4.74.7 13.613.6 39.939.9 2.9×2.9× 8 1928\,192 8.18.1 23.423.4 44.544.5 1.9×1.9× 16 38416\,384 18.718.7 24.124.1 47.647.6 2.0×2.0× 32 76832\,768 30.430.4 24.924.9 49.449.4 2.0×2.0× 65 53665\,536 28.128.1 25.525.5 67.567.5 2.6×2.6× 131 072131\,072 30.830.8 25.825.8 69.469.4 2.7×2.7× Appendix F Experimental protocols and architectures F.1 MQAR worked example and protocol Each MQAR example packs K distinct key–value pairs and K queries into a single sequence of length T=4KT=4K: the first 2K2K tokens interleave the K bindings (k1,v1,…,kK,vK)(k_1,v_1,…,k_K,v_K), then the remaining 2K2K positions reissue the K keys in random order, each followed by an answer slot the model must fill. Loss is computed only at answer positions, so the model must (i) store all K bindings presented in the first half and (i) retrieve the correct value an arbitrary number of steps later. Keys and values are drawn from V=8192V=8192, so random guessing floors at 1/8192≈1.2×10−41/8192≈ 1.2\!×\!10^-4. A worked K=4K=4, T=16T=16 example: position 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 input A 7 B 3 C 9 D 1 C ? A ? D ? B ? target 9 7 1 3 At K=1024K=1024, T=4096T=4096: 10241024 disjoint bindings must survive through up to 40964096 intervening tokens before the recurrent state is queried, with the state discriminating among 10241024 possibilities at each answer slot. F.2 Additive and convex output-gate ablation At dmodel=128d_model=128 with one head and KATA-Σ2 2 features: Gate state (B) T=1024T=1024 T=2048T=2048 T=3072T=3072 T=4096T=4096 Convex 1,066,496 0.997 0.864 0.567 0.335 Additive (GatedKATA-Σ4 4) 271,872 0.999 0.955 0.782 0.572 F.3 MQAR architecture and training Every model uses the canonical Zoology TransformerBlock. Its state mixer is Identity, and its sequence mixer is Hybrid(BaseConv, mixer), so one short depthwise convolution precedes every sequence operator. We use one head, following Zoology’s convention dhead=dmodeld_head=d_model, no positional embeddings, a tied LM head, and vocabulary size V=8192V=8192. Training uses batch size 256256, AdamW with wd=0.1wd=0.1, cosine annealing over 3232 epochs, and a three-point learning-rate sweep 10−3,3×10−3,10−2\10^-3,3\!×\!10^-3,10^-2\ with the best run selected per row. Training mixes streams up to Ktrain=64K_train=64 at T=256T=256; evaluation uses K∈128,256,512,768,1024K∈\128,256,512,768,1024\ and T∈512,1024,2048,3072,4096T∈\512,1024,2048,3072,4096\. GatedDeltaKATA in the overwrite table uses the full GDN-style configuration: ShortConv(k=4)(k=4) on q/ k/ v, GDN-style decay parameterization (Alog,dtbias,aproj)(A_log,d_tbias,a_proj), RMSNormRMSNorm on the output, and v-expansion 2×2×. GatedDeltaKATA applies the rank-11 erase to ψ(t)ψ( k_t), while GDN applies it to the raw t k_t; this is the single functional difference. Total state 141141 KB matches GDN’s 133133 KB; parameter counts match within 1%1\%. F.4 Per-method architectures and reproducibility We list, for each row in Sections˜5.1 and 5.2, the precise projections, gates, normalizations, and feature maps so that each architecture can be reproduced from a fresh TransformerBlock skeleton. All variants share the canonical Zoology outer loop described above (two-layer hybrid block, BaseConv(k=3)(k=3), no positional embeddings unless explicitly stated, tied LM head, vocab V=8192V=8192). Differences below concern only the sequence-mixer module. Throughout, d≡dmodeld≡ d_model; with H=1H=1, we have dhead=d_head=d. Plain KATA (additive recurrence with denominator). Three projections Wq,Wk,Wv∈ℝd×dW_q,W_k,W_v ^d× d are followed by a reduced PSD feature map. KATA-Σ2 2 splits k into ,∈ℝd/2 a, b ^d/2 and uses ψ()=ϵ+⊤+⊤ψ( k)=ε I+ a a + b b . KATA-Σ4 4 splits it into 1,…,4∈ℝd/4 a_1,…, a_4 ^d/4 and uses ψ()=ϵ+14∑i=14ii⊤ψ( k)=ε I+ 14 _i=1^4 a_i a_i . The factor 1/41/4 is the numerical scale used in the reported Σ4 4 configuration. It cancels from normalized plain-KATA weights as ϵ→0ε→ 0 and is retained as part of the unnormalized gated configuration. In either case, nψ=m(m+1)/2n_ψ=m(m+1)/2 for block width m=d/gm=d/g. The chunkwise recurrence computes the numerator and denominator with the packed feature map, and returns t=ψ(t)⊤t/ψ(t)⊤t o_t=ψ( q_t) S_t/ψ( q_t) Z_t followed by Wo∈ℝd×dW_o ^d× d. The extras configuration adds depthwise ShortConv(k=4)(k=4), per-head RMSNorm, and value expansion 2×2×; ϵ=10−4ε=10^-4. KATA-Orthant. Same Wq,Wk,WvW_q,W_k,W_v projections; feature map ψ()=ReLU()+ϵψ( x)=ReLU( x)+ε 1, post-feature dimension nψ=dn_ψ=d. The recurrence is normalized linear attention, t=t−1+ψ(t)t⊤ S_t= S_t-1+ψ( k_t) v_t , t=t−1+ψ(t) Z_t= Z_t-1+ψ( k_t), t=(ψ(t)⊤t)/(ψ(t)⊤t) o_t=(ψ( q_t) S_t)/(ψ( q_t) Z_t), implemented via FLA’s normalized linear-attention kernel. ShortConv(k=4)(k=4) and output RMSNormRMSNorm are enabled; ϵ=10−6ε=10^-6. KATA-Lorentz. Identical to KATA-Orthant except for the feature map: with ∈ℝd x ^d, write =1:d−1 y= x_1:d-1 and s=xds=x_d, then ψ()=(,∥2(1+s2))∈ℝdψ( x)=( y,\; y _2(1+s^2)) ^d. The image lies in the closed Lorentz cone (,t):t≥∥2\( y,t):t≥ y _2\ so ⟨ψ(),ψ()⟩≥0 ψ( x),ψ( y) ≥ 0. State and dispatch are identical to the orthant case. GatedKATA (additive scalar decay, no denominator). Adds a single per-head per-token log-decay projection Wα∈ℝd×HW_α ^d× H (with bias) producing logγt=logσ(Wαt)∈ℝH _t= σ(W_α x_t) ^H. The recurrence is t=γtt−1+ψ(t)t⊤ S_t= _t\, S_t-1+ψ( k_t) v_t , t=ψ(t)⊤t o_t=ψ( q_t) S_t (no denominator), implemented via FLA’s simple gated-linear-attention kernel on the packed ψ with the per-token gate. The convex-gate ablation pre-scales t v_t by 1−γt1- _t before the same kernel, yielding t=γtt−1+(1−γt)ψ(t)t⊤ S_t= _t S_t-1+(1- _t)ψ( k_t) v_t . The KATA-Σ2 2 and KATA-Σ4 4 feature variants are as above; ϵ=10−4ε=10^-4. GatedDeltaKATA (PSD inside the GDN raw-key recurrence). Component-for-component match to Gated DeltaNet except for the substitution of ψ(t)ψ( k_t) for t k_t in the recurrence. Projections: Wq,Wk∈ℝd×dW_q,W_k ^d× d, Wv∈ℝd×2dW_v ^d× 2d (default v-expansion 2×2×). Depthwise ShortConv(k=4)(k=4) on ,, q, k, v, no SiLU. Beta projection Wβ∈ℝd×HW_β ^d× H producing βt=σ(Wβt) _t=σ(W_β x_t). Decay parameterization, matching FLA’s gated-delta-rule kernel, gt=−exp(Alog)⊙softplus(Wαt+dt_bias)g_t=- (A_log) (W_α x_t+dt\_bias) with Alog∈ℝHA_log ^H initialized by logU(0,16) U(0,16) and dt_bias∈ℝHdt\_bias ^H calibrated so that softplus(dt_bias)∼U(10−3,10−1)softplus(dt\_bias) U(10^-3,10^-1); AlogA_log and dt_biasdt\_bias are excluded from weight decay. The recurrence is: t=γt[t−1−βtψ(t)ψ(t)⊤t−1]+βtψ(t)t⊤. S_t= _t [ S_t-1- _tψ( k_t)ψ( k_t) S_t-1 ]+ _tψ( k_t) v_t . This recurrence is delegated to FLA’s gated-delta-rule kernel on packed ψ; the rank-11 erase ψ(t)⊤t−1ψ( k_t) S_t-1 is contracted directly, so the nψ×nψn_ψ× n_ψ matrix ψ(t)ψ(t)⊤ψ( k_t)ψ( k_t) is never materialized. Output passes through per-head RMSNormRMSNorm (ϵnorm=10−5ε_norm=10^-5) and Wo∈ℝ2d×dW_o ^2d× d. KATA-Σ4 4 uses H=2H=2 because the kernel requires packed feature dimension at most 256256; the packed dimension is 528528 at H=1,d=128H=1,d=128 and 136136 at H=2H=2. Optional knobs (disabled in the reported runs unless noted): per-head ℓ2 _2 normalization of , q, k before ψ with ϵ=10−6ε=10^-6; RoPE on , q, k with base 10410^4. Gated DeltaNet (baseline). FLA’s GatedDeltaNet mixer used out-of-the-box, configured to match the surrounding skeleton: l_max set to the longest evaluation sequence, NH=1=1, use_short_conv= use\_short\_conv=True (k=4k=4), use_gate= use\_gate=False. Feature substrate: raw t∈d−1 k_t ^d-1 (FLA’s use_qk_l2norm_in_kernel). Recurrence is identical in form to GatedDeltaKATA above with ψ()=ψ( k)= k. State per head is d×2d× 2d (for v-expansion 22); at d=128,d=128, NH=1=1, total ∼133 \!133 KB. Softmax attention (full / sliding window). A standard MHA block uses PyTorch scaled dot-product attention (SDPA) with a causal mask. Three projections Wq,Wk,Wv∈ℝd×dW_q,W_k,W_v ^d× d and an output Wo∈ℝd×dW_o ^d× d surround the attention operator. The ++\!RoPE variant rotates , q, k before SDPA with base θ∈104,5×104θ∈\10^4,5\!×\!10^4\; reported runs use θ=5×104θ=5\!×\!10^4. The sliding-window variant restricts the mask to the W=256W=256 tokens preceding the query and caches the boolean mask. We use PyTorch’s memory-efficient SDPA backend for this configuration. At sequence length T, the KV cache contains 2dT2dT floats for full softmax and 2dW2dW for sliding-window attention. Initialization and optimization. Linear layers use Zoology’s (0,0.022)N(0,0.02^2) initialization, with GPT-2 residual scaling 1/2Nlayers1/ 2N_layers on WoW_o, and the LM head is tied to the embeddings. We use AdamW (β1=0.9,β2=0.95)( _1=0.9, _2=0.95), weight decay 0.10.1 except on AlogA_log and dt_biasdt\_bias, gradient clipping at 1.01.0, and a 3232-epoch cosine schedule without warmup. For each row, we select the best learning rate in 10−3,3×10−3,10−2\10^-3,3\!×\!10^-3,10^-2\ and stop when the hardest extrapolation slice reaches 0.9990.999 accuracy.