acceptodds
Under review as a conference paper at ICLR 2027

Kernelized Linear Attention: Breaking the Capacity Wall with Symmetric Cones

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 certifying attention activations on 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 also recovers a parameter-free convex output gate and characterizes associative capacity through the Welch interference floor. We implement KATA as fused Triton kernels at two operating points: a flash-attention-style forward up to FlashAttention-2 throughput, and an exact chunked-state form that reaches FlashAttention-2 forward throughput at k tokens. 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 MQAR at a 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.

Primary area:
learning theory
Keywords:
linear attention, transformers, kernel methods, LLM, pretraining

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_fxJ6OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Kernelized Linear Attention Activations (KATA), a framework that studies linear-attention feature maps through the geometry of symmetric cones. It analyzes associative recall using spherical-packing bounds and power signal-to-noise ratio (pSNR), showing that rank-one positive semidefinite (PSD) features can reduce interference through squared inner products and improve idealized retrieval capacity. The authors develop several PSD-based linear-attention variants with additive, gated, and delta-rule updates, alongside Triton implementations. Experiments on MQAR, repeated-key overwrite, and 340M-parameter language models demonstrate substantial improvements in associative recall over existing recurrent architectures, although these gains involve larger recurrent states and trade-offs in language-modeling quality.

Critical strengths
  • Principled geometric analysis of associative capacity. The paper connects symmetric-cone geometry, spherical packing, and interference bounds to explain limitations of linear attention. The PSD construction and pSNR analysis provide a useful theoretical perspective on how nonlinear feature maps improve associative recall.

  • Strong associative-recall results across multiple settings. KATA-M1 achieves 0.985 MQAR accuracy at 16× extrapolation, compared with 0.419 for Gated DeltaNet, while KATA-M2 substantially improves high-entropy UUID retrieval in pretrained language models (0.616 vs. 0.004 at 2K). The repeated-key overwrite experiments further demonstrate the complementary benefits of feature geometry and delta-rule updates.

Critical weaknesses
  • Unclear quality-efficiency advantage over existing architectures. The improved recall relies on substantially expanded PSD feature states: KATA-M1 uses 266K state entries versus 65.5K for the largest Gated DeltaNet baseline, while the linear-state PSD kernels remain slower than Gated DeltaNet. Without state-matched comparisons against competitive architectures or simpler quadratic feature maps, it is difficult to establish whether the proposed geometry offers a superior capacity-efficiency trade-off rather than primarily benefiting from increased state size.

  • Limited validation of practical language-modeling benefits. The pretrained experiments are restricted to 340M models with 2K context, where KATA generally exhibits worse perplexity than Gated DeltaNet and softmax attention. Moreover, the strong MQAR length extrapolation deteriorates sharply with RoPE (Table 5), and the pretrained models also struggle beyond their training horizon, raising concerns about whether the associative-recall improvements translate to practical long-context language modeling.

Questions for authors
  • Can the authors provide state-memory-matched comparisons against Gated DeltaNet and simpler quadratic-kernel baselines, together with inference latency, to establish whether KATA improves the recall-efficiency Pareto frontier?

  • Can the authors clarify whether the RoPE extrapolation failures are intrinsic to the squared-inner-product kernel and whether the improved recall persists under controlled, architecture-matched comparisons at longer context lengths?

3 comments
AuthorsOpenReview ↗

Rebuttal P1

We thank the reviewer for recognizing the originality of our geometric analysis and for raising some important questions related to the recall-efficiency advantage of KATA feature maps.

Before we address the raised questions, we invite you to check our responses to the other reviewers and our clarification about our contributions.

The limitation on the 340M LLMs are not due to recall, our results show that PSD kernels do better at retrieval than first order linear attention. What the LLMs results demonstrate is that the improved recall is not sufficient to improve language modeling tasks, especially when mixing similar concepts. This motivates integrating the delta-rule into the KATA framework to incorporate overwrite as well, but is left for future work.

To address the questions raised by the review:

Q1. Can the authors provide state-memory-matched comparisons against Gated DeltaNet and simpler quadratic kernels, together with inference latency? A1: The advantage of using PSD outer product expansion is that we can get larger state space without adding parameters to the neural network. When kk have dd dimensions, we can map the key to a D=d(d+1)/2D=d(d+1)/2 state space via the outer product kk⊤k k^\top. First order attention (GLA, GDN) has to map to DD directly to get the same capacity. In the Qwen3.5 4B, that means that the model has to add 16B parameters in its GatedDeltaNet layers to achieve similar capacity to the quadratic PSD kernel. The inference in this case we be dominated by the projections WKW_K and WQW_Q, not by the the linear attention state-space update.

