acceptodds
Under review as a conference paper at ICLR 2027

Linearized Attention Cannot Enter the Kernel Regime at Any Practical Width

Abstract

Influence functions are now widely used to audit transformer training data, relying on the unverified assumption that attention reaches the neural tangent kernel (NTK) regime. Softmax attention admits no exact NTK, so this question is studied in this paper through linearized attention, the standard tractable proxy. This proxy is shown not to enter the kernel regime at any practical width. An exact correspondence is established between parameter-free linearized attention and a data-dependent Gram-induced kernel whose condition number is the cube of the input Gram's. With the effective condition number of the input Gram matrix, a width suffices for convergence, and a matching necessity bound makes the exclusion two-sided. For natural image datasets, with (MNIST) and (CIFAR-10), even the tight requirement exceeds , more than ten orders of magnitude beyond the parameters of the largest known architectures. Influence malleability is introduced to measure the consequence. Linearized attention exhibits 3–9 higher malleability than ReLU networks under adversarial data perturbation, with the gap set by dataset condition number and task. For trainable query, key, and value projections, an exact NTK block decomposition yields a precondition floor . Non-convergence then persists at exponent two for every dataset studied. The cubic mechanism itself is erased under standard independent initialization and survives only under an explicit, checkpoint-measurable condition. This precondition is measured above the non-convergence threshold across more than twenty pretrained language, vision, and audio models, the setting where influence methods are deployed.

Primary area:
learning theory
Keywords:
neural tangent kernel, linear attention mechanism, softmax, influence function

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_wpSjOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies finite-width kernel approximation for linearized attention and the sensitivity of training-data influence scores. Starting from the parameter-free transformation XX^\top X, the authors analyze the amplification of the Gram matrix’s condition number, derive sufficient width conditions and necessary lower bounds for kernel approximation, and extend the analysis to a simplified model with trainable QKV projections. Experiments on image datasets show that the studied model does not consistently approach its kernel predictor over the tested widths, and that its influence scores are more sensitive to training-data perturbations. The authors further discuss practical implications through condition-number measurements on pretrained models.

Critical strengths
  • The paper connects attention-based feature aggregation, spectral conditioning, and influence-score sensitivity, providing a clear perspective on the limitations of kernel approximation.
  • The theoretical analysis includes both sufficient width conditions and necessary lower bounds, and distinguishes the behavior of trainable QKV projections under independent and aligned initialization.
  • The experiments examine the phenomena of interest through width sweeps, different perturbation methods, and measurements on pretrained representations.
Critical weaknesses
  1. The width bounds do not fully support the general impossibility claim in the title. Theorem 4.4 provides a sufficient width condition; a large sufficient bound alone does not establish that smaller widths must fail. Theorem 4.5 adds a necessary lower bound involving \lambda_{\min}(K_\infty), but the matching \kappa(G)^3 dependence in Appendix C.14 is established for a specific two-point construction. The same necessary width cannot be inferred solely from \kappa(G) measured on real datasets. The enormous width requirements stated for MNIST and CIFAR-10 therefore still need justification for these particular datasets.
  2. The assumptions underlying existing data attribution methods are not accurately characterized. The introduction describes TRAK, DataInf, and EK-FAC as uniformly requiring the model to remain in the kernel regime throughout training. However, TRAK uses local linearization around the trained parameters, while DataInf and EK-FAC involve local influence-function and curvature approximations. These approximations are distinct from using the infinite-width NTK at initialization to describe the entire training trajectory. The paper’s kernel non-convergence results therefore do not directly establish that these methods are unreliable.
  3. Influence malleability is not adequately distinguished from attribution error. Perturbing training data may also change the examples’ true influence, so sign flips or ranking changes alone do not demonstrate inaccurate attribution. The experiments primarily compute influence scores using empirical kernels, without corresponding validation against actual retraining after removing or reweighting examples. The results therefore support sensitivity to perturbations, but do not yet establish that practical data attribution is unreliable.
Questions for authors
  1. How does the kernel approximation criterion relate to attribution accuracy under regularization? Section 3 describes the approximation requirement in terms of the regularization scale λ\lambda, whereas the main width theorems use error relative to \lambda_{\min}(K_\infty). For the values of λ\lambda used in the experiments, is the latter criterion necessary for accurate influence estimation?
  2. How is the dataset-dependent feature transformation handled when an example is removed? The updates in the appendix hold the kernel fixed, but XX^\top X changes with the training set. Do the reported influence scores correspond to removal with a fixed reference set, or to recomputing all features and retraining after removal?
  3. What is the precise scope of the statement “Softmax attention does not admit an exact NTK”? Prior work has derived NTKs for attention networks under specific scaling choices and infinite-head limits. Does this statement refer to the absence of a deterministic limit with finitely many heads, the lack of a closed-form expression, or another limitation?
2 comments

The authors thank Reviewer wpSj for the detailed review.


