Linearized Attention Cannot Enter the Kernel Regime at Any Practical Width

Jose Marie Antonio Miñoza; Paulo Mario P. Medina; Sebastian C. Ibañez

cs.LGMar 13, 2026

Linearized Attention Cannot Enter the Kernel Regime at Any Practical Width

Authors: Jose Marie Antonio Miñoza, Paulo Mario P. Medina, Sebastian C. Ibañez

Organizations: Center for AI Research PH

Abstract

Understanding whether attention mechanisms converge to the kernel regime is foundational to the validity of influence functions for transformer accountability. Exact NTK characterization of softmax attention is precluded by its exponential nonlinearity; linearized attention is the canonical tractable proxy and the object of study here. This paper establishes that even this proxy does not converge to its NTK limit at any practical width, revealing a fundamental trade-off in the learning dynamics of attention. An exact correspondence is established between parameter-free linearized attention and a data-dependent Gram-induced kernel; spectral amplification analysis shows that the attention transformation cubes the Gram matrix's condition number, requiring width $m = Ω(κ_d(\mathbf{G})^6 n\log n)$ for NTK convergence, where $κ_d(\mathbf{G})$ is the effective condition number of the rank- $\min(n,d)$ truncation of the input Gram matrix; for natural image datasets this threshold is physically infeasible ( $m \gg 10^{24}$ for MNIST and $m \gg 10^{29}$ for CIFAR-10, 12--17 orders of magnitude beyond the largest known architectures). Influence malleability is introduced to characterize this non-convergence: linearized attention exhibits 2--9 $\times$ higher malleability than ReLU networks under adversarial data perturbation, with the gap depending on dataset condition number and task setting. A dual implication is established: the same data-dependent kernel is shown theoretically to reduce approximation error when targets align with the data geometry, while, empirically, creating vulnerability to adversarial manipulation of the training data. The structural argument extends to trainable QKV attention under standard initialization, with direct consequences for influence methods applied to deployed transformer architectures.

Figures & tables

Figure 1: NTK distance

\|f_{m}-f_{\text{NTK}}\|

across network widths, where

f_{m}

is the finite-width trained model and

f_{\text{NTK}}

is the infinite-width NTK predictor. 2L-ReLU (blue) shows expected convergence: distance decreases as

m\to\infty

. MLP-Attn (orange), using linearized attention (

f^{\text{att}}(\mathbf{X})=\mathbf{X}\mathbf{X}^{T}\mathbf{X}

) not full softmax, shows fundamentally different behavior: distance fails to decrease monotonically on either dataset (non-monotonic on MNIST, increasing on CIFAR-10), consistent with the non-convergence established in Theorem 4.8 (see Remark 4.1 for the convergence/non-convergence/divergence taxonomy). This figure is a diagnostic illustration; Theorem 4.8 is a mathematical result that does not require empirical validation at these scales.

MNIST
Model	$m$ =16	$m$ =1024	$m$ =4096
2L-ReLU	45.1	39.9	39.2
MLP-Attn	10.3	33.3	43.4
CIFAR-10
2L-ReLU	246.2	101.7	56.9
MLP-Attn	3.7	10.4	12.6

Table 1: NTK distance

\|f_{m}-f_{\text{NTK}}\|

across network widths. 2L-ReLU exhibits monotonically decreasing distance, consistent with convergence to the kernel regime. MLP-Attn shows qualitatively different behavior: non-monotonic across the full width sweep on MNIST (Figure 1 ), monotonically increasing on CIFAR-10.

Dataset	Setting	Model	FGSM	PGD	MIM
MNIST	10-class	2L-ReLU	4.1	3.3	3.4
	10-class	MLP-Attn	34.6	28.9	21.9
	Binary	2L-ReLU	8.4	8.4	8.6
	Binary	MLP-Attn	25.9	41.0	40.5
CIFAR-10	10-class	2L-ReLU	3.3	3.1	3.2
	10-class	MLP-Attn	26.4	19.1	20.5

