Linear attention replaces the transformer's all-pairs comparison between tokens with a running summary: every past token is added into a fixed-size matrix, and each new query reads from that matrix. This makes each generation step cost the same no matter how long the context is. The price is that the summary blurs individual tokens together, so the model struggles to recall a specific fact it saw thousands of tokens ago. The standard fix keeps a small cache of exact tokens next to the summary. In practice that cache is simply the most recent 64 to 128 tokens. We propose to let the model choose which past tokens stay exact under a hard slot budget. Tokens that are dropped are not discarded: their contribution is written into the linear summary instead. Every token's weight is therefore split between "stored exactly" and "compressed," and the two parts always sum to one.
The selection step comes from combinatorial optimization. During training, each token gets a fractional retention value between 0 and 1, with the values constrained to sum to the budget. This is a relaxed version of the discrete keep-or-drop choice, and gradients flow through it. At inference, the fractional values are converted into discrete decisions by swap rounding. Swap rounding pairs two fractional tokens and shifts retention mass from one to the other until one of them reaches 0 or 1. Each step keeps the total fixed, so the cache never overflows, and each token is kept with probability equal to its trained fractional value. The core claim has two parts. First, a learned, non-contiguous retention set closes more of the recall gap than a recency window of the same memory size. Second, doing it this way (fractional training plus marginal-preserving rounding that returns evicted mass to the summary) beats simply ranking tokens by a learned score and keeping the top ones. The second part is the one a skeptic will doubt, and the experiments are built around it.
Why this gap is real
The recall problem in linear attention is well documented. Zoology trains many sub-quadratic language models on the Pile. It attributes 82% of their perplexity gap to transformers to "associative recall hits," meaning tokens that require retrieving an earlier key–value association. It also argues that a fixed-size recurrent state cannot solve multi-query recall unless the state grows with sequence length. That result constrains any fixed-memory design, including ours. We accept it and do not claim to beat it. Our aim is to spend a fixed budget better than a recency window does. BASED pairs a Taylor-series approximation of softmax with a small exact sliding window. It reports large recall gains and high throughput, but its exact memory is always the most recent contiguous tokens. Interdomain Attention compresses the history onto continuous basis functions and admits a remaining gap on exact-string recall. Taken together, these papers motivate the proposal: exact token-level addressing matters, and today it is only available for recent tokens.
Two papers already connect optimization-based selection to attention-adjacent components, and they are the closest prior work. USMoE poses the assignment of tokens to experts in mixture-of-experts layers as a global linear program and solves it with a flattened top-K. It works in the feedforward routing layer, not in attention memory, and it uses greedy selection rather than rounding with guarantees. Fast KV Compaction via Attention Matching compresses a softmax transformer's key–value cache after the fact. It selects tokens by greedy sparse recovery (orthogonal matching pursuit) and fits a per-token weight to stand in for discarded mass, and it beats eviction heuristics such as H2O at 50x compression. Our design differs in three ways. Selection happens online inside a linear-time architecture during training, not after training on a quadratic model. Discarded mass goes into a learned recurrent summary rather than into bias terms on the kept tokens. And the rounding step has an exact budget and preserves each token's marginal retention probability.
The rounding technique itself comes from the combinatorial optimization literature. The nearly-linear-time knapsack paper uses swap rounding while keeping only a constant number of coordinates fractional at any time. We borrow that "controlled fractionality" idea directly. The same paper's enormous constant factors are a warning that its guarantee-driven machinery should not be imported wholesale, so we borrow only the pairwise mass-transfer step. Online Dependent Rounding Schemes shows that online rounding decisions can keep budgets while retaining good ratios, which suggests irrevocable streaming decisions need not be crude. ProbFair pairs continuous pull probabilities with dependent rounding to enforce hard budgets, which is the closest structural template for our training/inference split.
Core mechanism
At step $t$ the layer holds a linear state $S_t \in \mathbb{R}^{d\times d}$ and a cache of $B$ exact key–value slots. A small scoring head gives each token a retention value $x_i \in [0,1]$. One subtlety matters here. If the only constraint is $\sum_i x_i = B$ and the objective is linear in $x$, the optimal solution is already integral: it just keeps the top $B$ scores. There would be nothing for rounding to do. We therefore use a regularized relaxation. The fractional retention is the projection of the scores onto the capped simplex, which yields a sparse, clipped-linear solution in which most tokens are exactly 0 or 1 and only borderline tokens are fractional. Each token's write into the summary is scaled by its compressed share:
$$S_t = S_{t-1} + (1 - x_t)\,\phi(k_t)v_t^\top,$$
Here $\phi$ is the feature map, and $k_t, v_t$ are the token's key and value. The token is also read from the exact cache with weight $x_t$. As tokens arrive online, the new token competes only with the at most one currently fractional slot, and swap rounding between them restores the invariant: $B-1$ or $B$ integral slots plus at most one fractional slot. When a token's retention drops, its lost mass $\Delta x$ is added to $S_t$ at that moment. The per-step cost is $O(d^2 + Bd)$, so the whole sequence costs $O(N(d^2 + Bd))$, which remains linear in $N$.
This bookkeeping also partly resolves the tension the research file identifies, that discrete selection breaks the associativity that makes linear attention cheap. Associativity is kept for the summary. Only the $B$ cached tokens are handled by exact softmax, and $B$ is constant.
Research Program
The work has three parts. The first builds the layer and a chunked training kernel in the style of Lightning Attention. Within a chunk, the capped-simplex projection is computed in parallel, and swap rounding is applied only at inference.
The second is analysis. The summary part of the output is linear in $x$, so under marginal-preserving rounding its expectation matches the fractional training output exactly. The softmax cache part is nonlinear in $x$, so a mismatch remains there. We will measure how large that mismatch is and track it through training. We will also report the fraction of time the fractional slot is non-empty, because a very small fraction would mean rounding hardly matters.
The third is the experiments below. Their purpose is to separate three effects: learned selection versus recency, fractional training versus straight-through top-K, and dependent rounding versus deterministic or independent rounding.
Baselines
The naive reference is plain linear attention with the additive update and no exact cache. On Wikitext-103, Going Beyond Linear Transformers with Recurrent Fast Weight Programmers reports a test perplexity of 38.3 for this model, against 34.1 for a quadratic transformer and 33.8 for Delta LSTM. We will reproduce that setting so our numbers can be compared directly with those. The quadratic transformer serves as an upper reference, not as a competitor.
The strongest existing method on this question is BASED, the Taylor-series linear attention with a static exact window from Simple linear attention language models balance the recall-throughput tradeoff. That paper reports that BASED beats Mamba by 10.36 accuracy points on recall-intensive tasks at 1.3B parameters. To make the comparison fair, we will use the same Taylor feature map and give both models identical memory: the state plus the same number of exact slots $B$, measured in bytes. Both will get the same tokens, parameter count, and hyperparameter search budget. Our method beats BASED only if it improves MQAR accuracy and RULER retrieval once needles sit outside the window, while losing no more than a small margin in perplexity and throughput. As a second strong baseline, we add a delta-rule linear attention without a cache, following Practical Computational Power of Linear Transformers.
The most dangerous competitor is our own architecture with the rounding idea removed. This is learned top-B eviction: the same scoring head, the top $B$ tokens kept deterministically, evicted tokens written fully into the summary, and training via a straight-through estimator. We also run an H2O-style variant in which eviction is driven by accumulated attention mass. Two further ablations isolate the rounding step. Independent rounding keeps each token with probability $x_i$ and handles budget overflow by truncation. Deterministic thresholding of the trained fractional values replaces swap rounding. A last ablation removes the "evicted mass goes into the summary" rule, so dropped tokens are simply discarded. That ablation tests whether conserving each token's mass matters at all.
Why not just…?
Why not just use a static sliding window like BASED? It is the right default. Because it is contiguous, it maps well onto tensor cores, and its throughput advantage is real. However, by construction it cannot hold a needle placed thousands of tokens back. RULER shows that many long-context models fail well before their claimed length on retrieval and variable tracking. The decisive test is RULER needle depth versus accuracy at equal memory. If our method only matches the window when needles are recent and does not win when needles are distant, the idea fails. We also test a split budget (half window, half selected slots), since recency may simply be the best prior for part of the budget.
Why not just keep the top-B tokens by a learned score? This is a real threat, and we do not argue it away. With a single cardinality constraint, deterministic top-B already enforces the budget exactly, so swap rounding's main textbook advantage, exact feasibility, is shared with greedy selection. USMoE's gains from global rather than local selection (USMoE) and the attention-matching paper's wins over H2O (Fast KV Compaction) suggest the selection criterion matters. Neither, however, compares against our relaxation. Our bet rests on training rather than on feasibility: fractional retention provides gradients to borderline tokens that straight-through top-K misroutes. The learned-top-B ablation settles this directly. If it matches us, the contribution shrinks to "learned non-contiguous retention with mass conservation," and we will report that outcome.
Why not just use a delta-rule update and skip discrete selection? Delta-rule models reach 100% on Parity and 85–92% on Code Execution where plain linear models score 0% (Recurrent Fast Weight Programmers). Delta LSTM, however, trains at 14K words/sec versus 66K for the base linear model. Zoology's state-size argument also applies to any fixed recurrent state, whatever its update rule. The two ideas are complementary, so we include a delta-rule summary paired with our cache as a fourth arm.
Why not just add one full-attention layer? Zoology reports that hybrids close 97.4% of the perplexity gap. Even one uncompressed layer, though, keeps a cache that grows with $N$. We report this hybrid as a memory-unbounded reference point and compare against it at matched memory only at lengths where it still fits.
Proposed Experiments
On MQAR we vary the number of stored pairs, the sequence length, and the budget $B$. The claim predicts that our method's accuracy stays near-perfect until the number of queried associations exceeds $B$, while the window baseline collapses once associations fall outside the window. No reported MQAR accuracy for BASED at a fixed state size was found on Lacuna, so we will reproduce BASED ourselves. On Wikitext-103 we reproduce the fast-weight setting above to check that selection does not hurt perplexity relative to 38.3 for plain linear attention and 34.1 for the transformer.
At 360M parameters, trained on a 10B-token Pile subset as in Zoology, we measure perplexity split into associative-recall hits and all other tokens. This split tests whether the gain lands where the 82% gap lives. We then evaluate RULER at 4k to 32k tokens, sweeping needle depth and variable-tracking hop count, and run SWDE and FDA as used in BASED. No reported RULER or SWDE number for BASED was found on Lacuna, so all comparisons will be same-recipe reproductions.
Throughput and memory are measured for prefill and for generating 1,024 tokens against BASED.
Three checks are decisive. First, needle-depth curves on RULER against the matched-memory window. Second, the learned-top-B ablation on MQAR and recall-hit perplexity; this is the check that determines whether the rounding and relaxation pay for themselves. Third, the discard-versus-conserve ablation, which shows whether routing evicted mass into the summary is doing real work.
References
- Zoology: Measuring and Improving Recall in Efficient Language Models
- Simple linear attention language models balance the recall-throughput tradeoff
- Interdomain Attention: Beyond Token-Level Key-Value Memory
- Rethinking Sparse Mixture of Experts from a Unified Perspective
- Fast KV Compaction via Attention Matching
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Online Dependent Rounding Schemes
- Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting
- Various Lengths, Constant Speed: Efficient Language Modeling with Lightning Attention
- Going Beyond Linear Transformers with Recurrent Fast Weight Programmers
- Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions
- RULER: What’s the Real Context Size of Your Long-Context Language Models?