Linear attention avoids the cost of comparing every token with every other token. It does this by mapping each key and query through a feature map and summing the results into a fixed-size memory. We propose a simple change of viewpoint. If that feature map is a sparse, nonnegative code over $m$ learned "atoms" (basis directions), then linear attention is exactly a dictionary bottleneck. Each token writes its value into the few atoms its key activates, and reads back from the few atoms its query activates. This makes the feature map a feed-forward sparse approximation, meaning a network that predicts a sparse code in one pass instead of running an iterative solver. That literature has a precise, proven account of where single-pass encoders fail.
Our claim is that a large part of linear attention's known weakness is an encoding failure, not only a capacity failure. That weakness is that distinct tokens interfere inside the fixed-size memory. Single-layer threshold encoders cannot separate similar-but-distinct keys onto distinct atoms, so their contributions pile up in the same memory slots. A slightly deeper sparse encoder over a large dictionary should reduce this interference. It should also keep cost linear in sequence length and proportional to the number of active atoms per token, not to the dictionary size. Unlike pruning or a handful of summary tokens, it keeps a per-token path that dense prediction needs.
Core Claim
Let $z(x) \in \mathbb{R}_{\ge 0}^m$ be an $s$-sparse code produced by an encoder $f_\theta$. Here $m$ is the dictionary size, with $m \gg d$, and $s \ll m$ is the number of active atoms. Write $q_i, k_j, v_j$ for the query, key and value of tokens $i, j$ in a sequence of $N$ tokens. The layer computes
$$ y_i \;=\; \frac{\sum_{a} z(q_i)_a\, S_a}{\sum_a z(q_i)_a\, n_a + \epsilon}, \qquad S_a = \sum_{j=1}^{N} z(k_j)_a\, v_j, \quad n_a = \sum_{j=1}^N z(k_j)_a . $$
In this expression, $S_a \in \mathbb{R}^{d_v}$ is the value content stored in atom $a$, $n_a$ is its normalizer, and $\epsilon$ is a small constant. Because only $s$ atoms are touched per token, writing and reading both cost $O(N s d_v)$. The memory is $m \times d_v$ regardless of $N$. This is ordinary linear attention with a particular feature map. We do not claim the layer is new in form. The new contribution is the diagnosis, the encoder design that follows from it, and the measurement.
The diagnosis is about crosstalk. When a query matches key $k_j$, every other token sharing atoms with $k_j$ adds crosstalk to $y_i$. If supports were spread like random $s$-subsets of $m$, each pair would share about $s^2/m$ atoms. The total crosstalk relative to the signal would then scale like $N s / m$, so clean retrieval would need roughly $N \ll m/s$.
A learned single-layer encoder does worse than random. The amortization gap result of Compute Optimal Inference and Provable Amortisation Gap in Sparse Autoencoders shows that $\mathrm{ReLU}(Wx+b)$ encoders cannot recover the true sparse code from a lower-dimensional dense vector. That paper also found that a small MLP encoder raised median automated interpretability F1 from roughly 0.60 to 0.83 on GPT-2 activations. In attention, this predicts that similar keys collapse onto the same supports and interfere more than the random baseline.
We therefore predict three things for a fixed attention FLOP budget, measured as $s$ times encoder cost. A two-layer sparse encoder trained with an auxiliary reconstruction objective $k \approx D z(k)$ will lower retrieval crosstalk and improve accuracy over single-layer thresholding. Here $D$ is a decoding dictionary, separate from the encoder as in Scaling White-Box Transformers for Vision. The same encoder will close most of the gap to quadratic attention on dense prediction. A dense feature map of equal state size will not.
Relation to Prior Work
Two papers motivate the reframing. Attention: Self-Expression Is All You Need relates attention to self-expressive subspace clustering, where sparsity selects relevant tokens. It is purely analytical and notes that sparse solvers are too slow. In-Context Compositional Learning via Sparse Coding Transformer replaces query, key and value projections with encoding and decoding dictionaries and single-step soft-thresholding. It reaches 82.7% versus 65.1% on S-RAVEN, but only on sequences of at most 16 panels and with exactly the single-layer encoder the amortization-gap result warns against. We keep its feed-forward spirit. We move it to long sequences, where the scaling question exists, and replace its encoder.
Three dictionary-attention methods constrain the design. Learning Dictionary for Visual Attention (Dic-Attn) decomposes features with an iterative Elastic Net solve. It cuts 292G to 20G MACs on one input shape but degrades past seven blocks and was tested only on CIFAR-10 and ModelNet40. This tells us iterative solving inside every layer is fragile. ATD has image tokens cross-attend to learned dictionary tokens with dense softmax. It needs a reparameterized scale to fight attention dilution as the dictionary grows. Sparse supports avoid dilution by construction, because each token spreads its mass over only $s$ atoms. Scaling White-Box Transformers for Vision (CRATE-α) uses unrolled ISTA with overcomplete, decoupled dictionaries in the MLP. It leaves attention quadratic, which is the complement of what we do. We borrow its decoupled encode/decode dictionaries, and from Sparse Coding with Multi-layer Decoders using Variance Regularization we borrow a variance penalty against dead atoms.
On the attention side, LookupViT compresses tokens into $M$ summary tokens via softmax cross-attention. Its authors report it does not yet handle detection or segmentation. Dynamic Linear Attention keeps dense linear-attention states but merges them by an information score. Neither treats the feature map as a sparse code whose recovery quality can be measured.
Research Program
We will build a ViT in which every attention layer is replaced by the sparse-code layer above, with separate encoders for queries and keys. The main variable is the encoder, which we set to one of four forms at matched attention FLOPs:
- single-layer soft-thresholding, the Sparse Coding Transformer form;
- a two-layer MLP followed by top-$s$ selection;
- three unrolled ISTA steps with learned step sizes, the CRATE-style form;
- a dense nonnegative feature map with the same state size $m \times d_v$, as the non-sparse control.
Secondary variables are $m$ (512 to 8192), $s$ (4 to 32), and whether the auxiliary reconstruction loss and variance penalty are on. A local depthwise convolution sits beside the layer in every variant so that fine spatial detail is not the bottleneck being measured.
Analysis comes before scale. First, on a synthetic associative-recall task with controllable key similarity, we measure the following as $N$ grows:
- per-query crosstalk energy;
- support overlap between distinct keys;
- the code's mean correlation with ground-truth supports, the MCC metric used in the amortization-gap paper.
This tests whether crosstalk follows the $N s/m$ scaling for good encoders and exceeds it for single-layer ones. Second, we pretrain on ImageNet-1K and transfer to ADE20K, which tests both global mixing and per-token fidelity.
Baselines
The naive reference is a standard ViT with full softmax attention, trained under the identical recipe at each resolution. It defines the accuracy ceiling and the quadratic cost curve. A run counts as matching it if top-1 is within 0.5 points at 224px while using less attention memory at 384px and 512px. We will also report where the ViT runs out of memory.
The strongest compression competitor is LookupViT, which reports 79.1% ImageNet-1K accuracy with 2.12x fewer FLOPs than a ViT-B/16 at 78.6% (LookupViT). It is the most direct rival because it also routes $N$ tokens through a small learned set, using softmax instead of sparse codes. We will reimplement it at our model size, with $M$ chosen so its FLOPs equal ours, using the same data, epochs and hyperparameter search budget. Beating it means higher top-1 at equal FLOPs and, more importantly, a working ADE20K result, where LookupViT has none.
For absolute context on hierarchical efficient backbones, SG-Former-Base reports 84.7% top-1 and 52.7 mIoU on ADE20K (SG-Former). That comparison is not FLOP-matched, so we will report it but not claim to beat it.
The linear-attention baseline is a dense-feature-map linear attention with the same state size. We will also include the information-score state merging of Dynamic Linear Attention adapted to bidirectional vision. We found no reported result on Lacuna for linear attention on ImageNet-1K or ADE20K. Its reported numbers are relative gains on RULER, so we will establish this baseline ourselves under our recipe.
The pruning baseline is Top-K token pruning, shown to be a resilient baseline by Which Tokens to Use?. For segmentation we will recover pruned tokens with the standard fill-in scheme.
The key ablation isolates the encoder. The four encoder variants share everything else and are matched on attention FLOPs. If the deep sparse encoder does not beat both single-layer thresholding and the dense map, the central claim fails.
Why not just…?
Why not just use softmax cross-attention to a small set of learned summary tokens, as LookupViT does? This is the real threat. On classification, summary tokens may do just as well, because classification needs only a global summary. The difference should appear where each token must read back its own information. A sparse code gives each token a private combination of $s$ atoms, whereas a softmax write over $M=25$ summary tokens blurs it. The ADE20K comparison and the high-similarity regime of the synthetic recall task settle this. If LookupViT matches us there too at equal FLOPs, we will report that sparsity buys nothing over softmax routing.
Why not just use ordinary linear attention, or Dynamic Linear Attention, with a better dense feature map? Our dense-map control has the same state size. The question is whether a dense $m$-dimensional feature map at $O(N m d_v)$ cost can match a sparse one at $O(N s d_v)$. If a dense map at equal FLOPs, and therefore much smaller $m$, matches us, then the sparse-coding view is just a relabeling. The synthetic crosstalk measurements will show which mechanism accounts for any gain.
Why not just prune tokens with Top-K or FastV-style attention scores? An Image is Worth 1/2 Tokens After Layer 2 cuts up to 45% of compute in vision-language models with no loss. Pruning is cheap and strong for classification. However, Decoupling Spatial and Semantic Token Compression documents spatial bias and lost context, and discarded tokens cannot be recovered for dense outputs. We expect pruning to be competitive on ImageNet-1K and to lose on ADE20K, and we will report both.
Why not just run a few steps of an exact solver instead of training a deeper encoder? The unrolled-ISTA arm tests this at matched FLOPs. Dic-Attn's degradation beyond seven blocks suggests per-layer iterative solving destabilizes deep stacks. Our experiments will show whether a learned two-layer encoder gets the same code quality, measured by MCC and crosstalk, more stably.
Proposed Experiments and Decisive Checks
The first decisive check is the synthetic recall study. Plot retrieval accuracy and crosstalk against $N$ for each encoder at fixed $m$ and $s$. The hypothesis survives only if three things hold: the deep sparse encoder approaches the random-support $N s/m$ curve, single-layer thresholding falls measurably below it as key similarity rises, and the gap tracks code MCC.
The second check is ImageNet-1K at small-ViT scale. Each method trains under one recipe at 224px. We fine-tune at 384px and 512px, reporting top-1, attention FLOPs, measured throughput and peak memory.
The third check is ADE20K semantic segmentation in mIoU, using one shared decoder head across all backbones. This is where we expect the method to separate from LookupViT and from pruning.
Two results would falsify the proposal. One is the deep sparse encoder failing to beat the dense feature map at equal FLOPs on both ADE20K and the high-similarity recall task. The other is the reconstruction loss having no effect on crosstalk. Either would mean the amortization gap is not what limits linear attention here.
References
- Compute Optimal Inference and Provable Amortisation Gap in Sparse Autoencoders
- Scaling White-Box Transformers for Vision
- Attention: Self-Expression Is All You Need
- In-Context Compositional Learning via Sparse Coding Transformer
- Learning Dictionary for Visual Attention
- ATD: Improved Transformer With Adaptive Token Dictionary for Image Restoration
- Sparse Coding with Multi-layer Decoders using Variance Regularization
- LookupViT: Compressing Visual Information to a Limited Number of Tokens
- Dynamic Linear Attention
- SG-Former: Self-guided Transformer with Evolving Token Reallocation
- Which Tokens to Use? Investigating Token Reduction in Vision Transformers
- An Image is Worth 1/2 Tokens After Layer 2: Plug-and-Play Inference Acceleration for Large Vision-Language Models
- Decoupling Spatial and Semantic Token Compression for Vision-Language Model Acceleration