W1. The width bounds do not fully support the general impossibility claim in the title.

The paper's theoretical framework is NTK convergence analysis, specifically whether the empirical NTK of a linearized-attention network concentrates around its infinite-width limit at practical widths. The revised version states the precise claim explicitly in the opening of Section 4. Theorem 4.4 establishes that the sufficient width for ε\varepsilon-approximate NTK convergence is at least Ω(κd(G)6log⁡n/ε2)\Omega(\kappa_ {d}(\mathbf{G})^ {6} \log n / \varepsilon^ {2}), where convergence means

∥Km−K∞∥2/λmin(K∞)≤ε.\lVert\mathbf{K}_ {m} - \mathbf{K}_ {\infty}\rVert_ {2} / \lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty}) \leq \varepsilon.

The title's claim concerns certification. No practical width carries a certificate of convergence under the conditions analyzed. The sufficient bound in Theorem 4.4 does not preclude approximation at smaller widths.

Theorem 4.5 adds a necessity lower bound. For a fixed tolerance ε\varepsilon, any width below 1/(8ε2λmin(K∞)2)1/(8\varepsilon^ {2} \lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty})^ {2}) must fail. The two-point coalescing construction (Appendix C.14) establishes that the lower bound attains κd(G)3\kappa_ {d}(\mathbf{G})^ {3} scaling, confirming the cubic exponent in Theorem 4.4 is tight and intrinsic to the architecture. With κd(G)≈9×108\kappa_ {d}(\mathbf{G}) \approx 9 \times 10^ {8} for MNIST, the necessity lower bound alone already exceeds 102610^ {26}, while the sufficient width from Theorem 4.4 is larger still.


W2. The assumptions underlying TRAK, DataInf, and EK-FAC are not accurately characterized.

The introduction overstates what these methods require. The statement that these methods share the assumption that the first-order NTK approximation holds throughout training is imprecise. TRAK (Park et al., 2023) constructs attribution scores via local linearization around the trained parameters. The empirical NTK need not remain constant throughout training. DataInf and EK-FAC similarly operate through local curvature approximations around a converged checkpoint.

The paper's non-convergence results bear on these methods through Theorem 4.9. The effective conditioning floor κ+(K∞QKV)≥κd(G)\kappa^ {+}(\mathbf{K}_ {\infty}^ {\mathrm{QKV}}) \geq \kappa_ {d}(\mathbf{G}) holds at every analyzed initialization, so the influence operator at any checkpoint inherits the ill-conditioning of the data Gram. The connection to methods like TRAK runs through this structural ill-conditioning at the checkpoint. The revised introduction reflects this and removes the imprecise "throughout training" characterization.


W3. Influence malleability is not adequately distinguished from attribution error.

The experiments measure sensitivity of attribution scores to bounded adversarial perturbations, treating sign flips as evidence of ill-conditioning, with no claim about attribution correctness.

Under the same perturbation budget, 2L-ReLU flips at 3.3–4.1% vs. MLP-Attn at 26.4–34.6% (Table 1). If sign flips were genuine responses to changed data, both architectures would flip at similar rates, but the 8–10× gap is attributable to kernel conditioning. Theorem C.23 certifies that bounded perturbations of size εK\varepsilon_ {K} cannot flip attributions when λ>εK\lambda > \varepsilon_ {K}, a condition that fails for MLP-Attn because the floor result forces λmin(K)\lambda_ {\mathrm{min}}(\mathbf{K}) too small at any practical width.

Jacot et al. (2018) and Lee et al. (2019) guarantee that kernel-based influence scores for 2L-ReLU converge to the true leave-one-out attribution as width grows. Figure 1 confirms the empirical NTK Km\mathbf{K}_ {m} is close to K∞\mathbf{K}_ {\infty} at the widths studied for 2L-ReLU, so the stability bound applies tightly. The formal connection between the malleability measure μˉM\bar{\mu}_ {M} and the empirical Flip Rate is in Appendix B.5.3 (Remark, Formal-Empirical Bridge).

High malleability is a necessary condition for unreliable attribution, with sufficiency not claimed. Leave-one-out retraining requires one full model training for each removed example and is not included in the current work.

Ghorbani et al. (2019, AAAI) show adversarially constructed perturbations can drive attribution rankings to near-complete reversal without changing the predicted label. Basu et al. (2021, ICLR) show influence estimates in deep networks lose rank validity at scale, with near-zero Spearman correlation on CIFAR-100 and ImageNet. Theorems 4.2 and 4.9 provide a structural account: cubic conditioning amplification is an intrinsic property of the architecture's kernel at any parameter point, so any perturbation with nonzero projection onto the low-eigenvalue subspace of K\mathbf{K} flips influence signs.

Q1. How does the kernel approximation criterion relate to attribution accuracy under regularization?

The two criteria control different properties of the influence vector. Theorem C.23 gives

