Attention-based representations for multi-task computation

# Attention-based representations for multi-task computation
Source: [https://arxiv.org/html/2608.04243](https://arxiv.org/html/2608.04243)
Daniel Hsu Columbia Universitydjhsu@cs\.columbia\.edu\. Supported in part by the National Science Foundation under grant DMS\-2502259, the Office of Naval Research under grant N00014\-24\-1\-2700, and a Research Award from the Columbia Center of AI Technology in collaboration with Amazon\.

###### Abstract

Multi\-head attention layers produce vector representations that support multiple downstream tasks\. We establish bounds on the number of heads required in two simple and concrete multi\-task scenarios\. In the first scenario, a vector representation is sought so that linear predictors can compute both the smallest and largest numbers in a given list\. In this case, it is known two attention heads with small embedding dimension and bit precision level suffice\. We prove that a single attention head requires exponentially higher embedding dimension or precision level\. In the second scenario, a vector representation is sought so that a polynomial threshold function can compute the XOR of a given string ofnnbits\. This scenario is analogous to the first one forn=2n=2, since XOR is readily computed by a linear function using a vector representation that encodes both the AND and the OR of the two bits\. We observe thatnn\-bit XOR requires the product of the number of heads and the polynomial degree to be at leastnn, and we construct multi\-head attention layers that match this lower bound\. These results generalize to arbitrary \(symmetric\) Boolean functions, where the bound is given in terms of the threshold degree\.

## 1Introduction

Attention heads—which are the building blocks of transformers\[[28](https://arxiv.org/html/2608.04243#bib.bib28)\]—have been successfully used to learn“task\-independent”representations in a variety of scenarios\[e\.g\.,[14](https://arxiv.org/html/2608.04243#bib.bib14),[20](https://arxiv.org/html/2608.04243#bib.bib20)\]\. In transformers, layers of several attention heads are composed together to form these representations, and the use of*multiple layers*seems to be necessary for several natural computational tasks related to multi\-step reasoning\[[16](https://arxiv.org/html/2608.04243#bib.bib16),[5](https://arxiv.org/html/2608.04243#bib.bib5),[15](https://arxiv.org/html/2608.04243#bib.bib15),[24](https://arxiv.org/html/2608.04243#bib.bib24),[4](https://arxiv.org/html/2608.04243#bib.bib4),[17](https://arxiv.org/html/2608.04243#bib.bib17)\]\.

What is less clearly established in the literature is the necessity of*multiple attention heads in a single layer*\. \(Recent exceptions are discussed in[Section1\.1](https://arxiv.org/html/2608.04243#S1.SS1)\.\) Intuitively speaking, using multiple attention heads allows for multiple computations to be carried out in parallel, and hence produce representations that are useful for multiple tasks\. However, the necessity of using multiple heads to achieve this is not a foregone conclusion\. Indeed, a single attention head—with output elements post\-processed by a neural network—can approximate essentially any function arbitrarily well, as long as the attention head’s embedding dimension or bit precision level is high enough\[e\.g\.,[11](https://arxiv.org/html/2608.04243#bib.bib11)\]\. So the necessity of multiple heads must arise from restrictions on aspects such as dimension, precision level, and the post\-processing\.

This article considers the limits of attention heads for producing vector representations that support multiple tasks in two scenarios\. In the first scenario, the two tasks are computing the minimum and the maximum of a given list of integers\. Separately, each task is easily and succinctly supported by a single attention head, post\-processed by a linear classifier\. We show, in[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1), that a single attention head cannot support both tasks simultaneously in this way unless the value embedding dimension or precision level is large as a function of the input or problem domain size\.

In the second scenario, the overall task is to compute the exclusive\-or \(XOR\) of a given string ofnnbits\. Forn=2n=2bits, the XOR is readily determined as a linear function of two other binary features: the AND of the bits and the OR of the bits\. Separately, each of AND and OR is easily and succinctly handled by a single attention head, post\-processed by a linear classifier; in this sense, the22\-bit XOR scenario is similar to minimum and maximum computation\.Viswanathan \[[29](https://arxiv.org/html/2608.04243#bib.bib29)\]recently observed that no single attention head post\-processed by a linear classifier can compute22\-bit XOR\. We generalize this observation tonn\-bit XOR: any attention layer post\-processed by a polynomial threshold function that computesnn\-bit XOR must satisfy

polynomial degree×number of attention heads≥n\.\\text\{polynomial degree\}\\times\\text\{number of attention heads\}\\geq n\.We also show that the bound is tight: for any positive integersDDandHHsatisfyingD×H≥nD\\times H\\geq n,nn\-bit XOR can be computed by anHH\-head attention layer \(with value embedding dimension at mostO​\(min⁡\{D,log⁡H\}\)O\(\\min\\\{D,\\log H\\\}\)\), post\-processed by a degree\-DDpolynomial threshold function\. Our results fornn\-bit XOR generalize to arbitrary \(symmetric\) Boolean functions with threshold degreeTT; we show thatD×H≥TD\\times H\\geq Tis both necessary and sufficient\.

### 1\.1Related works

Many recent theoretical results about transformers emphasize the importance of multiple attention layers for certain tasks\[e\.g\.,[16](https://arxiv.org/html/2608.04243#bib.bib16),[5](https://arxiv.org/html/2608.04243#bib.bib5),[15](https://arxiv.org/html/2608.04243#bib.bib15),[22](https://arxiv.org/html/2608.04243#bib.bib22),[21](https://arxiv.org/html/2608.04243#bib.bib21),[24](https://arxiv.org/html/2608.04243#bib.bib24),[4](https://arxiv.org/html/2608.04243#bib.bib4),[12](https://arxiv.org/html/2608.04243#bib.bib12),[23](https://arxiv.org/html/2608.04243#bib.bib23),[17](https://arxiv.org/html/2608.04243#bib.bib17),[13](https://arxiv.org/html/2608.04243#bib.bib13)\]\. Our focus is the importance of multiple heads in a single layer\.

A few recent works address the role of multiple attention heads in a single layer\.Yu et al\. \[[30](https://arxiv.org/html/2608.04243#bib.bib30)\]proves separations betweenHHandH\+1H\+1attention heads, for allH≥1H\\geq 1; here we only compare to the specialization of their result toH=1H=1heads\. Their lower bounds are established for a family of tasks of approximately computing functions similar to\(x1,…,xn\)↦min⁡\{x1,…,xn\}\+max⁡\{x1,…,xn\}\(x\_\{1\},\\dotsc,x\_\{n\}\)\\mapsto\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\+\\max\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}over a bounded real domain; these tasks are similar in spirit to the problem we study\. They show that when the query, key, and value embeddings have uniformly bounded norms, and the embedding dimension is much smaller thannn, then by a pigeonhole principle argument, there are at least two inputs \(with different correct outputs\) that are mapped to similar vectors by the attention head, and such vectors are not well\-distinguished by Lipschitz neural networks\. Our result on simultaneousmin\\minandmax\\maxcomputation is not directly comparable, in that \(i\) we consider exact computation ofmin\\minandmax\\maxover a finite domain \(as opposed to approximate computation of real\-valued functions\); \(ii\) we only consider a single attention head \(as opposed to separations for larger numbers of heads\); \(iii\) we only consider post\-processing by linear classifiers \(as opposed to more general neural networks\); and \(iv\) we put precision limits on the value embeddings\. However, in our result, \(i\) we do not require bounds on the classifiers’ weight vectors or on the key and query vectors, \(ii\) the classifiers are not required to be Lipschitz, and \(iii\) the norm bound on the value embeddings can be exponential in the embedding dimension without changing the conclusion of the lower bound\. Our proof focuses on a geometric obstruction that arises from simultaneousmin\\minandmax\\maxcomputation, whereas the proof of[Yu et al\.](https://arxiv.org/html/2608.04243#bib.bib30)uses analytic limitations of neural networks\.

Tesfaye et al\. \[[26](https://arxiv.org/html/2608.04243#bib.bib26)\]andViswanathan \[[29](https://arxiv.org/html/2608.04243#bib.bib29)\]both give separations between one and two attention heads, post\-processed by linear classifiers, using problems that are very different from our simultaneousmin\\minandmax\\maxproblem\.Tesfaye et al\. \[[26](https://arxiv.org/html/2608.04243#bib.bib26)\]prove a one\-versus\-two head separation using a problem that they call Endpoint Selection Problem \(ESP\)\. In ESP, the input is a four\-tuple\(u,v,i,\#\)\(u,v,i,\\\#\), whereuuandvvcome from a finite setVV,iicomes from another set\{1,2\}\\\{1,2\\\}\(disjoint fromVV\), and\#\\\#is a fixed query token \(like\[CLS\], per the convention from BERT\[[6](https://arxiv.org/html/2608.04243#bib.bib6)\]\), with\#∉V∪\{1,2\}\\\#\\notin V\\cup\\\{1,2\\\}\. The correct output isuuifi=1i=1and isvvifi=2i=2\. The challenge is that an attention head is required to provide this output at the position corresponding to the query token\#\\\#\.[Tesfaye et al\.](https://arxiv.org/html/2608.04243#bib.bib26)show that a single attention head post\-processed by a linear classifier cannot solve ESP, but two attention heads can do so with constant embedding dimension andlog⁡\|V\|\\log\\lvert V\\rvertprecision\. As the authors note, the impossibility result does not hold if the output can be taken from the position of theiitoken\. So the difficulty arises from a specific requirement of how an attention head is to be used\.

Viswanathan \[[29](https://arxiv.org/html/2608.04243#bib.bib29)\]studies the two\-bit XOR problem, where the input is\(x1,x2\)∈\{0,1\}2\(x\_\{1\},x\_\{2\}\)\\in\\\{0,1\\\}^\{2\}and the output isx1⊕x2x\_\{1\}\\oplus x\_\{2\}\. It is shown that for any single attention head, the vector produced on inputs\(0,1\)\(0,1\)and\(1,0\)\(1,0\)is on the line segment joining the vectors produced on inputs\(0,0\)\(0,0\)and\(1,1\)\(1,1\)\. Therefore, a linear classifier cannot separate the\(0,1\)\(0,1\)and\(1,0\)\(1,0\)cases from the\(0,0\)\(0,0\)and\(1,1\)\(1,1\)cases\. Notably, this simple geometric argument does not depend on the dimension or the precision level of the embeddings\.[Viswanathan](https://arxiv.org/html/2608.04243#bib.bib29)also shows that using two attention heads readily solves the problem: essentially, one head implements an AND gate and the other head implements an OR gate\. We generalize their observations tonn\-bit XOR, and consider attention layers with multiple heads and post\-processing by general polynomial threshold functions\.

Some prior works establish the inability of self\-attention layers or \(variants of\) transformers to computenn\-bit XOR\.Hahn \[[9](https://arxiv.org/html/2608.04243#bib.bib9)\]andHao et al\. \[[10](https://arxiv.org/html/2608.04243#bib.bib10)\]study a variant of constant\-size transformers that use“unique hard attention”instead of the standard softmax attention, and show that they cannot computenn\-bit XOR\.Kozachinskiy et al\. \[[13](https://arxiv.org/html/2608.04243#bib.bib13)\]shows that every multi\-head attention layer post\-processed by a fixed\-size ReLU network has average sensitivityO~​\(n\)\\tilde\{O\}\\lparen\\sqrt\{n\}\\rparen, and hence cannot compute functions of higher average sensitivity such asnn\-bit XOR\. These results do not apply to attention layers that are post\-processed by functions of size possibly growing withnn, or to attention layers with a number of heads that may grow withnn\.

Adler \[[1](https://arxiv.org/html/2608.04243#bib.bib1)\]studies the role of multiple attention heads from the perspective of memorization capacity\. They find that when query/key vectors across all heads in an attention layer share a fixed \(dimension\) budget, the number of directed relationships between tokens that can be memorized is higher for layers with many heads than for layers with one head \(or few heads, empirically\)\. Using multiple heads reduces the interference from superposition in the embedding space\. Their analysis focuses solely on the expressiveness of attention scores; in particular, they do not study the effect of value vectors\. Our results are complementary: we focus on natural computational tasks supported by attention layers, and our analysis hinges on geometric constraints due to the way value vectors are combined\. Our lower bounds put no restrictions on the query/key vectors whatsoever\.

### 1\.2Proof techniques

Our lower bound for the minimum/maximum scenario is based on two key ingredients\. The first ingredient is the Erdős–Szekeres theorem\[[8](https://arxiv.org/html/2608.04243#bib.bib8),[25](https://arxiv.org/html/2608.04243#bib.bib25)\], which states that every sequence of distinct real numbers of lengthT\+1T\+1must either contain a subsequence of length≥T\+1\\geq\\sqrt\{T\}\+1that is either increasing or decreasing\. In our setting, if the attention weights assigned to some collection of numbers are increasing, then the smallest number in this collection will get relatively low attention weight compared to larger numbers\. Hence, in order for a linear classifier to compute the minimum, the value embeddings associated with the smallest number in this collection should“stand out”among the value embeddings for larger numbers \(e\.g\., by being orthogonal to the other value embeddings\)\. This line of reasoning leads to a system of constraints for a large number of the value embeddings\. Similarly, if attention weights are decreasing, then we get analogous constraints on the value embeddings in order for a linear classifier to compute the maximum\. The Erdős–Szekeres theorem guarantees that, for every choice of attention weights, either the minimum or the maximum task implies constraints on a large number of the value embeddings\.

The second ingredient is a translation of the constraints on the value embeddings into lower bounds on the dimensionality or precision level of the value embeddings\. Although the value embeddings are not required to be orthogonal, they must satisfy an“irrepresentable condition”similar to that ofZhao and Yu \[[31](https://arxiv.org/html/2608.04243#bib.bib31)\]\. We use a volume argument, similar to that ofAwerbuch and Kleinberg \[[2](https://arxiv.org/html/2608.04243#bib.bib2)\]in their analysis of barycentric spanners, to show that any collection of vectors from an integer lattice satisfying the constraints must either have large dimension or have exponentially large norm\. The lattice and norm constraint is easily translated to a constraint on the bit precision level of the value embeddings\.

Our lower bound fornn\-bit XOR is a simple extension of the observations byViswanathan \[[29](https://arxiv.org/html/2608.04243#bib.bib29)\]andKozachinskiy et al\. \[[13](https://arxiv.org/html/2608.04243#bib.bib13)\]\. Specifically, we use a rational function representation of attention heads over the finite token space\{0,1\}\\\{0,1\\\}—a representation that was also used byKozachinskiy et al\. \[[13](https://arxiv.org/html/2608.04243#bib.bib13)\]—and then appeal to a known results about the threshold degree ofnn\-bit XOR\. The argument works to provide a lower bound for any Boolean function in terms of the threshold degree\.

The matching upper bounds fornn\-bit XOR \(and, in fact, any symmetric Boolean function\) are also based on rational function representations achievable by multi\-head attention layers\. Each attention head outputs a vector scaled by the reciprocal of an affine function of the input string’s weight \(i\.e\., the number of11’s in the input\), a standard technique used in previous attention head constructions for parity\[e\.g\.,[5](https://arxiv.org/html/2608.04243#bib.bib5)\]\. An elementary argument based on factorization then gives a construction where the dimension of the value embeddings is equal to the degree of the post\-processing polynomial threshold function\.

To reduce the value embedding dimension, our approach reduces to the following question about sign\-representing the parity function: What is \(a bound on\) the smallestdd, such that for all positive integersDDandHH, there are univariate polynomialsP1,…,PdP\_\{1\},\\dotsc,P\_\{d\}, all of degree at mostHH, and add\-variate polynomialggof degree at mostDD, such thatsign⁡\(g​\(P1​\(t\),…,Pd​\(t\)\)\)=\(−1\)t\\operatorname\{sign\}\(g\(P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\)\)\)=\(\-1\)^\{t\}for allt∈\{0,1,…,n\}t\\in\\\{0,1,\\dotsc,n\\\}? \(Here,HHcorresponds to the number of attention heads, andDDis the degree of the polynomial threshold function\.\) We obtain a bound by constructing small additive bases in the sense ofMossige \[[19](https://arxiv.org/html/2608.04243#bib.bib19)\], Challis and Robinson \[[3](https://arxiv.org/html/2608.04243#bib.bib3)\]and others \(a\.k\.a\. postage stamp bases\), but with a restriction on the basis elements\. Specifically, for a given pair of positive integers\(D,H\)\(D,H\), we require an additiveDD\-basisℬ\\mathcal\{B\}with rangeD​HDH, with the additional restriction that all elements ofℬ\\mathcal\{B\}come from\[H\]\[H\]\. The dimension we achieve this way is equal to the cardinality of such an additive basis \(plus one\)\. To see this, note that, by definition, the additiveDD\-basisℬ\\mathcal\{B\}grants a representation of everyℓ∈\[D​H\]\\ell\\in\[DH\]as the sum of at mostDD\(not necessarily distinct\) elements ofℬ\\mathcal\{B\}\. LettingPi​\(t\)=tβiP\_\{i\}\(t\)=t^\{\\beta\_\{i\}\}for eachβi∈ℬ\\beta\_\{i\}\\in\\mathcal\{B\}, any monomialtℓt^\{\\ell\}forℓ∈\[D​H\]\\ell\\in\[DH\]is equal to the evaluation of some monomialz1c1​z2c2​⋯z\_\{1\}^\{c\_\{1\}\}z\_\{2\}^\{c\_\{2\}\}\\dotsmof total degreec1\+c2\+⋯≤Dc\_\{1\}\+c\_\{2\}\+\\dotsb\\leq Dat\(z1,z2,…\)=\(P1​\(t\),P2​\(t\),…\)\(z\_\{1\},z\_\{2\},\\dotsc\)=\(P\_\{1\}\(t\),P\_\{2\}\(t\),\\dotsc\)\. We show the existence of the required additiveDD\-bases of size≤2​p\+1\\leq 2p\+1wheneverD≳p​H1/pD\\gtrsim pH^\{1/p\}for anyp≥1p\\geq 1\. Combining this with the simpler approach \(where the dimension is at mostDD\), it follows that dimensionO​\(min⁡\{D,log⁡H\}\)O\(\\min\\\{D,\\log H\\\}\)can always be achieved\.

## 2Preliminaries

In this[section](https://arxiv.org/html/2608.04243#S2), we define the basic notions used in our results and proofs\.

#### Attention\.

We consider the standard softmax attention mechanism with only a single query vectorqq, which can be regarded as corresponding to a special\[CLS\]token \(per the convention from BERT\[[6](https://arxiv.org/html/2608.04243#bib.bib6)\]\) presented alongside the actual input\(x1,…,xn\)\(x\_\{1\},\\dotsc,x\_\{n\}\)\. The*attention operator*Att:\(ℝ×ℝd\)n→ℝd\\operatorname\{Att\}\\colon\(\\mathbb\{R\}\\times\\mathbb\{R\}^\{d\}\)^\{n\}\\to\\mathbb\{R\}^\{d\}is defined as follows:

Att\(⟨q,kj⟩,vj\)j=1n:=∑j=1nexp⁡\(⟨q,kj⟩\)​vj∑j=1nexp⁡\(⟨q,kj⟩\)\.\\operatorname\{Att\}\(\\langle q,k\_\{j\}\\rangle,v\_\{j\}\)\_\{j=1\}^\{n\}:=\\frac\{\\sum\_\{j=1\}^\{n\}\\exp\(\\langle q,k\_\{j\}\\rangle\)v\_\{j\}\}\{\\sum\_\{j=1\}^\{n\}\\exp\(\\langle q,k\_\{j\}\\rangle\)\}\.Here,\(kj,vj\)j=1n\(k\_\{j\},v\_\{j\}\)\_\{j=1\}^\{n\}are thennpairs of key and value vectors corresponding to thenninput elements, andddis the dimension of the value vectors\. Because we are only concerned with a single query vector, which appears only through an inner product with key vectors, the dimension of the query and key vectors is irrelevant, although all of our constructions can be realized with one\-dimensional query and key vectors\. \(In fact, eachexp⁡\(⟨q,kj⟩\)\\exp\(\\langle q,k\_\{j\}\\rangle\)can be replaced by any positive numberαj\>0\\alpha\_\{j\}\>0; we use the standard exponential and inner product form for simplicity and conformity\.\)

An*attention head*with value vector dimensionddfor an input token domainΩ\\Omegais a mapping fromΩn→ℝd\\Omega^\{n\}\\to\\mathbb\{R\}^\{d\}parameterized by\(⟨q,kω⟩,vω\)∈ℝ×ℝd\(\\langle q,k\_\{\\omega\}\\rangle,v\_\{\\omega\}\)\\in\\mathbb\{R\}\\times\\mathbb\{R\}^\{d\}for allω∈Ω\\omega\\in\\Omega, and computesAtt\(⟨q,kxj⟩,vxj\)j=1n\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}on every input\(x1,…,xn\)∈Ωn\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\Omega^\{n\}\. An*HH\-head attention layer*is a collection ofHHattention heads \(with the same value vector dimensiondd\) that computes the sum of outputs of allHHattention heads on a given input\. We will use eitherΩ=\[M\]:=\{1,…,M\}\\Omega=\[M\]:=\\\{1,\\dotsc,M\\\}for a positive integerMM, orΩ=\{0,1\}\\Omega=\\\{0,1\\\}\.

#### Linear classifiers\.

An*unambiguousMM\-class linear classifier*f:ℝd→\[M\]∪\{⊥\}f\\colon\\mathbb\{R\}^\{d\}\\to\[M\]\\cup\\\{\\bot\\\}is parameterized byMMweight vectorsθ1,…,θM∈ℝd\\theta\_\{1\},\\dotsc,\\theta\_\{M\}\\in\\mathbb\{R\}^\{d\}; on inputz∈ℝdz\\in\\mathbb\{R\}^\{d\}, it returnsArg​maxi∈\[M\]⁡⟨θi,z⟩\\operatorname\{Arg\\max\}\_\{i\\in\[M\]\}\\langle\\theta\_\{i\},z\\rangle, whereArg​max\\operatorname\{Arg\\max\}returns⊥\\botif there is a tie for thearg⁡max\\operatorname\{\\arg\\max\}, and otherwise it returns the uniquearg⁡max\\operatorname\{\\arg\\max\}\. When inputs come from a finite domain, the⊥\\botvalue is avoided by minimally perturbing the weight vectors\.

#### Polynomials and sign\-representations\.

Throughout this paper, only polynomials with real\-valued coefficients are considered\. The sole exceptions areℝd\\mathbb\{R\}^\{d\}\-valued polynomials in[Section5\.2](https://arxiv.org/html/2608.04243#S5.SS2)\(so the coefficients are realdd\-vectors\), which can be regarded asddseparate real\-valued polynomials\.

Annn\-variate polynomialpp*sign\-represents*a Boolean functionf:\{0,1\}n→\{−1,1\}f\\colon\\\{0,1\\\}^\{n\}\\to\\\{\-1,1\\\}iff​\(x\)=sign⁡\(p​\(x\)\)f\(x\)=\\operatorname\{sign\}\(p\(x\)\)for allx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}\. The*threshold degree*of a Boolean functionf:\{0,1\}n→\{−1,1\}f\\colon\\\{0,1\\\}^\{n\}\\to\\\{\-1,1\\\}is the minimum degreeDDsuch that there exists annn\-variate polynomialppof degreeDDthat sign\-representsff\. \(The composition ofsign\\operatorname\{sign\}and a polynomial function is a*polynomial threshold function*\.\) A Boolean functionf:\{0,1\}n→\{−1,1\}f\\colon\\\{0,1\\\}^\{n\}\\to\\\{\-1,1\\\}is*symmetric*if it only depends on the weight of the input\|x\|:=\|\{iΓi∈\[n\],xi=1\}\|=∑i=1nxi\\lvert x\\rvert:=\\lvert\\\{i\\nonscript\\\>\|\\nonscript\\\>\\mathopen\{\}i\\in\[n\],x\_\{i\}=1\\\}\\rvert=\\sum\_\{i=1\}^\{n\}x\_\{i\}, i\.e\., there existsF:\{0,1,…,n\}→\{−1,1\}F\\colon\\\{0,1,\\dotsc,n\\\}\\to\\\{\-1,1\\\}such thatf​\(x\)=F​\(\|x\|\)f\(x\)=F\(\\lvert x\\rvert\)for allx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}\. For example, thenn\-bit XOR functionx↦\(−1\)\|x\|x\\mapsto\(\-1\)^\{\\lvert x\\rvert\}is symmetric\.

#### Additive bases\.

For positive integersDDandTT, a set of positive integersℬ\\mathcal\{B\}is an*additiveDD\-basis with rangeTT*if every non\-negative integer at mostTTcan be written as a sum of at mostDD\(not necessarily distinct\) elements ofℬ\\mathcal\{B\}\. The empty sum is taken to be equal to zero\.

## 3Main results

### 3\.1Attention\-based minimum and maximum computation

The following[theorem](https://arxiv.org/html/2608.04243#Thmtheorem1)is our main result for the first scenario concerning computation of the minimum and maximum of a list ofnnintegers\.

###### Theorem 1\.

Fix integersM≥2M\\geq 2andn≥2n\\geq 2\. Suppose there are the following:

- •precision levelp∈ℤ\+p\\in\\mathbb\{Z\}\_\{\+\}and norm boundℓ≥2−p\\ell\\geq 2^\{\-p\};
- •query/key values⟨q,k1⟩,…,⟨q,kM⟩∈ℝ\\langle q,k\_\{1\}\\rangle,\\dotsc,\\langle q,k\_\{M\}\\rangle\\in\\mathbb\{R\};
- •value vectorsv1,…,vM∈ℝdv\_\{1\},\\dotsc,v\_\{M\}\\in\\mathbb\{R\}^\{d\}such that for everyi∈\[M\]i\\in\[M\], every component ofviv\_\{i\}is an integer multiple of2−p2^\{\-p\}, and the Euclidean norm ofviv\_\{i\}is at mostℓ\\ell;
- •unambiguousMM\-class linear classifiersfmin,fmax:ℝd→\[M\]∪\{⊥\}f^\{\\min\},f^\{\\max\}\\colon\\mathbb\{R\}^\{d\}\\to\[M\]\\cup\\\{\\bot\\\};

such that for all\(x1,…,xn\)∈\[M\]n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\[M\]^\{n\},

fmin\(Att\(⟨q,kxj⟩,vxj\)j=1n\)\\displaystyle f^\{\\min\}\(\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\)=min⁡\{x1,…,xn\};\\displaystyle=\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\};fmax\(Att\(⟨q,kxj⟩,vxj\)j=1n\)\\displaystyle f^\{\\max\}\(\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\)=max⁡\{x1,…,xn\}\.\\displaystyle=\\max\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\.Then

d​\(1\+p\+log2⁡\(ℓ\)\)≥min⁡\{⌊1\+M−1⌋,⌊n−12⌋\}\.d\\left\\lparen 1\+p\+\\log\_\{2\}\(\\ell\)\\right\\rparen\\geq\\min\\left\\\{\\left\\lfloor 1\+\\sqrt\{M\-1\}\\right\\rfloor,\\left\\lfloor\\frac\{n\-1\}\{2\}\\right\\rfloor\\right\\\}\.

[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)implies that at least one ofdd,pp, andlog2⁡\(ℓ\)\\log\_\{2\}\(\\ell\)must grow roughly as the square\-root ofmin⁡\{M,n\}\\min\\\{\\sqrt\{M\},n\\\}\. IfM≳n2M\\gtrsim n^\{2\}, then we may derive the weaker but simpler conclusion

max⁡\{d,p,log⁡\(ℓ\)\}≳n\.\\max\\\{d,p,\\log\(\\ell\)\\\}\\gtrsim\\sqrt\{n\}\.Observe thatℓ\\ellcan be exponential ind\+pd\+pwithout changing this conclusion aboutddandpp\.

In[AppendixA](https://arxiv.org/html/2608.04243#A1), we describe an attention head and linear classifier for computingmin\\min, withd=⌈8​ln⁡\(M\)⌉d=\\lceil 8\\ln\(M\)\\rceil,ℓ=⌈8​ln⁡\(M\)⌉\\ell=\\sqrt\{\\lceil 8\\ln\(M\)\\rceil\}, andp=0p=0\. A small change makes the construction work formax\\max\. So two such attention heads can support bothmin\\minandmax\\max\. For anyM=poly⁡\(n\)M=\\operatorname\{poly\}\(n\), the“resource requirement”\(dd,pp\) is exponentially smaller than that of one attention head\.

The proof of[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)is given in[Section4](https://arxiv.org/html/2608.04243#S4)\.

### 3\.2Attention\-based XOR computation

For the second scenario, we generalize the results ofViswanathan \[[29](https://arxiv.org/html/2608.04243#bib.bib29)\]from two\-bit XOR tonn\-bit XOR for allnn\.

###### Theorem 2\.

Letf:\{0,1\}n→\{−1,1\}f\\colon\\\{0,1\\\}^\{n\}\\to\\\{\-1,1\\\}have threshold degreeTT\. Suppose there are the following:

- •HHattention heads, where for eachh∈\[H\]h\\in\[H\], thehh\-th head is specified by: - –query/key values⟨q\(h\),k0\(h\)⟩,⟨q\(h\),k1\(h\)⟩∈ℝ\\langle q^\{\(h\)\},k\_\{0\}^\{\(h\)\}\\rangle,\\langle q^\{\(h\)\},k\_\{1\}^\{\(h\)\}\\rangle\\in\\mathbb\{R\}; - –value vectorsv0\(h\),v1\(h\)∈ℝdv\_\{0\}^\{\(h\)\},v\_\{1\}^\{\(h\)\}\\in\\mathbb\{R\}^\{d\};
- •dd\-variate polynomialggof degreeDD;

such that for all\(x1,…,xn\)∈\{0,1\}n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\},

sign\(g\(∑h=1HAtt\(⟨q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n\)\)=f\(x1,…,xn\)\.\\operatorname\{sign\}\\left\\lparen g\\left\\lparen\\sum\_\{h=1\}^\{H\}\\operatorname\{Att\}\(\\langle q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}\\right\\rparen\\right\\rparen=f\(x\_\{1\},\\dotsc,x\_\{n\}\)\.\(1\)Then

Thenn\-bit XOR \(a\.k\.a\. parity\) function has threshold degreenn\[[18](https://arxiv.org/html/2608.04243#bib.bib18)\]\. Hence, we obtain the following[corollary](https://arxiv.org/html/2608.04243#Thmcorollary1)\.

###### Corollary 1\.

Ifffis thenn\-bit XOR function in the setting of[Theorem2](https://arxiv.org/html/2608.04243#Thmtheorem2), thenD×H≥nD\\times H\\geq n\.

Similar to the result ofViswanathan \[[29](https://arxiv.org/html/2608.04243#bib.bib29)\]for the two\-bit XOR,[Theorem2](https://arxiv.org/html/2608.04243#Thmtheorem2)and[Corollary1](https://arxiv.org/html/2608.04243#Thmcorollary1)do not restrict the dimension or bit precision level of the value vectors \(or the key and query vectors\)\.

To show the tightness of our lower bound, we give constructions ofHH\-head attention layers post\-processed by a polynomial threshold function of degreeDD, for all choices ofDDandHHsatisfyingD×H≥TD\\times H\\geq T, in which the value vectors have dimension at mostO​\(min⁡\{D,log⁡H\}\)O\(\\min\\\{D,\\log H\\\}\)\.

###### Theorem 3\.

Letf:\{0,1\}n→\{−1,1\}f\\colon\\\{0,1\\\}^\{n\}\\to\\\{\-1,1\\\}be a symmetric Boolean function with threshold degreeTT\. For any positive integersDDandHHsatisfyingD×H≥TD\\times H\\geq T, there existHHattention heads—specified as in[Theorem2](https://arxiv.org/html/2608.04243#Thmtheorem2)with value vector dimensiond≤min⁡\{D,2​max⁡\{1,⌈log2⁡H⌉\}\+2\}d\\leq\\min\\\{D,2\\max\\\{1,\\lceil\\log\_\{2\}H\\rceil\\\}\+2\\\}—and a polynomialg:ℝd→\{−1,1\}g\\colon\\mathbb\{R\}^\{d\}\\to\\\{\-1,1\\\}of degreeDDsuch that[Equation1](https://arxiv.org/html/2608.04243#S3.E1)holds for all\(x1,…,xn\)∈\{0,1\}n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\}\.

IfDDis at least a constant positive power ofHH\(e\.g\.,D≳H0\.01D\\gtrsim H^\{0\.01\}\), or ifDDitself is a constant, then our proof shows that the value vector dimension can be a constant\. We leave open whether the dimension can be further improved belowO​\(min⁡\{D,log⁡H\}\)O\(\\min\\\{D,\\log H\\\}\)for intermediate values ofDD\.

The proofs of[Theorems2](https://arxiv.org/html/2608.04243#Thmtheorem2)and[3](https://arxiv.org/html/2608.04243#Thmtheorem3)are given in[Section5](https://arxiv.org/html/2608.04243#S5)\.

## 4Proof of[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)

In this[section](https://arxiv.org/html/2608.04243#S4), we prove[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)\.

### 4\.1Histogram representation

Given an input\(x1,…,xn\)∈\[M\]n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\[M\]^\{n\}, consider its histogram vectorh∈ℤ\+Mh\\in\\mathbb\{Z\}\_\{\+\}^\{M\}such that

hi:=∑j=1n𝟙​\{xj=i\}for alli∈\[M\]\.h\_\{i\}:=\\sum\_\{j=1\}^\{n\}\\mathds\{1\}\\\{x\_\{j\}=i\\\}\\qquad\\text\{for all $i\\in\[M\]$\}\.Note thath1\+⋯\+hM=nh\_\{1\}\+\\dotsb\+h\_\{M\}=n\. Let

αi:=exp⁡\(⟨q,ki⟩\)\>0for alli∈\[M\]\\alpha\_\{i\}:=\\exp\(\\langle q,k\_\{i\}\\rangle\)\>0\\qquad\\text\{for all $i\\in\[M\]$\}be the \(unnormalized\) attention weights\. Then we have

Z:=∑i=1Mhiαi\>0andAtt\(⟨q,kxj⟩,vxj\)j=1n=1Z∑i=1Mhiαivi\.Z:=\\sum\_\{i=1\}^\{M\}h\_\{i\}\\alpha\_\{i\}\>0\\qquad\\text\{and\}\\qquad\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}=\\frac\{1\}\{Z\}\\sum\_\{i=1\}^\{M\}h\_\{i\}\\alpha\_\{i\}v\_\{i\}\.

### 4\.2Monotonic subsequence of attention weights

The following is the first key ingredient for the proof of[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)\.

###### Lemma 1\.

IfM≥\(N−1\)2\+1M\\geq\(N\-1\)^\{2\}\+1, then there exists\(x1,…,xN\)∈\[M\]N\(x\_\{1\},\\dotsc,x\_\{N\}\)\\in\[M\]^\{N\}withx1<⋯<xNx\_\{1\}<\\dotsb<x\_\{N\}such that\(αxj\)j=1N\(\\alpha\_\{x\_\{j\}\}\)\_\{j=1\}^\{N\}is either non\-decreasing or non\-increasing\.

###### Proof\.

This is a consequence of the Erdős–Szekeres theorem\[[8](https://arxiv.org/html/2608.04243#bib.bib8),[25](https://arxiv.org/html/2608.04243#bib.bib25)\]\. ∎

Intuitively, a non\-decreasing \(non\-increasing\)\(αxj\)j=1N\(\\alpha\_\{x\_\{j\}\}\)\_\{j=1\}^\{N\}presents an obstacle formin\\min\(max\\max\)\. This intuition is developed in[Sections4\.3](https://arxiv.org/html/2608.04243#S4.SS3)and[4\.4](https://arxiv.org/html/2608.04243#S4.SS4)next\.

### 4\.3Constraints implied by a correct minimum classifier

Letθ1,…,θM\\theta\_\{1\},\\dotsc,\\theta\_\{M\}be the weight vectors forfminf^\{\\min\}\. Throughout this[section](https://arxiv.org/html/2608.04243#S4.SS3), we assume that

fmin\(Att\(⟨q,kxj⟩,vxj\)j=1n\)=min\{x1,…,xn\}f^\{\\min\}\(\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\)=\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}for all\(x1,…,xn\)∈\[M\]n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\[M\]^\{n\}\. We show that the correctness of the minimum classifier implies many linear constraints on the value vectors\.

For allx,y,i∈\[M\]x,y,i\\in\[M\], define

Δix,y:=αi​⟨θx−θy,vi⟩\.\\Delta\_\{i\}^\{x,y\}:=\\alpha\_\{i\}\\langle\\theta\_\{x\}\-\\theta\_\{y\},v\_\{i\}\\rangle\.This is the \(potential\) contribution ofiito the classifier’s comparison ofxxandyy\. Indeed, using the histogram representation forAtt\(⟨q,kxj⟩,vxj\)j=1n\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}and linearity, we have

⟨θx−θy,Att\(⟨q,kxj⟩,vxj\)j=1n⟩=⟨θx−θy,1Z∑i=1Mhiαivi⟩=1Z∑i=1MhiΔix,y\.\\langle\\theta\_\{x\}\-\\theta\_\{y\},\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\\rangle=\\left\\langle\\theta\_\{x\}\-\\theta\_\{y\},\\frac\{1\}\{Z\}\\sum\_\{i=1\}^\{M\}h\_\{i\}\\alpha\_\{i\}v\_\{i\}\\right\\rangle=\\frac\{1\}\{Z\}\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}\.SinceZ\>0Z\>0, we have

⟨θx,Att\(⟨q,kxj⟩,vxj\)j=1n⟩\>⟨θy,Att\(⟨q,kxj⟩,vxj\)j=1n⟩⇔∑i=1MhiΔix,y\>0\.\\langle\\theta\_\{x\},\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\\rangle\>\\langle\\theta\_\{y\},\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\\rangle\\iff\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}\>0\.
The next[lemma](https://arxiv.org/html/2608.04243#Thmlemma2)shows that, for the comparison betweenxxandyy\(forx<yx<y\), the presence ofxxin the input has a positive contribution, and presence of larger elementsz≥yz\\geq ycan only have smaller \(in magnitude\) contributions\.

###### Lemma 2\.

Ifx<yx<y, thenΔxx,y\>0\\Delta\_\{x\}^\{x,y\}\>0, and\|Δzx,y\|<1n−1​Δxx,y\\lvert\\Delta\_\{z\}^\{x,y\}\\rvert<\\frac\{1\}\{n\-1\}\\Delta\_\{x\}^\{x,y\}for allz≥yz\\geq y\.

###### Proof sketch\.

Fixx,y∈\[M\]x,y\\in\[M\]withx<yx<y\. Suppose the input is\(x,…,x\)\(x,\\dotsc,x\), so the minimum isxx\. For the output of the linear classifier to bexx, we must have∑i=1Mhi​Δix,y\>0\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}\>0, where\(hi\)i=1M\(h\_\{i\}\)\_\{i=1\}^\{M\}is the histogram vector for this input\. But∑i=1Mhi​Δix,y=n​Δxx,y\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}=n\\Delta\_\{x\}^\{x,y\}\. ThereforeΔxx,y\>0\\Delta\_\{x\}^\{x,y\}\>0, proving the first part of the claim\. The proof of the second part uses similar reasoning as above for some other simple inputs\. For example, by considering the inputs\(y,…,y\)\(y,\\dotsc,y\)and\(x,y,…,y\)\(x,y,\\dotsc,y\), we find thatΔyx,y<0\\Delta\_\{y\}^\{x,y\}<0and−Δyx,y<Δxx,y/\(n−1\)\-\\Delta\_\{y\}^\{x,y\}<\\Delta\_\{x\}^\{x,y\}/\(n\-1\)\. See[AppendixB](https://arxiv.org/html/2608.04243#A2)for full details\. ∎

The next[lemma](https://arxiv.org/html/2608.04243#Thmlemma3)shows that, for a subset of\[M\]\[M\]whose attention weights are non\-decreasing, the inequalities from[Lemma2](https://arxiv.org/html/2608.04243#Thmlemma2)can be translated to a system of linear constraints on the corresponding elements’ value vectors\. The inequalities are similar to the“irrepresentable condition”ofZhao and Yu \[[31](https://arxiv.org/html/2608.04243#bib.bib31)\], with theλi\\lambda\_\{i\}in[Lemma3](https://arxiv.org/html/2608.04243#Thmlemma3)serving as dual certificates for the impossibility of representingvxiv\_\{x\_\{i\}\}as a linear combination ofvxi\+1,…,vxNv\_\{x\_\{i\+1\}\},\\dotsc,v\_\{x\_\{N\}\}with small coefficients\.

###### Lemma 3\.

Suppose there exists\(x1,…,xN\)∈\[M\]N\(x\_\{1\},\\dotsc,x\_\{N\}\)\\in\[M\]^\{N\}withx1<⋯<xNx\_\{1\}<\\dotsb<x\_\{N\}such that\(αxj\)j=1N\(\\alpha\_\{x\_\{j\}\}\)\_\{j=1\}^\{N\}is non\-decreasing\. For eachi∈\{1,…,N−1\}i\\in\\\{1,\\dotsc,N\-1\\\}, there existsλi∈ℝd\\lambda\_\{i\}\\in\\mathbb\{R\}^\{d\}such that⟨λi,vxi⟩=1\\langle\\lambda\_\{i\},v\_\{x\_\{i\}\}\\rangle=1, and\|⟨λi,vxj⟩\|<1n−1\\lvert\\langle\\lambda\_\{i\},v\_\{x\_\{j\}\}\\rangle\\rvert<\\frac\{1\}\{n\-1\}for allj\>ij\>i\.

###### Proof\.

Fixi∈\{1,…,N−1\}i\\in\\\{1,\\dotsc,N\-1\\\}\. By[Lemma2](https://arxiv.org/html/2608.04243#Thmlemma2), and the fact thatαx\>0\\alpha\_\{x\}\>0for allx∈\[M\]x\\in\[M\], we have

⟨θxi−θxi\+1,vxi⟩\>0\\langle\\theta\_\{x\_\{i\}\}\-\\theta\_\{x\_\{i\+1\}\},v\_\{x\_\{i\}\}\\rangle\>0\(2\)and, for allj\>ij\>i,

\|⟨θxi−θxi\+1,vxj⟩\|<αxiαxj⋅1n−1​⟨θxi−θxi\+1,vxi⟩≤1n−1​⟨θxi−θxi\+1,vxi⟩\\lvert\\langle\\theta\_\{x\_\{i\}\}\-\\theta\_\{x\_\{i\+1\}\},v\_\{x\_\{j\}\}\\rangle\\rvert<\\frac\{\\alpha\_\{x\_\{i\}\}\}\{\\alpha\_\{x\_\{j\}\}\}\\cdot\\frac\{1\}\{n\-1\}\\langle\\theta\_\{x\_\{i\}\}\-\\theta\_\{x\_\{i\+1\}\},v\_\{x\_\{i\}\}\\rangle\\leq\\frac\{1\}\{n\-1\}\\langle\\theta\_\{x\_\{i\}\}\-\\theta\_\{x\_\{i\+1\}\},v\_\{x\_\{i\}\}\\rangle\(3\)where the second inequality uses[Equation2](https://arxiv.org/html/2608.04243#S4.E2)and the fact thatαxj≥αxi\\alpha\_\{x\_\{j\}\}\\geq\\alpha\_\{x\_\{i\}\}forj\>ij\>i\. So let

λi:=1⟨θxi−θxi\+1,vxi⟩​\(θxi−θxi\+1\)\.\\lambda\_\{i\}:=\\frac\{1\}\{\\langle\\theta\_\{x\_\{i\}\}\-\\theta\_\{x\_\{i\+1\}\},v\_\{x\_\{i\}\}\\rangle\}\\lparen\\theta\_\{x\_\{i\}\}\-\\theta\_\{x\_\{i\+1\}\}\\rparen\.Then⟨λi,vxi⟩=1\\langle\\lambda\_\{i\},v\_\{x\_\{i\}\}\\rangle=1and\|⟨λi,vxj⟩\|<1/\(n−1\)\\lvert\\langle\\lambda\_\{i\},v\_\{x\_\{j\}\}\\rangle\\rvert<1/\(n\-1\)for allj\>ij\>ifollow from[Equation2](https://arxiv.org/html/2608.04243#S4.E2)and[Equation3](https://arxiv.org/html/2608.04243#S4.E3)\. ∎

### 4\.4Constraints implied by a correct maximum classifier

Letθ~1,…,θ~M\\tilde\{\\theta\}\_\{1\},\\dotsc,\\tilde\{\\theta\}\_\{M\}be the weight vectors forfmaxf^\{\\max\}\. Throughout this[section](https://arxiv.org/html/2608.04243#S4.SS4), we assume that

fmax\(Att\(⟨q,kxj⟩,vxj\)j=1n\)=max\{x1,…,xn\}f^\{\\max\}\(\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\)=\\max\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}for all\(x1,…,xn\)∈\[M\]n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\[M\]^\{n\}\. For allx,y,i∈\[M\]x,y,i\\in\[M\], defineΔ~ix,y:=αi​⟨θ~x−θ~y,vi⟩\\tilde\{\\Delta\}\_\{i\}^\{x,y\}:=\\alpha\_\{i\}\\langle\\tilde\{\\theta\}\_\{x\}\-\\tilde\{\\theta\}\_\{y\},v\_\{i\}\\rangle, so we have

⟨θ~x,Att\(⟨q,kxj⟩,vxj\)j=1n⟩\>⟨θ~y,Att\(⟨q,kxj⟩,vxj\)j=1n⟩⇔∑i=1MhiΔ~ix,y\>0\.\\langle\\tilde\{\\theta\}\_\{x\},\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\\rangle\>\\langle\\tilde\{\\theta\}\_\{y\},\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\\rangle\\iff\\sum\_\{i=1\}^\{M\}h\_\{i\}\\tilde\{\\Delta\}\_\{i\}^\{x,y\}\>0\.
###### Lemma 4\.

Ifx\>yx\>y, thenΔ~xx,y\>0\\tilde\{\\Delta\}\_\{x\}^\{x,y\}\>0, and\|Δ~zx,y\|<1n−1​Δ~xx,y\\lvert\\tilde\{\\Delta\}\_\{z\}^\{x,y\}\\rvert<\\frac\{1\}\{n\-1\}\\tilde\{\\Delta\}\_\{x\}^\{x,y\}for allz≤yz\\leq y\.

###### Lemma 5\.

Suppose there exists\(x1,…,xN\)∈\[M\]N\(x\_\{1\},\\dotsc,x\_\{N\}\)\\in\[M\]^\{N\}withx1<⋯<xNx\_\{1\}<\\dotsb<x\_\{N\}such that\(αxj\)j=1N\(\\alpha\_\{x\_\{j\}\}\)\_\{j=1\}^\{N\}is non\-increasing\. For eachi∈\{2,…,N\}i\\in\\\{2,\\dotsc,N\\\}, there existsμi∈ℝd\\mu\_\{i\}\\in\\mathbb\{R\}^\{d\}such that⟨μi,vxi⟩=1\\langle\\mu\_\{i\},v\_\{x\_\{i\}\}\\rangle=1and\|⟨μi,vxj⟩\|<1n−1\\lvert\\langle\\mu\_\{i\},v\_\{x\_\{j\}\}\\rangle\\rvert<\\frac\{1\}\{n\-1\}for allj<ij<i\.

The proof of[Lemma4](https://arxiv.org/html/2608.04243#Thmlemma4)is completely analogous to that of[Lemma2](https://arxiv.org/html/2608.04243#Thmlemma2)\. The proof of[Lemma5](https://arxiv.org/html/2608.04243#Thmlemma5)uses[Lemma4](https://arxiv.org/html/2608.04243#Thmlemma4)in a way analogous to how the proof of[Lemma3](https://arxiv.org/html/2608.04243#Thmlemma3)uses[Lemma2](https://arxiv.org/html/2608.04243#Thmlemma2)\.

### 4\.5Approximately triangular configurations

The second key ingredient for the proof of[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)is the geometric obstruction captured in[Lemma6](https://arxiv.org/html/2608.04243#Thmlemma6)below\. It is used in conjunction with either[Lemma3](https://arxiv.org/html/2608.04243#Thmlemma3)or[Lemma5](https://arxiv.org/html/2608.04243#Thmlemma5)in the proof of the main theorem; the vectorsu1,…,uNu\_\{1\},\\dotsc,u\_\{N\}will be \(scalings of\) an appropriately chosen list of value vectors in our application\.

###### Lemma 6\.

FixN≥1N\\geq 1andL≥1L\\geq 1\. Suppose non\-zero vectorsu1,…,uN,w2,…,wN∈ℝdu\_\{1\},\\dotsc,u\_\{N\},w\_\{2\},\\dotsc,w\_\{N\}\\in\\mathbb\{R\}^\{d\}satisfy, for someϵ∈\(0,1/R\)\\epsilon\\in\\lparen 0,1/R\\rparen:

⟨wi,ui⟩\\displaystyle\\langle w\_\{i\},u\_\{i\}\\rangle=1for alli\>1,\\displaystyle=1\\quad\\text\{for all $i\>1$\},\|⟨wi,uj⟩\|\\displaystyle\\lvert\\langle w\_\{i\},u\_\{j\}\\rangle\\rvert≤ϵfor allj<i,\\displaystyle\\leq\\epsilon\\quad\\text\{for all $j<i$\},whereR≥1R\\geq 1is the dimension ofspan⁡\(\{u1,…,uN\}\)\\operatorname\{span\}\\lparen\\\{u\_\{1\},\\dotsc,u\_\{N\}\\\}\\rparen\. Furthermore, suppose eachuiu\_\{i\}has integer components and Euclidean norm at mostLL\. Then

N≤R​\(1\+log⁡\(L\)log⁡\(1R​ϵ\)\)\.N\\leq R\\left\\lparen 1\+\\frac\{\\log\(L\)\}\{\\log\\left\\lparen\\frac\{1\}\{R\\epsilon\}\\right\\rparen\}\\right\\rparen\.More precisely, ifrir\_\{i\}is the dimension ofspan⁡\(\{u1,…,ui\}\)\\operatorname\{span\}\\lparen\\\{u\_\{1\},\\dotsc,u\_\{i\}\\\}\\rparen, andNr=\|\{i\>1Γri=ri−1=r\}\|N\_\{r\}=\\lvert\\\{i\>1\\nonscript\\\>\|\\nonscript\\\>\\mathopen\{\}r\_\{i\}=r\_\{i\-1\}=r\\\}\\rvert, then

∑r=1RNr​log⁡\(1r​ϵ\)≤R​log⁡\(L\)\.\\sum\_\{r=1\}^\{R\}N\_\{r\}\\log\\left\\lparen\\frac\{1\}\{r\\epsilon\}\\right\\rparen\\leq R\\log\(L\)\.\(4\)

To get some intuition for[Lemma6](https://arxiv.org/html/2608.04243#Thmlemma6), consider the limitϵ→0\\epsilon\\to 0, so we have a perfectly upper triangular configuration: there is a matrixWWsuch thatW𝖳​\[u1​∣⋯∣​uN\]W^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}\[u\_\{1\}\\mid\\dotsb\\mid u\_\{N\}\]is anN×NN\\times Nupper triangular matrix with ones on the diagonal\. This means that this matrix product is non\-singular, so the rank of each matrix in the product isNN\. Hence,N=RN=Ris required\.

When we allowϵ\>0\\epsilon\>0, the vectorsu1,…,uNu\_\{1\},\\dotsc,u\_\{N\}need not be linearly independent\. However, the approximate triangular configuration implies that ifui∈span⁡\(\{u1,…,ui−1\}\)u\_\{i\}\\in\\operatorname\{span\}\(\\\{u\_\{1\},\\dotsc,u\_\{i\-1\}\\\}\), and we writeuiu\_\{i\}as a linear combination ofrrof these preceding vectors, whererris the dimension of the span, then at least one of the coefficients must have large magnitude\. This implies a particular“volume growth”as we find vectorsuiu\_\{i\}that remain in the span of preceding vectors, similar to the analysis of barycentric spanners due toAwerbuch and Kleinberg \[[2](https://arxiv.org/html/2608.04243#bib.bib2)\]\. The number of such volume growth steps is then limited by assumptions of bounded precision and bounded norm, which we leverage through[Claims1](https://arxiv.org/html/2608.04243#Thmclaim1)and[2](https://arxiv.org/html/2608.04243#Thmclaim2)given below and proved in[AppendixB](https://arxiv.org/html/2608.04243#A2)\.

###### Claim 1\.

If every column of a matrixBBhas Euclidean norm at mostLL, thendet\(B𝖳​B\)≤L2​r\\det\(B^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}B\)\\leq L^\{2r\}, whererris the number of columns ofBB\.

###### Claim 2\.

If every entry of a matrixAAis an integer, andAAhas full column rank, thendet\(A𝖳​A\)≥1\\det\(A^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}A\)\\geq 1\.

We now prove[Lemma6](https://arxiv.org/html/2608.04243#Thmlemma6)\.

###### Proof of[Lemma6](https://arxiv.org/html/2608.04243#Thmlemma6)\.

We analyze a process that considers the \(non\-zero\) vectorsu1,…,uNu\_\{1\},\\dotsc,u\_\{N\}in order and produces two sequences of matrices\(Ai\)i=1N\(A\_\{i\}\)\_\{i=1\}^\{N\}and\(Bi\)i=1N\(B\_\{i\}\)\_\{i=1\}^\{N\}\. For eachi∈\[N\]i\\in\[N\], letUi:=\{u1,…,ui\}U\_\{i\}:=\\\{u\_\{1\},\\dotsc,u\_\{i\}\\\},Si:=span⁡\(Ui\)S\_\{i\}:=\\operatorname\{span\}\(U\_\{i\}\), andri:=dim\(Si\)r\_\{i\}:=\\dim\(S\_\{i\}\), so1=r1≤⋯≤rN=R1=r\_\{1\}\\leq\\dotsb\\leq r\_\{N\}=R\. The process is shown[Figure1](https://arxiv.org/html/2608.04243#S4.F1)\.

LetA1:=\[u1\]A\_\{1\}:=\[u\_\{1\}\]andB1:=\[u1\]B\_\{1\}:=\[u\_\{1\}\]\.For eachi=2,…,Ni=2,\\dotsc,N:–Ifui∉Si−1u\_\{i\}\\notin S\_\{i\-1\}\(soSi−1≠Si=span⁡\(Si−1∪\{ui\}\)S\_\{i\-1\}\\neq S\_\{i\}=\\operatorname\{span\}\(S\_\{i\-1\}\\cup\\\{u\_\{i\}\\\}\),ri=ri−1\+1r\_\{i\}=r\_\{i\-1\}\+1\), then: \(*rank\-increasing step*\)\*LetAi:=\[Ai−1∣ui\]A\_\{i\}:=\[A\_\{i\-1\}\\mid u\_\{i\}\]andBi:=\[Bi−1∣ui\]B\_\{i\}:=\[B\_\{i\-1\}\\mid u\_\{i\}\]\.–Else \(soui∈Si−1=Siu\_\{i\}\\in S\_\{i\-1\}=S\_\{i\},r:=ri=ri−1r:=r\_\{i\}=r\_\{i\-1\}\): \(*rank\-preserving step*\)\*LetAi:=Ai−1A\_\{i\}:=A\_\{i\-1\}\.\*Letb1,…,brb\_\{1\},\\dotsc,b\_\{r\}denote the columns ofBi−1B\_\{i\-1\}\.\*Let\(t1,…,tr\)∈ℝr\(t\_\{1\},\\dotsc,t\_\{r\}\)\\in\\mathbb\{R\}^\{r\}be coefficients such thatui=t1​b1\+⋯\+tr​bru\_\{i\}=t\_\{1\}b\_\{1\}\+\\dotsb\+t\_\{r\}b\_\{r\}\.\*Pick anyk∈arg⁡maxj∈\[r\]⁡\|tj\|k\\in\\operatorname\{\\arg\\max\}\_\{j\\in\[r\]\}\\lvert t\_\{j\}\\rvert\.\*LetBi:=\[b1​∣⋯∣​bk−1​∣ui∣​bk\+1​∣⋯∣​br\]B\_\{i\}:=\[b\_\{1\}\\mid\\dotsb\\mid b\_\{k\-1\}\\mid u\_\{i\}\\mid b\_\{k\+1\}\\mid\\dotsb\\mid b\_\{r\}\]\.

Figure 1:The process analyzed in the proof of[Lemma6](https://arxiv.org/html/2608.04243#Thmlemma6)\.The definition ofAiA\_\{i\}in for\-loop stepiiensures \(i\) every column inAiA\_\{i\}is a vector fromUiU\_\{i\}, and \(ii\) the columns ofAiA\_\{i\}form an ordered basis forSiS\_\{i\}; the same is true forBiB\_\{i\}\. Because the columns ofAiA\_\{i\}and the columns ofBiB\_\{i\}form bases for the same subspace, there is a unique \(and invertible\)ri×rir\_\{i\}\\times r\_\{i\}change\-of\-basis matrixCiC\_\{i\}such thatBi=Ai​CiB\_\{i\}=A\_\{i\}C\_\{i\}\. The same is true fori=1i=1, withC1:=\[1\]C\_\{1\}:=\[1\]\. The determinant of a product of square matrices is the product of their determinants, so

det\(Bi𝖳​Bi\)=det\(Ai𝖳​Ai\)​det\(Ci\)2\.\\det\(B\_\{i\}^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}B\_\{i\}\)=\\det\(A\_\{i\}^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}A\_\{i\}\)\\det\(C\_\{i\}\)^\{2\}\.\(5\)With thei=Ni=Ncase of[Equation5](https://arxiv.org/html/2608.04243#S4.E5)and the fact thatdet\(C1\)=1\\det\(C\_\{1\}\)=1, we obtain the telescoping identity:

det\(BN𝖳​BN\)=det\(AN𝖳​AN\)​∏i=2N\(det\(Ci\)det\(Ci−1\)\)2\.\\det\(B\_\{N\}^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}B\_\{N\}\)=\\det\(A\_\{N\}^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}A\_\{N\}\)\\prod\_\{i=2\}^\{N\}\\left\\lparen\\frac\{\\det\(C\_\{i\}\)\}\{\\det\(C\_\{i\-1\}\)\}\\right\\rparen^\{2\}\.\(6\)
We next analyze the ratiosdet\(Ci\)/det\(Ci−1\)\\det\(C\_\{i\}\)/\\det\(C\_\{i\-1\}\)\. Suppose stepiiis a rank\-increasing step\. Then

Ai=\[Ai−1∣ui\]andBi=\[Bi−1∣ui\]=\[Ai−1​Ci−1∣ui\]=\[Ai−1∣ui\]⏟Ai​\[Ci−11\]\.A\_\{i\}=\[A\_\{i\-1\}\\mid u\_\{i\}\]\\qquad\\text\{and\}\\qquad B\_\{i\}=\[B\_\{i\-1\}\\mid u\_\{i\}\]=\[A\_\{i\-1\}C\_\{i\-1\}\\mid u\_\{i\}\]=\\underbrace\{\[A\_\{i\-1\}\\mid u\_\{i\}\]\}\_\{A\_\{i\}\}\\begin\{bmatrix\}C\_\{i\-1\}&\\\\ &1\\end\{bmatrix\}\.Therefore

Ci=\[Ci−11\],C\_\{i\}=\\begin\{bmatrix\}C\_\{i\-1\}&\\\\ &1\\end\{bmatrix\},which implies

\(det\(Ci\)det\(Ci−1\)\)2=1\.\\left\\lparen\\frac\{\\det\(C\_\{i\}\)\}\{\\det\(C\_\{i\-1\}\)\}\\right\\rparen^\{2\}=1\.\(7\)
Now suppose instead that stepiiis a rank\-preserving step\. Adopt the notationsrr,b1,…,brb\_\{1\},\\dotsc,b\_\{r\},kk, andt:=\(t1,…,tr\)t:=\(t\_\{1\},\\dotsc,t\_\{r\}\)from[Figure1](https://arxiv.org/html/2608.04243#S4.F1)\. SinceBiB\_\{i\}swaps outbkb\_\{k\}forui=t1​b1\+⋯\+tr​bru\_\{i\}=t\_\{1\}b\_\{1\}\+\\dotsb\+t\_\{r\}b\_\{r\}inBi−1=\[b1​∣⋯∣​br\]B\_\{i\-1\}=\[b\_\{1\}\\mid\\dotsb\\mid b\_\{r\}\], we can writeBi=Bi−1​TB\_\{i\}=B\_\{i\-1\}T, where

T:=\[Ik−1\|t\|Ir−k\]T:=\\left\[\\begin\{array\}\[\]\{ccc\}I\_\{k\-1\}&\|&\\\\ &t&\\\\ &\|&I\_\{r\-k\}\\end\{array\}\\right\]is ther×rr\\times rmatrix obtained by replacing thekk\-th column of ther×rr\\times ridentity matrix bytt\(as a column vector\)\. Since we also haveAi=Ai−1A\_\{i\}=A\_\{i\-1\},

Bi=Bi−1​T=\(Ai−1​Ci−1\)​T=Ai​\(Ci−1​T\),B\_\{i\}=B\_\{i\-1\}T=\(A\_\{i\-1\}C\_\{i\-1\}\)T=A\_\{i\}\(C\_\{i\-1\}T\),which impliesCi=Ci−1​TC\_\{i\}=C\_\{i\-1\}T, and hencedet\(Ci\)=det\(Ci−1\)​det\(T\)\\det\(C\_\{i\}\)=\\det\(C\_\{i\-1\}\)\\det\(T\)\. The Laplace expansion ofdet\(T\)\\det\(T\)along thekk\-th column ofTTimplies thatdet\(T\)=tk\\det\(T\)=t\_\{k\}\. Therefore

\(det\(Ci\)det\(Ci−1\)\)2=tk2\.\\left\\lparen\\frac\{\\det\(C\_\{i\}\)\}\{\\det\(C\_\{i\-1\}\)\}\\right\\rparen^\{2\}=t\_\{k\}^\{2\}\.\(8\)Now we show a lower bound on\|tk\|\\lvert t\_\{k\}\\rvert\. By linearity, the triangle inequality, and the choice ofkk,

\|⟨wi,ui⟩\|\\displaystyle\\lvert\\langle w\_\{i\},u\_\{i\}\\rangle\\rvert=\|t1​⟨wi,b1⟩\+⋯\+tr​⟨wi,br⟩\|\\displaystyle=\\lvert t\_\{1\}\\langle w\_\{i\},b\_\{1\}\\rangle\+\\dotsb\+t\_\{r\}\\langle w\_\{i\},b\_\{r\}\\rangle\\rvert≤\|t1\|⋅\|⟨wi,b1⟩\|\+⋯\+\|tr\|⋅\|⟨wi,br⟩\|\\displaystyle\\leq\\lvert t\_\{1\}\\rvert\\cdot\\lvert\\langle w\_\{i\},b\_\{1\}\\rangle\\rvert\+\\dotsb\+\\lvert t\_\{r\}\\rvert\\cdot\\lvert\\langle w\_\{i\},b\_\{r\}\\rangle\\rvert≤\|tk\|⋅\(\|⟨wi,b1⟩\|\+⋯\+\|⟨wi,br⟩\|\)\.\\displaystyle\\leq\\lvert t\_\{k\}\\rvert\\cdot\\left\\lparen\\lvert\\langle w\_\{i\},b\_\{1\}\\rangle\\rvert\+\\dotsb\+\\lvert\\langle w\_\{i\},b\_\{r\}\\rangle\\rvert\\right\\rparen\.\(9\)Using the assumptions onwiw\_\{i\}andu1,…,uiu\_\{1\},\\dotsc,u\_\{i\}, and the fact that every column ofBi−1B\_\{i\-1\}comes fromUi−1U\_\{i\-1\}, it follows that

⟨wi,ui⟩=1and\|⟨wi,b1⟩\|\+⋯\+\|⟨wi,br⟩\|≤r​ϵ\.\\langle w\_\{i\},u\_\{i\}\\rangle=1\\qquad\\text\{and\}\\qquad\\lvert\\langle w\_\{i\},b\_\{1\}\\rangle\\rvert\+\\dotsb\+\\lvert\\langle w\_\{i\},b\_\{r\}\\rangle\\rvert\\leq r\\epsilon\.\(10\)Therefore, combining[Equations9](https://arxiv.org/html/2608.04243#S4.E9)and[10](https://arxiv.org/html/2608.04243#S4.E10)gives\|tk\|≥1/\(r​ϵ\)\\lvert t\_\{k\}\\rvert\\geq 1/\(r\\epsilon\), and hence by[Equation8](https://arxiv.org/html/2608.04243#S4.E8),

\(det\(Ci\)det\(Ci−1\)\)2≥\(1r​ϵ\)2\.\\left\\lparen\\frac\{\\det\(C\_\{i\}\)\}\{\\det\(C\_\{i\-1\}\)\}\\right\\rparen^\{2\}\\geq\\left\\lparen\\frac\{1\}\{r\\epsilon\}\\right\\rparen^\{2\}\.\(11\)
Now we return to the telescoping identity[Equation6](https://arxiv.org/html/2608.04243#S4.E6)\. For eachr∈\[R\]r\\in\[R\], letNrN\_\{r\}denote the number of rank\-preserving stepsiiwithri=ri−1=rr\_\{i\}=r\_\{i\-1\}=r\. Then by[Equations7](https://arxiv.org/html/2608.04243#S4.E7)and[11](https://arxiv.org/html/2608.04243#S4.E11),

∏i=2N\(det\(Ci\)det\(Ci−1\)\)2≥∏r=1R\(1r​ϵ\)2​Nr\.\\prod\_\{i=2\}^\{N\}\\left\\lparen\\frac\{\\det\(C\_\{i\}\)\}\{\\det\(C\_\{i\-1\}\)\}\\right\\rparen^\{2\}\\geq\\prod\_\{r=1\}^\{R\}\\left\\lparen\\frac\{1\}\{r\\epsilon\}\\right\\rparen^\{2N\_\{r\}\}\.Moreover, by[Claim1](https://arxiv.org/html/2608.04243#Thmclaim1)and[Claim2](https://arxiv.org/html/2608.04243#Thmclaim2),

det\(BN𝖳​BN\)≤L2​Randdet\(AN𝖳​AN\)≥1\.\\det\(B\_\{N\}^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}B\_\{N\}\)\\leq L^\{2R\}\\qquad\\text\{and\}\\qquad\\det\(A\_\{N\}^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}A\_\{N\}\)\\geq 1\.Combining the inequalities in these last two displays with[Equation6](https://arxiv.org/html/2608.04243#S4.E6)gives

L2​R≥det\(BN𝖳​BN\)=det\(AN𝖳​AN\)​∏i=2N\(det\(Ci\)det\(Ci−1\)\)2≥∏r=1R\(1r​ϵ\)2​Nr\.L^\{2R\}\\geq\\det\(B\_\{N\}^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}B\_\{N\}\)=\\det\(A\_\{N\}^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}A\_\{N\}\)\\prod\_\{i=2\}^\{N\}\\left\\lparen\\frac\{\\det\(C\_\{i\}\)\}\{\\det\(C\_\{i\-1\}\)\}\\right\\rparen^\{2\}\\geq\\prod\_\{r=1\}^\{R\}\\left\\lparen\\frac\{1\}\{r\\epsilon\}\\right\\rparen^\{2N\_\{r\}\}\.Sincelog⁡\(1r​ϵ\)≥log⁡\(1R​ϵ\)\>0\\log\\lparen\\tfrac\{1\}\{r\\epsilon\}\\rparen\\geq\\log\\lparen\\tfrac\{1\}\{R\\epsilon\}\\rparen\>0for allr∈\[R\]r\\in\[R\]by the assumptionϵ∈\(0,1/R\)\\epsilon\\in\\lparen 0,1/R\\rparen, taking logarithms and simplifying gives[Equation4](https://arxiv.org/html/2608.04243#S4.E4)\. We conclude that the total number of for\-loop steps,N−1N\-1, satisfies

N−1\\displaystyle N\-1=\(number of rank\-increasing steps\)\+\(number of rank\-preserving steps\)\\displaystyle=\\text\{\(number of rank\-increasing steps\)\}\+\\text\{\(number of rank\-preserving steps\)\}=\(R−1\)\+\(N1\+⋯\+NR\)\\displaystyle=\\left\\lparen R\-1\\right\\rparen\+\\left\\lparen N\_\{1\}\+\\dotsb\+N\_\{R\}\\right\\rparen≤R−1\+1log⁡\(1R​ϵ\)​∑r=1RNr​log⁡\(1r​ϵ\)\\displaystyle\\leq R\-1\+\\frac\{1\}\{\\log\\left\\lparen\\frac\{1\}\{R\\epsilon\}\\right\\rparen\}\\sum\_\{r=1\}^\{R\}N\_\{r\}\\log\\left\\lparen\\frac\{1\}\{r\\epsilon\}\\right\\rparen≤R−1\+R​log⁡\(L\)log⁡\(1R​ϵ\)\(by[Equation4](https://arxiv.org/html/2608.04243#S4.E4)\)\.∎\\displaystyle\\leq R\-1\+\\frac\{R\\log\(L\)\}\{\\log\\left\\lparen\\frac\{1\}\{R\\epsilon\}\\right\\rparen\}\\qquad\\text\{\(by \\lx@cref\{creftypecap~refnum\}\{eq:main\}\)\}\.\\qed

### 4\.6Finishing the proof

We now finish the proof of[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)\.

###### Proof of[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)\.

We may assume thatvi≠0v\_\{i\}\\neq 0for alli∈\[M\]i\\in\[M\]\. This is because if the input hasxj=ix\_\{j\}=ifor allj∈\[n\]j\\in\[n\], thenAtt\(⟨q,kxj⟩,vxj\)j=1n=vi\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}=v\_\{i\}, which cannot be zero iffminf^\{\\min\}andfmaxf^\{\\max\}are to output non\-⊥\\botvalues\.

We apply[Lemma1](https://arxiv.org/html/2608.04243#Thmlemma1)to obtain\(x1,…,xN\)∈\[M\]N\(x\_\{1\},\\dotsc,x\_\{N\}\)\\in\[M\]^\{N\}for

N:=min⁡\{⌊1\+M−1⌋,⌊n−12⌋\}N:=\\min\\left\\\{\\left\\lfloor 1\+\\sqrt\{M\-1\}\\right\\rfloor,\\left\\lfloor\\frac\{n\-1\}\{2\}\\right\\rfloor\\right\\\}withx1<⋯<xNx\_\{1\}<\\dotsb<x\_\{N\}and\(αxj\)j=1N\(\\alpha\_\{x\_\{j\}\}\)\_\{j=1\}^\{N\}either non\-decreasing or non\-increasing\. If\(αxj\)j=1N\(\\alpha\_\{x\_\{j\}\}\)\_\{j=1\}^\{N\}is non\-decreasing, then we apply[Lemma3](https://arxiv.org/html/2608.04243#Thmlemma3), and setui:=2p​vxN−i\+1u\_\{i\}:=2^\{p\}v\_\{x\_\{N\-i\+1\}\}and \(fori≥2i\\geq 2\)wi:=2−p​λN−i\+1w\_\{i\}:=2^\{\-p\}\\lambda\_\{N\-i\+1\}\. If\(αxj\)j=1N\(\\alpha\_\{x\_\{j\}\}\)\_\{j=1\}^\{N\}is non\-increasing, then we apply[Lemma5](https://arxiv.org/html/2608.04243#Thmlemma5), and setui:=2p​vxiu\_\{i\}:=2^\{p\}v\_\{x\_\{i\}\}and \(fori≥2i\\geq 2\)wi:=2−p​μiw\_\{i\}:=2^\{\-p\}\\mu\_\{i\}\. In either case, we obtain non\-zero vectorsu1,…,uN,w2,…,wNu\_\{1\},\\dotsc,u\_\{N\},w\_\{2\},\\dotsc,w\_\{N\}satisfying the preconditions of[Lemma6](https://arxiv.org/html/2608.04243#Thmlemma6)withL:=2p​ℓL:=2^\{p\}\\ellandϵ:=1/\(n−1\)\\epsilon:=1/\(n\-1\)\. The span ofu1,…,uNu\_\{1\},\\dotsc,u\_\{N\}has dimension

R≤min⁡\{d,⌊1\+M−1⌋,⌊n−12⌋\},R\\leq\\min\\left\\\{d,\\left\\lfloor 1\+\\sqrt\{M\-1\}\\right\\rfloor,\\left\\lfloor\\frac\{n\-1\}\{2\}\\right\\rfloor\\right\\\},\(12\)and hence

log⁡1R​ϵ≥log⁡\(2\)\.\\log\\frac\{1\}\{R\\epsilon\}\\geq\\log\(2\)\.\(13\)Combining[Equations12](https://arxiv.org/html/2608.04243#S4.E12)and[13](https://arxiv.org/html/2608.04243#S4.E13)with[Lemma6](https://arxiv.org/html/2608.04243#Thmlemma6), we have

N≤R​\(1\+log⁡\(L\)log⁡\(1R​ϵ\)\)≤d​\(1\+log2⁡\(L\)\)=d​\(1\+p\+log2⁡\(ℓ\)\)\.∎N\\leq R\\left\\lparen 1\+\\frac\{\\log\(L\)\}\{\\log\\left\\lparen\\frac\{1\}\{R\\epsilon\}\\right\\rparen\}\\right\\rparen\\leq d\\left\\lparen 1\+\\log\_\{2\}\(L\)\\right\\rparen=d\\left\\lparen 1\+p\+\\log\_\{2\}\(\\ell\)\\right\\rparen\.\\qed

## 5Proofs of[Theorems2](https://arxiv.org/html/2608.04243#Thmtheorem2)and[3](https://arxiv.org/html/2608.04243#Thmtheorem3)

In this[section](https://arxiv.org/html/2608.04243#S5), we prove[Theorems2](https://arxiv.org/html/2608.04243#Thmtheorem2)and[3](https://arxiv.org/html/2608.04243#Thmtheorem3)\.

### 5\.1Notation

Throughout this[section](https://arxiv.org/html/2608.04243#S5), we use the notations

⟨q,k0⟩,⟨q,k1⟩∈ℝandv0,v1∈ℝd\\langle q,k\_\{0\}\\rangle,\\langle q,k\_\{1\}\\rangle\\in\\mathbb\{R\}\\quad\\text\{and\}\\quad v\_\{0\},v\_\{1\}\\in\\mathbb\{R\}^\{d\}\(14\)to denote the parameters for a single attention head, which on input\(x1,…,xn\)∈\{0,1\}n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\}, computes

Att\(⟨q,kxj⟩,vxj\)j=1n\.\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\.And we use the notations

⟨q\(h\),k0\(h\)⟩,⟨q\(h\),k1\(h\)⟩∈ℝandv0\(h\),v1\(h\)∈ℝd,∀h∈\[H\]\\langle q^\{\(h\)\},k\_\{0\}^\{\(h\)\}\\rangle,\\langle q^\{\(h\)\},k\_\{1\}^\{\(h\)\}\\rangle\\in\\mathbb\{R\}\\quad\\text\{and\}\\quad v\_\{0\}^\{\(h\)\},v\_\{1\}^\{\(h\)\}\\in\\mathbb\{R\}^\{d\},\\qquad\\forall h\\in\[H\]\(15\)to denote the parameters for anHH\-head attention layer, which on input\(x1,…,xn\)∈\{0,1\}n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\}, computes

∑h=1HAtt\(⟨q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n\.\\sum\_\{h=1\}^\{H\}\\operatorname\{Att\}\(\\langle q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}\.

### 5\.2Rational representations of attention layers

We first show[Theorem2](https://arxiv.org/html/2608.04243#Thmtheorem2)\. The proof begins with the standard observation that the output of anHH\-head attention layer on any inputx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}is given by a rational functionP​\(x\)/Q​\(x\)P\(x\)/Q\(x\), wherePPis anℝd\\mathbb\{R\}^\{d\}\-valued polynomial of degree at mostHH, andQQis a polynomial of degree at mostHHthat is positive on\{0,1\}n\\\{0,1\\\}^\{n\}\.

###### Lemma 7\.

Consider anyHHattention heads with parameters[Equation15](https://arxiv.org/html/2608.04243#S5.E15)\(and value vector dimensiondd\)\. There exist anℝd\\mathbb\{R\}^\{d\}\-valuednn\-variate polynomialPPof degree at mostHH, and annn\-variate polynomialQQof degree at mostHHsuch thatQ​\(x1,…,xn\)\>0Q\(x\_\{1\},\\dotsc,x\_\{n\}\)\>0and∑h=1HAtt\(⟨q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n=P\(x1,…,xn\)/Q\(x1,…,xn\)\\sum\_\{h=1\}^\{H\}\\operatorname\{Att\}\(\\langle q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}=P\(x\_\{1\},\\dotsc,x\_\{n\}\)/Q\(x\_\{1\},\\dotsc,x\_\{n\}\)for all\(x1,…,xn\)∈\{0,1\}n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\}\.

###### Proof\.

Consider a single attention head with parameters[Equation14](https://arxiv.org/html/2608.04243#S5.E14)\. For any input\(x1,…,xn\)∈\{0,1\}n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\},

Att\(⟨q,kxj⟩,vxj\)j=1n=A​\(x1,…,xn\)Z​\(x1,…,xn\),\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}=\\frac\{A\(x\_\{1\},\\dotsc,x\_\{n\}\)\}\{Z\(x\_\{1\},\\dotsc,x\_\{n\}\)\},where we defineA:ℝn→ℝdA\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}^\{d\}andZ:ℝn→ℝZ\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}by

A​\(x1,…,xn\)\\displaystyle A\(x\_\{1\},\\dotsc,x\_\{n\}\):=∑i=1n\(1−xi\)​exp⁡\(⟨q,k0⟩\)​v0\+xi​exp⁡\(⟨q,k1⟩\)​v1\\displaystyle:=\\sum\_\{i=1\}^\{n\}\(1\-x\_\{i\}\)\\exp\(\\langle q,k\_\{0\}\\rangle\)v\_\{0\}\+x\_\{i\}\\exp\(\\langle q,k\_\{1\}\\rangle\)v\_\{1\}andZ​\(x1,…,xn\)\\displaystyle Z\(x\_\{1\},\\dotsc,x\_\{n\}\):=∑i=1n\(1−xi\)​exp⁡\(⟨q,k0⟩\)\+xi​exp⁡\(⟨q,k1⟩\)\.\\displaystyle:=\\sum\_\{i=1\}^\{n\}\(1\-x\_\{i\}\)\\exp\(\\langle q,k\_\{0\}\\rangle\)\+x\_\{i\}\\exp\(\\langle q,k\_\{1\}\\rangle\)\.Observe thatAAandZZare affine functions of\(x1,…,xn\)\(x\_\{1\},\\dotsc,x\_\{n\}\), withZZtaking positive values on\{0,1\}n\\\{0,1\\\}^\{n\}\.

Therefore, the sum ofHHattention heads can be written as

∑h=1HAtt\(⟨q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n=∑h=1HA\(h\)​\(x1,…,xn\)Z\(h\)​\(x1,…,xn\)\\sum\_\{h=1\}^\{H\}\\operatorname\{Att\}\(\\langle q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}=\\sum\_\{h=1\}^\{H\}\\frac\{A^\{\(h\)\}\(x\_\{1\},\\dotsc,x\_\{n\}\)\}\{Z^\{\(h\)\}\(x\_\{1\},\\dotsc,x\_\{n\}\)\}whereA\(1\),…,A\(H\):ℝn→ℝdA^\{\(1\)\},\\dotsc,A^\{\(H\)\}\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}^\{d\}andZ\(1\),…,Z\(H\):ℝn→ℝZ^\{\(1\)\},\\dotsc,Z^\{\(H\)\}\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}are all affine functions, with each ofZ\(1\),…,Z\(H\)Z^\{\(1\)\},\\dotsc,Z^\{\(H\)\}taking positive values on\{0,1\}n\\\{0,1\\\}^\{n\}\. DefineZ\(1:H\):=∏h=1HZ\(h\)Z^\{\(1:H\)\}:=\\prod\_\{h=1\}^\{H\}Z^\{\(h\)\}, which takes positive values on\{0,1\}n\\\{0,1\\\}^\{n\}; and for eachh∈\[H\]h\\in\[H\], defineZ\(−h\):=∏h′≠hZ\(h′\)Z^\{\(\-h\)\}:=\\prod\_\{h^\{\\prime\}\\neq h\}Z^\{\(h^\{\\prime\}\)\}\. Then we have

∑h=1HA\(h\)​\(x1,…,xn\)Z\(h\)​\(x1,…,xn\)=∑h=1HA\(h\)​\(x1,…,xn\)​Z\(−h\)​\(x1,…,xn\)Z\(1:H\)​\(x1,…,xn\)\.\\sum\_\{h=1\}^\{H\}\\frac\{A^\{\(h\)\}\(x\_\{1\},\\dotsc,x\_\{n\}\)\}\{Z^\{\(h\)\}\(x\_\{1\},\\dotsc,x\_\{n\}\)\}=\\frac\{\\sum\_\{h=1\}^\{H\}A^\{\(h\)\}\(x\_\{1\},\\dotsc,x\_\{n\}\)Z^\{\(\-h\)\}\(x\_\{1\},\\dotsc,x\_\{n\}\)\}\{Z^\{\(1:H\)\}\(x\_\{1\},\\dotsc,x\_\{n\}\)\}\.\(16\)For eachh∈\[H\]h\\in\[H\],Z\(−h\)Z^\{\(\-h\)\}is the product ofH−1H\-1affine functions and hence is a polynomial of degree at mostH−1H\-1\. Therefore, each of the numerator and denominator in the right\-hand side expression in[Equation16](https://arxiv.org/html/2608.04243#S5.E16)is a polynomial of degree at mostHH\. ∎

We next consider the effect of composing a polynomial function with a rational function whose denominator is positive over a domain\.

###### Lemma 8\.

Supposeggis add\-variate polynomial of degree at mostDD,PPis annn\-variateℝd\\mathbb\{R\}^\{d\}\-valued polynomial of degree at mostHH, andQQis annn\-variate polynomial of degree at mostHHwithQ​\(x\)\>0Q\(x\)\>0for allx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}\. Then there exists annn\-variate polynomialRRof degree at mostD​HDHsuch that, for allx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\},sign⁡\(g​\(P​\(x\)/Q​\(x\)\)\)=sign⁡\(R​\(x\)\)\\operatorname\{sign\}\(g\(P\(x\)/Q\(x\)\)\)=\\operatorname\{sign\}\(R\(x\)\)\.

###### Proof\.

For eachj∈\[d\]j\\in\[d\], writePjP\_\{j\}for thejj\-th component ofPP\. For a multi\-indexK=\(K1,…,Kd\)∈ℕ0d:=\{\(z1,…,zd\)Γzi∈ℤ,zi≥0∀i∈\[d\]\}K=\(K\_\{1\},\\dotsc,K\_\{d\}\)\\in\\mathbb\{N\}\_\{0\}^\{d\}:=\\\{\(z\_\{1\},\\dotsc,z\_\{d\}\)\\nonscript\\\>\|\\nonscript\\\>\\mathopen\{\}z\_\{i\}\\in\\mathbb\{Z\},z\_\{i\}\\geq 0\\,\\forall i\\in\[d\]\\\}, write\|K\|:=∑j=1dKj\\lvert K\\rvert:=\\sum\_\{j=1\}^\{d\}K\_\{j\}\. Sincegghas degree at mostDD, we can write

g​\(z1,…,zd\)=∑K∈ℕ0d:\|K\|≤DcK​∏j=1dzjKjg\(z\_\{1\},\\dotsc,z\_\{d\}\)=\\sum\_\{\\begin\{subarray\}\{c\}K\\in\\mathbb\{N\}\_\{0\}^\{d\}:\\\\ \\lvert K\\rvert\\leq D\\end\{subarray\}\}c\_\{K\}\\prod\_\{j=1\}^\{d\}z\_\{j\}^\{K\_\{j\}\}for some real coefficientscKc\_\{K\}\. Formally defineR​\(x\):=Q​\(x\)D​g​\(P​\(x\)/Q​\(x\)\)R\(x\):=Q\(x\)^\{D\}g\(P\(x\)/Q\(x\)\), which after expanding the expression forggbecomes

R​\(x\)=Q​\(x\)D​∑K∈ℕ0d:\|K\|≤DcK​∏j=1d\(Pj​\(x\)/Q​\(x\)\)Kj=∑K∈ℕ0d:\|K\|≤DcK​Q​\(x\)D−\|K\|​∏j=1dPj​\(x\)Kj\.R\(x\)=Q\(x\)^\{D\}\\sum\_\{\\begin\{subarray\}\{c\}K\\in\\mathbb\{N\}\_\{0\}^\{d\}:\\\\ \\lvert K\\rvert\\leq D\\end\{subarray\}\}c\_\{K\}\\prod\_\{j=1\}^\{d\}\(P\_\{j\}\(x\)/Q\(x\)\)^\{K\_\{j\}\}=\\sum\_\{\\begin\{subarray\}\{c\}K\\in\\mathbb\{N\}\_\{0\}^\{d\}:\\\\ \\lvert K\\rvert\\leq D\\end\{subarray\}\}c\_\{K\}Q\(x\)^\{D\-\\lvert K\\rvert\}\\prod\_\{j=1\}^\{d\}P\_\{j\}\(x\)^\{K\_\{j\}\}\.The term in the final sum corresponding to multi\-indexKKhas degree

deg⁡\(Q​\(x\)D−\|K\|​∏j=1dPj​\(x\)Kj\)≤\(D−\|K\|\)​deg⁡\(Q\)\+∑j=1dKj​deg⁡\(Pj\)≤\(D−\|K\|\)​H\+\|K\|​H=D​H\.\\deg\\left\\lparen Q\(x\)^\{D\-\\lvert K\\rvert\}\\prod\_\{j=1\}^\{d\}P\_\{j\}\(x\)^\{K\_\{j\}\}\\right\\rparen\\leq\(D\-\\lvert K\\rvert\)\\deg\(Q\)\+\\sum\_\{j=1\}^\{d\}K\_\{j\}\\deg\(P\_\{j\}\)\\leq\(D\-\\lvert K\\rvert\)H\+\\lvert K\\rvert H=DH\.ThereforeRRis annn\-variate polynomial withdeg⁡\(R\)≤D​H\\deg\(R\)\\leq DH\. Moreover, sinceQ​\(x\)D\>0Q\(x\)^\{D\}\>0for allx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}, we have

sign⁡\(g​\(P​\(x\)/Q​\(x\)\)\)=sign⁡\(Q​\(x\)D​g​\(P​\(x\)/Q​\(x\)\)\)=sign⁡\(R​\(x\)\)∀x∈\{0,1\}n\.∎\\operatorname\{sign\}\(g\(P\(x\)/Q\(x\)\)\)=\\operatorname\{sign\}\(Q\(x\)^\{D\}g\(P\(x\)/Q\(x\)\)\)=\\operatorname\{sign\}\(R\(x\)\)\\quad\\forall x\\in\\\{0,1\\\}^\{n\}\.\\qed

Combining[Lemmas7](https://arxiv.org/html/2608.04243#Thmlemma7)and[8](https://arxiv.org/html/2608.04243#Thmlemma8)shows that if the composition of a degree\-DDpolynomialggand anHH\-head attention layer sign\-representsffon\{0,1\}n\\\{0,1\\\}^\{n\}, then there is a degree\-D​HDHpolynomialRRthat sign\-representsffas well\. This implies thatD×H≥TD\\times H\\geq T, proving[Theorem2](https://arxiv.org/html/2608.04243#Thmtheorem2)\.

### 5\.3Realizing a polynomial threshold function with attention heads

The remainder of[Section5](https://arxiv.org/html/2608.04243#S5)is dedicated to proving[Theorem3](https://arxiv.org/html/2608.04243#Thmtheorem3)\. In[Lemma9](https://arxiv.org/html/2608.04243#Thmlemma9), we show a basic computation achievable by a single attention head, which will serve as the basis for richer computations achievable by multiple attention heads\.

###### Lemma 9\.

For any vectorsa,b∈ℝda,b\\in\\mathbb\{R\}^\{d\}and scalarc\>−1c\>\-1, there is an attention head with parameters[Equation14](https://arxiv.org/html/2608.04243#S5.E14)and value vector dimensiondd, such that for allx=\(x1,…,xn\)∈\{0,1\}nx=\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\},

Att\(⟨q,kxj⟩,vxj\)j=1n=a\+1n\+c​\|x\|b\.\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}=a\+\\frac\{1\}\{n\+c\\lvert x\\rvert\}b\.

###### Proof\.

Set⟨q,k0⟩:=0\\langle q,k\_\{0\}\\rangle:=0,⟨q,k1⟩:=ln⁡\(1\+c\)\\langle q,k\_\{1\}\\rangle:=\\ln\(1\+c\),v0:=a\+1n​bv\_\{0\}:=a\+\\frac\{1\}\{n\}b,v1:=a\+1n​\(1\+c\)​bv\_\{1\}:=a\+\\frac\{1\}\{n\(1\+c\)\}b\. Then

∑j=1n\(\(1−xj\)​exp⁡\(⟨q,k0⟩\)​\(v0−a\)\+xj​exp⁡\(⟨q,k1⟩\)​\(v1−a\)\)\\displaystyle\\sum\_\{j=1\}^\{n\}\\left\\lparen\(1\-x\_\{j\}\)\\exp\(\\langle q,k\_\{0\}\\rangle\)\(v\_\{0\}\-a\)\+x\_\{j\}\\exp\(\\langle q,k\_\{1\}\\rangle\)\(v\_\{1\}\-a\)\\right\\rparen=∑j=1n\(\(1−xj\)​bn\+xj​\(1\+c\)​bn​\(1\+c\)\)=b\\displaystyle=\\sum\_\{j=1\}^\{n\}\\left\\lparen\\frac\{\(1\-x\_\{j\}\)b\}\{n\}\+\\frac\{x\_\{j\}\(1\+c\)b\}\{n\(1\+c\)\}\\right\\rparen=band∑j=1n\(\(1−xj\)​exp⁡\(⟨q,k0⟩\)\+xj​exp⁡\(⟨q,k1⟩\)\)\\displaystyle\\sum\_\{j=1\}^\{n\}\\left\\lparen\(1\-x\_\{j\}\)\\exp\(\\langle q,k\_\{0\}\\rangle\)\+x\_\{j\}\\exp\(\\langle q,k\_\{1\}\\rangle\)\\right\\rparen=∑j=1n\(\(1−xj\)\+xj​\(1\+c\)\)=n\+c​\|x\|\.\\displaystyle=\\sum\_\{j=1\}^\{n\}\\left\\lparen\(1\-x\_\{j\}\)\+x\_\{j\}\(1\+c\)\\right\\rparen=n\+c\\lvert x\\rvert\.Therefore

Att\(⟨q,kxj⟩,vxj\)j=1n=a\+Att\(⟨q,kxj⟩,vxj−a\)j=1n=a\+1n\+c​\|x\|b\.∎\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}=a\+\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\-a\)\_\{j=1\}^\{n\}=a\+\\frac\{1\}\{n\+c\\lvert x\\rvert\}b\.\\qed

In[Lemma10](https://arxiv.org/html/2608.04243#Thmlemma10), we give a standard construction of a basis for the space of bounded degree polynomials using products of distinct affine functions\. We defer the proof to[AppendixB](https://arxiv.org/html/2608.04243#A2)\.

###### Lemma 10\.

Fix any non\-zero scalarnnand distinct non\-zero scalarsc1,…,cHc\_\{1\},\\dotsc,c\_\{H\}, and define the univariate polynomials

Q0​\(t\):=∏h=1H\(n\+ch​t\),Qh​\(t\):=∏h′≠h\(n\+ch′​t\)∀h∈\[H\]\.Q\_\{0\}\(t\):=\\prod\_\{h=1\}^\{H\}\(n\+c\_\{h\}t\),\\qquad Q\_\{h\}\(t\):=\\prod\_\{h^\{\\prime\}\\neq h\}\(n\+c\_\{h^\{\\prime\}\}t\)\\quad\\forall h\\in\[H\]\.\(17\)ThenQ0,Q1,…,QHQ\_\{0\},Q\_\{1\},\\dotsc,Q\_\{H\}form a basis for the vector space of polynomials of degree at mostHH\.

[Lemma11](https://arxiv.org/html/2608.04243#Thmlemma11)is the core of our construction: we show thatHHattention heads with value vector dimensionddcan realize the anyddpolynomials in\|x\|\\lvert x\\rvertof degree at mostHH, up to a positive scaling that ultimately does not affect the sign after being post\-processed by a homogeneous polynomial\.

###### Lemma 11\.

SupposeP1,…,PdP\_\{1\},\\dotsc,P\_\{d\}are univariate polynomials, each of degree at mostHH\. Then there is anHH\-head attention layer with parameters[Equation15](https://arxiv.org/html/2608.04243#S5.E15)and value vector dimensiondd, such that for allx=\(x1,…,xn\)∈\{0,1\}nx=\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\},

∑h=1HAtt\(⟨\(q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n=\(P1​\(\|x\|\),…,Pd​\(\|x\|\)\)Q0​\(\|x\|\),\\sum\_\{h=1\}^\{H\}\\operatorname\{Att\}\(\\langle\(q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}=\\frac\{\(P\_\{1\}\(\\lvert x\\rvert\),\\dotsc,P\_\{d\}\(\\lvert x\\rvert\)\)\}\{Q\_\{0\}\(\\lvert x\\rvert\)\},whereQ0Q\_\{0\}is a real\-valued function that is positive on the non\-negative reals\. Furthermore, ifggis a homogeneousdd\-variate polynomial, then for allx=\(x1,…,xn\)∈\{0,1\}nx=\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\},

sign\(g\(∑h=1HAtt\(⟨\(q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n\)\)=sign\(g\(P1\(\|x\|\),…,Pd\(\|x\|\)\)\)\.\\operatorname\{sign\}\\left\\lparen g\\left\\lparen\\sum\_\{h=1\}^\{H\}\\operatorname\{Att\}\(\\langle\(q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}\\right\\rparen\\right\\rparen=\\operatorname\{sign\}\\left\\lparen g\\left\\lparen P\_\{1\}\(\\lvert x\\rvert\),\\dotsc,P\_\{d\}\(\\lvert x\\rvert\)\\right\\rparen\\right\\rparen\.

###### Proof\.

Fix any distinct positive scalarsch\>0c\_\{h\}\>0for allh∈\[H\]h\\in\[H\], and letQ0,Q1,…,QHQ\_\{0\},Q\_\{1\},\\dotsc,Q\_\{H\}be the corresponding polynomials defined in[Equation17](https://arxiv.org/html/2608.04243#S5.E17), which form an \(ordered\) basis for the vector space of polynomials of degree at mostHHas per[Lemma10](https://arxiv.org/html/2608.04243#Thmlemma10)\. Then for eachi∈\[d\]i\\in\[d\], there exists scalarsαi,βi\(1\),…,βi\(H\)\\alpha\_\{i\},\\beta\_\{i\}^\{\(1\)\},\\dotsc,\\beta\_\{i\}^\{\(H\)\}such that

Pi=αi​Q0\+∑h=1Hβi\(h\)​Qh\.P\_\{i\}=\\alpha\_\{i\}Q\_\{0\}\+\\sum\_\{h=1\}^\{H\}\\beta\_\{i\}^\{\(h\)\}Q\_\{h\}\.Formally dividing through byQ0Q\_\{0\}gives

Pi​\(t\)Q0​\(t\)=αi\+∑h=1H1n\+ch​t​βi\(h\)=∑h=1H\(1H​αi\+1n\+ch​t​βi\(h\)\)∀i∈\[d\]\.\\frac\{P\_\{i\}\(t\)\}\{Q\_\{0\}\(t\)\}=\\alpha\_\{i\}\+\\sum\_\{h=1\}^\{H\}\\frac\{1\}\{n\+c\_\{h\}t\}\\beta\_\{i\}^\{\(h\)\}=\\sum\_\{h=1\}^\{H\}\\left\\lparen\\frac\{1\}\{H\}\\alpha\_\{i\}\+\\frac\{1\}\{n\+c\_\{h\}t\}\\beta\_\{i\}^\{\(h\)\}\\right\\rparen\\quad\\forall i\\in\[d\]\.Observe thatQ0​\(t\)\>0Q\_\{0\}\(t\)\>0for allt≥0t\\geq 0sincech≥0c\_\{h\}\\geq 0for allh∈\[H\]h\\in\[H\]\.

Letα:=\(α1,…,αd\)∈ℝd\\alpha:=\(\\alpha\_\{1\},\\dotsc,\\alpha\_\{d\}\)\\in\\mathbb\{R\}^\{d\}andβ\(h\):=\(β1\(h\),…,βd\(h\)\)∈ℝd\\beta^\{\(h\)\}:=\(\\beta\_\{1\}^\{\(h\)\},\\dotsc,\\beta\_\{d\}^\{\(h\)\}\)\\in\\mathbb\{R\}^\{d\}for eachh∈\[H\]h\\in\[H\]\. For eachh∈\[H\]h\\in\[H\], we apply[Lemma9](https://arxiv.org/html/2608.04243#Thmlemma9)witha:=α/Ha:=\\alpha/H,b:=β\(h\)b:=\\beta^\{\(h\)\},c:=ch\>0c:=c\_\{h\}\>0; this provides a construction forHHattention heads with parameters[Equation15](https://arxiv.org/html/2608.04243#S5.E15)and value vector dimensiondd, such that for allx=\(x1,…,xn\)∈\{0,1\}nx=\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\},

Att\(⟨\(q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n=1Hα\+1n\+ch​\|x\|β\(h\),∀h∈\[H\]\.\\operatorname\{Att\}\(\\langle\(q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}=\\frac\{1\}\{H\}\\alpha\+\\frac\{1\}\{n\+c\_\{h\}\\lvert x\\rvert\}\\beta^\{\(h\)\},\\quad\\forall h\\in\[H\]\.Therefore

∑h=1HAtt\(⟨q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n=α\+∑h=1H1n\+ch​\|x\|β\(h\)=\(P1​\(\|x\|\),…,Pd​\(\|x\|\)\)Q0​\(\|x\|\)\.\\sum\_\{h=1\}^\{H\}\\operatorname\{Att\}\(\\langle q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}=\\alpha\+\\sum\_\{h=1\}^\{H\}\\frac\{1\}\{n\+c\_\{h\}\\lvert x\\rvert\}\\beta^\{\(h\)\}=\\frac\{\(P\_\{1\}\(\\lvert x\\rvert\),\\dotsc,P\_\{d\}\(\\lvert x\\rvert\)\)\}\{Q\_\{0\}\(\\lvert x\\rvert\)\}\.Note thatQ0​\(\|x\|\)Q\_\{0\}\(\\lvert x\\rvert\)is positive because\|x\|≥0\\lvert x\\rvert\\geq 0for allx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}\.

For the final claim \(after“Furthermore”\), letDDdenote the degree ofgg, and observe that for anyx=\(x1,…,xn\)∈\{0,1\}nx=\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\\\{0,1\\\}^\{n\},

g\(∑h=1HAtt\(⟨q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n\)=g\(P1​\(\|x\|\)Q0​\(\|x\|\),…,Pd​\(\|x\|\)Q0​\(\|x\|\)\)=g​\(P1​\(\|x\|\),…,Pd​\(\|x\|\)\)Q0​\(\|x\|\)D,g\\left\\lparen\\sum\_\{h=1\}^\{H\}\\operatorname\{Att\}\(\\langle q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}\\right\\rparen=g\\left\\lparen\\frac\{P\_\{1\}\(\\lvert x\\rvert\)\}\{Q\_\{0\}\(\\lvert x\\rvert\)\},\\dotsc,\\frac\{P\_\{d\}\(\\lvert x\\rvert\)\}\{Q\_\{0\}\(\\lvert x\\rvert\)\}\\right\\rparen=\\frac\{g\\lparen P\_\{1\}\(\\lvert x\\rvert\),\\dotsc,P\_\{d\}\(\\lvert x\\rvert\)\\rparen\}\{Q\_\{0\}\(\\lvert x\\rvert\)^\{D\}\},where the last equality follows by homogeneity ofgg\. SinceQ0​\(\|x\|\)\>0Q\_\{0\}\(\\lvert x\\rvert\)\>0, we have

sign\(g\(∑h=1HAtt\(⟨q\(h\),kxj\(h\)⟩,vxj\(h\)\)j=1n\)\)\\displaystyle\\operatorname\{sign\}\\left\\lparen g\\left\\lparen\\sum\_\{h=1\}^\{H\}\\operatorname\{Att\}\(\\langle q^\{\(h\)\},k\_\{x\_\{j\}\}^\{\(h\)\}\\rangle,v\_\{x\_\{j\}\}^\{\(h\)\}\)\_\{j=1\}^\{n\}\\right\\rparen\\right\\rparen=sign⁡\(g​\(P1​\(\|x\|\),…,Pd​\(\|x\|\)\)Q0​\(\|x\|\)D\)\\displaystyle=\\operatorname\{sign\}\\left\\lparen\\frac\{g\\lparen P\_\{1\}\(\\lvert x\\rvert\),\\dotsc,P\_\{d\}\(\\lvert x\\rvert\)\\rparen\}\{Q\_\{0\}\(\\lvert x\\rvert\)^\{D\}\}\\right\\rparen=sign⁡\(g​\(P1​\(\|x\|\),…,Pd​\(\|x\|\)\)\)\.∎\\displaystyle=\\operatorname\{sign\}\\left\\lparen g\\lparen P\_\{1\}\(\\lvert x\\rvert\),\\dotsc,P\_\{d\}\(\\lvert x\\rvert\)\\rparen\\right\\rparen\.\\qed

### 5\.4Degree\-restricted compositional sign\-representations

To use[Lemma11](https://arxiv.org/html/2608.04243#Thmlemma11), we need sign\-representations for symmetric Boolean functions that are the formg​\(P1​\(\|x\|\),…,Pd​\(\|x\|\)\)g\(P\_\{1\}\(\\lvert x\\rvert\),\\dotsc,P\_\{d\}\(\\lvert x\\rvert\)\)for some polynomialsP1,…,PdP\_\{1\},\\dotsc,P\_\{d\}of degree at mostHHand a homogeneousdd\-variate polynomial of degree at mostDD\.[Lemma12](https://arxiv.org/html/2608.04243#Thmlemma12)shows how to construct such representations with value vector dimensiond=Dd=Dusing partial products of the polynomial factorization\.

###### Lemma 12\.

LetF​\(t\)F\(t\)be a univariate polynomial of degreeTT\. SupposeDDandHHare positive integers withD×H≥TD\\times H\\geq T\. There exist

- •a positive integerd≤Dd\\leq D;
- •a homogeneousdd\-variate polynomialggwith degree at mostDD;
- •ddunivariate polynomialsP1​\(t\),…,Pd​\(t\)P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\), each of degree at mostHH;

such that

sign⁡\(F​\(t\)\)=sign⁡\(g​\(P1​\(t\),…,Pd​\(t\)\)\)\.\\operatorname\{sign\}\(F\(t\)\)=\\operatorname\{sign\}\(g\(P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\)\)\)\.

###### Proof\.

SinceF​\(t\)F\(t\)is a \(real\) univariate polynomial of degreeTT, it hasTTcomplex rootsr1,…,rTr\_\{1\},\\dotsc,r\_\{T\}\(counting multiplicity\), and thus it has a factorization

F​\(t\)=c​∏j=1T\(t−rj\),F\(t\)=c\\prod\_\{j=1\}^\{T\}\(t\-r\_\{j\}\),whereccis a real scalar\. LetT′∈\{0,…,T\}T^\{\\prime\}\\in\\\{0,\\dotsc,T\\\}denote the number of real roots\. Order the roots so thatr1,…,rT′r\_\{1\},\\dotsc,r\_\{T^\{\\prime\}\}are real, and letQ​\(t\):=∏j=T′\+1T\(t−rj\)Q\(t\):=\\prod\_\{j=T^\{\\prime\}\+1\}^\{T\}\(t\-r\_\{j\}\)denote the part of the product corresponding to non\-real roots, soF​\(t\)=c​∏j=1T′\(t−rj\)​Q​\(t\)F\(t\)=c\\prod\_\{j=1\}^\{T^\{\\prime\}\}\(t\-r\_\{j\}\)Q\(t\)\. We claim thatQ​\(t\)\>0Q\(t\)\>0\. To see this, note that any complex rootr=a\+b​ir=a\+b\\mathrm\{i\}withb≠0b\\neq 0can be paired with another root equal to its complex conjugater¯=a−b​i\\bar\{r\}=a\-b\\mathrm\{i\}, and the product of their contributing factors is

\(t−r\)​\(t−r¯\)=\(t−\(a\+b​i\)\)​\(t−\(a−b​i\)\)=\(t−a\)2\+b2\>0\.\(t\-r\)\(t\-\\bar\{r\}\)=\(t\-\(a\+b\\mathrm\{i\}\)\)\(t\-\(a\-b\\mathrm\{i\}\)\)=\(t\-a\)^\{2\}\+b^\{2\}\>0\.
SinceD×H≥T≥T′D\\times H\\geq T\\geq T^\{\\prime\}, we may partition the indices\[T′\]\[T^\{\\prime\}\]intod≤Dd\\leq Ddisjoint setsJ1,…,JdJ\_\{1\},\\dotsc,J\_\{d\}with at mostHHindices per set\. For eachi∈\[d\]i\\in\[d\], define

Pi​\(t\):=∏j∈Ji\(t−rj\),P\_\{i\}\(t\):=\\prod\_\{j\\in J\_\{i\}\}\(t\-r\_\{j\}\),which is a polynomial of degree\|Ji\|≤H\\lvert J\_\{i\}\\rvert\\leq H\. Also define thedd\-variate polynomial

g​\(z1,…,zd\):=sign⁡\(c\)​z1​⋯​zd,g\(z\_\{1\},\\dotsc,z\_\{d\}\):=\\operatorname\{sign\}\(c\)z\_\{1\}\\dotsm z\_\{d\},which is homogeneous and has degree at mostDD\. We have

\|c\|​g​\(P1​\(t\),…,Pd​\(t\)\)​Q​\(t\)=c​\(∏j∈J1\(t−rj\)\)​⋯​\(∏j∈Jd\(t−rj\)\)​Q​\(t\)=c​∏j=1T′\(t−rj\)​Q​\(t\)=F​\(t\)\.\\lvert c\\rvert g\(P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\)\)Q\(t\)=c\\left\\lparen\\prod\_\{j\\in J\_\{1\}\}\(t\-r\_\{j\}\)\\right\\rparen\\dotsm\\left\\lparen\\prod\_\{j\\in J\_\{d\}\}\(t\-r\_\{j\}\)\\right\\rparen Q\(t\)=c\\prod\_\{j=1\}^\{T^\{\\prime\}\}\(t\-r\_\{j\}\)Q\(t\)=F\(t\)\.Therefore, sinceQ​\(t\)\>0Q\(t\)\>0,

sign⁡\(g​\(P1​\(t\),…,Pd​\(t\)\)\)=sign⁡\(\|c\|​g​\(P1​\(t\),…,Pd​\(t\)\)​Q​\(t\)\)=sign⁡\(F​\(t\)\)\.∎\\operatorname\{sign\}\\left\\lparen g\(P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\)\)\\right\\rparen=\\operatorname\{sign\}\\left\\lparen\\lvert c\\rvert g\(P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\)\)Q\(t\)\\right\\rparen=\\operatorname\{sign\}\\left\\lparen F\(t\)\\right\\rparen\.\\qed

WhenDDis large \(relative to some positive power ofHH\), we can achieve a smaller value vector dimensionddusing a different approach based on additive bases\. We first show how to carry out this approach when provided a suitable additiveDD\-basis in[Lemma13](https://arxiv.org/html/2608.04243#Thmlemma13); the conditions requires to guarantee the existence of such an additiveDD\-basis are deferred to[Lemma14](https://arxiv.org/html/2608.04243#Thmlemma14)\.

###### Lemma 13\.

LetF​\(t\)F\(t\)be a univariate polynomial of degreeTT\. Supposeℬ⊆\[H\]\\mathcal\{B\}\\subseteq\[H\]is an additiveDD\-basis with rangeTT\. Setd:=\|ℬ\|\+1d:=\\lvert\\mathcal\{B\}\\rvert\+1\. There exist

- •a homogeneousdd\-variate polynomialggwith degreeDD;
- •ddunivariate monomialsP1​\(t\),…,Pd​\(t\)P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\), each of degree at mostHH;

such that

F​\(t\)=g​\(P1​\(t\),…,Pd​\(t\)\)\.F\(t\)=g\(P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\)\)\.

###### Proof\.

Denote thed−1d\-1elements ofℬ\\mathcal\{B\}byβ1,…,βd−1\\beta\_\{1\},\\dotsc,\\beta\_\{d\-1\}\. DefinePi​\(t\):=tβiP\_\{i\}\(t\):=t^\{\\beta\_\{i\}\}for eachi∈\[d−1\]i\\in\[d\-1\], andPd​\(t\):=1P\_\{d\}\(t\):=1\. Sinceℬ⊆\[H\]\\mathcal\{B\}\\subseteq\[H\], eachPi​\(t\)P\_\{i\}\(t\)is a monomial of degree at mostHH\. Sinceℬ\\mathcal\{B\}is an additiveDD\-basis with rangeTT, eachℓ∈\{0,1,…,T\}\\ell\\in\\\{0,1,\\dotsc,T\\\}can be written as

ℓ=cℓ,1​β1\+⋯\+cℓ,d−1​βd−1\\ell=c\_\{\\ell,1\}\\beta\_\{1\}\+\\dotsb\+c\_\{\\ell,d\-1\}\\beta\_\{d\-1\}for some non\-negative integerscℓ,1,…,cℓ,d−1c\_\{\\ell,1\},\\dotsc,c\_\{\\ell,d\-1\}that sum to at mostDD\. Furthermore, for eachℓ\\ell, definecℓ,d:=D−∑i=1d−1cℓ,i≥0c\_\{\\ell,d\}:=D\-\\sum\_\{i=1\}^\{d\-1\}c\_\{\\ell,i\}\\geq 0, so we have

∑i=1dcℓ,i=D,∀ℓ∈\{0,1,…,T\}\.\\sum\_\{i=1\}^\{d\}c\_\{\\ell,i\}=D,\\quad\\forall\\ell\\in\\\{0,1,\\dotsc,T\\\}\.\(18\)ExpandF​\(t\)F\(t\)in the monomial basis:

F​\(t\)=∑ℓ=0Taℓ​tℓ;F\(t\)=\\sum\_\{\\ell=0\}^\{T\}a\_\{\\ell\}t^\{\\ell\};correspondingly, define thedd\-variate polynomialggby

g​\(z1,…,zd\):=∑ℓ=0Taℓ​∏i=1dzicℓ,i\.g\(z\_\{1\},\\dotsc,z\_\{d\}\):=\\sum\_\{\\ell=0\}^\{T\}a\_\{\\ell\}\\prod\_\{i=1\}^\{d\}z\_\{i\}^\{c\_\{\\ell,i\}\}\.Note that[Equation18](https://arxiv.org/html/2608.04243#S5.E18)ensures thatggis homogeneous and has degreeDD\. Furthermore,

g​\(P1​\(t\),…,Pd​\(t\)\)\\displaystyle g\(P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\)\)=∑ℓ=0Taℓ​P1​\(t\)cℓ,1​⋯​Pd−1​\(t\)cℓ,d−1​Pd​\(t\)cℓ,d\\displaystyle=\\sum\_\{\\ell=0\}^\{T\}a\_\{\\ell\}P\_\{1\}\(t\)^\{c\_\{\\ell,1\}\}\\dotsm P\_\{d\-1\}\(t\)^\{c\_\{\\ell,d\-1\}\}P\_\{d\}\(t\)^\{c\_\{\\ell,d\}\}=∑ℓ=0Taℓ​\(tβ1\)cℓ,1​⋯​\(tβd−1\)cℓ,d−1​\(1\)cℓ,d\\displaystyle=\\sum\_\{\\ell=0\}^\{T\}a\_\{\\ell\}\\left\\lparen t^\{\\beta\_\{1\}\}\\right\\rparen^\{c\_\{\\ell,1\}\}\\dotsm\\left\\lparen t^\{\\beta\_\{d\-1\}\}\\right\\rparen^\{c\_\{\\ell,d\-1\}\}\\left\\lparen 1\\right\\rparen^\{c\_\{\\ell,d\}\}=∑ℓ=0Taℓ​tℓ=F​\(t\)\.∎\\displaystyle=\\sum\_\{\\ell=0\}^\{T\}a\_\{\\ell\}t^\{\\ell\}=F\(t\)\.\\qed

The existence of small additiveDD\-bases from\[H\]\[H\]is provided in the next[lemma](https://arxiv.org/html/2608.04243#Thmlemma14)under an assumption about the relationship betweenDDandHH\. The proof is given in[AppendixC](https://arxiv.org/html/2608.04243#A3)\.

###### Lemma 14\.

LetDD,HH,ppbe positive integers withD\+2≥2​p​\(b−1\)D\+2\\geq 2p\(b\-1\)whereb:=⌈H1/p⌉b:=\\lceil H^\{1/p\}\\rceil\. Every non\-negative integer at mostD​HDHis equal to the sum of at mostDDcopies of elements from

ℬ:=\{H\}∪ℬ1∪ℬ2\\mathcal\{B\}:=\\\{H\\\}\\cup\\mathcal\{B\}\_\{1\}\\cup\\mathcal\{B\}\_\{2\}whereℬ1:=\{b0,b1,…,bp−1\}∩\{1,…,H−1\}\\mathcal\{B\}\_\{1\}:=\\\{b^\{0\},b^\{1\},\\dotsc,b^\{p\-1\}\\\}\\cap\\\{1,\\dotsc,H\-1\\\}andℬ2:=\{H−βΓβ∈ℬ1\}\\mathcal\{B\}\_\{2\}:=\\\{H\-\\beta\\nonscript\\\>\|\\nonscript\\\>\\mathopen\{\}\\beta\\in\\mathcal\{B\}\_\{1\}\\\}\. Hence, there exists an additiveDD\-basisℬ⊆\[H\]\\mathcal\{B\}\\subseteq\[H\]with rangeD​HDHof cardinality\|ℬ\|≤2​p\+1\\lvert\\mathcal\{B\}\\rvert\\leq 2p\+1\.

### 5\.5Finishing the proof

We can now complete the proof of[Theorem3](https://arxiv.org/html/2608.04243#Thmtheorem3)\.

###### Proof of[Theorem3](https://arxiv.org/html/2608.04243#Thmtheorem3)\.

By Minsky\-Papert symmetrization\[[18](https://arxiv.org/html/2608.04243#bib.bib18)\], it is known that the threshold degree of a symmetric Boolean functionf:\{0,1\}n→\{−1,1\}f\\colon\\\{0,1\\\}^\{n\}\\to\\\{\-1,1\\\}is also the minimum degreeTTof a univariate polynomialF​\(t\)F\(t\)such thatx↦F​\(\|x\|\)x\\mapsto F\(\\lvert x\\rvert\)sign\-representsff\. So fix a univariate polynomialF​\(t\)F\(t\)of degreeTT, and assumeD×H≥TD\\times H\\geq T\. Letp:=max⁡\{1,⌈log2⁡\(H\)⌉\}p:=\\max\\\{1,\\lceil\\log\_\{2\}\(H\)\\rceil\\\}\. There are two cases to consider\.

- •Case 1:D≤2​p−3D\\leq 2p\-3\. We use[Lemma12](https://arxiv.org/html/2608.04243#Thmlemma12)to obtain a sign\-representation ofF​\(t\)F\(t\)byg​\(P1​\(t\),…,Pd​\(t\)\)g\(P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\)\)withd=Dd=D, which we use with[Lemma11](https://arxiv.org/html/2608.04243#Thmlemma11)to get the requiredHHattention heads anddd\-variate polynomialgg\. Note that this construction is applicable for all values ofDD, not just those withD≤2​p−3D\\leq 2p\-3\.
- •Case 2:D≥2​p−2D\\geq 2p\-2\. Letb:=⌈H1/p⌉=2b:=\\lceil H^\{1/p\}\\rceil=2, soD\+2≥2​p​\(b−1\)D\+2\\geq 2p\(b\-1\)\. We can therefore obtain an additiveDD\-basisℬ⊆\[H\]\\mathcal\{B\}\\subseteq\[H\]with rangeT≤D​HT\\leq DHfrom[Lemma14](https://arxiv.org/html/2608.04243#Thmlemma14)\. We useℬ\\mathcal\{B\}and[Lemma13](https://arxiv.org/html/2608.04243#Thmlemma13)to obtain a representation ofF​\(t\)=g​\(P1​\(t\),…,Pd​\(t\)\)F\(t\)=g\(P\_\{1\}\(t\),\\dotsc,P\_\{d\}\(t\)\)withd=\|ℬ\|\+1≤2​p\+2d=\\lvert\\mathcal\{B\}\\rvert\+1\\leq 2p\+2, which again we use with[Lemma11](https://arxiv.org/html/2608.04243#Thmlemma11)to get the requiredHHattention heads anddd\-variate polynomialgg\. ∎

To obtain an explicit construction of the multi\-head self\-attention layer and post\-processing polynomial threshold function, we require access to a univariate polynomialF​\(t\)F\(t\)such thatx↦F​\(\|x\|\)x\\mapsto F\(\\lvert x\\rvert\)sign\-represents the target symmetric Boolean function\. When[Lemma12](https://arxiv.org/html/2608.04243#Thmlemma12)is used, it suffices to have the real roots ofF​\(t\)F\(t\)and the sign of its leading coefficient\. When[Lemma13](https://arxiv.org/html/2608.04243#Thmlemma13)is used instead, we need the coefficients ofF​\(t\)F\(t\)in the monomial basis\. All other aspects of the proof of[Theorem3](https://arxiv.org/html/2608.04243#Thmtheorem3)are constructive\.

## 6Discussion

The most patent limitation of[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)is that it only considers post\-processing by linear classifiers\. Although linear predictability is a natural benchmark for assessing multi\-task representations\[e\.g\.,[7](https://arxiv.org/html/2608.04243#bib.bib7),[27](https://arxiv.org/html/2608.04243#bib.bib27)\], it is also common to use non\-linear predictors such as kernel machines and neural networks\. It is not clear to us how to extend the lower bound in[Theorem1](https://arxiv.org/html/2608.04243#Thmtheorem1)to hold against non\-linear classifiers, nor is it clear how to get around the lower bound with such classifiers \(without also greatly increasing the embedding dimension or precision level\)\. If further restrictions are put on the classifier \(e\.g\., smoothness\), then techniques similar to those fromYu et al\. \[[30](https://arxiv.org/html/2608.04243#bib.bib30)\]can be used to establish lower bounds against some families of non\-linear classifiers like neural networks \(see[AppendixD](https://arxiv.org/html/2608.04243#A4)\)\.

[Theorems2](https://arxiv.org/html/2608.04243#Thmtheorem2)and[3](https://arxiv.org/html/2608.04243#Thmtheorem3)together show that increasing the number of heads in an attention layer \(when post\-processed by a polynomial threshold function\) serves the role of amplifying the threshold degree of \(symmetric\) Boolean functions that can be computed\. A large value vector dimension cannot compensate for an deficient number of heads\. OurHH\-head attention layer constructions use dimensionO​\(min⁡\{D,log⁡H\}\)O\(\\min\\\{D,\\log H\\\}\)\. It would be interesting to understand if this dimension is necessary, or what fine\-grained role the dimension plays for sign\-representing Boolean functions\.

Our results concern standard softmax attention without any bells and whistles like positional embeddings and layer normalization\. Considering the effect of these features, as well as the joint role of multiple heads and multiple layers, are interesting directions for future research\.

## References

- Adler \[2026\]Micah Adler\.A capacity\-based rationale for multi\-head attention, 2026\.URL[https://arxiv\.org/abs/2509\.22840](https://arxiv.org/abs/2509.22840)\.
- Awerbuch and Kleinberg \[2008\]Baruch Awerbuch and Robert Kleinberg\.Online linear optimization and adaptive routing\.*Journal of Computer and System Sciences*, 74\(1\):97–114, 2008\.
- Challis and Robinson \[2010\]Michael F Challis and John P Robinson\.Some extremal postage stamp bases\.*Journal of Integer Sequences*, 13\(2\):3, 2010\.
- Chen et al\. \[2024\]Lijie Chen, Binghui Peng, and Hongxun Wu\.Theoretical limitations of multi\-layer transformer, 2024\.URL[https://arxiv\.org/abs/2412\.02975](https://arxiv.org/abs/2412.02975)\.
- Chiang et al\. \[2023\]David Chiang, Peter Cholak, and Anand Pillay\.Tighter bounds on the expressivity of transformer encoders, 2023\.URL[https://arxiv\.org/abs/2301\.10743](https://arxiv.org/abs/2301.10743)\.
- Devlin et al\. \[2018\]Jacob Devlin, Ming\-Wei Chang, Kenton Lee, and Kristina Toutanova\.BERT: Pre\-training of deep bidirectional transformers for language understanding, 2018\.URL[https://arxiv\.org/abs/1810\.04805](https://arxiv.org/abs/1810.04805)\.
- Du et al\. \[2020\]Simon S\. Du, Wei Hu, Sham M\. Kakade, Jason D\. Lee, and Qi Lei\.Few\-shot learning via learning the representation, provably, 2020\.URL[https://arxiv\.org/abs/2002\.09434](https://arxiv.org/abs/2002.09434)\.
- Erdős and Szekeres \[1935\]Paul Erdős and George Szekeres\.A combinatorial problem in geometry\.*Compositio Mathematica*, 2:463–470, 1935\.
- Hahn \[2020\]Michael Hahn\.Theoretical limitations of self\-attention in neural sequence models\.*Transactions of the Association for Computational Linguistics*, 8:156–171, December 2020\.ISSN 2307\-387X\.doi:10\.1162/tacl˙a˙00306\.URL[http://dx\.doi\.org/10\.1162/tacl\_a\_00306](http://dx.doi.org/10.1162/tacl_a_00306)\.
- Hao et al\. \[2022\]Yiding Hao, Dana Angluin, and Robert Frank\.Formal language recognition by hard attention transformers: Perspectives from circuit complexity, 2022\.URL[https://arxiv\.org/abs/2204\.06618](https://arxiv.org/abs/2204.06618)\.
- Kajitsuka and Sato \[2023\]Tokio Kajitsuka and Issei Sato\.Are transformers with one layer self\-attention using low\-rank weight matrices universal approximators?, 2023\.URL[https://arxiv\.org/abs/2307\.14023](https://arxiv.org/abs/2307.14023)\.
- Kozachinskiy \[2024\]Alexander Kozachinskiy\.Lower bounds on transformers with infinite precision, 2024\.URL[https://arxiv\.org/abs/2412\.20195](https://arxiv.org/abs/2412.20195)\.
- Kozachinskiy et al\. \[2026\]Alexander Kozachinskiy, Tomasz Steifer, and Przemysław Wałȩga\.Parity, sensitivity, and transformers, 2026\.URL[https://arxiv\.org/abs/2602\.05896](https://arxiv.org/abs/2602.05896)\.
- Lin et al\. \[2017\]Zhouhan Lin, Minwei Feng, Cicero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio\.A structured self\-attentive sentence embedding, 2017\.URL[https://arxiv\.org/abs/1703\.03130](https://arxiv.org/abs/1703.03130)\.
- Liu et al\. \[2022\]Bingbin Liu, Jordan T\. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang\.Transformers learn shortcuts to automata, 2022\.URL[https://arxiv\.org/abs/2210\.10749](https://arxiv.org/abs/2210.10749)\.
- Merrill and Sabharwal \[2022\]William Merrill and Ashish Sabharwal\.The parallelism tradeoff: Limitations of log\-precision transformers, 2022\.URL[https://arxiv\.org/abs/2207\.00729](https://arxiv.org/abs/2207.00729)\.
- Merrill and Sabharwal \[2025\]William Merrill and Ashish Sabharwal\.A little depth goes a long way: The expressive power of log\-depth transformers, 2025\.URL[https://arxiv\.org/abs/2503\.03961](https://arxiv.org/abs/2503.03961)\.
- Minsky and Papert \[1969\]Marvin Minsky and Seymour Papert\.*Perceptrons: An introduction to computational geometry*\.MIT Press, 1969\.
- Mossige \[1987\]Svein Mossige\.On extremalhh\-basesA4A\_\{4\}\.*Mathematica Scandinavica*, pages 5–16, 1987\.
- Parikh et al\. \[2016\]Ankur P\. Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit\.A decomposable attention model for natural language inference, 2016\.URL[https://arxiv\.org/abs/1606\.01933](https://arxiv.org/abs/1606.01933)\.
- Peng et al\. \[2024\]Binghui Peng, Srini Narayanan, and Christos Papadimitriou\.On limitations of the transformer architecture, 2024\.URL[https://arxiv\.org/abs/2402\.08164](https://arxiv.org/abs/2402.08164)\.
- Sanford et al\. \[2023\]Clayton Sanford, Daniel Hsu, and Matus Telgarsky\.Representational strengths and limitations of transformers, 2023\.URL[https://arxiv\.org/abs/2306\.02896](https://arxiv.org/abs/2306.02896)\.
- Sanford et al\. \[2024a\]Clayton Sanford, Daniel Hsu, and Matus Telgarsky\.One\-layer transformers fail to solve the induction heads task, 2024a\.URL[https://arxiv\.org/abs/2408\.14332](https://arxiv.org/abs/2408.14332)\.
- Sanford et al\. \[2024b\]Clayton Sanford, Daniel Hsu, and Matus Telgarsky\.Transformers, parallel computation, and logarithmic depth, 2024b\.URL[https://arxiv\.org/abs/2402\.09268](https://arxiv.org/abs/2402.09268)\.
- Steele \[1995\]J\. Michael Steele\.Variations on the monotone subsequence theme of Erdös and Szekeres\.In David Aldous, Persi Diaconis, Joel Spencer, and J\. Michael Steele, editors,*Discrete Probability and Algorithms*, pages 111–131, New York, NY, 1995\. Springer New York\.
- Tesfaye et al\. \[2026\]Amanuel Tesfaye, Zeno Kujawa, Rajmohan Rajaraman, and Ravi Sundaram\.Two \(narrow\) heads are better than \(an arbitrarily wide\) one\.In*The Fourteenth International Conference on Learning Representations*, 2026\.URL[https://openreview\.net/forum?id=RRmPbbZsvl](https://openreview.net/forum?id=RRmPbbZsvl)\.
- Tripuraneni et al\. \[2020\]Nilesh Tripuraneni, Chi Jin, and Michael I\. Jordan\.Provable meta\-learning of linear representations, 2020\.URL[https://arxiv\.org/abs/2002\.11684](https://arxiv.org/abs/2002.11684)\.
- Vaswani et al\. \[2017\]Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N\. Gomez, Lukasz Kaiser, and Illia Polosukhin\.Attention is all you need, 2017\.URL[https://arxiv\.org/abs/1706\.03762](https://arxiv.org/abs/1706.03762)\.
- Viswanathan \[2026\]Karthik Viswanathan\.How many attention heads do you need to do XOR?LessWrong, April 2026\.URL[https://www\.lesswrong\.com/posts/T66BKwSufh5SfiPHm/how\-many\-attention\-heads\-do\-you\-need\-to\-do\-xor\-3](https://www.lesswrong.com/posts/T66BKwSufh5SfiPHm/how-many-attention-heads-do-you-need-to-do-xor-3)\.
- Yu et al\. \[2025\]Penghao Yu, Haotian Jiang, Zeyu Bao, Ruoxi Yu, and Qianxiao Li\.The effect of attention head count on transformer approximation, 2025\.URL[https://arxiv\.org/abs/2510\.06662](https://arxiv.org/abs/2510.06662)\.
- Zhao and Yu \[2006\]Peng Zhao and Bin Yu\.On model selection consistency of Lasso\.*Journal of Machine Learning Research*, 7\(90\):2541–2563, 2006\.URL[http://jmlr\.org/papers/v7/zhao06a\.html](http://jmlr.org/papers/v7/zhao06a.html)\.

## Appendix AAttention\-based minimum computation

In this[appendix](https://arxiv.org/html/2608.04243#A1), we describe an attention head and linear classifier that computes the minimum of a given list ofnnintegers from\[M\]\[M\]\.

###### Proposition 1\.

Fix integersM≥2M\\geq 2andn≥1n\\geq 1, and setd:=⌈8​ln⁡\(M\)⌉d:=\\left\\lceil 8\\ln\(M\)\\right\\rceil\. There exists query/key values⟨q,k1⟩,…,⟨q,kM⟩∈ℝ\\langle q,k\_\{1\}\\rangle,\\dotsc,\\langle q,k\_\{M\}\\rangle\\in\\mathbb\{R\}, value vectorsv1,…,vM∈\{−1,1\}dv\_\{1\},\\dotsc,v\_\{M\}\\in\\\{\-1,1\\\}^\{d\}, and an unambiguousMM\-class linear classifierfmin:ℝd→\[M\]∪\{⊥\}f^\{\\min\}\\colon\\mathbb\{R\}^\{d\}\\to\[M\]\\cup\\\{\\bot\\\}such that for all\(x1,…,xn\)∈\[M\]n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\[M\]^\{n\},

fmin\(Att\(⟨q,kxj⟩,vxj\)j=1n\)=min\{x1,…,xn\}\.f^\{\\min\}\(\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\)=\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\.

In this construction, the value vectors have dimensiond=⌈8​ln⁡\(M\)⌉d=\\lceil 8\\ln\(M\)\\rceiland Euclidean norm exactlyℓ:=d=⌈8​ln⁡\(M\)⌉\\ell:=\\sqrt\{d\}=\\sqrt\{\\lceil 8\\ln\(M\)\\rceil\}, and their components are integer multiples of2−p2^\{\-p\}forp:=0p:=0\.

The same construction works for computing the maximum, just negating all query/key values in the attention head construction\.

###### Proof of[Proposition1](https://arxiv.org/html/2608.04243#Thmproposition1)\.

Choose vectorsvx∈\{−1,1\}dv\_\{x\}\\in\\\{\-1,1\\\}^\{d\}for eachx∈\[M\]x\\in\[M\]such that every pair of vectorsvx,vyv\_\{x\},v\_\{y\}forx≠yx\\neq ydiffer in at leastd/4d/4positions\. Such a choice of vectors is guaranteed to be possible by the Gilbert\-Varshamov bound sinced≥8​ln⁡\(M\)d\\geq 8\\ln\(M\)\. Define⟨q,kx⟩:=−η​x\\langle q,k\_\{x\}\\rangle:=\-\\eta xfor eachx∈\[M\]x\\in\[M\], whereη:=⌈ln⁡\(n​\(n​d−1\)\)⌉\\eta:=\\lceil\\ln\(n\(nd\-1\)\)\\rceil\. Let the weight vectors forfminf^\{\\min\}beθx:=vx\\theta\_\{x\}:=v\_\{x\}for allx∈\[M\]x\\in\[M\]\.

Consider an input\(x1,…,xn\)\(x\_\{1\},\\dotsc,x\_\{n\}\)wherex=min⁡\{x1,…,xn\}x=\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\. Then a short calculation shows that the outputzzof the attention head can be written as

z=p​vx\+\(1−p\)​v¯,z=pv\_\{x\}\+\(1\-p\)\\bar\{v\},wherev¯\\bar\{v\}is a convex combination of othervyv\_\{y\}’s withy≠xy\\neq x, andp∈\[1−1/\(n​d\),1\]p\\in\[1\-1/\(nd\),1\]\. Then

⟨θx,z⟩=⟨vx,z⟩=p​⟨vx,vx⟩\+\(1−p\)​⟨vx,v¯⟩≥p​d−\(1−p\)​d=d−2n\.\\langle\\theta\_\{x\},z\\rangle=\\langle v\_\{x\},z\\rangle=p\\langle v\_\{x\},v\_\{x\}\\rangle\+\(1\-p\)\\langle v\_\{x\},\\bar\{v\}\\rangle\\geq pd\-\(1\-p\)d=d\-\\frac\{2\}\{n\}\.Fory≠xy\\neq x, sincevyv\_\{y\}andvxv\_\{x\}differ in at leastd/4d/4positions,

⟨θy,z⟩=⟨vy,z⟩=p​⟨vy,vx⟩\+\(1−p\)​⟨vy,v¯⟩≤p​d2\+\(1−p\)​d≤d2\+12​n\.\\langle\\theta\_\{y\},z\\rangle=\\langle v\_\{y\},z\\rangle=p\\langle v\_\{y\},v\_\{x\}\\rangle\+\(1\-p\)\\langle v\_\{y\},\\bar\{v\}\\rangle\\leq p\\frac\{d\}\{2\}\+\(1\-p\)d\\leq\\frac\{d\}\{2\}\+\\frac\{1\}\{2n\}\.So we have⟨θx,z⟩\>⟨θy,z⟩\\langle\\theta\_\{x\},z\\rangle\>\\langle\\theta\_\{y\},z\\ranglefor ally≠xy\\neq x\(sinced\>5/nd\>5/n\)\. ∎

## Appendix BDeferred proofs

See[2](https://arxiv.org/html/2608.04243#Thmlemma2)

###### Proof\.

Fixx,y∈\[M\]x,y\\in\[M\]withx<yx<y\. We consider different inputs\(x1,…,xn\)∈\[M\]n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\[M\]^\{n\}corresponding to different histogram vectorshh, and derive consequences of correctmin\\mincomputation on these inputs\.

1. 1\.Supposehx=nh\_\{x\}=nandhi=0h\_\{i\}=0for alli≠xi\\neq x\. The minimum isxx, so ∑i=1Mhi​Δix,y\>0\.\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}\>0\.Moreover, ∑i=1Mhi​Δix,y=hx​Δxx,y=n​Δxx,y\.\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}=h\_\{x\}\\Delta\_\{x\}^\{x,y\}=n\\Delta\_\{x\}^\{x,y\}\.Hence Δxx,y\>0\.\\Delta\_\{x\}^\{x,y\}\>0\.This proves the first part of the claim\.
2. 2\.Supposehy=nh\_\{y\}=nandhi=0h\_\{i\}=0for alli≠yi\\neq y\. The minimum isyy, so ∑i=1Mhi​Δix,y<0\.\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}<0\.Moreover, ∑i=1Mhi​Δix,y=hy​Δyx,y=n​Δyx,y\.\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}=h\_\{y\}\\Delta\_\{y\}^\{x,y\}=n\\Delta\_\{y\}^\{x,y\}\.Hence Δyx,y<0\.\\Delta\_\{y\}^\{x,y\}<0\.\(19\)
3. 3\.Supposehx=1h\_\{x\}=1andhz=n−1h\_\{z\}=n\-1for somez≥yz\\geq y, andhi=0h\_\{i\}=0for alli∉\{x,z\}i\\notin\\\{x,z\\\}\. The minimum isxx, so ∑i=1Mhi​Δix,y\>0\.\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}\>0\.Moreover, ∑i=1Mhi​Δix,y=hx​Δxx,y\+hz​Δzx,y=Δxx,y\+\(n−1\)​Δzx,y\.\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}=h\_\{x\}\\Delta\_\{x\}^\{x,y\}\+h\_\{z\}\\Delta\_\{z\}^\{x,y\}=\\Delta\_\{x\}^\{x,y\}\+\(n\-1\)\\Delta\_\{z\}^\{x,y\}\.Hence Δzx,y\>−1n−1​Δxx,y,\\Delta\_\{z\}^\{x,y\}\>\-\\frac\{1\}\{n\-1\}\\Delta\_\{x\}^\{x,y\},\(20\)and, in particular, forz=yz=y, \|Δyx,y\|=−Δyx,y<1n−1​Δxx,y\\lvert\\Delta\_\{y\}^\{x,y\}\\rvert=\-\\Delta\_\{y\}^\{x,y\}<\\frac\{1\}\{n\-1\}\\Delta\_\{x\}^\{x,y\}\(21\)where we have used the fact thatΔyx,y\\Delta\_\{y\}^\{x,y\}is negative, per[Equation19](https://arxiv.org/html/2608.04243#A2.E19)\.
4. 4\.Supposehy=1h\_\{y\}=1andhz=n−1h\_\{z\}=n\-1for somez\>yz\>y, andhi=0h\_\{i\}=0for alli∉\{y,z\}i\\notin\\\{y,z\\\}\. The minimum isyy, so ∑i=1Mhi​Δix,y<0\.\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}<0\.Moreover, ∑i=1Mhi​Δix,y=hy​Δyx,y\+hz​Δzx,y=Δyx,y\+\(n−1\)​Δzx,y\.\\sum\_\{i=1\}^\{M\}h\_\{i\}\\Delta\_\{i\}^\{x,y\}=h\_\{y\}\\Delta\_\{y\}^\{x,y\}\+h\_\{z\}\\Delta\_\{z\}^\{x,y\}=\\Delta\_\{y\}^\{x,y\}\+\(n\-1\)\\Delta\_\{z\}^\{x,y\}\.Hence Δzx,y<−1n−1​Δyx,y=1n−1​\|Δyx,y\|\.\\Delta\_\{z\}^\{x,y\}<\-\\frac\{1\}\{n\-1\}\\Delta\_\{y\}^\{x,y\}=\\frac\{1\}\{n\-1\}\\lvert\\Delta\_\{y\}^\{x,y\}\\rvert\.Combining with[Equation21](https://arxiv.org/html/2608.04243#A2.E21), we have Δzx,y<1\(n−1\)2​Δxx,y≤1n−1​Δxx,y\.\\Delta\_\{z\}^\{x,y\}<\\frac\{1\}\{\\lparen n\-1\\rparen^\{2\}\}\\Delta\_\{x\}^\{x,y\}\\leq\\frac\{1\}\{n\-1\}\\Delta\_\{x\}^\{x,y\}\.\(22\)Combining[Equation22](https://arxiv.org/html/2608.04243#A2.E22)and[Equation20](https://arxiv.org/html/2608.04243#A2.E20)\(both of which hold for allz\>yz\>y\) gives \|Δzx,y\|<1n−1​Δxx,y\.\\lvert\\Delta\_\{z\}^\{x,y\}\\rvert<\\frac\{1\}\{n\-1\}\\Delta\_\{x\}^\{x,y\}\.\(23\)Combining[Equation21](https://arxiv.org/html/2608.04243#A2.E21)and[Equation23](https://arxiv.org/html/2608.04243#A2.E23)proves the second part of the claim\. ∎

See[1](https://arxiv.org/html/2608.04243#Thmclaim1)

###### Proof\.

The claim follows from Hadamard’s inequality\. ∎

See[2](https://arxiv.org/html/2608.04243#Thmclaim2)

###### Proof\.

Since every entry ofAAis an integer, so is every entry ofA𝖳​AA^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}A\. SinceAAhas full column rank,A𝖳​AA^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}Ais positive definite, and hencedet\(A𝖳​A\)\>0\\det\(A^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}A\)\>0\. Butdet\(A𝖳​A\)\\det\(A^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}A\)is a polynomial in the entries ofA𝖳​AA^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}Awith integer coefficients and hence must evaluate to an integer\. Sodet\(A𝖳​A\)≥1\\det\(A^\{\\scriptscriptstyle\{\\mathsf\{T\}\}\}A\)\\geq 1\. ∎

See[10](https://arxiv.org/html/2608.04243#Thmlemma10)

###### Proof\.

Each ofQ0,Q1,…,QHQ\_\{0\},Q\_\{1\},\\dotsc,Q\_\{H\}is polynomial of degree at mostHH\. Hence it suffices to show that they are linearly independent\. Consider any real scalarsα0,α1,…,αH\\alpha\_\{0\},\\alpha\_\{1\},\\dotsc,\\alpha\_\{H\}and define

P:=∑i=0Hαi​Qi\.P:=\\sum\_\{i=0\}^\{H\}\\alpha\_\{i\}Q\_\{i\}\.Fixh∈\[H\]h\\in\[H\], and consider the evaluation ofPPatt:=−n/cht:=\-n/c\_\{h\}\. SinceQi​\(−n/ch\)=0Q\_\{i\}\(\-n/c\_\{h\}\)=0for alli≠hi\\neq h, we have

P​\(−n/ch\)=αh​∏i≠h\(n​\(1−cich\)\)\.P\(\-n/c\_\{h\}\)=\\alpha\_\{h\}\\prod\_\{i\\neq h\}\\left\\lparen n\\left\\lparen 1\-\\frac\{c\_\{i\}\}\{c\_\{h\}\}\\right\\rparen\\right\\rparen\.Since the scalarsc1,…,cHc\_\{1\},\\dotsc,c\_\{H\}are non\-zero and distinct, ifPPis the zero polynomial, thenαh=0\\alpha\_\{h\}=0for allh∈\[H\]h\\in\[H\]\. SinceQ0Q\_\{0\}is evidently not the zero polynomial, it follows that ifα0​Q0≡0\\alpha\_\{0\}Q\_\{0\}\\equiv 0, thenα0=0\\alpha\_\{0\}=0as well\. So, ifPPis the zero polynomial, thenα0=α1=⋯=αH=0\\alpha\_\{0\}=\\alpha\_\{1\}=\\dotsb=\\alpha\_\{H\}=0, which means thatQ0,Q1,…,QHQ\_\{0\},Q\_\{1\},\\dotsc,Q\_\{H\}are linearly independent\. ∎

## Appendix CAdditive bases

In this[appendix](https://arxiv.org/html/2608.04243#A3), we give an approach for constructing additiveDD\-bases with rangeD​HDHusing elements from\[H\]\[H\]\.

To give the main idea of the construction, we consider the special case whereH≥2H\\geq 2is a power\-of\-two \(so in[Lemma14](https://arxiv.org/html/2608.04243#Thmlemma14), we havep=log2⁡Hp=\\log\_\{2\}Handb=2b=2\)\. The candidate additiveDD\-basis isℬ=\{H\}∪ℬ1∪ℬ2\\mathcal\{B\}=\\\{H\\\}\\cup\\mathcal\{B\}\_\{1\}\\cup\\mathcal\{B\}\_\{2\}, whereℬ1=\{20,21,22,…,H/2\}\\mathcal\{B\}\_\{1\}=\\\{2^\{0\},2^\{1\},2^\{2\},\\dotsc,H/2\\\}, andℬ2=\{H−20,H−21,H−22,…,H/2\}\\mathcal\{B\}\_\{2\}=\\\{H\-2^\{0\},H\-2^\{1\},H\-2^\{2\},\\dotsc,H/2\\\}\. Let us test this candidate by trying to find a representation of an arbitraryn∈\[D​H\]n\\in\[DH\]as a sum of at mostDD\(not necessarily distinct\) elements ofℬ\\mathcal\{B\}\. We could try to useq=⌊n/H⌋q=\\lfloor n/H\\rfloorcopies ofHH, along with the elements ofℬ1\\mathcal\{B\}\_\{1\}needed to form the remainderr=n−q​H≤H−1r=n\-qH\\leq H\-1\. The only reason this representation might not work is that it uses more thanDDelements, meaning thatq\+log2⁡H≥D\+1q\+\\log\_\{2\}H\\geq D\+1\. In this case, we can try to reduce the number of copies ofHHneeded—say, fromqqtoq−Δq\-\\Delta—and make up for the difference by using elements ofℬ2\\mathcal\{B\}\_\{2\}to representΔ​H\+r\\Delta H\+r\. This latter representation is possible for some non\-negative integerΔ\\Deltaat mostlog2⁡H−1\\log\_\{2\}H\-1\. So, in the worst case, we needq≥log2⁡H−1q\\geq\\log\_\{2\}H\-1to be implied by the conditionq\+log2⁡H≥D\+1q\+\\log\_\{2\}H\\geq D\+1, which is true for large enoughDD\(i\.e\.,D≥2​\(log2⁡H−1\)D\\geq 2\(\\log\_\{2\}H\-1\)for this special case\)\.

See[14](https://arxiv.org/html/2608.04243#Thmlemma14)

###### Proof\.

The definition ofbbensures thatbp≥Hb^\{p\}\\geq H, and hence every non\-negative integerrrless thanHHcan be written as

r=c0​b0\+c1​b1\+⋯\+cp−1​bp−1r=c\_\{0\}b^\{0\}\+c\_\{1\}b^\{1\}\+\\dotsb\+c\_\{p\-1\}b^\{p\-1\}where the coefficientsc0,c1,…,cp−1c\_\{0\},c\_\{1\},\\dotsc,c\_\{p\-1\}are non\-negative integers at mostb−1b\-1\. For anyi∈\{0,…,p−1\}i\\in\\\{0,\\dotsc,p\-1\\\}, ifci\>0c\_\{i\}\>0, thenbi≤r<Hb^\{i\}\\leq r<H, and hencebi∈ℬ1b\_\{i\}\\in\\mathcal\{B\}\_\{1\}\. Moreover,

c0\+c1\+⋯\+cp−1≤p​\(b−1\)\.c\_\{0\}\+c\_\{1\}\+\\dotsb\+c\_\{p\-1\}\\leq p\(b\-1\)\.Therefore,rris equal to the sum of at mostp​\(b−1\)p\(b\-1\)copies of elements fromℬ1\\mathcal\{B\}\_\{1\}\.

Now consider any non\-negative integern≤D​Hn\\leq DH\. Ifn=D​Hn=DH, then we are done, sincennis the sum ofDDcopies ofHH\. So assumen≤D​H−1n\\leq DH\-1, and write

whereqqis the integer quotient, andrris the integer remainder\. Sincen≤D​H−1n\\leq DH\-1, the quotient is a non\-negative integer satisfying

q=⌊nH⌋≤⌊D​H−1H⌋=⌊D−1H⌋=D−1\.q=\\left\\lfloor\\frac\{n\}\{H\}\\right\\rfloor\\leq\\left\\lfloor\\frac\{DH\-1\}\{H\}\\right\\rfloor=\\left\\lfloor D\-\\frac\{1\}\{H\}\\right\\rfloor=D\-1\.Ifr=0r=0, then we are done, sincennis the sum ofq≤D−1q\\leq D\-1copies ofHH\. So henceforth we assume bothq≤D−1q\\leq D\-1andr≥1r\\geq 1\.

We now consider two cases:q\+p​\(b−1\)≤Dq\+p\(b\-1\)\\leq Dandq\+p​\(b−1\)≥D\+1q\+p\(b\-1\)\\geq D\+1\.

- •Case 1:q\+p​\(b−1\)≤Dq\+p\(b\-1\)\\leq D\. Sincer≥1r\\geq 1is integer remainder ofnnafter taking out multiples ofHH, it is a positive integer less thanHH\. Sorris equal to the sum ofmmcopies of elements fromℬ1\\mathcal\{B\}\_\{1\}for somem≤p​\(b−1\)m\\leq p\(b\-1\)\. Sincen=q​H\+rn=qH\+r, it follows thatnnis equal to the sum ofqqcopies ofHHandmmcopies of elements fromℬ1\\mathcal\{B\}\_\{1\}\. Sinceq\+m≤q\+p​\(b−1\)≤Dq\+m\\leq q\+p\(b\-1\)\\leq D, the claim follows in this case\.
- •Case 2:q\+p​\(b−1\)≥D\+1q\+p\(b\-1\)\\geq D\+1\. LetR:=H−rR:=H\-r, which is a positive integer less thanHH\. SoRRis equal to the sum ofmmcopies of elements fromℬ1\\mathcal\{B\}\_\{1\}for somem≤p​\(b−1\)m\\leq p\(b\-1\): R=β1\+⋯\+βm,β1,…,βm∈ℬ1\.R=\\beta\_\{1\}\+\\dotsb\+\\beta\_\{m\},\\quad\\beta\_\{1\},\\dotsc,\\beta\_\{m\}\\in\\mathcal\{B\}\_\{1\}\.Then n\\displaystyle n=q​H\+r\\displaystyle=qH\+r=\(q\+1\)​H−R\\displaystyle=\(q\+1\)H\-R=\(q\+1−m\)​H\+∑i=1m\(H−βi\)\.\\displaystyle=\(q\+1\-m\)H\+\\sum\_\{i=1\}^\{m\}\(H\-\\beta\_\{i\}\)\.Sinceq≥D\+1−p​\(b−1\)q\\geq D\+1\-p\(b\-1\),m≤p​\(b−1\)m\\leq p\(b\-1\), and \(by assumption\)D\+2≥2​p​\(b−1\)D\+2\\geq 2p\(b\-1\), it follows that a:=q\+1−m≥D\+2−2​p​\(b−1\)a:=q\+1\-m\\geq D\+2\-2p\(b\-1\)is a non\-negative integer\. Sonnis equal to the sum ofaacopies ofHHandmmcopies of elements fromℬ2\\mathcal\{B\}\_\{2\}\. Sinceq≤D−1q\\leq D\-1, it follows thata\+m=q\+1≤Da\+m=q\+1\\leq D\. Hence the claim follows in this case as well\. ∎

Note that we cannot hope to have such constant\-size additiveDD\-bases with rangeD​HDHfor arbitrary\(D,H\)\(D,H\)\. To see this, consider any set of positive integersℬ\\mathcal\{B\}of cardinalityk≥1k\\geq 1\. Then there are at most\(D\+kk\)\\binom\{D\+k\}\{k\}choices of\(c1,…,ck\)\(c\_\{1\},\\dotsc,c\_\{k\}\)with non\-negative integersc1,…,ckc\_\{1\},\\dotsc,c\_\{k\}that sum to at mostDD\. But there areD​H\+1DH\+1non\-negative integers at mostD​HDH\. Ifℬ\\mathcal\{B\}is an additiveDD\-basis with rangeD​HDHand cardinalitykk, then

\(D\+kk\)≥D​H\+1,\\binom\{D\+k\}\{k\}\\geq DH\+1,which impliesH≤\(D\+1\)k−1H\\leq\(D\+1\)^\{k\-1\}\.

## Appendix DLower bounds against post\-processing by Lipschitz predictors

In this[appendix](https://arxiv.org/html/2608.04243#A4), we consider attention heads that are post\-processed by a Lipschitz predictor\.[Proposition2](https://arxiv.org/html/2608.04243#Thmproposition2)shows that such attention heads cannot support bothmin\\minandmax\\maxcomputation unless the Lipschitz constant of the post\-processing classifiers or the distance between some pair of value vectors roughly grows at least as the square\-root of the input size\. The proof is similar in spirit to that ofYu et al\. \[[30](https://arxiv.org/html/2608.04243#bib.bib30)\]\. A lower bound on the Lipschitz constant of two\-layer neural net with Lipschitz activation functions and bounded parameter matrices implies a lower bound on the number of hidden units in the neural net\[see, e\.g\.,[30](https://arxiv.org/html/2608.04243#bib.bib30), Lemma 4\]\.

Let∥⋅∥\\lVert\\cdot\\rVertdenote a norm onℝd\\mathbb\{R\}^\{d\}, and let∥⋅∥∞\\lVert\\cdot\\rVert\_\{\\infty\}denote the infinity\-norm onℝM\\mathbb\{R\}^\{M\}\. LetΔ\(\[M\]\):=\{\(p1,…,pM\)Γpi≥0∀i∈\[M\],p1\+⋯\+pM=1\}\\Delta\(\[M\]\):=\\\{\(p\_\{1\},\\dotsc,p\_\{M\}\)\\nonscript\\\>\|\\nonscript\\\>\\mathopen\{\}p\_\{i\}\\geq 0\\,\\forall i\\in\[M\],p\_\{1\}\+\\dotsb\+p\_\{M\}=1\\\}denote the space of probability vectors inℝM\\mathbb\{R\}^\{M\}\. Finally, lete1,…,eMe\_\{1\},\\dotsc,e\_\{M\}denote the coordinate basis vectors inℝM\\mathbb\{R\}^\{M\}\.

###### Proposition 2\.

Fix integersM≥2M\\geq 2andn≥2n\\geq 2\. Suppose there are the following:

- •error boundϵ∈\(0,1/2\)\\epsilon\\in\\lparen 0,1/2\\rparen;
- •diameterD≥0D\\geq 0and Lipschitz constantL≥0L\\geq 0;
- •query/key values⟨q,k1⟩,…,⟨q,kM⟩∈ℝ\\langle q,k\_\{1\}\\rangle,\\dotsc,\\langle q,k\_\{M\}\\rangle\\in\\mathbb\{R\};
- •value vectorsv1,…,vM∈ℝdv\_\{1\},\\dotsc,v\_\{M\}\\in\\mathbb\{R\}^\{d\}such that∥vi−vj∥≤D\\lVert v\_\{i\}\-v\_\{j\}\\rVert\\leq Dfor alli,j∈\[M\]i,j\\in\[M\];
- •functionsgmin,gmax:ℝd→Δ​\(\[M\]\)g^\{\\min\},g^\{\\max\}\\colon\\mathbb\{R\}^\{d\}\\to\\Delta\(\[M\]\)that areLL\-Lipschitz maps from\(conv⁡\(\{v1,…,vM\}\),∥⋅∥\)\(\\operatorname\{conv\}\(\\\{v\_\{1\},\\dotsc,v\_\{M\}\\\}\),\\lVert\\cdot\\rVert\)to\(Δ​\(\[M\]\),∥⋅∥∞\)\(\\Delta\(\[M\]\),\\lVert\\cdot\\rVert\_\{\\infty\}\);

such that for all\(x1,…,xn\)∈\[M\]n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\[M\]^\{n\},

∥gmin\(Att\(⟨q,kxi⟩,vxi\)i=1n\)−emin⁡\{x1,…,xn\}∥∞\\displaystyle\\lVert g^\{\\min\}\(\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{i\}\}\\rangle,v\_\{x\_\{i\}\}\)\_\{i=1\}^\{n\}\)\-e\_\{\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\}\\rVert\_\{\\infty\}≤ϵ,\\displaystyle\\leq\\epsilon,∥gmax\(Att\(⟨q,kxi⟩,vxi\)i=1n\)−emax⁡\{x1,…,xn\}∥∞\\displaystyle\\lVert g^\{\\max\}\(\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{i\}\}\\rangle,v\_\{x\_\{i\}\}\)\_\{i=1\}^\{n\}\)\-e\_\{\\max\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\}\\rVert\_\{\\infty\}≤ϵ\.\\displaystyle\\leq\\epsilon\.Then

D​L≥\(1−2​ϵ\)​n\.DL\\geq\(1\-2\\epsilon\)n\.

The proof of[Proposition2](https://arxiv.org/html/2608.04243#Thmproposition2)relies on the following[lemma](https://arxiv.org/html/2608.04243#Thmlemma15)\.

###### Lemma 15\.

SupposeM≥2M\\geq 2and∥vi−vj∥≤D\\lVert v\_\{i\}\-v\_\{j\}\\rVert\\leq Dfor alli,j∈\[M\]i,j\\in\[M\]\. There exist\(x1,…,xn\)∈\[M\]n\(x\_\{1\},\\dotsc,x\_\{n\}\)\\in\[M\]^\{n\}and\(x1′,…,xn′\)∈\[M\]n\(x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\)\\in\[M\]^\{n\}such that

∥Att\(⟨q,kxj⟩,vxj\)j=1n−Att\(⟨q,kxj′⟩,vxj′\)j=1n∥≤Dn,\\lVert\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\}\-\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}^\{\\prime\}\}\\rangle,v\_\{x\_\{j\}^\{\\prime\}\}\)\_\{j=1\}^\{n\}\\rVert\\leq\\frac\{D\}\{n\},and at least one of the following inequalities hold:

min⁡\{x1,…,xn\}\\displaystyle\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}≠min⁡\{x1′,…,xn′\},\\displaystyle\\neq\\min\\\{x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\\\},max⁡\{x1,…,xn\}\\displaystyle\\max\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}≠max⁡\{x1′,…,xn′\}\.\\displaystyle\\neq\\max\\\{x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\\\}\.

###### Proof\.

Pick anyi,j∈\[M\]i,j\\in\[M\]withi<ji<j\. Supposeαi≤αj\\alpha\_\{i\}\\leq\\alpha\_\{j\}, whereαi:=exp⁡\(⟨q,ki⟩\)\\alpha\_\{i\}:=\\exp\\lparen\\langle q,k\_\{i\}\\rangle\\rparenandαj:=exp⁡\(⟨q,kj⟩\)\\alpha\_\{j\}:=\\exp\\lparen\\langle q,k\_\{j\}\\rangle\\rparen\. Set

\(x1,…,xn\)\\displaystyle\(x\_\{1\},\\dotsc,x\_\{n\}\):=\(i,j,…,j\),\\displaystyle:=\(i,j,\\dotsc,j\),\(x1′,…,xn′\)\\displaystyle\(x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\):=\(j,j,…,j\),\\displaystyle:=\(j,j,\\dotsc,j\),z\\displaystyle z:=Att\(⟨q,kxj⟩,vxj\)j=1n,\\displaystyle:=\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\},z′\\displaystyle z^\{\\prime\}:=Att\(⟨q,kxj′⟩,vxj′\)j=1n\.\\displaystyle:=\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}^\{\\prime\}\}\\rangle,v\_\{x\_\{j\}^\{\\prime\}\}\)\_\{j=1\}^\{n\}\.So we have

min⁡\{x1,…,xn\}≠min⁡\{x1′,…,xn′\}\.\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\\neq\\min\\\{x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\\\}\.Moreover,

z−z′\\displaystyle z\-z^\{\\prime\}=αi​vi\+\(n−1\)​αj​vjαi\+\(n−1\)​αj−vj\\displaystyle=\\frac\{\\alpha\_\{i\}v\_\{i\}\+\(n\-1\)\\alpha\_\{j\}v\_\{j\}\}\{\\alpha\_\{i\}\+\(n\-1\)\\alpha\_\{j\}\}\-v\_\{j\}=αiαi\+\(n−1\)​αj​\(vi−vj\)\\displaystyle=\\frac\{\\alpha\_\{i\}\}\{\\alpha\_\{i\}\+\(n\-1\)\\alpha\_\{j\}\}\(v\_\{i\}\-v\_\{j\}\)=11\+\(n−1\)​αj/αi​\(vi−vj\)\.\\displaystyle=\\frac\{1\}\{1\+\(n\-1\)\\alpha\_\{j\}/\\alpha\_\{i\}\}\(v\_\{i\}\-v\_\{j\}\)\.Sinceαj/αi≥1\\alpha\_\{j\}/\\alpha\_\{i\}\\geq 1and∥vi−vj∥≤D\\lVert v\_\{i\}\-v\_\{j\}\\rVert\\leq D, we have

∥z−z′∥=11\+\(n−1\)​αj/αi​∥vi−vj∥≤1n​∥vi−vj∥≤Dn\.\\lVert z\-z^\{\\prime\}\\rVert=\\frac\{1\}\{1\+\(n\-1\)\\alpha\_\{j\}/\\alpha\_\{i\}\}\\lVert v\_\{i\}\-v\_\{j\}\\rVert\\leq\\frac\{1\}\{n\}\\lVert v\_\{i\}\-v\_\{j\}\\rVert\\leq\\frac\{D\}\{n\}\.
Now instead supposeαi\>αj\\alpha\_\{i\}\>\\alpha\_\{j\}\. Set

\(x1,…,xn\)\\displaystyle\(x\_\{1\},\\dotsc,x\_\{n\}\):=\(i,…,i,j\),\\displaystyle:=\(i,\\dotsc,i,j\),\(x1′,…,xn′\)\\displaystyle\(x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\):=\(i,…,i,i\),\\displaystyle:=\(i,\\dotsc,i,i\),z\\displaystyle z:=Att\(⟨q,kxj⟩,vxj\)j=1n,\\displaystyle:=\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\},z′\\displaystyle z^\{\\prime\}:=Att\(⟨q,kxj′⟩,vxj′\)j=1n\.\\displaystyle:=\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}^\{\\prime\}\}\\rangle,v\_\{x\_\{j\}^\{\\prime\}\}\)\_\{j=1\}^\{n\}\.So we have

max⁡\{x1,…,xn\}≠max⁡\{x1′,…,xn′\}\.\\max\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\\neq\\max\\\{x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\\\}\.Moreover,

z−z′\\displaystyle z\-z^\{\\prime\}=\(n−1\)​αi​vi\+αj​vj\(n−1\)​αi\+αj−vi\\displaystyle=\\frac\{\(n\-1\)\\alpha\_\{i\}v\_\{i\}\+\\alpha\_\{j\}v\_\{j\}\}\{\(n\-1\)\\alpha\_\{i\}\+\\alpha\_\{j\}\}\-v\_\{i\}=αj\(n−1\)​αi\+αj​\(vj−vi\)\\displaystyle=\\frac\{\\alpha\_\{j\}\}\{\(n\-1\)\\alpha\_\{i\}\+\\alpha\_\{j\}\}\(v\_\{j\}\-v\_\{i\}\)=1\(n−1\)​αi/αj\+1​\(vj−vi\)\.\\displaystyle=\\frac\{1\}\{\(n\-1\)\\alpha\_\{i\}/\\alpha\_\{j\}\+1\}\(v\_\{j\}\-v\_\{i\}\)\.Sinceαi/αj\>1\\alpha\_\{i\}/\\alpha\_\{j\}\>1and∥vj−vi∥≤D\\lVert v\_\{j\}\-v\_\{i\}\\rVert\\leq D, we have

∥z−z′∥=1\(n−1\)​αi/αj\+1​∥vj−vi∥≤1n​∥vj−vi∥≤Dn\.∎\\lVert z\-z^\{\\prime\}\\rVert=\\frac\{1\}\{\(n\-1\)\\alpha\_\{i\}/\\alpha\_\{j\}\+1\}\\lVert v\_\{j\}\-v\_\{i\}\\rVert\\leq\\frac\{1\}\{n\}\\lVert v\_\{j\}\-v\_\{i\}\\rVert\\leq\\frac\{D\}\{n\}\.\\qed

###### Proof of[Proposition2](https://arxiv.org/html/2608.04243#Thmproposition2)\.

Fix\(x1,…,xn\),\(x1′,…,xn′\)∈\[M\]n\(x\_\{1\},\\dotsc,x\_\{n\}\),\(x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\)\\in\[M\]^\{n\}with the properties guaranteed in[Lemma15](https://arxiv.org/html/2608.04243#Thmlemma15), and let

z\\displaystyle z:=Att\(⟨q,kxj⟩,vxj\)j=1n,\\displaystyle:=\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}\}\\rangle,v\_\{x\_\{j\}\}\)\_\{j=1\}^\{n\},z′\\displaystyle z^\{\\prime\}:=Att\(⟨q,kxj′⟩,vxj′\)j=1n\.\\displaystyle:=\\operatorname\{Att\}\(\\langle q,k\_\{x\_\{j\}^\{\\prime\}\}\\rangle,v\_\{x\_\{j\}^\{\\prime\}\}\)\_\{j=1\}^\{n\}\.Suppose

min⁡\{x1,…,xn\}≠min⁡\{x1′,…,xn′\}\.\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\\neq\\min\\\{x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\\\}\.Then by the triangle inequality and the Lipschitz property ofgming^\{\\min\},

1=∥emin⁡\{x1,…,xn\}−emin⁡\{x1′,…,xn′\}∥∞\\displaystyle 1=\\lVert e\_\{\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\}\-e\_\{\\min\\\{x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\\\}\}\\rVert\_\{\\infty\}≤∥emin⁡\{x1,…,xn\}−gmin​\(z\)∥∞\\displaystyle\\leq\\lVert e\_\{\\min\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\}\-g^\{\\min\}\(z\)\\rVert\_\{\\infty\}\+∥gmin​\(z\)−gmin​\(z′\)∥∞\\displaystyle\\qquad\+\\lVert g^\{\\min\}\(z\)\-g^\{\\min\}\(z^\{\\prime\}\)\\rVert\_\{\\infty\}\+∥gmin​\(z′\)−emin⁡\{x1′,…,xn′\}∥∞\\displaystyle\\qquad\+\\lVert g^\{\\min\}\(z^\{\\prime\}\)\-e\_\{\\min\\\{x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\\\}\}\\rVert\_\{\\infty\}≤ϵ\+L​∥z−z′∥\+ϵ\\displaystyle\\leq\\epsilon\+L\\lVert z\-z^\{\\prime\}\\rVert\+\\epsilon≤2​ϵ\+D​Ln,\\displaystyle\\leq 2\\epsilon\+\\frac\{DL\}\{n\},so re\-arranging gives

\(1−2​ϵ\)​n≤D​L\.\(1\-2\\epsilon\)n\\leq DL\.An analogous argument handles the case whenmax⁡\{x1,…,xn\}≠max⁡\{x1′,…,xn′\}\\max\\\{x\_\{1\},\\dotsc,x\_\{n\}\\\}\\neq\\max\\\{x\_\{1\}^\{\\prime\},\\dotsc,x\_\{n\}^\{\\prime\}\\\}\. ∎