Conceptio › Archive › arXiv CS

arXiv CSopen access

The Impossibility Triangle of Long-Context Modeling

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

knowledge-representation reasoning

artificial intelligence, reasoning, knowledge representation

Journal of Machine Learning Research (2026) 1-41

Submitted ; Published

The Impossibility Triangle of Long-Context Modeling Yan Zhou

[email protected]

School of Mathematics and Statistics Changsha University of Science and Technology Changsha, Hunan 410114, China

arXiv:2605.05066v1 [cs.CL] 6 May 2026

Editor:

Abstract We identify and prove a fundamental trade-off governing long-sequence models: no model can simultaneously achieve (i) per-step computation independent of sequence length (E, Efficiency), (ii) state size independent of sequence length (C, Compactness), and (iii) the ability to recall a number of historical facts proportional to sequence length (R, Recall). We formalize this trade-off within an Online Sequence Processor abstraction that unifies Transformers, state space models, linear recurrent networks, and their hybrids. Using the Data Processing Inequality and Fano’s Inequality, we prove that any model satisfying E and C can recall at most O(poly(d)/ log V ) key-value pairs from a sequence of arbitrary length, where d is the model dimension and V is the vocabulary size. We classify 52 architectures published before March 2026 into the triangle, showing that each achieves at most two of the three properties and that hybrid architectures trace continuous trajectories in the interior. Experiments on synthetic associative recall tasks with five representative architectures validate the theoretical bound: empirical recall capacity lies strictly below the information-theoretic limit, and no architecture escapes the triangle. Keywords: impossibility theorem, long-context modeling, state space models, linear attention, information theory

1 Introduction Modeling long sequences is a central challenge in modern machine learning. Since the introduction of the Transformer (Vaswani et al., 2017), a large body of work has sought architectures that can process sequences of tens or hundreds of thousands of tokens efficiently. State space models (Gu et al., 2021; Gu and Dao, 2023), linear recurrent networks (Katharopoulos et al., 2020; Peng et al., 2023a; Sun et al., 2024b; Yang et al., 2023), and memory-augmented systems (Wu et al., 2022; Behrouz et al., 2024) have each addressed different aspects of this problem. As of early 2026, more than fifty distinct architectures have been proposed, many achieving strong empirical results on language modeling, longdocument understanding, or long-range synthetic benchmarks. Despite this progress, a basic question remains unanswered: why does no single architecture simultaneously deliver fast per-step inference, small memory footprint, and accurate retrieval of arbitrary historical information? Practitioners have long observed that Transformers with KV-caches excel at recall but consume memory proportional to sequence length; that Mamba and RWKV maintain compact fixed-size states but struggle with finegrained retrieval at long range; and that hybrid architectures interpolate between these ©2026 Yan Zhou. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v/.html.

Zhou

extremes without fully resolving the tension. These observations suggest the existence of a structural limitation, but no formal statement or proof has appeared in the literature. This paper fills this gap. We prove that the three desiderata—Efficiency (E), Compactness (C), and Recall (R)—form an impossibility triangle: any two can be achieved simultaneously, but all three cannot. The proof is information-theoretic and unconditional: it makes no assumptions about the architecture’s internal structure beyond causality and numerical stability. We make four contributions. First, we introduce the Online Sequence Processor (OSP) abstraction, a seven-tuple that unifies autoregressive Transformers, state space models, linear recurrent networks, and their hybrids under a single formalism, and we give rigorous definitions of E, C, and R within this abstraction (Section 3). Second, we prove the impossibility theorem and a quantitative recall bound using the Data Processing Inequality and Fano’s Inequality, and we extend the result to continuous-state systems via a Lipschitz stability argument (Section 4). Third, we systematically classify 52 architectures published before March 2026 into the triangle, providing for each a rigorous analysis of which properties it satisfies and which it necessarily violates (Section 5). Fourth, we validate the theoretical bound through five experiments on synthetic associative recall tasks, confirming that empirical recall capacity lies strictly below the information-theoretic limit and that hybrid architectures trace continuous trajectories inside the triangle (Section 7). The structure of the paper follows the contributions above. Section 2 discusses related work. Section 3 introduces the formal framework. Section 4 states and proves the impossibility theorem. Section 5 classifies 52 architectures. Section 6 analyzes the quantitative trade-off surface. Section 7 presents experimental validation. Section 8 discusses implications, limitations, and open problems. Section 9 concludes. Appendix A contains detailed proofs; Appendix B provides per-architecture analysis; Appendix C gives experimental details.

2 Related Work Long-sequence architectures. The Transformer (Vaswani et al., 2017) established softmax attention as the dominant sequence-mixing mechanism, achieving strong recall through direct access to all past tokens via the KV-cache. Subsequent work reduced the quadratic training cost through sparse patterns (Child et al., 2019; Beltagy et al., 2020; Zaheer et al., 2020; Kitaev et al., 2020), locality-sensitive hashing (Kitaev et al., 2020), kernel approximations (Katharopoulos et al., 2020; Krzysztof et al., 2021; Qin et al., 2022), and hardwareaware exact implementations (Dao et al., 2022; Dao, 2023; Shah et al., 2024). A parallel line introduced structured state space models (Gu et al., 2021, 2022; Gupta et al., 2022; Smith et al.; Fu et al., 2022; Poli et al., 2023a), culminating in the selective SSM of Mamba (Gu and Dao, 2023) and its successors (Dao and Gu, 2024; Lahoti et al., 2026). Linear recurrent networks with data-dependent gating (Peng et al., 2023a, 2024, 2025; Sun et al., 2024b; Yang et al., 2023; Qin et al., 2024; Yang et al., 2024b,a; Feng et al., 2024; Beck et al., 2024; Ma et al., 2022, 2024) further extended this family. Memory-augmented models (Wu et al., 2022; Martins et al., 2022; Munkhdalai et al., 2024; Behrouz et al., 2024; Sun et al., 2024a) and hybrid architectures combining SSM layers with attention layers (Lieber et al., 2024; Glorioso et al., 2024b; De et al., 2024; Ren et al., 2024; Poli et al., 2023b; Blakeman 2

Impossibility Triangle of Long-Context Modeling

et al., 2025; Li et al., 2025; Glorioso et al., 2024a) represent the most recent developments. Engineering methods for extending context length without architectural change (Liu et al., 2023; Peng et al., 2023b; Xiao et al., 2023; Han et al., 2024; Jin et al., 2024; Yuan et al., 2025) complement these architectural efforts. Section 5 provides a detailed classification of all these architectures. Theoretical analysis of sequence models. Arora et al. (2024) empirically identified and quantified the recall–throughput trade-off in linear attention models, providing the closest precedent to the present work. Their BASED architecture explicitly explores the Pareto frontier between recall accuracy and generation throughput, but does not prove a formal impossibility result. Circuit-complexity analyses have shown that Transformers belong to the complexity class TC0 under standard assumptions, while certain recurrent models can recognize all regular languages (Peng et al., 2025). These results address expressive power rather than the resource trade-off studied here. The duality between SSMs and structured attention was formalized by Dao and Gu (2024), who showed that Mamba-2 layers correspond to multiplication by structured semiseparable matrices; this duality is structural rather than impossibility-theoretic. Information-theoretic tools in machine learning. The Data Processing Inequality and Fano’s Inequality (Cover, 1999) are standard tools in communication theory and have been applied to prove minimax lower bounds in statistics and learning theory. Their use in analyzing the memory capacity of sequence models appears to be novel. Impossibility theorems in computer science and mathematics. Our result is analogous in spirit to several classical impossibility theorems. The CAP theorem (Brewer, 2000; Gilbert and Lynch, 2002) states that a distributed data store cannot simultaneously guarantee consistency, availability, and partition tolerance. The FLP impossibility (Fischer et al., 1985) shows that deterministic consensus is impossible in an asynchronous network with even one faulty process. Arrow’s impossibility theorem (Arrow, 2012) proves that no rankorder voting system can satisfy a small set of fairness axioms simultaneously. Each of these results identifies three desirable properties and proves that at most two can coexist. Our theorem follows the same tripartite structure, with E, C, and R playing the roles of the three conflicting desiderata. The proof technique is different: we use information theory rather than combinatorics or asynchronous computation models.

3 Formal Framework This section introduces the computational abstraction (Section 3.1), the canonical evaluation task (Section 3.2), and the three properties whose mutual incompatibility we prove (Section 3.3). Table 1 at the end of this section collects all symbols. 3.1 Online Sequence Processor We model any causal sequence model as an online system that maintains a state, updates it token by token, and answers queries from that state.

Zhou

Definition 1 (Online Sequence Processor) An Online Sequence Processor (OSP) is a seven-tuple P = (S, X , Q, A, δ, ρ, s0 ), where X is a finite input alphabet with |X | = V , called the vocabulary size; Q and A are the query space and answer space; S is a measurable state space; s0 ∈ S is the initial state; δ : S × X → S is the state transition function; and ρ : S × Q → ∆(A) is the readout function, where ∆(A) denotes the simplex of probability distributions over A. Given an input sequence x = (x1 , x2 , . . . , xT ) ∈ X T of length T , the state evolves as st = δ(st−1 , xt ),

t = 1, 2, . . . , T.

(1)

The OSP answers a query q ∈ Q after processing the full sequence by sampling from ρ(sT , q). The is deliberately broad. A Transformer with KV-cache corresponds to S∞ abstraction t d kv S = t=0 (R ) , where the state st = {(ki , vi )}ti=1 is the set of all past key-value pairs and grows with t. A recurrent model such as Mamba (Gu and Dao, 2023) corresponds to S = RN ×d with fixed dimensions N and d, and the transition takes the form st = Āt ⊙st−1 + B̄t xt . Both instantiations satisfy Definition 1. Two axioms constrain the class of OSPs we consider. Axiom 2 (Causality) The state st is a deterministic function of (s0 , x1 , . . . , xt ) alone. Equivalently, st is conditionally independent of future tokens (xt+1 , . . . , xT ) given the past. Axiom 2 restricts attention to causal (autoregressive) models, which is the standard setting for language model inference. Every decoder-only Transformer, every unidirectional RNN, and every causal SSM satisfies this axiom. Axiom 3 (Numerical Stability) When S ⊆ Rd , the transition function δ is L-Lipschitz: for all s, s′ ∈ S and all x ∈ X , ∥δ(s, x) − δ(s′ , x)∥ ≤ L · ∥s − s′ ∥,

(2)

where L is polynomial in the model dimension d. Axiom 3 excludes pathological constructions in which a single real-valued component encodes unbounded information via infinite-precision arithmetic. Any model implemented in b-bit floating-point satisfies this axiom with L depending on the weight magnitudes and nonlinearities. 3.2 Associative Recall Task To measure an OSP’s ability to retrieve fine-grained historical information, we use a canonical synthetic task that abstracts the “needle-in-a-haystack” evaluation.1 Definition 4 (Associative Recall) The associative recall task AR(n, V ) with n key-value pairs over vocabulary size V proceeds as follows: 1. The needle-in-a-haystack protocol was introduced as a practical LLM benchmark by Greg Kamradt in 2023; see https://github.com/gkamradt/LLMTest_NeedleInAHaystack.

Impossibility Triangle of Long-Context Modeling

(i) Sample n distinct keys k1 , . . . , kn uniformly without replacement from X . (ii) Sample n values v1 , . . . , vn independently and uniformly from X . (iii) Construct a sequence of length T ≥ 3n + 2 by interleaving the key-value pairs with filler tokens drawn uniformly from X . Each pair (ki , vi ) is preceded by a distinguished key marker token. (iv) Append a distinguished query marker token followed by kj , where j ∼ Uniform([n]). (v) The model must output vj . The information content of a correct answer is log2 V bits. Storing all n pairs requires at least n log2 V bits. The task isolates the recall capability from other aspects of language modeling such as syntax or world knowledge: success requires the model to have retained the specific binding between the queried key and its value across the full sequence length. 3.3 Three Desiderata We define three properties that correspond to distinct computational resources: time (E), space (C), and information (R). Definition 5 (Efficiency E) An OSP P satisfies Efficiency, written E, if there exists a polynomial p, independent of T , such that for all t ≤ T , Cost δ(st−1 , xt ) ≤ p(d), (3) where Cost(·) counts arithmetic operations (FLOPs) and d is the model dimension. Definition 5 requires that the cost of processing a single token does not grow with the number of tokens already processed. Models whose per-step cost is O(d2 ) or O(N d) with fixed state dimension N —such as Mamba (Gu and Dao, 2023), RetNet (Sun et al., 2024b), and GLA (Yang et al., 2023)—satisfy E. A standard autoregressive Transformer, whose attention computation at step t requires reading all t past key-value pairs at cost O(t · d), does not. Definition 6 (Compactness C) An OSP P satisfies Compactness, written C, if there exists a polynomial q, independent of T , such that for all t ≤ T , |st |bits ≤ q(d),

(4)

