CS Paper Radar

Attention Kernels for Learning Maps Between Heavy-Tailed Measures

Kailen Hargenrader, Edoardo Calvello, Bohan Chen

cs.LG ·submitted 2026-09-30 18:38 UTC · v1
published

Abstract

Operator learning on probability measures can be accomplished with transformers. For measures with polynomial tails, the exponential weighting in softmax can make the corresponding measure-level attention integrals diverge. This motivates replacing the exponential with slower-growing functions. We construct two benchmarks for operator learning on measures with closed-form targets. We use these benchmarks to study attention kernel growth and data transformation in post-norm transformers. Without data transformation, the softmax models exhibit ensemble collapse on both heavy-tailed benchmarks, while the three slower-growing kernels avoid collapse. Symlog preprocessing allows softmax to avoid collapse on the matrix inverse task but not on the sheared swap task. On the Gaussian control, all four kernels perform similarly. We also examine how sample size affects the sensitivity of empirical energy and Wasserstein distances to tail differences. These results support slower-growing attention kernels as an effective design choice for post-norm transformers learning from heavy-tailed ensembles.

Comment
32 pages, 17 figures, accepted to NeurIPS 2026 Workshop on AI for Stochastic Dynamics

Closest papers

Nearest neighbours by meaning across the whole index.

Training-Free Universal Approximation by Prompting Random Transformers

cs.LG math.NAmath.ST ·2026-08-10 ·Alexander Hsu, Rongjie Lai
similarity 0.72
Abstract · 31 pages, 5 figures. Comments welcome!

How expressive is prompting a transformer? Answering this question is important for separating the roles of prompting, architecture, and pretraining in transformer models, and for determining whether task-specific behavior must be stored in model weights or can instead be induced at inference time through the prompt. We show, in an approximation-theoretic sense, that pretraining is optional: a single-layer softmax attention network with random, untrained weights can approximate any Hölder function on a compact manifold when steered by an appropriate soft prompt. Guided by the connection between softmax attention and kernel methods, we construct explicit soft prompts (a prompt per target function, independent of the query) as solutions to linear systems matching attention logits to Gaussian kernel exponents, under which the frozen transformer emulates the classical Nadaraya-Watson kernel estimator. The construction requires only a mild rank condition on the weights, which we show holds almost surely under Gaussian initialization. The prompted network inherits the theoretical guarantees of kernel regression, leading to universal approximation theorems with minimax-optimal rates that depend on the intrinsic dimension. We further quantify the cost of prompting, exposing a tradeoff between the norm of the constructed soft prompt tokens, prompt length, and hidden dimension. Numerical experiments corroborate the constructions and predicted rates.

0.40

Stability of Measure-to-Measure Transformers on Sub-Gaussian Data

cs.LG stat.ML ·2026-10-06 ·Frank Cole, Nicholas H. Nelsen, Takashi Furuya
similarity 0.67
Abstract

Transformers have exhibited impressive empirical success across various domains, but their theoretical foundations remain less developed. This work constitutes a mathematical study of the measure-to-measure operators defined by transformers. We show that transformers map sub-Gaussian inputs to sub-Gaussian outputs; this ensures that taking arbitrary-length compositions of the softmax operator is well-defined. We then show that transformers are Hölder continuous with respect to the 1-Wasserstein distance on appropriate spaces of sub-Gaussian inputs. This allows us to establish estimates on the error propagation along a transformer between a sub-Gaussian input and its empirical approximation. We also study a mean-field analog of the cross-attention mechanism, which is an operator from a pair of probability measures to a single probability measure. We show that cross-attention exhibits different Hölder regularity and sample-complexity in its two input arguments. Last, we apply our results to deduce approximation guarantees for measure-to-measure transformers. Together, these results provide a firm stability and finite-sample theory for transformers on sub-Gaussian data.

0.53

The Kernel Reality Check: Benchmarking and Distilling Efficient Attention at Scale

cs.LG ·2026-11-17 ·Fırat Öncel, Cem Subakan, Mirco Ravanelli, Çağatay Yıldız
top venuecode/data similarity 0.66
Abstract · Accepted at NeurIPS 2026. 20 pages

