REVIEW 3 major objections 5 minor 11 references
From TLinFormer to TConstFormer: The Leap to Constant-Time Transformer Attention: Achieving O(1) Computation and O(1) KV Cache during Autoregressive Inference
T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read TConstFormer claims that autoregressive generation past the first token runs in amortized constant time with a constant-size KV cache, via a fixed context window re-encoded once per k tokens.
desk verdict The O(1) amortized inference claim is contradicted by the paper's own equations; the architecture is a plausible compression variant but the central result doesn't hold. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The periodic state update mechanism: a fixed-size context window (Woh) is re-encoded by cross-attention from the full history only when the sliding generation window advances, and a cache hit reuses that encoding for the next k-1 tokens. The cache-miss/cache-hit dual mode carries the argument: cache-miss cost is linear in N, while cache-hit cost is constant, (H+1)D Woh + (H+2)D Wog^2, independent of N.
What would settle it
Decode continuously from a fixed long prompt for more than Wog generated tokens (e.g., 100,000 tokens with Wog=256) while measuring average per-token latency and peak KV cache usage. If the average latency grows with N, or the cache size exceeds roughly 2B((H+1)Woh+(H+2)Wog)dmodel bytes, the amortized O(1) claim fails.
Extended reading notes
Core claim
On its own terms, the paper discovers a way to reorganize Transformer attention so the inference state is a bounded-size representation rather than the full history. TConstFormer compresses the historical context into a fixed window Woh through cross-attention layers, lets the generation window Wog attend only to that compressed context, and only recomputes the context encoding when the window slides. Between slides, each new token costs constant work; on the slide, the cost is linear in N. The paper presents this as 'Constant-State Representation': the model's state no longer grows with history, making the KV cache O(1) and per-token compute amortized O(1).
Load-bearing premise
The load-bearing premise is that the linear cache-miss recomputation is a rare one-off event and can be amortized away; but on a continuous stream it recurs every Wog generated tokens while the history length N keeps growing, so the average per-token cost scales with N unless something bounds how often resynchronization happens.
Editorial extensions
If this is right
- If the claims hold, a deployed model could generate the 2nd through k-th tokens of any response in constant time regardless of how long the input prompt is, as long as the prompt itself is fixed.
- KV cache memory would stop being a function of context length, so the practical OOM ceiling on long-context inference disappears; only the Woh+Wog window needs to be resident.
- The approach is compatible with the paper's existing TLinFormer and with standard Transformer layers, so it can be dropped into decoder stacks at equivalent parameter count.
- Training cost rises (the paper reports roughly 42% slower epochs) but this is a one-time investment traded against repeated inference gains.
- The constant-state design implies old tokens are only accessible through a compressed summary, so tasks requiring verbatim recall are expected to be hard, which the paper flags as open.
Reading between the lines
- A reader extending the paper to an unbounded stream should note that the paper's own linear cache-miss cost recurs every Wog generated tokens; the amortized constant claim applies cleanly to a single finite generation cycle, not to a continuously growing history without additional accounting.
- The constant-state requirement suggests a testable scaling prediction: models with larger Woh should show better long-range recall; if perplexity on long-context tasks stays flat as Woh grows, the compressed summary is not the limiting factor.
- Because the cache-hit cost still includes O(Wog^2) causal self-attention, 'constant' is relative to N, not to the generation window; shrinking Wog trades per-token latency against the amount of context available within the current chunk.
- The paper's information-theoretic argument implies a concrete quantitative claim, that a compressed context of around 134 tokens should suffice for a 10^7-token sequence; this could be tested directly by measuring downstream perplexity at fixed compression ratios across sequence lengths.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes TConstFormer, a Transformer-like architecture that compresses historical context into a fixed-size window Woh and maintains a generation window Wog. The authors claim a true O(1) KV cache and an amortized O(1) per-token inference cost: k-1 'cache hit' steps are constant-time and one periodic 'cache miss' step performs a linear-time synchronization. The paper derives cost formulas in Appendix A, trains 41M-parameter variants on wikitext-103, and reports inference time and memory comparisons against a standard Transformer and TLinFormer. The central computational claim is contradicted by the paper's own equations: Eq. (4) makes every cache miss linear in total sequence length N, and Section 5.2.1 states that such a miss recurs after every Wog generated tokens. On a continuous stream, the average per-token cost is therefore O(N/Wog), which grows with N, not O(1).
Significance. If the amortized O(1) claim were correct, TConstFormer would be a significant architectural advance for streaming inference. The paper does provide a concrete fixed-memory design, explicit complexity expressions, and a public code release, which are useful. However, the headline result is unsupported by the paper's own derivation. The experiments only measure constant cache-hit steps and never exercise the recurring linear synchronization, so the empirical evidence does not rescue the claim. The honest version of the contribution is a fixed-memory architecture with O(N/Wog) amortized per-token cost between periodic full recompressions; that is a useful trade-off but not the claimed 'leap to constant-time attention.'
major comments (3)
- [§4.3, Eq. (4), Eq. (5)] The amortized O(1) claim is contradicted by the paper's own formulas. A cache miss costs O(N) according to Eq. (4), and Section 5.2.1 states that a cache miss recurs after every Wog generated tokens. Over one full cycle the total cost is O(N) + (Wog-1)·O(1), so the average per generated token is O(N/Wog). Since N itself grows by Wog each cycle, generating T tokens costs sum_{j=0}^{T/Wog} O(N0 + j·Wog) = O(T^2/Wog), giving an average per-token cost of O(T), not O(1). The abstract's 'amortized' averaging over only the k-1 constant steps omits the recurring linear step.
- [§5.2.1 and §6.4.1] The experimental protocol never triggers a cache miss after the initial one. Section 6.4.1 generates only 6 tokens per initial sequence length and selects the third token as the cache-hit example. With the stated 1K-512-0.5 configuration, Wog = 256, so all measured tokens lie inside the same generation window and the periodic O(N) synchronization is never exercised. Consequently, Figure 8(c)'s horizontal lower bound and the 40x speedup ratio characterize only the cache-hit regime; they do not support an end-to-end O(1) streaming claim. The authors should measure latency over at least two full sync cycles and report the amortized cost.
- [§4.2] The 'cache hit' definition makes the O(1) result partly definitional: it excludes the very step that depends on N. The linear recompression is not a one-time initialization cost but a recurring part of inference after every Wog tokens. Treating that step as outside the amortized accounting is circular. The correct amortized complexity is O(N/Wog) per token, which is constant only if Wog grows with N, but Wog is a fixed hyperparameter in this design.
minor comments (5)
- [§1, Eq. notation] The expression O(N^2 d) appears with a missing superscript in the introduction; please fix the typography.
- [§4] Woh, Wog, and H are introduced informally. A short notation table or explicit hyperparameter definitions before Eq. (4) would improve readability and reproducibility.
- [§6.4.1] The testing protocol should state the value of Wog used in inference and explain explicitly that only 6 tokens are generated, so no cache miss occurs during the timed segment. This is essential for interpreting Figures 8(c), 8(f), and 8(i).
- [§7] The compressed-sensing heuristic n > C log N is cited without evidence that a language model's hidden state satisfies the sparsity or restricted-isometry assumptions required by that theory. This passage should be labeled as speculative intuition, not a theoretical foundation.
- [Title and abstract] The phrase 'constant-time Transformer attention' overclaims. At best, the model offers constant time per token between periodic linear synchronizations, with amortized cost O(N/Wog).
Circularity Check
Amortized O(1) claim is imposed by definition: the recurring linear cache-miss cost (Eq. 4) is omitted from the amortization, so the average is O(N/Wog), not O(1).
-
other
[Abstract / Introduction; Section 4.3; Section 5.2.1; Appendix A Eq. (4)]
"The model performs purely constant-time operations for k−1 consecutive steps and executes a global information synchronization at a linear cost only on the k-th step (e.g., k = 256). This makes the average single-step computational cost constant, ensuring sustained high throughput."
The advertised amortized O(1) is not derived from the paper's own equations. Eq. (4) gives the cache-miss cost as C1·N + C0, with C1 = D·(2Woh), and Eq. (5) gives the cache-hit cost as constant. Section 5.2.1 states that a cache-miss recomputation occurs after every Wog generated tokens. Averaging over one full generation cycle yields [C1·N + C0 + (Wog−1)·T_hit]/Wog = C1·N/Wog + O(1), which grows with N — not O(1). The only way to read the claim as O(1) is to define 'amortized' over a fixed k-step window while ignoring that the recurring linear term itself scales with the ever-growing N. Thus the headline complexity is put into the definition of 'amortized' rather than obtained from Eqs. (4)–(5).
full rationale
The paper's per-cache-hit O(1) cost (Eq. 5) is a genuine, self-contained derivation, and there is no fit-to-data circularity or load-bearing self-citation chain. However, the central claim — 'O(1) in an amortized sense' — is circular/definitional. The paper defines a cache hit to exclude the linear recompression of the growing history, and then treats that linear recompression as a one-off cost per fixed-size generation cycle. But Section 5.2.1 shows the recomputation recurs every Wog generated tokens while the total sequence length N keeps growing. Combining the paper's own Eq. (4) (linear cache-miss cost) with Eq. (5) (constant cache-hit cost) gives an average per-token cost of O(N/Wog), which is not constant. The advertised complexity therefore relies on defining 'amortized' in a way that discards the scaling of the very term that must be amortized. This is a definitional forcing of the result rather than a consequence of the stated equations, so it warrants a high circularity score even though the underlying per-step constant-time computation for cache hits is valid.
Assumptions & free parameters
free parameters (3)
- Historical context window size Woh =
256 or 512 in experiments; ratio variants 0.382, 0.5, 0.618
- Generation window size Wog =
256 or 512, with ratios as above
- Internal depth H =
2
assumptions (5)
- standard math Attention is computed by the exact softmax formula and cost counts only FLOPs
- domain assumption Woh, Wog, and H are fixed and bounded after training
- ad hoc to paper A cache miss occurs only once per generation cycle, after Wog new tokens, and the linear cost can be amortized over those Wog tokens
- domain assumption A TConstFormer block with H=2, stacked twice, has the same parameter count as an 8-layer standard Transformer
- domain assumption The compressed-sensing guideline n > C log N justifies a small history window
Cite this review
Pith. "Pith review of From TLinFormer to TConstFormer: The Leap to Constant-Time Transformer Attention: Achieving O(1) Computation and O(1) KV Cache during Autoregressive Inference." pith.science (2026). https://pith.science/paper/WLBLDWPS
@misc{pith2026250900202,
author = {Pith},
title = {Pith review of: From TLinFormer to TConstFormer: The Leap to Constant-Time Transformer Attention: Achieving O(1) Computation and O(1) KV Cache during Autoregressive Inference},
year = {2026},
howpublished = {\url{https://pith.science/paper/WLBLDWPS}},
note = {Machine review of arXiv:2509.00202}
}
abstract
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(N^2 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.
Figures
Figures from the paper (5 more)
Reference graph
Works this paper leans on
-
[1]
Mohammed M. Abo-Zahhad, Aziza I. Hussein, and Abdelfatah M. Mohamed. Compressive Sensing Algorithms for Signal Processing Applications: A Survey. International Journal of Communications, Network and System Sciences , 08(06):197–216, 2015
work page 2015
-
[2]
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The Long-Document Transformer, December 2020. arXiv:2004.05150 [cs]
arXiv 2020
-
[3]
Emmanuel Candes, Justin Romberg, and Terence Tao. Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information, September
-
[4]
Zhongpan Tang. Rethinking Transformer Connectivity: TLinFormer, A Path to Exact, Full Context-Aware Linear Attention, August 2025. arXiv:2508.20407 [cs]
work page Pith review arXiv 2025
-
[5]
Gomez, Lukasz Kaiser, and Illia Polosukhin
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need, August 2023. arXiv:1706.03762 [cs]. A Detailed Derivation of Computational Complexity This appendix provides a detailed derivation of Equations (1) and (5) from the main text. We analyze the upper bound o...
arXiv 2023
-
[6]
Computational Cost of the Left Window (Historical Context) : • First Layer Cross-Attention: The query sequence from the context window at- tends to the full history. Cost is D· (N− Wog)· Woh. • Intermediate Self-Attention Layers ( H layers): Self-attention is performed within the context window of size Woh. Cost is H· D· W 2 oh. • Final Layer Cross-Attent...
-
[7]
Computational Cost of the Right Window (Generation Area) : • Cross-Attention with Intermediate Context Layers ( H + 1 layers, includ- ing final output layer) : The generation window attends to the processed context window. Cost is ( H + 1)· D· Wog· Woh. • Causal Self-Attention (All H+2 layers, including final output layer): Causal self-attention is perfor...
-
[8]
Derivation of Total Computational Cost (T): The total cost is the sum of the costs of the two windows, T = Cleft + Cright. T = [ 2D(N− Wog)Woh + HDW 2 oh ] + [ (H + 1)DWogWoh + (H + 2)DW 2 og ] Step 1: Expand all terms = ( 2DN Woh− 2DWogWoh + HDW 2 oh ) + ( HDW ogWoh + DWogWoh + HDW 2 og + 2DW 2 og ) Step 2: Combine like terms = 2DN Woh− 2DWogWoh + DWogWo...
Show all 11 references
-
[9]
Computational Cost of the Left Window (Historical Context) : Cleft = 0
-
[10]
Cost is ( H + 1)· D· Woh
Computational Cost of the Right Window (Generation Area) : • Cross-Attention with Intermediate Context Layers (H +1 layers, including final output layer): Only the last token of the generation window participates in the computation. Cost is ( H + 1)· D· Woh. • Causal Self-Atte...
-
[11]
T = (H + 1)DWoh + (H + 2)DW 2 og Derivation complete
Derivation of Total Computational Cost (T): The total cost is the sum of the costs of the two windows, T = Cleft + Cright. T = (H + 1)DWoh + (H + 2)DW 2 og Derivation complete. 19
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.