Research map / Architectures and efficiency / RNNs and normalization
Scaling Laws for Associative Memories
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies outer-product associative memories with random embeddings under Zipf-distributed tokens, deriving scaling laws in model capacity d and data size T and comparing memory storage schemes and optimizer effects.
Problem
Understanding the statistical origins of LLM scaling laws with respect to data size and model capacity, using a simple associative memory model of transformer intermediate layers with heavy-tailed (Zipf) token distributions.
Approach
Model memorization as a d x d matrix of outer products of random embeddings storing Zipf-distributed input-output associations; derive precise error rates for different weighting/thresholding schemes (error ~ d^{-(alpha-1)} + T^{-1+1/alpha} for top-P thresholding) and analyze how SGD, batch size, step size, Adam and layer norm shape the stored memory.
Key results
- Top-P thresholding with P ~ d/log(d) achieves the minimax-optimal error scaling d^{-(alpha-1)} (up to logs), and the combined error scales as T^{-1+1/alpha} + d^{-alpha+1}.
- Frequency-weighted schemes q_rho give slower error decay d^{-(alpha-1)/(2 rho alpha)}; storing all seen data (rho=0) yields a zero-one overflow transition at d about N.
- Theory predicts small learning rates and large batches store rare associations poorly, while large step sizes and small batches store more, with Adam and layer norm helping in experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace frequency weighting q(x)=p(x) with thresholded uniform weights on the top d associations | Associative memory with random embeddings · Zipf-distributed data | generalization error scaling: d^{-(\alpha-1)/2\alpha} + T^{-1+1/\alpha} -> d^{-\alpha+1} + T^{-1+1/\alpha} | Helped |
| Add thresholding at P \simeq d^{1/(2\alpha\rho + 1)} to frequency weighting q(x)=p(x)^\rho | Associative memory with random embeddings · Zipf-distributed data, infinite data | generalization error scaling: d^{-(\alpha -1) / 2\rho\alpha} -> d^{-(\alpha-1) / (2\rho\alpha + 1)} | Helped |
| Use uniform weights with \rho=0 and threshold storage at P\simeq d/\log(d) | Associative memory with random embeddings · Zipf-distributed data, finite data and finite memory | generalization error scaling: T^{-1+1/\alpha} + d^{-\alpha+1} | Helped |
| Use q(x)=1 rather than q(x)=p(x) | Associative memory trained with a large batch · Finite number of training examples | generalization error | Helped |
| Use smaller batches and more update steps instead of a large-batch update | Associative memory trained with gradient descent · Finite training data | generalization error | Helped |
| Increase the learning rate | Associative memory trained with SGD · When d > N | generalization error | Helped |
| Use a large learning rate rather than a small learning rate | Associative memory trained with SGD · Limited capacity, d < N | generalization error | Mixed |
| Schedule a large learning rate early and reduce it later | Associative memory trained with SGD · Finite-capacity associative memory | generalization error | Helped |
| Use Adam instead of naive large-batch SGD | Associative memory · Optimization-based memorization | generalization error | Helped |
| Add layer normalization | Associative memory trained with cross-entropy · Optimization-based memorization | generalization error | Helped |
| Learn the input embeddings rather than keeping random embeddings | Associative memory · N=100, M=5, d=2 | generalization error | Helped |
Surprising findings
- Learned embeddings allow zero generalization error with d=2 when M=5, contrasting with the d >= N needed for random embeddings.
Limitations
- Model is a single linear outer-product memory with deterministic labels, far from full transformers.
- Some bounds hold only up to logarithmic factors and constants.
Experimental setup
Datasets: synthetic Zipf-distributed input-output pairs
Metrics: generalization error
Baselines: q_0 (store all seen data) q_rho frequency-weighted memory top-P thresholding scheme
Builds on: Hopfield networks Adam layer normalization
Closest papers by meaning
- Learning Associative Memories with Gradient Descent (ICML 2024 · similarity 0.90)
- Factual recall in linear associative memories: sharp asymptotics and mechanistic insights (NeurIPS 2026 · similarity 0.90)
- On the Recall Scaling Laws in Mamba: A Theoretical and Mechanistic Study via Hashing (NeurIPS 2026 · similarity 0.89)
- Semantically-correlated memories in a dense associative model (ICML 2024 · similarity 0.89)
- Understanding Factual Recall in Transformers via Associative Memories (ICLR 2025 · similarity 0.89)
- Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.