본 논문은 Transformer 기반 기초 모델에서 프롬프트 튜닝의 통계적 및 계산적 한계를 조사합니다. 단일 헤드, 단일 셀프 어텐션 레이어를 가진 Transformer에서의 프롬프트 튜닝이 (i) 보편적이며 (ii) 강한 지수 시간 가설(SETH) 하에서 효율적인 (거의 선형 시간) 알고리즘을 지원함을 보여줍니다. 통계적으로, 이러한 가장 단순한 Transformer에서의 프롬프트 튜닝이 시퀀스-투-시퀀스 Lipschitz 함수에 대한 보편적 근사기임을 증명합니다. 또한, 1-레이어, 1-헤드 Transformer로 어떤 데이터셋이라도 암기하기 위해 필요한 소프트 프롬프트 토큰에 대한 지수적($dL$ 및 $(1/\epsilon)$) 하한을 제공합니다. 계산적으로, 소프트 프롬프트에 의해 유도된 키와 쿼리의 노름에 의해 결정되는 프롬프트 튜닝 효율성의 상전이를 확인하고, 상한 기준을 제공합니다. 이 기준을 넘어서는 경우, SETH 하에서 프롬프트 튜닝을 위한 하위 2차(효율적인) 알고리즘은 존재하지 않습니다. 이 기준 내에서, 거의 선형 시간 프롬프트 튜닝 추론 알고리즘의 존재를 증명함으로써 이론을 보여줍니다. 이러한 기본적인 한계는 실무자를 위한 표현력 있고 효율적인 프롬프트 튜닝 방법을 설계하기 위한 중요한 필요 조건을 제공합니다.