∥Im−I∞∥2≤εKλ(λ−εK)∥y∥2,\lVert\boldsymbol{\mathcal{I}}_ {m} - \boldsymbol{\mathcal{I}}_ {\infty}\rVert_ {2} \leq \frac{\varepsilon_ {K}}{\lambda(\lambda - \varepsilon_ {K})} \lVert\mathbf{y}\rVert_ {2},

where εK\varepsilon_ {K} is the spectral-norm difference between Km\mathbf{K}_ {m} and K∞\mathbf{K}_ {\infty}. This bounds the absolute deviation of the influence vector as a function of λ\lambda.

The relative criterion εK/λmin(K∞)\varepsilon_ {K} / \lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty}) is necessary for sign accuracy. The ridge λ\lambda stabilizes eigenvalues of (Km+λI)(\mathbf{K}_ {m} + \lambda\mathbf{I}) but leaves the eigenvectors of Km\mathbf{K}_ {m} unchanged. The sign of Ii=ei⊤(Km+λI)−1y\mathcal{I}_ {i} = \mathbf{e}_ {i}^ {\top}(\mathbf{K}_ {m} + \lambda\mathbf{I})^ {-1}\mathbf{y} depends on the alignment of example ii with Km\mathbf{K}_ {m}'s eigenmodes. When εK≫λmin(K∞)\varepsilon_ {K} \gg \lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty}), the bottom eigenvectors rotate substantially from those of K∞\mathbf{K}_ {\infty} (Davis-Kahan), flipping sign independently of λ\lambda. At the measured κd(G)≈9×108\kappa_ {d}(\mathbf{G}) \approx 9 \times 10^ {8}, λmin(K∞)=λr(G)3≪λ=10−3\lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty}) = \lambda_ {r}(\mathbf{G})^ {3} \ll \lambda = 10^ {-3}, making the relative criterion far more stringent than the λ\lambda-based bound and the correct threshold for certifying sign reliability.


Q2. How is the dataset-dependent feature transformation handled when an example is removed?

The reported influence scores correspond to removal with a fixed reference set. The Sherman-Morrison approximation treats the feature map fatt(X)=XX⊤Xf^ {\mathrm{att}}(\mathbf{X}) = \mathbf{X}\mathbf{X}^ {\top}\mathbf{X} as fixed at the full training set when one example is removed, following the standard influence function framework (Koh and Liang, 2017). The transductive coupling (where removing xi\mathbf{x}_ {i} changes all remaining feature representations through XX⊤\mathbf{X}\mathbf{X}^ {\top}) is not propagated through the removal step. This approximation is acknowledged in Appendix B.5.1 as one whose validity in the transductive setting is not fully characterized, and the revised experimental section states this scope explicitly. The malleability analysis measures sensitivity of these approximate scores to perturbation.


Q3. What is the precise scope of "Softmax attention admits no exact NTK"?

In the standard finite-head, 1/dk1/\sqrt{d_ {k}}-scaled regime, the softmax score matrix AijA_ {ij} couples queries and keys nonlinearly and data-dependently, preventing both a parameter-independent limiting kernel and a tractable closed-form expression. The softmax normalization prevents the Jacobian concentration required by standard NTK convergence (Jacot et al., 2018; Lee et al., 2019), since AijA_ {ij} depends on both the parameters and the input X\mathbf{X}. A single softmax attention layer has a non-Gaussian infinite-width limit (Sakai et al., 2025), so no NNGP prior exists in the standard single-head regime. The GP limit for multi-head softmax attention requires heads →∞\to\infty (Hron et al., 2020, Theorem 3), a non-standard regime with no tractable closed-form kernel (Hron et al., Section 4.1). Linearized attention (first-order Taylor expansion of the score matrix, identity QKV projections) yields fatt(X)=XX⊤Xf^ {\mathrm{att}}(\mathbf{X}) = \mathbf{X}\mathbf{X}^ {\top}\mathbf{X}, which admits both. Yang (2020), Remark 7.4 explicitly defers NTK convergence for non-backpropagation-like architectures of which softmax attention is an instance.

Prior work has derived NTK-like quantities for attention under infinite-head limits or non-standard temperature scalings. The revised version cites Yang (2020), Remark 7.4 at the point where the claim appears and adds a parenthetical specifying the standard-regime scope.


The authors are happy to discuss any of the above points further during the discussion period.

Reviewer_2dLFOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper investigates the finite-width NTK approximation for a linearized-attention feature map followed by a two-layer ReLU net, with some QKV extensions. It gives spectral amplification identities and width bounds. Experiments argue that practical attention models are still outside the kernel regime, so influence estimates are unreliable.

Critical strengths

The finite-width analysis goes beyond just showing an infinite-width limit. Matching bounds on a two-point construction and the NTK decomposition under different QKV initializations give concrete insight into how data geometry and parameterization affect kernel approximation.

