# From TLinFormer to TConstFormer: The Leap to Constant-Time Transformer Attention: Achieving O(1) Computation and O(1) KV Cache during Autoregressive Inference

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 1 of its 7 references that are in the map.
- First posted on arXiv 29 Aug 2025.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

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

- [Rethinking Transformer Connectivity: TLinFormer, A Path to Exact, Full Context-Aware Linear Attention](https://mlsanity.com/paper/2508.20407/) (2025)

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

- [ProxyFormer: A Dual-Stream Proxy Architecture for Ultra-Long Context and High-Resolution Generation](https://mlsanity.com/paper/2608.23463/) (2026)

## Abstract (arXiv)

Although the Transformer has become the cornerstone of modern AI, its autoregressive inference suffers from a linearly growing KV Cache and a computational complexity of O(N2 d), severely hindering its ability to process ultra-long sequences. To overcome this limitation, this paper introduces the TConstFormer architecture, building upon our previous work, TLinFormer. TConstFormer employs an innovative periodic state update mechanism to achieve a truly constant-size O(1) KV Cache. The computational complexity of this mechanism is also O(1) in an amortized sense: it performs purely constant-time computations for k-1 consecutive steps (e.g., k=256) and executes a single linear-time global information synchronization only on the k-th step. Theoretical calculations and experimental results demonstrate that TConstFormer exhibits an overwhelming advantage over baseline models in terms of speed, memory efficiency, and overall performance on long-text inference tasks. This breakthrough paves the way for efficient and robust streaming language model applications.