- 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
- 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.
- 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.
- 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
- How does the kernel approximation criterion relate to attribution accuracy under regularization? Section 3 describes the approximation requirement in terms of the regularization scale , whereas the main width theorems use error relative to \lambda_{\min}(K_\infty). For the values of used in the experiments, is the latter criterion necessary for accurate influence estimation?
- 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?
- 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
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
where is the spectral-norm difference between and . This bounds the absolute deviation of the influence vector as a function of .
The relative criterion is necessary for sign accuracy. The ridge stabilizes eigenvalues of but leaves the eigenvectors of unchanged. The sign of depends on the alignment of example with 's eigenmodes. When , the bottom eigenvectors rotate substantially from those of (Davis-Kahan), flipping sign independently of . At the measured , , making the relative criterion far more stringent than the -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 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 changes all remaining feature representations through ) 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, -scaled regime, the softmax score matrix 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 depends on both the parameters and the input . 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 (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 , 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.
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 ε-approximate NTK convergence is at least Ω(κd(G)6logn/ε2), where convergence means
∥Km−K∞∥2/λmin(K∞)≤ε.
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 ε, any width below 1/(8ε2λmin(K∞)2) must fail. The two-point coalescing construction (Appendix C.14) establishes that the lower bound attains κd(G)3 scaling, confirming the cubic exponent in Theorem 4.4 is tight and intrinsic to the architecture. With κd(G)≈9×108 for MNIST, the necessity lower bound alone already exceeds 1026, 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) 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 cannot flip attributions when λ>εK, a condition that fails for MLP-Attn because the floor result forces λmin(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 is close to K∞ at the widths studied for 2L-ReLU, so the stability bound applies tightly. The formal connection between the malleability measure μˉ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 flips influence signs.