Critical weaknesses
  1. The main impossibility claim isn’t established. A large sufficient width in Theorem 4.4 doesn’t mean failure at smaller widths. Theorem 4.5 gives a necessary bound via the actual NTK minimum eigenvalue, but the cubic dependence on the input condition number holds only for a particular data family. Applying that worst-case scaling to MNIST/CIFAR needs more justification.

  2. The theoretical criterion doesn’t deliver the claimed training/attribution consequences. Init-time NTK approximation, kernel stability during training, and local influence around a trained checkpoint are different properties. The paper doesn’t establish the implications between them. Its global spectral criterion can also be much stronger than what regularized prediction needs. TRAK-type methods don’t require the whole training trajectory to stay in the init kernel regime.

  3. Experiments don’t close these gaps. CE-trained nets vs KRR can confound kernel approximation with training-objective differences. Influence sign flips measure sensitivity, not attribution error, without retraining-based ground truth. Embedding Gram condition numbers in pretrained models doesn’t verify the conditions the QKV analysis needs.

Questions for authors
  1. Can you get dataset-specific necessary width bounds from the actual normalized NTK spectrum? In particular, what justifies the reported 10^26 and 10^22 thresholds beyond plugging input condition numbers into the two-point worst-case scaling?

  2. What theoretical or empirical evidence links failure of your init spectral criterion to inaccurate attribution at trained checkpoints? Do the conclusions survive with matched training objectives and attribution checked against actual retraining outcomes?

2 comments

The authors thank Reviewer 2dLF for the detailed reading and for identifying the points where the paper's framing can be sharpened.


W1. A large sufficient width does not establish that smaller widths fail.

The paper is an NTK convergence theory paper. Its claims concern the conditions under which the empirical NTK of a linearized-attention architecture can be certified to approximate its infinite-width limit, and the width required for that certification. The paper makes two claims with distinct logical status, and the revised Section 4 opening now renders that distinction explicit. Theorem 4.4 establishes that m=Ω(κd(G)6log⁡n/ε2)m = \Omega(\kappa_ {d}(\mathbf{G})^ {6} \log n / \varepsilon^ {2}) is a sufficient width for ε\varepsilon-approximate NTK convergence. The bound does not preclude convergence at smaller widths. The title's claim concerns certification. At MNIST-measured κd(G)≈9×108\kappa_ {d}(\mathbf{G}) \approx 9 \times 10^ {8}, the necessity lower bound on required width already exceeds 102610^ {26}, while the largest deployed architectures reach 101210^ {12} parameters, fourteen orders of magnitude below that threshold. The sufficient width from Theorem 4.4 is larger still. No width achievable in practice satisfies the sufficient convergence condition established here.

Theorem 4.5 strengthens this by establishing that the cubic exponent is tight. It states a general distributional lower bound: for ε\varepsilon smaller than λmin(K∞)/2\lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty})/2, any mm-neuron network with i.i.d. initialization that converges with probability exceeding 15/1615/16 must satisfy

m≥18ε2λmin(K∞)2.m \geq \frac{1}{8\varepsilon^ {2} \lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty})^ {2}}.

The two-point coalescing construction (Appendix C.14) establishes that the lower bound attains κd(G)3\kappa_ {d}(\mathbf{G})^ {3} scaling, confirming the cubic exponent in Theorem 4.4 is tight and intrinsic to the architecture. Theorems 4.4 and 4.5 therefore establish jointly that the κd\kappa_ {d}-dependence in the sufficient bound is tight. Because λmin(K∞)\lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty}) equals λr(G)3⋅c\lambda_ {r}(\mathbf{G})^ {3} \cdot c (Theorem 4.2), the Theorem 4.5 lower bound is dataset-specific and computable from the measured Gram spectrum. The MNIST and CIFAR-10 values are worked out in the response to Q1 below.


W2. The theoretical criterion doesn't deliver the claimed training/attribution consequences.

The concern separates three distinct properties. The paper addresses each separately.

NTK approximation at initialization is the subject of Theorems 4.4 and 4.5. These establish a sufficient width bound and a matching necessity lower bound tight in the cubic exponent, both for the relative spectral criterion. No width achievable in practice carries a convergence certificate under the analyzed conditions.

Kernel stability during training figures in two separate parts of the paper. Figure 1 reports that NTK distance between Km\mathbf{K}_ {m} and K∞\mathbf{K}_ {\infty} stays flat or grows during training for MLP-Attn, confirming the architecture stays in the feature-learning regime. The theoretical results (Theorem 4.9, Proposition 4.11) make no claim about whether the kernel remains stable during training. The floor κ+(K)≥κd(G)\kappa^ {+}(\mathbf{K}) \geq \kappa_ {d}(\mathbf{G}) holds at any parameter point, including trained checkpoints, by a Schur complement argument on the QKV block structure.

