Local Linear Attention: An Optimal Interpolation of Linear and Softmax Attention For Test-Time Regression

Yifei Zuo, Yutong Yin, Zhichen Zeng, Ang Li, Banghua Zhu, Zhaoran Wang

TL;DR

Local Linear Attention (LLA) is a novel attention mechanism derived from local linear regression that optimally interpolates between Softmax and Linear Attention. It overcomes the "boundary bias" of Softmax and the "approximation error" of Linear models, delivering state-of-the-art performance on associative recall and non-stationary regression tasks while remaining hardware-efficient via a custom "FlashLLA" kernel.

Overview of the LLA framework: (Left) Regression performance on non-stationary data where LLA tracks the ground truth more accurately than Softmax (Attn) or Mesa; (Middle) Theoretical links between bias-variance trade-off and associative memory; (Right) Conceptual comparison of attention families.

Introduction: The Performance-Efficiency Gap

Modern deep learning architectures rely heavily on the Transformer's Softmax Attention. While expressive, its $O(n^2)$ scaling with sequence length $n$ poses a significant bottleneck for long-context applications. To address this, Linear Attention (LA) and State Space Models (SSMs) like Mamba have emerged, offering $O(n)$ efficiency.

However, a persistent "performance gap" remains. Linear models often struggle with complex, non-linear data due to model misspecification—attempting to fit a global linear rule to non-stationary data. Conversely, Softmax Attention acts as a "local constant" estimator; while flexible, it suffers from boundary bias, leading to significant errors when queries fall near the edges of data clusters. This paper proposes Local Linear Attention (LLA) to systematically bridge this gap by viewing attention through the lens of nonparametric regression.

Methods: Attention as Local Linear Regression

The core innovation of LLA is the formulation of the attention mechanism as a local linear regression solver. Instead of simple averaging (Softmax) or global fitting (Linear Attention), LLA fits a unique local linear model for every query.

Conceptual comparison of attention mechanisms: Linear Attention fits a global line, Softmax Attention performs local constant averaging, and Local Linear Attention fits a local linear trend for each query.

Mathematical Foundation

Derived from nonparametric statistics, LLA uses a kernel to weight historical key-value pairs based on their proximity to the current query. It then solves a ridge regression problem to find the optimal local linear fit. This approach allows the model to capture local trends more accurately than a constant estimator while avoiding the rigidity of a global linear model.

FlashLLA and Computational Efficiency

To ensure practical utility, the authors developed FlashLLA, a hardware-efficient, blockwise algorithm implemented as a Triton kernel. Key technical contributions include:

  • Memory Primitives: Algebraic optimizations avoid materializing $O(n^2d)$ matrices, maintaining an $O(nd)$ memory footprint.
  • Matrix-Free Inversion: LLA avoids explicit $d \times d$ matrix inversions by using the Conjugate Gradient (CG) method, solving the local linear systems iteratively and efficiently.

Experimental Evaluation

The authors evaluated LLA across several benchmarks designed to test memory and regression capabilities:

  • Non-Stationary Regression: In tasks like Piecewise-Linear Regression, LLA significantly outperformed Softmax, Linear Attention, and MesaNet by effectively handling abrupt shifts in data relationships.
  • Associative Recall: On the Multi-Query Associative Recall (MQAR) benchmark, LLA achieved state-of-the-art accuracy, demonstrating a cleaner and more robust learning curve than competitors like Gated DeltaNet.
  • In-Context Learning: LLA showed superior performance in tracking permutations and performing in-context regression, particularly as the data dimensionality ($d$) increased.

Key Insights

  • Optimal Interpolation: LLA serves as the "Goldilocks" of attention mechanisms. It avoids being "too local" like Softmax (which suffers from boundary bias) or "too global" like Linear Attention (which suffers from approximation error).
  • Bias-Variance Trade-off: By fitting local lines, LLA achieves a superior bias-variance trade-off, making it particularly effective for non-stationary data.
  • Attention as an Optimizer: This work reinforces the perspective that attention layers are implicit optimization algorithms—"test-time regressors"—that learn to solve specific sub-problems during inference.

Conclusion

While LLA offers significant theoretical and empirical advantages, challenges remain in scaling to multi-billion parameter models and optimizing I/O intensity. However, its ability to bridge the gap between efficiency and expressivity makes it a promising direction for the next generation of sequence models.

Summary updated

BibTeX
@inproceedings{zuo2026local,
  author = {Yifei Zuo and Yutong Yin and Zhichen Zeng and Ang Li and Banghua Zhu and Zhaoran Wang},
  title = {{Local Linear Attention: An Optimal Interpolation of Linear and Softmax Attention For Test-Time Regression}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=WGpzi489XY},
}
Figure