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

• Published in: arXiv.org 2024-11
• Main Authors: Hu, Jerry Yao-Chieh, Wei-Po, Wang, Gilani, Ammar, Li, Chenyang, Zhao, Song, Liu, Han
• Format: Article
• Language: English
• Subjects: Algorithms; Criteria; Lower bounds; Phase transitions; Upper bounds
• ISSN: 2331-8422

We investigate the statistical and computational limits of prompt tuning for transformer-based foundation models. Our key contributions are prompt tuning on \textit{single-head} transformers with only a \textit{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/\epsilon)\) 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 \textit{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.