Local influence at a trained checkpoint is addressed by Theorem 4.9 and Proposition 4.11, with no invocation of training dynamics. Proposition 4.11 establishes that the precondition floor κ+(K)≥κd(G)\kappa^ {+}(\mathbf{K}) \geq \kappa_ {d}(\mathbf{G}) holds at every parameter point in the analyzed QKV family, trained or otherwise, as a consequence of the architecture's Gram structure alone. For deployed models outside that family, Section 5 and Table 3 confirm the floor empirically across more than 20 architectures. The claim about attribution reliability at trained checkpoints therefore does not assume training passed through the kernel regime.

Global spectral criterion vs. regularized prediction. The malleability claim derives from the floor result alone. With λ=10−3\lambda = 10^ {-3} and λ1(K∞)≈(9×108)3\lambda_ {1}(\mathbf{K}_ {\infty}) \approx (9 \times 10^ {8})^ {3} on MNIST, Theorem C.23 bounds the deviation of the influence vector (Km+λI)−1y(\mathbf{K}_ {m} + \lambda\mathbf{I})^ {-1}\mathbf{y} from its infinite-width analog:

εKλ(λ−εK)∥y∥2.\frac{\varepsilon_ {K}}{\lambda(\lambda - \varepsilon_ {K})} \lVert\mathbf{y}\rVert_ {2}.

None of these methods requires the global lazy-training assumption, as reflected in the revised introduction. The connection runs through the floor: the influence operator at any trained checkpoint inherits κd(G)\kappa_ {d}(\mathbf{G}) as a conditioning lower bound.

W3. The experiments measure sensitivity rather than attribution accuracy.

The experiments report NTK distance across widths and influence sign-flip rates under adversarial perturbation, as direct measurements of the two quantities the theory predicts should be large given kernel non-convergence. Ground-truth leave-one-out validation requires retraining, which is computationally infeasible at the dataset scales studied (n=60,000n = 60{,}000 for MNIST, n=50,000n = 50{,}000 for CIFAR-10). The experimental section states this scope explicitly. The results corroborate the theoretical prediction of sensitivity, and the gap between MLP-Attn and 2L-ReLU flip rates under matched perturbation budgets is consistent with a poorly conditioned kernel concentrating influence on a few eigendirections and rendering attribution along the remaining directions sensitive.

Both architectures are trained with the same objective, so the comparison is architecturally controlled. The gap between CE-trained networks and their KRR counterparts is a known source of imprecision for influence functions generally, discussed in Appendix B.1.

Table 3 measures κd(G)\kappa_ {d}(\mathbf{G}) across more than 20 pretrained architectures in support of the floor result (Theorem 4.9). Since κ+(K)≥κd(G)\kappa^ {+}(\mathbf{K}) \geq \kappa_ {d}(\mathbf{G}) holds at any parameter point and for any influence kernel factoring through G\mathbf{G}, κd(G)\kappa_ {d}(\mathbf{G}) quantifies the minimum ill-conditioning inherited by any such operator on those data. Table 3 confirms κd(G)\kappa_ {d}(\mathbf{G}) exceeds the non-convergence threshold across all architectures studied, corroborating the floor in the regime where influence methods are deployed.


Q1. Can dataset-specific necessary width bounds be obtained from the actual normalized NTK spectrum?

Yes. Theorem 4.2 establishes K∞∝G3\mathbf{K}_ {\infty} \propto \mathbf{G}^ {3} exactly for the parameter-free architecture analyzed in Sections 3--4. The smallest eigenvalue λmin(K∞)=λr(G)3⋅c\lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty}) = \lambda_ {r}(\mathbf{G})^ {3} \cdot c is therefore determined by the actual data Gram spectrum. The thresholds 102610^ {26} and 102210^ {22} are κd(G)3\kappa_ {d}(\mathbf{G})^ {3} evaluated at the measured κd≈9×108\kappa_ {d} \approx 9 \times 10^ {8} (MNIST) and 4×1074 \times 10^ {7} (CIFAR-10).

Theorem 4.5 gives a dataset-specific width lower bound, with convergence probability exceeding 15/1615/16 requiring m≥1/(8ε2λmin(K∞,seq)2)m \geq 1/(8\varepsilon^ {2}\lambda_ {\mathrm{min}}(\mathbf{K}_ {\infty,\text{seq}})^ {2}) (the 15/1615/16 threshold follows from a Paley--Zygmund argument on the diagonal entries of Km,seq\mathbf{K}_ {m,\text{seq}}, detailed in Appendix C). That bound is computable from the measured G\mathbf{G} spectrum via the cubic identity. The two-point construction in Appendix C.14 is a separate tightness argument for exponent 3.


Q2. What links the spectral criterion at initialization to attribution accuracy at trained checkpoints?

Three theorems connect the analysis at initialization to trained checkpoints.

The identity G~=G3\tilde{\mathbf{G}} = \mathbf{G}^ {3} and the conditioning amplification κd(G~)=κd(G)3\kappa_ {d}(\tilde{\mathbf{G}}) = \kappa_ {d}(\mathbf{G})^ {3} are deterministic properties of the architecture at any width (Theorem 4.2).