Our paper also compares different architectures at various states space sizes. Even in equal state space size, PSD kernels are better at recall.

Based on Table 1 (other expanded results are in the appendix), closely matched feature-value state sizes:

MethodHeadDimParametersStateEntriesMQAR@2KMQAR@4K
GatedDeltaNet2566,047,75065,5360.9090.419
KATA-Σ2\Sigma2641,134,01667,5841.0000.958

We have deliberately introduced KATA-Σ2\Sigma2 (PSD features) to get smaller feature-value space, and it achieves 0.958 versus 0.419 at 16× the training length, with similar state entries and 5.33× fewer parameters. The improvement therefore persists at substantially smaller state sizes than KATA-M1's 266,240 entries (our response to Reviewer 6Aqr discusses the MQAR selection protocol).

So KATA PSD feature maps are not only closer to recall-efficiency pareto boundary, but also to the parameterization-recall pareto frontier. We have expanded on the later using Qwen3.5-4B as example in our response to Reviewer iocT: how KATA does not require additional model parameters to improve recall. The expanded state space is 10x cheaper than expanding the attention head dimension.

Q2. Are RoPE extrapolation failures intrinsic to the squared kernel, and does recall persist in controlled longer-context comparisons?

A2: The failure is not unique to the squared kernel. Table 5 includes the following MQAR ablation at 4K, after training up to 256 tokens:

MethodWithout RoPEWith RoPE
Softmax1.0000.012
KATA-M20.9700.003

The pretrained models share a 340M backbone, while mixer components differ. At 2K, UUID recall is 0.616 for KATA-M2, 0.004 for GDN, and 0.930 for softmax. Replacing KATA-M2's RoPE with a GDN-style short convolution retains 0.530, so its in-window recall benefit does not require RoPE.

KATA's strong result without RoPE shows that the squared kernel can extrapolate on this task. The issue when RoPE is used is two folds:

  • The mechanism overfits on the training length.
  • The RoPE decaying is weaker in linear attention, we expand on this in Appendix B.3 (L:1018) in our paper and how RoPE affects attention scores in linear attention vs. softmax attention.

The motivation behind KATA is maximizing recall at fixed state space, which PSD feature map is optimal under hardware constraints. Whether that translates to better language modeling is a different question: our empirical results show that it's negative. When we incorporated Delta-rule with KATA, we got better perplexity on Wikitext than GDN and reduced it over LAMBADA by 1 nat. Delta-rule in our (novel) overwrite benchmark showed that it resolves the issue of mixing different values for the same key, which we interpreted as better fluency. In a much simpler analogy: if one has better ability at memorizing the information they hear, that does not mean they're better at combining pieces of information with subtle differences. Softmax attention which its large capacity is still better at the mixing. These results show that treating attention as pure associative recall mechanism is not doing it justice and suggests better architecture via a DeltaKATA variant.

Thank you for the detailed rebuttal and clarifications.

The state-matched comparison between KATA-$\Sigma$2 and Gated DeltaNet addresses my primary concern in Q1. Achieving substantially better MQAR accuracy (0.958 vs. 0.419 at 4K) with comparable state sizes provides convincing evidence that the improvement is not simply due to a larger recurrent state. I also appreciate the parameter-efficiency argument for PSD feature expansion, although a direct latency comparison would further strengthen the practical efficiency claims.

Regarding Q2, I agree that the RoPE extrapolation failure is not specific to KATA, as the softmax baseline exhibits similar degradation. The distinction between associative recall capacity and general language-modeling quality is also well taken. However, the practical benefits remain somewhat limited: while DeltaKATA improves WikiText perplexity over Gated DeltaNet, its LAMBADA perplexity remains higher, and the results suggest that improved recall alone is insufficient for stronger language modeling.

Overall, the rebuttal resolves much of my concern about the recall-efficiency advantage and clarifies the intended scope of the contribution. Given the theoretical insights and convincing associative-recall improvements, I am inclined to increase my rating to reflect them, while retaining some reservations about the practical language-modeling benefits and end-to-end efficiency.

