Prompt Tuning Transformers for Data Memorization
Authors: Haiyu Wang
Yuanyuan Lin
Venue: NeurIPS 2025 poster ()
Keywords: Transformers
Data Memorization
Prompt Tuning
Primary area: deep_learning
TL;DR: We study the data memorization ability of Transformers with prompts

Abstract: Prompt tuning has emerged as a powerful parameter-efficient fine-tuning technique, allowing large pretrained Transformers to adapt to downstream tasks by optimizing a small set of prompt embeddings. Despite its empirical success, the extent to which prompt tuning can memorize data remains poorly understood. In this paper, we provide both theoretical and empirical analyses of data memorization ability of prompt-tuned Transformers. Building on recent theoretical frameworks, we derive an upper bound on the required prompt length for exact memorization of finite datasets and establish a trade-off between prompt length and the number of autoregressive generation steps. Specifically, we show that a constant-size Transformer can memorize $n$ input-output pairs with prompts of length $\tilde{O}(\sqrt{nN})$, where $N$ denotes the sequence length. Empirical results further demonstrate that prompt-tuned, randomly initialized Transformers are able to effectively memorize finite datasets. These models also capture the intrinsic low-rank structure of the data, leading to a reduction in the required prompt length. Finally, we analyze how the initialization of the Transformer backbone affects the performance of prompt tuning. Our findings provide new insights into the expressivity, efficiency, and underlying mechanisms of prompt tuning, bridging theoretical memorization limits with observed empirical behaviors.

Prompt Tuning Transformers for Data Memorization
Haiyu Wang
Yuanyuan Lin"
Department of Statistics and Data Science The Chinese University of Hong Kong Hai Hai ink. cuhk. edu
Department of Statistics and Data Science The Chinese University of Hong Kong ylin@sta. cuhk, edu.
Abstract
Prompt tuning has emerged as powerful parameter-efficient fine-tuning technique, allowing large pretrained Transformers to adapt to downstream tasks by optimizing small set of prompt embeddings. Despite its empirical success, the extent to which prompt tuning can memorize data remains poorly understood. In this paper, provide both theoretical and empirical analyses data memorization ability of prompt-tuned Transformers. Building on recent theoretical frameworks, for exact memorization of finite datasets and establish a trade-off between prompt length and the number of autoregressive generation steps. Specifically, that a constant-size Transformer can memorize n input-output pairs with prompts length Ö(vnN), where N denotes the sequence length. Empirical results further demonstrate that prompt-tuned, randomly initialized Transformers are able to effectively memorize finite datasets. These models also capture the intrinsic low-rank structure of the data, leading reduction the required prompt length. Finally, we analyze how the initialization of the Transformer backbone affects the performance of prompt tuning. Our findings provide new insights into the expressivity, efficiency, and underlying mechanisms of prompt tuning, bridging theoretical memorization limits with observed empirical behaviors.
derive upper bound the required prompt length
show
Introduction
Large pre-trained Transformer models have become the cornerstone of modern artificial intelligence, exhibiting remarkable capabilities language understanding, reasoning, and transfer learning
[Devim al
2019, Dosovitskry et alj, 2020 Jumper et all 21211 Raffel et all 2020 Iu cf all
20216 Ramesh
2021 Tay et alj, 2022. Sabaraa et all, 2022 Villegas et all 2022, Peebles and
Xie 0023, Han et all 2022 Hadi et all 2023, Naveed et all 2023, ef all 2025). To make such
massive models more adaptable downstream applications, parameter-efficint fine-tuning (PEFT) techniques have been proposed as practical alternatives to full fine-tuning substantially reducing the number of trainable parameters while preserving competitive performance eHu 2022 Liu all
202A
Lester ctal 202T]] Among these approaches, prompt tuning stands out for its simplicity and generality: it freezes the pretrained backbone while learning only a small set of task-specific prompt embeddings, enabling lightweight yet effective adaptation across diverse domains [Zhou et all 2022
Ge al 2023. [ha et all 2122
Fang CI all 20223]]
Memorization or generalization? Despite their impressive empirical success, large language models have reignited long-standing debate: do they genuinely generalize unseen inputs, or do they predominantly memorize patterns and examples from pretraining finetuning corpora? Empirical evidence indicates that LLMs often exhibit a blurred boundary between memorization and generalization -aterliitatiiommmmmmiiiinnn factual or low-complexity patterns while generalizing in reasoning- intensive or compositional tasks [Wang el al, 2022 Harimann all, 2I2K"). This duality challenges
"Corresponding Author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

our conventional understanding of what it means for a neural network to understand data, raising fundamental questions about the nature of knowledge stored within LLMs. Intuitively, parameter- efficient fine-tuning methods, which updates only a limited number of parameters within otherwise fixed architectures, are expected to possess weaker memorization capacity than fully fine-tuned models. With most of the representational power locked in the frozen backbone, such methods may struggle to encode task-specific information solely through prompt embeddings. This observation naturally leads to fundamental question: to what extent can prompt tuning memorize data when the underlying Transformer remains fixed?
Expressivity or vulnerability? Recent studies have suggested that data memorization should merely be interpreted as byproduct of training, but rather as a quantitative indicator of a model's 's expressive ability. Allen-Zhu and [2024]] observed that fully trained Transformers can encode roughly two bits of input information per parameter, while theoretical analyses further link this memorization ability to the model's functional richness and representational power [Kimi et all 2022, Mahdavi all 2023, Kajitsuka and Sato, (0244). However, the same ability to store detailed information internally also introduces potential vulnerabilities: memorized data can be extracted via carefully crafted or learned prompts, risking the exposure sensitive or proprietary information contained in the training corpus [Carlini et all 2022, Ozdayi all 2023]. Therefore, understanding the mechanisms and implications of memorization is crucial not only for characterizing the expressive power of large language models, but also for assessing the privacy risks they inherently pose.
Motivated by these considerations regarding the practical significance of data memorization, and inspired by recent theoretical advances [Wang all, 2023) Petrro et all, 2023, ef all 2024, Petroy all 2024, Nakada et all 2025), we investigate the expressive ability of prompt tuning in memorizing finite datasets with zero error. Moreover, to disentangle the architectural expressivity of the Transformers from the effects of pretraining, we investigate prompt tuning applied to randomly initialized Transformers. This setting allows us to examine whether prompt embeddings alone can enable memorization when the backbone model provides no task-specific prior knowledge. Our main contributions are summarized as follows:
Main Contributions Our main contributions are summarized follows:
Building upon the recent thcoretical framework in [Nakada et all 2025], which demonstrated that prompt tuning Transformer can exactly impiement ReLU feed- forward neural network, we derive the first upper bound on required the prompt length memorize finite datasets. Specifically, prove that prompt tuning constant-size Transformer with the prompt length of Ö(vnN) can memorize input sequences of length N.
We further establish a theoretical trade-off between the prompt length and number of the intermediate steps during autoregressive generation. When N 1, we show that prompts of length (n) with Ó(1) intermediate steps can memorize input-output pairs, while the same memorization capacity can be achieved with shorter prompts of length Ö(vr) if Ö(vn) intermediate steps allowed.
Our experiments demonstrate that prompt-tuned, randomly initialized Transformers can effectively memorize finite datasets, especially when the word embeddings exhibit structural regularity. Moreover, these models are able to capture the intrinsic low-rank structure of the data, which in turn enables a reduction the required prompt length. Finally, we analyze how the initialization of the Transformer backbone influences the overall performance of prompt tuning.
1.1 Related Works
Theoretical Understanding of Data Memorization One of the fundamental study on the expressive capacity of Transformers is see whether Transformers can achieve zero loss on finite input-label pairs, which is named the data memorization ability. Kum et all [2022] is the first work to study the data memorization ability of Transformers. They proved that Transformers with Ö(d + n + VnN) parameters are able to memorize N sequences of d-dimensional tokens with length Mahdavi el all [002]] showed that multi-head self-attention mechanism with H heads

---

