Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention

# Three Tokens Force Exponential Feature Rankin Nonnegative Kernel Attention
Source: [https://arxiv.org/html/2608.11427](https://arxiv.org/html/2608.11427)
###### Abstract

Full attention exposes every token pair, whereas kernel attention compresses a sequence into a fixed\-dimensional sketch\. We show that this distinction becomes exponential at the first context length containing two competing candidates\. On Min\-IP over Boolean inputs, rank\-one normalized kernel attention solves every sequence of length at most two exactly\. In contrast, any single normalized nonnegative kernel\-attention head that succeeds on all three\-token sequences with error strictly below1/21/2requires2Ω⁡\(m\)2^\{\\Omega\(m\)\}features, even with arbitrary finite\-dimensional tokenwise values and an arbitrary query\-dependent affine readout\. Dense softmax solves the same task withmm\-dimensional scores and constant temperature\. The conclusion survives position\-dependent token maps and a causal final query\. As context length grows, the lower bound approaches the exact2m2^\{m\}\-feature realization\. Separately, for deterministic multihead, multilayer sketch models whose cross\-token channels have finite alphabets, we prove a transcript lower bound linear in the number of independent answers and logarithmic in their alphabet size\.

## 1Introduction

One way to study the expressive power of attention is to isolate the basic operations that an attention layer makes available to a larger computation\. Content\-dependent selection is especially native to attention: a query compares several candidate tokens and routes information according to the most favorable score\. Nearest\-neighbor and minimum\-inner\-product primitives have therefore served as testbeds for separating attention architectures, as seen in[16](https://arxiv.org/html/2608.11427#bib.bib4),[2](https://arxiv.org/html/2608.11427#bib.bib7), and[1](https://arxiv.org/html/2608.11427#bib.bib8)\.

Full self\-attention implements this primitive explicitly: each query compares itself directly with every token in a sequence\([13](https://arxiv.org/html/2608.11427#bib.bib1)\)\. This interaction materializesN2N^\{2\}pairwise scores\. Kernelized linear attention instead factors the attention kernel and aggregates the sequence into sufficient statistics such as a key–value matrix and a key sum, as in[10](https://arxiv.org/html/2608.11427#bib.bib2)and[6](https://arxiv.org/html/2608.11427#bib.bib3)\. It avoids forming the pairwise matrix, but every query now receives the rest of the sequence through a shared, fixed\-dimensional sketch\. The question is thus not merely whether individual kernel entries can be approximated, but whether explicit comparison can be replaced by a compressed additive representation\.

We isolate this question through*Min\-IP*\. Given a sequenceX=\(x1,…,xN\)X=\(x\_\{1\},\\ldots,x\_\{N\}\)of Boolean tokensxi∈\{0,1\}mx\_\{i\}\\in\\\{0,1\\\}^\{m\}, the target at every position is

ti​\(X\)=min1≤j≤N⁡⟨xi,xj⟩\.t\_\{i\}\(X\)=\\min\_\{1\\leq j\\leq N\}\\langle x\_\{i\},x\_\{j\}\\rangle\.\(1\)Asking only for the best score, rather than the identity of a minimizing token, removes key–value routing and output\-encoding complications: the model only has to perform the comparison\. Self\-token interactions, repeated tokens, and ties are included\. The task is inspired by Orthogonal Vectors becauseti=0t\_\{i\}=0exactly whenxix\_\{i\}has an orthogonal partner in the sequence, but our lower bounds are unconditional architecture theorems rather than fine\-grained complexity consequences\.

Why focus on the shortest possible context? Linear attention is often motivated as a long\-context alternative to full attention, so its limitations are naturally associated with compressing many tokens into a fixed\-size state\. We show that the obstruction appears much earlier\. At length two, each query has only one cross\-token candidate, and a rank\-one normalized average retains enough information for an affine tokenwise readout to recover the answer\. At length three, the query must choose between two candidates, and uniform minimum retrieval already requires exponentially many nonnegative kernel features\. Long contexts amplify the bottleneck, but do not create it\.

The context\-length phase transition is sharp: rank one solves all lengths at most two exactly, whereas length three requires2Θ⁡\(m\)2^\{\\Theta\(m\)\}nonnegative kernel features\. Values may be arbitrary finite\-dimensional vectors and the readout may be an arbitrary query\-dependent affine map, so the separation is not caused by identity values or a narrow value projection\. The same exponential conclusion survives tokenwise positional maps and a causal database\-prefix/final\-query formulation\. As the fixed context length grows, the exponent approaches one, nearly matching an exact2m2^\{m\}positive\-feature endpoint\.

The proof uses only three families of inputs of the same length\. An exact linear identity eliminates all value contributions and forces a constant multiplicative preference whenever two candidate overlaps differ by a fixed gap\. Iterating over intermediate Boolean overlaps amplifies this preference exponentially\. A constant\-weight code and a nonsymmetric approximate\-identity lemma then turn it into a rank lower bound\.

We separately obtain a finite\-precision result for broader models\. A typed multilevel family embeds\(s\+1\)q\(s\+1\)^\{q\}independent output vectors into length\-2​q2qMin\-IP instances\. Any deterministic multilayer sketch model that solves them must therefore communicate at leastq​log2​\(s\+1\)q\\log\_\{2\}\(s\+1\)bits\. This result covers multiple heads, layers, signed sketches, and arbitrary local computation, provided every cross\-token channel is counted and has a finite alphabet\. It is an information bound, not a per\-head rank theorem\.

#### Contributions\.

We contribute three results:

- •A sharp three\-token phase transition: rank one suffices through total length two, while total length three requires2Ω⁡\(m\)2^\{\\Omega\(m\)\}nonnegative kernel features under arbitrary values and affine query\-dependent readout, including position\-dependent maps and a causal final query\.
- •A fixed\-length amplification mechanism whose exponent approaches the exact2m2^\{m\}positive\-feature endpoint, while dense softmax succeeds withmm\-dimensional scores and constant temperature at length three\.
- •A deterministicq​log2​\(s\+1\)q\\log\_\{2\}\(s\+1\)finite\-transcript bound for multiple heads and layers, plus two controlled feature\-capacity experiments that separate proof witnesses from learned OOD behavior\.

## 2Task and architecture

### 2\.1Min\-IP

Fix integersm,n≥1m,n\\geq 1\. Let𝒳m,n\\mathcal\{X\}\_\{m,n\}be the set of sequencesX=\(x1,…,xN\)X=\(x\_\{1\},\\ldots,x\_\{N\}\)with1≤N≤n1\\leq N\\leq nand tokensxi∈\{0,1\}mx\_\{i\}\\in\\\{0,1\\\}^\{m\}\. A model solves the task with errorε\\varepsilonif it outputs real scalarst^i​\(X\)\\widehat\{t\}\_\{i\}\(X\)satisfying

\|t^i​\(X\)−ti​\(X\)\|<ε∀X∈𝒳m,n,∀i∈\{1,…,\|X\|\}\.\\left\|\\widehat\{t\}\_\{i\}\(X\)\-t\_\{i\}\(X\)\\right\|<\\varepsilon\\qquad\\forall X\\in\\mathcal\{X\}\_\{m,n\},\\quad\\forall i\\in\\\{1,\\ldots,\|X\|\\\}\.\(2\)The main exact\-recovery regime is0<ε≤1/20<\\varepsilon\\leq 1/2\. Sincetit\_\{i\}is an integer and the inequality is strict, nearest\-integer rounding uniquely recovers every target\. The lower bound already holds under the weaker requirement of correctness only at length three\. Letr⋆​\(m,n\)r^\{\\star\}\(m,n\)denote the minimum positive feature dimension of a single architecture that succeeds at all lengths up tonnwith error<1/2<1/2\.

The cross\-attention version has fixed queriesqiq\_\{i\}and a databasedjd\_\{j\}, with targetminj⁡⟨qi,dj⟩\\min\_\{j\}\\langle q\_\{i\},d\_\{j\}\\rangle\. Type coordinates can embed it into self\-attention while making every query–query and unintended database overlap larger than the desired minimum\. Section[4](https://arxiv.org/html/2608.11427#S4)uses this device\.

### 2\.2Dense softmax attention

One head computes

si​j=q​\(xi\)⊤​k​\(xj\),wi​j=esi​j∑ℓ=1Nesi​ℓ,yi=∑j=1Nwi​j​v​\(xj\),s\_\{ij\}=q\(x\_\{i\}\)^\{\\top\}k\(x\_\{j\}\),\\qquad w\_\{ij\}=\\frac\{e^\{s\_\{ij\}\}\}\{\\sum\_\{\\ell=1\}^\{N\}e^\{s\_\{i\\ell\}\}\},\\qquad y\_\{i\}=\\sum\_\{j=1\}^\{N\}w\_\{ij\}v\(x\_\{j\}\),followed by a tokenwise scalar readout\. We call this*dense*or*full softmax attention*because every query scores every token\.

### 2\.3Normalized nonnegative kernel attention

LetϕQ,ϕK:\{0,1\}m→ℝr\\phi\_\{Q\},\\phi\_\{K\}:\\\{0,1\\\}^\{m\}\\to\\mathbb\{R\}^\{r\}induce

α⁡\(x,z\)=⟨ϕQ​\(x\),ϕK​\(z\)⟩≥0on the Boolean domain\.\\alpha\(x,z\)=\\langle\\phi\_\{Q\}\(x\),\\phi\_\{K\}\(z\)\\rangle\\geq 0\\qquad\\text\{on the Boolean domain\.\}The value mapv:\{0,1\}m→ℝdvv:\\\{0,1\\\}^\{m\}\\to\\mathbb\{R\}^\{d\_\{v\}\}is arbitrary\. The attention output for queryxix\_\{i\}is

ai​\(X\)=∑jα⁡\(xi,xj\)​v​\(xj\)∑jα⁡\(xi,xj\),a\_\{i\}\(X\)=\\frac\{\\sum\_\{j\}\\alpha\(x\_\{i\},x\_\{j\}\)v\(x\_\{j\}\)\}\{\\sum\_\{j\}\\alpha\(x\_\{i\},x\_\{j\}\)\},\(3\)where the denominator must be positive on every valid input\. The readout is an arbitrary query\-dependent affine map

t^i=β⁡\(xi\)\+w​\(xi\)⊤​ai​\(X\)\.\\widehat\{t\}\_\{i\}=\\beta\(x\_\{i\}\)\+w\(x\_\{i\}\)^\{\\top\}a\_\{i\}\(X\)\.\(4\)There are no positions, additional heads or layers, nonlinear post\-attention lookup, or other cross\-token channels in the headline theorem\.

The sequence enters Equation \([3](https://arxiv.org/html/2608.11427#S2.E3)\) only through

S=∑jϕK​\(xj\)​v​\(xj\)⊤∈ℝr×dv,z=∑jϕK​\(xj\)∈ℝr,S=\\sum\_\{j\}\\phi\_\{K\}\(x\_\{j\}\)v\(x\_\{j\}\)^\{\\top\}\\in\\mathbb\{R\}^\{r\\times d\_\{v\}\},\\qquad z=\\sum\_\{j\}\\phi\_\{K\}\(x\_\{j\}\)\\in\\mathbb\{R\}^\{r\},sinceai=ϕQ​\(xi\)⊤​S/\[ϕQ​\(xi\)⊤​z\]a\_\{i\}=\\phi\_\{Q\}\(x\_\{i\}\)^\{\\top\}S/\[\\phi\_\{Q\}\(x\_\{i\}\)^\{\\top\}z\]\. Over the Boolean domain, write\[m\]=\{1,…,m\}\[m\]=\\\{1,\\ldots,m\\\}and letxS∈\{0,1\}mx\_\{S\}\\in\\\{0,1\\\}^\{m\}denote the indicator vector ofS⊆\[m\]S\\subseteq\[m\]\. Then the kernel matrixAS,T=α⁡\(xS,xT\)A\_\{S,T\}=\\alpha\(x\_\{S\},x\_\{T\}\)satisfiesA=ΦQ​ΦK⊤A=\\Phi\_\{Q\}\\Phi\_\{K\}^\{\\top\}and hencerank⁡\(A\)≤r\\operatorname\{rank\}\(A\)\\leq r\.

## 3A three\-token exponential separation

### 3\.1Dense and exact\-feature upper bounds

###### Theorem 1\(Dense softmin\)\.

Use scoressi​j=−τ⁡⟨xi,xj⟩s\_\{ij\}=\-\\tau\\langle x\_\{i\},x\_\{j\}\\rangle, valuesv⁡\(xj\)=xjv\(x\_\{j\}\)=x\_\{j\}, and readoutt^i=⟨xi,yi⟩\\widehat\{t\}\_\{i\}=\\langle x\_\{i\},y\_\{i\}\\rangle\. For0<ε≤1/20<\\varepsilon\\leq 1/2, ifτ≥log⁡\(n/ε\)\\tau\\geq\\log\(n/\\varepsilon\), then0≤t^i−ti<ε0\\leq\\widehat\{t\}\_\{i\}\-t\_\{i\}<\\varepsilonfor every sequence of length at mostnn\. At length three andε=1/2\\varepsilon=1/2, the sufficient temperature is the constantlog⁡6\\log 6\.

###### Proof\.

Fix queryii, letMiM\_\{i\}be its minimizers, and putdj=⟨xi,xj⟩−ti∈ℤ≥0d\_\{j\}=\\langle x\_\{i\},x\_\{j\}\\rangle\-t\_\{i\}\\in\\mathbb\{Z\}\_\{\\geq 0\}\. The readout averages the overlapsti\+djt\_\{i\}\+d\_\{j\}\. Cancelling the common factore−τ​tie^\{\-\\tau t\_\{i\}\}gives

t^i−ti=∑jdj​e−τ​dj∑je−τ​dj=∑j∉Midj​e−τ​dj\|Mi\|\+∑j∉Mie−τ​dj\.\\widehat\{t\}\_\{i\}\-t\_\{i\}=\\frac\{\\sum\_\{j\}d\_\{j\}e^\{\-\\tau d\_\{j\}\}\}\{\\sum\_\{j\}e^\{\-\\tau d\_\{j\}\}\}=\\frac\{\\sum\_\{j\\notin M\_\{i\}\}d\_\{j\}e^\{\-\\tau d\_\{j\}\}\}\{\|M\_\{i\}\|\+\\sum\_\{j\\notin M\_\{i\}\}e^\{\-\\tau d\_\{j\}\}\}\.This is nonnegative\. Sinceτ≥log⁡\(n/ε\)≥log⁡2\\tau\\geq\\log\(n/\\varepsilon\)\\geq\\log 2andd≤2d−1d\\leq 2^\{d\-1\}ford≥1d\\geq 1, each numerator term is at moste−τe^\{\-\\tau\}\. Thus the error is at most\(n−1\)​e−τ<ε\(n\-1\)e^\{\-\\tau\}<\\varepsilon\(and is zero forn=1n=1\)\. The calculation includes ties and repetitions\. ∎

###### Theorem 2\(Exact positive features\)\.

For everyτ\>0\\tau\>0, the Boolean kernelKτ​\(x,z\)=e−τ​⟨x,z⟩K\_\{\\tau\}\(x,z\)=e^\{\-\\tau\\langle x,z\\rangle\}has an exact nonnegative feature factorization of dimension2m2^\{m\}, and every exact real bilinear factorization of this kernel has dimension at least2m2^\{m\}\. For0<ε≤1/20<\\varepsilon\\leq 1/2, choosingτ≥log⁡\(n/ε\)\\tau\\geq\\log\(n/\\varepsilon\)and the values and readout of Theorem[1](https://arxiv.org/html/2608.11427#Thmtheorem1)therefore solves Min\-IP at all lengths up tonnwith error<ε<\\varepsilonusingr=2mr=2^\{m\}\. In particular,r⋆​\(m,n\)≤2mr^\{\\star\}\(m,n\)\\leq 2^\{m\}\.

###### Proof\.

Index coordinates byu∈\{0,1\}mu\\in\\\{0,1\\\}^\{m\}, takeϕQ​\(x\)=ex\\phi\_\{Q\}\(x\)=e\_\{x\}, and setϕK​\(z\)u=Kτ​\(u,z\)\>0\\phi\_\{K\}\(z\)\_\{u\}=K\_\{\\tau\}\(u,z\)\>0\. Their inner product isKτ​\(x,z\)K\_\{\\tau\}\(x,z\), so every normalizer is positive\. Withv⁡\(z\)=zv\(z\)=z, this reproduces Theorem[1](https://arxiv.org/html/2608.11427#Thmtheorem1)\. The full cube kernel matrix is\(111e−τ\)⊗m\\bigl\(\\begin\{smallmatrix\}1&1\\\\ 1&e^\{\-\\tau\}\\end\{smallmatrix\}\\bigr\)^\{\\otimes m\}, of rank2m2^\{m\}because the one\-bit matrix has rank two\. Any bilinear factorization throughℝr\\mathbb\{R\}^\{r\}has matrix rank at mostrr\. ∎

### 3\.2Fixed\-length domination and amplification

Fix queryxxand definegx​\(z\)=β⁡\(x\)\+w​\(x\)⊤​v​\(z\)g\_\{x\}\(z\)=\\beta\(x\)\+w\(x\)^\{\\top\}v\(z\)\. Normalization reduces arbitrary values and affine readout to

t^x​\(X\)=∑jα⁡\(x,xj\)​gx​\(xj\)∑jα⁡\(x,xj\)\.\\widehat\{t\}\_\{x\}\(X\)=\\frac\{\\sum\_\{j\}\\alpha\(x,x\_\{j\}\)g\_\{x\}\(x\_\{j\}\)\}\{\\sum\_\{j\}\\alpha\(x,x\_\{j\}\)\}\.\(5\)
###### Lemma 3\(Fixed\-length gap domination\)\.

Assume correctness with error strictly below0<ε≤1/20<\\varepsilon\\leq 1/2on every sequence of one fixed length exactlyn≥3n\\geq 3\. If

t=⟨x,y⟩<u=⟨x,z⟩≤⟨x,x⟩,d=u−t,t=\\langle x,y\\rangle<u=\\langle x,z\\rangle\\leq\\langle x,x\\rangle,\\qquad d=u\-t,andd≥2​ε​\(n−1\)/\(n−2\)d\\geq 2\\varepsilon\(n\-1\)/\(n\-2\), then

α⁡\(x,y\)\>\(n−2\)​\(d−2​ε\)2​ε​α​\(x,z\)\.\\alpha\(x,y\)\>\\frac\{\(n\-2\)\(d\-2\\varepsilon\)\}\{2\\varepsilon\}\\alpha\(x,z\)\.\(GD\)Forε=1/2\\varepsilon=1/2, every integer gapd≥2d\\geq 2gives the factor\(n−2\)​\(d−1\)\(n\-2\)\(d\-1\)\.

###### Proof\.

PutL=n−1L=n\-1,K=n−2K=n\-2, anda=α⁡\(x,x\)a=\\alpha\(x,x\),b=α⁡\(x,y\)b=\\alpha\(x,y\),c=α⁡\(x,z\)c=\\alpha\(x,z\)\. After subtractingttfrom the scalarized values, writep=gx​\(x\)−tp=g\_\{x\}\(x\)\-t,q=gx​\(y\)−tq=g\_\{x\}\(y\)\-t, ands=gx​\(z\)−ts=g\_\{x\}\(z\)\-t\. On the three exact\-length inputsY=\(x,yL\)Y=\(x,y^\{L\}\),Z=\(x,zL\)Z=\(x,z^\{L\}\), andM=\(x,y,zK\)M=\(x,y,z^\{K\}\), the shifted targets are0,d,00,d,0\. Positive denominators turn strict correctness into

NY=a​p\+L​b​q,DY=a\+L​b,NY\>−ε​DY,NZ=a​p\+L​c​s,DZ=a\+L​c,NZ\>\(d−ε\)​DZ,NM=a​p\+b​q\+K​c​s,DM=a\+b\+K​c,NM<ε​DM\.\\begin\{array\}\[\]\{lll\}N\_\{Y\}=ap\+Lbq,&D\_\{Y\}=a\+Lb,&N\_\{Y\}\>\-\\varepsilon D\_\{Y\},\\\\ N\_\{Z\}=ap\+Lcs,&D\_\{Z\}=a\+Lc,&N\_\{Z\}\>\(d\-\\varepsilon\)D\_\{Z\},\\\\ N\_\{M\}=ap\+bq\+Kcs,&D\_\{M\}=a\+b\+Kc,&N\_\{M\}<\\varepsilon D\_\{M\}\.\\end\{array\}The identityNM−L−1​NY−\(K/L\)​NZ=0N\_\{M\}\-L^\{\-1\}N\_\{Y\}\-\(K/L\)N\_\{Z\}=0cancelsp,q,sp,q,sseparately\. Combining the last column with this identity gives0<ε​DM\+\(ε/L\)​DY−\(K/L\)​\(d−ε\)​DZ0<\\varepsilon D\_\{M\}\+\(\\varepsilon/L\)D\_\{Y\}\-\(K/L\)\(d\-\\varepsilon\)D\_\{Z\}\. Expanding the three denominators gives

0<\(2​ε−K​dL\)​a\+2​ε​b−K⁡\(d−2​ε\)​c\.0<\\left\(2\\varepsilon\-\\frac\{Kd\}\{L\}\\right\)a\+2\\varepsilon b\-K\(d\-2\\varepsilon\)c\.Sincea≥0a\\geq 0and the gap condition makes its coefficient nonpositive, \(GD\) follows\. All inequalities remain strict and use only lengthnn\. ∎

###### Lemma 4\(Approximate identity rank\)\.

IfC∈ℝt×tC\\in\\mathbb\{R\}^\{t\\times t\}hasCi​i=1C\_\{ii\}=1and\|Ci​j\|≤1/λ\|C\_\{ij\}\|\\leq 1/\\lambdafori≠ji\\neq j, then

rank⁡\(C\)≥t1\+\(t−1\)/λ2\.\\operatorname\{rank\}\(C\)\\geq\\frac\{t\}\{1\+\(t\-1\)/\\lambda^\{2\}\}\.

###### Proof\.

Heretr⁡C=t\\operatorname\{tr\}C=tand‖C‖F2≤t\+t⁡\(t−1\)/λ2\\\|C\\\|\_\{F\}^\{2\}\\leq t\+t\(t\-1\)/\\lambda^\{2\}\. Symmetry is unnecessary: nuclear–Frobenius duality givest=\|⟨C,I⟩\|≤‖C‖∗≤rank⁡\(C\)​‖C‖Ft=\|\\langle C,I\\rangle\|\\leq\\\|C\\\|\_\{\*\}\\leq\\sqrt\{\\operatorname\{rank\}\(C\)\}\\\|C\\\|\_\{F\}\. Squaring proves the claim\. ∎

###### Theorem 5\(Amplified fixed\-length rank bound\)\.

Fix an integer1≤h≤m1\\leq h\\leq m\. Let∅≠𝒢⊆\(\[m\]h\)\\varnothing\\neq\\mathcal\{G\}\\subseteq\\binom\{\[m\]\}\{h\}have directed distance at leastΔ\\Delta, meaning\|S∖U\|≥Δ\|S\\setminus U\|\\geq\\Deltafor every distinctS,U∈𝒢S,U\\in\\mathcal\{G\}\. Thus everyxSx\_\{S\}has Hamming weighthh\. Under the hypotheses of Lemma[3](https://arxiv.org/html/2608.11427#Thmtheorem3), choose an integerg≤Δg\\leq\\Deltasuch thatg\>2​ε​\(n−1\)/\(n−2\)g\>2\\varepsilon\(n\-1\)/\(n\-2\), and set

μg=\(n−2\)​\(g−2​ε\)2​ε\>1,Λ=μg⌊Δ/g⌋\.\\mu\_\{g\}=\\frac\{\(n\-2\)\(g\-2\\varepsilon\)\}\{2\\varepsilon\}\>1,\\qquad\\Lambda=\\mu\_\{g\}^\{\\lfloor\\Delta/g\\rfloor\}\.Then

r≥\|𝒢\|1\+\(\|𝒢\|−1\)/Λ2≥12​min⁡\{\|𝒢\|,Λ2\}\.r\\geq\\frac\{\|\\mathcal\{G\}\|\}\{1\+\(\|\\mathcal\{G\}\|\-1\)/\\Lambda^\{2\}\}\\geq\\frac\{1\}\{2\}\\min\\\{\|\\mathcal\{G\}\|,\\Lambda^\{2\}\\\}\.\(6\)

###### Proof\.

If\|𝒢\|=1\|\\mathcal\{G\}\|=1, the first bound reduces tor≥1r\\geq 1\. Indeed,r=0r=0makes every kernel weight and hence every denominator zero\. Hence assume\|𝒢\|≥2\|\\mathcal\{G\}\|\\geq 2and setBS,U=α⁡\(xS,xUc\)B\_\{S,U\}=\\alpha\(x\_\{S\},x\_\{U^\{c\}\}\)forS,U∈𝒢S,U\\in\\mathcal\{G\}\. We first showBS,S\>Λ​BS,UB\_\{S,S\}\>\\Lambda B\_\{S,U\}wheneverS≠US\\neq U\.

Fix distinctS,U∈𝒢S,U\\in\\mathcal\{G\}\. In rowSSofBB, take the queryx=xSx=x\_\{S\}and the two key tokensy0=xScy\_\{0\}=x\_\{S^\{c\}\}andyk=xUcy\_\{k\}=x\_\{U^\{c\}\}\. Their overlaps withxxare⟨x,y0⟩=0\\langle x,y\_\{0\}\\rangle=0and⟨x,yk⟩=\|S∖U\|=:D≥Δ≥g\\langle x,y\_\{k\}\\rangle=\|S\\setminus U\|=:D\\geq\\Delta\\geq g, whileD≤\|S\|=h=⟨x,x⟩D\\leq\|S\|=h=\\langle x,x\\rangle\. To amplify this comparison, connect the two tokens through intermediate overlap levels\. WriteD=k​g\+r0D=kg\+r\_\{0\}, wherek=⌊D/g⌋k=\\lfloor D/g\\rfloorand0≤r0<g0\\leq r\_\{0\}<g, and setℓ0=0\\ell\_\{0\}=0andℓi=i​g\+r0\\ell\_\{i\}=ig\+r\_\{0\}for1≤i≤k1\\leq i\\leq k\. For1≤i<k1\\leq i<k, chooseyiy\_\{i\}to be the indicator of anyℓi\\ell\_\{i\}coordinates insupp⁡\(x\)\\operatorname\{supp\}\(x\)\. Such a choice exists becauseℓi<D≤‖x‖1\\ell\_\{i\}<D\\leq\\\|x\\\|\_\{1\}, and it satisfies⟨x,yi⟩=ℓi\\langle x,y\_\{i\}\\rangle=\\ell\_\{i\}\. The first overlap gap isg\+r0g\+r\_\{0\}and every later gap isgg\. Thus the remainderr0r\_\{0\}is absorbed into the first step and no gap is smaller thangg\. Lemma[3](https://arxiv.org/html/2608.11427#Thmtheorem3)therefore givesα⁡\(x,yi−1\)\>μg​α​\(x,yi\)\\alpha\(x,y\_\{i\-1\}\)\>\\mu\_\{g\}\\alpha\(x,y\_\{i\}\)at each of thekksteps\. Multiplying these inequalities and usingk=⌊D/g⌋≥⌊Δ/g⌋k=\\lfloor D/g\\rfloor\\geq\\lfloor\\Delta/g\\rfloorgivesBS,S\>μg⌊D/g⌋​BS,U≥Λ​BS,UB\_\{S,S\}\>\\mu\_\{g\}^\{\\lfloor D/g\\rfloor\}B\_\{S,U\}\\geq\\Lambda B\_\{S,U\}\. Because every row has an off\-diagonal entry and the kernel is nonnegative, the strict inequality also makes everyBS,SB\_\{S,S\}positive\. ThusR=diag⁡\(BS,S\)R=\\operatorname\{diag\}\(B\_\{S,S\}\)is invertible\. ForC=R−1​BC=R^\{\-1\}B, we haveCS,S=1C\_\{S,S\}=1and0≤CS,U<1/Λ0\\leq C\_\{S,U\}<1/\\Lambdaoff diagonal\. SinceBBis a submatrix of the possibly asymmetric kernel matrix,rank⁡\(C\)=rank⁡\(B\)≤r\\operatorname\{rank\}\(C\)=\\operatorname\{rank\}\(B\)\\leq r\. Lemma[4](https://arxiv.org/html/2608.11427#Thmtheorem4)proves the first bound in \([6](https://arxiv.org/html/2608.11427#S3.E6)\)\. For the second, putt=\|𝒢\|t=\|\\mathcal\{G\}\|\. Ift≤Λ2t\\leq\\Lambda^\{2\}, the denominator is at most22\. Ift\>Λ2t\>\\Lambda^\{2\}, it is at most2​t/Λ22t/\\Lambda^\{2\}\. These givet/2t/2andΛ2/2\\Lambda^\{2\}/2, respectively\. ∎

### 3\.3The phase transition

###### Theorem 6\(Three\-token phase transition\)\.

For everym≥1m\\geq 1,

r⋆​\(m,1\)=r⋆​\(m,2\)=1\.r^\{\\star\}\(m,1\)=r^\{\\star\}\(m,2\)=1\.For everym≥168m\\geq 168, letM=2​⌊m/2⌋M=2\\lfloor m/2\\rfloor\. Every model correct on all sequences of length exactly three with error strictly below1/21/2satisfies

r≥24​⌊M/40⌋−1≥2m/10−6\.r\\geq 2^\{4\\lfloor M/40\\rfloor\-1\}\\geq 2^\{m/10\-6\}\.\(7\)Together with Theorem[2](https://arxiv.org/html/2608.11427#Thmtheorem2), this givesr⋆​\(m,3\)=2Θ⁡\(m\)r^\{\\star\}\(m,3\)=2^\{\\Theta\(m\)\}\.

###### Proof\.

Dimension zero makes every denominator zero, sor⋆≥1r^\{\\star\}\\geq 1\. For lengths at most two, takeα⁡\(x,z\)=1\\alpha\(x,z\)=1,v⁡\(z\)=zv\(z\)=z, and read out2​⟨xi,ai​\(X\)⟩−‖xi‖12\\langle x\_\{i\},a\_\{i\}\(X\)\\rangle\-\\\|x\_\{i\}\\\|\_\{1\}\. This returns self\-overlap at length one and the sole cross\-overlap at length two, which cannot exceed self\-overlap\.

For the lower bound we first construct the code required by Theorem[5](https://arxiv.org/html/2608.11427#Thmtheorem5)\. Work in the even active dimensionMM, letℒ=\(\[M\]M/2\)\\mathcal\{L\}=\\binom\{\[M\]\}\{M/2\}be the middle layer, and putΔ=⌊M/8⌋\\Delta=\\lfloor M/8\\rfloor\. FixS∈ℒS\\in\\mathcal\{L\}\. A wordU∈ℒU\\in\\mathcal\{L\}with\|S∖U\|=a\|S\\setminus U\|=ais obtained by removingaaelements ofSSand addingaafromScS^\{c\}, so there are exactly\(M/2a\)2\\binom\{M/2\}\{a\}^\{2\}choices\. Equal word sizes give\|S∖U\|=\|U∖S\|\|S\\setminus U\|=\|U\\setminus S\|\. Greedily select a word and delete every word at distance belowΔ\\Delta\. The selected family𝒢\\mathcal\{G\}has the required directed distance, and its sizeT=\|𝒢\|T=\|\\mathcal\{G\}\|satisfies

T≥\(MM/2\)∑a=0Δ−1\(M/2a\)2\.T\\geq\\frac\{\\binom\{M\}\{M/2\}\}\{\\sum\_\{a=0\}^\{\\Delta\-1\}\\binom\{M/2\}\{a\}^\{2\}\}\.Indeed, the numerator counts all words and the denominator bounds how many are deleted at each selection\. The central coefficient is the largest of theM\+1M\+1binomial coefficients whose sum is2M2^\{M\}, so\(MM/2\)≥2M/\(M\+1\)\\binom\{M\}\{M/2\}\\geq 2^\{M\}/\(M\+1\)\. LetH2​\(p\)=−p​log2​p−\(1−p\)​log2⁡\(1−p\)H\_\{2\}\(p\)=\-p\\log\_\{2\}p\-\(1\-p\)\\log\_\{2\}\(1\-p\)\. The standard bound\(qp​q\)≤2q​H2​\(p\)\\binom\{q\}\{pq\}\\leq 2^\{qH\_\{2\}\(p\)\}and monotonicity ofH2H\_\{2\}on\[0,1/2\]\[0,1/2\], applied withq=M/2q=M/2andp=2​a/M<1/4p=2a/M<1/4, give\(M/2a\)2≤2M​H2​\(1/4\)\\binom\{M/2\}\{a\}^\{2\}\\leq 2^\{MH\_\{2\}\(1/4\)\}\. The denominator has at mostM\+1M\+1terms\. Therefore

log2⁡T≥\(1−H2​\(1/4\)\)​M−2​log2⁡\(M\+1\)≥M/10\\log\_\{2\}T\\geq\(1\-H\_\{2\}\(1/4\)\)M\-2\\log\_\{2\}\(M\+1\)\\geq M/10forM≥168M\\geq 168\.

Now apply Theorem[5](https://arxiv.org/html/2608.11427#Thmtheorem5)to𝒢\\mathcal\{G\}withh=M/2h=M/2,n=3n=3,ε=1/2\\varepsilon=1/2, andg=5g=5\. Thenμg=4\\mu\_\{g\}=4andΛ2=24​⌊M/40⌋≤2M/10≤T\\Lambda^\{2\}=2^\{4\\lfloor M/40\\rfloor\}\\leq 2^\{M/10\}\\leq T\. Hence the minimum in \([6](https://arxiv.org/html/2608.11427#S3.E6)\) isΛ2\\Lambda^\{2\}, givingr≥Λ2/2=24​⌊M/40⌋−1r\\geq\\Lambda^\{2\}/2=2^\{4\\lfloor M/40\\rfloor\-1\}, the first bound in \([7](https://arxiv.org/html/2608.11427#S3.E7)\)\. Whenmmis odd, fixing the final coordinate to zero leaves the active dimensionM=m−1M=m\-1and preserves every overlap\. Finally,M≥m−1M\\geq m\-1and⌊M/40⌋≥M/40−1\\lfloor M/40\\rfloor\\geq M/40\-1give4​⌊M/40⌋−1≥m/10−64\\lfloor M/40\\rfloor\-1\\geq m/10\-6\. ∎

###### Corollary 7\(Near\-full rank for growing fixed context\)\.

If an integer\-valued exact context lengthn=n⁡\(m\)n=n\(m\)tends to infinity and the model succeeds on every sequence of exactly that length with error below1/21/2, then

r≥2m−o⁡\(m\)\.r\\geq 2^\{m\-o\(m\)\}\.

###### Proof\.

For all sufficiently largemm, putM=2​⌊m/2⌋M=2\\lfloor m/2\\rfloor,s=log2⁡\(n−2\)s=\\log\_\{2\}\(n\-2\),Δ=2​⌈M/\(2​s\)⌉\\Delta=2\\lceil M/\(2s\)\\rceil, andρ=2​Δ/M\\rho=2\\Delta/M\. Then2≤Δ≤M/42\\leq\\Delta\\leq M/4\. Usingg=2g=2givesμ2=n−2\\mu\_\{2\}=n\-2andlog2⁡Λ2≥M\\log\_\{2\}\\Lambda^\{2\}\\geq M\. The same greedy packing bound gives a code of size

T≥2M−M​H2​\(ρ\)\(M\+1\)​Δ\.T\\geq\\frac\{2^\{M\-MH\_\{2\}\(\\rho\)\}\}\{\(M\+1\)\\Delta\}\.BecauseT≤2M≤Λ2T\\leq 2^\{M\}\\leq\\Lambda^\{2\}, Theorem[5](https://arxiv.org/html/2608.11427#Thmtheorem5)yieldsr≥2M−M​H2​\(ρ\)−log2⁡\(\(M\+1\)​Δ\)−1r\\geq 2^\{M\-MH\_\{2\}\(\\rho\)\-\\log\_\{2\}\(\(M\+1\)\\Delta\)\-1\}\. Asn⁡\(m\)→∞n\(m\)\\to\\infty,ρ≤2/s\+4/M=o⁡\(1\)\\rho\\leq 2/s\+4/M=o\(1\)\. SinceM≥m−1M\\geq m\-1, the exponent ism−o⁡\(m\)m\-o\(m\)\. ∎

###### Theorem 8\(Position\-dependent and causal final\-query extension\)\.

Fix one query position andn−1n\-1visible source positions\. Allow arbitrary position\-dependent tokenwise key and value maps, a position\-dependent query map and affine readout, and nonnegative contributions

Aj​\(x,z\)=⟨ϕQ​\(x\),ϕK,j​\(z\)⟩≥0A\_\{j\}\(x,z\)=\\langle\\phi\_\{Q\}\(x\),\\phi\_\{K,j\}\(z\)\\rangle\\geq 0in a sharedrr\-dimensional feature space\. With positive denominators and no other cross\-token channel, Theorem[5](https://arxiv.org/html/2608.11427#Thmtheorem5), Theorem[6](https://arxiv.org/html/2608.11427#Thmtheorem6), and Corollary[7](https://arxiv.org/html/2608.11427#Thmtheorem7)remain valid\. If source positionjjinstead uses an independent feature space of dimensionrjr\_\{j\}, the same conclusions hold withrrreplaced by the total dimension∑jrj\\sum\_\{j\}r\_\{j\}\. The result applies causally when the database occupies a visible prefix and the queried output is at the final position\.

###### Proof\.

WriteL=n−1L=n\-1,K=L−1K=L\-1, and subtractt=⟨x,y⟩t=\\langle x,y\\ranglefrom every scalarized value\. At source positionjj, putbj=Aj​\(x,y\)b\_\{j\}=A\_\{j\}\(x,y\),cj=Aj​\(x,z\)c\_\{j\}=A\_\{j\}\(x,z\),qj=gx,j​\(y\)−tq\_\{j\}=g\_\{x,j\}\(y\)\-t, andsj=gx,j​\(z\)−ts\_\{j\}=g\_\{x,j\}\(z\)\-t\. Letaadenote the self\-kernel term\. LetYYplaceyyeverywhere,ZZplacezzeverywhere, andMℓM\_\{\\ell\}placeyyonly at positionℓ\\ell\. Direct expansion gives∑ℓ=1LNMℓ=NY\+\(L−1\)​NZ\\sum\_\{\\ell=1\}^\{L\}N\_\{M\_\{\\ell\}\}=N\_\{Y\}\+\(L\-1\)N\_\{Z\}\. Summing the strict mixed\-input upper inequalities and using the lower inequalities forY,ZY,Zyields

0<\(2​ε​L−K​d\)​a\+2​ε​∑jbj−K⁡\(d−2​ε\)​∑jcj\.0<\(2\\varepsilon L\-Kd\)a\+2\\varepsilon\\sum\_\{j\}b\_\{j\}\-K\(d\-2\\varepsilon\)\\sum\_\{j\}c\_\{j\}\.The gap condition makes the self coefficient nonpositive\. Hence the effective kernelAeff​\(x,z\)=∑jAj​\(x,z\)=⟨ϕQ​\(x\),∑jϕK,j​\(z\)⟩A^\{\\mathrm\{eff\}\}\(x,z\)=\\sum\_\{j\}A\_\{j\}\(x,z\)=\\langle\\phi\_\{Q\}\(x\),\\sum\_\{j\}\\phi\_\{K,j\}\(z\)\\rangleobeys the same domination lemma and has rank at mostrr\. The preceding chain and rank proof applies\. Concatenating independent position spaces charges∑jrj\\sum\_\{j\}r\_\{j\}\. A final causal query sees the entire database prefix, whereas no claim is made about unseen future tokens\. ∎

#### Why the scope is necessary\.

Nonnegativity converts one\-sided domination into absolute off\-diagonal control\. Signed kernels can cancel and need not obey this argument\. Multiple heads can specialize and cancel through their output projection\. An unrestricted nonlinear exact\-real decoder can encode a finite token histogram in one real coordinate\. We therefore make only the finite\-precision communication statement below for broader multilayer sketch models, rather than extending the one\-head rank claim beyond its proof\.

## 4Finite\-precision information for heads and depth

Choose integersM,s≥1M,s\\geq 1, total input dimensionm=2\+M\+sm=2\+M\+s, and a constant\-weight code𝒞⊆\(\[M\]h\)\\mathcal\{C\}\\subseteq\\binom\{\[M\]\}\{h\}satisfying1≤h≤M1\\leq h\\leq Mand\|U∖S\|≥s\+1\|U\\setminus S\|\\geq s\+1for distinct codewords\. ForS∈𝒞S\\in\\mathcal\{C\}, define

qS=\(0,1,xSc,𝟏s\),dU,k=\(1,0,xU,uk\),q\_\{S\}=\(0,1,x\_\{S^\{c\}\},\\mathbf\{1\}\_\{s\}\),\\qquad d\_\{U,k\}=\(1,0,x\_\{U\},u\_\{k\}\),whereuk∈\{0,1\}su\_\{k\}\\in\\\{0,1\\\}^\{s\}has Hamming weightk∈\{0,…,s\}k\\in\\\{0,\\ldots,s\\\}\. Fix anyqq\-word subcode𝒬⊆𝒞\\mathcal\{Q\}\\subseteq\\mathcal\{C\}\. Forκ∈\{0,…,s\}𝒬\\kappa\\in\\\{0,\\ldots,s\\\}^\{\\mathcal\{Q\}\}, use the fixed query block\(qS\)S∈𝒬\(q\_\{S\}\)\_\{S\\in\\mathcal\{Q\}\}followed by\(dS,κS\)S∈𝒬\(d\_\{S,\\kappa\_\{S\}\}\)\_\{S\\in\\mathcal\{Q\}\}\.

The overlap identity

⟨qS,dU,k⟩=\|U∖S\|\+k\\langle q\_\{S\},d\_\{U,k\}\\rangle=\|U\\setminus S\|\+kshows that the matching token has overlapkk, while every nonmatching database token has overlap at leasts\+1s\+1\. Query–query overlaps are also at leasts\+1s\+1, including self tokens\. Hence the exact query target ist⁡\(qS\)=κSt\(q\_\{S\}\)=\\kappa\_\{S\}with no tie or padding shortcut\.

For the information results, consider a deterministic sketch model\. Tokeniistarts athi\(0\)=E⁡\(xi,i\)h\_\{i\}^\{\(0\)\}=E\(x\_\{i\},i\)\. At layerℓ\\ell, the model computes the finite\-alphabet global messageσℓ=Fℓ​\(h1\(ℓ−1\),…,hN\(ℓ−1\)\)∈Σℓ\\sigma\_\{\\ell\}=F\_\{\\ell\}\(h\_\{1\}^\{\(\\ell\-1\)\},\\ldots,h\_\{N\}^\{\(\\ell\-1\)\}\)\\in\\Sigma\_\{\\ell\}and then updates each token locally ashi\(ℓ\)=Uℓ​\(hi\(ℓ−1\),σℓ,i\)h\_\{i\}^\{\(\\ell\)\}=U\_\{\\ell\}\(h\_\{i\}^\{\(\\ell\-1\)\},\\sigma\_\{\\ell\},i\)\. The final decoder also reads each token separately\. Hence the complete transcript\(σ1,…,σL\)\(\\sigma\_\{1\},\\ldots,\\sigma\_\{L\}\)contains all information communicated between different tokens\.

###### Theorem 9\(Transcript injectivity\)\.

Consider any deterministic sketch\-based model in which every cross\-token channel passes through finite nonempty sketch alphabetsΣ1,…,ΣL\\Sigma\_\{1\},\\ldots,\\Sigma\_\{L\}, while query tokens and their positions are fixed across assignments\. If2​q≤n2q\\leq nand it solves every valid input with error below1/21/2, then

∑ℓ=1Llog2⁡\|Σℓ\|≥q​log2⁡\(s\+1\)\.\\sum\_\{\\ell=1\}^\{L\}\\log\_\{2\}\|\\Sigma\_\{\\ell\}\|\\geq q\\log\_\{2\}\(s\+1\)\.

###### Proof\.

Letτ⁡\(κ\)=\(σ1​\(Xκ\),…,σL​\(Xκ\)\)\\tau\(\\kappa\)=\(\\sigma\_\{1\}\(X\_\{\\kappa\}\),\\ldots,\\sigma\_\{L\}\(X\_\{\\kappa\}\)\)\. Equal transcripts start from equal query states because query tokens and positions are fixed\. The shared sketch and deterministic local update then preserve equality layer by layer, giving identical final outputs\. Strict error below1/21/2rounds each output to its integer target, so two assignments with the same transcript must be equal\. Thusτ\\tauinjects\(s\+1\)q\(s\+1\)^\{q\}assignments intoΣ1×⋯×ΣL\\Sigma\_\{1\}\\times\\cdots\\times\\Sigma\_\{L\}\. Taking logarithms proves the claim\. ∎

In particular, if anLL\-layer,HH\-head linear\-attention model communicates onlySℓ,h∈ℝr×dvS\_\{\\ell,h\}\\in\\mathbb\{R\}^\{r\\times d\_\{v\}\}andzℓ,h∈ℝrz\_\{\\ell,h\}\\in\\mathbb\{R\}^\{r\}, with at most2p2^\{p\}values per coordinate, then

L​H​r​\(dv\+1\)​p≥q​log2⁡\(s\+1\)\.LHr\(d\_\{v\}\+1\)p\\geq q\\log\_\{2\}\(s\+1\)\.\(8\)Any additional cross\-token channel must be counted\. No claim is made for an unrestricted exact\-real transcript\.

###### Proposition 10\(Size of the multilevel family\)\.

For everym≥32m\\geq 32, sets=⌊m/log2⁡m⌋s=\\lfloor m/\\log\_\{2\}m\\rfloor,M=m−s−2M=m\-s\-2, andh=⌊M/2⌋h=\\lfloor M/2\\rfloor\. There is a constant\-weight code𝒞⊆\(\[M\]h\)\\mathcal\{C\}\\subseteq\\binom\{\[M\]\}\{h\}satisfying\|U∖S\|≥s\+1\|U\\setminus S\|\\geq s\+1for all distinctS,U∈𝒞S,U\\in\\mathcal\{C\}, with

\|𝒞\|≥2M\(M\+1\)​\(s\+1\)​\(e​M/s\)2​s=2m−O⁡\(m​log⁡log⁡m/log⁡m\)\.\|\\mathcal\{C\}\|\\geq\\frac\{2^\{M\}\}\{\(M\+1\)\(s\+1\)\(eM/s\)^\{2s\}\}=2^\{m\-O\(m\\log\\log m/\\log m\)\}\.Thus the hard family may useq=min⁡\{⌊n/2⌋,\|𝒞\|\}q=\\min\\\{\\lfloor n/2\\rfloor,\|\\mathcal\{C\}\|\\\}query–database pairs\. Theorem[9](https://arxiv.org/html/2608.11427#Thmtheorem9)then requiresΩ⁡\(q​log⁡m\)\\Omega\(q\\log m\)transcript bits and, whenever⌊n/2⌋≤\|𝒞\|\\lfloor n/2\\rfloor\\leq\|\\mathcal\{C\}\|,Ω⁡\(n​log⁡m\)\\Omega\(n\\log m\)bits\.

###### Proof\.

FixS∈\(\[M\]h\)S\\in\\binom\{\[M\]\}\{h\}\. A word at directed distanceaais formed by removingaaelements ofSSand addingaafrom its complement, giving\(ha\)​\(M−ha\)\\binom\{h\}\{a\}\\binom\{M\-h\}\{a\}choices\. Greedily selecting a word and deleting all words through distancesstherefore removes at most

∑a=0s\(ha\)​\(M−ha\)≤\(s\+1\)​\(e​M/s\)2​s\.\\sum\_\{a=0\}^\{s\}\\binom\{h\}\{a\}\\binom\{M\-h\}\{a\}\\leq\(s\+1\)\(eM/s\)^\{2s\}\.Since the middle layer has size at least2M/\(M\+1\)2^\{M\}/\(M\+1\), this proves the finite bound\. Form≥32m\\geq 32,s≤m/5s\\leq m/5,M≥4​m/5−2M\\geq 4m/5\-2, andh\>s\+1h\>s\+1, so the packing radius is legal\. Moreover,2​s​log2⁡\(e​M/s\)=O⁡\(m​log⁡log⁡m/log⁡m\)2s\\log\_\{2\}\(eM/s\)=O\(m\\log\\log m/\\log m\), whileM=m−O⁡\(m/log⁡m\)M=m\-O\(m/\\log m\)\. Finallylog2⁡\(s\+1\)=Θ⁡\(log⁡m\)\\log\_\{2\}\(s\+1\)=\\Theta\(\\log m\)\. Each hard instance uses two tokens per codeword, so chooseq=min⁡\{⌊n/2⌋,\|𝒞\|\}q=\\min\\\{\\lfloor n/2\\rfloor,\|\\mathcal\{C\}\|\\\}and apply Theorem[9](https://arxiv.org/html/2608.11427#Thmtheorem9)\. ∎

## 5Experiments

We study the proof’s length\-three family and learned positive\-feature attention on larger held\-out families\. Each setting is finite and not a feature\-rank lower bound\. The worst\-case guarantees come from the theory\.

### 5\.1Finite three\-token family

The construction starts with fifteen 24\-bit vectors, each containing 12 ones and separated from the others by directed distance at least six\. Each ordered pair gives a queryxxand a key chain whose overlaps withxxrise from zero to at least six in jumpst→ut\\to uof at least three\. Each jump emits\(x,y,y\)\(x,y,y\),\(x,z,z\)\(x,z,z\), and\(x,y,z\)\(x,y,z\)with targetst,u,tt,u,t\. Strict correctness forcesα⁡\(x,y\)\>2​α​\(x,z\)\\alpha\(x,y\)\>2\\alpha\(x,z\), so ratios multiply along the chain as plotted in Figure[1](https://arxiv.org/html/2608.11427#S5.F1)\(c\)\. The 424 jumps give1,2721\{,\}272inputs\.

Using free query/key feature and query–token lookup tables, we train six ranks from five initializations on the complete family\. Rank is the only restricted resource, and success means maximum error below1/21/2\. The proof excludesr<8r<8\. Mean maximum error remains above0\.800\.80throughr=15r=15, all fiver=32r=32runs solve the family, and a constructedr=15r=15solution attributes learned failure there to optimization rather than a stronger lower bound\.

Figure 1:Feature\-rank sweep: maximum error, ordered\-pair coverage, andr=32r=32endpoint ratios against the dashed factor\-two\-per\-step envelope\. Shading marks proof\-excluded ranks, the star the constructedr=15r=15model, and bars are 95% Student\-ttintervals\.
### 5\.2OOD feature\-capacity scaling

At scale\(M,q,n\)\(M,q,n\), a shuffled length\-n=2​qn=2qinput containsqqqueries andqqdatabase slots derived fromMM\-bit codewords\. An assignment fills slotiiwith queryii’s matching token, giving Min\-IP target zero, or with safe padding, giving target one without changing the length\. At\(M,q,n\)=\(6,4,8\),\(8,6,12\),\(10,8,16\)\(M,q,n\)=\(6,4,8\),\(8,6,12\),\(10,8,16\), train and joint\-OOD test pools are disjoint in assignments, codewords, and coordinate permutations, and positions are hidden\.

We train five initializations of one\-layer, one\-head positive\-feature models at nine ranks and a dense control\. The typed token dimension isM\+2≤12M\+2\\leq 12, sodv=16d\_\{v\}=16spans the full affine linear value/readout class\. Exact\-sequence accuracy is the fraction of test inputs on which every query has error below1/21/2\. Its90%90\\%transition moves fromr=8r=8to1616to6464across the three scales, while learned dense attention is exact in every seed\.

![Refer to caption](https://arxiv.org/html/2608.11427v1/figure2.png)Figure 2:Joint\-OOD exact\-sequence accuracy with saturated linear values \(dv=16d\_\{v\}=16\): five\-seed means in \(a\) and 95% Student\-ttintervals in \(b\)\. The90%90\\%transition is8→16→648\\to 16\\to 64, and the dashed dense control is exact\.

## 6Related work

All\-query minimum\-inner\-product retrieval has already been used to distinguish full and sparse attention:[16](https://arxiv.org/html/2608.11427#bib.bib4)derive an Orthogonal\-Vectors\-Conjecture\-conditional sparse\-attention depth separation\.[1](https://arxiv.org/html/2608.11427#bib.bib8)give conditional runtime lower bounds for global document\-similarity and Min\-IP variants against all truly subquadratic algorithms\. Our narrower unconditional theorem lower\-bounds the feature dimension governing the standard linear\-attention sketch\.

Several works identify complementary rank and depth bottlenecks\.[5](https://arxiv.org/html/2608.11427#bib.bib5)study query/key score rank for realizing attention matrices\.[2](https://arxiv.org/html/2608.11427#bib.bib7)already prove score\-rank/head separations for nearest\-neighbor approximation on short sequences, including a three\-vector setup\. We therefore do not claim the first short\-context attention\-rank separation\. Their lower bound concerns the rank of the per\-head linear projection used to form attention scores, together with head count, under a distributional approximation criterion\. Ours concerns domain\-level nonnegative kernel feature rank for one head under worst\-case strict error\.[12](https://arxiv.org/html/2608.11427#bib.bib6)and[15](https://arxiv.org/html/2608.11427#bib.bib13)establish complementary depth/resource separations for kernelized or hybrid linear/full attention\. These resources and quantifiers are not interchangeable with Theorem[6](https://arxiv.org/html/2608.11427#Thmtheorem6)\.

The closest representation\-level analogy is the separation between explicit multi\-vector interaction and a compressed single\-vector embedding\.[9](https://arxiv.org/html/2608.11427#bib.bib10)and[8](https://arxiv.org/html/2608.11427#bib.bib11)lower\-bound the dimension required for a single inner product to approximate Chamfer/MAX\-IP similarities, even for data\-dependent embeddings\. Their resource is the dimension of a single\-vector embedding of a growing point cloud, equivalently the approximate rank of the resulting similarity matrix\. We instead fix two candidates, grow only token dimension, and bound the tokenwise nonnegative kernel feature rank inside normalized attention, despite arbitrary values and query\-dependent affine decoding\. Their results therefore do not imply our exponential fixed\-candidate bound\.[14](https://arxiv.org/html/2608.11427#bib.bib12)separately study dimension\-limited top\-kkretrieval\. We do not claim the first general pairwise\-versus\-compressed representation separation\.

Kernelized recurrent implementations introduced the linear\-attention sketch view\([10](https://arxiv.org/html/2608.11427#bib.bib2)\)\. Performer supplies positive random features for softmax approximation\([6](https://arxiv.org/html/2608.11427#bib.bib3)\)\. Approximation of individual kernel entries does not by itself guarantee exact minimum retrieval after normalization\. KATA studies nonnegative feature geometry and associative capacity through symmetric cones\([7](https://arxiv.org/html/2608.11427#bib.bib9)\)\. Our result is complementary because it is a worst\-case task lower bound over arbitrary asymmetric nonnegative feature maps and arbitrary tokenwise values with affine query\-dependent decoding\. Signed and zero\-sum attention is an important escape route rather than a class covered by our theorem\([11](https://arxiv.org/html/2608.11427#bib.bib14)\)\.

Communication and finite\-state bounds for recall and recurrent models are established tools\. Examples include[3](https://arxiv.org/html/2608.11427#bib.bib15),[4](https://arxiv.org/html/2608.11427#bib.bib16), and[17](https://arxiv.org/html/2608.11427#bib.bib17)\. Our finite\-precision contribution is the multilevel Min\-IP embedding and its exact transcript accounting, not the generic injectivity principle\.

## 7Limitations and conclusion

The headline theorem excludes signed kernels, multiple heads or layers, hybrid branches, recurrence, and nonlinear exact\-real decoding\. Its positional extension charges tokenwise position maps but not a separate cross\-token channel\. The finite\-transcript theorem covers broader models only with finite\-alphabet cross\-token channels and says nothing about unrestricted exact\-real states\. For explicit features, rankrrsets ther⁡\(dv\+1\)r\(d\_\{v\}\+1\)\- coordinate sketch size and cost, but not an implementation\-independent runtime lower bound\. Training failure may reflect optimization and finite\-family success may reflect memorization, so the experiments are interpreted separately\.

Within this visible scope, the separation appears at the first context length with two competing candidates\. Rank one is exact through length two, but length three already requires2Ω⁡\(m\)2^\{\\Omega\(m\)\}features\. As fixed context length grows, the exponent approaches the exact2m2^\{m\}endpoint\. Dense softmax instead exposes the three pairwise comparisons usingmm\-dimensional scores and constant temperature\. Multiple heads and layers are genuine escape routes from the one\-head rank theorem\. At finite precision, the multilevel family shows that their total communicated information must still scale with the number of independent answers\.

## References

- Alman and Yu \(2025\)J\. Alman and Z\. YuFundamental limitations on subquadratic alternatives to transformers\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.11427#S1.p1.1),[§6](https://arxiv.org/html/2608.11427#S6.p1.1)\.
- Amselet al\.\(2025\)N\. Amsel, G\. Yehudai, and J\. BrunaQuality over quantity in attention layers\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.11427#S1.p1.1),[§6](https://arxiv.org/html/2608.11427#S6.p2.1)\.
- Aroraet al\.\(2024\)S\. Arora, S\. Eyuboglu, M\. Zhang, A\. Timalsina, I\. J\. Alberti, D\. Zinsley, J\. Zou, A\. Rudra, and C\. RéSimple linear attention language models balance recall and throughput\.InInternational Conference on Machine Learning,Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p5.1)\.
- Bhattamishraet al\.\(2024\)S\. Bhattamishra, A\. Patel, P\. Blunsom, and V\. KanadeSeparations in representational capabilities of transformers and recurrent architectures\.InAdvances in Neural Information Processing Systems,Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p5.1)\.
- Bhojanapalliet al\.\(2020\)S\. Bhojanapalli, C\. Yun, A\. S\. Rawat, S\. J\. Reddi, and S\. KumarLow\-rank bottleneck in multi\-head attention models\.InInternational Conference on Machine Learning,Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p2.1)\.
- Choromanskiet al\.\(2021\)K\. Choromanski, V\. Likhosherstov, D\. Dohan, X\. Song, A\. Gane, T\. Sarlos, P\. Hawkins, J\. Davis, A\. Mohiuddin, L\. Kaiser, D\. Belanger, L\. Colwell, and A\. WellerRethinking attention with performers\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.11427#S1.p2.1),[§6](https://arxiv.org/html/2608.11427#S6.p4.1)\.
- Ghriss and Chakraborty \(2026\)A\. Ghriss and S\. ChakrabortyKernelized linear attention: breaking the capacity wall with symmetric cones\.arXiv preprint arXiv:2607\.17419\.Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p4.1)\.
- Jayaramet al\.\(2026\)R\. Jayaram, H\. Lin, V\. Mirrokni, and D\. P\. WoodruffNear\-optimal dimension lower bounds for single\-vector embeddings of maximum inner product similarity\.arXiv preprint arXiv:2607\.20393\.Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p3.1)\.
- Jayaram \(2026\)R\. JayaramMulti\-vector embeddings are provably more expressive than single vector embeddings\.arXiv preprint arXiv:2606\.23475\.Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p3.1)\.
- Katharopouloset al\.\(2020\)A\. Katharopoulos, A\. Vyas, N\. Pappas, and F\. FleuretTransformers are RNNs: fast autoregressive transformers with linear attention\.InInternational Conference on Machine Learning,pp\. 5156–5165\.Cited by:[§1](https://arxiv.org/html/2608.11427#S1.p2.1),[§6](https://arxiv.org/html/2608.11427#S6.p4.1)\.
- Luet al\.\(2026\)J\. Lu, X\. Han, Y\. Sun, V\. Pati, Y\. Kim, S\. Somani, and S\. YangZeroS: zero\-sum linear attention for efficient transformers\.arXiv preprint arXiv:2602\.05230\.Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p4.1)\.
- Sanfordet al\.\(2024\)C\. Sanford, D\. Hsu, and M\. TelgarskyTransformers, parallel computation, and logarithmic depth\.InInternational Conference on Machine Learning,Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p2.1)\.
- Vaswaniet al\.\(2017\)A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, L\. Kaiser, and I\. PolosukhinAttention is all you need\.InAdvances in Neural Information Processing Systems,Vol\.30\.Cited by:[§1](https://arxiv.org/html/2608.11427#S1.p2.1)\.
- Welleret al\.\(2026\)O\. Weller, M\. Boratko, I\. Naim, and J\. LeeOn the theoretical limitations of embedding\-based retrieval\.InInternational Conference on Learning Representations,Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p3.1)\.
- Yeet al\.\(2026\)X\. Ye, X\. He, C\. Liao, C\. Wu, and P\. LuA provable expressiveness hierarchy in hybrid linear\-full attention\.arXiv preprint arXiv:2602\.01763\.Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p2.1)\.
- Zaheeret al\.\(2020\)M\. Zaheer, G\. Guruganesh, A\. Dubey, J\. Ainslie, C\. Alberti, S\. Ontanon, P\. Pham, A\. Ravula, Q\. Wang, L\. Yang, and A\. AhmedBig bird: transformers for longer sequences\.InAdvances in Neural Information Processing Systems,Vol\.33,pp\. 17283–17297\.Cited by:[§1](https://arxiv.org/html/2608.11427#S1.p1.1),[§6](https://arxiv.org/html/2608.11427#S6.p1.1)\.
- Zhou \(2026\)Y\. ZhouThe impossibility triangle of long\-context modeling\.arXiv preprint arXiv:2605\.05066\.Cited by:[§6](https://arxiv.org/html/2608.11427#S6.p5.1)\.