We appreciate the reviewer's follow-up and for reconsidering their assessment after addressing their concerns.

Regarding the practical language-modeling benefits of linear attention, it's worth noting that it's a core result of the empirical experiments: expanding the capacity of the linear attention mechanism using our KATA approach significantly improves recall, but not fluency. That's also the reason we introduced the (new) overwrite benchmark (which is not part of the Zoology's test suite). Our diagnosis relates exactly to the point you have raised about RoPE: within linear attention mechanisms (not just KATA-derived), RoPE does not provide a positional signal that is strong enough to encode the sequential order of the keys. The delta-rule allows to solve this by explicitly decaying the values associated with already seen keys, but that might not be a desirable effect if the task favors an older value. Hence the need for learnable forget/keep scores. These are promising directions for future work.

Reviewer_iocTOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper the authors study how the feature map used in linear attention affects the ability to retrieve key/value associations from a memory of fixed size. In linear attention the authors replace the softmax exponential with an inner product between finite feature vectors. The authors schematize feature maps with nonnegative similarity using symmetric cones and focus on positive-semidefinite (PSD) features of the form ψ(u)=uu⊤\psi(u)=uu^\top, which give the squared dot-product term (q⊤k)2(q^\top k)^2.

The authors use geometric packing bounds to study how many key representations can have small pairwise overlap. They also derive a signal to noise comparison between linear and quadratic features. Their KATA models (Kernelized Linear Attention Activations) use these features with rules that add new information, reduce the influence of older information, or update the value stored for a key.

The authors finally provide experiments including associative recall, overwrite of a repeated key, and language models trained on 15B tokens. Their results show strong recall in several settings, with tradeoffs in memory use, language model quality, and performance beyond the training length.

Critical strengths

I personally find the question of improving recall with a fixed size memory useful. I think table 1 contains promising results, particularly KATA-Sigma2's improvement over the (wider) Gated DeltaNet baseline at a similar reported state size. This comparison is the main empirical reason I find the method worth investigating.

I also appreciate the experimental effort provided by the authors, including language model pretraining and implementation benchmarks rather than only synthetic examples. The authors report weaker perplexity results as well, making clear that better recall on some tasks does not imply better performance in every setting.

Critical weaknesses

My main concerns for this submission regard the contribution beyond existing polynomial attention and how strongly the results support the claimed capacity improvement. I list the weaknesses I found below.

  1. I personally think the comparison with closely related methods should be expanded, in particular I refer to the works in [1], [2], and [3]. In [1] the authors already study quadratic attention features, normalization, and associative recall, making it especially relevant to the construction ψ(u)=uu⊤\psi(u)=uu^\top in section 3.1. Given this connection, I had difficulty identifying whether the main additional contribution is the cone interpretation, the grouped features, or an improvement over existing quadratic attention methods. I would appreciate from the authors a clearer explanation of these differences and a direct comparison of their KATA model with the method in [1]. Since [2] and [3] also study efficient ways to compute polynomial attention, I would like the authors to explain how their computational approach differs from those works, and which benefits are specific to their proposed method.

  2. In my opinion, the capacity claims stated may be broader than the theoretical results. If I understood correctly in theorem 3 and equation 7 the authors show how many key vectors can be arranged so that their features have small pairwise inner products. This does not by itself establish that all the associated values can be retrieved accurately from the same memory. In theorem 4 the authors compare the contribution of the desired value with the combined contributions of the other values under a simplified model. The calculation in equation 8 assumes independent random values, while equations 9 and 10 use the same prescribed squared correlation between the query and every incorrect key. I appreciate that these assumptions are stated and that section 6 distinguishes the different notions of capacity, but however I think the title "Breaking the Capacity Wall" and the introduction should make clearer that these results concern separation of keys and an idealized retrieval criterion (and not a guarantee of accurate recall in trained models).

  3. I think the memory cost should be more central to the interpretation. In section 3.1, the authors expand each pp dimensional vector into p(p+1)/2p(p+1)/2 feature coordinates, and the memory matrix in equation 2 grows with this number. The increase in the idealized retrieval threshold from order pp to order p2p^2 therefore comes with a larger memory. I would distinguish this more clearly from improving recall while keeping the amount of stored memory unchanged. I acknowledge that table 1 includes useful comparisons between models storing similar numbers of entries. My concern is not that all the empirical improvements come from extra memory, but that the theoretical result and these experiments establish different things. A clearer statement of what is proved at a fixed memory budget, and what is demonstrated only experimentally, would help assess the main contribution.

