# Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiency

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2024.

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

- [On Statistical Rates of Conditional Diffusion Transformers: Approximation, Estimation and Minimax Optimality](https://mlsanity.com/paper/2411.17522/) (2024)
- [T2VWorldBench: A Benchmark for Evaluating World Knowledge in Text-to-Video Generation](https://mlsanity.com/paper/2507.18107/) (2025)
- [Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting](https://mlsanity.com/paper/2510.04401/) (2025)
- [High-Order Matching for One-Step Shortcut Diffusion Models](https://mlsanity.com/paper/2502.00688/) (2025)
- [A Theoretical Analysis of Discrete Flow Matching Generative Models](https://mlsanity.com/paper/2509.22623/) (2025)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation](https://mlsanity.com/paper/2502.00500/) (2025)
- [Circuit Complexity Bounds for Visual Autoregressive Model](https://mlsanity.com/paper/2501.04299/) (2025)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [T2VTextBench: A Human Evaluation Benchmark for Textual Control in Video Generation Models](https://mlsanity.com/paper/2505.04946/) (2025)
- [Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective](https://mlsanity.com/paper/2504.13558/) (2025)
- [Approximation Bounds for Transformer Networks with Application to Regression](https://mlsanity.com/paper/2504.12175/) (2025)
- [Memory Limitations of Prompt Tuning in Transformers](https://mlsanity.com/paper/2509.00421/) (2025)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [A unified framework for establishing the universal approximation of transformer-type architectures](https://mlsanity.com/paper/2506.23551/) (2025)
- [Training-Free Universal Approximation by Prompting Random Transformers](https://mlsanity.com/paper/2608.09558/) (2026)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)
- [Transformer Approximations from ReLUs](https://mlsanity.com/paper/2604.24878/) (2026)
- [Approximation Error Upper and Lower Bounds for H"older Class with Transformers](https://mlsanity.com/paper/2605.07463/) (2026)
- [How Many Different Outputs Can a Transformer Generate?](https://mlsanity.com/paper/2605.22223/) (2026)
- [On the Capability and Limitation of Hard Prompt](https://mlsanity.com/paper/2609.32302/) (2026)
- [When Can Prefixes Compile LoRA? Exact Resource-Capped Tests for Frozen Attention](https://mlsanity.com/paper/2609.36766/) (2026)

## Abstract (arXiv)

We investigate the statistical and computational limits of prompt tuning for transformer-based foundation models. Our key contributions are prompt tuning on single-head transformers with only a single self-attention layer: (i) is universal, and (ii) supports efficient (even almost-linear time) algorithms under the Strong Exponential Time Hypothesis (SETH). Statistically, we prove that prompt tuning on such simplest possible transformers are universal approximators for sequence-to-sequence Lipschitz functions. In addition, we provide an exponential-in-dL and -in-(1/ε) lower bound on the required soft-prompt tokens for prompt tuning to memorize any dataset with 1-layer, 1-head transformers. Computationally, we identify a phase transition in the efficiency of prompt tuning, determined by the norm of the soft-prompt-induced keys and queries, and provide an upper bound criterion. Beyond this criterion, no sub-quadratic (efficient) algorithm for prompt tuning exists under SETH. Within this criterion, we showcase our theory by proving the existence of almost-linear time prompt tuning inference algorithms. These fundamental limits provide important necessary conditions for designing expressive and efficient prompt tuning methods for practitioners.