Memory-augmented Transformers can implement Linear First-Order Optimization Methods

Sanchayan Dutta, Suvrit SraSubmission to ICLR 2025 · Rejected

TL;DR

While standard Transformers can simulate gradient descent during in-context learning, they struggle to capture algorithms that rely on past optimization trajectories. This paper shows that memory-augmented linear Transformers (Memformers) can theoretically implement and empirically learn Linear First-Order Methods (LFOMs)—such as Conjugate Gradient Descent (CGD) and momentum methods—by storing past attention states in memory registers. Remarkably, a Memformer using a single set of learned parameters shared across a batch can match or even outperform per-instance CGD on linear regression tasks.

What Problem Does This Paper Address?

Prior theoretical and empirical work revealed that Transformers perform implicit optimization during their forward pass—specifically simulating vanilla or preconditioned gradient descent (GD). However, practical optimization relies heavily on acceleration and momentum, which combine past gradients to navigate ill-conditioned landscapes.

Can Transformers learn more advanced, accelerated optimization algorithms? Standard attention layers struggle to maintain accumulated gradient histories across iterations. The authors tackle this question by investigating whether augmenting linear Transformers with recurrent memory registers allows them to execute and learn the broad family of Linear First-Order Methods (LFOMs).

Methods

The authors build on the linear self-attention framework (without softmax) applied to in-context linear regression:

  • CGD-like Dynamic Memory: Introduces a recurrent memory register $R_\ell$ that tracks search directions: $$R_\ell = \text{Attn}_{P_\ell, Q_\ell}(Z_\ell) + \gamma_\ell R_{\ell-1}, \quad Z_{\ell+1} = Z_\ell + \frac{\alpha_\ell}{n} R_\ell$$ Here, the attention output represents the current gradient step, while $\gamma_\ell$ and $\alpha_\ell$ emulate CGD's conjugacy update and step size.

  • General LFOM Memformer: Extends this to an arbitrary combination of past layers using element-wise Hadamard weighting $\Gamma_j^\ell \odot R_j$, allowing the network to coordinate-wise scale and combine historical updates across all preceding steps.

  • Theoretical Equivalence: The authors prove that these memory updates formally map to CGD search directions and general LFOM updates on empirical least-squares quadratic losses.
  • Multi-Head Attention & Quasi-Newton (GD++): Evaluates multi-head linear attention (aggregating multiple gradient estimates into memory) and non-zero sub-blocks to simulate truncated Neumann-series approximations to the inverse Hessian (GD++).

Datasets

The study evaluates models exclusively on synthetic in-context linear regression prompts:

  • Covariates $x^{(i)} \in \mathbb{R}^d$ and targets $w^* \in \mathbb{R}^d$ sampled from Gaussian distributions with covariance $\Sigma = U^\top D U$ (where $U$ is a random orthogonal matrix and $D$ controls conditioning: isotropic vs. non-isotropic).
  • Evaluated on problem dimensions $d = 5$ ($n = 20$ prompt tokens) and $d = 10$, using test batches generated independently from training distributions.
  • No standard real-world benchmark datasets are used.

Key Insights and Ideas

  • Memory as Gradient History: In linear Transformers, self-attention outputs correspond directly to preconditioned gradient steps. Recurrent memory registers naturally act as momentum buffers and conjugate direction trackers.
  • Shared Parameters vs. Dynamic Line Search: Classical CGD computes exact step sizes ($\alpha_n$) and conjugacy coefficients ($\gamma_n$) on the fly for each individual problem instance. In contrast, the Memformer learns static, shared parameters across a training distribution and applies them uniformly across test batches—yet still matches or surpasses instance-specific CGD.
  • Beyond CGD with Learned Preconditioners: When Memformer weight matrices are parameterized beyond scalars, the network learns non-trivial preconditioners alongside momentum, resulting in an "LFOM-like" algorithm that converges faster than standard CGD on non-isotropic data.
  • Multi-Head Attention as Variance Reduction: Increasing the number of attention heads allows different heads to capture distinct data subspaces, acting like an ensemble that stabilizes gradient updates before storing them in memory.

Key Results

  • Matching and Outperforming CGD: On non-isotropic quadratic tasks ($d=5$), the CGD-like Memformer achieves comparable log-loss convergence to true CGD. When allowed full matrix preconditioning, the LFOM Memformer clearly outperforms standard CGD (achieving $\log(\text{loss}) \approx -2.0$ vs. $-1.5$ after 4 layers).
  • Outperforming Momentum and NAG: In comparative baselines, the LFOM Memformer consistently achieves faster convergence and lower loss than Nesterov Accelerated Gradient ($\beta = 0.9, \eta = 0.03$) and Momentum GD ($\beta = 0.9, \eta = 0.005$).
  • Dominance on Small Batches: On small training batch sizes ($B=1$ and $B=10$), Memformers with scalar preconditioners show dramatic advantages over per-sample CGD (e.g., reaching $\log(\text{loss}) \le -20$ vs. $-1$ at $B=1$).
  • Scaling Depth: In tests scaling to $d=10$ with 7 layers, the Memformer matches CGD step-for-step across 6 layers and remains competitive at layer 7.
  • Head Scaling: A 5-head attention Memformer achieves faster loss reduction than a single-head architecture, empirically validating that multi-head mechanisms benefit in-context optimization.

Limitations and Future Work

  • Restricted Function Class: The analysis and empirical evaluations are limited to linear regression (quadratic loss) with linear attention (no softmax) and omit MLP blocks.
  • No Dramatic Edge on Generic Quadratics: When preconditioners dominate the convergence behavior, the authors note that memory-augmented models do not radically outperform standard preconditioned GD.
  • Computational Scaling Constraints: Training models beyond 7 layers and $d=10$ was computationally prohibitive under the authors' hardware setup (Google Colab T4 GPUs).
  • Future Directions: Extending memory mechanisms to non-quadratic objectives, nonlinear attention, and exploring learned memory gates (similar to LSTMs/GRUs) for meta-learning practical optimizers.

Summary updated

Abstract

We show that memory-augmented Transformers (Memformers) can implement linear first-order optimization methods such as conjugate gradient descent, momentum methods, and more generally, methods that linearly combines past gradients. Building on prior work that demonstrates how Transformers can simulate preconditioned gradient descent, we provide theoretical and empirical evidence that Memformers can learn more advanced optimization algorithms. Specifically, we analyze how memory registers in Memformers store suitable intermediate attention values allowing them to implement algorithms such as conjugate gradient. Our results show that Memformers can efficiently learn these methods by training on random linear regression tasks, even learning methods that outperform conjugate gradient. This work extends our knowledge about the algorithmic capabilities of Transformers, showing how they can learn complex optimization methods.
BibTeX
@misc{dutta2024memory,
  author = {Sanchayan Dutta and Suvrit Sra},
  title = {{Memory-augmented Transformers can implement Linear First-Order Optimization Methods}},
  year = {2024},
  eprint = {2410.07263},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.07263},
}
Figure