In the end, given the weaknesses listed above I currently lean towards weak rejection. I find the practical results interesting but I am not yet convinced that the additional contribution over related quadratic attention methods is sufficiently established. I also think the capacity claims need a more precise interpretation. I am be happy to reconsider my assessment if the authors clarify the additional contribution, strengthen the comparison with the closest methods and explain more clearly what the theoretical results establish about recall and memory use.

[1] Y. Aksenov et al., "Linear Transformers with Learnable Kernel Functions are Better In-Context Models." ACL 2024.

[2] T. C. Nauen et al., "TaylorShift: Shifting the Complexity of Self-Attention from Squared to Linear (and Back) using Taylor-Softmax." arxiv 2024.

[3] P. Kacham et al., "PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels." ICML 2024.

Questions for authors

I list my main questions below in a synthetic way. Please refer to the weaknesses section above for the more detailed discussion and further questions.

  1. What is the main additional contribution of the proposed KATA model relative to [1], [2], and [3]? In particular, what could be a direct comparison with the method in [1] using similar amounts of memory and the same training conditions? [1,2,3] are listed in the weaknesses section above.
  2. Can the authors explain more directly how theorem 3 and the calculation in theorem 4 relate to retrieving the correct values? Which conclusions about recall follow from the theory and which are supported only by the experiments?
4 comments
AuthorsOpenReview ↗

Rebuttal P1: Response to raised concerns

We appreciate the reviewer's interest in our work and the recognition of the important implications of our results in understanding and improving the recall performance at fixed state size

The review raised points related to missing related work (as did Reviewer 6Aqr), so we first state our contributions to clarify the link with prior work: our KATA framework has two foundational components:

  • Narrowing down the possible kernels that can be used in linear attention by satisfying mild assumptions that match softmax activations.
  • Of the selected kernel output space geometry, we characterize their recall capacity based on interference and noise-to-signal ratio. The empirical contribution is the design and implementation of kernels that map into the PSD cone (or cartesian product of PSD cones as in KATA-M2), with the aim of making the mechanism more efficient to run without compromising on recall. The empirical results show that our theoretical ranking of the 3 cones holds and 2nd order kernel is consistently better at recall than first order linear attention, even at equal state space size, as you have correctly noted. It's always good to have efficient GPU implementations (in this case, faster than Flash-Attention 2), but we believe that the novelty still stands without hardware efficiency: with bounded (RMSNorm of L2Norm) keys, optimizing recall is equivalent to optimally packing codes on the unit hypersphere. We believe this is a major step towards mechanistic interpretation of attention mechanism and the transformer architecture.

Based on this, we never claim that the obtained feature maps are novel, in fact we cite multiple related work that test plain linear, ReLU activated, and quadratic attention. The main differentiation is the principled derivation and recall capacity characterization. Our experiments show that the capacity ranking holds empirically, while the GPU acceleration is an added benefit that allows us to pretrain LLMs without sacrificing GPU hours.

We took some time to analyze the related work you have cited:

  • ReBased [1] explores the feature map ψ(k)=(γk+β)(γk+β)T\psi(k) = (\gamma k + \beta)(\gamma k + \beta)^T, with learned query/key normalization and Triton implementations. This is equivalent exactly the same as KATA-M1 feature map, and in principle the same as Based if we assume that WKW_K and WQW_Q can absorb the parameterization. Our experiments go much further by pretraining LLMs and testing recall at longer horizons
  • TaylorShift [2] evaluates the Taylor kernel 1+q⊤k+(q⊤k)2/21+q^\top k+(q^\top k)^2/2 (truncated Taylor expansion) with normalization and a transition between direct and linear computation according to sequence length (similar principle to SSM kernel vs Flash KATA kernel).
  • PolySketchFormer [3] uses higher-degree polynomial kernels with sketches with approximation guarantees, and self-tensoring construction that ensures nonnegative similarities. As we noted in Appendix A.4:L938, any polynomial approximation beyond degree 2 can not be leveraged to use a fixed state space without significant slow down in inference and training (limited by fast SRAM capacity). PolySketchFormer sketches higher degrees via quadratic approximation, so in the end, it's still quadratic.

