Abstract
Recent research has demonstrated that Transformers can perform In-Context Learning (ICL), effectively acting as optimization algorithms during their forward pass. However, standard architectures often struggle to implement sophisticated algorithms that require memory of past steps, such as Conjugate Gradient Descent (CGD). This paper shows that memory-augmented Transformers (Memformers) are powerful enough to implement and learn the entire class of Linear First-Order Methods (LFOMs). By treating optimization as a learnable task, these models can discover meta-optimization strategies that outperform classical hand-designed algorithms on specific data distributions.
Introduction
The ability of Transformers to simulate gradient-based optimization is a key driver of their success in in-context learning. While simple Gradient Descent (GD) can be approximated by standard layers, more advanced methods like CGD or Nesterov’s Accelerated Gradient require storing and linearly combining past gradients. This work investigates whether the addition of memory—via the Memformer architecture—allows Transformers to efficiently learn and execute these advanced optimization techniques.
Methodology
The authors utilize Memformers, which retain intermediate attention values across layers, providing the necessary "memory" for LFOMs. Key technical contributions include:
- Theoretical Framework: Rigorous proofs showing that specific Memformer configurations exactly replicate CGD and general LFOM iterations.
- Learnable LFOMs: Optimization parameters (e.g., step sizes and conjugacy coefficients) are treated as learnable weights shared across a data distribution, enabling the discovery of "average-case" optimal strategies.
- Mixture-of-Experts (MoE): A gating mechanism is used to handle Out-of-Distribution (OOD) samples by specializing attention heads for different data variances, allowing for test-time adaptation.
- Linear Transformer Analysis: The study focuses on Linear Transformers (omitting softmax) to analyze the loss landscape and prove equivalence to preconditioned gradient methods.
Key Results
Empirical evaluations on synthetic benchmarks, such as Random Linear Regression and Gaussian Mixture Models, highlight the advantages of the Memformer approach.
The Average-Case Advantage
Unlike classical CGD, which calculates optimal parameters for every single sample, a Memformer learns a single set of weights that works best on average for a distribution. This "meta-learned" approach allows the model to exploit statistical regularities in the data that sample-specific optimization ignores. The Memformer's superiority is most pronounced in small batch size settings ($B=1$ or $10$), where it learns highly efficient parameters that classical methods—running independently on each sample—cannot match.
As shown in Figure 2, the "Memformer with CGD" consistently achieves lower loss than classical CGD and other first-order methods like Nesterov AGM and Momentum GD. This demonstrates the power of meta-learning optimization parameters for a specific distribution.
Algorithm Discovery and Generalization
The "LFOM Memformer" variant demonstrates the model's ability to generalize across the entire class of linear first-order methods. By incorporating blocks that approximate the Hessian inverse (akin to quasi-Newton methods), the Memformer can achieve even faster convergence, rivaling second-order methods in some scenarios.
Figure 3 further illustrates that the "LFOM Memformer" outperforms classical baselines on non-isotropic data. The results confirm that memory is the critical architectural component required to unlock history-dependent optimization algorithms within the Transformer framework. Additionally, the MoE-based approach successfully adapted to unseen variances in Gaussian inputs, maintaining low loss where fixed-parameter models failed.
Discussion and Conclusion
This work frames LFOMs as statistically learnable algorithms, moving beyond hand-designed optimization techniques. By leveraging memory, Memformers can implement a broad class of first-order methods and even approximate second-order effects through meta-learning. While currently focused on quadratic objectives, future work will explore non-convex landscapes and the computational trade-offs of Transformer-based optimization. This research marks a significant step toward machine-discovered optimization strategies tailored for specific domains.
Summary updated