where |st |bits denotes the minimum description length of the state st in bits. Definition 6 requires that the memory footprint of the model’s state does not grow with sequence length. A fixed-size recurrent state st ∈ RN ×d with b-bit components has |st |bits = N · d · b, which is independent of T and satisfies C. A KV-cache storing all past tokens, with |st |bits = t · d · b, grows linearly in t and does not satisfy C. Definition 7 ((α, n)-Recall R) An OSP P satisfies R(α, n) on task AR(n, V ) if for every i ∈ [n], Pr ρ(sT , ki ) = vi ≥ α, (5) where the probability is over the random construction of the sequence in Definition 4. 5

Zhou

Definition 8 (Strong Recall) An OSP has strong recall if there exist constants γ > 0 and ε ∈ (0, 1 − 1/V ) such that P satisfies R(1 − ε, γT ) for all sufficiently large T . Strong recall (Definition 8) requires that the number of accurately retrievable key-value pairs grows proportionally to the sequence length. The condition ε < 1 − 1/V ensures that the recall accuracy exceeds the trivial baseline of uniform random guessing, which achieves accuracy 1/V . This is the demanding form of recall whose incompatibility with E and C we establish in Section 4. Remark 9 The three properties address orthogonal resources. E bounds computation per step (time), C bounds state size (space), and R bounds retrievable information (knowledge). As we show in Section 4.4, any pair of the three is achievable by an explicit construction; the impossibility is strictly tripartite. 3.4 Summary of Notation Table 1 collects all symbols used in the paper. Each symbol is introduced at a single point and used consistently thereafter. Table 1: Summary of notation. “Ref.” indicates the definition, axiom, equation, or section where each symbol is introduced. Symbol

Type

OSP components P tuple S set X set Q set A set ∆(A) set δ function ρ function s0 element st element

Meaning

Ref.

Online Sequence Processor State space Input alphabet (vocabulary) Query space Answer space Probability simplex over A State transition: S × X → S Readout: S × Q → ∆(A) Initial state (s0 ∈ S) State after processing tokens x1 , . . . , xt

Def. 1 Def. 1 Def. 1 Def. 1 Def. 1 Def. 1 Def. 1 Def. 1 Def. 1 Eq. (1)

Dimensional and precision quantities V integer Vocabulary size (V = |X |) d integer Model dimension (embedding width) T integer Sequence length N integer SSM state dimension (architecture-dependent) b integer Floating-point precision (bits per component) L real ≥ 0 Lipschitz constant of δ dh integer Attention head dimension (dh = d/nheads ) dk , d v integer Key and value dimensions in unified recurrence m integer Feature dimension in kernel approximation dc integer Latent compression dimension (MLA) Architectural quantities nlayers integer

Total number of layers

Def. 1 Def. 5 Eq. (1) Sec. 3.1 Thm. 14 Ax. 3 Sec. 7.1 Eq. (16) App. B.2 App. B.1 Prop. 17

Impossibility Triangle of Long-Context Modeling

Table 1: Summary of notation (continued). Symbol

Type

Meaning

Ref.

nheads |θ|

integer integer

Sec. 7.1 App. B.6

|W |

integer

nattn nssm nswa rattn

integer integer integer real ∈ [0, 1] integer

Number of attention heads per layer Number of parameters in neural memory (Titans) Number of parameters in test-time-trained memory (TTT) Number of global attention layers (hybrid) Number of SSM layers (hybrid) Number of sliding-window attention layers Fraction of attention layers in hybrid Sliding-window size (local attention)

Prop. 21

Associative recall with n pairs, vocabulary V Number of key-value pairs i-th key (ki ∈ X ) i-th value (vi ∈ X ) Model’s output for query ki : v̂i ∼ ρ(sT , ki ) (v1 , . . . , vn ) Input sequence (x1 , . . . , xT ) {1, 2, . . . , n}

Def. 4 Def. 4 Def. 4 Def. 4 Sec. 4.2 Sec. 4.2 Sec. 3.1 Def. 7

Efficiency: per-step cost ≤ p(d) Compactness: state size ≤ q(d) bits Recall: accuracy ≥ α on n pairs Recall accuracy threshold

Def. 5 Def. 6 Def. 7 Def. 7

Error tolerance (α = 1 − ε)

Def. 8

Recall scaling constant (n ≥ γT ) Max pairs recallable at accuracy ≥ 1 − ε Bound in E definition Bound in C definition

Def. 8 Thm. 10 Def. 5 Def. 6

Associative recall task AR(n, V ) task n integer ki element vi element v̂i element v vector x vector [n] set Three properties E property C property R(α, n) property α real ∈ (0, 1] ε real ∈ (0, 1) γ real > 0 n∗ integer p(·) polynomial q(·) polynomial

Unified recurrence (Section 5.1) St matrix Recurrent state matrix (St ∈ Rdk ×dv ) Gt tensor Gating tensor (controls forgetting) Ut function Update function (controls writing) Read function Query-dependent readout ⊙ operator Hadamard (elementwise) product ⊗ operator Outer product ECR profile (Section 6) e real ∈ [0, 1] c real ∈ [0, 1] r real ∈ [0, 1]

App. B.6 Eq. (18) Eq. (18) Prop. 21 Sec. 5.4

Eq. (16) Eq. (16) Eq. (16) Eq. (16) Eq. (16) Table 3

Normalized efficiency loss

Def. 22

Normalized compactness loss

Def. 22

Normalized recall ratio (n∗ /T )

Def. 22

Information-theoretic quantities H(X) real ≥ 0 Shannon entropy of random variable X I(X; Y ) real ≥ 0 Mutual information between X and Y

Lem. 11 Lem. 11

Zhou

Table 1: Summary of notation (continued). Symbol

Type

Meaning

Ref.

h(ε) |s|bits

real ≥ 0 real ≥ 0

Binary entropy: −ε log2 ε − (1−ε) log2 (1−ε) Minimum description length of state s in bits

Lem. 12 Def. 6

Attention mechanism (Appendix B) WQ , WK , WV matrix Query, key, value projection matrices αti real Attention weight from position t to i ∈ [0, 1] ϕ function Kernel feature map (linear attention) σ function Sigmoid function Cost and asymptotics Cost(·) real ≥ 0 O(·)

Arithmetic operation count (FLOPs) Asymptotic upper bound

Eq. (35) Eq. (36) Eq. (38) Table 3 Def. 5 —

4 The Impossibility Theorem This section states and proves the main result. Section 4.1 gives the theorem and a quantitative recall bound. Section 4.2 presents the proof. Section 4.3 extends the result to continuous-state systems. Section 4.4 establishes that each pair of properties is individually attainable. 4.1 Statement Theorem 10 (Impossibility Triangle) Let P = (S, X , Q, A, δ, ρ, s0 ) be an OSP satisfying Axioms 2 and 3, with vocabulary size V = |X | ≥ 2. There is no P that simultaneously satisfies all three of the following: (i) Efficiency E: Cost(δ(st−1 , xt )) ≤ p(d) for a polynomial p independent of T ; (ii) Compactness C: |st |bits ≤ q(d) for a polynomial q independent of T ; (iii) Strong Recall R: there exist γ > 0 and ε ∈ (0, 1 − 1/V ) such that R(1 − ε, γT ) holds for all sufficiently large T . Moreover, any P satisfying (i) and (ii) can recall at most n∗ ≤

q(d) (1 − ε) log2 V − 1

(6)

key-value pairs at accuracy 1 − ε. Since q(d) is independent of T , this implies n∗ = O(poly(d)/ log V ) = o(T ) as T → ∞, contradicting (iii). 4.2 Proof The proof has three steps. Step 1 bounds the information that the state can carry about the input. Step 2 bounds the information that successful recall demands. Step 3 combines the two bounds. We first recall two classical results. Lemma 11 (Data Processing Inequality (Cover, 1999, Theorem 2.8.1)) If random variables X, Y , Z form a Markov chain X → Y → Z, then I(X; Z) ≤ I(X; Y ). 8

Impossibility Triangle of Long-Context Modeling

Lemma 12 (Fano’s Inequality (Cover, 1999, Theorem 2.10.1)) Let X be a random variable taking values in a finite set V with |V| = V , and let X̂ be an estimate satisfying Pr[X̂ = X] ≥ 1 − ε. Then I(X; X̂) ≥ (1 − ε) log2 V − h(ε),

(7)

where h(ε) = −ε log2 ε − (1 − ε) log2 (1 − ε) ≤ 1 is the binary entropy function. Proof [Proof of Theorem 10] Fix an instance of AR(n, V ) as in Definition 4. Let v = (v1 , . . . , vn ) denote the n values, each drawn independently and uniformly from X . Let sT denote the state after processing the full sequence of length T , and let v̂i = ρ(sT , ki ) denote the model’s output when queried with key ki . Step 1: information upper bound. By Axiom 2, sT is a deterministic function of the input sequence x. The values v determine part of x, and each output v̂i is produced from sT and ki alone. For each i ∈ [n], the chain vi → x → sT → v̂i

(8)

is Markov. Applying Lemma 11 to v → x → sT and using the standard bound I(X; Y ) ≤ H(Y ) ≤ |Y |bits , we obtain I(v; sT ) ≤ H(sT ) ≤ |sT |bits ≤ q(d),

(9)

where the last inequality is condition (ii). Step 2: information lower bound. By condition (iii), Pr[v̂i = vi ] ≥ 1 − ε for each i. Applying Lemma 12 and using h(ε) ≤ 1, I(vi ; v̂i ) ≥ (1 − ε) log2 V − 1.

(10)

Since v̂i is a function of (sT , ki ), the data processing inequality gives I(vi ; sT ) ≥ I(vi ; v̂i ). Combining with (10), I(vi ; sT ) ≥ (1 − ε) log2 V − 1. (11) The values v1 , . . . , vn are mutually independent by construction (Definition 4, item (ii)). By the chain rule for mutual information, I(v; sT ) =

n X

I(vi ; sT | v1 , . . . , vi−1 ).

(12)

i=1

We claim that I(vi ; sT | v1 , . . . , vi−1 ) ≥ I(vi ; sT ) for each i. To see this, note that by the chain rule applied in a different order, I(vi ; sT , v1 , . . . , vi−1 ) = I(vi ; v1 , . . . , vi−1 ) + I(vi ; sT | v1 , . . . , vi−1 ), | {z } = 0 (independence)

so I(vi ; sT | v1 , . . . , vi−1 ) = I(vi ; sT , v1 , . . . , vi−1 ) ≥ I(vi ; sT ), where the inequality holds because (sT , v1 , . . . , vi−1 ) contains sT as a component. Substituting into (12) and using (11), I(v; sT ) ≥

n X

I(vi ; sT ) ≥ n (1 − ε) log2 V − 1 .

i=1

(13)

Zhou

Step 3: combining the bounds.

Inequalities (9) and (13) together give

n (1 − ε) log2 V − 1 ≤ q(d).

(14)

The coefficient (1−ε) log2 V −1 is strictly positive because ε < 1−1/V implies (1−ε) > 1/V , hence (1 − ε) log2 V > (log2 V )/V ≥ (log2 2)/2 = 1/2 > 0 for V ≥ 2, and for any V ≥ 4 (which includes all practical vocabulary sizes) we have (1 − ε) log2 V > 1. Rearranging (14) yields the bound (6). Since q(d) is independent of T , the right-hand side is O(poly(d)/ log V ), which is o(T ). Strong recall requires n ≥ γT , so for T > q(d)/[γ((1 − ε) log2 V − 1)] the requirement is violated.

Remark 13 The bound (6) reflects a fundamental information-theoretic limit rather than an artifact of the proof technique. A state of q(d) bits can encode at most q(d)/ log2 V independent symbols from an alphabet of size V ; the factor (1 − ε) accounts for approximate recall. The bound is achievable in an order-of-magnitude sense by a dictionary that stores as many key-value pairs as its bit budget allows. 4.3 Extension to Continuous States Theorem 10 uses the minimum description length |st |bits . For discrete or finite-precision states, this is well defined. For continuous states st ∈ Rd with b-bit components, |st |bits = d · b. One might ask whether infinite-precision arithmetic could circumvent the bound. Axiom 3 rules this out. Theorem 14 (Lipschitz Capacity Bound) Let P have state space S = Rd with b-bit precision per component, and let the transition function be L-Lipschitz (Axiom 3). Then n∗ ≤

d · b + d · T · log2 L . (1 − ε) log2 V − 1

(15)

Proof With L-Lipschitz transitions and initial precision b bits per component, a perturbation of magnitude 2−b in the initial state grows to at most LT · 2−b after T steps. Equivalently, the effective precision after T steps is at most b + T log2 L bits per component (De et al., 2024). The total information capacity of the state is therefore bounded by d(b+T log2 L) bits. Replacing q(d) in the proof of Theorem 10 with this capacity yields (15).

