Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiency
Authors: Jerry Yao-Chieh Hu
Wei-Po Wang
Ammar Gilani
Chenyang Li
Zhao Song
Han Liu
Venue: ICLR 2025 Poster (2025)
Keywords: Foundation Model
Prompt Tuning
Transformer
Universal Approximation
Memory Capacity
Computational Efficiency
Fine-Grained Complexity
Primary area: foundation or frontier models, including LLMs
TL;DR: We study the statistical and computational limits of prompt tuning in single-layer, single-head transformer, showing it is universal seq2seq approximator and, supports almost linear efficient inference.

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

Published as a conference paper at ICLR 2025
FUNDAMENTAL LIMITS OF PROMPT TUNING TRANS- FORMERS: UNIVERSALITY, CAPACITY AND EFFICIENCY
Jerry Yao-Chieh Hu*
Wei-Po Wang*t
Ammar Gilani!
Chenyang Li
Zhao Song
Han Liu'
Northwestern University
National Taiwan University
FFuzhou University
UC Berkeley
(hu, emmargilan12224 oo edu, bo9202009entu.cdu. tw
{ (1chenyang550, magic. linuxkde| agmail.com, hanl baniiu@northwwstrrr.coo
ABSTRACT
We investigate the statistical and computational limits of prompt tuning for transformer-based foundation models. Our key contributions are prompt tuning on single-head transformers with only a single self-attention layer: (i) universal, and (ii) supports efficient (even almost-lineat time) algorithms under the Strong Exponential Time Hypothesis (SETH). Statistically, we prove that prompt tuning such simplest possible transformers are universal approximators for sequence- to-sequence Lipschitz functions. In addition, we provide an exponential-ine and -in-(1/e) lower bound on the required soft-prompt tokens for prompt tuning to memorize any dataset with I I-layer, 1-head transformers. Computationally, we identify a phase transition in the efficiency of prompt tuning, determined by the norm of the soft-prompt-nnducee criterion. Beyond this criterion, sub-quadratic (efficient) algorithm for prompt tuning exists under SETH. Within this criterion, we showcase our theory by proving the existence of almost-linear time prompt tuning inference algorithms. These fundamental limits provide important necessary conditions for designing expressive and efficient prompt tuning methods for practitioners.
keys and queries, and provide an upper bound
INTRODUCTION
We investigate the statistical and computational limits prompt tuning for transformer-based foundation models. These models are gigantic transformer-based architectures (Bommasani et al., 2021), pretrained on vast datasets, are pivotal across multiple fields (Touvron et al., 2023b;a; Brown al., 2020; Floridi and Chiriatti, 2020; Yang al., 2023; Wu al., 2023; Nguyen et al., 2024; Zhou et al., 2025; 2024; 2023; Ji et al., 2021: Thirunavukarasu et al., 2023; Singhal et al., 2023; Moor al., 2023). Despite their power, the significant cost of pretraining these models often makes them prohibitive outside certain industrial labs. Thus, most practitioners resort to fine-tuning methods to tailor these models to specific needs (Zheng et al., 2024; Ding al., 2022). However, fine-tuning large models with billions or trillions of parameters is still often resource-intensive (Minace et al., 2024). Prompt tuning mitigates this by adapting learnable prompt with a limited set of parameters (tokens), preserving the pretrained model weights and allowing adaptation to new tasks or data without any retraining (Lester et al., 2021; Liu et al., 2021). It saves substantial computational resources and time. However, despite its empirical successes (Gao et al., 2024; Shi and Lipani, 2024; Fu et al., 2024; Chen al., 2023; Wang et al., 2023b; Khattak et al., 2023; Jia et al., 2022; Liu et al., 2022; 2021), the theoretical aspects of prompt tuning still underexplored, relatively (Wang et al., 2023a; Petrov et al., 2024). This work provides a timely thcoretical analysis of the statistical and computational limits of prompt tuning, aiming to explain its successes and offer principled guidance for future prompt tuning methods terms of performance and computational cost.
Let X, Y Rd F. be the input and the corresponding label sequences, respectively. For E [L], denote X E IRd as the i-th token (column) of X. Let [5 denote sequential concatenation.
"qqul contribution. Full version and future updates are on arXiv. Throughout this work, universality universal approximation refers sequence-to-seqeenee (seq2seq) universal approximation.

---

Published as a conference paper at ICLR 2025
Definition 1.1 (Prompt Tuning). Let be pretrained transformer. Let P E R be a length- Lp prompt weight (termed soft-prompt) prepended to input prompt X such that X = X e Idx L.) For any downstream task with finetuning dataset S = {(x(, y( the problem of prompt tuning is to find a prompt weight Px by solving the following optimization problem
p = argmin Σ
for some loss f: RdLL x RaxL + Ra. (1.1)
In this work, aim to study Definition 1.1 statistically and computationally.
Statistically, we explore the expressive power of prompt tuning a transformer of the simplest config- uration. Formally, we investigate whether it is possible approximate any sequence- -e-suueeec function f through prompt tuning with a pretrained single-head, single-layer transformer T such that
de (T(PP, -.).,pp 1) c, for some e O,
(1.2)
where approximation error between two functions d (J1, f2) = Here, Il- denotes entrywise f, -norm, i.e., ||X C Σラ= E (Xiz Specifically, while Wang et al. (2023a, Theorem report the universality' of prompt tuning transformers with O + (1()))) attention layers with 2 heads of hidden dimension and (((1ee)d(L,tz) FFN layers with 4 MLP neurons, ask the following question:
Question 1. Is it possible to improve (Wang et al., 2023a) toward the universality of prompt tuning on single-head single-layer pretrained transformers?
To answer Question 1, we first refine previous results of attention contextual mapping (Lemma 2.2) and establish a chaining reduction for bounding approximation error of prompt tuning (Section 2.3).
Computationally, we investigate the computational hardness of prompt tuning in transformer-based foundation models using fine-grained complexity theory (Williams, 2018). We observe that the computational hardness of prompt tuning ties to the quadratic time complexity of the transformer attention heads. Although designing algorithms to bypass this Q(L²) computation time is tempting. to the best of our knowledge, there lacks formal results to support and describe such approaches in a comprehensive fashion. To bridge this gap, we pose below questions and develop a foundational theory to characterize the complexity of prompt tuning for large transformer-basee models:
Question 2. Is it possible to improve the S?L?) time with a bounded approximation error?
Question More aggressively, is it possible do such computations in almost linear time L 11(+0(1)
In this work, we answer both Questions and 3 for the forward inference of prompt tuning. To answer them, we explore approximate prompt tuning computations with precision guarantees. To be concrete, let K, Wo, Wv E gdxé be attention weights such that Q = Wy E _ and V Wv E RdxL Recall the Attention Mechanism
K WK E L
Z V Softmax (KTQ3)= (Wy exp (X W W WQX
E d
(1.3)
with the inverse temperature > and D diag (exp(X W W X 11) Here, exp(.) is entry-wise exponential function. For simplicity of presentation, we set 3 = 1 in this work.
Formally, we study the following approximation problem for prompt tuning inference. Let Op WºXp E (I, Kp WxXp (L,++ and Vp WK (L,,+t,
Problem (Approximate Prompt Tuning Inference APTI). Let 8p > 0 and B > 0. Given Qp, Kp. Vp E (L+LL)) with guarantees that max [ll][11pplllpp 11 | mmax V max) < B, we aim to study approximation problem APTI(d, L,, Lpp B, dr), aiming to approximate
Throughout this work, universality refers to sequence-to-sequeee (seq2seq) universal approximation. For attention weights Wv, WK. Wa Rx hidden dimension is
2

---

Published as a conference paper at ICLR 2025
V Softmax (p)) with a matrix Ż such that
2 v Softmax
(K Up) Ilmax S SŌp,
Here, for matrix M Re write |M max.,j j |Mazl
In this work, we aim investigate the computational limits of all possible efficient algorithms for APTI(d, L, Lp, B, ôf) under realistic setting of = 1 1/poly(L).
Contributions. We study the fundamental limits of prompt tuning. Our contributions are threefold:
Universality. We prove that prompt tuning transformers with the simplest configurations
single-head, single-layer attention are universal approximators for Lipschitz sequence-to- sequence functions. Additionally, we reduce the required number of FFN layers in the prompt tuning transformer 2. These results improve upon (Wang et al., 2023a), which requires deep transformers with ( + ()) attention layers and (((1/c)dLZz+b) FFN layers.
Memorization. We show that prompt tuning such simple transformers (1-head, 1 1-layer attention and 2 FNN layers) is capable of complete memorization of datasets without any assumption on the data. Moreover, prompt tokens for any dataset, where d, L are the data dimension and sequence length, respectively, and is the approximation error. Our results improve upon those of (Wang et al., 2023a), which consider datasets with only two-token sequences and focus solely on memorizing the final token.
establish exponential-in-de and -in-(1/e) Iower bound on the required soft-
Efficiency. We address Question 2 by identifying phase transition behavior efficiency based on the norm of soft- poft-prompt-ioo prompt-induced queries and keys (Theorem 3.1). This establishes an efficiency criterion for prompt tuning inference, enabling efficient (sub-quadratic) algorithms when the criterion is met. Additionally, we address Question 3 by pushing the limits of efficiency in prompt tuning toward nearly-lineal time under this criterion (Theorem 3.2).
Organization. Section 2 presents statistical analysis on prompt tuming's ' universality and memory capacity. Section 3 explore the computational limits inference with prompt tuning. The appendix includes the related works (Appendix B.1) and the detailed proofs of the main text.
Notations. We use lower case letters to denote vectors and upper case letters to denote matrices. The index set {I,....I } is denoted by [4], where / E N+, We write fa ---ormm as Il-lla. Throughout this paper, we denote input, label sequences X, Y RdxL and prompt sequences P E Rd
2 STATISTICAL LIMITS OF PROMPT TUNING: UNIVERSALITY AND CAPACITY
To better understand the expressive power of prompt tuning, we explore its universality (Sections 2.3 and 2.4) and memory capacity (Section 2.5) on transformer of simplest configurations.
Overview of Our Results. Let Th,err denote transformers with h heads, hidden size, and r MLP neurons, and let represent the approximation error tolerance. Let X E d and R be the input and soft-prompt defined in Definition 1.1, respectively. We answer Question affirmatively, and present three results for transformer models with 1-head, I-layer attention layers:
Lemma 2.1 (1-Head, I-Layer Attention with Any-Rank Weight Matrices Is Contextual Mapping, Informal Version of Lemma 2.2). A 1-head, 1-layer attention mechanism with weight matrices WK, Wo, Wv of any rank is able to associate each input sequence with a unique label sequence.
Theorem 2.1 (Universality of Tuning T1.1,1 Transformers with O(e=d(L,+D)) FFN Layers, Informal Version of Theorem 2.3). Prompt tuning transformers with head, a hidden size of 1, and O(c-d(I,, +t), FFN layers width are universal approximators for Lipschitz seq-to-seq functions.
Theorem 2.2 (Universality of Prompt Tuning -1,,,r=(( ((ol-=0((+((tt))) Transformers with FFN Layers, Informal Version of Theorem 2.4). Prompt tuning transformers with head, hidden size of and FFN layers of width ((c-d((( ()( are universal approximators for Lipschitz seq-to-seq functions.
Comparing with Prior Works. Our results improve previous works in three aspects:
3

---

Published as a conference paper at ICLR 2025
Any Weight Matrices. While Kajitsuka and Sato (2024) show that a self-attention layer with rank-1 weight matrices serves as a contextual map, we improve this to weight matrices of any rank.
Transformers with 1-Head, 1-Layer Attention. While Wang et al. (2023a) show that prompt tuning on transformers of ((( + ())1 attention layers with at least 2 attention heads, we achieve the universality of prompt tuning transformers with only single-head single-layer attention.
Only 2 FFN Layers. We identify a width-depth tradeoff of universality. While Wang et al. (2023a) achieve prompt tuning universality with transformers of (((/e))(LL, FFN layers, we show that the same universality holds with I-head, l-layer transformers of only 2 FFN layers.
Technical Overview. Our proof strategy is to characterize the joint approximation error from different components of a transformer block via a chained reduction of piece-wise constant approximations.
Quantized Functions and Piece-Wise Constant Approximations
(PI) Piece-Wise Constant Approximation. We consider a class of Lipschitz functions as our target functions fxegseqq and employ piece-wise constant approximations" Namely, first quantize the input and output domain of the target functions and obtain a class of quantized target functions. These quantized target functions (denoted by Jsoq2sa) are piece-wise constant functions mapping grids of the input domain to grids of the output domain.
(P2) Surrogate Prompt Tuning Transformer. Next, we construct a surrogate function heeqpseg for the transformer. This surrogate function takes prompts (i.e., Zp = [P. E (d)( as inputs. We approximate each quantized target function /sepssaq with Lp-imputed output of heeq2seg. Namely, we only use the last output tokens huequeey to approximate f seqquey. We achieve this by associating unique prompt with each quantized target function.
(P3) Prompting Tuning Transformer Approximate heegZagq Then, we construct a transformer
T on which prompt tuning approximates the surrogate function Msoq2seg with bounded error. Chained Reduction of Piece-Wise Constant Approximations
A transformer layer consists of self-attention layer (AAl) and FFN layer. We utilize f(Au) as a contextual mapping. A (6, conttettl mapping preserves the correspondence of its input-output pair up to (Ó, 7) accuracy (see Definition 2.6 for formal definition). Furthermore, instead of just token-wiss wise manipulation, contextual mapping allows us to capture the context of input sequence
whole. This allows quantify the quality of mapping in terms of its ability to perform picce-wise approximation up to any precision.
Lastly, FFN layers map the outputs of ((At) the desired outputs within bounded error. This results in a chained reduction of approximation errors; we observe that for each step, Error[(P3)] 2 [P2)] 2 Error Error[(P1)). Therefore, we conclude that prompt tuning on the transformer is a universal approximator for our target functions f.
2.1 PRELIMINARIES AND PROBLEM SETUP
We first present the ideas we build on.
Let Z E R denote the input embeddings of attention layer and denote the hidden dimension.
Transformer Block, Let h-head self-attention layer as a function ((A)) RdxL - d
h wi (AA) (Z, Z) E RaxL
((SA) (Z)= = Z Σ
(2.1)
where We E Rdxe and f(Am) is the size-s self-attention mechanism for the i-th head
f(Ai)) (Z.k, Z) (WtzZ) Softmax [(W T (W)) R.
Here, s(Ant) Rd x R dx + Fs acts token-wisst and Wi. ; W W E -xxd are the weight matrices. Next, we define the r-neuron feed-forward layer function as (FF) E F(FF). Rdxt. + d and the
'A piece-wis constant approximation approximates function fasgusg by a series of constant values across different segments of its domain. This technique involves discretizing the function's 's domain into intervals and assigning constant value to the function over each interval. Please see (Yun et al., 2020) for utilizing piece-wise constant approximations for the transformer's universality.
4

---

Published as a conference paper at ICLR 2025
output at k-th token as
((F) (Z) = Z,, + Re Z,, + b()) + 6(2),
(2.2)
where W E Rexd and W(2) Rdxr are weight matrices, and b B()) RR' are the bias terms.
Definition 2.1 (Transformer Block). We define transformer block of h h-head, s-size and r-neuron f(Thher)) (Z) f(FF) (F(SA) (Z) R R
Now, we define the transformer networks as compositions of transformer blocks.
Definition 2.2 (Transformer Network Function Class) Let Th,s, denote the transformer network
function class where each function E Thh,,"" consists of transformer blocks f(Th with h heads of size s and MLP hidden neurons: Thes. {T 12 g
))}
Prompt Tuning Pretrained Transformer Models. In this work, we consider the prompt tuning problem Definition 1.1 with a pretrained transformer network T E Th.ss..
Problem Setup. To answer Question 1, we focus on the universal approximation of prompt tuning pretrained transformer models. We start by stating the target functions of our approximation.
Definition 2.3 (Target Function Class). Let Fo be the C-Lipschitz (under p-norm) target function class of continuous sequence-to- -o-uuunnce. Let freg2seq continuous sequence-to-sequenee functions on a compact set of sequence.
Fcc [0, 1 + [0, 11xx. denote
Explicitly, for any [seg2s0g E Fc and two input sequences Z' RdxL have I[fseauseg (2) - freguee (Z')laa < C Z'lla. In this work, we adopt freq2scg our approximation target function. Concretely, we investigate whether it possible approximate any C-Lipschitz ssquence-to-sequee
function Sreqsey through prompt tuning with pretrained single-head, single- layer transformer model. Namely, we reformulate Question into the following problem.
Problem 2. Is it possible to find a pretrained transformer model т E T111r such that, for any fseq2s0q Fc. prompt tuning satisfies d., (T[[P, -D)...... /seg2sea) for some 0? Here,
da(fi, = (ʃ [lf(()) - fa(z)
1/a
measures the difference between functions fI and fz in the token- -nomm.
2.2 ANY-RANK SINGLE-LAYER ATTENTION IS A CONTEXTUAL MAPPING FUNCTION
In this subsection, we present new results on the contextual mapping property of attention. These results allow us to use feed-forward neural networks to map each input sequence to its corresponding label sequence, thereby achieving universal approximation in Section 2.3.
Background:
Contextual Mapping, As stated in the previous technical overview, a key element of our proof is the concept of contextual mapping in attention (Kajitsuka and Sato, 2024; Yun et al., 2020). Contextual mapping enables transformers to move beyond simple token-wise manipulation and capture the full context of sequence. Through this, identical tokens within different input sequences become distinguishable. Let Z, Y E R be the input embeddings and output label sequences, respectively. Let Z, E Rd be the i-th token (column) of each Z embedding sequence.
Definition 2.4 (Vocabulary). define the i-th vocabulary set for i E [N] by v(i) =Uke(r] 2 C
Rd, and the whole vocabulary set V is defined by USE[N (() C Rdd.
Note that while "vocabulary" typically refers to the tokens' codomain, here it refers to the set of all tokens within a single sequence. To facilitate our analysis, we introduce the idea input token separation following (Kajitsuka and Sato, 2024; Kim et al., 2022; Yun et al., 2020).
Definition 2.5 (Tokenwise Separateness). Let z ((N) RdxL embeddings. Then,
2(1),... Z(N) are called tokenwise (Tmin: Tmaxx 6) sepaaaaad if the following conditions hold.
5

---

Published as a conference paper at ICLR 2025
(i) For any i [N] and & E [4], 1Z > Tmin holds.
(ii) For any i [M] and [r];||<2, Tmax holds.
(iii) For any i.j E [N] and I [z]
if 2 * 2.67 then 1 - 2 > holds.
Note that when only conditions (ii) and (iii) hold, we denote this as (7, 6) -.ss)))attteeesss Moreover, only condition (iii) holds, we denote it as
( (f)-separateness.
To clarify condition (iii,, we consider cases where there are repeated tokens between different input sequences. Next, we define contextual mapping. Contextual mapping describes a function's 's ability to capture the context of each input sequence as whole and assign a unique ID each input sequence.
Definition 2.6 (Contextual Mapping). A function q: Rdx d is said to be (7, 5) contexxxlll mapping for set of embeddings ( ...... Z(N) R L if the following conditions hold:
1. Contextual Sensitivity y. For any i E [N] and l E [T.], |lg (Z))). ::ll < 7 holds.
2. Approximation Error 6. For any i, E [N] and k, E [L] such that v o vli or 2 ikk + z.!
(la(Z()) ):,k- ((())) )=all > 8 holds.
Note that 9 (Z( for i E [N] is called a context ID of z
Any-Rank Attention is Contextual Mapping. Now we present the result showing that 1-head, 1-layer )attenatnatatnntionn block with any-rank weight matrices is contextual mapping.
Lemma 2.2 (Any-Ram Rank Attention as a (7, -onnteettlll Mapping, Modified from Theorem 2 of (Kajitsuka and Sato, 2024)). Let (
((N) E dd L be (7min: Ymmxx e) --tokenwssse separated embeddings, with the vocabulary set V ULE(N] D(i) c Rd. Additionally, assume no duplicate word
tokens in each sequence, i.c., - * !. for any E [N] and k, E [4]. Then, there exists I-layer, single-head attention mechanism with weight matrices W(O) E Raxs and Wv, WK, Wq E Rxxd that serves as a (7, -7-o)ecclll mapping for the embeddings z z Z(N), where:
Y 7max + 4
and 8 = exp (-5c 1 log L). with K == Tmaxx/ Timin
Sketch. Sketch. We generalize (Kajitsuka and Sato, 2024, Theorem 2) where all weight matrices have to be rank-1. We eliminate the rank-1 requirement by constructing the weight matrices as an outer product sum Σ. uud where u, E IR,, o RRd This extends (Kajitsuka and Sato, 2024, Theorem 2) holds for attention with weights of any rank. Please see Appendix E. 1 for a detailed proof.
Lemma 2.2 indicates that any-rank self-attention function distinguishes input tokens N 2 such that (00) * (d)) In other words, it distinguishes two identical tokens within different context.
Remark 2.1 (Comparing with Existing Works). In comparison, Kajitsuka and Sato (2024) provide a proof for the case where all self-attention weight matrices Wv, WK. Wq E Rax are rank- 1 strictly. However, this is almost impossible in practice for any pre-trained transformer-based models. In contrast, by considering self-attention weight matrices of rank p, where 1 S S min(d, s), we show that single-head, single-layer self-attention with matrices of any rank a contextual mapping, pushing the universality of (prompt-tuning transformers towards more practical scenarios.
Next, we utilize Lemma 2.2 to prove the universality and memory capacity of prompt tuning on transformer networks with single layer self-attention.
2.3 UNIVERSALITY OF PROMPT TUNING T1.1,4 WITH ((()c))((x)zt) FEN LAYERS
In this section, we prove the universality of prompt tuning by showing that there exists a simple transformer of single-layer self-attention T E 7..1.4 such that for any freq2s0q E Fc, prompt tuning on r approximates this function up to some eгтor >> O. Specifically, E T consists of single-head, single-layer, size-one self-attention function f(SA) E (SAA), and ((()))d((t,+t) feed-forward layers (FF) E (+FF), each with 4 MLP hidden neurons. Formally, we write
T..11 (T d + RdxL
((PF)
(PFF ((SA) ((FF)
(FF)) (2.3)

---

Published as a conference paper at ICLR 2025
Proof Strategy. We employ chained reduction of piece-wite wise constant approximations:
(AI) We start by quantizing the input and oulput domain of Ssequseq E Fc into a quantized function
f saqsseq I5,L + Go,L, where Gs.L {0, 0, 26, ................................ _]
Here, feeq2sa, Fo denote the quantized function and function class. In essence, this is perform- ing ppece-wise constant approximation with bounded error (A2) Next, we construct surrogate quantized sequence-to-sequee
function
hseqtseq (b((L++)) + LL) where G5, = {0, 6, 26...., ()dx(L,+L)
Here Reeupey takes prompts and embeddings Zp [P. as inputs. Crucially, its T-pimpeeed output approximates any sequiee E Fc by using various soft prompts P.
(A3) Finally, we show that there exist transformers + E T 1.14 approximating /see22oy to any precision. By simple reduction from hsequwyy- J Tuugsey and /seq2egs we achieve the universality of prompt tuning on T.,1.4 with ((1/6))(4z+21) FFN layers, where is the approximation error.
Remark 2.2. We remark that while (AI) shares some similarity with (Wang et al., 2023a) by the nature of quantization approach to transformer's universality (Yun al., 2020), (A2) and (A3) differ significantly in techniques and results. See the opening of this section for an overview.
For (A1) and (A2), we introduce the next lemma, and approximate the quantized Freqasay with a Ly-imputed version of some quantized pruuence-o--sqqeneee function
lsseusee (.,(L,+b) -0,(L,+L): where G8, (0, 28, ................................ 8) ()d(()))))
Lemma 2.3 (Universality of Prompt Tuning Surrogate Function heeq2se))) Let Fo be class of C-Lipschitz soquence-to-sequenee functions. where each function fseg2s0q [0, _] + [0, 1] Define the discrete function space (s.(L,+LL {0, 25,..., 8) (L, Then, there exists function lssaqsee (8, - (8,(L,+L) such that for any Leequea Fc, there exists prompt p E gdxL, satisfying
dp (N(((P, -D)...: fsequssa) S e/22,
where the prompt sequence length Lp satisfies Lp 2 LA, with A = (2c (2c-CC(dL)
Proof Sketch. Our proof consists of three steps. Firstly. we approximate each function in Fc by piece-wise constant function in Fc. Fo is constructed by quantizing the input and output domain of
Fc. This gives us function class of limited size, so that further discussion is feasible. Secondly,
we construct quantized prompt set P. We correspond each quantized function f(()
seq2saq E Fo to
prompt p()) E P. Lastly, we build sequence-to teaeccett--eqqunee function
hueq2so 95,LL++L) - 98.(L,+L) with G5,(L,+1) = {0,5, 26, ...,....1. 83 (L
that takes soft-prompt P and embeddings Z as input. Most importantly, this function haag behaves
like (()) seq2sey when taking the corresponding prompt P(O) Namely, it satisfies heeq ((P(1), DaL.p p(i)
soqpseg (.). Please see Appendix F.1 for detailed proof.
For (A3), we present the next lemma demonstrating that T approximates heqgseg up to any desired precision. The technical contribution involves using the contextual mapping property of any-rank I-layer, 1-head attention (Lemma 2.2) to preserve the piece-wiss constant approximation.
Lemma 2.4 (Transformer E T1.1.11 1,11,1 Approximate hssa2soq to Any Precision). For any given quantized -equence-to-seqqeecee function hoequeyy (8,(Lp+L) Gollz+L) with Go.(L++L)

---

Published as a conference paper at ICLR 2025
{0,6, 10,6,20 26, E = (dx such that h[[P, -I)....
8) D)dx(Ix+ there exists transformer 7 E T with positional embedding
Proof. Please see Appendix for detailed proof.
Altogether, we state our main result: the universality of prompt tuning for a E T..1,4 transformer.
Theorem 2.3 (Universality of Prompt Tuning for E TA.1.4 1.4 Transformers). Let 1 S p and E O. There exists transformer T with single self-attention layer such that for any Ssea2s0q Fc, there exists prompt _dxLy satisfying da (T[[P, -D....-D)..... .p frequsea) S
Proof Sketch. By Lemmas 2.3 and 2.4, we obtain a E T.. with soft-prompt P G8, such that for any Srequeeq Fc, da (T((P, De.,yy Ssequeey See Appendix F.3 for detailed proof. D
Intuitively, Theorem 2.3 indicates that even the simplest transformer with 1-head, 1- 1-layer attention has enough expressive power through prompt tuning approximate any Lipschitz seq2seq function.
2.4 WIDTH-DEPTH TRADEOFF: UNIVERSALITY OF PROMPT TUNING (1.. (1po) ONLY NEEDS 2 FFN LAYERS
In Section 2.3, achieve the universality of prompt tuning simple transformers with many FFN layers. In this section, we explore the possibility further simplifying such transformer blocks by reducing the number of FFN layers. Surprisingly, we show that two FFN layers are sufficient.
We begin by determining the minimum number of FFN layers required for E I.I., transformers to achieve universality through prompt tuning. For clarity, we denote the transformer with four MLP neurons as Ta (i.e., (2.3)) and the transformer with MLP neurons as TB.
Lemma 2.5 (Required Number of FFN Layers). A transformer т E T1.14 as defined in (2.3), requires ((11e))dL, FFN layers be a universal approximator through prompt tuning.
Proof. Please see Appendix G.1 for detailed proof.
Next, prove the universality of prompt tuning another simple transformer block T with smaller FFN depth than T from Section 2.3. This suggests a trade-off between the depth and width of the transformer. Let transformers r E Th T11.r consist of single-head, single-layer, size-one
self-attention (SA)) and 2 feed-forwand layers, fl (FT) and f2 ((FF) each with r MLP hidden neurons:
T 1,1, (T Rdx + R === =((F) f(SA) f(FF)).
Proof Strategy. We follow a similar proof strategy as in Section 2.3, but with key difference: we use the construction technique from (Kajitsuka and Sato, 2024) to build a transformer with single-head, single-layer, size-one self-attention, and two FFN layers. We achieve this by summing multiple shifted ReLU functions to map inputs to desired outputs with precision guarantees. Moreover, this approach reduces the number of FFN layers by increasing the number of neurons in the MLP.
Theorem 2.4 (Prompt Tuning Transformers with Single-Head, Single-Layer Attention and Two Feed-Forward Layers). Let S p < oo and > O. There exists a transformer T E T 71.1," with single self-attention layer and r = ((1/))((L,pt)) MLP neurons, such that for any freq2saq Fc. there exists prompt P e Rd satisfying: dp (T([P, (eoPP-- S e.
Proof. Please see Appendix G.2 for a detailed proof.
2.5 MEMORY CAPACITY OF PROMPT TUNING
Based universality results, show the memory capacity of prompt tuning simple trans- former networks with single-head single-layer self-attention. We start with the definition.
8

---

Published as a conference paper at ICLR 2025
Definition 2.7 (Prompt Tuning Memorization). Given dataset {(x(i, ) with
R a pretrained transformer т E memorizes S through prompt tuning if there y x()
exists prompt P RRdL, such that: max [[,, J).,,, yl Ila S for all E (N].
We now prove the existence a transformer T that memorizes any dataset S through prompt tuning, We remark that this result is easy to extend to TTA, transformers.
Theorem 2.5 (Memorization Capacity of Prompt Tuning). Consider a dataset
(())) LN
i=1
where X y E [0, 1]ax1. Assume the corresponding embedding sequences Z(1), _ Z are generated from C-Lipschitz function. Then, there exists single-layer, single-head head attention transformer E T with = ((1/c)((Lotb)) and soft-prompt P RdxLe such that,
(((P, - -r c, for any E [N],
where Lp 2 LA with A (2e- ((dL)VAa)
Proof Sketch. We first find the underlying sequence-t--sequeece function of the dataset S, denoted by Segpsey [0, 1]axt + [o, 1]dx1, such that for any E [M], fimp (Z y Next, we complete
the proof by utilizing the results of Theorem 2.4 construct transformer E T that is capable
of approximating feggss through prompt tuning. Please see Appendix H.1 for a detailed proof. C
Remark 2.3. Theorem 2.5 shows that a simple transformer is capable of memorizing any dataset through prompt tuming, when configured carefully. In contrast, (Wang et al., 2023a, Theorem 3) is limited to datasets with only two tokens per example and defines memorization as memorizing only the last token. Additionally, we provide lower bound the prompt sequence length required to memorize any dataset, based on its dimensions and the desired accuracy.
Remark 2.4. In (Wang et al., 2023a, Theorem 2), the authors construct dataset and prove it to be unmemorizable by prompt tuning a transformer. However, their analysis differs from ours as assumes full-rank self-attention weight matrices and specific feed-forward layer structure. Their specialized dataset design relies on the invertibility of the weight matrices and weak feed-forward layer, preventing the transformer from mapping contextual embeddings to the correct labels. We discuss these limitations in the expressive power of prompt tuning in Appendix J. In contrast, we prove that transformer with single-layer self-attention and weight matrices of any rank capable of achieving memorization through prompt tuning.
3 COMPUTATIONAL LIMITS OF PROMPT TUNING
We analyze the computational limits of inference of prompt tuning Problem using fine-grained complexity theory. Specifically, recall that X, JP. E (dx(L,) with Qp = WoX, e (dx(L,++), Kp = WK X, E (L,, and Vp Wx X, E (Lx+), We study approximate prompt wuing inference with precision guarantees under 5p 1/poly + I.).
Problem (Approximate Prompt Tuning Inference APTI). Let 6f and B Given Qp Kyp V, (Lxx))+ with guarantees that max pI |1 |m V I B, we aim to study an approximation problem APTI(d, L, Lp. B, 8r), aiming to approximate V,, Softmax (KJQp) with matrix 7 such that
2 Vi Softmax (KJ Ilmax Spp
Here, for a matrix M E Raxb we write ||axx == maxi. MMal--
3.1 PRELIMINARIES: STRONG EXPONENTIAL TIME HYPOTHESIS (SETH)
Our hardness results are built on a common conjecture. Impagliazzo and Paturi (2001) introduce the Strong Exponential Time Hypothesis (SETH) as stronger form of the P of NP conjecture. It suggests

---

Published as a conference paper at ICLR 2025
that our current best SAT algorithms optimal and is popular conjecture for proving fine ain-ggrined lower bounds for a wide variety of algorithmic problems (Cygan et al., 2016; Williams, 2018).
Hypothesis 1 (SETH). For every e >> 0, there is positive integer k 2 3 such that k-SAT on formulas with n variables cannot be solved in ((2(1=)a)) time, even by a randomized algorithm.
Below, we rely on SETH to facilitate the fine-grained reduction for lower bound result (Theorem 3.1).
3.2 EFFICIENCY CRITERION FOR PROMPT TUNING INFERENCE
We answer Question 2 affirmatively by identifying phase transition behavior in the efficiency of all possible algorithms for Prompt Tuning Inference problem APTI (Problem 1), based on on the norm of Qp = Xx p. Kp = Wx Xp. and V = Wv with Xp = [P, X] E (dd(LLpL))
Theorem 3.1 Bosed Efficiency Phase Transition). Let 1| I B, Kyllmax S B and II max S B with = O Vlog( Lp + I.)) Assuming Hypothesis 1, for every q > O, there are constants C, Ca. C. > 0 such that: there no O(Lp + L)²-9)-time- (sub-quadratic) algorithm for the problem APTI(I, I,, Itp. d = C log(T,p L), B = Co Coolog(T, + or = (T.p + L) L))
Proof Sketch. Sketch. (ATTC in (Alman and Song, 2023)) via straightforward reduction. We achieve this by establishing correspondence between APIT and ATTC, then applying reduction with tighter error bounds using prompt tuning imputation (i.e., [[+]; Ip mmxx I || max). See Appendix 1.1 for detailed proof. D
Our proof strategy involves connecting APIT to the hardness of attention inference
Remark 3.1. Theorem 3.1 suggests efficiency threshold for the upper bound of l|Qpll
|lmpl Iaxi B O Vlog(L Lpp + L)). Only below this threshold are efficient algorithms for Problem 1 possible i.e. solving APIT in (Lp + L)2-2(1) (sub-quadratic) time is possible.
3.3 PROMPT TUNING CAN BE AS FAST AS ALMOST-LINEAR TIME
We answer Question affirmatively by proving the existence of almost- time efficient algorithms for Prompt Tuning Inference problem APTI (Problem 1) based on low-rank approximation.
Theorem 3.2 (Almost-Linear Prompt Tuning Inference). The prompt tuning inference problem
APTI(L, Lp, d = O (log Lp + L)), B = ol /log(L Lp + L)), 8r = 1/poly(Lp + L)) can be solved in time Tmai ((Lp + L). Lp + L) dd = (L, + L) ++0())
Proof Sketch. We prove this using low-degree polynomial approximation of transformer attention. Consider a matrix A E RRxx and function f R + R. We define ((A) IRPx - IR as the matrix obtained by applying f to each entry of A. The goal of the polynomial method to identify low-rank approximation of fA)) This method is effective if A has low rank and f can be approximated by a low low-degree polynomial. allowing f(A) to also be represented as a low-rank matrix. This low-rank approximation can be efficiently computed in almost linear time via low-rank decomposition (Li et al., 2025; Alman and Yu, 2024; Hu et al., 2024b; Alman and Song, 2023; Aggarwal and Alman, 2022). Alman and Song (2023) provide bounds on the polynomial degrees necessary for approximating softmax attention with low rank. Utilizing these results and the structural properties of prompt tuning imputation (i.e., ||[-]. - max < mlml) we construct low-rank approximation for the prompt tuning inference problem APTI. See Appendix I.2 for a proof. O
Theorem 3.2 provides a formal example the efficient criterion Theorem 3.1 for APTI using low-rank approximation within controllable approximation error. This is applicable under Theorem 3.1 when the efficiency criterion is met. Specifically, to achieve nearly-linear (Lp + L) ++((1) time prompt tuning inference with bounded error 1/poly(L, L). require B = ol /log (4, L)).
Concise Summary. We study the statistical and computational limits of prompt-tuning transformers and identify key necessary conditions for designing expressive and efficient prompt-tuning methods. Due to page limits, we defer concluding remarks and practical implications to Appendix A, related work and limitations to Appendix B, and additional results sequence- to soseeuuence approximation with one-layer, one-head attention using generic weight matrices an extension of (Kajitsuka and Sato, 2024) more generic setting to Appendix C.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
JH would like thank Tokio Kajitsuka, Jigyasa Kumari, Mimi Gallagher, Sara Sanchez, Dino Feng and Andrew Chen for enlightening discussions; Weimin Wu, Yi-Chen Lee, Yu-Chao Huang, Maojiang Su, and Hude Liu for collaborations on related topies; and the Red Maple Family for their support. The authors also thank the authors of (Wang et al., 2023a) for their clarifications, and thank the anonymous reviewers and program chairs for constructive comments.
JH is partially supported by the Walter P. Murphy Fellowship. HL is partially supported by NIH R01LM1372201, AbbVie and Dolby. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.
REFERENCES
Amol Aggarwal and Josh Alman. Optimal-degre polynomial approximations for exponentials and gaussian kernel density estimation. In Proceedings of the 37th Computational Complexity Conference, CCC '22, Dagstuhl, DEU, 2022. Schloss Dagstubl-Leibniz-Zenten fuer Informatik. ISBN 9783959772419. doi:
Silas Alberti, Niclas Dern, Laura Thesing, and Gitta Kutyniok. Sumformer: Universal approximation for efficient transformers. In Topological, Algebraic and Geometric Learning Workshops 2023, pages 72-86. PMLR, 2023.
Josh Alman and Zhao Song. Fast attention requires bounded entries. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives transformers. arXiv preprint arXiv:2410.04277 2024.
Kavosh Asadi and Michael Littman. An alternative softmax operator for reinforcement learning. In International Conference on Machine Learning (ICML), pages 243-252. PMLR, 2017.
Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of transformer: memory viewpoint. Advances in Neural Information Processing Systems, 36, 2024.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportuni- ties and risks of foundation models. arXiv preprint arXiv:2 2021.
Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D) Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Guangyi Chen, Weiran Yao, Xiangchen Song, Xinyue Li, Yongming Rao, and Kun Zhang. PLOT: Prompt learning with optimal transport for vision-language models. In The Eleventh International Conference on Learning Representations (ICLR), 2023.
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems hard as enf-sat. ACM Transactions on Algorithms (TALG), 12(3):1-24 1-24, 2016.
Ning Ding, Yujia Qin, Guang Yang, Fuchao Wei, Zonghan Yang, Yusheng Su, Shengding Hu, Yulin Chen, Chi-Min Chan, Weize Chen, et al. Delta tuning: A comprehensive study of parameter efficient methods for pre-trained language models. arXiv preprint arXiv:2203.0661 2022.
Ning Ding, Yujia Qin, Guang Yang, Fuchao Wei, Zonghan Yang. Yusheng Su, Shengding Hu, Yulin Chen, Chi-Min Chan, Weize Chen, et al. Parameter-effcieent fine-tuning of large-scale pre-trained language models. Nature Machine Intelligence, 5(3):220-23) 235, 2023.
Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, and Zhifang Sui. A survey in-context learning. arXiv preprint arXiv:2301.002:: 2022.
11

---

Published as a conference paper at ICLR 2025
Luciano Floridi and Massimo Chiriatti. Gpt-3: Its nature, scope, limits, and consequences. Minds and Machines, 30:681-694, 2020.
Shuai Fu, Xiequn Wang, Qiushi Huang, and Yu Zhang. Nemesis: Normalizing the soft prompt vectors of vision-langee languagee models. In The Twelfth International Conference on Learning Representations (ICLR), 2024.
Ziqi Gao, Xiangguo Sun, Zijing Liu, Yu Li, Hong Cheng, and Jia Li. Protein multimer structure pre- diction via prompt learning. In The Twelfth International Conference Learning Representations (ICLR), 2024.
Alexander Havrilla and Wenjing Liao. Understanding scaling laws with statistical and approximation theory for transformer neural networks on intrinsically low-dimensional data. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Soufiane Hayou, Nikhil Ghosh, and Bin Yu. Lora+: Efficient low rank adaptation of large models. arXiv preprint arXiv:2402 2024.
Edward 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. In International Conference on Learning Representations (ICLR), 2022.
Jerry Yao-Chieh Hu, Donglin Yang, Dennis Wu, Chenwei Xu, Bo-Yu Chen, and Han Liu. On sparse modern hopfield model. In Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS), 2023.
Jerry Yao-Chich Hu, Pei-Hsuan Chang, Robin Luo, Hong-Yo Yu Chen, Weijian Li, Wei-Po Wang, and Han Liu. Outlier-efficient hopfield layers for large transformer-based models. In Forty-first International Conference Machine Learning (ICML), 2024a.
Jerry Yao-Chieh Hu, Thomas Lin, Zhao Song, and Han Liu. On computational limits of modern hopfield models: A fine-grained complexity analysis. In Forty-first International Conference on Machine Learning (ICML), 2024b.
Jerry Yao-Chieh Hu, Dennis Wu, and Han Liu. Provably optimal memory capacity for modern dense associative memories as spherical codes. In
hopfield models: Fransformer-comper Teihth- Conference Neural Information Processing Systems (NeurIPS), 2024c.
Jerry Cao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Computational limits of low-rank adaptation (lora) fine-tuning for transformer models. In The Thirleenth International Conference on Learning Representations, 2025.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 6272):367-375, 2001.
Yanrong Ji, Zhihan Zhou, Han Liu, and Ramana V Davuluri. Dnabert: pre-trained bidirectional encoder representations from transformers model for dna-language in genome. Bioinformatics, 37 (15):2112-22) 12-2120,222222 2021.
Menglin Jia, Luming Tang, Bor-Chun Chen, Claire Cardie, Serge Belongie, Bharath Hariharan, and Ser-Nam Lim. Visual prompt tuning. In European Conference Computer Vision, pages 709-727. Springer, 2022.
Haotian Jiang and Qianxiao Li. Approximation theory of transformer networks for sequence modeling. arXiv preprint arXiv:2305.1842 2023.
Tokio Kajitsuka and Issei Sato. Are transformers with layer self-attention using low-rank weight matrices universal approximators? The Twelfth International Conference on Learning Representations (ICLR), 2024.
Tokio Kajitsuka and Issei Sato. Optimal memorization capacity of transformers. In The Eleventh International Conference Learning Representations (ICIR), 2025.
12

---

Published as a conference paper at ICLR 2025
Muhammad Uzair Khattak, Hanoona Rasheed, Muhammad Maaz, Salman Khan, and Fahad Shahbaz Khan. Maple: Multi-modal prompt learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 19113-19122, 2023.
Junghwan Kim, Michelle Kim, and Barzan Mozafari. Provable memorization capacity of transformers. In The Eleventh International Conference on Learning Representations, 2022.
Brian Lester, Rami AI-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning. arXiv preprint arXiv:2104 08.086,1, 2021.
Chenyang Li, Yingyu Liang. Zhenmei Shi, and Zhao Song. When can we solve the weighted low rank approximation problem in truly subquadratic time? arXiv preprint 261112 2025.
Xiang Lisa Li and Perey Liang. Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint arXiv: 101110010000000 2021.
Yingyu Liang, Zhenmei Shi, Zhao Song, and Chiwun Yang. Toward infinite-long prefix in transformer. arXiv preprini arXiv:2406. 102006644400 /4036, 2024.
Haokun Liu, Derek Tam, Mohammed Mugeeth, Jay Mohta, Tenghao Huang. Mohit Bansal, and Colin A Raffel. Few-shot parameter-effiiient fine-tuning is better and cheaper than in-context learning. Advances Neural Information Processing Systems,
19000-996.20000 2022.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9):1-35, 2023.
Xiao Liu, Kaixuan Ji, Yicheng Fu, Weng Lam Tam, Zhengxiao Du, Zhilin Yang, and Jie Tang. P-tuning v2: Prompt tuning be comparable fine-tuning universally across scales and tasks. arXiv preprint arXiv:2110.07602, 2021.
Sadegh Mahdavi, Renjie Liao, and Christos Thrampoulidis. Memorization capacity of multi-head attention in transformers. arXiv preprint arXiv:2336.0000/ 02000, 2023.
Shervin Minaee, Tomas Mikolov, Narjes Nikzad, Meysam Chenaghlu, Richard Socher, Xavier Amatriain, and Jianfeng Gao. Large language models: A survey, arXiv preprint arXiv:2402.06196, 2024.
Michael Moor, Oishi Banerjee, Zahra Shakeri Hossein Abad, Harlan M Krumholz, Jure Leskovec, Bric J Topol, and Pranav Rajpurkar. Foundation models for generalist medical artificial intelligence. Nature, 61 616(7956):299-66, 2023.
Eric Nguyen, Michael Poli, Marjan Faizi, Armin Thomas, Michael Wornow, Callum Birch-Sykes, Stefano Massaroli, Aman Patel, Clayton Rabideau, Yoshua Bengio, et al. Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution. Advances in neural information processing systems, 36, 2024.
Samet Oymak, Ankit Singh Rawat, Mahdi Soltanolkotabi, and Christos Thrampoulidis. On role of attention in prompt-tuning, In International Conference on Machine Learning, pages 66724-26768. PMLR, 2023.
Rui Pan, Xiang Liu, Shizhe Diao, Renjie Pi, Jipeng Zhang, Chi Han, and Tong Zhang. Lisa: Layerwise importance sampling for memory-efficient large language model fine-tuning. arXiv preprint arXiv:2403. 1et.:22433799993 17919, 2024.
Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. In Conference on Learning Theory (COLT), pages 3627- 3661. PMLR, 2021.
Aleksandar Petrov, Philip HS Torr and Adel Bibi. When do prompting and prefix-tunin work? theory of capabilities and limitations. arXiv preprint XXi:22310.19695 2023.
Aleksandar Petrov, Philip HS Torr, and Adel Bibi. Prompting a pretrained transformer can be a universal approximator. arXiv preprint a402v:2402. 14753, 2024.
13

---

Published as a conference paper at ICLR 2025
Hubert Ramsauer, Bernhard Schafl, Johannes Lehner, Philipp Seidl, Michael Widrich, Thomas Adler, Lukas Gruber, Markus Holzleitner, Milena Pavlovic, Geir Kjetil Sandve, et al. Hopfield networks is all you need. arXiv preprint arX1v:2008.02217, 2020
Zhengxiang Shi and Aldo Lipani. DePT: Decomposed prompt tuning for parameter-efficien fine- tuning. In The Twelfth International Conference on Learning Representations (ICLR), 2024.
Zhemmei Shi, Junyi Wei, Zhuoyan Xu, and Yingyu Liang. Why larger language models do in-context learning differently? arXiv preprint arXiv:2405. 19592, 2024.
Karan Singhal, Shekoofch Azizi, Tao Tu, S Sara Mahdavi, Jason Wei. Hyung Won Chung, Nathan Scales, Ajay Tanwani, Heather Cole-Lewis, Stephen Pfohl, et al. Large language models encode clinical knowledge. Nature, 620(7972) 2023.
Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez. Ting Fang Tan, and Daniel Shu Wei Ting. Large language models in medicine. Nature medicine, 29(8): 1930-1940, 2023.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint (eXXi::332..3777 2023a. 2023a
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprini arXiv:2307.09288. 2023b.
Qiang Wang, Bei Li, Tong Xiao, Jingbo Zhu, Changliang Li, Derek F Wong, and Lidia $ Chao. Learning deep transformer models for machine translation. arXiv preprint 1rXiv:196.001780 2019.
Yihan Wang, Jatin Chauhan, Wei Wang, and Cho-Jui Hsich. Universality and limitations of prompt tuning. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023a.
Zhen Wang. Rameswar Panda, Leonid Karlinsky, Rogerio Feris, Huan Sun, and Yoon Kim. Multi- task prompt tuning enables parameter-efficient transfer learning. In The Eleventh International Conference on Learning Representations (ICLR), 2023b.
Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, et al. Larger language models do in-context learning differently, arXiv preprint (iX.iv:2333.038444 2023.
Yuxin Wen, Neel Jain, John Kirchenbauer, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery. Advances in Neural Information Processing Systems, 36, 2024.
Virginia Vassilevska Williams. On some fine- the-grained questions in algorithms and complexity. In Proceedings of the international congress of mathematicians: Rio de janeiro 2018, pages 3447- 3487. World Scientific, 2018.
Dennis Wu, Jerry Yao-Chich Hu, Teng- Yun Hsiao, and Han Liu. Uniform memory retrieval with larger capacity for modern hopfield models. In Forty-first International Conference on Machine Learning (ICML), 2024a.
Dennis Wu, Jerry Cho-Chieh Hu, Weijian Li, Bo- Yu Chen, and Han Liu. Stanhop: Sparse tandem hop- field model for memory memory-enhanced time series prediction. The Twelfth International Conference on Learning Representations (ICLR), 2024b.
Shijie Wu, Ozan Irsoy. Steven Lu, Vadim Dabravolski, Mark Dredze, Sebastian Gehrmann, Prabhan- jan Kambadur, David Rosenberg, and Gideon Mann. Bloomberggpt: A large language model for finance. arXiv preprint 2303. 17544, 2023.
Ruibin Xiong, Yunchang Yang. Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the transformer architecture. In International Conference on Machine Learning, pages 10524-10533, PMLR, 2020.
14

---

Published as a conference paper at ICLR 2025
Zhuoyan Xu, Zhenmei Shi, and Yingyu Liang. Do large language models have compositional ability? an investigation into limitations and scalability. In First Conference on Language Modeling (CoLM), 2024.
Hongyang Yang, Xiao-Yar Yang Liu, and Christina Dan Wang. Fingpt: Open-source financial large language models. arXiv preprini urXiv:2306.0603/ 2023.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are trans- formers universal approximators of Sequence-to-sequeee functions? In International Conference on Learning Representations (ICLR), 2020.
Yaowei Zheng, Richong Zhang, Junhao Zhang, Yanhan Ye, and Zheyan Luo. Llamafactory: Unified efficient fine-tuning of 100+ language models. arXiv preprint arXiv:2403.13372, 2024.
Zhihan Zhou, Yanrong Ji, Weijian Li, Pratik Dutta, Ramana Davuluri, and Han Liu. Dnabert-2: Effi- cient foundation model and benchmark for multi-species genome. arXiv preprint Xiv::23066.1000 2023.
Zhihan Zhou, Winmin Wu, Harrison Ho, Jiayi Wang, Lizhen Shi, Ramana V Davuluri, Zhong Wang, and Han Liu. Dnabert-s: Learning species-aware dna embedding with genome foundation models. arXiv preprint 4rX1v.2402.08877, 2024.
Zhihan Zhou, Robert Riley, Satria Kautsar, Weimin Wu, Rob Egan, Steven Hofmeyr, Shira Goldhaber- Gordon, Mutian Yu, Harrison Ho, Fengchen Liu, et al. Genomeocean: An efficient genome foundation model trained large-scale metagenomic assemblies. bioRxiv, pages 2025-01, 2025.
15

---

Published as a conference paper at ICLR 2025
Appendix
A Discussion and Concluding Remarks
17
Related Works, Limitations and Broader Impact
18
B.I Related Works
18
B.2 Limitations and Broader Impact
19
Additional Theoretical Results: Universality Transformers with L-Layer, 1-Head,
Any-Rank Self-Attention
20
D Background: Boltzmann Operator and Attention Mechanism
22
D.I Essential Properties of Boltzmann Operator
22
D.2 Distance Preservation of Boltzmann Operator
23
Proofs of Section 2.2
27
E.
Proofs of Lemma 2.2
27
F Proofs of Section 2.3
33
F.1
Proof of Lemma 2.3
33
F.2 Proofs of Lemma 2.4
35
F3
Proofs of Theorem 2.3
37
Proofs of Section 2.4
38
G.1
Proof of Lemma 2.5
38
G.2 Proof of Theorem 2.4
H Proofs of Section 2.5
42
H.1 Proof of Theorem 2.5
42
I Proofs Computational Limits of Prompt Tuning (Section 3)
LI Proof of Theorem 3.1
43
I.2
Proof of Theorem 3.2
43
Limitations of Prompt Tuning Transformers
44
J.1
Discussion on the Limitations of Prompt Tuning
44
J.2
Examples of Prompt Tuning Failures
45
K Supplementary Proofs for Appendix D
46
K.1
Lemma D.
46
K.2
Lemma D.2
46
................................
K.3
Lemma D.3
47
K.4
Lemma D.4
48
K.5
Lemma D.5
48
K.6
Lemma D.6
48
K.7
Lemma D.7
49
K.8
Lemma D.8
50
K.9
Lemma D.9
51
K.10
Lemma E.
52
16

---

Published as a conference paper at ICLR 2025
A DISCUSSION AND CONCLUDING REMARKS
We study the fundamental limits of prompt tuning transformer-based pretrained models (i.e., foun- dation models) in two aspects: statistical and computational. Statistically, we show the universality of prompt tuning transformer models with 1-head, 1-layer attention layers (Theorem 2.3 and Theo- rem 2.4). Recall that is the token dimension, L is the input sequence length, Lp is the poft-prompt length, and is the approximation error. Our results significantly relax previous requirements for thick layers, reducing from O(LL, ())) layers to attention layer, and from (((1e)d(L4,+a) layers to FFN layers for prompt tuning universality. In addition, we prove the memorization capacity of prompt tuning and derive exponential in-dL and in- lower bound on required soft prompt tokens (Theorem 2.5). Different from (Wang et al., 2023a) where the analysis of capacity is solely on datasets of two-token sequences and focuses on only memorizing the last token, we demonstrate a complete memorization of prompt tuning on any general dataset. Computationally. we establish an efficient criterion of all possible prompt tuning inference for the norm of soft-prompt induced keys and queries (Theorem 3.1). In addition, we showcase our theory by proving the existence of nearly-linea time prompt tuning algorithms (Theorem 3.2).
Practical Implications from Statistical Limits (Section 2). We analyze the universality of prompt tuning transformers with minimal structures and its memorization capacity on general datasets.
Our results show that the universality of prompt tuning pretrained transformer is achievable on as simple as a single-layer, single-head attention transformer. This demonstrates that universality in prompt-tuning isn't limited to large, complex foundation models.
Universality (Theorem 2.4).
Width-Depth Tradeoff (Section 2.4). Our results highlight trade-off in the design choices for the depth and width of FEN (MLP) layers: (i) ((1/c)d((+ FFN layers of width 4 (ii) 2 FFN layers of width ((1 L)))(L))))) In practice, (i) and (ii) differ in memory usage, parallelization, and optimization preferences, leading to distinct application scenarios.
Memorization (Section 2.5). Our memorization results apply to general datasets, whereas prior results are limited to specialized cases. This makes our results go beyond specialized theoretical analysis and align more with practical applications with a suggested long soft-prompt length.
Practical Implications from Computational Limits (Section 3). We analyze the O(L2) bottleneck of prompt tuning transformers and provides useful guidance for designing efficient prompt tuning (approximation) methods with precision guarantees. Let Qp = WoXp. Kp = W Xp. and V,, = Wy with X, [P.X] E Ldx(L,+L), Here L and Lp are the input and soft-prompt length.
Self- and Cross-Attention. Our computational results apply to both self-attention and cross-attention prompt tuning. This is because the norm bound conditions depend on max[|Qpl, K2l..V/l. which are valid for both self- and cross-attention inputs.
Necessary Conditions for Subquadratic Prompt Tuning (Theorem 3.1). Our result suggests proper normalization soft-prompt and weight matrices required to ensure subquadratic prompt tuning inference, i.e., max (plx Kyllmaxs
[mxx S O( [log(og + L)).
Necessary Conditions for Almost Linear Time Prompt Tuning (Theorem 3.2). Our result sug- gests more strict normalization on soft-prompt and weight matrices are required to ensure almost lin- car time prompt tuning inference, i.c., max(1 Qp max: I maxx
[1% [mxxx S o /log(L, (Lp + 4)).
Suitable normalizations for the above can be implemented using pre-activation layer normalization (Xiong et al., 2020; Wang et al., 2019) to control mlaas outlier-free attention activation functions (Hu et al., 2024a) to control | WR mmxx |[ maxx [[ max-
|Xp
17

---

Published as a conference paper at ICLR 2025
B RELATED WORKS, LIMITATIONS AND BROADER IMPACT
B.1 RELATED WORKS
Context-based Fine-tuning and Soft-prompt Tuning. Recently, resource-efficient fine-tuning strategies (Ding et al., 2023; 2022), such as LoRA (Pan et al., 2024; Hayou et. 2024; Hu et al., 2025; 2022), emerge powerful alternatives to conventional full fine-tuning. In contrast, context-based fine-tuning techniques, like hard-prompt tuning (Wen et al., 2024), in-context learning (Xu et al., 2024; Shi et al., 2024; Wei et al., 2023; Dong et al., 2022; Brown et al., 2020), and trefix-tuning (Liang et al., 2024; Li and Liang, 2021), adapt pretrained models to specific tasks without modifying underlying model parameters (Brown et al., 2020; Li and Liang, 2021; Liu et al., 2022). One of the most effective methods is soft-prompt tuning (Liu et al., 2023), which uses real-valued embeddings to guide model outputs. This approach leverages the expressive power of continuous spaces to fine-tune responses, avoiding extensive parameter updates and making it both efficient and less resource-intensive than traditional fine-tuning methods (Lester et al., 2021; Liu et al., 2022).
Universality of Transformers. The universality of transformers refers to their ability to serve as universal approximators. This means that transformers theoretically model any seatennceto-squeeee function to a desired degree of accuracy. Yun al. (2020) show that transformers universally functions by stacking numerous layers of feed-forward functions
approximate requence-to-seqeene and self-attention functions. a different approach, Jiang and Li (2023) affirm the universality of transformers by utilizing the Kolmogoroy-Albee representation Theorem. Furthermore, Alberti et al. (2023) demonstrate universal approximation for architectures that incorporate non-standard attention mechanisms. Most recently. Kajitsuka and Sato (2024) show that transformers with one self-attention layer are a universal approximator. Of independent interest, recent work by Havrilla and Liao (2024) examines the generalization and approximation of transformers under Hölder smoothness and low-dimensional subspace assumptions.
Our paper is motivated by and builds upon works of Yun et al. (2020); Kajitsuka and Sato (2024). Specifically, we study the universality of prompt tuning transformers using the analysis framework by Yun et al. (2020). Furthermore, we extend the contextual mapping property of 1-rank attention by Kajitsuka and Sato (2024) to any-rank attention. This allows us to establish the universality of prompt tuning transformers in the simplest configuration single-layer, single-head attention.
Analysis on Prompt Tuning. Prompt tuning has been successful various applications. However, the theoretical analysis of it is less developed. Petrov et al. (2023) discuss different kinds of context- based learning, and experimentally show when prompt tuning successful adapting to new tasks. In this work, we tackle the prompt tuning problem from theoretical perspective. Oymak al. (2023) identify the cases where the attention layer with prompt tuning is more expressive than a self-attention layer. They utilize prompt tokens dependent weight matrices. In addition, they require weight matrices to be full rank. Conversely, our study explores the expressive power of prompt tuning under more general conditions, without relying on such assumptions. Wang et al. (2023a) show the universality of prompt tuning transformers with an increasing number of layers in proportion to the input data dimension and the quantization grid. Petrov et al. (2024) prove the universality of prompt tuning on transformers with the number of layers linear in the input sequence length. Liang et al. (2024) study the convergence guarantee for prompt tuning with ultra-long soft-prompt in the Neural Tangent Kernel region (NTK), On the other hand, we focus on approximation and computation properties of prompt tuning transformers with
self attention..
Our work builds on (Wang et al., 2023a). as both quantize the input and output domains of sequence- to-sequence functions to establish universal approximation. However, this work differs in three aspects. First, while Wang et al. (2023a) require transformers with a number of layers proportional to the input data dimension and two attention heads, we demonstrate the universality of prompt tuning with the simplest transformer: single-layer, single-head attention transformer. Second, we present the first study to show complete data memorization through prompt tuning, providing a lower bound on the required soft-prompt tokens for single-layer, single-head transformer to memorize any dataset. Lastly, we provide the first comprehensive analysis of the computational limits, proving the existence of nearly-linear time prompt tuning inference algorithms.
18

---

Published as a conference paper at ICLR 2025
Memory Capacity of Transformer. Even though there has not been much analysis on the memory capacity of prompt tuning, there are many works on the memorization of transformers itself. Kim et al. (2022) prove 2n self-attention blocks sufficient for the memorization of finite samples, where n. denotes the sequence length of data. Mahdavi et al. (2023) show that a multi-head-attenioon with h heads is able memorize (hh)) examples. Kajitsuka and Sato (2025; 2024) prove the memorization capacity for a single-layer transformer. They demonstrate that for N sequence- lo-sequence data examples, each with dimension d n, the number of parameters required for memorization is (nNd + d²). Another area of research introduces distinct type of memory capacity for transformers by linking transformer attention mechanisms with dense associative memory models, specifically modern Hopfield networks (Bietti et al., 2024; Hu et al., 2024a;b;e; 2023; Wu al., 2024a;b; Ramsauer et al., 2020).
The closest work to ours is (Wang et al., 2023a), where they discuss the required prompt tokens for prompt tuning on memorizing a special sqquence-t-sequenee examples are required to have exactly two tokens each. In addition, they discussed the memorization of only the last token of each data sequence. In contrast, we provide the first analysis on general cases where prompt tuning memorizes the whole sequence for each example in general dataset with no assumption on the data. In addition, our work is the first to provide the lower bound on the re- quired soft- soft-prompt tokens for memorization.
dataset. In the special dataset, the
B.2 LIMITATIONS AND BROADER IMPACT
Limitations. By the formal nature of this work, our results do not lead to practical implementations. However, we anticipate that our findings will offer valuable insights for future prompt tuning methods.
Moreover, our memorization findings indicate an exponential dependence on the data sequence length and approximation precision 1/c. Although resource-cfficient this exponential dependence implies that prompt tuning pretrained transformers may not be an optimal method for encoding or memorizing information. This leads to two fundamental possibilities:
While not investigated in this work, there may be information information-theoretiic highlights the limitations of our current memory capacity results for prompt tuning.
theoretic lower bound that
If we prove that no upper bound can match this lower bound, it would reveal a fundamental limitation of prompt tuning: is not an information-efficien learning method (or machine).
We plan to investigate these issues in future work.
Broader Impact. This theoretical work aims to shed light on the foundations of large transformer- based models and is not expected have negative social impacts.
19

---

Published as a conference paper at ICLR 2025
C ADDITIONAL THEORETICAL RESULTS: UNIVERSALITY OF TRANSFORMERS WITH 1-LAYER, 1-HEAD, ANY-RANK SELF-ATTENTIO
Lemma 2.2 shows that any-rank single-layer, single-head attention is contextual mapping. A di- rect consequence is the universality of transformers with 1-layer, 1-head, any-rank" self-attention following Kajitsuka and Sato (2024). We believe this result may be of independent interest.
Theorem C.1. Let 1 S < co and > 0. For any freqzeey E Fc, there exists transformer with single-layer, single-head attention and any-rank weight matrices T (or E TB. with (((1/))dl) with positional embedding E Rdx such that da (T, Jee22ey)) I c.
Proof Sketch. Sketch. This proof inspired by (Yun al., 2020) and similar the proof of Lemma F.2.
There are mainly three steps:
1. Given an input data X E Rdd we first apply positional encoding F,, which is given
2
T-1 L-1
0
2
E
2
Then a series of feed-forward layers in the modified Transformer network quantizes X E' to quantized sequence M Jö.L. Here, we define the grid
F.S = 00
5| x 6 87 x x LL 1:
where la: :: bJ = {a, a + c, a 25,... - E, b}. Note that with the positional encoding, our contextual mapping through self-attention won't 't be limited to permutation equivalent functions.
2. Next, by utilizing Lemma 2.2, the single self-attention layer in the modified transformer takes the input M and implements a contextual mapping q Rdx + _
3. Finally, series of feed-forward layers map elements of the contextual embedding ((M) to the desired output value of Sseqpsyy X).
We remark that Step 2 distinguishes us from prior works by utilizing the fact that any- any-rank attention a contextual mapping Lemma 2.2. This improves the result of (Kajitsuka and Sato, 2024), which requires an attention layer of rank one.
Proof of Theorem C.I. First, we apply the positional encoding E E Rd on the input sequence X dx 1, so that each token has different domain, The positional encoding E is given
2
L
0
1
2
L
--1
E
2
We next forward layers (FF) to implement quantization map quantize the input X + E in to its discrete version M G..r. The grid Fs.s. is defined as
8j x [1 2 07d 1L-1:6 8]d
By any-rank attention, refer attention head with generic weights of arbitrary rank.
20

---

Published as a conference paper at ICLR 2025
where la : b] := {a, + E, 2e,...,b E, b}. Note that the first column of X + E is in [0, 1]" the second is in [1, 2|" and so on. Here, we write the quantization mapping as
0. 1j x L 1, 1, 00:8: -5 x.
: 8: 87
Inspired by the construction recipe by (Yun al., 2020), this task is realized by dL/6 feed-forward layers. We add / layers of ((FF) with the following form, for l 0, L- â and i ,....,d
Z - 2 + e ((600)² 2 2- k01%)
0 t<oort2 --+11 o
6(1)
(C.1)
where e(!) = (1,0,0,... 0) Rd and o(t) E + is an entrywise function, where the set of activation functions consists of all piece-wise linear functions with at least one piece being constant and at most three pieces. Furthermore, any activation function ø E Φ is realized by 4 MLP neurons. Each layer in the form of (C.1) quantizes X (the i-th row) in [kō, kō + 6) to kō. We denote output after the feed-forward layers as M E G.,
Next, in order to utilize Lemma 2.2, we observe that the quantized output M from the previous step has no duplicate tokens, since each column has a unique domain. Also, we see that M token-wise (dd, Vd(L- 6), vdo) -separated. This easily observed have, for any k, I E
|Ma > Vd,
|MM < vd(L -), 6),
M M, > v88.
As result, with Lemma 2.2, arrive (T, A--ootexettlll mapping q: 1R + gaxt where
Vdo
35
r = vT(T. 8)
Vell.
4
A exp(=5(p[ddmmm))
Now have successfully mapped each input sequence X E to unique contextual embeddings ((M) E RdxL, We next associate each unique embeddings to a corresponding expected output of Iseupsey(X)
We use feed-forward layers map each token of ((M) to the desired [o, 11d As (Yun al., 2020, C.3), with method similar to (C.1), we need one layer for each unique value of ( ) for each M E L. There are in total (1/8)aL possibilities of M and each corresponds to some output of hoog2soy (PP, -)). Since we only focus on the last L tokens of output, we require O (L(1/8)"*) O (8 di) layers to map these distinct numbers to expected outputs.
This completes the proof for transformers T E TT) T.1114 the same recipe, and we refer to the proof of Lemma G.2 for details.
1.14 The proof for transformers т E T T1.1.r follows
21

---

Published as a conference paper at ICLR 2025
D BACKGROUND: BOLTZMANN OPERATOR AND ATTENTION MECHANISM
Here, present auxiliary definitions and lemmas to prepare proofs.
To demonstrate that a single-layer self-attention mechanism with matrices of any rank acts as a contextual map, we follow (Kajitsuka and Sato, 2024; Asadi and Littman, 2017). Specifically, utilize the connection between self-attention mechanisms and the Boltzmann operator Boltz.
In this section, introduce non-original but still necessary auxiliary lemmas. We defer the proofs to Appendix K for completeness. Below, we start with the definition of the Boltzmann operator Boltz.
Following (Asadi and Littman, 2017; Kajitsuka and Sato, 2024), we associate the Softmax function with the Boltzmann operator Boltz defined below:
Boltzmann Operator.
Definition D.1 (Softmax and Boltz). Let (Zi...... ,,, E 1 and the function Softmax R² RR operate element-wise: Softmax (z), = exp (2,) /E/=1 exp (zz). Denote p = (P1.... .Pn) = Softmax (=) E R" with p. = Softmax (z);- The Boltzmann operator Boltz R - IR is defined as
Boltz(z) Softmax(2) 2 ZTp P.P..
(D.1)
To give brief overview to this section, Appendix D.I, we first introduced the essential properties of Boltz. Next, in Appendix D.2, we utilized these properties to further illustrate the Boltz operator's ability to maintain the separation between inputs.
In the following, present the essential properties of Boltz in Appendix D.I.
D.1 ESSENTIAL PROPERTIES OF BOLTZMANN OPERATOR
Before characterizing the Boltzmann operator Boltz, we introduce some useful functions and essential properties Boltz from (Kajitsuka and Sato, 2024) to facilitate our proofs.
We first recall the partition function and the (Gibbs) entropy function from statistical physics,
((2) exp(z:), and S(p) = Σ In(p:).
(D.2)
Then, the next lemma presents the relation between the Boltzmann operator Boltz, partition function Z and entropy S.
Lemma D.1 (Boltz, Z and S). With the definitions given above and a vector 2 = (zi,...,24 E R", the Boltzmann operator Boltz also takes the form
Boltz(z) S(p) In 2(2).
Proof. See Appendix K.1 for a detailed proof.
Next, recall that Boltz decreases monotonically when the maximum entry sufficiently distant from the other entries.
Lemma D.2 (Monotonically Decrease, Lemma 4 of (Kajitsuka and Sato, 2024)). Given vector 2 = (Z Zn) E R", the Boltzmann operator Boltz(z) monotonically decreases in the direction of 2; when maxje[n] 2j 24 In 1, that is,
i Boltz(z) P. (1 11pp + S(p)) 0.
0z
Proof. See Appendix K.2 for detailed proof.
22

---

Published as a conference paper at ICLR 2025
The next lemma shows the concavity of Boltz when the max entry and the rest of the entries distant enough.
Lemma D.3 (Concave, Lemma 5 of (Kajitsuka and Sato, 2024)), Given vector = (Z1..... 2n E R" the Boltzmann operator Boltz(z) is concave with respect 2 when maxje[n] 2j 2 In n that is,
Boltz(z) < 0.
0z
Proof. See Appendix K.3 a detailed proof.
To ease the later calculation and better understand the characteristics of the Boltzmann operator, the next lemma shows the bounds of the output of Boltz when given inputs with certain constraints.
Lemma D.4 (Lower Bound of Boltz with (ö)- -epparrae Input), Given tokenwise (d)-separated vector 2 = (zi,..., 2n) E R" with 2 2 and >> In n + 1. Also let the entries of z be sorted in decreasing order with no duplicate entry, that is, for any i E [n], j.
6.
Then Boltzmann operator Boltz(2) lower bounded by Boltz(2) > Boltz(z')
where z' = (21, 21 - 6,...,23 21 5)
Proof. See Appendix K.4 for a detailed proof.
Next, we present another property of Boltz, which states that when two vectors share the same first entries but differ in dimension, the output of Boltz for the lower-dimensional vector will be larger.
Lemma D.5 (Boltz Value Comparison). Given two tokenwise (d)-searatted vectors z (zi,..., 2n) R", z' = (zf...., =/m)) RM with m > 2 2 and 5 In 1. Also let the entries z, x be sorted decreasing order with no duplicate entry. In addition, let the first n entries of z' be z, that is,
(z/,...,,2.) 2n)
Then, have
Boltz(2) Boltz(2').
Proof.
See Appendix K.5 for a detailed proof.
With a solid understanding of Boltz established, we leverage its properties to demonstrate that Boltz preserves the separation between two distinct input tokens.
D.2 DISTANCE PRESERVATION OF BOLTZMANN OPERATOR
In this section, by utilizing the above properties, we show that when given well separated input tokens, the output of Boltz is also separated. We start by examining specific cases with more stringent constraints on the inputs, and subsequently expand our discussion to more general scenarios.
We first discuss the case when the two input vector has same entries.
23

---

Published as a conference paper at ICLR 2025
Lemma D.6 (Input of Complete Different Entries, Lemma of (Kajitsuka and Sato, 2024)), Let and consider two vectors (01,-... an), (61,-..;0m) bn) E R In addition, assume the following conditions hold:
Decreasing order entries: The entries and are sorted strictly decreasing order.
41
02
On and b > b2 >
> bn-
Tokenwise (e)-separateness: For any i,j E [n]] if a; + bj
a4 - byو > 8,
and i <.
0, 0j 8 b bj > 6,
where 8 2 41nm n..
Initial dominance: The largest element in ais strictly greater than the largest element in b,
a1 > b2
Under these assumptions, we have
Boltz(a) Boltz(b) (In -
(a: (bi-
Proof Sketch. To find the lower bound of Boltz Boltz(b), we first find some lower bound of Boluz(a) and some upper bound of Boltx(b) that ease the computation. From Lemma D.4, we have
that Boltz(a)= > Boltz(a') where a' = (a1, a1 - 6, 8.....(1 01 8) In addition, by definition of Boltz the upper bound of Boltz(b) is Boltz(b) < 61 As result, we evaluate Boltz(a') b1 complete the proof. See Appendix K.6 for a detailed proof.
Next, show that when two inputs are different only by one last entry, their Boltz outputs still different with a certain distance.
Lemma D.7 (Input of One Entry Difference, Lemma 6 of (Kajitsuka and Sato, 2024)), Consider n 2 2. and two vectors a = (a),..., an-1, ),), b = (b),... 1 b,) E IR.. In addition, assume the following conditions hold:
Identical first entries: The first n entries of a the same as 6,
a; = b,Vi E [n - 1].
Strict inequality for last entry: The last entry of a is strictly greater than that of b,
Og bn-
Well separated: The last entry is sufficiently smaller than the maximum of the first n entries
of a,
max a4 a, > Inm +
Then the difference of Boltz(a) between Boltz(b) is lower bounded as
b
Boltz(b) Boltz(a) (a, b,)) (5 + an bn In
1)
Σ ch
24

---

Published as a conference paper at ICLR 2025
Proof. See Appendix K.7 for detailed proof.
Now, we consider a more general case, where the top entries are the same.
Lemma D.8 (Input of Matching Top Entries, Lemma 7 of (Kajitsuka and Sato, 2024)), Let and consider two vectors (a1,..., an). (bI..... b,) E R In addition, assume the following conditions hold:
Decreasing order entries: The entries of and are sorted in strictly decreasing order,
02 > > and
b1 > b2 ... > bn.
Tokenwise (d)-separateness: For any i,j E [n]]. if * bj
a. - bزو > 8,
and i <
0, 0j 8,
b, bj > 6,
where 5 2 4 nnn.
Identical first entries: Let a, have the same top-k entries for E [n 1], which is
(01, ax) (bI...., by)
(A: 1)-th dominance: The largest element in ais strictly greater than the largest element in b.
0&+1 bk+1-
Under these assumptions, we have
Boltz(a) - Boltz(b) > In (n:) e ( -brr1)
Proof Sketch. As the top-k entries of a, are the same, and all entries are (d)-separated while sorted decreasing order, when 0k+1 > b , we have
Boltz(b) Boltz(a).
To understand the intuition behind this, first recognize that Boltz calculates a weighted sum of elements, assigning higher weights to larger entries. Additionally, the total sum of all weights equals one. Consequently, when all entries are distinct and arranged descending order, larger (I: + 1)-th entry, shares more weight from the top & greatest terms, compared smaller (K 1)-th entry. This results in a lower weighted sum.
Next, we compute the value of Boltz(b) Boltz((). By Lemma D.5, we have that Boltz(a) is upper bounded by Bollz(oup). where
aup (0), .2...., ak. 4x+1))
Also, similar to Lemma D.4, Boltz(b) is lower bounded by Boltz(bo.) where
bio (a), 42 ... age bu+ be.t...., bb+1).
Computing Boltz(b,) Boltz (up) is easier than directly calculating Boltz(b) Boltz(a) as able to decompose Boltz(br.) and utilize Lemma D.7 to arrive at the final bound. See Appendix K.8 for detailed proof.
25

---

Published as a conference paper at ICLR 2025
Finally, by utilizing the results above, show that the Boltzmann operator is mapping that projects input sequences to scalar values while preserving some distance.
Lemma D.9 (Boltz Preserves Distance, Lemma of (Kajitsuaa and Sato, 2024)), Given (r, 6)- tokenwise separated vectors 2(1), ....., (N) E R" with no duplicate entries in each vector, that
(1) 2! + =t
where E [A] and s,t E [n], s # t. Also, let
8 2 4 lnn.
Then, the outputs of the Boltzmann operator are (7, 8") seeparatte
Boltz (1) S S,
(D.3)
Boltz (2())
Boltz (0)) > 8' = =inn -In²(n) .e -
27
(D.4)
for all i,j E [NV], j.
Proof. See Appendix K.9 for detailed proof.
We have now established that the Boltz operator has the property of preserving the distances between inputs.
26

---

Published as a conference paper at ICLR 2025
E PROOFS OF SECTION 2.2
In this section, by relating Softmax with Boltz, we show that the one layer single head self- attention with weight matrices of any rank is contextual mapping.
first introduce a helper lemma.
Lemma E.1 (Lemma 13 of (Park et al., 2021)), For any finite subset C Rd, there exists least one unit vector E IRd such that
x'll
$
Iu (x x') 1 2'1
X
Td
for any x E X.
Proof. See Appendix K.10 for detailed proof.
E.I PROOFS OF LEMMA 2.2
With Lemma E.I, we develop a method to configure weight matrices of a self-attention layer.
Lemma F.2 (Construction of Weight Matrices). Given a dataset with a (Timin- Tmax e)-separated
finite vocabulary V C Rdd there exist rank-p weight matrices WK. Wq RRexd such that
(Wkva)" (WQue) (Wxu)) (WQua) 6,
for any 8 > 0, any min (d, s) p 2 1, and any Vas vb. Ve E with vo * us. Specifically, the
matrices are constructed as follows:
a 1/ E Rexd
WK Σ nag Raxd Wq Σ
where Q1 of E Rd are unit vectors satisfying Lemma E.1, and pr, ph RR satisfy
5 I PTMl 2 5(VV + 1)da CYimin
Proof of Lemma E.2. We build our proof upon (Kajitsuka and Sato, 2024).
We start the proof by applying Lemma E. to V U {0}. We obtain at least unit vector Rd such that for any Va, Ub E V {0} and va # ub we have
1/ vbll S l (va - vb)l S 1l1a - voll-
(VI + 1)
By choosing Uy 0, we have that for any Ue E V
(IV) + 1) a.s |ell S 1q de S |ell-
(E.1)
For convenience, we denote the set of all unit vector y that satisfies (F. as Q. where
o {RE
([V) + 10. |ell S 1a ve S [|vel]
27

---

Published as a conference paper at ICLR 2025
Next, we choose some arbitrary vector pairs P1.P1 R that satisfy
pT ((2) +1' 8
(F.2)
Mymin
We construct the weight matrices by setting
WK
pige E B2xdd
i=1
Wq
>
Rexd
j=1
where P1,pl p1 satisfies (E.2) and q1, 11 E Q. We arrive at (WKua) (Wque) (Wkos) (WQve)
(va vb) T (Wx) (Wove)
0
(Vo vb)
Σ q.p..
Σ p/ Vo
UUa vb) gipt
Σ plj
vo
(Va- vn)
4.P. p3 TT
i= j=1
(va vb) |n|
/ T vel lpT pil
(We choose
1p p4
large enough so it's the dominating term in the sum.)
8 Emmin
1
(1V + 2) 10 - voll (VV] + 1)
([V) + 1) ||vell
(By (E.1) and (E.2))
8.
(By (7mins Ymaax; c) separatennss of V)
This completes the proof.
Now we present the result showing that softmax-bascl 1-layer attention block is a contextual mapping.
Lemma E.3 (Lemma 2.2 Restated), Let z(1)... Z(N) E R be (Tmins Tmaxx -otonnee separated embeddings, with the vocabulary set V = USE[N] vGt c Rdd Additionally, assume
no duplicate word tokens in each sequence, i.e., 2002 + 2 for any E [N] and k, E [4]. Then, there exists a I-layer, single-head attention mechanism with weight matrices W(O) dd and Wv, WK, Wq E Ixd that serves as (y, contextua mapping for the embeddings 2(1) ((N), where:
and 8 = exp (-5e '11' dr log L), with Tmnax/ Famaxx//umm /miin
7 7max 4
Remark E.1 (Comparing with Existing Works). In comparison with (Kajitsuka and Sato, 2024), they provided a proof for the case where all self-attention weight matrices Wv. WK. Wo E Rexd strictly rank-1. However, this is almost impossible for any pre-trained transformer based models. Here, by considering self-attention weight matrices of rank-p where min (d, s) 2 2 1, we are able to show that singe-head-single--aeer self-attention with matrices of any rank is contextual mapping.
28

---

Published as a conference paper at ICLR 2025
Remark E.2. In (Kajitsuka and Sato, 2024), y and å chosen follows:
1max (12) 12 3)rd exp 1) (2 (2 I. + max
2(In 2 Tmin
T Timax 4'
A
4e7min
Since the exponential term dominates the polynomial terms, Lemma 2.2, we simplify A to exp(-0(e-(p)) [ L)).
Proof Sketch. We generalize the results of (Kajisuua and Sato, 2024, Theorem 2) where all weight matrices have be rank-1. We eliminate the rank-1 requirement, and extend the lemma for weights of any rank p. This is achieved by constructing the weight matrices as outer product sum Σ u.v. where E R², U R Specifically, we divide the proof into two parts:
We first construct softmax-based self-attention that maps different input tokens to unique contex- tual embeddings, by configuring weight matrices according to Lemma E.2.
Secondly, for the identical tokens within different context, we utilize the tokenwise separateness guaranteed by Lemma E.2 and Lemma D.9 which shows Boltz preserves some separateness.
As a result, we prove that the self-attention function distinguishes input embeddings 2 such that v(0) f vO3
2.0)
Proof of Lemma 2.2. We build our proof upon (Kajitsuka and Sato, 2024). We construct self- attention layer that is a contextual mapping. There are mainly two things to prove. We first show that the attention later we constructed maps different tokens to unique ids. Secondly, we prove that the self-attention function distinguishes duplicate input tokens within different context. For the first part, show that our self-attention layer satisfies:
|wo (Wv Softmax [WWZZ))) T (woz.?)) (W
|
<
(E.3)
for E [N] and & E [n]. Since with (E.3), it easy to show that
y (SA) (z(()
((AA) (z())
((1) 2
(1)) v/61
(E.4)
1.k
2
(i) w6n
z
(
c
(By e-separatedness of Z and E.3)
4
2'
for any i,j E [N] and k, E [rx] such that (.1) i We define the weight matrices as
+ z(()
Now, we prove (E.3) by utilizing Lemma E.2.
WK K
Σ p:g E Bxd
Wa Σ 1/,5
Roxd
j=1
where pi,p' E IR and gi d' E RRdd addition, let 4ln and pI, RR an arbitrary vector pair that satisfies
1p. p1 = ((V) + 1 8
(E.5)
CYmin
29

---

Published as a conference paper at ICLR 2025
Then by Lemma E.2, there is some unit vector 01 such that we have,
(Wxv)) (Wov))) (Wxu)) (Wou.) > 6,
(E.6)
for any Va Ub, ve E V with vo # ub. In addition, for the other two weight matrices Wo E Raxs and Wy E Rexd we set
e Wv
Σ Th E BRodd 1=1
(E.7)
where d" E Rd, of qi and pp R is some nonzero vector that satisfies
[Wop
(E.8)
4prmaxx
for any i [p]. a result, we now bound v as:
| = Wo (())
Softmax
(
$ Wo (W,
(Denote at. Softmax
(wxzZ0) (Woz )
Wo (Wv
===1
max K'En]
Wo Wv 2(1) (()
EBer o 1)
max E'En]
Wo Σ ved IT
z,(1)
(By Lemma E.2)
WWP
max E
1." z(10)
(By (E.8)
max KEEn
(By (E.8) and |44 || 1)
4
4mma
4
Next, for the second part, prove that with the weight matrices Wo, Wv, WK. WqQ configured above, the attention layer distinguishes duplicate input tokens with different context, z!() z
7,kk
with yli) * Vo) We choose any i,j [N] and k, / [n] such that - z!! and p(t) * vo) In
addition, define (+), al)) as
(1) (W>Z(0) T (Wez!!) ER. ( (WazVi) (Woz!?) E R
From (E.6) we have that (1) and a are tokenwise (y, -sspprrate where y is computed by
(6) a
= (Wxz (
30

---

Published as a conference paper at ICLR 2025
Σ pigi _ 2.1 (,ke)
Σ pluy 2
2 2007 :,k' qiPi
Σ ps 2
s,kr q:P;
(
5,ke Qi |p. p31 1/ 2.4
S (M2) 1)dd 8
mmx
(By (E.5) and | -11b5ll =
CYmin
Therefore,
87 mmax
7= (IV] 1)td
Cymin
Now, since v+) * Vli and there is no duplicate token in z(0) and Z respectively, we use Lemma D.9 and obtain that
Boltz (o()) Boltz (a(o)) (a())
Softmax [o.0] - (al))) Softmax [aco] (F.9)
8'
(Inn)²e 27
As assumed 7,00) 2 have
T (1())
Softmax [act]]
- (a(ai)) Softmax [aco]
(E.
(1) 1.k
(Wo)T T Wx (z(0) Softmax [ali)] -66 Softmax [ab1)
Σ 05155 Σ pog. ) (z() Softmax [act] -Z0 Softmax [oco1)
(2
(By Lemma E.2)
2!!91
105 pil (1 z Softmax [alo]] - (1. 2 Softmax [ab]
1=1
Ymax (IV) + 1)4 Td 8
(1T220) 20) Softmax [at0]] - (()) Softmax [a6i]]
Cluin
(By (E.5)
By combining (E.9) and (E.10), we have
4: T 2(0) Softmax [a[0]- - -(1 2(1) Softmax [aco]]
8'
EYmmin
(E.
(|D) + 17 dō
31

---

Published as a conference paper at ICLR 2025
Now arrive the lower bound of the difference between the self-attention outputs of Z Z
as:
(SA)
(z(())
(2(3) -
(E.
i,k
Wo (Wv
Soflmax [a() -oo (wrzu)) Sofumax [ato)
|ork'll
(00 TT z(()) TT.T
Softmax [a()]
(o: z(0) Softmax [aci]
(Wv >i ((
8'
Eymin
(By (E.8) and (E.
4 Ymax (IV) + 1)a fmax
where 5 = 4 In n and 8' = In2 22
27 with y = ([V) + 11) maxad (eiin) Note that we are able
use (E. in the last inequality of (E.12) because (E.11) is guaranteed by gı, and set of qi when constructing Wv in (E.7),
32

---

Published as a conference paper at ICLR 2025
F PROOFS OF SECTION 2.3
We consider the continuous
functions on a compact set of sequence as fseq2saq"
[0. 1 + [0, 1]axL, Furthermore, consider the function class of continuous sequence-fo-sequenee
Fc which is C-Lipschitz in &a norm. Explicitly, for any Sseqsseq E Fc and input embeddings
Z, Z', we have
[ regusey (?) Sseuzzey (z')la S CI - lll
In addition, we consider simple transformers E T which consist of single-head single-layer size-one self-attention f(SA) E ((S)) and 6 + lz feed-forward layers f( FF(F) each with MLP hidden neurons:
T1.14 == (r: R pdx4|T= (FFF) ..... of ((FF) f((A) ((FF) o... f1 (PF) fh
Stz
Finally, define the approximation error for some given functions f1, J2 as:
do (21, ((111(2)- f2())) dz
(F.I)
In this section, we prove the universality of prompt tuning by showing that there exists simple transformer of single-layer self-attention T such that for any Seegseyy E Fc, prompt tuning on approximates this function up to some error é >> O.
The proof follows the construction base recipe of (Yun al., 2020) and (Wang al., 2023a). We start by quantizing the input and output domain of Fc such that - for each faeq E Fc, we obtain a quantized function [seq2eaq G5.L + G5,7 where G8 = {0, 25. Here, seqgseq Fc denote the seq2seq function and quantized function class, respectively. This basically performing a piece-wise constant approximation, i.e., the values inside a quantized grid assume the same value. Next, build surrogate quantized sequence-to-see ()dx(Lx+L) that takes the
8]dx1.
function
heegsey +5, - -8,(L,-) with (),(L,+L) = {0, 5, 25, concatenation of prompts and embeddings as inputs. Importantly, we let "the last tokes" of this quantized function heey2syy approximates any fseq2wey E Fc by taking different prompts P. Finally, we construct some transformer E T...1.4 to approximate haeepway- This leads to a chaining reduction of approximations, which implies E T.... approximates faeq2soq up any accuracy e.
F.1 PROOF OF LEMMA 2.3
We start by building quantized sequence-to-sequeee functions heeqpsey 98,(1.,+L) -> (5,(L,+L)) with quantized prompts to approximate Faeqsoq. Next, we approximate hooq2scq with transformer functions T1.1.4 1,4 To achieve this, self-attention layer as contextual mapping. As result, output domain of transformers. Also, we utilize construct transformer for prompt tuning approximate any continuous requence-to-sequens function.
the feed-forward layer for quantizing the input and
First, introduce the lemma below which shows that, the quantized sequence- squeenceto-seqquncce function I seqsee is approximated by some sequence-to-sequene to-sequence function heegasey (8,(T,,+ - G8, where Go,(L,+L) = 6, 6,
8] dx
Lemma F.1 (Lemma 2.3 Restated), Let Fc be class of C-Lipschitz sequence-tor to to-ueuenccee functions, where each function Seequsea [0, 1 [0, 1 dxdxL Define the discrete function space 95,(L,+2) (0, 6, 25....,. 8) x)dx(LL)))) (L,+ Then, there exists a function Muegsesy 95,(L,+L) - (3,(L, such that for any freq200q E Fc, there exists a prompt P E IRdx satisfying
dp -D.,.. Sropan)) S c/2,
33

---

Published as a conference paper at ICLR 2025
where the prompt sequence length Lp satisfies Lp LA, with X - ((LL)
Proof of Lemma F.I. We first quantize the input and output sequence domain of Fo by quantizing
[0, 1]dxL into a grid space Gs, = {0, d, 26...., 8) 5]dxL, Observe that there are n (1) aZ
different matrices in the grid space G8,L. Now, consider all the possible input to output mappings,
have n² piece-wise constant functions I seqpseg E Fc.. We define J Sequsey Ga.t. J> Go.t.
{ [saq2s0g (2)
Z E Go.L otherwise
Fseq2o0y (Z)
[ sss2soa (?*)
where k2 < Zs.j. Zi, S (kr,) + 1) 8, while Z E 18,7 and Kis, E {0, 1, 1/6 - 1}. We set the function class for the quantized space Fc = ( sequseq: seq2saq soq2seq Then, by utilizing the C-Lipschitzness, we have that for any fsaq2saq E Fc, there a piece-wise constant approximation function [ Seequsyy E Fc that satisfies
F(2)
((m)
( |l |1Fro2200 (2)
1/a
do (f seq2seq: fsoq2seg)
fseq200q (2)lla
(By (F.1))
(ʃ (C8)² dI
1/a
.d..) dz
(By C-Lipschitznes))
Co(dL)
By choosing = 6* such that C :/2 S c/2, we have da (F segireyy Sseubeyy) S 6 2
(F22
Next, we quantize the prompts P E RdxLp, We consider a set of quantized prompts in grid space Go,L, {0, 6, 26, ...,, 8] dxxxLp, This gives m, (1) dLp different quantized prompts. We denote this set of prompts as P = (P(1), p(2) "..,..,,,mp, p(mm))
Since there are = n (+dr
با functions in Fo, the required prompt length Lp to index all m
functions in Fo is This gives
dL Lp 8
( ((())) dL
2 L
(Since we choose ó such that C8(dL) < </2)
Finally, define some quantized function hoaq2sa G3,(LoL)) Go,(Lp+2) where G8,(L,+L) {0, 6, 25, .., 1 (T,p(() and let
Macgzsoy
[[p(9,2] :.hp:
-())
sequseg (2).
(F33
In addition, we set the first Lp columns of hsoggsoa to be zero, which is
hooq2s0q ([p(0,)))
k,ibp 0,
34

---

Published as a conference paper at ICLR 2025
for all Z [0, 1| PE L., Furthermore, let
Mscag2009 (LP, D)).. Isseuszey (1 2)) 1))..
PEP otherwise
Bueu2see (1P, (P,2))..
where kz < P.g. (kig + 1) while P E P and kjj E (0. -}. 1/8
As a result, we show that with properly chosen grid granularity 6n, for any sequence-to- sequence function Sroq2eg Fc, we build quantized function h with prompt / that approximates Ssapsey with error e/2.
da (1ooa2500 -D), froqus0)) da (Fsoq2sqq fseq200)) E/22.
This completes the proof.
F.2 PROOFS LEMMA 2.4
Here we show 7 E TA T.1.1 approximates the surrogate quantized seq2seq function hgeg2seg up to any precision. To do this, we utilize Lemma 2.2 to construct transformer E T Then we show that this transformer т approximates quantized aequence-to-sequenee functions heeupsey ((P.
Lemma F.2 (Lemma 2.4 Restated). For any given quantized eqquence-to-sequenee function hacq2soq (d > L) with +L) {0, 6, 26..... 1 8)dx (L,+ there exists transformer T E T 1.1. with positional encoding E E (d 4), such that T = h[[P, 1)
Proof Sketch. This lemma is inspired by (Wang et al., 2023a, Lemma 2). There are mainly three steps:
1. Given input data with prompt [P, Z] E (Lp+L)) we first apply positional encoding F, which given as
0 2
Lp + L 1
0
Lp + L 1-1
E
I. +
Then series of feed-forward layers in the modified Transformer network quantizes [P, Z| E to a quantized sequence M Gs,(tyy1.. Here, define the grid
Go,LL,+) == 00: 8 5] x 5: 8j x [L, + Lp 6]
where :a: ::: ::bb = {a, a + E, a + 2E,..., b- E, b}. Note that with the positional encoding, our contextual mapping through self-attention won't 't be limited to permutation equivalent functions.
2. Next, by utilizing Lemma 2.2, the single self-attention layer in the modified transformer takes the input M and implements contextual mapping q Rdx(L+L.) + LL)
3. Finally, series of feed-forward layers map elements of the contextual embedding (MM) to the desired output value of heegsssy (P, Z)).
We remark that Step 2 distinguishes from prior works by utilizing the fact that any-ra any-rank attention a contextual mapping Lemma 2.2. This dramatically improves the result (Wang et al., 2023a), which requires depth of dT./c layers, to just single layer.
35

---

Published as a conference paper at ICLR 2025
Proof of Lemma F.2. First, apply the positional encoding E E (dx((E+t)) the input sequence with prompt sequence [P, 2] E Rdx(Lp+L), so that each token has a different domain. The positional encoding given
2 Lp + L
0 2 ...
4
E
T + I
We next use feed-forward layers f(+)) to implement quantization map quantize the input [P. 2 + E in to its discrete version M (8, The grid (h, 1.) is defined as
G8.14,+2 = 6: 1-::::1-:00 5/ x 1 00 07 x.. x [K, + L 1 :: Lp + L 5]a
where [a: l b] == {a. a, 22, ..... e, b}. Note that the first column of [P, 2] + E is in [0, 1] the second is in [1, 2] and so on. Here, we write the quantization mapping as
[0, 11 x L + L 1, Lp + LJd + [0 8: 57 x Lp - 1: Lp + L 819
where (a: : b) := (a, a e, + 28 ...... ., E, b}. Inspired by the construction recipe by (Yun et al., 2020), this task realized by Lg + L) feed layers. We add d(Lpp + L)/ō layers of ((FF) with the following form, for k 0, 0, ...., (Lp L) 8 and I....,d. .d:
- 2 - (00 =0 ((=0)) z -k1,,
0 0<rot
x()) = 11++1 0 6
(F.4)
where e(1) = (1, 0) Rd and o(t) E + is entrywise function, where the set of activation functions consists of all piece-wise linear functions with at least one piece being constant and at most three pieces. Furthermore, any activation function ø E O is realized by 4 MLP neurons. Each layer in the form of (F.4) quantizes X,, (the i-th row) in (kō kō + 6) to kō. We denote output after the feed-forward layers as E G..
Next, in order utilize Lemma 2.2, observe that the quantized output M from the previous step has no duplicate tokens, since each column has a unique domain. Also, we see that M token-wise (Vd, vd(L' 5), /8 separated where L' Lp + L. This is easily observed as we have, for any k, L. [Lp + L].
|M. Vd.
|M < vd(L, + L - 8);
MM M. vdo.
As result, with Lemma 2.2, we arrive at (I' A) conttextull mapping q (Lp+ (Lx(()+ where
Vdo
38 4
F = Va(L' 8) = VolL'
4
A =
Now we have successfully mapped each input sequence [P, Z] + E to unique context ID q(M) LL,+LL We next associate each unique embeddings corresponding expected output of h[[,,-))
Finally, feed-forward layers map each token of q (M) the desired [0, 1] As in (Yun et al., 2020, C.3), with method similar to (F.4) we need one layer for each unique value of (M)
36

---

Published as a conference paper at ICLR 2025
for each M (.p( There are in total (1/8)((ppt)) possibilities of M and each corresponds to some output of Raca2soq (PP, =]). Since only focus the last L tokens of output, we require O (I(1/5)((xx+)) O (8 (8-dl(+tt)) layers map these distinct numbers expected outputs.
This completes the proof.
F.3 PROOFS THEOREM 2.3
With Lemma F2, we are able to find a transformer T E T such that T([P, 2]) = ([) Finally, arrive the theorem that shows that a transformer of one single-head self-attention layer a universal approximator for sequence-t--sequenee functions.
Theorem F.1 (Theorem 2.3 Restated), Let - p < oc and T with single self-attention layer such that for any feeq2seq Fc, there exists prompt P E Rdx satisfying da (T([P, -1).. feegoaa) S c.
There exists transformer
Proof of Theorem 2.3. Combining Lemma F.1 and Lemma F:2, we arrive transformer T E .1..1. with prompt P Gs,L, such that for any sequence-to requence-to-sqquene to-sequnnce freg2seq E Fc.
da T (PP.-D..gp: (
da (T
Mosq2sag ([P, ..P.D)D.o:)) + da (haaq2s00 ([P, 1), kp: Ssequesa)
6.
This completes the proof.
37

---

Published as a conference paper at ICLR 2025
G PROOFS OF SECTION 2.4
G.1 PROOF OF LEMMA 2.5
For the transformer TTA T in the previous section Appendix we compute the required number of FFN layers.
Lemma G.1 (Lemmaa 2.5 Restated). A transformer E T as defined in (2.3), requires ((1/c)d(l,tb) FFN layers be a universal approximator through prompt tuning.
Proof. As shown in the final step of the proof for Lemma F.2, we require O (8-d((1p:tE)) layers to map these distinct numbers to expected outputs. Recall that in (F22), have the relation of quantization granularity å and function approximation error Co(dL) I e/2. We write the number of feed-forward layers as O (2L(C(d)) /e) O (e (od(Ltt()), where C' is the Lipschitz constant and a is from the -nom we use for measuring the approximation emro.
L
G.2 PROOF OF THEOREM 2.4
In this section, we prove the universality of prompt tuning on another simple transformer architecture with smaller depth than T from Section 2.3. This provides us case for trade off between the depth and width of the transformer.
Consider transformers E Th. which consist of single-head single-layer size-one self-attention ((AA) and two feed-forward layers f(FF) ( each with MLP hidden neurons:
T 1.b. (g Raxt + R (MF) ((SA) f(H)))
We prove the universality of prompt tuning by showing that there exists transformer network I such that for any fregsey E Fcs prompt tuning approximates this function up to some error e 0.
Similar to the proof of Theorem F.I. we start by quantizing the input and output domain of Fo to obtain quantized functions
F Toeqzsay G8.L + GE.L.
where
G8.7 (0, .... 8lax1.
This basically performing piece-wise constant approximation. Next, we build quantized sequence-to-sequee function
Bueg2sog 95,LL,+L) - 95.(L,+L) with 95.(L,+L) {0,5, 26 ........ .,, 1011---xxxee (xxx())))))
that takes the concatenation of prompts P and embeddings Z as inputs. This quantized function heeq2say approximates any Ssqq2eeq E Fc by taking different prompts P. Finally, we construct some
transformer 7 E T to approximate lsoqg50q.
First, utilize the results from Lemma F.1, which shows that the quantized sequence-to-sequene function F ssquzey is approximated by some sequence toaeeeett--qqueee to-sequence function
heog200n G5.(Lo+)) - (5,(L,+1 with G5,(L,+L) {0,5,28 1-ddx((ppt))
38

---

Published as a conference paper at ICLR 2025
Next, in Lemma G.2, utilize Lemma 2.2 construct transformer TB 1,1," Then, the transformer to approximate quantized sequence-tossqquene to-seuennce functions hggg ((P.-I).
Lemma G.2 (Transformer Construction). For any given quantized sequence-to-sequeene function
Mgog2000 (L - (6,(L,+L) with (5.(L,+L) {0, 26, 8) ()xx(1,,())
there exists transformer T T1.1. with positional embedding E' E (d, such that
da (T, h([P, DD...:)) $ c/2.
Proof Sketch. The proof this lemma follows a similar idea as Lemma F.2. Nonetheless, by applying the construction technique from (Kajitsuka and Sato, 2024), employ transformer configuration that utilizes just two feed-forward layers.
The proof consists of three steps:
1. Given an input data with prompt [P, Z] E (dx((t)t)) we first apply positional encoding E, which is given as
0 2 :
Ip + T. 1
Tp + T
F
2
Lp + L
Then a series of feed-forward layers in the modified Transformer network quantizes [P, + E a quantized sequence M E Gs. Here, we define the grid
::: 1] x [1 8: 6: 2) x ................................ x [Tp + - L, + I.jd
: 6] = {a, a + E, 2 e, 6}. Note that with the positional encoding, our contextual mapping through self-attention won't limited to permutation equivalent functions.
where ja s::
2. Next, by utilizing Lemma 2.2, the single self- aff-attention layer in the modified transformer takes the input M and implements contextual mapping q Rdx(L+4p) + (L)
3. Finally, series feed-forward layers map elements of the contextual embedding (M) the desired output value of huggusey (PP, Z)).
Proof of Lemma G.2. First, we apply the positional encoding E' (L,+ on the input sequence with prompt sequence [P. Z] E Ld, so that each token of has different domain. The positional encoding E is given as
2
L + L
2
L, +-1
E
Lp +
We next use the first feed-forward layer ((T)) implement a quantization map to quantize the input [P, 2] + into its discrete version M E T. Here, we define the grid
g. = (8: 8 11d x [1 5 2d
[Lp + L 1 46:00 Lp L]d
39

---

Published as a conference paper at ICLR 2025
where [a E b| := {a. + 2e....,b b}. Note that the first column of [P, Z] + E is in [0, 1]2 the second in [1, 2] and so on. Here, we write the quantization mapping as
10, 10,1 x.... pp + L 1, Ln 1 - 16: 8: 87 x... [Lp
8: Lp L
where [a & b] = {a,a s .,, E, b}. Following (Kajitsuka and Sato, 2024), this quantization task is done by constructing the feed-forward layer as 0-approximated step function. Consider a real value piece-wise constant function ((Sup)) I + IR, for any small 0 > 0, 2 E R, we have the 0-approximation
(Lp L1016-1)
((Su)) (2) =
(ReLU (z/0 t5/0) ReLU (z/0 1 t8/8)) 8
(G.1)
z<0
5
05=<ō
L + Lp
L+ 4p - 652
which is a series of small step functions, each beginning their rise at tō and ending at + 18. Here, we show the first two terms / = 0, 1 for clarity:
2 < 0
t = 0: (ReLU (2/0) - ReLU (z/0- 5 =
20/0
0 < < 0
8
0 2
0
2 << 8
t= 1: (ReLU
- ReLU (z/0 6/0)) 8
=
zō/0 8 <
6
0 0-852
With (G.1), it is straightforward that we extend it to Rdx As result, we have the first ford-forward layer ((
(L1+1)(1/-11
(TF) (Z)
Σ
(ReLU (Ziz/0 18/0) ReLU (Zzz/0 18/0)) (G.2)
((Step) (Zis),
where E [d],j E [T, + 1J,0 < 8 < 1 and 0>> 0. With (G.2), we are able to quantize each sequence [P, 2| + E to quantized version M E Go.
Next, order to utilize Lemma 2.2, we observe that the quantized input M from the previous step has no duplicate tokens, since each column has unique domain. Also, we see that M is token-wise
(vd, vd(LL - o), vdo) -separated where L' = Lp + L. This is easily observed as we have, for any
k, I. [L, + L].
MM > Vd,
MM < vd(Lp + L 8),
| Tr.al Vd8.
As a result, with Lemma 2.2 the single self-attention layer implements a contextual mapping q: (dx((+ + bd) we arrive
(T, A) coontexxl mapping where
ddb
38
P= Vd(L' 6)
ValL'
40

---

Published as a conference paper at ICLR 2025
A cxp(-=))["ddmmm)]
Now we have successfully mapped each input sequence [P Z| + unique context ID g(M)
Rdx (T) We next associate each unique embeddings corresponding expected output of Beeqgoo ([P.-))-
We associate each unique contextual embeddings to the corresponding output of h(PP: :]) using the second feed-forward layer f/²². As in (Kajitsuka and Sato, 2024, A.5), this is achieved by constructing bump function Soump Rdx(Lp+L)) + pdx(L,+L) for each possible output from the last step i [(1/8y((ppth) Each bump function foump is realized by 3d( + L) MLP neurons. Therefore, need 3d Lp (1/8))((,,+2 MLP neurons construct the feed-forward layer ((HH) so that each contextual embedding is mapped to the expected output of heog2seg ([P, :I). A bump function Suamp for a quantized sequence A E Gs is written as:
h(P.A) d(Lpp L)
foomp (Q)
ReLU (K(QU) -A.)) 1) ReLU (KQ Al,)))
ReLU (K(Qu, A.,) + 1)],
where Q (dx((,tT)) is some context ID scalar K 0. Furthermore, recall that in (F.2), have the relation of quantization granularity ō and function approximation
Cō S
e/2. We express the number of neurons in terms of as O [d(Lp + L)(C (c) ) O (e ()) where C is the Lipschitz constant and is from the la -nomm for measuring the approximation error.
As result, by choosing the appropriate step function approximation arrive
dp (hwaazeeg -1),,pp:s7) S e/2.
This completes the proof.
Finally, we arrive at the theorem that shows that prompt tuning on some transformers with single-head single-attention layer and two feed-forward layers is universal approximator for sequence-to- sequence functions.
Theorem G.1 (Theorem 2.4 Restated), Let 1 S p < oo and > 0, there exist a transformer т E T with single self-attention layer, r Old(Ly + L)) MLP neurons and quantization granularity such that for any freyseyy E Fc there exists a prompt P e RdxL, with
da (C((P.-)..... fseq2sey) < e.
Proof of Theorem 2.4. Combining Lemma F.1 and Lemma G.2, arrive at transformer r E 1111 with prompt Gs, such that for any senneence-tosequeeee Sseqsseq E Fc.
da ((PP ((P..D). Sseuprrs)
< do DD,,, h (IP, -1)x,p)))))))))>) + da (hscogooa (LP, De... fmeq2s00)
<.
This completes the proof.
41

---

Published as a conference paper at ICLR 2025
H PROOFS OF SECTION 2.5
In this section, we show the memorization capacity of prompt tuning transformer networks with single layer self attention. We now prove that there exist transformer TB such that for any dataset S, the transformer 7 memorizes S 'troough prompt tuning.
H.1 PROOF OF THEOREM 2.5
Theorem H.1 (Theorem 2.5 Restated). Consider dataset S - {(X1), ((
f=11 where
X y(o) E [0. 1]axL, Assume the coresponding embedding sequences z ,..... 2(8) are gener- ated from C'-Lipschizz function. Then, there exists single-layer, single-head attention transformer T Th.1. with O ((I/e)d(L,+tL)) and soft-prompt P E RdxLE such that, for any E [N]:
||[(P, (T(PP220)).. 210 - Se,
where Lp 2 LA, with x = (2e C((L)/(a))
Proof Sketch. We first find some sequence-to-sequene function fimp2eg
[0, 1]dxL + [0, 1]dxt,
such that for any i [N], Sequs0s (z()) = y()) Next, we complete the proof by utilizing the results
of Theorem 2.4 to construct a transformer E T T..L." that capable of approximating fseq20oq through prompt tuning.
Proof of Theorem 2.5. From the sequence-to-sequueee function class Fo, there exist function feeqsso [0, 1]dxL + [0, 1]dx such that, feop20a (Z ( for any E [AV]
Next, since we utilize positional encoding, no information would be lost in the quantization step of Theorem 2.4. By utilizing the results of Theorem 2.4, we construct a transformer <TH. such that
T1.1r
da (T((P, fieepsoy) (/ (1IT((P,Z)).1 fimpusey (Z) dZ
Se.
As result, arrive
max iE[N] T(PP, ((P,,(00)... - Sc
42

---

Published as a conference paper at ICLR 2025
I PROOFS OF COMPUTATIONAL LIMITS OF PROMPT TUNING (SECTION 3)
We first introduce some helper definition and lemmas from fine-grained complexity theory (Alman and Song, 2023).
Definition I.1 (Approximate Attention Computation At,C(n, d, B, ea). Definition 1.2 (Alman and Song, 2023)), Let > 0 and B > O be parameters. Given three matrices Q, K, E Raxd, with the guarantees that [[Q[|max & B, |K|]mmm I B, and Imaa Σ B. (ttC d. c.) outputs matrix T Raxd which is approximately equal to Att(Q, K, = D AV, meaning,
- - D-D--AVV AV S Ca.
with A = cxp(QKT) and D = (lag(AA,)
Here, for matrix M R=xx, we write [M max,, |
Lemma L1 FFineGGrinnd Upper bound, Theorem 1.4 in (Alman and Song, 2023)), AAttC(n, d Olog n), o(vlog n)), fa 1/poly(n)) can be solved in time Tmat (n, o()) d) 1
Lemma I.2 (Fine-Grained Lower bound, see Theorem 1.3 in (Alman and Song, 2023)). Assuming
SETH, for every there constants C, Ca. Co > 0 such that: there is no O(n 2 time algorithm for the problem AAttC(n, d = C' loggn, n, B = Cov log nggn,e CC).
1.1 PROOF THEOREM 3.1
Proof of Theorem 3.1. Recall the Prompt Tuning Inference Problem APTI from Problem 1.
Problem 1 (Approximate Prompt Tuning Inference APTI(d, L, Lip 6F)). Let 8F 0 and B > Given three Qp. Kp. Vp E [dx((++1,,) with guarantees that [Qpll I B, || max S and [IVpll S B, we aim to study an approximation problem APTI(d, L, L,L. B, 8r), that approximates V, Softmax (x)) with matrix Z such that ||ž V, Softmax (KJ (p) ll Imax I 6p, where, for a matrix M E Raxb, we write || = max,, Ma,l
We rewrite
vp Softmax (K. = VD exp (p) Qp).
By transpose-invariance property of ||-llmaxe we observe ? Vp Softmax (K) max equivalent to | - D-'AVV with the following identifications between APIT and ATTC:
Sp is
(Lp + L) = n, d, B,
7 Vp V, Kp K, Op =
By 11 | < || maxi complete the proof via simple reduction from fine-grained upper bound result Lemma I.1.
I.2 PROOF OF THEOREM 3.2
Proof of Theorem 3.2. Using the same identifications as in the proof Theorem 3.1, we complete the proof with Lemma I.2.
43

---

Published as a conference paper at ICLR 2025
J LIMITATIONS OF PROMPT TUNING TRANSFORMERS
In Section 2, we demonstrate that through prompt tuning, even a transformer with the simplest architecture can serve as universal approximator. However, to achieve this, it is necessary to construct specific transformer tailored for the task. In this section, we explore how prompts influence the output of pretrained transformer model. Additionally, we investigate the boundaries of prompt tuning on arbitrary pretrained transformer model by analyzing its underlying mechanisms.
J.1 DISCUSSION ON THE LIMITATIONS OF PROMPT TUNING
For simplicity, consider a single-layer transformer function class with head of size and r MLP hidden neurons:
To == =- :RRxL + 1T = ((tb) (s(SA)
The tokenwise output of the transformer with input [P, X] Rdx((pp is
T ((P, = f(FF) (f(An) (I,, XI) + [P.
where [P. ] the concatenation of a prompt E gd and data X RdxL By taking the
inverse of cer-fforarrd function f ( 1); Rd + Rd, we have
f(Au) (x, [P, E (H (v) x,
(J.1)
where x = x and is the corresponding label token for æ.
Next, to better understand how the prompt P affect the output of the transformer, focus on the output token of the attention layer corresponding to some data token x X
f(Au) (z, XI)
(J.2)
Wo (Wv (Wv|P,X) (P) Softmax
(W<IP,XI)* (Wx(P:))T((Qq)))
exp (Wx((P (Woz)
[Wx (P,X), T (Wor)
exp
(WoWW/PP.
L+ exp
(WxIP.X].)) (WQz)
E Wo (WvlP, ().i)) exp
(Wx X).s) T (Wox)
Ih exp
(WxIP, T (Wor)
Ly exp
(WKP.)) (Wox)
f(AN) P)
Σm exp (W)X,,)) T. (Woz) flau) (I,
Ej exp (P,(P,)).s)) (Woz)
Ej exp (Wk[P, X).)) (Wor)
(P,x) ((An) (Ir, P)
V (X,x)
p(An) (x, X),
(P, x.)
V (P. x)
where (-...))) is positive scalar and defined as
v/ (A, Eexp exp (
44

---

Published as a conference paper at ICLR 2025
Combining (J.1) and (J.2), we have
V (P,2) ([P,X],00
((Au) (2,
V/ (X,x) ((P,XI,xx)
p(Au) (x) p(rF)-1 (v) - (I.3)
Essentially, with all parameters for the beed-forward and self-attention layers fixed, prompt tun- ing finds the prompt P such that (J.3) holds for each input-label pair (x, y). In (J.3), note that while -(),,,)) are positive scalars, the attention terms f(Am)() are vectors. The initial term ((.zz) (Aa)) (ar, P) depends entirely
P, highlighting the strong effect of prompt tuning on shaping the model's ' outputs by guiding the attention mechanism. In contrast, P's influence on the vixX,,) / ((Ar) (x, X) is limited to scaling, preserving the original attention pattern between x and X. Thus, prompt tuning biases the attention function's output but does not alter the intrinsic attention pattern between æ and X.
second term V[P...]..)
This manipulation highlights prompt tuning's 's ability to subtly refine and leverage the pretrained model's 's knowledge without disrupting its core attention dynamics. However, it constrains prompt tuning's 's expressiveness, Thus, prompt tuning is limited to realigning latent knowledge within the model, failing to learn new knowledge, which would require altering the model's core attention dynamics.
cannot change the direction of the attention output vector f(Al) (xx X).
In Section 2.5, we discuss the cases where prompt tuning is able to memorize some general data set. Here, on the other hand, we also provide an example where prompt tuning on some general transformers fails to memorize some simple data set.
J.2 EXAMPLES OF PROMPT TUNING FAILURES
The memorization ability in Theorem 2.5 is based on some specific transformers we carefully constructed for the memorization task. However, as we discussed in Appendix J, there exists limitations for prompt tuning on when learning new knowledge. Here, we provide an example where prompt tuning some arbitrary transformers fails to memorize. We first introduce some assumptions on the relation between our transformer and dataset.
Assumption J.1. We assume that all output tokens (Y()), ..& are in the range set of (HH), We assume that Wq. WK. Wv, Wo are full rank matrices and that ((SA) (x(+) are distinct for i 1,2, .....
Now, we show that transformers through prompt tuning fails memorize some simple data
Corollary J.0.1 (Prompt Tuning Fails to Memorize, Theorem 2 of (Wang et al., 2023a)). For any pretrained single layer transformer т T, there exist sequence-to-seve se-eueece dataset (1)
( xx] we cannot find a prompt P E RdxLL, with any Lp 0 such that ([P, xx.) yı holds for any i = 1,2. The vectors zo, 21, 22 are denoted post positional encodings.
S = (x 2
x+ ( = (D() 1/2 ( (x
( [u(2) y/²² and
Remark J.1. The most important aspect of this dataset is the shared token x² As shown in Appendix J.1, to learn the first example (X(), y()), we are able to find prompt P. such that
V (P,x') V (IP, ((P) ((A)) (x", P)
V/ (x(1))) xx*)
p(Am) (ar, / (at,x.1)) E (((F))1
(1)
+ V (IP, x()] x*))
U/2
x²
However, now the vector f(Au) (x+, P) is fixed as prompt P has been chosen. This prevents us from finding a prompt to cater to the second example, which is written as
V (P,x*) ([,,X() x+)
V (x(2),x²* ((Au) (x" P) V (IP, xt) flau) (at (2t,,(12)) ((FF)-1 ( (2)
y/2
x².
Thus, the expressive power of prompt tuning is limited.
45

---

Published as a conference paper at ICLR 2025
K
SUPPLEMENTARY PROOFS FOR APPENDIX D
Here we restate some proofs of the properties of Boltzmann operator from (Kajitsuka and Sato, 2024) for completeness.
K.1
LEMMA D.1
Proof of Lemma D.I. By taking in Pt defined in Definition D.I, see
Inp; In Σ e
In (z).
(K.1)
Also, by the definition of Boltz, we have
Boltz(z) =
Σ zpps
Σ Pi In (p, Z())
(By (K.1))
Σ
In Σ
piln In 2(z)
==
==1
S(p) + In ((2).
This completes the proof.
K.2
LEMMA D.2
Proof of Lemma D.2. We restate the proof from (Kajitsuka and Sato, 2024) for completeness.
We first observe that
2
e
0zj"
Pi
Ōzj
k=1 e*
(K.2)
8zze²1
k= (*k Clie
2km1 E=x) 2
dizez
E
2k=1 E
E )²
= Py (Bis - -Pi),
where 6ig the delta function, i.e., 5.g = only when = j.
Next have
Boltz(2) =
Σ pjpj
0z,
Oz,
Ozj
Op
Pj +
Zj
dz
Ozi
P: +
2jPr (5.z Pj)
(By (K.2))
j=1
p: (1 2 Boltz (=))
(By (D.1)
p:
+ z S(p) In 2()))
(By Lemma D.1)
46

---

Published as a conference paper at ICLR 2025
Since Ps 0, only need to focus the second term
+ 2, + S(p) In 2() 0.
This means
2 In 22) -
By using maxje(n] 2, S In (2) (Boyd and Vandenberghe, 2004, p. 72) and S(p) I In n, we have that, when
44 < In E(z) S(p) 1,
satisfied, the Boltzmann operator Boltz(z) monotonically decreases in the direction of 2,
K.3
LEMMA D.3
Proof of Lemma D.3. We restate the proof from (Kajitsuka and Sato, 2024) for completeness.
Observe that
(S(p)
Σ
Py
In Pj
(K.3)
dz,
j=l
a
Opi
0
Σ
Pj + PJ Zzi
In
0zi
5=1
Σ j=1
Ps (6.z Pj) In + Ps (6.z Pÿ)
(By (K.2))
Σ 1=1
b6 (Inp) + 1) - P, Imp, -Psl
(Inp, + S(p)
(By 8, 1,8(p) E In p.. Eps Ps 1)
= P: (In + S(p)).
Now, we prove the concavity by taking the derivative once again from Lemma D.2, which is
0²
θ Ds (1 Inp, + S(p))
Bolta(z)
(By Lemma D.2)
0z,
ap:
I1+Imp + S(p)) +
(1 In + S(p))
Oz,
0z,
pi (1 - pt)
P. (1 p.) Inp, S(p)) + p;
Ps (Inp, + S(p))
P;
(By (K.2) and (K.3))
[[1 2p:) (Inp, S(p) + +] = P. [[1 2p:) (z - hn (2)) + S(p) + 1) +1]
(By (K.I)
Since Pa 0, analyze the second term. Consider pa //2 we have
-1
2; - In 2(=) +1 < 1 2p;
47

---

Published as a conference paper at ICLR 2025
By using maXje[o] 2 In (2) (Boyd and Vandenberghe, 2004, p. 72) and S(p) I In have
-2 + 2p:
24
max JE(n]
In n + - 2p;
Since -2+2p: is unbounded below in domain 1-2p:
1/B Ps 0, focus discussing cases where
P. > 0. We now have
-2 -2 2p:
-2 >
< -3
1 2p;
As result, the Boltzmann operator Boltz(z) is concave with respect to for any
#/ max 2j In 3. 5E(m]
This completes the proof.
K.4 LEMMA D.4
Proof of Lemma D.4. From Lemma D.2, know that Boltz(z) monotonically decreases in the direction of 2; when 2, < 21 n 1. Since z is tokenwise (o)-separated and has no duplicate entry, given 21, the minimum of Boltz(=) happens 2" (21, 21 26. ..., 21 - (n - 1)6)
where > Inn + 1. By Lemma D.2, we see that
Boltz(2) > Boltz(z") > Boltz(z').
K.5
LEMMA D.5
Proof of Lemma D.5. For any 2', we find some 2" E IR",, where
(#f -00)
By Lemma D.2, we have
Boltz(=*) > Boltz(z').
In addition, for any n, we able to find some 2n with last (m n) entries being (-oo). As result, we have
Boltz(2) = Boltz(2*)) > Boltz(2').
K.6
LEMMA D.6
Proof of Lemma D.6. We restate the proof from (Kajitsuka and Sato, 2024) for completeness.
Let a' E R.. be
a' = (a), di - 6).
(K.4)
From Lemma D.4, we know that Boltz(a) > Boltz(a'). In addition, we have:
Boltz(a')
48

---

i Published as a conference paper at ICLR 2025
12
eat
Σ
0
2==1 e0g
i=1
a
+ (n - 1) (a] 8) c
(By (K.4)
Ea + (n 1) 1)
a1 + (n - 1) (01 8)
+ (n 1)
(n 1)de
01 14 (n 1)e
Also, we know that Boltz(b) b1 since entries of sorted decreasing order. Therefore,
Boltz(a) - Boltz(6)
2 Boltz(a') - bi
(n - 1)ōe-
> 01
(a1 - 6) 1 + (n 1)e-
(By bi ai -ō)
(n 1)ōe 5
8
1 (n 1) 1)6-6
8
(By -212+3
1+ (n 1)e-
2 Inn.
Note that Inn > (Inn)2e-(am) (ar bi)), because ai -b b1 > Inn implies Inn (ar--bbi) < 1.
K.7
LEMMA D.7
Proof of Lemma D.7. We restate the proof from (Kajitsuka and Sato, 2024) for completeness. With the concavity given in Lemma D.3 and first-order Taylor approximation, we have
Boltz (b), 1, + (an t) ot
Boltz (b1,..., > Boltz (bi...., 1 an),
for an.
Then, by setting = bn. we obtain
Boltz (bI,... 1n - Boltz (b.....,b,,, an)
Boltz(b) Boltz(a)
i Boltz "1y....bb-11
(an bm)
t
(an
bm) -Pn (1 + In + S(())
(By Lemma D.2)
(an
bm))
Pn 1 + bn mmxx b; + In iE|u]
(an
bm) Pu
(ō + an
- bn - -Inn- 1)
bn
(an bm)
(5 + an - bn -nnn 1).
E bb
This completes the proof.
49

---

Published as a conference paper at ICLR 2025
K.8
LEMMA D.8
Proof of Lemma D.8. We restate the proof from (Kajitsuka and Sato, 2024) for completeness.
Let
Oup (a1, 02 ..2..... ... ONe ak+1) E IR++1
bno = (01, ..,,... 0A b b bk+1) E IR..
Then, Lemma D.2 implies that
Boltz(a) < Boltz(Lup); boltz(b) Boltz(bbo)
Thus we only have to bound Boltz(bo) Boltz((aa).
Let
k
=
Σ
a
and & = Σ
e
1=1
1=1
Next, decompose Boltz(bra):
Boltz(boo) = 7k + (n - k) b
Ev + (n b)ebe+1
Th + bu +
&o cbu (0b
Ykk (bk+1 + In(n k)) (0
In(n R:) (bx42+)m(x-8) Ea + +lal--))(
Ex + ebati tuunn k))
In(n k) (bemrtlu(n-b)
ak Boltz (k, bk+1 + In(n k))
&a + ch (n((n)))
Therefore, we have
Boltz(bbo) Boltz(aup)
(K.5)
In(n - k) be
Boltz (a),..., age butt + In(n k)) - Boltz(amp)
Ea +be4r+
Note that by Lemma D.7, we also have
boltz (a1..... ag b + In(n k)) (oltz(Oup)
(K.6)
(ax+1 bktt - In(n (() k)) (5 + ax+1 bet1 In(nn (((n-k)] k) -In(k + 1) 11)
& + Ebeeitthing cle4++
> (6 12n) 21n 1)
(By 8-separatedness)
Ea + clu-itla(n-R)
(n(=+)((n-))
Ex + eb2t +l(x-k)) 4nn2(n)
(By assumption > >11n))
Now plug (K.6) into (K.5) to obtain
Boltz(br.) Boltz((ap)
50

---

Published as a conference paper at ICLR 2025
In(n - k) che ++n((n=))
Boltz (Q1,.... ak. bb+1 + In(n - k)) Boltz((up)
&
((trth((n-k)
(4 (n) In(n k))
EA + eh (ithnaa()))) (hIrstm((=-))
E + tlesi+ln(nnk) (n).
Also, for the denominator, we have
k+1
Ek + blus--u((-k)
(By ax41 > bu-1 In(n k))
k+1
c
1)8
(By < 01 (1 1)6)
1=1
2ea1!
(By > lm2)
Therefore, we arrive at
e cb(11tn(nn-R
Boltx(b) (ollz((up)
Ek + cbe+ith((n-k) n)I
e (n++++(((-k))
2e
(Iun)² (aan))-(arraa (ar-t)11))
This implies that
-(ss- Bolta(b) - Boltz(a) > (In ( bb4+))
This completes the proof.
K.9
LEMMA D.9
Proof of Lemma D.9. We restate the proof from (Kajitsuka and Sato, 2024) for completeness.
First, we observe that Boltz is permutation invariant by definition. In addition, there are no duplicate entries each vector 2;. Therefore, w.l.o.g. we write the vectors in entrywise decreasing order (i) zn for any E [N]. We prove (D.3) by utilizing the first constraint of (7, d') ottkeeene separateness of 2(), which is
(1)
< %
for any i E [N] and E [n]. Since 2n (4) Boltz(2(1)) < (0) we have
(0l max ()210) 12200)/16001 7.
Next, prove the 8' o'-separateness. Consider i [N] and E [m], w.l.o.g. assume that there exists E (O...., 1} such that
(2
(1)
(1) (2()))
.2. ( and ac+1 b
51

---

Published as a conference paper at ICLR 2025
Then, by combining Lemma D.8 and Lemma D.6, we have
[Boltz((()) Boltz(2(0)
(Inn)ee - -(f- -+41)= #+11
( 27.
(ar b641 < 2r since (7, 6) -eparated)
This completes the proof.
K.10
LEMMA E
Proof of Lemma E.I. We restate the proof from (Park et al., 2021) for completeness.
unit vector. Next, we prove the first inequality. We focus on the cases where | N 2 and 2 2. We first prove that for any vector R4, unit vector Rd uniformly randomly drawn from the hypersphere g satisfies
We first note that the second inequality simple because
|el| N
Pr
uu
(K.7)
md
N
With (K.7), we define V = for - x' xx E X}.
Then, the union bound implies
Pr
ul
|||||
8
Σ Pr
[
u|
||a||
8
N2
dd
N2
xdz
Wev
AE
N(N
2
1,
2
N
and thus there exists at least one unit vector u that satisfies the lower bound. We start the prove with
8
Pr
N2
Pr
|u1
2
8
2r
0
<
(By symmetry of the uniform distribution)
2
Td
2
Area (gd-2). (sin( d-)
Area (Sd-1)
100-11
NZ mm
Area (Sd-2)
=
(sin()))d-2dd)
Area (Sd
cos (Na Vi
2
(d r ($ +1)
(sin (sin()))d-2dó
-
dl ( +1)
cos-1
2
(d 1) dd +
1do
(By Gautschi inequality and sin(m) S
π
( -
2d
1dp
(Since d 1)
π
0os
NZ
52

---

Published as a conference paper at ICLR 2025
2d
π
π
2
COS
N2
x
2d
8
sin
π
N2
R
2d
8
π
2
N2
Rd
2
( s 5sin
(0) 7)
N2
This completes the proof.
53


Reviews:
[{"review_id": "iEE4kS2Mne", "reviewer": "Reviewer_CLcT", "summary": "The paper investigates the limits of prompt tuning in transformer-based models by focusing on the simplest architectures with a single self-attention layer and head. The authors prove that such simple transformers can universally approximate any Lipschitz continuous sequence-to-sequence function through prompt tuning. They also demonstrate that these transformers can memorize any dataset via prompt tuning by establishing an exponential lower bound on the required number of soft-prompt tokens based on data dimension, sequence length, and desired error tolerance. Additionally, they identify a computational efficiency phase transition determined by the norms of the soft-prompt-induced keys and queries. They establish an efficiency threshold beyond which no sub-quadratic algorithm exists under the SETH, but within this threshold, they prove the existence of almost linear-time inference algorithms for prompt tuning.", "questions": "1. The paper \"Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?\" stated that they easily extended their analysis of contextual mapping to masked self-attention, which is what's actually used in practice. Since such an extension might be beneficial for completeness, could the authors elaborate on why they haven't addressed it? Was it more challenging in this case?\n\n2. The identified efficiency criterion (Theorem 3.1) requires controlling the norms of the soft-prompt-induced keys and queries to be $O(\\log(L_p + L))$. In practical applications, particularly with large-scale models and datasets, how feasible is it to meet this criterion?\n\n**Minor Remarks**\n\n1. In order to make them multiplication-compatible, $W_O^i$ should be $d \\times s$, and this doesn’t propagate to later sections.\n\n2. The infinity norm is already defined in matrices, which gives the maximum row sum, and perhaps a better notation would be $||M||_{max}$ for clarity.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The paper advances the theory of prompt tuning by proving that even the simplest transformer architectures—with a single attention head and a single self-attention layer—can universally approximate any Lipschitz continuous sequence-to-sequence function.\n \n2. The paper notably discovers a phase transition in computational efficiency based on the norms of the soft-prompt-induced keys and queries. It provides a criterion under which prompt tuning can be performed in sub-quadratic time and demonstrates the existence of almost linear time algorithms under certain conditions.\n\n3. The paper introduces new applications, such as the chained reduction of piece-wise constant approximations, to prove universality results. It also extends the contextual mapping property to any-rank weight matrices in single-layer attention mechanisms, improving the rank-1 limitation of previous work.", "weaknesses": "1. The paper contains numerous grammatical errors, and some sentences are poorly constructed. A thorough proofreading is required to enhance the readability of the text.\n\n2. While the paper brings new applications of previous concepts to function approximation, the technical novelty appears limited, with many proofs in Section 2 overlapping significantly with those used in \"Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?\" and Universality and Limitations of Prompt Tuning\" papers.\n\n3. The paper does not include experiments to showcase any of the theoretical results. The authors could demonstrate the approximation capabilities of single-head, single-layer transformers for sequence-to-sequence functions in Section 2. The authors can even use synthetic datasets designed to have known Lipschitz properties. Deeper transformers with more heads and layers might be used for comparison.\n \n4. Another empirical comparison might be examining the relationship between the number of soft-prompt tokens and the model's ability to memorize datasets, as suggested by the exponential lower bound. Again, one might utilize synthetic datasets where the complexity (e.g., vocabulary size, sequence length) can be controlled.\n\n5. I think the authors should perhaps discuss and more on the results and analysis of the “Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?” and compare the results as they prove that transformers with one self-attention layer are universal approximators for permutation equivariant continuous functions. Also, explaining how the results in the current paper relate to or differ from theirs might provide insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2T6v8JVFvS", "reviewer": "Reviewer_BCYB", "summary": "This paper studies the fundamental limits of prompt tuning and derives several interesting theoretical properties on single-head transformers with a single self-attention layer. The authors 1) show that prompt tuning can universally approximate any sequence-to-sequence function, subject to some continuity assumptions,  2) show that prompt tuning can memorize arbitrary datasets and 3) prove the existence of almost-linear time prompt tuning algorithms, which builds the theoretical foundation on the computational time required for prompt tuning.", "questions": "Please refer to \"Weaknesses\" above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, given the theoretical nature of the paper, it is a dense read by design, but the good presentation has helped a lot by clearly outlining the different contributions (e.g., universality results, memorization properties and the computational time analysis). The paper is quite solid in terms of the theoretical contributions. The contributions are outlined cleanly and the flow is great. The theoretical results also represent a significant contribution over existing works, such as [1].\n\nReferences\n\n[1] Yihan Wang, Jatin Chauhan, Wei Wang, and Cho-Jui Hsieh. Universality and limitations of prompt tuning. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023a.", "weaknesses": "To begin with my feedback, I'd like to mention that while I have a grasp about the high-level ideas and contributions of the paper, I have not checked the math and derivations in detail although they seem reasonable; I am not an expert in this area, so I might not have sufficient knowledge in judging the merits and significance of the work w.r.t. the previous works, so I defer the assessment of these parts to other reviewers and the AC. \n\nI understand the paper outlines many \"there exists\" type of results which cannot be verified easily with practical algorithms, however, I do think the authors could give add some discussions on in what circumstances their theoretical results could lead to practical implications, especially given that prompt tuning itself is a very *practical* low-cost adaptation technique, so for the results to be relevant and of interest beyond the theoretical community, some kind of discussions about practical impact are essential. There also seems to be some contradictions given the paper suggests that even a shallow, single-head transformer is already universal yet there is some empirical evidence that prompt tuning is more effective with deeper transformers -- while I understand some gap between theory and practice can be acceptable especially given that many theoretical properties of prompt tuning are not well-known thus far, I wonder whether the authors could give any comments on why that is the case? Is it possible that there are unrealistic assumptions in the theoretical analysis?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xK3TVKfkjT", "reviewer": "Reviewer_VLhX", "summary": "This paper studies the theoretical properties of 1-layer 1-head transformers in terms of their approximation power and also the existence of efficient algorithms to approximate arbitrary 1-layer 1-head transformers with weights of bounded norms. There are 3 main theoretical results in the paper. The first result (theorem 2.1) shows that a single self-attention layer with sufficiently large number of MLP layers can approximate any Lipschitz function that maps one sequence of real-value vectors to another sequence of real-valued vectors. The second result (theorem 2.3) shows that a 1-layer 1-head transformers with sufficiently wide 2-layer MLPs can memorize any dataset generated by Lipschitz functions with prompt tuning with sufficiently long prompt. Finally, the third result (Theorem 3.1) shows that the Prompt Tuning Inference problem can be approximated efficiently in nearly linear time (in terms of the sequence length) through a reduction to a previously known result (AttC).", "questions": "> We study the fundamental limits of prompt tuning transformer-based pre-trained models (i.e., foundation models) in two aspects\n\nWhere does the pretraining affect this analysis? As far as I can tell, the paper only considers the representational power of the transformer. Why does it matter if the transformer is pre-trained or not? If pretraining matters in the analysis, I would expect to see some assumptions about the representation from pretraining but I am not sure if there is any.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is technically strong. It provides several improvements over previous results on the topic.\nWhile I did not verify every single proof, the overall argument seems sound and the conclusion plausible.\nThe paper is fairly well-written for such a technically involved paper, and I believe the results in this paper will be useful for future work studying the approximation properties of transformers.", "weaknesses": "Overall, while the paper is technically solid, I have a hard time seeing it being impactful for communities beyond those studying the representational power of transformers. \n\nI consider myself to be reasonably well-informed about the development of deep learning theory. These kinds of approximation results are certainly nice to know, but they rarely make any impact in practice or even inform any algorithmic design. For example, the authors claim that:\n\n> These fundamental limits provide important necessary conditions for designing expressive and efficient prompt tuning methods for practitioners.\n\nI do not see how these results will have any impact on how we do prompt tuning right now. What does it tell us that we do not already know? If there are, I would like to see them discussed in more detail in the paper. For example, does this result says about why prompt tuning fails in certain scenarios?\n\nI would also like to see related work in the main body of the paper and a more detailed discussion of how this result relates to prior works. The page limit has been raised to 10 so there is no reason to leave them in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Wr5E9xRRWa", "reviewer": "Reviewer_8DjM", "summary": "This paper considers the approximation power of the transformer architecture. The authors prove that single-head, single-layer attention is a uniform approximator of a certain class of Lipschitz functions over the space of sequences of tokens. The authors also provide results regarding the ability of transformers to memorize a dataset, where they improve on previous results regarding the number of fully connected layers needed to memorize. Finally, they provide a complexity-theory style result regarding the efficiency of prompt tuning. Their result indicates that prompt tuning is possible in nearly linear time under several assumptions.", "questions": "See above", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The paper is well-written, other from a few minor typos. There is clear effort to clearly lay out the problems and their solutions, including statements of intermediate lemmas.\n* The problem clearly addresses an important problem. It's worth knowing the approximation power of the transformer architecture, given its widespread use. \n* The results also improve on the previous work of (Wang et al., 2023) in a non-trivial way.", "weaknesses": "**Organization and presentation.**\n* In general, it's inarguable that this is not an easy paper to read. This is the nature of universal approximation style papers; the technical assumptions needed for this work can be daunting. However, there are a few things that I think the authors could do to make this paper appealing to more \"casual\" readers.\n    * Rather than trying to state the theorems in full detail, opt for informal statements, with the rigorous version deferred to the appendix. This would likely lighten the load in the main text.\n    * No matter how tempting, do not use \\vspace{} with a negative argument. The paper is hard enough to read as is; decreasing the skips between lines does not help this whatsoever.\n    * Try, whenever possible, to include equations on their own lines. There too many long-ish equations displayed in-line in this paper. As a result, I had a hard time reading this paper; I expect others will feel similarly.\n* The paper could also benefit from slightly more thoughtfulness around the notation used.\n    * Define notation **before** it is used. The authors use a lot of notation in the introduction that is defined in the next section. \n    * Similarly, there is confusion about the indexing variable $p$. My understanding is that this variable is used both as an indexing variable for token sequences of length or index $p$, and as the norm-type (e.g., for norms on an $L^p$ functional space). Using separate variables would improve readability.\n    * Using (capital) $Z$ and (lower-case) $s$ to denote the hidden dimension is confusing. Perhaps it would be better to stick to either capital or lower-case letters when they play the same role.\n   * This may just be a typo, but in Problem 2, $d_p$ takes three arguments the first time it's used, but it is defined later on (in the next sentence) as having only two arguments. I think perhaps there is a missing underscore before the $L_p$, so it ends up being $\\tau([P,\\cdot])_{:,L_p}$.\n    * The word vocabulary is a bit overloaded. It generally is used to mean the codomain of the tokenizer. But here it's more like the set of columns of the datasets $Z^(i)$. It would be worth disambiguating this.\n\n**Assumptions.**\n* This paper would benefit from expanding on why each of its assumptions is reasonable. This is lacking throughout the paper. One could argue that this doesn't matter for universal approximation results. And yet, the fact remains that these results would be stronger and more useful if the authors made clear whether the assumptions hold in cases closer to real-world problems.  Some further comments:\n    * Is the class of seq2seq Lipschitz functions a reasonable class of functions to consider? The definition under Def. 2.3 indicates that the functions are Lipschitz over the space of tokens unless I've misunderstood something. But why should we expect the space of tokens to admit local structure that makes Lipschitz meaningful? In general, tokens in the Euclidean neighborhood of other tokens may not share any semantic similarity. It makes me wonder whether there might be a better class of functions for a universality result.\n    * I have a similar concern about the token separation assumption in Def. 2.5. This seems a bit unreasonable given the possibility that the dataset may contain repeated queries. It would be worth explaining how reliant the theory is on these results.\n\n**Miscellaneous.**\n* The section on computational limits (Section 3) felt relatively rushed to me. It wasn't clear why this problem is related to $k$-SAT, or what the reduction is that powered Theorem 3.2. The original limit was 10 pages, so perhaps the additional page of content could be used to expand on this part.\n* The line at the end that says \"By the formal nature of this work, our results do not lead to practical implementations. However, we anticipate that our findings will offer valuable insights to future prompt tuning methods\" was disappointing. Not only is there no attempt to ground these ideas in real world settings, but the statement regarding the impact of this work is, in a word, vague. Is there not more that the authors can say here? This is an opportunity to say why you think that this research is impactful. And if you don't think that this paper will be impactful, it's worth asking why it was carried out in the first place. Of course, no one is expecting a paper on uniform approximation to be immediately applicable to modern LLMs. However, it would be worth speculating for at least a paragraph about why you think these results will be helpful moving forward, i.e., what kinds of \"valuable insights\" do you think this work will yield?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)