WorksComputer Science
Transformers as Generic Deep Neural Networks: Exact Compilation, the Cost of Removing Activation-Activation Products, and Multi-Agent Attention Clustering
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 least 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- attention 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 from to per 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, for , on Pythia-70M.
Introduction
Transformers [1] 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]. NVIDIA’s Jetson DLA has no matrix-multiply layer [3]. On phones, llm.npu runs the linear layers on the NPU and keeps LayerNorm and attention on the CPU or GPU [4]. Vendors answer with Transformer-specific operators and units for attention, softmax and normalization [5, 6, 7].
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], and PTQ4ViT adds twin-uniform quantizers for the post-softmax and post-GELU activations [9]. FQ-ViT adds power-of-two factors for LayerNorm and a log-integer softmax [10]. RepQ-ViT reparameterizes quantization scales [11], IGQ-ViT groups channels per instance [12], I-BERT replaces the nonlinearities by integer polynomials [13], and SmoothQuant moves activation outliers into the weights of language models [14].
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). We call it the strict graph. Squares replace products, through 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 approximation 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 least scalar nonlinear evaluations per head at and at , whatever the scalar functions, depth or width (Theorem 2).
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, evaluations per head (Proposition 1). With the exponential and the reciprocal it adds no pointwise work (Proposition 2), and with matrix multiplication of two activations the extended compilation adds no work of either kind (Theorem 3). On a GPU, for , the Hadamard and strict graphs run at 1.0 to 1.3 and 1.2 to 1.5 times the latency of this extended graph. Theorems 2 and 3 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, 16], current NPUs expose it [6, 17, 18], and convolutional networks with squeeze-and-excitation gating already use the elementwise product [19, 20].
Clustered attention. The attention weights of a query cluster on a few keys [21, 22, 23] when its scores have a gap (Lemma 1). Queries cluster too [24, 25], and queries close to one point share their top keys (Lemma 2). Top- attention keeps the largest scores of each query [21, 22], the topological rule of bird flocks [26]. 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). Centroids of the query clusters [25] choose the keys before the scores, so the strict graph forms only scores per head (Corollary 2, Proposition 5). One step of the Motsch–Tadmor flocking model is one attention head (Proposition 6).
We test the compilation on three model families: DeiT-Tiny [27] for image classification on Oxford-IIIT Pet [28] and ImageNet-1k [29], MambaIRv2-Light [30] for super-resolution, and Pythia-70M [31] for language modeling.
Related work. Universal approximation gives some network within each error on a compact set [32, 33]. Forming products from squares is classical: tables of quarter-squares multiply by polarization [34], Winograd’s inner product forms the self-terms of each row once and halves the products of a matrix multiplication [35], and expressivity proofs for ReLU networks use [36]. Compilers such as Glow map a model onto the operators a device provides [37]. Privacy-preserving inference decomposes attention, softmax and LayerNorm into primitive operations for cryptographic protocols, usually with polynomial approximations [38, 39, 40]. Multiplication-free training replaces every product by an approximate piecewise-affine operation and trains on that arithmetic [41]. Training-time alternatives simplify LayerNorm [42] or remove it [43, 44]. Top- attention saves memory on long contexts [21, 22, 23], usually by renormalizing the kept scores. Scatterbrain adds a low-rank estimate of the non-selected attention to a sparse one [45], Combiner attends to the rest of the sequence through region summaries [46], and MagicPIG replaces top- selection by sampling to avoid its bias [47]. Clustered attention chooses the kept keys by query centroids and gives the other keys the weights of the centroid [25]; we use its key selection with calibrated centroids. Lookup tables, piecewise-linear units and integer approximations implement scalar nonlinearities in hardware [7, 48, 49].
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 of scalar functions. A graph over the strict basis is a finite acyclic graph whose nodes are of three types:
weight–activation contraction: a fixed affine map , where and are parameters of the graph and do not depend on the input;
unary map: applied entrywise, with ;
routing: copy, reshape, permutation, concatenation, broadcast, masking, and selection of entries by comparisons of computed values (max, 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 , we call 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], multiplies two activations and is not in this basis. The set is a parameter. Shifts such as and scalings such as belong to the preceding affine node, so a unary set needs only the shape of each function.
Definition 2 (Strict unary set). , with .
Each function has one role. The square forms second moments and products: where the squares of the factors are shared across products, as for the rows of , and and in LayerNorm, and polarization, , for an isolated product. The sigmoid gives the exponential, . The inverse square root normalizes LayerNorm and, squared, gives the reciprocal, for . GELU is the MLP activation (Definition 3). The set has no exponential and no logarithm.
Definition 3 (Transform sets). The Transformer transform set is , where
and softmax acts on each row of scores. A model may use the approximation [50] instead, which changes the model. Then GELU is no longer a basic operation: it is omitted from every unary set, and the sigmoid is added where missing. Here , and , , , , , , , are fixed parameters, and one attention head has tokens, head dimension , , , and .
A compiled graph serves a fixed context capacity , and the construction gives one graph for each . 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 is computed exactly by a finite graph over .
We call the graph of Theorem 1 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–6 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 graph , the pointwise work is the number of scalar evaluations of unary maps in one forward pass; it counts evaluations, not nodes. The contraction work is the number of multiply–accumulate steps in its fixed affine nodes and in its products of two activations. The source graph of a transform
is the graph of its defining formula in Definition 3, with each product of two activations as one product node; PW() and MAC() are its work. Score is one product node with PW and MAC per 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 replaces by the graph , its added work is and .
Theorem 2 (Lower bound for product-free compilation). Fix one attention head and any set of scalar functions, and let the entries of , , and range freely over . Every product-free graph that computes Score exactly has PW , and every product-free graph that computes Mix exactly has PW .
The source graphs of Score and Mix make no unary evaluation, so the bounds hold for the added work . 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). It therefore needs at least as many unary evaluations as its target has coordinates that stay linearly independent modulo affine functions; for Score these are all entries.
The strict graph pays unary evaluations per head in Score and in Mix, a factor above the bound of Theorem 2 for Score and above it for Mix. Supplementary § 7 shows how far the bound of Theorem 2 can be raised.
For one DeiT-Tiny block with dense attention (Table 1), the strict graph makes 61 times the unary evaluations of the source block, and 92% of them fall in Score and Mix.
| Transform | Source | Bound, dense / routed | Strict | Strict, routed | Hadamard | Extended |
| Symbolic | ||||||
| LN | ||||||
| softmax | ||||||
| Score | / | |||||
| Mix | / | |||||
| DeiT-Tiny | ||||||
| LN | ||||||
| softmax | ||||||
| Score | / | |||||
| Mix | / | |||||
| Block total |
Table 1. Pointwise work per DeiT-Tiny block. Unary evaluations per instance of each transform; tokens, heads of dimension , MLP width . Source: the source graph (Definition 4), with GELU and dense attention. Bound: Theorem 2 for dense scores, Corollary 2 for the routed scores. Strict: Theorem 1; routed: Proposition 5, with in the DeiT-Tiny rows. Hadamard: Proposition 1. Extended: Theorem 3. Block totals count both LayerNorms.
Activation–activation products remove the cost
Theorem 2 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).
| Accelerator | Unary maps on the NPU | Strict graph | Hadamard graph | Extended graph |
| Arm Ethos-U55/U65 [68] | Exp, Log, Rsqrt, GELU, Sigmoid, Tanh | Whole | Whole | Whole |
| Arm Ethos-U85 [68] | Exp, Log, Rsqrt, GELU, Sigmoid, Tanh | Whole | Whole | Whole |
| VeriSilicon VIP [69] | Exp, Log, Rsqrt, GELU, Sigmoid, Tanh | Whole | Whole | Whole |
| TI TDA4VM, C7x with MMA [70] | Exp, Log, Sqrt, GELU, Sigmoid, Tanh; power by a constant | Whole | Whole | Whole |
| Rockchip RK3588 [71] | GELU, Sigmoid, Tanh; power with exponent , 2 or 3 | Whole | Whole | Whole |
| Renesas R-Car V4H/V4M, CNN-IP and DSP [72] | CNN-IP: ReLU, Sigmoid, Tanh | DSP: Rsqrt | DSP: Rsqrt | DSP: MatMul, softmax, LayerNorm, GELU |
| NVIDIA Jetson Xavier/Orin DLA [3] | ReLU, Sigmoid, Tanh, Abs, Sin, Cos, Atan; INT8 power and division by a constant | Whole | Whole | Host: MatMul |
| Google Edge TPU [2] | ReLU, Sigmoid, Tanh, Rsqrt | Whole | Whole | Host: MatMul, row-wise softmax |
| Open-source NVDLA IP [73] | ReLU, Sigmoid, Tanh | Host: Rsqrt | Host: Rsqrt | Host: MatMul, softmax, LayerNorm Rsqrt |
| Arm Ethos-N78 [74] | ReLU, Sigmoid, Tanh | Host: Rsqrt | Host: Rsqrt | Host: MatMul, softmax, LayerNorm Rsqrt |
Table S1. Documented NPU support of the dense compiled graphs. Whole-graph compilation on the devices is future work.
Definition 5 (Hadamard basis). The Hadamard basis has the three node types of and a fourth, the Hadamard product of two activations with broadcasting.
Definition 6 (Hadamard unary set). .
With the Hadamard product, the square is , the exponential is , and the reciprocal is .
Proposition 1 (Sigmoid and inverse square root suffice with the Hadamard product). Every finite Transformer block over is computed exactly by a finite graph over in which softmax adds per head and every other transform adds .
We call this graph the Hadamard graph. Its products add per head to Score and Mix and to softmax. For one DeiT-Tiny block it makes unary evaluations, against for the strict graph (Table 1).
The 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). .
is the set of scalar functions in the defining formulas of : 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 is computed exactly by a finite graph over with for every transform . For Score and Mix a separate reduction node adds per head; for every other transform .
Matrix multiplication of two activations keeps the products of and , which a Hadamard product writes to memory, inside the MAC array (Supplementary § 9).
Definition 8 (Extended basis). The extended basis adds to matrix multiplication (MatMul) and batched matrix multiplication (BMM) of two activations. With they form the activation–activation products. For a common , .
Theorem 3 (Exact compilation with no added work). Every finite Transformer block over is computed exactly by a finite graph over , and this compilation has for every transform .
We call the graph of Theorem 3 the extended graph. It is the source graph of each transform (Definition 4), so it adds no work: and stay one matrix-multiplication node each, with multiply–accumulate steps per head and no unary evaluation. Theorems 2 and 3 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 into time, let and be the throughputs of the MAC array and the pointwise unit, and .
Corollary 1 (Time separation). Fix an -head block. Assume that unary maps run only on the pointwise unit, at rate at most , and that the extended graph runs Score and Mix on the MAC array at rate . In every transform-wise product-free compilation, the Score and Mix subgraphs take at least ; in the extended graph they take . The first time is longer whenever , in particular whenever .
The strict graph makes more than unary evaluations in Score and Mix, so on them it is at least times slower than the extended graph. For DeiT-Tiny (, ) the threshold is 96.6. The extended basis maps onto a current NPU without a Transformer-specific unit; Figure 1 shows the unit that runs each node.

