Prompt Tuning Transformers for Data Memorization
Haiyu Wang, Yuanyuan Lin
One research direction for understanding Transformers' representational capacity involves quantifying their data memorization ability. However, the memorization capacity of Transformers with prompts is not yet well understood. In this work, we extend the existing results on prompt tuning Transformers to simulate ReLU neural networks with the Autoregressive algorithm in \citep{nakada2025theoretical} to a more general case where the width of the ReLU neural network can be a small constant. Based on this, we prove that a constant-size Transformer with prompts whose length is $\tilde{O}(\sqrt{nN})$ can memorize any $N$ input sequence of length $n$. Our results discard the reliance on large feed-forward layers. Besides, we also theoretically prove that a trade-off exists between the prompt length and computational efficiency. Our findings, supported by experiments, demonstrate that a single-layer randomly initialized Transformer with prompts can possess competitive data memorization ability compared with models trained from scratch. In addition, we validate that the prompt length is potentially reduced if the low-rank structure exists.