Repeat after me: Transformers are better than state space models at copying

arXiv:2402.01032v2 (3 June 2024), Harvard University (Kempner Institute; Center of Mathematical Sciences and Applications). ICML 2024, PMLR 235, as printed. Read by researcher R4f for research batch R4 (recurrence for the base and the person slot), 5 October 2026. Provenance: papers/base/jelassi2024_copying.provenance.json.

What was read

• Read in full: every line of the pdftotext conversion (20 pages, 1,816 lines): abstract, Sections 1–6, impact statement, references, and Appendices A (positional encodings, training and evaluation), B (data efficiency, uniform-string copying, n-gram models), C (proof of the upper bound: Theorem 2.3, Lemma 2.4, Lemmas C.1–C.4) and D (proof of the lower bound: Theorem 2.7, Lemma D.1).
• Not read: figure contents. The text holds only axis labels, legends and captions, so results come from text and captions; no number is read off a curve. The two-column layout interleaves in the extraction and was read back into order.

What they did

• Defined "generalized state space models" (GSSMs): any sequence model whose input-dependent memory is a fixed-size state S, updated by s_i = u(s_{i−1}, x_i), with mem(S) = log|S| bits.
  • The class covers S4, Mamba, LSTMs, linear attention and parallel RNNs such as RWKV and RetNet.
  • The bound limits input-dependent memory only (activations, the state). Parameters and the cost of updates are unconstrained (Remark 2.1).
• Theory on copying a uniform random string of length L over an alphabet of D tokens.
• Training from scratch on synthetic tasks at about 160M parameters, with a 26-letter alphabet and contexts packed with examples:
  • Transformers (GPT-NeoX, 12 layers, width 1,024, 16 heads) with RoPE, NoPE, ALiBi or their own "Hard-ALiBi";
  • Mamba (24 layers, width 1,024, state size swept from 16 to 256; 32 was best);
  • an LSTM of about 40M parameters (4 layers).
• Pretrained comparisons: Pythia 410M, 1.4B and 2.8B against Mamba 360M, 1.4B and 2.8B (as labelled). All were trained on the Pile with the same tokenizer; Mamba has slightly lower perplexity.

Main results (verified)

• The lower bound (Theorem 2.7). Any GSSM's error on uniform copying of length L exceeds 1 − |S|/D^L. By Corollary 2.8, with mem(S) < L·log D − 1 bits the error exceeds 1/2. A fixed-size state cannot copy a string with more bits than it holds.
• The upper bound (Theorem 2.3). A depth-2 Transformer of dimension O(n log D) copies strings of length up to D^n. Its error is below the probability of a repeated n-gram, which for uniform strings is under L²·D^−n (Lemma 2.4).
  • Mechanism: hash n-grams, attend to the previous occurrence of the current n-gram, and output the token that followed it.
  • Its input-dependent memory, Õ(L), is optimal up to logarithmic factors.
• Learning to copy at about 160M:
  • for strings of up to 300 tokens, Transformers needed about 100× fewer training examples than the best GSSM;
  • for strings of up to 30 tokens, Mamba needed about 10× more than Transformers and the LSTM about 100× more;
  • the LSTM could not learn length-300 copying at all, even scored per character.
• Length generalisation (trained on up to 50 tokens, tested up to 1,000):
  • the GSSMs (LSTM, Mamba) drop to zero "almost immediately" beyond the training length;
  • Transformers decay gradually;
  • the Hard-ALiBi Transformer copies almost perfectly up to 1,000.
• How Transformers copy. Accuracy falls once inputs contain duplicated n-grams of 5 or more tokens, and the Hard-ALiBi Transformer matches a perfect 5-gram model. Transformers copy by n-gram lookup.
• Lookup with the key after the text against before it:
  • With the query after the text, Transformers trained on up to 30 tokens generalise to 100 with a small drop; GSSMs do poorly beyond their training lengths.
  • With the key given before the text, GSSMs generalise perfectly and beat the NoPE and ALiBi Transformers, though not Hard-ALiBi. They "can write the key into the state and then ignore inputs that do not match".
  • The authors' summary: GSSMs "can be effective when the tasks only require a summary of the inputs rather than storing the entire context."
• Pretrained models:
  • Phone-book lookup: once the book has 70 or more entries, even Pythia-410M beats Mamba-2.8B. The prompt format is stated inconsistently: the text says two examples, the caption says 1-shot.
  • Copying C4 text: the smallest Transformer "dramatically outperforms" the largest GSSM, even though the GSSM has enough bits to hold the text.
  • Shuffled words: both model families lose accuracy, the GSSMs more; the largest GSSM reaches zero at 300 tokens.
  • Uniform random strings: Pythia-1.4B copies almost 100%; Mamba degrades.
  • SQuAD (2.8B, one demonstration, F1 by paragraph length): the two are equal on short paragraphs, and Mamba degrades faster as paragraphs grow.
• Where GSSMs are better (cited, not tested here): tracking a small O(1) state variable over time (flip-flop languages, Liu et al. 2023), and very long inputs such as DNA.
• The authors' conclusion: build hybrids that give SSMs an attention-like mechanism. "Humans have an incredibly limited capacity for memorizing sequences ... but can translate entire novels if we allow them to look back at the text."
• Compute: about 600 GPU-hours (RTX8000) for the final runs.

Limits

• The theorem concerns uniform random strings. Natural text compresses, and the shuffling experiment shows that compressibility helps GSSMs.
• The synthetic experiments use about 160M parameters and one hyperparameter setting each.
• The pretrained comparison uses early Mamba (Pile, 300B tokens); no hybrid is trained, and nothing is fine-tuned to fix copying.
• Most results are in figures; the text gives qualitative descriptions and a few thresholds.

What it means for the base (inference)

• The loss is fundamental, not a training shortfall. No recurrent state, however it is trained, holds more bits than its size. Exact recall of a growing record needs memory that grows with the record. Waleffe 2024's 8B phone-book failure is one instance of this bound.
• A verbatim episodic record must live outside any fixed-size state: an external store, read by attention or retrieval, as B2 already requires. The same bound covers memory tokens in recurrent-memory Transformers and xLSTM's matrix memory, because both are fixed-size input-dependent states.
• What a state can keep: a summary, and what it was told in advance to look for. That suits a small, slowly changing code (a mood, a person setting), not a person's memories.
• Perplexity does not reveal the loss. Mamba had lower perplexity than Pythia and still lost at copying and lookup, so a backbone comparison must include recall probes.