To supplement the comparison, we ran their public code on the same settings used for our comparison to GDN and Flash-Attention (TaylorShift implementation is non-causal):

ContextFA2KATA-M1*KATA-M2*ReBasedTaylorShiftPolySketch degree 2PolySketch degree 4, sketch 32
1K0.1400.1470.1490.2643.1030.5901.552
2K0.3260.2690.2960.54311.6514.0073.236
4K1.0140.6820.7841.34945.29510.7836.847
8K3.5912.2982.6814.03542.54623.99614.977
16K13.9469.41011.23413.15986.98352.38028.936
32K55.01636.26643.30346.998743.432108.62557.627
64K229.495149.77589.254185.340OOMCompile OOM120.897
128K938.294395.801176.721730.636OOMCompile OOMCompile OOM

KATA-M2 breaks the head dimension into 2 groups, similar to Polysketch 4-32, allowing more speed-up at medium to long horizons. In all settings, KATA implementations are much more efficient. (OOM are due to materialization of intermediate states, which limit long context compilation).

AuthorsOpenReview ↗

Rebuttal P1: Addressing concerns & Answers

In the capacity characterization, we assume values are independent to force the mechanism to assign different key per value. If the values overlap, the packing can assign them the same key and fake more capacity.

Our parameter-efficiency claim is that a learned projection of width dd can generate D=d(d+1)/2D=d(d+1)/2 quadratic coordinates. In contrast, first order linear attention has to map to the DD coordinates directly.

To understand the implication, let's take Qwen3.5-4B. Its hidden states use dimention 2560, and the linear GatedDeltaNet uses 16 query/key heads of dimension 128, and 32 value heads of dimension 128. The PSD kernel maps each 128-dimensional query/key vector into D=128×129/2=8,256D=128\times129/2=8,256, with no additional learned projection weights. For comparison, directly widening the first-order GDN query/key heads to 8,256 coordinates would increase their combined projection weights per layer from: 2×2560×16×128=10,485,7602\times2560\times16\times128=10,485,760 to 2×2560×16×8256=676,331,520.2\times2560\times16\times8256=676,331,520. This means that the 24 linear layers will require 16.4B parameters alone instead of the current 250M parameters.

In contrast, KATA quadratic fixed state expands the value state from 2MiB to 129MiB, for an equivalent 1.5B more parameters instead of 16.4B, which means it reaches the same capacity at 10x less memory compared to parameterization.

Even at comparable feature-value state size, KATA PSD features outperform first order features (GLA, GDN) on MQAR as shown in Table 1 in the paper (relevant entries below):

MethodParametersFeature–value state entriesMQAR at 2KMQAR at 4K
GLA, dh=256d_h=2565,798,14465,5360.9020.491
DeltaNet, dh=256d_h=2565,520,12865,5360.8650.342
Gated DeltaNet, dh=256d_h=2566,047,75065,5360.9090.419
KATA-Σ2\Sigma2, dh=64d_h=641,134,01667,5841.0000.958

The review recognizes the transparency in presenting our empirical results. KATA addresses the question of maximizing recall at given state space size, but we found out that better recall does not always translate to better LLMs performance. This is a strong evidence that the attention mechanism does more than just in-context retrieval, but also overwrite, deletion, information mixing, where the delta-rule turned out to be helpful. This might explain why hybrid architectures combining delta-rule in GDN and full attention (Qwen3.5) can outperform vanilla transformers.

Q1. What is the main additional contribution of the proposed KATA model relative to [1], [2], and [3]? In particular, what could be a direct comparison with the method in [1] using similar amounts of memory and the same training conditions?

A1: The main contribution is the capacity-characterization framework, supported by the grouped constructions and experiments described above. Although we show that our implementation is more efficient than prior work, it is provided to be able to train LLMs and test the cone capacity hierarchy. The core result is that capacity depends on the state-space size, and that low-rank (rays in PSD) feature maps are can exploit the expand the expanded state space without the need to increase the head dimension.

Q2. Can the authors explain more directly how theorem 3 and the calculation in theorem 4 relate to retrieving the correct values? Which conclusions about recall follow from the theory and which are supported only by the experiments?

