Universality and Limitations of Prompt Tuning
Authors: Yihan Wang
Jatin Chauhan
Wei Wang
Cho-Jui Hsieh
Venue: NeurIPS 2023 poster (2023)
Keywords: prompt-tuning; language model; expressive power

Abstract: Despite the demonstrated empirical efficacy of prompt tuning to adapt a pretrained language model for a new task, the theoretical underpinnings of the difference between "tuning parameters before the input" against "the tuning of model weights" are limited. We thus take one of the first steps to understand the role of soft-prompt tuning for transformer-based architectures. By considering a general purpose architecture, we analyze prompt tuning from the lens of both: universal approximation and limitations with finite-depth fixed-weight pretrained transformers for continuous-valued functions. Our universality result guarantees the existence of a strong transformer with a prompt to approximate any sequence-to-sequence function in the set of Lipschitz functions. The limitations of prompt tuning for limited-depth transformers are first proved by constructing a set of datasets, that cannot be memorized by a prompt of any length for a given single encoder layer. We also provide a lower bound on the required number of tunable prompt parameters and compare the result with the number of parameters required for a low-rank update (based on LoRA) for a single-layer setting. We finally extend our analysis to multi-layer settings by providing sufficient conditions under which the transformer can at best learn datasets from invertible functions only. Our theoretical claims are also corroborated by empirical results.

