Algorithm

1. ShiftAddLLM Accelerating Pretrained LLMs via Post-Training Multiplication-Less Reparameterization

Abstract

ShiftAddLLM의 핵심 목적은 Pretrained LLM에서 비용이 큰 Multiplication을 제거하여 Memory, Latency, Energy를 줄이는 것이다.

기존 LLM은 매우 많은 Parameter를 가지고 있으며, Attention과 MLP에서 대규모 Matrix Multiplication을 반복적으로 수행한다.

즉 LLM Inference의 주요 비용은 크게

$$ \text{Large Parameter Size} + \text{Dense Multiplication} $$

으로 볼 수 있다.

기존 Quantization은 Weight의 Bit-width를 줄여 Memory 사용량을 감소시키는 데 효과적이지만, 실제 계산 과정에서 Multiplication 자체는 여전히 남을 수 있다.

ShiftAddLLM은 이 문제를 해결하기 위해 Weight Matrix를 다음과 같이 Binary Matrix와 Scaling Factor의 조합으로 표현한다.

$$ W \approx \sum_{i=1}^{q}\alpha_i B_i $$

여기서

• $B_i$: Binary Matrix
• $\alpha_i$: Scaling Factor

이다.

그리고 기존 Multiplication을 다음 연산으로 변환한다.

$$ \boxed{ \text{Multiplication} \rightarrow \text{Shift + LUT Query + Add} } $$