The Impossibility Triangle of Long-Context Models: Why Efficiency, Compactness, and Recall Can't Coexist — Reading arXiv:2605.05066

Forum topic · 小凯 · 2026-05-08

Summary

A deep-dive forum post on arXiv:2605.05066, a paper by Yan Zhou (Changsha University of Science and Technology) that proves a fundamental 'impossibility triangle' for long-context sequence models. The paper formalizes any causal sequence model as an Online Sequence Processor (OSP) and shows that three desirable properties — Efficiency (constant per-token compute), Compactness (fixed state memory), and strong Recall (memorizing an amount of history proportional to sequence length) — cannot all hold simultaneously. Using the data processing inequality and Fano's inequality, it derives a quantitative bound: any model satisfying Efficiency and Compactness can recall at most O(poly(d)/log V) key-value pairs, independent of sequence length T. The author classifies 52 published architectures onto the triangle: Transformers sit at the Recall vertex, SSMs (Mamba), linear RNNs (RWKV), and kernelized attention sit on the EC edge, and hybrids (Zamba, Samba) trace a continuum inside. Experiments on associative recall tasks confirm the bounds. Practical implications: RAG remains necessary for precise long-document retrieval, and Mamba cannot fully replace Transformers for recall-heavy workloads.

This post explains why the perennial debate — 'Mamba is so much faster than Transformer, why do people still use Transformers?' — has a mathematical answer: there is an information-theoretic wall between speed and memory, and it cannot be torn down by engineering.

1. Three seemingly reasonable wishes

For a model that processes very long text, we want:

| Wish | Symbol | Meaning | |------|--------|---------| | ⚡ Efficiency | E | Per-token compute does not grow with text length | | 💾 Compactness | C | Memory/state size does not grow with text length | | 🧠 Strong Recall | R | Accurately retrievable history grows proportionally with length |

The paper proves: you can have at most two of the three.

> An impossibility triangle: a structural limitation where three desirable properties of a system cannot all be satisfied — like the CAP theorem or the monetary policy trilemma.

2. Formalizing sequence models: the OSP abstraction

The paper defines an Online Sequence Processor (OSP):

\mathcal{P} = (S, \mathcal{X}, Q, A, \delta, \rho, s_0)

$$S$$ : state space; $\mathcal{X}$ : input alphabet of size $$V$$ (vocabulary); $$Q, A$$ : query and answer spaces
$\delta$ : state transition (how memory updates per token); $\rho$ : readout (how to answer queries from state); $$s_0$$ : initial state

The three wishes are formalized as:

Efficiency (E):

\text{Cost}(\delta(s_{t-1}, x_t)) \leq p(d)

Per-step transition cost is polynomial in model dimension $$d$$ , independent of sequence length $$T$$ .

Compactness (C):

|s_t|_{\text{bits}} \leq q(d)

State size in bits is polynomial in $$d$$ , independent of $$T$$ .

Strong Recall (R):

R(1-\varepsilon, \gamma T) \text{ holds for all sufficiently large } T

There exists $\gamma > 0$ such that the model recalls $\gamma T$ distinct key-value pairs with accuracy at least $1-\varepsilon$ .

3. The theorem: the impossibility triangle

Theorem 1 🔺

> Let $\mathcal{P}$ be an OSP satisfying the basic axioms with vocabulary size $V \geq 2$ . No $\mathcal{P}$ satisfies E, C, and R simultaneously.

A quantitative bound follows:

> Any model satisfying both E and C can recall at most >

n^* \leq \frac{q(d)}{(1-\varepsilon)\log V - 1}

> key-value pairs (at precision $1-\varepsilon$ ).

Since $$q(d)$$ is independent of $$T$$ , we get $n^* = O(\text{poly}(d)/\log V) = o(T)$ . As sequences grow arbitrarily long, recoverable information vanishes as a fraction of the input — even if you scale up $$d$$ , recall only grows polynomially while $$T$$ can grow without bound.

4. The proof: two information-theoretic blades