Remark 15 When L ≤ 1 (contractive dynamics, typical of stable SSMs with eigenvalues |λi | < 1), the capacity is at most d · b bits and does not grow with T ; information decays exponentially. When L > 1 (expansive dynamics), the capacity grows linearly in T , but the system amplifies perturbations exponentially, rendering it numerically unstable. The stable regime L ≤ 1 and compactness together enforce the information bottleneck that drives the impossibility. 10

Impossibility Triangle of Long-Context Modeling

Table 2: The impossibility triangle. Each row shows a combination of properties. The first three rows are achievable (Theorem 16); the last is not (Theorem 10). E

Achievable?

✓ ✓ × ✓

✓ × ✓ ✓

× ✓ ✓ ✓

Yes Yes Yes No

Representative architectures Mamba, RetNet, GLA, RWKV, xLSTM KV-cache Transformer, Memorizing Tr. Re-computation models —

4.4 Achievability We now show that the impossibility is tight: each pair of properties is achievable by an explicit construction. This confirms that the constraint is genuinely tripartite. Theorem 16 (Achievability) Each of the following pairs is constructively achievable: (a) E ∧ C: achieved by any stable linear state space model ; (b) E ∧ R: achieved by a KV-cache Transformer with sub-linear retrieval ; (c) C ∧ R: achieved by a re-computation model. Proof (a) Consider a linear SSM with transition st = Ā st−1 + B̄ xt and readout yt = C st , where Ā ∈ RN ×N , B̄ ∈ RN ×d , and C ∈ Rd×N are fixed matrices. The per-step cost is O(N · d), independent of T , satisfying E. The state st ∈ RN has |st |bits = N · b, independent of T , satisfying C. By Theorem 10, the recall capacity is n∗ ≤ O(N · b/ log V ), which does not grow with T ; strong R is violated. Architectures in this category include Mamba (Gu and Dao, 2023), RetNet (Sun et al., 2024b), RWKV (Peng et al., 2023a), and GLA (Yang et al., 2023). (b) Consider a Transformer that stores all past key-value pairs st = {(ki , vi )}ti=1 and retrieves via exact attention or approximate nearest-neighbor search. Per-step insertion costs O(d); per-step attention or retrieval costs O(d log t) with appropriate data structures. This satisfies E in an amortized sense (cost grows at most logarithmically). Recall is nearperfect by construction (R satisfied). However, |st |bits = t · d · b, which grows linearly in t; C is violated. Architectures in this category include the standard Transformer (Vaswani et al., 2017) and the Memorizing Transformer (Wu et al., 2022). (c) Consider a model that maintains a compressed summary of fixed size O(d) bits but, upon receiving a query, re-scans the full input sequence (assumed accessible from external storage not counted as state). The summary satisfies C. Re-scanning yields perfect recall (R satisfied). However, re-scanning costs O(T · d) per query; E is violated. Table 2 summarizes the achievability results alongside the main impossibility.

5 Taxonomy: Classifying All Architectures We now classify 52 architectures published before March 2026 into the impossibility triangle. For each architecture, we identify which of the three properties it satisfies and verify consistency with Theorem 10. Section 5.1 introduces a unified recurrence that encompasses 11

Zhou

Table 3: Instantiations of the unified recurrence (16) for representative fixed-state architectures. All satisfy E and C; none achieves strong R (Theorem 10). Notation: I denotes the identity, γ a scalar decay, σ the sigmoid function, ⊙ elementwise product, ⊗ outer product. Architecture

Gate Gt

Update Ut

Linear Transformer RetNet GLA Mamba (S6) DeltaNet xLSTM (mLSTM) RWKV-7

I (no decay) γI (scalar decay) diag(σ(wt )) (data-dep.) diag(exp(∆t A)) I − βt kt kt⊤ ft · I (exp. gate) vector-valued gate

kt ⊗ v t kt ⊗ v t kt ⊗ vt ∆ t Bt ⊗ x t βt vt ⊗ k t i t · vt ⊗ kt generalized delta rule

all fixed-state models. Sections 5.2–5.5 classify architectures by region. Section 5.6 presents the complete classification table. 5.1 Unified Recurrence for Fixed-State Models All fixed-state models in our taxonomy—SSMs, linear RNNs, gated linear attention variants, and extended LSTMs—can be expressed in a single canonical form: St = Gt ⊙ St−1 + Ut (kt , vt , St−1 ),

yt = Read(qt , St ),

(16)

where St ∈ Rdk ×dv is the recurrent state matrix, Gt is a gating tensor controlling forgetting, Ut is an update function controlling writing, and Read is a query-dependent readout. Table 3 shows how specific architectures instantiate these components. The unified form makes explicit that all these architectures compress the full history into a matrix St of fixed dimensions. By Theorem 10, the recall capacity is bounded by n∗ ≤ |St |bits /[(1 − ε) log2 V − 1], regardless of how Gt and Ut are parameterized. The architectures differ in how efficiently they utilize the available state bits—GLA and DeltaNet achieve higher empirical n∗ than the Linear Transformer, for instance—but none can exceed the information-theoretic ceiling. 5.2 Region R: Full-Attention Architectures Architectures in this region maintain a state whose size grows with T , enabling accurate recall at the cost of violating E and/or C. Proposition 17 The Transformer with KV-cache (Vaswani et al., 2017) satisfies R but violates both E and C. Proof The state at step t is st = {(ki , vi )}ti=1 , so |st |bits = t · 2 · d · nlayers · b, which grows linearly in t (C violated). Computing attention at step t requires reading all t past key-value pairs, costing O(t · d) (E violated). Recall is achieved by direct content-based addressing over the full history (R satisfied).

Impossibility Triangle of Long-Context Modeling

The same analysis applies, with minor modifications to the constant factors, to MultiQuery Attention (Shazeer, 2019), Grouped-Query Attention (Ainslie et al., 2023), and Multi-Latent Attention (Liu et al., 2024). These variants reduce the KV-cache size by constant factors (sharing heads or compressing to lower-dimensional latents) but do not change the asymptotic dependence on T . FlashAttention (Dao et al., 2022; Dao, 2023; Shah et al., 2024) is an implementation optimization that reduces memory access cost but does not alter the algorithmic complexity; it computes exact softmax attention and therefore inherits the same classification. Ring Attention (Liu et al., 2023) distributes the KV-cache across devices but does not reduce its total size. The Memorizing Transformer (Wu et al., 2022) augments a standard Transformer with external kNN memory, storing all past representations; the external memory grows with T , violating C. 5.3 Region E ∧ C: Fixed-State Models Architectures in this region maintain a state of fixed size, enabling constant-cost inference at the expense of limited recall. We organize them into four sub-families. State space models. S4 (Gu et al., 2021), S4D (Gu et al., 2022), DSS (Gupta et al., 2022), and S5 (Smith et al.) introduced structured linear recurrences with HiPPO-based initialization for long-range modeling. H3 (Fu et al., 2022) augmented the SSM with gating for language modeling. Hyena (Poli et al., 2023a) replaced the parametric state matrix with implicit long convolutions. Mamba (Gu and Dao, 2023) introduced input-dependent (selective) parameters Āt , B̄t , Ct , significantly improving recall within the fixed-state constraint. Mamba-2 (Dao and Gu, 2024) reformulated the computation as structured semiseparable matrix multiplication for hardware efficiency. Mamba-3 (Lahoti et al., 2026) further improved state tracking through complex-valued states and MIMO formulations. All these models satisfy E and C: the per-step cost is O(N · d) and the state size is N · d · b bits, both independent of T . Proposition 18 For any SSM with state dimension N , model dimension d, and b-bit precision, the recall capacity on AR(n, V ) satisfies n∗ ≤

N · d · b · nlayers . (1 − ε) log2 V − 1

(17)

This follows directly from Theorem 10 by substituting q(d) = N · d · b · nlayers . For typical values (N = 16, d = 64, b = 32, nlayers = 2, V = 32), the bound gives n∗ ≤ 18,724, which far exceeds practical recall at these dimensions but becomes the binding constraint as T grows. Linear RNNs and gated linear attention. The Linear Transformer (Katharopoulos et al., 2020) and Performer (Krzysztof et al., 2021) linearize attention by removing the softmax, accumulating key-value outer products in a fixed matrix St ∈ Rdk ×dv . cosFormer (Qin et al., 2022) uses a cosine kernel. RetNet (Sun et al., 2024b) adds exponential decay. GLA (Yang et al., 2023) introduces data-dependent gating. HGRN2 (Qin et al., 2024) adds hierarchical gating with state expansion. DeltaNet (Yang et al., 2024b) and Gated DeltaNet (Yang et al., 2024a) use the delta rule for associative memory updates. RWKV4 (Peng et al., 2023a), RWKV-5/6 (Peng et al., 2024), and RWKV-7 (Peng et al., 2025) 13

Zhou

progressively introduced matrix-valued states, dynamic recurrence, and vector-valued gating. Kimi Linear (Team et al., 2025) extends delta attention to large-scale deployment. MinGRU/MinLSTM (Feng et al., 2024) demonstrate that minimal gated RNNs suffice for parallelizable training. Gated Slot Attention (Zhang et al., 2024) uses a fixed number of memory slots with gated read-write. All satisfy E and C with state size O(d2 ) bits per layer, and all are subject to the bound (6). Extended LSTM variants. xLSTM (Beck et al., 2024) introduces exponential gating (sLSTM) and matrix-valued memory (mLSTM). The mLSTM variant maintains a matrix state Ct ∈ Rd×d updated via Ct = ft Ct−1 + it (vt ⊗ kt ), which is an instance of the unified recurrence (16) with exponential gates. MEGA (Ma et al., 2022) combines exponential moving averages with gated attention. MEGALODON (Ma et al., 2024) extends this to complex-valued EMA with normalization for large-scale pretraining. All satisfy E and C; their recall capacity is governed by the same information-theoretic bound. Sparse and local attention. Longformer (Beltagy et al., 2020), BigBird (Zaheer et al., 2020), StreamingLLM (Xiao et al., 2023), and LM-Infinite (Han et al., 2024) restrict attention to a fixed-size local window (plus a small number of global tokens or attention sinks). When the window size w is fixed, the effective state is O(w · d) bits and the per-step cost is O(w · d), both independent of T . These models satisfy E and C but sacrifice R: information outside the window is discarded or accessible only through compressed representations. Memory-augmented models with fixed-size memory. The ∞-former (Martins et al., 2022) maintains a continuous long-term memory of fixed size. Infini-Attention (Munkhdalai et al., 2024) combines local softmax attention with a compressive memory updated via linear attention; the compressive memory is a fixed-size matrix Mt ∈ Rdk ×dv . Titans (Behrouz et al., 2024) uses a test-time-trainable neural network as memory, with the network parameters θt serving as the fixed-size state updated by gradient descent at each step. TTTLinear/MLP (Sun et al., 2024a) similarly treats the hidden state as a learnable model updated via self-supervised loss at inference time. All four maintain states of fixed size (C satisfied) and update them in constant time (E satisfied). Despite their sophisticated update rules, the information-theoretic bound of Theorem 10 applies to all: the neural memory parameters θt contain |θ| scalar values at b-bit precision, yielding |θ| · b bits of total capacity, which bounds n∗ independently of T . Remark 19 Titans and TTT have been described in some prior work as achieving all three properties simultaneously. This characterization is imprecise. While these models improve the empirical utilization of state capacity—for instance, TTT continues to reduce perplexity with increasing context length where Mamba saturates (Sun et al., 2024a)—their fixed-size state imposes the same asymptotic recall ceiling as any other E ∧ C architecture. The distinction between “better utilization of bounded capacity” and “unbounded capacity” is precisely the content of Theorem 10. 5.4 Interior of the Triangle: Hybrid Architectures Hybrid architectures interleave fixed-state layers (SSM or linear RNN) with attention layers. Their position in the triangle depends on the proportion of attention layers and the type of attention used. 14

Impossibility Triangle of Long-Context Modeling

Global-attention hybrids. Jamba (Lieber et al., 2024) interleaves Mamba layers with full (global) Transformer attention layers and MoE modules, using approximately one attention layer per seven Mamba layers. Zamba (Glorioso et al., 2024b) and Zamba-2 (Glorioso et al., 2024a) use a similar strategy with shared attention blocks. StripedHyena (Poli et al., 2023b) alternates Hyena convolution layers with attention layers. Nemotron-H (Blakeman et al., 2025) replaces 92% of attention layers with Mamba-2 layers. MiniMax-01 (Li et al., 2025) combines lightning attention (a gated linear variant) with standard attention and MoE. For any hybrid with rattn > 0 fraction of global attention layers, the KV-cache of those layers grows as O(rattn · T · d). Consequently, the total state size is |sT |bits = nssm · N · d · b + | {z } SSM layers (fixed)

n ·T ·d·b | attn {z }

(18)

Attention layers (growing)