Table 2: Influence flip rates (%) across perturbation types (

\varepsilon=0.03

) for both classification settings. In the 10-class setting MLP-Attn shows 6–9

\times

higher malleability; the gap narrows to

{\approx}\,1\times

in binary CIFAR-10 (cars vs. planes) due to lower

\kappa_{d}(\mathbf{G})

, consistent with Theorem 4.8 (Appendix A.2 ). Binary setting follows Zhang and Zhang (2022) . Epoch-by-epoch progression in Table 5 (Appendix E ).

Panel of Figure 2 — Figure 2: Analysis of influence dynamics. (a) MLP-Attn exhibits consistently higher influence malleability (flip rate) across all perturbation types, reflecting its operation in the feature learning regime. (b) Rank correlation analysis reveals that 2L-ReLU maintains rigid influence rankings while MLP-Attn shows lower correlation, indicating continuous re-evaluation of data dependencies. The Transformed intervention (replacing influential examples with adversarial versions) produces the most structured adaptation pattern.

Dataset	Model	Standard	Adv-Trained
MNIST	2L-ReLU	3.3	43.4
MNIST	MLP-Attn	28.9	42.2
CIFAR-10	2L-ReLU	3.1	36.5
CIFAR-10	MLP-Attn	19.1	38.6

Table 3: Effect of adversarial training on influence flip rates (%). Full training-epoch progression in Table 5 (Appendix E ).

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Dim.	Classes	Norm.
MNIST	784	10	(.13, .31)
Fashion-MNIST	784	10	(.29, .35)
CIFAR-10	3072	10	(.5, .5, .5)

Appendix

Table 4: Dataset specifications. Dim. = input dimension, Norm. = (mean, std) normalization parameters. Standard training set sizes are used.

Panel of Figure 3 — Figure 3: Contribution to model complexity (blue) and average influence score (red) for MLP-Attn across three datasets. The U-shaped complexity curve indicates that the most influential points (both harmful and helpful) contribute most to model complexity, consistent with findings of Zhang and Zhang [2022] .

Figure 4: Top influential training examples for a representative test digit. Positive influencers (top rows) increase test loss when removed; negative influencers (bottom rows) decrease it. The key distinction is quantitative: MLP-Attn flip rate 28.9% vs. 3.3% for 2L-ReLU under PGD (Table 2 ), reflecting the Gram-induced kernel’s data-dependent structure.

Figure 5: Loss landscape comparison (MNIST) at finite width $m=1024$ (left two panels) and infinite-width NTK limit (right two panels). 2L-ReLU (blue) converges toward its NTK landscape: both finite and infinite-width surfaces share similar geometry. MLP-Attn (orange) shows a qualitatively different finite-width landscape (sharp, deep minimum) compared to its NTK limit (broad, shallow basin), visualizing the NTK non-convergence from a loss geometry perspective. NTK distances: 2L-ReLU $=39.93$ , MLP-Attn $=33.30$ .

Figure 6: NTK distance

1-\cos(K_{m},K_{\infty})

versus network width

m

for four attention variants (mean

\pm

std over 10 seeds). This metric is scale-invariant : it measures angular alignment (eigenvector structure) between

K_{m}

and

K_{\infty}

, and is blind to eigenvalue magnitudes. Compare with Figure 1, which uses the magnitude-sensitive function-space distance

\|f_{m}-f_{\mathrm{NTK}}\|

and shows non-monotonic or increasing divergence for linearized attention. The two are not contradictory: at large widths the eigenvectors of

K_{m}

align with those of

K_{\infty}

(low cosine distance), while the eigenvalues remain cubically amplified by

\kappa_{d}(G)^{3}

(high function-space distance, cf. Theorem 4.8 ). 2L-ReLU and linearized attention decrease gradually with width, indicating genuine structural alignment; the sweep extends to

m=4096

, covering and exceeding the hidden dimensions of standard transformers (BERT: 768, ViT-L: 1024, GPT-2: 1600). Softmax and exponential attention show near-zero distance at all widths, but this is vacuous: their feature maps collapse to a single direction (Figure 7 , mean pairwise cosim

=1.000

), so

