作为通用深度神经网络的 Transformer：精确编译、消除激活值之间乘积的代价，以及多智能体注意力聚类

# Transformers as Generic Deep Neural Networks: Exact Compilation, the Cost of Removing Activation–Activation Products, and Multi-Agent Attention Clustering
Source: [https://arxiv.org/html/2610.28958](https://arxiv.org/html/2610.28958)
Sergey SalishevAffiliation:St\. Petersburg State University, Saint Petersburg 199034, RussiaAffiliation:Corresponding author: s\.salischev@spbu\.ruZeev VolkovichAffiliation:Department of Software Engineering, Braude College of Engineering, Karmiel 2161002, Israel

###### Abstract

Transformers are deployed as a special model class\. Neural processing units \(NPU\) add dedicated operators for attention and normalization, and quantization relies on Transformer\-specific algorithms\. We show the computation does not force this\. Every Transformer block, with attention, LayerNorm and a GELU MLP, compiles exactly into a generic deep neural network built from fixed affine maps, routing and the square, sigmoid and inverse square root, plus GELU or its sigmoid approximation\. Without activation–activation products, every transform\-wise compilation adds at leastN2N^\{2\}scalar nonlinear evaluations per head for dense scores\. Keeping that one operation type removes this cost; its elementwise form, present on every surveyed NPU, suffices with the sigmoid and inverse square root\. For top\-kkattention with exchangeable tail scores, we prove that exact or conditional\-mean tail mass gives an unbiased, minimum\-mean\-square\-error estimate of the attention distribution, while tail drop is conditionally biased\. When queries or agents cluster, centroids choose the keys first, reducing the number of computed scores fromN2N^\{2\}toN​kNkper head\. On DeiT\-Tiny, MambaIRv2\-Light and Pythia\-70M the compiled models match their references with all keys, standard post\-training quantization applies, and the exact tail\-mass estimate beats tail dropping with half as many keys on DeiT\-Tiny and, fork≤8k\\leq 8, on Pythia\-70M\.

## Introduction

Transformers\[[1](https://arxiv.org/html/2610.28958#bib.bib1)\]are treated as a model class apart from the deep neural networks \(DNNs\) that accelerators and tools were first built for\. This view has two practical consequences\.

The first is hardware\. Accelerators built for convolutional networks run a fixed operator set and hand everything else to the host\. The Edge TPU compiler cuts the model at the first unsupported operation and runs the rest on the CPU\[[2](https://arxiv.org/html/2610.28958#bib.bib2)\]\. NVIDIA’s Jetson DLA has no matrix\-multiply layer\[[3](https://arxiv.org/html/2610.28958#bib.bib3)\]\. On phones, llm\.npu runs the linear layers on the NPU and keeps LayerNorm and attention on the CPU or GPU\[[4](https://arxiv.org/html/2610.28958#bib.bib4)\]\. Vendors answer with Transformer\-specific operators and units for attention, softmax and normalization\[[5](https://arxiv.org/html/2610.28958#bib.bib5),[6](https://arxiv.org/html/2610.28958#bib.bib6),[7](https://arxiv.org/html/2610.28958#bib.bib7)\]\.

The second is quantization\. Post\-training quantization \(PTQ\) of Transformers relies on dedicated algorithms\. Liu et al\. search quantization scales with a ranking\-aware objective\[[8](https://arxiv.org/html/2610.28958#bib.bib8)\], and PTQ4ViT adds twin\-uniform quantizers for the post\-softmax and post\-GELU activations\[[9](https://arxiv.org/html/2610.28958#bib.bib9)\]\. FQ\-ViT adds power\-of\-two factors for LayerNorm and a log\-integer softmax\[[10](https://arxiv.org/html/2610.28958#bib.bib10)\]\. RepQ\-ViT reparameterizes quantization scales\[[11](https://arxiv.org/html/2610.28958#bib.bib11)\], IGQ\-ViT groups channels per instance\[[12](https://arxiv.org/html/2610.28958#bib.bib12)\], I\-BERT replaces the nonlinearities by integer polynomials\[[13](https://arxiv.org/html/2610.28958#bib.bib13)\], and SmoothQuant moves activation outliers into the weights of language models\[[14](https://arxiv.org/html/2610.28958#bib.bib14)\]\.

We show that the computation does not force this split\. The argument has four steps\.

*Exact compilation\.*Every Transformer block, with LayerNorm, scaled dot\-product attention, softmax and a GELU MLP, compiles exactly into a generic DNN of fixed affine maps, scalar nonlinearities and routing, with no product of two activations \(Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1)\)\. We call it the strict graph\. Squares replace products, througha​b=12​\[\(a\+b\)2−a2−b2\]ab=\\tfrac\{1\}\{2\}\[\(a\+b\)^\{2\}\-a^\{2\}\-b^\{2\}\]where the squares of the factors are shared and through polarization otherwise, and no exponential or logarithm is needed: squares, the sigmoid and the inverse square root suffice, with GELU or its approximationx​σ​\(1\.702​x\)x\\,\\sigma\(1\.702x\)as the MLP activation\.

*The cost of strictness\.*Since the strict graph has no dedicated layers, standard DNN tools apply to it\. But removing products of two activations has a price\. For free arguments, any compilation without them adds at leastN2N^\{2\}scalar nonlinear evaluations per head atQ​K⊤QK^\{\\top\}andN​dNdatP​VPV, whatever the scalar functions, depth or width \(Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)\)\.

*One more operation type\.*Adding activation–activation products removes the price\. Their elementwise form, the Hadamard product, is on every NPU we survey, and it suffices: with it, a block needs only the sigmoid and the inverse square root besides its MLP activation, and only softmax adds work,2​N22N^\{2\}evaluations per head \(Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1)\)\. With the exponential and the reciprocal it adds no pointwise work \(Proposition[2](https://arxiv.org/html/2610.28958#Thmproposition2)\), and with matrix multiplication of two activations the extended compilation adds no work of either kind \(Theorem[3](https://arxiv.org/html/2610.28958#Thmtheorem3)\)\. On a GPU, fork≤64k\\leq 64, the Hadamard and strict graphs run at1\.01\.0to1\.31\.3and1\.21\.2to1\.51\.5times the latency of this extended graph\. Theorems[2](https://arxiv.org/html/2610.28958#Thmtheorem2)and[3](https://arxiv.org/html/2610.28958#Thmtheorem3)make this operation type necessary and sufficient for compilation without added pointwise work\. Practice already uses this operation set\. ONNX defines LayerNormalization and Softmax as functions over it\[[15](https://arxiv.org/html/2610.28958#bib.bib15),[16](https://arxiv.org/html/2610.28958#bib.bib16)\], current NPUs expose it\[[6](https://arxiv.org/html/2610.28958#bib.bib6),[17](https://arxiv.org/html/2610.28958#bib.bib17),[18](https://arxiv.org/html/2610.28958#bib.bib18)\], and convolutional networks with squeeze\-and\-excitation gating already use the elementwise product\[[19](https://arxiv.org/html/2610.28958#bib.bib19),[20](https://arxiv.org/html/2610.28958#bib.bib20)\]\.

*Clustered attention\.*The attention weights of a query cluster on a few keys\[[21](https://arxiv.org/html/2610.28958#bib.bib21),[22](https://arxiv.org/html/2610.28958#bib.bib22),[23](https://arxiv.org/html/2610.28958#bib.bib23)\]when its scores have a gap \(Lemma[1](https://arxiv.org/html/2610.28958#Thmlemma1)\)\. Queries cluster too\[[24](https://arxiv.org/html/2610.28958#bib.bib24),[25](https://arxiv.org/html/2610.28958#bib.bib25)\], and queries close to one point share their top keys \(Lemma[2](https://arxiv.org/html/2610.28958#Thmlemma2)\)\. Top\-kkattention keeps thekklargest scores of each query\[[21](https://arxiv.org/html/2610.28958#bib.bib21),[22](https://arxiv.org/html/2610.28958#bib.bib22)\], the topological rule of bird flocks\[[26](https://arxiv.org/html/2610.28958#bib.bib26)\]\. We add an estimate of the omitted probability mass, spread uniformly over the dropped keys\. For exchangeable tail scores, exact or conditional\-mean tail mass gives the unbiased, minimum\-mean\-square\-error attention\-distribution estimate; tail drop is conditionally biased \(Theorem[4](https://arxiv.org/html/2610.28958#Thmtheorem4)\)\. Centroids of the query clusters\[[25](https://arxiv.org/html/2610.28958#bib.bib25)\]choose the keys before the scores, so the strict graph forms onlyN​kNkscores per head \(Corollary[2](https://arxiv.org/html/2610.28958#Thmcorollary2), Proposition[5](https://arxiv.org/html/2610.28958#Thmproposition5)\)\. One step of the Motsch–Tadmor flocking model is one attention head \(Proposition[6](https://arxiv.org/html/2610.28958#Thmproposition6)\)\.

We test the compilation on three model families: DeiT\-Tiny\[[27](https://arxiv.org/html/2610.28958#bib.bib27)\]for image classification on Oxford\-IIIT Pet\[[28](https://arxiv.org/html/2610.28958#bib.bib28)\]and ImageNet\-1k\[[29](https://arxiv.org/html/2610.28958#bib.bib29)\], MambaIRv2\-Light\[[30](https://arxiv.org/html/2610.28958#bib.bib30)\]for super\-resolution, and Pythia\-70M\[[31](https://arxiv.org/html/2610.28958#bib.bib31)\]for language modeling\.

*Related work\.*Universal approximation gives some network within each error on a compact set\[[32](https://arxiv.org/html/2610.28958#bib.bib32),[33](https://arxiv.org/html/2610.28958#bib.bib33)\]\. Forming products from squares is classical: tables of quarter\-squares multiply by polarization\[[34](https://arxiv.org/html/2610.28958#bib.bib34)\], Winograd’s inner product forms the self\-terms of each row once and halves the products of a matrix multiplication\[[35](https://arxiv.org/html/2610.28958#bib.bib35)\], and expressivity proofs for ReLU networks usea​b=12​\[\(a\+b\)2−a2−b2\]ab=\\tfrac\{1\}\{2\}\[\(a\+b\)^\{2\}\-a^\{2\}\-b^\{2\}\]\[[36](https://arxiv.org/html/2610.28958#bib.bib36)\]\. Compilers such as Glow map a model onto the operators a device provides\[[37](https://arxiv.org/html/2610.28958#bib.bib37)\]\. Privacy\-preserving inference decomposes attention, softmax and LayerNorm into primitive operations for cryptographic protocols, usually with polynomial approximations\[[38](https://arxiv.org/html/2610.28958#bib.bib38),[39](https://arxiv.org/html/2610.28958#bib.bib39),[40](https://arxiv.org/html/2610.28958#bib.bib40)\]\. Multiplication\-free training replaces every product by an approximate piecewise\-affine operation and trains on that arithmetic\[[41](https://arxiv.org/html/2610.28958#bib.bib41)\]\. Training\-time alternatives simplify LayerNorm\[[42](https://arxiv.org/html/2610.28958#bib.bib42)\]or remove it\[[43](https://arxiv.org/html/2610.28958#bib.bib43),[44](https://arxiv.org/html/2610.28958#bib.bib44)\]\. Top\-kkattention saves memory on long contexts\[[21](https://arxiv.org/html/2610.28958#bib.bib21),[22](https://arxiv.org/html/2610.28958#bib.bib22),[23](https://arxiv.org/html/2610.28958#bib.bib23)\], usually by renormalizing the kept scores\. Scatterbrain adds a low\-rank estimate of the non\-selected attention to a sparse one\[[45](https://arxiv.org/html/2610.28958#bib.bib45)\], Combiner attends to the rest of the sequence through region summaries\[[46](https://arxiv.org/html/2610.28958#bib.bib46)\], and MagicPIG replaces top\-kkselection by sampling to avoid its bias\[[47](https://arxiv.org/html/2610.28958#bib.bib47)\]\. Clustered attention chooses the kept keys by query centroids and gives the other keys the weights of the centroid\[[25](https://arxiv.org/html/2610.28958#bib.bib25)\]; we use its key selection with calibrated centroids\. Lookup tables, piecewise\-linear units and integer approximations implement scalar nonlinearities in hardware\[[48](https://arxiv.org/html/2610.28958#bib.bib48),[49](https://arxiv.org/html/2610.28958#bib.bib49),[7](https://arxiv.org/html/2610.28958#bib.bib7)\]\.

*What is new\.*Unlike universal approximation, the compiled graph is exact on all inputs, reuses the trained weights and has a known size\. Unlike compilers and privacy\-preserving decompositions, we ask which small operator set expresses a whole block exactly\. New are the lower bound that prices product\-free compilation and the extended construction that removes the price\. Unlike multiplication\-free training, we compile a trained model, keep LayerNorm, and remove only products of two activations\. Our tail\-mass estimate is simpler than those of Scatterbrain, Combiner and clustered attention\. It is a fixed affine map for a constant mass\. For clustered queries, new are the cost bounds for the selected scores and the flocking step as one attention head\.

## Results

### Theory

All proofs are in Methods\.

#### A generic DNN vocabulary

We describe a DNN by the types of operations its nodes perform\. Three types cover plain convolutional networks and multilayer perceptrons\.

###### Definition 1\(Strict basis\)\.

Fix a setΦ\\Phiof scalar functions\. A graph over the strict basisℬstrict​\(Φ\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\)is a finite acyclic graph whose nodes are of three types:

1. 1\.*weight–activation contraction*: a fixed affine mapx↦A​x\+bx\\mapsto Ax\+b, whereAAandbbare parameters of the graph and do not depend on the input;
2. 2\.*unary map*:x↦ϕ⁡\(x\)x\\mapsto\\phi\(x\)applied entrywise, withϕ∈Φ\\phi\\in\\Phi;
3. 3\.*routing*: copy, reshape, permutation, concatenation, broadcast, masking, and selection of entries by comparisons of computed values \(max,TopK\\mathrm\{TopK\}, gather\), with a fixed tie\-breaking rule\.

No node multiplies two quantities that both depend on the input; a square is a unary map\. For everyΦ\\Phi, we callℬstrict​\(Φ\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\)a*product\-free*basis and its graphs product\-free graphs\.

Convolutions, fully connected layers, batch normalization at inference, residual sums and average pooling are fixed affine maps; max pooling is routing\. ReLU, GELU and other activations are unary maps\. Gating, as in squeeze\-and\-excitation blocks\[[19](https://arxiv.org/html/2610.28958#bib.bib19)\], multiplies two activations and is not in this basis\. The setΦ\\Phiis a parameter\. Shifts such asx\+εx\+\\varepsilonand scalings such asx/2x/2belong to the preceding affine node, so a unary set needs only the shape of each function\.

###### Definition 2\(Strict unary set\)\.

Φstrict=\{\(⋅\)2,σ,\(⋅\)−1/2,GELU\}\\Phi\_\{\\mathrm\{strict\}\}=\\\{\(\\cdot\)^\{2\},\\ \\sigma,\\ \(\\cdot\)^\{\-1/2\},\\ \\mathrm\{GELU\}\\\}, withσ⁡\(t\)=1/\(1\+e−t\)\\sigma\(t\)=1/\(1\+e^\{\-t\}\)\.

Each function has one role\. The square forms second moments and products:a​b=12​\[\(a\+b\)2−a2−b2\]ab=\\tfrac\{1\}\{2\}\[\(a\+b\)^\{2\}\-a^\{2\}\-b^\{2\}\]where the squares of the factors are shared across products, as for the rows ofQQ,KKandVVand in LayerNorm, and polarization,a​b=14​\[\(a\+b\)2−\(a−b\)2\]ab=\\tfrac\{1\}\{4\}\[\(a\+b\)^\{2\}\-\(a\-b\)^\{2\}\], for an isolated product\. The sigmoid gives the exponential,et=σ⁡\(t\)/σ⁡\(−t\)e^\{t\}=\\sigma\(t\)/\\sigma\(\-t\)\. The inverse square root normalizes LayerNorm and, squared, gives the reciprocal,1/x=\(x−1/2\)21/x=\(x^\{\-1/2\}\)^\{2\}forx\>0x\>0\.GELU\\mathrm\{GELU\}is the MLP activation \(Definition[3](https://arxiv.org/html/2610.28958#Thmdefinition3)\)\. The set has no exponential and no logarithm\.

###### Definition 3\(Transform sets\)\.

The Transformer transform set is

𝒯Tr=\{Aff,LN,Score,softmax,Mix,MLPGELU\},\\mathcal\{T\}\_\{\\mathrm\{Tr\}\}=\\\{\\mathrm\{Aff\},\\ \\mathrm\{LN\},\\ \\mathrm\{Score\},\\ \\mathrm\{softmax\},\\ \\mathrm\{Mix\},\\ \\mathrm\{MLP\}\_\{\\mathrm\{GELU\}\}\\\},where

Aff⁡\(x\)\\displaystyle\\mathrm\{Aff\}\(x\)=A​x\+b,\\displaystyle=Ax\+b,LN⁡\(x\)\\displaystyle\\mathrm\{LN\}\(x\)=β\+γ⊙x−mean⁡\(x\)Var⁡\(x\)\+ε,\\displaystyle=\\beta\+\\gamma\\odot\\frac\{x\-\\mathrm\{mean\}\(x\)\}\{\\sqrt\{\\mathrm\{Var\}\(x\)\+\\varepsilon\}\},Score⁡\(Q,K\)\\displaystyle\\mathrm\{Score\}\(Q,K\)=Q​K⊤/d,\\displaystyle=QK^\{\\top\}/\\sqrt\{d\},Mix⁡\(P,V\)\\displaystyle\\mathrm\{Mix\}\(P,V\)=P​V,\\displaystyle=PV,MLPGELU​\(x\)\\displaystyle\\mathrm\{MLP\}\_\{\\mathrm\{GELU\}\}\(x\)=A2​GELU​\(A1​x\+b1\)\+b2,\\displaystyle=A\_\{2\}\\mathrm\{GELU\}\(A\_\{1\}x\+b\_\{1\}\)\+b\_\{2\},GELU⁡\(x\)\\displaystyle\\mathrm\{GELU\}\(x\)=x2​\(1\+erf⁡\(x/2\)\),\\displaystyle=\\tfrac\{x\}\{2\}\\bigl\(1\+\\operatorname\{erf\}\(x/\\sqrt\{2\}\)\\bigr\),andsoftmax\\mathrm\{softmax\}acts on each row of scores\. A model may use the approximationGELU⁡\(x\)≈x​σ​\(1\.702​x\)\\mathrm\{GELU\}\(x\)\\approx x\\,\\sigma\(1\.702x\)\[[50](https://arxiv.org/html/2610.28958#bib.bib50)\]instead, which changes the model\. ThenGELU\\mathrm\{GELU\}is no longer a basic operation: it is omitted from every unary set, and the sigmoid is added where missing\. HereVar⁡\(x\)=meani​\[\(xi−mean⁡\(x\)\)2\]\\mathrm\{Var\}\(x\)=\\mathrm\{mean\}\_\{i\}\[\(x\_\{i\}\-\\mathrm\{mean\}\(x\)\)^\{2\}\],ε\>0\\varepsilon\>0andA,b,β,γ,A1,b1,A2,b2A,b,\\beta,\\gamma,A\_\{1\},b\_\{1\},A\_\{2\},b\_\{2\}are fixed parameters, and one attention head hasNNtokens, head dimensiondd,Q,K,V∈ℝN×dQ,K,V\\in\\mathbb\{R\}^\{N\\times d\}andP∈ℝN×NP\\in\\mathbb\{R\}^\{N\\times N\}\.

A compiled graph serves a fixed context capacityNN, and the construction gives one graph for eachNN\. Shorter inputs are padded and masked, and causal models use the causal mask\. Masks are fixed routing and affine maps\.

#### Every Transformer block compiles exactly

###### Theorem 1\(Exact compilation into the strict basis\)\.

Every finite Transformer block composed of transforms in𝒯Tr\\mathcal\{T\}\_\{\\mathrm\{Tr\}\}is computed exactly by a finite graph overℬstrict​\(Φstrict\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\_\{\\mathrm\{strict\}\}\)\.

We call the graph of Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1)the*strict graph*\. A compilation is*transform\-wise*when it replaces each transform of the block by its own graph that computes that transform exactly; the graphs then compose\. The strict graph is transform\-wise: Lemmas[3](https://arxiv.org/html/2610.28958#Thmlemma3)–[6](https://arxiv.org/html/2610.28958#Thmlemma6)in Methods give the graph of each transform\.

#### Strict compilation pays an unavoidable pointwise cost

A multiply–accumulate \(MAC\) array computes products of matrices and reuses each loaded number many times\. A unary map takes one number and returns one, so it runs on a separate, slower scalar, vector or lookup\-table unit\. We count the two kinds of work separately\.

###### Definition 4\(Pointwise, contraction and added work\)\.

For a graphGG, the pointwise workPW⁡\(G\)\\mathrm\{PW\}\(G\)is the number of scalar evaluations of unary maps in one forward pass; it counts evaluations, not nodes\. The contraction workMAC⁡\(G\)\\mathrm\{MAC\}\(G\)is the number of multiply–accumulate steps in its fixed affine nodes and in its products of two activations\. The*source graph*of a transformTTis the graph of its defining formula in Definition[3](https://arxiv.org/html/2610.28958#Thmdefinition3), with each product of two activations as one product node;PW⁡\(T\)\\mathrm\{PW\}\(T\)andMAC⁡\(T\)\\mathrm\{MAC\}\(T\)are its work\.Score\\mathrm\{Score\}is one product node withPW=0\\mathrm\{PW\}=0andMAC=N2​d\\mathrm\{MAC\}=N^\{2\}dper head, LayerNorm forms its second moment with a product node and pays one inverse square root per token, and softmax pays one exponential per entry and one reciprocal per row\. If a transform\-wise compilation replacesTTby the graphGTG\_\{T\}, its added work isΔ​PW​\(T\)=PW⁡\(GT\)−PW⁡\(T\)\\Delta\\mathrm\{PW\}\(T\)=\\mathrm\{PW\}\(G\_\{T\}\)\-\\mathrm\{PW\}\(T\)andΔ​MAC​\(T\)=MAC⁡\(GT\)−MAC⁡\(T\)\\Delta\\mathrm\{MAC\}\(T\)=\\mathrm\{MAC\}\(G\_\{T\}\)\-\\mathrm\{MAC\}\(T\)\.

###### Theorem 2\(Lower bound for product\-free compilation\)\.

Fix one attention head and any setΦ\\Phiof scalar functions, and let the entries ofQQ,KK,PPandVVrange freely overℝ\\mathbb\{R\}\. Every product\-free graph that computesScore=Q​K⊤/d\\mathrm\{Score\}=QK^\{\\top\}/\\sqrt\{d\}exactly hasPW≥N2\\mathrm\{PW\}\\geq N^\{2\}, and every product\-free graph that computesMix=P​V\\mathrm\{Mix\}=PVexactly hasPW≥N​d\\mathrm\{PW\}\\geq Nd\.

The source graphs ofScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}make no unary evaluation, so the bounds hold for the added workΔ​PW\\Delta\\mathrm\{PW\}\. They hold for every depth, width and choice of affine coefficients, and they count evaluations, so fusing nodes does not lower them\. On inputs where its routing is fixed, a product\-free graph is an affine function of its unary outputs \(Methods, Lemma[9](https://arxiv.org/html/2610.28958#Thmlemma9)\)\. It therefore needs at least as many unary evaluations as its target has coordinates that stay linearly independent modulo affine functions; forScore\\mathrm\{Score\}these are allN2N^\{2\}entries\.

The strict graph paysN2​d\+2​N​dN^\{2\}d\+2Ndunary evaluations per head inScore\\mathrm\{Score\}andN2​d\+N2\+N​dN^\{2\}d\+N^\{2\}\+NdinMix\\mathrm\{Mix\}, a factord\+2​d/Nd\+2d/Nabove the bound of Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)forScore\\mathrm\{Score\}andN\+N/d\+1N\+N/d\+1above it forMix\\mathrm\{Mix\}\. Supplementary Section S1 shows how far the bound of Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)can be raised\.

For one DeiT\-Tiny block with dense attention \(Table[1](https://arxiv.org/html/2610.28958#Sx2.T1)\), the strict graph makes6161times the unary evaluations of the source block, and92%92\\%of them fall inScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}\.

Table 1:Pointwise work per DeiT\-Tiny block\.Unary evaluations per instance of each transform;N=197N=197tokens,h=3h=3heads of dimensiond=64d=64, MLP width4​h​d4hd\. Source: the source graph \(Definition[4](https://arxiv.org/html/2610.28958#Thmdefinition4)\), with GELU and dense attention\. Bound: Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)for dense scores, Corollary[2](https://arxiv.org/html/2610.28958#Thmcorollary2)for thekkrouted scores\. Strict: Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1); routed: Proposition[5](https://arxiv.org/html/2610.28958#Thmproposition5), withk=16k=16in the DeiT\-Tiny rows\. Hadamard: Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1)\. Extended: Theorem[3](https://arxiv.org/html/2610.28958#Thmtheorem3)\. Block totals count both LayerNorms\.
#### Activation–activation products remove the cost

Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)names the missing operation type: the product of two activations\. Every NPU we survey provides it as an elementwise product, together with the sigmoid \(Supplementary Table[S1](https://arxiv.org/html/2610.28958#Sx8.T1)\)\.

###### Definition 5\(Hadamard basis\)\.

The Hadamard basisℬ⊙​\(Φ\)\\mathcal\{B\}\_\{\\odot\}\(\\Phi\)has the three node types ofℬstrict​\(Φ\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\)and a fourth, the*Hadamard product*a⊙ba\\odot bof two activations with broadcasting\.

###### Definition 6\(Hadamard unary set\)\.

Φ⊙=\{σ,\(⋅\)−1/2,GELU\}\\Phi\_\{\\odot\}=\\\{\\sigma,\\ \(\\cdot\)^\{\-1/2\},\\ \\mathrm\{GELU\}\\\}\.

With the Hadamard product, the square isx⊙xx\\odot x, the exponential iset=σ\(t\)⊙\(σ\(−t\)−1/2⊙σ\(−t\)−1/2\)e^\{t\}=\\sigma\(t\)\\odot\\bigl\(\\sigma\(\-t\)^\{\-1/2\}\\odot\\sigma\(\-t\)^\{\-1/2\}\\bigr\), and the reciprocal isx−1/2⊙x−1/2x^\{\-1/2\}\\odot x^\{\-1/2\}\.

###### Proposition 1\(Sigmoid and inverse square root suffice with the Hadamard product\)\.

Every finite Transformer block over𝒯Tr\\mathcal\{T\}\_\{\\mathrm\{Tr\}\}is computed exactly by a finite graph overℬ⊙​\(Φ⊙\)\\mathcal\{B\}\_\{\\odot\}\(\\Phi\_\{\\odot\}\)in which softmax addsΔ​PW=2​N2\\Delta\\mathrm\{PW\}=2N^\{2\}per head and every other transform addsΔ​PW=0\\Delta\\mathrm\{PW\}=0\.

We call this graph the*Hadamard graph*\. Its products addΔ​MAC≤N2​d\\Delta\\mathrm\{MAC\}\\leq N^\{2\}dper head toScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}and2​N2\+N2N^\{2\}\+Nto softmax\. For one DeiT\-Tiny block it makes5\.02×1055\.02\\times 10^\{5\}unary evaluations, against1\.64×1071\.64\\times 10^\{7\}for the strict graph \(Table[1](https://arxiv.org/html/2610.28958#Sx2.T1)\)\.

The2​N22N^\{2\}evaluations of softmax come from building the exponential from sigmoids\. With the exponential and the reciprocal as unary maps they vanish\.

###### Definition 7\(Extended unary set\)\.

Φext=\{exp,\(⋅\)−1,\(⋅\)−1/2,GELU\}\\Phi\_\{\\mathrm\{ext\}\}=\\\{\\exp,\\ \(\\cdot\)^\{\-1\},\\ \(\\cdot\)^\{\-1/2\},\\ \\mathrm\{GELU\}\\\}\.

Φext\\Phi\_\{\\mathrm\{ext\}\}is the set of scalar functions in the defining formulas of𝒯Tr\\mathcal\{T\}\_\{\\mathrm\{Tr\}\}: the exponential and the reciprocal of softmax, the inverse square root of LayerNorm and the MLP activation\.

###### Proposition 2\(The Hadamard product suffices\)\.

Every finite Transformer block over𝒯Tr\\mathcal\{T\}\_\{\\mathrm\{Tr\}\}is computed exactly by a finite graph overℬ⊙​\(Φext\)\\mathcal\{B\}\_\{\\odot\}\(\\Phi\_\{\\mathrm\{ext\}\}\)withΔ​PW​\(T\)=0\\Delta\\mathrm\{PW\}\(T\)=0for every transformTT\. ForScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}a separate reduction node addsΔ​MAC≤N2​d\\Delta\\mathrm\{MAC\}\\leq N^\{2\}dper head; for every other transformΔ​MAC​\(T\)=0\\Delta\\mathrm\{MAC\}\(T\)=0\.

Matrix multiplication of two activations keeps theN2​dN^\{2\}dproducts ofQ​K⊤QK^\{\\top\}andP​VPV, which a Hadamard product writes to memory, inside the MAC array \(Supplementary Section S3\)\.

###### Definition 8\(Extended basis\)\.

The extended basisℬext​\(Φ\)\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\(\\Phi\)adds toℬ⊙​\(Φ\)\\mathcal\{B\}\_\{\\odot\}\(\\Phi\)matrix multiplication \(MatMul\) and batched matrix multiplication \(BMM\) of two activations\. With⊙\\odotthey form the*activation–activation products*\. For a commonΦ\\Phi,ℬstrict​\(Φ\)⊂ℬ⊙​\(Φ\)⊂ℬext​\(Φ\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\)\\subset\\mathcal\{B\}\_\{\\odot\}\(\\Phi\)\\subset\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\(\\Phi\)\.

###### Theorem 3\(Exact compilation with no added work\)\.

Every finite Transformer block over𝒯Tr\\mathcal\{T\}\_\{\\mathrm\{Tr\}\}is computed exactly by a finite graph overℬext​\(Φext\)\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\(\\Phi\_\{\\mathrm\{ext\}\}\), and this compilation hasΔ​PW​\(T\)=Δ​MAC​\(T\)=0\\Delta\\mathrm\{PW\}\(T\)=\\Delta\\mathrm\{MAC\}\(T\)=0for every transformTT\.

We call the graph of Theorem[3](https://arxiv.org/html/2610.28958#Thmtheorem3)the*extended graph*\. It is the source graph of each transform \(Definition[4](https://arxiv.org/html/2610.28958#Thmdefinition4)\), so it adds no work:Q​K⊤QK^\{\\top\}andP​VPVstay one matrix\-multiplication node each, withN2​dN^\{2\}dmultiply–accumulate steps per head and no unary evaluation\. Theorems[2](https://arxiv.org/html/2610.28958#Thmtheorem2)and[3](https://arxiv.org/html/2610.28958#Thmtheorem3)together make activation–activation products necessary and sufficient for a transform\-wise compilation that adds no pointwise work\.

To turn the bound of Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)into time, letRmacR\_\{\\mathrm\{mac\}\}andRpwR\_\{\\mathrm\{pw\}\}be the throughputs of the MAC array and the pointwise unit, andκ=Rmac/Rpw\\kappa=R\_\{\\mathrm\{mac\}\}/R\_\{\\mathrm\{pw\}\}\.

###### Corollary 1\(Time separation\)\.

Fix anhh\-head block\. Assume that unary maps run only on the pointwise unit, at rate at mostRpwR\_\{\\mathrm\{pw\}\}, and that the extended graph runsScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}on the MAC array at rateRmacR\_\{\\mathrm\{mac\}\}\. In every transform\-wise product\-free compilation, theScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}subgraphs take at leasth⁡\(N2\+N​d\)/Rpwh\(N^\{2\}\+Nd\)/R\_\{\\mathrm\{pw\}\}; in the extended graph they take2​h​N2​d/Rmac2hN^\{2\}d/R\_\{\\mathrm\{mac\}\}\. The first time is longer wheneverκ\>2​N​d/\(N\+d\)\\kappa\>2Nd/\(N\+d\), in particular wheneverκ≥2​d\\kappa\\geq 2d\.

The strict graph makes more than2​h​N2​d2hN^\{2\}dunary evaluations inScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}, so on them it is at leastκ\\kappatimes slower than the extended graph\. For DeiT\-Tiny \(N=197N=197,d=64d=64\) the threshold2​N​d/\(N\+d\)2Nd/\(N\+d\)is96\.696\.6\. The extended basis maps onto a current NPU without a Transformer\-specific unit; Figure[1](https://arxiv.org/html/2610.28958#Sx2.F1)shows the unit that runs each node\.

Transformer blockLN,Q​K⊤QK^\{\\top\},softmax,P​VPV,GELU\-MLP,top\-kkStrict graph\(Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1)\)adds about2​h​N2​d2hN^\{2\}dsquaresQ​K⊤,P​VQK^\{\\top\},PVHadamard graph\(Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1)\)adds2​h​N22hN^\{2\}unarymaps in softmaxExtended graph\(Theorem[3](https://arxiv.org/html/2610.28958#Thmtheorem3)\)adds no workMAC arrayLUT / PWL unitRoutingfixed affine mapssquare, sigmoid,inverse square root,GELU∗routing,TopK\\mathrm\{TopK\}fixed affine maps,Hadamard⊙\\odotsigmoid,inverse square root,GELU∗routing,TopK\\mathrm\{TopK\}fixed affine maps,Q​K⊤QK^\{\\top\},P​VPV,Hadamard⊙\\odotexponential, reciprocal,inverse square root,GELU∗or sigmoidrouting,TopK\\mathrm\{TopK\}Figure 1:Three exact compilations of a Transformer block\.Each row lists the nodes of one graph under the NPU unit that runs them;NNtokens,hhheads of dimensiondd\.∗if used in the source graph\.
#### Attention weights cluster on a few keys

Fix one queryqiq\_\{i\}, the keysk1,…,kNk\_\{1\},\\dots,k\_\{N\}and the valuesv1,…,vNv\_\{1\},\\dots,v\_\{N\}, the rows ofKKandVV, and1≤k<N1\\leq k<N\. Under a mask,NNcounts the valid keys of the row\. The scores aresj=qi⋅kj/ds\_\{j\}=q\_\{i\}\\cdot k\_\{j\}/\\sqrt\{d\}, sorted ass\(1\)≥⋯≥s\(N\)s\_\{\(1\)\}\\geq\\dots\\geq s\_\{\(N\)\}, the attention distribution isπ=softmax⁡\(s\)\\pi=\\mathrm\{softmax\}\(s\), and the attention output iso=∑jπj​vjo=\\sum\_\{j\}\\pi\_\{j\}v\_\{j\}\. Top\-kkattention keeps the supportI=TopK⁡\(s,k\)I=\\mathrm\{TopK\}\(s,k\)and drops the otherm=N−km=N\-kkeys, the setJJ\. The tail massτ=∑j∈Jπj\\tau=\\sum\_\{j\\in J\}\\pi\_\{j\}is the attention outsideII, andΔk=s\(k\)−s\(k\+1\)\\Delta\_\{k\}=s\_\{\(k\)\}\-s\_\{\(k\+1\)\}is the score gap\. The attention weights cluster onIIwhenΔk\\Delta\_\{k\}is large\. Queries cluster too\.

###### Lemma 1\(Score gap\)\.

τ≤mk​e−Δk\\tau\\leq\\frac\{m\}\{k\}\\,e^\{\-\\Delta\_\{k\}\}\.

###### Lemma 2\(Shared support\)\.

Letc∈ℝdc\\in\\mathbb\{R\}^\{d\}andρ≥0\\rho\\geq 0\. If‖qi−c‖≤ρ\\\|q\_\{i\}\-c\\\|\\leq\\rhoandΔk\>2​ρ​maxj​‖kj‖/d\\Delta\_\{k\}\>2\\rho\\max\_\{j\}\\\|k\_\{j\}\\\|/\\sqrt\{d\}, the scoresc⋅kj/dc\\cdot k\_\{j\}/\\sqrt\{d\}have the same topkkkeysIIasqiq\_\{i\}\.

By Lemma[2](https://arxiv.org/html/2610.28958#Thmlemma2), queries withinρ\\rhoof one pointccshare their topkkkeys when each meets the gap condition, and by Lemma[1](https://arxiv.org/html/2610.28958#Thmlemma1)each of them puts at mostmk​e−Δk\\frac\{m\}\{k\}e^\{\-\\Delta\_\{k\}\}of its attention outside these keys\.

#### Top\-kkattention with a tail\-mass estimate

The softmax over the kept scores,π~j=exp⁡\(sj\)/∑l∈Iexp⁡\(sl\)\\tilde\{\\pi\}\_\{j\}=\\exp\(s\_\{j\}\)/\\sum\_\{l\\in I\}\\exp\(s\_\{l\}\)forj∈Ij\\in I, needs onlysIs\_\{I\}\. The dense distribution onIIisπj=\(1−τ\)​π~j\\pi\_\{j\}=\(1\-\\tau\)\\tilde\{\\pi\}\_\{j\}\. Writea=∑j∈Iπ~j​vja=\\sum\_\{j\\in I\}\\tilde\{\\pi\}\_\{j\}v\_\{j\}for the mean of the kept values underπ~\\tilde\{\\pi\},u¯=1m​∑j∈Jvj\\bar\{u\}=\\frac\{1\}\{m\}\\sum\_\{j\\in J\}v\_\{j\}for the plain mean of the dropped values, andb=1τ​∑j∈Jπj​vjb=\\frac\{1\}\{\\tau\}\\sum\_\{j\\in J\}\\pi\_\{j\}v\_\{j\}for their mean underπ\\pi;τ\>0\\tau\>0since every softmax weight is positive\. Theno=\(1−τ\)​a\+τ​bo=\(1\-\\tau\)a\+\\tau b\.

###### Definition 9\(Tail\-mass top\-kkattention\)\.

For a tail massq∈\[0,1\]q\\in\[0,1\], the estimatep^\\hat\{p\}ofπ\\piand the outputo^\\hat\{o\}are

p^j=\(1−q\)​π~j\(j∈I\),p^j=qm\(j∈J\),o^=\(1−q\)​a\+q​u¯\.\\hat\{p\}\_\{j\}=\(1\-q\)\\,\\tilde\{\\pi\}\_\{j\}\\ \\ \(j\\in I\),\\qquad\\hat\{p\}\_\{j\}=\\frac\{q\}\{m\}\\ \\ \(j\\in J\),\\qquad\\hat\{o\}=\(1\-q\)\\,a\+q\\,\\bar\{u\}\.*Calibrated*mode uses one constantqqper block, the mean tail mass of the reference model over calibration data\.*Exact*mode usesq=τq=\\tau\.*Tail drop*, the usual top\-kkattention, usesq=0q=0\. Fork=0k=0,I=∅I=\\varnothing,m=Nm=Nandq=1q=1, sop^j=1/N\\hat\{p\}\_\{j\}=1/Nando^\\hat\{o\}is the mean of the values; calibrated and exact mode coincide\. Fork≥Nk\\geq Nthe map is dense attention\.

The sparse transform set𝒯k,q\\mathcal\{T\}\_\{k,q\}is𝒯Tr\\mathcal\{T\}\_\{\\mathrm\{Tr\}\}with softmax and value mixing replaced by this map\. This changes the model\. Its source graph, used to count work, computeso^\\hat\{o\}in the all\-values form

o^=∑j∈I\(p^j−qm\)​vj\+qm​∑j=1Nvj,\\hat\{o\}=\\sum\_\{j\\in I\}\\Bigl\(\\hat\{p\}\_\{j\}\-\\frac\{q\}\{m\}\\Bigr\)v\_\{j\}\+\\frac\{q\}\{m\}\\sum\_\{j=1\}^\{N\}v\_\{j\},\(1\)which reads only the kept values and the sum of all values\. Value mixing then costsN​k​dNkdmultiply–accumulate steps per head instead ofN2​dN^\{2\}d, plus the sum of all values, kept as a prefix sum under a causal mask\. Exact mode also forms allN2N^\{2\}scores for the dense normalizer\.

###### Proposition 3\(Sparse attention compiles exactly\)\.

Every finite block over𝒯k,q\\mathcal\{T\}\_\{k,q\}is computed exactly by a finite graph overℬstrict​\(Φstrict\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\_\{\\mathrm\{strict\}\}\), and by a finite graph overℬext​\(Φext\)\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\(\\Phi\_\{\\mathrm\{ext\}\}\)withΔ​PW​\(T\)=Δ​MAC​\(T\)=0\\Delta\\mathrm\{PW\}\(T\)=\\Delta\\mathrm\{MAC\}\(T\)=0for every transformTT\.

LetO=\(I,sI,V\)O=\(I,s\_\{I\},V\)be what top\-kkattention reads: the kept keys, their scores and the values\.

###### Theorem 4\(Tail\-mass estimate is unbiased and optimal\)\.

Let the scoresssand the valuesVVbe random, with𝔼​‖vj‖2<∞\\mathbb\{E\}\\\|v\_\{j\}\\\|^\{2\}<\\inftyfor everyjj\. Assume that the tail scores\(sj\)j∈J\(s\_\{j\}\)\_\{j\\in J\}are exchangeable givenOO: their conditional law is invariant under permutations ofJJ\.

1. \(i\)Withq=𝔼⁡\[τ∣O\]q=\\mathbb\{E\}\[\\tau\\mid O\], the estimate satisfiesp^=𝔼⁡\[π∣O\]\\hat\{p\}=\\mathbb\{E\}\[\\pi\\mid O\]ando^=𝔼⁡\[o∣O\]\\hat\{o\}=\\mathbb\{E\}\[o\\mid O\]\. Both are unbiased, and they minimize𝔼​‖p^−π‖2\\mathbb\{E\}\\\|\\hat\{p\}\-\\pi\\\|^\{2\}and𝔼​‖o^−o‖2\\mathbb\{E\}\\\|\\hat\{o\}\-o\\\|^\{2\}among all functions ofOO\. In exact mode the same holds given\(O,τ\)\(O,\\tau\), withq=τq=\\tau\.
2. \(ii\)Tail drop has conditional bias𝔼\[p^−π∣O\]=𝔼\[τ∣O\]\(π~I,−𝟙J/m\)\\mathbb\{E\}\[\\hat\{p\}\-\\pi\\mid O\]=\\mathbb\{E\}\[\\tau\\mid O\]\\,\(\\tilde\{\\pi\}\_\{I\},\-\\mathbbm\{1\}\_\{J\}/m\)and𝔼⁡\[o^−o∣O\]=𝔼⁡\[τ∣O\]​\(a−u¯\)\\mathbb\{E\}\[\\hat\{o\}\-o\\mid O\]=\\mathbb\{E\}\[\\tau\\mid O\]\\,\(a\-\\bar\{u\}\)\. Its conditional distribution bias vanishes only when𝔼⁡\[τ∣O\]=0\\mathbb\{E\}\[\\tau\\mid O\]=0\.

Theorem[4](https://arxiv.org/html/2610.28958#Thmtheorem4)concerns the attention distribution and the output of one head, not the loss of the whole model\. Part \(i\) covers exact mode, and calibrated mode whenτ\\tauis mean\-independent ofOO\. Among constant tail masses,𝔼​\(q−τ\)2=\(q−𝔼​τ\)2\+Var​τ\\mathbb\{E\}\(q\-\\tau\)^\{2\}=\(q\-\\mathbb\{E\}\\tau\)^\{2\}\+\\mathrm\{Var\}\\tauis minimal atq=𝔼​τq=\\mathbb\{E\}\\tau, which the calibratedqqestimates\.

###### Proposition 4\(Error decomposition\)\.

For every query,

o^−o=τ⁡\(u¯−b\)\+\(q−τ\)​\(u¯−a\),‖p^−π‖22=\(q−τ\)2​w\+∑j∈J\(πj−τm\)2,\\hat\{o\}\-o=\\tau\\,\(\\bar\{u\}\-b\)\+\(q\-\\tau\)\\,\(\\bar\{u\}\-a\),\\qquad\\\|\\hat\{p\}\-\\pi\\\|\_\{2\}^\{2\}=\(q\-\\tau\)^\{2\}\\,w\+\\sum\_\{j\\in J\}\\Bigl\(\\pi\_\{j\}\-\\frac\{\\tau\}\{m\}\\Bigr\)^\{2\},withw=‖π~I‖22\+1mw=\\\|\\tilde\{\\pi\}\_\{I\}\\\|\_\{2\}^\{2\}\+\\frac\{1\}\{m\}\. Tail drop has output errorτ⁡\(a−b\)\\tau\\,\(a\-b\)\.

Proposition[4](https://arxiv.org/html/2610.28958#Thmproposition4)needs no assumption\. The error splits into a uniform\-tail term and a term from the error in the tail mass, and exact mode removes the second term, so for every query it minimizes the distribution error overqq\. When the tail is uniform,πj=τ/m\\pi\_\{j\}=\\tau/monJJ, sob=u¯b=\\bar\{u\}and exact mode has no error, while tail drop keeps the errorτ⁡\(a−b\)\\tau\(a\-b\)\. In the expected distribution error, only𝔼⁡\[\(q−τ\)2​w\]\\mathbb\{E\}\[\(q\-\\tau\)^\{2\}w\]depends onqq, so the best constant isq∗=𝔼⁡\[w​τ\]/𝔼⁡\[w\]q^\{\*\}=\\mathbb\{E\}\[w\\tau\]/\\mathbb\{E\}\[w\], which equals𝔼​τ\\mathbb\{E\}\\tauwhenwwandτ\\tauare uncorrelated\.

#### Centroids factor the selection scores

Exact top\-kkforms allN2N^\{2\}scores before it selects, so its strict graph makes at leastN2N^\{2\}unary evaluations per head \(Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)\)\. When the queries cluster, the keys can be chosen before the scores, and only thekkkept scores of each query are formed\.

###### Corollary 2\(Cost of selected scores\)\.

Fix one head and1≤k≤N1\\leq k\\leq N, and let each query selectkkkeys by a rule that is constant on some open set of inputs\. Every product\-free graph that computes theN​kNkselected scores hasPW≥N​k\\mathrm\{PW\}\\geq Nk\. Given the selected key indices, a graph overℬstrict​\(Φstrict\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\_\{\\mathrm\{strict\}\}\)computes them withPW=N​k​d\+2​N​d\\mathrm\{PW\}=Nkd\+2Nd\.

For each head, k\-means on calibration queries givesCCcentroidsc1,…,cCc\_\{1\},\\dots,c\_\{C\}, the rows ofW∈ℝC×dW\\in\\mathbb\{R\}^\{C\\times d\}\. Queryiigoes to its nearest centroidcr⁡\(i\)c\_\{r\(i\)\}, the one that maximizes the affine scoreqi⋅cr−12​‖cr‖2q\_\{i\}\\cdot c\_\{r\}\-\\tfrac\{1\}\{2\}\\\|c\_\{r\}\\\|^\{2\}, and the assignmentE∈\{0,1\}N×CE\\in\\\{0,1\\\}^\{N\\times C\}factors the queries asQ≈E​WQ\\approx EW\. The selection scoresE​W​K⊤/dEWK^\{\\top\}/\\sqrt\{d\}, a gather of the centroid scoresW​K⊤/dWK^\{\\top\}/\\sqrt\{d\}, replaceQ​K⊤/dQK^\{\\top\}/\\sqrt\{d\}, and the routed support of queryiiis the topkkkeys of its row\. It is the exact top\-kksupport ofqiq\_\{i\}whenever the gap condition of Lemma[2](https://arxiv.org/html/2610.28958#Thmlemma2)holds forc=cr⁡\(i\)c=c\_\{r\(i\)\}\. LikeTopK\\mathrm\{TopK\}of the scores, it is constant on an open set of inputs, so Corollary[2](https://arxiv.org/html/2610.28958#Thmcorollary2)bounds its scores\. The source graph of the routed map is the all\-values form \([1](https://arxiv.org/html/2610.28958#Sx2.E1)\) on the routed support\.

###### Proposition 5\(Routed support\)\.

For fixed centroids and anhh\-head block, tail\-mass attention with a constant tail mass on the routed supports is computed exactly by a graph overℬstrict​\(Φstrict\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\_\{\\mathrm\{strict\}\}\)whoseScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}subgraphs makeh⁡\(2​N​k​d\+N​k\+3​N​d\)h\(2Nkd\+Nk\+3Nd\)unary evaluations, and by a graph overℬext​\(Φext\)\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\(\\Phi\_\{\\mathrm\{ext\}\}\)withΔ​PW=0\\Delta\\mathrm\{PW\}=0\.

In both graphs the assignment scores and the centroid scores are fixed affine maps with2​h​C​N​d2hCNdmultiply–accumulate steps, and the assignment and the selection are routing, so the router adds no unary evaluation\. Proposition[4](https://arxiv.org/html/2610.28958#Thmproposition4)holds for every support, so the error of the routed estimate splits into the same uniform\-tail and tail\-mass terms\.

#### A flocking step is one attention head

In the Motsch–Tadmor flocking model\[[51](https://arxiv.org/html/2610.28958#bib.bib51)\], agentiiat positionxix\_\{i\}with velocityviv\_\{i\}follows

v˙i=α⁡\(∑jπi​j​vj−vi\),πi​j=g⁡\(‖xi−xj‖\)∑lg⁡\(‖xi−xl‖\),\\dot\{v\}\_\{i\}=\\alpha\\Bigl\(\\sum\_\{j\}\\pi\_\{ij\}v\_\{j\}\-v\_\{i\}\\Bigr\),\\qquad\\pi\_\{ij\}=\\frac\{g\(\\\|x\_\{i\}\-x\_\{j\}\\\|\)\}\{\\sum\_\{l\}g\(\\\|x\_\{i\}\-x\_\{l\}\\\|\)\},wherejjandllrun over all agents andggis a decreasing influence function\.

###### Proposition 6\(Flocking step\)\.

Forg⁡\(r\)=e−θ​r2g\(r\)=e^\{\-\\theta r^\{2\}\}withθ\>0\\theta\>0,πi​j=softmaxj​\(2​θ​xi⊤​xj−θ​‖xj‖2\)\\pi\_\{ij\}=\\mathrm\{softmax\}\_\{j\}\(2\\theta\\,x\_\{i\}^\{\\top\}x\_\{j\}\-\\theta\\\|x\_\{j\}\\\|^\{2\}\), so∑jπi​j​vj\\sum\_\{j\}\\pi\_\{ij\}v\_\{j\}is one head of distance\-based attention\[[52](https://arxiv.org/html/2610.28958#bib.bib52)\]with queries2​θ​xi2\\theta x\_\{i\}, keysxjx\_\{j\}, a bias−θ​‖xj‖2\-\\theta\\\|x\_\{j\}\\\|^\{2\}per key and valuesvjv\_\{j\}\. The topkkkeys of agentiiare itskknearest agents\.

Tail\-mass attention \(Definition[9](https://arxiv.org/html/2610.28958#Thmdefinition9)\) gives thekknearest agents of agentiithe weights\(1−q\)​π~j\(1\-q\)\\tilde\{\\pi\}\_\{j\}and each of the othermmagents the weightq/mq/m\. Proposition[4](https://arxiv.org/html/2610.28958#Thmproposition4)gives the error of this top\-kkflocking step exactly, and Theorem[4](https://arxiv.org/html/2610.28958#Thmtheorem4)applies when the far positions are exchangeable given the kept scores, velocities andxix\_\{i\}\. By the proof of Proposition[6](https://arxiv.org/html/2610.28958#Thmproposition6), Lemma[2](https://arxiv.org/html/2610.28958#Thmlemma2)holds for these scores withd\\sqrt\{d\}replaced by11, so agents close to one centroid share its routed support when the gap condition holds\.

### Experiments

#### The compiled models match their references

We compile three pretrained models with the extended graph and top\-kktail\-mass attention, and evaluate them before training\. With all keys kept, the compiled models match their references:91\.36%91\.36\\%against91\.36%91\.36\\%on Pet,72\.01%72\.01\\%against72\.02%72\.02\\%on ImageNet,32\.5132\.51dB against32\.5132\.51dB on Set5, and a token negative log\-likelihood \(NLL\) of4\.54964\.5496against4\.54964\.5496on WikiText\-2\. The strict and extended graphs compute the same model exactly \(Theorems[1](https://arxiv.org/html/2610.28958#Thmtheorem1)and[3](https://arxiv.org/html/2610.28958#Thmtheorem3)\)\. Only model changes, such as top\-kkattention, and rounding change accuracy\.

#### The strict graph pays the predicted cost

Table[2](https://arxiv.org/html/2610.28958#Sx2.T2)measures the cost of the strict graphs of Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1)and Proposition[3](https://arxiv.org/html/2610.28958#Thmproposition3)on a GPU\. The reference calls fused attention and LayerNorm kernels\. The extended graph runs at2\.52\.5to5\.65\.6times the reference latency in Tables[2](https://arxiv.org/html/2610.28958#Sx2.T2)and[4](https://arxiv.org/html/2610.28958#Sx2.T4)\. The strict graph takes1\.21\.2to2\.42\.4times the latency and, at top\-6464,2\.32\.3times the peak memory of the extended graph\. The GPU hasκ≈2\\kappa\\approx 2for squares \(Methods\), far below the threshold of Corollary[1](https://arxiv.org/html/2610.28958#Thmcorollary1), so this slowdown does not come from the bound of Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)\. It comes from the construction:ddtimes more pointwise work than the bound, andN2​dN^\{2\}doperands per head that the implementation writes to memory\. A per\-module profile puts7373to77%77\\%of the added time inScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}\(Supplementary Table[S2](https://arxiv.org/html/2610.28958#Sx10.T2)\)\. A merged GPU kernel avoids these writes; no transform\-wise product\-free graph avoids the bound of Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)\.

With the same GELU approximation, the strict graph stays within0\.60\.6points of the Hadamard graph and of its polarization variant with top\-kksupport, and within0\.40\.4points routed\. Two runs of one strict configuration differ by up to0\.50\.5points with top\-kksupport and1\.51\.5points routed, since the tail mass and centroids are calibrated on augmented training images\. Squares cost no accuracy beyond run\-to\-run variation\. With top\-kksupport, polarization makes1\.91\.9times the unary evaluations and, fork≤64k\\leq 64, runs1313to1414times slower with5\.55\.5times the memory \(Supplementary Section S5\)\. In integer arithmetic both identities are exact \(Methods\)\.

Table 2:Measured cost of the compilations\.DeiT\-Tiny on Pet, bf16, before distillation\. Accuracy \(%\), and latency and peak GPU memory relative to the reference, which takes2\.202\.20ms per batch of 32 and6262MB \(Methods\)\. Hadamard: Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1)\. Strict: Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1); polarization: polarization for every product\. The extended graph uses GELU, the othersx⊙σ⁡\(1\.702​x\)x\\odot\\sigma\(1\.702x\)\. Top\-kk: thekklargest exact scores\. Routed:kkkeys chosen by 32 query centroids before the scores \(Methods\)\. Atk=197k=197both supports hold every key\.ExtendedHadamardStrictStrict, polarizationkkAcc\.LatencyMemoryAcc\.LatencyMemoryAcc\.LatencyMemoryAcc\.LatencyMemory*Top\-kksupport*1686\.243\.28×3\.28\\times1\.62×1\.62\\times83\.514\.18×4\.18\\times8\.72×8\.72\\times84\.085\.04×5\.04\\times8\.65×8\.65\\times83\.9568\.3×68\.3\\times47\.1×47\.1\\times3289\.233\.89×3\.89\\times2\.32×2\.32\\times87\.464\.73×4\.73\\times8\.72×8\.72\\times87\.985\.37×5\.37\\times8\.65×8\.65\\times87\.7176\.1×76\.1\\times47\.1×47\.1\\times6490\.354\.88×4\.88\\times3\.70×3\.70\\times89\.595\.75×5\.75\\times8\.72×8\.72\\times89\.787\.14×7\.14\\times8\.65×8\.65\\times89\.7093\.1×93\.1\\times47\.1×47\.1\\times19791\.365\.41×5\.41\\times2\.45×2\.45\\times90\.3510\.5×10\.5\\times17\.3×17\.3\\times90\.7313\.0×13\.0\\times17\.2×17\.2\\times90\.57132×132\\times63\.1×63\.1\\times*Routed support*1680\.133\.35×3\.35\\times1\.54×1\.54\\times78\.603\.48×3\.48\\times2\.21×2\.21\\times78\.224\.73×4\.73\\times2\.19×2\.19\\times78\.4414\.1×14\.1\\times5\.90×5\.90\\times3287\.144\.03×4\.03\\times2\.28×2\.28\\times85\.664\.10×4\.10\\times3\.56×3\.56\\times85\.964\.73×4\.73\\times3\.55×3\.55\\times85\.5522\.3×22\.3\\times11\.0×11\.0\\times6489\.814\.37×4\.37\\times3\.73×3\.73\\times88\.635\.56×5\.56\\times6\.27×6\.27\\times88\.886\.67×6\.67\\times6\.23×6\.23\\times88\.9940\.1×40\.1\\times21\.2×21\.2\\times
#### The elementwise product removes most of the strict cost

With top\-kksupport andk≤64k\\leq 64, the Hadamard graph of Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1)runs at1\.21\.2to1\.31\.3times the latency of the extended graph, against1\.41\.4to1\.51\.5for the strict graph, at similar memory \(Table[2](https://arxiv.org/html/2610.28958#Sx2.T2)\)\. Its measured unary counts equal Table[1](https://arxiv.org/html/2610.28958#Sx2.T1):2\.2×1062\.2\\times 10^\{6\}per image atk=16k=16, against1\.1×1081\.1\\times 10^\{8\}for the strict graph\. Its remaining cost is theN2​dN^\{2\}dproducts ofQ​K⊤QK^\{\\top\}per head, which this implementation writes to memory \(Supplementary Table[S2](https://arxiv.org/html/2610.28958#Sx10.T2)\)\. With top\-kksupport, the approximation of GELU costs the Hadamard graph0\.70\.7to2\.62\.6and the strict graph0\.30\.3to2\.32\.3points; with GELU, the Hadamard graph stays within0\.10\.1points of the extended graph\.

#### NPUs provide the Hadamard basis

Supplementary Table[S1](https://arxiv.org/html/2610.28958#Sx8.T1)shows where each graph runs on ten edge accelerators by documented operator support, with the approximation of GELU where GELU is missing\. The R\-Car V4H runs both graphs with its DSP\. Of the other nine, the strict graph runs entirely on seven, including the Edge TPU and, in INT8, the Jetson DLA; the open\-source NVDLA IP and Ethos\-N78 lack the inverse square root\. The extended graph runs entirely on five; the toolchains of the other four have no matrix product of two activations and place it on the host\. All ten multiply two activations elementwise, so none is product\-free\. The Hadamard graph uses the operations of the strict graph, so it runs wherever the strict graph runs\.

#### Standard quantization applies to the compiled graph

We apply the post\-training quantization \(PTQ\) used for convolutional networks\[[53](https://arxiv.org/html/2610.28958#bib.bib53),[54](https://arxiv.org/html/2610.28958#bib.bib54)\]: symmetric max\-abs scales from calibration data, with no training or reconstruction and no Transformer\-specific quantizer\. The only fitted quantities are least\-squares output maps \(Methods\)\.

The strict graph in Table[3](https://arxiv.org/html/2610.28958#Sx2.T3)replaces GELU byx​σ​\(1\.702​x\)x\\,\\sigma\(1\.702x\), so it uses the reduced strict basisℬstrict\(\{\(⋅\)2,σ,\(⋅\)−1/2\}\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\\{\(\\cdot\)^\{2\},\\sigma,\(\\cdot\)^\{\-1/2\}\\\}\)\. The extended graph keeps GELU and the matrix products ofℬext​\(Φext\)\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\(\\Phi\_\{\\mathrm\{ext\}\}\)\. Quantizers cut each graph into units with integer inputs and outputs \(Methods\)\. Weights, the logits and the inputs of linear, convolution and product nodes take 8 bits; the fixed affine nodes of the strict graph take 12\-bit inputs, since these include squares and sums of squares\.

PTQ changes the accuracy of the strict graph by−1\.47\-1\.47to−0\.05\-0\.05points with per\-channel weight scales, and by−1\.06\-1\.06to−0\.14\-0\.14with one scale per weight tensor\. On the extended graph it changes accuracy by−2\.5\-2\.5to−3\.9\-3\.9points\.

Table 3:Standard post\-training quantization of the compiled DeiT\-Tiny on Pet\.Top\-1 accuracy \(%\) of the bf16 float model and after PTQ of the whole model with per\-channel or per\-tensor weight scales\. On the calibration data the fp32 simulation holds every integer sum exactly \(Methods\)\. Nodes: quantized nodes, the output identity included\. PV:k/Nk/N\. Strict: the reduced strict graph, before distillation\. Extended: the Jeffreys\-distilled extended graph\.
#### The tail\-mass estimate beats tail drop

*Image classification\.*Table[4](https://arxiv.org/html/2610.28958#Sx2.T4)reports Oxford\-IIIT Pet and ImageNet\-1k with calibrated tail mass\. The Jeffreys divergenceDJD\_\{J\}between the predictive distributions of the compiled and reference models falls from0\.980\.98atk=8k=8to0\.0430\.043atk=64k=64and2×10−42\\times 10^\{\-4\}with all keys\. One epoch of distillation\[[55](https://arxiv.org/html/2610.28958#bib.bib55)\]against the reference with the Jeffreys divergence\[[56](https://arxiv.org/html/2610.28958#bib.bib56)\], withqqtrainable, brings top\-6464to90\.43±0\.18%90\.43\\pm 0\.18\\%over five seeds\. On ImageNet, without training, top\-6464is within1\.191\.19points of the reference\.

Table 4:DeiT\-Tiny compiled with calibrated tail\-mass top\-kk\.Pet: top\-1 accuracy \(%\) of the compiled model, Jeffreys divergenceDJD\_\{J\}to the reference, accuracy after one epoch of Jeffreys distillation \(mean±\\pms\.d\. over five seeds\), and latency of the compiled forward pass relative to the reference \(Methods\)\. ImageNet\-1k: accuracy of the compiled model without training\. PV isk/Nk/N\. References:91\.36%91\.36\\%\(Pet\),72\.02%72\.02\\%\(ImageNet\)\.*Image restoration\.*MambaIRv2\-Light\[[30](https://arxiv.org/html/2610.28958#bib.bib30)\]is a super\-resolution model that combines state\-space scans with windowed attention overN=256N=256positions\. Its attention and LayerNorm modules compile as in DeiT\-Tiny, and the state\-space scans stay as they are\. Table[5](https://arxiv.org/html/2610.28958#Sx2.T5)reports×4\\times 4and×2\\times 2super\-resolution on Set5\[[57](https://arxiv.org/html/2610.28958#bib.bib57)\], before and after three epochs ofL1L\_\{1\}fine\-tuning on DIV2K\[[58](https://arxiv.org/html/2610.28958#bib.bib58)\]\. Before training, exact tail mass gives the highest PSNR at everyk<Nk<N, and top\-6464is within0\.030\.03dB of the reference\. After fine\-tuning, exact mode and tail drop end within0\.060\.06dB of each other fork≥4k\\geq 4\.

Table 5:MambaIRv2\-Light on Set5\.PSNR \(dB\) before \(pre\) and after \(post\) three epochs ofL1L\_\{1\}fine\-tuning on DIV2K, selected on DIV2K training crops \(Methods\)\. References:32\.5132\.51dB \(×4\\times 4\),38\.2438\.24dB \(×2\\times 2\)\. Atk=0k=0all weight sits on the uniform tail, which tail drop cannot express; atk=256k=256the modes coincide and the tail\-drop cells repeat the calibrated run\.*Language modeling\.*Pythia\-70M\[[31](https://arxiv.org/html/2610.28958#bib.bib31)\]is a decoder\-only model with a causal mask, evaluated on WikiText\-2\[[59](https://arxiv.org/html/2610.28958#bib.bib59)\]withN=128N=128tokens\. Causal rows have different numbers of valid keys, so a single calibratedqqdoes not apply, and we use exact tail mass\. Table[6](https://arxiv.org/html/2610.28958#Sx2.T6)shows that exact tail mass keeps the NLL within0\.010\.01nats of the reference down tok=16k=16, while tail drop loses0\.040\.04nats there\.

Table 6:Pythia\-70M on WikiText\-2\.Token NLL \(nats\) and perplexity \(PPL\) of the compiled model without training, with exact tail mass and with tail drop, over2\.53×1052\.53\\times 10^\{5\}validation tokens in float32\.τ¯\\bar\{\\tau\}is the mean omitted tail mass of top\-kkon the dense scores of 4 random training minibatches of 4 sequences\. Reference: NLL4\.54964\.5496, PPL94\.5994\.59\.Figure[2](https://arxiv.org/html/2610.28958#Sx2.F2)compares the three modes\. On DeiT\-Tiny/Pet, exact mode atkkbeats tail drop at2​k2kfor all testedk≤32k\\leq 32; calibrated mode does so fork≤16k\\leq 16\. At equalk=8k=8, calibrated mode gains73\.873\.8points over tail drop\. The per\-head optimality of Theorem[4](https://arxiv.org/html/2610.28958#Thmtheorem4)does not order model accuracy: fork≤4k\\leq 4calibrated mode beats exact mode\. On Pythia\-70M, exact mode atkkbeats tail drop at2​k2kfor everyk≤8k\\leq 8\. On MambaIRv2\-Light, exact mode is the best of the three at everyk<Nk<N\. Calibrated mode falls below tail drop there fork≥16k\\geq 16, since one constant per block fits poorly a per\-query tail mass with s\.d\. about0\.20\.2at a mean of0\.570\.57\(k=16k=16\)\.

141664197002020404060608080kkaccuracy \(%\)\(a\) DeiT\-Tiny, Pet14166410−310^\{\-3\}10−110^\{\-1\}kkΔ\\DeltaNLL \(nats\)\(b\) Pythia\-70M, WikiText\-214166425625253030kkPSNR \(dB\)\(c\) MambaIRv2\-Light×4\\times 4, Set5tail dropcalibratedexactreferenceFigure 2:Tail\-mass estimate against tail drop\.Quality of the compiled model before any training, as a function of the number of kept keyskk\. \(a\) DeiT\-Tiny on Oxford\-IIIT Pet, top\-1 accuracy\. \(b\) Pythia\-70M on WikiText\-2, increase of the token negative log\-likelihood over the reference \(N=128N=128\); calibrated mode does not apply to causal rows, whose numbers of valid keys differ\. \(c\) MambaIRv2\-Light×4\\times 4super\-resolution on Set5, PSNR\.
#### Clustered queries cut the cost of the strict graph

The measured unary counts equal Proposition[5](https://arxiv.org/html/2610.28958#Thmproposition5)at every testedkk\. Atk=16k=16the routed strict DeiT\-Tiny graph uses2\.2×2\.2\\timesinstead of8\.6×8\.6\\timesthe reference memory and makes2\.4×1072\.4\\times 10^\{7\}instead of1\.1×1081\.1\\times 10^\{8\}unary evaluations per image \(Table[2](https://arxiv.org/html/2610.28958#Sx2.T2)\), at78\.22%78\.22\\%against84\.08%84\.08\\%accuracy; its latency falls from5\.05\.0to4\.74\.7times the reference\. With twice the keys it matches exact top\-kk: atk=32k=32it reaches85\.96%85\.96\\%with37%37\\%of the unary evaluations and41%41\\%of the memory of exact top\-1616\.

The routed support is accurate where the queries of a cluster attend to the same keys\. On DeiT\-Tiny it holds83%83\\%to95%95\\%of the attention mass of exact top\-kkfork=8k=8to6464, and99%99\\%in the last block, where the queries are most clustered\. Pythia\-70M queries cluster more tightly, but queries of one cluster attend to different keys, and with tail drop its perplexity rises by9%9\\%atk=32k=32\. Routing leaves the extended graph unchanged atN=197N=197and cuts the Hadamard graph’s memory by75%75\\%atk=16k=16\.

## Discussion

An NPU needs no attention, softmax or normalization unit to run Transformers\. The elementwise product of two activations removes the pointwise cost that Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)prices, and a MAC array that accepts two activation operands only keeps theN2​dN^\{2\}dproducts ofQ​K⊤QK^\{\\top\}andP​VPVout of memory\.

Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)applies to transform\-wise compilation, which keeps the attention contractions as subgraphs; a compilation that never formsQ​K⊤QK^\{\\top\}is outside it \(Supplementary Section S1\)\. Corollary[1](https://arxiv.org/html/2610.28958#Thmcorollary1)needs hardware whose MAC array outruns its pointwise unit by more than2​N​d/\(N\+d\)2Nd/\(N\+d\)\.

The construction extends to other blocks\. RMSNorm\[[42](https://arxiv.org/html/2610.28958#bib.bib42)\]compiles as LayerNorm without the mean\. A gated MLP such as SwiGLU\[[60](https://arxiv.org/html/2610.28958#bib.bib60)\]multiplies two activations, and its SiLU isx​σ​\(x\)x\\,\\sigma\(x\), so both take a polarization graph in the strict basis and a Hadamard node in the Hadamard and extended bases\.

For autonomous and multi\-agent systems, the Hadamard graph lets a robot or drone run a Transformer policy on an NPU built for convolutional networks\. By Proposition[6](https://arxiv.org/html/2610.28958#Thmproposition6), top\-kkattention is the topological rule of starling flocks, where each bird follows a fixed number of nearest neighbors\[[26](https://arxiv.org/html/2610.28958#bib.bib26)\], and the tail\-mass term describes the far agents by their total weight and mean velocity, as cluster\-level models of multi\-agent control do\[[61](https://arxiv.org/html/2610.28958#bib.bib61)\]\.

*Future work\.*The latency and memory reported here are GPU measurements, and the NPU placement of Supplementary Table[S1](https://arxiv.org/html/2610.28958#Sx8.T1)comes from documented operator support\. Compiling the three graphs and their quantized integer units with the NPU toolchains, and running them on the devices, is the next step\. A per\-query predictor of the tail mass from the selected scores would bring calibrated mode toward exact mode without the dense normalizer\. A swarm optimizer built on top\-kkattention with a tail\-mass term is the multi\-agent counterpart of these results\.

## Methods

### Notation

⟨ℬ⟩\\langle\\mathcal\{B\}\\rangleis the class of finite acyclic graphs over a basisℬ\\mathcal\{B\}\. It is closed under composition\. We writeF∈⟨ℬ⟩F\\in\\langle\\mathcal\{B\}\\ranglewhen a graph in⟨ℬ⟩\\langle\\mathcal\{B\}\\ranglecomputesFFexactly\.M⁡\(x,y\)M\(x,y\)is the polarization graph ofx​yxy: one fixed affine node formsx±yx\\pm y, two squares follow, and one fixed affine node returns14​\[\(x\+y\)2−\(x−y\)2\]=x​y\\tfrac\{1\}\{4\}\[\(x\+y\)^\{2\}\-\(x\-y\)^\{2\}\]=xy\.M~​\(x,y\)\\tilde\{M\}\(x,y\)is the norm\-expansion graph ofx​yxywhenx2x^\{2\}andy2y^\{2\}are available: one fixed affine node formsx\+yx\+y, one square follows, and one fixed affine node returns12​\[\(\(x\+y\)2−x2\)−y2\]=x​y\\tfrac\{1\}\{2\}\[\(\(x\+y\)^\{2\}\-x^\{2\}\)\-y^\{2\}\]=xy, subtracting the two close squares first\. For an index tupleII,gather⁡\(s,I\)=\(si1,…,sik\)\\operatorname\{gather\}\(s,I\)=\(s\_\{i\_\{1\}\},\\dots,s\_\{i\_\{k\}\}\)\.TopK\\mathrm\{TopK\}returns indices in descending order of score with a fixed tie\-breaking rule\.

### Compilation lemmas

Each lemma realizes one transform\. In this sectionℬstrict\\mathcal\{B\}\_\{\\mathrm\{strict\}\}isℬstrict​\(Φstrict\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\_\{\\mathrm\{strict\}\}\)\(Definition[2](https://arxiv.org/html/2610.28958#Thmdefinition2)\) andℬext\\mathcal\{B\}\_\{\\mathrm\{ext\}\}isℬext​\(Φext\)\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\(\\Phi\_\{\\mathrm\{ext\}\}\)\(Definition[7](https://arxiv.org/html/2610.28958#Thmdefinition7)\)\.

###### Lemma 3\(Affine maps, residuals, routing, GELU MLP\)\.

Fixed affine maps, residual sums and routing maps are nodes of both bases\.x↦A2​GELU​\(A1​x\+b1\)\+b2x\\mapsto A\_\{2\}\\mathrm\{GELU\}\(A\_\{1\}x\+b\_\{1\}\)\+b\_\{2\}is the compositionAffA2,b2∘GELU∘AffA1,b1\\mathrm\{Aff\}\_\{A\_\{2\},b\_\{2\}\}\\circ\\mathrm\{GELU\}\\circ\\mathrm\{Aff\}\_\{A\_\{1\},b\_\{1\}\}in both bases\.

###### Proof\.

For the approximation,x​σ​\(1\.702​x\)x\\,\\sigma\(1\.702x\)is one sigmoid after a fixed scaling and one product:M⁡\(x,σ⁡\(1\.702​x\)\)M\\bigl\(x,\\sigma\(1\.702x\)\\bigr\), two squares per hidden unit, in the strict basis, and one Hadamard node in the extended basis\. ∎

###### Lemma 4\(LayerNorm\)\.

LN∈⟨ℬstrict⟩\\mathrm\{LN\}\\in\\langle\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\\rangleandLN∈⟨ℬext⟩\\mathrm\{LN\}\\in\\langle\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\\rangle\.

###### Proof\.

Letu=x−mean⁡\(x\)​𝟙u=x\-\\mathrm\{mean\}\(x\)\\mathbbm\{1\}, which is affine\. Strict:r2=meani​\(ui2\)r^\{2\}=\\mathrm\{mean\}\_\{i\}\(u\_\{i\}^\{2\}\)uses squares and an affine mean,a=\(r2\+ε\)−1/2a=\(r^\{2\}\+\\varepsilon\)^\{\-1/2\}is one unary evaluation per token, andzi=M~​\(ui,a\)=ui/r2\+εz\_\{i\}=\\tilde\{M\}\(u\_\{i\},a\)=u\_\{i\}/\\sqrt\{r^\{2\}\+\\varepsilon\}reusesui2u\_\{i\}^\{2\}and formsa2a^\{2\}once per token, so it costs one square per entry and one per token\. ThenLNi​\(x\)=βi\+γi​zi\\mathrm\{LN\}\_\{i\}\(x\)=\\beta\_\{i\}\+\\gamma\_\{i\}z\_\{i\}is affine inzz\. Extended:r2=mean⁡\(u⊙u\)r^\{2\}=\\mathrm\{mean\}\(u\\odot u\)is a Hadamard product followed by an affine mean,a=\(r2\+ε\)−1/2a=\(r^\{2\}\+\\varepsilon\)^\{\-1/2\}is one unary evaluation per token, andLN⁡\(x\)=β\+γ⊙\(u⊙a\)\\mathrm\{LN\}\(x\)=\\beta\+\\gamma\\odot\(u\\odot a\), where the product with the fixedγ\\gammais affine andu⊙au\\odot ais a broadcast Hadamard product\. ∎

###### Lemma 5\(Scores and value mixing\)\.

\(Q,K\)↦Q​K⊤/d\(Q,K\)\\mapsto QK^\{\\top\}/\\sqrt\{d\}and\(P,V\)↦P​V\(P,V\)\\mapsto PVlie in⟨ℬstrict⟩\\langle\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\\rangleand in⟨ℬext⟩\\langle\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\\rangle\.

###### Proof\.

Strict:Si​j=\(2​d\)−1​\[∑f\(qi​f\+kj​f\)2−‖qi‖2−‖kj‖2\]S\_\{ij\}=\(2\\sqrt\{d\}\)^\{\-1\}\\bigl\[\\sum\_\{f\}\(q\_\{if\}\+k\_\{jf\}\)^\{2\}\-\\\|q\_\{i\}\\\|^\{2\}\-\\\|k\_\{j\}\\\|^\{2\}\\bigr\]and\(P​V\)i​j=12​\[∑ℓ\(vℓ​j2−\(vℓ​j−pi​ℓ\)2\)\+∑ℓpi​ℓ2\]\(PV\)\_\{ij\}=\\tfrac\{1\}\{2\}\\bigl\[\\sum\_\{\\ell\}\\bigl\(v\_\{\\ell j\}^\{2\}\-\(v\_\{\\ell j\}\-p\_\{i\\ell\}\)^\{2\}\\bigr\)\+\\sum\_\{\\ell\}p\_\{i\\ell\}^\{2\}\\bigr\], with the norms formed once per row and the sums affine:N2​d\+2​N​dN^\{2\}d\+2Ndsquares per head for the scores andN2​d\+N2\+N​dN^\{2\}d\+N^\{2\}\+Ndfor the mix\. In the mix the two close squares are subtracted per term, inside the node that sums overℓ\\ell\. Extended: each map is oneMatMul\\mathrm\{MatMul\}orBMM\\mathrm\{BMM\}node followed by a fixed scaling\. ∎

###### Lemma 6\(Softmax\)\.

s↦softmax⁡\(s\)s\\mapsto\\mathrm\{softmax\}\(s\)lies in⟨ℬstrict⟩\\langle\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\\rangleand in⟨ℬext⟩\\langle\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\\rangle\.

###### Proof\.

Letti=si−maxl⁡sl≤0t\_\{i\}=s\_\{i\}\-\\max\_\{l\}s\_\{l\}\\leq 0, where the maximum is a routing selection, andni=etin\_\{i\}=e^\{t\_\{i\}\}, so thatZ=∑jnj≥1Z=\\sum\_\{j\}n\_\{j\}\\geq 1\. The shift leavessoftmax\\mathrm\{softmax\}unchanged and keepsσ⁡\(−ti\)\\sigma\(\-t\_\{i\}\)in\[12,1\)\[\\tfrac\{1\}\{2\},1\)andZZin\[1,N\]\[1,N\], so every inverse square root below acts on a number in\[12,N\]\[\\tfrac\{1\}\{2\},N\]\. Strict: sinceσ⁡\(t\)/σ⁡\(−t\)=et\\sigma\(t\)/\\sigma\(\-t\)=e^\{t\}for everytt,ni=M\(σ\(ti\),\(σ\(−ti\)−1/2\)2\)n\_\{i\}=M\\bigl\(\\sigma\(t\_\{i\}\),\\,\(\\sigma\(\-t\_\{i\}\)^\{\-1/2\}\)^\{2\}\\bigr\), with two sigmoids, one inverse square root and three squares per entry;ZZis affine innn, andpi=M\(ni,\(Z−1/2\)2\)p\_\{i\}=M\\bigl\(n\_\{i\},\(Z^\{\-1/2\}\)^\{2\}\\bigr\)adds two squares per entry and one inverse square root and one square per row\. Extended:ni=exp⁡\(ti\)n\_\{i\}=\\exp\(t\_\{i\}\), one exponential per entry, andp=n⊙Z−1p=n\\odot Z^\{\-1\}, one reciprocal per row and a broadcast Hadamard product\. ∎

###### Lemma 7\(Tail\-mass top\-kkattention\)\.

The map of Definition[9](https://arxiv.org/html/2610.28958#Thmdefinition9)from\(s,V\)\(s,V\)too^\\hat\{o\}, for a fixed calibratedqqor forq=τq=\\tau, lies in⟨ℬstrict⟩\\langle\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\\rangleand in⟨ℬext⟩\\langle\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\\rangle\.

###### Proof\.

Masks are fixed routing and affine maps\. We treat three cases\.

*k=0k=0\.*Definition[9](https://arxiv.org/html/2610.28958#Thmdefinition9)giveso^=1N​∑jvj\\hat\{o\}=\\frac\{1\}\{N\}\\sum\_\{j\}v\_\{j\}, a fixed affine map\.

*k≥Nk\\geq N\.*Nothing is dropped and the map is dense attention, covered by Lemmas[5](https://arxiv.org/html/2610.28958#Thmlemma5)and[6](https://arxiv.org/html/2610.28958#Thmlemma6)\.

*1≤k<N1\\leq k<N\.*I=TopK⁡\(s,k\)I=\\mathrm\{TopK\}\(s,k\)ands^=gather⁡\(s,I\)\\hat\{s\}=\\operatorname\{gather\}\(s,I\)are routing\. In both modes the graph computes the all\-values form \([1](https://arxiv.org/html/2610.28958#Sx2.E1)\), which equals Definition[9](https://arxiv.org/html/2610.28958#Thmdefinition9)because∑j∈Jvj=∑j=1Nvj−∑j∈Ivj\\sum\_\{j\\in J\}v\_\{j\}=\\sum\_\{j=1\}^\{N\}v\_\{j\}\-\\sum\_\{j\\in I\}v\_\{j\}\. Its parts are the coefficientsωj=p^j−q/m\\omega\_\{j\}=\\hat\{p\}\_\{j\}\-q/m, the kept mixing∑j∈Iωj​vj\\sum\_\{j\\in I\}\\omega\_\{j\}v\_\{j\}, and the tail term\(q/m\)​∑j=1Nvj\(q/m\)\\sum\_\{j=1\}^\{N\}v\_\{j\}\. The kept mixing is the norm expansion of Lemma[5](https://arxiv.org/html/2610.28958#Thmlemma5)over thekkkept values in the strict basis and one product node overkkvalues in the extended basis\. In calibrated mode,π~\\tilde\{\\pi\}follows Lemma[6](https://arxiv.org/html/2610.28958#Thmlemma6)ons^\\hat\{s\}, with the selected maximums^1\\hat\{s\}\_\{1\}as shift;p^j=\(1−q\)​π~j\\hat\{p\}\_\{j\}=\(1\-q\)\\tilde\{\\pi\}\_\{j\}andωj\\omega\_\{j\}are affine inπ~\\tilde\{\\pi\}, and the tail term is a fixed affine map ofVV\. In exact mode, the dense normalizer is formed from all scores with the dense maximum as shift:nj=exp⁡\(sj−maxl⁡sl\)n\_\{j\}=\\exp\(s\_\{j\}\-\\max\_\{l\}s\_\{l\}\),Z=∑jnjZ=\\sum\_\{j\}n\_\{j\},p^j=nj/Z\\hat\{p\}\_\{j\}=n\_\{j\}/Zforj∈Ij\\in I\(Lemma[6](https://arxiv.org/html/2610.28958#Thmlemma6)\), andτ=1−∑j∈Ip^j\\tau=1\-\\sum\_\{j\\in I\}\\hat\{p\}\_\{j\}\. The coefficientsωj=p^j−τ/m\\omega\_\{j\}=\\hat\{p\}\_\{j\}\-\\tau/mare affine in\(p^,τ\)\(\\hat\{p\},\\tau\)\. The tail term\(τ/m\)​∑jvj\(\\tau/m\)\\sum\_\{j\}v\_\{j\}is a product of the scalar activationτ\\tauwith thedd\-dimensional activation∑jvj\\sum\_\{j\}v\_\{j\}: a norm expansion withτ2\\tau^\{2\}once per row and the squares of∑jvj\\sum\_\{j\}v\_\{j\}once per head in the strict basis, and one broadcast Hadamard node withddscalar products in the extended basis\. ∎

### Proofs of Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1), Propositions[1](https://arxiv.org/html/2610.28958#Thmproposition1)and[2](https://arxiv.org/html/2610.28958#Thmproposition2)and Theorem[3](https://arxiv.org/html/2610.28958#Thmtheorem3)

###### Proof of Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1)\.

Replace every transform of the block by its strict realization from Lemmas[3](https://arxiv.org/html/2610.28958#Thmlemma3)–[6](https://arxiv.org/html/2610.28958#Thmlemma6)\. Each realization computes its transform exactly, and⟨ℬstrict⟩\\langle\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\\rangleis closed under composition\. ∎

###### Proof of Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1)\.

Take the strict graph of Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1)\. Replace each product graph,M⁡\(x,y\)M\(x,y\)orM~​\(x,y\)\\tilde\{M\}\(x,y\), by one Hadamard nodex⊙yx\\odot y, drop the squares of the factors it used, and form each remaining square asx⊙xx\\odot x\. SinceM⁡\(x,y\)=M~​\(x,y\)=x​yM\(x,y\)=\\tilde\{M\}\(x,y\)=xy, the new graph computes the same function, and its unary maps are those ofΦ⊙\\Phi\_\{\\odot\}\.Score\\mathrm\{Score\}andMix\\mathrm\{Mix\}become a broadcast Hadamard product and a fixed sum,Si​j=d−1/2∑f\(qi⋅⊙kj⋅\)fS\_\{ij\}=d^\{\-1/2\}\\sum\_\{f\}\(q\_\{i\\cdot\}\\odot k\_\{j\\cdot\}\)\_\{f\}and\(PV\)i​j=∑ℓ\(pi⋅⊙v⋅j\)ℓ\(PV\)\_\{ij\}=\\sum\_\{\\ell\}\(p\_\{i\\cdot\}\\odot v\_\{\\cdot j\}\)\_\{\\ell\}, with no unary map\. LayerNorm keeps one inverse square root per token, as its source graph\. The MLP keeps one GELU per hidden unit, or one sigmoid and one Hadamard product for the approximation, as its source graph\. Softmax keeps, per entry, two sigmoids and one inverse square root forni=σ\(ti\)⊙\(σ\(−ti\)−1/2⊙σ\(−ti\)−1/2\)n\_\{i\}=\\sigma\(t\_\{i\}\)\\odot\\bigl\(\\sigma\(\-t\_\{i\}\)^\{\-1/2\}\\odot\\sigma\(\-t\_\{i\}\)^\{\-1/2\}\\bigr\), and, per row, one inverse square root for1/Z=Z−1/2⊙Z−1/21/Z=Z^\{\-1/2\}\\odot Z^\{\-1/2\}\(Lemma[6](https://arxiv.org/html/2610.28958#Thmlemma6)\)\. Its source graph pays one exponential per entry and one reciprocal per row, so softmax adds2​N22N^\{2\}unary evaluations per head\. For the contraction work, the products ofScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}cost theN2​dN^\{2\}dmultiplications of the source, and each fixed sum adds at mostN2​dN^\{2\}dmultiply–accumulate steps per head\. Softmax adds two products per entry fornin\_\{i\}and one per row for1/Z1/Z, so2​N2\+N2N^\{2\}\+Nper head; its sum over the row and its productn⊙Z−1n\\odot Z^\{\-1\}are those of the source graph\. ∎

###### Proof of Proposition[2](https://arxiv.org/html/2610.28958#Thmproposition2)\.

Replace every transform exceptScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}by its extended realization from Lemmas[3](https://arxiv.org/html/2610.28958#Thmlemma3)–[6](https://arxiv.org/html/2610.28958#Thmlemma6); these use only Hadamard products among the activation–activation products\. Each performs the operations of its source graph \(Definition[4](https://arxiv.org/html/2610.28958#Thmdefinition4)\)\. Affine maps, residuals, routing and the GELU MLP are basis nodes\. LayerNorm performs, per token, an affine mean, the productu⊙uu\\odot uand its mean, one inverse square root, and the rescaling\. Softmax performs one exponential per entry, an affine sum, one reciprocal per row and a broadcast product\. SoΔ​PW=Δ​MAC=0\\Delta\\mathrm\{PW\}=\\Delta\\mathrm\{MAC\}=0for these transforms\. ComputeScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}as in the proof of Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1), by a broadcast Hadamard product and a fixed reduction\. No unary map is added, soΔ​PW=0\\Delta\\mathrm\{PW\}=0, and the reduction adds at mostN2​dN^\{2\}dmultiply–accumulate steps per head\. ∎

###### Proof of Theorem[3](https://arxiv.org/html/2610.28958#Thmtheorem3)\.

Replace every transform of the block by its extended realization from Lemmas[3](https://arxiv.org/html/2610.28958#Thmlemma3)–[6](https://arxiv.org/html/2610.28958#Thmlemma6)\. Each realization computes its transform exactly, and⟨ℬext⟩\\langle\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\\rangleis closed under composition\. Every transform exceptScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}has the realization of the proof of Proposition[2](https://arxiv.org/html/2610.28958#Thmproposition2), withΔ​PW=Δ​MAC=0\\Delta\\mathrm\{PW\}=\\Delta\\mathrm\{MAC\}=0\.Score\\mathrm\{Score\}andMix\\mathrm\{Mix\}are singleMatMul\\mathrm\{MatMul\}orBMM\\mathrm\{BMM\}nodes of the source shape:PW=0\\mathrm\{PW\}=0andMAC=N2​d\\mathrm\{MAC\}=N^\{2\}dbefore and after\. HenceΔ​PW=Δ​MAC=0\\Delta\\mathrm\{PW\}=\\Delta\\mathrm\{MAC\}=0for every transform\. ∎

The basesℬstrict​\(Φstrict\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\_\{\\mathrm\{strict\}\}\)andℬext​\(Φext\)\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\(\\Phi\_\{\\mathrm\{ext\}\}\)are not nested\. WithΦall=Φstrict∪Φext\\Phi\_\{\\mathrm\{all\}\}=\\Phi\_\{\\mathrm\{strict\}\}\\cup\\Phi\_\{\\mathrm\{ext\}\}, Theorems[1](https://arxiv.org/html/2610.28958#Thmtheorem1)and[3](https://arxiv.org/html/2610.28958#Thmtheorem3)also hold in the nested basesℬstrict​\(Φall\)⊂ℬext​\(Φall\)\\mathcal\{B\}\_\{\\mathrm\{strict\}\}\(\\Phi\_\{\\mathrm\{all\}\}\)\\subset\\mathcal\{B\}\_\{\\mathrm\{ext\}\}\(\\Phi\_\{\\mathrm\{all\}\}\), since enlarging the unary set keeps every graph valid\.

### Proof of Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)

The proof follows the nonlinear rank of the target\.Φ\\Phiis an arbitrary set of real functions\. For a setD⊆ℝnD\\subseteq\\mathbb\{R\}^\{n\}write𝒜⁡\(D\)\\mathcal\{A\}\(D\)for the restrictions toDDof affine functions onℝn\\mathbb\{R\}^\{n\}\. ForF:D→ℝrF\\colon D\\to\\mathbb\{R\}^\{r\}, the nonlinear rank

nrkD⁡\(F\)=dim\(\(span⁡\{F1,…,Fr\}\+𝒜⁡\(D\)\)/𝒜⁡\(D\)\)\\operatorname\{nrk\}\_\{D\}\(F\)=\\dim\\Bigl\(\\bigl\(\\operatorname\{span\}\\\{F\_\{1\},\\dots,F\_\{r\}\\\}\+\\mathcal\{A\}\(D\)\\bigr\)/\\mathcal\{A\}\(D\)\\Bigr\)counts the coordinates ofFFthat stay linearly independent onDDafter adding affine functions\.

###### Lemma 8\(Fixed routing on a set dense in a ball\)\.

LetGGbe a finite product\-free graph with inputs inℝn\\mathbb\{R\}^\{n\}, and letU⊆ℝnU\\subseteq\\mathbb\{R\}^\{n\}be a nonempty open set\. There is a setD⊆UD\\subseteq Uand an open ballB⊆UB\\subseteq Usuch thatDDis dense inBBand every routing decision ofGGis the same at every point ofDD\.

###### Proof\.

GGhas finitely many routing nodes, and each, with its fixed tie\-breaking rule, has finitely many outcomes: an order of finitely many compared values, or a selection among finitely many entries\. The joint outcome therefore takes finitely many values, and the sets of points ofUUwith a given joint outcome form a finite partition ofUU\. A finite union of nowhere dense sets is nowhere dense, andUUis not, so some partD′D^\{\\prime\}is not nowhere dense: its closure contains an open ballBB, which we may take insideUU\. ThenD=D′∩BD=D^\{\\prime\}\\cap Bis dense inBB\. ∎

No continuity is used: the outcome sets may be arbitrary, soΦ\\Phineeds no continuity or measurability\.

###### Lemma 9\(Affine reduction\)\.

LetGGbe product\-free with outputsG1,…,GrG\_\{1\},\\dots,G\_\{r\}, let all routing ofGGbe constant on a setDD, and lety1,…,yuy\_\{1\},\\dots,y\_\{u\}be the outputs of its unary evaluations,u=PW⁡\(G\)u=\\mathrm\{PW\}\(G\), viewed as functions onDD\. Then there are affineℓj\\ell\_\{j\}and constantscj​tc\_\{jt\}withGj=ℓj\+∑tcj​t​ytG\_\{j\}=\\ell\_\{j\}\+\\sum\_\{t\}c\_\{jt\}y\_\{t\}onDD\.

###### Proof\.

By induction along a topological order, every value inGGis onDDan affine function of\(x,y1,…,yu\)\(x,y\_\{1\},\\dots,y\_\{u\}\)\. Inputs are\. A fixed affine node maps affine functions to affine functions\. A routing node acts onDDas a fixed0/10/1selection matrix\. A unary node outputs someyty\_\{t\}\. No node multiplies two values, so the induction never leaves the affine functions of\(x,y\)\(x,y\)\. ∎

###### Lemma 10\(Pointwise work bounds nonlinear rank\)\.

If a product\-free graphGGcomputesFFexactly on a setDDon which its routing is constant, thenPW⁡\(G\)≥nrkD⁡\(F\)\\mathrm\{PW\}\(G\)\\geq\\operatorname\{nrk\}\_\{D\}\(F\)\.

###### Proof\.

By Lemma[9](https://arxiv.org/html/2610.28958#Thmlemma9), everyFjF\_\{j\}equals∑tcj​t​yt\\sum\_\{t\}c\_\{jt\}y\_\{t\}modulo𝒜⁡\(D\)\\mathcal\{A\}\(D\)\. In the ambient quotient of all real functions onDDby𝒜⁡\(D\)\\mathcal\{A\}\(D\), the classes ofF1,…,FrF\_\{1\},\\ldots,F\_\{r\}lie in the span of theuuunary\-output classes\. Their span therefore has dimension at mostuu\. ∎

###### Lemma 11\(Rank of quadratic forms\)\.

LetDDbe dense in an open ballB⊆ℝnB\\subseteq\\mathbb\{R\}^\{n\}, and letF1,…,FrF\_\{1\},\\dots,F\_\{r\}be homogeneous quadratic polynomials onℝn\\mathbb\{R\}^\{n\}such that eachFsF\_\{s\}has a monomial, with nonzero coefficient, that no otherFtF\_\{t\}has\. ThennrkD⁡\(F\)=r\\operatorname\{nrk\}\_\{D\}\(F\)=r\.

###### Proof\.

Suppose∑sλs​Fs\\sum\_\{s\}\\lambda\_\{s\}F\_\{s\}agrees onDDwith an affine function\. Both sides are continuous andDDis dense inBB, so they agree onBB\. Polynomials that agree on an open set agree everywhere, and a homogeneous quadratic polynomial that is affine is zero\. The coefficient of the monomial that onlyFsF\_\{s\}has isλs\\lambda\_\{s\}times a nonzero number, so everyλs\\lambda\_\{s\}vanishes\. ∎

###### Proof of Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)\.

LetGGbe a product\-free graph with inputs inℝn\\mathbb\{R\}^\{n\}that computesS=Q​K⊤/dS=QK^\{\\top\}/\\sqrt\{d\}exactly, and takeDDandBBfrom Lemma[8](https://arxiv.org/html/2610.28958#Thmlemma8)withU=ℝnU=\\mathbb\{R\}^\{n\}\. The entrySi​j=d−1/2∑fqi​fkj​fS\_\{ij\}=d^\{\-1/2\}\\sum\_\{f\}q\_\{if\}k\_\{jf\}is a homogeneous quadratic polynomial, and no other entry has its monomialsqi​f​kj​fq\_\{if\}k\_\{jf\}\. Lemma[11](https://arxiv.org/html/2610.28958#Thmlemma11)givesnrkD⁡\(S\)=N2\\operatorname\{nrk\}\_\{D\}\(S\)=N^\{2\}, and Lemma[10](https://arxiv.org/html/2610.28958#Thmlemma10)givesPW⁡\(G\)≥N2\\mathrm\{PW\}\(G\)\\geq N^\{2\}\. ForMix\\mathrm\{Mix\}, the entry\(P​V\)i​j=∑ℓpi​ℓ​vℓ​j\(PV\)\_\{ij\}=\\sum\_\{\\ell\}p\_\{i\\ell\}v\_\{\\ell j\},\(i,j\)∈\[N\]×\[d\]\(i,j\)\\in\[N\]\\times\[d\], has the monomialspi​ℓ​vℓ​jp\_\{i\\ell\}v\_\{\\ell j\}, which no other entry has, so Lemmas[11](https://arxiv.org/html/2610.28958#Thmlemma11)and[10](https://arxiv.org/html/2610.28958#Thmlemma10)givePW⁡\(G\)≥N​d\\mathrm\{PW\}\(G\)\\geq Nd\. ∎

###### Proof of Corollary[1](https://arxiv.org/html/2610.28958#Thmcorollary1)\.

A transform\-wise product\-free compilation of anhh\-head block contains its ownScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}subgraph for each head, each exact for all arguments and sharing no unary evaluation with the others, so these subgraphs havePW≥h⁡\(N2\+N​d\)\\mathrm\{PW\}\\geq h\(N^\{2\}\+Nd\)by Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)\. Unary maps run only on the pointwise unit, at rate at mostRpwR\_\{\\mathrm\{pw\}\}, so they take at leasth⁡\(N2\+N​d\)/Rpwh\(N^\{2\}\+Nd\)/R\_\{\\mathrm\{pw\}\}\. In the extended graph,Score\\mathrm\{Score\}andMix\\mathrm\{Mix\}havePW=0\\mathrm\{PW\}=0andMAC=2​h​N2​d\\mathrm\{MAC\}=2hN^\{2\}dand, by assumption, take2​h​N2​d/Rmac2hN^\{2\}d/R\_\{\\mathrm\{mac\}\}\. The first time exceeds the second exactly whenκ\>2​N2​d/\(N2\+N​d\)=2​N​d/\(N\+d\)\\kappa\>2N^\{2\}d/\(N^\{2\}\+Nd\)=2Nd/\(N\+d\), which is below2​d2d\. The strict graph of Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1)hasPW=h⁡\(2​N2​d\+N2\+3​N​d\)\>2​h​N2​d\\mathrm\{PW\}=h\(2N^\{2\}d\+N^\{2\}\+3Nd\)\>2hN^\{2\}dinScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}\(Lemma[5](https://arxiv.org/html/2610.28958#Thmlemma5)\), hence a pointwise time of at leastκ\\kappatimes the extended time\. ∎

### Proofs for clustered attention

###### Proof of Lemma[1](https://arxiv.org/html/2610.28958#Thmlemma1)\.

The normalizer is at least∑j∈Iesj≥k​es\(k\)\\sum\_\{j\\in I\}e^\{s\_\{j\}\}\\geq k\\,e^\{s\_\{\(k\)\}\}, and the tail sum∑j∈Jesj\\sum\_\{j\\in J\}e^\{s\_\{j\}\}is at mostm​es\(k\+1\)m\\,e^\{s\_\{\(k\+1\)\}\}, soτ≤mk​es\(k\+1\)−s\(k\)\\tau\\leq\\frac\{m\}\{k\}e^\{s\_\{\(k\+1\)\}\-s\_\{\(k\)\}\}\. ∎

###### Proof of Lemma[2](https://arxiv.org/html/2610.28958#Thmlemma2)\.

LetR=maxl⁡‖kl‖R=\\max\_\{l\}\\\|k\_\{l\}\\\|\. For every key,\|qi⋅kj−c⋅kj\|≤‖qi−c‖​‖kj‖≤ρ​R\|q\_\{i\}\\cdot k\_\{j\}\-c\\cdot k\_\{j\}\|\\leq\\\|q\_\{i\}\-c\\\|\\,\\\|k\_\{j\}\\\|\\leq\\rho R\. Forj∈Ij\\in Iandl∈Jl\\in J,\(c⋅kj−c⋅kl\)/d≥\(qi⋅kj−qi⋅kl\)/d−2​ρ​R/d≥Δk−2​ρ​R/d\>0\(c\\cdot k\_\{j\}\-c\\cdot k\_\{l\}\)/\\sqrt\{d\}\\geq\(q\_\{i\}\\cdot k\_\{j\}\-q\_\{i\}\\cdot k\_\{l\}\)/\\sqrt\{d\}\-2\\rho R/\\sqrt\{d\}\\geq\\Delta\_\{k\}\-2\\rho R/\\sqrt\{d\}\>0, so every key ofIIscores above every key ofJJundercc\. ∎

###### Proof of Proposition[3](https://arxiv.org/html/2610.28958#Thmproposition3)\.

Exactness: replace softmax and value mixing by the realization of Lemma[7](https://arxiv.org/html/2610.28958#Thmlemma7)in each basis, and the other transforms as in Theorems[1](https://arxiv.org/html/2610.28958#Thmtheorem1)and[3](https://arxiv.org/html/2610.28958#Thmtheorem3)\. Work in the extended basis: fork=0k=0the map is an affine average and fork≥Nk\\geq Nit is dense attention, both equal to their source graphs\. For1≤k<N1\\leq k<Nthe source graph is the all\-values form \([1](https://arxiv.org/html/2610.28958#Sx2.E1)\) with theqqof the mode, and the extended realization of Lemma[7](https://arxiv.org/html/2610.28958#Thmlemma7)is this graph\.TopK\\mathrm\{TopK\}and gather are routing\. The softmax follows Lemma[6](https://arxiv.org/html/2610.28958#Thmlemma6), with one exponential per kept score in calibrated mode and one per score in exact mode, and one reciprocal per row\. The kept mixing is one product node overkkvalues\. The tail term is a fixed affine map in calibrated mode and one broadcast product node withddscalar products in exact mode\. HenceΔ​PW=Δ​MAC=0\\Delta\\mathrm\{PW\}=\\Delta\\mathrm\{MAC\}=0for every transform in both modes\. ∎

###### Proof of Theorem[4](https://arxiv.org/html/2610.28958#Thmtheorem4)\.

\(i\) GivenOO, the normalizerZ=∑jesjZ=\\sum\_\{j\}e^\{s\_\{j\}\}is a symmetric function of the tail scores, so the tail weightsπj=esj/Z\\pi\_\{j\}=e^\{s\_\{j\}\}/Z,j∈Jj\\in J, are exchangeable givenOO, and𝔼⁡\[πj∣O\]\\mathbb\{E\}\[\\pi\_\{j\}\\mid O\]is the same for allj∈Jj\\in J\. Thesemmvalues sum to𝔼⁡\[τ∣O\]\\mathbb\{E\}\[\\tau\\mid O\], so each equals𝔼⁡\[τ∣O\]/m\\mathbb\{E\}\[\\tau\\mid O\]/m\. Forj∈Ij\\in I,πj=\(1−τ\)​π~j\\pi\_\{j\}=\(1\-\\tau\)\\tilde\{\\pi\}\_\{j\}andπ~j\\tilde\{\\pi\}\_\{j\}is a function ofOO, so𝔼⁡\[πj∣O\]=\(1−𝔼⁡\[τ∣O\]\)​π~j\\mathbb\{E\}\[\\pi\_\{j\}\\mid O\]=\(1\-\\mathbb\{E\}\[\\tau\\mid O\]\)\\tilde\{\\pi\}\_\{j\}\. Withq=𝔼⁡\[τ∣O\]q=\\mathbb\{E\}\[\\tau\\mid O\]this isp^=𝔼⁡\[π∣O\]\\hat\{p\}=\\mathbb\{E\}\[\\pi\\mid O\]\. SinceVVis part ofOOandoois linear inπ\\pi,𝔼⁡\[o∣O\]=∑j𝔼⁡\[πj∣O\]​vj=o^\\mathbb\{E\}\[o\\mid O\]=\\sum\_\{j\}\\mathbb\{E\}\[\\pi\_\{j\}\\mid O\]v\_\{j\}=\\hat\{o\}\. The weights lie in\[0,1\]\[0,1\]and𝔼​‖vj‖2<∞\\mathbb\{E\}\\\|v\_\{j\}\\\|^\{2\}<\\infty, soπ\\piandooare square integrable, and a conditional expectation of a square\-integrable variable is unbiased and minimizes the mean squared error over all functions of the conditioning variables\. In exact mode,τ\\tauis observed\. GivenOO,τ\\tauis a symmetric function of the tail scores, so they stay exchangeable given\(O,τ\)\(O,\\tau\)\. Then𝔼\[πj∣O,τ\]\\mathbb\{E\}\[\\pi\_\{j\}\\mid O,\\tau\]is the same for allj∈Jj\\in Jand sums toτ\\tauoverJJ, so it equalsτ/m\\tau/m, and𝔼\[πj∣O,τ\]=\(1−τ\)π~j\\mathbb\{E\}\[\\pi\_\{j\}\\mid O,\\tau\]=\(1\-\\tau\)\\tilde\{\\pi\}\_\{j\}forj∈Ij\\in I\. This isp^\\hat\{p\}withq=τq=\\tau\. \(ii\) Forq=0q=0,p^I=π~I\\hat\{p\}\_\{I\}=\\tilde\{\\pi\}\_\{I\}andp^J=0\\hat\{p\}\_\{J\}=0, so𝔼\[p^−π∣O\]=\(π~I−\(1−𝔼\[τ∣O\]\)π~I,−𝔼\[τ∣O\]𝟙J/m\)=𝔼\[τ∣O\]\(π~I,−𝟙J/m\)\\mathbb\{E\}\[\\hat\{p\}\-\\pi\\mid O\]=\(\\tilde\{\\pi\}\_\{I\}\-\(1\-\\mathbb\{E\}\[\\tau\\mid O\]\)\\tilde\{\\pi\}\_\{I\},\\,\-\\mathbb\{E\}\[\\tau\\mid O\]\\mathbbm\{1\}\_\{J\}/m\)=\\mathbb\{E\}\[\\tau\\mid O\]\(\\tilde\{\\pi\}\_\{I\},\-\\mathbbm\{1\}\_\{J\}/m\)\. By \(i\),𝔼⁡\[o∣O\]=\(1−𝔼⁡\[τ∣O\]\)​a\+𝔼⁡\[τ∣O\]​u¯\\mathbb\{E\}\[o\\mid O\]=\(1\-\\mathbb\{E\}\[\\tau\\mid O\]\)a\+\\mathbb\{E\}\[\\tau\\mid O\]\\bar\{u\}, ando^=a\\hat\{o\}=aforq=0q=0, so𝔼⁡\[o^−o∣O\]=𝔼⁡\[τ∣O\]​\(a−u¯\)\\mathbb\{E\}\[\\hat\{o\}\-o\\mid O\]=\\mathbb\{E\}\[\\tau\\mid O\]\(a\-\\bar\{u\}\)\. ∎

###### Proof of Proposition[4](https://arxiv.org/html/2610.28958#Thmproposition4)\.

By Definition[9](https://arxiv.org/html/2610.28958#Thmdefinition9),o^=\(1−q\)​a\+q​u¯\\hat\{o\}=\(1\-q\)a\+q\\bar\{u\}, ando=\(1−τ\)​a\+τ​bo=\(1\-\\tau\)a\+\\tau b\. Subtracting,o^−o=\(τ−q\)​a\+q​u¯−τ​b=τ⁡\(u¯−b\)\+\(q−τ\)​\(u¯−a\)\\hat\{o\}\-o=\(\\tau\-q\)a\+q\\bar\{u\}\-\\tau b=\\tau\(\\bar\{u\}\-b\)\+\(q\-\\tau\)\(\\bar\{u\}\-a\)\. Forq=0q=0this isτ⁡\(a−b\)\\tau\(a\-b\)\. For the distribution,p^j−πj=\(τ−q\)​π~j\\hat\{p\}\_\{j\}\-\\pi\_\{j\}=\(\\tau\-q\)\\tilde\{\\pi\}\_\{j\}onII, andp^j−πj=\(q−τ\)/m\+\(τ/m−πj\)\\hat\{p\}\_\{j\}\-\\pi\_\{j\}=\(q\-\\tau\)/m\+\(\\tau/m\-\\pi\_\{j\}\)onJJ\. Squaring and summing, the cross term is2​\(q−τ\)​m−1​∑j∈J\(τ/m−πj\)=02\(q\-\\tau\)m^\{\-1\}\\sum\_\{j\\in J\}\(\\tau/m\-\\pi\_\{j\}\)=0, since∑j∈Jπj=τ\\sum\_\{j\\in J\}\\pi\_\{j\}=\\tau, which leaves\(q−τ\)2​\(‖π~I‖22\+1/m\)\+∑j∈J\(πj−τ/m\)2\(q\-\\tau\)^\{2\}\(\\\|\\tilde\{\\pi\}\_\{I\}\\\|\_\{2\}^\{2\}\+1/m\)\+\\sum\_\{j\\in J\}\(\\pi\_\{j\}\-\\tau/m\)^\{2\}\. ∎

###### Proof of Corollary[2](https://arxiv.org/html/2610.28958#Thmcorollary2)\.

Choose an open setUUof inputs on which the selection is constant, takeDDandBBfrom Lemma[8](https://arxiv.org/html/2610.28958#Thmlemma8)insideUU, and write the selected key indices of queryiiasji​1,…,ji​kj\_\{i1\},\\ldots,j\_\{ik\}\. The selected scoreFi​t=d−1/2∑fqi​fkji​t​fF\_\{it\}=d^\{\-1/2\}\\sum\_\{f\}q\_\{if\}k\_\{j\_\{it\}f\}has the monomialsqi​f​kji​t​fq\_\{if\}k\_\{j\_\{it\}f\}, which no other selected score has, since thekkkeys of a query are distinct\. Lemmas[11](https://arxiv.org/html/2610.28958#Thmlemma11)and[10](https://arxiv.org/html/2610.28958#Thmlemma10)givePW≥N​k\\mathrm\{PW\}\\geq Nk\. For the upper bound, routing gathers thekkkeys of each query, each selected score costsddsquares ofqi\+kjq\_\{i\}\+k\_\{j\}, and the norms of theNNqueries and theNNkeys cost2​N​d2Nd\(Lemma[5](https://arxiv.org/html/2610.28958#Thmlemma5)\)\. ∎

###### Proof of Proposition[5](https://arxiv.org/html/2610.28958#Thmproposition5)\.

The assignment scoresqi⋅cr−12​‖cr‖2q\_\{i\}\\cdot c\_\{r\}\-\\tfrac\{1\}\{2\}\\\|c\_\{r\}\\\|^\{2\}and the centroid scorescr⋅kjc\_\{r\}\\cdot k\_\{j\}are fixed affine maps ofQQandKK, withh​C​N​dhCNdmultiply–accumulate steps each\.TopK\\mathrm\{TopK\}over centroids,TopK\\mathrm\{TopK\}over keys for each centroid, and the gather of each query’s list are routing\. The selected scores costN​k​d\+2​N​dNkd\+2Ndsquares per head \(Corollary[2](https://arxiv.org/html/2610.28958#Thmcorollary2)\), and the kept mixing of Lemma[7](https://arxiv.org/html/2610.28958#Thmlemma7)costsN​k​d\+N​k\+N​dNkd\+Nk\+Nd\(Lemma[5](https://arxiv.org/html/2610.28958#Thmlemma5)\)\. With a constant tail mass the tail term is a fixed affine map ofVV\. In the extended basis the scores and the mixing are product nodes overkkkeys, and every unary map is one of the source graph\. ∎

###### Proof of Proposition[6](https://arxiv.org/html/2610.28958#Thmproposition6)\.

g⁡\(‖xi−xj‖\)=e−θ​‖xi‖2​e2​θ​xi⊤​xj−θ​‖xj‖2g\(\\\|x\_\{i\}\-x\_\{j\}\\\|\)=e^\{\-\\theta\\\|x\_\{i\}\\\|^\{2\}\}\\,e^\{2\\theta x\_\{i\}^\{\\top\}x\_\{j\}\-\\theta\\\|x\_\{j\}\\\|^\{2\}\}\. The first factor does not depend onjjand cancels against the same factor in the sum overll, which leaves the softmax\. The score of agentjjequalsθ​‖xi‖2−θ​‖xi−xj‖2\\theta\\\|x\_\{i\}\\\|^\{2\}\-\\theta\\\|x\_\{i\}\-x\_\{j\}\\\|^\{2\}, whose first term does not depend onjj; sinceθ\>0\\theta\>0, thekklargest scores belong to thekknearest agents\. Lemma[2](https://arxiv.org/html/2610.28958#Thmlemma2)holds for these scores withd\\sqrt\{d\}replaced by11: the bias of agentjjenters the scores of every query equally and cancels in each comparison of its proof\. ∎

### Models and data

*DeiT\-Tiny\.*We use the timm\[[62](https://arxiv.org/html/2610.28958#bib.bib62)\]DeiT\-Tiny\[[27](https://arxiv.org/html/2610.28958#bib.bib27)\]\(patch 16,224×224224\\times 224input,N=197N=197\)\. For Oxford\-IIIT Pet\[[28](https://arxiv.org/html/2610.28958#bib.bib28)\]\(37 classes, 3,680 training and 3,669 test images\) we fine\-tune the classifier head for 20 epochs on the training split and keep the epoch with the highest training accuracy, measured without augmentation; the reference reaches91\.36%91\.36\\%\. Pet has no validation split\. We report its test split, and no step selects on it\. For ImageNet\-1k\[[29](https://arxiv.org/html/2610.28958#bib.bib29)\]we use the pretrained checkpoint \(72\.02%72\.02\\%\)\.

*MambaIRv2\-Light\.*We use the released×2\\times 2and×4\\times 4lightweight super\-resolution weights\[[30](https://arxiv.org/html/2610.28958#bib.bib30)\]\. The attention acts on16×1616\\times 16windows, soN=256N=256\. Training uses DIV2K\[[58](https://arxiv.org/html/2610.28958#bib.bib58)\]patches of64×6464\\times 64low\-resolution pixels; evaluation reports PSNR on the Y channel of Set5\[[57](https://arxiv.org/html/2610.28958#bib.bib57)\]with the standard border crop\.

*Pythia\-70M\.*We use EleutherAI’s Pythia\-70M\[[31](https://arxiv.org/html/2610.28958#bib.bib31)\]with eager attention on non\-overlapping 128\-token windows of WikiText\-2 \(raw\)\[[59](https://arxiv.org/html/2610.28958#bib.bib59)\],2\.53×1052\.53\\times 10^\{5\}validation tokens\. The partial rotary embedding multiplies each query and key by a fixed rotation for each position, an affine node\.

### Tail\-mass calibration

Calibrated mode runs the reference model on calibration minibatches from the training split and records, for each block, the dense\-softmax mass outside the top\-kkscores of every query\. The block’sqqis the mean over queries\. We use the full Pet training split \(115 minibatches of 32\), 10 ImageNet training minibatches and 8 DIV2K minibatches\. Exact mode computesτ\\taufor each query at run time from the full softmax normalizer\. Supplementary Section S6 compares the tail modes and the calibrated with the exact tail mass\.

### Query\-centroid routing

For each block and head, k\-means \(k\-means\+\+ initialization, 30 Lloyd iterations\) fits 32 centroidscrc\_\{r\}to at most2162^\{16\}queries from 20 random training minibatches \(64 for Pythia\-70M\), taken after the rotary embedding\. Each query goes to its nearest centroid and takes the topkkkeys ofcr⁡\(i\)⋅kjc\_\{r\(i\)\}\\cdot k\_\{j\}, under the causal mask for Pythia\-70M\. Without a causal mask, each centroid keeps its topkkkeys and each query takes the list of its centroid, so noN×NN\\times Nmatrix is formed\. For causal routing, the implementation materializes anN×NN\\times Nmatrix of centroid selection scores and forms valid\-value means with a dense lower\-triangular contraction; keeping each centroid’s top\-kkkeys and the value sum over successive prefixes removes both dense operations\. In calibrated mode and with tail drop the graph gathers thekkrouted keys of each query and forms only their scores, by the norm expansion in the strict graph and by a batched product in the extended graph\. Exact mode forms all scores for its normalizer\. The tail term is that of Definition[9](https://arxiv.org/html/2610.28958#Thmdefinition9)\. For the strict graph with GELU atk=16k=16,3232and6464, the latency benchmark gives4\.194\.19,3\.893\.89and5\.415\.41times the reference latency with the routed support against4\.344\.34,4\.584\.58and6\.196\.19with exact top\-kk; the extended graph gives3\.353\.35to4\.374\.37against3\.283\.28to4\.884\.88, and its peak memory changes by less than5%5\\%\. Calibrated mode uses the mean mass outside the routed support on the calibration minibatches of the top\-kkruns\. We report, on the held\-out Pet test split and the WikiText\-2 validation split, the dense mass inside the routed support relative to the exact top\-kksupport, and the accuracy before fine\-tuning\. Pythia\-70M has no calibrated mode, so its perplexity is compared with tail dropping in both supports\. With 8 and 128 centroids the routed mass atk=16k=16is76%76\\%and92%92\\%of the top\-kkmass on DeiT\-Tiny and89%89\\%and93%93\\%on Pythia\-70M\.

### Distillation and fine\-tuning

For DeiT\-Tiny on Pet we distill\[[55](https://arxiv.org/html/2610.28958#bib.bib55)\]the compiled model against the frozen reference for one epoch with AdamW \(batch 64, learning rate5×10−55\\times 10^\{\-5\}, weight decay0\.050\.05, cosine schedule without warm\-up, gradient clipping at1\.01\.0\) and loss\(1−λ\)CE\(s,y\)\+λ\(KL\(s∥t\)\+KL\(t∥s\)\)\(1\-\\lambda\)\\,\\mathrm\{CE\}\(s,y\)\+\\lambda\\bigl\(\\mathrm\{KL\}\(s\\\|t\)\+\\mathrm\{KL\}\(t\\\|s\)\\bigr\), withλ=1\\lambda=1\(Jeffreys\) orλ=0\\lambda=0\(cross\-entropy\), over seeds 42 to 46\. Supplementary Section S7 compares the two losses\. Each run keeps the epoch, or the model before training, with the highest training accuracy, measured without augmentation, and later steps use the seed with the highest such accuracy; ties keep the earlier one\. The tail massqqis trainable, a scalar parameter per block clamped to\[0,1\]\[0,1\]in the forward pass\. For MambaIRv2\-Light we fine\-tune for three epochs with AdamW \(batch 8, learning rate2×10−42\\times 10^\{\-4\}, weight decay10−410^\{\-4\}, cosine schedule, gradient clipping at1\.01\.0\) on theL1L\_\{1\}loss to the high\-resolution targets and keep the epoch with the highest training PSNR on one center crop of each DIV2K training image: the third epoch in 22 of the 26 runs, the second in 3, and the untrained model for×2\\times 2atk=256k=256\. Set5 is only evaluated\. Pythia\-70M is evaluated without training\.

### Post\-training quantization

*Precision\.*We target edge NPUs, so DeiT\-Tiny and MambaIRv2\-Light run in bf16, which stores each value in half the memory of fp32 with 8 significant bits\. With all keys, bf16 changes the accuracy of every DeiT\-Tiny graph by at most0\.460\.46points and the PSNR of MambaIRv2\-Light by at most0\.040\.04dB against fp32 \(Supplementary Section S8\)\. An 8\-bit PTQ code drops the 8\-bit exponent of a bf16 value and keeps its sign and 7 more bits: all values of a tensor share one scale\. Near the largest value of its tensor the code is as fine as bf16, and smaller values lose bits\. A square doubles the exponent range of its input: a value at2−42^\{\-4\}of the largest has a square at2−82^\{\-8\}of the largest square\. Bit widths are those of the input codes\. The fixed affine nodes of the strict graph read squares and sums of squares, so their inputs take 12 bits; weights, the logits and the inputs of linear, convolution and product nodes, including the two scalings by the calibrated tail mass in each block, take 8 bits\.

*Quantized graph\.*Quantized nodes are the linear and convolution layers, the products of two activations or of an activation and a parameter, and the fixed affine nodes with a coefficient tensor, including the residual and position\-embedding additions\. Each quantized node has one quantizer per input, and this quantizer is also the output quantizer of the preceding node, so every boundary is quantized once\. An identity node at the model output gives the last layer an output quantizer too, so the logits are 8\-bit codes with one scale, and the model is quantized from the image to the logits\. Unary maps, routing, and plain sums and means over an axis have no quantizer of their own\. A sum or mean reads integer codes with fixed scales, or their squares, so its result is an integer with a fixed scale\. It keeps its full integer range, with no rounding to a specific bit width; the next quantizer sets the width\. The graph between two quantizers is thus a unit with integer inputs and integer outputs: a quantized node with its output map, followed by any unary, routing and summing nodes\. Every tensor that passes from one unit to the next is an integer code, so the quantized graph is an integer graph however its units are evaluated\. On an NPU, a unit is an integer multiply–accumulate followed by a requantization, a fixed multiplier and offset\[[53](https://arxiv.org/html/2610.28958#bib.bib53)\], and the lookup\-table or piecewise\-linear units of the NPU approximate its unary nodes over the calibrated input range\[[48](https://arxiv.org/html/2610.28958#bib.bib48),[49](https://arxiv.org/html/2610.28958#bib.bib49)\]\.

*Simulation and calibration\.*We simulate each unit in fp32\[[54](https://arxiv.org/html/2610.28958#bib.bib54)\], with the integer codes held in fp32 tensors\. fp32 holds every integer up to224≈1\.7×1072^\{24\}\\approx 1\.7\\times 10^\{7\}, so the integer sums are exact\. The run checks this for every node with integer inputs: over the calibration data, the sum of the absolute products of the node stays below4\.5×1064\.5\\times 10^\{6\}, a factor3\.73\.7below this limit\. The output maps and unary nodes run in fp32\. The bf16 float model is the reference\. Calibration runs it for two forward passes over the full Pet training split: the first records the maximum absolute value of every node input, the second fits the output maps to its outputs\. Activations use one symmetric max\-abs scale per input tensor\. Linear and convolution weights use one symmetric scale per output channel; affine coefficient tensors use one scale\. A linear or convolution node takes its output scale as the product of input and weight scales and fits a per\-channel output bias; other nodes fit an affine output map by least squares\. A node that combines several inputs of different range, as the norm expansion does withv2v^\{2\}and\(v−p\)2\(v\-p\)^\{2\}or withu2u^\{2\}anda2a^\{2\}, quantizes each input on its own grid and rescales it before the sum, as an integer add with per\-input multipliers does\. Quantizing the logits changes accuracy by−0\.16\-0\.16to\+0\.30\+0\.30points\. Supplementary Section S9 gives PTQ of the strict graph with exact GELU\.

*Integer products from squares\.*For integer operands both identities hold exactly when no intermediate step overflows or requantizes\. For signed 8\-bit operands in\[−128,127\]\[\-128,127\], the sums and differences lie in\[−256,255\]\[\-256,255\]\. A shared table of squares needs 512 signed\-index entries, or 257 magnitude\-index entries, with 17\-bit unsigned outputs, and the difference of two squares fits in 18 signed bits\. Dividing\(a\+b\)2−\(a−b\)2\(a\+b\)^\{2\}\-\(a\-b\)^\{2\}by four, or\(a\+b\)2−a2−b2\(a\+b\)^\{2\}\-a^\{2\}\-b^\{2\}by two, before accumulation gives the integer product exactly\. Each product has magnitude at most2142^\{14\}, so a signed 32\-bit accumulator holds a dot product of every lengthd<217d<2^\{17\}\.

### Timing and unary counts

Latency is the GPU time of the forward pass alone, divided by that of the reference, on one NVIDIA RTX 4070 Ti SUPER\. Ten batches of 32 images from the held\-out Pet test split are first stored on the GPU\. Each model runs in bf16 undertorch\.compilein the default, reduce\-overhead and max\-autotune modes, and we report its fastest mode: the median of five timed runs over the ten batches, with CUDA events after a warm\-up\. Peak memory is the maximum allocated GPU memory during an eager evaluation pass over the held\-out Pet test split, with only the measured model on the GPU; Supplementary Section S10 gives the tensor sizes behind it\. Unary evaluations are counted with forward hooks on every unary node over one test minibatch\. With all keys, the DeiT\-Tiny count per image equals twelve block totals of Table[1](https://arxiv.org/html/2610.28958#Sx2.T1)plus the final LayerNorm:6\.02×1066\.02\\times 10^\{6\}for the Hadamard graph and1\.96×1081\.96\\times 10^\{8\}for the strict graph with GELU\. The implementation of the extended graph forms the squaresu⊙uu\\odot uof its 25 LayerNorms with a unary square node, so its count of4\.17×1064\.17\\times 10^\{6\}adds25​N​h​d=9\.46×10525Nhd=9\.46\\times 10^\{5\}to that sum\. Withx⊙σ⁡\(1\.702​x\)x\\odot\\sigma\(1\.702x\)the strict graph forms this product from two squares,8​N​h​d8Nhdmore per block\.

*The GPU ratio\.*The RTX 4070 Ti SUPER has 66 Ada streaming multiprocessors at a boost clock of2\.612\.61GHz\. Each multiprocessor retires 128 FP32 operations per clock on its CUDA cores and 256 dense bf16 multiply–accumulates per clock with FP32 accumulation on its tensor cores\[[63](https://arxiv.org/html/2610.28958#bib.bib63)\]\. This givesRpw≈22R\_\{\\mathrm\{pw\}\}\\approx 22T/s,Rmac≈44R\_\{\\mathrm\{mac\}\}\\approx 44T/s andκ≈2\\kappa\\approx 2\.

### Numerical conventions

The compiled LayerNorm uses theε\\varepsilonof each reference:10−610^\{\-6\}for DeiT\-Tiny and10−510^\{\-5\}for MambaIRv2\-Light and Pythia\-70M\. Softmax normalization divides by the max\-shifted partition sumZZ\. The DeiT\-Tiny and MambaIRv2\-Light checkpoints store their weights in bf16; Pythia\-70M runs in fp32 \(Supplementary Section S8\)\. The bf16 runs evaluate the reference and every compiled graph under PyTorch CUDA autocast, which keeps means and sums in fp32; a node that adds several inputs stores its result in the precision of its first input\. In float64, against the reference with its weights rounded to bf16 the same way, the extended and strict DeiT\-Tiny graphs and the Hadamard graph with exact GELU, all with all keys, reproduce the reference logits on 16 Pet test images to6×10−86\\times 10^\{\-8\}\. The differences between the compiled and reference models in Table[2](https://arxiv.org/html/2610.28958#Sx2.T2)therefore come from bf16 weights and arithmetic\. The implementation of the strict graph evaluates\(x\+ε\)−1/2\(x\+\\varepsilon\)^\{\-1/2\}as a single kernel; it equals the inverse square root after a fixed affine map\.

## Data availability

All datasets are public: Oxford\-IIIT Pet\[[28](https://arxiv.org/html/2610.28958#bib.bib28)\], ImageNet\-1k\[[29](https://arxiv.org/html/2610.28958#bib.bib29)\], DIV2K\[[58](https://arxiv.org/html/2610.28958#bib.bib58)\], Set5\[[57](https://arxiv.org/html/2610.28958#bib.bib57)\]and WikiText\-2\[[59](https://arxiv.org/html/2610.28958#bib.bib59)\]\. Pretrained weights come from timm, the MambaIRv2 release and the Hugging Face hub\.

## Code availability

## References

- \[1\]Vaswani, A\.*et al\.*Attention is all you need\.In*Advances in Neural Information Processing Systems*, vol\. 30, 5998–6008 \(2017\)\.URL[https://proceedings\.neurips\.cc/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa\-Abstract\.html](https://proceedings.neurips.cc/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html)\.
- \[2\]Google Coral\.TensorFlow models on the edge TPU\.[https://www\.coral\.ai/docs/edgetpu/models\-intro/](https://www.coral.ai/docs/edgetpu/models-intro/)\(2026\)\.Accessed 2026\-05\-05\.
- \[3\]NVIDIA\.TensorRT documentation: DLA supported layers and restrictions\.[https://docs\.nvidia\.com/deeplearning/tensorrt/latest/inference\-library/dla\-layer\-restrictions\.html](https://docs.nvidia.com/deeplearning/tensorrt/latest/inference-library/dla-layer-restrictions.html)\(2026\)\.Accessed 2026\-10\-03\.
- \[4\]Xu, D\.*et al\.*Fast on\-device LLM inference with NPUs\.In*Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems \(ASPLOS\)*\(2025\)\.
- \[5\]Park, J\., Yoon, H\., Ahn, D\., Choi, J\. & Kim, J\.\-J\.OPTIMUS: OPTImized matrix MUltiplication structure for transformer neural network accelerator\.In*Proceedings of Machine Learning and Systems \(MLSys\)*, vol\. 2 \(2020\)\.URL[https://proceedings\.mlsys\.org/paper\_files/paper/2020/hash/91ba7292e5388b90b58d0b839a7f19ec\-Abstract\.html](https://proceedings.mlsys.org/paper_files/paper/2020/hash/91ba7292e5388b90b58d0b839a7f19ec-Abstract.html)\.
- \[6\]Seo, M\.*et al\.*IANUS: Integrated accelerator based on NPU\-PIM unified memory system\.In*Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems \(ASPLOS\)*\(2024\)\.
- \[7\]Kim, J\., Kim, S\., Choi, K\. & Park, I\.\-C\.Hardware\-efficient SoftMax architecture with bit\-wise exponentiation and reciprocal calculation\.*IEEE Transactions on Circuits and Systems I: Regular Papers*71, 4574–4585 \(2024\)\.
- \[8\]Liu, Z\.*et al\.*Post\-training quantization for vision transformer\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, vol\. 34 \(2021\)\.URL[https://proceedings\.neurips\.cc/paper/2021/hash/ec8956637a99787bd197eacd77acce5e\-Abstract\.html](https://proceedings.neurips.cc/paper/2021/hash/ec8956637a99787bd197eacd77acce5e-Abstract.html)\.
- \[9\]Yuan, Z\., Xue, C\., Chen, Y\., Wu, Q\. & Sun, G\.PTQ4ViT: Post\-training quantization for vision transformers with twin uniform quantization\.In*Proceedings of the European Conference on Computer Vision \(ECCV\)*\(2022\)\.
- \[10\]Lin, Y\., Zhang, T\., Sun, P\., Li, Z\. & Zhou, S\.FQ\-ViT: Post\-training quantization for fully quantized vision transformer\.In*Proceedings of the Thirty\-First International Joint Conference on Artificial Intelligence \(IJCAI\)*\(2022\)\.
- \[11\]Li, Z\., Xiao, J\., Yang, L\. & Gu, Q\.RepQ\-ViT: Scale reparameterization for post\-training quantization of vision transformers\.In*Proceedings of the IEEE/CVF International Conference on Computer Vision \(ICCV\)*\(2023\)\.
- \[12\]Moon, J\., Kim, D\., Cheon, J\. & Ham, B\.Instance\-aware group quantization for vision transformers\.In*Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\)*\(2024\)\.
- \[13\]Kim, S\., Gholami, A\., Yao, Z\., Mahoney, M\. W\. & Keutzer, K\.I\-BERT: Integer\-only BERT quantization\.In*Proceedings of the 38th International Conference on Machine Learning*, vol\. 139 of*Proceedings of Machine Learning Research*, 5506–5518 \(PMLR, 2021\)\.URL[https://proceedings\.mlr\.press/v139/kim21d\.html](https://proceedings.mlr.press/v139/kim21d.html)\.
- \[14\]Xiao, G\.*et al\.*SmoothQuant: Accurate and efficient post\-training quantization for large language models\.In*Proceedings of the 40th International Conference on Machine Learning \(ICML\)*, vol\. 202 of*Proceedings of Machine Learning Research*, 38087–38099 \(PMLR, 2023\)\.URL[https://proceedings\.mlr\.press/v202/xiao23c\.html](https://proceedings.mlr.press/v202/xiao23c.html)\.
- \[15\]ONNX\.LayerNormalization \(opset 17\), function definition\.[https://onnx\.ai/onnx/operators/onnx\_\_LayerNormalization\.html](https://onnx.ai/onnx/operators/onnx__LayerNormalization.html)\(2026\)\.Accessed 2026\-10\-03\.
- \[16\]ONNX\.Softmax \(opset 13\), function definition\.[https://onnx\.ai/onnx/operators/onnx\_\_Softmax\.html](https://onnx.ai/onnx/operators/onnx__Softmax.html)\(2026\)\.Accessed 2026\-10\-03\.
- \[17\]AMD\.Vitis AI ONNX operators for Ryzen AI NPUs\.[https://vitisai\.docs\.amd\.com/projects/gen2/en/latest/docs/additional\_information/operators\.html](https://vitisai.docs.amd.com/projects/gen2/en/latest/docs/additional_information/operators.html)\(2026\)\.Accessed 2026\-10\-03\.
- \[18\]Arm\.Ethos\-U Vela compiler 5\.2\.0: Supported operators\.[https://gitlab\.arm\.com/artificial\-intelligence/ethos\-u/ethos\-u\-vela/\-/blob/main/SUPPORTED\_OPS\.md](https://gitlab.arm.com/artificial-intelligence/ethos-u/ethos-u-vela/-/blob/main/SUPPORTED_OPS.md)\(2026\)\.Accessed 2026\-10\-03\.
- \[19\]Hu, J\., Shen, L\. & Sun, G\.Squeeze\-and\-excitation networks\.In*Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition \(CVPR\)*, 7132–7141 \(2018\)\.
- \[20\]Howard, A\.*et al\.*Searching for MobileNetV3\.In*Proceedings of the IEEE/CVF International Conference on Computer Vision \(ICCV\)*, 1314–1324 \(2019\)\.
- \[21\]Gupta, A\., Dar, G\., Goodman, S\., Ciprut, D\. & Berant, J\.Memory\-efficient transformers via top\-kkattention\.In*Proceedings of the Second Workshop on Simple and Efficient Natural Language Processing*, 39–52 \(Association for Computational Linguistics, 2021\)\.URL[https://aclanthology\.org/2021\.sustainlp\-1\.5/](https://aclanthology.org/2021.sustainlp-1.5/)\.
- \[22\]Wang, H\., Zhang, Z\. & Han, S\.SpAtten: Efficient sparse attention architecture with cascade token and head pruning\.In*2021 IEEE International Symposium on High\-Performance Computer Architecture \(HPCA\)*, 97–110 \(2021\)\.
- \[23\]Gong, P\.*et al\.*HATA: Trainable and hardware\-efficient hash\-aware top\-kkattention for scalable large model inference\.In*Findings of the Association for Computational Linguistics: ACL 2025*, 24856–24871 \(2025\)\.URL[https://aclanthology\.org/2025\.findings\-acl\.1275/](https://aclanthology.org/2025.findings-acl.1275/)\.
- \[24\]Geshkovski, B\., Letrouit, C\., Polyanskiy, Y\. & Rigollet, P\.A mathematical perspective on Transformers\.*Bulletin of the American Mathematical Society*62, 427–479 \(2025\)\.URL[https://arxiv\.org/abs/2312\.10794](https://arxiv.org/abs/2312.10794)\.
- \[25\]Vyas, A\., Katharopoulos, A\. & Fleuret, F\.Fast transformers with clustered attention\.In*Advances in Neural Information Processing Systems*, vol\. 33 \(2020\)\.URL[https://proceedings\.neurips\.cc/paper\_files/paper/2020/file/f6a8dd1c954c8506aadc764cc32b895e\-Paper\.pdf](https://proceedings.neurips.cc/paper_files/paper/2020/file/f6a8dd1c954c8506aadc764cc32b895e-Paper.pdf)\.
- \[26\]Ballerini, M\.*et al\.*Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study\.*Proceedings of the National Academy of Sciences*105, 1232–1237 \(2008\)\.
- \[27\]Touvron, H\.*et al\.*Training data\-efficient image transformers & distillation through attention\.In*Proceedings of the 38th International Conference on Machine Learning*, vol\. 139 of*Proceedings of Machine Learning Research*, 10347–10357 \(PMLR, 2021\)\.URL[https://proceedings\.mlr\.press/v139/touvron21a\.html](https://proceedings.mlr.press/v139/touvron21a.html)\.
- \[28\]Parkhi, O\. M\., Vedaldi, A\., Zisserman, A\. & Jawahar, C\. V\.Cats and dogs\.In*Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition \(CVPR\)*, 3498–3505 \(2012\)\.
- \[29\]Deng, J\.*et al\.*ImageNet: A large\-scale hierarchical image database\.In*Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition \(CVPR\)*, 248–255 \(2009\)\.
- \[30\]Guo, H\.*et al\.*MambaIRv2: Attentive state space restoration\.In*Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\)*, 28124–28133 \(2025\)\.
- \[31\]Biderman, S\.*et al\.*Pythia: A suite for analyzing large language models across training and scaling\.In*Proceedings of the 40th International Conference on Machine Learning \(ICML\)*, vol\. 202 of*Proceedings of Machine Learning Research*, 2397–2430 \(PMLR, 2023\)\.URL[https://proceedings\.mlr\.press/v202/biderman23a\.html](https://proceedings.mlr.press/v202/biderman23a.html)\.
- \[32\]Cybenko, G\.Approximation by superpositions of a sigmoidal function\.*Mathematics of Control, Signals and Systems*2, 303–314 \(1989\)\.
- \[33\]Pinkus, A\.Approximation theory of the MLP model in neural networks\.*Acta Numerica*8, 143–195 \(1999\)\.
- \[34\]Laundy, S\. L\.*Table of Quarter\-Squares of All Integer Numbers, up to 100,000, by which the Product of Two Factors May Be Found by the Aid of Addition and Subtraction Alone*\(Charles and Edwin Layton, London, 1856\)\.
- \[35\]Winograd, S\.A new algorithm for inner product\.*IEEE Transactions on Computers*C\-17, 693–694 \(1968\)\.
- \[36\]Yarotsky, D\.Error bounds for approximations with deep ReLU networks\.*Neural Networks*94, 103–114 \(2017\)\.
- \[37\]Rotem, N\.*et al\.*Glow: Graph lowering compiler techniques for neural networks\.arXiv:1805\.00907 \(2018\)\.
- \[38\]Chen, T\.*et al\.*THE\-X: Privacy\-preserving transformer inference with homomorphic encryption\.In*Findings of the Association for Computational Linguistics: ACL 2022*\(2022\)\.
- \[39\]Hao, M\.*et al\.*Iron: Private inference on transformers\.In*Advances in Neural Information Processing Systems*, vol\. 35 \(2022\)\.
- \[40\]Pang, Q\., Zhu, J\., Möllering, H\., Zheng, W\. & Schneider, T\.BOLT: Privacy\-preserving, accurate and efficient inference for transformers\.In*IEEE Symposium on Security and Privacy \(S&P\)*\(2024\)\.
- \[41\]Kosson, A\. & Jaggi, M\.Multiplication\-free transformer training via piecewise affine operations\.In*Advances in Neural Information Processing Systems*, vol\. 36 \(2023\)\.
- \[42\]Zhang, B\. & Sennrich, R\.Root mean square layer normalization\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, vol\. 32, 12360–12371 \(2019\)\.URL[https://proceedings\.neurips\.cc/paper/2019/hash/1e8a19426224ca89e83cef47f1e7f53b\-Abstract\.html](https://proceedings.neurips.cc/paper/2019/hash/1e8a19426224ca89e83cef47f1e7f53b-Abstract.html)\.
- \[43\]Bachlechner, T\., Majumder, B\. P\., Mao, H\., Cottrell, G\. & McAuley, J\.ReZero is all you need: Fast convergence at large depth\.In*Proceedings of the Thirty\-Seventh Conference on Uncertainty in Artificial Intelligence*, vol\. 161 of*Proceedings of Machine Learning Research*, 1352–1361 \(PMLR, 2021\)\.URL[https://proceedings\.mlr\.press/v161/bachlechner21a\.html](https://proceedings.mlr.press/v161/bachlechner21a.html)\.
- \[44\]Zhu, J\., Chen, X\., He, K\., LeCun, Y\. & Liu, Z\.Transformers without normalization\.*arXiv preprint arXiv:2503\.10622*\(2025\)\.
- \[45\]Chen, B\.*et al\.*Scatterbrain: Unifying sparse and low\-rank attention approximation\.In*Advances in Neural Information Processing Systems*, vol\. 34 \(2021\)\.URL[https://proceedings\.neurips\.cc/paper/2021/hash/9185f3ec501c674c7c788464a36e7fb3\-Abstract\.html](https://proceedings.neurips.cc/paper/2021/hash/9185f3ec501c674c7c788464a36e7fb3-Abstract.html)\.
- \[46\]Ren, H\.*et al\.*Combiner: Full attention transformer with sparse computation cost\.In*Advances in Neural Information Processing Systems*, vol\. 34 \(2021\)\.URL[https://proceedings\.neurips\.cc/paper/2021/hash/bd4a6d0563e0604510989eb8f9ff71f5\-Abstract\.html](https://proceedings.neurips.cc/paper/2021/hash/bd4a6d0563e0604510989eb8f9ff71f5-Abstract.html)\.
- \[47\]Chen, Z\.*et al\.*MagicPIG: LSH sampling for efficient LLM generation\.In*International Conference on Learning Representations \(ICLR\)*\(2025\)\.URL[https://proceedings\.iclr\.cc/paper\_files/paper/2025/hash/6d50d824ae819d5a961c1d8edc15e833\-Abstract\-Conference\.html](https://proceedings.iclr.cc/paper_files/paper/2025/hash/6d50d824ae819d5a961c1d8edc15e833-Abstract-Conference.html)\.
- \[48\]Yu, J\.*et al\.*NN\-LUT: Neural approximation of non\-linear operations for efficient transformer inference\.In*Proceedings of the 59th ACM/IEEE Design Automation Conference \(DAC\)*, 577–582 \(2022\)\.
- \[49\]Upadhyay, M\., Juneja, R\., Wong, W\.\-F\. & Peh, L\.\-S\.NOVA: NoC\-based vector unit for mapping attention layers on a CNN accelerator\.In*2024 Design, Automation & Test in Europe Conference & Exhibition \(DATE\)*, 1–6 \(2024\)\.
- \[50\]Hendrycks, D\. & Gimpel, K\.Gaussian error linear units \(GELUs\)\.*arXiv preprint arXiv:1606\.08415*\(2016\)\.
- \[51\]Motsch, S\. & Tadmor, E\.A new model for self\-organized dynamics and its flocking behavior\.*Journal of Statistical Physics*144, 923–947 \(2011\)\.
- \[52\]Kim, H\., Papamakarios, G\. & Mnih, A\.The Lipschitz constant of self\-attention\.In*Proceedings of the 38th International Conference on Machine Learning*, vol\. 139 of*Proceedings of Machine Learning Research*, 5562–5571 \(PMLR, 2021\)\.URL[https://proceedings\.mlr\.press/v139/kim21i\.html](https://proceedings.mlr.press/v139/kim21i.html)\.
- \[53\]Jacob, B\.*et al\.*Quantization and training of neural networks for efficient integer\-arithmetic\-only inference\.In*Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition \(CVPR\)*, 2704–2713 \(2018\)\.
- \[54\]Nagel, M\.*et al\.*A white paper on neural network quantization\.arXiv:2106\.08295 \(2021\)\.
- \[55\]Hinton, G\., Vinyals, O\. & Dean, J\.Distilling the knowledge in a neural network\.arXiv:1503\.02531 \(2015\)\.
- \[56\]Jeffreys, H\.An invariant form for the prior probability in estimation problems\.*Proceedings of the Royal Society of London\. Series A*186, 453–461 \(1946\)\.
- \[57\]Bevilacqua, M\., Roumy, A\., Guillemot, C\. & Alberi Morel, M\.\-L\.Low\-complexity single\-image super\-resolution based on nonnegative neighbor embedding\.In*Proceedings of the British Machine Vision Conference \(BMVC\)*, 135\.1–135\.10 \(BMVA Press, 2012\)\.URL[https://bmva\-archive\.org\.uk/bmvc/2012/BMVC/paper135/index\.html](https://bmva-archive.org.uk/bmvc/2012/BMVC/paper135/index.html)\.
- \[58\]Agustsson, E\. & Timofte, R\.NTIRE 2017 challenge on single image super\-resolution: Dataset and study\.In*Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops \(CVPRW\)*\(2017\)\.
- \[59\]Merity, S\., Xiong, C\., Bradbury, J\. & Socher, R\.Pointer sentinel mixture models\.In*International Conference on Learning Representations \(ICLR\)*\(2017\)\.URL[https://openreview\.net/forum?id=Byj72udxe](https://openreview.net/forum?id=Byj72udxe)\.
- \[60\]Shazeer, N\.GLU variants improve transformer\.arXiv:2002\.05202 \(2020\)\.
- \[61\]Erofeeva, V\., Granichin, O\., Avros, R\. & Volkovich, Z\.Multilevel modeling and control of dynamic systems\.*Scientific Reports*14, 27903 \(2024\)\.
- \[62\]Wightman, R\.PyTorch image models\.[https://github\.com/huggingface/pytorch\-image\-models](https://github.com/huggingface/pytorch-image-models)\(2019\)\.
- \[63\]NVIDIA\.NVIDIA Ada GPU architecture\.Whitepaper, version 2\.02,[https://images\.nvidia\.com/aem\-dam/Solutions/Data\-Center/l4/nvidia\-ada\-gpu\-architecture\-whitepaper\-V2\.02\.pdf](https://images.nvidia.com/aem-dam/Solutions/Data-Center/l4/nvidia-ada-gpu-architecture-whitepaper-V2.02.pdf)\(2023\)\.
- \[64\]Strassen, V\.Gaussian elimination is not optimal\.*Numerische Mathematik*13, 354–356 \(1969\)\.
- \[65\]Alman, J\.*et al\.*More asymmetry yields faster matrix multiplication\.In*Proceedings of the 2025 Annual ACM\-SIAM Symposium on Discrete Algorithms \(SODA\)*, 2005–2039 \(2025\)\.
- \[66\]Bürgisser, P\., Clausen, M\. & Shokrollahi, M\. A\.*Algebraic Complexity Theory*\(Springer, 1997\)\.
- \[67\]Mirzadeh, I\.*et al\.*ReLU strikes back: Exploiting activation sparsity in large language models\.In*International Conference on Learning Representations*\(2024\)\.URL[https://arxiv\.org/abs/2310\.04564](https://arxiv.org/abs/2310.04564)\.
- \[68\]Arm\.Ethos\-U Vela compiler source code \(regor backend\), commit dd3f874\.[https://gitlab\.arm\.com/artificial\-intelligence/ethos\-u/ethos\-u\-vela](https://gitlab.arm.com/artificial-intelligence/ethos-u/ethos-u-vela)\(2026\)\.Filesethosu/regor/tflite/tflite\_supported\_operators\_u55\.cpp,\_u85\.cpp,architecture/ethosu55/ethos\_u55\_register\_cs\_generator\.cpp,architecture/ethosu85/ethos\_u85\.cpp\. Accessed 2026\-10\-03\.
- \[69\]VeriSilicon\.TensorFlow Lite VX delegate for VeriSilicon NPUs, commit b76047d\.[https://github\.com/VeriSilicon/tflite\-vx\-delegate](https://github.com/VeriSilicon/tflite-vx-delegate)\(2026\)\.Operator mapop\_map\.ccandop\_status\.md\. Accessed 2026\-10\-03\.
- \[70\]Texas Instruments\.edgeai\-tidl\-tools: Supported operators, commit 7cdef46\.[https://github\.com/TexasInstruments/edgeai\-tidl\-tools/blob/master/docs/operators\.md](https://github.com/TexasInstruments/edgeai-tidl-tools/blob/master/docs/operators.md)\(2026\)\.Accessed 2026\-10\-09\.
- \[71\]Rockchip\.RKNN compiler support operator list, v2\.3\.2\.[https://github\.com/airockchip/rknn\-toolkit2/tree/master/doc](https://github.com/airockchip/rknn-toolkit2/tree/master/doc)\(2025\)\.Accessed 2026\-10\-09\.
- \[72\]Renesas\.R\-car hybrid compiler: Supported operators, commit e73e7d9\.[https://github\.com/renesas\-rcar/renesas\-rcar\-HybridCompiler](https://github.com/renesas-rcar/renesas-rcar-HybridCompiler)\(2025\)\.Accessed 2026\-10\-09\.
- \[73\]NVIDIA\.NVDLA software stack, commit 79538ba\.[https://github\.com/nvdla/sw](https://github.com/nvdla/sw)\(2019\)\.Compiler layer types \(umd/core/include/nvdla/IType\.h\) and CPU softmax \(umd/core/src/compiler/engine\-ast/SoftMaxOp\.cpp\)\. Accessed 2026\-10\-03\.
- \[74\]Arm\.Arm Ethos\-N driver stack, support library, commit 6834c82\.[https://github\.com/ARM\-software/ethos\-n\-driver\-stack](https://github.com/ARM-software/ethos-n-driver-stack)\(2025\)\.driver/support\_library/src/SupportQueries\.cppandSUPPORTED\.md\. Accessed 2026\-10\-03\.
- \[75\]NVIDIA\.NVDLA hardware architectural specification: LUT programming\.[https://nvdla\.org/hw/v1/ias/lut\-programming\.html](https://nvdla.org/hw/v1/ias/lut-programming.html)\(2018\)\.Accessed 2026\-10\-09\.
- \[76\]Hong, J\.\-W\. & Kung, H\. T\.I/O complexity: The red\-blue pebble game\.In*Proceedings of the 13th Annual ACM Symposium on Theory of Computing \(STOC\)*, 326–333 \(1981\)\.
- \[77\]Brent, R\. P\.Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd’s identity\.*Numerische Mathematik*16, 145–156 \(1970\)\.

Supplementary Information

## S1\. Tightness and scope of the bound

*Squares only\.*WithΦ=\{\(⋅\)2\}\\Phi=\\\{\(\\cdot\)^\{2\}\\\}and one nonlinear layer,PW\\mathrm\{PW\}is within a factor two of the bilinear rank of the matrix multiplication tensor, since polarization turns each product into two squares and each square is one product\. Fast matrix multiplication\[[64](https://arxiv.org/html/2610.28958#bib.bib64),[65](https://arxiv.org/html/2610.28958#bib.bib65)\]then gives strict graphs withPW=O⁡\(n2\.373\)\\mathrm\{PW\}=O\(n^\{2\.373\}\)forn×nn\\times nproducts, so noΩ⁡\(N2​d\)\\Omega\(N^\{2\}d\)bound holds for thisΦ\\Phi, and the factord\+2​d/Nd\+2d/Nbetween the strict graph of Theorem[1](https://arxiv.org/html/2610.28958#Thmtheorem1)and Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)is not forced\. Conversely, on the set of Lemma[8](https://arxiv.org/html/2610.28958#Thmlemma8)a graph over\{\(⋅\)2\}\\\{\(\\cdot\)^\{2\}\\\}withPW\\mathrm\{PW\}squarings is an arithmetic circuit withPW\\mathrm\{PW\}nonscalar multiplications, and nonscalar multiplications never exceed the total arithmetic cost\[[66](https://arxiv.org/html/2610.28958#bib.bib66)\]\. Ford=Nd=N, a lower bound of orderN2\+δN^\{2\+\\delta\}for thisΦ\\Phiwould therefore prove that the exponent of matrix multiplication is at least2\+δ2\+\\delta, an open problem\. For fixeddd,N2​d=O⁡\(N2\)N^\{2\}d=O\(N^\{2\}\)and the theorem is tight in order\. MAC arrays and tensor units run the classical product, and the strict graph follows it\.

*UnrestrictedΦ\\Phi\.*On a bounded box,Score\\mathrm\{Score\}is computed by a product\-free graph withN2\+2​N​dN^\{2\}\+2Ndunary evaluations, so no argument that ignores the regularity ofΦ\\Phican improve Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)beyond the additive2​N​d2Nd\. Map then=2​N​dn=2Ndinputs affinely into\[0,1\)\[0,1\)\. Forp=1,…,np=1,\\dots,nletψp\\psi\_\{p\}sendx∈\[0,1\)x\\in\[0,1\), written in binary with infinitely many zero digits, to the number whose digit at positionr​n\+prn\+pis therr\-th digit ofxxand whose other digits are zero\. The affine sumz=∑pψp​\(xp\)z=\\sum\_\{p\}\\psi\_\{p\}\(x\_\{p\}\)interleaves the digits of all inputs, has infinitely many zero digits, and so determines everyxpx\_\{p\}\. One further unary map per output,ϕi​j​\(z\)=Si​j\\phi\_\{ij\}\(z\)=S\_\{ij\}, decodes the score\. The total isn\+N2n\+N^\{2\}evaluations\. The construction reaches the bound by first encoding its inputs; one evaluation of a linear form alone cannot compute a product on an open set, becauseϕ⁡\(a⋅x\+b\)\\phi\(a\\cdot x\+b\)is constant on hyperplanes\.

*Transform\-wise scope\.*Applied to a whole block as one map, the nonlinear rank is at most the number of outputs,N​h​d=3\.78×104Nhd=3\.78\\times 10^\{4\}for DeiT\-Tiny, below the pointwise work of the source block\. A compilation that never formsQ​K⊤QK^\{\\top\}is therefore outside Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)\. The theorem concerns the attention contractions as transforms, which is the form in which every Transformer implementation and every NPU operator set presents them\.

## S2\. NPU operator support

Table[S1](https://arxiv.org/html/2610.28958#Sx8.T1)answers, for ten edge accelerators and from their documented operator support, whether the dense strict, Hadamard and extended graphs run entirely on the NPU\. “Whole” means the documentation lists every operation of the graph as supported on the accelerator; otherwise the cell lists the operations left to the host CPU or GPU, or, on R\-Car, to the on\-chip DSP\. MatMul is a matrix product of two activations, as inQ​K⊤QK^\{\\top\}andP​VPV, and Rsqrt is the inverse square root\. Where the compiler or runtime is open source we read the placement from its code at the commit given in the reference; for the three closed toolchains, Rockchip, Jetson DLA and Edge TPU, we use the vendor documentation\. A square runs as the elementwise productx⊙xx\\odot x, which every accelerator in the table supports\. A softmax counts as on the NPU when the NPU runs it as a native row\-wise operator or runs both the exponential and the reciprocal\. Where an accelerator lacks GELU, the MLP usesx​σ​\(1\.702​x\)x\\,\\sigma\(1\.702x\), which every accelerator in the table runs with its sigmoid and its elementwise product; edge deployments also replace GELU by ReLU and fine\-tune\[[67](https://arxiv.org/html/2610.28958#bib.bib67)\]\. Compiling the graphs with these toolchains and running them on the devices is future work\.

Table S1:Documented NPU support of the dense compiled graphs\.Whole\-graph compilation on the devices is future work\.AcceleratorUnary maps on the NPUStrict graphHadamard graphExtended graphArm Ethos\-U55/U65\[[68](https://arxiv.org/html/2610.28958#bib.bib68)\]Exp, Log, Rsqrt, GELU, Sigmoid, TanhWholeWholeWholeArm Ethos\-U85\[[68](https://arxiv.org/html/2610.28958#bib.bib68)\]Exp, Log, Rsqrt, GELU, Sigmoid, TanhWholeWholeWholeVeriSilicon VIP\[[69](https://arxiv.org/html/2610.28958#bib.bib69)\]Exp, Log, Rsqrt, GELU, Sigmoid, TanhWholeWholeWholeTI TDA4VM, C7x with MMA\[[70](https://arxiv.org/html/2610.28958#bib.bib70)\]Exp, Log, Sqrt, GELU, Sigmoid, Tanh; power by a constantWholeWholeWholeRockchip RK3588\[[71](https://arxiv.org/html/2610.28958#bib.bib71)\]GELU, Sigmoid, Tanh; power with exponent±0\.5\\pm 0\.5, 2 or 3WholeWholeWholeRenesas R\-Car V4H/V4M, CNN\-IP and DSP\[[72](https://arxiv.org/html/2610.28958#bib.bib72)\]CNN\-IP: ReLU, Sigmoid, TanhDSP: RsqrtDSP: RsqrtDSP: MatMul, softmax, LayerNorm, GELUNVIDIA Jetson Xavier/Orin DLA\[[3](https://arxiv.org/html/2610.28958#bib.bib3)\]ReLU, Sigmoid, Tanh, Abs, Sin, Cos, Atan; INT8 power and division by a constantWholeWholeHost: MatMulGoogle Edge TPU\[[2](https://arxiv.org/html/2610.28958#bib.bib2)\]ReLU, Sigmoid, Tanh, RsqrtWholeWholeHost: MatMul, row\-wise softmaxOpen\-source NVDLA IP\[[73](https://arxiv.org/html/2610.28958#bib.bib73)\]ReLU, Sigmoid, TanhHost: RsqrtHost: RsqrtHost: MatMul, softmax, LayerNorm RsqrtArm Ethos\-N78\[[74](https://arxiv.org/html/2610.28958#bib.bib74)\]ReLU, Sigmoid, TanhHost: RsqrtHost: RsqrtHost: MatMul, softmax, LayerNorm RsqrtThe strict graph needs only squares, the sigmoid and the inverse square root, so it runs whole on seven accelerators: Ethos\-U55/U65, Ethos\-U85, VeriSilicon VIP, the TI TDA4VM, the Rockchip RK3588, the Edge TPU and, in INT8, the Jetson DLA\. On the Jetson DLA the inverse square root runs as an INT8 power and the reciprocal as an INT8 division, each with a constant operand, and softmax runs on the NPU on Orin\. The R\-Car CNN\-IP lacks the inverse square root and runs it on the on\-chip DSP\. The open\-source NVDLA IP and Ethos\-N78 lack the inverse square root too and leave it, with the LayerNorm and the reciprocal that need it, to the host\. The extended graph runs whole on Ethos\-U, VeriSilicon, the TDA4VM and the RK3588, and on R\-Car with the DSP\. The toolchains of the other four have no matrix product of two activations and place the MatMul on the host, on three of them also softmax, and on two also the inverse square root of LayerNorm\. The Edge TPU compiler adds a limit of its own: it splits a model only once, so the first unsupported operation and everything after it run on the CPU\[[2](https://arxiv.org/html/2610.28958#bib.bib2)\]\. The strict graph runs whole there, and the extended graph moves to the CPU from the first attention score on\. On NVIDIA these limits come from the toolchains, not the hardware: the open\-source NVDLA IP, which the Jetson DLA is based on, has a programmable lookup table with linear interpolation, two tables of 65 and 257 entries, in its activation and normalization units\[[75](https://arxiv.org/html/2610.28958#bib.bib75)\]\. It can hold every function ofΦstrict\\Phi\_\{\\mathrm\{strict\}\}andΦext\\Phi\_\{\\mathrm\{ext\}\}, but both NVIDIA toolchains fill it only for the functions in the table\.

Every accelerator multiplies two activations elementwise, so none is product\-free in the sense of Definition[1](https://arxiv.org/html/2610.28958#Thmdefinition1): a CNN\-class NPU provides the Hadamard basisℬ⊙\\mathcal\{B\}\_\{\\odot\}\. There,Q​K⊤QK^\{\\top\}andP​VPVneed no pointwise work, since a broadcast Hadamard product followed by a fixed sum computes them \(Proposition[2](https://arxiv.org/html/2610.28958#Thmproposition2)\)\. With the sigmoid and the inverse square root, the Hadamard basis also runs the rest of the block \(Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1)\)\. The Hadamard graph takes the operations of the strict graph, with the elementwise product between two activations where the strict graph multiplies an activation by itself, so it runs on the accelerators where the strict graph runs\. Where the toolchain multiplies only tensors of equal shape, as on the Ethos\-N78, broadcast routing expands both operands first, as the strict graph does for its polarization operands\. The Ethos\-U55 compiler takes this route: it turns a matrix multiplication between activations into an elementwise product into an int32 buffer followed by a sum, one output column at a time\. The Ethos\-U85 compiler runs the same operation on its MAC array\.TopK\\mathrm\{TopK\}runs on the TDA4VM accelerator and on the R\-Car DSP\. On the other accelerators top\-kkattention and the routed support keep the selection on the host; Ethos\-U and VeriSilicon can instead replaceTopK\\mathrm\{TopK\}bykkarg\-max passes with masking\.

## S3\. Why the bound counts pointwise work

WriteIOL​\(G\)\\mathrm\{IO\}\_\{L\}\(G\)for the minimum number of words moved between a fast memory ofLLwords and slow memory, over all schedules of a graphGG\. With bandwidthβ\\beta, every schedule takes time

T⁡\(G\)≥max⁡\(IOL​\(G\)/β,MAC⁡\(G\)/Rmac,PW⁡\(G\)/Rpw\)\.T\(G\)\\ \\geq\\ \\max\\Bigl\(\\mathrm\{IO\}\_\{L\}\(G\)/\\beta,\\ \\mathrm\{MAC\}\(G\)/R\_\{\\mathrm\{mac\}\},\\ \\mathrm\{PW\}\(G\)/R\_\{\\mathrm\{pw\}\}\\Bigr\)\.The unfused strict graph writes theN2​dN^\{2\}dvaluesqi​f\+kj​fq\_\{if\}\+k\_\{jf\}to memory \(Supplementary Section S10\), so this one schedule has arithmetic intensityΘ⁡\(1\)\\Theta\(1\)and moves far more thanIOL\\mathrm\{IO\}\_\{L\}\. These writes are a property of the schedule, not of the basis\. The strict expansion ofScore\\mathrm\{Score\}in Lemma[5](https://arxiv.org/html/2610.28958#Thmlemma5)has the access pattern of the matrix product it replaces, so the tiling of the matrix product applies\. With square output tiles of sideΘ⁡\(L\)\\Theta\(\\sqrt\{L\}\), streaming over the reduction index, andLLsmall compared with the operands, a fused schedule moves

IOL=O⁡\(N2​dL\+N2\+N​d\)\\mathrm\{IO\}\_\{L\}=O\\Bigl\(\\frac\{N^\{2\}d\}\{\\sqrt\{L\}\}\+N^\{2\}\+Nd\\Bigr\)words per head, where the last two terms are the compulsory traffic of writing the scores and readingQQandKK; for classical \(non\-Strassen\) schedules of the native product the first term is also a lower bound in this regime\[[76](https://arxiv.org/html/2610.28958#bib.bib76)\]\. A fused strict kernel therefore has the same traffic order as nativeQ​K⊤QK^\{\\top\}\. Fusion changes neither the number of unary evaluations nor the unit that must perform them\. That is why Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)boundsPW\\mathrm\{PW\}and Corollary[1](https://arxiv.org/html/2610.28958#Thmcorollary1)rests on the third term\. The same tiling applies to a Hadamard product followed by a fixed reduction \(Proposition[2](https://arxiv.org/html/2610.28958#Thmproposition2)\): fused, it has the access pattern of the matrix product, so the Hadamard and extended bases differ only in the schedule a compiler chooses\.

## S4\. Where the compiled graph spends its time

Table[S2](https://arxiv.org/html/2610.28958#Sx10.T2)runs each graph eagerly, times the top\-level submodules of every block with CUDA events and records their working memory, for DeiT\-Tiny on Pet atk=16k=16\(bf16, 20 test batches of 32, RTX 4070 Ti SUPER\)\. The working memory of a module is the peak memory it allocates above what is in use when it starts; the table reports the largest value over its calls\. The strict graph adds64\.864\.8ms per batch over the extended graph;73\.3%73\.3\\%of it falls inScore\\mathrm\{Score\}andMix\\mathrm\{Mix\}, and9\.89\.8ms in softmax\. The module totals are117\.0117\.0and52\.252\.2ms per batch, a ratio of2\.22\.2\. The profiled reference runs its attention unfused, withQ​K⊤QK^\{\\top\}, softmax andP​VPVas separate kernels: it spends9\.09\.0ms there, against4\.14\.1ms and22MiB in its fused attention kernel, with a module total of25\.925\.9ms\. Atk=32k=32andk=64k=64the shares are74\.8%74\.8\\%and76\.5%76\.5\\%\.Score\\mathrm\{Score\}costs the same at everykkbecause scores are computed densely;Mix\\mathrm\{Mix\}grows withkk\. The routed graph of Table[2](https://arxiv.org/html/2610.28958#Sx2.T2)forms only the selected scores:Score\\mathrm\{Score\}falls from5050to1111ms per batch and its working memory from469469to7777MiB, and the centroid selection adds9\.69\.6ms\.

The Hadamard graph of Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1)forms the same broadcast grid as the strict graph, with one product per term instead of a sum and a square\. ItsScore\\mathrm\{Score\}takes31\.631\.6ms per batch, against49\.749\.7ms for the strict graph, and471471MiB, the bf16 tensor of theN2​dN^\{2\}dproducts per head of one batch; the strict graph holds one tensor of the same size, since it squares its sums in place\. Its module total is78\.278\.2ms\. With routed support itsScore\\mathrm\{Score\}falls to9\.29\.2ms and7878MiB, the centroid selection adds9\.79\.7ms, and the module total is65\.265\.2ms\.

The profile runs one kernel per node and synchronizes around every module, so it shows where eager time goes\. Table[2](https://arxiv.org/html/2610.28958#Sx2.T2)times the compiled forward pass on batches already on the GPU \(Methods\), wheretorch\.compilefuses the elementwise chains of every graph\. Atk=16k=16the compiled reference takes2\.202\.20ms per batch, and the extended, Hadamard and strict graphs take7\.217\.21,9\.189\.18and11\.0811\.08ms\. The strict graph thus takes1\.541\.54times the time of the extended graph, against2\.22\.2in the eager module totals\. Fused kernels keep the intermediates of a chain in fp32; all accuracies come from the eager bf16 runs\.

Table S2:Per\-module GPU time and working memory atk=16k=16in eager execution, summed over the 12 blocks of one batch\. Routed: 32 query centroids\. Ext\.: the extended graph, with GELU; the other graphs usex⊙σ⁡\(1\.702​x\)x\\odot\\sigma\(1\.702x\)\. Ref\.: the reference with unfused attention\. Softmax: top\-kkwith the tail term, dense for Ref\.Time \(ms/batch\)Working memory \(MiB\)StrictHadamardStrictHadamardModuletop\-kkroutedtop\-kkroutedExt\.Ref\.top\-kkroutedtop\-kkroutedExt\.Ref\.Score\\mathrm\{Score\}\(Q​K⊤QK^\{\\top\}\)49\.710\.731\.69\.24\.04\.146977471781414Mix\\mathrm\{Mix\}\(P​VPV\)7\.411\.84\.97\.05\.62\.8818178783912LayerNorm23\.022\.217\.917\.917\.95\.516171919199Softmax24\.924\.014\.012\.715\.12\.11518911828Centroid selection–9\.6–9\.7–––4–3––Linear \(qkv, proj\)3\.33\.84\.23\.64\.35\.0779999MLP8\.79\.45\.55\.15\.36\.3838328281818
## S5\. Polarization and squares

The strict graph forms each product of two activations from squares, by one of two classical identities:

a​b=14​\[\(a\+b\)2−\(a−b\)2\],a​b=12​\[\(a\+b\)2−a2−b2\]\.ab=\\tfrac\{1\}\{4\}\\bigl\[\(a\+b\)^\{2\}\-\(a\-b\)^\{2\}\\bigr\],\\qquad ab=\\tfrac\{1\}\{2\}\\bigl\[\(a\+b\)^\{2\}\-a^\{2\}\-b^\{2\}\\bigr\]\.The first, polarization, is the method of quarter\-squares\[[34](https://arxiv.org/html/2610.28958#bib.bib34)\]\. The second, the norm expansion, forms products in expressivity proofs for ReLU networks\[[36](https://arxiv.org/html/2610.28958#bib.bib36)\]\.

*Cost\.*Polarization pays two squares per product\. The norm expansion pays one square per product plus the squaresa2a^\{2\}andb2b^\{2\}of the factors, so an isolated product costs two squares by polarization and three by the norm expansion\. In a contraction each factor enters many products, and its square is formed once\.Q​K⊤QK^\{\\top\}of twoN×dN\\times dmatrices then costs2​N2​d2N^\{2\}dsquares by polarization andN2​d\+2​N​dN^\{2\}d\+2Ndby the norm expansion, and the ratio to the bound of Theorem[2](https://arxiv.org/html/2610.28958#Thmtheorem2)falls from2​d2dtod\+2​d/Nd\+2d/N\. This is Winograd’s precomputation of the self\-terms of each row\[[35](https://arxiv.org/html/2610.28958#bib.bib35)\], with squares in place of products\. The strict graph uses the norm expansion where the squares of the factors are shared, inQ​K⊤QK^\{\\top\},P​VPV, LayerNorm and the exact tail term, and polarization elsewhere, in softmax and the GELU approximation\.

*Exactness\.*Both identities are exact in real arithmetic and, without overflow or requantization, in integer arithmetic \(Methods\)\.

*Rounding\.*Both identities recover a small product as the difference of large squares\. In the value mix the resulty=∑kpk​vky=\\sum\_\{k\}p\_\{k\}v\_\{k\}is a weighted mean of the values, while the squares sum to about∑kvk2\\sum\_\{k\}v\_\{k\}^\{2\}; on DeiT\-Tiny this ratio is6565atk=16k=16and543543with all keys\. In bf16 the order of the operations then sets the error \(Table[S3](https://arxiv.org/html/2610.28958#Sx11.T3)\)\. Rounding each partial sum before the subtraction,12​\[∑k\(pk\+vk\)2−∑kpk2−∑kvk2\]\\tfrac\{1\}\{2\}\\bigl\[\\sum\_\{k\}\(p\_\{k\}\+v\_\{k\}\)^\{2\}\-\\sum\_\{k\}p\_\{k\}^\{2\}\-\\sum\_\{k\}v\_\{k\}^\{2\}\\bigr\], gives57%57\\%relative error with all keys\. Subtracting the two close squares per term inside the node that sums over keys gives14%14\\%for either identity:14​∑k\[\(pk\+vk\)2−\(pk−vk\)2\]\\tfrac\{1\}\{4\}\\sum\_\{k\}\\bigl\[\(p\_\{k\}\+v\_\{k\}\)^\{2\}\-\(p\_\{k\}\-v\_\{k\}\)^\{2\}\\bigr\]by polarization and12​\[∑k\(vk2−\(vk−pk\)2\)\+∑kpk2\]\\tfrac\{1\}\{2\}\\bigl\[\\sum\_\{k\}\\bigl\(v\_\{k\}^\{2\}\-\(v\_\{k\}\-p\_\{k\}\)^\{2\}\\bigr\)\+\\sum\_\{k\}p\_\{k\}^\{2\}\\bigr\]by the norm expansion\. With this order the two identities differ in cost, not in precision\. As Brent showed for Winograd’s identity\[[77](https://arxiv.org/html/2610.28958#bib.bib77)\], scaling the operands helps further: the fixed affine mapsp→λ​pp\\to\\lambda pandv→v/λv\\to v/\\lambdawithλ2=‖v‖/‖p‖\\lambda^\{2\}=\\\|v\\\|/\\\|p\\\|cut the error to2\.7%2\.7\\%\.

*Scaling and PTQ\.*Brent’s scaling and the PTQ scales are the same choice\. PTQ gives each tensor a grid with steps=max⁡\|x\|/\(2b−1−1\)s=\\max\|x\|/\(2^\{b\-1\}\-1\)forbbbits\. The node that formsa±ba\\pm badds two tensors, so in integers both operands sit on one grid, and with the step set by the larger operand the smaller keeps few levels: in the mix the weightsp≤1p\\leq 1share the grid of values several times larger\. The scalinga→λ​aa\\to\\lambda a,b→b/λb\\to b/\\lambdaleaves the product unchanged and gives both operands the same range, so one grid fits both\. It also makes the squares as small as they can be, sinceλ2​a2\+b2/λ2≥2​\|a​b\|\\lambda^\{2\}a^\{2\}\+b^\{2\}/\\lambda^\{2\}\\geq 2\|ab\|with equality atλ2=\|b\|/\|a\|\\lambda^\{2\}=\|b\|/\|a\|, and the size of the squares sets the step of the node that subtracts them\. PTQ calibration already measures the ranges, soλ2=max⁡\|b\|/max⁡\|a\|\\lambda^\{2\}=\\max\|b\|/\\max\|a\|follows from the same statistics, andλ\\lambdafolds into the fixed affine maps that produceaaandbband into the output maps, so it costs nothing at run time\. A node that combines several inputs, as the norm expansion does, quantizes each input on its own grid and rescales it before the sum \(Methods\); this takes care of the subtraction, but the balance of the operands insidea±ba\\pm bstill sets the number of bits\. The strict graph in this paper applies noλ\\lambda, and its fixed affine nodes take 12\-bit input codes\. Brent’s scaling can reduce this bit width\.

Table S3:bf16 error of the value mix on DeiT\-Tiny/Pet, relative to float64, averaged over the 12 blocks of 16 test images\. Partial sums and scaled: emulated kernels with bf16 rounding of every stored value;λ\\lambdais fitted on 8 other images\. The cancellation factor is∑kvk2/\|y\|\\sum\_\{k\}v\_\{k\}^\{2\}/\|y\|\.
## S6\. Tail\-mass ablation on DeiT\-Tiny

Table[S4](https://arxiv.org/html/2610.28958#Sx12.T4)compares the tail modes on Pet before training, and after Jeffreys distillation with trainableqq\. A fixed small tail mass \(q=10−3q=10^\{\-3\}\) behaves like tail drop: the omitted mass must be estimated\. Table[S5](https://arxiv.org/html/2610.28958#Sx12.T5)compares the calibratedqq, a constant per block averaged on the training split, with the exact per\-query tail mass on the held\-out Pet test split, which no calibration or selection reads\. Both sample 4096 queries per block from each minibatch of 32 images\. The two means agree within0\.0120\.012, and within0\.0010\.001fork≥16k\\geq 16, while single queries spread widely around them\.

This spread leaves room between the two modes\. Calibrated mode usesq=𝔼​τq=\\mathbb\{E\}\\tauand exact modeq=τq=\\tau\. Between them lies the conditional mean𝔼⁡\[τ∣ϕ\]\\mathbb\{E\}\[\\tau\\mid\\phi\]for any statisticϕ\\phiof what top\-kkattention reads, such as the log\-sum\-exp of the kept scores, thekk\-th score and the numbermmof dropped keys\. Its expected squared error is never larger than that of the constant, sinceVar​τ=𝔼​\(𝔼⁡\[τ∣ϕ\]−τ\)2\+Var​𝔼​\[τ∣ϕ\]\\mathrm\{Var\}\\tau=\\mathbb\{E\}\\bigl\(\\mathbb\{E\}\[\\tau\\mid\\phi\]\-\\tau\\bigr\)^\{2\}\+\\mathrm\{Var\}\\mathbb\{E\}\[\\tau\\mid\\phi\]\. Predicting the dropped partition sum asm​g​\(ϕ\)m\\,g\(\\phi\), instead ofτ\\tauitself, givesq=0q=0when no key is dropped\. It therefore also covers causal attention, where the tail mass grows with the position of the query and one constant per block fits poorly: on Pythia\-70M atk=16k=16the exact tail mass on 4 training minibatches is0\.062±0\.1150\.062\\pm 0\.115, between00and0\.700\.70\.

Table S4:Tail modes on DeiT\-Tiny/Pet, top\-1 accuracy \(%\)\. The last column is the saved one of five Jeffreys\-distilled runs with trainableqq, the run with the highest training accuracy\.Table S5:Calibrated against exact tail mass on DeiT\-Tiny/Pet\.Calibrated: the per\-block constant from the training split, averaged over blocks\. Exact: per\-query tail mass on the held\-out Pet test split, mean±\\pms\.d\. within a block averaged over blocks \(min, max\)\.
## S7\. Distillation loss

Table[S6](https://arxiv.org/html/2610.28958#Sx13.T6)compares cross\-entropy and Jeffreys distillation on Pet\. For2≤k≤322\\leq k\\leq 32, Jeffreys distillation recovers45%45\\%to46%46\\%of the accuracy gap between the compiled model and the reference, and cross\-entropy36%36\\%to43%43\\%\. Jeffreys gains most,1\.21\.2to1\.51\.5points, atk=2k=2and44, since it matches the full teacher distribution and not only the label\.

Table S6:Distillation on DeiT\-Tiny/Pet, top\-1 accuracy \(%\) of the saved run, the one with the highest training accuracy, and mean±\\pms\.d\. over five seeds\.
## S8\. bf16 against fp32

Table[S7](https://arxiv.org/html/2610.28958#Sx14.T7)compares bf16 with fp32 for every network with all keys\. The bf16 column evaluates the saved models: weights in bf16 and arithmetic under CUDA autocast, as in the main tables\. The fp32 column uses the fp32 reference weights and IEEE fp32 arithmetic\. Each compiled graph is rebuilt in fp32, so its fixed coefficients are fp32 too\. With all keys, no calibrated quantity is active\. The DeiT\-Tiny and Pythia\-70M results repeat exactly between runs\. MambaIRv2\-Light uses nondeterministic kernels, and two runs differ by up to0\.010\.01dB\.

In fp32, every compiled graph with exact GELU reproduces its reference \(Theorems[1](https://arxiv.org/html/2610.28958#Thmtheorem1)and[3](https://arxiv.org/html/2610.28958#Thmtheorem3), Proposition[1](https://arxiv.org/html/2610.28958#Thmproposition1)\)\. On Pet, the extended, strict and Hadamard graphs match the accuracy and loss of DeiT\-Tiny to four digits\. The extended graph matches on ImageNet\-1k and WikiText\-2, and on Set5 within the run\-to\-run variation\. Withx​σ​\(1\.702​x\)x\\,\\sigma\(1\.702x\), the strict and Hadamard graphs compute the same model and give the same fp32 accuracy\. bf16 changes the accuracy of DeiT\-Tiny by at most0\.460\.46points and the PSNR of MambaIRv2\-Light by at most0\.040\.04dB\.

Pythia\-70M runs in fp32\. In bf16 its validation NLL rises from4\.554\.55to6\.686\.68nats, for the reference and the compiled graph alike\. Only bf16 weights with fp32 arithmetic give4\.564\.56\. The degradation cause is the logits\. They share a large offset that softmax ignores: their median is10611061, while the top two differ by a median of0\.730\.73\. Near10001000, bf16 resolves steps of88, so it loses the ranking of the tokens\. The output projection causes1\.71\.7of the2\.12\.1nats and attention the other0\.40\.4\.

Table S7:bf16 against fp32 with all keys\.Top\-1 accuracy \(%\) for DeiT\-Tiny, PSNR \(dB\) on the Y channel of Set5 for MambaIRv2\-Light, validation NLL \(nats\) for Pythia\-70M\. Sigmoid GELU:x​σ​\(1\.702​x\)x\\,\\sigma\(1\.702x\)\.NetworkModelbf16fp32bf16−\-fp32DeiT\-Tiny, Petreference91\.3691\.33\+0\.03\+0\.03extended91\.3691\.33\+0\.03\+0\.03strict, GELU91\.0691\.33−0\.27\-0\.27Hadamard, GELU91\.2891\.33−0\.05\-0\.05strict, sigmoid GELU90\.7390\.27\+0\.46\+0\.46Hadamard, sigmoid GELU90\.3590\.27\+0\.08\+0\.08DeiT\-Tiny, ImageNet\-1kreference72\.0272\.02\+0\.01\+0\.01extended72\.0172\.020\.000\.00MambaIRv2\-Light×2\\times 2, Set5reference38\.23438\.272−0\.038\-0\.038extended38\.23138\.270−0\.039\-0\.039MambaIRv2\-Light×4\\times 4, Set5reference32\.51132\.512−0\.002\-0\.002extended32\.50232\.507−0\.006\-0\.006Pythia\-70M, WikiText\-2reference6\.6814\.550\+2\.131\+2\.131extended6\.6804\.550\+2\.130\+2\.130
## S9\. Quantization with exact GELU

Table[3](https://arxiv.org/html/2610.28958#Sx2.T3)reports each graph in its deployment configuration: the strict graph withx​σ​\(1\.702​x\)x\\,\\sigma\(1\.702x\)and 12\-bit inputs of its fixed affine nodes, before distillation, and the extended graph with GELU and 8\-bit codes, after Jeffreys distillation\. Table[S8](https://arxiv.org/html/2610.28958#Sx15.T8)compares the strict graph with exact GELU and withx​σ​\(1\.702​x\)x\\,\\sigma\(1\.702x\)under the same PTQ, both before distillation\. The quantized graph has 344 nodes with GELU and 380 with its approximation, 332 and 368 atk=197k=197\. Exact GELU matches no NPU configuration and serves as a comparison\. With either GELU, PTQ costs the strict graph at most1\.51\.5points, against2\.52\.5to3\.93\.9points for the extended graph\.

Table S8:PTQ of the strict graph with exact GELU and withx​σ​\(1\.702​x\)x\\,\\sigma\(1\.702x\)on DeiT\-Tiny/Pet, before distillation, with the PTQ of Table[3](https://arxiv.org/html/2610.28958#Sx2.T3)\. bf16: top\-1 accuracy \(%\) of the float model\.Δ\\Delta: change after PTQ with per\-channel or per\-tensor weight scales\. The approximation columns repeat Table[3](https://arxiv.org/html/2610.28958#Sx2.T3)\.
## S10\. Tensor sizes

NativeQ​K⊤QK^\{\\top\}reads2​N​d2Ndvalues per head and writesN2N^\{2\}\. The unfused strict graph also writes theN2​dN^\{2\}dsumsqi​f\+kj​fq\_\{if\}\+k\_\{jf\}, squares them in place, and reduces overff\. For DeiT\-Tiny that is2\.48×1062\.48\\times 10^\{6\}values per head per image against3\.88×1043\.88\\times 10^\{4\}, a factord=64d=64, which drives the memory column of Table[2](https://arxiv.org/html/2610.28958#Sx2.T2)\. Top\-kkmixing readskkof theNNvalue rows per query, a fractionk/Nk/Nof the value traffic of dense mixing\.