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