where nssm and nattn are the numbers of SSM and attention layers. When rattn > 0 and T → ∞, the second term dominates and the state grows without bound: C is violated. The per-step cost of the attention layers is O(nattn · T · d), which also grows with T : E is violated in the strict sense. However, the constant factors are reduced relative to a pure Transformer by the factor rattn , and these models achieve strong recall through their attention layers. Proposition 20 A hybrid architecture with rattn > 0 fraction of global attention layers satisfies R but violates strict E and strict C. Its effective position in the triangle interpolates between the E∧C vertex (at rattn = 0) and the R region (at rattn = 1), with state size scaling as O(rattn · T · d). Local-attention hybrids. Griffin (De et al., 2024) and its deployed variant RecurrentGemma combine a gated linear recurrence (RG-LRU) with sliding-window attention of fixed window size w. Samba (Ren et al., 2024) similarly combines Mamba layers with slidingwindow attention. For these architectures, the state size is O(N · d + w · d), which is independent of T when w is fixed. The per-step cost is O(N · d + w · d), also independent of T . These models therefore satisfy both E and C. Their recall capability exceeds that of pure SSMs because the local attention window provides exact retrieval within the most recent w tokens, but information beyond the window is accessible only through the compressed recurrent state. They do not achieve strong R in the sense of Definition 8, because the number of exactly retrievable pairs is bounded by w + n∗ssm , which does not grow with T . Proposition 21 A hybrid architecture with only sliding-window attention (window size w fixed) satisfies E and C but not strong R. Its recall capacity is bounded by n∗ ≤ w + qssm (d)/[(1 − ε) log2 V − 1], where qssm (d) is the SSM state capacity. 5.5 Engineering Methods Several methods extend the effective context length of existing architectures without modifying the underlying model. YaRN (Peng et al., 2023b) adjusts RoPE frequencies to support longer contexts. Sequence parallelism and Ring Attention (Liu et al., 2023) distribute the KV-cache across devices. Self-Extend (Jin et al., 2024) groups positions to enable zero-shot 15

Zhou

length generalization. Native Sparse Attention (Yuan et al., 2025) introduces hardwarealigned trainable sparsity patterns. These methods do not change the asymptotic complexity class of the base architecture: a Transformer with YaRN still has O(T ) state size and O(T ) per-step cost; Ring Attention distributes but does not reduce the total KV-cache. We therefore classify these methods according to their base architecture. 5.6 Complete Classification Table 4 classifies all 52 architectures into the impossibility triangle. For each architecture, we indicate the year, the category, whether it satisfies each of the three properties, and its region in the triangle. Table 4: Classification of 52 long-sequence architectures into the impossibility triangle. Symbols: ✓ = satisfied, × = violated, △ = partially satisfied (constant-factor improvement without asymptotic change). “Region” indicates the achievable pair or the interior position. Architectures are grouped by family and ordered chronologically within each group. Category

Region

Full attention (Region R, violating E and/or C) 1 Transformer / MHA 2017 2 Multi-Query Attention 2019 3 Grouped-Query Attention 2023 4 Multi-Latent Attention 2024 5 FlashAttention 1/2/3 2022–24 6 Memorizing Transformer 2022 7 Ring Attention 2023

Architecture

Year

Attention Attention Attention Attention Attention Memory Engineering

× × × × △ △ ×

× △ △ △ × × ×

✓ ✓ ✓ ✓ ✓ ✓ ✓

R R R R R R R

SSM family (Region E ∧ C) 8 S4 9 S4D / DSS 10 S5 11 H3 12 Hyena 13 Mamba (S6) 14 Mamba-2 (SSD) 15 Mamba-3

SSM SSM SSM SSM SSM SSM SSM SSM

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

× × × × × × × ×

EC EC EC EC EC EC EC EC

Linear RNN / gated linear attention (Region E ∧ C) 16 Linear Transformer 2020 17 Performer 2020 18 cosFormer 2022 19 RWKV-4 2023 20 RWKV-5/6 2024 21 RWKV-7 2025 22 RetNet 2023 23 GLA 2023 24 HGRN / HGRN2 2023–24 25 DeltaNet 2024 26 Gated DeltaNet 2025 27 Kimi Linear 2025 28 MinGRU / MinLSTM 2024 29 Gated Slot Attention 2024

Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN Linear RNN

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

× × × × × × × × × × × × × ×

EC EC EC EC EC EC EC EC EC EC EC EC EC EC

Extended LSTM / EMA variants (Region E ∧ C) 30 xLSTM (sLSTM + mLSTM) 2024 31 MEGA 2022 32 MEGALODON 2024

Ext. LSTM Ext. LSTM Ext. LSTM

✓ ✓ ✓

× × ×

EC EC EC

2021 2022 2022 2022 2023 2023 2024 2026

Sparse / local attention (Region E ∧ C)

Impossibility Triangle of Long-Context Modeling

Table 4: Classification of 52 long-sequence architectures into the impossibility triangle (continued). #

Architecture

Year

Category

Region

33 34 35 36

Longformer BigBird StreamingLLM LM-Infinite

2020 2020 2023 2023

Sparse Attn Sparse Attn Sparse Attn Sparse Attn

✓ ✓ ✓ ✓

× × × ×

EC EC EC EC

Memory-augmented, fixed state (Region E ∧ C) 37 ∞-former 2021 38 Infini-Attention 2024 39 Titans 2025 40 TTT-Linear/MLP 2024

Memory Memory Memory Memory

✓ ✓ ✓ ✓

× × × ×

EC EC EC EC

Hybrid: global attention (Interior, toward R) 41 Jamba / Jamba-1.5 2024 42 Zamba / Zamba-2 2024–25 43 StripedHyena / SH2 2023–25 44 Nemotron-H 2025 45 MiniMax-01 2025

Hybrid Hybrid Hybrid Hybrid Hybrid

△ △ △ △ △

✓ ✓ ✓ ✓ ✓

Interior Interior Interior Interior Interior

Hybrid: local attention only (Region E ∧ C, enhanced R) 46 Griffin / RecurrentGemma 2024 Hybrid 47 Samba 2024 Hybrid

✓ ✓

× ×

EC EC

(base arch.) (base arch.) (base arch.) (base arch.) (base arch.)

— — — — —

Engineering methods (inherit base architecture classification) 48 YaRN / LongRoPE 2023–25 Engineering 49 Sequence Parallelism 2021–24 Engineering 50 Landmark Attention 2023 Engineering 51 Self-Extend 2024 Engineering 52 Native Sparse Attention 2025 Engineering

Figure 1 provides a schematic visualization of the triangle with representative architectures positioned according to their classification.

6 Quantitative Trade-off Analysis Theorem 10 establishes a binary impossibility: all three properties cannot coexist. This section moves beyond the binary statement to characterize the continuous trade-off surface. We define normalized scores for each property (Section 6.1), derive a fundamental trade-off inequality (Section 6.2), and discuss the Pareto frontier (Section 6.3). 6.1 Normalized ECR Scores To compare architectures on a common scale, we define normalized scores that map each property to the interval [0, 1].

Definition 22 (ECR Profile) For an OSP P evaluated at sequence length T with vocabulary size V and model dimension d, the ECR profile is the triple (e, c, r) ∈ [0, 1]3 defined 17

Zhou

The Impossibility Triangle of Long-Sequence Models Recall

com Re-

Jamba

atio put

TraKV-Ca nsfo che rme r

Transformer

Titans/TTT

Griffin/Samba

GLA Mamba

Linear Attn

SSM / Linear RNN Mamba / RWKV / RetNet

Efficiency

Compactness

Figure 1: The impossibility triangle of long-sequence models. The three vertices represent the three desiderata: Efficiency (E), Compactness (C), and Recall (R). Each architecture is positioned according to which properties it satisfies. The center (∅) is provably unachievable (Theorem 10). SSMs and linear RNNs cluster near the E–C edge; KV-cache Transformers occupy the R vertex; hybrid architectures lie in the interior, interpolating between the extremes. by maxt≤T Cost(δ(st−1 , xt )) , T ·d maxt≤T |st |bits , c = T · log2 V · b n∗ (1 − ε) , r = T e =

(19) (20) (21)

where n∗ (1 − ε) is the maximum number of key-value pairs recallable at accuracy ≥ 1 − ε, and b is the floating-point precision. Lower e indicates better efficiency; lower c indicates better compactness; higher r indicates better recall. For a model satisfying E, e = O(1/T ) → 0 as T grows; for one violating E, e remains Θ(1) or grows. Similarly, C implies c = O(1/T ) → 0, while a KV-cache Transformer has c = Θ(1). Strong R requires r = Θ(1); fixed-state models have r = O(1/T ) → 0. 6.2 Trade-off Inequality The impossibility theorem implies a quantitative constraint on the ECR profile. 18

Impossibility Triangle of Long-Context Modeling

Theorem 23 (Trade-off Inequality) For any OSP satisfying Axioms 2 and 3, the ECR profile (e, c, r) satisfies r ≤

c · T · log2 V · b c·b = . T · [(1 − ε) log2 V − 1] (1 − ε) − 1/ log2 V

(22)

Proof By Definition 22, |sT |bits ≤ c · T · log2 V · b and n∗ = r · T . Substituting into the bound (6) from Theorem 10 gives r · T ≤ c · T · log2 V · b/[(1 − ε) log2 V − 1]. Dividing both sides by T and simplifying the denominator yields (22).

Corollary 24 The point (e, c, r) = (0, 0, r0 ) with r0 > 0 is infeasible. That is, when both efficiency loss and compactness loss approach zero, recall must also approach zero. Corollary 24 is the quantitative restatement of the impossibility: achieving perfect efficiency and perfect compactness simultaneously forces recall to vanish. 6.3 Pareto Frontier Given the trade-off inequality, a natural question is which architectures are Pareto-optimal in the (c, r) plane at a given T . An architecture is Pareto-optimal if no other architecture achieves both lower c and higher r. Our experimental results (Section 7, Figure 6) show that at any fixed T , the Transformer dominates on r but at the cost of large c, while Mamba and GLA dominate on c but with small r. Hybrid architectures and GLA with its efficient gating occupy intermediate positions on the frontier.

7 Experiments We validate the theoretical results through five experiments on the synthetic associative recall task (Definition 4). Our goal is not to benchmark production-scale models but to verify three predictions of the theory: (i) empirical recall capacity lies below the informationtheoretic bound of Theorem 10; (ii) fixed-state models exhibit r → 0 as T grows while Transformers maintain constant r; and (iii) hybrid architectures trace a continuous path inside the triangle as the attention ratio varies. 7.1 Setup Task. We use AR(n, V ) with V = 32. For each experiment, we train a separate model instance for each (n, T ) configuration, ensuring that the model is optimized for the specific recall difficulty rather than tested zero-shot. We define n∗ as the largest n for which accuracy ≥ α = 0.90. Full training and evaluation details are given in Appendix C. Architectures. We implement five architectures within the OSP framework, all with model dimension d = 64 and 2 layers: • Transformer: causal multi-head self-attention (4 heads) with learned positional embeddings and KV-cache. State size: |st |bits = T · d · nlayers · 2 · b (grows with T ). 19

Zhou

• Linear Transformer: ELU-kernel linear attention (Katharopoulos et al., 2020) with cumulative key-value outer product state St ∈ Rdk ×dv . State size: fixed at nlayers · nheads · d2h · b bits. • Mamba (N=16 and N=64): selective SSM (Gu and Dao, 2023) with inputdependent discretization. State size: fixed at nlayers · d · N · b bits. • GLA: gated linear attention (Yang et al., 2023) with data-dependent scalar gates. State size: fixed at nlayers · nheads · d2h · b bits. • Hybrid(rattn ): 4-layer model interleaving Mamba layers with causal attention layers, parameterized by the attention ratio rattn ∈ [0, 1]. All models use b = 32-bit floating-point precision. The Transformer and GLA include learned positional embeddings; Mamba includes learned positional embeddings to aid the synthetic task (standard Mamba relies on implicit positional encoding through the recurrence, which requires longer training to learn on this task). Full hyperparameter details are in Appendix C. 7.2 Experiment 1: Recall Capacity vs. State Size We measure accuracy as a function of n at fixed T = 32 for all five architectures, then extract n∗ for each. Results. Figure 2 shows the results. The Transformer achieves perfect accuracy (≥ 0.99) for all tested values n = 1, . . . , 10, yielding n∗ = 10 (the maximum tested). GLA achieves n∗ = 9, with accuracy remaining above 0.99 for n ≤ 9 and dropping sharply at n = 10. The Linear Transformer achieves n∗ = 3. Both Mamba variants (N=16 and N=64) achieve n∗ = 1, with accuracy dropping below the threshold at n = 2. The right panel of Figure 2 plots each architecture’s (|s|bits , n∗ ) pair alongside the theoretical bound curve from Theorem 10. All empirical points lie strictly below the bound, consistent with the theorem. The Transformer, with its growing state (|s|bits = 262,144 at T = 32), achieves the highest recall. Among fixed-state models (all with |s|bits ≤ 262,144), GLA utilizes its state capacity most efficiently, followed by the Linear Transformer and then Mamba. 7.3 Experiment 2: ECR Profiles Across Sequence Lengths We measure n∗ for each architecture at T ∈ {20, 32, 48, 64} and compute the ECR profile (Definition 22). Results. Table 5 reports the profiles at T = 64. The Transformer and the Hybrid(rattn = 0.5) achieve the highest recall (n∗ = 16 each) but at the cost of growing state size. Among fixed-state models, GLA achieves n∗ = 4, the Linear Transformer achieves n∗ = 1, and Mamba achieves n∗ = 1. As T increases from 20 to 64, the recall ratio r = n∗ /T remains stable for the Transformer (around 0.20–0.25) but decreases for all fixed-state models, consistent with the prediction that r → 0 for models satisfying E ∧ C. 7.4 Experiment 3: Scaling Behavior with T We track three quantities as T varies: per-step FLOPs, state size, and recall ratio r = n∗ /T . 20

