On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recovery

Renpu Liu, Ruida Zhou, Cong Shen, Jing Yang

Abstract

An intriguing property of the Transformer is its ability to perform in-context learning (ICL), where the model solves inference tasks without parameter updating based on demonstration pairs. While previous research suggested ICL is enabled by Transformers performing implicit gradient descent, this work demonstrates that Transformers can implement more sophisticated learning-to-optimize (L2O) algorithms. Specifically, for in-context sparse recovery (LASSO), we prove that a $K$-layer Transformer can perform an L2O algorithm with a linear convergence rate relative to $K$. This provides a new perspective on the superior ICL capabilities of shallow Transformers. Unlike conventional L2O algorithms, the trained Transformer generalizes across different measurement matrices and leverages structural information in training tasks to accelerate convergence, findings supported by our experimental results.

Introduction

In-Context Learning (ICL) remains one of the most compelling features of Large Language Models, allowing them to adapt to new tasks via prompts containing a few examples. Recent theoretical work has attempted to demystify this by framing the Transformer's forward pass as a form of implicit gradient descent. However, this explanation faces two significant hurdles: efficiency and robustness. Standard gradient descent converges at a sublinear rate, which fails to explain why shallow Transformers are so effective. Furthermore, traditional Learning-to-Optimize (L2O) methods—neural networks trained to act as optimizers—are often brittle and fail when the underlying problem structure changes between training and inference.

This paper addresses these gaps by showing that Transformers are not merely performing gradient descent; they are implementing advanced L2O algorithms capable of linear convergence and robust generalization.

The LISTA-VM Framework

The researchers focus on the problem of In-Context Sparse Recovery, typically formulated as a LASSO (Least Absolute Shrinkage and Selection Operator) problem. To bridge the gap between Transformers and optimization, they introduce a novel algorithm: Learned Iterative Soft-Thresholding Algorithm with Varying Measurements (LISTA-VM).

Mapping Architecture to Optimization

The study provides a mathematical construction showing how a $K$-layer decoder-based Transformer can explicitly implement the LISTA-VM algorithm:

  • Self-Attention Layers: These layers are utilized to calculate gradient updates and incorporate "curvature" information. In this context, the attention mechanism acts as a learned pre-conditioner, adjusting the optimization step based on the specific data in the prompt.
  • MLP Layers: The Multi-Layer Perceptron components implement the "soft-thresholding" operation—the mathematical core of sparse recovery—using ReLU activations to enforce sparsity.
  • Read-out Functions: The authors analyze how the model extracts the final solution, finding that query-based quadratic read-outs are theoretically and empirically superior to simple linear read-outs as the number of demonstration examples increases.

Key Insights: Efficiency and Generalization

Linear Convergence

A primary contribution of this work is the proof that a $K$-layer Transformer can achieve a convergence rate of $O(e^{-K})$. This linear convergence is significantly faster than the $O(1/K)$ rate associated with standard gradient descent. This explains how even models with relatively few layers can achieve high precision in solving optimization tasks in-context.

Robustness to Varying Measurements

Traditional L2O models typically have "hard-coded" weights optimized for a specific measurement matrix. If the matrix changes at test time, the model fails. In contrast, the Transformer uses its attention mechanism to make its internal optimization weights dependent on the matrix provided in the prompt. This allows the model to generalize to entirely new measurement matrices without retraining.

Structural Awareness

Transformers demonstrate an ability to "sniff out" hidden patterns within training data. For instance, if sparse signals consistently appear in specific coordinate subsets, the Transformer learns to exploit this structure, further accelerating convergence during ICL—a feat that conventional iterative solvers cannot match.

Experimental Validation

The authors validated their theory using synthetic datasets of sparse vectors and sub-Gaussian measurement matrices. They compared a constructed "Small Transformer" and an off-the-shelf GPT-2 model against classical solvers (ISTA, FISTA) and state-of-the-art L2O methods (LISTA, ALISTA).

  • Generalization Performance: When the measurement matrix varied at test time, traditional L2O methods saw error rates stall (remaining near 3.0), while the Transformer and LISTA-VM maintained high accuracy (dropping below 0.5).
  • Benchmark Superiority: Both the constructed Transformer and GPT-2 significantly outperformed classical iterative solvers like FISTA in terms of prediction loss, confirming that the forward pass executes a highly optimized version of the sparse recovery algorithm.

Conclusion and Future Work

This research shifts the understanding of ICL from simple gradient descent to a more sophisticated L2O paradigm. By proving that Transformers can achieve linear convergence and handle varying problem structures, the authors provide a robust theoretical foundation for the efficiency of the Transformer architecture.

However, limitations remain. The current proofs largely assume a noiseless scenario and are specific to sparse recovery. Future research is needed to determine if these L2O strategies extend to non-linear or non-convex optimization tasks and how different attention variants (such as FlashAttention) might influence these dynamics.

Summary updated

Abstract

An intriguing property of the Transformer is its ability to perform in-context learning (ICL), where the Transformer can solve different inference tasks without parameter updating based on the contextual information provided by the corresponding input-output demonstration pairs. It has been theoretically proved that ICL is enabled by the capability of Transformers to perform gradient-descent algorithms (Von Oswald et al., 2023a; Bai et al., 2024). This work takes a step further and shows that Transformers can perform learning-to-optimize (L2O) algorithms. Specifically, for the ICL sparse recovery (formulated as LASSO) tasks, we show that a K-layer Transformer can perform an L2O algorithm with a provable convergence rate linear in K. This provides a new perspective explaining the superior ICL capability of Transformers, even with only a few layers, which cannot be achieved by the standard gradient-descent algorithms. Moreover, unlike the conventional L2O algorithms that require the measurement matrix involved in training to match that in testing, the trained Transformer is able to solve sparse recovery problems generated with different measurement matrices. Besides, Transformers as an L2O algorithm can leverage structural information embedded in the training tasks to accelerate its convergence during ICL, and generalize across different lengths of demonstration pairs, where conventional L2O algorithms typically struggle or fail. Such theoretical findings are supported by our experimental results.
BibTeX
@inproceedings{liu2025learn,
  author = {Renpu Liu and Ruida Zhou and Cong Shen and Jing Yang},
  title = {{On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recovery}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=NHhjczmJjo},
}
Figure