Kernelized attention methods, which aim to replace the $O(N^2)$ complexity of softmax attention with $O(N)$ alternatives, have been the focus of intense research in the last five years. Despite growing interest, systematic evaluations and fair comparisons across approaches and scales are still missing. We analyze kernelized attention in two halves and highlight prominent limitations on each. On efficiency, FlashAttention achieves lower memory consumption and faster wall-clock time than SOTA kernelized methods during training and in vision transformers across most sequence lengths (with inference-time memory in causal language models the only clear exception), contradicting the core assumption for pure kernelized attention used as a drop-in replacement for softmax. We also discover that reported efficiency gains often fail to reproduce against modern baselines. On quality, current kernelized methods leave gaps of 2-10 points relative to softmax under a unified distillation protocol, and model scala alone does not close these gaps. We show this gap is not intrinsic to kernelization: LARA++, a principled extension of LARA that approximates softmax via importance sampling with adaptive proposal distributions, recovers up to 99% of softmax accuracy. We establish that the gap is closable; however, the computational overhead remains substantial, leaving the efficiency wall intact. Code is available at https://github.com/firatoncel/KernelRealityCheckNeurIPS2026

0.75

Quasi Linear Kernel Attention with Infinite Capacity

cs.LG math.NA ·2026-09-28 ·Nicolaj Rux, Johannes Hertrich, Sebastian Neumayer
benchmarktheory similarity 0.66
Abstract

The evaluation cost of transformers with softmax attention scales quadratically with sequence length. Kernel attention addresses this by replacing softmax with a more general kernel function. In this paper, we aim to identify kernels that retain the expressivity of attention while enabling quasi linear computation. To quantify expressivity, we introduce a capacity for each kernel, measuring the maximum sequence length for which the attention matrix can approximate the identity. A higher capacity thus indicates greater expressivity. We show that expressive kernels like softmax, Gauss, and Laplace have infinite capacity. In contrast, common quasi linear kernels, such as those derived from finite dimensional feature maps, exhibit finite capacity. As a solution, we propose additive kernels constructed from univariate spline and polynomial exponential kernels. We prove that these maintain infinite capacity while allowing quasi linear computation via sorting. Finally, we implement additive sorting kernels efficiently and benchmark them against modern softmax backends, demonstrating advantages for long sequences.

0.32

Transformers as Adaptive Kernel Learners across Tasks for In-Context Learning

cs.LG math.NAmath.ST ·2026-10-17 ·Zhaiming Shen, Alexander Cloninger, Rongjie Lai, Wenjing Liao
similarity 0.66
Abstract

Transformers have emerged as a dominant architecture in modern machine learning, with in-context learning (ICL) enabling models to adapt to new tasks by conditioning on prompts, without any parameter updates. To understand the attention mechanism in transformer blocks, a growing line of theoretical work interprets ICL through the lens of classical statistical estimators. Recent works have established a connection between the attention mechanism and kernel methods, while the kernel function is usually assumed to be fixed. In practice, the query and key matrices in the attention mechanism are trained, which allows the attention mechanism to serve as an adaptive kernel method. In this work, we demonstrate that transformers can act as adaptive anisotropic kernel learners. Specifically, we study ICL for low-rank linear and multi-index nonlinear regressions, and conduct numerical simulations to show that the learned attention scores closely resemble the oracle kernels for these function classes. We then develop a general framework to analyze the generalization error of ICL by connecting transformers to the oracle kernel estimator for each function class. Our theory gives an explicit and constructive implementation of the oracle kernel estimators for these function classes using a wide and shallow transformer architecture, illustrating how the prediction is carried out by the interaction between the query token and the context tokens. Our work complements existing studies by providing numerical and theoretical evidence of how the attention mechanism adapts to anisotropic kernels in both linear and nonlinear settings.

0.13

Measure Neural Mappings

cs.LG stat.ML ·2026-10-12 ·Ricardo Baptista, Edoardo Calvello, Bohan Chen, Andrew Stuart, Urbain Vaes
theory similarity 0.66
Abstract · 65 pages, 6 figures, 7 tables