For trainable projections, the limiting NTK at both analyzed initialization schemes satisfies κ+(K∞QKV)≥κd(G)\kappa^ {+}(\mathbf{K}_ {\infty}^ {\mathrm{QKV}}) \geq \kappa_ {d}(\mathbf{G}) (Theorem 4.9). Under independent Gaussian initialization, K∞QKV∝G\mathbf{K}_ {\infty}^ {\mathrm{QKV}} \propto \mathbf{G} (exponent 1). Under aligned orthogonal initialization, the exponent ranges from 1 to 3. Within the aligned family, Proposition 4.11 extends this to any parameter point, including trained checkpoints. The floor κ+(K)≥κd(G)\kappa^ {+}(\mathbf{K}) \geq \kappa_ {d}(\mathbf{G}) holds for every parameter value within that family. Outside the aligned family, no analogous characterization is claimed, and the connection to attribution at trained checkpoints runs through the empirical malleability measurements of Section 5.

Whether methods such as TRAK can circumvent this floor is addressed in the revised introduction (see W2 above).

Ghorbani et al. (2019, AAAI) show attribution rankings reverse under imperceptible perturbations. Basu et al. (2021, ICLR) show influence estimates lose rank validity in deep networks, the class of unreliability measured as flip rate in Section 5. Theorem 4.9 gives the floor κ+(K)≥κd(G)\kappa^{+}(\mathbf{K}) \geq \kappa_{d}(\mathbf{G}) at every parameter value in the analyzed families, and Table 3 confirms κd(G)\kappa_{d}(\mathbf{G}) exceeds the non-convergence threshold across all more than 20 architectures studied. Every attribution operator factoring through G\mathbf{G} inherits this ill-conditioning at any checkpoint.


The authors are prepared to discuss any of the above during the rebuttal period.

Reviewer_ZzFQOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies whether linearized attention can reach the NTK regime at practical network widths.

Critical strengths

The paper does not provide sufficient strengths to justify its acceptance until the weaknesses are addressed.

Critical weaknesses

W1: This paper does clearly show how the proposed approach could generalize across different modern transformers. In addition, can this approach be applied to other backbones e.g., CNNs or Mamba? If so, how can this be demonstrated through experimental analysis? If not please explain the reasons. W2. Motivation of the paper needs to be clearer. In addition, motivation-related figures are needed to demonstrate what previous studies do not address and what this paper aims to address. W3. Evidence is needed to support claims made in the paper e.g., “The learning dynamics of attention etc...” W4. How the authors justify the claim that “Linearized attention shows 3–9× higher influence flip rates than ReLU networks (6–9× multiclass, attenuated at low κd(G))”? Is there sufficient experimental analysis to support the claim? W5. How do the authors established that linearized attention creates adversarial vulnerabilities? Is there any theoretical proof and any experimental analysis to support the claim? W6. Why do the authors refers to the self-attention mechanism is linearized attention? This claim should be properly justified theoretical analysis, supported by references to prior studies and experimental evidence. W7. The paper lacks comparison with diverse adversarial attacks such as, AutoAttack, C&W, and any recent diffusion attacks published at top venues (e.g., CVPR, ICLR, ICML, NeurIPS) main conference during 2024-2026. W8. There are insufficient recent baselines for comparison. W9. The paper needs to be evaluated on ImageNet benchmarks and compared with prior recent baselines. W10. Additional qualitative analysis could improve the readability of the paper. W11. More comparisons with modern attention architectures are needed to support the broader claims. W12. Why did the authors not compare with their prior methods, such as Zhang & Zhang (2022), and TRAK (Parketal.,2023) etc. (see page: 3; line-134-135). W13. When mentioning the models such as “Mamba, RWKV, DeepSeek-V3,andKimi-K2”, authors should include appropriate citations.

Questions for authors

See Weaknesses.

3 comments

The authors thank Reviewer ZzFQ for taking the time to read the submission.


Preliminary note. This paper studies NTK convergence for attention-based architectures, with implications for the representational dynamics of attention and for influence-based data attribution on transformers. The central question is whether attention-based networks enter the kernel regime, motivated by the reliability of influence methods such as TRAK, DataInf, and EK-FAC when applied to transformer models. The analysis is made tractable via a linearized attention proxy (fatt(X)=XX⊤Xf^ {\text{att}}(\mathbf{X}) = \mathbf{X}\mathbf{X}^ {\top}\mathbf{X}), which yields a closed-form kernel amenable to exact theoretical analysis. The central result characterizes how attention-based feature maps amplify data geometry: the data Gram's condition number is cubically amplified in the attention NTK (κd(G~)=κd(G)3\kappa_ {d}(\tilde{\mathbf{G}}) = \kappa_ {d}(\mathbf{G})^ {3}, Theorem 4.2), making NTK-regime convergence unachievable at any practical width and placing the reliability of influence attribution on transformers in question. The malleability floor result (Theorem 4.9) is validated empirically across more than 20 pretrained models. The experiments measure NTK distance and stability of influence scores under perturbation to corroborate the theoretical predictions.