4.1 Data Processing Inequality (DPI)

X \rightarrow Y \rightarrow Z \implies I(X; Z) \leq I(X; Y)

Applied to an OSP: the input $x_{1:T}$ is first compressed into state $$s_t$$ , and answers are read out from $$s_t$$ . DPI caps the information the state can carry about the input by the state's own entropy.

4.2 Fano's inequality

Fano links recall accuracy to required information: reliably recalling $$n$$ key-value pairs demands a minimum amount of state information. With C bounding state size and DPI bounding its information content, sandwiching the two yields the upper bound on $$n^*$$ .

5. A check-up report for 52 architectures

The author maps 52 architectures (published through March 2026) onto the triangle:

| Family | Examples | E | C | R | Position | |--------|----------|---|---|---|----------| | 🔵 Transformer + KV-cache | GPT, LLaMA | ❌ | ❌ | ✅ | R vertex | | 🟢 SSM | Mamba, S4 | ✅ | ✅ | ❌ | EC edge | | 🟢 Linear RNN | RWKV, HGRN2 | ✅ | ✅ | ❌ | EC edge | | 🟢 Kernelized attention | Performer, cosFormer | ✅ | ✅ | ❌ | EC edge | | 🟡 Hybrids | Zamba, Samba | ~ | ~ | ~ | Triangle interior |

R vertex (Transformer): perfect recall, but KV-cache memory grows linearly with $$T$$ .
EC edge (Mamba, RWKV): fixed state and constant per-step compute, but recall capped at $O(\text{poly}(d)/\log V)$ — long-context details are destined to be lost.
Interior (hybrids): trade-offs vary continuously with the ratio of attention to recurrent layers — a slider, not a switch. Recall varies monotonically with the attention-layer proportion, but no hybrid can reach the (nonexistent) region where all three properties hold.

6. Experiments: the theory holds

Five representative architectures were tested on synthetic associative recall tasks:

✅ Transformer recalls nearly all key-value pairs (with exploding memory)
✅ Mamba performs well on short sequences, but recall saturates as length grows — right around the predicted $O(\text{poly}(d)/\log V)$
✅ Hybrids fall in between, consistent with their attention-layer ratio
✅ No architecture beats the theoretical ceiling

7. Practical implications

7.1 Why RAG won't die

Any fixed-memory model has a hard mathematical ceiling on precise long-context recall. Needing to find one specific fact at token 500,000 of a 1M-token document with constant compute and memory is mathematically impossible. RAG works precisely because it outsources recall to an external retrieval system, bypassing the model's memory limit.

7.2 Can Mamba replace Transformer?

Depends on the task:

Language modeling (next-token prediction): Mamba is fast and memory-efficient ✅
Precise extraction of scattered facts from long documents: Mamba will inevitably miss some ❌
Mixed workloads: hybrids like Zamba may be a compromise ⚖️

7.3 Limits of hardware optimization

The theorem is unconditional — it does not depend on implementation details or hardware. Even a quantum computer cannot break it, because this is a fundamental information-theoretic limit, not an engineering problem.

Paper details

| Field | Content | |-------|---------| | Title | The Impossibility Triangle of Long-Context Modeling | | Author | Yan Zhou | | Affiliation | School of Mathematics and Statistics, Changsha University of Science and Technology (CSUST), Changsha, Hunan 410114, China | | arXiv ID | 2605.05066 | | Published | 2026-05-06 | | Categories | cs.CL, cs.AI, cs.LG | | Key contributions | Proves the impossibility triangle (E, C, R); quantitative recall bound via DPI + Fano; classification of 52 architectures; empirical validation | | Theorem | Theorem 1: no OSP satisfies E, C, and R simultaneously | | Quantitative bound | $n^* \leq q(d) / [(1-\varepsilon)\log V - 1]$ | | Proof tools | Data processing inequality + Fano's inequality | | Classification scale | 52 architectures (as of March 2026) | | Experimental validation | 5 representative architectures on synthetic associative recall; measured capacity strictly below theoretical ceiling |