Transformer theory · Statistical learning theory / Open question
The Memory Required to Reason
Long-context reasoning needs memory, but storing every past representation is expensive. The important question is which information can be discarded without changing what the model can reliably do. Efficiency payoff: Compress persistent context while controlling the error of complete generated trajectories.
Seed catalog · Showing the bundled record.
Problem statement
For finite-precision causal softmax transformers with bounded query/key/value norms, assume every reachable length-n key bank admits at most k clusters of radius r, with this promise holding for both full-cache and compressed generation over H further tokens. Determine the minimum stored bits for a streaming cache scheme to keep the two generated-token distributions within total variation epsilon. Account for cluster discovery, value aggregation and feedback of altered outputs into future queries; one-query attention error is only an intermediate bound.
Assumptions and scope
- Fix embedding dimension, numeric precision, attention norms and the model's observable output error; charge stored bits rather than an unbounded-precision real register.
- Declare a structural promise such as controlled covering complexity, relevance sparsity or task-state sufficiency, and how it persists under generated continuations.
- Separate approximation of one attention query from trajectory-distribution or task-success preservation. Queries may depend on previous compressed outputs.
What would settle it?
Matching memory/error/horizon bounds and a streaming scheme for a nontrivial structured class, or a lower bound showing that apparently compressible local attention still requires large end-to-end memory.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Haris and Onak prove worst-case KV space barriers and structured exceptions; SubGen gives clustered-key approximation guarantees. Universal sublinear attention memory is therefore not open. The residual target links a persistent structural promise to full autoregressive reasoning accuracy. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Haris and Onak — Compression Barriers in Autoregressive Transformers ↗partial theory · source checked 2026-11-19
Publisher abstract checked: worst-case linear KV space in the stated dimension regime, low-dimensional bounds and structured exceptions. General sublinear memory without assumptions is not open.
- Zandieh et al. — SubGen: Token Generation in Sublinear Time and Memory ↗related algorithm · source checked 2026-11-19
Primary search abstract checked: online key clustering and value sampling with approximation guarantees under exploitable structure. A local attention bound is not automatically an end-to-end generation guarantee.
- Chen et al. — MELODI: Exploring Memory Compression for Long Contexts ↗related algorithm · source checked 2026-11-20
Google DeepMind ICLR 2025 publication page checked: hierarchical recurrent compression and empirical memory savings. Trajectory-level approximation guarantees are a separate question.
- Cetin et al. — An Evolved Universal Transformer Memory ↗related algorithm · source checked 2026-11-20
Sakana technical overview checked: learned retention and cross-model/domain experiments. These do not prove universal zero-shot memory-policy transfer.