Impossibility Triangle of Long-Context Modeling

(a) Accuracy vs. Number of Pairs

(b) Recall Capacity vs. State Size Thm 1 bound

1.0

14 12

Max recallable pairs n ∗

Recall accuracy

0.8

0.6

0.4

Transformer (n ∗ =10)

10 GLA (n ∗ =9)

8 6 4

0.2

0.0

Transformer LinearTransformer Mamba(N=16) Mamba(N=64)

GLA

Mamba(N=16) (n ∗ =1)

LinearTransformer (n ∗ =3)

α = 0.90

Random (1/32)

Mamba(N=64) (n ∗ =1)

0 6

Number of key-value pairs n

105

104

State size (bits)

106

Figure 2: Experiment 1. (a) Recall accuracy as a function of the number of key-value pairs n at T = 32. The Transformer maintains perfect accuracy across all tested n; fixed-state models degrade as n increases, with the degradation onset depending on the architecture. The dashed line marks the α = 0.90 threshold. (b) Maximum recall n∗ vs. state size for each architecture. The dashed curve is the information-theoretic upper bound from Theorem 10. All empirical points lie below the bound. Table 5: ECR profiles at T = 64. FLOPs/step is the per-step computation cost; state size is in bits; n∗ is the max recall at α = 0.90; r = n∗ /T is the recall ratio. The Transformer and Hybrid achieve the highest r but with growing state and cost. Architecture Transformer Hybrid(r=0.5) GLA Linear Transformer Mamba (N=16)

FLOPs/step

State (bits)

n∗

Region

16,384 10,240 4,096 4,096 1,024

524,288 589,824 65,536 65,536 65,536

16 16 4 1 1

0.250 0.250 0.063 0.016 0.016

R Interior EC EC EC

Results. Figure 3 shows the scaling behavior. In the left panel (per-step FLOPs), the Transformer’s cost grows linearly with T , while Mamba and GLA remain constant—confirming the E dichotomy. In the center panel (state size), the Transformer’s state grows linearly while all fixed-state models remain flat—confirming the C dichotomy. In the right panel (recall ratio r), the Transformer maintains r ≈ 0.20–0.25 across all T , while the Linear Transformer and Mamba show r decreasing toward zero—confirming the R prediction of Theorem 10. GLA maintains a higher r than other fixed-state models at small T but shows the beginning of decline at T = 64, consistent with its bounded state eventually becoming the bottleneck. 7.5 Experiment 4: Hybrid Architecture Interpolation We vary the attention ratio rattn ∈ {0, 0.125, 0.25, . . . , 1.0} in the 4-layer Hybrid model at T = 32 and measure n∗ , state size, and per-step FLOPs. 21

Zhou

(a) Efficiency: Cost per step 104

(b) Compactness: State size

Transformer LinearTransformer Mamba(N=16) GLA

4 × 105

0.25 0.20

Recall ratio n ∗ /T

Per-step FLOPs

State size (bits)

3 × 105 2 × 105

105 103 20

Sequence length T

6 × 104

0.15

Transformer LinearTransformer Mamba(N=16) GLA

0.10 0.05

Sequence length T

Figure 3: Experiment 3. Scaling behavior as sequence length T increases. Left: Per-step FLOPs. The Transformer’s cost grows with T ; fixed-state models (Mamba, GLA, Linear Transformer) remain constant. Center: State size. The Transformer’s KV-cache grows linearly; fixed-state models are flat. Right: Recall ratio r = n∗ /T . The Transformer maintains stable recall; fixed-state models show r → 0, consistent with Theorem 10.

(a) Recall Capacity vs. Attention Ratio

2A+2S

(b) Cost of Recall: State & Compute 500

4A+0S

n ∗ =10

8000

450 7000

1A+3S n ∗ =7

Pure SSM (n ∗ =1) Pure Transformer (n ∗ =10)

FLOPs per step

400

State size (Kbits)

Max recallable pairs n ∗

State size (Kbits) FLOPs/step

350

6000

300 250

5000

200

0A+4S n ∗ =1

150 0

4000 0.0

0.2

0.4

0.6

Attention layer ratio rattn

0.8

1.0

0.0

0.2

0.4

0.6

Attention layer ratio rattn

0.8

1.0

Figure 4: Experiment 4. Hybrid architecture interpolation at T = 32. (a) Recall capacity n∗ increases with the attention ratio rattn , saturating at rattn ≈ 0.5. Annotations show the number of attention (A) and SSM (S) layers. (b) State size and per-step FLOPs both increase with rattn , quantifying the cost of improved recall.

Results. Figure 4 shows the results. The left panel plots n∗ against rattn . At rattn = 0 (pure Mamba), n∗ = 1. Adding a single attention layer (rattn = 0.25) raises n∗ to 7. At rattn = 0.5 (two attention layers), n∗ reaches the maximum of 10 and saturates. The right panel shows that both state size and per-step FLOPs increase monotonically with rattn , confirming the cost of improved recall. This experiment directly illustrates the interior of the impossibility triangle: as rattn increases, the architecture moves from the E ∧ C edge toward the R vertex, trading compactness and efficiency for recall. 22

Impossibility Triangle of Long-Context Modeling

(a) Empirical Recall vs. Bound Infeasible region Mamba(N=4) Mamba(N=8) Mamba(N=16)

Empirical n ∗

104

(b) Mean Bound Utilization

Mamba(N=32) Mamba(N=64) LinearTransformer GLA

0.02%

Mamba(N=4)

103

102

Mamba(N=8)

0.01%

LinearTransformer

0.01%

Mamba(N=16)

101

100

0.04%

GLA

100

101

102

103

Information-theoretic bound

Mamba(N=32)

0.00%

Mamba(N=64)

0.00%

0.00

104

0.01%

0.01

0.02

0.03

0.04

Mean utilization of bound (%)

0.05

Figure 5: Experiment 5. Verification of the information-theoretic bound. (a) Empirical n∗ vs. theoretical bound for all tested configurations (7 architectures × 2 sequence lengths). All points lie below the diagonal, confirming Theorem 10. The shaded region above the diagonal is provably infeasible. (b) Mean utilization of the bound per architecture. All architectures use far below 0.1% of the theoretical capacity, reflecting that practical models allocate state for purposes beyond key-value storage. 7.6 Experiment 5: Information-Theoretic Bound Verification We verify that empirical recall never exceeds the theoretical bound (6) across multiple architectures and state sizes. We test Mamba with N ∈ {4, 8, 16, 32, 64}, the Linear Transformer, and GLA, each at T ∈ {32, 64}. Results. Figure 5 shows the results. The left panel plots empirical n∗ against the informationtheoretic bound for each configuration. All points lie strictly below the diagonal (the n∗ = bound line), confirming that the theorem is not violated in any case. The right panel shows the mean utilization of the bound (ratio n∗ /bound) per architecture. GLA achieves the highest utilization at approximately 0.04%, but all architectures remain far below 0.1% of the theoretical ceiling. The large gap between empirical recall and the bound reflects two factors: the bound is an information-theoretic maximum that assumes optimal encoding, while the models must also use their state for purposes beyond key-value storage (e.g., representing positional information, filler tokens, and task structure). Figure 6 compares all architectures at the largest tested sequence length, plotting n∗ against state size with the theoretical bound overlaid.

8 Discussion 8.1 Relationship to Classical Impossibility Theorems The impossibility triangle shares structural features with several classical results in computer science and mathematics, summarized in Table 6. In each case, three desirable properties are identified, any two can be achieved, but all three cannot. The proof techniques differ—we use information theory, CAP uses asynchronous network models, FLP uses bivalency arguments, and Arrow uses combinatorics—but the conceptual message is the same: 23

Zhou

Architecture Comparison at T = 64 Theorem 1 bound

Max recallable pairs n ∗

Transformer n ∗ =16 Hybrid(r=0.5) n ∗ =16

5 GLA n ∗ =4

Mamba(N=16) n ∗ =1 LinearTransformer n ∗ =1

0 104

105

State size (bits)

106

Figure 6: Architecture comparison at T = 64. Each point represents an architecture; the dashed curve is the theoretical upper bound from Theorem 10. The Transformer and Hybrid achieve the highest recall through large (growing) states. Fixed-state models (GLA, Linear Transformer, Mamba) are clustered at lower recall despite varying state sizes. The shaded region above the bound is infeasible. Table 6: Comparison with classical impossibility theorems. Theorem

Domain

Three properties

CAP (Brewer, 2000; Gilbert and Lynch, 2002) FLP (Fischer et al., 1985) Arrow (Arrow, 2012) Ours

Distributed systems Distributed consensus Social choice Sequence models

Consistency, Availability, Partition tolerance Termination, Validity, Agreement IIA, Pareto, Non-dictatorship E, C, R

certain engineering goals are fundamentally incompatible, and system design must make explicit choices about which property to sacrifice. 8.2 Can the Triangle Be Escaped? We consider three potential escape routes and explain why none succeeds. Data-dependent states. One might allow the state size to adapt to the input, expanding only when the sequence contains dense information and remaining compact otherwise. This is effectively what hybrid architectures with MoE or adaptive computation do. However, the impossibility theorem applies to worst-case inputs (the AR task generates uniformly random key-value pairs), and any fixed budget on expected state size still implies a bound on recall for sufficiently long sequences. Approximate recall. Relaxing the accuracy requirement from 1 − ε to a larger ε softens the bound (6) but does not eliminate it. The denominator (1 − ε) log2 V − 1 decreases as ε 24

Impossibility Triangle of Long-Context Modeling

increases, allowing more pairs to be recalled, but n∗ remains O(poly(d)) and independent of T . The triangle becomes “softer” but does not vanish. External memory. Models with external retrieval databases (e.g., the Memorizing Transformer (Wu et al., 2022)) can achieve strong recall, but the external database grows with T , violating C. In the OSP formalism, the database is part of the state. If it is excluded from the state definition, the model effectively has access to the raw input, which corresponds to construction (c) of Theorem 16 (re-computation) and violates E due to retrieval cost. 8.3 Implications for Architecture Design The impossibility theorem is not a negative result in the practical sense. Rather, it provides a design compass for architecture selection: • For applications where recall is paramount (e.g., long-document question answering, multi-hop reasoning), architectures in the R region (Transformers with large KVcaches) or global-attention hybrids (Jamba, Nemotron-H) are appropriate, with the understanding that memory and compute costs scale with T . • For applications where efficiency and compactness are paramount (e.g., edge deployment, streaming inference), architectures in the E ∧ C region (Mamba, RWKV, GLA) are appropriate, with the understanding that fine-grained recall at long range will be limited. • For applications requiring a balance, local-attention hybrids (Griffin, Samba) or memoryaugmented models (Titans, TTT) offer the best compromise, providing exact recall within a local window and compressed recall beyond it. The attention ratio rattn in hybrid architectures (Experiment 4) serves as a direct tuning knob for positioning a model within the triangle. 8.4 Limitations Our analysis has several limitations. First, the experiments use small-scale models (d = 64, 2 layers) on a synthetic task. While the theoretical bound holds at any scale, the empirical tightness of the bound may differ at larger scales where models can utilize their state more efficiently. Second, the associative recall task is a worst-case construction with uniformly random key-value pairs; natural language has structure and redundancy that models can exploit, potentially achieving higher effective recall than the worst-case bound suggests. Third, our classification of 52 architectures relies on asymptotic complexity analysis; constant factors, which matter greatly in practice, are not captured by the E and C definitions. 8.5 Open Problems We highlight four directions for future work. 1. Pareto frontier characterization. What is the exact shape of the Pareto frontier in the (e, c, r) space? Our experiments sketch the frontier at small scale; characterizing it at production scale remains open. 2. Distribution-dependent bounds. Can tighter bounds be obtained for inputs drawn from structured distributions (e.g., natural language) rather than worst-case 25

Zhou

random inputs? A distribution-dependent version of Theorem 10 would bridge the gap between the information-theoretic ceiling and practical performance. 3. Computational lower bounds. Theorem 10 is information-theoretic. Can computational complexity theory (e.g., cell-probe lower bounds or conditional hardness from SETH) provide stronger constraints on architectures that have sufficient state capacity but insufficient computation per step? 4. Multi-modal and multi-turn settings. The OSP abstraction considers a single sequence. Extending the framework to multi-modal inputs (interleaved text, images, audio) and multi-turn conversation (where the “sequence” grows across turns) would broaden its applicability.