A2: Theorem 3 bounds geometric address capacity while Theorem 4 analyzes an idealized retrieval criterion. For unit-norm features and an exact matched-key query the matched unnormalized score is a⋆=1a_\star=1. With independent isotropic values, the desired expected power is:

pSNR=∣a⋆∣2∑j≠⋆∣aj∣2.\mathrm{pSNR}=\frac{|a_\star|^2}{\sum_{j\ne\star}|a_j|^2}.

If every distractor's overlap is at most ϵ\epsilon:

pSNR≥1(T−1)ϵ2.\mathrm{pSNR}\geq\frac{1}{(T-1)\epsilon^2}.

The condition pSNR>1\mathrm{pSNR}>1 means that that the signal exceeds the interference.

So in summary:

  • We prove: the geometric packing result and the stated signal-to-noise characterization.
  • We demonstrate empirically: PSD constructions improve learned MQAR and pretrained model recall, including at comparable state sizes, with the limitations shown by perplexity and length extrapolation.

We kindly remind the reviewer to respond to our rebuttal and let us know whether we have adequately addressed their questions and concerns, as the discussion period is drawing to a close.

I thank the authors for their detailed responses and the further comparisons. In particular, thanks to their clarification I more clearly understand the main contributions of their work relative to previous polynomial attention methods, and also the distinction between the theoretical capacity results and the actual recall performance. I find the additional computational comparisons and the discussion of parameter and memory efficiency also helpful. I still have some reservations about the novelty relative to existing methods and the broader interpretation of the theoretical capacity results. Nevertheless, I find the empirical results promising, and I think the rebuttal has addressed most of my concerns.

Provided that the authors incorporate the clarifications and additional comparisons into the revised manuscript I am happy to increase my score to weak acceptance.

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

This paper explains the key interference of linear attention as the packing of the inner sphere of the cone, and uses the non negative kernel features of the self dual homogeneous cone organization to focus on the study of rank one PSD mapping. Authors provide the packing lower bound and idealized pSNR analysis under fixed interference tolerance, designs grouped PSD features and their combination with delta rule and forget gate, and provides Triton implementation. The experiment includes MQAR, repeated key overwriting, 15B token pre training of 340M model, as well as recall and hardware evaluation.

Critical strengths
  1. The PSD packing construction, Haar average interference analysis, and normalized readout of the corresponding convex combination identity are basically clear. The author simultaneously reports on secondary implementation, linear state implementation, and forward-backward delay, and acknowledges the decrease in confusion, failure of position extrapolation, and trade-offs between different variants, avoiding only displaying advantageous results.

  2. In Table 2, the 340M model achieved KATA-M2 of 0.616, Gated DeltaNet of 0.004, and softmax of 0.930 on a 2K UUID needle. PSD features do demonstrate the potential to preserve high entropy content. The rewriting experiment also demonstrated the complementary effect of feature capacity and the delta update rule.

Critical weaknesses
  1. Lack of the retrieval task performance. Pls provide at least 1-2 groups of this experiment analysis.

  2. Lack of closest comparison with existing methods, and the novelty of the methods is still unclear. The core kernel function of the complete rank one KATA-M1 is (q^\top k)^2. Power Attention [1] has been conducted on q^\top k)^p, symmetric tensor feature unfolding, parameter independent state capacity adjustment, and block GPU implementation, symmetric tensor feature unfolding, parameter independent state capacity adjustment, and block GPU implementation.

Reference: [1] Scaling Context Requires Rethinking Attention

Questions for authors
  1. Does extrapolation slicing participate in learning rate or checkpoint selection?

  2. Will the results remain after switching to the independent selection protocol?

  3. What is the independent benefit of KATA compared to quadratic Power Attention and Taylor features under the same parameter/state budget?

  4. Which actual variants meet Assumption 2? How should the theory of grouping characteristics be restated?

3 comments
AuthorsOpenReview ↗

Rebuttal P1: Response to raised weaknesses

We thank the reviewer for taking the time to read and analyze our work. As the current review stands, you have raised concerns about missing retrieval evaluations, missing comparisons with related work, unclear novelty of the work, with additional questions related to the checkpoint selection, and the benefit of KATA compared to existing polynomial attention mechanisms.