and O parameters is capable of memorizing O(H)) data samples. Recently, Kajitsuka and Sata [0045 proved that Transformers with only one single-head self-attention layer possess data memorization ability. However, the required parameters in their work have to be Odd + d²). Chen and Zou [2024] built the results of Transformers with ReI.U activation function in the self- attention layers under the assumption each data label is distinct. Kajitukaa and Sate [20ZE]] made an effort to derive the optimal number of parameters needed to memorize given data points. was shown that Transformers with Ö(vN) parameters can memorize N imput sequences of length n in the next-token prediction task and OVvnN) parameters in the next-token prediction setting. They further proved that Ö(vN parameters in the next-token prediction is optimal up to logarithmic factors. Dana et [2022] proved that one-layer attentiononnl Transformer with H heads each of dimension d,, can memorize Hd,," - d associations.
Theoretical Understanding of Prompt Tuning Proposed by Lesterctaal 2021], prompt tuning has emerged as a promising parameter-efficient fine-tuning approach. Waan el al [202%] analyzed prompt tuning from the lens of universal approximation ability and limitations with knite-depth fixed-weight pretrained Transformers. Their results showed that Transformers with prompts are able to approximate any sequence- ceeeencc-tt-segeeee so-sequence Lipschitz function. Besides, they constructed dataset, that cannot be memorized by single-layer Transformer with prompts of any length. Hu et all [2022]] investigated expressive power of single-layer and single-head Transformer, showing that prompt tuning is universal approximator and explicitly deriving the lower bound on the length of required prompt tokens. Rerrov an [202% formally showed that soft prompt tuning and prefix tuning are more expressive than prompting that only operates in the discrete token space. Besides, they demonstrated that prompt tuning suffers from some structural limitations that hold back the Transformers from forming task-specific attention patterns. In their another work [[etrrov et all 20221] Transformers with prompts were proved to be able universally approximate continuous functions defined on the hypersphere. However, the number of trainable parameters needed is larger than training from scratch, which showed that prompt tuning might be less efficient. Oymak et al. [2023] developed new statistical foundations for gradient-based prompt tuning, characterized its optimization and generalization dynamics, and explored how may facilitate attending to context- relevant information. Qiu et al. [2024]] showed there exists finite-size Transformer such that for any computable function, there exists corresponding prompt following which the Transformer computes the function, meaning that prompt tuning is Turing-complete. Our work is mainly built upon the framework proposed by Nakada constant-size Transformer can exactly implement ReLU feed-forward neural network with the prompt length being determined by the rank of weight matrices in each layer.
[2025]], in which they showed that prompt tuning
Preliminaries
2.1 Transformers
In this section, we formalize some basic concepts about Transformer architecture, which was first proposed by [Vaswan et all 2017]. In general, Transformers are defined by stacking multiple Transformer layers, each of which consists of self-attention layer and a feed-forward layer.
Self-attention Layer:
The core of Transformer architecture is the self-attention mechanism, which mixes information across different positions in the input sequences. The pair-wise dot-product and activation function determine how much focus each token should have on others in a sequence. To be specific, an self-attention layer F SA R IRD with H heads is defined as
H
F
x
Σ W Xo
(w
(W (1) x)) Q
RD
(2.1)
where Dmm E N+ is the embedding size, ((( R + R is the activation function in the self-attention layer. The self-attention layer computes a weighted average of linearly transformed token representations, with the attention weights determined by the similarity between query and key projections.
w E R the weight matrices,
Feed-forward layer: Self-attention layers deal with the interactions between different tokens, while layers provide non-linear, token-wise transformation, which processes each token
3

---

independently. A feed-forward layer FFF Ri XN + +R XN is given by
FFF (X) = + (W
(2.2)
where Diia is the hidden dimension, chosen to be i().). Wi E R W2 DDux and o' is the element-wise activation function in the feed-forward layer.
Remark 2.1. Let øs denote the Softmax function (i.e., [a,(2))] = cm E/= c=i [d]. for any 2: E )R"), and n denote the ReI.U function (i.e., (0)) max (2;, 0). E [d], for any x E R*). In existing literature, o' is usually chosen to be ReL.U function while has many distinct options.
et [2019] and Gu all [202]]] used Hardmax function for mathematical simplicity; Kajitsuka
and and Sato [01)]]] utilized Softmax function and proved that single self-attention layer with Hardmax function may not be powerful. Recently, Una el all [20258l] proposed to utilize different o', which may help to break the curse of dimensionality, In this paper, we set a and of both be element-wise
ReLU function. See discussion in Appendix D.5.
Based on the definitions of the self-attention and feed feed-forward layers, the class of Transformer neural networks can be formally defined as:
T(D Dout Disd, H, = T - F
1 o.. F
E
where Din is the embedding size, Dout is the output size, Dhid is the hidden dimension, H is the number of heads, is the number of Transformer layers, each consisting of self-attention layer and feed-forward layer. out and &nn two linear affine functions, which are designed to truncate the output and embed the input, respectively. For any sequential data point X E RdxN, we have Ein( (X) E IRP..XN, where the embedding size satisfies Din Od). If we let the output dimension Dout S Din, then we have E out (Y) = Domei E DouttN for any E RR
2.2 Feed-Forward Neural Networks
We denote F.F(W, L, Rd > Rd') as the set of vector-valued functions á Rd - Rd that can be represented by a feed-forward neural network (FFN) with width S E N+, depth < E N and activation function is oR. The width of a FFN refers to the maximum number of neurons in the hidden layers and the depth corresponds to the number of hidden layers. For instance, suppose Φ Rdd + Rd' is a vector-valued function realized by a feed-forward neural network activated by OR. Then, can be expressed
Φ LLOOR C
C1 o0R Co.
where each Le is affine linear map given by Lx(x)) War + be for f 1. L. Here, We E Rdetixde and b Rde+1 are the weight matrix and bias term, respectively, with du d. d..... ..... dg N and dxtb d'. Clearly, & E FF(W, + R²"), where W = max (di, .d.).
2.3 Autoregressive Generation
Given a Transformer T E T(Dins Douts Diid, H,T') for some Din Douts Drad, H,T E N+, which has the following form
T = E Eat F(D)
FF
(L)
SA o...o
F(1)
FF o of (())
SA o E Ein.
We let g denote the main part of T, that
g F (L)
Fo
(T)
F()). F(1)
SA For any sequential data X E RdxN and prompts P RR... Denote Xemb [P, (X)] E [R x(M+), In Autoregressive generation, the last token of the output will be prepended to the original sequence to form the new input. To be specific, suppose that Xemb ....... MM #M ".THH.,.....,M4V" NN where E; P... RP:.. for any i [M]. and 2; (x) ).iiM for any i E {M + 1, 1.... ......,N. + M). Given the generation step K E N g iteratively generates a sequence tokens #M+ ... #M - N ... N Following the techniques in [Naaada et all 2025]. we need to deal with certain piece of the generated sequence, which motivates us to give the following definition.
FF o SA
and we have #++++1 g( #+))

---

Definition 2.1. Given Transformer T E T(Din D Dout, Dhid, H, L) for some Dins Douts Diid, Hi E No, and the autoregressive generation step K N+ T can be written as T Eout o 9 Ein with 9 F PP o F&A SA o ..... F PF o F(l)
SA Given input sequence X RáxN and prompts P E RDmxMM with length M E NN T sequentially generate K tokens according
the autoregressive algorithm, denoted by 2M+N+1:". M which satisfy M++ 9([x1,...
2N ( for i [K]. Then, for any K1, E N with 1 < K1 K2 I K, we let TP.K,,K, K,K x,( (X) denote the piece from the K1 11 token to the Ky-th token of the generated sequence, that is
KP,Ki,Ks (X) = ouur ( #M4N+Kaa) (R
In particular, we let T T..0,0()) denote Eou og (P + Ein (X))),
2.4 Prompt Tuning
Prompt tuning aims to design or learn suitable prompts that can guide Transformers to generate desired output. Let X E Rd be a sequential input. Each column of X, that is, X.,. for any i E [M] is called the i-th token of X. Let E X be the label of X. [.-]] represents the horizontal concatenation of matrices. the following, we give the definition of prompt tuning.
Definition 2.2 (Prompt Tuning). Let Transformer T E T(Din; Dout: Daid: H, T.) for some Din, Dout, Dasd, H,L E N+ be pretrained model with frozen parameters. For any downstream task with finetuning dataset S {()),,, prompt RDrxXM of length M the output of T given input ( with prompt P and autoregressive algorithm is defined as
(X (*), Y(")] RdxN R XN and
(1) Kx,
where K₂ 1- K₁ N. Let : prompt tuning is to find an optimal prompt P such that
Poo xN RDouxXN + R20 be the loss function. The goal of
Σ e (f: SM++1 r())
P E arg min
PERPi .MEN
Technically, do not approach the above problem above from optimization perspective. Instead, we directly prove the existence of suitable prompts that enable a certain pretrained Transformer to achieve zero loss any given finite dataset satisfying some assumptions. Note that prompt tuning only prepends prompt tokens to the original inputs, whereas prefix-tuning -uning inserts such prompt tokens to the input of each self-attention layers (See details in [[Petrov et all 2023).. In this work, do not distinguish between the two.
3 Prompt Tuning Transformers for Data Memorization
In this section, state the main results of this paper regarding the memorization capacity of Transformers with prompts. Informally, memorization capacity refers to the possibility that models can achieve zero loss on specific number of arbitrary data points. To be more precise, given input-label pairs (x(1), ())))))))) (")..... (x("), y()) C. RaxN x [C]1xN, where C N+ is constant, representing the vocabulary size. We are interested in constructing an autoregressive Transformer T RdxN + [C]1xM with prompt P, and generation step Ki, K2 such that TPpKK.KK (X )9)= ()) holds for any [n). Here, formally state the assumptions regarding the data be memorized.
(x(1)
Assumption 3.1. Let (X(1), , ()) output pairs, where d is the input dimension, N is the sequence length, and C' E N+ represents the size of the vocabulary. We treat d, C constant and assume the following conditions are satisfied:
(X("), (n), (*) C pdxN
[ be a sequence of input-
For every E [n]] and & E [N], x k
[0, 1]d and || l| I for some r 2 1.
2. For every i E [n] and 1, E [N], either x x(0) = x( or |
x x 2 8 holds for
some < 0 < 1.
5

---

Figure I: Attention patterns of prompt tuning Roberta-base [Liu et al, 2019]. We report the attention patterns of prompt tuning Roberta-base base (12 layers, heads) for classification task on SST- 2 dataset (first row) and regression task unstructured random dataset (second row). When prompt tuning on SST-2 dataset, even if we provide a prompt with 8 tokens, the model mainly uses only two of them. However, when prompt tuning random dataset consisting of random input-output pairs, the model tends to use more prompt tokens.
3. For every E [n]. we can not find any j E [n]] with j * such that
x = x (i) up to permutations.
4. For every i E [n], and any k. [N], if X k
x! :1
we have
( (8) y y
Since we only consider finite datasets in this work, we can always find the desired r and 6, meaning that 1) and 2) in Assumption [ are inherently satisfied without imposing extra limitations on the datasets. Mentioned in [Sontag, [997] without 1) and 2), a linear order of parameters is needed to memorize n arbitrary data points. In order to achieve sub-linear memorization capacity, 1) and 2) are necessary, which are two common assumptions in existing works [Park et al, 2021I, (ardi et all 2021 Kim et all 2022, Kajitsuka and Sato 2023, 2024]. As for 3) and 4) in Assumption B know that Transformer architecture permutation invariant, that is, given any permutation matrix P. P)T(XP) T(X) P holds for any Transformer T. If (+) x up to a certain permutation, meaning that ( = T(X ()) up to the same permutation. Since in this work, we do not focus on positional encoding, that is why 3) and 4) are assumed to be satisfied. Otherwise, we can easily construct certain datasets that Transformers trivially cannot memorize. In the following, Proposition M shows that prompt tuning Transformers can memorize single token input-output pairs.
Proposition 3.1. Fix any n, d E N+ There exists Trunsformer T E <T(inn Dout, Drid, H, L) such that for any sequence of inpul-output pairs (L) )(.)),... (x(()) (y(")) E Rd x [C] satisfying Assumption B.A. there exsit prompt E RR xM and K N+ such that
(p. = =y( for any i E [n],
where Dín = O(d). Dout = 0(1), Duad = O(D..). = 0(1), = 0(1),, and M = Ö(vn). K = Ö(vn).
The proof of Proposition 3.I in Appendix DI Our proof depends on the following lemma, which shows that prompt-tuned Transformer with autoregressive algorithm is able to exactly implement ReLU neural networks with various width and depth by extending the results in Naaaada all
2025
Lemma 3.1. Fix any W. d E N There exists Transformer T E T(Din Dout. Drid. H, L) such that for any ReLU fordard neural network f E FF(W, L, Rd Rd ). where W, L, d, d'

---

N with d' < d, and n inputs X X(".... , C RaxN, there exists prompt P E RP XM
K1, K2 E N such that
Tp
any i E [n], X (0) = -1((x ".x, forany
where Din O(W V d). Dost= Odd), Dnsa - O(D.)) H 0(1, L = O(1), and M
O((W V V)) K1. K2 O(LL).
In Lemma EE]l the prompt length depends on the width and depth of the target feed-forward neural network, while the number of intermediate steps only depends on the depth. This is because any self- attention layer can capture the interaction between arbitrary token pairs due to the inner product, meaning that self-attention layer is in some sense infinitely "wide" if we plug in long enough prompt tokens. Based on this, we can establish a trade-off between the number of intermediate steps in autoregressive generation between the prompt length, which is summarized in the following corollary.
Corollary 3.1. Fix any n, d E N There exists a Transformer T E T(D Douts Duids H, L) such that for any sequence of input-oupus pairs (x(1), )..., Assumption B there exist prompt P E R. XM and K E No such that
yy()) E Rd [C] satisfying
Tp-,,K(E(()) y() for any i E [n],
where Din = O(n), Dout = 0(1), Dnia O(Di),, H = 0(), L = 0(1), and M = Ö(n), K = O(1).
The result in Corollary 6. reveals a trade-off between prompt length and the computational path: prompt of length Ö(yn) with (Vyn) intermediate steps and a prompt of length O(z) with Õ(1) intermediate steps have the same memorization ability, which underscores the advantage of employing longer chains of intermediate computation prior to producing the final answer [Wl 2022]. To extend our result to the case where sequence length N > 1, we need to consider the interactions between data tokens instead of only the interaction between data tokens and prompt tokens. This idea results in the following theorem.
Theorem 3.1. Fix any n, d E N There exists a composition of three Transformers T = (3() o ((
TT2) o (1) with T()) T(D!!) D oat hid: H(), )(0), such thatfor any sequence of input-ouppu
pairs (X(1) (y()),, (x))), (n). (m)) RRxN x [C]LıN satisfying Assumption 3. and N 1,
there exist prompts p(() E RD M and k() KKL E N such that
Tr(3)) P() xx xx(3)
(2)
p x o (1())
p() x(), xg) (x()) = y for any E [n],
where ( Od), D (i) O()), ( hid O(D H O(1), L = O(1), and M
Ō(VNN), ((6) K(O) Ô(N VNN), for = 1,
The proof of Theorem of 3. provided in Appendix II which basically follows the framework in [Kantsuka and Sato, 2022) The primary difference between two cases N = 1 and N > 1 is that we need to include the influence from other data tokens. For example, let (1) = [21, 2r2] and x²2 = 23). where x2 + xz. If ( and (2) are their corresponding labels, is possible that (1) * y.??) even if æ1 appears in both sequences, which reflects the real-world fact that the same val
words in different contexts may carry different meanings. To address this, we need to differentiate 21 in (1) and (2) based on the context where it appears by mapping it to different values via self- attention mechanism. Besides, approach is grounded in the concept of "Contextual Mapping", first formulated in [[un et all 201%] and further developed in [Kim et all, 2022, Kajitsuka and Sato, 2023. 20224). In Theorem B
also need to retain information in originally distinct tokens. This
adopt the technique from [Kaptsuka and Sato, 2024|]. In particular, we use Transformer ( to map each token into space with higher dimension to enhance separability. The subsequent layer (2) is designed to integrate contextual information by simply computing the summation of columns over input sequences. This process ensures that each token is mapped to unique vector determined by both the token itself and its context: if two tokens differ, or if identical tokens appear in different contexts, the resulting representations will differ as well. One important thing to point out is that in
7

---

[Kantsuka and Satd, MD2H], the separation gap between such vectors decays exponentially in terms of the number of data points be memorized. But in Theorem [.]l we can keep it as a constant due to the separation in high dimensional space, thereby keeping the required prompt length controllable. Finally, we build T(3) to perform point-wise fitting, mapping the contextualized representations to their corresponding labels.
Remark 3.1. (n) and ( in Theorem B. are mainly designed to implement feed-forward neural network through prompt tuning. According to Lemma EAT, we know the prompt length depends on the rank of [W.6 b] in each layer of the target feed-forward neural network, where [W, b) denotes the concatenation of the weight matrix and bias term. It is known that neural networks exhibit a low-rank bias, that is, they tend to converge toward solutions with low-rank weight matrices which leads to a possible reduction in prompt length in our setting. One explanation lies the fact that natural datasets usually present a low-dimensional structure, implying inherently limited intrinsic complexity [[alzano et all 20225]. As illustrated in Figure M. prompt tuning indeed favors low- complexity solutions by allowing data tokens to primarily attend to only small subset of prompt tokens even when longer prompts are provided. Further discussion of this phenomenon can be found in Appendix H
4 Prompt Tuning Random Transformers
The Transformer constructed in Theorem [.] is universal across the datasets to be memorized. Its architecture and parameters only depend on the input dimension d, while the number of data points only affects the embedding layer. The backbone Transformer contains task-specific information, rather, it defines a general mechanism governing the interactions between data tokens and prompt tokens. Motivated by this universality, we shift our attention studying the effectiveness of prompt tuning randomly initialized Transformers. Specifically, we investigate its memorization ability under different word embeddings, how initialization affects the performance and whether datasets with a low-rank structure can reduce the prompt length. This section seeks to understand the inductive bias of Transformer architecture, the fundamental limitations of prompt tuning, and the extent to which prompt tuning can steer the behavior of a model with frozen parameters.
4.1 Data Memorization Ability
We conduct experiments to evaluate the memorization ability of prompt tuned random Transformers. Specifically, we employ a two layer randomly initialized Transformer with an embedding size of 512, matching that of TS-small. The initialization strategy is the default in Pytorch. The data points to be memorized are randomly sampled from the IMDb [Maas el all 2011 dataset. As our focus is on whether models can memorize finite datasets, report the training accuracy for dataset sizes of 1600, 2500, and 3600. Correspondingly. the prompt length is set to be 40, 50, and 60, respectively. Each imput sequence is truncated to length of 8 and the outputs at the last data token are compared with labels using cross-entropy loss.
We consider two activation functions in each self-attention layer: ReLU and Softmax. The motivation for this choice is that Softmax widely adopted in practice, while ReLU is used in the construction of Theorem R.I. For each activation function, we examine two types of word embeddings: those initialized using the T5-small embeddings (frozen), and those that are randomly initialized and also kept untrainable. We compare prompt tuning against embedding-onl
training of Transformers [Khong and Andreas, 2024 Results are shown in Table II and a summary of findings is provided below.
Meaningful word embeddings boost accuracy As shown in Table MI when the word embeddings are initialized with T5-small pretrained embeddings and kept frozen, the resulting accuracy is substantially higher than that with randomly initialized embeddings. This indicates that meaningful pretrained embeddings already encode strong signals that facilitate the mapping from inputs to labels. and are kept untrainable, the accuracy is much higher than random word embeddings. Meaningful word embeddings already contain strong signal mapping from the inputs to labels. In this setting, the influence of prompt tokens appears to serve primarily as slight calibration rather than fundamental driver of the model's behavior. This interpretation is supported by the attention patterns visualized in Figure both Softmax and ReLU Transformer automatically allocate most of their attention weights to data tokens, with only minimal focus prompt tokens.
8

---

ReLU outperforms Softmax As shown in Table MI prompt-tuned ReLU Transformers initialized random consistently outperform their Softmax counterparts under both T5-small and random embedding settings. To further understand this phenomenon, the visualization in Figure E offers a plausible explanation. When using T5 embeddings, ReL.U-based attention layers can assign disproportionately large weights (often exceeding 10) to data tokens, as they are not constrained by the normalization inherent in Softmax attention. In contrast, Softmax-based attention inevitably distributes its weights across both data and prompt tokens, limiting the emphasis that can be placed on individual data tokens. However, this flexibility ReLU attention comes with a trade- off: Transformers trained from scratch with ReLU attention often exhibit less stable optimization dynamics, since the lack of normalization may amplify gradient- relatee instabilities during training [Shen et all 2023
Table 1: Training accuracy across different activation functions, embeddings and dataset sizes.
Activation
Prompts
Embedding
Acc(1600)
Acc(2500)
Acc(3600)
ReLU
T5-small
0.9962
0.9944
0.9925
ReLU
Random 0.8619
0.8216
0.8164
ReLU
X
Trainable 0.9962
0.9944
0.9947
Softmax
T5-small 0.8888
0.8740
0.8486
Softmax
Random 0.5375
0.5484
0.5186
Softmax
X
Trainable 0.9969
0.9928
0.9936
4.2 Random Backbone Still Captures the Low-rank Structure In the Dataset
Based on the observations from Figure M. 0. B. and Lemma E the required prompt length appears to depend the complexity of the downstream tasks. This raises important question: does this property depend specifically on pretrained LLMs, or can prompt-tuned random Transformer also capture the intrinsic structure of datasets. To investigate this, examine performance across different prompt lengths using datasets generated by a low-rank feed-forward neural network.
We randomly generate input data X E R ((4444), and initialize a ReLU ferd-forward neural network f with 8 layers, input dimension 16, and width 32. For the Normal task, f is initialized following the default strategy and kept frozen. For the low-rank mapping task, replace each concatenation
weight matrix and the bias term, that is, [W, b] by a rank-1 matrix and also make each of them untrainable. For the low-rank input and mapping task, we constrain the input data points to be in low-rank linear space. The training dataset size is 2000 and test dataset size is 200. As shown in Table Dl prompt tuning random Transformer capture the low-rank structure the dataset and prompts with much less length can even better performance.
Table 2: MSE Loss with a low-rank structure in the dataset.
Prompt Length
10
20
30
40
Dataset
Normal
0.3258
0.2580
0.2674
0.2364
Low-rank mapping
0.0076
0.0053
0.0026
0.0022
Low-rank input and mapping
0.0038
0.0015
0.0015
0.0007
4.3 Initialization and Limitation
For mathematical simplicity, let T FF FSA SA denote single layer Transformer consisting of one self-attention layer and one feed-forward layer. We omit the embedding and decoding matrices
here and consider dataset (x(1), y ()),,... (x) (()) c Rdx N Rd consisting of n input- (())
label pairs to be memorized. Let P E RdxM denote the prompt. If for some E [n], this implies that F ( (1),, E ()),, where F ()) :=
w Rd F FFF(() = In other words, during the computation of self-attention the output

---

representation of the last token must be shifted into the space F Fy Since all the parameters of T are frozen and further the interactions between data tokens are fixed, this shift can only be achieved through prompt tokens. In [Wang et all 2023], they explicitly constructed counterexample showing that regardless of the number of prompt tokens, the data tokens can not be shifted to F F Motivated by this, can identify several constrained initialization strategies as follows:
Low-norm FFF: if Wi and W2 in FFF satisfy || WWell 1, then FFF is invertible [aang et all 2023, Behrmann et all 2019). As a result, FF remains small.
Low-rank Wv: Since the output of any self-attention layer is a linear combination of the column vectors of Wv, constraining the rank of Wy can reduce the diversity of the output.
Low-rank Wx: As shown in (Bhojanapali et all, 2020), the ranks of WK and Wq affect the diversity of the ways tokens interacting with others.
Low-rank Wq: Similar to the effect of low-rank WK.
As shown in Table low-norm FFN degrades the performance only when the prompt length is small. Among the low-rank variants, low-rank Wy exhibits the lowest accuracy, while low-rank Wx and low-rank We have relatively slight negative impact on the performance.
Table 3: Training Accuracy across different initialization strategies.
Prompt Length
10
20
30
40
Initialization
Random
0.7865
0.8263
0.8462
0.8619
Low-norm FFN
0.7788
0.8119
0.8550
0.8631
Low-rank Wv
0.5125
0.6625
0.5994
0.5631
Low-rank WK K
0.7163
0.7356
0.7394
0.7512
Low-rank WQ
0.7506
0.7569
0.7538
0.7481
5 Conclusion
Our study provides a new perspective on how prompt tuning enables Transformers to memorize and represent data. Rather than viewing prompts merely task adaptors, we show that they can encode substantial structural information about the dataset itself. Theoretical analysis reveals that the prompt length required for memorization scales sublinearly with the dataset size, while empirical results confirm that prompt-tunce random Transformers can still capture low-rank regularities in data embeddings. These findings suggest that prompt tuning leverages the implicit inductive bias of Transformers to compress information efficiently, even without task-specific supervision.
Our analysis primarily focuses on simplified Transformer architectures and small datasets, which allow for controlled theoretical and empirical investigation but do not fully capture the complexity of large-scale pretrained models. Extending the current framework to realistic large language model settings, and studying how prompt tuning interacts with pretraining dynamics, remain promising directions for future work.
Limitations:
Acknowledgments
We thank the anonymous reviewers for their insightful feedback and valuable suggestions that helped improve this paper. Yuanyuan Lin's research partially supported by the Hong Kong Research Grants Council (No. 1N..44304523 and Direct Grants for Research, The Chinese University of Hong Kong.
10

---

References
Zeyuan Allen-Zhu and Yuanzhi Li. Physics of language models: Part 3.3, knowledge capacity scaling laws. arXiv preprint arXiv:244.055005 2024.
Laura Balzano, Tianjiao Ding, Benjamin Haeffele, Soo Min Kwon, Qing Qu, Peng Wang. Zhangyang Wang. and Can Yaras. An overview of low-rank structures in the training and adaptation of large models. arXiv preprint (rXx::2503,19850 2025.
Jens Behrmann, Will Grathwohl, Ricky TQ Chen, David Duvenaud, and Jörn-Henrik Jacobsen. Invertible residual networks. In International conference on machine learning, pages 573-582. PMLR, 2019.
Srinadh Bhojanapalli, Chulhee Yun, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Low- rank bottleneck in multi-head attention models. In International conference on machine learning, pages 864-873. PMLR, 2020.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. In The Eleventh International Conference on Learning Representations, 2022.
Xingwu Chen and Difan Zou. What can transformer learn with varying depth? case studies on sequence learning tasks. arXiv preprint arXiv:2404.0160) 2024.
Léo Dana, Muni Sreenivas Pydi, and Yann Chevaleyre. Memorization in attention-only transformers.
arXiv preprint arXiv:2411.10111 2024.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume (long and short papers), pages 4171-4188 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint MOX1::0010.11929 2020.
Taoran Fang, Yunchao Zhang, Yang Yang, Chunping Wang, and Lei Chen. Universal prompt tuning for graph neural networks. Advances in Neural Information Processing Systems, 36:52444-52499, 2023.
Chunjiang Ge, Rui Huang, Mixue Xie, Zihang Lai, Shiji Song, Shuang Li, and Gao Huang. Domain adaptation via prompt learning. IEEE Transactions Neural Networks and Learning Systems, 2023.
Yuxian Gu, Xu Han, Zhiyuan Liu, and Minlie Huang. Ppt: Pre-trained prompt tuning for few-shot learning. arXiv preprint arXiv:2109.0433,, 2021.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in neural information processing systems, 31, 2018.
Iryna Gurevych, Michael Kohler, and Gözde Gül Şahin. On the rate of convergence of a classifier based transformer encoder. IEEE Transactions on Information Theory, (8(12):8139-8155, 2022.
Muhammad Usman Hadi, Rizwan Qureshi, Abbas Shah, Muhammad Irfan, Anas Zafar, Muhammad Bilal Shaikh, Naveed Akhtar, Jia Wu, Seyedali Mirjalili, et al. A survey on large language models: Applications, challenges, limitations, and practical usage. Authorea Preprints, 3, 2023.
Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al. A survey on vision transformer. IEEE transactions on pattern analysis and machine intelligence, 45(1):87-110, 2022.

---

Valentin Hartmann, Anshuman Suri, Vincent Bindschaedler, David Evans, Shruti Tople, and Robert West. Sok: Memorization in general-purpose large language models, arXiv preprint arXiv:2310. 18362, 2023.
Alexander Havrilla and Wenjing Liao. Understanding scaling laws with statistical and approximation theory for transformer neural networks on intrinsically low-dimensional data. Advances in Neural Information Processing Systems, 37:42162-4221 2024.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu. Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. ICLR, 1(2):3, 2022.
Jerry Yao-Chiel Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zhao Song, and Han Liu. Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency. arXiv preprint 4rX1v:241..1655,, 2024.
Jerry Yao-Chieh Hu, Hude Liu, Hong- Yu Chen, Weimin Wu, and Han Liu. Universal approximation with softmax attention, 2025. URL
15956.
Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola. The low-rank simplicity bias in deep networks. arXiv preprint 10314:2003.1042, 2021.
Wenlong Ji, Weizhe Yuan, Emily Getzen, Kyunghyun Cho, Michael Jordan, Song Mei, Jason E Weston, Weijie J Su. Jing Xu, and Linjun Zhang. An overview of large language models for statisticians. arXiv preprint arXhv:2502.17844 2025.
Menglin Jia, Luming Tang, Bor-Chun Chen, Claire Cardie, Serge Belongie, Bharath Hariharan, and Ser-Nan Lim. Visual prompt tuning. In European conference on computer vision, pages 709-727. Springer, 2022.
Haotian Jiang and Qianxiao Li. Approximation rate of the transformer architecture for sequence modeling. Advances in Neural Information Processing Systems, 37:68926-68955, 2024.
Yuling Jiao, Yanming Lai, Defeng Sun, Yang Wang, and Bokai Yan. Approximation bounds for
transformer networks with application to regression. arXiv preprint arXiv:2504.12175 2025a.
Yuling Jiao, Yanming Lai, Yang Wang, and Bokai Yan. Transformers can overcome the curse of dimensionality: A theoretical study from an approximation perspective. arXiv preprint ar04v:2504. 13558, 2025b.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, al. Highly accurate protein structure prediction with alphafold. nature, 596(787)):583-55)) 2021.
Tokio Kajitsuka and Issei Sato. Are transformers with one layer self-attention using low-rank weight matrices universal approximators? arXiv preprint 2rXIv:2307.140233 2023.
Tokio Kajitsuka and Issei Sato. Optimal memorization capacity of transformers. arXiv preprint arXiv:2409. 17677, 2024.
Junghwan Kim, Michelle Kim, and Barzan Mozafari. Provable memorization capacity of
transformers. In The Eleventh International Conference on Learning Representations, 2022.
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efffiient prompt tuning, arXiv preprint arXiv:2104.0869) 2021.
Hude Liu, Jerry Yao-Chieh Hu, Zhao Song, and Han Liu. Attention mechanism, max-affine partition, and universal approximation. arXiv preprint arXiv:2504.19900 19901, 2025.
Xiao Liu, Kaixuan Ji, Yicheng Fu, Weng Lam Tam, Zhengxiao Du, Zhilin Yang, and Jie Tang. P- tuning v2: Prompt tuning can comparable to fine-tuning universally across scales and tasks. arXiv preprint ar arXiv:2110.07602 2021a.
12

---

Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zet,lemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprini arXiv: 1692, 2019.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer. Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference on computer vision, pages 10012-10022, 2021b.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint
arXiv:1711.05101. 2017.
Andrew Maas, Raymond E. Daly, Peter T Pham, Dan Huang, Andrew Y Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pages 142-150, 2011.
Sadegh Mahdavi, Renjie Liao, and Christos Thrampoulidis. Memorization capacity of multi-head attention in transformers. arXiv preprint arXiv:2306. 02010, 2023.
Ryumei Nakada, Wenlong Ji, Tianxi Cai, James Zou, and Linjun Zhang. A theoretical framework for prompt engineering: Approximating smooth functions with transformer prompts. arXiv preprint arXiv:2503.20561. 2025.
Humza Naveed, Asad Ullah Khan, Shi Qiu, Muhammad Saqib, Saced Anwar, Muhammad Usman, Naveed Akhtar, Nick Barnes, and Ajmal Mian. A comprehensive overview of large language models. arXiv preprint #rXiv:2307.06433 2023.
Samet Oymak, Ankit Singh Rawat, Mahdi Soltanolkotabi, and Christos Thrampoulidis. On the role of attention in prompt-tuning. In International Conference Machine Learning, pages 26724- 26768. PMLR, 2023.
Mustafa Safa Ozdayi, Charith Peris, Jack FitzGerald, Christophe Dupuy, Jimit Majmudar, Haidar Khan, Rahil Parikh, and Rahul Gupta. Controlling the extraction of memorized data from large language models via prompt-tuning. arXiv preprint arXiv:2305. 11759, 2023.
Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. In Conference on learning theory, pages 3627-3661. PMLR, 2021.
William Peebles and Saining Xie. Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF international conference on computer vision, pages 4195-4205, 2023.
Aleksandar Petrov, Philip HS Torr, and Adel Bibi. When do prompting and prefix-tuning work? a theory of capabilities and limitations. arXiv preprint arXiv:2310.19699 2023.
Aleksandar Petrov, Philip HS Torr, and Adel Bibi. Prompting a pretrained transformer can be universal approximator. arXiv preprint 20X1v:2402.14753, 2024.
Ruizhong Qiu, Zhe Xu, Wenxuan Bao, and Hanghang Tong. Ask, and it shall be given: On the turing completeness of prompting. arXiv preprint arXiv:241 1.01992, 2024.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1 167, 2020.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. International conference on machine learning, pages 8821-8831 Pmir, 2021.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. Photorealistic text-to-image diffusion models with deep language understanding. Advances in neural information processing systems, 35:36479-36494, 2022.
Kai Shen, Junliang Guo, Xu Tan, Siliang Tang, Rui Wang, and Jiang Bian. A study on relu and softmax in transformer. arXiv preprint ar21v:2302.06461 2023.
13

---

Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng. and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631-1642, Seattle, Washington, USA, October 2013. Association for Computational Linguistics. URL https: //t/://wwww aclweb. org/anthology 013-1170,
Eduardo D. Sontag. Shattering all sets of k points in general position requires (k 1)/2 parameters.
Neural Computation, 92):337-334, 1997. doid00 116/nec.
Shokichi Takakura and Taiji Suzuki. Approximation and estimation ability of transformers for sequence-to-sequencee functions with infinite dimensional input. In International Conference on Machine Learning, pages 33416-33447. PMLR, 2023.
Naoki Takeshita and Masaaki Imaizumi. Approximation of permutation invariant polynomials by transformers: Efficient construction column-sizz arXiv preprint arXiv:2502.11467 2025.
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: survey. ACM Computing Surveys, 55(6):1-28, 2022.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of relu neural networks. arXiv preprint vrXiv:2110.03111 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Ruben Villegas, Mohammad Babaeizadeh, Pieter-Jan Kindermans, Hernan Moraldo, Han Zhang, Mohammad Taghi Saffar, Santiago Castro, Julius Kunze, and Dumitru Erhan. Phenaki: Variable length video generation from open domain textual description. arXiv preprint arXiv:2210.02399, 2022.
Xinyi Wang, Antonis Antoniades, Yanai Elazar, Alfonso Amayuelas, Alon Albalak, Kexun Zhang, and William Yang Wang. Generalization vs memorization: Tracing language models' capabiliitess back to pretraining data. arXiv preprint urXiv:2407.14983 2024.
Yihan Wang, Jatin Chauhan, Wei Wang, and Cho-Jui Hsich. Universality and limitations of prompt tuning. Advances in Neural Information Processing Systems, 36:75623-75643, 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's transformers: State-of-the--a natural language processing. arXiv preprint 1rXiv:1910.03771, 2019.
Mitchell Wortsman, Jaehoon Lee, Justin Gilmer, and Simon Kornblith. Replacing softmax with relu in vision transformers. arXiv preprint 2xXiv:300908886, 2023.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of -o-eecee----eeeeeee functions? In International Conference on Learning Representations, 2019.
Chulhee Yun, Yin- Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. O(n) connections are expressive enough: Universal approximability of sparse transformers. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 13783-13794. Curran Associates, Inc., 2020. URL https: iewpeeeeeeeeiineeeeeeeeeeeeeeeee wttpurips.ccppppppppeeeppp ffrffff11 files/paper/ 4DDDFff...0777444335636622222222
påf.
Ziqian Zhong and Jacob Andreas. Algorithmic capabiliitis of random transformers. Advances in Neural Information Processing Systems, 37:104357-104388 2024.
Kaiyang Zhou, Jingkang Yang, Chen Change Loy, and Ziwei Liu. Learning to prompt for vision- language models. International Journal of Computer Vision, 13009))2337-23888 2022.
14

---

Appendix
Notation Table
16
Additional Related Works
17
Construction of Prompts
18
Prools of Section 3
18
Proof of Lemma
18
D.2 Proof of Proposition 3.
20
D.3 Proof of Corollary 3.1
21
4 Proof of Theorem
21
D.5 The Limitation of a Sinlle ReLU Scll-attention Layer
27
Supporting Lemmas
28
Prompt Tuning Transtormers to Exactly Implement Residual Feed-Forward Neura
Networks
29
Data Memorization with Real Labels
30
Low-Rank Bias of Prompt Tuning
32
Experimental Details
34
Setup Detail
34
Additional Expenmental Results
35
15

---

A
Notation Table
Functions
A B
The function with domain A and range
fog
Composition of the functions f and
f(x; 0)
A function of æ parametrized by 0. (Sometimes we write f(x) and omit the argument to lighten notation)
(2(x)
ReLU function, max( (r,000 0}
Softmax function, (a()) = exp(x;;)
(s))
E exp(x;;
|
L norm L norm of æ Spectral norm of matrix X 0O norm of Positive part of æ, i.., max(0, max(x, y)
X l2
a ooo
+
V
FSA
self-attention layer
F FF
Feed-forward layer
T(Ding Dont, Dridd H, L)
Transformer neural network class with embedding size Din- output dimension Dowt hidden dimension hasd- number of heads H, number of layers L
FF(W,L,R* - R
Feed-forward neural network class with width W, depth I, input dimension and output dimension d', activation function dn
R(W, N.W. + Rd)
Residual feed-forward neural network class with hidden dimension W. number of layers L, input dimension and output dimension activation function OR
Numbers and Arrays
A scalar (integer or real)
a
vector
4
A matrix
I,
Identity matrix with n rows and columns
Identity matrix with dimensionality implied by context
Standard basis vector [O..... 0, 1,0, 0] with a at
position
1,xm
All-one matrix with dimensionality n x m
16

---

Sets
The set of real numbers
RD
The set of D-dimensional real vectors The set of D-dimensional positive real vectors The set containing and The set of all integers between O and
{0,
{0, 1. n
[n]
The of all integers between and n, that is, [n] (1,"",, m)
Indexing
a,
Element of vector a, with indexing starting at
a-1
The last element of vector a
Aij
Element i.j of matrix A
Row of matrix A
Age
From i-th row to the last row of matrix
A.
Column i of matrix A
A.
from i-th column the last column of matrix A
Asymptotics
f(n) (g((n)
grows at most fast as g for sufficiently large grows at most as fast as g for sufficiently large n, up logarithmic factors
f(n) Ö(g(n))
((n) (((()))
grows at least fast as g for sufficiently large There exists positive constant e such that f S eg holds
f2g
B Additional Related Works
Another line of theoretical study on the expressive capacity of Transformers is consider the approximation ability Transformers, that is, can Transformers approximate functions that belong to given function class. The most seminal work by [[Yu et al, 2M1] provided the first universal approximation thcorem for Transformers, showing that any continuous sequence-to-see to-sequence functions defined on compact domain can be approximated by Transformers to any finite precision. They also extended the results to sparse Transformers [Yun et all 2020]. Later, Gurevych et all [2022] established constructive method, proving that Transformers can approximate piecewise polynomials. Jiang and Li [0021]] built their results of approximating continuous functions by shallow Transformers based on the Kolmogorov Representation Theorem. Takakura and Suzuki [2023]] provided both approximation and estimation error with 7-smooth function class under the assumption that the input is infinite dimensional. Similarly, Havrilla and Liad [2022]] assumed that the input data has low-dimensional manifold structure and established approximation results for 3-Hölder continuous functions with Transformers. They also gave an explicit form of the scaling law by utilizing techniques from non- non-parametric statistics. Kaptsuka and Sato [202]] showed that Transformers with one single-head self-attention layer are able be universal approximator by exploring the relationship between the Softmax function in self-attention layers and the Boltzmann operator. Dakeshita and Imazumii [2025] proved that Transformers can efficiently approximate colunn-symmetric polynomials with respect to the number of parameters. Recently, Jiao et all [2025%] derived the approximation results of Transformers for Hölder class and Sobolev class under T.Pnoom, where p Foo). Besides, their another work [Iiao et all 202511 showed that Transformers can overcome the curse of dimensionality based on the Kolmogorov-Arnole Representation Theorem. Concurrent work Bi al [12A]]] made an effort avoid the dependence
17

---

on large ReLU feed-forward layers, by proving that self-attention layers alone can approximate a generalized version of ReLU function and hence subsumes any known approximators based on ReLU feed-forward neural networks. Similarly, Liu [2025] proved that single self-attention layer, preceded by sum-of-linear transformations, is capable of approximating any continuous function compact domain under 7 -norm, highlighting the inherent expressive ability of self- attention mechanism alone.
C Construction of Prompts
We basically follow the framework introduced in [Nakada al 2025 to construct prompts. Given prompt E X for any Raxx let X emb
[P, in (X)J. We have
X emb
11 ......
B. a ...
MM+N RR (NN+))))+),
prompt tnkens
data tokens
Where Din 2 is the embedding size, M is the length of the prompt and N the length of the input sequence. In this work, set Din 4d 8. Each prompt token is divided into parts: guidance embedding and positional embedding The exact form of prompt tokens is defined below
Uj
0 03d+4
1
3j =
u
Pj
T
Rdd+s
for E [M],
(C.1)
S
guidance emberkling positional emhedding
Sw;
Sj
where u, E Rd called the guidance embedding, and Pj E R3d+8 is the positional encoding, defined as P, = p( == (0% 1, SJ) The large enough S > denotes the scaling factor, which ensures that the positional encoding remains significant relative to guidance embedding. The constant serves as bias term, while the zeros Py function as a temporal memory store intermediate variables because of the skip connection. Guidance embeddings aim to guide the Transformers, which store the task-specific information. The integer wA E N+ works as indicator to force Transformers to focus on certain prompt tokens in different autoregressive generation steps. Given same scaling factor S in prompt tokens, data tokens & TM+11'" MMM defined as follows
X
Osd+4
3MH (X. P0. +
E Rid4s
for E [N].
(C.2)
S
S (M + i)
D Proofs of Section 3
This section provides all the detailed proofs in Section GL
D.I Proof of Lemma 3
Lemma shows that prompt tuning a Transformer can exactly implement a ReLU feed-forward neural network, that is, given the same input, the output is the same. Our results are built upon [Nakada et all 2025)), by extending their results the case where the width of the target ReLU heed-forward neural network can be smaller than the input dimension.
18

---

Lemma D.1 (Restatement of Lemma B. Fix any W. d E N There exists a Transformer
T T(Dins D Dout, Dhids H,L) L) such that for any ReLU feed-forward neural network
FF(W, L, Rd + Rd where W, W,L, d,
N+ with d' S d, and n inputs X(1, , X(x) C
RdxN there exists a prompt P RRPax K1, K2 E EN such that
Tp.Ky.Ko X (1) (S (1) [(x for any i E [n],
where Din O(W d). Dout Odd), Dhid O(D..) 0(1), L O(1), and M
O((W V d)).,. K1 K2 O(LL).
Proof of Lemma
Suppose f has the following form
= Lr oR C1- Li CIooR Co(æ),
where Le(x)) = Wax + be with We E Rdetixde and b, E Rd for l 0, .. L. In the following, consider two cases: Case 1: W d, Case 2: W d, respectively.
Case 1: W 2 Let Wt for & E [L] U {0) denote series of matrices that incorporate the bias terms by into multiplication of matrices with dimension p(O++))((++)) which are defined
W t
be
0
We
0
(((++)x(W+)) for [
0
0
0
With We in hand, we define a new feed-forward neural network f as
f(x) OLOORO C1-10 E1 o oR Lo(x))
where Le(x)= Wi()). It clear that E FF(W + I, R. RW+1). For any X
101 ... [NN]= RaxN,, let X = (&1 ... ANvl E R(W+IjxN, where a, = x 1, (w -w- for i E [N]. It is direct to verity that
f(0.)210 f(x.),
and
f(t))1a41 [f(x))
By applying Lemma
F to f. we know that there exists Transformer T
T(Dis Douts Drid, H, L). and prompt P IRpixxA, K2 N such that
f(w))i.d = ff(x,) f(x.) for any i E [N], Tp. (X) (X)
or by using different E we have
for any i E [N], where Ki41 = K; + The proof of Case is completed by pointing out that D., = O(W), D Dout O(d), Drid O(D,,), and H 0(1), L =O(1), and M O((W + 1) + 1)). K, ((N(L+2)
Tp.k,,K (X)
_1] ((x:) [f(x:) [1]')),]]''
Case 2: W < d Similar to Case 1, let We for é E 1 {0} denote series of matrices that incorporate the bias terms by into multiplication of matrices with dimension R(dd-1)((++1), which are defined as
W
b
0
W.
0
1
0
E p(d+1)x(d+1) for i E [L] U (0).
19

---

With We in hand, we define a new feea-forward neural network f as
f(x) = Ê1 CLOORO 1 Li oR Lo(ar).
where Lx(xx) = (x)).. It is clear that f E FFid 1, L, R + Rd+1). For any X
1...... .N E RAxN, let X [0,,-.. Gxl R(d+))xN where ã; [ for i [N].
is direct to verify that
f( = f(ar),
and
f ((.)) = [f(x:]
By applying Lemma to f. we know that there exists a Transformer T E T(Din Douts Dhid, H, L), and prompt TRDixxM K; N such that
K, f(()) f(x))" for any i [N],
or by using different Eont: we have
Tp, f(a.) = =1 [x:)) for any i E [N],
where Ki+1 K; + The proof of Case is completed by pointing out that Dir O(W).
Dout = O(d), Dhid = O(Di.), and H = O(1, L = O(1), and M = O((d + 1) + 1)), K; = ON)(
Finally, we have proved that for any feed-forwad neural network f E FF(W, I, Rd + Rd there exists Transformer TDDin, Dout, Drid, H, I.) such that
Tp.KI.k, (X) = [f(X.1), ... ,(X.,N]] for any X E 10,1,
where Dm O(W V d), Dout = O()), Diad O(Di)), и 0(1) I. = O(1), and M O((W v d)L), K,, Kg = O(N)). The proof is completed by considering Tp, Tp (X()) for i E [n].
D.2 Proof of Proposition 3
Proposition D.1 (Restatement of Proposition I. Fix any nI, d E N+ There exists Transformer T T(Diny Douts Drids L) such that for any sequence of input-oulpul pairs (x) ()))).... (x((), ((m)) ((())) Rd [C] satisfying Assumption 1 there exsit a prompt P
RDi KM and K E N+ such that
T (x)() = (() for any E [n],
where Din = Odd), Dout O(1), Drid O(D..). H O(1), L = 0(1, and M = Ö(Vn). K =((vn)
Proof of Proposition 1 According to Assumption 1-11 we know that x(+) E [0, 1jd with | <
r, and (1) (0()) 8 for some r > 1, < 8 S 1. By applying Lemma DE to
(x(),, y()), ... (x y (")),, there exists ford-forward neural network f E T(W, L, Rd
R)
with W = 0(1, = (Vm) such that f()(1)) = y() Then, by applying Lemma i to f. there
exists Transformer T E T(Din, Dout, Dhid, H, L). and prompt P E RP XM K, N such that
Tp TP.K,,K (x) (0) ()) for any E [n],
where O(D..) = O(d), Dont = 0(1), Dhid O(Din), H = 0(1), L 0(1), and M = Ō((T). K, Ö(vn).
20

---

D.3 Proof of Corollary +
The proof of Corollary is similar to that of Proposition 1 where we only need replace Lemma Em by Lemma
Fix any n, E N There exists a Transformer T T(Dmn Dutt Dhid, H, L) such that for any sequence of input-oupuu pairs (x y (()),... (ax("), y(m)) Rd x [C] satisfying Assumption B. there exist a prompt P
Corollary D.1 (Restatement of Corollary B.
RDi XM and K E N+ such that
TP.KKK( = y1)) for any i E [n],
where Din = O(n), Dout = 0(1), Diid O(Din), H = 0(1, L = 0(1, and M Ö(n),
K = O(1)
Proof of Corollary B According to Assumption B we know that x(() E [0. 1j with || S
and ||x(()) xz 1| 2 8 for some 2 1, 0 < 5 S 1. By applying Lemma EK to
(x(),, y ), (x!2 "y(")), there exists feed-forward neural network f E T(W, L, Rd - R)
with W = O(n). L = Ó(1) such that f(x(0) y Then, by applying Lemma B to f. there
exists a Transformer T E (Dim, Dout, Drid, H, L). and prompt P E RR X.
K E N such that
Tp, Tp,,,x(x(0) = =0() for any i [n],
where O(D,n) = O()), D = (1), Dnad ODD.)) 0 L = 0(1), and M Ö(n). K = O1)).
D.4 Proof of Theorem 3
Theorem D.1 (Restatement of Theorem
1.. Fix any n, d E N There exists a composition of
three Transformers T T33) (2) T()) with T T(D D(t) Did H, L), such that for
any sequence of input-output pairs (x(), ()) (x(1), y y(m) RdxN x [C]|x satisfying
Assumption 1 and N 1, there exist prompts p(() E RD XMO and K(a _K2 E N such that
(3( P(. P30, (00,,(3)) (ea,, .((
71(2)
x()) xx²) o (1(1)
(x() y for any i E [m],
p() p() k
where D (0) Od), D (i)
0(1), D O(D()) H 0(1), L = O()) and M
Ō( O(vnN), (1) K. Ö( V.N). = 1,2,3.
Proof of Theorem 1 Our proof basically follows [Kajitukaa and Sato, MIZeI]. Step 1: For any X E RdxN define function m(x): Rd + N as counting the number of occurences of x in X, that
is, mxx) = Hk E [N] : X = xH.. Let m, denote the corresponding m( of (0), Firstly, we show that for any dataset { {(x (1) )) satisfying Assumption B.Il there exists subset A C Rd
with A S n such that for any i E [n]. there exists x E A such that
m,(x)) F mz(x),
which means that we can only use a set containing less than n elements to differentiate each X (+) To prove this fact, we can see that the case when n 1 is obvious. We assume that the case for = A is correct, and prove the case where = 1: + 1. Let (X(1), (1)),, (X (k+11) (k+1)) C RdxN x [C] be a sequence of input-output pairs, which satisfy Assumption B. Then, by applying the assumption about n k to the first & data points, we know that there exists subset A C Rd with |A| < k such that for any i * j E [r]]. there exists x E A such that m, # (x).
If there exists E [k] such that for any x E A, the following holds
m (x) = m (x))
Then, we can find an element & E Rd such that m, (x) + m=+1(() (x) due to the fact that ( o ( under any permutations. Subsequently, we define a new set A' = A AU (æ)) which the desired set for the case where n le + 1 and |A'| < k + clearly. The induction is comleted.
21

---

Step 2: Construction of (()) In this step, we present the construction of T Let S denote the set introduced in Step 1. Let g + [|S|] be an arbitrary bijective function, which maps each token in S to a unique positive integer less than (8]. For each token æ E S, we consider mapping it to an element in high-dimension space, in which they are separable. With this motivation hand, we define ((() for i [n] by
Σ (x))
where (2 E [0,1) is a one-hot vector with in the g(X (, I-th position. According to Assumption B and definition of S, for any # E [m], we can always either find k, E [N] such
that x(2 # x Sr or x x E but m X # m mx As result, we have the
following fact
-
.0)
21,
(D.1)
2
holds for any i E [n]. and the norm of each (() is upper bounded by
(3)
e
[oxx N.
ISKSN Es
By applying Lemma
to (1).
(x),, there exists a unit vector v E RISI such that
8
200 a66) 1| S 10(00 200) $ (000 20 ||
(D.2) In and / 1......... [n][S] //SS//er / 1) E NISI, The motivation of introducing è is to use an integer vector to approximate n² / To and make it convenient for later techniques based on memorization of integer labels. It is clear that
2 T|S]
holds for any i.j E [n]. Let h be the function
+ x
|8|
|| |I - -612
-
1
S|
(D.3)
For any (t), we have
Σ
h(x
Σ
[n TV ((x
ISKENX
ISKEN,X!EES
Σ
(x
T 2()
We point out that Eisken h(x!2) can be viewed as the integrated information of the
sequence (1),The explanation is as follows. For any i + E [n]. we have
Σ
h(x
Σ
((x())) (k)
(D.4)
I (1)
ISAEN.X
TT (o(1) - {6723|
(D.5)
2 S no (x((0) - -x(0)
(n²|s) VVVV -8) T)T((()) 260)
(D.6)
2
(1)) 40)
ViSi (+()) x0(5
(D.7)
VIs
600 a
(D.8)
2 SS.
(D.9)
22

---

where the last inequality is derived from Eq Besides, the second to last inequality is derived from Eq and the following fact
in| |2|SSVTT (x 2ا0ه
= n SS w. "T((t ($(
+b))|
8
2 n π.
n2 x||
> 25/s)
(1) x())
Up to now, we have constructed a function h such that EisieN, (Pes h(X()) different with each other and the difference between them is large. In
where the first inequality is based on Eq
D
the meantime is straightforward to verify that |x(x))] S 2n [SVTT, and we can further derive
Σ
h(x S 2n V
(D.10)
where we use the fact |S| S n. With function in hand, we define function Φ Rd -> R such that
((x)
x
Φ(x) 0 otherwise.
Notice that the possible number of inputs for the function & is at most n.N, and all outputs are less than equal to [2n2|S] I [2m² VTl. Then, consider to implement é. By applying Lemma E.2. we know there exists a feed-forward neural network fi E FF((1, L1, Rd + R) such that for any i E [n] and [M]
feed-forward neural network
Si(X!
h(x
ES
otherwise.
If we let C1 = [2n² VT and R 20r(n VTd, we have
Wi = O(1, = - + V logn
max R1 log Cib Ö(VT).
In the following, verify that fi can represent the information of the input sequences. For any i [n]] with i # j. we have
N
N
Σ (X
Σ
Σ
h(x(1)
Σ
h(x
(D.11)
1=1
ISKEN.X
V 21,
(D.12)
where the last inequality if from Eq Up to now, we have already constructed a feed-forward neural nework f1, which aims to capture the information of the whole sequence. the following, we show that also can construct
forwwrd neural network f2 that can remain the information of individual tokens. Let V denote the set that contains all the tokens appearing in the dataset, that
is, V = (x (i) E [m), l E [N]]. According to Assumption Bal. we know that there exists
1 and < 8 < 1 such that for any 2;, x E V with i * j. we have ||x, x, ll2 8 and | < r. Based on this, we apply Lemma E.4 to V and gain a feed-forward neural network
f2 E (()) Idd + RR) such that
0 < fx(x 10r(nN)200 VTd,
for any i E [n]] and A: E [N]. and
- - 22
(D.13)
23

---

for any i.j E [n] and k [N] with _.k * x Then, we consider integrate f1 and f2 into one single feed-forward neural network, which can both capture the information of the sequence but also that of the tokens. Besides, we also augment the output dimension by one more and pad by which is used as temporary memory. Let Fi R R which takes the input E R and outputs
Fi(x) = (x) f((2),
Since we know that
fi (FFF)))) - R), f2 ((( R),
which means that F1 E FF(O(1), ((V)), R3). We assume that 2 3. By applying Lemma 3 to Fi, know that there exists Transformer T(t) T(D D D hid: H(),, I()), and prompt p(1) DD x (1())
K K2 N such that
(x(1) = ( RI
FI(X .N)
T(l)) pi) p k(
for any E [n]. We have D Od). ( 0(1). D O(1), and M = ( K
O(D!.) H 0(1), L()
in (1) K3 (1) Ö(N Vn). The construction of Ti is completed.
Step 3: Construction of (2) In this step, we aim to construct Transformer (2) to integrate the T2) consists of one self-attention layer and one feed-forward
information of whole the sequence.
layer, that is, (2) = FFF o FSA. Define
0
0
We WK
0
1
and
0
0
0
Wv
0
0 0
As for the weight matrices in FFF, we let
W W₂
which means that FFF just an identity mapping with skip connection. Given any X
X1.1
X1,2
X1.N
X
X2.2
Xa.N
IRNN with the the 3-th element of each column being zero, and
1
24

---

the 4-th element being 1, We know that the output of T given input X is
( = FFF o FSA (A)
(x)
0
0
1
0
0
0
0
1
X
X
1
0
0
0
0
0
0
1
0
ENE[M] X1.6
EnelM XI ENE(N X2,6
0
0
0 0
0
EXE(N) X2,4
x
0
0
0
0
0
n
n
0
0
0
X
ENEIN X1,k
ENEIN X1,
EKEINI 11,
0
0
X
1,2
XI,N
X2,1
X2,2
X2,N
ENE(N) X1,k
ΣNE[N] X1.k
ΣeE(N] X1,k
In particular, let 8 denote the k-th column of the output of (2) given input ('1) which can be calculated as
x(" (x5))) (1).
P
A(X
f((x!)
8k
EREIN (x
We claim that 8) can help to differentiate different tokens or the same tokens in different contexts. For any i.j E [n], and k, I E [N], if X
* (1) according to (D..), we know that
f2(X fz( 2.
( Besides. for any i [n],, and # le [N], if x (8) x we immediatetly have s ( On
the other hand, for any of j E [n]. according assumption B we have ( + x under any permutation. Then, Eq. (D. implies
2
Rm
Thus, by incoporating the above three cases, the difference between any two arbitrary columns of the output of (2) has the following form
2 2 x(0 + 6 x
8
8
(1)
0
i= x
= x 5
21
i
x
25

---

where we use the basic fact
fi 2 {2(x 1,k
)(
(2(x
(
EnErN f((x
EPEINI F((((()
min { -
Σ f(x -
Σ s(x(12)
[E[N]
NE
As for the upper bound of the norm of 8k we compute it
fi
fa(x!)
ENEINI {i(
< (x( + f2(x (2)
Σ (2 AE(N
12m Vi 100 + n [2n V +
s 21rn 4 N28-1vmu
It we let ((2) E RDD. x (
where M 0, and K(2) = K. (i)
0 we have
T p KP K
(3)
Pa pu [r x( (x ),, 8
for any i E [n].
which completes the construction of (2).
( Step 3: Construction of T3)) In this step, we construct T3) to map each sk to its corresponding label yK Let Rs = 20 21rn N28-1 (nN)²- 1 vdd. By applying Lemma (i) for E [n] and l E [N], there exists feed-forward neural network fa Rd - R with width W3 O()) and depth La
to onput- pairs (8) yi,k)
nN lognN max Rs, log C}) = Ö(VnN),
O OlVnN NN log(nN)+ +
such that
fa(s (8)
v
(6)
for any i [n], k E [N].
Then, we apply Lemma 5 to fa and gain a Transformer (3) E T(D! (3) ((3) in
hid H() L())),
and prompt P(3) E RD x M(3) (3) k(
(3)
E N such that
T (3)
([s!))... N 1) = (()
(0)
p R(
pma
for any i E [n]], where ((3) 011,, D out
0(1, (39) = (DD H(3) 0(1), =0)) 0(1)
in and (a) Ö(VnN), K(3) K3 = Ö(N VnN).
Step Put every thing together T == (3) (2)) (1)) with
Based on our analysis above, we have proved that There exist
T()) E TT0(0)000,000)0000,,
T 2) E T(011),011,000))00)0.00
(3) E ((011,,00,,00,0000000)0
26

---

and
p ROldixÓ(V))
p(d ROO))O)))
p(, (O(U))((VNN))
and
KT" K2 Ö(N Vn).
K. K.)) = =0(1,
K( K2 Ö(N vnN)
such that
((3) pi p k k
( pla kg
T()))
pi) p k k( ( (x(1) y0
for any E [n],
which completes the proof of Theorem
D.5 The Limitation a Single ReLU Self-attention Layer
In Theorem 1 the activation function used in each self-attention layer is ReLU. Although ReLU- based Transformers are not commonly utilized practice, empirical studies [Shen ct all 2023 Wortsman all, [[E]] have demonstrated that, with appropriate normalization techniques, they can achieve competitive performance across a range of tasks. The Softmax function converts pairwise dot products into strictly positive attention weights, enabling each token to attend all others in the absence of explicit masking. However, for theoretical analysis, it is often necessary to restrict attention specific tokens. To achieve such deterministic token interactions, existing studies typically replace Softmax with Hardmax function or constrain it to perform column averaging operation. contrast, since ReLU function zeroes out all negative inputs, it provides a more explicit mechanism to control token interactions (see details in [[aaada all 2025)). Nevertheless, this does imply that ReLU-based self-attention theoretically more expressive than its Softmax-based counterpart.
In this following, study the limitation of single layer ReLU self-attention distinguish the same token in different contexts. Specifically, we want to know for any sequential inputs X X e RdxN with x x for some k, I E [N], and (1) + (2) under any column permutation, whether we can find a ReLU self-attention layer F SA such that
F Fx) )..k # F SA (2)
According to Theorem in [Kajitsuka and Sato, 2023), a single Softmax self-attention layer is able to achieve this property. However, in the following, we construct counterexample to show there exist (I) * (2) with x(I) x such that any single ReLU self-attention layer can not differentiate the second token in X (1) and (2).
Fix any d I+ Let (1) (ajv, a28, agv) Rdx3 and ( = (aa a22, (g with Rd and (1, 022, azs, Cta, as E Ryo- Let OR denote the ReLU function and FSA be an arbitrary single self-attention layer with H heads, which has the following form,
H Σ w
F Fsa(X)
X
XOR (W x) (W x) RDiXN
27

---

Through direct verification and according to the definition of ReLU function, the second column of the outputs of FSA given input X (1) and X (2)
are
x = )=
agafon W Σ
W b) w/ - azafon((Wa o
w
R (WW v, W u))
1
a2(af + 0 + aτ) on W w))
H
F FsA(X(2)) ),2 = X (2)
a o) a2azoR w w
+
:22
+ a
(Wl (1)
w w w))
a2 + 0 + a
onl (n( w b))
of + ag = aj + ag. we always have F Fsa( = Fsa((((2) ):2, even if (an, 02 03) + (org, 012, a5).
E
Supporting Lemmas
Lemma E.1 (Theorem C.2 in el 2025)). For any L layer ReLU feed-forward neural network f. which has the following
f(x) Lt. o oR 11.10... L1 LIo0n
La(w) forany any Rd
where Ce(x)= == Wi with We E Raxd, There exists a Transformer T E T(Din: Dout. Drad, H. L) with all the parameters only depend on and Dan Odd), Dout O(d), Drid O(D... H 0()), L O(1) satisfying: for any data points m C [0, 1]d, there exists prompt P RERDiN Pia M such that
Tr.k.,K f(x;),
where K; n (L 1) for i E [n], and M = -O rank(W.)
OOdd (L 1)).
Lemma E.2 (Lemma C.1, [Kajtsuka and Sato, 21224)). Let n, m, d, E N with S m, and 2 of n labels, and a1(1), (m()))))))))))) (m) Rd be set of m imputs such that (0) [0, 1jd with ||x((0) [|2 I r for any i [m], and || -اا0| ô for any i.j E [m]] with i # j. Denote = 20rm28 /Td. Then, there exists a ferdard neural network f Rd - IR with width W = 0(1), depth I.
O 8 1. Let 112) ; y(()) E [C] be
o (Vnlogn V log
n
max (log( max(log (log(R), log(C)) log,())))
such that (z)(0)) = (0) for every E [m], and (()(0)) = for any [m]][n].
Lemma E.3. Let n. m, d, C E N+ with n S m. and r 2 1, < ò < 1. Let y (y()) be a set n labels and (.)).... .... (m) Rd be set of inputs such that (1) [0, 1]d with || ||
for any i im], and (1x x55 1|2 2 8 for any i E [m] with i + j. Denote = 20rm2 Vnd. Then, there exsits a feed-forward neural network f IRd + R with width W (n), depth L
O(max{log R, log C)),
such that (2) = (1) for every i [n], and f (x) 0 for every E [m]])
28

---

Proof of Lemma H In Lemma E we notice that the width of the feed-fon bred-forward neural network constant, while the depth depends on the number of data points be memorized. This result can be transformed into the one where the width depends on the number of data points while depth is constant up to logarithmic factors, Firstly, by applying Lemma Ed to {x(() (
Ji=,, there exists reed-forward neural network f with width and depth both O(1) such that the inputs are mapped R while approximately remains their original distance. Let 211) E R denote f Next, let B E [[v]]]] ([1) be an arbitrary integer. We divide data points 2(1), :... ,x(") into & subsets, each of which has size of B². We denote these subsets as II. 8" We apply Lemma
these subsets respectively to get n. feed-forward neural networks f1, J..... f f each of which satisfies
(y x66) L,, 00
f((x01)
Otherwise.
Let F denote the concatenation of fi S. f fs, which takes input (01) and outputs
f((x(1)
F(x(
(o(1)
There is only one entry of F(x(()) not zero and equals to y( It is clear that f FF()(1), Rd R), and fi FF(O(I), (maxx R, log C)), + R) for any E [+ Then, we know that
F FF O(max(log R, log CT), Rd R),
which completes the proof by letting f = F.
Ler ((1) (n) E Rd be imputs such that x0) 1]d with || 1l2 S r for any i [m], and
Lemma E.4 (Lemma A.2, Narch et all 2021)). Let n E N+ and r 2 5 8
( x 201112 2 8 for any i,j E [m]] with i + j. Then, there exists a feed-forward neural network
I (()), Rd R), such that 0 fxx(0) 10rn25 1on00--ivr for every [N] and
ff((()) f(x(0) 2 for every i, [n] with +
Lemma E.5 (PPak all 20211). Let d E NN. Then, for any finite subset S Rd, there exists a unit vector u E Rd such that
x
x' d'112 S </0 T (x
1 x'll2
SS/2
nd
holds for any x, x' E S.
F
Prompt Tuning Transformers to Exactly Implement Residual Feed-Forward Neural Networks
Residual feed-forward neural network was proposed by [He ct all 2016), which is widely used existing works [Yun all 201 substitute of non-residual feed-forward neural networks. We define the class of residual neural networks as
R(W, L, Rd Rd)
f f F F1(x). Rd
There are three parameters to describe residual neural network. d is the input dimension and the output dimension. F.(x) == æ + WFoR + b:) + 62, where W! E RWxd by RWW and W? E RddW Dy E Rd. F represents the element-wise ReLU function. W called the width of R and I. is called the depth. We provide a lemma that shows any residual feed-forward neural network can be realized by non-residual one.
Lemma F.1. For any residual neural network g E R(W, L, Rd Rd) with some d, W. N then g FF(W 2d, L, Rd + Rd).
29

---

Given any residual neural network E R(W, L, Rd + R which can be written as ( Fr. o Fi (z). Firstly, without loss of generality, we show that ReLU feed-fore forward neural networks can implement Fj. We define
Proof. Our proof basically follows [[ba al 212A5
W
b 0
W1 -
Laxd
E <R(W++d)xd
b
E IR
W +2d
-aadd
W2 = W?? Iaxd
-Iaxa) E Rdx((++2l)
b2 = of E Rd.
is straightforward to verify that
W b1) + + W.
dR(Z)
+ b2
on(-x)
= Wi(oo( ( b()) + [ - oR(- b2
= x W on W x b\) + b¹ = F1
where use the fact that ( a non-residual feed-forward neural network with width W + 2d and depth Similarly, we define fi in the same manner which implements Fú, respectively. In the last, By composing (fiherz) have a seed-forward neural network f = fL fL-10 o fi, and the width of which is W + 2d, while the depth is L, that is, f E FF(W + 2d, L. Rd + R The proof is completed by pointing out that (a) = (ax) for any Rd.
Let fi denote
+b which
We present the extension of Lemma where the residual one.
neural network replaced by
Lemma F.2. Fix any W.d E N+. There exsits a Transformer T E T(D Douts Drid, H, L) such that for any residual ReLU feed-forward neural network g R(W, L, Rd 4 R for some W. L.d. d E N and inputs X ((1) c RAXN There exits prompt P E RPix XM K1, K2 E No such that
TP,K,KK, lo(x -(( for any i [n].
where Din O(W 2d). D Dout 0(1), Drid O(D,), H O(1, L. O(1), and M O((W + d). K1, K2 = O(N
Proof. According FF(W + 2d, L, Rd + (Rd) such that f(x) = g(r)) for any x E Rd. This proof is completed by applying Lemma to f.
Proposition [. there exists feed-forward ReLU neural network f
G Data Memorization with Real Labels
In Section R. we focus on integer labels, which can be regarded as a classification problem. is easy extend our results to real labels by adopting methods in existing literature. As proposed in [Vardi all 2021], when the output range is bounded, we can partition the output range into e-length intervals, each interval can be treated as class. Then reduce the problem to data memorization with ( classes. However, this method can only achieve e-crror instcad zero loss. Although [Hu Cal 202AI] show that there exists trade-off between the width and depth of neural networks, their results are established on e-error. In this section, we first show that it is easy to build a ReLU neural network with width and depth 1, which maps input vectors to real labels. Our proof is modified from [Jio et all 20267 where we use a ReLU neural network instead of a residual neural network.
Lemma G.I. Given any d, E N Let ()), ... (a) g())) C Rd x [0, 1] be the input- label pairs with [|ax(0) ( 21 2 8 for every i + E [m] and || l|2 S f every E [n]. Then, there exists a feed-forware neural network f FF(((()) 0(1), Rd - R) such that f (x)(0) = ( for any i [n].
30

---

Proof. According to Lemma + there exists v E Rd such that a v are distinct. Let K > be determined later. We define
Ko (o(
w = K
1 2
6.Th
- Ku x(11)
(w y1 -2,1), 6,¹h 0.
KvJar x!1) +1
where wi IRaxd b. E R w/
Rlx3 and b,²² R.
is straightforward to verify that
w WF ( x b..)) + +b,²²
yy TR(KK (x (x-x - -1) 2oR(Ku -x-x (x-x toRKKT (x- x00) + +1)
= I
where (xx) satisfies I (x())) = and ((x) = 0 if lf x(0)) 2 1/K. We choose K >
minsgy 10 (1w5))=a1) Define
(1)
(
6
( = (W W ( 0,
6
where (11) p3axd 6(0) E R3h, (2) E RIx3n ((2) E R. Let
f(x) W( (1))))))) b()) ((2)
(((0)
The proof is completed by verifying that f(x(11) = ( f FFF(O()) Rd R).
Next, we present the trade-off between the width and depth of the feed-froward neural networks that are constructed to memorize datasets with real labels. [Yun et all 2013, their results rely on
piecewise linear functions which yield approximation error by ReLU function and et 2024] also face the same problem. Our following result is novel since it does not cause any extra error and exactly achieves the zero loss.
Lemma G.2. Given any d, n E Zt. Let (1) (1(())y)11) ()))),.... (wx!)) , y()) C Rd x [0, 1] be the input- x000 2 8 for every + [m] and [|x) S r for every [n]. Then,
label pairs with there exists a fordrd neural network f FF(((L),, O(n), Rd + R) such that f(x = (()
for any i [n].
Proof of Lemma + According to Lemma DEL there exists feed-forward neural network F
Rd + R with width O(1) and depth O(1) such that [+) F(x(1)) 2 2 and F(x(1)) 2 0 for
any * j [m]. Let (f) denote the output of F given input (1) fx) = x w on (w(())
b(*) b) where
(x(1) -1
1
(1) =
-z(1)
: = (g() (6) - 4) 22,
6.0 = 0.
(1(())
+
31

---

and w/ E Rax1 b10 ER., W E RIxs, 6y E R. is direct to verify that
f(z)= + oR ( x + b + 6.¹
= x + (g(0) - x - 4) 0n(z - x11) - 1) - 1-20n22 - x10) + onlo -x00
x 100+11 +1)
-10( -4 -4 if = 11),
-1x 1
if x 000 21.
Define (x)) = 000000(0000000000 +0) +4. Let f on In- E R(3 R).
Since y()) E [0, 1). we can verify that
f(x())= = y for any i E [n].
By applying Lemma to f. there exists a feed-forward neural network f E FF((5 1 -> R) such that f((x(0) = y for any i [m]. Let f denote the composition of f and F. is clear that E (F())(())(())) Rd + R, which completes the proof.
Note that in order to obtain the similar trade-off between prompt length and the number of intermediate steps in Section G. we need to prove that there exists a ReLU neural network with depth Ö(vn) that can memorize n data points with real labels. However, we only derive weaker version with ((n) depth, which is still an open problem for future research, We provide similar Theorems of prompt tuning Transformers for data memorization with real labels without proof since the proof' are basically the same as that of Theorem 3.].
Theorem G.I. Fix any d E N+ There exists composition of three Transformers T = (3 ((a) D(i)
T(2) O (1) with T()) E T(D(
out hid: H L such that for any sequence of input-oulput
pairs (x(), y (1)), (x),,, (()) RRxN x [C]IIN satisfying Assumption 3. and N
there exist prompts p(ù) RD M and K(O .K2") E N such that
Tr(3) P() x(1) k(a)
(
x()) xx)) o (T(
p (() (x()) = yy for any i E [n],
where ( = (d), (1) = 0(1), 1 hid (DD.), H0O = 0(1), 7 = 0(1), and M
(n). K K2 = O(N - n). for 1,2,3
Theorem G.2. Fix any d, n E N There exists a composition of three Transformers T = (3) ((1)
(22) (1) with ( E ((D
in ((i) outr hid: Hú, I(),, such that for any sequence of input-outuut
pairs (x(), ()) ......,.......... (*)
(n) (m) R x [C]1>N satisfying Assumption and N
there exist prompty p(() E RD xM and K(O ..( N such that
(x(3)
(22)
x(") .K!') o f()
ka,,kl xx (x(1) yy for any E [n],
P(3 x x
where D = O(n V d). D in
out = 0(1). hid = O(D.), H00 = -(1), L0) = O(1), and
M( On), K(O) K(O) O(N), for 1,
H Low-Rank Bias of Prompt Tuning
Deep neural networks, despite their enormous parameter counts, often display an implicit preference for learning functions of low effective complexity. One notable manifestation of this phenomenon is the low-rank biasthe empirical tendency of neural networks to produce representations, weight matrices, or inputoutput mappings that are approximately low-rank, even in the absence of explicit rank constraints. This bias reflects a form of structural simplicity that naturally arises from standard optimization and regularization procedures such as stochastic gradient descent, weight decay, and early stopping [Kunasekar all, 2018. Huh et all 2021]
In the case of linear models, theoretical analyses have shown that gradient descent implicitly minimizes the nuclear norm, thereby converging to low-rank solutions. This phenomenon extends
32

---

to deep nonlinear networks, where empirical studies reveal that the singular value spectra of trained weight matrices and activation covariances decay rapidlysuggestng that most of the representational variance is captured by a small number of dominant modes. Similar low-rank patterns also emerge in self-attention mechanisms, where effective attention maps are often confined to low-dimensional subspaces.
From a theoretical perspective, the low-rank bias can be viewed form of implicit regularization, whereby the dynamics of stochastic gradient descent favor smoother and more compressive mappings. This implicit regularization provides partial explanation for the strong generalization ability of overparameterized neural networks: low-rank solutions reduce model complexity and improve robustness input perturbations. However, this same bias can also limit expressivitytasks requiring high-rank or highly entangled feature interactions may be more difficult to capture under such constraints.
An equally important factor lies in the geometry of the data distribution itself. Real-world data-such images, language, audio, and other structured signals-typically lie on near low-dimensional manifold embedded within a high-dimensional ambient space. This manifold hypothesis implies that, although input representations are high-dimensional, the intrinsic degrees of freedom governing them are much smaller. Neural networks trained via gradient- optimization may thus naturally adapt to this underlying manifold structure, leading to the emergence of low-rank patterns in their learned parameters and representations.
In the following, we prove that under certain assumption, prompt tuning does can capture the low- rank structure in the dataset, which leads to a reduction in prompt length. The prompt length does not depend on the number of data points to be memorzied, while mainly determined by the number of classes.
Theorem H.1. Fix any n, d E N+ There exists a Transformer T E TT(Din: Douts Drid= H, L) such that for any sequence of inpul-oulpul pairs (xx(2,, ,y y(")),... (x(t), ()()) E Rd x [C] satisfying .yfm)) have at most m different values with n = m k.
Assumption 3.1 and we assume that y ......" Without loss of generality, we denote the m different values as v(1), ,... _u(m), Define the set y(t)
(x) y05) = }. which contains all the inputs whose labels are the same. We assume that for any i E [m], there exsits vector 260) E Rd such that for any x E 7(1, we have x = c. z(0) for some distinct e Ryo- Then, there exist prompt P E RDax XM and K N+ such that
(x(,, = =y(²) for any i [n],
where Din O(n), Dout O(), Drid O(Din), H 0(1), L 0(1), and M 0m)), K = 0(1).
Proof of Theorem (x: (n) (()) can be divided into m subsets. in each of which, labels are the same. Without loss of generality, we assume that all the (0) are listed in order in terms of their labels and
According our assumption, we know that the whole dataset
(I) (1)),,
we let æ (0), According to Lemma E there exists Rd such that v x() are distinct.
Let K > be determined later. We define
KU (1)) c(1)
w!Oh = K
1 TT.
b(")=
- Ko Ta(0)
W cli) y (9, 22,1), b13) = 0.
KoTx(1) + cc())
where ( Raxd 600 E R$. w/
E Rlx3 and (2) R.
It is straightforward to verify that
w (2) (n( x x+++ b(4) 6!2)
c(1) (0)
on(Ko (x x()) (0)) -2on(Ko (0)) + ton(Ko (x (x-x(()) + cl0))
cte) (1())))))))
33

---

where [((x) satisfies (((x()) clt) and (x)) 0 v
(x x z0)) 2 1o
Let c
max(]c()) |cl We choose K
o (w/s) 211i Define
2c
minug
W1
w
b(
w = (
W
b 0,
W
bn
where ( E Raaxd (())
E R8n ( E Rix3n ((2) E R. Let
f(z) on W x1 b(t) + b(2)
on
((x).
is direct verify that f fxx(1) = y0) and f E FF((O()) Rd + R) by using the fact on(-c(() + (c( = (8)
|c(0]
min v T (x xx(1)]| |c(() if)
a vx x (0)) min v0 (xli) - (0))
(x(1)xx(1)
2c
K
As for the ranks, we point out that
rank (W(1) (b(1) I 3m.
rank (alk((())) 1 1.
According Lemma D and Lemma
G there exsits
Transformer T
T(Din Dout, Drid; H, L). prompt P Rin XM
and K E N such that
T. (x = y0)
where Din = On). Dout = O(1), Diad = O(Di.) H = 0(1), L = 0(1), and M = (m)).
K O(1). The proof is completed.
I Experimental Details
I.1 Setup Details
All the experiments are conducted on one NVIDIA T4 GPU. Our code is based on standard Py PyTocch modules.
Figure II We randomly sample 1000 samples from SST-2 dataset [Socher et all 2 [ which are
truncated length of 8. The length of the prompts prepended the inputs also 8. Number of training epochs is 1000, leanring rate is 0.005. Optimizer is Adam [Loshehloov and Hatter, 2017] We the Roberta-base (12 heads and 12 layers) implementation of Hugginface WWoffetall 2019). We plot the average attention patterns over all the training samples of heads in the 10-th layer.
We randomly sample 1600, 2500, and 3600 data points from IMDb dataset [Maas et all 2010 and the corresponding prompt length is set to be 40, 50, and 60, which is roughly the square root of the dataset size. Number of training epochs is 100, learning rate is 0.001. Optimizer is AdamW. We use a two-layer hand-crafted Transformer architecture, in which the activation function in each self-attention layer can be ReLU or Softmax, number of heads is and hidden dimension is 4 times the embedding size 512.
Table M
Table We randomly sample 2000 input sequential data ( [R6xx8 from distribution 1(-4.4). Then, we initialize a ReLU feed-forward neural network with 8 layers and width 32 following three strategies: default initialization strategy PyTorch, replacing [W. b) in each layer by rank-1 matrix, and initializing low-rank [W, b) together with rank-1 embedding layer. To achieve low-rank structure, we use the fact that rank(AA S min(ran (rank())) rank Number of training epochs is 100, learning rate is 0.001. Optimizer is AdamW. The backbone is one-layer one-head Transformer with ReLU activation, embedding size 128, hidden dimension 128. Prompt length is set to be 10, 20, 30 and 40.
34

---

Table 3 We randomly sample 1600 data points from IMDb dataset the set the prompt length to be 40. The backbone a two-layer ReLU Transformer with random word embeddings. Number of training epochs is 100, learning rate is 0.001. Optimizer is AdamW. To initialize low-norm FFN, we utilize the SVD of W and modify spetral norm. To initialize low-rank Wv, WK. Wo, q. we set them to be multiplication of two low-rank matrices.
1.2 Additional Experimental Results
In this section, we present some additional experimental results.
Figure 2: Attention patterns from head to head 6 of random ReLU, Softmax Transformer averaged over 100 samples from IMDb dataset, using word embeddings from T5-small. The input sequence length is 16 where the first 8 tokens prompt tokens and the remaining 8 data tokens. The first row displays attention patterns of random Softmax Transformer, and the second row corresponds to the ReLU Transformer. Due the normalization effect in Softmax function, the attention weights on data tokens in the random Softmax transformer are diluted by the presence of prompt tokens. In contrast, the random ReLU Transformer can assign significantly larger attention weights to data tokens.
Figure 3: Attention patterns from head to head 6 of random ReLU, Softmax Transformer averaged 100 samples from IMDb dataset, using random word embeddings. The input sequence length 16 where the first 8 tokens are prompt tokens and the remaining are data tokens. The first row displays attention patterns random Softmax Transformer. and the second row corresponds the ReLU Transformer. Both Softmax and ReLU Transformer tend to assign equal attention weights to prompt tokens and data tokens.
35

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (12 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist one of the factors in their evaluation. While "[Yes] is generally preferable provided proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
"[No] ", perfectly acceptable to answer "[No]
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist".
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and/or introduction should clearly state the claims made, including the contributions made the paper
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
36

---

Justification:
They are mentioned separatly in the conlusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model -ell-speciiication asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of community. Reviewers will be specifically instructed to not penalize honesty conceriing limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
All detailed proof and assumptions are provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All the experimental details reproduce the results are mentioned in the Appendix.
37

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), relcasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We only use public datasets this paper. The code will be publically available upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ mnips.cc/public/gu.dee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
38

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
We have mentioned all the training details and evaluation settings in the Appendix.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: All of our experiments are all for proof-of- We only focus on whether the experimental results are consistent with our mathematical theory.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, statistical significance tests, at least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our experiments are not computationally demanding and our paper not an experimental study.
39

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
All code of ethics are followed.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
There is no societal impact of this work since this paper is mainly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
40

---

Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode..w.......ooo.oooooo.o.... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
41

---

Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsoureing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research
with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs have not been used for constructing the core, important, original components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard compontts..
Please refer to our L.LM policy [tteg://eeerrrseeccc//ooeererees for what should or should not be described.
42


Reviews:
[{"review_id": "NQLtOLWgoq", "reviewer": "Reviewer_QVye", "summary": "This theory paper studies the data memorization capabilities of the prompt tuning technique on Transformers. It builds on prior work which, under some conditions, emulates ReLU nets using transformers to finite precision. The authors extend on this work by providing novel theoretical results to narrower ReLU nets, an upper bound on the prompt length for which a constant-size transformer can memorize data, and empirical evidence that the theoretical results work in practice. They further elucidate that this prompt length can be shortened if the ReLU weights are low rank.", "questions": "- What practical insights can we take away from the theoretical findings here that would be useful to the average prompt tuning user?\n- Can the authors elaborate more on the practical implications of the assumptions?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- the paper marks a notable and novel advancement over prior work\n- there is experimentation provided to support the theoretical results\n- the authors propose an upper bound which, to my knowledge, has not been proposed before in this line of work\n- the authors investigate additional cases of low-rank ReLU nets which has not been studied before in this line of work\n\nWeaknesses:\n- This introduction of this paper is written as if the reader is already familiar with prior work. This can be quite confusing and additional context should be given to motivate the work. Furthermore, a significant portion of contributions are in the appendix which should have otherwise been in the main body.\n- It is unclear what, if any, practical takeaway there is here for those who are still using prompt tuning today.\n- this paper makes assumptions (such as in 4.1). The extent to which these assumptions further deviate the practicality of this work is unclear and should be discussed.\n\nWhile I am not an expert here, this paper reads rigorous and clearly marks an advance over prior theory, hence my tepid accept. I would strongly recommend that the authors make a case for why this work is relevant and practical outside of theory.", "was_revised": true, "final_justification": "The paper proposes a novel theoretical insight on data memorization in prompt tuning, extending on past work. During the discussion period, the authors sufficiently addressed concerns, particularly those around practicality and empirical evaluations.", "rebuttal": "Thank you for taking the time to review our paper and sharing your insightful comments. We will address your questions below.\n> W1. This introduction of this paper is written as if the reader is already familiar with prior work. This can be quite confusing and additional context should be given to motivate the work. Furthermore, a significant portion of contributions are in the appendix which should have otherwise been in the main body.\n\nOur work is closely related to two fields: Data Memorization and Prompt Tuning. Data Memorization aims to study the ability of neural networks to achieve zero loss on discrete datasets while Prompt Tuning requires designing or learning different prompts that can help Transformers adapt to downstream tasks. Data Memorization is important both from a privacy perspective [1], and as a stepping stone towards quantifying the model's ability to generalize to new data [2, 3]. Besides, to theoretically understand the superior performance of Transformers, some works also focus on their approximation ability [4]. Since data memorization is usually a key component to derive approximation results, it is reasonable to study Transformers' data memorization ability to verify their  representational capability. Prompt tuning tries to enable fixed pretrained Transformers to handle different tasks with corresponding prompts. Here, we combine Data Memorization and Prompt Tuning to provide a theoretical analysis of the success of prompt tuning.\n\n> W2 and Q2. What practical insights can we take away from the theoretical findings here that would be useful to the average prompt tuning user?\n\n- The first practical insight is that longer prompts are more informative. Since each prompt in our work stores the information of the target ReLU feed-forward neural networks, whose width and depth decide the prompt length. This means that longer prompts are more powerful because of the expressive ability of wider or deeper ReLU neural networks [5]. Some empirical studies [6,7] are consistent with our results.\n- Fixed Transformers with different prompts can adapt to different tasks. In Proposition 3.1,  the architecture and parameters of the constructed Transformer only depend on $\\max(W,p)$, where $W$ represents the width of the ReLU feed-forward network that will be simulated and $p$ is the data dimension. Moreover, we show that a small constant-width ReLU feed-forward network can achieve data memorization for non-sequential data, which leads to the data memorization ability of a fixed Transformer. Here, a fixed Transformer can be viewed as a pretrained Transformer with the parameters frozen, which aligns with the real-world setting of prompt tuning. \n- Design prompts with large spectral norm. According to the definition of prompts in (2.6), $S$ is a large enough positive constant, which means that the constructed prompts have a large spectral norm. This phenomenon has been observed by [8].\n\n- It is important to note that our theoretical results are all constructive rather than prescriptive, meaning that other factors like the optimization dynamics and computational resources should also be considered in practice.\n\n> W3 and Q3. Can the authors elaborate more on the practical implications of the assumptions?\n\nFirstly, we would like to note that the $(r,\\delta)$-separateness (see Assumption 4.1) is a standard assumption in the study of data memorization [9,10,11]. Since in the task of data memorization, we consider a discrete dataset with finite samples, and any discrete dataset is naturally $(r,\\delta)$-separated, so this assumption is loose. In terms of the \"consistently labeled\" assumption in Theorem 4.1 and 4.2, we note that this assumption is necessary since a Transformer is a permutation equivariant function (please refer to claim 1 in [4] for detailed proof). We say a function $f: \\mathbb{R}^{d\\times n}\\rightarrow \\mathbb{R}^{d\\times n}$ is permutation equivalent if for any permutation matrix $P$, we have $f(XP) = f(X)P$. In other words, if we permute the columns of the input $X$, the columns of the output $f(X)$ are permuted in the same way. Let $(Z^{(1)},y^{(1)})$ and $(Z^{(2)},y^{(2)})$ be two input-label pairs and $Z^{(1)}=Z^{(2)}$ up to permutations. Suppose that $Z_{:,i}^{(1)}=Z_{:,j}^{(2)}$ for some $i,j\\in [n]$ while $y_{:,i}^{(1)}\\neq y_{:,j}^{(2)}$, we can prove that there exists no Transformer $f$ such that $f(Z_{:,i}^{(1)})= y_{:,i}^{(1)}$ and $f(Z_{:,j}^{(2)}) = y_{:,j}^{(2)}$, which means that any Transformer fails to memorize $(Z^{(1)},y^{(1)})$ and $(Z^{(2)},y^{(2)})$. In [10], they define a special positional embedding to break the permutation equivariant limitation. We will provide a discussion about this in our final version.\n\n\n\n\n## References\n\n[1] Carlini and Nicholas. Extracting training data from large language models.\n\n[2] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization.\n\n[3] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: where bigger models and more data hurt.\n\n[4] Yun, Chulhee, et al. Are transformers universal approximators of sequence-to-sequence functions?.\n\n[5] Lu, Jianfeng, et al. Deep network approximation for smooth functions.\n\n[6] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners.\n\n[7] Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. (2022). Rethinking the role of demonstrations: What makes in-context learning work?\n\n[8] Wang, Yihan, et al. Universality and limitations of prompt tuning.\n\n[9] Kajitsuka and Sato, Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators? ICLR 2024.\n\n[10]  Kim et al., Provable Memorization Capacity of Transformers. ICLR 2023.\n\n[11] Vardi et al., On the Optimal Memorization Capacity of ReLU Neural Networks. ICLR 2021."}, {"review_id": "tkC7Hcjx4p", "reviewer": "Reviewer_cRMN", "summary": "This paper investigates how much data a constant-size Transformer can memorize when it is adapted only through prompt tuning. Building on and generalizing earlier work, the authors prove that prompts of length $\\tilde{O}(\\sqrt{nN})$ are sufficient for a Transformer to memorize $N$ sequences of length $n$, even when the simulated ReLU network has only constant width. They also provide a theoretical trade-off between prompt length and the number of autoregressive steps required, and they offer appendix-level experiments suggesting that low-rank structure in the target network can further shorten prompts.", "questions": "1. A compact table showing memorization accuracy versus prompt length—and a simple plot of the length–efficiency trade-off—would greatly strengthen the empirical link to your theory.\n\n2. Could you discuss concrete datasets or tasks where token-wise separateness and consistent labeling approximately hold, and comment on what happens when they fail?\n\n3. A small table contrasting your new upper bounds with those of Kajitsuka & Sato (2024), Hu et al. (2024), and Nakada et al. (2025) would help readers quantify the improvement across different regimes.\n\n4. Why does accuracy peak at prompt length 50 but drop at 60 as observed in Table 8? Please clarify why a longer prompt does not monotonically improve accuracy. A short analysis or ablation would make the empirical trend more convincing.\n\n5. On lines 208–209 the displayed equation should end with a comma, and the following where should start with a lowercase “w” because it continues the same sentence.", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper improves on prior work by providing the first explicit upper bound on prompt length for sequence-to-sequence memorization and by establishing a clear trade-off between prompt length and efficiency. These contributions extend Nakada et al. (2025) to constant-width networks and move beyond earlier works that offered only exponential lower bounds or relied on wide feed-forward layers.\n\n2. Rigorous and well-documented analysis.\nFormal definitions, lemmas, and proofs are presented with care, and the architecture of the prompt construction is spelled out in detail. A thorough Related-Work section situates the contribution within both theoretical and empirical literature, helping readers see exactly how this work fits into the evolving prompt-tuning landscape.\n\n3. By showing when large embedding dimensions are unavoidable and how low-rank structure can shrink prompt length, the paper offers concrete guidance for designing prompt-tuning strategies. The results also strengthen the argument that fixed, pretrained Transformers can solve new tasks through prompts alone, a point of practical relevance for resource-constrained adaptation.\n\n**Weaknesses**\n\n1. All substantive experiments are relegated to the appendix; the body contains no figures, tables, or quantitative results. This omission makes it hard for readers to gauge how well the theory matches practice and does not meet common expectations for reproducibility.\n\n2. Theoretical guarantees hinge on strong assumptions such as token-wise separateness and consistent labeling, yet the manuscript offers no empirical check on how often these assumptions hold or how performance degrades when they do not. Consequently, the practical impact of the results remains unclear.\n\n3. Dense notation, many nested definitions, and the absence of illustrative diagrams or worked examples make the paper hard to follow for non-experts. Moreover, the intricate prompt design is not accompanied by a step-by-step example, which would help readers replicate the construction.", "was_revised": true, "final_justification": "The paper gives a clear theory result by showing the first upper bound on prompt length for constant-size Transformers and explaining the trade-off between prompt length and efficiency. As reviewer xVXV and I both said, the paper needs to be reorganized to make the theory and experiments easier to follow.", "rebuttal": "We thank the reviewer for their thorough response! We address some of your concerns below.\n\n> **W1 and Q1. All substantive experiments are relegated to the appendix; the body contains no figures, tables, or quantitative results. This omission makes it hard for readers to gauge how well the theory matches practice and does not meet common expectations for reproducibility. /  compact table showing memorization accuracy versus prompt length—and a simple plot of the length–efficiency trade-off—would greatly strengthen the empirical link to your theory.**\n\nWe apologize for the organization of this paper, and this will be modified in our revised version following your comments. We provide a brief outline of our experiments here:\n\n- Table 1 and Table 2 study the Transformer simulation for deep ReLU neural networks and shallow ones, finding that deep neural networks are much easier to simulate than shallow ones. This experiment supports Proposition 3.1 in our work.\n\n- Table 3 explores the relationship between the Transformer simulation for shallow ReLU neural network and the embedding size, finding that the embedding size becomes the bottleneck rather than the prompt length when simulating shallow ReLU neural networks. This supports our Remark 3.4. \n\n- Table 4 and 5 show that the prompt length is sharply reduced when simulating ReLU neural networks with a low-rank structure in the weight matrices. Only $1/10$ prompt length is needed to achieve similar performance. This verifies our discussion in Section G.\n\n- Table 6 and 7 compare the performance of prompt tuning and training from scratch on a real-world dataset when the embedding size is chosen to be $256$, finding that prompt tuning can only achieve inferior performance. This also verifies our discussion in Section G. This supports our Theorem 4.1.\n\n- Table 8 and 9 compare the performance of prompt tuning and training from scratch on a real-world dataset when the embedding size is chosen to be $16$, finding that prompt tuning performs better than training from scratch when the embedding size is small.\n\nHere, we provide the table showing the accuracy versus prompt length. We will reorganize our paper and provide more experimental results in the main text following the reviewer's suggestions.\n\n| Embedding size |   Prompt length | Acc |\n|--------------------|-------------------|------|\n|256| 0| 1.0000|\n| 256| 40| 0.9800|\n| 256| 50| 0.9756|\n| 256| 60| 0.9731|\n|16| 0| 0.8281|\n| 16| 40| 0.9206|\n| 16| 50| 0.9381|\n| 16| 60| 0.9350|\n\n\n\n> **W2 and Q2. Could you discuss concrete datasets or tasks where token-wise separateness and consistent labeling approximately hold, and comment on what happens when they fail?**\n\nFirstly, we would like to note that the $(r,\\delta)$-separateness (see Assumption 4.1) is a standard assumption in the study of data memorization [9,10,11]. Since in the task of data memorization, we consider a discrete dataset with finite samples, and any discrete dataset is naturally $(r,\\delta)$-separated, so this assumption is loose. In terms of the \"consistently labeled\" assumption in Theorem 4.1 and 4.2, we note that this assumption is necessary since a Transformer is a permutation equivariant function (please refer to claim 1 in [4] for detailed proof). We say a function $f: \\mathbb{R}^{d\\times n}\\rightarrow \\mathbb{R}^{d\\times n}$ is permutation equivalent if for any permutation matrix $P$, we have $f(XP) = f(X)P$. In other words, if we permute the columns of the input $X$, the columns of the output $f(X)$ are permuted in the same way. Let $(Z^{(1)},y^{(1)})$ and $(Z^{(2)},y^{(2)})$ be two input-label pairs and $Z^{(1)}=Z^{(2)}$ up to permutations. Suppose that $Z_{:,i}^{(1)}=Z_{:,j}^{(2)}$ for some $i,j\\in [n]$ while $y_{:,i}^{(1)}\\neq y_{:,j}^{(2)}$, we can prove that there exists no Transformer $f$ such that $f(Z_{:,i}^{(1)})= y_{:,i}^{(1)}$ and $f(Z_{:,j}^{(2)}) = y_{:,j}^{(2)}$, which means that any Transformer fails to memorize $(Z^{(1)},y^{(1)})$ and $(Z^{(2)},y^{(2)})$. In [10], they define a special positional embedding to break the permutation equivariant limitation. It is still unclear that whether their method can be integrated into our work. We will provide a discussion about this in our final version.\n\n> **W3. Dense notation, many nested definitions, and the absence of illustrative diagrams or worked examples make the paper hard to follow for non-experts. Moreover, the intricate prompt design is not accompanied by a step-by-step example, which would help readers replicate the construction.**\n\nThank you for your suggestions, which we believe will make our paper clearer and easier to follow. In the revised version, we will provide a toy example to show how these prompts are constructed step-by-step, and a notation table in the Appendix to facilitate understanding. Briefly speaking, the prompts we designed store the information of the ReLU feed-forward to be simulated and the position information, which decides the interaction between the prompts and data to be memorized.\n\n> **Q3. A small table contrasting your new upper bounds with those of Kajitsuka & Sato (2024), Hu et al. (2024), and Nakada et al. (2025) would help readers quantify the improvement across different regimes.**\n\nOur problem setting is different from all existing works. [1] studied the data memorization ability of Transformers with prompts. However, they results can only achieve $\\varepsilon$ error instead of zero error and they assume that there exists a sequence-to-sequence continuous function $f$ such that $f(Z^{(i)}) = y^{(i)}$ for each input-label pair $(Z^{(i)},y^{(i)})$, which is a stronger assumption that ours. [2] was the first to show that a Transformer with different prompts can simulate/ exactly compute different ReLU feed-forward neural networks, and did not consider Transformers' ability to deal with sequential data. Besides, [3] studied the problem of how efficiently Transformers can memorize datapoints with a minimum number of parameters. Their results show that the number of parameters is upper bounded by $\\tilde{O}(\\sqrt{nN})$, which aligns with the prompt length in our work. Their work is not based on the prompt tuning technique, and the Transformers they constructed rely mostly on large feed-forward layers while only one self-attention layer is used, making it hard to isolate the role of the attention mechanism itself. Table 1 in [3] provides a detailed comparison among existing works with respect to the number of parameters that are needed to memorize $N$ datapoints. Since our work does not focus on the number of parameters, we can not find a place for our work in that table. But one thing is certain is that [1] only provides a lower bound of prompt length needed for data memorization, we are the first to prove an upper bound.\n\n> **Q4 Why does accuracy peak at prompt length 50 but drop at 60 as observed in Table 8? Please clarify why a longer prompt does not monotonically improve accuracy. A short analysis or ablation would make the empirical trend more convincing.**\n\nWe provide a possible explanation here: The performance of prompt tuning depends on many aspects: model size, prompt initialization, optimization, task complexity ……. In our work, we theoretically prove that Transformers with prompts can memorize any set of datapoints if the prompts are sufficiently long. Our proof is constructive rather than prescriptive for training, meaning that standard gradient-based methods may not always efficiently find the required weight configuration so the gap between theory and practice is inevitable. Besides, long prompts may introduce extra information and disturb the optimization process. Figure 3(a) in [4] shows that longer prompts may result in a decline in performance and models with different number of parameters present different tolerance to long prompts. Similar results can be found in Figure 4 in [5] and Table 2 in [6]. In order to fully understand how prompt tuning works, it is necessary to consider other factors, like optimization. \n\n> **Q5. On lines 208–209 the displayed equation should end with a comma, and the following where should start with a lowercase “w” because it continues the same sentence.**\n\nWe apologize for this typo, and this will be corrected in our revised version.\n\n## References\n\n[1] Hu, Jerry Yao-Chieh, et al. Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency.\n\n[2] Nakada, Ryumei, et al. A Theoretical Framework for Prompt Engineering: Approximating Smooth Functions with Transformer Prompts.\n\n[3] Kajitsuka, Tokio, and Issei Sato. On the optimal memorization capacity of transformers.\n\n[4] Lester, Brian, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning.\n\n[5] Li, Xiang Lisa, and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation.\n\n[6] Joon-Young Choi, Junho Kim, Jun-Hyung Park, Wing-Lam Mok, and SangKeun Lee. SMoP: Towards Efficient and Effective Prompt Tuning with Sparse Mixture-of-Prompts."}, {"review_id": "N7nV1Wrzte", "reviewer": "Reviewer_URsx", "summary": "The paper studies the memorization capacity of transformers using prompts. It shows that a constant-size transformer with ReLU attention can memorize $N$ token-wise separable sequences of length $n$, using prompts of length $\\tilde{O}(\\sqrt{nN})$.", "questions": "Question:\n\n- Regarding the statement *\"if the target ReLU neural network presents the low-rank structure, the required prompt length is sharply reduced\"*:\n  - Is this an empirical observation without a formal proof?\n  - Since the ReLU network is constructed from the data, what does the assumption of a \"low-rank structure\" imply about the underlying data to be memorized?\n- It would be helpful to include a brief proof sketch in the main text to aid understanding.\n\n- minor comments:\n  - The term *Autoregressive Generalization* is somewhat unclear to me, as it is not obvious what is being generalized in this context.\n  - In the abstract, it is claimed that *“a constant-size Transformer with prompts ... can memorize any $N$ input sequences of length $n$.”* However, as stated in the main text, this requires Assumption 4.1 (token-wise separability). I suggest clarifying this condition in the abstract to avoid overstatement.\n\nPlease also refer to the weaknesses. I am happy to revise my score based on the authors’ rebuttal and the discussion with other reviewers.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper provides a theoretical analysis of the memorization capabilities of transformers with prompt tuning.  It shows that a constant-size transformer with ReLU attention can memorize any amount of data, as long as the prompt length grows in the order of $\\tilde O(\\sqrt {nN})$. The observation that the required prompt length can potentially be reduced in the presence of low-rank structure is also interesting.\n\nWeaknesses:\n\n- The proof technique primarily builds on two existing results: (1) the simulation of ReLU neural networks via prompt-tuning transformers [Nakada et al., 2025], and (2) the use of $\\tilde{O}(\\sqrt{nN})$-size deep ReLU networks to memorize $N$ labels [Kajitsuka and Sato, 2024]. As a result, the technical originality appears somewhat limited. It would be helpful if the authors could more clearly explain the core novelty of their contribution.\n- Using prompt tuning as a means to memorize arbitrary data seems somewhat unnatural. It would strengthen the paper to include a discussion of real-world scenarios where such a setup is relevant, to better motivate the problem.\n- The results are derived specifically for transformers with ReLU attention, rather than the more commonly used softmax attention. This limits the applicability of the findings to standard transformer architectures.", "was_revised": true, "final_justification": "After considering the rebuttal, I have updated my score to 4. My recommendation is based on the following points:\n\nSignificance: The authors explained the reasonableness of their assumptions (e.g., ReLU attention) and discussed how their setting relates to real-world scenarios.\n\nTechnical contribution: The authors extended the results of [16] to a more general case where the width of the simulated ReLU network can be a small constant. While this is a meaningful step, the novelty remains somewhat limited.", "rebuttal": "Thank you for taking the time to review our paper and sharing your insightful comments! We address some of your concerns below.\n\n> **W1. The proof technique primarily builds on two existing results: (1) the simulation of ReLU neural networks via prompt-tuning transformers [Nakada et al., 2025], and (2) the use of $\\tilde{O}(\\sqrt{nN})$-size deep ReLU networks to memorize $N$ labels [Kajitsuka and Sato, 2024]. As a result, the technical originality appears somewhat limited. It would be helpful if the authors could more clearly explain the core novelty of their contribution.** \n\nOur contribution can be summarized as follows:\n\n- We theoretically verify the expressive ability of prompt tuning from the data memorization perspective. To our best knowledge, [1] was the first to study this problem. However, their results focus on $\\epsilon$ error rather than zero error and they only provided the lower bound of the prompt length needed for data memorization. We are the first to give an upper bound.\n\n- We theoretically prove that there exists a prompt length and computational efficiency trade-off. Longer prompts lead to less iterations in the autoregressive algorithm.\n\n- We provide a possible explanation of why prompt tuning is efficient in terms of prompt length by connecting prompt tuning with the low-rank structure in the ReLu feed-forward neural networks that are simulated.\n\n- We extend the results in [16] to a more general case where the width of the ReLU feed-forward neural network to be simulated can be a small constant and can be smaller than the data dimension, which is not trivial. Besides,  we show that ReLU Transformers can implement contextual mapping under the prompt tuning setting.\n\n> **W2. Using prompt tuning as a means to memorize arbitrary data seems somewhat unnatural. It would strengthen the paper to include a discussion of real-world scenarios where such a setup is relevant, to better motivate the problem.**\n\n- Data Memorization is closely related to data privacy issues. If prompt tuning has the data memorization ability, this means that prompt tuning is not inherently privacy-preserving. Proper safeguards (e.g., DP, federated learning) should be applied to ensure data privacy when using prompt tuning in sensitive applications. Some empirical works have studied this problem [6,7,8].\n\n- Data Memorization studies the expressive ability of Transformers to achieve infinite error on discrete datasets, which is an extension of the finite precision approximation results provided by [2,3]. \n\n- Data Memorization is a stepping stone towards quantifying the model's ability to generalize to new data [4,5].\n\n\nWe will provide a detailed discussion in our revised version.\n\n> **W3. The results are derived specifically for transformers with ReLU attention, rather than the more commonly used softmax attention. This limits the applicability of the findings to standard transformer architectures.**\n\nIn theoretical analysis, Softmax Transformers are notoriously difficult to deal with. Many existing works resort to the Hardmax function for mathematical simplicity, which can be approximated by the Softmax function [1, 2, 3,]. Besides, some other works utilize the uniform Transformers, in which the self-attention layers are designed to implement the column average operation [9, 10]. ReLU Transformers are also widely used in theoretical works [13,14]. Although ReLU Transformers are not the most common one in practice, some works [11,12] compared the performance of ReLU Transformers and Softmax Transformers on various tasks, finding that ReLU Transformers have the potential to surpass Softmax Transformers on certain tasks. Due to the clear mathematical property of ReLU function and its close relationship with ReLU feed-forward neural networks, we can achieve exactly zero error instead of $\\varepsilon$-error in [1]. Although ReLU Transformers are mathematically simpler, it does not mean that they are more powerful. In Proposition 4.1, we prove that a single layer ReLU Transformer can not implement contextual mapping while a single layer Softmax Transformer can (see Theorem 2 in [15]). Extending our results to Softmax Transformers is a valuable attempt, which is left for our future research.\n\n> **Q1. Regarding the statement \"if the target ReLU neural network presents the low-rank structure, the required prompt length is sharply reduced\": Is this an empirical observation without a formal proof? Since the ReLU network is constructed from the data, what does the assumption of a \"low-rank structure\" imply about the underlying data to be memorized?**\n\n- Yes, it is an empirical observation, but it can also be theoretically proved. Please see section G in our work. Briefly speaking, the prompt length depends on the rank of the concatenation of the weight matrices and bias terms in each layer of the ReLU feed-forward network to be simulated (i.e., rank($[W_i,b_i]$)). If we let each $[W_i,b_i] = UT^{\\top}$, where $U,T$ are rank-1 matrices, our results in Tables 4 and 5 show that $1/10$ prompt length can achieve comparable results. In fact, our results provide a possible explanation of the efficiency of prompt tuning, that is, Transformers with relatively short prompts (less than 100) already present powerful performance (see figure 3a in [17]).\n\n- Some works show that there exists a low-rank structure in the weight matrices in ReLU feed-forward neural networks trained with certain regularization [18]. Besides, some other works propose to approximate weight matrices with low-rank matrices without a decline in accuracy [19,20]. We assume that prompt tuning can implicitly capture this low-rank structure during training, which leads to the satisfying performance of short prompts. This may be a possible explanation for the success of prompt tuning. We did not prove that the ReLU feed-forward neural networks in our construction may be low-rank under some assumptions about the data to be memorized, and the implication about data is not clear up to now, but it is a very interesting direction for future research. However, existing related works are scarce. [21] study the approximation ability of swish neural networks and [22] consider orthogonally separable data from an optimization perspective. Thank the reviewer for this very insightful comment. We will further study that in the future.\n\n> **Q2. It would be helpful to include a brief proof sketch in the main text to aid understanding.**\n\nWe apologize for the confusion caused by our organization of this paper. We will include a proof sketch in our revised version to make it clearer.\n\n> **Q3. The term Autoregressive Generalization is somewhat unclear to me, as it is not obvious what is being generalized in this context./ In the abstract, it is claimed that “a constant-size Transformer with prompts ... can memorize any \n input sequences of length.” However, as stated in the main text, this requires Assumption 4.1 (token-wise separability). I suggest clarifying this condition in the abstract to avoid overstatement.**\n\nIn fact, \"Autoregressive Generalization\" should be written as \"Autoregressive Generation\". We will correct this typo in our revised version. Since we consider discrete finite datasets, the token-wise separability is naturally satisfied, and this is a standard assumption in existing works [10,15]. This assumption does not impose extra limitations on the data but only provides a convenience for mathematics.\n\n## References\n\n [1] Hu, Jerry Yao-Chieh, et al. Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency.\n\n[2] Chulhee Yun, et al. Are transformers universal approximators of sequence-to-sequence functions?\n\n[3] Wang, Yihan, et al. Universality and limitations of prompt tuning.\n\n[4] Chiyuan Zhang, et al. Understanding deep learning requires rethinking generalization.\n\n[5] Preetum Nakkiran, et al. Deep double descent: where bigger models and more data hurt.\n\n[6] Xie, Shangyu, et al. Does prompt-tuning language model ensure privacy?.\n\n[7] Li, Yansong, et al. Privacy-preserving prompt tuning for large language model services. \n\n[8] Hong, Junyuan, et al. Dp-opt: Make large language model your privacy-preserving prompt engineer.\n\n[9] Jiao, Yuling, et al. Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective.\n\n[10] Kajitsuka, Tokio, and Issei Sato. On the optimal memorization capacity of transformers.\n\n[11] Shen, Kai, et al. A study on relu and softmax in transformer.\n\n[12] Wortsman, Mitchell, et al. Replacing softmax with relu in vision transformers.\n\n[13] Havrilla, Alexander, et al. Understanding scaling laws with statistical and approximation theory for transformer neural networks on intrinsically low-dimensional data.\n\n[14] Bai, Yu, et al. Transformers as statisticians: Provable in-context learning with in-context algorithm selection.\n\n[15] Kajitsuka, Tokio, and Issei Sato. Are transformers with one layer self-attention using low-rank weight matrices universal approximators?.\n\n[16] Nakada, Ryumei, et al. A Theoretical Framework for Prompt Engineering: Approximating Smooth Functions with Transformer Prompts.\n\n[17] Lester, Brian, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning.\n\n[18] Kuzborskij, et al. Low-rank bias, weight decay, and model merging in neural networks.\n\n[19] Jian Xue, et al. Restructuring of deep neural network acoustic models with\nsingular value decomposition.\n\n[20] Xiyu Yu, et al. On compressing deep models by\nlow rank and sparse decomposition.\n\n[21] Zimeng Li, et all.Approximation to Smooth Functions by Low-Rank Swish Networks.\n\n[22] Bui Thi Mai, et al. The inductive bias of relu networks on orthogonally separable data."}, {"review_id": "cRXUjHDn0I", "reviewer": "Reviewer_xVXV", "summary": "This paper studies the role that prompts (and prompt tuning) plays in the expressive capacity of transformers. The main paper is fully theoretical with results that outline how to simulate ReLU networks with transformers. They use this framework to show that a constant size transformer can memorize any N sequential data points of length n with prompts whose lengths are $O(sqrt(nN))$ in additional to other theoretical points.", "questions": "- In line 373 you write the prompt length is $O(nN)$ but in theorem 4.1 you claim it is $O(sqrt(nN))$. Is this a typo?\n- Please see additional questions in the \"Strengths and Weaknesses\" section under \"Quality\" and \"Clarity\" for additional questions.", "limitations": "Concisely compiling the limitations in a single subsection in the conclusion would be helpful for the reader.", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Quality:**\n\n- I notice that one of the main claims in the abstract is line 11: \"Our findings, supported by experiments,...\", but no where in the main paper are experiments. The experiments are included in the appendix, but I find it challenging to know which experiments are mean to support which theoretical results in the main paper.\n- I notice in the experimental description in Appendix H.1 line 956: \"Our experiments do not follow Proposition 3.1 exactly in several aspects. First, we discard the Autoregressive algorithm 1 because we find it does not improve performance too much.\". Then why include algorithm 1? And why not modify Proposition 3.1 to exactly match your supporting experiments?\n\n**Clarity:**\n\n- I found the organization of this paper a little tricky to follow since it claims to contain both theoretical and experimental results in the abstract, but the experimental results are not logically organized following the respective theoretical result section in the main text but rather sequestered to the appendix.\n- I did not fully understand what the concrete relationship between section 3 and section 4 is. I understand that transformers can simulate ReLU networks. I also understand that prompts can be structured in such a way that the input output pair exhibits a loss of 0 (memorization), but if/why is this specific to simulating ReLU networks?\n\n**Significance:**\n\n- The motivation for this line of work is: better understanding the role that model context (prompts) play for improving the expressive power of transformers. This style of inquiry helps shape the understanding of transformer failure modes and limits.\n\n**Originality:**\n\n- The scope of this paper is out of my main area of expertise, therefore after reviewing the related work, it seems the authors have built on existing frameworks to simulate ReLU networks using transformers but have introduced new theorems and lemmas.", "was_revised": true, "final_justification": "As detailed in my post-rebuttal discussion, I will raise my score to a 3 for two reasons:\n- As the paper currently stands, and by the reviewing guidelines, the results in this paper are not easy to follow/reproducible without the suggested reorganization provided by the authors. The concern w.r.t. paper organization of both theoretical/emprical results which were shared by myself and reviewer cRMN would require a substantial reorganization ensure this paper is both understandable/reproducible. At the time of submission, the clarity and organization of the paper was below par.\n- I outline some raised concerns during rebuttal below. The theme here is that in practice no one \"tunes\" their prompts when querying their language model. Instead, practically, people study \"memorization\" (achieving zero loss on a model input) by iteratively querying language models on large training corpuses [1]. The authors have written that data memorization is a problem pertaining to privacy, but study a randomly initialized model's ability to \"memorize\" prompts: this is a setting where there is no privacy concern. There is a clear disconnect between what is being studied, and the practical utility of it in informing the true limits of model's ability to memorize a prompt. If instead, the framing was around studying the relationship between model initialization schemes as they pertain to the expressive power of prompts, I think that would be a more straightforward/well-motivated story given the current experimental setup.\n  -  As the authors point out \"We admit that prompt tuning may not be necessarily designed to implement the simulation of ReLU feed-forward neural networks, some other potential effects will be studied in the future\"\n  -  reviewer QVYe points out \"It is unclear what, if any, practical takeaway there is here for those who are still using prompt tuning today\"\n  -  reviewer URsx points out \"Using prompt tuning as a means to memorize arbitrary data seems somewhat unnatural. It would strengthen the paper to include a discussion of real-world scenarios where such a setup is relevant, to better motivate the problem.\"", "rebuttal": "Thank you for taking the time to review our paper and sharing your insightful comments! We address some of your concerns below.\n\n> **W1. I notice that one of the main claims in the abstract is line 11: \"Our findings, supported by experiments,...\", but no where in the main paper are experiments. The experiments are included in the appendix, but I find it challenging to know which experiments are mean to support which theoretical results in the main paper.**\n\nWe apologize for the organization of this paper, and this will be modified in our revised version following your comments. We provide a brief outline of our experiments here:\n\n- Table 1 and Table 2 study the Transformer simulation for deep ReLU neural networks and shallow ones, finding that deep neural networks are much easier to simulate than shallow ones. This experiment supports Proposition 3.1 in our work.\n\n- Table 3 explores the relationship between the Transformer simulation for shallow ReLU neural network and the embedding size, finding that the embedding size becomes the bottleneck rather than the prompt length when simulating shallow ReLU neural networks. This supports our Remark 3.4. \n\n- Table 4 and 5 show that the prompt length is sharply reduced when simulating ReLU neural networks with a low-rank structure in the weight matrices. Only $1/10$ prompt length is needed to achieve similar performance. This verifies our discussion in Section G.\n\n- Table 6 and 7 compare the performance of prompt tuning and training from scratch on a real-world dataset when the embedding size is chosen to be $256$, finding that prompt tuning can only achieve inferior performance. This also verifies our discussion in Section G. This supports our Theorem 4.1.\n\n- Table 8 and 9 compare the performance of prompt tuning and training from scratch on a real-world dataset when the embedding size is chosen to be $16$, finding that prompt tuning performs better than training from scratch when the embedding size is small.\n\n> **W2. I notice in the experimental description in Appendix H.1 line 956: \"Our experiments do not follow Proposition 3.1 exactly in several aspects. First, we discard the Autoregressive algorithm 1 because we find it does not improve performance too much.\". Then why include algorithm 1? And why not modify Proposition 3.1 to exactly match your supporting experiments?**\n\nAutoregressive algorithm is the key technique that can help us prove the data memorization ability of prompt tuning a fixed size Transformer and it shows the powerful parameter sharing property of Transformer architecture. However, we find that the computational burden is unbearable in practice and that is why we did not utilize the same setting in Proposition 3.1. It is important to note that we always use a simpler setting in our experiments than those in theories and find that the results are already satisfying. Since our theories are all constructive, meaning that gradient-based optimization methods may not always find the required weight configurations. We hope the reviewer could understand the gap between theoretical proofs and experiments is inevitable. Actually, our work provide a possible analysis of prompt tuning, which may explain its success in practice. Some insights coming from our theoretical comtributions may guide the empirical study, such as, low-rank structure can reduce the prompt length, etc. To fully understand data memorization ability of prompt tuning, other factors like the optimization dynamics have to be considered in the meantime, which is left for future research and we will include this in our limitation section.\n\n> **W3. I found the organization of this paper a little tricky to follow since it claims to contain both theoretical and experimental results in the abstract, but the experimental results are not logically organized following the respective theoretical result section in the main text but rather sequestered to the appendix.**\n\nWe apologize for the confusion caused by the organization of this paper. We will polish it in our revised version, and we provide an outline of our experiments in the answer of **W1**, hoping this may help the reviewer understand our paper. Thanks for your time and patience again. Every comment and feedback will make our paper clearer and better.\n\n> **W4. I did not fully understand what the concrete relationship between section 3 and section 4 is. I understand that transformers can simulate ReLU networks. I also understand that prompts can be structured in such a way that the input output pair exhibits a loss of 0 (memorization), but if/why is this specific to simulating ReLU networks?**\n\nIn our work, Section 3 explores the Transformer simulation for ReLU feed-forward neural networks, that is, given the same input, there exist proper prompts such that the Transformer can output the same output as the target ReLU feed-forward neural network. In Section 4, we study the data memorization ability of prompt-tuning Transformers. The connection between Section 3 and Section 4 is that in the analysis of data memorization, ReLU feed-forward neural networks are necessary, prompt tuning here replaces all the ReLU feed-forward neural networks. We admit that prompt tuning may not be necessarily designed to implement the simulation of ReLU feed-forward neural networks, some other potential effects will be studied in the future. We will provide a discussion about the effects of prompt tuning in the revised version.\n\n> **Q1. In line 373 you write the prompt length is $\\tilde{O}(nN)$ but in theorem 4.1 you claim it is $\\tilde{O}(\\sqrt{nN})$ . Is this a typo?**\n\nYes, this is indeed a typo, and the correct one is $\\tilde{O}(\\sqrt{nM})$. We apologize for this mistake and this will be modified in our revised version."}]

Author rebuttal:

Meta-review: In this work, the authors show that a single-layer randomly initialized Transformer with prompts possess competitive data memorization ability compared with models trained from scratch. The work builds on prior work to provide novel theoretical results to narrower ReLU nets, an upper bound on the prompt length for which a constant-size transformer can memorize data.

Most reviewers were positive about this work. Post rebuttal they indicated that
- The paper provides theoretical insight on data memorization in prompt tuning, extending on past work. The reviewer was satisfied iwth the answers provided by the authors during the rebuttal, addressing concerns regarding practicality and empirical evaluations.
- The paper provided the first upper bound on prompt length for constant-size Transformers and explaining the trade-off between prompt length and efficiency. The reviewer also indicated that the paper readability could be improved.
- The paper extends prior results in a meaningful, albeit limited way. The reviewer also found the practical relevance and assumptions credible post rebuttal discussion.

The less positive reviewer raised their score (to borderline reject), indicating that they would like to see the paper being reorganised to be more easy to follow. One of the more positive reviewers echoed that. I'd encourage the authors to revise the paper to make it more accessible. The reviewer also remained critical about the framing and suggested studying the relationship between model initialization schemes given the current experimental setup instead. While this a valid direction to consider, it is IMO beyond the scope of the current submission.
Decision: Accept (poster)