Two terms used throughout the paper are distinct. Influence functions (or influence methods) refers to training-data attribution techniques — TRAK, DataInf, EK-FAC — that estimate each training example's contribution to model predictions by linearizing the loss around trained parameters. These are the methods whose reliability is under examination. Influence malleability (Definition 3.4) is a metric introduced in this paper: the rate at which influence scores reverse sign when training data is adversarially perturbed within a small ℓ∞\ell_ {\infty} budget. Malleability measures how brittle the outputs of influence functions are under data perturbation, as a consequence of the kernel's ill-conditioning. Malleability is a property of influence-function outputs, distinct from the model's adversarial robustness.


W1, W6, W11 (scope of analysis and linearized attention terminology). Linearized attention designates the first-order Taylor expansion of softmax attention around the identity projection (Section 3.1: fatt(X)=XX⊤Xf^ {\text{att}}(\mathbf{X}) = \mathbf{X}\mathbf{X}^ {\top}\mathbf{X}). Softmax attention admits no exact NTK because its score matrix depends nonlinearly on both queries and keys, making the kernel ill-defined at finite width. Linearized attention is the tractable proxy, obtained by applying exp⁡(Aij)≈1+Aij\exp(A_ {ij}) \approx 1 + A_ {ij} to the score matrix and fixing QKV projections to the identity, which yields a closed-form kernel that can be analyzed exactly (Section 3.1, Appendix C). It differs from the trainable efficient-attention architectures (Katharopoulos et al., 2020; Choromanski et al., 2021) that share the "linear attention" label in the systems literature, which approximate softmax via learned feature maps. CNNs (locally-connected convolutions) and Mamba (selective state-space dynamics) do not employ attention maps of the form XX⊤\mathbf{X}\mathbf{X}^ {\top}, so the cubic identity κd(G~)=κd(G)3\kappa_ {d}(\tilde{\mathbf{G}}) = \kappa_ {d}(\mathbf{G})^ {3} requires a separate derivation for each.

The two main results generalize differently. The cubic identity is architecture-specific. The malleability floor result (Theorem 4.9), however, holds for any influence operator whose kernel factors through the data Gram G\mathbf{G}, since such an operator inherits κd(G)\kappa_ {d}(\mathbf{G}) as a conditioning floor as a consequence of the kernel's range structure. Section 5 and Table 3 measure κd(G)\kappa_ {d}(\mathbf{G}) on over 20 diverse pretrained models (ViT, CLIP, ResNet, DINO) and find large values uniformly on natural image datasets, confirming that the conditioning floor reflects a property of the data geometry shared across architectures.

The cubic amplification result (Theorems 4.2, 4.4–4.5) is specific to the XX⊤X\mathbf{X}\mathbf{X}^ {\top}\mathbf{X} feature map. Establishing the analogous identity for CNNs or Mamba requires a separate derivation. The malleability floor (Theorem 4.9) applies more broadly: any influence operator whose kernel factors through G\mathbf{G} inherits κd(G)\kappa_ {d}(\mathbf{G}) as a conditioning lower bound, regardless of architecture. The revised Section 3.1 makes both scopes explicit.

W2, W3 (motivation and the uncharacterized learning dynamics claim). The core motivation is that influence methods (TRAK, DataInf, EK-FAC) assume the kernel regime holds for transformers, yet whether attention actually enters that regime has not been established. Figure 1 is the primary motivation figure. It plots NTK distance between Km\mathbf{K}_ {m} and K∞\mathbf{K}_ {\infty} as a function of width for 2L-ReLU and MLP-Attn on MNIST and CIFAR-10 and shows that the two architectures behave qualitatively differently: 2L-ReLU converges, MLP-Attn does not. The "largely uncharacterized" claim traces directly to Yang (2020, Remark 7.4), which explicitly deferred NTK convergence analysis for architectures outside the backpropagation regime, including attention. The revised introduction anchors the claim to Yang (2020, Remark 7.4) and notes that whether influence methods depending on this assumption work for transformers has not been shown. The present paper resolves that deferred case for the first-order proxy.


W4 (evidence for the 3–9× flip rate range). Table 1 gives the exact numbers. In the 10-class MNIST setting, the influence flip rate under FGSM is 34.6% for MLP-Attn versus 4.1% for 2L-ReLU (ratio ≈ 8.4×). Under PGD, the rates are 28.9% versus 3.3% (ratio ≈ 8.8×). In the 10-class CIFAR-10 setting, the FGSM ratio is 26.4%/3.3% ≈ 8.0×. The 3–9× range covers these multiclass measurements. Binary CIFAR-10 is a confounded setting acknowledged in Section 5.3 and Appendix B.1.