The novelty of our Kernelized Linear Attention (KATA) framework consists of three axes (in order of importance):

  • Axis 1 (novel): We narrow down the possible linear attention feature maps following a principled approach based on symmetric cones characterization.
  • Axis 2 (novel): Introduce a new memorization capacity method based on the mutual interference and signal-to-noise ratio analysis, with 2 proposed finite dimensional constructions.
  • Axis 3 (overlaps with prior work): design and implementation of efficient feature maps that adopt the selected geometries. This is the cherry on top: there is little use of an elegant theory if it can't be tested, so we implemented KATA-M1 and its other variants (M2 and$\Sigma2$) with reduced state-space. The goal is to have an implementation that is at least as fast as Flash-Attention kernels, which on its own is a major effort. We emphasize that we never claim that the kernels selected by KATA are novel and our contributions do not depend on such claim.

The review mentions that there is "lack of retrieval task performance". We would like to clarify that the majority of the experiments address "retrieval" (which we call "recall"), including Zoology's MQAR [3] benchmark, RULER's needle-in-a-haystack and the Based in-context suite. We also report two complementary groups of retrieval evaluations on pretrained 340M-parameter language models in Table 2 (Sections 4.4 and 4.5):

  • On RULER's benchmark, KATA-M2 achieves 0.616 UUID recall at 2K, compared with 0.004 for Gated DeltaNet and 0.930 for softmax attention. Interestingly, KATA-M2 also outperforms KATA-M1 (0.458), despite using half the recurrent state size (135,168 versus 266,240 entries). Our analysis in Section 4.4 distinguishes geometric capacity from realized retrieval performance, which also depends on how the model exploits the available geometry.
  • We evaluate the pretrained LLMs on SWDE, FDA, SQuAD, TriviaQA, and NQ, which complement direct associative recall with tasks requiring contextual interpretation. KATA-M1 achieves the strongest fixed-state result on SWDE (0.375), whereas KATA-M2 and DeltaKATA-M1 perform better on FDA and SQuAD. As discussed in Section 4.5 and Appendix B.2, these results also reveal the limitations of substring-based evaluation: it can reward verbose generation instead of better recall.
  • These evaluations complement our controlled MQAR experiments in Section 4.1, Table 1, and Appendix B, Table 5, where KATA-M1 retains 0.985 accuracy at 16× the training sequence length, while DeltaKATA-M1 reaches 0.999.

Comparison With Power Attention [1]