K_{\infty}

itself is rank-1. Both

K_{m}

and

K_{\infty}

are identical degenerate matrices at every width, making cosine similarity trivially unity regardless of convergence. The oscillations of the dashed lines near the numerical floor are floating-point noise in this degenerate regime.

Figure 7: Feature map diversity for each attention variant, measured as mean off-diagonal pairwise cosine similarity of

\phi(\mathbf{x}_{i})

embeddings. Values near 1 indicate collapse to a single direction (degenerate). Softmax and exponential attention achieve

\cos=1.000

on both datasets, confirming that their near-zero NTK distances in Figure 6 are artifacts of rank-1 kernel collapse rather than principled convergence. Linearized attention and 2L-ReLU maintain diverse embeddings, validating the non-convergence result of Theorem 4.8 .

Architecture	Dataset	Training Progression							Flip Rate
		Epoch 1			Epoch 10		Epoch 100
		Base	Curated	Trans.	Curated	Trans.	Curated	Trans.
2L-ReLU	MNIST	91.6%	89.2%	91.8%	95.1%	97.1%	97.8%	98.4%	3.3%
	FashionMNIST	88.5%	86.1%	89.2%	90.8%	93.1%	93.9%	95.6%	15.0%
	CIFAR-10	65.3%	63.8%	66.1%	68.9%	70.8%	71.6%	73.1%	3.1%
MLP-Attn	MNIST	93.1%	90.7%	93.3%	96.6%	98.6%	99.3%	99.9%	28.9%

Appendix

Table 5: Extended learning dynamics analysis across training epochs and intervention types. Base : standard training accuracy. Curated : accuracy after removing top 10% influential examples. Trans. : accuracy with adversarially transformed influential examples. Flip Rate : percentage of top 10% influential examples that reverse influence sign under PGD attack. The MLP-Attn architecture shows (1) systematic development of adaptive data dependencies, (2) higher sensitivity to data interventions, and (3) emergence of influence malleability as attention learns flexible data relationships.

Linear Attention

Linear attention reduces sequence-length costs by replacing pairwise token interactions with kernel features, recurrent states, or compact memory.

See all 129 papers

Oct 9, 2026

Not All Dimensions Are Equal: Outlier-Aware Attention Linearization with Grouped Quadratic Kernels

Linearizing softmax attention offers a route to efficient Transformer inference, but preserving pretrained attention remains challenging. We identify an important source of approximation error overlooked by standard linearization methods: a small number of outlier dimensions contribute disproportionately to query-key dot products and account for a large fraction of the approximation error. Motivated by this heterogeneity, we propose Outlier-Aware Attention Linearization (OAL), a dimension-aware method for constructing quadratic attention approximations. Starting from a second-order Taylor approximation, we introduce a Hadamard-product formulation that makes individual query-key contributions explicit. This formulation relaxes globally shared coefficients to support dimension-specific linear terms and cross-dimensional quadratic interactions while preserving separable evaluation. To retain this flexibility with fewer parameters, OAL groups dimensions with similar contribution scales to share coefficients, while allowing distinct treatment of the few outliers. The resulting positive quadratic kernel is calibrated against pretrained attention outputs and admits linear-time evaluation with respect to sequence length for fixed head dimensions. On Qwen2.5-0.5B, OAL reduces frozen-attention output relative MSE by approximately 8.9% compared with DiJiang. Replacing middle-layer attention modules and jointly fine-tuning the kernel coefficients with LoRA further lowers WikiText-103 perplexity from 31.71 to 27.50 compared with a learned global quadratic, while improving accuracy on PIQA, HellaSwag, and ARC-E. These results demonstrate the value of outlier-aware dimension grouping for both attention approximation and pretrained-model conversion. The code is available at https://github.com/wuqianyue09/OAL

Weiqi Sun, Qianyue Wu, Wenjia Wang +1

