Kernelized Linear Attention: Breaking the Capacity Wall with Symmetric Cones

• URL: http://arxiv.org/abs/2607.17419v1
• Date: Sun, 19 Jul 2026 21:46:09 GMT
• Title: Kernelized Linear Attention: Breaking the Capacity Wall with Symmetric Cones
• Abstract summary: Linear attention promises constant-time recurrent inference but degrades sharply on associative recall.<n>We introduce Kernelized Linear Attention Activations (KATA), a framework whose feature maps are derived from first principles.<n>We show that rank-one positive semi-definite features offer a favorable capacity--interference tradeoff.
• Score: 4.847095054351615
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Linear attention promises constant-time recurrent inference but degrades sharply on associative recall. We formulate attention recall as a spherical-packing problem and introduce Kernelized Linear Attention Activations (KATA), a framework whose feature maps are derived from first principles by certifying nonnegative attention weights through a self-dual homogeneous cone. Building on this observation, we show that rank-one positive semi-definite (PSD) features offer a favorable capacity--interference tradeoff. KATA recovers a parameter-free convex output gate and characterizes associative capacity through the Welch interference floor. For tolerances above this floor, KATA enlarges the state without adding parameters and admits spherical codes with exponentially many keys in the projection dimension. We implement KATA as fused Triton kernels at two operating points: a flash-attention-style forward up to ${\sim}1.6\times$ FlashAttention-2 throughput, and an exact $O(T)$ chunked-state form that reaches ${\sim}11\times$ FlashAttention-2 forward throughput at $131$k tokens. An associative scan of the first-order feature lowers the inter-chunk recurrence depth to $O(\log(T/C))$ for chunk size $C$ and averages ${\sim}2.4\times$ the throughput of a matched sequential linear-attention baseline. On long-range MQAR and repeated-key overwrite, several KATA variants outperform Gated DeltaNet, with parameter counts and state sizes reported alongside accuracy. Induction preserves near-perfect recall, while kernel benchmarks show that the maps can be implemented efficiently. KATA retains $0.985$ MQAR at a $16\times$ out-of-distribution length, approaching the softmax with roughly one quarter of the KV-cache entries. Experiments on 340M-parameter LLMs reveal a feature-dependent fluency trade-off and clarify how positional embeddings, delta rules, and decay gates interact with feature geometry.

Related papers

• SANE: State Anomaly Neutralization for Stable Extreme-Context Delta-Rule Models [53.86918766240095]
  Delta-Rule recurrent models maintain a fixed-size state, enabling $O(1)$ inference memory but potentially becoming unstable under extreme-context extrapolation.<n>We propose textbfState Anomaly Neutralization (SANE), which applies adaptive $tanh$ compression at chunk boundaries while preserving the intra-chunk parallel structure.
  arXiv  Detail & Related papers  (2026-08-23T10:41:07Z)
• Flash-CNNCap: Capacitance Extraction via Image Mapping [3.790585344640331]
  Flash-CNNCap is a CNN-based extractor that reformulates full-matrix capacitance prediction as image-to-image regression over spatial contribution maps.<n>A total-capacitance model and a master-conditioned coupling model each predict a spatial map that is reduced to conductor-level values.<n>The maps are learned from conductor-level labels without per-pixel supervision.
  arXiv  Detail & Related papers  (2026-07-26T22:46:20Z)
• Attention at the Theoretical Minimum: A Mathematics of Arrays Framework for Memory-Optimal Transformer Kernels [0.0]
  We present a reformulation of scaled dot-product attention and its numerically stable softmax.<n>The DNF achieves $O(n_dk + n_dv)$ data movement versus $O(n2 + n_dk + n_dv)$ for the standard implementation.<n>Unlike hardware-specific accelerators or empirical tiling schemes such as FlashAttention, MoA simultaneously provides array fusion, shape-transformation correctness, and predictive cost models.
  arXiv  Detail & Related papers  (2026-06-05T14:44:49Z)
• LimiX-2M: Mitigating Low-Rank Collapse and Attention Bottlenecks in Tabular Foundation Models [56.999481798138625]
  LimiX-2M is a 2M- parameter model that outperforms larger TabPFN-v2 and TabICL baselines on widely used benchmarks.<n>We present a unified tokenize-and-route framework for strong Tabular foundation models (TFMs)<n>Results highlight value-aware tokenization and readout-aligned routing as key levers for improving the accuracy--efficiency trade-off in TFMs.
  arXiv  Detail & Related papers  (2026-06-03T06:07:33Z)
• Tensor Cache: Eviction-conditioned Associative Memory for Transformers [20.67103891489219]
  Cache pairs sliding-window softmax attention as a first-level cache (L1) with a fixed-size outer-product fast-weight memory as a second-level cache fed by KV pairs evicted from the window.<n>Recent tokens remain in exact local attention; evicted pairs are compressed into a per-layer matrix $A$ and read by future queries through a single matrix multiplication.
  arXiv  Detail & Related papers  (2026-05-21T00:21:51Z)
• Variational Linear Attention: Stable Associative Memory for Long-Context Transformers [0.6117371161379209]
  Linear attention reduces the quadratic cost of softmax attention to $mathcalO(T)$, but its memory state grows as $mathcalO(T)$ in Frobenius norm.<n>We introduce textbfVariational Linear Attention (VLA), which reframes the memory update as an online regularised least-squares problem.
  arXiv  Detail & Related papers  (2026-05-11T20:03:12Z)
• Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval [59.859592671274704]
  How many key-value associations can a $dtimes d$ linear memory store?<n>We show that the answer depends not only on the $d2$ degrees of freedom in the memory matrix, but also on the retrieval criterion.
  arXiv  Detail & Related papers  (2026-05-06T17:53:20Z)
• Linear-Readout Floors and Threshold Recovery in Computation in Superposition [0.0]
  Two recent approaches to computation in superposition reach different capacity regimes.<n>We argue these results are not contradictory because they maintain different interface invariants.<n> Robust nonlinear reset beyond the Hnni template is left open.
  arXiv  Detail & Related papers  (2026-05-02T02:11:31Z)
• AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT [1.2891210250935148]
  AAC is a differentiable landmark-election module for ALT (A*, Landmarks, and Triangle) shortest-paths.<n>It is the first differentiable instance of the compress-while-admisibility tradition in classical search.
  arXiv  Detail & Related papers  (2026-04-22T16:31:21Z)
• Scaling Attention via Feature Sparsity [50.64995497733461]
  Scaling Transformers to ultra-long contexts is bottlenecked by the $O(n2 d)$ cost of self-attention.<n>We propose Sparse Feature Attention, where queries and keys are represented as $k$-sparse codes that preserve high-dimensional expressivity.<n>Across GPT-2 and Qwen3 pretraining, SFA matches dense baselines while improving speed by up to $2.5times$ and reducing FLOPs and KV-cache by nearly 50%.
  arXiv  Detail & Related papers  (2026-03-17T08:41:50Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses. We propose a new algorithm that attains an $widetildeO(dsqrtHS3K + sqrtHSAK)$ regret with high probability.
  arXiv  Detail & Related papers  (2024-03-07T15:03:50Z)
• H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models [110.06476624089679]
  We introduce a novel approach for implementing the KV cache which significantly reduces its memory footprint. Our approach is based on the observation that a small portion of tokens contributes most of the value when computing attention scores. We propose Heavy Hitter (H$$O), a KV cache eviction policy that dynamically retains a balance of recent and H$$ tokens.
  arXiv  Detail & Related papers  (2023-06-24T20:11:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.