본 논문은 미세 조정을 위한 저랭크 적응(LoRA)의 계산적 한계를 미세 입자 복잡도 이론을 사용하여 연구합니다. LoRA 적응의 기울기 계산 내에 저랭크 분해의 존재는 알고리즘 속도 향상을 가능하게 한다는 주요 관찰 결과를 바탕으로, 강한 지수 시간 가설(SETH)을 가정하여 효율성의 상전이 동작을 확인하고, LoRA 업데이트 계산을 항별로 제어하여 거의 선형 알고리즘의 존재를 증명합니다. 특히, 입력 시퀀스 X, 사전 훈련된 가중치 W*, 그리고 어댑터 행렬 αBA/r의 곱셈으로부터 생성되는 특정 규범을 기반으로, 모든 가능한 rank-r LoRA 업데이트 알고리즘의 효율성에서 급격한 전환을 확인하고, 이러한 규범에 대한 공유 상한 임계값을 도출하여 이 임계값 이하에서만 LoRA의 효율적인 (sub-quadratic) 근사 알고리즘이 존재함을 보여줍니다. 또한, LoRA 기울기의 계층적 저랭크 구조를 활용하고 일련의 연결된 저랭크 근사를 사용하여 기울기를 근사함으로써 LoRA 적응을 위한 거의 선형 근사 알고리즘의 존재를 증명합니다. 이론을 보여주기 위해 부분적 (예: W_V 및 W_Q만) 및 전체적 (예: W_Q, W_V 및 W_K) 어텐션 헤드 가중치 적응의 두 가지 실질적인 시나리오를 고려합니다.