We introduce and define measure neural mappings (MNMs), which combine measure-dependent neural transport with ensemble consistency for learning operators on probability measures. Ensemble consistency requires outputs from growing ensembles sampled from an input law to converge to the specified population output in probability. We establish quantitative continuum limits for attention on noncompact laws under strong sub-Gaussian and tail-integrability assumptions. These laws accommodate unbounded state spaces in scientific machine learning, including Bayesian inference and uncertainty quantification. For fixed self-attention transformers, the expected output Wasserstein error is bounded by the empirical input Wasserstein error plus an additional $N^{-1/2}$ attention term. These self-attention transformers are MNMs under the stated assumptions: pre-norm architectures follow from compact stability after normalization, while post-norm architectures are covered under the stated tail conditions. We prove corresponding cross-attention estimates and extend the results to multihead attention and grouped transformer evaluation, with convergence as the group size grows. For Set Transformers viewed as measure-to-vector mappings, we obtain an $N^{-1/2}$ bound on the expected Euclidean output error under the stated assumptions. Experiments on seven operators in dimensions $d=1,2,3,5,10$ support the predicted particle-count dependence, using one-dimensional Wasserstein computations and Sinkhorn approximations in higher dimensions. The observed Wasserstein and sliced Wasserstein decay rates are close to their respective theoretical sampling benchmarks.

0.18

Flow-based Spectral Kernel Learning for Nonstationary Attention

cs.LG stat.ML ·2026-10-21 ·Zi Yang, Ying Li, Alejandro Lancho, Darío C. Larese, Pablo M. Olmos +1 more
code/data similarity 0.65
Abstract · 23 pages

Kernelized attention provides a useful perspective for understanding self-attention as a similarity-based aggregation mechanism, but existing approaches often rely on fixed or stationary kernels, limiting their ability to adapt the similarity structure to complex token interactions. In this paper, we propose flow-based spectral kernel attention (FSKA), a framework for learning expressive nonstationary attention kernels. FSKA formulates kernelized attention through spectral density learning and parameterizes the resulting bivariate spectral density with normalizing flows. This design enables flexible and regularizable kernel learning while remaining compatible with scalable linear-attention computation. We further show that expressive kernel learning enables a simplified attention design with removed query--key projections and fixed orthogonal value projections, resulting in a more parameter-efficient architecture. Controlled experiments on classification, ablation, and scalability profiling show that FSKA achieves competitive or improved performance over existing attention mechanisms, while reducing projection-related trainable parameters by approximately $40\%$--$47\%$ compared with most baselines and maintaining favorable linear-attention memory scaling. Code Available: https://github.com/ziyang18/FSKA.

0.29

Counting with Attention and LayerNorm: Norm Scaling and Representation Geometry

cs.LG ·2026-10-12 ·Ayyub Shaffy, Manoj Dhakal, Safal Shrestha, Keith W. Ross
similarity 0.65
Abstract · 29 pages, 8 figures, 3 tables

Counting is a simple task on which transformers can nevertheless fail at long sequence lengths. We study the cost of counting in a single attention layer, up to a maximum length $L$, focusing on how softmax attention and layer normalization shape the representation from which the count is recovered. We mainly focus on regression read-out but also consider classification read-out. For regression, we show unnormalized linear attention counts exactly at parameter norms independent of $L$. For softmax attention, regression cannot count exactly with finite parameters; it recovers the count after rounding, but only when the vector parameter norms grow with $L$. We measure this cost by $B_{\min}$, the smallest bound that can be placed on every trainable vector to ensure exact counting after rounding, and derive tight rates. At fixed model dimension, $B_{\min}$ grows as $L$ without normalization, as $L^{3/2}$ under bare post-normalization, and as $L^{3/4}$ with learned post-normalization. The last rate is unexpected: post-normalization discards the magnitude that carries the count and might be expected to make counting harder, yet with a learnable gain it counts at a smaller norm than softmax without normalization. Bare pre-normalization is different: it bounds the attention scores, so beyond a finite length no parameter norm suffices. A classification read-out keeps every norm bounded under every placement, but a dense head stores one output vector per count and costs more in storage. Experiments on the post-normalized model reproduce this split between the two read-outs. Together, our theoretical and empirical findings characterize how self-attention, layer-normalization placement, and read-out choice shape the representation geometry and parameter cost of counting in the minimal single-head architecture studied here.

0.29