Figure 1. Three exact compilations of a Transformer block. Each row lists the nodes of one graph under the NPU unit that runs them; tokens, heads of dimension . *if used in the source graph.
Attention weights cluster on a few keys
Fix one query , the keys and the values , the rows of and , and . Under a mask, counts the valid keys of the row. The scores are , sorted as , the attention distribution is , and the attention output is . Top- attention keeps the support and drops the other keys, the set . The tail mass is the attention outside , and is the score gap. The attention weights cluster on when is large. Queries cluster too.
Lemma 1 (Score gap). .
Lemma 2 (Shared support). Let and . If and , the scores have the same top keys as .
By Lemma 2, queries within of one point share their top keys when each meets the gap condition, and by Lemma 1 each of them puts at most of its attention outside these keys.
Top-k attention with a tail-mass estimate
The softmax over the kept scores, for , needs only . The dense distribution on is . Write for the mean of the kept values under , for the plain mean of the dropped values, and for their mean under ; since every softmax weight is positive. Then .
Definition 9 (Tail-mass top- attention). For a tail mass , the estimate of and the output are
Calibrated mode uses one constant per block, the mean tail mass of the reference model over calibration data. Exact mode uses . Tail drop, the usual top- attention, uses . For , , and , so and is the mean of the values; calibrated and exact mode coincide. For the map is dense attention.
The sparse transform set is with softmax and value mixing replaced by this map. This changes the model. Its source graph, used to count work, computes in the all-values form
which reads only the kept values and the sum of all values. Value mixing then costs multiply–accumulate steps per head instead of , plus the sum of all values, kept as a prefix sum under a causal mask. Exact mode also forms all scores for the dense normalizer.
Proposition 3 (Sparse attention compiles exactly). *Every finite block over is computed exactly by a finite graph over , and by a finite graph over with for every transform .
Let be what top- attention reads: the kept keys, their scores and the values.
Theorem 4 (Tail-mass estimate is unbiased and optimal). Let the scores and the values be random, with for every . Assume that the tail scores are exchangeable given : their conditional law is invariant under permutations of .
With , the estimate satisfies and . Both are unbiased, and they minimize and among all functions of . In exact mode the same holds given , with .
Tail drop has conditional bias and . Its conditional distribution bias vanishes only when .
Theorem 4 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 is mean-independent of . Among constant tail masses, is minimal at , which the calibrated estimates.
Proposition 4 (Error decomposition). For every query,
with . Tail drop has output error .
Proposition 4 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 over . When the tail is uniform, on , so and exact mode has no error, while tail drop keeps the error . In the expected distribution error, only depends on , so the best constant is , which equals when and are uncorrelated.
Centroids factor the selection scores
Exact top- forms all scores before it selects, so its strict graph makes at least unary evaluations per head (Theorem 2). When the queries cluster, the keys can be chosen before the scores, and only the kept scores of each query are formed.
Corollary 2 (Cost of selected scores). Fix one head and , and let each query select keys by a rule that is constant on some open set of inputs. Every product-free graph that computes the selected scores has . Given the selected key indices, a graph over computes them with .
For each head, k-means on calibration queries gives centroids , the rows of . Query goes to its nearest centroid , the one that maximizes the affine score , and the assignment factors the queries as . The selection scores , a gather of the centroid scores , replace , and the routed support of query is the top keys of its row. It is the exact top- support of whenever the gap condition of Lemma 2 holds for . Like TopK of the scores, it is constant on an open set of inputs, so Corollary 2 bounds its scores. The source graph of the routed map is the all-values form (1) on the routed support.
Proposition 5 (Routed support). For fixed centroids and an -head block, tail-mass attention with a constant tail mass on the routed supports is computed exactly by a graph over whose Score and Mix subgraphs make unary evaluations, and by a graph over with .
In both graphs the assignment scores and the centroid scores are fixed affine maps with multiply–accumulate steps, and the assignment and the selection are routing, so the router adds no unary evaluation. Proposition 4 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], agent at position with velocity follows
where and run over all agents and is a decreasing influence function.
Proposition 6 (Flocking step). For with , , so is one head of distance-based attention [52] with queries , keys , a bias per key and values . The top keys of agent are its nearest agents.
Tail-mass attention (Definition 9) gives the nearest agents of agent the weights and each of the other agents the weight . Proposition 4 gives the error of this top- flocking step exactly, and Theorem 4 applies when the far positions are exchangeable given the kept scores, velocities and . By the proof of Proposition 6, Lemma 2 holds for these scores with replaced by , 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- tail-mass attention, and evaluate them before training. With all keys kept, the compiled models match their references: 91.36% against 91.36% on Pet, 72.01% against 72.02% on ImageNet, 32.51 dB against 32.51 dB on Set5, and a token negative log-likelihood (NLL) of 4.5496 against 4.5496 on WikiText-2. The strict and extended graphs compute the same model exactly (Theorems 1 and 3). Only model changes, such as top- attention, and rounding change accuracy.
The strict graph pays the predicted cost
Table 2 measures the cost of the strict graphs of Theorem 1 and Proposition 3 on a GPU. The reference calls fused attention and LayerNorm kernels. The extended graph runs at 2.5 to 5.6 times the reference latency in Table 2 and Table 4. The strict graph takes 1.2 to 2.4 times the latency and, at top-64, 2.3 times the peak memory of the extended graph. The GPU has for squares (Methods), far below the threshold of Corollary 1, so this slowdown does not come from the bound of Theorem 2. It comes from the construction: times more pointwise work than the bound, and operands per head that the implementation writes to memory. A per-module profile puts 73 to 77% of the added time in Score and Mix (Supplementary Table S2). A merged GPU kernel avoids these writes; no transform-wise product-free graph avoids the bound of Theorem 2.
| Extended | Hadamard | Strict | Strict, polarization | |||||||||
| Acc. | Latency | Memory | Acc. | Latency | Memory | Acc. | Latency | Memory | Acc. | Latency | Memory | |
| Top- support | ||||||||||||
| 16 | 86.24 | 3.28× | 1.62× | 83.51 | 4.18× | 8.72× | 84.08 | 5.04× | 8.65× | 83.95 | 68.3× | 47.1× |
| 32 | 89.23 | 3.89× | 2.32× | 87.46 | 4.73× | 8.72× | 87.98 | 5.37× | 8.65× | 87.71 | 76.1× | 47.1× |
| 64 | 90.35 | 4.88× | 3.70× | 89.59 | 5.75× | 8.72× | 89.78 | 7.14× | 8.65× | 89.70 | 93.1× | 47.1× |
| 197 | 91.36 | 5.41× | 2.45× | 90.35 | 10.5× | 17.3× | 90.73 | 13.0× | 17.2× | 90.57 | 132× | 63.1× |
| Routed support | ||||||||||||
| 16 | 80.13 | 3.35× | 1.54× | 78.60 | 3.48× | 2.21× | 78.22 | 4.73× | 2.19× | 78.44 | 14.1× | 5.90× |
| 32 | 87.14 | 4.03× | 2.28× | 85.66 | 4.10× | 3.56× | 85.96 | 4.73× | 3.55× | 85.55 | 22.3× | 11.0× |
| 64 | 89.81 | 4.37× | 3.73× | 88.63 | 5.56× | 6.27× | 88.88 | 6.67× | 6.23× | 88.99 | 40.1× | 21.2× |
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 takes 2.20 ms per batch of 32 and 62 MB (Methods). Hadamard: Proposition 1. Strict: Theorem 1; polarization: polarization for every product. The extended graph uses GELU, the others . Top-: the largest exact scores. Routed: keys chosen by 32 query centroids before the scores (Methods). At both supports hold every key.
Table 4. DeiT-Tiny compiled with calibrated tail-mass top-. Pet: top-1 accuracy (%) of the compiled model, Jeffreys divergence to the reference, accuracy after one epoch of Jeffreys distillation (mean s.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 is . References: 91.36% (Pet), 72.02% (ImageNet).
| PV | Compiled | Distilled | Latency | Compiled | ||
| 1 | 0.01 | 15.73 | 6.26 | 41.22 0.60 | 2.45 | 10.84 |
| 2 | 0.01 | 42.95 | 4.07 | 65.30 0.47 | 2.85 | 27.79 |
| 4 | 0.02 | 67.10 | 2.20 | 78.22 0.18 | 2.99 | 45.03 |
| 8 | 0.04 | 79.50 | 0.97 | 84.91 0.15 | 3.06 | 57.20 |
| 16 | 0.08 | 86.24 | 0.38 | 88.56 0.19 | 3.28 | 64.66 |
| 32 | 0.16 | 89.23 | 0.14 | 90.18 0.08 | 3.89 | 68.81 |
| 64 | 0.32 | 90.35 | 0.045 | 90.43 0.18 | 4.88 | 70.83 |
| 96 | 0.49 | 90.76 | 0.016 | 90.86 0.22 | 5.32 | 71.50 |
| 128 | 0.65 | 91.11 | 0.0055 | 91.11 0.00 | 5.61 | 71.82 |
| 197 | 1.00 | 91.36 | 0.0002 | 91.36 0.00 | 5.41 | 72.01 |
Table 4. DeiT-Tiny compiled with calibrated tail-mass top-. Pet: top-1 accuracy (%) of the compiled model, Jeffreys divergence to the reference, accuracy after one epoch of Jeffreys distillation (mean s.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 is . References: 91.36% (Pet), 72.02% (ImageNet).
With the same GELU approximation, the strict graph stays within 0.6 points of the Hadamard graph and of its polarization variant with top- support, and within 0.4 points routed. Two runs of one strict configuration differ by up to 0.5 points with top- support and 1.5 points routed, since the tail mass and centroids are calibrated on augmented training images. Squares cost no accuracy beyond run-to-run variation. With top- support, polarization makes 1.9 times the unary evaluations and, for , runs 13 to 14 times slower with 5.5 times the memory (Supplementary § 11). In integer arithmetic both identities are exact (Methods).
The elementwise product removes most of the strict cost
With top- support and , the Hadamard graph of Proposition 1 runs at 1.2 to 1.3 times the latency of the extended graph, against 1.4 to 1.5 for the strict graph, at similar memory (Table 2). Its measured unary counts equal Table 1: per image at , against for the strict graph. Its remaining cost is the products of per head, which this implementation writes to memory (Supplementary Table S2). With top- support, the approximation of GELU costs the Hadamard graph 0.7 to 2.6 and the strict graph 0.3 to 2.3 points; with GELU, the Hadamard graph stays within 0.1 points of the extended graph.
NPUs provide the Hadamard basis
Supplementary Table S1 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, 54]: 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 replaces GELU by , so it uses the reduced strict basis . The extended graph keeps GELU and the matrix products of . 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.
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: . Strict: the reduced strict graph, before distillation. Extended: the Jeffreys-distilled extended graph.
| PV | Graph | Nodes | bf16 | Per-channel PTQ | Per-channel | Per-tensor PTQ | Per-tensor | |
| 16 | 0.08 | strict | 380 | 84.08 | 82.61 | −1.47 | 83.02 | −1.06 |
| 32 | 0.16 | strict | 380 | 87.98 | 87.30 | −0.68 | 87.27 | −0.71 |
| 64 | 0.32 | strict | 380 | 89.78 | 89.72 | −0.05 | 89.64 | −0.14 |
| 197 | 1.00 | strict | 368 | 90.73 | 90.27 | −0.46 | 89.75 | −0.98 |
| 16 | 0.08 | extended | 247 | 88.58 | 86.13 | −2.45 | 84.90 | −3.68 |
| 32 | 0.16 | extended | 247 | 90.19 | 86.26 | −3.92 | 86.54 | −3.65 |
| 64 | 0.32 | extended | 247 | 90.76 | 87.44 | −3.33 | 87.16 | −3.60 |
| 197 | 1.00 | extended | 235 | 91.36 | 88.74 | −2.62 | 88.50 | −2.86 |
Table 3.
PTQ changes the accuracy of the strict graph by −1.47 to −0.05 points with per-channel weight scales, and by −1.06 to −0.14 with one scale per weight tensor. On the extended graph it changes accuracy by −2.5 to −3.9 points.
The tail-mass estimate beats tail drop
Image classification. Table 4 reports Oxford-IIIT Pet and ImageNet-1k with calibrated tail mass. The Jeffreys divergence between the predictive distributions of the compiled and reference models falls from 0.98 at to 0.043 at and with all keys. One epoch of distillation [55] against the reference with the Jeffreys divergence [56], with trainable, brings top-64 to over five seeds. On ImageNet, without training, top-64 is within 1.19 points of the reference.
Image restoration. MambaIRv2-Light [30] is a super-resolution model that combines state-space scans with windowed attention over positions. Its attention and LayerNorm modules compile as in DeiT-Tiny, and the state-space scans stay as they are. Table 5 reports and super-resolution on Set5 [57], before and after three epochs of fine-tuning on DIV2K [58]. Before training, exact tail mass gives the highest PSNR at every , and top-64 is within 0.03 dB of the reference. After fine-tuning, exact mode and tail drop end within 0.06 dB of each other for .
| Tail drop pre | Tail drop post | Calibrated pre | Calibrated post | Exact pre | Exact post | Calibrated pre | Calibrated post | |
| 0 | – | – | 30.22 | 31.10 | 30.22 | 31.10 | 35.98 | 37.24 |
| 1 | 22.11 | 30.64 | 30.45 | 31.32 | 30.95 | 31.73 | 36.17 | 37.36 |
| 2 | 26.05 | 31.63 | 30.62 | 31.55 | 31.36 | 31.97 | 36.35 | 37.52 |
| 4 | 29.66 | 32.07 | 30.85 | 31.81 | 31.71 | 32.11 | 36.50 | 37.62 |
| 16 | 31.99 | 32.37 | 31.55 | 32.23 | 32.19 | 32.34 | 37.05 | 37.90 |
| 64 | 32.43 | 32.47 | 32.27 | 32.45 | 32.48 | 32.51 | 37.90 | 38.13 |
| 256 | 32.51 | 32.51 | 32.51 | 32.51 | 32.50 | 32.52 | 38.23 | 38.23 |
Table 5. MambaIRv2-Light on Set5. PSNR (dB) before (pre) and after (post) three epochs of L1 fine-tuning on DIV2K, selected on DIV2K training crops (Methods). References: 32.51 dB (×4), 38.24 dB (×2). At all weight sits on the uniform tail, which tail drop cannot express; at the modes coincide and the tail-drop cells repeat the calibrated run.
Language modeling. Pythia-70M [31] is a decoder-only model with a causal mask, evaluated on WikiText-2 [59] with tokens. Causal rows have different numbers of valid keys, so a single calibrated does not apply, and we use exact tail mass. Table 6 shows that exact tail mass keeps the NLL within 0.01 nats of the reference down to , while tail drop loses 0.04 nats there.
| Exact tail mass NLL | Exact tail mass NLL | Exact tail mass PPL | Tail drop NLL | Tail drop NLL | Tail drop PPL | ||
| 128 | 4.5496 | 0.0000 | 94.59 | 4.5496 | 0.0000 | 94.59 | 0.000 |
| 64 | 4.5497 | 0.0002 | 94.61 | 4.5497 | 0.0002 | 94.61 | 0.004 |
| 32 | 4.5513 | 0.0017 | 94.75 | 4.5567 | 0.0072 | 95.27 | 0.023 |
| 16 | 4.5584 | 0.0088 | 95.43 | 4.5885 | 0.0390 | 98.35 | 0.062 |
| 8 | 4.5822 | 0.0326 | 97.73 | 4.6811 | 0.1316 | 107.89 | 0.123 |
| 4 | 4.6534 | 0.1038 | 104.94 | 4.9232 | 0.3737 | 137.44 | 0.205 |
| 2 | 4.8267 | 0.2771 | 124.80 | 5.5418 | 0.9923 | 255.14 | 0.313 |
| 1 | 5.1804 | 0.6308 | 177.76 | 6.6381 | 2.0885 | 763.65 | 0.440 |
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, over validation tokens in float32. is the mean omitted tail mass of top- on the dense scores of 4 random training minibatches of 4 sequences. Reference: NLL 4.5496, PPL 94.59.
Figure 2 compares the three modes. On DeiT-Tiny/Pet, exact mode at beats tail drop at for all tested ; calibrated mode does so for . At equal , calibrated mode gains 73.8 points over tail drop. The per-head optimality of Theorem 4 does not order model accuracy: for calibrated mode beats exact mode. On Pythia-70M, exact mode at beats tail drop at for every . On MambaIRv2-Light, exact mode is the best of the three at every . Calibrated mode falls below tail drop there for , since one constant per block fits poorly a per-query tail mass with s.d. about 0.2 at a mean of 0.57 ().

Figure 2. Tail-mass estimate against tail drop. Quality of the compiled model before any training, as a function of the number of kept keys . (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 (); calibrated mode does not apply to causal rows, whose numbers of valid keys differ. (c) MambaIRv2-Light super-resolution on Set5, PSNR.
Clustered queries cut the cost of the strict graph
The measured unary counts equal Proposition 5 at every tested . At the routed strict DeiT-Tiny graph uses instead of the reference memory and makes instead of unary evaluations per image (Table 2), at 78.22% against 84.08% accuracy; its latency falls from 5.0 to 4.7 times the reference. With twice the keys it matches exact top-: at it reaches 85.96% with 37% of the unary evaluations and 41% of the memory of exact top-16.
The routed support is accurate where the queries of a cluster attend to the same keys. On DeiT-Tiny it holds 83% to 95% of the attention mass of exact top- for to 64, and 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 by 9% at . Routing leaves the extended graph unchanged at and cuts the Hadamard graph’s memory by 75% at .
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 prices, and a MAC array that accepts two activation operands only keeps the products of and out of memory.
Theorem 2 applies to transform-wise compilation, which keeps the attention contractions as subgraphs; a compilation that never forms is outside it (Supplementary Section S1). Corollary 1 needs hardware whose MAC array outruns its pointwise unit by more than .
The construction extends to other blocks. RMSNorm [42] compiles as LayerNorm without the mean. A gated MLP such as SwiGLU [60] multiplies two activations, and its SiLU is , 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, top- attention is the topological rule of starling flocks, where each bird follows a fixed number of nearest neighbors [26], 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].
Future work. The latency and memory reported here are GPU measurements, and the NPU placement of Supplementary Table S1 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- attention with a tail-mass term is the multi-agent counterpart of these results.
Methods
Notation
is the class of finite acyclic graphs over a basis . It is closed under composition. We write when a graph in computes exactly. is the polarization graph of : one fixed affine node forms , two squares follow, and one fixed affine node returns . is the norm-expansion graph of when and are available: one fixed affine node forms , one square follows, and one fixed affine node returns , subtracting the two close squares first. For an index tuple , gather. TopK returns indices in descending order of score with a fixed tie-breaking rule.
Compilation lemmas
Each lemma realizes one transform. In this section is (Definition 2) and is (Definition 7).
Lemma 3 (Affine maps, residuals, routing, GELU MLP). Fixed affine maps, residual sums and routing maps are nodes of both bases. is the composition in both bases.
Proof. For the approximation, is one sigmoid after a fixed scaling and one product: , two squares per hidden unit, in the strict basis, and one Hadamard node in the extended basis.
Lemma 4 (LayerNorm). and .
Proof. Let , which is affine. Strict: uses squares and an affine mean, is one unary evaluation per token, and reuses and forms once per token, so it costs one square per entry and one per token. Then is affine in . Extended: is a Hadamard product followed by an affine mean, is one unary evaluation per token, and , where the product with the fixed is affine and is a broadcast Hadamard product.
Lemma 5 (Scores and value mixing). and lie in and in .
Proof. Strict: and , with the norms formed once per row and the sums affine: squares per head for the scores and for the mix. In the mix the two close squares are subtracted per term, inside the node that sums over . Extended: each map is one MatMul or BMM node followed by a fixed scaling.
Lemma 6 (Softmax). lies in and in .
Proof. Let , where the maximum is a routing selection, and , so that . The shift leaves softmax unchanged and keeps in and in , so every inverse square root below acts on a number in . Strict: since for every , , with two sigmoids, one inverse square root and three squares per entry; is affine in , and adds two squares per entry and one inverse square root and one square per row. Extended: , one exponential per entry, and , one reciprocal per row and a broadcast Hadamard product.
Lemma 7 (Tail-mass top- attention). The map of Definition 9 from to , for a fixed calibrated or for , lies in and in .
Proof. Masks are fixed routing and affine maps. We treat three cases.
. Definition 9 gives , a fixed affine map.
. Nothing is dropped and the map is dense attention, covered by Lemmas 5 and 6.
. and are routing. In both modes the graph computes the all-values form (1), which equals Definition 9 because . Its parts are the coefficients , the kept mixing , and the tail term . The kept mixing is the norm expansion of Lemma 5 over the kept values in the strict basis and one product node over values in the extended basis. In calibrated mode, follows Lemma 6 on , with the selected maximum as shift; and are affine in , and the tail term is a fixed affine map of . In exact mode, the dense normalizer is formed from all scores with the dense maximum as shift: , , for (Lemma 6), and . The coefficients are affine in . The tail term is a product of the scalar activation with the -dimensional activation : a norm expansion with once per row and the squares of once per head in the strict basis, and one broadcast Hadamard node with scalar products in the extended basis.
Proofs of Theorem 1, Propositions 1 and 2 and Theorem 3
Proof of Theorem 1. Replace every transform of the block by its strict realization from Lemmas 3–6. Each realization computes its transform exactly, and is closed under composition.
Proof of Proposition 1. Take the strict graph of Theorem 1. Replace each product graph, or , by one Hadamard node , drop the squares of the factors it used, and form each remaining square as . Since , the new graph computes the same function, and its unary maps are those of . Score and Mix become a broadcast Hadamard product and a fixed sum, and , 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 for , and, per row, one inverse square root for (Lemma 6). Its source graph pays one exponential per entry and one reciprocal per row, so softmax adds unary evaluations per head. For the contraction work, the products of Score and Mix cost the multiplications of the source, and each fixed sum adds at most multiply–accumulate steps per head. Softmax adds two products per entry for and one per row for , so per head; its sum over the row and its product are those of the source graph.
Proof of Proposition 2. Replace every transform except Score and Mix by its extended realization from Lemmas 3–6; these use only Hadamard products among the activation–activation products. Each performs the operations of its source graph (Definition 4). Affine maps, residuals, routing and the GELU MLP are basis nodes. LayerNorm performs, per token, an affine mean, the product and 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 for these transforms. Compute Score and Mix as in the proof of Proposition 1, by a broadcast Hadamard product and a fixed reduction. No unary map is added, so , and the reduction adds at most multiply–accumulate steps per head.
Proof of Theorem 3. Replace every transform of the block by its extended realization from Lemmas 3–6. Each realization computes its transform exactly, and is closed under composition. Every transform except Score and Mix has the realization of the proof of Proposition 2, with . Score and Mix are single MatMul or BMM nodes of the source shape: and before and after. Hence for every transform.
The bases and are not nested. With , Theorems 1 and 3 also hold in the nested bases , since enlarging the unary set keeps every graph valid.
Proof of Theorem 2
The proof follows the nonlinear rank of the target. is an arbitrary set of real functions. For a set write for the restrictions to of affine functions on . For , the nonlinear rank
counts the coordinates of that stay linearly independent on after adding affine functions.
Lemma 8 (Fixed routing on a set dense in a ball). Let be a finite product-free graph with inputs in , and let be a nonempty open set. There is a set and an open ball such that is dense in and every routing decision of is the same at every point of .
Proof. has 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 of with a given joint outcome form a finite partition of . A finite union of nowhere dense sets is nowhere dense, and is not, so some part is not nowhere dense: its closure contains an open ball , which we may take inside . Then is dense in .
No continuity is used: the outcome sets may be arbitrary, so needs no continuity or measurability.
Lemma 9 (Affine reduction). Let be product-free with outputs , let all routing of be constant on a set , and let be the outputs of its unary evaluations, , viewed as functions on . Then there are affine and constants with on
Proof. By induction along a topological order, every value in is on an affine function of . Inputs are. A fixed affine node maps affine functions to affine functions. A routing node acts on as a fixed 0/1 selection matrix. A unary node outputs some . No node multiplies two values, so the induction never leaves the affine functions of .
Lemma 10 (Pointwise work bounds nonlinear rank). If a product-free graph computes exactly on a set on which its routing is constant, then .
Proof. By Lemma 9, every equals modulo . In the ambient quotient of all real functions on by , the classes of lie in the span of the unary-output classes. Their span therefore has dimension at most .
Lemma 11 (Rank of quadratic forms). Let be dense in an open ball , and let be homogeneous quadratic polynomials on such that each has a monomial, with nonzero coefficient, that no other has. Then .
Proof. Suppose agrees on with an affine function. Both sides are continuous and is dense in , so they agree on . 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 only has is times a nonzero number, so every vanishes.
Proof of Theorem 2. Let be a product-free graph with inputs in that computes exactly, and take and from Lemma 8 with . The entry is a homogeneous quadratic polynomial, and no other entry has its monomials . Lemma 11 gives , and Lemma 10 gives . For Mix, the entry , , has the monomials , which no other entry has, so Lemmas 11 and 10 give .
Proof of Corollary 1. A transform-wise product-free compilation of an -head block contains its own Score and Mix subgraph for each head, each exact for all arguments and sharing no unary evaluation with the others, so these subgraphs have by Theorem 2. Unary maps run only on the pointwise unit, at rate at most , so they take at least . In the extended graph, Score and Mix have and and, by assumption, take . The first time exceeds the second exactly when , which is below . The strict graph of Theorem 1 has in Score and Mix (Lemma 5), hence a pointwise time of at least times the extended time.
Proofs for clustered attention
Proof of Lemma 1. The normalizer is at least , and the tail sum is at most , so .
Proof of Lemma 2. Let . For every key, . For and , , so every key of scores above every key of under .
Proof of Proposition 3. Exactness: replace softmax and value mixing by the realization of Lemma 7 in each basis, and the other transforms as in Theorems 1 and 3. Work in the extended basis: for the map is an affine average and for it is dense attention, both equal to their source graphs. For the source graph is the all-values form (1) with the of the mode, and the extended realization of Lemma 7 is this graph. TopK and gather are routing. The softmax follows Lemma 6, 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 over values. The tail term is a fixed affine map in calibrated mode and one broadcast product node with scalar products in exact mode. Hence for every transform in both modes.
Proof of Theorem 4. (i) Given , the normalizer is a symmetric function of the tail scores, so the tail weights , , are exchangeable given , and is the same for all . These values sum to , so each equals . For , and is a function of , so . With this is . Since is part of and is linear in , . The weights lie in and , so and are 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, is observed. Given , is a symmetric function of the tail scores, so they stay exchangeable given . Then is the same for all and sums to over , so it equals , and for . This is with . (ii) For , and , so . By (i), , and for , so .
Proof of Proposition 4. By Definition 9, , and . Subtracting, . For this is . For the distribution, on , and on . Squaring and summing, the cross term is , since , which leaves .
Proof of Corollary 2. Choose an open set of inputs on which the selection is constant, take and from Lemma 8 inside , and write the selected key indices of query as . The selected score has the monomials , which no other selected score has, since the keys of a query are distinct. Lemmas 11 and 10 give . For the upper bound, routing gathers the keys of each query, each selected score costs squares of , and the norms of the queries and the keys cost (Lemma 5).
Proof of Proposition 5. The assignment scores and the centroid scores are fixed affine maps of and , with multiply–accumulate steps each. TopK over centroids, TopK over keys for each centroid, and the gather of each query’s list are routing. The selected scores cost squares per head (Corollary 2), and the kept mixing of Lemma 7 costs (Lemma 5). With a constant tail mass the tail term is a fixed affine map of . In the extended basis the scores and the mixing are product nodes over keys, and every unary map is one of the source graph.
Proof of Proposition 6. . The first factor does not depend on and cancels against the same factor in the sum over , which leaves the softmax. The score of agent equals , whose first term does not depend on ; since , the largest scores belong to the nearest agents. Lemma 2 holds for these scores with replaced by : the bias of agent enters the scores of every query equally and cancels in each comparison of its proof.
Models and data
DeiT-Tiny. We use the timm [62] DeiT-Tiny [27] (patch 16, input, ). For Oxford-IIIT Pet [28] (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 reaches 91.36%. Pet has no validation split. We report its test split, and no step selects on it. For ImageNet-1k [29] we use the pretrained checkpoint (72.02%).
MambaIRv2-Light. We use the released and lightweight super-resolution weights [30]. The attention acts on windows, so . Training uses DIV2K [58] patches of low-resolution pixels; evaluation reports PSNR on the Y channel of Set5 [57] with the standard border crop.
Pythia-70M. We use EleutherAI’s Pythia-70M [31] with eager attention on non-overlapping 128-token windows of WikiText-2 (raw) [59], 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- scores of every query. The block’s is 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 for each query at run time from the full softmax normalizer. Supplementary § 12 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 centroids to at most 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 top keys of , under the causal mask for Pythia-70M. Without a causal mask, each centroid keeps its top keys and each query takes the list of its centroid, so no matrix is formed. For causal routing, the implementation materializes an matrix of centroid selection scores and forms valid-value means with a dense lower-triangular contraction; keeping each centroid’s top- keys and the value sum over successive prefixes removes both dense operations. In calibrated mode and with tail drop the graph gathers the routed 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. For the strict graph with GELU at , 32 and 64, the latency benchmark gives 4.19, 3.89 and 5.41 times the reference latency with the routed support against 4.34, 4.58 and 6.19 with exact top-; the extended graph gives 3.35 to 4.37 against 3.28 to 4.88, and its peak memory changes by less than 5%. Calibrated mode uses the mean mass outside the routed support on the calibration minibatches of the top- runs. 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- support, 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 at is 76% and 92% of the top- mass on DeiT-Tiny and 89% and 93% on Pythia-70M.
Distillation and fine-tuning
For DeiT-Tiny on Pet we distill [55] the compiled model against the frozen reference for one epoch with AdamW (batch 64, learning rate , weight decay 0.05, cosine schedule without warm-up, gradient clipping at 1.0) and loss , with (Jeffreys) or (cross-entropy), over seeds 42 to 46. Supplementary § 13 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 mass is trainable, a scalar parameter per block clamped to in the forward pass. For MambaIRv2-Light we fine-tune for three epochs with AdamW (batch 8, learning rate , weight decay , cosine schedule, gradient clipping at 1.0) on the 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 at . 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 most 0.46 points and the PSNR of MambaIRv2-Light by at most 0.04 dB against fp32 (Supplementary § 14). 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 at of the largest has a square at 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], and the lookup-table or piecewise-linear units of the NPU approximate its unary nodes over the calibrated input range [48, 49].
Simulation and calibration. We simulate each unit in fp32 [54], with the integer codes held in fp32 tensors. fp32 holds every integer up to , 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 below , a factor 3.7 below 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 with and or with and , 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 to points. 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 , the sums and differences lie in . 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 by four, or by two, before accumulation gives the integer product exactly. Each product has magnitude at most , so a signed 32-bit accumulator holds a dot product of every length .
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 under torch.compile in 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 plus the final LayerNorm: for the Hadamard graph and for the strict graph with GELU. The implementation of the extended graph forms the squares of its 25 LayerNorms with a unary square node, so its count adds to that sum. With the strict graph forms this product from two squares, more per block.
The GPU ratio. The RTX 4070 Ti SUPER has 66 Ada streaming multiprocessors at a boost clock of 2.61 GHz. 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]. This gives T/s, T/s and .
Numerical conventions
The compiled LayerNorm uses the of each reference: for DeiT-Tiny and for MambaIRv2-Light and Pythia-70M. Softmax normalization divides by the max-shifted partition sum . 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 to . The differences between the compiled and reference models in Table 2 therefore come from bf16 weights and arithmetic. The implementation of the strict graph evaluates 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], ImageNet-1k [29], DIV2K [58], Set5 [57] and WikiText-2 [59]. Pretrained weights come from timm, the MambaIRv2 release and the Hugging Face hub.
Code availability
The compiler, the experiment configurations and the scripts that produce every table and figure are released under the MIT license at https://github.com/iceslice0/transformer-to-dnn.
Tightness and scope of the bound
Squares only. With and one nonlinear layer, 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, 65] then gives strict graphs with for products, so no bound holds for this , and the factor between the strict graph of Theorem 1 and Theorem 2 is not forced. Conversely, on the set of Lemma 8 a graph over with PW squarings is an arithmetic circuit with PW nonscalar multiplications, and nonscalar multiplications never exceed the total arithmetic cost [66]. For , a lower bound of order for this would therefore prove that the exponent of matrix multiplication is at least , an open problem. For fixed , and the theorem is tight in order. MAC arrays and tensor units run the classical product, and the strict graph follows it.
Unrestricted . On a bounded box, Score is computed by a product-free graph with unary evaluations, so no argument that ignores the regularity of can improve Theorem 2 beyond the additive . Map the inputs affinely into . For let send , written in binary with infinitely many zero digits, to the number whose digit at position is the -th digit of and whose other digits are zero. The affine sum interleaves the digits of all inputs, has infinitely many zero digits, and so determines every . One further unary map per output, , decodes the score. The total is 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 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, for DeiT-Tiny, below the pointwise work of the source block. A compilation that never forms is therefore outside Theorem 2. The theorem concerns the attention contractions as transforms, which is the form in which every Transformer implementation and every NPU operator set presents them.
NPU operator support
Table S1 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 in and , 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 product , 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 uses , 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]. Compiling the graphs with these toolchains and running them on the devices is future work.
The 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]. 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]. It can hold every function of and , 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: a CNN-class NPU provides the Hadamard basis . There, and need no pointwise work, since a broadcast Hadamard product followed by a fixed sum computes them (Proposition 2). With the sigmoid and the inverse square root, the Hadamard basis also runs the rest of the block (Proposition 1). 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 runs on the TDA4VM accelerator and on the R-Car DSP. On the other accelerators top- attention and the routed support keep the selection on the host; Ethos-U and VeriSilicon can instead replace TopK by arg-max passes with masking.
Why the bound counts pointwise work
Write for the minimum number of words moved between a fast memory of words and slow memory, over all schedules of a graph . With bandwidth , every schedule takes time
The unfused strict graph writes the values to memory (Supplementary § 16), so this one schedule has arithmetic intensity and moves far more than . These writes are a property of the schedule, not of the basis. The strict expansion of Score in Lemma 5 has the access pattern of the matrix product it replaces, so the tiling of the matrix product applies. With square output tiles of side , streaming over the reduction index, and small compared with the operands, a fused schedule moves
words per head, where the last two terms are the compulsory traffic of writing the scores and reading and ; for classical (non-Strassen) schedules of the native product the first term is also a lower bound in this regime [76]. A fused strict kernel therefore has the same traffic order as native . Fusion changes neither the number of unary evaluations nor the unit that must perform them. That is why Theorem 2 bounds PW and Corollary 1 rests on the third term. The same tiling applies to a Hadamard product followed by a fixed reduction (Proposition 2): fused, it has the access pattern of the matrix product, so the Hadamard and extended bases differ only in the schedule a compiler chooses.
Where the compiled graph spends its time
Table S2 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 at (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 adds 64.8 ms per batch over the extended graph; 73.3% of it falls in Score and Mix, and 9.8 ms in softmax. The module totals are 117.0 and 52.2 ms per batch, a ratio of 2.2. The profiled reference runs its attention unfused, with , softmax and as separate kernels: it spends 9.0 ms there, against 4.1 ms and 2 MiB in its fused attention kernel, with a module total of 25.9 ms. At and the shares are 74.8% and 76.5%. Score costs the same at every because scores are computed densely; Mix grows with . The routed graph of Table 2 forms only the selected scores: Score falls from 50 to 11 ms per batch and its working memory from 469 to 77 MiB, and the centroid selection adds 9.6 ms.
| Module | Time (ms/batch) | Working memory (MiB) | ||||||||||
| Strict | Hadamard | Strict | Hadamard | |||||||||
| top- | routed | top- | routed | Ext. | Ref. | top- | routed | top- | routed | Ext. | Ref. | |
| Score () | 49.7 | 10.7 | 31.6 | 9.2 | 4.0 | 4.1 | 469 | 77 | 471 | 78 | 14 | 14 |
| Mix () | 7.4 | 11.8 | 4.9 | 7.0 | 5.6 | 2.8 | 81 | 81 | 78 | 78 | 39 | 12 |
| LayerNorm | 23.0 | 22.2 | 17.9 | 17.9 | 17.9 | 5.5 | 16 | 17 | 19 | 19 | 19 | 9 |
| Softmax | 24.9 | 24.0 | 14.0 | 12.7 | 15.1 | 2.1 | 15 | 18 | 9 | 11 | 8 | 28 |
| Centroid selection | — | 9.6 | — | 9.7 | — | — | — | 4 | — | 3 | — | — |
| Linear (qkv, proj) | 3.3 | 3.8 | 4.2 | 3.6 | 4.3 | 5.0 | 7 | 7 | 9 | 9 | 9 | 9 |
| MLP | 8.7 | 9.4 | 5.5 | 5.1 | 5.3 | 6.3 | 83 | 83 | 28 | 28 | 18 | 18 |
Table S2. Per-module GPU time and working memory at in eager execution, summed over the 12 blocks of one batch. Routed: 32 query centroids. Ext.: the extended graph, with GELU; the other graphs use . Ref.: the reference with unfused attention. Softmax: top- with the tail term, dense for Ref.
The Hadamard graph of Proposition 1 forms the same broadcast grid as the strict graph, with one product per term instead of a sum and a square. Its Score takes 31.6 ms per batch, against 49.7 ms for the strict graph, and 471 MiB, the bf16 tensor of the products 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 is 78.2 ms. With routed support its Score falls to 9.2 ms and 78 MiB, the centroid selection adds 9.7 ms, and the module total is 65.2 ms.
The profile runs one kernel per node and synchronizes around every module, so it shows where eager time goes. Table 2 times the compiled forward pass on batches already on the GPU (Methods), where torch.compile fuses the elementwise chains of every graph. At the compiled reference takes 2.20 ms per batch, and the extended, Hadamard and strict graphs take 7.21, 9.18 and 11.08 ms. The strict graph thus takes 1.54 times the time of the extended graph, against 2.2 in the eager module totals. Fused kernels keep the intermediates of a chain in fp32; all accuracies come from the eager bf16 runs.
Polarization and squares
The strict graph forms each product of two activations from squares, by one of two classical identities:
The first, polarization, is the method of quarter-squares [34]. The second, the norm expansion, forms products in expressivity proofs for ReLU networks [36].
Cost. Polarization pays two squares per product. The norm expansion pays one square per product plus the squares and 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. of two matrices then costs squares by polarization and by the norm expansion, and the ratio to the bound of Theorem 2 falls from to . This is Winograd’s precomputation of the self-terms of each row [35], with squares in place of products. The strict graph uses the norm expansion where the squares of the factors are shared, in , , 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 result is a weighted mean of the values, while the squares sum to about ; on DeiT-Tiny this ratio is 65 at and 543 with all keys. In bf16 the order of the operations then sets the error (Table S3). Rounding each partial sum before the subtraction, , gives 57% relative error with all keys. Subtracting the two close squares per term inside the node that sums over keys gives 14% for either identity: by polarization and by the norm expansion. With this order the two identities differ in cost, not in precision. As Brent showed for Winograd’s identity [77], scaling the operands helps further: the fixed affine maps and with cut the error to 2.7%.
| Cancellation | Polarization, per term | partial sums | per term | per term, scaled | |
| 16 | 65 | 4.3% | 9.1% | 5.0% | 1.0% |
| 197 | 543 | 14.1% | 57.4% | 14.4% | 2.7% |
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; is fitted on 8 other images. The cancellation factor is .
Scaling and PTQ. Brent’s scaling and the PTQ scales are the same choice. PTQ gives each tensor a grid with step for bits. The node that forms adds 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 weights share the grid of values several times larger. The scaling , leaves 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 with equality at , and the size of the squares sets the step of the node that subtracts them. PTQ calibration already measures the ranges, so follows from the same statistics, and folds into the fixed affine maps that produce and and 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 inside still sets the number of bits. The strict graph in this paper applies no , and its fixed affine nodes take 12-bit input codes. Brent’s scaling can reduce this bit width.
Tail-mass ablation on DeiT-Tiny
Table S4 compares the tail modes on Pet before training, and after Jeffreys distillation with trainable . A fixed small tail mass () behaves like tail drop: the omitted mass must be estimated. Table S5 compares the calibrated , 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 within 0.012, and within 0.001 for , while single queries spread widely around them.
| tail drop | fixed | calibrated | exact | calibrated, distilled | |
| 1 | 2.53 | 2.78 | 15.73 | 8.69 | 41.89 |
| 2 | 3.16 | 2.86 | 42.95 | 21.31 | 64.57 |
| 4 | 2.83 | 3.11 | 67.10 | 58.60 | 78.09 |
| 8 | 5.70 | 5.51 | 79.50 | 81.77 | 84.71 |
| 16 | 39.44 | 39.33 | 86.24 | 88.80 | 88.58 |
| 32 | 81.71 | 82.07 | 89.23 | 90.84 | 90.19 |
| 64 | 89.10 | 88.91 | 90.35 | 91.36 | 90.76 |
Table S4. Tail modes on DeiT-Tiny/Pet, top-1 accuracy (%). The last column is the saved one of five Jeffreys-distilled runs with trainable , the run with the highest training accuracy.
| calibrated mean , training | exact , test | |
| 1 | 0.7825 | 0.7943 0.1540 (0.0007, 0.9925) |
| 2 | 0.7139 | 0.7229 0.1703 (0.0004, 0.9852) |
| 4 | 0.6294 | 0.6349 0.1839 (0.0004, 0.9710) |
| 8 | 0.5278 | 0.5300 0.1885 (0.0001, 0.9438) |
| 16 | 0.4116 | 0.4125 0.1770 (0.0000, 0.8915) |
| 32 | 0.2826 | 0.2831 0.1475 (0, 0.7920) |
| 64 | 0.1511 | 0.1513 0.0980 (0, 0.6052) |
| 96 | 0.0811 | 0.0814 0.0607 (0, 0.4286) |
| 128 | 0.0394 | 0.0398 0.0330 (0, 0.2627) |
| 197 | 0 | 0 |
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 s.d. within a block averaged over blocks (min, max).
This spread leaves room between the two modes. Calibrated mode uses and exact mode . Between them lies the conditional mean for any statistic of what top- attention reads, such as the log-sum-exp of the kept scores, the -th score and the number of dropped keys. Its expected squared error is never larger than that of the constant, since . Predicting the dropped partition sum as , instead of itself, gives when 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 at the exact tail mass on 4 training minibatches is 0.062 0.115, between 0 and 0.70.
Distillation loss
Table S6 compares cross-entropy and Jeffreys distillation on Pet. For , Jeffreys distillation recovers 45% to 46% of the accuracy gap between the compiled model and the reference, and cross-entropy 36% to 43%. Jeffreys gains most, 1.2 to 1.5 points, at and 4, since it matches the full teacher distribution and not only the label.
| compiled | CE saved | CE mean | Jeffreys saved | Jeffreys mean | |
| 1 | 15.73 | 41.24 | 41.89 | ||
| 2 | 42.95 | 64.49 | 64.57 | ||
| 4 | 67.10 | 77.02 | 78.09 | ||
| 8 | 79.50 | 84.33 | 84.71 | ||
| 16 | 86.24 | 88.17 | 88.58 | ||
| 32 | 89.23 | 89.92 | 90.19 | ||
| 64 | 90.35 | 90.84 | 90.76 | ||
| 96 | 90.76 | 90.90 | 91.25 | ||
| 128 | 91.11 | 91.11 | 91.11 | ||
| 197 | 91.36 | 91.36 | 91.36 |
Table S6. Distillation on DeiT-Tiny/Pet, top-1 accuracy (%) of the saved run, the one with the highest training accuracy, and mean ± s.d. over five seeds.
bf16 against fp32
Table S7 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 to 0.01 dB.
| Network | Model | bf16 | fp32 | bf16 − fp32 |
| DeiT-Tiny, Pet | reference | 91.36 | 91.33 | +0.03 |
| extended | 91.36 | 91.33 | +0.03 | |
| strict, GELU | 91.06 | 91.33 | −0.27 | |
| Hadamard, GELU | 91.28 | 91.33 | −0.05 | |
| strict, sigmoid GELU | 90.73 | 90.27 | +0.46 | |
| Hadamard, sigmoid GELU | 90.35 | 90.27 | +0.08 | |
| DeiT-Tiny, ImageNet-1k | reference | 72.02 | 72.02 | +0.01 |
| extended | 72.01 | 72.02 | 0.00 | |
| MambaIRv2-Light ×2, Set5 | reference | 38.234 | 38.272 | −0.038 |
| extended | 38.231 | 38.270 | −0.039 | |
| MambaIRv2-Light ×4, Set5 | reference | 32.511 | 32.512 | −0.002 |
| extended | 32.502 | 32.507 | −0.006 | |
| Pythia-70M, WikiText-2 | reference | 6.681 | 4.550 | +2.131 |
| extended | 6.680 | 4.550 | +2.130 |
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: .
In fp32, every compiled graph with exact GELU reproduces its reference (Theorems 1 and 3, Proposition 1). 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. With , the strict and Hadamard graphs compute the same model and give the same fp32 accuracy. bf16 changes the accuracy of DeiT-Tiny by at most 0.46 points and the PSNR of MambaIRv2-Light by at most 0.04 dB.
Pythia-70M runs in fp32. In bf16 its validation NLL rises from 4.55 to 6.68 nats, for the reference and the compiled graph alike. Only bf16 weights with fp32 arithmetic give 4.56. The degradation cause is the logits. They share a large offset that softmax ignores: their median is 1061, while the top two differ by a median of 0.73. Near 1000, bf16 resolves steps of 8, so it loses the ranking of the tokens. The output projection causes 1.7 of the 2.1 nats and attention the other 0.4.
Quantization with exact GELU
Table 3 reports each graph in its deployment configuration: the strict graph with 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 compares the strict graph with exact GELU and with under the same PTQ, both before distillation. The quantized graph has 344 nodes with GELU and 380 with its approximation, 332 and 368 at . Exact GELU matches no NPU configuration and serves as a comparison. With either GELU, PTQ costs the strict graph at most 1.5 points, against 2.5 to 3.9 points for the extended graph.
| GELU: bf16 | GELU: , per-channel | GELU: , per-tensor | : bf16 | : , per-channel | : , per-tensor | |
| 16 | 86.37 | −1.44 | −0.90 | 84.08 | −1.47 | −1.06 |
| 32 | 89.07 | −0.76 | −0.68 | 87.98 | −0.68 | −0.71 |
| 64 | 90.35 | −0.49 | +0.05 | 89.78 | −0.05 | −0.14 |
| 197 | 91.06 | −0.08 | +0.19 | 90.73 | −0.46 | −0.98 |
Table S8. PTQ of the strict graph with exact GELU and with on DeiT-Tiny/Pet, before distillation, with the PTQ of Table 3. bf16: top-1 accuracy (%) of the float model. : change after PTQ with per-channel or per-tensor weight scales. The approximation columns repeat Table 3.
Tensor sizes
Native reads values per head and writes . The unfused strict graph also writes the sums , squares them in place, and reduces over . For DeiT-Tiny that is values per head per image against , a factor , which drives the memory column of Table 2. Top- mixing reads of the value rows per query, a fraction of the value traffic of dense mixing.
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.arxiv.org/abs/1706.03762
- [2]Google Coral. TensorFlow models on the edge TPU. 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 (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).arxiv.org/abs/2407.05858
- [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.
- [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).DOI
- [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).DOI
- [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.arxiv.org/abs/2106.14156
- [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).arxiv.org/abs/2111.12293
- [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).arxiv.org/abs/2111.13824
- [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).arxiv.org/abs/2212.08254
- [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).arxiv.org/abs/2404.00928
- [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.arxiv.org/abs/2101.01321
- [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.arxiv.org/abs/2211.10438
- [15]ONNX. LayerNormalization (opset 17), function definition. 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 (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 (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 (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).arxiv.org/abs/1905.02244
- [21]Gupta, A., Dar, G., Goodman, S., Ciprut, D. & Berant, J. Memory-efficient transformers via top-k attention. 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/.arxiv.org/abs/2106.06899
- [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-k attention 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/.arxiv.org/abs/2506.02572
- [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.
- [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.arxiv.org/abs/2007.04825
- [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).DOI
- [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.
- [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).DOI
- [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).arxiv.org/abs/2411.15269
- [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.arxiv.org/abs/2304.01373
- [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).DOI
- [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).DOI
- [36]Yarotsky, D. Error bounds for approximations with deep ReLU networks. Neural Networks 94, 103–114 (2017).DOI
- [37]Rotem, N. et al. Glow: Graph lowering compiler techniques for neural networks. arXiv:1805.00907 (2018).arxiv.org/abs/1805.00907
- [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).arxiv.org/abs/2206.00216
- [39]Hao, M. et al. Iron: Private inference on transformers. In Advances in Neural Information Processing Systems, vol. 35 (2022).DOI
- [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).arxiv.org/abs/2305.17190
- [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.
- [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.
- [44]Zhu, J., Chen, X., He, K., LeCun, Y. & Liu, Z. Transformers without normalization. arXiv preprint arXiv:2503.10622 (2025).arxiv.org/abs/2503.10622
- [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.arxiv.org/abs/2110.15343
- [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.
- [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.arxiv.org/abs/2410.16179
- [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).arxiv.org/abs/2112.02191
- [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).arxiv.org/abs/2405.04206
- [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).DOI
- [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.arxiv.org/abs/2006.04710
- [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).arxiv.org/abs/1712.05877
- [54]Nagel, M. et al. A white paper on neural network quantization. arXiv:2106.08295 (2021).arxiv.org/abs/2106.08295
- [55]Hinton, G., Vinyals, O. & Dean, J. Distilling the knowledge in a neural network. arXiv:1503.02531 (2015).arxiv.org/abs/1503.02531
- [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).pubmed.ncbi.nlm.nih.gov/20998741
- [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.DOI
- [58]Augustsson, E. & Timoftе, 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.arxiv.org/abs/1609.07843
- [60]Shazeer, N. GLU variants improve transformer. arXiv:2002.05202 (2020).arxiv.org/abs/2002.05202
- [61]Erofeeva, V., Granichin, O., Avros, R. & Volkovich, Z. Multilevel modeling and control of dynamic systems. Scientific Reports 14, 27903 (2024).DOI
- [62]Wightman, R. 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/14/nvidia-ada-gpu-architecture-whitepaper-v2.02.pdf (2023).
- [64]Strassen, V. Gaussian elimination is not optimal. Numerische Mathematik 13, 354–356 (1969).DOI
- [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).arxiv.org/abs/2404.16349
- [66]Bürgisser, P., Clausen, M. & Shokrollahi, M. A. Algebraic Complexity Theory (Springer, 1997).DOI
- [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.
- [68]Arm. Ethos-U Vela compiler source code (regor backend), commit dd3f874. https://gitlab.arm.com/artificial-intelligence/ethos-u/ethos-u-vela (2026). Files ethosu/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 (2026). Operator map op_map.cc and op_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 (2026). Accessed 2026-10-09.
- [71]Rockchip. RKNN compiler support operator list, v2.3.2. 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 (2025). Accessed 2026-10-09.
- [73]NVIDIA. NVDLA software stack, commit 79538ba. 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 (2025). driver/support_library/src/SupportQueries.cpp and SUPPORTED.md. Accessed 2026-10-03.
- [75]NVIDIA. NVDLA hardware architectural specification: LUT programming. 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).DOI