LoLA: Low-Rank Linear Attention with Sparse Caching
Luke McDermott [email protected], Robert W. Heath Jr. [email protected], Rahul Parhi [email protected] · 2025
Read LoLA: Low-Rank Linear Attention with Sparse Caching by Luke McDermott [email protected], Robert W. Heath Jr. [email protected], Rahul Parhi [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23666.txt.
Introduction
Luke McDermott, Robert Heath, and Rahul Parhi present LoLA in a 2025 paper on cheaper long memory for AI models. A transformer's cost per word grows with context length, which blocks lifelong learning from endless text. A leaner method holds fixed memory but recalls past facts poorly.
LoLA boosts that lean method with no new training by splitting past pairs three ways. Fresh pairs sit in a small local cache, hard pairs in a sparse global cache, and the rest in the core state. A self recall error score steers which pairs go where. On a key hunt task, accuracy leapt from 0.6% to 97.4%. The cache used is 4.6 times smaller than a big rival model's at the same length.
Catalog record
| CREATOR | Luke McDermott [email protected], Robert W. Heath Jr. [email protected], Rahul Parhi [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-23666
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
LoLA: Low-Rank Linear Attention with Sparse Caching Luke McDermott [email protected], Robert W. Heath Jr. [email protected], Rahul Parhi [email protected] Abstract The per-token cost of transformer inference scales with context length, preventing its application to lifelong in-context learning. Linear attention is an efficient alternative that maintains a constant memory footprint, even on infinite context lengths. While this is a potential candidate for lifelong learning, it falls short in memory capacity. In this paper, we propose LoLA, a training-free augmentation to linear attention that boosts associative recall. LoLA distributes past key-value pairs from context into three memory systems: (i) recent pairs in a local sliding window cache; (ii) difficult-to-memorize pairs in a sparse, global cache; and (iii) generic pairs in the recurrent hidden state of linear attention. We show through ablations that our self-recall error metric is crucial to efficiently manage long-term associative memories. On pass-key retrieval tasks, LoLA improves the base model’s performance from 0.6 % 0.6\% to 97.4 % 97.4\% accuracy. This is achieved with a 4.6 × \times smaller cache than Llama-3.1 8B on 4K context length. LoLA also outperforms other 1B and 8B parameter subquadratic models on zero-shot commonsense reasoning tasks. Reviewed on OpenReview: https://openreview.net/forum?id=3KhDA252y3 1 Introduction Transformer-based large language models (LLMs) rely on storing all past tokens in an ever-growing key-value (KV) cache ( Vaswani et al., 2017 ) . This allows future query tokens to access past memories with associative recall, which enables in-context learning ( Olsson et al., 2022 ) . Since no previous information is discarded, the KV cache continues to grow with context length. This eventually leads to a memory bottleneck on long context tasks, such as lifelong in-context learning. As a result, transformers cannot condition next token predictions on arbitrarily long sequences. Alternative architectures to transformers have been proposed—such as Mamba ( Gu and Dao, 2024 ) , DeltaNet ( Schlag et al., 2021 ) , linear attention ( Katharopoulos et al., 2020 ) , and others ( Yang et al., 2024a ; Behrouz et al., 2024 ; Sun et al., 2024 ) —to reduce the compute complexity from quadratic to linear. Additionally, these approaches reduce the memory cost from linear to constant. In particular, linear attention removes the exponential dot product in softmax ( Katharopoulos et al., 2020 ) . This effectively collapses the unbounded KV-cache into a fixed-size matrix, which corresponds to a recurrently formed hidden state (i.e., a linear RNN). This constructs a linear associative memory map from keys to values. Past memories can be recalled through a vector-matrix product of an incoming query vector and the hidden state matrix. Linear attention enables constant-cost prediction per token when conditioned on arbitrarily long contexts. While efficient and flexible, linear attention architectures lag behind transformers in terms of memory capacity. This is largely noticeable on tasks leveraging in-context learning ( Paperno et al., 2016 ; Hsieh et al., 2024 ) . The removal of the exponential dot product allows for non-orthogonal keys to interfere with the hidden state’s learned key-to-value map. This interference—denoted as a memory collision —impairs associative recall. Despite linear attention’s efficiency and simplicity, this limitation in memory capacity prevents more widespread adoption. Previous work used nonlinear query and key activations to improve the exponential dot product approximation ( Choromanski et al., 2020 ; Zhang et al., 2024 ) . However, these attempts are essentially performing a low-rank approximation of the infinite-rank exponential dot product kernel. Additional use of sparse attention ( Chen et al., 2021 ) can improve linear attention’s recall; however, hybrid approaches often only focus on local information with sliding window attention ( Arora et al., 2024 ; Zhang et al., 2025a ; Lan et al., 2025 ; Van Nguyen et al., 2025 ) . These approaches can struggle to recall critical, long-term facts that fall outside the window. This raises our fundamental research question: How can long term associative memory for subquadratic language models be improved? Contributions We present LoLA: Low-rank Linear Attention with sparse caching. LoLA is a novel inference augmentation that boosts the performance of hybrid linear attention layers. LoLA distributes historical tokens into three forms of memory: (i) recent KV pairs are stored in a sliding window cache, (ii) difficult-to-memorize pairs in a sparse global cache, and (iii) all other pairs are placed in a recurrent hidden-state matrix via linear attention. LoLA performs a self-recall check to see which KV pairs disagree with the current hidden state’s linear associative map. LoLA sparsely caches the interfering memories in full rank. The selection mechanism effectively mitigates memory collisions with a small, constant-sized cache. This inference strategy can be applied on top of previously trained linear attention + sliding window models (e.g., LoLCATs) to significantly improve associative recall. As a result, LoLA extracts stronger language modeling capabilities from the same base model weights. Utilizes Self-Recall Error. We introduce an importance metric for key-value pairs to reduce memory collisions in the hidden state of linear attention. This is computed by determining if a key can recall its own value with linear attention. In our ablations, we show that this performance increase cannot be obtained from using a larger sliding window or other sparse attention metrics. Enables Associative Recall. As a lightweight inference strategy, LoLA enables pass-key retrieval on up to 8K context lengths in needle-in-a-haystack tasks from the RULER benchmark ( Hsieh et al., 2024 ) . With a 4.6x smaller cache than Llama-3.1 8B ( Grattafiori et al., 2024 ) , our approach boosts accuracy from LoLCATs’ 0.6\% to 97.4\% at 4K context lengths with the same model weights. Improves Language Modeling. LoLA shows superior performance on zero-shot commonsense reasoning tasks among 1B and 8B parameter subquadratic architectures. This demonstrates that effective memory management can boost language modeling performance. 2 Preliminaries In this section, we review softmax attention through the lens of associative memory. Then, we show how linear attention naturally forms a recurrent hidden state. We address practical implementations for training linear architectures and highlight unresolved drawbacks of previous approaches. 2.1 Softmax Attention as a Nonparametric, Online Learner Transformers process a sequence of input tokens \{\bm{x}_{t}\}_{t=1}^{n} , for \bm{x}_{t}\in\mathbb{R}^{d} ( Vaswani et al., 2017 ) . For each attention head, the input tokens are transformed into three distinct representations—queries, keys, and values—via trainable weight matrices \mathbf{W}_{q},\mathbf{W}_{k}\in\mathbb{R}^{d\times d_{k}} and \mathbf{W}_{v}\in\mathbb{R}^{d\times d_{v}} . For a given token \bm{x}_{t} , define \underbrace{\bm{q}_{t}=\mathbf{W}_{q}\bm{x}_{t}}_{\text{query}},\quad\underbrace{\bm{k}_{t}=\mathbf{W}_{k}\bm{x}_{t}}_{\text{key}},\quad\underbrace{\bm{v}_{t}=\mathbf{W}_{v}\bm{x}_{t}}_{\text{value}}. (1) Causal attention uses the current query to recall past information from key-value pairs. The similarity between the query \bm{q}_{t} and key \bm{k}_{i} is denoted as \alpha_{ti}\in(0,1) . This similarity score determines how much value \bm{v}_{i} is used for the current output token at time t . The output token \bm{y}_{t} is defined by \bm{y}_{t}=\sum_{i=1}^{t}\alpha_{ti}\,\bm{v}_{i}\in\mathbb{R}^{d_{v}},\quad\text{with}\quad\alpha_{ti}=\frac{\exp\left(\bm{q}_{t}^{\top}\bm{k}_{i}/\sqrt{d_{k}}\right)}{\sum_{j=1}^{t}\exp\left(\bm{q}_{t}^{\top}\bm{k}_{j}/\sqrt{d_{k}}\right)}. (2) We view softmax attention as a nonparametric function m_{t}:\mathbb{R}^{d_{k}}\to\mathbb{R}^{d_{v}} that fits to the past context at inference time. This online function m_{t} learns to map keys to their associated value in context with m_{t}(\bm{k}_{i})\approx\bm{v}_{i} for (\bm{k}_{i},\bm{v}_{i})\in\{(\bm{k}_{i},\bm{v}_{i})\}_{i=1}^{t} . Then, m_{t} applies the learned transformation to the query, \bm{y}_{t}=m_{t}(\bm{q}_{t}) . The set of past key-value pairs forms an online "training set" of input-output labels. The query acts as an unsupervised "test set". Softmax attention caches all past key-value pairs to perform this non-parametric, or “look-up table”, operation. Since the function complexity scales