9 Conclusion We have established that long-sequence models face a fundamental impossibility: Efficiency (E), Compactness (C), and Recall (R) cannot be simultaneously achieved. The proof, based on the Data Processing Inequality and Fano’s Inequality, shows that any model with fixed-size state can recall at most O(poly(d)/ log V ) key-value pairs, regardless of sequence length. We classified 52 architectures published before March 2026 into this framework, confirming that each satisfies at most two of the three properties. Experiments on synthetic associative recall tasks validated the theoretical bound and demonstrated the continuous trade-off in hybrid architectures. The impossibility triangle serves the same role for sequence model design that the CAP theorem serves for distributed systems: it does not prohibit building useful systems, but it clarifies the trade-offs that any design must navigate. Every long-sequence architecture is a choice about which vertex of the triangle to approach and which property to sacrifice. We hope this framework aids practitioners in making that choice explicitly and aids researchers in identifying the most promising directions for narrowing the gap between theoretical limits and practical performance.

Acknowledgments and Disclosure of Funding The author thanks the anonymous reviewers for their constructive feedback. This work was supported by the School of Mathematics and Statistics at Changsha University of Science and Technology. The author declares no competing interests.

Appendix A. Full Proofs This appendix provides complete proofs for all results stated in the main text, including intermediate lemmas that were invoked without proof. A.1 Proof of the Independence Lemma (used in Theorem 10, Step 2) The following lemma justifies the inequality used in Step 2 of the proof of Theorem 10, specifically the transition from (12) to (13) in Section 4.2.

Impossibility Triangle of Long-Context Modeling

Lemma 25 (Independence Lemma) Let v1 , . . . , vn be mutually independent random variables, and let Z be an arbitrary random variable (possibly dependent on all vi ). Then for each i ∈ [n], I(vi ; Z | v1 , . . . , vi−1 ) ≥ I(vi ; Z). (23) Proof We apply the chain rule for mutual information in two ways. I(vi ; Z, v1 , . . . , vi−1 ):

First, expand

I(vi ; Z, v1 , . . . , vi−1 ) = I(vi ; v1 , . . . , vi−1 ) + I(vi ; Z | v1 , . . . , vi−1 ).

(24)

Since v1 , . . . , vn are mutually independent, I(vi ; v1 , . . . , vi−1 ) = 0. Therefore, I(vi ; Z | v1 , . . . , vi−1 ) = I(vi ; Z, v1 , . . . , vi−1 ).

(25)

Second, expand the same quantity in a different order: I(vi ; Z, v1 , . . . , vi−1 ) = I(vi ; Z) + I(vi ; v1 , . . . , vi−1 | Z).

(26)

Since mutual information is nonneg ative, I(vi ; v1 , . . . , vi−1 | Z) ≥ 0. Combining (25) and (26), I(vi ; Z | v1 , . . . , vi−1 ) = I(vi ; Z) + I(vi ; v1 , . . . , vi−1 | Z) ≥ I(vi ; Z).

(27)

This completes the proof.

Remark 26 The independence of v1 , . . . , vn is essential. If the values were correlated (e.g., vi = v1 for all i), then knowing v1 would reveal vi , and the state would only need to store one value rather than n. The AR task (Definition 4) explicitly requires independent values (item (ii)), ensuring that the information requirement scales linearly with n. A.2 Detailed Proof of Theorem 14 (Lipschitz Capacity Bound) We provide a self-contained proof of the Lipschitz capacity bound stated in Section 4.3. Proof [Proof of Theorem 14] Let s0 ∈ Rd be the initial state with each component represented in b-bit floating-point precision. The initial state can encode at most d · b bits of information. Consider two initial states s0 and s′0 differing by ∆s0 = s′0 − s0 with ∥∆s0 ∥ = 2−b (the smallest representable perturbation). After one transition step with input x1 , the Lipschitz condition (Axiom 3) gives ∥s1 − s′1 ∥ = ∥δ(s0 , x1 ) − δ(s′0 , x1 )∥ ≤ L · ∥∆s0 ∥ = L · 2−b .

(28)

After T steps, applying the Lipschitz condition recursively, ∥sT − s′T ∥ ≤ LT · ∥∆s0 ∥ = LT · 2−b .

(29)

The effective precision of the state after T steps is determined by the smallest perturbation in s0 that produces a distinguishable difference in sT . A perturbation of magnitude 27

Zhou

ϵ in s0 grows to at most LT · ϵ in sT . For this to exceed the representation threshold 2−b , we need ϵ ≥ 2−b /LT = 2−(b+T log2 L) . Therefore, the effective precision per component is at most b + T log2 L bits. The total information capacity of the state sT is bounded by |sT |eff bits ≤ d · (b + T log2 L).

(30)

Substituting this effective capacity into the argument of Theorem 10 (replacing q(d) with d · (b + T log2 L) in inequality (14)), we obtain n∗ ≤

d · b + d · T · log2 L , (1 − ε) log2 V − 1

(31)

which is (15).

Remark 27 The bound (15) reveals three dynamical regimes: (i) Contractive (L < 1): log2 L < 0, so the effective capacity decreases with T . Information about early inputs is exponentially forgotten. This is the typical regime for stable SSMs with eigenvalues |λi | < 1. (ii) Isometric (L = 1): log2 L = 0, so the effective capacity equals d · b, independent of T . Information is preserved but the total capacity does not grow. This corresponds to unitary or orthogonal recurrences. (iii) Expansive (L > 1): log2 L > 0, so the effective capacity grows linearly with T . In principle, this allows recall to grow with T , but the system amplifies perturbations exponentially, making it numerically unstable. In practice, gradient clipping and finiteprecision arithmetic prevent exploitation of this regime. A.3 Proof of Theorem 16 (Achievability) The proof in Section 4.4 provides constructions for each pair. Here we verify the claimed complexity bounds in detail. Construction (a): E ∧ C via linear SSM. Consider the SSM st = Āst−1 + B̄xt with st ∈ RN , Ā ∈ RN ×N , B̄ ∈ RN ×din , and readout yt = Cst with C ∈ Rdout ×N . Efficiency. The transition requires one matrix-vector multiplication Āst−1 costing O(N 2 ) operations, one matrix-vector multiplication B̄xt costing O(N ·din ) operations, and one vector addition costing O(N ) operations. The total per-step cost is O(N 2 + N · din ), which is independent of t and T . Setting p(d) = N 2 + N · din satisfies Definition 5. Compactness. The state st ∈ RN has |st |bits = N · b bits at b-bit precision, independent of t and T . Setting q(d) = N · b satisfies Definition 6. Recall violation. By Theorem 10, n∗ ≤ N · b/[(1 − ε) log2 V − 1], which is independent of T . For T > n∗ /γ, strong recall (Definition 8) is violated. Construction (b): E∧R via KV-cache with sub-linear retrieval. Consider a model that maintains a hash table st = {(ki , vi )}ti=1 indexed by keys. Efficiency. Inserting a new key-value pair into a hash table costs O(d) amortized. Retrieving a value given a query key costs O(d) expected time (hash lookup). The total 28

Impossibility Triangle of Long-Context Modeling

per-step cost is O(d), independent of t. More precisely, if approximate nearest-neighbor search is used instead of exact hashing, the cost is O(d log t), which grows sub-linearly and satisfies E in a relaxed sense. For exact hashing with the AR task (where keys are discrete tokens), the cost is O(d) per step. Recall. The exact key-value pair is stored and retrievable by construction. For any n ≤ t, Pr[ρ(st , ki ) = vi ] = 1 for all i ∈ [n]. This satisfies R(1, n) for all n, and in particular strong R. Compactness violation. The state size |st |bits = t · d · b grows linearly with t. For any polynomial q(d), there exists t > q(d)/(d·b) such that |st |bits > q(d). Therefore C is violated. Construction (c): C ∧ R via re-computation. Consider a model with state st = compress(x1 , . . . , xt ) ∈ Rdc for a fixed compression dimension dc . The raw input (x1 , . . . , xT ) is stored in external memory (e.g., disk) and is not counted as part of the state. Compactness. The state st has |st |bits = dc · b, independent of t. Recall. Upon receiving query kj , the model re-scans the external input to find the pair (kj , vj ) and returns vj . This achieves Pr[ρ(sT , kj ) = vj ] = 1 for all j, satisfying strong R. Efficiency violation. The re-scan costs O(T · d) per query, which grows linearly with T . Therefore E is violated. A.4 Proof of Theorem 23 (Trade-off Inequality) Proof [Proof of Theorem 23] By Definition 22, the state size satisfies |sT |bits ≤ c·T ·log2 V ·b, and the number of recallable pairs is n∗ = r · T . Substituting into the bound (6) from Theorem 10, c · T · log2 V · b r·T ≤ . (32) (1 − ε) log2 V − 1 Dividing both sides by T > 0, r ≤

c · log2 V · b . (1 − ε) log2 V − 1

(33)

Factoring log2 V from the denominator, r ≤

c·b , (1 − ε) − 1/ log2 V

(34)

which is (22).

A.5 Proof of Proposition 17 Proof Consider a Transformer with nlayers layers, nheads attention heads per layer, head dimension dh = d/nheads , and b-bit precision. State size. At step t, each layer stores a key vector ki ∈ Rd and a value vector vi ∈ Rd for each of the t past tokens. The total state size is |st |bits = nlayers · t · 2d · b, 29

Zhou

which grows linearly in t. For any polynomial q(d) independent of T , there exists t > q(d)/(2 · nlayers · d · b) such that |st |bits > q(d). Therefore C is violated. Per-step cost. At step t, the attention computation requires computing qt⊤ ki for all i ≤ t (cost O(t · d) per head, O(t · d) total across heads since nheads · dh = d), followed by the softmax-weighted sum over values (cost O(t · d)). Across nlayers layers, the total per-step cost is O(nlayers · t · d), which grows linearly in t. Therefore E is violated. Recall. The softmax attention mechanism computes √ exp(qj⊤ ki / dh ) v̂j = · vi . √ PT ⊤ m=1 exp(qj km / dh ) i=1 T X

When the query qj is sufficiently aligned with the target key kj (which a trained model learns to ensure), the attention weight on position j approaches 1, and v̂j ≈ vj . Empirically, trained Transformers achieve near-perfect accuracy on AR(n, V ) for n up to the context window limit. Therefore R is satisfied.

A.6 Proof of Proposition 18 Proof Consider an SSM with nlayers layers, state dimension N per layer, model dimension d, and b-bit precision. (n ) (1) (ℓ) The total state across all layers is st = (st , . . . , st layers ) with st ∈ RN ×d for each layer ℓ. The minimum description length is |st |bits = nlayers · N · d · b. This is independent of t, so C is satisfied with q(d) = nlayers · N · d · b. The per-step transition cost is O(nlayers · N · d), independent of t, so E is satisfied. Substituting q(d) = nlayers · N · d · b into the bound (6), n∗ ≤

nlayers · N · d · b , (1 − ε) log2 V − 1

which is (17). Since n∗ is independent of T , strong recall (Definition 8) is violated for sufficiently large T .

A.7 Proof of Propositions 20 and 21 Proof [Proof of Proposition 20] Consider a hybrid architecture with nlayers total layers, of which nattn = ⌈rattn · nlayers ⌉ are global attention layers and nssm = nlayers − nattn are SSM layers. State size. The SSM layers contribute nssm · N · d · b bits (fixed). Each attention layer stores KV pairs for all t past tokens, contributing nattn · t · 2d · b bits (growing). The total is |st |bits = nssm · N · d · b + nattn · t · 2d · b. 30

Impossibility Triangle of Long-Context Modeling

When rattn > 0 (i.e., nattn ≥ 1), the second term grows linearly in t, so C is violated. Per-step cost. The SSM layers cost O(nssm · N · d) per step (constant). The attention layers cost O(nattn · t · d) per step (growing). When nattn ≥ 1, E is violated. Recall. The attention layers provide direct access to all past tokens within their scope. A model with even one global attention layer can route recall-critical information through that layer, achieving strong recall for sequences within the effective capacity. Empirically, Jamba with rattn ≈ 1/8 achieves high recall on 256K-token benchmarks (Lieber et al., 2024). Interpolation. At rattn = 0, the model is a pure SSM (satisfying E ∧ C, violating R). At rattn = 1, the model is a pure Transformer (satisfying R, violating E ∧ C). Intermediate values of rattn produce architectures in the interior of the triangle, with state size and cost scaling as O(rattn · T · d). Proof [Proof of Proposition 21] Consider a hybrid with nssm SSM layers and nswa slidingwindow attention layers with fixed window size w. State size. The SSM layers contribute nssm · N · d · b bits. Each sliding-window layer stores KV pairs for the most recent w tokens, contributing nswa · w · 2d · b bits. The total is

|st |bits = nssm · N · d · b + nswa · w · 2d · b,

