← All AI/ML open problems

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.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-19

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

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

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

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

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