The Chinese University of Hong Kong, Shenzhen · Beijing Normal University, Zhuhai · National University of Singapore

Attention Approximation Efficient Attention Linear Attention Transformer Inference

Ask PDF

May 13, 2026

Exact Linear Attention

This paper introduces Exact Linear Attention (ELA), a mechanism that achieves linear computational complexity for Transformer attention by exploiting the exact decomposition property of kernel functions, thereby eliminating approximation error. We identify and address two key limitations of prior linear attention -- gradient explosion and token attention dilution -- by imposing kernel constraints that ensure non-negativity, discriminability, and geometric interpretability. Several kernel functions are proposed, including the Hadamard Exp Kernel, Summation Squared Euclidean Distance Kernel, and Subtraction Squared Euclidean Distance Kernel, each tailored for specific attention behaviors. Beyond the core attention formulation, the paper presents three engineering innovations: (1) a Hyper-Link structure that replaces traditional residual connections to mitigate gradient degradation; (2) a Memory Lobe module based on bidirectional linear attention, which captures "transformation flow" across layers to implement qualitative memory and an implicit reinforcement learning paradigm; and (3) a routing-score-based bias mechanism for Mixture-of-Experts (MoE) to improve interpretability and semantic alignment. Experimental results demonstrate that ELA achieves up to 6x faster decoding speed and 75% reduction in KV cache memory usage compared to full attention, while maintaining comparable or superior training performance. The proposed memory module accelerates convergence and enhances generalization. Furthermore, we extend the linear attention principle to vision models, yielding YOLO-LAT, which attains up to 4.3x GPU inference speedup and 7.9x parameter reduction with competitive detection accuracy. These results underline the broad applicability of exact linear attention for scaling Transformer models to ultra-long sequences and efficient visual tasks.

Weinuo Ou

Wuyi University

Efficient Transformer Inference Self-Attention Linear Attention

Ask PDF

Jul 25, 2026

The Entropic Bound for Transformers: Why Static Rank Fails and Attention-Native Rank Recovers

Neural scaling laws describe how loss decreases as models, data, and compute grow, but they do not answer a prior question: for a fixed task, what is the minimum model capacity required to solve it? We study this through the Entropic Bound, a spectral notion of task-intrinsic capacity for Transformers. We first prove that, in a linear attention surrogate, the intrinsic rank

r^*

of the token-mixing operator is a tight lower bound: any rank-deficient model incurs unavoidable excess risk, and the bound is achievable at

r^*

. We further show that gradient descent recovers this rank under standard low-rank implicit-bias assumptions, confirm all three properties empirically, and show

r^*

is recoverable from data before training. We then ask whether this transfers to real attention. A naive transfer fails, and a controlled interpolation ladder localizes the cause precisely: it is not softmax and not a rank constraint, but the input-conditioned nature of attention's mixing operator, which a static weight kernel cannot summarize. Motivated by this, we introduce an attention-native intrinsic rank -- the minimum query-key kernel rank realizing the task within the attention class -- and show that under this definition the full Entropic Bound structure (deficiency, achievability, recovery) is restored for both linear and softmax attention, with the energy effective rank as the estimator robust to softmax distortion. Finally, we map the boundary of data-only predictability:

r^*

is exactly recoverable for linear QK attention, even without the value map at scale, while softmax attention admits only partial pre-training recovery due to nonlinear inversion and kernel-value identifiability effects. Our results reframe the Entropic Bound from a post-hoc descriptor into an attention-native capacity measure with a precisely characterized predictability frontier.

Byeong Hoon Yoon

Independent Researcher

Softmax Attention Transformer Expressivity Low-Rank Approximation Attention Mechanisms

Ask PDF

Abstract

Linear Attention

Explore similar work

Not All Dimensions Are Equal: Outlier-Aware Attention Linearization with Grouped Quadratic Kernels

Exact Linear Attention

The Entropic Bound for Transformers: Why Static Rank Fails and Attention-Native Rank Recovers