which is independent of t when w is fixed. Therefore C is satisfied. Per-step cost. The SSM layers cost O(nssm · N · d). The sliding-window layers cost O(nswa · w · d). Both are independent of t. Therefore E is satisfied. Recall. The sliding-window layers provide exact recall for the most recent w tokens. Beyond the window, information is accessible only through the SSM’s compressed state. The total recall capacity is bounded by

n∗ ≤ w +

nssm · N · d · b , (1 − ε) log2 V − 1

which is independent of T . Strong recall requires n∗ ≥ γT , which fails for T > (w +n∗ssm )/γ.

Appendix B. Architecture Details This appendix provides the state transition equations and complexity analysis for each architecture family discussed in Section 5. For each family, we give the canonical recurrence, the state dimensions, the per-step cost, and the resulting recall bound from Theorem 10. 31

Zhou

B.1 Full-Attention Transformer Family The standard multi-head attention computes, at step t, qt = WQ xt ,

kt = WK xt , vt = WV xt , √ exp(qt⊤ ki / dh ) , i = 1, . . . , t, αti = Pt √ ⊤ j=1 exp(qt kj / dh ) ot =

t X

αti vi ,

(35) (36)

(37)

i=1

where WQ , WK , WV ∈ Rd×d are projection matrices and dh = d/nheads is the head dimension. State: st = {(ki , vi )}ti=1 , with |st |bits = t · 2d · b per layer. Cost: Computing (36)–(37) requires O(t · d) operations per layer. Variants. Multi-Query Attention (Shazeer, 2019) shares K, V across heads, reducing the KV-cache by a factor of nheads but not changing the O(t) dependence. Grouped-Query Attention (Ainslie et al., 2023) shares K, V within groups of g heads, interpolating between MHA (g = nheads ) and MQA (g = 1). Multi-Latent Attention (Liu et al., 2024) compresses K, V into a low-dimensional latent cKV ∈ Rdc with dc ≪ d, reducing the per-token cache t from 2d · b to dc · b bits, but the cache still grows linearly in t. B.2 Linear Attention Family The Linear Transformer (Katharopoulos et al., 2020) replaces the softmax in (36) with a kernel feature map ϕ: St = St−1 + ϕ(kt ) vt⊤ ,

(38)

zt = zt−1 + ϕ(kt ),

(39)

ϕ(qt )⊤ St , ot = ϕ(qt )⊤ zt

(40)

where St ∈ Rm×dv , zt ∈ Rm , and m is the feature dimension. State: (St , zt ) with |st |bits = (m · dv + m) · b per layer, independent of t. Cost: O(m · dv ) per step per layer. Recall bound: n∗ ≤ nlayers · nheads · (m · dv + m) · b/[(1 − ε) log2 V − 1]. The Performer (Krzysztof et al., 2021) uses positive orthogonal random features for ϕ. cosFormer (Qin et al., 2022) uses a cosine-based kernel. All share the same recurrence structure and complexity. B.3 SSM Family The canonical SSM recurrence is ht = Āt ⊙ ht−1 + B̄t xt ,

(41)

yt = Ct ht + D xt ,

(42)

Impossibility Triangle of Long-Context Modeling

where ht ∈ Rd×N is the hidden state, Āt ∈ Rd×N is the discretized state matrix, B̄t ∈ Rd×N is the discretized input matrix, and Ct ∈ Rd×N is the output matrix. In S4 (Gu et al., 2021), Ā and B̄ are fixed (input-independent) and derived from the HiPPO matrix via bilinear discretization. In Mamba (Gu and Dao, 2023), all three matrices are input-dependent: ∆t = softplus(W∆ xt + b∆ ),

Bt = WB xt ,

Ct = WC xt ,

Āt = exp(∆t · A),

B̄t = ∆t · Bt . (43)

State: ht ∈ Rd×N with |st |bits = d · N · b per layer, independent of t. Cost: The transition (41) requires elementwise multiplication Āt ⊙ ht−1 (O(d · N )) and outer product B̄t xt (O(d · N )), totaling O(d · N ) per layer. Computing the input-dependent parameters (43) adds O(d · N ). Recall bound: n∗ ≤ nlayers · d · N · b/[(1 − ε) log2 V − 1]. Mamba-2 (Dao and Gu, 2024) restructures the computation as a structured semiseparable matrix multiplication, improving hardware utilization without changing the state size or asymptotic cost. Mamba-3 (Lahoti et al., 2026) introduces complex-valued states and MIMO formulations, increasing the effective expressiveness of the state update while maintaining the same dimensional footprint d × N . B.4 Gated Linear RNN Family RetNet (Sun et al., 2024b) uses exponential decay: St = γ St−1 + kt vt⊤ ,

ot = qt⊤ St ,

(44)

where γ ∈ (0, 1) is a learnable scalar decay factor and St ∈ Rdk ×dv . GLA (Yang et al., 2023) generalizes the decay to a data-dependent gate: St = diag(σ(wt )) St−1 + kt vt⊤ ,

ot = qt⊤ St ,

(45)

∈ Rdk and σ is the sigmoid function.

where wt = Wg xt DeltaNet (Yang et al., 2024b) uses the delta rule for associative memory: St = St−1 − βt (kt⊤ St−1 )kt + βt vt kt⊤ = (I − βt kt kt⊤ ) St−1 + βt vt kt⊤ ,

(46)

where βt ∈ (0, 1) is a learned step size. The delta rule implements a “last-write-wins” update: the projection kt⊤ St−1 retrieves the current value associated with key kt , subtracts it, and writes the new value vt . Gated DeltaNet (Yang et al., 2024a) adds a data-dependent forget gate to (46). RWKV-4 (Peng et al., 2023a) uses exponentially weighted key-value accumulation: at at = e−w at−1 + ekt vt , bt = e−w bt−1 + ekt , ot = σ(rt ) ⊙ , (47) bt where w is a learnable decay vector. RWKV-5/6 (Peng et al., 2024) extends the state to matrix-valued form with dynamic recurrence. RWKV-7 (Peng et al., 2025) introduces vector-valued gating and a generalized delta rule, combining the associative update of DeltaNet with the exponential gating of xLSTM. All architectures in this family maintain a matrix state St ∈ Rdk ×dv (or equivalent) of fixed size, yielding the same asymptotic recall bound. The differences lie in how efficiently each parameterization of Gt and Ut in the unified recurrence (16) utilizes the available state capacity. 33

Zhou

B.5 Extended LSTM Family xLSTM (Beck et al., 2024) introduces two variants. The scalar variant (sLSTM) uses exponential gating: ct = ft ct−1 + it zt ,

nt = ft nt−1 + it ,

ht = ot ⊙

ct , nt

(48)

where ft = exp(wf⊤ xt + bf ) is the exponential forget gate, it = exp(wi⊤ xt + bi ) is the exponential input gate, zt is the cell input, and ot = σ(wo⊤ xt + bo ) is the output gate. The state (ct , nt ) has dimension O(d). The matrix variant (mLSTM) replaces the scalar cell with a matrix: Ct = ft Ct−1 + it (vt kt⊤ ),

nt = ft nt−1 + it kt ,

h̃t =

C t qt , max(|n⊤ t qt |, 1)

ht = ot ⊙ h̃t , (49)

where Ct ∈ Rd×d is the matrix memory. This is an instance of the unified recurrence (16) with Gt = ft · I and Ut = it · vt ⊗ kt . The state size is |st |bits = (d2 + d) · b per layer. MEGA (Ma et al., 2022) uses an exponential moving average mt = α mt−1 + (1 − α) xt combined with gated single-head attention. MEGALODON (Ma et al., 2024) extends this to complex-valued EMA (CEMA) with timestep normalization for stable large-scale training. Both maintain fixed-size EMA states. B.6 Memory-Augmented Models The ∞-former (Martins et al., 2022) maintains a continuous long-term memory updated through a learned write mechanism. Infini-Attention (Munkhdalai et al., 2024) combines local softmax attention within a fixed chunk with a compressive memory updated via linear attention: Mt = Mt−1 + σ(kt ) vt⊤ ,

omem = t

σ(qt )⊤ Mt , σ(qt )⊤ ztmem

ot = gt ⊙ olocal + (1 − gt ) ⊙ omem , t t

(50)

where Mt ∈ Rdk ×dv is the compressive memory, ztmem is the memory normalizer (analogous to zt in (39) but maintained separately), and gt is a learned gating scalar. The memory Mt has fixed size, satisfying C. Titans (Behrouz et al., 2024) treats the memory as a small neural network with parameters θt , updated at each step via gradient descent on a key-value binding loss: θt = θt−1 − ηt ∇θ L(fθt−1 (kt ), vt ),

(51)

where fθ is the memory network and L is a reconstruction loss. The state is θt with |θt |bits = |θ| · b bits, independent of t. TTT-Linear/MLP (Sun et al., 2024a) similarly treats the hidden state as model weights updated by self-supervised learning: Wt = Wt−1 − η ∇W Lssl (Wt−1 ; xt ), The weight matrix Wt has fixed dimensions, satisfying C. 34

yt = fWt (xt ).

(52)

Impossibility Triangle of Long-Context Modeling

Table 7: Model configurations used in all experiments. All models use d = 64, 2 layers (except Hybrid which uses 4 layers), and 32-bit floating-point precision. Architecture

Transformer Linear Transformer Mamba (N=16) Mamba (N=64) GLA Hybrid(rattn )

64 64 64 64 64 64

Layers Heads 2 2 2 2 2 4

4 4 — — 4 4

State dim N

Parameters

— (KV-cache) d2h = 256 per head N = 16 N = 64 d2h = 256 per head N = 16 (SSM layers)

∼70K ∼70K ∼85K ∼120K ∼75K ∼100–140K

For all four architectures, the state capacity is |θ| · b bits for Titans and |W | · b bits for TTT. By Theorem 10, this gives n∗ ≤ |θ| · b/[(1 − ε) log2 V − 1] for Titans and n∗ ≤ |W | · b/[(1 − ε) log2 V − 1] for TTT, both independent of T . The gradient-based update rules in Titans and TTT can be viewed as sophisticated instantiations of Ut in the unified recurrence (16), where the “gate” Gt corresponds to the identity minus the learning rate times the Hessian, and the “update” Ut corresponds to the gradient step. Despite the greater expressiveness of these update rules compared to simple linear accumulation, the information-theoretic ceiling remains the same.

Appendix C. Experiment Details C.1 Task Construction Each instance of AR(n, V ) is constructed as follows. We use V = 32 as the vocabulary size. The input alphabet X = {0, 1, . . . , 31} consists of 32 regular tokens. Three additional special tokens are used: a key marker (token 32), a value marker (token 33, reserved but not explicitly used in the sequence), and a query marker (token 34). The total vocabulary presented to the model is |X | + 3 = 35. For a given n and sequence length T , the sequence is constructed as: 1. For each i = 1, . . . , n: emit the key marker, then ki , then vi (3 tokens per pair). 2. Emit T − 3n − 2 filler tokens drawn uniformly from {0, . . . , 31}. 3. Emit the query marker, then kj where j ∼ Uniform([n]). The target output is vj . The constraint T ≥ 3n + 2 ensures non-negative filler length. C.2 Model Configurations Table 7 summarizes the hyperparameters of each architecture. C.3 Training Protocol All models are trained from scratch for each (n, T ) configuration. We use the AdamW optimizer (Loshchilov and Hutter, 2019) with learning rate 3 × 10−4 , weight decay 0.01, and gradient clipping at norm 1.0. The learning rate schedule consists of a linear warmup over the first 200 steps followed by cosine decay to 5% of the peak learning rate over the remaining steps. Each model is trained for 8,000 steps with batch size 64. Training data is generated online: each batch consists of freshly sampled AR(n, V ) instances, so the model 35

Zhou

never sees the same sequence twice. The loss function is the cross-entropy between the model’s output distribution at the last position and the target value vj . C.4 Evaluation Protocol After training, each model is evaluated on 200 independently generated test instances. For each instance, the model’s prediction is the argmax of the output logits at the last position, restricted to the vocabulary {0, . . . , V − 1}. The accuracy is the fraction of instances for which the prediction equals the target vj . We define n∗ as the largest n for which accuracy ≥ 0.90. The evaluation sweeps are: • Experiment 1 (Section 7.2): n ∈ {1, 2, . . . , 10} at T = 32. • Experiments 2–3: n ∈ {1, 2, 4, 8, 16, 32} for each T ∈ {20, 32, 48, 64}. • Experiment 4: at T = 32, we test n ∈ {1, 2, . . . , 10} and sweep the attention ratio rattn over nine values from 0 to 1 in increments of 0.125. • Experiment 5: n ∈ {1, 2, . . . , 10} for each T ∈ {32, 64} and each architecture variant. C.5 Information-Theoretic Bound Computation The theoretical bound from Theorem 10 is computed as n∗bound =

q(d) , (1 − ε) log2 V − 1

(53)