Universality and Limitations of Prompt Tuning
Yihan Wang
Jatin Chauhan UCLA
Wei Wang
UCLA vangyshan617@gmail com
UCLA
com
weiwang@cs. catwaan@cssuclaaeee ucla.
Cho-Jui Hsieh
Google and UCLA chohsieh@cs ucla edu
Abstract
Despite the demonstrated empirical efficacy of prompt tuning to adapt pretrained language model for new task, the theoretical underpinnings of the difference between "tuning parameters before the input" against "the tuning of model weights" are limited. We thus take one of the first steps understand the role of soft-prompt tuning for transformer- based architectures. By considering general purpose architecture, we analyze prompt tuning from the lens of both: universal approxi- mation and limitations with finite depth fixed-weight pretrained transformers for continuous -aauuud valued functions. Our universality result guarantees the existence of a strong transformer with prompt to approximate any geguence-t--eqqenne function in the set Lipschitz functions. The limitations of prompt tuning for limited-depth transformers are first proved by constructing set of datasets, that cannot be memorized by a prompt of any length for a given single encoder layer. We also provide a lower bound on the required number of tunable prompt parame- ters and compare the result with the number of parameters required for a low-rank update (based on LoRA) for single-layer setting. We finally extend our analysis to multi-layer settings by providing sufficient conditions under which the transformer at best learn datasets from invertible functions only. Our theoretical claims are also corroborated by empirical results.
Introduction
The surge in the empirical research of large-scale models has led to the emergence of a new paradigm of prompt tuning. Current large models consist of billions of parameters [Brown et al.) 2020 Chowdhery al. 2022 which greatly exacerbate the cost of tuning the entire model weights
tradient-based optimization. On the other hand, the power of scale in both model size and pretraining dataset size has demonstrated strong capabilities by achieving reasonable performance through
learnable prompt appended before the input (Li and Liang 2021 Lester et al.) 2021]. Despite this, several questions emanate around the abilities and limitations of prompt tuning.
In this work, we aim to characterize some natural yet essential questions about prompt tuning with transformer architectures. Firstly, are prompts universal approximators, i.e. with fixed pretrained transformer network, can we find a prompt to approximate any sequence-to-sequeee given space? yes, can we construct the transformer for this universality result? Second, can we identify failure modes of prompt tuning when applied on potentially non-optimal but non-trivial transformers? Moreover, since prompt tuning is usually compared against LoRA A (Hu et al. 2021 in consideration to parameter-effiice than LoRA? Answering these questions can lead to important insights on when and how to perform prompt tuning to adapt pretrained transformer network to a given downstream task of interest.
function in
tuning, is prompt tuning then more/less serramettr-efficieen
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this work, we seek to answer these questions with appropriate theoretical analysis and further validate our claims with empirical results. We first characterize the universal nature of prompt tuning by constructing specific transformer network. We show that for a given approximation error and the space of sequence-to-sepe to-sequece Lipschitz functions, we can construct a transformer network, with a suitable number of layers, that can leverage prompt tuning to approximate any function in this space. Despite this universality of prompt tuning with a carefully constructed pretrained transformer, we then identify some limitations of prompt tuning with weaker but non-trivial transformers. We prove this by constructing simple but cannot be memorized by prompt tuning for a given transformer. We also extend our analysis to more general settings where the shared token is not required. In this setting, we first prove that prompt tuning on a single-layer transformer requires ((n)) trainable parameters to memorize training examples, wherein for LoRA, it suffices with (n)) trainable parameters. We finally extend our analysis to the multi-layer setting and provide sufficient conditions under which prompt tuning exhibits extremely limited capacity to at best memorizing datasets from invertible functions.
datasets with shared input tokens, which are surprisingly
Our contributions can be summarized as below:
We characterize the universal nature of prompt tuning by explicitly constructing transformer network (Theorem
We provide a construction-basee argument for sequenee-to-sequene to-seuuence datasets that cannot be
learned by prompt tuning with given single-layer transformer (Theorem 2
We provide the lower bound on the required number of parameters for prompt tuning to memorize any
functions (Theorem 3).
We provide sufficient condition for multi-layer transformers, under which datasets with shared output tokens cannot be learned with prompt tuning (Theorem
We conduct empirical studies, including real-world datasets, verify our theoretical claims.
2
Related Work
Theoretical Analysis of Transformers Various works have characterized the theoretical properties of transformers and its primary self-attention component. Yun al. [2020) studies the universal approximation ability of transformers for continuous permutation equivariant sequeenceto-sseqeene functions with compact support and further examined the role of using positional encodings to circumvent permutation equivariant condition. [éérez et al. [202]] show that transformer with a hard- attention Turing complete based on their capacity perform computations and access the internal dense representations of the data. Wei et al. [2021) further shows that transformers can approximate Turing machines with bounded computation time with a new notion of approximation. (Dong et al., 2021] provides a negative yet interesting result signifying the limitations of pure self-attention in terms of rank diminishing of the input. Other works including Kim al. [202T], Dasoulas al.) [2021] derive upper bounds on the Lipschitz constant of respective modifications of the attention mechanism. The works by Li et al. 2022), Zhang et al. 2020) documented optimization perspective on transformer training via SGD.
Fine-tuning and Prompt Tuning Fine-tuning is the standard way to adapt a pretrained model to downstream tasks. The most standard and popular paradigm is tuning the model weights via suitable optimization procedure along with a linear head on the output representations [Radford et al.) 2018 Devlin et al. [019]. Subsequent works studied more parameter-efficien ways of fine-tuning by updating either a subset of model parameters [Ben Zaken et al., 2022] or restricting the parameter- updates to now-dimensional subspace (Aghajanyan et al. 202 1] Hu et al. 2021 Mahabadi et al.) 202T]. The work by Hu et al. [202T] (their framework referred to as LoRA) has garnered particular interest in the community and Malladi et al. [2023] has provided kernel mechanism. In the particular context of LLMs, prompt tuning has emerged as the de facto approach where only the prompt is updated while keeping the rest of the transformer weights and
interpretation of LoRA via the
architecture fixed [Shin et al. 2020
Lester et al. 2021 and Liang 2021
Analysis of Prompt Tuning Wei et al. 2022 studies the link between prompt tuning and down- stream tasks with an underlying latent variable generative model of text, which is confined to a Hidden Markoy Model. However, they focused on the discrete vocabulary setting contrary to our

---

results for continuous sequence-to-sequeee functions. Some more recent works [Akyürek et al. 2023 Von Oswald al. [023] characterize an intriguing property of specific form of prompting. referred to as in-context learning, where they proved by construction that transformers can implement learning algorithms for linear models based on gradient descent and closed-form ridge regression. This work however pursued a different and specific direction from the prompting results we aim to provide for generic settings.
Memorization Capacity of Neural Networks A series of works have sought to provide finite sample universal memorization capacity results neural networks and the understanding expres- sive power of neural networks. |Huang and Huang [190]. Huang and Babri 1998), [uang] (2003). Yamasaki [993] analyze the memorization capacity FNNs with sigmoid and other bounded activa- tion functions. Hardt and Ma [20T6), Zhang et al. [202T], Nguyen and Hein (2018) provide results for modern ReLU networks including FNNs and CNNs. For transformer architectures, Kim et al. prove that transformers memorize dataset with finite parameters. To the best of our knowledge, similar results for prompt tuning have not been studied in continuous settings for transformer architectures.
Transformers and Parameter Efficient Training
3.1 Preliminaries
We use the following notations throughout the paper. A bold lower case character, c.g. x, denotes vector. A bold upper case character, e.g. W, denotes matrix while Wi,. W,, and W., is the (i. j-th element, i-th row, j-th column, respectively. We use a single superscript or subscript to denote the index of matrix, e.g. X, X' denote the i-th matrix in matrices sequence. We use a and for softmax and hardmax operators, respectively. We use ReLU(v) = max(vv 0) to denote the ReLU activation function where max(-) function is applied entry-wise Cone(a), a2,-., Am) to denote a cone without its origin point where Cone(a) a2,-.., am) = (x Di a,a; aq 0). We also define the minus operation between set S and vector as S-V= ( -- S}. S). In Section 4
vector. We use
we use (a: b: c) to denote a grid (a, a + b, a 2h,.., C bb
from with interval b.
Transformer networks [Vaswani et al., 2017 are a stack of multiple transformer layers, composed subsequently. A transformer layer has two key components: MLP layer, with residual connections around both blocks. We consider the input and output to be sequences of tokens X E daxm and Y E Rd where m is the number of tokens in the sequence and d the token dimension.
attention layer and token-wise
Definition 1 (Attention Layer). We define an h-head attention layer parameterized with Wg. g. WR. W., W. between single token and a token sequence X as
Att(x,X) = Σ
(W(x)
The normalizing factor of _ is subsumed in the weight matrices Wi, for notational simplicity.
Vdea
We can then define the cross attention between two sequences X₃ E gdxm: and X2 E Rddmm (We X (X1 ):,k for simplicity):
Att(X,, X2) = [Att(x], X2), Att(x2, X2), .... At Att(Xm, X2)].
Definition 2 (Standard Transformer Layer). With definition) 7 we define standard transformer layer
7 as
MLP(X)= W22ReL 1 b,) + by + X. WyReLU + +b)) +b + X
(2)
TX) KLP(Att(X,X) +X)..
The definition here omits the layer normalization block for simplicity (following [Kim et al. 2027
We denote the set of transformer networks with h heads of size and MLP hidden neurons with Theair In Section 4 we utilize modified transformer network with hardmax operation ā instead of softmax a. We denote this modified version of transformer networks as Th.s.r
3

---

During fine-tuning, we optimize the matrices W W W in the attention layer and WT, 22, bj. b2 the MLP layer pertaining loss function C. However prompt tuning, the pretrained model weight matrices are fixed and we optimize a tunable sequence prepended to the input.
Prompt Tuning Given a pretrained transformer network T and a downstream training dataset S= [(X,, Yi)..., (Xn, Y,)), prompt tuning seeks to find prompt P IR IRd with mp tunable tokens under the loss function L:
P = arg min Σ L(o (()(P,X)))..mp Y.).
The tunable prompt P is shared amongst all the inputs task. Note that P in prompt tuning is a continuously trainable parameter, alternately referred to as soft prompt, which is different from hard prompt that the latter operates on a discrete space of predefined vocabulary. Since the representation power of soft prompts is strictly more than the hard prompts, the limitations studied in this paper also extend to hard prompts.
In the subsequent sections, we analyze the universality and limitations of prompt tuming while comparing the latter against fine-tuning and LoRA(Hu et al. 2021], which is low-rank version of model fine-tuning. In Section + we prove that prompt tuning can be universal approximators for sequence-to-sequeme to-sequence functions, while providing the construction for the same. In Sections and and [ we identify the failure modes where prompt tuning cannot learn with possibly non- non-optimal but non-trivial pretrained transformer network.
Universality of Prompt Tuning
Without loss of generality, we assume that the support and range set of all considered sequence-to- sequence functions f is 0, 1jaxm this section. We define Fr. as the collection of continuous sequence-to-sqquene
I--lisschitz functions under norm and sequence length m. For ʃ E Fz and any two inputs X, X' E [o, _]dxm, we have [[ f(X')ll < L|X X'Ilp. Furthermore, given functions f1, f2, the approximation error under p-norm (which is entry- is measured as:
- (21, - / - fxx)
(5)
Primarily, we show that there exists Transformer network T2,1,4 such that for any f FL. prompt tuning on can approximate this function upto some error budget > O.
Theorem 1. Let 1 S p < oo and O, there exist a transformer network g 72,1,4 and prompt length mp such that for any E FL we can find a prompt P E Rdxmp with
f) S
Here we use the transformer in a encoder mode which generates the m outputs one step. In Appendix C.4, similar result can be obtained for next-token prediction, which is widely used in many recent language models.
The proof is inspired from (Yun et al. 2019a which follows the typical construction based proof mechanism to show universality. Thereby, we can construct "meta-transformer" for prompt tuning to approximate any sequence-to-sequencce function with prompt tuning. Next we briefly describe the two steps for the construction of this transfrranfor..... We start by building a meta-function for FL.
Building the Meta-Function We denote the length of all inputs as m and the prompt length as mp. Then we can build sequence-to-ssquenee meta-function that accepts inputs with length + mp-
Lemma 1. For the sequence-to-sequueec function space Fr. with functions f : 10, 1 [0, 1jxxm, we can build a sequence-to-ssequeeee function g [0, 1]dxx (]dx(m,,+))) (m, - [0, (mp such that for any f E FL, we can find P E gdxmp, (L -))..mp. f) S e/2.
The complete proof is given in Appendix C.I Succinetly, we first quantize the input and output sequence space of [0, []dxm into grid G..m {0, 6, 28, ..., 8d thus leading C²
(3mmm ) jalm possible functions mappings from the input the output, in this discrete space. By

---

this quantized function space as FL = f2... fc), we can select å such that the approximation eтror for any function is less than e/2. Then we construct a of quantized prompts Go
{0, 6, 26, ..., 8) g to index these C' functions and construct a quantized function I where ((P x ).)mp
f. (X), 2....., C, for all X E Gr thereby concluding the lemma.
Next we can utilize some conclusions in YYun et al.
2019a to construct transformer for g.
Constructing the Meta-Transformer We first introduce useful lemma which enables the con- struction of a transformer for any quantized sequence-to-seqquenee function.
Lemma 2. For any given quantized function f : [0, 1]dxm + [0, 1]dxm with quantization at interval
0
1
2
m
0
1
2
m10
5, 3h E 721.1 such that f f= h with positional embedding E
1 2
The proof mainly follows the discussions in Section C of Yun et al. 2019a].. To prove this lemma, the network can be constructed in the following three steps. We first use a series of MLP layers to quantize the input to grid [0: 5 1 5jdxm and then series of attention layers to obtain a unique contextual mapping for each quantized input. Finally we can use a series of MLP layers to map the unique contextual mapping to the desired outputs. While transformer network usually stacks self-attention and MLP layers alternately within a single layer, the aforementioned construction can be trivially attained via the use of skip connections. The complete proof of Lemmal 2 is deferred to Appendix C.2
Since 9 is quantized function in grid +m,. following Lemma 2 we can find modified version of transformer h E 72,111 such that ((P, X)) h(P, X.)). The modified version of transformer g with hardmax operators can then be approximated with a standard transformer g with softmax operators by Lemma 3
Lemma 3 (Lemmaa in Yun et al. 2019a)) For each h e T2...1 0 and 1 S p < oo,
3g E 2,1,44 such that dp (h.gg) S c/2.
Since the approximation error can be treated uniformly amongst the P., we have that (p(h((P,, :D)..:::m g( (P...)).. < (p(h((P,,))) ((P...)) S e/2. Therefore, we can build transformer 22,,,, such that for any -o-renncc-----uueceeeeee f FL. we can find a quantized version Si E Fr. and the corresponding prompt P, E Gs,m, such that
(P..(PP: f) dp(o([P D.mmp: h(P,, (D) dp mDempp F.) doff..fsc..
Theorem I provides the construction for large transformer (discussed more in appendix) that is sufficient for prompt tuning to exhibit universal approximation over Lipschitz function space. However, even this strong transformer also has limitations with prompt tuning when the target function f & Fr. this an essential limitation for prompt tuning on any transformer? In the next section, we will theoretically analyze the limitations of prompt tuning with transformers and target functions under more general conditions.
5 Limitations of Prompt-Tuning Single Layer Transformer
To analyse the failure modes and therefore the limitations under the setting where a transformer has fixed pretrained weights, we follow the lens of exact memorization in the subsequent sections.
Definition 3 (Memorization of Sequence-to Sequence-to-Sqqueeee Sequence Dataset). Given sequence-to to-euuenee dataset S = ((X1, Ki),..., (X,, Yn)} where X,, Y; E Tdxmm are the input/oulput sequences, we consider function exactly memorizing datasel S if f(X;) = Y; In the following proofs of this section, we explicitly focus on the last output token, ie:
We start from the analysis on a single layer transformer and extend to multi- layer settings in Section
5

---

5.1 Failure modes of Prompt Tuning
is straightforward to note that prompt tuning has limited expressive power when the number of trainable parameters is limited. A natural question to then ask is: Does increasing the number of trainable prompt tokens suffice? While known that for MLPs, even with a single hidden layer, increasing the number of hidden neurons can memorize any training data (unn et al.) 2019b]. However, as we will prove next, this is not the case for prompt tuning. This result highlights an essential limitation of prompt tuning compared to model fine-tuning.
Before providing the theorem statement, we first outline some straightforward assumptions on the pretrained transformer and datasets, without which prompt tuning trivial loses expressive power.
We consider sequence-tar toaiceetttseeueee to-senuence datasets of the form S {X,,, Y1), (X2, Y2)...... ..... (X,: Y, with n distinct examples and a Lingl-layer single-heat head standard transformer defined in Definition The results can be directly extended to the single-layer multi-heat scenario, which skip here to avoid notational clutter.
Assumption 1 (Non-trivial conditions). We assume that all oulput tokens (Y, d.. are in the range set of MLP, otherwise the expressivity becomes trivially weak. We assume that W q. Wk. We are full rank matrices and that Att(X;, X,) + X, are distinct i= ..., Th.
Assumption 2 (Assumption for the MLP layer). We assume that d 2 2 + dim dim((MLP (y11) xo) U (MLP 2y22) (y2)) - Xo)) for the datasel constructed in Theorem 2 and token dimension d. dim(S)
measures the dimension of subspace spanned by vectors in set S and MLP-1(yy (y) = (x MLP(x) y).
We provide an example for this assumption in Example 7 and a sufficient condition in the following Lemma
Lemma 4. If Will x I|Wal2 < 1, where Ill is the matrix spectral norm, then the MLP block in Definition 2 is invertible, ie, MLP a singleton set.
ll2
Therefore, if Lemma 4 holds and d 2 4, Assumption
2 also holds.
Proof of Lemma 4 can be found in Appendix C.5 The experimental evidence in (Dong et al. 2021 shows that for most architectures, the norm of the weight matrices indeed admits small values and thus the requirement that W llla ||Wall2 is mild condition.
With these assumptions, here we introduce our first theorem on the unlearnability of prompt tuning.
Theorem 2. For single layer transformer T defined above with Assumptions and a sequence-to-sequeen ), and we cannot find a prompt P E Rdxm, with any mp > 0 such that ([P, x,)) = Y;
2 we can build
dataset S = {(X
xo], Y = (11.y1o)),, (X2 X2, xol. Y2 =
holds for any i 1, 2. The vectors Xg, X1, X2 are denoted post positional encodings.
An important feature of this dataset is that the same token Xa is shared between the two examples, and the expressive capability of prompt tuning is limited by the correlation of outputs corresponding to this token in different examples. We show a concrete example here to illustrate this theorem (note that Lemma 4 is in fact not required in the following construction) and defer the formal proof to Appendix C.6
Example 1. We consider a single-head transformer layer T, where b = b 0. W1 1rxd W₂- = _dxr, Then the token-wise MLP layer is a concatenation of two linear functions:
MLP(x)= = (W2 W1 + I)x, (W >0 0
(Wix)o 0
Here (Wix)o denotes the first element of vector Wix.
W₂ W, +I non-singular matrix. Therefore, for any y in MLP(X)'s output set, (y)) contains at most two points (y, (W2 W. + +I-'y). We arbitrarily choose Xp, Y10 and y20-
As long as d 2 6 (from Assumption 2h. we can find C1, C2 such that C1, C2 1 Y10 N20
Xp. (W2 2 W, +II)-tyinn 1000-yy1--0001 Xo, (W₂ W -1y0 - Xo, Ci .L C2. Then we choose x; and x2 such that
(Xn, X, ) C₁ and Att(Xn, X2) || C2 (Lemma in Appendix). Then Cone (Attt(xx, X1)
in
Xo) n Cone( Att((x, X2), b Xo) 0, for any
{Y10, (W + I)- and E {y20, (W2W) W, + y2 Here Cone stands for convex cone defined in Section 3.1
}.

---

If a P exists such that =(P...)) Y, holds for both i = 1, 2, then we have
Att (xo, [P. x1)) = 1 Xo:
P, A. X1) + X(P, [P, P, P)
(8)
Att (xo: [P, X2]) X Xo; PP, X2]))At((xnn X2) A(P, No:
[P, (2
where )(:;;)) is positive scalar. We also have
Att(xo, [P, P.X1l) + X MLP MLP (y1n)
Att [P (2]) + Xo MLP (y20)
(A PP X.)) xu) yso, 1,
Therefore, Att(x P) must be in both Cone a Xo. Attt(xo: X1) and Cone
Xp. Att X2)), where E {yio: (W,W, + 1) yio and b E {v20. (W₂ + +1) y2o h. which contradicts the existence of P as
X1). a xo) Cone(-Att(xx: X2), ()b..
xo) = 0. Therefore, in this example, even though we allow an arbitrary number of trainable param-
eters in prompt P. we cannot find one to exactly memorize the training set with only two training examples.
This theorem reveals an important difference between prompt tuning and adjusting the model weights directly. For any training dataset S with two training examples {(X,, Y2), (X2, Y2) J. so long as
At X1) + X₃ and Att Att(X2, (X2, X2) + X2 are distinct, MLP can easily map the post-attention features to expected output tokens with finite number of hidden neurons. As result, tuning the MLP parameters for this pretrained transformers can memorize any dataset in the form of Assumption However, prompt tuning cannot achieve this even if the number of tunable tokens -> infinity, thereby limiting the expressiveness of prompt tuning when compared to model fine-tuning.
5.2 Comparison with a More General Dataset
we constructed sequence- pernneee-t--equeeee datasets that cannot be learned by given transformer layer with prompt tuning, by utilizing the shared token between different training examples. In this section, we compare the expressive power of prompt tuning and fine-tuning under a more general dataset construction where the former requirement can be relaxed.
In Section 5.1
Since the primary essence of prompt tuning is to perform parameter-effiiien tuning, wherein we task with fewer tunable parameters, compare
seek adapt pretrained large model to prompt tuning with another parameter-efficien version of model-tuning: LoRA (Hu et al. 2021]. Succinctly, we compare the required number of parameters memorize given dataset. Again, consider a sequence-to-sequeeee
dataset S = {X1,, YI), (X2, Y2), (X., Yn)}, J. where X; [x,1 X22, .... Xim] and Y; [ya Vi2, .... Yim]. We again discuss the memorization of the last output token for simplicity and results can be directly extended.
We first give the required number of parameters of LoRA to memorize dataset S.
Lemma 5 (LoRA). For standard single-layer transformer defined in Desinition MLP hidden neurons, for any sequence-tor --sseencccee dataset satisfying Assumptions) we can apply a low-rank update to MLP weights with (nd) parameters to memorize T (X,)).m
2 with r 2
Ymm-
This lemma is derived based on the memorization capabilities of 1-hidden layer MLPs Yun et al. 2019b]. As the post-attention values for different training inputs are difffernnt from Assumption can construct a low rank update with ((nd) parameters on the MLP layer to memorize S. We defer the complete proof to Appendix C.7
For prompt tuning, we derive a result the next theorem which shows that it requires M(nd) tunable parameters to memorize some constructed dataset S with examples.
Theorem 3 (Lower bound on Tunable Prompt Parameters). For any single layer transformer defined in Definition _ there exists a sequence-to-sent tosuueenceee dataset {(X, = [x1o x1], V1g.V1113 (X2 [x20, x2), (21)) (X,, = [x x,,,, [yn. Vnil)} that satisfies Assumption training examples such that we need at least n prompt tokens in to memorize the training set, ie,
| with n < d
for ((P, X.))., = Yn to hold for all 1,2 ...,.
This dataset can be constructed by including n examples that require n linearly independent prompts tokens. The complete proof is deferred to Appendix C.8
7

---

Note that in Theorem we provide a key lower bound on the required number of prompt tokens for exact memorization and this can very well more than nd. This partially (but not necessarily) explains the worse empirical performance of prompt tuning against L under a comparable number of trainable parameters.
6 Extension to Multi-Layer Setting
In this section, we extend our analysis to multi-layer setting and provide sufficient condition under which the expressiveness of prompt tuning is restricted. An immediate consequence of our result an interesting connection to the spectral norm of soft prompts surfaces. This result provides partial understanding of the phenomenon that soft prompt P vectors typically exhibit larger norms compared to the actual input X, after the tuning.
With some further notation adjustments, we denote an H layer pretrained transformer network as g(E T) 7 72 .... 7..,,,,,, the input that the following compactness condition is satisfied:
X², and the set of possible prompts as P! We assume
[[['' X - D
s.t. [P+ X = -= ((P' X VI -I=,,1111,0 I,..., H.
Here [+] is the input to the first layer 7 with P E pl, x E x2 and || ||2 is the spectral norm. Similarly, [p#+1, " x=+++] denotes the output set.
We start by providing an upper bound to the Lipschitz constant of attention, pertaining to eq 9 This derivation is different from the works of [Dasoulas et al. 2021 Vuckovic be of independent interest.
2020 and thus can
Lemma 6. Under the compactess condition, the Lipschitz constant of the i-th attention head the 1-th transformer layer, denoted for simplicity as Att Att admits the following bound w.r.t the entire input sequence of length m:
()(()) Lip(Ate" (
(10)
and the Lipschitz constant of the entire attention block in layer I, denoted as A Att', admits the bound:
Lip(Ate((..))
(I 12 x Lip(Atti)))).
(11)
is noteworthy that this upper bound is dependent on D the spectral norm of the input prepended with the prompt. In conjunction with the following theorem, we obtain result on limited expressivity of prompt tuning by showing that the transformer becomes invertible, in consideration functions from p x X + pH+1 x X +H+ (an extension to functions of the from X' - H-1 is provided in Appendix Section C.II.
Theorem 4. A transformer g E T is invertible, ie .g..- (X) (X ( = Y is singleton set VY in range of g. if:
1. The Lipschitz constant of the attention block in each layer +' is strictly less than
2. The Lipschitz constant of the 2-layer ReLU block in each layer T², which is bounded by [ 2 x [ Ilz. is strictly less than I.
Proof of Theorem 4 can be found in Appendix C.9 Combining Lemma and Theorem 4 we observe that the invertibility is guaranteed if the upper bound for the Lipschitz constant the attention, eq 11 and the MLP layer, is strictly less than 1. In this case, we can then construct arbitrarily many datasets where two different inputs share the same output, and prompt tuning cannot learn (more subtly: memorize) these datasets with restricted prompt norm.

---

7 Experiments
7.1 Experimental Settings
In Section 7.2 we use a standard single-layer single-head transformer from Definition 2 to justify the infinite prompt-length limitation. In Section 7.3 we justify the increasing prompt norm on the pretrained LLaMA 7B model [Touvron et al., [023]. For prompt tuning and LoRA, we use the Huggingface Peft library [Mangrulkar et al. 2022 On the dataset front, we utilize the RTE subtask of SuperGlue dataset [Wang et 2019| and WMT14 En-Fr translation [Bojar et al. 2014]. More
details and hyperparameter settings can found Appendix A
7.2 Limited Expressivity of Infinite Length Prompt
We first construct the dataset following the proof of Theorem 2 and then show that prompt tuning cannot memorize this simple dataset {X] [x1, Xa), Y1 V11. (X2
[22, xo]. Y2-
(y21, even with very large prompt lengths.
We set the token dimension d 10. We follow the default pytorch weight initialization and then normalize WT, W2 such that W2ll2 x || [Will2 < 1, following Assumption 2 We randomly sample
Xo, Y10. Y20 in a uniform distribution in [0, 1)dd and construct the corresponding vectors: X1 and X2 following Theorem 2 To compute MLP (y), we follow (Kim et al., 2021 Section 4.1 with 5000 iterations at convergence. We solve ( [xo: x1l) c in Lemma with gradient descent
terminating (Attt (x,, c) < 0.0001. We repeat this setup to obtain 3 different datasets for distinct Xo: y 10, Y20 and denote these with S,, i = 1, 1,2,3.
We perform prompt tuning, MLP fine-tuning and MLP LoRA training on the constructed datasets for 5 runs and report the mean and standard deviation of per-element Mean Squared Error (MSE) loss y10. Y20 at convergence. We show the comparison between prompt-tuning and MLP fine-tuning in Figure []] As we can observe from the figure, increasing the number of soft prompt tokens post certain threshold that does not exhibit any reduction in MSE. On the contrary. fine-tuning on the MLP layer tend to easily memorize the training set by reducing the training loss to almost zero (all the three curves for fine-tuning overlap and thus not differentiated). Note that we plot the standard deviation, however it is negligible in the range. Similar to fine-tuning on the MLP layer, LoRA with width 2 on the MLP layer also achieves near-zero training loss which is less than 10-10 10 on the constructed dataset. We don't plot the comparison on Figure[]aa all the six curves are overlapped). This result validates our Theorem that LoRA can memorize dataset with n examples with trainable parameters (n)) while prompt-tuning may require more.
7.3 Increasing Prompt Spectral Norm during Tuning
As discussed in Section 6 major constraint the expressive power of prompt tuning is the spectral norm of soft prompts. In Figure 2 we plot the curve for spectral norm of soft prompt as training progresses and the loss reduces on RTE dataset. The curve for WMT14 En-Fr dataset can be found in Appendix B This trend clearly highlights that in order to counter the limit on the capacity, the spectral norm consistently increases till the training loss saturates.
8 Conclusions
In this work, we embark on exploring the capabilities of prompt tuning in the continuous regime, contrasting it with fine-tuning, as an initial endeavor towards a theoretical comprehension. We prove by construction that prompt tuning admits universal approximation within the space of Lipschitz functions. Additionally, we identified inherent limitations of prompt tuning on single-layer trans- formers by constructing theoretically difficult datasets for prompt tuning. These limitations are then extended to lulti-layer setting under a specific prompt-norm restriction.
we note that the limitation of prompt-tuning primarily arises from the correlation across different inputs. Broadly describing, prompt-tuning implements transformation different inputs via "additional attention values", which is more restrictive as compared to the transformations from MI. layers on input tokens. An interesting potential direction to improve prompt-tuning is: "designing mechanism to leverage prompting in order to generate
From the analysis in Theorem 2 and 3

---

Prampt st Laring
Prompt Spectral Norm
Validation Loss
1.1
Fine-tuiing
PromstTuring on
100
Fine-tuning on
00
Taiming MS2 loss
0.05
Ann fun-tuuiing on
3.2
0.8
0.7
0.00
1830
5003
120
120
180
230
Length of Soft Prompt
Taining Staps
Figure MSE losses at convergence for the 3 constructed datasets (following Theorem 2). We plot the bold curves with increasing prompt length in prompt tuning and dashed fixed lines in fine-tuning (all three datasets overlapping).
Figure Increasing prompt spectral norm dur- ing tuning SuperClue RTE dataset.
prompt-dependent adapter/LoRA updates". We expect have some future work focusing on designing novel prompt-tuning strategies along this direction.
Limitations While our results provide valuable insights, extending the construction in Theorem to multiple layers and deriving tighter bounds for Lemma are critical steps for deeper understanding of the limitations of prompt tuning.
Acknowledgments and Disclosure of Funding
We thank the reviewers for their invaluable feedbacks. The work is supported in part by NSF 2008177 2048280, 2325121, 233196611 3331966, ONR
References
Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the effectiveness of language model fine-tuning. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). pages 7319-7328, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/w1/2021 http:///2221..1-ooo..ao... acll-long.568 URL
https://aclanthhllgg oorg org.org///0 wttgg/2221.cao acl-looo... 558
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? investigations with linear models. In The Eleventh International
Conference on Learning Representations, 2023. URL httppss:///peerevveeee wwwpeerrvvewwnee/ffooooee www.:eeenn//re.ee
0goX4H8yN4I
Jens Behrmann, Will Grathwohl, Ricky T. Q. Chen, David Duvenaud, and Joem-Henrik Jacob- sen. Invertible residual networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, edi- tors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 573-582 PMLR, 09-15 Jun 2019. URL https://pproeeeding mlr www.sspesseeee v97 w97/bb///o
https//99/bbebbaaab http//bhhmmannnnnmm html
Elad Ben Zaken, Yoav Goldberg, and Shauli Ravfogel. BitFit:
Simple parameter-efficient fine-tuning transformer-based masked language-modet In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 1-9, Dublin, Ireland, May 2022. Association Computational L Linguistics. doi: 10. 1/22663311/1222..22 acl- s.ort.1. URL
https: www.lloyy.ooorgoooooooooo 2022 acl short.1
10

---

Ondrej Bojar, Christian Buck. Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling. Christof Monz. Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Ales Tamchyna. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the Ninth Workshop on Statistical Machine Translation, pages 12-58, Baltimore, Maryland, USA, June 2014. Association for Computational Linguistics. URL http:///s //www
aclweb.orge www.o//ggggggggggggooooooooooott httphooooogg///////////// /ttp://///////4330000000
Tom B. Brown, Benjamin Mann, Nick Ryder, Mclanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi. Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern. Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language modeling with pathways, 2022.
George Dasoulas, Kevin Scaman, and Aladin Virmaux. Lipschitz normalization for self- attfetttnnion layers with application to graph neural networks, 2021.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.1866531 I/N19-1423. URLhttps. //aclanthology org. 1423
Yihe Dong, Jean- Baptiste Cordonnier, and Andreas Loukas. Attention is not all you need: pure attention loses rank doubly exponentially with depth. In Marina Meila and Tong Zhang, edi- tors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2793-2803. PMLR, 18-24 Jul 2021. URL httips://proceeddnng. mlr. prwss/rssvvve. https//v19//oooo//// html
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint arXiv: 2016.
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models, 2021.
Guang-Bin Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE transactions on neural networks, 14(2):274-281, 2003.
Guang-Bin Huang and Haroon A Babri. Upper bounds on the number of hidden neurons in feedfor- ward networks with arbitrary bounded nonlinear activation functions. IEEE transactions on neural networks, 9(1):224-22)) 1998.
S-C Huang and Y-F Huang. Bounds on number of hidden neurons of multilayer perceptrons in classification and recognition. In 1990 IEEE International Symposium Circuits and Systems (ISCAS), pages 2500-2503. IEEE, 1990.
Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention 2021.

---

Junghwan Kim, Michelle Kim, and Barzan Mozafari. Provable memorization capacity of transformers. In The Eleventh International Conference on Learning Representations.
Brian Lester, Rami AI-Rfou, and Noah Constant. The power of scale for parameter-efficien prompt tuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 3045-3059, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 1116653/1/2021.mmllppp www.lp-mainnn222 URL https //aclanthology. org/ 2021 emnlp-main. 243
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Lunguage Processing (Volume I: Long Papers), pages 4582-4597 Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v1/20211 aal-oon...33
URL acclatoo///llnnthoooogyy org/ 22212021.200 acl 1onl-lon.... 1ong..533 353
Zhiyuan Li, Srinadh Bhojanapalli, Manzil Zaheer, Sashank Reddi, and Sanjiv Kumar. Robust training of neural networks using scale invariant architectures. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 6656-12684, PMLR, 17-23 Jul 2022. Utt.htps::/ htt.htttps//rroceeedingg mlr mlr www.press/v122/122266 html
Rabeeh Karimi Mahabadi, James Henderson, and Sebastian Ruder. Compacter: Efficient low-rank hypercomplex adapter layers, 2021.
Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora. A kernel-based view of language model fine-tuning, 2023.
Sourab Mangrulkar, Sylvain Gugger, Lysandre Debut, Belkada Younes, and Paul Sayak. Peft: State- of-the-art parameter-efficient fine-tuning methods. btapp:://githb.. com www./ugginggaa/////eeeee////// 2022.
Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep cnns. In International conference on machine learning, pages 3730-3739. PMLR, 2018.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1-35, 2021. URL http://jmirrrog/pppeeeee 22tp///2222200000/// 3020000---00 html
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training, 2018.
Taylor Shin, Yasaman Razeghi, Robert L. Logan IV au2, Eric Wallace, and Sameer Singh. Au- toprompt: Eliciting knowledge from language models with automatically generated prompts. 2020.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix. Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pages 35151-35174. PMLR, 2023.
James Vuckovic, Aristide Baratin, and Remi Tachet des Combes. A mathematical theory of attention, 2020.
Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Oner Levy, and Samuel Bowman. Superglue: stickier benchmark for general-purpose language understanding systems. Advances in neural information processing systems, 32, 2019.
12

---

Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: a case study on approximating turing machines with transformers. CoRR, abs/2107.13163, 2021. URL https
//arxiv.orz www. www.ooggggbb/aa.o..o...o...... 2107 13163
Colin Wei, Sang Michael Xie, and Tengyu Ma. Why do pretrained language models help in downstream tasks? an analysis of head and prompt tuning, 2022.
Masami Yamasaki. The lower bound of the capacity for a neural network with multiple hidden layers. In ICANN'93: Proceedings of the International Conference on Artificial Neural Networks Amsterdam, The Netherlands 13-16 September 1993 3, pages 546-549. Springer, 1993.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequeeice-to-sequenee functions? arXiv preprint arXiv:1912.10077, 2019)
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. Advances Neural Information Processing Systems, 32, 201 9b.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are trans- formers universal approximators of sequemce-to-seeqeeee functions? In International Conference on Learning Representations, 2020. URL /
net net/forunt htr///orumm//m -iddddiddd-Brrrr
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications the ACM, 64(3):107-115, 2021.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models?, 2020.
13

---

A Experimental Details
All the experiments are run on NVIDIA RTX A6000 GPU. For experiments with Llama 7B model, we use batch size 32 and learning rate 0.001. For experiment WMT14 En-Fr translation, we only compute the loss on the first 100 examples for computational efficiency.
We use Adam optimizer and optimal learning rate from grid search at 0.1 for prompt-tuning and at 0.001 for fine-tuning in Section 7.2
In Section 7.3 we use the default loss function in Huggingface implementation for causal language models. We prompt length 10 and the prompt tokens initialized the first tokens in the model vocabulary.
B Additional Experiments
As mentioned in Section 7,3 the second real world dataset used in our experiment is WMT14 En-Fr translation in order to illustrate that the spectral norm of soft prompts increases during training. We show the curve in Figure
Prompt Spectral
0.90
2,500
Norm
2.475
0.85
Valldation LOSS
2,425
2.400
2.350
10
25
Training Stops
Figure 3: Increasing prompt spectral norm during tuning on WMT14 En-Fr translation dataset.
C Proof of Lemmas and Theorems
C.1 Proof of Lemma
For the can build a sequence-to-sequence function g [0. 1]dx (1x >> [0, 1 1x (mppmm) such that for any FL, we can find P [ ( (PP,))P.,.ppp -))..m f) S e/2.
function space Fr, with functions f. [0, 1]axm [0, 1]dxm, we
Proof. we first quantize the input and output sequence space of [0, 1]dxm into grid space Gs.m (0, 6, 25, - 57dxm, which leads to = (gakm) aaxm functions considering all input and output mappings in this grid. We index these C functions as Fg = f2.., For X & Go we let f()) = f(()) if ki < Xi,, Xi, < (ki. + 1)8 and X Gom-
Then for any f E FL, we can find a function f E FL such that dp(f.f) (f()f() - ((X) 1/1 < (ʃ Im
L(md)²5. We choose 8 = 6, such that L(md) c/2. For the prompt part, we choose my such that zaxmp 2 C. Then we can build a set of quan- tized prompts in Ga,,, {0, 26, dlaxmp index these C functions. We denote this set of prompts as (P1, Pi........PPe Finally create the quantized function and let
14

---

P ))) m. (X) and O( P.. X A.mmp = =0, v. E [0. 10.1)xmm P E Gam,, For P & ms we set ( (P.))) x) = ((P x if kā < Pi.. P.j S (ki.j + 1)6 and P E Gs.mp"
Therefore, with a properly chosen ò = 81, for any f E FL. we can find P E Raxmp such that dp(f.g(P, (D.m.,))) = dp f) - c/2.
C.2
Proof of Lemma
For any given quantized function f [0, 1]dxm + [0, 1juxm
with quantization at interval 6, 3h
0
1
2
m
1
2
m
72,11 such that f f= h with positional embedding E
:
"
0 1 2
m
Proof. The proof is given following Section in Yun et [2019a] appendix. With Section C.I in Yun al. [2019a], there exists function By composed of dun token-wiss feed-forward layers with hidden layer size = and ReLU activation to implement this scalar quantization on each input element:
kō
kō st< (k + 1)6, = 0,,, m/0 -
(t) = 1- 8- md otherwise
Then with Section C.2 in Yun et al. (019aa, we can stack m(1/5)² + attention layers map all possible input sequences in grid [0 ó 8j4 x [1 0 5]d ... [m 1 8 6jd to distinct numbers which are at least 8 from each other.
Finally we only require 0(m(1/8)dm) layers to map these distinct numbers to expected outputs.
C.3 Proof of Lemma 3
Lemma 3 is alsmost the same as Yun et al. 2019a] except that we use e/2 instead e/3.
C.4 Extension of Theorem Next-token Predictors
As an extension of Theorem 1 we consider approximating set of seguence-to-sequeee functions when we use a transformer layer as a next-token predictor. We consider set of sequence-to so-eeuence
functions F,, with Lipschitz constant L under norm p. f E Fr, [0, 1]dxm - [0, 1]dx m accepts
an input of length and outputs sequence of length m2. For any X, X' [0, 10,1]axe 1]dxmi we have [If(XX) f(X')l, Ilp L||
X'Ipp-
Next we show that we can construct a transformer т which can approximate any f E FL with prompt-tuning when
it next-token predictor.
Theorem 5. For any f E FL, we can construct a transformer T such that for any f E Fr, S <0000 and O, we can find a prompt P E [0, 1]dxmp, such that (, hP))) S e, where
h(P) (PP, (2,,P-)
Ta2 (P. (D---..--
is the sereenceet--seuencc function implemented with the transformer when accepting sequences with length ma + my +
Proof. Similar to Theorem we quantize the inputs to grid of [0 1- 8] with interval 5 and set my = (8dxma))
is chosen such that L(m,d) d/ < m. 1/pp, We index the C (8dxma36dxxm different fs as f2...... fc and its sub-function to generate the i-th output token as I2- The C sequence-to-sequenec functions can then be indexed by distinct prompts. Similar to Lemma 2 we can construct transformer which can map all possible input sequences in grids [0
x ... [m 1 m 5]d, < m S mi + m2 + mp to distinct numbers.
A final series of MLP layers then map these distinct numbers to desired output vectors where inputs
15

---

in the same grid are mapped to the same output token at each step. Then for any input x E [0, 1 1 and any f², we can find prompt P, such that
|T x - - 16 (x) S m2 -1/8e
S m2 1/8e
Then we have ()()())) s.
C,5 Proof of Lemma
If W l2 W2lla <1, where || |la is the matrix spectral norm, then the MLP block in Definition is invertible, ie, MLP-1 is singleton set.
Proof. Based on the sufficient conditions for invertibility of a residual block Behrmann et al. (2019). we have that if the feedforward part of a residual block WyReLU(W , b1) with respect to some metric, i.c. its Lipschitz constant < 1, and the metric space on which is defined is complete, then MLP in e invertible. Since we are dealing with the euclidean space, any metric induced by the || lp norm for p E [1, oo] ensures the space is complete.
b2 is a contraction
The Lipschitz constant of W2ReLU W,x+bb b1) b2 is simply ||Willa x W2ll2- Thus the statement of the lemma follows.
C.6 Proof of Theorem 2
For single layer transformer t defined above with Assumptions dataset ((X; X1, xol, Y1 [yn: Y1ol), (X2 [x2, xo): Y2 Y21. )2o)))), and we cannot find
1 and we can build seq-to-seq
prompt E Rdxm, with any my > such that 7[P X,)) Y, holds for any i 2. The
vectors X1. X2 are denoted post positional encodings.
Proof. Before proving Theorem 2 first provide lemma that will be used in proof and also Theorem 3
Lemma 7. Given any E Rdxmm there are almost anywhere for which we can find another vector
X1 E daxmm such that A (xx, [x,,x1)) x1]) || e with full rank attention weights W Wk. W
Proof. If Wo c, we can just set Xo, which makes Att(xo, [Xo. x) c hold.
If W Xy let ac W Xo where R. As W. is full-rank, we can find such that
X = v = aW c. Xu- Then we will have
Att(xp, (x0+ x1l)
cxp (( ((Wxx)) W X + cxp TT ( (Wa(aW, --l)aa -W.))
exp ((Wax)) (W x))x)) + exp ((,,)) (Wa(aW.'c c- xo)))
Therefore, as long as W, Xp Y W.(W,lc), we can change a such that Att(xo, (Xo, xi)) =
3W , + (1 - ()c - W2))) where 3 exp (WWxx)))((WW)))=FFF)Fr (xx ((W,xx) (W.(aW. waw.aa..e-aeee cxx)]))
exp ((W, (Waxo))
When a 0, (xtt(xps x1), = W.X0, when a + -00 or a + oc, Att(Xp: [xo x1))
W. As Att(xo, xx)) is continuous w.r.t changing a, there must exist such that Att(Xo, Xx. x1]) c.
Pass the two input sequences X,, X₂ through the attention layer Att with any prompt P, we can get the last output token as:
Att(Xo: P,X,)) =X Xo: P, Xi) + A(P, Xo: (,Xx)))tt(xoo P)
(12)
Att(Xo. P,X,)) =X Xo. P. xtt(x X²) A(P. Xo. 2 P)
(13)
16

---

Here X(X [x1, X2]) E (0,1) 1) is positive scalar, defined as X(X1, X2, x₂)
Σ, exp(( (W,,x) (Wox2))
exp((( (WX))()))))((Wxxx)))
Xij is the jth token in X, for notation simplicity.
1. Then from equation 12 Att(xo, P) must be on Conee-AAt(xo- X1), Att(xo, [P, Xi))) and Cone(-Att(X,,
22), (xo, [P, X2))).
2. On the otherhand, as we want to memorize the two examples, we must have Axt(xo: [P,X,]] X MMP- and Att(xo, [P. X2]) + X My20)
We construct the dataset S with arbitrary Yio and Y20. Then if dim (y
xo) U
(MLP-> (y2n) (y)a)) xo)) + (Assumption 2g. we can find two vectors cı; C2 such that C C2 1
+ Xo E MLP-1
+ Xg E MLP (220) and C1 Cc. Then we can choose X1, X2 such that
Axt X1) c and (xa X2) C2 (Lemma)) 7) Combine this construction with assumption |
we have that Cone(-Att (xo, X1), Att(xo, P1)) and (ant(-Att(x)) X2). Att Att(Xo, [P. X2
has no intersection, which means that cannot find a P to memorize this constructed dataset.
C.7 Proof of Lemma
For standard for any single-layer transformer 7 defined Definition with 2 n. MLP hidden neurons, dataset satisfying Assumptions MLP weights with ((nd) parameters to memorize T(X:)..
apply low-rank update Yim-
Proof. We use MLP,(x) to denote the jth output of the MLP layer for input token x, which is
MLP 3 (x) = Iz + b2.j wk.j
x) + b1 0)
According our assumption, Att(Xim, X;) are unique vectors for i 1, ..., Then we only need use the MLP layer to map each x; At (X.m; X,) + Xim yin. where we get a new token-wise wise dataset ((x,, y1), (X2. y2), (Xn: vn)]
Then we need find Wk. a and by such that
m
MLP,(x.) = Fi.j + b2
Whs max((ax, + b1 0) Vi.jj i 1,2, ...,,,, n.j 1,2, ....
(14)
which is equivalent to constructing standard MLP to memorize dataset:
Wki max((ass x,) + b1 0) = Vo.s - Fz
Σ kmn+1
Wky max((ax; xx) + 01 0) b2.5 (15)
Follow Thoerem 1 in Yun et al. (201b]), we can construct a, bi...., bn such that for X1. X2. Xns have 2; x;), by < 21 by ... bn 2n. Then can find W1, ..., Wn, which solves equation 15 For d-dimension output, we need to find W E Raad and E Bd and b E IR.. With LoRA, we need a low-rank update of size m X n + n X d for W2. a low-rank update of size d x x for W, and update of size n for b1. which is O(n x d) in total. Normally we have m d, then we need an update with parameter size around (4n + 1)d to memorize the last token of training examples.
C.8 Proof of Theorem 3
For any single layer transformer 7 defined in Definition 2 there exists seq-to-seq dataset {(X, [X10, x1], [y10, 10. Yn))), (X, [x x2). [y20. Y21)), Y2i))) ..., (X,, [x,0= xn). [y ] that satisfies Assumption T with < training examples such that we need at least n prompt tokens in to memorize the training set, ie, for T[P,,[[PPp X.)), yu to hold for all = 1,2,
17

---

Proof. Without loss of generality, we assume W2 has no zero elements, otherwise we can just ignore this hidden neuron in MLP layer.
Rd has d bases (t. = 1,2, 2,2,... .....,dd, d). then MLP-1(y:) must be bounded on either positive or negative part of these d directions, which means there exists B 2 0 such that
vīt; |tyyll
s B. E (y (ys)). 1,
Otherwise VB > 0, 3t,, we can find a v E (y. that Te, 2 B. Meanwhile we have MLP(v) ) ++ W ReVLR W Wiv+bj). As ||v|| can be arbitrarily large, if Wiv 0. ||MLP(v)] + oo ||| + oo. Wiv + 0, [[MP[[)][ can also be arbitrarily large when increasing the norm due to the non-linearity of ReLU(W IV b1).
Then we can find set of n linearly independent vectors (C1, Cg...., cx such that (a: : a, c, 1 a, E MLP MLP MVV")(ya)} = @ by enlarging the norm of C. With the n vectors, we can begin to construct our dataset:
We set x; = C;, = 1,2...., and find X such that C; 1 Att(x;,X, X;) (Lemma
and Att(x; X;) are distinet for i 1,2,..., (Assumption 1t which makes {ar X1 X(X,,X,, x1; [P, (1) a, - Xn. A(X,, xn, [P, X,, Jx,,(x,, x,, linearly indepen- dent for any a; MLP (ya). Here ((s..-) the same as defined Section C.6
Moreover, we have
Att(x;, [P. X,)) X(X,, P, (.),,, P) X(X,, x, (x) (16)
MLP (yn) xx
Then (xt P). 10:==1,. 1,2, must be n linearly independent vectors, which requires
rank PA) = n,
(17)
where A Rm is the attention score matrix between x; and P. P Rdxmm is the prompt token sequence and W, is the attention value weight. Therefore, we must have m, 2 n.
C.9 Proof of Theorem
A transformer is invertible if:
1. The Lipschitz constant of the attention block in each layer 7' is strictly less than
2. The Lipschitz constant of the 2-layer ReLU block in each layer 7', which is bounded by [W x [[W[le ||2 is strictly less than I
Proof. This proof is based on the proof provided for lemma 4 thus we restrict ourselves to the sketch: Based the sufficient condition for invertibility in Behrmann et al. [2019] condition (1) implies that the attention block (eq [} with the residual connection, ie X Att X, X). an invertible function. Similarly, condition (2) implies that the MLP block which constitutes of the 2-layer ReLU block with
the residual connection (eq 2 also exhibit invertibility.
Thus each transformer layer 7f (eq 3) is invertible by noting that its composition of two invertible
functions. The same property ensures that the entire transformer architecture T is also invertible. D
C.10 Proof of Lemma
Under the compactness condition, the Lipschitz constant of the i-th attention head in the 1-th transformer layer, denoted for simplicity as Attil, admits the following bound w.r. the entire input sequence of length m:
Lip(Att* (.,)) < (1 8/m
(18)
and the Lipschitz constant of the entire attention block in layer I, denoted as Att', admits the bound:
Lip(Att'(.
(I 12 x Lip(Att()))).
(19)
18

---

Proof. We drop the superseripts i, in the proof to avoid notation clutter. Similarly, we denote the concatenation of the prompt matrix P and the original input matrix X, simply with X.
Derivation for single head eq 18
Consider two matrices X1 X2 E X' = (X E Rxx"; ||| < D} Denote with A1, A2 the corresponding attention matrices respectively, which can be defined as:
A = (((Wx,)) "
A o((W2X2) W X2)
(20)
The output of the attention head, denoted with Att(.) admits the following:
I A1A 222l22
(21)
Σ |
X2 le
(22)
A X2A1 X2A1 /
(23)
(I 12 X X X + | - A2lla) W
(24)
I
[| X2112 + ||A| D) wll2
(25)
where (a) holds from the spectral norm properties and in (b) we use the bounded input spectral norm assumptions. now focus on the second term A A2 in eq 25 From the bound in lemma
we have:
A - A2lla & 2 ml G|l2
(26)
where is the diagonal matrix with entires described in lemma 8 We now invoke lemma to obtaín the following:
A A2ll2 I 2/m 2 x 2| W W Wgll2D x |X X2ll2
(27)
Combining the previous inequality with eq 25 we have the following bound:
(xx)) Att - (1 + 8 m W W [
X2ll2
(28)
Derivation for the entire block eq 11:
The proof follows simply by leveraging the following property:
Property: for a matrix C = [A, B), the spectral norm of C admits the bound:
||a|| S V | + |
We then simply combine the definition of the attention block and the lipschitz constant bound in eq 18 with the above property in order to obtain the desired bound.
Lemma 8 (Dong et al. 2021 Lemma A.1). For the column stochastic matrix A obtained by performing column-wise sofumax of some matrix Z (where in our setting Z = (W& x,, T TWW, W,X,, and another row stochastic matrix A2 obtained by performing column-wise softmax of some matrix Zz where Ze Zi E (for some E, which need not belong to X), we have the following bound:
A
(29)
where the inequality is elementwise and G is a diagonal matrix with entries as G maxj,3' 18 E(5 -5.)). Here dy is a one-hot vector with the entry in the hth dimension. Lemma 9, Following the notations of (eemmaa 8 we have the following spectral norm bound:
A A2ll2 2/m Gll2
(30)
Proof. We begin by noting the following entry-wise inequality from eq 29
A₂G < A A₂ 2A2G
(31)
19

---

which ensures that ||A, A2l1= I 2| F.
We also have the following using matrix norm equivalence:
||A A2ll2 I A| A2l1æ
(32)
Invoking the matrix norm equivalence again, we have that
2| A2 -
(33)
where rank(.) is the matrix rank.
Combining the inequalities, attain the bound:
|| A2ll2 s 3/mll A2/22 |
(34)
since A₂ is column-
|| 2
0
Lemma 10. The term G in lemma 9 admits the following spectral norm bound:
||||2 2 W
||2||x X2ll2
(35)
here D the previously stated spectral norm bound of the inputs X E X²
Proof. We begin by noting that since G is square diagonal matrix with non-negative real values, the singular values of G are the corresponding diagonal elements.
We thus have that || ||||mau Since G admits the form described in lemma 8 is trivial to note that:
G|l2 where |Imaz is the maz norm.
||G max
max "..
E. Evy
(36)
2|
max Ell
(37)
where the second inequality follows from the matrix norm equivalence. Now, we can bound the last term El|2 by noting that the inputs X belong to a bounded set. This allows us provide the following bounds:
El 2 = (l X1) W X1 - (W,X2) T W X2lle
(38)
= |I( X W W (W.XI) W X2 + (WeXI) - (WxX2) T
X₂
(39)
s (|Xillal WT W a122 + |X2la W W. [12)] - X2112
(40)
< 2DD W / - X21l2
(41)
C.11 Extension of Lemma
Lemma @ and theorem 4 operate over functions from pl x X - pl+1 x x We can relax the requirement of the prompt and provide the Lipschitz constant upper bound in consideration to functions of the form X' - XL+1 by using the following assumption:
Assumption 3. Assume for simplicity that ||P| 1 = 1.
P/ll2 2 S a'|| X/ VI 1. al when
Note: A recursive expression for a' in the above assumption can be provided, but the expression does not admit a simplified form and we thus omit it here.
We will use D'x akin to eq 9 to denote the compactness corresponding the input matrix across the layers.
Based on this assumption, we have the following Lipschitz constant upper bound:
Lemma 11. The Lipschitz constant of the single head At ti admits the following bound want the input part, X of length mxx of the input sequence:
Lip(Att (1-9) < (81+10))+8//xx1)400+ (a (o)))))((W)) wT)112 |/ (42)
For Forl=1, 1, a² in the above bound.
The Lipschitz constant of the entire attention block in layer follows similarly.
20

---

Proof. For some first layer input X and prompt P, let denote the direct output of the attention head the 1-th layer with X We have the following update rule for X/:
x w P x (( (Pl.
w
W x
W PP X A
(43)
Here, Pl is the updated prompt matrix w.r. the input. For two different inputs X and X at the first layer, P P2 P. since the prompt same across inputs. A then simply the corresponding
column-stochastic matrix.
With the context clear, we now drop the superscripts i, 1, done previously. For X X2112. we have:
X X2 2
P A
[P2, A22alalaallllllllll
s (1Aill2y [P: P2ll |
X₂
P2
2
X 11 A
Azll2 ||W,ll
(44)
where the second inequality is attained using the property of spectral norm of concatenated matrices.
We now consider the term |A1 A₂ 12. By invoking lemmas and 10 we have that:
A A2/12 S 2/mx x E||2
where E [W&PP, ) W W (W P2. x2)) Wa
(45)
Invoking assumption
E |E|2 can further be bounded as:
E 2Dx 1 a (W ///2
(46)
Finally, by combining the bound for
E 2 and assumption with eq 44
obtain:
X X2l12
(47)
8/mxXx/1+ (W&))
Woll2) || (Waa)
X2l12
(48)
which provides us the desired bound.
By setting a² 0, the when there is prompt, obtain similar bound lemma 6
21


Reviews:
[{"review_id": "fsIax2N9Eo", "reviewer": "Reviewer_1J6k", "summary": "In this work, the authors embark on exploring the capabilities of prompt tuning in the continuous regime,\ncontrasting it with fine-tuning, as an initial endeavor toward theoretical comprehension. The authors prove\nby construction that prompt tuning admits universal approximation within the space of Lipschitz\nfunctions. Additionally, the authors identified inherent limitations of prompt tuning on single-layer transformers by constructing theoretically difficult datasets for prompt tuning. These limitations are then\nextended to multi-layer settings under a specific prompt-norm restriction.", "questions": "N/A", "limitations": "the authors adequately addressed the limitations in last page.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The authors characterize the universal nature of prompt tuning by explicitly constructing a transformer\nnetwork.\n\n2. The authors provide a construction-based argument for sequence-to-sequence datasets that cannot be\nlearned by prompt tuning with a given single-layer transformer.\n\n3. The authors provide the lower bound on the required number of parameters for prompt tuning to\nmemorize any sequence-to-sequence functions.\n\n4. The authors provide a sufficient condition for multi-layer transformers, under which datasets with\nshared output tokens cannot be learned with prompt tuning.\n\nOverall, this paper is well written. The hypothesis of these theories is acceptable and the theoretical analysis is solid. \n", "weaknesses": "Please add more experiments to support the theoretical result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer 1J6k for the positive feedback and valuable suggestions. For the corresponding additional experiments to validate our theorems, please see the general response. If the response satisfies your concerns, we hope that you will improve the score to reflect the same. We are happy to answer any more questions. "}, {"review_id": "mdz8f1XhEu", "reviewer": "Reviewer_VZsv", "summary": "This paper presents theoretical analysis of prompt tuning by 1) formally define the attention and prompting operations, 2) deriving the universality of prompt tuning with a strong transformer model, 3) further discussing the limitation of prompt tuning under the case of single and multi-layered transformer models. Explorative experiments on standard models and benchmark datasets demonstrate the correctness of the derived theorems.", "questions": "Please see weaknesses part.", "limitations": "No limitations or potential negative societal impacts discussed in the main context.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written with clearly defined definitions and theorem presentations.\n- Exploring prompt tuning from a theoretical perspective is very interesting and important, since better understanding the limitations of prompts is the key to improve prompting techniques.\n- The theorems seems correct and solid.", "weaknesses": "- The experimental part is a bit weak compared with the theoretical part. \n- It will be nice to have some further discussions on how to leverage the current limitations of prompt tuning to design better prompting-based models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer VZsv for the feedback and valuable suggestions. We address each of the concerns below:\n\n**Regarding additional experiments**\n\nPlease see the general response.\n\n**Regarding discussions on potential directions to improve prompt-tuning**\n\nFrom the analysis in Theorem 2 and 3, we note that the limitation of prompt-tuning primarily arises from the correlation across different inputs. Broadly describing, prompt-tuning implements transformation on different inputs via “additional attention values”, which is more restrictive as compared to the transformations from linear layer/MLP layer on input tokens. An interesting potential direction is: “designing a mechanism to leverage prompting in order to generate prompt-dependent adapter/LoRA updates”.\n\nSince the primary emphasis of the paper is to provide one of the first theoretical works to understand soft prompt tuning, we plan to focus on designing novel prompt-tuning strategies in future work.  \n\nIf the response satisfies your concerns, we hope that you will improve the score to reflect the same. We are happy to answer any more questions. \n"}, {"review_id": "EBwez6Ppv0", "reviewer": "Reviewer_E8G5", "summary": "This paper focuses on understanding the role and theoretical underpinnings of soft-prompt tuning in transformer-based architectures, which is a technique used to adapt pretrained language models for new tasks. Despite the empirical effectiveness of this method, there's a lack of theoretical understanding of how it differs from tuning the model weights.\n\nThe paper takes significant steps in several areas:\n\n1. **Universal Approximation Analysis:** The researchers prove a universality result that guarantees the existence of a transformer with a prompt that can approximate any sequence-to-sequence function within the set of Lipschitz functions, which are a class of functions that have a particular property of bounded rate of change.\n\n2. **Limitations of Limited-Depth Transformers:** The researchers construct datasets that cannot be memorized by a prompt of any length for a single-layer transformer, demonstrating the inherent limitations of prompt-tuning in this setting. The paper extends the analysis to multi-layer transformer settings, providing conditions under which transformers can only learn from invertible functions. This shows additional limitations of the transformer model.\n\n3. **Lower Bound on Tunable Prompt Parameters:** They establish a lower bound on the required number of tunable prompt parameters and compare this with the parameters needed for a low-rank update (LoRA). This helps to illuminate the resource trade-offs between these two methods.\n\n4. **Empirical Results:** The researchers also provide empirical results that back up their theoretical findings, adding credibility to their conclusions.\n", "questions": "1. How to extend the conclusion to decoder models like GPTs that can generate new content?\n\n2. Can you provide some specific examples (with detailed values) for the limitation analysis? E.g. assume the dimension $d = 1$, then x and y are all just numbers. Then I can have a better understanding of why some functions  are not learnable via prompt tuning.\n\nI'm not familiar with theoretical analysis, and skipped the proofs. I will leave the judgement of proofs to my peer reviewers and area chairs. \n\nIn addition, several typos should be fixed:\n\n\"We use the following notations throughout the paper. A bold lower case character, eg x,\": eg --> e.g.\n\n\"If yes, can we construct the a transformer for this universality result?\": the a --> a\n\n", "limitations": "Not fully addressed. The authors do not mention the limitation in encoder-only models.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "One of the strengths of the paper is its theoretical grounding. It provides a theoretical understanding of the difference between 'tuning parameters before the input' and 'the tuning of model weights'. The paper presents a strong universality result, stating the existence of a strong transformer with a prompt that can approximate any sequence-to-sequence function in the set of Lipschitz functions. \n\nIn addition, the paper presents a detailed analysis of the limitations of prompt-tuning, especially for limited-depth transformers. The authors create specific datasets that cannot be memorized by any prompt of any length for a single encoder layer. This analysis provides useful insights into the constraints of prompt-tuning.\n\nThe paper is generally easy-to-follow in idea. Although I do not check the theoretical correctness of these proofs.", "weaknesses": "\nWhile this paper takes a commendable effort in delving into the theoretical underpinnings of prompt-tuning in transformer-based architectures, it has several significant shortcomings.\n\nFirstly, the focus on sequence-to-sequence encoder models poses a substantial gap in the relevance of these findings to practical, real-world application. The universality of sequence-to-sequence transformers cannot be immediately generalized to decoder models, which are commonly used in practice and can handle an arbitrary number of output tokens. Therefore, the study needs to address how its theoretical results can be extended to these types of models. Without this, the scope of the paper's relevance becomes significantly narrow and its conclusions may not be directly applicable to most use-cases.\n\nSecondly, the reliance on the universality results from Yun et al.'s work (\"Are transformers universal approximators of sequence-to-sequence functions?\") reduces the novelty of the paper. While it is valid to build upon previous work, the authors have not demonstrated a significant extension or new application of these universality findings. It would be beneficial for the paper to provide more novel insights or extend the known results to a more general setting beyond what is already known from the referenced work.\n\nLastly, the exploration of limitations in prompt-tuning is an interesting aspect of the paper. However, the limited breadth of the experiments conducted undermines the impact of these findings. The limitation proofs revolve around specific, constructed single-layer transformers, which do not cover the wide array of transformer architectures used in practice. The implications of these limitations would be far more convincing if the authors could generalize the findings to multi-layer transformers or a wider variety of architectures.\n\nTo improve upon these shortcomings, the authors might consider broadening their analysis to include decoder models, providing more novel extensions to the universality results, and expanding the scope of their limitation analysis to apply to a broader range of transformer architectures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer E8G5 for the feedback and valuable suggestions. We have addressed each of the concerns below:\n\n**Regarding the extension of Theorem 1 to decoder models**\n\nThank you for your valuable suggestion. The universality result in Theorem 1 can be extended to decoder models with some minor modifications to the transformer network construction. \n\nFor a decoder model, the output is generated by recursively feeding it with the input and output that is already generated. Therefore, the input length can be changing throughout the generation process.\n\nTo generalize Theorem 1 to decoder models, we consider a set of L-Lipschitz sequence-to-sequence(seq2seq) functions $F_{L, M}$, where functions in $F_{L, M} $ accept an input sequence $X \\in [0, 1]^{d \\times m}$, $1 \\leq m \\leq M$ and $M$ is the maximum input/output length. \nWe can prove that a transformer network $\\tau$ can be constructed such that for any $f \\in F_{L, M}, X\\in[0, 1]^{d \\times m}, m \\leq M$ and $\\epsilon > 0$, we can find a prompt $P \\in [0, 1]^{d \\times m_p}$ such that $d(\\tau([P, X])_{:, m_p:}, f(X)) \\leq \\epsilon$.\n\nThe key idea is that the same attention layers used in Lemma 2 proof can generate unique contextual mappings for inputs with arbitrary lengths $m \\leq M$. Therefore, we only need to increase the capacity of the final series of MLP layers to map the additional contextual mappings for $m \\lt M$.\n\nBy constructing the final series of MLP layers, $\\tau$ can approximate the desired output token for any input sequence at each generation iteration with an appropriate prompt $P$, which can therefore approximate any seq2seq function under the setting of decoder models.\n\nWe will add this extension and detailed proof in our revision of the manuscript.\n\n**Regarding the novelty of Theorem 1**\n\nAlthough proof of Theorem 1 is partially dependent on some lemmas (Part of Lemma 2 and Lemma 3) from Yun et al, from a technical viewpoint Lemma 1 is non-trivial and reduces the construction of a transformer network for universal prompt-tuning to the construction of a transformer network for a meta sequence-to-sequence function, which allows us to leverage some lemmas from Yun et al. Furthermore, we would like to emphasize that we are the first ones to construct a transformer for universal prompt-tuning in the continuous setting. This opens up a broad arena for future work. \n\n**Regarding the implications of limitation results**\n\nOur limitation results in Theorem 2 and 3 apply to standard single-layer transformers under mild assumptions (Assumption 2 and 3), which are building blocks of a variety of transformer networks. Therefore, studying the limitation of single-layer transformer layers provides a lot of insights for general transformer networks. For analysis on multi-layer transformers, as the reviewer has pointed out already in the paper summary, we have extended to multi-layer transformers in Theorem 4, which provides conditions under which these general purpose transformers learn a very small class of functions and are thus weak.\n\n**Regarding examples with $d=1$**\n\nAs we have discussed in Assumption 2, which is a prerequisite assumption for Theorem 2, the dimension of a token $d$ should satisfy $d \\geq 2 + \\text{dim}((\\text{MLP}^{-1}(y_{10}) - x_0) \\cup (\\text{MLP}^{-1}(y_{20} )- x_0))$ where $\\text{dim}(Q)$ measures the dimension of a subspace spanned by vectors in the set $Q$. Therefore, $d$ should be at least 3 in our analysis, which is also a reasonable assumption in practical seq2seq datasets.\n\n**Typos**\n\nWe will fix the typos in the updated version of the manuscript.\n\nIf the response satisfies your concerns, we hope that you will improve the score to reflect the same. We are happy to answer any more questions.  \n\n\n"}, {"review_id": "v63y7ZbKv1", "reviewer": "Reviewer_adez", "summary": "This paper wants to provide the insights on \"when and how to perform prompt tuning to adapt a pretrained transformer to downstream tasks\", by theoretically quantifying the universality (i.e., universal approximators) and limitations (i.e., representation capacity) of prompt tuning, in complementing a lot of work focusing on empirically improve soft prompt tuning, such as better initialization or hyper-parameter tuning. Crucially, they show prompt tuning with theoretically very strong transformer models can approximate any seq2seq functions in the set of Lipschitz functions, and they theoretically and empirically show some limitations on weaker transformers (constructed seq2seq datasets as low bounds) by their relatively lower memorization ability. ", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This work shows the universality of prompts to the Lipschitz function space, and the limitations of prompt tuning at their memorization ability. The proofs are interesting and well-guaranteed. \n2. The mathematical derivations do show your deliberate thinking and rigorous reasoning. \n3. The paper writing is almost well-structured. ", "weaknesses": "1. Just for curious, you define F_L by directly posting the L-lipschitz functions. However, indeed, this causes some unavoidable confusions to readers, as what are \"L-lipschitz functions\"? Can you provide any context? Especially for some highly theoretical papers?\n2. Some writings make me confusing, even though the general structure looks good. \n3. Just one question: Is the first section of universality looks very similar to your cited ICLR work on Transformer's universal approximators?  \n\nI am happy to raise scores if you can make this more clear to me, such that this highly theoretical paper can obtain a more rigorous consideration for its ratings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer adez for the feedback and valuable suggestions. We have addressed each of the concerns below:\n\n**Regarding explanation on L-Lipschitz function**\n\nIn this work, we consider a sequence-to-sequence function $f$ with input $X \\in [0, 1]^{d \\times m}$. $f$ is an L-Lipschitz function under norm $p$ if $\\|f(X_1) - f(X_2)\\|_p \\leq L \\|X_1 - X_2\\|_p$. \nBroadly speaking, the Lipschitz property allows the following: give some function $f$ and two distinct inputs $x_1, x_2$, we can bound the difference between the outputs $f(x_1), f(x_2)$ (under some metric) via the difference between the inputs (under a potentially different metric), along with a constant which is the Lipschitz constant. We will provide a more formal definition in the updated version of the manuscript.\n\nIntuitively, this property means the function is continuous in the sense that two close-by inputs are mapped to two close-by outputs, which is a commonly used assumption in theoretical analysis. This property ensures that the approximation error is bounded when we quantize the input/output of seq2seq functions under consideration in Lemma 1.\n\n**Regarding the novelty of Theorem 1**\n\nYes, in the proof of Theorem 1, part of Lemma 2 and Lemma 3 are borrowed from Yun et. al. However, as discussed previously, from a technical viewpoint Lemma 1 is non-trivial and reduces the construction of a transformer network for universal prompt-tuning to the construction of a transformer network for a meta sequence-to-sequence function, which allows us to leverage some lemmas from Yun et al. Furthermore, we would like to emphasize that we are the first ones to construct a transformer for universal prompt-tuning in the continuous setting. This opens up a broad arena for future work. \n\nIf the response satisfies your concerns, we hope that you will improve the score to reflect the same. We are happy to answer any more questions. \n\n"}, {"review_id": "SARk1XgSIY", "reviewer": "Reviewer_AVty", "summary": "This paper examines the theoretical capacity and limitations of prompt tuning. The authors have demonstrated the possibility of constructing a large transformer model that is sufficient for prompt-tuning to exhibit universal approximation over a Lipschitz function space. However, they have also shown the limitations of prompt tuning compared to model fine-tuning by constructing sequence-to-sequence datasets that cannot be learned by prompt-tuning with a given single-layer transformer, even if the soft-prompt embedding size approaches infinity. Additionally, compared with LoRA, prompt-tuning may require more prompt tokens for exact memorization.", "questions": "Please respond to questions in the \"Weaknesses\" section.", "limitations": "some assumptions are given and not sure whether they are applied in real-world applications ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Originality\n    - This paper has pretty good originality. It first theoretically studies the theoretical capacity and limitations of prompt tuning.\n\n- Clarity\n    - The structures are clear and conclusions are emphasized.\n\n- Significance\n    - The problem studied in this paper is important", "weaknesses": "- The authors have conducted experiments to support the proposed limitation. However, additional experimental verifications may be necessary to reinforce the theoretical claims and demonstrate the impact on a wider range of tasks and datasets.\n\n- The authors have created sequence-to-sequence datasets that are simple in structure but cannot be memorized by prompt-tuning for a given transformer model. Therefore, they argue that prompt-tuning has limited expressiveness compared to model fine-tuning. However, is memorization typically necessary in real-world applications? Does memorization lead to overfitting? As I understand it, such a phenomenon could also be viewed as a potential advantage in preventing overfitting and achieving generalization ability in the process of downstream adaptation.\n\n- The authors have provided quite a few mathematical proofs and concluded several insights. I wonder whether there are any guidance for practical prompt-tuning applications.  For example, they provide a lower bound on the required number of prompt tokens for exact memorization and point out that such lower bound can be higher than LoRA’s. I would like to know that on which scenarios this could happen and it is recommended to user LoRA rather than prompt-tuning.\n\n- The authors need to correct some minor typos.\n    - line 30, typo:  the or a\n    - line 503, line 508, are they the same reference?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer AVty for the feedback and valuable suggestions. We have addressed each of the concerns below:\n\n**Regarding additional experiments on more datasets**\n\nPlease see our general response for experiments on additional datasets\n\n**Significance of memorization capacity of neural networks**\n\nMemorization capacity is a measurement of the representation power of a neural network architecture. For universal approximators like MLP networks, we can control their memorization capability (expressive power) by changing its depth or breadth to avoid underfitting on complicated data. However, as shown in our theorems, prompt-tuning has an essential limitation that some datasets cannot be memorized even with an infinite number of trainable tokens, which can lead to severe underfitting on datasets that cannot be resolved by merely increasing the number of trainable parameters. \n\nWe also emphasize that the role of memorization here is in the context of theoretically characterizing the representative power of neural networks and is not directly associated with overfitting, which results in poor accuracy numbers or task specific metrics.\n\n**Regarding scenarios where LoRA is better than prompt-tuning**\n\nA concrete example of when prompt-tuning needs more trainable parameters is Theorem 2 where prompt-tuning cannot memorize the constructed dataset with even an infinite number of trainable tokens. \n\nFor more general cases, in eq(16) $m_p \\geq n$ does not guarantee that $rank(A) =n$, which is dependent on the property of the dataset $X_1, …, X_n$. If $rank(A) < n$ for prompt length $m_p = O(n)$, prompt-tuning requires more trainable parameters than LoRA. ( eq(16) in the appendix should be $rank(W_v P A^T) = n$ due to a typo in the submitted version, which will be corrected in the updated manuscript)\n\nMore practically speaking, since the representative power of prompt tuning is worse than LORA, prompt tuning can only capture functions that deviated not too much from the given transformer. Therefore, when the target task is closer to the pretraining task, prompt tuning would be suitable; while when the target task is drastically different from the pretraining task, prompt tuning may not be able to capture the function and thus LORA could be a better choice.\n\n**Some assumptions are given and not sure whether they are applied in real-world applications**\n\nWe made two assumptions in Section 5. Assumption 1 ensures that our analysis is conducted under a non-trivial setting where prompt-tuning and LoRA won’t lose their expressive power trivially.  Assumption 2 is required for the limitation result in Theorem 2. As we have discussed in Lemma 4 and Example 1, this assumption is mild and is supported by some related empirical works.\n\n**Typos**\n\nWe will fix the typos in the updated version of the manuscript.\n\nIf the response satisfies your concerns, we hope that you will improve the score to reflect the same. We are happy to answer any more questions.\n\n\n"}]

Author rebuttal:
We thank all the reviewers for their feedback and valuable suggestions. 

**General response on additional experiments**

As requested by most reviewers, we add additional experiments to further validate our theoretical results in the paper.

In Section 7, we designed two experiments to validate our main results for single-layer and multi-layer transformer networks, respectively. In addition to Figure 2, we have another plot for the dataset (WMT14 EnFr) in Appendix Figure 3. Here we did an additional experiment on WMT16 EnDe and showed the spectral norm of soft prompt and loss in the following table.

| Steps                        | 5      | 10     | 15     | 20     | 25     | 30     | 35     | 40     | 45     | 50     |
|------------------------------|--------|--------|--------|--------|--------|--------|--------|--------|--------|--------|
| Spectral Norm of Soft Prompt | 2.4254 | 2.4728 | 2.5173 | 2.5465 | 2.5646 | 2.5772 | 2.5864 | 2.5900 | 2.5910 | 2.5912 |
| Validation Loss              | 0.9478 | 0.9201 | 0.9008 | 0.9062 | 0.8910 | 0.8917 | 0.8915 | 0.8967 | 0.8970 | 0.8959 |


As we can see from Figure 3 and this table, the results are consistent with Figure 2 that there is a clear trend of increasing spectral norm of soft prompt during prompt-tuning, which validates our theoretical analysis in Theorem 4.

For Figure 1, we did an additional experiment to show that LoRA can perfectly memorize the constructed dataset with two examples with LoRA width $r=2$. With LoRA width $r=2$, it can achieve training loss close to 0 (less than 1e-10) which is similar to the performance of full-fine tuning on the constructed dataset. This additional result validates our Theorem 3 that LoRA can memorize a dataset with $n$ examples with trainable parameters $O(n)$ while prompt-tuning may require more.

We will add the additional experiment results and figures in our future manuscript. We hope the reviewers can re-evaluate our work based on these responses.



Meta-review: The reviewers' feedback reflects a positive assessment of the paper's theoretical foundations and contributions. They highlight the paper's exploration of prompt tuning in the continuous regime, backed by theoretical analyses and proofs. The proven universal approximation capability within the Lipschitz functions space is acknowledged as a key strength. Through the reviewers-authors discussion phase, the reviewers express satisfaction with the provided clarifications and improvements, leading to an increased rating. Additionally, the authors are suggested to consider discussing potential directions for enhancing prompt methods based on the presented analysis.
Decision: Accept (poster)