Kaczmarz Linear Attention

• URL: http://arxiv.org/abs/2605.08587v1
• Date: Sat, 09 May 2026 01:07:01 GMT
• Title: Kaczmarz Linear Attention
• Abstract summary: Linear recurrent models compress the context into a fixed-size state, making the rule that forgets, writes, and edits information a central design problem.<n>Gated DeltaNet (GDN) combines gated state decay with delta-rule residual writes, using a learnable coefficient to balance forgetting and update magnitude.<n>We propose Kaczmarz Linear (KLA), a one-scalar modification of GDN that preserves the state shape, gates, linear recurrence, and chunkwise parallel algorithm.
• Score: 11.650692583508663
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Long-context language modeling remains central to modern sequence modeling, but the quadratic cost of Transformer attention makes scaling computationally prohibitive. Linear recurrent models address this bottleneck by compressing the context into a fixed-size state, making the rule that forgets, writes, and edits information a central design problem. To address state maintenance, Gated DeltaNet (GDN) combines gated state decay with delta-rule residual writes, using a learnable coefficient to balance forgetting and update magnitude. However, this coefficient is learned empirically rather than derived from the underlying objective, which can lead to suboptimal update magnitudes. We revisit the online-regression objective underlying GDN and, inspired by the Kaczmarz projection method, derive the key-norm-normalized dynamic step size $β_t = η_t / (\|k_t\|_2^2 + ε)$ for residual updates. We propose Kaczmarz Linear Attention (KLA), a one-scalar modification of GDN that preserves the state shape, gates, linear recurrence, and chunkwise parallel algorithm. At the 0.4B scale with a 1B-token budget, KLA achieves the lowest validation perplexity among evaluated linear-time baselines, 8.09 versus 8.50 for GDN, and remains stable up to 65K tokens. On controlled tasks, KLA reaches 100% on single-needle-in-a-haystack retrieval, improves 8x multi-query associative recall by 7.03 points over GDN, and delivers 2.1x higher decode throughput at 32K context. These results suggest that the key-norm-normalized Kaczmarz coefficient is a first-order design axis for delta-rule sequence models: it improves accuracy, extrapolation, and decoding efficiency without changing the recurrent state or hardware kernel.

Related papers

• Online Bayesian Node Classification on Inductive Graphs under Distribution Shift [4.1234601543641904]
  We introduce a variational Bayesian last-layer (VBLL) objective that jointly trains the encoder and an approximate last-layer posterior.<n>Online GVBLL is the only method to achieve the best accuracy and negative log-likelihood on every dataset.<n>It improves accuracy by up to 17 percentage points on Cora and 14 percentage points on ogbn-arxiv over the strongest non-GVBLL baseline.
  arXiv  Detail & Related papers  (2026-09-12T02:23:30Z)
• Kalman Delta Networks: Uncertainty-aware Associative Memory [27.530297884143604]
  We reformulate recurrent associative memory as a linear--Gaussian state-space model.<n>Within KDNs, the transition propagates both the memory state and its uncertainty.<n>We show that KDN variants consistently improve perplexity and mean downstream accuracy over state-of-the-art linear-attention models.
  arXiv  Detail & Related papers  (2026-09-07T17:53:29Z)
• REVES: REvision and VErification--Augmented Training for Test-Time Scaling [53.197756110943395]
  We propose a two-stage iterative framework that alternates between online data/prompt augmentation and policy optimization.<n>We observe gains of +6.5 points over the RL baseline and +4.0 points over standard multi-turn training.
  arXiv  Detail & Related papers  (2026-06-17T10:37:23Z)
• Learning to Solve Generative ODEs Beyond the Linear Span [50.13853710831612]
  We propose SpanLift, a lightweight neural solver that augments scalar-coefficient updates with a spatial residual operator.<n>Across pixel-space diffusion, latent flow matching, and precipitation nowcasting, SpanLift achieves state-of-the-art few-step sampling.
  arXiv  Detail & Related papers  (2026-06-07T15:22:13Z)