W5 (theoretical proof of adversarial vulnerability). Theorem 4.2 shows that KLinAttnK_ {\text{LinAttn}} routes each influence score through all nn training points via G\mathbf{G}, so a small input change propagates globally. Theorem 4.4 shows the attention map cubes the condition number: κd(G~)=κd(G)3\kappa_ {d}(\tilde{\mathbf{G}}) = \kappa_ {d}(\mathbf{G})^ {3}. With κd(G)≈9×108\kappa_ {d}(\mathbf{G}) \approx 9\times10^ {8} on MNIST, the kernel inversion (K+λI)−1(\mathbf{K}+\lambda\mathbf{I})^ {-1} becomes sensitive to small perturbations. Theorem C.23 gives a stability bound showing that a perturbation of size ϵ\epsilon to the kernel changes influence scores by at most ϵ/[λ(λ−ϵ)]\epsilon/[\lambda(\lambda-\epsilon)]. When λ1(K)≫λ\lambda_ {1}(\mathbf{K}) \gg \lambda — the case here — this bound is too large to certify stability, so influence scores carry no reliability guarantee. Theorem 4.9 extends the ill-conditioning to trainable QKV projections: the floor κ+(K)≥κd(G)\kappa^ {+}(\mathbf{K}) \geq \kappa_ {d}(\mathbf{G}) holds regardless of initialization, so the vulnerability is structural, independent of the parameter-free proxy. Table 1 and Section 5.3 show the 6–9$\times$ flip-rate gap that this predicts.

W7, W8, W9 (AutoAttack, C&W, diffusion attacks, and ImageNet evaluation). The experiments test one theoretical prediction: that kernel non-convergence produces higher sensitivity of influence scores to training-data perturbations. The metric is the stability of attribution scores under perturbation, determined by the kernel's conditioning. The flip rate under any perturbation method is governed by the conditioning of (K+λI)−1(\mathbf{K} + \lambda\mathbf{I})^ {-1}: a poorly conditioned kernel amplifies sensitivity to any perturbation with nonzero projection onto the low-eigenvalue subspace, regardless of how that perturbation is generated. AutoAttack, C&W, and diffusion attacks operate via different generation mechanisms, but the quantity being measured — stability of influence scores under bounded perturbation — depends on the kernel's spectral structure. The specific attack family determines only how the perturbation is generated. FGSM and PGD are sufficient to expose this structure, and the theoretical results apply unconditionally.

2L-ReLU is the simplest architecture for which NTK convergence is fully established by classical theory (Jacot et al., 2018; Lee et al., 2019). MLP-Attn = 2L-ReLU with a linearized attention block. The two architectures differ in exactly one component, so any malleability difference is unambiguously attributable to that component. Replacing 2L-ReLU with Mamba, ViT, or another architecture introduces multiple simultaneous differences and severs the connection to the theoretical prediction. Malleability experiments on Mamba additionally require first establishing that Mamba's feature map induces cubic conditioning amplification, a separate theoretical result the paper does not claim. ImageNet-scale evaluation requires exact NTK computation well beyond the tractable ceiling of m≤4096m \leq 4096.


W10 (additional qualitative analysis). The paper includes Figures 1–8 covering NTK distance curves, influence flip rate measurements, NTK validation, training dynamics, pretrained model conditioning across more than 20 models, and an adversarial training ablation. Additional illustrations for any specific aspect are available on request during the discussion period.


W12 (comparison with prior methods). Zhang & Zhang (2022) provides the influence formulation on which the paper is built directly (Section 3: "following the NTK-based influence formulation of Zhang & Zhang (2022)"). TRAK (Park et al., 2023) deploys the same KRR-linearization on trained transformers. The revised text makes this explicit: "the same approach is deployed by TRAK (Park et al., 2023) on trained transformers." Both are cited in Related Work as representative influence methods whose NTK-regime assumption this paper examines. Direct comparison of attribution quality would constitute a separate empirical benchmarking study. The present work examines the theoretical preconditions for these methods.


W13 (missing citations). Citations for Mamba, RWKV, DeepSeek-V3, and Kimi-K2 have been added at their first occurrence in the revised text.


Summary. The paper establishes that no practical width certifies NTK convergence for the linearized-attention architecture. With κd(G)≈9×108\kappa_ {d}(\mathbf{G}) \approx 9 \times 10^ {8} on MNIST, the necessity lower bound (Theorem 4.5) already exceeds 102610^ {26}; the sufficient width from Theorem 4.4 is larger still. Controlled experiments on MNIST and CIFAR-10 corroborate this quantitatively. The scope is restricted to architectures employing the XX⊤X\mathbf{X}\mathbf{X}^ {\top}\mathbf{X} feature map. CNNs and Mamba lie outside this class. Further discussion is welcome during the review period.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.