# Token Statistics Transformer: Linear-Time Attention via Variational Rate Reduction

arXiv: https://arxiv.org/abs/2412.17810 · HTML: https://mlsanity.com/paper/2412.17810/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 48 references that are in the map.
- First posted on arXiv 23 Dec 2024.

## Builds on (most cited first, 6 of 6)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Dive into Deep Learning](https://mlsanity.com/paper/2106.11342/) (2021)
- [White-Box Transformers via Sparse Rate Reduction: Compression Is All There Is?](https://mlsanity.com/paper/2311.13110/) (2023)

## Built on by (most cited first, 10 of 10)

- [Simplifying DINO via Coding Rate Regularization](https://mlsanity.com/paper/2502.10385/) (2025)
- [Transolver is a Linear Transformer: Revisiting Physics-Attention through the Lens of Linear Attention](https://mlsanity.com/paper/2511.06294/) (2025)
- [Adaptive Context Length Optimization with Low-Frequency Truncation for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2510.26389/) (2025)
- [Towards Interpretable and Efficient Attention: Compressing All by Contracting a Few](https://mlsanity.com/paper/2509.16875/) (2025)
- [MGDFIS: Multi-scale Global-detail Feature Integration Strategy for Small Object Detection](https://mlsanity.com/paper/2506.12697/) (2025)
- [A Weakly Supervised Transformer for Rare Disease Diagnosis and Subphenotyping from EHRs with Pulmonary Case Studies](https://mlsanity.com/paper/2507.02998/) (2025)
- [HLA: Hadamard Linear Attention](https://mlsanity.com/paper/2602.12128/) (2026)
- [Interpretable and Sparse Linear Attention with Decoupled Membership-Subspace Modeling via MCR2 Objective](https://mlsanity.com/paper/2601.17042/) (2026)
- [Self-Gating Attention for Efficient Time Series Forecasting](https://mlsanity.com/paper/2607.02344/) (2026)
- [Attention-Only White-Box Transformer via LeJEPA-Based Self-Supervised Pretraining](https://mlsanity.com/paper/2608.04213/) (2026)

## Abstract (arXiv)

The attention operator is arguably the key distinguishing factor of transformer architectures, which have demonstrated state-of-the-art performance on a variety of tasks. However, transformer attention operators often impose a significant computational burden, with the computational complexity scaling quadratically with the number of tokens. In this work, we propose a novel transformer attention operator whose computational complexity scales linearly with the number of tokens. We derive our network architecture by extending prior work which has shown that a transformer style architecture naturally arises by "white-box" architecture design, where each layer of the network is designed to implement an incremental optimization step of a maximal coding rate reduction objective (MCR2). Specifically, we derive a novel variational form of the MCR2 objective and show that the architecture that results from unrolled gradient descent of this variational objective leads to a new attention module called Token Statistics Self-Attention (TSSA). TSSA has linear computational and memory complexity and radically departs from the typical attention architecture that computes pairwise similarities between tokens. Experiments on vision, language, and long sequence tasks show that simply swapping TSSA for standard self-attention, which we refer to as the Token Statistics Transformer (ToST), achieves competitive performance with conventional transformers while being significantly more computationally efficient and interpretable. Our results also somewhat call into question the conventional wisdom that pairwise similarity style attention mechanisms are critical to the success of transformer architectures. Code will be available at https://github.com/RobinWu218/ToST.