Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiency
We investigate the statistical and computational limits of prompt tuning for transformer-based foundation models. Our key contributions are that prompt tuning on *single-head* transformers with only a *single* self-attention layer: (i) is universal, and (ii) supports efficient (even almost-linear…