• OSDN: Improving Delta Rule with Provable Online Preconditioning in Linear Attention [12.93065958346192]
  Online Scaled DeltaNet improves JRT-style in-context recall by 32% over DeltaNet.<n> scaling to 1.3B parameters, it achieves a 39% reduction in the recall residual ratio.
  arXiv  Detail & Related papers  (2026-05-13T12:59:26Z)
• MDN: Parallelizing Stepwise Momentum for Delta Linear Attention [27.145174798663035]
  Linear Attention (LA) offers a promising paradigm for scaling large language models to long sequences.<n>Recent LA models such as Mamba2 and GDN interpret linear recurrences as closed-form online gradient descent.<n>Momentum DeltaNet (MDN) leverages Triton kernels to achieve comparable training throughput with competitive linear models.
  arXiv  Detail & Related papers  (2026-05-07T08:12:09Z)
• Preconditioned DeltaNet: Curvature-aware Sequence Modeling for Linear Recurrences [51.38664601405696]
  We introduce preconditioned variants of DeltaNet, GDN, and KDA alongside efficient chunkwise parallel algorithms for computing them.<n>Our preconditioned delta-rule recurrences yield consistent performance improvements across synthetic recall benchmarks and language modeling at the 340M and 1B scale.
  arXiv  Detail & Related papers  (2026-04-22T21:38:25Z)
• BASIS: Balanced Activation Sketching with Invariant Scalars for "Ghost Backpropagation" [0.0]
  Activation memory required for exact backpropagation scales linearly with network depth, context length, and feature dimensionality.<n>In this paper, we introduce an efficient backpropagation algorithm that fully decouples activation memory from the batch and sequence dimensions.
  arXiv  Detail & Related papers  (2026-03-05T20:38:25Z)
• Gated KalmaNet: A Fading Memory Layer Through Test-Time Ridge Regression [53.48692193399171]
  Gated KalmaNet (GKA) is a layer that reduces the gap by accounting for the full past when predicting the next token.<n>We solve an online ridge regression problem at test time, with constant memory and linear compute cost in the sequence length.<n>On long-context, GKA excels at real-world RAG and LongQA tasks up to 128k tokens, achieving more than $10$% relative improvement over other fading memory baselines.
  arXiv  Detail & Related papers  (2025-11-26T03:26:37Z)
• Continuous Autoregressive Language Models [56.49239051750678]
  We introduce Continuous Autoregressive Language Models (CALM)<n>CALM uses a high-fidelity autoencoder to compress a chunk of K tokens into a single continuous vector.<n>We develop a comprehensive likelihood-free framework that enables robust training, evaluation, and controllable sampling.
  arXiv  Detail & Related papers  (2025-10-31T17:58:11Z)
• Comba: Improving Bilinear RNNs with Closed-loop Control [57.800320390698516]
  We introduce the concept of Bilinear RNNs with a comprehensive analysis on the advantages and limitations of these models.<n>We propose a novel Bilinear RNN variant named Comba, which adopts a scalar-plus-low-rank state transition, with both state feedback and output feedback corrections.<n>We also implement a hardware-efficient chunk-wise parallel kernel in Triton and train models with 340M/1.3B parameters on large-scale corpus.
  arXiv  Detail & Related papers  (2025-06-03T05:44:50Z)
• Hyperspherical Normalization for Scalable Deep Reinforcement Learning [57.016639036237315]
  SimbaV2 is a novel reinforcement learning architecture designed to stabilize optimization.<n>It scales up effectively with larger models and greater compute, achieving state-of-the-art performance on 57 continuous control tasks.
  arXiv  Detail & Related papers  (2025-02-21T08:17:24Z)
• Robust Implicit Networks via Non-Euclidean Contractions [63.91638306025768]
  Implicit neural networks show improved accuracy and significant reduction in memory consumption. They can suffer from ill-posedness and convergence instability. This paper provides a new framework to design well-posed and robust implicit neural networks.
  arXiv  Detail & Related papers  (2021-06-06T18:05:02Z)

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.