Limites Computacionais da Adaptação de Baixa Classificação (LoRA) para Modelos Baseados em Transformer

Estudamos os limites computacionais da atualização da Adaptação de Baixa Classificação (LoRA) para ajuste fino de modelos baseados em transformer utilizando teoria da complexidade detalhada. Nossa principal observação é que a existência de decomposições de baixa classificação dentro da computação de gradiente da adaptação LoRA leva a um possível aumento de velocidade algorítmica. Isso nos permite (i) identificar um comportamento de transição de fase e (ii) provar a existência de algoritmos quase lineares controlando a computação da atualização LoRA termo a termo, assumindo a Hipótese do Tempo Exponencial Forte (SETH). Para o primeiro, identificamos uma transição acentuada na eficiência de todos os possíveis algoritmos de atualização LoRA de classificação-r para transformers, com base em normas específicas resultantes das multiplicações da sequência de entrada X, pesos pré-treinados W^ e matrizes de adaptadores B A / r. Especificamente, derivamos um limite superior compartilhado para tais normas e mostramos que algoritmos de aproximação eficientes (sub-quadráticos) da LoRA existem apenas abaixo deste limite. Para o último, provamos a existência de algoritmos de aproximação quase lineares para a adaptação LoRA utilizando as estruturas hierárquicas de baixa classificação dos gradientes LoRA e aproximando os gradientes com uma série de aproximações de baixa classificação encadeadas. Para demonstrar nossa teoria, consideramos dois cenários práticos: adaptações parciais (por exemplo, apenas WV e WQ) e adaptações completas (por exemplo, WQ, WV e WK) de pesos em cabeçotes de atenção.