# Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent

arXiv: https://arxiv.org/abs/2410.11268 · HTML: https://mlsanity.com/paper/2410.11268/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 94 of its 121 references that are in the map.
- First posted on arXiv 15 Oct 2024.

## Builds on (most cited first, 30 of 94)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Finetuned Language Models Are Zero-Shot Learners](https://mlsanity.com/paper/2109.01652/) (2021)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [Transformer Feed-Forward Layers Are Key-Value Memories](https://mlsanity.com/paper/2012.14913/) (2020)
- [Making Pre-trained Language Models Better Few-shot Learners](https://mlsanity.com/paper/2012.15723/) (2020)
- [LIMA: Less Is More for Alignment](https://mlsanity.com/paper/2305.11206/) (2023)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Super-NaturalInstructions: Generalization via Declarative Instructions on 1600+ NLP Tasks](https://mlsanity.com/paper/2204.07705/) (2022)
- [LLaMA-Adapter: Efficient Fine-tuning of Language Models with Zero-init Attention](https://mlsanity.com/paper/2303.16199/) (2023)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [Cross-Task Generalization via Natural Language Crowdsourcing Instructions](https://mlsanity.com/paper/2104.08773/) (2021)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [LLaMA-Adapter V2: Parameter-Efficient Visual Instruction Model](https://mlsanity.com/paper/2304.15010/) (2023)
- [DIN-SQL: Decomposed In-Context Learning of Text-to-SQL with Self-Correction](https://mlsanity.com/paper/2304.11015/) (2023)

## Built on by (most cited first, 22 of 22)

- [A Survey on Latent Reasoning](https://mlsanity.com/paper/2507.06203/) (2025)
- [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024)
- [Circuit Complexity Bounds for RoPE-based Transformer Architecture](https://mlsanity.com/paper/2411.07602/) (2024)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [Data Whisperer: Efficient Data Selection for Task-Specific LLM Fine-Tuning via Few-Shot In-Context Learning](https://mlsanity.com/paper/2505.12212/) (2025)
- [Enhancing Auto-regressive Chain-of-Thought through Loop-Aligned Reasoning](https://mlsanity.com/paper/2502.08482/) (2025)
- [High-Order Matching for One-Step Shortcut Diffusion Models](https://mlsanity.com/paper/2502.00688/) (2025)
- [Training-Free Looped Transformers](https://mlsanity.com/paper/2605.23872/) (2026)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent](https://mlsanity.com/paper/2504.04702/) (2025)
- [Loop the Loopies!](https://mlsanity.com/paper/2607.16051/) (2026)
- [Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data](https://mlsanity.com/paper/2601.15158/) (2026)
- [Unlocking the Theory Behind Scaling 1-Bit Neural Networks](https://mlsanity.com/paper/2411.01663/) (2024)
- [Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers](https://mlsanity.com/paper/2501.10688/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [In-Context Probing for Membership Inference in Fine-Tuned Language Models](https://mlsanity.com/paper/2512.16292/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Can Transformers Break Encryption Schemes via In-Context Learning?](https://mlsanity.com/paper/2508.10235/) (2025)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)
- [Learning to Extrapolate in Depth with Looped Transformers](https://mlsanity.com/paper/2610.14456/) (2026)

## Abstract (arXiv)

In-context learning has been recognized as a key factor in the success of Large Language Models (LLMs). It refers to the model's ability to learn patterns on the fly from provided in-context examples in the prompt during inference. Previous studies have demonstrated that the Transformer architecture used in LLMs can implement a single-step gradient descent update by processing in-context examples in a single forward pass. Recent work has further shown that, during in-context learning, a looped Transformer can implement multi-step gradient descent updates in forward passes. However, their theoretical results require an exponential number of in-context examples, n = exp(Omega(T)), where T is the number of loops or passes, to achieve a reasonably low error. In this paper, we study linear looped Transformers in-context learning on linear vector generation tasks. We show that linear looped Transformers can implement multi-step gradient descent efficiently for in-context learning. Our results demonstrate that as long as the input data has a constant condition number, e.g., n = O(d), the linear looped Transformers can achieve a small error by multi-step gradient descent during in-context learning. Furthermore, our preliminary experiments validate our theoretical analysis. Our findings reveal that the Transformer architecture possesses a stronger in-context learning capability than previously understood, offering new insights into the mechanisms behind LLMs and potentially guiding the better design of efficient inference algorithms for LLMs.