Overview
Long-sequence modeling has long been constrained by the \(O(T^2)\) cost of self-attention. Proposed remedies—linear attention, state space models (SSMs), and hybrid architectures—have lacked a unified theoretical characterization. A 2026 paper by Yan Zhou (School of Mathematics and Statistics, Changsha University of Science and Technology) addresses this gap by proving an Impossibility Triangle for long-context modeling and systematically classifying 52 architectures published before March 2026 (arXiv:2605.05066, 41 pages).
> Note: Analogy with the CAP theorem. The author explicitly compares the triangle to the CAP theorem in distributed systems: it does not prevent building useful systems, but forces designers to make explicit trade-offs among conflicting guarantees.
The OSP Framework
The paper introduces the Online Sequence Processor (OSP) abstraction, a seven-tuple \((\mathcal{X}, \mathcal{S}, f, g, h, s_0, T)\) covering input space, state space, state transition \(f\), output function \(g\), optional update rule \(h\), initial state \(s_0\), and sequence length \(T\).
Under this framework:
- Standard Transformer: KV-cache is an explicit state growing with \(T\)
- Mamba / SSM: a fixed-dimensional hidden vector \(h_t \in \mathbb{R}^N\) is a compact state
- Linear Transformer: the accumulated key-value outer product \(S_t \in \mathbb{R}^{d_k \times d_v}\) is a structured compact state
- Hybrids: compositions of multiple sub-states
- Efficiency (\(\mathfrak{E}\)): per-step FLOPs independent of \(T\), i.e., \(\text{FLOPs}(s_t, x_t) = O(1)\)
- Compactness (\(\mathfrak{C}\)): state size in bits independent of \(T\), i.e., \(\|s_t\|_{\text{bits}} = O(1)\)
- Recall (\(\mathfrak{R}\)): number of recoverable key-value pairs scales as \(n^* = \Omega(T)\)
- Title: *The Impossibility Triangle of Long-Context Modeling*
- arXiv: 2605.05066
- Date: 2026-05-06
- Author: Yan Zhou, School of Mathematics and Statistics, Changsha University of Science and Technology
- Length: 41 pages, 6 figures
Three properties are formally defined:
The Main Theorem
Theorem (Impossibility Triangle). No Online Sequence Processor can simultaneously satisfy Efficiency (\(\mathfrak{E}\)), Compactness (\(\mathfrak{C}\)), and Recall (\(\mathfrak{R}\)).
Any model satisfying \(\mathfrak{E}\) and \(\mathfrak{C}\) is bounded by:
Crucially, this bound is independent of sequence length \(T\): no matter how long the input, a compact, efficient model can recall only a fixed number of past facts.
Proof sketch (three steps): 1. Compression: by Compactness, \(s_t\) has a fixed bit budget; via the Data Processing Inequality, the mutual information \(I(s_t; x_{1:t})\) is capped by the state entropy \(H(s_t)\). 2. Information demand of recall: Fano's Inequality links recall error probability to mutual information: \(P_e \geq 1 - \frac{I + \log 2}{\log(V^n)}\). 3. Combined bound: recoverable pairs satisfy \(n^* \leq O(\text{poly}(d) / \log V)\).
The result extends to continuous-state systems via a Lipschitz stability argument: even continuous states are effectively limited by the model's numerical-precision bits.
Classification of 52 Architectures
Each of the 52 analyzed architectures satisfies at most two of the three properties:
| Category | Examples | Achieves | Sacrifices | State | |:---------|:---------|:--------:|:----------:|:------| | Standard Transformer | GPT, LLaMA, DeepSeek | \(\mathfrak{R} + \mathfrak{E}\) | \(\mathfrak{C}\) | KV-cache grows with \(T\) | | SSMs | Mamba, S4, DSS, S5 | \(\mathfrak{E} + \mathfrak{C}\) | \(\mathfrak{R}\) | Fixed-size hidden state | | Linear attention | Linear Transformer, Performer, RWKV | \(\mathfrak{E} + \mathfrak{C}\) | \(\mathfrak{R}\) | Accumulated outer product / kernel state | | Gated linear attention | GLA, HGRN, RetNet | \(\mathfrak{E} + \mathfrak{C}\) | \(\mathfrak{R}\) | Data-dependent gated state | | Hybrids | Samba, Griffin, Zamba, Jamba | internal trade-off | internal trade-off | Composable states | | Sparse attention | BigBird, Longformer, Ring Attention | \(\mathfrak{R} + \mathfrak{E}\) (approx.) | \(\mathfrak{C}\) (approx.) | Sparsified/distributed KV-cache |
For hybrids parameterized by attention ratio \(r_{\text{attn}} \in [0,1]\), the paper proves a continuous trade-off curve strictly inside the triangle:
As \(r_{\text{attn}} \to 0\) the model approaches Mamba (\(\mathfrak{E}+\mathfrak{C}\)); as \(r_{\text{attn}} \to 1\) it approaches Transformer (\(\mathfrak{R}+\mathfrak{E}\)) — but the \(\mathfrak{R}+\mathfrak{C}\) edge can never be reached.
Experimental Validation
Five architectures were tested on synthetic associative recall tasks (recall the value of a queried key among \(n\) pairs):
| Architecture | State size | Bound utilization | Finding | |:-------------|:-----------|:-----------------:|:--------| | Transformer | \(O(T \cdot d)\) | N/A (no \(\mathfrak{C}\)) | Only architecture achieving linear recall | | Linear Transformer | \(O(d^2)\) | < 0.01% | Fixed state, limited recall | | Mamba (N=64) | \(O(d \cdot N)\) | < 0.02% | Increasing N helps little | | GLA | \(O(d^2)\) | ~0.04% | Best among fixed-state models | | Hybrid (\(r_{\text{attn}}=0.5\)) | mixed | in between | Validates continuous trade-off |
Key findings: (1) the theoretical bound is far from being reached in practice — even GLA achieves only ~0.04% of the information-theoretic limit, since state capacity is spent on positional encoding, task structure, and padding; (2) all empirical points fall strictly below the theoretical bound, matching the proven infeasible region.
Design Implications
1. Choose architectures by application needs: exact retrieval over very long documents favors Transformers/sparse attention; streaming workloads favor SSMs. 2. Optimize hybrids along the trade-off curve, not toward breaking the boundary: tuning attention ratio, state dimension, and gating smoothly interpolates among E, C, R. 3. Recall should be a mandatory evaluation metric: advertised "context window" measures tokens *processed*, not tokens *recallable* — the theorem proves these are fundamentally decoupled for E+C architectures. 4. The information-theoretic bound marks the theoretical ceiling: the 0.04% utilization implies large practical optimization headroom via better state encoding and compression.
Limitations and Open Problems
Limitations: worst-case bounds may be loose for structured data; associative recall isolates pure memorization, not reasoning or generalization; classification rests on the author's reading of each architecture's published description.
Open questions: can external memory or hierarchical states approximate all three vertices? Can reasoning compensate for recall deficits in real tasks? How can the bound guide state-encoding optimization to close the 0.04% gap?