Pith. sign in

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 →

arxiv 2509.00202 v1 pith:WLBLDWPS submitted 2025-08-29 cs.LG

classification cs.LG
keywords TConstFormerconstant-timeattentionKVcacheautoregressiveinferenceperiodicstateupdatelong-contextmodelingstreaminglinear
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

TConstFormer is an attention architecture that aims to decouple per-token inference cost and memory from the length of the generated history. The paper's core claim is that by keeping a fixed-size historical context window and a fixed-size generation window, and by running a single linear-cost 'global synchronization' once every k tokens (k=256), autoregressive generation beyond the first token can run in amortized O(1) time with an O(1) KV cache. If this holds, streaming inference on arbitrarily long text would no longer hit the memory-bandwidth wall of standard Transformers, whose KV cache and per-token latency grow with context. The paper supports the claim with complexity equations for cache-miss and cache-hit modes and with experiments on a 41M-parameter model showing flat cache-hit latency and up to tens of times speedup over baselines.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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)
  1. [§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.
  2. [§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.
  3. [§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. [§1, Eq. notation] The expression O(N^2 d) appears with a missing superscript in the introduction; please fix the typography.
  2. [§4] Woh, Wog, and H are introduced informally. A short notation table or explicit hyperparameter definitions before Eq. (4) would improve readability and reproducibility.
  3. [§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).
  4. [§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.
  5. [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

1 steps flagged · score 7.0 of 10

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).

  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 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on hand-chosen hyperparameters and on the unstated amortization assumption that a growing linear recompression cost can be spread over a fixed window. No new physical or mathematical entities are introduced; the 'Constant-State Representation' is a descriptive concept with no independent falsifiable handle.

free parameters (3)
  • Historical context window size Woh = 256 or 512 in experiments; ratio variants 0.382, 0.5, 0.618
    Chosen by hand; determines the fixed KV cache size and the slope C1 = D(2Woh) of the linear cache-miss cost.
  • Generation window size Wog = 256 or 512, with ratios as above
    Chosen by hand; sets the period between cache misses and the number of constant-time steps over which the paper amortizes cost.
  • Internal depth H = 2
    Chosen pragmatically for the 41M model; controls constants and the asserted parameter parity with an 8-layer baseline.
assumptions (5)
  • standard math Attention is computed by the exact softmax formula and cost counts only FLOPs
    Used throughout Appendix A to derive Equations (1)-(5).
  • domain assumption Woh, Wog, and H are fixed and bounded after training
    Section 4.1 concludes O(N) and O(1) based on these being constants; valid for a single frozen model.
  • 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
    This is the unstated premise behind 'amortized O(1)' in Section 1 and Section 4.3. It fails for an unbounded stream because N grows each cycle.
  • domain assumption A TConstFormer block with H=2, stacked twice, has the same parameter count as an 8-layer standard Transformer
    Section 6.2.1 asserts parameter parity without parameter counts or weight-sharing details; if false, PPL comparisons are not fair.
  • domain assumption The compressed-sensing guideline n > C log N justifies a small history window
    Section 7 invokes refs [3,1] to argue a window of about 134 tokens can encode 10^7 tokens; this is an empirical heuristic, not a guarantee for language.

how reviews work

0 comments
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 reproduced from arXiv: 2509.00202 by the authors.

Figure 1
Figure 1. By removing the connections between x1, x2, x3 and h11, h12 in TLinFormer, we obtain the TConstFormer architecture. 3 TConstFormer Architecture To implement the connection structure shown in Figure 1b, we still use the same attention components as in TLinFormer, as illustrated in [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Connection diagrams for the 4 types of attention mechanisms required in this paper. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Schematic of a stacked TConstFormer network structure. [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Windowed computation schematic. Let the total input sequence length be N, the feature dimension be D, and the number of intermediate self-attention layers within a TConstFormer block be H. The model is partitioned into a window of length Woh for processing historical c…
Figure 5
Figure 5. Figure 5: Sliding window information processing flow during training. [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 6
Figure 6. Figure 6: Training efficiency comparison at different sequence lengths. The plots show the wall-clock time required for each model to complete a single epoch at training sequence lengths of 512, 1K, and 2K. 6.3.2 Validation Set PPL [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Perplexity (PPL) of each model over training epochs. [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: Inference performance and cache efficiency comparison. (a) Baseline model’s latency grows super-linearly with sequence length. (b, c) Both TLinFormer and TConstFormer demonstrate excellent scalability. Their dual-mode performance (peaks for cache miss upper bound, trou…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

11 extracted references · 9 canonical work pages

  1. [1]

    Abo-Zahhad, Aziza I

    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

  2. [2]

    Peters, and Arman Cohan

    Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The Long-Document Transformer, December 2020. arXiv:2004.05150 [cs]

  3. [3]

    Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information, September

    Emmanuel Candes, Justin Romberg, and Terence Tao. Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information, September

  4. [4]

    Rethinking Transformer Connectivity: TLinFormer, A Path to Exact, Full Context-Aware Linear Attention

    Zhongpan Tang. Rethinking Transformer Connectivity: TLinFormer, A Path to Exact, Full Context-Aware Linear Attention, August 2025. arXiv:2508.20407 [cs]

  5. [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...

  6. [6]

    Cost is D· (N− Wog)· Woh

    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. [7]

    Cost is ( H + 1)· D· Wog· Woh

    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. [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
  1. [9]

    Computational Cost of the Left Window (Historical Context) : Cleft = 0

  2. [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...

  3. [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

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.