where q(d) = |s|bits is the total state size in bits. In our experiments, ε = 0.10 and V = 32, giving a denominator of (1 − 0.10) × log2 32 − 1 = 0.90 × 5 − 1 = 3.5. For the Linear Transformer with nlayers = 2, nheads = 4, and dh = 16, the state per layer consists of nheads matrices of size dh × dh , giving |s|bits = 2 × 4 × 16 × 16 × 32 = 65,536 bits. The theoretical bound is n∗bound = 65,536/3.5 ≈ 18,724 pairs. The empirical n∗ values observed in our experiments (at most 10 pairs) are far below this bound, reflecting the gap between information-theoretic capacity and the capacity that gradient-trained models can practically utilize on the AR task at this scale. C.6 Computational Resources All experiments were conducted on NVIDIA RTX 3090 GPUs (24GB VRAM). Each model training run (8,000 steps, batch size 64) takes approximately 3–8 minutes depending on the architecture and sequence length. The full experimental pipeline (5 experiments × multiple architectures × multiple n values) completed in approximately 10 hours on a single GPU. No multi-GPU training was required due to the small model sizes. C.7 Reproducibility All experiments use a fixed random seed (42) for reproducibility. The code, configuration files, and raw experimental results are available at [URL to be added upon publication]. The experimental framework is implemented in PyTorch and requires only standard packages (torch, numpy, pandas, matplotlib). 36

Impossibility Triangle of Long-Context Modeling

References Joshua Ainslie, James Lee-Thorp, Michiel De Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 4895–4901, 2023. Simran Arora, Sabri Eyuboglu, Michael Zhang, Aman Timalsina, Silas Alberti, Dylan Zinsley, James Zou, Atri Rudra, and Christopher Ré. Simple linear attention language models balance the recall-throughput tradeoff. arXiv preprint arXiv:2402.18668, 2024. Kenneth J Arrow. Social choice and individual values, volume 12. Yale university press, 2012. Maximilian Beck, Korbinian Pöppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. xlstm: Extended long short-term memory. Advances in Neural Information Processing Systems, 37:107547–107603, 2024. Ali Behrouz, Peilin Zhong, and Vahab Mirrokni. Titans: Learning to memorize at test time. arXiv preprint arXiv:2501.00663, 2024. Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150, 2020. Aaron Blakeman, Aarti Basant, Abhinav Khattar, Adithya Renduchintala, Akhiad Bercovich, Aleksander Ficek, Alexis Bjorlin, Ali Taghibakhshi, Amala Sanjay Deshmukh, Ameya Sunil Mahabaleshwarkar, et al. Nemotron-h: A family of accurate and efficient hybrid mamba-transformer models. arXiv preprint arXiv:2504.03624, 2025. Eric A Brewer. Towards robust distributed systems. In PODC, volume 7, pages 343477– 343502. Portland, OR, 2000. Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509, 2019. Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999. Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691, 2023. Tri Dao and Albert Gu. Transformers are ssms: Generalized models and efficient algorithms through structured state space duality, 2024. URL https://arxiv.org/abs/ 2405.21060. Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in neural information processing systems, 35:16344–16359, 2022. 37

Zhou

Soham De, Samuel L Smith, Anushan Fernando, Aleksandar Botev, George CristianMuraru, Albert Gu, Ruba Haroun, Leonard Berrada, Yutian Chen, Srivatsan Srinivasan, et al. Griffin: Mixing gated linear recurrences with local attention for efficient language models. arXiv preprint arXiv:2402.19427, 2024. Leo Feng, Frederick Tung, Mohamed Osama Ahmed, Yoshua Bengio, and Hossein Hajimirsadeghi. Were rnns all we needed? arXiv preprint arXiv:2410.01201, 2024. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374–382, 1985. Daniel Y Fu, Tri Dao, Khaled K Saab, Armin W Thomas, Atri Rudra, and Christopher Ré. Hungry hungry hippos: Towards language modeling with state space models. arxiv 2022. arXiv preprint arXiv:2212.14052, 2022. Seth Gilbert and Nancy Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. Acm Sigact News, 33(2):51–59, 2002. Paolo Glorioso, Quentin Anthony, Yury Tokpanov, Anna Golubeva, Vasudev Shyam, James Whittington, Jonathan Pilault, and Beren Millidge. The zamba2 suite: Technical report. arXiv preprint arXiv:2411.15242, 2024a. Paolo Glorioso, Quentin Anthony, Yury Tokpanov, James Whittington, Jonathan Pilault, Adam Ibrahim, and Beren Millidge. Zamba: A compact 7b ssm hybrid model. arXiv preprint arXiv:2405.16712, 2024b. Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752, 2023. Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00396, 2021. Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. On the parameterization and initialization of diagonal state space models. Advances in neural information processing systems, 35:35971–35983, 2022. Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective as structured state spaces. Advances in neural information processing systems, 35:22982– 22994, 2022. Chi Han, Qifan Wang, Hao Peng, Wenhan Xiong, Yu Chen, Heng Ji, and Sinong Wang. Lm-infinite: Zero-shot extreme length generalization for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 3991–4008, 2024. Hongye Jin, Xiaotian Han, Jingfeng Yang, Zhimeng Jiang, Zirui Liu, Chia-Yuan Chang, Huiyuan Chen, and Xia Hu. Llm maybe longlm: Self-extend llm context window without tuning. arXiv preprint arXiv:2401.01325, 2024. 38

Impossibility Triangle of Long-Context Modeling

Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are RNNs: Fast autoregressive transformers with linear attention. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5156–5165. PMLR, 13–18 Jul 2020. URL https://proceedings.mlr.press/v119/katharopoulos20a. html. Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04451, 2020. Choromanski Krzysztof, Likhosherstov Valerii, Dohan David, Song Xingyou, Gane Andreea, Sarlos Tamas, Hawkins Peter, Davis Jared, Mohiuddin Afroz, Kaiser Lukasz, et al. Rethinking attention with performers. Proceedings of ICLR, 2021. Aakash Lahoti, Kevin Y Li, Berlin Chen, Caitlin Wang, Aviv Bick, J Zico Kolter, Tri Dao, and Albert Gu. Mamba-3: Improved sequence modeling using state space principles. arXiv preprint arXiv:2603.15569, 2026. Aonian Li, Bangwei Gong, Bo Yang, Boji Shan, Chang Liu, Cheng Zhu, Chunhao Zhang, Congchao Guo, Da Chen, Dong Li, et al. Minimax-01: Scaling foundation models with lightning attention. arXiv preprint arXiv:2501.08313, 2025. Opher Lieber, Barak Lenz, Hofit Bata, Gal Cohen, Jhonathan Osin, Itay Dalmedigos, Erez Safahi, Shaked Meirom, Yonatan Belinkov, Shai Shalev-Shwartz, et al. Jamba: A hybrid transformer-mamba language model. arXiv preprint arXiv:2403.19887, 2024. Aixin Liu, Bei Feng, Bin Wang, Bingxuan Wang, Bo Liu, Chenggang Zhao, Chengqi Dengr, Chong Ruan, Damai Dai, Daya Guo, et al. Deepseek-v2: A strong, economical, and efficient mixture-of-experts language model. arXiv preprint arXiv:2405.04434, 2024. Hao Liu, Matei Zaharia, and Pieter Abbeel. Ring attention with blockwise transformers for near-infinite context. arXiv preprint arXiv:2310.01889, 2023. Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arxiv. arXiv preprint arXiv:1711.05101, 10, 2019. Xuezhe Ma, Chunting Zhou, Xiang Kong, Junxian He, Liangke Gui, Graham Neubig, Jonathan May, and Luke Zettlemoyer. Mega: Moving average equipped gated attention. arXiv preprint arXiv:2209.10655, 2022. Xuezhe Ma, Xiaomeng Yang, Wenhan Xiong, Beidi Chen, Lili Yu, Hao Zhang, Jonathan May, Luke Zettlemoyer, Omer Levy, and Chunting Zhou. Megalodon: Efficient llm pretraining and inference with unlimited context length. Advances in Neural Information Processing Systems, 37:71831–71854, 2024. Pedro Henrique Martins, Zita Marinho, and André FT Martins. ∞-former: Infinite memory transformer. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5468–5485, 2022. 39

Zhou

Tsendsuren Munkhdalai, Manaal Faruqui, and Siddharth Gopal. Leave no context behind: Efficient infinite context transformers with infini-attention. arXiv preprint arXiv:2404.07143, 101:15, 2024. Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Stella Biderman, Huanqi Cao, Xin Cheng, Michael Chung, Leon Derczynski, et al. Rwkv: Reinventing rnns for the transformer era. In Findings of the association for computational linguistics: EMNLP 2023, pages 14048–14077, 2023a. Bo Peng, Daniel Goldstein, Quentin Anthony, Alon Albalak, Eric Alcaide, Stella Biderman, Eugene Cheah, Xingjian Du, Teddy Ferdinan, Haowen Hou, et al. Eagle and finch: Rwkv with matrix-valued states and dynamic recurrence. arXiv preprint arXiv:2404.05892, 2024. Bo Peng, Ruichong Zhang, Daniel Goldstein, Eric Alcaide, Xingjian Du, Haowen Hou, Jiaju Lin, Jiaxing Liu, Janna Lu, William Merrill, et al. Rwkv-7” goose” with expressive dynamic state evolution. arXiv preprint arXiv:2503.14456, 2025. Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole. Yarn: Efficient context window extension of large language models. arXiv preprint arXiv:2309.00071, 2023b. Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. In International Conference on Machine Learning, pages 28043–28078. PMLR, 2023a. Michael Poli, Jue Wang, Stefano Massaroli, Jeffrey Quesnelle, Ryan Carlow, Eric Nguyen, and Armin Thomas. Stripedhyena: Moving beyond transformers with hybrid signal processing models. GitHub repository, 12, 2023b. Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. arXiv preprint arXiv:2202.08791, 2022. Zhen Qin, Songlin Yang, Weixuan Sun, Xuyang Shen, Dong Li, Weigao Sun, and Yiran Zhong. Hgrn2: Gated linear rnns with state expansion. arXiv preprint arXiv:2404.07904, 2024. Liliang Ren, Yang Liu, Yadong Lu, Yelong Shen, Chen Liang, and Weizhu Chen. Samba: Simple hybrid state space models for efficient unlimited context language modeling. arXiv preprint arXiv:2406.07522, 2024. Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani, and Tri Dao. Flashattention-3: Fast and accurate attention with asynchrony and low-precision. Advances in Neural Information Processing Systems, 37:68658–68685, 2024. Noam Shazeer. Fast transformer decoding: One write-head is all you need. arXiv preprint arXiv:1911.02150, 2019. 40

Impossibility Triangle of Long-Context Modeling

Jimmy TH Smith, Andrew Warrington, and Scott W Linderman. Simplified state space layers for sequence modeling, 2023. URL https://arxiv. org/abs/2208.04933, 2208:04933. Yu Sun, Xinhao Li, Karan Dalal, Jiarui Xu, Arjun Vikram, Genghan Zhang, Yann Dubois, Xinlei Chen, Xiaolong Wang, Sanmi Koyejo, et al. Learning to (learn at test time): Rnns with expressive hidden states. arXiv preprint arXiv:2407.04620, 2024a. Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models (2023). URL http://arxiv. org/abs/2307.08621 v1, 2024b. Kimi Team, Yu Zhang, Zongyu Lin, Xingcheng Yao, Jiaxi Hu, Fanqing Meng, Chengyin Liu, Xin Men, Songlin Yang, Zhiyuan Li, et al. Kimi linear: An expressive, efficient attention architecture. arXiv preprint arXiv:2510.26692, 2025. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. Yuhuai Wu, Markus N Rabe, DeLesley Hutchins, and Christian Szegedy. Memorizing transformers. arXiv preprint arXiv:2203.08913, 2022. Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309.17453, 2023. Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim. Gated linear attention transformers with hardware-efficient training. arXiv preprint arXiv:2312.06635, 2023. Songlin Yang, Jan Kautz, and Ali Hatamizadeh. Gated delta networks: Improving mamba2 with delta rule. arXiv preprint arXiv:2412.06464, 2024a. Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing linear transformers with the delta rule over sequence length. Advances in neural information processing systems, 37:115491–115522, 2024b. Jingyang Yuan, Huazuo Gao, Damai Dai, Junyu Luo, Liang Zhao, Zhengyan Zhang, Zhenda Xie, Yuxing Wei, Lean Wang, Zhiping Xiao, et al. Native sparse attention: Hardwarealigned and natively trainable sparse attention. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 23078– 23097, 2025. Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 33:17283–17297, 2020. Yu Zhang, Songlin Yang, Ruijie Zhu, Yue Zhang, Leyang Cui, Yiqiao Wang, Bolun Wang, Freda Shi, Bailin Wang, Wei Bi, et al. Gated slot attention for efficient linear-time sequence modeling. Advances in Neural Information Processing Systems, 37:116870– 116898, 2024. 41

Record · ID 158554 · SHA-256 5e0579a2b93b8da4
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.