You have also pointed out to Power attention [1] as relevant work. To judge the paper on its own merits, we have analyzed it and respond as follows:

  • Power Attention starts from the Based [2] quadratic polynomial of the exponential (already referred to in the related work), and then asks proposes the generic "<q,k>^p". In our work, we show that only the even values of p=2r are admissible, the odd degrees p=2r+1 do not map to a symmetric cone. Moreover, as we note in Appendix A.4:L938, anything beyond r=1 (<q,k>^2) is impractical to implement with current hardware (limited SRAM capacity): the materialization of the state-space is memory-bound and requires larger state-space ((d+2r−12r)\binom{d+2r-1}{2r}), offsetting the ultimate goal of linear attention: computational and storage efficiency.
  • Power Attention focuses entirely on the efficiency quadratic kernel (implementation and management of the state-space), but after running their code we found that our triton kernels are 2x to 3x faster at any context length up to 128k tokens, and we use 1.8x less memory (as we don't materialize intermediate states). So even on the 3rd axis of our contributions (implementation), we're significantly ahead (batch size 8, 16 attention heads, 64 head dim, H100 GPU). This shows based on the 3rd axis of our contribution (GPU implementation) we substantially outperform their implementation:
ContextFlash-Attention2 (ms)KATA-M1 (ms)PowerAttention p=2 (ms)Speed-up
1K0.1470.1330.2802.10x
2K0.3340.2530.6282.48x
4K0.9980.6661.9112.87x
8K3.6372.2686.9833.08x
16K13.758.3926.873.20x
32K53.2733.55106.293.17x
64K218.50142.08424.722.99x
128K924.72592.061707.242.88x

References:

[1] Scaling Context Requires Rethinking Attention

[2] Simple linear attention language models balance the recall-throughput tradeoff

[3] Zoology: Measuring and Improving Recall in Efficient Language Models

AuthorsOpenReview ↗

Rebuttal P1: Response to questions

Here we respond to the questions raised by the reviewer:

Q1. Does extrapolation slicing participate in learning rate or checkpoint selection?

A1: Yes, the "in-distribution" extrapolation slices participate in selection in our experiments. Our MQAR evaluation follows the established Zoology [3] convention of sweeping learning rates separately for each architecture and reporting the best achieved accuracy. Zoology explicitly reports maximum test accuracy over its learning-rate sweep, and subsequent work: Mamba [4], Mamba-2[5], GLA[6], Gated DeltaNet[7], follows its experimental setting. We apply the same search budget and selection procedure to KATA and all evaluated baselines. However, the KATA results do not depend on choosing different learning rates or checkpoints for different lengths: for every KATA configuration, one learning rate and one evaluated checkpoint reproduce the entire reported curve to its displayed precision.

Q2. Will the results remain after switching to the independent selection protocol?

A2: Yes. Following our answer A1, our KATA results do not depend on slice-specific selection. Meanwhile, each baseline slice-wise maximum is at least as high as the best (LR, checkpoint) per horizon. As such, we were more lenient in scoring the MQAR baselines which get the benefit of per-slice selection. Despite such advantage, KATA's strong performance holds.

Q3. What is the independent benefit of KATA compared to quadratic Power Attention and Taylor features under the same parameter/state budget?

A3: KATA is a principled framework for identifying feature geometries that support nonnegative linear attention and how their memorization capacity depends on tolerated interference: we combine softmax-inspired non-negativity and rotational symmetry with explicit self-duality and homogeneity assumptions to constrain the admissible geometries. Performance-wise, quadratic Power Attention is exactly the same as KATA-M1. Taylor features (2nd order) are the same as Lorentz-cone ×\times PSD cone, and following our capacity analysis, should have capacity O(2d+d(d+1))O(2d + d(d+1)) compared to O(d(d+1))O(d(d+1)) of quadratic Power attention, but at the cost of slightly larger state-space.

Q4. Which actual variants meet Assumption 2? How should the theory of grouping characteristics be restated?

A4: Assumption 2 can only be satisfied by the Lorentz Cone and PSD cone. So theorem 1 is to be understood as a necessary (but not sufficient) condition. The reason for that is simply because we can rotate the vector (1,1) (in R^2_+) to have negative coordinates. For Lorentz and SPD, we can define TUT_U that preserves the isometry on the blocks in the inner product <q,k>. KATA-M2 only satisfies a per-block isometry, it should be seen a compromise towards reducing state-space size.

On the informativeness evaluation

The reviewer rated the informativeness of our work as minimal (score 1); we have therefore clarify the insights contributed by our capacity-characterization framework and what our experiments reveal about the role (and limits) of capacity in attention. To the extent of our knowledge, we are the first to narrow the set of possible linear attention variants under reasonable assumptions that match softmax attention mechanism, and we derive exact capacity bounds under a target interference level. We also test our capacity-characterization claims via synthetic experiments (MQAR and overwrite), as well as implementing different variants that take into consideratoin hardware constraints, which we we used for a Small Language Model (SLM) pre-training.

Our results confirmed the recall capacity but also showed that (to our surprise) that better capacity does not necessarily imply better fluency. This contrasts with the memorization-recall perspective our work builds on: attention mechanism is not only about retrieval, but also overwriting and deletion; the last two are challenging even to large-capacity softmax attention while the delta-rule seems to handle such property well.

References:

[3] : Zoology: Measuring and Improving Recall in Efficient Language Models

[4] : Mamba: Linear-Time Sequence Modeling with Selective State Spaces

[5] : Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality

[6] : Gated Linear Attention Transformers with Hardware-Efficient Training

[7] : Gated Delta Networks: Improving Mamba2 with Delta Rule

We kindly remind the reviewer to respond to our rebuttal and let us know whether we have adequately addressed their questions and concerns, as the discussion period is drawing to a close.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revision update

Following our discussion with the reviewers, we have added a clear statement of the contributions at the end of the introduction (highlighted in blue). We also updated the abstract to explicitly use PSD features in the MQAR claim ("PSD feature maps retaining 0.985 MQAR at a 16× out-of-distribution length") to avoid attributing this performance specifically to KATA, since PSD kernels have been used in prior work as noted in the related work section and during the rebuttals. Regarding the baselines provided during the rebuttals, we will add those in the appendix if needed, but we decided to keep the Flash-Attention2 and GDN references in the speed-up benchmarks as they are much stronger than the baselines mentioned by the reviewers.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.